summaryrefslogtreecommitdiffstats
path: root/llparse-builder/src/loop-checker
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--llparse-builder/src/loop-checker/index.ts205
-rw-r--r--llparse-builder/src/loop-checker/lattice.ts115
2 files changed, 320 insertions, 0 deletions
diff --git a/llparse-builder/src/loop-checker/index.ts b/llparse-builder/src/loop-checker/index.ts
new file mode 100644
index 0000000..5751955
--- /dev/null
+++ b/llparse-builder/src/loop-checker/index.ts
@@ -0,0 +1,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);
+ }
+}
diff --git a/llparse-builder/src/loop-checker/lattice.ts b/llparse-builder/src/loop-checker/lattice.ts
new file mode 100644
index 0000000..8d2a7fe
--- /dev/null
+++ b/llparse-builder/src/loop-checker/lattice.ts
@@ -0,0 +1,115 @@
+import * as assert from 'assert';
+
+const MAX_VALUE = 256;
+const WORD_SIZE = 32;
+const SIZE = (MAX_VALUE / WORD_SIZE) | 0;
+const WORD_FILL = -1 | 0;
+
+assert.strictEqual(MAX_VALUE % WORD_SIZE, 0);
+
+export type LatticeValue = 'empty' | ReadonlyArray<number> | 'any';
+
+/**
+ * A fixed-size bitfield, really
+ */
+export class Lattice {
+ protected readonly words: number[];
+
+ constructor(value: LatticeValue) {
+ this.words = new Array(SIZE).fill(value === 'any' ? WORD_FILL : 0);
+
+ if (Array.isArray(value)) {
+ for (const single of value) {
+ this.add(single);
+ }
+ }
+ }
+
+ public check(bit: number): boolean {
+ assert(0 <= bit && bit < MAX_VALUE, 'Invalid bit');
+ const index = (bit / WORD_SIZE) | 0;
+ const off = bit % WORD_SIZE;
+ return (this.words[index] & (1 << off)) !== 0;
+ }
+
+ public union(other: Lattice): Lattice {
+ const result = new Lattice('empty');
+
+ for (let i = 0; i < SIZE; i++) {
+ result.words[i] = this.words[i] | other.words[i];
+ }
+
+ return result;
+ }
+
+ public intersect(other: Lattice): Lattice {
+ const result = new Lattice('empty');
+
+ for (let i = 0; i < SIZE; i++) {
+ result.words[i] = this.words[i] & other.words[i];
+ }
+
+ return result;
+ }
+
+ public subtract(other: Lattice): Lattice {
+ const result = new Lattice('empty');
+
+ for (let i = 0; i < SIZE; i++) {
+ result.words[i] = this.words[i] & (~other.words[i]);
+ }
+
+ return result;
+ }
+
+ public isEqual(other: Lattice): boolean {
+ if (this === other) {
+ return true;
+ }
+
+ for (let i = 0; i < SIZE; i++) {
+ if (this.words[i] !== other.words[i]) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ public *[Symbol.iterator](): Iterator<number> {
+ // TODO(indutny): improve speed if needed
+ for (let i = 0; i < MAX_VALUE; i++) {
+ if (this.check(i)) {
+ yield i;
+ }
+ }
+ }
+
+ public toJSON(): any {
+ let isEmpty = true;
+ let isFull = true;
+ for (let i = 0; i < SIZE; i++) {
+ if (this.words[i] !== 0) {
+ isEmpty = false;
+ }
+ if (this.words[i] !== WORD_FILL) {
+ isFull = false;
+ }
+ }
+ if (isEmpty) {
+ return 'empty';
+ }
+ if (isFull) {
+ return 'any';
+ }
+ return Array.from(this);
+ }
+
+ // Private
+
+ private add(bit: number): void {
+ assert(0 <= bit && bit < MAX_VALUE, 'Invalid bit');
+ const index = (bit / WORD_SIZE) | 0;
+ const off = bit % WORD_SIZE;
+ this.words[index] |= 1 << off;
+ }
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-13 03:09:10 +0000