Mihaela Mihaljevic
4552d24067
key(), id(), and EXSLT set:leading/set:trailing sorted their result with sorted(by: Node.precedes). precedes recomputes both nodes' document-order keys on every comparison, and each key walks the node to the root taking its index among each parent's children, a linear scan of a wide parent. Over a wide flat fan-out the sort was therefore quadratic. key() also deduplicated its matches with matched.contains(where: ===), a linear membership scan, O(m^2) in the match count. The EXSLT relative() used the cache-less documentOrder, rescanning the parent per node. Sort through sortedByDocumentOrder() (each key computed once behind a shared sibling-index cache), deduplicate key()'s matches through a Set, and give relative() a shared cache. The selected nodes, their document order, and the deduplication are unchanged. A key()-driven transform over a 20k-element document drops from ~1.15s to ~0.43s (~2.7x). The full suite, the Apache Xalan XSLT gold-output corpus, the W3C XPath/XSLT/EXSLT tests, and the WASM build stay green; XSLTKeyIdOrderTests pins key() dedup-and-order and id() document order.
57 lines
2.6 KiB
Swift
57 lines
2.6 KiB
Swift
import Testing
|
|
@testable import PureXML
|
|
|
|
/// `key()`, `id()`, and the EXSLT `set:leading`/`set:trailing` functions return
|
|
/// their nodes in document order. The order is now computed through the cached
|
|
/// `sortedByDocumentOrder`/`documentOrder(cache:)` path (not `sorted(by:precedes)`
|
|
/// or the cache-less key, which rescanned a wide parent per comparison), and
|
|
/// `key()` deduplicates through a set, not a linear membership scan. These pin
|
|
/// that the results are unchanged: the right nodes, in document order, once each.
|
|
@Suite("XSLT key/id/set document order and dedup")
|
|
struct XSLTKeyIdOrderTests {
|
|
@Test("key() returns its matches in document order, deduplicated")
|
|
func test_keyDedupAndOrder() throws {
|
|
// Several values map to overlapping nodes; the node-set second argument
|
|
// unions them and each matching node must appear once, in document order.
|
|
let source = """
|
|
<data>
|
|
<r k="a">1</r><r k="b">2</r><r k="a">3</r><r k="c">4</r><r k="b">5</r>
|
|
<want>a</want><want>b</want><want>a</want>
|
|
</data>
|
|
"""
|
|
let style = """
|
|
<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
|
|
<xsl:output method="xml" indent="no"/>
|
|
<xsl:key name="byK" match="r" use="@k"/>
|
|
<xsl:template match="/">
|
|
<out><xsl:for-each select="key('byK', /data/want)"><xsl:value-of select="."/>,</xsl:for-each></out>
|
|
</xsl:template>
|
|
</xsl:stylesheet>
|
|
"""
|
|
let out = try PureXML.XSLT.transform(stylesheet: style, source: source)
|
|
// k='a' -> nodes 1,3; k='b' -> nodes 2,5. Union, deduplicated, in
|
|
// document order: 1,2,3,5.
|
|
#expect(out.hasSuffix("<out>1,2,3,5,</out>"))
|
|
}
|
|
|
|
@Test("id() with several tokens returns the elements in document order")
|
|
func test_idOrder() throws {
|
|
let source = """
|
|
<!DOCTYPE doc [<!ATTLIST item ref ID #IMPLIED>]>
|
|
<doc><item ref="c">C</item><item ref="a">A</item><item ref="b">B</item></doc>
|
|
"""
|
|
let style = """
|
|
<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
|
|
<xsl:output method="xml" indent="no"/>
|
|
<xsl:template match="/">
|
|
<out><xsl:for-each select="id('b a c')"><xsl:value-of select="."/></xsl:for-each></out>
|
|
</xsl:template>
|
|
</xsl:stylesheet>
|
|
"""
|
|
let out = try PureXML.XSLT.transform(stylesheet: style, source: source)
|
|
// id() returns the referenced elements in document order regardless of the
|
|
// token order: C, A, B as they appear.
|
|
#expect(out.hasSuffix("<out>CAB</out>"))
|
|
}
|
|
}
|