PureXML/Sources/XSLT/XSLTRuntime.swift
Mihaela Mihaljevic dc6727538d
perf(xslt): make the template evaluator iterative (#358)
The XSLT engine was mutually recursive on template-application and result-tree
nesting (instantiate, evaluate, applyTemplates), so a recursive named template
whose depth comes from source data could overflow the native stack (SIGBUS) on
attacker-controllable input, and an identity transform of a deep source
overflowed on a small (Swift-concurrency Task) stack.

The engine is now an explicit work-stack driver (XSLTDriver). Each instruction
appends its produced items to a sink or pushes sub-work, with the rest of the
body pushed first so result-tree document order is preserved; template
application, the built-in rule's source descent, and result-element nesting all
run on the heap. Only stylesheet-bounded helper evaluation (a variable's or
parameter's result-tree fragment, an attribute set, an xsl:message body)
re-enters through a nested driver call, whose native depth is bounded by the
stylesheet's own nesting.

The result-tree serialization walks the engine now exposes at depth were made
iterative too: XSLTNamespaceFixup (an explicit pre-order visit that keeps the
ns0/ns1 counter in document order), the text and string-value extractions
(iterative accumulators), and the content-type-meta and CDATA-section rewrites
(the shared Node.rebuildingBottomUp spine).

Deep recursion now succeeds on any stack: a 5000-level recursive template builds
and serializes on the test Task stack. maxTemplateDepth is retained as runaway
protection (an unbounded result tree would exhaust memory), defaulting to 40000
and throwing XSLTError.recursionLimitExceeded only past that.

Behavior is otherwise unchanged: the full Apache Xalan XSLT 1.0 conformance
corpus (1086 cases) and the in-repo XSLT/XPath suites pass identically; one
previously-failing Xalan case (mdocs07) now passes and was de-baselined. Full
suite green. Closes #356.
2026-06-27 19:29:51 +02:00

88 lines
3.8 KiB
Swift

extension PureXML.XSLT {
/// The default ceiling on logical template-application nesting (see
/// ``RecursionGuard``). The evaluator is iterative, so this is no longer a
/// stack limit but a runaway guard: legitimate deep recursion (well into the
/// thousands) succeeds, while an infinite or unbounded recursion, whose result
/// tree would grow without bound, fails gracefully once it passes this depth.
/// Configurable per transform.
public static let defaultMaxTemplateDepth = 40000
/// One produced item: a node for the result tree, or an attribute to attach to
/// the enclosing element.
enum ResultItem {
case node(PureXML.Model.Node)
case attribute(PureXML.Model.Attribute)
}
/// The evaluation context during instantiation.
struct XSLTContext {
var node: PureXML.Model.TreeNode
/// The current node when it is not a tree node (an attribute or
/// namespace node); `node` then holds its owner element.
var current: PureXML.XPath.Node?
var position: Int
var size: Int
var variables: [String: PureXML.XPath.Value]
/// The XPath context node: `current` when set, else the tree node.
var focus: PureXML.XPath.Node {
current ?? .tree(node)
}
/// The mode of the template currently being instantiated, so `apply-imports`
/// re-applies in the same mode.
var mode: String?
/// The import precedence of the template currently being instantiated, so
/// `apply-imports` considers only templates below it. `.max` outside a template.
var importPrecedence: Int
/// The floor of the current template's stylesheet's import subtree;
/// apply-imports searches [importRangeLow, importPrecedence).
var importRangeLow: Int = 0
/// The stylesheet xmlns bindings of the template being instantiated,
/// so prefixed names in its expressions resolve by URI.
var namespaces: [String: String] = [:]
/// The base URI of the stylesheet element currently being instantiated
/// (its template's or global variable's source file), against which a
/// relative string-form `document()` reference resolves (XSLT 1.0 12.1).
var baseURI: String = ""
init(
node: PureXML.Model.TreeNode,
current: PureXML.XPath.Node? = nil,
position: Int,
size: Int,
variables: [String: PureXML.XPath.Value],
mode: String? = nil,
importPrecedence: Int = .max,
baseURI: String = "",
) {
self.node = node
self.current = current
self.position = position
self.size = size
self.variables = variables
self.mode = mode
self.importPrecedence = importPrecedence
self.baseURI = baseURI
}
}
/// Shared, mutable signal that an `xsl:message terminate="yes"` fired, carrying
/// its text. A reference type so the value-semantics transformer can set it.
final class Termination {
var message: String?
}
/// Shared, mutable latch for runaway template recursion. The evaluator is
/// iterative, so deep recursion no longer overflows the stack; this instead
/// caps the *logical* template-application depth (carried on each work item)
/// so an unbounded or infinite recursion, whose result tree would grow without
/// bound, fails gracefully rather than exhausting memory. `exceeded` latches
/// once the depth passes `maxTemplateDepth`, so the work stack drains and the
/// transform throws. A reference type so the value-semantics transformer can
/// set it.
final class RecursionGuard {
var exceeded = false
}
}