Fix/improve recursive dependency detection

The old method of detecting recursive dependencies was overcomplicated
and only worked in the simple case of A → B → C → A and not
A → B → C → B. This new method works as follows:

- Given a dependency path…

  - Get all of the links in the last document in the path.

  - If there are no links, return the path.

  - If there are links which point to a file in the path, it is a
    recursive dependency. Return the path ending at the point of
    recursion.

  - Otherwise (there are nonrecursive links), process each path which
    results from appending each link to the end of the current path and
    return all of them.

The algorithm ends with a set of paths to leaf nodes in the dependency
tree, and each nonroot node in this tree (leaf or branch) is a
dependency. This is what the behaviour should have been from the
beginning. (The old method attempted to process the tree in layers,
rather than as a set of paths.)

diff --git a/lib/expandmetadata.xslt b/lib/expandmetadata.xslt
index 2501355ef5bca2b455b569d8736c0e8acb0de6eb..f2efd18209177db3a846d1053cf16955ed2a74f8 100644 (file)
--- a/lib/expandmetadata.xslt
+++ b/lib/expandmetadata.xslt
@@ -25,72 +25,56 @@ If a copy of the M·P·L was not distributed with this file, You can obtain one
 >
        <variable name="builddir" select="//书社vocab:BuildDirectory/@nfo:fileUrl"/>
        <variable name="files" select="//书社vocab:SourceFile|//书社vocab:IncludeFile"/>
-       <template name="书社:process-dependencies">
-               <param name="processed"/>
-               <param name="unprocessed"/>
-               <variable name="queue">
-                       <copy-of select="exsl:node-set($unprocessed)/书社:dependency-root"/>
-                       <for-each select="exsl:node-set($unprocessed)/书社:dependency">
-                               <if test="not((exsl:node-set($processed)/书社:*|preceding-sibling::书社:*|following-sibling::书社:recursive-dependency)[string()=string(current())])">
-                                       <copy-of select="."/>
-                               </if>
-                       </for-each>
-               </variable>
-               <variable name="old">
-                       <copy-of select="exsl:node-set($processed)/书社:dependency-root"/>
-                       <copy-of select="exsl:node-set($processed)/书社:recursive-dependency"/>
-                       <for-each select="exsl:node-set($unprocessed)/书社:recursive-dependency">
-                               <if test="not((exsl:node-set($processed)/书社:recursive-dependency|preceding-sibling::书社:recursive-dependency)[string()=string(current())])">
-                                       <copy-of select="."/>
-                               </if>
-                       </for-each>
-                       <for-each select="exsl:node-set($processed)/书社:dependency">
-                               <if test="not(exsl:node-set($unprocessed)/书社:recursive-dependency[string()=string(current())])">
-                                       <copy-of select="."/>
-                               </if>
-                       </for-each>
-                       <copy-of select="$queue"/>
-               </variable>
-               <variable name="new">
-                       <for-each select="exsl:node-set($queue)/书社:*">
-                               <for-each select="$files[@rdf:about=string(current()) and nie:interpretedAs/nfo:PlainTextDocument]">
-                                       <variable name="parent" select="@rdf:about"/>
-                                       <variable name="uri" select="书社vocab:hasParsedFile/@nfo:fileUrl"/>
-                                       <for-each select="document($uri)//书社:link[@xlink:show='embed']">
-                                               <variable name="identifier" select="string(current()/@xlink:href)"/>
-                                               <variable name="is-dir" select="substring($identifier, string-length($identifier))='/'"/>
-                                               <for-each select="$files/@rdf:about[string(.)=$identifier or $is-dir and starts-with(., $identifier)]">
-                                                       <sort select="." data-type="text" lang="zxx" case-order="upper-first"/>
-                                                       <choose>
-                                                               <when test="exsl:node-set($old)/书社:dependency-root[string()=string(current())]">
-                                                                       <书社:recursive-dependency>
-                                                                               <value-of select="$parent"/>
-                                                                       </书社:recursive-dependency>
-                                                               </when>
-                                                               <otherwise>
-                                                                       <书社:dependency>
-                                                                               <value-of select="."/>
-                                                                       </书社:dependency>
-                                                               </otherwise>
-                                                       </choose>
-                                               </for-each>
+       <template name="书社:collect-dependency-paths">
+               <param name="path" select="/.."/>
+               <variable name="parent" select="string($path/*[last()])"/>
+               <variable name="children-fragment">
+                       <for-each select="$files[@rdf:about=$parent and nie:interpretedAs/nfo:PlainTextDocument]">
+                               <variable name="uri" select="书社vocab:hasParsedFile/@nfo:fileUrl"/>
+                               <for-each select="document($uri)//书社:link[@xlink:show='embed']">
+                                       <variable name="identifier" select="string(@xlink:href)"/>
+                                       <variable name="is-dir" select="substring($identifier, string-length($identifier))='/'"/>
+                                       <for-each select="$files/@rdf:about[string(.)=$identifier or $is-dir and starts-with(., $identifier)]">
+                                               <sort select="." data-type="text" lang="zxx" case-order="upper-first"/>
+                                               <choose>
+                                                       <when test="$path/*[string(.)=string(current())]">
+                                                               <书社:recursive-dependency>
+                                                                       <value-of select="."/>
+                                                               </书社:recursive-dependency>
+                                                       </when>
+                                                       <otherwise>
+                                                               <书社:dependency>
+                                                                       <value-of select="."/>
+                                                               </书社:dependency>
+                                                       </otherwise>
+                                               </choose>
                                        </for-each>
                                </for-each>
                        </for-each>
                </variable>
