1 files changed, 182 insertions, 0 deletions
diff --git a/llparse-builder/src/span-allocator.ts b/llparse-builder/src/span-allocator.ts
new file mode 100644
index 0000000..b3e8f6b
--- /dev/null
+++ b/llparse-builder/src/span-allocator.ts
@@ -0,0 +1,182 @@
+import * as assert from 'assert';
+import * as debugAPI from 'debug';
+
+import { Node, SpanEnd, SpanStart } from './node';
+import { Reachability } from './reachability';
+import { Span } from './span';
+
+const debug = debugAPI('llparse-builder:span-allocator');
+
+type SpanSet = Set<Span>;
+
+interface ISpanActiveInfo {
+  readonly active: Map<Node, SpanSet>;
+  readonly spans: ReadonlyArray<Span>;
+}
+
+type SpanOverlap = Map<Span, SpanSet>;
+
+export interface ISpanAllocatorResult {
+  readonly colors: ReadonlyMap<Span, number>;
+  readonly concurrency: ReadonlyArray<ReadonlyArray<Span> >;
+  readonly max: number;
+}
+
+function id(node: SpanStart | SpanEnd): Span {
+  return node.span;
+}
+
+export class SpanAllocator {
+  public allocate(root: Node): ISpanAllocatorResult {
+    const r = new Reachability();
+    const nodes = r.build(root);
+    const info = this.computeActive(nodes);
+    this.check(info);
+    const overlap = this.computeOverlap(info);
+    return this.color(info.spans, overlap);
+  }
+
+  private computeActive(nodes: ReadonlyArray<Node>): ISpanActiveInfo {
+    const activeMap: Map<Node, SpanSet> = new Map();
+    nodes.forEach((node) => activeMap.set(node, new Set()));
+
+    const queue: Set<Node> = new Set(nodes);
+    const spans: SpanSet = new Set();
+    for (const node of queue) {
+      queue.delete(node);
+
+      const active = activeMap.get(node)!;
+
+      if (node instanceof SpanStart) {
+        const span = id(node);
+        spans.add(span);
+        active.add(span);
+      }
+
+      active.forEach((span) => {
+        // Don't propagate span past the spanEnd
+        if (node instanceof SpanEnd && span === id(node)) {
+          return;
+        }
+
+        node.getAllEdges().forEach((edge) => {
+          const edgeNode = edge.node;
+
+          // Disallow loops
+          if (edgeNode instanceof SpanStart) {
+            assert.notStrictEqual(id(edgeNode), span,
+              `Detected loop in span "${span.callback.name}", started ` +
+              `at "${node.name}"`);
+          }
+
+          const edgeActive = activeMap.get(edgeNode)!;
+          if (edgeActive.has(span)) {
+            return;
+          }
+
+          edgeActive.add(span);
+          queue.add(edgeNode);
+        });
+      });
+    }
+
+    return { active: activeMap, spans: Array.from(spans) };
+  }
+
+  private check(info: ISpanActiveInfo): void {
+    debug('check start');
+    for (const [ node, spans ] of info.active) {
+      for (const edge of node.getAllEdges()) {
+        if (edge.node instanceof SpanStart) {
+          continue;
+        }
+
+        // Skip terminal nodes
+        if (edge.node.getAllEdges().length === 0) {
+          continue;
+        }
+
+        debug('checking edge from %j to %j', node.name, edge.node.name);
+
+        const edgeSpans = info.active.get(edge.node)!;
+        for (const subSpan of edgeSpans) {
+          assert(spans.has(subSpan),
+            `Unmatched span end for "${subSpan.callback.name}" ` +
+            `at "${edge.node.name}", coming from "${node.name}"`);
+        }
+
+        if (edge.node instanceof SpanEnd) {
+          const span = id(edge.node);
+          assert(spans.has(span),
+            `Unmatched span end for "${span.callback.name}"`);
+        }
+      }
+    }
+  }
+
+  private computeOverlap(info: ISpanActiveInfo): SpanOverlap {
+    const active = info.active;
+    const overlap: SpanOverlap = new Map();
+
+    info.spans.forEach((span) => overlap.set(span, new Set()));
+
+    active.forEach((spans) => {
+      spans.forEach((one) => {
+        const set = overlap.get(one)!;
+        spans.forEach((other) => {
+          if (other !== one) {
+            set.add(other);
+          }
+        });
+      });
+    });
+
+    return overlap;
+  }
+
+  private color(spans: ReadonlyArray<Span>, overlapMap: SpanOverlap)
+    : ISpanAllocatorResult {
+    let max = -1;
+    const colors: Map<Span, number> = new Map();
+
+    const allocate = (span: Span): number => {
+      if (colors.has(span)) {
+        return colors.get(span)!;
+      }
+
+      const overlap = overlapMap.get(span)!;
+
+      // See which colors are already used
+      const used: Set<number> = new Set();
+      for (const subSpan of overlap) {
+        if (colors.has(subSpan)) {
+          used.add(colors.get(subSpan)!);
+        }
+      }
+
+      // Find minimum available color
+      let i;
+      for (i = 0; used.has(i); i++) {
+        // no-op
+      }
+
+      max = Math.max(max, i);
+      colors.set(span, i);
+
+      return i;
+    };
+
+    const map: Map<Span, number> = new Map();
+
+    spans.forEach((span) => map.set(span, allocate(span)));
+
+    const concurrency: Span[][] = new Array(max + 1);
+    for (let i = 0; i < concurrency.length; i++) {
+      concurrency[i] = [];
+    }
+
+    spans.forEach((span) => concurrency[allocate(span)].push(span));
+
+    return { colors: map, concurrency, max };
+  }
+}