From: Lady <redacted>
Date: Wed, 3 Jul 2024 01:42:56 +0000 (-0400)
Subject: Fix/improve recursive dependency detection
X-Git-Tag: 0.12.1^0
X-Git-Url: https://git.ladys.computer/Shushe/commitdiff_plain/c84c2b38caf34807fd1c52a8f19fcf0af7e9807e?ds=sidebyside;hp=155d175a24d3bccf25677cc7e33314dc963da766

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 2501355..f2efd18 100644
--- 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"/>