commit a091e7c4c132680be00a5021386dcad16f6b45df
parent 2633fd83c25fe178b19aac2cd7649d3745ffd54a
Author: Henrik Skupin <mail@hskupin.info>
Date: Mon, 1 Dec 2025 20:43:58 +0000
Bug 2000801 - [remote] Add class for bi-directional maps (BiMap). r=jdescottes
Differential Revision: https://phabricator.services.mozilla.com/D273538
Diffstat:
4 files changed, 304 insertions(+), 0 deletions(-)
diff --git a/remote/jar.mn b/remote/jar.mn
@@ -16,6 +16,7 @@ remote.jar:
content/shared/Addon.sys.mjs (shared/Addon.sys.mjs)
content/shared/AppInfo.sys.mjs (shared/AppInfo.sys.mjs)
content/shared/AsyncQueue.sys.mjs (shared/AsyncQueue.sys.mjs)
+ content/shared/BiMap.sys.mjs (shared/BiMap.sys.mjs)
content/shared/Browser.sys.mjs (shared/Browser.sys.mjs)
content/shared/Capture.sys.mjs (shared/Capture.sys.mjs)
content/shared/ChallengeHeaderParser.sys.mjs (shared/ChallengeHeaderParser.sys.mjs)
diff --git a/remote/shared/BiMap.sys.mjs b/remote/shared/BiMap.sys.mjs
@@ -0,0 +1,139 @@
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+const lazy = {};
+
+ChromeUtils.defineESModuleGetters(lazy, {
+ generateUUID: "chrome://remote/content/shared/UUID.sys.mjs",
+});
+
+/**
+ * A bidirectional map that maintains two-way mappings between UUIDs and objects.
+ *
+ * This class ensures that each object maps to exactly one UUID
+ * and vice versa. Also it allows efficient lookup in both directions:
+ *
+ * - from a UUID to an object
+ * - from an object to a UUID
+ */
+export class BiMap {
+ #idToObject;
+ #objectToId;
+
+ constructor() {
+ this.#idToObject = new Map();
+ this.#objectToId = new Map();
+ }
+
+ /**
+ * Clears all the mappings.
+ */
+ clear() {
+ this.#idToObject = new Map();
+ this.#objectToId = new Map();
+ }
+
+ /**
+ * Deletes a mapping by the given object.
+ *
+ * @param {object} object
+ * The object to remove from the BiMap.
+ */
+ deleteByObject(object) {
+ const id = this.#objectToId.get(object);
+
+ if (id !== undefined) {
+ this.#objectToId.delete(object);
+ this.#idToObject.delete(id);
+ }
+ }
+
+ /**
+ * Deletes a mapping by the given id.
+ *
+ * @param {string} id
+ * The id to remove from the BiMap.
+ */
+ deleteById(id) {
+ const object = this.#idToObject.get(id);
+
+ if (object !== undefined) {
+ this.#idToObject.delete(id);
+ this.#objectToId.delete(object);
+ }
+ }
+
+ /**
+ * Retrieves the id for the given object, or inserts a new mapping if not found.
+ *
+ * @param {object} object
+ * The object to look up or insert.
+ *
+ * @returns {string}
+ * The id associated with the object.
+ */
+ getOrInsert(object) {
+ if (this.hasObject(object)) {
+ return this.getId(object);
+ }
+
+ const id = lazy.generateUUID();
+ this.#objectToId.set(object, id);
+ this.#idToObject.set(id, object);
+
+ return id;
+ }
+
+ /**
+ * Retrieves the id associated with the given object.
+ *
+ * @param {object} object
+ * The object to look up.
+ *
+ * @returns {string}
+ * The id associated with the object, or undefined if not found.
+ */
+ getId(object) {
+ return this.#objectToId.get(object);
+ }
+
+ /**
+ * Retrieves the object associated with the given id.
+ *
+ * @param {string} id
+ * The id to look up.
+ *
+ * @returns {object}
+ * The object associated with the id, or undefined if not found.
+ */
+ getObject(id) {
+ return this.#idToObject.get(id);
+ }
+
+ /**
+ * Checks whether the BiMap contains the given id.
+ *
+ * @param {string} id
+ * The id to check for.
+ *
+ * @returns {boolean}
+ * True if the id exists in the BiMap, false otherwise.
+ */
+ hasId(id) {
+ return this.#idToObject.has(id);
+ }
+
+ /**
+ * Checks whether the BiMap contains the given object.
+ *
+ * @param {object} object
+ * The object to check for.
+ *
+ * @returns {boolean}
+ * True if the object exists in the BiMap, false otherwise.
+ */
+ hasObject(object) {
+ return this.#objectToId.has(object);
+ }
+}
diff --git a/remote/shared/test/xpcshell/test_BiMap.js b/remote/shared/test/xpcshell/test_BiMap.js
@@ -0,0 +1,162 @@
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this file,
+ * You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+const { BiMap } = ChromeUtils.importESModule(
+ "chrome://remote/content/shared/BiMap.sys.mjs"
+);
+
+add_task(function test_BiMap_constructor() {
+ const bimap = new BiMap();
+ ok(bimap, "BiMap instance created");
+});
+
+add_task(function test_BiMap_clear() {
+ const bimap = new BiMap();
+ const obj1 = { foo: "bar" };
+ const obj2 = { baz: "qux" };
+
+ const id1 = bimap.getOrInsert(obj1);
+ const id2 = bimap.getOrInsert(obj2);
+
+ ok(bimap.hasId(id1), "First id exists before clear");
+ ok(bimap.hasId(id2), "Second id exists before clear");
+
+ bimap.clear();
+
+ ok(!bimap.hasId(id1), "First id removed after clear");
+ ok(!bimap.hasId(id2), "Second id removed after clear");
+ ok(!bimap.hasObject(obj1), "First object removed after clear");
+ ok(!bimap.hasObject(obj2), "Second object removed after clear");
+});
+
+add_task(function test_BiMap_getOrInsert() {
+ const bimap = new BiMap();
+ const obj = { foo: "bar" };
+
+ const regExpUUID = new RegExp(
+ /^[a-f|0-9]{8}-[a-f|0-9]{4}-[a-f|0-9]{4}-[a-f|0-9]{4}-[a-f|0-9]{12}$/g
+ );
+
+ const id = bimap.getOrInsert(obj);
+
+ ok(regExpUUID.test(id), "Returned a valid UUID");
+ equal(bimap.getId(obj), id, "Object is mapped to the id");
+ equal(bimap.getObject(id), obj, "Id is mapped to the object");
+});
+
+add_task(function test_BiMap_multipleMappings() {
+ const bimap = new BiMap();
+ const obj1 = { name: "first" };
+ const obj2 = { name: "second" };
+ const obj3 = { name: "third" };
+
+ const id1 = bimap.getOrInsert(obj1);
+ const id2 = bimap.getOrInsert(obj2);
+ const id3 = bimap.getOrInsert(obj3);
+
+ equal(bimap.getId(obj1), id1, "First mapping correct");
+ equal(bimap.getId(obj2), id2, "Second mapping correct");
+ equal(bimap.getId(obj3), id3, "Third mapping correct");
+
+ equal(bimap.getObject(id1), obj1, "First reverse mapping correct");
+ equal(bimap.getObject(id2), obj2, "Second reverse mapping correct");
+ equal(bimap.getObject(id3), obj3, "Third reverse mapping correct");
+});
+
+add_task(function test_BiMap_getId() {
+ const bimap = new BiMap();
+ const obj = { foo: "bar" };
+
+ equal(bimap.getId(obj), undefined, "Returns undefined for unknown object");
+
+ const id = bimap.getOrInsert(obj);
+
+ equal(bimap.getId(obj), id, "Retrieved correct id for object");
+});
+
+add_task(function test_BiMap_getObject() {
+ const bimap = new BiMap();
+ const obj = { foo: "bar" };
+
+ equal(
+ bimap.getObject("unknown-id"),
+ undefined,
+ "Returns undefined for unknown id"
+ );
+
+ const id = bimap.getOrInsert(obj);
+
+ equal(bimap.getObject(id), obj, "Retrieved correct object for id");
+});
+
+add_task(function test_BiMap_hasId() {
+ const bimap = new BiMap();
+ const obj = { foo: "bar" };
+
+ const id = bimap.getOrInsert(obj);
+
+ ok(!bimap.hasId("unknown-id"), "Returns false for unknown id");
+ ok(bimap.hasId(id), "Returns true for existing id");
+});
+
+add_task(function test_BiMap_hasObject() {
+ const bimap = new BiMap();
+ const obj = { foo: "bar" };
+ const otherObj = { baz: "qux" };
+
+ ok(!bimap.hasObject(otherObj), "Returns false for non-existing object");
+
+ bimap.getOrInsert(obj);
+
+ ok(bimap.hasObject(obj), "Returns true for existing object");
+});
+
+add_task(function test_BiMap_deleteById() {
+ const bimap = new BiMap();
+ const obj = { foo: "bar" };
+
+ const id = bimap.getOrInsert(obj);
+
+ ok(bimap.hasId(id), "Id exists before deletion");
+ ok(bimap.hasObject(obj), "Object exists before deletion");
+
+ // Deleting non-existing id should not affect existing mappings.
+ bimap.deleteById("unknown-id");
+
+ ok(bimap.hasId(id), "Existing id still present");
+ ok(bimap.hasObject(obj), "Existing object still present");
+
+ // Delete existing id.
+ bimap.deleteById(id);
+
+ ok(!bimap.hasId(id), "Id removed after deletion");
+ ok(!bimap.hasObject(obj), "Object removed after deletion");
+ equal(bimap.getId(obj), undefined, "Object no longer maps to id");
+ equal(bimap.getObject(id), undefined, "Id no longer maps to object");
+});
+
+add_task(function test_BiMap_deleteByObject() {
+ const bimap = new BiMap();
+ const obj = { foo: "bar" };
+ const otherObj = { baz: "qux" };
+
+ const id = bimap.getOrInsert(obj);
+
+ ok(bimap.hasId(id), "Id exists before deletion");
+ ok(bimap.hasObject(obj), "Object exists before deletion");
+
+ // Deleting non-existing object should not affect existing mappings.
+ bimap.deleteByObject(otherObj);
+
+ ok(bimap.hasId(id), "Existing id still present");
+ ok(bimap.hasObject(obj), "Existing object still present");
+
+ // Delete existing object.
+ bimap.deleteByObject(obj);
+
+ ok(!bimap.hasId(id), "Id removed after deletion");
+ ok(!bimap.hasObject(obj), "Object removed after deletion");
+ equal(bimap.getId(obj), undefined, "Object no longer maps to id");
+ equal(bimap.getObject(id), undefined, "Id no longer maps to object");
+});
diff --git a/remote/shared/test/xpcshell/xpcshell.toml b/remote/shared/test/xpcshell/xpcshell.toml
@@ -5,6 +5,8 @@ head = "head.js"
["test_AsyncQueue.js"]
+["test_BiMap.js"]
+
["test_ChallengeHeaderParser.js"]
["test_DOM.js"]