+               <variable name="children" select="exsl:node-set($children-fragment)"/>
                <choose>
-                       <when test="exsl:node-set($new)/*">
-                               <call-template name="书社:process-dependencies">
-                                       <with-param name="processed">
-                                               <copy-of select="$old"/>
-                                       </with-param>
-                                       <with-param name="unprocessed">
-                                               <copy-of select="$new"/>
-                                       </with-param>
-                               </call-template>
+                       <when test="$children/*">
+                               <for-each select="$children/书社:recursive-dependency">
+                                       <书社:dependency-path>
+                                               <copy-of select="$path[string(.)=string(current())]/preceding-sibling::*"/>
+                                               <copy-of select="."/>
+                                       </书社:dependency-path>
+                               </for-each>
+                               <for-each select="$children/书社:dependency">
+                                       <variable name="path-fragment">
+                                               <copy-of select="$path"/>
+                                               <copy-of select="."/>
+                                       </variable>
+                                       <call-template name="书社:collect-dependency-paths">
+                                               <with-param name="path" select="exsl:node-set($path-fragment)"/>
+                                       </call-template>
+                               </for-each>
                        </when>
                        <otherwise>
-                               <copy-of select="$old"/>
+                               <书社:dependency-path>
+                                       <copy-of select="$path"/>
+                               </书社:dependency-path>
                        </otherwise>
                </choose>
        </template>
@@ -188,13 +172,21 @@ If a copy of the M·P·L was not distributed with this file, You can obtain one
        </template>
        <template match="书社vocab:SourceFile|书社vocab:IncludeFile" mode="书社:dependencies">
                <if test="nie:interpretedAs/nfo:PlainTextDocument">
-                       <call-template name="书社:process-dependencies">
-                               <with-param name="unprocessed">
-                                       <书社:dependency-root>
-                                               <value-of select="@rdf:about"/>
-                                       </书社:dependency-root>
-                               </with-param>
-                       </call-template>
+                       <variable name="path-fragment">
+                               <书社:dependency-root>
+                                       <value-of select="@rdf:about"/>
+                               </书社:dependency-root>
+                       </variable>
+                       <variable name="paths-fragment">
+                               <call-template name="书社:collect-dependency-paths">
+                                       <with-param name="path" select="exsl:node-set($path-fragment)"/>
+                               </call-template>
+                       </variable>
+                       <for-each select="exsl:node-set($paths-fragment)/*/*[not(self::书社:dependency-root)]">
+                               <if test="not(preceding::*[string(.)=string(current())])">
+                                       <copy-of select="."/>
+                               </if>
+                       </for-each>
                </if>
        </template>
        <output method="xml" encoding="UTF-8"/>