Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Browse files

Implement infinite loop detection

Fixes #26.
commit d7fc0b5c3bfbcd079712d2d4958ec38eb9ad3822 1 parent 95ce20e
@dmajda dmajda authored
View
1  Makefile
@@ -18,6 +18,7 @@ MODULES = utils/arrays \
compiler/passes/generate-javascript \
compiler/passes/remove-proxy-rules \
compiler/passes/report-left-recursion \
+ compiler/passes/report-infinite-loops \
compiler/passes/report-missing-rules \
compiler \
peg
View
3  lib/compiler.js
@@ -12,7 +12,8 @@ var compiler = {
passes: {
check: {
reportMissingRules: require("./compiler/passes/report-missing-rules"),
- reportLeftRecursion: require("./compiler/passes/report-left-recursion")
+ reportLeftRecursion: require("./compiler/passes/report-left-recursion"),
+ reportInfiniteLoops: require("./compiler/passes/report-infinite-loops")
},
transform: {
removeProxyRules: require("./compiler/passes/remove-proxy-rules")
View
27 lib/compiler/passes/report-infinite-loops.js
@@ -0,0 +1,27 @@
+var GrammarError = require("../../grammar-error"),
+ asts = require("../asts"),
+ visitor = require("../visitor");
+
+/*
+ * Reports expressions that don't consume any input inside |*| or |+| in the
+ * grammar, which prevents infinite loops in the generated parser.
+ */
+function reportInfiniteLoops(ast) {
+ var check = visitor.build({
+ zero_or_more: function(node) {
+ if (asts.matchesEmpty(ast, node.expression)) {
+ throw new GrammarError("Infinite loop detected.");
+ }
+ },
+
+ one_or_more: function(node) {
+ if (asts.matchesEmpty(ast, node.expression)) {
+ throw new GrammarError("Infinite loop detected.");
+ }
+ }
+ });
+
+ check(ast);
+}
+
+module.exports = reportInfiniteLoops;
View
1  package.json
@@ -27,6 +27,7 @@
"lib/compiler/passes/generate-javascript.js",
"lib/compiler/passes/remove-proxy-rules.js",
"lib/compiler/passes/report-left-recursion.js",
+ "lib/compiler/passes/report-infinite-loops.js",
"lib/compiler/passes/report-missing-rules.js",
"lib/grammar-error.js",
"lib/parser.js",
View
1  spec/index.html
@@ -11,6 +11,7 @@
<script src="unit/compiler/passes/helpers.js"></script>
<script src="unit/compiler/passes/report-missing-rules.spec.js"></script>
<script src="unit/compiler/passes/report-left-recursion.spec.js"></script>
+ <script src="unit/compiler/passes/report-infinite-loops.spec.js"></script>
<script src="unit/compiler/passes/remove-proxy-rules.spec.js"></script>
<script src="unit/compiler/passes/generate-bytecode.spec.js"></script>
<script src="api/pegjs-api.spec.js"></script>
View
71 spec/unit/compiler/passes/report-infinite-loops.spec.js
@@ -0,0 +1,71 @@
+describe("compiler pass |reportLeftRecursion|", function() {
+ var pass = PEG.compiler.passes.check.reportInfiniteLoops;
+
+ it("reports infinite loops for zero_or_more", function() {
+ expect(pass).toReportError('start = ("")*', {
+ message: "Infinite loop detected."
+ });
+ });
+
+ it("reports infinite loops for one_or_more", function() {
+ expect(pass).toReportError('start = ("")+', {
+ message: "Infinite loop detected."
+ });
+ });
+
+ it("computes empty string matching correctly", function() {
+ expect(pass).toReportError('start = ("" / "a" / "b")*');
+ expect(pass).toReportError('start = ("a" / "" / "b")*');
+ expect(pass).toReportError('start = ("a" / "b" / "")*');
+ expect(pass).not.toReportError('start = ("a" / "b" / "c")*');
+
+ expect(pass).toReportError('start = ("" { })*');
+ expect(pass).not.toReportError('start = ("a" { })*');
+
+ expect(pass).toReportError('start = ("" "" "")*');
+ expect(pass).not.toReportError('start = ("a" "" "")*');
+ expect(pass).not.toReportError('start = ("" "a" "")*');
+ expect(pass).not.toReportError('start = ("" "" "a")*');
+
+ expect(pass).toReportError('start = (a:"")*');
+ expect(pass).not.toReportError('start = (a:"a")*');
+
+ expect(pass).toReportError('start = ($"")*');
+ expect(pass).not.toReportError('start = ($"a")*');
+
+ expect(pass).toReportError('start = (&"")*');
+ expect(pass).toReportError('start = (&"a")*');
+
+ expect(pass).toReportError('start = (!"")*');
+ expect(pass).toReportError('start = (!"a")*');
+
+ expect(pass).toReportError('start = (""?)*');
+ expect(pass).toReportError('start = ("a"?)*');
+
+ expect(pass).toReportError('start = (""*)*');
+ expect(pass).toReportError('start = ("a"*)*');
+
+ expect(pass).toReportError('start = (""+)*');
+ expect(pass).not.toReportError('start = ("a"+)*');
+
+ expect(pass).toReportError('start = (&{ })*');
+
+ expect(pass).toReportError('start = (!{ })*');
+
+ expect(pass).toReportError([
+ 'start = a*',
+ 'a = ""'
+ ].join('\n'));
+ expect(pass).not.toReportError([
+ 'start = a*',
+ 'a = "a"'
+ ].join('\n'));
+
+ expect(pass).toReportError('start = ""*');
+ expect(pass).not.toReportError('start = "a"*');
+
+ expect(pass).not.toReportError('start = [a-d]*');
+
+ expect(pass).not.toReportError('start = "."*');
+ });
+});
Please sign in to comment.
Something went wrong with that request. Please try again.