Small improvements to storage

[Etiquette] / memory.js

// 📧🏷️ É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 } = (() => {
    if ($ == null) {
      // No value was provided; generate a random one and store its
      // buffer.
      const values = crypto.getRandomValues(new Uint32Array(1));
      const { buffer } = values;
      return {
        number: new DataView(buffer).getUint32(0) >>> 2,
        buffer,
      };
    } else {
      // A value was provided, so a buffer needs to be generated.
      const number = $ & -1 >>> 2;
      const buffer = new ArrayBuffer(4);
      new DataView(buffer).setUint32(0, number << 2, false);
      return { number, buffer };
    }
  })();
  const checksum = number % 37;
  const wrmg = wrmgBase32String(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 30‐bit W·R·M·G base32
 * identifier and then returns that same identifier in normalized form.
 *
 * ☡ This function will throw if the provided value is not a 30‐bit
 * W·R·M·G base32 value with a leading checksum.
 *
 * ※ 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.
   *
   * The identifier `000-0000` is deleted from the start and can only
   * be manually set.
   */
  #deleted = new Set([`${mintID(0)}`]);

  /** 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.
            //
            // ※ Successive identifiers are used in order to guarantee
            // an eventual result; continuing to generate random
            // identifiers could go on forever.
            id = mintID(id.value + 1);
            literalValue = `${id}`;
          }
          return literalValue;
        } else {
          // ☡ There are no identifiers left to assign.
          //
          // ※ This is unlikely to ever be possible in practice.
          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 normalized = normalizeID(id);
    this.#deleted.add(normalized);
    return store.delete(normalized);
  }

  /** 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 normalized = normalizeID(id);
    const data = store.get(normalized);
    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, normalized);
    }
  }

  /**
   * 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)];
    }
  }
}