sup_xml_core/xpath/exslt/
sets.rs

1//! EXSLT set family — https://exslt.org/set/
2//!
3//! All functions live in the `http://exslt.org/sets` namespace.
4//!
5//! Coverage:
6//!
7//! | Function          | Returns  | Semantics                                  |
8//! |-------------------|----------|--------------------------------------------|
9//! | `difference`      | nodeset  | nodes in A not in B (by node identity)     |
10//! | `intersection`    | nodeset  | nodes in both A and B (by node identity)   |
11//! | `distinct`        | nodeset  | one representative per distinct string-val |
12//! | `has-same-node`   | boolean  | non-empty intersection?                    |
13//! | `leading`         | nodeset  | nodes from A before first node also in B   |
14//! | `trailing`        | nodeset  | nodes from A after last node also in B     |
15//!
16//! Identity comparisons use `NodeId` equality, which is canonical
17//! in our index — two NodeIds refer to the same node iff they're
18//! equal.  This lets `difference` / `intersection` / `has-same-node`
19//! / `leading` / `trailing` be O(n+m) via `HashSet<NodeId>` instead
20//! of O(n*m) string-value comparison.  `distinct` is the one
21//! exception — per spec it dedups by string-value, not identity.
22
23use std::collections::HashSet;
24
25use crate::error::{ErrorDomain, ErrorLevel, XmlError};
26use crate::xpath::eval::Value;
27use crate::xpath::index::{DocIndexLike, NodeId};
28
29use super::Result;
30
31fn err(msg: impl Into<String>) -> XmlError {
32    XmlError::new(ErrorDomain::XPath, ErrorLevel::Error, msg)
33}
34
35pub fn dispatch<I: DocIndexLike>(
36    name: &str, args: Vec<Value>, idx: &I,
37) -> Option<Result<Value>> {
38    let r: Result<Value> = match name {
39        "difference"     => difference(&args),
40        "intersection"   => intersection(&args),
41        "distinct"       => distinct(&args, idx),
42        "has-same-node"  => has_same_node(&args),
43        "leading"        => leading(&args),
44        "trailing"       => trailing(&args),
45        _ => return None,
46    };
47    Some(r)
48}
49
50// ── helpers ───────────────────────────────────────────────────────
51
52fn two_nodesets<'a>(args: &'a [Value], name: &str) -> Result<(&'a [NodeId], &'a [NodeId])> {
53    if args.len() != 2 {
54        return Err(err(format!("set:{name} requires 2 nodeset arguments")));
55    }
56    let a = match &args[0] {
57        Value::NodeSet(ns) => ns.as_slice(),
58        _ => return Err(err(format!("set:{name} first arg must be a nodeset"))),
59    };
60    let b = match &args[1] {
61        Value::NodeSet(ns) => ns.as_slice(),
62        _ => return Err(err(format!("set:{name} second arg must be a nodeset"))),
63    };
64    Ok((a, b))
65}
66
67// ── difference ────────────────────────────────────────────────────
68
69fn difference(args: &[Value]) -> Result<Value> {
70    let (a, b) = two_nodesets(args, "difference")?;
71    let b_set: HashSet<NodeId> = b.iter().copied().collect();
72    let out: Vec<NodeId> = a.iter().copied().filter(|id| !b_set.contains(id)).collect();
73    Ok(Value::NodeSet(out))
74}
75
76// ── intersection ──────────────────────────────────────────────────
77
78fn intersection(args: &[Value]) -> Result<Value> {
79    let (a, b) = two_nodesets(args, "intersection")?;
80    let b_set: HashSet<NodeId> = b.iter().copied().collect();
81    let out: Vec<NodeId> = a.iter().copied().filter(|id| b_set.contains(id)).collect();
82    Ok(Value::NodeSet(out))
83}
84
85// ── has-same-node ─────────────────────────────────────────────────
86
87fn has_same_node(args: &[Value]) -> Result<Value> {
88    let (a, b) = two_nodesets(args, "has-same-node")?;
89    let b_set: HashSet<NodeId> = b.iter().copied().collect();
90    Ok(Value::Boolean(a.iter().any(|id| b_set.contains(id))))
91}
92
93// ── distinct ──────────────────────────────────────────────────────
94
95/// `set:distinct(nodeset)` — dedup by *string-value*, returning the
96/// first occurrence of each unique string in document order.  This
97/// is the one set function that doesn't use node identity.
98fn distinct<I: DocIndexLike>(args: &[Value], idx: &I) -> Result<Value> {
99    if args.len() != 1 {
100        return Err(err("set:distinct requires 1 nodeset argument"));
101    }
102    let ns = match &args[0] {
103        Value::NodeSet(ns) => ns,
104        _ => return Err(err("set:distinct requires a nodeset argument")),
105    };
106    let mut seen: HashSet<String> = HashSet::new();
107    let mut out: Vec<NodeId> = Vec::new();
108    for &id in ns {
109        let s = idx.string_value(id);
110        if seen.insert(s) {
111            out.push(id);
112        }
113    }
114    Ok(Value::NodeSet(out))
115}
116
117// ── leading / trailing ────────────────────────────────────────────
118
119/// `set:leading(A, B)` — nodes from `A` that appear before the
120/// first node in `A` that's also in `B`.  Per spec, "document
121/// order" is the ordering used to determine "before" — which
122/// matches `A`'s order (the engine returns nodesets in document
123/// order).
124fn leading(args: &[Value]) -> Result<Value> {
125    let (a, b) = two_nodesets(args, "leading")?;
126    let b_set: HashSet<NodeId> = b.iter().copied().collect();
127    let mut out: Vec<NodeId> = Vec::new();
128    for &id in a {
129        if b_set.contains(&id) { break; }
130        out.push(id);
131    }
132    Ok(Value::NodeSet(out))
133}
134
135/// `set:trailing(A, B)` — nodes from `A` that appear after the
136/// last node in `A` that's also in `B`.
137fn trailing(args: &[Value]) -> Result<Value> {
138    let (a, b) = two_nodesets(args, "trailing")?;
139    let b_set: HashSet<NodeId> = b.iter().copied().collect();
140    // Find the index of the last A-element that's in B; "trailing"
141    // is everything after that index.  If no overlap, "trailing"
142    // is empty (per libexslt's interpretation; the EXSLT spec is
143    // slightly ambiguous here but this matches what real
144    // stylesheets expect).
145    let mut cut = None;
146    for (i, &id) in a.iter().enumerate() {
147        if b_set.contains(&id) { cut = Some(i); }
148    }
149    let out: Vec<NodeId> = match cut {
150        Some(i) => a[i + 1..].to_vec(),
151        None    => Vec::new(),
152    };
153    Ok(Value::NodeSet(out))
154}
155
156#[cfg(test)]
157mod tests {
158    use super::*;
159    use crate::xpath::XPathContext;
160    use crate::{parse_str, ParseOptions};
161
162    fn ns(v: &Value) -> &[NodeId] {
163        if let Value::NodeSet(ns) = v { ns } else { panic!("expected nodeset, got {v:?}") }
164    }
165    fn b(v: &Value) -> bool {
166        if let Value::Boolean(b) = v { *b } else { panic!("expected boolean, got {v:?}") }
167    }
168
169    #[test]
170    fn difference_removes_overlap() {
171        let doc = parse_str("<r><a/><b/><c/><d/></r>", &ParseOptions::default()).unwrap();
172        let ctx = XPathContext::new(&doc);
173        let all = ctx.eval("/r/*").unwrap();          // a, b, c, d
174        let bd  = ctx.eval("/r/b | /r/d").unwrap();   // b, d
175        let r = dispatch("difference", vec![all, bd], &ctx.index).unwrap().unwrap();
176        // {a,b,c,d} − {b,d} = {a,c}
177        assert_eq!(ns(&r).len(), 2);
178    }
179
180    #[test]
181    fn intersection_keeps_overlap() {
182        let doc = parse_str("<r><a/><b/><c/><d/></r>", &ParseOptions::default()).unwrap();
183        let ctx = XPathContext::new(&doc);
184        let ac = ctx.eval("/r/a | /r/c").unwrap();
185        let bc = ctx.eval("/r/b | /r/c").unwrap();
186        let r = dispatch("intersection", vec![ac, bc], &ctx.index).unwrap().unwrap();
187        // {a,c} ∩ {b,c} = {c}
188        assert_eq!(ns(&r).len(), 1);
189    }
190
191    #[test]
192    fn has_same_node_detects_overlap() {
193        let doc = parse_str("<r><a/><b/><c/></r>", &ParseOptions::default()).unwrap();
194        let ctx = XPathContext::new(&doc);
195        let ab = ctx.eval("/r/a | /r/b").unwrap();
196        let bc = ctx.eval("/r/b | /r/c").unwrap();
197        assert!(b(&dispatch("has-same-node", vec![ab, bc], &ctx.index).unwrap().unwrap()));
198        let a = ctx.eval("/r/a").unwrap();
199        let c = ctx.eval("/r/c").unwrap();
200        assert!(!b(&dispatch("has-same-node", vec![a, c], &ctx.index).unwrap().unwrap()));
201    }
202
203    #[test]
204    fn distinct_dedups_by_string_value_not_identity() {
205        // Two <i> nodes with identical string-value: distinct should
206        // collapse them to one.
207        let doc = parse_str(
208            "<r><i>x</i><i>y</i><i>x</i><i>z</i></r>",
209            &ParseOptions::default(),
210        ).unwrap();
211        let ctx = XPathContext::new(&doc);
212        let all = ctx.eval("/r/i").unwrap();
213        let r = dispatch("distinct", vec![all], &ctx.index).unwrap().unwrap();
214        // 4 input nodes, 3 distinct string values → 3 output.
215        assert_eq!(ns(&r).len(), 3);
216    }
217
218    #[test]
219    fn leading_returns_prefix_before_first_overlap() {
220        let doc = parse_str("<r><a/><b/><c/><d/></r>", &ParseOptions::default()).unwrap();
221        let ctx = XPathContext::new(&doc);
222        let abcd = ctx.eval("/r/*").unwrap();
223        let c    = ctx.eval("/r/c").unwrap();
224        let r = dispatch("leading", vec![abcd, c], &ctx.index).unwrap().unwrap();
225        // {a,b,c,d}.leading({c}) → {a,b}
226        assert_eq!(ns(&r).len(), 2);
227    }
228
229    #[test]
230    fn trailing_returns_suffix_after_last_overlap() {
231        let doc = parse_str("<r><a/><b/><c/><d/></r>", &ParseOptions::default()).unwrap();
232        let ctx = XPathContext::new(&doc);
233        let abcd = ctx.eval("/r/*").unwrap();
234        let b_   = ctx.eval("/r/b").unwrap();
235        let r = dispatch("trailing", vec![abcd, b_], &ctx.index).unwrap().unwrap();
236        // {a,b,c,d}.trailing({b}) → {c,d}
237        assert_eq!(ns(&r).len(), 2);
238    }
239
240    #[test]
241    fn empty_inputs_are_handled() {
242        let doc = parse_str("<r><a/></r>", &ParseOptions::default()).unwrap();
243        let ctx = XPathContext::new(&doc);
244        let empty = Value::NodeSet(Vec::new());
245        let any   = ctx.eval("/r/a").unwrap();
246        // ∅ − A = ∅
247        assert_eq!(ns(&dispatch("difference",
248            vec![empty.clone(), any.clone()], &ctx.index).unwrap().unwrap()).len(), 0);
249        // A − ∅ = A
250        assert_eq!(ns(&dispatch("difference",
251            vec![any.clone(), empty.clone()], &ctx.index).unwrap().unwrap()).len(), 1);
252        // ∅ ∩ A = ∅
253        assert_eq!(ns(&dispatch("intersection",
254            vec![empty, any], &ctx.index).unwrap().unwrap()).len(), 0);
255    }
256
257    #[test]
258    fn unknown_function_returns_none() {
259        let doc = parse_str("<r/>", &ParseOptions::default()).unwrap();
260        let ctx = XPathContext::new(&doc);
261        assert!(dispatch("nonsense", vec![], &ctx.index).is_none());
262    }
263}
sup_xml_core/xpath/exslt/sets.rs

sup_xml_core/xpath/exslt/
sets.rs
