test-incremental.js

'use strict';

// --------------------------------------------------------------------
// Imports
// --------------------------------------------------------------------

const fs = require('fs');
const ohm = require('..');
const test = require('ava');
const testUtil = require('./helpers/testUtil');

const {makeGrammar} = testUtil;

// --------------------------------------------------------------------
// Private stuff
// --------------------------------------------------------------------

function pluckMemoProp(result, propName) {
  return result.matcher.memoTable.map(info => {
    const result = {};
    if (info == null) return {};
    if (propName === 'examinedLength') {
      result.maxExaminedLength = info.maxExaminedLength;
    } else if (propName === 'rightmostFailureOffset') {
      result.maxRightmostFailureOffset = info.maxRightmostFailureOffset;
    }
    Object.keys(info.memo).forEach(ruleName => {
      const memoRec = info.memo[ruleName];
      result[ruleName] = memoRec[propName];
    });
    return result;
  });
}

const checkOffsetActions = {
  _nonterminal(...children) {
    const desc = this._node.ctorName + ' @ ' + this.source.startIdx;
    this.args.t.is(this.source.startIdx, this.args.startIdx, desc);
    for (let i = 0; i < children.length; ++i) {
      const childStartIdx = this.args.startIdx + this._node.childOffsets[i];
      children[i].checkOffsets(this.args.t, childStartIdx);
    }
  },
  _terminal() {
    const desc = '"' + this.sourceString + '" @ ' + this.source.startIdx;
    this.args.t.is(this.source.startIdx, this.args.startIdx, desc);
  },
  _iter(...children) {
    return children.map(c => c.checkOffsets(this.args.t, this.args.childStartIdx));
  },
};

const ctorTreeActions = {
  _default(...children) {
    return [this.ctorName].concat(children.map(c => c.ctorTree));
  },
};

// --------------------------------------------------------------------
// Tests
// --------------------------------------------------------------------

test('basic incremental parsing', t => {
  const g = makeGrammar([
    'G {',
    '  start = notLastLetter* letter',
    '  notLastLetter = letter &letter',
    '}',
  ]);

  // Create an operation which reconstructs the matched based on the offsets
  // stored for each node. This can be compared to the input stored in the matcher.
  const s = g.createSemantics().addOperation('reconstructInput(input)', {
    start(letters, lastLetter) {
      const lastLetterOffset = this._node.childOffsets[1];
      return (
        letters.reconstructInput(this.args.input) +
        lastLetter.reconstructInput(this.args.input.slice(lastLetterOffset))
      );
    },
    notLastLetter(letter, _) {
      return letter.reconstructInput(this.args.input);
    },
    _iter(...children) {
      return this._node.childOffsets
          .map((offset, i) => {
            const c = children[i].reconstructInput(this.args.input.slice(offset));
            return c;
          })
          .join('');
    },
    _terminal() {
      return this.sourceString;
    },
  });

  const im = g.matcher();
  let result;

  im.replaceInputRange(0, 0, 'helloworld');
  t.is(im.getInput(), 'helloworld');
  im.replaceInputRange(3, 5, 'X');
  t.is(im.getInput(), 'helXworld');

  result = im.match();
  t.is(s(result).reconstructInput(im.getInput()), 'helXworld');

  t.truthy(im.match('start').succeeded());
  t.truthy(im.match().succeeded());
  t.is(s(result).reconstructInput(im.getInput()), 'helXworld');

  im.replaceInputRange(0, 4, '');
  t.is(im.getInput(), 'world');

  result = im.match();
  t.is(s(result).reconstructInput(im.getInput()), 'world');

  im.replaceInputRange(3, 4, ' ');
  t.is(im.getInput(), 'wor d');
  t.truthy(im.match().failed());

  im.replaceInputRange(0, 4, 'aa');
  t.is(im.getInput(), 'aad');

  result = im.match();
  t.is(s(result).reconstructInput(im.getInput()), 'aad');

  im.replaceInputRange(1, 2, '9');
  t.truthy(im.match().failed());
});

test('trickier incremental parsing', t => {
  const g = makeGrammar([
    'G {',
    '  start = start letter  -- rec',
    '        | lookahead',
    '        | "a"',
    '  lookahead = &"ac" "a"',
    '}',
  ]);
  const s = g.createSemantics().addAttribute('ctorTree', ctorTreeActions);
  const im = g.matcher();
  let result;

  im.replaceInputRange(0, 0, 'ab');
  result = im.match();
  t.truthy(result.succeeded());
  t.deepEqual(s(result).ctorTree, [
    'start',
    ['start_rec', ['start', ['_terminal']], ['letter', ['lower', ['_terminal']]]],
  ]);

  // When the input is 'ac', the lookahead rule should now succeed.
  im.replaceInputRange(1, 2, 'c');
  result = im.match();
  t.truthy(result.succeeded());
  t.deepEqual(s(result).ctorTree, [
    'start',
    [
      'start_rec',
      ['start', ['lookahead', ['_terminal'], ['_terminal']]],
      ['letter', ['lower', ['_terminal']]],
    ],
  ]);
});

