lezer - npm Package Compare versions

Comparing version 0.5.1 to 0.5.2

CHANGELOG.md

@@ -0,1 +1,11 @@
+## 0.5.2 (2020-01-09)
+
+### Bug fixes
+
+Fix an issue where the parser will sometimes continue, and even pick as result, a parse with error recovery even though there are error-free parses available.
+
+Fix a mistake in our binary heap implementation that would cause stacks to be ordered incorrectly.
+
+Fix an issue where the `Stack.startOf` method would ignore the top frame of the stack.
+
 ## 0.5.1 (2020-01-01)
@@ -2,0 +12,0 @@

dist/index.js

@@ -39,6 +39,6 @@ 'use strict';
     // Amount to add for a single recover action
-    Badness[Badness["Unit"] = 100] = "Unit";
+    Badness[Badness["Unit"] = 1000000] = "Unit";
     // Badness at which we disallow adding a stack if another stack
     // shares its top state and position.
-    Badness[Badness["Deduplicate"] = 200] = "Deduplicate";
+    Badness[Badness["Deduplicate"] = 2000000] = "Deduplicate";
     // The maximum amount of active stacks at which recovery actions are
@@ -49,3 +49,3 @@ // applied
     // don't recover.
-    Badness[Badness["TooBadToRecover"] = 500] = "TooBadToRecover";
+    Badness[Badness["TooBadToRecover"] = 5000000] = "TooBadToRecover";
     // If the best sibling is this amount better than the current stack,
@@ -308,3 +308,3 @@ // don't apply recovery.
         this.pos = this.reducePos = nextEnd;
-        this.badness += 100 /* Unit */;
+        this.badness += 1000000 /* Unit */;
     };
