packageDocumentation module import { CharCode } from "./charCode" ; import { LRUCache } from "./map" ; import * as strings from "./strings" ; public export interface IMatch { start : number ; end : number ; } param word param wordToMatchAgainst internal export type IFilter = ( word : string , wordToMatchAgainst : string ) => IMatch [ ] | null ; returns internal export function or ( ... filter ) { return function ( word , wordToMatchAgainst ) : IMatch [ ] | null { for ( let i = 0 , len = filter . length ; i < len ; i ++ ) { const match = filter [ i ] ( word , wordToMatchAgainst ) ; if ( match ) { return match ; } } return null ; } ; } internal export const matchesStrictPrefix = _matchesPrefix . bind ( undefined , false ) ; internal export const matchesPrefix = _matchesPrefix . bind ( undefined , true ) ; function _matchesPrefix ( ignoreCase , word , wordToMatchAgainst ) { if ( ! wordToMatchAgainst || wordToMatchAgainst . length < word . length ) { return null ; } let matches ; if ( ignoreCase ) { matches = strings . startsWithIgnoreCase ( wordToMatchAgainst , word ) ; } else { matches = wordToMatchAgainst . indexOf ( word ) === 0 ; } if ( ! matches ) { return null ; } return word . length > 0 ? [ { start : 0 , end : word . length } ] : [ ] ; } internal export function matchesContiguousSubString ( word , wordToMatchAgainst ) { const index = wordToMatchAgainst . toLowerCase ( ) . indexOf ( word . toLowerCase ( ) ) ; if ( index === - 1 ) { return null ; } return [ { start : index , end : index + word . length } ] ; } param word param wordToMatchAgainst internal export function matchesSubString ( word , wordToMatchAgainst ) { return _matchesSubString ( word . toLowerCase ( ) , wordToMatchAgainst . toLowerCase ( ) , 0 , 0 ) ; } function _matchesSubString ( word , wordToMatchAgainst , i , j ) { if ( i === word . length ) { return [ ] ; } else if ( j === wordToMatchAgainst . length ) { return null ; } else { if ( word [ i ] === wordToMatchAgainst [ j ] ) { let result = null ; if ( result = _matchesSubString ( word , wordToMatchAgainst , i + 1 , j + 1 ) ) { return join ( { start : j , end : j + 1 } , result ) ; } return null ; } return _matchesSubString ( word , wordToMatchAgainst , i , j + 1 ) ; } } function isLower ( code ) { return CharCode . a <= code && code <= CharCode . z ; } function isUpper ( code ) { return CharCode . A <= code && code <= CharCode . Z ; } function isNumber ( code ) { return CharCode . Digit0 <= code && code <= CharCode . Digit9 ; } function isWhitespace ( code ) { return ( code === CharCode . Space || code === CharCode . Tab || code === CharCode . LineFeed || code === CharCode . CarriageReturn ) ; } const wordSeparators = new Set < number > ( ) ; '`~!@#$%^&*()-=+[{]}\\|;:\'",.<>/?' . split ( "" ) . forEach ( ( s ) => wordSeparators . add ( s . charCodeAt ( 0 ) ) ) ; function isWordSeparator ( code ) { return isWhitespace ( code ) || wordSeparators . has ( code ) ; } function charactersMatch ( codeA , codeB ) { return ( codeA === codeB ) || ( isWordSeparator ( codeA ) && isWordSeparator ( codeB ) ) ; } function isAlphanumeric ( code ) { return isLower ( code ) || isUpper ( code ) || isNumber ( code ) ; } function join ( head , tail ) { if ( tail . length === 0 ) { tail = [ head ] ; } else if ( head . end === tail [ 0 ] . start ) { tail [ 0 ] . start = head . start ; } else { tail . unshift ( head ) ; } return tail ; } function nextAnchor ( camelCaseWord , start ) { for ( let i = start ; i < camelCaseWord . length ; i ++ ) { const c = camelCaseWord . charCodeAt ( i ) ; if ( isUpper ( c ) || isNumber ( c ) || ( i > 0 && ! isAlphanumeric ( camelCaseWord . charCodeAt ( i - 1 ) ) ) ) { return i ; } } return camelCaseWord . length ; } function _matchesCamelCase ( word , camelCaseWord , i , j ) { if ( i === word . length ) { return [ ] ; } else if ( j === camelCaseWord . length ) { return null ; } else if ( word [ i ] !== camelCaseWord [ j ] . toLowerCase ( ) ) { return null ; } else { let result = null ; let nextUpperIndex = j + 1 ; result = _matchesCamelCase ( word , camelCaseWord , i + 1 , j + 1 ) ; while ( ! result && ( nextUpperIndex = nextAnchor ( camelCaseWord , nextUpperIndex ) ) < camelCaseWord . length ) { result = _matchesCamelCase ( word , camelCaseWord , i + 1 , nextUpperIndex ) ; nextUpperIndex ++ ; } return result === null ? null : join ( { start : j , end : j + 1 } , result ) ; } } interface ICamelCaseAnalysis { upperPercent : number ; lowerPercent : number ; alphaPercent : number ; numericPercent : number ; } function analyzeCamelCaseWord ( word ) { let upper = 0 , lower = 0 , alpha = 0 , numeric = 0 , code = 0 ; for ( let i = 0 ; i < word . length ; i ++ ) { code = word . charCodeAt ( i ) ; if ( isUpper ( code ) ) { upper ++ ; } if ( isLower ( code ) ) { lower ++ ; } if ( isAlphanumeric ( code ) ) { alpha ++ ; } if ( isNumber ( code ) ) { numeric ++ ; } } const upperPercent = upper / word . length ; const lowerPercent = lower / word . length ; const alphaPercent = alpha / word . length ; const numericPercent = numeric / word . length ; return { upperPercent , lowerPercent , alphaPercent , numericPercent } ; } function isUpperCaseWord ( analysis ) { const { upperPercent , lowerPercent } = analysis ; return lowerPercent === 0 && upperPercent > 0.6 ; } function isCamelCaseWord ( analysis ) { const { upperPercent , lowerPercent , alphaPercent , numericPercent } = analysis ; return lowerPercent > 0.2 && upperPercent < 0.8 && alphaPercent > 0.6 && numericPercent < 0.2 ; } function isCamelCasePattern ( word ) { let upper = 0 , lower = 0 , code = 0 , whitespace = 0 ; for ( let i = 0 ; i < word . length ; i ++ ) { code = word . charCodeAt ( i ) ; if ( isUpper ( code ) ) { upper ++ ; } if ( isLower ( code ) ) { lower ++ ; } if ( isWhitespace ( code ) ) { whitespace ++ ; } } if ( ( upper === 0 || lower === 0 ) && whitespace === 0 ) { return word . length <= 30 ; } else { return upper <= 5 ; } } param word param wordToMatchAgainst internal export function matchesCamelCase ( word , camelCaseWord ) { if ( ! camelCaseWord ) { return null ; } camelCaseWord = camelCaseWord . trim ( ) ; if ( camelCaseWord . length === 0 ) { return null ; } if ( ! isCamelCasePattern ( camelCaseWord ) ) { return null ; } if ( camelCaseWord . length > 60 ) { return null ; } const analysis = analyzeCamelCaseWord ( camelCaseWord ) ; if ( ! isCamelCaseWord ( analysis ) ) { if ( ! isUpperCaseWord ( analysis ) ) { return null ; } camelCaseWord = camelCaseWord . toLowerCase ( ) ; } let result = null ; let i = 0 ; word = word . toLowerCase ( ) ; while ( i < camelCaseWord . length && ( result = _matchesCamelCase ( word , camelCaseWord , 0 , i ) ) === null ) { i = nextAnchor ( camelCaseWord , i + 1 ) ; } return result ; } param word param target param contiguous internal export function matchesWords ( word , target , contiguous = false ) { if ( ! target || target . length === 0 ) { return null ; } let result = null ; let i = 0 ; word = word . toLowerCase ( ) ; target = target . toLowerCase ( ) ; while ( i < target . length && ( result = _matchesWords ( word , target , 0 , i , contiguous ) ) === null ) { i = nextWord ( target , i + 1 ) ; } return result ; } function _matchesWords ( word , target , i , j , contiguous ) { if ( i === word . length ) { return [ ] ; } else if ( j === target . length ) { return null ; } else if ( ! charactersMatch ( word . charCodeAt ( i ) , target . charCodeAt ( j ) ) ) { return null ; } else { let result = null ; let nextWordIndex = j + 1 ; result = _matchesWords ( word , target , i + 1 , j + 1 , contiguous ) ; if ( ! contiguous ) { while ( ! result && ( nextWordIndex = nextWord ( target , nextWordIndex ) ) < target . length ) { result = _matchesWords ( word , target , i + 1 , nextWordIndex , contiguous ) ; nextWordIndex ++ ; } } return result === null ? null : join ( { start : j , end : j + 1 } , result ) ; } } function nextWord ( word , start ) { for ( let i = start ; i < word . length ; i ++ ) { if ( isWordSeparator ( word . charCodeAt ( i ) ) || ( i > 0 && isWordSeparator ( word . charCodeAt ( i - 1 ) ) ) ) { return i ; } } return word . length ; } const fuzzyContiguousFilter = or ( matchesPrefix , matchesCamelCase , matchesContiguousSubString ) ; const fuzzySeparateFilter = or ( matchesPrefix , matchesCamelCase , matchesSubString ) ; const fuzzyRegExpCache = new LRUCache < string , RegExp > ( 10000 ) ; internal export function matchesFuzzy ( word , wordToMatchAgainst , enableSeparateSubstringMatching = false ) { if ( typeof word !== "string" || typeof wordToMatchAgainst !== "string" ) { return null ; } let regexp = fuzzyRegExpCache . get ( word ) ; if ( ! regexp ) { regexp = new RegExp ( strings . convertSimple2RegExpPattern ( word ) , "i" ) ; fuzzyRegExpCache . set ( word , regexp ) ; } const match = regexp . exec ( wordToMatchAgainst ) ; if ( match ) { return [ { start : match . index , end : match . index + match [ 0 ] . length } ] ; } return enableSeparateSubstringMatching ? fuzzySeparateFilter ( word , wordToMatchAgainst ) : fuzzyContiguousFilter ( word , wordToMatchAgainst ) ; } internal export function matchesFuzzy2 ( pattern , word ) { const score = fuzzyScore ( pattern , pattern . toLowerCase ( ) , 0 , word , word . toLowerCase ( ) , 0 , true ) ; return score ? createMatches ( score ) : null ; } internal export function createMatches ( score ) { if ( typeof score === "undefined" ) { return [ ] ; } const matches = score [ 1 ] . toString ( 2 ) ; const wordStart = score [ 2 ] ; const res = [ ] ; for ( let pos = wordStart ; pos < _maxLen ; pos ++ ) { if ( matches [ matches . length - ( pos + 1 ) ] === "1" ) { const last = res [ res . length - 1 ] ; if ( last && last . end === pos ) { last . end = pos + 1 ; } else { res . push ( { start : pos , end : pos + 1 } ) ; } } } return res ; } const _maxLen = 128 ; function initTable ( ) { const table = [ ] ; const row = [ 0 ] ; for ( let i = 1 ; i <= _maxLen ; i ++ ) { row . push ( - i ) ; } for ( let i = 0 ; i <= _maxLen ; i ++ ) { const thisRow = row . slice ( 0 ) ; thisRow [ 0 ] = - i ; table . push ( thisRow ) ; } return table ; } const _table = initTable ( ) ; const _scores = initTable ( ) ; const _arrows = < Arrow [ ] [ ] > initTable ( ) ; const _debug = false ; function isSeparatorAtPos ( value , index ) { if ( index < 0 || index >= value . length ) { return false ; } const code = value . charCodeAt ( index ) ; switch ( code ) { case CharCode . Underline : case CharCode . Dash : case CharCode . Period : case CharCode . Space : case CharCode . Slash : case CharCode . Backslash : case CharCode . SingleQuote : case CharCode . DoubleQuote : case CharCode . Colon : case CharCode . DollarSign : return true ; default : return false ; } } function isWhitespaceAtPos ( value , index ) { if ( index < 0 || index >= value . length ) { return false ; } const code = value . charCodeAt ( index ) ; switch ( code ) { case CharCode . Space : case CharCode . Tab : return true ; default : return false ; } } function isUpperCaseAtPos ( pos , word , wordLow ) { return word [ pos ] !== wordLow [ pos ] ; } internal export function isPatternInWord ( patternLow , patternPos , patternLen , wordLow , wordPos , wordLen ) { while ( patternPos < patternLen && wordPos < wordLen ) { if ( patternLow [ patternPos ] === wordLow [ wordPos ] ) { patternPos += 1 ; } wordPos += 1 ; } return patternPos === patternLen ; } const enum Arrow { Top = 0b1 , Diag = 0b10 , Left = 0b100 } internal export type FuzzyScore = [ number , number , number ] ; internal export namespace FuzzyScore { internal export const Default = < [ - 100 , 0 , 0 ] > Object . freeze ( [ - 100 , 0 , 0 ] ) ; internal export function isDefault ( score ? ) { return ! score || ( score [ 0 ] === - 100 && score [ 1 ] === 0 && score [ 2 ] === 0 ) ; } } internal export type FuzzyScorer = ( pattern : string , lowPattern : string , patternPos : number , word : string , lowWord : string , wordPos : number , firstMatchCanBeWeak : boolean ) => FuzzyScore | undefined ; internal export function fuzzyScore ( pattern , patternLow , patternStart , word , wordLow , wordStart , firstMatchCanBeWeak ) { const patternLen = pattern . length > _maxLen ? _maxLen : pattern . length ; const wordLen = word . length > _maxLen ? _maxLen : word . length ; if ( patternStart >= patternLen || wordStart >= wordLen || ( patternLen - patternStart ) > ( wordLen - wordStart ) ) { return undefined ; } if ( ! isPatternInWord ( patternLow , patternStart , patternLen , wordLow , wordStart , wordLen ) ) { return undefined ; } let row = 1 ; let column = 1 ; let patternPos = patternStart ; let wordPos = wordStart ; let hasStrongFirstMatch = false ; for ( row = 1 , patternPos = patternStart ; patternPos < patternLen ; row ++ , patternPos ++ ) { for ( column = 1 , wordPos = wordStart ; wordPos < wordLen ; column ++ , wordPos ++ ) { const score = _doScore ( pattern , patternLow , patternPos , patternStart , word , wordLow , wordPos ) ; if ( patternPos === patternStart && score > 1 ) { hasStrongFirstMatch = true ; } _scores [ row ] [ column ] = score ; const diag = _table [ row - 1 ] [ column - 1 ] + ( score > 1 ? 1 : score ) ; const top = _table [ row - 1 ] [ column ] + - 1 ; const left = _table [ row ] [ column - 1 ] + - 1 ; if ( left >= top ) { if ( left > diag ) { _table [ row ] [ column ] = left ; _arrows [ row ] [ column ] = Arrow . Left ; } else if ( left === diag ) { _table [ row ] [ column ] = left ; _arrows [ row ] [ column ] = Arrow . Left | Arrow . Diag ; } else { _table [ row ] [ column ] = diag ; _arrows [ row ] [ column ] = Arrow . Diag ; } } else { if ( top > diag ) { _table [ row ] [ column ] = top ; _arrows [ row ] [ column ] = Arrow . Top ; } else if ( top === diag ) { _table [ row ] [ column ] = top ; _arrows [ row ] [ column ] = Arrow . Top | Arrow . Diag ; } else { _table [ row ] [ column ] = diag ; _arrows [ row ] [ column ] = Arrow . Diag ; } } } } if ( ! hasStrongFirstMatch && ! firstMatchCanBeWeak ) { return undefined ; } _matchesCount = 0 ; _topScore = - 100 ; _wordStart = wordStart ; _firstMatchCanBeWeak = firstMatchCanBeWeak ; _findAllMatches2 ( row - 1 , column - 1 , patternLen === wordLen ? 1 : 0 , 0 , false ) ; if ( _matchesCount === 0 ) { return undefined ; } return [ _topScore , _topMatch2 , wordStart ] ; } function _doScore ( pattern , patternLow , patternPos , patternStart , word , wordLow , wordPos ) { if ( patternLow [ patternPos ] !== wordLow [ wordPos ] ) { return - 1 ; } if ( wordPos === ( patternPos - patternStart ) ) { if ( pattern [ patternPos ] === word [ wordPos ] ) { return 7 ; } else { return 5 ; } } else if ( isUpperCaseAtPos ( wordPos , word , wordLow ) && ( wordPos === 0 || ! isUpperCaseAtPos ( wordPos - 1 , word , wordLow ) ) ) { if ( pattern [ patternPos ] === word [ wordPos ] ) { return 7 ; } else { return 5 ; } } else if ( isSeparatorAtPos ( wordLow , wordPos ) && ( wordPos === 0 || ! isSeparatorAtPos ( wordLow , wordPos - 1 ) ) ) { return 5 ; } else if ( isSeparatorAtPos ( wordLow , wordPos - 1 ) || isWhitespaceAtPos ( wordLow , wordPos - 1 ) ) { return 5 ; } else { return 1 ; } } let _matchesCount = 0 ; let _topMatch2 = 0 ; let _topScore = 0 ; let _wordStart = 0 ; let _firstMatchCanBeWeak = false ; function _findAllMatches2 ( row , column , total , matches , lastMatched ) { if ( _matchesCount >= 10 || total < - 25 ) { return ; } let simpleMatchCount = 0 ; while ( row > 0 && column > 0 ) { const score = _scores [ row ] [ column ] ; const arrow = _arrows [ row ] [ column ] ; if ( arrow === Arrow . Left ) { column -= 1 ; if ( lastMatched ) { total -= 5 ; } else if ( matches !== 0 ) { total -= 1 ; } lastMatched = false ; simpleMatchCount = 0 ; } else { if ( arrow & Arrow . Diag ) { if ( arrow & Arrow . Left ) { _findAllMatches2 ( row , column - 1 , matches !== 0 ? total - 1 : total , matches , lastMatched ) ; } total += score ; row -= 1 ; column -= 1 ; lastMatched = true ; matches += 2 ** ( column + _wordStart ) ; if ( score === 1 ) { simpleMatchCount += 1 ; if ( row === 0 && ! _firstMatchCanBeWeak ) { return undefined ; } } else { total += 1 + ( simpleMatchCount * ( score - 1 ) ) ; simpleMatchCount = 0 ; } } else { return undefined ; } } } total -= column >= 3 ? 9 : column * 3 ; _matchesCount += 1 ; if ( total > _topScore ) { _topScore = total ; _topMatch2 = matches ; } } internal export function fuzzyScoreGracefulAggressive ( pattern , lowPattern , patternPos , word , lowWord , wordPos , firstMatchCanBeWeak ) { return fuzzyScoreWithPermutations ( pattern , lowPattern , patternPos , word , lowWord , wordPos , true , firstMatchCanBeWeak ) ; } internal export function fuzzyScoreGraceful ( pattern , lowPattern , patternPos , word , lowWord , wordPos , firstMatchCanBeWeak ) { return fuzzyScoreWithPermutations ( pattern , lowPattern , patternPos , word , lowWord , wordPos , false , firstMatchCanBeWeak ) ; } function fuzzyScoreWithPermutations ( pattern , lowPattern , patternPos , word , lowWord , wordPos , aggressive , firstMatchCanBeWeak ) { let top = fuzzyScore ( pattern , lowPattern , patternPos , word , lowWord , wordPos , firstMatchCanBeWeak ) ; if ( top && ! aggressive ) { return top ; } if ( pattern . length >= 3 ) { const tries = Math . min ( 7 , pattern . length - 1 ) ; for ( let movingPatternPos = patternPos + 1 ; movingPatternPos < tries ; movingPatternPos ++ ) { const newPattern = nextTypoPermutation ( pattern , movingPatternPos ) ; if ( newPattern ) { const candidate = fuzzyScore ( newPattern , newPattern . toLowerCase ( ) , patternPos , word , lowWord , wordPos , firstMatchCanBeWeak ) ; if ( candidate ) { candidate [ 0 ] -= 3 ; if ( ! top || candidate [ 0 ] > top [ 0 ] ) { top = candidate ; } } } } } return top ; } function nextTypoPermutation ( pattern , patternPos ) { if ( patternPos + 1 >= pattern . length ) { return undefined ; } const swap1 = pattern [ patternPos ] ; const swap2 = pattern [ patternPos + 1 ] ; if ( swap1 === swap2 ) { return undefined ; } return pattern . slice ( 0 , patternPos ) + swap2 + swap1 + pattern . slice ( patternPos + 2 ) ; }