]> Lady’s Gitweb - Etiquette/commitdiff
Initial {memory ∣ storage} model
authorLady <redacted>
Sat, 27 May 2023 06:42:55 +0000 (23:42 -0700)
committerLady <redacted>
Wed, 14 Jun 2023 02:06:50 +0000 (19:06 -0700)
deno.lock [new file with mode: 0644]
deps.js [new file with mode: 0644]
dev-deps.js [new file with mode: 0644]
memory.js [new file with mode: 0644]
memory.test.js [new file with mode: 0644]

diff --git a/deno.lock b/deno.lock
new file mode 100644 (file)
index 0000000..3aecc25
--- /dev/null
+++ b/deno.lock
@@ -0,0 +1,19 @@
+{
+  "version": "2",
+  "remote": {
+    "https://deno.land/std@0.189.0/fmt/colors.ts": "d67e3cd9f472535241a8e410d33423980bec45047e343577554d3356e1f0ef4e",
+    "https://deno.land/std@0.189.0/testing/_diff.ts": "1a3c044aedf77647d6cac86b798c6417603361b66b54c53331b312caeb447aea",
+    "https://deno.land/std@0.189.0/testing/_format.ts": "a69126e8a469009adf4cf2a50af889aca364c349797e63174884a52ff75cf4c7",
+    "https://deno.land/std@0.189.0/testing/_test_suite.ts": "30f018feeb3835f12ab198d8a518f9089b1bcb2e8c838a8b615ab10d5005465c",
+    "https://deno.land/std@0.189.0/testing/asserts.ts": "e16d98b4d73ffc4ed498d717307a12500ae4f2cbe668f1a215632d19fcffc22f",
+    "https://deno.land/std@0.189.0/testing/bdd.ts": "59f7f7503066d66a12e50ace81bfffae5b735b6be1208f5684b630ae6b4de1d0",
+    "https://deno.land/std@0.189.0/testing/mock.ts": "220ed9b8151cb2cac141043d4cfea7c47673fab5d18d1c1f0943297c8afb5d13",
+    "https://git.ladys.computer/Pisces/blob_plain/0.3.1:/binary.js": "b8691c74168fc7bc9e0c056df76a08ca5e3ffcd78b03d8e9c318e1bc78cf580b",
+    "https://git.ladys.computer/Pisces/blob_plain/0.3.1:/collection.js": "4dfb83bbd082bef873c2ae8904a2ba3204379065b0244e8c5a737b7666888fdc",
+    "https://git.ladys.computer/Pisces/blob_plain/0.3.1:/function.js": "d45970c39106ee652cf681ccf98dc7fa86fcd9578a86d2b65c49bf9fffd7f158",
+    "https://git.ladys.computer/Pisces/blob_plain/0.3.1:/numeric.js": "cb6d0c224b36aec086cbf895c9a6aa593a0fbfdaccc346b0c5be1d1a0bfc1775",
+    "https://git.ladys.computer/Pisces/blob_plain/0.3.1:/object.js": "932e9fa5b07db7b32815c7a7b21b63ef8a92b7de8fdc8bbde0e4ee70baf0b522",
+    "https://git.ladys.computer/Pisces/blob_plain/0.3.1:/string.js": "38697c9a325937254d7de12633890b5848862ea6e7cd51bc08713b0fca86ac21",
+    "https://git.ladys.computer/Pisces/blob_plain/0.3.1:/value.js": "d1e0bac8e3fc6403b67f0b2b979946a257935aa5c18bf1fbf5768a59e61bf59b"
+  }
+}
diff --git a/deps.js b/deps.js
new file mode 100644 (file)
index 0000000..fa371be
--- /dev/null
+++ b/deps.js
@@ -0,0 +1,13 @@
+// 📧🏷️ Étiquette ∷ deps.js
+// ====================================================================
+//
+// Copyright © 2023 Lady [@ Lady’s Computer].
+//
+// 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 <https://mozilla.org/MPL/2.0/>.
+
+export {
+  wrmgBase32Binary,
+  wrmgBase32String,
+} from "https://git.ladys.computer/Pisces/blob_plain/0.3.1:/binary.js";
diff --git a/dev-deps.js b/dev-deps.js
new file mode 100644 (file)
index 0000000..ed20df8
--- /dev/null
@@ -0,0 +1,25 @@
+// 📧🏷️ Étiquette ∷ dev-deps.js
+// ====================================================================
+//
+// Copyright © 2023 Lady [@ Lady’s Computer].
+//
+// 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 <https://mozilla.org/MPL/2.0/>.
+
+export {
+  assert,
+  assertEquals,
+  assertStrictEquals,
+  assertThrows,
+} from "https://deno.land/std@0.189.0/testing/asserts.ts";
+export {
+  beforeEach,
+  describe,
+  it,
+} from "https://deno.land/std@0.189.0/testing/bdd.ts";
+export {
+  assertSpyCall,
+  assertSpyCalls,
+  spy,
+} from "https://deno.land/std@0.189.0/testing/mock.ts";
diff --git a/memory.js b/memory.js
new file mode 100644 (file)
index 0000000..6773bdd
--- /dev/null
+++ b/memory.js
@@ -0,0 +1,361 @@
+// 📧🏷️ Étiquette ∷ memory.js
+// ====================================================================
+//
+// Copyright © 2023 Lady [@ Lady’s Computer].
+//
+// 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 <https://mozilla.org/MPL/2.0/>.
+
+import { wrmgBase32Binary, wrmgBase32String } from "./deps.js";
+
+/**
+ * A symbol which is used internally to identify the constructor
+ * associated with a stored object.
+ *
+ * ※ This value is not exposed.
+ */
+const constructorSymbol = Symbol("constructor");
+
+/**
+ * Mints a new W·R·M·G base32 identifier with a prefixed checksum.
+ *
+ * If an argument is provided, it is used as the underlying numeric
+ * value for the identifier.
+ *
+ * The return value is a `String` *object* with a `.value` own property
+ * giving the underlying numeric value for the string.
+ *
+ * ※ This function is not exposed.
+ */
+const mintID = ($ = null) => {
+  const [number, buffer] = $ == null
+    ? (() => {
+      // No value was provided; generate a random one and store its
+      // buffer.
+      const values = crypto.getRandomValues(new Uint32Array(1));
+      const view = new DataView(values.buffer);
+      return [
+        view.getUint32(0) >>> 2, // drop the final 2 bits
+        view.buffer,
+      ];
+    })()
+    : [$ >>> 0 & -1 >>> 2, null];
+  const checksum = number % 37;
+  const wrmg = wrmgBase32String(
+    buffer ?? (() => {
+      // A value was provided, so a buffer still needs to be generated.
+      const view = new DataView(new ArrayBuffer(4));
+      view.setUint32(0, number << 2, false);
+      return view.buffer;
+    })(),
+  );
+  return Object.assign(
+    new String(
+      `${"0123456789ABCDEFGHJKMNPQRSTVWXYZ*~$=U"[checksum]}${
+        wrmg.substring(0, 2)
+      }-${wrmg.substring(2, 6)}`,
+    ),
+    { value: number },
+  );
+};
+
+/**
+ * Validates the checksum prefixing the provided W·R·M·G base32
+ * identifier and then returns that same identifier in normalized form.
+ *
+ * ※ This function is not exposed.
+ */
+const normalizeID = ($) => {
+  const identifier = `${$}`;
+  const checksum = "0123456789ABCDEFGHJKMNPQRSTVWXYZ*~$=U".indexOf(
+    identifier[0].toUpperCase(),
+  );
+  if (checksum == -1) {
+    // The checksum character is invalid.
+    throw new RangeError(`Invalid checksum: "${identifier[0]}".`);
+  } else {
+    // There is a valid checksum.
+    const binary = wrmgBase32Binary`${identifier.substring(1)}0`;
+    const { byteLength } = binary;
+    if (byteLength != 4) {
+      // The identifier was of unexpected size.
+      throw new RangeError(
+        `Expected id to fit within 4 bytes, but got ${byteLength}.`,
+      );
+    } else {
+      // The identifier was correctly‐sized.
+      const value = new DataView(binary).getUint32(0, false);
+      if (value & 0b11) {
+        // The final two bits, which should have been padded with
+        // zeroes, have a nonzero value.
+        //
+        // This should be impossible and indicates something went very
+        // wrong in base32 decoding.
+        throw new RangeError("Unexpected values in lower two bits");
+      } else {
+        // The final two bits are zero as expected.
+        const number = value >>> 2;
+        if (checksum != number % 37) {
+          // The checksum does not match the number.
+          throw new RangeError(
+            `Invalid checksum for id: ${identifier} (${number})`,
+          );
+        } else {
+          // The checksum matches. Mint a new identifier with the same
+          // number to normalize its form.
+          return `${mintID(number)}`;
+        }
+      }
+    }
+  }
+};
+
+/**
+ * A symbol which is used to identify the method for constructing a new
+ * instance of a constructor based on stored data.
+ *
+ * ※ This value is exposed as `Storage.toInstance`.
+ */
+const toInstanceSymbol = Symbol("Storage.toInstance");
+
+/**
+ * A symbol which is used to identify the method for converting an
+ * instance into an object of enumerable own properties suitable for
+ * persistence.
+ *
+ * ※ This value is exposed as `Storage.toObject`.
+ */
+const toObjectSymbol = Symbol("Storage.toObject");
+
+/**
+ * An in‐memory store of items with checksum‐prefixed 6‐digit W·R·M·G
+ * base32 identifiers.
+ */
+export class Storage {
+  static {
+    // Define `Storage.toInstance` and `Storage.toObject` as
+    // nonconfigurable, non·enumerable, read·only properties with the
+    // appropriate values.
+    Object.defineProperties(this, {
+      toInstance: {
+        configurable: false,
+        enumerable: false,
+        value: toInstanceSymbol,
+        writable: false,
+      },
+      toObject: {
+        configurable: false,
+        enumerable: false,
+        value: toObjectSymbol,
+        writable: false,
+      },
+    });
+  }
+
+  /**
+   * A `Set` of deleted identifiers, to ensure they are not
+   * re·assigned.
+   */
+  #deleted = new Set();
+
+  /** The `Map` used to actually store the data internally. */
+  #store = new Map();
+
+  /**
+   * Returns a new instance constructed from the provided data as
+   * retrieved from the provided identifier.
+   */
+  #construct(data, id) {
+    const {
+      [constructorSymbol]: constructor,
+      ...object
+    } = data;
+    if (!(toInstanceSymbol in constructor)) {
+      // There is no method on the constructor for generating an
+      // instance.
+      throw new TypeError(
+        "Constructor must implement Storage.toInstance for object to be retrieved.",
+      );
+    } else {
+      // Generate an instance and return it.
+      return constructor[toInstanceSymbol](object, id);
+    }
+  }
+
+  /**
+   * Stores the provided instance and returns its identifier.
+   *
+   * If a second argument is given, that identifier will be used;
+   * otherwise, an unused one will be allocated.
+   */
+  #persist(instance, maybeID = null) {
+    const store = this.#store;
+    const deleted = this.#deleted;
+    if (Object(instance) !== instance) {
+      // The provided value is not an object.
+      throw new TypeError("Only objects can be stored.");
+    } else if (!(toObjectSymbol in instance)) {
+      // The provided value does not have a method for generating an
+      // object to store.
+      throw new TypeError(
+        "Object must implement Storage.toObject to be stored.",
+      );
+    } else {
+      // The provided value has a method for generating a storage
+      // object.
+      const { constructor } = instance;
+      const object = instance[toObjectSymbol]();
+      const id = maybeID ?? (() => {
+        // No identifier was provided; attempt to generate one.
+        if (deleted.size + store.size < 1 << 30) {
+          // There is at least one available identifier.
+          let id = mintID();
+          let literalValue = `${id}`;
+          while (
+            deleted.has(literalValue) || store.has(literalValue)
+          ) {
+            // Generate successive identifiers until an available one
+            // is reached.
+            id = mintID(id.value + 1);
+            literalValue = `${id}`;
+          }
+          return literalValue;
+        } else {
+          // There are no identifiers left to assign.
+          throw new TypeError("Out of room.");
+        }
+      })();
+      store.set(
+        id,
+        Object.assign(
+          Object.create(null, {
+            [constructorSymbol]: {
+              configurable: false,
+              enumerable: false,
+              value: constructor,
+              writable: false,
+            },
+          }),
+          object,
+        ),
+      );
+      return id;
+    }
+  }
+
+  /**
+   * Stores the provided object with a new identifier, and returns the
+   * assigned identifier.
+   */
+  add(instance) {
+    return this.#persist(instance);
+  }
+
+  /**
+   * Removes the data at the provided identifier.
+   *
+   * The identifier will not be re·assigned.
+   */
+  delete(id) {
+    const store = this.#store;
+    const validID = normalizeID(id);
+    this.#deleted.add(validID);
+    return store.delete(validID);
+  }
+
+  /** Yields successive identifier~instance pairs from storage. */
+  *entries() {
+    for (const [id, data] of this.#store.entries()) {
+      // Iterate over the entries, construct instances, and yield them
+      // with their identifiers.
+      yield [id, this.#construct(data, id)];
+    }
+  }
+
+  /**
+   * Call the provided callback function with successive instances
+   * constructed from data in storage.
+   *
+   * The callback function will be called with the constructed
+   * instance, its identifier, and this `Storage` instance.
+   *
+   * If a second argument is provided, it will be used as the `this`
+   * value.
+   */
+  forEach(callback, thisArg = undefined) {
+    for (const [id, data] of this.#store.entries()) {
+      // Iterate over the entries, construct objects, and call the
+      // callback function with them and their identifiers.
+      callback.call(thisArg, this.#construct(data, id), id, this);
+    }
+  }
+
+  /**
+   * Returns an instance constructed from the data stored at the
+   * provided identifier, or `null` if the identifier has no data.
+   */
+  get(id) {
+    const store = this.#store;
+    const validID = normalizeID(id);
+    const data = store.get(validID);
+    if (data == null) {
+      // No object was at the provided identifier.
+      return null;
+    } else {
+      // The provided identifier had a stored object; return the
+      // constructed instance.
+      return this.#construct(data, validID);
+    }
+  }
+
+  /**
+   * Returns whether the provided identifier currently has data
+   * associated with it.
+   */
+  has(id) {
+    const store = this.#store;
+    return store.has(normalizeID(id));
+  }
+
+  /** Yields successive identifiers with data in storage. */
+  *keys() {
+    yield* this.#store.keys();
+  }
+
+  /**
+   * Sets the data for the provided identifier to be that generated
+   * from the provided instance, then returns this `Storage` object.
+   */
+  set(id, instance) {
+    this.#persist(instance, normalizeID(id));
+    return this;
+  }
+
+  /**
+   * Returns the number of identifiers with data in storage.
+   *
+   * ☡ This number may be smaller than the actual number of used
+   * identifiers, as deleted identifiers are *not* freed up for re·use.
+   */
+  get size() {
+    return this.#store.size;
+  }
+
+  /** Yields successive instances constructed from data in storage. */
+  *values() {
+    for (const [id, data] of this.#store.entries()) {
+      // Iterate over the entries, construct instances, and yield them.
+      yield this.#construct(data, id);
+    }
+  }
+
+  /** Yields successive identifier~instance pairs from storage. */
+  *[Symbol.iterator]() {
+    for (const [id, data] of this.#store.entries()) {
+      // Iterate over the entries, construct instances, and yield them
+      // with their identifiers.
+      yield [id, this.#construct(data, id)];
+    }
+  }
+}
diff --git a/memory.test.js b/memory.test.js
new file mode 100644 (file)
index 0000000..8187635
--- /dev/null
@@ -0,0 +1,267 @@
+// 📧🏷️ Étiquette ∷ memory.test.js
+// ====================================================================
+//
+// Copyright © 2023 Lady [@ Lady’s Computer].
+//
+// 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 <https://mozilla.org/MPL/2.0/>.
+
+import {
+  assert,
+  assertEquals,
+  assertStrictEquals,
+  assertThrows,
+  beforeEach,
+  describe,
+  it,
+} from "./dev-deps.js";
+import { Storage } from "./memory.js";
+
+/** A simple storable class for use in testing. */
+class Storable {
+  /** Constructs a new instance with the provided data. */
+  constructor(data) {
+    this.data = data;
+    this.id = null;
+  }
+
+  /** Returns a new instance with the provided data and id. */
+  static [Storage.toInstance](data, id) {
+    const result = new Storable(data);
+    result.id = id;
+    return result;
+  }
+
+  /** Returns the data of this instance. */
+  [Storage.toObject]() {
+    return this.data;
+  }
+}
+
+describe("Storage", () => {
+  it("[[Construct]] creates a new Storage", () => {
+    assertStrictEquals(
+      Object.getPrototypeOf(new Storage()),
+      Storage.prototype,
+    );
+  });
+
+  describe(".toInstance", () => {
+    it("[[Get]] returns a symbol", () => {
+      assertStrictEquals(typeof Storage.toInstance, "symbol");
+    });
+
+    it("[[Set]] throws", () => {
+      assertThrows(() => Storage.toInstance = null);
+    });
+  });
+
+  describe(".toObject", () => {
+    it("[[Get]] returns a symbol", () => {
+      assertStrictEquals(typeof Storage.toObject, "symbol");
+    });
+
+    it("[[Set]] throws", () => {
+      assertThrows(() => Storage.toObject = null);
+    });
+  });
+
+  describe("::add", () => {
+    let instance;
+
+    beforeEach(() => {
+      instance = new Storage();
+    });
+
+    it("[[Call]] returns an id", () => {
+      const result = instance.add(new Storable());
+      assertStrictEquals(typeof result, "string");
+      assert(
+        /^[0-9A-Z*~$=][0-9A-TV-Z]{2}-[0-9A-TV-Z]{4}$/u.test(result),
+      );
+    });
+
+    it("[[Call]] stores data for retrieval later", () => {
+      const data = { my: "data" };
+      const storable = new Storable(data);
+      const newID = instance.add(storable);
+      assertEquals(instance.get(newID).data, data);
+    });
+
+    it("[[Call]] does not store non‐enumerable properties", () => {
+      const data = Object.create(null, {
+        gone: { enumerable: false },
+      });
+      const storable = new Storable(data);
+      const newID = instance.add(storable);
+      assert(!("gone" in instance.get(newID).data));
+    });
+
+    it("[[Call]] does not store prototype properties", () => {
+      const data = Object.create({ gone: true });
+      const storable = new Storable(data);
+      const newID = instance.add(storable);
+      assert(!("gone" in instance.get(newID).data));
+    });
+
+    it("[[Call]] throws if the provided value is not an object", () => {
+      assertThrows(() => {
+        instance.add("");
+      });
+    });
+
+    it("[[Call]] throws if the provided value does not implement `[Storage.toObject]`", () => {
+      assertThrows(() => {
+        instance.add(Object.create(null));
+      });
+    });
+  });
+
+  describe("::delete", () => {
+    let instance;
+
+    beforeEach(() => {
+      instance = new Storage();
+    });
+
+    it("[[Call]] returns whether the value was assigned", () => {
+      assertStrictEquals(instance.delete("000-0000"), false);
+      const newID = instance.add(new Storable());
+      assertStrictEquals(instance.delete(newID), true);
+    });
+
+    it("[[Call]] deletes the value", () => {
+      const newID = instance.add(new Storable());
+      instance.delete(newID);
+      assertStrictEquals(instance.get(newID), null);
+    });
+
+    it("[[Call]] throws if the provided identifier is invalid", () => {
+      assertThrows(() => {
+        instance.delete("");
+      });
+    });
+  });
+
+  describe("::has", () => {
+    let instance;
+
+    beforeEach(() => {
+      instance = new Storage();
+    });
+
+    it("[[Call]] returns whether the value was assigned", () => {
+      assertStrictEquals(instance.has("000-0000"), false);
+      instance.set("000-0000", new Storable());
+      assertStrictEquals(instance.has("000-0000"), true);
+      instance.delete("000-0000")
+      assertStrictEquals(instance.has("000-0000"), false);
+    });
+
+    it("[[Call]] throws if the provided identifier is invalid", () => {
+      assertThrows(() => {
+        instance.has("");
+      });
+    });
+  });
+
+  describe("::set", () => {
+    let instance;
+    let newID;
+
+    beforeEach(() => {
+      instance = new Storage();
+      newID = new Storage().add(new Storable());
+    });
+
+    it("[[Call]] returns the instance", () => {
+      const result = instance.set(newID, new Storable());
+      assertStrictEquals(result, instance);
+    });
+
+    it("[[Call]] stores data for retrieval later", () => {
+      const data = { my: "data" };
+      const storable = new Storable(data);
+      instance.set(newID, storable);
+      assertEquals(instance.get(newID).data, data);
+    });
+
+    it("[[Call]] updates existing data", () => {
+      const data = { my: "data" };
+      const storable = new Storable(data);
+      instance.set(newID, storable);
+      data.my = "new data"
+      instance.set(newID, storable);
+      assertEquals(instance.get(newID).data, data);
+    });
+
+    it("[[Call]] does not store non‐enumerable properties", () => {
+      const data = Object.create(null, {
+        gone: { enumerable: false },
+      });
+      const storable = new Storable(data);
+      instance.set(newID, storable);
+      assert(!("gone" in instance.get(newID).data));
+    });
+
+    it("[[Call]] does not store prototype properties", () => {
+      const data = Object.create({ gone: true });
+      const storable = new Storable(data);
+      instance.set(newID, storable);
+      assert(!("gone" in instance.get(newID).data));
+    });
+
+    it("[[Call]] throws if the provided identifier is invalid", () => {
+      assertThrows(() => {
+        instance.set("", new Storable());
+      });
+    });
+
+    it("[[Call]] throws if the provided value is not an object", () => {
+      assertThrows(() => {
+        instance.set(newID, "");
+      });
+    });
+
+    it("[[Call]] throws if the provided value does not implement `[Storage.toObject]`", () => {
+      assertThrows(() => {
+        instance.set(newID, Object.create(null));
+      });
+    });
+  });
+
+  describe("::size", () => {
+    let instance;
+
+    beforeEach(() => {
+      instance = new Storage();
+    });
+
+    it("[[Get]] returns the number of stored values", () => {
+      assertStrictEquals(instance.size, 0);
+      instance.add(new Storable());
+      assertStrictEquals(instance.size, 1);
+      const newID = instance.add(new Storable());
+      assertStrictEquals(instance.size, 2);
+      instance.set(newID, new Storable());
+      assertStrictEquals(instance.size, 2);
+    });
+
+    it("[[Get]] does not count deleted values", () => {
+      assertStrictEquals(instance.size, 0);
+      instance.add(new Storable());
+      assertStrictEquals(instance.size, 1);
+      const newID = instance.add(new Storable());
+      assertStrictEquals(instance.size, 2);
+      instance.delete(newID);
+      assertStrictEquals(instance.size, 1);
+    });
+
+    it("[[Set]] throws when setting", () => {
+      assertThrows(() => {
+        instance.size = 1;
+      });
+    });
+  });
+});
This page took 0.048077 seconds and 4 git commands to generate.