From f93839558d528f600b10fbe816914e7ff91fca64 Mon Sep 17 00:00:00 2001 From: Florian Dold Date: Thu, 8 Jun 2017 12:15:45 +0200 Subject: aa trees --- src/memidb-test.ts | 114 ----- src/memidb.ts | 1086 --------------------------------------------- src/memidb/aatree-test.ts | 84 ++++ src/memidb/aatree.ts | 388 ++++++++++++++++ src/memidb/memidb-test.ts | 114 +++++ src/memidb/memidb.ts | 961 +++++++++++++++++++++++++++++++++++++++ 6 files changed, 1547 insertions(+), 1200 deletions(-) delete mode 100644 src/memidb-test.ts delete mode 100644 src/memidb.ts create mode 100644 src/memidb/aatree-test.ts create mode 100644 src/memidb/aatree.ts create mode 100644 src/memidb/memidb-test.ts create mode 100644 src/memidb/memidb.ts (limited to 'src') diff --git a/src/memidb-test.ts b/src/memidb-test.ts deleted file mode 100644 index 8f8498a6e..000000000 --- a/src/memidb-test.ts +++ /dev/null @@ -1,114 +0,0 @@ -/* - This file is part of TALER - (C) 2017 Inria and GNUnet e.V. - - TALER is free software; you can redistribute it and/or modify it under the - terms of the GNU General Public License as published by the Free Software - Foundation; either version 3, or (at your option) any later version. - - TALER is distributed in the hope that it will be useful, but WITHOUT ANY - WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR - A PARTICULAR PURPOSE. See the GNU General Public License for more details. - - You should have received a copy of the GNU General Public License along with - TALER; see the file COPYING. If not, see - */ - -import {test} from "ava"; -import * as memidb from "./memidb"; - -test.cb("db open", (t) => { - let ncb = 0; - const idb = new memidb.MemoryIDBFactory(); - const req = idb.open("testdb"); - let called = false; - req.onupgradeneeded = (evt) => { - ncb += 1; - called = true; - t.is(req.result, evt.target); - t.is(evt.oldVersion, 0); - t.is(evt.newVersion, 1); - t.truthy(req.result); - t.pass(); - } - req.onsuccess = (evt) => { - t.is(ncb, 1); - t.is(req.result, evt.target); - t.truthy(req.result); - t.end(); - } -}); - -test.cb("store creation", (t) => { - const idb = new memidb.MemoryIDBFactory(); - const req = idb.open("testdb"); - req.onupgradeneeded = (evt) => { - const db: IDBDatabase = req.result; - - const store1 = db.createObjectStore("b-store"); - t.is(store1.name, "b-store"); - t.deepEqual(Array.from(db.objectStoreNames), ["b-store"]); - - const store2 = db.createObjectStore("a-store"); - t.is(store2.name, "a-store"); - t.deepEqual(Array.from(db.objectStoreNames), ["a-store", "b-store"]); - - const store3 = db.createObjectStore("c-store"); - t.is(store3.name, "c-store"); - t.deepEqual(Array.from(db.objectStoreNames), ["a-store", "b-store", "c-store"]); - t.pass(); - } - req.onsuccess = (evt) => { - t.end(); - } -}); - - -test.cb("put and get", (t) => { - const idb = new memidb.MemoryIDBFactory(); - const req = idb.open("testdb"); - req.onupgradeneeded = (evt) => { - const db: IDBDatabase = req.result; - const store1 = db.createObjectStore("mystore"); - store1.put({answer: 42}, "a"); - } - req.onsuccess = (evt) => { - t.end() - } -}); - - -test("key path evaluation", (t) => { - const obj = { - a: { - b: { - c: 42, - }, - }, - b: "hello", - "": "spam", - arr: ["foo", "bar"], - } - t.deepEqual(memidb.evaluateKeyPath(obj, ""), obj); - t.deepEqual(memidb.evaluateKeyPath(obj, "a.b.c"), 42); - t.deepEqual(memidb.evaluateKeyPath(obj, "a.b"), {c: 42}); - t.deepEqual(memidb.evaluateKeyPath(obj, "foo"), undefined); - t.deepEqual(memidb.evaluateKeyPath(obj, ["a.b.c", "foo"]), undefined); - t.deepEqual(memidb.evaluateKeyPath(obj, ["a.b.c", "b"]), [42, "hello"]); - t.deepEqual(memidb.evaluateKeyPath(obj, "arr.0"), "foo"); - t.deepEqual(memidb.evaluateKeyPath(obj, "."), "spam"); -}); - -test("key path evaluation with replacement", (t) => { - const obj: any = { - a: { - b: { - c: 42, - }, - }, - } - memidb.evaluateKeyPath(obj, "a.b.c", 24); - t.is(obj.a.b.c, 24); - memidb.evaluateKeyPath(obj, "a.b", 24); - t.is(obj.a.b, 24); -}); diff --git a/src/memidb.ts b/src/memidb.ts deleted file mode 100644 index 3348d97a7..000000000 --- a/src/memidb.ts +++ /dev/null @@ -1,1086 +0,0 @@ -/* - This file is part of TALER - (C) 2017 Inria and GNUnet e.V. - - TALER is free software; you can redistribute it and/or modify it under the - terms of the GNU General Public License as published by the Free Software - Foundation; either version 3, or (at your option) any later version. - - TALER is distributed in the hope that it will be useful, but WITHOUT ANY - WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR - A PARTICULAR PURPOSE. See the GNU General Public License for more details. - - You should have received a copy of the GNU General Public License along with - TALER; see the file COPYING. If not, see - */ - -/** - * In-memory implementation of the IndexedDB interface. - * - * Transactions support rollback, but they are all run sequentially within the - * same MemoryIDBFactory. - * - * Every operation involves copying the whole database state, making it only - * feasible for small databases. - */ - -/* work in progres ... */ -/* tslint:disable */ - - -const structuredClone = require("structured-clone"); - - -interface Store { - name: string; - keyPath?: string | string[]; - keyGenerator: number; - autoIncrement: boolean; - objects: { [primaryKey: string]: any }; - indices: { [indexName: string]: Index }; -} - -interface Index { - multiEntry: boolean; - unique: boolean; - - /** - * Map the index's key to the primary key. - */ - map: { [indexKey: string]: string[] }; -} - - -interface Database { - name: string; - version: number; - stores: { [name: string]: Store }; -} - - -interface Databases { - [name: string]: Database; -} - - -/** - * Resolved promise, used to schedule various things - * by calling .next on it. - */ -const alreadyResolved = Promise.resolve(); - - -class MyDomStringList extends Array implements DOMStringList { - contains(s: string) { - for (let i = 0; i < this.length; i++) { - if (s === this[i]) { - return true; - } - } - return false; - } - item(i: number) { - return this[i]; - } -} - - - -interface AATreeNode { - left?: AATreeNode; - right?: AATreeNode; - level: number; - key: any; -} - -export type AATree = AATreeNode | undefined; - - -function skew(t: AATreeNode) { - if (t.left && t.left.level == t.level) { - return { - left: t.left.left, - right: t, - key: t.left.key, - level: t.level, - }; - } - return t; -} - - -function split(t: AATreeNode) { - if (t.right && t.right.right && - t.level == t.right.level && - t.right.level == t.right.right.level) { - return { - level: t.level + 1, - key: t.right.key, - left: { - level: t.level, - key: t.key, - left: t.left, - right: t.right.left, - }, - right: { - key: t.right.right.key, - left: t.right.right.left, - level: t.level, - right: t.right.right.right, - }, - } - } - return t; -} - -/** - * Non-destructively insert a new key into an AA tree. - */ -export function treeInsert(t: AATree, k: any): AATreeNode { - if (!t) { - return { - level: 0, - key: k, - } - } - const cmp = compareKeys(k, t.key); - if (cmp == 0) { - return t; - } - let r = Object.assign({}, t); - if (cmp == -1) { - r.left = treeInsert(t.left, k); - } else { - r.right = treeInsert(t.right, k); - } - return split(skew(r)); -} - - -/** - * Check AA tree invariants. Useful for testing. - */ -export function checkInvariants(t: AATree): boolean { - if (!t) { - return true; - } - throw Error("not implemented"); -} - - -function adjust(t: AATreeNode): AATreeNode { - throw Error("not implemented"); -} - -function treeDeleteLargest(t: AATreeNode): { key: any, tree: AATree } { - if (!t.right) { - return { key: t.key, tree: t.left }; - } - const d = treeDeleteLargest(t.right); - return { - key: d.key, - tree: adjust({ - level: t.level, - key: t.key, - left: t.left, - right: d.tree, - }), - }; -} - - -//function treeDelete(t: AATree, k: any): AATreeNode { -// if (!t) { -// return t; -// } -// const cmp = compareKeys(k, t.key); -// if (cmp == 0) { -// if (!t.left) { -// return t.right; -// } -// if (!t.right) { -// return t.left; -// } -// const d = treeDeleteLargest(t.left); -// return adjust({ -// key: d.key, -// left: d.tree, -// right: t.right, -// level: t.level, -// }); -// } else { -// } -//} - - - -class MyKeyRange implements IDBKeyRange { - static only(value: any): IDBKeyRange { - return new MyKeyRange(value, value, false, false); - } - - static bound(lower: any, upper: any, lowerOpen: boolean = false, upperOpen: boolean = false) { - return new MyKeyRange(lower, upper, lowerOpen, upperOpen); - } - - static lowerBound(lower: any, lowerOpen: boolean = false) { - return new MyKeyRange(lower, undefined, lowerOpen, true); - } - - static upperBound(upper: any, upperOpen: boolean = false) { - return new MyKeyRange(undefined, upper, true, upperOpen); - } - - constructor(public lower: any, public upper: any, public lowerOpen: boolean, public upperOpen: boolean) { - } -} - - -/** - * Type guard for an IDBKeyRange. - */ -export function isKeyRange(obj: any): obj is IDBKeyRange { - return (typeof obj === "object" && - "lower" in obj && "upper" in obj && - "lowerOpen" in obj && "upperOpen" in obj); -} - - -function compareKeys(a: any, b: any): -1|0|1 { - throw Error("not implemented") -} - - -class IndexHandle implements IDBIndex { - - _unique: boolean; - _multiEntry: boolean; - - get keyPath(): string | string[] { - throw Error("not implemented"); - } - - get name () { - return this.indexName; - } - - get unique() { - return this._unique; - } - - get multiEntry() { - return this._multiEntry; - } - - constructor(public objectStore: MyObjectStore, public indexName: string) { - } - - count(key?: IDBKeyRange | IDBValidKey): IDBRequest { - throw Error("not implemented"); - } - - get(key: IDBKeyRange | IDBValidKey): IDBRequest { - throw Error("not implemented"); - } - - getKey(key: IDBKeyRange | IDBValidKey): IDBRequest { - throw Error("not implemented"); - } - - openCursor(range?: IDBKeyRange | IDBValidKey, direction?: IDBCursorDirection): IDBRequest { - throw Error("not implemented"); - } - - openKeyCursor(range?: IDBKeyRange | IDBValidKey, direction?: IDBCursorDirection): IDBRequest { - throw Error("not implemented"); - } -} - -class MyRequest implements IDBRequest { - onerror: (this: IDBRequest, ev: Event) => any; - - onsuccess: (this: IDBRequest, ev: Event) => any; - successHandlers: Array<(this: IDBRequest, ev: Event) => any> = []; - - done: boolean = false; - _result: any; - - constructor(public _transaction: Transaction, public runner: () => void) { - } - - callSuccess() { - const ev = new MyEvent("success", this); - if (this.onsuccess) { - this.onsuccess(ev); - } - for (let h of this.successHandlers) { - h.call(this, ev); - } - } - - get error(): DOMException { - return (null as any) as DOMException; - } - - get result(): any { - return this._result; - } - - get source() { - // buggy type definitions don't allow null even though it's in - // the spec. - return (null as any) as (IDBObjectStore | IDBIndex | IDBCursor); - } - - get transaction() { - return this._transaction; - } - - dispatchEvent(evt: Event): boolean { - return false; - } - - get readyState() { - if (this.done) { - return "done"; - } - return "pending"; - } - - removeEventListener(type: string, - listener?: EventListenerOrEventListenerObject, - options?: boolean | EventListenerOptions): void { - throw Error("not implemented"); - } - - addEventListener(type: string, - listener: EventListenerOrEventListenerObject, - useCapture?: boolean): void { - switch (type) { - case "success": - this.successHandlers.push(listener as any); - break; - } - } -} - -class OpenDBRequest extends MyRequest implements IDBOpenDBRequest { - onblocked: (this: IDBOpenDBRequest, ev: Event) => any; - - onupgradeneeded: (this: IDBOpenDBRequest, ev: IDBVersionChangeEvent) => any; - upgradeneededHandlers: Array<(this: IDBOpenDBRequest, ev: IDBVersionChangeEvent) => any> = []; - - callOnupgradeneeded(ev: IDBVersionChangeEvent) { - if (this.onupgradeneeded) { - this.onupgradeneeded(ev); - } - for (let h of this.upgradeneededHandlers) { - h.call(this, ev); - } - } - - removeEventListener(type: string, - listener?: EventListenerOrEventListenerObject, - options?: boolean | EventListenerOptions): void { - throw Error("not implemented"); - } - - addEventListener(type: string, - listener: EventListenerOrEventListenerObject, - useCapture?: boolean): void { - switch (type) { - case "upgradeneeded": - this.upgradeneededHandlers.push(listener as any); - break; - default: - super.addEventListener(type, listener, useCapture); - } - } -} - -function follow(x: any, s: string, replacement?: any): any { - if (s === "") { - return x; - } - const ptIdx = s.indexOf("."); - if (ptIdx < 0) { - const v = x[s]; - if (replacement !== undefined) { - x[s] = replacement; - } - return v; - } else { - const identifier = s.substring(0, ptIdx); - const rest = s.substring(ptIdx + 1); - return follow(x[identifier], rest, replacement); - } -} - -export function evaluateKeyPath(x: any, path: string | string[], replacement?: any): any { - if (typeof path === "string") { - return follow(x, path, replacement); - } else if (Array.isArray(path)) { - const res: any[] = []; - for (let s of path) { - let c = follow(x, s, replacement); - if (c === undefined) { - return undefined; - } - res.push(c); - } - return res; - } else { - throw Error("invalid key path, must be string or array of strings"); - } -} - -function stringifyKey(key: any) { - return JSON.stringify(key); -} - -export function isValidKey(key: any, memo: any[] = []) { - if (typeof key === "string" || typeof key === "number" || key instanceof Date) { - return true; - } - if (Array.isArray(key)) { - for (const element of key) { - if (!isValidKey(element, memo.concat([key]))) { - return false; - } - } - return true; - } - return false; -} - -class MyObjectStore implements IDBObjectStore { - - _keyPath: string | string[] | undefined; - _autoIncrement: boolean; - - get indexNames() { - return new DOMStringList(); - } - - constructor(public transaction: Transaction, public storeName: string) { - this._keyPath = this.transaction.transactionDbData.stores[this.storeName].keyPath as (string | string[]); - this._autoIncrement = this.transaction.transactionDbData.stores[this.storeName].autoIncrement; - } - - get keyPath(): string | string[] { - // TypeScript definitions are wrong here and don't permit a null keyPath - return this._keyPath as (string | string[]); - } - - get name() { - return this.storeName; - } - - get autoIncrement() { - return this._autoIncrement; - } - - storeImpl(originalValue: any, key: any|undefined, allowExisting: boolean) { - if (this.transaction.mode === "readonly") { - throw Error(); - } - if (!this.transaction.active) { - throw Error(); - } - if (!this.transaction.transactionDbData.stores.hasOwnProperty(this.storeName)) { - throw Error("object store was deleted"); - } - - const store = this.transaction.transactionDbData.stores[this.storeName]; - - const value = structuredClone(originalValue); - - if (this.keyPath) { - // we're dealine with in-line keys - if (key) { - throw Error("keys not allowed with in-line keys"); - } - key = evaluateKeyPath(value, this.keyPath); - if (!key && !this.autoIncrement) { - throw Error("key path must evaluate to key for in-line stores without autoIncrement"); - } - if (this.autoIncrement) { - if (key && typeof key === "number") { - store.keyGenerator = key + 1; - } else { - key = store.keyGenerator; - store.keyGenerator += 1; - evaluateKeyPath(value, this.keyPath, key); - } - } - } else { - // we're dealing with out-of-line keys - if (!key && !this.autoIncrement) { - throw Error("key must be provided for out-of-line stores without autoIncrement"); - } - key = this.transaction.transactionDbData.stores - if (this.autoIncrement) { - if (key && typeof key === "number") { - store.keyGenerator = key + 1; - } else { - key = store.keyGenerator; - store.keyGenerator += 1; - } - } - } - - const stringKey = stringifyKey(key); - - if (store.objects.hasOwnProperty(stringKey) && !allowExisting) { - throw Error("key already exists"); - } - - const req = new MyRequest(this.transaction, () => { - req.source = this; - store.objects[stringKey] = value; - }); - return req; - } - - put(value: any, key?: any): IDBRequest { - return this.storeImpl(value, key, true); - } - - add(value: any, key?: any): IDBRequest { - return this.storeImpl(value, key, false); - } - - delete(key: any): IDBRequest { - if (this.transaction.mode === "readonly") { - throw Error(); - } - if (!this.transaction.active) { - throw Error(); - } - if (!this.transaction.transactionDbData.stores.hasOwnProperty(this.storeName)) { - throw Error("object store was deleted"); - } - const store = this.transaction.transactionDbData.stores[this.storeName]; - const stringKey = stringifyKey(key); - const req = new MyRequest(this.transaction, () => { - req.source = this; - delete store.objects[stringifyKey]; - }); - return req; - } - - get(key: any): IDBRequest { - if (!this.transaction.active) { - throw Error(); - } - if (!this.transaction.transactionDbData.stores.hasOwnProperty(this.storeName)) { - throw Error("object store was deleted"); - } - if (isKeyRange(key)) { - throw Error("not implemented"); - } - const store = this.transaction.transactionDbData.stores[this.storeName]; - const stringKey = stringifyKey(key); - const req = new MyRequest(this.transaction, () => { - req.source = this; - req.result = store.objects[stringKey]; - }); - return req; - } - - deleteIndex(indexName: string) { - throw Error("not implemented"); - } - - clear(): IDBRequest { - throw Error("not implemented"); - } - - count(key?: any): IDBRequest { - throw Error("not implemented"); - } - - createIndex(name: string, keyPath: string | string[], optionalParameters?: IDBIndexParameters): IDBIndex { - throw Error("not implemented"); - } - - index(indexName: string): IDBIndex { - return new IndexHandle(this, indexName); - } - - openCursor(range?: IDBKeyRange | IDBValidKey, direction?: IDBCursorDirection): IDBRequest { - throw Error("not implemented"); - } -} - - -class Db implements IDBDatabase { - - onabort: (this: IDBDatabase, ev: Event) => any; - onerror: (this: IDBDatabase, ev: Event) => any; - onversionchange: (ev: IDBVersionChangeEvent) => any; - - _storeNames: string[] = []; - - constructor(private _name: string, private _version: number, private factory: MemoryIDBFactory) { - for (let storeName in this.dbData.stores) { - if (this.dbData.stores.hasOwnProperty(storeName)) { - this._storeNames.push(storeName); - } - } - this._storeNames.sort(); - } - - get dbData(): Database { - return this.factory.data[this._name]; - } - - set dbData(data) { - this.factory.data[this._name] = data; - } - - get name() { - return this._name; - } - - get objectStoreNames() { - return new MyDomStringList(...this._storeNames); - } - - get version() { - return this._version; - } - - close() { - } - - createObjectStore(name: string, optionalParameters?: IDBObjectStoreParameters): IDBObjectStore { - let tx = this.factory.getTransaction(); - if (tx.mode !== "versionchange") { - throw Error("invalid mode"); - } - - const td = tx.transactionDbData; - if (td.stores[name]) { - throw Error("object store already exists"); - } - - td.stores[name] = { - autoIncrement: !!(optionalParameters && optionalParameters.autoIncrement), - indices: {}, - keyGenerator: 1, - name, - objects: [], - }; - - this._storeNames.push(name); - this._storeNames.sort(); - - return new MyObjectStore(tx, name); - } - - deleteObjectStore(name: string): void { - let tx = this.factory.getTransaction(); - if (tx.mode !== "versionchange") { - throw Error("invalid mode"); - } - - const td = tx.transactionDbData; - if (td.stores[name]) { - throw Error("object store does not exists"); - } - - const idx = this._storeNames.indexOf(name); - if (idx < 0) { - throw Error(); - } - this._storeNames.splice(idx, 1); - - delete td.stores[name]; - } - - transaction(storeNames: string | string[], mode: IDBTransactionMode = "readonly"): IDBTransaction { - const tx = new Transaction(this._name, this, mode); - return tx; - } - - dispatchEvent(evt: Event): boolean { - throw Error("not implemented"); - } - - removeEventListener(type: string, - listener?: EventListenerOrEventListenerObject, - options?: boolean | EventListenerOptions): void { - throw Error("not implemented"); - } - - addEventListener(type: string, - listener: EventListenerOrEventListenerObject, - useCapture?: boolean): void { - throw Error("not implemented"); - } -} - -enum TransactionState { - Created = 1, - Running = 2, - Commited = 3, - Aborted = 4, -} - -class Transaction implements IDBTransaction { - readonly READ_ONLY: string = "readonly"; - readonly READ_WRITE: string = "readwrite"; - readonly VERSION_CHANGE: string = "versionchange"; - - onabort: (this: IDBTransaction, ev: Event) => any; - onerror: (this: IDBTransaction, ev: Event) => any; - oncomplete: (this: IDBTransaction, ev: Event) => any; - - completeHandlers: Array<(this: IDBTransaction, ev: Event) => any> = []; - - state: TransactionState = TransactionState.Created; - - _transactionDbData: Database|undefined; - - constructor(public dbName: string, public dbHandle: Db, public _mode: IDBTransactionMode) { - } - - get mode() { - return this._mode; - } - - get active(): boolean { - return this.state === TransactionState.Running || this.state === TransactionState.Created; - } - - start() { - if (this.state != TransactionState.Created) { - throw Error(); - } - this.state = TransactionState.Running; - this._transactionDbData = structuredClone(this.dbHandle.dbData); - if (!this._transactionDbData) { - throw Error(); - } - } - - commit() { - if (this.state != TransactionState.Running) { - throw Error(); - } - if (!this._transactionDbData) { - throw Error(); - } - this.state = TransactionState.Commited; - this.dbHandle.dbData = this._transactionDbData; - } - - get error(): DOMException { - throw Error("not implemented"); - } - - get db() { - return this.dbHandle; - } - - get transactionDbData() { - if (this.state != TransactionState.Running) { - throw Error(); - } - let d = this._transactionDbData; - if (!d) { - throw Error(); - } - return d; - } - - abort() { - throw Error("not implemented"); - } - - objectStore(storeName: string): IDBObjectStore { - return new MyObjectStore(this, storeName); - } - - dispatchEvent(evt: Event): boolean { - throw Error("not implemented"); - } - - removeEventListener(type: string, - listener?: EventListenerOrEventListenerObject, - options?: boolean | EventListenerOptions): void { - throw Error("not implemented"); - } - - addEventListener(type: string, - listener: EventListenerOrEventListenerObject, - useCapture?: boolean): void { - switch (type) { - case "complete": - this.completeHandlers.push(listener as any); - break; - } - } - - callComplete(ev: Event) { - if (this.oncomplete) { - this.oncomplete(ev); - } - for (let h of this.completeHandlers) { - h.call(this, ev); - } - } -} - - -/** - * Polyfill for CustomEvent. - */ -class MyEvent implements Event { - readonly NONE: number = 0; - readonly CAPTURING_PHASE: number = 1; - readonly AT_TARGET: number = 2; - readonly BUBBLING_PHASE: number = 3; - - _bubbles = false; - _cancelable = false; - _target: any; - _currentTarget: any; - _defaultPrevented: boolean = false; - _eventPhase: number = 0; - _timeStamp: number = 0; - _type: string; - - constructor(typeArg: string, target: any) { - this._type = typeArg; - this._target = target; - } - - get eventPhase() { - return this._eventPhase; - } - - get returnValue() { - return this.defaultPrevented; - } - - set returnValue(v: boolean) { - if (v) { - this.preventDefault(); - } - } - - get isTrusted() { - return false; - } - - get bubbles() { - return this._bubbles; - } - - get cancelable() { - return this._cancelable; - } - - set cancelBubble(v: boolean) { - if (v) { - this.stopPropagation(); - } - } - - get defaultPrevented() { - return this._defaultPrevented; - } - - stopPropagation() { - throw Error("not implemented"); - } - - get currentTarget() { - return this._currentTarget; - } - - get target() { - return this._target; - } - - preventDefault() { - } - - get srcElement() { - return this.target; - } - - get timeStamp() { - return this._timeStamp; - } - - get type() { - return this._type; - } - - get scoped() { - return false; - } - - initEvent(eventTypeArg: string, canBubbleArg: boolean, cancelableArg: boolean) { - if (this._eventPhase != 0) { - return; - } - - this._type = eventTypeArg; - this._bubbles = canBubbleArg; - this._cancelable = cancelableArg; - } - - stopImmediatePropagation() { - throw Error("not implemented"); - } - - deepPath(): EventTarget[] { - return []; - } -} - - -class VersionChangeEvent extends MyEvent { - _newVersion: number|null; - _oldVersion: number; - constructor(oldVersion: number, newVersion: number|null, target: any) { - super("VersionChange", target); - this._oldVersion = oldVersion; - this._newVersion = newVersion; - } - - get newVersion() { - return this._newVersion; - } - - get oldVersion() { - return this._oldVersion; - } -} - - -export class MemoryIDBFactory implements IDBFactory { - data: Databases = {}; - - currentRequest: MyRequest|undefined; - - scheduledRequests: MyRequest[] = []; - - private addRequest(r: MyRequest) { - this.scheduledRequests.push(r); - if (this.currentRequest) { - return; - } - const runNext = (prevRequest?: MyRequest) => { - const nextRequest = this.scheduledRequests.shift(); - if (nextRequest) { - const tx = nextRequest.transaction; - - if (tx.state === TransactionState.Running) { - // Okay, we're continuing with the same transaction - } else if (tx.state === TransactionState.Created) { - tx.start(); - } else { - throw Error(); - } - - this.currentRequest = nextRequest; - this.currentRequest.runner(); - this.currentRequest.done = true; - this.currentRequest = undefined; - runNext(nextRequest); - } else if (prevRequest) { - // We have no other request scheduled, so - // auto-commit the transaction that the - // previous request worked on. - let lastTx = prevRequest._transaction; - lastTx.commit(); - } - }; - alreadyResolved.then(() => { - runNext(); - }); - } - - /** - * Get the only transaction that is active right now - * or throw if no transaction is active. - */ - getTransaction() { - const req = this.currentRequest; - if (!req) { - throw Error(); - } - return req.transaction; - } - - cmp(a: any, b: any): number { - throw Error("not implemented"); - } - - deleteDatabase(name: string): IDBOpenDBRequest { - throw Error("not implemented"); - } - - open(dbName: string, version?: number): IDBOpenDBRequest { - if (version !== undefined && version <= 0) { - throw Error("invalid version"); - } - - let upgradeNeeded = false; - let oldVersion: number; - let mydb: Database; - if (dbName in this.data) { - mydb = this.data[dbName]; - if (!mydb) { - throw Error(); - } - oldVersion = mydb.version; - if (version === undefined || version == mydb.version) { - // we can open without upgrading - } else if (version > mydb.version) { - upgradeNeeded = true; - mydb.version = version; - } else { - throw Error("version error"); - } - } else { - mydb = { - name: dbName, - stores: {}, - version: (version || 1), - }; - upgradeNeeded = true; - oldVersion = 0; - } - - this.data[dbName] = mydb; - - const db = new Db(dbName, mydb.version, this); - const tx = new Transaction(dbName, db, "versionchange"); - - const req = new OpenDBRequest(tx, () => { - req._result = db; - if (upgradeNeeded) { - let versionChangeEvt = new VersionChangeEvent(oldVersion, mydb.version, db); - req.callOnupgradeneeded(versionChangeEvt); - } - req.callSuccess(); - }); - - this.addRequest(req); - - return req; - } -} - -/** - * Inject our IndexedDb implementation in the global namespace, - * potentially replacing an existing implementation. - */ -export function injectGlobals() { -} diff --git a/src/memidb/aatree-test.ts b/src/memidb/aatree-test.ts new file mode 100644 index 000000000..21ae26173 --- /dev/null +++ b/src/memidb/aatree-test.ts @@ -0,0 +1,84 @@ +/* + This file is part of TALER + (C) 2017 Inria and GNUnet e.V. + + TALER is free software; you can redistribute it and/or modify it under the + terms of the GNU General Public License as published by the Free Software + Foundation; either version 3, or (at your option) any later version. + + TALER is distributed in the hope that it will be useful, but WITHOUT ANY + WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR + A PARTICULAR PURPOSE. See the GNU General Public License for more details. + + You should have received a copy of the GNU General Public License along with + TALER; see the file COPYING. If not, see + */ + + +import {test} from "ava"; + +import * as aat from "./aatree"; + + +function shuffleArray(array: any[]): any[] { + for (let i = array.length - 1; i > 0; i--) { + const j = Math.floor(Math.random() * (i + 1)); + const temp = array[i]; + array[i] = array[j]; + array[j] = temp; + } + return array; +} + + +function myCmp(a: any, b: any): number { + if (a < b) { + return -1; + } + if (a > b) { + return 1; + } + return 0; +} + + +test("insertion", (t) => { + let vs = []; + for (let i = 0; i < 1000; i++) { + vs.push(Math.floor(Math.random() * 500)); + } + + let tree = undefined; + t.true(aat.checkInvariants(tree)); + + for (let i = 0; i < 1000; i++) { + tree = aat.treeInsert(tree, vs[i], myCmp); + t.true(aat.checkInvariants(tree)); + t.true(aat.treeFind(tree, vs[i], myCmp)); + } + + vs = Array.from(new Set(vs)); + + vs.sort((a, b) => a - b); + t.deepEqual(aat.treeToArray(tree), vs); +}); + + +test("deletion", (t) => { + let vs = []; + let tree = undefined; + for (let i = 0; i < 1000; i++) { + vs.push(Math.floor(Math.random() * 500)); + tree = aat.treeInsert(tree, vs[i], myCmp); + t.true(aat.checkInvariants(tree)); + t.true(aat.treeFind(tree, vs[i], myCmp)); + } + + shuffleArray(vs); + + for (let i = 0; i < 1000; i++) { + tree = aat.treeDelete(tree, vs[i], myCmp); + t.true(aat.checkInvariants(tree)); + t.false(aat.treeFind(tree, vs[i], myCmp)); + } +}); diff --git a/src/memidb/aatree.ts b/src/memidb/aatree.ts new file mode 100644 index 000000000..50c4f0aae --- /dev/null +++ b/src/memidb/aatree.ts @@ -0,0 +1,388 @@ +/* + This file is part of TALER + (C) 2017 Inria and GNUnet e.V. + + TALER is free software; you can redistribute it and/or modify it under the + terms of the GNU General Public License as published by the Free Software + Foundation; either version 3, or (at your option) any later version. + + TALER is distributed in the hope that it will be useful, but WITHOUT ANY + WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR + A PARTICULAR PURPOSE. See the GNU General Public License for more details. + + You should have received a copy of the GNU General Public License along with + TALER; see the file COPYING. If not, see + */ + + +/** + * Implementation of AA trees (Arne Andersson, 1993) as a persistent data + * structure (Prabhakar Ragde, 2014). + * + * AA trees were chosen since they balance efficiency and a simple + * implementation. + */ + + +/** + * An AA tree, either a node or 'undefined' as sentinel element. + */ +export type AATree = AATreeNode | undefined; + + +interface AATreeNode { + left: AATree; + right: AATree; + level: number; + key: any; +} + + +/** + * Check AA tree invariants. Useful for testing. + */ +export function checkInvariants(t: AATree): boolean { + // No invariants for the sentinel. + if (!t) { + return true; + } + + // AA1: The left child of a node x has level one less than x. + if (level(t.left) != level(t) - 1) { + console.log("violated AA1"); + + console.log(JSON.stringify(t, undefined, 2)); + return false; + } + + // AA2: The right child of x has the same level (x is a "double" node) or one less (x is a "single" node). + if (!(level(t.right) === level(t) || level(t.right) === level(t) - 1)) { + console.log("violated AA2"); + console.log("level(t.right)", level(t.right)); + console.log("level(t)", level(t)); + return false; + } + + // AA3: The right child of the right child of x has level less than x. + if (t.right && t.right.right) { + if (level(t.right.right) >= level(t)) { + console.log("violated AA3"); + console.log(JSON.stringify(t, undefined, 2)); + return false; + } + } + + // AA4: All internal nodes have two children. + // This invariant follows from how we defined "level" + return true; +} + + +/** + * Fix a violation of invariant AA1 by reversing a link. + * + * ``` + * y <--- t => y ---> t + * / \ \ => / / \ + * a b c => a b c + * ``` + */ +function skew(t: AATreeNode) { + if (t.left && t.left.level === t.level) { + return { ...t.left, right: { ...t, left: t.left.right } }; + } + return t; +} + + +/** + * Fix a violation of invariant AA3 by pulling up the middle node. + * + * ``` + * => y + * => / \ + * t --> y --> z => t z + * / / => / \ + * a b => a b + * ``` + */ +function split(t: AATreeNode) { + if (t.right && t.right.right && + t.level === t.right.level && + t.right.level === t.right.right.level) { + return { + level: t.level + 1, + key: t.right.key, + left: { ...t, right: t.right.left }, + right: t.right.right, + } + } + return t; +} + + +/** + * Non-destructively insert a new key into an AA tree. + */ +export function treeInsert(t: AATree, k: any, cmpFn: (k1: any, k2: any) => number): AATreeNode { + if (!t) { + return { + level: 1, + key: k, + left: undefined, + right: undefined, + } + } + const cmp = cmpFn(k, t.key); + if (cmp === 0) { + return t; + } else if (cmp < 0) { + return split(skew({ ...t, left: treeInsert(t.left, k, cmpFn)})); + } else { + return split(skew({ ...t, right: treeInsert(t.right, k, cmpFn)})); + } +} + + +/** + * Level of an AA tree node, or zero if it's a sentinel. + */ +function level(t: AATree) { + if (!t) { + return 0; + } + return t.level; +} + + +/** + * Check if a node is single, i.e. doens't have a right child + * on the same level. + */ +function isSingle(t: AATree) { + if (t && t.right && t.right.level === t.level) { + return false; + } + return true; +} + + +/** + * Restore invariants that were broken by deleting a node. + * + * Assumes that invariants for t.left and t.right are already adjusted. + */ +function adjust(t: AATreeNode): AATreeNode { + // First check if left or right subtree are at the right level. Note that + // they can't be both at the wrong level, since only one node is deleted + // before calling adjust. + const leftOkay = level(t.left) === level(t) - 1; + const rightOkay = (level(t.right) === level(t) || level(t.right) === level(t) - 1); + if (leftOkay && rightOkay) { + return t; + } + if (!rightOkay) { + if (isSingle(t.left)) { + return skew({ ...t, level: t.level - 1 }); + } + /* + * ( t ) => ( b ) + * / \ => / \ + * x -> b \ => x t + * / / \ \ => / \ / \ + * a d e c => a d e c + */ + const b = t.left!.right!; + return { + level: b.level + 1, + key: b.key, + left: { ...t.left, right: b.left }, + right: { ...t, level: t.level - 1, left: b.right }, + }; + } + if (!leftOkay) { + if (isSingle(t)) { + return split({ ...t, level: t.level - 1 }); + } + /* + * t -> ( r ) => ( a ) -> r + * / / \ => / / \ + * / a -> d b => t d b + * / / => / \ + * x c => l c + * + * t -> r => ( a ) + * / / \ => / \ + * / a b => t r -> b + * / / \ => / \ / + * x c d => l c d + * + * Only Level of r differs, depending on whether a is single or double. + * Node 'r' must be split, as node 'b' might be double. + */ + const a = t.right!.left!; + const n = isSingle(a) ? a.level : a.level + 1; + return { + key: a.key, + left: { ...t, level: a.level, right: a.left }, + level: a.level + 1, + right: split({ + level: n, + left: a.right, + right: t.right!.right, + key: t.right!.key, + }), + }; + } + throw Error("not reached"); +} + + +function treeDeleteLargest(t: AATreeNode): { key: any, tree: AATree } { + if (!t.right) { + return { key: t.key, tree: t.left }; + } + const d = treeDeleteLargest(t.right); + return { + key: d.key, + tree: adjust({ ...t, right: d.tree}), + }; +} + + +/** + * Count the number of elements stored in the tree. + */ +export function treeSize(t: AATree): number { + if (!t) { + return 0; + } + return treeSize(t.left) + treeSize(t.right) + 1; +} + + +/** + * Get an array of (sorted) keys from an AA tree. + */ +export function treeToArray(t: AATree, accum: any[] = []) { + if (!t) { + return accum; + } + treeToArray(t.left, accum); + accum.push(t.key); + treeToArray(t.right, accum); + return accum; +} + + +/** + * Check if a key can be found in a tree. + */ +export function treeFind(t: AATree, k: any, cmpFn: (k1: any, k2: any) => number): boolean { + if (!t) { + return false; + } + const cmp = cmpFn(k, t.key); + if (cmp < 0) { + return treeFind(t.left, k, cmpFn); + } + if (cmp > 0) { + return treeFind(t.right, k, cmpFn); + } + return true; +} + + +/** + * Get the largest key in the tree. + */ +export function treeBiggest(t: AATree): any { + if (!t) { + return undefined; + } + if (!t.right) { + return t.key; + } + return treeBiggest(t); +} + + +/** + * Get the smallest key in the tree. + */ +export function treeSmallest(t: AATree): any { + if (!t) { + return undefined; + } + if (!t.left) { + return t.key; + } + return treeSmallest(t); +} + + +/** + * Get the smallest key from the tree that is larger than the given key. + * Returns 'undefined' if the given key is the largest key. + */ +export function treeNextKey(t: AATree, k: any, cmpFn: (k1: any, k2: any) => number): any { + if (!t) { + return undefined; + } + const cmp = cmpFn(k, t.key); + if (cmp === 0) { + return treeSmallest(t.right); + } + if (cmp < 0) { + const r = treeNextKey(t.left, k, cmpFn); + if (r) { + return r; + } + return t.key; + } + if (cmp < 0) { + return treeNextKey(t.right, k, cmpFn); + } +} + + +/** + * Get the largest tree from the tree that is smaller than the given key. + * Returns 'undefined' if the given key is the smallest key. + */ +export function treePreviousKey(t: AATree, k: any, cmpFn: (k1: any, k2: any) => number): any { + return treeNextKey(t, k, (k1, k2) => -cmpFn(k1, k2)); +} + + +/** + * Returns a new tree without the given key. + */ +export function treeDelete(t: AATree, k: any, cmpFn: (k1: any, k2: any) => number): AATree { + if (!t) { + return t; + } + const cmp = cmpFn(k, t.key); + if (cmp === 0) { + if (!t.left) { + return t.right; + } + if (!t.right) { + return t.left; + } + const d = treeDeleteLargest(t.left); + return adjust({ + key: d.key, + left: d.tree, + right: t.right, + level: t.level, + }); + } + if (cmp < 0) { + return adjust({ ...t, left: treeDelete(t.left, k, cmpFn) }); + } + if (cmp > 0) { + return adjust({ ...t, right: treeDelete(t.right, k, cmpFn) }); + } + throw Error("not reached"); +} diff --git a/src/memidb/memidb-test.ts b/src/memidb/memidb-test.ts new file mode 100644 index 000000000..8f8498a6e --- /dev/null +++ b/src/memidb/memidb-test.ts @@ -0,0 +1,114 @@ +/* + This file is part of TALER + (C) 2017 Inria and GNUnet e.V. + + TALER is free software; you can redistribute it and/or modify it under the + terms of the GNU General Public License as published by the Free Software + Foundation; either version 3, or (at your option) any later version. + + TALER is distributed in the hope that it will be useful, but WITHOUT ANY + WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR + A PARTICULAR PURPOSE. See the GNU General Public License for more details. + + You should have received a copy of the GNU General Public License along with + TALER; see the file COPYING. If not, see + */ + +import {test} from "ava"; +import * as memidb from "./memidb"; + +test.cb("db open", (t) => { + let ncb = 0; + const idb = new memidb.MemoryIDBFactory(); + const req = idb.open("testdb"); + let called = false; + req.onupgradeneeded = (evt) => { + ncb += 1; + called = true; + t.is(req.result, evt.target); + t.is(evt.oldVersion, 0); + t.is(evt.newVersion, 1); + t.truthy(req.result); + t.pass(); + } + req.onsuccess = (evt) => { + t.is(ncb, 1); + t.is(req.result, evt.target); + t.truthy(req.result); + t.end(); + } +}); + +test.cb("store creation", (t) => { + const idb = new memidb.MemoryIDBFactory(); + const req = idb.open("testdb"); + req.onupgradeneeded = (evt) => { + const db: IDBDatabase = req.result; + + const store1 = db.createObjectStore("b-store"); + t.is(store1.name, "b-store"); + t.deepEqual(Array.from(db.objectStoreNames), ["b-store"]); + + const store2 = db.createObjectStore("a-store"); + t.is(store2.name, "a-store"); + t.deepEqual(Array.from(db.objectStoreNames), ["a-store", "b-store"]); + + const store3 = db.createObjectStore("c-store"); + t.is(store3.name, "c-store"); + t.deepEqual(Array.from(db.objectStoreNames), ["a-store", "b-store", "c-store"]); + t.pass(); + } + req.onsuccess = (evt) => { + t.end(); + } +}); + + +test.cb("put and get", (t) => { + const idb = new memidb.MemoryIDBFactory(); + const req = idb.open("testdb"); + req.onupgradeneeded = (evt) => { + const db: IDBDatabase = req.result; + const store1 = db.createObjectStore("mystore"); + store1.put({answer: 42}, "a"); + } + req.onsuccess = (evt) => { + t.end() + } +}); + + +test("key path evaluation", (t) => { + const obj = { + a: { + b: { + c: 42, + }, + }, + b: "hello", + "": "spam", + arr: ["foo", "bar"], + } + t.deepEqual(memidb.evaluateKeyPath(obj, ""), obj); + t.deepEqual(memidb.evaluateKeyPath(obj, "a.b.c"), 42); + t.deepEqual(memidb.evaluateKeyPath(obj, "a.b"), {c: 42}); + t.deepEqual(memidb.evaluateKeyPath(obj, "foo"), undefined); + t.deepEqual(memidb.evaluateKeyPath(obj, ["a.b.c", "foo"]), undefined); + t.deepEqual(memidb.evaluateKeyPath(obj, ["a.b.c", "b"]), [42, "hello"]); + t.deepEqual(memidb.evaluateKeyPath(obj, "arr.0"), "foo"); + t.deepEqual(memidb.evaluateKeyPath(obj, "."), "spam"); +}); + +test("key path evaluation with replacement", (t) => { + const obj: any = { + a: { + b: { + c: 42, + }, + }, + } + memidb.evaluateKeyPath(obj, "a.b.c", 24); + t.is(obj.a.b.c, 24); + memidb.evaluateKeyPath(obj, "a.b", 24); + t.is(obj.a.b, 24); +}); diff --git a/src/memidb/memidb.ts b/src/memidb/memidb.ts new file mode 100644 index 000000000..4ad3a01b9 --- /dev/null +++ b/src/memidb/memidb.ts @@ -0,0 +1,961 @@ +/* + This file is part of TALER + (C) 2017 Inria and GNUnet e.V. + + TALER is free software; you can redistribute it and/or modify it under the + terms of the GNU General Public License as published by the Free Software + Foundation; either version 3, or (at your option) any later version. + + TALER is distributed in the hope that it will be useful, but WITHOUT ANY + WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR + A PARTICULAR PURPOSE. See the GNU General Public License for more details. + + You should have received a copy of the GNU General Public License along with + TALER; see the file COPYING. If not, see + */ + +/** + * In-memory implementation of the IndexedDB interface. + * + * Transactions support rollback, but they are all run sequentially within the + * same MemoryIDBFactory. + * + * Every operation involves copying the whole database state, making it only + * feasible for small databases. + */ + +/* work in progres ... */ +/* tslint:disable */ + + +const structuredClone = require("structured-clone"); + + +interface Store { + name: string; + keyPath?: string | string[]; + keyGenerator: number; + autoIncrement: boolean; + objects: { [primaryKey: string]: any }; + indices: { [indexName: string]: Index }; +} + +interface Index { + multiEntry: boolean; + unique: boolean; + + /** + * Map the index's key to the primary key. + */ + map: { [indexKey: string]: string[] }; +} + + +interface Database { + name: string; + version: number; + stores: { [name: string]: Store }; +} + + +interface Databases { + [name: string]: Database; +} + + +/** + * Resolved promise, used to schedule various things + * by calling .next on it. + */ +const alreadyResolved = Promise.resolve(); + + +class MyDomStringList extends Array implements DOMStringList { + contains(s: string) { + for (let i = 0; i < this.length; i++) { + if (s === this[i]) { + return true; + } + } + return false; + } + item(i: number) { + return this[i]; + } +} + + + + +class MyKeyRange implements IDBKeyRange { + static only(value: any): IDBKeyRange { + return new MyKeyRange(value, value, false, false); + } + + static bound(lower: any, upper: any, lowerOpen: boolean = false, upperOpen: boolean = false) { + return new MyKeyRange(lower, upper, lowerOpen, upperOpen); + } + + static lowerBound(lower: any, lowerOpen: boolean = false) { + return new MyKeyRange(lower, undefined, lowerOpen, true); + } + + static upperBound(upper: any, upperOpen: boolean = false) { + return new MyKeyRange(undefined, upper, true, upperOpen); + } + + constructor(public lower: any, public upper: any, public lowerOpen: boolean, public upperOpen: boolean) { + } +} + + +/** + * Type guard for an IDBKeyRange. + */ +export function isKeyRange(obj: any): obj is IDBKeyRange { + return (typeof obj === "object" && + "lower" in obj && "upper" in obj && + "lowerOpen" in obj && "upperOpen" in obj); +} + + +export function compareKeys(a: any, b: any): -1|0|1 { + throw Error("not implemented") +} + + +class IndexHandle implements IDBIndex { + + _unique: boolean; + _multiEntry: boolean; + + get keyPath(): string | string[] { + throw Error("not implemented"); + } + + get name () { + return this.indexName; + } + + get unique() { + return this._unique; + } + + get multiEntry() { + return this._multiEntry; + } + + constructor(public objectStore: MyObjectStore, public indexName: string) { + } + + count(key?: IDBKeyRange | IDBValidKey): IDBRequest { + throw Error("not implemented"); + } + + get(key: IDBKeyRange | IDBValidKey): IDBRequest { + throw Error("not implemented"); + } + + getKey(key: IDBKeyRange | IDBValidKey): IDBRequest { + throw Error("not implemented"); + } + + openCursor(range?: IDBKeyRange | IDBValidKey, direction?: IDBCursorDirection): IDBRequest { + throw Error("not implemented"); + } + + openKeyCursor(range?: IDBKeyRange | IDBValidKey, direction?: IDBCursorDirection): IDBRequest { + throw Error("not implemented"); + } +} + +class MyRequest implements IDBRequest { + onerror: (this: IDBRequest, ev: Event) => any; + + onsuccess: (this: IDBRequest, ev: Event) => any; + successHandlers: Array<(this: IDBRequest, ev: Event) => any> = []; + + done: boolean = false; + _result: any; + + _source: (IDBObjectStore | IDBIndex | IDBCursor | null) = null; + + constructor(public _transaction: Transaction, public runner: () => void) { + } + + callSuccess() { + const ev = new MyEvent("success", this); + if (this.onsuccess) { + this.onsuccess(ev); + } + for (let h of this.successHandlers) { + h.call(this, ev); + } + } + + get error(): DOMException { + return (null as any) as DOMException; + } + + get result(): any { + return this._result; + } + + get source() { + // buggy type definitions don't allow null even though it's in + // the spec. + return this._source as (IDBObjectStore | IDBIndex | IDBCursor); + } + + get transaction() { + return this._transaction; + } + + dispatchEvent(evt: Event): boolean { + return false; + } + + get readyState() { + if (this.done) { + return "done"; + } + return "pending"; + } + + removeEventListener(type: string, + listener?: EventListenerOrEventListenerObject, + options?: boolean | EventListenerOptions): void { + throw Error("not implemented"); + } + + addEventListener(type: string, + listener: EventListenerOrEventListenerObject, + useCapture?: boolean): void { + switch (type) { + case "success": + this.successHandlers.push(listener as any); + break; + } + } +} + +class OpenDBRequest extends MyRequest implements IDBOpenDBRequest { + onblocked: (this: IDBOpenDBRequest, ev: Event) => any; + + onupgradeneeded: (this: IDBOpenDBRequest, ev: IDBVersionChangeEvent) => any; + upgradeneededHandlers: Array<(this: IDBOpenDBRequest, ev: IDBVersionChangeEvent) => any> = []; + + callOnupgradeneeded(ev: IDBVersionChangeEvent) { + if (this.onupgradeneeded) { + this.onupgradeneeded(ev); + } + for (let h of this.upgradeneededHandlers) { + h.call(this, ev); + } + } + + removeEventListener(type: string, + listener?: EventListenerOrEventListenerObject, + options?: boolean | EventListenerOptions): void { + throw Error("not implemented"); + } + + addEventListener(type: string, + listener: EventListenerOrEventListenerObject, + useCapture?: boolean): void { + switch (type) { + case "upgradeneeded": + this.upgradeneededHandlers.push(listener as any); + break; + default: + super.addEventListener(type, listener, useCapture); + } + } +} + +function follow(x: any, s: string, replacement?: any): any { + if (s === "") { + return x; + } + const ptIdx = s.indexOf("."); + if (ptIdx < 0) { + const v = x[s]; + if (replacement !== undefined) { + x[s] = replacement; + } + return v; + } else { + const identifier = s.substring(0, ptIdx); + const rest = s.substring(ptIdx + 1); + return follow(x[identifier], rest, replacement); + } +} + +export function evaluateKeyPath(x: any, path: string | string[], replacement?: any): any { + if (typeof path === "string") { + return follow(x, path, replacement); + } else if (Array.isArray(path)) { + const res: any[] = []; + for (let s of path) { + let c = follow(x, s, replacement); + if (c === undefined) { + return undefined; + } + res.push(c); + } + return res; + } else { + throw Error("invalid key path, must be string or array of strings"); + } +} + +function stringifyKey(key: any) { + return JSON.stringify(key); +} + +export function isValidKey(key: any, memo: any[] = []) { + if (typeof key === "string" || typeof key === "number" || key instanceof Date) { + return true; + } + if (Array.isArray(key)) { + for (const element of key) { + if (!isValidKey(element, memo.concat([key]))) { + return false; + } + } + return true; + } + return false; +} + +class MyObjectStore implements IDBObjectStore { + + _keyPath: string | string[] | undefined; + _autoIncrement: boolean; + + get indexNames() { + return new DOMStringList(); + } + + constructor(public transaction: Transaction, public storeName: string) { + this._keyPath = this.transaction.transactionDbData.stores[this.storeName].keyPath as (string | string[]); + this._autoIncrement = this.transaction.transactionDbData.stores[this.storeName].autoIncrement; + } + + get keyPath(): string | string[] { + // TypeScript definitions are wrong here and don't permit a null keyPath + return this._keyPath as (string | string[]); + } + + get name() { + return this.storeName; + } + + get autoIncrement() { + return this._autoIncrement; + } + + storeImpl(originalValue: any, key: any|undefined, allowExisting: boolean) { + if (this.transaction.mode === "readonly") { + throw Error(); + } + if (!this.transaction.active) { + throw Error(); + } + if (!this.transaction.transactionDbData.stores.hasOwnProperty(this.storeName)) { + throw Error("object store was deleted"); + } + + const store = this.transaction.transactionDbData.stores[this.storeName]; + + const value = structuredClone(originalValue); + + if (this.keyPath) { + // we're dealine with in-line keys + if (key) { + throw Error("keys not allowed with in-line keys"); + } + key = evaluateKeyPath(value, this.keyPath); + if (!key && !this.autoIncrement) { + throw Error("key path must evaluate to key for in-line stores without autoIncrement"); + } + if (this.autoIncrement) { + if (key && typeof key === "number") { + store.keyGenerator = key + 1; + } else { + key = store.keyGenerator; + store.keyGenerator += 1; + evaluateKeyPath(value, this.keyPath, key); + } + } + } else { + // we're dealing with out-of-line keys + if (!key && !this.autoIncrement) { + throw Error("key must be provided for out-of-line stores without autoIncrement"); + } + key = this.transaction.transactionDbData.stores + if (this.autoIncrement) { + if (key && typeof key === "number") { + store.keyGenerator = key + 1; + } else { + key = store.keyGenerator; + store.keyGenerator += 1; + } + } + } + + const stringKey = stringifyKey(key); + + if (store.objects.hasOwnProperty(stringKey) && !allowExisting) { + throw Error("key already exists"); + } + + const req = new MyRequest(this.transaction, () => { + req._source = this; + store.objects[stringKey] = value; + }); + return req; + } + + put(value: any, key?: any): IDBRequest { + return this.storeImpl(value, key, true); + } + + add(value: any, key?: any): IDBRequest { + return this.storeImpl(value, key, false); + } + + delete(key: any): IDBRequest { + if (this.transaction.mode === "readonly") { + throw Error(); + } + if (!this.transaction.active) { + throw Error(); + } + if (!this.transaction.transactionDbData.stores.hasOwnProperty(this.storeName)) { + throw Error("object store was deleted"); + } + const store = this.transaction.transactionDbData.stores[this.storeName]; + const stringKey = stringifyKey(key); + const req = new MyRequest(this.transaction, () => { + req._source = this; + delete store.objects[stringKey]; + }); + return req; + } + + get(key: any): IDBRequest { + if (!this.transaction.active) { + throw Error(); + } + if (!this.transaction.transactionDbData.stores.hasOwnProperty(this.storeName)) { + throw Error("object store was deleted"); + } + if (isKeyRange(key)) { + throw Error("not implemented"); + } + const store = this.transaction.transactionDbData.stores[this.storeName]; + const stringKey = stringifyKey(key); + const req = new MyRequest(this.transaction, () => { + req._source = this; + req._result = store.objects[stringKey]; + }); + return req; + } + + deleteIndex(indexName: string) { + throw Error("not implemented"); + } + + clear(): IDBRequest { + throw Error("not implemented"); + } + + count(key?: any): IDBRequest { + throw Error("not implemented"); + } + + createIndex(name: string, keyPath: string | string[], optionalParameters?: IDBIndexParameters): IDBIndex { + throw Error("not implemented"); + } + + index(indexName: string): IDBIndex { + return new IndexHandle(this, indexName); + } + + openCursor(range?: IDBKeyRange | IDBValidKey, direction?: IDBCursorDirection): IDBRequest { + throw Error("not implemented"); + } +} + + +class Db implements IDBDatabase { + + onabort: (this: IDBDatabase, ev: Event) => any; + onerror: (this: IDBDatabase, ev: Event) => any; + onversionchange: (ev: IDBVersionChangeEvent) => any; + + _storeNames: string[] = []; + + constructor(private _name: string, private _version: number, private factory: MemoryIDBFactory) { + for (let storeName in this.dbData.stores) { + if (this.dbData.stores.hasOwnProperty(storeName)) { + this._storeNames.push(storeName); + } + } + this._storeNames.sort(); + } + + get dbData(): Database { + return this.factory.data[this._name]; + } + + set dbData(data) { + this.factory.data[this._name] = data; + } + + get name() { + return this._name; + } + + get objectStoreNames() { + return new MyDomStringList(...this._storeNames); + } + + get version() { + return this._version; + } + + close() { + } + + createObjectStore(name: string, optionalParameters?: IDBObjectStoreParameters): IDBObjectStore { + let tx = this.factory.getTransaction(); + if (tx.mode !== "versionchange") { + throw Error("invalid mode"); + } + + const td = tx.transactionDbData; + if (td.stores[name]) { + throw Error("object store already exists"); + } + + td.stores[name] = { + autoIncrement: !!(optionalParameters && optionalParameters.autoIncrement), + indices: {}, + keyGenerator: 1, + name, + objects: [], + }; + + this._storeNames.push(name); + this._storeNames.sort(); + + return new MyObjectStore(tx, name); + } + + deleteObjectStore(name: string): void { + let tx = this.factory.getTransaction(); + if (tx.mode !== "versionchange") { + throw Error("invalid mode"); + } + + const td = tx.transactionDbData; + if (td.stores[name]) { + throw Error("object store does not exists"); + } + + const idx = this._storeNames.indexOf(name); + if (idx < 0) { + throw Error(); + } + this._storeNames.splice(idx, 1); + + delete td.stores[name]; + } + + transaction(storeNames: string | string[], mode: IDBTransactionMode = "readonly"): IDBTransaction { + const tx = new Transaction(this._name, this, mode); + return tx; + } + + dispatchEvent(evt: Event): boolean { + throw Error("not implemented"); + } + + removeEventListener(type: string, + listener?: EventListenerOrEventListenerObject, + options?: boolean | EventListenerOptions): void { + throw Error("not implemented"); + } + + addEventListener(type: string, + listener: EventListenerOrEventListenerObject, + useCapture?: boolean): void { + throw Error("not implemented"); + } +} + +enum TransactionState { + Created = 1, + Running = 2, + Commited = 3, + Aborted = 4, +} + +class Transaction implements IDBTransaction { + readonly READ_ONLY: string = "readonly"; + readonly READ_WRITE: string = "readwrite"; + readonly VERSION_CHANGE: string = "versionchange"; + + onabort: (this: IDBTransaction, ev: Event) => any; + onerror: (this: IDBTransaction, ev: Event) => any; + oncomplete: (this: IDBTransaction, ev: Event) => any; + + completeHandlers: Array<(this: IDBTransaction, ev: Event) => any> = []; + + state: TransactionState = TransactionState.Created; + + _transactionDbData: Database|undefined; + + constructor(public dbName: string, public dbHandle: Db, public _mode: IDBTransactionMode) { + } + + get mode() { + return this._mode; + } + + get active(): boolean { + return this.state === TransactionState.Running || this.state === TransactionState.Created; + } + + start() { + if (this.state != TransactionState.Created) { + throw Error(); + } + this.state = TransactionState.Running; + this._transactionDbData = structuredClone(this.dbHandle.dbData); + if (!this._transactionDbData) { + throw Error(); + } + } + + commit() { + if (this.state != TransactionState.Running) { + throw Error(); + } + if (!this._transactionDbData) { + throw Error(); + } + this.state = TransactionState.Commited; + this.dbHandle.dbData = this._transactionDbData; + } + + get error(): DOMException { + throw Error("not implemented"); + } + + get db() { + return this.dbHandle; + } + + get transactionDbData() { + if (this.state != TransactionState.Running) { + throw Error(); + } + let d = this._transactionDbData; + if (!d) { + throw Error(); + } + return d; + } + + abort() { + throw Error("not implemented"); + } + + objectStore(storeName: string): IDBObjectStore { + return new MyObjectStore(this, storeName); + } + + dispatchEvent(evt: Event): boolean { + throw Error("not implemented"); + } + + removeEventListener(type: string, + listener?: EventListenerOrEventListenerObject, + options?: boolean | EventListenerOptions): void { + throw Error("not implemented"); + } + + addEventListener(type: string, + listener: EventListenerOrEventListenerObject, + useCapture?: boolean): void { + switch (type) { + case "complete": + this.completeHandlers.push(listener as any); + break; + } + } + + callComplete(ev: Event) { + if (this.oncomplete) { + this.oncomplete(ev); + } + for (let h of this.completeHandlers) { + h.call(this, ev); + } + } +} + + +/** + * Polyfill for CustomEvent. + */ +class MyEvent implements Event { + readonly NONE: number = 0; + readonly CAPTURING_PHASE: number = 1; + readonly AT_TARGET: number = 2; + readonly BUBBLING_PHASE: number = 3; + + _bubbles = false; + _cancelable = false; + _target: any; + _currentTarget: any; + _defaultPrevented: boolean = false; + _eventPhase: number = 0; + _timeStamp: number = 0; + _type: string; + + constructor(typeArg: string, target: any) { + this._type = typeArg; + this._target = target; + } + + get eventPhase() { + return this._eventPhase; + } + + get returnValue() { + return this.defaultPrevented; + } + + set returnValue(v: boolean) { + if (v) { + this.preventDefault(); + } + } + + get isTrusted() { + return false; + } + + get bubbles() { + return this._bubbles; + } + + get cancelable() { + return this._cancelable; + } + + set cancelBubble(v: boolean) { + if (v) { + this.stopPropagation(); + } + } + + get defaultPrevented() { + return this._defaultPrevented; + } + + stopPropagation() { + throw Error("not implemented"); + } + + get currentTarget() { + return this._currentTarget; + } + + get target() { + return this._target; + } + + preventDefault() { + } + + get srcElement() { + return this.target; + } + + get timeStamp() { + return this._timeStamp; + } + + get type() { + return this._type; + } + + get scoped() { + return false; + } + + initEvent(eventTypeArg: string, canBubbleArg: boolean, cancelableArg: boolean) { + if (this._eventPhase != 0) { + return; + } + + this._type = eventTypeArg; + this._bubbles = canBubbleArg; + this._cancelable = cancelableArg; + } + + stopImmediatePropagation() { + throw Error("not implemented"); + } + + deepPath(): EventTarget[] { + return []; + } +} + + +class VersionChangeEvent extends MyEvent { + _newVersion: number|null; + _oldVersion: number; + constructor(oldVersion: number, newVersion: number|null, target: any) { + super("VersionChange", target); + this._oldVersion = oldVersion; + this._newVersion = newVersion; + } + + get newVersion() { + return this._newVersion; + } + + get oldVersion() { + return this._oldVersion; + } +} + + +export class MemoryIDBFactory implements IDBFactory { + data: Databases = {}; + + currentRequest: MyRequest|undefined; + + scheduledRequests: MyRequest[] = []; + + private addRequest(r: MyRequest) { + this.scheduledRequests.push(r); + if (this.currentRequest) { + return; + } + const runNext = (prevRequest?: MyRequest) => { + const nextRequest = this.scheduledRequests.shift(); + if (nextRequest) { + const tx = nextRequest.transaction; + + if (tx.state === TransactionState.Running) { + // Okay, we're continuing with the same transaction + } else if (tx.state === TransactionState.Created) { + tx.start(); + } else { + throw Error(); + } + + this.currentRequest = nextRequest; + this.currentRequest.runner(); + this.currentRequest.done = true; + this.currentRequest = undefined; + runNext(nextRequest); + } else if (prevRequest) { + // We have no other request scheduled, so + // auto-commit the transaction that the + // previous request worked on. + let lastTx = prevRequest._transaction; + lastTx.commit(); + } + }; + alreadyResolved.then(() => { + runNext(); + }); + } + + /** + * Get the only transaction that is active right now + * or throw if no transaction is active. + */ + getTransaction() { + const req = this.currentRequest; + if (!req) { + throw Error(); + } + return req.transaction; + } + + cmp(a: any, b: any): number { + throw Error("not implemented"); + } + + deleteDatabase(name: string): IDBOpenDBRequest { + throw Error("not implemented"); + } + + open(dbName: string, version?: number): IDBOpenDBRequest { + if (version !== undefined && version <= 0) { + throw Error("invalid version"); + } + + let upgradeNeeded = false; + let oldVersion: number; + let mydb: Database; + if (dbName in this.data) { + mydb = this.data[dbName]; + if (!mydb) { + throw Error(); + } + oldVersion = mydb.version; + if (version === undefined || version == mydb.version) { + // we can open without upgrading + } else if (version > mydb.version) { + upgradeNeeded = true; + mydb.version = version; + } else { + throw Error("version error"); + } + } else { + mydb = { + name: dbName, + stores: {}, + version: (version || 1), + }; + upgradeNeeded = true; + oldVersion = 0; + } + + this.data[dbName] = mydb; + + const db = new Db(dbName, mydb.version, this); + const tx = new Transaction(dbName, db, "versionchange"); + + const req = new OpenDBRequest(tx, () => { + req._result = db; + if (upgradeNeeded) { + let versionChangeEvt = new VersionChangeEvent(oldVersion, mydb.version, db); + req.callOnupgradeneeded(versionChangeEvt); + } + req.callSuccess(); + }); + + this.addRequest(req); + + return req; + } +} + +/** + * Inject our IndexedDb implementation in the global namespace, + * potentially replacing an existing implementation. + */ +export function injectGlobals() { +} -- cgit v1.2.3