src/common/framework/data_cache.ts

/**
 * Utilities to improve the performance of the CTS, by caching data that is
 * expensive to build using a two-level cache (in-memory, pre-computed file).
 */

import { assert } from '../util/util.js';

interface DataStore {
  load(path: string): Promise<Uint8Array>;
}

/** Logger is a basic debug logger function */
export type Logger = (s: string) => void;

/**
 * DataCacheNode represents a single cache entry in the LRU DataCache.
 * DataCacheNode is a doubly linked list, so that least-recently-used entries can be removed, and
 * cache hits can move the node to the front of the list.
 */
class DataCacheNode {
  public constructor(path: string, data: unknown) {
    this.path = path;
    this.data = data;
  }

  /** insertAfter() re-inserts this node in the doubly-linked list after `prev` */
  public insertAfter(prev: DataCacheNode) {
    this.unlink();
    this.next = prev.next;
    this.prev = prev;
    prev.next = this;
    if (this.next) {
      this.next.prev = this;
    }
  }

  /** unlink() removes this node from the doubly-linked list */
  public unlink() {
    const prev = this.prev;
    const next = this.next;
    if (prev) {
      prev.next = next;
    }
    if (next) {
      next.prev = prev;
    }
    this.prev = null;
    this.next = null;
  }

  public readonly path: string; // The file path this node represents
  public readonly data: unknown; // The deserialized data for this node
  public prev: DataCacheNode | null = null; // The previous node in the doubly-linked list
  public next: DataCacheNode | null = null; // The next node in the doubly-linked list
}

/** DataCache is an interface to a LRU-cached data store used to hold data cached by path */
export class DataCache {
  public constructor() {
    this.lruHeadNode.next = this.lruTailNode;
    this.lruTailNode.prev = this.lruHeadNode;
  }

  /** setDataStore() sets the backing data store used by the data cache */
  public setStore(dataStore: DataStore) {
    this.dataStore = dataStore;
  }

  /** setDebugLogger() sets the verbose logger */
  public setDebugLogger(logger: Logger) {
    this.debugLogger = logger;
  }

  /**
   * fetch() retrieves cacheable data from the data cache, first checking the
   * in-memory cache, then the data store (if specified), then resorting to
   * building the data and storing it in the cache.
   */
  public async fetch<Data>(cacheable: Cacheable<Data>): Promise<Data> {
    {
      // First check the in-memory cache
      const node = this.cache.get(cacheable.path);
      if (node !== undefined) {
        this.log('in-memory cache hit');
        node.insertAfter(this.lruHeadNode);
        return Promise.resolve(node.data as Data);
      }
    }
    this.log('in-memory cache miss');
    // In in-memory cache miss.
    // Next, try the data store.
    if (this.dataStore !== null && !this.unavailableFiles.has(cacheable.path)) {
      let serialized: Uint8Array | undefined;
      try {
        serialized = await this.dataStore.load(cacheable.path);
        this.log('loaded serialized');
      } catch (err) {
        // not found in data store
        this.log(`failed to load (${cacheable.path}): ${err}`);
        this.unavailableFiles.add(cacheable.path);
      }
      if (serialized !== undefined) {
        this.log(`deserializing`);
        const data = cacheable.deserialize(serialized);
        this.addToCache(cacheable.path, data);
        return data;
      }
    }
    // Not found anywhere. Build the data, and cache for future lookup.
    this.log(`cache: building (${cacheable.path})`);
    const data = await cacheable.build();
    this.addToCache(cacheable.path, data);
    return data;
  }

  /**
   * addToCache() creates a new node for `path` and `data`, inserting the new node at the front of
   * the doubly-linked list. If the number of entries in the cache exceeds this.maxCount, then the
   * least recently used entry is evicted
   * @param path the file path for the data
   * @param data the deserialized data
   */
  private addToCache(path: string, data: unknown) {
    if (this.cache.size >= this.maxCount) {
      const toEvict = this.lruTailNode.prev;
      assert(toEvict !== null);
      toEvict.unlink();
      this.cache.delete(toEvict.path);
      this.log(`evicting ${toEvict.path}`);
    }
    const node = new DataCacheNode(path, data);
    node.insertAfter(this.lruHeadNode);
    this.cache.set(path, node);
    this.log(`added ${path}. new count: ${this.cache.size}`);
  }

  private log(msg: string) {
    if (this.debugLogger !== null) {
      this.debugLogger(`DataCache: ${msg}`);
    }
  }

  // Max number of entries in the cache before LRU entries are evicted.
  private readonly maxCount = 4;

  private cache = new Map<string, DataCacheNode>();
  private lruHeadNode = new DataCacheNode('', null); // placeholder node (no path or data)
  private lruTailNode = new DataCacheNode('', null); // placeholder node (no path or data)
  private unavailableFiles = new Set<string>();
  private dataStore: DataStore | null = null;
  private debugLogger: Logger | null = null;
}

/** The data cache */
export const dataCache = new DataCache();

/** true if the current process is building the cache */
let isBuildingDataCache = false;

/** @returns true if the data cache is currently being built */
export function getIsBuildingDataCache() {
  return isBuildingDataCache;
}

/** Sets whether the data cache is currently being built */
export function setIsBuildingDataCache(value = true) {
  isBuildingDataCache = value;
}

/**
 * Cacheable is the interface to something that can be stored into the
 * DataCache.
 * The 'npm run gen_cache' tool will look for module-scope variables of this
 * interface, with the name `d`.
 */
export interface Cacheable<Data> {
  /** the globally unique path for the cacheable data */
  readonly path: string;

  /**
   * build() builds the cacheable data.
   * This is assumed to be an expensive operation and will only happen if the
   * cache does not already contain the built data.
   */
  build(): Promise<Data>;

  /**
   * serialize() encodes `data` to a binary representation so that it can be stored in a cache file.
   */
  serialize(data: Data): Uint8Array;

  /**
   * deserialize() is the inverse of serialize(), decoding the binary representation back to a Data
   * object.
   */
  deserialize(binary: Uint8Array): Data;
}