Create reverse code flow graph

[Glyphack]

In the semantic analysis we bind the definitions to symbol table. Since a symbol can be redefined multiple times we need to track what is the definition of a symbol at any given time in the code. For this reverse code flow graph can be used.

Here's an explanation from source graph's cody on how to build it:

Here is an example of how Pyright creates a reverse code flow graph for a Python program:

# Example Python code

def func(a):
    if a > 0:
        b = a * 2
    else:
        b = 0
    
    print(b)

func(5)

Pyright would analyze this code and build a reverse code flow graph that looks something like this:

Node: CallExpression: print(b)

Node: NameExpression: b
|
v
Node: IfStatement: if a > 0:...else:...
|
v
Node: CallExpression: func(5)
The key steps are:

Start with endpoint expressions like print(b).

Trace backwards to where b was defined in the if statement.

Keep tracing back through assignments, function calls, etc to build the graph.

The graph is reversed compared to execution order - it flows from usage to definitions.

Loops and branches create multiple code flow paths.

So Pyright recursively walks the AST starting from end points, tracing variable definitions, assignments, function calls, etc to build the full graph. This allows it to understand all of the possible code paths that led to a variable's value.

The reverse flow graph is then used for type inference, data flow analysis, reachability, etc. Let me know if you need any clarification or have additional examples!

Here is one way to build a graph representing the symbol table while traversing the AST:

Create a Graph class that stores nodes and edges. Each node represents a symbol, and edges represent relationships between symbols (e.g. one symbol using another symbol).

As you traverse the AST, create nodes for each symbol you encounter by calling graph.addNode(symbol).

Add edges between nodes when you detect symbol relationships. For example:

function traverse(node) {

  if (node is FunctionDefinition) {
    let funcNode = graph.addNode(node.name)
    
    for (let param of node.params) {
      let paramNode = graph.addNode(param.name)
      graph.addEdge(funcNode, paramNode) 
    }
  }

  if (node is VariableDeclaration) {
    let varNode = graph.addNode(node.name)
  }

  // etc...
}

The graph.addEdge(a, b) call creates an edge between nodes a and b, representing that a uses/depends on b.

After traversing the entire AST, you will have a Graph populated with nodes for all symbols, and edges showing how they relate to each other.

You can then use a graph visualization library like D3.js to render the graph from the symbol table.