@@ -354,4 +354,5 @@ /// Check if the given term would be able to be shifted (optionally
     Stack.prototype.startOf = function (types) {
-        for (var frame = this.stack.length - 3; frame >= 0; frame -= 3) {
-            var force = this.cx.parser.stateSlot(this.stack[frame], 5 /* ForcedReduce */);
+        for (var frame = this.stack.length; frame >= 0; frame -= 3) {
+            var state = frame == this.stack.length ? this.state : this.stack[frame];
+            var force = this.cx.parser.stateSlot(state, 5 /* ForcedReduce */);
             if (types.includes(force & 65535 /* ValueMask */)) {
@@ -384,3 +385,3 @@ var base = frame - (3 * (force >> 19 /* ReduceDepthShift */));
             stack.pushState(nextStates[i], this.pos);
-            stack.badness += 100 /* Unit */;
+            stack.badness += 1000000 /* Unit */;
             result.push(stack);
@@ -400,3 +401,3 @@ }
             this.storeNode(0 /* Err */, this.reducePos, this.reducePos, 4, true);
-            this.badness += 100 /* Unit */;
+            this.badness += 1000000 /* Unit */;
         }
@@ -828,2 +829,5 @@ this.reduce(reduce);
         var _b = _a === void 0 ? {} : _a, _c = _b.cache, cache = _c === void 0 ? undefined : _c, _d = _b.strict, strict = _d === void 0 ? false : _d, _e = _b.bufferLength, bufferLength = _e === void 0 ? lezerTree.DefaultBufferLength : _e;
+        // Active stacks that can't progress normally. A non-finished parse
+        // always has at least one stack either here or in this.stacks.
+        this.stoppedStacks = [];
         this.stacks = [Stack.start(new StackContext(parser, bufferLength, input))];
@@ -833,27 +837,4 @@ this.strict = strict;
     }
-    ParseContext.prototype.takeStack = function () {
-        // Binary heap pop
-        var stacks = this.stacks, elt = stacks[0], replacement = stacks.pop();
-        if (stacks.length == 0)
-            return elt;
-        stacks[0] = replacement;
-        for (var index = 0;;) {
-            var childIndex = (index << 1) + 1;
-            if (childIndex >= stacks.length)
-                break;
-            var child = stacks[childIndex];
-            if (childIndex + 1 < stacks.length && child.compare(stacks[childIndex + 1]) >= 0) {
-                child = stacks[childIndex + 1];
-                childIndex++;
-            }
-            if (replacement.compare(child) < 0)
-                break;
-            stacks[childIndex] = replacement;
-            stacks[index] = child;
-            index = childIndex;
-        }
-        return elt;
-    };
     ParseContext.prototype.putStack = function (stack) {
-        if (stack.badness >= 200 /* Deduplicate */) {
+        if (stack.badness >= 2000000 /* Deduplicate */) {
             for (var i = 0; i < this.stacks.length; i++) {
@@ -863,8 +844,5 @@ var other = this.stacks[i];
                     var diff = stack.badness - other.badness || stack.stack.length - other.stack.length;
-                    if (diff < 0) {
+                    if (diff < 0)
                         this.stacks[i] = stack;
-                        return true;
-                    }
-                    else if (diff >= 0)
-                        return false;
+                    return;
                 }
@@ -880,15 +858,5 @@ }
             if (maxOther > stack.buffer.length)
-                return false;
+                return;
         }
-        // Binary heap add
-        var index = this.stacks.push(stack) - 1;
-        while (index > 0) {
-            var parentIndex = index >> 1, parent = this.stacks[parentIndex];
-            if (stack.compare(parent) >= 0)
-                break;
-            this.stacks[index] = parent;
-            this.stacks[parentIndex] = stack;
-            index = parentIndex;
-        }
-        return true;
+        putOnHeap(this.stacks, stack);
     };
@@ -908,3 +876,14 @@ /// Execute one parse step. This picks the parse stack that's
     ParseContext.prototype.advance = function () {
-        var stack = this.takeStack(), start = stack.pos, _a = stack.cx, input = _a.input, parser = _a.parser;
+        // Stopped stacks get advanced (or discarded, or finished) when
+        // there are no regular stacks with a lower position left. This
+        // makes sure error recovery only happens when all non-recovering
+        // advances have been made, which helps prune out unneccesary
+        // error recovery.
+        if (this.stoppedStacks.length > 0 && (!this.stacks.length || this.stacks[0].pos > this.stoppedStacks[0].pos))
+            return this.advanceStoppedStack(takeFromHeap(this.stoppedStacks));
+        this.advanceStack(takeFromHeap(this.stacks));
+        return null;
+    };
+    ParseContext.prototype.advanceStack = function (stack) {
+        var start = stack.pos, _a = stack.cx, input = _a.input, parser = _a.parser;
         var base = verbose ? stack + " -> " : "";
@@ -919,3 +898,3 @@ if (this.cache) {
                     this.putStack(stack);
-                    return null;
+                    return;
                 }
@@ -944,8 +923,8 @@ if (cached.children.length == 0 || cached.positions[0] > 0)
             }
-            var end_1 = this.scanForNestEnd(stack, endToken, filterEnd);
-            var clippedInput = stack.cx.input.clip(end_1);
+            var end = this.scanForNestEnd(stack, endToken, filterEnd);
+            var clippedInput = stack.cx.input.clip(end);
             if (parseNode || !nested) {
                 var node = parseNode ? parseNode(clippedInput, stack.pos) : lezerTree.Tree.empty;
-                if (node.length != end_1 - stack.pos)
-                    node = new lezerTree.Tree(node.type, node.children, node.positions, end_1 - stack.pos);
+                if (node.length != end - stack.pos)
+                    node = new lezerTree.Tree(node.type, node.children, node.positions, end - stack.pos);
                 if (wrapType != null)
@@ -962,3 +941,3 @@ node = new lezerTree.Tree(parser.group.types[wrapType], [node], [0], node.length);
             }
-            return null;
+            return;
         }
@@ -971,18 +950,20 @@ var defaultReduce = parser.stateSlot(stack.state, 4 /* DefaultReduce */);
                 console.log(base + stack + (" (via always-reduce " + parser.getName(defaultReduce & 65535 /* ValueMask */) + ")"));
-            return null;
+            return;
         }
         var actions = stack.cx.tokens.getActions(stack, input);
         for (var i = 0; i < actions.length;) {
-            var action = actions[i++], term_1 = actions[i++], end_2 = actions[i++];
+            var action = actions[i++], term = actions[i++], end = actions[i++];
             var localStack = i == actions.length ? stack : stack.split();
-            localStack.apply(action, term_1, end_2);
+            localStack.apply(action, term, end);
             if (verbose)
                 console.log(base + localStack + (" (via " + ((action & 65536 /* ReduceFlag */) == 0 ? "shift"
-                    : "reduce of " + parser.getName(action & 65535 /* ValueMask */)) + " for " + parser.getName(term_1) + " @ " + start + (localStack == stack ? "" : ", split") + ")"));
+                    : "reduce of " + parser.getName(action & 65535 /* ValueMask */)) + " for " + parser.getName(term) + " @ " + start + (localStack == stack ? "" : ", split") + ")"));
             this.putStack(localStack);
         }
