Cache map improvements (#856)

* Update CacheMap API; get=>getOrCreate; add get; add set; add has

* Update tests

* Add more tests

3 files changed, 147 insertions, 55 deletions

diff --git a/ext/bg/js/json-schema.js b/ext/bg/js/json-schema.js
index 357432e5..4d77f0db 100644
--- a/ext/bg/js/json-schema.js
+++ b/ext/bg/js/json-schema.js
@@ -125,7 +125,7 @@ class JsonSchemaProxyHandler {
 
 class JsonSchemaValidator {
     constructor() {
-        this._regexCache = new CacheMap(100, (pattern, flags) => new RegExp(pattern, flags));
+        this._regexCache = new CacheMap(100, ([pattern, flags]) => new RegExp(pattern, flags));
     }
 
     createProxy(target, schema) {
@@ -676,7 +676,7 @@ class JsonSchemaValidator {
     }
 
     _getRegex(pattern, flags) {
-        const regex = this._regexCache.get(pattern, flags);
+        const regex = this._regexCache.getOrCreate([pattern, flags]);
         regex.lastIndex = 0;
         return regex;
     }
diff --git a/ext/mixed/js/cache-map.js b/ext/mixed/js/cache-map.js
index 7953e2cc..bcfb2ff4 100644
--- a/ext/mixed/js/cache-map.js
+++ b/ext/mixed/js/cache-map.js
@@ -24,7 +24,7 @@ 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)
+     *   The signature is: create(path)
      */
     constructor(maxCount, create) {
         if (!(
@@ -60,11 +60,56 @@ class CacheMap {
     }
 
     /**
+     * Returns whether or not an item exists at the given path.
+     * @param path Array corresponding to the key of the cache.
+     * @returns A boolean indicating whether ot not the item exists.
+     */
+    has(path) {
+        const node = this._accessNode(false, false, null, false, path);
+        return (node !== null);
+    }
+
+    /**
+     * Gets an item at the given path, if it exists. Otherwise, returns undefined.
+     * @param path Array corresponding to the key of the cache.
+     * @returns The existing value at the path, if any; otherwise, undefined.
+     */
+    get(path) {
+        const node = this._accessNode(false, false, null, true, path);
+        return (node !== null ? node.value : void 0);
+    }
+
+    /**
      * 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.
+     * @param path Array corresponding to the key of the cache.
+     * @returns The existing value at the path, if any; otherwise, a newly created value.
      */
-    get(...path) {
+    getOrCreate(path) {
+        return this._accessNode(true, false, null, true, path).value;
+    }
+
+    /**
+     * Sets a value at a given path.
+     * @param path Array corresponding to the key of the cache.
+     * @param value The value to store in the cache.
+     */
+    set(path, value) {
+        this._accessNode(false, true, value, true, path);
+    }
+
+    /**
+     * Clears the cache.
+     */
+    clear() {
+        this._map.clear();
+        this._count = 0;
+        this._resetEndNodes();
+    }
+
+    // Private
+
+    _accessNode(create, set, value, updateRecency, path) {
         let ii = path.length;
         if (ii === 0) { throw new Error('Invalid path'); }
 
@@ -77,13 +122,18 @@ class CacheMap {
         }
 
         if (i === ii) {
-            // Found (map is now a node)
-            this._updateRecency(map);
-            return map.value;
+            // Found (map should now be a node)
+            if (updateRecency) { this._updateRecency(map); }
+            if (set) { map.value = value; }
+            return map;
         }
 
         // Create new
-        const value = this._create(...path);
+        if (create) {
+            value = this._create(path);
+        } else if (!set) {
+            return null;
+        }
 
         // Create mapping
         --ii;
@@ -101,20 +151,9 @@ class CacheMap {
 
         this._updateCount();
 
-        return value;
-    }
-
-    /**
-     * Clears the cache.
-     */
-    clear() {
-        this._map.clear();
-        this._count = 0;
-        this._resetEndNodes();
+        return node;
     }
 
-    // Private
-
     _updateRecency(node) {
         this._removeNode(node);
         this._addNode(node, this._listFirst);
diff --git a/test/test-cache-map.js b/test/test-cache-map.js
index 9307dd2c..12367a90 100644
--- a/test/test-cache-map.js
+++ b/test/test-cache-map.js
@@ -57,101 +57,154 @@ function testApi() {
             maxCount: 1,
             expectedCount: 1,
             calls: [
-                ['get', 'a', 'b', 'c']
+                {func: 'getOrCreate', args: [['a', 'b', 'c']]}
             ]
         },
         {
             maxCount: 10,
             expectedCount: 1,
             calls: [
-                ['get', 'a', 'b', 'c'],
-                ['get', 'a', 'b', 'c'],
-                ['get', 'a', 'b', 'c']
+                {func: 'getOrCreate', args: [['a', 'b', 'c']]},
+                {func: 'getOrCreate', args: [['a', 'b', 'c']]},
+                {func: 'getOrCreate', args: [['a', 'b', 'c']]}
             ]
         },
         {
             maxCount: 10,
             expectedCount: 3,
             calls: [
-                ['get', 'a1', 'b', 'c'],
-                ['get', 'a2', 'b', 'c'],
-                ['get', 'a3', 'b', 'c']
+                {func: 'getOrCreate', args: [['a1', 'b', 'c']]},
+                {func: 'getOrCreate', args: [['a2', 'b', 'c']]},
+                {func: 'getOrCreate', args: [['a3', 'b', 'c']]}
             ]
         },
         {
             maxCount: 10,
             expectedCount: 3,
             calls: [
-                ['get', 'a', 'b1', 'c'],
-                ['get', 'a', 'b2', 'c'],
-                ['get', 'a', 'b3', 'c']
+                {func: 'getOrCreate', args: [['a', 'b1', 'c']]},
+                {func: 'getOrCreate', args: [['a', 'b2', 'c']]},
+                {func: 'getOrCreate', args: [['a', 'b3', 'c']]}
             ]
         },
         {
             maxCount: 10,
             expectedCount: 3,
             calls: [
-                ['get', 'a', 'b', 'c1'],
-                ['get', 'a', 'b', 'c2'],
-                ['get', 'a', 'b', 'c3']
+                {func: 'getOrCreate', args: [['a', 'b', 'c1']]},
+                {func: 'getOrCreate', args: [['a', 'b', 'c2']]},
+                {func: 'getOrCreate', args: [['a', 'b', 'c3']]}
             ]
         },
         {
             maxCount: 1,
             expectedCount: 1,
             calls: [
-                ['get', 'a1', 'b', 'c'],
-                ['get', 'a2', 'b', 'c'],
-                ['get', 'a3', 'b', 'c']
+                {func: 'getOrCreate', args: [['a1', 'b', 'c']]},
+                {func: 'getOrCreate', args: [['a2', 'b', 'c']]},
+                {func: 'getOrCreate', args: [['a3', 'b', 'c']]}
             ]
         },
         {
             maxCount: 1,
             expectedCount: 1,
             calls: [
-                ['get', 'a', 'b1', 'c'],
-                ['get', 'a', 'b2', 'c'],
-                ['get', 'a', 'b3', 'c']
+                {func: 'getOrCreate', args: [['a', 'b1', 'c']]},
+                {func: 'getOrCreate', args: [['a', 'b2', 'c']]},
+                {func: 'getOrCreate', args: [['a', 'b3', 'c']]}
             ]
         },
         {
             maxCount: 1,
             expectedCount: 1,
             calls: [
-                ['get', 'a', 'b', 'c1'],
-                ['get', 'a', 'b', 'c2'],
-                ['get', 'a', 'b', 'c3']
+                {func: 'getOrCreate', args: [['a', 'b', 'c1']]},
+                {func: 'getOrCreate', args: [['a', 'b', 'c2']]},
+                {func: 'getOrCreate', args: [['a', 'b', 'c3']]}
             ]
         },
         {
             maxCount: 10,
             expectedCount: 0,
             calls: [
-                ['get', 'a', 'b', 'c1'],
-                ['get', 'a', 'b', 'c2'],
-                ['get', 'a', 'b', 'c3'],
-                ['clear']
+                {func: 'getOrCreate', args: [['a', 'b', 'c1']]},
+                {func: 'getOrCreate', args: [['a', 'b', 'c2']]},
+                {func: 'getOrCreate', args: [['a', 'b', 'c3']]},
+                {func: 'clear', args: []}
             ]
         },
         {
             maxCount: 0,
             expectedCount: 0,
             calls: [
-                ['get', 'a1', 'b', 'c'],
-                ['get', 'a', 'b2', 'c'],
-                ['get', 'a', 'b', 'c3']
+                {func: 'getOrCreate', args: [['a1', 'b', 'c']]},
+                {func: 'getOrCreate', args: [['a', 'b2', 'c']]},
+                {func: 'getOrCreate', args: [['a', 'b', 'c3']]}
+            ]
+        },
+        {
+            maxCount: 10,
+            expectedCount: 1,
+            calls: [
+                {func: 'get', args: [['a1', 'b', 'c']], returnValue: void 0},
+                {func: 'has', args: [['a1', 'b', 'c']], returnValue: false},
+                {func: 'set', args: [['a1', 'b', 'c'], 32], returnValue: void 0},
+                {func: 'get', args: [['a1', 'b', 'c']], returnValue: 32},
+                {func: 'has', args: [['a1', 'b', 'c']], returnValue: true}
+            ]
+        },
+        {
+            maxCount: 10,
+            expectedCount: 2,
+            calls: [
+                {func: 'set', args: [['a1', 'b', 'c'], 32], returnValue: void 0},
+                {func: 'get', args: [['a1', 'b', 'c']], returnValue: 32},
+                {func: 'set', args: [['a1', 'b', 'c'], 64], returnValue: void 0},
+                {func: 'get', args: [['a1', 'b', 'c']], returnValue: 64},
+                {func: 'set', args: [['a2', 'b', 'c'], 96], returnValue: void 0},
+                {func: 'get', args: [['a2', 'b', 'c']], returnValue: 96}
+            ]
+        },
+        {
+            maxCount: 2,
+            expectedCount: 2,
+            calls: [
+                {func: 'has', args: [['a1', 'b', 'c']], returnValue: false},
+                {func: 'has', args: [['a2', 'b', 'c']], returnValue: false},
+                {func: 'has', args: [['a3', 'b', 'c']], returnValue: false},
+                {func: 'set', args: [['a1', 'b', 'c'], 1], returnValue: void 0},
+                {func: 'has', args: [['a1', 'b', 'c']], returnValue: true},
+                {func: 'has', args: [['a2', 'b', 'c']], returnValue: false},
+                {func: 'has', args: [['a3', 'b', 'c']], returnValue: false},
+                {func: 'set', args: [['a2', 'b', 'c'], 2], returnValue: void 0},
+                {func: 'has', args: [['a1', 'b', 'c']], returnValue: true},
+                {func: 'has', args: [['a2', 'b', 'c']], returnValue: true},
+                {func: 'has', args: [['a3', 'b', 'c']], returnValue: false},
+                {func: 'set', args: [['a3', 'b', 'c'], 3], returnValue: void 0},
+                {func: 'has', args: [['a1', 'b', 'c']], returnValue: false},
+                {func: 'has', args: [['a2', 'b', 'c']], returnValue: true},
+                {func: 'has', args: [['a3', 'b', 'c']], returnValue: true}
             ]
         }
     ];
 
-    const create = (...args) => args.join(',');
+    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;
+        for (const call of calls) {
+            const {func, args} = call;
+            let returnValue;
+            switch (func) {
+                case 'get': returnValue = cache.get(...args); break;
+                case 'getOrCreate': returnValue = cache.getOrCreate(...args); break;
+                case 'set': returnValue = cache.set(...args); break;
+                case 'has': returnValue = cache.has(...args); break;
+                case 'clear': returnValue = cache.clear(...args); break;
+            }
+            if (Object.prototype.hasOwnProperty.call(call, 'returnValue')) {
+                const {returnValue: expectedReturnValue} = call;
+                assert.deepStrictEqual(returnValue, expectedReturnValue);
             }
         }
         assert.strictEqual(cache.count, expectedCount);