filters.ts ×47

Frontier kind: Code frontier

unlabeled · c_b85edd31e302

2064 tests · 5580 LOC · 29 files · introduces 0 tests · 212 LOC · 1 file

Introduces — evidence that enters the hierarchy at this concept

Code
47 ranges212 lines · 1 files
Tests
0 tests

Contains — complete concept membership

All code (extent)
786 ranges5580 lines · 29 files · Browse complete extent
All tests (intent)
2064 testsBrowse complete intent

Neighbourhood graph

The orange circle is the focus. Violet and green circles are every ancestor and descendant, broader and narrower, at any distance; blue squares and pink diamonds are the introduced files and exact introduced tests of every visible concept, not only the focus's. Arrows point from broader to narrower concepts and bridge only concepts omitted from this view. Undirected links show source or test introduction. Concept and file size follows LOC; exact test nodes use test-count units.

Introduced files, introduced tests, and structurally relevant concept specialization

In the embedded map, ordinary wheel input scrolls the page; use the visible controls to zoom and drag to pan. Open the full-screen map for canvas navigation: wheel pans, Ctrl/Command plus wheel zooms, and arrow keys pan when this region is focused. On touch screens, open the full-screen map to pan or pinch. If JavaScript or WebGL is unavailable, use the native relationship evidence on this page.

Graph controls are ready.

Interactive rendering requires JavaScript and WebGL. Use the native relationship evidence on this page while the interactive map is unavailable.

Native relationship evidence

Every exact file and test below is linked only from the concept that introduces it.

Introduced tests

Every collected test enters the hierarchy at exactly one concept.

No tests are introduced at this concept. Its intent tests are introduced by other concepts.

Introduced code

Every collected source range enters the hierarchy at exactly one concept.

1 file ranked by introduced lines: 212 introduced LOC across 47 ranges. Expand a file to inspect source; the > gutter marks introduced lines.

src/vs/base/common/filters.ts 212 introduced LOC · 47 ranges

Open complete file

