Permalink
Browse files

Merge branch 'unresolved'

  • Loading branch information...
2 parents c0049a6 + c656e76 commit 3db99f2d87abdddb9d29a0d0cf86e272c59d4ddb @robey committed Nov 11, 2016
Showing with 98 additions and 23 deletions.
  1. +3 −3 src/packrattle/combiners.js
  2. +63 −14 src/packrattle/engine.js
  3. +10 −0 src/packrattle/match.js
  4. +9 −5 src/packrattle/promise_set.js
  5. +13 −1 test/src/test_onfail.js
@@ -130,11 +130,11 @@ export function drop(p) {
export function optional(p, defaultValue) {
return newParser("optional", {
wrap: p,
- cacheable: (typeof defaultValue == "string"),
- extraCacheKey: defaultValue
+ cacheable: (typeof defaultValue == "string" || defaultValue == null),
+ extraCacheKey: defaultValue == null ? "(null)" : ("str:" + defaultValue)
}, (state, results, p) => {
state.schedule(p).then(match => {
- results.add(match);
+ if (match.ok) results.add(match);
// unless we committed to p, always try the non-p case too.
if (!match.commit) results.add(state.success(defaultValue));
});
@@ -39,6 +39,9 @@ export default class Engine {
// if any handler throws an exception, abort immediately.
this.currentException = null;
+
+ // set of ParserState that haven't received a result yet
+ this.unresolvedStates = {};
}
/*
@@ -58,6 +61,10 @@ export default class Engine {
}
});
this.cache[state.id] = results;
+ this.unresolvedStates[state.id] = state;
+ results.then(() => {
+ delete this.unresolvedStates[state.id];
+ });
if (this.debugGraph) {
this.debugGraph.addNode(state.id, state.parser, state.span());
@@ -90,26 +97,27 @@ export default class Engine {
});
// start the engine!
- while (!this.workQueue.isEmpty && successes.length == 0 && !this.currentException) {
- const { state, results } = this.workQueue.get();
+ while (Object.keys(this.unresolvedStates).length > 0) {
+ while (!this.workQueue.isEmpty && successes.length == 0 && !this.currentException) {
+ const { state, results } = this.workQueue.get();
- this.ticks++;
- this.currentState = state;
- if (this.debugger) {
- this.debugger(`${rpad(this.ticks, 4)}. [${state.parser.id}]${state.parser.inspect()} @ ${state.inspect()}`);
- }
+ this.ticks++;
+ this.currentState = state;
+ if (this.debugger) {
+ this.debugger(`${rpad(this.ticks, 4)}. [${state.parser.id}]${state.parser.inspect()} @ ${state.inspect()}`);
+ }
- state.parser.matcher(state, results, ...(state.parser.children || []));
- }
+ state.parser.matcher(state, results, ...(state.parser.children || []));
+ }
- if (this.currentException) throw this.currentException;
+ if (this.currentException) throw this.currentException;
- this.currentState = null;
+ this.currentState = null;
+ this.flushUnresolvedState();
+ }
// message with 'commit' set has highest priority. secondary sort by depth.
- failures.sort((a, b) => {
- return (a.commit != b.commit) ? (b.commit ? 1 : -1) : (b.state.startpos - a.state.startpos);
- });
+ failures.sort((a, b) => b.priority - a.priority);
if (this.debugger) {
if (successes.length > 0) {
@@ -125,6 +133,47 @@ export default class Engine {
return successes.length > 0 ? successes[0] : failures[0];
}
+
+ /*
+ * okay, gather round, kids.
+ *
+ * GLL handles recursion by allowing cycles in the parser graph, and
+ * assuming that if there's a successful match, some number of recursions
+ * will find it. (the recursions are done cheaply in parallel by memoizing.
+ * check out the docs folder for more about that.)
+ *
+ * but if there's no match, the engine will give up and declare failure
+ * without necessarily marking all nodes as failed. for example:
+ *
+ * const expr = alt(number, [ () => expr, "+", () => expr ]);
+ *
+ * if the "number" parser fails, then "expr" can never succeed. GLL handles
+ * this by making the 2nd alternative's result dependent on "expr". once
+ * "number" fails, it runs out of ways forward and gives up without
+ * explicitly marking "expr" as failed. this is correct, but for certain
+ * kinds of transform, we'd like to notice all failures and generate a good
+ * error message (or even convert it to a success, in the case of "not").
+ *
+ * so we track unresolved parser states, and if the engine ends with any
+ * still unresolved, we pick the deepest state (the state that nested most
+ * deeply before cycling back), mark it as failed, and let the engine run
+ * again to see if it can make any more progress. we repeat this until all
+ * states are resolved; usually, each failure triggers a cascade of other
+ * failures that finish off one cycle.
+ */
+ flushUnresolvedState() {
+ const states = [];
+ Object.keys(this.unresolvedStates).forEach(key => {
+ states.push(this.unresolvedStates[key]);
+ });
+ if (states.length == 0) return;
+ states.sort((a, b) => b.depth - a.depth);
+ if (this.debugger) this.debugger("unresolved states: " + states.map(s => s.id).join(", "));
+
+ const state = states[0];
+ if (this.debugger) this.debugger(`forcing fail of ${state.id}`);
+ this.cache[state.id].add(state.failure());
+ }
}
@@ -27,6 +27,7 @@ export default class Match {
"value='" + quote(this.value && this.value.inspect ? this.value.inspect() : this.value) + "'"
];
if (this.commit) fields.push("commit");
+ fields.push(`priority=0x${this.priority.toString(16)}`);
return "Match(" + fields.join(", ") + ")";
}
@@ -59,4 +60,13 @@ export default class Match {
rv.commit = true;
return rv;
}
+
+ // determine how "important" this match is (larger number: higher priority).
+ get priority() {
+ // higher startpos is better.
+ let rv = this.state.startpos;
+ // commit is even better.
+ if (this.commit) rv += Math.pow(2, 40);
+ return rv;
+ }
}
@@ -15,10 +15,11 @@
*/
export default class PromiseSet {
constructor(options = {}) {
- // optimize for the case of 1 value or 1 listener.
+ // optimize for the case of 1 value and 2 listeners.
this.value0 = null;
this.values = null;
this.listener0 = null;
+ this.listener1 = null;
this.listeners = null;
this.debugger = options.debugger;
this.exceptionHandler = options.exceptionHandler;
@@ -40,8 +41,9 @@ export default class PromiseSet {
if (this.debugger) this.debugger(value.inspect ? value.inspect() : value.toString());
- if (this.listener0) this.listener0(value);
- if (this.listeners) this.listeners.forEach(f => f(value));
+ if (this.listener0 != null) this.listener0(value);
+ if (this.listener1 != null) this.listener1(value);
+ if (this.listeners != null) this.listeners.forEach(f => f(value));
return this;
}
@@ -55,10 +57,12 @@ export default class PromiseSet {
}
};
- if (!this.listener0) {
+ if (this.listener0 == null) {
this.listener0 = safeCallback;
+ } else if (this.listener1 == null) {
+ this.listener1 = safeCallback;
} else {
- if (!this.listeners) this.listeners = [];
+ if (this.listeners == null) this.listeners = [];
this.listeners.push(safeCallback);
}
@@ -27,5 +27,17 @@ describe("Parser.onFail", () => {
).named("widget");
(() => p.run("a")).should.throw(/widget/);
- })
+ });
+
+ it("executes onFail for unresolvable loops", () => {
+ const number = pr.regex(/\d+/);
+ // this is unresolvable, because it can never finish "failing" p until it gets the result from p.
+ const p = pr.alt(
+ number,
+ [ () => p, ".", () => p ],
+ [ "i", () => p ]
+ ).named("numbers");
+
+ (() => p.run("ice")).should.throw(/numbers/);
+ });
});

0 comments on commit 3db99f2

Please sign in to comment.