use std::borrow::Cow;
use std::cmp::Ordering;
use std::collections::{HashMap, HashSet};
use std::hash::BuildHasher;
use std::ops::{Deref, DerefMut};
use std::sync::Arc;
use icu_collator::preferences::CollationCaseFirst;
use icu_collator::{Collator, CollatorBorrowed, CollatorPreferences, options::CollatorOptions};
use icu_locale::Locale;
use super::budget::{
EXECUTION_RECURSION_DEPTH_CEILING, Meter, append_metered_string, reconcile_replacement_growth,
reserve_metered_string, reserve_retained_hash_map_slot, reserve_retained_hash_set_slot,
reserve_retained_vec_slot, reserve_temporary_vec_slot,
};
use super::compiler::{
AttributeSet, AttributeValueTemplate, AvtPart, Expression, ExsltFunction, Instruction,
InstructionSequence, NameTest, NamespaceAlias, Sort, Stylesheet, Template, Variable,
};
use super::lexical::{
is_ncname, is_xml_whitespace, trim_xml_whitespace, unicode_decimal_value, xpath_string_literal,
};
use super::serializer::{serialize, serialize_fragment};
use super::xpath::{
CustomCallSession, EXSLT_COMMON_NS, Evaluator, EvaluatorSourceOptions, PreparedEvaluatorSource,
SourceNode, XPathValue, parse_xpath_number, prepare_evaluator_source, xpath_number,
};
use super::{
Attribute, BudgetKind, Document, Error, ExecutionBudget, ExecutionEnvironment, ExecutionUsage,
ExpandedName, Namespace, NodeId, NodeKind, NodeReference, OutputDefinition, Reported, Resolver,
Result, SerializedOutput, Value,
};
pub type Parameters = HashMap<ExpandedName, Value>;
struct SourceParameterRemap {
mapping: Option<HashMap<NodeId, NodeId>>,
owned_bytes: usize,
}
struct PreparedParameters<'a> {
effective_globals: HashMap<ExpandedName, &'a super::compiler::GlobalVariable>,
source_remap: SourceParameterRemap,
}
struct AttributeSetExpansion<'a> {
declarations: &'a [AttributeSet],
active: Vec<&'a ExpandedName>,
reserved_owned_bytes: usize,
}
impl<'a> AttributeSetExpansion<'a> {
const fn new(declarations: &'a [AttributeSet]) -> Self {
Self {
declarations,
active: Vec::new(),
reserved_owned_bytes: 0,
}
}
fn push(&mut self, name: &'a ExpandedName, meter: &mut Meter) -> Result<()> {
if self.active.contains(&name) {
return Err(Error::Static("attribute-set cycle".into()));
}
meter.recursion_with_ceiling(
self.active.len().saturating_add(1),
EXECUTION_RECURSION_DEPTH_CEILING,
)?;
reserve_temporary_vec_slot(&mut self.active, meter, &mut self.reserved_owned_bytes)?;
self.active.push(name);
Ok(())
}
}
fn select_attribute_set_declarations<'a>(
declarations: &'a [AttributeSet],
name: &ExpandedName,
meter: &mut Meter,
) -> Result<(Vec<&'a AttributeSet>, usize)> {
let mut selected = Vec::new();
let mut reserved_owned_bytes = 0usize;
let result = (|| {
for declaration in declarations.iter().filter(|set| &set.name == name) {
reserve_temporary_vec_slot(&mut selected, meter, &mut reserved_owned_bytes)?;
selected.push(declaration);
}
if selected.is_empty() {
return Err(Error::Static(format!(
"undefined attribute-set {}",
name.local
)));
}
selected.sort_unstable_by_key(|set| (std::cmp::Reverse(set.precedence), set.order));
Ok(())
})();
if let Err(error) = result {
drop(selected);
meter.release_owned_bytes(reserved_owned_bytes);
return Err(error);
}
Ok((selected, reserved_owned_bytes))
}
#[derive(Clone, Copy)]
enum CopyDocument<'a> {
Source,
Fragment(&'a Document),
}
#[derive(Clone, Copy)]
struct PendingCopyNode {
source: NodeId,
target_parent: NodeId,
depth: usize,
use_instruction_base: bool,
}
#[derive(Debug, Clone)]
pub struct ExecutionOptions {
pub budget: ExecutionBudget,
pub initial_mode: Option<ExpandedName>,
pub initial_template: Option<ExpandedName>,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Message {
pub content: String,
pub terminate: bool,
}
#[derive(Debug, Clone)]
pub struct TransformResult {
pub document: Document,
pub serialized: SerializedOutput,
pub secondary_outputs: Vec<SecondaryOutput>,
pub messages: Vec<Message>,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct SecondaryOutput {
pub uri: Arc<String>,
pub serialized: SerializedOutput,
}
impl Stylesheet {
pub fn execute<R: Resolver + 'static>(
&self,
source: &Document,
parameters: &Parameters,
resolver: Arc<R>,
options: ExecutionOptions,
) -> Result<TransformResult> {
self.execute_with_environment(
source,
parameters,
ExecutionEnvironment::new(resolver),
options,
)
}
pub fn execute_with_environment<R: Resolver + 'static>(
&self,
source: &Document,
parameters: &Parameters,
environment: ExecutionEnvironment<R>,
options: ExecutionOptions,
) -> Result<TransformResult> {
self.execute_reported(source, parameters, environment, options)
.outcome
}
pub fn execute_reported<R: Resolver + 'static>(
&self,
source: &Document,
parameters: &Parameters,
environment: ExecutionEnvironment<R>,
options: ExecutionOptions,
) -> Reported<TransformResult, ExecutionUsage> {
let mut meter = match Meter::new(options.budget, source.source_bytes()) {
Ok(meter) => meter.with_work_ceiling(environment.work_ceiling),
Err(error) => {
return Reported {
outcome: Err(error),
usage: ExecutionUsage::default(),
};
}
};
let prepared = self.prepare_execution(source, parameters, &environment, &mut meter);
let (prepared, prepared_parameters, source_options) = match prepared {
Ok(prepared) => prepared,
Err(error) => {
return Reported {
outcome: Err(error),
usage: meter.admitted_work(),
};
}
};
let mut state = match Execution::start(
self,
prepared,
parameters,
prepared_parameters,
environment,
meter,
source_options,
) {
Ok(state) => state,
Err(failure) => {
let (error, usage) = *failure;
return Reported {
outcome: Err(error),
usage,
};
}
};
let serialized = state.run(&options, &self.output);
let usage = state.meter.admitted_work();
Reported {
outcome: serialized.map(|serialized| TransformResult {
document: state.result,
serialized,
secondary_outputs: state.secondary_outputs,
messages: state.messages,
}),
usage,
}
}
fn prepare_execution<'s, R: Resolver + 'static>(
&'s self,
source: &Document,
parameters: &Parameters,
environment: &ExecutionEnvironment<R>,
meter: &mut Meter,
) -> Result<(
PreparedEvaluatorSource,
PreparedParameters<'s>,
EvaluatorSourceOptions,
)> {
for identity in self.resource_identities() {
environment
.resolver
.authorize(super::ResourceAccess::Dependency(identity))?;
}
let effective_globals = effective_globals(self, meter)?;
for (name, value) in parameters {
if effective_globals
.get(name)
.is_some_and(|global| global.is_parameter)
{
validate_parameter_value(value, source)?;
}
}
let source_options = EvaluatorSourceOptions {
process_xinclude: environment.process_xinclude,
whitespace: Arc::clone(&self.whitespace),
clock: environment.clock.as_ref().map(Arc::clone),
};
let mut prepared = prepare_evaluator_source(
source,
environment.resolver.as_ref(),
meter,
&source_options,
)?;
let prepared_parameters = PreparedParameters {
effective_globals,
source_remap: SourceParameterRemap {
mapping: prepared.remap.take(),
owned_bytes: std::mem::take(&mut prepared.remap_owned_bytes),
},
};
Ok((prepared, prepared_parameters, source_options))
}
}
impl Execution<'_> {
fn run(
&mut self,
options: &ExecutionOptions,
output: &OutputDefinition,
) -> Result<SerializedOutput> {
let root = SourceNode::Node(self.evaluator.source.root());
if let Some(name) = &options.initial_template {
self.call_named(
name,
Arc::new(EvaluatedParameters::default()),
&root,
ApplyFrame::new(1, 1, 1),
None,
)?;
} else {
self.apply_one(
root,
options.initial_mode.as_ref(),
Arc::new(EvaluatedParameters::default()),
ApplyFrame::new(1, 1, 1),
)?;
}
self.result.finalize_xml_ids(&mut self.meter)?;
serialize(&self.result, output, &mut self.meter)
}
}
pub(crate) fn apply_source_whitespace_rules(
document: &mut Document,
rules: &[(NameTest, bool, usize, usize)],
meter: &mut Meter,
) -> Result<Option<(HashMap<NodeId, NodeId>, usize)>> {
if rules.is_empty() {
return Ok(None);
}
let mut stripped = Vec::new();
let mut stripped_reservation = 0usize;
for (_, node) in document.nodes() {
if let Err(error) =
reserve_temporary_vec_slot(&mut stripped, meter, &mut stripped_reservation)
{
meter.release_owned_bytes(stripped_reservation);
return Err(error);
}
match should_strip_source_whitespace(document, node, rules, meter) {
Ok(strip) => stripped.push(u8::from(strip)),
Err(error) => {
meter.release_owned_bytes(stripped_reservation);
return Err(error);
}
}
}
if !stripped.contains(&1) {
meter.release_owned_bytes(stripped_reservation);
return Ok(None);
}
let retained = document.retain_nodes(meter, |_, id, _| stripped[id.0] == 0);
drop(stripped);
meter.release_owned_bytes(stripped_reservation);
retained.map(Some)
}
fn should_strip_source_whitespace(
document: &Document,
node: &super::model::Node,
rules: &[(NameTest, bool, usize, usize)],
meter: &mut Meter,
) -> Result<bool> {
let NodeKind::Text { value, .. } = &node.kind else {
return Ok(false);
};
if !value
.chars()
.all(|character| matches!(character, '\t' | '\n' | '\r' | ' '))
{
return Ok(false);
}
let Some(parent) = node.parent.and_then(|parent| document.node(parent)) else {
return Ok(false);
};
let NodeKind::Element { name, .. } = &parent.kind else {
return Ok(false);
};
if source_xml_space_preserves_whitespace(document, node.parent) {
return Ok(false);
}
let mut decision: Option<&(NameTest, bool, usize, usize)> = None;
for candidate @ (test, _, precedence, order) in rules {
meter.charge(BudgetKind::PatternEvaluations, 1)?;
if test.matches(name)
&& decision.is_none_or(|(best_test, _, best_precedence, best_order)| {
(*precedence, test.priority(), *order)
> (*best_precedence, best_test.priority(), *best_order)
})
{
decision = Some(candidate);
}
}
Ok(matches!(decision, Some((_, false, _, _))))
}
fn source_xml_space_preserves_whitespace(
document: &Document,
mut ancestor: Option<NodeId>,
) -> bool {
while let Some(id) = ancestor {
let Some(current) = document.node(id) else {
return false;
};
if let NodeKind::Element { attributes, .. } = ¤t.kind {
for attribute in attributes {
if attribute.name.namespace.as_deref()
!= Some("http://www.w3.org/XML/1998/namespace")
{
continue;
}
if attribute.name.local != "space" {
continue;
}
match attribute.value.as_str() {
"preserve" => return true,
"default" => return false,
_ => continue,
}
}
}
ancestor = current.parent;
}
false
}
struct Execution<'a> {
stylesheet: &'a Stylesheet,
evaluator: Evaluator,
result: Document,
output_stack: Vec<NodeId>,
output_stack_reserved_owned_bytes: usize,
scopes: Vec<VariableScope>,
scopes_reserved_owned_bytes: usize,
pending_globals: HashMap<ExpandedName, &'a super::compiler::GlobalVariable>,
initializing_globals: Vec<&'a ExpandedName>,
initializing_globals_reserved_owned_bytes: usize,
meter: Meter,
messages: Vec<Message>,
secondary_outputs: Vec<SecondaryOutput>,
secondary_output_uris: HashSet<Arc<String>>,
secondary_output_uri_index_bytes: usize,
modes: Vec<MeteredMode>,
modes_reserved_owned_bytes: usize,
exslt_calls: ExsltCallStack,
function_depth: usize,
native_sequence_depth: usize,
building_keys: HashSet<(usize, NodeId)>,
building_key_index_bytes: usize,
attribute_insert_position: Option<usize>,
attribute_protected_names: Option<ProtectedAttributeNames>,
result_is_temporary: bool,
}
struct ProtectedAttributeNames {
fingerprints: HashSet<u64>,
protected_count: usize,
index_bytes: usize,
}
impl ProtectedAttributeNames {
fn release(self, meter: &mut Meter) {
meter.release_owned_bytes(self.index_bytes);
}
}
#[derive(Default)]
struct VariableScope {
values: HashMap<ExpandedName, Value>,
retained_owned_bytes: usize,
}
struct SavedScopes {
items: Vec<VariableScope>,
reserved_owned_bytes: usize,
}
fn save_local_scopes(scopes: &mut Vec<VariableScope>, meter: &mut Meter) -> Result<SavedScopes> {
let count = scopes.len().saturating_sub(1);
let requested_bytes = count.saturating_mul(std::mem::size_of::<VariableScope>());
meter.charge(BudgetKind::OwnedBytes, requested_bytes)?;
let mut items = Vec::new();
if let Err(error) = items.try_reserve_exact(count) {
meter.release_owned_bytes(requested_bytes);
return Err(Error::Dynamic(format!(
"failed to reserve saved variable scopes: {error}"
)));
}
let actual_bytes = items
.capacity()
.saturating_mul(std::mem::size_of::<VariableScope>());
reconcile_replacement_growth(meter, requested_bytes, actual_bytes)?;
items.extend(scopes.drain(1..));
Ok(SavedScopes {
items,
reserved_owned_bytes: actual_bytes,
})
}
fn restore_local_scopes(scopes: &mut Vec<VariableScope>, saved: SavedScopes, meter: &mut Meter) {
debug_assert!(scopes.capacity() >= scopes.len() + saved.items.len());
scopes.extend(saved.items);
meter.release_owned_bytes(saved.reserved_owned_bytes);
}
impl VariableScope {
fn insert_retained(
&mut self,
name: &ExpandedName,
retained: RetainedValue,
meter: &mut Meter,
) -> Result<()> {
insert_retained_binding(
&mut self.values,
&mut self.retained_owned_bytes,
name,
retained,
meter,
"variable",
)
}
fn release(self, meter: &mut Meter) {
meter.release_owned_bytes(self.retained_owned_bytes);
}
}
impl Deref for VariableScope {
type Target = HashMap<ExpandedName, Value>;
fn deref(&self) -> &Self::Target {
&self.values
}
}
impl DerefMut for VariableScope {
fn deref_mut(&mut self) -> &mut Self::Target {
&mut self.values
}
}
struct RetainedValue {
value: Value,
retained_owned_bytes: usize,
}
fn insert_retained_binding(
values: &mut HashMap<ExpandedName, Value>,
retained_owned_bytes: &mut usize,
name: &ExpandedName,
retained: RetainedValue,
meter: &mut Meter,
kind: &str,
) -> Result<()> {
if values.contains_key(name) {
retained.release(meter);
return Err(Error::Dynamic(format!(
"duplicate {kind} binding for {}",
name.local
)));
}
if let Err(error) = reserve_retained_hash_map_slot(values, meter, retained_owned_bytes) {
retained.release(meter);
return Err(error);
}
*retained_owned_bytes = retained_owned_bytes
.checked_add(retained.retained_owned_bytes)
.expect("charged retained binding storage fits usize");
values.insert(name.clone(), retained.value);
Ok(())
}
impl RetainedValue {
fn release(self, meter: &mut Meter) {
meter.release_owned_bytes(self.retained_owned_bytes);
}
}
#[derive(Default)]
struct ExsltCallStack {
results: Vec<Option<Value>>,
results_reserved_owned_bytes: usize,
binding_defaults: Vec<DefaultBindingFrame>,
binding_defaults_reserved_owned_bytes: usize,
}
struct DefaultBindingFrame {
name: ExpandedName,
charged_owned_bytes: usize,
}
impl ExsltCallStack {
fn binds_defaults(&self, name: &ExpandedName) -> bool {
self.binding_defaults
.iter()
.any(|active| &active.name == name)
}
fn enter(&mut self, default_name: Option<&ExpandedName>, meter: &mut Meter) -> Result<()> {
reserve_temporary_vec_slot(
&mut self.results,
meter,
&mut self.results_reserved_owned_bytes,
)?;
let default_name = if let Some(name) = default_name {
reserve_temporary_vec_slot(
&mut self.binding_defaults,
meter,
&mut self.binding_defaults_reserved_owned_bytes,
)?;
let owned_bytes = expanded_name_owned_bytes(name);
meter.charge(BudgetKind::OwnedBytes, owned_bytes)?;
Some(DefaultBindingFrame {
name: name.clone(),
charged_owned_bytes: owned_bytes,
})
} else {
None
};
self.results.push(None);
if let Some(frame) = default_name {
self.binding_defaults.push(frame);
}
Ok(())
}
fn result_is_pending(&self) -> Option<bool> {
self.results.last().map(Option::is_none)
}
fn set_result(&mut self, value: Value) {
*self
.results
.last_mut()
.expect("function result frame was checked") = Some(value);
}
fn leave(&mut self, bound_defaults: bool, meter: &mut Meter) -> Option<Value> {
if bound_defaults {
let frame = self
.binding_defaults
.pop()
.expect("default-binding function frame remains present");
meter.release_owned_bytes(frame.charged_owned_bytes);
}
self.results
.pop()
.expect("EXSLT function result frame remains present")
}
}
struct MeteredString {
value: String,
retained_owned_bytes: usize,
}
impl MeteredString {
const fn new() -> Self {
Self {
value: String::new(),
retained_owned_bytes: 0,
}
}
fn push_str(&mut self, value: &str, meter: &mut Meter) -> Result<()> {
append_metered_string(&mut self.value, value, meter)?;
self.retained_owned_bytes = self.value.capacity();
Ok(())
}
fn reserve(&mut self, additional: usize, meter: &mut Meter) -> Result<()> {
reserve_metered_string(&mut self.value, additional, meter)?;
self.retained_owned_bytes = self.value.capacity();
Ok(())
}
fn from_borrowed(value: &str, meter: &mut Meter) -> Result<Self> {
let mut output = Self::new();
output.push_str(value, meter)?;
Ok(output)
}
fn transfer(self, meter: &mut Meter) -> String {
meter.release_owned_bytes(self.retained_owned_bytes);
self.value
}
fn release(self, meter: &mut Meter) {
meter.release_owned_bytes(self.retained_owned_bytes);
}
fn into_parts(self) -> (String, usize) {
(self.value, self.retained_owned_bytes)
}
fn as_str(&self) -> &str {
&self.value
}
}
impl Deref for MeteredString {
type Target = str;
fn deref(&self) -> &Self::Target {
&self.value
}
}
impl std::fmt::Display for MeteredString {
fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
self.value.fmt(formatter)
}
}
#[derive(Default)]
struct EvaluatedParameters {
values: HashMap<ExpandedName, Value>,
retained_owned_bytes: usize,
}
impl Deref for EvaluatedParameters {
type Target = HashMap<ExpandedName, Value>;
fn deref(&self) -> &Self::Target {
&self.values
}
}
impl EvaluatedParameters {
fn insert_retained(
&mut self,
name: &ExpandedName,
retained: RetainedValue,
meter: &mut Meter,
) -> Result<()> {
insert_retained_binding(
&mut self.values,
&mut self.retained_owned_bytes,
name,
retained,
meter,
"xsl:with-param",
)
}
fn release(self, meter: &mut Meter) {
meter.release_owned_bytes(self.retained_owned_bytes);
}
}
struct ResultTreeState {
document: Document,
output_stack: Vec<NodeId>,
output_stack_reserved_owned_bytes: usize,
attribute_insert_position: Option<usize>,
attribute_protected_names: Option<ProtectedAttributeNames>,
was_temporary: bool,
}
struct MeteredMode {
name: Option<ExpandedName>,
reserved_owned_bytes: usize,
}
#[derive(Clone, Copy)]
enum AttributePosition {
Back,
}
#[derive(Clone, Copy)]
struct ApplyFrame {
max_precedence: Option<usize>,
position: usize,
size: usize,
depth: usize,
}
enum TemplateTask {
EnterTemplate {
program: TemplateProgram,
params: Arc<EvaluatedParameters>,
node: SourceNode,
frame: ApplyFrame,
current_rule_precedence: Option<usize>,
},
ApplyOne {
node: SourceNode,
mode: Option<ExpandedName>,
mode_reserved_owned_bytes: usize,
params: Arc<EvaluatedParameters>,
frame: ApplyFrame,
},
ApplyBatch {
nodes: Vec<SourceNode>,
next: usize,
mode: Option<ExpandedName>,
params: Arc<EvaluatedParameters>,
depth: usize,
reserved_owned_bytes: usize,
},
ForEachBatch {
nodes: Vec<SourceNode>,
next: usize,
body: InstructionSequence,
depth: usize,
reserved_owned_bytes: usize,
},
Sequence {
instructions: InstructionSequence,
index: usize,
node: SourceNode,
position: usize,
size: usize,
depth: usize,
precedence: Option<usize>,
},
RestoreScopes(SavedScopes),
RestoreMode,
PopOutput,
PushScope,
PopScope,
}
struct TemplateProgram {
parameters: Arc<[Variable]>,
body: InstructionSequence,
}
#[derive(Default)]
struct TemplateTaskStack {
items: Vec<TemplateTask>,
reserved_owned_bytes: usize,
}
impl TemplateTaskStack {
fn push(&mut self, task: TemplateTask, meter: &mut Meter) -> Result<()> {
reserve_temporary_vec_slot(&mut self.items, meter, &mut self.reserved_owned_bytes)?;
self.items.push(task);
Ok(())
}
fn pop(&mut self) -> Option<TemplateTask> {
self.items.pop()
}
fn release(self, meter: &mut Meter) {
meter.release_owned_bytes(self.reserved_owned_bytes);
}
}
impl TemplateTask {
fn enter_template(
template: &Template,
params: Arc<EvaluatedParameters>,
node: SourceNode,
frame: ApplyFrame,
current_rule_precedence: Option<usize>,
) -> Self {
Self::EnterTemplate {
program: TemplateProgram {
parameters: Arc::clone(&template.params),
body: Arc::clone(&template.body),
},
params,
node,
frame,
current_rule_precedence,
}
}
}
fn push_scoped_sequence(
tasks: &mut TemplateTaskStack,
meter: &mut Meter,
instructions: InstructionSequence,
node: SourceNode,
frame: ApplyFrame,
precedence: Option<usize>,
) -> Result<()> {
tasks.push(TemplateTask::PopScope, meter)?;
tasks.push(
TemplateTask::Sequence {
instructions,
index: 0,
node,
position: frame.position,
size: frame.size,
depth: frame.depth,
precedence,
},
meter,
)?;
tasks.push(TemplateTask::PushScope, meter)
}
impl ApplyFrame {
const fn new(position: usize, size: usize, depth: usize) -> Self {
Self {
max_precedence: None,
position,
size,
depth,
}
}
}
impl<'a> Execution<'a> {
#[cfg(test)]
fn new<R: Resolver + 'static>(
stylesheet: &'a Stylesheet,
source: PreparedEvaluatorSource,
parameters: &Parameters,
prepared_parameters: PreparedParameters<'a>,
environment: ExecutionEnvironment<R>,
meter: Meter,
source_options: EvaluatorSourceOptions,
) -> Result<Self> {
Self::start(
stylesheet,
source,
parameters,
prepared_parameters,
environment,
meter,
source_options,
)
.map_err(|failure| failure.0)
}
fn start<R: Resolver + 'static>(
stylesheet: &'a Stylesheet,
source: PreparedEvaluatorSource,
parameters: &Parameters,
prepared_parameters: PreparedParameters<'a>,
environment: ExecutionEnvironment<R>,
mut meter: Meter,
source_options: EvaluatorSourceOptions,
) -> std::result::Result<Self, Box<(Error, ExecutionUsage)>> {
let setup = (|| {
let evaluator = Evaluator::new(
source,
&stylesheet.principal_document,
stylesheet.principal_base_uri.as_deref(),
&stylesheet.module_documents,
environment.resolver,
&mut meter,
source_options,
)?;
let result = Document::empty(None);
meter.charge(
BudgetKind::OwnedBytes,
metered_document_owned_bytes(&result),
)?;
let result_root = result.root();
let mut scopes = Vec::new();
let mut scopes_reserved_owned_bytes = 0;
reserve_temporary_vec_slot(&mut scopes, &mut meter, &mut scopes_reserved_owned_bytes)?;
scopes.push(VariableScope::default());
let mut modes = Vec::new();
let mut modes_reserved_owned_bytes = 0;
reserve_temporary_vec_slot(&mut modes, &mut meter, &mut modes_reserved_owned_bytes)?;
modes.push(MeteredMode {
name: None,
reserved_owned_bytes: 0,
});
let mut output_stack = Vec::new();
let mut output_stack_reserved_owned_bytes = 0;
reserve_temporary_vec_slot(
&mut output_stack,
&mut meter,
&mut output_stack_reserved_owned_bytes,
)?;
output_stack.push(result_root);
Ok((
evaluator,
result,
(scopes, scopes_reserved_owned_bytes),
(modes, modes_reserved_owned_bytes),
(output_stack, output_stack_reserved_owned_bytes),
))
})();
let (
evaluator,
result,
(scopes, scopes_reserved_owned_bytes),
(modes, modes_reserved_owned_bytes),
(output_stack, output_stack_reserved_owned_bytes),
) = match setup {
Ok(setup) => setup,
Err(error) => return Err(Box::new((error, meter.admitted_work()))),
};
let mut state = Self {
stylesheet,
evaluator,
result,
output_stack,
output_stack_reserved_owned_bytes,
scopes,
scopes_reserved_owned_bytes,
pending_globals: HashMap::new(),
initializing_globals: Vec::new(),
initializing_globals_reserved_owned_bytes: 0,
meter,
messages: vec![],
secondary_outputs: vec![],
secondary_output_uris: HashSet::new(),
secondary_output_uri_index_bytes: 0,
modes,
modes_reserved_owned_bytes,
exslt_calls: ExsltCallStack::default(),
function_depth: 0,
native_sequence_depth: 0,
building_keys: HashSet::new(),
building_key_index_bytes: 0,
attribute_insert_position: None,
attribute_protected_names: None,
result_is_temporary: false,
};
state.evaluator.initialize_xslt(
Arc::clone(&stylesheet.decimal_formats),
Arc::clone(&stylesheet.function_names),
Arc::clone(&stylesheet.keys),
Arc::clone(&stylesheet.key_name_indices),
);
let PreparedParameters {
effective_globals,
source_remap:
SourceParameterRemap {
mapping,
owned_bytes,
},
} = prepared_parameters;
let initialized = state.initialize_globals(parameters, mapping.as_ref(), effective_globals);
drop(mapping);
state.meter.release_owned_bytes(owned_bytes);
match initialized {
Ok(()) => Ok(state),
Err(error) => Err(Box::new((error, state.meter.admitted_work()))),
}
}
fn ensure_key_index(
&mut self,
source: &str,
namespaces: &[(String, String)],
context: &SourceNode,
) -> Result<()> {
let logical_root = self
.evaluator
.source
.logical_root_for(context)
.ok_or_else(|| Error::Dynamic("key() context has no logical document".into()))?;
self.ensure_key_indexes_for_roots(source, namespaces, std::slice::from_ref(&logical_root))
}
fn ensure_key_indexes_for_all_documents(
&mut self,
source: &str,
namespaces: &[(String, String)],
) -> Result<()> {
let (roots, roots_reservation) =
metered_node_id_snapshot(self.evaluator.source.logical_roots(), &mut self.meter)?;
let result = self.ensure_key_indexes_for_roots(source, namespaces, &roots);
drop(roots);
self.meter.release_owned_bytes(roots_reservation);
result
}
fn ensure_key_indexes_for_roots(
&mut self,
source: &str,
namespaces: &[(String, String)],
roots: &[NodeId],
) -> Result<()> {
let (calls, reservation) =
super::expression::metered_unprefixed_call_arguments(source, "key", &mut self.meter)?;
let result = (|| {
if calls
.iter()
.all(|(_, arguments)| literal_key_name(arguments, namespaces).is_some())
{
for root in roots.iter().copied() {
for (_, arguments) in &calls {
let (namespace, local) = literal_key_name(arguments, namespaces)
.expect("all key names are literals")?;
if let Some(slot) = self.key_slot(namespace, local) {
self.build_key_slot(slot, root)?;
}
}
}
} else {
for root in roots.iter().copied() {
for slot in 0..self.stylesheet.key_name_indices.len() {
self.build_key_slot(slot, root)?;
}
}
}
Ok(())
})();
self.meter.release_owned_bytes(reservation);
result
}
fn key_slot(&self, namespace: Option<&str>, local: &str) -> Option<usize> {
self.stylesheet.key_name_indices.iter().position(|index| {
let name = &self.stylesheet.keys[*index].name;
name.namespace.as_deref() == namespace && name.local == local
})
}
fn build_key_slot(&mut self, key_slot: usize, logical_root: NodeId) -> Result<()> {
if self.evaluator.key_index_ready(key_slot, logical_root) {
return Ok(());
}
reserve_retained_hash_set_slot(
&mut self.building_keys,
&mut self.meter,
&mut self.building_key_index_bytes,
)?;
let identity = (key_slot, logical_root);
if !self.building_keys.insert(identity) {
let key_index = self.stylesheet.key_name_indices[key_slot];
return Err(Error::Dynamic(format!(
"cyclic xsl:key dependency for {}",
self.stylesheet.keys[key_index].name.local
)));
}
let declarations = Arc::clone(&self.stylesheet.keys);
let key_index = self.stylesheet.key_name_indices[key_slot];
let name = &declarations[key_index].name;
let variables = HashMap::new();
for declaration in declarations
.iter()
.filter(|declaration| &declaration.name == name)
{
let mut pending = Vec::new();
let mut pending_reservation = 0usize;
reserve_temporary_vec_slot(&mut pending, &mut self.meter, &mut pending_reservation)?;
pending.push(logical_root);
let result = (|| {
while let Some(id) = pending.pop() {
let (child_count, attribute_count) =
self.evaluator.source.node(id).map_or((0, 0), |source| {
let attributes = if declaration.match_pattern.matches_attributes {
match &source.kind {
NodeKind::Element { attributes, .. } => attributes.len(),
_ => 0,
}
} else {
0
};
(source.children.len(), attributes)
});
for child_index in (0..child_count).rev() {
let Some(child) = self
.evaluator
.source
.node(id)
.and_then(|source| source.children.get(child_index))
.copied()
else {
continue;
};
reserve_temporary_vec_slot(
&mut pending,
&mut self.meter,
&mut pending_reservation,
)?;
pending.push(child);
}
self.append_key_values(
key_slot,
declaration,
SourceNode::Node(id),
&variables,
)?;
for index in 0..attribute_count {
self.append_key_values(
key_slot,
declaration,
SourceNode::Attribute { owner: id, index },
&variables,
)?;
}
}
Ok(())
})();
drop(pending);
self.meter.release_owned_bytes(pending_reservation);
if let Err(error) = result {
self.building_keys.remove(&identity);
return Err(error);
}
}
self.building_keys.remove(&identity);
self.evaluator
.finish_key_index(key_slot, logical_root, &mut self.meter)
}
fn append_key_values(
&mut self,
key_slot: usize,
declaration: &super::compiler::KeyDeclaration,
node: SourceNode,
variables: &HashMap<ExpandedName, Value>,
) -> Result<()> {
if !self.matches_pattern(&declaration.match_pattern, &node, variables)? {
return Ok(());
}
match self.evaluate(&declaration.use_expression, &node, 1, 1)? {
XPathValue::NodeSet(nodes) => {
for selected in nodes.iter() {
let (value, value_reservation) = self
.evaluator
.materialize_temporary_string_value(selected, &mut self.meter)?;
self.evaluator.append_key_entry(
key_slot,
value,
value_reservation,
&node,
&mut self.meter,
)?;
}
}
value => {
let (value, value_reservation) =
value.into_fully_metered_temporary_string(&self.evaluator, &mut self.meter)?;
self.evaluator.append_key_entry(
key_slot,
value,
value_reservation,
&node,
&mut self.meter,
)?;
}
}
Ok(())
}
fn matches_pattern(
&mut self,
pattern: &super::compiler::Pattern,
node: &SourceNode,
variables: &HashMap<ExpandedName, Value>,
) -> Result<bool> {
self.meter.charge(BudgetKind::PatternEvaluations, 1)?;
self.matches_pattern_precharged(pattern, node, variables)
}
fn matches_pattern_precharged(
&mut self,
pattern: &super::compiler::Pattern,
node: &SourceNode,
variables: &HashMap<ExpandedName, Value>,
) -> Result<bool> {
if self.evaluator.pattern_terminal_rejects(pattern, node)? {
return Ok(false);
}
if xpath_calls_key(&pattern.source) {
self.ensure_key_index(&pattern.source, &pattern.namespaces, node)?;
}
self.evaluator
.matches(pattern, node, variables, &mut self.meter)
}
fn initialize_globals(
&mut self,
parameters: &Parameters,
source_remap: Option<&HashMap<NodeId, NodeId>>,
mut effective: HashMap<ExpandedName, &'a super::compiler::GlobalVariable>,
) -> Result<()> {
let mut order = Vec::new();
let mut order_reservation = 0usize;
for global in effective.values().copied() {
if let Err(error) =
reserve_temporary_vec_slot(&mut order, &mut self.meter, &mut order_reservation)
{
self.meter.release_owned_bytes(order_reservation);
return Err(error);
}
order.push(global);
}
order.sort_by_key(|global| global.order);
let initialized = (|| {
for global in &order {
let name = &global.variable.name;
if global.is_parameter
&& let Some(value) = parameters.get(name)
{
let name_owned_bytes = expanded_name_owned_bytes(name);
self.meter
.charge(BudgetKind::OwnedBytes, name_owned_bytes)?;
let mut retained =
match clone_parameter_value(value, source_remap, &mut self.meter) {
Ok(retained) => retained,
Err(error) => {
self.meter.release_owned_bytes(name_owned_bytes);
return Err(error);
}
};
retained.retained_owned_bytes = retained
.retained_owned_bytes
.saturating_add(name_owned_bytes);
self.scopes[0].insert_retained(name, retained, &mut self.meter)?;
effective.remove(name);
}
}
self.pending_globals = effective;
for global in &order {
self.ensure_global(&global.variable.name)?;
}
Ok(())
})();
drop(order);
self.meter.release_owned_bytes(order_reservation);
debug_assert!(self.initializing_globals.is_empty());
self.initializing_globals.clear();
self.meter
.release_owned_bytes(self.initializing_globals_reserved_owned_bytes);
self.initializing_globals_reserved_owned_bytes = 0;
initialized
}
fn ensure_global(&mut self, name: &ExpandedName) -> Result<()> {
if self.scopes[0].contains_key(name) {
return Ok(());
}
if self.initializing_globals.contains(&name) {
return circular_global_dependency_error(
&self.initializing_globals,
name,
&mut self.meter,
);
}
let Some(global) = self.pending_globals.remove(name) else {
return Ok(());
};
self.meter.recursion_with_ceiling(
self.initializing_globals.len().saturating_add(1),
EXECUTION_RECURSION_DEPTH_CEILING,
)?;
push_initializing_global(
&mut self.initializing_globals,
&global.variable.name,
&mut self.meter,
&mut self.initializing_globals_reserved_owned_bytes,
)?;
let value = self.evaluate_variable(
&global.variable,
&SourceNode::Node(self.evaluator.source.root()),
1,
1,
1,
None,
);
self.initializing_globals.pop();
let retained = value?;
self.scopes[0].insert_retained(name, retained, &mut self.meter)?;
Ok(())
}
fn ensure_expression_globals(&mut self, expression: &Expression) -> Result<()> {
for name in expression.variable_references.iter() {
if !self
.scopes
.iter()
.rev()
.any(|scope| scope.contains_key(name))
{
self.ensure_global(name)?;
}
}
Ok(())
}
fn variables(&mut self) -> Result<(HashMap<ExpandedName, Value>, usize)> {
let (capacity, reserved_owned_bytes) = visible_variable_snapshot_size(&self.scopes);
self.meter
.charge(BudgetKind::OwnedBytes, reserved_owned_bytes)?;
let mut variables = HashMap::with_capacity(capacity);
variables.extend(
visible_variable_bindings(&self.scopes)
.map(|(name, value)| (name.clone(), value.clone())),
);
Ok((variables, reserved_owned_bytes))
}
fn pop_scope(&mut self) {
let scope = self
.scopes
.pop()
.expect("scope stack retains its global scope");
scope.release(&mut self.meter);
}
fn push_scope(&mut self) -> Result<()> {
reserve_temporary_vec_slot(
&mut self.scopes,
&mut self.meter,
&mut self.scopes_reserved_owned_bytes,
)?;
self.scopes.push(VariableScope::default());
Ok(())
}
fn restore_caller_scopes(&mut self, saved: SavedScopes) {
while self.scopes.len() > 1 {
self.pop_scope();
}
restore_local_scopes(&mut self.scopes, saved, &mut self.meter);
}
fn release_parameters_if_last(&mut self, parameters: &Arc<EvaluatedParameters>) {
if Arc::strong_count(parameters) == 1 {
self.meter
.release_owned_bytes(parameters.retained_owned_bytes);
}
}
fn pop_mode(&mut self) {
if let Some(mode) = self.modes.pop() {
self.meter.release_owned_bytes(mode.reserved_owned_bytes);
}
}
fn apply_one(
&mut self,
node: SourceNode,
mode: Option<&ExpandedName>,
params: Arc<EvaluatedParameters>,
frame: ApplyFrame,
) -> Result<()> {
let mode_reserved_owned_bytes = mode.map_or(0, expanded_name_owned_bytes);
self.meter
.charge(BudgetKind::OwnedBytes, mode_reserved_owned_bytes)?;
self.run_template_tasks(TemplateTask::ApplyOne {
node,
mode: mode.cloned(),
mode_reserved_owned_bytes,
params,
frame,
})
}
fn execute_template(
&mut self,
template: &Template,
node: SourceNode,
params: Arc<EvaluatedParameters>,
frame: ApplyFrame,
current_rule_precedence: Option<usize>,
) -> Result<()> {
self.run_template_tasks(TemplateTask::enter_template(
template,
params,
node,
frame,
current_rule_precedence,
))
}
fn run_template_tasks(&mut self, initial: TemplateTask) -> Result<()> {
let scope_depth = self.scopes.len();
let mode_depth = self.modes.len();
let output_depth = self.output_stack.len();
let mut tasks = TemplateTaskStack::default();
let result = if let Err(error) = reserve_temporary_vec_slot(
&mut tasks.items,
&mut self.meter,
&mut tasks.reserved_owned_bytes,
) {
if let TemplateTask::ApplyOne {
mode_reserved_owned_bytes,
..
} = initial
{
self.meter.release_owned_bytes(mode_reserved_owned_bytes);
}
Err(error)
} else {
tasks.items.push(initial);
self.run_template_task_stack(&mut tasks)
};
if result.is_err() {
while let Some(task) = tasks.pop() {
match task {
TemplateTask::RestoreScopes(caller_scopes) => {
self.restore_caller_scopes(caller_scopes);
}
TemplateTask::ApplyBatch {
params,
reserved_owned_bytes,
..
} => {
self.release_parameters_if_last(¶ms);
self.meter.release_owned_bytes(reserved_owned_bytes);
}
TemplateTask::ForEachBatch {
reserved_owned_bytes,
..
} => {
self.meter.release_owned_bytes(reserved_owned_bytes);
}
TemplateTask::ApplyOne {
mode_reserved_owned_bytes,
..
} => self.meter.release_owned_bytes(mode_reserved_owned_bytes),
_ => {}
}
}
while self.scopes.len() > scope_depth {
self.pop_scope();
}
while self.modes.len() > mode_depth {
self.pop_mode();
}
self.output_stack.truncate(output_depth);
}
tasks.release(&mut self.meter);
result
}
fn run_template_task_stack(&mut self, tasks: &mut TemplateTaskStack) -> Result<()> {
while let Some(task) = tasks.pop() {
match task {
TemplateTask::EnterTemplate {
program,
params,
node,
frame,
current_rule_precedence,
} => self.push_template_tasks(
tasks,
program,
params,
node,
frame,
current_rule_precedence,
)?,
TemplateTask::ApplyOne {
node,
mode,
mode_reserved_owned_bytes,
params,
frame,
} => self.push_apply_one_tasks(
tasks,
node,
mode,
mode_reserved_owned_bytes,
params,
frame,
)?,
TemplateTask::ApplyBatch {
nodes,
next,
mode,
params,
depth,
reserved_owned_bytes,
} => {
let Some(selected) = nodes.get(next).cloned() else {
self.release_parameters_if_last(¶ms);
self.meter.release_owned_bytes(reserved_owned_bytes);
continue;
};
let total = nodes.len();
let selected_mode = mode.clone();
if let Err(error) = tasks.push(
TemplateTask::ApplyBatch {
nodes,
next: next + 1,
mode,
params: Arc::clone(¶ms),
depth,
reserved_owned_bytes,
},
&mut self.meter,
) {
self.meter.release_owned_bytes(reserved_owned_bytes);
self.release_parameters_if_last(¶ms);
return Err(error);
}
tasks.push(
TemplateTask::ApplyOne {
node: selected,
mode: selected_mode,
mode_reserved_owned_bytes: 0,
params,
frame: ApplyFrame::new(next + 1, total, depth),
},
&mut self.meter,
)?;
}
TemplateTask::ForEachBatch {
nodes,
next,
body,
depth,
reserved_owned_bytes,
} => {
let Some(selected) = nodes.get(next).cloned() else {
self.meter.release_owned_bytes(reserved_owned_bytes);
continue;
};
let total = nodes.len();
tasks.push(
TemplateTask::ForEachBatch {
nodes,
next: next + 1,
body: Arc::clone(&body),
depth,
reserved_owned_bytes,
},
&mut self.meter,
)?;
push_scoped_sequence(
tasks,
&mut self.meter,
body,
selected,
ApplyFrame::new(next + 1, total, depth),
None,
)?;
}
TemplateTask::RestoreScopes(caller_scopes) => {
self.restore_caller_scopes(caller_scopes);
}
TemplateTask::RestoreMode => {
self.pop_mode();
}
TemplateTask::PopOutput => {
self.output_stack.pop();
}
TemplateTask::PushScope => self.push_scope()?,
TemplateTask::PopScope => {
self.pop_scope();
}
TemplateTask::Sequence {
instructions,
index,
node,
position,
size,
depth,
precedence,
} => {
self.meter.recursion(depth)?;
let Some(instruction) = instructions.get(index) else {
continue;
};
tasks.push(
TemplateTask::Sequence {
instructions: instructions.clone(),
index: index + 1,
node: node.clone(),
position,
size,
depth,
precedence,
},
&mut self.meter,
)?;
match instruction {
Instruction::CallTemplate { name, parameters } => {
self.meter.charge(BudgetKind::TemplateApplications, 1)?;
let supplied = self.evaluate_with_params(
parameters, &node, position, size, depth, precedence,
)?;
let target = self
.stylesheet
.templates
.iter()
.filter(|candidate| candidate.name.as_ref() == Some(name))
.max_by_key(|candidate| (candidate.precedence, candidate.order))
.ok_or_else(|| {
Error::Dynamic(format!(
"named template {} not found",
name.local
))
})?;
tasks.push(
TemplateTask::enter_template(
target,
Arc::new(supplied),
node,
ApplyFrame::new(position, size, depth + 1),
precedence,
),
&mut self.meter,
)?;
}
Instruction::ApplyTemplates {
select,
mode,
sorts,
parameters,
} => {
let (mut nodes, node_reservation) =
self.select_nodes(select, &node, position, size)?;
if let Err(error) =
self.sort_nodes(&mut nodes, sorts, &node, position, size)
{
self.meter.release_owned_bytes(node_reservation);
return Err(error);
}
let supplied = match self.evaluate_with_params(
parameters, &node, position, size, depth, precedence,
) {
Ok(supplied) => Arc::new(supplied),
Err(error) => {
self.meter.release_owned_bytes(node_reservation);
return Err(error);
}
};
let mode_reservation =
mode.as_ref().map_or(0, expanded_name_owned_bytes);
if let Err(error) =
self.meter.charge(BudgetKind::OwnedBytes, mode_reservation)
{
self.meter.release_owned_bytes(node_reservation);
return Err(error);
}
self.push_apply_batch(
tasks,
nodes,
node_reservation,
MeteredMode {
name: mode.clone(),
reserved_owned_bytes: mode_reservation,
},
supplied,
depth + 1,
)?;
}
Instruction::ApplyImports => {
let current_rule_precedence = precedence.ok_or_else(|| {
Error::Dynamic(
"xsl:apply-imports requires a current template rule".into(),
)
})?;
let mode = self.modes.last().and_then(|mode| mode.name.as_ref());
let mode_reserved_owned_bytes =
mode.map_or(0, expanded_name_owned_bytes);
self.meter
.charge(BudgetKind::OwnedBytes, mode_reserved_owned_bytes)?;
if let Err(error) = tasks.push(
TemplateTask::ApplyOne {
node,
mode: mode.cloned(),
mode_reserved_owned_bytes,
params: Arc::new(EvaluatedParameters::default()),
frame: ApplyFrame {
max_precedence: Some(current_rule_precedence),
position,
size,
depth: depth + 1,
},
},
&mut self.meter,
) {
self.meter.release_owned_bytes(mode_reserved_owned_bytes);
return Err(error);
}
}
Instruction::LiteralElement {
base_uri,
name,
prefix,
attributes,
namespaces,
children,
attribute_sets,
} => {
self.meter.check_additional(
BudgetKind::OwnedBytes,
self.literal_projection_owned_bytes(
name,
prefix.as_deref(),
namespaces,
base_uri.as_deref(),
),
)?;
let (name, prefix, result_namespaces) = self
.alias_literal_name_and_namespaces(
name,
prefix.as_deref(),
namespaces,
)?;
let id = self.push_node_with_base(
self.parent(),
NodeKind::Element {
name,
prefix,
attributes: vec![],
namespaces: result_namespaces.into(),
},
base_uri.clone(),
)?;
self.push_output_node(id)?;
self.apply_attribute_sets(
attribute_sets,
&node,
ApplyFrame::new(position, size, depth),
precedence,
)?;
for attribute in attributes {
let value =
self.evaluate_avt(&attribute.value, &node, position, size)?;
let (name, prefix) = self.alias_attribute_name(
&attribute.name,
attribute.prefix.as_deref(),
);
let value = value.transfer(&mut self.meter);
self.add_literal_attribute(Attribute {
name,
prefix,
value,
})?;
}
tasks.push(TemplateTask::PopOutput, &mut self.meter)?;
push_scoped_sequence(
tasks,
&mut self.meter,
Arc::clone(children),
node,
ApplyFrame::new(position, size, depth + 1),
precedence,
)?;
}
Instruction::Element { body, .. } => {
self.begin_computed_element(
instruction,
&node,
ApplyFrame::new(position, size, depth),
precedence,
)?;
tasks.push(TemplateTask::PopOutput, &mut self.meter)?;
push_scoped_sequence(
tasks,
&mut self.meter,
Arc::clone(body),
node,
ApplyFrame::new(position, size, depth + 1),
precedence,
)?;
}
Instruction::Copy {
base_uri,
body,
attribute_sets,
} => match &node {
SourceNode::Node(source_id) => {
let source =
self.evaluator.source.node(*source_id).ok_or_else(|| {
Error::Dynamic("stale source node".into())
})?;
let kind = clone_for_xsl_copy(&source.kind, &self.meter)?;
match kind {
NodeKind::Element {
name,
prefix,
namespaces,
..
} => {
let target = self.push_xsl_copy_element(
name,
prefix,
namespaces,
base_uri.as_deref(),
)?;
self.push_output_node(target)?;
self.apply_attribute_sets(
attribute_sets,
&node,
ApplyFrame::new(position, size, depth),
precedence,
)?;
tasks.push(TemplateTask::PopOutput, &mut self.meter)?;
push_scoped_sequence(
tasks,
&mut self.meter,
Arc::clone(body),
node,
ApplyFrame::new(position, size, depth + 1),
precedence,
)?;
}
NodeKind::Root => push_scoped_sequence(
tasks,
&mut self.meter,
Arc::clone(body),
node,
ApplyFrame::new(position, size, depth + 1),
precedence,
)?,
NodeKind::Text { value, .. } => {
self.append_text(&value, false)?
}
NodeKind::Comment(value) => {
self.push_node(self.parent(), NodeKind::Comment(value))?;
}
NodeKind::ProcessingInstruction { target, value } => {
self.push_node(
self.parent(),
NodeKind::ProcessingInstruction { target, value },
)?;
}
}
}
SourceNode::Attribute { owner, index } => {
self.copy_source_attribute(*owner, *index)?;
}
SourceNode::Namespace { owner, index } => {
self.copy_source_namespace(*owner, *index)?;
}
},
Instruction::ForEach {
select,
sorts,
body,
} => {
let (mut nodes, node_reservation) =
self.select_nodes(select, &node, position, size)?;
if let Err(error) =
self.sort_nodes(&mut nodes, sorts, &node, position, size)
{
self.meter.release_owned_bytes(node_reservation);
return Err(error);
}
self.push_for_each_batch(
tasks,
nodes,
node_reservation,
Arc::clone(body),
depth + 1,
)?;
}
Instruction::If { test, body } => {
if self.evaluate(test, &node, position, size)?.boolean() {
push_scoped_sequence(
tasks,
&mut self.meter,
Arc::clone(body),
node,
ApplyFrame::new(position, size, depth + 1),
precedence,
)?;
}
}
Instruction::Choose {
branches,
otherwise,
} => {
let mut selected = otherwise;
for (test, body) in branches {
if self.evaluate(test, &node, position, size)?.boolean() {
selected = body;
break;
}
}
push_scoped_sequence(
tasks,
&mut self.meter,
Arc::clone(selected),
node,
ApplyFrame::new(position, size, depth + 1),
precedence,
)?;
}
Instruction::ExtensionFallback {
name,
present,
body,
} => {
if !present {
return Err(Error::Unsupported(format!(
"extension element {name} has no xsl:fallback"
)));
}
push_scoped_sequence(
tasks,
&mut self.meter,
Arc::clone(body),
node,
ApplyFrame::new(position, size, depth + 1),
precedence,
)?;
}
instruction => self.execute_instruction(
instruction,
&node,
position,
size,
depth,
precedence,
)?,
}
}
}
}
Ok(())
}
fn push_apply_one_tasks(
&mut self,
tasks: &mut TemplateTaskStack,
node: SourceNode,
mode: Option<ExpandedName>,
mode_reserved_owned_bytes: usize,
params: Arc<EvaluatedParameters>,
frame: ApplyFrame,
) -> Result<()> {
let mut mode_reserved_owned_bytes = mode_reserved_owned_bytes;
let result = self.push_apply_one_tasks_inner(
tasks,
node,
mode,
&mut mode_reserved_owned_bytes,
params,
frame,
);
self.meter.release_owned_bytes(mode_reserved_owned_bytes);
result
}
fn push_apply_one_tasks_inner(
&mut self,
tasks: &mut TemplateTaskStack,
node: SourceNode,
mode: Option<ExpandedName>,
mode_reserved_owned_bytes: &mut usize,
params: Arc<EvaluatedParameters>,
frame: ApplyFrame,
) -> Result<()> {
self.meter.recursion(frame.depth)?;
self.meter.charge(BudgetKind::TemplateApplications, 1)?;
let variables = HashMap::new();
let mut selected = None::<&Template>;
for template in self.stylesheet.templates.iter() {
self.meter.charge(BudgetKind::PatternEvaluations, 1)?;
if template.pattern.is_none()
|| template.mode != mode
|| frame
.max_precedence
.is_some_and(|max| template.precedence >= max)
{
continue;
}
let pattern = template.pattern.as_ref().expect("pattern was checked");
if self.matches_pattern_precharged(pattern, &node, &variables)?
&& selected.is_none_or(|current| {
template.precedence > current.precedence
|| (template.precedence == current.precedence
&& (template.priority > current.priority
|| (template.priority == current.priority
&& template.order > current.order)))
})
{
selected = Some(template);
}
}
if let Some(template) = selected {
reserve_temporary_vec_slot(
&mut self.modes,
&mut self.meter,
&mut self.modes_reserved_owned_bytes,
)?;
self.modes.push(MeteredMode {
name: mode,
reserved_owned_bytes: *mode_reserved_owned_bytes,
});
*mode_reserved_owned_bytes = 0;
tasks.push(TemplateTask::RestoreMode, &mut self.meter)?;
let current_rule_precedence = Some(template.precedence);
tasks.push(
TemplateTask::enter_template(
template,
params,
node,
frame,
current_rule_precedence,
),
&mut self.meter,
)?;
return Ok(());
}
self.release_parameters_if_last(¶ms);
match &node {
SourceNode::Node(id) => {
let kind = self.evaluator.source.node(*id).map(|source| &source.kind);
match kind {
Some(NodeKind::Root | NodeKind::Element { .. }) => {
let children = self.evaluator.children(&node, &mut self.meter)?;
let child_reservation = children
.capacity()
.saturating_mul(std::mem::size_of::<SourceNode>());
self.meter
.charge(BudgetKind::OwnedBytes, child_reservation)?;
let built_in_params = Arc::new(EvaluatedParameters::default());
let reservation = std::mem::take(mode_reserved_owned_bytes);
self.push_apply_batch(
tasks,
children,
child_reservation,
MeteredMode {
name: mode,
reserved_owned_bytes: reservation,
},
built_in_params,
frame.depth + 1,
)
}
Some(NodeKind::Text { .. }) => self.append_source_leaf_text(&node, false),
_ => Ok(()),
}
}
SourceNode::Attribute { .. } => self.append_source_leaf_text(&node, false),
SourceNode::Namespace { .. } => Ok(()),
}
}
fn push_apply_batch(
&mut self,
tasks: &mut TemplateTaskStack,
nodes: Vec<SourceNode>,
node_reservation: usize,
mode: MeteredMode,
params: Arc<EvaluatedParameters>,
depth: usize,
) -> Result<()> {
if nodes.is_empty() {
self.meter.release_owned_bytes(node_reservation);
self.meter.release_owned_bytes(mode.reserved_owned_bytes);
self.release_parameters_if_last(¶ms);
return Ok(());
}
debug_assert_eq!(
node_reservation,
nodes
.capacity()
.saturating_mul(std::mem::size_of::<SourceNode>())
);
let mode_bytes = mode
.name
.as_ref()
.map_or(0, expanded_name_owned_bytes)
.saturating_mul(2);
let additional_mode_reservation = mode_bytes.saturating_sub(mode.reserved_owned_bytes);
if let Err(error) = self
.meter
.charge(BudgetKind::OwnedBytes, additional_mode_reservation)
{
self.meter.release_owned_bytes(node_reservation);
self.meter.release_owned_bytes(mode.reserved_owned_bytes);
return Err(error);
}
let reserved_owned_bytes = node_reservation.saturating_add(mode_bytes);
if let Err(error) = tasks.push(
TemplateTask::ApplyBatch {
nodes,
next: 0,
mode: mode.name,
params,
depth,
reserved_owned_bytes,
},
&mut self.meter,
) {
self.meter.release_owned_bytes(reserved_owned_bytes);
return Err(error);
}
Ok(())
}
fn push_for_each_batch(
&mut self,
tasks: &mut TemplateTaskStack,
nodes: Vec<SourceNode>,
node_reservation: usize,
body: InstructionSequence,
depth: usize,
) -> Result<()> {
if nodes.is_empty() {
self.meter.release_owned_bytes(node_reservation);
return Ok(());
}
debug_assert_eq!(
node_reservation,
nodes
.capacity()
.saturating_mul(std::mem::size_of::<SourceNode>())
);
if let Err(error) = tasks.push(
TemplateTask::ForEachBatch {
nodes,
next: 0,
body,
depth,
reserved_owned_bytes: node_reservation,
},
&mut self.meter,
) {
self.meter.release_owned_bytes(node_reservation);
return Err(error);
}
Ok(())
}
fn push_template_tasks(
&mut self,
tasks: &mut TemplateTaskStack,
program: TemplateProgram,
params: Arc<EvaluatedParameters>,
node: SourceNode,
frame: ApplyFrame,
current_rule_precedence: Option<usize>,
) -> Result<()> {
let ApplyFrame {
position,
size,
depth,
..
} = frame;
self.meter.recursion(depth)?;
reserve_temporary_vec_slot(
&mut tasks.items,
&mut self.meter,
&mut tasks.reserved_owned_bytes,
)?;
let caller_scopes = save_local_scopes(&mut self.scopes, &mut self.meter)?;
tasks.items.push(TemplateTask::RestoreScopes(caller_scopes));
self.push_scope()?;
for parameter in program.parameters.iter() {
let retained = if let Some(value) = params.get(¶meter.name) {
let retained_owned_bytes = binding_owned_bytes(¶meter.name, value);
self.meter
.check_additional(BudgetKind::OwnedBytes, retained_owned_bytes)?;
let value = value.clone();
self.meter
.charge(BudgetKind::OwnedBytes, retained_owned_bytes)?;
RetainedValue {
value,
retained_owned_bytes,
}
} else {
self.evaluate_variable(
parameter,
&node,
position,
size,
depth,
current_rule_precedence,
)?
};
self.scopes
.last_mut()
.expect("template parameter scope exists")
.insert_retained(¶meter.name, retained, &mut self.meter)?;
}
self.release_parameters_if_last(¶ms);
tasks.push(
TemplateTask::Sequence {
instructions: program.body,
index: 0,
node,
position,
size,
depth,
precedence: current_rule_precedence,
},
&mut self.meter,
)
}
fn begin_computed_element(
&mut self,
instruction: &Instruction,
node: &SourceNode,
frame: ApplyFrame,
precedence: Option<usize>,
) -> Result<()> {
let Instruction::Element {
base_uri,
name,
namespace,
namespaces: static_namespaces,
attribute_sets,
..
} = instruction
else {
unreachable!("computed-element instruction")
};
let lexical = self.evaluate_avt(name, node, frame.position, frame.size)?;
let (prefix, local) = split_name(&lexical)?;
let namespace = namespace
.as_ref()
.map(|value| self.evaluate_avt(value, node, frame.position, frame.size))
.transpose()?;
let namespace = match namespace {
Some(namespace) => Some(namespace),
None => computed_element_namespace(static_namespaces, prefix.as_deref())
.map(|uri| MeteredString::from_borrowed(uri, &mut self.meter))
.transpose()?,
};
let (namespace, namespace_reservation) = match namespace {
Some(namespace) => {
let (namespace, reservation) = namespace.into_parts();
(Some(namespace), reservation)
}
None => (None, 0),
};
let (prefix, namespace) = normalize_computed_namespace(prefix, namespace, &lexical)?;
require_bound_computed_prefix(prefix.as_deref(), namespace.as_deref(), &lexical)?;
let (namespaces, namespace_clone_reservation) = match namespace.as_ref() {
Some(uri) => {
self.meter.charge(BudgetKind::OwnedBytes, uri.len())?;
let namespaces = vec![Namespace {
prefix: prefix.clone(),
uri: uri.clone(),
}];
let reservation = namespaces[0].uri.capacity();
if reservation > uri.len() {
self.meter
.charge(BudgetKind::OwnedBytes, reservation - uri.len())?;
}
(namespaces, reservation)
}
None => (Vec::new(), 0),
};
lexical.release(&mut self.meter);
let pushed = self.push_node_with_base(
self.parent(),
NodeKind::Element {
name: ExpandedName::new(namespace, local),
prefix,
namespaces: namespaces.into(),
attributes: vec![],
},
base_uri.clone(),
);
self.meter
.release_owned_bytes(namespace_reservation.saturating_add(namespace_clone_reservation));
let id = pushed?;
self.push_output_node(id)?;
self.apply_attribute_sets(attribute_sets, node, frame, precedence)
}
fn execute_sequence(
&mut self,
instructions: &[Instruction],
node: &SourceNode,
position: usize,
size: usize,
depth: usize,
current_precedence: Option<usize>,
) -> Result<()> {
self.meter.recursion(depth)?;
self.meter.recursion_with_ceiling(
self.native_sequence_depth + 1,
EXECUTION_RECURSION_DEPTH_CEILING,
)?;
self.native_sequence_depth += 1;
let result = instructions.iter().try_for_each(|instruction| {
self.execute_instruction(instruction, node, position, size, depth, current_precedence)
});
self.native_sequence_depth -= 1;
result
}
fn execute_scoped_sequence(
&mut self,
instructions: &[Instruction],
node: &SourceNode,
position: usize,
size: usize,
depth: usize,
current_precedence: Option<usize>,
) -> Result<()> {
self.push_scope()?;
let result = self.execute_sequence(
instructions,
node,
position,
size,
depth,
current_precedence,
);
self.pop_scope();
result
}
fn execute_instruction(
&mut self,
instruction: &Instruction,
node: &SourceNode,
position: usize,
size: usize,
depth: usize,
current_precedence: Option<usize>,
) -> Result<()> {
match instruction {
Instruction::Text(value, disable) => self.append_text(value, *disable),
Instruction::LiteralElement {
base_uri,
name,
prefix,
attributes,
namespaces,
children,
attribute_sets,
} => {
self.meter.check_additional(
BudgetKind::OwnedBytes,
self.literal_projection_owned_bytes(
name,
prefix.as_deref(),
namespaces,
base_uri.as_deref(),
),
)?;
let (name, prefix, result_namespaces) =
self.alias_literal_name_and_namespaces(name, prefix.as_deref(), namespaces)?;
let parent = self.parent();
let id = self.push_node_with_base(
parent,
NodeKind::Element {
name,
prefix,
attributes: vec![],
namespaces: result_namespaces.into(),
},
base_uri.clone(),
)?;
self.push_output_node(id)?;
self.apply_attribute_sets(
attribute_sets,
node,
ApplyFrame::new(position, size, depth),
current_precedence,
)?;
for attribute in attributes {
let value = self.evaluate_avt(&attribute.value, node, position, size)?;
let (name, prefix) =
self.alias_attribute_name(&attribute.name, attribute.prefix.as_deref());
let value = value.transfer(&mut self.meter);
self.add_literal_attribute(Attribute {
name,
prefix,
value,
})?;
}
let result = self.execute_scoped_sequence(
children,
node,
position,
size,
depth + 1,
current_precedence,
);
self.output_stack.pop();
result
}
Instruction::ApplyTemplates {
select,
mode,
sorts,
parameters,
} => {
let (mut nodes, node_reservation) =
self.select_nodes(select, node, position, size)?;
let result = (|| {
self.sort_nodes(&mut nodes, sorts, node, position, size)?;
let supplied = Arc::new(self.evaluate_with_params(
parameters,
node,
position,
size,
depth,
current_precedence,
)?);
let total = nodes.len();
let applied = (|| {
for (index, selected) in nodes.drain(..).enumerate() {
self.apply_one(
selected,
mode.as_ref(),
Arc::clone(&supplied),
ApplyFrame::new(index + 1, total, depth + 1),
)?;
}
Ok(())
})();
self.release_parameters_if_last(&supplied);
applied
})();
self.meter.release_owned_bytes(node_reservation);
result
}
Instruction::ApplyImports => {
let current_rule_precedence = current_precedence.ok_or_else(|| {
Error::Dynamic("xsl:apply-imports requires a current template rule".into())
})?;
let mode = self.modes.last().and_then(|mode| mode.name.as_ref());
let mode_reserved_owned_bytes = mode.map_or(0, expanded_name_owned_bytes);
self.meter
.charge(BudgetKind::OwnedBytes, mode_reserved_owned_bytes)?;
self.run_template_tasks(TemplateTask::ApplyOne {
node: node.clone(),
mode: mode.cloned(),
mode_reserved_owned_bytes,
params: Arc::new(EvaluatedParameters::default()),
frame: ApplyFrame {
max_precedence: Some(current_rule_precedence),
position,
size,
depth: depth + 1,
},
})
}
Instruction::CallTemplate { name, parameters } => {
let supplied = Arc::new(self.evaluate_with_params(
parameters,
node,
position,
size,
depth,
current_precedence,
)?);
self.call_named(
name,
supplied,
node,
ApplyFrame::new(position, size, depth + 1),
current_precedence,
)
}
Instruction::ForEach {
select,
sorts,
body,
} => {
let (mut nodes, node_reservation) =
self.select_nodes(select, node, position, size)?;
let result = (|| {
self.sort_nodes(&mut nodes, sorts, node, position, size)?;
let total = nodes.len();
for (index, selected) in nodes.iter().enumerate() {
self.push_scope()?;
let result = self.execute_sequence(
body,
selected,
index + 1,
total,
depth + 1,
None,
);
self.pop_scope();
result?;
}
Ok(())
})();
self.meter.release_owned_bytes(node_reservation);
result
}
Instruction::If { test, body } => {
if self.evaluate(test, node, position, size)?.boolean() {
self.execute_scoped_sequence(
body,
node,
position,
size,
depth + 1,
current_precedence,
)?
}
Ok(())
}
Instruction::Choose {
branches,
otherwise,
} => {
for (test, body) in branches {
if self.evaluate(test, node, position, size)?.boolean() {
return self.execute_scoped_sequence(
body,
node,
position,
size,
depth + 1,
current_precedence,
);
}
}
self.execute_scoped_sequence(
otherwise,
node,
position,
size,
depth + 1,
current_precedence,
)
}
Instruction::ValueOf {
select,
disable_output_escaping,
} => {
let value = self.evaluate(select, node, position, size)?;
self.append_xpath_text(value, *disable_output_escaping)
}
Instruction::CopyOf { select, base_uri } => {
match self.evaluate(select, node, position, size)? {
XPathValue::NodeSet(nodes) => {
for selected in nodes {
self.copy_source(
&selected,
self.parent(),
depth + 1,
base_uri.as_deref(),
)?
}
}
XPathValue::ResultTreeFragment(fragment) => {
self.copy_document(
&fragment,
fragment.root(),
self.parent(),
depth + 1,
base_uri.as_deref(),
)?;
}
value => self.append_xpath_text(value, false)?,
}
Ok(())
}
Instruction::Copy {
base_uri,
body,
attribute_sets,
} => {
match node {
SourceNode::Node(id) => {
if let Some(source) = self.evaluator.source.node(*id) {
let kind = clone_for_xsl_copy(&source.kind, &self.meter)?;
match kind {
NodeKind::Element {
name,
prefix,
attributes: _,
namespaces,
} => {
let target = self.push_xsl_copy_element(
name,
prefix,
namespaces,
base_uri.as_deref(),
)?;
self.push_output_node(target)?;
self.apply_attribute_sets(
attribute_sets,
node,
ApplyFrame::new(position, size, depth),
current_precedence,
)?;
let result = self.execute_scoped_sequence(
body,
node,
position,
size,
depth + 1,
current_precedence,
);
self.output_stack.pop();
result?
}
NodeKind::Text { value, .. } => self.append_text(&value, false)?,
NodeKind::Comment(value) => {
self.push_node(self.parent(), NodeKind::Comment(value))?;
}
NodeKind::ProcessingInstruction { target, value } => {
self.push_node(
self.parent(),
NodeKind::ProcessingInstruction { target, value },
)?;
}
NodeKind::Root => self.execute_scoped_sequence(
body,
node,
position,
size,
depth + 1,
current_precedence,
)?,
}
}
}
SourceNode::Attribute { owner, index } => {
self.copy_source_attribute(*owner, *index)?;
}
SourceNode::Namespace { owner, index } => {
self.copy_source_namespace(*owner, *index)?;
}
}
Ok(())
}
Instruction::Element { body, .. } => {
self.begin_computed_element(
instruction,
node,
ApplyFrame::new(position, size, depth),
current_precedence,
)?;
let result = self.execute_scoped_sequence(
body,
node,
position,
size,
depth + 1,
current_precedence,
);
self.output_stack.pop();
result
}
Instruction::Attribute {
name,
namespace,
namespaces: static_namespaces,
body,
} => {
let lexical = self.evaluate_avt(name, node, position, size)?;
let (prefix, local) = split_name(&lexical)?;
let namespace = namespace
.as_ref()
.map(|value| self.evaluate_avt(value, node, position, size))
.transpose()?;
let namespace = match namespace {
Some(namespace) => Some(namespace),
None => prefix
.as_deref()
.and_then(|prefix| static_namespace(static_namespaces, prefix))
.map(|uri| MeteredString::from_borrowed(uri, &mut self.meter))
.transpose()?,
};
let (namespace, namespace_reservation) = match namespace {
Some(namespace) => {
let (namespace, reservation) = namespace.into_parts();
(Some(namespace), reservation)
}
None => (None, 0),
};
let (prefix, namespace) =
normalize_computed_namespace(prefix, namespace, &lexical)?;
validate_computed_attribute_name(prefix.as_deref(), &local, namespace.as_deref())?;
require_bound_computed_prefix(prefix.as_deref(), namespace.as_deref(), &lexical)?;
let value =
self.capture_text(body, node, position, size, depth, current_precedence)?;
let value = value.transfer(&mut self.meter);
lexical.release(&mut self.meter);
self.meter.release_owned_bytes(namespace_reservation);
self.add_attribute(Attribute {
name: ExpandedName::new(namespace, local),
prefix,
value,
})
}
Instruction::Comment(body) => {
let value =
self.capture_text(body, node, position, size, depth, current_precedence)?;
let value = value.transfer(&mut self.meter);
if value.contains("--") || value.ends_with('-') {
return Err(Error::Dynamic(
"xsl:comment produced invalid comment content".into(),
));
}
self.push_node(self.parent(), NodeKind::Comment(value))?;
Ok(())
}
Instruction::Processing { name, body } => {
let target = self.evaluate_avt(name, node, position, size)?;
if target.eq_ignore_ascii_case("xml") || !is_ncname(&target) {
return Err(Error::Dynamic(
"invalid processing-instruction target".into(),
));
}
let value =
self.capture_text(body, node, position, size, depth, current_precedence)?;
let value = value.transfer(&mut self.meter);
if value.contains("?>") {
return Err(Error::Dynamic("processing instruction contains ?>".into()));
}
let target = target.transfer(&mut self.meter);
self.push_node(
self.parent(),
NodeKind::ProcessingInstruction {
target,
value: (!value.is_empty()).then_some(value),
},
)?;
Ok(())
}
Instruction::Number(number) => {
let explicit_value = if let Some(expression) = &number.value {
Some(
self.evaluate(expression, node, position, size)?
.into_number(&self.evaluator, &mut self.meter)?,
)
} else {
None
};
let (values, values_owned_bytes) = if explicit_value.is_some() {
(Vec::new(), 0)
} else {
self.number_sequence(number, node)?
};
let values = explicit_value
.as_ref()
.map_or(values.as_slice(), std::slice::from_ref);
if values.is_empty() {
self.meter.release_owned_bytes(values_owned_bytes);
return Ok(());
}
if number.value.is_some()
&& let [value] = values
&& (!value.is_finite() || *value < 0.5)
{
return self.append_text(&super::value::format_xpath_number(*value), false);
}
let grouping_separator_value = number
.grouping_separator
.as_ref()
.map(|value| self.evaluate_avt(value, node, position, size))
.transpose()?;
let grouping_separator = grouping_separator_value
.as_ref()
.map(|value| {
let mut characters = value.chars();
let Some(first) = characters.next() else {
return Ok(None);
};
if characters.next().is_some() {
if number.forward_compatible {
return Ok(None);
}
return Err(Error::Dynamic(
"xsl:number grouping-separator must evaluate to at most one character"
.into(),
));
}
Ok(Some(first))
})
.transpose()?
.flatten();
let grouping_size_value = number
.grouping_size
.as_ref()
.map(|value| self.evaluate_avt(value, node, position, size))
.transpose()?;
let grouping_size = grouping_size_value
.as_ref()
.and_then(|value| parse_xpath_number(value))
.filter(|value| value.is_finite())
.filter(|value| *value > 0.0)
.map(|value| value as usize)
.filter(|value| *value > 0);
let format = self.evaluate_avt(&number.format, node, position, size)?;
let lang = number
.lang
.as_ref()
.map(|value| self.evaluate_avt(value, node, position, size))
.transpose()?;
let letter_value = number
.letter_value
.as_ref()
.map(|value| self.evaluate_avt(value, node, position, size))
.transpose()?;
let effective_letter_value = match letter_value.as_deref() {
None | Some("alphabetic" | "traditional") => letter_value.as_deref(),
Some(_) if number.forward_compatible => None,
Some(value) => {
return Err(Error::Dynamic(format!(
"xsl:number letter-value must evaluate to alphabetic or traditional, got `{value}`"
)));
}
};
let formatted = format_number_sequence(
values,
&format,
lang.as_deref(),
effective_letter_value,
grouping_separator,
grouping_size,
&mut self.meter,
);
grouping_separator_value
.into_iter()
.for_each(|value| value.release(&mut self.meter));
grouping_size_value
.into_iter()
.for_each(|value| value.release(&mut self.meter));
format.release(&mut self.meter);
lang.into_iter()
.for_each(|value| value.release(&mut self.meter));
letter_value
.into_iter()
.for_each(|value| value.release(&mut self.meter));
self.meter.release_owned_bytes(values_owned_bytes);
let formatted = formatted?;
let (formatted, reservation) = formatted.into_parts();
self.append_precharged_text(formatted, reservation, false)
}
Instruction::Variable(variable) => {
let retained = self.evaluate_variable(
variable,
node,
position,
size,
depth,
current_precedence,
)?;
self.scopes
.last_mut()
.ok_or_else(|| Error::Dynamic("missing variable scope".into()))?
.insert_retained(&variable.name, retained, &mut self.meter)?;
Ok(())
}
Instruction::Message { terminate, body } => {
self.meter.charge(BudgetKind::Messages, 1)?;
let fragment = self.capture_fragment(
body,
node,
ApplyFrame::new(position, size, depth),
current_precedence,
None,
)?;
let content = self.consume_temporary_fragment(fragment, serialize_fragment)?;
if *terminate {
return Err(terminating_message_error(content, &mut self.meter)?);
}
reserve_retained_vec_slot(&mut self.messages, &mut self.meter)?;
self.messages.push(Message {
content,
terminate: false,
});
Ok(())
}
Instruction::SecondaryOutput {
uri,
properties,
body,
} => {
let uri = self.evaluate_avt(uri, node, position, size)?;
if uri.is_empty() {
return Err(Error::Dynamic(
"secondary-output URI must not be empty".into(),
));
}
if self.secondary_output_uris.contains(&uri.value) {
return Err(Error::Dynamic(format!(
"secondary-output URI `{uri}` was produced more than once"
)));
}
let uri = uri.transfer(&mut self.meter);
let uri_owned_bytes = uri.capacity().saturating_add(
std::mem::size_of::<String>()
.saturating_add(2usize.saturating_mul(std::mem::size_of::<usize>())),
);
self.meter.charge(BudgetKind::OwnedBytes, uri_owned_bytes)?;
reserve_retained_hash_set_slot(
&mut self.secondary_output_uris,
&mut self.meter,
&mut self.secondary_output_uri_index_bytes,
)?;
let uri = Arc::new(uri);
self.secondary_output_uris.insert(Arc::clone(&uri));
let definition_owned_bytes = self.stylesheet.output.owned_bytes();
self.meter
.charge(BudgetKind::OwnedBytes, definition_owned_bytes)?;
let mut definition = self.stylesheet.output.clone();
let output = (|| {
for (name, value) in properties {
let value = self.evaluate_avt(value, node, position, size)?;
let value = value.transfer(&mut self.meter);
apply_secondary_output_property(
&mut definition,
name,
value,
&mut self.meter,
)?;
}
let fragment = self.capture_output_tree(
body,
node,
ApplyFrame::new(position, size, depth + 1),
current_precedence,
None,
)?;
let serialized = self
.consume_temporary_fragment(fragment, |fragment, meter| {
serialize(fragment, &definition, meter)
})?;
reserve_retained_vec_slot(&mut self.secondary_outputs, &mut self.meter)?;
self.secondary_outputs
.push(SecondaryOutput { uri, serialized });
Ok(())
})();
self.meter.release_owned_bytes(definition.owned_bytes());
output
}
Instruction::ExtensionFallback {
name,
present,
body,
} => {
if !present {
return Err(Error::Unsupported(format!(
"extension element {name} has no xsl:fallback"
)));
}
self.execute_scoped_sequence(
body,
node,
position,
size,
depth + 1,
current_precedence,
)
}
Instruction::CompatibilityComment(value) => {
self.push_node(self.parent(), NodeKind::Comment(value.clone()))?;
Ok(())
}
Instruction::FunctionResult {
select,
content,
base_uri,
} => {
self.ensure_function_result_is_pending()?;
let value = if let Some(select) = select {
xpath_to_public(self.evaluate(select, node, position, size)?)
} else {
Value::ResultTreeFragment(Arc::new(self.capture_fragment(
content,
node,
ApplyFrame::new(position, size, depth + 1),
current_precedence,
base_uri.as_deref(),
)?))
};
self.ensure_function_result_is_pending()?;
self.exslt_calls.set_result(value);
Ok(())
}
}
}
fn ensure_function_result_is_pending(&self) -> Result<()> {
let Some(is_pending) = self.exslt_calls.result_is_pending() else {
return Err(Error::Dynamic(
"func:result executed outside an EXSLT function".into(),
));
};
if !is_pending {
return Err(Error::Dynamic(
"EXSLT function produced more than one result".into(),
));
}
Ok(())
}
fn evaluate(
&mut self,
expression: &super::compiler::Expression,
node: &SourceNode,
position: usize,
size: usize,
) -> Result<XPathValue> {
self.meter.charge(BudgetKind::XPathEvaluations, 1)?;
self.meter.charge(BudgetKind::XPathOperations, 1)?;
self.evaluate_after_charge(expression, node, position, size)
}
fn evaluate_after_charge(
&mut self,
expression: &super::compiler::Expression,
node: &SourceNode,
position: usize,
size: usize,
) -> Result<XPathValue> {
self.ensure_expression_globals(expression)?;
let uses_key = xpath_calls_key(&expression.source);
if let Some(name) = direct_variable_reference(expression)?
&& let Some(value) = self.scopes.iter().rev().find_map(|scope| scope.get(&name))
&& let Some(value) = clone_allocation_free_variable_value(value)
{
return Ok(value);
}
match trim_xml_whitespace(&expression.source) {
"." => {
return Ok(XPathValue::NodeSet(self.evaluator.singleton(
node,
true,
&mut self.meter,
)?));
}
"@*" => {
return Ok(XPathValue::NodeSet(
self.evaluator.attributes(node, &mut self.meter)?,
));
}
_ => {}
}
if let Some(value) = self.evaluate_scalar_fast(expression, node)? {
return Ok(value);
}
if let Some(value) = self.evaluate_rtf_order(expression, node)? {
return Ok(XPathValue::Number(value));
}
let (mut variables, mut reserved_owned_bytes) = self.variables()?;
let custom_calls = CustomCallSession::default();
loop {
if uses_key {
self.ensure_key_indexes_for_all_documents(
&expression.source,
&expression.namespaces,
)?;
}
let document_count = self.evaluator.source.logical_roots().len();
let value = self.evaluator.evaluate(
expression,
node,
position,
size,
&variables,
&mut self.meter,
Some(&custom_calls),
);
let dynamic_variables = self.evaluator.take_dynamic_variable_requests();
if dynamic_variables
.names
.iter()
.any(|name| self.pending_globals.contains_key(name))
{
self.meter.release_owned_bytes(reserved_owned_bytes);
drop(variables);
let mut initialized = Ok(());
for name in &dynamic_variables.names {
if self.pending_globals.contains_key(name)
&& let Err(error) = self.ensure_global(name)
{
initialized = Err(error);
break;
}
}
dynamic_variables.release(&mut self.meter);
initialized?;
(variables, reserved_owned_bytes) = self.variables()?;
self.meter.charge(BudgetKind::XPathEvaluations, 1)?;
self.meter.charge(BudgetKind::XPathOperations, 1)?;
continue;
}
dynamic_variables.release(&mut self.meter);
if let Some((key_slot, logical_root)) = self.evaluator.take_dynamic_key_request() {
self.build_key_slot(key_slot, logical_root)?;
self.meter.charge(BudgetKind::XPathEvaluations, 1)?;
self.meter.charge(BudgetKind::XPathOperations, 1)?;
continue;
}
if uses_key && self.evaluator.source.logical_roots().len() != document_count {
continue;
}
let call = self.evaluator.take_custom_function_call(
&custom_calls,
&variables,
&mut self.meter,
)?;
let Some(call) = call else {
self.meter
.release_owned_bytes(custom_calls.retained_bytes());
self.meter.release_owned_bytes(reserved_owned_bytes);
return value;
};
let function = self
.stylesheet
.functions
.iter()
.filter(|function| function.name == call.name)
.max_by_key(|function| (function.precedence, function.order))
.cloned()
.ok_or_else(|| Error::Dynamic(format!("unknown function {}", call.name.local)))?;
let result = self.call_exslt_function(
&function,
call.arguments,
&call.node,
call.position,
call.size,
)?;
self.evaluator
.complete_custom_function_call(&custom_calls, result, &mut self.meter)?;
self.meter.charge(BudgetKind::XPathEvaluations, 1)?;
self.meter.charge(BudgetKind::XPathOperations, 1)?;
}
}
fn evaluate_rtf_order(
&mut self,
expression: &Expression,
node: &SourceNode,
) -> Result<Option<f64>> {
if !expression
.namespaces
.iter()
.any(|(prefix, namespace)| prefix == "exsl" && namespace == EXSLT_COMMON_NS)
{
return Ok(None);
}
let Some(remainder) = expression
.source
.trim_matches(is_xml_whitespace)
.strip_prefix("count(exsl:node-set($")
else {
return Ok(None);
};
let Some((variable, predicate)) = remainder.split_once(")/*[name() = ") else {
return Ok(None);
};
let Some(target_expression) = predicate.strip_suffix("]/preceding-sibling::*)") else {
return Ok(None);
};
if !variable.chars().all(|character| {
character.is_ascii_alphanumeric() || matches!(character, '_' | '-' | '.' | ':')
}) {
return Ok(None);
}
let (prefix, local) = variable
.split_once(':')
.map_or((None, variable), |(prefix, local)| (Some(prefix), local));
let namespace = prefix
.map(|prefix| {
expression
.namespaces
.iter()
.find(|(candidate, _)| candidate == prefix)
.map(|(_, namespace)| namespace.clone())
.ok_or_else(|| Error::Static(format!("unbound variable prefix {prefix}")))
})
.transpose()?;
let variable = ExpandedName::new(namespace, local);
let Some(Value::ResultTreeFragment(fragment)) = self
.scopes
.iter()
.rev()
.find_map(|scope| scope.get(&variable))
else {
return Ok(None);
};
let (mut targets, reserved_owned_bytes) = match trim_xml_whitespace(target_expression) {
"name(current())" => collect_metered_strings(
std::slice::from_ref(node),
&self.evaluator,
&mut self.meter,
|evaluator, target, visit| evaluator.visit_qualified_name(target, visit),
)?,
path if path.starts_with("current()/") => {
let Some((nodes, node_reservation)) = self.evaluator.relative_nodes(
path.trim_start_matches("current()/"),
node,
&expression.namespaces,
&mut self.meter,
)?
else {
return Ok(None);
};
let targets = collect_metered_strings(
&nodes,
&self.evaluator,
&mut self.meter,
|evaluator, target, visit| evaluator.visit_string_value(target, visit),
);
drop(nodes);
self.meter.release_owned_bytes(node_reservation);
targets?
}
_ => return Ok(None),
};
let result = (|| {
self.meter
.charge(BudgetKind::XPathOperations, targets.len())?;
let max_target_bytes = targets.iter().map(String::len).max().unwrap_or(0);
let comparisons = targets
.len()
.checked_ilog2()
.map_or(0, |power| power as usize + 1);
self.meter.charge(
BudgetKind::XPathOperations,
targets
.len()
.saturating_mul(comparisons)
.saturating_mul(max_target_bytes.max(1)),
)?;
targets.sort_unstable();
targets.dedup();
let Some(root) = fragment.node(fragment.root()) else {
return Ok(Some(0.0));
};
let mut preceding = 0usize;
let mut union_count = 0usize;
for child in &root.children {
self.meter.charge(BudgetKind::XPathOperations, 1)?;
let Some(candidate) = fragment.node(*child) else {
continue;
};
if let NodeKind::Element { name, prefix, .. } = &candidate.kind {
self.meter.charge(
BudgetKind::XPathOperations,
comparisons.saturating_mul(
max_target_bytes
.max(name.local.len().saturating_add(
prefix.as_deref().map_or(0, |value| value.len() + 1),
))
.max(1),
),
)?;
let matched = targets
.binary_search_by(|target| match prefix.as_deref() {
Some(prefix) => target.as_bytes().iter().copied().cmp(
prefix
.bytes()
.chain(std::iter::once(b':'))
.chain(name.local.bytes()),
),
None => target.as_str().cmp(name.local.as_str()),
})
.is_ok();
if matched {
union_count = preceding;
}
preceding += 1;
}
}
Ok(Some(union_count as f64))
})();
self.meter.release_owned_bytes(reserved_owned_bytes);
result
}
fn evaluate_scalar_fast(
&mut self,
expression: &Expression,
node: &SourceNode,
) -> Result<Option<XPathValue>> {
let source = trim_xml_whitespace(&expression.source);
match source {
"self::text()" => {
return Ok(Some(XPathValue::NodeSet(self.evaluator.singleton(
node,
self.evaluator.is_text_node(node),
&mut self.meter,
)?)));
}
"self::*" => {
return Ok(Some(XPathValue::NodeSet(self.evaluator.singleton(
node,
self.evaluator.is_element_node(node),
&mut self.meter,
)?)));
}
"normalize-space(.)" => {
let mut capacity = 0usize;
let mut pending_space = false;
self.evaluator
.visit_string_value_metered(node, &mut self.meter, |value| {
measure_normalized_xpath_space(value, &mut capacity, &mut pending_space);
})?;
self.meter
.check_additional(BudgetKind::OwnedBytes, capacity)?;
let mut output = String::with_capacity(capacity);
let mut pending_space = false;
self.evaluator
.visit_string_value_metered(node, &mut self.meter, |value| {
append_normalized_xpath_space(value, &mut output, &mut pending_space);
})?;
return Ok(Some(XPathValue::String(output)));
}
"concat('<',name(.),'>')" => {
return self
.formatted_qualified_name(node, "<", ">")
.map(XPathValue::String)
.map(Some);
}
"concat('</',name(.),'>')" => {
return self
.formatted_qualified_name(node, "</", ">")
.map(XPathValue::String)
.map(Some);
}
_ => {}
}
if let Some((variable, increment)) = source
.strip_prefix('$')
.and_then(|value| value.split_once('+'))
&& let Some(variable) = lexical_variable_name(variable)
&& let Some(increment) = parse_xpath_number(increment)
{
let Some(number) = self.scalar_variable_number(variable, &expression.namespaces)?
else {
return Ok(None);
};
return Ok(Some(XPathValue::Number(number + increment)));
}
if let Some(arguments) = source
.strip_prefix("substring (")
.and_then(|value| value.strip_suffix(')'))
&& let Some((literal, remainder)) = arguments.split_once(',')
&& let Some(literal) = xpath_string_literal(literal)
&& let Some((start, length)) = remainder.split_once(',')
&& trim_xml_whitespace(start) == "0"
&& let Some((variable, factor)) = length
.trim_matches(is_xml_whitespace)
.strip_prefix('$')
.and_then(|value| value.split_once('*'))
&& let Some(variable) = lexical_variable_name(variable)
&& let Some(factor) = parse_xpath_number(factor)
{
let Some(number) = self.scalar_variable_number(variable, &expression.namespaces)?
else {
return Ok(None);
};
let length = number * factor;
let take = length.round().max(1.0) as usize - 1;
self.meter
.charge(BudgetKind::XPathOperations, literal.len())?;
let end = literal
.char_indices()
.nth(take)
.map_or(literal.len(), |(offset, _)| offset);
self.meter.check_additional(BudgetKind::OwnedBytes, end)?;
return Ok(Some(XPathValue::String(literal[..end].to_owned())));
}
if let Some(variable) = source
.strip_prefix("string-length($")
.and_then(|value| value.strip_suffix(") > 0"))
&& let Some(variable) = lexical_variable_name(variable)
{
let value = self.variable_string(variable, &expression.namespaces, 0)?;
return Ok(Some(XPathValue::Boolean(!value.is_empty())));
}
if let Some(arguments) = source
.strip_prefix("substring-before($")
.and_then(|value| value.strip_suffix(')'))
&& let Some((variable, delimiter)) = arguments.split_once(',')
&& let Some(variable) = lexical_variable_name(variable)
&& let Some(delimiter) = xpath_string_literal(delimiter)
{
let value_len = match self.variable_value(variable, &expression.namespaces)? {
Value::String(value) | Value::StoredExpression(value) => value.len(),
Value::Boolean(true) => "true".len(),
Value::Boolean(false) => "false".len(),
Value::Number(_) | Value::NodeSet(_) | Value::ResultTreeFragment(_) => {
return Ok(None);
}
};
self.meter.charge(BudgetKind::XPathOperations, value_len)?;
self.meter
.charge(BudgetKind::XPathOperations, delimiter.len())?;
let value = self.variable_string(variable, &expression.namespaces, 0)?;
let head = value.split_once(delimiter).map_or("", |(head, _)| head);
let value_workspace = if matches!(&value, Cow::Owned(_)) {
value.len()
} else {
0
};
self.meter.check_additional(
BudgetKind::OwnedBytes,
value_workspace.saturating_add(head.len()),
)?;
return Ok(Some(XPathValue::String(head.to_owned())));
}
if let Some(arguments) = source
.strip_prefix("substring($")
.and_then(|value| value.strip_suffix(')'))
&& let Some((variable, offset)) = arguments.split_once(',')
&& let Some(variable) = lexical_variable_name(variable)
&& let Some(offset) = trim_xml_whitespace(offset).strip_prefix("string-length($")
&& let Some((length_variable, increment)) = offset.split_once(")+")
&& let Some(length_variable) = lexical_variable_name(length_variable)
&& let Ok(increment) = trim_xml_whitespace(increment).parse::<usize>()
{
let value = self.variable_string(variable, &expression.namespaces, 0)?;
let value_workspace = if matches!(&value, Cow::Owned(_)) {
value.len()
} else {
0
};
let length = self
.variable_string(length_variable, &expression.namespaces, value_workspace)?
.chars()
.count();
let start = length.saturating_add(increment).saturating_sub(1);
let start = value
.char_indices()
.nth(start)
.map_or(value.len(), |(offset, _)| offset);
let result = &value[start..];
self.meter.check_additional(
BudgetKind::OwnedBytes,
value_workspace.saturating_add(result.len()),
)?;
return Ok(Some(XPathValue::String(result.to_owned())));
}
if let Some(variable) = source
.strip_prefix("boolean($")
.and_then(|value| value.strip_suffix(')'))
&& let Some(variable) = lexical_variable_name(variable)
{
let value = self.variable_value(variable, &expression.namespaces)?;
return Ok(Some(XPathValue::Boolean(value.boolean())));
}
Ok(None)
}
fn formatted_qualified_name(
&self,
node: &SourceNode,
opening: &str,
closing: &str,
) -> Result<String> {
let mut name_bytes = 0usize;
self.evaluator.visit_qualified_name(node, |segment| {
debug_assert!(name_bytes.checked_add(segment.len()).is_some());
name_bytes += segment.len();
});
debug_assert!(
opening
.len()
.checked_add(name_bytes)
.and_then(|bytes| bytes.checked_add(closing.len()))
.is_some()
);
let output_bytes = opening.len() + name_bytes + closing.len();
self.meter
.check_additional(BudgetKind::OwnedBytes, output_bytes)?;
let mut output = String::with_capacity(output_bytes);
output.push_str(opening);
self.evaluator
.visit_qualified_name(node, |segment| output.push_str(segment));
output.push_str(closing);
Ok(output)
}
fn variable_value(&self, lexical: &str, namespaces: &[(String, String)]) -> Result<&Value> {
let name = expanded_variable_name(lexical, namespaces)?;
self.scopes
.iter()
.rev()
.find_map(|scope| scope.get(&name))
.ok_or_else(|| Error::Dynamic(format!("undefined variable ${lexical}")))
}
fn scalar_variable_number(
&mut self,
lexical: &str,
namespaces: &[(String, String)],
) -> Result<Option<f64>> {
let name = expanded_variable_name(lexical, namespaces)?;
let value = self
.scopes
.iter()
.rev()
.find_map(|scope| scope.get(&name))
.ok_or_else(|| Error::Dynamic(format!("undefined variable ${lexical}")))?;
Ok(Some(match value {
Value::Boolean(value) => f64::from(u8::from(*value)),
Value::Number(value) => *value,
Value::String(value) => {
self.meter
.charge(BudgetKind::XPathOperations, value.len())?;
xpath_number(value)
}
Value::StoredExpression(_) | Value::NodeSet(_) | Value::ResultTreeFragment(_) => {
return Ok(None);
}
}))
}
fn variable_string<'value>(
&'value self,
lexical: &str,
namespaces: &[(String, String)],
concurrent_owned_bytes: usize,
) -> Result<Cow<'value, str>> {
let value = self.variable_value(lexical, namespaces)?;
self.value_string(value, concurrent_owned_bytes)
}
fn value_string<'value>(
&'value self,
value: &'value Value,
concurrent_owned_bytes: usize,
) -> Result<Cow<'value, str>> {
value_string(
value,
&self.evaluator.source,
&self.meter,
concurrent_owned_bytes,
)
}
fn call_exslt_function(
&mut self,
function: &ExsltFunction,
arguments: Vec<Value>,
node: &SourceNode,
position: usize,
size: usize,
) -> Result<Value> {
if arguments.len() > function.params.len() {
return Err(Error::Dynamic(format!(
"EXSLT function {} accepts at most {} arguments, received {}",
function.name.local,
function.params.len(),
arguments.len()
)));
}
let binds_defaults = arguments.len() < function.params.len();
if binds_defaults && self.exslt_calls.binds_defaults(&function.name) {
return Err(Error::Dynamic(format!(
"circular default parameter evaluation in EXSLT function {}",
function.name.local
)));
}
debug_assert!(self.function_depth < usize::MAX);
let depth = self.function_depth + 1;
self.meter
.recursion_with_ceiling(depth, EXECUTION_RECURSION_DEPTH_CEILING)?;
self.exslt_calls
.enter(binds_defaults.then_some(&function.name), &mut self.meter)?;
let caller_scopes = match save_local_scopes(&mut self.scopes, &mut self.meter) {
Ok(saved) => saved,
Err(error) => {
self.exslt_calls.leave(binds_defaults, &mut self.meter);
return Err(error);
}
};
if let Err(error) = self.push_scope() {
self.restore_caller_scopes(caller_scopes);
self.exslt_calls.leave(binds_defaults, &mut self.meter);
return Err(error);
}
let previous_result = match self.enter_result_tree(None, true) {
Ok(previous) => previous,
Err(error) => {
self.restore_caller_scopes(caller_scopes);
self.exslt_calls.leave(binds_defaults, &mut self.meter);
return Err(error);
}
};
self.function_depth = depth;
let parameters = (|| {
for (index, parameter) in function.params.iter().enumerate() {
let retained = if let Some(value) = arguments.get(index) {
let retained_owned_bytes = binding_owned_bytes(¶meter.name, value);
self.meter
.check_additional(BudgetKind::OwnedBytes, retained_owned_bytes)?;
let value = value.clone();
self.meter
.charge(BudgetKind::OwnedBytes, retained_owned_bytes)?;
RetainedValue {
value,
retained_owned_bytes,
}
} else {
self.evaluate_variable(parameter, node, position, size, depth + 1, None)?
};
self.scopes
.last_mut()
.expect("function parameter scope exists")
.insert_retained(¶meter.name, retained, &mut self.meter)?;
}
Ok(())
})();
let execution = parameters.and_then(|()| {
self.execute_sequence(&function.body, node, position, size, depth + 1, None)
});
let value = self.exslt_calls.leave(binds_defaults, &mut self.meter);
let generated_result_nodes = self.result.node_count() > 1;
let temporary_result = self.restore_result_tree(previous_result);
self.meter
.release_owned_bytes(metered_document_owned_bytes(&temporary_result));
self.restore_caller_scopes(caller_scopes);
debug_assert!(self.function_depth > 0);
self.function_depth -= 1;
execution?;
if generated_result_nodes {
return Err(Error::Dynamic(format!(
"EXSLT function {} generated result nodes outside func:result",
function.name.local
)));
}
Ok(value.unwrap_or_else(|| Value::String(String::new())))
}
fn select_nodes(
&mut self,
expression: &super::compiler::Expression,
node: &SourceNode,
position: usize,
size: usize,
) -> Result<(Vec<SourceNode>, usize)> {
self.meter.charge(BudgetKind::XPathEvaluations, 1)?;
let nodes = match trim_xml_whitespace(&expression.source) {
"node()" => self.evaluator.children(node, &mut self.meter)?,
"." => self.evaluator.singleton(node, true, &mut self.meter)?,
"@*" => self.evaluator.attributes(node, &mut self.meter)?,
"preceding-sibling::node()[normalize-space()][1][self::comment()]" => self
.evaluator
.preceding_nonempty_comment(node, &mut self.meter)?,
"@*|node()" | "node()|@*" => self
.evaluator
.attributes_and_children(node, &mut self.meter)?,
_ => {
if let Some(selected) =
self.evaluator
.select_child_axis(expression, node, &mut self.meter)?
{
return Ok(selected);
}
match self.evaluate_after_charge(expression, node, position, size)? {
XPathValue::NodeSet(nodes) => nodes,
value => {
return Err(Error::Dynamic(format!(
"XPath `{}` must return a node-set, received {}",
expression.source,
xpath_value_kind(&value),
)));
}
}
}
};
let reserved_owned_bytes = nodes
.capacity()
.saturating_mul(std::mem::size_of::<SourceNode>());
self.meter
.charge(BudgetKind::OwnedBytes, reserved_owned_bytes)?;
Ok((nodes, reserved_owned_bytes))
}
fn evaluate_variable(
&mut self,
variable: &Variable,
node: &SourceNode,
position: usize,
size: usize,
depth: usize,
current_rule_precedence: Option<usize>,
) -> Result<RetainedValue> {
let value = if let Some(select) = &variable.select {
xpath_to_public(self.evaluate(select, node, position, size)?)
} else if variable.content.is_empty() {
Value::String(String::new())
} else {
Value::ResultTreeFragment(Arc::new(self.capture_fragment(
&variable.content,
node,
ApplyFrame::new(position, size, depth),
current_rule_precedence,
variable.base_uri.as_deref(),
)?))
};
let additional_owned_bytes = expanded_name_owned_bytes(&variable.name).saturating_add(
variable
.select
.as_ref()
.map_or(0, |_| value_owned_bytes(&value)),
);
self.meter
.charge(BudgetKind::OwnedBytes, additional_owned_bytes)?;
let retained_owned_bytes = expanded_name_owned_bytes(&variable.name).saturating_add(
if variable.select.is_some() {
value_owned_bytes(&value)
} else if let Value::ResultTreeFragment(document) = &value {
metered_document_owned_bytes(document)
} else {
0
},
);
Ok(RetainedValue {
retained_owned_bytes,
value,
})
}
fn evaluate_with_params(
&mut self,
parameters: &[super::compiler::WithParam],
node: &SourceNode,
position: usize,
size: usize,
depth: usize,
current_rule_precedence: Option<usize>,
) -> Result<EvaluatedParameters> {
let mut evaluated = EvaluatedParameters::default();
for parameter in parameters {
let retained = match self.evaluate_variable(
¶meter.variable,
node,
position,
size,
depth,
current_rule_precedence,
) {
Ok(retained) => retained,
Err(error) => {
evaluated.release(&mut self.meter);
return Err(error);
}
};
if let Err(error) =
evaluated.insert_retained(¶meter.variable.name, retained, &mut self.meter)
{
evaluated.release(&mut self.meter);
return Err(error);
}
}
Ok(evaluated)
}
fn call_named(
&mut self,
name: &ExpandedName,
params: Arc<EvaluatedParameters>,
node: &SourceNode,
frame: ApplyFrame,
current_rule_precedence: Option<usize>,
) -> Result<()> {
self.meter.recursion(frame.depth)?;
self.meter.charge(BudgetKind::TemplateApplications, 1)?;
let template = self
.stylesheet
.named_template_index
.get(name)
.map(|index| &self.stylesheet.templates[*index])
.ok_or_else(|| Error::Dynamic(format!("named template {} not found", name.local)))?;
self.execute_template(
template,
node.clone(),
params,
frame,
current_rule_precedence,
)
}
fn evaluate_avt(
&mut self,
avt: &AttributeValueTemplate,
node: &SourceNode,
position: usize,
size: usize,
) -> Result<MeteredString> {
let mut output = MeteredString::new();
for part in &avt.0 {
match part {
AvtPart::Literal(value) => {
output.push_str(value, &mut self.meter)?;
}
AvtPart::Expression(expression) => {
let value = self.evaluate(expression, node, position, size)?;
append_avt_expression_value(
&mut output,
value,
&self.evaluator,
&mut self.meter,
)?;
}
}
}
Ok(output)
}
fn sort_nodes(
&mut self,
nodes: &mut [SourceNode],
sorts: &[Sort],
context_node: &SourceNode,
context_position: usize,
context_size: usize,
) -> Result<()> {
if sorts.is_empty() {
return Ok(());
}
let workspace_bytes = sort_workspace_bytes(nodes.len(), sorts.len());
self.meter.charge(BudgetKind::OwnedBytes, workspace_bytes)?;
let mut retained_bytes = 0usize;
let result = (|| {
let mut specs = Vec::with_capacity(sorts.len());
for sort in sorts {
let case_order = sort
.case_order
.as_ref()
.map(|value| {
self.evaluate_avt(value, context_node, context_position, context_size)
})
.transpose()?;
let mut case_order = case_order;
if case_order
.as_ref()
.is_some_and(|value| !matches!(value.as_str(), "upper-first" | "lower-first"))
{
if sort.forward_compatible {
case_order
.take()
.expect("invalid case-order is present")
.release(&mut self.meter);
} else {
let value = case_order.as_ref().expect("invalid case-order is present");
return Err(Error::Dynamic(format!(
"xsl:sort case-order must evaluate to `upper-first` or `lower-first`, got `{value}`"
)));
}
}
let lang = sort
.lang
.as_ref()
.map(|value| {
self.evaluate_avt(value, context_node, context_position, context_size)
})
.transpose()?;
let mut data_type = self.evaluate_avt(
&sort.data_type,
context_node,
context_position,
context_size,
)?;
if !matches!(data_type.as_str(), "text" | "number") {
if sort.forward_compatible {
data_type.value.clear();
data_type.push_str("text", &mut self.meter)?;
} else {
return Err(Error::Dynamic(format!(
"xsl:sort data-type must evaluate to `text` or `number`, got `{data_type}`"
)));
}
}
let collator = match lang.as_deref().filter(|lang| !lang.is_empty()) {
Some(lang) => match locale_collator(lang, case_order.as_deref()) {
Ok(collator) => Some(collator),
Err(_) if sort.forward_compatible => None,
Err(error) => return Err(error),
},
None => None,
};
let mut order =
self.evaluate_avt(&sort.order, context_node, context_position, context_size)?;
if !matches!(order.as_str(), "ascending" | "descending") {
if sort.forward_compatible {
order.value.clear();
order.push_str("ascending", &mut self.meter)?;
} else {
return Err(Error::Dynamic(format!(
"xsl:sort order must evaluate to `ascending` or `descending`, got `{order}`"
)));
}
}
lang.into_iter()
.for_each(|value| value.release(&mut self.meter));
let (data_type, data_type_bytes) = data_type.into_parts();
let (order, order_bytes) = order.into_parts();
let (case_order, case_order_bytes) = case_order.map_or_else(
|| (None, 0),
|value| {
let (value, bytes) = value.into_parts();
(Some(value), bytes)
},
);
let spec = EvaluatedSort {
data_type,
order,
case_order,
collator,
};
let bytes = data_type_bytes
.saturating_add(order_bytes)
.saturating_add(case_order_bytes);
debug_assert_eq!(bytes, spec.owned_bytes());
retained_bytes = retained_bytes
.checked_add(bytes)
.expect("charged sort storage fits usize");
specs.push(spec);
}
let mut keyed = Vec::with_capacity(nodes.len());
for (index, node) in nodes.iter().enumerate() {
let mut keys = Vec::with_capacity(sorts.len());
for (sort, spec) in sorts.iter().zip(&specs) {
let value = self.evaluate(&sort.select, node, index + 1, nodes.len())?;
let key = if spec.data_type == "number" {
SortKey::Number(value.into_number(&self.evaluator, &mut self.meter)?)
} else {
let (value, reservation) = value.into_fully_metered_temporary_string(
&self.evaluator,
&mut self.meter,
)?;
SortKey::text_precharged(value, reservation, &mut self.meter)?
};
retained_bytes = retained_bytes
.checked_add(key.owned_bytes())
.expect("charged sort storage fits usize");
keys.push(key);
}
keyed.push((node.clone(), keys, index));
}
let mut order = (0..keyed.len()).collect::<Vec<_>>();
try_stable_sort_by(&mut order, |left, right| {
let left = &keyed[*left];
let right = &keyed[*right];
self.meter.charge(BudgetKind::SortComparisons, 1)?;
for ((l, r), spec) in left.1.iter().zip(&right.1).zip(&specs) {
let mut ordering = l.compare(
r,
spec.case_order.as_deref(),
spec.collator.as_ref(),
&mut self.meter,
)?;
if spec.order == "descending" {
ordering = ordering.reverse()
}
if ordering != Ordering::Equal {
return Ok(ordering);
}
}
Ok(left.2.cmp(&right.2))
})?;
for (target, index) in nodes.iter_mut().zip(order) {
*target = keyed[index].0.clone()
}
Ok(())
})();
self.meter
.release_owned_bytes(workspace_bytes.saturating_add(retained_bytes));
result
}
fn capture_text(
&mut self,
body: &[Instruction],
node: &SourceNode,
position: usize,
size: usize,
depth: usize,
precedence: Option<usize>,
) -> Result<MeteredString> {
let previous = self.enter_result_tree(None, true)?;
let result =
self.execute_scoped_sequence(body, node, position, size, depth + 1, precedence);
let captured = result.and_then(|()| {
let root = self
.result
.node(self.result.root())
.ok_or_else(|| Error::Dynamic("captured result has no root node".into()))?;
let mut bytes = 0usize;
for child in &root.children {
let Some(NodeKind::Text { value, .. }) =
self.result.node(*child).map(|node| &node.kind)
else {
return Err(Error::Dynamic(
"xsl:attribute, xsl:comment, and xsl:processing-instruction content may produce only text nodes".into(),
));
};
bytes = bytes.saturating_add(value.len());
}
self.meter.charge(BudgetKind::OwnedBytes, bytes)?;
let mut captured = String::with_capacity(bytes);
for child in &root.children {
if let Some(NodeKind::Text { value, .. }) =
self.result.node(*child).map(|node| &node.kind)
{
captured.push_str(value);
}
}
Ok(MeteredString {
value: captured,
retained_owned_bytes: bytes,
})
});
let temporary = self.restore_result_tree(previous);
self.meter
.release_owned_bytes(metered_document_owned_bytes(&temporary));
captured
}
fn consume_temporary_fragment<T>(
&mut self,
fragment: Document,
consume: impl FnOnce(&Document, &mut Meter) -> Result<T>,
) -> Result<T> {
let fragment_owned_bytes = metered_document_owned_bytes(&fragment);
let result = consume(&fragment, &mut self.meter);
self.meter.release_owned_bytes(fragment_owned_bytes);
result
}
fn capture_fragment(
&mut self,
body: &[Instruction],
node: &SourceNode,
frame: ApplyFrame,
precedence: Option<usize>,
base_uri: Option<&str>,
) -> Result<Document> {
self.capture_result_tree(body, node, frame, precedence, base_uri, true)
}
fn capture_output_tree(
&mut self,
body: &[Instruction],
node: &SourceNode,
frame: ApplyFrame,
precedence: Option<usize>,
base_uri: Option<&str>,
) -> Result<Document> {
self.capture_result_tree(body, node, frame, precedence, base_uri, false)
}
fn capture_result_tree(
&mut self,
body: &[Instruction],
node: &SourceNode,
frame: ApplyFrame,
precedence: Option<usize>,
base_uri: Option<&str>,
is_temporary: bool,
) -> Result<Document> {
let previous = self.enter_result_tree(base_uri, is_temporary)?;
let result = self.execute_scoped_sequence(
body,
node,
frame.position,
frame.size,
frame.depth + 1,
precedence,
);
let mut captured = self.restore_result_tree(previous);
let finalized = result.and_then(|()| captured.finalize_xml_ids(&mut self.meter));
match finalized {
Ok(()) => Ok(captured),
Err(error) => {
self.meter
.release_owned_bytes(metered_document_owned_bytes(&captured));
Err(error)
}
}
}
fn empty_metered_result(&mut self, base_uri: Option<&str>) -> Result<Document> {
let document = Document::empty(base_uri.map(str::to_owned));
self.meter.charge(
BudgetKind::OwnedBytes,
metered_document_owned_bytes(&document),
)?;
Ok(document)
}
fn enter_result_tree(
&mut self,
base_uri: Option<&str>,
is_temporary: bool,
) -> Result<ResultTreeState> {
let temporary = self.empty_metered_result(base_uri)?;
let temporary_root = temporary.root();
let mut output_stack = Vec::new();
let mut output_stack_reserved_owned_bytes = 0;
if let Err(error) = reserve_temporary_vec_slot(
&mut output_stack,
&mut self.meter,
&mut output_stack_reserved_owned_bytes,
) {
self.meter
.release_owned_bytes(metered_document_owned_bytes(&temporary));
return Err(error);
}
output_stack.push(temporary_root);
Ok(ResultTreeState {
document: std::mem::replace(&mut self.result, temporary),
output_stack: std::mem::replace(&mut self.output_stack, output_stack),
output_stack_reserved_owned_bytes: std::mem::replace(
&mut self.output_stack_reserved_owned_bytes,
output_stack_reserved_owned_bytes,
),
attribute_insert_position: self.attribute_insert_position.take(),
attribute_protected_names: self.attribute_protected_names.take(),
was_temporary: std::mem::replace(&mut self.result_is_temporary, is_temporary),
})
}
fn restore_result_tree(&mut self, previous: ResultTreeState) -> Document {
let captured = std::mem::replace(&mut self.result, previous.document);
self.meter
.release_owned_bytes(self.output_stack_reserved_owned_bytes);
self.output_stack = previous.output_stack;
self.output_stack_reserved_owned_bytes = previous.output_stack_reserved_owned_bytes;
self.attribute_insert_position = previous.attribute_insert_position;
self.attribute_protected_names = previous.attribute_protected_names;
self.result_is_temporary = previous.was_temporary;
captured
}
fn push_output_node(&mut self, node: NodeId) -> Result<()> {
reserve_temporary_vec_slot(
&mut self.output_stack,
&mut self.meter,
&mut self.output_stack_reserved_owned_bytes,
)?;
self.output_stack.push(node);
Ok(())
}
fn copy_document(
&mut self,
document: &Document,
source_id: NodeId,
parent: NodeId,
depth: usize,
instruction_base_uri: Option<&str>,
) -> Result<()> {
self.copy_node_subtree(
CopyDocument::Fragment(document),
source_id,
parent,
depth,
instruction_base_uri,
)
}
fn copy_source(
&mut self,
node: &SourceNode,
parent: NodeId,
depth: usize,
instruction_base_uri: Option<&str>,
) -> Result<()> {
match node {
SourceNode::Node(id) => {
self.copy_node_subtree(
CopyDocument::Source,
*id,
parent,
depth,
instruction_base_uri,
)?;
}
SourceNode::Attribute { owner, index } => {
self.copy_source_attribute(*owner, *index)?;
}
SourceNode::Namespace { owner, index } => {
self.copy_source_namespace(*owner, *index)?;
}
}
Ok(())
}
fn copy_node_subtree(
&mut self,
document: CopyDocument<'_>,
source_id: NodeId,
parent: NodeId,
depth: usize,
instruction_base_uri: Option<&str>,
) -> Result<()> {
let mut pending = Vec::new();
let mut pending_reservation = 0usize;
reserve_temporary_vec_slot(&mut pending, &mut self.meter, &mut pending_reservation)?;
pending.push(PendingCopyNode {
source: source_id,
target_parent: parent,
depth,
use_instruction_base: true,
});
let result = (|| {
while let Some(current) = pending.pop() {
self.meter.recursion(current.depth)?;
let source = match document {
CopyDocument::Source => self.evaluator.source.node(current.source),
CopyDocument::Fragment(document) => document.node(current.source),
}
.ok_or_else(|| Error::Dynamic("stale copy-of source node".into()))?;
let child_count = source.children.len();
let children_use_instruction_base =
current.use_instruction_base && matches!(source.kind, NodeKind::Root);
let target_parent = if matches!(source.kind, NodeKind::Root) {
current.target_parent
} else {
let inherited_base = if current.use_instruction_base {
instruction_base_uri
} else {
self.result
.node(current.target_parent)
.and_then(|node| node.base_uri.as_deref())
};
let base_uri = copied_node_base_uri(&source.kind, inherited_base)?;
let clone_bytes = node_kind_owned_bytes(&source.kind)
.saturating_add(base_uri.as_deref().map_or(0, str::len));
self.result
.reserve_metered_push_containers(current.target_parent, &mut self.meter)?;
self.meter.check_additional(
BudgetKind::ResultNodes,
1usize.saturating_add(node_kind_embedded_nodes(&source.kind)),
)?;
self.meter
.check_additional(BudgetKind::OwnedBytes, clone_bytes)?;
let kind = source.kind.clone();
self.push_node_with_base(current.target_parent, kind, base_uri)?
};
for index in (0..child_count).rev() {
let child = match document {
CopyDocument::Source => self.evaluator.source.node(current.source),
CopyDocument::Fragment(document) => document.node(current.source),
}
.and_then(|source| source.children.get(index).copied())
.ok_or_else(|| Error::Dynamic("stale copy-of source child".into()))?;
reserve_temporary_vec_slot(
&mut pending,
&mut self.meter,
&mut pending_reservation,
)?;
pending.push(PendingCopyNode {
source: child,
target_parent,
depth: current.depth.saturating_add(1),
use_instruction_base: children_use_instruction_base,
});
}
}
Ok(())
})();
drop(pending);
self.meter.release_owned_bytes(pending_reservation);
result
}
fn copy_source_attribute(&mut self, owner: NodeId, index: usize) -> Result<()> {
let attribute = match self.evaluator.source.node(owner).map(|node| &node.kind) {
Some(NodeKind::Element { attributes, .. }) => attributes.get(index),
_ => None,
};
if let Some(attribute) = attribute {
self.meter
.check_additional(BudgetKind::OwnedBytes, attribute_owned_bytes(attribute))?;
self.add_attribute(attribute.clone())?;
}
Ok(())
}
fn copy_source_namespace(&mut self, owner: NodeId, index: usize) -> Result<()> {
let namespace = match self.evaluator.source.node(owner).map(|node| &node.kind) {
Some(NodeKind::Element { namespaces, .. }) => namespaces.get(index),
_ => None,
};
if let Some(namespace) = namespace {
self.meter
.check_additional(BudgetKind::OwnedBytes, namespace_owned_bytes(namespace))?;
self.add_namespace(namespace.clone())?;
}
Ok(())
}
fn apply_attribute_sets(
&mut self,
names: &[ExpandedName],
node: &SourceNode,
frame: ApplyFrame,
current_precedence: Option<usize>,
) -> Result<()> {
let declarations = Arc::clone(&self.stylesheet.attribute_sets);
let mut expansion = AttributeSetExpansion::new(&declarations);
let result = (|| {
for name in names {
self.apply_attribute_set(name, node, frame, current_precedence, &mut expansion)?;
}
Ok(())
})();
self.meter
.release_owned_bytes(expansion.reserved_owned_bytes);
result
}
fn apply_attribute_set<'s>(
&mut self,
name: &'s ExpandedName,
node: &SourceNode,
frame: ApplyFrame,
current_precedence: Option<usize>,
expansion: &mut AttributeSetExpansion<'s>,
) -> Result<()> {
expansion.push(name, &mut self.meter)?;
let (sets, sets_reservation) = match select_attribute_set_declarations(
expansion.declarations,
name,
&mut self.meter,
) {
Ok(selected) => selected,
Err(error) => {
expansion.active.pop();
return Err(error);
}
};
let mut previous_protected = self.attribute_protected_names.take();
let mut outer_protected = None;
let result = (|| {
let mut cursor = 0;
while cursor < sets.len() {
let precedence = sets[cursor].precedence;
if cursor == 0 {
self.attribute_protected_names = previous_protected.take();
} else {
let retired = self.attribute_protected_names.take();
if outer_protected.is_none() {
outer_protected = retired;
} else if let Some(retired) = retired {
retired.release(&mut self.meter);
}
self.attribute_protected_names = Some(self.current_attribute_names()?);
}
while cursor < sets.len() && sets[cursor].precedence == precedence {
let set = sets[cursor];
let set_start = self.current_attribute_count()?;
for used in &set.uses {
self.apply_attribute_set(
used,
node,
ApplyFrame::new(frame.position, frame.size, frame.depth + 1),
current_precedence,
expansion,
)?
}
let previous_position = self.attribute_insert_position.replace(set_start);
let execution = self.execute_sequence(
&set.attributes,
node,
frame.position,
frame.size,
frame.depth + 1,
current_precedence,
);
self.attribute_insert_position = previous_position;
execution?;
cursor += 1;
}
}
Ok(())
})();
let active_protection = self.attribute_protected_names.take();
if let Some(outer) = outer_protected {
if let Some(active_protection) = active_protection {
active_protection.release(&mut self.meter);
}
self.attribute_protected_names = Some(outer);
} else {
self.attribute_protected_names = active_protection;
}
drop(sets);
self.meter.release_owned_bytes(sets_reservation);
result?;
expansion.active.pop();
Ok(())
}
fn parent(&self) -> NodeId {
self.output_stack
.last()
.copied()
.unwrap_or_else(|| self.result.root())
}
fn push_node(&mut self, parent: NodeId, kind: NodeKind) -> Result<NodeId> {
push_result_node(&mut self.result, &mut self.meter, parent, kind)
}
fn push_node_with_base(
&mut self,
parent: NodeId,
kind: NodeKind,
base_uri: Option<String>,
) -> Result<NodeId> {
self.result
.reserve_metered_push_containers(parent, &mut self.meter)?;
self.meter
.charge(BudgetKind::OwnedBytes, node_kind_owned_bytes(&kind))?;
self.meter.charge(
BudgetKind::OwnedBytes,
base_uri.as_deref().map_or(0, str::len),
)?;
self.meter.charge(
BudgetKind::ResultNodes,
1usize.saturating_add(node_kind_embedded_nodes(&kind)),
)?;
Ok(self.result.push(parent, kind, base_uri))
}
fn push_xsl_copy_element(
&mut self,
name: ExpandedName,
prefix: Option<String>,
namespaces: Arc<Vec<Namespace>>,
base_uri: Option<&str>,
) -> Result<NodeId> {
let parent = self.parent();
self.result
.reserve_metered_push_containers(parent, &mut self.meter)?;
let owned_bytes = expanded_name_owned_bytes(&name)
.saturating_add(prefix.as_ref().map_or(0, String::len))
.saturating_add(base_uri.map_or(0, str::len));
self.meter
.check_additional(BudgetKind::OwnedBytes, owned_bytes)?;
self.meter.check_additional(
BudgetKind::ResultNodes,
1usize.saturating_add(namespaces.len()),
)?;
self.meter.charge(BudgetKind::OwnedBytes, owned_bytes)?;
self.meter.charge(
BudgetKind::ResultNodes,
1usize.saturating_add(namespaces.len()),
)?;
Ok(self.result.push(
parent,
NodeKind::Element {
name,
prefix,
attributes: Vec::new(),
namespaces,
},
base_uri.map(str::to_owned),
))
}
fn append_text(&mut self, value: &str, disable: bool) -> Result<()> {
self.append_text_value(Cow::Borrowed(value), disable)
}
fn append_source_leaf_text(&mut self, node: &SourceNode, disable: bool) -> Result<()> {
let parent = self.parent();
let Some(value) = self.evaluator.borrowed_leaf_string_value(node) else {
return Ok(());
};
append_result_text(
&mut self.result,
&mut self.meter,
parent,
Cow::Borrowed(value),
disable && !self.result_is_temporary,
)
}
fn append_xpath_text(&mut self, value: XPathValue, disable: bool) -> Result<()> {
let (value, reservation) =
value.into_fully_metered_temporary_string(&self.evaluator, &mut self.meter)?;
self.append_precharged_text(value, reservation, disable)
}
fn append_precharged_text(
&mut self,
value: String,
reservation: usize,
disable: bool,
) -> Result<()> {
let parent = self.parent();
append_precharged_result_text(
&mut self.result,
&mut self.meter,
parent,
value,
reservation,
disable && !self.result_is_temporary,
)
}
fn append_text_value(&mut self, value: Cow<'_, str>, disable: bool) -> Result<()> {
let parent = self.parent();
append_result_text(
&mut self.result,
&mut self.meter,
parent,
value,
disable && !self.result_is_temporary,
)
}
fn add_attribute(&mut self, attribute: Attribute) -> Result<()> {
self.add_attribute_with_position(attribute, AttributePosition::Back, false)
}
fn add_literal_attribute(&mut self, attribute: Attribute) -> Result<()> {
self.add_attribute_with_position(attribute, AttributePosition::Back, true)
}
fn add_attribute_with_position(
&mut self,
mut attribute: Attribute,
position: AttributePosition,
element_base_includes_attribute: bool,
) -> Result<()> {
let parent = self.parent();
let protected = self
.attribute_protected_names
.as_ref()
.is_some_and(|protected| {
let fingerprint = protected.fingerprints.hasher().hash_one(&attribute.name);
protected.fingerprints.contains(&fingerprint)
&& self.result.node(parent).is_some_and(|node| {
matches!(
&node.kind,
NodeKind::Element { attributes, .. }
if attributes[..protected.protected_count]
.iter()
.any(|existing| existing.name == attribute.name)
)
})
});
if protected {
return Ok(());
}
const XML_NS: &str = "http://www.w3.org/XML/1998/namespace";
let effective_base = if !element_base_includes_attribute
&& attribute.name.namespace.as_deref() == Some(XML_NS)
&& attribute.name.local == "base"
{
let inherited = self
.result
.node(parent)
.and_then(|node| node.base_uri.as_deref());
Some(super::resolver::resolve_uri_reference(
inherited,
&attribute.value,
)?)
} else {
None
};
let node = self
.result
.node_mut(parent)
.ok_or_else(|| Error::Dynamic("attribute has no result parent".into()))?;
let NodeKind::Element {
attributes,
namespaces,
..
} = &mut node.kind
else {
return Err(Error::Dynamic(
"attribute cannot be added after a non-element result".into(),
));
};
if !node.children.is_empty() {
return Err(Error::Dynamic(
"attribute cannot be added after result children".into(),
));
}
let namespaces = make_namespaces_mut_metered(namespaces, &mut self.meter)?;
let generated_namespace = fixup_attribute_namespace(&mut attribute, namespaces);
if generated_namespace.is_some() {
self.meter.charge(BudgetKind::ResultNodes, 1)?;
reserve_retained_vec_slot(namespaces, &mut self.meter)?;
}
let existing_index = attributes
.iter()
.position(|existing| existing.name == attribute.name);
if existing_index.is_none() {
self.meter.charge(BudgetKind::ResultNodes, 1)?;
reserve_retained_vec_slot(attributes, &mut self.meter)?;
}
let owned_bytes = attribute_owned_bytes(&attribute).saturating_add(
generated_namespace
.as_ref()
.map_or(0, namespace_owned_bytes),
);
self.meter.charge(BudgetKind::OwnedBytes, owned_bytes)?;
if let Some(base_uri) = &effective_base {
self.meter.charge(BudgetKind::OwnedBytes, base_uri.len())?;
}
namespaces.extend(generated_namespace);
let mut replaced_owned_bytes = 0usize;
if let Some(existing) = existing_index.map(|index| &mut attributes[index]) {
let replaced = std::mem::replace(existing, attribute);
replaced_owned_bytes = attribute_owned_bytes(&replaced);
} else {
match position {
AttributePosition::Back => {
if let Some(index) = self.attribute_insert_position.as_mut() {
attributes.insert(*index, attribute);
*index += 1;
} else {
attributes.push(attribute);
}
}
}
}
if let Some(base_uri) = effective_base
&& let Some(replaced) = node.base_uri.replace(base_uri)
{
replaced_owned_bytes = replaced_owned_bytes.saturating_add(replaced.len());
}
self.meter.release_owned_bytes(replaced_owned_bytes);
Ok(())
}
fn current_attribute_count(&self) -> Result<usize> {
let node = self
.result
.node(self.parent())
.ok_or_else(|| Error::Dynamic("attribute has no result parent".into()))?;
let NodeKind::Element { attributes, .. } = &node.kind else {
return Err(Error::Dynamic(
"attribute requires an element result".into(),
));
};
Ok(attributes.len())
}
fn current_attribute_names(&mut self) -> Result<ProtectedAttributeNames> {
let node = self
.result
.node(self.parent())
.ok_or_else(|| Error::Dynamic("attribute has no result parent".into()))?;
let NodeKind::Element { attributes, .. } = &node.kind else {
return Err(Error::Dynamic(
"attribute requires an element result".into(),
));
};
let protected_count = attributes.len();
let mut fingerprints = HashSet::new();
let mut index_bytes = 0;
for attribute in attributes {
let fingerprint = fingerprints.hasher().hash_one(&attribute.name);
reserve_retained_hash_set_slot(&mut fingerprints, &mut self.meter, &mut index_bytes)?;
fingerprints.insert(fingerprint);
}
Ok(ProtectedAttributeNames {
fingerprints,
protected_count,
index_bytes,
})
}
fn add_namespace(&mut self, mut namespace: Namespace) -> Result<()> {
let node = self
.result
.node(self.parent())
.ok_or_else(|| Error::Dynamic("namespace has no result parent".into()))?;
let NodeKind::Element {
name,
prefix,
attributes,
namespaces,
} = &node.kind
else {
return Err(Error::Dynamic(
"namespace requires an element result".into(),
));
};
if !node.children.is_empty() {
return Err(Error::Dynamic(
"namespace cannot be added after result children".into(),
));
}
let conflicts_with_element = namespace.prefix == *prefix
&& name.namespace.as_deref() != Some(namespace.uri.as_str());
let conflicts_with_attribute = attributes.iter().any(|attribute| {
attribute.prefix == namespace.prefix
&& attribute.name.namespace.as_deref() != Some(namespace.uri.as_str())
});
if conflicts_with_element || conflicts_with_attribute {
if namespaces
.iter()
.any(|existing| existing.uri == namespace.uri)
{
return Ok(());
}
namespace.prefix = Some(unused_namespace_prefix(namespaces));
}
if namespace.prefix.is_none() && prefix.is_none() && name.namespace.is_none() {
return Ok(());
}
self.meter
.charge(BudgetKind::OwnedBytes, namespace_owned_bytes(&namespace))?;
let replaced_owned_bytes = {
let node = self
.result
.node_mut(self.parent())
.ok_or_else(|| Error::Dynamic("namespace has no result parent".into()))?;
let NodeKind::Element { namespaces, .. } = &mut node.kind else {
return Err(Error::Dynamic(
"namespace requires an element result".into(),
));
};
let namespaces = make_namespaces_mut_metered(namespaces, &mut self.meter)?;
let existing_index = namespaces
.iter()
.position(|existing| existing.prefix == namespace.prefix);
if existing_index.is_none() {
self.meter.charge(BudgetKind::ResultNodes, 1)?;
reserve_retained_vec_slot(namespaces, &mut self.meter)?;
}
if let Some(existing) = existing_index.map(|index| &mut namespaces[index]) {
let replaced_owned_bytes = namespace_owned_bytes(existing);
*existing = namespace;
replaced_owned_bytes
} else {
namespaces.push(namespace);
0
}
};
self.meter.release_owned_bytes(replaced_owned_bytes);
Ok(())
}
fn alias_name(
&self,
name: &ExpandedName,
prefix: Option<&str>,
) -> (ExpandedName, Option<String>) {
let Some(alias) = self.namespace_alias(name.namespace.as_deref()) else {
return (name.clone(), prefix.map(str::to_owned));
};
(
ExpandedName::new(alias.result_namespace.clone(), name.local.clone()),
alias.output_prefix.clone(),
)
}
fn alias_attribute_name(
&self,
name: &ExpandedName,
prefix: Option<&str>,
) -> (ExpandedName, Option<String>) {
if prefix.is_none() {
return (ExpandedName::new(None::<String>, name.local.clone()), None);
}
self.alias_name(name, prefix)
}
fn alias_literal_name_and_namespaces(
&mut self,
name: &ExpandedName,
prefix: Option<&str>,
namespaces: &[Namespace],
) -> Result<(ExpandedName, Option<String>, Vec<Namespace>)> {
let (name, mut prefix) = self.alias_name(name, prefix);
let index_bytes = namespaces
.len()
.saturating_mul(std::mem::size_of::<(u64, usize)>())
.saturating_mul(2);
self.meter.charge(BudgetKind::OwnedBytes, index_bytes)?;
let mut prefix_positions: HashMap<u64, usize> = HashMap::with_capacity(namespaces.len());
let mut result_namespaces =
Vec::<Namespace>::with_capacity(namespaces.len().saturating_add(1));
for namespace in namespaces {
let mapped = self.alias_namespace(namespace);
let mut fingerprint = prefix_positions.hasher().hash_one(mapped.prefix.as_deref());
loop {
if let Some(&existing) = prefix_positions.get(&fingerprint) {
if result_namespaces[existing].prefix == mapped.prefix {
result_namespaces[existing] = mapped;
break;
}
fingerprint = fingerprint.wrapping_add(1);
continue;
}
prefix_positions.insert(fingerprint, result_namespaces.len());
result_namespaces.push(mapped);
break;
}
}
fixup_element_namespace(&name, &mut prefix, &mut result_namespaces);
drop(prefix_positions);
self.meter.release_owned_bytes(index_bytes);
Ok((name, prefix, result_namespaces))
}
fn literal_projection_owned_bytes(
&self,
name: &ExpandedName,
prefix: Option<&str>,
namespaces: &[Namespace],
base_uri: Option<&str>,
) -> usize {
let name_alias = self.namespace_alias(name.namespace.as_deref());
let result_namespace = name_alias
.and_then(|alias| alias.result_namespace.as_deref())
.or(name.namespace.as_deref());
let result_prefix = name_alias
.and_then(|alias| alias.output_prefix.as_deref())
.or(prefix);
let namespace_payload = namespaces.iter().fold(0usize, |total, namespace| {
let alias = self.namespace_alias(Some(namespace.uri.as_str()));
let mapped_prefix = alias
.and_then(|alias| alias.output_prefix.as_deref())
.or(namespace.prefix.as_deref());
let mapped_uri = alias
.and_then(|alias| alias.result_namespace.as_deref())
.unwrap_or(namespace.uri.as_str());
total
.saturating_add(mapped_prefix.map_or(0, str::len))
.saturating_add(mapped_uri.len())
});
let generated_prefix_bytes = "ns_"
.len()
.saturating_add(namespaces.len().saturating_add(1).ilog10() as usize)
.saturating_add(1);
name.local
.len()
.saturating_add(result_namespace.map_or(0, str::len))
.saturating_add(result_prefix.map_or(0, str::len))
.saturating_add(namespace_payload)
.saturating_add(
namespaces
.len()
.saturating_add(1)
.saturating_mul(std::mem::size_of::<Namespace>()),
)
.saturating_add(generated_prefix_bytes)
.saturating_add(result_prefix.map_or(0, str::len))
.saturating_add(result_namespace.map_or(0, str::len))
.saturating_add(base_uri.map_or(0, str::len))
}
fn alias_namespace(&self, namespace: &Namespace) -> Namespace {
let Some(alias) = self.namespace_alias(Some(namespace.uri.as_str())) else {
return namespace.clone();
};
Namespace {
prefix: alias.output_prefix.clone(),
uri: alias.result_namespace.clone().unwrap_or_default(),
}
}
fn namespace_alias(&self, namespace: Option<&str>) -> Option<&NamespaceAlias> {
let index = match namespace {
Some(namespace) => self
.stylesheet
.namespace_alias_index
.get(namespace)
.copied(),
None => self.stylesheet.default_namespace_alias,
}?;
self.stylesheet.namespace_aliases.get(index)
}
fn number_sequence(
&mut self,
instruction: &super::compiler::NumberInstruction,
node: &SourceNode,
) -> Result<(Vec<f64>, usize)> {
let mut lineage = Vec::new();
let mut lineage_owned_bytes = 0;
reserve_temporary_vec_slot(&mut lineage, &mut self.meter, &mut lineage_owned_bytes)?;
lineage.push(node.clone());
let mut cursor = match node {
SourceNode::Node(id) => self.evaluator.source.node(*id).and_then(|node| node.parent),
SourceNode::Attribute { owner, .. } | SourceNode::Namespace { owner, .. } => {
Some(*owner)
}
};
while let Some(id) = cursor {
if let Err(error) = self.meter.charge(BudgetKind::XPathOperations, 1) {
self.meter.release_owned_bytes(lineage_owned_bytes);
return Err(error);
}
if let Err(error) =
reserve_temporary_vec_slot(&mut lineage, &mut self.meter, &mut lineage_owned_bytes)
{
self.meter.release_owned_bytes(lineage_owned_bytes);
return Err(error);
}
lineage.push(SourceNode::Node(id));
cursor = self.evaluator.source.node(id).and_then(|node| node.parent);
}
let (variables, reserved_owned_bytes) = self.variables()?;
let mut matches = |this: &mut Self, candidate: &SourceNode| -> Result<bool> {
if let Some(pattern) = &instruction.count {
this.matches_pattern(pattern, candidate, &variables)
} else {
Ok(same_node_kind_and_name(
&this.evaluator.source,
node,
candidate,
))
}
};
let from = |this: &mut Self, candidate: &SourceNode| -> Result<bool> {
instruction.from.as_ref().map_or(Ok(false), |pattern| {
this.matches_pattern(pattern, candidate, &variables)
})
};
let result = (|| match instruction.level.as_str() {
"single" => {
for candidate in lineage {
if from(self, &candidate)? {
break;
}
if matches(self, &candidate)? {
let mut values = Vec::new();
let mut values_owned_bytes = 0;
reserve_temporary_vec_slot(
&mut values,
&mut self.meter,
&mut values_owned_bytes,
)?;
values.push(self.sibling_number(&candidate, &mut matches)? as f64);
return Ok((values, values_owned_bytes));
}
}
Ok((Vec::new(), 0))
}
"multiple" => {
let mut values = Vec::new();
let mut values_owned_bytes = 0;
for candidate in lineage.into_iter().rev() {
if from(self, &candidate)? {
values.clear();
continue;
}
if matches(self, &candidate)? {
reserve_temporary_vec_slot(
&mut values,
&mut self.meter,
&mut values_owned_bytes,
)?;
values.push(self.sibling_number(&candidate, &mut matches)? as f64);
}
}
Ok((values, values_owned_bytes))
}
"any" => {
let mut count = 0usize;
let logical_root = self
.evaluator
.source
.logical_root_for(node)
.ok_or_else(|| Error::Dynamic("numbering node has no logical root".into()))?;
let node_bytes = std::mem::size_of::<NodeId>();
let mut traversal_bytes = 0usize;
let result = (|| {
self.meter.charge(BudgetKind::OwnedBytes, node_bytes)?;
traversal_bytes = node_bytes;
let mut pending = Vec::with_capacity(1);
pending.push(logical_root);
while let Some(id) = pending.pop() {
self.meter.charge(BudgetKind::XPathOperations, 1)?;
if let Some(source) = self.evaluator.source.node(id) {
let required = pending.len().saturating_add(source.children.len());
if required > pending.capacity() {
let growth = required - pending.capacity();
let growth_bytes = growth.saturating_mul(node_bytes);
self.meter.charge(BudgetKind::OwnedBytes, growth_bytes)?;
traversal_bytes = traversal_bytes.saturating_add(growth_bytes);
pending.reserve_exact(source.children.len());
}
pending.extend(source.children.iter().rev().copied());
}
let candidate = SourceNode::Node(id);
if from(self, &candidate)? {
count = 0;
} else if matches(self, &candidate)? {
count += 1;
}
if &candidate == node {
let mut values = Vec::new();
let mut values_owned_bytes = 0;
if count > 0 {
reserve_temporary_vec_slot(
&mut values,
&mut self.meter,
&mut values_owned_bytes,
)?;
values.push(count as f64);
}
return Ok((values, values_owned_bytes));
}
let is_current_owner = matches!(
node,
SourceNode::Attribute { owner, .. } | SourceNode::Namespace { owner, .. }
if *owner == id
);
if is_current_owner {
if from(self, node)? {
count = 0;
} else if matches(self, node)? {
count += 1;
}
let mut values = Vec::new();
let mut values_owned_bytes = 0;
if count > 0 {
reserve_temporary_vec_slot(
&mut values,
&mut self.meter,
&mut values_owned_bytes,
)?;
values.push(count as f64);
}
return Ok((values, values_owned_bytes));
}
}
Err(Error::Dynamic(
"numbering node is outside its logical document".into(),
))
})();
self.meter.release_owned_bytes(traversal_bytes);
result
}
level => Err(Error::Static(format!(
"unsupported xsl:number level {level}"
))),
})();
self.meter.release_owned_bytes(lineage_owned_bytes);
self.meter.release_owned_bytes(reserved_owned_bytes);
result
}
fn sibling_number(
&mut self,
node: &SourceNode,
matches: &mut impl FnMut(&mut Self, &SourceNode) -> Result<bool>,
) -> Result<usize> {
#[derive(Clone, Copy)]
enum SiblingAxis {
Children { parent: NodeId, count: usize },
}
let axis = match node {
SourceNode::Node(id) => {
let Some(parent) = self.evaluator.source.node(*id).and_then(|node| node.parent)
else {
return Ok(1);
};
let count = self
.evaluator
.source
.node(parent)
.map_or(0, |node| node.children.len());
SiblingAxis::Children { parent, count }
}
SourceNode::Attribute { .. } | SourceNode::Namespace { .. } => {
self.meter.charge(BudgetKind::XPathOperations, 1)?;
return Ok(usize::from(matches(self, node)?));
}
};
let mut count = 0;
let SiblingAxis::Children {
parent,
count: sibling_count,
} = axis;
for index in 0..sibling_count {
self.meter.charge(BudgetKind::XPathOperations, 1)?;
let Some(child) = self
.evaluator
.source
.node(parent)
.and_then(|node| node.children.get(index))
else {
break;
};
let sibling = SourceNode::Node(*child);
if matches(self, &sibling)? {
count += 1;
}
if &sibling == node {
break;
}
}
Ok(count)
}
}
fn terminating_message_error(mut content: String, meter: &mut Meter) -> Result<Error> {
const PREFIX: &str = "xsl:message terminated transformation: ";
reserve_metered_string(&mut content, PREFIX.len(), meter)?;
content.insert_str(0, PREFIX);
Ok(Error::Dynamic(content))
}
fn effective_globals<'a>(
stylesheet: &'a Stylesheet,
meter: &mut Meter,
) -> Result<HashMap<ExpandedName, &'a super::compiler::GlobalVariable>> {
let table_bytes = stylesheet
.globals
.len()
.saturating_mul(std::mem::size_of::<(
ExpandedName,
&super::compiler::GlobalVariable,
)>())
.saturating_mul(2);
meter.charge(BudgetKind::OwnedBytes, table_bytes)?;
let mut effective: HashMap<ExpandedName, &super::compiler::GlobalVariable> =
HashMap::with_capacity(stylesheet.globals.len());
for global in stylesheet.globals.iter() {
if let Some(current) = effective.get_mut(&global.variable.name) {
match global.precedence.cmp(¤t.precedence) {
Ordering::Greater => {
*current = global;
}
Ordering::Equal => {
return Err(Error::Static(format!(
"duplicate global variable {} at equal import precedence",
global.variable.name.local
)));
}
Ordering::Less => {}
}
} else {
let name_bytes = expanded_name_owned_bytes(&global.variable.name);
meter.charge(BudgetKind::OwnedBytes, name_bytes)?;
effective.insert(global.variable.name.clone(), global);
}
}
Ok(effective)
}
fn append_avt_expression_value(
output: &mut MeteredString,
value: XPathValue,
evaluator: &Evaluator,
meter: &mut Meter,
) -> Result<()> {
let (value, temporary_bytes) = value.into_fully_metered_temporary_string(evaluator, meter)?;
let appended = output.push_str(&value, meter);
meter.release_owned_bytes(temporary_bytes);
appended
}
fn clone_parameter_value(
value: &Value,
remap: Option<&HashMap<NodeId, NodeId>>,
meter: &mut Meter,
) -> Result<RetainedValue> {
let requested_owned_bytes = parameter_value_owned_bytes(value, remap);
meter.charge(BudgetKind::OwnedBytes, requested_owned_bytes)?;
let cloned = match (value, remap) {
(Value::NodeSet(nodes), Some(remap)) => {
let retained_nodes = nodes
.iter()
.filter(|node| remap_parameter_node(node, remap).is_some())
.count();
let mut output = Vec::new();
if let Err(error) = output.try_reserve_exact(retained_nodes) {
meter.release_owned_bytes(requested_owned_bytes);
return Err(Error::Dynamic(format!(
"failed to reserve remapped parameter storage: {error}"
)));
}
output.extend(
nodes
.iter()
.filter_map(|node| remap_parameter_node(node, remap)),
);
Value::NodeSet(output)
}
_ => value.clone(),
};
let actual_owned_bytes = value_owned_bytes(&cloned);
if actual_owned_bytes > requested_owned_bytes {
if let Err(error) = meter.charge(
BudgetKind::OwnedBytes,
actual_owned_bytes - requested_owned_bytes,
) {
meter.release_owned_bytes(requested_owned_bytes);
return Err(error);
}
} else {
meter.release_owned_bytes(requested_owned_bytes - actual_owned_bytes);
}
Ok(RetainedValue {
value: cloned,
retained_owned_bytes: actual_owned_bytes,
})
}
fn validate_parameter_value(value: &Value, source: &Document) -> Result<()> {
let Value::NodeSet(nodes) = value else {
return Ok(());
};
for node in nodes {
if node_reference_owner(node).document_identity() != source.identity() {
return Err(Error::Dynamic(
"node-set parameter contains a reference from a foreign document".into(),
));
}
if source.document_order_key(node).is_none() {
return Err(Error::Dynamic(
"node-set parameter contains a stale or out-of-range reference".into(),
));
}
}
Ok(())
}
fn node_reference_owner(node: &NodeReference) -> NodeId {
match node {
NodeReference::Node(id) => *id,
NodeReference::Attribute { owner, .. } | NodeReference::Namespace { owner, .. } => *owner,
}
}
fn parameter_value_owned_bytes(value: &Value, remap: Option<&HashMap<NodeId, NodeId>>) -> usize {
match (value, remap) {
(Value::NodeSet(nodes), Some(remap)) => nodes
.iter()
.filter(|node| remap_parameter_node(node, remap).is_some())
.count()
.saturating_mul(std::mem::size_of::<NodeReference>()),
_ => value_owned_bytes(value),
}
}
fn remap_parameter_node(
node: &NodeReference,
remap: &HashMap<NodeId, NodeId>,
) -> Option<NodeReference> {
match node {
NodeReference::Node(id) => remap.get(id).copied().map(NodeReference::Node),
NodeReference::Attribute { owner, index } => {
remap
.get(owner)
.copied()
.map(|owner| NodeReference::Attribute {
owner,
index: *index,
})
}
NodeReference::Namespace { owner, index } => {
remap
.get(owner)
.copied()
.map(|owner| NodeReference::Namespace {
owner,
index: *index,
})
}
}
}
fn append_normalized_xpath_space(value: &str, output: &mut String, pending_space: &mut bool) {
for character in value.chars() {
if matches!(character, ' ' | '\t' | '\r' | '\n') {
*pending_space = !output.is_empty();
} else {
if *pending_space {
output.push(' ');
*pending_space = false;
}
output.push(character);
}
}
}
fn measure_normalized_xpath_space(value: &str, bytes: &mut usize, pending_space: &mut bool) {
for character in value.chars() {
if matches!(character, ' ' | '\t' | '\r' | '\n') {
*pending_space = *bytes != 0;
} else {
if *pending_space {
*bytes = bytes.saturating_add(1);
*pending_space = false;
}
*bytes = bytes.saturating_add(character.len_utf8());
}
}
}
fn try_stable_sort_by<T: Copy>(
values: &mut [T],
mut compare: impl FnMut(&T, &T) -> Result<Ordering>,
) -> Result<()> {
let mut width = 1usize;
let mut source = values.to_vec();
let mut target = source.clone();
while width < source.len() {
let step = width.saturating_mul(2);
for start in (0..source.len()).step_by(step) {
let middle = start.saturating_add(width).min(source.len());
let end = start.saturating_add(step).min(source.len());
let (mut left, mut right, mut output) = (start, middle, start);
while left < middle && right < end {
if compare(&source[left], &source[right])? != Ordering::Greater {
target[output] = source[left];
left += 1;
} else {
target[output] = source[right];
right += 1;
}
output += 1;
}
while left < middle {
target[output] = source[left];
left += 1;
output += 1;
}
while right < end {
target[output] = source[right];
right += 1;
output += 1;
}
}
std::mem::swap(&mut source, &mut target);
width = width.saturating_mul(2);
}
values.copy_from_slice(&source);
Ok(())
}
fn sort_workspace_bytes(node_count: usize, sort_count: usize) -> usize {
let specs = sort_count.saturating_mul(std::mem::size_of::<EvaluatedSort>());
let keyed = node_count.saturating_mul(std::mem::size_of::<(SourceNode, Vec<SortKey>, usize)>());
let keys = node_count
.saturating_mul(sort_count)
.saturating_mul(std::mem::size_of::<SortKey>());
let order = node_count
.saturating_mul(std::mem::size_of::<usize>())
.saturating_mul(3);
specs
.saturating_add(keyed)
.saturating_add(keys)
.saturating_add(order)
}
fn xpath_calls_key(source: &str) -> bool {
super::expression::has_unprefixed_function_call(source, "key")
}
fn literal_key_name<'a>(
arguments: &'a str,
namespaces: &'a [(String, String)],
) -> Option<Result<(Option<&'a str>, &'a str)>> {
let mut quote = None;
let mut depth = 0usize;
let mut end = arguments.len();
for (index, character) in arguments.char_indices() {
if let Some(active) = quote {
if character == active {
quote = None;
}
continue;
}
match character {
'\'' | '"' => quote = Some(character),
'(' | '[' => depth += 1,
')' | ']' => depth = depth.saturating_sub(1),
',' if depth == 0 => {
end = index;
break;
}
_ => {}
}
}
let lexical = xpath_string_literal(trim_xml_whitespace(&arguments[..end]))?;
let (prefix, local) = lexical
.split_once(':')
.map_or((None, lexical), |(prefix, local)| (Some(prefix), local));
if local.is_empty() || local.contains(':') {
return Some(Err(Error::Dynamic(format!("invalid key QName {lexical}"))));
}
let namespace = match prefix {
Some(prefix) => match static_namespace(namespaces, prefix) {
Some(namespace) => Some(namespace),
None => return Some(Err(Error::Dynamic(format!("unbound key prefix {prefix}")))),
},
None => None,
};
Some(Ok((namespace, local)))
}
fn fixup_attribute_namespace(
attribute: &mut Attribute,
namespaces: &[Namespace],
) -> Option<Namespace> {
const XML_NAMESPACE: &str = "http://www.w3.org/XML/1998/namespace";
let Some(uri) = attribute.name.namespace.as_deref() else {
attribute.prefix = None;
return None;
};
if uri == XML_NAMESPACE {
attribute.prefix = Some("xml".into());
return None;
}
let requested = attribute.prefix.as_deref().filter(|prefix| {
!matches!(*prefix, "xml" | "xmlns")
&& namespaces
.iter()
.find(|namespace| namespace.prefix.as_deref() == Some(*prefix))
.is_none_or(|namespace| namespace.uri == uri)
});
let prefix = requested
.map(str::to_owned)
.or_else(|| {
namespaces
.iter()
.find(|namespace| {
namespace.prefix.is_some()
&& namespace.uri == uri
&& !matches!(namespace.prefix.as_deref(), Some("xml" | "xmlns"))
})
.and_then(|namespace| namespace.prefix.clone())
})
.unwrap_or_else(|| unused_namespace_prefix(namespaces));
if namespaces
.iter()
.all(|namespace| namespace.prefix.as_deref() != Some(&prefix))
{
let namespace = Namespace {
prefix: Some(prefix.clone()),
uri: uri.to_owned(),
};
attribute.prefix = Some(prefix);
return Some(namespace);
}
attribute.prefix = Some(prefix);
None
}
fn fixup_element_namespace(
name: &ExpandedName,
prefix: &mut Option<String>,
namespaces: &mut Vec<Namespace>,
) {
const XML_NAMESPACE: &str = "http://www.w3.org/XML/1998/namespace";
let Some(uri) = name.namespace.as_deref() else {
*prefix = None;
return;
};
if uri == XML_NAMESPACE {
*prefix = Some("xml".into());
return;
}
if matches!(prefix.as_deref(), Some("xml" | "xmlns")) {
*prefix = Some(unused_namespace_prefix(namespaces));
}
let binding = namespaces
.iter()
.position(|namespace| namespace.prefix == *prefix);
match binding {
Some(index) if namespaces[index].uri == uri => {}
Some(index) => {
let replacement = unused_namespace_prefix(namespaces);
namespaces[index].prefix = Some(replacement);
namespaces.push(Namespace {
prefix: prefix.clone(),
uri: uri.to_owned(),
});
}
None => namespaces.push(Namespace {
prefix: prefix.clone(),
uri: uri.to_owned(),
}),
}
}
fn unused_namespace_prefix(namespaces: &[Namespace]) -> String {
let mut index = 1usize;
loop {
let candidate = format!("ns_{index}");
if namespaces
.iter()
.all(|namespace| namespace.prefix.as_deref() != Some(&candidate))
{
return candidate;
}
index = index.saturating_add(1);
}
}
#[derive(Clone)]
enum SortKey {
Text { value: String, default_key: String },
Number(f64),
}
struct EvaluatedSort {
data_type: String,
order: String,
case_order: Option<String>,
collator: Option<CollatorBorrowed<'static>>,
}
impl EvaluatedSort {
fn owned_bytes(&self) -> usize {
self.data_type
.capacity()
.saturating_add(self.order.capacity())
.saturating_add(self.case_order.as_ref().map_or(0, String::capacity))
}
}
impl SortKey {
fn text_precharged(value: String, reservation: usize, meter: &mut Meter) -> Result<Self> {
debug_assert_eq!(reservation, value.capacity());
if let Err(error) = meter.charge(BudgetKind::XPathOperations, value.len()) {
meter.release_owned_bytes(reservation);
return Err(error);
}
let key_bytes = default_collation_key_bytes(&value);
if let Err(error) = meter.charge(BudgetKind::XPathOperations, value.len()) {
meter.release_owned_bytes(reservation);
return Err(error);
}
if let Err(error) = meter.charge(BudgetKind::OwnedBytes, key_bytes) {
meter.release_owned_bytes(reservation);
return Err(error);
}
let default_key = default_collation_key(&value, key_bytes);
let mut key_reservation = key_bytes;
if let Err(error) = reconcile_temporary_capacity(
meter,
&mut key_reservation,
key_bytes,
default_key.capacity(),
) {
meter.release_owned_bytes(reservation.saturating_add(key_reservation));
return Err(error);
}
Ok(Self::Text { value, default_key })
}
fn owned_bytes(&self) -> usize {
match self {
Self::Text { value, default_key } => {
value.capacity().saturating_add(default_key.capacity())
}
Self::Number(_) => 0,
}
}
fn compare(
&self,
other: &Self,
case_order: Option<&str>,
collator: Option<&CollatorBorrowed<'static>>,
meter: &mut Meter,
) -> Result<Ordering> {
match (self, other) {
(
Self::Text {
value: left,
default_key: left_key,
},
Self::Text {
value: right,
default_key: right_key,
},
) => {
if let Some(collator) = collator {
meter.charge(BudgetKind::XPathOperations, left.len())?;
meter.charge(BudgetKind::XPathOperations, right.len())?;
return Ok(collator.compare(left, right));
}
meter.charge(BudgetKind::XPathOperations, left_key.len())?;
meter.charge(BudgetKind::XPathOperations, right_key.len())?;
let primary = left_key.cmp(right_key);
if primary != Ordering::Equal {
return Ok(primary);
}
meter.charge(BudgetKind::XPathOperations, left.len())?;
meter.charge(BudgetKind::XPathOperations, right.len())?;
let secondary = left
.chars()
.flat_map(char::to_lowercase)
.cmp(right.chars().flat_map(char::to_lowercase));
if secondary != Ordering::Equal {
return Ok(secondary);
}
meter.charge(BudgetKind::XPathOperations, left.len())?;
meter.charge(BudgetKind::XPathOperations, right.len())?;
Ok(match case_order {
Some("upper-first") => left.cmp(right),
Some("lower-first") => right.cmp(left),
_ => left.cmp(right),
})
}
(Self::Number(left), Self::Number(right)) => {
Ok(left.partial_cmp(right).unwrap_or_else(|| {
if left.is_nan() && right.is_nan() {
Ordering::Equal
} else if left.is_nan() {
Ordering::Less
} else {
Ordering::Greater
}
}))
}
_ => Ok(Ordering::Equal),
}
}
}
fn default_collation_key_bytes(value: &str) -> usize {
value
.chars()
.flat_map(char::to_lowercase)
.try_fold(0usize, |bytes, character| {
bytes.checked_add(if character == '_' {
char::MAX.len_utf8()
} else {
character.len_utf8()
})
})
.unwrap_or(usize::MAX)
}
fn default_collation_key(value: &str, key_bytes: usize) -> String {
let mut key = String::with_capacity(key_bytes);
for character in value.chars().flat_map(char::to_lowercase) {
key.push(if character == '_' {
char::MAX
} else {
character
});
}
key
}
fn apply_secondary_output_property(
definition: &mut super::OutputDefinition,
name: &str,
value: String,
meter: &mut Meter,
) -> Result<()> {
let replaced_owned_bytes = secondary_output_property_owned_bytes(definition, name)?;
let retains_value = secondary_output_property_retains_value(name)?;
let value_owned_bytes = value.len();
meter.charge(BudgetKind::OwnedBytes, value_owned_bytes)?;
let result = set_secondary_output_property(definition, name, value);
match result {
Ok(()) => {
meter.release_owned_bytes(replaced_owned_bytes);
if !retains_value {
meter.release_owned_bytes(value_owned_bytes);
}
Ok(())
}
Err(error) => {
meter.release_owned_bytes(value_owned_bytes);
Err(error)
}
}
}
fn set_secondary_output_property(
definition: &mut super::OutputDefinition,
name: &str,
value: String,
) -> Result<()> {
let yes_no = |value: &str| match value {
"yes" => Ok(true),
"no" => Ok(false),
_ => Err(Error::Dynamic(format!(
"secondary-output {name} must be yes or no"
))),
};
match name {
"method" => {
let method = match value.as_str() {
"xml" => super::OutputMethod::Xml,
"html" => super::OutputMethod::Html,
"text" => super::OutputMethod::Text,
_ => {
return Err(Error::Dynamic(format!(
"unsupported secondary-output method {value:?}"
)));
}
};
definition.method_explicit = true;
definition.method = method;
}
"version" => definition.version = Some(value),
"encoding" => {
definition.encoding_explicit = true;
definition.encoding = value;
}
"omit-xml-declaration" => definition.omit_xml_declaration = yes_no(&value)?,
"standalone" => definition.standalone = Some(yes_no(&value)?),
"doctype-public" => definition.doctype_public = Some(value),
"doctype-system" => definition.doctype_system = Some(value),
"indent" => {
definition.indent_explicit = true;
definition.indent = yes_no(&value)?;
}
"media-type" => definition.media_type = Some(value),
_ => {
return Err(Error::Dynamic(format!(
"unsupported secondary-output property {name:?}"
)));
}
}
Ok(())
}
fn secondary_output_property_owned_bytes(
definition: &super::OutputDefinition,
name: &str,
) -> Result<usize> {
match name {
"method" | "omit-xml-declaration" | "standalone" | "indent" => Ok(0),
"version" => Ok(definition.version.as_ref().map_or(0, String::len)),
"encoding" => Ok(definition.encoding.len()),
"doctype-public" => Ok(definition.doctype_public.as_ref().map_or(0, String::len)),
"doctype-system" => Ok(definition.doctype_system.as_ref().map_or(0, String::len)),
"media-type" => Ok(definition.media_type.as_ref().map_or(0, String::len)),
_ => Err(Error::Dynamic(format!(
"unsupported secondary-output property {name:?}"
))),
}
}
fn secondary_output_property_retains_value(name: &str) -> Result<bool> {
match name {
"version" | "encoding" | "doctype-public" | "doctype-system" | "media-type" => Ok(true),
"method" | "omit-xml-declaration" | "standalone" | "indent" => Ok(false),
_ => Err(Error::Dynamic(format!(
"unsupported secondary-output property {name:?}"
))),
}
}
fn metered_node_id_snapshot(nodes: &[NodeId], meter: &mut Meter) -> Result<(Vec<NodeId>, usize)> {
let mut snapshot = Vec::new();
let mut reserved_owned_bytes = 0;
for node in nodes.iter().copied() {
if let Err(error) =
reserve_temporary_vec_slot(&mut snapshot, meter, &mut reserved_owned_bytes)
{
meter.release_owned_bytes(reserved_owned_bytes);
return Err(error);
}
snapshot.push(node);
}
Ok((snapshot, reserved_owned_bytes))
}
fn collect_metered_strings(
nodes: &[SourceNode],
evaluator: &Evaluator,
meter: &mut Meter,
mut visit: impl FnMut(&Evaluator, &SourceNode, &mut dyn FnMut(&str)),
) -> Result<(Vec<String>, usize)> {
let mut string_bytes = 0usize;
for node in nodes {
visit(evaluator, node, &mut |segment| {
string_bytes = string_bytes.saturating_add(segment.len());
});
}
let vector_bytes = nodes.len().saturating_mul(std::mem::size_of::<String>());
let expected_bytes = vector_bytes.saturating_add(string_bytes);
meter.charge(BudgetKind::OwnedBytes, expected_bytes)?;
let mut reserved_owned_bytes = expected_bytes;
let result = (|| {
let mut values = Vec::new();
values
.try_reserve_exact(nodes.len())
.map_err(|error| Error::Dynamic(format!("failed to reserve XPath strings: {error}")))?;
reconcile_temporary_capacity(
meter,
&mut reserved_owned_bytes,
vector_bytes,
values
.capacity()
.saturating_mul(std::mem::size_of::<String>()),
)?;
for node in nodes {
let mut bytes = 0usize;
visit(evaluator, node, &mut |segment| {
bytes = bytes.saturating_add(segment.len());
});
let mut value = String::new();
value.try_reserve_exact(bytes).map_err(|error| {
Error::Dynamic(format!("failed to reserve XPath string value: {error}"))
})?;
reconcile_temporary_capacity(
meter,
&mut reserved_owned_bytes,
bytes,
value.capacity(),
)?;
visit(evaluator, node, &mut |segment| value.push_str(segment));
values.push(value);
}
Ok((values, reserved_owned_bytes))
})();
if result.is_err() {
meter.release_owned_bytes(reserved_owned_bytes);
}
result
}
fn reconcile_temporary_capacity(
meter: &mut Meter,
reserved_owned_bytes: &mut usize,
expected: usize,
actual: usize,
) -> Result<()> {
if actual < expected {
let released = expected - actual;
meter.release_owned_bytes(released);
*reserved_owned_bytes -= released;
} else if actual > expected {
let additional = actual - expected;
meter.charge(BudgetKind::OwnedBytes, additional)?;
*reserved_owned_bytes = reserved_owned_bytes.saturating_add(additional);
}
Ok(())
}
fn locale_collator(lang: &str, case_order: Option<&str>) -> Result<CollatorBorrowed<'static>> {
let locale = lang.parse::<Locale>().map_err(|error| {
Error::Dynamic(format!("xsl:sort lang value {lang:?} is invalid: {error}"))
})?;
let mut preferences = CollatorPreferences::from(locale);
preferences.case_first = match case_order {
Some("upper-first") => Some(CollationCaseFirst::Upper),
Some("lower-first") => Some(CollationCaseFirst::Lower),
_ => None,
};
Collator::try_new(preferences, CollatorOptions::default())
.map_err(|error| Error::Dynamic(format!("xsl:sort lang {lang:?} is unavailable: {error}")))
}
fn xpath_to_public(value: XPathValue) -> Value {
match value {
XPathValue::NodeSet(nodes) => Value::NodeSet(nodes),
XPathValue::ResultTreeFragment(document) => Value::ResultTreeFragment(document),
XPathValue::Boolean(value) => Value::Boolean(value),
XPathValue::Number(value) => Value::Number(value),
XPathValue::String(value) => Value::String(value),
XPathValue::StoredExpression(value) => Value::StoredExpression(value),
}
}
fn xpath_value_kind(value: &XPathValue) -> &'static str {
match value {
XPathValue::NodeSet(_) => "node-set",
XPathValue::ResultTreeFragment(_) => "result-tree-fragment",
XPathValue::Boolean(_) => "boolean",
XPathValue::Number(_) => "number",
XPathValue::String(_) => "string",
XPathValue::StoredExpression(_) => "stored-expression",
}
}
fn direct_variable_reference(
expression: &super::compiler::Expression,
) -> Result<Option<ExpandedName>> {
let source = trim_xml_whitespace(&expression.source);
let Some(lexical) = source.strip_prefix('$') else {
return Ok(None);
};
if !is_lexical_variable_name(lexical) {
return Ok(None);
}
expanded_variable_name(lexical, &expression.namespaces).map(Some)
}
fn clone_allocation_free_variable_value(value: &Value) -> Option<XPathValue> {
match value {
Value::Boolean(value) => Some(XPathValue::Boolean(*value)),
Value::Number(value) => Some(XPathValue::Number(*value)),
Value::ResultTreeFragment(document) => {
Some(XPathValue::ResultTreeFragment(Arc::clone(document)))
}
Value::NodeSet(_) | Value::String(_) | Value::StoredExpression(_) => None,
}
}
fn expanded_variable_name(lexical: &str, namespaces: &[(String, String)]) -> Result<ExpandedName> {
let (prefix, local) = lexical
.split_once(':')
.map_or((None, lexical), |(prefix, local)| (Some(prefix), local));
let namespace = prefix
.map(|prefix| {
namespaces
.iter()
.find(|(candidate, _)| candidate == prefix)
.map(|(_, namespace)| namespace.clone())
.ok_or_else(|| Error::Static(format!("unbound variable prefix {prefix}")))
})
.transpose()?;
Ok(ExpandedName::new(namespace, local))
}
fn is_lexical_variable_name(value: &str) -> bool {
let mut parts = value.split(':');
let Some(first) = parts.next() else {
return false;
};
is_ncname(first) && parts.next().is_none_or(is_ncname) && parts.next().is_none()
}
fn lexical_variable_name(value: &str) -> Option<&str> {
let value = value.trim_matches(is_xml_whitespace);
is_lexical_variable_name(value).then_some(value)
}
fn split_name(value: &str) -> Result<(Option<String>, String)> {
if let Some((prefix, local)) = value.split_once(':') {
if local.contains(':') || !is_ncname(prefix) || !is_ncname(local) {
return Err(Error::Dynamic(format!("invalid computed QName {value}")));
}
Ok((Some(prefix.into()), local.into()))
} else if !is_ncname(value) {
Err(Error::Dynamic(format!("invalid computed QName {value}")))
} else {
Ok((None, value.into()))
}
}
fn normalize_computed_namespace(
prefix: Option<String>,
namespace: Option<String>,
lexical: &str,
) -> Result<(Option<String>, Option<String>)> {
const XML_NS: &str = "http://www.w3.org/XML/1998/namespace";
const XMLNS_NS: &str = "http://www.w3.org/2000/xmlns/";
if namespace.as_deref() == Some("") {
return Ok((None, None));
}
if namespace.as_deref() == Some(XMLNS_NS) {
return Err(Error::Dynamic(format!(
"computed QName `{lexical}` uses the reserved xmlns namespace"
)));
}
if namespace.as_deref() == Some(XML_NS) {
return Ok((Some("xml".into()), namespace));
}
if matches!(prefix.as_deref(), Some("xml" | "xmlns")) && namespace.is_some() {
return Ok((None, namespace));
}
Ok((prefix, namespace))
}
fn copied_node_base_uri(kind: &NodeKind, inherited: Option<&str>) -> Result<Option<String>> {
const XML_NS: &str = "http://www.w3.org/XML/1998/namespace";
let explicit = match kind {
NodeKind::Element { attributes, .. } => attributes.iter().find(|attribute| {
attribute.name.namespace.as_deref() == Some(XML_NS) && attribute.name.local == "base"
}),
_ => None,
};
explicit.map_or_else(
|| Ok(inherited.map(str::to_owned)),
|attribute| super::resolver::resolve_uri_reference(inherited, &attribute.value).map(Some),
)
}
fn static_namespace<'a>(namespaces: &'a [(String, String)], prefix: &str) -> Option<&'a str> {
if prefix == "xml" {
return Some("http://www.w3.org/XML/1998/namespace");
}
namespaces
.iter()
.rev()
.find(|(candidate, _)| candidate == prefix)
.map(|(_, uri)| uri.as_str())
}
fn computed_element_namespace<'a>(
namespaces: &'a [(String, String)],
prefix: Option<&str>,
) -> Option<&'a str> {
static_namespace(namespaces, prefix.unwrap_or_default())
}
fn require_bound_computed_prefix(
prefix: Option<&str>,
namespace: Option<&str>,
lexical: &str,
) -> Result<()> {
if let Some(prefix) = prefix
&& namespace.is_none()
{
return Err(Error::Dynamic(format!(
"computed QName `{lexical}` uses unbound prefix `{prefix}`"
)));
}
Ok(())
}
fn validate_computed_attribute_name(
prefix: Option<&str>,
local: &str,
namespace: Option<&str>,
) -> Result<()> {
const XMLNS_NS: &str = "http://www.w3.org/2000/xmlns/";
if (prefix.is_none() && local == "xmlns") || namespace == Some(XMLNS_NS) {
return Err(Error::Dynamic(
"xsl:attribute cannot construct an XML namespace declaration".into(),
));
}
Ok(())
}
fn format_number_sequence(
values: &[f64],
format: &str,
_lang: Option<&str>,
_letter_value: Option<&str>,
separator: Option<char>,
size: Option<usize>,
meter: &mut Meter,
) -> Result<MeteredString> {
if values.is_empty() {
return Ok(MeteredString::new());
}
let (runs, formats, separators) = number_format_run_counts(format);
let token_workspace = runs
.saturating_mul(std::mem::size_of::<(bool, &str)>())
.saturating_add(formats.saturating_mul(std::mem::size_of::<&str>()))
.saturating_add(separators.saturating_mul(std::mem::size_of::<&str>()));
meter.charge(BudgetKind::OwnedBytes, token_workspace)?;
let result = (|| {
let tokens = tokenize_number_format(format);
if tokens.formats.is_empty() {
let mut output = MeteredString::new();
append_metered(&mut output, tokens.prefix, meter)?;
for (index, value) in values.iter().enumerate() {
if index > 0 {
append_metered(&mut output, ".", meter)?;
}
format_number_into(&mut output, *value, "1", separator, size, meter)?;
}
return Ok(output);
}
let mut output = MeteredString::new();
append_metered(&mut output, tokens.prefix, meter)?;
for (index, value) in values.iter().enumerate() {
if index > 0 {
let separator = tokens
.separators
.get(index - 1)
.or_else(|| tokens.separators.last())
.copied()
.unwrap_or(".");
append_metered(&mut output, separator, meter)?;
}
let token = tokens
.formats
.get(index)
.or_else(|| tokens.formats.last())
.copied()
.unwrap_or("1");
format_number_into(&mut output, *value, token, separator, size, meter)?;
}
append_metered(&mut output, tokens.suffix, meter)?;
Ok(output)
})();
meter.release_owned_bytes(token_workspace);
result
}
fn append_metered(output: &mut MeteredString, value: &str, meter: &mut Meter) -> Result<()> {
output.push_str(value, meter)
}
struct NumberFormatTokens<'a> {
prefix: &'a str,
formats: Vec<&'a str>,
separators: Vec<&'a str>,
suffix: &'a str,
}
pub(crate) fn expanded_name_owned_bytes(name: &ExpandedName) -> usize {
name.namespace
.as_ref()
.map_or(0, String::capacity)
.saturating_add(name.local.capacity())
}
fn attribute_owned_bytes(attribute: &Attribute) -> usize {
expanded_name_owned_bytes(&attribute.name)
.saturating_add(attribute.prefix.as_ref().map_or(0, String::capacity))
.saturating_add(attribute.value.capacity())
}
fn append_result_text(
result: &mut Document,
meter: &mut Meter,
parent: NodeId,
value: Cow<'_, str>,
disable: bool,
) -> Result<()> {
if value.is_empty() {
return Ok(());
}
let previous = result
.node(parent)
.and_then(|node| node.children.last().copied());
if let Some(previous) = previous
&& result.node(previous).is_some_and(|node| {
matches!(
&node.kind,
NodeKind::Text {
disable_output_escaping,
..
} if *disable_output_escaping == disable
)
})
{
let temporary_bytes = match &value {
Cow::Owned(value) => Some(value.capacity()),
Cow::Borrowed(_) => None,
};
if let Some(bytes) = temporary_bytes {
meter.charge(BudgetKind::OwnedBytes, bytes)?;
}
let appended = if let Some(NodeKind::Text { value: current, .. }) =
result.node_mut(previous).map(|node| &mut node.kind)
{
append_metered_string(current, &value, meter)
} else {
unreachable!("previous node was checked as text")
};
if let Some(bytes) = temporary_bytes {
meter.release_owned_bytes(bytes);
}
return appended;
}
let retained = match &value {
Cow::Owned(value) => value.capacity(),
Cow::Borrowed(value) => value.len(),
};
meter.check_additional(BudgetKind::OwnedBytes, retained)?;
push_result_node(
result,
meter,
parent,
NodeKind::Text {
value: value.into_owned(),
disable_output_escaping: disable,
},
)?;
Ok(())
}
fn append_precharged_result_text(
result: &mut Document,
meter: &mut Meter,
parent: NodeId,
value: String,
reservation: usize,
disable: bool,
) -> Result<()> {
debug_assert_eq!(reservation, value.capacity());
if value.is_empty() {
meter.release_owned_bytes(reservation);
return Ok(());
}
let previous = result
.node(parent)
.and_then(|node| node.children.last().copied());
if let Some(previous) = previous
&& result.node(previous).is_some_and(|node| {
matches!(
&node.kind,
NodeKind::Text {
disable_output_escaping,
..
} if *disable_output_escaping == disable
)
})
{
let appended = if let Some(NodeKind::Text { value: current, .. }) =
result.node_mut(previous).map(|node| &mut node.kind)
{
append_metered_string(current, &value, meter)
} else {
unreachable!("previous node was checked as text")
};
meter.release_owned_bytes(reservation);
return appended;
}
let base_uri = result.node(parent).and_then(|node| node.base_uri.clone());
let insertion = (|| {
result.reserve_metered_push_containers(parent, meter)?;
meter.charge(
BudgetKind::OwnedBytes,
base_uri.as_deref().map_or(0, str::len),
)?;
meter.charge(BudgetKind::ResultNodes, 1)?;
Ok(result.push(
parent,
NodeKind::Text {
value,
disable_output_escaping: disable,
},
base_uri,
))
})();
if insertion.is_err() {
meter.release_owned_bytes(reservation);
}
insertion.map(|_| ())
}
fn push_result_node(
result: &mut Document,
meter: &mut Meter,
parent: NodeId,
kind: NodeKind,
) -> Result<NodeId> {
let base_uri = result.node(parent).and_then(|node| node.base_uri.clone());
result.reserve_metered_push_containers(parent, meter)?;
meter.charge(BudgetKind::OwnedBytes, node_kind_owned_bytes(&kind))?;
meter.charge(
BudgetKind::OwnedBytes,
base_uri.as_deref().map_or(0, str::len),
)?;
meter.charge(
BudgetKind::ResultNodes,
1usize.saturating_add(node_kind_embedded_nodes(&kind)),
)?;
Ok(result.push(parent, kind, base_uri))
}
fn namespace_owned_bytes(namespace: &Namespace) -> usize {
namespace
.prefix
.as_ref()
.map_or(0, String::capacity)
.saturating_add(namespace.uri.capacity())
}
fn make_namespaces_mut_metered<'a>(
namespaces: &'a mut Arc<Vec<Namespace>>,
meter: &mut Meter,
) -> Result<&'a mut Vec<Namespace>> {
if Arc::strong_count(namespaces) > 1 {
let cloned_bytes = namespaces
.len()
.saturating_mul(std::mem::size_of::<Namespace>())
.saturating_add(namespaces.iter().fold(0usize, |total, namespace| {
total.saturating_add(namespace_owned_bytes(namespace))
}));
meter.charge(BudgetKind::OwnedBytes, cloned_bytes)?;
}
Ok(Arc::make_mut(namespaces))
}
fn node_kind_owned_bytes(kind: &NodeKind) -> usize {
match kind {
NodeKind::Root => 0,
NodeKind::Text { value, .. } | NodeKind::Comment(value) => value.capacity(),
NodeKind::ProcessingInstruction { target, value } => target
.capacity()
.saturating_add(value.as_ref().map_or(0, String::capacity)),
NodeKind::Element {
name,
prefix,
attributes,
namespaces,
} => attributes
.iter()
.fold(
expanded_name_owned_bytes(name)
.saturating_add(prefix.as_ref().map_or(0, String::capacity))
.saturating_add(
attributes
.capacity()
.saturating_mul(std::mem::size_of::<Attribute>()),
)
.saturating_add(
namespaces
.capacity()
.saturating_mul(std::mem::size_of::<Namespace>()),
),
|total, attribute| total.saturating_add(attribute_owned_bytes(attribute)),
)
.saturating_add(namespaces.iter().fold(0usize, |total, namespace| {
total.saturating_add(namespace_owned_bytes(namespace))
})),
}
}
fn node_kind_embedded_nodes(kind: &NodeKind) -> usize {
match kind {
NodeKind::Element {
attributes,
namespaces,
..
} => attributes.len().saturating_add(namespaces.len()),
_ => 0,
}
}
fn value_string<'a>(
value: &'a Value,
source: &'a Document,
meter: &Meter,
concurrent_owned_bytes: usize,
) -> Result<Cow<'a, str>> {
match value {
Value::NodeSet(nodes) => nodes
.iter()
.filter_map(|node| source.document_order_key(node).map(|key| (key, node)))
.min_by_key(|(key, _)| *key)
.map_or_else(
|| Ok(Cow::Borrowed("")),
|(_, node)| node_reference_string(node, source, meter, concurrent_owned_bytes),
),
Value::Boolean(true) => Ok(Cow::Borrowed("true")),
Value::Boolean(false) => Ok(Cow::Borrowed("false")),
Value::Number(value) => {
let value = super::value::format_xpath_number(*value);
meter.check_additional(
BudgetKind::OwnedBytes,
concurrent_owned_bytes.saturating_add(value.len()),
)?;
Ok(Cow::Owned(value))
}
Value::String(value) | Value::StoredExpression(value) => Ok(Cow::Borrowed(value)),
Value::ResultTreeFragment(document) => {
metered_document_string(document, document.root(), meter, concurrent_owned_bytes)
}
}
}
fn node_reference_string<'a>(
node: &NodeReference,
document: &'a Document,
meter: &Meter,
concurrent_owned_bytes: usize,
) -> Result<Cow<'a, str>> {
match node {
NodeReference::Node(id) => {
metered_document_string(document, *id, meter, concurrent_owned_bytes)
}
NodeReference::Attribute { owner, index } => Ok(document
.node(*owner)
.and_then(|node| match &node.kind {
NodeKind::Element { attributes, .. } => attributes.get(*index),
_ => None,
})
.map_or(Cow::Borrowed(""), |attribute| {
Cow::Borrowed(attribute.value.as_str())
})),
NodeReference::Namespace { owner, index } => Ok(document
.node(*owner)
.and_then(|node| match &node.kind {
NodeKind::Element { namespaces, .. } => namespaces.get(*index),
_ => None,
})
.map_or(Cow::Borrowed(""), |namespace| {
Cow::Borrowed(namespace.uri.as_str())
})),
}
}
fn metered_document_string<'a>(
document: &'a Document,
id: NodeId,
meter: &Meter,
concurrent_owned_bytes: usize,
) -> Result<Cow<'a, str>> {
let Some(node) = document.node(id) else {
return Ok(Cow::Borrowed(""));
};
match &node.kind {
NodeKind::Text { value, .. } | NodeKind::Comment(value) => Ok(Cow::Borrowed(value)),
NodeKind::ProcessingInstruction { value, .. } => {
Ok(Cow::Borrowed(value.as_deref().unwrap_or("")))
}
NodeKind::Root | NodeKind::Element { .. } => {
let mut output_bytes = 0usize;
document.visit_string_value(id, |value| {
output_bytes = output_bytes.saturating_add(value.len());
});
meter.check_additional(
BudgetKind::OwnedBytes,
concurrent_owned_bytes.saturating_add(output_bytes),
)?;
let mut output = String::with_capacity(output_bytes);
document.visit_string_value(id, |value| output.push_str(value));
Ok(Cow::Owned(output))
}
}
}
fn push_initializing_global<'a>(
active: &mut Vec<&'a ExpandedName>,
name: &'a ExpandedName,
meter: &mut Meter,
reserved_owned_bytes: &mut usize,
) -> Result<()> {
reserve_temporary_vec_slot(active, meter, reserved_owned_bytes)?;
active.push(name);
Ok(())
}
fn circular_global_dependency_error(
active: &[&ExpandedName],
repeated: &ExpandedName,
meter: &mut Meter,
) -> Result<()> {
let mut message = String::new();
append_metered_string(&mut message, "circular global variable dependency: ", meter)?;
for (index, name) in active.iter().enumerate() {
if index != 0 {
append_metered_string(&mut message, " -> ", meter)?;
}
append_metered_string(&mut message, &name.local, meter)?;
}
append_metered_string(&mut message, " -> ", meter)?;
append_metered_string(&mut message, &repeated.local, meter)?;
Err(Error::Dynamic(message))
}
fn clone_for_xsl_copy(kind: &NodeKind, meter: &Meter) -> Result<NodeKind> {
let copied_bytes = match kind {
NodeKind::Element { name, prefix, .. } => {
expanded_name_owned_bytes(name).saturating_add(prefix.as_ref().map_or(0, String::len))
}
kind => node_kind_owned_bytes(kind),
};
meter.check_additional(BudgetKind::OwnedBytes, copied_bytes)?;
Ok(match kind {
NodeKind::Element {
name,
prefix,
namespaces,
..
} => NodeKind::Element {
name: name.clone(),
prefix: prefix.clone(),
attributes: Vec::new(),
namespaces: namespaces.clone(),
},
kind => kind.clone(),
})
}
fn value_owned_bytes(value: &Value) -> usize {
match value {
Value::NodeSet(nodes) => nodes
.capacity()
.saturating_mul(std::mem::size_of::<NodeReference>()),
Value::Boolean(_) | Value::Number(_) => 0,
Value::String(value) | Value::StoredExpression(value) => value.capacity(),
Value::ResultTreeFragment(_) => std::mem::size_of::<Arc<Document>>(),
}
}
fn metered_document_owned_bytes(document: &Document) -> usize {
document.nodes().fold(
document
.retained_tree_container_bytes()
.saturating_add(document.retained_identity_index_bytes()),
|total, (_, node)| {
total
.saturating_add(node_kind_owned_bytes(&node.kind))
.saturating_add(node.base_uri.as_ref().map_or(0, String::len))
},
)
}
fn binding_owned_bytes(name: &ExpandedName, value: &Value) -> usize {
expanded_name_owned_bytes(name).saturating_add(value_owned_bytes(value))
}
fn visible_variable_snapshot_size(scopes: &[VariableScope]) -> (usize, usize) {
let mut count = 0usize;
let mut payload = 0usize;
for (name, value) in visible_variable_bindings(scopes) {
count = count.saturating_add(1);
payload = payload
.saturating_add(expanded_name_owned_bytes(name))
.saturating_add(value_owned_bytes(value));
}
let table = count
.saturating_mul(std::mem::size_of::<(ExpandedName, Value)>())
.saturating_mul(2);
(count, payload.saturating_add(table))
}
fn visible_variable_bindings(
scopes: &[VariableScope],
) -> impl Iterator<Item = (&ExpandedName, &Value)> {
scopes.iter().enumerate().flat_map(move |(index, scope)| {
scope.iter().filter(move |(name, _)| {
!scopes[index + 1..]
.iter()
.any(|inner| inner.contains_key(*name))
})
})
}
fn tokenize_number_format(format: &str) -> NumberFormatTokens<'_> {
let (run_count, format_count, separator_count) = number_format_run_counts(format);
let mut runs = Vec::<(bool, &str)>::with_capacity(run_count);
let mut run_start = 0usize;
let mut run_kind = None;
for (index, character) in format.char_indices() {
let alphanumeric = character.is_alphanumeric();
if let Some(kind) = run_kind
&& kind != alphanumeric
{
runs.push((kind, &format[run_start..index]));
run_start = index;
}
run_kind = Some(alphanumeric);
}
if let Some(kind) = run_kind {
runs.push((kind, &format[run_start..]));
}
let prefix = runs
.first()
.filter(|(alphanumeric, _)| !*alphanumeric)
.map(|(_, value)| *value)
.unwrap_or_default();
let suffix = runs
.last()
.filter(|(alphanumeric, _)| !*alphanumeric)
.map(|(_, value)| *value)
.unwrap_or_default();
let mut formats = Vec::with_capacity(format_count);
formats.extend(
runs.iter()
.filter(|(alphanumeric, _)| *alphanumeric)
.map(|(_, value)| *value),
);
let mut separators = Vec::with_capacity(separator_count);
separators.extend(
runs.iter()
.skip_while(|(alphanumeric, _)| !*alphanumeric)
.skip(1)
.take_while(|_| true)
.filter(|(alphanumeric, _)| !*alphanumeric)
.map(|(_, value)| *value)
.take(format_count.saturating_sub(1)),
);
NumberFormatTokens {
prefix,
formats,
separators,
suffix,
}
}
fn number_format_run_counts(format: &str) -> (usize, usize, usize) {
let mut previous = None;
let mut runs = 0usize;
let mut formats = 0usize;
let mut separators = 0usize;
for character in format.chars() {
let alphanumeric = character.is_alphanumeric();
if previous != Some(alphanumeric) {
runs = runs.saturating_add(1);
if alphanumeric {
formats = formats.saturating_add(1);
} else {
separators = separators.saturating_add(1);
}
previous = Some(alphanumeric);
}
}
(runs, formats, separators)
}
fn format_number_into(
output: &mut MeteredString,
value: f64,
format: &str,
separator: Option<char>,
size: Option<usize>,
meter: &mut Meter,
) -> Result<()> {
debug_assert!(value.is_nan() || value.round() > 0.0);
if value.is_nan() {
return append_metered(output, "NaN", meter);
}
let rounded = value.round();
if rounded <= 0.0 {
let width = format
.chars()
.filter(|character| unicode_decimal_value(*character).is_some())
.count()
.max(1);
let zero = decimal_zero(format);
return append_localized_decimal(output, "0", width, zero, None, None, meter);
}
match format {
"A" | "a" => {
let decimal = super::value::format_xpath_number(rounded);
let value = alphabetic_decimal(&decimal, format == "A");
append_metered(output, &value, meter)
}
"I" | "i" => {
let value = if rounded <= 3999.0 {
roman(rounded as usize, format == "I")
} else {
super::value::format_xpath_number(rounded)
};
append_metered(output, &value, meter)
}
_ => {
let width = format
.chars()
.filter(|character| unicode_decimal_value(*character).is_some())
.count();
let ascii = format!("{rounded:.0}");
append_localized_decimal(
output,
&ascii,
width,
decimal_zero(format),
separator,
size,
meter,
)
}
}
}
fn decimal_zero(token: &str) -> char {
token
.chars()
.filter_map(|character| {
unicode_decimal_value(character).and_then(|digit| {
u32::from(character)
.checked_sub(digit)
.and_then(char::from_u32)
})
})
.next_back()
.unwrap_or('0')
}
fn append_localized_decimal(
output: &mut MeteredString,
ascii: &str,
width: usize,
zero: char,
separator: Option<char>,
size: Option<usize>,
meter: &mut Meter,
) -> Result<()> {
let ascii_digits = ascii.chars().count();
let digits = width.max(ascii_digits);
let padding = digits.saturating_sub(ascii_digits);
let grouping_size = size.filter(|size| *size > 0);
let groups = grouping_size.map_or(0, |size| digits.saturating_sub(1) / size);
let separator_bytes = separator.zip(grouping_size).map_or(0, |(separator, _)| {
groups.saturating_mul(separator.len_utf8())
});
let digit_bytes = padding
.saturating_mul(zero.len_utf8())
.saturating_add(ascii.chars().fold(0usize, |total, character| {
total.saturating_add(
character
.to_digit(10)
.and_then(|digit| char::from_u32(u32::from(zero) + digit))
.unwrap_or(character)
.len_utf8(),
)
}));
let additional = digit_bytes.saturating_add(separator_bytes);
output.reserve(additional, meter)?;
let mut characters = std::iter::repeat_n(zero, padding).chain(ascii.chars().map(|character| {
character
.to_digit(10)
.and_then(|digit| char::from_u32(u32::from(zero) + digit))
.unwrap_or(character)
}));
for index in 0..digits {
if index > 0
&& let Some((separator, size)) = separator.zip(grouping_size)
&& (digits - index).is_multiple_of(size)
{
output.value.push(separator);
}
let character = characters.next().expect("decimal width matches iterator");
output.value.push(character);
}
Ok(())
}
fn same_node_kind_and_name(document: &Document, left: &SourceNode, right: &SourceNode) -> bool {
match (left, right) {
(
SourceNode::Attribute {
owner: left_owner,
index: left_index,
},
SourceNode::Attribute {
owner: right_owner,
index: right_index,
},
) => {
let attribute = |owner, index| {
document.node(owner).and_then(|node| match &node.kind {
NodeKind::Element { attributes, .. } => attributes.get(index),
_ => None,
})
};
attribute(*left_owner, *left_index).map(|attribute| &attribute.name)
== attribute(*right_owner, *right_index).map(|attribute| &attribute.name)
}
(
SourceNode::Namespace {
owner: left_owner,
index: left_index,
},
SourceNode::Namespace {
owner: right_owner,
index: right_index,
},
) => {
let namespace = |owner, index| {
document.node(owner).and_then(|node| match &node.kind {
NodeKind::Element { namespaces, .. } => namespaces.get(index),
_ => None,
})
};
namespace(*left_owner, *left_index).map(|namespace| &namespace.prefix)
== namespace(*right_owner, *right_index).map(|namespace| &namespace.prefix)
}
(SourceNode::Node(left), SourceNode::Node(right)) => match (
document.node(*left).map(|node| &node.kind),
document.node(*right).map(|node| &node.kind),
) {
(
Some(NodeKind::Element { name: left, .. }),
Some(NodeKind::Element { name: right, .. }),
) => left == right,
(Some(NodeKind::Text { .. }), Some(NodeKind::Text { .. }))
| (Some(NodeKind::Comment(_)), Some(NodeKind::Comment(_)))
| (Some(NodeKind::Root), Some(NodeKind::Root)) => true,
(
Some(NodeKind::ProcessingInstruction { target: left, .. }),
Some(NodeKind::ProcessingInstruction { target: right, .. }),
) => left == right,
_ => false,
},
_ => false,
}
}
fn alphabetic_decimal(decimal: &str, upper: bool) -> String {
let mut digits = decimal
.bytes()
.map(|digit| digit - b'0')
.collect::<Vec<_>>();
let mut start = 0usize;
let mut reversed = Vec::with_capacity(decimal.len());
while start < digits.len() {
let mut borrow = 1u8;
for digit in digits[start..].iter_mut().rev() {
if borrow == 0 {
break;
}
if *digit == 0 {
*digit = 9;
} else {
*digit -= 1;
borrow = 0;
}
}
let mut remainder = 0u16;
for digit in &mut digits[start..] {
let dividend = remainder * 10 + u16::from(*digit);
*digit = (dividend / 26) as u8;
remainder = dividend % 26;
}
let base = if upper { b'A' } else { b'a' };
reversed.push(base + remainder as u8);
while start < digits.len() && digits[start] == 0 {
start += 1;
}
}
reversed.reverse();
String::from_utf8(reversed).expect("alphabetic digits are ASCII")
}
fn roman(mut value: usize, upper: bool) -> String {
if value == 0 || value > 3999 {
return value.to_string();
}
let mut output = String::new();
for (number, numeral) in [
(1000, "M"),
(900, "CM"),
(500, "D"),
(400, "CD"),
(100, "C"),
(90, "XC"),
(50, "L"),
(40, "XL"),
(10, "X"),
(9, "IX"),
(5, "V"),
(4, "IV"),
(1, "I"),
] {
while value >= number {
output.push_str(numeral);
value -= number;
}
}
if upper { output } else { output.to_lowercase() }
}
#[cfg(all(test, not(feature = "embedded")))]
mod tests;