lezer-tree - npm Package Compare versions

Comparing version 0.1.1 to 0.2.0

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

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 {};

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

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",

src/README.md

@@ -13,14 +13,6 @@ ### Trees
 
-### Node types
+### Node tags
 
-@TagMap
+@Tag
 
-@isTagged
-
-@grammarID
-
-@termID
-
-@allocateGrammarID
-
 ### Buffers
@@ -27,0 +19,0 @@

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("")
 }

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

105998

increased by6.31%

Lines of code

1730

increased by8.06%

No dependency changes