1// Tests of the pure core of the file finder (static/js/files.js). Run with
2// node --test 'internal/adapters/web/jstest/*.test.mjs'
3import assert from 'node:assert/strict';
4import { test } from 'node:test';
5
6globalThis.window = globalThis;
7await import('../static/js/files.js');
8const F = window.ermiteFinder;
9
10const REPO = [
11 'README.md',
12 'cmd/ermite/main.go',
13 'internal/adapters/web/tree.go',
14 'internal/adapters/web/tree.templ',
15 'internal/adapters/web/tree_templ.go',
16 'internal/adapters/web/static/css/30-list.css',
17 'internal/adapters/web/static/js/files.js',
18 'internal/adapters/web/jstest/files.test.mjs',
19 'internal/adapters/gitcli/read.go',
20 'internal/domain/tree_path.go',
21 'docs/web/tree-view.md',
22 'src/deeply/nested/dir/with/a/treehouse.txt',
23];
24const idx = F.index(REPO);
25const top = (q, k = 50, prev = null) => F.search(idx, q, k, prev);
26const names = (r) => r.hits.map((h) => REPO[h.i]);
27
28test('search: rejects what is not a subsequence', () => {
29 assert.deepEqual(names(top('zzz')), []);
30 assert.deepEqual(names(top('gnirt')), [], 'order matters');
31 assert.equal(top('zzz').all.length, 0);
32 assert.deepEqual(names(top('')), []);
33 assert.deepEqual(names(top(' ')), []);
34 assert.equal(top('q').all.length, 0, 'a character no path has');
35});
36
37test('search: ranking', () => {
38 const r = names(top('tree'));
39 assert.ok(r.indexOf('internal/adapters/web/tree.go') >= 0);
40 assert.ok(r.indexOf('internal/adapters/web/tree.go') < r.indexOf('internal/adapters/web/static/css/30-list.css'),
41 'basename match beats a scattered one: ' + r.join(', '));
42 // Equal scores: the shorter path first, then the path.
43 assert.ok(r.indexOf('internal/adapters/web/tree.go') < r.indexOf('internal/adapters/web/tree.templ'), r.join(', '));
44 assert.ok(r.indexOf('internal/adapters/web/tree.templ') < r.indexOf('internal/adapters/web/tree_templ.go'), r.join(', '));
45 assert.ok(r.indexOf('internal/adapters/web/tree.templ') < r.indexOf('src/deeply/nested/dir/with/a/treehouse.txt'), r.join(', '));
46});
47
48test('search: wbtree matches web/tree.templ', () => {
49 const r = names(top('wbtree'));
50 assert.ok(r.includes('internal/adapters/web/tree.templ'), r.join(', '));
51 assert.ok(r.includes('internal/adapters/web/tree.go'));
52});
53
54test('search: basename prefix beats a deep match', () => {
55 const x = F.index(['a/b/c/d/e/main_helper.go', 'x/m/a/i/n.go', 'main.go', 'pkg/domain/admin.go']);
56 const r = F.search(x, 'main').hits.map((h) => x.paths[h.i]);
57 assert.equal(r[0], 'main.go');
58 assert.ok(r.indexOf('a/b/c/d/e/main_helper.go') < r.indexOf('x/m/a/i/n.go'), r.join(', '));
59 assert.ok(r.indexOf('a/b/c/d/e/main_helper.go') < r.indexOf('pkg/domain/admin.go'), r.join(', '));
60});
61
62test('search: camelCase and separators earn bonuses', () => {
63 const x = F.index(['pkg/fooBarBaz.go', 'pkg/foobarbaz.go', 'pkg/fxoxoxbxa.go']);
64 const r = F.search(x, 'fbb').hits.map((h) => x.paths[h.i]);
65 assert.equal(r[0], 'pkg/fooBarBaz.go', r.join(', '));
66});
67
68test('search: several terms', () => {
69 const r = names(top('web tree'));
70 assert.ok(r.length > 0);
71 assert.ok(r.slice(0, 3).every((p) => p.includes('web') && p.includes('tree')), r.join(', '));
72 assert.ok(!r.includes('README.md'));
73 // Every term must match.
74 assert.deepEqual(names(top('web zzz')), []);
75 // The order of the terms is free.
76 assert.deepEqual(new Set(names(top('tree web'))), new Set(names(top('web tree'))));
77});
78
79test('search: top k, ties by length then path', () => {
80 const ps = [];
81 for (let i = 0; i < 200; i++) ps.push('d/file' + i + '.txt');
82 const x = F.index(ps);
83 const r = F.search(x, 'file', 50);
84 assert.equal(r.hits.length, 50);
85 assert.equal(r.all.length, 200);
86 const got = r.hits.map((h) => x.paths[h.i]);
87 for (let i = 1; i < got.length; i++) {
88 const a = got[i - 1];
89 const b = got[i];
90 assert.ok(a.length < b.length || (a.length === b.length && a < b), a + ' before ' + b);
91 }
92 assert.equal(got[0], 'd/file0.txt');
93});
94
95test('search: incremental results equal a cold search', () => {
96 const big = [];
97 let seed = 7;
98 const rnd = () => (seed = (seed * 1103515245 + 12345) & 0x7fffffff) / 0x7fffffff;
99 const words = ['web', 'tree', 'file', 'test', 'main', 'util', 'core', 'index', 'view', 'model'];
100 for (let i = 0; i < 3000; i++) {
101 const depth = 1 + Math.floor(rnd() * 4);
102 const segs = [];
103 for (let d = 0; d < depth; d++) segs.push(words[Math.floor(rnd() * words.length)] + (rnd() < 0.3 ? 'Case' : '') + Math.floor(rnd() * 20));
104 big.push(segs.join('/') + ['.go', '.js', '.md'][Math.floor(rnd() * 3)]);
105 }
106 const x = F.index(big);
107 const queries = ['t', 'tr', 'tre', 'tree', 'tree w', 'tree we', 'tree web', 'tre web', 'tree web m'];
108 let prev = null;
109 for (const q of queries) {
110 const warm = F.search(x, q, 50, prev);
111 const cold = F.search(x, q, 50, null);
112 assert.deepEqual(warm.hits, cold.hits, q);
113 assert.deepEqual(Array.from(warm.all), Array.from(cold.all), q);
114 prev = warm;
115 }
116 // A query that does not extend the previous one searches everything.
117 const a = F.search(x, 'tree', 50, null);
118 assert.deepEqual(F.search(x, 'web', 50, a).hits, F.search(x, 'web', 50, null).hits);
119 assert.deepEqual(F.search(x, 'tre', 50, a).hits, F.search(x, 'tre', 50, null).hits, 'shortening');
120 // A result of another index is not a source of candidates.
121 const y = F.index(['zzz']);
122 assert.deepEqual(F.search(y, 'z', 50, a).hits.length, 1);
123});
124
125test('positions', () => {
126 const p = 'internal/adapters/web/tree.go';
127 const x = F.index([p]);
128 assert.deepEqual(F.positions(x, 0, 'tree'), [p.indexOf('tree.go'), p.indexOf('tree.go') + 1, p.indexOf('tree.go') + 2, p.indexOf('tree.go') + 3]);
129 const y = F.index(['internal/adapters/web/tree.templ']);
130 const pos = F.positions(y, 0, 'wbtree');
131 const s = y.paths[0];
132 assert.equal(pos.map((i) => s[i]).join(''), 'wbtree');
133 assert.deepEqual(pos, [...pos].sort((a, b) => a - b));
134 assert.equal(pos[0], s.indexOf('web'), 'w of the web directory');
135 // Two terms.
136 const z = F.index(['src/web/tree.go']);
137 const both = F.positions(z, 0, 'web tree');
138 assert.equal(both.map((i) => z.paths[0][i]).join(''), 'webtree');
139});
140
141// Case is folded for A-Z only, and a position is an index of the original
142// string; both are seen through search and positions.
143test('non-ASCII paths: ASCII-only folding, positions index the original', () => {
144 const cases = [
145 // path, query, the characters the query marks (null: no match)
146 ['İndex/Straße.go', 'index', null], // İ is not an ASCII capital I
147 ['İndex/Straße.go', 'ndex', 'ndex'],
148 ['İndex/Straße.go', 'stra', 'Stra'],
149 ['İndex/Straße.go', 'strasse', null], // ß is not ss
150 ['ABC/Def.TXT', 'abc/def.txt', 'ABC/Def.TXT'],
151 ['README.md', 'readme', 'README'],
152 ['README.md', 'README', 'README'],
153 ];
154 for (const [path, q, want] of cases) {
155 const x = F.index([path]);
156 const r = F.search(x, q);
157 const pos = F.positions(x, 0, q);
158 if (want === null) {
159 assert.equal(r.hits.length, 0, `${q} in ${path}`);
160 assert.deepEqual(pos, [], `${q} in ${path}: nothing is claimed`);
161 } else {
162 assert.equal(r.hits.length, 1, `${q} in ${path}`);
163 assert.equal(pos.map((i) => path[i]).join(''), want, `${q} in ${path}`);
164 }
165 }
166 assert.equal(F.positions(F.index(['İndex/Straße.go']), 0, 'ndex')[0], 1, 'the İ before it counts as one');
167});
168
169test('positions of a long path (greedy)', () => {
170 const long = 'a/'.repeat(600) + 'target.txt';
171 const x = F.index([long]);
172 const r = F.search(x, 'target');
173 assert.equal(r.hits.length, 1);
174 const pos = F.positions(x, 0, 'target');
175 assert.equal(pos.map((i) => long[i]).join(''), 'target');
176});
177
178test('visible', () => {
179 assert.equal(F.visible('a\u202eb'), 'a<U+202E>b');
180 assert.equal(F.visible('x\u200by'), 'x<U+200B>y');
181 assert.equal(F.visible('a\u0007b'), 'a<U+0007>b');
182 assert.equal(F.visible('\u3164'), '<U+3164>');
183 assert.equal(F.visible('\u2028'), '<U+2028>');
184 assert.equal(F.visible('plain/ünï.go'), 'plain/ünï.go');
185 assert.equal(F.visible('tab\tname'), 'tab<U+0009>name', 'the finder shows a control character; Go refuses such paths anyway');
186});
187
188test('performance on 100,000 paths (AC6)', () => {
189 const dirs = ['internal', 'cmd', 'pkg', 'src', 'lib', 'docs', 'test', 'web', 'adapters', 'domain', 'app', 'static'];
190 const names = ['tree', 'blob', 'commit', 'diff', 'index', 'main', 'util', 'handler', 'service', 'reader', 'writer', 'config'];
191 const exts = ['.go', '.js', '.md', '.templ', '.css', '.txt'];
192 const paths = [];
193 for (let i = 0; paths.length < 100000; i++) {
194 const d = [dirs[i % 12], dirs[(i * 7) % 12], dirs[(i * 13 + 5) % 12], 'pkg' + (i % 311)];
195 paths.push(d.join('/') + '/' + names[(i * 5) % 12] + '_' + (i % 977) + names[(i >> 3) % 12] + exts[i % 6]);
196 }
197 let t0 = performance.now();
198 const x = F.index(paths);
199 const build = performance.now() - t0;
200
201 const timings = [];
202 let prev = null;
203 let worst = 0;
204 for (const q of ['t', 'tr', 'tre', 'tree', 'tree h', 'wbtree', 'internal handler', 'zzzq']) {
205 t0 = performance.now();
206 const r = F.search(x, q, 50, prev);
207 const ms = performance.now() - t0;
208 worst = Math.max(worst, ms);
209 timings.push(q + ': ' + ms.toFixed(1) + ' ms (' + r.all.length + ' matches)');
210 prev = r;
211 }
212 // The cold query of a single character is the worst case: every path matches.
213 t0 = performance.now();
214 F.search(x, 'e');
215 const cold = performance.now() - t0;
216 t0 = performance.now();
217 F.search(x, 'inthand');
218 const cold2 = performance.now() - t0;
219 t0 = performance.now();
220 const r = F.search(x, 'tree h');
221 for (const h of r.hits) F.positions(x, h.i, 'tree h');
222 const withPos = performance.now() - t0;
223 console.log(`AC6 index of ${paths.length} paths: ${build.toFixed(1)} ms (target < 150, asserted < 1500)`);
224 console.log(`AC6 queries (incremental): ${timings.join('; ')}`);
225 console.log(`AC6 cold 'e': ${cold.toFixed(1)} ms; cold 'inthand': ${cold2.toFixed(1)} ms; 'tree h' with positions of the hits: ${withPos.toFixed(1)} ms (target < 30, asserted < 300)`);
226 assert.ok(build < 1500, 'index ' + build);
227 assert.ok(Math.max(worst, cold, cold2, withPos) < 300, 'query ' + Math.max(worst, cold, cold2, withPos));
228});
229
230// ---- a brute-force reference of the scoring --------------------------------
231
232// The reference tries every placement of the term in the path and scores it by
233// the documented rules; the DP of files.js must find the same best score.
234function refBonus(orig, j) {
235 if (j === 0) return 10;
236 const p = orig[j - 1];
237 const c = orig[j];
238 if (p === '/') return 10;
239 if ('_-. '.includes(p)) return 8;
240 const upper = c >= 'A' && c <= 'Z';
241 const lower = c >= 'a' && c <= 'z';
242 if (p >= 'a' && p <= 'z' && upper) return 7;
243 if (p >= '0' && p <= '9' && (upper || lower)) return 7;
244 return 0;
245}
246
247function refPlacement(orig, pos) {
248 let score = 0;
249 pos.forEach((j, i) => {
250 const b = refBonus(orig, j);
251 score += 16 + (i === 0 ? 2 * b : b);
252 if (i > 0) {
253 const gap = j - pos[i - 1] - 1;
254 score += gap === 0 ? Math.max(b, 4) : -(gap + 2);
255 }
256 });
257 return score;
258}
259
260// refBest is the best score of the placements of t at or after from (null: none).
261function refBest(orig, lower, t, from) {
262 let best = null;
263 const go = (i, start, pos) => {
264 if (i === t.length) {
265 const sc = refPlacement(orig, pos);
266 if (best === null || sc > best) best = sc;
267 return;
268 }
269 for (let j = start; j < lower.length; j++) if (lower[j] === t[i]) go(i + 1, j + 1, [...pos, j]);
270 };
271 go(0, from, []);
272 return best;
273}
274
275function refTerm(orig, t, isLast) {
276 const lower = orig.replace(/[A-Z]/g, (c) => c.toLowerCase());
277 const all = refBest(orig, lower, t, 0);
278 if (all === null) return null;
279 if (!isLast) return all;
280 const base = orig.lastIndexOf('/') + 1;
281 let best = all;
282 if (base === 0) best += 24;
283 else {
284 const r = refBest(orig, lower, t, base);
285 if (r !== null && r + 24 > best) best = r + 24;
286 }
287 if (lower.startsWith(t, base)) best += 16;
288 return best;
289}
290
291test('search and positions agree with a brute-force reference', () => {
292 let seed = 12345;
293 const rnd = (n) => {
294 seed = (Math.imul(seed, 1103515245) + 12345) & 0x7fffffff;
295 return Math.floor((seed / 0x80000000) * n);
296 };
297 const alphabet = 'abcabcABC//..__-1';
298 const paths = new Set();
299 while (paths.size < 3000) {
300 let p = '';
301 for (let n = 1 + rnd(14); n > 0; n--) p += alphabet[rnd(alphabet.length)];
302 paths.add(p);
303 }
304 const list = Array.from(paths);
305 const x = F.index(list);
306 const queries = [];
307 for (let n = 0; n < 40; n++) {
308 let q = '';
309 for (let k = 1 + rnd(3); k > 0; k--) q += 'abc/._-1'[rnd(8)];
310 queries.push(q);
311 }
312 for (let n = 0; n < 20; n++) queries.push('ab'[rnd(2)] + 'c/.'[rnd(3)] + ' ' + 'abc'[rnd(3)] + 'a_'[rnd(2)]);
313 let compared = 0;
314 for (const q of queries) {
315 const terms = q.split(/\s+/).filter(Boolean);
316 const res = F.search(x, q, list.length);
317 const got = new Map(res.hits.map((h) => [h.i, h.score]));
318 for (let i = 0; i < list.length; i++) {
319 let total = 0;
320 for (let n = 0; n < terms.length && total !== null; n++) {
321 const sc = refTerm(list[i], terms[n], n === terms.length - 1);
322 total = sc === null ? null : total + sc;
323 }
324 if (total === null) {
325 assert.ok(!got.has(i), `${q}: ${list[i]} cannot match`);
326 continue;
327 }
328 assert.equal(got.get(i), total, `${q}: score of ${list[i]}`);
329 compared++;
330 if (terms.length === 1) {
331 // The positions are a placement of the term that scores the best.
332 const pos = F.positions(x, i, q);
333 assert.equal(pos.map((j) => list[i][j]).join('').toLowerCase(), terms[0], `${q}: characters of ${list[i]}`);
334 const lower = list[i].toLowerCase();
335 const base = list[i].lastIndexOf('/') + 1;
336 const all = refBest(list[i], lower, terms[0], 0);
337 const inBase = base === 0 ? null : refBest(list[i], lower, terms[0], base);
338 const want = inBase !== null && inBase + 24 > all ? inBase : all;
339 assert.equal(refPlacement(list[i], pos), want, `${q}: placement of ${list[i]}`);
340 }
341 }
342 }
343 assert.ok(compared > 2000, 'compared ' + compared);
344});