Brunobkr/llama.cpp_AlgMor24_github

1/**2 * @import {3 *   Chunk,4 *   Code,5 *   ConstructRecord,6 *   Construct,7 *   Effects,8 *   InitialConstruct,9 *   ParseContext,10 *   Point,11 *   State,12 *   TokenizeContext,13 *   Token14 * } from 'micromark-util-types'15 */16 17/**18 * @callback Restore19 *   Restore the state.20 * @returns {undefined}21 *   Nothing.22 *23 * @typedef Info24 *   Info.25 * @property {Restore} restore26 *   Restore.27 * @property {number} from28 *   From.29 *30 * @callback ReturnHandle31 *   Handle a successful run.32 * @param {Construct} construct33 *   Construct.34 * @param {Info} info35 *   Info.36 * @returns {undefined}37 *   Nothing.38 */39 40import createDebug from 'debug'41import {ok as assert} from 'devlop'42import {markdownLineEnding} from 'micromark-util-character'43import {push, splice} from 'micromark-util-chunked'44import {resolveAll} from 'micromark-util-resolve-all'45import {codes, values} from 'micromark-util-symbol'46 47const debug = createDebug('micromark')48 49/**50 * Create a tokenizer.51 * Tokenizers deal with one type of data (e.g., containers, flow, text).52 * The parser is the object dealing with it all.53 * `initialize` works like other constructs, except that only its `tokenize`54 * function is used, in which case it doesn’t receive an `ok` or `nok`.55 * `from` can be given to set the point before the first character, although56 * when further lines are indented, they must be set with `defineSkip`.57 *58 * @param {ParseContext} parser59 *   Parser.60 * @param {InitialConstruct} initialize61 *   Construct.62 * @param {Omit<Point, '_bufferIndex' | '_index'> | undefined} [from]63 *   Point (optional).64 * @returns {TokenizeContext}65 *   Context.66 */67export function createTokenizer(parser, initialize, from) {68  /** @type {Point} */69  let point = {70    _bufferIndex: -1,71    _index: 0,72    line: (from && from.line) || 1,73    column: (from && from.column) || 1,74    offset: (from && from.offset) || 075  }76  /** @type {Record<string, number>} */77  const columnStart = {}78  /** @type {Array<Construct>} */79  const resolveAllConstructs = []80  /** @type {Array<Chunk>} */81  let chunks = []82  /** @type {Array<Token>} */83  let stack = []84  /** @type {boolean | undefined} */85  let consumed = true86 87  /**88   * Tools used for tokenizing.89   *90   * @type {Effects}91   */92  const effects = {93    attempt: constructFactory(onsuccessfulconstruct),94    check: constructFactory(onsuccessfulcheck),95    consume,96    enter,97    exit,98    interrupt: constructFactory(onsuccessfulcheck, {interrupt: true})99  }100 101  /**102   * State and tools for resolving and serializing.103   *104   * @type {TokenizeContext}105   */106  const context = {107    code: codes.eof,108    containerState: {},109    defineSkip,110    events: [],111    now,112    parser,113    previous: codes.eof,114    sliceSerialize,115    sliceStream,116    write117  }118 119  /**120   * The state function.121   *122   * @type {State | undefined}123   */124  let state = initialize.tokenize.call(context, effects)125 126  /**127   * Track which character we expect to be consumed, to catch bugs.128   *129   * @type {Code}130   */131  let expectedCode132 133  if (initialize.resolveAll) {134    resolveAllConstructs.push(initialize)135  }136 137  return context138 139  /** @type {TokenizeContext['write']} */140  function write(slice) {141    chunks = push(chunks, slice)142 143    main()144 145    // Exit if we’re not done, resolve might change stuff.146    if (chunks[chunks.length - 1] !== codes.eof) {147      return []148    }149 150    addResult(initialize, 0)151 152    // Otherwise, resolve, and exit.153    context.events = resolveAll(resolveAllConstructs, context.events, context)154 155    return context.events156  }157 158  //159  // Tools.160  //161 162  /** @type {TokenizeContext['sliceSerialize']} */163  function sliceSerialize(token, expandTabs) {164    return serializeChunks(sliceStream(token), expandTabs)165  }166 167  /** @type {TokenizeContext['sliceStream']} */168  function sliceStream(token) {169    return sliceChunks(chunks, token)170  }171 172  /** @type {TokenizeContext['now']} */173  function now() {174    // This is a hot path, so we clone manually instead of `Object.assign({}, point)`175    const {_bufferIndex, _index, line, column, offset} = point176    return {_bufferIndex, _index, line, column, offset}177  }178 179  /** @type {TokenizeContext['defineSkip']} */180  function defineSkip(value) {181    columnStart[value.line] = value.column182    accountForPotentialSkip()183    debug('position: define skip: `%j`', point)184  }185 186  //187  // State management.188  //189 190  /**191   * Main loop (note that `_index` and `_bufferIndex` in `point` are modified by192   * `consume`).193   * Here is where we walk through the chunks, which either include strings of194   * several characters, or numerical character codes.195   * The reason to do this in a loop instead of a call is so the stack can196   * drain.197   *198   * @returns {undefined}199   *   Nothing.200   */201  function main() {202    /** @type {number} */203    let chunkIndex204 205    while (point._index < chunks.length) {206      const chunk = chunks[point._index]207 208      // If we’re in a buffer chunk, loop through it.209      if (typeof chunk === 'string') {210        chunkIndex = point._index211 212        if (point._bufferIndex < 0) {213          point._bufferIndex = 0214        }215 216        while (217          point._index === chunkIndex &&218          point._bufferIndex < chunk.length219        ) {220          go(chunk.charCodeAt(point._bufferIndex))221        }222      } else {223        go(chunk)224      }225    }226  }227 228  /**229   * Deal with one code.230   *231   * @param {Code} code232   *   Code.233   * @returns {undefined}234   *   Nothing.235   */236  function go(code) {237    assert(consumed === true, 'expected character to be consumed')238    consumed = undefined239    debug('main: passing `%s` to %s', code, state && state.name)240    expectedCode = code241    assert(typeof state === 'function', 'expected state')242    state = state(code)243  }244 245  /** @type {Effects['consume']} */246  function consume(code) {247    assert(code === expectedCode, 'expected given code to equal expected code')248 249    debug('consume: `%s`', code)250 251    assert(252      consumed === undefined,253      'expected code to not have been consumed: this might be because `return x(code)` instead of `return x` was used'254    )255    assert(256      code === null257        ? context.events.length === 0 ||258            context.events[context.events.length - 1][0] === 'exit'259        : context.events[context.events.length - 1][0] === 'enter',260      'expected last token to be open'261    )262 263    if (markdownLineEnding(code)) {264      point.line++265      point.column = 1266      point.offset += code === codes.carriageReturnLineFeed ? 2 : 1267      accountForPotentialSkip()268      debug('position: after eol: `%j`', point)269    } else if (code !== codes.virtualSpace) {270      point.column++271      point.offset++272    }273 274    // Not in a string chunk.275    if (point._bufferIndex < 0) {276      point._index++277    } else {278      point._bufferIndex++279 280      // At end of string chunk.281      if (282        point._bufferIndex ===283        // Points w/ non-negative `_bufferIndex` reference284        // strings.285        /** @type {string} */ (chunks[point._index]).length286      ) {287        point._bufferIndex = -1288        point._index++289      }290    }291 292    // Expose the previous character.293    context.previous = code294 295    // Mark as consumed.296    consumed = true297  }298 299  /** @type {Effects['enter']} */300  function enter(type, fields) {301    /** @type {Token} */302    // @ts-expect-error Patch instead of assign required fields to help GC.303    const token = fields || {}304    token.type = type305    token.start = now()306 307    assert(typeof type === 'string', 'expected string type')308    assert(type.length > 0, 'expected non-empty string')309    debug('enter: `%s`', type)310 311    context.events.push(['enter', token, context])312 313    stack.push(token)314 315    return token316  }317 318  /** @type {Effects['exit']} */319  function exit(type) {320    assert(typeof type === 'string', 'expected string type')321    assert(type.length > 0, 'expected non-empty string')322 323    const token = stack.pop()324    assert(token, 'cannot close w/o open tokens')325    token.end = now()326 327    assert(type === token.type, 'expected exit token to match current token')328 329    assert(330      !(331        token.start._index === token.end._index &&332        token.start._bufferIndex === token.end._bufferIndex333      ),334      'expected non-empty token (`' + type + '`)'335    )336 337    debug('exit: `%s`', token.type)338    context.events.push(['exit', token, context])339 340    return token341  }342 343  /**344   * Use results.345   *346   * @type {ReturnHandle}347   */348  function onsuccessfulconstruct(construct, info) {349    addResult(construct, info.from)350  }351 352  /**353   * Discard results.354   *355   * @type {ReturnHandle}356   */357  function onsuccessfulcheck(_, info) {358    info.restore()359  }360 361  /**362   * Factory to attempt/check/interrupt.363   *364   * @param {ReturnHandle} onreturn365   *   Callback.366   * @param {{interrupt?: boolean | undefined} | undefined} [fields]367   *   Fields.368   */369  function constructFactory(onreturn, fields) {370    return hook371 372    /**373     * Handle either an object mapping codes to constructs, a list of374     * constructs, or a single construct.375     *376     * @param {Array<Construct> | ConstructRecord | Construct} constructs377     *   Constructs.378     * @param {State} returnState379     *   State.380     * @param {State | undefined} [bogusState]381     *   State.382     * @returns {State}383     *   State.384     */385    function hook(constructs, returnState, bogusState) {386      /** @type {ReadonlyArray<Construct>} */387      let listOfConstructs388      /** @type {number} */389      let constructIndex390      /** @type {Construct} */391      let currentConstruct392      /** @type {Info} */393      let info394 395      return Array.isArray(constructs)396        ? /* c8 ignore next 1 */397          handleListOfConstructs(constructs)398        : 'tokenize' in constructs399          ? // Looks like a construct.400            handleListOfConstructs([/** @type {Construct} */ (constructs)])401          : handleMapOfConstructs(constructs)402 403      /**404       * Handle a list of construct.405       *406       * @param {ConstructRecord} map407       *   Constructs.408       * @returns {State}409       *   State.410       */411      function handleMapOfConstructs(map) {412        return start413 414        /** @type {State} */415        function start(code) {416          const left = code !== null && map[code]417          const all = code !== null && map.null418          const list = [419            // To do: add more extension tests.420            /* c8 ignore next 2 */421            ...(Array.isArray(left) ? left : left ? [left] : []),422            ...(Array.isArray(all) ? all : all ? [all] : [])423          ]424 425          return handleListOfConstructs(list)(code)426        }427      }428 429      /**430       * Handle a list of construct.431       *432       * @param {ReadonlyArray<Construct>} list433       *   Constructs.434       * @returns {State}435       *   State.436       */437      function handleListOfConstructs(list) {438        listOfConstructs = list439        constructIndex = 0440 441        if (list.length === 0) {442          assert(bogusState, 'expected `bogusState` to be given')443          return bogusState444        }445 446        return handleConstruct(list[constructIndex])447      }448 449      /**450       * Handle a single construct.451       *452       * @param {Construct} construct453       *   Construct.454       * @returns {State}455       *   State.456       */457      function handleConstruct(construct) {458        return start459 460        /** @type {State} */461        function start(code) {462          // To do: not needed to store if there is no bogus state, probably?463          // Currently doesn’t work because `inspect` in document does a check464          // w/o a bogus, which doesn’t make sense. But it does seem to help perf465          // by not storing.466          info = store()467          currentConstruct = construct468 469          if (!construct.partial) {470            context.currentConstruct = construct471          }472 473          // Always populated by defaults.474          assert(475            context.parser.constructs.disable.null,476            'expected `disable.null` to be populated'477          )478 479          if (480            construct.name &&481            context.parser.constructs.disable.null.includes(construct.name)482          ) {483            return nok(code)484          }485 486          return construct.tokenize.call(487            // If we do have fields, create an object w/ `context` as its488            // prototype.489            // This allows a “live binding”, which is needed for `interrupt`.490            fields ? Object.assign(Object.create(context), fields) : context,491            effects,492            ok,493            nok494          )(code)495        }496      }497 498      /** @type {State} */499      function ok(code) {500        assert(code === expectedCode, 'expected code')501        consumed = true502        onreturn(currentConstruct, info)503        return returnState504      }505 506      /** @type {State} */507      function nok(code) {508        assert(code === expectedCode, 'expected code')509        consumed = true510        info.restore()511 512        if (++constructIndex < listOfConstructs.length) {513          return handleConstruct(listOfConstructs[constructIndex])514        }515 516        return bogusState517      }518    }519  }520 521  /**522   * @param {Construct} construct523   *   Construct.524   * @param {number} from525   *   From.526   * @returns {undefined}527   *   Nothing.528   */529  function addResult(construct, from) {530    if (construct.resolveAll && !resolveAllConstructs.includes(construct)) {531      resolveAllConstructs.push(construct)532    }533 534    if (construct.resolve) {535      splice(536        context.events,537        from,538        context.events.length - from,539        construct.resolve(context.events.slice(from), context)540      )541    }542 543    if (construct.resolveTo) {544      context.events = construct.resolveTo(context.events, context)545    }546 547    assert(548      construct.partial ||549        context.events.length === 0 ||550        context.events[context.events.length - 1][0] === 'exit',551      'expected last token to end'552    )553  }554 555  /**556   * Store state.557   *558   * @returns {Info}559   *   Info.560   */561  function store() {562    const startPoint = now()563    const startPrevious = context.previous564    const startCurrentConstruct = context.currentConstruct565    const startEventsIndex = context.events.length566    const startStack = Array.from(stack)567 568    return {from: startEventsIndex, restore}569 570    /**571     * Restore state.572     *573     * @returns {undefined}574     *   Nothing.575     */576    function restore() {577      point = startPoint578      context.previous = startPrevious579      context.currentConstruct = startCurrentConstruct580      context.events.length = startEventsIndex581      stack = startStack582      accountForPotentialSkip()583      debug('position: restore: `%j`', point)584    }585  }586 587  /**588   * Move the current point a bit forward in the line when it’s on a column589   * skip.590   *591   * @returns {undefined}592   *   Nothing.593   */594  function accountForPotentialSkip() {595    if (point.line in columnStart && point.column < 2) {596      point.column = columnStart[point.line]597      point.offset += columnStart[point.line] - 1598    }599  }600}601 602/**603 * Get the chunks from a slice of chunks in the range of a token.604 *605 * @param {ReadonlyArray<Chunk>} chunks606 *   Chunks.607 * @param {Pick<Token, 'end' | 'start'>} token608 *   Token.609 * @returns {Array<Chunk>}610 *   Chunks.611 */612function sliceChunks(chunks, token) {613  const startIndex = token.start._index614  const startBufferIndex = token.start._bufferIndex615  const endIndex = token.end._index616  const endBufferIndex = token.end._bufferIndex617  /** @type {Array<Chunk>} */618  let view619 620  if (startIndex === endIndex) {621    assert(endBufferIndex > -1, 'expected non-negative end buffer index')622    assert(startBufferIndex > -1, 'expected non-negative start buffer index')623    // @ts-expect-error `_bufferIndex` is used on string chunks.624    view = [chunks[startIndex].slice(startBufferIndex, endBufferIndex)]625  } else {626    view = chunks.slice(startIndex, endIndex)627 628    if (startBufferIndex > -1) {629      const head = view[0]630      if (typeof head === 'string') {631        view[0] = head.slice(startBufferIndex)632        /* c8 ignore next 4 -- used to be used, no longer */633      } else {634        assert(startBufferIndex === 0, 'expected `startBufferIndex` to be `0`')635        view.shift()636      }637    }638 639    if (endBufferIndex > 0) {640      // @ts-expect-error `_bufferIndex` is used on string chunks.641      view.push(chunks[endIndex].slice(0, endBufferIndex))642    }643  }644 645  return view646}647 648/**649 * Get the string value of a slice of chunks.650 *651 * @param {ReadonlyArray<Chunk>} chunks652 *   Chunks.653 * @param {boolean | undefined} [expandTabs=false]654 *   Whether to expand tabs (default: `false`).655 * @returns {string}656 *   Result.657 */658function serializeChunks(chunks, expandTabs) {659  let index = -1660  /** @type {Array<string>} */661  const result = []662  /** @type {boolean | undefined} */663  let atTab664 665  while (++index < chunks.length) {666    const chunk = chunks[index]667    /** @type {string} */668    let value669 670    if (typeof chunk === 'string') {671      value = chunk672    } else673      switch (chunk) {674        case codes.carriageReturn: {675          value = values.cr676 677          break678        }679 680        case codes.lineFeed: {681          value = values.lf682 683          break684        }685 686        case codes.carriageReturnLineFeed: {687          value = values.cr + values.lf688 689          break690        }691 692        case codes.horizontalTab: {693          value = expandTabs ? values.space : values.ht694 695          break696        }697 698        case codes.virtualSpace: {699          if (!expandTabs && atTab) continue700          value = values.space701 702          break703        }704 705        default: {706          assert(typeof chunk === 'number', 'expected number')707          // Currently only replacement character.708          value = String.fromCharCode(chunk)709        }710      }711 712    atTab = chunk === codes.horizontalTab713    result.push(value)714  }715 716  return result.join('')717}718