Mike Gerwitz

Activist for User Freedom

aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorMike Gerwitz <gerwitm@lovullo.com>2016-07-05 09:49:26 -0400
committerMike Gerwitz <gerwitm@lovullo.com>2016-07-05 23:49:30 -0400
commit6bb4c0583042041acb9fa4f6107da3ca1c862e90 (patch)
tree08f4a3591ad313ffa8d90cab327a9a84d313f6ed
parent93287bd1017889dac7d69aef582194ec776bd93b (diff)
downloadtame-6bb4c0583042041acb9fa4f6107da3ca1c862e90.tar.gz
tame-6bb4c0583042041acb9fa4f6107da3ca1c862e90.tar.bz2
tame-6bb4c0583042041acb9fa4f6107da3ca1c862e90.zip
Add (beginning of) graph API
* doc/tame.texi: Add graph include. * src/graph.xsl: Added. * test/graph-test.xsl: Added. * test/graph.xspec: Added.
-rw-r--r--doc/tame.texi3
-rw-r--r--src/graph.xsl85
-rw-r--r--test/graph-test.xsl82
-rw-r--r--test/graph.xspec110
4 files changed, 280 insertions, 0 deletions
diff --git a/doc/tame.texi b/doc/tame.texi
index 10ed1d0..760e302 100644
--- a/doc/tame.texi
+++ b/doc/tame.texi
@@ -79,6 +79,7 @@ Free Documentation License".
@menu
* Macro Expansion::
+* Dependency Graph::
@end menu
@node Macro Expansion
@@ -92,6 +93,8 @@ Free Documentation License".
@include ../src/preproc/expand/expand-sequence.texi
@raisesections
+@include ../src/graph.texi
+
@include license.texi
@bye
diff --git a/src/graph.xsl b/src/graph.xsl
new file mode 100644
index 0000000..727d3f5
--- /dev/null
+++ b/src/graph.xsl
@@ -0,0 +1,85 @@
+<?xml version="1.0"?>
+<!--
+ Dependency graph
+
+ Copyright (C) 2016 LoVullo Associates, Inc.
+
+ This file is part of TAME.
+
+ TAME is free software: you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation, either version 3 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program. If not, see
+ <http://www.gnu.org/licenses/>.
+-->
+<stylesheet version="2.0"
+ xmlns="http://www.w3.org/1999/XSL/Transform"
+ xmlns:xs="http://www.w3.org/2001/XMLSchema"
+ xmlns:f="http://mikegerwitz.com/hoxsl/apply"
+ xmlns:graph="http://www.lovullo.com/tame/graph"
+ xmlns:preproc="http://www.lovullo.com/rater/preproc">
+
+<import href="../hoxsl/src/apply.xsl" />
+
+<!--
+ @node Dependency Graph
+ @section Dependency Graph
+
+ The dependency graph is a directed graph consisting of
+ every known symbol,
+ post-expansion (@pxref{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
+ @code{preproc:sym-dep} nodes,
+ and edges by child @code{preproc:sym-ref} nodes.
+ Graphs are represented by @code{preproc:sym-deps}.
+ The graph of each package is considered to be a subgraph of the
+ entire dependency graph for a particular system.@c
+ @footnote{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.}
+-->
+
+<!--
+ Retrieve dependenices for @var{$symbol} on the @var{$graph},
+ using the lookup function @var{$lookup} to resolve external
+ subgraphs.
+ @var{$lookup} will be used only if the symbol cannot be
+ found in @var{$graph},
+ in which case the result of @var{$lookup} will used used in a
+ recursive call as the new @var{$graph}.
+
+ From a graph perspective,
+ the dependencies are edges on the @var{$symbol} vertex.
+-->
+<function name="graph:dep-lookup" as="element( preproc:sym-dep )?">
+ <param name="symbol" as="element( preproc:sym )" />
+ <param name="graph" as="element( preproc:sym-deps )" />
+ <param name="lookup" />
+
+ <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( $symbol,
+ f:apply( $lookup, $symbol ),
+ $lookup )
+ else
+ ()" />
+</function>
+
+</stylesheet>
diff --git a/test/graph-test.xsl b/test/graph-test.xsl
new file mode 100644
index 0000000..40d183e
--- /dev/null
+++ b/test/graph-test.xsl
@@ -0,0 +1,82 @@
+<?xml version="1.0"?>
+<!--
+ Tests dependency graph
+
+ Copyright (C) 2016 LoVullo Associates, Inc.
+
+ This file is part of TAME.
+
+ TAME is free software: you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation, either version 3 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program. If not, see
+ <http://www.gnu.org/licenses/>.
+-->
+<stylesheet version="2.0"
+ xmlns="http://www.w3.org/1999/XSL/Transform"
+ xmlns:xs="http://www.w3.org/2001/XMLSchema"
+ xmlns:graph="http://www.lovullo.com/tame/graph"
+ xmlns:preproc="http://www.lovullo.com/rater/preproc"
+ xmlns:foo="http://www.lovullo.com/_junk">
+
+<!-- SUT -->
+<import href="../src/graph.xsl" />
+
+<import href="graph-test.xsl.apply" />
+
+
+<variable name="foo:document" as="element( foo:root )">
+ <foo:root>
+ <preproc:symtable>
+ <preproc:sym name="local" />
+ <preproc:sym name="local-dep-a" />
+ <preproc:sym name="local-dep-b" />
+
+ <preproc:sym name="external"
+ src="not-here" />
+
+ <!-- says remote, but has local symbol deps -->
+ <preproc:sym name="external-but-not"
+ src="not-here" />
+
+ <preproc:sym name="missing-deps" />
+ </preproc:symtable>
+
+ <preproc:sym-deps>
+ <preproc:sym-dep name="local">
+ <preproc:sym-ref name="local-dep-a" />
+ <preproc:sym-ref name="local-dep-b" />
+ </preproc:sym-dep>
+
+ <preproc:sym-dep name="local-dep-a">
+ <preproc:sym-ref name="local-dep-a-dep" />
+ </preproc:sym-dep>
+
+ <preproc:sym-dep name="external-but-not">
+ <preproc:sym-ref name="dep-external-but-not" />
+ </preproc:sym-dep>
+ </preproc:sym-deps>
+ </foo:root>
+</variable>
+
+<function name="foo:lookup">
+ <param name="yield" as="element()" />
+ <param name="symbol" as="element( preproc:sym )" />
+
+ <!-- stub graph -->
+ <preproc:sym-deps>
+ <preproc:sym-dep name="{$symbol/@name}">
+ <sequence select="$yield" />
+ </preproc:sym-dep>
+ </preproc:sym-deps>
+</function>
+
+</stylesheet>
diff --git a/test/graph.xspec b/test/graph.xspec
new file mode 100644
index 0000000..aef7be9
--- /dev/null
+++ b/test/graph.xspec
@@ -0,0 +1,110 @@
+<?xml version="1.0"?>
+<!--
+ Tests dependency graph
+
+ Copyright (C) 2016 LoVullo Associates, Inc.
+
+ This file is part of TAME.
+
+ TAME is free software: you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation, either version 3 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program. If not, see
+ <http://www.gnu.org/licenses/>.
+-->
+<description xmlns="http://www.jenitennison.com/xslt/xspec"
+ xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
+ xmlns:x="http://www.jenitennison.com/xslt/xspec"
+ xmlns:graph="http://www.lovullo.com/tame/graph"
+ xmlns:preproc="http://www.lovullo.com/rater/preproc"
+ xmlns:foo="http://www.lovullo.com/_junk"
+ stylesheet="graph-test.xsl">
+
+ <scenario label="graph:dep-lookup">
+ <scenario label="given a symbol">
+ <scenario label="in the same package">
+ <scenario label="where dependencies exist">
+ <call function="graph:dep-lookup">
+ <param name="symbol"
+ select="$foo:document/preproc:symtable
+ /preproc:sym[ @name='local' ]" />
+ <param name="graph"
+ select="$foo:document/preproc:sym-deps" />
+
+ <param name="lookup" select="()" />
+ </call>
+
+ <expect label="returns local dependencies"
+ test="$x:result is
+ $foo:document/preproc:sym-deps/preproc:sym-dep[
+ @name='local' ]" />
+ </scenario>
+
+
+ <scenario label="with external @src but local deps">
+ <call function="graph:dep-lookup">
+ <param name="symbol"
+ select="$foo:document/preproc:symtable
+ /preproc:sym[ @name='external-but-not' ]" />
+ <param name="graph"
+ select="$foo:document/preproc:sym-deps" />
+
+ <param name="lookup" select="()" />
+ </call>
+
+ <expect label="returns local dependencies"
+ test="$x:result is
+ $foo:document/preproc:sym-deps/preproc:sym-dep[
+ @name='external-but-not' ]" />
+ </scenario>
+
+
+ <scenario label="where dependencies are missing">
+ <call function="graph:dep-lookup">
+ <param name="symbol"
+ select="$foo:document/preproc:symtable
+ /preproc:sym[ @name='missing-deps' ]" />
+ <param name="graph"
+ select="$foo:document/preproc:sym-deps" />
+
+ <param name="lookup" select="()" />
+ </call>
+
+ <expect label="return empty sequence"
+ test="empty( $x:result )" />
+ </scenario>
+ </scenario>
+
+
+ <scenario label="in a separate package">
+ <variable name="foo:expected-lookup" as="element()">
+ <foo:lookup-ok />
+ </variable>
+
+ <scenario label="where dependencies exist">
+ <call function="graph:dep-lookup">
+ <param name="symbol"
+ select="$foo:document/preproc:symtable
+ /preproc:sym[ @name='external' ]" />
+ <param name="graph"
+ select="$foo:document/preproc:sym-deps" />
+
+ <param name="lookup"
+ select="foo:lookup( $foo:expected-lookup )" />
+ </call>
+
+ <expect label="returns external dependenices"
+ test="exists( $x:result/foo:lookup-ok )" />
+ </scenario>
+ </scenario>
+ </scenario>
+ </scenario>
+</description>