Next: , Previous: , Up: Top   [Contents][Index]

## 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.8

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.9 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>


### (8)

The node names are for compatibility with legacy systems and may change in the future; always use the graph API, and only use the node QNames for type checks.

### (9)

This is done by calling graph:union#1.

Next: , Previous: , Up: Top   [Contents][Index]