GitCorner

Code

ossartcraftvectorcraft🌐
2bc41aeb8602
//! `xpath` on XML and XMLList values: XPath 1.0 expressions
//! (<https://www.w3.org/TR/1999/REC-xpath-19991116/>) evaluated on E4X trees.
//!
//! An expression is read into tokens, then into a syntax tree whose nodes live in one arena, and is
//! evaluated with an explicit task stack, so neither step uses native recursion. Brackets nest at
//! most [`crate::Options::max_depth`] deep. Every token, task and visited node takes fuel, and the
//! token, tree, node-set and string buffers are held against the heap limit while they live.
//!
//! `/` is a root node above the topmost node of the context node's tree. A node-set result is
//! returned as an XMLList of the selected nodes themselves, in document order with attributes
//! before children. The root node and namespace nodes can be selected and tested inside an
//! expression, but a result that holds one throws a `TypeError`, since E4X has no such value. The
//! tree keeps no DTD, so `id()` selects nothing. Prefixes in the expression are read from the
//! namespaces in scope on the context element, and `xml` is always bound.

use std::collections::{HashMap, HashSet};
use std::mem::replace;
use std::rc::Rc;

use crate::builtins::arg;
use crate::error::TOO_DEEP;
use crate::heap::{Key, ObjId, XmlKind, XmlName, XmlNs, key};
use crate::interp::{Abrupt, ErrorType, HeldBytes, Interp, JsResult};
use crate::regexp_vm::use_fuel_n;
use crate::string_builtins::{self, charge_units, flat_charged, push_held};
use crate::value::Value;
use crate::xml::{Xv, is_name_part, is_name_start, is_xml_space, valid_xml_units};
use crate::xml_builtins::scope_of;

const XML_URI: &str = "http://www.w3.org/XML/1998/namespace";
const COLON: u16 = b':' as u16;
const STAR: u16 = b'*' as u16;
const SLASH: u16 = b'/' as u16;
const DOT: u16 = b'.' as u16;
const EQUALS: u16 = b'=' as u16;
const DASH: u16 = b'-' as u16;
/// The estimated bytes of a syntax tree node's own lists, beyond its slot in the arena.
const EXPR_BYTES: usize = 64;
/// The estimated bytes of one entry of a hash map or set the evaluator keeps.
const ENTRY_BYTES: usize = 64;

fn empty() -> Key {
    Rc::from(Vec::new())
}

fn syntax(interp: &mut Interp, message: &str) -> Abrupt {
    interp.throw(ErrorType::Syntax, message)
}

fn internal() -> Abrupt {
    Abrupt::Internal("XPath evaluation state".into())
}

fn is_digit(c: u16) -> bool {
    (0x30..=0x39).contains(&c)
}

// ---- tokens ----

#[derive(Clone, Copy, PartialEq)]
enum Punct {
    LParen,
    RParen,
    LBracket,
    RBracket,
    Dot,
    DotDot,
    At,
    Comma,
    ColonColon,
    Slash,
    SlashSlash,
    Pipe,
    Plus,
    Minus,
    Eq,
    Ne,
    Lt,
    Le,
    Gt,
    Ge,
}

/// A token as the lexer reads it, before names and `*` are told apart by their position.
enum Raw {
    Punct(Punct),
    Star,
    Name(Option<Key>, Key),
    PrefixStar(Key),
    Literal(Key),
    Number(f64),
    Var(Key),
}

#[derive(Clone, Copy, PartialEq)]
enum Axis {
    Ancestor,
    AncestorOrSelf,
    Attribute,
    Child,
    Descendant,
    DescendantOrSelf,
    Following,
    FollowingSibling,
    Namespace,
    Parent,
    Preceding,
    PrecedingSibling,
    Itself,
}

const AXES: [(&str, Axis); 13] = [
    ("ancestor", Axis::Ancestor),
    ("ancestor-or-self", Axis::AncestorOrSelf),
    ("attribute", Axis::Attribute),
    ("child", Axis::Child),
    ("descendant", Axis::Descendant),
    ("descendant-or-self", Axis::DescendantOrSelf),
    ("following", Axis::Following),
    ("following-sibling", Axis::FollowingSibling),
    ("namespace", Axis::Namespace),
    ("parent", Axis::Parent),
    ("preceding", Axis::Preceding),
    ("preceding-sibling", Axis::PrecedingSibling),
    ("self", Axis::Itself),
];

impl Axis {
    /// Whether the axis lists its nodes in reverse document order.
    fn reverse(self) -> bool {
        matches!(self, Axis::Ancestor | Axis::AncestorOrSelf | Axis::Preceding | Axis::PrecedingSibling)
    }
}

/// A node test. A prefix is resolved when the expression runs.
#[derive(Clone)]
enum Test {
    Any,
    Prefix(Key),
    Name(Option<Key>, Key),
    Node,
    Text,
    Comment,
    Pi(Option<Key>),
}

#[derive(Clone, Copy, PartialEq)]
enum Bin {
    Or,
    And,
    Eq,
    Ne,
    Lt,
    Le,
    Gt,
    Ge,
    Add,
    Sub,
    Mul,
    Div,
    Mod,
    Union,
}

impl Bin {
    fn precedence(self) -> u8 {
        match self {
            Bin::Or => 1,
            Bin::And => 2,
            Bin::Eq | Bin::Ne => 3,
            Bin::Lt | Bin::Le | Bin::Gt | Bin::Ge => 4,
            Bin::Add | Bin::Sub => 5,
            Bin::Mul | Bin::Div | Bin::Mod => 6,
            Bin::Union => 8,
        }
    }
}

/// The precedence of unary minus: tighter than `*`, looser than `|`.
const NEG_PRECEDENCE: u8 = 7;

#[derive(Clone, Copy, PartialEq)]
enum Func {
    Last,
    Position,
    Count,
    Id,
    LocalName,
    NamespaceUri,
    Name,
    String,
    Concat,
    StartsWith,
    Contains,
    SubstringBefore,
    SubstringAfter,
    Substring,
    StringLength,
    NormalizeSpace,
    Translate,
    Boolean,
    Not,
    True,
    False,
    Lang,
    Number,
    Sum,
    Floor,
    Ceiling,
    Round,
}

/// The core function library (XPath 1.0 section 4): each name, and its least and most arguments.
const FUNCS: [(&str, Func, usize, usize); 27] = [
    ("last", Func::Last, 0, 0),
    ("position", Func::Position, 0, 0),
    ("count", Func::Count, 1, 1),
    ("id", Func::Id, 1, 1),
    ("local-name", Func::LocalName, 0, 1),
    ("namespace-uri", Func::NamespaceUri, 0, 1),
    ("name", Func::Name, 0, 1),
    ("string", Func::String, 0, 1),
    ("concat", Func::Concat, 2, usize::MAX),
    ("starts-with", Func::StartsWith, 2, 2),
    ("contains", Func::Contains, 2, 2),
    ("substring-before", Func::SubstringBefore, 2, 2),
    ("substring-after", Func::SubstringAfter, 2, 2),
    ("substring", Func::Substring, 2, 3),
    ("string-length", Func::StringLength, 0, 1),
    ("normalize-space", Func::NormalizeSpace, 0, 1),
    ("translate", Func::Translate, 3, 3),
    ("boolean", Func::Boolean, 1, 1),
    ("not", Func::Not, 1, 1),
    ("true", Func::True, 0, 0),
    ("false", Func::False, 0, 0),
    ("lang", Func::Lang, 1, 1),
    ("number", Func::Number, 0, 1),
    ("sum", Func::Sum, 1, 1),
    ("floor", Func::Floor, 1, 1),
    ("ceiling", Func::Ceiling, 1, 1),
    ("round", Func::Round, 1, 1),
];

