sup_xml_core/xpath/ast.rs
1/// XPath 1.0 abstract syntax tree.
2
3#[derive(Debug, Clone, Copy, PartialEq, Eq)]
4pub enum Axis {
5 Ancestor,
6 AncestorOrSelf,
7 Attribute,
8 Child,
9 Descendant,
10 DescendantOrSelf,
11 Following,
12 FollowingSibling,
13 Namespace,
14 Parent,
15 Preceding,
16 PrecedingSibling,
17 Self_,
18}
19
20impl Axis {
21 pub fn is_reverse(&self) -> bool {
22 matches!(
23 self,
24 Axis::Ancestor | Axis::AncestorOrSelf | Axis::Preceding | Axis::PrecedingSibling
25 )
26 }
27}
28
29#[derive(Debug, Clone, PartialEq)]
30pub enum NodeTest {
31 /// node() — any node on the axis
32 AnyNode,
33 /// text()
34 Text,
35 /// comment()
36 Comment,
37 /// processing-instruction() or processing-instruction('target')
38 PI(Option<String>),
39 /// document-node() — matches document nodes (XPath 2.0 §2.5.4).
40 /// Distinct from `AnyNode` so XSLT `match="document-node()"`
41 /// patterns don't accidentally cover element / text / etc.
42 ///
43 /// The optional inner test carries the element name test of a
44 /// `document-node(element(N))` / `document-node(element(*))` form
45 /// (XPath 2.0 §2.5.4.3): the node matches only when it is a
46 /// document node whose document element satisfies that test.
47 /// `None` is the bare `document-node()`.
48 Document(Option<Box<NodeTest>>),
49 /// * — any element/attribute
50 Wildcard,
51 /// prefix:* — any element/attribute in this namespace prefix
52 PrefixWildcard(String),
53 /// *:localname — any namespace, specific local name (XPath 2.0
54 /// §2.5.5.3 — `WildcardName ::= NCName ":" "*" | "*" ":" NCName`).
55 LocalNameOnly(String),
56 /// localname (no prefix)
57 LocalName(String),
58 /// prefix:localname
59 QName(String, String),
60 /// Unprefixed name that resolves through the XSLT 2.0
61 /// `xpath-default-namespace` attribute (XSLT 2.0 §5.1.1).
62 /// The XPath parser produces `LocalName`; the XSLT compiler
63 /// rewrites those into this variant when an ancestor of the
64 /// stylesheet element declares a non-empty default URI for
65 /// element name tests. Stored as expanded URI + local part so
66 /// runtime matching is a pair-compare without binding lookup.
67 DefaultNamespaceName { uri: String, local: String },
68}
69
70#[derive(Debug, Clone)]
71pub struct Step {
72 pub axis: Axis,
73 pub node_test: NodeTest,
74 pub predicates: Vec<Expr>,
75 /// XPath 2.0 `StepExpr ::= AxisStep | FilterExpr`. When
76 /// `Some`, the step is a FilterExpr (a primary expression
77 /// like a function call or parenthesised expression) that
78 /// produces its own sequence per input node — `axis` and
79 /// `node_test` are unused for the eval but kept at their
80 /// default (`Self_` / `AnyNode`) so existing code that
81 /// destructures `Step` directly still type-checks.
82 /// `path/key('x', 'y')` and `path/(expr)` parse into this
83 /// shape.
84 pub filter: Option<Box<Expr>>,
85}
86
87#[derive(Debug, Clone)]
88pub enum LocationPath {
89 Absolute(Vec<Step>),
90 Relative(Vec<Step>),
91}
92
93#[derive(Debug, Clone)]
94pub enum Expr {
95 Or(Box<Expr>, Box<Expr>),
96 And(Box<Expr>, Box<Expr>),
97 /// General comparison (`=`, `!=`, `<`, `>`, `<=`, `>=`) — existential
98 /// over the cartesian product of the two operand sequences
99 /// (XPath 2.0 §3.5.2).
100 Eq(Box<Expr>, Box<Expr>),
101 Ne(Box<Expr>, Box<Expr>),
102 Lt(Box<Expr>, Box<Expr>),
103 Gt(Box<Expr>, Box<Expr>),
104 Le(Box<Expr>, Box<Expr>),
105 Ge(Box<Expr>, Box<Expr>),
106 /// Value comparison (`eq`, `ne`, `lt`, `gt`, `le`, `ge`) — single-
107 /// item operands, returns the empty sequence when either side is
108 /// empty, raises a type error when either side has more than one
109 /// item (XPath 2.0 §3.5.1).
110 ValueEq(Box<Expr>, Box<Expr>),
111 ValueNe(Box<Expr>, Box<Expr>),
112 ValueLt(Box<Expr>, Box<Expr>),
113 ValueGt(Box<Expr>, Box<Expr>),
114 ValueLe(Box<Expr>, Box<Expr>),
115 ValueGe(Box<Expr>, Box<Expr>),
116 Add(Box<Expr>, Box<Expr>),
117 Sub(Box<Expr>, Box<Expr>),
118 Mul(Box<Expr>, Box<Expr>),
119 Div(Box<Expr>, Box<Expr>),
120 Mod(Box<Expr>, Box<Expr>),
121 Neg(Box<Expr>),
122 Union(Box<Expr>, Box<Expr>),
123 Path(LocationPath),
124 /// Primary expression with optional predicates and additional steps.
125 FilterPath {
126 primary: Box<Expr>,
127 predicates: Vec<Expr>,
128 steps: Vec<Step>,
129 },
130 FunctionCall(String, Vec<Expr>),
131 Variable(String),
132 Literal(String),
133 /// Integer literal — no `.` and no exponent (`42`), an `xs:integer`.
134 /// A literal too large for `i64` is lexed as a [`Expr::Decimal`].
135 Integer(i64),
136 /// Decimal literal — a `.` but no exponent (`3.14`), an `xs:decimal`.
137 /// Carries an exact [`rust_decimal::Decimal`] parsed from the
138 /// source lexical form (so `0.1` is 1/10 exactly, not the f64
139 /// nearest neighbour). Stringifies in decimal form, never
140 /// scientific.
141 Decimal(rust_decimal::Decimal),
142 /// Numeric literal with an exponent (`1.5e0`) — an `xs:double`.
143 /// In a 2.0 host this evaluates to a typed double so it takes the
144 /// F&O scientific string form.
145 Double(f64),
146 /// XPath 2.0 `if (cond) then a else b`. Both branches are
147 /// `ExprSingle` — already parsed as full expressions.
148 IfThenElse {
149 cond: Box<Expr>,
150 then_branch: Box<Expr>,
151 else_branch: Box<Expr>,
152 },
153 /// XPath 2.0 `for $v in seq return body`, with chained bindings
154 /// (`for $a in A, $b in B return ...`) flattened into the
155 /// `bindings` list in source order.
156 For {
157 bindings: Vec<(String, Expr)>,
158 body: Box<Expr>,
159 },
160 /// XPath 3.0 `let $v := expr return body`, with chained bindings
161 /// (`let $a := A, $b := B return ...`) flattened into the
162 /// `bindings` list in source order. Each binding is evaluated
163 /// once and is visible to later bindings and the body.
164 Let {
165 bindings: Vec<(String, Expr)>,
166 body: Box<Expr>,
167 },
168 /// XPath 2.0 range `m to n` — yields the integer sequence m, m+1,
169 /// …, n (inclusive). Empty when m > n. Atomic non-integer
170 /// operands round to integers before the range materialises.
171 Range(Box<Expr>, Box<Expr>),
172 /// XPath 3.0 simple-map operator `E1 ! E2` — evaluates `E2` with
173 /// each item of `E1` as the context item; concatenates results
174 /// in iteration order (no document-order sort). Distinct from
175 /// `/` in that the right-hand side need not be a node-step:
176 /// `(1, 2, 3) ! (. * 2)` yields (2, 4, 6).
177 SimpleMap(Box<Expr>, Box<Expr>),
178 /// XPath 2.0 node-comparison `$a << $b` — true iff `$a`
179 /// precedes `$b` in document order. Empty operands yield
180 /// the empty sequence.
181 NodeBefore(Box<Expr>, Box<Expr>),
182 /// XPath 2.0 node-comparison `$a >> $b` — node-after.
183 NodeAfter(Box<Expr>, Box<Expr>),
184 /// XPath 2.0 node-comparison `$a is $b` — true iff both operands
185 /// are the same node. Each operand must atomise to at most one
186 /// node; an empty operand yields the empty sequence (§3.5.3).
187 NodeIs(Box<Expr>, Box<Expr>),
188 /// XPath 2.0 parenthesised sequence literal `(a, b, c)` — at least
189 /// two elements (a singleton is just a parenthesised expression).
190 /// Evaluation concatenates each item; atomics become synthetic
191 /// text nodes so the result is uniformly a NodeSet.
192 Sequence(Vec<Expr>),
193 /// XPath 2.0 quantified expression `some $v in seq satisfies test`
194 /// / `every $v in seq satisfies test`. Boolean result: any /
195 /// all items of the sequence satisfy the predicate.
196 Quantified {
197 kind: QuantifierKind,
198 bindings: Vec<(String, Expr)>,
199 test: Box<Expr>,
200 },
201 /// XPath 2.0 `lhs idiv rhs` — integer quotient with truncation
202 /// towards zero (XPath 2.0 § 3.4). Distinct from `div`, which
203 /// always produces a float.
204 IDiv(Box<Expr>, Box<Expr>),
205 /// XPath 2.0 `lhs intersect rhs` — node-set intersection in
206 /// document order.
207 Intersect(Box<Expr>, Box<Expr>),
208 /// XPath 2.0 `lhs except rhs` — nodes in `lhs` not present in
209 /// `rhs`, document order preserved.
210 Except(Box<Expr>, Box<Expr>),
211 /// XPath 2.0 `expr instance of SequenceType` — boolean predicate.
212 InstanceOf(Box<Expr>, SequenceType),
213 /// XPath 2.0 `expr cast as SingleType` — value conversion;
214 /// raises a runtime error when the source value can't be cast.
215 CastAs(Box<Expr>, SingleType),
216 /// XPath 3.1 `try { TryExpr } catch <NameTest>* { CatchExpr } …`
217 /// — evaluate `body`; on dynamic error, walk catches and
218 /// evaluate the first whose name-tests match the caught
219 /// error's QName. Inside the catch handler, `$err:code` /
220 /// `$err:description` / etc. are bound to the error's
221 /// metadata.
222 TryCatch {
223 body: Box<Expr>,
224 catches: Vec<XPathCatch>,
225 },
226 /// XPath 2.0 `expr castable as SingleType` — boolean predicate
227 /// for "can this value cast without error".
228 CastableAs(Box<Expr>, SingleType),
229 /// XPath 2.0 `expr treat as SequenceType` — assertion that the
230 /// runtime value already conforms; raises an error otherwise.
231 TreatAs(Box<Expr>, SequenceType),
232 /// Synthetic — not produced by the XPath parser. The XSLT
233 /// compiler wraps each top-level expression whose static context
234 /// declares a non-codepoint `[xsl:]default-collation` so the
235 /// runtime can install that URI on a thread-local before
236 /// evaluating `inner`. Value-comparison operators (`eq`, `ne`,
237 /// `lt`, …) consult that thread-local when both operands are
238 /// strings/untyped — XPath 2.0 §3.5.2 says they use the static
239 /// default collation in that case.
240 WithDefaultCollation(String, Box<Expr>),
241 /// Synthetic — not produced by the XPath parser. The XSLT
242 /// compiler wraps each top-level expression that sits in an
243 /// XPath-1.0 backwards-compatibility scope (a `[xsl:]version="1.0"`
244 /// ancestor inside a 2.0 stylesheet, XSLT 2.0 §3.8). The runtime
245 /// installs a thread-local flag before evaluating `inner` so the
246 /// XPath-1.0-compat conversion rules (XPath 2.0 §B.1) apply:
247 /// arithmetic operands are atomised to xs:double, and `to`-range
248 /// bounds use the first item of a sequence.
249 BackwardsCompat(Box<Expr>),
250 /// XPath 3.1 §3.11.1 map constructor `map { k1: v1, k2: v2, … }`.
251 /// Each entry is `(key-expr, value-expr)`; keys evaluate to a
252 /// single atomic value, values to an arbitrary sequence.
253 MapConstructor(Vec<(Expr, Expr)>),
254 /// XPath 3.1 §3.11.2 array constructors — `[ a, b, c ]` (square:
255 /// one member per comma-separated expression) or `array { … }`
256 /// (curly: one member per item of the contained sequence).
257 ArrayConstructor { members: Vec<Expr>, square: bool },
258 /// XPath 3.1 §3.11.3 postfix lookup `E ? K` — indexes into the map
259 /// or array produced by `E`.
260 Lookup(Box<Expr>, LookupKey),
261 /// XPath 3.1 unary lookup `? K` — indexes into the context item.
262 UnaryLookup(LookupKey),
263 /// XPath 3.1 §3.12 inline function `function($p, …) { body }`.
264 /// Parameter types and the return type are accepted but not
265 /// enforced; only the parameter names matter for binding.
266 InlineFunction {
267 params: Vec<String>,
268 /// Declared signature (parameter and return types, `item()*` where
269 /// omitted) — used for function subtyping in `instance of`.
270 sig: Box<FunctionSig>,
271 body: Box<Expr>,
272 },
273 /// XPath 3.0 §3.1.4 context-item expression `.` used as a primary —
274 /// yields the current context item (which may be a non-node such as a
275 /// function item). Distinct from a `self::node()` step: produced only
276 /// where `.` carries a postfix (`.(args)`, `.?key`), so the context
277 /// item's actual value, not its node projection, drives the postfix.
278 ContextItem,
279 /// XPath 3.1 §3.1.6 named function reference `name#arity`.
280 NamedFunctionRef { name: String, arity: usize },
281 /// XPath 3.1 §3.2.2 dynamic function call `F(args)` where `F` is
282 /// an expression yielding a function item. The `?` placeholder
283 /// (partial application) appears as [`Expr::Placeholder`] in args.
284 DynamicCall { func: Box<Expr>, args: Vec<Expr> },
285 /// XPath 3.1 partial-application argument placeholder (`?`).
286 Placeholder,
287}
288
289/// The key selector of an XPath 3.1 lookup expression (`?K`).
290#[derive(Debug, Clone)]
291pub enum LookupKey {
292 /// `?*` — all values of the map / all members of the array.
293 Wildcard,
294 /// `?name` — the entry whose key is the string `name`.
295 Name(String),
296 /// `?123` — integer key (map) or 1-based position (array).
297 Integer(i64),
298 /// `?(expr)` — the key(s) computed by the parenthesised expression.
299 Expr(Box<Expr>),
300}
301
302/// XPath 2.0 SequenceType — limited to what we recognise. Anything
303/// outside `xs:string` / `xs:integer` / `xs:decimal` / `xs:double`
304/// / `xs:boolean` / `xs:date` / `xs:dateTime` / `xs:time` /
305/// `xs:anyAtomicType` / `xs:anyURI` (atomic) or `item()` / `node()`
306/// / `element()` / `attribute()` / `text()` / `comment()` /
307/// `processing-instruction()` / `document-node()` (kind) is parsed
308/// but flagged as unsupported at eval time.
309#[derive(Debug, Clone, PartialEq)]
310pub struct SequenceType {
311 pub item: ItemType,
312 pub occurrence: Occurrence,
313}
314
315/// The signature of a specific function test `function(T1, …, Tn) as R`
316/// (XPath 3.1 §2.5.4.3). Drives the function-subtyping rules applied by
317/// `instance of` / `treat as`: the parameter types are contravariant and
318/// the return type is covariant.
319#[derive(Debug, Clone, PartialEq)]
320pub struct FunctionSig {
321 pub params: Vec<SequenceType>,
322 pub ret: SequenceType,
323}
324
325/// `SingleType` — a `SequenceType` with implicit `?` (one or zero).
326/// Used in `cast as` / `castable as`.
327pub type SingleType = SequenceType;
328
329#[derive(Debug, Clone, PartialEq)]
330pub enum ItemType {
331 /// `item()` — any item.
332 Any,
333 /// `xs:foo` atomic type test. Stored verbatim as the local name
334 /// (with `xs:` stripped); eval uses the name to pick a string-to-
335 /// value coercion.
336 Atomic(String),
337 /// `node()` — any node.
338 AnyNode,
339 /// Specific kind tests with optional name. Name is `None` for
340 /// the bare-paren form (e.g. `element()`); `Some` for
341 /// `element(foo)`.
342 Element(Option<String>),
343 Attribute(Option<String>),
344 Text,
345 Comment,
346 PI(Option<String>),
347 Document,
348 /// Function test (XPath 3.1 §2.5.4.3). `None` is `function(*)` (any
349 /// function item); `Some` carries a specific `function(T1, …, Tn) as R`
350 /// signature, matched by function subtyping.
351 Function(Option<Box<FunctionSig>>),
352 /// Map test (XPath 3.1 §2.5.4.4) — `map(*)` or `map(K, V)`. Matched as
353 /// "any map"; the key/value types are parsed but not modelled.
354 Map,
355 /// Array test (XPath 3.1 §2.5.4.5) — `array(*)` or `array(T)`. Matched
356 /// as "any array"; the member type is parsed but not modelled.
357 Array,
358 /// `empty-sequence()` — matches only the empty sequence. As an
359 /// item test it matches no individual item; the empty case is
360 /// admitted by the cardinality check alone.
361 EmptySequence,
362}
363
364/// Occurrence indicator (XPath 2.0 § 2.5.3) attached to a SequenceType.
365#[derive(Debug, Clone, Copy, PartialEq, Eq)]
366pub enum Occurrence {
367 /// Exactly one (default — no indicator).
368 One,
369 /// `?` — zero or one.
370 Optional,
371 /// `+` — one or more.
372 OneOrMore,
373 /// `*` — zero or more.
374 ZeroOrMore,
375}
376
377/// Distinguishes `some` (∃) from `every` (∀) quantified expressions.
378#[derive(Debug, Clone, Copy, PartialEq, Eq)]
379pub enum QuantifierKind { Some, Every }
380
381/// One catch clause of an [`Expr::TryCatch`]. The grammar is
382/// `"catch" NameTest ("|" NameTest)* "{" Expr "}"`, with `"*"`
383/// allowed as a catch-all in place of a specific QName.
384#[derive(Debug, Clone)]
385pub struct XPathCatch {
386 /// QName matchers from the `catch` clause's name list. An
387 /// empty list (or a single `Any`) is catch-all.
388 pub matchers: Vec<CatchNameTest>,
389 /// Body expression to evaluate when this clause matches.
390 pub body: Expr,
391}
392
393/// One name-test in an XPath try/catch `catch` clause name list.
394#[derive(Debug, Clone)]
395pub enum CatchNameTest {
396 /// `*` — any error matches.
397 Any,
398 /// `*:NCName` — matches any-namespace, specific local name.
399 LocalNameOnly(String),
400 /// `prefix:*` — namespace wildcard.
401 PrefixWildcard(String),
402 /// `prefix:local` / `local` — fully-qualified.
403 QName { prefix: Option<String>, local: String },
404}
405
406/// Maximum depth of predicates-within-predicates anywhere in `expr`.
407///
408/// A single `Step` carrying `[p]` predicates is depth 1; if `p` itself
409/// contains a `Path` whose steps carry their own `[q]` predicates,
410/// that's depth 2; and so on. This is the *semantic* nesting that
411/// drives the evaluator's N^k blow-up — distinct from the parser's
412/// grammar-production recursion depth (which the parser already bounds
413/// with `MAX_PARSE_DEPTH`).
414///
415/// Used to reject pathological inputs like
416/// `//*[//*[//*[//*[//*[.='x']]]]]` at parse time, before the
417/// evaluator's step budget burns ~500k charges to reach the same
418/// conclusion at much higher latency.
419pub fn max_predicate_nesting(expr: &Expr) -> u32 {
420 fn expr_depth(e: &Expr) -> u32 {
421 match e {
422 Expr::Or(a, b) | Expr::And(a, b)
423 | Expr::Eq(a, b) | Expr::Ne(a, b)
424 | Expr::Lt(a, b) | Expr::Gt(a, b) | Expr::Le(a, b) | Expr::Ge(a, b)
425 | Expr::ValueEq(a, b) | Expr::ValueNe(a, b)
426 | Expr::ValueLt(a, b) | Expr::ValueGt(a, b)
427 | Expr::ValueLe(a, b) | Expr::ValueGe(a, b)
428 | Expr::Add(a, b) | Expr::Sub(a, b)
429 | Expr::Mul(a, b) | Expr::Div(a, b) | Expr::Mod(a, b)
430 | Expr::Union(a, b)
431 | Expr::NodeBefore(a, b) | Expr::NodeAfter(a, b) | Expr::NodeIs(a, b) => expr_depth(a).max(expr_depth(b)),
432 Expr::Neg(a) => expr_depth(a),
433 Expr::Path(p) => path_depth(p),
434 Expr::FilterPath { primary, predicates, steps } => {
435 let primary_d = expr_depth(primary);
436 let pred_d = predicates.iter()
437 .map(|p| 1 + expr_depth(p))
438 .max()
439 .unwrap_or(0);
440 let step_d = steps.iter().map(step_depth).max().unwrap_or(0);
441 primary_d.max(pred_d).max(step_d)
442 }
443 Expr::FunctionCall(_, args) =>
444 args.iter().map(expr_depth).max().unwrap_or(0),
445 Expr::Variable(_) | Expr::Literal(_)
446 | Expr::Integer(_) | Expr::Decimal(_) | Expr::Double(_) => 0,
447 Expr::IfThenElse { cond, then_branch, else_branch } =>
448 expr_depth(cond)
449 .max(expr_depth(then_branch))
450 .max(expr_depth(else_branch)),
451 Expr::For { bindings, body } | Expr::Let { bindings, body } => {
452 let body_d = expr_depth(body);
453 bindings.iter().map(|(_, e)| expr_depth(e)).max().unwrap_or(0).max(body_d)
454 }
455 Expr::Range(a, b) => expr_depth(a).max(expr_depth(b)),
456 Expr::SimpleMap(a, b) => expr_depth(a).max(expr_depth(b)),
457 Expr::Sequence(items) =>
458 items.iter().map(expr_depth).max().unwrap_or(0),
459 Expr::Quantified { bindings, test, .. } => {
460 let t = expr_depth(test);
461 bindings.iter().map(|(_, e)| expr_depth(e)).max().unwrap_or(0).max(t)
462 }
463 Expr::IDiv(a, b) | Expr::Intersect(a, b) | Expr::Except(a, b)
464 => expr_depth(a).max(expr_depth(b)),
465 Expr::InstanceOf(a, _) | Expr::CastAs(a, _) | Expr::CastableAs(a, _)
466 | Expr::TreatAs(a, _) => expr_depth(a),
467 Expr::TryCatch { body, catches } => {
468 let b = expr_depth(body);
469 catches.iter().map(|c| expr_depth(&c.body)).max().unwrap_or(0).max(b)
470 }
471 Expr::WithDefaultCollation(_, inner) => expr_depth(inner),
472 Expr::BackwardsCompat(inner) => expr_depth(inner),
473 Expr::MapConstructor(entries) => entries.iter()
474 .map(|(k, v)| expr_depth(k).max(expr_depth(v))).max().unwrap_or(0),
475 Expr::ArrayConstructor { members, .. } =>
476 members.iter().map(expr_depth).max().unwrap_or(0),
477 Expr::Lookup(base, key) => expr_depth(base).max(lookup_key_depth(key)),
478 Expr::UnaryLookup(key) => lookup_key_depth(key),
479 Expr::InlineFunction { body, .. } => expr_depth(body),
480 Expr::NamedFunctionRef { .. } | Expr::Placeholder | Expr::ContextItem => 0,
481 Expr::DynamicCall { func, args } => expr_depth(func)
482 .max(args.iter().map(expr_depth).max().unwrap_or(0)),
483 }
484 }
485 fn lookup_key_depth(k: &LookupKey) -> u32 {
486 match k {
487 LookupKey::Expr(e) => expr_depth(e),
488 _ => 0,
489 }
490 }
491 fn step_depth(s: &Step) -> u32 {
492 s.predicates.iter()
493 .map(|p| 1 + expr_depth(p))
494 .max()
495 .unwrap_or(0)
496 }
497 fn path_depth(p: &LocationPath) -> u32 {
498 let steps = match p {
499 LocationPath::Absolute(s) | LocationPath::Relative(s) => s,
500 };
501 steps.iter().map(step_depth).max().unwrap_or(0)
502 }
503 expr_depth(expr)
504}