Google Git Google Git
Sign in
rust/rust/704858caa7ac7b8564d87defbbca9dcbe7d31b33/./src/librustdoc/html/static/js/stringdex.js
blob: a5772e5c364c400bec0f01fd2ad4ecc5ed46a6cc [file]
// ignore-tidy-file-filelength
/**
* @import * as stringdex from "./stringdex.d.ts"
*/
const EMPTY_UINT8 = new Uint8Array();
/**
* @property {Uint8Array} keysAndCardinalities
* @property {Uint8Array[]} containers
*/
class RoaringBitmap {
/**
* @param {Uint8Array|null} u8array
* @param {number} [startingOffset]
*/
constructor(u8array, startingOffset) {
const start = startingOffset ? startingOffset : 0;
let i = start;
/** @type {Uint8Array} */
this.keysAndCardinalities = EMPTY_UINT8;
/** @type {(RoaringBitmapArray|RoaringBitmapBits|RoaringBitmapRun)[]} */
this.containers = [];
/** @type {number} */
this.consumed_len_bytes = 0;
if (u8array === null || u8array.length === i || u8array[i] === 0) {
return this;
} else if (u8array[i] > 0xf0) {
// Special representation of tiny sets that are close together
const lspecial = u8array[i] & 0x0f;
this.keysAndCardinalities = new Uint8Array(lspecial * 4);
let pspecial = i + 1;
let key = u8array[pspecial + 2] | (u8array[pspecial + 3] << 8);
let value = u8array[pspecial] | (u8array[pspecial + 1] << 8);
let entry = (key << 16) | value;
let container;
container = new RoaringBitmapArray(1, new Uint8Array(4));
container.array[0] = value & 0xFF;
container.array[1] = (value >> 8) & 0xFF;
this.containers.push(container);
this.keysAndCardinalities[0] = key;
this.keysAndCardinalities[1] = key >> 8;
pspecial += 4;
for (let ispecial = 1; ispecial < lspecial; ispecial += 1) {
entry += u8array[pspecial] | (u8array[pspecial + 1] << 8);
value = entry & 0xffff;
key = entry >> 16;
container = this.addToArrayAt(key);
const cardinalityOld = container.cardinality;
container.array[cardinalityOld * 2] = value & 0xFF;
container.array[(cardinalityOld * 2) + 1] = (value >> 8) & 0xFF;
container.cardinality = cardinalityOld + 1;
pspecial += 2;
}
this.consumed_len_bytes = pspecial - i;
return this;
} else if (u8array[i] > 0xe0) {
// Special representation of a node with multiple runs
const run_count_m1 = (u8array[i] & 0x0f);
const run_count = run_count_m1 + 1;
this.keysAndCardinalities = new Uint8Array(run_count * 4);
// the run keys and values
let pspecial = i + 1;
// the run lengths
let pnspecial = pspecial + (run_count * 4);
/** @type {number|null} */
let previous_key = null;
/** @type {RoaringBitmapRun|null} */
let previous_container = null;
for (let j = 0; j < run_count; j += 1) {
const key = u8array[pspecial + 2] | (u8array[pspecial + 3] << 8);
const value = u8array[pspecial] | (u8array[pspecial + 1] << 8);
const run_length_m1 = j % 2 === 0 ?
(u8array[pnspecial] >> 4) :
(u8array[pnspecial] & 0x0f);
if (j % 2 !== 0) {
pnspecial += 1;
}
pspecial += 4;
if (key === previous_key && previous_container !== null) {
const new_container_array = new Uint8Array(
(previous_container.runcount + 1) * 4,
);
new_container_array.set(previous_container.array);
new_container_array[previous_container.runcount * 4] = value & 0xFF;
new_container_array[(previous_container.runcount * 4) + 1] =
(value >> 8) & 0xFF;
new_container_array[(previous_container.runcount * 4) + 2] =
run_length_m1;
previous_container.array = new_container_array;
previous_container.runcount += 1;
let cardinalitym1 =
this.keysAndCardinalities[(this.containers.length * 4) - 2] |
(this.keysAndCardinalities[(this.containers.length * 4) - 1] << 8);
cardinalitym1 += run_length_m1 + 1;
this.keysAndCardinalities[(this.containers.length * 4) - 2] =
cardinalitym1 & 0xFF;
this.keysAndCardinalities[(this.containers.length * 4) - 1] =
(cardinalitym1 >> 8) & 0xFF;
} else {
previous_key = key;
previous_container = new RoaringBitmapRun(1, Uint8Array.of(
value & 0xFF,
(value >> 8) & 0xFF,
run_length_m1,
0,
));
this.containers.push(previous_container);
this.keysAndCardinalities[(this.containers.length * 4) - 4] = key & 0xFF;
this.keysAndCardinalities[(this.containers.length * 4) - 3] = (key >> 8) & 0xFF;
this.keysAndCardinalities[(this.containers.length * 4) - 2] = run_length_m1;
}
}
if (run_count % 2 !== 0) {
pnspecial += 1;
}
this.consumed_len_bytes = pnspecial - i;
return this;
} else if (u8array[i] > 0xd0) {
// Special representation of tiny sets that are close together
const lspecial = u8array[i] & 0x0f;
this.keysAndCardinalities = new Uint8Array(lspecial * 4);
let pspecial = i + 1;
let key = u8array[pspecial + 2] | (u8array[pspecial + 3] << 8);
let value = u8array[pspecial] | (u8array[pspecial + 1] << 8);
let entry = (key << 16) | value;
let container;
container = new RoaringBitmapArray(1, new Uint8Array(4));
container.array[0] = value & 0xFF;
container.array[1] = (value >> 8) & 0xFF;
this.containers.push(container);
this.keysAndCardinalities[0] = key;
this.keysAndCardinalities[1] = key >> 8;
pspecial += 4;
for (let ispecial = 1; ispecial < lspecial; ispecial += 1) {
entry += u8array[pspecial];
value = entry & 0xffff;
key = entry >> 16;
container = this.addToArrayAt(key);
const cardinalityOld = container.cardinality;
container.array[cardinalityOld * 2] = value & 0xFF;
container.array[(cardinalityOld * 2) + 1] = (value >> 8) & 0xFF;
container.cardinality = cardinalityOld + 1;
pspecial += 1;
}
this.consumed_len_bytes = pspecial - i;
return this;
} else if (u8array[i] > 0x80) {
// Special representation of tiny sets that are runs
const lspecial = u8array[i] & 0x3f;
const lspecialm1 = lspecial - 1;
this.keysAndCardinalities = new Uint8Array(4);
i += 1;
const key = u8array[i + 2] | (u8array[i + 3] << 8);
const value = u8array[i] | (u8array[i + 1] << 8);
const container = new RoaringBitmapRun(1, new Uint8Array(4));
container.array[0] = value & 0xFF;
container.array[1] = (value >> 8) & 0xFF;
container.array[2] = lspecialm1 & 0xFF;
container.array[3] = lspecialm1 >> 8;
this.containers.push(container);
this.keysAndCardinalities[0] = key & 0xFF;
this.keysAndCardinalities[1] = (key >> 8) & 0xFF;
this.keysAndCardinalities[2] = lspecialm1 & 0xFF;
this.keysAndCardinalities[3] = lspecialm1 >> 8;
this.consumed_len_bytes = 5;
return this;
} else if (u8array[i] < 0x3a) {
// Special representation of tiny sets with arbitrary 32-bit integers
const lspecial = u8array[i];
this.keysAndCardinalities = new Uint8Array(lspecial * 4);
let pspecial = i + 1;
for (let ispecial = 0; ispecial < lspecial; ispecial += 1) {
const key = u8array[pspecial + 2] | (u8array[pspecial + 3] << 8);
const value = u8array[pspecial] | (u8array[pspecial + 1] << 8);
const container = this.addToArrayAt(key);
const cardinalityOld = container.cardinality;
container.array[cardinalityOld * 2] = value & 0xFF;
container.array[(cardinalityOld * 2) + 1] = (value >> 8) & 0xFF;
container.cardinality = cardinalityOld + 1;
pspecial += 4;
}
this.consumed_len_bytes = pspecial - i;
return this;
}
// https://github.com/RoaringBitmap/RoaringFormatSpec
//
// Roaring bitmaps are used for flags that can be kept in their
// compressed form, even when loaded into memory. This decoder
// turns the containers into objects, but uses byte array
// slices of the original format for the data payload.
const has_runs = u8array[i] === 0x3b;
if (u8array[i] !== 0x3a && u8array[i] !== 0x3b) {
throw new Error("not a roaring bitmap: " + u8array[i]);
}
const size = has_runs ?
((u8array[i + 2] | (u8array[i + 3] << 8)) + 1) :
((u8array[i + 4] | (u8array[i + 5] << 8) |
(u8array[i + 6] << 16) | (u8array[i + 7] << 24)));
i += has_runs ? 4 : 8;
let is_run;
if (has_runs) {
const is_run_len = (size + 7) >> 3;
is_run = new Uint8Array(u8array.buffer, i + u8array.byteOffset, is_run_len);
i += is_run_len;
} else {
is_run = EMPTY_UINT8;
}
this.keysAndCardinalities = u8array.subarray(i, i + (size * 4));
i += size * 4;
let offsets = null;
if (!has_runs || size >= 4) {
offsets = [];
for (let j = 0; j < size; ++j) {
offsets.push(u8array[i] | (u8array[i + 1] << 8) | (u8array[i + 2] << 16) |
(u8array[i + 3] << 24));
i += 4;
}
}
for (let j = 0; j < size; ++j) {
if (offsets && offsets[j] !== i - start) {
throw new Error(`corrupt bitmap ${j}: ${i - start} / ${offsets[j]}`);
}
const cardinality = (this.keysAndCardinalities[(j * 4) + 2] |
(this.keysAndCardinalities[(j * 4) + 3] << 8)) + 1;
if (is_run[j >> 3] & (1 << (j & 0x7))) {
const runcount = (u8array[i] | (u8array[i + 1] << 8));
i += 2;
this.containers.push(new RoaringBitmapRun(
runcount,
new Uint8Array(u8array.buffer, i + u8array.byteOffset, runcount * 4),
));
i += runcount * 4;
} else if (cardinality >= 4096) {
this.containers.push(new RoaringBitmapBits(new Uint8Array(
u8array.buffer,
i + u8array.byteOffset, 8192,
)));
i += 8192;
} else {
const end = cardinality * 2;
this.containers.push(new RoaringBitmapArray(
cardinality,
new Uint8Array(u8array.buffer, i + u8array.byteOffset, end),
));
i += end;
}
}
this.consumed_len_bytes = i - start;
}
/**
* @param {number} number
* @returns {RoaringBitmap}
*/
static makeSingleton(number) {
const result = new RoaringBitmap(null, 0);
result.keysAndCardinalities = Uint8Array.of(
(number >> 16), (number >> 24),
0, 0, // keysAndCardinalities stores the true cardinality minus 1
);
result.containers.push(new RoaringBitmapArray(
1,
Uint8Array.of(number, number >> 8),
));
return result;
}
/** @returns {RoaringBitmap} */
static everything() {
if (EVERYTHING_BITMAP.isEmpty()) {
let i = 0;
const l = 1 << 16;
const everything_range = new RoaringBitmapRun(1, Uint8Array.of(0, 0, 0xff, 0xff));
EVERYTHING_BITMAP.keysAndCardinalities = new Uint8Array(l * 4);
while (i < l) {
EVERYTHING_BITMAP.containers.push(everything_range);
// key
EVERYTHING_BITMAP.keysAndCardinalities[(i * 4) + 0] = i;
EVERYTHING_BITMAP.keysAndCardinalities[(i * 4) + 1] = i >> 8;
// cardinality (minus one)
EVERYTHING_BITMAP.keysAndCardinalities[(i * 4) + 2] = 0xff;
EVERYTHING_BITMAP.keysAndCardinalities[(i * 4) + 3] = 0xff;
i += 1;
}
}
return EVERYTHING_BITMAP;
}
/** @returns {RoaringBitmap} */
static empty() {
return EMPTY_BITMAP;
}
/** @returns {boolean} */
isEmpty() {
return this.containers.length === 0;
}
/**
* Helper function used when constructing bitmaps from lists.
* Returns an array container with at least two free byte slots
* and bumps `this.cardinalities`.
* @param {number} key
* @returns {RoaringBitmapArray}
*/
addToArrayAt(key) {
let mid = this.getContainerId(key);
/** @type {RoaringBitmapArray|RoaringBitmapBits|RoaringBitmapRun} */
let container;
if (mid === -1) {
container = new RoaringBitmapArray(0, new Uint8Array(2));
mid = this.containers.length;
this.containers.push(container);
if (mid * 4 > this.keysAndCardinalities.length) {
const keysAndContainers = new Uint8Array(mid * 8);
keysAndContainers.set(this.keysAndCardinalities);
this.keysAndCardinalities = keysAndContainers;
}
this.keysAndCardinalities[(mid * 4) + 0] = key;
this.keysAndCardinalities[(mid * 4) + 1] = key >> 8;
} else {
container = this.containers[mid];
const cardinalityOld =
this.keysAndCardinalities[(mid * 4) + 2] |
(this.keysAndCardinalities[(mid * 4) + 3] << 8);
const cardinality = cardinalityOld + 1;
this.keysAndCardinalities[(mid * 4) + 2] = cardinality;
this.keysAndCardinalities[(mid * 4) + 3] = cardinality >> 8;
}
// the logic for handing this number is annoying, because keysAndCardinalities stores
// the cardinality *minus one*, so that it can count up to 65536 with only two bytes
// (because empty containers are never stored).
//
// So, if this is a new container, the stored cardinality contains `0 0`, which is
// the proper value of the old cardinality (an imaginary empty container existed).
// If this is adding to an existing container, then the above `else` branch bumps it
// by one, leaving us with a proper value of `cardinality - 1`.
const cardinalityOld =
this.keysAndCardinalities[(mid * 4) + 2] |
(this.keysAndCardinalities[(mid * 4) + 3] << 8);
if (!(container instanceof RoaringBitmapArray) ||
container.array.byteLength < ((cardinalityOld + 1) * 2)
) {
const newBuf = new Uint8Array((cardinalityOld + 1) * 4);
let idx = 0;
for (const cvalue of container.values()) {
newBuf[idx] = cvalue & 0xFF;
newBuf[idx + 1] = (cvalue >> 8) & 0xFF;
idx += 2;
}
if (container instanceof RoaringBitmapArray) {
container.cardinality = cardinalityOld;
container.array = newBuf;
return container;
}
const newcontainer = new RoaringBitmapArray(cardinalityOld, newBuf);
this.containers[mid] = newcontainer;
return newcontainer;
} else {
return container;
}
}
/**
* @param {RoaringBitmap} that
* @returns {RoaringBitmap}
*/
union(that) {
if (this.isEmpty()) {
return that;
}
if (that.isEmpty()) {
return this;
}
if (this === RoaringBitmap.everything() || that === RoaringBitmap.everything()) {
return RoaringBitmap.everything();
}
let i = 0;
const il = this.containers.length;
let j = 0;
const jl = that.containers.length;
const result = new RoaringBitmap(null, 0);
result.keysAndCardinalities = new Uint8Array((il + jl) * 4);
while (i < il || j < jl) {
const ik = i * 4;
const jk = j * 4;
const k = result.containers.length * 4;
if (j >= jl || (i < il && (
(this.keysAndCardinalities[ik + 1] < that.keysAndCardinalities[jk + 1]) ||
(this.keysAndCardinalities[ik + 1] === that.keysAndCardinalities[jk + 1] &&
this.keysAndCardinalities[ik] < that.keysAndCardinalities[jk])
))) {
result.keysAndCardinalities[k + 0] = this.keysAndCardinalities[ik + 0];
result.keysAndCardinalities[k + 1] = this.keysAndCardinalities[ik + 1];
result.keysAndCardinalities[k + 2] = this.keysAndCardinalities[ik + 2];
result.keysAndCardinalities[k + 3] = this.keysAndCardinalities[ik + 3];
result.containers.push(this.containers[i]);
i += 1;
} else if (i >= il || (j < jl && (
(that.keysAndCardinalities[jk + 1] < this.keysAndCardinalities[ik + 1]) ||
(that.keysAndCardinalities[jk + 1] === this.keysAndCardinalities[ik + 1] &&
that.keysAndCardinalities[jk] < this.keysAndCardinalities[ik])
))) {
result.keysAndCardinalities[k + 0] = that.keysAndCardinalities[jk + 0];
result.keysAndCardinalities[k + 1] = that.keysAndCardinalities[jk + 1];
result.keysAndCardinalities[k + 2] = that.keysAndCardinalities[jk + 2];
result.keysAndCardinalities[k + 3] = that.keysAndCardinalities[jk + 3];
result.containers.push(that.containers[j]);
j += 1;
} else {
// this key is not smaller than that key
// that key is not smaller than this key
// they must be equal
const thisContainer = this.containers[i];
const thatContainer = that.containers[j];
let card = 0;
if (thisContainer instanceof RoaringBitmapBits &&
thatContainer instanceof RoaringBitmapBits
) {
const resultArray = new Uint8Array(
thisContainer.array.length > thatContainer.array.length ?
thisContainer.array.length :
thatContainer.array.length,
);
let k = 0;
const kl = resultArray.length;
while (k < kl) {
const c = thisContainer.array[k] | thatContainer.array[k];
resultArray[k] = c;
card += bitCount(c);
k += 1;
}
result.containers.push(new RoaringBitmapBits(resultArray));
} else {
const thisValues = thisContainer.values();
const thatValues = thatContainer.values();
let thisResult = thisValues.next();
let thatResult = thatValues.next();
/** @type {Array<number>} */
const resultValues = [];
while (!thatResult.done || !thisResult.done) {
// generator will definitely implement the iterator protocol correctly
/** @type {number} */
const thisValue = thisResult.value;
/** @type {number} */
const thatValue = thatResult.value;
if (thatResult.done || thisValue < thatValue) {
resultValues.push(thisValue);
thisResult = thisValues.next();
} else if (thisResult.done || thatValue < thisValue) {
resultValues.push(thatValue);
thatResult = thatValues.next();
} else {
// this value is not smaller than that value
// that value is not smaller than this value
// they must be equal
resultValues.push(thisValue);
thisResult = thisValues.next();
thatResult = thatValues.next();
}
}
const resultArray = new Uint8Array(resultValues.length * 2);
let k = 0;
for (const value of resultValues) {
// roaring bitmap is little endian
resultArray[k] = value & 0xFF;
resultArray[k + 1] = (value >> 8) & 0xFF;
k += 2;
}
result.containers.push(new RoaringBitmapArray(
resultValues.length,
resultArray,
));
card = resultValues.length;
}
result.keysAndCardinalities[k + 0] = this.keysAndCardinalities[ik + 0];
result.keysAndCardinalities[k + 1] = this.keysAndCardinalities[ik + 1];
card -= 1;
result.keysAndCardinalities[k + 2] = card;
result.keysAndCardinalities[k + 3] = card >> 8;
i += 1;
j += 1;
}
}
return result;
}
/**
* @param {RoaringBitmap} that
* @returns {RoaringBitmap}
*/
intersection(that) {
if (this.isEmpty() || that.isEmpty()) {
return EMPTY_BITMAP;
}
if (this === RoaringBitmap.everything()) {
return that;
}
if (that === RoaringBitmap.everything()) {
return this;
}
let i = 0;
const il = this.containers.length;
let j = 0;
const jl = that.containers.length;
const result = new RoaringBitmap(null, 0);
result.keysAndCardinalities = new Uint8Array((il > jl ? il : jl) * 4);
while (i < il && j < jl) {
const ik = i * 4;
const jk = j * 4;
const k = result.containers.length * 4;
if (j >= jl || (i < il && (
(this.keysAndCardinalities[ik + 1] < that.keysAndCardinalities[jk + 1]) ||
(this.keysAndCardinalities[ik + 1] === that.keysAndCardinalities[jk + 1] &&
this.keysAndCardinalities[ik] < that.keysAndCardinalities[jk])
))) {
i += 1;
} else if (i >= il || (j < jl && (
(that.keysAndCardinalities[jk + 1] < this.keysAndCardinalities[ik + 1]) ||
(that.keysAndCardinalities[jk + 1] === this.keysAndCardinalities[ik + 1] &&
that.keysAndCardinalities[jk] < this.keysAndCardinalities[ik])
))) {
j += 1;
} else {
// this key is not smaller than that key
// that key is not smaller than this key
// they must be equal
const thisContainer = this.containers[i];
const thatContainer = that.containers[j];
let card = 0;
if (thisContainer instanceof RoaringBitmapBits &&
thatContainer instanceof RoaringBitmapBits
) {
const resultArray = new Uint8Array(
thisContainer.array.length > thatContainer.array.length ?
thisContainer.array.length :
thatContainer.array.length,
);
let k = 0;
const kl = resultArray.length;
while (k < kl) {
const c = thisContainer.array[k] & thatContainer.array[k];
resultArray[k] = c;
card += bitCount(c);
k += 1;
}
if (card !== 0) {
result.containers.push(new RoaringBitmapBits(resultArray));
}
} else {
const thisValues = thisContainer.values();
const thatValues = thatContainer.values();
let thisValue = thisValues.next();
let thatValue = thatValues.next();
const resultValues = [];
while (!thatValue.done && !thisValue.done) {
if (thisValue.value < thatValue.value) {
thisValue = thisValues.next();
} else if (thatValue.value < thisValue.value) {
thatValue = thatValues.next();
} else {
// this value is not smaller than that value
// that value is not smaller than this value
// they must be equal
resultValues.push(thisValue.value);
thisValue = thisValues.next();
thatValue = thatValues.next();
}
}
card = resultValues.length;
if (card !== 0) {
const resultArray = new Uint8Array(resultValues.length * 2);
let k = 0;
for (const value of resultValues) {
// roaring bitmap is little endian
resultArray[k] = value & 0xFF;
resultArray[k + 1] = (value >> 8) & 0xFF;
k += 2;
}
result.containers.push(new RoaringBitmapArray(
resultValues.length,
resultArray,
));
}
}
if (card !== 0) {
result.keysAndCardinalities[k + 0] = this.keysAndCardinalities[ik + 0];
result.keysAndCardinalities[k + 1] = this.keysAndCardinalities[ik + 1];
card -= 1;
result.keysAndCardinalities[k + 2] = card;
result.keysAndCardinalities[k + 3] = card >> 8;
}
i += 1;
j += 1;
}
}
return result;
}
/** @param {number} keyvalue */
contains(keyvalue) {
const key = keyvalue >> 16;
const value = keyvalue & 0xFFFF;
const mid = this.getContainerId(key);
return mid === -1 ? false : this.containers[mid].contains(value);
}
/**
* @param {number} keyvalue
* @returns {RoaringBitmap}
*/
remove(keyvalue) {
const key = keyvalue >> 16;
const value = keyvalue & 0xFFFF;
const mid = this.getContainerId(key);
if (mid === -1) {
return this;
}
const container = this.containers[mid];
if (!container.contains(value)) {
return this;
}
const newCardinality = (this.keysAndCardinalities[(mid * 4) + 2] |
(this.keysAndCardinalities[(mid * 4) + 3] << 8));
const l = this.containers.length;
const m = l - (newCardinality === 0 ? 1 : 0);
const result = new RoaringBitmap(null, 0);
result.keysAndCardinalities = new Uint8Array(m * 4);
let j = 0;
for (let i = 0; i < l; i += 1) {
if (i === mid) {
if (newCardinality !== 0) {
result.keysAndCardinalities[(j * 4) + 0] = key;
result.keysAndCardinalities[(j * 4) + 1] = key >> 8;
const card = newCardinality - 1;
result.keysAndCardinalities[(j * 4) + 2] = card;
result.keysAndCardinalities[(j * 4) + 3] = card >> 8;
const newContainer = new RoaringBitmapArray(
newCardinality,
new Uint8Array(newCardinality * 2),
);
let newContainerSlot = 0;
for (const containerValue of container.values()) {
if (containerValue !== value) {
newContainer.array[newContainerSlot] = value & 0xFF;
newContainerSlot += 1;
newContainer.array[newContainerSlot] = value >> 8;
newContainerSlot += 1;
}
}
result.containers.push(newContainer);
j += 1;
}
} else {
result.keysAndCardinalities[(j * 4) + 0] = this.keysAndCardinalities[(i * 4) + 0];
result.keysAndCardinalities[(j * 4) + 1] = this.keysAndCardinalities[(i * 4) + 1];
result.keysAndCardinalities[(j * 4) + 2] = this.keysAndCardinalities[(i * 4) + 2];
result.keysAndCardinalities[(j * 4) + 3] = this.keysAndCardinalities[(i * 4) + 3];
result.containers.push(this.containers[i]);
j += 1;
}
}
return result;
}
/**
* @param {number} key
* @returns {number}
*/
getContainerId(key) {
// Binary search algorithm copied from
// https://en.wikipedia.org/wiki/Binary_search#Procedure
//
// Format is required by specification to be sorted.
// Because keys are 16 bits and unique, length can't be
// bigger than 2**16, and because we have 32 bits of safe int,
// left + right can't overflow.
let left = 0;
let right = this.containers.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
const x = this.keysAndCardinalities[(mid * 4)] |
(this.keysAndCardinalities[(mid * 4) + 1] << 8);
if (x < key) {
left = mid + 1;
} else if (x > key) {
right = mid - 1;
} else {
return mid;
}
}
return -1;
}
* entries() {
const l = this.containers.length;
for (let i = 0; i < l; ++i) {
const key = this.keysAndCardinalities[i * 4] |
(this.keysAndCardinalities[(i * 4) + 1] << 8);
for (const value of this.containers[i].values()) {
yield (key << 16) | value;
}
}
}
/**
* @returns {number|null}
*/
first() {
for (const entry of this.entries()) {
return entry;
}
return null;
}
/**
* @returns {number}
*/
cardinality() {
let result = 0;
const l = this.containers.length;
for (let i = 0; i < l; ++i) {
const card = this.keysAndCardinalities[(i * 4) + 2] |
(this.keysAndCardinalities[(i * 4) + 3] << 8);
result += card + 1;
}
return result;
}
}
class RoaringBitmapRun {
/**
* @param {number} runcount
* @param {Uint8Array} array
*/
constructor(runcount, array) {
this.runcount = runcount;
this.array = array;
}
/** @param {number} value */
contains(value) {
// Binary search algorithm copied from
// https://en.wikipedia.org/wiki/Binary_search#Procedure
//
// Since runcount is stored as 16 bits, left + right
// can't overflow.
let left = 0;
let right = this.runcount - 1;
while (left <= right) {
const mid = (left + right) >> 1;
const i = mid * 4;
const start = this.array[i] | (this.array[i + 1] << 8);
const lenm1 = this.array[i + 2] | (this.array[i + 3] << 8);
if ((start + lenm1) < value) {
left = mid + 1;
} else if (start > value) {
right = mid - 1;
} else {
return true;
}
}
return false;
}
* values() {
let i = 0;
while (i < this.runcount) {
const start = this.array[i * 4] | (this.array[(i * 4) + 1] << 8);
const lenm1 = this.array[(i * 4) + 2] | (this.array[(i * 4) + 3] << 8);
let value = start;
let j = 0;
while (j <= lenm1) {
yield value;
value += 1;
j += 1;
}
i += 1;
}
}
}
class RoaringBitmapArray {
/**
* @param {number} cardinality
* @param {Uint8Array} array
*/
constructor(cardinality, array) {
this.cardinality = cardinality;
this.array = array;
}
/** @param {number} value */
contains(value) {
// Binary search algorithm copied from
// https://en.wikipedia.org/wiki/Binary_search#Procedure
//
// Since cardinality can't be higher than 4096, left + right
// cannot overflow.
let left = 0;
let right = this.cardinality - 1;
while (left <= right) {
const mid = (left + right) >> 1;
const i = mid * 2;
const x = this.array[i] | (this.array[i + 1] << 8);
if (x < value) {
left = mid + 1;
} else if (x > value) {
right = mid - 1;
} else {
return true;
}
}
return false;
}
/** @returns {Generator<number>} */
* values() {
let i = 0;
const l = this.cardinality * 2;
while (i < l) {
yield this.array[i] | (this.array[i + 1] << 8);
i += 2;
}
}
}
class RoaringBitmapBits {
/**
* @param {Uint8Array} array
*/
constructor(array) {
this.array = array;
}
/** @param {number} value */
contains(value) {
return !!(this.array[value >> 3] & (1 << (value & 7)));
}
* values() {
let i = 0;
const l = this.array.length << 3;
while (i < l) {
if (this.contains(i)) {
yield i;
}
i += 1;
}
}
}
const EMPTY_BITMAP = new RoaringBitmap(null, 0);
EMPTY_BITMAP.consumed_len_bytes = 0;
const EMPTY_BITMAP1 = new RoaringBitmap(null, 0);
EMPTY_BITMAP1.consumed_len_bytes = 1;
const EVERYTHING_BITMAP = new RoaringBitmap(null, 0);
/**
* A mapping from six byte nodeids to an arbitrary value.
* We don't just use `Map` because that requires double hashing.
* @template T
* @property {Uint8Array} keys
* @property {T[]} values
* @property {number} size
* @property {number} capacityClass
*/
class HashTable {
/**
* Construct an empty hash table.
*/
constructor() {
this.keys = EMPTY_UINT8;
/** @type {(T|undefined)[]} */
this.values = [];
this.size = 0;
this.capacityClass = 0;
}
/**
* @returns {Generator<[Uint8Array, T]>}
*/
* entries() {
const keys = this.keys;
const values = this.values;
const l = this.values.length;
for (let i = 0; i < l; i += 1) {
const value = values[i];
if (value !== undefined) {
yield [keys.subarray(i * 5, (i + 1) * 5), value];
}
}
}
/**
* Add a value to the hash table.
* @param {Uint8Array} key
* @param {T} value
*/
set(key, value) {
// 90 % load factor
if (this.size * 10 >= this.values.length * 9) {
const keys = this.keys;
const values = this.values;
const l = values.length;
this.capacityClass += 1;
const capacity = 1 << this.capacityClass;
this.keys = new Uint8Array(capacity * 5);
this.values = [];
for (let i = 0; i < capacity; i += 1) {
this.values.push(undefined);
}
this.size = 0;
for (let i = 0; i < l; i += 1) {
const oldValue = values[i];
if (oldValue !== undefined) {
this.setNoGrow(keys, i * 5, oldValue);
}
}
}
this.setNoGrow(key, 0, value);
}
/**
* @param {Uint8Array} key
* @param {number} start
* @param {T} value
*/
setNoGrow(key, start, value) {
const mask = ~(0xffffffff << this.capacityClass);
const keys = this.keys;
const values = this.values;
const l = 1 << this.capacityClass;
// because we know that our values are already hashed,
// just chop off the first byte
let slot = (
(key[start + 1] << 24) |
(key[start + 2] << 16) |
(key[start + 3] << 8) |
key[start + 4]
) & mask;
for (let distance = 0; distance < l; ) {
const j = slot * 5;
const otherValue = values[slot];
if (otherValue === undefined) {
values[slot] = value;
const keysStart = slot * 5;
keys[keysStart + 0] = key[start + 0];
keys[keysStart + 1] = key[start + 1];
keys[keysStart + 2] = key[start + 2];
keys[keysStart + 3] = key[start + 3];
keys[keysStart + 4] = key[start + 4];
this.size += 1;
break;
} else if (
key[start + 0] === keys[j + 0] &&
key[start + 1] === keys[j + 1] &&
key[start + 2] === keys[j + 2] &&
key[start + 3] === keys[j + 3] &&
key[start + 4] === keys[j + 4]
) {
values[slot] = value;
break;
} else {
const otherPreferredSlot = (
(keys[j + 1] << 24) | (keys[j + 2] << 16) |
(keys[j + 3] << 8) | keys[j + 4]
) & mask;
const otherDistance = otherPreferredSlot <= slot ?
slot - otherPreferredSlot :
(l - otherPreferredSlot) + slot;
if (distance > otherDistance) {
// if the other key is closer to its preferred slot than this one,
// then insert our node in its place and swap
//
// https://cglab.ca/~abeinges/blah/robinhood-part-1/
const otherKey = keys.slice(j, j + 5);
values[slot] = value;
value = otherValue;
keys[j + 0] = key[start + 0];
keys[j + 1] = key[start + 1];
keys[j + 2] = key[start + 2];
keys[j + 3] = key[start + 3];
keys[j + 4] = key[start + 4];
key = otherKey;
start = 0;
distance = otherDistance;
}
distance += 1;
slot = (slot + 1) & mask;
}
}
}
/**
* Retrieve a value
* @param {Uint8Array} key
* @returns {T|undefined}
*/
get(key) {
if (key.length !== 5) {
throw "invalid key";
}
return this.getWithOffsetKey(key, 0);
}
/**
* Retrieve a value
* @param {Uint8Array} key
* @param {number} start
* @returns {T|undefined}
*/
getWithOffsetKey(key, start) {
const mask = ~(0xffffffff << this.capacityClass);
const keys = this.keys;
const values = this.values;
const l = 1 << this.capacityClass;
// because we know that our values are already hashed,
// just chop off the lower four bytes
let slot = (
(key[start + 1] << 24) |
(key[start + 2] << 16) |
(key[start + 3] << 8) |
key[start + 4]
) & mask;
for (let distance = 0; distance < l; distance += 1) {
const j = slot * 5;
const value = values[slot];
if (value === undefined) {
break;
} else if (
key[start + 0] === keys[j + 0] &&
key[start + 1] === keys[j + 1] &&
key[start + 2] === keys[j + 2] &&
key[start + 3] === keys[j + 3] &&
key[start + 4] === keys[j + 4]
) {
return value;
} else {
const otherPreferredSlot = (
(keys[j + 1] << 24) | (keys[j + 2] << 16) |
(keys[j + 3] << 8) | keys[j + 4]
) & mask;
const otherDistance = otherPreferredSlot <= slot ?
slot - otherPreferredSlot :
(l - otherPreferredSlot) + slot;
if (distance > otherDistance) {
break;
}
}
slot = (slot + 1) & mask;
}
return undefined;
}
}
/*eslint-disable */
// ignore-tidy-linelength
/** <https://stackoverflow.com/questions/43122082/efficiently-count-the-number-of-bits-in-an-integer-in-javascript>
* @param {number} n
* @returns {number}
*/
function bitCount(n) {
n = (~~n) - ((n >> 1) & 0x55555555);
n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
return ((n + (n >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}
/*eslint-enable */
/**
* https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore%E2%80%93Horspool_algorithm
*/
class Uint8ArraySearchPattern {
/** @param {Uint8Array} needle */
constructor(needle) {
this.needle = needle;
this.skipTable = [];
const m = needle.length;
for (let i = 0; i < 256; i += 1) {
this.skipTable.push(m);
}
for (let i = 0; i < m - 1; i += 1) {
this.skipTable[needle[i]] = m - 1 - i;
}
}
/**
* @param {Uint8Array} haystack
* @returns {boolean}
*/
matches(haystack) {
const needle = this.needle;
const skipTable = this.skipTable;
const m = needle.length;
const n = haystack.length;
let skip = 0;
search: while (n - skip >= m) {
for (let i = m - 1; i >= 0; i -= 1) {
if (haystack[skip + i] !== needle[i]) {
skip += skipTable[haystack[skip + m - 1]];
continue search;
}
}
return true;
}
return false;
}
}
/**
* @param {stringdex.Hooks} hooks
* @returns {Promise<stringdex.Database>}
*/
function loadDatabase(hooks) {
/** @type {stringdex.Callbacks} */
const callbacks = {
rr_: function(data) {
const dataObj = JSON.parse(data);
for (const colName of Object.keys(dataObj)) {
if (Object.hasOwn(dataObj[colName], "N")) {
const counts = [];
const countsstring = dataObj[colName]["N"];
let i = 0;
const l = countsstring.length;
while (i < l) {
let n = 0;
let c = countsstring.charCodeAt(i);
while (c < 96) { // 96 = "`"
n = (n << 4) | (c & 0xF);
i += 1;
c = countsstring.charCodeAt(i);
}
n = (n << 4) | (c & 0xF);
counts.push(n);
i += 1;
}
registry.dataColumns.set(colName, new DataColumn(
counts,
makeUint8ArrayFromBase64(dataObj[colName]["H"]),
new RoaringBitmap(makeUint8ArrayFromBase64(dataObj[colName]["E"]), 0),
colName,
Object.hasOwn(dataObj[colName], "I") ?
makeSearchTreeFromBase64(dataObj[colName].I)[1] :
null,
));
}
}
const cb = registry.searchTreeRootCallback;
if (cb) {
cb(null, new Database(registry.searchTreeRoots, registry.dataColumns));
}
},
err_rr_: function(err) {
const cb = registry.searchTreeRootCallback;
if (cb) {
cb(err, null);
}
},
rd_: function(dataString) {
const l = dataString.length;
const data = new Uint8Array(l);
for (let i = 0; i < l; ++i) {
data[i] = dataString.charCodeAt(i);
}
loadColumnFromBytes(data);
},
err_rd_: function(filename, err) {
const nodeid = makeUint8ArrayFromHex(filename);
const cb = registry.dataColumnLoadPromiseCallbacks.get(nodeid);
if (cb) {
cb(err, null);
}
},
rb_: function(dataString64) {
loadColumnFromBytes(makeUint8ArrayFromBase64(dataString64));
},
err_rb_: function(filename, err) {
const nodeid = makeUint8ArrayFromHex(filename);
const cb = registry.dataColumnLoadPromiseCallbacks.get(nodeid);
if (cb) {
cb(err, null);
}
},
rn_: function(inputBase64) {
const [nodeid, tree] = makeSearchTreeFromBase64(inputBase64);
const cb = registry.searchTreeLoadPromiseCallbacks.get(nodeid);
if (cb) {
cb(null, tree);
registry.searchTreeLoadPromiseCallbacks.set(nodeid, null);
}
},
err_rn_: function(filename, err) {
const nodeid = makeUint8ArrayFromHex(filename);
const cb = registry.searchTreeLoadPromiseCallbacks.get(nodeid);
if (cb) {
cb(err, null);
}
},
};
/**
* @type {{
* searchTreeRoots: Map<string, SearchTree>;
* searchTreeLoadPromiseCallbacks: HashTable<(function(any, SearchTree?): any)|null>;
* searchTreePromises: HashTable<Promise<SearchTree>>;
* dataColumnLoadPromiseCallbacks: HashTable<function(any, Uint8Array[]?): any>;
* dataColumns: Map<string, DataColumn>;
* dataColumnsBuckets: HashTable<Promise<Uint8Array[]>>;
* searchTreeLoadByNodeID: function(Uint8Array): Promise<SearchTree>;
* searchTreeRootCallback?: function(any, Database?): any;
* dataLoadByNameAndHash: function(string, Uint8Array): Promise<Uint8Array[]>;
* }}
*/
const registry = {
searchTreeRoots: new Map(),
searchTreeLoadPromiseCallbacks: new HashTable(),
searchTreePromises: new HashTable(),
dataColumnLoadPromiseCallbacks: new HashTable(),
dataColumns: new Map(),
dataColumnsBuckets: new HashTable(),
searchTreeLoadByNodeID: function(nodeid) {
/** @type {Promise<SearchTree>} */
let newPromise;
if ((nodeid[0] & 0x80) !== 0) {
const isSuffixOnly = (nodeid[0] & 0x40) !== 0;
const isRun = (nodeid[0] & 0x20) !== 0;
const lengthOrData = nodeid[0] & 0x1F;
const id = (nodeid[1] << 24) | (nodeid[2] << 16) | (nodeid[3] << 8) | nodeid[4];
let bitmap;
if (isRun) {
bitmap = new RoaringBitmap(null);
bitmap.containers.push(new RoaringBitmapRun(
1,
Uint8Array.of(
id & 0xFF,
(id >> 8) & 0xFF,
lengthOrData,
0,
),
));
bitmap.keysAndCardinalities = Uint8Array.of(
(id >> 16) & 0xff,
(id >> 24) & 0xff,
lengthOrData,
0,
);
} else {
bitmap = RoaringBitmap.makeSingleton(id);
}
let tree;
if (isSuffixOnly) {
tree = new SuffixSearchTree(
EMPTY_SEARCH_TREE_BRANCHES,
isRun ? 0 : (lengthOrData + 1),
bitmap,
);
} else {
tree = new PrefixSearchTree(
EMPTY_SEARCH_TREE_BRANCHES,
EMPTY_SEARCH_TREE_BRANCHES,
isRun ? EMPTY_UINT8 : Uint8Array.of(LONG_ALPHABET.chars[lengthOrData]),
bitmap,
EMPTY_BITMAP,
);
}
newPromise = Promise.resolve(tree);
} else {
const existingPromise = registry.searchTreePromises.get(nodeid);
if (existingPromise) {
return existingPromise;
}
const hashHex = makeHexFromUint8Array(nodeid);
newPromise = new Promise((resolve, reject) => {
const cb = registry.searchTreeLoadPromiseCallbacks.get(nodeid);
if (cb) {
registry.searchTreeLoadPromiseCallbacks.set(nodeid, (err, data) => {
cb(err, data);
if (data) {
resolve(data);
} else {
reject(err);
}
});
} else {
registry.searchTreeLoadPromiseCallbacks.set(nodeid, (err, data) => {
if (data) {
resolve(data);
} else {
reject(err);
}
});
hooks.loadTreeByHash(hashHex);
}
});
registry.searchTreePromises.set(nodeid, newPromise);
}
return newPromise;
},
dataLoadByNameAndHash: function(name, hash) {
const existingBucket = registry.dataColumnsBuckets.get(hash);
if (existingBucket) {
return existingBucket;
}
const hashHex = makeHexFromUint8Array(hash);
/** @type {Promise<Uint8Array[]>} */
const newBucket = new Promise((resolve, reject) => {
const cb = registry.dataColumnLoadPromiseCallbacks.get(hash);
if (cb) {
registry.dataColumnLoadPromiseCallbacks.set(hash, (err, data) => {
cb(err, data);
if (data) {
resolve(data);
} else {
reject(err);
}
});
} else {
registry.dataColumnLoadPromiseCallbacks.set(hash, (err, data) => {
if (data) {
resolve(data);
} else {
reject(err);
}
});
hooks.loadDataByNameAndHash(name, hashHex);
}
});
registry.dataColumnsBuckets.set(hash, newBucket);
return newBucket;
},
};
/**
* The set of child subtrees.
* @template ST
* @type {{
* nodeids: Uint8Array,
* subtrees: Array<Promise<ST>|null>,
* }}
*/
class SearchTreeBranches {
/**
* Construct the subtree list with `length` nulls
* @param {number} length
* @param {Uint8Array} nodeids
*/
constructor(length, nodeids) {
this.nodeids = nodeids;
this.subtrees = [];
for (let i = 0; i < length; ++i) {
this.subtrees.push(null);
}
}
/**
* @param {number} i
* @returns {Uint8Array}
*/
getNodeID(i) {
return new Uint8Array(
this.nodeids.buffer,
this.nodeids.byteOffset + (i * 5),
5,
);
}
// https://github.com/microsoft/TypeScript/issues/17227
/** @returns {Generator<[number, Promise<ST>|null]>} */
entries() {
throw new Error();
}
/**
* @param {number} _k
* @returns {number}
*/
getIndex(_k) {
throw new Error();
}
/**
* @param {number} _i
* @returns {number}
*/
getKey(_i) {
throw new Error();
}
/**
* @returns {Uint8Array}
*/
getKeys() {
throw new Error();
}
}
/**
* A sorted array of search tree branches.
*
* @template ST
* @extends SearchTreeBranches<ST>
* @type {{
* keys: Uint8Array,
* nodeids: Uint8Array,
* subtrees: Array<Promise<ST>|null>,
* }}
*/
class SearchTreeBranchesArray extends SearchTreeBranches {
/**
* @param {Uint8Array} keys
* @param {Uint8Array} nodeids
*/
constructor(keys, nodeids) {
super(keys.length, nodeids);
this.keys = keys;
let i = 1;
while (i < this.keys.length) {
if (this.keys[i - 1] >= this.keys[i]) {
throw new Error("HERE");
}
i += 1;
}
}
/** @returns {Generator<[number, Promise<ST>|null]>} */
* entries() {
let i = 0;
const l = this.keys.length;
while (i < l) {
yield [this.keys[i], this.subtrees[i]];
i += 1;
}
}
/**
* @param {number} k
* @returns {number}
*/
getIndex(k) {
// Since length can't be bigger than 256,
// left + right can't overflow.
let left = 0;
let right = this.keys.length - 1;
while (left <= right) {
const mid = (left + right) >> 1;
if (this.keys[mid] < k) {
left = mid + 1;
} else if (this.keys[mid] > k) {
right = mid - 1;
} else {
return mid;
}
}
return -1;
}
/**
* @param {number} i
* @returns {number}
*/
getKey(i) {
return this.keys[i];
}
/**
* @returns {Uint8Array}
*/
getKeys() {
return this.keys;
}
}
const EMPTY_SEARCH_TREE_BRANCHES = new SearchTreeBranchesArray(
EMPTY_UINT8,
EMPTY_UINT8,
);
class Alphabet {
constructor() {
/** @type {number[]} */
this.chars = [];
/** @type {number} */
this.len = 0;
/** @type {number} */
this.bytes = 0;
/** @type {number} */
this.flag = 0;
/** @type {number} */
this.bitwidth = 0;
}
/**
* @param {number} c
* @returns {boolean}
*/
contains(c) {
return this.chars.indexOf(c) !== -1;
}
/**
* @param {number} c
* @returns {number}
*/
index(c) {
return this.chars.indexOf(c);
}
}
/** @type {Alphabet} */
const VOWELONLY_ALPHABITMAP = Object.assign(
new Alphabet(),
{
chars: [0x61, 0x65, 0x69, 0x6f, 0x75],
len: 5,
bytes: 0,
flag: 0x80,
},
);
/** @type {Alphabet} */
const CONSONANTSONLY_ALPHABET = Object.assign(
new Alphabet(),
{
chars: [],
len: 21,
bytes: 2,
flag: 0xc0,
},
);
for (let i = 0x61; i <= 0x7A; ++i) {
if (i === 0x61 || i === 0x65 || i === 0x69 || i === 0x6f || i === 0x75) {
// 21 bits, 26 letters, so skip aeiou
continue;
}
CONSONANTSONLY_ALPHABET.chars.push(i);
}
/** @type {Alphabet} */
const HEX_ALPHABET = Object.assign(
new Alphabet(),
{
chars: [],
len: 16,
bytes: 2,
flag: 0xfc,
},
);
for (let i = 0x30; i <= 0x39; ++i) {
HEX_ALPHABET.chars.push(i);
}
for (let i = 0x61; i <= 0x66; ++i) {
HEX_ALPHABET.chars.push(i);
}
/** @type {Alphabet} */
const SHORT_ALPHABET = Object.assign(
new Alphabet(),
{
chars: [],
len: 24,
bytes: 3,
flag: 0xfd,
},
);
for (let i = 0x61; i <= 0x7A; ++i) {
if (i === 0x76 || i === 0x71) {
// 24 entries, 26 letters, so we skip q and v
continue;
}
SHORT_ALPHABET.chars.push(i);
}
/** @type {Alphabet} */
const LONG_ALPHABET = Object.assign(
new Alphabet(),
{
chars: [0x31, 0x32, 0x33, 0x34, 0x35, 0x36],
len: 32,
bytes: 4,
flag: 0xfe,
},
);
for (let i = 0x61; i <= 0x7A; ++i) {
LONG_ALPHABET.chars.push(i);
}
/** @type {Alphabet} */
const ASCII_ALPHABET = Object.assign(
new Alphabet(),
{
chars: [],
len: 128,
bytes: 16,
flag: 0xf0,
/**
* @param {number} c
* @returns {boolean}
*/
contains(c) {
return c <= 0x7f;
},
/**
* @param {number} c
* @returns {number}
*/
index(c) {
return c;
},
},
);
for (let i = 0x00; i <= 0x7f; ++i) {
ASCII_ALPHABET.chars.push(i);
}
/** @type {Alphabet} */
const RAWBYTE_ALPHABET = Object.assign(
new Alphabet(),
{
chars: [],
len: 256,
bytes: 32,
flag: 0xff,
/**
* @param {number} _c
* @returns {boolean}
*/
contains(_c) {
return true;
},
/**
* @param {number} c
* @returns {number}
*/
index(c) {
return c;
},
},
);
for (let i = 0x00; i <= 0xff; ++i) {
RAWBYTE_ALPHABET.chars.push(i);
}
/**
* Parse an alphabet and buffer where the flag is right at the beginning.
* @param {number} start
* @param {Uint8Array} buf
* @returns {{"alphabet": Alphabet, "consumed_len_bytes": number, "len": number}?}
*/
Alphabet.parse = function(start, buf) {
const flag = buf[start];
const parsed = Alphabet.parseFlag(flag, start + 1, buf);
if (!parsed) {
return null;
}
parsed.consumed_len_bytes += 1;
return parsed;
};
/**
* Parse an alphabet and buffer where the flag is not at the beginning.
* @param {number} flag
* @param {number} i
* @param {Uint8Array} buf
* @returns {{"alphabet": Alphabet, "consumed_len_bytes": number, "len": number}?}
*/
Alphabet.parseFlag = function(flag, i, buf) {
if (flag <= 0x80) {
return null;
}
const alphabet = flag === RAWBYTE_ALPHABET.flag ? RAWBYTE_ALPHABET : (
flag === ASCII_ALPHABET.flag ? ASCII_ALPHABET : (
flag === LONG_ALPHABET.flag ? LONG_ALPHABET : (
flag === SHORT_ALPHABET.flag ? SHORT_ALPHABET : (
flag === HEX_ALPHABET.flag ? HEX_ALPHABET : (
flag >= CONSONANTSONLY_ALPHABET.flag ? CONSONANTSONLY_ALPHABET : VOWELONLY_ALPHABITMAP
)))));
let len = alphabet === CONSONANTSONLY_ALPHABET || alphabet === VOWELONLY_ALPHABITMAP ?
bitCount(flag & 0x1f) : 0;
for (let ix = 0; ix < alphabet.bytes; ++ix) {
len += bitCount(buf[i]);
i += 1;
}
return {alphabet, consumed_len_bytes: alphabet.bytes, len};
};
/**
* @template ST
* @extends SearchTreeBranches<ST>
*/
class SearchTreeBranchesAlphaBitmap extends SearchTreeBranches {
/**
* @param {Alphabet} alphabet
* @param {Uint8Array} buffer
* @param {Uint8Array} nodeids
*/
constructor(alphabet, buffer, nodeids) {
let bitmap;
if (alphabet === VOWELONLY_ALPHABITMAP) {
bitmap = new Uint8Array(1);
bitmap[0] = buffer[0] & 0x1f;
} else if (alphabet === CONSONANTSONLY_ALPHABET) {
bitmap = new Uint8Array(3);
bitmap[0] = buffer[1];
bitmap[1] = buffer[2];
bitmap[2] = buffer[0] & 0x1f;
} else {
bitmap = buffer.subarray(1);
}
let cardinality = 0;
for (let i = 0; i < bitmap.length; ++i) {
cardinality += bitCount(bitmap[i]);
}
super(cardinality, nodeids);
this.bitmap = bitmap;
this.alphabet = alphabet;
}
/**
* Yields [character, SearchTree] pairs.
* @returns {Generator<[number, Promise<ST>|null]>}
*/
* entries() {
let i = 0;
let j = 0;
while (i < this.alphabet.len) {
if (this.bitmap[i >> 3] & (1 << (i & 0x07))) {
yield [this.alphabet.chars[i], this.subtrees[j]];
j += 1;
}
i += 1;
}
}
/**
* Given a character, returns the numbered index of the search
* tree, or -1 if there isn't one.
* @param {number} c
* @returns {number}
*/
getIndex(c) {
//return this.getKeys().indexOf(c);
if (!this.alphabet.contains(c)) {
return -1;
}
const k = this.alphabet.index(c);
if (this.bitmap[k >> 3] & (1 << (k & 0x07))) {
let result = bitCount(~(0xff << (k & 0x07)) & this.bitmap[k >> 3]);
for (let ix = 0; ix < (k >> 3); ++ix) {
result += bitCount(this.bitmap[ix]);
}
return result;
} else {
return -1;
}
}
/**
* Given the numbered index of a search tree, returns the key.
* This is the exact opposite of getIndex().
* @param {number} branch_index
* @returns {number}
*/
getKey(branch_index) {
return this.getKeys()[branch_index];
}
/**
* Returns a list of one-byte keys.
* @returns {Uint8Array}
*/
getKeys() {
let length = 0;
for (let i = 0; i < this.bitmap.length; ++i) {
length += bitCount(this.bitmap[i]);
}
const result = new Uint8Array(length);
let result_index = 0;
for (let ix = 0; ix < this.alphabet.len; ++ix) {
if (this.bitmap[ix >> 3] & (1 << (ix & 0x07))) {
result[result_index] = this.alphabet.chars[ix];
result_index += 1;
}
}
return result;
}
}
/**
* @typedef {PrefixSearchTree|SuffixSearchTree|InlineNeighborsTree} SearchTree
* @typedef {PrefixTrie|SuffixTrie} Trie
*/
/**
* An interleaved [prefix] and [suffix tree],
* used for name-based search.
*
* This data structure is used to drive prefix matches,
* such as matching the query "link" to `LinkedList`,
* and Lev-distance matches, such as matching the
* query "hahsmap" to `HashMap`.
*
* [prefix tree]: https://en.wikipedia.org/wiki/Prefix_tree
* [suffix tree]: https://en.wikipedia.org/wiki/Suffix_tree
*
* branches
* : A sorted-array map of subtrees.
*
* data
* : The substring represented by this node. The root node
* is always empty.
*
* leaves_suffix
* : The IDs of every entry that matches. Levenshtein matches
* won't include these.
*
* leaves_whole
* : The IDs of every entry that matches exactly. Levenshtein matches
* will include these.
*
* @type {{
* might_have_prefix_branches: SearchTreeBranches<SearchTree>,
* branches: SearchTreeBranches<SearchTree>,
* data: Uint8Array,
* leaves_suffix: RoaringBitmap,
* leaves_whole: RoaringBitmap,
* }}
*/
class PrefixSearchTree {
/**
* @param {SearchTreeBranches<SearchTree>} branches
* @param {SearchTreeBranches<SearchTree>} might_have_prefix_branches
* @param {Uint8Array} data
* @param {RoaringBitmap} leaves_whole
* @param {RoaringBitmap} leaves_suffix
*/
constructor(
branches,
might_have_prefix_branches,
data,
leaves_whole,
leaves_suffix,
) {
this.might_have_prefix_branches = might_have_prefix_branches;
this.branches = branches;
this.data = data;
this.leaves_suffix = leaves_suffix;
this.leaves_whole = leaves_whole;
}
/**
* Returns the Trie for the root node.
*
* A Trie pointer refers to a single node in a logical decompressed search tree
* (the real search tree is compressed).
*
* @param {DataColumn} dataColumn
* @param {Uint8ArraySearchPattern} searchPattern
* @return {PrefixTrie}
*/
trie(dataColumn, searchPattern) {
return new PrefixTrie(this, 0, dataColumn, searchPattern);
}
/**
* Return the trie representing `name`
* @param {Uint8Array|string} name
* @param {DataColumn} dataColumn
* @returns {Promise<Trie?>}
*/
async search(name, dataColumn) {
if (typeof name === "string") {
const utf8encoder = new TextEncoder();
name = utf8encoder.encode(name);
}
const searchPattern = new Uint8ArraySearchPattern(name);
/** @type {Trie} */
let trie = this.trie(dataColumn, searchPattern);
for (const datum of name) {
// code point definitely exists
/** @type {Promise<Trie>?} */
const newTrie = trie.child(datum);
if (newTrie) {
trie = await newTrie;
} else {
return null;
}
}
return trie;
}
/**
* @param {Uint8Array|string} name
* @param {DataColumn} dataColumn
* @returns {AsyncGenerator<Trie>}
*/
async* searchLev(name, dataColumn) {
if (typeof name === "string") {
const utf8encoder = new TextEncoder();
name = utf8encoder.encode(name);
}
const w = name.length;
if (w < 3) {
const trie = await this.search(name, dataColumn);
if (trie !== null) {
yield trie;
}
return;
}
const searchPattern = new Uint8ArraySearchPattern(name);
const levParams = w >= 6 ?
new Lev2TParametricDescription(w) :
new Lev1TParametricDescription(w);
/** @type {Array<[Promise<Trie>, number]>} */
const stack = [[Promise.resolve(this.trie(dataColumn, searchPattern)), 0]];
const n = levParams.n;
while (stack.length !== 0) {
// It's not empty
/** @type {[Promise<Trie>, number]} */
//@ts-expect-error
const [triePromise, levState] = stack.pop();
const trie = await triePromise;
for (const byte of trie.keysExcludeSuffixOnly()) {
const levPos = levParams.getPosition(levState);
const vector = levParams.getVector(
name,
byte,
levPos,
Math.min(w, levPos + (2 * n) + 1),
);
const newLevState = levParams.transition(
levState,
levPos,
vector,
);
if (newLevState >= 0) {
const child = trie.child(byte);
if (child) {
stack.push([child, newLevState]);
if (levParams.isAccept(newLevState)) {
yield child;
}
}
}
}
}
}
/** @returns {RoaringBitmap} */
getCurrentLeaves() {
return this.leaves_whole.union(this.leaves_suffix);
}
}
/**
* A representation of a set of strings in the search index,
* as a subset of the entire tree.
*/
class PrefixTrie {
/**
* @param {PrefixSearchTree} tree
* @param {number} offset
* @param {DataColumn} dataColumn
* @param {Uint8ArraySearchPattern} searchPattern
*/
constructor(tree, offset, dataColumn, searchPattern) {
this.tree = tree;
this.offset = offset;
this.dataColumn = dataColumn;
this.searchPattern = searchPattern;
}
/**
* All exact matches for the string represented by this node.
* @returns {RoaringBitmap}
*/
matches() {
if (this.offset === this.tree.data.length) {
return this.tree.leaves_whole;
} else {
return EMPTY_BITMAP;
}
}
/**
* All matches for strings that contain the string represented by this node.
* @returns {AsyncGenerator<RoaringBitmap>}
*/
async* substringMatches() {
/** @type {Promise<SearchTree>[]} */
let layer = [Promise.resolve(this.tree)];
while (layer.length) {
const current_layer = layer;
layer = [];
for await (const tree of current_layer) {
/** @type {number[]?} */
let rejected = null;
let leaves = tree.getCurrentLeaves();
for (const leaf of leaves.entries()) {
const haystack = await this.dataColumn.at(leaf);
if (haystack === undefined || !this.searchPattern.matches(haystack)) {
if (!rejected) {
rejected = [];
}
rejected.push(leaf);
}
}
if (rejected) {
if (leaves.cardinality() !== rejected.length) {
for (const rej of rejected) {
leaves = leaves.remove(rej);
}
yield leaves;
}
} else {
yield leaves;
}
}
/** @type {HashTable<[number, PrefixSearchTree|SuffixSearchTree][]>} */
const subnodes = new HashTable();
for await (const nodeEncoded of current_layer) {
const node = nodeEncoded instanceof InlineNeighborsTree ?
nodeEncoded.decode() :
nodeEncoded;
const branches = node.branches;
const l = branches.subtrees.length;
for (let i = 0; i < l; ++i) {
const subtree = branches.subtrees[i];
if (subtree) {
layer.push(subtree);
} else if (subtree === null) {
const byte = branches.getKey(i);
const newnode = branches.getNodeID(i);
if (!newnode) {
throw new Error(`malformed tree; no node for key ${byte}`);
} else {
let subnode_list = subnodes.get(newnode);
if (!subnode_list) {
subnode_list = [[byte, node]];
subnodes.set(newnode, subnode_list);
} else {
subnode_list.push([byte, node]);
}
}
} else {
throw new Error(`malformed tree; index ${i} does not exist`);
}
}
}
for (const [newnode, subnode_list] of subnodes.entries()) {
const res = registry.searchTreeLoadByNodeID(newnode);
for (const [byte, node] of subnode_list) {
const branches = node.branches;
const i = branches.getIndex(byte);
branches.subtrees[i] = res;
if (node instanceof PrefixSearchTree) {
const might_have_prefix_branches = node.might_have_prefix_branches;
const mhpI = might_have_prefix_branches.getIndex(byte);
if (mhpI !== -1) {
might_have_prefix_branches.subtrees[mhpI] = res;
}
}
}
layer.push(res);
}
}
}
/**
* All matches for strings that start with the string represented by this node.
* @returns {AsyncGenerator<RoaringBitmap>}
*/
async* prefixMatches() {
/** @type {{node: Promise<SearchTree>, len: number}[]} */
let layer = [{node: Promise.resolve(this.tree), len: 0}];
// https://en.wikipedia.org/wiki/Heap_(data_structure)#Implementation_using_arrays
/** @type {{bitmap: RoaringBitmap, length: number}[]} */
const backlog = [];
while (layer.length !== 0 || backlog.length !== 0) {
const current_layer = layer;
layer = [];
let minLength = null;
// push every entry in the current layer into the backlog,
// a min-heap of result entries
// we then yield the smallest ones (can't yield bigger ones
// if we want to do them in order)
for (const {node, len} of current_layer) {
const treeEncoded = await node;
const tree = treeEncoded instanceof InlineNeighborsTree ?
treeEncoded.decode() :
treeEncoded;
if (!(tree instanceof PrefixSearchTree)) {
continue;
}
const length = len + tree.data.length;
if (minLength === null || length < minLength) {
minLength = length;
}
let backlogSlot = backlog.length;
backlog.push({bitmap: tree.leaves_whole, length});
while (backlogSlot > 0 &&
backlog[backlogSlot].length < backlog[(backlogSlot - 1) >> 1].length
) {
const parentSlot = (backlogSlot - 1) >> 1;
const parent = backlog[parentSlot];
backlog[parentSlot] = backlog[backlogSlot];
backlog[backlogSlot] = parent;
backlogSlot = parentSlot;
}
}
// yield nodes in length order, smallest one first
// we know that, whatever the smallest item is
// every child will be bigger than that
while (backlog.length !== 0) {
const backlogEntry = backlog[0];
if (minLength !== null && backlogEntry.length > minLength) {
break;
}
if (!backlogEntry.bitmap.isEmpty()) {
yield backlogEntry.bitmap;
}
backlog[0] = backlog[backlog.length - 1];
backlog.length -= 1;
let backlogSlot = 0;
const backlogLength = backlog.length;
while (backlogSlot < backlogLength) {
const leftSlot = (backlogSlot << 1) + 1;
const rightSlot = (backlogSlot << 1) + 2;
let smallest = backlogSlot;
if (leftSlot < backlogLength &&
backlog[leftSlot].length < backlog[smallest].length
) {
smallest = leftSlot;
}
if (rightSlot < backlogLength &&
backlog[rightSlot].length < backlog[smallest].length
) {
smallest = rightSlot;
}
if (smallest === backlogSlot) {
break;
} else {
const tmp = backlog[backlogSlot];
backlog[backlogSlot] = backlog[smallest];
backlog[smallest] = tmp;
backlogSlot = smallest;
}
}
}
// if we still have more subtrees to walk, then keep going
/** @type {HashTable<{byte: number, tree: PrefixSearchTree, len: number}[]>} */
const subnodes = new HashTable();
for await (const {node, len} of current_layer) {
const treeEncoded = await node;
const tree = treeEncoded instanceof InlineNeighborsTree ?
treeEncoded.decode() :
treeEncoded;
if (!(tree instanceof PrefixSearchTree)) {
continue;
}
const length = len + tree.data.length;
const mhp_branches = tree.might_have_prefix_branches;
const l = mhp_branches.subtrees.length;
for (let i = 0; i < l; ++i) {
const len = length + 1;
const subtree = mhp_branches.subtrees[i];
if (subtree) {
layer.push({node: subtree, len});
} else if (subtree === null) {
const byte = mhp_branches.getKey(i);
const newnode = mhp_branches.getNodeID(i);
if (!newnode) {
throw new Error(`malformed tree; no node for key ${byte}`);
} else {
let subnode_list = subnodes.get(newnode);
if (!subnode_list) {
subnode_list = [{byte, tree, len}];
subnodes.set(newnode, subnode_list);
} else {
subnode_list.push({byte, tree, len});
}
}
}
}
}
for (const [newnode, subnode_list] of subnodes.entries()) {
const res = registry.searchTreeLoadByNodeID(newnode);
let len = Number.MAX_SAFE_INTEGER;
for (const {byte, tree, len: subtreelen} of subnode_list) {
if (subtreelen < len) {
len = subtreelen;
}
const mhp_branches = tree.might_have_prefix_branches;
const i = mhp_branches.getIndex(byte);
mhp_branches.subtrees[i] = res;
const branches = tree.branches;
const bi = branches.getIndex(byte);
branches.subtrees[bi] = res;
}
layer.push({node: res, len});
}
}
}
/**
* Returns all keys that are children of this node.
* @returns {Uint8Array}
*/
keys() {
const data = this.tree.data;
if (this.offset === data.length) {
return this.tree.branches.getKeys();
} else {
return Uint8Array.of(data[this.offset]);
}
}
/**
* Returns all nodes that are direct children of this node.
* @returns {[number, Promise<Trie>][]}
*/
children() {
const data = this.tree.data;
if (this.offset === data.length) {
/** @type {[number, Promise<Trie>][]} */
const nodes = [];
let i = 0;
for (const [k, v] of this.tree.branches.entries()) {
/** @type {Promise<SearchTree>} */
let node;
if (v) {
node = v;
} else {
const newnode = this.tree.branches.getNodeID(i);
if (!newnode) {
throw new Error(`malformed tree; no hash for key ${k}: ${newnode} \
${this.tree.branches.nodeids} ${this.tree.branches.getKeys()}`);
}
node = registry.searchTreeLoadByNodeID(newnode);
this.tree.branches.subtrees[i] = node;
const mhpI = this.tree.might_have_prefix_branches.getIndex(k);
if (mhpI !== -1) {
this.tree.might_have_prefix_branches.subtrees[mhpI] = node;
}
}
nodes.push([k, node.then(node => {
return node.trie(this.dataColumn, this.searchPattern);
})]);
i += 1;
}
return nodes;
} else {
/** @type {number} */
const codePoint = data[this.offset];
const trie = new PrefixTrie(
this.tree,
this.offset + 1,
this.dataColumn,
this.searchPattern,
);
return [[codePoint, Promise.resolve(trie)]];
}
}
/**
* Returns all keys that are children of this node.
* @returns {Uint8Array}
*/
keysExcludeSuffixOnly() {
const data = this.tree.data;
if (this.offset === data.length) {
return this.tree.might_have_prefix_branches.getKeys();
} else {
return Uint8Array.of(data[this.offset]);
}
}
/**
* Returns all nodes that are direct children of this node.
* @returns {[number, Promise<Trie>][]}
*/
childrenExcludeSuffixOnly() {
const data = this.tree.data;
if (this.offset === data.length) {
/** @type {[number, Promise<Trie>][]} */
const nodes = [];
let i = 0;
for (const [k, v] of this.tree.might_have_prefix_branches.entries()) {
/** @type {Promise<SearchTree>} */
let node;
if (v) {
node = v;
} else {
const newnode = this.tree.might_have_prefix_branches.getNodeID(i);
if (!newnode) {
throw new Error(`malformed tree; no node for key ${k}`);
}
node = registry.searchTreeLoadByNodeID(newnode);
this.tree.might_have_prefix_branches.subtrees[i] = node;
this.tree.branches.subtrees[this.tree.branches.getIndex(k)] = node;
}
nodes.push([k, node.then(node => {
return node.trie(this.dataColumn, this.searchPattern);
})]);
i += 1;
}
return nodes;
} else {
/** @type {number} */
const codePoint = data[this.offset];
const trie = new PrefixTrie(
this.tree,
this.offset + 1,
this.dataColumn,
this.searchPattern,
);
return [[codePoint, Promise.resolve(trie)]];
}
}
/**
* Returns a single node that is a direct child of this node.
* @param {number} byte
* @returns {Promise<Trie>?}
*/
child(byte) {
if (this.offset === this.tree.data.length) {
const i = this.tree.branches.getIndex(byte);
if (i !== -1) {
let branch = this.tree.branches.subtrees[i];
if (branch === null) {
const newnode = this.tree.branches.getNodeID(i);
if (!newnode) {
throw new Error(`malformed tree; no node for key ${byte}`);
}
branch = registry.searchTreeLoadByNodeID(newnode);
this.tree.branches.subtrees[i] = branch;
const mhpI = this.tree.might_have_prefix_branches.getIndex(byte);
if (mhpI !== -1) {
this.tree.might_have_prefix_branches.subtrees[mhpI] = branch;
}
}
return branch.then(branch => branch.trie(this.dataColumn, this.searchPattern));
}
} else if (this.tree.data[this.offset] === byte) {
return Promise.resolve(new PrefixTrie(
this.tree,
this.offset + 1,
this.dataColumn,
this.searchPattern,
));
}
return null;
}
}
/**
* A [suffix tree], used for name-based search.
*
* This data structure is used to drive substring matches,
* such as matching the query "inked" to `LinkedList`.
*
* [suffix tree]: https://en.wikipedia.org/wiki/Suffix_tree
*
* Suffix trees do not actually carry the intermediate data
* between branches, so, in order to validate the results,
* they must go through a filtering step at the end.
* Suffix trees also cannot match lev and exact matches,
* so those just return empty sets.
*
* branches
* : A sorted-array map of subtrees.
*
* dataLen
* : The length of the substring used by this node.
*
* leaves_suffix
* : The IDs of every entry that matches. Levenshtein matches
* won't include these.
*
* @type {{
* branches: SearchTreeBranches<SearchTree>,
* dataLen: number,
* leaves_suffix: RoaringBitmap,
* }}
*/
class SuffixSearchTree {
/**
* @param {SearchTreeBranches<SearchTree>} branches
* @param {number} dataLen
* @param {RoaringBitmap} leaves_suffix
*/
constructor(
branches,
dataLen,
leaves_suffix,
) {
this.branches = branches;
this.dataLen = dataLen;
this.leaves_suffix = leaves_suffix;
}
/**
* Returns the Trie for the root node.
*
* A Trie pointer refers to a single node in a logical decompressed search tree
* (the real search tree is compressed).
*
* @param {DataColumn} dataColumn
* @param {Uint8ArraySearchPattern} searchPattern
* @return {Trie}
*/
trie(dataColumn, searchPattern) {
return new SuffixTrie(this, 0, dataColumn, searchPattern);
}
/**
* Return the trie representing `name`
* @param {Uint8Array|string} name
* @param {DataColumn} dataColumn
* @returns {Promise<Trie?>}
*/
async search(name, dataColumn) {
if (typeof name === "string") {
const utf8encoder = new TextEncoder();
name = utf8encoder.encode(name);
}
const searchPattern = new Uint8ArraySearchPattern(name);
let trie = this.trie(dataColumn, searchPattern);
for (const datum of name) {
// code point definitely exists
const newTrie = trie.child(datum);
if (newTrie) {
trie = await newTrie;
} else {
return null;
}
}
return trie;
}
/**
* @param {Uint8Array|string} _name
* @param {DataColumn} _dataColumn
* @returns {AsyncGenerator<Trie>}
*/
async* searchLev(_name, _dataColumn) {
// this function only returns whole-string matches,
// which pure-suffix nodes don't have, so is
// intentionally blank
}
/** @returns {RoaringBitmap} */
getCurrentLeaves() {
return this.leaves_suffix;
}
}
/**
* A representation of a set of strings in the search index,
* as a subset of the entire tree (suffix-only).
*/
class SuffixTrie {
/**
* @param {SuffixSearchTree} tree
* @param {number} offset
* @param {DataColumn} dataColumn
* @param {Uint8ArraySearchPattern} searchPattern
*/
constructor(tree, offset, dataColumn, searchPattern) {
this.tree = tree;
this.offset = offset;
this.dataColumn = dataColumn;
this.searchPattern = searchPattern;
}
/**
* All exact matches for the string represented by this node.
* Since pure-suffix nodes have no exactly-matching children,
* this function returns the empty bitmap.
* @returns {RoaringBitmap}
*/
matches() {
return EMPTY_BITMAP;
}
/**
* All matches for strings that contain the string represented by this node.
* @returns {AsyncGenerator<RoaringBitmap>}
*/
async* substringMatches() {
/** @type {Promise<SearchTree>[]} */
let layer = [Promise.resolve(this.tree)];
while (layer.length) {
const current_layer = layer;
layer = [];
for await (const tree of current_layer) {
/** @type {number[]?} */
let rejected = null;
let leaves = tree.getCurrentLeaves();
for (const leaf of leaves.entries()) {
const haystack = await this.dataColumn.at(leaf);
if (haystack === undefined || !this.searchPattern.matches(haystack)) {
if (!rejected) {
rejected = [];
}
rejected.push(leaf);
}
}
if (rejected) {
if (leaves.cardinality() !== rejected.length) {
for (const rej of rejected) {
leaves = leaves.remove(rej);
}
yield leaves;
}
} else {
yield leaves;
}
}
/** @type {HashTable<[number, PrefixSearchTree|SuffixSearchTree][]>} */
const subnodes = new HashTable();
for await (const nodeEncoded of current_layer) {
const node = nodeEncoded instanceof InlineNeighborsTree ?
nodeEncoded.decode() :
nodeEncoded;
const branches = node.branches;
const l = branches.subtrees.length;
for (let i = 0; i < l; ++i) {
const subtree = branches.subtrees[i];
if (subtree) {
layer.push(subtree);
} else if (subtree === null) {
const newnode = branches.getNodeID(i);
if (!newnode) {
throw new Error(`malformed tree; no node for index ${i}`);
} else {
let subnode_list = subnodes.get(newnode);
if (!subnode_list) {
subnode_list = [[i, node]];
subnodes.set(newnode, subnode_list);
} else {
subnode_list.push([i, node]);
}
}
} else {
throw new Error(`malformed tree; index ${i} does not exist`);
}
}
}
for (const [newnode, subnode_list] of subnodes.entries()) {
const res = registry.searchTreeLoadByNodeID(newnode);
for (const [i, node] of subnode_list) {
const branches = node.branches;
branches.subtrees[i] = res;
}
layer.push(res);
}
}
}
/**
* All matches for strings that start with the string represented by this node.
* Since this is a pure-suffix node, there aren't any.
* @returns {AsyncGenerator<RoaringBitmap>}
*/
async* prefixMatches() {
// this function only returns prefix matches,
// which pure-suffix nodes don't have, so is
// intentionally blank
}
/**
* Returns all keys that are children of this node.
* @returns {Uint8Array}
*/
keysExcludeSuffixOnly() {
return EMPTY_UINT8;
}
/**
* Returns all nodes that are direct children of this node.
* @returns {[number, Promise<Trie>][]}
*/
childrenExcludeSuffixOnly() {
return [];
}
/**
* Returns a single node that is a direct child of this node.
* @param {number} byte
* @returns {Promise<Trie>?}
*/
child(byte) {
if (this.offset === this.tree.dataLen) {
const i = this.tree.branches.getIndex(byte);
if (i !== -1) {
/** @type {Promise<SearchTree>?} */
let branch = this.tree.branches.subtrees[i];
if (branch === null) {
const newnode = this.tree.branches.getNodeID(i);
if (!newnode) {
throw new Error(`malformed tree; no node for key ${byte}`);
}
branch = registry.searchTreeLoadByNodeID(newnode);
this.tree.branches.subtrees[i] = branch;
}
return branch.then(branch => branch.trie(this.dataColumn, this.searchPattern));
}
} else {
return Promise.resolve(new SuffixTrie(
this.tree,
this.offset + 1,
this.dataColumn,
this.searchPattern,
));
}
return null;
}
}
/**
* Represents a subtree where all transitive leaves
* have a shared 16bit prefix and there are no sub-branches.
*/
class InlineNeighborsTree {
/**
* @param {Uint8Array} encoded
* @param {number} start
*/
constructor(
encoded,
start,
) {
this.encoded = encoded;
this.start = start;
}
/**
* @return {PrefixSearchTree|SuffixSearchTree}
*/
decode() {
let i = this.start;
const encoded = this.encoded;
const has_branches = (encoded[i] & 0x04) !== 0;
/** @type {boolean} */
const is_suffixes_only = (encoded[i] & 0x01) !== 0;
const leaves_count = (encoded[i] >> 4) & 0x07;
const leaves_is_run = (encoded[i] >> 7) !== 0;
i += 1;
let branch_flag = 0;
if (has_branches) {
branch_flag = encoded[i];
i += 1;
}
const dlen = encoded[i] & 0x3f;
i += 1;
/** @type {Uint8Array} */
let data = EMPTY_UINT8;
if (!is_suffixes_only && dlen !== 0) {
data = encoded.subarray(i, i + dlen);
i += dlen;
}
const branch_flag_alphabet = Alphabet.parseFlag(branch_flag, i, encoded);
let branch_alphabitmap = EMPTY_UINT8;
if (branch_flag_alphabet) {
branch_alphabitmap = new Uint8Array(branch_flag_alphabet.consumed_len_bytes + 1);
branch_alphabitmap[0] = branch_flag;
branch_alphabitmap.set(
encoded.subarray(i, i + branch_flag_alphabet.consumed_len_bytes),
1,
);
i += branch_flag_alphabet.consumed_len_bytes;
}
const branch_count = branch_flag_alphabet ? branch_flag_alphabet.len : branch_flag;
const leaf_value_upper = encoded[i] | (encoded[i + 1] << 8);
i += 2;
/** @type {Promise<SearchTree>[]} */
const branch_nodes = [];
for (let j = 0; j < branch_count; j += 1) {
const branch_dlen = encoded[i] & 0x0f;
const branch_leaves_count = (encoded[i] >> 4) & 0x07;
const branch_leaves_is_run = (encoded[i] >> 7) !== 0;
i += 1;
/** @type {Uint8Array} */
let branch_data = EMPTY_UINT8;
if (!is_suffixes_only && branch_dlen !== 0) {
branch_data = encoded.subarray(i, i + branch_dlen);
i += branch_dlen;
}
const branch_leaves = new RoaringBitmap(null);
branch_leaves.keysAndCardinalities = Uint8Array.of(
leaf_value_upper & 0xff,
(leaf_value_upper >> 8) & 0xff,
(branch_leaves_count - 1) & 0xff,
((branch_leaves_count - 1) >> 8) & 0xff,
);
if (branch_leaves_is_run) {
branch_leaves.containers = [
new RoaringBitmapRun(
1,
Uint8Array.of(
encoded[i],
encoded[i + 1],
branch_leaves_count - 1,
0,
),
),
];
i += 2;
} else {
branch_leaves.containers = [
new RoaringBitmapArray(
branch_leaves_count,
encoded.subarray(i, i + (branch_leaves_count * 2)),
),
];
i += branch_leaves_count * 2;
}
branch_nodes.push(Promise.resolve(
is_suffixes_only ?
new SuffixSearchTree(
EMPTY_SEARCH_TREE_BRANCHES,
branch_dlen,
branch_leaves,
) :
new PrefixSearchTree(
EMPTY_SEARCH_TREE_BRANCHES,
EMPTY_SEARCH_TREE_BRANCHES,
branch_data,
branch_leaves,
EMPTY_BITMAP,
),
));
}
/** @type {SearchTreeBranches<SearchTree>} */
const branches = branch_count === 0 ?
EMPTY_SEARCH_TREE_BRANCHES :
branch_flag_alphabet ?
new SearchTreeBranchesAlphaBitmap(
branch_flag_alphabet.alphabet,
branch_alphabitmap,
EMPTY_UINT8,
) :
new SearchTreeBranchesArray(
encoded.subarray(i, i + branch_count),
EMPTY_UINT8,
);
if (!branch_flag_alphabet) {
i += branch_count;
}
branches.subtrees = branch_nodes;
let leaves = EMPTY_BITMAP;
if (leaves_count !== 0) {
leaves = new RoaringBitmap(null);
leaves.keysAndCardinalities = Uint8Array.of(
leaf_value_upper & 0xff,
(leaf_value_upper >> 8) & 0xff,
(leaves_count - 1) & 0xff,
((leaves_count - 1) >> 8) & 0xff,
);
if (leaves_is_run) {
leaves.containers = [
new RoaringBitmapRun(
1,
Uint8Array.of(
encoded[i],
encoded[i + 1],
leaves_count - 1,
0,
),
),
];
i += 2;
} else {
leaves.containers = [
new RoaringBitmapArray(
leaves_count,
encoded.subarray(i, i + (leaves_count * 2)),
),
];
i += leaves_count * 2;
}
}
return is_suffixes_only ?
new SuffixSearchTree(
branches,
dlen,
leaves,
) :
new PrefixSearchTree(
branches,
branches,
data,
leaves,
EMPTY_BITMAP,
);
}
/**
* Returns the Trie for the root node.
*
* A Trie pointer refers to a single node in a logical decompressed search tree
* (the real search tree is compressed).
*
* @param {DataColumn} dataColumn
* @param {Uint8ArraySearchPattern} searchPattern
* @return {Trie}
*/
trie(dataColumn, searchPattern) {
const tree = this.decode();
return tree instanceof SuffixSearchTree ?
new SuffixTrie(tree, 0, dataColumn, searchPattern) :
new PrefixTrie(tree, 0, dataColumn, searchPattern);
}
/**
* Return the trie representing `name`
* @param {Uint8Array|string} name
* @param {DataColumn} dataColumn
* @returns {Promise<Trie?>}
*/
search(name, dataColumn) {
return this.decode().search(name, dataColumn);
}
/**
* @param {Uint8Array|string} name
* @param {DataColumn} dataColumn
* @returns {AsyncGenerator<Trie>}
*/
searchLev(name, dataColumn) {
return this.decode().searchLev(name, dataColumn);
}
/** @returns {RoaringBitmap} */
getCurrentLeaves() {
return this.decode().getCurrentLeaves();
}
}
class DataColumn {
/**
* Construct the wrapper object for a data column.
* @param {number[]} counts
* @param {Uint8Array} hashes
* @param {RoaringBitmap} emptyset
* @param {string} name
* @param {SearchTree?} searchTree
*/
constructor(counts, hashes, emptyset, name, searchTree) {
this.searchTree = searchTree;
this.hashes = hashes;
this.emptyset = emptyset;
this.name = name;
/** @type {{"hash": Uint8Array, "data": Uint8Array[]?, "end": number}[]} */
this.buckets = [];
this.bucket_keys = [];
const l = counts.length;
let k = 0;
let totalLength = 0;
for (let i = 0; i < l; ++i) {
const count = counts[i];
totalLength += count;
const start = k;
for (let j = 0; j < count; ++j) {
if (emptyset.contains(k)) {
j -= 1;
}
k += 1;
}
const end = k;
const bucket = {hash: hashes.subarray(i * 5, (i + 1) * 5), data: null, end, count};
this.buckets.push(bucket);
this.bucket_keys.push(start);
}
this.length = totalLength;
}
/**
* Check if a cell contains the empty string.
* @param {number} id
* @returns {boolean}
*/
isEmpty(id) {
return this.emptyset.contains(id);
}
/**
* Look up a cell by row ID.
* @param {number} id
* @returns {Promise<Uint8Array>|Uint8Array|undefined}
*/
at(id) {
if (this.emptyset.contains(id)) {
return EMPTY_UINT8;
} else {
let idx = -1;
while (this.bucket_keys[idx + 1] <= id) {
idx += 1;
}
if (idx === -1 || idx >= this.bucket_keys.length) {
return undefined;
} else {
const start = this.bucket_keys[idx];
const bucket = this.buckets[idx];
const data = this.buckets[idx].data;
if (data === null) {
return this.atAsyncFetch(id, start, bucket);
} else {
return data[id - start];
}
}
}
}
/**
* Look up a cell by row ID.
* @param {number} id
* @param {number} start
* @param {{hash: Uint8Array, data: Uint8Array[] | null, end: number}} bucket
* @returns {Promise<Uint8Array>}
*/
async atAsyncFetch(id, start, bucket) {
const {hash, end} = bucket;
const dataSansEmptysetOrig = await registry.dataLoadByNameAndHash(
this.name,
hash,
);
// After the `await` resolves, another task might fill
// in the data. If so, we should use that.
let data = bucket.data;
if (data !== null) {
return data[id - start];
}
const dataSansEmptyset = [...dataSansEmptysetOrig];
/** @type {(Uint8Array[])|null} */
let dataWithEmptyset = null;
let pos = start;
let insertCount = 0;
while (pos < end) {
if (this.emptyset.contains(pos)) {
if (dataWithEmptyset === null) {
dataWithEmptyset = dataSansEmptyset.splice(0, insertCount);
} else if (insertCount !== 0) {
dataWithEmptyset.push(
...dataSansEmptyset.splice(0, insertCount),
);
}
insertCount = 0;
dataWithEmptyset.push(EMPTY_UINT8);
} else {
insertCount += 1;
}
pos += 1;
}
data = dataWithEmptyset === null ?
dataSansEmptyset :
dataWithEmptyset.concat(dataSansEmptyset);
bucket.data = data;
return data[id - start];
}
/**
* Search by exact substring
* @param {Uint8Array|string} name
* @returns {Promise<Trie?>}
*/
async search(name) {
return await (this.searchTree ? this.searchTree.search(name, this) : null);
}
/**
* Search by whole, inexact match
* @param {Uint8Array|string} name
* @returns {AsyncGenerator<Trie>}
*/
async *searchLev(name) {
if (this.searchTree) {
yield* this.searchTree.searchLev(name, this);
}
}
}
class Database {
/**
* The primary frontend for accessing data in this index.
*
* @param {Map<string, SearchTree>} searchTreeRoots
* @param {Map<string, DataColumn>} dataColumns
*/
constructor(searchTreeRoots, dataColumns) {
this.searchTreeRoots = searchTreeRoots;
this.dataColumns = dataColumns;
}
/**
* Search a column by name, returning verbatim matched IDs.
* @param {string} colname
* @returns {SearchTree|undefined}
*/
getIndex(colname) {
return this.searchTreeRoots.get(colname);
}
/**
* Look up a cell by column ID and row ID.
* @param {string} colname
* @returns {DataColumn|undefined}
*/
getData(colname) {
return this.dataColumns.get(colname);
}
}
/**
* Load a data column.
* @param {Uint8Array} data
*/
function loadColumnFromBytes(data) {
const hashBuf = Uint8Array.of(0, 0, 0, 0, 0, 0, 0, 0);
const truncatedHash = hashBuf.subarray(3, 8);
siphashOfBytes(data, 0, 0, 0, 0, hashBuf);
const cb = registry.dataColumnLoadPromiseCallbacks.get(truncatedHash);
if (cb) {
const backrefs = [];
const dataSansEmptyset = [];
let i = 0;
const l = data.length;
while (i < l) {
let c = data[i];
if (c >= 48 && c <= 63) { // 48 = "0", 63 = "?"
dataSansEmptyset.push(backrefs[c - 48]);
i += 1;
} else {
let n = 0;
while (c < 96) { // 96 = "`"
n = (n << 4) | (c & 0xF);
i += 1;
c = data[i];
}
n = (n << 4) | (c & 0xF);
i += 1;
const item = data.subarray(i, i + n);
dataSansEmptyset.push(item);
i += n;
backrefs.unshift(item);
if (backrefs.length > 16) {
backrefs.pop();
}
}
}
cb(null, dataSansEmptyset);
}
}
/**
* @param {string} inputBase64
* @returns {[Uint8Array, SearchTree]}
*/
function makeSearchTreeFromBase64(inputBase64) {
const input = makeUint8ArrayFromBase64(inputBase64);
let i = 0;
const l = input.length;
/** @type {HashTable<SearchTree>} */
const stash = new HashTable();
const hash = Uint8Array.of(0, 0, 0, 0, 0, 0, 0, 0);
const truncatedHash = hash.subarray(3, 8);
// used for handling compressed (that is, relative-offset) nodes
/** @type {{hash: Uint8Array, used: boolean}[]} */
const hash_history = [];
/** @type {Uint8Array[]} */
const data_history = [];
let canonical = EMPTY_UINT8;
/** @type {SearchTree} */
let tree = new PrefixSearchTree(
EMPTY_SEARCH_TREE_BRANCHES,
EMPTY_SEARCH_TREE_BRANCHES,
EMPTY_UINT8,
EMPTY_BITMAP,
EMPTY_BITMAP,
);
/**
* @param {Uint8Array} input
* @param {number} i
* @param {number} compression_tag
* @returns {{
* "might_have_prefix_branches": SearchTreeBranches<SearchTree>,
* "branches": SearchTreeBranches<SearchTree>,
* "branches_header": Uint8Array,
* "cpnodes": Uint8Array,
* "csnodes": Uint8Array,
* "branches_keys": Uint8Array,
* "consumed_len_bytes": number,
* }}
*/
function makeBranchesFromBinaryData(
input,
i,
compression_tag,
) {
const is_pure_suffixes_only_node = (compression_tag & 0x01) !== 0x00;
const is_stack_compressed = (compression_tag & 0x02) !== 0;
const is_long_compressed = (compression_tag & 0x04) !== 0;
const all_children_are_compressed =
(compression_tag & 0xF0) === 0xF0 && !is_long_compressed;
const any_children_are_compressed =
(compression_tag & 0xF0) !== 0x00 || is_long_compressed;
const start_point = i;
/**
* @type {Alphabet|null}
*/
let cpalphabet = null;
/**
* @type {Uint8Array}
*/
let cpalphabitmap = EMPTY_UINT8;
/**
* @type {number}
*/
let cplen;
/**
* @type {Alphabet|null}
*/
let csalphabet = null;
/**
* @type {Uint8Array}
*/
let csalphabitmap = EMPTY_UINT8;
/**
* @type {number}
*/
let cslen;
// might-have-prefix nodes
if (is_pure_suffixes_only_node) {
cplen = 0;
} else {
const parsed = Alphabet.parse(i, input);
if (parsed) {
cpalphabitmap = input.subarray(i, i + parsed.consumed_len_bytes);
cpalphabet = parsed.alphabet;
cplen = parsed.len;
i += parsed.consumed_len_bytes;
} else {
cplen = input[i];
i += 1;
}
}
// suffix-only nodes
const parsed = Alphabet.parse(i, input);
if (parsed) {
csalphabitmap = input.subarray(i, i + parsed.consumed_len_bytes);
csalphabet = parsed.alphabet;
cslen = parsed.len;
i += parsed.consumed_len_bytes;
} else {
cslen = input[i];
i += 1;
}
const branches_header = input.subarray(start_point, i);
// now process the hashes, offsets, or stack
let j = 0;
/** @type {Uint8Array} */
let cpnodes;
if (any_children_are_compressed) {
cpnodes = cplen === 0 ? EMPTY_UINT8 : new Uint8Array(cplen * 5);
while (j < cplen) {
const is_compressed = all_children_are_compressed ||
((0x10 << j) & compression_tag) !== 0;
if (is_compressed) {
let slot = hash_history.length - 1;
if (is_stack_compressed) {
while (hash_history[slot].used) {
slot -= 1;
}
} else {
slot -= input[i];
i += 1;
}
hash_history[slot].used = true;
cpnodes.set(
hash_history[slot].hash,
j * 5,
);
} else {
const joff = j * 5;
cpnodes[joff + 0] = input[i + 0];
cpnodes[joff + 1] = input[i + 1];
cpnodes[joff + 2] = input[i + 2];
cpnodes[joff + 3] = input[i + 3];
cpnodes[joff + 4] = input[i + 4];
i += 5;
}
j += 1;
}
} else {
cpnodes = cplen === 0 ? EMPTY_UINT8 : input.subarray(i, i + (cplen * 5));
i += cplen * 5;
}
j = 0;
/** @type {Uint8Array} */
let csnodes;
if (any_children_are_compressed) {
csnodes = cslen === 0 ? EMPTY_UINT8 : new Uint8Array(cslen * 5);
while (j < cslen) {
const is_compressed = all_children_are_compressed ||
((0x10 << (cplen + j)) & compression_tag) !== 0;
if (is_compressed) {
let slot = hash_history.length - 1;
if (is_stack_compressed) {
while (hash_history[slot].used) {
slot -= 1;
}
} else {
slot -= input[i];
i += 1;
}
hash_history[slot].used = true;
csnodes.set(
hash_history[slot].hash,
j * 5,
);
} else {
const joff = j * 5;
csnodes[joff + 0] = input[i + 0];
csnodes[joff + 1] = input[i + 1];
csnodes[joff + 2] = input[i + 2];
csnodes[joff + 3] = input[i + 3];
csnodes[joff + 4] = input[i + 4];
i += 5;
}
j += 1;
}
} else {
csnodes = cslen === 0 ? EMPTY_UINT8 : input.subarray(i, i + (cslen * 5));
i += cslen * 5;
}
const start_point_keys = i;
let might_have_prefix_branches;
if (cplen === 0) {
might_have_prefix_branches = EMPTY_SEARCH_TREE_BRANCHES;
} else if (cpalphabet) {
might_have_prefix_branches = new SearchTreeBranchesAlphaBitmap(
cpalphabet,
cpalphabitmap,
cpnodes,
);
} else {
might_have_prefix_branches = new SearchTreeBranchesArray(
new Uint8Array(input.buffer, i + input.byteOffset, cplen),
cpnodes,
);
i += cplen;
}
let branches;
if (cslen === 0) {
branches = might_have_prefix_branches;
} else {
if (csalphabet) {
branches = new SearchTreeBranchesAlphaBitmap(
csalphabet,
csalphabitmap,
csnodes,
);
} else {
branches = new SearchTreeBranchesArray(
new Uint8Array(input.buffer, i + input.byteOffset, cslen),
csnodes,
);
i += cslen;
}
if (cplen !== 0) {
const hashes = new Uint8Array((cplen + cslen) * 5);
if (cplen + cslen > 32) {
const raw_bits = new Uint8Array(RAWBYTE_ALPHABET.bytes + 1);
raw_bits[0] = RAWBYTE_ALPHABET.flag;
const bits = raw_bits.subarray(1);
const mhp_keys = might_have_prefix_branches.getKeys();
const so_keys = branches.getKeys();
let mhp_i = 0;
let so_i = 0;
let j = 0;
while (mhp_i < cplen || so_i < cslen) {
if (so_i === cslen || mhp_keys[mhp_i] < so_keys[so_i]) {
const joff = j * 5;
const mhp_off = mhp_i * 5;
hashes[joff + 0] = cpnodes[mhp_off + 0];
hashes[joff + 1] = cpnodes[mhp_off + 1];
hashes[joff + 2] = cpnodes[mhp_off + 2];
hashes[joff + 3] = cpnodes[mhp_off + 3];
hashes[joff + 4] = cpnodes[mhp_off + 4];
const ix = mhp_keys[mhp_i];
bits[ix >> 3] |= 1 << (ix & 0x07);
mhp_i += 1;
} else {
const joff = j * 5;
const so_off = so_i * 5;
hashes[joff + 0] = csnodes[so_off + 0];
hashes[joff + 1] = csnodes[so_off + 1];
hashes[joff + 2] = csnodes[so_off + 2];
hashes[joff + 3] = csnodes[so_off + 3];
hashes[joff + 4] = csnodes[so_off + 4];
const ix = so_keys[so_i];
bits[ix >> 3] |= 1 << (ix & 0x07);
so_i += 1;
}
j += 1;
}
branches = new SearchTreeBranchesAlphaBitmap(
RAWBYTE_ALPHABET,
raw_bits,
hashes,
);
} else {
const merged_keys = new Uint8Array(cplen + cslen);
const mhp_keys = might_have_prefix_branches.getKeys();
const so_keys = branches.getKeys();
let mhp_i = 0;
let so_i = 0;
let j = 0;
while (mhp_i < cplen || so_i < cslen) {
if (so_i === cslen || mhp_keys[mhp_i] < so_keys[so_i]) {
const joff = j * 5;
const mhp_off = mhp_i * 5;
hashes[joff + 0] = cpnodes[mhp_off + 0];
hashes[joff + 1] = cpnodes[mhp_off + 1];
hashes[joff + 2] = cpnodes[mhp_off + 2];
hashes[joff + 3] = cpnodes[mhp_off + 3];
hashes[joff + 4] = cpnodes[mhp_off + 4];
merged_keys[j] = mhp_keys[mhp_i];
mhp_i += 1;
} else {
const joff = j * 5;
const so_off = so_i * 5;
hashes[joff + 0] = csnodes[so_off + 0];
hashes[joff + 1] = csnodes[so_off + 1];
hashes[joff + 2] = csnodes[so_off + 2];
hashes[joff + 3] = csnodes[so_off + 3];
hashes[joff + 4] = csnodes[so_off + 4];
merged_keys[j] = so_keys[so_i];
so_i += 1;
}
j += 1;
}
branches = new SearchTreeBranchesArray(
merged_keys,
hashes,
);
}
}
}
const branches_keys = input.subarray(start_point_keys, i);
return {
consumed_len_bytes: i - start_point,
cpnodes,
csnodes,
branches,
might_have_prefix_branches,
branches_header,
branches_keys,
};
}
while (i < l) {
const start = i;
let data;
// compression_tag = 1 means pure-suffixes-only,
// which is not considered "compressed" for the purposes of this loop
// because that's the canonical, hashed version of the data
let compression_tag = input[i];
const is_pure_suffixes_only_node = (compression_tag & 0x01) !== 0;
const is_long_compressed = (compression_tag & 0x04) !== 0;
const is_data_compressed = (compression_tag & 0x08) !== 0;
i += 1;
if (is_long_compressed) {
compression_tag |= input[i] << 8;
i += 1;
}
/** @type {number} */
let dlen;
/** @type {number} */
let no_leaves_flag;
/** @type {number} */
let no_branches_flag;
if (is_data_compressed && is_pure_suffixes_only_node) {
dlen = 0;
no_leaves_flag = 0x80;
no_branches_flag = 0;
} else {
dlen = input[i] & 0x3F;
no_leaves_flag = input[i] & 0x80;
no_branches_flag = input[i] & 0x40;
i += 1;
}
if (no_leaves_flag !== 0 && no_branches_flag !== 0) {
// node with packed leaves and common 16bit prefix
const leaves_count = (compression_tag >> 4) & 0x07;
const leaves_is_run = ((compression_tag >> 4) & 0x08) !== 0;
const branch_flag = is_long_compressed ?
(compression_tag >> 8) & 0xff :
0;
if (is_data_compressed) {
data = data_history[data_history.length - dlen - 1];
dlen = data.length;
} else if (is_pure_suffixes_only_node) {
data = EMPTY_UINT8;
} else {
data = dlen === 0 ?
EMPTY_UINT8 :
new Uint8Array(input.buffer, i + input.byteOffset, dlen);
i += dlen;
}
const branches_start = i;
const branch_flag_alphabet = Alphabet.parseFlag(branch_flag, i, input);
const branch_count = branch_flag_alphabet ? branch_flag_alphabet.len : branch_flag;
if (branch_flag_alphabet) {
i += branch_flag_alphabet.consumed_len_bytes;
}
// leaf_value_upper
i += 2;
// branch_nodes
for (let j = 0; j < branch_count; j += 1) {
const branch_dlen = input[i] & 0x0f;
const branch_leaves_count = (input[i] >> 4) & 0x0f;
const branch_leaves_is_run = (input[i] >> 7) !== 0;
i += 1;
if (!is_pure_suffixes_only_node) {
i += branch_dlen;
}
if (branch_leaves_is_run) {
i += 2;
} else {
i += branch_leaves_count * 2;
}
}
// branch keys
if (!branch_flag_alphabet) {
i += branch_count;
}
// leaves
if (leaves_is_run) {
i += 2;
} else {
i += leaves_count * 2;
}
if (is_data_compressed) {
const clen = (
1 + // first compression header byte
(is_long_compressed ? 1 : 0) + // branch flag
1 + // data length and other flags
dlen + // data
(i - branches_start) // branches and leaves
);
const canonical = new Uint8Array(clen);
let ci = 0;
canonical[ci] = input[start] ^ 0x08;
ci += 1;
if (is_long_compressed) {
canonical[ci] = input[start + ci];
ci += 1;
}
canonical[ci] = dlen | 0xc0;
ci += 1;
for (let j = 0; j < dlen; j += 1) {
canonical[ci] = data[j];
ci += 1;
}
for (let j = branches_start; j < i; j += 1) {
canonical[ci] = input[j];
ci += 1;
}
tree = new InlineNeighborsTree(canonical, 0);
siphashOfBytes(canonical, 0, 0, 0, 0, hash);
} else {
tree = new InlineNeighborsTree(input, start);
siphashOfBytes(new Uint8Array(
input.buffer,
start + input.byteOffset,
i - start,
), 0, 0, 0, 0, hash);
}
} else if (compression_tag > 1) {
// compressed node
if (is_pure_suffixes_only_node) {
data = EMPTY_UINT8;
} else if (is_data_compressed) {
data = data_history[data_history.length - dlen - 1];
dlen = data.length;
} else {
data = dlen === 0 ?
EMPTY_UINT8 :
new Uint8Array(input.buffer, i + input.byteOffset, dlen);
i += dlen;
}
const {
cpnodes,
csnodes,
consumed_len_bytes: branches_consumed_len_bytes,
branches,
might_have_prefix_branches,
branches_header,
branches_keys,
} = no_branches_flag !== 0 ?
{
cpnodes: EMPTY_UINT8,
csnodes: EMPTY_UINT8,
consumed_len_bytes: 0,
branches: EMPTY_SEARCH_TREE_BRANCHES,
might_have_prefix_branches: EMPTY_SEARCH_TREE_BRANCHES,
branches_header: EMPTY_UINT8,
branches_keys: EMPTY_UINT8,
} :
makeBranchesFromBinaryData(input, i, compression_tag);
i += branches_consumed_len_bytes;
let whole;
let suffix;
if (is_pure_suffixes_only_node) {
if (no_leaves_flag) {
whole = EMPTY_BITMAP;
suffix = EMPTY_BITMAP;
} else {
suffix = input[i] === 0 ?
EMPTY_BITMAP1 :
new RoaringBitmap(input, i);
i += suffix.consumed_len_bytes;
}
tree = new SuffixSearchTree(
branches,
dlen,
suffix,
);
const clen = (
// lengths of children and data
(is_data_compressed ? 1 : 2) +
// branches
branches_header.length +
csnodes.length +
branches_keys.length +
// leaves
suffix.consumed_len_bytes
);
if (canonical.length < clen) {
canonical = new Uint8Array(clen);
}
let ci = 0;
if (is_data_compressed) {
canonical[ci] = 0x09;
ci += 1;
} else {
canonical[ci] = 1;
ci += 1;
canonical[ci] = dlen | no_leaves_flag | no_branches_flag;
ci += 1;
}
canonical.set(branches_header, ci);
ci += branches_header.length;
canonical.set(csnodes, ci);
ci += csnodes.length;
canonical.set(branches_keys, ci);
ci += branches_keys.length;
const leavesOffset = i - suffix.consumed_len_bytes;
for (let j = leavesOffset; j < i; j += 1) {
canonical[ci + j - leavesOffset] = input[j];
}
siphashOfBytes(canonical.subarray(0, clen), 0, 0, 0, 0, hash);
} else {
if (no_leaves_flag) {
whole = EMPTY_BITMAP;
suffix = EMPTY_BITMAP;
} else {
whole = input[i] === 0 ?
EMPTY_BITMAP1 :
new RoaringBitmap(input, i);
i += whole.consumed_len_bytes;
suffix = input[i] === 0 ?
EMPTY_BITMAP1 :
new RoaringBitmap(input, i);
i += suffix.consumed_len_bytes;
}
tree = new PrefixSearchTree(
branches,
might_have_prefix_branches,
data,
whole,
suffix,
);
const clen = (
2 + // lengths of children and data
dlen +
branches_header.length +
cpnodes.length + csnodes.length +
branches_keys.length +
whole.consumed_len_bytes +
suffix.consumed_len_bytes
);
if (canonical.length < clen) {
canonical = new Uint8Array(clen);
}
let ci = 0;
canonical[ci] = 0;
ci += 1;
canonical[ci] = dlen | no_leaves_flag | no_branches_flag;
ci += 1;
canonical.set(data, ci);
ci += data.length;
canonical.set(branches_header, ci);
ci += branches_header.length;
canonical.set(cpnodes, ci);
ci += cpnodes.length;
canonical.set(csnodes, ci);
ci += csnodes.length;
canonical.set(branches_keys, ci);
ci += branches_keys.length;
const leavesOffset = i - whole.consumed_len_bytes - suffix.consumed_len_bytes;
for (let j = leavesOffset; j < i; j += 1) {
canonical[ci + j - leavesOffset] = input[j];
}
siphashOfBytes(canonical.subarray(0, clen), 0, 0, 0, 0, hash);
}
} else {
// uncompressed node
if (dlen === 0 || is_pure_suffixes_only_node) {
data = EMPTY_UINT8;
} else {
data = new Uint8Array(input.buffer, i + input.byteOffset, dlen);
i += dlen;
}
const {
consumed_len_bytes: branches_consumed_len_bytes,
branches,
might_have_prefix_branches,
} = no_branches_flag !== 0 ?
{
consumed_len_bytes: 0,
branches: EMPTY_SEARCH_TREE_BRANCHES,
might_have_prefix_branches: EMPTY_SEARCH_TREE_BRANCHES,
} :
makeBranchesFromBinaryData(input, i, compression_tag);
i += branches_consumed_len_bytes;
let whole;
let suffix;
if (no_leaves_flag) {
whole = EMPTY_BITMAP;
suffix = EMPTY_BITMAP;
} else if (is_pure_suffixes_only_node) {
whole = EMPTY_BITMAP;
suffix = input[i] === 0 ?
EMPTY_BITMAP1 :
new RoaringBitmap(input, i);
i += suffix.consumed_len_bytes;
} else {
whole = input[i] === 0 ?
EMPTY_BITMAP1 :
new RoaringBitmap(input, i);
i += whole.consumed_len_bytes;
suffix = input[i] === 0 ?
EMPTY_BITMAP1 :
new RoaringBitmap(input, i);
i += suffix.consumed_len_bytes;
}
siphashOfBytes(new Uint8Array(
input.buffer,
start + input.byteOffset,
i - start,
), 0, 0, 0, 0, hash);
tree = is_pure_suffixes_only_node ?
new SuffixSearchTree(
branches,
dlen,
suffix,
) :
new PrefixSearchTree(
branches,
might_have_prefix_branches,
data,
whole,
suffix,
);
}
hash[3] &= 0x7f;
hash_history.push({hash: truncatedHash.slice(), used: false});
if (data.length !== 0) {
data_history.push(data);
}
if (!(tree instanceof InlineNeighborsTree)) {
const tree_branch_nodeids = tree.branches.nodeids;
const tree_branch_subtrees = tree.branches.subtrees;
let j = 0;
const lb = tree.branches.subtrees.length;
while (j < lb) {
// node id with a 1 in its most significant bit is inlined, and, so
// it won't be in the stash
if ((tree_branch_nodeids[j * 5] & 0x80) === 0) {
const subtree = stash.getWithOffsetKey(tree_branch_nodeids, j * 5);
if (subtree !== undefined) {
tree_branch_subtrees[j] = Promise.resolve(subtree);
}
}
j += 1;
}
}
if (tree instanceof PrefixSearchTree) {
const tree_mhp_branch_nodeids = tree.might_have_prefix_branches.nodeids;
const tree_mhp_branch_subtrees = tree.might_have_prefix_branches.subtrees;
let j = 0;
const lb = tree.might_have_prefix_branches.subtrees.length;
while (j < lb) {
// node id with a 1 in its most significant bit is inlined, and, so
// it won't be in the stash
if ((tree_mhp_branch_nodeids[j * 5] & 0x80) === 0) {
const subtree = stash.getWithOffsetKey(tree_mhp_branch_nodeids, j * 5);
if (subtree !== undefined) {
tree_mhp_branch_subtrees[j] = Promise.resolve(subtree);
}
}
j += 1;
}
}
if (i !== l) {
stash.set(truncatedHash, tree);
}
}
return [truncatedHash, tree];
}
return new Promise((resolve, reject) => {
registry.searchTreeRootCallback = (error, data) => {
if (data) {
resolve(data);
} else {
reject(error);
}
};
hooks.loadRoot(callbacks);
});
}
if (typeof window !== "undefined") {
window.Stringdex = {
loadDatabase,
};
window.RoaringBitmap = RoaringBitmap;
if (window.StringdexOnload) {
window.StringdexOnload.forEach(cb => cb(window.Stringdex));
}
} else {
/** @type {stringdex.Stringdex} */
// eslint-disable-next-line no-undef
module.exports.Stringdex = {
loadDatabase,
};
/** @type {stringdex.RoaringBitmap} */
// eslint-disable-next-line no-undef
module.exports.RoaringBitmap = RoaringBitmap;
}
// eslint-disable-next-line max-len
// polyfill https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Uint8Array/fromBase64
/**
* @type {function(string): Uint8Array} base64
*/
//@ts-expect-error
const makeUint8ArrayFromBase64 = Uint8Array.fromBase64 ? Uint8Array.fromBase64 : (string => {
const bytes_as_string = atob(string);
const l = bytes_as_string.length;
const bytes = new Uint8Array(l);
for (let i = 0; i < l; ++i) {
bytes[i] = bytes_as_string.charCodeAt(i);
}
return bytes;
});
/**
* @type {function(string): Uint8Array} base64
*/
//@ts-expect-error
const makeUint8ArrayFromHex = Uint8Array.fromHex ? Uint8Array.fromHex : (string => {
/** @type {Object<string, number>} */
const alpha = {
"0": 0, "1": 1,
"2": 2, "3": 3,
"4": 4, "5": 5,
"6": 6, "7": 7,
"8": 8, "9": 9,
"a": 10, "b": 11,
"A": 10, "B": 11,
"c": 12, "d": 13,
"C": 12, "D": 13,
"e": 14, "f": 15,
"E": 14, "F": 15,
};
const l = string.length >> 1;
const bytes = new Uint8Array(l);
for (let i = 0; i < l; i += 1) {
const top = string[i << 1];
const bottom = string[(i << 1) + 1];
bytes[i] = (alpha[top] << 4) | alpha[bottom];
}
return bytes;
});
/**
* @type {function(Uint8Array): string} base64
*/
//@ts-expect-error
const makeHexFromUint8Array = Uint8Array.prototype.toHex ? (array => array.toHex()) : (array => {
/** @type {string[]} */
const alpha = [
"0", "1",
"2", "3",
"4", "5",
"6", "7",
"8", "9",
"a", "b",
"c", "d",
"e", "f",
];
const l = array.length;
const v = [];
for (let i = 0; i < l; ++i) {
v.push(alpha[array[i] >> 4]);
v.push(alpha[array[i] & 0xf]);
}
return v.join("");
});
//////////////
/**
* SipHash 1-3
* @param {Uint8Array} input data to be hashed; all codepoints in string should be less than 256
* @param {number} k0lo first word of key
* @param {number} k0hi second word of key
* @param {number} k1lo third word of key
* @param {number} k1hi fourth word of key
* @param {Uint8Array} output the data to write (clobber the first eight bytes)
*/
function siphashOfBytes(input, k0lo, k0hi, k1lo, k1hi, output) {
// hash state
// While siphash uses 64 bit state, js only has native support
// for 32 bit numbers. BigInt, unfortunately, doesn't count.
// It's too slow.
let v0lo = k0lo ^ 0x70736575;
let v0hi = k0hi ^ 0x736f6d65;
let v1lo = k1lo ^ 0x6e646f6d;
let v1hi = k1hi ^ 0x646f7261;
let v2lo = k0lo ^ 0x6e657261;
let v2hi = k0hi ^ 0x6c796765;
let v3lo = k1lo ^ 0x79746573;
let v3hi = k1hi ^ 0x74656462;
const inputLength = input.length;
let inputI = 0;
// main hash loop
const left = inputLength & 0x7;
let milo = 0;
let mihi = 0;
while (inputI < inputLength - left) {
u8ToU64le(inputI, inputI + 8);
v3lo ^= milo;
v3hi ^= mihi;
siphashCompress();
v0lo ^= milo;
v0hi ^= mihi;
inputI += 8;
}
u8ToU64le(inputI, inputI + left);
// finish
const blo = milo;
const bhi = ((inputLength & 0xff) << 24) | mihi;
v3lo ^= blo;
v3hi ^= bhi;
siphashCompress();
v0lo ^= blo;
v0hi ^= bhi;
v2lo ^= 0xff;
siphashCompress();
siphashCompress();
siphashCompress();
output[7] = (v0lo ^ v1lo ^ v2lo ^ v3lo) & 0xff;
output[6] = (v0lo ^ v1lo ^ v2lo ^ v3lo) >>> 8;
output[5] = (v0lo ^ v1lo ^ v2lo ^ v3lo) >>> 16;
output[4] = (v0lo ^ v1lo ^ v2lo ^ v3lo) >>> 24;
output[3] = (v0hi ^ v1hi ^ v2hi ^ v3hi) & 0xff;
output[2] = (v0hi ^ v1hi ^ v2hi ^ v3hi) >>> 8;
output[1] = (v0hi ^ v1hi ^ v2hi ^ v3hi) >>> 16;
output[0] = (v0hi ^ v1hi ^ v2hi ^ v3hi) >>> 24;
/**
* Convert eight bytes to a single 64-bit number
* @param {number} offset
* @param {number} length
*/
function u8ToU64le(offset, length) {
const n0 = offset < length ? input[offset] & 0xff : 0;
const n1 = offset + 1 < length ? input[offset + 1] & 0xff : 0;
const n2 = offset + 2 < length ? input[offset + 2] & 0xff : 0;
const n3 = offset + 3 < length ? input[offset + 3] & 0xff : 0;
const n4 = offset + 4 < length ? input[offset + 4] & 0xff : 0;
const n5 = offset + 5 < length ? input[offset + 5] & 0xff : 0;
const n6 = offset + 6 < length ? input[offset + 6] & 0xff : 0;
const n7 = offset + 7 < length ? input[offset + 7] & 0xff : 0;
milo = n0 | (n1 << 8) | (n2 << 16) | (n3 << 24);
mihi = n4 | (n5 << 8) | (n6 << 16) | (n7 << 24);
}
function siphashCompress() {
// v0 += v1;
v0hi = (v0hi + v1hi + (((v0lo >>> 0) + (v1lo >>> 0) > 0xffffffff) ? 1 : 0)) | 0;
v0lo = (v0lo + v1lo) | 0;
// rotl(v1, 13)
let v1lo_ = v1lo;
let v1hi_ = v1hi;
v1lo = (v1lo_ << 13) | (v1hi_ >>> 19);
v1hi = (v1hi_ << 13) | (v1lo_ >>> 19);
// v1 ^= v0
v1lo ^= v0lo;
v1hi ^= v0hi;
// rotl(v0, 32)
const v0lo_ = v0lo;
const v0hi_ = v0hi;
v0lo = v0hi_;
v0hi = v0lo_;
// v2 += v3
v2hi = (v2hi + v3hi + (((v2lo >>> 0) + (v3lo >>> 0) > 0xffffffff) ? 1 : 0)) | 0;
v2lo = (v2lo + v3lo) | 0;
// rotl(v3, 16)
let v3lo_ = v3lo;
let v3hi_ = v3hi;
v3lo = (v3lo_ << 16) | (v3hi_ >>> 16);
v3hi = (v3hi_ << 16) | (v3lo_ >>> 16);
// v3 ^= v2
v3lo ^= v2lo;
v3hi ^= v2hi;
// v0 += v3
v0hi = (v0hi + v3hi + (((v0lo >>> 0) + (v3lo >>> 0) > 0xffffffff) ? 1 : 0)) | 0;
v0lo = (v0lo + v3lo) | 0;
// rotl(v3, 21)
v3lo_ = v3lo;
v3hi_ = v3hi;
v3lo = (v3lo_ << 21) | (v3hi_ >>> 11);
v3hi = (v3hi_ << 21) | (v3lo_ >>> 11);
// v3 ^= v0
v3lo ^= v0lo;
v3hi ^= v0hi;
// v2 += v1
v2hi = (v2hi + v1hi + (((v2lo >>> 0) + (v1lo >>> 0) > 0xffffffff) ? 1 : 0)) | 0;
v2lo = (v2lo + v1lo) | 0;
// rotl(v1, 17)
v1lo_ = v1lo;
v1hi_ = v1hi;
v1lo = (v1lo_ << 17) | (v1hi_ >>> 15);
v1hi = (v1hi_ << 17) | (v1lo_ >>> 15);
// v1 ^= v2
v1lo ^= v2lo;
v1hi ^= v2hi;
// rotl(v2, 32)
const v2lo_ = v2lo;
const v2hi_ = v2hi;
v2lo = v2hi_;
v2hi = v2lo_;
}
}
//////////////
// Parts of this code are based on Lucene, which is licensed under the
// Apache/2.0 license.
// More information found here:
// https://fossies.org/linux/lucene/lucene/core/src/java/org/apache/lucene/util/automaton/
// LevenshteinAutomata.java
class ParametricDescription {
/**
* @param {number} w
* @param {number} n
* @param {Int32Array} minErrors
*/
constructor(w, n, minErrors) {
this.w = w;
this.n = n;
this.minErrors = minErrors;
}
/**
* @param {number} absState
* @returns {boolean}
*/
isAccept(absState) {
const state = Math.floor(absState / (this.w + 1));
const offset = absState % (this.w + 1);
return this.w - offset + this.minErrors[state] <= this.n;
}
/**
* @param {number} absState
* @returns {number}
*/
getPosition(absState) {
return absState % (this.w + 1);
}
/**
* @param {Uint8Array} name
* @param {number} charCode
* @param {number} pos
* @param {number} end
* @returns {number}
*/
getVector(name, charCode, pos, end) {
let vector = 0;
for (let i = pos; i < end; i += 1) {
vector = vector << 1;
if (name[i] === charCode) {
vector |= 1;
}
}
return vector;
}
/**
* @param {Int32Array} data
* @param {number} index
* @param {number} bitsPerValue
* @returns {number}
*/
unpack(data, index, bitsPerValue) {
const bitLoc = (bitsPerValue * index);
const dataLoc = bitLoc >> 5;
const bitStart = bitLoc & 31;
if (bitStart + bitsPerValue <= 32) {
// not split
return ((data[dataLoc] >> bitStart) & this.MASKS[bitsPerValue - 1]);
} else {
// split
const part = 32 - bitStart;
return ~~(((data[dataLoc] >> bitStart) & this.MASKS[part - 1]) +
((data[1 + dataLoc] & this.MASKS[bitsPerValue - part - 1]) << part));
}
}
}
ParametricDescription.prototype.MASKS = new Int32Array([
0x1, 0x3, 0x7, 0xF,
0x1F, 0x3F, 0x7F, 0xFF,
0x1FF, 0x3F, 0x7FF, 0xFFF,
0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF,
0x1FFFF, 0x3FFFF, 0x7FFFF, 0xFFFFF,
0x1FFFFF, 0x3FFFFF, 0x7FFFFF, 0xFFFFFF,
0x1FFFFFF, 0x3FFFFFF, 0x7FFFFFF, 0xFFFFFFF,
0x1FFFFFFF, 0x3FFFFFFF, 0x7FFFFFFF, 0xFFFFFFFF,
]);
// The following code was generated with the moman/finenight pkg
// This package is available under the MIT License, see NOTICE.txt
// for more details.
// This class is auto-generated, Please do not modify it directly.
// You should modify the https://gitlab.com/notriddle/createAutomata.py instead.
// The following code was generated with the moman/finenight pkg
// This package is available under the MIT License, see NOTICE.txt
// for more details.
// This class is auto-generated, Please do not modify it directly.
// You should modify https://gitlab.com/notriddle/moman-rustdoc instead.
class Lev2TParametricDescription extends ParametricDescription {
/**
* @param {number} absState
* @param {number} position
* @param {number} vector
* @returns {number}
*/
transition(absState, position, vector) {
let state = Math.floor(absState / (this.w + 1));
let offset = absState % (this.w + 1);
if (position === this.w) {
if (state < 3) {
const loc = Math.imul(vector, 3) + state;
offset += this.unpack(this.offsetIncrs0, loc, 1);
state = this.unpack(this.toStates0, loc, 2) - 1;
}
} else if (position === this.w - 1) {
if (state < 5) {
const loc = Math.imul(vector, 5) + state;
offset += this.unpack(this.offsetIncrs1, loc, 1);
state = this.unpack(this.toStates1, loc, 3) - 1;
}
} else if (position === this.w - 2) {
if (state < 13) {
const loc = Math.imul(vector, 13) + state;
offset += this.unpack(this.offsetIncrs2, loc, 2);
state = this.unpack(this.toStates2, loc, 4) - 1;
}
} else if (position === this.w - 3) {
if (state < 28) {
const loc = Math.imul(vector, 28) + state;
offset += this.unpack(this.offsetIncrs3, loc, 2);
state = this.unpack(this.toStates3, loc, 5) - 1;
}
} else if (position === this.w - 4) {
if (state < 45) {
const loc = Math.imul(vector, 45) + state;
offset += this.unpack(this.offsetIncrs4, loc, 3);
state = this.unpack(this.toStates4, loc, 6) - 1;
}
} else {
// eslint-disable-next-line no-lonely-if
if (state < 45) {
const loc = Math.imul(vector, 45) + state;
offset += this.unpack(this.offsetIncrs5, loc, 3);
state = this.unpack(this.toStates5, loc, 6) - 1;
}
}
if (state === -1) {
// null state
return -1;
} else {
// translate back to abs
return Math.imul(state, this.w + 1) + offset;
}
}
// state map
// 0 -> [(0, 0)]
// 1 -> [(0, 1)]
// 2 -> [(0, 2)]
// 3 -> [(0, 1), (1, 1)]
// 4 -> [(0, 2), (1, 2)]
// 5 -> [(0, 1), (1, 1), (2, 1)]
// 6 -> [(0, 2), (1, 2), (2, 2)]
// 7 -> [(0, 1), (2, 1)]
// 8 -> [(0, 1), (2, 2)]
// 9 -> [(0, 2), (2, 1)]
// 10 -> [(0, 2), (2, 2)]
// 11 -> [t(0, 1), (0, 1), (1, 1), (2, 1)]
// 12 -> [t(0, 2), (0, 2), (1, 2), (2, 2)]
// 13 -> [(0, 2), (1, 2), (2, 2), (3, 2)]
// 14 -> [(0, 1), (1, 1), (3, 2)]
// 15 -> [(0, 1), (2, 2), (3, 2)]
// 16 -> [(0, 1), (3, 2)]
// 17 -> [(0, 1), t(1, 2), (2, 2), (3, 2)]
// 18 -> [(0, 2), (1, 2), (3, 1)]
// 19 -> [(0, 2), (1, 2), (3, 2)]
// 20 -> [(0, 2), (1, 2), t(1, 2), (2, 2), (3, 2)]
// 21 -> [(0, 2), (2, 1), (3, 1)]
// 22 -> [(0, 2), (2, 2), (3, 2)]
// 23 -> [(0, 2), (3, 1)]
// 24 -> [(0, 2), (3, 2)]
// 25 -> [(0, 2), t(1, 2), (1, 2), (2, 2), (3, 2)]
// 26 -> [t(0, 2), (0, 2), (1, 2), (2, 2), (3, 2)]
// 27 -> [t(0, 2), (0, 2), (1, 2), (3, 1)]
// 28 -> [(0, 2), (1, 2), (2, 2), (3, 2), (4, 2)]
// 29 -> [(0, 2), (1, 2), (2, 2), (4, 2)]
// 30 -> [(0, 2), (1, 2), (2, 2), t(2, 2), (3, 2), (4, 2)]
// 31 -> [(0, 2), (1, 2), (3, 2), (4, 2)]
// 32 -> [(0, 2), (1, 2), (4, 2)]
// 33 -> [(0, 2), (1, 2), t(1, 2), (2, 2), (3, 2), (4, 2)]
// 34 -> [(0, 2), (1, 2), t(2, 2), (2, 2), (3, 2), (4, 2)]
// 35 -> [(0, 2), (2, 1), (4, 2)]
// 36 -> [(0, 2), (2, 2), (3, 2), (4, 2)]
// 37 -> [(0, 2), (2, 2), (4, 2)]
// 38 -> [(0, 2), (3, 2), (4, 2)]
// 39 -> [(0, 2), (4, 2)]
// 40 -> [(0, 2), t(1, 2), (1, 2), (2, 2), (3, 2), (4, 2)]
// 41 -> [(0, 2), t(2, 2), (2, 2), (3, 2), (4, 2)]
// 42 -> [t(0, 2), (0, 2), (1, 2), (2, 2), (3, 2), (4, 2)]
// 43 -> [t(0, 2), (0, 2), (1, 2), (2, 2), (4, 2)]
// 44 -> [t(0, 2), (0, 2), (1, 2), (2, 2), t(2, 2), (3, 2), (4, 2)]
/** @param {number} w - length of word being checked */
constructor(w) {
super(w, 2, new Int32Array([
0,1,2,0,1,-1,0,-1,0,-1,0,-1,0,-1,-1,-1,-1,-1,-2,-1,-1,-2,-1,-2,
-1,-1,-1,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,
]));
}
}
Lev2TParametricDescription.prototype.toStates0 = /*2 bits per value */ new Int32Array([
0xe,
]);
Lev2TParametricDescription.prototype.offsetIncrs0 = /*1 bits per value */ new Int32Array([
0x0,
]);
Lev2TParametricDescription.prototype.toStates1 = /*3 bits per value */ new Int32Array([
0x1a688a2c,
]);
Lev2TParametricDescription.prototype.offsetIncrs1 = /*1 bits per value */ new Int32Array([
0x3e0,
]);
Lev2TParametricDescription.prototype.toStates2 = /*4 bits per value */ new Int32Array([
0x70707054,0xdc07035,0x3dd3a3a,0x2323213a,
0x15435223,0x22545432,0x5435,
]);
Lev2TParametricDescription.prototype.offsetIncrs2 = /*2 bits per value */ new Int32Array([
0x80000,0x55582088,0x55555555,0x55,
]);
Lev2TParametricDescription.prototype.toStates3 = /*5 bits per value */ new Int32Array([
0x1c0380a4,0x700a570,0xca529c0,0x180a00,
0xa80af180,0xc5498e60,0x5a546398,0x8c4300e8,
0xac18c601,0xd8d43501,0x863500ad,0x51976d6a,
0x8ca0180a,0xc3501ac2,0xb0c5be16,0x76dda8a5,
0x18c4519,0xc41294a,0xe248d231,0x1086520c,
0xce31ac42,0x13946358,0x2d0348c4,0x6732d494,
0x1ad224a5,0xd635ad4b,0x520c4139,0xce24948,
0x22110a52,0x58ce729d,0xc41394e3,0x941cc520,
0x90e732d4,0x4729d224,0x39ce35ad,
]);
Lev2TParametricDescription.prototype.offsetIncrs3 = /*2 bits per value */ new Int32Array([
0x80000,0xc0c830,0x300f3c30,0x2200fcff,
0xcaa00a08,0x3c2200a8,0xa8fea00a,0x55555555,
0x55555555,0x55555555,0x55555555,0x55555555,
0x55555555,0x55555555,
]);
Lev2TParametricDescription.prototype.toStates4 = /*6 bits per value */ new Int32Array([
0x801c0144,0x1453803,0x14700038,0xc0005145,
0x1401,0x14,0x140000,0x0,
0x510000,0x6301f007,0x301f00d1,0xa186178,
0xc20ca0c3,0xc20c30,0xc30030c,0xc00c00cd,
0xf0c00c30,0x4c054014,0xc30944c3,0x55150c34,
0x8300550,0x430c0143,0x50c31,0xc30850c,
0xc3143000,0x50053c50,0x5130d301,0x850d30c2,
0x30a08608,0xc214414,0x43142145,0x21450031,
0x1400c314,0x4c143145,0x32832803,0x28014d6c,
0xcd34a0c3,0x1c50c76,0x1c314014,0x430c30c3,
0x1431,0xc300500,0xca00d303,0xd36d0e40,
0x90b0e400,0xcb2abb2c,0x70c20ca1,0x2c32ca2c,
0xcd2c70cb,0x31c00c00,0x34c2c32c,0x5583280,
0x558309b7,0x6cd6ca14,0x430850c7,0x51c51401,
0x1430c714,0xc3087,0x71451450,0xca00d30,
0xc26dc156,0xb9071560,0x1cb2abb2,0xc70c2144,
0xb1c51ca1,0x1421c70c,0xc51c00c3,0x30811c51,
0x24324308,0xc51031c2,0x70820820,0x5c33830d,
0xc33850c3,0x30c30c30,0xc30c31c,0x451450c3,
0x20c20c20,0xda0920d,0x5145914f,0x36596114,
0x51965865,0xd9643653,0x365a6590,0x51964364,
0x43081505,0x920b2032,0x2c718b28,0xd7242249,
0x35cb28b0,0x2cb3872c,0x972c30d7,0xb0c32cb2,
0x4e1c75c,0xc80c90c2,0x62ca2482,0x4504171c,
0xd65d9610,0x33976585,0xd95cb5d,0x4b5ca5d7,
0x73975c36,0x10308138,0xc2245105,0x41451031,
0x14e24208,0xc35c3387,0x51453851,0x1c51c514,
0xc70c30c3,0x20451450,0x14f1440c,0x4f0da092,
0x4513d41,0x6533944d,0x1350e658,0xe1545055,
0x64365a50,0x5519383,0x51030815,0x28920718,
0x441c718b,0x714e2422,0x1c35cb28,0x4e1c7387,
0xb28e1c51,0x5c70c32c,0xc204e1c7,0x81c61440,
0x1c62ca24,0xd04503ce,0x85d63944,0x39338e65,
0x8e154387,0x364b5ca3,0x38739738,
]);
Lev2TParametricDescription.prototype.offsetIncrs4 = /*3 bits per value */ new Int32Array([
0x10000000,0xc00000,0x60061,0x400,
0x0,0x80010008,0x249248a4,0x8229048,
0x2092,0x6c3603,0xb61b6c30,0x6db6036d,
0xdb6c0,0x361b0180,0x91b72000,0xdb11b71b,
0x6db6236,0x1008200,0x12480012,0x24924906,
0x48200049,0x80410002,0x24000900,0x4924a489,
0x10822492,0x20800125,0x48360,0x9241b692,
0x6da4924,0x40009268,0x241b010,0x291b4900,
0x6d249249,0x49493423,0x92492492,0x24924924,
0x49249249,0x92492492,0x24924924,0x49249249,
0x92492492,0x24924924,0x49249249,0x92492492,
0x24924924,0x49249249,0x92492492,0x24924924,
0x49249249,0x92492492,0x24924924,0x49249249,
0x92492492,0x24924924,0x49249249,0x92492492,
0x24924924,0x49249249,0x92492492,0x24924924,
0x49249249,0x92492492,0x24924924,0x49249249,
0x92492492,0x24924924,0x49249249,0x2492,
]);
Lev2TParametricDescription.prototype.toStates5 = /*6 bits per value */ new Int32Array([
0x801c0144,0x1453803,0x14700038,0xc0005145,
0x1401,0x14,0x140000,0x0,
0x510000,0x4e00e007,0xe0051,0x3451451c,
0xd015000,0x30cd0000,0xc30c30c,0xc30c30d4,
0x40c30c30,0x7c01c014,0xc03458c0,0x185e0c07,
0x2830c286,0x830c3083,0xc30030,0x33430c,
0x30c3003,0x70051030,0x16301f00,0x8301f00d,
0x30a18617,0xc20ca0c,0x431420c3,0xb1450c51,
0x14314315,0x4f143145,0x34c05401,0x4c30944c,
0x55150c3,0x30830055,0x1430c014,0xc00050c3,
0xc30850,0xc314300,0x150053c5,0x25130d30,
0x5430d30c,0xc0354154,0x300d0c90,0x1cb2cd0c,
0xc91cb0c3,0x72c30cb2,0x14f1cb2c,0xc34c0540,
0x34c30944,0x82182214,0x851050c2,0x50851430,
0x1400c50c,0x30c5085,0x50c51450,0x150053c,
0xc25130d3,0x8850d30,0x1430a086,0x450c2144,
0x51cb1c21,0x1c91c70c,0xc71c314b,0x34c1cb1,
0x6c328328,0xc328014d,0x76cd34a0,0x1401c50c,
0xc31c3140,0x31430c30,0x14,0x30c3005,
0xa0ca00d3,0x535b0c,0x4d2830ca,0x514369b3,
0xc500d01,0x5965965a,0x30d46546,0x6435030c,
0x8034c659,0xdb439032,0x2c390034,0xcaaecb24,
0x30832872,0xcb28b1c,0x4b1c32cb,0x70030033,
0x30b0cb0c,0xe40ca00d,0x400d36d0,0xb2c90b0e,
0xca1cb2ab,0xa2c70c20,0x6575d95c,0x4315b5ce,
0x95c53831,0x28034c5d,0x9b705583,0xa1455830,
0xc76cd6c,0x40143085,0x71451c51,0x871430c,
0x450000c3,0xd3071451,0x1560ca00,0x560c26dc,
0xb35b2851,0xc914369,0x1a14500d,0x46593945,
0xcb2c939,0x94507503,0x328034c3,0x9b70558,
0xe41c5583,0x72caaeca,0x1c308510,0xc7147287,
0x50871c32,0x1470030c,0xd307147,0xc1560ca0,
0x1560c26d,0xabb2b907,0x21441cb2,0x38a1c70c,
0x8e657394,0x314b1c93,0x39438738,0x43083081,
0x31c22432,0x820c510,0x830d7082,0x50c35c33,
0xc30c338,0xc31c30c3,0x50c30c30,0xc204514,
0x890c90c2,0x31440c70,0xa8208208,0xea0df0c3,
0x8a231430,0xa28a28a2,0x28a28a1e,0x1861868a,
0x48308308,0xc3682483,0x14516453,0x4d965845,
0xd4659619,0x36590d94,0xd969964,0x546590d9,
0x20c20541,0x920d20c,0x5914f0da,0x96114514,
0x65865365,0xe89d3519,0x99e7a279,0x9e89e89e,
0x81821827,0xb2032430,0x18b28920,0x422492c7,
0xb28b0d72,0x3872c35c,0xc30d72cb,0x32cb2972,
0x1c75cb0c,0xc90c204e,0xa2482c80,0x24b1c62c,
0xc3a89089,0xb0ea2e42,0x9669a31c,0xa4966a28,
0x59a8a269,0x8175e7a,0xb203243,0x718b2892,
0x4114105c,0x17597658,0x74ce5d96,0x5c36572d,
0xd92d7297,0xe1ce5d70,0xc90c204,0xca2482c8,
0x4171c62,0x5d961045,0x976585d6,0x79669533,
0x964965a2,0x659689e6,0x308175e7,0x24510510,
0x451031c2,0xe2420841,0x5c338714,0x453851c3,
0x51c51451,0xc30c31c,0x451450c7,0x41440c20,
0xc708914,0x82105144,0xf1c58c90,0x1470ea0d,
0x61861863,0x8a1e85e8,0x8687a8a2,0x3081861,
0x24853c51,0x5053c368,0x1341144f,0x96194ce5,
0x1544d439,0x94385514,0xe0d90d96,0x5415464,
0x4f1440c2,0xf0da0921,0x4513d414,0x533944d0,
0x350e6586,0x86082181,0xe89e981d,0x18277689,
0x10308182,0x89207185,0x41c718b2,0x14e24224,
0xc35cb287,0xe1c73871,0x28e1c514,0xc70c32cb,
0x204e1c75,0x1c61440c,0xc62ca248,0x90891071,
0x2e41c58c,0xa31c70ea,0xe86175e7,0xa269a475,
0x5e7a57a8,0x51030817,0x28920718,0xf38718b,
0xe5134114,0x39961758,0xe1ce4ce,0x728e3855,
0x5ce0d92d,0xc204e1ce,0x81c61440,0x1c62ca24,
0xd04503ce,0x85d63944,0x75338e65,0x5d86075e,
0x89e69647,0x75e76576,
]);
Lev2TParametricDescription.prototype.offsetIncrs5 = /*3 bits per value */ new Int32Array([
0x10000000,0xc00000,0x60061,0x400,
0x0,0x60000008,0x6b003080,0xdb6ab6db,
0x2db6,0x800400,0x49245240,0x11482412,
0x104904,0x40020000,0x92292000,0xa4b25924,
0x9649658,0xd80c000,0xdb0c001b,0x80db6d86,
0x6db01b6d,0xc0600003,0x86000d86,0x6db6c36d,
0xddadb6ed,0x300001b6,0x6c360,0xe37236e4,
0x46db6236,0xdb6c,0x361b018,0xb91b7200,
0x6dbb1b71,0x6db763,0x20100820,0x61248001,
0x92492490,0x24820004,0x8041000,0x92400090,
0x24924830,0x555b6a49,0x2080012,0x20004804,
0x49252449,0x84112492,0x4000928,0x240201,
0x92922490,0x58924924,0x49456,0x120d8082,
0x6da4800,0x69249249,0x249a01b,0x6c04100,
0x6d240009,0x92492483,0x24d5adb4,0x60208001,
0x92000483,0x24925236,0x6846da49,0x10400092,
0x241b0,0x49291b49,0x636d2492,0x92494935,
0x24924924,0x49249249,0x92492492,0x24924924,
0x49249249,0x92492492,0x24924924,0x49249249,
0x92492492,0x24924924,0x49249249,0x92492492,
0x24924924,0x49249249,0x92492492,0x24924924,
0x49249249,0x92492492,0x24924924,0x49249249,
0x92492492,0x24924924,0x49249249,0x92492492,
0x24924924,0x49249249,0x92492492,0x24924924,
0x49249249,0x92492492,0x24924924,0x49249249,
0x92492492,0x24924924,0x49249249,0x92492492,
0x24924924,0x49249249,0x92492492,0x24924924,
0x49249249,0x92492492,0x24924924,0x49249249,
0x92492492,0x24924924,0x49249249,0x92492492,
0x24924924,0x49249249,0x92492492,0x24924924,
0x49249249,0x92492492,0x24924924,0x49249249,
0x92492492,0x24924924,0x49249249,0x92492492,
0x24924924,0x49249249,0x92492492,0x24924924,
0x49249249,0x92492492,0x24924924,
]);
class Lev1TParametricDescription extends ParametricDescription {
/**
* @param {number} absState
* @param {number} position
* @param {number} vector
* @returns {number}
*/
transition(absState, position, vector) {
let state = Math.floor(absState / (this.w + 1));
let offset = absState % (this.w + 1);
if (position === this.w) {
if (state < 2) {
const loc = Math.imul(vector, 2) + state;
offset += this.unpack(this.offsetIncrs0, loc, 1);
state = this.unpack(this.toStates0, loc, 2) - 1;
}
} else if (position === this.w - 1) {
if (state < 3) {
const loc = Math.imul(vector, 3) + state;
offset += this.unpack(this.offsetIncrs1, loc, 1);
state = this.unpack(this.toStates1, loc, 2) - 1;
}
} else if (position === this.w - 2) {
if (state < 6) {
const loc = Math.imul(vector, 6) + state;
offset += this.unpack(this.offsetIncrs2, loc, 2);
state = this.unpack(this.toStates2, loc, 3) - 1;
}
} else {
// eslint-disable-next-line no-lonely-if
if (state < 6) {
const loc = Math.imul(vector, 6) + state;
offset += this.unpack(this.offsetIncrs3, loc, 2);
state = this.unpack(this.toStates3, loc, 3) - 1;
}
}
if (state === -1) {
// null state
return -1;
} else {
// translate back to abs
return Math.imul(state, this.w + 1) + offset;
}
}
// state map
// 0 -> [(0, 0)]
// 1 -> [(0, 1)]
// 2 -> [(0, 1), (1, 1)]
// 3 -> [(0, 1), (1, 1), (2, 1)]
// 4 -> [(0, 1), (2, 1)]
// 5 -> [t(0, 1), (0, 1), (1, 1), (2, 1)]
/** @param {number} w - length of word being checked */
constructor(w) {
super(w, 1, new Int32Array([0,1,0,-1,-1,-1]));
}
}
Lev1TParametricDescription.prototype.toStates0 = /*2 bits per value */ new Int32Array([
0x2,
]);
Lev1TParametricDescription.prototype.offsetIncrs0 = /*1 bits per value */ new Int32Array([
0x0,
]);
Lev1TParametricDescription.prototype.toStates1 = /*2 bits per value */ new Int32Array([
0xa43,
]);
Lev1TParametricDescription.prototype.offsetIncrs1 = /*1 bits per value */ new Int32Array([
0x38,
]);
Lev1TParametricDescription.prototype.toStates2 = /*3 bits per value */ new Int32Array([
0x12180003,0xb45a4914,0x69,
]);
Lev1TParametricDescription.prototype.offsetIncrs2 = /*2 bits per value */ new Int32Array([
0x558a0000,0x5555,
]);
Lev1TParametricDescription.prototype.toStates3 = /*3 bits per value */ new Int32Array([
0x900c0003,0xa1904864,0x45a49169,0x5a6d196a,
0x9634,
]);
Lev1TParametricDescription.prototype.offsetIncrs3 = /*2 bits per value */ new Int32Array([
0xa0fc0000,0x5555ba08,0x55555555,
]);