diff options
Diffstat (limited to 'llparse-frontend/src')
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; +} |