[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[taler-wallet-core] 01/02: idb-bridge: faster indices, various correctne
|
From: |
gnunet |
|
Subject: |
[taler-wallet-core] 01/02: idb-bridge: faster indices, various correctness fixes and tests |
|
Date: |
Wed, 15 Dec 2021 02:58:40 +0100 |
This is an automated email from the git hooks/post-receive script.
dold pushed a commit to branch master
in repository wallet-core.
commit e84a1789af2a0292128807b86649a45c4da0a51c
Author: Florian Dold <florian@dold.me>
AuthorDate: Wed Dec 15 02:37:03 2021 +0100
idb-bridge: faster indices, various correctness fixes and tests
---
packages/idb-bridge/package.json | 2 -
packages/idb-bridge/src/MemoryBackend.test.ts | 188 +++++
packages/idb-bridge/src/MemoryBackend.ts | 713 +++++++++---------
packages/idb-bridge/src/backend-interface.ts | 2 +-
packages/idb-bridge/src/bridge-idb.ts | 2 -
.../idb-wpt-ported/idbcursor-update-index.test.ts | 2 -
packages/idb-bridge/src/index.ts | 2 -
packages/idb-bridge/src/tree/b+tree.ts | 822 ++++++++++++++++++---
packages/idb-bridge/src/tree/interfaces.ts | 28 +-
.../idb-bridge/src/util/structuredClone.test.ts | 9 +-
packages/idb-bridge/src/util/structuredClone.ts | 98 ++-
pnpm-lock.yaml | 35 +-
12 files changed, 1414 insertions(+), 489 deletions(-)
diff --git a/packages/idb-bridge/package.json b/packages/idb-bridge/package.json
index f3ed0888..52bc872d 100644
--- a/packages/idb-bridge/package.json
+++ b/packages/idb-bridge/package.json
@@ -19,7 +19,6 @@
"@rollup/plugin-commonjs": "^17.1.0",
"@rollup/plugin-json": "^4.1.0",
"@rollup/plugin-node-resolve": "^11.2.0",
- "@types/lodash": "^4.14.178",
"@types/node": "^14.14.22",
"ava": "^3.15.0",
"esm": "^3.2.25",
@@ -29,7 +28,6 @@
"typescript": "^4.1.3"
},
"dependencies": {
- "lodash": "^4.17.21",
"tslib": "^2.1.0"
},
"ava": {
diff --git a/packages/idb-bridge/src/MemoryBackend.test.ts
b/packages/idb-bridge/src/MemoryBackend.test.ts
index 292f1b49..ac1a9d90 100644
--- a/packages/idb-bridge/src/MemoryBackend.test.ts
+++ b/packages/idb-bridge/src/MemoryBackend.test.ts
@@ -23,6 +23,12 @@ import {
BridgeIDBRequest,
BridgeIDBTransaction,
} from "./bridge-idb";
+import {
+ IDBCursorDirection,
+ IDBCursorWithValue,
+ IDBKeyRange,
+ IDBValidKey,
+} from "./idbtypes.js";
import { MemoryBackend } from "./MemoryBackend";
function promiseFromRequest(request: BridgeIDBRequest): Promise<any> {
@@ -104,6 +110,7 @@ test("Spec: Example 1 Part 2", async (t) => {
test("Spec: Example 1 Part 3", async (t) => {
const backend = new MemoryBackend();
+ backend.enableTracing = true;
const idb = new BridgeIDBFactory(backend);
const request = idb.open("library");
@@ -348,3 +355,184 @@ test("export", async (t) => {
t.is(exportedData2.databases["library"].schema.databaseVersion, 42);
t.pass();
});
+
+test("range queries", async (t) => {
+ const backend = new MemoryBackend();
+ backend.enableTracing = true;
+ const idb = new BridgeIDBFactory(backend);
+
+ const request = idb.open("mydb");
+ request.onupgradeneeded = () => {
+ const db = request.result;
+ const store = db.createObjectStore("bla", { keyPath: "x" });
+ store.createIndex("by_y", "y");
+ store.createIndex("by_z", "z");
+ };
+
+ const db: BridgeIDBDatabase = await promiseFromRequest(request);
+
+ t.is(db.name, "mydb");
+
+ const tx = db.transaction("bla", "readwrite");
+
+ const store = tx.objectStore("bla");
+
+ store.put({ x: 0, y: "a" });
+ store.put({ x: 2, y: "a" });
+ store.put({ x: 4, y: "b" });
+ store.put({ x: 8, y: "b" });
+ store.put({ x: 10, y: "c" });
+ store.put({ x: 12, y: "c" });
+
+ await promiseFromTransaction(tx);
+
+ async function doCursorStoreQuery(
+ range: IDBKeyRange | IDBValidKey | undefined,
+ direction: IDBCursorDirection | undefined,
+ expected: any[],
+ ): Promise<void> {
+ const tx = db.transaction("bla", "readwrite");
+ const store = tx.objectStore("bla");
+ const vals: any[] = [];
+
+ const req = store.openCursor(range, direction);
+ while (1) {
+ await promiseFromRequest(req);
+ const cursor: IDBCursorWithValue = req.result;
+ if (!cursor) {
+ break;
+ }
+ cursor.continue();
+ vals.push(cursor.value);
+ }
+
+ await promiseFromTransaction(tx);
+
+ t.deepEqual(vals, expected);
+ }
+
+ async function doCursorIndexQuery(
+ range: IDBKeyRange | IDBValidKey | undefined,
+ direction: IDBCursorDirection | undefined,
+ expected: any[],
+ ): Promise<void> {
+ const tx = db.transaction("bla", "readwrite");
+ const store = tx.objectStore("bla");
+ const index = store.index("by_y");
+ const vals: any[] = [];
+
+ const req = index.openCursor(range, direction);
+ while (1) {
+ await promiseFromRequest(req);
+ const cursor: IDBCursorWithValue = req.result;
+ if (!cursor) {
+ break;
+ }
+ cursor.continue();
+ vals.push(cursor.value);
+ }
+
+ await promiseFromTransaction(tx);
+
+ t.deepEqual(vals, expected);
+ }
+
+ await doCursorStoreQuery(undefined, undefined, [
+ {
+ x: 0,
+ y: "a",
+ },
+ {
+ x: 2,
+ y: "a",
+ },
+ {
+ x: 4,
+ y: "b",
+ },
+ {
+ x: 8,
+ y: "b",
+ },
+ {
+ x: 10,
+ y: "c",
+ },
+ {
+ x: 12,
+ y: "c",
+ },
+ ]);
+
+ await doCursorStoreQuery(
+ BridgeIDBKeyRange.bound(0, 12, true, true),
+ undefined,
+ [
+ {
+ x: 2,
+ y: "a",
+ },
+ {
+ x: 4,
+ y: "b",
+ },
+ {
+ x: 8,
+ y: "b",
+ },
+ {
+ x: 10,
+ y: "c",
+ },
+ ],
+ );
+
+ await doCursorIndexQuery(
+ BridgeIDBKeyRange.bound("a", "c", true, true),
+ undefined,
+ [
+ {
+ x: 4,
+ y: "b",
+ },
+ {
+ x: 8,
+ y: "b",
+ },
+ ],
+ );
+
+ await doCursorIndexQuery(undefined, "nextunique", [
+ {
+ x: 0,
+ y: "a",
+ },
+ {
+ x: 4,
+ y: "b",
+ },
+ {
+ x: 10,
+ y: "c",
+ },
+ ]);
+
+ await doCursorIndexQuery(undefined, "prevunique", [
+ {
+ x: 10,
+ y: "c",
+ },
+ {
+ x: 4,
+ y: "b",
+ },
+ {
+ x: 0,
+ y: "a",
+ },
+ ]);
+
+ db.close();
+
+ t.pass();
+});
diff --git a/packages/idb-bridge/src/MemoryBackend.ts
b/packages/idb-bridge/src/MemoryBackend.ts
index 41d0d7fb..de4bca88 100644
--- a/packages/idb-bridge/src/MemoryBackend.ts
+++ b/packages/idb-bridge/src/MemoryBackend.ts
@@ -33,7 +33,7 @@ import {
structuredRevive,
} from "./util/structuredClone";
import { ConstraintError, DataError } from "./util/errors";
-import BTree, { ISortedMapF } from "./tree/b+tree";
+import BTree, { ISortedMapF, ISortedSetF } from "./tree/b+tree";
import { compareKeys } from "./util/cmp";
import { StoreKeyResult, makeStoreKeyValue } from "./util/makeStoreKeyValue";
import { getIndexKeys } from "./util/getIndexKeys";
@@ -95,18 +95,11 @@ interface Database {
connectionCookies: string[];
}
-/** @public */
-export interface IndexDump {
- name: string;
- records: IndexRecord[];
-}
-
/** @public */
export interface ObjectStoreDump {
name: string;
keyGenerator: number;
records: ObjectStoreRecord[];
- indexes: { [name: string]: IndexDump };
}
/** @public */
@@ -140,7 +133,7 @@ interface Connection {
/** @public */
export interface IndexRecord {
indexKey: Key;
- primaryKeys: Key[];
+ primaryKeys: ISortedSetF<Key>;
}
/** @public */
@@ -185,6 +178,27 @@ function nextStoreKey<T>(
return res[1].primaryKey;
}
+function assertInvariant(cond: boolean): asserts cond {
+ if (!cond) {
+ throw Error("invariant failed");
+ }
+}
+
+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,
@@ -258,22 +272,20 @@ export class MemoryBackend implements Backend {
* Must be called before any connections to the database backend have
* been made.
*/
- importDump(data: any) {
- if (this.enableTracing) {
- console.log("importing dump (a)");
- }
+ 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");
}
- data = structuredRevive(data);
-
this.databases = {};
for (const dbName of Object.keys(data.databases)) {
@@ -285,29 +297,10 @@ export class MemoryBackend implements Backend {
for (const objectStoreName of Object.keys(
data.databases[dbName].objectStores,
)) {
- const dumpedObjectStore =
+ const storeSchema = schema.objectStores[objectStoreName];
+ const dumpedObjectStore: ObjectStoreDump =
data.databases[dbName].objectStores[objectStoreName];
- const indexes: { [name: string]: Index } = {};
- for (const indexName of Object.keys(dumpedObjectStore.indexes)) {
- const dumpedIndex = dumpedObjectStore.indexes[indexName];
- const pairs = dumpedIndex.records.map((r: any) => {
- return structuredClone([r.indexKey, r]);
- });
- const indexData: ISortedMapF<Key, IndexRecord> = new BTree(
- pairs,
- compareKeys,
- );
- const index: Index = {
- deleted: false,
- modifiedData: undefined,
- modifiedName: undefined,
- originalName: indexName,
- originalData: indexData,
- };
- indexes[indexName] = index;
- }
-
const pairs = dumpedObjectStore.records.map((r: any) => {
return structuredClone([r.primaryKey, r]);
});
@@ -323,10 +316,34 @@ export class MemoryBackend implements Backend {
originalData: objectStoreData,
originalName: objectStoreName,
originalKeyGenerator: dumpedObjectStore.keyGenerator,
- committedIndexes: indexes,
+ 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,
+ };
+ const storeData = objectStoreData;
+
+ storeData.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,
@@ -368,16 +385,6 @@ export class MemoryBackend implements Backend {
const objectStores: { [name: string]: ObjectStoreDump } = {};
for (const objectStoreName of Object.keys(db.committedObjectStores)) {
const objectStore = db.committedObjectStores[objectStoreName];
-
- const indexes: { [name: string]: IndexDump } = {};
- for (const indexName of Object.keys(objectStore.committedIndexes)) {
- const index = objectStore.committedIndexes[indexName];
- const indexRecords: IndexRecord[] = [];
- index.originalData.forEach((v: IndexRecord) => {
- indexRecords.push(structuredClone(v));
- });
- indexes[indexName] = { name: indexName, records: indexRecords };
- }
const objectStoreRecords: ObjectStoreRecord[] = [];
objectStore.originalData.forEach((v: ObjectStoreRecord) => {
objectStoreRecords.push(structuredClone(v));
@@ -386,7 +393,6 @@ export class MemoryBackend implements Backend {
name: objectStoreName,
records: objectStoreRecords,
keyGenerator: objectStore.originalKeyGenerator,
- indexes: indexes,
};
}
const dbDump: DatabaseDump = {
@@ -1047,17 +1053,17 @@ export class MemoryBackend implements Backend {
indexProperties.multiEntry,
);
for (const indexKey of indexKeys) {
- const existingRecord = indexData.get(indexKey);
- if (!existingRecord) {
+ const existingIndexRecord = indexData.get(indexKey);
+ if (!existingIndexRecord) {
throw Error("db inconsistent: expected index entry missing");
}
- const newPrimaryKeys = existingRecord.primaryKeys.filter(
- (x) => compareKeys(x, primaryKey) !== 0,
+ const newPrimaryKeys = existingIndexRecord.primaryKeys.without(
+ primaryKey,
);
- if (newPrimaryKeys.length === 0) {
+ if (newPrimaryKeys.size === 0) {
index.modifiedData = indexData.without(indexKey);
} else {
- const newIndexRecord = {
+ const newIndexRecord: IndexRecord = {
indexKey,
primaryKeys: newPrimaryKeys,
};
@@ -1117,11 +1123,6 @@ export class MemoryBackend implements Backend {
);
}
- let numResults = 0;
- let indexKeys: Key[] = [];
- let primaryKeys: Key[] = [];
- let values: Value[] = [];
-
const forward: boolean =
req.direction === "next" || req.direction === "nextunique";
const unique: boolean =
@@ -1133,280 +1134,44 @@ export class MemoryBackend implements Backend {
const haveIndex = req.indexName !== undefined;
+ let resp: RecordGetResponse;
+
if (haveIndex) {
const index =
myConn.objectStoreMap[req.objectStoreName].indexMap[req.indexName!];
const indexData = index.modifiedData || index.originalData;
- let indexPos = req.lastIndexPosition;
-
- if (indexPos === undefined) {
- // First time we iterate! So start at the beginning (lower/upper)
- // of our allowed range.
- indexPos = forward ? range.lower : range.upper;
- }
-
- let primaryPos = req.lastObjectStorePosition;
-
- // We might have to advance the index key further!
- if (req.advanceIndexKey !== undefined) {
- const compareResult = compareKeys(req.advanceIndexKey, indexPos);
- if ((forward && compareResult > 0) || (!forward && compareResult > 0))
{
- indexPos = req.advanceIndexKey;
- } else if (compareResult == 0 && req.advancePrimaryKey !== undefined) {
- // index keys are the same, so advance the primary key
- if (primaryPos === undefined) {
- primaryPos = req.advancePrimaryKey;
- } else {
- const primCompareResult = compareKeys(
- req.advancePrimaryKey,
- primaryPos,
- );
- if (
- (forward && primCompareResult > 0) ||
- (!forward && primCompareResult < 0)
- ) {
- primaryPos = req.advancePrimaryKey;
- }
- }
- }
- }
-
- if (indexPos === undefined || indexPos === null) {
- indexPos = forward ? indexData.minKey() : indexData.maxKey();
- }
-
- if (indexPos === undefined) {
- throw Error("invariant violated");
- }
-
- let indexEntry: IndexRecord | undefined;
- indexEntry = indexData.get(indexPos);
- if (!indexEntry) {
- const res = forward
- ? indexData.nextHigherPair(indexPos)
- : indexData.nextLowerPair(indexPos);
- if (res) {
- indexEntry = res[1];
- indexPos = indexEntry.indexKey;
- }
- }
-
- if (unique) {
- while (1) {
- if (req.limit != 0 && numResults == req.limit) {
- break;
- }
- if (indexPos === undefined) {
- break;
- }
- if (!range.includes(indexPos)) {
- break;
- }
- if (indexEntry === undefined) {
- break;
- }
-
- if (
- req.lastIndexPosition === null ||
- req.lastIndexPosition === undefined ||
- compareKeys(indexEntry.indexKey, req.lastIndexPosition) !== 0
- ) {
- indexKeys.push(indexEntry.indexKey);
- primaryKeys.push(indexEntry.primaryKeys[0]);
- numResults++;
- }
-
- const res: any = forward
- ? indexData.nextHigherPair(indexPos)
- : indexData.nextLowerPair(indexPos);
- if (res) {
- indexPos = res[1].indexKey;
- indexEntry = res[1] as IndexRecord;
- } else {
- break;
- }
- }
- } else {
- let primkeySubPos = 0;
-
- // Sort out the case where the index key is the same, so we have
- // to get the prev/next primary key
- if (
- indexEntry !== undefined &&
- req.lastIndexPosition !== undefined &&
- compareKeys(indexEntry.indexKey, req.lastIndexPosition) === 0
- ) {
- let pos = forward ? 0 : indexEntry.primaryKeys.length - 1;
- this.enableTracing &&
- console.log(
- "number of primary keys",
- indexEntry.primaryKeys.length,
- );
- this.enableTracing && console.log("start pos is", pos);
- // Advance past the lastObjectStorePosition
- do {
- const cmpResult = compareKeys(
- req.lastObjectStorePosition,
- indexEntry.primaryKeys[pos],
- );
- this.enableTracing && console.log("cmp result is", cmpResult);
- if ((forward && cmpResult < 0) || (!forward && cmpResult > 0)) {
- break;
- }
- pos += forward ? 1 : -1;
- this.enableTracing && console.log("now pos is", pos);
- } while (pos >= 0 && pos < indexEntry.primaryKeys.length);
-
- // Make sure we're at least at advancedPrimaryPos
- while (
- primaryPos !== undefined &&
- pos >= 0 &&
- pos < indexEntry.primaryKeys.length
- ) {
- const cmpResult = compareKeys(
- primaryPos,
- indexEntry.primaryKeys[pos],
- );
- if ((forward && cmpResult <= 0) || (!forward && cmpResult >= 0)) {
- break;
- }
- pos += forward ? 1 : -1;
- }
- primkeySubPos = pos;
- } else if (indexEntry !== undefined) {
- primkeySubPos = forward ? 0 : indexEntry.primaryKeys.length - 1;
- }
-
- if (this.enableTracing) {
- console.log("subPos=", primkeySubPos);
- console.log("indexPos=", indexPos);
- }
-
- while (1) {
- if (req.limit != 0 && numResults == req.limit) {
- break;
- }
- if (indexPos === undefined) {
- break;
- }
- if (!range.includes(indexPos)) {
- break;
- }
- if (indexEntry === undefined) {
- break;
- }
- if (
- primkeySubPos < 0 ||
- primkeySubPos >= indexEntry.primaryKeys.length
- ) {
- const res: any = forward
- ? indexData.nextHigherPair(indexPos)
- : indexData.nextLowerPair(indexPos);
- if (res) {
- indexPos = res[1].indexKey;
- indexEntry = res[1];
- primkeySubPos = forward ? 0 : indexEntry!.primaryKeys.length - 1;
- continue;
- } else {
- break;
- }
- }
- indexKeys.push(indexEntry.indexKey);
- primaryKeys.push(indexEntry.primaryKeys[primkeySubPos]);
- numResults++;
- primkeySubPos += forward ? 1 : -1;
- }
- }
-
- // Now we can collect the values based on the primary keys,
- // if requested.
- if (req.resultLevel === ResultLevel.Full) {
- for (let i = 0; i < numResults; i++) {
- const result = 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(result.value);
- }
- }
+ 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,
+ });
} else {
- // only based on object store, no index involved, phew!
- let storePos = req.lastObjectStorePosition;
- if (storePos === undefined) {
- storePos = forward ? range.lower : range.upper;
- }
-
if (req.advanceIndexKey !== undefined) {
throw Error("unsupported request");
}
-
- storePos = furthestKey(forward, req.advancePrimaryKey, storePos);
-
- if (storePos !== null && storePos !== undefined) {
- // 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 (this.enableTracing) {
- console.log("store entry:", storeEntry);
- }
- if (
- !storeEntry ||
- (req.lastObjectStorePosition !== undefined &&
- compareKeys(req.lastObjectStorePosition, storePos) === 0)
- ) {
- storePos = storeData.nextHigherKey(storePos);
- }
- } else {
- storePos = forward ? storeData.minKey() : storeData.maxKey();
- if (this.enableTracing) {
- console.log("setting starting store pos to", 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);
- }
+ resp = getObjectStoreRecords({
+ forward,
+ storeData,
+ limit: req.limit,
+ range,
+ resultLevel: req.resultLevel,
+ advancePrimaryKey: req.advancePrimaryKey,
+ lastIndexPosition: req.lastIndexPosition,
+ lastObjectStorePosition: req.lastObjectStorePosition,
+ });
}
if (this.enableTracing) {
- console.log(`TRACING: getRecords got ${numResults} results`);
+ console.log(`TRACING: getRecords got ${resp.count} results`);
}
- return {
- count: numResults,
- indexKeys:
- req.resultLevel >= ResultLevel.OnlyKeys && haveIndex
- ? indexKeys
- : undefined,
- primaryKeys:
- req.resultLevel >= ResultLevel.OnlyKeys ? primaryKeys : undefined,
- values: req.resultLevel >= ResultLevel.Full ? values : undefined,
- };
+ return resp;
}
async storeRecord(
@@ -1586,21 +1351,20 @@ export class MemoryBackend implements Backend {
if (indexProperties.unique) {
throw new ConstraintError();
} else {
- const pred = (x: Key) => compareKeys(x, primaryKey) === 0;
- if (existingRecord.primaryKeys.findIndex(pred) === -1) {
- const newIndexRecord = {
- indexKey: indexKey,
- primaryKeys: [...existingRecord.primaryKeys, primaryKey].sort(
- compareKeys,
- ),
- };
- index.modifiedData = indexData.with(indexKey, newIndexRecord,
true);
- }
+ 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: [primaryKey],
+ primaryKeys,
};
index.modifiedData = indexData.with(indexKey, newIndexRecord, true);
}
@@ -1699,3 +1463,286 @@ export class MemoryBackend implements Backend {
}
}
}
+
+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, range, forward, indexData } = req;
+ let indexPos = req.lastIndexPosition;
+ let objectStorePos: IDBValidKey | undefined = undefined;
+ let indexEntry: IndexRecord | undefined = undefined;
+ const rangeStart = forward ? range.lower : range.upper;
+ const dataStart = forward ? indexData.minKey() : indexData.maxKey();
+ indexPos = furthestKey(forward, indexPos, rangeStart);
+ indexPos = furthestKey(forward, indexPos, dataStart);
+
+ function nextIndexEntry(): IndexRecord | undefined {
+ assertInvariant(indexPos != null);
+ const res: [IDBValidKey, IndexRecord] | undefined = forward
+ ? indexData.nextHigherPair(indexPos)
+ : indexData.nextLowerPair(indexPos);
+ if (res) {
+ indexEntry = res[1];
+ indexPos = indexEntry.indexKey;
+ return indexEntry;
+ } else {
+ indexEntry = undefined;
+ indexPos = undefined;
+ return undefined;
+ }
+ }
+
+ function packResult(): RecordGetResponse {
+ return {
+ count: numResults,
+ indexKeys:
+ req.resultLevel >= ResultLevel.OnlyKeys ? indexKeys : undefined,
+ primaryKeys:
+ req.resultLevel >= ResultLevel.OnlyKeys ? primaryKeys : undefined,
+ values: req.resultLevel >= ResultLevel.Full ? values : undefined,
+ };
+ }
+
+ if (indexPos == null) {
+ return packResult();
+ }
+
+ // Now we align at indexPos and after objectStorePos
+
+ indexEntry = indexData.get(indexPos);
+ if (!indexEntry) {
+ // We're not aligned to an index key, go to next index entry
+ nextIndexEntry();
+ }
+ if (indexEntry) {
+ objectStorePos = nextKey(
+ true,
+ indexEntry.primaryKeys,
+ req.lastObjectStorePosition,
+ );
+ }
+
+ if (
+ forward &&
+ range.lowerOpen &&
+ range.lower != null &&
+ compareKeys(range.lower, indexPos) === 0
+ ) {
+ const e = nextIndexEntry();
+ objectStorePos = e?.primaryKeys.minKey();
+ }
+
+ if (
+ !forward &&
+ range.upperOpen &&
+ range.upper != null &&
+ compareKeys(range.upper, indexPos) === 0
+ ) {
+ const e = nextIndexEntry();
+ objectStorePos = e?.primaryKeys.minKey();
+ }
+
+ if (
+ unique &&
+ indexPos != null &&
+ req.lastIndexPosition != null &&
+ compareKeys(indexPos, req.lastIndexPosition) === 0
+ ) {
+ const e = nextIndexEntry();
+ objectStorePos = e?.primaryKeys.minKey();
+ }
+
+ if (req.advancePrimaryKey) {
+ indexPos = furthestKey(forward, indexPos, req.advanceIndexKey);
+ if (indexPos) {
+ indexEntry = indexData.get(indexPos);
+ if (!indexEntry) {
+ nextIndexEntry();
+ }
+ }
+ }
+
+ // Use advancePrimaryKey if necessary
+ if (
+ req.advanceIndexKey != null &&
+ req.advancePrimaryKey &&
+ indexPos != null &&
+ indexEntry &&
+ compareKeys(indexPos, req.advanceIndexKey) == 0
+ ) {
+ if (
+ objectStorePos == null ||
+ compareKeys(req.advancePrimaryKey, objectStorePos) > 0
+ ) {
+ objectStorePos = nextKey(
+ true,
+ indexEntry.primaryKeys,
+ req.advancePrimaryKey,
+ );
+ }
+ }
+
+ while (1) {
+ if (indexPos === undefined) {
+ break;
+ }
+ if (req.limit != 0 && numResults == req.limit) {
+ break;
+ }
+ if (!range.includes(indexPos)) {
+ break;
+ }
+ if (indexEntry === undefined) {
+ break;
+ }
+ if (objectStorePos == null) {
+ // We don't have any more records with the current index key.
+ nextIndexEntry();
+ if (indexEntry) {
+ objectStorePos = indexEntry.primaryKeys.minKey();
+ }
+ continue;
+ }
+ indexKeys.push(indexEntry.indexKey);
+ primaryKeys.push(objectStorePos);
+ numResults++;
+ if (unique) {
+ objectStorePos = undefined;
+ } else {
+ objectStorePos = indexEntry.primaryKeys.nextHigherKey(objectStorePos);
+ }
+ }
+
+ // Now we can 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(result.value);
+ }
+ }
+
+ return packResult();
+}
+
+function getObjectStoreRecords(req: {
+ storeData: ISortedMapF<IDBValidKey, ObjectStoreRecord>;
+ lastIndexPosition?: IDBValidKey;
+ forward: boolean;
+ range: IDBKeyRange;
+ lastObjectStorePosition?: IDBValidKey;
+ advancePrimaryKey?: IDBValidKey;
+ limit: number;
+ resultLevel: ResultLevel;
+}): RecordGetResponse {
+ let numResults = 0;
+ const indexKeys: Key[] = [];
+ const primaryKeys: Key[] = [];
+ const values: Value[] = [];
+ const { storeData, range, forward } = req;
+
+ function packResult(): RecordGetResponse {
+ 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 rangeStart = forward ? range.lower : range.upper;
+ const dataStart = forward ? storeData.minKey() : storeData.maxKey();
+ let storePos = req.lastObjectStorePosition;
+ storePos = furthestKey(forward, storePos, rangeStart);
+ storePos = furthestKey(forward, storePos, dataStart);
+ 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/backend-interface.ts
b/packages/idb-bridge/src/backend-interface.ts
index ae43c9df..1b9883d2 100644
--- a/packages/idb-bridge/src/backend-interface.ts
+++ b/packages/idb-bridge/src/backend-interface.ts
@@ -103,7 +103,7 @@ export interface RecordGetRequest {
advancePrimaryKey?: IDBValidKey;
/**
* Maximum number of results to return.
- * If -1, return all available results
+ * If 0, return all available results
*/
limit: number;
resultLevel: ResultLevel;
diff --git a/packages/idb-bridge/src/bridge-idb.ts
b/packages/idb-bridge/src/bridge-idb.ts
index f015d2a9..9ea258fd 100644
--- a/packages/idb-bridge/src/bridge-idb.ts
+++ b/packages/idb-bridge/src/bridge-idb.ts
@@ -1132,8 +1132,6 @@ export class BridgeIDBIndex implements IDBIndex {
);
}
- BridgeIDBFactory.enableTracing && console.log("opening cursor on", this);
-
this._confirmActiveTransaction();
range = simplifyRange(range);
diff --git
a/packages/idb-bridge/src/idb-wpt-ported/idbcursor-update-index.test.ts
b/packages/idb-bridge/src/idb-wpt-ported/idbcursor-update-index.test.ts
index 363ef4af..53866545 100644
--- a/packages/idb-bridge/src/idb-wpt-ported/idbcursor-update-index.test.ts
+++ b/packages/idb-bridge/src/idb-wpt-ported/idbcursor-update-index.test.ts
@@ -1,7 +1,5 @@
import test from "ava";
import { BridgeIDBCursor, BridgeIDBKeyRange } from "..";
-import { BridgeIDBCursorWithValue } from "../bridge-idb";
-import { IDBDatabase } from "../idbtypes";
import {
createDatabase,
createdb,
diff --git a/packages/idb-bridge/src/index.ts b/packages/idb-bridge/src/index.ts
index fa9edaea..0abbf105 100644
--- a/packages/idb-bridge/src/index.ts
+++ b/packages/idb-bridge/src/index.ts
@@ -16,7 +16,6 @@ import { Listener } from "./util/FakeEventTarget";
import {
DatabaseDump,
ObjectStoreDump,
- IndexDump,
IndexRecord,
ObjectStoreRecord,
MemoryBackendDump,
@@ -64,7 +63,6 @@ export type {
RequestObj,
DatabaseDump,
ObjectStoreDump,
- IndexDump,
IndexRecord,
ObjectStoreRecord,
IndexProperties,
diff --git a/packages/idb-bridge/src/tree/b+tree.ts
b/packages/idb-bridge/src/tree/b+tree.ts
index abe65e35..76dd79dd 100644
--- a/packages/idb-bridge/src/tree/b+tree.ts
+++ b/packages/idb-bridge/src/tree/b+tree.ts
@@ -1,30 +1,6 @@
-/*
-Copyright (c) 2018 David Piepgrass
-
-Permission is hereby granted, free of charge, to any person obtaining a copy
-of this software and associated documentation files (the "Software"), to deal
-in the Software without restriction, including without limitation the rights
-to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
-copies of the Software, and to permit persons to whom the Software is
-furnished to do so, subject to the following conditions:
-
-The above copyright notice and this permission notice shall be included in all
-copies or substantial portions of the Software.
-
-THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
-IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
-FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
-AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
-LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
-OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
-SOFTWARE.
-
-SPDX-License-Identifier: MIT
-*/
-
-// Original repository: https://github.com/qwertie/btree-typescript
-
+// B+ tree by David Piepgrass. License: MIT
import { ISortedMap, ISortedMapF } from "./interfaces";
+
export type {
ISetSource,
ISetSink,
@@ -71,17 +47,108 @@ type index = number;
// - 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
-/** Compares two numbers, strings, arrays of numbers/strings, Dates,
- * or objects that have a valueOf() method returning a number or string.
- * Optimized for numbers. Returns 1 if a>b, -1 if a<b, and 0 if a===b.
+/**
+ * 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: any, b: any) {
- var c = a - b;
- if (c === c) return c; // a & b are number
- // General case (c is NaN): string / arrays / Date / incomparable things
- if (a) a = a.valueOf();
- if (b) b = b.valueOf();
- return a < b ? -1 : a > b ? 1 : a == b ? 0 : c;
+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;
}
/**
@@ -153,12 +220,17 @@ export default class BTree<K = any, V = any>
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.
- * This is not required for numbers, strings and arrays of numbers/strings.
+ * 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.
@@ -169,11 +241,13 @@ export default class BTree<K = any, V = any>
maxNodeSize?: number,
) {
this._maxNodeSize = maxNodeSize! >= 4 ? Math.min(maxNodeSize!, 256) : 32;
- this._compare = compare || defaultComparator;
+ this._compare =
+ compare || ((defaultComparator as any) as (a: K, b: K) => number);
if (entries) this.setPairs(entries);
}
- // ES6 Map<K,V> methods ///////////////////////////////////////////////////
+ /////////////////////////////////////////////////////////////////////////////
+ // ES6 Map<K,V> methods /////////////////////////////////////////////////////
/** Gets the number of key-value pairs in the tree. */
get size() {
@@ -292,7 +366,8 @@ export default class BTree<K = any, V = any>
return this.editRange(key, key, true, DeleteRange) !== 0;
}
- // Clone-mutators /////////////////////////////////////////////////////////
+ /////////////////////////////////////////////////////////////////////////////
+ // Clone-mutators ///////////////////////////////////////////////////////////
/** Returns a copy of the tree with the specified key set (the value is
undefined). */
with(key: K): BTree<K, V | undefined>;
@@ -437,7 +512,8 @@ export default class BTree<K = any, V = any>
return p;
}
- // Iterator methods ///////////////////////////////////////////////////////
+ /////////////////////////////////////////////////////////////////////////////
+ // Iterator methods /////////////////////////////////////////////////////////
/** Returns an iterator that provides items in order (ascending order if
* the collection's comparator uses ascending order, as is the default.)
@@ -500,7 +576,7 @@ export default class BTree<K = any, V = any>
/** Returns an iterator that provides items in reversed order.
* @param highestKey Key at which to start iterating, or undefined to
- * start at minKey(). If the specified key doesn't exist then
iteration
+ * 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.
@@ -512,13 +588,21 @@ export default class BTree<K = any, V = any>
reusedArray?: (K | V)[],
skipHighest?: boolean,
): IterableIterator<[K, V]> {
- if ((highestKey = highestKey || this.maxKey()) === undefined)
- return iterator<[K, V]>(); // collection is empty
+ 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 || this._compare(leaf.keys[i], highestKey) > 0)) i++;
+ if (
+ !skipHighest &&
+ i < leaf.keys.length &&
+ this._compare(leaf.keys[i], highestKey) <= 0
+ )
+ i++;
var state = reusedArray !== undefined ? 1 : 0;
return iterator<[K, V]>(() => {
@@ -596,6 +680,319 @@ export default class BTree<K = any, V = any>
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,
+ );
+ }
+
+ ///////////////////////////////////////////////////////////////////////////
+ // 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> {
@@ -618,7 +1015,8 @@ export default class BTree<K = any, V = any>
});
}
- // Additional methods /////////////////////////////////////////////////////
+ /////////////////////////////////////////////////////////////////////////////
+ // Additional methods ///////////////////////////////////////////////////////
/** Returns the maximum number of children/values before nodes will split. */
get maxNodeSize() {
@@ -714,30 +1112,90 @@ export default class BTree<K = any, V = any>
return this.set(key, value, false);
}
- /** Returns the next pair whose key is larger than the specified key (or
undefined if there is none) */
- nextHigherPair(key: K): [K, V] | undefined {
- var it = this.entries(key, ReusedArray);
- var r = it.next();
- if (!r.done && this._compare(r.value[0], key) <= 0) r = it.next();
- return r.value;
+ /** 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) */
- nextHigherKey(key: K): K | undefined {
- var p = this.nextHigherPair(key);
- return p ? p[0] : p;
+ /** 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) */
- nextLowerPair(key: K): [K, V] | undefined {
- var it = this.entriesReversed(key, ReusedArray, true);
- return it.next().value;
+ /** 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) */
- nextLowerKey(key: K): K | undefined {
- var p = this.nextLowerPair(key);
- return p ? p[0] : p;
+ /** 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.
@@ -836,7 +1294,7 @@ export default class BTree<K = any, V = any>
/**
* 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
+ * Specfically, 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
@@ -926,9 +1384,15 @@ export default class BTree<K = any, V = any>
/** 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 {
- for (var node = this._root, h = -1; node != null; h++)
- node = (node as any).children;
- return h;
+ 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.
@@ -948,7 +1412,8 @@ export default class BTree<K = any, V = any>
/** Ensures mutations are allowed, reversing the effect of freeze(). */
unfreeze() {
- // @ts-ignore
+ // @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;
@@ -967,7 +1432,7 @@ export default class BTree<K = any, V = any>
* 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);
+ var size = this._root.checkValid(0, this, 0);
check(
size === this.size,
"size mismatch: counted ",
@@ -987,10 +1452,7 @@ if (Symbol && Symbol.iterator)
(BTree as any).prototype.add = BTree.prototype.set;
function iterator<T>(
- next: () => { done?: boolean; value?: T } = () => ({
- done: true,
- value: undefined,
- }),
+ next: () => IteratorResult<T> = () => ({ done: true, value: undefined }),
): IterableIterator<T> {
var result: any = { next };
if (Symbol && Symbol.iterator)
@@ -1016,6 +1478,7 @@ class BNode<K, V> {
this.isShared = undefined;
}
+ ///////////////////////////////////////////////////////////////////////////
// Shared methods /////////////////////////////////////////////////////////
maxKey() {
@@ -1025,7 +1488,6 @@ class BNode<K, V> {
// 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 {
- // TODO: benchmark multiple search strategies
const keys = this.keys;
var lo = 0,
hi = keys.length,
@@ -1094,12 +1556,28 @@ class BNode<K, V> {
return c === 0 ? i : i ^ failXor;*/
}
+ /////////////////////////////////////////////////////////////////////////////
// Leaf Node: misc //////////////////////////////////////////////////////////
- minKey() {
+ 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>(
@@ -1117,7 +1595,40 @@ class BNode<K, V> {
return i < 0 ? defaultValue : this.values[i];
}
- checkValid(depth: number, tree: BTree<K, V>): number {
+ 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(
@@ -1127,16 +1638,25 @@ class BNode<K, V> {
"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);
+ check(
+ depth == 0 || kL > 0,
+ "empty leaf at depth",
+ depth,
+ "and baseIndex",
+ baseIndex,
+ );
return kL;
}
+ /////////////////////////////////////////////////////////////////////////////
// Leaf Node: set & node splitting //////////////////////////////////////////
set(
@@ -1233,6 +1753,7 @@ class BNode<K, V> {
return new BNode<K, V>(keys, values);
}
+ /////////////////////////////////////////////////////////////////////////////
// Leaf Node: scanning & deletions //////////////////////////////////////////
forRange<R>(
@@ -1331,6 +1852,14 @@ class BNodeInternal<K, V> extends BNode<K, V> {
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;
@@ -1339,8 +1868,51 @@ class BNodeInternal<K, V> extends BNode<K, V> {
: undefined;
}
- checkValid(depth: number, tree: BTree<K, V>): number {
- var kL = this.keys.length,
+ 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,
@@ -1349,19 +1921,30 @@ class BNodeInternal<K, V> extends BNode<K, V> {
"lengths",
kL,
cL,
+ "baseIndex",
+ baseIndex,
+ );
+ check(
+ kL > 1 || depth > 0,
+ "internal node has length",
+ kL,
+ "at depth",
+ depth,
+ "baseIndex",
+ baseIndex,
);
- check(kL > 1, "internal node has length", kL, "at depth", depth);
- var size = 0,
+ 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);
+ size += c[i].checkValid(depth + 1, tree, baseIndex + size);
childSize += c[i].keys.length;
- check(size >= childSize, "wtf"); // no way this will ever fail
+ check(size >= childSize, "wtf", baseIndex); // no way this will ever fail
check(
i === 0 || c[i - 1].constructor === c[i].constructor,
- "type mismatch",
+ "type mismatch, baseIndex:",
+ baseIndex,
);
if (c[i].maxKey() != k[i])
check(
@@ -1374,6 +1957,8 @@ class BNodeInternal<K, V> extends BNode<K, V> {
c[i].maxKey(),
"at depth",
depth,
+ "baseIndex",
+ baseIndex,
);
if (!(i === 0 || tree._compare(k[i - 1], k[i]) < 0))
check(
@@ -1387,7 +1972,9 @@ class BNodeInternal<K, V> extends BNode<K, V> {
k[i],
);
}
- var toofew = childSize < (tree.maxNodeSize >> 1) * cL;
+ // 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,
@@ -1397,14 +1984,17 @@ class BNodeInternal<K, V> extends BNode<K, V> {
size,
") at depth",
depth,
- ", maxNodeSize:",
+ "maxNodeSize:",
tree.maxNodeSize,
"children.length:",
cL,
+ "baseIndex:",
+ baseIndex,
);
return size;
}
+ /////////////////////////////////////////////////////////////////////////////
// Internal Node: set & node splitting //////////////////////////////////////
set(
@@ -1497,8 +2087,12 @@ class BNodeInternal<K, V> extends BNode<K, V> {
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,
@@ -1509,14 +2103,14 @@ class BNodeInternal<K, V> extends BNode<K, V> {
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),
- this.keys.length - 1,
+ keys.length - 1,
);
- var keys = this.keys,
- children = this.children;
if (!editMode) {
// Simple case
for (; i <= iHigh; i++) {
@@ -1545,6 +2139,8 @@ class BNodeInternal<K, V> extends BNode<K, V> {
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;
@@ -1554,15 +2150,18 @@ class BNodeInternal<K, V> extends BNode<K, V> {
var half = tree._maxNodeSize >> 1;
if (iLow > 0) iLow--;
for (i = iHigh; i >= iLow; i--) {
- if (children[i].keys.length <= half)
- this.tryMerge(i, tree._maxNodeSize);
- }
- // Are we completely empty?
- if (children[0].keys.length === 0) {
- check(children.length === 1 && keys.length === 1, "emptiness bug");
- children.shift();
- keys.shift();
+ 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;
@@ -1601,6 +2200,27 @@ class BNodeInternal<K, V> extends BNode<K, V> {
}
}
+/**
+ * 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
@@ -1608,6 +2228,10 @@ class BNodeInternal<K, V> extends BNode<K, V> {
// 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 },
@@ -1623,7 +2247,7 @@ const ReusedArray: any[] = []; // assumed thread-local
function check(fact: boolean, ...args: any[]) {
if (!fact) {
- args.unshift("B+ tree "); // at beginning of message
+ args.unshift("B+ tree"); // at beginning of message
throw new Error(args.join(" "));
}
}
diff --git a/packages/idb-bridge/src/tree/interfaces.ts
b/packages/idb-bridge/src/tree/interfaces.ts
index ce8808d0..01013c03 100644
--- a/packages/idb-bridge/src/tree/interfaces.ts
+++ b/packages/idb-bridge/src/tree/interfaces.ts
@@ -1,28 +1,4 @@
-/*
-Copyright (c) 2018 David Piepgrass
-
-Permission is hereby granted, free of charge, to any person obtaining a copy
-of this software and associated documentation files (the "Software"), to deal
-in the Software without restriction, including without limitation the rights
-to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
-copies of the Software, and to permit persons to whom the Software is
-furnished to do so, subject to the following conditions:
-
-The above copyright notice and this permission notice shall be included in all
-copies or substantial portions of the Software.
-
-THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
-IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
-FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
-AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
-LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
-OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
-SOFTWARE.
-
-SPDX-License-Identifier: MIT
-*/
-
-// Original repository: https://github.com/qwertie/btree-typescript
+// 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
@@ -350,6 +326,8 @@ export interface IMapF<K = any, V = any> extends
IMapSource<K, V>, ISetF<K> {
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>
diff --git a/packages/idb-bridge/src/util/structuredClone.test.ts
b/packages/idb-bridge/src/util/structuredClone.test.ts
index 352c2c30..a14260da 100644
--- a/packages/idb-bridge/src/util/structuredClone.test.ts
+++ b/packages/idb-bridge/src/util/structuredClone.test.ts
@@ -46,9 +46,16 @@ test("structured clone", (t) => {
});
});
-test("structured clone (cycles)", (t) => {
+test("structured clone (array cycles)", (t) => {
const obj1: any[] = [1, 2];
obj1.push(obj1);
const obj1Clone = structuredClone(obj1);
t.is(obj1Clone, obj1Clone[2]);
});
+
+test("structured clone (object cycles)", (t) => {
+ const obj1: any = { a: 1, b: 2 };
+ obj1.c = obj1;
+ const obj1Clone = structuredClone(obj1);
+ t.is(obj1Clone, obj1Clone.c);
+});
diff --git a/packages/idb-bridge/src/util/structuredClone.ts
b/packages/idb-bridge/src/util/structuredClone.ts
index b6b53743..51e4483e 100644
--- a/packages/idb-bridge/src/util/structuredClone.ts
+++ b/packages/idb-bridge/src/util/structuredClone.ts
@@ -14,7 +14,7 @@
permissions and limitations under the License.
*/
-import cloneDeep from "lodash/cloneDeep";
+import { DataCloneError } from "./errors.js";
const { toString: toStr } = {};
const hasOwn = {}.hasOwnProperty;
@@ -77,6 +77,100 @@ function isRegExp(val: any): boolean {
return toStringTag(val) === "RegExp";
}
+function copyBuffer(cur: any) {
+ if (cur instanceof Buffer) {
+ return Buffer.from(cur);
+ }
+
+ return new cur.constructor(cur.buffer.slice(), cur.byteOffset, cur.length);
+}
+
+function checkCloneableOrThrow(x: any) {
+ if (x == null) return;
+ if (typeof x !== "object" && typeof x !== "function") return;
+ if (x instanceof Date) return;
+ if (Array.isArray(x)) return;
+ if (x instanceof Map) return;
+ if (x instanceof Set) return;
+ if (isUserObject(x)) return;
+ if (isPlainObject(x)) return;
+ throw new DataCloneError();
+}
+
+export function mkDeepClone() {
+ const refs = [] as any;
+ const refsNew = [] as any;
+
+ return clone;
+
+ function cloneArray(a: any) {
+ var keys = Object.keys(a);
+ var a2 = new Array(keys.length);
+ refs.push(a);
+ refsNew.push(a2);
+ for (var i = 0; i < keys.length; i++) {
+ var k = keys[i] as any;
+ var cur = a[k];
+ checkCloneableOrThrow(cur);
+ if (typeof cur !== "object" || cur === null) {
+ a2[k] = cur;
+ } else if (cur instanceof Date) {
+ a2[k] = new Date(cur);
+ } else if (ArrayBuffer.isView(cur)) {
+ a2[k] = copyBuffer(cur);
+ } else {
+ var index = refs.indexOf(cur);
+ if (index !== -1) {
+ a2[k] = refsNew[index];
+ } else {
+ a2[k] = clone(cur);
+ }
+ }
+ }
+ refs.pop();
+ refsNew.pop();
+ return a2;
+ }
+
+ function clone(o: any) {
+ checkCloneableOrThrow(o);
+ if (typeof o !== "object" || o === null) return o;
+ if (o instanceof Date) return new Date(o);
+ if (Array.isArray(o)) return cloneArray(o);
+ if (o instanceof Map) return new Map(cloneArray(Array.from(o)));
+ if (o instanceof Set) return new Set(cloneArray(Array.from(o)));
+ var o2 = {} as any;
+ refs.push(o);
+ refsNew.push(o2);
+ for (var k in o) {
+ if (Object.hasOwnProperty.call(o, k) === false) continue;
+ var cur = o[k] as any;
+ checkCloneableOrThrow(cur);
+ if (typeof cur !== "object" || cur === null) {
+ o2[k] = cur;
+ } else if (cur instanceof Date) {
+ o2[k] = new Date(cur);
+ } else if (cur instanceof Map) {
+ o2[k] = new Map(cloneArray(Array.from(cur)));
+ } else if (cur instanceof Set) {
+ o2[k] = new Set(cloneArray(Array.from(cur)));
+ } else if (ArrayBuffer.isView(cur)) {
+ o2[k] = copyBuffer(cur);
+ } else {
+ var i = refs.indexOf(cur);
+ if (i !== -1) {
+ o2[k] = refsNew[i];
+ } else {
+ o2[k] = clone(cur);
+ }
+ }
+ }
+ refs.pop();
+ refsNew.pop();
+ return o2;
+ }
+}
+
function internalEncapsulate(
val: any,
outRoot: any,
@@ -262,5 +356,5 @@ export function structuredRevive(val: any): any {
* Structured clone for IndexedDB.
*/
export function structuredClone(val: any): any {
- return cloneDeep(val);
+ return mkDeepClone()(val);
}
diff --git a/pnpm-lock.yaml b/pnpm-lock.yaml
index bad5c096..923659f3 100644
--- a/pnpm-lock.yaml
+++ b/pnpm-lock.yaml
@@ -129,24 +129,20 @@ importers:
'@rollup/plugin-commonjs': ^17.1.0
'@rollup/plugin-json': ^4.1.0
'@rollup/plugin-node-resolve': ^11.2.0
- '@types/lodash': ^4.14.178
'@types/node': ^14.14.22
ava: ^3.15.0
esm: ^3.2.25
- lodash: ^4.17.21
prettier: ^2.2.1
rimraf: ^3.0.2
rollup: ^2.37.1
tslib: ^2.1.0
typescript: ^4.1.3
dependencies:
- lodash: 4.17.21
tslib: 2.1.0
devDependencies:
'@rollup/plugin-commonjs': 17.1.0_rollup@2.37.1
'@rollup/plugin-json': 4.1.0_rollup@2.37.1
'@rollup/plugin-node-resolve': 11.2.0_rollup@2.37.1
- '@types/lodash': 4.14.178
'@types/node': 14.14.22
ava: 3.15.0
esm: 3.2.25
@@ -10169,10 +10165,6 @@ packages:
resolution: {integrity: sha1-7ihweulOEdK4J7y+UnC86n8+ce4=}
dev: true
- /@types/lodash/4.14.178:
- resolution: {integrity:
sha512-0d5Wd09ItQWH1qFbEyQ7oTQ3GZrMfth5JkbN3EvTKLXcHLRDSXeLnlvlOn0wvxVIwK5o2M8JzP/OWz7T3NRsbw==}
- dev: true
-
/@types/markdown-to-jsx/6.11.3:
resolution: {integrity:
sha512-30nFYpceM/ZEvhGiqWjm5quLUxNeld0HCzJEXMZZDpq53FPkS85mTwkWtCXzCqq8s5JYLgM5W392a02xn8Bdaw==}
dependencies:
@@ -11573,7 +11565,7 @@ packages:
/axios/0.21.4:
resolution: {integrity:
sha512-ut5vewkiu8jjGBdqpM44XxjuCjq9LAKeHVmoVfHVzy8eHgxxq8SbAVQNovDA8mVi05kP0Ea/n/UzcSHcTJQfNg==}
dependencies:
- follow-redirects: 1.14.5
+ follow-redirects: 1.14.5_debug@4.3.2
transitivePeerDependencies:
- debug
dev: true
@@ -15713,16 +15705,6 @@ packages:
optional: true
dev: false
- /follow-redirects/1.14.5:
- resolution: {integrity:
sha512-wtphSXy7d4/OR+MvIFbCVBDzZ5520qV8XfPklSN5QtxuMUJZ+b0Wnst1e1lCDocfzuCkHqj8k0FpZqO+UIaKNA==}
- engines: {node: '>=4.0'}
- peerDependencies:
- debug: '*'
- peerDependenciesMeta:
- debug:
- optional: true
- dev: true
-
/follow-redirects/1.14.5_debug@4.3.2:
resolution: {integrity:
sha512-wtphSXy7d4/OR+MvIFbCVBDzZ5520qV8XfPklSN5QtxuMUJZ+b0Wnst1e1lCDocfzuCkHqj8k0FpZqO+UIaKNA==}
engines: {node: '>=4.0'}
@@ -19335,6 +19317,7 @@ packages:
/lodash/4.17.21:
resolution: {integrity:
sha512-v2kDEe57lecTulaDIuNTPy3Ry4gLGJ6Z1O3vE1krgXZNrsQ+LFTGHVxVjcXPs17LhbZVGedAJv8XZ1tvj5FvSg==}
+ dev: true
/log-symbols/4.1.0:
resolution: {integrity:
sha512-8XPvpAA8uyhfteu8pIvQxpJZ7SYYdpUivZpGy6sFsBuKRY/7rQGavedeB8aK+Zkyq6upMFVL/9AW6vOYzfRyLg==}
@@ -20948,7 +20931,7 @@ packages:
resolution: {integrity:
sha512-7Wjy+9E3WwLOEL30D+m8TSTF7qJJUJLONBnwQp0518siuMxUQUbgZwssaFX+QKlZkjHZcw/IpZCt/H0srrntSg==}
engines: {node: '>=6'}
dependencies:
- ts-pnp: 1.2.0_typescript@4.4.3
+ ts-pnp: 1.2.0_typescript@4.3.5
transitivePeerDependencies:
- typescript
dev: true
@@ -25024,6 +25007,18 @@ packages:
tslib: 2.3.1
dev: true
+ /ts-pnp/1.2.0_typescript@4.3.5:
+ resolution: {integrity:
sha512-csd+vJOb/gkzvcCHgTGSChYpy5f1/XKNsmvBGO4JXS+z1v2HobugDz4s1IeFXM3wZB44uczs+eazB5Q/ccdhQw==}
+ engines: {node: '>=6'}
+ peerDependencies:
+ typescript: '*'
+ peerDependenciesMeta:
+ typescript:
+ optional: true
+ dependencies:
+ typescript: 4.3.5
+ dev: true
+
/ts-pnp/1.2.0_typescript@4.4.3:
resolution: {integrity:
sha512-csd+vJOb/gkzvcCHgTGSChYpy5f1/XKNsmvBGO4JXS+z1v2HobugDz4s1IeFXM3wZB44uczs+eazB5Q/ccdhQw==}
engines: {node: '>=6'}
--
To stop receiving notification emails like this one, please contact
gnunet@gnunet.org.