aa treesdold/dev/memidb

4 files changed, 1547 insertions, 0 deletions

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 <http://www.gnu.org/licenses/>
+ */
+
+
+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 <http://www.gnu.org/licenses/>
+ */
+
+
+/**
+ * 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 <http://www.gnu.org/licenses/>
+ */
+
+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 <http://www.gnu.org/licenses/>
+ */
+
+/**
+ * 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<string> 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() {
+}