var utils = require(“../../utils”),

GrammarError = require("../../grammar-error");

/* Checks that no left recursion is present. */ module.exports = function(ast) {

function nop() {}

function checkExpression(node, appliedRules) {
  check(node.expression, appliedRules);
}

function checkSubnodes(propertyName) {
  return function(node, appliedRules) {
    utils.each(node[propertyName], function(subnode) {
      check(subnode, appliedRules);
    });
  };
}

var check = utils.buildNodeVisitor({
  grammar:     checkSubnodes("rules"),

  rule:
    function(node, appliedRules) {
      check(node.expression, appliedRules.concat(node.name));
    },

  named:       checkExpression,
  choice:      checkSubnodes("alternatives"),
  action:      checkExpression,

  sequence:
    function(node, appliedRules) {
      if (node.elements.length > 0) {
        check(node.elements[0], appliedRules);
      }
    },

  labeled:      checkExpression,
  text:         checkExpression,
  simple_and:   checkExpression,
  simple_not:   checkExpression,
  semantic_and: nop,
  semantic_not: nop,
  optional:     checkExpression,
  zero_or_more: checkExpression,
  one_or_more:  checkExpression,

  rule_ref:
    function(node, appliedRules) {
      if (utils.contains(appliedRules, node.name)) {
        throw new GrammarError(
          "Left recursion detected for rule \"" + node.name + "\"."
        );
      }
      check(utils.findRuleByName(ast, node.name), appliedRules);
    },

  literal:      nop,
  "class":      nop,
  any:          nop
});

check(ast, []);

};