Get node/path by position

[squeedee]

Hey there. I'm currently writing monaco editor support for my yaml based DSL. I want to write 'jump to definition' support, where a string in the document should refer to an earlier string:

things:
  - name: thing1
     ...
  - name: thing2
     ...
  - name: thing3
     parent: thing1

It's more complex than this contrived example, but what I need to do is take my current character position (say hovering somewhere in parent: thing1,

1. doc.getNodeAtPosition(myPos) >> Node[thing1], Path[.....]
2. node is pathed in a way I care about Path == Path["things",2,"parent"]

This way i can identify I am looking for the definition of a 'parent reference'..

I hope that's clear enough... The important part here is, id like getNodeAtPosition(pos: Position): Node | Pair | Document, []string (or []node)

Right now I'm using visit, looking for the pair with a key: "parent", testing if it's value's position overlaps the cursor position, and then walking the path, but it's a little brutish and inelegant. Just wondering if there was a better approach?

[eemeli]

In what way do you find visit() to be inelegant for this? It's not obvious to me how a different approach would be more efficient.

[squeedee]

Well like i said, the most elegant mechanism I can think of is a function (that might well wrap visit, or use an index) in the form:

nodeAtPosition:AnyNodeType, Path: []AnyNodeType = f(pos: Position, node: Node | Doc)

Now I can implement f, but something similar may exist. Not knowing what I don't know, I ask if something like this, or more elegant than implementing it with Visit, exists. I understand it may not, I don't know until I ask.

It's not obvious to me how a different approach would be more efficient.

It could already be implemented as a utility. I'm not saying you need to, just that you may have.
I can think of more efficient read-speed solutions, at the cost of write speed (like a balanced tree). I imagine it would not be a good design, but it doesn't mean you aren't clever than I am - hence I ask.

[squeedee]

I should properly answer this:

In what way do you find visit() to be inelegant for this

Typically when parsing a language file you end up with a LALR result, which you refer to as the CST, and typically build an AST. The AST tends to be for-purpose, like your AST seems to be aimed at "Modify a YAML file and maintain meta (comments, order, position)".. ASTs written for language support in editors tend (in my limited experience) to optimize for the fact there's an active insertion point (caret) for plain text entry and other tooling like "get definition" and "find usages". I was wondering, but not expecting, if there was this kind of optimization already in your AST.

visit() absolutely does work and I'm glad for it, because this way your library still saves me a lot of heavy lifting, unlike most YAML parser libraries which only give us In-Memory native representations (with yaml comments, and source locations, completely gone).

[eemeli]

Ah, okay, so with visit() the issue is that it iterates through the nodes in a sequential fashion rather than e.g. doing a binary search through the AST, yes? I see now how that's a bit inefficient, and could benefit from a custom solution. If you end up writing such a function, I'd be happy to consider a PR adding it? Probably as a separate function like visit().

As for "get definition" and "find usages", here I presume you're talking about your DSL, yes? YAML does include aliases, for which a resolve() method is provided. As the changes to anchors aren't reactively tracked, that does end up using visit() internally.

[squeedee]

Yeah, for my DSL. It's probably lazy of me, not creating my own for-purpose AST but I need so little extra.

To make a good custom solution would mean correctly implementing a b-tree that responds to mutations of the Document AST, and I'm not sure I'm up to that task. I will simply move on with visit and call it a day. I appreciate you discussing it with me.

[squeedee]

For others who might ask: no there isn't currently a fast index to find a node at a position (caret). Which should have been how I posed the question :D

In my mind, a b-tree with spanning indexes (just using first-position) indexing position to a node, would work here. It would need to support live edits to the Document AST for completeness (not just create-on-parse). Finally it would probably slow down parsing, and definitely slow down insert/edits, because creating or mutating a node would necessarily require the right side of the tree to be rebuilt, so it would definitely need to be guarded by an option eg: parseDocument(doc,{createPositionIndex: true}