Socket
Socket
Sign inDemoInstall

lezer-tree

Package Overview
Dependencies
Maintainers
1
Versions
25
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

lezer-tree - npm Package Compare versions

Comparing version 0.11.1 to 0.12.0

dist/tree.cjs.map
dist/tree.es.js.map

26

CHANGELOG.md

@@ -0,1 +1,27 @@

## 0.12.0 (2020-10-23)
### Breaking changes
`Tree.iterate` no longer allows returning from inside the iteration (use cursors directly for that kind of use cases).
`Subtree` has been renamed to `SyntaxNode` and narrowed in scope a little.
The `top`, `skipped`, and `error` node props no longer exist.
### New features
The package now offers a `TreeCursor` abstraction, which can be used for both regular iteration and for custom traversal of a tree.
`SyntaxNode` instances have `nextSibling`/`prevSibling` getters that allow more direct navigation through the tree.
Node types now expose `isTop`, `isSkipped`, `isError`, and `isRepeated` properties that indicate special status.
Adds `NodeProp.group` to assign group names to node types.
Syntax nodes now have helper functions `getChild` and `getChildren` to retrieve direct child nodes by type or group.
`NodeType.match` (and thus `NodeProp.add`) now allows types to be targeted by group name.
Node types have a new `is` method for checking whether their name or one of their groups matches a given string.
## 0.11.1 (2020-09-26)

@@ -2,0 +28,0 @@

96

dist/tree.d.ts

@@ -8,10 +8,2 @@ export declare const DefaultBufferLength = 1024;

}
declare type EnterFunc<T> = (type: NodeType, start: number, end: number) => T | false | undefined;
declare type LeaveFunc = (type: NodeType, start: number, end: number) => void;
declare type IterateArgs<T> = {
enter: EnterFunc<T>;
leave?: LeaveFunc;
from?: number;
to?: number;
};
export declare class NodeProp<T> {

@@ -33,7 +25,5 @@ deserialize: (str: string) => T;

} | ((type: NodeType) => T | undefined)): NodePropSource;
static error: NodeProp<boolean>;
static skipped: NodeProp<boolean>;
static closedBy: NodeProp<readonly string[]>;
static openedBy: NodeProp<readonly string[]>;
static top: NodeProp<boolean>;
static group: NodeProp<readonly string[]>;
}

