"use strict";

var arrays       = require("../../utils/arrays"),
    GrammarError = require("../../grammar-error"),
    asts         = require("../asts"),
    visitor      = require("../visitor");

/*
 * Reports left recursion in the grammar, which prevents infinite recursion in
 * the generated parser.
 *
 * Both direct and indirect recursion is detected. The pass also correctly
 * reports cases like this:
 *
 *   start = "a"? start
 *
 * In general, if a rule reference can be reached without consuming any input,
 * it can lead to left recursion.
 */
function reportLeftRecursion(ast) {
  var check = visitor.build({
    rule: function(node, visitedRules) {
      check(node.expression, visitedRules.concat(node.name));
    },

    sequence: function(node, visitedRules) {
      arrays.every(node.elements, function(element) {
        if (element.type === "rule_ref") {
          check(element, visitedRules);
        }

        return !asts.alwaysAdvancesOnSuccess(ast, element);
      });
    },

    rule_ref: function(node, visitedRules) {
      if (arrays.contains(visitedRules, node.name)) {
        throw new GrammarError(
          "Left recursion detected for rule \"" + node.name + "\".",
          node.location
        );
      }

      check(asts.findRule(ast, node.name), visitedRules);
    }
  });

  check(ast, []);
}

module.exports = reportLeftRecursion;

"use strict";

var arrays       = require("../../utils/arrays"),
    GrammarError = require("../../grammar-error"),
    asts         = require("../asts"),
    visitor      = require("../visitor");

/*
 * Reports left recursion in the grammar, which prevents infinite recursion in
 * the generated parser.
 *
 * Both direct and indirect recursion is detected. The pass also correctly
 * reports cases like this:
 *
 *   start = "a"? start
 *
 * In general, if a rule reference can be reached without consuming any input,
 * it can lead to left recursion.
 */
function reportLeftRecursion(ast) {
  var visitedRules = [];

  var check = visitor.build({
    rule: function(node) {
      visitedRules.push(node.name);
      check(node.expression);
      visitedRules.pop(node.name);
    },

    sequence: function(node) {
      arrays.every(node.elements, function(element) {
        if (element.type === "rule_ref") {
          check(element);
        }

        return !asts.alwaysAdvancesOnSuccess(ast, element);
      });
    },

    rule_ref: function(node) {
      if (arrays.contains(visitedRules, node.name)) {
        throw new GrammarError(
          "Left recursion detected for rule \"" + node.name + "\".",
          node.location
        );
      }

      check(asts.findRule(ast, node.name));
    }
  });

  check(ast);
}

module.exports = reportLeftRecursion;

Change handling of the |visitedRules| array
reportLeftRecursion: Change handling of the |visitedRules| array

Before this commit, the |reportLeftRecursion| pass was written in
functional style, passing the |visitedRules| array around as a parameter
and making a new copy each time a rule was visited. This apparently
caused performance problems in some deeply recursive grammars.

This commit makes it so that there is just one array which is shared
across all the visitor functions via a closure and modified as rules are
visited.

I don't like losing the functional style (it was elegant) but
performance is more important.

Fixes #203.
