From 2ee9431f1ba5bf67546bbf85758a01991c40673f Mon Sep 17 00:00:00 2001 From: Florian Dold Date: Sat, 15 Jun 2019 22:44:54 +0200 Subject: idb wip --- packages/idb-bridge/src/BridgeIDBCursor.ts | 315 +++++ .../idb-bridge/src/BridgeIDBCursorWithValue.ts | 44 + packages/idb-bridge/src/BridgeIDBDatabase.ts | 239 ++++ packages/idb-bridge/src/BridgeIDBFactory.ts | 192 +++ packages/idb-bridge/src/BridgeIDBIndex.ts | 316 +++++ packages/idb-bridge/src/BridgeIDBKeyRange.ts | 133 ++ packages/idb-bridge/src/BridgeIDBObjectStore.ts | 441 +++++++ packages/idb-bridge/src/BridgeIDBOpenDBRequest.ts | 36 + packages/idb-bridge/src/BridgeIDBRequest.ts | 86 ++ packages/idb-bridge/src/BridgeIDBTransaction.ts | 301 +++++ .../idb-bridge/src/BridgeIDBVersionChangeEvent.ts | 41 + packages/idb-bridge/src/MemoryBackend.test.ts | 31 + packages/idb-bridge/src/MemoryBackend.ts | 662 ++++++++++ packages/idb-bridge/src/backend-interface.ts | 145 +++ packages/idb-bridge/src/tree/b+tree.ts | 1351 ++++++++++++++++++++ packages/idb-bridge/src/tree/interfaces.ts | 329 +++++ packages/idb-bridge/src/util/FakeEvent.ts | 80 ++ packages/idb-bridge/src/util/FakeEventTarget.ts | 177 +++ packages/idb-bridge/src/util/canInjectKey.ts | 34 + packages/idb-bridge/src/util/cmp.ts | 108 ++ packages/idb-bridge/src/util/deepEquals.ts | 75 ++ packages/idb-bridge/src/util/enforceRange.ts | 18 + packages/idb-bridge/src/util/errors.ts | 120 ++ packages/idb-bridge/src/util/extractKey.ts | 55 + packages/idb-bridge/src/util/fakeDOMStringList.ts | 37 + packages/idb-bridge/src/util/injectKey.ts | 48 + packages/idb-bridge/src/util/makeStoreKeyValue.ts | 92 ++ packages/idb-bridge/src/util/openPromise.ts | 22 + packages/idb-bridge/src/util/queueTask.ts | 21 + packages/idb-bridge/src/util/structuredClone.ts | 15 + packages/idb-bridge/src/util/types.ts | 73 ++ packages/idb-bridge/src/util/validateKeyPath.ts | 77 ++ packages/idb-bridge/src/util/valueToKey.ts | 70 + 33 files changed, 5784 insertions(+) create mode 100644 packages/idb-bridge/src/BridgeIDBCursor.ts create mode 100644 packages/idb-bridge/src/BridgeIDBCursorWithValue.ts create mode 100644 packages/idb-bridge/src/BridgeIDBDatabase.ts create mode 100644 packages/idb-bridge/src/BridgeIDBFactory.ts create mode 100644 packages/idb-bridge/src/BridgeIDBIndex.ts create mode 100644 packages/idb-bridge/src/BridgeIDBKeyRange.ts create mode 100644 packages/idb-bridge/src/BridgeIDBObjectStore.ts create mode 100644 packages/idb-bridge/src/BridgeIDBOpenDBRequest.ts create mode 100644 packages/idb-bridge/src/BridgeIDBRequest.ts create mode 100644 packages/idb-bridge/src/BridgeIDBTransaction.ts create mode 100644 packages/idb-bridge/src/BridgeIDBVersionChangeEvent.ts create mode 100644 packages/idb-bridge/src/MemoryBackend.test.ts create mode 100644 packages/idb-bridge/src/MemoryBackend.ts create mode 100644 packages/idb-bridge/src/backend-interface.ts create mode 100644 packages/idb-bridge/src/tree/b+tree.ts create mode 100644 packages/idb-bridge/src/tree/interfaces.ts create mode 100644 packages/idb-bridge/src/util/FakeEvent.ts create mode 100644 packages/idb-bridge/src/util/FakeEventTarget.ts create mode 100644 packages/idb-bridge/src/util/canInjectKey.ts create mode 100644 packages/idb-bridge/src/util/cmp.ts create mode 100644 packages/idb-bridge/src/util/deepEquals.ts create mode 100644 packages/idb-bridge/src/util/enforceRange.ts create mode 100644 packages/idb-bridge/src/util/errors.ts create mode 100644 packages/idb-bridge/src/util/extractKey.ts create mode 100644 packages/idb-bridge/src/util/fakeDOMStringList.ts create mode 100644 packages/idb-bridge/src/util/injectKey.ts create mode 100644 packages/idb-bridge/src/util/makeStoreKeyValue.ts create mode 100644 packages/idb-bridge/src/util/openPromise.ts create mode 100644 packages/idb-bridge/src/util/queueTask.ts create mode 100644 packages/idb-bridge/src/util/structuredClone.ts create mode 100644 packages/idb-bridge/src/util/types.ts create mode 100644 packages/idb-bridge/src/util/validateKeyPath.ts create mode 100644 packages/idb-bridge/src/util/valueToKey.ts (limited to 'packages/idb-bridge/src') diff --git a/packages/idb-bridge/src/BridgeIDBCursor.ts b/packages/idb-bridge/src/BridgeIDBCursor.ts new file mode 100644 index 000000000..0120bb7d5 --- /dev/null +++ b/packages/idb-bridge/src/BridgeIDBCursor.ts @@ -0,0 +1,315 @@ +/* + Copyright 2019 Florian Dold + Copyright 2017 Jeremy Scheff + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express + or implied. See the License for the specific language governing + permissions and limitations under the License. + */ + +import BridgeIDBKeyRange from "./BridgeIDBKeyRange"; +import BridgeIDBObjectStore from "./BridgeIDBObjectStore"; +import BridgeIDBRequest from "./BridgeIDBRequest"; +import cmp from "./util/cmp"; +import { + DataError, + InvalidAccessError, + InvalidStateError, + ReadOnlyError, + TransactionInactiveError, +} from "./util/errors"; +import extractKey from "./util/extractKey"; +import structuredClone from "./util/structuredClone"; +import { + CursorRange, + CursorSource, + Key, + Value, + BridgeIDBCursorDirection, +} from "./util/types"; +import valueToKey from "./util/valueToKey"; +import { + RecordGetRequest, + ResultLevel, + Backend, + DatabaseTransaction, + RecordStoreRequest, +} from "./backend-interface"; + +/** + * http://www.w3.org/TR/2015/REC-IndexedDB-20150108/#cursor + */ +class BridgeIDBCursor { + _request: BridgeIDBRequest | undefined; + + private _gotValue: boolean = false; + private _range: CursorRange; + private _position = undefined; // Key of previously returned record + private _objectStorePosition = undefined; + private _keyOnly: boolean = false; + + private _source: CursorSource; + private _direction: BridgeIDBCursorDirection; + private _key = undefined; + private _primaryKey: Key | undefined = undefined; + private _indexName: string | undefined; + private _objectStoreName: string; + + constructor( + source: CursorSource, + objectStoreName: string, + indexName: string | undefined, + range: CursorRange, + direction: BridgeIDBCursorDirection, + request: BridgeIDBRequest, + keyOnly: boolean, + ) { + this._indexName = indexName; + this._objectStoreName = objectStoreName; + this._range = range; + this._source = source; + this._direction = direction; + this._request = request; + this._keyOnly = keyOnly; + } + + get _effectiveObjectStore(): BridgeIDBObjectStore { + if (this.source instanceof BridgeIDBObjectStore) { + return this.source; + } + return this.source.objectStore; + } + + get _backend(): Backend { + return this._source._backend; + } + + // Read only properties + get source() { + return this._source; + } + set source(val) { + /* For babel */ + } + + get direction() { + return this._direction; + } + set direction(val) { + /* For babel */ + } + + get key() { + return this._key; + } + set key(val) { + /* For babel */ + } + + get primaryKey() { + return this._primaryKey; + } + set primaryKey(val) { + /* For babel */ + } + + /** + * https://w3c.github.io/IndexedDB/#iterate-a-cursor + */ + async _iterate(key?: Key, primaryKey?: Key): Promise { + const recordGetRequest: RecordGetRequest = { + direction: this.direction, + indexName: this._indexName, + lastIndexPosition: this._position, + lastObjectStorePosition: this._objectStorePosition, + limit: 1, + range: this._range, + objectStoreName: this._objectStoreName, + advanceIndexKey: key, + advancePrimaryKey: primaryKey, + resultLevel: this._keyOnly ? ResultLevel.OnlyKeys : ResultLevel.Full, + }; + + const { btx } = this.source._confirmActiveTransaction(); + + let response = await this._backend.getRecords( + btx, + recordGetRequest, + ); + + if (response.count === 0) { + return null; + } + + return this; + } + + // http://www.w3.org/TR/2015/REC-IndexedDB-20150108/#widl-IDBCursor-update-IDBRequest-any-value + public update(value: Value) { + if (value === undefined) { + throw new TypeError(); + } + + const transaction = this._effectiveObjectStore.transaction; + + if (transaction._state !== "active") { + throw new TransactionInactiveError(); + } + + if (transaction.mode === "readonly") { + throw new ReadOnlyError(); + } + + if (this._effectiveObjectStore._deleted) { + throw new InvalidStateError(); + } + if ( + !(this.source instanceof BridgeIDBObjectStore) && + this.source._deleted + ) { + throw new InvalidStateError(); + } + + if (!this._gotValue || !this.hasOwnProperty("value")) { + throw new InvalidStateError(); + } + + const storeReq: RecordStoreRequest = { + overwrite: true, + key: this._primaryKey, + value: value, + objectStoreName: this._objectStoreName, + }; + + const operation = async () => { + const { btx } = this.source._confirmActiveTransaction(); + this._backend.storeRecord(btx, storeReq); + }; + return transaction._execRequestAsync({ + operation, + source: this, + }); + } + + /** + * http://www.w3.org/TR/2015/REC-IndexedDB-20150108/#widl-IDBCursor-advance-void-unsigned-long-count + */ + public advance(count: number) { + throw Error("not implemented"); + } + + /** + * http://www.w3.org/TR/2015/REC-IndexedDB-20150108/#widl-IDBCursor-continue-void-any-key + */ + public continue(key?: Key) { + const transaction = this._effectiveObjectStore.transaction; + + if (transaction._state !== "active") { + throw new TransactionInactiveError(); + } + + if (this._effectiveObjectStore._deleted) { + throw new InvalidStateError(); + } + if ( + !(this.source instanceof BridgeIDBObjectStore) && + this.source._deleted + ) { + throw new InvalidStateError(); + } + + if (!this._gotValue) { + throw new InvalidStateError(); + } + + if (key !== undefined) { + key = valueToKey(key); + + const cmpResult = cmp(key, this._position); + + if ( + (cmpResult <= 0 && + (this.direction === "next" || this.direction === "nextunique")) || + (cmpResult >= 0 && + (this.direction === "prev" || this.direction === "prevunique")) + ) { + throw new DataError(); + } + } + + if (this._request) { + this._request.readyState = "pending"; + } + + const operation = async () => { + this._iterate(key); + }; + + transaction._execRequestAsync({ + operation, + request: this._request, + source: this.source, + }); + + this._gotValue = false; + } + + // https://w3c.github.io/IndexedDB/#dom-idbcursor-continueprimarykey + public continuePrimaryKey(key: Key, primaryKey: Key) { + throw Error("not implemented"); + } + + public delete() { + const transaction = this._effectiveObjectStore.transaction; + + if (transaction._state !== "active") { + throw new TransactionInactiveError(); + } + + if (transaction.mode === "readonly") { + throw new ReadOnlyError(); + } + + if (this._effectiveObjectStore._deleted) { + throw new InvalidStateError(); + } + if ( + !(this.source instanceof BridgeIDBObjectStore) && + this.source._deleted + ) { + throw new InvalidStateError(); + } + + if (!this._gotValue || !this.hasOwnProperty("value")) { + throw new InvalidStateError(); + } + + const operation = async () => { + const { btx } = this.source._confirmActiveTransaction(); + this._backend.deleteRecord( + btx, + this._objectStoreName, + BridgeIDBKeyRange._valueToKeyRange(this._primaryKey), + ); + }; + + return transaction._execRequestAsync({ + operation, + source: this, + }); + } + + public toString() { + return "[object IDBCursor]"; + } +} + +export default BridgeIDBCursor; diff --git a/packages/idb-bridge/src/BridgeIDBCursorWithValue.ts b/packages/idb-bridge/src/BridgeIDBCursorWithValue.ts new file mode 100644 index 000000000..2739a6f14 --- /dev/null +++ b/packages/idb-bridge/src/BridgeIDBCursorWithValue.ts @@ -0,0 +1,44 @@ +/* + Copyright 2017 Jeremy Scheff + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express + or implied. See the License for the specific language governing + permissions and limitations under the License. + */ + +import BridgeIDBCursor from "./BridgeIDBCursor"; +import { + CursorRange, + CursorSource, + BridgeIDBCursorDirection, + Value, +} from "./util/types"; + +class FDBCursorWithValue extends BridgeIDBCursor { + public value: Value = undefined; + + constructor( + source: CursorSource, + objectStoreName: string, + indexName: string | undefined, + range: CursorRange, + direction: BridgeIDBCursorDirection, + request?: any, + ) { + super(source, objectStoreName, indexName, range, direction, request, true); + } + + public toString() { + return "[object IDBCursorWithValue]"; + } +} + +export default FDBCursorWithValue; diff --git a/packages/idb-bridge/src/BridgeIDBDatabase.ts b/packages/idb-bridge/src/BridgeIDBDatabase.ts new file mode 100644 index 000000000..cff2fd6e3 --- /dev/null +++ b/packages/idb-bridge/src/BridgeIDBDatabase.ts @@ -0,0 +1,239 @@ +/* + * Copyright 2017 Jeremy Scheff + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express + * or implied. See the License for the specific language governing + * permissions and limitations under the License. + */ + +import BridgeIDBTransaction from "./BridgeIDBTransaction"; +import { + ConstraintError, + InvalidAccessError, + InvalidStateError, + NotFoundError, + TransactionInactiveError, +} from "./util/errors"; +import fakeDOMStringList from "./util/fakeDOMStringList"; +import FakeEventTarget from "./util/FakeEventTarget"; +import { FakeDOMStringList, KeyPath, TransactionMode } from "./util/types"; +import validateKeyPath from "./util/validateKeyPath"; +import queueTask from "./util/queueTask"; +import { + Backend, + DatabaseConnection, + Schema, + DatabaseTransaction, +} from "./backend-interface"; + +/** + * Ensure that an active version change transaction is currently running. + */ +const confirmActiveVersionchangeTransaction = (database: BridgeIDBDatabase) => { + if (!database._runningVersionchangeTransaction) { + throw new InvalidStateError(); + } + + // Find the latest versionchange transaction + const transactions = database._transactions.filter( + (tx: BridgeIDBTransaction) => { + return tx.mode === "versionchange"; + }, + ); + const transaction = transactions[transactions.length - 1]; + + if (!transaction || transaction._state === "finished") { + throw new InvalidStateError(); + } + + if (transaction._state !== "active") { + throw new TransactionInactiveError(); + } + + return transaction; +}; + + +// http://www.w3.org/TR/2015/REC-IndexedDB-20150108/#database-interface +class BridgeIDBDatabase extends FakeEventTarget { + _closePending = false; + _closed = false; + _runningVersionchangeTransaction = false; + _transactions: Array = []; + + _backendConnection: DatabaseConnection; + _backend: Backend; + + _schema: Schema; + + get name(): string { + return this._schema.databaseName; + } + + get version(): number { + return this._schema.databaseVersion; + } + + get objectStoreNames(): FakeDOMStringList { + return fakeDOMStringList(Object.keys(this._schema.objectStores)).sort(); + } + + /** + * http://www.w3.org/TR/2015/REC-IndexedDB-20150108/#database-closing-steps + */ + _closeConnection() { + this._closePending = true; + + const transactionsComplete = this._transactions.every( + (transaction: BridgeIDBTransaction) => { + return transaction._state === "finished"; + }, + ); + + if (transactionsComplete) { + this._closed = true; + this._backend.close(this._backendConnection); + } else { + queueTask(() => { + this._closeConnection(); + }); + } + } + + constructor(backend: Backend, backendConnection: DatabaseConnection) { + super(); + + this._schema = backend.getSchema(backendConnection); + + this._backend = backend; + this._backendConnection = backendConnection; + } + + // http://w3c.github.io/IndexedDB/#dom-idbdatabase-createobjectstore + public createObjectStore( + name: string, + options: { autoIncrement?: boolean; keyPath?: KeyPath } | null = {}, + ) { + if (name === undefined) { + throw new TypeError(); + } + const transaction = confirmActiveVersionchangeTransaction(this); + const backendTx = transaction._backendTransaction; + if (!backendTx) { + throw Error("invariant violated"); + } + + const keyPath = + options !== null && options.keyPath !== undefined + ? options.keyPath + : null; + const autoIncrement = + options !== null && options.autoIncrement !== undefined + ? options.autoIncrement + : false; + + if (keyPath !== null) { + validateKeyPath(keyPath); + } + + if (!Object.keys(this._schema.objectStores).includes(name)) { + throw new ConstraintError(); + } + + if (autoIncrement && (keyPath === "" || Array.isArray(keyPath))) { + throw new InvalidAccessError(); + } + + transaction._backend.createObjectStore(backendTx, name, keyPath, autoIncrement); + + this._schema = this._backend.getSchema(this._backendConnection); + + return transaction.objectStore("name"); + } + + public deleteObjectStore(name: string): void { + if (name === undefined) { + throw new TypeError(); + } + const transaction = confirmActiveVersionchangeTransaction(this); + transaction._objectStoresCache.delete(name); + } + + public _internalTransaction( + storeNames: string | string[], + mode?: TransactionMode, + backendTransaction?: DatabaseTransaction, + ): BridgeIDBTransaction { + mode = mode !== undefined ? mode : "readonly"; + if ( + mode !== "readonly" && + mode !== "readwrite" && + mode !== "versionchange" + ) { + throw new TypeError("Invalid mode: " + mode); + } + + const hasActiveVersionchange = this._transactions.some( + (transaction: BridgeIDBTransaction) => { + return ( + transaction._state === "active" && + transaction.mode === "versionchange" && + transaction.db === this + ); + }, + ); + if (hasActiveVersionchange) { + throw new InvalidStateError(); + } + + if (this._closePending) { + throw new InvalidStateError(); + } + + if (!Array.isArray(storeNames)) { + storeNames = [storeNames]; + } + if (storeNames.length === 0 && mode !== "versionchange") { + throw new InvalidAccessError(); + } + for (const storeName of storeNames) { + if (this.objectStoreNames.indexOf(storeName) < 0) { + throw new NotFoundError( + "No objectStore named " + storeName + " in this database", + ); + } + } + + const tx = new BridgeIDBTransaction(storeNames, mode, this, backendTransaction); + this._transactions.push(tx); + return tx; + } + + public transaction( + storeNames: string | string[], + mode?: TransactionMode, + ): BridgeIDBTransaction { + if (mode === "versionchange") { + throw new TypeError("Invalid mode: " + mode); + } + return this._internalTransaction(storeNames, mode); + } + + public close() { + this._closeConnection(); + } + + public toString() { + return "[object IDBDatabase]"; + } +} + +export default BridgeIDBDatabase; diff --git a/packages/idb-bridge/src/BridgeIDBFactory.ts b/packages/idb-bridge/src/BridgeIDBFactory.ts new file mode 100644 index 000000000..c2747238e --- /dev/null +++ b/packages/idb-bridge/src/BridgeIDBFactory.ts @@ -0,0 +1,192 @@ +/* + * Copyright 2019 Florian Dold + * Copyright 2017 Jeremy Scheff + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express + * or implied. See the License for the specific language governing + * permissions and limitations under the License. + */ + +import BridgeIDBDatabase from "./BridgeIDBDatabase"; +import BridgeIDBOpenDBRequest from "./BridgeIDBOpenDBRequest"; +import BridgeIDBVersionChangeEvent from "./BridgeIDBVersionChangeEvent"; +import compareKeys from "./util/cmp"; +import enforceRange from "./util/enforceRange"; +import { AbortError, VersionError } from "./util/errors"; +import FakeEvent from "./util/FakeEvent"; +import { Backend, DatabaseConnection } from "./backend-interface"; +import queueTask from "./util/queueTask"; + +type DatabaseList = Array<{ name: string; version: number }>; + +class BridgeIDBFactory { + public cmp = compareKeys; + private backend: Backend; + private connections: BridgeIDBDatabase[] = []; + + public constructor(backend: Backend) { + this.backend = backend; + } + + // http://www.w3.org/TR/2015/REC-IndexedDB-20150108/#widl-IDBFactory-deleteDatabase-IDBOpenDBRequest-DOMString-name + public deleteDatabase(name: string): BridgeIDBOpenDBRequest { + const request = new BridgeIDBOpenDBRequest(); + request.source = null; + + queueTask(async () => { + const databases = await this.backend.getDatabases(); + const dbInfo = databases.find((x) => x.name == name); + if (!dbInfo) { + // Database already doesn't exist, success! + const event = new BridgeIDBVersionChangeEvent("success", { + newVersion: null, + oldVersion: 0, + }); + request.dispatchEvent(event); + return; + } + const oldVersion = dbInfo.version; + + try { + const dbconn = await this.backend.connectDatabase(name); + const backendTransaction = await this.backend.enterVersionChange(dbconn, 0); + await this.backend.deleteDatabase(backendTransaction, name); + await this.backend.commit(backendTransaction); + await this.backend.close(dbconn); + + request.result = undefined; + request.readyState = "done"; + + const event2 = new BridgeIDBVersionChangeEvent("success", { + newVersion: null, + oldVersion, + }); + request.dispatchEvent(event2); + } catch (err) { + request.error = new Error(); + request.error.name = err.name; + request.readyState = "done"; + + const event = new FakeEvent("error", { + bubbles: true, + cancelable: true, + }); + event.eventPath = []; + request.dispatchEvent(event); + } + }); + + return request; + } + + // tslint:disable-next-line max-line-length + // http://www.w3.org/TR/2015/REC-IndexedDB-20150108/#widl-IDBFactory-open-IDBOpenDBRequest-DOMString-name-unsigned-long-long-version + public open(name: string, version?: number) { + if (arguments.length > 1 && version !== undefined) { + // Based on spec, not sure why "MAX_SAFE_INTEGER" instead of "unsigned long long", but it's needed to pass + // tests + version = enforceRange(version, "MAX_SAFE_INTEGER"); + } + if (version === 0) { + throw new TypeError(); + } + + const request = new BridgeIDBOpenDBRequest(); + + queueTask(async () => { + let dbconn: DatabaseConnection; + try { + dbconn = await this.backend.connectDatabase(name); + } catch (err) { + request._finishWithError(err); + return; + } + + const schema = this.backend.getSchema(dbconn); + const existingVersion = schema.databaseVersion; + + if (version === undefined) { + version = existingVersion !== 0 ? existingVersion : 1; + } + + const requestedVersion = version; + + if (existingVersion > requestedVersion) { + request._finishWithError(new VersionError()); + return; + } + + const db = new BridgeIDBDatabase(this.backend, dbconn); + + if (existingVersion < requestedVersion) { + // http://www.w3.org/TR/2015/REC-IndexedDB-20150108/#dfn-steps-for-running-a-versionchange-transaction + + for (const otherConn of this.connections) { + const event = new BridgeIDBVersionChangeEvent("versionchange", { + newVersion: version, + oldVersion: existingVersion, + }); + otherConn.dispatchEvent(event); + } + + if (this._anyOpen()) { + const event = new BridgeIDBVersionChangeEvent("blocked", { + newVersion: version, + oldVersion: existingVersion, + }); + request.dispatchEvent(event); + } + + const backendTransaction = await this.backend.enterVersionChange(dbconn, requestedVersion); + db._runningVersionchangeTransaction = true; + + const transaction = db._internalTransaction( + [], + "versionchange", + backendTransaction, + ); + const event = new BridgeIDBVersionChangeEvent("upgradeneeded", { + newVersion: version, + oldVersion: existingVersion, + }); + + request.result = db; + request.readyState = "done"; + request.transaction = transaction; + request.dispatchEvent(event); + + await transaction._waitDone(); + + db._runningVersionchangeTransaction = false; + } + + this.connections.push(db); + return db; + }); + + return request; + } + + // https://w3c.github.io/IndexedDB/#dom-idbfactory-databases + public databases(): Promise { + return this.backend.getDatabases(); + } + + public toString(): string { + return "[object IDBFactory]"; + } + + private _anyOpen(): boolean { + return this.connections.some(c => !c._closed && !c._closePending); + } +} + +export default BridgeIDBFactory; diff --git a/packages/idb-bridge/src/BridgeIDBIndex.ts b/packages/idb-bridge/src/BridgeIDBIndex.ts new file mode 100644 index 000000000..6001bc051 --- /dev/null +++ b/packages/idb-bridge/src/BridgeIDBIndex.ts @@ -0,0 +1,316 @@ +/* + Copyright 2017 Jeremy Scheff + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express + or implied. See the License for the specific language governing + permissions and limitations under the License. + */ + +import BridgeIDBCursor from "./BridgeIDBCursor"; +import BridgeIDBCursorWithValue from "./BridgeIDBCursorWithValue"; +import BridgeIDBKeyRange from "./BridgeIDBKeyRange"; +import BridgeIDBObjectStore from "./BridgeIDBObjectStore"; +import BridgeIDBRequest from "./BridgeIDBRequest"; +import enforceRange from "./util/enforceRange"; +import { + ConstraintError, + InvalidStateError, + TransactionInactiveError, +} from "./util/errors"; +import { BridgeIDBCursorDirection, Key, KeyPath } from "./util/types"; +import valueToKey from "./util/valueToKey"; +import BridgeIDBTransaction from "./BridgeIDBTransaction"; +import { + Schema, + Backend, + DatabaseTransaction, + RecordGetRequest, + ResultLevel, +} from "./backend-interface"; + +const confirmActiveTransaction = ( + index: BridgeIDBIndex, +): BridgeIDBTransaction => { + if (index._deleted || index.objectStore._deleted) { + throw new InvalidStateError(); + } + + if (index.objectStore.transaction._state !== "active") { + throw new TransactionInactiveError(); + } + + return index.objectStore.transaction; +}; + +// http://www.w3.org/TR/2015/REC-IndexedDB-20150108/#idl-def-IDBIndex +class BridgeIDBIndex { + objectStore: BridgeIDBObjectStore; + + get _schema(): Schema { + return this.objectStore.transaction.db._schema; + } + + get keyPath(): KeyPath { + return this._schema.indexes[this._name].keyPath; + } + + get multiEntry(): boolean { + return this._schema.indexes[this._name].multiEntry; + } + + get unique(): boolean { + return this._schema.indexes[this._name].unique; + } + + get _backend(): Backend { + return this.objectStore._backend; + } + + _confirmActiveTransaction(): { btx: DatabaseTransaction } { + return this.objectStore._confirmActiveTransaction(); + } + + private _name: string; + + public _deleted: boolean = false; + + constructor(objectStore: BridgeIDBObjectStore, name: string) { + this._name = name; + this.objectStore = objectStore; + } + + get name() { + return this._name; + } + + // https://w3c.github.io/IndexedDB/#dom-idbindex-name + set name(name: any) { + const transaction = this.objectStore.transaction; + + if (!transaction.db._runningVersionchangeTransaction) { + throw new InvalidStateError(); + } + + if (transaction._state !== "active") { + throw new TransactionInactiveError(); + } + + const { btx } = this._confirmActiveTransaction(); + + const oldName = this._name; + const newName = String(name); + + if (newName === oldName) { + return; + } + + this._backend.renameIndex(btx, oldName, newName); + + if (this.objectStore.indexNames.indexOf(name) >= 0) { + throw new ConstraintError(); + } + } + + // tslint:disable-next-line max-line-length + // http://www.w3.org/TR/2015/REC-IndexedDB-20150108/#widl-IDBIndex-openCursor-IDBRequest-any-range-IDBCursorDirection-direction + public openCursor( + range?: BridgeIDBKeyRange | Key | null | undefined, + direction: BridgeIDBCursorDirection = "next", + ) { + confirmActiveTransaction(this); + + if (range === null) { + range = undefined; + } + if (range !== undefined && !(range instanceof BridgeIDBKeyRange)) { + range = BridgeIDBKeyRange.only(valueToKey(range)); + } + + const request = new BridgeIDBRequest(); + request.source = this; + request.transaction = this.objectStore.transaction; + + const cursor = new BridgeIDBCursorWithValue( + this, + this.objectStore.name, + this._name, + range, + direction, + request, + ); + + const operation = async () => { + return cursor._iterate(); + }; + + return this.objectStore.transaction._execRequestAsync({ + operation, + request, + source: this, + }); + } + + // tslint:disable-next-line max-line-length + // http://www.w3.org/TR/2015/REC-IndexedDB-20150108/#widl-IDBIndex-openKeyCursor-IDBRequest-any-range-IDBCursorDirection-direction + public openKeyCursor( + range?: BridgeIDBKeyRange | Key | null | undefined, + direction: BridgeIDBCursorDirection = "next", + ) { + confirmActiveTransaction(this); + + if (range === null) { + range = undefined; + } + if (range !== undefined && !(range instanceof BridgeIDBKeyRange)) { + range = BridgeIDBKeyRange.only(valueToKey(range)); + } + + const request = new BridgeIDBRequest(); + request.source = this; + request.transaction = this.objectStore.transaction; + + const cursor = new BridgeIDBCursor( + this, + this.objectStore.name, + this._name, + range, + direction, + request, + true, + ); + + return this.objectStore.transaction._execRequestAsync({ + operation: cursor._iterate.bind(cursor), + request, + source: this, + }); + } + + public get(key: BridgeIDBKeyRange | Key) { + confirmActiveTransaction(this); + + if (!(key instanceof BridgeIDBKeyRange)) { + key = BridgeIDBKeyRange._valueToKeyRange(key); + } + + const getReq: RecordGetRequest = { + direction: "next", + indexName: this._name, + limit: 1, + range: key, + objectStoreName: this.objectStore._name, + resultLevel: ResultLevel.Full, + }; + + const operation = async () => { + const { btx } = this._confirmActiveTransaction(); + const result = await this._backend.getRecords(btx, getReq); + if (result.count == 0) { + return undefined; + } + const values = result.values; + if (!values) { + throw Error("invariant violated"); + } + return values[0]; + }; + + return this.objectStore.transaction._execRequestAsync({ + operation, + source: this, + }); + } + + // http://w3c.github.io/IndexedDB/#dom-idbindex-getall + public getAll(query?: BridgeIDBKeyRange | Key, count?: number) { + throw Error("not implemented"); + } + + // http://www.w3.org/TR/2015/REC-IndexedDB-20150108/#widl-IDBIndex-getKey-IDBRequest-any-key + public getKey(key: BridgeIDBKeyRange | Key) { + confirmActiveTransaction(this); + + if (!(key instanceof BridgeIDBKeyRange)) { + key = BridgeIDBKeyRange._valueToKeyRange(key); + } + + const getReq: RecordGetRequest = { + direction: "next", + indexName: this._name, + limit: 1, + range: key, + objectStoreName: this.objectStore._name, + resultLevel: ResultLevel.OnlyKeys, + }; + + const operation = async () => { + const { btx } = this._confirmActiveTransaction(); + const result = await this._backend.getRecords(btx, getReq); + if (result.count == 0) { + return undefined; + } + const primaryKeys = result.primaryKeys; + if (!primaryKeys) { + throw Error("invariant violated"); + } + return primaryKeys[0]; + }; + + return this.objectStore.transaction._execRequestAsync({ + operation, + source: this, + }); + } + + // http://w3c.github.io/IndexedDB/#dom-idbindex-getallkeys + public getAllKeys(query?: BridgeIDBKeyRange | Key, count?: number) { + throw Error("not implemented"); + } + + // http://www.w3.org/TR/2015/REC-IndexedDB-20150108/#widl-IDBIndex-count-IDBRequest-any-key + public count(key: BridgeIDBKeyRange | Key | null | undefined) { + confirmActiveTransaction(this); + + if (key === null) { + key = undefined; + } + if (key !== undefined && !(key instanceof BridgeIDBKeyRange)) { + key = BridgeIDBKeyRange.only(valueToKey(key)); + } + + const getReq: RecordGetRequest = { + direction: "next", + indexName: this._name, + limit: 1, + range: key, + objectStoreName: this.objectStore._name, + resultLevel: ResultLevel.OnlyCount, + }; + + const operation = async () => { + const { btx } = this._confirmActiveTransaction(); + const result = await this._backend.getRecords(btx, getReq); + return result.count; + }; + + return this.objectStore.transaction._execRequestAsync({ + operation, + source: this, + }); + + } + + public toString() { + return "[object IDBIndex]"; + } +} + +export default BridgeIDBIndex; diff --git a/packages/idb-bridge/src/BridgeIDBKeyRange.ts b/packages/idb-bridge/src/BridgeIDBKeyRange.ts new file mode 100644 index 000000000..2b32c7e0a --- /dev/null +++ b/packages/idb-bridge/src/BridgeIDBKeyRange.ts @@ -0,0 +1,133 @@ +/* + Copyright 2019 Florian Dold + Copyright 2017 Jeremy Scheff + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express + or implied. See the License for the specific language governing + permissions and limitations under the License. + */ + +import compareKeys from "./util/cmp"; +import { DataError } from "./util/errors"; +import { Key } from "./util/types"; +import valueToKey from "./util/valueToKey"; + +// http://www.w3.org/TR/2015/REC-IndexedDB-20150108/#range-concept +class BridgeIDBKeyRange { + public static only(value: Key) { + if (arguments.length === 0) { + throw new TypeError(); + } + value = valueToKey(value); + return new BridgeIDBKeyRange(value, value, false, false); + } + + static lowerBound(lower: Key, open: boolean = false) { + if (arguments.length === 0) { + throw new TypeError(); + } + lower = valueToKey(lower); + return new BridgeIDBKeyRange(lower, undefined, open, true); + } + + static upperBound(upper: Key, open: boolean = false) { + if (arguments.length === 0) { + throw new TypeError(); + } + upper = valueToKey(upper); + return new BridgeIDBKeyRange(undefined, upper, true, open); + } + + static bound( + lower: Key, + upper: Key, + lowerOpen: boolean = false, + upperOpen: boolean = false, + ) { + if (arguments.length < 2) { + throw new TypeError(); + } + + const cmpResult = compareKeys(lower, upper); + if (cmpResult === 1 || (cmpResult === 0 && (lowerOpen || upperOpen))) { + throw new DataError(); + } + + lower = valueToKey(lower); + upper = valueToKey(upper); + return new BridgeIDBKeyRange(lower, upper, lowerOpen, upperOpen); + } + + readonly lower: Key | undefined; + readonly upper: Key | undefined; + readonly lowerOpen: boolean; + readonly upperOpen: boolean; + + constructor( + lower: Key | undefined, + upper: Key | undefined, + lowerOpen: boolean, + upperOpen: boolean, + ) { + this.lower = lower; + this.upper = upper; + this.lowerOpen = lowerOpen; + this.upperOpen = upperOpen; + } + + // https://w3c.github.io/IndexedDB/#dom-idbkeyrange-includes + includes(key: Key) { + if (arguments.length === 0) { + throw new TypeError(); + } + key = valueToKey(key); + + if (this.lower !== undefined) { + const cmpResult = compareKeys(this.lower, key); + + if (cmpResult === 1 || (cmpResult === 0 && this.lowerOpen)) { + return false; + } + } + if (this.upper !== undefined) { + const cmpResult = compareKeys(this.upper, key); + + if (cmpResult === -1 || (cmpResult === 0 && this.upperOpen)) { + return false; + } + } + return true; + } + + toString() { + return "[object IDBKeyRange]"; + } + + static _valueToKeyRange(value: any, nullDisallowedFlag: boolean = false) { + if (value instanceof BridgeIDBKeyRange) { + return value; + } + + if (value === null || value === undefined) { + if (nullDisallowedFlag) { + throw new DataError(); + } + return new BridgeIDBKeyRange(undefined, undefined, false, false); + } + + const key = valueToKey(value); + + return BridgeIDBKeyRange.only(key); + } + +} + +export default BridgeIDBKeyRange; diff --git a/packages/idb-bridge/src/BridgeIDBObjectStore.ts b/packages/idb-bridge/src/BridgeIDBObjectStore.ts new file mode 100644 index 000000000..197f06d86 --- /dev/null +++ b/packages/idb-bridge/src/BridgeIDBObjectStore.ts @@ -0,0 +1,441 @@ +/* + Copyright 2017 Jeremy Scheff + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express + or implied. See the License for the specific language governing + permissions and limitations under the License. + */ + +import BridgeIDBCursor from "./BridgeIDBCursor"; +import BridgeIDBCursorWithValue from "./BridgeIDBCursorWithValue"; +import BridgeIDBIndex from "./BridgeIDBIndex"; +import BridgeIDBKeyRange from "./BridgeIDBKeyRange"; +import BridgeIDBRequest from "./BridgeIDBRequest"; +import BridgeIDBTransaction from "./BridgeIDBTransaction"; + +import { + ConstraintError, + DataError, + InvalidAccessError, + InvalidStateError, + NotFoundError, + ReadOnlyError, + TransactionInactiveError, +} from "./util/errors"; +import extractKey from "./util/extractKey"; +import fakeDOMStringList from "./util/fakeDOMStringList"; +import structuredClone from "./util/structuredClone"; +import { + FakeDOMStringList, + BridgeIDBCursorDirection, + Key, + KeyPath, + Value, +} from "./util/types"; +import validateKeyPath from "./util/validateKeyPath"; +import valueToKey from "./util/valueToKey"; +import { + DatabaseTransaction, + RecordGetRequest, + ResultLevel, +} from "./backend-interface"; + + +// http://www.w3.org/TR/2015/REC-IndexedDB-20150108/#object-store +class BridgeIDBObjectStore { + _indexesCache: Map = new Map(); + + transaction: BridgeIDBTransaction; + + get autoIncrement(): boolean { + return this._schema.objectStores[this._name].autoIncrement; + } + + get indexNames(): FakeDOMStringList { + return fakeDOMStringList(this._schema.objectStores[this._name].indexes).sort(); + } + + get keyPath(): KeyPath | null { + return this._schema.objectStores[this._name].keyPath; + } + + _name: string; + + get _schema() { + return this.transaction.db._schema; + } + + _deleted: boolean = false; + + constructor(transaction: BridgeIDBTransaction, name: string) { + this._name = name; + this.transaction = transaction; + } + + get name() { + return this._name; + } + + get _backend() { + return this.transaction.db._backend; + } + + get _backendConnection() { + return this.transaction.db._backendConnection; + } + + _confirmActiveTransaction(): { btx: DatabaseTransaction } { + const btx = this.transaction._backendTransaction; + if (!btx) { + throw new InvalidStateError(); + } + return { btx }; + } + + // http://w3c.github.io/IndexedDB/#dom-idbobjectstore-name + set name(newName: any) { + const transaction = this.transaction; + + if (!transaction.db._runningVersionchangeTransaction) { + throw new InvalidStateError(); + } + + let { btx } = this._confirmActiveTransaction(); + + + newName = String(newName); + + const oldName = this._name; + + if (newName === oldName) { + return; + } + + this._backend.renameObjectStore(btx, oldName, newName); + this.transaction.db._schema = this._backend.getSchema(this._backendConnection); + } + + public _store(value: Value, key: Key | undefined, overwrite: boolean) { + if (this.transaction.mode === "readonly") { + throw new ReadOnlyError(); + } + const operation = async () => { + const { btx } = this._confirmActiveTransaction(); + return this._backend.storeRecord(btx, { + objectStoreName: this._name, + key: key, + value: value, + overwrite, + }); + }; + + return this.transaction._execRequestAsync({ operation, source: this }); + } + + public put(value: Value, key?: Key) { + if (arguments.length === 0) { + throw new TypeError(); + } + return this._store(value, key, true); + } + + public add(value: Value, key?: Key) { + if (arguments.length === 0) { + throw new TypeError(); + } + return this._store(value, key, false); + } + + public delete(key: Key) { + if (arguments.length === 0) { + throw new TypeError(); + } + + if (this.transaction.mode === "readonly") { + throw new ReadOnlyError(); + } + + if (!(key instanceof BridgeIDBKeyRange)) { + key = valueToKey(key); + } + + const operation = async () => { + const { btx } = this._confirmActiveTransaction(); + return this._backend.deleteRecord(btx, this._name, key); + } + + return this.transaction._execRequestAsync({ + operation, + source: this, + }); + } + + public get(key?: BridgeIDBKeyRange | Key) { + if (arguments.length === 0) { + throw new TypeError(); + } + + if (!(key instanceof BridgeIDBKeyRange)) { + key = valueToKey(key); + } + + const recordRequest: RecordGetRequest = { + objectStoreName: this._name, + indexName: undefined, + lastIndexPosition: undefined, + lastObjectStorePosition: undefined, + direction: "next", + limit: 1, + resultLevel: ResultLevel.Full, + range: key, + }; + + const operation = async () => { + const { btx } = this._confirmActiveTransaction(); + const result = await this._backend.getRecords( + btx, + recordRequest, + ); + if (result.count == 0) { + return undefined; + } + const values = result.values; + if (!values) { + throw Error("invariant violated"); + } + return values[0]; + }; + + return this.transaction._execRequestAsync({ + operation, + source: this, + }); + } + + // http://w3c.github.io/IndexedDB/#dom-idbobjectstore-getall + public getAll(query?: BridgeIDBKeyRange | Key, count?: number) { + throw Error("not implemented"); + } + + // http://w3c.github.io/IndexedDB/#dom-idbobjectstore-getkey + public getKey(key?: BridgeIDBKeyRange | Key) { + throw Error("not implemented"); + } + + // http://w3c.github.io/IndexedDB/#dom-idbobjectstore-getallkeys + public getAllKeys(query?: BridgeIDBKeyRange | Key, count?: number) { + throw Error("not implemented"); + } + + public clear() { + throw Error("not implemented"); + } + + public openCursor( + range?: BridgeIDBKeyRange | Key, + direction: BridgeIDBCursorDirection = "next", + ) { + + if (range === null) { + range = undefined; + } + if (range !== undefined && !(range instanceof BridgeIDBKeyRange)) { + range = BridgeIDBKeyRange.only(valueToKey(range)); + } + + const request = new BridgeIDBRequest(); + request.source = this; + request.transaction = this.transaction; + + const cursor = new BridgeIDBCursorWithValue( + this, + this._name, + undefined, + range, + direction, + request, + ); + + return this.transaction._execRequestAsync({ + operation: () => cursor._iterate(), + request, + source: this, + }); + } + + public openKeyCursor( + range?: BridgeIDBKeyRange | Key, + direction?: BridgeIDBCursorDirection, + ) { + if (range === null) { + range = undefined; + } + if (range !== undefined && !(range instanceof BridgeIDBKeyRange)) { + range = BridgeIDBKeyRange.only(valueToKey(range)); + } + + if (!direction) { + direction = "next"; + } + + const request = new BridgeIDBRequest(); + request.source = this; + request.transaction = this.transaction; + + const cursor = new BridgeIDBCursor( + this, + this._name, + undefined, + range, + direction, + request, + true, + ); + + return this.transaction._execRequestAsync({ + operation: cursor._iterate.bind(cursor), + request, + source: this, + }); + } + + // tslint:disable-next-line max-line-length + // http://www.w3.org/TR/2015/REC-IndexedDB-20150108/#widl-IDBObjectStore-createIndex-IDBIndex-DOMString-name-DOMString-sequence-DOMString--keyPath-IDBIndexParameters-optionalParameters + public createIndex( + indexName: string, + keyPath: KeyPath, + optionalParameters: { multiEntry?: boolean; unique?: boolean } = {}, + ) { + if (arguments.length < 2) { + throw new TypeError(); + } + + if (!this.transaction.db._runningVersionchangeTransaction) { + throw new InvalidStateError(); + } + + const { btx } = this._confirmActiveTransaction(); + + const multiEntry = + optionalParameters.multiEntry !== undefined + ? optionalParameters.multiEntry + : false; + const unique = + optionalParameters.unique !== undefined + ? optionalParameters.unique + : false; + + if (this.transaction.mode !== "versionchange") { + throw new InvalidStateError(); + } + + if (this.indexNames.indexOf(indexName) >= 0) { + throw new ConstraintError(); + } + + validateKeyPath(keyPath); + + if (Array.isArray(keyPath) && multiEntry) { + throw new InvalidAccessError(); + } + + this._backend.createIndex( + btx, + indexName, + this._name, + keyPath, + multiEntry, + unique, + ); + + return new BridgeIDBIndex(this, indexName); + } + + // https://w3c.github.io/IndexedDB/#dom-idbobjectstore-index + public index(name: string) { + if (arguments.length === 0) { + throw new TypeError(); + } + + if (this.transaction._state === "finished") { + throw new InvalidStateError(); + } + + const index = this._indexesCache.get(name); + if (index !== undefined) { + return index; + } + + return new BridgeIDBIndex(this, name); + } + + public deleteIndex(name: string) { + if (arguments.length === 0) { + throw new TypeError(); + } + + if (this.transaction.mode !== "versionchange") { + throw new InvalidStateError(); + } + + if (!this.transaction.db._runningVersionchangeTransaction) { + throw new InvalidStateError(); + } + + const { btx } = this._confirmActiveTransaction(); + + const index = this._indexesCache.get(name); + if (index !== undefined) { + index._deleted = true; + } + + this._backend.deleteIndex(btx, name); + } + + // http://www.w3.org/TR/2015/REC-IndexedDB-20150108/#widl-IDBObjectStore-count-IDBRequest-any-key + public count(key?: Key | BridgeIDBKeyRange) { + + if (key === null) { + key = undefined; + } + if (key !== undefined && !(key instanceof BridgeIDBKeyRange)) { + key = BridgeIDBKeyRange.only(valueToKey(key)); + } + + const recordGetRequest: RecordGetRequest = { + direction: "next", + indexName: undefined, + lastIndexPosition: undefined, + limit: -1, + objectStoreName: this._name, + lastObjectStorePosition: undefined, + range: key, + resultLevel: ResultLevel.OnlyCount, + }; + + const operation = async () => { + const { btx } = this._confirmActiveTransaction(); + const result = await this._backend.getRecords( + btx, + recordGetRequest, + ); + return result.count; + }; + + return this.transaction._execRequestAsync({ operation, source: this }); + } + + public toString() { + return "[object IDBObjectStore]"; + } +} + +export default BridgeIDBObjectStore; diff --git a/packages/idb-bridge/src/BridgeIDBOpenDBRequest.ts b/packages/idb-bridge/src/BridgeIDBOpenDBRequest.ts new file mode 100644 index 000000000..7b636193f --- /dev/null +++ b/packages/idb-bridge/src/BridgeIDBOpenDBRequest.ts @@ -0,0 +1,36 @@ +/* + Copyright 2019 Florian Dold + Copyright 2017 Jeremy Scheff + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express + or implied. See the License for the specific language governing + permissions and limitations under the License. +*/ + +import BridgeIDBRequest from "./BridgeIDBRequest"; +import { EventCallback } from "./util/types"; + +class BridgeIDBOpenDBRequest extends BridgeIDBRequest { + public onupgradeneeded: EventCallback | null = null; + public onblocked: EventCallback | null = null; + + constructor() { + super(); + // https://www.w3.org/TR/IndexedDB/#open-requests + this.source = null; + } + + public toString() { + return "[object IDBOpenDBRequest]"; + } +} + +export default BridgeIDBOpenDBRequest; diff --git a/packages/idb-bridge/src/BridgeIDBRequest.ts b/packages/idb-bridge/src/BridgeIDBRequest.ts new file mode 100644 index 000000000..cd0092859 --- /dev/null +++ b/packages/idb-bridge/src/BridgeIDBRequest.ts @@ -0,0 +1,86 @@ +/* + * Copyright 2017 Jeremy Scheff + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express + * or implied. See the License for the specific language governing + * permissions and limitations under the License. + */ + +import BridgeFDBCursor from "./BridgeIDBCursor"; +import BridgeIDBIndex from "./BridgeIDBIndex"; +import BridgeIDBObjectStore from "./BridgeIDBObjectStore"; +import BridgeIDBTransaction from "./BridgeIDBTransaction"; +import { InvalidStateError } from "./util/errors"; +import FakeEventTarget from "./util/FakeEventTarget"; +import { EventCallback } from "./util/types"; +import FakeEvent from "./util/FakeEvent"; + +class BridgeIDBRequest extends FakeEventTarget { + _result: any = null; + _error: Error | null | undefined = null; + source: BridgeFDBCursor | BridgeIDBIndex | BridgeIDBObjectStore | null = null; + transaction: BridgeIDBTransaction | null = null; + readyState: "done" | "pending" = "pending"; + onsuccess: EventCallback | null = null; + onerror: EventCallback | null = null; + + get error() { + if (this.readyState === "pending") { + throw new InvalidStateError(); + } + return this._error; + } + + set error(value: any) { + this._error = value; + } + + get result() { + if (this.readyState === "pending") { + throw new InvalidStateError(); + } + return this._result; + } + + set result(value: any) { + this._result = value; + } + + toString() { + return "[object IDBRequest]"; + } + + _finishWithError(err: Error) { + this.result = undefined; + this.readyState = "done"; + + this.error = new Error(err.message); + this.error.name = err.name; + + const event = new FakeEvent("error", { + bubbles: true, + cancelable: true, + }); + event.eventPath = []; + this.dispatchEvent(event); + } + + _finishWithResult(result: any) { + this.result = result; + this.readyState = "done"; + + const event = new FakeEvent("success"); + event.eventPath = []; + this.dispatchEvent(event); + } +} + +export default BridgeIDBRequest; diff --git a/packages/idb-bridge/src/BridgeIDBTransaction.ts b/packages/idb-bridge/src/BridgeIDBTransaction.ts new file mode 100644 index 000000000..a7057e297 --- /dev/null +++ b/packages/idb-bridge/src/BridgeIDBTransaction.ts @@ -0,0 +1,301 @@ +import BridgeIDBDatabase from "./BridgeIDBDatabase"; +import BridgeIDBObjectStore from "./BridgeIDBObjectStore"; +import BridgeIDBRequest from "./BridgeIDBRequest"; +import { + AbortError, + InvalidStateError, + NotFoundError, + TransactionInactiveError, +} from "./util/errors"; +import fakeDOMStringList from "./util/fakeDOMStringList"; +import FakeEvent from "./util/FakeEvent"; +import FakeEventTarget from "./util/FakeEventTarget"; +import { + EventCallback, + FakeDOMStringList, + RequestObj, + TransactionMode, +} from "./util/types"; +import queueTask from "./util/queueTask"; +import openPromise from "./util/openPromise"; +import { DatabaseTransaction, Backend } from "./backend-interface"; +import { array } from "prop-types"; + +// http://www.w3.org/TR/2015/REC-IndexedDB-20150108/#transaction +class BridgeIDBTransaction extends FakeEventTarget { + public _state: "active" | "inactive" | "committing" | "finished" = "active"; + public _started = false; + public _objectStoresCache: Map = new Map(); + + public _backendTransaction?: DatabaseTransaction; + + public objectStoreNames: FakeDOMStringList; + public mode: TransactionMode; + public db: BridgeIDBDatabase; + public error: Error | null = null; + public onabort: EventCallback | null = null; + public oncomplete: EventCallback | null = null; + public onerror: EventCallback | null = null; + + private _waitPromise: Promise; + private _resolveWait: () => void; + + public _scope: Set; + private _requests: Array<{ + operation: () => void; + request: BridgeIDBRequest; + }> = []; + + get _backend(): Backend { + return this.db._backend; + } + + constructor( + storeNames: string[], + mode: TransactionMode, + db: BridgeIDBDatabase, + backendTransaction?: DatabaseTransaction, + ) { + super(); + + const myOpenPromise = openPromise(); + this._waitPromise = myOpenPromise.promise; + this._resolveWait = myOpenPromise.resolve; + + this._scope = new Set(storeNames); + this._backendTransaction = backendTransaction; + this.mode = mode; + this.db = db; + this.objectStoreNames = fakeDOMStringList(Array.from(this._scope).sort()); + + this.db._transactions.push(this); + } + + // http://www.w3.org/TR/2015/REC-IndexedDB-20150108/#dfn-steps-for-aborting-a-transaction + async _abort(errName: string | null) { + this._state = "finished"; + + if (errName !== null) { + const e = new Error(); + e.name = errName; + this.error = e; + } + + // Should this directly remove from _requests? + for (const { request } of this._requests) { + if (request.readyState !== "done") { + request.readyState = "done"; // This will cancel execution of this request's operation + if (request.source) { + request.result = undefined; + request.error = new AbortError(); + + const event = new FakeEvent("error", { + bubbles: true, + cancelable: true, + }); + event.eventPath = [this.db, this]; + request.dispatchEvent(event); + } + } + } + + // Only roll back if we actually executed the scheduled operations. + const maybeBtx = this._backendTransaction; + if (maybeBtx) { + await this._backend.rollback(maybeBtx); + } + + queueTask(() => { + const event = new FakeEvent("abort", { + bubbles: true, + cancelable: false, + }); + event.eventPath = [this.db]; + this.dispatchEvent(event); + }); + + } + + public abort() { + if (this._state === "committing" || this._state === "finished") { + throw new InvalidStateError(); + } + this._state = "active"; + + this._abort(null); + } + + // http://w3c.github.io/IndexedDB/#dom-idbtransaction-objectstore + public objectStore(name: string) { + if (this._state !== "active") { + throw new InvalidStateError(); + } + + const objectStore = this._objectStoresCache.get(name); + if (objectStore !== undefined) { + return objectStore; + } + + return new BridgeIDBObjectStore(this, name); + } + + // http://www.w3.org/TR/2015/REC-IndexedDB-20150108/#dfn-steps-for-asynchronously-executing-a-request + public _execRequestAsync(obj: RequestObj) { + const source = obj.source; + const operation = obj.operation; + let request = obj.hasOwnProperty("request") ? obj.request : null; + + if (this._state !== "active") { + throw new TransactionInactiveError(); + } + + // Request should only be passed for cursors + if (!request) { + if (!source) { + // Special requests like indexes that just need to run some code + request = new BridgeIDBRequest(); + } else { + request = new BridgeIDBRequest(); + request.source = source; + request.transaction = (source as any).transaction; + } + } + + this._requests.push({ + operation, + request, + }); + + return request; + } + + public async _start() { + this._started = true; + + if (!this._backendTransaction) { + this._backendTransaction = await this._backend.beginTransaction( + this.db._backendConnection, + Array.from(this._scope), + this.mode, + ); + } + + // Remove from request queue - cursor ones will be added back if necessary by cursor.continue and such + let operation; + let request; + while (this._requests.length > 0) { + const r = this._requests.shift(); + + // This should only be false if transaction was aborted + if (r && r.request.readyState !== "done") { + request = r.request; + operation = r.operation; + break; + } + } + + if (request && operation) { + if (!request.source) { + // Special requests like indexes that just need to run some code, with error handling already built into + // operation + await operation(); + } else { + let defaultAction; + let event; + try { + const result = await operation(); + request.readyState = "done"; + request.result = result; + request.error = undefined; + + // http://www.w3.org/TR/2015/REC-IndexedDB-20150108/#dfn-fire-a-success-event + if (this._state === "inactive") { + this._state = "active"; + } + event = new FakeEvent("success", { + bubbles: false, + cancelable: false, + }); + } catch (err) { + request.readyState = "done"; + request.result = undefined; + request.error = err; + + // http://www.w3.org/TR/2015/REC-IndexedDB-20150108/#dfn-fire-an-error-event + if (this._state === "inactive") { + this._state = "active"; + } + event = new FakeEvent("error", { + bubbles: true, + cancelable: true, + }); + + defaultAction = this._abort.bind(this, err.name); + } + + try { + event.eventPath = [this.db, this]; + request.dispatchEvent(event); + } catch (err) { + if (this._state !== "committing") { + this._abort("AbortError"); + } + throw err; + } + + // Default action of event + if (!event.canceled) { + if (defaultAction) { + defaultAction(); + } + } + } + + // On to the next one + if (this._requests.length > 0) { + this._start(); + } else { + // Give it another chance for new handlers to be set before finishing + queueTask(() => this._start()); + } + return; + } + + // Check if transaction complete event needs to be fired + if (this._state !== "finished") { + // Either aborted or committed already + this._state = "finished"; + + if (!this.error) { + const event = new FakeEvent("complete"); + this.dispatchEvent(event); + } + + const idx = this.db._transactions.indexOf(this); + if (idx < 0) { + throw Error("invariant failed"); + } + this.db._transactions.splice(idx, 1); + + this._resolveWait(); + } + } + + public commit() { + if (this._state !== "active") { + throw new InvalidStateError(); + } + + this._state = "committing"; + } + + public toString() { + return "[object IDBRequest]"; + } + + _waitDone(): Promise { + return this._waitPromise; + } +} + +export default BridgeIDBTransaction; diff --git a/packages/idb-bridge/src/BridgeIDBVersionChangeEvent.ts b/packages/idb-bridge/src/BridgeIDBVersionChangeEvent.ts new file mode 100644 index 000000000..6fc63ee35 --- /dev/null +++ b/packages/idb-bridge/src/BridgeIDBVersionChangeEvent.ts @@ -0,0 +1,41 @@ +/* + Copyright 2019 Florian Dold + Copyright 2017 Jeremy Scheff + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express + or implied. See the License for the specific language governing + permissions and limitations under the License. + */ + +import FakeEvent from "./util/FakeEvent"; + +class BridgeIDBVersionChangeEvent extends FakeEvent { + public newVersion: number | null; + public oldVersion: number; + + constructor( + type: "blocked" | "success" | "upgradeneeded" | "versionchange", + parameters: { newVersion?: number | null; oldVersion?: number } = {}, + ) { + super(type); + + this.newVersion = + parameters.newVersion !== undefined ? parameters.newVersion : null; + this.oldVersion = + parameters.oldVersion !== undefined ? parameters.oldVersion : 0; + } + + public toString() { + return "[object IDBVersionChangeEvent]"; + } +} + +export default BridgeIDBVersionChangeEvent; diff --git a/packages/idb-bridge/src/MemoryBackend.test.ts b/packages/idb-bridge/src/MemoryBackend.test.ts new file mode 100644 index 000000000..3d2d0fbc9 --- /dev/null +++ b/packages/idb-bridge/src/MemoryBackend.test.ts @@ -0,0 +1,31 @@ +import test from 'ava'; +import MemoryBackend from './MemoryBackend'; +import BridgeIDBFactory from './BridgeIDBFactory'; + +test.cb("basics", (t) => { + + const backend = new MemoryBackend(); + const idb = new BridgeIDBFactory(backend); + + const request = idb.open("library"); + request.onupgradeneeded = () => { + const db = request.result; + const store = db.createObjectStore("books", {keyPath: "isbn"}); + const titleIndex = store.createIndex("by_title", "title", {unique: true}); + const authorIndex = store.createIndex("by_author", "author"); + + // Populate with initial data. + store.put({title: "Quarry Memories", author: "Fred", isbn: 123456}); + store.put({title: "Water Buffaloes", author: "Fred", isbn: 234567}); + store.put({title: "Bedrock Nights", author: "Barney", isbn: 345678}); + }; + + request.onsuccess = () => { + t.end(); + }; + + request.onerror = () => { + t.fail(); + }; + +}); diff --git a/packages/idb-bridge/src/MemoryBackend.ts b/packages/idb-bridge/src/MemoryBackend.ts new file mode 100644 index 000000000..2d4b8ab93 --- /dev/null +++ b/packages/idb-bridge/src/MemoryBackend.ts @@ -0,0 +1,662 @@ +import { + Backend, + DatabaseConnection, + DatabaseTransaction, + Schema, + RecordStoreRequest, + IndexProperties, +} from "./backend-interface"; +import structuredClone from "./util/structuredClone"; +import { InvalidStateError, InvalidAccessError } from "./util/errors"; +import BTree, { ISortedMap, ISortedMapF } from "./tree/b+tree"; +import BridgeIDBFactory from "./BridgeIDBFactory"; +import compareKeys from "./util/cmp"; +import extractKey from "./util/extractKey"; +import { Key, Value, KeyPath } from "./util/types"; + +enum TransactionLevel { + Disconnected = 0, + Connected = 1, + Read = 2, + Write = 3, + VersionChange = 4, +} + +interface ObjectStore { + originalName: string; + modifiedName: string | undefined; + originalData: ISortedMapF; + modifiedData: ISortedMapF | undefined; + deleted: boolean; + originalKeyGenerator: number; + modifiedKeyGenerator: number | undefined; +} + +interface Index { + originalName: string; + modifiedName: string | undefined; + originalData: ISortedMapF; + modifiedData: ISortedMapF | undefined; + deleted: boolean; +} + +interface Database { + committedObjectStores: { [name: string]: ObjectStore }; + modifiedObjectStores: { [name: string]: ObjectStore }; + committedIndexes: { [name: string]: Index }; + modifiedIndexes: { [name: string]: Index }; + committedSchema: Schema; + /** + * Was the transaction deleted during the running transaction? + */ + deleted: boolean; + + txLevel: TransactionLevel; + + connectionCookie: string | undefined; +} + +interface Connection { + dbName: string; + + modifiedSchema: Schema | undefined; + + /** + * Has the underlying database been deleted? + */ + deleted: boolean; + + /** + * Map from the effective name of an object store during + * the transaction to the real name. + */ + objectStoreMap: { [currentName: string]: ObjectStore }; + indexMap: { [currentName: string]: Index }; +} + +class AsyncCondition { + wait(): Promise { + throw Error("not implemented"); + } + + trigger(): void {} +} + + + + +function insertIntoIndex( + index: Index, + value: Value, + indexProperties: IndexProperties, +) { + if (indexProperties.multiEntry) { + + } else { + const key = extractKey(value, indexProperties.keyPath); + } + throw Error("not implemented"); +} + +/** + * Primitive in-memory backend. + */ +export class MemoryBackend implements Backend { + databases: { [name: string]: Database } = {}; + + connectionIdCounter = 1; + + transactionIdCounter = 1; + + /** + * Connections by connection cookie. + */ + connections: { [name: string]: Connection } = {}; + + /** + * Connections by transaction (!!) cookie. In this implementation, + * at most one transaction can run at the same time per connection. + */ + connectionsByTransaction: { [tx: string]: Connection } = {}; + + /** + * Condition that is triggered whenever a client disconnects. + */ + disconnectCond: AsyncCondition = new AsyncCondition(); + + /** + * Conditation that is triggered whenever a transaction finishes. + */ + transactionDoneCond: AsyncCondition = new AsyncCondition(); + + async getDatabases(): Promise<{ name: string; version: number }[]> { + const dbList = []; + for (const name in this.databases) { + dbList.push({ + name, + version: this.databases[name].committedSchema.databaseVersion, + }); + } + return dbList; + } + + async deleteDatabase(tx: DatabaseTransaction, name: string): Promise { + const myConn = this.connectionsByTransaction[tx.transactionCookie]; + if (!myConn) { + throw Error("no connection associated with transaction"); + } + const myDb = this.databases[name]; + if (!myDb) { + throw Error("db not found"); + } + if (myDb.committedSchema.databaseName !== name) { + throw Error("name does not match"); + } + if (myDb.txLevel < TransactionLevel.VersionChange) { + throw new InvalidStateError(); + } + if (myDb.connectionCookie !== tx.transactionCookie) { + throw new InvalidAccessError(); + } + myDb.deleted = true; + } + + async connectDatabase(name: string): Promise { + const connectionId = this.connectionIdCounter++; + const connectionCookie = `connection-${connectionId}`; + + let database = this.databases[name]; + if (!database) { + const schema: Schema = { + databaseName: name, + indexes: {}, + databaseVersion: 0, + objectStores: {}, + }; + database = { + committedSchema: schema, + deleted: false, + modifiedIndexes: {}, + committedIndexes: {}, + committedObjectStores: {}, + modifiedObjectStores: {}, + txLevel: TransactionLevel.Disconnected, + connectionCookie: undefined, + }; + this.databases[name] = database; + } + + while (database.txLevel !== TransactionLevel.Disconnected) { + await this.disconnectCond.wait(); + } + + database.txLevel = TransactionLevel.Connected; + database.connectionCookie = connectionCookie; + + return { connectionCookie }; + } + + async beginTransaction( + conn: DatabaseConnection, + objectStores: string[], + mode: import("./util/types").TransactionMode, + ): Promise { + const transactionCookie = `tx-${this.transactionIdCounter++}`; + const myConn = this.connections[conn.connectionCookie]; + if (!myConn) { + throw Error("connection not found"); + } + const myDb = this.databases[myConn.dbName]; + if (!myDb) { + throw Error("db not found"); + } + + while (myDb.txLevel !== TransactionLevel.Connected) { + await this.transactionDoneCond.wait(); + } + + if (mode === "readonly") { + myDb.txLevel = TransactionLevel.Read; + } else if (mode === "readwrite") { + myDb.txLevel = TransactionLevel.Write; + } else { + throw Error("unsupported transaction mode"); + } + + this.connectionsByTransaction[transactionCookie] = myConn; + + return { transactionCookie }; + } + + async enterVersionChange( + conn: DatabaseConnection, + newVersion: number, + ): Promise { + const transactionCookie = `tx-vc-${this.transactionIdCounter++}`; + const myConn = this.connections[conn.connectionCookie]; + if (!myConn) { + throw Error("connection not found"); + } + const myDb = this.databases[myConn.dbName]; + if (!myDb) { + throw Error("db not found"); + } + + while (myDb.txLevel !== TransactionLevel.Connected) { + await this.transactionDoneCond.wait(); + } + + myDb.txLevel = TransactionLevel.VersionChange; + + this.connectionsByTransaction[transactionCookie] = myConn; + + return { transactionCookie }; + } + + async close(conn: DatabaseConnection): Promise { + const myConn = this.connections[conn.connectionCookie]; + if (!myConn) { + throw Error("connection not found - already closed?"); + } + if (!myConn.deleted) { + const myDb = this.databases[myConn.dbName]; + if (myDb.txLevel != TransactionLevel.Connected) { + throw Error("invalid state"); + } + myDb.txLevel = TransactionLevel.Disconnected; + } + delete this.connections[conn.connectionCookie]; + } + + getSchema(dbConn: DatabaseConnection): Schema { + const myConn = this.connections[dbConn.connectionCookie]; + if (!myConn) { + throw Error("unknown connection"); + } + const db = this.databases[myConn.dbName]; + if (!db) { + throw Error("db not found"); + } + if (myConn.modifiedSchema) { + return myConn.modifiedSchema; + } + return db.committedSchema; + } + + renameIndex( + btx: DatabaseTransaction, + oldName: string, + newName: string, + ): void { + const myConn = this.connections[btx.transactionCookie]; + if (!myConn) { + throw Error("unknown connection"); + } + const db = this.databases[myConn.dbName]; + if (!db) { + throw Error("db not found"); + } + if (db.txLevel < TransactionLevel.VersionChange) { + throw Error("only allowed in versionchange transaction"); + } + let schema = myConn.modifiedSchema; + if (!schema) { + throw Error(); + } + if (schema.indexes[newName]) { + throw new Error("new index name already used"); + } + if (!schema.indexes[oldName]) { + throw new Error("new index name already used"); + } + const index: Index = myConn.indexMap[oldName]; + if (!index) { + throw Error("old index missing in connection's index map"); + } + schema.indexes[newName] = schema.indexes[newName]; + delete schema.indexes[oldName]; + for (const storeName in schema.objectStores) { + const store = schema.objectStores[storeName]; + store.indexes = store.indexes.map(x => { + if (x == oldName) { + return newName; + } else { + return x; + } + }); + } + myConn.indexMap[newName] = index; + delete myConn.indexMap[oldName]; + index.modifiedName = newName; + } + + deleteIndex(btx: DatabaseTransaction, indexName: string): void { + const myConn = this.connections[btx.transactionCookie]; + if (!myConn) { + throw Error("unknown connection"); + } + const db = this.databases[myConn.dbName]; + if (!db) { + throw Error("db not found"); + } + if (db.txLevel < TransactionLevel.VersionChange) { + throw Error("only allowed in versionchange transaction"); + } + let schema = myConn.modifiedSchema; + if (!schema) { + throw Error(); + } + if (!schema.indexes[indexName]) { + throw new Error("index does not exist"); + } + const index: Index = myConn.indexMap[indexName]; + if (!index) { + throw Error("old index missing in connection's index map"); + } + index.deleted = true; + delete schema.indexes[indexName]; + delete myConn.indexMap[indexName]; + for (const storeName in schema.objectStores) { + const store = schema.objectStores[storeName]; + store.indexes = store.indexes.filter(x => { + return x !== indexName; + }); + } + } + + deleteObjectStore(btx: DatabaseTransaction, name: string): void { + const myConn = this.connections[btx.transactionCookie]; + if (!myConn) { + throw Error("unknown connection"); + } + const db = this.databases[myConn.dbName]; + if (!db) { + throw Error("db not found"); + } + if (db.txLevel < TransactionLevel.VersionChange) { + throw Error("only allowed in versionchange transaction"); + } + const schema = myConn.modifiedSchema; + if (!schema) { + throw Error(); + } + const objectStoreProperties = schema.objectStores[name]; + if (!objectStoreProperties) { + throw Error("object store not found"); + } + const objectStore = myConn.objectStoreMap[name]; + if (!objectStore) { + throw Error("object store not found in map"); + } + const indexNames = objectStoreProperties.indexes; + for (const indexName of indexNames) { + this.deleteIndex(btx, indexName); + } + + objectStore.deleted = true; + delete myConn.objectStoreMap[name]; + delete schema.objectStores[name]; + } + + renameObjectStore( + btx: DatabaseTransaction, + oldName: string, + newName: string, + ): void { + const myConn = this.connections[btx.transactionCookie]; + if (!myConn) { + throw Error("unknown connection"); + } + const db = this.databases[myConn.dbName]; + if (!db) { + throw Error("db not found"); + } + if (db.txLevel < TransactionLevel.VersionChange) { + throw Error("only allowed in versionchange transaction"); + } + const schema = myConn.modifiedSchema; + if (!schema) { + throw Error(); + } + if (!schema.objectStores[oldName]) { + throw Error("object store not found"); + } + if (schema.objectStores[newName]) { + throw Error("new object store already exists"); + } + const objectStore = myConn.objectStoreMap[oldName]; + if (!objectStore) { + throw Error("object store not found in map"); + } + objectStore.modifiedName = newName; + schema.objectStores[newName] = schema.objectStores[oldName]; + delete schema.objectStores[oldName]; + delete myConn.objectStoreMap[oldName]; + myConn.objectStoreMap[newName] = objectStore; + } + + createObjectStore( + btx: DatabaseTransaction, + name: string, + keyPath: string | string[] | null, + autoIncrement: boolean, + ): void { + const myConn = this.connections[btx.transactionCookie]; + if (!myConn) { + throw Error("unknown connection"); + } + const db = this.databases[myConn.dbName]; + if (!db) { + throw Error("db not found"); + } + if (db.txLevel < TransactionLevel.VersionChange) { + throw Error("only allowed in versionchange transaction"); + } + const newObjectStore: ObjectStore = { + deleted: false, + modifiedName: undefined, + originalName: name, + modifiedData: undefined, + originalData: new BTree([], compareKeys), + modifiedKeyGenerator: undefined, + originalKeyGenerator: 1, + }; + const schema = myConn.modifiedSchema; + if (!schema) { + throw Error("no schema for versionchange tx"); + } + schema.objectStores[name] = { + autoIncrement, + keyPath, + indexes: [], + }; + myConn.objectStoreMap[name] = newObjectStore; + db.modifiedObjectStores[name] = newObjectStore; + } + + createIndex( + btx: DatabaseTransaction, + indexName: string, + objectStoreName: string, + keyPath: import("./util/types").KeyPath, + multiEntry: boolean, + unique: boolean, + ): void { + const myConn = this.connections[btx.transactionCookie]; + if (!myConn) { + throw Error("unknown connection"); + } + const db = this.databases[myConn.dbName]; + if (!db) { + throw Error("db not found"); + } + if (db.txLevel < TransactionLevel.VersionChange) { + throw Error("only allowed in versionchange transaction"); + } + const indexProperties: IndexProperties = { + keyPath, + multiEntry, + unique, + }; + const newIndex: Index = { + deleted: false, + modifiedData: undefined, + modifiedName: undefined, + originalData: new BTree([], compareKeys), + originalName: indexName, + }; + myConn.indexMap[indexName] = newIndex; + db.modifiedIndexes[indexName] = newIndex; + const schema = myConn.modifiedSchema; + if (!schema) { + throw Error("no schema in versionchange tx"); + } + const objectStoreProperties = schema.objectStores[objectStoreName]; + if (!objectStoreProperties) { + throw Error("object store not found"); + } + objectStoreProperties.indexes.push(indexName); + schema.indexes[indexName] = indexProperties; + + // FIXME: build index from existing object store! + } + + async deleteRecord( + btx: DatabaseTransaction, + objectStoreName: string, + range: import("./BridgeIDBKeyRange").default, + ): Promise { + const myConn = this.connections[btx.transactionCookie]; + if (!myConn) { + throw Error("unknown connection"); + } + const db = this.databases[myConn.dbName]; + if (!db) { + throw Error("db not found"); + } + if (db.txLevel < TransactionLevel.Write) { + throw Error("only allowed in write transaction"); + } + } + + async getRecords( + btx: DatabaseTransaction, + req: import("./backend-interface").RecordGetRequest, + ): Promise { + const myConn = this.connections[btx.transactionCookie]; + if (!myConn) { + throw Error("unknown connection"); + } + const db = this.databases[myConn.dbName]; + if (!db) { + throw Error("db not found"); + } + if (db.txLevel < TransactionLevel.Write) { + throw Error("only allowed while running a transaction"); + } + throw Error("not implemented"); + } + + async storeRecord( + btx: DatabaseTransaction, + storeReq: RecordStoreRequest, + ): Promise { + const myConn = this.connections[btx.transactionCookie]; + if (!myConn) { + throw Error("unknown connection"); + } + const db = this.databases[myConn.dbName]; + if (!db) { + throw Error("db not found"); + } + if (db.txLevel < TransactionLevel.Write) { + throw Error("only allowed while running a transaction"); + } + const schema = myConn.modifiedSchema + ? myConn.modifiedSchema + : db.committedSchema; + + const objectStore = myConn.objectStoreMap[storeReq.objectStoreName]; + + const storeKeyResult: StoreKeyResult = getStoreKey( + storeReq.value, + storeReq.key, + objectStore.modifiedKeyGenerator || objectStore.originalKeyGenerator, + schema.objectStores[storeReq.objectStoreName].autoIncrement, + schema.objectStores[storeReq.objectStoreName].keyPath, + ); + let key = storeKeyResult.key; + let value = storeKeyResult.value; + objectStore.modifiedKeyGenerator = storeKeyResult.updatedKeyGenerator; + + if (!objectStore.modifiedData) { + objectStore.modifiedData = objectStore.originalData; + } + const modifiedData = objectStore.modifiedData; + const hasKey = modifiedData.has(key); + if (hasKey && !storeReq.overwrite) { + throw Error("refusing to overwrite"); + } + + objectStore.modifiedData = modifiedData.with(key, value, true); + + for (const indexName of schema.objectStores[storeReq.objectStoreName] + .indexes) { + const index = myConn.indexMap[indexName]; + if (!index) { + throw Error("index referenced by object store does not exist"); + } + const indexProperties = schema.indexes[indexName]; + insertIntoIndex(index, value, indexProperties); + } + } + + async rollback(btx: DatabaseTransaction): Promise { + const myConn = this.connections[btx.transactionCookie]; + if (!myConn) { + throw Error("unknown connection"); + } + const db = this.databases[myConn.dbName]; + if (!db) { + throw Error("db not found"); + } + if (db.txLevel < TransactionLevel.Read) { + throw Error("only allowed while running a transaction"); + } + db.modifiedIndexes = {}; + db.modifiedObjectStores = {}; + db.txLevel = TransactionLevel.Connected; + myConn.modifiedSchema = structuredClone(db.committedSchema); + myConn.indexMap = Object.assign({}, db.committedIndexes); + myConn.objectStoreMap = Object.assign({}, db.committedObjectStores); + for (const indexName in db.committedIndexes) { + const index = db.committedIndexes[indexName]; + index.deleted = false; + index.modifiedData = undefined; + index.modifiedName = undefined; + } + for (const objectStoreName in db.committedObjectStores) { + const objectStore = db.committedObjectStores[objectStoreName]; + objectStore.deleted = false; + objectStore.modifiedData = undefined; + objectStore.modifiedName = undefined; + objectStore.modifiedKeyGenerator = undefined; + } + } + + async commit(btx: DatabaseTransaction): Promise { + const myConn = this.connections[btx.transactionCookie]; + if (!myConn) { + throw Error("unknown connection"); + } + const db = this.databases[myConn.dbName]; + if (!db) { + throw Error("db not found"); + } + if (db.txLevel < TransactionLevel.Read) { + throw Error("only allowed while running a transaction"); + } + } +} + +export default MemoryBackend; diff --git a/packages/idb-bridge/src/backend-interface.ts b/packages/idb-bridge/src/backend-interface.ts new file mode 100644 index 000000000..c0f498a10 --- /dev/null +++ b/packages/idb-bridge/src/backend-interface.ts @@ -0,0 +1,145 @@ +import { + TransactionMode, + Value, + BridgeIDBCursorDirection, + Key, + KeyPath, + BridgeIDBDatabaseInfo, +} from "./util/types"; +import BridgeIDBKeyRange from "./BridgeIDBKeyRange"; + +export interface ObjectStoreProperties { + keyPath: KeyPath | null; + autoIncrement: boolean; + indexes: string[]; +} + +export interface IndexProperties { + keyPath: KeyPath; + multiEntry: boolean; + unique: boolean; +} + +export interface Schema { + databaseName: string; + databaseVersion: number; + objectStores: { [name: string]: ObjectStoreProperties }; + indexes: { [name: string]: IndexProperties }; +} + +export interface DatabaseConnection { + connectionCookie: string; +} + +export interface DatabaseTransaction { + transactionCookie: string; +} + +export enum ResultLevel { + Full, + OnlyKeys, + OnlyCount, +} + +export interface RecordGetRequest { + direction: BridgeIDBCursorDirection; + objectStoreName: string; + indexName: string | undefined; + range: BridgeIDBKeyRange | undefined; + lastIndexPosition?: Key; + lastObjectStorePosition?: Key; + advanceIndexKey?: Key; + advancePrimaryKey?: Key; + limit: number; + resultLevel: ResultLevel; +} + +export interface RecordGetResponse { + values: Value[] | undefined; + keys: Key[] | undefined; + primaryKeys: Key[] | undefined; + count: number; +} + +export interface RecordStoreRequest { + objectStoreName: string; + value: Value; + key: Key | undefined; + overwrite: boolean; +} + +export interface Backend { + getDatabases(): Promise; + + connectDatabase(name: string): Promise; + + beginTransaction( + conn: DatabaseConnection, + objectStores: string[], + mode: TransactionMode, + ): Promise; + + enterVersionChange( + conn: DatabaseConnection, + newVersion: number, + ): Promise; + + /** + * Even though the standard interface for indexedDB doesn't require + * the client to run deleteDatabase in a version transaction, there is + * implicitly one running. + */ + deleteDatabase(btx: DatabaseTransaction, name: string): Promise; + + close(db: DatabaseConnection): Promise; + + getSchema(db: DatabaseConnection): Schema; + + renameIndex(btx: DatabaseTransaction, oldName: string, newName: string): void; + + deleteIndex(btx: DatabaseTransaction, indexName: string): void; + + rollback(btx: DatabaseTransaction): Promise; + + commit(btx: DatabaseTransaction): Promise; + + deleteObjectStore(btx: DatabaseTransaction, name: string): void; + + createObjectStore( + btx: DatabaseTransaction, + name: string, + keyPath: string | string[] | null, + autoIncrement: boolean, + ): void; + + renameObjectStore( + btx: DatabaseTransaction, + oldName: string, + newName: string, + ): void; + + createIndex( + btx: DatabaseTransaction, + indexName: string, + objectStoreName: string, + keyPath: KeyPath, + multiEntry: boolean, + unique: boolean, + ): void; + + deleteRecord( + btx: DatabaseTransaction, + objectStoreName: string, + range: BridgeIDBKeyRange, + ): Promise; + + getRecords( + btx: DatabaseTransaction, + req: RecordGetRequest, + ): Promise; + + storeRecord( + btx: DatabaseTransaction, + storeReq: RecordStoreRequest, + ): Promise; +} diff --git a/packages/idb-bridge/src/tree/b+tree.ts b/packages/idb-bridge/src/tree/b+tree.ts new file mode 100644 index 000000000..01187cdc2 --- /dev/null +++ b/packages/idb-bridge/src/tree/b+tree.ts @@ -0,0 +1,1351 @@ +/* +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 + + +import { ISortedMap, ISortedMapF } from './interfaces'; +export { + ISetSource, ISetSink, ISet, ISetF, ISortedSetSource, ISortedSet, ISortedSetF, + IMapSource, IMapSink, IMap, IMapF, ISortedMapSource, ISortedMap, ISortedMapF +} from './interfaces'; + +export type EditRangeResult = {value?:V, break?:R, delete?:boolean}; + +type index = number; + +// Informative microbenchmarks & stuff: +// http://www.jayconrod.com/posts/52/a-tour-of-v8-object-representation (very educational) +// https://blog.mozilla.org/luke/2012/10/02/optimizing-javascript-variable-access/ (local vars are faster than properties) +// http://benediktmeurer.de/2017/12/13/an-introduction-to-speculative-optimization-in-v8/ (other stuff) +// https://jsperf.com/js-in-operator-vs-alternatives (avoid 'in' operator; `.p!==undefined` faster than `hasOwnProperty('p')` in all browsers) +// https://jsperf.com/instanceof-vs-typeof-vs-constructor-vs-member (speed of type tests varies wildly across browsers) +// https://jsperf.com/detecting-arrays-new (a.constructor===Array is best across browsers, assuming a is an object) +// https://jsperf.com/shallow-cloning-methods (a constructor is faster than Object.create; hand-written clone faster than Object.assign) +// https://jsperf.com/ways-to-fill-an-array (slice-and-replace is fastest) +// https://jsperf.com/math-min-max-vs-ternary-vs-if (Math.min/max is slow on Edge) +// https://jsperf.com/array-vs-property-access-speed (v.x/v.y is faster than a[0]/a[1] in major browsers IF hidden class is constant) +// https://jsperf.com/detect-not-null-or-undefined (`x==null` slightly slower than `x===null||x===undefined` on all browsers) +// Overall, microbenchmarks suggest Firefox is the fastest browser for JavaScript and Edge is the slowest. +// Lessons from https://v8project.blogspot.com/2017/09/elements-kinds-in-v8.html: +// - Avoid holes in arrays. Avoid `new Array(N)`, it will be "holey" permanently. +// - Don't read outside bounds of an array (it scans prototype chain). +// - Small integer arrays are stored differently from doubles +// - Adding non-numbers to an array deoptimizes it permanently into a general array +// - Objects can be used like arrays (e.g. have length property) but are slower +// - V8 source (NewElementsCapacity in src/objects.h): arrays grow by 50% + 16 elements + +/** 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 ? 1 : a == b ? 0 : c; +}; + +/** + * A reasonably fast collection of key-value pairs with a powerful API. + * Largely compatible with the standard Map. BTree is a B+ tree data structure, + * so the collection is sorted by key. + * + * B+ trees tend to use memory more efficiently than hashtables such as the + * standard Map, especially when the collection contains a large number of + * items. However, maintaining the sort order makes them modestly slower: + * O(log size) rather than O(1). This B+ tree implementation supports O(1) + * fast cloning. It also supports freeze(), which can be used to ensure that + * a BTree is not changed accidentally. + * + * Confusingly, the ES6 Map.forEach(c) method calls c(value,key) instead of + * c(key,value), in contrast to other methods such as set() and entries() + * which put the key first. I can only assume that the order was reversed on + * the theory that users would usually want to examine values and ignore keys. + * BTree's forEach() therefore works the same way, but a second method + * `.forEachPair((key,value)=>{...})` is provided which sends you the key + * first and the value second; this method is slightly faster because it is + * the "native" for-each method for this class. + * + * Out of the box, BTree supports keys that are numbers, strings, arrays of + * numbers/strings, Date, and objects that have a valueOf() method returning a + * number or string. Other data types, such as arrays of Date or custom + * objects, require a custom comparator, which you must pass as the second + * argument to the constructor (the first argument is an optional list of + * initial items). Symbols cannot be used as keys because they are unordered + * (one Symbol is never "greater" or "less" than another). + * + * @example + * Given a {name: string, age: number} object, you can create a tree sorted by + * name and then by age like this: + * + * var tree = new BTree(undefined, (a, b) => { + * if (a.name > b.name) + * return 1; // Return a number >0 when a > b + * else if (a.name < b.name) + * return -1; // Return a number <0 when a < b + * else // names are equal (or incomparable) + * return a.age - b.age; // Return >0 when a.age > b.age + * }); + * + * tree.set({name:"Bill", age:17}, "happy"); + * tree.set({name:"Fran", age:40}, "busy & stressed"); + * tree.set({name:"Bill", age:55}, "recently laid off"); + * tree.forEachPair((k, v) => { + * console.log(`Name: ${k.name} Age: ${k.age} Status: ${v}`); + * }); + * + * @description + * The "range" methods (`forEach, forRange, editRange`) will return the number + * of elements that were scanned. In addition, the callback can return {break:R} + * to stop early and return R from the outer function. + * + * - TODO: Test performance of preallocating values array at max size + * - TODO: Add fast initialization when a sorted array is provided to constructor + * + * For more documentation see https://github.com/qwertie/btree-typescript + * + * Are you a C# developer? You might like the similar data structures I made for C#: + * BDictionary, BList, etc. See http://core.loyc.net/collections/ + * + * @author David Piepgrass + */ +export default class BTree implements ISortedMapF, ISortedMap +{ + private _root: BNode = EmptyLeaf as BNode; + _size: number = 0; + _maxNodeSize: number; + _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. + * @param entries A set of key-value pairs to initialize the tree + * @param maxNodeSize Branching factor (maximum items or children per node) + * Must be in range 4..256. If undefined or <4 then default is used; if >256 then 256. + */ + public constructor(entries?: [K,V][], compare?: (a: K, b: K) => number, maxNodeSize?: number) { + this._maxNodeSize = maxNodeSize! >= 4 ? Math.min(maxNodeSize!, 256) : 32; + this._compare = compare || defaultComparator; + if (entries) + this.setPairs(entries); + } + + // ES6 Map methods /////////////////////////////////////////////////// + + /** Gets the number of key-value pairs in the tree. */ + get size() { return this._size; } + /** Gets the number of key-value pairs in the tree. */ + get length() { return this._size; } + /** Returns true iff the tree contains no key-value pairs. */ + get isEmpty() { return this._size === 0; } + + /** Releases the tree so that its size is 0. */ + clear() { + this._root = EmptyLeaf as BNode; + this._size = 0; + } + + forEach(callback: (v:V, k:K, tree:BTree) => void, thisArg?: any): number; + + /** Runs a function for each key-value pair, in order from smallest to + * largest key. For compatibility with ES6 Map, the argument order to + * the callback is backwards: value first, then key. Call forEachPair + * instead to receive the key as the first argument. + * @param thisArg If provided, this parameter is assigned as the `this` + * value for each callback. + * @returns the number of values that were sent to the callback, + * or the R value if the callback returned {break:R}. */ + forEach(callback: (v:V, k:K, tree:BTree) => {break?:R}|void, thisArg?: any): R|number { + if (thisArg !== undefined) + callback = callback.bind(thisArg); + return this.forEachPair((k, v) => callback(v, k, this)); + } + + /** Runs a function for each key-value pair, in order from smallest to + * largest key. The callback can return {break:R} (where R is any value + * except undefined) to stop immediately and return R from forEachPair. + * @param onFound A function that is called for each key-value pair. This + * function can return {break:R} to stop early with result R. + * The reason that you must return {break:R} instead of simply R + * itself is for consistency with editRange(), which allows + * multiple actions, not just breaking. + * @param initialCounter This is the value of the third argument of + * `onFound` the first time it is called. The counter increases + * by one each time `onFound` is called. Default value: 0 + * @returns the number of pairs sent to the callback (plus initialCounter, + * if you provided one). If the callback returned {break:R} then + * the R value is returned instead. */ + forEachPair(callback: (k:K, v:V, counter:number) => {break?:R}|void, initialCounter?: number): R|number { + var low = this.minKey(), high = this.maxKey(); + return this.forRange(low!, high!, true, callback, initialCounter); + } + + /** + * Finds a pair in the tree and returns the associated value. + * @param defaultValue a value to return if the key was not found. + * @returns the value, or defaultValue if the key was not found. + * @description Computational complexity: O(log size) + */ + get(key: K, defaultValue?: V): V | undefined { + return this._root.get(key, defaultValue, this); + } + + /** + * Adds or overwrites a key-value pair in the B+ tree. + * @param key the key is used to determine the sort order of + * data in the tree. + * @param value data to associate with the key (optional) + * @param overwrite Whether to overwrite an existing key-value pair + * (default: true). If this is false and there is an existing + * key-value pair then this method has no effect. + * @returns true if a new key-value pair was added. + * @description Computational complexity: O(log size) + * Note: when overwriting a previous entry, the key is updated + * as well as the value. This has no effect unless the new key + * has data that does not affect its sort order. + */ + set(key: K, value: V, overwrite?: boolean): boolean { + if (this._root.isShared) + this._root = this._root.clone(); + var result = this._root.set(key, value, overwrite, this); + if (result === true || result === false) + return result; + // Root node has split, so create a new root node. + this._root = new BNodeInternal([this._root, result]); + return true; + } + + /** + * Returns true if the key exists in the B+ tree, false if not. + * Use get() for best performance; use has() if you need to + * distinguish between "undefined value" and "key not present". + * @param key Key to detect + * @description Computational complexity: O(log size) + */ + has(key: K): boolean { + return this.forRange(key, key, true, undefined) !== 0; + } + + /** + * Removes a single key-value pair from the B+ tree. + * @param key Key to find + * @returns true if a pair was found and removed, false otherwise. + * @description Computational complexity: O(log size) + */ + delete(key: K): boolean { + return this.editRange(key, key, true, DeleteRange) !== 0; + } + + // Clone-mutators ///////////////////////////////////////////////////////// + + /** Returns a copy of the tree with the specified key set (the value is undefined). */ + with(key: K): BTree; + /** Returns a copy of the tree with the specified key-value pair set. */ + with(key: K, value: V2, overwrite?: boolean): BTree; + with(key: K, value?: V2, overwrite?: boolean): BTree { + let nu = this.clone() as BTree; + return nu.set(key, value, overwrite) || overwrite ? nu : this; + } + + /** Returns a copy of the tree with the specified key-value pairs set. */ + withPairs(pairs: [K,V|V2][], overwrite: boolean): BTree { + let nu = this.clone() as BTree; + return nu.setPairs(pairs, overwrite) !== 0 || overwrite ? nu : this; + } + + /** Returns a copy of the tree with the specified keys present. + * @param keys The keys to add. If a key is already present in the tree, + * neither the existing key nor the existing value is modified. + * @param returnThisIfUnchanged if true, returns this if all keys already + * existed. Performance note: due to the architecture of this class, all + * node(s) leading to existing keys are cloned even if the collection is + * ultimately unchanged. + */ + withKeys(keys: K[], returnThisIfUnchanged?: boolean): BTree { + let nu = this.clone() as BTree, changed = false; + for (var i = 0; i < keys.length; i++) + changed = nu.set(keys[i], undefined, false) || changed; + return returnThisIfUnchanged && !changed ? this : nu; + } + + /** Returns a copy of the tree with the specified key removed. + * @param returnThisIfUnchanged if true, returns this if the key didn't exist. + * Performance note: due to the architecture of this class, node(s) leading + * to where the key would have been stored are cloned even when the key + * turns out not to exist and the collection is unchanged. + */ + without(key: K, returnThisIfUnchanged?: boolean): BTree { + return this.withoutRange(key, key, true, returnThisIfUnchanged); + } + + /** Returns a copy of the tree with the specified keys removed. + * @param returnThisIfUnchanged if true, returns this if none of the keys + * existed. Performance note: due to the architecture of this class, + * node(s) leading to where the key would have been stored are cloned + * even when the key turns out not to exist. + */ + withoutKeys(keys: K[], returnThisIfUnchanged?: boolean): BTree { + let nu = this.clone(); + return nu.deleteKeys(keys) || !returnThisIfUnchanged ? nu : this; + } + + /** Returns a copy of the tree with the specified range of keys removed. */ + withoutRange(low: K, high: K, includeHigh: boolean, returnThisIfUnchanged?: boolean): BTree { + let nu = this.clone(); + if (nu.deleteRange(low, high, includeHigh) === 0 && returnThisIfUnchanged) + return this; + return nu; + } + + /** Returns a copy of the tree with pairs removed whenever the callback + * function returns false. `where()` is a synonym for this method. */ + filter(callback: (k:K,v:V,counter:number) => boolean, returnThisIfUnchanged?: boolean): BTree { + var nu = this.greedyClone(); + var del: any; + nu.editAll((k,v,i) => { + if (!callback(k, v, i)) return del = Delete; + }); + if (!del && returnThisIfUnchanged) + return this; + return nu; + } + + /** Returns a copy of the tree with all values altered by a callback function. */ + mapValues(callback: (v:V,k:K,counter:number) => R): BTree { + var tmp = {} as {value:R}; + var nu = this.greedyClone(); + nu.editAll((k,v,i) => { + return tmp.value = callback(v, k, i), tmp as any; + }); + return nu as any as BTree; + } + + /** Performs a reduce operation like the `reduce` method of `Array`. + * It is used to combine all pairs into a single value, or perform + * conversions. `reduce` is best understood by example. For example, + * `tree.reduce((P, pair) => P * pair[0], 1)` multiplies all keys + * together. It means "start with P=1, and for each pair multiply + * it by the key in pair[0]". Another example would be converting + * the tree to a Map (in this example, note that M.set returns M): + * + * var M = tree.reduce((M, pair) => M.set(pair[0],pair[1]), new Map()) + * + * **Note**: the same array is sent to the callback on every iteration. + */ + reduce(callback: (previous:R,currentPair:[K,V],counter:number,tree:BTree) => R, initialValue: R): R; + reduce(callback: (previous:R|undefined,currentPair:[K,V],counter:number,tree:BTree) => R): R|undefined; + reduce(callback: (previous:R|undefined,currentPair:[K,V],counter:number,tree:BTree) => R, initialValue?: R): R|undefined { + let i = 0, p = initialValue; + var it = this.entries(this.minKey(), ReusedArray), next; + while (!(next = it.next()).done) + p = callback(p, next.value, i++, this); + return p; + } + + // Iterator methods /////////////////////////////////////////////////////// + + /** Returns an iterator that provides items in order (ascending order if + * the collection's comparator uses ascending order, as is the default.) + * @param lowestKey First key to be iterated, or undefined to start at + * minKey(). If the specified key doesn't exist then iteration + * starts at the next higher key (according to the comparator). + * @param reusedArray Optional array used repeatedly to store key-value + * pairs, to avoid creating a new array on every iteration. + */ + entries(lowestKey?: K, reusedArray?: (K|V)[]): IterableIterator<[K,V]> { + var info = this.findPath(lowestKey); + if (info === undefined) return iterator<[K,V]>(); + var {nodequeue, nodeindex, leaf} = info; + var state = reusedArray !== undefined ? 1 : 0; + var i = (lowestKey === undefined ? -1 : leaf.indexOf(lowestKey, 0, this._compare) - 1); + + return iterator<[K,V]>(() => { + jump: for (;;) { + switch(state) { + case 0: + if (++i < leaf.keys.length) + return {done: false, value: [leaf.keys[i], leaf.values[i]]}; + state = 2; + continue; + case 1: + if (++i < leaf.keys.length) { + reusedArray![0] = leaf.keys[i], reusedArray![1] = leaf.values[i]; + return {done: false, value: reusedArray as [K,V]}; + } + state = 2; + case 2: + // Advance to the next leaf node + for (var level = -1;;) { + if (++level >= nodequeue.length) { + state = 3; continue jump; + } + if (++nodeindex[level] < nodequeue[level].length) + break; + } + for (; level > 0; level--) { + nodequeue[level-1] = (nodequeue[level][nodeindex[level]] as BNodeInternal).children; + nodeindex[level-1] = 0; + } + leaf = nodequeue[0][nodeindex[0]]; + i = -1; + state = reusedArray !== undefined ? 1 : 0; + continue; + case 3: + return {done: true, value: undefined}; + } + } + }); + } + + /** Returns an iterator that provides items in reversed order. + * @param highestKey Key at which to start iterating, or undefined to + * start at minKey(). If the specified key doesn't exist then iteration + * starts at the next lower key (according to the comparator). + * @param reusedArray Optional array used repeatedly to store key-value + * pairs, to avoid creating a new array on every iteration. + * @param skipHighest Iff this flag is true and the highestKey exists in the + * collection, the pair matching highestKey is skipped, not iterated. + */ + entriesReversed(highestKey?: K, reusedArray?: (K|V)[], skipHighest?: boolean): IterableIterator<[K,V]> { + if ((highestKey = highestKey || this.maxKey()) === 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++; + var state = reusedArray !== undefined ? 1 : 0; + + return iterator<[K,V]>(() => { + jump: for (;;) { + switch(state) { + case 0: + if (--i >= 0) + return {done: false, value: [leaf.keys[i], leaf.values[i]]}; + state = 2; + continue; + case 1: + if (--i >= 0) { + reusedArray![0] = leaf.keys[i], reusedArray![1] = leaf.values[i]; + return {done: false, value: reusedArray as [K,V]}; + } + state = 2; + case 2: + // Advance to the next leaf node + for (var level = -1;;) { + if (++level >= nodequeue.length) { + state = 3; continue jump; + } + if (--nodeindex[level] >= 0) + break; + } + for (; level > 0; level--) { + nodequeue[level-1] = (nodequeue[level][nodeindex[level]] as BNodeInternal).children; + nodeindex[level-1] = nodequeue[level-1].length-1; + } + leaf = nodequeue[0][nodeindex[0]]; + i = leaf.keys.length; + state = reusedArray !== undefined ? 1 : 0; + continue; + case 3: + return {done: true, value: undefined}; + } + } + }); + } + + /* Used by entries() and entriesReversed() to prepare to start iterating. + * It develops a "node queue" for each non-leaf level of the tree. + * Levels are numbered "bottom-up" so that level 0 is a list of leaf + * nodes from a low-level non-leaf node. The queue at a given level L + * consists of nodequeue[L] which is the children of a BNodeInternal, + * and nodeindex[L], the current index within that child list, such + * such that nodequeue[L-1] === nodequeue[L][nodeindex[L]].children. + * (However inside this function the order is reversed.) + */ + private findPath(key?: K): { nodequeue: BNode[][], nodeindex: number[], leaf: BNode } | undefined + { + var nextnode = this._root; + var nodequeue: BNode[][], nodeindex: number[]; + + if (nextnode.isLeaf) { + nodequeue = EmptyArray, nodeindex = EmptyArray; // avoid allocations + } else { + nodequeue = [], nodeindex = []; + for (var d = 0; !nextnode.isLeaf; d++) { + nodequeue[d] = (nextnode as BNodeInternal).children; + nodeindex[d] = key === undefined ? 0 : nextnode.indexOf(key, 0, this._compare); + if (nodeindex[d] >= nodequeue[d].length) + return; // first key > maxKey() + nextnode = nodequeue[d][nodeindex[d]]; + } + nodequeue.reverse(); + nodeindex.reverse(); + } + return {nodequeue, nodeindex, leaf:nextnode}; + } + + /** 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 { + var it = this.entries(firstKey, ReusedArray); + return iterator(() => { + var n: IteratorResult = it.next(); + if (n.value) n.value = n.value[0]; + return n; + }); + } + + /** Returns a new iterator for iterating the values of each pair in order by key. + * @param firstKey: Minimum key whose associated value is included in the output. */ + values(firstKey?: K): IterableIterator { + var it = this.entries(firstKey, ReusedArray); + return iterator(() => { + var n: IteratorResult = it.next(); + if (n.value) n.value = n.value[1]; + return n; + }); + } + + // Additional methods ///////////////////////////////////////////////////// + + /** Returns the maximum number of children/values before nodes will split. */ + get maxNodeSize() { + return this._maxNodeSize; + } + + /** Gets the lowest key in the tree. Complexity: O(log size) */ + minKey(): K | undefined { return this._root.minKey(); } + + /** Gets the highest key in the tree. Complexity: O(1) */ + maxKey(): K | undefined { return this._root.maxKey(); } + + /** Quickly clones the tree by marking the root node as shared. + * Both copies remain editable. When you modify either copy, any + * nodes that are shared (or potentially shared) between the two + * copies are cloned so that the changes do not affect other copies. + * This is known as copy-on-write behavior, or "lazy copying". */ + clone(): BTree { + this._root.isShared = true; + var result = new BTree(undefined, this._compare, this._maxNodeSize); + result._root = this._root; + result._size = this._size; + return result; + } + + /** Performs a greedy clone, immediately duplicating any nodes that are + * not currently marked as shared, in order to avoid marking any nodes + * as shared. + * @param force Clone all nodes, even shared ones. + */ + greedyClone(force?: boolean): BTree { + var result = new BTree(undefined, this._compare, this._maxNodeSize); + result._root = this._root.greedyClone(force); + result._size = this._size; + return result; + } + + /** Gets an array filled with the contents of the tree, sorted by key */ + toArray(maxLength: number = 0x7FFFFFFF): [K,V][] { + let min = this.minKey(), max = this.maxKey(); + if (min !== undefined) + return this.getRange(min, max!, true, maxLength) + return []; + } + + /** Gets an array of all keys, sorted */ + keysArray() { + var results: K[] = []; + this._root.forRange(this.minKey()!, this.maxKey()!, true, false, this, 0, + (k,v) => { results.push(k); }); + return results; + } + + /** Gets an array of all values, sorted by key */ + valuesArray() { + var results: V[] = []; + this._root.forRange(this.minKey()!, this.maxKey()!, true, false, this, 0, + (k,v) => { results.push(v); }); + return results; + } + + /** Gets a string representing the tree's data based on toArray(). */ + toString() { + return this.toArray().toString(); + } + + /** Stores a key-value pair only if the key doesn't already exist in the tree. + * @returns true if a new key was added + */ + setIfNotPresent(key: K, value: V): boolean { + return this.set(key, value, false); + } + + /** Returns the next pair whose key is larger than the specified key (or undefined if there is none) */ + 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 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 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 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; + } + + /** Edits the value associated with a key in the tree, if it already exists. + * @returns true if the key existed, false if not. + */ + changeIfPresent(key: K, value: V): boolean { + return this.editRange(key, key, true, (k,v) => ({value})) !== 0; + } + + /** + * Builds an array of pairs from the specified range of keys, sorted by key. + * Each returned pair is also an array: pair[0] is the key, pair[1] is the value. + * @param low The first key in the array will be greater than or equal to `low`. + * @param high This method returns when a key larger than this is reached. + * @param includeHigh If the `high` key is present, its pair will be included + * in the output if and only if this parameter is true. Note: if the + * `low` key is present, it is always included in the output. + * @param maxLength Length limit. getRange will stop scanning the tree when + * the array reaches this size. + * @description Computational complexity: O(result.length + log size) + */ + getRange(low: K, high: K, includeHigh?: boolean, maxLength: number = 0x3FFFFFF): [K,V][] { + var results: [K,V][] = []; + this._root.forRange(low, high, includeHigh, false, this, 0, (k,v) => { + results.push([k,v]) + return results.length > maxLength ? Break : undefined; + }); + return results; + } + + /** Adds all pairs from a list of key-value pairs. + * @param pairs Pairs to add to this tree. If there are duplicate keys, + * later pairs currently overwrite earlier ones (e.g. [[0,1],[0,7]] + * associates 0 with 7.) + * @param overwrite Whether to overwrite pairs that already exist (if false, + * pairs[i] is ignored when the key pairs[i][0] already exists.) + * @returns The number of pairs added to the collection. + * @description Computational complexity: O(pairs.length * log(size + pairs.length)) + */ + setPairs(pairs: [K,V][], overwrite?: boolean): number { + var added = 0; + for (var i = 0; i < pairs.length; i++) + if (this.set(pairs[i][0], pairs[i][1], overwrite)) + added++; + return added; + } + + forRange(low: K, high: K, includeHigh: boolean, onFound?: (k:K,v:V,counter:number) => void, initialCounter?: number): number; + + /** + * Scans the specified range of keys, in ascending order by key. + * Note: the callback `onFound` must not insert or remove items in the + * collection. Doing so may cause incorrect data to be sent to the + * callback afterward. + * @param low The first key scanned will be greater than or equal to `low`. + * @param high Scanning stops when a key larger than this is reached. + * @param includeHigh If the `high` key is present, `onFound` is called for + * that final pair if and only if this parameter is true. + * @param onFound A function that is called for each key-value pair. This + * function can return {break:R} to stop early with result R. + * @param initialCounter Initial third argument of onFound. This value + * increases by one each time `onFound` is called. Default: 0 + * @returns The number of values found, or R if the callback returned + * `{break:R}` to stop early. + * @description Computational complexity: O(number of items scanned + log size) + */ + forRange(low: K, high: K, includeHigh: boolean, onFound?: (k:K,v:V,counter:number) => {break?:R}|void, initialCounter?: number): R|number { + var r = this._root.forRange(low, high, includeHigh, false, this, initialCounter || 0, onFound); + return typeof r === "number" ? r : r.break!; + } + + /** + * Scans and potentially modifies values for a subsequence of keys. + * Note: the callback `onFound` should ideally be a pure function. + * 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 + * clone() of the collection, otherwise the clone could be modified + * by changes requested by the callback. + * @param low The first key scanned will be greater than or equal to `low`. + * @param high Scanning stops when a key larger than this is reached. + * @param includeHigh If the `high` key is present, `onFound` is called for + * that final pair if and only if this parameter is true. + * @param onFound A function that is called for each key-value pair. This + * function can return `{value:v}` to change the value associated + * with the current key, `{delete:true}` to delete the current pair, + * `{break:R}` to stop early with result R, or it can return nothing + * (undefined or {}) to cause no effect and continue iterating. + * `{break:R}` can be combined with one of the other two commands. + * The third argument `counter` is the number of items iterated + * previously; it equals 0 when `onFound` is called the first time. + * @returns The number of values scanned, or R if the callback returned + * `{break:R}` to stop early. + * @description + * Computational complexity: O(number of items scanned + log size) + * Note: if the tree has been cloned with clone(), any shared + * nodes are copied before `onFound` is called. This takes O(n) time + * where n is proportional to the amount of shared data scanned. + */ + editRange(low: K, high: K, includeHigh: boolean, onFound: (k:K,v:V,counter:number) => EditRangeResult|void, initialCounter?: number): R|number { + var root = this._root; + if (root.isShared) + this._root = root = root.clone(); + try { + var r = root.forRange(low, high, includeHigh, true, this, initialCounter || 0, onFound); + return typeof r === "number" ? r : r.break!; + } finally { + while (root.keys.length <= 1 && !root.isLeaf) + this._root = root = root.keys.length === 0 ? EmptyLeaf : + (root as any as BNodeInternal).children[0]; + } + } + + /** Same as `editRange` except that the callback is called for all pairs. */ + editAll(onFound: (k:K,v:V,counter:number) => EditRangeResult|void, initialCounter?: number): R|number { + return this.editRange(this.minKey()!, this.maxKey()!, true, onFound, initialCounter); + } + + /** + * Removes a range of key-value pairs from the B+ tree. + * @param low The first key scanned will be greater than or equal to `low`. + * @param high Scanning stops when a key larger than this is reached. + * @param includeHigh Specifies whether the `high` key, if present, is deleted. + * @returns The number of key-value pairs that were deleted. + * @description Computational complexity: O(log size + number of items deleted) + */ + deleteRange(low: K, high: K, includeHigh: boolean): number { + return this.editRange(low, high, includeHigh, DeleteRange); + } + + /** Deletes a series of keys from the collection. */ + deleteKeys(keys: K[]): number { + for (var i = 0, r = 0; i < keys.length; i++) + if (this.delete(keys[i])) + r++; + return r; + } + + /** Gets the height of the tree: the number of internal nodes between the + * BTree object and its leaf nodes (zero if there are no internal nodes). */ + get height(): number { + for (var node = this._root, h = -1; node != null; h++) + node = (node as any).children; + return h; + } + + /** Makes the object read-only to ensure it is not accidentally modified. + * Freezing does not have to be permanent; unfreeze() reverses the effect. + * This is accomplished by replacing mutator functions with a function + * that throws an Error. Compared to using a property (e.g. this.isFrozen) + * this implementation gives better performance in non-frozen BTrees. + */ + freeze() { + var t = this as any; + // Note: all other mutators ultimately call set() or editRange() + // so we don't need to override those others. + t.clear = t.set = t.editRange = function() { + throw new Error("Attempted to modify a frozen BTree"); + }; + } + + /** Ensures mutations are allowed, reversing the effect of freeze(). */ + unfreeze() { + delete this.clear; + delete this.set; + delete this.editRange; + } + + /** Returns true if the tree appears to be frozen. */ + get isFrozen() { + return this.hasOwnProperty('editRange'); + } + + /** Scans the tree for signs of serious bugs (e.g. this.size doesn't match + * number of elements, internal nodes not caching max element properly...) + * Computational complexity: O(number of nodes), i.e. O(size). This method + * skips the most expensive test - whether all keys are sorted - but it + * does check that maxKey() of the children of internal nodes are sorted. */ + checkValid() { + var size = this._root.checkValid(0, this); + check(size === this.size, "size mismatch: counted ", size, "but stored", this.size); + } +} + +declare const Symbol: any; +if (Symbol && Symbol.iterator) // iterator is equivalent to entries() + (BTree as any).prototype[Symbol.iterator] = BTree.prototype.entries; +(BTree as any).prototype.where = BTree.prototype.filter; +(BTree as any).prototype.setRange = BTree.prototype.setPairs; +(BTree as any).prototype.add = BTree.prototype.set; + +function iterator(next: () => {done:boolean,value?:T} = (() => ({ done:true, value:undefined }))): IterableIterator { + var result: any = { next }; + if (Symbol && Symbol.iterator) + result[Symbol.iterator] = function() { return this; }; + return result; +} + + +/** Leaf node / base class. **************************************************/ +class BNode { + // If this is an internal node, _keys[i] is the highest key in children[i]. + keys: K[]; + values: V[]; + isShared: true | undefined; + get isLeaf() { return (this as any).children === undefined; } + + constructor(keys: K[] = [], values?: V[]) { + this.keys = keys; + this.values = values || undefVals as any[]; + this.isShared = undefined; + } + + // Shared methods ///////////////////////////////////////////////////////// + + maxKey() { + return this.keys[this.keys.length-1]; + } + + // If key not found, returns i^failXor where i is the insertion index. + // Callers that don't care whether there was a match will set failXor=0. + indexOf(key: K, failXor: number, cmp: (a:K, b:K) => number): index { + // TODO: benchmark multiple search strategies + const keys = this.keys; + var lo = 0, hi = keys.length, mid = hi >> 1; + while(lo < hi) { + var c = cmp(keys[mid], key); + if (c < 0) + lo = mid + 1; + else if (c > 0) // key < keys[mid] + hi = mid; + else if (c === 0) + return mid; + else { + // c is NaN or otherwise invalid + if (key === key) // at least the search key is not NaN + return keys.length; + else + throw new Error("BTree: NaN was used as a key"); + } + mid = (lo + hi) >> 1; + } + return mid ^ failXor; + + // Unrolled version: benchmarks show same speed, not worth using + /*var i = 1, c: number = 0, sum = 0; + if (keys.length >= 4) { + i = 3; + if (keys.length >= 8) { + i = 7; + if (keys.length >= 16) { + i = 15; + if (keys.length >= 32) { + i = 31; + if (keys.length >= 64) { + i = 127; + i += (c = i < keys.length ? cmp(keys[i], key) : 1) < 0 ? 64 : -64; + sum += c; + i += (c = i < keys.length ? cmp(keys[i], key) : 1) < 0 ? 32 : -32; + sum += c; + } + i += (c = i < keys.length ? cmp(keys[i], key) : 1) < 0 ? 16 : -16; + sum += c; + } + i += (c = i < keys.length ? cmp(keys[i], key) : 1) < 0 ? 8 : -8; + sum += c; + } + i += (c = i < keys.length ? cmp(keys[i], key) : 1) < 0 ? 4 : -4; + sum += c; + } + i += (c = i < keys.length ? cmp(keys[i], key) : 1) < 0 ? 2 : -2; + sum += c; + } + i += (c = i < keys.length ? cmp(keys[i], key) : 1) < 0 ? 1 : -1; + c = i < keys.length ? cmp(keys[i], key) : 1; + sum += c; + if (c < 0) { + ++i; + c = i < keys.length ? cmp(keys[i], key) : 1; + sum += c; + } + if (sum !== sum) { + if (key === key) // at least the search key is not NaN + return keys.length ^ failXor; + else + throw new Error("BTree: NaN was used as a key"); + } + return c === 0 ? i : i ^ failXor;*/ + } + + // Leaf Node: misc ////////////////////////////////////////////////////////// + + minKey() { + return this.keys[0]; + } + + clone(): BNode { + var v = this.values; + return new BNode(this.keys.slice(0), v === undefVals ? v : v.slice(0)); + } + + greedyClone(force?: boolean): BNode { + return this.isShared && !force ? this : this.clone(); + } + + get(key: K, defaultValue: V|undefined, tree: BTree): V|undefined { + var i = this.indexOf(key, -1, tree._compare); + return i < 0 ? defaultValue : this.values[i]; + } + + checkValid(depth: number, tree: BTree): number { + var kL = this.keys.length, vL = this.values.length; + check(this.values === undefVals ? kL <= vL : kL === vL, + "keys/values length mismatch: depth", depth, "with lengths", kL, vL); + // 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); + return kL; + } + + // Leaf Node: set & node splitting ////////////////////////////////////////// + + set(key: K, value: V, overwrite: boolean|undefined, tree: BTree): boolean|BNode { + var i = this.indexOf(key, -1, tree._compare); + if (i < 0) { + // key does not exist yet + i = ~i; + tree._size++; + + if (this.keys.length < tree._maxNodeSize) { + return this.insertInLeaf(i, key, value, tree); + } else { + // This leaf node is full and must split + var newRightSibling = this.splitOffRightSide(), target: BNode = this; + if (i > this.keys.length) { + i -= this.keys.length; + target = newRightSibling; + } + target.insertInLeaf(i, key, value, tree); + return newRightSibling; + } + } else { + // Key already exists + if (overwrite !== false) { + if (value !== undefined) + this.reifyValues(); + // usually this is a no-op, but some users may wish to edit the key + this.keys[i] = key; + this.values[i] = value; + } + return false; + } + } + + reifyValues() { + if (this.values === undefVals) + return this.values = this.values.slice(0, this.keys.length); + return this.values; + } + + insertInLeaf(i: index, key: K, value: V, tree: BTree) { + this.keys.splice(i, 0, key); + if (this.values === undefVals) { + while (undefVals.length < tree._maxNodeSize) + undefVals.push(undefined); + if (value === undefined) { + return true; + } else { + this.values = undefVals.slice(0, this.keys.length - 1); + } + } + this.values.splice(i, 0, value); + return true; + } + + takeFromRight(rhs: BNode) { + // Reminder: parent node must update its copy of key for this node + // assert: neither node is shared + // assert rhs.keys.length > (maxNodeSize/2 && this.keys.length) { + // Reminder: parent node must update its copy of key for this node + // assert: neither node is shared + // assert rhs.keys.length > (maxNodeSize/2 && this.keys.length { + // Reminder: parent node must update its copy of key for this node + var half = this.keys.length >> 1, keys = this.keys.splice(half); + var values = this.values === undefVals ? undefVals : this.values.splice(half); + return new BNode(keys, values); + } + + // Leaf Node: scanning & deletions ////////////////////////////////////////// + + forRange(low: K, high: K, includeHigh: boolean|undefined, editMode: boolean, tree: BTree, count: number, + onFound?: (k:K, v:V, counter:number) => EditRangeResult|void): EditRangeResult|number { + var cmp = tree._compare; + var iLow, iHigh; + if (high === low) { + if (!includeHigh) + return count; + iHigh = (iLow = this.indexOf(low, -1, cmp)) + 1; + if (iLow < 0) + return count; + } else { + iLow = this.indexOf(low, 0, cmp); + iHigh = this.indexOf(high, -1, cmp); + if (iHigh < 0) + iHigh = ~iHigh; + else if (includeHigh === true) + iHigh++; + } + var keys = this.keys, values = this.values; + if (onFound !== undefined) { + for(var i = iLow; i < iHigh; i++) { + var key = keys[i]; + var result = onFound(key, values[i], count++); + if (result !== undefined) { + if (editMode === true) { + if (key !== keys[i] || this.isShared === true) + throw new Error("BTree illegally changed or cloned in editRange"); + if (result.delete) { + this.keys.splice(i, 1); + if (this.values !== undefVals) + this.values.splice(i, 1); + tree._size--; + i--; + iHigh--; + } else if (result.hasOwnProperty('value')) { + values![i] = result.value!; + } + } + if (result.break !== undefined) + return result; + } + } + } else + count += iHigh - iLow; + return count; + } + + /** Adds entire contents of right-hand sibling (rhs is left unchanged) */ + mergeSibling(rhs: BNode, _: number) { + this.keys.push.apply(this.keys, rhs.keys); + if (this.values === undefVals) { + if (rhs.values === undefVals) + return; + this.values = this.values.slice(0, this.keys.length); + } + this.values.push.apply(this.values, rhs.reifyValues()); + } +} + +/** Internal node (non-leaf node) ********************************************/ +class BNodeInternal extends BNode { + // Note: conventionally B+ trees have one fewer key than the number of + // children, but I find it easier to keep the array lengths equal: each + // keys[i] caches the value of children[i].maxKey(). + children: BNode[]; + + constructor(children: BNode[], keys?: K[]) { + if (!keys) { + keys = []; + for (var i = 0; i < children.length; i++) + keys[i] = children[i].maxKey(); + } + super(keys); + this.children = children; + } + + clone(): BNode { + var children = this.children.slice(0); + for (var i = 0; i < children.length; i++) + children[i].isShared = true; + return new BNodeInternal(children, this.keys.slice(0)); + } + + greedyClone(force?: boolean): BNode { + if (this.isShared && !force) + return this; + var nu = new BNodeInternal(this.children.slice(0), this.keys.slice(0)); + for (var i = 0; i < nu.children.length; i++) + nu.children[i] = nu.children[i].greedyClone(); + return nu; + } + + minKey() { + return this.children[0].minKey(); + } + + get(key: K, defaultValue: V|undefined, tree: BTree): V|undefined { + var i = this.indexOf(key, 0, tree._compare), children = this.children; + return i < children.length ? children[i].get(key, defaultValue, tree) : undefined; + } + + checkValid(depth: number, tree: BTree) : number { + var kL = this.keys.length, cL = this.children.length; + check(kL === cL, "keys/children length mismatch: depth", depth, "lengths", kL, cL); + check(kL > 1, "internal node has length", kL, "at depth", depth); + var size = 0, c = this.children, k = this.keys, childSize = 0; + for (var i = 0; i < cL; i++) { + size += c[i].checkValid(depth + 1, tree); + childSize += c[i].keys.length; + check(size >= childSize, "wtf"); // no way this will ever fail + check(i === 0 || c[i-1].constructor === c[i].constructor, "type mismatch"); + if (c[i].maxKey() != k[i]) + check(false, "keys[", i, "] =", k[i], "is wrong, should be ", c[i].maxKey(), "at depth", depth); + if (!(i === 0 || tree._compare(k[i-1], k[i]) < 0)) + check(false, "sort violation at depth", depth, "index", i, "keys", k[i-1], k[i]); + } + var toofew = childSize < (tree.maxNodeSize >> 1)*cL; + if (toofew || childSize > tree.maxNodeSize*cL) + check(false, toofew ? "too few" : "too many", "children (", childSize, size, ") at depth", depth, ", maxNodeSize:", tree.maxNodeSize, "children.length:", cL); + return size; + } + + // Internal Node: set & node splitting ////////////////////////////////////// + + set(key: K, value: V, overwrite: boolean|undefined, tree: BTree): boolean|BNodeInternal { + var c = this.children, max = tree._maxNodeSize, cmp = tree._compare; + var i = Math.min(this.indexOf(key, 0, cmp), c.length - 1), child = c[i]; + + if (child.isShared) + c[i] = child = child.clone(); + if (child.keys.length >= max) { + // child is full; inserting anything else will cause a split. + // Shifting an item to the left or right sibling may avoid a split. + // We can do a shift if the adjacent node is not full and if the + // current key can still be placed in the same node after the shift. + var other: BNode; + if (i > 0 && (other = c[i-1]).keys.length < max && cmp(child.keys[0], key) < 0) { + if (other.isShared) + c[i-1] = other = other.clone(); + other.takeFromRight(child); + this.keys[i-1] = other.maxKey(); + } else if ((other = c[i+1]) !== undefined && other.keys.length < max && cmp(child.maxKey(), key) < 0) { + if (other.isShared) + c[i+1] = other = other.clone(); + other.takeFromLeft(child); + this.keys[i] = c[i].maxKey(); + } + } + + var result = child.set(key, value, overwrite, tree); + if (result === false) + return false; + this.keys[i] = child.maxKey(); + if (result === true) + return true; + + // The child has split and `result` is a new right child... does it fit? + if (this.keys.length < max) { // yes + this.insert(i+1, result); + return true; + } else { // no, we must split also + var newRightSibling = this.splitOffRightSide(), target: BNodeInternal = this; + if (cmp(result.maxKey(), this.maxKey()) > 0) { + target = newRightSibling; + i -= this.keys.length; + } + target.insert(i+1, result); + return newRightSibling; + } + } + + insert(i: index, child: BNode) { + this.children.splice(i, 0, child); + this.keys.splice(i, 0, child.maxKey()); + } + + splitOffRightSide() { + var half = this.children.length >> 1; + return new BNodeInternal(this.children.splice(half), this.keys.splice(half)); + } + + takeFromRight(rhs: BNode) { + // Reminder: parent node must update its copy of key for this node + // assert: neither node is shared + // assert rhs.keys.length > (maxNodeSize/2 && this.keys.length).children.shift()!); + } + + takeFromLeft(lhs: BNode) { + // Reminder: parent node must update its copy of key for this node + // assert: neither node is shared + // assert rhs.keys.length > (maxNodeSize/2 && this.keys.length).children.pop()!); + } + + // Internal Node: scanning & deletions ////////////////////////////////////// + + forRange(low: K, high: K, includeHigh: boolean|undefined, editMode: boolean, tree: BTree, count: number, + onFound?: (k:K, v:V, counter:number) => EditRangeResult|void): EditRangeResult|number + { + var cmp = tree._compare; + 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); + var keys = this.keys, children = this.children; + if (!editMode) { + // Simple case + for(; i <= iHigh; i++) { + var result = children[i].forRange(low, high, includeHigh, editMode, tree, count, onFound); + if (typeof result !== 'number') + return result; + count = result; + } + } else if (i <= iHigh) { + try { + for(; i <= iHigh; i++) { + if (children[i].isShared) + children[i] = children[i].clone(); + var result = children[i].forRange(low, high, includeHigh, editMode, tree, count, onFound); + keys[i] = children[i].maxKey(); + if (typeof result !== 'number') + return result; + count = result; + } + } finally { + // Deletions may have occurred, so look for opportunities to merge nodes. + var half = tree._maxNodeSize >> 1; + if (iLow > 0) + iLow--; + for(i = iHigh; i >= iLow; i--) { + if (children[i].keys.length <= half) + 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(); + } + } + } + return count; + } + + /** Merges child i with child i+1 if their combined size is not too large */ + tryMerge(i: index, maxSize: number): boolean { + var children = this.children; + if (i >= 0 && i + 1 < children.length) { + if (children[i].keys.length + children[i+1].keys.length <= maxSize) { + if (children[i].isShared) // cloned already UNLESS i is outside scan range + children[i] = children[i].clone(); + children[i].mergeSibling(children[i+1], maxSize); + children.splice(i + 1, 1); + this.keys.splice(i + 1, 1); + this.keys[i] = children[i].maxKey(); + return true; + } + } + return false; + } + + mergeSibling(rhs: BNode, maxNodeSize: number) { + // assert !this.isShared; + var oldLength = this.keys.length; + this.keys.push.apply(this.keys, rhs.keys); + this.children.push.apply(this.children, (rhs as any as BNodeInternal).children); + // If our children are themselves almost empty due to a mass-delete, + // they may need to be merged too (but only the oldLength-1 and its + // right sibling should need this). + this.tryMerge(oldLength-1, maxNodeSize); + } +} + +// Optimization: this array of `undefined`s is used instead of a normal +// array of values in nodes where `undefined` is the only value. +// Its length is extended to max node size on first use; since it can +// be shared between trees with different maximums, its length can only +// increase, never decrease. Its type should be undefined[] but strangely +// TypeScript won't allow the comparison V[] === undefined[]. To prevent +// users from making this array too large, BTree has a maximum node size. +var undefVals: any[] = []; + +const Delete = {delete: true}, DeleteRange = () => Delete; +const Break = {break: true}; +const EmptyLeaf = (function() { + var n = new BNode(); n.isShared = true; return n; +})(); +const EmptyArray: any[] = []; +const ReusedArray: any[] = []; // assumed thread-local + +function check(fact: boolean, ...args: any[]) { + if (!fact) { + args.unshift('B+ tree '); // at beginning of message + throw new Error(args.join(' ')); + } +} + +/** A BTree frozen in the empty state. */ +export const EmptyBTree = (() => { let t = new BTree(); t.freeze(); return t; })(); \ No newline at end of file diff --git a/packages/idb-bridge/src/tree/interfaces.ts b/packages/idb-bridge/src/tree/interfaces.ts new file mode 100644 index 000000000..c708c20b5 --- /dev/null +++ b/packages/idb-bridge/src/tree/interfaces.ts @@ -0,0 +1,329 @@ +/* +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 + + +/** Read-only set interface (subinterface of IMapSource). + * The word "set" usually means that each item in the collection is unique + * (appears only once, based on a definition of equality used by the + * collection.) Objects conforming to this interface aren't guaranteed not + * to contain duplicates, but as an example, BTree implements this + * interface and does not allow duplicates. */ +export interface ISetSource +{ + /** Returns the number of key/value pairs in the map object. */ + size: number; + /** Returns a boolean asserting whether the key exists in the map object or not. */ + has(key: K): boolean; + /** Returns a new iterator for iterating the items in the set (the order is implementation-dependent). */ + keys(): IterableIterator; +} + +/** Read-only map interface (i.e. a source of key-value pairs). */ +export interface IMapSource extends ISetSource +{ + /** Returns the number of key/value pairs in the map object. */ + size: number; + /** Returns the value associated to the key, or undefined if there is none. */ + get(key: K): V|undefined; + /** Returns a boolean asserting whether the key exists in the map object or not. */ + has(key: K): boolean; + /** Calls callbackFn once for each key-value pair present in the map object. + * The ES6 Map class sends the value to the callback before the key, so + * this interface must do likewise. */ + forEach(callbackFn: (v:V, k:K, map:IMapSource) => void, thisArg: any): void; + + /** Returns an iterator that provides all key-value pairs from the collection (as arrays of length 2). */ + entries(): IterableIterator<[K,V]>; + /** Returns a new iterator for iterating the keys of each pair. */ + keys(): IterableIterator; + /** Returns a new iterator for iterating the values of each pair. */ + values(): IterableIterator; + // TypeScript compiler decided Symbol.iterator has type 'any' + //[Symbol.iterator](): IterableIterator<[K,V]>; +} + +/** Write-only set interface (the set cannot be queried, but items can be added to it.) + * @description Note: BTree does not officially implement this interface, + * but BTree can be used as an instance of ISetSink. */ +export interface ISetSink +{ + /** Adds the specified item to the set, if it was not in the set already. */ + add(key: K): any; + /** Returns true if an element in the map object existed and has been + * removed, or false if the element did not exist. */ + delete(key: K): boolean; + /** Removes everything so that the set is empty. */ + clear(): void; +} + +/** Write-only map interface (i.e. a drain into which key-value pairs can be "sunk") */ +export interface IMapSink +{ + /** Returns true if an element in the map object existed and has been + * removed, or false if the element did not exist. */ + delete(key: K): boolean; + /** Sets the value for the key in the map object (the return value is + * boolean in BTree but Map returns the Map itself.) */ + set(key: K, value: V): any; + /** Removes all key/value pairs from the IMap object. */ + clear(): void; +} + +/** Set interface. + * @description Note: BTree does not officially implement this interface, + * but BTree can be used as an instance of ISet. */ +export interface ISet extends ISetSource, ISetSink { } + +/** An interface compatible with ES6 Map and BTree. This interface does not + * describe the complete interface of either class, but merely the common + * interface shared by both. */ +export interface IMap extends IMapSource, IMapSink { } + +/** An data source that provides read-only access to a set of items called + * "keys" in sorted order. This is a subinterface of ISortedMapSource. */ +export interface ISortedSetSource extends ISetSource +{ + /** Gets the lowest key in the collection. */ + minKey(): K | undefined; + /** Gets the highest key in the collection. */ + maxKey(): K | undefined; + /** Returns the next key larger than the specified key (or undefined if there is none) */ + nextHigherKey(key: K): K|undefined; + /** Returns the next key smaller than the specified key (or undefined if there is none) */ + nextLowerKey(key: K): K|undefined; + /** Calls `callback` on the specified range of keys, in ascending order by key. + * @param low The first key scanned will be greater than or equal to `low`. + * @param high Scanning stops when a key larger than this is reached. + * @param includeHigh If the `high` key is present in the map, `onFound` is called + * for that final pair if and only if this parameter is true. + * @param onFound A function that is called for each key pair. Because this + * is a subinterface of ISortedMapSource, if there is a value + * associated with the key, it is passed as the second parameter. + * @param initialCounter Initial third argument of `onFound`. This value + * increases by one each time `onFound` is called. Default: 0 + * @returns Number of pairs found and the number of times `onFound` was called. + */ + forRange(low: K, high: K, includeHigh: boolean, onFound?: (k:K,v:any,counter:number) => void, initialCounter?: number): number; + /** Returns a new iterator for iterating the keys of each pair in ascending order. + * @param firstKey: Minimum key to include in the output. */ + keys(firstKey?: K): IterableIterator; +} + +/** An data source that provides read-only access to items in sorted order. */ +export interface ISortedMapSource extends IMapSource, ISortedSetSource +{ + /** Returns the next pair whose key is larger than the specified key (or undefined if there is none) */ + nextHigherPair(key: K): [K,V]|undefined; + /** Returns the next pair whose key is smaller than the specified key (or undefined if there is none) */ + nextLowerPair(key: K): [K,V]|undefined; + /** Builds an array of pairs from the specified range of keys, sorted by key. + * Each returned pair is also an array: pair[0] is the key, pair[1] is the value. + * @param low The first key in the array will be greater than or equal to `low`. + * @param high This method returns when a key larger than this is reached. + * @param includeHigh If the `high` key is present in the map, its pair will be + * included in the output if and only if this parameter is true. Note: + * if the `low` key is present, it is always included in the output. + * @param maxLength Maximum length of the returned array (default: unlimited) + * @description Computational complexity: O(result.length + log size) + */ + getRange(low: K, high: K, includeHigh?: boolean, maxLength?: number): [K,V][]; + /** Calls `callback` on the specified range of keys, in ascending order by key. + * @param low The first key scanned will be greater than or equal to `low`. + * @param high Scanning stops when a key larger than this is reached. + * @param includeHigh If the `high` key is present in the map, `onFound` is called + * for that final pair if and only if this parameter is true. + * @param onFound A function that is called for each key-value pair. + * @param initialCounter Initial third argument of onFound. This value + * increases by one each time `onFound` is called. Default: 0 + * @returns Number of pairs found and the number of times `callback` was called. + */ + forRange(low: K, high: K, includeHigh: boolean, onFound?: (k:K,v:V,counter:number) => void, initialCounter?: number): number; + /** Returns an iterator that provides items in order by key. + * @param firstKey: Minimum key to include in the output. */ + entries(firstKey?: K): IterableIterator<[K,V]>; + /** Returns a new iterator for iterating the keys of each pair in ascending order. + * @param firstKey: Minimum key to include in the output. */ + keys(firstKey?: K): IterableIterator; + /** Returns a new iterator for iterating the values of each pair in order by key. + * @param firstKey: Minimum key whose associated value is included in the output. */ + values(firstKey?: K): IterableIterator; + + // This method should logically be in IMapSource but is not supported by ES6 Map + /** Performs a reduce operation like the `reduce` method of `Array`. + * It is used to combine all pairs into a single value, or perform conversions. */ + reduce(callback: (previous:R,currentPair:[K,V],counter:number,tree:IMapF) => R, initialValue: R): R; + /** Performs a reduce operation like the `reduce` method of `Array`. + * It is used to combine all pairs into a single value, or perform conversions. */ + reduce(callback: (previous:R|undefined,currentPair:[K,V],counter:number,tree:IMapF) => R): R|undefined; +} + +/** An interface for a set of keys (the combination of ISortedSetSource and ISetSink) */ +export interface ISortedSet extends ISortedSetSource, ISetSink { } + +/** An interface for a sorted map (dictionary), + * not including functional/persistent methods. */ +export interface ISortedMap extends IMap, ISortedMapSource +{ + // All of the following methods should be in IMap but are left out of IMap + // so that IMap is compatible with ES6 Map. + + /** Adds or overwrites a key-value pair in the sorted map. + * @param key the key is used to determine the sort order of data in the tree. + * @param value data to associate with the key + * @param overwrite Whether to overwrite an existing key-value pair + * (default: true). If this is false and there is an existing + * key-value pair then the call to this method has no effect. + * @returns true if a new key-value pair was added, false if the key + * already existed. */ + set(key: K, value: V, overwrite?: boolean): boolean; + /** Adds all pairs from a list of key-value pairs. + * @param pairs Pairs to add to this tree. If there are duplicate keys, + * later pairs currently overwrite earlier ones (e.g. [[0,1],[0,7]] + * associates 0 with 7.) + * @param overwrite Whether to overwrite pairs that already exist (if false, + * pairs[i] is ignored when the key pairs[i][0] already exists.) + * @returns The number of pairs added to the collection. + */ + setPairs(pairs: [K,V][], overwrite?: boolean): number; + /** Deletes a series of keys from the collection. */ + deleteKeys(keys: K[]): number; + /** Removes a range of key-value pairs from the B+ tree. + * @param low The first key deleted will be greater than or equal to `low`. + * @param high Deleting stops when a key larger than this is reached. + * @param includeHigh Specifies whether the `high` key, if present, is deleted. + * @returns The number of key-value pairs that were deleted. */ + deleteRange(low: K, high: K, includeHigh: boolean): number; + + // TypeScript requires these methods of ISortedMapSource to be repeated + entries(firstKey?: K): IterableIterator<[K,V]>; + keys(firstKey?: K): IterableIterator; + values(firstKey?: K): IterableIterator; +} + +/** An interface for a functional set, in which the set object could be read-only + * but new versions of the set can be created by calling "with" or "without" + * methods to add or remove keys. This is a subinterface of IMapF, + * so the items in the set may be referred to as "keys". */ +export interface ISetF extends ISetSource { + /** Returns a copy of the set with the specified key included. + * @description You might wonder why this method accepts only one key + * instead of `...keys: K[]`. The reason is that the derived interface + * IMapF expects the second parameter to be a value. Therefore + * withKeys() is provided to set multiple keys at once. */ + with(key: K): ISetF; + /** Returns a copy of the set with the specified key removed. */ + without(key: K): ISetF; + /** Returns a copy of the tree with all the keys in the specified array present. + * @param keys The keys to add. + * @param returnThisIfUnchanged If true, the method returns `this` when + * all of the keys are already present in the collection. The + * default value may be true or false depending on the concrete + * implementation of the interface (in BTree, the default is false.) */ + withKeys(keys: K[], returnThisIfUnchanged?: boolean): ISetF; + /** Returns a copy of the tree with all the keys in the specified array removed. */ + withoutKeys(keys: K[], returnThisIfUnchanged?: boolean): ISetF; + /** Returns a copy of the tree with items removed whenever the callback + * function returns false. + * @param callback A function to call for each item in the set. + * The second parameter to `callback` exists because ISetF + * is a subinterface of IMapF. If the object is a map, v + * is the value associated with the key, otherwise v could be + * undefined or another copy of the third parameter (counter). */ + filter(callback: (k:K,v:any,counter:number) => boolean, returnThisIfUnchanged?: boolean): ISetF; +} + +/** An interface for a functional map, in which the map object could be read-only + * but new versions of the map can be created by calling "with" or "without" + * methods to add or remove keys or key-value pairs. + */ +export interface IMapF extends IMapSource, ISetF { + /** Returns a copy of the tree with the specified key set (the value is undefined). */ + with(key: K): IMapF; + /** Returns a copy of the tree with the specified key-value pair set. */ + with(key: K, value: V2, overwrite?: boolean): IMapF; + /** Returns a copy of the tree with the specified key-value pairs set. */ + withPairs(pairs: [K,V|V2][], overwrite: boolean): IMapF; + /** Returns a copy of the tree with all the keys in the specified array present. + * @param keys The keys to add. If a key is already present in the tree, + * neither the existing key nor the existing value is modified. + * @param returnThisIfUnchanged If true, the method returns `this` when + * all of the keys are already present in the collection. The + * default value may be true or false depending on the concrete + * implementation of the interface (in BTree, the default is false.) */ + withKeys(keys: K[], returnThisIfUnchanged?: boolean): IMapF; + /** Returns a copy of the tree with all values altered by a callback function. */ + mapValues(callback: (v:V,k:K,counter:number) => R): IMapF; + /** Performs a reduce operation like the `reduce` method of `Array`. + * It is used to combine all pairs into a single value, or perform conversions. */ + reduce(callback: (previous:R,currentPair:[K,V],counter:number,tree:IMapF) => R, initialValue: R): R; + /** Performs a reduce operation like the `reduce` method of `Array`. + * It is used to combine all pairs into a single value, or perform conversions. */ + reduce(callback: (previous:R|undefined,currentPair:[K,V],counter:number,tree:IMapF) => R): R|undefined; + + // Update return types in ISetF + without(key: K): IMapF; + withoutKeys(keys: K[], returnThisIfUnchanged?: boolean): IMapF; + /** Returns a copy of the tree with pairs removed whenever the callback + * function returns false. */ + filter(callback: (k:K,v:V,counter:number) => boolean, returnThisIfUnchanged?: boolean): IMapF; +} + +/** An interface for a functional sorted set: a functional set in which the + * keys (items) are sorted. This is a subinterface of ISortedMapF. */ +export interface ISortedSetF extends ISetF, ISortedSetSource +{ + // TypeScript requires this method of ISortedSetSource to be repeated + keys(firstKey?: K): IterableIterator; +} + +export interface ISortedMapF extends ISortedSetF, IMapF, ISortedMapSource +{ + /** Returns a copy of the tree with the specified range of keys removed. */ + withoutRange(low: K, high: K, includeHigh: boolean, returnThisIfUnchanged?: boolean): ISortedMapF; + + // TypeScript requires these methods of ISortedSetF and ISortedMapSource to be repeated + entries(firstKey?: K): IterableIterator<[K,V]>; + keys(firstKey?: K): IterableIterator; + values(firstKey?: K): IterableIterator; + forRange(low: K, high: K, includeHigh: boolean, onFound?: (k:K,v:V,counter:number) => void, initialCounter?: number): number; + + // Update the return value of methods from base interfaces + with(key: K): ISortedMapF; + with(key: K, value: V2, overwrite?: boolean): ISortedMapF; + withKeys(keys: K[], returnThisIfUnchanged?: boolean): ISortedMapF; + withPairs(pairs: [K,V|V2][], overwrite: boolean): ISortedMapF; + mapValues(callback: (v:V,k:K,counter:number) => R): ISortedMapF; + without(key: K): ISortedMapF; + withoutKeys(keys: K[], returnThisIfUnchanged?: boolean): ISortedMapF; + filter(callback: (k:K,v:any,counter:number) => boolean, returnThisIfUnchanged?: boolean): ISortedMapF; +} + +export interface ISortedMapConstructor { + new (entries?: [K,V][], compare?: (a: K, b: K) => number): ISortedMap; +} +export interface ISortedMapFConstructor { + new (entries?: [K,V][], compare?: (a: K, b: K) => number): ISortedMapF; +} \ No newline at end of file diff --git a/packages/idb-bridge/src/util/FakeEvent.ts b/packages/idb-bridge/src/util/FakeEvent.ts new file mode 100644 index 000000000..bf17f7e72 --- /dev/null +++ b/packages/idb-bridge/src/util/FakeEvent.ts @@ -0,0 +1,80 @@ +/* + Copyright 2017 Jeremy Scheff + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express + or implied. See the License for the specific language governing + permissions and limitations under the License. +*/ + + +import FakeEventTarget from "./FakeEventTarget"; +import { EventType } from "./types"; + +class Event { + public eventPath: FakeEventTarget[] = []; + public type: EventType; + + public readonly NONE = 0; + public readonly CAPTURING_PHASE = 1; + public readonly AT_TARGET = 2; + public readonly BUBBLING_PHASE = 3; + + // Flags + public propagationStopped = false; + public immediatePropagationStopped = false; + public canceled = false; + public initialized = true; + public dispatched = false; + + public target: FakeEventTarget | null = null; + public currentTarget: FakeEventTarget | null = null; + + public eventPhase: 0 | 1 | 2 | 3 = 0; + + public defaultPrevented = false; + + public isTrusted = false; + public timeStamp = Date.now(); + + public bubbles: boolean; + public cancelable: boolean; + + constructor( + type: EventType, + eventInitDict: { bubbles?: boolean; cancelable?: boolean } = {}, + ) { + this.type = type; + + this.bubbles = + eventInitDict.bubbles !== undefined ? eventInitDict.bubbles : false; + this.cancelable = + eventInitDict.cancelable !== undefined + ? eventInitDict.cancelable + : false; + } + + public preventDefault() { + if (this.cancelable) { + this.canceled = true; + } + } + + public stopPropagation() { + this.propagationStopped = true; + } + + public stopImmediatePropagation() { + this.propagationStopped = true; + this.immediatePropagationStopped = true; + } +} + +export default Event; diff --git a/packages/idb-bridge/src/util/FakeEventTarget.ts b/packages/idb-bridge/src/util/FakeEventTarget.ts new file mode 100644 index 000000000..3c7eaf468 --- /dev/null +++ b/packages/idb-bridge/src/util/FakeEventTarget.ts @@ -0,0 +1,177 @@ +/* + Copyright 2017 Jeremy Scheff + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express + or implied. See the License for the specific language governing + permissions and limitations under the License. + */ + + +import { InvalidStateError } from "./errors"; +import FakeEvent from "./FakeEvent"; +import { EventCallback, EventType } from "./types"; + +type EventTypeProp = + | "onabort" + | "onblocked" + | "oncomplete" + | "onerror" + | "onsuccess" + | "onupgradeneeded" + | "onversionchange"; + +interface Listener { + callback: EventCallback; + capture: boolean; + type: EventType; +} + +const stopped = (event: FakeEvent, listener: Listener) => { + return ( + event.immediatePropagationStopped || + (event.eventPhase === event.CAPTURING_PHASE && + listener.capture === false) || + (event.eventPhase === event.BUBBLING_PHASE && listener.capture === true) + ); +}; + +// http://www.w3.org/TR/dom/#concept-event-listener-invoke +const invokeEventListeners = (event: FakeEvent, obj: FakeEventTarget) => { + event.currentTarget = obj; + + // The callback might cause obj.listeners to mutate as we traverse it. + // Take a copy of the array so that nothing sneaks in and we don't lose + // our place. + for (const listener of obj.listeners.slice()) { + if (event.type !== listener.type || stopped(event, listener)) { + continue; + } + + // @ts-ignore + listener.callback.call(event.currentTarget, event); + } + + const typeToProp: { [key in EventType]: EventTypeProp } = { + abort: "onabort", + blocked: "onblocked", + complete: "oncomplete", + error: "onerror", + success: "onsuccess", + upgradeneeded: "onupgradeneeded", + versionchange: "onversionchange", + }; + const prop = typeToProp[event.type]; + if (prop === undefined) { + throw new Error(`Unknown event type: "${event.type}"`); + } + + const callback = event.currentTarget[prop]; + if (callback) { + const listener = { + callback, + capture: false, + type: event.type, + }; + if (!stopped(event, listener)) { + // @ts-ignore + listener.callback.call(event.currentTarget, event); + } + } +}; + +abstract class FakeEventTarget { + public readonly listeners: Listener[] = []; + + // These will be overridden in individual subclasses and made not readonly + public readonly onabort: EventCallback | null | undefined; + public readonly onblocked: EventCallback | null | undefined; + public readonly oncomplete: EventCallback | null | undefined; + public readonly onerror: EventCallback | null | undefined; + public readonly onsuccess: EventCallback | null | undefined; + public readonly onupgradeneeded: EventCallback | null | undefined; + public readonly onversionchange: EventCallback | null | undefined; + + public addEventListener( + type: EventType, + callback: EventCallback, + capture = false, + ) { + this.listeners.push({ + callback, + capture, + type, + }); + } + + public removeEventListener( + type: EventType, + callback: EventCallback, + capture = false, + ) { + const i = this.listeners.findIndex(listener => { + return ( + listener.type === type && + listener.callback === callback && + listener.capture === capture + ); + }); + + this.listeners.splice(i, 1); + } + + // http://www.w3.org/TR/dom/#dispatching-events + public dispatchEvent(event: FakeEvent) { + if (event.dispatched || !event.initialized) { + throw new InvalidStateError("The object is in an invalid state."); + } + event.isTrusted = false; + + event.dispatched = true; + event.target = this; + // NOT SURE WHEN THIS SHOULD BE SET event.eventPath = []; + + event.eventPhase = event.CAPTURING_PHASE; + for (const obj of event.eventPath) { + if (!event.propagationStopped) { + invokeEventListeners(event, obj); + } + } + + event.eventPhase = event.AT_TARGET; + if (!event.propagationStopped) { + invokeEventListeners(event, event.target); + } + + if (event.bubbles) { + event.eventPath.reverse(); + event.eventPhase = event.BUBBLING_PHASE; + if (event.eventPath.length === 0 && event.type === "error") { + console.error("Unhandled error event: ", event.target); + } + for (const obj of event.eventPath) { + if (!event.propagationStopped) { + invokeEventListeners(event, obj); + } + } + } + + event.dispatched = false; + event.eventPhase = event.NONE; + event.currentTarget = null; + + if (event.canceled) { + return false; + } + return true; + } +} + +export default FakeEventTarget; diff --git a/packages/idb-bridge/src/util/canInjectKey.ts b/packages/idb-bridge/src/util/canInjectKey.ts new file mode 100644 index 000000000..c6c9c24ab --- /dev/null +++ b/packages/idb-bridge/src/util/canInjectKey.ts @@ -0,0 +1,34 @@ +import { KeyPath, Value } from "./types"; + +// http://w3c.github.io/IndexedDB/#check-that-a-key-could-be-injected-into-a-value +const canInjectKey = (keyPath: KeyPath, value: Value) => { + if (Array.isArray(keyPath)) { + // tslint:disable-next-line max-line-length + throw new Error( + "The key paths used in this section are always strings and never sequences, since it is not possible to create a object store which has a key generator and also has a key path that is a sequence.", + ); + } + + const identifiers = keyPath.split("."); + if (identifiers.length === 0) { + throw new Error("Assert: identifiers is not empty"); + } + identifiers.pop(); + + for (const identifier of identifiers) { + if (typeof value !== "object" && !Array.isArray(value)) { + return false; + } + + const hop = value.hasOwnProperty(identifier); + if (!hop) { + return true; + } + + value = value[identifier]; + } + + return typeof value === "object" || Array.isArray(value); +}; + +export default canInjectKey; diff --git a/packages/idb-bridge/src/util/cmp.ts b/packages/idb-bridge/src/util/cmp.ts new file mode 100644 index 000000000..9d0dc99a2 --- /dev/null +++ b/packages/idb-bridge/src/util/cmp.ts @@ -0,0 +1,108 @@ +/* + Copyright 2017 Jeremy Scheff + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express + or implied. See the License for the specific language governing + permissions and limitations under the License. + */ + +import { DataError } from "./errors"; +import valueToKey from "./valueToKey"; + +const getType = (x: any) => { + if (typeof x === "number") { + return "Number"; + } + if (x instanceof Date) { + return "Date"; + } + if (Array.isArray(x)) { + return "Array"; + } + if (typeof x === "string") { + return "String"; + } + if (x instanceof ArrayBuffer) { + return "Binary"; + } + + throw new DataError(); +}; + +// https://w3c.github.io/IndexedDB/#compare-two-keys +const compareKeys = (first: any, second: any): -1 | 0 | 1 => { + if (second === undefined) { + throw new TypeError(); + } + + first = valueToKey(first); + second = valueToKey(second); + + const t1 = getType(first); + const t2 = getType(second); + + if (t1 !== t2) { + if (t1 === "Array") { + return 1; + } + if ( + t1 === "Binary" && + (t2 === "String" || t2 === "Date" || t2 === "Number") + ) { + return 1; + } + if (t1 === "String" && (t2 === "Date" || t2 === "Number")) { + return 1; + } + if (t1 === "Date" && t2 === "Number") { + return 1; + } + return -1; + } + + if (t1 === "Binary") { + first = new Uint8Array(first); + second = new Uint8Array(second); + } + + if (t1 === "Array" || t1 === "Binary") { + const length = Math.min(first.length, second.length); + for (let i = 0; i < length; i++) { + const result = compareKeys(first[i], second[i]); + + if (result !== 0) { + return result; + } + } + + if (first.length > second.length) { + return 1; + } + if (first.length < second.length) { + return -1; + } + return 0; + } + + if (t1 === "Date") { + if (first.getTime() === second.getTime()) { + return 0; + } + } else { + if (first === second) { + return 0; + } + } + + return first > second ? 1 : -1; +}; + +export default compareKeys; diff --git a/packages/idb-bridge/src/util/deepEquals.ts b/packages/idb-bridge/src/util/deepEquals.ts new file mode 100644 index 000000000..8d05ad21e --- /dev/null +++ b/packages/idb-bridge/src/util/deepEquals.ts @@ -0,0 +1,75 @@ +/* +Copyright (c) 2017 Evgeny Poberezkin + +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. +*/ + + + + +const isArray = Array.isArray; +const keyList = Object.keys; +const hasProp = Object.prototype.hasOwnProperty; + +function deepEquals(a: any, b: any): boolean { + if (a === b) return true; + + if (a && b && typeof a == "object" && typeof b == "object") { + const arrA = isArray(a); + const arrB = isArray(b); + let i; + let length; + let key; + + if (arrA && arrB) { + length = a.length; + if (length != b.length) return false; + for (i = length; i-- !== 0; ) if (!deepEquals(a[i], b[i])) return false; + return true; + } + + if (arrA != arrB) return false; + + const dateA = a instanceof Date; + const dateB = b instanceof Date; + if (dateA != dateB) return false; + if (dateA && dateB) return a.getTime() == b.getTime(); + + const regexpA = a instanceof RegExp; + const regexpB = b instanceof RegExp; + if (regexpA != regexpB) return false; + if (regexpA && regexpB) return a.toString() == b.toString(); + + const keys = keyList(a); + length = keys.length; + + if (length !== keyList(b).length) return false; + + for (i = length; i-- !== 0; ) if (!hasProp.call(b, keys[i])) return false; + + for (i = length; i-- !== 0; ) { + key = keys[i]; + if (!deepEquals(a[key], b[key])) return false; + } + + return true; + } + + return a !== a && b !== b; +} diff --git a/packages/idb-bridge/src/util/enforceRange.ts b/packages/idb-bridge/src/util/enforceRange.ts new file mode 100644 index 000000000..0cf3b6c85 --- /dev/null +++ b/packages/idb-bridge/src/util/enforceRange.ts @@ -0,0 +1,18 @@ +// https://heycam.github.io/webidl/#EnforceRange + +const enforceRange = ( + num: number, + type: "MAX_SAFE_INTEGER" | "unsigned long", +) => { + const min = 0; + const max = type === "unsigned long" ? 4294967295 : 9007199254740991; + + if (isNaN(num) || num < min || num > max) { + throw new TypeError(); + } + if (num >= 0) { + return Math.floor(num); + } +}; + +export default enforceRange; diff --git a/packages/idb-bridge/src/util/errors.ts b/packages/idb-bridge/src/util/errors.ts new file mode 100644 index 000000000..bbf9498c1 --- /dev/null +++ b/packages/idb-bridge/src/util/errors.ts @@ -0,0 +1,120 @@ +/* + Copyright 2017 Jeremy Scheff + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express + or implied. See the License for the specific language governing + permissions and limitations under the License. + */ + + +/* tslint:disable: max-classes-per-file max-line-length */ + +const messages = { + AbortError: + "A request was aborted, for example through a call to IDBTransaction.abort.", + ConstraintError: + "A mutation operation in the transaction failed because a constraint was not satisfied. For example, an object such as an object store or index already exists and a request attempted to create a new one.", + DataCloneError: + "The data being stored could not be cloned by the internal structured cloning algorithm.", + DataError: "Data provided to an operation does not meet requirements.", + InvalidAccessError: + "An invalid operation was performed on an object. For example transaction creation attempt was made, but an empty scope was provided.", + InvalidStateError: + "An operation was called on an object on which it is not allowed or at a time when it is not allowed. Also occurs if a request is made on a source object that has been deleted or removed. Use TransactionInactiveError or ReadOnlyError when possible, as they are more specific variations of InvalidStateError.", + NotFoundError: + "The operation failed because the requested database object could not be found. For example, an object store did not exist but was being opened.", + ReadOnlyError: + 'The mutating operation was attempted in a "readonly" transaction.', + TransactionInactiveError: + "A request was placed against a transaction which is currently not active, or which is finished.", + VersionError: + "An attempt was made to open a database using a lower version than the existing version.", +}; + +export class AbortError extends Error { + constructor(message = messages.AbortError) { + super(); + this.name = "AbortError"; + this.message = message; + } +} + +export class ConstraintError extends Error { + constructor(message = messages.ConstraintError) { + super(); + this.name = "ConstraintError"; + this.message = message; + } +} + +export class DataCloneError extends Error { + constructor(message = messages.DataCloneError) { + super(); + this.name = "DataCloneError"; + this.message = message; + } +} + +export class DataError extends Error { + constructor(message = messages.DataError) { + super(); + this.name = "DataError"; + this.message = message; + } +} + +export class InvalidAccessError extends Error { + constructor(message = messages.InvalidAccessError) { + super(); + this.name = "InvalidAccessError"; + this.message = message; + } +} + +export class InvalidStateError extends Error { + constructor(message = messages.InvalidStateError) { + super(); + this.name = "InvalidStateError"; + this.message = message; + } +} + +export class NotFoundError extends Error { + constructor(message = messages.NotFoundError) { + super(); + this.name = "NotFoundError"; + this.message = message; + } +} + +export class ReadOnlyError extends Error { + constructor(message = messages.ReadOnlyError) { + super(); + this.name = "ReadOnlyError"; + this.message = message; + } +} + +export class TransactionInactiveError extends Error { + constructor(message = messages.TransactionInactiveError) { + super(); + this.name = "TransactionInactiveError"; + this.message = message; + } +} + +export class VersionError extends Error { + constructor(message = messages.VersionError) { + super(); + this.name = "VersionError"; + this.message = message; + } +} diff --git a/packages/idb-bridge/src/util/extractKey.ts b/packages/idb-bridge/src/util/extractKey.ts new file mode 100644 index 000000000..fd14c5a64 --- /dev/null +++ b/packages/idb-bridge/src/util/extractKey.ts @@ -0,0 +1,55 @@ +import { Key, KeyPath, Value } from "./types"; +import valueToKey from "./valueToKey"; + +// http://www.w3.org/TR/2015/REC-IndexedDB-20150108/#dfn-steps-for-extracting-a-key-from-a-value-using-a-key-path +const extractKey = (keyPath: KeyPath, value: Value) => { + if (Array.isArray(keyPath)) { + const result: Key[] = []; + + for (let item of keyPath) { + // This doesn't make sense to me based on the spec, but it is needed to pass the W3C KeyPath tests (see same + // comment in validateKeyPath) + if ( + item !== undefined && + item !== null && + typeof item !== "string" && + (item as any).toString + ) { + item = (item as any).toString(); + } + result.push(valueToKey(extractKey(item, value))); + } + + return result; + } + + if (keyPath === "") { + return value; + } + + let remainingKeyPath: string | null = keyPath; + let object = value; + + while (remainingKeyPath !== null) { + let identifier; + + const i = remainingKeyPath.indexOf("."); + if (i >= 0) { + identifier = remainingKeyPath.slice(0, i); + remainingKeyPath = remainingKeyPath.slice(i + 1); + } else { + identifier = remainingKeyPath; + remainingKeyPath = null; + } + + if (!object.hasOwnProperty(identifier)) { + return; + } + + object = object[identifier]; + } + + return object; +}; + +export default extractKey; diff --git a/packages/idb-bridge/src/util/fakeDOMStringList.ts b/packages/idb-bridge/src/util/fakeDOMStringList.ts new file mode 100644 index 000000000..5add17588 --- /dev/null +++ b/packages/idb-bridge/src/util/fakeDOMStringList.ts @@ -0,0 +1,37 @@ +/* + * Copyright 2017 Jeremy Scheff + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express + * or implied. See the License for the specific language governing + * permissions and limitations under the License. + */ + +import { FakeDOMStringList } from "./types"; + +// Would be nicer to sublcass Array, but I'd have to sacrifice Node 4 support to do that. + +const fakeDOMStringList = (arr: string[]): FakeDOMStringList => { + const arr2 = arr.slice(); + + Object.defineProperty(arr2, "contains", { + // tslint:disable-next-line object-literal-shorthand + value: (value: string) => arr2.indexOf(value) >= 0, + }); + + Object.defineProperty(arr2, "item", { + // tslint:disable-next-line object-literal-shorthand + value: (i: number) => arr2[i], + }); + + return arr2 as FakeDOMStringList; +}; + +export default fakeDOMStringList; diff --git a/packages/idb-bridge/src/util/injectKey.ts b/packages/idb-bridge/src/util/injectKey.ts new file mode 100644 index 000000000..89d3a01d8 --- /dev/null +++ b/packages/idb-bridge/src/util/injectKey.ts @@ -0,0 +1,48 @@ +import { KeyPath, Value, Key } from "./types"; +import canInjectKey from "./canInjectKey"; +import { DataError } from "./errors"; +import structuredClone from "./structuredClone"; + +export function injectKey(keyPath: KeyPath, value: Value, key: Key): Value { + if (Array.isArray(keyPath)) { + // tslint:disable-next-line max-line-length + throw new Error( + "The key paths used in this section are always strings and never sequences, since it is not possible to create a object store which has a key generator and also has a key path that is a sequence.", + ); + } + + const identifiers = keyPath.split("."); + if (identifiers.length === 0) { + throw new Error("Assert: identifiers is not empty"); + } + + const lastIdentifier = identifiers.pop(); + + if (lastIdentifier === null || lastIdentifier === undefined) { + throw Error(); + } + + for (const identifier of identifiers) { + if (typeof value !== "object" && !Array.isArray(value)) { + return false; + } + + const hop = value.hasOwnProperty(identifier); + if (!hop) { + return true; + } + + value = value[identifier]; + } + + if (!(typeof value === "object" || Array.isArray(value))) { + throw new Error("can't inject key"); + } + + const newValue = structuredClone(value); + newValue[lastIdentifier] = structuredClone(key); + + return newValue; +} + +export default injectKey; \ No newline at end of file diff --git a/packages/idb-bridge/src/util/makeStoreKeyValue.ts b/packages/idb-bridge/src/util/makeStoreKeyValue.ts new file mode 100644 index 000000000..4850cec26 --- /dev/null +++ b/packages/idb-bridge/src/util/makeStoreKeyValue.ts @@ -0,0 +1,92 @@ +import { Value, Key, KeyPath } from "./types"; +import extractKey from "./extractKey"; +import { DataError } from "./errors"; +import valueToKey from "./valueToKey"; +import structuredClone from "./structuredClone"; +import injectKey from "./injectKey"; + +export interface StoreKeyResult { + updatedKeyGenerator: number; + key: Key; + value: Value; +} + +export function makeStoreKeyValue( + value: Value, + key: Key | undefined, + currentKeyGenerator: number, + autoIncrement: boolean, + keyPath: KeyPath | null, +): StoreKeyResult { + const haveKey = key !== undefined && key !== null; + const haveKeyPath = keyPath !== null && keyPath !== undefined; + + // This models a decision table on (haveKey, haveKeyPath, autoIncrement) + + value = structuredClone(value); + + if (haveKey) { + if (haveKeyPath) { + // (yes, yes, no) + // (yes, yes, yes) + throw new DataError(); + } else { + if (autoIncrement) { + // (yes, no, yes) + key = valueToKey(key)!; + let updatedKeyGenerator: number; + if (typeof key !== "number") { + updatedKeyGenerator = currentKeyGenerator; + } else { + updatedKeyGenerator = key; + } + return { + key: key!, + value: value, + updatedKeyGenerator, + }; + } else { + // (yes, no, no) + throw new DataError(); + } + } + } else { + if (haveKeyPath) { + if (autoIncrement) { + // (no, yes, yes) + + let updatedKeyGenerator: number; + const maybeInlineKey = extractKey(keyPath!, value); + if (maybeInlineKey === undefined) { + value = injectKey(keyPath!, value, currentKeyGenerator); + key = currentKeyGenerator; + updatedKeyGenerator = currentKeyGenerator + 1; + } else if (typeof maybeInlineKey === "number") { + key = maybeInlineKey; + updatedKeyGenerator = maybeInlineKey; + } else { + key = maybeInlineKey; + updatedKeyGenerator = currentKeyGenerator + 1; + } + return { + key: key, + value: value, + updatedKeyGenerator, + } + } else { + // (no, yes, no) + key = extractKey(keyPath!, value); + key = valueToKey(key); + return { + key: key!, + value: value, + updatedKeyGenerator: currentKeyGenerator, + }; + } + } else { + // (no, no, yes) + // (no, no, no) + throw new DataError(); + } + } +} \ No newline at end of file diff --git a/packages/idb-bridge/src/util/openPromise.ts b/packages/idb-bridge/src/util/openPromise.ts new file mode 100644 index 000000000..3f6da81bd --- /dev/null +++ b/packages/idb-bridge/src/util/openPromise.ts @@ -0,0 +1,22 @@ +function openPromise(): { + promise: Promise; + resolve: (v?: T | PromiseLike) => void; + reject: (err?: any) => void; +} { + let resolve; + let reject; + const promise = new Promise((resolve2, reject2) => { + resolve = resolve2; + reject = reject2; + }); + if (!resolve) { + throw Error("broken invariant"); + } + if (!reject) { + throw Error("broken invariant"); + } + + return { promise, resolve, reject }; +} + +export default openPromise; diff --git a/packages/idb-bridge/src/util/queueTask.ts b/packages/idb-bridge/src/util/queueTask.ts new file mode 100644 index 000000000..7d59c2263 --- /dev/null +++ b/packages/idb-bridge/src/util/queueTask.ts @@ -0,0 +1,21 @@ +/* + Copyright 2019 Florian Dold + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express + or implied. See the License for the specific language governing + permissions and limitations under the License. + */ + + export function queueTask(fn: () => void) { + setImmediate(fn); + } + + export default queueTask; \ No newline at end of file diff --git a/packages/idb-bridge/src/util/structuredClone.ts b/packages/idb-bridge/src/util/structuredClone.ts new file mode 100644 index 000000000..8b6b61315 --- /dev/null +++ b/packages/idb-bridge/src/util/structuredClone.ts @@ -0,0 +1,15 @@ + +function structuredCloneImpl(val: any, visited: WeakMap): any { + // FIXME: replace with real implementation! + return JSON.parse(JSON.stringify(val)); +} + +/** + * Structured clone for IndexedDB. + */ +export function structuredClone(val: any): any { + const visited: WeakMap = new WeakMap(); + return structuredCloneImpl(val, visited); +} + +export default structuredClone; \ No newline at end of file diff --git a/packages/idb-bridge/src/util/types.ts b/packages/idb-bridge/src/util/types.ts new file mode 100644 index 000000000..7aea22ab1 --- /dev/null +++ b/packages/idb-bridge/src/util/types.ts @@ -0,0 +1,73 @@ +/* + Copyright 2017 Jeremy Scheff + Copyright 2019 Florian Dold + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express + or implied. See the License for the specific language governing + permissions and limitations under the License. +*/ + +import BridgeIDBRequest from "../BridgeIDBRequest"; +import BridgeIDBKeyRange from "../BridgeIDBKeyRange"; +import BridgeIDBIndex from "../BridgeIDBIndex"; +import BridgeIBObjectStore from "../BridgeIDBObjectStore"; + +interface EventInCallback extends Event { + target: any; + error: Error | null; +} + +export type EventCallback = (event: EventInCallback) => void; + +export type EventType = + | "abort" + | "blocked" + | "complete" + | "error" + | "success" + | "upgradeneeded" + | "versionchange"; + +export type CursorSource = BridgeIDBIndex | BridgeIBObjectStore; + + +export interface FakeDOMStringList extends Array { + contains: (value: string) => boolean; + item: (i: number) => string | undefined; +} + +export type BridgeIDBCursorDirection = "next" | "nextunique" | "prev" | "prevunique"; + +export type KeyPath = string | string[]; + +export type Key = any; + +export type CursorRange = Key | BridgeIDBKeyRange | undefined; + +export type Value = any; + +export interface Record { + key: Key; + value: Key | Value; // For indexes, will be Key. For object stores, will be Value. +} + +export type TransactionMode = "readonly" | "readwrite" | "versionchange"; + +export interface BridgeIDBDatabaseInfo { + name: string; + version: number +}; + +export interface RequestObj { + operation: () => Promise; + request?: BridgeIDBRequest | undefined; + source?: any; +} diff --git a/packages/idb-bridge/src/util/validateKeyPath.ts b/packages/idb-bridge/src/util/validateKeyPath.ts new file mode 100644 index 000000000..18552a5d4 --- /dev/null +++ b/packages/idb-bridge/src/util/validateKeyPath.ts @@ -0,0 +1,77 @@ +/* + Copyright 2017 Jeremy Scheff + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express + or implied. See the License for the specific language governing + permissions and limitations under the License. +*/ + +import { KeyPath } from "./types"; + +// http://www.w3.org/TR/2015/REC-IndexedDB-20150108/#dfn-valid-key-path +const validateKeyPath = (keyPath: KeyPath, parent?: "array" | "string") => { + // This doesn't make sense to me based on the spec, but it is needed to pass the W3C KeyPath tests (see same + // comment in extractKey) + if ( + keyPath !== undefined && + keyPath !== null && + typeof keyPath !== "string" && + keyPath.toString && + (parent === "array" || !Array.isArray(keyPath)) + ) { + keyPath = keyPath.toString(); + } + + if (typeof keyPath === "string") { + if (keyPath === "" && parent !== "string") { + return; + } + try { + // https://mathiasbynens.be/demo/javascript-identifier-regex for ECMAScript 5.1 / Unicode v7.0.0, with + // reserved words at beginning removed + // tslint:disable-next-line max-line-length + const validIdentifierRegex = /^(?:[\$A-Z_a-z\xAA\xB5\xBA\xC0-\xD6\xD8-\xF6\xF8-\u02C1\u02C6-\u02D1\u02E0-\u02E4\u02EC\u02EE\u0370-\u0374\u0376\u0377\u037A-\u037D\u037F\u0386\u0388-\u038A\u038C\u038E-\u03A1\u03A3-\u03F5\u03F7-\u0481\u048A-\u052F\u0531-\u0556\u0559\u0561-\u0587\u05D0-\u05EA\u05F0-\u05F2\u0620-\u064A\u066E\u066F\u0671-\u06D3\u06D5\u06E5\u06E6\u06EE\u06EF\u06FA-\u06FC\u06FF\u0710\u0712-\u072F\u074D-\u07A5\u07B1\u07CA-\u07EA\u07F4\u07F5\u07FA\u0800-\u0815\u081A\u0824\u0828\u0840-\u0858\u08A0-\u08B2\u0904-\u0939\u093D\u0950\u0958-\u0961\u0971-\u0980\u0985-\u098C\u098F\u0990\u0993-\u09A8\u09AA-\u09B0\u09B2\u09B6-\u09B9\u09BD\u09CE\u09DC\u09DD\u09DF-\u09E1\u09F0\u09F1\u0A05-\u0A0A\u0A0F\u0A10\u0A13-\u0A28\u0A2A-\u0A30\u0A32\u0A33\u0A35\u0A36\u0A38\u0A39\u0A59-\u0A5C\u0A5E\u0A72-\u0A74\u0A85-\u0A8D\u0A8F-\u0A91\u0A93-\u0AA8\u0AAA-\u0AB0\u0AB2\u0AB3\u0AB5-\u0AB9\u0ABD\u0AD0\u0AE0\u0AE1\u0B05-\u0B0C\u0B0F\u0B10\u0B13-\u0B28\u0B2A-\u0B30\u0B32\u0B33\u0B35-\u0B39\u0B3D\u0B5C\u0B5D\u0B5F-\u0B61\u0B71\u0B83\u0B85-\u0B8A\u0B8E-\u0B90\u0B92-\u0B95\u0B99\u0B9A\u0B9C\u0B9E\u0B9F\u0BA3\u0BA4\u0BA8-\u0BAA\u0BAE-\u0BB9\u0BD0\u0C05-\u0C0C\u0C0E-\u0C10\u0C12-\u0C28\u0C2A-\u0C39\u0C3D\u0C58\u0C59\u0C60\u0C61\u0C85-\u0C8C\u0C8E-\u0C90\u0C92-\u0CA8\u0CAA-\u0CB3\u0CB5-\u0CB9\u0CBD\u0CDE\u0CE0\u0CE1\u0CF1\u0CF2\u0D05-\u0D0C\u0D0E-\u0D10\u0D12-\u0D3A\u0D3D\u0D4E\u0D60\u0D61\u0D7A-\u0D7F\u0D85-\u0D96\u0D9A-\u0DB1\u0DB3-\u0DBB\u0DBD\u0DC0-\u0DC6\u0E01-\u0E30\u0E32\u0E33\u0E40-\u0E46\u0E81\u0E82\u0E84\u0E87\u0E88\u0E8A\u0E8D\u0E94-\u0E97\u0E99-\u0E9F\u0EA1-\u0EA3\u0EA5\u0EA7\u0EAA\u0EAB\u0EAD-\u0EB0\u0EB2\u0EB3\u0EBD\u0EC0-\u0EC4\u0EC6\u0EDC-\u0EDF\u0F00\u0F40-\u0F47\u0F49-\u0F6C\u0F88-\u0F8C\u1000-\u102A\u103F\u1050-\u1055\u105A-\u105D\u1061\u1065\u1066\u106E-\u1070\u1075-\u1081\u108E\u10A0-\u10C5\u10C7\u10CD\u10D0-\u10FA\u10FC-\u1248\u124A-\u124D\u1250-\u1256\u1258\u125A-\u125D\u1260-\u1288\u128A-\u128D\u1290-\u12B0\u12B2-\u12B5\u12B8-\u12BE\u12C0\u12C2-\u12C5\u12C8-\u12D6\u12D8-\u1310\u1312-\u1315\u1318-\u135A\u1380-\u138F\u13A0-\u13F4\u1401-\u166C\u166F-\u167F\u1681-\u169A\u16A0-\u16EA\u16EE-\u16F8\u1700-\u170C\u170E-\u1711\u1720-\u1731\u1740-\u1751\u1760-\u176C\u176E-\u1770\u1780-\u17B3\u17D7\u17DC\u1820-\u1877\u1880-\u18A8\u18AA\u18B0-\u18F5\u1900-\u191E\u1950-\u196D\u1970-\u1974\u1980-\u19AB\u19C1-\u19C7\u1A00-\u1A16\u1A20-\u1A54\u1AA7\u1B05-\u1B33\u1B45-\u1B4B\u1B83-\u1BA0\u1BAE\u1BAF\u1BBA-\u1BE5\u1C00-\u1C23\u1C4D-\u1C4F\u1C5A-\u1C7D\u1CE9-\u1CEC\u1CEE-\u1CF1\u1CF5\u1CF6\u1D00-\u1DBF\u1E00-\u1F15\u1F18-\u1F1D\u1F20-\u1F45\u1F48-\u1F4D\u1F50-\u1F57\u1F59\u1F5B\u1F5D\u1F5F-\u1F7D\u1F80-\u1FB4\u1FB6-\u1FBC\u1FBE\u1FC2-\u1FC4\u1FC6-\u1FCC\u1FD0-\u1FD3\u1FD6-\u1FDB\u1FE0-\u1FEC\u1FF2-\u1FF4\u1FF6-\u1FFC\u2071\u207F\u2090-\u209C\u2102\u2107\u210A-\u2113\u2115\u2119-\u211D\u2124\u2126\u2128\u212A-\u212D\u212F-\u2139\u213C-\u213F\u2145-\u2149\u214E\u2160-\u2188\u2C00-\u2C2E\u2C30-\u2C5E\u2C60-\u2CE4\u2CEB-\u2CEE\u2CF2\u2CF3\u2D00-\u2D25\u2D27\u2D2D\u2D30-\u2D67\u2D6F\u2D80-\u2D96\u2DA0-\u2DA6\u2DA8-\u2DAE\u2DB0-\u2DB6\u2DB8-\u2DBE\u2DC0-\u2DC6\u2DC8-\u2DCE\u2DD0-\u2DD6\u2DD8-\u2DDE\u2E2F\u3005-\u3007\u3021-\u3029\u3031-\u3035\u3038-\u303C\u3041-\u3096\u309D-\u309F\u30A1-\u30FA\u30FC-\u30FF\u3105-\u312D\u3131-\u318E\u31A0-\u31BA\u31F0-\u31FF\u3400-\u4DB5\u4E00-\u9FCC\uA000-\uA48C\uA4D0-\uA4FD\uA500-\uA60C\uA610-\uA61F\uA62A\uA62B\uA640-\uA66E\uA67F-\uA69D\uA6A0-\uA6EF\uA717-\uA71F\uA722-\uA788\uA78B-\uA78E\uA790-\uA7AD\uA7B0\uA7B1\uA7F7-\uA801\uA803-\uA805\uA807-\uA80A\uA80C-\uA822\uA840-\uA873\uA882-\uA8B3\uA8F2-\uA8F7\uA8FB\uA90A-\uA925\uA930-\uA946\uA960-\uA97C\uA984-\uA9B2\uA9CF\uA9E0-\uA9E4\uA9E6-\uA9EF\uA9FA-\uA9FE\uAA00-\uAA28\uAA40-\uAA42\uAA44-\uAA4B\uAA60-\uAA76\uAA7A\uAA7E-\uAAAF\uAAB1\uAAB5\uAAB6\uAAB9-\uAABD\uAAC0\uAAC2\uAADB-\uAADD\uAAE0-\uAAEA\uAAF2-\uAAF4\uAB01-\uAB06\uAB09-\uAB0E\uAB11-\uAB16\uAB20-\uAB26\uAB28-\uAB2E\uAB30-\uAB5A\uAB5C-\uAB5F\uAB64\uAB65\uABC0-\uABE2\uAC00-\uD7A3\uD7B0-\uD7C6\uD7CB-\uD7FB\uF900-\uFA6D\uFA70-\uFAD9\uFB00-\uFB06\uFB13-\uFB17\uFB1D\uFB1F-\uFB28\uFB2A-\uFB36\uFB38-\uFB3C\uFB3E\uFB40\uFB41\uFB43\uFB44\uFB46-\uFBB1\uFBD3-\uFD3D\uFD50-\uFD8F\uFD92-\uFDC7\uFDF0-\uFDFB\uFE70-\uFE74\uFE76-\uFEFC\uFF21-\uFF3A\uFF41-\uFF5A\uFF66-\uFFBE\uFFC2-\uFFC7\uFFCA-\uFFCF\uFFD2-\uFFD7\uFFDA-\uFFDC])(?:[\$0-9A-Z_a-z\xAA\xB5\xBA\xC0-\xD6\xD8-\xF6\xF8-\u02C1\u02C6-\u02D1\u02E0-\u02E4\u02EC\u02EE\u0300-\u0374\u0376\u0377\u037A-\u037D\u037F\u0386\u0388-\u038A\u038C\u038E-\u03A1\u03A3-\u03F5\u03F7-\u0481\u0483-\u0487\u048A-\u052F\u0531-\u0556\u0559\u0561-\u0587\u0591-\u05BD\u05BF\u05C1\u05C2\u05C4\u05C5\u05C7\u05D0-\u05EA\u05F0-\u05F2\u0610-\u061A\u0620-\u0669\u066E-\u06D3\u06D5-\u06DC\u06DF-\u06E8\u06EA-\u06FC\u06FF\u0710-\u074A\u074D-\u07B1\u07C0-\u07F5\u07FA\u0800-\u082D\u0840-\u085B\u08A0-\u08B2\u08E4-\u0963\u0966-\u096F\u0971-\u0983\u0985-\u098C\u098F\u0990\u0993-\u09A8\u09AA-\u09B0\u09B2\u09B6-\u09B9\u09BC-\u09C4\u09C7\u09C8\u09CB-\u09CE\u09D7\u09DC\u09DD\u09DF-\u09E3\u09E6-\u09F1\u0A01-\u0A03\u0A05-\u0A0A\u0A0F\u0A10\u0A13-\u0A28\u0A2A-\u0A30\u0A32\u0A33\u0A35\u0A36\u0A38\u0A39\u0A3C\u0A3E-\u0A42\u0A47\u0A48\u0A4B-\u0A4D\u0A51\u0A59-\u0A5C\u0A5E\u0A66-\u0A75\u0A81-\u0A83\u0A85-\u0A8D\u0A8F-\u0A91\u0A93-\u0AA8\u0AAA-\u0AB0\u0AB2\u0AB3\u0AB5-\u0AB9\u0ABC-\u0AC5\u0AC7-\u0AC9\u0ACB-\u0ACD\u0AD0\u0AE0-\u0AE3\u0AE6-\u0AEF\u0B01-\u0B03\u0B05-\u0B0C\u0B0F\u0B10\u0B13-\u0B28\u0B2A-\u0B30\u0B32\u0B33\u0B35-\u0B39\u0B3C-\u0B44\u0B47\u0B48\u0B4B-\u0B4D\u0B56\u0B57\u0B5C\u0B5D\u0B5F-\u0B63\u0B66-\u0B6F\u0B71\u0B82\u0B83\u0B85-\u0B8A\u0B8E-\u0B90\u0B92-\u0B95\u0B99\u0B9A\u0B9C\u0B9E\u0B9F\u0BA3\u0BA4\u0BA8-\u0BAA\u0BAE-\u0BB9\u0BBE-\u0BC2\u0BC6-\u0BC8\u0BCA-\u0BCD\u0BD0\u0BD7\u0BE6-\u0BEF\u0C00-\u0C03\u0C05-\u0C0C\u0C0E-\u0C10\u0C12-\u0C28\u0C2A-\u0C39\u0C3D-\u0C44\u0C46-\u0C48\u0C4A-\u0C4D\u0C55\u0C56\u0C58\u0C59\u0C60-\u0C63\u0C66-\u0C6F\u0C81-\u0C83\u0C85-\u0C8C\u0C8E-\u0C90\u0C92-\u0CA8\u0CAA-\u0CB3\u0CB5-\u0CB9\u0CBC-\u0CC4\u0CC6-\u0CC8\u0CCA-\u0CCD\u0CD5\u0CD6\u0CDE\u0CE0-\u0CE3\u0CE6-\u0CEF\u0CF1\u0CF2\u0D01-\u0D03\u0D05-\u0D0C\u0D0E-\u0D10\u0D12-\u0D3A\u0D3D-\u0D44\u0D46-\u0D48\u0D4A-\u0D4E\u0D57\u0D60-\u0D63\u0D66-\u0D6F\u0D7A-\u0D7F\u0D82\u0D83\u0D85-\u0D96\u0D9A-\u0DB1\u0DB3-\u0DBB\u0DBD\u0DC0-\u0DC6\u0DCA\u0DCF-\u0DD4\u0DD6\u0DD8-\u0DDF\u0DE6-\u0DEF\u0DF2\u0DF3\u0E01-\u0E3A\u0E40-\u0E4E\u0E50-\u0E59\u0E81\u0E82\u0E84\u0E87\u0E88\u0E8A\u0E8D\u0E94-\u0E97\u0E99-\u0E9F\u0EA1-\u0EA3\u0EA5\u0EA7\u0EAA\u0EAB\u0EAD-\u0EB9\u0EBB-\u0EBD\u0EC0-\u0EC4\u0EC6\u0EC8-\u0ECD\u0ED0-\u0ED9\u0EDC-\u0EDF\u0F00\u0F18\u0F19\u0F20-\u0F29\u0F35\u0F37\u0F39\u0F3E-\u0F47\u0F49-\u0F6C\u0F71-\u0F84\u0F86-\u0F97\u0F99-\u0FBC\u0FC6\u1000-\u1049\u1050-\u109D\u10A0-\u10C5\u10C7\u10CD\u10D0-\u10FA\u10FC-\u1248\u124A-\u124D\u1250-\u1256\u1258\u125A-\u125D\u1260-\u1288\u128A-\u128D\u1290-\u12B0\u12B2-\u12B5\u12B8-\u12BE\u12C0\u12C2-\u12C5\u12C8-\u12D6\u12D8-\u1310\u1312-\u1315\u1318-\u135A\u135D-\u135F\u1380-\u138F\u13A0-\u13F4\u1401-\u166C\u166F-\u167F\u1681-\u169A\u16A0-\u16EA\u16EE-\u16F8\u1700-\u170C\u170E-\u1714\u1720-\u1734\u1740-\u1753\u1760-\u176C\u176E-\u1770\u1772\u1773\u1780-\u17D3\u17D7\u17DC\u17DD\u17E0-\u17E9\u180B-\u180D\u1810-\u1819\u1820-\u1877\u1880-\u18AA\u18B0-\u18F5\u1900-\u191E\u1920-\u192B\u1930-\u193B\u1946-\u196D\u1970-\u1974\u1980-\u19AB\u19B0-\u19C9\u19D0-\u19D9\u1A00-\u1A1B\u1A20-\u1A5E\u1A60-\u1A7C\u1A7F-\u1A89\u1A90-\u1A99\u1AA7\u1AB0-\u1ABD\u1B00-\u1B4B\u1B50-\u1B59\u1B6B-\u1B73\u1B80-\u1BF3\u1C00-\u1C37\u1C40-\u1C49\u1C4D-\u1C7D\u1CD0-\u1CD2\u1CD4-\u1CF6\u1CF8\u1CF9\u1D00-\u1DF5\u1DFC-\u1F15\u1F18-\u1F1D\u1F20-\u1F45\u1F48-\u1F4D\u1F50-\u1F57\u1F59\u1F5B\u1F5D\u1F5F-\u1F7D\u1F80-\u1FB4\u1FB6-\u1FBC\u1FBE\u1FC2-\u1FC4\u1FC6-\u1FCC\u1FD0-\u1FD3\u1FD6-\u1FDB\u1FE0-\u1FEC\u1FF2-\u1FF4\u1FF6-\u1FFC\u200C\u200D\u203F\u2040\u2054\u2071\u207F\u2090-\u209C\u20D0-\u20DC\u20E1\u20E5-\u20F0\u2102\u2107\u210A-\u2113\u2115\u2119-\u211D\u2124\u2126\u2128\u212A-\u212D\u212F-\u2139\u213C-\u213F\u2145-\u2149\u214E\u2160-\u2188\u2C00-\u2C2E\u2C30-\u2C5E\u2C60-\u2CE4\u2CEB-\u2CF3\u2D00-\u2D25\u2D27\u2D2D\u2D30-\u2D67\u2D6F\u2D7F-\u2D96\u2DA0-\u2DA6\u2DA8-\u2DAE\u2DB0-\u2DB6\u2DB8-\u2DBE\u2DC0-\u2DC6\u2DC8-\u2DCE\u2DD0-\u2DD6\u2DD8-\u2DDE\u2DE0-\u2DFF\u2E2F\u3005-\u3007\u3021-\u302F\u3031-\u3035\u3038-\u303C\u3041-\u3096\u3099\u309A\u309D-\u309F\u30A1-\u30FA\u30FC-\u30FF\u3105-\u312D\u3131-\u318E\u31A0-\u31BA\u31F0-\u31FF\u3400-\u4DB5\u4E00-\u9FCC\uA000-\uA48C\uA4D0-\uA4FD\uA500-\uA60C\uA610-\uA62B\uA640-\uA66F\uA674-\uA67D\uA67F-\uA69D\uA69F-\uA6F1\uA717-\uA71F\uA722-\uA788\uA78B-\uA78E\uA790-\uA7AD\uA7B0\uA7B1\uA7F7-\uA827\uA840-\uA873\uA880-\uA8C4\uA8D0-\uA8D9\uA8E0-\uA8F7\uA8FB\uA900-\uA92D\uA930-\uA953\uA960-\uA97C\uA980-\uA9C0\uA9CF-\uA9D9\uA9E0-\uA9FE\uAA00-\uAA36\uAA40-\uAA4D\uAA50-\uAA59\uAA60-\uAA76\uAA7A-\uAAC2\uAADB-\uAADD\uAAE0-\uAAEF\uAAF2-\uAAF6\uAB01-\uAB06\uAB09-\uAB0E\uAB11-\uAB16\uAB20-\uAB26\uAB28-\uAB2E\uAB30-\uAB5A\uAB5C-\uAB5F\uAB64\uAB65\uABC0-\uABEA\uABEC\uABED\uABF0-\uABF9\uAC00-\uD7A3\uD7B0-\uD7C6\uD7CB-\uD7FB\uF900-\uFA6D\uFA70-\uFAD9\uFB00-\uFB06\uFB13-\uFB17\uFB1D-\uFB28\uFB2A-\uFB36\uFB38-\uFB3C\uFB3E\uFB40\uFB41\uFB43\uFB44\uFB46-\uFBB1\uFBD3-\uFD3D\uFD50-\uFD8F\uFD92-\uFDC7\uFDF0-\uFDFB\uFE00-\uFE0F\uFE20-\uFE2D\uFE33\uFE34\uFE4D-\uFE4F\uFE70-\uFE74\uFE76-\uFEFC\uFF10-\uFF19\uFF21-\uFF3A\uFF3F\uFF41-\uFF5A\uFF66-\uFFBE\uFFC2-\uFFC7\uFFCA-\uFFCF\uFFD2-\uFFD7\uFFDA-\uFFDC])*$/; + if (keyPath.length >= 1 && validIdentifierRegex.test(keyPath)) { + return; + } + } catch (err) { + throw new SyntaxError(err.message); + } + if (keyPath.indexOf(" ") >= 0) { + throw new SyntaxError( + "The keypath argument contains an invalid key path (no spaces allowed).", + ); + } + } + + if (Array.isArray(keyPath) && keyPath.length > 0) { + if (parent) { + // No nested arrays + throw new SyntaxError( + "The keypath argument contains an invalid key path (nested arrays).", + ); + } + for (const part of keyPath) { + validateKeyPath(part, "array"); + } + return; + } else if (typeof keyPath === "string" && keyPath.indexOf(".") >= 0) { + keyPath = keyPath.split("."); + for (const part of keyPath) { + validateKeyPath(part, "string"); + } + return; + } + + throw new SyntaxError(); +}; + +export default validateKeyPath; diff --git a/packages/idb-bridge/src/util/valueToKey.ts b/packages/idb-bridge/src/util/valueToKey.ts new file mode 100644 index 000000000..3a9e36786 --- /dev/null +++ b/packages/idb-bridge/src/util/valueToKey.ts @@ -0,0 +1,70 @@ +/* + Copyright 2017 Jeremy Scheff + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express + or implied. See the License for the specific language governing + permissions and limitations under the License. + */ + + +import { DataError } from "./errors"; +import { Key } from "./types"; + +// https://w3c.github.io/IndexedDB/#convert-a-value-to-a-input +function valueToKey(input: any, seen?: Set): Key | Key[] { + if (typeof input === "number") { + if (isNaN(input)) { + throw new DataError(); + } + return input; + } else if (input instanceof Date) { + const ms = input.valueOf(); + if (isNaN(ms)) { + throw new DataError(); + } + return new Date(ms); + } else if (typeof input === "string") { + return input; + } else if ( + input instanceof ArrayBuffer || + (typeof ArrayBuffer !== "undefined" && + ArrayBuffer.isView && + ArrayBuffer.isView(input)) + ) { + if (input instanceof ArrayBuffer) { + return new Uint8Array(input).buffer; + } + return new Uint8Array(input.buffer).buffer; + } else if (Array.isArray(input)) { + if (seen === undefined) { + seen = new Set(); + } else if (seen.has(input)) { + throw new DataError(); + } + seen.add(input); + + const keys = []; + for (let i = 0; i < input.length; i++) { + const hop = input.hasOwnProperty(i); + if (!hop) { + throw new DataError(); + } + const entry = input[i]; + const key = valueToKey(entry, seen); + keys.push(key); + } + return keys; + } else { + throw new DataError(); + } +}; + +export default valueToKey; -- cgit v1.2.3