XSLT 1.0：行走並過濾樹向後

Question

我有下面的XML：

<things> 
    <thing name="Foo" available="yes"/> 
    <thing name="Bar" available="no"/> 
    <thing name="Baz" available="yes"> 
    <parent name="Foo"/> 
    <parent name="Bar"/> 
    </thing> 
    <thing name="Qux" available="no"> 
    <parent name="Foo"/> 
    <parent name="Bar"/> 
    </thing> 
    <thing name="Waldo" available="yes"> 
    <parent name="Foo"/> 
    <parent name="Bar"/> 
    <parent name="Baz"/> 
    <parent name="Qux"/> 
    </thing> 
</things> 

這代表如下所示的結構：

• 富
  • 巴茲
    • 沃爾多
  • Qux
    • 金都
  • 金都
• 酒吧
  • 巴茲
    • 金都
  • Qux
    • 金都
  • 金都

實際的XML是相當大，嵌套深。不可改變的事情可以在任何地方。沒有循環（有自己作爲祖先的東西）。

現在我想要生成Waldo的所有可能路徑，過濾出包含不可用路徑的路徑。像下面這樣的結果的東西就是我在尋找：

<ul> 
    <li> 
    <a href="#Foo">Foo</a> 
    <ul> 
     <li> 
     <a href="#Baz">Baz</a> 
     <ul> 
      <li> 
      <b>Waldo</b> 
      </li> 
     </ul> 
     </li> 
    </ul> 
    </li> 
</ul> 
<ul> 
    <li> 
    <a href="#Foo">Foo</a> 
    <ul> 
     <li> 
     <b>Waldo</b> 
     </li> 
    </ul> 
    </li> 
</ul> 

即：

• 富
  • 巴茲
    • 金都
• 富
  • 金都

從葉節點開始，查找樹，產生所有可能的路徑而忽略不可用路徑讓我難住了。任何見解，散文，僞代碼或XSLT都非常感謝！

Answer 1

該轉化：

<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform" 
xmlns:ext="http://exslt.org/common" exclude-result-prefixes="ext"> 
<xsl:output omit-xml-declaration="yes" indent="yes"/> 
<xsl:strip-space elements="*"/> 

<xsl:key name="kChildren" match="thing" use="parent/@name"/> 

<xsl:template match="/*"> 
    <xsl:variable name="vrtfPass1"> 
     <things> 
      <xsl:apply-templates select="thing[not(parent)]"/> 
     </things> 
    </xsl:variable> 


    <xsl:apply-templates select="ext:node-set($vrtfPass1)/*" 
         mode="pass2"/> 
</xsl:template> 

<xsl:template match="thing"> 
    <xsl:copy> 
     <xsl:copy-of select="@*"/> 
     <xsl:apply-templates select="key('kChildren', @name)"/> 
    </xsl:copy> 
</xsl:template> 

    <xsl:template match="node()|@*" mode="pass2"> 
    <xsl:copy> 
     <xsl:apply-templates select="node()|@*" mode="pass2"/> 
    </xsl:copy> 
</xsl:template> 

<xsl:template mode="pass2" 
     match="*[not(@name = 'Waldo' or .//*[@name='Waldo'])]" /> 
</xsl:stylesheet> 

當所提供的XML文檔施加：

<things> 
    <thing name="Foo" available="yes"/> 
    <thing name="Bar" available="no"/> 
    <thing name="Baz" available="yes"> 
     <parent name="Foo"/> 
     <parent name="Bar"/> 
    </thing> 
    <thing name="Qux" available="no"> 
     <parent name="Foo"/> 
     <parent name="Bar"/> 
    </thing> 
    <thing name="Waldo" available="yes"> 
     <parent name="Foo"/> 
     <parent name="Bar"/> 
     <parent name="Qux"/> 
    </thing> 
</things> 

產生僅包含 「分支」 含有 「金都」 結果：

<things> 
    <thing name="Foo" available="yes"> 
     <thing name="Qux" available="no"> 
     <thing name="Waldo" available="yes"/> 
     </thing> 
     <thing name="Waldo" available="yes"/> 
    </thing> 
    <thing name="Bar" available="no"> 
     <thing name="Qux" available="no"> 
     <thing name="Waldo" available="yes"/> 
     </thing> 
     <thing name="Waldo" available="yes"/> 
    </thing> 
</things> 

作爲練習，讀者可以將其轉換爲任何最終的HTML格式。

說明：

1. 這是一個兩通轉化。

2. 第一遍構造一棵樹，其中明確表示父子關係。

3. 第二遍是標識規則，通過用空體（「刪除」模板）的模板覆蓋對於不具有屬性name與字串值"Waldo"含有thing子樹。

第一遍的結果是：

<things> 
    <thing name="Foo" available="yes"> 
     <thing name="Baz" available="yes"/> 
     <thing name="Qux" available="no"> 
     <thing name="Waldo" available="yes"/> 
     </thing> 
     <thing name="Waldo" available="yes"/> 
    </thing> 
    <thing name="Bar" available="no"> 
     <thing name="Baz" available="yes"/> 
     <thing name="Qux" available="no"> 
     <thing name="Waldo" available="yes"/> 
     </thing> 
     <thing name="Waldo" available="yes"/> 
    </thing> 
</things> 

第二遍剝掉2個<thing name="Baz" available="yes"/>元件以產生最終結果。