Mike Gerwitz

Activist for User Freedom

aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorMike Gerwitz <gerwitm@lovullo.com>2016-07-05 12:34:42 -0400
committerMike Gerwitz <gerwitm@lovullo.com>2016-07-06 00:14:50 -0400
commite34cf22d6b84bbcf9a144128fdf6fb7eebc6f357 (patch)
tree99bf2b6113946048524a8323cb444ff05d04d44f
parent6bb4c0583042041acb9fa4f6107da3ca1c862e90 (diff)
downloadtame-e34cf22d6b84bbcf9a144128fdf6fb7eebc6f357.tar.gz
tame-e34cf22d6b84bbcf9a144128fdf6fb7eebc6f357.tar.bz2
tame-e34cf22d6b84bbcf9a144128fdf6fb7eebc6f357.zip
Add graph:reverse
* src/graph.xsl: Added graph:reverse * test/graph.xspec: Associated tests * test/graph-test.xsl: Added test data
-rw-r--r--src/graph.xsl62
-rw-r--r--test/graph-test.xsl32
-rw-r--r--test/graph.xspec64
3 files changed, 158 insertions, 0 deletions
diff --git a/src/graph.xsl b/src/graph.xsl
index 727d3f5..692f577 100644
--- a/src/graph.xsl
+++ b/src/graph.xsl
@@ -82,4 +82,66 @@
()" />
</function>
+
+<!--
+ Produce a new graph that is the transpose of
+ @var{$graph}@mdash{}that is,
+ the graph @var{$graph} with the direction of all of its edges
+ reversed.
+
+ This is useful for processing what symbols are @emph{used by} other
+ symbols.
+
+ For example:
+
+ @float Figure, fig:reverse-graph
+ @verbatim
+ G: A->B->C->E
+ \
+ `->D
+
+ G': A<-B<-C<-E
+ ^
+ `D
+ @end verbatim
+ @caption{G' is the transpose of G}
+ @end float
+
+ Edge attributes (@code{preproc:sym-ref/@@*)} will be set to the
+ union of all attributes on all edges of the same @code{@@name} in
+ @code{$graph}.
+ @emph{If edge attributes do not share the same value,
+ the behavior is undefined.}
+-->
+<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>
+
</stylesheet>
diff --git a/test/graph-test.xsl b/test/graph-test.xsl
index 40d183e..fea46fa 100644
--- a/test/graph-test.xsl
+++ b/test/graph-test.xsl
@@ -67,6 +67,38 @@
</foo:root>
</variable>
+
+<!-- a graph that is easier to mentally grasp when reversed -->
+<variable name="foo:reverse-graph" as="element( preproc:sym-deps )">
+ <preproc:sym-deps>
+ <preproc:sym-dep name="A">
+ <preproc:sym-ref name="B" />
+ <preproc:sym-ref name="C" cattr="cvalue" />
+ </preproc:sym-dep>
+
+ <preproc:sym-dep name="B">
+ <preproc:sym-ref name="C" cattr="cvalue" cattr2="cvalue2" />
+ </preproc:sym-dep>
+
+ <preproc:sym-dep name="C">
+ <preproc:sym-ref name="D" />
+ </preproc:sym-dep>
+
+ <!-- produces a cycle -->
+ <preproc:sym-dep name="D">
+ <preproc:sym-ref name="B" />
+ </preproc:sym-dep>
+
+ <!-- disconnected -->
+ <preproc:sym-dep name="X">
+ <preproc:sym-ref name="Z" />
+ </preproc:sym-dep>
+
+ <preproc:sym-dep name="Z" />
+ </preproc:sym-deps>
+</variable>
+
+
<function name="foo:lookup">
<param name="yield" as="element()" />
<param name="symbol" as="element( preproc:sym )" />
diff --git a/test/graph.xspec b/test/graph.xspec
index aef7be9..14a04ef 100644
--- a/test/graph.xspec
+++ b/test/graph.xspec
@@ -107,4 +107,68 @@
</scenario>
</scenario>
</scenario>
+
+
+ <scenario label="graph:reverse on a disconnected DAG">
+ <call function="graph:reverse">
+ <param name="graph"
+ select="$foo:reverse-graph" />
+ </call>
+
+ <!-- "root" (walk=0) vertices are used by nothing -->
+
+ <expect label="reverses walk=0 edges (A)"
+ test="empty(
+ $x:result/preproc:sym-dep[ @name = 'A' ]/* )" />
+
+ <expect label="reverses walk=0 edges (X)"
+ test="empty(
+ $x:result/preproc:sym-dep[ @name = 'X' ]/* )" />
+
+
+ <expect label="reverses edges recursively (B-A)"
+ test="exists( $x:result/preproc:sym-dep[ @name = 'B' ]
+ /preproc:sym-ref[ @name = 'A' ] )" />
+
+ <!-- circular -->
+ <expect label="reverses edges recursively (B-D)"
+ test="exists( $x:result/preproc:sym-dep[ @name = 'B' ]
+ /preproc:sym-ref[ @name = 'D' ] )" />
+
+ <expect label="reverses edges recursively (C-A)"
+ test="exists( $x:result/preproc:sym-dep[ @name = 'C' ]
+ /preproc:sym-ref[ @name = 'A' ] )" />
+
+ <expect label="reverses edges recursively (C-B)"
+ test="exists( $x:result/preproc:sym-dep[ @name = 'C' ]
+ /preproc:sym-ref[ @name = 'B' ] )" />
+
+ <expect label="reverses edges recursively (D-C)"
+ test="exists( $x:result/preproc:sym-dep[ @name = 'D' ]
+ /preproc:sym-ref[ @name = 'C' ] )" />
+
+ <expect label="reverses walk=1 edges (Z-X)"
+ test="exists( $x:result/preproc:sym-dep[ @name = 'Z' ]
+ /preproc:sym-ref[ @name = 'X' ] )" />
+
+
+ <!-- if done properly, we should have no new edges (the direction
+ on existing edges should just be reversed): the new graph
+ should be an isomorphism of the original -->
+ <expect label="does not produce any additional edges"
+ test="count( $x:result//preproc:sym-ref )
+ = count( $foo:reverse-graph//preproc:sym-ref )" />
+
+ <expect label="does not produce any additional vertices"
+ test="count( distinct-values( $x:result//preproc:*/@name ) )
+ = count( distinct-values(
+ $foo:reverse-graph//preproc:*/@name ) )" />
+
+ <expect label="copies union of edge attributes to new edges"
+ test="every $edge in $x:result//preproc:sym-ref
+ [ ancestor::preproc:sym-dep[ @name = 'C' ] ]
+ satisfies
+ $edge/@cattr = 'cvalue'
+ and $edge/@cattr2 = 'cvalue2'" />
+ </scenario>
</description>