123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410
'use strict';
// --------------------------------------------------------------------// Imports// --------------------------------------------------------------------
const Trace = require('./Trace');const common = require('./common');const errors = require('./errors');const nodes = require('./nodes');const pexprs = require('./pexprs-main');
const {TerminalNode} = nodes;const {NonterminalNode} = nodes;const {IterationNode} = nodes;
// --------------------------------------------------------------------// Operations// --------------------------------------------------------------------
/*  Evaluate the expression and return `true` if it succeeds, `false` otherwise. This method should  only be called directly by `State.prototype.eval(expr)`, which also updates the data structures  that are used for tracing. (Making those updates in a method of `State` enables the trace-specific  data structures to be "secrets" of that class, which is good for modularity.)
  The contract of this method is as follows:  * When the return value is `true`,    - the state object will have `expr.getArity()` more bindings than it did before the call.  * When the return value is `false`,    - the state object may have more bindings than it did before the call, and    - its input stream's position may be anywhere.
  Note that `State.prototype.eval(expr)`, unlike this method, guarantees that neither the state  object's bindings nor its input stream's position will change if the expression fails to match.*/pexprs.PExpr.prototype.eval = common.abstract('eval'); // function(state) { ... }
pexprs.any.eval = function(state) {  const {inputStream} = state;  const origPos = inputStream.pos;  const ch = inputStream.next();  if (ch) {    state.pushBinding(new TerminalNode(ch.length), origPos);    return true;  } else {    state.processFailure(origPos, this);    return false;  }};
pexprs.end.eval = function(state) {  const {inputStream} = state;  const origPos = inputStream.pos;  if (inputStream.atEnd()) {    state.pushBinding(new TerminalNode(0), origPos);    return true;  } else {    state.processFailure(origPos, this);    return false;  }};
pexprs.Terminal.prototype.eval = function(state) {  const {inputStream} = state;  const origPos = inputStream.pos;  if (!inputStream.matchString(this.obj)) {    state.processFailure(origPos, this);    return false;  } else {    state.pushBinding(new TerminalNode(this.obj.length), origPos);    return true;  }};
pexprs.Range.prototype.eval = function(state) {  const {inputStream} = state;  const origPos = inputStream.pos;
  // A range can operate in one of two modes: matching a single, 16-bit _code unit_,  // or matching a _code point_. (Code points over 0xFFFF take up two 16-bit code units.)  const cp = this.matchCodePoint ? inputStream.nextCodePoint() : inputStream.nextCharCode();
  // Always compare by code point value to get the correct result in all scenarios.  // Note that for strings of length 1, codePointAt(0) and charPointAt(0) are equivalent.  if (cp !== undefined && this.from.codePointAt(0) <= cp && cp <= this.to.codePointAt(0)) {    state.pushBinding(new TerminalNode(String.fromCodePoint(cp).length), origPos);    return true;  } else {    state.processFailure(origPos, this);    return false;  }};
pexprs.Param.prototype.eval = function(state) {  return state.eval(state.currentApplication().args[this.index]);};
pexprs.Lex.prototype.eval = function(state) {  state.enterLexifiedContext();  const ans = state.eval(this.expr);  state.exitLexifiedContext();  return ans;};
pexprs.Alt.prototype.eval = function(state) {  for (let idx = 0; idx < this.terms.length; idx++) {    if (state.eval(this.terms[idx])) {      return true;    }  }  return false;};
pexprs.Seq.prototype.eval = function(state) {  for (let idx = 0; idx < this.factors.length; idx++) {    const factor = this.factors[idx];    if (!state.eval(factor)) {      return false;    }  }  return true;};
pexprs.Iter.prototype.eval = function(state) {  const {inputStream} = state;  const origPos = inputStream.pos;  const arity = this.getArity();  const cols = [];  const colOffsets = [];  while (cols.length < arity) {    cols.push([]);    colOffsets.push([]);  }
  let numMatches = 0;  let prevPos = origPos;  let idx;  while (numMatches < this.maxNumMatches && state.eval(this.expr)) {    if (inputStream.pos === prevPos) {      throw errors.kleeneExprHasNullableOperand(this, state._applicationStack);    }    prevPos = inputStream.pos;    numMatches++;    const row = state._bindings.splice(state._bindings.length - arity, arity);    const rowOffsets = state._bindingOffsets.splice(        state._bindingOffsets.length - arity,        arity    );    for (idx = 0; idx < row.length; idx++) {      cols[idx].push(row[idx]);      colOffsets[idx].push(rowOffsets[idx]);    }  }  if (numMatches < this.minNumMatches) {    return false;  }  let offset = state.posToOffset(origPos);  let matchLength = 0;  if (numMatches > 0) {    const lastCol = cols[arity - 1];    const lastColOffsets = colOffsets[arity - 1];
    const endOffset =      lastColOffsets[lastColOffsets.length - 1] + lastCol[lastCol.length - 1].matchLength;    offset = colOffsets[0][0];    matchLength = endOffset - offset;  }  const isOptional = this instanceof pexprs.Opt;  for (idx = 0; idx < cols.length; idx++) {    state._bindings.push(        new IterationNode(cols[idx], colOffsets[idx], matchLength, isOptional)    );    state._bindingOffsets.push(offset);  }  return true;};
pexprs.Not.prototype.eval = function(state) {  /*    TODO:    - Right now we're just throwing away all of the failures that happen inside a `not`, and      recording `this` as a failed expression.    - Double negation should be equivalent to lookahead, but that's not the case right now wrt      failures. E.g., ~~'foo' produces a failure for ~~'foo', but maybe it should produce      a failure for 'foo' instead.  */
  const {inputStream} = state;  const origPos = inputStream.pos;  state.pushFailuresInfo();
  const ans = state.eval(this.expr);
  state.popFailuresInfo();  if (ans) {    state.processFailure(origPos, this);    return false;  }
  inputStream.pos = origPos;  return true;};
pexprs.Lookahead.prototype.eval = function(state) {  const {inputStream} = state;  const origPos = inputStream.pos;  if (state.eval(this.expr)) {    inputStream.pos = origPos;    return true;  } else {    return false;  }};
pexprs.Apply.prototype.eval = function(state) {  const caller = state.currentApplication();  const actuals = caller ? caller.args : [];  const app = this.substituteParams(actuals);
  const posInfo = state.getCurrentPosInfo();  if (posInfo.isActive(app)) {    // This rule is already active at this position, i.e., it is left-recursive.    return app.handleCycle(state);  }
  const memoKey = app.toMemoKey();  const memoRec = posInfo.memo[memoKey];
  if (memoRec && posInfo.shouldUseMemoizedResult(memoRec)) {    if (state.hasNecessaryInfo(memoRec)) {      return state.useMemoizedResult(state.inputStream.pos, memoRec);    }    delete posInfo.memo[memoKey];  }  return app.reallyEval(state);};
pexprs.Apply.prototype.handleCycle = function(state) {  const posInfo = state.getCurrentPosInfo();  const {currentLeftRecursion} = posInfo;  const memoKey = this.toMemoKey();  let memoRec = posInfo.memo[memoKey];
  if (currentLeftRecursion && currentLeftRecursion.headApplication.toMemoKey() === memoKey) {    // We already know about this left recursion, but it's possible there are "involved    // applications" that we don't already know about, so...    memoRec.updateInvolvedApplicationMemoKeys();  } else if (!memoRec) {    // New left recursion detected! Memoize a failure to try to get a seed parse.    memoRec = posInfo.memoize(memoKey, {      matchLength: 0,      examinedLength: 0,      value: false,      rightmostFailureOffset: -1,    });    posInfo.startLeftRecursion(this, memoRec);  }  return state.useMemoizedResult(state.inputStream.pos, memoRec);};
pexprs.Apply.prototype.reallyEval = function(state) {  const {inputStream} = state;  const origPos = inputStream.pos;  const origPosInfo = state.getCurrentPosInfo();  const ruleInfo = state.grammar.rules[this.ruleName];  const {body} = ruleInfo;  const {description} = ruleInfo;
  state.enterApplication(origPosInfo, this);
  if (description) {    state.pushFailuresInfo();  }
  // Reset the input stream's examinedLength property so that we can track  // the examined length of this particular application.  const origInputStreamExaminedLength = inputStream.examinedLength;  inputStream.examinedLength = 0;
  let value = this.evalOnce(body, state);  const currentLR = origPosInfo.currentLeftRecursion;  const memoKey = this.toMemoKey();  const isHeadOfLeftRecursion = currentLR && currentLR.headApplication.toMemoKey() === memoKey;  let memoRec;
  if (isHeadOfLeftRecursion) {    value = this.growSeedResult(body, state, origPos, currentLR, value);    origPosInfo.endLeftRecursion();    memoRec = currentLR;    memoRec.examinedLength = inputStream.examinedLength - origPos;    memoRec.rightmostFailureOffset = state._getRightmostFailureOffset();    origPosInfo.memoize(memoKey, memoRec); // updates origPosInfo's maxExaminedLength  } else if (!currentLR || !currentLR.isInvolved(memoKey)) {    // This application is not involved in left recursion, so it's ok to memoize it.    memoRec = origPosInfo.memoize(memoKey, {      matchLength: inputStream.pos - origPos,      examinedLength: inputStream.examinedLength - origPos,      value,      failuresAtRightmostPosition: state.cloneRecordedFailures(),      rightmostFailureOffset: state._getRightmostFailureOffset(),    });  }  const succeeded = !!value;
  if (description) {    state.popFailuresInfo();    if (!succeeded) {      state.processFailure(origPos, this);    }    if (memoRec) {      memoRec.failuresAtRightmostPosition = state.cloneRecordedFailures();    }  }
  // Record trace information in the memo table, so that it is available if the memoized result  // is used later.  if (state.isTracing() && memoRec) {    const entry = state.getTraceEntry(origPos, this, succeeded, succeeded ? [value] : []);    if (isHeadOfLeftRecursion) {      common.assert(entry.terminatingLREntry != null || !succeeded);      entry.isHeadOfLeftRecursion = true;    }    memoRec.traceEntry = entry;  }
  // Fix the input stream's examinedLength -- it should be the maximum examined length  // across all applications, not just this one.  inputStream.examinedLength = Math.max(      inputStream.examinedLength,      origInputStreamExaminedLength  );
  state.exitApplication(origPosInfo, value);
  return succeeded;};
pexprs.Apply.prototype.evalOnce = function(expr, state) {  const {inputStream} = state;  const origPos = inputStream.pos;
  if (state.eval(expr)) {    const arity = expr.getArity();    const bindings = state._bindings.splice(state._bindings.length - arity, arity);    const offsets = state._bindingOffsets.splice(state._bindingOffsets.length - arity, arity);    const matchLength = inputStream.pos - origPos;    return new NonterminalNode(this.ruleName, bindings, offsets, matchLength);  } else {    return false;  }};
pexprs.Apply.prototype.growSeedResult = function(body, state, origPos, lrMemoRec, newValue) {  if (!newValue) {    return false;  }
  const {inputStream} = state;
  while (true) {    lrMemoRec.matchLength = inputStream.pos - origPos;    lrMemoRec.value = newValue;    lrMemoRec.failuresAtRightmostPosition = state.cloneRecordedFailures();
    if (state.isTracing()) {      // Before evaluating the body again, add a trace node for this application to the memo entry.      // Its only child is a copy of the trace node from `newValue`, which will always be the last      // element in `state.trace`.      const seedTrace = state.trace[state.trace.length - 1];      lrMemoRec.traceEntry = new Trace(          state.input,          origPos,          inputStream.pos,          this,          true,          [newValue],          [seedTrace.clone()]      );    }    inputStream.pos = origPos;    newValue = this.evalOnce(body, state);    if (inputStream.pos - origPos <= lrMemoRec.matchLength) {      break;    }    if (state.isTracing()) {      state.trace.splice(-2, 1); // Drop the trace for the old seed.    }  }  if (state.isTracing()) {    // The last entry is for an unused result -- pop it and save it in the "real" entry.    lrMemoRec.traceEntry.recordLRTermination(state.trace.pop(), newValue);  }  inputStream.pos = origPos + lrMemoRec.matchLength;  return lrMemoRec.value;};
pexprs.UnicodeChar.prototype.eval = function(state) {  const {inputStream} = state;  const origPos = inputStream.pos;  const ch = inputStream.next();  if (ch && this.pattern.test(ch)) {    state.pushBinding(new TerminalNode(ch.length), origPos);    return true;  } else {    state.processFailure(origPos, this);    return false;  }};