diff options
Diffstat (limited to 'packages')
| -rw-r--r-- | packages/idb-bridge/package.json | 2 | ||||
| -rw-r--r-- | packages/idb-bridge/src/MemoryBackend.test.ts | 188 | ||||
| -rw-r--r-- | packages/idb-bridge/src/MemoryBackend.ts | 713 | ||||
| -rw-r--r-- | packages/idb-bridge/src/backend-interface.ts | 2 | ||||
| -rw-r--r-- | packages/idb-bridge/src/bridge-idb.ts | 2 | ||||
| -rw-r--r-- | packages/idb-bridge/src/idb-wpt-ported/idbcursor-update-index.test.ts | 2 | ||||
| -rw-r--r-- | packages/idb-bridge/src/index.ts | 2 | ||||
| -rw-r--r-- | packages/idb-bridge/src/tree/b+tree.ts | 822 | ||||
| -rw-r--r-- | packages/idb-bridge/src/tree/interfaces.ts | 28 | ||||
| -rw-r--r-- | packages/idb-bridge/src/util/structuredClone.test.ts | 9 | ||||
| -rw-r--r-- | packages/idb-bridge/src/util/structuredClone.ts | 98 |
11 files changed, 1399 insertions, 469 deletions
diff --git a/packages/idb-bridge/package.json b/packages/idb-bridge/package.json index f3ed0888f..52bc872da 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 292f1b495..ac1a9d908 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 41d0d7fbb..de4bca883 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"; @@ -96,17 +96,10 @@ interface Database { } /** @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 ae43c9df7..1b9883d2b 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 f015d2a9f..9ea258fd2 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 363ef4afa..538665457 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 fa9edaea6..0abbf1056 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 abe65e355..76dd79dda 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 ce8808d09..01013c038 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 352c2c30b..a14260daa 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 b6b537433..51e4483e1 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); } |