From: Lady Date: Sat, 27 May 2023 06:42:55 +0000 (-0700) Subject: Initial {memory ∣ storage} model X-Git-Url: https://git.ladys.computer/Etiquette/commitdiff_plain/ce40db353c27887f4345c88fc70a7251bf688bbb Initial {memory ∣ storage} model --- diff --git a/deno.lock b/deno.lock new file mode 100644 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 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 . + +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 index 0000000..ed20df8 --- /dev/null +++ b/dev-deps.js @@ -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 . + +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 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 . + +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 index 0000000..8187635 --- /dev/null +++ b/memory.test.js @@ -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 . + +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; + }); + }); + }); +});