-        if (actions.length > 0)
-            return null;
-        // If we're here, the stack failed to advance normally
-        if (start == input.length && parser.stateFlag(stack.state, 2 /* Accepting */)) // End of file
+        if (actions.length == 0)
+            putOnHeap(this.stoppedStacks, stack);
+    };
+    ParseContext.prototype.advanceStoppedStack = function (stack) {
+        var _a = stack.cx, input = _a.input, parser = _a.parser;
+        if (stack.pos == input.length && parser.stateFlag(stack.state, 2 /* Accepting */)) // End of file
             return this.finishStack(stack);
@@ -994,14 +975,15 @@ // Not end of file. See if we should recover.
         // stack, don't continue it.
-        if (minBad <= stack.badness &&
+        if (this.stacks.length && minBad <= stack.badness &&
             (this.stacks.length >= 25 /* MaxRecoverStacks */ ||
-                stack.badness > Math.min(500 /* TooBadToRecover */, minBad * 3 /* RecoverSiblingFactor */)))
+                stack.badness > Math.min(5000000 /* TooBadToRecover */, minBad * 3 /* RecoverSiblingFactor */)))
             return null;
-        var _c = stack.cx.tokens.mainToken, end = _c.end, term = _c.value;
+        var _b = stack.cx.tokens.mainToken, end = _b.end, term = _b.value;
         if (this.strict) {
-            if (this.stacks.length)
+            if (this.stacks.length || this.stoppedStacks.length)
                 return null;
-            throw new SyntaxError("No parse at " + start + " with " + parser.getName(term) + " (stack is " + stack + ")");
+            throw new SyntaxError("No parse at " + stack.pos + " with " + parser.getName(term) + " (stack is " + stack + ")");
         }