/// A token the parser reads: names and `*` with their roles decided (XPath 1.0 section 3.7).
enum Tok {
    Punct(Punct),
    Op(Bin),
    Test(Test),
    Axis(Axis),
    Func(Func, &'static str),
    Literal(Key),
    Number(f64),
    Var(Key),
}

fn ncname_end(src: &[u16], at: usize) -> Option<usize> {
    let first = *src.get(at)?;
    if first == COLON || !is_name_start(first) {
        return None;
    }
    let mut end = at + 1;
    while src.get(end).is_some_and(|&c| c != COLON && is_name_part(c)) {
        end += 1;
    }
    valid_xml_units(src.get(at..end)?).then_some(end)
}

fn lex_name(src: &[u16], at: usize) -> Option<(Raw, usize)> {
    let end = ncname_end(src, at)?;
    let first: Key = Rc::from(src.get(at..end)?);
    if src.get(end) != Some(&COLON) || src.get(end + 1) == Some(&COLON) {
        return Some((Raw::Name(None, first), end));
    }
    if src.get(end + 1) == Some(&STAR) {
        return Some((Raw::PrefixStar(first), end + 2));
    }
    let local_end = ncname_end(src, end + 1)?;
    Some((Raw::Name(Some(first), Rc::from(src.get(end + 1..local_end)?)), local_end))
}

fn lex_number(src: &[u16], at: usize) -> Option<(Raw, usize)> {
    let mut end = at;
    while src.get(end).copied().is_some_and(is_digit) {
        end += 1;
    }
    if src.get(end) == Some(&DOT) {
        end += 1;
        while src.get(end).copied().is_some_and(is_digit) {
            end += 1;
        }
    }
    let text = String::from_utf16(src.get(at..end)?).ok()?;
    Some((Raw::Number(text.parse().ok()?), end))
}

fn lex_literal(src: &[u16], at: usize, quote: u16) -> Option<(Raw, usize)> {
    let rest = src.get(at + 1..)?;
    let len = rest.iter().position(|&c| c == quote)?;
    Some((Raw::Literal(Rc::from(rest.get(..len)?)), at + len + 2))
}

fn lex_var(src: &[u16], at: usize) -> Option<(Raw, usize)> {
    let (Raw::Name(..), end) = lex_name(src, at + 1)? else { return None };
    Some((Raw::Var(Rc::from(src.get(at + 1..end)?)), end))
}

/// The token that starts at `src[at]`, and the offset after it.
fn lex_one(src: &[u16], at: usize, c: u16) -> Option<(Raw, usize)> {
    if c != COLON && is_name_start(c) {
        return lex_name(src, at);
    }
    let next = src.get(at + 1).copied();
    let p = |p: Punct, n: usize| Some((Raw::Punct(p), at + n));
    match char::from_u32(u32::from(c))? {
        '(' => p(Punct::LParen, 1),
        ')' => p(Punct::RParen, 1),
        '[' => p(Punct::LBracket, 1),
        ']' => p(Punct::RBracket, 1),
        '@' => p(Punct::At, 1),
        ',' => p(Punct::Comma, 1),
        '|' => p(Punct::Pipe, 1),
        '+' => p(Punct::Plus, 1),
        '-' => p(Punct::Minus, 1),
        '=' => p(Punct::Eq, 1),
        '*' => Some((Raw::Star, at + 1)),
        '/' if next == Some(SLASH) => p(Punct::SlashSlash, 2),
        '/' => p(Punct::Slash, 1),
        ':' if next == Some(COLON) => p(Punct::ColonColon, 2),
        '!' if next == Some(EQUALS) => p(Punct::Ne, 2),
        '<' if next == Some(EQUALS) => p(Punct::Le, 2),
        '<' => p(Punct::Lt, 1),
        '>' if next == Some(EQUALS) => p(Punct::Ge, 2),
        '>' => p(Punct::Gt, 1),
        '.' if next == Some(DOT) => p(Punct::DotDot, 2),
        '.' if next.is_some_and(is_digit) => lex_number(src, at),
        '.' => p(Punct::Dot, 1),
        '"' | '\'' => lex_literal(src, at, c),
        '$' => lex_var(src, at),
        _ if is_digit(c) => lex_number(src, at),
        _ => None,
    }
}

fn lex(interp: &mut Interp, held: &mut HeldBytes, src: &[u16]) -> JsResult<Vec<Raw>> {
    let mut out = Vec::new();
    let mut at = 0;
    loop {
        while src.get(at).copied().is_some_and(is_xml_space) {
            at += 1;
        }
        let Some(&c) = src.get(at) else { return Ok(out) };
        let Some((raw, end)) = lex_one(src, at, c) else {
            return Err(syntax(interp, &format!("the XPath expression cannot be read at offset {at}")));
        };
        charge_units(interp, end - at)?;
        push_held(interp, held, &mut out, raw)?;
        at = end;
    }
}

fn units_are(units: &[u16], text: &str) -> bool {
    units.iter().copied().eq(text.encode_utf16())
}

fn operator_name(name: &[u16]) -> Option<Bin> {
    [("and", Bin::And), ("or", Bin::Or), ("mod", Bin::Mod), ("div", Bin::Div)].into_iter().find(|(n, _)| units_are(name, n)).map(|(_, b)| b)
}

fn punct_token(p: Punct) -> Tok {
    match p {
        Punct::Pipe => Tok::Op(Bin::Union),
        Punct::Plus => Tok::Op(Bin::Add),
        Punct::Minus => Tok::Op(Bin::Sub),
        Punct::Eq => Tok::Op(Bin::Eq),
        Punct::Ne => Tok::Op(Bin::Ne),
        Punct::Lt => Tok::Op(Bin::Lt),
        Punct::Le => Tok::Op(Bin::Le),
        Punct::Gt => Tok::Op(Bin::Gt),
        Punct::Ge => Tok::Op(Bin::Ge),
        other => Tok::Punct(other),
    }
}

/// Whether a token at this point is an operator: there is a token before it, and it is not `@`,
/// `::`, `(`, `[`, `,` or an operator (XPath 1.0 section 3.7).
fn operator_position(last: Option<&Tok>) -> bool {
    last.is_some_and(|t| {
        !matches!(
            t,
            Tok::Punct(Punct::LParen | Punct::LBracket | Punct::At | Punct::Comma | Punct::Slash | Punct::SlashSlash)
                | Tok::Op(_)
                | Tok::Axis(_)
                | Tok::Func(..)
        )
    })
}

/// A name followed by `(`: a node type test, which also takes its `)`, or a function call.
/// Returns the token and how many raw tokens it takes.
fn call_or_node_type(interp: &mut Interp, prefix: Option<&Key>, name: &Key, after: &[Raw]) -> JsResult<(Tok, usize)> {
    if prefix.is_none() {
        let plain = [("node", Test::Node), ("text", Test::Text), ("comment", Test::Comment)].into_iter().find(|(n, _)| units_are(name, n));
        if let Some((_, test)) = plain {
            return match after.first() {
                Some(Raw::Punct(Punct::RParen)) => Ok((Tok::Test(test), 3)),
                _ => Err(syntax(interp, "an XPath node type test takes no argument")),
            };
        }
        if units_are(name, "processing-instruction") {
            return match after {
                [Raw::Punct(Punct::RParen), ..] => Ok((Tok::Test(Test::Pi(None)), 3)),
                [Raw::Literal(target), Raw::Punct(Punct::RParen), ..] => Ok((Tok::Test(Test::Pi(Some(target.clone()))), 4)),
                _ => Err(syntax(interp, "processing-instruction() takes one string literal or none")),
            };
        }
    }
    let found = FUNCS.iter().find(|(n, ..)| prefix.is_none() && units_are(name, n));
    match found {
        Some(&(n, f, ..)) => Ok((Tok::Func(f, n), 2)),
        None => {
            let shown = String::from_utf16_lossy(name);
            Err(interp.type_error(&format!("{shown} is not an XPath 1.0 function")))
        }
    }
}

fn classify(interp: &mut Interp, held: &mut HeldBytes, raw: &[Raw]) -> JsResult<Vec<Tok>> {
    let mut out: Vec<Tok> = Vec::new();
    let mut at = 0;
    while let Some(r) = raw.get(at) {
        interp.use_fuel()?;
        let operator = operator_position(out.last());
        let next = raw.get(at + 1);
        let (tok, used) = match r {
            Raw::Star if operator => (Tok::Op(Bin::Mul), 1),
            Raw::Star => (Tok::Test(Test::Any), 1),
            Raw::Name(None, n) if operator => match operator_name(n) {
                Some(op) => (Tok::Op(op), 1),
                None => return Err(syntax(interp, "an XPath operator is missing")),
            },
            Raw::Name(p, n) if matches!(next, Some(Raw::Punct(Punct::LParen))) => {
                call_or_node_type(interp, p.as_ref(), n, raw.get(at + 2..).unwrap_or_default())?
            }
            Raw::Name(p, n) if matches!(next, Some(Raw::Punct(Punct::ColonColon))) => {
                let axis = AXES.iter().find(|(a, _)| p.is_none() && units_are(n, a)).map(|&(_, a)| a);
                match axis {
                    Some(a) => (Tok::Axis(a), 2),
                    None => return Err(syntax(interp, &format!("{} is not an XPath axis", String::from_utf16_lossy(n)))),
                }
            }
            Raw::Name(p, n) => (Tok::Test(Test::Name(p.clone(), n.clone())), 1),
            Raw::PrefixStar(p) => (Tok::Test(Test::Prefix(p.clone())), 1),
            Raw::Punct(Punct::ColonColon) => return Err(syntax(interp, "an XPath axis name is missing before ::")),
            Raw::Punct(p) => (punct_token(*p), 1),
            Raw::Literal(s) => (Tok::Literal(s.clone()), 1),
            Raw::Number(n) => (Tok::Number(*n), 1),
            Raw::Var(v) => (Tok::Var(v.clone()), 1),
        };
        push_held(interp, held, &mut out, tok)?;
        at += used;
    }
    Ok(out)
}

// ---- the syntax tree ----

struct Step {
    axis: Axis,
    test: Test,
    preds: Vec<usize>,
}

enum Expr {
    Bin(Bin, usize, usize),
    Neg(usize),
    Num(f64),
    Lit(Key),
    Var(usize),
    Call(Func, Vec<usize>),
    /// A location path, or a filter expression with its predicates, followed by steps.
    Path {
        filter: Option<(usize, Vec<usize>)>,
        absolute: bool,
        steps: Vec<Step>,
    },
}

/// A parsed expression: the tree in its arena, its root, and the variables and prefixes it names.
struct Parsed {
    exprs: Vec<Expr>,
    root: usize,
    vars: Vec<Key>,
    prefixes: Vec<Key>,
    _held: HeldBytes,
}

#[derive(Clone, Copy)]
enum Op {
    Bin(Bin),
    Neg,
}

impl Op {
    fn precedence(self) -> u8 {
        match self {
            Op::Bin(b) => b.precedence(),
            Op::Neg => NEG_PRECEDENCE,
        }
    }
}

/// A path expression being read.
#[derive(Default)]
struct Operand {
    filter: Option<(usize, Vec<usize>)>,
    absolute: bool,
    steps: Vec<Step>,
    /// The last step is `.` or `..`, which take no predicate.
    abbreviated: bool,
}

impl Operand {
    fn bare_root(&self) -> bool {
        self.absolute && self.steps.is_empty() && self.filter.is_none()
    }
}

enum FrameKind {
    Top,
    Group,
    Pred,
    Args(Func, &'static str, Vec<usize>),
}

/// One bracket level: its operators and operands, read by operator precedence.
struct Frame {
    kind: FrameKind,
    ops: Vec<Op>,
    vals: Vec<usize>,
    operand: Option<Operand>,
}

impl Frame {
    fn new(kind: FrameKind) -> Self {
        Frame { kind, ops: Vec::new(), vals: Vec::new(), operand: None }
    }
}

#[derive(Clone, Copy, PartialEq)]
enum Want {
    Operand,
    Step,
    Test(Axis),
    After,
}

struct Parser<'i> {
    interp: &'i mut Interp,
    held: HeldBytes,
    exprs: Vec<Expr>,
    vars: Vec<Key>,
    var_index: HashMap<Key, usize>,
    prefixes: HashSet<Key>,
    frames: Vec<Frame>,
    want: Want,
}

impl Parser<'_> {
    fn error(&mut self, message: &str) -> Abrupt {
        syntax(self.interp, message)
    }

    fn push_expr(&mut self, e: Expr) -> JsResult<usize> {
        self.held.add(self.interp, EXPR_BYTES)?;
        push_held(self.interp, &mut self.held, &mut self.exprs, e)?;
        Ok(self.exprs.len() - 1)
    }

    fn top(&mut self) -> JsResult<&mut Frame> {
        self.frames.last_mut().ok_or_else(internal)
    }

    fn operand(&mut self) -> JsResult<&mut Operand> {
        self.top()?.operand.as_mut().ok_or_else(internal)
    }

    fn open(&mut self, kind: FrameKind) -> JsResult<()> {
        if self.frames.len() >= self.interp.options.max_depth {
            return Err(self.error(TOO_DEEP));
        }
        self.held.add(self.interp, size_of::<Frame>())?;
        self.frames.push(Frame::new(kind));
        self.want = Want::Operand;
        Ok(())
    }

    fn token(&mut self, tok: Tok) -> JsResult<()> {
        match self.want {
            Want::Operand => self.operand_token(tok),
            Want::Step => self.step_token(tok),
            Want::Test(axis) => match tok {
                Tok::Test(test) => self.push_step(axis, test, false),
                _ => Err(self.error("an XPath node test is missing")),
            },
            Want::After => self.after_token(tok),
        }
    }

    fn primary(&mut self, e: Expr) -> JsResult<()> {
        let id = self.push_expr(e)?;
        self.top()?.operand = Some(Operand { filter: Some((id, Vec::new())), ..Operand::default() });
        self.want = Want::After;
        Ok(())
    }

    fn operand_token(&mut self, tok: Tok) -> JsResult<()> {
        match tok {
            Tok::Op(Bin::Sub) => {
                self.top()?.ops.push(Op::Neg);
                Ok(())
            }
            Tok::Punct(Punct::Slash) => {
                self.top()?.operand = Some(Operand { absolute: true, ..Operand::default() });
                self.want = Want::Step;
                Ok(())
            }
            Tok::Punct(Punct::SlashSlash) => {
                self.top()?.operand = Some(Operand { absolute: true, ..Operand::default() });
                self.descendants_step()
            }
            Tok::Literal(s) => self.primary(Expr::Lit(s)),
            Tok::Number(n) => self.primary(Expr::Num(n)),
            Tok::Var(name) => {
                let next = self.vars.len();
                let at = *self.var_index.entry(name.clone()).or_insert(next);
                if at == next {
                    push_held(self.interp, &mut self.held, &mut self.vars, name)?;
                }
                self.primary(Expr::Var(at))
            }
            Tok::Func(f, n) => self.open(FrameKind::Args(f, n, Vec::new())),
            Tok::Punct(Punct::LParen) => self.open(FrameKind::Group),
            Tok::Punct(Punct::RParen) if self.empty_call()? => self.close_paren(),
            tok @ (Tok::Test(_) | Tok::Axis(_) | Tok::Punct(Punct::At | Punct::Dot | Punct::DotDot)) => {
                self.top()?.operand = Some(Operand::default());
                self.step_token(tok)
            }
            _ => Err(self.error("an XPath operand is missing")),
        }
    }