@@ -46,2 +36,7 @@ export declare class NodePropSource {

prop<T>(prop: NodeProp<T>): T | undefined;
get isTop(): boolean;
get isSkipped(): boolean;
get isError(): boolean;
get isRepeated(): boolean;
is(name: string): boolean;
static none: NodeType;

@@ -57,18 +52,3 @@ static match<T>(map: {

}
export declare abstract class Subtree {
abstract parent: Subtree | null;
abstract type: NodeType;
get name(): string;
abstract start: number;
abstract end: number;
get depth(): number;
get root(): Tree;
abstract iterate<T = any>(args: IterateArgs<T>): T | undefined;
resolve(pos: number, side?: -1 | 0 | 1): Subtree;
abstract childBefore(pos: number): Subtree | null;
abstract childAfter(pos: number): Subtree | null;
get firstChild(): Subtree | null;
get lastChild(): Subtree | null;
}
export declare class Tree extends Subtree {
export declare class Tree {
readonly type: NodeType;

@@ -78,6 +58,3 @@ readonly children: readonly (Tree | TreeBuffer)[];

readonly length: number;
parent: null;
constructor(type: NodeType, children: readonly (Tree | TreeBuffer)[], positions: readonly number[], length: number);
get start(): number;
get end(): number;
private partial;

@@ -87,5 +64,11 @@ applyChanges(changes: readonly ChangedRange[]): Tree;

static empty: Tree;
iterate<T = any>({ from, to, enter, leave }: IterateArgs<T>): T | undefined;
childBefore(pos: number): Subtree | null;
childAfter(pos: number): Subtree | null;
cursor(pos?: number, side?: -1 | 0 | 1): TreeCursor;
get topNode(): SyntaxNode;
resolve(pos: number, side?: -1 | 0 | 1): SyntaxNode;
iterate(spec: {
enter(type: NodeType, from: number, to: number): false | void;
leave?(type: NodeType, from: number, to: number): void;
from?: number;
to?: number;
}): void;
append(other: Tree): Tree;

@@ -95,3 +78,3 @@ balance(maxBufferLength?: number): Tree;

}
export declare type BuildData = {
declare type BuildData = {
buffer: BufferCursor | readonly number[];

@@ -107,5 +90,46 @@ group: NodeGroup;

readonly type: NodeType;
iterate<T = any>({ from, to, enter, leave }: IterateArgs<T>): T | undefined;
private parentNodesByEnd;
}
export interface SyntaxNode {
type: NodeType;
name: string;
from: number;
to: number;
parent: SyntaxNode | null;
firstChild: SyntaxNode | null;
lastChild: SyntaxNode | null;
childAfter(pos: number): SyntaxNode | null;
childBefore(pos: number): SyntaxNode | null;
nextSibling: SyntaxNode | null;
prevSibling: SyntaxNode | null;
cursor: TreeCursor;
resolve(pos: number, side?: -1 | 0 | 1): SyntaxNode;
getChild(type: string, before?: string | null, after?: string | null): SyntaxNode | null;
getChildren(type: string, before?: string | null, after?: string | null): SyntaxNode[];
}
export declare class TreeCursor {
type: NodeType;
get name(): string;
from: number;
to: number;
private buffer;
private stack;
private index;
private bufferNode;
private yieldNode;
private yieldBuf;
private yield;
firstChild(): boolean;
lastChild(): boolean;
childAfter(pos: number): boolean;
childBefore(pos: number): boolean;
parent(): boolean;
nextSibling(): boolean;
prevSibling(): boolean;
private atLastNode;
private move;
next(): boolean;
prev(): boolean;
moveTo(pos: number, side?: -1 | 0 | 1): this;
get node(): SyntaxNode;
}
export interface BufferCursor {

@@ -112,0 +136,0 @@ pos: number;

1265

dist/tree.es.js
/// The default maximum length of a `TreeBuffer` node.
export const DefaultBufferLength = 1024;
class Iteration {
constructor(enter, leave) {
this.enter = enter;
this.leave = leave;
this.result = undefined;
}
get done() { return this.result !== undefined; }
doEnter(type, start, end) {
let value = this.enter(type, start, end);
if (value === undefined)
return true;
if (value !== false)
this.result = value;
return false;
}
}
let nextPropID = 0;
var DefaultBufferLength = 1024;
var nextPropID = 0;
var CachedNode = new WeakMap();
/// Each [node type](#tree.NodeType) can have metadata associated with
/// it in props. Instances of this class represent prop names.
export class NodeProp {
var NodeProp = /** @class */ (function () {
/// Create a new node prop type. You can optionally pass a
/// `deserialize` function.
constructor({ deserialize } = {}) {
function NodeProp(_a) {
var deserialize = (_a === void 0 ? {} : _a).deserialize;
this.id = nextPropID++;
this.deserialize = deserialize || (() => {
this.deserialize = deserialize || (function () {
throw new Error("This node type doesn't define a deserialize function");

@@ -33,9 +19,9 @@ });

/// the identity function.
static string() { return new NodeProp({ deserialize: str => str }); }
NodeProp.string = function () { return new NodeProp({ deserialize: function (str) { return str; } }); };
/// Create a number-valued node prop whose deserialize function is
/// just `Number`.
static number() { return new NodeProp({ deserialize: Number }); }
NodeProp.number = function () { return new NodeProp({ deserialize: Number }); };
/// Creates a boolean-valued node prop whose deserialize function
/// returns true for any input.
static flag() { return new NodeProp({ deserialize: () => true }); }
NodeProp.flag = function () { return new NodeProp({ deserialize: function () { return true; } }); };
/// Store a value for this prop in the given object. This can be

@@ -45,6 +31,6 @@ /// useful when building up a prop object to pass to the

/// argument.
set(propObj, value) {
NodeProp.prototype.set = function (propObj, value) {
propObj[this.id] = value;
return propObj;
}
};
/// This is meant to be used with

@@ -57,29 +43,25 @@ /// [`NodeGroup.extend`](#tree.NodeGroup.extend) or

/// it does.
add(match) {
NodeProp.prototype.add = function (match) {
return new NodePropSource(this, typeof match == "function" ? match : NodeType.match(match));
}
}
/// The special node type that the parser uses to represent parse
/// errors has this flag set. (You shouldn't use it for custom nodes
/// that represent erroneous content.)
NodeProp.error = NodeProp.flag();
/// Nodes that were produced by skipped expressions (such as
/// comments) have this prop set to true.
NodeProp.skipped = NodeProp.flag();
/// Prop that is used to describe matching delimiters. For opening
/// delimiters, this holds an array of node names (written as a
/// space-separated string when declaring this prop in a grammar)
/// for the node types of closing delimiters that match it.
NodeProp.closedBy = new NodeProp({ deserialize: str => str.split(" ") });
/// The inverse of [`openedBy`](#tree.NodeProp^closedBy). This is
/// attached to closing delimiters, holding an array of node names
/// of types of matching opening delimiters.
NodeProp.openedBy = new NodeProp({ deserialize: str => str.split(" ") });
/// Indicates that this node indicates a top level document.
NodeProp.top = NodeProp.flag();
};
/// Prop that is used to describe matching delimiters. For opening
/// delimiters, this holds an array of node names (written as a
/// space-separated string when declaring this prop in a grammar)
/// for the node types of closing delimiters that match it.
NodeProp.closedBy = new NodeProp({ deserialize: function (str) { return str.split(" "); } });
/// The inverse of [`openedBy`](#tree.NodeProp^closedBy). This is
/// attached to closing delimiters, holding an array of node names
/// of types of matching opening delimiters.
NodeProp.openedBy = new NodeProp({ deserialize: function (str) { return str.split(" "); } });
/// Used to assign node types to groups (for example, all node
/// types that represent an expression could be tagged with an
/// `"Expression"` group).
NodeProp.group = new NodeProp({ deserialize: function (str) { return str.split(" "); } });
return NodeProp;
}());
/// Type returned by [`NodeProp.add`](#tree.NodeProp.add). Describes
/// the way a prop should be added to each node type in a node group.
export class NodePropSource {
var NodePropSource = /** @class */ (function () {
/// @internal
constructor(
function NodePropSource(
/// @internal

@@ -92,7 +74,8 @@ prop,

}
}
return NodePropSource;
}());
/// Each node in a syntax tree has a node type associated with it.
export class NodeType {
var NodeType = /** @class */ (function () {
/// @internal
constructor(
function NodeType(
/// The name of the node type. Not necessarily unique, but if the

@@ -107,25 +90,72 @@ /// grammar was written properly, different node types with the

/// used in the parser.
id) {
id,
/// @internal
flags) {
if (flags === void 0) { flags = 0; }
this.name = name;
this.props = props;
this.id = id;
this.flags = flags;
}
/// Retrieves a node prop for this type. Will return `undefined` if
/// the prop isn't present on this node.
prop(prop) { return this.props[prop.id]; }
NodeType.prototype.prop = function (prop) { return this.props[prop.id]; };
Object.defineProperty(NodeType.prototype, "isTop", {
/// True when this is the top node of a grammar.
get: function () { return (this.flags & 1) > 0; },
enumerable: true,
configurable: true
});
Object.defineProperty(NodeType.prototype, "isSkipped", {
/// True when this node is produced by a skip rule.
get: function () { return (this.flags & 2) > 0; },
enumerable: true,
configurable: true
});
Object.defineProperty(NodeType.prototype, "isError", {
/// Indicates whether this is an error node.
get: function () { return (this.flags & 4) > 0; },
enumerable: true,
configurable: true
});
Object.defineProperty(NodeType.prototype, "isRepeated", {
/// When true, this node type is used to cache repetition, and is
/// not a user-defined named node.
get: function () { return (this.flags & 8) > 0; },
enumerable: true,
configurable: true
});
/// Returns true when this node's name or one of its
/// [groups](#tree.NodeProp^group) matches the given string.
NodeType.prototype.is = function (name) {
if (this.name == name)
return true;
var group = this.prop(NodeProp.group);
return group ? group.indexOf(name) > -1 : false;
};
/// Create a function from node types to arbitrary values by
/// specifying an object whose property names are node names. Often
/// useful with [`NodeProp.add`](#tree.NodeProp.add). You can put
/// multiple node names, separated by spaces, in a single property
/// name to map multiple node names to a single value.
static match(map) {
let direct = Object.create(null);
for (let prop in map)
for (let name of prop.split(" "))
/// specifying an object whose property names are node or
/// [group](#tree.NodeProp^group) names. Often useful with
/// [`NodeProp.add`](#tree.NodeProp.add). You can put multiple
/// names, separated by spaces, in a single property name to map
/// multiple node names to a single value.
NodeType.match = function (map) {
var direct = Object.create(null);
for (var prop in map)
for (var _i = 0, _a = prop.split(" "); _i < _a.length; _i++) {
var name = _a[_i];
direct[name] = map[prop];
return (node) => direct[node.name];
}
}
/// An empty dummy node type to use when no actual type is available.
NodeType.none = new NodeType("", Object.create(null), 0);
}
return function (node) {
for (var groups = node.prop(NodeProp.group), i = -1; i < (groups ? groups.length : 0); i++) {
var found = direct[i < 0 ? node.name : groups[i]];
if (found)
return found;
}
};
};
/// An empty dummy node type to use when no actual type is available.
NodeType.none = new NodeType("", Object.create(null), 0);
return NodeType;
}());
/// A node group holds a collection of node types. It is used to

@@ -139,10 +169,10 @@ /// compactly represent trees by storing their type ids, rather than a

/// slots.
export class NodeGroup {
var NodeGroup = /** @class */ (function () {
/// Create a group with the given types. The `id` property of each
/// type should correspond to its position within the array.
constructor(
function NodeGroup(
/// The node types in this group, by id.
types) {
this.types = types;
for (let i = 0; i < types.length; i++)
for (var i = 0; i < types.length; i++)
if (types[i].id != i)

@@ -154,12 +184,18 @@ throw new RangeError("Node type ids should correspond to array positions when creating a node group");

/// [`NodeProp.add`](#tree.NodeProp.add).
extend(...props) {
let newTypes = [];
for (let type of this.types) {
let newProps = null;
for (let source of props) {
let value = source.f(type);
NodeGroup.prototype.extend = function () {
var props = [];
for (var _i = 0; _i < arguments.length; _i++) {
props[_i] = arguments[_i];
}
var newTypes = [];
for (var _a = 0, _b = this.types; _a < _b.length; _a++) {
var type = _b[_a];
var newProps = null;
for (var _c = 0, props_1 = props; _c < props_1.length; _c++) {
var source = props_1[_c];
var value = source.f(type);
if (value !== undefined) {
if (!newProps) {
newProps = Object.create(null);
for (let prop in type.props)
for (var prop in type.props)
newProps[prop] = type.props[prop];

@@ -170,51 +206,8 @@ }

}
newTypes.push(newProps ? new NodeType(type.name, newProps, type.id) : type);
newTypes.push(newProps ? new NodeType(type.name, newProps, type.id, type.flags) : type);
}
return new NodeGroup(newTypes);
}
}
/// A subtree is a representation of part of the syntax tree. It may
/// either be the tree root, or a tagged node.
export class Subtree {
// Shorthand for `.type.name`.
get name() { return this.type.name; }
/// The depth (number of parent nodes) of this subtree
get depth() {
let d = 0;
for (let p = this.parent; p; p = p.parent)
d++;
return d;
}
/// The root of the tree that this subtree is part of
get root() {
let cx = this;
while (cx.parent)
cx = cx.parent;
return cx;
}
/// Find the node at a given position. By default, this will return
/// the lowest-depth subtree that covers the position from both
/// sides, meaning that nodes starting or ending at the position
/// aren't entered. You can pass a `side` of `-1` to enter nodes
/// that end at the position, or `1` to enter nodes that start
/// there.
resolve(pos, side = 0) {
let result = this.resolveAt(pos);
// FIXME this is slightly inefficient in that it scans the result
// of resolveAt twice (but further complicating child-finding
// logic seems unattractive as well)
if (side != 0)
for (;;) {
let child = (side < 0 ? result.childBefore(pos) : result.childAfter(pos));
if (!child || (side < 0 ? child.end : child.start) != pos)
break;
result = child;
}
return result;
}
/// Get the first child of this subtree.
get firstChild() { return this.childAfter(this.start - 1); }
/// Find the last child of this subtree.
get lastChild() { return this.childBefore(this.end + 1); }
}
};
return NodeGroup;
}());
/// A piece of syntax tree. There are two ways to approach these

@@ -230,11 +223,11 @@ /// trees: the way they are actually stored in memory, and the

/// representation is very awkward, so most client code will want to
/// use the `Subtree` interface instead, which provides a view on some
/// part of this data structure, and can be used (through `resolve`,
/// for example) to zoom in on any single node.
export class Tree extends Subtree {
/// use the `TreeCursor` interface instead, which provides a view on
/// some part of this data structure, and can be used to move around
/// to adjacent nodes.
var Tree = /** @class */ (function () {
/// Construct a new tree. You usually want to go through
/// [`Tree.build`](#tree.Tree^build) instead.
constructor(type,
function Tree(type,
/// The tree's child nodes. Children small enough to fit in a
/// `TreeBuffer` will be represented as such, other children can be
/// `TreeBuffer will be represented as such, other children can be
/// further `Tree` instances with their own internal structure.

@@ -247,3 +240,2 @@ children,

length) {
super();
this.type = type;

@@ -254,17 +246,15 @@ this.children = children;

}
get start() { return 0; }
get end() { return this.length; }
/// @internal
toString() {
let children = this.children.map(c => c.toString()).join();
return !this.name ? children :
(/\W/.test(this.name) && !this.type.prop(NodeProp.error) ? JSON.stringify(this.name) : this.name) +
Tree.prototype.toString = function () {
var children = this.children.map(function (c) { return c.toString(); }).join();
return !this.type.name ? children :
(/\W/.test(this.type.name) && !this.type.isError ? JSON.stringify(this.type.name) : this.type.name) +
(children.length ? "(" + children + ")" : "");
}
partial(start, end, offset, children, positions) {
for (let i = 0; i < this.children.length; i++) {
let from = this.positions[i];
};
Tree.prototype.partial = function (start, end, offset, children, positions) {
for (var i = 0; i < this.children.length; i++) {
var from = this.positions[i];
if (from > end)
break;
let child = this.children[i], to = from + child.length;
var child = this.children[i], to = from + child.length;
if (to < start)

@@ -280,3 +270,3 @@ continue;

}
}
};
/// Apply a set of edits to a tree, removing all nodes that were

@@ -288,23 +278,24 @@ /// touched by the edits, and moving remaining nodes so that their

/// subsequent incremental re-parse.
applyChanges(changes) {
Tree.prototype.applyChanges = function (changes) {
if (changes.length == 0)
return this;
let children = [], positions = [];
var children = [], positions = [];
function cutAt(tree, pos, side) {
let found = -1;
tree.iterate({
from: pos,
to: side < 0 ? 0 : tree.length,
enter() { return found < 0 ? undefined : false; },
leave(type, start, end) {
if (found < 0 && (side < 0 ? end <= pos : start >= pos) && !type.prop(NodeProp.error))
found = side < 0 ? Math.min(pos, end - 1) : Math.max(pos, start + 1);
}
});
return found > -1 ? found : side < 0 ? 0 : tree.length;
var cursor = tree.cursor(pos, -side);
for (;;) {
if (!cursor.enter(side, pos))
for (;;) {
if ((side < 0 ? cursor.to <= pos : cursor.from >= pos) && !cursor.type.isError)
return side < 0 ? Math.min(pos, cursor.to - 1) : Math.max(pos, cursor.from + 1);
if (cursor.sibling(side))
break;
if (!cursor.parent())
return side < 0 ? 0 : tree.length;
}
}
}
let off = 0;
for (let i = 0, pos = 0;; i++) {
let next = i == changes.length ? null : changes[i];
let nextPos = next ? cutAt(this, next.fromA, -1) : this.length;
var off = 0;
for (var i = 0, pos = 0;; i++) {
var next = i == changes.length ? null : changes[i];
var nextPos = next ? cutAt(this, next.fromA, -1) : this.length;
if (nextPos > pos)

@@ -318,13 +309,13 @@ this.partial(pos, nextPos, off, children, positions);

return new Tree(NodeType.none, children, positions, this.length + off);
}
};
/// Take the part of the tree up to the given position.
cut(at) {
Tree.prototype.cut = function (at) {
if (at >= this.length)
return this;
let children = [], positions = [];
for (let i = 0; i < this.children.length; i++) {
let from = this.positions[i];
var children = [], positions = [];
for (var i = 0; i < this.children.length; i++) {
var from = this.positions[i];
if (from >= at)
break;
let child = this.children[i], to = from + child.length;
var child = this.children[i], to = from + child.length;
children.push(to <= at ? child : child.cut(at - from));

@@ -334,118 +325,79 @@ positions.push(from);

return new Tree(this.type, children, positions, at);
}
iterate({ from = this.start, to = this.end, enter, leave }) {
let iter = new Iteration(enter, leave);
this.iterInner(from, to, 0, iter);
return iter.result;
}
/// @internal
iterInner(from, to, offset, iter) {
if (this.type.name && !iter.doEnter(this.type, offset, offset + this.length))
return;
if (from <= to) {
for (let i = 0; i < this.children.length && !iter.done; i++) {
let child = this.children[i], start = this.positions[i] + offset, end = start + child.length;
if (start > to)
break;
if (end < from)
continue;
child.iterInner(from, to, start, iter);
}
};
/// Get a [tree cursor](#tree.TreeCursor) rooted at this tree. When
/// `pos` is given, the cursor is [moved](#tree.TreeCursor.moveTo)
/// to the given position and side.
Tree.prototype.cursor = function (pos, side) {
if (side === void 0) { side = 0; }
var scope = (pos != null && CachedNode.get(this)) || this.topNode;
var cursor = new TreeCursor(scope);
if (pos != null) {
cursor.moveTo(pos, side);
CachedNode.set(this, cursor.tree);
}
else {
for (let i = this.children.length - 1; i >= 0 && !iter.done; i--) {
let child = this.children[i], start = this.positions[i] + offset, end = start + child.length;
if (end < to)
break;
if (start > from)
return cursor;
};
Object.defineProperty(Tree.prototype, "topNode", {
/// Get a [syntax node](#tree.SyntaxNode) object for the top of the
/// tree.
get: function () {
return new TreeNode(this, 0, 0, null);
},
enumerable: true,
configurable: true
});
/// Get the [syntax node](#tree.SyntaxNode) at the given position.
/// If `side` is -1, this will move into nodes that end at the
/// position. If 1, it'll move into nodes that start at the
/// position. With 0, it'll only enter nodes that cover the position
/// from both sides.
Tree.prototype.resolve = function (pos, side) {
if (side === void 0) { side = 0; }
return this.cursor(pos, side).node;
};
/// Iterate over the tree and its children, calling `enter` for any
/// node that touches the `from`/`to` region (if given) before
/// running over such a node's children, and `leave` (if given) when
/// leaving the node. When `enter` returns `false`, the given node
/// will not have its children iterated over (or `leave` called).
Tree.prototype.iterate = function (spec) {
var enter = spec.enter, leave = spec.leave, _a = spec.from, from = _a === void 0 ? 0 : _a, _b = spec.to, to = _b === void 0 ? this.length : _b;
for (var c = this.cursor();;) {
var mustLeave = false;
if (c.from <= to && c.to >= from && (c.type.isRepeated || enter(c.type, c.from, c.to) !== false)) {
if (c.firstChild())
continue;
child.iterInner(from, to, start, iter);
mustLeave = true;
}
}
if (iter.leave && this.type.name)
iter.leave(this.type, offset, offset + this.length);
return;
}
/// @internal
resolveAt(pos) {
if (cacheRoot == this) {
for (let tree = cached;;) {
let next = tree.parent;
if (!next)
for (;;) {
if (mustLeave && leave)
leave(c.type, c.from, c.to);
if (c.nextSibling())
break;
if (tree.start < pos && tree.end > pos)
return tree.resolve(pos);
tree = next;
if (!c.parent())
return;
mustLeave = true;
}
}
cacheRoot = this;
return cached = this.resolveInner(pos, 0, this);
}
childBefore(pos) {
return this.findChild(pos, -1, 0, this);
}
childAfter(pos) {
return this.findChild(pos, 1, 0, this);
}
/// @internal
findChild(pos, side, start, parent) {
for (let i = 0; i < this.children.length; i++) {
let childStart = this.positions[i] + start, select = -1;
if (childStart >= pos) {
if (side < 0 && i > 0)
select = i - 1;
else if (side > 0)
select = i;
else
break;
}
if (select < 0 && (childStart + this.children[i].length > pos || side < 0 && i == this.children.length - 1))
select = i;
if (select >= 0) {
let child = this.children[select], childStart = this.positions[select] + start;
if (child.length == 0 && childStart == pos)
continue;
if (child instanceof Tree) {
if (child.type.name)
return new NodeSubtree(child, childStart, parent);
return child.findChild(pos, side, childStart, parent);
}
else {
let found = child.findIndex(pos, side, childStart, 0, child.buffer.length);
if (found > -1)
return new BufferSubtree(child, childStart, found, parent);
}
}
}
return null;
}
/// @internal
resolveInner(pos, start, parent) {
let found = this.findChild(pos, 0, start, parent);
return found ? found.resolveAt(pos) : parent;
}
};
/// Append another tree to this tree. `other` must have empty space
/// big enough to fit this tree at its start.
append(other) {
Tree.prototype.append = function (other) {
if (other.children.length && other.positions[0] < this.length)
throw new Error("Can't append overlapping trees");
return new Tree(this.type, this.children.concat(other.children), this.positions.concat(other.positions), other.length);
}
};
/// Balance the direct children of this tree.
balance(maxBufferLength = DefaultBufferLength) {
Tree.prototype.balance = function (maxBufferLength) {
if (maxBufferLength === void 0) { maxBufferLength = DefaultBufferLength; }
return this.children.length <= BalanceBranchFactor ? this
: balanceRange(this.type, NodeType.none, this.children, this.positions, 0, this.children.length, 0, maxBufferLength, this.length);
}
};
/// Build a tree from a postfix-ordered buffer of node information,
/// or a cursor over such a buffer.
static build(data) { return buildTree(data); }
}
/// The empty tree
Tree.empty = new Tree(NodeType.none, [], [], 0);
Tree.prototype.parent = null;
// Top-level `resolveAt` calls store their last result here, so that
// if the next call is near the last, parent trees can be cheaply
// reused.
let cacheRoot = Tree.empty;
let cached = Tree.empty;
/// or a cursor over such a buffer.
Tree.build = function (data) { return buildTree(data); };
/// The empty tree
Tree.empty = new Tree(NodeType.none, [], [], 0);
return Tree;
}());
/// Tree buffers contain (type, start, end, endIndex) quads for each

@@ -455,5 +407,5 @@ /// node. In such a buffer, nodes are stored in prefix order (parents

/// children belong to it)
export class TreeBuffer {
var TreeBuffer = /** @class */ (function () {
/// Create a tree buffer @internal
constructor(
function TreeBuffer(
/// @internal

@@ -464,3 +416,4 @@ buffer,

/// @internal
group, type = NodeType.none) {
group, type) {
if (type === void 0) { type = NodeType.none; }
this.buffer = buffer;

@@ -472,31 +425,33 @@ this.length = length;

/// @internal
toString() {
let parts = [];
for (let index = 0; index < this.buffer.length;)
index = this.childToString(index, parts);
return parts.join(",");
}
TreeBuffer.prototype.toString = function () {
var result = [];
for (var index = 0; index < this.buffer.length;) {
result.push(this.childString(index));
index = this.buffer[index + 3];
}
return result.join(",");
};
/// @internal
childToString(index, parts) {
let id = this.buffer[index], endIndex = this.buffer[index + 3];
let type = this.group.types[id], result = type.name;
if (/\W/.test(result) && !type.prop(NodeProp.error))
TreeBuffer.prototype.childString = function (index) {
var id = this.buffer[index], endIndex = this.buffer[index + 3];
var type = this.group.types[id], result = type.name;
if (/\W/.test(result) && !type.isError)
result = JSON.stringify(result);
index += 4;
if (endIndex > index) {
let children = [];
while (index < endIndex)
index = this.childToString(index, children);
result += "(" + children.join(",") + ")";
if (endIndex == index)
return result;
var children = [];
while (index < endIndex) {
children.push(this.childString(index));
index = this.buffer[index + 3];
}
parts.push(result);
return index;
}
return result + "(" + children.join(",") + ")";
};
/// @internal
cut(at) {
let cutPoint = 0;
TreeBuffer.prototype.cut = function (at) {
var cutPoint = 0;
while (cutPoint < this.buffer.length && this.buffer[cutPoint + 1] < at)
cutPoint += 4;
let newBuffer = new Uint16Array(cutPoint);
for (let i = 0; i < cutPoint; i += 4) {
var newBuffer = new Uint16Array(cutPoint);
for (var i = 0; i < cutPoint; i += 4) {
newBuffer[i] = this.buffer[i];

@@ -508,198 +463,519 @@ newBuffer[i + 1] = this.buffer[i + 1];

return new TreeBuffer(newBuffer, Math.min(at, this.length), this.group);
};
/// @internal
TreeBuffer.prototype.findChild = function (startIndex, endIndex, dir, after) {
var buffer = this.buffer, pick = -1;
for (var i = startIndex; i != endIndex; i = buffer[i + 3]) {
if (after != -100000000 /* None */) {
var start = buffer[i + 1], end = buffer[i + 2];
if (dir > 0) {
if (end > after)
pick = i;
if (end > after)
break;
}
else {
if (start < after)
pick = i;
if (end >= after)
break;
}
}
else {
pick = i;
if (dir > 0)
break;
}
}
return pick;
};
return TreeBuffer;
}());
var TreeNode = /** @class */ (function () {
function TreeNode(node, from, index, _parent) {
this.node = node;
this.from = from;
this.index = index;
this._parent = _parent;
}
iterate({ from = 0, to = this.length, enter, leave }) {
let iter = new Iteration(enter, leave);
this.iterInner(from, to, 0, iter);
return iter.result;
Object.defineProperty(TreeNode.prototype, "type", {
get: function () { return this.node.type; },
enumerable: true,
configurable: true
});
Object.defineProperty(TreeNode.prototype, "name", {
get: function () { return this.node.type.name; },
enumerable: true,
configurable: true
});
Object.defineProperty(TreeNode.prototype, "to", {
get: function () { return this.from + this.node.length; },
enumerable: true,
configurable: true
});
TreeNode.prototype.nextChild = function (i, dir, after) {
for (var parent = this;;) {
for (var _a = parent.node, children = _a.children, positions = _a.positions, e = dir > 0 ? children.length : -1; i != e; i += dir) {
var next = children[i], start = positions[i] + parent.from;
if (after != -100000000 /* None */ && (dir < 0 ? start >= after : start + next.length <= after))
continue;
if (next instanceof TreeBuffer) {
var index = next.findChild(0, next.buffer.length, dir, after == -100000000 /* None */ ? -100000000 /* None */ : after - start);
if (index > -1)
return new BufferNode(new BufferContext(parent, next, i, start), null, index);
}
else if (!next.type.isRepeated || hasChild(next)) {
var inner = new TreeNode(next, start, i, parent);
return !inner.type.isRepeated ? inner : inner.nextChild(dir < 0 ? next.children.length - 1 : 0, dir, after);
}
}
if (!parent.type.isRepeated)
return null;
i = parent.index + dir;
parent = parent._parent;
}
};
Object.defineProperty(TreeNode.prototype, "firstChild", {
get: function () { return this.nextChild(0, 1, -100000000 /* None */); },
enumerable: true,
configurable: true
});
Object.defineProperty(TreeNode.prototype, "lastChild", {
get: function () { return this.nextChild(this.node.children.length - 1, -1, -100000000 /* None */); },
enumerable: true,
configurable: true
});
TreeNode.prototype.childAfter = function (pos) { return this.nextChild(0, 1, pos); };
TreeNode.prototype.childBefore = function (pos) { return this.nextChild(this.node.children.length - 1, -1, pos); };
TreeNode.prototype.nextSignificant = function () {
var val = this;
while (val.type.isRepeated)
val = val._parent;
return val;
};
Object.defineProperty(TreeNode.prototype, "parent", {
get: function () {
return this._parent ? this._parent.nextSignificant() : null;
},
enumerable: true,
configurable: true
});
Object.defineProperty(TreeNode.prototype, "nextSibling", {
get: function () {
return this._parent ? this._parent.nextChild(this.index + 1, 1, -1) : null;
},
enumerable: true,
configurable: true
});
Object.defineProperty(TreeNode.prototype, "prevSibling", {
get: function () {
return this._parent ? this._parent.nextChild(this.index - 1, -1, -1) : null;
},
enumerable: true,
configurable: true
});
Object.defineProperty(TreeNode.prototype, "cursor", {
get: function () { return new TreeCursor(this); },
enumerable: true,
configurable: true
});
TreeNode.prototype.resolve = function (pos, side) {
if (side === void 0) { side = 0; }
return this.cursor.moveTo(pos, side).node;
};
TreeNode.prototype.getChild = function (type, before, after) {
if (before === void 0) { before = null; }
if (after === void 0) { after = null; }
var r = getChildren(this, type, before, after);
return r.length ? r[0] : null;
};
TreeNode.prototype.getChildren = function (type, before, after) {
if (before === void 0) { before = null; }
if (after === void 0) { after = null; }
return getChildren(this, type, before, after);
};
/// @internal
TreeNode.prototype.toString = function () { return this.node.toString(); };
return TreeNode;
}());
function getChildren(node, type, before, after) {
var cur = node.cursor, result = [];
if (!cur.firstChild())
return result;
if (before != null)
while (!cur.type.is(before))
if (!cur.nextSibling())
return result;
for (;;) {
if (after != null && cur.type.is(after))
return result;
if (cur.type.is(type))
result.push(cur.node);
if (!cur.nextSibling())
return after == null ? result : [];
}
}
var BufferContext = /** @class */ (function () {
function BufferContext(parent, buffer, index, start) {
this.parent = parent;
this.buffer = buffer;
this.index = index;
this.start = start;
}
return BufferContext;
}());
var BufferNode = /** @class */ (function () {
function BufferNode(context, _parent, index) {
this.context = context;
this._parent = _parent;
this.index = index;
this.type = context.buffer.group.types[context.buffer.buffer[index]];
}
Object.defineProperty(BufferNode.prototype, "name", {
get: function () { return this.type.name; },
enumerable: true,
configurable: true
});
Object.defineProperty(BufferNode.prototype, "from", {
get: function () { return this.context.start + this.context.buffer.buffer[this.index + 1]; },
enumerable: true,
configurable: true
});
Object.defineProperty(BufferNode.prototype, "to", {
get: function () { return this.context.start + this.context.buffer.buffer[this.index + 2]; },
enumerable: true,
configurable: true
});
BufferNode.prototype.child = function (dir, after) {
var buffer = this.context.buffer;
var index = buffer.findChild(this.index + 4, buffer.buffer[this.index + 3], dir, after == -100000000 /* None */ ? -100000000 /* None */ : after - this.context.start);
return index < 0 ? null : new BufferNode(this.context, this, index);
};
Object.defineProperty(BufferNode.prototype, "firstChild", {
get: function () { return this.child(1, -100000000 /* None */); },
enumerable: true,
configurable: true
});
Object.defineProperty(BufferNode.prototype, "lastChild", {
get: function () { return this.child(-1, -100000000 /* None */); },
enumerable: true,
configurable: true
});
BufferNode.prototype.childAfter = function (pos) { return this.child(1, pos); };
BufferNode.prototype.childBefore = function (pos) { return this.child(-1, pos); };
Object.defineProperty(BufferNode.prototype, "parent", {
get: function () {
return this._parent || this.context.parent.nextSignificant();
},
enumerable: true,
configurable: true
});
BufferNode.prototype.externalSibling = function (dir) {
return this._parent ? null : this.context.parent.nextChild(this.context.index + dir, dir, -1);
};
Object.defineProperty(BufferNode.prototype, "nextSibling", {
get: function () {
var buffer = this.context.buffer;
var after = buffer.buffer[this.index + 3];
if (after < (this._parent ? buffer.buffer[this._parent.index + 3] : buffer.buffer.length))
return new BufferNode(this.context, this._parent, after);
return this.externalSibling(1);
},
enumerable: true,
configurable: true
});
Object.defineProperty(BufferNode.prototype, "prevSibling", {
get: function () {
var buffer = this.context.buffer;
var parentStart = this._parent ? this._parent.index + 4 : 0;
if (this.index == parentStart)
return this.externalSibling(-1);
return new BufferNode(this.context, this._parent, buffer.findChild(parentStart, this.index, -1, -1));
},
enumerable: true,
configurable: true
});
Object.defineProperty(BufferNode.prototype, "cursor", {
get: function () { return new TreeCursor(this); },
enumerable: true,
configurable: true
});
BufferNode.prototype.resolve = function (pos, side) {
if (side === void 0) { side = 0; }
return this.cursor.moveTo(pos, side).node;
};
/// @internal
iterInner(from, to, offset, iter) {
if (from <= to) {
for (let index = 0; index < this.buffer.length;)
index = this.iterChild(from, to, offset, index, iter);
BufferNode.prototype.toString = function () { return this.context.buffer.childString(this.index); };
BufferNode.prototype.getChild = function (type, before, after) {
if (before === void 0) { before = null; }
if (after === void 0) { after = null; }
var r = getChildren(this, type, before, after);
return r.length ? r[0] : null;
};
BufferNode.prototype.getChildren = function (type, before, after) {
if (before === void 0) { before = null; }
if (after === void 0) { after = null; }
return getChildren(this, type, before, after);
};
return BufferNode;
}());
/// A tree cursor object focuses on a given node in a syntax tree, and
/// allows you to move to adjacent nodes.
var TreeCursor = /** @class */ (function () {
/// @internal
function TreeCursor(node) {
this.buffer = null;
this.stack = [];
this.index = 0;
this.bufferNode = null;
if (node instanceof TreeNode) {
this.yieldNode(node);
}
else {
this.iterRev(from, to, offset, 0, this.buffer.length, iter);
this.tree = node.context.parent;
this.buffer = node.context;
for (var n = node._parent; n; n = n._parent)
this.stack.unshift(n.index);
this.bufferNode = node;
this.yieldBuf(node.index);
}
}
Object.defineProperty(TreeCursor.prototype, "name", {
/// Shorthand for `.type.name`.
get: function () { return this.type.name; },
enumerable: true,
configurable: true
});
TreeCursor.prototype.yieldNode = function (node) {
if (!node)
return false;
this.tree = node;
this.type = node.type;
this.from = node.from;
this.to = node.to;
return true;
};
TreeCursor.prototype.yieldBuf = function (index, type) {
this.index = index;
var _a = this.buffer, start = _a.start, buffer = _a.buffer;
this.type = type || buffer.group.types[buffer.buffer[index]];
this.from = start + buffer.buffer[index + 1];
this.to = start + buffer.buffer[index + 2];
return true;
};
TreeCursor.prototype.yield = function (node) {
if (!node)
return false;
if (node instanceof TreeNode) {
this.buffer = null;
return this.yieldNode(node);
}
this.buffer = node.context;
return this.yieldBuf(node.index, node.type);
};
/// @internal
iterChild(from, to, offset, index, iter) {
let type = this.group.types[this.buffer[index++]], start = this.buffer[index++] + offset, end = this.buffer[index++] + offset, endIndex = this.buffer[index++];
if (start > to)
return this.buffer.length;
if (end >= from && iter.doEnter(type, start, end)) {
while (index < endIndex && !iter.done)
index = this.iterChild(from, to, offset, index, iter);
if (iter.leave)
iter.leave(type, start, end);
TreeCursor.prototype.toString = function () {
return this.buffer ? this.buffer.buffer.childString(this.index) : this.tree.toString();
};
/// @internal
TreeCursor.prototype.enter = function (dir, after) {
if (!this.buffer)
return this.yield(this.tree.nextChild(dir < 0 ? this.tree.node.children.length - 1 : 0, dir, after));
var buffer = this.buffer.buffer;
var index = buffer.findChild(this.index + 4, buffer.buffer[this.index + 3], dir, after == -100000000 /* None */ ? -100000000 /* None */ : after - this.buffer.start);
if (index < 0)
return false;
this.stack.push(this.index);
return this.yieldBuf(index);
};
/// Move the cursor to this node's first child. When this returns
/// false, the node has no child, and the cursor has not been moved.
TreeCursor.prototype.firstChild = function () { return this.enter(1, -100000000 /* None */); };
/// Move the cursor to this node's last child.
TreeCursor.prototype.lastChild = function () { return this.enter(-1, -100000000 /* None */); };
/// Move the cursor to the first child that starts at or after `pos`.
TreeCursor.prototype.childAfter = function (pos) { return this.enter(1, pos); };
/// Move to the last child that ends at or before `pos`.
TreeCursor.prototype.childBefore = function (pos) { return this.enter(-1, pos); };
/// Move the node's parent node, if this isn't the top node.
TreeCursor.prototype.parent = function () {
if (!this.buffer)
return this.yieldNode(this.tree.parent);
if (this.stack.length)
return this.yieldBuf(this.stack.pop());
var parent = this.buffer.parent.nextSignificant();
this.buffer = null;
return this.yieldNode(parent);
};
/// @internal
TreeCursor.prototype.sibling = function (dir) {
if (!this.buffer)
return this.tree._parent ? this.yield(this.tree._parent.nextChild(this.tree.index + dir, dir, -100000000 /* None */)) : false;
var buffer = this.buffer.buffer, d = this.stack.length - 1;
if (dir < 0) {
var parentStart = d < 0 ? 0 : this.stack[d] + 4;
if (this.index != parentStart)
return this.yieldBuf(buffer.findChild(parentStart, this.index, -1, -100000000 /* None */));
}
return endIndex;
}
parentNodesByEnd(startIndex, endIndex) {
// Build up an array of node indices reflecting the order in which
// non-empty nodes end, to avoid having to scan for parent nodes
// at every position during reverse iteration.
let order = [];
let scan = (index) => {
let end = this.buffer[index + 3];
if (end == index + 4)
return end;
for (let i = index + 4; i < end;)
i = scan(i);
order.push(index);
return end;
};
for (let index = startIndex; index < endIndex;)
index = scan(index);
return order;
}
/// @internal
iterRev(from, to, offset, startIndex, endIndex, iter) {
let endOrder = this.parentNodesByEnd(startIndex, endIndex);
// Index range for the next non-empty node
let nextStart = -1, nextEnd = -1;
let takeNext = () => {
if (endOrder.length > 0) {
nextStart = endOrder.pop();
nextEnd = this.buffer[nextStart + 3];
else {
var after_1 = buffer.buffer[this.index + 3];
if (after_1 < (d < 0 ? buffer.buffer.length : buffer.buffer[this.stack[d] + 3]))
return this.yieldBuf(after_1);
}
return d < 0 ? this.yield(this.buffer.parent.nextChild(this.buffer.index + dir, dir, -100000000 /* None */)) : false;
};
/// Move to this node's next sibling, if any.
TreeCursor.prototype.nextSibling = function () { return this.sibling(1); };
/// Move to this node's previous sibling, if any.
TreeCursor.prototype.prevSibling = function () { return this.sibling(-1); };
TreeCursor.prototype.atLastNode = function (dir) {
var _a, _b;
var index, parent, buffer = this.buffer;
if (buffer) {
if (dir > 0) {
if (this.index < buffer.buffer.buffer.length)
return false;
}
else {
nextEnd = -1;
for (var i = 0; i < this.index; i++)
if (buffer.buffer.buffer[i + 3] < this.index)
return false;
}
};
takeNext();
run: for (let index = endIndex; index > startIndex && !iter.done;) {
while (nextEnd == index) {
let base = nextStart;
let id = this.buffer[base], start = this.buffer[base + 1] + offset, end = this.buffer[base + 2] + offset;
takeNext();
if (start <= from && end >= to) {
if (!iter.doEnter(this.group.types[id], start, end)) {
// Skip the entire node
index = base;
while (nextEnd > base)
takeNext();
continue run;
}
}
(index = buffer.index, parent = buffer.parent);
}
else {
(_a = this.tree, index = _a.index, parent = _a._parent);
}
for (; parent; _b = parent, index = _b.index, parent = _b._parent, _b) {
for (var i = index + dir, e = dir < 0 ? -1 : parent.node.children.length; i != e; i += dir) {
var child = parent.node.children[i];
if (!child.type.isRepeated || child instanceof TreeBuffer || hasChild(child))
return false;
}
let endIndex = this.buffer[--index], end = this.buffer[--index] + offset, start = this.buffer[--index] + offset, id = this.buffer[--index];
if (start > from || end < to)
continue;
if ((endIndex != index + 4 || iter.doEnter(this.group.types[id], start, end)) && iter.leave)
iter.leave(this.group.types[id], start, end);
}
}
/// @internal
findIndex(pos, side, start, from, to) {
let lastI = -1;
for (let i = from, buf = this.buffer; i < to;) {
let start1 = buf[i + 1] + start, end1 = buf[i + 2] + start;
let ignore = start1 == end1 && start1 == pos;
if (start1 >= pos) {
if (side > 0 && !ignore)
return i;
return true;
};
TreeCursor.prototype.move = function (dir) {
if (this.enter(dir, -100000000 /* None */))
return true;
for (;;) {
if (this.sibling(dir))
return true;
if (this.atLastNode(dir) || !this.parent())
return false;
}
};
/// Move to the next node in a
/// [pre-order](https://en.wikipedia.org/wiki/Tree_traversal#Pre-order_(NLR))
/// traversal, going from a node to its first child or, if the
/// current node is empty, its next sibling or the next sibling of
/// the first parent node that has one.
TreeCursor.prototype.next = function () { return this.move(1); };
/// Move to the next node in a last-to-first pre-order traveral. A
/// node is followed by ist last child or, if it has none, its
/// previous sibling or the previous sibling of the first parent
/// node that has one.
TreeCursor.prototype.prev = function () { return this.move(-1); };
/// Move the cursor to the innermost node that covers `pos`. If
/// `side` is -1, it will enter nodes that end at `pos`. If it is 1,
/// it will enter nodes that start at `pos`.
TreeCursor.prototype.moveTo = function (pos, side) {
if (side === void 0) { side = 0; }
// Move up to a node that actually holds the position, if possible
while (this.from == this.to ||
(side < 1 ? this.from >= pos : this.from > pos) ||
(side > -1 ? this.to <= pos : this.to < pos))
if (!this.parent())
break;
// Then scan down into child nodes as far as possible
for (;;) {
if (side < 0 ? !this.childBefore(pos) : !this.childAfter(pos))
break;
if (this.from == this.to ||
(side < 1 ? this.from >= pos : this.from > pos) ||
(side > -1 ? this.to <= pos : this.to < pos)) {
this.parent();
break;
}
if (end1 > pos)
return i;
if (!ignore)
lastI = i;
i = buf[i + 3];
}
return side < 0 ? lastI : -1;
}
return this;
};
Object.defineProperty(TreeCursor.prototype, "node", {
/// Get a [syntax node](#tree.SyntaxNode) at the cursor's current
/// position.
get: function () {
if (!this.buffer)
return this.tree;
var cache = this.bufferNode, result = null, depth = 0;
if (cache && cache.context == this.buffer) {
scan: for (var index = this.index, d = this.stack.length; d >= 0;) {
for (var c = cache; c; c = c._parent)
if (c.index == index) {
if (index == this.index)
return c;
result = c;
depth = d + 1;
break scan;
}
index = this.stack[--d];
}
}
for (var i = depth; i < this.stack.length; i++)
result = new BufferNode(this.buffer, result, this.stack[i]);
return this.bufferNode = new BufferNode(this.buffer, result, this.index);
},
enumerable: true,
configurable: true
});
return TreeCursor;
}());
function hasChild(tree) {
return tree.children.some(function (ch) { return !ch.type.isRepeated || ch instanceof TreeBuffer || hasChild(ch); });
}
class NodeSubtree extends Subtree {
constructor(node, start, parent) {
super();
this.node = node;
this.start = start;
this.parent = parent;
}
get type() { return this.node.type; }
get end() { return this.start + this.node.length; }
resolveAt(pos) {
if (pos <= this.start || pos >= this.end)
return this.parent.resolveAt(pos);
return this.node.resolveInner(pos, this.start, this);
}
childBefore(pos) {
return this.node.findChild(pos, -1, this.start, this);
}
childAfter(pos) {
return this.node.findChild(pos, 1, this.start, this);
}
toString() { return this.node.toString(); }
iterate({ from = this.start, to = this.end, enter, leave }) {
let iter = new Iteration(enter, leave);
this.node.iterInner(from, to, this.start, iter);
return iter.result;
}
}
class BufferSubtree extends Subtree {
constructor(buffer, bufferStart, index, parent) {
super();
var FlatBufferCursor = /** @class */ (function () {
function FlatBufferCursor(buffer, index) {
this.buffer = buffer;
this.bufferStart = bufferStart;
this.index = index;
this.parent = parent;
}
get type() { return this.buffer.group.types[this.buffer.buffer[this.index]]; }
get start() { return this.buffer.buffer[this.index + 1] + this.bufferStart; }
get end() { return this.buffer.buffer[this.index + 2] + this.bufferStart; }
get endIndex() { return this.buffer.buffer[this.index + 3]; }
childBefore(pos) {
let index = this.buffer.findIndex(pos, -1, this.bufferStart, this.index + 4, this.endIndex);
return index < 0 ? null : new BufferSubtree(this.buffer, this.bufferStart, index, this);
}
childAfter(pos) {
let index = this.buffer.findIndex(pos, 1, this.bufferStart, this.index + 4, this.endIndex);
return index < 0 ? null : new BufferSubtree(this.buffer, this.bufferStart, index, this);
}
iterate({ from = this.start, to = this.end, enter, leave }) {
let iter = new Iteration(enter, leave);
if (from <= to)
this.buffer.iterChild(from, to, this.bufferStart, this.index, iter);
else
this.buffer.iterRev(from, to, this.bufferStart, this.index, this.endIndex, iter);
return iter.result;
}
resolveAt(pos) {
if (pos <= this.start || pos >= this.end)
return this.parent.resolveAt(pos);
let found = this.buffer.findIndex(pos, 0, this.bufferStart, this.index + 4, this.endIndex);
return found < 0 ? this : new BufferSubtree(this.buffer, this.bufferStart, found, this).resolveAt(pos);
}
toString() {
let result = [];
this.buffer.childToString(this.index, result);
return result.join("");
}
}
class FlatBufferCursor {
constructor(buffer, index) {
this.buffer = buffer;
this.index = index;
}
get id() { return this.buffer[this.index - 4]; }
get start() { return this.buffer[this.index - 3]; }
get end() { return this.buffer[this.index - 2]; }
get size() { return this.buffer[this.index - 1]; }
get pos() { return this.index; }
next() { this.index -= 4; }
fork() { return new FlatBufferCursor(this.buffer, this.index); }
}
const BalanceBranchFactor = 8;
Object.defineProperty(FlatBufferCursor.prototype, "id", {
get: function () { return this.buffer[this.index - 4]; },
enumerable: true,
configurable: true
});
Object.defineProperty(FlatBufferCursor.prototype, "start", {
get: function () { return this.buffer[this.index - 3]; },
enumerable: true,
configurable: true
});
Object.defineProperty(FlatBufferCursor.prototype, "end", {
get: function () { return this.buffer[this.index - 2]; },
enumerable: true,
configurable: true
});
Object.defineProperty(FlatBufferCursor.prototype, "size", {
get: function () { return this.buffer[this.index - 1]; },
enumerable: true,
configurable: true
});
Object.defineProperty(FlatBufferCursor.prototype, "pos", {
get: function () { return this.index; },
enumerable: true,
configurable: true
});
FlatBufferCursor.prototype.next = function () { this.index -= 4; };
FlatBufferCursor.prototype.fork = function () { return new FlatBufferCursor(this.buffer, this.index); };
return FlatBufferCursor;
}());
var BalanceBranchFactor = 8;
function buildTree(data) {
let { buffer, group, topID = 0, maxBufferLength = DefaultBufferLength, reused = [], minRepeatType = group.types.length } = data;
let cursor = Array.isArray(buffer) ? new FlatBufferCursor(buffer, buffer.length) : buffer;
let types = group.types;
var _a = data, buffer = _a.buffer, group = _a.group, _b = _a.topID, topID = _b === void 0 ? 0 : _b, _c = _a.maxBufferLength, maxBufferLength = _c === void 0 ? DefaultBufferLength : _c, _d = _a.reused, reused = _d === void 0 ? [] : _d, _e = _a.minRepeatType, minRepeatType = _e === void 0 ? group.types.length : _e;
var cursor = Array.isArray(buffer) ? new FlatBufferCursor(buffer, buffer.length) : buffer;
var types = group.types;
function takeNode(parentStart, minPos, children, positions, inRepeat) {
let { id, start, end, size } = cursor;
var id = cursor.id, start = cursor.start, end = cursor.end, size = cursor.size;
while (id == inRepeat) {
cursor.next();
({ id, start, end, size } = cursor);
(id = cursor.id, start = cursor.start, end = cursor.end, size = cursor.size);
}
let startPos = start - parentStart;
var startPos = start - parentStart;
if (size < 0) { // Reused node

@@ -711,17 +987,17 @@ children.push(reused[id]);

}
let type = types[id], node, buffer;
var type = types[id], node, buffer;
if (end - start <= maxBufferLength && (buffer = findBufferSize(cursor.pos - minPos, inRepeat))) {
// Small enough for a buffer, and no reused nodes inside
let data = new Uint16Array(buffer.size - buffer.skip);
let endPos = cursor.pos - buffer.size, index = data.length;
var data_1 = new Uint16Array(buffer.size - buffer.skip);
var endPos = cursor.pos - buffer.size, index = data_1.length;
while (cursor.pos > endPos)
index = copyToBuffer(buffer.start, data, index, inRepeat);
node = new TreeBuffer(data, end - buffer.start, group, inRepeat < 0 ? NodeType.none : types[inRepeat]);
index = copyToBuffer(buffer.start, data_1, index, inRepeat);
node = new TreeBuffer(data_1, end - buffer.start, group, inRepeat < 0 ? NodeType.none : types[inRepeat]);
startPos = buffer.start - parentStart;
}
else { // Make it a node
let endPos = cursor.pos - size;
var endPos = cursor.pos - size;
cursor.next();
let localChildren = [], localPositions = [];
let localInRepeat = id >= minRepeatType ? id : -1;
var localChildren = [], localPositions = [];
var localInRepeat = id >= minRepeatType ? id : -1;
while (cursor.pos > endPos)

@@ -746,6 +1022,6 @@ takeNode(start, endPos, localChildren, localPositions, localInRepeat);

// (`maxSize`) or before such a node.
let fork = cursor.fork();
let size = 0, start = 0, skip = 0, minStart = fork.end - maxBufferLength;
let result = { size: 0, start: 0, skip: 0 };
scan: for (let minPos = fork.pos - maxSize; fork.pos > minPos;) {
var fork = cursor.fork();
var size = 0, start = 0, skip = 0, minStart = fork.end - maxBufferLength;
var result = { size: 0, start: 0, skip: 0 };
scan: for (var minPos = fork.pos - maxSize; fork.pos > minPos;) {
// Pretend nested repeat nodes of the same type don't exist

@@ -763,7 +1039,7 @@ if (fork.id == inRepeat) {

}
let nodeSize = fork.size, startPos = fork.pos - nodeSize;
var nodeSize = fork.size, startPos = fork.pos - nodeSize;
if (nodeSize < 0 || startPos < minPos || fork.start < minStart)
break;
let localSkipped = fork.id >= minRepeatType ? 4 : 0;
let nodeStart = fork.start;
var localSkipped = fork.id >= minRepeatType ? 4 : 0;
var nodeStart = fork.start;
fork.next();

@@ -789,9 +1065,9 @@ while (fork.pos > startPos) {

function copyToBuffer(bufferStart, buffer, index, inRepeat) {
let { id, start, end, size } = cursor;
var id = cursor.id, start = cursor.start, end = cursor.end, size = cursor.size;
cursor.next();
if (id == inRepeat)
return index;
let startIndex = index;
var startIndex = index;
if (size > 4) {
let endPos = cursor.pos - (size - 4);
var endPos = cursor.pos - (size - 4);
while (cursor.pos > endPos)

@@ -808,12 +1084,12 @@ index = copyToBuffer(bufferStart, buffer, index, inRepeat);

}
let children = [], positions = [];
var children = [], positions = [];
while (cursor.pos > 0)
takeNode(0, 0, children, positions, -1);
let length = children.length ? positions[0] + children[0].length : 0;
var length = children.length ? positions[0] + children[0].length : 0;
return new Tree(group.types[topID], children.reverse(), positions.reverse(), length);
}
function balanceRange(outerType, innerType, children, positions, from, to, start, maxBufferLength, length) {
let localChildren = [], localPositions = [];
var localChildren = [], localPositions = [];
if (length <= maxBufferLength) {
for (let i = from; i < to; i++) {
for (var i = from; i < to; i++) {
localChildren.push(children[i]);

@@ -824,8 +1100,8 @@ localPositions.push(positions[i] - start);

else {
let maxChild = Math.max(maxBufferLength, Math.ceil(length * 1.5 / BalanceBranchFactor));
for (let i = from; i < to;) {
let groupFrom = i, groupStart = positions[i];
var maxChild = Math.max(maxBufferLength, Math.ceil(length * 1.5 / BalanceBranchFactor));
for (var i = from; i < to;) {
var groupFrom = i, groupStart = positions[i];
i++;
for (; i < to; i++) {
let nextEnd = positions[i] + children[i].length;
var nextEnd = positions[i] + children[i].length;
if (nextEnd - groupStart > maxChild)

@@ -835,5 +1111,5 @@ break;

if (i == groupFrom + 1) {
let only = children[groupFrom];
var only = children[groupFrom];
if (only instanceof Tree && only.type == innerType && only.length > maxChild << 1) { // Too big, collapse
for (let j = 0; j < only.children.length; j++) {
for (var j = 0; j < only.children.length; j++) {
localChildren.push(only.children[j]);

@@ -850,3 +1126,3 @@ localPositions.push(only.positions[j] + groupStart - start);

else {
let inner = balanceRange(innerType, innerType, children, positions, groupFrom, i, groupStart, maxBufferLength, positions[i - 1] + children[i - 1].length - groupStart);
var inner = balanceRange(innerType, innerType, children, positions, groupFrom, i, groupStart, maxBufferLength, positions[i - 1] + children[i - 1].length - groupStart);
if (innerType != NodeType.none && !containsType(inner.children, innerType))

@@ -862,6 +1138,11 @@ inner = new Tree(NodeType.none, inner.children, inner.positions, inner.length);

function containsType(nodes, type) {
for (let elt of nodes)
for (var _i = 0, nodes_1 = nodes; _i < nodes_1.length; _i++) {
var elt = nodes_1[_i];
if (elt.type == type)
return true;
}
return false;
}
export { DefaultBufferLength, NodeGroup, NodeProp, NodePropSource, NodeType, Tree, TreeBuffer, TreeCursor };
//# sourceMappingURL=tree.es.js.map

18

package.json
{
"name": "lezer-tree",
"version": "0.11.1",
"version": "0.12.0",
"description": "Syntax tree data structure for the lezer parser",

@@ -17,3 +17,10 @@ "main": "dist/tree.cjs",

"ist": "^1.1.1",
"typescript": "^3.7.2"
"rollup": "^2.27.1",
"@rollup/plugin-commonjs": "^15.1.0",
"@rollup/plugin-node-resolve": "^9.0.0",
"rollup-plugin-typescript2": "^0.27.2",
"typescript": "^3.7.2",
"@types/mocha": "^5.2.6",
"ts-node": "^8.0.3",
"mocha": "^8.1.3"
},

@@ -26,7 +33,6 @@ "files": ["dist"],

"scripts": {
"watch": "tsc --outDir dist -w -d",
"build:cjs": "tsc --outDir dist -d && mv dist/tree.js dist/tree.cjs",
"build:es": "tsc src/tree.ts --outDir . -m es2015 -t es2015 && mv tree.js dist/tree.es.js",
"prepare": "npm run build:cjs && npm run build:es"
"watch": "rollup -w -c rollup.config.js",
"prepare": "rollup -c rollup.config.js",
"test": "mocha -r ts-node/register/transpile-only test/test-*.ts"
}
}
dist/tree.js.map
dist/tree.cjs

Sorry, the diff of this file is not supported yet

SocketSocket SOC 2 Logo

Product

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

About

Packages

npm

Go

Maven

PyPI

Rubygems

Stay in touch

Get open source security insights delivered straight into your inbox.

  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc