Socket
Socket
Sign inDemoInstall

lezer-tree

Package Overview
Dependencies
0
Maintainers
1
Versions
25
Alerts
File Explorer

Advanced tools

npm Scripts
License

Install Socket

Detect and block malicious and high-risk dependencies

Install

Comparing version 0.1.1 to 0.2.0

16

CHANGELOG.md

@@ -0,1 +1,17 @@

## 0.2.0 (2019-08-02)
### Bug fixes
Fix incorrect node length calculation in `Tree.build`.
### New features
Tree nodes are now identified with tags.
New `Tag` data structure to represent node tags.
### Breaking changes
Drop support for grammar ids and node types.
## 0.1.1 (2019-07-09)

@@ -2,0 +18,0 @@

50

dist/tree.d.ts
export declare const DefaultBufferLength = 1024;
export declare function isTagged(type: number): boolean;
export declare function grammarID(type: number): number;
export declare function termID(type: number): number;
export declare function allocateGrammarID(): number;
export interface ChangedRange {

@@ -12,4 +8,4 @@ fromA: number;

}
export declare type EnterFunc<T> = (type: number, start: number, end: number) => T | false | undefined;
export declare type LeaveFunc = (type: number, start: number, end: number) => void;
export declare type EnterFunc<T> = (tag: Tag, start: number, end: number) => T | false | undefined;
export declare type LeaveFunc = (tag: Tag, start: number, end: number) => void;
declare class Iteration<T> {

@@ -21,7 +17,7 @@ readonly enter: EnterFunc<T>;

readonly done: boolean;
doEnter(type: number, start: number, end: number): boolean;
doEnter(tag: Tag, start: number, end: number): boolean;
}
export declare abstract class Subtree {
abstract parent: Subtree | null;
abstract type: number;
abstract tag: Tag;
abstract start: number;

@@ -31,3 +27,3 @@ abstract end: number;

readonly root: Tree;
abstract toString(tags?: TagMap<any>): string;
abstract toString(): string;
abstract iterate<T = any>(from: number, to: number, enter: EnterFunc<T>, leave?: LeaveFunc): T | undefined;

@@ -45,8 +41,11 @@ resolve(pos: number, side?: -1 | 0 | 1): Subtree;

readonly length: number;
readonly tags: readonly Tag[];
readonly type: number;
parent: null;
constructor(children: (Tree | TreeBuffer)[], positions: number[], length: number, type?: number);
constructor(children: (Tree | TreeBuffer)[], positions: number[], length: number, tags: readonly Tag[], type?: number);
readonly start: number;
toString(tags?: TagMap<any>): string;
readonly end: number;
readonly tag: Tag;
isPartOf(tags: readonly Tag[]): boolean;
toString(): string;
private partial;

@@ -65,3 +64,3 @@ applyChanges(changes: readonly ChangedRange[]): Tree;

balance(maxBufferLength?: number): Tree;
static build(buffer: BufferCursor | readonly number[], grammarID: number, maxBufferLength?: number, reused?: Tree[]): Tree;
static build(buffer: BufferCursor | readonly number[], tags: readonly Tag[], maxBufferLength?: number, reused?: Tree[]): Tree;
}

