3 files changed, 358 insertions, 0 deletions
diff --git a/llparse-builder/test/builder-test.ts b/llparse-builder/test/builder-test.ts
new file mode 100644
index 0000000..82723ec
--- /dev/null
+++ b/llparse-builder/test/builder-test.ts
@@ -0,0 +1,94 @@
+import * as assert from 'assert';
+
+import { Builder } from '../src/builder';
+
+describe('LLParse/Builder', () => {
+  let b: Builder;
+  beforeEach(() => {
+    b = new Builder();
+  });
+
+  it('should build primitive graph', () => {
+    const start = b.node('start');
+    const end = b.node('end');
+
+    start
+      .peek('e', end)
+      .match('a', start)
+      .otherwise(b.error(1, 'error'));
+
+    end
+      .skipTo(start);
+
+    const edges = start.getEdges();
+    assert.strictEqual(edges.length, 2);
+
+    assert(!edges[0].noAdvance);
+    assert.strictEqual(edges[0].node, start);
+
+    assert(edges[1].noAdvance);
+    assert.strictEqual(edges[1].node, end);
+  });
+
+  it('should disallow duplicate edges', () => {
+    const start = b.node('start');
+
+    start.peek('e', start);
+
+    assert.throws(() => {
+      start.peek('e', start);
+    }, /duplicate edge/);
+  });
+
+  it('should disallow select to non-invoke', () => {
+    const start = b.node('start');
+
+    assert.throws(() => {
+      start.select('a', 1, start);
+    }, /value to non-Invoke/);
+  });
+
+  it('should disallow select to match-invoke', () => {
+    const start = b.node('start');
+    const invoke = b.invoke(b.code.match('something'));
+
+    assert.throws(() => {
+      start.select('a', 1, invoke);
+    }, /Invalid.*code signature/);
+  });
+
+  it('should disallow peek to value-invoke', () => {
+    const start = b.node('start');
+    const invoke = b.invoke(b.code.value('something'));
+
+    assert.throws(() => {
+      start.peek('a', invoke);
+    }, /Invalid.*code signature/);
+  });
+
+  it('should allow select to value-invoke', () => {
+    const start = b.node('start');
+    const invoke = b.invoke(b.code.value('something'));
+
+    assert.doesNotThrow(() => {
+      start.select('a', 1, invoke);
+    });
+  });
+
+  it('should create edges for Invoke', () => {
+    const start = b.node('start');
+    const invoke = b.invoke(b.code.value('something'), {
+      '-1': start,
+      '1': start,
+      '10': start,
+    });
+
+    const edges = invoke.getEdges();
+    const keys = edges.map((edge) => edge.key!);
+    assert.deepStrictEqual(keys, [
+      -1,
+      1,
+      10,
+    ]);
+  });
+});
diff --git a/llparse-builder/test/loop-checker-test.ts b/llparse-builder/test/loop-checker-test.ts
new file mode 100644
index 0000000..0df6064
--- /dev/null
+++ b/llparse-builder/test/loop-checker-test.ts
@@ -0,0 +1,118 @@
+import * as assert from 'assert';
+
+import { Builder, LoopChecker } from '../src/builder';
+
+describe('LLParse/LoopChecker', () => {
+  let b: Builder;
+  let lc: LoopChecker;
+  beforeEach(() => {
+    b = new Builder();
+    lc = new LoopChecker();
+  });
+
+  it('should detect shallow loops', () => {
+    const start = b.node('start');
+
+    start
+      .otherwise(start);
+
+    assert.throws(() => {
+      lc.check(start);
+    }, /Detected loop in "start".*"start"/);
+  });
+
+  it('should detect loops', () => {
+    const start = b.node('start');
+    const a = b.node('a');
+    const invoke = b.invoke(b.code.match('nop'), {
+      0: start,
+    }, b.error(1, 'error'));
+
+    start
+      .peek('a', a)
+      .otherwise(b.error(1, 'error'));
+
+    a.otherwise(invoke);
+
+    assert.throws(() => {
+      lc.check(start);
+    }, /Detected loop in "a".*"a" -> "invoke_nop"/);
+  });
+
+  it('should detect seemingly unreachable keys', () => {
+    const start = b.node('start');
+    const loop = b.node('loop');
+
+    start
+      .peek('a', loop)
+      .otherwise(b.error(1, 'error'));
+
+    loop
+      .match('a', loop)
+      .otherwise(loop);
+
+    assert.throws(() => {
+      lc.check(start);
+    }, /Detected loop in "loop" through.*"loop"/);
+  });
+
+  it('should ignore loops through `peek` to `match`', () => {
+    const start = b.node('start');
+    const a = b.node('a');
+    const invoke = b.invoke(b.code.match('nop'), {
+      0: start,
+    }, b.error(1, 'error'));
+
+    start
+      .peek('a', a)
+      .otherwise(b.error(1, 'error'));
+
+    a
+      .match('abc', invoke)
+      .otherwise(start);
+
+    assert.doesNotThrow(() => lc.check(start));
+  });
+
+  it('should ignore irrelevant `peek`s', () => {
+    const start = b.node('start');
+    const a = b.node('a');
+
+    start
+      .peek('a', a)
+      .otherwise(b.error(1, 'error'));
+
+    a
+      .peek('b', start)
+      .otherwise(b.error(1, 'error'));
+
+    assert.doesNotThrow(() => lc.check(start));
+  });
+
+  it('should ignore loops with multi `peek`/`match`', () => {
+    const start = b.node('start');
+    const another = b.node('another');
+
+    const NUM: ReadonlyArray<string> = [
+      '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
+    ];
+
+    const ALPHA: ReadonlyArray<string> = [
+      'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o',
+      'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z',
+      'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O',
+      'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z',
+    ];
+
+    start
+      .match(ALPHA, start)
+      .peek(NUM, another)
+      .skipTo(start);
+
+    another
+      .match(NUM, another)
+      .otherwise(start);
+
+    assert.doesNotThrow(() => lc.check(start));
+  });
+});
diff --git a/llparse-builder/test/span-allocator-test.ts b/llparse-builder/test/span-allocator-test.ts
new file mode 100644
index 0000000..bc8f656
--- /dev/null
+++ b/llparse-builder/test/span-allocator-test.ts
@@ -0,0 +1,146 @@
+import * as assert from 'assert';
+
+import { Builder, SpanAllocator } from '../src/builder';
+
+describe('LLParse/LoopChecker', () => {
+  let b: Builder;
+  let sa: SpanAllocator;
+  beforeEach(() => {
+    b = new Builder();
+    sa = new SpanAllocator();
+  });
+
+  it('should allocate single span', () => {
+    const span = b.span(b.code.span('span'));
+    const start = b.node('start');
+    const body = b.node('body');
+
+    start
+      .otherwise(span.start(body));
+
+    body
+      .skipTo(span.end(start));
+
+    const res = sa.allocate(start);
+
+    assert.strictEqual(res.max, 0);
+
+    assert.strictEqual(res.concurrency.length, 1);
+    assert.ok(res.concurrency[0].includes(span));
+
+    assert.strictEqual(res.colors.size, 1);
+    assert.strictEqual(res.colors.get(span), 0);
+  });
+
+  it('should allocate overlapping spans', () => {
+    const span1 = b.span(b.code.span('span1'));
+    const span2 = b.span(b.code.span('span2'));
+
+    const start = b.node('start');
+    const body1 = b.node('body1');
+    const body2 = b.node('body2');
+
+    start
+      .otherwise(span1.start(body1));
+
+    body1
+      .otherwise(span2.start(body2));
+
+    body2
+      .skipTo(span2.end(span1.end(start)));
+
+    const res = sa.allocate(start);
+
+    assert.strictEqual(res.max, 1);
+
+    assert.strictEqual(res.concurrency.length, 2);
+    assert.ok(res.concurrency[0].includes(span1));
+    assert.ok(res.concurrency[1].includes(span2));
+
+    assert.strictEqual(res.colors.size, 2);
+    assert.strictEqual(res.colors.get(span1), 0);
+    assert.strictEqual(res.colors.get(span2), 1);
+  });
+
+  it('should allocate non-overlapping spans', () => {
+    const span1 = b.span(b.code.span('span1'));
+    const span2 = b.span(b.code.span('span2'));
+
+    const start = b.node('start');
+    const body1 = b.node('body1');
+    const body2 = b.node('body2');
+
+    start
+      .match('a', span1.start(body1))
+      .otherwise(span2.start(body2));
+
+    body1
+      .skipTo(span1.end(start));
+
+    body2
+      .skipTo(span2.end(start));
+
+    const res = sa.allocate(start);
+
+    assert.strictEqual(res.max, 0);
+
+    assert.strictEqual(res.concurrency.length, 1);
+    assert.ok(res.concurrency[0].includes(span1));
+    assert.ok(res.concurrency[0].includes(span2));
+
+    assert.strictEqual(res.colors.size, 2);
+    assert.strictEqual(res.colors.get(span1), 0);
+    assert.strictEqual(res.colors.get(span2), 0);
+  });
+
+  it('should throw on loops', () => {
+    const span = b.span(b.code.span('span_name'));
+
+    const start = b.node('start');
+
+    start
+      .otherwise(span.start(start));
+
+    assert.throws(() => {
+      sa.allocate(start);
+    }, /loop.*span_name/);
+  });
+
+  it('should throw on unmatched ends', () => {
+    const start = b.node('start');
+    const span = b.span(b.code.span('on_data'));
+
+    start.otherwise(span.end().skipTo(start));
+
+    assert.throws(() => sa.allocate(start), /unmatched.*on_data/i);
+  });
+
+  it('should throw on branched unmatched ends', () => {
+    const start = b.node('start');
+    const end = b.node('end');
+    const span = b.span(b.code.span('on_data'));
+
+    start
+      .match('a', end)
+      .match('b', span.start(end))
+      .otherwise(b.error(1, 'error'));
+
+    end
+      .otherwise(span.end(start));
+
+    assert.throws(() => sa.allocate(start), /unmatched.*on_data/i);
+  });
+
+  it('should propagate through the Invoke map', () => {
+    const start = b.node('start');
+    const span = b.span(b.code.span('llparse__on_data'));
+
+    b.property('i8', 'custom');
+
+    start.otherwise(b.invoke(b.code.load('custom'), {
+      0: span.end().skipTo(start),
+    }, span.end().skipTo(start)));
+
+    assert.doesNotThrow(() => sa.allocate(span.start(start)));
+  });
+});