Brunobkr/llama.cpp_AlgMor24_github

1// Functions to compile 1 or more visitor objects into a single compiled visitor.2//3// # Visitor objects4//5// Visitor objects which are generated by rules' `create` functions have keys being either:6// * Name of an AST type. or7// * Name of an AST type postfixed with `:exit`.8//9// Each property value must be a function that handles that AST node.10//11// e.g.:12//13// ```14// {15//   BinaryExpression(node) {16//     // Do stuff on enter17//   },18//   'BinaryExpression:exit'(node) {19//     // Do stuff on exit20//   },21// }22// ```23//24// # Compiled visitor25//26// Compiled visitor is an array with `NODE_TYPES_COUNT` length, keyed by the ID of the node type.27// `NODE_TYPE_IDS_MAP` maps from type name to ID.28//29// Each element of compiled array is one of:30// * No visitor for this type = `null`.31// * Visitor for leaf node = visit function.32// * Visitor for non-leaf node = object of form `{ enter, exit }`,33//   where each property is either a visitor function or `null`.34//35// e.g.:36//37// ```38// [39//   // Leaf nodes40//   function(node) { /* do stuff */ },41//   // ...42//43//   // Non-leaf nodes44//   {45//     enter: function(node) { /* do stuff */ },46//     exit: null,47//   },48//   // ...49// ]50// ```51//52// # Object reuse53//54// No more than 1 compiled visitor exists at any time, so we reuse a single array `compiledVisitor`,55// rather than creating a new array for each file being linted.56//57// To compile visitors, call:58// * `initCompiledVisitor` once.59// * `addVisitorToCompiled` with each visitor object.60// * `finalizeCompiledVisitor` once.61//62// After this sequence of calls, `compiledVisitor` is ready to be used to walk the AST.63//64// We also recycle:65//66// * `{ enter, exit }` objects which are stored in compiled visitor.67// * Temporary arrays used to store multiple visit functions, which are merged into a single function68//   in `finalizeCompiledVisitor`.69//70// The aim is to reduce pressure on the garbage collector. All these recycled objects are long-lived71// and will graduate to "old space", which leaves as much capacity as possible in "new space"72// for objects created by user code in visitors. If ephemeral user-created objects all fit in new space,73// it will avoid full GC runs, which should greatly improve performance.74 75import {76  LEAF_NODE_TYPES_COUNT,77  NODE_TYPE_IDS_MAP,78  NODE_TYPES_COUNT,79} from "../generated/visit/type_ids.js";80 81// Compiled visitor used for visiting each file.82// Same array is reused for each file.83//84// Initialized with `.push()` to ensure V8 treats the array as "packed" (linear array),85// not "holey" (hash map). This is critical, as looking up elements in this array is a very hot path86// during AST visitation, and holey arrays are much slower.87// https://v8.dev/blog/elements-kinds88let compiledVisitor;89 90export function createCompiledVisitor() {91  // Create a new compiled visitor array92  compiledVisitor = [];93  for (let i = NODE_TYPES_COUNT; i !== 0; i--) {94    compiledVisitor.push(null);95  }96  return compiledVisitor;97}98 99// Arrays containing type IDs of types which have multiple visit functions defined for them.100//101// Filled with `0` initially up to maximum size they could ever need to be so:102// 1. These arrays never need to grow.103// 2. V8 treats these arrays as "PACKED_SMI_ELEMENTS".104const mergedLeafVisitorTypeIds = [],105  mergedEnterVisitorTypeIds = [],106  mergedExitVisitorTypeIds = [];107 108for (let i = LEAF_NODE_TYPES_COUNT; i !== 0; i--) {109  mergedLeafVisitorTypeIds.push(0);110}111 112for (let i = NODE_TYPES_COUNT - LEAF_NODE_TYPES_COUNT; i !== 0; i--) {113  mergedEnterVisitorTypeIds.push(0);114  mergedExitVisitorTypeIds.push(0);115}116 117mergedLeafVisitorTypeIds.length = 0;118mergedEnterVisitorTypeIds.length = 0;119mergedExitVisitorTypeIds.length = 0;120 121// `true` if `addVisitor` has been called with a visitor which visits at least one AST type122let hasActiveVisitors = false;123 124// Enter+exit object cache.125//126// `compiledVisitor` may contain many `{ enter, exit }` objects.127// Use this cache to reuse those objects across all visitor compilations.128//129// `enterExitObjectCacheNextIndex` is the index of first object in cache which is currently unused.130// It may point to the end of the cache array.131const enterExitObjectCache = [];132let enterExitObjectCacheNextIndex = 0;133 134function getEnterExitObject() {135  if (enterExitObjectCacheNextIndex < enterExitObjectCache.length) {136    return enterExitObjectCache[enterExitObjectCacheNextIndex++];137  }138 139  const enterExit = { enter: null, exit: null };140  enterExitObjectCache.push(enterExit);141  enterExitObjectCacheNextIndex++;142  return enterExit;143}144 145// Visit function arrays cache.146//147// During compilation, many arrays may be used temporarily to store multiple visit functions for same AST type.148// The functions in each array are merged into a single function in `finalizeCompiledVisitor`,149// after which these arrays aren't used again.150//151// Use this cache to reuse these arrays across each visitor compilation.152//153// `visitFnArrayCacheNextIndex` is the index of first array in cache which is currently unused.154// It may point to the end of the cache array.155const visitFnArrayCache = [];156let visitFnArrayCacheNextIndex = 0;157 158function createVisitFnArray(visit1, visit2) {159  if (visitFnArrayCacheNextIndex < visitFnArrayCache.length) {160    const arr = visitFnArrayCache[visitFnArrayCacheNextIndex++];161    arr.push(visit1, visit2);162    return arr;163  }164 165  const arr = [visit1, visit2];166  visitFnArrayCache.push(arr);167  visitFnArrayCacheNextIndex++;168  return arr;169}170 171/**172 * Initialize compiled visitor, ready for calls to `addVisitor`.173 */174export function initCompiledVisitor() {175  // Reset `compiledVisitor` array after previous compilation176  for (let i = 0; i < NODE_TYPES_COUNT; i++) {177    compiledVisitor[i] = null;178  }179 180  // Reset enter+exit objects which were used in previous compilation181  for (let i = 0; i < enterExitObjectCacheNextIndex; i++) {182    const enterExit = enterExitObjectCache[i];183    enterExit.enter = null;184    enterExit.exit = null;185  }186  enterExitObjectCacheNextIndex = 0;187}188 189/**190 * Add a visitor to compiled visitor.191 *192 * @param visitor - Visitor object193 */194export function addVisitorToCompiled(visitor) {195  if (visitor === null || typeof visitor !== "object") {196    throw new TypeError("Visitor must be an object");197  }198 199  // Exit if is empty visitor200  const keys = Object.keys(visitor),201    keysLen = keys.length;202  if (keysLen === 0) return;203 204  hasActiveVisitors = true;205 206  // Populate visitors array from provided object207  for (let i = 0; i < keysLen; i++) {208    let name = keys[i];209 210    const visitFn = visitor[name];211    if (typeof visitFn !== "function") {212      throw new TypeError(`'${name}' property of visitor object is not a function`);213    }214 215    const isExit = name.endsWith(":exit");216    if (isExit) name = name.slice(0, -5);217 218    const typeId = NODE_TYPE_IDS_MAP.get(name);219    if (typeId === void 0) throw new Error(`Unknown node type '${name}' in visitor object`);220 221    const existing = compiledVisitor[typeId];222    if (typeId < LEAF_NODE_TYPES_COUNT) {223      // Leaf node - store just 1 function, not enter+exit pair224      if (existing === null) {225        compiledVisitor[typeId] = visitFn;226      } else if (Array.isArray(existing)) {227        if (isExit) {228          existing.push(visitFn);229        } else {230          // Insert before last in array in case last was enter visit function from the current rule,231          // to ensure enter is called before exit.232          // It could also be either an enter or exit visitor function for another rule, but the order233          // rules are called in doesn't matter. We only need to make sure that a rule's exit visitor234          // isn't called before enter visitor *for that same rule*.235          existing.splice(existing.length - 1, 0, visitFn);236        }237      } else {238        // Same as above, enter visitor is put to front of list to make sure enter is called before exit239        compiledVisitor[typeId] = isExit240          ? createVisitFnArray(existing, visitFn)241          : createVisitFnArray(visitFn, existing);242        mergedLeafVisitorTypeIds.push(typeId);243      }244    } else {245      // Not leaf node - store enter+exit pair246      if (existing === null) {247        const enterExit = (compiledVisitor[typeId] = getEnterExitObject());248        if (isExit) {249          enterExit.exit = visitFn;250        } else {251          enterExit.enter = visitFn;252        }253      } else if (isExit) {254        const { exit } = existing;255        if (exit === null) {256          existing.exit = visitFn;257        } else if (Array.isArray(exit)) {258          exit.push(visitFn);259        } else {260          existing.exit = createVisitFnArray(exit, visitFn);261          mergedExitVisitorTypeIds.push(typeId);262        }263      } else {264        const { enter } = existing;265        if (enter === null) {266          existing.enter = visitFn;267        } else if (Array.isArray(enter)) {268          enter.push(visitFn);269        } else {270          existing.enter = createVisitFnArray(enter, visitFn);271          mergedEnterVisitorTypeIds.push(typeId);272        }273      }274    }275  }276}277 278/**279 * Finalize compiled visitor.280 *281 * After calling this function, `compiledVisitor` is ready to be used to walk the AST.282 *283 * @returns {boolean} - `true` if compiled visitor visits at least 1 AST type284 */285export function finalizeCompiledVisitor() {286  if (hasActiveVisitors === false) return false;287 288  // Merge visit functions for node types which have multiple visitors from different rules,289  // or enter+exit functions for leaf nodes290  for (let i = mergedLeafVisitorTypeIds.length - 1; i >= 0; i--) {291    const typeId = mergedLeafVisitorTypeIds[i];292    compiledVisitor[typeId] = mergeVisitFns(compiledVisitor[typeId]);293  }294 295  for (let i = mergedEnterVisitorTypeIds.length - 1; i >= 0; i--) {296    const typeId = mergedEnterVisitorTypeIds[i];297    const enterExit = compiledVisitor[typeId];298    enterExit.enter = mergeVisitFns(enterExit.enter);299  }300 301  for (let i = mergedExitVisitorTypeIds.length - 1; i >= 0; i--) {302    const typeId = mergedExitVisitorTypeIds[i];303    const enterExit = compiledVisitor[typeId];304    enterExit.exit = mergeVisitFns(enterExit.exit);305  }306 307  // Reset state, ready for next time308  mergedLeafVisitorTypeIds.length = 0;309  mergedEnterVisitorTypeIds.length = 0;310  mergedExitVisitorTypeIds.length = 0;311 312  // Note: Visit function arrays have been emptied in `mergeVisitFns`, so all arrays in `visitFnArrayCache`313  // are now empty and ready for reuse. We just need to reset the index.314  visitFnArrayCacheNextIndex = 0;315 316  hasActiveVisitors = false;317 318  return true;319}320 321/**322 * Merge array of visit functions into a single function, which calls each of input functions in turn.323 *324 * The array passed is cleared (length set to 0), so the array can be reused.325 *326 * The merged function is statically defined and does not contain a loop, to hopefully allow327 * JS engine to heavily optimize it.328 *329 * `mergers` contains pre-defined functions to merge up to 5 visit functions.330 * Merger functions for merging more than 5 visit functions are created dynamically on demand.331 *332 * @param visitFns - Array of visit functions333 * @returns Function which calls all of `visitFns` in turn.334 */335function mergeVisitFns(visitFns) {336  const numVisitFns = visitFns.length;337 338  // Get or create merger for merging `numVisitFns` functions339  let merger;340  if (mergers.length <= numVisitFns) {341    while (mergers.length < numVisitFns) {342      mergers.push(null);343    }344    merger = createMerger(numVisitFns);345    mergers.push(merger);346  } else {347    merger = mergers[numVisitFns];348    if (merger === null) merger = mergers[numVisitFns] = createMerger(numVisitFns);349  }350 351  // Merge functions352  const mergedFn = merger(...visitFns);353 354  // Empty `visitFns` array, so it can be reused355  visitFns.length = 0;356 357  return mergedFn;358}359 360/**361 * Create a merger function that merges `fnCount` functions.362 *363 * @param fnCount - Number of functions to be merged364 * @returns Function to merge `fnCount` functions365 */366function createMerger(fnCount) {367  const args = [];368  let body = "return node=>{";369  for (let i = 1; i <= fnCount; i++) {370    args.push(`visit${i}`);371    body += `visit${i}(node);`;372  }373  body += "}";374  args.push(body);375  // oxlint-disable-next-line typescript/no-implied-eval376  return new Function(...args);377}378 379// Pre-defined mergers for merging up to 5 functions380const mergers = [381  null, // No merger for 0 functions382  null, // No merger for 1 function383  (visit1, visit2) => (node) => {384    visit1(node);385    visit2(node);386  },387  (visit1, visit2, visit3) => (node) => {388    visit1(node);389    visit2(node);390    visit3(node);391  },392  (visit1, visit2, visit3, visit4) => (node) => {393    visit1(node);394    visit2(node);395    visit3(node);396    visit4(node);397  },398  (visit1, visit2, visit3, visit4, visit5) => (node) => {399    visit1(node);400    visit2(node);401    visit3(node);402    visit4(node);403    visit5(node);404  },405];406