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};