1 > /*--------------------------------------------------------------------------------------------- filters.ts
2 > * Copyright (c) Microsoft Corporation. All rights reserved.
3 > * Licensed under the MIT License. See License.txt in the project root for license information.
4 > *--------------------------------------------------------------------------------------------*/
5 >
6 > import { CharCode } from './charCode.js';
7 > import { LRUCache } from './map.js';
8 > import { getKoreanAltChars } from './naturalLanguage/korean.js';
9 > import { tryNormalizeToBase } from './normalization.js';
10 > import * as strings from './strings.js';
11 >
12 > export interface IFilter {
13 > // Returns null if word doesn't match.
14 > (word: string, wordToMatchAgainst: string): IMatch[] | null;
15 > }
16 >
17 > export interface IMatch {
18 > start: number;
19 > end: number;
20 > }
21 >
22 > // Combined filters
23 >
24 > /**
25 > * @returns A filter which combines the provided set
26 > * of filters with an or. The *first* filters that
27 > * matches defined the return value of the returned
28 > * filter.
29 > */
30 > export function or(...filter: IFilter[]): IFilter {
31 > return function (word: string, wordToMatchAgainst: string): IMatch[] | null {
32 for (let i = 0, len = filter.length; i < len; i++) {
33 const match = filter[i](word, wordToMatchAgainst);
38 return null;
39 };
40 > } filters.ts
41 >
42 > // Prefix
43 >
44 > export const matchesStrictPrefix: IFilter = _matchesPrefix.bind(undefined, false);
45 > export const matchesPrefix: IFilter = _matchesPrefix.bind(undefined, true);
46 >
47 function _matchesPrefix(ignoreCase: boolean, word: string, wordToMatchAgainst: string): IMatch[] | null {
48 if (!wordToMatchAgainst || wordToMatchAgainst.length < word.length) {
63 return word.length > 0 ? [{ start: 0, end: word.length }] : [];
64 }
65 > filters.ts
66 > // Contiguous Substring
67 >
68 > export function matchesContiguousSubString(word: string, wordToMatchAgainst: string): IMatch[] | null {
69 if (word.length > wordToMatchAgainst.length) {
70 return null;
78 return [{ start: index, end: index + word.length }];
79 }
80 > filters.ts
81 > export function matchesBaseContiguousSubString(word: string, wordToMatchAgainst: string): IMatch[] | null {
82 if (word.length > wordToMatchAgainst.length) {
83 return null;
93 return [{ start: index, end: index + word.length }];
94 }
95 > filters.ts
96 > // Substring
97 >
98 > export function matchesSubString(word: string, wordToMatchAgainst: string): IMatch[] | null {
99 if (word.length > wordToMatchAgainst.length) {
100 return null;
103 return _matchesSubString(word.toLowerCase(), wordToMatchAgainst.toLowerCase(), 0, 0);
104 }
105 > filters.ts
106 function _matchesSubString(word: string, wordToMatchAgainst: string, i: number, j: number): IMatch[] | null {
107 if (i === word.length) {
121 }
122 }
123 > filters.ts
124 > // CamelCase
125 >
126 function isLower(code: number): boolean {
127 return CharCode.a <= code && code <= CharCode.z;
128 }
129 > filters.ts
130 > export function isUpper(code: number): boolean {
131 return CharCode.A <= code && code <= CharCode.Z;
132 }
133 > filters.ts
134 function isNumber(code: number): boolean {
135 return CharCode.Digit0 <= code && code <= CharCode.Digit9;
136 }
137 > filters.ts
138 function isWhitespace(code: number): boolean {
139 return (
144 );
145 }
146 > filters.ts
147 > const wordSeparators = new Set<number>();
148 > // These are chosen as natural word separators based on written text.
149 > // It is a subset of the word separators used by the monaco editor.
150 > '()[]{}<>`\'"-/;:,.?!'
151 > .split('')
152 > .forEach(s => wordSeparators.add(s.charCodeAt(0)));
153 >
154 function isWordSeparator(code: number): boolean {
155 return isWhitespace(code) || wordSeparators.has(code);
156 }
157 > filters.ts
158 function charactersMatch(codeA: number, codeB: number): boolean {
159 return (codeA === codeB) || (isWordSeparator(codeA) && isWordSeparator(codeB));
160 }
161 > filters.ts
162 > const alternateCharsCache: Map<number, ArrayLike<number> | undefined> = new Map();
163 > /**
164 > * Gets alternative codes to the character code passed in. This comes in the
165 > * form of an array of character codes, all of which must match _in order_ to
166 > * successfully match.
167 > *
168 > * @param code The character code to check.
169 > */
170 function getAlternateCodes(code: number): ArrayLike<number> | undefined {
171 if (alternateCharsCache.has(code)) {
186 return result;
187 }
188 > filters.ts
189 function isAlphanumeric(code: number): boolean {
190 return isLower(code) || isUpper(code) || isNumber(code);
191 }
192 > filters.ts
193 function join(head: IMatch, tail: IMatch[]): IMatch[] {
194 if (tail.length === 0) {
201 return tail;
202 }
203 > filters.ts
204 function nextAnchor(camelCaseWord: string, start: number): number {
205 for (let i = start; i < camelCaseWord.length; i++) {
211 return camelCaseWord.length;
212 }
213 > filters.ts
214 function _matchesCamelCase(word: string, camelCaseWord: string, i: number, j: number): IMatch[] | null {
215 if (i === word.length) {
230 }
231 }
232 > filters.ts
233 > interface ICamelCaseAnalysis {
234 > upperPercent: number;
235 > lowerPercent: number;
236 > alphaPercent: number;
237 > numericPercent: number;
238 > }
239 >
240 > // Heuristic to avoid computing camel case matcher for words that don't
241 > // look like camelCaseWords.
242 function analyzeCamelCaseWord(word: string): ICamelCaseAnalysis {
243 let upper = 0, lower = 0, alpha = 0, numeric = 0, code = 0;
259 return { upperPercent, lowerPercent, alphaPercent, numericPercent };
260 }
261 > filters.ts
262 function isUpperCaseWord(analysis: ICamelCaseAnalysis): boolean {
263 const { upperPercent, lowerPercent } = analysis;
264 return lowerPercent === 0 && upperPercent > 0.6;
265 }
266 > filters.ts
267 function isCamelCaseWord(analysis: ICamelCaseAnalysis): boolean {
268 const { upperPercent, lowerPercent, alphaPercent, numericPercent } = analysis;
269 return lowerPercent > 0.2 && upperPercent < 0.8 && alphaPercent > 0.6 && numericPercent < 0.2;
270 }
271 > filters.ts
272 > // Heuristic to avoid computing camel case matcher for words that don't
273 > // look like camel case patterns.
274 function isCamelCasePattern(word: string): boolean {
275 let upper = 0, lower = 0, code = 0, whitespace = 0;
289 }
290 }
291 > filters.ts
292 > export function matchesCamelCase(word: string, camelCaseWord: string): IMatch[] | null {
293 if (!camelCaseWord) {
294 return null;
330 return result;
331 }
332 > filters.ts
333 > // Matches beginning of words supporting non-ASCII languages
334 > // If `contiguous` is true then matches word with beginnings of the words in the target. E.g. "pul" will match "Git: Pull"
335 > // Otherwise also matches sub string of the word with beginnings of the words in the target. E.g. "gp" or "g p" will match "Git: Pull"
336 > // Useful in cases where the target is words (e.g. command labels)
337 >
338 > export function matchesWords(word: string, target: string, contiguous: boolean = false): IMatch[] | null {
339 if (!target || target.length === 0) {
340 return null;
361 return result;
362 }
363 > filters.ts
364 function cloneMatches(matches: IMatch[] | null): IMatch[] | null {
365 if (matches === null) {
372 return result;
373 }
374 > filters.ts
375 function _matchesWords(word: string, target: string, wordIndex: number, targetIndex: number, contiguous: boolean, memo: Map<number, IMatch[] | null>): IMatch[] | null {
376 if (wordIndex === word.length) {
391 return computed;
392 }
393 > filters.ts
394 function _matchesWordsCompute(word: string, target: string, wordIndex: number, targetIndex: number, contiguous: boolean, memo: Map<number, IMatch[] | null>): IMatch[] | null {
395 let targetIndexOffset = 0;
440 return join({ start: targetIndex, end: targetIndex + targetIndexOffset + 1 }, result);
441 }
442 > filters.ts
443 function nextWord(word: string, start: number): number {
444 for (let i = start; i < word.length; i++) {
450 return word.length;
451 }
452 > filters.ts
453 > // Fuzzy
454 >
455 > const fuzzyContiguousFilter = or(matchesPrefix, matchesCamelCase, matchesContiguousSubString);
456 > const fuzzySeparateFilter = or(matchesPrefix, matchesCamelCase, matchesSubString);
457 > const fuzzyRegExpCache = new LRUCache<string, RegExp>(10000); // bounded to 10000 elements
458 >
459 > export function matchesFuzzy(word: string, wordToMatchAgainst: string, enableSeparateSubstringMatching = false): IMatch[] | null {
460 if (typeof word !== 'string' || typeof wordToMatchAgainst !== 'string') {
461 return null; // return early for invalid input
478 return enableSeparateSubstringMatching ? fuzzySeparateFilter(word, wordToMatchAgainst) : fuzzyContiguousFilter(word, wordToMatchAgainst);
479 }
480 > filters.ts
481 > /**
482 > * Match pattern against word in a fuzzy way. As in IntelliSense and faster and more
483 > * powerful than `matchesFuzzy`
484 > */
485 > export function matchesFuzzy2(pattern: string, word: string): IMatch[] | null {
486 const score = fuzzyScore(pattern, pattern.toLowerCase(), 0, word, word.toLowerCase(), 0, { firstMatchCanBeWeak: true, boostFullMatch: true });
487 return score ? createMatches(score) : null;
488 }
489 > filters.ts
490 > export function anyScore(pattern: string, lowPattern: string, patternPos: number, word: string, lowWord: string, wordPos: number): FuzzyScore {
491 const max = Math.min(13, pattern.length);
492 for (; patternPos < max; patternPos++) {
498 return [0, wordPos];
499 }
500 > filters.ts
501 > //#region --- fuzzyScore ---
502 >
503 > export function createMatches(score: undefined | FuzzyScore): IMatch[] {
504 if (typeof score === 'undefined') {
505 return [];
518 return res;
519 }
520 > filters.ts
521 > const _maxLen = 128;
522 >
523 > function initTable() {
524 > const table: number[][] = [];
525 > const row: number[] = [];
526 > for (let i = 0; i <= _maxLen; i++) {
527 > row[i] = 0;
528 > }
529 > for (let i = 0; i <= _maxLen; i++) {
530 > table.push(row.slice(0));
531 > }
532 > return table;
533 > }
534 >
535 > function initArr(maxLen: number) {
536 > const row: number[] = [];
537 > for (let i = 0; i <= maxLen; i++) {
538 > row[i] = 0;
539 > }
540 > return row;
541 > }
542 >
543 > const _minWordMatchPos = initArr(2 * _maxLen); // min word position for a certain pattern position
544 > const _maxWordMatchPos = initArr(2 * _maxLen); // max word position for a certain pattern position
545 > const _diag = initTable(); // the length of a contiguous diagonal match
546 > const _table = initTable();
547 > const _arrows = <Arrow[][]>initTable();
548 > const _debug = false;
549 >
550 function printTable(table: number[][], pattern: string, patternLen: number, word: string, wordLen: number): string {
551 function pad(s: string, n: number, pad = ' ') {
567 return ret;
568 }
569 > filters.ts
570 function printTables(pattern: string, patternStart: number, word: string, wordStart: number): void {
571 pattern = pattern.substr(patternStart);
575 console.log(printTable(_diag, pattern, pattern.length, word, word.length));
576 }
577 > filters.ts
578 function isSeparatorAtPos(value: string, index: number): boolean {
579 if (index < 0 || index >= value.length) {
610 }
611 }
612 > filters.ts
613 function isWhitespaceAtPos(value: string, index: number): boolean {
614 if (index < 0 || index >= value.length) {
624 }
625 }
626 > filters.ts
627 function isUpperCaseAtPos(pos: number, word: string, wordLow: string): boolean {
628 return word[pos] !== wordLow[pos];
629 }
630 > filters.ts
631 > export function isPatternInWord(patternLow: string, patternPos: number, patternLen: number, wordLow: string, wordPos: number, wordLen: number, fillMinWordPosArr = false): boolean {
632 while (patternPos < patternLen && wordPos < wordLen) {
633 if (patternLow[patternPos] === wordLow[wordPos]) {
642 return patternPos === patternLen; // pattern must be exhausted
643 }
644 > filters.ts
645 > const enum Arrow { Diag = 1, Left = 2, LeftLeft = 3 }
646 >
647 > /**
648 > * An array representing a fuzzy match.
649 > *
650 > * 0. the score
651 > * 1. the offset at which matching started
652 > * 2. `<match_pos_N>`
653 > * 3. `<match_pos_1>`
654 > * 4. `<match_pos_0>` etc
655 > */
656 > export type FuzzyScore = [score: number, wordStart: number, ...matches: number[]];
657 >
658 > export namespace FuzzyScore {
659 > /**
660 > * No matches and value `-100`
661 > */
662 > export const Default: FuzzyScore = ([-100, 0]);
663 >
664 > export function isDefault(score?: FuzzyScore): score is [-100, 0] {
665 return !score || (score.length === 2 && score[0] === -100 && score[1] === 0);
666 }
667 > } filters.ts
668 >
669 > export abstract class FuzzyScoreOptions {
670 >
671 > static default = { boostFullMatch: true, firstMatchCanBeWeak: false };
672 >
673 > constructor(
674 readonly firstMatchCanBeWeak: boolean,
675 readonly boostFullMatch: boolean,
676 ) { }
677 > } filters.ts
678 >
679 > export interface FuzzyScorer {
680 > (pattern: string, lowPattern: string, patternPos: number, word: string, lowWord: string, wordPos: number, options?: FuzzyScoreOptions): FuzzyScore | undefined;
681 > }
682 >
683 > export function fuzzyScore(pattern: string, patternLow: string, patternStart: number, word: string, wordLow: string, wordStart: number, options: FuzzyScoreOptions = FuzzyScoreOptions.default): FuzzyScore | undefined {
684
685 const patternLen = pattern.length > _maxLen ? _maxLen : pattern.length;
832 return result;
833 }
834 > filters.ts
835 function _fillInMaxWordMatchPos(patternLen: number, wordLen: number, patternStart: number, wordStart: number, patternLow: string, wordLow: string) {
836 let patternPos = patternLen - 1;
844 }
845 }
846 > filters.ts
847 function _doScore(
848 pattern: string, patternLow: string, patternPos: number, patternStart: number,
913 return score;
914 }
915 > filters.ts
916 > //#endregion
917 >
918 >
919 > //#region --- graceful ---
920 >
921 > export function fuzzyScoreGracefulAggressive(pattern: string, lowPattern: string, patternPos: number, word: string, lowWord: string, wordPos: number, options?: FuzzyScoreOptions): FuzzyScore | undefined {
922 return fuzzyScoreWithPermutations(pattern, lowPattern, patternPos, word, lowWord, wordPos, true, options);
923 }
924 > filters.ts
925 > export function fuzzyScoreGraceful(pattern: string, lowPattern: string, patternPos: number, word: string, lowWord: string, wordPos: number, options?: FuzzyScoreOptions): FuzzyScore | undefined {
926 return fuzzyScoreWithPermutations(pattern, lowPattern, patternPos, word, lowWord, wordPos, false, options);
927 }
928 > filters.ts
929 function fuzzyScoreWithPermutations(pattern: string, lowPattern: string, patternPos: number, word: string, lowWord: string, wordPos: number, aggressive: boolean, options?: FuzzyScoreOptions): FuzzyScore | undefined {
930 let top = fuzzyScore(pattern, lowPattern, patternPos, word, lowWord, wordPos, options);
959 return top;
960 }
961 > filters.ts
962 function nextTypoPermutation(pattern: string, patternPos: number): string | undefined {
963
978 + pattern.slice(patternPos + 2);
979 }
980 > filters.ts
981 > //#endregion