Huge News!Announcing our $40M Series B led by Abstract Ventures.Learn More
Socket
Sign inDemoInstall
Socket

lezer

Package Overview
Dependencies
Maintainers
1
Versions
37
Alerts
File Explorer

Advanced tools

Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

lezer - npm Package Compare versions

Comparing version 0.5.1 to 0.5.2

.rpt2_cache/rpt2_0948bd7b8fcfb5dfcefcf110e10b03d9379ed0cf/code/cache/8187a68439e32119fba970d61a3fe375ea27aece

10

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 @@

178

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;

@@ -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;

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

{
"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": {

@@ -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
}

@@ -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))

Sorry, the diff of this file is not supported yet

Sorry, the diff of this file is not supported yet

SocketSocket SOC 2 Logo

Product

  • Package Alerts
  • Integrations
  • Docs
  • Pricing
  • FAQ
  • Roadmap
  • Changelog

Packages

npm

Stay in touch

Get open source security insights delivered straight into your inbox.


  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc