sup_xml_core/xpath/
rtf.rs

1//! XSLT result-tree-fragment storage for XPath navigation.
2//!
3//! When XSLT 2.0 binds a body-form `xsl:variable`, the spec models
4//! the variable's value as a temporary document tree.  XPath
5//! expressions like `$rtf/foo` need to navigate into that tree just
6//! like a source document — children, attributes, predicates, the
7//! works.
8//!
9//! Our [`super::context::DocIndex`] is built once from the source
10//! and held as `&DocIndex` everywhere afterward, so RTFs can't be
11//! grafted into its primary node table mid-evaluation.  Instead
12//! each RTF is built complete-then-frozen as an [`RtfIndex`]
13//! (owned-string copies of element / attribute / text content) and
14//! pushed into a [`elsa::FrozenVec`] hosted by `DocIndex`.  The
15//! FrozenVec lets us append via shared `&self` while every
16//! `&RtfIndex` we hand out keeps its heap address stable for the
17//! lifetime of the surrounding evaluation — so the
18//! [`DocIndexLike`](super::index::DocIndexLike) accessors on
19//! `DocIndex` can route to the right RTF and return `&[NodeId]`
20//! slices directly from its internal table.
21//!
22//! ## NodeId encoding
23//!
24//! RTF node-ids carry a marker bit so the dispatch is a single
25//! mask test on every accessor.  The layout (on 64-bit `usize`):
26//!
27//! ```text
28//!  63        62      32             0
29//!   ┌────────┬───────┬───────────────┐
30//!   │ synth  │  RTF  │   rtf-index   │   ← bits 32..62 = which RTF
31//!   ├────────┴───────┴───────────────┤
32//!   │           local node id        │   ← bits 0..32   = node within
33//!   └────────────────────────────────┘
34//! ```
35//!
36//! `synth` is the existing EXSLT synthetic-text marker (bit 63);
37//! `RTF` is bit 62.  The two are mutually exclusive: an id is
38//! either synthetic-text, an RTF node, or a real source-tree node.
39
40use std::ops::Range;
41
42use super::index::XPathNodeKind;
43use super::NodeId;
44
45/// Bit 62 — set on every [`NodeId`] that addresses a node in an
46/// [`RtfIndex`].  Mutually exclusive with the synthetic-text
47/// marker (bit 63) so a single mask test on each accessor
48/// dispatches the three storage regions.
49pub const RTF_BASE: NodeId = 1_usize << (usize::BITS - 2);
50
51/// Number of low bits reserved for the per-RTF local node id.
52/// 32 bits is enough for 4-billion nodes inside a single RTF —
53/// orders of magnitude more than any real XSLT temporary tree.
54const RTF_LOCAL_BITS:  u32   = 32;
55const RTF_LOCAL_MASK:  NodeId = (1_usize << RTF_LOCAL_BITS) - 1;
56/// Bits 32..62 carry the RTF's index in the host
57/// [`super::context::DocIndex::rtfs`] vector — 30 bits, room for
58/// a billion RTFs per transformation.
59const RTF_INDEX_MASK:  NodeId = !(RTF_BASE | super::context::SYNTHETIC_TEXT_BASE | RTF_LOCAL_MASK);
60
61/// True iff `id` addresses an [`RtfIndex`] node (bit 62 set).
62#[inline(always)]
63pub fn is_rtf_id(id: NodeId) -> bool {
64    id & RTF_BASE != 0 && id & super::context::SYNTHETIC_TEXT_BASE == 0
65}
66
67/// Decompose an RTF node-id into `(host-vector index, local id)`.
68#[inline(always)]
69pub fn decode_rtf_id(id: NodeId) -> (usize, NodeId) {
70    let local = id & RTF_LOCAL_MASK;
71    let rtf_i = (id & RTF_INDEX_MASK) >> RTF_LOCAL_BITS;
72    (rtf_i, local)
73}
74
75/// Compose an RTF node-id from its host-vector index and the
76/// per-RTF local id.  Panics in debug mode when either component
77/// exceeds its bit budget.
78#[inline(always)]
79pub fn encode_rtf_id(rtf_i: usize, local: NodeId) -> NodeId {
80    debug_assert!(local <= RTF_LOCAL_MASK,
81        "RTF local id {local} exceeds 32-bit budget");
82    debug_assert!(rtf_i <= (RTF_INDEX_MASK >> RTF_LOCAL_BITS),
83        "RTF index {rtf_i} exceeds 30-bit budget");
84    RTF_BASE | (rtf_i << RTF_LOCAL_BITS) | local
85}
86
87// ── per-RTF node table ─────────────────────────────────────────────
88
89/// One node inside an [`RtfIndex`].  Strings are owned (boxed) so
90/// the index can stand alone after the source [`crate::xpath::eval`]
91/// result-tree fragment has been built — XSLT bind_variable
92/// constructs the index then drops the intermediate.
93///
94/// All NodeId fields (`parent`, `children`, attribute /
95/// namespace ranges) are stored **already encoded with the RTF
96/// marker bits** (via [`encode_rtf_id`]), so accessor methods
97/// can hand out `&[NodeId]` slices directly.  This costs the
98/// builder one bit-shift per id at construction time and saves
99/// the evaluator a per-access Vec allocation.
100#[derive(Debug)]
101pub struct RtfNode {
102    pub kind:     RtfNodeKind,
103    pub parent:   Option<NodeId>,
104    pub children: Vec<NodeId>,
105    pub attr_start: NodeId,
106    pub attr_end:   NodeId,
107    pub ns_start:   NodeId,
108    pub ns_end:     NodeId,
109}
110
111#[derive(Debug)]
112pub enum RtfNodeKind {
113    Document,
114    Element {
115        name: Box<str>,
116        local_name: Box<str>,
117        prefix: Option<Box<str>>,
118        namespace_uri: Box<str>,
119    },
120    Attribute {
121        name: Box<str>,
122        local_name: Box<str>,
123        prefix: Option<Box<str>>,
124        namespace_uri: Box<str>,
125        value: Box<str>,
126    },
127    Text(Box<str>),
128    Comment(Box<str>),
129    PI { target: Box<str>, data: Box<str> },
130    Namespace { prefix: Option<Box<str>>, uri: Box<str> },
131}
132
133/// One result-tree fragment indexed for XPath navigation.  Built
134/// complete-then-frozen — once a `RtfIndex` is pushed into the
135/// host [`elsa::FrozenVec`], its `nodes` table never mutates.
136#[derive(Debug)]
137pub struct RtfIndex {
138    /// LOCAL ids — node 0 is the synthetic Document node, the
139    /// rest are its descendants in document order.  Callers
140    /// outside this module always see the IDs encoded with the
141    /// `RTF_BASE` marker (via [`encode_rtf_id`]); the local Vec
142    /// is the implementation detail.
143    pub nodes: Vec<RtfNode>,
144    /// Self-index inside the host `DocIndex::rtfs` vector,
145    /// captured at registration time so accessors can re-encode
146    /// child / parent ids back to the marker form callers expect.
147    pub host_index: usize,
148}
149
150impl RtfIndex {
151    /// Children of `local_id` — already-encoded global ids so the
152    /// outer dispatcher can return the slice directly.
153    pub fn children(&self, local_id: NodeId) -> &[NodeId] {
154        &self.nodes[local_id].children
155    }
156
157    /// Parent of `local_id`, globally encoded.  Returns `None` for
158    /// the document root (LOCAL id 0).
159    pub fn parent(&self, local_id: NodeId) -> Option<NodeId> {
160        self.nodes[local_id].parent
161    }
162
163    pub fn attr_range(&self, local_id: NodeId) -> Range<NodeId> {
164        let n = &self.nodes[local_id];
165        n.attr_start..n.attr_end
166    }
167
168    pub fn ns_range(&self, local_id: NodeId) -> Range<NodeId> {
169        let n = &self.nodes[local_id];
170        n.ns_start..n.ns_end
171    }
172
173    pub fn kind(&self, local_id: NodeId) -> XPathNodeKind {
174        match self.nodes[local_id].kind {
175            RtfNodeKind::Document      => XPathNodeKind::Document,
176            RtfNodeKind::Element { .. } => XPathNodeKind::Element,
177            RtfNodeKind::Attribute { .. } => XPathNodeKind::Attribute,
178            RtfNodeKind::Text(_)       => XPathNodeKind::Text,
179            RtfNodeKind::Comment(_)    => XPathNodeKind::Comment,
180            RtfNodeKind::PI { .. }     => XPathNodeKind::PI,
181            RtfNodeKind::Namespace { .. } => XPathNodeKind::Namespace,
182        }
183    }
184
185    pub fn pi_target(&self, local_id: NodeId) -> &str {
186        match &self.nodes[local_id].kind {
187            RtfNodeKind::PI { target, .. } => target,
188            _ => "",
189        }
190    }
191
192    pub fn node_name(&self, local_id: NodeId) -> &str {
193        match &self.nodes[local_id].kind {
194            RtfNodeKind::Element { name, .. }
195                | RtfNodeKind::Attribute { name, .. } => name,
196            RtfNodeKind::PI { target, .. } => target,
197            // XPath 2.0 §2.5.4 — a namespace node's "node name" is
198            // its prefix (or the empty string for the default
199            // namespace binding).
200            RtfNodeKind::Namespace { prefix, .. } =>
201                prefix.as_deref().unwrap_or(""),
202            _ => "",
203        }
204    }
205
206    pub fn local_name(&self, local_id: NodeId) -> &str {
207        match &self.nodes[local_id].kind {
208            RtfNodeKind::Element { local_name, .. }
209                | RtfNodeKind::Attribute { local_name, .. } => local_name,
210            RtfNodeKind::PI { target, .. } => target,
211            RtfNodeKind::Namespace { prefix, .. } =>
212                prefix.as_deref().unwrap_or(""),
213            _ => "",
214        }
215    }
216
217    pub fn namespace_uri(&self, local_id: NodeId) -> &str {
218        match &self.nodes[local_id].kind {
219            RtfNodeKind::Element { namespace_uri, .. }
220                | RtfNodeKind::Attribute { namespace_uri, .. } => namespace_uri,
221            _ => "",
222        }
223    }
224
225    pub fn namespace_prefix(&self, local_id: NodeId) -> Option<&str> {
226        match &self.nodes[local_id].kind {
227            RtfNodeKind::Element { prefix, .. }
228                | RtfNodeKind::Attribute { prefix, .. } => prefix.as_deref(),
229            _ => None,
230        }
231    }
232
233    /// Recursive descendant text concatenation — XPath 1.0 §5
234    /// string-value semantics for element / document nodes.
235    /// Atomic kinds return their stored content directly.
236    pub fn string_value(&self, local_id: NodeId) -> String {
237        match &self.nodes[local_id].kind {
238            RtfNodeKind::Text(s)    => s.to_string(),
239            RtfNodeKind::Comment(s) => s.to_string(),
240            RtfNodeKind::PI { data, .. } => data.to_string(),
241            RtfNodeKind::Attribute { value, .. } => value.to_string(),
242            RtfNodeKind::Namespace { uri, .. } => uri.to_string(),
243            RtfNodeKind::Element { .. } | RtfNodeKind::Document => {
244                let mut out = String::new();
245                self.append_text(local_id, &mut out);
246                out
247            }
248        }
249    }
250
251    fn append_text(&self, local_id: NodeId, out: &mut String) {
252        // Children are stored already-encoded (global ids).
253        // string_value's recursion stays within one RTF, so we
254        // strip the marker bits back to the local index for
255        // each child.
256        for &child in &self.nodes[local_id].children {
257            let child_local = child & RTF_LOCAL_MASK;
258            match &self.nodes[child_local].kind {
259                RtfNodeKind::Text(s) => out.push_str(s),
260                RtfNodeKind::Element { .. } | RtfNodeKind::Document =>
261                    self.append_text(child_local, out),
262                _ => {}
263            }
264        }
265    }
266}
267
268
269// ── builder ────────────────────────────────────────────────────────
270
271/// Helper for populating an [`RtfIndex`] one node at a time.  The
272/// builder owns the slot index it'll be pushed into so it can
273/// encode child / parent / attribute ids directly to global form
274/// during construction; no second pass needed.
275///
276/// Typical usage from the XSLT engine:
277///
278/// ```ignore
279/// let mut b = idx.start_rtf();
280/// let root = b.add_document();
281/// let elem = b.add_element(root, "foo", "", None, &[]);
282/// b.add_text(elem, "hello");
283/// let root_id = idx.finish_rtf(b);   // returns encoded root NodeId
284/// ```
285pub struct RtfBuilder {
286    /// Host-vector slot this RTF will occupy.  Captured up front
287    /// so child / parent / attr ids encode to global form during
288    /// construction.
289    pub(crate) host_index: usize,
290    pub(crate) nodes:      Vec<RtfNode>,
291    /// Schema-aware: `(encoded NodeId, (type-ns, type-local))` for each
292    /// constructed node carrying a `type=` / `xsl:type=` annotation.
293    /// Collected during construction (the builder already encodes ids
294    /// to global form) and drained into the host index's PSVI table by
295    /// [`DocIndex::finish_rtf`](super::context::DocIndex).
296    pub typed_nodes: Vec<(NodeId, Box<(String, String)>)>,
297}
298
299impl RtfBuilder {
300    #[allow(dead_code)] // wired through DocIndex::start_rtf in the next step
301    pub(crate) fn new(host_index: usize) -> Self {
302        Self { host_index, nodes: Vec::new(), typed_nodes: Vec::new() }
303    }
304
305    #[inline]
306    fn glob(&self, local: NodeId) -> NodeId {
307        encode_rtf_id(self.host_index, local)
308    }
309
310    fn push(&mut self, kind: RtfNodeKind, parent: Option<NodeId>) -> NodeId {
311        let local_id = self.nodes.len();
312        self.nodes.push(RtfNode {
313            kind,
314            parent,
315            children:  Vec::new(),
316            attr_start: 0, attr_end: 0,
317            ns_start:   0, ns_end:   0,
318        });
319        self.glob(local_id)
320    }
321
322    fn local_of(global: NodeId) -> NodeId {
323        global & RTF_LOCAL_MASK
324    }
325
326    /// Add the synthetic Document node.  Must be the first call
327    /// — the index conventionally treats local id 0 as the
328    /// document root.  Returns the encoded global id.
329    pub fn add_document(&mut self) -> NodeId {
330        assert!(self.nodes.is_empty(),
331            "RtfBuilder::add_document must be the first call");
332        self.push(RtfNodeKind::Document, None)
333    }
334
335    /// Add an element child of `parent`.  `parent` is a global
336    /// id (the value previously returned by `add_document` or
337    /// another `add_element`).
338    pub fn add_element(
339        &mut self, parent: NodeId,
340        qname: &str, namespace_uri: &str, prefix: Option<&str>,
341    ) -> NodeId {
342        let (local_name, _) = qname.rsplit_once(':')
343            .map(|(_, l)| (l, true))
344            .unwrap_or((qname, false));
345        let id = self.push(RtfNodeKind::Element {
346            name:          qname.into(),
347            local_name:    local_name.into(),
348            prefix:        prefix.map(Into::into),
349            namespace_uri: namespace_uri.into(),
350        }, Some(parent));
351        let parent_local = Self::local_of(parent);
352        self.nodes[parent_local].children.push(id);
353        id
354    }
355
356    pub fn add_text(&mut self, parent: NodeId, content: &str) -> NodeId {
357        let id = self.push(RtfNodeKind::Text(content.into()), Some(parent));
358        let parent_local = Self::local_of(parent);
359        self.nodes[parent_local].children.push(id);
360        id
361    }
362
363    pub fn add_comment(&mut self, parent: NodeId, content: &str) -> NodeId {
364        let id = self.push(RtfNodeKind::Comment(content.into()), Some(parent));
365        let parent_local = Self::local_of(parent);
366        self.nodes[parent_local].children.push(id);
367        id
368    }
369
370    pub fn add_pi(&mut self, parent: NodeId, target: &str, data: &str) -> NodeId {
371        let id = self.push(RtfNodeKind::PI {
372            target: target.into(), data: data.into(),
373        }, Some(parent));
374        let parent_local = Self::local_of(parent);
375        self.nodes[parent_local].children.push(id);
376        id
377    }
378
379    /// Set the contiguous attribute-id range for an element.
380    /// Attributes are appended via `add_attribute` AFTER the
381    /// element and BEFORE any further content children — caller
382    /// is responsible for ordering and for calling `finish_attrs`
383    /// to lock in the range.
384    pub fn start_attrs(&mut self, elem_global: NodeId) {
385        let elem_local = Self::local_of(elem_global);
386        let start_local = self.nodes.len();
387        self.nodes[elem_local].attr_start = self.glob(start_local);
388        self.nodes[elem_local].attr_end   = self.glob(start_local);
389    }
390
391    pub fn add_attribute(
392        &mut self, elem_global: NodeId,
393        qname: &str, namespace_uri: &str, prefix: Option<&str>,
394        value: &str,
395    ) -> NodeId {
396        let (local_name, _) = qname.rsplit_once(':')
397            .map(|(_, l)| (l, true))
398            .unwrap_or((qname, false));
399        let id = self.push(RtfNodeKind::Attribute {
400            name:          qname.into(),
401            local_name:    local_name.into(),
402            prefix:        prefix.map(Into::into),
403            namespace_uri: namespace_uri.into(),
404            value:         value.into(),
405        }, Some(elem_global));
406        let elem_local = Self::local_of(elem_global);
407        // Extend the half-open range to cover this new attr.
408        let new_end_local = Self::local_of(id) + 1;
409        self.nodes[elem_local].attr_end = self.glob(new_end_local);
410        id
411    }
412
413    /// Open the namespace-node range for `elem_global`.  Subsequent
414    /// [`add_namespace_node`] calls populate the contiguous slab;
415    /// the range covers them automatically.  Callers must invoke
416    /// this *after* the attribute slab (`start_attrs` /
417    /// `add_attribute`) and *before* the first child, so attribute
418    /// and namespace nodes don't interleave with element children.
419    pub fn start_ns(&mut self, elem_global: NodeId) {
420        let elem_local = Self::local_of(elem_global);
421        let start_local = self.nodes.len();
422        self.nodes[elem_local].ns_start = self.glob(start_local);
423        self.nodes[elem_local].ns_end   = self.glob(start_local);
424    }
425
426    /// Add an in-scope namespace node to `elem_global`.  `prefix` is
427    /// `None` for the default-namespace binding and `Some("")` is
428    /// treated identically; otherwise pass the prefix without colons.
429    /// Returns the globally-encoded id of the new namespace node so
430    /// callers can index it directly (rarely needed — the typical
431    /// access path is `ns_range(elem)`).
432    pub fn add_namespace_node(
433        &mut self, elem_global: NodeId,
434        prefix: Option<&str>, uri: &str,
435    ) -> NodeId {
436        let prefix = prefix.filter(|p| !p.is_empty());
437        let id = self.push(
438            RtfNodeKind::Namespace {
439                prefix: prefix.map(Into::into),
440                uri:    uri.into(),
441            },
442            Some(elem_global),
443        );
444        let elem_local = Self::local_of(elem_global);
445        let new_end_local = Self::local_of(id) + 1;
446        self.nodes[elem_local].ns_end = self.glob(new_end_local);
447        id
448    }
449
450    /// Consume the builder into the populated [`RtfIndex`].
451    pub fn build(self) -> RtfIndex {
452        RtfIndex { nodes: self.nodes, host_index: self.host_index }
453    }
454}
455
456#[cfg(test)]
457mod tests {
458    use super::*;
459
460    #[test]
461    fn rtf_id_round_trips() {
462        let id = encode_rtf_id(7, 42);
463        assert!(is_rtf_id(id));
464        assert_eq!(decode_rtf_id(id), (7, 42));
465    }
466
467    #[test]
468    fn rtf_marker_is_disjoint_from_synthetic() {
469        let s = super::super::context::SYNTHETIC_TEXT_BASE;
470        let r = encode_rtf_id(0, 0);
471        assert!(!is_rtf_id(s),
472            "synthetic ids must not look like RTF ids");
473        assert!(r & s == 0,
474            "RTF and synthetic markers must be distinct bits");
475    }
476}
sup_xml_core/xpath/rtf.rs

sup_xml_core/xpath/
rtf.rs
