Adding upstream version 5.28.2+dfsg1+~cs23.11.12.3.upstream/5.28.2+dfsg1+_cs23.11.12.3upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

55 files changed, 1472 insertions, 0 deletions

diff --git a/llparse-frontend/src/code/and.ts b/llparse-frontend/src/code/and.ts
new file mode 100644
index 0000000..54dc5fd
--- /dev/null
+++ b/llparse-frontend/src/code/and.ts
@@ -0,0 +1,8 @@
+import { toCacheKey } from '../utils';
+import { FieldValue } from './field-value';
+
+export class And extends FieldValue {
+  constructor(name: string, field: string, value: number) {
+    super('match', `and_${field}_${toCacheKey(value)}`, name, field, value);
+  }
+}
diff --git a/llparse-frontend/src/code/base.ts b/llparse-frontend/src/code/base.ts
new file mode 100644
index 0000000..cde4b6d
--- /dev/null
+++ b/llparse-frontend/src/code/base.ts
@@ -0,0 +1,8 @@
+export type Signature = 'match' | 'value' | 'span';
+
+export abstract class Code {
+  constructor(public readonly signature: Signature,
+              public readonly cacheKey: string,
+              public readonly name: string) {
+  }
+}
diff --git a/llparse-frontend/src/code/external.ts b/llparse-frontend/src/code/external.ts
new file mode 100644
index 0000000..f4254c1
--- /dev/null
+++ b/llparse-frontend/src/code/external.ts
@@ -0,0 +1,7 @@
+import { Code, Signature } from './base';
+
+export abstract class External extends Code {
+  constructor(signature: Signature, name: string) {
+    super(signature, 'external_' + name, name);
+  }
+}
diff --git a/llparse-frontend/src/code/field-value.ts b/llparse-frontend/src/code/field-value.ts
new file mode 100644
index 0000000..1c7c109
--- /dev/null
+++ b/llparse-frontend/src/code/field-value.ts
@@ -0,0 +1,13 @@
+import * as assert from 'assert';
+
+import { Signature } from './base';
+import { Field } from './field';
+
+export abstract class FieldValue extends Field {
+  constructor(signature: Signature, cacheKey: string, name: string,
+              field: string, public readonly value: number) {
+    super(signature, cacheKey, name, field);
+
+    assert.strictEqual(value, value | 0, 'FieldValue `value` must be integer');
+  }
+}
diff --git a/llparse-frontend/src/code/field.ts b/llparse-frontend/src/code/field.ts
new file mode 100644
index 0000000..c60b8ef
--- /dev/null
+++ b/llparse-frontend/src/code/field.ts
@@ -0,0 +1,8 @@
+import { Code, Signature } from './base';
+
+export abstract class Field extends Code {
+  constructor(signature: Signature, cacheKey: string, name: string,
+              public readonly field: string) {
+    super(signature, cacheKey, name);
+  }
+}
diff --git a/llparse-frontend/src/code/index.ts b/llparse-frontend/src/code/index.ts
new file mode 100644
index 0000000..c7d5c69
--- /dev/null
+++ b/llparse-frontend/src/code/index.ts
@@ -0,0 +1,15 @@
+export * from './and';
+export * from './base';
+export * from './external';
+export * from './field-value';
+export * from './field';
+export * from './is-equal';
+export * from './load';
+export * from './match';
+export * from './mul-add';
+export * from './or';
+export * from './span';
+export * from './store';
+export * from './test';
+export * from './update';
+export * from './value';
diff --git a/llparse-frontend/src/code/is-equal.ts b/llparse-frontend/src/code/is-equal.ts
new file mode 100644
index 0000000..16a2ee2
--- /dev/null
+++ b/llparse-frontend/src/code/is-equal.ts
@@ -0,0 +1,9 @@
+import { toCacheKey } from '../utils';
+import { FieldValue } from './field-value';
+
+export class IsEqual extends FieldValue {
+  constructor(name: string, field: string, value: number) {
+    super('match', `is_equal_${field}_${toCacheKey(value)}`, name, field,
+      value);
+  }
+}
diff --git a/llparse-frontend/src/code/load.ts b/llparse-frontend/src/code/load.ts
new file mode 100644
index 0000000..76b715a
--- /dev/null
+++ b/llparse-frontend/src/code/load.ts
@@ -0,0 +1,7 @@
+import { Field } from './field';
+
+export class Load extends Field {
+  constructor(name: string, field: string) {
+    super('match', `load_${field}`, name, field);
+  }
+}
diff --git a/llparse-frontend/src/code/match.ts b/llparse-frontend/src/code/match.ts
new file mode 100644
index 0000000..819d2af
--- /dev/null
+++ b/llparse-frontend/src/code/match.ts
@@ -0,0 +1,7 @@
+import { External } from './external';
+
+export class Match extends External {
+  constructor(name: string) {
+    super('match', name);
+  }
+}
diff --git a/llparse-frontend/src/code/mul-add.ts b/llparse-frontend/src/code/mul-add.ts
new file mode 100644
index 0000000..c99be0d
--- /dev/null
+++ b/llparse-frontend/src/code/mul-add.ts
@@ -0,0 +1,26 @@
+import { toCacheKey } from '../utils';
+import { Field } from './field';
+
+export interface IMulAddOptions {
+  readonly base: number;
+  readonly max?: number;
+  readonly signed: boolean;
+}
+
+function toOptionsKey(options: IMulAddOptions): string {
+  let res = `base_${toCacheKey(options.base)}`;
+  if (options.max !== undefined) {
+    res += `_max_${toCacheKey(options.max)}`;
+  }
+  if (options.signed !== undefined) {
+    res += `_signed_${toCacheKey(options.signed)}`;
+  }
+  return res;
+}
+
+export class MulAdd extends Field {
+  constructor(name: string, field: string,
+              public readonly options: IMulAddOptions) {
+    super('value', `mul_add_${field}_${toOptionsKey(options)}`, name, field);
+  }
+}
diff --git a/llparse-frontend/src/code/or.ts b/llparse-frontend/src/code/or.ts
new file mode 100644
index 0000000..2328a9f
--- /dev/null
+++ b/llparse-frontend/src/code/or.ts
@@ -0,0 +1,8 @@
+import { toCacheKey } from '../utils';
+import { FieldValue } from './field-value';
+
+export class Or extends FieldValue {
+  constructor(name: string, field: string, value: number) {
+    super('match', `or_${field}_${toCacheKey(value)}`, name, field, value);
+  }
+}
diff --git a/llparse-frontend/src/code/span.ts b/llparse-frontend/src/code/span.ts
new file mode 100644
index 0000000..6241e03
--- /dev/null
+++ b/llparse-frontend/src/code/span.ts
@@ -0,0 +1,7 @@
+import { External } from './external';
+
+export class Span extends External {
+  constructor(name: string) {
+    super('span', name);
+  }
+}
diff --git a/llparse-frontend/src/code/store.ts b/llparse-frontend/src/code/store.ts
new file mode 100644
index 0000000..c2cb9ea
--- /dev/null
+++ b/llparse-frontend/src/code/store.ts
@@ -0,0 +1,7 @@
+import { Field } from './field';
+
+export class Store extends Field {
+  constructor(name: string, field: string) {
+    super('value', `store_${field}`, name, field);
+  }
+}
diff --git a/llparse-frontend/src/code/test.ts b/llparse-frontend/src/code/test.ts
new file mode 100644
index 0000000..21339e9
--- /dev/null
+++ b/llparse-frontend/src/code/test.ts
@@ -0,0 +1,8 @@
+import { toCacheKey } from '../utils';
+import { FieldValue } from './field-value';
+
+export class Test extends FieldValue {
+  constructor(name: string, field: string, value: number) {
+    super('match', `test_${field}_${toCacheKey(value)}`, name, field, value);
+  }
+}
diff --git a/llparse-frontend/src/code/update.ts b/llparse-frontend/src/code/update.ts
new file mode 100644
index 0000000..5fa5eec
--- /dev/null
+++ b/llparse-frontend/src/code/update.ts
@@ -0,0 +1,8 @@
+import { toCacheKey } from '../utils';
+import { FieldValue } from './field-value';
+
+export class Update extends FieldValue {
+  constructor(name: string, field: string, value: number) {
+    super('match', `update_${field}_${toCacheKey(value)}`, name, field, value);
+  }
+}
diff --git a/llparse-frontend/src/code/value.ts b/llparse-frontend/src/code/value.ts
new file mode 100644
index 0000000..4f32ae8
--- /dev/null
+++ b/llparse-frontend/src/code/value.ts
@@ -0,0 +1,7 @@
+import { External } from './external';
+
+export class Value extends External {
+  constructor(name: string) {
+    super('value', name);
+  }
+}
diff --git a/llparse-frontend/src/container/index.ts b/llparse-frontend/src/container/index.ts
new file mode 100644
index 0000000..a62aac8
--- /dev/null
+++ b/llparse-frontend/src/container/index.ts
@@ -0,0 +1,84 @@
+import * as assert from 'assert';
+
+import { ICodeImplementation } from '../implementation/code';
+import { IImplementation } from '../implementation/full';
+import { INodeImplementation } from '../implementation/node';
+import { ITransformImplementation } from '../implementation/transform';
+import { IWrap } from '../wrap';
+import { ContainerWrap } from './wrap';
+
+export { ContainerWrap };
+
+export class Container {
+  private readonly map: Map<string, IImplementation> = new Map();
+
+  public add(key: string, impl: IImplementation): void {
+    assert(!this.map.has(key), `Duplicate implementation key: "${key}"`);
+    this.map.set(key, impl);
+  }
+
+  public build(): IImplementation {
+    return {
+      code: this.buildCode(),
+      node: this.buildNode(),
+      transform: this.buildTransform(),
+    };
+  }
+
+  public buildCode(): ICodeImplementation {
+    return {
+      And: this.combine((impl) => impl.code.And),
+      IsEqual: this.combine((impl) => impl.code.IsEqual),
+      Load: this.combine((impl) => impl.code.Load),
+      Match: this.combine((impl) => impl.code.Match),
+      MulAdd: this.combine((impl) => impl.code.MulAdd),
+      Or: this.combine((impl) => impl.code.Or),
+      Span: this.combine((impl) => impl.code.Span),
+      Store: this.combine((impl) => impl.code.Store),
+      Test: this.combine((impl) => impl.code.Test),
+      Update: this.combine((impl) => impl.code.Update),
+      Value: this.combine((impl) => impl.code.Value),
+    };
+  }
+
+  public buildNode(): INodeImplementation {
+    return {
+      Consume: this.combine((impl) => impl.node.Consume),
+      Empty: this.combine((impl) => impl.node.Empty),
+      Error: this.combine((impl) => impl.node.Error),
+      Invoke: this.combine((impl) => impl.node.Invoke),
+      Pause: this.combine((impl) => impl.node.Pause),
+      Sequence: this.combine((impl) => impl.node.Sequence),
+      Single: this.combine((impl) => impl.node.Single),
+      SpanEnd: this.combine((impl) => impl.node.SpanEnd),
+      SpanStart: this.combine((impl) => impl.node.SpanStart),
+      TableLookup: this.combine((impl) => impl.node.TableLookup),
+    };
+  }
+
+  public buildTransform(): ITransformImplementation {
+    return {
+      ID: this.combine((impl) => impl.transform.ID),
+      ToLower: this.combine((impl) => impl.transform.ToLower),
+      ToLowerUnsafe: this.combine((impl) => impl.transform.ToLowerUnsafe),
+    };
+  }
+
+  private combine<T>(gather: (impl: IImplementation) => new(n: T) => IWrap<T>)
+    : new(n: T) => ContainerWrap<T> {
+    const wraps: Map<string, new(n: T) => IWrap<T>> = new Map();
+    for (const [ key, impl ] of this.map) {
+      wraps.set(key, gather(impl));
+    }
+
+    return class ContainerWrapSingle extends ContainerWrap<T> {
+      constructor(ref: T) {
+        super(ref);
+
+        for (const [ key, impl ] of wraps) {
+          this.map.set(key, new impl(ref));
+        }
+      }
+    };
+  }
+}
diff --git a/llparse-frontend/src/container/wrap.ts b/llparse-frontend/src/container/wrap.ts
new file mode 100644
index 0000000..f3b886c
--- /dev/null
+++ b/llparse-frontend/src/container/wrap.ts
@@ -0,0 +1,15 @@
+import * as assert from 'assert';
+
+import { IWrap } from '../wrap';
+
+export class ContainerWrap<T> {
+  protected readonly map: Map<string, IWrap<T>> = new Map();
+
+  constructor(public readonly ref: T) {
+  }
+
+  public get<R extends IWrap<T>>(key: string): R {
+    assert(this.map.has(key), `Unknown implementation key "${key}"`);
+    return this.map.get(key)! as R;
+  }
+}
diff --git a/llparse-frontend/src/enumerator.ts b/llparse-frontend/src/enumerator.ts
new file mode 100644
index 0000000..f2940a2
--- /dev/null
+++ b/llparse-frontend/src/enumerator.ts
@@ -0,0 +1,23 @@
+import { Node } from './node';
+import { IWrap } from './wrap';
+
+export class Enumerator {
+  public getAllNodes(root: IWrap<Node>): ReadonlyArray<IWrap<Node>> {
+    const nodes: Set<IWrap<Node>> = new Set();
+    const queue = [ root ];
+
+    while (queue.length !== 0) {
+      const node = queue.pop()!;
+      for (const slot of node.ref.getSlots()) {
+        if (nodes.has(slot.node)) {
+          continue;
+        }
+
+        nodes.add(slot.node);
+        queue.push(slot.node);
+      }
+    }
+
+    return Array.from(nodes);
+  }
+}
diff --git a/llparse-frontend/src/frontend.ts b/llparse-frontend/src/frontend.ts
new file mode 100644
index 0000000..91c5224
--- /dev/null
+++ b/llparse-frontend/src/frontend.ts
@@ -0,0 +1,513 @@
+import * as assert from 'assert';
+import * as debugAPI from 'debug';
+import * as source from 'llparse-builder';
+
+import * as frontend from './namespace/frontend';
+import { Container, ContainerWrap } from './container';
+import { IImplementation } from './implementation';
+import { SpanField } from './span-field';
+import { Trie, TrieEmpty, TrieNode, TrieSequence, TrieSingle } from './trie';
+import { Identifier, IUniqueName } from './utils';
+import { IWrap } from './wrap';
+import { Enumerator } from './enumerator';
+import { Peephole } from './peephole';
+
+const debug = debugAPI('llparse:translator');
+
+export { code, node, transform } from './namespace/frontend';
+
+export {
+  source,
+  Identifier,
+  IUniqueName,
+  IWrap,
+  SpanField,
+  Container,
+  ContainerWrap,
+};
+
+// Minimum number of cases of `single` node to make it eligable for
+// `TableLookup` optimization
+export const DEFAULT_MIN_TABLE_SIZE = 32;
+
+// Maximum width of entry in a table for a `TableLookup` optimization
+export const DEFAULT_MAX_TABLE_WIDTH = 4;
+
+type WrappedNode = IWrap<frontend.node.Node>;
+type WrappedCode = IWrap<frontend.code.Code>;
+
+export interface IFrontendLazyOptions {
+  readonly maxTableElemWidth?: number;
+  readonly minTableSize?: number;
+}
+
+export interface IFrontendResult {
+  readonly prefix: string;
+  readonly properties: ReadonlyArray<source.Property>;
+  readonly root: IWrap<frontend.node.Node>;
+  readonly spans: ReadonlyArray<SpanField>;
+  readonly resumptionTargets: ReadonlySet<WrappedNode>;
+}
+
+interface IFrontendOptions {
+  readonly maxTableElemWidth: number;
+  readonly minTableSize: number;
+}
+
+type MatchChildren = WrappedNode[];
+type MatchResult = WrappedNode | ReadonlyArray<WrappedNode>;
+
+interface ITableLookupTarget {
+  readonly keys: number[];
+  readonly noAdvance: boolean;
+  readonly trie: TrieEmpty;
+}
+
+export class Frontend {
+  private readonly options: IFrontendOptions;
+
+  private readonly id: Identifier = new Identifier(this.prefix + '__n_');
+  private readonly codeId: Identifier = new Identifier(this.prefix + '__c_');
+  private readonly map: Map<source.node.Node, WrappedNode> = new Map();
+  private readonly spanMap: Map<source.Span, SpanField> = new Map();
+  private readonly codeCache: Map<string, WrappedCode> = new Map();
+  private readonly resumptionTargets: Set<WrappedNode> = new Set();
+
+  constructor(private readonly prefix: string,
+              private readonly implementation: IImplementation,
+              options: IFrontendLazyOptions = {}) {
+    this.options = {
+      maxTableElemWidth: options.maxTableElemWidth === undefined ?
+        DEFAULT_MAX_TABLE_WIDTH : options.maxTableElemWidth,
+      minTableSize: options.minTableSize === undefined ?
+        DEFAULT_MIN_TABLE_SIZE : options.minTableSize,
+    };
+
+    assert(0 < this.options.maxTableElemWidth,
+      'Invalid `options.maxTableElemWidth`, must be positive');
+  }
+
+  public compile(root: source.node.Node,
+                 properties: ReadonlyArray<source.Property>): IFrontendResult {
+    debug('checking loops');
+    const lc = new source.LoopChecker();
+    lc.check(root);
+
+    debug('allocating spans');
+    const spanAllocator = new source.SpanAllocator();
+    const sourceSpans = spanAllocator.allocate(root);
+
+    const spans = sourceSpans.concurrency.map((concurrent, index) => {
+      const span = new SpanField(index, concurrent.map((sourceSpan) => {
+        return this.translateSpanCode(sourceSpan.callback);
+      }));
+
+      for (const sourceSpan of concurrent) {
+        this.spanMap.set(sourceSpan, span);
+      }
+
+      return span;
+    });
+
+    debug('translating');
+    let out = this.translate(root);
+
+    debug('enumerating');
+    const enumerator = new Enumerator();
+    let nodes = enumerator.getAllNodes(out);
+
+    debug('peephole optimization');
+    const peephole = new Peephole();
+    out = peephole.optimize(out, nodes);
+
+    debug('re-enumerating');
+    nodes = enumerator.getAllNodes(out);
+
+    debug('registering resumption targets');
+    this.resumptionTargets.add(out);
+    for (const node of nodes) {
+      this.registerNode(node);
+    }
+
+    return {
+      prefix: this.prefix,
+      properties,
+      resumptionTargets: this.resumptionTargets,
+      root: out,
+      spans,
+    };
+  }
+
+  // TODO(indutny): remove this in the next major release
+  public getResumptionTargets(): ReadonlySet<WrappedNode> {
+    return this.resumptionTargets;
+  }
+
+  private translate(node: source.node.Node): WrappedNode {
+    if (this.map.has(node)) {
+      return this.map.get(node)!;
+    }
+
+    const id = () => this.id.id(node.name);
+
+    const nodeImpl = this.implementation.node;
+
+    // Instantiate target class
+    let result: MatchResult;
+    if (node instanceof source.node.Error) {
+      result = new nodeImpl.Error(
+        new frontend.node.Error(id(), node.code, node.reason));
+    } else if (node instanceof source.node.Pause) {
+      result = new nodeImpl.Pause(
+        new frontend.node.Pause(id(), node.code, node.reason));
+    } else if (node instanceof source.node.Consume) {
+      result = new nodeImpl.Consume(
+        new frontend.node.Consume(id(), node.field));
+    } else if (node instanceof source.node.SpanStart) {
+      result = new nodeImpl.SpanStart(
+        new frontend.node.SpanStart(id(), this.spanMap.get(node.span)!,
+          this.translateSpanCode(node.span.callback)));
+    } else if (node instanceof source.node.SpanEnd) {
+      result = new nodeImpl.SpanEnd(
+        new frontend.node.SpanEnd(id(), this.spanMap.get(node.span)!,
+          this.translateSpanCode(node.span.callback)));
+    } else if (node instanceof source.node.Invoke) {
+      assert(node.code.signature === 'match' || node.code.signature === 'value',
+          'Passing `span` callback to `invoke` is not allowed');
+      result = new nodeImpl.Invoke(
+        new frontend.node.Invoke(id(), this.translateCode(node.code)));
+    } else if (node instanceof source.node.Match) {
+      result = this.translateMatch(node);
+    } else {
+      throw new Error(`Unknown node type for "${node.name}" ${node.constructor.toString()}`);
+    }
+
+    // Initialize result
+    const otherwise = node.getOtherwiseEdge();
+
+    if (Array.isArray(result)) {
+      assert(node instanceof source.node.Match);
+      const match = node as source.node.Match;
+
+      // TODO(indutny): move this to llparse-builder?
+      assert.notStrictEqual(otherwise, undefined,
+        `Node "${node.name}" has no \`.otherwise()\``);
+
+      // Assign otherwise to every node of Trie
+      if (otherwise !== undefined) {
+        for (const child of result) {
+          if (!child.ref.otherwise) {
+            child.ref.setOtherwise(this.translate(otherwise.node),
+              otherwise.noAdvance);
+          }
+        }
+      }
+
+      // Assign transform to every node of Trie
+      const transform = this.translateTransform(match.getTransform());
+      for (const child of result) {
+        child.ref.setTransform(transform);
+      }
+
+      assert(result.length >= 1);
+      return result[0];
+    } else {
+      const single: WrappedNode = result as WrappedNode;
+      assert(single.ref instanceof frontend.node.Node);
+
+      // Break loops
+      this.map.set(node, single);
+
+      if (otherwise !== undefined) {
+        single.ref.setOtherwise(this.translate(otherwise.node),
+          otherwise.noAdvance);
+      } else {
+        // TODO(indutny): move this to llparse-builder?
+        assert(node instanceof source.node.Error,
+          `Node "${node.name}" has no \`.otherwise()\``);
+      }
+
+      if (single.ref instanceof frontend.node.Invoke) {
+        for (const edge of node) {
+          single.ref.addEdge(edge.key as number, this.translate(edge.node));
+        }
+      } else {
+        assert.strictEqual(Array.from(node).length, 0);
+      }
+
+      return single;
+    }
+  }
+
+  private registerNode(node: any): void {
+    const nodeImpl = this.implementation.node;
+
+    // Nodes with prologue check (start_pos != end_pos)
+    if (node instanceof nodeImpl.Consume ||
+        node instanceof nodeImpl.Empty ||
+        node instanceof nodeImpl.Sequence ||
+        node instanceof nodeImpl.Single ||
+        node instanceof nodeImpl.SpanStart ||
+        node instanceof nodeImpl.TableLookup) {
+      this.resumptionTargets.add(node);
+
+    // Nodes that can interrupt the execution to be resumed at different node
+    } else if (node instanceof nodeImpl.Pause ||
+               node instanceof nodeImpl.SpanEnd) {
+      this.resumptionTargets.add(node.ref.otherwise!.node);
+    }
+  }
+
+  private translateMatch(node: source.node.Match): MatchResult {
+    const trie = new Trie(node.name);
+
+    const otherwise = node.getOtherwiseEdge();
+    const trieNode = trie.build(Array.from(node));
+    if (trieNode === undefined) {
+      return new this.implementation.node.Empty(
+        new frontend.node.Empty(this.id.id(node.name)));
+    }
+
+    const children: MatchChildren = [];
+    this.translateTrie(node, trieNode, children);
+    assert(children.length >= 1);
+
+    return children;
+  }
+
+  private translateTrie(node: source.node.Match, trie: TrieNode,
+                        children: MatchChildren): WrappedNode {
+    if (trie instanceof TrieEmpty) {
+      assert(this.map.has(node));
+      return this.translate(trie.node);
+    } else if (trie instanceof TrieSingle) {
+      return this.translateSingle(node, trie, children);
+    } else if (trie instanceof TrieSequence) {
+      return this.translateSequence(node, trie, children);
+    } else {
+      throw new Error('Unknown trie node');
+    }
+  }
+
+  private translateSingle(node: source.node.Match, trie: TrieSingle,
+                          children: MatchChildren)
+    : IWrap<frontend.node.Match> {
+    // See if we can apply TableLookup optimization
+    const maybeTable = this.maybeTableLookup(node, trie, children);
+    if (maybeTable !== undefined) {
+      return maybeTable;
+    }
+
+    const single = new this.implementation.node.Single(
+        new frontend.node.Single(this.id.id(node.name)));
+    children.push(single);
+
+    // Break the loop
+    if (!this.map.has(node)) {
+      this.map.set(node, single);
+    }
+    for (const child of trie.children) {
+      const childNode = this.translateTrie(node, child.node, children);
+
+      single.ref.addEdge({
+        key: child.key,
+        noAdvance: child.noAdvance,
+        node: childNode,
+        value: child.node instanceof TrieEmpty ? child.node.value : undefined,
+      });
+    }
+
+    const otherwise = trie.otherwise;
+    if (otherwise) {
+      single.ref.setOtherwise(
+        this.translateTrie(node, otherwise, children),
+        true,
+        otherwise.value);
+    }
+
+    return single;
+  }
+
+  private maybeTableLookup(node: source.node.Match, trie: TrieSingle,
+                           children: MatchChildren)
+    : IWrap<frontend.node.Match> | undefined {
+    if (trie.children.length < this.options.minTableSize) {
+      debug('not enough children of "%s" to allocate table, got %d need %d',
+        node.name, trie.children.length, this.options.minTableSize);
+      return undefined;
+    }
+
+    const targets: Map<source.node.Node, ITableLookupTarget> = new Map();
+
+    const bailout = !trie.children.every((child) => {
+      if (!(child.node instanceof TrieEmpty)) {
+        debug('non-leaf trie child of "%s" prevents table allocation',
+          node.name);
+        return false;
+      }
+
+      const empty: TrieEmpty = child.node;
+
+      // We can't pass values from the table yet
+      if (empty.value !== undefined) {
+        debug('value passing trie leaf of "%s" prevents table allocation',
+          node.name);
+        return false;
+      }
+
+      const target = empty.node;
+      if (!targets.has(target)) {
+        targets.set(target, {
+          keys: [ child.key ],
+          noAdvance: child.noAdvance,
+          trie: empty,
+        });
+        return true;
+      }
+
+      const existing = targets.get(target)!;
+
+      // TODO(indutny): just use it as a sub-key?
+      if (existing.noAdvance !== child.noAdvance) {
+        debug(
+          'noAdvance mismatch in a trie leaf of "%s" prevents ' +
+            'table allocation',
+          node.name);
+        return false;
+      }
+
+      existing.keys.push(child.key);
+      return true;
+    });
+
+    if (bailout) {
+      return undefined;
+    }
+
+    // We've width limit for this optimization
+    if (targets.size >= (1 << this.options.maxTableElemWidth)) {
+      debug('too many different trie targets of "%s" for a table allocation',
+        node.name);
+      return undefined;
+    }
+
+    const table = new this.implementation.node.TableLookup(
+        new frontend.node.TableLookup(this.id.id(node.name)));
+    children.push(table);
+
+    // Break the loop
+    if (!this.map.has(node)) {
+      this.map.set(node, table);
+    }
+
+    targets.forEach((target) => {
+      const next = this.translateTrie(node, target.trie, children);
+
+      table.ref.addEdge({
+        keys: target.keys,
+        noAdvance: target.noAdvance,
+        node: next,
+      });
+    });
+
+    debug('optimized "%s" to a table lookup node', node.name);
+    return table;
+  }
+
+  private translateSequence(node: source.node.Match, trie: TrieSequence,
+                            children: MatchChildren)
+    : IWrap<frontend.node.Match> {
+    const sequence = new this.implementation.node.Sequence(
+        new frontend.node.Sequence(this.id.id(node.name), trie.select));
+    children.push(sequence);
+
+    // Break the loop
+    if (!this.map.has(node)) {
+      this.map.set(node, sequence);
+    }
+
+    const childNode = this.translateTrie(node, trie.child, children);
+
+    const value = trie.child instanceof TrieEmpty ?
+      trie.child.value : undefined;
+
+    sequence.ref.setEdge(childNode, value);
+
+    return sequence;
+  }
+
+  private translateCode(code: source.code.Code): WrappedCode {
+    const prefixed = this.codeId.id(code.name).name;
+    const codeImpl = this.implementation.code;
+
+    let res: WrappedCode;
+    if (code instanceof source.code.IsEqual) {
+      res = new codeImpl.IsEqual(
+        new frontend.code.IsEqual(prefixed, code.field, code.value));
+    } else if (code instanceof source.code.Load) {
+      res = new codeImpl.Load(
+        new frontend.code.Load(prefixed, code.field));
+    } else if (code instanceof source.code.MulAdd) {
+      // TODO(indutny): verify property type
+      const m = new frontend.code.MulAdd(prefixed, code.field, {
+        base: code.options.base,
+        max: code.options.max,
+        signed: code.options.signed === undefined ? true : code.options.signed,
+      });
+      res = new codeImpl.MulAdd(m);
+    } else if (code instanceof source.code.And) {
+      res = new codeImpl.And(
+        new frontend.code.Or(prefixed, code.field, code.value));
+    } else if (code instanceof source.code.Or) {
+      res = new codeImpl.Or(
+        new frontend.code.Or(prefixed, code.field, code.value));
+    } else if (code instanceof source.code.Store) {
+      res = new codeImpl.Store(
+        new frontend.code.Store(prefixed, code.field));
+    } else if (code instanceof source.code.Test) {
+      res = new codeImpl.Test(
+        new frontend.code.Test(prefixed, code.field, code.value));
+    } else if (code instanceof source.code.Update) {
+      res = new codeImpl.Update(
+        new frontend.code.Update(prefixed, code.field, code.value));
+
+    // External callbacks
+    } else if (code instanceof source.code.Span) {
+      res = new codeImpl.Span(new frontend.code.Span(code.name));
+    } else if (code instanceof source.code.Match) {
+      res = new codeImpl.Match(new frontend.code.Match(code.name));
+    } else if (code instanceof source.code.Value) {
+      res = new codeImpl.Value(new frontend.code.Value(code.name));
+    } else {
+      throw new Error(`Unsupported code: "${code.name}"`);
+    }
+
+    // Re-use instances to build them just once
+    if (this.codeCache.has(res.ref.cacheKey)) {
+      return this.codeCache.get(res.ref.cacheKey)!;
+    }
+
+    this.codeCache.set(res.ref.cacheKey, res);
+    return res;
+  }
+
+  private translateSpanCode(code: source.code.Span): IWrap<frontend.code.Span> {
+    return this.translateCode(code) as IWrap<frontend.code.Span>;
+  }
+
+  private translateTransform(transform?: source.transform.Transform)
+    : IWrap<frontend.transform.Transform> {
+    const transformImpl = this.implementation.transform;
+    if (transform === undefined) {
+      return new transformImpl.ID(new frontend.transform.ID());
+    } else if (transform.name === 'to_lower') {
+      return new transformImpl.ToLower(
+        new frontend.transform.ToLower());
+    } else if (transform.name === 'to_lower_unsafe') {
+      return new transformImpl.ToLowerUnsafe(
+        new frontend.transform.ToLowerUnsafe());
+    } else {
+      throw new Error(`Unsupported transform: "${transform.name}"`);
+    }
+  }
+}
diff --git a/llparse-frontend/src/implementation/code.ts b/llparse-frontend/src/implementation/code.ts
new file mode 100644
index 0000000..c467ced
--- /dev/null
+++ b/llparse-frontend/src/implementation/code.ts
@@ -0,0 +1,16 @@
+import * as code from '../code';
+import { IWrap } from '../wrap';
+
+export interface ICodeImplementation {
+  readonly And: new(c: code.And) => IWrap<code.And>;
+  readonly IsEqual: new(c: code.IsEqual) => IWrap<code.IsEqual>;
+  readonly Load: new(c: code.Load) => IWrap<code.Load>;
+  readonly Match: new(c: code.Match) => IWrap<code.Match>;
+  readonly MulAdd: new(c: code.MulAdd) => IWrap<code.MulAdd>;
+  readonly Or: new(c: code.Or) => IWrap<code.Or>;
+  readonly Span: new(c: code.Span) => IWrap<code.Span>;
+  readonly Store: new(c: code.Store) => IWrap<code.Store>;
+  readonly Test: new(c: code.Test) => IWrap<code.Test>;
+  readonly Update: new(c: code.Update) => IWrap<code.Update>;
+  readonly Value: new(c: code.Value) => IWrap<code.Value>;
+}
diff --git a/llparse-frontend/src/implementation/full.ts b/llparse-frontend/src/implementation/full.ts
new file mode 100644
index 0000000..08c4c03
--- /dev/null
+++ b/llparse-frontend/src/implementation/full.ts
@@ -0,0 +1,9 @@
+import { ICodeImplementation } from './code';
+import { INodeImplementation } from './node';
+import { ITransformImplementation } from './transform';
+
+export interface IImplementation {
+  readonly code: ICodeImplementation;
+  readonly node: INodeImplementation;
+  readonly transform: ITransformImplementation;
+}
diff --git a/llparse-frontend/src/implementation/index.ts b/llparse-frontend/src/implementation/index.ts
new file mode 100644
index 0000000..2b5411b
--- /dev/null
+++ b/llparse-frontend/src/implementation/index.ts
@@ -0,0 +1,4 @@
+export * from './code';
+export * from './full';
+export * from './node';
+export * from './transform';
diff --git a/llparse-frontend/src/implementation/node.ts b/llparse-frontend/src/implementation/node.ts
new file mode 100644
index 0000000..af0b3df
--- /dev/null
+++ b/llparse-frontend/src/implementation/node.ts
@@ -0,0 +1,15 @@
+import * as node from '../node';
+import { IWrap } from '../wrap';
+
+export interface INodeImplementation {
+  readonly Consume: new(n: node.Consume) => IWrap<node.Consume>;
+  readonly Empty: new(n: node.Empty) => IWrap<node.Empty>;
+  readonly Error: new(n: node.Error) => IWrap<node.Error>;
+  readonly Invoke: new(n: node.Invoke) => IWrap<node.Invoke>;
+  readonly Pause: new(n: node.Pause) => IWrap<node.Pause>;
+  readonly Sequence: new(n: node.Sequence) => IWrap<node.Sequence>;
+  readonly Single: new(n: node.Single) => IWrap<node.Single>;
+  readonly SpanEnd: new(n: node.SpanEnd) => IWrap<node.SpanEnd>;
+  readonly SpanStart: new(n: node.SpanStart) => IWrap<node.SpanStart>;
+  readonly TableLookup: new(n: node.TableLookup) => IWrap<node.TableLookup>;
+}
diff --git a/llparse-frontend/src/implementation/transform.ts b/llparse-frontend/src/implementation/transform.ts
new file mode 100644
index 0000000..4382284
--- /dev/null
+++ b/llparse-frontend/src/implementation/transform.ts
@@ -0,0 +1,9 @@
+import * as transform from '../transform';
+import { IWrap } from '../wrap';
+
+export interface ITransformImplementation {
+  readonly ID: new(t: transform.ID) => IWrap<transform.ID>;
+  readonly ToLower: new(t: transform.ToLower) => IWrap<transform.ToLower>;
+  readonly ToLowerUnsafe: new(t: transform.ToLowerUnsafe)
+    => IWrap<transform.ToLowerUnsafe>;
+}
diff --git a/llparse-frontend/src/namespace/frontend.ts b/llparse-frontend/src/namespace/frontend.ts
new file mode 100644
index 0000000..2f89093
--- /dev/null
+++ b/llparse-frontend/src/namespace/frontend.ts
@@ -0,0 +1,5 @@
+import * as code from '../code';
+import * as node from '../node';
+import * as transform from '../transform';
+
+export { code, node, transform };
diff --git a/llparse-frontend/src/node/base.ts b/llparse-frontend/src/node/base.ts
new file mode 100644
index 0000000..1e93c49
--- /dev/null
+++ b/llparse-frontend/src/node/base.ts
@@ -0,0 +1,46 @@
+import { IUniqueName } from '../utils';
+import { IWrap } from '../wrap';
+import { Slot } from './slot';
+
+export interface IReadonlyOtherwiseEdge {
+  readonly node: IWrap<Node>;
+  readonly noAdvance: boolean;
+  readonly value: number | undefined;
+}
+
+interface IOtherwiseEdge {
+  node: IWrap<Node>;
+  readonly noAdvance: boolean;
+  readonly value: number | undefined;
+}
+
+export abstract class Node {
+  private privOtherwise: IOtherwiseEdge | undefined;
+  private privSlots: ReadonlyArray<Slot> | undefined;
+
+  constructor(public readonly id: IUniqueName) {
+  }
+
+  public setOtherwise(node: IWrap<Node>, noAdvance: boolean, value?: number) {
+    this.privOtherwise = { node, noAdvance, value };
+  }
+
+  public get otherwise(): IReadonlyOtherwiseEdge | undefined {
+    return this.privOtherwise;
+  }
+
+  public *getSlots() {
+    if (this.privSlots === undefined) {
+      this.privSlots = Array.from(this.buildSlots());
+    }
+
+    yield* this.privSlots;
+  }
+
+  protected *buildSlots() {
+    const otherwise = this.privOtherwise;
+    if (otherwise !== undefined) {
+      yield new Slot(otherwise.node, (value) => otherwise.node = value);
+    }
+  }
+}
diff --git a/llparse-frontend/src/node/consume.ts b/llparse-frontend/src/node/consume.ts
new file mode 100644
index 0000000..6ab49ac
--- /dev/null
+++ b/llparse-frontend/src/node/consume.ts
@@ -0,0 +1,8 @@
+import { IUniqueName } from '../utils';
+import { Node } from './base';
+
+export class Consume extends Node {
+  constructor(id: IUniqueName, readonly field: string) {
+    super(id);
+  }
+}
diff --git a/llparse-frontend/src/node/empty.ts b/llparse-frontend/src/node/empty.ts
new file mode 100644
index 0000000..45c552c
--- /dev/null
+++ b/llparse-frontend/src/node/empty.ts
@@ -0,0 +1,4 @@
+import { Node } from './base';
+
+export class Empty extends Node {
+}
diff --git a/llparse-frontend/src/node/error.ts b/llparse-frontend/src/node/error.ts
new file mode 100644
index 0000000..c4e6faf
--- /dev/null
+++ b/llparse-frontend/src/node/error.ts
@@ -0,0 +1,9 @@
+import { IUniqueName } from '../utils';
+import { Node } from './base';
+
+export class Error extends Node {
+  constructor(id: IUniqueName, public readonly code: number,
+              public readonly reason: string) {
+    super(id);
+  }
+}
diff --git a/llparse-frontend/src/node/index.ts b/llparse-frontend/src/node/index.ts
new file mode 100644
index 0000000..bd11015
--- /dev/null
+++ b/llparse-frontend/src/node/index.ts
@@ -0,0 +1,13 @@
+export * from './base';
+export * from './consume';
+export * from './empty';
+export * from './error';
+export * from './invoke';
+export * from './match';
+export * from './pause';
+export * from './sequence';
+export * from './single';
+export * from './slot';
+export * from './span-end';
+export * from './span-start';
+export * from './table-lookup';
diff --git a/llparse-frontend/src/node/invoke.ts b/llparse-frontend/src/node/invoke.ts
new file mode 100644
index 0000000..ba6ef53
--- /dev/null
+++ b/llparse-frontend/src/node/invoke.ts
@@ -0,0 +1,39 @@
+import { Code } from '../code';
+import { IUniqueName } from '../utils';
+import { IWrap } from '../wrap';
+import { Node } from './base';
+import { Slot } from './slot';
+
+interface IInvokeEdge {
+  readonly code: number;
+  node: IWrap<Node>;
+}
+
+export interface IReadonlyInvokeEdge {
+  readonly code: number;
+  readonly node: IWrap<Node>;
+}
+
+export class Invoke extends Node {
+  private readonly privEdges: IInvokeEdge[] = [];
+
+  constructor(id: IUniqueName, public readonly code: IWrap<Code>) {
+    super(id);
+  }
+
+  public addEdge(code: number, node: IWrap<Node>): void {
+    this.privEdges.push({ code, node });
+  }
+
+  public get edges(): ReadonlyArray<IReadonlyInvokeEdge> {
+    return this.privEdges;
+  }
+
+  protected *buildSlots() {
+    for (const edge of this.privEdges) {
+      yield new Slot(edge.node, (value) => edge.node = value);
+    }
+
+    yield* super.buildSlots();
+  }
+}
diff --git a/llparse-frontend/src/node/match.ts b/llparse-frontend/src/node/match.ts
new file mode 100644
index 0000000..8a499d3
--- /dev/null
+++ b/llparse-frontend/src/node/match.ts
@@ -0,0 +1,11 @@
+import { Transform } from '../transform';
+import { IWrap } from '../wrap';
+import { Node } from './base';
+
+export class Match extends Node {
+  public transform?: IWrap<Transform>;
+
+  public setTransform(transform: IWrap<Transform>): void {
+    this.transform = transform;
+  }
+}
diff --git a/llparse-frontend/src/node/pause.ts b/llparse-frontend/src/node/pause.ts
new file mode 100644
index 0000000..b9923d7
--- /dev/null
+++ b/llparse-frontend/src/node/pause.ts
@@ -0,0 +1,4 @@
+import { Error as ErrorNode } from './error';
+
+export class Pause extends ErrorNode {
+}
diff --git a/llparse-frontend/src/node/sequence.ts b/llparse-frontend/src/node/sequence.ts
new file mode 100644
index 0000000..c9105b3
--- /dev/null
+++ b/llparse-frontend/src/node/sequence.ts
@@ -0,0 +1,44 @@
+import * as assert from 'assert';
+import { Buffer } from 'buffer';
+
+import { IUniqueName } from '../utils';
+import { IWrap } from '../wrap';
+import { Node } from './base';
+import { Match } from './match';
+import { Slot } from './slot';
+
+interface ISequenceEdge {
+  node: IWrap<Node>;
+  readonly value: number | undefined;
+}
+
+export interface IReadonlySequenceEdge {
+  readonly node: IWrap<Node>;
+  readonly value: number | undefined;
+}
+
+export class Sequence extends Match {
+  private privEdge?: ISequenceEdge;
+
+  constructor(id: IUniqueName, public readonly select: Buffer) {
+    super(id);
+  }
+
+  public setEdge(node: IWrap<Node>, value?: number | undefined) {
+    assert.strictEqual(this.privEdge, undefined);
+    this.privEdge = { node, value };
+  }
+
+  public get edge(): IReadonlySequenceEdge | undefined {
+    return this.privEdge;
+  }
+
+  protected *buildSlots() {
+    const edge = this.privEdge;
+    if (edge !== undefined) {
+      yield new Slot(edge.node, (value) => edge.node = value);
+    }
+
+    yield* super.buildSlots();
+  }
+}
diff --git a/llparse-frontend/src/node/single.ts b/llparse-frontend/src/node/single.ts
new file mode 100644
index 0000000..0acf715
--- /dev/null
+++ b/llparse-frontend/src/node/single.ts
@@ -0,0 +1,46 @@
+import * as assert from 'assert';
+
+import { IUniqueName } from '../utils';
+import { IWrap } from '../wrap';
+import { Node } from './base';
+import { Match } from './match';
+import { Slot } from './slot';
+
+interface ISingleEdge {
+  readonly key: number;
+  node: IWrap<Node>;
+  readonly noAdvance: boolean;
+  readonly value: number | undefined;
+}
+
+export interface IReadonlySingleEdge {
+  readonly key: number;
+  node: IWrap<Node>;
+  readonly noAdvance: boolean;
+  readonly value: number | undefined;
+}
+
+export class Single extends Match {
+  private readonly privEdges: ISingleEdge[] = [];
+
+  public addEdge(edge: IReadonlySingleEdge): void {
+    this.privEdges.push({
+      key: edge.key,
+      noAdvance: edge.noAdvance,
+      node: edge.node,
+      value: edge.value,
+    });
+  }
+
+  public get edges(): ReadonlyArray<IReadonlySingleEdge> {
+    return this.privEdges;
+  }
+
+  protected *buildSlots() {
+    for (const edge of this.privEdges) {
+      yield new Slot(edge.node, (value) => edge.node = value);
+    }
+
+    yield* super.buildSlots();
+  }
+}
diff --git a/llparse-frontend/src/node/slot.ts b/llparse-frontend/src/node/slot.ts
new file mode 100644
index 0000000..923da86
--- /dev/null
+++ b/llparse-frontend/src/node/slot.ts
@@ -0,0 +1,20 @@
+import { IWrap } from '../wrap';
+import { Node } from './base';
+
+export class Slot {
+  private privNode: IWrap<Node>;
+
+  constructor(node: IWrap<Node>,
+              private readonly privUpdate: (value: IWrap<Node>) => void) {
+    this.privNode = node;
+  }
+
+  public get node(): IWrap<Node> {
+    return this.privNode;
+  }
+
+  public set node(value: IWrap<Node>) {
+    this.privNode = value;
+    this.privUpdate(value);
+  }
+}
diff --git a/llparse-frontend/src/node/span-end.ts b/llparse-frontend/src/node/span-end.ts
new file mode 100644
index 0000000..bf8d5cc
--- /dev/null
+++ b/llparse-frontend/src/node/span-end.ts
@@ -0,0 +1,12 @@
+import { Span } from '../code';
+import { SpanField } from '../span-field';
+import { IUniqueName } from '../utils';
+import { IWrap } from '../wrap';
+import { Node } from './base';
+
+export class SpanEnd extends Node {
+  constructor(id: IUniqueName, public readonly field: SpanField,
+              public readonly callback: IWrap<Span>) {
+    super(id);
+  }
+}
diff --git a/llparse-frontend/src/node/span-start.ts b/llparse-frontend/src/node/span-start.ts
new file mode 100644
index 0000000..89690f1
--- /dev/null
+++ b/llparse-frontend/src/node/span-start.ts
@@ -0,0 +1,12 @@
+import { Span } from '../code';
+import { SpanField } from '../span-field';
+import { IUniqueName } from '../utils';
+import { IWrap } from '../wrap';
+import { Node } from './base';
+
+export class SpanStart extends Node {
+  constructor(id: IUniqueName, public readonly field: SpanField,
+              public readonly callback: IWrap<Span>) {
+    super(id);
+  }
+}
diff --git a/llparse-frontend/src/node/table-lookup.ts b/llparse-frontend/src/node/table-lookup.ts
new file mode 100644
index 0000000..9880fc7
--- /dev/null
+++ b/llparse-frontend/src/node/table-lookup.ts
@@ -0,0 +1,43 @@
+import * as assert from 'assert';
+
+import { IUniqueName } from '../utils';
+import { IWrap } from '../wrap';
+import { Node } from './base';
+import { Match } from './match';
+import { Slot } from './slot';
+
+interface ITableEdge {
+  readonly keys: ReadonlyArray<number>;
+  node: IWrap<Node>;
+  readonly noAdvance: boolean;
+}
+
+export interface IReadonlyTableEdge {
+  readonly keys: ReadonlyArray<number>;
+  readonly node: IWrap<Node>;
+  readonly noAdvance: boolean;
+}
+
+export class TableLookup extends Match {
+  private readonly privEdges: ITableEdge[] = [];
+
+  public addEdge(edge: IReadonlyTableEdge): void {
+    this.privEdges.push({
+      keys: edge.keys,
+      noAdvance: edge.noAdvance,
+      node: edge.node,
+    });
+  }
+
+  public get edges(): ReadonlyArray<IReadonlyTableEdge> {
+    return this.privEdges;
+  }
+
+  protected *buildSlots() {
+    for (const edge of this.privEdges) {
+      yield new Slot(edge.node, (value) => edge.node = value);
+    }
+
+    yield* super.buildSlots();
+  }
+}
diff --git a/llparse-frontend/src/peephole.ts b/llparse-frontend/src/peephole.ts
new file mode 100644
index 0000000..19ac13f
--- /dev/null
+++ b/llparse-frontend/src/peephole.ts
@@ -0,0 +1,52 @@
+import { Node, Empty } from './node';
+import { IWrap } from './wrap';
+
+type WrapNode = IWrap<Node>;
+type WrapList = ReadonlyArray<WrapNode>;
+
+export class Peephole {
+  public optimize(root: WrapNode, nodes: WrapList): WrapNode {
+    let changed = new Set(nodes);
+
+    while (changed.size !== 0) {
+      const previous = changed;
+      changed = new Set();
+
+      for (const node of previous) {
+        if (this.optimizeNode(node)) {
+          changed.add(node);
+        }
+      }
+    }
+
+    while (root.ref instanceof Empty) {
+      if (!root.ref.otherwise!.noAdvance) {
+        break;
+      }
+
+      root = root.ref.otherwise!.node;
+    }
+
+    return root;
+  }
+
+  public optimizeNode(node: WrapNode): boolean {
+    let changed = false;
+    for (const slot of node.ref.getSlots()) {
+      if (!(slot.node.ref instanceof Empty)) {
+        continue;
+      }
+
+      const otherwise = slot.node.ref.otherwise!;
+
+      // Node actively skips, can't optimize!
+      if (!otherwise.noAdvance) {
+        continue;
+      }
+
+      slot.node = otherwise.node;
+      changed = true;
+    }
+    return changed;
+  }
+}
diff --git a/llparse-frontend/src/span-field.ts b/llparse-frontend/src/span-field.ts
new file mode 100644
index 0000000..0652f77
--- /dev/null
+++ b/llparse-frontend/src/span-field.ts
@@ -0,0 +1,8 @@
+import { Span } from './code';
+import { IWrap } from './wrap';
+
+export class SpanField {
+  constructor(public readonly index: number,
+              public readonly callbacks: ReadonlyArray<IWrap<Span>>) {
+  }
+}
diff --git a/llparse-frontend/src/transform/base.ts b/llparse-frontend/src/transform/base.ts
new file mode 100644
index 0000000..5397326
--- /dev/null
+++ b/llparse-frontend/src/transform/base.ts
@@ -0,0 +1,4 @@
+export abstract class Transform {
+  constructor(public readonly name: string) {
+  }
+}
diff --git a/llparse-frontend/src/transform/id.ts b/llparse-frontend/src/transform/id.ts
new file mode 100644
index 0000000..d86e3c1
--- /dev/null
+++ b/llparse-frontend/src/transform/id.ts
@@ -0,0 +1,7 @@
+import { Transform } from './base';
+
+export class ID extends Transform {
+  constructor() {
+    super('id');
+  }
+}
diff --git a/llparse-frontend/src/transform/index.ts b/llparse-frontend/src/transform/index.ts
new file mode 100644
index 0000000..f103b3b
--- /dev/null
+++ b/llparse-frontend/src/transform/index.ts
@@ -0,0 +1,4 @@
+export * from './base';
+export * from './id';
+export * from './to-lower';
+export * from './to-lower-unsafe';
diff --git a/llparse-frontend/src/transform/to-lower-unsafe.ts b/llparse-frontend/src/transform/to-lower-unsafe.ts
new file mode 100644
index 0000000..99d9618
--- /dev/null
+++ b/llparse-frontend/src/transform/to-lower-unsafe.ts
@@ -0,0 +1,7 @@
+import { Transform } from './base';
+
+export class ToLowerUnsafe extends Transform {
+  constructor() {
+    super('to_lower_unsafe');
+  }
+}
diff --git a/llparse-frontend/src/transform/to-lower.ts b/llparse-frontend/src/transform/to-lower.ts
new file mode 100644
index 0000000..b333fce
--- /dev/null
+++ b/llparse-frontend/src/transform/to-lower.ts
@@ -0,0 +1,7 @@
+import { Transform } from './base';
+
+export class ToLower extends Transform {
+  constructor() {
+    super('to_lower');
+  }
+}
diff --git a/llparse-frontend/src/trie/empty.ts b/llparse-frontend/src/trie/empty.ts
new file mode 100644
index 0000000..aba52ea
--- /dev/null
+++ b/llparse-frontend/src/trie/empty.ts
@@ -0,0 +1,9 @@
+import { node as api } from 'llparse-builder';
+import { TrieNode } from './node';
+
+export class TrieEmpty extends TrieNode {
+  constructor(public readonly node: api.Node,
+              public readonly value: number | undefined) {
+    super();
+  }
+}
diff --git a/llparse-frontend/src/trie/index.ts b/llparse-frontend/src/trie/index.ts
new file mode 100644
index 0000000..391c6a3
--- /dev/null
+++ b/llparse-frontend/src/trie/index.ts
@@ -0,0 +1,136 @@
+import * as assert from 'assert';
+import { Buffer } from 'buffer';
+import { Edge, node as api } from 'llparse-builder';
+
+import { TrieEmpty } from './empty';
+import { TrieNode } from './node';
+import { TrieSequence } from './sequence';
+import { ITrieSingleChild, TrieSingle } from './single';
+
+export { TrieEmpty, TrieNode, TrieSequence, TrieSingle };
+
+interface IEdge {
+  readonly key: Buffer;
+  readonly node: api.Node;
+  readonly noAdvance: boolean;
+  readonly value: number | undefined;
+}
+
+type Path = ReadonlyArray<Buffer>;
+type EdgeArray = ReadonlyArray<IEdge>;
+
+export class Trie {
+  constructor(private readonly name: string) {
+  }
+
+  public build(edges: ReadonlyArray<Edge>): undefined | TrieNode {
+    if (edges.length === 0) {
+      return undefined;
+    }
+
+    const internalEdges: IEdge[] = [];
+    for (const edge of edges) {
+      internalEdges.push({
+        key: edge.key as Buffer,
+        noAdvance: edge.noAdvance,
+        node: edge.node,
+        value: edge.value,
+      });
+    }
+
+    return this.level(internalEdges, []);
+  }
+
+  private level(edges: EdgeArray, path: Path): TrieNode {
+    const first = edges[0].key;
+    const last = edges[edges.length - 1].key;
+
+    // Leaf
+    if (edges.length === 1 && edges[0].key.length === 0) {
+      return new TrieEmpty(edges[0].node, edges[0].value);
+    }
+
+    // Find the longest common sub-string
+    let common = 0;
+    for (; common < first.length; common++) {
+      if (first[common] !== last[common]) {
+        break;
+      }
+    }
+
+    // Sequence
+    if (common > 1) {
+      return this.sequence(edges, first.slice(0, common), path);
+    }
+
+    // Single
+    return this.single(edges, path);
+  }
+
+  private slice(edges: EdgeArray, off: number): EdgeArray {
+    return edges.map((edge) => {
+      return {
+        key: edge.key.slice(off),
+        noAdvance: edge.noAdvance,
+        node: edge.node,
+        value: edge.value,
+      };
+    }).sort((a, b) => {
+      return a.key.compare(b.key);
+    });
+  }
+
+  private sequence(edges: EdgeArray, prefix: Buffer, path: Path): TrieNode {
+    const sliced = this.slice(edges, prefix.length);
+    const noAdvance = sliced.some((edge) => edge.noAdvance);
+    assert(!noAdvance);
+    const child = this.level(sliced, path.concat(prefix));
+
+    return new TrieSequence(prefix, child);
+  }
+
+  private single(edges: EdgeArray, path: Path): TrieNode {
+    // Check for duplicates
+    if (edges[0].key.length === 0) {
+      assert(path.length !== 0, `Empty root entry at "${this.name}"`);
+      assert(edges.length === 1 || edges[1].key.length !== 0,
+        `Duplicate entries in "${this.name}" at [ ${path.join(', ')} ]`);
+    }
+
+    let otherwise: TrieEmpty | undefined;
+    const keys: Map<number, IEdge[]> = new Map();
+    for (const edge of edges) {
+      if (edge.key.length === 0) {
+        otherwise = new TrieEmpty(edge.node, edge.value);
+        continue;
+      }
+      const key = edge.key[0];
+
+      if (keys.has(key)) {
+        keys.get(key)!.push(edge);
+      } else {
+        keys.set(key, [ edge ]);
+      }
+    }
+
+    const children: ITrieSingleChild[] = [];
+    keys.forEach((subEdges, key) => {
+      const sliced = this.slice(subEdges, 1);
+      const subpath = path.concat(Buffer.from([ key ]));
+
+      const noAdvance = subEdges.some((edge) => edge.noAdvance);
+      const allSame = subEdges.every((edge) => edge.noAdvance === noAdvance);
+
+      assert(allSame || subEdges.length === 0,
+        'Conflicting `.peek()` and `.match()` entries in ' +
+          `"${this.name}" at [ ${subpath.join(', ')} ]`);
+
+      children.push({
+        key,
+        noAdvance,
+        node: this.level(sliced, subpath),
+      });
+    });
+    return new TrieSingle(children, otherwise);
+  }
+}
diff --git a/llparse-frontend/src/trie/node.ts b/llparse-frontend/src/trie/node.ts
new file mode 100644
index 0000000..31f327c
--- /dev/null
+++ b/llparse-frontend/src/trie/node.ts
@@ -0,0 +1,2 @@
+export abstract class TrieNode {
+}
diff --git a/llparse-frontend/src/trie/sequence.ts b/llparse-frontend/src/trie/sequence.ts
new file mode 100644
index 0000000..6b17e02
--- /dev/null
+++ b/llparse-frontend/src/trie/sequence.ts
@@ -0,0 +1,9 @@
+import { node as api } from 'llparse-builder';
+import { TrieNode } from './node';
+
+export class TrieSequence extends TrieNode {
+  constructor(public readonly select: Buffer,
+              public readonly child: TrieNode) {
+    super();
+  }
+}
diff --git a/llparse-frontend/src/trie/single.ts b/llparse-frontend/src/trie/single.ts
new file mode 100644
index 0000000..c984af0
--- /dev/null
+++ b/llparse-frontend/src/trie/single.ts
@@ -0,0 +1,16 @@
+import { node as api } from 'llparse-builder';
+import { TrieEmpty } from './empty';
+import { TrieNode } from './node';
+
+export interface ITrieSingleChild {
+  readonly key: number;
+  readonly noAdvance: boolean;
+  readonly node: TrieNode;
+}
+
+export class TrieSingle extends TrieNode {
+  constructor(public readonly children: ReadonlyArray<ITrieSingleChild>,
+              public readonly otherwise: TrieEmpty | undefined) {
+    super();
+  }
+}
diff --git a/llparse-frontend/src/utils/identifier.ts b/llparse-frontend/src/utils/identifier.ts
new file mode 100644
index 0000000..c9ba6ad
--- /dev/null
+++ b/llparse-frontend/src/utils/identifier.ts
@@ -0,0 +1,32 @@
+export interface IUniqueName {
+  readonly name: string;
+  readonly originalName: string;
+}
+
+export class Identifier {
+  private readonly ns: Set<string> = new Set();
+
+  constructor(private readonly prefix: string = '',
+              private readonly postfix: string = '') {
+  }
+
+  public id(name: string): IUniqueName {
+    let target = this.prefix + name + this.postfix;
+    if (this.ns.has(target)) {
+      let i = 1;
+      for (; i < this.ns.size; i++) {
+        if (!this.ns.has(target + '_' + i)) {
+          break;
+        }
+      }
+
+      target += '_' + i;
+    }
+
+    this.ns.add(target);
+    return {
+      name: target,
+      originalName: name,
+    };
+  }
+}
diff --git a/llparse-frontend/src/utils/index.ts b/llparse-frontend/src/utils/index.ts
new file mode 100644
index 0000000..06e86f1
--- /dev/null
+++ b/llparse-frontend/src/utils/index.ts
@@ -0,0 +1,19 @@
+export { Identifier, IUniqueName } from './identifier';
+
+export function toCacheKey(value: number | boolean): string {
+  if (typeof value === 'number') {
+    if (value < 0) {
+      return 'm' + (-value);
+    } else {
+      return value.toString();
+    }
+  } else if (typeof value === 'boolean') {
+    if (value === true) {
+      return 'true';
+    } else {
+      return 'false';
+    }
+  } else {
+    throw new Error(`Unsupported value: "${value}"`);
+  }
+}
diff --git a/llparse-frontend/src/wrap.ts b/llparse-frontend/src/wrap.ts
new file mode 100644
index 0000000..013adb3
--- /dev/null
+++ b/llparse-frontend/src/wrap.ts
@@ -0,0 +1,3 @@
+export interface IWrap<T> {
+  readonly ref: T;
+}