Check Use Def Cycles

This algorithm traverses the a source model and checks that there are no cycles in the use-def graph.

Input

1. A list tul of translation units.

2. An analysis data structure a representing the results of analysis so far. The use-def map must already be computed. The visited symbol set, use-def path set, and use-def path list must be empty.

Output

1. The unmodified analysis a, if the check passes; otherwise an error.

Procedure

1. Visit each translation unit in tul with input a. Return a or an error as the result.

AST Visitor Methods

Each method accepts an analysis data structure a as input and yields either a new analysis data structure a' or an error as output.

1. Translation units: For each translation unit tu, visit each definition appearing in tu.

2. Definitions: For each definition d that may be involved in a cycle:

   1. Let s be the unique symbol representing d.

   2. Check whether s appears in the use-def symbol set of a. If it does, then the use-def matching list of a represents a cycle. Throw a semantic error. Use the use-def matching list to construct the cycle for the error message.

   3. Otherwise if s is not in the visited symbol set of a, then

      1. Let a' be the analysis data structure that results from adding s to the use-def symbol set set of a.

      2. Visit each use appearing in d with input a'.

      3. Let a'' be the analysis data structure that results from adding s to the visited symbol set of a.

      4. Yield a'' as the result.

   4. Otherwise we have already visited s; yield a as the result.

3. Uses: For each AST node n that represents a use:

   1. Look in the use-def map of n to get the symbol s corresponding to n. Throw an internal error if it is not there.

   2. Use n and s to construct a use-def matching m.

   3. Let a' be the analysis data structure that results from adding m to the use-def matching list of a.

   4. Visit the definition corresponding to s with input a'.

   5. Return a or an error.