@@ -28,10 +28,20 @@ const IGNORED_DIRECTORY_NAMES = new Set([
2828
2929interface 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+
3545const workspaceIndexCache = new Map < string , WorkspaceIndex > ( ) ;
3646const 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+
5877function 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
81200function 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