test('examinedLength - no LR', t => {
  const g = makeGrammar([
    'G {',
    '  start = notLastLetter* letter',
    '  notLastLetter = letter &letter',
    '}',
  ]);
  const result = g.match('yip');
  const values = pluckMemoProp(result, 'examinedLength');
  t.deepEqual(values, [
    {maxExaminedLength: 4, letter: 1, lower: 1, notLastLetter: 2, start: 4},
    {maxExaminedLength: 2, letter: 1, lower: 1, notLastLetter: 2},
    {maxExaminedLength: 2, letter: 1, lower: 1, notLastLetter: 2},
    {maxExaminedLength: 1, letter: 1, lower: 1, upper: 1, unicodeLtmo: 1},
  ]);
});

test('examinedLength - no LR, but non-monotonic', t => {
  const g = makeGrammar(['G {', '  start = "a" "b" "c" | letter letter letter', '}']);
  const result = g.match('abd');
  const values = pluckMemoProp(result, 'examinedLength');
  t.deepEqual(values, [
    {maxExaminedLength: 3, letter: 1, lower: 1, start: 3},
    {maxExaminedLength: 1, letter: 1, lower: 1},
    {maxExaminedLength: 1, letter: 1, lower: 1},
  ]);
});

test('examinedLength - simple LR', t => {
  const g = makeGrammar(['G {', '  start = start letter  -- rec', '        | letter', '}']);
  const result = g.match('yo');
  t.is(result.succeeded(), true);

  const values = pluckMemoProp(result, 'examinedLength');
  t.deepEqual(values, [
    {maxExaminedLength: 3, letter: 1, lower: 1, start: 3},
    {maxExaminedLength: 1, letter: 1, lower: 1},
    {maxExaminedLength: 1, letter: 1, lower: 1, upper: 1, unicodeLtmo: 1},
  ]);
});

test('examinedLength - complicated LR', t => {
  const g = makeGrammar([
    'G {',
    '  start = start foo  -- rec',
    '        | foo',
    '  foo = foo letter  -- rec',
    '      | any',
    '}',
  ]);
  const result = g.match('yo');
  t.is(result.succeeded(), true);

  const values = pluckMemoProp(result, 'examinedLength');
  t.deepEqual(values, [
    {maxExaminedLength: 3, any: 1, foo: 3, start: 3},
    {maxExaminedLength: 1, letter: 1, lower: 1},
    {maxExaminedLength: 1, letter: 1, lower: 1, upper: 1, unicodeLtmo: 1, any: 1, foo: 1},
  ]);
});

test('rightmostFailureOffset - no LR', t => {
  const g = makeGrammar([
    'G {',
    '  start = notLastLetter* letter',
    '  notLastLetter = letter &letter',
    '}',
  ]);
  const result = g.match('yip');
  const values = pluckMemoProp(result, 'rightmostFailureOffset');
  t.deepEqual(values, [
    {maxRightmostFailureOffset: 3, letter: -1, lower: -1, notLastLetter: -1, start: 3},
    {maxRightmostFailureOffset: -1, letter: -1, lower: -1, notLastLetter: -1},
    {maxRightmostFailureOffset: 1, letter: -1, lower: -1, notLastLetter: 1},
    {maxRightmostFailureOffset: 0, letter: 0, lower: 0, upper: 0, unicodeLtmo: 0},
  ]);
});

test('rightmostFailureOffset - simple LR', t => {
  const g = makeGrammar(['G {', '  start = start letter  -- rec', '        | letter', '}']);
  const result = g.match('yo');
  t.is(result.succeeded(), true);

  const values = pluckMemoProp(result, 'rightmostFailureOffset');
  t.deepEqual(values, [
    {maxRightmostFailureOffset: 2, letter: -1, lower: -1, start: 2},
    {maxRightmostFailureOffset: -1, letter: -1, lower: -1},
    {maxRightmostFailureOffset: 0, letter: 0, lower: 0, upper: 0, unicodeLtmo: 0},
  ]);
});

test('rightmostFailureOffset - complicated LR', t => {
  const g = makeGrammar([
    'G {',
    '  start = start foo  -- rec',
    '        | foo',
    '  foo = foo letter  -- rec',
    '      | any',
    '}',
  ]);
  const result = g.match('yo');
  t.is(result.succeeded(), true);

  const values = pluckMemoProp(result, 'rightmostFailureOffset');
  t.deepEqual(values, [
    {maxRightmostFailureOffset: 2, any: -1, foo: 2, start: 2},
    {maxRightmostFailureOffset: -1, letter: -1, lower: -1},
    {
      maxRightmostFailureOffset: 0,
      letter: 0,
      lower: 0,
      upper: 0,
      unicodeLtmo: 0,
      any: 0,
      foo: 0,
    },
  ]);
});

