Skip to content

Computing Dependencies

Jump to bottom
Robert L. Bocchino Jr. edited this page Apr 18, 2024 · 7 revisions

This algorithm computes dependencies for a list of translation units.

Input

  1. An analysis data structure a. The input file set of a must record the set of files presented for analysis.

  2. A list tul of FPP translation units.

Output

Procedure

  1. Resolve include specifiers: Recursively resolve include specifiers in tu. Add the path of each included file to the included file set in a. If the level is zero, then add the path of each included file to the direct dependency file set in a.

  2. Build the location specifier map: Traverse each translation unit tu in tul, updating the scope name list as modules are entered and exited. For each location specifier s encountered, do the following:

    1. Let k be the symbol kind specified in s. For example, in the specifier locate constant c at "c.fpp", the symbol kind is constant.

    2. Compute the qualified name q associated with s. For example, if the location specifier locate constant c at "c.fpp" appears inside module M, then q is M.c.

    3. Check the location specifier map for a mapping from (k, q) to some location specifier s'.

    4. If there is no such mapping, then add the mapping from (k, q) to s.

    5. Otherwise

      1. Compute the absolute path p associated with s. For example, if the location specifier locate constant c at "c.fpp" appears in the file /home/foo/bar/baz.fpp, then p is /home/foo/bar/c.fpp.

      2. Compute the absolute path p' associated with s'.

      3. If p does not equal p', then throw an error.

  3. Map uses to locations: Traverse each translation unit tu in tul, updating the scope name list as modules are entered and exited. For each use of a symbol u encountered, do the following:

    1. Resolve u to a list l of possible qualified names. For example, if u is c.d and it appears inside module B which appears inside module A, then l is A.B.c.d, A.c.d, c.d. Construct l with the innermost name first. For example, A.B.c.d appears before A.c.d.

    2. For each qualified name q in l, in order starting with the head of l, check the location specifier map of a for a path p corresponding to q.

    3. If p exists and is not in the input file set of a and is not already in the dependency file set of a, then

      1. If the level is zero, then add p to the direct dependency file set of a.

      2. Add p to the dependency file set of a.

      3. If the file f at p exists, then

        1. Parse f, generating a translation unit tu.

        2. Run this algorithm at the next level on the list [ tu ] with the value of a computed so far, but with an empty scope name list. Restore the current level and scope name list and let the result be the new a.

      4. Otherwise add p to the missing dependency file set of a.

  4. Eliminate included files as dependencies: For each file f in the included file set, if f appears in the dependency file set, then delete it from the set. The dependency is already recorded in the file that includes f.

Clone this wiki locally