declare function fuzzySearch<T>(Props: { query: string; source: T[]; callback: (item: T) => string; limit?: number; ambig?: number; timeout?: number; }): T[][];

function fuzzySearch({query, source, callback = w => w, limit, ambig, timeout} = {}) { // 検索keyword及び検索候補が空のときは何もしない if (query.trim() === '' || source.length === 0) return []; // 値のcheck if (typeof query !== 'string') throw Error('query is not a string.'); if (typeof callback !== 'function') throw Error('callback is not a function'); if (typeof limit !== 'number' && limit !== undefined) throw Error('limit is not a number'); if (limit <= 0) throw Error('limit is not more than 0.'); if (typeof ambig !== 'number' && ambig !== undefined) throw Error('ambig is not a number'); if (typeof timeout !== 'number') throw Error('timeout is not a number.'); if (timeout <= 0) throw Error('timeout is not more than 0.'); let cancel = false; const execCancel = () => cancel = true; // 計算を中断する関数 /* // この時点ではまだPromiseを開始しない const execPromise = () => new Promise((resolve) => {*/ // 空白文字で区切った文字列を並び替え、曖昧検索objectを作る const asearches = getPermutation(query.split(/\s/)) .map(wordList => new Asearch(` ${wordList.join(' ')} `)); //console.log('created asearches.'); // ambigの最大値を計算する let maxAmbig = ambig ?? Math.floor(` ${query} `.length / 4) + 1; maxAmbig = maxAmbig > 4 ? 4 : maxAmbig;

// 検索する const results = []; const totalResults = new Set(); const searchList = source.map(object => {return {object, text: callback(object)};}); const start = (new Date()).getTime();

for (const ambig of range(maxAmbig)) { const matches = []; for (const asearch of asearches) { // 検索したものを重複を取り除いて追加する for (const {object, text} of searchList) { if (limit && totalResults.size >= limit) execCancel(); if (cancel) { // 計算を中断する results.push(matches); //resolve(results); return results; } if (totalResults.has(text)) continue; if (!asearch.match(text, ambig)) continue; matches.push(object); totalResults.add(text); } if (start + timeout < (new Date()).getTime()) { console.info('time out'); execCancel(); } } results.push(matches); } //resolve(results); /*});*/ //console.log('created promise.'); //return {execute: execPromise, cancel: execCancel}; return results; }

const range = n => [...Array(n).keys()]; // [0,1,2,...,n-1]を返す class Asearch { get INITPAT() {return 0x80000000;} // 0100,0000,0000,0000,0000,0000,0000,0000 get MAXCHAR() {return 0x100;} // 256文字が上限 get INITSTATE() {return [this.INITPAT, 0, 0, 0];} constructor(source) { this.shiftpat = Array(this.MAXCHAR).map(_ => 0); this.epsilon = 0; let mask = this.INITPAT; for (const item of this.unpack(source)) { // 0x20 is a space if (item === 0x20) { this.epsilon |= mask; } else { this.shiftpat[item] |= mask; this.shiftpat[this.toupper(item)] |= mask; this.shiftpat[this.tolower(item)] |= mask; mask >>>= 1; } } this.acceptpat = mask; } tolower(c) { return this.isupper(c) ? c + 0x20 : c; } toupper(c) { return this.islower(c) ? c - 0x20 : c; } isupper(c) { // 0x41 = A, 0x5a = Z return (c >= 0x41) && (c <= 0x5a); } islower(c) { // 0x61 = a, 0x7a = z return (c >= 0x61) && (c <= 0x7a); } state(str = '') { let i0 = this.INITSTATE[0]; let i1 = this.INITSTATE[1]; let i2 = this.INITSTATE[2]; let i3 = this.INITSTATE[3]; for (const item of this.unpack(str)) { const mask = this.shiftpat[item]; i3 = (i3 & this.epsilon) | ((i3 & mask) >>> 1) | (i2 >>> 1) | i2; i2 = (i2 & this.epsilon) | ((i2 & mask) >>> 1) | (i1 >>> 1) | i1; i1 = (i1 & this.epsilon) | ((i1 & mask) >>> 1) | (i0 >>> 1) | i0; i0 = (i0 & this.epsilon) | ((i0 & mask) >>> 1); i1 |= i0 >>> 1; i2 |= i1 >>> 1; i3 |= i2 >>> 1; } return [i0, i1, i2, i3]; } match(str, ambig = 0) { ambig = ambig < this.INITSTATE.length ? ambig : this.INITSTATE.length - 1; const s = this.state(str); return (s[ambig] & this.acceptpat) !== 0; } // UTF-16 code pointを上8bitと下8bitとに分割する unpack(str) { return str.split('') .flatMap(char => { const code = char.charCodeAt(0); if (code > 0xFF) { return [(code & 0xFF00) >>> 8, code & 0xFF]; } return [code & 0xFF]; // 下の8ビットを取得する }); } }

// 重複は考慮していない function getPermutation(list) { if (list.length == 0) return list; if (list.length == 1) return [list]; if (list.length == 2) return [[list[0],list[1]],[list[1],list[0]]]; return list.flatMap(first => { const restList = list.filter(item => item !== first); return getPermutation(restList).map(permutation => [first, ...permutation]); }); }

(() => { const worker = new Worker('/api/code/programming-notes/WebWorker用asearch/test1_worker.js'); worker.postMessage({type: 'fetch', projects: [ 'hub', 'shokai', 'nishio', 'masui', 'rakusai', 'yuiseki', 'june29', 'ucdktr2016', 'villagepump', 'rashitamemo', 'thinkandcreateteck', 'customize', 'scrapboxlab', 'scrasobox', 'foldrr', 'scrapbox-drinkup', 'motoso', 'public-mrsekut', 'mrsekut-p', 'marshmallow-rm', 'wkpmm', 'sushitecture', 'nwtgck', 'dojineko', 'kadoyau', 'inteltank', 'sta', 'kn1cht', 'miyamonz', 'rmaruon', 'MISONLN41', 'yuta0801', 'choiyakiBox', 'choiyaki-hondana', 'spud-oimo', 'keroxp', 'aioilight', ]}); window.search = (word, {limit = 30, timeout = 10000,} = {}) => worker.postMessage({type: 'search', word, limit, timeout}); })();

self.importScripts('/api/code/programming-notes/WebWorker用asearch/script.js'); // 検索候補 const list = []; self.addEventListener('message', message => { switch (message.data.type) { case 'search': search(message.data); break; case 'fetch': fetch_(message.data.projects); break; } }); async function search({word, limit, timeout}) { _log(`start searching for ${word}...: limit = ${limit}`); const result = fuzzySearch({ query: word.split('/').join(' '), source: list, limit, timeout, }); _log('finished: %o', result); self.postMessage({links: result,}); /* const {execute, cancel} = fuzzySearch({ query: word.split('/').join(' '), source: list, limit, }); let promise = undefined; let timer = null; const post = async () => { clearTimeout(timer); const result = await promise; _log('finished: %o', result); self.postMessage({links: result,}); } _log('start timer.', timeout); promise = execute(); timer = setTimeout(async () => { cancel(); _log('abort searching.', timeout); clearTimeout(timer); const result = await promise; _log('finished: %o', result); self.postMessage({links: result,}); }, timeout); await post();*/ } async function fetch_(projects) { _log('Loading links from %o', projects); const result = await Promise.all(projects .map(project => fetchExternalLinks(project)) ); _log('Finish loading links from %o', projects); list.push(...result.flat()); } async function fetchExternalLinks(project) { let followingId = null; let temp = []; _log(`Start loading links from ${project}...`); do { _log(`Loading links from ${project}: followingId = ${followingId}`); const json = await (!followingId ? fetch(`/api/pages/${project}/search/titles`) : fetch(`/api/pages/${project}/search/titles?followingId=${followingId}`) ).then(res => { followingId = res.headers.get('X-Following-Id'); return res.json(); }); temp.push(...json.flatMap(page => [...page.links, page.title]).map(link => `/${project}/${link}`)); } while(followingId); const links = [...new Set(temp)]; // 重複を取り除く _log(`Loaded ${links.length} links from /${project}`); return links; } // debug用 function _log(msg, ...objects) { console.log(`[search-worker @WebWorker用asearch/test1.worker.js] ${msg}`, ...objects); }