    /// Whether the open bracket is a function call's, with nothing in it yet.
    fn empty_call(&mut self) -> JsResult<bool> {
        let f = self.top()?;
        Ok(matches!(&f.kind, FrameKind::Args(_, _, args) if args.is_empty()) && f.ops.is_empty() && f.vals.is_empty() && f.operand.is_none())
    }

    fn descendants_step(&mut self) -> JsResult<()> {
        self.operand()?.steps.push(Step { axis: Axis::DescendantOrSelf, test: Test::Node, preds: Vec::new() });
        self.want = Want::Step;
        Ok(())
    }

    fn push_step(&mut self, axis: Axis, test: Test, abbreviated: bool) -> JsResult<()> {
        if let Test::Prefix(p) | Test::Name(Some(p), _) = &test
            && !self.prefixes.contains(p)
        {
            self.held.add(self.interp, ENTRY_BYTES)?;
            self.prefixes.insert(p.clone());
        }
        self.held.add(self.interp, size_of::<Step>())?;
        let operand = self.operand()?;
        operand.steps.push(Step { axis, test, preds: Vec::new() });
        operand.abbreviated = abbreviated;
        self.want = Want::After;
        Ok(())
    }

    fn step_token(&mut self, tok: Tok) -> JsResult<()> {
        match tok {
            Tok::Punct(Punct::Dot) => self.push_step(Axis::Itself, Test::Node, true),
            Tok::Punct(Punct::DotDot) => self.push_step(Axis::Parent, Test::Node, true),
            Tok::Punct(Punct::At) => {
                self.want = Want::Test(Axis::Attribute);
                Ok(())
            }
            Tok::Axis(a) => {
                self.want = Want::Test(a);
                Ok(())
            }
            Tok::Test(t) => self.push_step(Axis::Child, t, false),
            tok if self.operand()?.bare_root() => {
                self.want = Want::After;
                self.after_token(tok)
            }
            _ => Err(self.error("an XPath step is missing")),
        }
    }

    fn after_token(&mut self, tok: Tok) -> JsResult<()> {
        match tok {
            Tok::Punct(p @ (Punct::LBracket | Punct::Slash | Punct::SlashSlash)) => {
                let operand = self.operand()?;
                let (bare, abbreviated) = (operand.bare_root(), operand.abbreviated);
                if bare || (p == Punct::LBracket && abbreviated) {
                    return Err(self.error("an XPath predicate or step cannot follow here"));
                }
                match p {
                    Punct::LBracket => self.open(FrameKind::Pred),
                    Punct::Slash => {
                        self.want = Want::Step;
                        Ok(())
                    }
                    _ => self.descendants_step(),
                }
            }
            Tok::Op(b) => self.binary(b),
            Tok::Punct(Punct::RParen) => self.close_paren(),
            Tok::Punct(Punct::RBracket) => self.close_bracket(),
            Tok::Punct(Punct::Comma) => self.next_argument(),
            _ => Err(self.error("an XPath operator is missing")),
        }
    }

    fn finish_operand(&mut self, operand: Operand) -> JsResult<usize> {
        match operand {
            Operand { filter: Some((e, preds)), steps, .. } if preds.is_empty() && steps.is_empty() => Ok(e),
            Operand { filter, absolute, steps, .. } => self.push_expr(Expr::Path { filter, absolute, steps }),
        }
    }

    fn reduce_one(&mut self, frame: &mut Frame) -> JsResult<()> {
        let op = frame.ops.pop().ok_or_else(internal)?;
        let rhs = frame.vals.pop().ok_or_else(internal)?;
        let e = match op {
            Op::Neg => Expr::Neg(rhs),
            Op::Bin(b) => Expr::Bin(b, frame.vals.pop().ok_or_else(internal)?, rhs),
        };
        let id = self.push_expr(e)?;
        frame.vals.push(id);
        Ok(())
    }

    fn binary(&mut self, b: Bin) -> JsResult<()> {
        let mut frame = self.frames.pop().ok_or_else(internal)?;
        let result = self.binary_in(&mut frame, b);
        self.frames.push(frame);
        result?;
        self.want = Want::Operand;
        Ok(())
    }

    fn binary_in(&mut self, frame: &mut Frame, b: Bin) -> JsResult<()> {
        let operand = frame.operand.take().ok_or_else(internal)?;
        let e = self.finish_operand(operand)?;
        frame.vals.push(e);
        while frame.ops.last().is_some_and(|op| op.precedence() >= b.precedence()) {
            self.interp.use_fuel()?;
            self.reduce_one(frame)?;
        }
        self.held.add(self.interp, 2 * size_of::<usize>())?;
        frame.ops.push(Op::Bin(b));
        Ok(())
    }

    /// Ends the innermost bracket and returns its kind and expression.
    fn close(&mut self) -> JsResult<(FrameKind, usize)> {
        if self.frames.len() < 2 {
            return Err(self.error("the XPath expression has an unmatched closing bracket"));
        }
        let mut frame = self.frames.pop().ok_or_else(internal)?;
        let e = self.reduce(&mut frame)?;
        Ok((frame.kind, e))
    }

    fn reduce(&mut self, frame: &mut Frame) -> JsResult<usize> {
        let operand = frame.operand.take().ok_or_else(|| syntax(self.interp, "an XPath operand is missing"))?;
        let e = self.finish_operand(operand)?;
        frame.vals.push(e);
        while !frame.ops.is_empty() {
            self.interp.use_fuel()?;
            self.reduce_one(frame)?;
        }
        match frame.vals.as_slice() {
            [e] => Ok(*e),
            _ => Err(internal()),
        }
    }

    fn close_paren(&mut self) -> JsResult<()> {
        let (kind, e) = if self.top()?.operand.is_none() {
            (self.frames.pop().ok_or_else(internal)?.kind, None)
        } else {
            let (kind, e) = self.close()?;
            (kind, Some(e))
        };
        match kind {
            FrameKind::Group => self.primary_id(e.ok_or_else(internal)?),
            FrameKind::Args(f, name, mut args) => {
                args.extend(e);
                let (_, _, least, most) = FUNCS.iter().find(|(_, g, ..)| *g == f).copied().ok_or_else(internal)?;
                if args.len() < least || args.len() > most {
                    return Err(self.interp.type_error(&format!("the XPath function {name} takes the wrong number of arguments")));
                }
                let call = self.push_expr(Expr::Call(f, args))?;
                self.primary_id(call)
            }
            _ => Err(self.error("the XPath expression has an unmatched )")),
        }
    }

    fn primary_id(&mut self, id: usize) -> JsResult<()> {
        if self.frames.is_empty() {
            return Err(self.error("the XPath expression has an unmatched )"));
        }
        self.top()?.operand = Some(Operand { filter: Some((id, Vec::new())), ..Operand::default() });
        self.want = Want::After;
        Ok(())
    }

    fn close_bracket(&mut self) -> JsResult<()> {
        let (kind, e) = self.close()?;
        if !matches!(kind, FrameKind::Pred) {
            return Err(self.error("the XPath expression has an unmatched ]"));
        }
        let operand = self.operand()?;
        match (operand.steps.last_mut(), operand.filter.as_mut()) {
            (Some(step), _) => step.preds.push(e),
            (None, Some((_, preds))) => preds.push(e),
            (None, None) => return Err(internal()),
        }
        self.want = Want::After;
        Ok(())
    }

    fn next_argument(&mut self) -> JsResult<()> {
        if !matches!(self.top()?.kind, FrameKind::Args(..)) || self.frames.len() < 2 {
            return Err(self.error("a comma in an XPath expression must separate function arguments"));
        }
        let mut frame = self.frames.pop().ok_or_else(internal)?;
        let e = self.reduce(&mut frame);
        if let (Ok(e), FrameKind::Args(_, _, args)) = (&e, &mut frame.kind) {
            args.push(*e);
        }
        frame.ops.clear();
        frame.vals.clear();
        self.frames.push(frame);
        e?;
        self.want = Want::Operand;
        Ok(())
    }

    fn finish(mut self) -> JsResult<Parsed> {
        let complete = self.want == Want::After || (self.want == Want::Step && self.operand()?.bare_root());
        if !complete || self.frames.len() != 1 {
            return Err(self.error("the XPath expression ends early"));
        }
        let mut frame = self.frames.pop().ok_or_else(internal)?;
        let root = self.reduce(&mut frame)?;
        Ok(Parsed { exprs: self.exprs, root, vars: self.vars, prefixes: self.prefixes.into_iter().collect(), _held: self.held })
    }
}

fn parse(interp: &mut Interp, src: &[u16]) -> JsResult<Parsed> {
    let mut held = HeldBytes::new(interp);
    let raw = lex(interp, &mut held, src)?;
    let toks = classify(interp, &mut held, &raw)?;
    drop(raw);
    let mut p = Parser {
        interp,
        held,
        exprs: Vec::new(),
        vars: Vec::new(),
        var_index: HashMap::new(),
        prefixes: HashSet::new(),
        frames: vec![Frame::new(FrameKind::Top)],
        want: Want::Operand,
    };
    for tok in toks {
        p.interp.use_fuel()?;
        p.token(tok)?;
    }
    p.finish()
}

// ---- values ----

/// A node of the XPath data model. `Root` is the root above the topmost node it names, and `Ns`
/// is a namespace node of `owner`, at position `at` among its namespaces.
#[derive(Clone, PartialEq, Eq, Hash)]
enum XNode {
    Root(ObjId),
    Node(ObjId),
    Ns { owner: ObjId, at: u32, prefix: Key, uri: Key },
}

#[derive(Clone, Copy, PartialEq)]
enum NodeKind {
    Root,
    Ns,
    Xml(XmlKind),
}

/// A list of nodes whose buffer is held against the heap limit.
struct Nodes {
    list: Vec<XNode>,
    held: HeldBytes,
}

impl Nodes {
    fn new(interp: &Interp) -> Self {
        Nodes { list: Vec::new(), held: HeldBytes::new(interp) }
    }

    fn push(&mut self, interp: &mut Interp, n: XNode) -> JsResult<()> {
        push_held(interp, &mut self.held, &mut self.list, n)
    }
}

/// A string value whose units are held against the heap limit when the evaluator built them.
struct Text {
    units: Key,
    _held: HeldBytes,
}

impl Text {
    fn plain(interp: &Interp, units: Key) -> Self {
        Text { units, _held: HeldBytes::new(interp) }
    }
}

struct TextBuf {
    units: Vec<u16>,
    held: HeldBytes,
}

impl TextBuf {
    fn new(interp: &Interp) -> Self {
        TextBuf { units: Vec::new(), held: HeldBytes::new(interp) }
    }

    fn push(&mut self, interp: &mut Interp, more: &[u16]) -> JsResult<()> {
        charge_units(interp, more.len())?;
        let want = self.units.len().saturating_add(more.len());
        let cap = self.units.capacity();
        if want > cap {
            let grown = want.max(cap.saturating_mul(2)).max(16);
            self.held.add(interp, (grown - cap).saturating_mul(2))?;
            self.units.reserve_exact(grown - self.units.len());
        }
        self.units.extend_from_slice(more);
        Ok(())
    }

