deno.land / x / fuse@v6.4.1 / dist / fuse.esm.js
نووسراو ببینە
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636163716381639164016411642164316441645164616471648164916501651165216531654165516561657165816591660166116621663166416651666166716681669167016711672167316741675167616771678167916801681168216831684168516861687168816891690169116921693169416951696169716981699170017011702170317041705170617071708170917101711171217131714171517161717171817191720172117221723172417251726172717281729173017311732173317341735173617371738173917401741174217431744174517461747174817491750175117521753175417551756175717581759176017611762176317641765176617671768/** * Fuse.js v6.4.1 - Lightweight fuzzy-search (http://fusejs.io) * * Copyright (c) 2020 Kiro Risk (http://kiro.me) * All Rights Reserved. Apache Software License 2.0 * * http://www.apache.org/licenses/LICENSE-2.0 */
function isArray(value) { return !Array.isArray ? getTag(value) === '[object Array]' : Array.isArray(value)}
// Adapted from: https://github.com/lodash/lodash/blob/master/.internal/baseToString.jsconst INFINITY = 1 / 0;function baseToString(value) { // Exit early for strings to avoid a performance hit in some environments. if (typeof value == 'string') { return value } let result = value + ''; return result == '0' && 1 / value == -INFINITY ? '-0' : result}
function toString(value) { return value == null ? '' : baseToString(value)}
function isString(value) { return typeof value === 'string'}
function isNumber(value) { return typeof value === 'number'}
// Adapted from: https://github.com/lodash/lodash/blob/master/isBoolean.jsfunction isBoolean(value) { return ( value === true || value === false || (isObjectLike(value) && getTag(value) == '[object Boolean]') )}
function isObject(value) { return typeof value === 'object'}
// Checks if `value` is object-like.function isObjectLike(value) { return isObject(value) && value !== null}
function isDefined(value) { return value !== undefined && value !== null}
function isBlank(value) { return !value.trim().length}
// Gets the `toStringTag` of `value`.// Adapted from: https://github.com/lodash/lodash/blob/master/.internal/getTag.jsfunction getTag(value) { return value == null ? value === undefined ? '[object Undefined]' : '[object Null]' : Object.prototype.toString.call(value)}
const EXTENDED_SEARCH_UNAVAILABLE = 'Extended search is not available';
const INCORRECT_INDEX_TYPE = "Incorrect 'index' type";
const LOGICAL_SEARCH_INVALID_QUERY_FOR_KEY = (key) => `Invalid value for key ${key}`;
const PATTERN_LENGTH_TOO_LARGE = (max) => `Pattern length exceeds max of ${max}.`;
const MISSING_KEY_PROPERTY = (name) => `Missing ${name} property in key`;
const INVALID_KEY_WEIGHT_VALUE = (key) => `Property 'weight' in key '${key}' must be a positive integer`;
const hasOwn = Object.prototype.hasOwnProperty;
class KeyStore { constructor(keys) { this._keys = []; this._keyMap = {};
let totalWeight = 0;
keys.forEach((key) => { let obj = createKey(key);
totalWeight += obj.weight;
this._keys.push(obj); this._keyMap[obj.id] = obj;
totalWeight += obj.weight; });
// Normalize weights so that their sum is equal to 1 this._keys.forEach((key) => { key.weight /= totalWeight; }); } get(keyId) { return this._keyMap[keyId] } keys() { return this._keys } toJSON() { return JSON.stringify(this._keys) }}
function createKey(key) { let path = null; let id = null; let src = null; let weight = 1;
if (isString(key) || isArray(key)) { src = key; path = createKeyPath(key); id = createKeyId(key); } else { if (!hasOwn.call(key, 'name')) { throw new Error(MISSING_KEY_PROPERTY('name')) }
const name = key.name; src = name;
if (hasOwn.call(key, 'weight')) { weight = key.weight;
if (weight <= 0) { throw new Error(INVALID_KEY_WEIGHT_VALUE(name)) } }
path = createKeyPath(name); id = createKeyId(name); }
return { path, id, weight, src }}
function createKeyPath(key) { return isArray(key) ? key : key.split('.')}
function createKeyId(key) { return isArray(key) ? key.join('.') : key}
function get(obj, path) { let list = []; let arr = false;
const deepGet = (obj, path, index) => { if (!path[index]) { // If there's no path left, we've arrived at the object we care about. list.push(obj); } else { let key = path[index];
const value = obj[key];
if (!isDefined(value)) { return }
// If we're at the last value in the path, and if it's a string/number/bool, // add it to the list if ( index === path.length - 1 && (isString(value) || isNumber(value) || isBoolean(value)) ) { list.push(toString(value)); } else if (isArray(value)) { arr = true; // Search each item in the array. for (let i = 0, len = value.length; i < len; i += 1) { deepGet(value[i], path, index + 1); } } else if (path.length) { // An object. Recurse further. deepGet(value, path, index + 1); } } };
// Backwards compatibility (since path used to be a string) deepGet(obj, isString(path) ? path.split('.') : path, 0);
return arr ? list : list[0]}
const MatchOptions = { // Whether the matches should be included in the result set. When `true`, each record in the result // set will include the indices of the matched characters. // These can consequently be used for highlighting purposes. includeMatches: false, // When `true`, the matching function will continue to the end of a search pattern even if // a perfect match has already been located in the string. findAllMatches: false, // Minimum number of characters that must be matched before a result is considered a match minMatchCharLength: 1};
const BasicOptions = { // When `true`, the algorithm continues searching to the end of the input even if a perfect // match is found before the end of the same input. isCaseSensitive: false, // When true, the matching function will continue to the end of a search pattern even if includeScore: false, // List of properties that will be searched. This also supports nested properties. keys: [], // Whether to sort the result list, by score shouldSort: true, // Default sort function: sort by ascending score, ascending index sortFn: (a, b) => a.score === b.score ? (a.idx < b.idx ? -1 : 1) : a.score < b.score ? -1 : 1};
const FuzzyOptions = { // Approximately where in the text is the pattern expected to be found? location: 0, // At what point does the match algorithm give up. A threshold of '0.0' requires a perfect match // (of both letters and location), a threshold of '1.0' would match anything. threshold: 0.6, // Determines how close the match must be to the fuzzy location (specified above). // An exact letter match which is 'distance' characters away from the fuzzy location // would score as a complete mismatch. A distance of '0' requires the match be at // the exact location specified, a threshold of '1000' would require a perfect match // to be within 800 characters of the fuzzy location to be found using a 0.8 threshold. distance: 100};
const AdvancedOptions = { // When `true`, it enables the use of unix-like search commands useExtendedSearch: false, // The get function to use when fetching an object's properties. // The default will search nested paths *ie foo.bar.baz* getFn: get, // When `true`, search will ignore `location` and `distance`, so it won't matter // where in the string the pattern appears. // More info: https://fusejs.io/concepts/scoring-theory.html#fuzziness-score ignoreLocation: false, // When `true`, the calculation for the relevance score (used for sorting) will // ignore the field-length norm. // More info: https://fusejs.io/concepts/scoring-theory.html#field-length-norm ignoreFieldNorm: false};
var Config = { ...BasicOptions, ...MatchOptions, ...FuzzyOptions, ...AdvancedOptions};
const SPACE = /[^ ]+/g;
// Field-length norm: the shorter the field, the higher the weight.// Set to 3 decimals to reduce index size.function norm(mantissa = 3) { const cache = new Map();
return { get(value) { const numTokens = value.match(SPACE).length;
if (cache.has(numTokens)) { return cache.get(numTokens) }
const n = parseFloat((1 / Math.sqrt(numTokens)).toFixed(mantissa));
cache.set(numTokens, n);
return n }, clear() { cache.clear(); } }}
class FuseIndex { constructor({ getFn = Config.getFn } = {}) { this.norm = norm(3); this.getFn = getFn; this.isCreated = false;
this.setIndexRecords(); } setSources(docs = []) { this.docs = docs; } setIndexRecords(records = []) { this.records = records; } setKeys(keys = []) { this.keys = keys; this._keysMap = {}; keys.forEach((key, idx) => { this._keysMap[key.id] = idx; }); } create() { if (this.isCreated || !this.docs.length) { return }
this.isCreated = true;
// List is Array<String> if (isString(this.docs[0])) { this.docs.forEach((doc, docIndex) => { this._addString(doc, docIndex); }); } else { // List is Array<Object> this.docs.forEach((doc, docIndex) => { this._addObject(doc, docIndex); }); }
this.norm.clear(); } // Adds a doc to the end of the index add(doc) { const idx = this.size();
if (isString(doc)) { this._addString(doc, idx); } else { this._addObject(doc, idx); } } // Removes the doc at the specified index of the index removeAt(idx) { this.records.splice(idx, 1);
// Change ref index of every subsquent doc for (let i = idx, len = this.size(); i < len; i += 1) { this.records[i].i -= 1; } } getValueForItemAtKeyId(item, keyId) { return item[this._keysMap[keyId]] } size() { return this.records.length } _addString(doc, docIndex) { if (!isDefined(doc) || isBlank(doc)) { return }
let record = { v: doc, i: docIndex, n: this.norm.get(doc) };
this.records.push(record); } _addObject(doc, docIndex) { let record = { i: docIndex, $: {} };
// Iterate over every key (i.e, path), and fetch the value at that key this.keys.forEach((key, keyIndex) => { // console.log(key) let value = this.getFn(doc, key.path);
if (!isDefined(value)) { return }
if (isArray(value)) { let subRecords = []; const stack = [{ nestedArrIndex: -1, value }];
while (stack.length) { const { nestedArrIndex, value } = stack.pop();
if (!isDefined(value)) { continue }
if (isString(value) && !isBlank(value)) { let subRecord = { v: value, i: nestedArrIndex, n: this.norm.get(value) };
subRecords.push(subRecord); } else if (isArray(value)) { value.forEach((item, k) => { stack.push({ nestedArrIndex: k, value: item }); }); } } record.$[keyIndex] = subRecords; } else if (!isBlank(value)) { let subRecord = { v: value, n: this.norm.get(value) };
record.$[keyIndex] = subRecord; } });
this.records.push(record); } toJSON() { return { keys: this.keys, records: this.records } }}
function createIndex(keys, docs, { getFn = Config.getFn } = {}) { const myIndex = new FuseIndex({ getFn }); myIndex.setKeys(keys.map(createKey)); myIndex.setSources(docs); myIndex.create(); return myIndex}
function parseIndex(data, { getFn = Config.getFn } = {}) { const { keys, records } = data; const myIndex = new FuseIndex({ getFn }); myIndex.setKeys(keys); myIndex.setIndexRecords(records); return myIndex}
function transformMatches(result, data) { const matches = result.matches; data.matches = [];
if (!isDefined(matches)) { return }
matches.forEach((match) => { if (!isDefined(match.indices) || !match.indices.length) { return }
const { indices, value } = match;
let obj = { indices, value };
if (match.key) { obj.key = match.key.src; }
if (match.idx > -1) { obj.refIndex = match.idx; }
data.matches.push(obj); });}
function transformScore(result, data) { data.score = result.score;}
function computeScore( pattern, { errors = 0, currentLocation = 0, expectedLocation = 0, distance = Config.distance, ignoreLocation = Config.ignoreLocation } = {}) { const accuracy = errors / pattern.length;
if (ignoreLocation) { return accuracy }
const proximity = Math.abs(expectedLocation - currentLocation);
if (!distance) { // Dodge divide by zero error. return proximity ? 1.0 : accuracy }
return accuracy + proximity / distance}
function convertMaskToIndices( matchmask = [], minMatchCharLength = Config.minMatchCharLength) { let indices = []; let start = -1; let end = -1; let i = 0;
for (let len = matchmask.length; i < len; i += 1) { let match = matchmask[i]; if (match && start === -1) { start = i; } else if (!match && start !== -1) { end = i - 1; if (end - start + 1 >= minMatchCharLength) { indices.push([start, end]); } start = -1; } }
// (i-1 - start) + 1 => i - start if (matchmask[i - 1] && i - start >= minMatchCharLength) { indices.push([start, i - 1]); }
return indices}
// Machine word sizeconst MAX_BITS = 32;
function search( text, pattern, patternAlphabet, { location = Config.location, distance = Config.distance, threshold = Config.threshold, findAllMatches = Config.findAllMatches, minMatchCharLength = Config.minMatchCharLength, includeMatches = Config.includeMatches, ignoreLocation = Config.ignoreLocation } = {}) { if (pattern.length > MAX_BITS) { throw new Error(PATTERN_LENGTH_TOO_LARGE(MAX_BITS)) }
const patternLen = pattern.length; // Set starting location at beginning text and initialize the alphabet. const textLen = text.length; // Handle the case when location > text.length const expectedLocation = Math.max(0, Math.min(location, textLen)); // Highest score beyond which we give up. let currentThreshold = threshold; // Is there a nearby exact match? (speedup) let bestLocation = expectedLocation;
// Performance: only computer matches when the minMatchCharLength > 1 // OR if `includeMatches` is true. const computeMatches = minMatchCharLength > 1 || includeMatches; // A mask of the matches, used for building the indices const matchMask = computeMatches ? Array(textLen) : [];
let index;
// Get all exact matches, here for speed up while ((index = text.indexOf(pattern, bestLocation)) > -1) { let score = computeScore(pattern, { currentLocation: index, expectedLocation, distance, ignoreLocation });
currentThreshold = Math.min(score, currentThreshold); bestLocation = index + patternLen;
if (computeMatches) { let i = 0; while (i < patternLen) { matchMask[index + i] = 1; i += 1; } } }
// Reset the best location bestLocation = -1;
let lastBitArr = []; let finalScore = 1; let binMax = patternLen + textLen;
const mask = 1 << (patternLen - 1);
for (let i = 0; i < patternLen; i += 1) { // Scan for the best match; each iteration allows for one more error. // Run a binary search to determine how far from the match location we can stray // at this error level. let binMin = 0; let binMid = binMax;
while (binMin < binMid) { const score = computeScore(pattern, { errors: i, currentLocation: expectedLocation + binMid, expectedLocation, distance, ignoreLocation });
if (score <= currentThreshold) { binMin = binMid; } else { binMax = binMid; }
binMid = Math.floor((binMax - binMin) / 2 + binMin); }
// Use the result from this iteration as the maximum for the next. binMax = binMid;
let start = Math.max(1, expectedLocation - binMid + 1); let finish = findAllMatches ? textLen : Math.min(expectedLocation + binMid, textLen) + patternLen;
// Initialize the bit array let bitArr = Array(finish + 2);
bitArr[finish + 1] = (1 << i) - 1;
for (let j = finish; j >= start; j -= 1) { let currentLocation = j - 1; let charMatch = patternAlphabet[text.charAt(currentLocation)];
if (computeMatches) { // Speed up: quick bool to int conversion (i.e, `charMatch ? 1 : 0`) matchMask[currentLocation] = +!!charMatch; }
// First pass: exact match bitArr[j] = ((bitArr[j + 1] << 1) | 1) & charMatch;
// Subsequent passes: fuzzy match if (i) { bitArr[j] |= ((lastBitArr[j + 1] | lastBitArr[j]) << 1) | 1 | lastBitArr[j + 1]; }
if (bitArr[j] & mask) { finalScore = computeScore(pattern, { errors: i, currentLocation, expectedLocation, distance, ignoreLocation });
// This match will almost certainly be better than any existing match. // But check anyway. if (finalScore <= currentThreshold) { // Indeed it is currentThreshold = finalScore; bestLocation = currentLocation;
// Already passed `loc`, downhill from here on in. if (bestLocation <= expectedLocation) { break }
// When passing `bestLocation`, don't exceed our current distance from `expectedLocation`. start = Math.max(1, 2 * expectedLocation - bestLocation); } } }
// No hope for a (better) match at greater error levels. const score = computeScore(pattern, { errors: i + 1, currentLocation: expectedLocation, expectedLocation, distance, ignoreLocation });
if (score > currentThreshold) { break }
lastBitArr = bitArr; }
const result = { isMatch: bestLocation >= 0, // Count exact matches (those with a score of 0) to be "almost" exact score: Math.max(0.001, finalScore) };
if (computeMatches) { const indices = convertMaskToIndices(matchMask, minMatchCharLength); if (!indices.length) { result.isMatch = false; } else if (includeMatches) { result.indices = indices; } }
return result}
function createPatternAlphabet(pattern) { let mask = {};
for (let i = 0, len = pattern.length; i < len; i += 1) { const char = pattern.charAt(i); mask[char] = (mask[char] || 0) | (1 << (len - i - 1)); }
return mask}
class BitapSearch { constructor( pattern, { location = Config.location, threshold = Config.threshold, distance = Config.distance, includeMatches = Config.includeMatches, findAllMatches = Config.findAllMatches, minMatchCharLength = Config.minMatchCharLength, isCaseSensitive = Config.isCaseSensitive, ignoreLocation = Config.ignoreLocation } = {} ) { this.options = { location, threshold, distance, includeMatches, findAllMatches, minMatchCharLength, isCaseSensitive, ignoreLocation };
this.pattern = isCaseSensitive ? pattern : pattern.toLowerCase();
this.chunks = [];
if (!this.pattern.length) { return }
const addChunk = (pattern, startIndex) => { this.chunks.push({ pattern, alphabet: createPatternAlphabet(pattern), startIndex }); };
const len = this.pattern.length;
if (len > MAX_BITS) { let i = 0; const remainder = len % MAX_BITS; const end = len - remainder;
while (i < end) { addChunk(this.pattern.substr(i, MAX_BITS), i); i += MAX_BITS; }
if (remainder) { const startIndex = len - MAX_BITS; addChunk(this.pattern.substr(startIndex), startIndex); } } else { addChunk(this.pattern, 0); } }
searchIn(text) { const { isCaseSensitive, includeMatches } = this.options;
if (!isCaseSensitive) { text = text.toLowerCase(); }
// Exact match if (this.pattern === text) { let result = { isMatch: true, score: 0 };
if (includeMatches) { result.indices = [[0, text.length - 1]]; }
return result }
// Otherwise, use Bitap algorithm const { location, distance, threshold, findAllMatches, minMatchCharLength, ignoreLocation } = this.options;
let allIndices = []; let totalScore = 0; let hasMatches = false;
this.chunks.forEach(({ pattern, alphabet, startIndex }) => { const { isMatch, score, indices } = search(text, pattern, alphabet, { location: location + startIndex, distance, threshold, findAllMatches, minMatchCharLength, includeMatches, ignoreLocation });
if (isMatch) { hasMatches = true; }
totalScore += score;
if (isMatch && indices) { allIndices = [...allIndices, ...indices]; } });
let result = { isMatch: hasMatches, score: hasMatches ? totalScore / this.chunks.length : 1 };
if (hasMatches && includeMatches) { result.indices = allIndices; }
return result }}
class BaseMatch { constructor(pattern) { this.pattern = pattern; } static isMultiMatch(pattern) { return getMatch(pattern, this.multiRegex) } static isSingleMatch(pattern) { return getMatch(pattern, this.singleRegex) } search(/*text*/) {}}
function getMatch(pattern, exp) { const matches = pattern.match(exp); return matches ? matches[1] : null}
// Token: 'file
class ExactMatch extends BaseMatch { constructor(pattern) { super(pattern); } static get type() { return 'exact' } static get multiRegex() { return /^="(.*)"$/ } static get singleRegex() { return /^=(.*)$/ } search(text) { const isMatch = text === this.pattern;
return { isMatch, score: isMatch ? 0 : 1, indices: [0, this.pattern.length - 1] } }}
// Token: !fire
class InverseExactMatch extends BaseMatch { constructor(pattern) { super(pattern); } static get type() { return 'inverse-exact' } static get multiRegex() { return /^!"(.*)"$/ } static get singleRegex() { return /^!(.*)$/ } search(text) { const index = text.indexOf(this.pattern); const isMatch = index === -1;
return { isMatch, score: isMatch ? 0 : 1, indices: [0, text.length - 1] } }}
// Token: ^file
class PrefixExactMatch extends BaseMatch { constructor(pattern) { super(pattern); } static get type() { return 'prefix-exact' } static get multiRegex() { return /^\^"(.*)"$/ } static get singleRegex() { return /^\^(.*)$/ } search(text) { const isMatch = text.startsWith(this.pattern);
return { isMatch, score: isMatch ? 0 : 1, indices: [0, this.pattern.length - 1] } }}
// Token: !^fire
class InversePrefixExactMatch extends BaseMatch { constructor(pattern) { super(pattern); } static get type() { return 'inverse-prefix-exact' } static get multiRegex() { return /^!\^"(.*)"$/ } static get singleRegex() { return /^!\^(.*)$/ } search(text) { const isMatch = !text.startsWith(this.pattern);
return { isMatch, score: isMatch ? 0 : 1, indices: [0, text.length - 1] } }}
// Token: .file$
class SuffixExactMatch extends BaseMatch { constructor(pattern) { super(pattern); } static get type() { return 'suffix-exact' } static get multiRegex() { return /^"(.*)"\$$/ } static get singleRegex() { return /^(.*)\$$/ } search(text) { const isMatch = text.endsWith(this.pattern);
return { isMatch, score: isMatch ? 0 : 1, indices: [text.length - this.pattern.length, text.length - 1] } }}
// Token: !.file$
class InverseSuffixExactMatch extends BaseMatch { constructor(pattern) { super(pattern); } static get type() { return 'inverse-suffix-exact' } static get multiRegex() { return /^!"(.*)"\$$/ } static get singleRegex() { return /^!(.*)\$$/ } search(text) { const isMatch = !text.endsWith(this.pattern); return { isMatch, score: isMatch ? 0 : 1, indices: [0, text.length - 1] } }}
class FuzzyMatch extends BaseMatch { constructor( pattern, { location = Config.location, threshold = Config.threshold, distance = Config.distance, includeMatches = Config.includeMatches, findAllMatches = Config.findAllMatches, minMatchCharLength = Config.minMatchCharLength, isCaseSensitive = Config.isCaseSensitive } = {} ) { super(pattern); this._bitapSearch = new BitapSearch(pattern, { location, threshold, distance, includeMatches, findAllMatches, minMatchCharLength, isCaseSensitive }); } static get type() { return 'fuzzy' } static get multiRegex() { return /^"(.*)"$/ } static get singleRegex() { return /^(.*)$/ } search(text) { return this._bitapSearch.searchIn(text) }}
// Token: 'file
class IncludeMatch extends BaseMatch { constructor(pattern) { super(pattern); } static get type() { return 'include' } static get multiRegex() { return /^'"(.*)"$/ } static get singleRegex() { return /^'(.*)$/ } search(text) { let location = 0; let index;
const indices = []; const patternLen = this.pattern.length;
// Get all exact matches while ((index = text.indexOf(this.pattern, location)) > -1) { location = index + patternLen; indices.push([index, location - 1]); }
const isMatch = !!indices.length;
return { isMatch, score: isMatch ? 1 : 0, indices } }}
// ❗Order is important. DO NOT CHANGE.const searchers = [ ExactMatch, IncludeMatch, PrefixExactMatch, InversePrefixExactMatch, InverseSuffixExactMatch, SuffixExactMatch, InverseExactMatch, FuzzyMatch];
const searchersLen = searchers.length;
// Regex to split by spaces, but keep anything in quotes togetherconst SPACE_RE = / +(?=([^\"]*\"[^\"]*\")*[^\"]*$)/;const OR_TOKEN = '|';
// Return a 2D array representation of the query, for simpler parsing.// Example:// "^core go$ | rb$ | py$ xy$" => [["^core", "go$"], ["rb$"], ["py$", "xy$"]]function parseQuery(pattern, options = {}) { return pattern.split(OR_TOKEN).map((item) => { let query = item .trim() .split(SPACE_RE) .filter((item) => item && !!item.trim());
let results = []; for (let i = 0, len = query.length; i < len; i += 1) { const queryItem = query[i];
// 1. Handle multiple query match (i.e, once that are quoted, like `"hello world"`) let found = false; let idx = -1; while (!found && ++idx < searchersLen) { const searcher = searchers[idx]; let token = searcher.isMultiMatch(queryItem); if (token) { results.push(new searcher(token, options)); found = true; } }
if (found) { continue }
// 2. Handle single query matches (i.e, once that are *not* quoted) idx = -1; while (++idx < searchersLen) { const searcher = searchers[idx]; let token = searcher.isSingleMatch(queryItem); if (token) { results.push(new searcher(token, options)); break } } }
return results })}
// These extended matchers can return an array of matches, as opposed// to a singl matchconst MultiMatchSet = new Set([FuzzyMatch.type, IncludeMatch.type]);
/** * Command-like searching * ====================== * * Given multiple search terms delimited by spaces.e.g. `^jscript .python$ ruby !java`, * search in a given text. * * Search syntax: * * | Token | Match type | Description | * | ----------- | -------------------------- | -------------------------------------- | * | `jscript` | fuzzy-match | Items that fuzzy match `jscript` | * | `=scheme` | exact-match | Items that are `scheme` | * | `'python` | include-match | Items that include `python` | * | `!ruby` | inverse-exact-match | Items that do not include `ruby` | * | `^java` | prefix-exact-match | Items that start with `java` | * | `!^earlang` | inverse-prefix-exact-match | Items that do not start with `earlang` | * | `.js$` | suffix-exact-match | Items that end with `.js` | * | `!.go$` | inverse-suffix-exact-match | Items that do not end with `.go` | * * A single pipe character acts as an OR operator. For example, the following * query matches entries that start with `core` and end with either`go`, `rb`, * or`py`. * * ``` * ^core go$ | rb$ | py$ * ``` */class ExtendedSearch { constructor( pattern, { isCaseSensitive = Config.isCaseSensitive, includeMatches = Config.includeMatches, minMatchCharLength = Config.minMatchCharLength, findAllMatches = Config.findAllMatches, location = Config.location, threshold = Config.threshold, distance = Config.distance } = {} ) { this.query = null; this.options = { isCaseSensitive, includeMatches, minMatchCharLength, findAllMatches, location, threshold, distance };
this.pattern = isCaseSensitive ? pattern : pattern.toLowerCase(); this.query = parseQuery(this.pattern, this.options); }
static condition(_, options) { return options.useExtendedSearch }
searchIn(text) { const query = this.query;
if (!query) { return { isMatch: false, score: 1 } }
const { includeMatches, isCaseSensitive } = this.options;
text = isCaseSensitive ? text : text.toLowerCase();
let numMatches = 0; let allIndices = []; let totalScore = 0;
// ORs for (let i = 0, qLen = query.length; i < qLen; i += 1) { const searchers = query[i];
// Reset indices allIndices.length = 0; numMatches = 0;
// ANDs for (let j = 0, pLen = searchers.length; j < pLen; j += 1) { const searcher = searchers[j]; const { isMatch, indices, score } = searcher.search(text);
if (isMatch) { numMatches += 1; totalScore += score; if (includeMatches) { const type = searcher.constructor.type; if (MultiMatchSet.has(type)) { allIndices = [...allIndices, ...indices]; } else { allIndices.push(indices); } } } else { totalScore = 0; numMatches = 0; allIndices.length = 0; break } }
// OR condition, so if TRUE, return if (numMatches) { let result = { isMatch: true, score: totalScore / numMatches };
if (includeMatches) { result.indices = allIndices; }
return result } }
// Nothing was matched return { isMatch: false, score: 1 } }}
const registeredSearchers = [];
function register(...args) { registeredSearchers.push(...args);}
function createSearcher(pattern, options) { for (let i = 0, len = registeredSearchers.length; i < len; i += 1) { let searcherClass = registeredSearchers[i]; if (searcherClass.condition(pattern, options)) { return new searcherClass(pattern, options) } }
return new BitapSearch(pattern, options)}
const LogicalOperator = { AND: '$and', OR: '$or'};
const KeyType = { PATH: '$path', PATTERN: '$val'};
const isExpression = (query) => !!(query[LogicalOperator.AND] || query[LogicalOperator.OR]);
const isPath = (query) => !!query[KeyType.PATH];
const isLeaf = (query) => !isArray(query) && isObject(query) && !isExpression(query);
const convertToExplicit = (query) => ({ [LogicalOperator.AND]: Object.keys(query).map((key) => ({ [key]: query[key] }))});
// When `auto` is `true`, the parse function will infer and initialize and add// the appropriate `Searcher` instancefunction parse(query, options, { auto = true } = {}) { const next = (query) => { let keys = Object.keys(query);
const isQueryPath = isPath(query);
if (!isQueryPath && keys.length > 1 && !isExpression(query)) { return next(convertToExplicit(query)) }
if (isLeaf(query)) { const key = isQueryPath ? query[KeyType.PATH] : keys[0];
const pattern = isQueryPath ? query[KeyType.PATTERN] : query[key];
if (!isString(pattern)) { throw new Error(LOGICAL_SEARCH_INVALID_QUERY_FOR_KEY(key)) }
const obj = { keyId: createKeyId(key), pattern };
if (auto) { obj.searcher = createSearcher(pattern, options); }
return obj }
let node = { children: [], operator: keys[0] };
keys.forEach((key) => { const value = query[key];
if (isArray(value)) { value.forEach((item) => { node.children.push(next(item)); }); } });
return node };
if (!isExpression(query)) { query = convertToExplicit(query); }
return next(query)}
class Fuse { constructor(docs, options = {}, index) { this.options = { ...Config, ...options };
if ( this.options.useExtendedSearch && !true ) { throw new Error(EXTENDED_SEARCH_UNAVAILABLE) }
this._keyStore = new KeyStore(this.options.keys);
this.setCollection(docs, index); }
setCollection(docs, index) { this._docs = docs;
if (index && !(index instanceof FuseIndex)) { throw new Error(INCORRECT_INDEX_TYPE) }
this._myIndex = index || createIndex(this.options.keys, this._docs, { getFn: this.options.getFn }); }
add(doc) { if (!isDefined(doc)) { return }
this._docs.push(doc); this._myIndex.add(doc); }
remove(predicate = (/* doc, idx */) => false) { const results = [];
for (let i = 0, len = this._docs.length; i < len; i += 1) { const doc = this._docs[i]; if (predicate(doc, i)) { this.removeAt(i); i -= 1;
results.push(doc); } }
return results }
removeAt(idx) { this._docs.splice(idx, 1); this._myIndex.removeAt(idx); }
getIndex() { return this._myIndex }
search(query, { limit = -1 } = {}) { const { includeMatches, includeScore, shouldSort, sortFn, ignoreFieldNorm } = this.options;
let results = isString(query) ? isString(this._docs[0]) ? this._searchStringList(query) : this._searchObjectList(query) : this._searchLogical(query);
computeScore$1(results, { ignoreFieldNorm });
if (shouldSort) { results.sort(sortFn); }
if (isNumber(limit) && limit > -1) { results = results.slice(0, limit); }
return format(results, this._docs, { includeMatches, includeScore }) }
_searchStringList(query) { const searcher = createSearcher(query, this.options); const { records } = this._myIndex; const results = [];
// Iterate over every string in the index records.forEach(({ v: text, i: idx, n: norm }) => { if (!isDefined(text)) { return }
const { isMatch, score, indices } = searcher.searchIn(text);
if (isMatch) { results.push({ item: text, idx, matches: [{ score, value: text, norm, indices }] }); } });
return results }
_searchLogical(query) {
const expression = parse(query, this.options);
const evaluate = (node, item, idx) => { if (!node.children) { const { keyId, searcher } = node;
const matches = this._findMatches({ key: this._keyStore.get(keyId), value: this._myIndex.getValueForItemAtKeyId(item, keyId), searcher });
if (matches && matches.length) { return [ { idx, item, matches } ] }
return [] }
/*eslint indent: [2, 2, {"SwitchCase": 1}]*/ switch (node.operator) { case LogicalOperator.AND: { const res = []; for (let i = 0, len = node.children.length; i < len; i += 1) { const child = node.children[i]; const result = evaluate(child, item, idx); if (result.length) { res.push(...result); } else { return [] } } return res } case LogicalOperator.OR: { const res = []; for (let i = 0, len = node.children.length; i < len; i += 1) { const child = node.children[i]; const result = evaluate(child, item, idx); if (result.length) { res.push(...result); break } } return res } } };
const records = this._myIndex.records; const resultMap = {}; const results = [];
records.forEach(({ $: item, i: idx }) => { if (isDefined(item)) { let expResults = evaluate(expression, item, idx);
if (expResults.length) { // Dedupe when adding if (!resultMap[idx]) { resultMap[idx] = { idx, item, matches: [] }; results.push(resultMap[idx]); } expResults.forEach(({ matches }) => { resultMap[idx].matches.push(...matches); }); } } });
return results }
_searchObjectList(query) { const searcher = createSearcher(query, this.options); const { keys, records } = this._myIndex; const results = [];
// List is Array<Object> records.forEach(({ $: item, i: idx }) => { if (!isDefined(item)) { return }
let matches = [];
// Iterate over every key (i.e, path), and fetch the value at that key keys.forEach((key, keyIndex) => { matches.push( ...this._findMatches({ key, value: item[keyIndex], searcher }) ); });
if (matches.length) { results.push({ idx, item, matches }); } });
return results } _findMatches({ key, value, searcher }) { if (!isDefined(value)) { return [] }
let matches = [];
if (isArray(value)) { value.forEach(({ v: text, i: idx, n: norm }) => { if (!isDefined(text)) { return }
const { isMatch, score, indices } = searcher.searchIn(text);
if (isMatch) { matches.push({ score, key, value: text, idx, norm, indices }); } }); } else { const { v: text, n: norm } = value;
const { isMatch, score, indices } = searcher.searchIn(text);
if (isMatch) { matches.push({ score, key, value: text, norm, indices }); } }
return matches }}
// Practical scoring functionfunction computeScore$1(results, { ignoreFieldNorm = Config.ignoreFieldNorm }) { results.forEach((result) => { let totalScore = 1;
result.matches.forEach(({ key, norm, score }) => { const weight = key ? key.weight : null;
totalScore *= Math.pow( score === 0 && weight ? Number.EPSILON : score, (weight || 1) * (ignoreFieldNorm ? 1 : norm) ); });
result.score = totalScore; });}
function format( results, docs, { includeMatches = Config.includeMatches, includeScore = Config.includeScore } = {}) { const transformers = [];
if (includeMatches) transformers.push(transformMatches); if (includeScore) transformers.push(transformScore);
return results.map((result) => { const { idx } = result;
const data = { item: docs[idx], refIndex: idx };
if (transformers.length) { transformers.forEach((transformer) => { transformer(result, data); }); }
return data })}
Fuse.version = '6.4.1';Fuse.createIndex = createIndex;Fuse.parseIndex = parseIndex;Fuse.config = Config;
{ Fuse.parseQuery = parse;}
{ register(ExtendedSearch);}
export default Fuse;
fuse
Version Info
3 years ago
