Navigate the AST by references, definitions and scopes. We can call it: name-bound AST shortcuts or name-driven traversal.

Specifically:

• navigate from a use site of a definition (already there but only to the name, not to the nearest term that defines - the NaBL match pattern)
• navigate from a definition to its nearest surrounding scope
• navigate from a scope to its nearest surrounding scope
• retrieve all definitions in a scope (directly and indirectly contained)
• retrieve all uses of a definition
• retrieve all scopes nested within a scope
• …

The intention is to navigate from term to term in the program AST by means of names in the program

I think this is useful for compilation/transformation that is not localised in the AST. The use case in GM is only for gathering and emitting the graph structures, slightly too weak to justify a full on approach to this.

This issue was spawned by https://yellowgrass.org/issue/NaBL/57 and its description is currently incomplete.

Submitted by Vlad Vergu on 24 July 2013 at 01:01

Can you specify what you exactly mean by these navigations? For example, we have something to get all uses for a definition, but it will simply be a list of uses with the same URI. The origin of these uses are the corresponding instances of the name. You can get the scope of a definition by manipulating its URI, but you will not get the term of that scope, just the URI. I don’t think that we can store the complete term here, because this is expensive for big trees with multiple scope levels. Maybe we can achieve this by origin tracking, that is, just storing the origin of the term, but not the term. For definitions, the origin is currently the origin of the name, not of the pattern. We can possibly change this. I still miss a general sketch why and where this is needed. We might not need this discussion here, but there should be a discussion before we support anything in this direction.

I agree a discussion is needed, hence rfc tag.

The intention is to navigate from term to term in the program AST by means of names in the program. Origin information might just be good enough if term-at-position is somewhat fast. I’ve updated the issue description.

Term to term navigation is rephrasing the graph metapher. This might have conceptual limitations, particular if the result of a transformation is not a correct graph but a tree with some annotations but also missing annotations.

I again see confusion with the term ‘origin information’, let’s clear this up.

The parser produces an AST where each node has location information that describes the location of that node in the textual source file. It is implemented as an ImploderAttachment on the node.

If a node is transformed, origin information is added to the transformed node that describes its origin node. This is a direct reference/pointer to the original node object. It is implemented as an DesugaredOriginAttachment or OriginAttachment. Note that transformed nodes do not have location information, but the location information can be retrieved by going to the origin term and getting that terms’ location information.

Definitions in the index have origin information to the name in the AST.

I don’t think term-at-position even uses location information, and it will be slow anyway.

@Gabriël: Can you sketch what kind of term-to-term navigation can in general be achieved with origins? What is not feasible?

@Guido: I don’t think I understand your question. Origin information is term-to-term. The origin can be changed to point to the NaBL pattern instead of the name.

How easy is it to navigate from a term with origin information to the original term?

Easy: <origin-term> term

Ok, then we can support the following things:

navigate from a use site of a definition (already there but only to the name, not to the nearest term that defines - the NaBL match pattern)

Can be achieved by changing the origin of the Def entry. This requires a change in the generator and in the library, but I am in favour of this change. The name can still be accessed by getting the name from the pattern by nabl-get-name.

navigate from a definition to its nearest surrounding scope
navigate from a scope to its nearest surrounding scope

This is both a combination of getting the URI, cutting it down to the scope URI and accessing the scope. Though, we cannot store the term. We need to store something smaller with the origin of the scope term.

retrieve all definitions in a scope (directly and indirectly contained)

Direct definitions needs to be supported for code completion anyway. Indirect things should be possible by combining nested scope search and direct lookup.

retrieve all uses of a definition

Already supported. I assume you also want the pattern here, not just the name. Requires the same changes as for Def.

retrieve all scopes nested within a scope

Requires YATHM.

Though, you need to be careful. I assume you will get terms before name analysis. Thus, you might not be able to stage this multiple times. It is really not about navigating a graph. It is about getting terms before analysis.

retrieve all definitions in a scope (directly and indirectly contained)

Direct definitions needs to be supported for code completion anyway. Indirect things should be possible by combining nested scope search and direct lookup.

This is in theory already supported (although untested), for example to get all variables in given scope and nested scopes during compilation:

get-variables(|partition):
	uri -> def*
	with
		task-push;
		task*           := <nabl-resolve-all-defs-subtasks(|partition, NablnsVariable(), [], All())> uri;
		Result(task-id) := <new-task(|partition)> Concat(task*);
		<task-evaluate-now> task-id;
		def* := <task-get-result> task-id;
		task-pop

retrieve all uses of a definition

Already supported. I assume you also want the pattern here, not just the name. Requires the same changes as for Def.

How is this supported? There’s no way to find all uses of a def in the index currently.

Ok, that means we need a task to get all definitions in a scope. This might be calculated beforehand for each scope. Not sure about this. There might also be a need for different versions: All definitions in current scope, all definitions in outer nested scopes (surrounding), all definitions in inner nested scopes (surrounded). But there might be a simpler version, that combines results from current scope and from other scopes, which are also queried.

I thought we could query uses. But this is gone?

There is a task to get all definitions in a scope, the task is here: https://github.com/metaborg/runtime-libraries/blob/master/org.spoofax.meta.runtime.libraries/nbl/tasks.str#L98 and to look up everything in nested scopes as well we use https://github.com/metaborg/runtime-libraries/blob/master/org.spoofax.meta.runtime.libraries/nbl/tasks.str#L107. Or do you mean one that does not filter on a namespace?

You can query uses but uses look like Use(Result(1)). They do not have a URI in them because the URI that a Use points to is only known after the resolution task has been solved, and we cannot change the index since entries are immutable.

Ok, so the uses will be an issue. Because you would query this with a URI, but you will not find entries here.

I was giving this another thought today and figured out a serious issue, that is accessing pattern terms from Def entries might break incrementality. Take a Java field public static int i as an example. In our current setup, this field is represented in the index by a Def entry and three Prop entries for type, visibility, and static/non-static. When you change the field into private static int i, one of the properties is updated and only tasks depending on this property need to be re-evaluated.

I understand Vlad that he likes to query visibility and static/non-static from the origin term of the `Def`` entry. This means, that, whenever this original term changes, all tasks that query this term need to be re-evaluated, even if the properties in question do not change. Even worse, to determine such changes, we need to explicitly store origin terms.

I am using a def property in my pack-sdf implementation. This works, but should not be the solution. I think the following can work:

1. Store a default property definition for every Def entry in the index. This property includes the file name and a path to the definition in the AST of this file. This property has a small memory footprint.
2. Provide a strategy to get the value of a definition property and retrieve the actual definition term. This strategy either uses an existing AST from an open editor, or loads the AST from the file.
3. Add some AST caching.