    fn finish(self) -> Text {
        Text { units: Rc::from(self.units), _held: self.held }
    }
}

enum Val {
    Set(Nodes),
    Bool(bool),
    Num(f64),
    Str(Text),
}

/// A variable's value, read from the variables object before evaluation starts.
enum Bound {
    Set(Vec<XNode>),
    Bool(bool),
    Num(f64),
    Str(Key),
}

#[derive(Clone)]
struct Ctx {
    node: XNode,
    pos: usize,
    size: usize,
}

/// A location path being evaluated. Stage 0 applies the filter expression's predicates to the
/// filter's nodes; stage `s` applies step `s - 1` to each node of `inputs` in turn.
struct PathRun {
    path: usize,
    stage: usize,
    inputs: Nodes,
    ci: usize,
    cur: Nodes,
    pred: usize,
    at: usize,
    kept: Nodes,
    waiting: bool,
    out: Nodes,
    seen: HashSet<XNode>,
    seen_held: HeldBytes,
}

enum Task {
    Eval(usize, Ctx),
    Bin(Bin),
    Neg,
    Logic { and: bool, rhs: usize, ctx: Ctx },
    Bool,
    Call(Func, usize, Ctx),
    PathStart(usize),
    Path(Box<PathRun>),
}

fn to_bool(v: &Val) -> bool {
    match v {
        Val::Set(s) => !s.list.is_empty(),
        Val::Bool(b) => *b,
        Val::Num(n) => *n != 0.0 && !n.is_nan(),
        Val::Str(t) => !t.units.is_empty(),
    }
}

/// The number a string stands for (XPath 1.0 section 4.4): optional white space, an optional
/// minus, digits with an optional fraction, optional white space; anything else is NaN.
fn str_num(interp: &mut Interp, units: &[u16]) -> JsResult<f64> {
    let start = units.iter().position(|&c| !is_xml_space(c)).unwrap_or(units.len());
    let end = units.iter().rposition(|&c| !is_xml_space(c)).map_or(start, |e| e + 1);
    let body = units.get(start..end).unwrap_or_default();
    let (negative, digits) = match body.split_first() {
        Some((&DASH, rest)) => (true, rest),
        _ => (false, body),
    };
    let dots = digits.iter().filter(|&&c| c == DOT).count();
    if dots > 1 || !digits.iter().all(|&c| c == DOT || is_digit(c)) || !digits.iter().any(|&c| is_digit(c)) {
        return Ok(f64::NAN);
    }
    let mut held = HeldBytes::new(interp);
    held.add(interp, digits.len())?;
    let text: String = digits.iter().map(|&c| char::from(c as u8)).collect();
    let n: f64 = text.parse().unwrap_or(f64::NAN);
    Ok(if negative { -n } else { n })
}

/// A number as a string (XPath 1.0 section 4.2): integers without a decimal point, and no
/// exponent.
fn num_text(n: f64) -> String {
    if n.is_nan() {
        "NaN".into()
    } else if n.is_infinite() {
        if n > 0.0 { "Infinity".into() } else { "-Infinity".into() }
    } else if n == 0.0 {
        "0".into()
    } else {
        format!("{n}")
    }
}

/// `round` (XPath 1.0 section 4.4): the nearest integer, halves toward positive infinity, with
/// negative zero for values from -0.5 up to zero.
fn round(n: f64) -> f64 {
    if !n.is_finite() || n == 0.0 {
        return n;
    }
    let floor = n.floor();
    let r = if n - floor >= 0.5 { floor + 1.0 } else { floor };
    if r == 0.0 && n < 0.0 { -0.0 } else { r }
}

fn compare_numbers(op: Bin, a: f64, b: f64) -> bool {
    match op {
        Bin::Eq => a == b,
        Bin::Ne => a != b,
        Bin::Lt => a < b,
        Bin::Le => a <= b,
        Bin::Gt => a > b,
        _ => a >= b,
    }
}

fn flip(op: Bin) -> Bin {
    match op {
        Bin::Lt => Bin::Gt,
        Bin::Le => Bin::Ge,
        Bin::Gt => Bin::Lt,
        Bin::Ge => Bin::Le,
        other => other,
    }
}

fn code_points(units: &[u16]) -> Vec<u32> {
    char::decode_utf16(units.iter().copied()).map(|r| r.map_or_else(|e| u32::from(e.unpaired_surrogate()), u32::from)).collect()
}

fn push_point(out: &mut Vec<u16>, p: u32) {
    match char::from_u32(p) {
        Some(c) => {
            let mut buf = [0u16; 2];
            out.extend_from_slice(c.encode_utf16(&mut buf));
        }
        None => out.extend(u16::try_from(p).ok()),
    }
}

fn lower(c: u16) -> u16 {
    if (0x41..=0x5A).contains(&c) { c + 0x20 } else { c }
}

fn same_ignoring_case(a: &[u16], b: &[u16]) -> bool {
    a.len() == b.len() && a.iter().zip(b).all(|(&x, &y)| lower(x) == lower(y))
}

fn name_uri(name: &XmlName) -> &[u16] {
    name.uri.as_deref().unwrap_or_default()
}

fn kind_of(interp: &Interp, n: &XNode) -> JsResult<NodeKind> {
    Ok(match n {
        XNode::Root(_) => NodeKind::Root,
        XNode::Ns { .. } => NodeKind::Ns,
        XNode::Node(x) => NodeKind::Xml(interp.xml_kind(*x)?),
    })
}

fn parent_of(interp: &Interp, n: &XNode) -> JsResult<Option<XNode>> {
    Ok(match n {
        XNode::Root(_) => None,
        XNode::Node(x) => Some(interp.xml_node(*x)?.parent.map_or(XNode::Root(*x), XNode::Node)),
        XNode::Ns { owner, .. } => Some(XNode::Node(*owner)),
    })
}

/// The parent of `x` and the position of `x` among its children, when `x` is a child.
fn child_position(interp: &mut Interp, x: ObjId) -> JsResult<Option<(ObjId, usize)>> {
    let node = interp.xml_node(x)?;
    let Some(p) = node.parent.filter(|_| node.kind != XmlKind::Attribute) else { return Ok(None) };
    let len = interp.xml_node(p)?.children.len();
    for i in 0..len {
        interp.use_fuel()?;
        if interp.xml_node(p)?.children.get(i) == Some(&x) {
            return Ok(Some((p, i)));
        }
    }
    Ok(None)
}

fn top_of(interp: &mut Interp, mut x: ObjId) -> JsResult<ObjId> {
    while let Some(p) = interp.xml_node(x)?.parent {
        interp.use_fuel()?;
        x = p;
    }
    Ok(x)
}

/// The XPath expression evaluator for one call: the parsed expression, the variables, the
/// prefixes resolved for the current context element, and the document order of the trees met.
struct Ev<'p> {
    parsed: &'p Parsed,
    bound: Vec<Bound>,
    uris: HashMap<Key, Key>,
    order: HashMap<ObjId, u64>,
    root_order: HashMap<ObjId, u64>,
    next: u64,
    held: HeldBytes,
    tasks: Vec<Task>,
    vals: Vec<Val>,
}

impl<'p> Ev<'p> {
    fn new(interp: &mut Interp, parsed: &'p Parsed, bound: Vec<Bound>) -> JsResult<Self> {
        let mut ev = Ev {
            parsed,
            bound: Vec::new(),
            uris: HashMap::new(),
            order: HashMap::new(),
            root_order: HashMap::new(),
            next: 0,
            held: HeldBytes::new(interp),
            tasks: Vec::new(),
            vals: Vec::new(),
        };
        for b in bound {
            let b = match b {
                Bound::Set(list) => {
                    let mut nodes = Nodes::new(interp);
                    for n in list {
                        nodes.push(interp, n)?;
                    }
                    let sorted = ev.sort(interp, nodes)?;
                    ev.held.add(interp, sorted.list.len().saturating_mul(size_of::<XNode>()))?;
                    Bound::Set(sorted.list)
                }
                other => other,
            };
            ev.bound.push(b);
        }
        Ok(ev)
    }

    // ---- document order ----

    fn put_order(&mut self, interp: &mut Interp, x: ObjId) -> JsResult<()> {
        self.held.add(interp, ENTRY_BYTES)?;
        self.order.insert(x, self.next);
        self.next += 1;
        Ok(())
    }

    /// Numbers the tree under `top` in document order: the root, then each node followed by its
    /// attributes and then its children.
    fn number_tree(&mut self, interp: &mut Interp, top: ObjId) -> JsResult<()> {
        if self.root_order.contains_key(&top) {
            return Ok(());
        }
        self.held.add(interp, ENTRY_BYTES)?;
        self.root_order.insert(top, self.next);
        self.next += 1;
        self.number_node(interp, top)?;
        let mut held = HeldBytes::new(interp);
        let mut stack = Vec::new();
        push_held(interp, &mut held, &mut stack, (top, 0usize))?;
        while let Some(&(x, at)) = stack.last() {
            interp.use_fuel()?;
            let Some(c) = interp.xml_node(x)?.children.get(at).copied() else {
                stack.pop();
                continue;
            };
            if let Some(frame) = stack.last_mut() {
                frame.1 += 1;
            }
            self.number_node(interp, c)?;
            push_held(interp, &mut held, &mut stack, (c, 0))?;
        }
        Ok(())
    }

    fn number_node(&mut self, interp: &mut Interp, x: ObjId) -> JsResult<()> {
        self.put_order(interp, x)?;
        let count = interp.xml_node(x)?.attrs.len();
        for i in 0..count {
            interp.use_fuel()?;
            if let Some(a) = interp.xml_node(x)?.attrs.get(i).copied() {
                self.put_order(interp, a)?;
            }
        }
        Ok(())
    }

    fn order_of(&mut self, interp: &mut Interp, n: &XNode) -> JsResult<(u64, u32)> {
        match n {
            XNode::Root(t) => {
                self.number_tree(interp, *t)?;
                Ok((self.root_order.get(t).copied().ok_or_else(internal)?, 0))
            }
            XNode::Node(x) => {
                if !self.order.contains_key(x) {
                    let top = top_of(interp, *x)?;
                    self.number_tree(interp, top)?;
                }
                Ok((self.order.get(x).copied().ok_or_else(internal)?, 0))
            }
            XNode::Ns { owner, at, .. } => {
                let (o, _) = self.order_of(interp, &XNode::Node(*owner))?;
                Ok((o, at.saturating_add(1)))
            }
        }
    }

    /// The nodes in document order, without repeats.
    fn sort(&mut self, interp: &mut Interp, set: Nodes) -> JsResult<Nodes> {
        if set.list.len() < 2 {
            return Ok(set);
        }
        let n = set.list.len() as u64;
        let mut held = HeldBytes::new(interp);
        let mut keyed = Vec::new();
        for x in set.list {
            let k = self.order_of(interp, &x)?;
            push_held(interp, &mut held, &mut keyed, (k, x))?;
        }
        use_fuel_n(interp, n.saturating_mul(u64::from(n.ilog2()) + 1) / 8 + 1)?;
        keyed.sort_by_key(|(k, _)| *k);
        keyed.dedup_by_key(|(k, _)| *k);
        let mut out = Nodes::new(interp);
        for (_, x) in keyed {
            out.push(interp, x)?;
        }
        Ok(out)
    }

    // ---- axes and node tests ----

    fn prefix_uri(&self, p: &Key) -> JsResult<&Key> {
        self.uris.get(p).ok_or_else(internal)
    }

    fn matches(&self, interp: &Interp, axis: Axis, test: &Test, n: &XNode) -> JsResult<bool> {
        let kind = kind_of(interp, n)?;
        let principal = match axis {
            Axis::Attribute => NodeKind::Xml(XmlKind::Attribute),
            Axis::Namespace => NodeKind::Ns,
            _ => NodeKind::Xml(XmlKind::Element),
        };
        let name = match n {
            XNode::Node(x) => interp.xml_node(*x)?.name.as_ref(),
            _ => None,
        };
        Ok(match test {
            Test::Node => true,
            Test::Text => kind == NodeKind::Xml(XmlKind::Text),
            Test::Comment => kind == NodeKind::Xml(XmlKind::Comment),
            Test::Pi(target) => kind == NodeKind::Xml(XmlKind::Pi) && target.as_ref().is_none_or(|t| name.is_some_and(|q| q.local == *t)),
            Test::Any => kind == principal,
            Test::Prefix(p) => {
                let uri = self.prefix_uri(p)?;
                kind == principal && name.is_some_and(|q| name_uri(q) == &**uri)
            }
            Test::Name(p, local) => kind == principal && self.name_matches(n, name, p.as_ref(), local)?,
        })
    }

    fn name_matches(&self, n: &XNode, name: Option<&XmlName>, prefix: Option<&Key>, local: &Key) -> JsResult<bool> {
        if let XNode::Ns { prefix: ns_prefix, .. } = n {
            return Ok(prefix.is_none() && ns_prefix == local);
        }
        let Some(q) = name else { return Ok(false) };
        let uri: &[u16] = match prefix {
            Some(p) => self.prefix_uri(p)?,
            None => &[],
        };
        Ok(q.local == *local && name_uri(q) == uri)
    }

    fn add(&self, interp: &mut Interp, out: &mut Nodes, axis: Axis, test: &Test, n: XNode) -> JsResult<()> {
        interp.use_fuel()?;
        if self.matches(interp, axis, test, &n)? {
            out.push(interp, n)?;
        }
        Ok(())
    }

    /// Adds `x` and the nodes under it, in document order.
    fn subtree(&self, interp: &mut Interp, out: &mut Nodes, axis: Axis, test: &Test, x: ObjId) -> JsResult<()> {
        self.add(interp, out, axis, test, XNode::Node(x))?;
        self.under(interp, out, axis, test, x)
    }

    /// Adds the nodes under `x`, in document order.
    fn under(&self, interp: &mut Interp, out: &mut Nodes, axis: Axis, test: &Test, x: ObjId) -> JsResult<()> {
        let mut held = HeldBytes::new(interp);
        let mut stack = Vec::new();
        push_held(interp, &mut held, &mut stack, (x, 0usize))?;
        while let Some(&(p, at)) = stack.last() {
            let Some(c) = interp.xml_node(p)?.children.get(at).copied() else {
                stack.pop();
                continue;
            };
            if let Some(frame) = stack.last_mut() {
                frame.1 += 1;
            }
            self.add(interp, out, axis, test, XNode::Node(c))?;
            push_held(interp, &mut held, &mut stack, (c, 0))?;
        }
        Ok(())
    }

    fn descendants(&self, interp: &mut Interp, out: &mut Nodes, axis: Axis, test: &Test, n: &XNode) -> JsResult<()> {
        match n {
            XNode::Root(t) => self.subtree(interp, out, axis, test, *t),
            XNode::Node(x) => self.under(interp, out, axis, test, *x),
            XNode::Ns { .. } => Ok(()),
        }
    }

    fn children(&self, interp: &mut Interp, out: &mut Nodes, axis: Axis, test: &Test, n: &XNode) -> JsResult<()> {
        let x = match n {
            XNode::Root(t) => return self.add(interp, out, axis, test, XNode::Node(*t)),
            XNode::Node(x) => *x,
            XNode::Ns { .. } => return Ok(()),
        };
        let count = interp.xml_node(x)?.children.len();
        for i in 0..count {
            if let Some(c) = interp.xml_node(x)?.children.get(i).copied() {
                self.add(interp, out, axis, test, XNode::Node(c))?;
            }
        }
        Ok(())
    }

    fn ancestors(&self, interp: &mut Interp, out: &mut Nodes, axis: Axis, test: &Test, n: &XNode) -> JsResult<()> {
        let mut cur = parent_of(interp, n)?;
        while let Some(p) = cur {
            cur = parent_of(interp, &p)?;
            self.add(interp, out, axis, test, p)?;
        }
        Ok(())
    }

    fn siblings(&self, interp: &mut Interp, out: &mut Nodes, axis: Axis, test: &Test, n: &XNode) -> JsResult<()> {
        let XNode::Node(x) = n else { return Ok(()) };
        let Some((p, at)) = child_position(interp, *x)? else { return Ok(()) };
        let count = interp.xml_node(p)?.children.len();
        let range: Box<dyn Iterator<Item = usize>> = if axis == Axis::FollowingSibling { Box::new(at + 1..count) } else { Box::new((0..at).rev()) };
        for i in range {
            if let Some(c) = interp.xml_node(p)?.children.get(i).copied() {
                self.add(interp, out, axis, test, XNode::Node(c))?;
            }
        }
        Ok(())
    }

    /// The node the following and preceding axes start from: an attribute's or a namespace
    /// node's element, or the node itself. The flag is true for the first two.
    fn start_of(interp: &Interp, n: &XNode) -> JsResult<Option<(ObjId, bool)>> {
        Ok(match n {
            XNode::Root(_) => None,
            XNode::Ns { owner, .. } => Some((*owner, true)),
            XNode::Node(x) => match interp.xml_node(*x)?.parent {
                Some(p) if interp.xml_kind(*x)? == XmlKind::Attribute => Some((p, true)),
                _ => Some((*x, false)),
            },
        })
    }

    fn following(&self, interp: &mut Interp, out: &mut Nodes, axis: Axis, test: &Test, n: &XNode) -> JsResult<()> {
        let Some((mut cur, owned)) = Self::start_of(interp, n)? else { return Ok(()) };
        if owned {
            self.under(interp, out, axis, test, cur)?;
        }
        while let Some((p, at)) = child_position(interp, cur)? {
            let count = interp.xml_node(p)?.children.len();
            for i in at + 1..count {
                if let Some(s) = interp.xml_node(p)?.children.get(i).copied() {
                    self.subtree(interp, out, axis, test, s)?;
                }
            }
            cur = p;
        }
        Ok(())
    }

    fn preceding(&self, interp: &mut Interp, out: &mut Nodes, axis: Axis, test: &Test, n: &XNode) -> JsResult<()> {
        let Some((mut cur, _)) = Self::start_of(interp, n)? else { return Ok(()) };
        while let Some((p, at)) = child_position(interp, cur)? {
            for i in (0..at).rev() {
                let Some(s) = interp.xml_node(p)?.children.get(i).copied() else { continue };
                let mut part = Nodes::new(interp);
                self.subtree(interp, &mut part, axis, test, s)?;
                for x in part.list.into_iter().rev() {
                    out.push(interp, x)?;
                }
            }
            cur = p;
        }
        Ok(())
    }

    fn attributes(&self, interp: &mut Interp, out: &mut Nodes, axis: Axis, test: &Test, n: &XNode) -> JsResult<()> {
        let XNode::Node(x) = n else { return Ok(()) };
        if interp.xml_kind(*x)? != XmlKind::Element {
            return Ok(());
        }
        let count = interp.xml_node(*x)?.attrs.len();
        for i in 0..count {
            if let Some(a) = interp.xml_node(*x)?.attrs.get(i).copied() {
                self.add(interp, out, axis, test, XNode::Node(a))?;
            }
        }
        Ok(())
    }

    fn namespaces(&self, interp: &mut Interp, out: &mut Nodes, axis: Axis, test: &Test, n: &XNode) -> JsResult<()> {
        let XNode::Node(x) = n else { return Ok(()) };
        if interp.xml_kind(*x)? != XmlKind::Element {
            return Ok(());
        }
        let xml = key("xml");
        let mut at = 0u32;
        let mut has_xml = false;
        let scope = scope_of(interp, Some(*x))?;
        for ns in &scope.list {
            let Some(prefix) = ns.prefix.clone() else { continue };
            if prefix.is_empty() && ns.uri.is_empty() {
                continue;
            }
            has_xml |= prefix == xml;
            self.add(interp, out, axis, test, XNode::Ns { owner: *x, at, prefix, uri: ns.uri.clone() })?;
            at += 1;
        }
        if !has_xml {
            self.add(interp, out, axis, test, XNode::Ns { owner: *x, at, prefix: xml, uri: key(XML_URI) })?;
        }
        Ok(())
    }

    /// The nodes `axis` reaches from `n` that pass `test`, nearest first.
    fn axis(&self, interp: &mut Interp, axis: Axis, test: &Test, n: &XNode) -> JsResult<Nodes> {
        let mut out = Nodes::new(interp);
        match axis {
            Axis::Itself => self.add(interp, &mut out, axis, test, n.clone())?,
            Axis::Child => self.children(interp, &mut out, axis, test, n)?,
            Axis::Descendant => self.descendants(interp, &mut out, axis, test, n)?,
            Axis::DescendantOrSelf => {
                self.add(interp, &mut out, axis, test, n.clone())?;
                self.descendants(interp, &mut out, axis, test, n)?;
            }
            Axis::Parent => {
                if let Some(p) = parent_of(interp, n)? {
                    self.add(interp, &mut out, axis, test, p)?;
                }
            }
            Axis::Ancestor => self.ancestors(interp, &mut out, axis, test, n)?,
            Axis::AncestorOrSelf => {
                self.add(interp, &mut out, axis, test, n.clone())?;
                self.ancestors(interp, &mut out, axis, test, n)?;
            }
            Axis::FollowingSibling | Axis::PrecedingSibling => self.siblings(interp, &mut out, axis, test, n)?,
            Axis::Following => self.following(interp, &mut out, axis, test, n)?,
            Axis::Preceding => self.preceding(interp, &mut out, axis, test, n)?,
            Axis::Attribute => self.attributes(interp, &mut out, axis, test, n)?,
            Axis::Namespace => self.namespaces(interp, &mut out, axis, test, n)?,
        }
        Ok(out)
    }

    // ---- string values and conversions ----

    /// The string-value of a node (XPath 1.0 section 5): the text under an element or the root,
    /// the value of any other node, and a namespace node's URI.
    fn string_value(&mut self, interp: &mut Interp, n: &XNode) -> JsResult<Text> {
        let x = match n {
            XNode::Ns { uri, .. } => return Ok(Text::plain(interp, uri.clone())),
            XNode::Root(t) => *t,
            XNode::Node(x) => *x,
        };
        let kind = interp.xml_kind(x)?;
        if kind == XmlKind::Element {
            return self.text_under(interp, x);
        }
        if matches!(n, XNode::Root(_)) && kind != XmlKind::Text {
            return Ok(Text::plain(interp, empty()));
        }
        let value = interp.xml_node(x)?.value.clone();
        let units = flat_charged(interp, &value)?;
        charge_units(interp, units.len())?;
        Ok(Text::plain(interp, units))
    }

    fn text_under(&mut self, interp: &mut Interp, x: ObjId) -> JsResult<Text> {
        let mut buf = TextBuf::new(interp);
        let mut held = HeldBytes::new(interp);
        let mut stack = Vec::new();
        push_held(interp, &mut held, &mut stack, (x, 0usize))?;
        while let Some(&(p, at)) = stack.last() {
            interp.use_fuel()?;
            let Some(c) = interp.xml_node(p)?.children.get(at).copied() else {
                stack.pop();
                continue;
            };
            if let Some(frame) = stack.last_mut() {
                frame.1 += 1;
            }
            match interp.xml_kind(c)? {
                XmlKind::Text => {
                    let value = interp.xml_node(c)?.value.clone();
                    let units = flat_charged(interp, &value)?;
                    buf.push(interp, &units)?;
                }
                XmlKind::Element => push_held(interp, &mut held, &mut stack, (c, 0))?,
                _ => {}
            }
        }
        Ok(buf.finish())
    }

    fn text_of(&mut self, interp: &mut Interp, v: Val) -> JsResult<Text> {
        match v {
            Val::Set(s) => match s.list.first() {
                Some(n) => self.string_value(interp, n),
                None => Ok(Text::plain(interp, empty())),
            },
            Val::Bool(b) => Ok(Text::plain(interp, key(if b { "true" } else { "false" }))),
            Val::Num(n) => Ok(Text::plain(interp, key(&num_text(n)))),
            Val::Str(t) => {
                // The caller reads the units, so they take fuel each time a value is used.
                charge_units(interp, t.units.len())?;
                Ok(t)
            }
        }
    }

    /// The number a node's string-value stands for.
    fn node_number(&mut self, interp: &mut Interp, n: &XNode) -> JsResult<f64> {
        let t = self.string_value(interp, n)?;
        str_num(interp, &t.units)
    }

    fn number_of(&mut self, interp: &mut Interp, v: Val) -> JsResult<f64> {
        match v {
            Val::Num(n) => Ok(n),
            Val::Bool(b) => Ok(f64::from(u8::from(b))),
            other => {
                let t = self.text_of(interp, other)?;
                str_num(interp, &t.units)
            }
        }
    }

    // ---- comparisons and operators ----

    fn compare(&mut self, interp: &mut Interp, op: Bin, a: Val, b: Val) -> JsResult<bool> {
        match (a, b) {
            (Val::Set(x), Val::Set(y)) => self.compare_sets(interp, op, &x, &y),
            (Val::Set(x), other) => self.compare_set(interp, op, &x, other),
            (other, Val::Set(y)) => self.compare_set(interp, flip(op), &y, other),
            (x, y) => self.compare_values(interp, op, x, y),
        }
    }

    fn compare_values(&mut self, interp: &mut Interp, op: Bin, a: Val, b: Val) -> JsResult<bool> {
        if !matches!(op, Bin::Eq | Bin::Ne) {
            let (x, y) = (self.number_of(interp, a)?, self.number_of(interp, b)?);
            return Ok(compare_numbers(op, x, y));
        }
        let equal = if matches!(a, Val::Bool(_)) || matches!(b, Val::Bool(_)) {
            to_bool(&a) == to_bool(&b)
        } else if matches!(a, Val::Num(_)) || matches!(b, Val::Num(_)) {
            let (x, y) = (self.number_of(interp, a)?, self.number_of(interp, b)?);
            return Ok(compare_numbers(op, x, y));
        } else {
            self.text_of(interp, a)?.units == self.text_of(interp, b)?.units
        };
        Ok(equal == (op == Bin::Eq))
    }

    /// Compares each node of `set` with `other`, which is not a node-set; `set` is on the left.
    fn compare_set(&mut self, interp: &mut Interp, op: Bin, set: &Nodes, other: Val) -> JsResult<bool> {
        if let Val::Str(t) = &other {
            charge_units(interp, t.units.len())?;
        }
        let n = match other {
            Val::Bool(b) => return self.compare_values(interp, op, Val::Bool(!set.list.is_empty()), Val::Bool(b)),
            Val::Str(t) if matches!(op, Bin::Eq | Bin::Ne) => {
                for node in &set.list {
                    if (self.string_value(interp, node)?.units == t.units) == (op == Bin::Eq) {
                        return Ok(true);
                    }
                }
                return Ok(false);
            }
            Val::Str(t) => str_num(interp, &t.units)?,
            Val::Num(n) => n,
            Val::Set(_) => return Err(internal()),
        };
        for node in &set.list {
            let v = self.node_number(interp, node)?;
            if compare_numbers(op, v, n) {
                return Ok(true);
            }
        }
        Ok(false)
    }

    fn strings_of(&mut self, interp: &mut Interp, held: &mut HeldBytes, set: &Nodes) -> JsResult<HashSet<Key>> {
        let mut out = HashSet::new();
        for node in &set.list {
            let t = self.string_value(interp, node)?;
            held.add(interp, ENTRY_BYTES.saturating_add(t.units.len().saturating_mul(2)))?;
            out.insert(t.units);
        }
        Ok(out)
    }

    /// The smallest and largest numbers the nodes' string-values stand for, leaving out NaN.
    fn number_range(&mut self, interp: &mut Interp, set: &Nodes) -> JsResult<Option<(f64, f64)>> {
        let mut range: Option<(f64, f64)> = None;
        for node in &set.list {
            let v = self.node_number(interp, node)?;
            if !v.is_nan() {
                range = Some(range.map_or((v, v), |(lo, hi)| (lo.min(v), hi.max(v))));
            }
        }
        Ok(range)
    }

    fn compare_sets(&mut self, interp: &mut Interp, op: Bin, a: &Nodes, b: &Nodes) -> JsResult<bool> {
        if a.list.is_empty() || b.list.is_empty() {
            return Ok(false);
        }
        if matches!(op, Bin::Eq | Bin::Ne) {
            let mut held = HeldBytes::new(interp);
            let right = self.strings_of(interp, &mut held, b)?;
            for node in &a.list {
                let s = self.string_value(interp, node)?;
                let found = if op == Bin::Eq { right.contains(&s.units) } else { right.len() > 1 || !right.contains(&s.units) };
                if found {
                    return Ok(true);
                }
            }
            return Ok(false);
        }
        let (Some((a_lo, a_hi)), Some((b_lo, b_hi))) = (self.number_range(interp, a)?, self.number_range(interp, b)?) else { return Ok(false) };
        Ok(match op {
            Bin::Lt | Bin::Le => compare_numbers(op, a_lo, b_hi),
            _ => compare_numbers(op, a_hi, b_lo),
        })
    }

    fn binary(&mut self, interp: &mut Interp, op: Bin, a: Val, b: Val) -> JsResult<Val> {
        match op {
            Bin::Union => {
                let (Val::Set(mut x), Val::Set(y)) = (a, b) else {
                    return Err(interp.type_error("both sides of an XPath | must select nodes"));
                };
                if x.list.is_empty() {
                    return Ok(Val::Set(y));
                }
                for n in y.list {
                    x.push(interp, n)?;
                }
                Ok(Val::Set(self.sort(interp, x)?))
            }
            Bin::Add | Bin::Sub | Bin::Mul | Bin::Div | Bin::Mod => {
                let (x, y) = (self.number_of(interp, a)?, self.number_of(interp, b)?);
                Ok(Val::Num(match op {
                    Bin::Add => x + y,
                    Bin::Sub => x - y,
                    Bin::Mul => x * y,
                    Bin::Div => x / y,
                    _ => x % y,
                }))
            }
            Bin::Or | Bin::And => Err(internal()),
            _ => Ok(Val::Bool(self.compare(interp, op, a, b)?)),
        }
    }

    // ---- functions ----

    fn set_arg(interp: &mut Interp, v: Option<Val>, name: &str) -> JsResult<Nodes> {
        match v {
            Some(Val::Set(s)) => Ok(s),
            _ => Err(interp.type_error(&format!("the XPath function {name} needs a node-set"))),
        }
    }

    fn text_arg(&mut self, interp: &mut Interp, v: Option<Val>, ctx: &Ctx) -> JsResult<Text> {
        match v {
            Some(v) => self.text_of(interp, v),
            None => self.string_value(interp, &ctx.node),
        }
    }

    fn number_arg(&mut self, interp: &mut Interp, v: Option<Val>) -> JsResult<f64> {
        let v = v.ok_or_else(internal)?;
        self.number_of(interp, v)
    }

    fn call(&mut self, interp: &mut Interp, f: Func, args: Vec<Val>, ctx: &Ctx) -> JsResult<Val> {
        let mut args = args.into_iter();
        Ok(match f {
            Func::Last => Val::Num(ctx.size as f64),
            Func::Position => Val::Num(ctx.pos as f64),
            Func::Count => Val::Num(Self::set_arg(interp, args.next(), "count")?.list.len() as f64),
            Func::Id => Val::Set(Nodes::new(interp)),
            Func::LocalName | Func::NamespaceUri | Func::Name => Val::Str(self.name_function(interp, f, args.next(), ctx)?),
            Func::Sum => {
                let set = Self::set_arg(interp, args.next(), "sum")?;
                let mut total = 0.0;
                for n in &set.list {
                    total += self.node_number(interp, n)?;
                }
                Val::Num(total)
            }
            Func::Boolean => Val::Bool(to_bool(&args.next().ok_or_else(internal)?)),
            Func::Not => Val::Bool(!to_bool(&args.next().ok_or_else(internal)?)),
            Func::True => Val::Bool(true),
            Func::False => Val::Bool(false),
            Func::Lang => {
                let wanted = self.text_arg(interp, args.next(), ctx)?;
                Val::Bool(self.lang(interp, &ctx.node, &wanted.units)?)
            }
            Func::Number => match args.next() {
                Some(v) => Val::Num(self.number_of(interp, v)?),
                None => Val::Num(self.node_number(interp, &ctx.node)?),
            },
            Func::Floor => Val::Num(self.number_arg(interp, args.next())?.floor()),
            Func::Ceiling => Val::Num(self.number_arg(interp, args.next())?.ceil()),
            Func::Round => Val::Num(round(self.number_arg(interp, args.next())?)),
            _ => return self.string_function(interp, f, args.collect(), ctx),
        })
    }

    fn string_function(&mut self, interp: &mut Interp, f: Func, args: Vec<Val>, ctx: &Ctx) -> JsResult<Val> {
        let mut texts = Vec::new();
        let mut held = HeldBytes::new(interp);
        for v in args {
            let t = self.text_of(interp, v)?;
            push_held(interp, &mut held, &mut texts, t)?;
        }
        if texts.is_empty() && matches!(f, Func::String | Func::StringLength | Func::NormalizeSpace) {
            texts.push(self.string_value(interp, &ctx.node)?);
        }
        if f == Func::String {
            return Ok(Val::Str(texts.into_iter().next().ok_or_else(internal)?));
        }
        let units = |at: usize| texts.get(at).map(|t| &*t.units).unwrap_or_default();
        Ok(match f {
            Func::StringLength => Val::Num(char::decode_utf16(units(0).iter().copied()).count() as f64),
            Func::StartsWith => Val::Bool(units(0).starts_with(units(1))),
            Func::Contains => Val::Bool(find(interp, units(0), units(1))?.is_some()),
            Func::SubstringBefore => {
                let at = find(interp, units(0), units(1))?;
                Val::Str(self.slice(interp, at.and_then(|i| units(0).get(..i)).unwrap_or_default())?)
            }
            Func::SubstringAfter => {
                let at = find(interp, units(0), units(1))?;
                Val::Str(self.slice(interp, at.and_then(|i| units(0).get(i + units(1).len()..)).unwrap_or_default())?)
            }
            Func::Concat => {
                let mut buf = TextBuf::new(interp);
                for t in &texts {
                    buf.push(interp, &t.units)?;
                }
                Val::Str(buf.finish())
            }
            Func::NormalizeSpace => Val::Str(normalize_space(interp, units(0))?),
            Func::Translate => Val::Str(translate(interp, units(0), units(1), units(2))?),
            _ => return Err(internal()),
        })
    }

    fn slice(&mut self, interp: &mut Interp, units: &[u16]) -> JsResult<Text> {
        let mut buf = TextBuf::new(interp);
        buf.push(interp, units)?;
        Ok(buf.finish())
    }

    fn substring(&mut self, interp: &mut Interp, args: Vec<Val>) -> JsResult<Val> {
        let mut args = args.into_iter();
        let text = self.text_of(interp, args.next().ok_or_else(internal)?)?;
        let start = round(self.number_arg(interp, args.next())?);
        let end = match args.next() {
            Some(len) => start + round(self.number_of(interp, len)?),
            None => f64::INFINITY,
        };
        charge_units(interp, text.units.len())?;
        let mut held = HeldBytes::new(interp);
        // The code points take 4 bytes each, and the result up to twice its 2-byte units.
        held.add(interp, text.units.len().saturating_mul(8))?;
        let mut out = Vec::new();
        for (i, p) in code_points(&text.units).into_iter().enumerate() {
            let position = (i + 1) as f64;
            if position >= start && position < end {
                push_point(&mut out, p);
            }
        }
        Ok(Val::Str(Text { units: Rc::from(out), _held: held }))
    }

    fn name_function(&mut self, interp: &mut Interp, f: Func, arg: Option<Val>, ctx: &Ctx) -> JsResult<Text> {
        let node = match arg {
            None => Some(ctx.node.clone()),
            Some(Val::Set(s)) => s.list.into_iter().next(),
            Some(_) => return Err(interp.type_error("the XPath name functions need a node-set")),
        };
        let units = match node {
            None | Some(XNode::Root(_)) => empty(),
            Some(XNode::Ns { prefix, .. }) => {
                if f == Func::NamespaceUri {
                    empty()
                } else {
                    prefix
                }
            }
            Some(XNode::Node(x)) => return node_name(interp, f, x),
        };
        Ok(Text::plain(interp, units))
    }

    /// Whether the context node's language, from the nearest `xml:lang` attribute on it or an
    /// ancestor, is `wanted` or a sublanguage of it, ignoring case.
    fn lang(&mut self, interp: &mut Interp, n: &XNode, wanted: &[u16]) -> JsResult<bool> {
        let mut cur = match n {
            XNode::Root(_) => None,
            XNode::Node(x) => Some(*x),
            XNode::Ns { owner, .. } => Some(*owner),
        };
        let xml = key(XML_URI);
        while let Some(x) = cur {
            interp.use_fuel()?;
            let node = interp.xml_node(x)?;
            let parent = node.parent;
            let count = node.attrs.len();
            for i in 0..count {
                interp.use_fuel()?;
                let Some(a) = interp.xml_node(x)?.attrs.get(i).copied() else { break };
                let attr = interp.xml_node(a)?;
                if attr.name.as_ref().is_some_and(|q| name_uri(q) == &*xml && units_are(&q.local, "lang")) {
                    let value = attr.value.clone();
                    let value = flat_charged(interp, &value)?;
                    let head = value.get(..wanted.len()).unwrap_or_default();
                    return Ok(same_ignoring_case(head, wanted) && (value.len() == wanted.len() || value.get(wanted.len()) == Some(&DASH)));
                }
            }
            cur = parent;
        }
        Ok(false)
    }

    // ---- running ----

    fn task(&mut self, interp: &mut Interp, t: Task) -> JsResult<()> {
        push_held(interp, &mut self.held, &mut self.tasks, t)
    }

    fn val(&mut self, interp: &mut Interp, v: Val) -> JsResult<()> {
        push_held(interp, &mut self.held, &mut self.vals, v)
    }

    fn pop(&mut self) -> JsResult<Val> {
        self.vals.pop().ok_or_else(internal)
    }

    fn root_of(interp: &mut Interp, n: &XNode) -> JsResult<XNode> {
        Ok(match n {
            XNode::Root(t) => XNode::Root(*t),
            XNode::Node(x) => XNode::Root(top_of(interp, *x)?),
            XNode::Ns { owner, .. } => XNode::Root(top_of(interp, *owner)?),
        })
    }

    fn bound_value(&mut self, interp: &mut Interp, at: usize) -> JsResult<Val> {
        Ok(match self.bound.get(at).ok_or_else(internal)? {
            Bound::Bool(b) => Val::Bool(*b),
            Bound::Num(n) => Val::Num(*n),
            Bound::Str(s) => Val::Str(Text::plain(interp, s.clone())),
            Bound::Set(list) => {
                let list = list.clone();
                let mut nodes = Nodes::new(interp);
                nodes.held.add(interp, list.len().saturating_mul(size_of::<XNode>()))?;
                nodes.list = list;
                Val::Set(nodes)
            }
        })
    }

    fn eval(&mut self, interp: &mut Interp, e: usize, ctx: Ctx) -> JsResult<()> {
        let parsed = self.parsed;
        match parsed.exprs.get(e).ok_or_else(internal)? {
            Expr::Num(n) => self.val(interp, Val::Num(*n)),
            Expr::Lit(s) => {
                let t = Text::plain(interp, s.clone());
                self.val(interp, Val::Str(t))
            }
            Expr::Var(at) => {
                let v = self.bound_value(interp, *at)?;
                self.val(interp, v)
            }
            Expr::Neg(a) => {
                self.task(interp, Task::Neg)?;
                self.task(interp, Task::Eval(*a, ctx))
            }
            Expr::Bin(op @ (Bin::And | Bin::Or), a, b) => {
                self.task(interp, Task::Logic { and: *op == Bin::And, rhs: *b, ctx: ctx.clone() })?;
                self.task(interp, Task::Eval(*a, ctx))
            }
            Expr::Bin(op, a, b) => {
                self.task(interp, Task::Bin(*op))?;
                self.task(interp, Task::Eval(*b, ctx.clone()))?;
                self.task(interp, Task::Eval(*a, ctx))
            }
            Expr::Call(f, args) => {
                self.task(interp, Task::Call(*f, args.len(), ctx.clone()))?;
                for a in args.iter().rev() {
                    self.task(interp, Task::Eval(*a, ctx.clone()))?;
                }
                Ok(())
            }
            Expr::Path { filter: Some((primary, _)), .. } => {
                self.task(interp, Task::PathStart(e))?;
                self.task(interp, Task::Eval(*primary, ctx))
            }
            Expr::Path { filter: None, absolute, steps } => {
                let start = if *absolute { Self::root_of(interp, &ctx.node)? } else { ctx.node };
                let mut inputs = Nodes::new(interp);
                inputs.push(interp, start)?;
                if steps.is_empty() {
                    return self.val(interp, Val::Set(inputs));
                }
                let first = self.step_axis(interp, e, 1, &inputs.list.first().cloned().ok_or_else(internal)?)?;
                let run = self.new_run(interp, e, 1, inputs, first);
                self.run_path(interp, Box::new(run))
            }
        }
    }

    fn new_run(&self, interp: &Interp, path: usize, stage: usize, inputs: Nodes, cur: Nodes) -> PathRun {
        PathRun {
            path,
            stage,
            inputs,
            ci: 0,
            cur,
            pred: 0,
            at: 0,
            kept: Nodes::new(interp),
            waiting: false,
            out: Nodes::new(interp),
            seen: HashSet::new(),
            seen_held: HeldBytes::new(interp),
        }
    }

    fn step(&mut self, interp: &mut Interp, t: Task) -> JsResult<()> {
        match t {
            Task::Eval(e, ctx) => self.eval(interp, e, ctx),
            Task::Bin(op) => {
                let b = self.pop()?;
                let a = self.pop()?;
                let v = self.binary(interp, op, a, b)?;
                self.val(interp, v)
            }
            Task::Neg => {
                let a = self.pop()?;
                let n = self.number_of(interp, a)?;
                self.val(interp, Val::Num(-n))
            }
            Task::Logic { and, rhs, ctx } => {
                let left = to_bool(&self.pop()?);
                if left != and {
                    return self.val(interp, Val::Bool(left));
                }
                self.task(interp, Task::Bool)?;
                self.task(interp, Task::Eval(rhs, ctx))
            }
            Task::Bool => {
                let v = to_bool(&self.pop()?);
                self.val(interp, Val::Bool(v))
            }
            Task::Call(f, n, ctx) => {
                let args = self.vals.split_off(self.vals.len().checked_sub(n).ok_or_else(internal)?);
                let v = if f == Func::Substring { self.substring(interp, args)? } else { self.call(interp, f, args, &ctx)? };
                self.val(interp, v)
            }
            Task::PathStart(e) => {
                let Val::Set(set) = self.pop()? else {
                    return Err(interp.type_error("an XPath predicate or step follows a value that is not a node-set"));
                };
                let run = self.new_run(interp, e, 0, Nodes::new(interp), set);
                self.run_path(interp, Box::new(run))
            }
            Task::Path(run) => self.run_path(interp, run),
        }
    }

    /// The predicates of a path's stage, and its step for a stage after the filter's.
    fn stage_of(&self, path: usize, stage: usize) -> JsResult<(&'p [usize], Option<&'p Step>)> {
        let parsed = self.parsed;
        let Some(Expr::Path { filter, steps, .. }) = parsed.exprs.get(path) else { return Err(internal()) };
        match stage.checked_sub(1) {
            None => Ok((filter.as_ref().map(|(_, p)| p.as_slice()).unwrap_or_default(), None)),
            Some(s) => {
                let step = steps.get(s).ok_or_else(internal)?;
                Ok((&step.preds, Some(step)))
            }
        }
    }

    fn step_axis(&self, interp: &mut Interp, path: usize, stage: usize, n: &XNode) -> JsResult<Nodes> {
        let (_, step) = self.stage_of(path, stage)?;
        let step = step.ok_or_else(internal)?;
        self.axis(interp, step.axis, &step.test, n)
    }

    /// Runs a path until a predicate needs evaluating, which it schedules before itself, or until
    /// the path's node-set is complete, which it pushes.
    fn run_path(&mut self, interp: &mut Interp, mut r: Box<PathRun>) -> JsResult<()> {
        loop {
            interp.use_fuel()?;
            if r.waiting {
                r.waiting = false;
                let v = self.pop()?;
                let keep = match v {
                    Val::Num(n) => n == (r.at + 1) as f64,
                    other => to_bool(&other),
                };
                if keep && let Some(n) = r.cur.list.get(r.at).cloned() {
                    r.kept.push(interp, n)?;
                }
                r.at += 1;
            }
            let (preds, _) = self.stage_of(r.path, r.stage)?;
            if let Some(&pred) = preds.get(r.pred) {
                if let Some(node) = r.cur.list.get(r.at).cloned() {
                    let ctx = Ctx { node, pos: r.at + 1, size: r.cur.list.len() };
                    r.waiting = true;
                    self.task(interp, Task::Path(r))?;
                    return self.task(interp, Task::Eval(pred, ctx));
                }
                r.cur = replace(&mut r.kept, Nodes::new(interp));
                r.pred += 1;
                r.at = 0;
                continue;
            }
            if !self.next_context(interp, &mut r)? {
                return Ok(());
            }
        }
    }

