-
Notifications
You must be signed in to change notification settings - Fork 63
/
report-infinite-recursion.js
101 lines (86 loc) · 2.53 KB
/
report-infinite-recursion.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
"use strict";
const asts = require("../asts");
const 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 reportInfiniteRecursion(ast, options, session) {
// Array with rule names for error message
const visitedRules = [];
// Array with rule_refs for diagnostic
const backtraceRefs = [];
const check = visitor.build({
rule(node) {
if (session.errors > 0) {
return;
}
visitedRules.push(node.name);
check(node.expression);
visitedRules.pop();
},
sequence(node) {
if (session.errors > 0) {
return;
}
node.elements.every(element => {
check(element);
if (session.errors > 0) {
return false;
}
return !asts.alwaysConsumesOnSuccess(ast, element);
});
},
repeated(node) {
if (session.errors > 0) {
return;
}
check(node.expression);
// If an expression does not consume input then recursion
// over delimiter is possible
if (node.delimiter
&& !asts.alwaysConsumesOnSuccess(ast, node.expression)
) {
check(node.delimiter);
}
},
rule_ref(node) {
if (session.errors > 0) {
return;
}
backtraceRefs.push(node);
const rule = asts.findRule(ast, node.name);
if (visitedRules.indexOf(node.name) !== -1) {
visitedRules.push(node.name);
session.error(
"Possible infinite loop when parsing (left recursion: "
+ visitedRules.join(" -> ")
+ ")",
rule.nameLocation,
backtraceRefs.map((ref, i, a) => ({
message: i + 1 !== a.length
? `Step ${i + 1}: call of the rule "${ref.name}" without input consumption`
: `Step ${i + 1}: call itself without input consumption - left recursion`,
location: ref.location,
}))
);
// Because we enter into recursion we should break it
return;
}
// Because we run all checks in one stage, some rules could be missing - this check
// executed in parallel
if (rule) {
check(rule);
}
backtraceRefs.pop();
},
});
check(ast);
}
module.exports = reportInfiniteRecursion;