@@ -71,6 +70,6 @@ export declare class TreeBuffer {

readonly length: number;
readonly grammarID: number;
constructor(buffer: Uint16Array, length: number, grammarID: number);
toString(tags?: TagMap<any>): string;
childToString(index: number, parts: string[], tags?: TagMap<any>): number;
readonly tags: readonly Tag[];
constructor(buffer: Uint16Array, length: number, tags: readonly Tag[]);
toString(): string;
childToString(index: number, parts: string[]): number;
cut(at: number): TreeBuffer;

@@ -92,14 +91,11 @@ iterInner<T>(from: number, to: number, offset: number, iter: Iteration<T>): void;

}
export declare class TagMap<T> {
readonly grammars: {
readonly [id: number]: readonly (T | null)[];
};
constructor(grammars: {
readonly [id: number]: readonly (T | null)[];
});
get(type: number): T | null;
static single<T>(grammarID: number, values: readonly (T | null)[]): TagMap<T>;
static combine<T>(maps: TagMap<T>[]): TagMap<T>;
static empty: TagMap<any>;
export declare class Tag {
readonly tag: string;
private parts;
constructor(tag: string);
private find;
has(name: string, value?: string): boolean;
matches(tag: Tag): number;
static empty: Tag;
}
export {};

263

dist/tree.js

@@ -18,16 +18,4 @@ "use strict";

exports.DefaultBufferLength = 1024;
/// Checks whether the given node type is a tagged node.
// Checks whether the given node type is a tagged node.
function isTagged(type) { return (type & 1) > 0; }
exports.isTagged = isTagged;
var GRAMMAR_ID_MASK = (Math.pow(2, 14) - 1) << 16, TERM_ID_MASK = Math.pow(2, 16) - 1;
/// Get the ID of the grammar that a node type is part of.
function grammarID(type) { return type & GRAMMAR_ID_MASK; }
exports.grammarID = grammarID;
/// Get the term ID for the given node type.
function termID(type) { return type & TERM_ID_MASK; }
exports.termID = termID;
var nextGrammarID = 0;
/// Allocate a new unique grammar ID.
function allocateGrammarID() { return (nextGrammarID++) << 16; }
exports.allocateGrammarID = allocateGrammarID;
var Iteration = /** @class */ (function () {

@@ -44,4 +32,4 @@ function Iteration(enter, leave) {

});
Iteration.prototype.doEnter = function (type, start, end) {
var value = this.enter(type, start, end);
Iteration.prototype.doEnter = function (tag, start, end) {
var value = this.enter(tag, start, end);
if (value === undefined)

@@ -133,3 +121,3 @@ return true;

__extends(Tree, _super);
/// Construct a tree.
/// @internal
function Tree(

@@ -145,3 +133,5 @@ /// The tree's child nodes. Children small enough to fit in a

length,
/// This tree's node type. The root node has type 0.
/// Mapping from node types to tags for this grammar @internal
tags,
/// This tree's node type. The root node has type 0. @internal
type) {

@@ -153,2 +143,3 @@ if (type === void 0) { type = 0; }

_this.length = length;
_this.tags = tags;
_this.type = type;

@@ -158,2 +149,3 @@ return _this;

Object.defineProperty(Tree.prototype, "start", {
/// @internal
get: function () { return 0; },

@@ -163,8 +155,4 @@ enumerable: true,

});
Tree.prototype.toString = function (tags) {
var name = !isTagged(this.type) ? null : tags ? tags.get(this.type) : this.type;
var children = this.children.map(function (c) { return c.toString(tags); }).join();
return !name ? children : name + (children.length ? "(" + children + ")" : "");
};
Object.defineProperty(Tree.prototype, "end", {
/// @internal
get: function () { return this.length; },

@@ -174,2 +162,18 @@ enumerable: true,

});
Object.defineProperty(Tree.prototype, "tag", {
/// @internal
get: function () { return isTagged(this.type) ? this.tags[this.type >> 1] : Tag.empty; },
enumerable: true,
configurable: true
});
/// Check whether this tree's tag belongs to a given set of tags.
/// Can be used to determine that a node belongs to the grammar
/// defined by a specific parser.
Tree.prototype.isPartOf = function (tags) { return this.tags == tags; };
/// @internal
Tree.prototype.toString = function () {
var name = !isTagged(this.type) ? null : this.tag.tag;
var children = this.children.map(function (c) { return c.toString(); }).join();
return !name ? children : name + (children.length ? "(" + children + ")" : "");
};
Tree.prototype.partial = function (start, end, offset, children, positions) {

@@ -225,3 +229,3 @@ for (var i = 0; i < this.children.length; i++) {

}
return new Tree(children, positions, this.length + off);
return new Tree(children, positions, this.length + off, this.tags);
};

@@ -241,4 +245,5 @@ /// Take the part of the tree up to the given position.

}
return new Tree(children, positions, at, this.type);
return new Tree(children, positions, at, this.tags, this.type);
};
/// @internal
Tree.prototype.iterate = function (from, to, enter, leave) {

@@ -251,3 +256,3 @@ var iter = new Iteration(enter, leave);

Tree.prototype.iterInner = function (from, to, offset, iter) {
if (isTagged(this.type) && !iter.doEnter(this.type, offset, offset + this.length))
if (isTagged(this.type) && !iter.doEnter(this.tag, offset, offset + this.length))
return;

@@ -275,3 +280,3 @@ if (from <= to) {

if (iter.leave && isTagged(this.type))
iter.leave(this.type, offset, offset + this.length);
iter.leave(this.tag, offset, offset + this.length);
return;

@@ -284,5 +289,7 @@ };

};
/// @internal
Tree.prototype.childBefore = function (pos) {
return this.findChild(pos, -1, 0, this);
};
/// @internal
Tree.prototype.childAfter = function (pos) {

@@ -333,3 +340,3 @@ return this.findChild(pos, 1, 0, this);

throw new Error("Can't append overlapping trees");
return new Tree(this.children.concat(other.children), this.positions.concat(other.positions), other.length, this.type);
return new Tree(this.children.concat(other.children), this.positions.concat(other.positions), other.length, this.tags, this.type);
};

@@ -341,13 +348,13 @@ /// Balance the direct children of this tree. Should only be used on

return this.children.length <= BalanceBranchFactor ? this :
balanceRange(this.type, this.children, this.positions, 0, this.children.length, 0, maxBufferLength);
balanceRange(this.type, this.tags, this.children, this.positions, 0, this.children.length, 0, maxBufferLength);
};
/// Build a tree from a postfix-ordered buffer of node information,
/// or a cursor over such a buffer.
Tree.build = function (buffer, grammarID, maxBufferLength, reused) {
Tree.build = function (buffer, tags, maxBufferLength, reused) {
if (maxBufferLength === void 0) { maxBufferLength = exports.DefaultBufferLength; }
if (reused === void 0) { reused = []; }
return buildTree(Array.isArray(buffer) ? new FlatBufferCursor(buffer, buffer.length) : buffer, grammarID, maxBufferLength, reused);
return buildTree(Array.isArray(buffer) ? new FlatBufferCursor(buffer, buffer.length) : buffer, tags, maxBufferLength, reused);
};
/// The empty tree
Tree.empty = new Tree([], [], 0);
Tree.empty = new Tree([], [], 0, []);
return Tree;

@@ -364,18 +371,18 @@ }(Subtree));

// FIXME store a type in here to efficiently represent nodes whose children all fit in a buffer (esp repeat nodes)?
function TreeBuffer(buffer, length, grammarID) {
function TreeBuffer(buffer, length, tags) {
this.buffer = buffer;
this.length = length;
this.grammarID = grammarID;
this.tags = tags;
}
/// @internal
TreeBuffer.prototype.toString = function (tags) {
TreeBuffer.prototype.toString = function () {
var parts = [];
for (var index = 0; index < this.buffer.length;)
index = this.childToString(index, parts, tags);
index = this.childToString(index, parts);
return parts.join(",");
};
/// @internal
TreeBuffer.prototype.childToString = function (index, parts, tags) {
TreeBuffer.prototype.childToString = function (index, parts) {
var type = this.buffer[index], endIndex = this.buffer[index + 3];
var result = String(tags ? tags.get(type | this.grammarID) : type);
var result = this.tags[type >> 1].tag;
index += 4;

@@ -385,3 +392,3 @@ if (endIndex > index) {

while (index < endIndex)
index = this.childToString(index, children, tags);
index = this.childToString(index, children);
result += "(" + children.join(",") + ")";

@@ -404,3 +411,3 @@ }

}
return new TreeBuffer(newBuffer, Math.min(at, this.length), this.grammarID);
return new TreeBuffer(newBuffer, Math.min(at, this.length), this.tags);
};

@@ -419,10 +426,10 @@ /// @internal

TreeBuffer.prototype.iterChild = function (from, to, offset, index, iter) {
var type = this.buffer[index++] | this.grammarID, start = this.buffer[index++] + offset, end = this.buffer[index++] + offset, endIndex = this.buffer[index++];
var tag = this.tags[this.buffer[index++] >> 1], 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)) {
if (end >= from && iter.doEnter(tag, start, end)) {
while (index < endIndex && !iter.done)
index = this.iterChild(from, to, offset, index, iter);
if (iter.leave)
iter.leave(type, start, end);
iter.leave(tag, start, end);
}

@@ -469,6 +476,6 @@ return endIndex;

var base = nextStart;
var type_1 = this.buffer[base] | this.grammarID, start_1 = this.buffer[base + 1] + offset, end_1 = this.buffer[base + 2] + offset;
var type_1 = this.buffer[base], start_1 = this.buffer[base + 1] + offset, end_1 = this.buffer[base + 2] + offset;
takeNext();
if (start_1 <= from && end_1 >= to) {
if (!iter.doEnter(type_1, start_1, end_1)) {
if (!iter.doEnter(this.tags[type_1 >> 1], start_1, end_1)) {
// Skip the entire node

@@ -482,7 +489,7 @@ index = base;

}
var endIndex_1 = this.buffer[--index], end = this.buffer[--index] + offset, start = this.buffer[--index] + offset, type = this.buffer[--index] | this.grammarID;
var endIndex_1 = this.buffer[--index], end = this.buffer[--index] + offset, start = this.buffer[--index] + offset, type = this.buffer[--index];
if (start > from || end < to)
continue;
if ((endIndex_1 != index + 4 || iter.doEnter(type, start, end)) && iter.leave)
iter.leave(type, start, end);
if ((endIndex_1 != index + 4 || iter.doEnter(this.tags[type >> 1], start, end)) && iter.leave)
iter.leave(this.tags[type >> 1], start, end);
}

@@ -521,4 +528,4 @@ };

}
Object.defineProperty(NodeSubtree.prototype, "type", {
get: function () { return this.node.type; },
Object.defineProperty(NodeSubtree.prototype, "tag", {
get: function () { return this.node.tag; },
enumerable: true,

@@ -543,3 +550,3 @@ configurable: true

};
NodeSubtree.prototype.toString = function (tags) { return this.node.toString(tags); };
NodeSubtree.prototype.toString = function () { return this.node.toString(); };
NodeSubtree.prototype.iterate = function (from, to, enter, leave) {

@@ -562,4 +569,4 @@ var iter = new Iteration(enter, leave);

}
Object.defineProperty(BufferSubtree.prototype, "type", {
get: function () { return this.buffer.buffer[this.index] | this.buffer.grammarID; },
Object.defineProperty(BufferSubtree.prototype, "tag", {
get: function () { return this.buffer.tags[this.buffer.buffer[this.index] >> 1]; },
enumerable: true,

@@ -605,5 +612,5 @@ configurable: true

};
BufferSubtree.prototype.toString = function (tags) {
BufferSubtree.prototype.toString = function () {
var result = [];
this.buffer.childToString(this.index, result, tags);
this.buffer.childToString(this.index, result);
return result.join("");

@@ -648,3 +655,3 @@ };

var BalanceBranchFactor = 8;
function buildTree(cursor, grammarID, maxBufferLength, reused) {
function buildTree(cursor, tags, maxBufferLength, reused) {
function takeNode(parentStart, minPos, children, positions) {

@@ -664,6 +671,6 @@ var type = cursor.type, start = cursor.start, end = cursor.end, size = cursor.size, buffer;

index = copyToBuffer(buffer.start, data, index);
node = new TreeBuffer(data, end - buffer.start, grammarID);
node = new TreeBuffer(data, end - buffer.start, tags);
// Wrap if this is a repeat node
if (!isTagged(type))
node = new Tree([node], [0], end - buffer.start, type | grammarID);
node = new Tree([node], [0], end - buffer.start, tags, type);
startPos = buffer.start - parentStart;

@@ -679,3 +686,3 @@ }

localPositions.reverse();
node = new Tree(localChildren, localPositions, end - start, type | grammarID);
node = new Tree(localChildren, localPositions, end - start, tags, type);
}

@@ -686,3 +693,3 @@ children.push(node);

if (!isTagged(type) && (cursor.pos == 0 || cursor.type != type))
maybeBalanceSiblings(children, positions, type | grammarID);
maybeBalanceSiblings(children, positions, type);
}

@@ -699,3 +706,3 @@ function maybeBalanceSiblings(children, positions, type) {

var start = positions[to - 1];
var wrapped = balanceRange(type, children.slice(from, to).reverse(), positions.slice(from, to).reverse(), 0, to - from, start, maxBufferLength);
var wrapped = balanceRange(type, tags, children.slice(from, to).reverse(), positions.slice(from, to).reverse(), 0, to - from, start, maxBufferLength);
children.length = positions.length = from + 1;

@@ -753,5 +760,6 @@ children[from] = wrapped;

takeNode(0, 0, children, positions);
return new Tree(children.reverse(), positions.reverse(), children.length ? positions[0] + children[0].length : 0);
var length = children.length ? positions[0] + children[0].length : 0;
return new Tree(children.reverse(), positions.reverse(), length, tags);
}
function balanceRange(type, children, positions, from, to, start, maxBufferLength) {
function balanceRange(type, tags, children, positions, from, to, start, maxBufferLength) {
var length = (positions[to - 1] + children[to - 1].length) - start;

@@ -794,3 +802,3 @@ if (from == to - 1 && start == 0) {

// Wrap with our type to make reuse possible
only = new Tree([only], [0], only.length, type);
only = new Tree([only], [0], only.length, tags, type);
}

@@ -800,3 +808,3 @@ localChildren.push(only);

else {
localChildren.push(balanceRange(type, children, positions, groupFrom, i, groupStart, maxBufferLength));
localChildren.push(balanceRange(type, tags, children, positions, groupFrom, i, groupStart, maxBufferLength));
}

@@ -806,42 +814,103 @@ localPositions.push(groupStart - start);

}
return new Tree(localChildren, localPositions, length, type);
return new Tree(localChildren, localPositions, length, tags, type);
}
/// A tag map is a data structure that holds metadata per tagged node
/// type, possibly across grammars. Each parser comes with a tag map
/// that holds the names for its tagged nodes, but you can also define
/// such maps yourself.
var TagMap = /** @class */ (function () {
/// @internal
function TagMap(grammars) {
this.grammars = grammars;
function badTag(tag) {
throw new SyntaxError("Invalid tag " + JSON.stringify(tag));
}
/// Tags represent information about nodes. They are an ordered
/// collection of parts (more specific ones first) written in the form
/// `boolean.literal.expression` (where `boolean` further specifies
/// `literal`, which in turn further specifies `expression`).
///
/// A part may also have a value, written after an `=` sign, as in
/// `tag.selector.lang=css`. Part names and values may be double
/// quoted (using JSON string notation) when they contain non-word
/// characters.
///
/// This wrapper object pre-parses the tag for easy querying.
var Tag = /** @class */ (function () {
/// Create a tag object from a string.
function Tag(
/// The string that the tag is based on.
tag) {
this.tag = tag;
var parts = [];
if (tag.length)
for (var pos = 0;;) {
var start = pos;
while (pos < tag.length) {
var next = tag.charCodeAt(pos);
if (next == 61 || next == 46)
break; // "=" or "."
pos++;
}
if (pos == start)
badTag(tag);
var name = tag.slice(start, pos), value = "";
if (tag.charCodeAt(pos) == 61) {
var valStart = ++pos;
if (tag.charCodeAt(pos) == 34 /* '"' */) {
for (pos++;;) {
if (pos >= tag.length)
badTag(tag);
var next = tag.charCodeAt(pos++);
if (next == 92)
pos++;
else if (next == 34)
break;
}
value = JSON.parse(tag.slice(valStart, pos));
}
else {
while (pos < tag.length && tag.charCodeAt(pos) != 46)
pos++;
value = tag.slice(valStart, pos);
}
}
parts.push(name, value);
if (pos == tag.length)
break;
if (tag.charCodeAt(pos) != 46)
badTag(tag);
pos++;
}
this.parts = parts;
}
/// Get the value associated with the given type, if any.
TagMap.prototype.get = function (type) {
if (!isTagged(type))
return null;
var table = this.grammars[grammarID(type) >> 16];
return table && table[termID(type) >> 1];
Tag.prototype.find = function (name, value) {
for (var i = 0; i < this.parts.length; i += 2) {
if (this.parts[i] == name && (value == null || this.parts[i + 1] == value))
return i;
}
return -1;
};
/// Create a tag map for a single grammar from a flat array that
/// holds, for each term ID, the associated value.
TagMap.single = function (grammarID, values) {
var _a;
return new TagMap((_a = {}, _a[grammarID >> 16] = values, _a));
/// Check whether this tag has a part by the given name. If `value`
/// is given, this will only return true when that part also has
/// that specific value.
Tag.prototype.has = function (name, value) {
return this.find(name, value) > -1;
};
/// Combine tag maps for multiple grammars into a single one that
/// covers all of those grammars.
TagMap.combine = function (maps) {
var grammars = {};
for (var _i = 0, maps_1 = maps; _i < maps_1.length; _i++) {
var map = maps_1[_i];
for (var id in map.grammars)
grammars[id] = map.grammars[id];
/// See whether this tag contains all the parts present in the
/// argument tag, and, if the part has a value in the query tag, the
/// same value in this tag. Returns a specificity score—0 means
/// there was no match, a higher score means the query matched more
/// specific parts of the tag.
Tag.prototype.matches = function (tag) {
var score = 0;
if (tag.parts.length == 0)
return 1;
for (var i = 0; i < tag.parts.length; i += 2) {
var val = tag.parts[i + 1];
var found = this.find(tag.parts[i], val || undefined);
if (found < 0)
return 0;
score += Math.pow(2, ((tag.parts.length - i) >> 1)) + (val ? 1 : 0);
}
return new TagMap(grammars);
return score;
};
/// The empty tag map.
TagMap.empty = new TagMap([]);
return TagMap;
/// The empty tag, returned for nodes that don't have a meaningful
/// tag.
Tag.empty = new Tag("");
return Tag;
}());
exports.TagMap = TagMap;
exports.Tag = Tag;
//# sourceMappingURL=tree.js.map

2

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

@@ -5,0 +5,0 @@ "main": "dist/tree.js",

12

src/README.md

@@ -13,14 +13,6 @@ ### Trees

### Node types
### Node tags
@TagMap
@Tag
@isTagged
@grammarID
@termID
@allocateGrammarID
### Buffers

@@ -27,0 +19,0 @@

252

src/tree.ts
/// The default maximum length of a `TreeBuffer` node.
export const DefaultBufferLength = 1024
/// Checks whether the given node type is a tagged node.
export function isTagged(type: number) { return (type & 1) > 0 }
// Checks whether the given node type is a tagged node.
function isTagged(type: number) { return (type & 1) > 0 }
const GRAMMAR_ID_MASK = (2**14 - 1) << 16, TERM_ID_MASK = 2**16 - 1
/// Get the ID of the grammar that a node type is part of.
export function grammarID(type: number) { return type & GRAMMAR_ID_MASK }
/// Get the term ID for the given node type.
export function termID(type: number) { return type & TERM_ID_MASK }
let nextGrammarID = 0
/// Allocate a new unique grammar ID.
export function allocateGrammarID() { return (nextGrammarID++) << 16 }
/// The `unchanged` method expects changed ranges in this format.

@@ -30,3 +20,3 @@ export interface ChangedRange {

/// Signature of the `enter` function passed to `Subtree.iterate`. It is given
/// a node's type, start position, and end position for every node,
/// a node's tag, start position, and end position for every node,
/// and can return...

@@ -41,6 +31,6 @@ ///

/// value from the `iterate` method.
export type EnterFunc<T> = (type: number, start: number, end: number) => T | false | undefined
export type EnterFunc<T> = (tag: Tag, start: number, end: number) => T | false | undefined
/// Signature of the `leave` function passed to `Subtree.iterate`.
export type LeaveFunc = (type: number, start: number, end: number) => void
export type LeaveFunc = (tag: Tag, start: number, end: number) => void

@@ -55,4 +45,4 @@ class Iteration<T> {

doEnter(type: number, start: number, end: number) {
let value = this.enter(type, start, end)
doEnter(tag: Tag, start: number, end: number) {
let value = this.enter(tag, start, end)
if (value === undefined) return true

@@ -70,4 +60,4 @@ if (value !== false) this.result = value

/// The node's type, or 0 if this is the root
abstract type: number
/// The node's tag. Will be `Tag.empty` for the root
abstract tag: Tag
/// The start source offset of this subtree

@@ -93,3 +83,3 @@ abstract start: number

/// @internal
abstract toString(tags?: TagMap<any>): string
abstract toString(): string

@@ -148,5 +138,6 @@ /// Iterate over all nodes in this subtree. Will iterate through the

export class Tree extends Subtree {
/// @internal
parent!: null
/// Construct a tree.
/// @internal
constructor(

@@ -162,4 +153,6 @@ /// The tree's child nodes. Children small enough to fit in a

readonly length: number,
/// This tree's node type. The root node has type 0.
readonly type = 0
/// Mapping from node types to tags for this grammar @internal
readonly tags: readonly Tag[],
/// This tree's node type. The root node has type 0. @internal
readonly type: number = 0
) {

@@ -169,12 +162,23 @@ super()

/// @internal
get start() { return 0 }
toString(tags?: TagMap<any>): string {
let name = !isTagged(this.type) ? null : tags ? tags.get(this.type) : this.type
let children = this.children.map(c => c.toString(tags)).join()
/// @internal
get end() { return this.length }
/// @internal
get tag() { return isTagged(this.type) ? this.tags[this.type >> 1] : Tag.empty }
/// Check whether this tree's tag belongs to a given set of tags.
/// Can be used to determine that a node belongs to the grammar
/// defined by a specific parser.
isPartOf(tags: readonly Tag[]) { return this.tags == tags }
/// @internal
toString(): string {
let name = !isTagged(this.type) ? null : this.tag.tag
let children = this.children.map(c => c.toString()).join()
return !name ? children : name + (children.length ? "(" + children + ")" : "")
}
get end() { return this.length }
private partial(start: number, end: number, offset: number, children: (Tree | TreeBuffer)[], positions: number[]) {

@@ -225,3 +229,3 @@ for (let i = 0; i < this.children.length; i++) {

}
return new Tree(children, positions, this.length + off)
return new Tree(children, positions, this.length + off, this.tags)
}

@@ -240,8 +244,9 @@

}
return new Tree(children, positions, at, this.type)
return new Tree(children, positions, at, this.tags, this.type)
}
/// The empty tree
static empty = new Tree([], [], 0)
static empty = new Tree([], [], 0, [])
/// @internal
iterate<T = any>(from: number, to: number, enter: EnterFunc<T>, leave?: LeaveFunc) {

@@ -255,5 +260,5 @@ let iter = new Iteration(enter, leave)

iterInner<T>(from: number, to: number, offset: number, iter: Iteration<T>) {
if (isTagged(this.type) && !iter.doEnter(this.type, offset, offset + this.length))
if (isTagged(this.type) && !iter.doEnter(this.tag, offset, offset + this.length))
return
if (from <= to) {

@@ -274,3 +279,3 @@ for (let i = 0; i < this.children.length && !iter.done; i++) {

}
if (iter.leave && isTagged(this.type)) iter.leave(this.type, offset, offset + this.length)
if (iter.leave && isTagged(this.type)) iter.leave(this.tag, offset, offset + this.length)
return

@@ -284,2 +289,3 @@ }

/// @internal
childBefore(pos: number): Subtree | null {

@@ -289,2 +295,3 @@ return this.findChild(pos, -1, 0, this)

/// @internal
childAfter(pos: number): Subtree | null {

@@ -330,3 +337,3 @@ return this.findChild(pos, 1, 0, this)

if (other.children.length && other.positions[0] < this.length) throw new Error("Can't append overlapping trees")
return new Tree(this.children.concat(other.children), this.positions.concat(other.positions), other.length, this.type)
return new Tree(this.children.concat(other.children), this.positions.concat(other.positions), other.length, this.tags, this.type)
}

@@ -338,3 +345,3 @@

return this.children.length <= BalanceBranchFactor ? this :
balanceRange(this.type, this.children, this.positions, 0, this.children.length, 0, maxBufferLength)
balanceRange(this.type, this.tags, this.children, this.positions, 0, this.children.length, 0, maxBufferLength)
}

@@ -345,7 +352,7 @@

static build(buffer: BufferCursor | readonly number[],
grammarID: number,
tags: readonly Tag[],
maxBufferLength: number = DefaultBufferLength,
reused: Tree[] = []) {
return buildTree(Array.isArray(buffer) ? new FlatBufferCursor(buffer, buffer.length) : buffer as BufferCursor,
grammarID, maxBufferLength, reused)
tags, maxBufferLength, reused)
}

@@ -363,9 +370,9 @@ }

// FIXME store a type in here to efficiently represent nodes whose children all fit in a buffer (esp repeat nodes)?
constructor(readonly buffer: Uint16Array, readonly length: number, readonly grammarID: number) {}
constructor(readonly buffer: Uint16Array, readonly length: number, readonly tags: readonly Tag[]) {}
/// @internal
toString(tags?: TagMap<any>) {
toString() {
let parts: string[] = []
for (let index = 0; index < this.buffer.length;)
index = this.childToString(index, parts, tags)
index = this.childToString(index, parts)
return parts.join(",")

@@ -375,9 +382,9 @@ }

/// @internal
childToString(index: number, parts: string[], tags?: TagMap<any>): number {
childToString(index: number, parts: string[]): number {
let type = this.buffer[index], endIndex = this.buffer[index + 3]
let result = String(tags ? tags.get(type | this.grammarID)! : type)
let result = this.tags[type >> 1].tag
index += 4
if (endIndex > index) {
let children: string[] = []
while (index < endIndex) index = this.childToString(index, children, tags)
while (index < endIndex) index = this.childToString(index, children)
result += "(" + children.join(",") + ")"

@@ -400,3 +407,3 @@ }

}
return new TreeBuffer(newBuffer, Math.min(at, this.length), this.grammarID)
return new TreeBuffer(newBuffer, Math.min(at, this.length), this.tags)
}

@@ -416,8 +423,8 @@

iterChild<T>(from: number, to: number, offset: number, index: number, iter: Iteration<T>) {
let type = this.buffer[index++] | this.grammarID, start = this.buffer[index++] + offset,
let tag = this.tags[this.buffer[index++] >> 1], 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)) {
if (end >= from && iter.doEnter(tag, start, end)) {
while (index < endIndex && !iter.done) index = this.iterChild(from, to, offset, index, iter)
if (iter.leave) iter.leave(type, start, end)
if (iter.leave) iter.leave(tag, start, end)
}

@@ -461,6 +468,6 @@ return endIndex

let base = nextStart
let type = this.buffer[base] | this.grammarID, start = this.buffer[base + 1] + offset, end = this.buffer[base + 2] + offset
let type = this.buffer[base], start = this.buffer[base + 1] + offset, end = this.buffer[base + 2] + offset
takeNext()
if (start <= from && end >= to) {
if (!iter.doEnter(type, start, end)) {
if (!iter.doEnter(this.tags[type >> 1], start, end)) {
// Skip the entire node

@@ -474,6 +481,6 @@ index = base

let endIndex = this.buffer[--index], end = this.buffer[--index] + offset,
start = this.buffer[--index] + offset, type = this.buffer[--index] | this.grammarID
start = this.buffer[--index] + offset, type = this.buffer[--index]
if (start > from || end < to) continue
if ((endIndex != index + 4 || iter.doEnter(type, start, end)) && iter.leave)
iter.leave(type, start, end)
if ((endIndex != index + 4 || iter.doEnter(this.tags[type >> 1], start, end)) && iter.leave)
iter.leave(this.tags[type >> 1], start, end)
}

@@ -507,3 +514,3 @@ }

get type() { return this.node.type }
get tag() { return this.node.tag }

@@ -526,3 +533,3 @@ get end() { return this.start + this.node.length }

toString(tags?: TagMap<any>) { return this.node.toString(tags) }
toString() { return this.node.toString() }

@@ -544,3 +551,3 @@ iterate<T = any>(from: number, to: number, enter: EnterFunc<T>, leave?: LeaveFunc) {

get type() { return this.buffer.buffer[this.index] | this.buffer.grammarID }
get tag() { return this.buffer.tags[this.buffer.buffer[this.index] >> 1] }
get start() { return this.buffer.buffer[this.index + 1] + this.bufferStart }

@@ -576,5 +583,5 @@ get end() { return this.buffer.buffer[this.index + 2] + this.bufferStart }

toString(tags?: TagMap<any>) {
toString() {
let result: string[] = []
this.buffer.childToString(this.index, result, tags)
this.buffer.childToString(this.index, result)
return result.join("")

@@ -613,3 +620,3 @@ }

function buildTree(cursor: BufferCursor, grammarID: number, maxBufferLength: number, reused: Tree[]): Tree {
function buildTree(cursor: BufferCursor, tags: readonly Tag[], maxBufferLength: number, reused: Tree[]): Tree {
function takeNode(parentStart: number, minPos: number, children: (Tree | TreeBuffer)[], positions: number[]) {

@@ -628,5 +635,5 @@ let {type, start, end, size} = cursor, buffer!: {size: number, start: number, skip: number} | null

index = copyToBuffer(buffer.start, data, index)
node = new TreeBuffer(data, end - buffer.start, grammarID)
node = new TreeBuffer(data, end - buffer.start, tags)
// Wrap if this is a repeat node
if (!isTagged(type)) node = new Tree([node], [0], end - buffer.start, type | grammarID)
if (!isTagged(type)) node = new Tree([node], [0], end - buffer.start, tags, type)
startPos = buffer.start - parentStart

@@ -640,3 +647,3 @@ } else { // Make it a node

localChildren.reverse(); localPositions.reverse()
node = new Tree(localChildren, localPositions, end - start, type | grammarID)
node = new Tree(localChildren, localPositions, end - start, tags, type)
}

@@ -648,3 +655,3 @@

if (!isTagged(type) && (cursor.pos == 0 || cursor.type != type))
maybeBalanceSiblings(children, positions, type | grammarID)
maybeBalanceSiblings(children, positions, type)
}

@@ -660,3 +667,3 @@

let start = positions[to - 1]
let wrapped = balanceRange(type, children.slice(from, to).reverse(), positions.slice(from, to).reverse(),
let wrapped = balanceRange(type, tags, children.slice(from, to).reverse(), positions.slice(from, to).reverse(),
0, to - from, start, maxBufferLength)

@@ -714,6 +721,8 @@ children.length = positions.length = from + 1

while (cursor.pos > 0) takeNode(0, 0, children, positions)
return new Tree(children.reverse(), positions.reverse(), children.length ? positions[0] + children[0].length : 0)
let length = children.length ? positions[0] + children[0].length : 0
return new Tree(children.reverse(), positions.reverse(), length, tags)
}
function balanceRange(type: number,
tags: readonly Tag[],
children: readonly (Tree | TreeBuffer)[], positions: readonly number[],

@@ -755,7 +764,7 @@ from: number, to: number,

// Wrap with our type to make reuse possible
only = new Tree([only], [0], only.length, type)
only = new Tree([only], [0], only.length, tags, type)
}
localChildren.push(only)
} else {
localChildren.push(balanceRange(type, children, positions, groupFrom, i, groupStart, maxBufferLength))
localChildren.push(balanceRange(type, tags, children, positions, groupFrom, i, groupStart, maxBufferLength))
}

@@ -765,38 +774,95 @@ localPositions.push(groupStart - start)

}
return new Tree(localChildren, localPositions, length, type)
return new Tree(localChildren, localPositions, length, tags, type)
}
/// A tag map is a data structure that holds metadata per tagged node
/// type, possibly across grammars. Each parser comes with a tag map
/// that holds the names for its tagged nodes, but you can also define
/// such maps yourself.
export class TagMap<T> {
/// @internal
constructor(readonly grammars: {readonly [id: number]: readonly (T | null)[]}) {}
function badTag(tag: string): never {
throw new SyntaxError("Invalid tag " + JSON.stringify(tag))
}
/// Get the value associated with the given type, if any.
get(type: number): T | null {
if (!isTagged(type)) return null
let table = this.grammars[grammarID(type) >> 16]
return table && table[termID(type) >> 1]
/// Tags represent information about nodes. They are an ordered
/// collection of parts (more specific ones first) written in the form
/// `boolean.literal.expression` (where `boolean` further specifies
/// `literal`, which in turn further specifies `expression`).
///
/// A part may also have a value, written after an `=` sign, as in
/// `tag.selector.lang=css`. Part names and values may be double
/// quoted (using JSON string notation) when they contain non-word
/// characters.
///
/// This wrapper object pre-parses the tag for easy querying.
export class Tag {
private parts: readonly string[]
/// Create a tag object from a string.
constructor(
/// The string that the tag is based on.
readonly tag: string
) {
let parts = []
if (tag.length) for (let pos = 0;;) {
let start = pos
while (pos < tag.length) {
let next = tag.charCodeAt(pos)
if (next == 61 || next == 46) break // "=" or "."
pos++
}
if (pos == start) badTag(tag)
let name = tag.slice(start, pos), value = ""
if (tag.charCodeAt(pos) == 61) {
let valStart = ++pos
if (tag.charCodeAt(pos) == 34 /* '"' */) {
for (pos++;;) {
if (pos >= tag.length) badTag(tag)
let next = tag.charCodeAt(pos++)
if (next == 92) pos++
else if (next == 34) break
}
value = JSON.parse(tag.slice(valStart, pos))
} else {
while (pos < tag.length && tag.charCodeAt(pos) != 46) pos++
value = tag.slice(valStart, pos)
}
}
parts.push(name, value)
if (pos == tag.length) break
if (tag.charCodeAt(pos) != 46) badTag(tag)
pos++
}
this.parts = parts
}
/// Create a tag map for a single grammar from a flat array that
/// holds, for each term ID, the associated value.
static single<T>(grammarID: number, values: readonly (T | null)[]) {
return new TagMap({[grammarID >> 16]: values})
private find(name: string, value?: string) {
for (let i = 0; i < this.parts.length; i += 2) {
if (this.parts[i] == name && (value == null || this.parts[i + 1] == value)) return i
}
return -1
}
/// Combine tag maps for multiple grammars into a single one that
/// covers all of those grammars.
static combine<T>(maps: TagMap<T>[]) {
let grammars: {[id: number]: readonly (T | null)[]} = {}
for (let map of maps) {
for (let id in map.grammars) grammars[id] = map.grammars[id]
/// Check whether this tag has a part by the given name. If `value`
/// is given, this will only return true when that part also has
/// that specific value.
has(name: string, value?: string) {
return this.find(name, value) > -1
}
/// See whether this tag contains all the parts present in the
/// argument tag, and, if the part has a value in the query tag, the
/// same value in this tag. Returns a specificity score—0 means
/// there was no match, a higher score means the query matched more
/// specific parts of the tag.
matches(tag: Tag) {
let score = 0
if (tag.parts.length == 0) return 1
for (let i = 0; i < tag.parts.length; i += 2) {
let val = tag.parts[i + 1]
let found = this.find(tag.parts[i], val || undefined)
if (found < 0) return 0
score += 2 ** ((tag.parts.length - i) >> 1) + (val ? 1 : 0)
}
return new TagMap(grammars)
return score
}
/// The empty tag map.
static empty = new TagMap<any>([])
/// The empty tag, returned for nodes that don't have a meaningful
/// tag.
static empty = new Tag("")
}
.tern-port

Sorry, the diff of this file is not supported yet

dist/tree.js.map

Sorry, the diff of this file is not supported yet

SocketSocket SOC 2 Logo

Product

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

About

Packages

Stay in touch

Get open source security insights delivered straight into your inbox.

  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc