[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[taler-wallet-core] branch master updated (2237058b -> f4d66541)
|
From: |
gnunet |
|
Subject: |
[taler-wallet-core] branch master updated (2237058b -> f4d66541) |
|
Date: |
Wed, 15 Dec 2021 02:58:39 +0100 |
This is an automated email from the git hooks/post-receive script.
dold pushed a change to branch master
in repository wallet-core.
from 2237058b style
new e84a1789 idb-bridge: faster indices, various correctness fixes and
tests
new f4d66541 idb-bridge: avoid unhandled rejection when closing DB
The 2 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
Summary of changes:
packages/idb-bridge/package.json | 2 -
packages/idb-bridge/src/MemoryBackend.test.ts | 188 +++++
packages/idb-bridge/src/MemoryBackend.ts | 723 +++++++++---------
packages/idb-bridge/src/backend-interface.ts | 2 +-
packages/idb-bridge/src/bridge-idb.ts | 6 +-
.../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, 1422 insertions(+), 495 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..99d5b796 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 = {
@@ -556,10 +562,12 @@ export class MemoryBackend implements Backend {
throw Error("connection not found - already closed?");
}
const myDb = this.databases[myConn.dbName];
- // FIXME: what if we're still in a transaction?
- myDb.connectionCookies = myDb.connectionCookies.filter(
- (x) => x != conn.connectionCookie,
- );
+ 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();
}
@@ -1047,17 +1055,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 +1125,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 +1136,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 +1353,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 +1465,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..5d5f531b 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);
@@ -2657,13 +2655,13 @@ export class BridgeIDBTransaction
}
}
- await waitMacroQueue();
-
if (!request._source) {
// Special requests like indexes that just need to run some code,
// with error handling already built into operation
await operation();
} else {
+ await waitMacroQueue();
+
let event;
try {
BridgeIDBFactory.enableTracing &&
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.
- [taler-wallet-core] branch master updated (2237058b -> f4d66541),
gnunet <=