commit d70655b71c66882a71bcc711fdb5fa230fbd6344
parent 8af69a904487761634f2fc1e396ec9a90a519f84
Author: Florian Dold <florian@dold.me>
Date: Wed, 8 Jul 2026 21:43:45 +0200
idb-bridge: remove support for memory/json backend for IndexedDB
Diffstat:
9 files changed, 7 insertions(+), 5068 deletions(-)
diff --git a/packages/idb-bridge/src/MemoryBackend.test.ts b/packages/idb-bridge/src/MemoryBackend.test.ts
@@ -1,69 +0,0 @@
-/*
- Copyright 2019 Florian Dold
-
- Licensed under the Apache License, Version 2.0 (the "License");
- you may not use this file except in compliance with the License.
- You may obtain a copy of the License at
-
- http://www.apache.org/licenses/LICENSE-2.0
-
- Unless required by applicable law or agreed to in writing, software
- distributed under the License is distributed on an "AS IS" BASIS,
- WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
- or implied. See the License for the specific language governing
- permissions and limitations under the License.
- */
-
-import { test } from "node:test";
-import assert from "node:assert";
-import { MemoryBackend } from "./MemoryBackend.js";
-import { BridgeIDBDatabase, BridgeIDBFactory } from "./bridge-idb.js";
-import { promiseFromRequest, promiseFromTransaction } from "./idbpromutil.js";
-
-test("export", async (t) => {
- const backend = new MemoryBackend();
- const idb = new BridgeIDBFactory(backend);
-
- const request = idb.open("library", 42);
- request.onupgradeneeded = () => {
- const db = request.result;
- const store = db.createObjectStore("books", { keyPath: "isbn" });
- const titleIndex = store.createIndex("by_title", "title", { unique: true });
- const authorIndex = store.createIndex("by_author", "author");
- };
-
- const db: BridgeIDBDatabase = await promiseFromRequest(request);
-
- const tx = db.transaction("books", "readwrite");
- tx.oncomplete = () => {
- console.log("oncomplete called");
- };
-
- const store = tx.objectStore("books");
-
- store.put({ title: "Quarry Memories", author: "Fred", isbn: 123456 });
- store.put({ title: "Water Buffaloes", author: "Fred", isbn: 234567 });
- store.put({ title: "Bedrock Nights", author: "Barney", isbn: 345678 });
-
- await promiseFromTransaction(tx);
-
- const exportedData = backend.exportDump();
- const backend2 = new MemoryBackend();
- backend2.importDump(exportedData);
- const exportedData2 = backend2.exportDump();
-
- assert.ok(
- exportedData.databases["library"].objectStores["books"].records.length ===
- 3,
- );
- assert.deepStrictEqual(exportedData, exportedData2);
-
- assert.strictEqual(
- exportedData.databases["library"].schema.databaseVersion,
- 42,
- );
- assert.strictEqual(
- exportedData2.databases["library"].schema.databaseVersion,
- 42,
- );
-});
diff --git a/packages/idb-bridge/src/MemoryBackend.ts b/packages/idb-bridge/src/MemoryBackend.ts
@@ -14,82 +14,11 @@
permissions and limitations under the License.
*/
-import { AsyncCondition, TransactionLevel } from "./backend-common.js";
-import {
- Backend,
- ConnectResult,
- DatabaseConnection,
- DatabaseTransaction,
- IndexGetQuery,
- IndexMeta,
- ObjectStoreGetQuery,
- ObjectStoreMeta,
- RecordGetResponse,
- RecordStoreRequest,
- RecordStoreResponse,
- ResultLevel,
- StoreLevel,
-} from "./backend-interface.js";
-import { BridgeIDBKeyRange } from "./bridge-idb.js";
-import { IDBKeyRange, IDBTransactionMode, IDBValidKey } from "./idbtypes.js";
-import BTree, { ISortedMapF, ISortedSetF } from "./tree/b+tree.js";
-import { compareKeys } from "./util/cmp.js";
-import { ConstraintError, DataError } from "./util/errors.js";
-import { getIndexKeys } from "./util/getIndexKeys.js";
-import { StoreKeyResult, makeStoreKeyValue } from "./util/makeStoreKeyValue.js";
-import {
- structuredClone,
- structuredEncapsulate,
- structuredRevive,
-} from "./util/structuredClone.js";
+import { IDBValidKey } from "./idbtypes.js";
type Key = IDBValidKey;
type Value = unknown;
-interface ObjectStore {
- originalName: string;
- modifiedName: string | undefined;
- originalData: ISortedMapF<Key, ObjectStoreRecord>;
- modifiedData: ISortedMapF<Key, ObjectStoreRecord> | undefined;
- deleted: boolean;
- originalKeyGenerator: number;
- modifiedKeyGenerator: number | undefined;
- committedIndexes: { [name: string]: Index };
- modifiedIndexes: { [name: string]: Index };
-}
-
-interface Index {
- originalName: string;
- modifiedName: string | undefined;
- originalData: ISortedMapF<Key, IndexRecord>;
- modifiedData: ISortedMapF<Key, IndexRecord> | undefined;
- deleted: boolean;
-}
-
-interface Database {
- committedObjectStores: { [name: string]: ObjectStore };
- committedSchema: Schema;
- /**
- * Was the transaction deleted during the running transaction?
- */
- deleted: boolean;
-
- txLevel: TransactionLevel;
-
- txOwnerConnectionCookie?: string;
- txOwnerTransactionCookie?: string;
-
- /**
- * Object stores that the transaction is allowed to access.
- */
- txRestrictObjectStores: string[] | undefined;
-
- /**
- * Connection cookies of current connections.
- */
- connectionCookies: string[];
-}
-
export interface ObjectStoreDump {
name: string;
keyGenerator: number;
@@ -123,96 +52,12 @@ export interface Schema {
objectStores: { [name: string]: ObjectStoreProperties };
}
-interface ObjectStoreMapEntry {
- store: ObjectStore;
- indexMap: { [currentName: string]: Index };
-}
-
-interface Connection {
- dbName: string;
-
- modifiedSchema: Schema;
-
- /**
- * Map from the effective name of an object store during
- * the transaction to the real name.
- */
- objectStoreMap: { [currentName: string]: ObjectStoreMapEntry };
-}
-
-/** @public */
-export interface IndexRecord {
- indexKey: Key;
- primaryKeys: ISortedSetF<Key>;
-}
-
/** @public */
export interface ObjectStoreRecord {
primaryKey: Key;
value: Value;
}
-function nextStoreKey<T>(
- forward: boolean,
- data: ISortedMapF<Key, ObjectStoreRecord>,
- k: Key | undefined,
-) {
- if (k === undefined || k === null) {
- return undefined;
- }
- const res = forward ? data.nextHigherPair(k) : data.nextLowerPair(k);
- if (!res) {
- return undefined;
- }
- return res[1].primaryKey;
-}
-
-function nextKey(
- forward: boolean,
- tree: ISortedSetF<IDBValidKey>,
- key: IDBValidKey | undefined,
-): IDBValidKey | undefined {
- if (key != null) {
- return forward ? tree.nextHigherKey(key) : tree.nextLowerKey(key);
- }
- return forward ? tree.minKey() : tree.maxKey();
-}
-
-/**
- * Return the key that is furthest in
- * the direction indicated by the 'forward' flag.
- */
-function furthestKey(
- forward: boolean,
- key1: Key | undefined,
- key2: Key | undefined,
-) {
- if (key1 === undefined) {
- return key2;
- }
- if (key2 === undefined) {
- return key1;
- }
- const cmpResult = compareKeys(key1, key2);
- if (cmpResult === 0) {
- // Same result
- return key1;
- }
- if (forward && cmpResult === 1) {
- return key1;
- }
- if (forward && cmpResult === -1) {
- return key2;
- }
- if (!forward && cmpResult === 1) {
- return key2;
- }
- if (!forward && cmpResult === -1) {
- return key1;
- }
- return undefined;
-}
-
export interface AccessStats {
primitiveStatements: number;
writeTransactions: number;
@@ -228,2022 +73,3 @@ function logtrace(m: string, ...args: any[]): void {
// Use stderr
console.error(m, ...args);
}
-
-/**
- * Primitive in-memory backend.
- *
- * @public
- */
-export class MemoryBackend implements Backend {
- private databases: { [name: string]: Database } = {};
-
- private connectionIdCounter = 1;
-
- private transactionIdCounter = 1;
-
- /**
- * Connections by connection cookie.
- */
- private connections: { [name: string]: Connection } = {};
-
- /**
- * Connections by transaction (!!) cookie. In this implementation,
- * at most one transaction can run at the same time per connection.
- */
- private connectionsByTransaction: { [tx: string]: Connection } = {};
-
- /**
- * Condition that is triggered whenever a client disconnects.
- */
- private disconnectCond: AsyncCondition = new AsyncCondition();
-
- /**
- * Condition that is triggered whenever a transaction finishes.
- */
- private transactionDoneCond: AsyncCondition = new AsyncCondition();
-
- afterCommitCallback?: () => Promise<void>;
-
- enableTracing: boolean = false;
-
- trackStats: boolean = true;
-
- accessStats: AccessStats = {
- primitiveStatements: 0,
- readTransactions: 0,
- writeTransactions: 0,
- readsPerStore: {},
- readsPerIndex: {},
- readItemsPerIndex: {},
- readItemsPerStore: {},
- writesPerStore: {},
- };
-
- /**
- * Load the data in this IndexedDB backend from a dump in JSON format.
- *
- * Must be called before any connections to the database backend have
- * been made.
- */
- importDump(dataJson: any) {
- if (this.transactionIdCounter != 1 || this.connectionIdCounter != 1) {
- throw Error(
- "data must be imported before first transaction or connection",
- );
- }
-
- // FIXME: validate!
- const data = structuredRevive(dataJson) as MemoryBackendDump;
-
- if (typeof data !== "object") {
- throw Error("db dump corrupt");
- }
-
- this.databases = {};
-
- for (const dbName of Object.keys(data.databases)) {
- const schema = data.databases[dbName].schema;
- if (typeof schema !== "object") {
- throw Error("DB dump corrupt");
- }
- const objectStores: { [name: string]: ObjectStore } = {};
- for (const objectStoreName of Object.keys(
- data.databases[dbName].objectStores,
- )) {
- const storeSchema = schema.objectStores[objectStoreName];
- const dumpedObjectStore: ObjectStoreDump =
- data.databases[dbName].objectStores[objectStoreName];
-
- const pairs = dumpedObjectStore.records.map((r: any) => {
- return structuredClone([r.primaryKey, r]);
- });
- const objectStoreData: ISortedMapF<Key, ObjectStoreRecord> = new BTree(
- pairs,
- compareKeys,
- );
- const objectStore: ObjectStore = {
- deleted: false,
- modifiedData: undefined,
- modifiedName: undefined,
- modifiedKeyGenerator: undefined,
- originalData: objectStoreData,
- originalName: objectStoreName,
- originalKeyGenerator: dumpedObjectStore.keyGenerator,
- committedIndexes: {},
- modifiedIndexes: {},
- };
- objectStores[objectStoreName] = objectStore;
-
- for (const indexName in storeSchema.indexes) {
- const indexSchema = storeSchema.indexes[indexName];
- const newIndex: Index = {
- deleted: false,
- modifiedData: undefined,
- modifiedName: undefined,
- originalData: new BTree([], compareKeys),
- originalName: indexName,
- };
- objectStore.committedIndexes[indexName] = newIndex;
- objectStoreData.forEach((v, k) => {
- try {
- this.insertIntoIndex(newIndex, k, v.value, indexSchema);
- } catch (e) {
- if (e instanceof DataError) {
- // We don't propagate this error here.
- return;
- }
- throw e;
- }
- });
- }
- }
- const db: Database = {
- deleted: false,
- committedObjectStores: objectStores,
- committedSchema: structuredClone(schema),
- connectionCookies: [],
- txLevel: TransactionLevel.None,
- txRestrictObjectStores: undefined,
- };
- this.databases[dbName] = db;
- }
- }
-
- private makeObjectStoreMap(database: Database): {
- [currentName: string]: ObjectStoreMapEntry;
- } {
- let map: { [currentName: string]: ObjectStoreMapEntry } = {};
- for (let objectStoreName in database.committedObjectStores) {
- const store = database.committedObjectStores[objectStoreName];
- const entry: ObjectStoreMapEntry = {
- store,
- indexMap: Object.assign({}, store.committedIndexes),
- };
- map[objectStoreName] = entry;
- }
- return map;
- }
-
- /**
- * Export the contents of the database to JSON.
- *
- * Only exports data that has been committed.
- */
- exportDump(): MemoryBackendDump {
- this.enableTracing && logtrace("exporting dump");
- const dbDumps: { [name: string]: DatabaseDump } = {};
- for (const dbName of Object.keys(this.databases)) {
- const db = this.databases[dbName];
- const objectStores: { [name: string]: ObjectStoreDump } = {};
- for (const objectStoreName of Object.keys(db.committedObjectStores)) {
- const objectStore = db.committedObjectStores[objectStoreName];
- const objectStoreRecords: ObjectStoreRecord[] = [];
- objectStore.originalData.forEach((v: ObjectStoreRecord) => {
- objectStoreRecords.push(structuredClone(v));
- });
- objectStores[objectStoreName] = {
- name: objectStoreName,
- records: objectStoreRecords,
- keyGenerator: objectStore.originalKeyGenerator,
- };
- }
- const dbDump: DatabaseDump = {
- objectStores,
- schema: structuredClone(this.databases[dbName].committedSchema),
- };
- dbDumps[dbName] = dbDump;
- }
- return structuredEncapsulate({ databases: dbDumps });
- }
-
- async getDatabases(): Promise<{ name: string; version: number }[]> {
- if (this.enableTracing) {
- logtrace("TRACING: getDatabase");
- }
- const dbList = [];
- for (const name in this.databases) {
- dbList.push({
- name,
- version: this.databases[name].committedSchema.databaseVersion,
- });
- }
- return dbList;
- }
-
- async deleteDatabase(name: string): Promise<void> {
- if (this.enableTracing) {
- logtrace(`TRACING: deleteDatabase(${name})`);
- }
- const myDb = this.databases[name];
- if (!myDb) {
- throw Error("db not found");
- }
- if (myDb.committedSchema.databaseName !== name) {
- throw Error("name does not match");
- }
-
- while (myDb.txLevel !== TransactionLevel.None) {
- await this.transactionDoneCond.wait();
- }
-
- myDb.deleted = true;
- delete this.databases[name];
- }
-
- async connectDatabase(name: string): Promise<ConnectResult> {
- if (this.enableTracing) {
- logtrace(`TRACING: connectDatabase(${name})`);
- }
- const connectionId = this.connectionIdCounter++;
- const connectionCookie = `connection-${connectionId}`;
-
- let database = this.databases[name];
- if (!database) {
- const schema: Schema = {
- databaseName: name,
- databaseVersion: 0,
- objectStores: {},
- };
- database = {
- committedSchema: schema,
- deleted: false,
- committedObjectStores: {},
- txLevel: TransactionLevel.None,
- connectionCookies: [],
- txRestrictObjectStores: undefined,
- };
- this.databases[name] = database;
- }
-
- if (database.connectionCookies.includes(connectionCookie)) {
- throw Error("already connected");
- }
-
- database.connectionCookies.push(connectionCookie);
-
- const myConn: Connection = {
- dbName: name,
- objectStoreMap: this.makeObjectStoreMap(database),
- modifiedSchema: structuredClone(database.committedSchema),
- };
-
- this.connections[connectionCookie] = myConn;
-
- return {
- conn: { connectionCookie },
- version: database.committedSchema.databaseVersion,
- objectStores: Object.keys(database.committedSchema.objectStores).sort(),
- };
- }
-
- async beginTransaction(
- conn: DatabaseConnection,
- objectStores: string[],
- mode: IDBTransactionMode,
- ): Promise<DatabaseTransaction> {
- const transactionCookie = `tx-${this.transactionIdCounter++}`;
- if (this.enableTracing) {
- logtrace(`TRACING: beginTransaction ${transactionCookie}`);
- }
- const myConn = this.connections[conn.connectionCookie];
- if (!myConn) {
- throw Error("connection not found");
- }
- const myDb = this.databases[myConn.dbName];
- if (!myDb) {
- throw Error("db not found");
- }
-
- while (myDb.txLevel !== TransactionLevel.None) {
- if (this.enableTracing) {
- logtrace(`TRACING: beginTransaction -- waiting for others to close`);
- }
- await this.transactionDoneCond.wait();
- }
-
- if (mode === "readonly") {
- myDb.txLevel = TransactionLevel.Read;
- } else if (mode === "readwrite") {
- myDb.txLevel = TransactionLevel.Write;
- } else {
- throw Error("unsupported transaction mode");
- }
-
- if (this.trackStats) {
- if (mode === "readonly") {
- this.accessStats.readTransactions++;
- } else if (mode === "readwrite") {
- this.accessStats.writeTransactions++;
- }
- }
-
- myDb.txRestrictObjectStores = [...objectStores];
-
- this.connectionsByTransaction[transactionCookie] = myConn;
-
- return { transactionCookie };
- }
-
- async enterVersionChange(
- conn: DatabaseConnection,
- newVersion: number,
- ): Promise<DatabaseTransaction> {
- if (this.enableTracing) {
- logtrace(`TRACING: enterVersionChange`);
- }
- const transactionCookie = `tx-vc-${this.transactionIdCounter++}`;
- const myConn = this.connections[conn.connectionCookie];
- if (!myConn) {
- throw Error("connection not found");
- }
- const myDb = this.databases[myConn.dbName];
- if (!myDb) {
- throw Error("db not found");
- }
-
- while (myDb.txLevel !== TransactionLevel.None) {
- await this.transactionDoneCond.wait();
- }
-
- myDb.txLevel = TransactionLevel.VersionChange;
- myDb.txOwnerConnectionCookie = conn.connectionCookie;
- myDb.txOwnerTransactionCookie = transactionCookie;
- myDb.txRestrictObjectStores = undefined;
-
- this.connectionsByTransaction[transactionCookie] = myConn;
-
- myConn.modifiedSchema.databaseVersion = newVersion;
-
- return { transactionCookie };
- }
-
- async close(conn: DatabaseConnection): Promise<void> {
- if (this.enableTracing) {
- logtrace(`TRACING: close (${conn.connectionCookie})`);
- }
- const myConn = this.connections[conn.connectionCookie];
- if (!myConn) {
- throw Error("connection not found - already closed?");
- }
- const myDb = this.databases[myConn.dbName];
- if (myDb) {
- // FIXME: what if we're still in a transaction?
- myDb.connectionCookies = myDb.connectionCookies.filter(
- (x) => x != conn.connectionCookie,
- );
- }
- delete this.connections[conn.connectionCookie];
- this.disconnectCond.trigger();
- }
-
- private requireConnectionFromTransaction(
- btx: DatabaseTransaction,
- ): Connection {
- const myConn = this.connectionsByTransaction[btx.transactionCookie];
- if (!myConn) {
- throw Error(`unknown transaction (${btx.transactionCookie})`);
- }
- return myConn;
- }
-
- renameIndex(
- btx: DatabaseTransaction,
- objectStoreName: string,
- oldName: string,
- newName: string,
- ): void {
- if (this.enableTracing) {
- logtrace(`TRACING: renameIndex(?, ${oldName}, ${newName})`);
- }
- const myConn = this.requireConnectionFromTransaction(btx);
- const db = this.databases[myConn.dbName];
- if (!db) {
- throw Error("db not found");
- }
- if (db.txLevel < TransactionLevel.VersionChange) {
- throw Error("only allowed in versionchange transaction");
- }
- let schema = myConn.modifiedSchema;
- if (!schema) {
- throw Error();
- }
- const indexesSchema = schema.objectStores[objectStoreName].indexes;
- if (indexesSchema[newName]) {
- throw new Error("new index name already used");
- }
- if (!indexesSchema) {
- throw new Error("new index name already used");
- }
- const index: Index =
- myConn.objectStoreMap[objectStoreName].indexMap[oldName];
- if (!index) {
- throw Error("old index missing in connection's index map");
- }
- indexesSchema[newName] = indexesSchema[newName];
- delete indexesSchema[oldName];
- myConn.objectStoreMap[objectStoreName].indexMap[newName] = index;
- delete myConn.objectStoreMap[objectStoreName].indexMap[oldName];
- index.modifiedName = newName;
- }
-
- deleteIndex(
- btx: DatabaseTransaction,
- objectStoreName: string,
- indexName: string,
- ): void {
- if (this.enableTracing) {
- logtrace(`TRACING: deleteIndex(${indexName})`);
- }
- const myConn = this.requireConnectionFromTransaction(btx);
- const db = this.databases[myConn.dbName];
- if (!db) {
- throw Error("db not found");
- }
- if (db.txLevel < TransactionLevel.VersionChange) {
- throw Error("only allowed in versionchange transaction");
- }
- let schema = myConn.modifiedSchema;
- if (!schema) {
- throw Error();
- }
- if (!schema.objectStores[objectStoreName].indexes[indexName]) {
- throw new Error("index does not exist");
- }
- const index: Index =
- myConn.objectStoreMap[objectStoreName].indexMap[indexName];
- if (!index) {
- throw Error("old index missing in connection's index map");
- }
- index.deleted = true;
- delete schema.objectStores[objectStoreName].indexes[indexName];
- delete myConn.objectStoreMap[objectStoreName].indexMap[indexName];
- }
-
- deleteObjectStore(btx: DatabaseTransaction, name: string): void {
- if (this.enableTracing) {
- logtrace(
- `TRACING: deleteObjectStore(${name}) in ${btx.transactionCookie}`,
- );
- }
- const myConn = this.requireConnectionFromTransaction(btx);
- const db = this.databases[myConn.dbName];
- if (!db) {
- throw Error("db not found");
- }
- if (db.txLevel < TransactionLevel.VersionChange) {
- throw Error("only allowed in versionchange transaction");
- }
- const schema = myConn.modifiedSchema;
- if (!schema) {
- throw Error();
- }
- const objectStoreProperties = schema.objectStores[name];
- if (!objectStoreProperties) {
- throw Error("object store not found");
- }
- const objectStoreMapEntry = myConn.objectStoreMap[name];
- if (!objectStoreMapEntry) {
- throw Error("object store not found in map");
- }
- const indexNames = Object.keys(objectStoreProperties.indexes);
- for (const indexName of indexNames) {
- this.deleteIndex(btx, name, indexName);
- }
-
- objectStoreMapEntry.store.deleted = true;
- delete myConn.objectStoreMap[name];
- delete schema.objectStores[name];
- }
-
- renameObjectStore(
- btx: DatabaseTransaction,
- oldName: string,
- newName: string,
- ): void {
- if (this.enableTracing) {
- logtrace(`TRACING: renameObjectStore(?, ${oldName}, ${newName})`);
- }
-
- const myConn = this.requireConnectionFromTransaction(btx);
- const db = this.databases[myConn.dbName];
- if (!db) {
- throw Error("db not found");
- }
- if (db.txLevel < TransactionLevel.VersionChange) {
- throw Error("only allowed in versionchange transaction");
- }
- const schema = myConn.modifiedSchema;
- if (!schema) {
- throw Error();
- }
- if (!schema.objectStores[oldName]) {
- throw Error("object store not found");
- }
- if (schema.objectStores[newName]) {
- throw Error("new object store already exists");
- }
- const objectStoreMapEntry = myConn.objectStoreMap[oldName];
- if (!objectStoreMapEntry) {
- throw Error("object store not found in map");
- }
- objectStoreMapEntry.store.modifiedName = newName;
- schema.objectStores[newName] = schema.objectStores[oldName];
- delete schema.objectStores[oldName];
- delete myConn.objectStoreMap[oldName];
- myConn.objectStoreMap[newName] = objectStoreMapEntry;
- }
-
- createObjectStore(
- btx: DatabaseTransaction,
- name: string,
- keyPath: string | string[] | null,
- autoIncrement: boolean,
- ): void {
- if (this.enableTracing) {
- logtrace(`TRACING: createObjectStore(${btx.transactionCookie}, ${name})`);
- }
- const myConn = this.requireConnectionFromTransaction(btx);
- const db = this.databases[myConn.dbName];
- if (!db) {
- throw Error("db not found");
- }
- if (db.txLevel < TransactionLevel.VersionChange) {
- throw Error("only allowed in versionchange transaction");
- }
- const newObjectStore: ObjectStore = {
- deleted: false,
- modifiedName: undefined,
- originalName: name,
- modifiedData: undefined,
- originalData: new BTree([], compareKeys),
- modifiedKeyGenerator: undefined,
- originalKeyGenerator: 1,
- committedIndexes: {},
- modifiedIndexes: {},
- };
- const schema = myConn.modifiedSchema;
- if (!schema) {
- throw Error("no schema for versionchange tx");
- }
- schema.objectStores[name] = {
- autoIncrement,
- keyPath,
- indexes: {},
- };
- myConn.objectStoreMap[name] = { store: newObjectStore, indexMap: {} };
- }
-
- createIndex(
- btx: DatabaseTransaction,
- indexName: string,
- objectStoreName: string,
- keyPath: string | string[],
- multiEntry: boolean,
- unique: boolean,
- ): void {
- if (this.enableTracing) {
- logtrace(`TRACING: createIndex(${indexName})`);
- }
- const myConn = this.requireConnectionFromTransaction(btx);
- const db = this.databases[myConn.dbName];
- if (!db) {
- throw Error("db not found");
- }
- if (db.txLevel < TransactionLevel.VersionChange) {
- throw Error("only allowed in versionchange transaction");
- }
- const indexProperties: IndexProperties = {
- keyPath,
- multiEntry,
- unique,
- };
- const newIndex: Index = {
- deleted: false,
- modifiedData: undefined,
- modifiedName: undefined,
- originalData: new BTree([], compareKeys),
- originalName: indexName,
- };
- myConn.objectStoreMap[objectStoreName].indexMap[indexName] = newIndex;
- const schema = myConn.modifiedSchema;
- if (!schema) {
- throw Error("no schema in versionchange tx");
- }
- const objectStoreProperties = schema.objectStores[objectStoreName];
- if (!objectStoreProperties) {
- throw Error("object store not found");
- }
- objectStoreProperties.indexes[indexName] = indexProperties;
-
- const objectStoreMapEntry = myConn.objectStoreMap[objectStoreName];
- if (!objectStoreMapEntry) {
- throw Error("object store does not exist");
- }
-
- const storeData =
- objectStoreMapEntry.store.modifiedData ||
- objectStoreMapEntry.store.originalData;
-
- storeData.forEach((v, k) => {
- try {
- this.insertIntoIndex(newIndex, k, v.value, indexProperties);
- } catch (e) {
- if (e instanceof DataError) {
- // We don't propagate this error here.
- return;
- }
- throw e;
- }
- });
- }
-
- async clearObjectStore(
- btx: DatabaseTransaction,
- objectStoreName: string,
- ): Promise<void> {
- const myConn = this.requireConnectionFromTransaction(btx);
- const db = this.databases[myConn.dbName];
- if (!db) {
- throw Error("db not found");
- }
- if (db.txLevel < TransactionLevel.Write) {
- throw Error("only allowed in write transaction");
- }
- if (
- db.txRestrictObjectStores &&
- !db.txRestrictObjectStores.includes(objectStoreName)
- ) {
- throw Error(
- `Not allowed to access store '${objectStoreName}', transaction is over ${JSON.stringify(
- db.txRestrictObjectStores,
- )}`,
- );
- }
-
- const schema = myConn.modifiedSchema;
- const objectStoreMapEntry = myConn.objectStoreMap[objectStoreName];
-
- objectStoreMapEntry.store.modifiedData = new BTree([], compareKeys);
-
- for (const indexName of Object.keys(
- schema.objectStores[objectStoreName].indexes,
- )) {
- const index = myConn.objectStoreMap[objectStoreName].indexMap[indexName];
- if (!index) {
- throw Error("index referenced by object store does not exist");
- }
- index.modifiedData = new BTree([], compareKeys);
- }
- }
-
- async deleteRecord(
- btx: DatabaseTransaction,
- objectStoreName: string,
- range: IDBKeyRange,
- ): Promise<void> {
- if (this.enableTracing) {
- logtrace(`TRACING: deleteRecord from store ${objectStoreName}`);
- }
- const myConn = this.requireConnectionFromTransaction(btx);
- const db = this.databases[myConn.dbName];
- if (!db) {
- throw Error("db not found");
- }
- if (db.txLevel < TransactionLevel.Write) {
- throw Error("only allowed in write transaction");
- }
- if (
- db.txRestrictObjectStores &&
- !db.txRestrictObjectStores.includes(objectStoreName)
- ) {
- throw Error(
- `Not allowed to access store '${objectStoreName}', transaction is over ${JSON.stringify(
- db.txRestrictObjectStores,
- )}`,
- );
- }
- if (typeof range !== "object") {
- throw Error("deleteRecord got invalid range (must be object)");
- }
- if (!("lowerOpen" in range)) {
- throw Error(
- "deleteRecord got invalid range (sanity check failed, 'lowerOpen' missing)",
- );
- }
-
- const schema = myConn.modifiedSchema;
- const objectStoreMapEntry = myConn.objectStoreMap[objectStoreName];
-
- if (!objectStoreMapEntry.store.modifiedData) {
- objectStoreMapEntry.store.modifiedData =
- objectStoreMapEntry.store.originalData;
- }
-
- let modifiedData = objectStoreMapEntry.store.modifiedData;
- let currKey: Key | undefined;
-
- if (range.lower === undefined || range.lower === null) {
- currKey = modifiedData.minKey();
- } else {
- currKey = range.lower;
- // We have a range with an lowerOpen lower bound, so don't start
- // deleting the lower bound. Instead start with the next higher key.
- if (range.lowerOpen && currKey !== undefined) {
- currKey = modifiedData.nextHigherKey(currKey);
- }
- }
-
- if (currKey === undefined) {
- throw Error("invariant violated");
- }
-
- // make sure that currKey is either undefined or pointing to an
- // existing object.
- let firstValue = modifiedData.get(currKey);
- if (!firstValue) {
- if (currKey !== undefined) {
- currKey = modifiedData.nextHigherKey(currKey);
- }
- }
-
- // loop invariant: (currKey is undefined) or (currKey is a valid key)
- while (true) {
- if (currKey === undefined) {
- // nothing more to delete!
- break;
- }
- if (range.upper !== null && range.upper !== undefined) {
- if (range.upperOpen && compareKeys(currKey, range.upper) === 0) {
- // We have a range that's upperOpen, so stop before we delete the upper bound.
- break;
- }
- if (!range.upperOpen && compareKeys(currKey, range.upper) > 0) {
- // The upper range is inclusive, only stop if we're after the upper range.
- break;
- }
- }
-
- const storeEntry = modifiedData.get(currKey);
- if (!storeEntry) {
- throw Error("assertion failed");
- }
-
- for (const indexName of Object.keys(
- schema.objectStores[objectStoreName].indexes,
- )) {
- const index =
- myConn.objectStoreMap[objectStoreName].indexMap[indexName];
- if (!index) {
- throw Error("index referenced by object store does not exist");
- }
- this.enableTracing &&
- logtrace(
- `deleting from index ${indexName} for object store ${objectStoreName}`,
- );
- const indexProperties =
- schema.objectStores[objectStoreName].indexes[indexName];
- this.deleteFromIndex(
- index,
- storeEntry.primaryKey,
- storeEntry.value,
- indexProperties,
- );
- }
-
- modifiedData = modifiedData.without(currKey);
-
- currKey = modifiedData.nextHigherKey(currKey);
- }
-
- objectStoreMapEntry.store.modifiedData = modifiedData;
- }
-
- private deleteFromIndex(
- index: Index,
- primaryKey: Key,
- value: Value,
- indexProperties: IndexProperties,
- ): void {
- if (this.enableTracing) {
- logtrace(`deleteFromIndex(${index.modifiedName || index.originalName})`);
- }
- if (value === undefined || value === null) {
- throw Error("cannot delete null/undefined value from index");
- }
- let indexData = index.modifiedData || index.originalData;
- const indexKeys = getIndexKeys(
- value,
- indexProperties.keyPath,
- indexProperties.multiEntry,
- );
- for (const indexKey of indexKeys) {
- const existingIndexRecord = indexData.get(indexKey);
- if (!existingIndexRecord) {
- throw Error("db inconsistent: expected index entry missing");
- }
- const newPrimaryKeys =
- existingIndexRecord.primaryKeys.without(primaryKey);
- if (newPrimaryKeys.size === 0) {
- index.modifiedData = indexData.without(indexKey);
- } else {
- const newIndexRecord: IndexRecord = {
- indexKey,
- primaryKeys: newPrimaryKeys,
- };
- index.modifiedData = indexData.with(indexKey, newIndexRecord, true);
- }
- }
- }
-
- async getObjectStoreRecords(
- btx: DatabaseTransaction,
- req: ObjectStoreGetQuery,
- ): Promise<RecordGetResponse> {
- if (this.enableTracing) {
- logtrace(`TRACING: getObjectStoreRecords`);
- logtrace("query", req);
- }
- const myConn = this.requireConnectionFromTransaction(btx);
- const db = this.databases[myConn.dbName];
- if (!db) {
- throw Error("db not found");
- }
- if (db.txLevel < TransactionLevel.Read) {
- throw Error("only allowed while running a transaction");
- }
- if (
- db.txRestrictObjectStores &&
- !db.txRestrictObjectStores.includes(req.objectStoreName)
- ) {
- throw Error(
- `Not allowed to access store '${
- req.objectStoreName
- }', transaction is over ${JSON.stringify(db.txRestrictObjectStores)}`,
- );
- }
- const objectStoreMapEntry = myConn.objectStoreMap[req.objectStoreName];
- if (!objectStoreMapEntry) {
- throw Error("object store not found");
- }
-
- let range;
- if (req.range == null) {
- range = new BridgeIDBKeyRange(undefined, undefined, true, true);
- } else {
- range = req.range;
- }
-
- if (typeof range !== "object") {
- throw Error(
- "getObjectStoreRecords was given an invalid range (sanity check failed, not an object)",
- );
- }
-
- if (!("lowerOpen" in range)) {
- throw Error(
- "getObjectStoreRecords was given an invalid range (sanity check failed, lowerOpen missing)",
- );
- }
-
- const forward: boolean =
- req.direction === "next" || req.direction === "nextunique";
-
- const storeData =
- objectStoreMapEntry.store.modifiedData ||
- objectStoreMapEntry.store.originalData;
-
- const resp = getObjectStoreRecords({
- forward,
- storeData,
- limit: req.limit,
- range,
- resultLevel: req.resultLevel,
- advancePrimaryKey: req.advancePrimaryKey,
- lastObjectStorePosition: req.lastObjectStorePosition,
- });
- if (this.trackStats) {
- const k = `${req.objectStoreName}`;
- this.accessStats.readsPerStore[k] =
- (this.accessStats.readsPerStore[k] ?? 0) + 1;
- this.accessStats.readItemsPerStore[k] =
- (this.accessStats.readItemsPerStore[k] ?? 0) + resp.count;
- }
- if (this.enableTracing) {
- logtrace(`TRACING: getRecords got ${resp.count} results`);
- }
- return resp;
- }
-
- async getIndexRecords(
- btx: DatabaseTransaction,
- req: IndexGetQuery,
- ): Promise<RecordGetResponse> {
- if (this.enableTracing) {
- logtrace(`TRACING: getIndexRecords`);
- logtrace("query", req);
- }
- const myConn = this.requireConnectionFromTransaction(btx);
- const db = this.databases[myConn.dbName];
- if (!db) {
- throw Error("db not found");
- }
- if (db.txLevel < TransactionLevel.Read) {
- throw Error("only allowed while running a transaction");
- }
- if (
- db.txRestrictObjectStores &&
- !db.txRestrictObjectStores.includes(req.objectStoreName)
- ) {
- throw Error(
- `Not allowed to access store '${
- req.objectStoreName
- }', transaction is over ${JSON.stringify(db.txRestrictObjectStores)}`,
- );
- }
- const objectStoreMapEntry = myConn.objectStoreMap[req.objectStoreName];
- if (!objectStoreMapEntry) {
- throw Error("object store not found");
- }
-
- let range;
- if (req.range == null || req.range === undefined) {
- range = new BridgeIDBKeyRange(undefined, undefined, true, true);
- } else {
- range = req.range;
- }
-
- if (typeof range !== "object") {
- throw Error(
- "getRecords was given an invalid range (sanity check failed, not an object)",
- );
- }
-
- if (!("lowerOpen" in range)) {
- throw Error(
- "getRecords was given an invalid range (sanity check failed, lowerOpen missing)",
- );
- }
-
- const forward: boolean =
- req.direction === "next" || req.direction === "nextunique";
- const unique: boolean =
- req.direction === "prevunique" || req.direction === "nextunique";
-
- const storeData =
- objectStoreMapEntry.store.modifiedData ||
- objectStoreMapEntry.store.originalData;
-
- const index =
- myConn.objectStoreMap[req.objectStoreName].indexMap[req.indexName!];
- const indexData = index.modifiedData || index.originalData;
- const resp = getIndexRecords({
- forward,
- indexData,
- storeData,
- limit: req.limit,
- unique,
- range,
- resultLevel: req.resultLevel,
- advanceIndexKey: req.advanceIndexKey,
- advancePrimaryKey: req.advancePrimaryKey,
- lastIndexPosition: req.lastIndexPosition,
- lastObjectStorePosition: req.lastObjectStorePosition,
- });
- if (this.trackStats) {
- const k = `${req.objectStoreName}.${req.indexName}`;
- this.accessStats.readsPerIndex[k] =
- (this.accessStats.readsPerIndex[k] ?? 0) + 1;
- this.accessStats.readItemsPerIndex[k] =
- (this.accessStats.readItemsPerIndex[k] ?? 0) + resp.count;
- }
- if (this.enableTracing) {
- logtrace(`TRACING: getIndexRecords got ${resp.count} results`);
- }
- return resp;
- }
-
- async storeRecord(
- btx: DatabaseTransaction,
- storeReq: RecordStoreRequest,
- ): Promise<RecordStoreResponse> {
- if (this.enableTracing) {
- logtrace(`TRACING: storeRecord`);
- logtrace(
- `key ${storeReq.key}, record ${JSON.stringify(
- structuredEncapsulate(storeReq.value),
- )}`,
- );
- }
- const myConn = this.requireConnectionFromTransaction(btx);
- const db = this.databases[myConn.dbName];
- if (!db) {
- throw Error("db not found");
- }
- if (db.txLevel < TransactionLevel.Write) {
- throw Error("store operation only allowed while running a transaction");
- }
- if (
- db.txRestrictObjectStores &&
- !db.txRestrictObjectStores.includes(storeReq.objectStoreName)
- ) {
- throw Error(
- `Not allowed to access store '${
- storeReq.objectStoreName
- }', transaction is over ${JSON.stringify(db.txRestrictObjectStores)}`,
- );
- }
-
- if (this.trackStats) {
- this.accessStats.writesPerStore[storeReq.objectStoreName] =
- (this.accessStats.writesPerStore[storeReq.objectStoreName] ?? 0) + 1;
- }
-
- const schema = myConn.modifiedSchema;
- const objectStoreMapEntry = myConn.objectStoreMap[storeReq.objectStoreName];
-
- if (!objectStoreMapEntry.store.modifiedData) {
- objectStoreMapEntry.store.modifiedData =
- objectStoreMapEntry.store.originalData;
- }
- const modifiedData = objectStoreMapEntry.store.modifiedData;
-
- let key;
- let value;
-
- if (storeReq.storeLevel === StoreLevel.UpdateExisting) {
- if (storeReq.key === null || storeReq.key === undefined) {
- throw Error("invalid update request (key not given)");
- }
-
- if (!objectStoreMapEntry.store.modifiedData.has(storeReq.key)) {
- throw Error("invalid update request (record does not exist)");
- }
- key = storeReq.key;
- value = storeReq.value;
- } else {
- const keygen =
- objectStoreMapEntry.store.modifiedKeyGenerator ||
- objectStoreMapEntry.store.originalKeyGenerator;
- const autoIncrement =
- schema.objectStores[storeReq.objectStoreName].autoIncrement;
- const keyPath = schema.objectStores[storeReq.objectStoreName].keyPath;
-
- if (
- keyPath !== null &&
- keyPath !== undefined &&
- storeReq.key !== undefined
- ) {
- // If in-line keys are used, a key can't be explicitly specified.
- throw new DataError();
- }
-
- let storeKeyResult: StoreKeyResult;
- try {
- storeKeyResult = makeStoreKeyValue({
- value: storeReq.value,
- key: storeReq.key,
- currentKeyGenerator: keygen,
- autoIncrement: autoIncrement,
- keyPath: keyPath,
- });
- } catch (e) {
- if (e instanceof DataError) {
- const kp = JSON.stringify(keyPath);
- const n = storeReq.objectStoreName;
- const m = `Could not extract key from value, objectStore=${n}, keyPath=${kp}, value=${JSON.stringify(
- storeReq.value,
- )}`;
- if (this.enableTracing) {
- console.error(e);
- console.error("value was:", storeReq.value);
- console.error("key was:", storeReq.key);
- }
- throw new DataError(m);
- } else {
- throw e;
- }
- }
- key = storeKeyResult.key;
- value = storeKeyResult.value;
- objectStoreMapEntry.store.modifiedKeyGenerator =
- storeKeyResult.updatedKeyGenerator;
- const hasKey = modifiedData.has(key);
-
- if (hasKey && storeReq.storeLevel !== StoreLevel.AllowOverwrite) {
- throw new ConstraintError("refusing to overwrite");
- }
- }
-
- const oldStoreRecord = modifiedData.get(key);
-
- const newObjectStoreRecord: ObjectStoreRecord = {
- // FIXME: We should serialize the key here, not just clone it.
- primaryKey: structuredClone(key),
- value: structuredClone(value),
- };
-
- objectStoreMapEntry.store.modifiedData = modifiedData.with(
- key,
- newObjectStoreRecord,
- true,
- );
-
- for (const indexName of Object.keys(
- schema.objectStores[storeReq.objectStoreName].indexes,
- )) {
- const index =
- myConn.objectStoreMap[storeReq.objectStoreName].indexMap[indexName];
- if (!index) {
- throw Error("index referenced by object store does not exist");
- }
- const indexProperties =
- schema.objectStores[storeReq.objectStoreName].indexes[indexName];
-
- // Remove old index entry first!
- if (oldStoreRecord) {
- try {
- this.deleteFromIndex(
- index,
- key,
- oldStoreRecord.value,
- indexProperties,
- );
- } catch (e) {
- if (e instanceof DataError) {
- // Do nothing
- } else {
- throw e;
- }
- }
- }
- try {
- this.insertIntoIndex(index, key, value, indexProperties);
- } catch (e) {
- if (e instanceof DataError) {
- // https://www.w3.org/TR/IndexedDB-2/#object-store-storage-operation
- // Do nothing
- } else {
- throw e;
- }
- }
- }
-
- return { key };
- }
-
- private insertIntoIndex(
- index: Index,
- primaryKey: Key,
- value: Value,
- indexProperties: IndexProperties,
- ): void {
- if (this.enableTracing) {
- logtrace(`insertIntoIndex(${index.modifiedName || index.originalName})`);
- }
- let indexData = index.modifiedData || index.originalData;
- let indexKeys;
- try {
- indexKeys = getIndexKeys(
- value,
- indexProperties.keyPath,
- indexProperties.multiEntry,
- );
- } catch (e) {
- if (e instanceof DataError) {
- const n = index.modifiedName || index.originalName;
- const p = JSON.stringify(indexProperties.keyPath);
- const m = `Failed to extract index keys from index ${n} for keyPath ${p}.`;
- if (this.enableTracing) {
- console.error(m);
- console.error("value was", value);
- }
- throw new DataError(m);
- } else {
- throw e;
- }
- }
- for (const indexKey of indexKeys) {
- const existingRecord = indexData.get(indexKey);
- if (existingRecord) {
- if (indexProperties.unique) {
- throw new ConstraintError();
- } else {
- const newIndexRecord: IndexRecord = {
- indexKey: indexKey,
- primaryKeys: existingRecord.primaryKeys.with(primaryKey),
- };
- index.modifiedData = indexData.with(indexKey, newIndexRecord, true);
- }
- } else {
- const primaryKeys: ISortedSetF<IDBValidKey> = new BTree(
- [[primaryKey, undefined]],
- compareKeys,
- );
- const newIndexRecord: IndexRecord = {
- indexKey: indexKey,
- primaryKeys,
- };
- index.modifiedData = indexData.with(indexKey, newIndexRecord, true);
- }
- }
- }
-
- async rollback(btx: DatabaseTransaction): Promise<void> {
- if (this.enableTracing) {
- logtrace(`TRACING: rollback`);
- }
- const myConn = this.connectionsByTransaction[btx.transactionCookie];
- if (!myConn) {
- throw Error("unknown transaction");
- }
- const db = this.databases[myConn.dbName];
- if (!db) {
- throw Error("db not found");
- }
- if (db.txLevel < TransactionLevel.Read) {
- throw Error("rollback is only allowed while running a transaction");
- }
- db.txLevel = TransactionLevel.None;
- db.txRestrictObjectStores = undefined;
- myConn.modifiedSchema = structuredClone(db.committedSchema);
- myConn.objectStoreMap = this.makeObjectStoreMap(db);
- for (const objectStoreName in db.committedObjectStores) {
- const objectStore = db.committedObjectStores[objectStoreName];
- objectStore.deleted = false;
- objectStore.modifiedData = undefined;
- objectStore.modifiedName = undefined;
- objectStore.modifiedKeyGenerator = undefined;
- objectStore.modifiedIndexes = {};
-
- for (const indexName of Object.keys(
- db.committedSchema.objectStores[objectStoreName].indexes,
- )) {
- const index = objectStore.committedIndexes[indexName];
- index.deleted = false;
- index.modifiedData = undefined;
- index.modifiedName = undefined;
- }
- }
- delete this.connectionsByTransaction[btx.transactionCookie];
- this.transactionDoneCond.trigger();
- }
-
- async commit(btx: DatabaseTransaction): Promise<void> {
- if (this.enableTracing) {
- logtrace(`TRACING: commit`);
- }
- const myConn = this.requireConnectionFromTransaction(btx);
- const db = this.databases[myConn.dbName];
- if (!db) {
- throw Error("db not found");
- }
- const txLevel = db.txLevel;
- if (txLevel < TransactionLevel.Read) {
- throw Error("only allowed while running a transaction");
- }
-
- db.committedSchema = structuredClone(myConn.modifiedSchema);
- db.txLevel = TransactionLevel.None;
- db.txRestrictObjectStores = undefined;
-
- db.committedObjectStores = {};
- db.committedObjectStores = {};
-
- for (const objectStoreName in myConn.objectStoreMap) {
- const objectStoreMapEntry = myConn.objectStoreMap[objectStoreName];
- const store = objectStoreMapEntry.store;
- store.deleted = false;
- store.originalData = store.modifiedData || store.originalData;
- store.originalName = store.modifiedName || store.originalName;
- store.modifiedIndexes = {};
- if (store.modifiedKeyGenerator !== undefined) {
- store.originalKeyGenerator = store.modifiedKeyGenerator;
- }
- db.committedObjectStores[objectStoreName] = store;
-
- for (const indexName in objectStoreMapEntry.indexMap) {
- const index = objectStoreMapEntry.indexMap[indexName];
- index.deleted = false;
- index.originalData = index.modifiedData || index.originalData;
- index.originalName = index.modifiedName || index.originalName;
- store.committedIndexes[indexName] = index;
- }
- }
-
- myConn.objectStoreMap = this.makeObjectStoreMap(db);
-
- delete this.connectionsByTransaction[btx.transactionCookie];
- this.transactionDoneCond.trigger();
-
- if (this.afterCommitCallback && txLevel >= TransactionLevel.Write) {
- await this.afterCommitCallback();
- }
- }
-
- getObjectStoreMeta(
- dbConn: DatabaseConnection,
- objectStoreName: string,
- ): ObjectStoreMeta | undefined {
- const conn = this.connections[dbConn.connectionCookie];
- if (!conn) {
- throw Error("db connection not found");
- }
- let schema = conn.modifiedSchema;
- if (!schema) {
- throw Error();
- }
- const storeInfo = schema.objectStores[objectStoreName];
- if (!storeInfo) {
- return undefined;
- }
- return {
- autoIncrement: storeInfo.autoIncrement,
- indexSet: Object.keys(storeInfo.indexes).sort(),
- keyPath: structuredClone(storeInfo.keyPath),
- };
- }
-
- getIndexMeta(
- dbConn: DatabaseConnection,
- objectStoreName: string,
- indexName: string,
- ): IndexMeta | undefined {
- const conn = this.connections[dbConn.connectionCookie];
- if (!conn) {
- throw Error("db connection not found");
- }
- let schema = conn.modifiedSchema;
- if (!schema) {
- throw Error();
- }
- const storeInfo = schema.objectStores[objectStoreName];
- if (!storeInfo) {
- return undefined;
- }
- const indexInfo = storeInfo.indexes[indexName];
- if (!indexInfo) {
- return;
- }
- return {
- keyPath: structuredClone(indexInfo.keyPath),
- multiEntry: indexInfo.multiEntry,
- unique: indexInfo.unique,
- };
- }
-}
-
-interface Boundary {
- key: Key;
- inclusive: boolean;
-}
-
-function getRangeEndBoundary(
- forward: boolean,
- range: IDBKeyRange | undefined | null,
-): Boundary | undefined {
- let endRangeKey: Uint8Array | undefined = undefined;
- let endRangeInclusive: boolean = false;
- if (range) {
- if (forward && range.upper != null) {
- endRangeKey = range.upper;
- endRangeInclusive = !range.upperOpen;
- } else if (!forward && range.lower != null) {
- endRangeKey = range.lower;
- endRangeInclusive = !range.lowerOpen;
- }
- }
- if (endRangeKey) {
- return {
- inclusive: endRangeInclusive,
- key: endRangeKey,
- };
- }
- return undefined;
-}
-
-function isOutsideBoundary(
- forward: boolean,
- endRange: Boundary,
- currentKey: Key,
-): boolean {
- const cmp = compareKeys(currentKey, endRange.key);
- if (forward && endRange.inclusive && cmp > 0) {
- return true;
- } else if (forward && !endRange.inclusive && cmp >= 0) {
- return true;
- } else if (!forward && endRange.inclusive && cmp < 0) {
- return true;
- } else if (!forward && !endRange.inclusive && cmp <= 0) {
- return true;
- }
- return false;
-}
-
-interface IndexIterPos {
- objectPos: Key;
- indexPos: Key;
-}
-
-type IndexData = ISortedMapF<IDBValidKey, IndexRecord>;
-
-function startIndex(req: {
- indexData: IndexData;
- forward: boolean;
- unique: boolean;
-}): IndexIterPos | undefined {
- const { forward, unique, indexData } = req;
- if (forward) {
- const indexPos = indexData.minKey();
- if (indexPos != null) {
- const indexEntry = indexData.get(indexPos);
- if (!indexEntry) {
- throw Error("data error");
- }
- const objectPos = indexEntry.primaryKeys.minKey();
- if (objectPos != null) {
- return { indexPos, objectPos };
- }
- }
- } else {
- const indexPos = indexData.maxKey();
- if (indexPos != null) {
- const indexEntry = indexData.get(indexPos);
- if (!indexEntry) {
- throw Error("data error");
- }
- let objectPos: Key | undefined;
- if (unique) {
- objectPos = indexEntry.primaryKeys.minKey();
- } else {
- objectPos = indexEntry.primaryKeys.maxKey();
- }
-
- if (objectPos != null) {
- return { indexPos, objectPos };
- }
- }
- }
- return undefined;
-}
-
-function continueIndexForwardInclusive(
- indexData: IndexData,
- targetIndexKey: Key,
- targetObjectKey: Key,
-): IndexIterPos | undefined {
- let indexEntry = indexData.get(targetIndexKey);
- if (indexEntry) {
- if (indexEntry.primaryKeys.has(targetObjectKey)) {
- return {
- indexPos: targetIndexKey,
- objectPos: targetObjectKey,
- };
- } else {
- const objectPos = indexEntry.primaryKeys.nextHigherKey(targetObjectKey);
- if (!objectPos) {
- return undefined;
- }
- return { indexPos: targetIndexKey, objectPos };
- }
- }
-
- const pair = indexData.nextHigherPair(targetIndexKey);
- if (!pair) {
- return undefined;
- }
-
- indexEntry = pair[1];
- const indexPos = pair[0];
-
- const objectPos = indexEntry.primaryKeys.minKey();
- if (!objectPos) {
- return undefined;
- }
-
- return { indexPos, objectPos };
-}
-
-function continueIndexForwardInclusiveUnique(
- indexData: IndexData,
- targetIndexKey: Key,
-): IndexIterPos | undefined {
- const indexEntry = indexData.get(targetIndexKey);
- if (indexEntry) {
- const objectPos = indexEntry.primaryKeys.minKey();
- if (!objectPos) {
- return undefined;
- }
- return {
- indexPos: targetIndexKey,
- objectPos,
- };
- }
- const pair = indexData.nextHigherPair(targetIndexKey);
- if (!pair) {
- return undefined;
- }
- const objectPos = pair[1].primaryKeys.minKey();
- if (!objectPos) {
- return undefined;
- }
- return {
- indexPos: pair[0],
- objectPos,
- };
-}
-
-function continueIndexForwardStrict(
- indexData: IndexData,
- targetIndexKey: Key,
- targetObjectKey: Key,
-): IndexIterPos | undefined {
- let indexEntry = indexData.get(targetIndexKey);
- if (indexEntry) {
- const objectPos = indexEntry.primaryKeys.nextHigherKey(targetObjectKey);
- if (!objectPos) {
- return undefined;
- }
- return { indexPos: targetIndexKey, objectPos };
- }
-
- const pair = indexData.nextHigherPair(targetIndexKey);
- if (!pair) {
- return undefined;
- }
-
- indexEntry = pair[1];
- const indexPos = pair[0];
-
- const objectPos = indexEntry.primaryKeys.minKey();
- if (!objectPos) {
- return undefined;
- }
-
- return { indexPos, objectPos };
-}
-
-function continueIndexForwardStrictUnique(
- indexData: IndexData,
- targetIndexKey: Key,
-): IndexIterPos | undefined {
- const pair = indexData.nextHigherPair(targetIndexKey);
- if (!pair) {
- return undefined;
- }
- const objectPos = pair[1].primaryKeys.minKey();
- if (!objectPos) {
- return undefined;
- }
- return {
- indexPos: pair[0],
- objectPos,
- };
-}
-
-function continueIndexBackwardInclusive(
- indexData: IndexData,
- targetIndexKey: Key,
- targetObjectKey: Key,
-): IndexIterPos | undefined {
- let indexEntry = indexData.get(targetIndexKey);
- if (indexEntry) {
- if (indexEntry.primaryKeys.has(targetObjectKey)) {
- return {
- indexPos: targetIndexKey,
- objectPos: targetObjectKey,
- };
- } else {
- const objectPos = indexEntry.primaryKeys.nextLowerKey(targetObjectKey);
- if (!objectPos) {
- return undefined;
- }
- return { indexPos: targetIndexKey, objectPos };
- }
- }
-
- const pair = indexData.nextLowerPair(targetIndexKey);
- if (!pair) {
- return undefined;
- }
-
- indexEntry = pair[1];
- const indexPos = pair[0];
-
- const objectPos = indexEntry.primaryKeys.maxKey();
- if (!objectPos) {
- return undefined;
- }
-
- return { indexPos, objectPos };
-}
-
-function continueIndexBackwardInclusiveUnique(
- indexData: IndexData,
- targetIndexKey: Key,
-): IndexIterPos | undefined {
- const indexEntry = indexData.get(targetIndexKey);
- if (indexEntry) {
- // Backwards iteration, but still use minKey for object pos
- const objectPos = indexEntry.primaryKeys.minKey();
- if (!objectPos) {
- return undefined;
- }
- return {
- indexPos: targetIndexKey,
- objectPos,
- };
- }
- const pair = indexData.nextLowerPair(targetIndexKey);
- if (!pair) {
- return undefined;
- }
- // Backwards iteration, but still use minKey for object pos
- const objectPos = pair[1].primaryKeys.minKey();
- if (!objectPos) {
- return undefined;
- }
- return {
- indexPos: pair[0],
- objectPos,
- };
-}
-
-function continueIndexBackwardStrict(
- indexData: IndexData,
- targetIndexKey: Key,
- targetObjectKey: Key,
-): IndexIterPos | undefined {
- let indexEntry = indexData.get(targetIndexKey);
- if (indexEntry) {
- const objectPos = indexEntry.primaryKeys.nextLowerKey(targetObjectKey);
- if (!objectPos) {
- return undefined;
- }
- return { indexPos: targetIndexKey, objectPos };
- }
-
- const pair = indexData.nextLowerPair(targetIndexKey);
- if (!pair) {
- return undefined;
- }
-
- indexEntry = pair[1];
- const indexPos = pair[0];
-
- const objectPos = indexEntry.primaryKeys.maxKey();
- if (!objectPos) {
- return undefined;
- }
-
- return { indexPos, objectPos };
-}
-
-function continueIndexBackwardStrictUnique(
- indexData: IndexData,
- targetIndexKey: Key,
-): IndexIterPos | undefined {
- const pair = indexData.nextLowerPair(targetIndexKey);
- if (!pair) {
- return undefined;
- }
- const objectPos = pair[1].primaryKeys.minKey();
- if (!objectPos) {
- return undefined;
- }
- return {
- indexPos: pair[0],
- objectPos,
- };
-}
-
-/**
- * Continue past targetIndexKey (and optionally targetObjectKey)
- * in the direction specified by "forward".
- * Do nothing if the current position is already past the
- * target position.
- */
-function continueIndex(req: {
- indexData: ISortedMapF<IDBValidKey, IndexRecord>;
- currentPos?: IndexIterPos;
- unique: boolean;
- inclusive: boolean;
- forward: boolean;
- targetIndexKey: Key;
- targetObjectKey?: Key;
-}): IndexIterPos | undefined {
- const currentPos = req.currentPos;
- const forward = req.forward;
- const inclusive = req.inclusive;
- const dir = forward ? 1 : -1;
- if (currentPos) {
- // Check that the target position after the current position.
- // If not, we just stay at the current position.
- const indexCmp = compareKeys(currentPos.indexPos, req.targetIndexKey);
- if (dir * indexCmp > 0) {
- return currentPos;
- }
- if (indexCmp === 0) {
- if (req.targetObjectKey != null) {
- const objectCmp = compareKeys(
- currentPos.objectPos,
- req.targetObjectKey,
- );
- if (req.inclusive && objectCmp === 0) {
- return currentPos;
- }
- if (dir * objectCmp > 0) {
- return currentPos;
- }
- } else if (req.inclusive) {
- return currentPos;
- }
- }
- }
- const indexData = req.indexData;
- if (forward) {
- if (req.unique || req.targetObjectKey == null) {
- if (inclusive) {
- return continueIndexForwardInclusiveUnique(
- indexData,
- req.targetIndexKey,
- );
- } else {
- return continueIndexForwardStrictUnique(indexData, req.targetIndexKey);
- }
- } else {
- if (inclusive) {
- return continueIndexForwardInclusive(
- indexData,
- req.targetIndexKey,
- req.targetObjectKey,
- );
- } else {
- return continueIndexForwardStrict(
- indexData,
- req.targetIndexKey,
- req.targetObjectKey,
- );
- }
- }
- } else {
- if (req.unique || req.targetObjectKey == null) {
- if (inclusive) {
- return continueIndexBackwardInclusiveUnique(
- indexData,
- req.targetIndexKey,
- );
- } else {
- return continueIndexBackwardStrictUnique(indexData, req.targetIndexKey);
- }
- } else {
- if (inclusive) {
- return continueIndexBackwardInclusive(
- indexData,
- req.targetIndexKey,
- req.targetObjectKey,
- );
- } else {
- return continueIndexBackwardStrict(
- indexData,
- req.targetIndexKey,
- req.targetObjectKey,
- );
- }
- }
- }
-}
-
-function getIndexRecords(req: {
- indexData: ISortedMapF<IDBValidKey, IndexRecord>;
- storeData: ISortedMapF<IDBValidKey, ObjectStoreRecord>;
- lastIndexPosition?: IDBValidKey;
- forward: boolean;
- unique: boolean;
- range: IDBKeyRange;
- lastObjectStorePosition?: IDBValidKey;
- advancePrimaryKey?: IDBValidKey;
- advanceIndexKey?: IDBValidKey;
- limit: number;
- resultLevel: ResultLevel;
-}): RecordGetResponse {
- let numResults = 0;
- const indexKeys: Key[] = [];
- const primaryKeys: Key[] = [];
- const values: Value[] = [];
- const { unique, forward, indexData } = req;
-
- function packResult(): RecordGetResponse {
- // Collect the values based on the primary keys,
- // if requested.
- if (req.resultLevel === ResultLevel.Full) {
- for (let i = 0; i < numResults; i++) {
- const result = req.storeData.get(primaryKeys[i]);
- if (!result) {
- console.error("invariant violated during read");
- console.error("request was", req);
- throw Error("invariant violated during read");
- }
- values.push(structuredClone(result.value));
- }
- }
- return {
- count: numResults,
- indexKeys:
- req.resultLevel >= ResultLevel.OnlyKeys ? indexKeys : undefined,
- primaryKeys:
- req.resultLevel >= ResultLevel.OnlyKeys ? primaryKeys : undefined,
- values: req.resultLevel >= ResultLevel.Full ? values : undefined,
- };
- }
-
- const endRange = getRangeEndBoundary(forward, req.range);
-
- let currentPos = startIndex({
- forward,
- indexData,
- unique,
- });
-
- if (currentPos == null) {
- return packResult();
- }
-
- if (req.advanceIndexKey != null) {
- currentPos = continueIndex({
- indexData,
- unique,
- inclusive: true,
- currentPos,
- forward,
- targetIndexKey: req.advanceIndexKey,
- targetObjectKey: req.advancePrimaryKey,
- });
-
- if (currentPos == null) {
- return packResult();
- }
- }
-
- if (req.lastIndexPosition != null) {
- currentPos = continueIndex({
- indexData,
- unique,
- inclusive: false,
- currentPos,
- forward,
- targetIndexKey: req.lastIndexPosition,
- targetObjectKey: req.lastObjectStorePosition,
- });
- if (!currentPos) {
- return packResult();
- }
- }
-
- if (req.range != null) {
- const targetKeyObj = forward ? req.range.lower : req.range.upper;
- if (targetKeyObj != null) {
- const targetKey = targetKeyObj;
- const inclusive = forward ? !req.range.lowerOpen : !req.range.upperOpen;
- currentPos = continueIndex({
- indexData,
- unique,
- inclusive,
- currentPos,
- forward,
- targetIndexKey: targetKey,
- });
- }
- if (!currentPos) {
- return packResult();
- }
- }
-
- while (1) {
- if (req.limit != 0 && numResults == req.limit) {
- break;
- }
- if (currentPos == null) {
- break;
- }
- if (endRange && isOutsideBoundary(forward, endRange, currentPos.indexPos)) {
- break;
- }
-
- indexKeys.push(structuredClone(currentPos.indexPos));
- primaryKeys.push(structuredClone(currentPos.objectPos));
-
- numResults++;
-
- currentPos = continueIndex({
- indexData,
- unique,
- forward,
- inclusive: false,
- currentPos: undefined,
- targetIndexKey: currentPos.indexPos,
- targetObjectKey: currentPos.objectPos,
- });
- }
-
- return packResult();
-}
-
-function getObjectStoreRecords(req: {
- storeData: ISortedMapF<IDBValidKey, ObjectStoreRecord>;
- forward: boolean;
- range: IDBKeyRange;
- lastObjectStorePosition?: IDBValidKey;
- advancePrimaryKey?: IDBValidKey;
- limit: number;
- resultLevel: ResultLevel;
-}): RecordGetResponse {
- let numResults = 0;
- const primaryKeys: Key[] = [];
- const values: Value[] = [];
- const { storeData, range, forward } = req;
-
- function packResult(): RecordGetResponse {
- return {
- count: numResults,
- indexKeys: undefined,
- primaryKeys:
- req.resultLevel >= ResultLevel.OnlyKeys ? primaryKeys : undefined,
- values: req.resultLevel >= ResultLevel.Full ? values : undefined,
- };
- }
-
- const rangeStart = forward ? range.lower : range.upper;
- const dataStart = forward ? storeData.minKey() : storeData.maxKey();
- let storePos = req.lastObjectStorePosition;
- storePos = furthestKey(forward, storePos, dataStart);
- storePos = furthestKey(forward, storePos, rangeStart);
- storePos = furthestKey(forward, storePos, req.advancePrimaryKey);
-
- if (storePos != null) {
- // Advance store position if we are either still at the last returned
- // store key, or if we are currently not on a key.
- const storeEntry = storeData.get(storePos);
- if (
- !storeEntry ||
- (req.lastObjectStorePosition != null &&
- compareKeys(req.lastObjectStorePosition, storePos) === 0)
- ) {
- storePos = forward
- ? storeData.nextHigherKey(storePos)
- : storeData.nextLowerKey(storePos);
- }
- } else {
- storePos = forward ? storeData.minKey() : storeData.maxKey();
- }
-
- if (
- storePos != null &&
- forward &&
- range.lowerOpen &&
- range.lower != null &&
- compareKeys(range.lower, storePos) === 0
- ) {
- storePos = storeData.nextHigherKey(storePos);
- }
-
- if (
- storePos != null &&
- !forward &&
- range.upperOpen &&
- range.upper != null &&
- compareKeys(range.upper, storePos) === 0
- ) {
- storePos = storeData.nextLowerKey(storePos);
- }
-
- while (1) {
- if (req.limit != 0 && numResults == req.limit) {
- break;
- }
- if (storePos === null || storePos === undefined) {
- break;
- }
- if (!range.includes(storePos)) {
- break;
- }
-
- const res = storeData.get(storePos);
-
- if (res === undefined) {
- break;
- }
-
- if (req.resultLevel >= ResultLevel.OnlyKeys) {
- primaryKeys.push(structuredClone(storePos));
- }
-
- if (req.resultLevel >= ResultLevel.Full) {
- values.push(structuredClone(res.value));
- }
-
- numResults++;
- storePos = nextStoreKey(forward, storeData, storePos);
- }
-
- return packResult();
-}
diff --git a/packages/idb-bridge/src/backends.test.ts b/packages/idb-bridge/src/backends.test.ts
@@ -22,15 +22,14 @@
/**
* Imports.
*/
-import { test, before } from "node:test";
import assert from "node:assert";
-import { MemoryBackend } from "./MemoryBackend.js";
+import { before, test } from "node:test";
import {
BridgeIDBCursorWithValue,
BridgeIDBDatabase,
- BridgeIDBFactory,
BridgeIDBKeyRange,
} from "./bridge-idb.js";
+import { promiseForTransaction } from "./idb-wpt-ported/wptsupport.js";
import { promiseFromRequest, promiseFromTransaction } from "./idbpromutil.js";
import {
IDBCursorDirection,
@@ -40,7 +39,6 @@ import {
IDBValidKey,
} from "./idbtypes.js";
import { initTestIndexedDB, useTestIndexedDb } from "./testingdb.js";
-import { promiseForTransaction } from "./idb-wpt-ported/wptsupport.js";
before(initTestIndexedDB);
@@ -422,50 +420,6 @@ test("simple deletion", async (t) => {
await promiseFromTransaction(tx2);
});
-test("export", async (t) => {
- const backend = new MemoryBackend();
- const idb = new BridgeIDBFactory(backend);
- const dbname = "library-" + new Date().getTime() + Math.random();
- const request = idb.open(dbname, 42);
- request.onupgradeneeded = () => {
- const db = request.result;
- const store = db.createObjectStore("books", { keyPath: "isbn" });
- const titleIndex = store.createIndex("by_title", "title", { unique: true });
- const authorIndex = store.createIndex("by_author", "author");
- };
-
- const db: BridgeIDBDatabase = await promiseFromRequest(request);
-
- const tx = db.transaction("books", "readwrite");
- tx.oncomplete = () => {
- console.log("oncomplete called");
- };
-
- const store = tx.objectStore("books");
-
- store.put({ title: "Quarry Memories", author: "Fred", isbn: 123456 });
- store.put({ title: "Water Buffaloes", author: "Fred", isbn: 234567 });
- store.put({ title: "Bedrock Nights", author: "Barney", isbn: 345678 });
-
- await promiseFromTransaction(tx);
-
- const exportedData = backend.exportDump();
- const backend2 = new MemoryBackend();
- backend2.importDump(exportedData);
- const exportedData2 = backend2.exportDump();
-
- assert.ok(
- exportedData.databases[dbname].objectStores["books"].records.length === 3,
- );
- assert.deepStrictEqual(exportedData, exportedData2);
-
- assert.strictEqual(exportedData.databases[dbname].schema.databaseVersion, 42);
- assert.strictEqual(
- exportedData2.databases[dbname].schema.databaseVersion,
- 42,
- );
-});
-
test("update with non-existent index values", async (t) => {
const idb = useTestIndexedDb();
const dbname = "mydb-" + new Date().getTime() + Math.random();
diff --git a/packages/idb-bridge/src/index.ts b/packages/idb-bridge/src/index.ts
@@ -25,7 +25,6 @@ import {
import { Event } from "./idbtypes.js";
import {
DatabaseDump,
- IndexRecord,
MemoryBackendDump,
ObjectStoreDump,
ObjectStoreRecord,
@@ -36,7 +35,6 @@ export * from "./sqlite3-interface.js";
export * from "./SqliteBackend.js";
export * from "./idbtypes.js";
-export { MemoryBackend } from "./MemoryBackend.js";
export type { AccessStats } from "./MemoryBackend.js";
export * from "./util/structuredClone.js";
export {
@@ -59,7 +57,6 @@ export type {
DatabaseList,
DatabaseTransaction,
Event,
- IndexRecord,
Listener,
MemoryBackendDump,
ObjectStoreDump,
diff --git a/packages/idb-bridge/src/testingdb.ts b/packages/idb-bridge/src/testingdb.ts
@@ -13,7 +13,6 @@
GNU Taler; see the file COPYING. If not, see <http://www.gnu.org/licenses/>
*/
-import { MemoryBackend } from "./MemoryBackend.js";
import { createSqliteBackend } from "./SqliteBackend.js";
import { Backend } from "./backend-interface.js";
import { BridgeIDBFactory } from "./bridge-idb.js";
@@ -25,9 +24,7 @@ let idbFactory: IDBFactory | undefined = undefined;
export async function initTestIndexedDB(): Promise<void> {
let backend: Backend;
if (process.env.IDB_TEST_BACKEND == "memory") {
- const memBackend = new MemoryBackend();
- backend = memBackend;
- memBackend.enableTracing = true;
+ throw Error("backend not supported");
} else {
const sqlite3Impl = await createNodeHelperSqlite3Impl({
enableTracing: false,
diff --git a/packages/idb-bridge/src/tree/b+tree.ts b/packages/idb-bridge/src/tree/b+tree.ts
@@ -1,2271 +0,0 @@
-// B+ tree by David Piepgrass. License: MIT
-import { ISortedMap, ISortedMapF } from "./interfaces.js";
-
-export type {
- IMap,
- IMapF,
- IMapSink,
- IMapSource,
- ISet,
- ISetF,
- ISetSink,
- ISetSource,
- ISortedMap,
- ISortedMapF,
- ISortedMapSource,
- ISortedSet,
- ISortedSetF,
- ISortedSetSource,
-} from "./interfaces.js";
-
-export type EditRangeResult<V, R = number> = {
- value?: V;
- break?: R;
- delete?: boolean;
-};
-
-type index = number;
-
-// Informative microbenchmarks & stuff:
-// http://www.jayconrod.com/posts/52/a-tour-of-v8-object-representation (very educational)
-// https://blog.mozilla.org/luke/2012/10/02/optimizing-javascript-variable-access/ (local vars are faster than properties)
-// http://benediktmeurer.de/2017/12/13/an-introduction-to-speculative-optimization-in-v8/ (other stuff)
-// https://jsperf.com/js-in-operator-vs-alternatives (avoid 'in' operator; `.p!==undefined` faster than `hasOwnProperty('p')` in all browsers)
-// https://jsperf.com/instanceof-vs-typeof-vs-constructor-vs-member (speed of type tests varies wildly across browsers)
-// https://jsperf.com/detecting-arrays-new (a.constructor===Array is best across browsers, assuming a is an object)
-// https://jsperf.com/shallow-cloning-methods (a constructor is faster than Object.create; hand-written clone faster than Object.assign)
-// https://jsperf.com/ways-to-fill-an-array (slice-and-replace is fastest)
-// https://jsperf.com/math-min-max-vs-ternary-vs-if (Math.min/max is slow on Edge)
-// https://jsperf.com/array-vs-property-access-speed (v.x/v.y is faster than a[0]/a[1] in major browsers IF hidden class is constant)
-// https://jsperf.com/detect-not-null-or-undefined (`x==null` slightly slower than `x===null||x===undefined` on all browsers)
-// Overall, microbenchmarks suggest Firefox is the fastest browser for JavaScript and Edge is the slowest.
-// Lessons from https://v8project.blogspot.com/2017/09/elements-kinds-in-v8.html:
-// - Avoid holes in arrays. Avoid `new Array(N)`, it will be "holey" permanently.
-// - Don't read outside bounds of an array (it scans prototype chain).
-// - Small integer arrays are stored differently from doubles
-// - Adding non-numbers to an array deoptimizes it permanently into a general array
-// - Objects can be used like arrays (e.g. have length property) but are slower
-// - V8 source (NewElementsCapacity in src/objects.h): arrays grow by 50% + 16 elements
-
-/**
- * Types that BTree supports by default
- */
-export type DefaultComparable =
- | number
- | string
- | Date
- | boolean
- | null
- | undefined
- | (number | string)[]
- | {
- valueOf: () =>
- | number
- | string
- | Date
- | boolean
- | null
- | undefined
- | (number | string)[];
- };
-
-/**
- * Compares DefaultComparables to form a strict partial ordering.
- *
- * Handles +/-0 and NaN like Map: NaN is equal to NaN, and -0 is equal to +0.
- *
- * Arrays are compared using '<' and '>', which may cause unexpected equality:
- * for example [1] will be considered equal to ['1'].
- *
- * Two objects with equal valueOf compare the same, but compare unequal to
- * primitives that have the same value.
- */
-export function defaultComparator(
- a: DefaultComparable,
- b: DefaultComparable,
-): number {
- // Special case finite numbers first for performance.
- // Note that the trick of using 'a - b' and checking for NaN to detect non-numbers
- // does not work if the strings are numeric (ex: "5"). This would leading most
- // comparison functions using that approach to fail to have transitivity.
- if (Number.isFinite(a as any) && Number.isFinite(b as any)) {
- return (a as number) - (b as number);
- }
-
- // The default < and > operators are not totally ordered. To allow types to be mixed
- // in a single collection, compare types and order values of different types by type.
- let ta = typeof a;
- let tb = typeof b;
- if (ta !== tb) {
- return ta < tb ? -1 : 1;
- }
-
- if (ta === "object") {
- // standardized JavaScript bug: null is not an object, but typeof says it is
- if (a === null) return b === null ? 0 : -1;
- else if (b === null) return 1;
-
- a = a!.valueOf() as DefaultComparable;
- b = b!.valueOf() as DefaultComparable;
- ta = typeof a;
- tb = typeof b;
- // Deal with the two valueOf()s producing different types
- if (ta !== tb) {
- return ta < tb ? -1 : 1;
- }
- }
-
- // a and b are now the same type, and will be a number, string or array
- // (which we assume holds numbers or strings), or something unsupported.
- if (a! < b!) return -1;
- if (a! > b!) return 1;
- if (a === b) return 0;
-
- // Order NaN less than other numbers
- if (Number.isNaN(a as any)) return Number.isNaN(b as any) ? 0 : -1;
- else if (Number.isNaN(b as any)) return 1;
- // This could be two objects (e.g. [7] and ['7']) that aren't ordered
- return Array.isArray(a) ? 0 : Number.NaN;
-}
-
-/**
- * Compares items using the < and > operators. This function is probably slightly
- * faster than the defaultComparator for Dates and strings, but has not been benchmarked.
- * Unlike defaultComparator, this comparator doesn't support mixed types correctly,
- * i.e. use it with `BTree<string>` or `BTree<number>` but not `BTree<string|number>`.
- *
- * NaN is not supported.
- *
- * Note: null is treated like 0 when compared with numbers or Date, but in general
- * null is not ordered with respect to strings (neither greater nor less), and
- * undefined is not ordered with other types.
- */
-export function simpleComparator(a: string, b: string): number;
-export function simpleComparator(a: number | null, b: number | null): number;
-export function simpleComparator(a: Date | null, b: Date | null): number;
-export function simpleComparator(
- a: (number | string)[],
- b: (number | string)[],
-): number;
-export function simpleComparator(a: any, b: any): number {
- return a > b ? 1 : a < b ? -1 : 0;
-}
-
-/**
- * A reasonably fast collection of key-value pairs with a powerful API.
- * Largely compatible with the standard Map. BTree is a B+ tree data structure,
- * so the collection is sorted by key.
- *
- * B+ trees tend to use memory more efficiently than hashtables such as the
- * standard Map, especially when the collection contains a large number of
- * items. However, maintaining the sort order makes them modestly slower:
- * O(log size) rather than O(1). This B+ tree implementation supports O(1)
- * fast cloning. It also supports freeze(), which can be used to ensure that
- * a BTree is not changed accidentally.
- *
- * Confusingly, the ES6 Map.forEach(c) method calls c(value,key) instead of
- * c(key,value), in contrast to other methods such as set() and entries()
- * which put the key first. I can only assume that the order was reversed on
- * the theory that users would usually want to examine values and ignore keys.
- * BTree's forEach() therefore works the same way, but a second method
- * `.forEachPair((key,value)=>{...})` is provided which sends you the key
- * first and the value second; this method is slightly faster because it is
- * the "native" for-each method for this class.
- *
- * Out of the box, BTree supports keys that are numbers, strings, arrays of
- * numbers/strings, Date, and objects that have a valueOf() method returning a
- * number or string. Other data types, such as arrays of Date or custom
- * objects, require a custom comparator, which you must pass as the second
- * argument to the constructor (the first argument is an optional list of
- * initial items). Symbols cannot be used as keys because they are unordered
- * (one Symbol is never "greater" or "less" than another).
- *
- * @example
- * Given a {name: string, age: number} object, you can create a tree sorted by
- * name and then by age like this:
- *
- * var tree = new BTree(undefined, (a, b) => {
- * if (a.name > b.name)
- * return 1; // Return a number >0 when a > b
- * else if (a.name < b.name)
- * return -1; // Return a number <0 when a < b
- * else // names are equal (or incomparable)
- * return a.age - b.age; // Return >0 when a.age > b.age
- * });
- *
- * tree.set({name:"Bill", age:17}, "happy");
- * tree.set({name:"Fran", age:40}, "busy & stressed");
- * tree.set({name:"Bill", age:55}, "recently laid off");
- * tree.forEachPair((k, v) => {
- * console.log(`Name: ${k.name} Age: ${k.age} Status: ${v}`);
- * });
- *
- * @description
- * The "range" methods (`forEach, forRange, editRange`) will return the number
- * of elements that were scanned. In addition, the callback can return {break:R}
- * to stop early and return R from the outer function.
- *
- * - TODO: Test performance of preallocating values array at max size
- * - TODO: Add fast initialization when a sorted array is provided to constructor
- *
- * For more documentation see https://github.com/qwertie/btree-typescript
- *
- * Are you a C# developer? You might like the similar data structures I made for C#:
- * BDictionary, BList, etc. See http://core.loyc.net/collections/
- *
- * @author David Piepgrass
- */
-export default class BTree<K = any, V = any>
- implements ISortedMapF<K, V>, ISortedMap<K, V>
-{
- private _root: BNode<K, V> = EmptyLeaf as BNode<K, V>;
- _size: number = 0;
- _maxNodeSize: number;
-
- /**
- * provides a total order over keys (and a strict partial order over the type K)
- * @returns a negative value if a < b, 0 if a === b and a positive value if a > b
- */
- _compare: (a: K, b: K) => number;
-
- /**
- * Initializes an empty B+ tree.
- * @param compare Custom function to compare pairs of elements in the tree.
- * If not specified, defaultComparator will be used which is valid as long as K extends DefaultComparable.
- * @param entries A set of key-value pairs to initialize the tree
- * @param maxNodeSize Branching factor (maximum items or children per node)
- * Must be in range 4..256. If undefined or <4 then default is used; if >256 then 256.
- */
- public constructor(
- entries?: [K, V][],
- compare?: (a: K, b: K) => number,
- maxNodeSize?: number,
- ) {
- this._maxNodeSize = maxNodeSize! >= 4 ? Math.min(maxNodeSize!, 256) : 32;
- this._compare =
- compare || (defaultComparator as any as (a: K, b: K) => number);
- if (entries) this.setPairs(entries);
- }
-
- /////////////////////////////////////////////////////////////////////////////
- // ES6 Map<K,V> methods /////////////////////////////////////////////////////
-
- /** Gets the number of key-value pairs in the tree. */
- get size() {
- return this._size;
- }
- /** Gets the number of key-value pairs in the tree. */
- get length() {
- return this._size;
- }
- /** Returns true iff the tree contains no key-value pairs. */
- get isEmpty() {
- return this._size === 0;
- }
-
- /** Releases the tree so that its size is 0. */
- clear() {
- this._root = EmptyLeaf as BNode<K, V>;
- this._size = 0;
- }
-
- forEach(
- callback: (v: V, k: K, tree: BTree<K, V>) => void,
- thisArg?: any,
- ): number;
-
- /** Runs a function for each key-value pair, in order from smallest to
- * largest key. For compatibility with ES6 Map, the argument order to
- * the callback is backwards: value first, then key. Call forEachPair
- * instead to receive the key as the first argument.
- * @param thisArg If provided, this parameter is assigned as the `this`
- * value for each callback.
- * @returns the number of values that were sent to the callback,
- * or the R value if the callback returned {break:R}. */
- forEach<R = number>(
- callback: (v: V, k: K, tree: BTree<K, V>) => { break?: R } | void,
- thisArg?: any,
- ): R | number {
- if (thisArg !== undefined) callback = callback.bind(thisArg);
- return this.forEachPair((k, v) => callback(v, k, this));
- }
-
- /** Runs a function for each key-value pair, in order from smallest to
- * largest key. The callback can return {break:R} (where R is any value
- * except undefined) to stop immediately and return R from forEachPair.
- * @param onFound A function that is called for each key-value pair. This
- * function can return {break:R} to stop early with result R.
- * The reason that you must return {break:R} instead of simply R
- * itself is for consistency with editRange(), which allows
- * multiple actions, not just breaking.
- * @param initialCounter This is the value of the third argument of
- * `onFound` the first time it is called. The counter increases
- * by one each time `onFound` is called. Default value: 0
- * @returns the number of pairs sent to the callback (plus initialCounter,
- * if you provided one). If the callback returned {break:R} then
- * the R value is returned instead. */
- forEachPair<R = number>(
- callback: (k: K, v: V, counter: number) => { break?: R } | void,
- initialCounter?: number,
- ): R | number {
- var low = this.minKey(),
- high = this.maxKey();
- return this.forRange(low!, high!, true, callback, initialCounter);
- }
-
- /**
- * Finds a pair in the tree and returns the associated value.
- * @param defaultValue a value to return if the key was not found.
- * @returns the value, or defaultValue if the key was not found.
- * @description Computational complexity: O(log size)
- */
- get(key: K, defaultValue?: V): V | undefined {
- return this._root.get(key, defaultValue, this);
- }
-
- /**
- * Adds or overwrites a key-value pair in the B+ tree.
- * @param key the key is used to determine the sort order of
- * data in the tree.
- * @param value data to associate with the key (optional)
- * @param overwrite Whether to overwrite an existing key-value pair
- * (default: true). If this is false and there is an existing
- * key-value pair then this method has no effect.
- * @returns true if a new key-value pair was added.
- * @description Computational complexity: O(log size)
- * Note: when overwriting a previous entry, the key is updated
- * as well as the value. This has no effect unless the new key
- * has data that does not affect its sort order.
- */
- set(key: K, value: V, overwrite?: boolean): boolean {
- if (this._root.isShared) this._root = this._root.clone();
- var result = this._root.set(key, value, overwrite, this);
- if (result === true || result === false) return result;
- // Root node has split, so create a new root node.
- this._root = new BNodeInternal<K, V>([this._root, result]);
- return true;
- }
-
- /**
- * Returns true if the key exists in the B+ tree, false if not.
- * Use get() for best performance; use has() if you need to
- * distinguish between "undefined value" and "key not present".
- * @param key Key to detect
- * @description Computational complexity: O(log size)
- */
- has(key: K): boolean {
- return this.forRange(key, key, true, undefined) !== 0;
- }
-
- /**
- * Removes a single key-value pair from the B+ tree.
- * @param key Key to find
- * @returns true if a pair was found and removed, false otherwise.
- * @description Computational complexity: O(log size)
- */
- delete(key: K): boolean {
- return this.editRange(key, key, true, DeleteRange) !== 0;
- }
-
- /////////////////////////////////////////////////////////////////////////////
- // Clone-mutators ///////////////////////////////////////////////////////////
-
- /** Returns a copy of the tree with the specified key set (the value is undefined). */
- with(key: K): BTree<K, V | undefined>;
- /** Returns a copy of the tree with the specified key-value pair set. */
- with<V2>(key: K, value: V2, overwrite?: boolean): BTree<K, V | V2>;
- with<V2>(
- key: K,
- value?: V2,
- overwrite?: boolean,
- ): BTree<K, V | V2 | undefined> {
- let nu = this.clone() as BTree<K, V | V2 | undefined>;
- return nu.set(key, value, overwrite) || overwrite ? nu : this;
- }
-
- /** Returns a copy of the tree with the specified key-value pairs set. */
- withPairs<V2>(pairs: [K, V | V2][], overwrite: boolean): BTree<K, V | V2> {
- let nu = this.clone() as BTree<K, V | V2>;
- return nu.setPairs(pairs, overwrite) !== 0 || overwrite ? nu : this;
- }
-
- /** Returns a copy of the tree with the specified keys present.
- * @param keys The keys to add. If a key is already present in the tree,
- * neither the existing key nor the existing value is modified.
- * @param returnThisIfUnchanged if true, returns this if all keys already
- * existed. Performance note: due to the architecture of this class, all
- * node(s) leading to existing keys are cloned even if the collection is
- * ultimately unchanged.
- */
- withKeys(
- keys: K[],
- returnThisIfUnchanged?: boolean,
- ): BTree<K, V | undefined> {
- let nu = this.clone() as BTree<K, V | undefined>,
- changed = false;
- for (var i = 0; i < keys.length; i++)
- changed = nu.set(keys[i], undefined, false) || changed;
- return returnThisIfUnchanged && !changed ? this : nu;
- }
-
- /** Returns a copy of the tree with the specified key removed.
- * @param returnThisIfUnchanged if true, returns this if the key didn't exist.
- * Performance note: due to the architecture of this class, node(s) leading
- * to where the key would have been stored are cloned even when the key
- * turns out not to exist and the collection is unchanged.
- */
- without(key: K, returnThisIfUnchanged?: boolean): BTree<K, V> {
- return this.withoutRange(key, key, true, returnThisIfUnchanged);
- }
-
- /** Returns a copy of the tree with the specified keys removed.
- * @param returnThisIfUnchanged if true, returns this if none of the keys
- * existed. Performance note: due to the architecture of this class,
- * node(s) leading to where the key would have been stored are cloned
- * even when the key turns out not to exist.
- */
- withoutKeys(keys: K[], returnThisIfUnchanged?: boolean): BTree<K, V> {
- let nu = this.clone();
- return nu.deleteKeys(keys) || !returnThisIfUnchanged ? nu : this;
- }
-
- /** Returns a copy of the tree with the specified range of keys removed. */
- withoutRange(
- low: K,
- high: K,
- includeHigh: boolean,
- returnThisIfUnchanged?: boolean,
- ): BTree<K, V> {
- let nu = this.clone();
- if (nu.deleteRange(low, high, includeHigh) === 0 && returnThisIfUnchanged)
- return this;
- return nu;
- }
-
- /** Returns a copy of the tree with pairs removed whenever the callback
- * function returns false. `where()` is a synonym for this method. */
- filter(
- callback: (k: K, v: V, counter: number) => boolean,
- returnThisIfUnchanged?: boolean,
- ): BTree<K, V> {
- var nu = this.greedyClone();
- var del: any;
- nu.editAll((k, v, i) => {
- if (!callback(k, v, i)) {
- return (del = Delete);
- }
- return undefined;
- });
- if (!del && returnThisIfUnchanged) return this;
- return nu;
- }
-
- /** Returns a copy of the tree with all values altered by a callback function. */
- mapValues<R>(callback: (v: V, k: K, counter: number) => R): BTree<K, R> {
- var tmp = {} as { value: R };
- var nu = this.greedyClone();
- nu.editAll((k, v, i) => {
- return ((tmp.value = callback(v, k, i)), tmp as any);
- });
- return nu as any as BTree<K, R>;
- }
-
- /** Performs a reduce operation like the `reduce` method of `Array`.
- * It is used to combine all pairs into a single value, or perform
- * conversions. `reduce` is best understood by example. For example,
- * `tree.reduce((P, pair) => P * pair[0], 1)` multiplies all keys
- * together. It means "start with P=1, and for each pair multiply
- * it by the key in pair[0]". Another example would be converting
- * the tree to a Map (in this example, note that M.set returns M):
- *
- * var M = tree.reduce((M, pair) => M.set(pair[0],pair[1]), new Map())
- *
- * **Note**: the same array is sent to the callback on every iteration.
- */
- reduce<R>(
- callback: (
- previous: R,
- currentPair: [K, V],
- counter: number,
- tree: BTree<K, V>,
- ) => R,
- initialValue: R,
- ): R;
- reduce<R>(
- callback: (
- previous: R | undefined,
- currentPair: [K, V],
- counter: number,
- tree: BTree<K, V>,
- ) => R,
- ): R | undefined;
- reduce<R>(
- callback: (
- previous: R | undefined,
- currentPair: [K, V],
- counter: number,
- tree: BTree<K, V>,
- ) => R,
- initialValue?: R,
- ): R | undefined {
- let i = 0,
- p = initialValue;
- var it = this.entries(this.minKey(), ReusedArray),
- next;
- while (!(next = it.next()).done) p = callback(p, next.value, i++, this);
- return p;
- }
-
- /////////////////////////////////////////////////////////////////////////////
- // Iterator methods /////////////////////////////////////////////////////////
-
- /** Returns an iterator that provides items in order (ascending order if
- * the collection's comparator uses ascending order, as is the default.)
- * @param lowestKey First key to be iterated, or undefined to start at
- * minKey(). If the specified key doesn't exist then iteration
- * starts at the next higher key (according to the comparator).
- * @param reusedArray Optional array used repeatedly to store key-value
- * pairs, to avoid creating a new array on every iteration.
- */
- entries(lowestKey?: K, reusedArray?: (K | V)[]): IterableIterator<[K, V]> {
- var info = this.findPath(lowestKey);
- if (info === undefined) return iterator<[K, V]>();
- var { nodequeue, nodeindex, leaf } = info;
- var state = reusedArray !== undefined ? 1 : 0;
- var i =
- lowestKey === undefined
- ? -1
- : leaf.indexOf(lowestKey, 0, this._compare) - 1;
-
- return iterator<[K, V]>(() => {
- jump: for (;;) {
- switch (state) {
- case 0:
- if (++i < leaf.keys.length)
- return { done: false, value: [leaf.keys[i], leaf.values[i]] };
- state = 2;
- continue;
- case 1:
- if (++i < leaf.keys.length) {
- ((reusedArray![0] = leaf.keys[i]),
- (reusedArray![1] = leaf.values[i]));
- return { done: false, value: reusedArray as [K, V] };
- }
- state = 2;
- continue;
- case 2:
- // Advance to the next leaf node
- for (var level = -1; ; ) {
- if (++level >= nodequeue.length) {
- state = 3;
- continue jump;
- }
- if (++nodeindex[level] < nodequeue[level].length) break;
- }
- for (; level > 0; level--) {
- nodequeue[level - 1] = (
- nodequeue[level][nodeindex[level]] as BNodeInternal<K, V>
- ).children;
- nodeindex[level - 1] = 0;
- }
- leaf = nodequeue[0][nodeindex[0]];
- i = -1;
- state = reusedArray !== undefined ? 1 : 0;
- continue;
- case 3:
- return { done: true, value: undefined };
- }
- }
- });
- }
-
- /** Returns an iterator that provides items in reversed order.
- * @param highestKey Key at which to start iterating, or undefined to
- * start at maxKey(). If the specified key doesn't exist then iteration
- * starts at the next lower key (according to the comparator).
- * @param reusedArray Optional array used repeatedly to store key-value
- * pairs, to avoid creating a new array on every iteration.
- * @param skipHighest Iff this flag is true and the highestKey exists in the
- * collection, the pair matching highestKey is skipped, not iterated.
- */
- entriesReversed(
- highestKey?: K,
- reusedArray?: (K | V)[],
- skipHighest?: boolean,
- ): IterableIterator<[K, V]> {
- if (highestKey === undefined) {
- highestKey = this.maxKey();
- skipHighest = undefined;
- if (highestKey === undefined) return iterator<[K, V]>(); // collection is empty
- }
- var { nodequeue, nodeindex, leaf } =
- this.findPath(highestKey) || this.findPath(this.maxKey())!;
- check(!nodequeue[0] || leaf === nodequeue[0][nodeindex[0]], "wat!");
- var i = leaf.indexOf(highestKey, 0, this._compare);
- if (
- !skipHighest &&
- i < leaf.keys.length &&
- this._compare(leaf.keys[i], highestKey) <= 0
- )
- i++;
- var state = reusedArray !== undefined ? 1 : 0;
-
- return iterator<[K, V]>(() => {
- jump: for (;;) {
- switch (state) {
- case 0:
- if (--i >= 0)
- return { done: false, value: [leaf.keys[i], leaf.values[i]] };
- state = 2;
- continue;
- case 1:
- if (--i >= 0) {
- ((reusedArray![0] = leaf.keys[i]),
- (reusedArray![1] = leaf.values[i]));
- return { done: false, value: reusedArray as [K, V] };
- }
- state = 2;
- continue jump;
- case 2:
- // Advance to the next leaf node
- for (var level = -1; ; ) {
- if (++level >= nodequeue.length) {
- state = 3;
- continue jump;
- }
- if (--nodeindex[level] >= 0) break;
- }
- for (; level > 0; level--) {
- nodequeue[level - 1] = (
- nodequeue[level][nodeindex[level]] as BNodeInternal<K, V>
- ).children;
- nodeindex[level - 1] = nodequeue[level - 1].length - 1;
- }
- leaf = nodequeue[0][nodeindex[0]];
- i = leaf.keys.length;
- state = reusedArray !== undefined ? 1 : 0;
- continue;
- case 3:
- return { done: true, value: undefined };
- }
- }
- });
- }
-
- /* Used by entries() and entriesReversed() to prepare to start iterating.
- * It develops a "node queue" for each non-leaf level of the tree.
- * Levels are numbered "bottom-up" so that level 0 is a list of leaf
- * nodes from a low-level non-leaf node. The queue at a given level L
- * consists of nodequeue[L] which is the children of a BNodeInternal,
- * and nodeindex[L], the current index within that child list, such
- * such that nodequeue[L-1] === nodequeue[L][nodeindex[L]].children.
- * (However inside this function the order is reversed.)
- */
- private findPath(
- key?: K,
- ):
- | { nodequeue: BNode<K, V>[][]; nodeindex: number[]; leaf: BNode<K, V> }
- | undefined {
- var nextnode = this._root;
- var nodequeue: BNode<K, V>[][], nodeindex: number[];
-
- if (nextnode.isLeaf) {
- ((nodequeue = EmptyArray), (nodeindex = EmptyArray)); // avoid allocations
- } else {
- ((nodequeue = []), (nodeindex = []));
- for (var d = 0; !nextnode.isLeaf; d++) {
- nodequeue[d] = (nextnode as BNodeInternal<K, V>).children;
- nodeindex[d] =
- key === undefined ? 0 : nextnode.indexOf(key, 0, this._compare);
- if (nodeindex[d] >= nodequeue[d].length) return; // first key > maxKey()
- nextnode = nodequeue[d][nodeindex[d]];
- }
- nodequeue.reverse();
- nodeindex.reverse();
- }
- return { nodequeue, nodeindex, leaf: nextnode };
- }
-
- /**
- * Computes the differences between `this` and `other`.
- * For efficiency, the diff is returned via invocations of supplied handlers.
- * The computation is optimized for the case in which the two trees have large amounts
- * of shared data (obtained by calling the `clone` or `with` APIs) and will avoid
- * any iteration of shared state.
- * The handlers can cause computation to early exit by returning {break: R}.
- * Neither of the collections should be changed during the comparison process (in your callbacks), as this method assumes they will not be mutated.
- * @param other The tree to compute a diff against.
- * @param onlyThis Callback invoked for all keys only present in `this`.
- * @param onlyOther Callback invoked for all keys only present in `other`.
- * @param different Callback invoked for all keys with differing values.
- */
- diffAgainst<R>(
- other: BTree<K, V>,
- onlyThis?: (k: K, v: V) => { break?: R } | void,
- onlyOther?: (k: K, v: V) => { break?: R } | void,
- different?: (k: K, vThis: V, vOther: V) => { break?: R } | void,
- ): R | undefined {
- if (other._compare !== this._compare) {
- throw new Error("Tree comparators are not the same.");
- }
-
- if (this.isEmpty || other.isEmpty) {
- if (this.isEmpty && other.isEmpty) return undefined;
- // If one tree is empty, everything will be an onlyThis/onlyOther.
- if (this.isEmpty)
- return onlyOther === undefined
- ? undefined
- : BTree.stepToEnd(BTree.makeDiffCursor(other), onlyOther);
- return onlyThis === undefined
- ? undefined
- : BTree.stepToEnd(BTree.makeDiffCursor(this), onlyThis);
- }
-
- // Cursor-based diff algorithm is as follows:
- // - Until neither cursor has navigated to the end of the tree, do the following:
- // - If the `this` cursor is "behind" the `other` cursor (strictly <, via compare), advance it.
- // - Otherwise, advance the `other` cursor.
- // - Any time a cursor is stepped, perform the following:
- // - If either cursor points to a key/value pair:
- // - If thisCursor === otherCursor and the values differ, it is a Different.
- // - If thisCursor > otherCursor and otherCursor is at a key/value pair, it is an OnlyOther.
- // - If thisCursor < otherCursor and thisCursor is at a key/value pair, it is an OnlyThis as long as the most recent
- // cursor step was *not* otherCursor advancing from a tie. The extra condition avoids erroneous OnlyOther calls
- // that would occur due to otherCursor being the "leader".
- // - Otherwise, if both cursors point to nodes, compare them. If they are equal by reference (shared), skip
- // both cursors to the next node in the walk.
- // - Once one cursor has finished stepping, any remaining steps (if any) are taken and key/value pairs are logged
- // as OnlyOther (if otherCursor is stepping) or OnlyThis (if thisCursor is stepping).
- // This algorithm gives the critical guarantee that all locations (both nodes and key/value pairs) in both trees that
- // are identical by value (and possibly by reference) will be visited *at the same time* by the cursors.
- // This removes the possibility of emitting incorrect diffs, as well as allowing for skipping shared nodes.
- const { _compare } = this;
- const thisCursor = BTree.makeDiffCursor(this);
- const otherCursor = BTree.makeDiffCursor(other);
- // It doesn't matter how thisSteppedLast is initialized.
- // Step order is only used when either cursor is at a leaf, and cursors always start at a node.
- let thisSuccess = true,
- otherSuccess = true,
- prevCursorOrder = BTree.compare(thisCursor, otherCursor, _compare);
- while (thisSuccess && otherSuccess) {
- const cursorOrder = BTree.compare(thisCursor, otherCursor, _compare);
- const {
- leaf: thisLeaf,
- internalSpine: thisInternalSpine,
- levelIndices: thisLevelIndices,
- } = thisCursor;
- const {
- leaf: otherLeaf,
- internalSpine: otherInternalSpine,
- levelIndices: otherLevelIndices,
- } = otherCursor;
- if (thisLeaf || otherLeaf) {
- // If the cursors were at the same location last step, then there is no work to be done.
- if (prevCursorOrder !== 0) {
- if (cursorOrder === 0) {
- if (thisLeaf && otherLeaf && different) {
- // Equal keys, check for modifications
- const valThis =
- thisLeaf.values[thisLevelIndices[thisLevelIndices.length - 1]];
- const valOther =
- otherLeaf.values[
- otherLevelIndices[otherLevelIndices.length - 1]
- ];
- if (!Object.is(valThis, valOther)) {
- const result = different(
- thisCursor.currentKey,
- valThis,
- valOther,
- );
- if (result && result.break) return result.break;
- }
- }
- } else if (cursorOrder > 0) {
- // If this is the case, we know that either:
- // 1. otherCursor stepped last from a starting position that trailed thisCursor, and is still behind, or
- // 2. thisCursor stepped last and leapfrogged otherCursor
- // Either of these cases is an "only other"
- if (otherLeaf && onlyOther) {
- const otherVal =
- otherLeaf.values[
- otherLevelIndices[otherLevelIndices.length - 1]
- ];
- const result = onlyOther(otherCursor.currentKey, otherVal);
- if (result && result.break) return result.break;
- }
- } else if (onlyThis) {
- if (thisLeaf && prevCursorOrder !== 0) {
- const valThis =
- thisLeaf.values[thisLevelIndices[thisLevelIndices.length - 1]];
- const result = onlyThis(thisCursor.currentKey, valThis);
- if (result && result.break) return result.break;
- }
- }
- }
- } else if (!thisLeaf && !otherLeaf && cursorOrder === 0) {
- const lastThis = thisInternalSpine.length - 1;
- const lastOther = otherInternalSpine.length - 1;
- const nodeThis =
- thisInternalSpine[lastThis][thisLevelIndices[lastThis]];
- const nodeOther =
- otherInternalSpine[lastOther][otherLevelIndices[lastOther]];
- if (nodeOther === nodeThis) {
- prevCursorOrder = 0;
- thisSuccess = BTree.step(thisCursor, true);
- otherSuccess = BTree.step(otherCursor, true);
- continue;
- }
- }
- prevCursorOrder = cursorOrder;
- if (cursorOrder < 0) {
- thisSuccess = BTree.step(thisCursor);
- } else {
- otherSuccess = BTree.step(otherCursor);
- }
- }
-
- if (thisSuccess && onlyThis)
- return BTree.finishCursorWalk(
- thisCursor,
- otherCursor,
- _compare,
- onlyThis,
- );
- if (otherSuccess && onlyOther)
- return BTree.finishCursorWalk(
- otherCursor,
- thisCursor,
- _compare,
- onlyOther,
- );
- return undefined;
- }
-
- ///////////////////////////////////////////////////////////////////////////
- // Helper methods for diffAgainst /////////////////////////////////////////
-
- private static finishCursorWalk<K, V, R>(
- cursor: DiffCursor<K, V>,
- cursorFinished: DiffCursor<K, V>,
- compareKeys: (a: K, b: K) => number,
- callback: (k: K, v: V) => { break?: R } | void,
- ): R | undefined {
- const compared = BTree.compare(cursor, cursorFinished, compareKeys);
- if (compared === 0) {
- if (!BTree.step(cursor)) return undefined;
- } else if (compared < 0) {
- check(false, "cursor walk terminated early");
- }
- return BTree.stepToEnd(cursor, callback);
- }
-
- private static stepToEnd<K, V, R>(
- cursor: DiffCursor<K, V>,
- callback: (k: K, v: V) => { break?: R } | void,
- ): R | undefined {
- let canStep: boolean = true;
- while (canStep) {
- const { leaf, levelIndices, currentKey } = cursor;
- if (leaf) {
- const value = leaf.values[levelIndices[levelIndices.length - 1]];
- const result = callback(currentKey, value);
- if (result && result.break) return result.break;
- }
- canStep = BTree.step(cursor);
- }
- return undefined;
- }
-
- private static makeDiffCursor<K, V>(tree: BTree<K, V>): DiffCursor<K, V> {
- const { _root, height } = tree;
- return {
- height: height,
- internalSpine: [[_root]],
- levelIndices: [0],
- leaf: undefined,
- currentKey: _root.maxKey(),
- };
- }
-
- /**
- * Advances the cursor to the next step in the walk of its tree.
- * Cursors are walked backwards in sort order, as this allows them to leverage maxKey() in order to be compared in O(1).
- * @param cursor The cursor to step
- * @param stepToNode If true, the cursor will be advanced to the next node (skipping values)
- * @returns true if the step was completed and false if the step would have caused the cursor to move beyond the end of the tree.
- */
- private static step<K, V>(
- cursor: DiffCursor<K, V>,
- stepToNode?: boolean,
- ): boolean {
- const { internalSpine, levelIndices, leaf } = cursor;
- if (stepToNode === true || leaf) {
- const levelsLength = levelIndices.length;
- // Step to the next node only if:
- // - We are explicitly directed to via stepToNode, or
- // - There are no key/value pairs left to step to in this leaf
- if (stepToNode === true || levelIndices[levelsLength - 1] === 0) {
- const spineLength = internalSpine.length;
- // Root is leaf
- if (spineLength === 0) return false;
- // Walk back up the tree until we find a new subtree to descend into
- const nodeLevelIndex = spineLength - 1;
- let levelIndexWalkBack = nodeLevelIndex;
- while (levelIndexWalkBack >= 0) {
- if (levelIndices[levelIndexWalkBack] > 0) {
- if (levelIndexWalkBack < levelsLength - 1) {
- // Remove leaf state from cursor
- cursor.leaf = undefined;
- levelIndices.pop();
- }
- // If we walked upwards past any internal node, slice them out
- if (levelIndexWalkBack < nodeLevelIndex)
- cursor.internalSpine = internalSpine.slice(
- 0,
- levelIndexWalkBack + 1,
- );
- // Move to new internal node
- cursor.currentKey =
- internalSpine[levelIndexWalkBack][
- --levelIndices[levelIndexWalkBack]
- ].maxKey();
- return true;
- }
- levelIndexWalkBack--;
- }
- // Cursor is in the far left leaf of the tree, no more nodes to enumerate
- return false;
- } else {
- // Move to new leaf value
- const valueIndex = --levelIndices[levelsLength - 1];
- cursor.currentKey = (leaf as unknown as BNode<K, V>).keys[valueIndex];
- return true;
- }
- } else {
- // Cursor does not point to a value in a leaf, so move downwards
- const nextLevel = internalSpine.length;
- const currentLevel = nextLevel - 1;
- const node = internalSpine[currentLevel][levelIndices[currentLevel]];
- if (node.isLeaf) {
- // Entering into a leaf. Set the cursor to point at the last key/value pair.
- cursor.leaf = node;
- const valueIndex = (levelIndices[nextLevel] = node.values.length - 1);
- cursor.currentKey = node.keys[valueIndex];
- } else {
- const children = (node as BNodeInternal<K, V>).children;
- internalSpine[nextLevel] = children;
- const childIndex = children.length - 1;
- levelIndices[nextLevel] = childIndex;
- cursor.currentKey = children[childIndex].maxKey();
- }
- return true;
- }
- }
-
- /**
- * Compares the two cursors. Returns a value indicating which cursor is ahead in a walk.
- * Note that cursors are advanced in reverse sorting order.
- */
- private static compare<K, V>(
- cursorA: DiffCursor<K, V>,
- cursorB: DiffCursor<K, V>,
- compareKeys: (a: K, b: K) => number,
- ): number {
- const {
- height: heightA,
- currentKey: currentKeyA,
- levelIndices: levelIndicesA,
- } = cursorA;
- const {
- height: heightB,
- currentKey: currentKeyB,
- levelIndices: levelIndicesB,
- } = cursorB;
- // Reverse the comparison order, as cursors are advanced in reverse sorting order
- const keyComparison = compareKeys(currentKeyB, currentKeyA);
- if (keyComparison !== 0) {
- return keyComparison;
- }
-
- // Normalize depth values relative to the shortest tree.
- // This ensures that concurrent cursor walks of trees of differing heights can reliably land on shared nodes at the same time.
- // To accomplish this, a cursor that is on an internal node at depth D1 with maxKey X is considered "behind" a cursor on an
- // internal node at depth D2 with maxKey Y, when D1 < D2. Thus, always walking the cursor that is "behind" will allow the cursor
- // at shallower depth (but equal maxKey) to "catch up" and land on shared nodes.
- const heightMin = heightA < heightB ? heightA : heightB;
- const depthANormalized = levelIndicesA.length - (heightA - heightMin);
- const depthBNormalized = levelIndicesB.length - (heightB - heightMin);
- return depthANormalized - depthBNormalized;
- }
-
- // End of helper methods for diffAgainst //////////////////////////////////
- ///////////////////////////////////////////////////////////////////////////
-
- /** Returns a new iterator for iterating the keys of each pair in ascending order.
- * @param firstKey: Minimum key to include in the output. */
- keys(firstKey?: K): IterableIterator<K> {
- var it = this.entries(firstKey, ReusedArray);
- return iterator<K>(() => {
- var n: IteratorResult<any> = it.next();
- if (n.value) n.value = n.value[0];
- return n;
- });
- }
-
- /** Returns a new iterator for iterating the values of each pair in order by key.
- * @param firstKey: Minimum key whose associated value is included in the output. */
- values(firstKey?: K): IterableIterator<V> {
- var it = this.entries(firstKey, ReusedArray);
- return iterator<V>(() => {
- var n: IteratorResult<any> = it.next();
- if (n.value) n.value = n.value[1];
- return n;
- });
- }
-
- /////////////////////////////////////////////////////////////////////////////
- // Additional methods ///////////////////////////////////////////////////////
-
- /** Returns the maximum number of children/values before nodes will split. */
- get maxNodeSize() {
- return this._maxNodeSize;
- }
-
- /** Gets the lowest key in the tree. Complexity: O(log size) */
- minKey(): K | undefined {
- return this._root.minKey();
- }
-
- /** Gets the highest key in the tree. Complexity: O(1) */
- maxKey(): K | undefined {
- return this._root.maxKey();
- }
-
- /** Quickly clones the tree by marking the root node as shared.
- * Both copies remain editable. When you modify either copy, any
- * nodes that are shared (or potentially shared) between the two
- * copies are cloned so that the changes do not affect other copies.
- * This is known as copy-on-write behavior, or "lazy copying". */
- clone(): BTree<K, V> {
- this._root.isShared = true;
- var result = new BTree<K, V>(undefined, this._compare, this._maxNodeSize);
- result._root = this._root;
- result._size = this._size;
- return result;
- }
-
- /** Performs a greedy clone, immediately duplicating any nodes that are
- * not currently marked as shared, in order to avoid marking any nodes
- * as shared.
- * @param force Clone all nodes, even shared ones.
- */
- greedyClone(force?: boolean): BTree<K, V> {
- var result = new BTree<K, V>(undefined, this._compare, this._maxNodeSize);
- result._root = this._root.greedyClone(force);
- result._size = this._size;
- return result;
- }
-
- /** Gets an array filled with the contents of the tree, sorted by key */
- toArray(maxLength: number = 0x7fffffff): [K, V][] {
- let min = this.minKey(),
- max = this.maxKey();
- if (min !== undefined) return this.getRange(min, max!, true, maxLength);
- return [];
- }
-
- /** Gets an array of all keys, sorted */
- keysArray() {
- var results: K[] = [];
- this._root.forRange(
- this.minKey()!,
- this.maxKey()!,
- true,
- false,
- this,
- 0,
- (k, v) => {
- results.push(k);
- },
- );
- return results;
- }
-
- /** Gets an array of all values, sorted by key */
- valuesArray() {
- var results: V[] = [];
- this._root.forRange(
- this.minKey()!,
- this.maxKey()!,
- true,
- false,
- this,
- 0,
- (k, v) => {
- results.push(v);
- },
- );
- return results;
- }
-
- /** Gets a string representing the tree's data based on toArray(). */
- toString() {
- return this.toArray().toString();
- }
-
- /** Stores a key-value pair only if the key doesn't already exist in the tree.
- * @returns true if a new key was added
- */
- setIfNotPresent(key: K, value: V): boolean {
- return this.set(key, value, false);
- }
-
- /** Returns the next pair whose key is larger than the specified key (or undefined if there is none).
- * If key === undefined, this function returns the lowest pair.
- * @param key The key to search for.
- * @param reusedArray Optional array used repeatedly to store key-value pairs, to
- * avoid creating a new array on every iteration.
- */
- nextHigherPair(key: K | undefined, reusedArray?: [K, V]): [K, V] | undefined {
- reusedArray = reusedArray || ([] as unknown as [K, V]);
- if (key === undefined) {
- return this._root.minPair(reusedArray);
- }
- return this._root.getPairOrNextHigher(
- key,
- this._compare,
- false,
- reusedArray,
- );
- }
-
- /** Returns the next key larger than the specified key, or undefined if there is none.
- * Also, nextHigherKey(undefined) returns the lowest key.
- */
- nextHigherKey(key: K | undefined): K | undefined {
- var p = this.nextHigherPair(key, ReusedArray as [K, V]);
- return p && p[0];
- }
-
- /** Returns the next pair whose key is smaller than the specified key (or undefined if there is none).
- * If key === undefined, this function returns the highest pair.
- * @param key The key to search for.
- * @param reusedArray Optional array used repeatedly to store key-value pairs, to
- * avoid creating a new array each time you call this method.
- */
- nextLowerPair(key: K | undefined, reusedArray?: [K, V]): [K, V] | undefined {
- reusedArray = reusedArray || ([] as unknown as [K, V]);
- if (key === undefined) {
- return this._root.maxPair(reusedArray);
- }
- return this._root.getPairOrNextLower(
- key,
- this._compare,
- false,
- reusedArray,
- );
- }
-
- /** Returns the next key smaller than the specified key, or undefined if there is none.
- * Also, nextLowerKey(undefined) returns the highest key.
- */
- nextLowerKey(key: K | undefined): K | undefined {
- var p = this.nextLowerPair(key, ReusedArray as [K, V]);
- return p && p[0];
- }
-
- /** Returns the key-value pair associated with the supplied key if it exists
- * or the pair associated with the next lower pair otherwise. If there is no
- * next lower pair, undefined is returned.
- * @param key The key to search for.
- * @param reusedArray Optional array used repeatedly to store key-value pairs, to
- * avoid creating a new array each time you call this method.
- * */
- getPairOrNextLower(key: K, reusedArray?: [K, V]): [K, V] | undefined {
- return this._root.getPairOrNextLower(
- key,
- this._compare,
- true,
- reusedArray || ([] as unknown as [K, V]),
- );
- }
-
- /** Returns the key-value pair associated with the supplied key if it exists
- * or the pair associated with the next lower pair otherwise. If there is no
- * next lower pair, undefined is returned.
- * @param key The key to search for.
- * @param reusedArray Optional array used repeatedly to store key-value pairs, to
- * avoid creating a new array each time you call this method.
- * */
- getPairOrNextHigher(key: K, reusedArray?: [K, V]): [K, V] | undefined {
- return this._root.getPairOrNextHigher(
- key,
- this._compare,
- true,
- reusedArray || ([] as unknown as [K, V]),
- );
- }
-
- /** Edits the value associated with a key in the tree, if it already exists.
- * @returns true if the key existed, false if not.
- */
- changeIfPresent(key: K, value: V): boolean {
- return this.editRange(key, key, true, (k, v) => ({ value })) !== 0;
- }
-
- /**
- * Builds an array of pairs from the specified range of keys, sorted by key.
- * Each returned pair is also an array: pair[0] is the key, pair[1] is the value.
- * @param low The first key in the array will be greater than or equal to `low`.
- * @param high This method returns when a key larger than this is reached.
- * @param includeHigh If the `high` key is present, its pair will be included
- * in the output if and only if this parameter is true. Note: if the
- * `low` key is present, it is always included in the output.
- * @param maxLength Length limit. getRange will stop scanning the tree when
- * the array reaches this size.
- * @description Computational complexity: O(result.length + log size)
- */
- getRange(
- low: K,
- high: K,
- includeHigh?: boolean,
- maxLength: number = 0x3ffffff,
- ): [K, V][] {
- var results: [K, V][] = [];
- this._root.forRange(low, high, includeHigh, false, this, 0, (k, v) => {
- results.push([k, v]);
- return results.length > maxLength ? Break : undefined;
- });
- return results;
- }
-
- /** Adds all pairs from a list of key-value pairs.
- * @param pairs Pairs to add to this tree. If there are duplicate keys,
- * later pairs currently overwrite earlier ones (e.g. [[0,1],[0,7]]
- * associates 0 with 7.)
- * @param overwrite Whether to overwrite pairs that already exist (if false,
- * pairs[i] is ignored when the key pairs[i][0] already exists.)
- * @returns The number of pairs added to the collection.
- * @description Computational complexity: O(pairs.length * log(size + pairs.length))
- */
- setPairs(pairs: [K, V][], overwrite?: boolean): number {
- var added = 0;
- for (var i = 0; i < pairs.length; i++)
- if (this.set(pairs[i][0], pairs[i][1], overwrite)) added++;
- return added;
- }
-
- forRange(
- low: K,
- high: K,
- includeHigh: boolean,
- onFound?: (k: K, v: V, counter: number) => void,
- initialCounter?: number,
- ): number;
-
- /**
- * Scans the specified range of keys, in ascending order by key.
- * Note: the callback `onFound` must not insert or remove items in the
- * collection. Doing so may cause incorrect data to be sent to the
- * callback afterward.
- * @param low The first key scanned will be greater than or equal to `low`.
- * @param high Scanning stops when a key larger than this is reached.
- * @param includeHigh If the `high` key is present, `onFound` is called for
- * that final pair if and only if this parameter is true.
- * @param onFound A function that is called for each key-value pair. This
- * function can return {break:R} to stop early with result R.
- * @param initialCounter Initial third argument of onFound. This value
- * increases by one each time `onFound` is called. Default: 0
- * @returns The number of values found, or R if the callback returned
- * `{break:R}` to stop early.
- * @description Computational complexity: O(number of items scanned + log size)
- */
- forRange<R = number>(
- low: K,
- high: K,
- includeHigh: boolean,
- onFound?: (k: K, v: V, counter: number) => { break?: R } | void,
- initialCounter?: number,
- ): R | number {
- var r = this._root.forRange(
- low,
- high,
- includeHigh,
- false,
- this,
- initialCounter || 0,
- onFound,
- );
- return typeof r === "number" ? r : r.break!;
- }
-
- /**
- * Scans and potentially modifies values for a subsequence of keys.
- * Note: the callback `onFound` should ideally be a pure function.
- * Specifically, it must not insert items, call clone(), or change
- * the collection except via return value; out-of-band editing may
- * cause an exception or may cause incorrect data to be sent to
- * the callback (duplicate or missed items). It must not cause a
- * clone() of the collection, otherwise the clone could be modified
- * by changes requested by the callback.
- * @param low The first key scanned will be greater than or equal to `low`.
- * @param high Scanning stops when a key larger than this is reached.
- * @param includeHigh If the `high` key is present, `onFound` is called for
- * that final pair if and only if this parameter is true.
- * @param onFound A function that is called for each key-value pair. This
- * function can return `{value:v}` to change the value associated
- * with the current key, `{delete:true}` to delete the current pair,
- * `{break:R}` to stop early with result R, or it can return nothing
- * (undefined or {}) to cause no effect and continue iterating.
- * `{break:R}` can be combined with one of the other two commands.
- * The third argument `counter` is the number of items iterated
- * previously; it equals 0 when `onFound` is called the first time.
- * @returns The number of values scanned, or R if the callback returned
- * `{break:R}` to stop early.
- * @description
- * Computational complexity: O(number of items scanned + log size)
- * Note: if the tree has been cloned with clone(), any shared
- * nodes are copied before `onFound` is called. This takes O(n) time
- * where n is proportional to the amount of shared data scanned.
- */
- editRange<R = V>(
- low: K,
- high: K,
- includeHigh: boolean,
- onFound: (k: K, v: V, counter: number) => EditRangeResult<V, R> | void,
- initialCounter?: number,
- ): R | number {
- var root = this._root;
- if (root.isShared) this._root = root = root.clone();
- try {
- var r = root.forRange(
- low,
- high,
- includeHigh,
- true,
- this,
- initialCounter || 0,
- onFound,
- );
- return typeof r === "number" ? r : r.break!;
- } finally {
- while (root.keys.length <= 1 && !root.isLeaf)
- this._root = root =
- root.keys.length === 0
- ? EmptyLeaf
- : (root as any as BNodeInternal<K, V>).children[0];
- }
- }
-
- /** Same as `editRange` except that the callback is called for all pairs. */
- editAll<R = V>(
- onFound: (k: K, v: V, counter: number) => EditRangeResult<V, R> | void,
- initialCounter?: number,
- ): R | number {
- return this.editRange(
- this.minKey()!,
- this.maxKey()!,
- true,
- onFound,
- initialCounter,
- );
- }
-
- /**
- * Removes a range of key-value pairs from the B+ tree.
- * @param low The first key scanned will be greater than or equal to `low`.
- * @param high Scanning stops when a key larger than this is reached.
- * @param includeHigh Specifies whether the `high` key, if present, is deleted.
- * @returns The number of key-value pairs that were deleted.
- * @description Computational complexity: O(log size + number of items deleted)
- */
- deleteRange(low: K, high: K, includeHigh: boolean): number {
- return this.editRange(low, high, includeHigh, DeleteRange);
- }
-
- /** Deletes a series of keys from the collection. */
- deleteKeys(keys: K[]): number {
- for (var i = 0, r = 0; i < keys.length; i++) if (this.delete(keys[i])) r++;
- return r;
- }
-
- /** Gets the height of the tree: the number of internal nodes between the
- * BTree object and its leaf nodes (zero if there are no internal nodes). */
- get height(): number {
- let node: BNode<K, V> | undefined = this._root;
- let height = -1;
- while (node) {
- height++;
- node = node.isLeaf
- ? undefined
- : (node as unknown as BNodeInternal<K, V>).children[0];
- }
- return height;
- }
-
- /** Makes the object read-only to ensure it is not accidentally modified.
- * Freezing does not have to be permanent; unfreeze() reverses the effect.
- * This is accomplished by replacing mutator functions with a function
- * that throws an Error. Compared to using a property (e.g. this.isFrozen)
- * this implementation gives better performance in non-frozen BTrees.
- */
- freeze() {
- var t = this as any;
- // Note: all other mutators ultimately call set() or editRange()
- // so we don't need to override those others.
- t.clear =
- t.set =
- t.editRange =
- function () {
- throw new Error("Attempted to modify a frozen BTree");
- };
- }
-
- /** Ensures mutations are allowed, reversing the effect of freeze(). */
- unfreeze() {
- // @ts-ignore "The operand of a 'delete' operator must be optional."
- // (wrong: delete does not affect the prototype.)
- delete this.clear;
- // @ts-ignore
- delete this.set;
- // @ts-ignore
- delete this.editRange;
- }
-
- /** Returns true if the tree appears to be frozen. */
- get isFrozen() {
- return this.hasOwnProperty("editRange");
- }
-
- /** Scans the tree for signs of serious bugs (e.g. this.size doesn't match
- * number of elements, internal nodes not caching max element properly...)
- * Computational complexity: O(number of nodes), i.e. O(size). This method
- * skips the most expensive test - whether all keys are sorted - but it
- * does check that maxKey() of the children of internal nodes are sorted. */
- checkValid() {
- var size = this._root.checkValid(0, this, 0);
- check(
- size === this.size,
- "size mismatch: counted ",
- size,
- "but stored",
- this.size,
- );
- }
-}
-
-declare const Symbol: any;
-if (Symbol && Symbol.iterator)
- // iterator is equivalent to entries()
- (BTree as any).prototype[Symbol.iterator] = BTree.prototype.entries;
-(BTree as any).prototype.where = BTree.prototype.filter;
-(BTree as any).prototype.setRange = BTree.prototype.setPairs;
-(BTree as any).prototype.add = BTree.prototype.set;
-
-function iterator<T>(
- next: () => IteratorResult<T> = () => ({ done: true, value: undefined }),
-): IterableIterator<T> {
- var result: any = { next };
- if (Symbol && Symbol.iterator)
- result[Symbol.iterator] = function () {
- return this;
- };
- return result;
-}
-
-/** Leaf node / base class. **************************************************/
-class BNode<K, V> {
- // If this is an internal node, _keys[i] is the highest key in children[i].
- keys: K[];
- values: V[];
- isShared: true | undefined;
- get isLeaf() {
- return (this as any).children === undefined;
- }
-
- constructor(keys: K[] = [], values?: V[]) {
- this.keys = keys;
- this.values = values || (undefVals as any[]);
- this.isShared = undefined;
- }
-
- ///////////////////////////////////////////////////////////////////////////
- // Shared methods /////////////////////////////////////////////////////////
-
- maxKey() {
- return this.keys[this.keys.length - 1];
- }
-
- // If key not found, returns i^failXor where i is the insertion index.
- // Callers that don't care whether there was a match will set failXor=0.
- indexOf(key: K, failXor: number, cmp: (a: K, b: K) => number): index {
- const keys = this.keys;
- var lo = 0,
- hi = keys.length,
- mid = hi >> 1;
- while (lo < hi) {
- var c = cmp(keys[mid], key);
- if (c < 0) lo = mid + 1;
- else if (c > 0)
- // key < keys[mid]
- hi = mid;
- else if (c === 0) return mid;
- else {
- // c is NaN or otherwise invalid
- if (key === key)
- // at least the search key is not NaN
- return keys.length;
- else throw new Error("BTree: NaN was used as a key");
- }
- mid = (lo + hi) >> 1;
- }
- return mid ^ failXor;
-
- // Unrolled version: benchmarks show same speed, not worth using
- /*var i = 1, c: number = 0, sum = 0;
- if (keys.length >= 4) {
- i = 3;
- if (keys.length >= 8) {
- i = 7;
- if (keys.length >= 16) {
- i = 15;
- if (keys.length >= 32) {
- i = 31;
- if (keys.length >= 64) {
- i = 127;
- i += (c = i < keys.length ? cmp(keys[i], key) : 1) < 0 ? 64 : -64;
- sum += c;
- i += (c = i < keys.length ? cmp(keys[i], key) : 1) < 0 ? 32 : -32;
- sum += c;
- }
- i += (c = i < keys.length ? cmp(keys[i], key) : 1) < 0 ? 16 : -16;
- sum += c;
- }
- i += (c = i < keys.length ? cmp(keys[i], key) : 1) < 0 ? 8 : -8;
- sum += c;
- }
- i += (c = i < keys.length ? cmp(keys[i], key) : 1) < 0 ? 4 : -4;
- sum += c;
- }
- i += (c = i < keys.length ? cmp(keys[i], key) : 1) < 0 ? 2 : -2;
- sum += c;
- }
- i += (c = i < keys.length ? cmp(keys[i], key) : 1) < 0 ? 1 : -1;
- c = i < keys.length ? cmp(keys[i], key) : 1;
- sum += c;
- if (c < 0) {
- ++i;
- c = i < keys.length ? cmp(keys[i], key) : 1;
- sum += c;
- }
- if (sum !== sum) {
- if (key === key) // at least the search key is not NaN
- return keys.length ^ failXor;
- else
- throw new Error("BTree: NaN was used as a key");
- }
- return c === 0 ? i : i ^ failXor;*/
- }
-
- /////////////////////////////////////////////////////////////////////////////
- // Leaf Node: misc //////////////////////////////////////////////////////////
-
- minKey(): K | undefined {
- return this.keys[0];
- }
-
- minPair(reusedArray: [K, V]): [K, V] | undefined {
- if (this.keys.length === 0) return undefined;
- reusedArray[0] = this.keys[0];
- reusedArray[1] = this.values[0];
- return reusedArray;
- }
-
- maxPair(reusedArray: [K, V]): [K, V] | undefined {
- if (this.keys.length === 0) return undefined;
- const lastIndex = this.keys.length - 1;
- reusedArray[0] = this.keys[lastIndex];
- reusedArray[1] = this.values[lastIndex];
- return reusedArray;
- }
-
- clone(): BNode<K, V> {
- var v = this.values;
- return new BNode<K, V>(
- this.keys.slice(0),
- v === undefVals ? v : v.slice(0),
- );
- }
-
- greedyClone(force?: boolean): BNode<K, V> {
- return this.isShared && !force ? this : this.clone();
- }
-
- get(key: K, defaultValue: V | undefined, tree: BTree<K, V>): V | undefined {
- var i = this.indexOf(key, -1, tree._compare);
- return i < 0 ? defaultValue : this.values[i];
- }
-
- getPairOrNextLower(
- key: K,
- compare: (a: K, b: K) => number,
- inclusive: boolean,
- reusedArray: [K, V],
- ): [K, V] | undefined {
- var i = this.indexOf(key, -1, compare);
- const indexOrLower = i < 0 ? ~i - 1 : inclusive ? i : i - 1;
- if (indexOrLower >= 0) {
- reusedArray[0] = this.keys[indexOrLower];
- reusedArray[1] = this.values[indexOrLower];
- return reusedArray;
- }
- return undefined;
- }
-
- getPairOrNextHigher(
- key: K,
- compare: (a: K, b: K) => number,
- inclusive: boolean,
- reusedArray: [K, V],
- ): [K, V] | undefined {
- var i = this.indexOf(key, -1, compare);
- const indexOrLower = i < 0 ? ~i : inclusive ? i : i + 1;
- const keys = this.keys;
- if (indexOrLower < keys.length) {
- reusedArray[0] = keys[indexOrLower];
- reusedArray[1] = this.values[indexOrLower];
- return reusedArray;
- }
- return undefined;
- }
-
- checkValid(depth: number, tree: BTree<K, V>, baseIndex: number): number {
- var kL = this.keys.length,
- vL = this.values.length;
- check(
- this.values === undefVals ? kL <= vL : kL === vL,
- "keys/values length mismatch: depth",
- depth,
- "with lengths",
- kL,
- vL,
- "and baseIndex",
- baseIndex,
- );
- // Note: we don't check for "node too small" because sometimes a node
- // can legitimately have size 1. This occurs if there is a batch
- // deletion, leaving a node of size 1, and the siblings are full so
- // it can't be merged with adjacent nodes. However, the parent will
- // verify that the average node size is at least half of the maximum.
- check(
- depth == 0 || kL > 0,
- "empty leaf at depth",
- depth,
- "and baseIndex",
- baseIndex,
- );
- return kL;
- }
-
- /////////////////////////////////////////////////////////////////////////////
- // Leaf Node: set & node splitting //////////////////////////////////////////
-
- set(
- key: K,
- value: V,
- overwrite: boolean | undefined,
- tree: BTree<K, V>,
- ): boolean | BNode<K, V> {
- var i = this.indexOf(key, -1, tree._compare);
- if (i < 0) {
- // key does not exist yet
- i = ~i;
- tree._size++;
-
- if (this.keys.length < tree._maxNodeSize) {
- return this.insertInLeaf(i, key, value, tree);
- } else {
- // This leaf node is full and must split
- var newRightSibling = this.splitOffRightSide(),
- target: BNode<K, V> = this;
- if (i > this.keys.length) {
- i -= this.keys.length;
- target = newRightSibling;
- }
- target.insertInLeaf(i, key, value, tree);
- return newRightSibling;
- }
- } else {
- // Key already exists
- if (overwrite !== false) {
- if (value !== undefined) this.reifyValues();
- // usually this is a no-op, but some users may wish to edit the key
- this.keys[i] = key;
- this.values[i] = value;
- }
- return false;
- }
- }
-
- reifyValues() {
- if (this.values === undefVals)
- return (this.values = this.values.slice(0, this.keys.length));
- return this.values;
- }
-
- insertInLeaf(i: index, key: K, value: V, tree: BTree<K, V>) {
- this.keys.splice(i, 0, key);
- if (this.values === undefVals) {
- while (undefVals.length < tree._maxNodeSize) undefVals.push(undefined);
- if (value === undefined) {
- return true;
- } else {
- this.values = undefVals.slice(0, this.keys.length - 1);
- }
- }
- this.values.splice(i, 0, value);
- return true;
- }
-
- takeFromRight(rhs: BNode<K, V>) {
- // Reminder: parent node must update its copy of key for this node
- // assert: neither node is shared
- // assert rhs.keys.length > (maxNodeSize/2 && this.keys.length<maxNodeSize)
- var v = this.values;
- if (rhs.values === undefVals) {
- if (v !== undefVals) v.push(undefined as any);
- } else {
- v = this.reifyValues();
- v.push(rhs.values.shift()!);
- }
- this.keys.push(rhs.keys.shift()!);
- }
-
- takeFromLeft(lhs: BNode<K, V>) {
- // Reminder: parent node must update its copy of key for this node
- // assert: neither node is shared
- // assert rhs.keys.length > (maxNodeSize/2 && this.keys.length<maxNodeSize)
- var v = this.values;
- if (lhs.values === undefVals) {
- if (v !== undefVals) v.unshift(undefined as any);
- } else {
- v = this.reifyValues();
- v.unshift(lhs.values.pop()!);
- }
- this.keys.unshift(lhs.keys.pop()!);
- }
-
- splitOffRightSide(): BNode<K, V> {
- // Reminder: parent node must update its copy of key for this node
- var half = this.keys.length >> 1,
- keys = this.keys.splice(half);
- var values =
- this.values === undefVals ? undefVals : this.values.splice(half);
- return new BNode<K, V>(keys, values);
- }
-
- /////////////////////////////////////////////////////////////////////////////
- // Leaf Node: scanning & deletions //////////////////////////////////////////
-
- forRange<R>(
- low: K,
- high: K,
- includeHigh: boolean | undefined,
- editMode: boolean,
- tree: BTree<K, V>,
- count: number,
- onFound?: (k: K, v: V, counter: number) => EditRangeResult<V, R> | void,
- ): EditRangeResult<V, R> | number {
- var cmp = tree._compare;
- var iLow, iHigh;
- if (high === low) {
- if (!includeHigh) return count;
- iHigh = (iLow = this.indexOf(low, -1, cmp)) + 1;
- if (iLow < 0) return count;
- } else {
- iLow = this.indexOf(low, 0, cmp);
- iHigh = this.indexOf(high, -1, cmp);
- if (iHigh < 0) iHigh = ~iHigh;
- else if (includeHigh === true) iHigh++;
- }
- var keys = this.keys,
- values = this.values;
- if (onFound !== undefined) {
- for (var i = iLow; i < iHigh; i++) {
- var key = keys[i];
- var result = onFound(key, values[i], count++);
- if (result !== undefined) {
- if (editMode === true) {
- if (key !== keys[i] || this.isShared === true)
- throw new Error("BTree illegally changed or cloned in editRange");
- if (result.delete) {
- this.keys.splice(i, 1);
- if (this.values !== undefVals) this.values.splice(i, 1);
- tree._size--;
- i--;
- iHigh--;
- } else if (result.hasOwnProperty("value")) {
- values![i] = result.value!;
- }
- }
- if (result.break !== undefined) return result;
- }
- }
- } else count += iHigh - iLow;
- return count;
- }
-
- /** Adds entire contents of right-hand sibling (rhs is left unchanged) */
- mergeSibling(rhs: BNode<K, V>, _: number) {
- this.keys.push.apply(this.keys, rhs.keys);
- if (this.values === undefVals) {
- if (rhs.values === undefVals) return;
- this.values = this.values.slice(0, this.keys.length);
- }
- this.values.push.apply(this.values, rhs.reifyValues());
- }
-}
-
-/** Internal node (non-leaf node) ********************************************/
-class BNodeInternal<K, V> extends BNode<K, V> {
- // Note: conventionally B+ trees have one fewer key than the number of
- // children, but I find it easier to keep the array lengths equal: each
- // keys[i] caches the value of children[i].maxKey().
- children: BNode<K, V>[];
-
- constructor(children: BNode<K, V>[], keys?: K[]) {
- if (!keys) {
- keys = [];
- for (var i = 0; i < children.length; i++) keys[i] = children[i].maxKey();
- }
- super(keys);
- this.children = children;
- }
-
- clone(): BNode<K, V> {
- var children = this.children.slice(0);
- for (var i = 0; i < children.length; i++) children[i].isShared = true;
- return new BNodeInternal<K, V>(children, this.keys.slice(0));
- }
-
- greedyClone(force?: boolean): BNode<K, V> {
- if (this.isShared && !force) return this;
- var nu = new BNodeInternal<K, V>(
- this.children.slice(0),
- this.keys.slice(0),
- );
- for (var i = 0; i < nu.children.length; i++)
- nu.children[i] = nu.children[i].greedyClone();
- return nu;
- }
-
- minKey() {
- return this.children[0].minKey();
- }
-
- minPair(reusedArray: [K, V]): [K, V] | undefined {
- return this.children[0].minPair(reusedArray);
- }
-
- maxPair(reusedArray: [K, V]): [K, V] | undefined {
- return this.children[this.children.length - 1].maxPair(reusedArray);
- }
-
- get(key: K, defaultValue: V | undefined, tree: BTree<K, V>): V | undefined {
- var i = this.indexOf(key, 0, tree._compare),
- children = this.children;
- return i < children.length
- ? children[i].get(key, defaultValue, tree)
- : undefined;
- }
-
- getPairOrNextLower(
- key: K,
- compare: (a: K, b: K) => number,
- inclusive: boolean,
- reusedArray: [K, V],
- ): [K, V] | undefined {
- var i = this.indexOf(key, 0, compare),
- children = this.children;
- if (i >= children.length) return this.maxPair(reusedArray);
- const result = children[i].getPairOrNextLower(
- key,
- compare,
- inclusive,
- reusedArray,
- );
- if (result === undefined && i > 0) {
- return children[i - 1].maxPair(reusedArray);
- }
- return result;
- }
-
- getPairOrNextHigher(
- key: K,
- compare: (a: K, b: K) => number,
- inclusive: boolean,
- reusedArray: [K, V],
- ): [K, V] | undefined {
- var i = this.indexOf(key, 0, compare),
- children = this.children,
- length = children.length;
- if (i >= length) return undefined;
- const result = children[i].getPairOrNextHigher(
- key,
- compare,
- inclusive,
- reusedArray,
- );
- if (result === undefined && i < length - 1) {
- return children[i + 1].minPair(reusedArray);
- }
- return result;
- }
-
- checkValid(depth: number, tree: BTree<K, V>, baseIndex: number): number {
- let kL = this.keys.length,
- cL = this.children.length;
- check(
- kL === cL,
- "keys/children length mismatch: depth",
- depth,
- "lengths",
- kL,
- cL,
- "baseIndex",
- baseIndex,
- );
- check(
- kL > 1 || depth > 0,
- "internal node has length",
- kL,
- "at depth",
- depth,
- "baseIndex",
- baseIndex,
- );
- let size = 0,
- c = this.children,
- k = this.keys,
- childSize = 0;
- for (var i = 0; i < cL; i++) {
- size += c[i].checkValid(depth + 1, tree, baseIndex + size);
- childSize += c[i].keys.length;
- check(size >= childSize, "wtf", baseIndex); // no way this will ever fail
- check(
- i === 0 || c[i - 1].constructor === c[i].constructor,
- "type mismatch, baseIndex:",
- baseIndex,
- );
- if (c[i].maxKey() != k[i])
- check(
- false,
- "keys[",
- i,
- "] =",
- k[i],
- "is wrong, should be ",
- c[i].maxKey(),
- "at depth",
- depth,
- "baseIndex",
- baseIndex,
- );
- if (!(i === 0 || tree._compare(k[i - 1], k[i]) < 0))
- check(
- false,
- "sort violation at depth",
- depth,
- "index",
- i,
- "keys",
- k[i - 1],
- k[i],
- );
- }
- // 2020/08: BTree doesn't always avoid grossly undersized nodes,
- // but AFAIK such nodes are pretty harmless, so accept them.
- let toofew = childSize === 0; // childSize < (tree.maxNodeSize >> 1)*cL;
- if (toofew || childSize > tree.maxNodeSize * cL)
- check(
- false,
- toofew ? "too few" : "too many",
- "children (",
- childSize,
- size,
- ") at depth",
- depth,
- "maxNodeSize:",
- tree.maxNodeSize,
- "children.length:",
- cL,
- "baseIndex:",
- baseIndex,
- );
- return size;
- }
-
- /////////////////////////////////////////////////////////////////////////////
- // Internal Node: set & node splitting //////////////////////////////////////
-
- set(
- key: K,
- value: V,
- overwrite: boolean | undefined,
- tree: BTree<K, V>,
- ): boolean | BNodeInternal<K, V> {
- var c = this.children,
- max = tree._maxNodeSize,
- cmp = tree._compare;
- var i = Math.min(this.indexOf(key, 0, cmp), c.length - 1),
- child = c[i];
-
- if (child.isShared) c[i] = child = child.clone();
- if (child.keys.length >= max) {
- // child is full; inserting anything else will cause a split.
- // Shifting an item to the left or right sibling may avoid a split.
- // We can do a shift if the adjacent node is not full and if the
- // current key can still be placed in the same node after the shift.
- var other: BNode<K, V>;
- if (
- i > 0 &&
- (other = c[i - 1]).keys.length < max &&
- cmp(child.keys[0], key) < 0
- ) {
- if (other.isShared) c[i - 1] = other = other.clone();
- other.takeFromRight(child);
- this.keys[i - 1] = other.maxKey();
- } else if (
- (other = c[i + 1]) !== undefined &&
- other.keys.length < max &&
- cmp(child.maxKey(), key) < 0
- ) {
- if (other.isShared) c[i + 1] = other = other.clone();
- other.takeFromLeft(child);
- this.keys[i] = c[i].maxKey();
- }
- }
-
- var result = child.set(key, value, overwrite, tree);
- if (result === false) return false;
- this.keys[i] = child.maxKey();
- if (result === true) return true;
-
- // The child has split and `result` is a new right child... does it fit?
- if (this.keys.length < max) {
- // yes
- this.insert(i + 1, result);
- return true;
- } else {
- // no, we must split also
- var newRightSibling = this.splitOffRightSide(),
- target: BNodeInternal<K, V> = this;
- if (cmp(result.maxKey(), this.maxKey()) > 0) {
- target = newRightSibling;
- i -= this.keys.length;
- }
- target.insert(i + 1, result);
- return newRightSibling;
- }
- }
-
- insert(i: index, child: BNode<K, V>) {
- this.children.splice(i, 0, child);
- this.keys.splice(i, 0, child.maxKey());
- }
-
- splitOffRightSide() {
- var half = this.children.length >> 1;
- return new BNodeInternal<K, V>(
- this.children.splice(half),
- this.keys.splice(half),
- );
- }
-
- takeFromRight(rhs: BNode<K, V>) {
- // Reminder: parent node must update its copy of key for this node
- // assert: neither node is shared
- // assert rhs.keys.length > (maxNodeSize/2 && this.keys.length<maxNodeSize)
- this.keys.push(rhs.keys.shift()!);
- this.children.push((rhs as BNodeInternal<K, V>).children.shift()!);
- }
-
- takeFromLeft(lhs: BNode<K, V>) {
- // Reminder: parent node must update its copy of key for this node
- // assert: neither node is shared
- // assert rhs.keys.length > (maxNodeSize/2 && this.keys.length<maxNodeSize)
- this.keys.unshift(lhs.keys.pop()!);
- this.children.unshift((lhs as BNodeInternal<K, V>).children.pop()!);
- }
-
- /////////////////////////////////////////////////////////////////////////////
- // Internal Node: scanning & deletions //////////////////////////////////////
-
- // Note: `count` is the next value of the third argument to `onFound`.
- // A leaf node's `forRange` function returns a new value for this counter,
- // unless the operation is to stop early.
- forRange<R>(
- low: K,
- high: K,
- includeHigh: boolean | undefined,
- editMode: boolean,
- tree: BTree<K, V>,
- count: number,
- onFound?: (k: K, v: V, counter: number) => EditRangeResult<V, R> | void,
- ): EditRangeResult<V, R> | number {
- var cmp = tree._compare;
- var keys = this.keys,
- children = this.children;
- var iLow = this.indexOf(low, 0, cmp),
- i = iLow;
- var iHigh = Math.min(
- high === low ? iLow : this.indexOf(high, 0, cmp),
- keys.length - 1,
- );
- if (!editMode) {
- // Simple case
- for (; i <= iHigh; i++) {
- var result = children[i].forRange(
- low,
- high,
- includeHigh,
- editMode,
- tree,
- count,
- onFound,
- );
- if (typeof result !== "number") return result;
- count = result;
- }
- } else if (i <= iHigh) {
- try {
- for (; i <= iHigh; i++) {
- if (children[i].isShared) children[i] = children[i].clone();
- var result = children[i].forRange(
- low,
- high,
- includeHigh,
- editMode,
- tree,
- count,
- onFound,
- );
- // Note: if children[i] is empty then keys[i]=undefined.
- // This is an invalid state, but it is fixed below.
- keys[i] = children[i].maxKey();
- if (typeof result !== "number") return result;
- count = result;
- }
- } finally {
- // Deletions may have occurred, so look for opportunities to merge nodes.
- var half = tree._maxNodeSize >> 1;
- if (iLow > 0) iLow--;
- for (i = iHigh; i >= iLow; i--) {
- if (children[i].keys.length <= half) {
- if (children[i].keys.length !== 0) {
- this.tryMerge(i, tree._maxNodeSize);
- } else {
- // child is empty! delete it!
- keys.splice(i, 1);
- children.splice(i, 1);
- }
- }
- }
- if (children.length !== 0 && children[0].keys.length === 0)
- check(false, "emptiness bug");
- }
- }
- return count;
- }
-
- /** Merges child i with child i+1 if their combined size is not too large */
- tryMerge(i: index, maxSize: number): boolean {
- var children = this.children;
- if (i >= 0 && i + 1 < children.length) {
- if (children[i].keys.length + children[i + 1].keys.length <= maxSize) {
- if (children[i].isShared)
- // cloned already UNLESS i is outside scan range
- children[i] = children[i].clone();
- children[i].mergeSibling(children[i + 1], maxSize);
- children.splice(i + 1, 1);
- this.keys.splice(i + 1, 1);
- this.keys[i] = children[i].maxKey();
- return true;
- }
- }
- return false;
- }
-
- mergeSibling(rhs: BNode<K, V>, maxNodeSize: number) {
- // assert !this.isShared;
- var oldLength = this.keys.length;
- this.keys.push.apply(this.keys, rhs.keys);
- this.children.push.apply(
- this.children,
- (rhs as any as BNodeInternal<K, V>).children,
- );
- // If our children are themselves almost empty due to a mass-delete,
- // they may need to be merged too (but only the oldLength-1 and its
- // right sibling should need this).
- this.tryMerge(oldLength - 1, maxNodeSize);
- }
-}
-
-/**
- * A walkable pointer into a BTree for computing efficient diffs between trees with shared data.
- * - A cursor points to either a key/value pair (KVP) or a node (which can be either a leaf or an internal node).
- * As a consequence, a cursor cannot be created for an empty tree.
- * - A cursor can be walked forwards using `step`. A cursor can be compared to another cursor to
- * determine which is ahead in advancement.
- * - A cursor is valid only for the tree it was created from, and only until the first edit made to
- * that tree since the cursor's creation.
- * - A cursor contains a key for the current location, which is the maxKey when the cursor points to a node
- * and a key corresponding to a value when pointing to a leaf.
- * - Leaf is only populated if the cursor points to a KVP. If this is the case, levelIndices.length === internalSpine.length + 1
- * and levelIndices[levelIndices.length - 1] is the index of the value.
- */
-type DiffCursor<K, V> = {
- height: number;
- internalSpine: BNode<K, V>[][];
- levelIndices: number[];
- leaf: BNode<K, V> | undefined;
- currentKey: K;
-};
-
-// Optimization: this array of `undefined`s is used instead of a normal
-// array of values in nodes where `undefined` is the only value.
-// Its length is extended to max node size on first use; since it can
-// be shared between trees with different maximums, its length can only
-// increase, never decrease. Its type should be undefined[] but strangely
-// TypeScript won't allow the comparison V[] === undefined[]. To prevent
-// users from making this array too large, BTree has a maximum node size.
-//
-// FAQ: undefVals[i] is already undefined, so why increase the array size?
-// Reading outside the bounds of an array is relatively slow because it
-// has the side effect of scanning the prototype chain.
-var undefVals: any[] = [];
-
-const Delete = { delete: true },
- DeleteRange = () => Delete;
-const Break = { break: true };
-const EmptyLeaf = (function () {
- var n = new BNode<any, any>();
- n.isShared = true;
- return n;
-})();
-const EmptyArray: any[] = [];
-const ReusedArray: any[] = []; // assumed thread-local
-
-function check(fact: boolean, ...args: any[]) {
- if (!fact) {
- args.unshift("B+ tree"); // at beginning of message
- throw new Error(args.join(" "));
- }
-}
-
-/** A BTree frozen in the empty state. */
-export const EmptyBTree = (() => {
- let t = new BTree();
- t.freeze();
- return t;
-})();
diff --git a/packages/idb-bridge/src/tree/interfaces.ts b/packages/idb-bridge/src/tree/interfaces.ts
@@ -1,377 +0,0 @@
-// B+ tree by David Piepgrass. License: MIT
-
-/** Read-only set interface (subinterface of IMapSource<K,any>).
- * The word "set" usually means that each item in the collection is unique
- * (appears only once, based on a definition of equality used by the
- * collection.) Objects conforming to this interface aren't guaranteed not
- * to contain duplicates, but as an example, BTree<K,V> implements this
- * interface and does not allow duplicates. */
-export interface ISetSource<K = any> {
- /** Returns the number of key/value pairs in the map object. */
- size: number;
- /** Returns a boolean asserting whether the key exists in the map object or not. */
- has(key: K): boolean;
- /** Returns a new iterator for iterating the items in the set (the order is implementation-dependent). */
- keys(): IterableIterator<K>;
-}
-
-/** Read-only map interface (i.e. a source of key-value pairs). */
-export interface IMapSource<K = any, V = any> extends ISetSource<K> {
- /** Returns the number of key/value pairs in the map object. */
- size: number;
- /** Returns the value associated to the key, or undefined if there is none. */
- get(key: K): V | undefined;
- /** Returns a boolean asserting whether the key exists in the map object or not. */
- has(key: K): boolean;
- /** Calls callbackFn once for each key-value pair present in the map object.
- * The ES6 Map class sends the value to the callback before the key, so
- * this interface must do likewise. */
- forEach(
- callbackFn: (v: V, k: K, map: IMapSource<K, V>) => void,
- thisArg?: any,
- ): void;
-
- /** Returns an iterator that provides all key-value pairs from the collection (as arrays of length 2). */
- entries(): IterableIterator<[K, V]>;
- /** Returns a new iterator for iterating the keys of each pair. */
- keys(): IterableIterator<K>;
- /** Returns a new iterator for iterating the values of each pair. */
- values(): IterableIterator<V>;
- // TypeScript compiler decided Symbol.iterator has type 'any'
- //[Symbol.iterator](): IterableIterator<[K,V]>;
-}
-
-/** Write-only set interface (the set cannot be queried, but items can be added to it.)
- * @description Note: BTree<K,V> does not officially implement this interface,
- * but BTree<K> can be used as an instance of ISetSink<K>. */
-export interface ISetSink<K = any> {
- /** Adds the specified item to the set, if it was not in the set already. */
- add(key: K): any;
- /** Returns true if an element in the map object existed and has been
- * removed, or false if the element did not exist. */
- delete(key: K): boolean;
- /** Removes everything so that the set is empty. */
- clear(): void;
-}
-
-/** Write-only map interface (i.e. a drain into which key-value pairs can be "sunk") */
-export interface IMapSink<K = any, V = any> {
- /** Returns true if an element in the map object existed and has been
- * removed, or false if the element did not exist. */
- delete(key: K): boolean;
- /** Sets the value for the key in the map object (the return value is
- * boolean in BTree but Map returns the Map itself.) */
- set(key: K, value: V): any;
- /** Removes all key/value pairs from the IMap object. */
- clear(): void;
-}
-
-/** Set interface.
- * @description Note: BTree<K,V> does not officially implement this interface,
- * but BTree<K> can be used as an instance of ISet<K>. */
-export interface ISet<K = any> extends ISetSource<K>, ISetSink<K> {}
-
-/** An interface compatible with ES6 Map and BTree. This interface does not
- * describe the complete interface of either class, but merely the common
- * interface shared by both. */
-export interface IMap<K = any, V = any>
- extends IMapSource<K, V>, IMapSink<K, V> {}
-
-/** An data source that provides read-only access to a set of items called
- * "keys" in sorted order. This is a subinterface of ISortedMapSource. */
-export interface ISortedSetSource<K = any> extends ISetSource<K> {
- /** Gets the lowest key in the collection. */
- minKey(): K | undefined;
- /** Gets the highest key in the collection. */
- maxKey(): K | undefined;
- /** Returns the next key larger than the specified key (or undefined if there is none) */
- nextHigherKey(key: K): K | undefined;
- /** Returns the next key smaller than the specified key (or undefined if there is none) */
- nextLowerKey(key: K): K | undefined;
- /** Calls `callback` on the specified range of keys, in ascending order by key.
- * @param low The first key scanned will be greater than or equal to `low`.
- * @param high Scanning stops when a key larger than this is reached.
- * @param includeHigh If the `high` key is present in the map, `onFound` is called
- * for that final pair if and only if this parameter is true.
- * @param onFound A function that is called for each key pair. Because this
- * is a subinterface of ISortedMapSource, if there is a value
- * associated with the key, it is passed as the second parameter.
- * @param initialCounter Initial third argument of `onFound`. This value
- * increases by one each time `onFound` is called. Default: 0
- * @returns Number of pairs found and the number of times `onFound` was called.
- */
- forRange(
- low: K,
- high: K,
- includeHigh: boolean,
- onFound?: (k: K, v: any, counter: number) => void,
- initialCounter?: number,
- ): number;
- /** Returns a new iterator for iterating the keys of each pair in ascending order.
- * @param firstKey: Minimum key to include in the output. */
- keys(firstKey?: K): IterableIterator<K>;
-}
-
-/** An data source that provides read-only access to items in sorted order. */
-export interface ISortedMapSource<K = any, V = any>
- extends IMapSource<K, V>, ISortedSetSource<K> {
- /** Returns the next pair whose key is larger than the specified key (or undefined if there is none) */
- nextHigherPair(key: K): [K, V] | undefined;
- /** Returns the next pair whose key is smaller than the specified key (or undefined if there is none) */
- nextLowerPair(key: K): [K, V] | undefined;
- /** Builds an array of pairs from the specified range of keys, sorted by key.
- * Each returned pair is also an array: pair[0] is the key, pair[1] is the value.
- * @param low The first key in the array will be greater than or equal to `low`.
- * @param high This method returns when a key larger than this is reached.
- * @param includeHigh If the `high` key is present in the map, its pair will be
- * included in the output if and only if this parameter is true. Note:
- * if the `low` key is present, it is always included in the output.
- * @param maxLength Maximum length of the returned array (default: unlimited)
- * @description Computational complexity: O(result.length + log size)
- */
- getRange(
- low: K,
- high: K,
- includeHigh?: boolean,
- maxLength?: number,
- ): [K, V][];
- /** Calls `callback` on the specified range of keys, in ascending order by key.
- * @param low The first key scanned will be greater than or equal to `low`.
- * @param high Scanning stops when a key larger than this is reached.
- * @param includeHigh If the `high` key is present in the map, `onFound` is called
- * for that final pair if and only if this parameter is true.
- * @param onFound A function that is called for each key-value pair.
- * @param initialCounter Initial third argument of onFound. This value
- * increases by one each time `onFound` is called. Default: 0
- * @returns Number of pairs found and the number of times `callback` was called.
- */
- forRange(
- low: K,
- high: K,
- includeHigh: boolean,
- onFound?: (k: K, v: V, counter: number) => void,
- initialCounter?: number,
- ): number;
- /** Returns an iterator that provides items in order by key.
- * @param firstKey: Minimum key to include in the output. */
- entries(firstKey?: K): IterableIterator<[K, V]>;
- /** Returns a new iterator for iterating the keys of each pair in ascending order.
- * @param firstKey: Minimum key to include in the output. */
- keys(firstKey?: K): IterableIterator<K>;
- /** Returns a new iterator for iterating the values of each pair in order by key.
- * @param firstKey: Minimum key whose associated value is included in the output. */
- values(firstKey?: K): IterableIterator<V>;
-
- // This method should logically be in IMapSource but is not supported by ES6 Map
- /** Performs a reduce operation like the `reduce` method of `Array`.
- * It is used to combine all pairs into a single value, or perform conversions. */
- reduce<R>(
- callback: (
- previous: R,
- currentPair: [K, V],
- counter: number,
- tree: IMapF<K, V>,
- ) => R,
- initialValue: R,
- ): R;
- /** Performs a reduce operation like the `reduce` method of `Array`.
- * It is used to combine all pairs into a single value, or perform conversions. */
- reduce<R>(
- callback: (
- previous: R | undefined,
- currentPair: [K, V],
- counter: number,
- tree: IMapF<K, V>,
- ) => R,
- ): R | undefined;
-}
-
-/** An interface for a set of keys (the combination of ISortedSetSource<K> and ISetSink<K>) */
-export interface ISortedSet<K = any> extends ISortedSetSource<K>, ISetSink<K> {}
-
-/** An interface for a sorted map (dictionary),
- * not including functional/persistent methods. */
-export interface ISortedMap<K = any, V = any>
- extends IMap<K, V>, ISortedMapSource<K, V> {
- // All of the following methods should be in IMap but are left out of IMap
- // so that IMap is compatible with ES6 Map.
-
- /** Adds or overwrites a key-value pair in the sorted map.
- * @param key the key is used to determine the sort order of data in the tree.
- * @param value data to associate with the key
- * @param overwrite Whether to overwrite an existing key-value pair
- * (default: true). If this is false and there is an existing
- * key-value pair then the call to this method has no effect.
- * @returns true if a new key-value pair was added, false if the key
- * already existed. */
- set(key: K, value: V, overwrite?: boolean): boolean;
- /** Adds all pairs from a list of key-value pairs.
- * @param pairs Pairs to add to this tree. If there are duplicate keys,
- * later pairs currently overwrite earlier ones (e.g. [[0,1],[0,7]]
- * associates 0 with 7.)
- * @param overwrite Whether to overwrite pairs that already exist (if false,
- * pairs[i] is ignored when the key pairs[i][0] already exists.)
- * @returns The number of pairs added to the collection.
- */
- setPairs(pairs: [K, V][], overwrite?: boolean): number;
- /** Deletes a series of keys from the collection. */
- deleteKeys(keys: K[]): number;
- /** Removes a range of key-value pairs from the B+ tree.
- * @param low The first key deleted will be greater than or equal to `low`.
- * @param high Deleting stops when a key larger than this is reached.
- * @param includeHigh Specifies whether the `high` key, if present, is deleted.
- * @returns The number of key-value pairs that were deleted. */
- deleteRange(low: K, high: K, includeHigh: boolean): number;
-
- // TypeScript requires these methods of ISortedMapSource to be repeated
- entries(firstKey?: K): IterableIterator<[K, V]>;
- keys(firstKey?: K): IterableIterator<K>;
- values(firstKey?: K): IterableIterator<V>;
-}
-
-/** An interface for a functional set, in which the set object could be read-only
- * but new versions of the set can be created by calling "with" or "without"
- * methods to add or remove keys. This is a subinterface of IMapF<K,V>,
- * so the items in the set may be referred to as "keys". */
-export interface ISetF<K = any> extends ISetSource<K> {
- /** Returns a copy of the set with the specified key included.
- * @description You might wonder why this method accepts only one key
- * instead of `...keys: K[]`. The reason is that the derived interface
- * IMapF expects the second parameter to be a value. Therefore
- * withKeys() is provided to set multiple keys at once. */
- with(key: K): ISetF<K>;
- /** Returns a copy of the set with the specified key removed. */
- without(key: K): ISetF<K>;
- /** Returns a copy of the tree with all the keys in the specified array present.
- * @param keys The keys to add.
- * @param returnThisIfUnchanged If true, the method returns `this` when
- * all of the keys are already present in the collection. The
- * default value may be true or false depending on the concrete
- * implementation of the interface (in BTree, the default is false.) */
- withKeys(keys: K[], returnThisIfUnchanged?: boolean): ISetF<K>;
- /** Returns a copy of the tree with all the keys in the specified array removed. */
- withoutKeys(keys: K[], returnThisIfUnchanged?: boolean): ISetF<K>;
- /** Returns a copy of the tree with items removed whenever the callback
- * function returns false.
- * @param callback A function to call for each item in the set.
- * The second parameter to `callback` exists because ISetF
- * is a subinterface of IMapF. If the object is a map, v
- * is the value associated with the key, otherwise v could be
- * undefined or another copy of the third parameter (counter). */
- filter(
- callback: (k: K, v: any, counter: number) => boolean,
- returnThisIfUnchanged?: boolean,
- ): ISetF<K>;
-}
-
-/** An interface for a functional map, in which the map object could be read-only
- * but new versions of the map can be created by calling "with" or "without"
- * methods to add or remove keys or key-value pairs.
- */
-export interface IMapF<K = any, V = any> extends IMapSource<K, V>, ISetF<K> {
- /** Returns a copy of the tree with the specified key set (the value is undefined). */
- with(key: K): IMapF<K, V | undefined>;
- /** Returns a copy of the tree with the specified key-value pair set. */
- with<V2>(key: K, value: V2, overwrite?: boolean): IMapF<K, V | V2>;
- /** Returns a copy of the tree with the specified key-value pairs set. */
- withPairs<V2>(pairs: [K, V | V2][], overwrite: boolean): IMapF<K, V | V2>;
- /** Returns a copy of the tree with all the keys in the specified array present.
- * @param keys The keys to add. If a key is already present in the tree,
- * neither the existing key nor the existing value is modified.
- * @param returnThisIfUnchanged If true, the method returns `this` when
- * all of the keys are already present in the collection. The
- * default value may be true or false depending on the concrete
- * implementation of the interface (in BTree, the default is false.) */
- withKeys(keys: K[], returnThisIfUnchanged?: boolean): IMapF<K, V | undefined>;
- /** Returns a copy of the tree with all values altered by a callback function. */
- mapValues<R>(callback: (v: V, k: K, counter: number) => R): IMapF<K, R>;
- /** Performs a reduce operation like the `reduce` method of `Array`.
- * It is used to combine all pairs into a single value, or perform conversions. */
- reduce<R>(
- callback: (
- previous: R,
- currentPair: [K, V],
- counter: number,
- tree: IMapF<K, V>,
- ) => R,
- initialValue: R,
- ): R;
- /** Performs a reduce operation like the `reduce` method of `Array`.
- * It is used to combine all pairs into a single value, or perform conversions. */
- reduce<R>(
- callback: (
- previous: R | undefined,
- currentPair: [K, V],
- counter: number,
- tree: IMapF<K, V>,
- ) => R,
- ): R | undefined;
-
- // Update return types in ISetF
- without(key: K): IMapF<K, V>;
- withoutKeys(keys: K[], returnThisIfUnchanged?: boolean): IMapF<K, V>;
- /** Returns a copy of the tree with pairs removed whenever the callback
- * function returns false. */
- filter(
- callback: (k: K, v: V, counter: number) => boolean,
- returnThisIfUnchanged?: boolean,
- ): IMapF<K, V>;
-}
-
-/** An interface for a functional sorted set: a functional set in which the
- * keys (items) are sorted. This is a subinterface of ISortedMapF. */
-export interface ISortedSetF<K = any> extends ISetF<K>, ISortedSetSource<K> {
- // TypeScript requires this method of ISortedSetSource to be repeated
- keys(firstKey?: K): IterableIterator<K>;
- without(key: K): ISortedSetF<K>;
- with(key: K): ISortedSetF<K>;
-}
-
-export interface ISortedMapF<K = any, V = any>
- extends ISortedSetF<K>, IMapF<K, V>, ISortedMapSource<K, V> {
- /** Returns a copy of the tree with the specified range of keys removed. */
- withoutRange(
- low: K,
- high: K,
- includeHigh: boolean,
- returnThisIfUnchanged?: boolean,
- ): ISortedMapF<K, V>;
-
- // TypeScript requires these methods of ISortedSetF and ISortedMapSource to be repeated
- entries(firstKey?: K): IterableIterator<[K, V]>;
- keys(firstKey?: K): IterableIterator<K>;
- values(firstKey?: K): IterableIterator<V>;
- forRange(
- low: K,
- high: K,
- includeHigh: boolean,
- onFound?: (k: K, v: V, counter: number) => void,
- initialCounter?: number,
- ): number;
-
- // Update the return value of methods from base interfaces
- with(key: K): ISortedMapF<K, V | undefined>;
- with<V2>(key: K, value: V2, overwrite?: boolean): ISortedMapF<K, V | V2>;
- withKeys(
- keys: K[],
- returnThisIfUnchanged?: boolean,
- ): ISortedMapF<K, V | undefined>;
- withPairs<V2>(
- pairs: [K, V | V2][],
- overwrite: boolean,
- ): ISortedMapF<K, V | V2>;
- mapValues<R>(callback: (v: V, k: K, counter: number) => R): ISortedMapF<K, R>;
- without(key: K): ISortedMapF<K, V>;
- withoutKeys(keys: K[], returnThisIfUnchanged?: boolean): ISortedMapF<K, V>;
- filter(
- callback: (k: K, v: any, counter: number) => boolean,
- returnThisIfUnchanged?: boolean,
- ): ISortedMapF<K, V>;
-}
-
-export interface ISortedMapConstructor<K, V> {
- new (entries?: [K, V][], compare?: (a: K, b: K) => number): ISortedMap<K, V>;
-}
-export interface ISortedMapFConstructor<K, V> {
- new (entries?: [K, V][], compare?: (a: K, b: K) => number): ISortedMapF<K, V>;
-}
diff --git a/packages/taler-wallet-core/src/host-impl.node.ts b/packages/taler-wallet-core/src/host-impl.node.ts
@@ -25,7 +25,6 @@
// eslint-disable-next-line no-duplicate-imports
import {
BridgeIDBFactory,
- MemoryBackend,
createSqliteBackend,
shimIndexedDB,
} from "@gnu-taler/idb-bridge";
@@ -36,82 +35,16 @@ import {
WalletRunConfig,
} from "@gnu-taler/taler-util";
import { createPlatformHttpLib } from "@gnu-taler/taler-util/http";
-import * as fs from "node:fs";
import { NodeThreadCryptoWorkerFactory } from "./crypto/workers/nodeThreadWorker.js";
import { SynchronousCryptoWorkerFactoryPlain } from "./crypto/workers/synchronousWorkerFactoryPlain.js";
import {
DefaultNodeWalletArgs,
getSqlite3FilenameFromStoragePath,
- makeTempfileId,
} from "./host-common.js";
import { Wallet, WalletDatabaseImplementation } from "./wallet.js";
const logger = new Logger("host-impl.node.ts");
-async function makeFileDb(
- args: DefaultNodeWalletArgs = {},
-): Promise<WalletDatabaseImplementation> {
- const myBackend = new MemoryBackend();
- if (process.env.TALER_WALLET_DBTRACING) {
- myBackend.enableTracing = true;
- } else {
- myBackend.enableTracing = false;
- }
- const storagePath = args.persistentStoragePath;
- if (storagePath) {
- try {
- const dbContentStr: string = fs.readFileSync(storagePath, {
- encoding: "utf-8",
- });
- const dbContent = JSON.parse(dbContentStr);
- myBackend.importDump(dbContent);
- } catch (e: any) {
- const code: string = e.code;
- if (code === "ENOENT") {
- logger.trace("wallet file doesn't exist yet");
- } else {
- logger.error("could not open wallet database file");
- throw Error(
- "could not open wallet database file",
- // @ts-expect-error no support for options.cause yet
- { cause: e },
- );
- }
- }
-
- myBackend.afterCommitCallback = async () => {
- logger.trace("committing database");
- // Allow caller to stop persisting the wallet.
- if (args.persistentStoragePath === undefined) {
- return;
- }
- const tmpPath = `${args.persistentStoragePath}-${makeTempfileId(5)}.tmp`;
- logger.trace("exported DB dump");
- const dbContent = myBackend.exportDump();
- fs.writeFileSync(tmpPath, JSON.stringify(dbContent, undefined, 2), {
- encoding: "utf-8",
- });
- // Atomically move the temporary file onto the DB path.
- fs.renameSync(tmpPath, args.persistentStoragePath);
- logger.trace("committing database done");
- };
- }
-
- BridgeIDBFactory.enableTracing = false;
-
- const myBridgeIdbFactory = new BridgeIDBFactory(myBackend);
- return {
- idbFactory: myBridgeIdbFactory,
- getStats: () => myBackend.accessStats,
- exportToFile(directory, stem) {
- throw Error("not supported");
- },
- async readBackupJson(path: string): Promise<any> {
- throw Error("not supported");
- },
- };
-}
-
async function makeSqliteDb(
args: DefaultNodeWalletArgs,
): Promise<WalletDatabaseImplementation> {
@@ -184,8 +117,7 @@ export async function createNativeWalletHost2(
args.persistentStoragePath &&
args.persistentStoragePath.endsWith(".json")
) {
- logger.info("using JSON file DB backend (slow, only use for testing)");
- dbResp = await makeFileDb(args);
+ throw Error("memory backend not supported");
} else {
logger.info(`using sqlite3 DB backend`);
dbResp = await makeSqliteDb(args);
diff --git a/packages/taler-wallet-core/src/host-impl.qtart.ts b/packages/taler-wallet-core/src/host-impl.qtart.ts
@@ -31,7 +31,6 @@ import type {
import {
BridgeIDBFactory,
createSqliteBackend,
- MemoryBackend,
shimIndexedDB,
} from "@gnu-taler/idb-bridge";
import {
@@ -41,12 +40,11 @@ import {
WalletRunConfig,
} from "@gnu-taler/taler-util";
import { createPlatformHttpLib } from "@gnu-taler/taler-util/http";
-import { qjsOs, qjsStd } from "@gnu-taler/taler-util/qtart";
+import { qjsStd } from "@gnu-taler/taler-util/qtart";
import { SynchronousCryptoWorkerFactoryPlain } from "./crypto/workers/synchronousWorkerFactoryPlain.js";
import {
DefaultNodeWalletArgs,
getSqlite3FilenameFromStoragePath,
- makeTempfileId,
} from "./host-common.js";
import { exportDb } from "./index.js";
import { Wallet, WalletDatabaseImplementation } from "./wallet.js";
@@ -159,53 +157,6 @@ async function makeSqliteDb(
};
}
-async function makeFileDb(
- args: DefaultNodeWalletArgs = {},
-): Promise<WalletDatabaseImplementation> {
- BridgeIDBFactory.enableTracing = false;
- const myBackend = new MemoryBackend();
- myBackend.enableTracing = false;
-
- const storagePath = args.persistentStoragePath;
- if (storagePath) {
- const dbContentStr = qjsStd.loadFile(storagePath);
- if (dbContentStr != null) {
- const dbContent = JSON.parse(dbContentStr);
- myBackend.importDump(dbContent);
- }
-
- myBackend.afterCommitCallback = async () => {
- logger.trace("committing database");
- // Allow caller to stop persisting the wallet.
- if (args.persistentStoragePath === undefined) {
- return;
- }
- const tmpPath = `${args.persistentStoragePath}-${makeTempfileId(5)}.tmp`;
- const dbContent = myBackend.exportDump();
- logger.trace("exported DB dump");
- qjsStd.writeFile(tmpPath, JSON.stringify(dbContent, undefined, 2));
- // Atomically move the temporary file onto the DB path.
- const res = qjsOs.rename(tmpPath, args.persistentStoragePath);
- if (res != 0) {
- throw Error("db commit failed at rename");
- }
- logger.trace("committing database done");
- };
- }
-
- const myBridgeIdbFactory = new BridgeIDBFactory(myBackend);
- return {
- idbFactory: myBridgeIdbFactory,
- getStats: () => myBackend.accessStats,
- exportToFile(directory, stem) {
- throw Error("not supported");
- },
- async readBackupJson(path: string): Promise<any> {
- throw Error("not supported");
- },
- };
-}
-
export async function createNativeWalletHost2(
args: DefaultNodeWalletArgs = {},
): Promise<{
@@ -219,8 +170,7 @@ export async function createNativeWalletHost2(
args.persistentStoragePath &&
args.persistentStoragePath.endsWith(".json")
) {
- logger.info("using JSON file DB backend (slow, only use for testing)");
- dbResp = await makeFileDb(args);
+ throw Error("json DB backend not supported anymore");
} else {
// logger.info("using sqlite3 DB backend");
dbResp = await makeSqliteDb(args);
