TableRowFilter = { /** @typedef {Map} SparseRowBitmap */ /** @typedef {Map} ShortMap */ /** @typedef {Map} TrigramMap */ /** @typedef {Map>} RowIndexMap */ /** @typedef {[Array, RowIndexMap, string]} STFilterResult */ const NO_TRIGRAM = new Map(), EMPTY_TRIGRAM = new Map(); const setZeroTimeout = (() => { const taskChannel = new MessageChannel(), taskQueue = []; taskChannel.port1.onmessage = () => { const [task, args] = taskQueue.shift(); task.apply(task, args); }; return function setZeroTimeout(task, ...args) { taskQueue.push([task, args]); taskChannel.port2.postMessage(null); }; })(); return class TableRowFilter { /** * @param {Array} rowContents */ constructor(rowContents) { let maxLen = 0 this.rowContents = rowContents = rowContents.map(str => { if (str.length > maxLen) maxLen = str.length; return str.toLowerCase(); }); const encoder = this.encoder = new TextEncoder(); if (maxLen * 4 > TableRowFilter.cc.length) TableRowFilter.cc = new Uint8Array(maxLen * 4); const {cc} = TableRowFilter; // For single char filters and bigram filters we use // sparse bitmaps to determine whether a row contains // them. For trigrams or longer we store the row plus // index where the trigram was found. Longer filters // can then be constructed from intersecting trigrams /** @type {ShortMap} */ this.shortMap = new Map(); /** @type {TrigramMap} */ this.trigramMap = new Map(); this.initialized = false; const {shortMap, trigramMap} = this; let i = 0; const initFilterMaps = () => { const t0 = performance.now(); let charsProcessed = 0; // We iterate over the rows in order, and over the characters // per row as well. This means suffixes are encountered in the // order of appearance, so for each trigram the rows will be // inserted in ascending order, and similarly the indices array // will be sorted as well. This simplifies doing the intersections // of trigrams later on. rowLoop: for (; i < rowContents.length; i++) { const rowString = rowContents[i]; let utf8len; if (rowString.length && (utf8len = encoder.encodeInto(rowString, cc).written)) { // let c0 = rowString.charCodeAt(0); let c0 = cc[0]; this.setBit(c0, i); if (utf8len > 1) { // let c1 = rowString.charCodeAt(1); let c1 = cc[1]; this.setBit(c1, i); // separate bigrams from chars by setting an extra bit this.setBit(0x10000 + (c0 << 8) + c1, i); for (let j = 2; j < utf8len; j++) { const c2 = cc[j]; this.setBit(c2, i); this.setBit(0x10000 + (c1 << 8) + c2, i); const key = (c0 << 16) + (c1 << 8) + c2; let rows = trigramMap.get(key); if (!rows) trigramMap.set(key, rows = new Map()); let indices = rows.get(i); if (!indices) rows.set(i, indices = []); indices.push(j - 2); c0 = c1; c1 = c2; } } if ((charsProcessed += rowString.length) > 1000) { charsProcessed = 0; if (performance.now() - t0 > 20) break rowLoop; } } } if (i < rowContents.length) setZeroTimeout(initFilterMaps); else this.initialized = true; }; initFilterMaps(); } static cc = new Uint8Array(0); /** * Convenience method to set row bits for single chars and bigrams * @param {number} key * @param {number} rowIdx */ setBit(key, rowIdx) { let rowBitmap = this.shortMap.get(key); if (!rowBitmap) this.shortMap.set(key, rowBitmap = new Map()); const row32 = rowBitmap.get(rowIdx >> 5); const bit = 1 << (rowIdx & 0x3F); // @ts-expect-error using bitmasking to force undefined to 0 if (!(row32 & bit)) rowBitmap.set(rowIdx >> 5, row32 | bit); } /** * @param {string} filterString * @param {STFilterResult} [prevResult] * @returns {STFilterResult} */ filter(filterString, prevResult = [[], this.trigramMap ? EMPTY_TRIGRAM : NO_TRIGRAM, ""]) { // There are many points where we bail quickly with an empty result, // so here's an arrow function to make sure it returns the correct // empty result each time. const emptyMap = this.trigramMap ? EMPTY_TRIGRAM : NO_TRIGRAM; /** @type {(fltrStr: string) => STFilterResult} */ const emptyResult = fltrStr => [[], emptyMap, fltrStr]; // bail early if there is no filter if (!filterString) return emptyResult(""); filterString = filterString.toLowerCase(); // Bail early if filterString continues/equals // pFilter and pRows is already empty. let [pRows, pRowMap, pFilter] = prevResult; if (pRowMap !== NO_TRIGRAM && !pRows.length && pFilter && filterString.startsWith(pFilter)) { prevResult[2] = filterString; return prevResult; } // If the maps are not initialized yet, fall back // to slower array filter approach if (!this.initialized) { const rows = []; const {rowContents} = this; if (pFilter && filterString.startsWith(pFilter)) { for (let i = 0; i < pRows.length; i++) { const rowIdx = pRows[i]; if (rowContents[rowIdx].indexOf(filterString) !== -1) { rows.push(rowIdx); } } } else { for (let i = 0; i < rowContents.length; i++) { if (rowContents[i].indexOf(filterString) !== -1) { rows.push(i); } } } return [ rows, NO_TRIGRAM, filterString ]; } const {encoder} = this; const {cc} = TableRowFilter; const {written: uf8length} = encoder.encodeInto(filterString, cc); // If the filterString is 1 or 2 chars, use the bitmap lookup if (filterString.length < 3) { let key = cc[0]; if (filterString.length === 2) { key = 0x10000 + (key << 8) + cc[1]; } const rowBitmap = this.shortMap.get(key); // if there is no bitmap, there are no rows if (!rowBitmap) return emptyResult(filterString); // Otherwise, convert bitmaps back to row indices. const rows = []; for (let [rowUpper, row32] of rowBitmap) { rowUpper <<= 5; for (let i = 0; row32 && i < 32; i++, row32 >>>= 1) { if (row32 & 1) rows.push(rowUpper + i); } } return [rows, new Map(), filterString]; } // We search backwards from the end of the filter string, until we // overlap the first trigram. This has two reasons. The first is to // handle strings whose lengths are not multiples of three, e.g. if // the filter is "hello there" then we intersect trigrams "hel", "ere", // " th", and "llo", the latter overlapping with the first "hel". // The other is that for text, adjacent ngrams are more strongly // correlated. When the goal is to narrow down the nr of rows quickly, // intersecting the *least* correlated trigrams does so faster. // Starting from the first trigram, then intersecting with the last, // and working back to the first is therefore more likely to narrow // down results quickly, speeding up intersections. let i = filterString.length - 3; /** @type {number} */ let start; // A cached result is only valid if it was generated via trigrams, so // neither by plain array filtering or via the bitmaps for single chars // or bigrams, and if the previous filter is a prefix of the current one. if (pRowMap !== NO_TRIGRAM && pFilter.length > 2 && filterString.startsWith(pFilter)) { start = pFilter.length - 3; } else { start = 0; // In all other cases, we start anew from the first trigram. const nRowMap = this.trigramMap.get((cc[0] << 16) + (cc[1] << 8) + cc[2]); // If a trigram is not present there are no rows associated with it if (!nRowMap) return emptyResult(filterString); // For longer filter strings we need to intersect multiple trigrams, // but also have to avoid mutating the original rowMaps and indices. // So we start with a deep copy of the first trigram's rowMap and its // indices. We mutate this copy as we intersect with later trigram // sections to narrow down the number of rows and their indices. pRowMap = new Map(); let j = 0; for (const [row, indices] of nRowMap) { pRows[j++] = row; pRowMap.set(row, indices.slice()); } pRows.length = j; // If the filterString fits in the first trigram, return results early if (filterString.length < 4) { return [pRows, pRowMap, filterString]; } } for (; i > start && pRows.length; i -= 3) { const nRowMap = this.trigramMap.get((cc[i] << 16) + (cc[i + 1] << 8) + cc[i + 2]); // If a trigram is not present there are no rows associated with it if (!nRowMap) return emptyResult(filterString); // Filter out all rows that aren't in both pRowMap and nRowMap // Iterate over the smallest array for a faster intersection. let k = 0; if (pRowMap.size <= nRowMap.size) { for (let j = 0; j < pRows.length; j++) { const row = pRows[j]; const indices = nRowMap.get(row); if (indices) pRows[k++] = row; else pRowMap.delete(row); } } else { const tempRowMap = new Map(); for (const nRow of nRowMap.keys()) { const indices = pRowMap.get(nRow); if (indices) { tempRowMap.set(nRow, indices); pRows[k++] = nRow; } } pRowMap = tempRowMap; } pRows.length = k; for (let j = 0; j < pRows.length; j++) { let row = pRows[j]; const indices = /** @type {Array} */ (pRowMap.get(row)); const nIndices = /** @type {Array} */ (nRowMap.get(row)); let l = 0, m = 0, n = 0; let idx = indices[m], nIdx = nIndices[n] - i; indexLoop: while (true) { while (idx < nIdx) { if (++m >= indices.length) break indexLoop; idx = indices[m]; } while (nIdx < idx) { if (++n >= nIndices.length) break indexLoop; nIdx = nIndices[n] - i; } if (idx === nIdx) { indices[l++] = indices[m++]; n++; if (m >= indices.length || n >= nIndices.length) break indexLoop; idx = indices[m], nIdx = nIndices[n] - i; } } // empty indices means empty row, in which case we filter it out if (!l) pRowMap.delete(row); else indices.length = l; } if (pRowMap.size < pRows.length) pRows = [...pRowMap.keys()]; } return [pRows, pRowMap, filterString]; } }; }