-        for (var _i = 0, _d = stack.recoverByInsert(term); _i < _d.length; _i++) {
-            var insert = _d[_i];
+        var base = verbose ? stack + " -> " : "";
+        for (var _i = 0, _c = stack.recoverByInsert(term); _i < _c.length; _i++) {
+            var insert = _c[_i];
             if (verbose)
@@ -1017,7 +999,7 @@ console.log(base + insert + " (via recover-insert)");
         }
-        else if (start == input.length) {
+        else if (stack.pos == input.length) {
             return this.finishStack(stack);
         }
-        if (end == start) {
-            if (start == input.length)
+        if (end == stack.pos) {
+            if (stack.pos == input.length)
                 return null;
@@ -1047,3 +1029,3 @@ end++;
         /// The position to which the parse has advanced.
-        get: function () { return this.stacks[0].pos; },
+        get: function () { return (this.stacks[0] || this.stoppedStacks[0]).pos; },
         enumerable: true,
@@ -1055,3 +1037,3 @@ configurable: true
     ParseContext.prototype.forceFinish = function () {
-        var stack = this.stacks[0].split();
+        var stack = (this.stacks[0] || this.stoppedStacks[0]).split();
         while (!stack.cx.parser.stateFlag(stack.state, 2 /* Accepting */) && stack.forceReduce()) { }
@@ -1081,4 +1063,4 @@ return stack.toTree();
         // Drop any other stack that has the same parent
-        if (this.stacks.some(function (s) { return s.cx.parent == parent; }))
-            this.stacks = this.stacks.filter(function (s) { return s.cx.parent != parent; }).sort(function (a, b) { return a.compare(b); });
+        this.stacks = dropParent(this.stacks, parent);
+        this.stoppedStacks = dropParent(this.stoppedStacks, parent);
         return parent;
@@ -1350,2 +1332,42 @@ };
 }
+// Binary heap add
+function putOnHeap(stacks, stack) {
+    var index = stacks.push(stack) - 1;
+    while (index > 0) {
+        var parentIndex = (index - 1) >> 1, parent = stacks[parentIndex];
+        if (stack.compare(parent) >= 0)
+            break;
+        stacks[index] = parent;
+        stacks[parentIndex] = stack;
+        index = parentIndex;
+    }
+}
+function takeFromHeap(stacks) {
+    // Binary heap pop
+    var elt = stacks[0], replacement = stacks.pop();
+    if (stacks.length == 0)
+        return elt;
+    stacks[0] = replacement;
+    for (var index = 0;;) {
+        var childIndex = (index << 1) + 1;
+        if (childIndex >= stacks.length)
+            break;
+        var child = stacks[childIndex];
+        if (childIndex + 1 < stacks.length && child.compare(stacks[childIndex + 1]) >= 0) {
+            child = stacks[childIndex + 1];
+            childIndex++;
+        }
+        if (replacement.compare(child) < 0)
+            break;
+        stacks[childIndex] = replacement;
+        stacks[index] = child;
+        index = childIndex;
+    }
+    return elt;
+}
+function dropParent(stacks, parent) {
+    return stacks.some(function (s) { return s.cx.parent == parent; })
+        ? stacks.filter(function (s) { return s.cx.parent != parent; }).sort(function (a, b) { return a.compare(b); })
+        : stacks;
+}
 
@@ -1352,0 +1374,0 @@ exports.NodeGroup = lezerTree.NodeGroup;

dist/parse.d.ts

@@ -12,10 +12,2 @@ import { Stack } from "./stack";
 }
-declare class CacheCursor {
-    trees: Tree[];
-    start: number[];
-    index: number[];
-    nextStart: number;
-    constructor(tree: Tree);
-    nodeAt(pos: number): Tree | null;
-}
 declare class CachedToken extends Token {
@@ -53,9 +45,11 @@ readonly tokenizer: Tokenizer;
 export declare class ParseContext {
-    stacks: Stack[];
-    cache: CacheCursor | null;
-    strict: boolean;
+    private stacks;
+    private stoppedStacks;
+    private cache;
+    private strict;
     constructor(parser: Parser, input: InputStream, { cache, strict, bufferLength }?: ParseOptions);
-    private takeStack;
     private putStack;
     advance(): Tree;
+    private advanceStack;
+    private advanceStoppedStack;
     private finishStack;
@@ -62,0 +56,0 @@ get pos(): number;

dist/stack.d.ts

 import { StackContext } from "./parse";
 import { Tree } from "lezer-tree";
 export declare const enum Badness {
-    Unit = 100,
-    Deduplicate = 200,
+    Unit = 1000000,
+    Deduplicate = 2000000,
     MaxRecoverStacks = 25,
-    TooBadToRecover = 500,
+    TooBadToRecover = 5000000,
     RecoverSiblingFactor = 3,
@@ -9,0 +9,0 @@ MaxParallelBufferLength = 800

package.json

 {
   "name": "lezer",
-  "version": "0.5.1",
+  "version": "0.5.2",
   "description": "Incremental parser",
@@ -14,3 +14,3 @@ "main": "dist/index.js",
     "rollup-plugin-typescript2": "^0.20.1",
-    "typescript": "^3.4.3"
+    "typescript": "^3.7.2"
   },
@@ -17,0 +17,0 @@ "dependencies": {

src/parse.ts

@@ -214,8 +214,9 @@ import {Stack, Badness} from "./stack"
 export class ParseContext {
-  /// @internal
-  stacks: Stack[]
-  /// @internal
-  cache: CacheCursor | null
-  /// @internal
-  strict: boolean
+  // Active parse stacks.
+  private stacks: Stack[]
+  // Active stacks that can't progress normally. A non-finished parse
+  // always has at least one stack either here or in this.stacks.
+  private stoppedStacks: Stack[] = []
+  private cache: CacheCursor | null
+  private strict: boolean
 
@@ -231,24 +232,3 @@ /// @internal
 
-  private takeStack() {
-    // Binary heap pop
-    let {stacks} = this, elt = stacks[0], replacement = stacks.pop()!
-    if (stacks.length == 0) return elt
-    stacks[0] = replacement
-    for (let index = 0;;) {
-      let childIndex = (index << 1) + 1
-      if (childIndex >= stacks.length) break
-      let child = stacks[childIndex]
-      if (childIndex + 1 < stacks.length && child.compare(stacks[childIndex + 1]) >= 0) {
-        child = stacks[childIndex + 1]
-        childIndex++
-      }
-      if (replacement.compare(child) < 0) break
-      stacks[childIndex] = replacement
-      stacks[index] = child
-      index = childIndex
-    }
-    return elt
-  }
-
-  private putStack(stack: Stack): boolean {
+  private putStack(stack: Stack) {
     if (stack.badness >= Badness.Deduplicate) {
@@ -259,4 +239,4 @@ for (let i = 0; i < this.stacks.length; i++) {
           let diff = stack.badness - other.badness || stack.stack.length - other.stack.length
-          if (diff < 0) { this.stacks[i] = stack; return true }
-          else if (diff >= 0) return false
+          if (diff < 0) this.stacks[i] = stack
+          return
         }
@@ -270,15 +250,6 @@ }
       let maxOther = this.stacks.reduce((m, s) => Math.max(m, s.buffer.length), 0)
-      if (maxOther > stack.buffer.length) return false
+      if (maxOther > stack.buffer.length) return
     }
 
-    // Binary heap add
-    let index = this.stacks.push(stack) - 1
-    while (index > 0) {
-      let parentIndex = index >> 1, parent = this.stacks[parentIndex]
-      if (stack.compare(parent) >= 0) break
-      this.stacks[index] = parent
-      this.stacks[parentIndex] = stack
-      index = parentIndex
-    }
-    return true
+    putOnHeap(this.stacks, stack)
   }
@@ -299,3 +270,15 @@
   advance() {
-    let stack = this.takeStack(), start = stack.pos, {input, parser} = stack.cx
+    // Stopped stacks get advanced (or discarded, or finished) when
+    // there are no regular stacks with a lower position left. This
+    // makes sure error recovery only happens when all non-recovering
+    // advances have been made, which helps prune out unneccesary
+    // error recovery.
+    if (this.stoppedStacks.length > 0 && (!this.stacks.length || this.stacks[0].pos > this.stoppedStacks[0].pos))
+      return this.advanceStoppedStack(takeFromHeap(this.stoppedStacks))
+    this.advanceStack(takeFromHeap(this.stacks))
+    return null
+  }
+
+  private advanceStack(stack: Stack) {
+    let start = stack.pos, {input, parser} = stack.cx
     let base = verbose ? stack + " -> " : ""
@@ -310,3 +293,3 @@
           this.putStack(stack)
-          return null
+          return
         }
@@ -344,3 +327,3 @@ if (cached.children.length == 0 || cached.positions[0] > 0) break
       }
-      return null
+      return
     }
@@ -353,3 +336,3 @@
       if (verbose) console.log(base + stack + ` (via always-reduce ${parser.getName(defaultReduce & Action.ValueMask)})`)
-      return null
+      return
     }
@@ -368,7 +351,9 @@
     }
-    if (actions.length > 0) return null
 
-    // If we're here, the stack failed to advance normally
+    if (actions.length == 0) putOnHeap(this.stoppedStacks, stack)
+  }
 
-    if (start == input.length && parser.stateFlag(stack.state, StateFlag.Accepting)) // End of file
+  private advanceStoppedStack(stack: Stack) {
+    let {input, parser} = stack.cx
+    if (stack.pos == input.length && parser.stateFlag(stack.state, StateFlag.Accepting)) // End of file
       return this.finishStack(stack)
@@ -381,3 +366,3 @@
     // stack, don't continue it.
-    if (minBad <= stack.badness &&
+    if (this.stacks.length && minBad <= stack.badness &&
         (this.stacks.length >= Badness.MaxRecoverStacks ||
@@ -389,6 +374,7 @@ stack.badness > Math.min(Badness.TooBadToRecover, minBad * Badness.RecoverSiblingFactor)))
     if (this.strict) {
-      if (this.stacks.length) return null
-      throw new SyntaxError("No parse at " + start + " with " + parser.getName(term) + " (stack is " + stack + ")")
+      if (this.stacks.length || this.stoppedStacks.length) return null
+      throw new SyntaxError("No parse at " + stack.pos + " with " + parser.getName(term) + " (stack is " + stack + ")")
     }
 
+    let base = verbose ? stack + " -> " : ""
     for (let insert of stack.recoverByInsert(term)) {
@@ -402,8 +388,8 @@ if (verbose) console.log(base + insert + " (via recover-insert)")
       this.putStack(reduce)
-    } else if (start == input.length) {
+    } else if (stack.pos == input.length) {
       return this.finishStack(stack)
     }
 
-    if (end == start) {
-      if (start == input.length) return null
+    if (end == stack.pos) {
+      if (stack.pos == input.length) return null
       end++
@@ -431,3 +417,3 @@ term = Term.Err
   /// The position to which the parse has advanced.
-  get pos() { return this.stacks[0].pos }
+  get pos() { return (this.stacks[0] || this.stoppedStacks[0]).pos }
 
@@ -437,3 +423,3 @@ /// Force the parse to finish, generating a tree containing the nodes
   forceFinish() {
-    let stack = this.stacks[0].split()
+    let stack = (this.stacks[0] || this.stoppedStacks[0]).split()
     while (!stack.cx.parser.stateFlag(stack.state, StateFlag.Accepting) && stack.forceReduce()) {}
@@ -462,4 +448,4 @@ return stack.toTree()
     // Drop any other stack that has the same parent
-    if (this.stacks.some(s => s.cx.parent == parent))
-      this.stacks = this.stacks.filter(s => s.cx.parent != parent).sort((a, b) => a.compare(b))
+    this.stacks = dropParent(this.stacks, parent)
+    this.stoppedStacks = dropParent(this.stoppedStacks, parent)
     return parent
@@ -734,1 +720,40 @@ }
 }
+
+// Binary heap add
+function putOnHeap(stacks: Stack[], stack: Stack) {
+  let index = stacks.push(stack) - 1
+  while (index > 0) {
+    let parentIndex = (index - 1) >> 1, parent = stacks[parentIndex]
+    if (stack.compare(parent) >= 0) break
+    stacks[index] = parent
+    stacks[parentIndex] = stack
+    index = parentIndex
+  }
+}
+
+function takeFromHeap(stacks: Stack[]) {
+  // Binary heap pop
+  let elt = stacks[0], replacement = stacks.pop()!
+  if (stacks.length == 0) return elt
+  stacks[0] = replacement
+  for (let index = 0;;) {
+    let childIndex = (index << 1) + 1
+    if (childIndex >= stacks.length) break
+    let child = stacks[childIndex]
+    if (childIndex + 1 < stacks.length && child.compare(stacks[childIndex + 1]) >= 0) {
+      child = stacks[childIndex + 1]
+      childIndex++
+    }
+    if (replacement.compare(child) < 0) break
+    stacks[childIndex] = replacement
+    stacks[index] = child
+    index = childIndex
+  }
+  return elt
+}
+
+function dropParent(stacks: Stack[], parent: Stack) {
+  return stacks.some(s => s.cx.parent == parent)
+    ? stacks.filter(s => s.cx.parent != parent).sort((a, b) => a.compare(b))
+    : stacks
+}

src/stack.ts

@@ -7,7 +7,7 @@ import {Action, Term, StateFlag, ParseState} from "./constants"
   // Amount to add for a single recover action
-  Unit = 100,
+  Unit = 1e6,
 
   // Badness at which we disallow adding a stack if another stack
   // shares its top state and position.
-  Deduplicate = 200,
+  Deduplicate = 2e6,
 
@@ -20,3 +20,3 @@ // The maximum amount of active stacks at which recovery actions are
   // don't recover.
-  TooBadToRecover = 500,
+  TooBadToRecover = 5e6,
 
@@ -305,4 +305,5 @@ // If the best sibling is this amount better than the current stack,
   startOf(types: readonly number[]) {
-    for (let frame = this.stack.length - 3; frame >= 0; frame -= 3) {
-      let force = this.cx.parser.stateSlot(this.stack[frame], ParseState.ForcedReduce)
+    for (let frame = this.stack.length; frame >= 0; frame -= 3) {
+      let state = frame == this.stack.length ? this.state : this.stack[frame]
+      let force = this.cx.parser.stateSlot(state, ParseState.ForcedReduce)
       if (types.includes(force & Action.ValueMask)) {
@@ -309,0 +310,0 @@ let base = frame - (3 * (force >> Action.ReduceDepthShift))

No alert changes

Improved metrics

Total package byte prevSize

2211447

0.35%

Lines of code

3047

1.3%

No dependency changes