interal(query): move to Searchable module

from https://github.com/caelestia-dots/shell

license is GPL, this project don't have a license yet, will use GPL

2 files changed, 2012 insertions, 0 deletions

diff --git a/utils/fuzzysort.js b/utils/fuzzysort.js
new file mode 100644
index 0000000..94308ff
--- /dev/null
+++ b/utils/fuzzysort.js
@@ -0,0 +1,705 @@
+.pragma library
+
+/*
+https://github.com/farzher/fuzzysort
+
+MIT License
+
+Copyright (c) 2018 Stephen Kamenar
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in all
+copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+SOFTWARE.
+*/
+
+var single =  (search, target) => {
+    if(!search || !target) return NULL
+
+    var preparedSearch = getPreparedSearch(search)
+    if(!isPrepared(target)) target = getPrepared(target)
+
+    var searchBitflags = preparedSearch.bitflags
+    if((searchBitflags & target._bitflags) !== searchBitflags) return NULL
+
+    return algorithm(preparedSearch, target)
+}
+
+var go = (search, targets, options) => {
+    if(!search) return options?.all ? all(targets, options) : noResults
+
+    var preparedSearch = getPreparedSearch(search)
+    var searchBitflags = preparedSearch.bitflags
+    var containsSpace  = preparedSearch.containsSpace
+
+    var threshold = denormalizeScore( options?.threshold || 0 )
+    var limit     = options?.limit || INFINITY
+
+    var resultsLen = 0; var limitedCount = 0
+    var targetsLen = targets.length
+
+    function push_result(result) {
+    if(resultsLen < limit) { q.add(result); ++resultsLen }
+    else {
+        ++limitedCount
+        if(result._score > q.peek()._score) q.replaceTop(result)
+    }
+    }
+
+    // This code is copy/pasted 3 times for performance reasons [options.key, options.keys, no keys]
+
+    // options.key
+    if(options?.key) {
+    var key = options.key
+    for(var i = 0; i < targetsLen; ++i) { var obj = targets[i]
+        var target = getValue(obj, key)
+        if(!target) continue
+        if(!isPrepared(target)) target = getPrepared(target)
+
+        if((searchBitflags & target._bitflags) !== searchBitflags) continue
+        var result = algorithm(preparedSearch, target)
+        if(result === NULL) continue
+        if(result._score < threshold) continue
+
+        result.obj = obj
+        push_result(result)
+    }
+
+    // options.keys
+    } else if(options?.keys) {
+    var keys = options.keys
+    var keysLen = keys.length
+
+    outer: for(var i = 0; i < targetsLen; ++i) { var obj = targets[i]
+
+        { // early out based on bitflags
+        var keysBitflags = 0
+        for (var keyI = 0; keyI < keysLen; ++keyI) {
+            var key = keys[keyI]
+            var target = getValue(obj, key)
+            if(!target) { tmpTargets[keyI] = noTarget; continue }
+            if(!isPrepared(target)) target = getPrepared(target)
+            tmpTargets[keyI] = target
+
+            keysBitflags |= target._bitflags
+        }
+
+        if((searchBitflags & keysBitflags) !== searchBitflags) continue
+        }
+
+        if(containsSpace) for(let i=0; i<preparedSearch.spaceSearches.length; i++) keysSpacesBestScores[i] = NEGATIVE_INFINITY
+
+        for (var keyI = 0; keyI < keysLen; ++keyI) {
+        target = tmpTargets[keyI]
+        if(target === noTarget) { tmpResults[keyI] = noTarget; continue }
+
+        tmpResults[keyI] = algorithm(preparedSearch, target, /*allowSpaces=*/false, /*allowPartialMatch=*/containsSpace)
+        if(tmpResults[keyI] === NULL) { tmpResults[keyI] = noTarget; continue }
+
+        // todo: this seems weird and wrong. like what if our first match wasn't good. this should just replace it instead of averaging with it
+        // if our second match isn't good we ignore it instead of averaging with it
+        if(containsSpace) for(let i=0; i<preparedSearch.spaceSearches.length; i++) {
+            if(allowPartialMatchScores[i] > -1000) {
+            if(keysSpacesBestScores[i] > NEGATIVE_INFINITY) {
+                var tmp = (keysSpacesBestScores[i] + allowPartialMatchScores[i]) / 4/*bonus score for having multiple matches*/
+                if(tmp > keysSpacesBestScores[i]) keysSpacesBestScores[i] = tmp
+            }
+            }
+            if(allowPartialMatchScores[i] > keysSpacesBestScores[i]) keysSpacesBestScores[i] = allowPartialMatchScores[i]
+        }
+        }
+
+        if(containsSpace) {
+        for(let i=0; i<preparedSearch.spaceSearches.length; i++) { if(keysSpacesBestScores[i] === NEGATIVE_INFINITY) continue outer }
+        } else {
+        var hasAtLeast1Match = false
+        for(let i=0; i < keysLen; i++) { if(tmpResults[i]._score !== NEGATIVE_INFINITY) { hasAtLeast1Match = true; break } }
+        if(!hasAtLeast1Match) continue
+        }
+
+        var objResults = new KeysResult(keysLen)
+        for(let i=0; i < keysLen; i++) { objResults[i] = tmpResults[i] }
+
+        if(containsSpace) {
+        var score = 0
+        for(let i=0; i<preparedSearch.spaceSearches.length; i++) score += keysSpacesBestScores[i]
+        } else {
+        // todo could rewrite this scoring to be more similar to when there's spaces
+        // if we match multiple keys give us bonus points
+        var score = NEGATIVE_INFINITY
+        for(let i=0; i<keysLen; i++) {
+            var result = objResults[i]
+            if(result._score > -1000) {
+            if(score > NEGATIVE_INFINITY) {
+                var tmp = (score + result._score) / 4/*bonus score for having multiple matches*/
+                if(tmp > score) score = tmp
+            }
+            }
+            if(result._score > score) score = result._score
+        }
+        }
+
+        objResults.obj = obj
+        objResults._score = score
+        if(options?.scoreFn) {
+        score = options.scoreFn(objResults)
+        if(!score) continue
+        score = denormalizeScore(score)
+        objResults._score = score
+        }
+
+        if(score < threshold) continue
+        push_result(objResults)
+    }
+
+    // no keys
+    } else {
+    for(var i = 0; i < targetsLen; ++i) { var target = targets[i]
+        if(!target) continue
+        if(!isPrepared(target)) target = getPrepared(target)
+
+        if((searchBitflags & target._bitflags) !== searchBitflags) continue
+        var result = algorithm(preparedSearch, target)
+        if(result === NULL) continue
+        if(result._score < threshold) continue
+
+        push_result(result)
+    }
+    }
+
+    if(resultsLen === 0) return noResults
+    var results = new Array(resultsLen)
+    for(var i = resultsLen - 1; i >= 0; --i) results[i] = q.poll()
+    results.total = resultsLen + limitedCount
+    return results
+}
+
+
+// this is written as 1 function instead of 2 for minification. perf seems fine ...
+// except when minified. the perf is very slow
+var highlight = (result, open='<b>', close='</b>') => {
+    var callback = typeof open === 'function' ? open : undefined
+
+    var target      = result.target
+    var targetLen   = target.length
+    var indexes     = result.indexes
+    var highlighted = ''
+    var matchI      = 0
+    var indexesI    = 0
+    var opened      = false
+    var parts       = []
+
+    for(var i = 0; i < targetLen; ++i) { var char = target[i]
+    if(indexes[indexesI] === i) {
+        ++indexesI
+        if(!opened) { opened = true
+        if(callback) {
+            parts.push(highlighted); highlighted = ''
+        } else {
+            highlighted += open
+        }
+        }
+
+        if(indexesI === indexes.length) {
+        if(callback) {
+            highlighted += char
+            parts.push(callback(highlighted, matchI++)); highlighted = ''
+            parts.push(target.substr(i+1))
+        } else {
+            highlighted += char + close + target.substr(i+1)
+        }
+        break
+        }
+    } else {
+        if(opened) { opened = false
+        if(callback) {
+            parts.push(callback(highlighted, matchI++)); highlighted = ''
+        } else {
+            highlighted += close
+        }
+        }
+    }
+    highlighted += char
+    }
+
+    return callback ? parts : highlighted
+}
+
+
+var prepare = (target) => {
+    if(typeof target === 'number') target = ''+target
+    else if(typeof target !== 'string') target = ''
+    var info = prepareLowerInfo(target)
+    return new_result(target, {_targetLower:info._lower, _targetLowerCodes:info.lowerCodes, _bitflags:info.bitflags})
+}
+
+var cleanup = () => { preparedCache.clear(); preparedSearchCache.clear() }
+
+
+// Below this point is only internal code
+// Below this point is only internal code
+// Below this point is only internal code
+// Below this point is only internal code
+
+
+class Result {
+    get ['indexes']() { return this._indexes.slice(0, this._indexes.len).sort((a,b)=>a-b) }
+    set ['indexes'](indexes) { return this._indexes = indexes }
+    ['highlight'](open, close) { return highlight(this, open, close) }
+    get ['score']() { return normalizeScore(this._score) }
+    set ['score'](score) { this._score = denormalizeScore(score) }
+}
+
+class KeysResult extends Array {
+    get ['score']() { return normalizeScore(this._score) }
+    set ['score'](score) { this._score = denormalizeScore(score) }
+}
+
+var new_result = (target, options) => {
+    const result = new Result()
+    result['target']             = target
+    result['obj']                = options.obj                   ?? NULL
+    result._score                = options._score                ?? NEGATIVE_INFINITY
+    result._indexes              = options._indexes              ?? []
+    result._targetLower          = options._targetLower          ?? ''
+    result._targetLowerCodes     = options._targetLowerCodes     ?? NULL
+    result._nextBeginningIndexes = options._nextBeginningIndexes ?? NULL
+    result._bitflags             = options._bitflags             ?? 0
+    return result
+}
+
+
+var normalizeScore = score => {
+    if(score === NEGATIVE_INFINITY) return 0
+    if(score > 1) return score
+    return Math.E ** ( ((-score + 1)**.04307 - 1) * -2)
+}
+var denormalizeScore = normalizedScore => {
+    if(normalizedScore === 0) return NEGATIVE_INFINITY
+    if(normalizedScore > 1) return normalizedScore
+    return 1 - Math.pow((Math.log(normalizedScore) / -2 + 1), 1 / 0.04307)
+}
+
+
+var prepareSearch = (search) => {
+    if(typeof search === 'number') search = ''+search
+    else if(typeof search !== 'string') search = ''
+    search = search.trim()
+    var info = prepareLowerInfo(search)
+
+    var spaceSearches = []
+    if(info.containsSpace) {
+    var searches = search.split(/\s+/)
+    searches = [...new Set(searches)] // distinct
+    for(var i=0; i<searches.length; i++) {
+        if(searches[i] === '') continue
+        var _info = prepareLowerInfo(searches[i])
+        spaceSearches.push({lowerCodes:_info.lowerCodes, _lower:searches[i].toLowerCase(), containsSpace:false})
+    }
+    }
+
+    return {lowerCodes: info.lowerCodes, _lower: info._lower, containsSpace: info.containsSpace, bitflags: info.bitflags, spaceSearches: spaceSearches}
+}
+
+
+
+var getPrepared = (target) => {
+    if(target.length > 999) return prepare(target) // don't cache huge targets
+    var targetPrepared = preparedCache.get(target)
+    if(targetPrepared !== undefined) return targetPrepared
+    targetPrepared = prepare(target)
+    preparedCache.set(target, targetPrepared)
+    return targetPrepared
+}
+var getPreparedSearch = (search) => {
+    if(search.length > 999) return prepareSearch(search) // don't cache huge searches
+    var searchPrepared = preparedSearchCache.get(search)
+    if(searchPrepared !== undefined) return searchPrepared
+    searchPrepared = prepareSearch(search)
+    preparedSearchCache.set(search, searchPrepared)
+    return searchPrepared
+}
+
+
+var all = (targets, options) => {
+    var results = []; results.total = targets.length // this total can be wrong if some targets are skipped
+
+    var limit = options?.limit || INFINITY
+
+    if(options?.key) {
+    for(var i=0;i<targets.length;i++) { var obj = targets[i]
+        var target = getValue(obj, options.key)
+        if(target == NULL) continue
+        if(!isPrepared(target)) target = getPrepared(target)
+        var result = new_result(target.target, {_score: target._score, obj: obj})
+        results.push(result); if(results.length >= limit) return results
+    }
+    } else if(options?.keys) {
+    for(var i=0;i<targets.length;i++) { var obj = targets[i]
+        var objResults = new KeysResult(options.keys.length)
+        for (var keyI = options.keys.length - 1; keyI >= 0; --keyI) {
+        var target = getValue(obj, options.keys[keyI])
+        if(!target) { objResults[keyI] = noTarget; continue }
+        if(!isPrepared(target)) target = getPrepared(target)
+        target._score = NEGATIVE_INFINITY
+        target._indexes.len = 0
+        objResults[keyI] = target
+        }
+        objResults.obj = obj
+        objResults._score = NEGATIVE_INFINITY
+        results.push(objResults); if(results.length >= limit) return results
+    }
+    } else {
+    for(var i=0;i<targets.length;i++) { var target = targets[i]
+        if(target == NULL) continue
+        if(!isPrepared(target)) target = getPrepared(target)
+        target._score = NEGATIVE_INFINITY
+        target._indexes.len = 0
+        results.push(target); if(results.length >= limit) return results
+    }
+    }
+
+    return results
+}
+
+
+var algorithm = (preparedSearch, prepared, allowSpaces=false, allowPartialMatch=false) => {
+    if(allowSpaces===false && preparedSearch.containsSpace) return algorithmSpaces(preparedSearch, prepared, allowPartialMatch)
+
+    var searchLower      = preparedSearch._lower
+    var searchLowerCodes = preparedSearch.lowerCodes
+    var searchLowerCode  = searchLowerCodes[0]
+    var targetLowerCodes = prepared._targetLowerCodes
+    var searchLen        = searchLowerCodes.length
+    var targetLen        = targetLowerCodes.length
+    var searchI          = 0 // where we at
+    var targetI          = 0 // where you at
+    var matchesSimpleLen = 0
+
+    // very basic fuzzy match; to remove non-matching targets ASAP!
+    // walk through target. find sequential matches.
+    // if all chars aren't found then exit
+    for(;;) {
+    var isMatch = searchLowerCode === targetLowerCodes[targetI]
+    if(isMatch) {
+        matchesSimple[matchesSimpleLen++] = targetI
+        ++searchI; if(searchI === searchLen) break
+        searchLowerCode = searchLowerCodes[searchI]
+    }
+    ++targetI; if(targetI >= targetLen) return NULL // Failed to find searchI
+    }
+
+    var searchI = 0
+    var successStrict = false
+    var matchesStrictLen = 0
+
+    var nextBeginningIndexes = prepared._nextBeginningIndexes
+    if(nextBeginningIndexes === NULL) nextBeginningIndexes = prepared._nextBeginningIndexes = prepareNextBeginningIndexes(prepared.target)
+    targetI = matchesSimple[0]===0 ? 0 : nextBeginningIndexes[matchesSimple[0]-1]
+
+    // Our target string successfully matched all characters in sequence!
+    // Let's try a more advanced and strict test to improve the score
+    // only count it as a match if it's consecutive or a beginning character!
+    var backtrackCount = 0
+    if(targetI !== targetLen) for(;;) {
+    if(targetI >= targetLen) {
+        // We failed to find a good spot for this search char, go back to the previous search char and force it forward
+        if(searchI <= 0) break // We failed to push chars forward for a better match
+
+        ++backtrackCount; if(backtrackCount > 200) break // exponential backtracking is taking too long, just give up and return a bad match
+
+        --searchI
+        var lastMatch = matchesStrict[--matchesStrictLen]
+        targetI = nextBeginningIndexes[lastMatch]
+
+    } else {
+        var isMatch = searchLowerCodes[searchI] === targetLowerCodes[targetI]
+        if(isMatch) {
+        matchesStrict[matchesStrictLen++] = targetI
+        ++searchI; if(searchI === searchLen) { successStrict = true; break }
+        ++targetI
+        } else {
+        targetI = nextBeginningIndexes[targetI]
+        }
+    }
+    }
+
+    // check if it's a substring match
+    var substringIndex = searchLen <= 1 ? -1 : prepared._targetLower.indexOf(searchLower, matchesSimple[0]) // perf: this is slow
+    var isSubstring = !!~substringIndex
+    var isSubstringBeginning = !isSubstring ? false : substringIndex===0 || prepared._nextBeginningIndexes[substringIndex-1] === substringIndex
+
+    // if it's a substring match but not at a beginning index, let's try to find a substring starting at a beginning index for a better score
+    if(isSubstring && !isSubstringBeginning) {
+    for(var i=0; i<nextBeginningIndexes.length; i=nextBeginningIndexes[i]) {
+        if(i <= substringIndex) continue
+
+        for(var s=0; s<searchLen; s++) if(searchLowerCodes[s] !== prepared._targetLowerCodes[i+s]) break
+        if(s === searchLen) { substringIndex = i; isSubstringBeginning = true; break }
+    }
+    }
+
+    // tally up the score & keep track of matches for highlighting later
+    // if it's a simple match, we'll switch to a substring match if a substring exists
+    // if it's a strict match, we'll switch to a substring match only if that's a better score
+
+    var calculateScore = matches => {
+    var score = 0
+
+    var extraMatchGroupCount = 0
+    for(var i = 1; i < searchLen; ++i) {
+        if(matches[i] - matches[i-1] !== 1) {score -= matches[i]; ++extraMatchGroupCount}
+    }
+    var unmatchedDistance = matches[searchLen-1] - matches[0] - (searchLen-1)
+
+    score -= (12+unmatchedDistance) * extraMatchGroupCount // penality for more groups
+
+    if(matches[0] !== 0) score -= matches[0]*matches[0]*.2 // penality for not starting near the beginning
+
+    if(!successStrict) {
+        score *= 1000
+    } else {
+        // successStrict on a target with too many beginning indexes loses points for being a bad target
+        var uniqueBeginningIndexes = 1
+        for(var i = nextBeginningIndexes[0]; i < targetLen; i=nextBeginningIndexes[i]) ++uniqueBeginningIndexes
+
+        if(uniqueBeginningIndexes > 24) score *= (uniqueBeginningIndexes-24)*10 // quite arbitrary numbers here ...
+    }
+
+    score -= (targetLen - searchLen)/2 // penality for longer targets
+
+    if(isSubstring)          score /= 1+searchLen*searchLen*1 // bonus for being a full substring
+    if(isSubstringBeginning) score /= 1+searchLen*searchLen*1 // bonus for substring starting on a beginningIndex
+
+    score -= (targetLen - searchLen)/2 // penality for longer targets
+
+    return score
+    }
+
+    if(!successStrict) {
+    if(isSubstring) for(var i=0; i<searchLen; ++i) matchesSimple[i] = substringIndex+i // at this point it's safe to overwrite matchehsSimple with substr matches
+    var matchesBest = matchesSimple
+    var score = calculateScore(matchesBest)
+    } else {
+    if(isSubstringBeginning) {
+        for(var i=0; i<searchLen; ++i) matchesSimple[i] = substringIndex+i // at this point it's safe to overwrite matchehsSimple with substr matches
+        var matchesBest = matchesSimple
+        var score = calculateScore(matchesSimple)
+    } else {
+        var matchesBest = matchesStrict
+        var score = calculateScore(matchesStrict)
+    }
+    }
+
+    prepared._score = score
+
+    for(var i = 0; i < searchLen; ++i) prepared._indexes[i] = matchesBest[i]
+    prepared._indexes.len = searchLen
+
+    const result    = new Result()
+    result.target   = prepared.target
+    result._score   = prepared._score
+    result._indexes = prepared._indexes
+    return result
+}
+var algorithmSpaces = (preparedSearch, target, allowPartialMatch) => {
+    var seen_indexes = new Set()
+    var score = 0
+    var result = NULL
+
+    var first_seen_index_last_search = 0
+    var searches = preparedSearch.spaceSearches
+    var searchesLen = searches.length
+    var changeslen = 0
+
+    // Return _nextBeginningIndexes back to its normal state
+    var resetNextBeginningIndexes = () => {
+    for(let i=changeslen-1; i>=0; i--) target._nextBeginningIndexes[nextBeginningIndexesChanges[i*2 + 0]] = nextBeginningIndexesChanges[i*2 + 1]
+    }
+
+    var hasAtLeast1Match = false
+    for(var i=0; i<searchesLen; ++i) {
+    allowPartialMatchScores[i] = NEGATIVE_INFINITY
+    var search = searches[i]
+
+    result = algorithm(search, target)
+    if(allowPartialMatch) {
+        if(result === NULL) continue
+        hasAtLeast1Match = true
+    } else {
+        if(result === NULL) {resetNextBeginningIndexes(); return NULL}
+    }
+
+    // if not the last search, we need to mutate _nextBeginningIndexes for the next search
+    var isTheLastSearch = i === searchesLen - 1
+    if(!isTheLastSearch) {
+        var indexes = result._indexes
+
+        var indexesIsConsecutiveSubstring = true
+        for(let i=0; i<indexes.len-1; i++) {
+        if(indexes[i+1] - indexes[i] !== 1) {
+            indexesIsConsecutiveSubstring = false; break;
+        }
+        }
+
+        if(indexesIsConsecutiveSubstring) {
+        var newBeginningIndex = indexes[indexes.len-1] + 1
+        var toReplace = target._nextBeginningIndexes[newBeginningIndex-1]
+        for(let i=newBeginningIndex-1; i>=0; i--) {
+            if(toReplace !== target._nextBeginningIndexes[i]) break
+            target._nextBeginningIndexes[i] = newBeginningIndex
+            nextBeginningIndexesChanges[changeslen*2 + 0] = i
+            nextBeginningIndexesChanges[changeslen*2 + 1] = toReplace
+            changeslen++
+        }
+        }
+    }
+
+    score += result._score / searchesLen
+    allowPartialMatchScores[i] = result._score / searchesLen
+
+    // dock points based on order otherwise "c man" returns Manifest.cpp instead of CheatManager.h
+    if(result._indexes[0] < first_seen_index_last_search) {
+        score -= (first_seen_index_last_search - result._indexes[0]) * 2
+    }
+    first_seen_index_last_search = result._indexes[0]
+
+    for(var j=0; j<result._indexes.len; ++j) seen_indexes.add(result._indexes[j])
+    }
+
+    if(allowPartialMatch && !hasAtLeast1Match) return NULL
+
+    resetNextBeginningIndexes()
+
+    // allows a search with spaces that's an exact substring to score well
+    var allowSpacesResult = algorithm(preparedSearch, target, /*allowSpaces=*/true)
+    if(allowSpacesResult !== NULL && allowSpacesResult._score > score) {
+    if(allowPartialMatch) {
+        for(var i=0; i<searchesLen; ++i) {
+        allowPartialMatchScores[i] = allowSpacesResult._score / searchesLen
+        }
+    }
+    return allowSpacesResult
+    }
+
+    if(allowPartialMatch) result = target
+    result._score = score
+
+    var i = 0
+    for (let index of seen_indexes) result._indexes[i++] = index
+    result._indexes.len = i
+
+    return result
+}
+
+// we use this instead of just .normalize('NFD').replace(/[\u0300-\u036f]/g, '') because that screws with japanese characters
+var remove_accents = (str) => str.replace(/\p{Script=Latin}+/gu, match => match.normalize('NFD')).replace(/[\u0300-\u036f]/g, '')
+
+var prepareLowerInfo = (str) => {
+    str = remove_accents(str)
+    var strLen = str.length
+    var lower = str.toLowerCase()
+    var lowerCodes = [] // new Array(strLen)    sparse array is too slow
+    var bitflags = 0
+    var containsSpace = false // space isn't stored in bitflags because of how searching with a space works
+
+    for(var i = 0; i < strLen; ++i) {
+    var lowerCode = lowerCodes[i] = lower.charCodeAt(i)
+
+    if(lowerCode === 32) {
+        containsSpace = true
+        continue // it's important that we don't set any bitflags for space
+    }
+
+    var bit = lowerCode>=97&&lowerCode<=122 ? lowerCode-97 // alphabet
+            : lowerCode>=48&&lowerCode<=57  ? 26           // numbers
+                                                            // 3 bits available
+            : lowerCode<=127                ? 30           // other ascii
+            :                                 31           // other utf8
+    bitflags |= 1<<bit
+    }
+
+    return {lowerCodes:lowerCodes, bitflags:bitflags, containsSpace:containsSpace, _lower:lower}
+}
+var prepareBeginningIndexes = (target) => {
+    var targetLen = target.length
+    var beginningIndexes = []; var beginningIndexesLen = 0
+    var wasUpper = false
+    var wasAlphanum = false
+    for(var i = 0; i < targetLen; ++i) {
+    var targetCode = target.charCodeAt(i)
+    var isUpper = targetCode>=65&&targetCode<=90
+    var isAlphanum = isUpper || targetCode>=97&&targetCode<=122 || targetCode>=48&&targetCode<=57
+    var isBeginning = isUpper && !wasUpper || !wasAlphanum || !isAlphanum
+    wasUpper = isUpper
+    wasAlphanum = isAlphanum
+    if(isBeginning) beginningIndexes[beginningIndexesLen++] = i
+    }
+    return beginningIndexes
+}
+var prepareNextBeginningIndexes = (target) => {
+    target = remove_accents(target)
+    var targetLen = target.length
+    var beginningIndexes = prepareBeginningIndexes(target)
+    var nextBeginningIndexes = [] // new Array(targetLen)     sparse array is too slow
+    var lastIsBeginning = beginningIndexes[0]
+    var lastIsBeginningI = 0
+    for(var i = 0; i < targetLen; ++i) {
+    if(lastIsBeginning > i) {
+        nextBeginningIndexes[i] = lastIsBeginning
+    } else {
+        lastIsBeginning = beginningIndexes[++lastIsBeginningI]
+        nextBeginningIndexes[i] = lastIsBeginning===undefined ? targetLen : lastIsBeginning
+    }
+    }
+    return nextBeginningIndexes
+}
+
+var preparedCache       = new Map()
+var preparedSearchCache = new Map()
+
+// the theory behind these being globals is to reduce garbage collection by not making new arrays
+var matchesSimple = []; var matchesStrict = []
+var nextBeginningIndexesChanges = [] // allows straw berry to match strawberry well, by modifying the end of a substring to be considered a beginning index for the rest of the search
+var keysSpacesBestScores = []; var allowPartialMatchScores = []
+var tmpTargets = []; var tmpResults = []
+
+// prop = 'key'                  2.5ms optimized for this case, seems to be about as fast as direct obj[prop]
+// prop = 'key1.key2'            10ms
+// prop = ['key1', 'key2']       27ms
+// prop = obj => obj.tags.join() ??ms
+var getValue = (obj, prop) => {
+    var tmp = obj[prop]; if(tmp !== undefined) return tmp
+    if(typeof prop === 'function') return prop(obj) // this should run first. but that makes string props slower
+    var segs = prop
+    if(!Array.isArray(prop)) segs = prop.split('.')
+    var len = segs.length
+    var i = -1
+    while (obj && (++i < len)) obj = obj[segs[i]]
+    return obj
+}
+
+var isPrepared = (x) => { return typeof x === 'object' && typeof x._bitflags === 'number' }
+var INFINITY = Infinity; var NEGATIVE_INFINITY = -INFINITY
+var noResults = []; noResults.total = 0
+var NULL = null
+
+var noTarget = prepare('')
+
+// Hacked version of https://github.com/lemire/FastPriorityQueue.js
+var fastpriorityqueue=r=>{var e=[],o=0,a={},v=r=>{for(var a=0,v=e[a],c=1;c<o;){var s=c+1;a=c,s<o&&e[s]._score<e[c]._score&&(a=s),e[a-1>>1]=e[a],c=1+(a<<1)}for(var f=a-1>>1;a>0&&v._score<e[f]._score;f=(a=f)-1>>1)e[a]=e[f];e[a]=v};return a.add=(r=>{var a=o;e[o++]=r;for(var v=a-1>>1;a>0&&r._score<e[v]._score;v=(a=v)-1>>1)e[a]=e[v];e[a]=r}),a.poll=(r=>{if(0!==o){var a=e[0];return e[0]=e[--o],v(),a}}),a.peek=(r=>{if(0!==o)return e[0]}),a.replaceTop=(r=>{e[0]=r,v()}),a}
+var q = fastpriorityqueue() // reuse this
+
diff --git a/utils/fzf.js b/utils/fzf.js
new file mode 100644
index 0000000..995a093
--- /dev/null
+++ b/utils/fzf.js
@@ -0,0 +1,1307 @@
+.pragma library
+
+/*
+https://github.com/ajitid/fzf-for-js
+
+BSD 3-Clause License
+
+Copyright (c) 2021, Ajit
+All rights reserved.
+
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions are met:
+
+1. Redistributions of source code must retain the above copyright notice, this
+   list of conditions and the following disclaimer.
+
+2. Redistributions in binary form must reproduce the above copyright notice,
+   this list of conditions and the following disclaimer in the documentation
+   and/or other materials provided with the distribution.
+
+3. Neither the name of the copyright holder nor the names of its
+   contributors may be used to endorse or promote products derived from
+   this software without specific prior written permission.
+
+THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+*/
+
+const normalized = {
+  216: "O",
+  223: "s",
+  248: "o",
+  273: "d",
+  295: "h",
+  305: "i",
+  320: "l",
+  322: "l",
+  359: "t",
+  383: "s",
+  384: "b",
+  385: "B",
+  387: "b",
+  390: "O",
+  392: "c",
+  393: "D",
+  394: "D",
+  396: "d",
+  398: "E",
+  400: "E",
+  402: "f",
+  403: "G",
+  407: "I",
+  409: "k",
+  410: "l",
+  412: "M",
+  413: "N",
+  414: "n",
+  415: "O",
+  421: "p",
+  427: "t",
+  429: "t",
+  430: "T",
+  434: "V",
+  436: "y",
+  438: "z",
+  477: "e",
+  485: "g",
+  544: "N",
+  545: "d",
+  549: "z",
+  564: "l",
+  565: "n",
+  566: "t",
+  567: "j",
+  570: "A",
+  571: "C",
+  572: "c",
+  573: "L",
+  574: "T",
+  575: "s",
+  576: "z",
+  579: "B",
+  580: "U",
+  581: "V",
+  582: "E",
+  583: "e",
+  584: "J",
+  585: "j",
+  586: "Q",
+  587: "q",
+  588: "R",
+  589: "r",
+  590: "Y",
+  591: "y",
+  592: "a",
+  593: "a",
+  595: "b",
+  596: "o",
+  597: "c",
+  598: "d",
+  599: "d",
+  600: "e",
+  603: "e",
+  604: "e",
+  605: "e",
+  606: "e",
+  607: "j",
+  608: "g",
+  609: "g",
+  610: "G",
+  613: "h",
+  614: "h",
+  616: "i",
+  618: "I",
+  619: "l",
+  620: "l",
+  621: "l",
+  623: "m",
+  624: "m",
+  625: "m",
+  626: "n",
+  627: "n",
+  628: "N",
+  629: "o",
+  633: "r",
+  634: "r",
+  635: "r",
+  636: "r",
+  637: "r",
+  638: "r",
+  639: "r",
+  640: "R",
+  641: "R",
+  642: "s",
+  647: "t",
+  648: "t",
+  649: "u",
+  651: "v",
+  652: "v",
+  653: "w",
+  654: "y",
+  655: "Y",
+  656: "z",
+  657: "z",
+  663: "c",
+  665: "B",
+  666: "e",
+  667: "G",
+  668: "H",
+  669: "j",
+  670: "k",
+  671: "L",
+  672: "q",
+  686: "h",
+  867: "a",
+  868: "e",
+  869: "i",
+  870: "o",
+  871: "u",
+  872: "c",
+  873: "d",
+  874: "h",
+  875: "m",
+  876: "r",
+  877: "t",
+  878: "v",
+  879: "x",
+  7424: "A",
+  7427: "B",
+  7428: "C",
+  7429: "D",
+  7431: "E",
+  7432: "e",
+  7433: "i",
+  7434: "J",
+  7435: "K",
+  7436: "L",
+  7437: "M",
+  7438: "N",
+  7439: "O",
+  7440: "O",
+  7441: "o",
+  7442: "o",
+  7443: "o",
+  7446: "o",
+  7447: "o",
+  7448: "P",
+  7449: "R",
+  7450: "R",
+  7451: "T",
+  7452: "U",
+  7453: "u",
+  7454: "u",
+  7455: "m",
+  7456: "V",
+  7457: "W",
+  7458: "Z",
+  7522: "i",
+  7523: "r",
+  7524: "u",
+  7525: "v",
+  7834: "a",
+  7835: "s",
+  8305: "i",
+  8341: "h",
+  8342: "k",
+  8343: "l",
+  8344: "m",
+  8345: "n",
+  8346: "p",
+  8347: "s",
+  8348: "t",
+  8580: "c"
+};
+for (let i = "\u0300".codePointAt(0); i <= "\u036F".codePointAt(0); ++i) {
+  const diacritic = String.fromCodePoint(i);
+  for (const asciiChar of "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz") {
+    const withDiacritic = (asciiChar + diacritic).normalize();
+    const withDiacriticCodePoint = withDiacritic.codePointAt(0);
+    if (withDiacriticCodePoint > 126) {
+      normalized[withDiacriticCodePoint] = asciiChar;
+    }
+  }
+}
+const ranges = {
+  a: [7844, 7863],
+  e: [7870, 7879],
+  o: [7888, 7907],
+  u: [7912, 7921]
+};
+for (const lowerChar of Object.keys(ranges)) {
+  const upperChar = lowerChar.toUpperCase();
+  for (let i = ranges[lowerChar][0]; i <= ranges[lowerChar][1]; ++i) {
+    normalized[i] = i % 2 === 0 ? upperChar : lowerChar;
+  }
+}
+function normalizeRune(rune) {
+  if (rune < 192 || rune > 8580) {
+    return rune;
+  }
+  const normalizedChar = normalized[rune];
+  if (normalizedChar !== void 0)
+    return normalizedChar.codePointAt(0);
+  return rune;
+}
+function toShort(number) {
+  return number;
+}
+function toInt(number) {
+  return number;
+}
+function maxInt16(num1, num2) {
+  return num1 > num2 ? num1 : num2;
+}
+const strToRunes = (str) => str.split("").map((s) => s.codePointAt(0));
+const runesToStr = (runes) => runes.map((r) => String.fromCodePoint(r)).join("");
+const whitespaceRunes = new Set(
+  " \f\n\r	\v\xA0\u1680\u2028\u2029\u202F\u205F\u3000\uFEFF".split("").map((v) => v.codePointAt(0))
+);
+for (let codePoint = "\u2000".codePointAt(0); codePoint <= "\u200A".codePointAt(0); codePoint++) {
+  whitespaceRunes.add(codePoint);
+}
+const isWhitespace = (rune) => whitespaceRunes.has(rune);
+const whitespacesAtStart = (runes) => {
+  let whitespaces = 0;
+  for (const rune of runes) {
+    if (isWhitespace(rune))
+      whitespaces++;
+    else
+      break;
+  }
+  return whitespaces;
+};
+const whitespacesAtEnd = (runes) => {
+  let whitespaces = 0;
+  for (let i = runes.length - 1; i >= 0; i--) {
+    if (isWhitespace(runes[i]))
+      whitespaces++;
+    else
+      break;
+  }
+  return whitespaces;
+};
+const MAX_ASCII = "\x7F".codePointAt(0);
+const CAPITAL_A_RUNE = "A".codePointAt(0);
+const CAPITAL_Z_RUNE = "Z".codePointAt(0);
+const SMALL_A_RUNE = "a".codePointAt(0);
+const SMALL_Z_RUNE = "z".codePointAt(0);
+const NUMERAL_ZERO_RUNE = "0".codePointAt(0);
+const NUMERAL_NINE_RUNE = "9".codePointAt(0);
+function indexAt(index, max, forward) {
+  if (forward) {
+    return index;
+  }
+  return max - index - 1;
+}
+const SCORE_MATCH = 16, SCORE_GAP_START = -3, SCORE_GAP_EXTENTION = -1, BONUS_BOUNDARY = SCORE_MATCH / 2, BONUS_NON_WORD = SCORE_MATCH / 2, BONUS_CAMEL_123 = BONUS_BOUNDARY + SCORE_GAP_EXTENTION, BONUS_CONSECUTIVE = -(SCORE_GAP_START + SCORE_GAP_EXTENTION), BONUS_FIRST_CHAR_MULTIPLIER = 2;
+function createPosSet(withPos) {
+  if (withPos) {
+    return /* @__PURE__ */ new Set();
+  }
+  return null;
+}
+function alloc16(offset, slab2, size) {
+  if (slab2 !== null && slab2.i16.length > offset + size) {
+    const subarray = slab2.i16.subarray(offset, offset + size);
+    return [offset + size, subarray];
+  }
+  return [offset, new Int16Array(size)];
+}
+function alloc32(offset, slab2, size) {
+  if (slab2 !== null && slab2.i32.length > offset + size) {
+    const subarray = slab2.i32.subarray(offset, offset + size);
+    return [offset + size, subarray];
+  }
+  return [offset, new Int32Array(size)];
+}
+function charClassOfAscii(rune) {
+  if (rune >= SMALL_A_RUNE && rune <= SMALL_Z_RUNE) {
+    return 1;
+  } else if (rune >= CAPITAL_A_RUNE && rune <= CAPITAL_Z_RUNE) {
+    return 2;
+  } else if (rune >= NUMERAL_ZERO_RUNE && rune <= NUMERAL_NINE_RUNE) {
+    return 4;
+  } else {
+    return 0;
+  }
+}
+function charClassOfNonAscii(rune) {
+  const char = String.fromCodePoint(rune);
+  if (char !== char.toUpperCase()) {
+    return 1;
+  } else if (char !== char.toLowerCase()) {
+    return 2;
+  } else if (char.match(/\p{Number}/gu) !== null) {
+    return 4;
+  } else if (char.match(/\p{Letter}/gu) !== null) {
+    return 3;
+  }
+  return 0;
+}
+function charClassOf(rune) {
+  if (rune <= MAX_ASCII) {
+    return charClassOfAscii(rune);
+  }
+  return charClassOfNonAscii(rune);
+}
+function bonusFor(prevClass, currClass) {
+  if (prevClass === 0 && currClass !== 0) {
+    return BONUS_BOUNDARY;
+  } else if (prevClass === 1 && currClass === 2 || prevClass !== 4 && currClass === 4) {
+    return BONUS_CAMEL_123;
+  } else if (currClass === 0) {
+    return BONUS_NON_WORD;
+  }
+  return 0;
+}
+function bonusAt(input, idx) {
+  if (idx === 0) {
+    return BONUS_BOUNDARY;
+  }
+  return bonusFor(charClassOf(input[idx - 1]), charClassOf(input[idx]));
+}
+function trySkip(input, caseSensitive, char, from) {
+  let rest = input.slice(from);
+  let idx = rest.indexOf(char);
+  if (idx === 0) {
+    return from;
+  }
+  if (!caseSensitive && char >= SMALL_A_RUNE && char <= SMALL_Z_RUNE) {
+    if (idx > 0) {
+      rest = rest.slice(0, idx);
+    }
+    const uidx = rest.indexOf(char - 32);
+    if (uidx >= 0) {
+      idx = uidx;
+    }
+  }
+  if (idx < 0) {
+    return -1;
+  }
+  return from + idx;
+}
+function isAscii(runes) {
+  for (const rune of runes) {
+    if (rune >= 128) {
+      return false;
+    }
+  }
+  return true;
+}
+function asciiFuzzyIndex(input, pattern, caseSensitive) {
+  if (!isAscii(input)) {
+    return 0;
+  }
+  if (!isAscii(pattern)) {
+    return -1;
+  }
+  let firstIdx = 0, idx = 0;
+  for (let pidx = 0; pidx < pattern.length; pidx++) {
+    idx = trySkip(input, caseSensitive, pattern[pidx], idx);
+    if (idx < 0) {
+      return -1;
+    }
+    if (pidx === 0 && idx > 0) {
+      firstIdx = idx - 1;
+    }
+    idx++;
+  }
+  return firstIdx;
+}
+const fuzzyMatchV2 = (caseSensitive, normalize, forward, input, pattern, withPos, slab2) => {
+  const M = pattern.length;
+  if (M === 0) {
+    return [{ start: 0, end: 0, score: 0 }, createPosSet(withPos)];
+  }
+  const N = input.length;
+  if (slab2 !== null && N * M > slab2.i16.length) {
+    return fuzzyMatchV1(caseSensitive, normalize, forward, input, pattern, withPos);
+  }
+  const idx = asciiFuzzyIndex(input, pattern, caseSensitive);
+  if (idx < 0) {
+    return [{ start: -1, end: -1, score: 0 }, null];
+  }
+  let offset16 = 0, offset32 = 0, H0 = null, C0 = null, B = null, F = null;
+  [offset16, H0] = alloc16(offset16, slab2, N);
+  [offset16, C0] = alloc16(offset16, slab2, N);
+  [offset16, B] = alloc16(offset16, slab2, N);
+  [offset32, F] = alloc32(offset32, slab2, M);
+  const [, T] = alloc32(offset32, slab2, N);
+  for (let i = 0; i < T.length; i++) {
+    T[i] = input[i];
+  }
+  let maxScore = toShort(0), maxScorePos = 0;
+  let pidx = 0, lastIdx = 0;
+  const pchar0 = pattern[0];
+  let pchar = pattern[0], prevH0 = toShort(0), prevCharClass = 0, inGap = false;
+  let Tsub = T.subarray(idx);
+  let H0sub = H0.subarray(idx).subarray(0, Tsub.length), C0sub = C0.subarray(idx).subarray(0, Tsub.length), Bsub = B.subarray(idx).subarray(0, Tsub.length);
+  for (let [off, char] of Tsub.entries()) {
+    let charClass = null;
+    if (char <= MAX_ASCII) {
+      charClass = charClassOfAscii(char);
+      if (!caseSensitive && charClass === 2) {
+        char += 32;
+      }
+    } else {
+      charClass = charClassOfNonAscii(char);
+      if (!caseSensitive && charClass === 2) {
+        char = String.fromCodePoint(char).toLowerCase().codePointAt(0);
+      }
+      if (normalize) {
+        char = normalizeRune(char);
+      }
+    }
+    Tsub[off] = char;
+    const bonus = bonusFor(prevCharClass, charClass);
+    Bsub[off] = bonus;
+    prevCharClass = charClass;
+    if (char === pchar) {
+      if (pidx < M) {
+        F[pidx] = toInt(idx + off);
+        pidx++;
+        pchar = pattern[Math.min(pidx, M - 1)];
+      }
+      lastIdx = idx + off;
+    }
+    if (char === pchar0) {
+      const score = SCORE_MATCH + bonus * BONUS_FIRST_CHAR_MULTIPLIER;
+      H0sub[off] = score;
+      C0sub[off] = 1;
+      if (M === 1 && (forward && score > maxScore || !forward && score >= maxScore)) {
+        maxScore = score;
+        maxScorePos = idx + off;
+        if (forward && bonus === BONUS_BOUNDARY) {
+          break;
+        }
+      }
+      inGap = false;
+    } else {
+      if (inGap) {
+        H0sub[off] = maxInt16(prevH0 + SCORE_GAP_EXTENTION, 0);
+      } else {
+        H0sub[off] = maxInt16(prevH0 + SCORE_GAP_START, 0);
+      }
+      C0sub[off] = 0;
+      inGap = true;
+    }
+    prevH0 = H0sub[off];
+  }
+  if (pidx !== M) {
+    return [{ start: -1, end: -1, score: 0 }, null];
+  }
+  if (M === 1) {
+    const result = {
+      start: maxScorePos,
+      end: maxScorePos + 1,
+      score: maxScore
+    };
+    if (!withPos) {
+      return [result, null];
+    }
+    const pos2 = /* @__PURE__ */ new Set();
+    pos2.add(maxScorePos);
+    return [result, pos2];
+  }
+  const f0 = F[0];
+  const width = lastIdx - f0 + 1;
+  let H = null;
+  [offset16, H] = alloc16(offset16, slab2, width * M);
+  {
+    const toCopy = H0.subarray(f0, lastIdx + 1);
+    for (const [i, v] of toCopy.entries()) {
+      H[i] = v;
+    }
+  }
+  let [, C] = alloc16(offset16, slab2, width * M);
+  {
+    const toCopy = C0.subarray(f0, lastIdx + 1);
+    for (const [i, v] of toCopy.entries()) {
+      C[i] = v;
+    }
+  }
+  const Fsub = F.subarray(1);
+  const Psub = pattern.slice(1).slice(0, Fsub.length);
+  for (const [off, f] of Fsub.entries()) {
+    let inGap2 = false;
+    const pchar2 = Psub[off], pidx2 = off + 1, row = pidx2 * width, Tsub2 = T.subarray(f, lastIdx + 1), Bsub2 = B.subarray(f).subarray(0, Tsub2.length), Csub = C.subarray(row + f - f0).subarray(0, Tsub2.length), Cdiag = C.subarray(row + f - f0 - 1 - width).subarray(0, Tsub2.length), Hsub = H.subarray(row + f - f0).subarray(0, Tsub2.length), Hdiag = H.subarray(row + f - f0 - 1 - width).subarray(0, Tsub2.length), Hleft = H.subarray(row + f - f0 - 1).subarray(0, Tsub2.length);
+    Hleft[0] = 0;
+    for (const [off2, char] of Tsub2.entries()) {
+      const col = off2 + f;
+      let s1 = 0, s2 = 0, consecutive = 0;
+      if (inGap2) {
+        s2 = Hleft[off2] + SCORE_GAP_EXTENTION;
+      } else {
+        s2 = Hleft[off2] + SCORE_GAP_START;
+      }
+      if (pchar2 === char) {
+        s1 = Hdiag[off2] + SCORE_MATCH;
+        let b = Bsub2[off2];
+        consecutive = Cdiag[off2] + 1;
+        if (b === BONUS_BOUNDARY) {
+          consecutive = 1;
+        } else if (consecutive > 1) {
+          b = maxInt16(b, maxInt16(BONUS_CONSECUTIVE, B[col - consecutive + 1]));
+        }
+        if (s1 + b < s2) {
+          s1 += Bsub2[off2];
+          consecutive = 0;
+        } else {
+          s1 += b;
+        }
+      }
+      Csub[off2] = consecutive;
+      inGap2 = s1 < s2;
+      const score = maxInt16(maxInt16(s1, s2), 0);
+      if (pidx2 === M - 1 && (forward && score > maxScore || !forward && score >= maxScore)) {
+        maxScore = score;
+        maxScorePos = col;
+      }
+      Hsub[off2] = score;
+    }
+  }
+  const pos = createPosSet(withPos);
+  let j = f0;
+  if (withPos && pos !== null) {
+    let i = M - 1;
+    j = maxScorePos;
+    let preferMatch = true;
+    while (true) {
+      const I = i * width, j0 = j - f0, s = H[I + j0];
+      let s1 = 0, s2 = 0;
+      if (i > 0 && j >= F[i]) {
+        s1 = H[I - width + j0 - 1];
+      }
+      if (j > F[i]) {
+        s2 = H[I + j0 - 1];
+      }
+      if (s > s1 && (s > s2 || s === s2 && preferMatch)) {
+        pos.add(j);
+        if (i === 0) {
+          break;
+        }
+        i--;
+      }
+      preferMatch = C[I + j0] > 1 || I + width + j0 + 1 < C.length && C[I + width + j0 + 1] > 0;
+      j--;
+    }
+  }
+  return [{ start: j, end: maxScorePos + 1, score: maxScore }, pos];
+};
+function calculateScore(caseSensitive, normalize, text, pattern, sidx, eidx, withPos) {
+  let pidx = 0, score = 0, inGap = false, consecutive = 0, firstBonus = toShort(0);
+  const pos = createPosSet(withPos);
+  let prevCharClass = 0;
+  if (sidx > 0) {
+    prevCharClass = charClassOf(text[sidx - 1]);
+  }
+  for (let idx = sidx; idx < eidx; idx++) {
+    let rune = text[idx];
+    const charClass = charClassOf(rune);
+    if (!caseSensitive) {
+      if (rune >= CAPITAL_A_RUNE && rune <= CAPITAL_Z_RUNE) {
+        rune += 32;
+      } else if (rune > MAX_ASCII) {
+        rune = String.fromCodePoint(rune).toLowerCase().codePointAt(0);
+      }
+    }
+    if (normalize) {
+      rune = normalizeRune(rune);
+    }
+    if (rune === pattern[pidx]) {
+      if (withPos && pos !== null) {
+        pos.add(idx);
+      }
+      score += SCORE_MATCH;
+      let bonus = bonusFor(prevCharClass, charClass);
+      if (consecutive === 0) {
+        firstBonus = bonus;
+      } else {
+        if (bonus === BONUS_BOUNDARY) {
+          firstBonus = bonus;
+        }
+        bonus = maxInt16(maxInt16(bonus, firstBonus), BONUS_CONSECUTIVE);
+      }
+      if (pidx === 0) {
+        score += bonus * BONUS_FIRST_CHAR_MULTIPLIER;
+      } else {
+        score += bonus;
+      }
+      inGap = false;
+      consecutive++;
+      pidx++;
+    } else {
+      if (inGap) {
+        score += SCORE_GAP_EXTENTION;
+      } else {
+        score += SCORE_GAP_START;
+      }
+      inGap = true;
+      consecutive = 0;
+      firstBonus = 0;
+    }
+    prevCharClass = charClass;
+  }
+  return [score, pos];
+}
+function fuzzyMatchV1(caseSensitive, normalize, forward, text, pattern, withPos, slab2) {
+  if (pattern.length === 0) {
+    return [{ start: 0, end: 0, score: 0 }, null];
+  }
+  if (asciiFuzzyIndex(text, pattern, caseSensitive) < 0) {
+    return [{ start: -1, end: -1, score: 0 }, null];
+  }
+  let pidx = 0, sidx = -1, eidx = -1;
+  const lenRunes = text.length;
+  const lenPattern = pattern.length;
+  for (let index = 0; index < lenRunes; index++) {
+    let rune = text[indexAt(index, lenRunes, forward)];
+    if (!caseSensitive) {
+      if (rune >= CAPITAL_A_RUNE && rune <= CAPITAL_Z_RUNE) {
+        rune += 32;
+      } else if (rune > MAX_ASCII) {
+        rune = String.fromCodePoint(rune).toLowerCase().codePointAt(0);
+      }
+    }
+    if (normalize) {
+      rune = normalizeRune(rune);
+    }
+    const pchar = pattern[indexAt(pidx, lenPattern, forward)];
+    if (rune === pchar) {
+      if (sidx < 0) {
+        sidx = index;
+      }
+      pidx++;
+      if (pidx === lenPattern) {
+        eidx = index + 1;
+        break;
+      }
+    }
+  }
+  if (sidx >= 0 && eidx >= 0) {
+    pidx--;
+    for (let index = eidx - 1; index >= sidx; index--) {
+      const tidx = indexAt(index, lenRunes, forward);
+      let rune = text[tidx];
+      if (!caseSensitive) {
+        if (rune >= CAPITAL_A_RUNE && rune <= CAPITAL_Z_RUNE) {
+          rune += 32;
+        } else if (rune > MAX_ASCII) {
+          rune = String.fromCodePoint(rune).toLowerCase().codePointAt(0);
+        }
+      }
+      const pidx_ = indexAt(pidx, lenPattern, forward);
+      const pchar = pattern[pidx_];
+      if (rune === pchar) {
+        pidx--;
+        if (pidx < 0) {
+          sidx = index;
+          break;
+        }
+      }
+    }
+    if (!forward) {
+      const sidxTemp = sidx;
+      sidx = lenRunes - eidx;
+      eidx = lenRunes - sidxTemp;
+    }
+    const [score, pos] = calculateScore(
+      caseSensitive,
+      normalize,
+      text,
+      pattern,
+      sidx,
+      eidx,
+      withPos
+    );
+    return [{ start: sidx, end: eidx, score }, pos];
+  }
+  return [{ start: -1, end: -1, score: 0 }, null];
+};
+const exactMatchNaive = (caseSensitive, normalize, forward, text, pattern, withPos, slab2) => {
+  if (pattern.length === 0) {
+    return [{ start: 0, end: 0, score: 0 }, null];
+  }
+  const lenRunes = text.length;
+  const lenPattern = pattern.length;
+  if (lenRunes < lenPattern) {
+    return [{ start: -1, end: -1, score: 0 }, null];
+  }
+  if (asciiFuzzyIndex(text, pattern, caseSensitive) < 0) {
+    return [{ start: -1, end: -1, score: 0 }, null];
+  }
+  let pidx = 0;
+  let bestPos = -1, bonus = toShort(0), bestBonus = toShort(-1);
+  for (let index = 0; index < lenRunes; index++) {
+    const index_ = indexAt(index, lenRunes, forward);
+    let rune = text[index_];
+    if (!caseSensitive) {
+      if (rune >= CAPITAL_A_RUNE && rune <= CAPITAL_Z_RUNE) {
+        rune += 32;
+      } else if (rune > MAX_ASCII) {
+        rune = String.fromCodePoint(rune).toLowerCase().codePointAt(0);
+      }
+    }
+    if (normalize) {
+      rune = normalizeRune(rune);
+    }
+    const pidx_ = indexAt(pidx, lenPattern, forward);
+    const pchar = pattern[pidx_];
+    if (pchar === rune) {
+      if (pidx_ === 0) {
+        bonus = bonusAt(text, index_);
+      }
+      pidx++;
+      if (pidx === lenPattern) {
+        if (bonus > bestBonus) {
+          bestPos = index;
+          bestBonus = bonus;
+        }
+        if (bonus === BONUS_BOUNDARY) {
+          break;
+        }
+        index -= pidx - 1;
+        pidx = 0;
+        bonus = 0;
+      }
+    } else {
+      index -= pidx;
+      pidx = 0;
+      bonus = 0;
+    }
+  }
+  if (bestPos >= 0) {
+    let sidx = 0, eidx = 0;
+    if (forward) {
+      sidx = bestPos - lenPattern + 1;
+      eidx = bestPos + 1;
+    } else {
+      sidx = lenRunes - (bestPos + 1);
+      eidx = lenRunes - (bestPos - lenPattern + 1);
+    }
+    const [score] = calculateScore(caseSensitive, normalize, text, pattern, sidx, eidx, false);
+    return [{ start: sidx, end: eidx, score }, null];
+  }
+  return [{ start: -1, end: -1, score: 0 }, null];
+};
+const prefixMatch = (caseSensitive, normalize, forward, text, pattern, withPos, slab2) => {
+  if (pattern.length === 0) {
+    return [{ start: 0, end: 0, score: 0 }, null];
+  }
+  let trimmedLen = 0;
+  if (!isWhitespace(pattern[0])) {
+    trimmedLen = whitespacesAtStart(text);
+  }
+  if (text.length - trimmedLen < pattern.length) {
+    return [{ start: -1, end: -1, score: 0 }, null];
+  }
+  for (const [index, r] of pattern.entries()) {
+    let rune = text[trimmedLen + index];
+    if (!caseSensitive) {
+      rune = String.fromCodePoint(rune).toLowerCase().codePointAt(0);
+    }
+    if (normalize) {
+      rune = normalizeRune(rune);
+    }
+    if (rune !== r) {
+      return [{ start: -1, end: -1, score: 0 }, null];
+    }
+  }
+  const lenPattern = pattern.length;
+  const [score] = calculateScore(
+    caseSensitive,
+    normalize,
+    text,
+    pattern,
+    trimmedLen,
+    trimmedLen + lenPattern,
+    false
+  );
+  return [{ start: trimmedLen, end: trimmedLen + lenPattern, score }, null];
+};
+const suffixMatch = (caseSensitive, normalize, forward, text, pattern, withPos, slab2) => {
+  const lenRunes = text.length;
+  let trimmedLen = lenRunes;
+  if (pattern.length === 0 || !isWhitespace(pattern[pattern.length - 1])) {
+    trimmedLen -= whitespacesAtEnd(text);
+  }
+  if (pattern.length === 0) {
+    return [{ start: trimmedLen, end: trimmedLen, score: 0 }, null];
+  }
+  const diff = trimmedLen - pattern.length;
+  if (diff < 0) {
+    return [{ start: -1, end: -1, score: 0 }, null];
+  }
+  for (const [index, r] of pattern.entries()) {
+    let rune = text[index + diff];
+    if (!caseSensitive) {
+      rune = String.fromCodePoint(rune).toLowerCase().codePointAt(0);
+    }
+    if (normalize) {
+      rune = normalizeRune(rune);
+    }
+    if (rune !== r) {
+      return [{ start: -1, end: -1, score: 0 }, null];
+    }
+  }
+  const lenPattern = pattern.length;
+  const sidx = trimmedLen - lenPattern;
+  const eidx = trimmedLen;
+  const [score] = calculateScore(caseSensitive, normalize, text, pattern, sidx, eidx, false);
+  return [{ start: sidx, end: eidx, score }, null];
+};
+const equalMatch = (caseSensitive, normalize, forward, text, pattern, withPos, slab2) => {
+  const lenPattern = pattern.length;
+  if (lenPattern === 0) {
+    return [{ start: -1, end: -1, score: 0 }, null];
+  }
+  let trimmedLen = 0;
+  if (!isWhitespace(pattern[0])) {
+    trimmedLen = whitespacesAtStart(text);
+  }
+  let trimmedEndLen = 0;
+  if (!isWhitespace(pattern[lenPattern - 1])) {
+    trimmedEndLen = whitespacesAtEnd(text);
+  }
+  if (text.length - trimmedLen - trimmedEndLen != lenPattern) {
+    return [{ start: -1, end: -1, score: 0 }, null];
+  }
+  let match = true;
+  if (normalize) {
+    const runes = text;
+    for (const [idx, pchar] of pattern.entries()) {
+      let rune = runes[trimmedLen + idx];
+      if (!caseSensitive) {
+        rune = String.fromCodePoint(rune).toLowerCase().codePointAt(0);
+      }
+      if (normalizeRune(pchar) !== normalizeRune(rune)) {
+        match = false;
+        break;
+      }
+    }
+  } else {
+    let runesStr = runesToStr(text).substring(trimmedLen, text.length - trimmedEndLen);
+    if (!caseSensitive) {
+      runesStr = runesStr.toLowerCase();
+    }
+    match = runesStr === runesToStr(pattern);
+  }
+  if (match) {
+    return [
+      {
+        start: trimmedLen,
+        end: trimmedLen + lenPattern,
+        score: (SCORE_MATCH + BONUS_BOUNDARY) * lenPattern + (BONUS_FIRST_CHAR_MULTIPLIER - 1) * BONUS_BOUNDARY
+      },
+      null
+    ];
+  }
+  return [{ start: -1, end: -1, score: 0 }, null];
+};
+const SLAB_16_SIZE = 100 * 1024;
+const SLAB_32_SIZE = 2048;
+function makeSlab(size16, size32) {
+  return {
+    i16: new Int16Array(size16),
+    i32: new Int32Array(size32)
+  };
+}
+const slab = makeSlab(SLAB_16_SIZE, SLAB_32_SIZE);
+var TermType = /* @__PURE__ */ ((TermType2) => {
+  TermType2[TermType2["Fuzzy"] = 0] = "Fuzzy";
+  TermType2[TermType2["Exact"] = 1] = "Exact";
+  TermType2[TermType2["Prefix"] = 2] = "Prefix";
+  TermType2[TermType2["Suffix"] = 3] = "Suffix";
+  TermType2[TermType2["Equal"] = 4] = "Equal";
+  return TermType2;
+})(TermType || {});
+const termTypeMap = {
+  [0]: fuzzyMatchV2,
+  [1]: exactMatchNaive,
+  [2]: prefixMatch,
+  [3]: suffixMatch,
+  [4]: equalMatch
+};
+function buildPatternForExtendedMatch(fuzzy, caseMode, normalize, str) {
+  let cacheable = true;
+  str = str.trimLeft();
+  {
+    const trimmedAtRightStr = str.trimRight();
+    if (trimmedAtRightStr.endsWith("\\") && str[trimmedAtRightStr.length] === " ") {
+      str = trimmedAtRightStr + " ";
+    } else {
+      str = trimmedAtRightStr;
+    }
+  }
+  let sortable = false;
+  let termSets = [];
+  termSets = parseTerms(fuzzy, caseMode, normalize, str);
+  Loop:
+    for (const termSet of termSets) {
+      for (const [idx, term] of termSet.entries()) {
+        if (!term.inv) {
+          sortable = true;
+        }
+        if (!cacheable || idx > 0 || term.inv || fuzzy && term.typ !== 0 || !fuzzy && term.typ !== 1) {
+          cacheable = false;
+          if (sortable) {
+            break Loop;
+          }
+        }
+      }
+    }
+  return {
+    str,
+    termSets,
+    sortable,
+    cacheable,
+    fuzzy
+  };
+}
+function parseTerms(fuzzy, caseMode, normalize, str) {
+  str = str.replace(/\\ /g, "	");
+  const tokens = str.split(/ +/);
+  const sets = [];
+  let set = [];
+  let switchSet = false;
+  let afterBar = false;
+  for (const token of tokens) {
+    let typ = 0, inv = false, text = token.replace(/\t/g, " ");
+    const lowerText = text.toLowerCase();
+    const caseSensitive = caseMode === "case-sensitive" || caseMode === "smart-case" && text !== lowerText;
+    const normalizeTerm = normalize && lowerText === runesToStr(strToRunes(lowerText).map(normalizeRune));
+    if (!caseSensitive) {
+      text = lowerText;
+    }
+    if (!fuzzy) {
+      typ = 1;
+    }
+    if (set.length > 0 && !afterBar && text === "|") {
+      switchSet = false;
+      afterBar = true;
+      continue;
+    }
+    afterBar = false;
+    if (text.startsWith("!")) {
+      inv = true;
+      typ = 1;
+      text = text.substring(1);
+    }
+    if (text !== "$" && text.endsWith("$")) {
+      typ = 3;
+      text = text.substring(0, text.length - 1);
+    }
+    if (text.startsWith("'")) {
+      if (fuzzy && !inv) {
+        typ = 1;
+      } else {
+        typ = 0;
+      }
+      text = text.substring(1);
+    } else if (text.startsWith("^")) {
+      if (typ === 3) {
+        typ = 4;
+      } else {
+        typ = 2;
+      }
+      text = text.substring(1);
+    }
+    if (text.length > 0) {
+      if (switchSet) {
+        sets.push(set);
+        set = [];
+      }
+      let textRunes = strToRunes(text);
+      if (normalizeTerm) {
+        textRunes = textRunes.map(normalizeRune);
+      }
+      set.push({
+        typ,
+        inv,
+        text: textRunes,
+        caseSensitive,
+        normalize: normalizeTerm
+      });
+      switchSet = true;
+    }
+  }
+  if (set.length > 0) {
+    sets.push(set);
+  }
+  return sets;
+}
+const buildPatternForBasicMatch = (query, casing, normalize) => {
+  let caseSensitive = false;
+  switch (casing) {
+    case "smart-case":
+      if (query.toLowerCase() !== query) {
+        caseSensitive = true;
+      }
+      break;
+    case "case-sensitive":
+      caseSensitive = true;
+      break;
+    case "case-insensitive":
+      query = query.toLowerCase();
+      caseSensitive = false;
+      break;
+  }
+  let queryRunes = strToRunes(query);
+  if (normalize) {
+    queryRunes = queryRunes.map(normalizeRune);
+  }
+  return {
+    queryRunes,
+    caseSensitive
+  };
+};
+function iter(algoFn, tokens, caseSensitive, normalize, forward, pattern, slab2) {
+  for (const part of tokens) {
+    const [res, pos] = algoFn(caseSensitive, normalize, forward, part.text, pattern, true, slab2);
+    if (res.start >= 0) {
+      const sidx = res.start + part.prefixLength;
+      const eidx = res.end + part.prefixLength;
+      if (pos !== null) {
+        const newPos = /* @__PURE__ */ new Set();
+        pos.forEach((v) => newPos.add(part.prefixLength + v));
+        return [[sidx, eidx], res.score, newPos];
+      }
+      return [[sidx, eidx], res.score, pos];
+    }
+  }
+  return [[-1, -1], 0, null];
+}
+function computeExtendedMatch(text, pattern, fuzzyAlgo, forward) {
+  const input = [
+    {
+      text,
+      prefixLength: 0
+    }
+  ];
+  const offsets = [];
+  let totalScore = 0;
+  const allPos = /* @__PURE__ */ new Set();
+  for (const termSet of pattern.termSets) {
+    let offset = [0, 0];
+    let currentScore = 0;
+    let matched = false;
+    for (const term of termSet) {
+      let algoFn = termTypeMap[term.typ];
+      if (term.typ === TermType.Fuzzy) {
+        algoFn = fuzzyAlgo;
+      }
+      const [off, score, pos] = iter(
+        algoFn,
+        input,
+        term.caseSensitive,
+        term.normalize,
+        forward,
+        term.text,
+        slab
+      );
+      const sidx = off[0];
+      if (sidx >= 0) {
+        if (term.inv) {
+          continue;
+        }
+        offset = off;
+        currentScore = score;
+        matched = true;
+        if (pos !== null) {
+          pos.forEach((v) => allPos.add(v));
+        } else {
+          for (let idx = off[0]; idx < off[1]; ++idx) {
+            allPos.add(idx);
+          }
+        }
+        break;
+      } else if (term.inv) {
+        offset = [0, 0];
+        currentScore = 0;
+        matched = true;
+        continue;
+      }
+    }
+    if (matched) {
+      offsets.push(offset);
+      totalScore += currentScore;
+    }
+  }
+  return { offsets, totalScore, allPos };
+}
+function getResultFromScoreMap(scoreMap, limit) {
+  const scoresInDesc = Object.keys(scoreMap).map((v) => parseInt(v, 10)).sort((a, b) => b - a);
+  let result = [];
+  for (const score of scoresInDesc) {
+    result = result.concat(scoreMap[score]);
+    if (result.length >= limit) {
+      break;
+    }
+  }
+  return result;
+}
+function getBasicMatchIter(scoreMap, queryRunes, caseSensitive) {
+  return (idx) => {
+    const itemRunes = this.runesList[idx];
+    if (queryRunes.length > itemRunes.length)
+      return;
+    let [match, positions] = this.algoFn(
+      caseSensitive,
+      this.opts.normalize,
+      this.opts.forward,
+      itemRunes,
+      queryRunes,
+      true,
+      slab
+    );
+    if (match.start === -1)
+      return;
+    if (this.opts.fuzzy === false) {
+      positions = /* @__PURE__ */ new Set();
+      for (let position = match.start; position < match.end; ++position) {
+        positions.add(position);
+      }
+    }
+    const scoreKey = this.opts.sort ? match.score : 0;
+    if (scoreMap[scoreKey] === void 0) {
+      scoreMap[scoreKey] = [];
+    }
+    scoreMap[scoreKey].push(Object.assign({
+      item: this.items[idx],
+      positions: positions != null ? positions : /* @__PURE__ */ new Set()
+    }, match));
+  };
+}
+function getExtendedMatchIter(scoreMap, pattern) {
+  return (idx) => {
+    const runes = this.runesList[idx];
+    const match = computeExtendedMatch(runes, pattern, this.algoFn, this.opts.forward);
+    if (match.offsets.length !== pattern.termSets.length)
+      return;
+    let sidx = -1, eidx = -1;
+    if (match.allPos.size > 0) {
+      sidx = Math.min(...match.allPos);
+      eidx = Math.max(...match.allPos) + 1;
+    }
+    const scoreKey = this.opts.sort ? match.totalScore : 0;
+    if (scoreMap[scoreKey] === void 0) {
+      scoreMap[scoreKey] = [];
+    }
+    scoreMap[scoreKey].push({
+      score: match.totalScore,
+      item: this.items[idx],
+      positions: match.allPos,
+      start: sidx,
+      end: eidx
+    });
+  };
+}
+function basicMatch(query) {
+  const { queryRunes, caseSensitive } = buildPatternForBasicMatch(
+    query,
+    this.opts.casing,
+    this.opts.normalize
+  );
+  const scoreMap = {};
+  const iter2 = getBasicMatchIter.bind(this)(
+    scoreMap,
+    queryRunes,
+    caseSensitive
+  );
+  for (let i = 0, len = this.runesList.length; i < len; ++i) {
+    iter2(i);
+  }
+  return getResultFromScoreMap(scoreMap, this.opts.limit);
+}
+function extendedMatch(query) {
+  const pattern = buildPatternForExtendedMatch(
+    Boolean(this.opts.fuzzy),
+    this.opts.casing,
+    this.opts.normalize,
+    query
+  );
+  const scoreMap = {};
+  const iter2 = getExtendedMatchIter.bind(this)(scoreMap, pattern);
+  for (let i = 0, len = this.runesList.length; i < len; ++i) {
+    iter2(i);
+  }
+  return getResultFromScoreMap(scoreMap, this.opts.limit);
+}
+const defaultOpts = {
+  limit: Infinity,
+  selector: (v) => v,
+  casing: "smart-case",
+  normalize: true,
+  fuzzy: "v2",
+  tiebreakers: [],
+  sort: true,
+  forward: true,
+  match: basicMatch
+};
+class Finder {
+  constructor(list, ...optionsTuple) {
+    this.opts = Object.assign(defaultOpts, optionsTuple[0]);
+    this.items = list;
+    this.runesList = list.map((item) => strToRunes(this.opts.selector(item).normalize()));
+    this.algoFn = exactMatchNaive;
+    switch (this.opts.fuzzy) {
+      case "v2":
+        this.algoFn = fuzzyMatchV2;
+        break;
+      case "v1":
+        this.algoFn = fuzzyMatchV1;
+        break;
+    }
+  }
+  find(query) {
+    if (query.length === 0 || this.items.length === 0)
+      return this.items.slice(0, this.opts.limit).map(createResultItemWithEmptyPos);
+    query = query.normalize();
+    let result = this.opts.match.bind(this)(query);
+    return postProcessResultItems(result, this.opts);
+  }
+}
+function createResultItemWithEmptyPos(item) {
+  return ({
+    item,
+    start: -1,
+    end: -1,
+    score: 0,
+    positions: /* @__PURE__ */ new Set()
+  })
+};
+function postProcessResultItems(result, opts) {
+  if (opts.sort) {
+    const { selector } = opts;
+    result.sort((a, b) => {
+      if (a.score === b.score) {
+        for (const tiebreaker of opts.tiebreakers) {
+          const diff = tiebreaker(a, b, selector);
+          if (diff !== 0) {
+            return diff;
+          }
+        }
+      }
+      return 0;
+    });
+  }
+  if (Number.isFinite(opts.limit)) {
+    result.splice(opts.limit);
+  }
+  return result;
+}
+function byLengthAsc(a, b, selector) {
+  return selector(a.item).length - selector(b.item).length;
+}
+function byStartAsc(a, b) {
+  return a.start - b.start;
+}