test('matchLength', t => {
  const g = makeGrammar(['G {', '  start = notLast* any', '  notLast = any &any', '}']);
  const result = g.match('woo');
  t.is(result.succeeded(), true);

  const values = pluckMemoProp(result, 'matchLength');
  t.deepEqual(values, [
    {any: 1, notLast: 1, start: 3},
    {any: 1, notLast: 1},
    {any: 1, notLast: 0},
    {any: 0},
  ]);
});

test('matchLength - complicated LR', t => {
  const g = makeGrammar([
    'G {',
    '  start = start foo  -- rec',
    '        | foo',
    '  foo = foo letter  -- rec',
    '      | any',
    '}',
  ]);
  const result = g.match('yo');
  t.is(result.succeeded(), true);

  const values = pluckMemoProp(result, 'matchLength');
  t.deepEqual(values, [
    {any: 1, foo: 2, start: 2},
    {letter: 1, lower: 1},
    {letter: 0, lower: 0, upper: 0, unicodeLtmo: 0, any: 0, foo: 0},
  ]);
});

test('binding offsets - lexical rules', t => {
  const g = makeGrammar([
    'G {',
    '  start = start foo  -- rec',
    '        | foo',
    '  foo = foo letter  -- rec',
    '      | "oo"',
    '}',
  ]);
  let result = g.match('oolong');
  t.is(result.succeeded(), true);

  const s = g.createSemantics().addOperation('checkOffsets(t, startIdx)', checkOffsetActions);
  s(result).checkOffsets(t, 0);

  result = g.match('oo');
  s(result).checkOffsets(t, 0);
});

test('binding offsets - syntactic rules', t => {
  const g = makeGrammar([
    '    G {',
    '  Start = letter NotLast* any',
    '  NotLast = any &any',
    '}',
  ]);
  let result = g.match('   a 4');
  t.truthy(result.succeeded());

  const s = g.createSemantics().addOperation('checkOffsets(t, startIdx)', checkOffsetActions);
  s(result).checkOffsets(t, result._cstOffset);

  result = g.match('a   4 ');
  t.truthy(result.succeeded());
  s(result).checkOffsets(t, result._cstOffset);
});

test('incremental parsing + attributes = incremental computation', t => {
  const g = ohm.grammar(fs.readFileSync('test/arithmetic.ohm'));

  let freshlyEvaluated;
  const s = g.createSemantics().addAttribute('value', {
    addExp_plus(x, _op, y) {
      const ans = x.value + y.value;
      freshlyEvaluated.push(this.sourceString);
      return ans;
    },
    addExp_minus(x, _op, y) {
      const ans = x.value - y.value;
      freshlyEvaluated.push(this.sourceString);
      return ans;
    },
    mulExp_times(x, _op, y) {
      const ans = x.value * y.value;
      freshlyEvaluated.push(this.sourceString);
      return ans;
    },
    mulExp_divide(x, _op, y) {
      const ans = x.value / y.value;
      freshlyEvaluated.push(this.sourceString);
      return ans;
    },
    priExp_paren(_open, x, _close) {
      const ans = x.value;
      freshlyEvaluated.push(this.sourceString);
      return ans;
    },
    number(_) {
      const ans = parseInt(this.sourceString);
      freshlyEvaluated.push(this.sourceString);
      return ans;
    },
  });

  const m = g.matcher();

  freshlyEvaluated = [];
  m.replaceInputRange(0, 0, '(1+2)*3-4');
  t.is(s(m.match()).value, 5);
  t.deepEqual(freshlyEvaluated, ['1', '2', '1+2', '(1+2)', '3', '(1+2)*3', '4', '(1+2)*3-4']);

  freshlyEvaluated = [];
  m.replaceInputRange(8, 9, '9');
  t.is(m.getInput(), '(1+2)*3-9');
  t.is(s(m.match()).value, 0);
  t.deepEqual(freshlyEvaluated, ['9', '(1+2)*3-9']);

  freshlyEvaluated = [];
  m.replaceInputRange(2, 3, '-');
  t.is(m.getInput(), '(1-2)*3-9');
  t.is(s(m.match()).value, -12);
  t.deepEqual(freshlyEvaluated, [
    '1', // why? because its 'examinedLength' property is 2
    // (you have to read the next character to know that you're done parsing a number)
    // and we changed that character from '+' to '-'
    '1-2',
    '(1-2)',
    '(1-2)*3',
    '(1-2)*3-9',
  ]);
});