What is the best way to capture usage of another function within another function?

[maxwnewcomer]

For example, let's say how I had the code
foobar.py

def bar():
     pass
def barbar():
     pass
def foo():
     bar()
     barbar()

Using,

global FILE_NODE
    (function_definition
        name: (identifier) @id
    ) @func {
        node def
        attr (def) type = "pop_symbol", symbol = (source-text @id), source_node = @func, is_definition
        edge FILE_NODE -> def
    }

I am able to link the function_definition of "foo" to foobar.py (as nodes).
Creating a graph like this:

If I wanted to make this:

What would be the right way to capture this in the tsg language? Especially if the program is confusing and looks like this

def bar():
     pass
def barbar():
     pass
def bar(): # reference this function in foo() not previous
     pass
def foo():
     bar()
     barbar()

[hendrikvanantwerpen]

Good questions! The premise of how stack graphs work is that we process of name resolution, i.e. linking references to definitions, is essentially split up in two parts.

The first part constructs a stack graph that should result in references being able to reach definitions. They do not necessarily have to be connected to them in a single step. This first part is what we use TSG for. The rules convert the program into a graph, but do this using fairly local information. We may create edges between the nodes of parents and children in the syntax tree, but usually not further than that.

The second part does a search in the graph to find the definitions that match references. This part traverses the edges, and can possible find reachable definitions that originated in parts of the program far from where the references is located. This is the non-local part. However, you don't have to program this directly, you rely on the path finding algorithm of the stack graph, and the structure of the constructed graph.

Given these two things, let's consider your example. (I'll just consider a single file here.) The FILE_NODE is the node that covers the whole file, and the definitions should be reachable from there. This is the case in your example rule, which adds an edge from FILE_NODE to the definitions. (The arrow in your diagram is in the opposite direction of the edge direction in the rule. The rule is correct here.) The references should be able to reach the definitions, so there should be a path from the reference to the definition. This is the case when there is a path from the reference to the FILE_NODE. We often call the nodes for lookups of references scopes or lexical scopes.

The diagram would look something like this now:

flowchart LR
  file_node(FILE_NODE)

  bar_def[bar]

  barbar_def[barbar]

  foo_def[foo]
  foo_scope(foo.scope)
  bar_ref[bar]
  barbar_ref[barbar]

  file_node --> bar_def
  file_node --> barbar_def
  file_node --> foo_def

  foo_scope --> file_node
  bar_ref --> foo_scope
  barbar_ref --> foo_scope

Loading

Finally, to debug the TSG rules you're writing, it is helpful to write tests. See this example. The comments say how you expect the reference to resolve (to which line). Run the test with tree-sitter-stack-graphs test command. This command also has flags to render an HTML version of the stack graph that was produced for the test file, which is great for debugging.

[maxwnewcomer]

@hendrikvanantwerpen This makes a lot more sense now, and understanding the direction of edges and why they should be that direction helped a lot.

A couple of clarifying questions:

1. Is the pop/push symbol notation the way we determine the difference between the multiple bar() definitions in the second example I gave?

2. In the example diagram you gave, is "foo.scope" is a "push_scope_node" (??), would the "bar", "barbar" and "foo" nodes on the right be "pop_symbol_nodes" and "bar" and "barbar" be "push_symbol_nodes"?

3. What do you use to make those diagrams? They are a lot cleaner than my own.

I really appreciate all the help and work you put into this repository, for some reason this project is super interesting to me and I'm super excited to learn more about this.

[hendrikvanantwerpen]

1. Push or pop indicates whether something is a reference or a definition, respectively. Two definitions will give two pop nodes. If you want to differentiate, you can do so by building a chain of scopes (nodes without symbols) and set precedences on the outgoing edges, similar to this:

   flowchart BT
   file_node(FILE_NODE)
   stmt1_scope(stmt1.scope)
   stmt2_scope(stmt2.scope)
   bar1_def[bar]
   bar2_def[bar]
   bar_ref[bar]
   stmt1_scope -->|precedence=0| file_node
   stmt2_scope -->|precedence=0| stmt1_scope
   stmt1_scope -->|precedence=1| bar1_def
   stmt2_scope -->|precedence=1| bar2_def
   bar_ref --> stmt2_scope
   

   Loading

2. The foo-scope node is just a node, without any special attributes. Using in a path doesn't change the stack of symbols, unlike push and pop nodes. The left nodes are pushes and the right nodes pops. Matching pushes and pops (i.e., with the same symbol) make a valid path and thus a resolved named.

3. See https://docs.github.com/en/get-started/writing-on-github/working-with-advanced-formatting/creating-diagrams