Repository: kevinmehall/rust-peg (language: rust)

Issue:
Detect infinite loops / left recursion
It's very easy to accidentally write a parser that goes into an infinite loop. This could be detected by having the generated parse functions keep track of the stack and abort when the same rule gets invoked from the same position as an earlier invocation. It would save having to look through the trace and work out where the infinite loop is coming from.


Discussion / hints:
It should be possible to detect left-recursion statically. We should make this an error.

Fix patch:
diff --git a/Cargo.toml b/Cargo.toml
index eb844dd..4fb1d5e 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -17,7 +17,7 @@ readme = "README.md"
 quote = "0.3"
 codemap = "0.1"
 codemap-diagnostic = "0.1"
-rustfmt-nightly = {version = "0.3.7", optional = true}
+rustfmt-nightly = {version = "0.6", optional = true}
 
 [[bin]]
 name = "rust-peg"
diff --git a/src/lib.rs b/src/lib.rs
index 85d5f41..0e92ae6 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -22,6 +22,9 @@ use codemap_diagnostic::{ Diagnostic, Level, SpanLabel, SpanStyle, Emitter, Colo
 mod translate;
 mod grammar;
 
+#[cfg(test)]
+mod test;
+
 struct PegCompiler {
     codemap: CodeMap,
     diagnostics: Vec<codemap_diagnostic::Diagnostic>
diff --git a/src/translate.rs b/src/translate.rs
index 7f11a9a..cd716db 100644
--- a/src/translate.rs
+++ b/src/translate.rs
@@ -1,8 +1,8 @@
 use std::borrow::ToOwned;
-use std::collections::HashMap;
+use std::collections::{ HashMap, HashSet };
 use quote::Tokens;
 pub use self::Expr::*;
-use codemap::Spanned;
+use codemap::{ Spanned, Span };
 use PegCompiler;
 
 fn raw(s: &str) -> Tokens {
@@ -63,6 +63,14 @@ impl Grammar {
 			}
 		}
 
+		for recursion in Grammar::check_for_left_recursion(&rules) {
+			compiler.span_error(
+				format!("Found illegal left recursion for rule {}: {}", recursion.rule_name, recursion.format_path()),
+				recursion.span,
+				None,
+			)
+		}
+
 		Ok(Grammar{ imports:imports, rules:rules, templates:templates, args: grammar_args.unwrap_or(vec![]) })
 	}
 
@@ -86,6 +94,71 @@ impl Grammar {
 		}).collect();
 		quote!(#(#args)*)
 	}
