Skip to main content

parsec_xpath/
lib.rs

1// SPDX-License-Identifier: Apache-2.0
2// Copyright 2026 James Conway
3
4//! XPath 1.0 over a parsec-html [`Document`], written from the W3C
5//! recommendation: every axis, node test and function of the core
6//! library, with the number, string and boolean rules of sections 3 and 4.
7//!
8//! The tree is read as lxml reads an HTML page, which is what scrapers
9//! expect: element and attribute names are the parser's lowercase ones
10//! (SVG's `clippath`, `viewbox`) in no namespace, so `//div` and `@href`
11//! match, `//DIV` and `@HREF` don't, and a prefixed name (`svg:rect`)
12//! matches nothing. An
13//! XML document built into the same tree brings its namespaces through
14//! [`Namespaces`], and names with a prefix take theirs from the prefixes
15//! a query is run with.
16//!
17//! A query reads the document through an [`Index`], which its owner
18//! builds once per version of the tree. Functions beyond the core library
19//! come from the caller through [`Extensions`].
20//!
21//! Shadow roots are left out, as `document.evaluate` leaves them out: the
22//! XPath data model has no shadow trees, so the axes follow the node tree
23//! and never cross into a host's shadow root or out of one. A shadow tree
24//! is queried on its own by indexing its root as one of [`Index::build`]'s
25//! roots, where it's a root node as a template's contents are: `/` from
26//! inside it is the shadow root, and its host isn't an ancestor.
27
28mod eval;
29mod index;
30mod lexer;
31mod parser;
32
33use std::borrow::Cow;
34use std::fmt;
35
36use parsec::{Document, NodeId};
37
38pub use eval::{Args, WORK_LIMIT};
39pub use index::{CDATA, COMMENT, DOCTYPE, DOCUMENT, ELEMENT, Index, PI, TEXT};
40
41/// The namespace the `xml` prefix is always bound to.
42pub const XML_NS: &str = "http://www.w3.org/XML/1998/namespace";
43
44#[derive(Debug, Clone, PartialEq, Eq)]
45pub struct XPathError {
46    pub query: String,
47    pub reason: String,
48}
49
50impl fmt::Display for XPathError {
51    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
52        write!(f, "invalid XPath {:?}: {}", self.query, self.reason)
53    }
54}
55
56impl std::error::Error for XPathError {}
57
58/// A value a caller can bind to a `$variable`.
59#[derive(Debug, Clone, PartialEq)]
60pub enum XValue {
61    Str(String),
62    Num(f64),
63    Bool(bool),
64}
65
66/// The namespaces of an XML document built into a parsec-html tree,
67/// which the tree leaves to its host. Ids are the host's; 0 is no
68/// namespace.
69pub trait Namespaces: Sync {
70    /// The namespace id of an element.
71    fn ns_of(&self, element: NodeId) -> u32;
72    /// The URI with id `id`; "" for 0.
73    fn uri(&self, id: u32) -> &str;
74    /// The id of `uri` in this document, None if nothing in it has that
75    /// namespace. "" is 0.
76    fn id_of(&self, uri: &str) -> Option<u32>;
77}
78
79/// The document a query runs over: its tree, the tree's index, and for
80/// an XML document its namespaces.
81#[derive(Clone, Copy)]
82pub struct Doc<'a> {
83    pub(crate) tree: &'a Document,
84    pub(crate) index: &'a Index,
85    pub(crate) names: Option<&'a dyn Namespaces>,
86}
87
88impl<'a> Doc<'a> {
89    /// An HTML document. `index` must be of `tree` as it is now.
90    pub fn html(tree: &'a Document, index: &'a Index) -> Doc<'a> {
91        Doc {
92            tree,
93            index,
94            names: None,
95        }
96    }
97
98    /// An XML document, whose elements are [`parsec::Ns::Xml`] and
99    /// whose attributes' namespaces are [`parsec::AttrNs::Host`] ids.
100    pub fn xml(tree: &'a Document, index: &'a Index, names: &'a dyn Namespaces) -> Doc<'a> {
101        Doc {
102            tree,
103            index,
104            names: Some(names),
105        }
106    }
107
108    pub fn tree(&self) -> &'a Document {
109        self.tree
110    }
111
112    pub fn is_xml(&self) -> bool {
113        self.names.is_some()
114    }
115
116    /// An attribute's value by name: exact in XML, and in HTML compared
117    /// ignoring ASCII case, as HTML names are lowercase.
118    pub fn attr(&self, node: NodeId, name: &str) -> Option<&'a str> {
119        let mut attrs = self.tree.attrs(node);
120        if self.is_xml() {
121            return attrs.find(|(_, n, _)| *n == name).map(|(_, _, v)| v);
122        }
123        attrs
124            .find(|(_, n, _)| n.eq_ignore_ascii_case(name))
125            .map(|(_, _, v)| v)
126    }
127
128    /// The name (as written, with any prefix) and value of the `index`th
129    /// attribute of `owner`, as an [`Item::Attr`] names it.
130    pub fn attr_at(&self, owner: NodeId, index: u32) -> (&'a str, &'a str) {
131        self.tree
132            .attrs(owner)
133            .nth(index as usize)
134            .map_or(("", ""), |(_, name, value)| (name, value))
135    }
136}
137
138/// A node in XPath's data model: a tree node, or an attribute (which the
139/// tree keeps on its element rather than as a node of its own). Sixteen
140/// bytes: a node-set can hold every node of a big page, so its name and
141/// value are read from the document ([`Doc::attr_at`]), not kept here.
142#[derive(Debug, Clone, Copy, PartialEq)]
143pub enum Item {
144    Node(NodeId),
145    Attr {
146        owner: NodeId,
147        /// Its place among the element's attributes.
148        index: u32,
149        /// The namespace id (see [`Namespaces`]); 0 for none.
150        ns: u32,
151    },
152}
153
154const _: () = assert!(std::mem::size_of::<Item>() == 16);
155
156/// What an expression evaluates to. A node-set is in document order,
157/// without duplicates.
158#[derive(Debug, Clone)]
159pub enum Value<'a> {
160    Nodes(Vec<Item>),
161    Str(Cow<'a, str>),
162    Num(f64),
163    Bool(bool),
164}
165
166/// Functions beyond XPath 1.0's core library, which a caller provides. A
167/// core function of the same name wins.
168pub trait Extensions: Sync {
169    /// Works out `name()`, or None if this has no function of that name.
170    fn call<'a>(&self, name: &str, args: &Args<'_, 'a>) -> Option<Result<Value<'a>, String>>;
171
172    /// Whether `name()` only ever gives a number or a yes or no, so a
173    /// predicate's call of it can be kept per node (see `memoize`).
174    fn scalar(&self, _name: &str) -> bool {
175        false
176    }
177}
178
179/// No functions beyond the core library.
180pub struct NoExtensions;
181
182impl Extensions for NoExtensions {
183    fn call<'a>(&self, _: &str, _: &Args<'_, 'a>) -> Option<Result<Value<'a>, String>> {
184        None
185    }
186}
187
188/// A compiled XPath expression. It holds no state of any document, so one
189/// can be shared by many threads.
190#[derive(Debug, Clone)]
191pub struct XPath {
192    src: String,
193    expr: parser::Expr,
194    /// The `$variables` the expression uses, found once here rather than
195    /// on every run.
196    variables: Vec<String>,
197}
198
199impl XPath {
200    pub fn new(src: &str) -> Result<XPath, XPathError> {
201        XPath::with_extensions(src, &NoExtensions)
202    }
203
204    /// [`XPath::new`], for running with `extensions`.
205    pub fn with_extensions(src: &str, extensions: &dyn Extensions) -> Result<XPath, XPathError> {
206        let tokens = lexer::tokenize(src)?;
207        let mut expr = parser::parse(src, tokens)?;
208        parser::memoize(&mut expr, &|name| extensions.scalar(name));
209        let mut variables = Vec::new();
210        expr.variables(&mut variables);
211        Ok(XPath {
212            src: src.to_string(),
213            expr,
214            variables,
215        })
216    }
217
218    /// The expression as written.
219    pub fn source(&self) -> &str {
220        &self.src
221    }
222
223    /// Evaluates with `scope` as the context node, `vars` giving the
224    /// `$variables` and `namespaces` binding prefixes to URIs as
225    /// `(prefix, uri)` (a later pair for a prefix wins). `extensions`
226    /// should be what the expression was compiled with.
227    pub fn evaluate<'a>(
228        &self,
229        doc: Doc<'a>,
230        scope: NodeId,
231        vars: &[(String, XValue)],
232        namespaces: &[(String, String)],
233        extensions: &dyn Extensions,
234    ) -> Result<Value<'a>, XPathError> {
235        self.evaluate_within(doc, scope, vars, namespaces, extensions, WORK_LIMIT)
236    }
237
238    /// [`XPath::evaluate`], giving up after `limit` units of work rather
239    /// than [`WORK_LIMIT`].
240    pub fn evaluate_within<'a>(
241        &self,
242        doc: Doc<'a>,
243        scope: NodeId,
244        vars: &[(String, XValue)],
245        namespaces: &[(String, String)],
246        extensions: &dyn Extensions,
247        limit: u64,
248    ) -> Result<Value<'a>, XPathError> {
249        if let Some(missing) = self
250            .variables
251            .iter()
252            .find(|v| !vars.iter().any(|(k, _)| k == *v))
253        {
254            return Err(XPathError {
255                query: self.src.clone(),
256                reason: format!("no value given for ${missing}"),
257            });
258        }
259        eval::run(&self.expr, doc, scope, vars, namespaces, extensions, limit).map_err(|reason| {
260            XPathError {
261                query: self.src.clone(),
262                reason,
263            }
264        })
265    }
266}
267
268// A compiled expression is shared between threads; this fails the build
269// if a change ever stops that.
270const _: () = {
271    const fn shareable<T: Send + Sync>() {}
272    shareable::<XPath>();
273    shareable::<Index>();
274};