    /// Adds the current context's nodes to the stage's result and moves to the next context or
    /// stage. Returns false when the path is complete and its node-set has been pushed.
    fn next_context(&mut self, interp: &mut Interp, r: &mut PathRun) -> JsResult<bool> {
        let cur = replace(&mut r.cur, Nodes::new(interp));
        if r.inputs.list.len() > 1 {
            for n in cur.list {
                if !r.seen.contains(&n) {
                    r.seen_held.add(interp, ENTRY_BYTES)?;
                    r.seen.insert(n.clone());
                    r.out.push(interp, n)?;
                }
            }
        } else {
            r.out = cur;
        }
        r.ci += 1;
        if let Some(n) = r.inputs.list.get(r.ci).cloned() {
            r.cur = self.step_axis(interp, r.path, r.stage, &n)?;
            r.pred = 0;
            r.at = 0;
            return Ok(true);
        }
        let out = replace(&mut r.out, Nodes::new(interp));
        let (_, step) = self.stage_of(r.path, r.stage)?;
        let done = if r.inputs.list.len() > 1 {
            self.sort(interp, out)?
        } else if step.is_some_and(|s| s.axis.reverse()) {
            let mut out = out;
            out.list.reverse();
            out
        } else {
            out
        };
        r.seen.clear();
        r.seen_held = HeldBytes::new(interp);
        r.stage += 1;
        let more = self.stage_of(r.path, r.stage).is_ok();
        let Some(first) = done.list.first().cloned().filter(|_| more) else {
            self.val(interp, Val::Set(done))?;
            return Ok(false);
        };
        r.inputs = done;
        r.ci = 0;
        r.cur = self.step_axis(interp, r.path, r.stage, &first)?;
        r.pred = 0;
        r.at = 0;
        Ok(true)
    }

    fn run(&mut self, interp: &mut Interp, e: usize, ctx: Ctx) -> JsResult<Val> {
        self.tasks.clear();
        self.vals.clear();
        self.task(interp, Task::Eval(e, ctx))?;
        while let Some(t) = self.tasks.pop() {
            interp.use_fuel()?;
            self.step(interp, t)?;
        }
        let v = self.pop()?;
        if !self.vals.is_empty() {
            return Err(internal());
        }
        Ok(v)
    }

    /// Binds the expression's prefixes to the namespaces in scope on `x`.
    fn resolve_prefixes(&mut self, interp: &mut Interp, x: ObjId) -> JsResult<()> {
        self.uris.clear();
        if self.parsed.prefixes.is_empty() {
            return Ok(());
        }
        let scope = scope_of(interp, Some(x))?;
        let parsed = self.parsed;
        for p in &parsed.prefixes {
            let uri = if units_are(p, "xml") {
                key(XML_URI)
            } else {
                match scope.list.iter().find(|ns| ns.prefix.as_ref() == Some(p)) {
                    Some(ns) if !ns.uri.is_empty() => ns.uri.clone(),
                    _ => {
                        let shown = String::from_utf16_lossy(p);
                        return Err(interp.type_error(&format!("the XPath prefix {shown} is not bound to a namespace")));
                    }
                }
            };
            self.held.add(interp, ENTRY_BYTES)?;
            self.uris.insert(p.clone(), uri);
        }
        Ok(())
    }

    /// The nodes the expression selects with `x` as the context node.
    fn select(&mut self, interp: &mut Interp, x: ObjId) -> JsResult<Vec<ObjId>> {
        self.resolve_prefixes(interp, x)?;
        let root = self.parsed.root;
        let Val::Set(set) = self.run(interp, root, Ctx { node: XNode::Node(x), pos: 1, size: 1 })? else {
            return Err(interp.type_error("the XPath expression does not evaluate to a node-set"));
        };
        let mut out = Vec::new();
        let mut held = HeldBytes::new(interp);
        for n in set.list {
            match n {
                XNode::Node(id) => push_held(interp, &mut held, &mut out, id)?,
                XNode::Root(_) => return Err(interp.type_error("the XPath expression selects the root node, which is not an XML value")),
                XNode::Ns { .. } => return Err(interp.type_error("the XPath expression selects a namespace node, which is not an XML value")),
            }
        }
        Ok(out)
    }
}

fn node_name(interp: &mut Interp, f: Func, x: ObjId) -> JsResult<Text> {
    let node = interp.xml_node(x)?;
    let (kind, parent) = (node.kind, node.parent);
    let Some(name) = node.name.clone() else { return Ok(Text::plain(interp, empty())) };
    let units = match (f, kind) {
        (_, XmlKind::Text | XmlKind::Comment) => empty(),
        (Func::NamespaceUri, XmlKind::Pi) => empty(),
        (Func::NamespaceUri, _) => Rc::from(name_uri(&name)),
        (Func::LocalName, _) | (_, XmlKind::Pi) => name.local,
        _ => return qualified_name(interp, x, parent, &name, kind == XmlKind::Attribute),
    };
    Ok(Text::plain(interp, units))
}

/// An element's or attribute's name as a QName, with a prefix declared for its namespace. The units
/// of a prefixed name are held against the heap limit while the text lives.
fn qualified_name(interp: &mut Interp, x: ObjId, parent: Option<ObjId>, name: &XmlName, attribute: bool) -> JsResult<Text> {
    let uri = name_uri(name);
    if uri.is_empty() {
        return Ok(Text::plain(interp, name.local.clone()));
    }
    let prefix = if units_are(uri, XML_URI) {
        key("xml")
    } else {
        match &name.prefix {
            Some(p) if !(attribute && p.is_empty()) => p.clone(),
            _ => {
                let scope = scope_of(interp, if attribute { parent } else { Some(x) })?;
                let usable = |ns: &XmlNs| *ns.uri == *uri && ns.prefix.as_ref().is_some_and(|p| !(attribute && p.is_empty()));
                scope.list.iter().find(|ns| usable(ns)).and_then(|ns| ns.prefix.clone()).unwrap_or_else(empty)
            }
        }
    };
    if prefix.is_empty() {
        return Ok(Text::plain(interp, name.local.clone()));
    }
    let mut buf = TextBuf::new(interp);
    buf.push(interp, &prefix)?;
    buf.push(interp, &[COLON])?;
    buf.push(interp, &name.local)?;
    Ok(buf.finish())
}

/// The first index where `needle` occurs in `hay`. Every position tried takes fuel.
fn find(interp: &mut Interp, hay: &[u16], needle: &[u16]) -> JsResult<Option<usize>> {
    string_builtins::find(interp, hay, needle, 0)
}

fn normalize_space(interp: &mut Interp, units: &[u16]) -> JsResult<Text> {
    let mut buf = TextBuf::new(interp);
    for word in units.split(|&c| is_xml_space(c)).filter(|w| !w.is_empty()) {
        if !buf.units.is_empty() {
            buf.push(interp, &[0x20])?;
        }
        buf.push(interp, word)?;
    }
    Ok(buf.finish())
}

fn translate(interp: &mut Interp, units: &[u16], from: &[u16], to: &[u16]) -> JsResult<Text> {
    charge_units(interp, units.len() + from.len() + to.len())?;
    let mut held = HeldBytes::new(interp);
    held.add(interp, from.len().saturating_add(units.len()).saturating_add(to.len()).saturating_mul(ENTRY_BYTES))?;
    let to = code_points(to);
    let mut map: HashMap<u32, Option<u32>> = HashMap::new();
    for (i, p) in code_points(from).into_iter().enumerate() {
        map.entry(p).or_insert_with(|| to.get(i).copied());
    }
    let mut out = Vec::new();
    for p in code_points(units) {
        match map.get(&p) {
            Some(Some(t)) => push_point(&mut out, *t),
            Some(None) => {}
            None => push_point(&mut out, p),
        }
    }
    Ok(Text { units: Rc::from(out), _held: held })
}

/// Reads the variables the expression names from `variables`.
fn bind(interp: &mut Interp, held: &mut HeldBytes, parsed: &Parsed, variables: &Value) -> JsResult<Vec<Bound>> {
    let mut out = Vec::new();
    for name in &parsed.vars {
        let v = match variables {
            Value::Object(o) if interp.has_property(*o, name)? => interp.get_from(*o, name, variables)?,
            _ => Value::Undefined,
        };
        if matches!(v, Value::Undefined) {
            let shown = String::from_utf16_lossy(name);
            return Err(interp.type_error(&format!("the XPath variable ${shown} is not bound")));
        }
        interp.temp_roots.push(v.clone());
        let b = match (interp.classify(&v), &v) {
            (Xv::Node(n), _) => Bound::Set(vec![XNode::Node(n)]),
            (Xv::List(l), _) => {
                // A later getter may change the list, so its items are held as roots themselves.
                let count = interp.xml_list(l)?.items.len();
                held.add(interp, count.saturating_mul(size_of::<ObjId>() + size_of::<XNode>() + size_of::<Value>()))?;
                let items = interp.xml_list(l)?.items.clone();
                interp.temp_roots.extend(items.iter().map(|&n| Value::Object(n)));
                Bound::Set(items.into_iter().map(XNode::Node).collect())
            }
            (Xv::Other, Value::Bool(b)) => Bound::Bool(*b),
            (Xv::Other, Value::Number(n)) => Bound::Num(*n),
            (Xv::Other, _) => {
                let s = interp.to_str(&v)?;
                Bound::Str(flat_charged(interp, &s)?)
            }
        };
        push_held(interp, held, &mut out, b)?;
    }
    Ok(out)
}

/// The nodes an expression runs on: the XML value itself, or each element of an XMLList.
fn contexts(interp: &mut Interp, held: &mut HeldBytes, this: &Value) -> JsResult<Vec<ObjId>> {
    match interp.classify(this) {
        Xv::Node(n) => Ok(vec![n]),
        Xv::List(l) => {
            let count = interp.xml_list(l)?.items.len();
            let mut out = Vec::new();
            for i in 0..count {
                interp.use_fuel()?;
                let Some(item) = interp.xml_list(l)?.items.get(i).copied() else { break };
                if interp.xml_kind(item)? == XmlKind::Element {
                    push_held(interp, held, &mut out, item)?;
                }
            }
            Ok(out)
        }
        Xv::Other => Err(interp.type_error("the method needs an XML value")),
    }
}

/// `xpath(expression[, variables])`: the nodes the XPath 1.0 `expression` selects with this XML
/// value as the context node, or, for an XMLList, with each of its elements in turn, as one
/// XMLList. Each property of `variables` binds the variable of its name.
pub(crate) fn xpath(interp: &mut Interp, this: Value, args: &[Value], _: bool) -> JsResult<Value> {
    if matches!(interp.classify(&this), Xv::Other) {
        return Err(interp.type_error("the method needs an XML value"));
    }
    let Value::String(source) = arg(args, 0) else {
        return Err(interp.type_error("xpath needs the expression as a string"));
    };
    let variables = arg(args, 1);
    if !matches!(variables, Value::Undefined | Value::Object(_)) {
        return Err(interp.type_error("xpath needs its variables as an object"));
    }
    interp.rooted(&[this.clone(), variables.clone()], |i| {
        let units = flat_charged(i, &source)?;
        let parsed = parse(i, &units)?;
        let mut held = HeldBytes::new(i);
        let bound = bind(i, &mut held, &parsed, &variables)?;
        let items = contexts(i, &mut held, &this)?;
        let out = i.new_xml_list(None, None)?;
        i.xml_keep(out);
        let mut ev = Ev::new(i, &parsed, bound)?;
        for item in items {
            for id in ev.select(i, item)? {
                i.list_push(out, id)?;
            }
        }
        Ok(Value::Object(out))
    })
}