Annotated CAST Part 1: Overview

Annotated CAST Passes Overview

Note: 'pass' has a conventional use in language implementation and compilers to denote a pass across the data structure that infers additional properties based on existing properties, and adds those new properties in-place in the data structure or as part of new data structure.

The Python script cast_to_annotated.py reads a JSON file that contains the CAST representation of a program and transforms it to annotated CAST. It then calls a series of additional passes that each augment the information in the annotated CAST nodes in preparation for the GrFN generation. The final pass uses the information in the annotated CAST to generate the GrFN json and the visual representation.

There are currently six passes in this process, implemented in the following .py files:

• cast_to_annotated.py
• id_collapse_pass.py
• container_scope_pass.py
• variable_version_pass.py
• grfn_var_creation_pass.py
• to_grfn_pass.py

cast_to_annotated.py

This pass traverses the CAST nodes and generates an annotated cast version of the CAST. It does this by copying each CAST node to a corresponding AnnCastNode which has additional attributes (fields) that are used in later passes to maintain information for GrFN generation. The information gathered in the various passes includes, for example, the variables modified and used by each container, and the version, scope and GrFN identifier of each variable reference.

The specific attributes for each annotated cast node are shown in Part 3. As an example, however, the code below shows the annotated cast class definition for an AnnCastName node:

class AnnCastName(AnnCastNode):
    def __init__(self, name, id, source_refs):
        self.name = name
        self.id = id
        self.source_refs = source_refs
        # container_scope is used to aid GrFN generation
        self.con_scope = None
        # versions are bound to the scope of the variable
        self.version = None
        self.grfn_id = None

Ultimately, each reference to a variable represented by an AnnCastName node is disambiguated by its variable name, numerical id, version, and scope. We call this the fullid of the variable and track the fullids in the following two attributes of the primary AnnCastNode:

        self.grfn_id_to_grfn_var = {}
        # the fullid of a AnnCastName node is a string which includes its
        # variable name, numerical id, version, and scope
        self.fullid_to_grfn_id = {}

The annotated cast for a node representing a container must maintain extensive information for GrFN generation. Each of the container types have attributes for the following:

• the modified, accessed, and used variables
• the container scope
• the highest versions of all variables used in the container
• dictionaries for each of the interfaces required by the container that map variable ids to their fullids

There are containers for if statements, loops, function definitions, and function calls.

id_collapse_pass.py

The GCC compiler maps all variable names to unique numerical identifiers, which is required to correctly disambiguate global and local variables that use the same name (i.e., a local variable x versus a global variable x). However, the ids generated are overly long, which complicates manual inspection and debugging.

During this pass, we collapse the variable ids (stored in AnnCastName nodes as shown above) to numbers that start at zero and increase as needed.

container_scope_pass.py

As mentioned, we distinguish each instance of a variable reference with its fullid, which consists of the variable name and its numerical id, version, and scope. For GrFN, the normal meaning of lexical scope is augmented with container scope information. For example, variable x appearing in an if body in main would have the scope module.main.if0-ifbody, whereas variable x appearing in a nested if body in main would have the scope module.main.if0.if-body.if0.if-body.

This pass traverses the annotated CAST to determine scoping information for all containers and variables. In addition, for each container, it keeps track of which variables are modified or accessed within the container and modifies the container attributes accordingly.

variable_version_pass.py

TODO:(Describe variable version scheme.) This pass determines the versions of all AnnCastName nodes and populates the dictionaries for container nodes that hold the mappings of variable ids to their highest version in that scope.

Within a container, each variable starts at version 0. If the variable is assigned to within that container scope, its version increases. For example, assuming that this code snippet is the first if in main, the variable versions of x are shown in the comments:

   if (x > 100)     # x ver 0 id 1 in module.main.if0.if-expr
   {
           
       x = x + y;   # x ver 0 id 1  module.main.if0.if-body (on RHS)
                    # x ver 1 id 1  module.main.if0.if-body (on LHS)
               
       x = x + 1;   # x ver 1 id 1  module.main.if0.if-body (on RHS)
                    # x ver 2 id 1  module.main.if0.if-body (on LHS)
   }

This pass determines the correct version of each instance of a variable reference and stores that version in the respective AnnCastName node. In addition, each container has an attribute to store the highest versions of the variables seen in that container scope. This pass stores that information for each container. TODO: Mention that we distinguish highest versions along different branches, etc. This allows us to retain most (all?) of the lexical scoping information that would be lost if we only had container scope.

grfn_var_creation_pass.py

(Note: at this point, we want to create the GrFN graphs and are not concerned with the lambda's that are required for execution.)

To make a GrFN VariableNode, we need

• VariableIdentifier:
  • namespace: str
  • scope: str
  • var_name: str
  • index: int (which is the version attribute in AnnCastName nodes)
  • metadata: List[TypedMetadata] (for now just an empty list)

In Loop and Conditional containers, we will need to store the same GrFN VariableNodes at different AnnCastName nodes. For example, the version 0 of a variable in the If scope should be used for version 0 of ifbody and elsebody scope.

We also want to start on what VariableNodes will be on each side of an interface or decision node, and create the condtional VariableNodes.

Goal: At the end of this pass, we will have created all VariableNodes that will be used in the GrFN. We will also have made note of what VariableNodes are used at container interfaces, container decision nodes, and container conditional nodes.

to_grfn_pass.py

Annotated CAST Passes Details

Prototype for new Annotated Cast pass:

Each pass does a traversal of the annotated CAST, which means that code for the visitor pattern is repeated on any given pass. To facilitate implementing a new pass, we have a prototype of the visitor code that can be used as a starting point for a new pass. This is in the branch in the file ann_cast_prototype.py.

(TODO: Instead remove this here and instead add pointer ann_cast_prototype.py as that is the reference implementation.)