Add graph:reverse

* src/graph.xsl: Added graph:reverse
* test/graph.xspec: Associated tests
* test/graph-test.xsl: Added test data

2 files changed, 96 insertions, 0 deletions

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>