+
+	fn check_for_left_recursion(rules: &Vec<Rule>) -> Vec<LeftRecursion> {
+		let mut recursions = Vec::new();
+
+		let rule_map: HashMap<&str, &Rule> = rules.iter().map(|rule| (&rule.name[..], rule)).collect();
+		for rule in rules.iter() {
+			LeftRecursionChecker::new(&rule.name, &rule_map).check(rule, &mut recursions)
+		}
+
+		recursions
+	}
+}
+
+struct LeftRecursionChecker<'a> {
+	rule_map: &'a HashMap<&'a str, &'a Rule>,
+	rule_name: &'a str,
+	rule_stack: Vec<&'a str>,
+	visited_rules: HashSet<&'a str>,
+}
+
+impl <'a> LeftRecursionChecker<'a> {
+	fn new(rule_name: &'a str, rule_map: &'a HashMap<&'a str, &'a Rule>) -> LeftRecursionChecker<'a> {
+		let mut rule_stack = Vec::new();
+		rule_stack.push(rule_name);
+		LeftRecursionChecker {
+			rule_map,
+			rule_name,
+			rule_stack,
+			visited_rules: HashSet::new(),
+		}
+    }
+
+	fn check(&mut self, rule: &'a Rule, recursions: &mut Vec<LeftRecursion>) {
+		let left_rules = rule.expr.left_rules(&rule.expr.span);
+
+		for left_rule in left_rules {
+			if self.rule_name == left_rule.node {
+				self.rule_stack.push(left_rule.node);
+				recursions.push(LeftRecursion{
+					rule_name: self.rule_name.into(),
+					span: left_rule.span,
+					path: self.rule_stack.iter().map(|x| (*x).into()).collect(),
+				});
+				self.rule_stack.pop();
+			} else if let Some(rule) = self.rule_map.get(left_rule.node) {
+				if self.visited_rules.insert(&rule.name) {
+					self.rule_stack.push(&rule.name);
+					self.check(rule, recursions);
+					self.rule_stack.pop();
+				}
+            }
+		}
+	}
+}
+
+struct LeftRecursion {
+	rule_name: String,
+	path: Vec<String>,
+	span: Span,
+}
+
+impl LeftRecursion {
+	fn format_path(&self) -> String {
+		self.path.join(" -> ")
+	}
 }
 
 pub enum Item {
@@ -142,6 +215,46 @@ pub enum Expr {
 	InfixExpr{ atom: Box<Spanned<Expr>>, levels: Vec<InfixLevel> }
 }
 
+impl Expr {
+	fn left_rules(&self, span: &Span) -> HashSet<Spanned<&str>> {
+		let mut rules = HashSet::new();
+		self.left_rules_recurse(&mut rules, span);
+		rules
+	}
+
+	fn left_rules_recurse<'a>(&'a self, rules: &mut HashSet<Spanned<&'a str>>, span: &Span) {
+		match *self {
+            RuleExpr(ref rule) => {
+				rules.insert(Spanned{ span: *span, node: rule });
+			},
+            SequenceExpr(ref exprs)
+			| TemplateInvoke(_, ref exprs) => {
+                if let Some(expr) = exprs.first() {
+                    exprs[0].left_rules_recurse(rules, &expr.span);
+                }
+            }
+            ChoiceExpr(ref choices) => {
+                for choice in choices {
+                    choice.left_rules_recurse(rules, &choice.span);
+                }
+            }
+            OptionalExpr(ref expr)
+            | Repeat(ref expr, _, _)
+			| MatchStrExpr(ref expr)
+			| QuietExpr(ref expr)
+            | PosAssertExpr(ref expr)
+            | NegAssertExpr(ref expr) => expr.left_rules_recurse(rules, &expr.span),
+			InfixExpr{ ref atom, .. } => atom.left_rules_recurse(rules, &atom.span),
+            ActionExpr(ref tagged_actions, _, _) => {
+                if let Some(action) = tagged_actions.first() {
+                    action.expr.left_rules_recurse(rules, &action.expr.span);
+                }
+            }
+            _ => {}
+		}
+	}
+}
+
 #[derive(Copy, Clone, PartialEq, Eq)]
 pub enum InfixAssoc { Left, Right }
 


Test patch:
diff --git a/src/test.rs b/src/test.rs
new file mode 100644
index 0000000..578a786
--- /dev/null
+++ b/src/test.rs
@@ -0,0 +1,39 @@
+use ::{ grammar, translate, PegCompiler };
+
+fn compile(src: &str) -> PegCompiler {
+	let mut compiler = PegCompiler::new();
+	let file = compiler.codemap.add_file("input.test".into(), src.into());
+
+	let ast_items = grammar::items(&file.source(), file.span).unwrap();
+	translate::Grammar::from_ast(&mut compiler, ast_items).unwrap();
+
+    compiler
+}
+
+#[test]
+fn test_finds_left_recursion() {
+	let compiler = compile(r#"
+foo
+	= "foo" foo
+	/ bar
+
+bar
+	= "bar" bar
+	/ foo
+"#);
+
+	assert_eq!(compiler.diagnostics[0].message, "Found illegal left recursion for rule foo: foo -> bar -> foo");
+	assert_eq!(compiler.diagnostics[1].message, "Found illegal left recursion for rule bar: bar -> foo -> bar");
+	assert_eq!(compiler.diagnostics.len(), 2);
+}
+
+#[test]
+fn test_finds_direct_left_recursion() {
+	let compiler = compile(r#"
+foo
+	= foo
+"#);
+
+	assert_eq!(compiler.diagnostics[0].message, "Found illegal left recursion for rule foo: foo -> foo");
+	assert_eq!(compiler.diagnostics.len(), 1);
+}
\ No newline at end of file