CacheMap (#715)

* Create CacheMap class

* Add test

3 files changed, 346 insertions, 1 deletions

diff --git a/ext/mixed/js/cache-map.js b/ext/mixed/js/cache-map.js
new file mode 100644
index 00000000..7953e2cc
--- /dev/null
+++ b/ext/mixed/js/cache-map.js
@@ -0,0 +1,177 @@
+/*
+ * Copyright (C) 2020  Yomichan Authors
+ *
+ * This program 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 of the License, or
+ * (at your option) any later version.
+ *
+ * This program 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 this program.  If not, see <https://www.gnu.org/licenses/>.
+ */
+
+/**
+ * Class which caches a map of values using an arbitrary length path,
+ * keeping the most recently accessed values.
+ */
+class CacheMap {
+    /**
+     * Creates a new CacheMap.
+     * @param maxCount The maximum number of entries able to be stored in the cache.
+     * @param create A function to create a value for the corresponding path.
+     *   The signature is: create(...path)
+     */
+    constructor(maxCount, create) {
+        if (!(
+            typeof maxCount === 'number' &&
+            Number.isFinite(maxCount) &&
+            maxCount >= 0 &&
+            Math.floor(maxCount) === maxCount
+        )) {
+            throw new Error('Invalid maxCount');
+        }
+
+        this._maxCount = maxCount;
+        this._create = create;
+        this._count = 0;
+        this._map = new Map();
+        this._listFirst = this._createNode(null, null);
+        this._listLast = this._createNode(null, null);
+        this._resetEndNodes();
+    }
+
+    /**
+     * Returns the number of items in the cache.
+     */
+    get count() {
+        return this._count;
+    }
+
+    /**
+     * Returns the maximum number of items that can be added to the cache.
+     */
+    get maxCount() {
+        return this._maxCount;
+    }
+
+    /**
+     * Gets an item at the given path, if it exists. Otherwise, creates a new item
+     * and adds it to the cache. If the count exceeds the maximum count, items will be removed.
+     * @param path Arguments corresponding to the key of the cache.
+     */
+    get(...path) {
+        let ii = path.length;
+        if (ii === 0) { throw new Error('Invalid path'); }
+
+        let map = this._map;
+        let i = 0;
+        for (; i < ii; ++i) {
+            const map2 = map.get(path[i]);
+            if (typeof map2 === 'undefined') { break; }
+            map = map2;
+        }
+
+        if (i === ii) {
+            // Found (map is now a node)
+            this._updateRecency(map);
+            return map.value;
+        }
+
+        // Create new
+        const value = this._create(...path);
+
+        // Create mapping
+        --ii;
+        for (; i < ii; ++i) {
+            const map2 = new Map();
+            map.set(path[i], map2);
+            map = map2;
+        }
+
+        // Assign
+        const node = this._createNode(value, path);
+        this._addNode(node, this._listFirst);
+        map.set(path[ii], node);
+        ++this._count;
+
+        this._updateCount();
+
+        return value;
+    }
+
+    /**
+     * Clears the cache.
+     */
+    clear() {
+        this._map.clear();
+        this._count = 0;
+        this._resetEndNodes();
+    }
+
+    // Private
+
+    _updateRecency(node) {
+        this._removeNode(node);
+        this._addNode(node, this._listFirst);
+    }
+
+    _updateCount() {
+        for (let removeCount = this._count - this._maxCount; removeCount > 0; --removeCount) {
+            const node = this._listLast.previous;
+            this._removeNode(node);
+            this._removeMapping(node.path);
+            --this._count;
+        }
+    }
+
+    _createNode(value, path) {
+        return {value, path, previous: null, next: null};
+    }
+
+    _addNode(node, previous) {
+        const next = previous.next;
+        node.next = next;
+        node.previous = previous;
+        previous.next = node;
+        next.previous = node;
+    }
+
+    _removeNode(node) {
+        node.next.previous = node.previous;
+        node.previous.next = node.next;
+    }
+
+    _removeMapping(path) {
+        const ii = path.length - 1;
+        let i = 0;
+        const maps = [];
+        let map = this._map;
+        for (; i < ii; ++i) {
+            const map2 = map.get(path[i]);
+            if (typeof map2 === 'undefined') { return; }
+            maps.push([map, map2]);
+            map = map2;
+        }
+
+        // Delete node
+        map.delete(path[ii]);
+
+        // Clear empty paths
+        for (i = ii - 1; i >= 0; --i) {
+            let map2;
+            [map, map2] = maps[i];
+            if (map2.size > 0) { return; }
+            map.delete(path[i]);
+        }
+    }
+
+    _resetEndNodes() {
+        this._listFirst.next = this._listLast;
+        this._listLast.previous = this._listFirst;
+    }
+}
diff --git a/package.json b/package.json
index aaa7087e..5704ddb3 100644
--- a/package.json
+++ b/package.json
@@ -9,7 +9,7 @@
         "build": "node ./dev/build.js",
         "test": "npm run test-lint && npm run test-code && npm run test-manifest",
         "test-lint": "eslint . && node ./test/lint/global-declarations.js",
-        "test-code": "node ./test/test-schema.js && node ./test/test-dictionary.js && node ./test/test-database.js && node ./test/test-document.js && node ./test/test-object-property-accessor.js && node ./test/test-japanese.js && node ./test/test-text-source-map.js && node ./test/test-dom-text-scanner.js",
+        "test-code": "node ./test/test-schema.js && node ./test/test-dictionary.js && node ./test/test-database.js && node ./test/test-document.js && node ./test/test-object-property-accessor.js && node ./test/test-japanese.js && node ./test/test-text-source-map.js && node ./test/test-dom-text-scanner.js && node ./test/test-cache-map.js",
         "test-manifest": "node ./test/test-manifest.js"
     },
     "repository": {
diff --git a/test/test-cache-map.js b/test/test-cache-map.js
new file mode 100644
index 00000000..00383e65
--- /dev/null
+++ b/test/test-cache-map.js
@@ -0,0 +1,168 @@
+/*
+ * Copyright (C) 2020  Yomichan Authors
+ *
+ * This program 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 of the License, or
+ * (at your option) any later version.
+ *
+ * This program 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 this program.  If not, see <https://www.gnu.org/licenses/>.
+ */
+
+const assert = require('assert');
+const {VM} = require('./yomichan-vm');
+
+const vm = new VM({console});
+vm.execute([
+    'mixed/js/cache-map.js'
+]);
+const CacheMap = vm.get('CacheMap');
+
+
+function testConstructor() {
+    const data = [
+        [false, () => new CacheMap(0, () => null)],
+        [false, () => new CacheMap(1, () => null)],
+        [false, () => new CacheMap(Number.MAX_VALUE, () => null)],
+        [true,  () => new CacheMap(-1, () => null)],
+        [true,  () => new CacheMap(1.5, () => null)],
+        [true,  () => new CacheMap(Number.NaN, () => null)],
+        [true,  () => new CacheMap(Number.POSITIVE_INFINITY, () => null)],
+        [true,  () => new CacheMap('a', () => null)]
+    ];
+
+    for (const [throws, create] of data) {
+        if (throws) {
+            assert.throws(create);
+        } else {
+            assert.doesNotThrow(create);
+        }
+    }
+}
+
+function testApi() {
+    const data = [
+        {
+            maxCount: 1,
+            expectedCount: 0,
+            calls: []
+        },
+        {
+            maxCount: 1,
+            expectedCount: 1,
+            calls: [
+                ['get', 'a', 'b', 'c']
+            ]
+        },
+        {
+            maxCount: 10,
+            expectedCount: 1,
+            calls: [
+                ['get', 'a', 'b', 'c'],
+                ['get', 'a', 'b', 'c'],
+                ['get', 'a', 'b', 'c']
+            ]
+        },
+        {
+            maxCount: 10,
+            expectedCount: 3,
+            calls: [
+                ['get', 'a1', 'b', 'c'],
+                ['get', 'a2', 'b', 'c'],
+                ['get', 'a3', 'b', 'c']
+            ]
+        },
+        {
+            maxCount: 10,
+            expectedCount: 3,
+            calls: [
+                ['get', 'a', 'b1', 'c'],
+                ['get', 'a', 'b2', 'c'],
+                ['get', 'a', 'b3', 'c']
+            ]
+        },
+        {
+            maxCount: 10,
+            expectedCount: 3,
+            calls: [
+                ['get', 'a', 'b', 'c1'],
+                ['get', 'a', 'b', 'c2'],
+                ['get', 'a', 'b', 'c3']
+            ]
+        },
+        {
+            maxCount: 1,
+            expectedCount: 1,
+            calls: [
+                ['get', 'a1', 'b', 'c'],
+                ['get', 'a2', 'b', 'c'],
+                ['get', 'a3', 'b', 'c']
+            ]
+        },
+        {
+            maxCount: 1,
+            expectedCount: 1,
+            calls: [
+                ['get', 'a', 'b1', 'c'],
+                ['get', 'a', 'b2', 'c'],
+                ['get', 'a', 'b3', 'c']
+            ]
+        },
+        {
+            maxCount: 1,
+            expectedCount: 1,
+            calls: [
+                ['get', 'a', 'b', 'c1'],
+                ['get', 'a', 'b', 'c2'],
+                ['get', 'a', 'b', 'c3']
+            ]
+        },
+        {
+            maxCount: 10,
+            expectedCount: 0,
+            calls: [
+                ['get', 'a', 'b', 'c1'],
+                ['get', 'a', 'b', 'c2'],
+                ['get', 'a', 'b', 'c3'],
+                ['clear']
+            ]
+        },
+        {
+            maxCount: 0,
+            expectedCount: 0,
+            calls: [
+                ['get', 'a1', 'b', 'c'],
+                ['get', 'a', 'b2', 'c'],
+                ['get', 'a', 'b', 'c3']
+            ]
+        }
+    ];
+
+    const create = (...args) => args.join(',');
+    for (const {maxCount, expectedCount, calls} of data) {
+        const cache = new CacheMap(maxCount, create);
+        assert.strictEqual(cache.maxCount, maxCount);
+        for (const [name, ...args] of calls) {
+            switch (name) {
+                case 'get': cache.get(...args); break;
+                case 'clear': cache.clear(); break;
+            }
+        }
+        assert.strictEqual(cache.count, expectedCount);
+    }
+}
+
+
+function main() {
+    testConstructor();
+    testApi();
+}
+
+
+if (require.main === module) { main(); }