B.1 Package Subgraphs

Each package has its own independent dependency graph. These vertices may have virtual edges to other packages’ graphs—edges that will be formed once combined the referenced graph; these edges are indicated with preproc:sym-ref/@src.

Graph operations are usually performed on single packages, but it is occionally necessary to traverse packages to recurisvely resolve dependencies. graph:dep-lookup#3 makes this easy:

TODO: Generic graph functions.

function: element( preproc:sym-dep )? graph:dep-lookup (lookup as xs:sequence*, graph as element( preproc:sym-deps ), symbol as element( preproc:sym ))

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

Retrieve dependenices for $symbol on the $graph, using the lookup function $lookup to resolve external subgraphs. $lookup will be used only if the symbol cannot be found in $graph, in which case the result of $lookup will used used in a recursive call as the new $graph.

From a graph perspective, the dependencies are edges on the $symbol vertex.

Parameters are organized for partial application.

Definition:

<function name="graph:dep-lookup"  as="element( preproc:sym-dep )?">
  <param name="lookup" />
  <param name="graph"  as="element( preproc:sym-deps )" />
  <param name="symbol"  as="element( preproc:sym )" />

  <variable name="deps"  as="element( preproc:sym-dep )?"  select="$graph/preproc:sym-dep [ @name = $symbol/@name ]" />

  <sequence select="if ( exists( $deps ) ) then $deps else if ( $lookup ) then graph:dep-lookup( $lookup, f:apply( $lookup, $symbol ), $symbol ) else ()" />
</function>

graph:dep-lookup#3 can be used together with the convenience function graph:make-from-deps#2 to produce a graph that contains all dependencies for a given symbol list. Used together with graph:reverse#1, a reverse dependency graph can be easily created that provides a useful “used by” relationship.

function: element( preproc:sym-deps )* graph:make-from-deps (lookup as item()+, symbols as element( preproc:sym )*)

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

Create a dependency graph containing all dependencies of the given symbol list $symbols. The graph contains the union of the minimal subset of all package subgraphs—only vertices representing a symbol in $symbols or its direct dependencies are included.

This function is not recursive; it assumes that the given symbol list $symbols is sufficient for whatever operation is being performed.

The lookup function $lookup is invoked once per symbol in $symbols with the preproc:sym to look up. The final result is used to produce a new normalized graph, with any duplicate vertices and edges removed.

Definition:

<function name="graph:make-from-deps"  as="element( preproc:sym-deps )*">
  <param name="lookup"  as="item()+" />
  <param name="symbols"  as="element( preproc:sym )*" />

  <sequence select="graph:make-from-vertices( for $symbol in $symbols return f:apply( $lookup, $symbol ) )" />
</function>