AK-21/Graphite-Industrial-Intelligence

1/**2 * Some of the internal operations of micromark do lots of editing3 * operations on very large arrays. This runs into problems with two4 * properties of most circa-2020 JavaScript interpreters:5 *6 *  - Array-length modifications at the high end of an array (push/pop) are7 *    expected to be common and are implemented in (amortized) time8 *    proportional to the number of elements added or removed, whereas9 *    other operations (shift/unshift and splice) are much less efficient.10 *  - Function arguments are passed on the stack, so adding tens of thousands11 *    of elements to an array with `arr.push(...newElements)` will frequently12 *    cause stack overflows. (see <https://stackoverflow.com/questions/22123769/rangeerror-maximum-call-stack-size-exceeded-why>)13 *14 * SpliceBuffers are an implementation of gap buffers, which are a15 * generalization of the "queue made of two stacks" idea. The splice buffer16 * maintains a cursor, and moving the cursor has cost proportional to the17 * distance the cursor moves, but inserting, deleting, or splicing in18 * new information at the cursor is as efficient as the push/pop operation.19 * This allows for an efficient sequence of splices (or pushes, pops, shifts,20 * or unshifts) as long such edits happen at the same part of the array or21 * generally sweep through the array from the beginning to the end.22 *23 * The interface for splice buffers also supports large numbers of inputs by24 * passing a single array argument rather passing multiple arguments on the25 * function call stack.26 *27 * @template T28 *   Item type.29 */30export class SpliceBuffer {31  /**32   * @param {ReadonlyArray<T> | null | undefined} [initial]33   *   Initial items (optional).34   * @returns35   *   Splice buffer.36   */37  constructor(initial) {38    /** @type {Array<T>} */39    this.left = initial ? [...initial] : [];40    /** @type {Array<T>} */41    this.right = [];42  }43 44  /**45   * Array access;46   * does not move the cursor.47   *48   * @param {number} index49   *   Index.50   * @return {T}51   *   Item.52   */53  get(index) {54    if (index < 0 || index >= this.left.length + this.right.length) {55      throw new RangeError('Cannot access index `' + index + '` in a splice buffer of size `' + (this.left.length + this.right.length) + '`');56    }57    if (index < this.left.length) return this.left[index];58    return this.right[this.right.length - index + this.left.length - 1];59  }60 61  /**62   * The length of the splice buffer, one greater than the largest index in the63   * array.64   */65  get length() {66    return this.left.length + this.right.length;67  }68 69  /**70   * Remove and return `list[0]`;71   * moves the cursor to `0`.72   *73   * @returns {T | undefined}74   *   Item, optional.75   */76  shift() {77    this.setCursor(0);78    return this.right.pop();79  }80 81  /**82   * Slice the buffer to get an array;83   * does not move the cursor.84   *85   * @param {number} start86   *   Start.87   * @param {number | null | undefined} [end]88   *   End (optional).89   * @returns {Array<T>}90   *   Array of items.91   */92  slice(start, end) {93    /** @type {number} */94    const stop = end === null || end === undefined ? Number.POSITIVE_INFINITY : end;95    if (stop < this.left.length) {96      return this.left.slice(start, stop);97    }98    if (start > this.left.length) {99      return this.right.slice(this.right.length - stop + this.left.length, this.right.length - start + this.left.length).reverse();100    }101    return this.left.slice(start).concat(this.right.slice(this.right.length - stop + this.left.length).reverse());102  }103 104  /**105   * Mimics the behavior of Array.prototype.splice() except for the change of106   * interface necessary to avoid segfaults when patching in very large arrays.107   *108   * This operation moves cursor is moved to `start` and results in the cursor109   * placed after any inserted items.110   *111   * @param {number} start112   *   Start;113   *   zero-based index at which to start changing the array;114   *   negative numbers count backwards from the end of the array and values115   *   that are out-of bounds are clamped to the appropriate end of the array.116   * @param {number | null | undefined} [deleteCount=0]117   *   Delete count (default: `0`);118   *   maximum number of elements to delete, starting from start.119   * @param {Array<T> | null | undefined} [items=[]]120   *   Items to include in place of the deleted items (default: `[]`).121   * @return {Array<T>}122   *   Any removed items.123   */124  splice(start, deleteCount, items) {125    /** @type {number} */126    const count = deleteCount || 0;127    this.setCursor(Math.trunc(start));128    const removed = this.right.splice(this.right.length - count, Number.POSITIVE_INFINITY);129    if (items) chunkedPush(this.left, items);130    return removed.reverse();131  }132 133  /**134   * Remove and return the highest-numbered item in the array, so135   * `list[list.length - 1]`;136   * Moves the cursor to `length`.137   *138   * @returns {T | undefined}139   *   Item, optional.140   */141  pop() {142    this.setCursor(Number.POSITIVE_INFINITY);143    return this.left.pop();144  }145 146  /**147   * Inserts a single item to the high-numbered side of the array;148   * moves the cursor to `length`.149   *150   * @param {T} item151   *   Item.152   * @returns {undefined}153   *   Nothing.154   */155  push(item) {156    this.setCursor(Number.POSITIVE_INFINITY);157    this.left.push(item);158  }159 160  /**161   * Inserts many items to the high-numbered side of the array.162   * Moves the cursor to `length`.163   *164   * @param {Array<T>} items165   *   Items.166   * @returns {undefined}167   *   Nothing.168   */169  pushMany(items) {170    this.setCursor(Number.POSITIVE_INFINITY);171    chunkedPush(this.left, items);172  }173 174  /**175   * Inserts a single item to the low-numbered side of the array;176   * Moves the cursor to `0`.177   *178   * @param {T} item179   *   Item.180   * @returns {undefined}181   *   Nothing.182   */183  unshift(item) {184    this.setCursor(0);185    this.right.push(item);186  }187 188  /**189   * Inserts many items to the low-numbered side of the array;190   * moves the cursor to `0`.191   *192   * @param {Array<T>} items193   *   Items.194   * @returns {undefined}195   *   Nothing.196   */197  unshiftMany(items) {198    this.setCursor(0);199    chunkedPush(this.right, items.reverse());200  }201 202  /**203   * Move the cursor to a specific position in the array. Requires204   * time proportional to the distance moved.205   *206   * If `n < 0`, the cursor will end up at the beginning.207   * If `n > length`, the cursor will end up at the end.208   *209   * @param {number} n210   *   Position.211   * @return {undefined}212   *   Nothing.213   */214  setCursor(n) {215    if (n === this.left.length || n > this.left.length && this.right.length === 0 || n < 0 && this.left.length === 0) return;216    if (n < this.left.length) {217      // Move cursor to the this.left218      const removed = this.left.splice(n, Number.POSITIVE_INFINITY);219      chunkedPush(this.right, removed.reverse());220    } else {221      // Move cursor to the this.right222      const removed = this.right.splice(this.left.length + this.right.length - n, Number.POSITIVE_INFINITY);223      chunkedPush(this.left, removed.reverse());224    }225  }226}227 228/**229 * Avoid stack overflow by pushing items onto the stack in segments230 *231 * @template T232 *   Item type.233 * @param {Array<T>} list234 *   List to inject into.235 * @param {ReadonlyArray<T>} right236 *   Items to inject.237 * @return {undefined}238 *   Nothing.239 */240function chunkedPush(list, right) {241  /** @type {number} */242  let chunkStart = 0;243  if (right.length < 10000) {244    list.push(...right);245  } else {246    while (chunkStart < right.length) {247      list.push(...right.slice(chunkStart, chunkStart + 10000));248      chunkStart += 10000;249    }250  }251}