Appendix B Dependency Graph

The dependency graph is a directed graph consisting of every known symbol, post-expansion (see Macro Expansion). Cycles are produced only by function recursion and otherwise cause an error, so the graph is studied as a DAG (directed acyclic graph) with few exceptions.

Vertices in the dependency graph are represented by preproc:sym-dep nodes, and edges by child preproc:sym-ref nodes. Graphs are represented by preproc:sym-deps. The graph of each package is considered to be a subgraph of the entire dependency graph for a particular system.⁸

function: element( preproc:sym-deps ) graph:make-from-vertices (vertices as element( preproc:sym-dep )*)

xmlns:graph="http://www.lovullo.com/tame/graph"

Create a graph from the given vertex set $vertices. The resulting graph will be normalized with duplicate vertices and edges removed, making it suitable for ad hoc graph generation.⁹

Definition:

<function name="graph:make-from-vertices"  as="element( preproc:sym-deps )">
  <param name="vertices"  as="element( preproc:sym-dep )*" />

  <variable name="graph"  as="element( preproc:sym-deps )">
    <preproc:sym-deps>
        <sequence select="$vertices" />
    </preproc:sym-deps>
  </variable>

  <!-- dedupe/normalize -->
  <sequence select="graph:union( $graph )" />
</function>

function: element( preproc:sym-deps ) graph:reverse (graph as element( preproc:sym-deps ))

xmlns:graph="http://www.lovullo.com/tame/graph"

Produce a new graph that is the transpose of $graph—that is, the graph $graph with the direction of all of its edges reversed.

This is useful for processing what symbols are used by other symbols.

For example:

G:  A->B->C->E
     \
      `->D

G': A<-B<-C<-E
    ^
     `D

Figure B.1: G’ is the transpose of G

Edge attributes (preproc:sym-ref/@*) will be set to the union of all attributes on all edges of the same @name in $graph. If edge attributes do not share the same value, the behavior is undefined.

Definition:

<function name="graph:reverse"  as="element( preproc:sym-deps )">
  <param name="graph"  as="element( preproc:sym-deps )" />

  <variable name="reversed"  as="element( preproc:sym-dep )*">
    <for-each-group select="$graph//preproc:sym-ref"  group-by="@name">
      <preproc:sym-dep name="{@name}">
        <for-each select="current-group()/ancestor::preproc:sym-dep">
          <preproc:sym-ref>
            <sequence select="current-group()/@*" />

            <!-- keep our name (overrides the above) -->
            <attribute name="name"  select="@name" />
          </preproc:sym-ref>
        </for-each>
      </preproc:sym-dep>
    </for-each-group>
  </variable>

  <preproc:sym-deps>
    <!-- vertices in $graph with no dependencies will not be in
         $reversed -->
    <for-each select="$graph/preproc:sym-dep[ not( @name = $reversed/preproc:sym-ref/@name ) ]">
      <preproc:sym-dep name="{@name}" />
    </for-each>

    <sequence select="$reversed" />
  </preproc:sym-deps>
</function>

function: element( preproc:sym-deps )* graph:union (graphs as element( preproc:sym-deps )*)

xmlns:graph="http://www.lovullo.com/tame/graph"

Merge sequence of graphs $graphs into a single graph by taking the union of all vertices and edges. Directionality will be preserved.

Edge attributes (preproc:sym-ref/@*) will be set to the union of all attributes on all edges of the same @name. If edge attributes do not share the same value, the behavior is undefined.

For example:

G₁:  A->B->C
G₂:  C->A
G₃:  B->C->D

G∪:  A->B->C->D
     ^____/

Figure B.2: (G₁ ∪ G₂ ∪ G₃)

This function also removes duplicate vertices and edges, so it can be used with a single (or multiple) graphs to normalize and tidy things up. Any unknown XML nodes are removed.

Definition:

<function name="graph:union"  as="element( preproc:sym-deps )*">
  <param name="graphs"  as="element( preproc:sym-deps )*" />

  <preproc:sym-deps>
    <for-each-group select="$graphs/preproc:sym-dep"  group-by="@name">
      <preproc:sym-dep name="{@name}">
        <for-each-group select="current-group()/preproc:sym-ref"  group-by="@name">
          <preproc:sym-ref>
            <sequence select="current-group()/@*" />

            <!-- keep our name (overrides the above) -->
            <attribute name="name"  select="@name" />
          </preproc:sym-ref>
        </for-each-group>
      </preproc:sym-dep>
    </for-each-group>
  </preproc:sym-deps>
</function>