AK-21/Graphite-Industrial-Intelligence

1import {constants} from 'micromark-util-symbol'2 3/**4 * Some of the internal operations of micromark do lots of editing5 * operations on very large arrays. This runs into problems with two6 * properties of most circa-2020 JavaScript interpreters:7 *8 *  - Array-length modifications at the high end of an array (push/pop) are9 *    expected to be common and are implemented in (amortized) time10 *    proportional to the number of elements added or removed, whereas11 *    other operations (shift/unshift and splice) are much less efficient.12 *  - Function arguments are passed on the stack, so adding tens of thousands13 *    of elements to an array with `arr.push(...newElements)` will frequently14 *    cause stack overflows. (see <https://stackoverflow.com/questions/22123769/rangeerror-maximum-call-stack-size-exceeded-why>)15 *16 * SpliceBuffers are an implementation of gap buffers, which are a17 * generalization of the "queue made of two stacks" idea. The splice buffer18 * maintains a cursor, and moving the cursor has cost proportional to the19 * distance the cursor moves, but inserting, deleting, or splicing in20 * new information at the cursor is as efficient as the push/pop operation.21 * This allows for an efficient sequence of splices (or pushes, pops, shifts,22 * or unshifts) as long such edits happen at the same part of the array or23 * generally sweep through the array from the beginning to the end.24 *25 * The interface for splice buffers also supports large numbers of inputs by26 * passing a single array argument rather passing multiple arguments on the27 * function call stack.28 *29 * @template T30 *   Item type.31 */32export class SpliceBuffer {33  /**34   * @param {ReadonlyArray<T> | null | undefined} [initial]35   *   Initial items (optional).36   * @returns37   *   Splice buffer.38   */39  constructor(initial) {40    /** @type {Array<T>} */41    this.left = initial ? [...initial] : []42    /** @type {Array<T>} */43    this.right = []44  }45 46  /**47   * Array access;48   * does not move the cursor.49   *50   * @param {number} index51   *   Index.52   * @return {T}53   *   Item.54   */55  get(index) {56    if (index < 0 || index >= this.left.length + this.right.length) {57      throw new RangeError(58        'Cannot access index `' +59          index +60          '` in a splice buffer of size `' +61          (this.left.length + this.right.length) +62          '`'63      )64    }65 66    if (index < this.left.length) return this.left[index]67    return this.right[this.right.length - index + this.left.length - 1]68  }69 70  /**71   * The length of the splice buffer, one greater than the largest index in the72   * array.73   */74  get length() {75    return this.left.length + this.right.length76  }77 78  /**79   * Remove and return `list[0]`;80   * moves the cursor to `0`.81   *82   * @returns {T | undefined}83   *   Item, optional.84   */85  shift() {86    this.setCursor(0)87    return this.right.pop()88  }89 90  /**91   * Slice the buffer to get an array;92   * does not move the cursor.93   *94   * @param {number} start95   *   Start.96   * @param {number | null | undefined} [end]97   *   End (optional).98   * @returns {Array<T>}99   *   Array of items.100   */101  slice(start, end) {102    /** @type {number} */103    const stop =104      end === null || end === undefined ? Number.POSITIVE_INFINITY : end105 106    if (stop < this.left.length) {107      return this.left.slice(start, stop)108    }109 110    if (start > this.left.length) {111      return this.right112        .slice(113          this.right.length - stop + this.left.length,114          this.right.length - start + this.left.length115        )116        .reverse()117    }118 119    return this.left120      .slice(start)121      .concat(122        this.right.slice(this.right.length - stop + this.left.length).reverse()123      )124  }125 126  /**127   * Mimics the behavior of Array.prototype.splice() except for the change of128   * interface necessary to avoid segfaults when patching in very large arrays.129   *130   * This operation moves cursor is moved to `start` and results in the cursor131   * placed after any inserted items.132   *133   * @param {number} start134   *   Start;135   *   zero-based index at which to start changing the array;136   *   negative numbers count backwards from the end of the array and values137   *   that are out-of bounds are clamped to the appropriate end of the array.138   * @param {number | null | undefined} [deleteCount=0]139   *   Delete count (default: `0`);140   *   maximum number of elements to delete, starting from start.141   * @param {Array<T> | null | undefined} [items=[]]142   *   Items to include in place of the deleted items (default: `[]`).143   * @return {Array<T>}144   *   Any removed items.145   */146  splice(start, deleteCount, items) {147    /** @type {number} */148    const count = deleteCount || 0149 150    this.setCursor(Math.trunc(start))151    const removed = this.right.splice(152      this.right.length - count,153      Number.POSITIVE_INFINITY154    )155    if (items) chunkedPush(this.left, items)156    return removed.reverse()157  }158 159  /**160   * Remove and return the highest-numbered item in the array, so161   * `list[list.length - 1]`;162   * Moves the cursor to `length`.163   *164   * @returns {T | undefined}165   *   Item, optional.166   */167  pop() {168    this.setCursor(Number.POSITIVE_INFINITY)169    return this.left.pop()170  }171 172  /**173   * Inserts a single item to the high-numbered side of the array;174   * moves the cursor to `length`.175   *176   * @param {T} item177   *   Item.178   * @returns {undefined}179   *   Nothing.180   */181  push(item) {182    this.setCursor(Number.POSITIVE_INFINITY)183    this.left.push(item)184  }185 186  /**187   * Inserts many items to the high-numbered side of the array.188   * Moves the cursor to `length`.189   *190   * @param {Array<T>} items191   *   Items.192   * @returns {undefined}193   *   Nothing.194   */195  pushMany(items) {196    this.setCursor(Number.POSITIVE_INFINITY)197    chunkedPush(this.left, items)198  }199 200  /**201   * Inserts a single item to the low-numbered side of the array;202   * Moves the cursor to `0`.203   *204   * @param {T} item205   *   Item.206   * @returns {undefined}207   *   Nothing.208   */209  unshift(item) {210    this.setCursor(0)211    this.right.push(item)212  }213 214  /**215   * Inserts many items to the low-numbered side of the array;216   * moves the cursor to `0`.217   *218   * @param {Array<T>} items219   *   Items.220   * @returns {undefined}221   *   Nothing.222   */223  unshiftMany(items) {224    this.setCursor(0)225    chunkedPush(this.right, items.reverse())226  }227 228  /**229   * Move the cursor to a specific position in the array. Requires230   * time proportional to the distance moved.231   *232   * If `n < 0`, the cursor will end up at the beginning.233   * If `n > length`, the cursor will end up at the end.234   *235   * @param {number} n236   *   Position.237   * @return {undefined}238   *   Nothing.239   */240  setCursor(n) {241    if (242      n === this.left.length ||243      (n > this.left.length && this.right.length === 0) ||244      (n < 0 && this.left.length === 0)245    )246      return247    if (n < this.left.length) {248      // Move cursor to the this.left249      const removed = this.left.splice(n, Number.POSITIVE_INFINITY)250      chunkedPush(this.right, removed.reverse())251    } else {252      // Move cursor to the this.right253      const removed = this.right.splice(254        this.left.length + this.right.length - n,255        Number.POSITIVE_INFINITY256      )257      chunkedPush(this.left, removed.reverse())258    }259  }260}261 262/**263 * Avoid stack overflow by pushing items onto the stack in segments264 *265 * @template T266 *   Item type.267 * @param {Array<T>} list268 *   List to inject into.269 * @param {ReadonlyArray<T>} right270 *   Items to inject.271 * @return {undefined}272 *   Nothing.273 */274function chunkedPush(list, right) {275  /** @type {number} */276  let chunkStart = 0277 278  if (right.length < constants.v8MaxSafeChunkSize) {279    list.push(...right)280  } else {281    while (chunkStart < right.length) {282      list.push(283        ...right.slice(chunkStart, chunkStart + constants.v8MaxSafeChunkSize)284      )285      chunkStart += constants.v8MaxSafeChunkSize286    }287  }288}289