summaryrefslogtreecommitdiffstats
path: root/llparse-builder/src/reachability.ts
diff options
context:
space:
mode:
Diffstat (limited to 'llparse-builder/src/reachability.ts')
-rw-r--r--llparse-builder/src/reachability.ts31
1 files changed, 31 insertions, 0 deletions
diff --git a/llparse-builder/src/reachability.ts b/llparse-builder/src/reachability.ts
new file mode 100644
index 0000000..88bcd65
--- /dev/null
+++ b/llparse-builder/src/reachability.ts
@@ -0,0 +1,31 @@
+import { Node } from './node';
+
+/**
+ * This class finds all reachable nodes
+ */
+export class Reachability {
+ /**
+ * Build and return list of reachable nodes.
+ */
+ public build(root: Node): ReadonlyArray<Node> {
+ const res = new Set();
+ const queue = [ root ];
+ while (queue.length !== 0) {
+ const node = queue.pop()!;
+ if (res.has(node)) {
+ continue;
+ }
+ res.add(node);
+
+ for (const edge of node) {
+ queue.push(edge.node);
+ }
+
+ const otherwise = node.getOtherwiseEdge();
+ if (otherwise !== undefined) {
+ queue.push(otherwise.node);
+ }
+ }
+ return Array.from(res) as ReadonlyArray<Node>;
+ }
+}