Skip to content

Commit ee784bf

Browse files
committed
Add fuzzy workspace entry search
1 parent 5a90b6b commit ee784bf

2 files changed

Lines changed: 186 additions & 31 deletions

File tree

‎apps/server/src/workspaceEntries.test.ts‎

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -70,6 +70,32 @@ describe("searchWorkspaceEntries", () => {
7070
assert.isTrue(result.entries.every((entry) => entry.path.toLowerCase().includes("compo")));
7171
});
7272

73+
it("supports fuzzy subsequence queries for composer path search", async () => {
74+
const cwd = makeTempDir("t3code-workspace-fuzzy-query-");
75+
writeFile(cwd, "src/components/Composer.tsx");
76+
writeFile(cwd, "src/components/composePrompt.ts");
77+
writeFile(cwd, "docs/composition.md");
78+
79+
const result = await searchWorkspaceEntries({ cwd, query: "cmp", limit: 10 });
80+
const paths = result.entries.map((entry) => entry.path);
81+
82+
assert.isAbove(result.entries.length, 0);
83+
assert.include(paths, "src/components");
84+
assert.include(paths, "src/components/Composer.tsx");
85+
});
86+
87+
it("tracks truncation without sorting every fuzzy match", async () => {
88+
const cwd = makeTempDir("t3code-workspace-fuzzy-limit-");
89+
writeFile(cwd, "src/components/Composer.tsx");
90+
writeFile(cwd, "src/components/composePrompt.ts");
91+
writeFile(cwd, "docs/composition.md");
92+
93+
const result = await searchWorkspaceEntries({ cwd, query: "cmp", limit: 1 });
94+
95+
assert.lengthOf(result.entries, 1);
96+
assert.isTrue(result.truncated);
97+
});
98+
7399
it("excludes gitignored paths for git repositories", async () => {
74100
const cwd = makeTempDir("t3code-workspace-gitignore-");
75101
runGit(cwd, ["init"]);

‎apps/server/src/workspaceEntries.ts‎

Lines changed: 160 additions & 31 deletions
Original file line numberDiff line numberDiff line change
@@ -28,10 +28,20 @@ const IGNORED_DIRECTORY_NAMES = new Set([
2828

2929
interface WorkspaceIndex {
3030
scannedAt: number;
31-
entries: ProjectEntry[];
31+
entries: SearchableWorkspaceEntry[];
3232
truncated: boolean;
3333
}
3434

35+
interface SearchableWorkspaceEntry extends ProjectEntry {
36+
normalizedPath: string;
37+
normalizedName: string;
38+
}
39+
40+
interface RankedWorkspaceEntry {
41+
entry: SearchableWorkspaceEntry;
42+
score: number;
43+
}
44+
3545
const workspaceIndexCache = new Map<string, WorkspaceIndex>();
3646
const inFlightWorkspaceIndexBuilds = new Map<string, Promise<WorkspaceIndex>>();
3747

@@ -55,27 +65,136 @@ function basenameOf(input: string): string {
5565
return input.slice(separatorIndex + 1);
5666
}
5767

68+
function toSearchableWorkspaceEntry(entry: ProjectEntry): SearchableWorkspaceEntry {
69+
const normalizedPath = entry.path.toLowerCase();
70+
return {
71+
...entry,
72+
normalizedPath,
73+
normalizedName: basenameOf(normalizedPath),
74+
};
75+
}
76+
5877
function normalizeQuery(input: string): string {
5978
return input
6079
.trim()
6180
.replace(/^[@./]+/, "")
6281
.toLowerCase();
6382
}
6483

65-
function scoreEntry(entry: ProjectEntry, query: string): number {
84+
function scoreSubsequenceMatch(value: string, query: string): number | null {
85+
if (!query) return 0;
86+
87+
let queryIndex = 0;
88+
let firstMatchIndex = -1;
89+
let previousMatchIndex = -1;
90+
let gapPenalty = 0;
91+
92+
for (let valueIndex = 0; valueIndex < value.length; valueIndex += 1) {
93+
if (value[valueIndex] !== query[queryIndex]) {
94+
continue;
95+
}
96+
97+
if (firstMatchIndex === -1) {
98+
firstMatchIndex = valueIndex;
99+
}
100+
if (previousMatchIndex !== -1) {
101+
gapPenalty += valueIndex - previousMatchIndex - 1;
102+
}
103+
104+
previousMatchIndex = valueIndex;
105+
queryIndex += 1;
106+
if (queryIndex === query.length) {
107+
const spanPenalty = valueIndex - firstMatchIndex + 1 - query.length;
108+
const lengthPenalty = Math.min(64, value.length - query.length);
109+
return firstMatchIndex * 2 + gapPenalty * 3 + spanPenalty + lengthPenalty;
110+
}
111+
}
112+
113+
return null;
114+
}
115+
116+
function scoreEntry(entry: SearchableWorkspaceEntry, query: string): number | null {
66117
if (!query) {
67118
return entry.kind === "directory" ? 0 : 1;
68119
}
69120

70-
const normalizedPath = entry.path.toLowerCase();
71-
const normalizedName = basenameOf(normalizedPath);
121+
const { normalizedPath, normalizedName } = entry;
72122

73123
if (normalizedName === query) return 0;
74124
if (normalizedPath === query) return 1;
75125
if (normalizedName.startsWith(query)) return 2;
76126
if (normalizedPath.startsWith(query)) return 3;
77127
if (normalizedPath.includes(`/${query}`)) return 4;
78-
return 5;
128+
if (normalizedName.includes(query)) return 5;
129+
if (normalizedPath.includes(query)) return 6;
130+
131+
const nameFuzzyScore = scoreSubsequenceMatch(normalizedName, query);
132+
if (nameFuzzyScore !== null) {
133+
return 100 + nameFuzzyScore;
134+
}
135+
136+
const pathFuzzyScore = scoreSubsequenceMatch(normalizedPath, query);
137+
if (pathFuzzyScore !== null) {
138+
return 200 + pathFuzzyScore;
139+
}
140+
141+
return null;
142+
}
143+
144+
function compareRankedWorkspaceEntries(
145+
left: RankedWorkspaceEntry,
146+
right: RankedWorkspaceEntry,
147+
): number {
148+
const scoreDelta = left.score - right.score;
149+
if (scoreDelta !== 0) return scoreDelta;
150+
return left.entry.path.localeCompare(right.entry.path);
151+
}
152+
153+
function findInsertionIndex(
154+
rankedEntries: RankedWorkspaceEntry[],
155+
candidate: RankedWorkspaceEntry,
156+
): number {
157+
let low = 0;
158+
let high = rankedEntries.length;
159+
160+
while (low < high) {
161+
const middle = low + Math.floor((high - low) / 2);
162+
const current = rankedEntries[middle];
163+
if (!current) {
164+
break;
165+
}
166+
167+
if (compareRankedWorkspaceEntries(candidate, current) < 0) {
168+
high = middle;
169+
} else {
170+
low = middle + 1;
171+
}
172+
}
173+
174+
return low;
175+
}
176+
177+
function insertRankedEntry(
178+
rankedEntries: RankedWorkspaceEntry[],
179+
candidate: RankedWorkspaceEntry,
180+
limit: number,
181+
): void {
182+
if (limit <= 0) {
183+
return;
184+
}
185+
186+
const insertionIndex = findInsertionIndex(rankedEntries, candidate);
187+
if (rankedEntries.length < limit) {
188+
rankedEntries.splice(insertionIndex, 0, candidate);
189+
return;
190+
}
191+
192+
if (insertionIndex >= limit) {
193+
return;
194+
}
195+
196+
rankedEntries.splice(insertionIndex, 0, candidate);
197+
rankedEntries.pop();
79198
}
80199

81200
function isPathInIgnoredDirectory(relativePath: string): boolean {
@@ -253,20 +372,26 @@ async function buildWorkspaceIndexFromGit(cwd: string): Promise<WorkspaceIndex |
253372
}
254373
}
255374

256-
const directoryEntries: ProjectEntry[] = [...directorySet]
375+
const directoryEntries = [...directorySet]
257376
.toSorted((left, right) => left.localeCompare(right))
258-
.map((directoryPath) => ({
259-
path: directoryPath,
260-
kind: "directory",
261-
parentPath: parentPathOf(directoryPath),
262-
}));
263-
const fileEntries: ProjectEntry[] = [...new Set(filePaths)]
377+
.map(
378+
(directoryPath): ProjectEntry => ({
379+
path: directoryPath,
380+
kind: "directory",
381+
parentPath: parentPathOf(directoryPath),
382+
}),
383+
)
384+
.map(toSearchableWorkspaceEntry);
385+
const fileEntries = [...new Set(filePaths)]
264386
.toSorted((left, right) => left.localeCompare(right))
265-
.map((filePath) => ({
266-
path: filePath,
267-
kind: "file",
268-
parentPath: parentPathOf(filePath),
269-
}));
387+
.map(
388+
(filePath): ProjectEntry => ({
389+
path: filePath,
390+
kind: "file",
391+
parentPath: parentPathOf(filePath),
392+
}),
393+
)
394+
.map(toSearchableWorkspaceEntry);
270395

271396
const entries = [...directoryEntries, ...fileEntries];
272397
return {
@@ -284,7 +409,7 @@ async function buildWorkspaceIndex(cwd: string): Promise<WorkspaceIndex> {
284409
const shouldFilterWithGitIgnore = await isInsideGitWorkTree(cwd);
285410

286411
let pendingDirectories: string[] = [""];
287-
const entries: ProjectEntry[] = [];
412+
const entries: SearchableWorkspaceEntry[] = [];
288413
let truncated = false;
289414

290415
while (pendingDirectories.length > 0 && !truncated) {
@@ -351,11 +476,11 @@ async function buildWorkspaceIndex(cwd: string): Promise<WorkspaceIndex> {
351476
continue;
352477
}
353478

354-
const entry: ProjectEntry = {
479+
const entry = toSearchableWorkspaceEntry({
355480
path: candidate.relativePath,
356481
kind: candidate.dirent.isDirectory() ? "directory" : "file",
357482
parentPath: parentPathOf(candidate.relativePath),
358-
};
483+
});
359484
entries.push(entry);
360485

361486
if (candidate.dirent.isDirectory()) {
@@ -414,18 +539,22 @@ export async function searchWorkspaceEntries(
414539
): Promise<ProjectSearchEntriesResult> {
415540
const index = await getWorkspaceIndex(input.cwd);
416541
const normalizedQuery = normalizeQuery(input.query);
417-
const candidates = normalizedQuery
418-
? index.entries.filter((entry) => entry.path.toLowerCase().includes(normalizedQuery))
419-
: index.entries;
420-
421-
const ranked = candidates.toSorted((left, right) => {
422-
const scoreDelta = scoreEntry(left, normalizedQuery) - scoreEntry(right, normalizedQuery);
423-
if (scoreDelta !== 0) return scoreDelta;
424-
return left.path.localeCompare(right.path);
425-
});
542+
const limit = Math.max(0, Math.floor(input.limit));
543+
const rankedEntries: RankedWorkspaceEntry[] = [];
544+
let matchedEntryCount = 0;
545+
546+
for (const entry of index.entries) {
547+
const score = scoreEntry(entry, normalizedQuery);
548+
if (score === null) {
549+
continue;
550+
}
551+
552+
matchedEntryCount += 1;
553+
insertRankedEntry(rankedEntries, { entry, score }, limit);
554+
}
426555

427556
return {
428-
entries: ranked.slice(0, input.limit),
429-
truncated: index.truncated || ranked.length > input.limit,
557+
entries: rankedEntries.map((candidate) => candidate.entry),
558+
truncated: index.truncated || matchedEntryCount > limit,
430559
};
431560
}

0 commit comments

Comments
 (0)