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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
|
import * as assert from 'assert';
import * as debugAPI from 'debug';
import { Node } from '../node';
import { Reachability } from '../reachability';
import { Lattice } from './lattice';
const debug = debugAPI('llparse-builder:loop-checker');
const EMPTY_VALUE = new Lattice('empty');
const ANY_VALUE = new Lattice('any');
/**
* This class implements a loop checker pass. The goal of this pass is to verify
* that the graph doesn't contain infinite loops.
*/
export class LoopChecker {
private readonly lattice: Map<Node, Lattice> = new Map();
// Just a cache of terminated keys
private readonly terminatedCache: Map<Node, Lattice> = new Map();
/**
* Run loop checker pass on a graph starting from `root`.
*
* Throws on failure.
*
* @param root Graph root node
*/
public check(root: Node): void {
const r = new Reachability();
const nodes = r.build(root);
for (const node of nodes) {
debug('checking loops starting from %j', node.name);
// Set initial lattice value for all nodes
this.clear(nodes);
// Mark root as reachable with any value
this.lattice.set(node, ANY_VALUE);
// Raise lattice values
let changed: Set<Node> = new Set([ root ]);
while (changed.size !== 0) {
if (debug.enabled) {
debug('changed %j', Array.from(changed).map((other) => other.name));
}
const next: Set<Node> = new Set();
for (const changedNode of changed) {
this.propagate(changedNode, next);
}
changed = next;
}
debug('lattice stabilized');
// Visit nodes and walk through reachable edges to detect loops
this.visit(node, []);
}
}
private clear(nodes: ReadonlyArray<Node>): void {
for (const node of nodes) {
this.lattice.set(node, EMPTY_VALUE);
}
}
private propagate(node: Node, changed: Set<Node>): void {
let value: Lattice = this.lattice.get(node)!;
debug('propagate(%j), initial value %j', node.name, value);
// Terminate values that are consumed by `match`/`select`
const terminated = this.terminate(node, value, changed);
if (!terminated.isEqual(EMPTY_VALUE)) {
debug('node %j terminates %j', node.name, terminated);
value = value.subtract(terminated);
if (value.isEqual(EMPTY_VALUE)) {
return;
}
}
const keysByTarget: Map<Node, Lattice> = new Map();
// Propagate value through `.peek()`/`.otherwise()` edges
for (const edge of node.getAllEdges()) {
if (!edge.noAdvance) {
continue;
}
let targetValue: Lattice;
if (keysByTarget.has(edge.node)) {
targetValue = keysByTarget.get(edge.node)!;
} else {
targetValue = this.lattice.get(edge.node)!;
}
// `otherwise` or `Invoke`'s edges
if (edge.key === undefined || typeof edge.key === 'number') {
targetValue = targetValue.union(value);
} else {
// `.peek()`
const edgeValue = new Lattice([ edge.key[0] ]).intersect(value);
if (edgeValue.isEqual(EMPTY_VALUE)) {
continue;
}
targetValue = targetValue.union(edgeValue);
}
keysByTarget.set(edge.node, targetValue);
}
for (const [ child, childValue ] of keysByTarget) {
debug('node %j propagates %j to %j', node.name, childValue,
child.name);
this.update(child, childValue, changed);
}
}
private update(node: Node, newValue: Lattice, changed: Set<Node>): boolean {
const value = this.lattice.get(node)!;
if (newValue.isEqual(value)) {
return false;
}
this.lattice.set(node, newValue);
changed.add(node);
return true;
}
private terminate(node: Node, value: Lattice, changed: Set<Node>): Lattice {
if (this.terminatedCache.has(node)) {
return this.terminatedCache.get(node)!;
}
const terminated: number[] = [];
for (const edge of node.getAllEdges()) {
if (edge.noAdvance) {
continue;
}
// Ignore `otherwise` and `Invoke`'s edges
if (edge.key === undefined || typeof edge.key === 'number') {
continue;
}
terminated.push(edge.key[0]);
}
const result = new Lattice(terminated);
this.terminatedCache.set(node, result);
return result;
}
private visit(node: Node, path: ReadonlyArray<Node>): void {
let value = this.lattice.get(node)!;
debug('enter %j, value is %j', node.name, value);
const terminated = this.terminatedCache.has(node) ?
this.terminatedCache.get(node)! : EMPTY_VALUE;
if (!terminated.isEqual(EMPTY_VALUE)) {
debug('subtract terminated %j', terminated);
value = value.subtract(terminated);
if (value.isEqual(EMPTY_VALUE)) {
debug('terminated everything');
return;
}
}
for (const edge of node.getAllEdges()) {
if (!edge.noAdvance) {
continue;
}
let edgeValue = value;
// `otherwise` or `Invoke`'s edges
if (edge.key === undefined || typeof edge.key === 'number') {
// nothing to do
// `.peek()`
} else {
edgeValue = edgeValue.intersect(new Lattice([ edge.key[0] ]));
}
// Ignore unreachable edges
if (edgeValue.isEqual(EMPTY_VALUE)) {
continue;
}
if (path.indexOf(edge.node) !== -1) {
if (path.length === 0) {
throw new Error(
`Detected loop in "${edge.node.name}" through "${edge.node.name}"`);
}
throw new Error(
`Detected loop in "${edge.node.name}" through chain ` +
`${path.map((parent) => '"' + parent.name + '"').join(' -> ')}`);
}
this.visit(edge.node, path.concat(edge.node));
}
debug('leave %j', node.name);
}
}
|
