import { compareAnything } from './comparers' ; import { matchesPrefix , IMatch , matchesCamelCase , isUpper } from './filters' ; import path from './path' ; import { isWindows , isLinux } from './platform' ; import { stripWildcards , equalsIgnoreCase } from './strings' ; import { CharCode } from './charCode' ; export type Score = [ number , number [ ] ] ; export type ScorerCache = { [ key ] : IItemScore ; } ; const sep = path . sep ; const NO_MATCH = 0 ; const NO_SCORE = [ NO_MATCH , [ ] ] ; export function score ( target , query , queryLower , fuzzy ) { if ( ! target || ! query ) { return NO_SCORE ; } const targetLength = target . length ; const queryLength = query . length ; if ( targetLength < queryLength ) { return NO_SCORE ; } const targetLower = target . toLowerCase ( ) ; if ( ! fuzzy ) { const indexOfQueryInTarget = targetLower . indexOf ( queryLower ) ; if ( indexOfQueryInTarget === - 1 ) { return NO_SCORE ; } } const res = doScore ( query , queryLower , queryLength , target , targetLower , targetLength ) ; return res ; } function doScore ( query , queryLower , queryLength , target , targetLower , targetLength ) { const scores = [ ] ; const matches = [ ] ; for ( let queryIndex = 0 ; queryIndex < queryLength ; queryIndex ++ ) { const queryIndexOffset = queryIndex * targetLength ; const queryIndexPreviousOffset = queryIndexOffset - targetLength ; const queryIndexGtNull = queryIndex > 0 ; const queryCharAtIndex = query [ queryIndex ] ; const queryLowerCharAtIndex = queryLower [ queryIndex ] ; for ( let targetIndex = 0 ; targetIndex < targetLength ; targetIndex ++ ) { const targetIndexGtNull = targetIndex > 0 ; const currentIndex = queryIndexOffset + targetIndex ; const leftIndex = currentIndex - 1 ; const diagIndex = queryIndexPreviousOffset + targetIndex - 1 ; const leftScore = targetIndexGtNull ? scores [ leftIndex ] : 0 ; const diagScore = queryIndexGtNull && targetIndexGtNull ? scores [ diagIndex ] : 0 ; const matchesSequenceLength = queryIndexGtNull && targetIndexGtNull ? matches [ diagIndex ] : 0 ; let score ; if ( ! diagScore && queryIndexGtNull ) { score = 0 ; } else { score = computeCharScore ( queryCharAtIndex , queryLowerCharAtIndex , target , targetLower , targetIndex , matchesSequenceLength ) ; } if ( score && diagScore + score >= leftScore ) { matches [ currentIndex ] = matchesSequenceLength + 1 ; scores [ currentIndex ] = diagScore + score ; } else { matches [ currentIndex ] = NO_MATCH ; scores [ currentIndex ] = leftScore ; } } } const positions = [ ] ; let queryIndex = queryLength - 1 ; let targetIndex = targetLength - 1 ; while ( queryIndex >= 0 && targetIndex >= 0 ) { const currentIndex = queryIndex * targetLength + targetIndex ; const match = matches [ currentIndex ] ; if ( match === NO_MATCH ) { targetIndex -- ; } else { positions . push ( targetIndex ) ; queryIndex -- ; targetIndex -- ; } } return [ scores [ queryLength * targetLength - 1 ] , positions . reverse ( ) ] ; } function computeCharScore ( queryCharAtIndex , queryLowerCharAtIndex , target , targetLower , targetIndex , matchesSequenceLength ) { let score = 0 ; if ( queryLowerCharAtIndex !== targetLower [ targetIndex ] ) { return score ; } score += 1 ; if ( matchesSequenceLength > 0 ) { score += matchesSequenceLength * 5 ; } if ( queryCharAtIndex === target [ targetIndex ] ) { score += 1 ; } if ( targetIndex === 0 ) { score += 8 ; } else { const separatorBonus = scoreSeparatorAtPos ( target . charCodeAt ( targetIndex - 1 ) ) ; if ( separatorBonus ) { score += separatorBonus ; } else if ( isUpper ( target . charCodeAt ( targetIndex ) ) ) { score += 1 ; } } return score ; } function scoreSeparatorAtPos ( charCode ) { switch ( charCode ) { case CharCode . Slash : case CharCode . Backslash : return 5 ; case CharCode . Underline : case CharCode . Dash : case CharCode . Period : case CharCode . Space : case CharCode . SingleQuote : case CharCode . DoubleQuote : case CharCode . Colon : return 4 ; default : return 0 ; } } /**
 * Scoring on structural items that have a label and optional description.
 */ export interface IItemScore { /**
     * Overall score.
     */ score : number ; /**
     * Matches within the label.
     */ labelMatch ? : IMatch [ ] ; /**
     * Matches within the description.
     */ descriptionMatch ? : IMatch [ ] ; } const NO_ITEM_SCORE = Object . freeze ( { score : 0 } ) ; export interface IItemAccessor < T > { /**
     * Just the label of the item to score on.
     */ getItemLabel ( item ) : string | null ; /**
     * The optional description of the item to score on. Can be null.
     */ getItemDescription ( item ) : string | null ; /**
     * If the item is a file, the path of the file to score on. Can be null.
     */ getItemPath ( file ) : string | undefined ; } const PATH_IDENTITY_SCORE = 1 << 18 ; const LABEL_PREFIX_SCORE = 1 << 17 ; const LABEL_CAMELCASE_SCORE = 1 << 16 ; const LABEL_SCORE_THRESHOLD = 1 << 15 ; export interface IPreparedQuery { original : string ; value : string ; lowercase : string ; containsPathSeparator : boolean ; } /**
 * Helper function to prepare a search value for scoring in quick open by removing unwanted characters.
 */ export function prepareQuery ( original ) { if ( ! original ) { original = '' ; } let value = stripWildcards ( original ) . replace ( /\s/g , '' ) ; if ( isWindows ) { value = value . replace ( /\//g , sep ) ; } const lowercase = value . toLowerCase ( ) ; const containsPathSeparator = value . indexOf ( sep ) >= 0 ; return { original , value , lowercase , containsPathSeparator } ; } export function scoreItem < T > ( item , query , fuzzy , accessor , cache ) { if ( ! item || ! query . value ) { return NO_ITEM_SCORE ; } const label = accessor . getItemLabel ( item ) ; if ( ! label ) { return NO_ITEM_SCORE ; } const description = accessor . getItemDescription ( item ) ; let cacheHash ; if ( description ) { cacheHash = `${ label }${ description }${ query . value }${ fuzzy }` ; } else { cacheHash = `${ label }${ query . value }${ fuzzy }` ; } const cached = cache [ cacheHash ] ; if ( cached ) { return cached ; } const itemScore = doScoreItem ( label , description , accessor . getItemPath ( item ) , query , fuzzy ) ; cache [ cacheHash ] = itemScore ; return itemScore ; } function createMatches ( offsets ) { let ret = [ ] ; if ( ! offsets ) { return ret ; } let last ; for ( const pos of offsets ) { if ( last && last . end === pos ) { last . end += 1 ; } else { last = { start : pos , end : pos + 1 } ; ret . push ( last ) ; } } return ret ; } function doScoreItem ( label , description , path , query , fuzzy ) { if ( path && ( isLinux ? query . original === path : equalsIgnoreCase ( query . original , path ) ) ) { return { score : PATH_IDENTITY_SCORE , labelMatch : [ { start : 0 , end : label . length } ] , descriptionMatch : description ? [ { start : 0 , end : description . length } ] : undefined , } ; } const preferLabelMatches = ! path || ! query . containsPathSeparator ; if ( preferLabelMatches ) { const prefixLabelMatch = matchesPrefix ( query . value , label ) ; if ( prefixLabelMatch ) { return { score : LABEL_PREFIX_SCORE , labelMatch : prefixLabelMatch } ; } const camelcaseLabelMatch = matchesCamelCase ( query . value , label ) ; if ( camelcaseLabelMatch ) { return { score : LABEL_CAMELCASE_SCORE , labelMatch : camelcaseLabelMatch } ; } const [ labelScore , labelPositions ] = score ( label , query . value , query . lowercase , fuzzy ) ; if ( labelScore ) { return { score : labelScore + LABEL_SCORE_THRESHOLD , labelMatch : createMatches ( labelPositions ) , } ; } } if ( description ) { let descriptionPrefix = description ; if ( ! ! path ) { descriptionPrefix = `${ description }${ sep }` ; } const descriptionPrefixLength = descriptionPrefix . length ; const descriptionAndLabel = `${ descriptionPrefix }${ label }` ; const [ labelDescriptionScore , labelDescriptionPositions ] = score ( descriptionAndLabel , query . value , query . lowercase , fuzzy ) ; if ( labelDescriptionScore ) { const labelDescriptionMatches = createMatches ( labelDescriptionPositions ) ; const labelMatch = [ ] ; const descriptionMatch = [ ] ; labelDescriptionMatches . forEach ( ( h ) => { if ( h . start < descriptionPrefixLength && h . end > descriptionPrefixLength ) { labelMatch . push ( { start : 0 , end : h . end - descriptionPrefixLength } ) ; descriptionMatch . push ( { start : h . start , end : descriptionPrefixLength } ) ; } else if ( h . start >= descriptionPrefixLength ) { labelMatch . push ( { start : h . start - descriptionPrefixLength , end : h . end - descriptionPrefixLength , } ) ; } else { descriptionMatch . push ( h ) ; } } ) ; return { score : labelDescriptionScore , labelMatch , descriptionMatch } ; } } return NO_ITEM_SCORE ; } export function compareItemsByScore < T > ( itemA , itemB , query , fuzzy , accessor , cache , fallbackComparer = fallbackCompare ) { const itemScoreA = scoreItem ( itemA , query , fuzzy , accessor , cache ) ; const itemScoreB = scoreItem ( itemB , query , fuzzy , accessor , cache ) ; const scoreA = itemScoreA . score ; const scoreB = itemScoreB . score ; if ( scoreA === PATH_IDENTITY_SCORE || scoreB === PATH_IDENTITY_SCORE ) { if ( scoreA !== scoreB ) { return scoreA === PATH_IDENTITY_SCORE ? - 1 : 1 ; } } if ( scoreA === LABEL_PREFIX_SCORE || scoreB === LABEL_PREFIX_SCORE ) { if ( scoreA !== scoreB ) { return scoreA === LABEL_PREFIX_SCORE ? - 1 : 1 ; } const labelA = accessor . getItemLabel ( itemA ) || '' ; const labelB = accessor . getItemLabel ( itemB ) || '' ; if ( labelA . length !== labelB . length ) { return labelA . length - labelB . length ; } } if ( scoreA === LABEL_CAMELCASE_SCORE || scoreB === LABEL_CAMELCASE_SCORE ) { if ( scoreA !== scoreB ) { return scoreA === LABEL_CAMELCASE_SCORE ? - 1 : 1 ; } const labelA = accessor . getItemLabel ( itemA ) || '' ; const labelB = accessor . getItemLabel ( itemB ) || '' ; const comparedByMatchLength = compareByMatchLength ( itemScoreA . labelMatch , itemScoreB . labelMatch ) ; if ( comparedByMatchLength !== 0 ) { return comparedByMatchLength ; } if ( labelA . length !== labelB . length ) { return labelA . length - labelB . length ; } } if ( scoreA > LABEL_SCORE_THRESHOLD || scoreB > LABEL_SCORE_THRESHOLD ) { if ( scoreB < LABEL_SCORE_THRESHOLD ) { return - 1 ; } if ( scoreA < LABEL_SCORE_THRESHOLD ) { return 1 ; } } if ( scoreA !== scoreB ) { return scoreA > scoreB ? - 1 : 1 ; } const itemAMatchDistance = computeLabelAndDescriptionMatchDistance ( itemA , itemScoreA , accessor ) ; const itemBMatchDistance = computeLabelAndDescriptionMatchDistance ( itemB , itemScoreB , accessor ) ; if ( itemAMatchDistance && itemBMatchDistance && itemAMatchDistance !== itemBMatchDistance ) { return itemBMatchDistance > itemAMatchDistance ? - 1 : 1 ; } return fallbackComparer ( itemA , itemB , query , accessor ) ; } function computeLabelAndDescriptionMatchDistance < T > ( item , score , accessor ) { let matchStart = - 1 ; let matchEnd = - 1 ; if ( score . descriptionMatch && score . descriptionMatch . length ) { matchStart = score . descriptionMatch [ 0 ] . start ; } else if ( score . labelMatch && score . labelMatch . length ) { matchStart = score . labelMatch [ 0 ] . start ; } if ( score . labelMatch && score . labelMatch . length ) { matchEnd = score . labelMatch [ score . labelMatch . length - 1 ] . end ; if ( score . descriptionMatch && score . descriptionMatch . length ) { const itemDescription = accessor . getItemDescription ( item ) ; if ( itemDescription ) { matchEnd += itemDescription . length ; } } } else if ( score . descriptionMatch && score . descriptionMatch . length ) { matchEnd = score . descriptionMatch [ score . descriptionMatch . length - 1 ] . end ; } return matchEnd - matchStart ; } function compareByMatchLength ( matchesA ? , matchesB ? ) { if ( ( ! matchesA && ! matchesB ) || ( ( ! matchesA || ! matchesA . length ) && ( ! matchesB || ! matchesB . length ) ) ) { return 0 ; } if ( ! matchesB || ! matchesB . length ) { return - 1 ; } if ( ! matchesA || ! matchesA . length ) { return 1 ; } const matchStartA = matchesA [ 0 ] . start ; const matchEndA = matchesA [ matchesA . length - 1 ] . end ; const matchLengthA = matchEndA - matchStartA ; const matchStartB = matchesB [ 0 ] . start ; const matchEndB = matchesB [ matchesB . length - 1 ] . end ; const matchLengthB = matchEndB - matchStartB ; return matchLengthA === matchLengthB ? 0 : matchLengthB < matchLengthA ? 1 : - 1 ; } export function fallbackCompare < T > ( itemA , itemB , query , accessor ) { const labelA = accessor . getItemLabel ( itemA ) || '' ; const labelB = accessor . getItemLabel ( itemB ) || '' ; const descriptionA = accessor . getItemDescription ( itemA ) ; const descriptionB = accessor . getItemDescription ( itemB ) ; const labelDescriptionALength = labelA . length + ( descriptionA ? descriptionA . length : 0 ) ; const labelDescriptionBLength = labelB . length + ( descriptionB ? descriptionB . length : 0 ) ; if ( labelDescriptionALength !== labelDescriptionBLength ) { return labelDescriptionALength - labelDescriptionBLength ; } const pathA = accessor . getItemPath ( itemA ) ; const pathB = accessor . getItemPath ( itemB ) ; if ( pathA && pathB && pathA . length !== pathB . length ) { return pathA . length - pathB . length ; } if ( labelA !== labelB ) { return compareAnything ( labelA , labelB , query . value ) ; } if ( descriptionA && descriptionB && descriptionA !== descriptionB ) { return compareAnything ( descriptionA , descriptionB , query . value ) ; } if ( pathA && pathB && pathA !== pathB ) { return compareAnything ( pathA , pathB , query . value ) ; } return 0 ; }