Best headless browser for AI agents. Lite, Fast, High-Compatibility. Built in Rust
Rust ai-agentsai-toolsbrowserbrowser-automationcloud-browserheadlessheadless-browserkitesurfplaywrightpuppeteerrustservoweb-crawlerweb-crawlingweb-scraperweb-scraping
use std::{borrow::Cow, sync::Arc};
use indexmap::IndexSet;
use moli_selector::{
StyloElementDependencySnapshot as StyleElementDependencySnapshot,
stylo_removed_element_dependency_snapshots as removed_element_dependency_snapshots,
};
use smallvec::SmallVec;
use crate::{
document_runtime::DomHandle,
dom::native::{DomHost, DomMutationEffects, Node},
};
const REMOVED_SUBTREE_SNAPSHOT_NODE_LIMIT: usize = 256;
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub(crate) enum StyleMutationEffect {
Attribute {
element: DomHandle,
name: String,
old_value: Option<String>,
new_value: Option<String>,
},
ConnectedSubtrees {
roots: Arc<[DomHandle]>,
},
DisconnectedSubtrees {
roots: Arc<[DomHandle]>,
},
SlotAssignment {
slot: DomHandle,
previous_assigned_nodes: Option<Vec<DomHandle>>,
assigned_nodes: Option<Vec<DomHandle>>,
},
CharacterData {
node: DomHandle,
},
ChildList {
parent: DomHandle,
added_nodes: Vec<DomHandle>,
removed_nodes: Vec<DomHandle>,
removed_element_snapshots: Vec<StyleElementDependencySnapshot>,
previous_sibling: Option<DomHandle>,
next_sibling: Option<DomHandle>,
},
}
impl StyleMutationEffect {
#[cfg(test)]
pub(crate) fn attribute_for_element_ns(
host: &DomHost,
element: DomHandle,
namespace: Option<&str>,
name: &str,
old_value: Option<String>,
new_value: Option<String>,
) -> Self {
Self::Attribute {
element,
name: if namespace.is_some() {
name.to_owned()
} else {
normalized_style_attribute_name(host, element, name)
},
old_value,
new_value,
}
}
pub(crate) fn from_dom_mutation_effects(
host: &DomHost,
effects: &DomMutationEffects,
) -> SmallVec<[Self; 1]> {
// A single text update needs neither deduplication nor a heap buffer.
let style = effects.style();
if let [node] = style.character_data_mutations()
&& style.attribute_mutations().is_empty()
&& style.child_list_mutations().is_empty()
&& effects.tree().connected_roots().is_empty()
&& effects.tree().disconnected_roots().is_empty()
&& effects.slots().assignment_changes().is_empty()
&& effects.slots().changed_slots().is_empty()
{
return SmallVec::from_buf([Self::CharacterData { node: *node }]);
}
let mut style_effects = IndexSet::new();
let connected_roots = effects.tree().connected_roots();
#[cfg(debug_assertions)]
{
let connected_root_set = connected_roots
.iter()
.copied()
.collect::<std::collections::HashSet<_>>();
debug_assert!(
effects
.scripts()
.connected_roots()
.iter()
.all(|root| connected_root_set.contains(root)),
"script connection roots must also be tree connection roots"
);
}
if !connected_roots.is_empty() {
style_effects.insert(Self::ConnectedSubtrees {
roots: shared_tree_roots(
connected_roots,
effects
.style()
.child_list_mutations()
.iter()
.map(|mutation| (mutation.added_nodes(), mutation.shared_added_nodes())),
),
});
}
let disconnected_roots = effects.tree().disconnected_roots();
if !disconnected_roots.is_empty() {
style_effects.insert(Self::DisconnectedSubtrees {
roots: shared_tree_roots(
disconnected_roots,
effects
.style()
.child_list_mutations()
.iter()
.map(|mutation| {
(mutation.removed_nodes(), mutation.shared_removed_nodes())
}),
),
});
}
let detailed_slot_assignment_slots = effects
.slots()
.assignment_changes()
.iter()
.map(|change| change.slot())
.collect::<IndexSet<_>>();
for change in effects.slots().assignment_changes() {
style_effects.insert(Self::SlotAssignment {
slot: change.slot(),
previous_assigned_nodes: Some(change.previous_assigned_nodes().to_vec()),
assigned_nodes: Some(change.assigned_nodes().to_vec()),
});
}
for &slot in effects.slots().changed_slots() {
if detailed_slot_assignment_slots.contains(&slot) {
continue;
}
style_effects.insert(Self::SlotAssignment {
slot,
previous_assigned_nodes: None,
assigned_nodes: None,
});
}
for &node in effects.style().character_data_mutations() {
style_effects.insert(Self::CharacterData { node });
}
for mutation in effects.style().child_list_mutations() {
style_effects.insert(Self::ChildList {
parent: mutation.target(),
added_nodes: mutation.added_nodes().to_vec(),
removed_nodes: mutation.removed_nodes().to_vec(),
removed_element_snapshots: removed_element_dependency_snapshots_for_mutation(
host,
mutation.removed_nodes(),
),
previous_sibling: mutation.previous_sibling(),
next_sibling: mutation.next_sibling(),
});
}
for mutation in effects.style().attribute_mutations() {
let normalized_name = if mutation.namespace().is_some() {
mutation.local_name().to_owned()
} else {
normalized_style_attribute_name(host, mutation.target(), mutation.local_name())
};
style_effects.insert(Self::Attribute {
element: mutation.target(),
name: normalized_name,
old_value: mutation.old_value().map(str::to_owned),
new_value: mutation.new_value().map(str::to_owned),
});
}
style_effects.into_iter().collect()
}
pub(super) fn attribute_dependency_change(&self) -> Option<StyleAttributeDependencyChange<'_>> {
let Self::Attribute {
name,
old_value,
new_value,
..
} = self
else {
return None;
};
Some(StyleAttributeDependencyChange::new(
name,
old_value.as_deref(),
new_value.as_deref(),
))
}
}
fn shared_tree_roots<'a>(
roots: &[DomHandle],
child_list_roots: impl Iterator<Item = (&'a [DomHandle], Arc<[DomHandle]>)>,
) -> Arc<[DomHandle]> {
child_list_roots
.filter_map(|(candidate, shared)| (candidate == roots).then_some(shared))
.next()
.unwrap_or_else(|| Arc::from(roots))
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) enum StyleAttributeImpact {
None,
LayoutMetric,
ComputedStyle,
DescendantComputedStyle,
StylesheetLinkage,
LayoutMetricAndStylesheetLinkage,
}
impl StyleAttributeImpact {
pub(crate) fn for_attribute_name(name: &str) -> Self {
let name = name.to_ascii_lowercase();
match name.as_str() {
"style" | "class" | "id" | "hidden" => Self::ComputedStyle,
"width" | "height" | "cols" | "rows" | "size" | "value" | "border" | "slot"
| "align" => Self::LayoutMetric,
"cellpadding" => Self::DescendantComputedStyle,
"href" | "rel" | "media" | "blocking" | "disabled" => Self::StylesheetLinkage,
"type" => Self::LayoutMetricAndStylesheetLinkage,
_ if moli_selector::is_svg_presentation_attribute_name(&name) => Self::LayoutMetric,
_ => Self::None,
}
}
pub(crate) fn affects_layout_metric(self) -> bool {
matches!(
self,
Self::LayoutMetric
| Self::ComputedStyle
| Self::DescendantComputedStyle
| Self::LayoutMetricAndStylesheetLinkage
)
}
#[cfg(test)]
pub(crate) fn changes_computed_style(self) -> bool {
matches!(self, Self::ComputedStyle | Self::DescendantComputedStyle)
}
#[cfg(test)]
pub(crate) fn changes_stylesheet_linkage(self) -> bool {
matches!(
self,
Self::StylesheetLinkage | Self::LayoutMetricAndStylesheetLinkage
)
}
}
pub(crate) fn normalized_style_attribute_name(
host: &DomHost,
handle: DomHandle,
name: &str,
) -> String {
host.node(handle)
.and_then(Node::as_element)
.map(|element| element.normalized_attribute_name(name))
.unwrap_or_else(|| name.to_owned())
}
/// Keep only live structural history for an emptied ordinary fragment. Removed
/// roots must already have been invalidated from the original effects, and the
/// caller must retain the original source scope. A fragment with children, an
/// element parent, and a ShadowRoot can still have selector-dependent styles.
/// Their histories must pass the ordinary retained-topology checks unchanged.
pub(super) fn normalized_deferred_structural_mutation_effects<'a>(
host: &DomHost,
effects: &'a [StyleMutationEffect],
) -> Cow<'a, [StyleMutationEffect]> {
if !effects
.iter()
.any(|effect| is_empty_ordinary_fragment_child_list(host, effect))
{
return Cow::Borrowed(effects);
}
let mut normalized = Vec::with_capacity(effects.len());
let mut connected_roots = IndexSet::new();
let mut disconnected_roots = IndexSet::new();
let mut connected_slot = None;
let mut disconnected_slot = None;
for effect in effects {
if is_empty_ordinary_fragment_child_list(host, effect) {
continue;
}
match effect {
StyleMutationEffect::ConnectedSubtrees { roots } => {
if connected_slot.is_none() {
connected_slot = Some(normalized.len());
normalized.push(effect.clone());
}
connected_roots.extend(roots.iter().copied());
}
StyleMutationEffect::DisconnectedSubtrees { roots } => {
if disconnected_slot.is_none() {
disconnected_slot = Some(normalized.len());
normalized.push(effect.clone());
}
disconnected_roots.extend(roots.iter().copied());
}
// Connection facts are sets, but child-list and slot histories are
// ordered inputs. Do not deduplicate or collapse their splices.
_ => normalized.push(effect.clone()),
}
}
if let Some(slot) = connected_slot {
normalized[slot] = StyleMutationEffect::ConnectedSubtrees {
roots: connected_roots.into_iter().collect::<Vec<_>>().into(),
};
}
if let Some(slot) = disconnected_slot {
normalized[slot] = StyleMutationEffect::DisconnectedSubtrees {
roots: disconnected_roots.into_iter().collect::<Vec<_>>().into(),
};
}
Cow::Owned(normalized)
}
fn is_empty_ordinary_fragment_child_list(host: &DomHost, effect: &StyleMutationEffect) -> bool {
let StyleMutationEffect::ChildList { parent, .. } = effect else {
return false;
};
host.node(*parent)
.is_some_and(|node| node.is_document_fragment() && node.first_child().is_none())
&& !host.is_shadow_root(*parent)
}
pub(super) fn detached_style_subtree_roots_for_mutations(
effects: &[StyleMutationEffect],
) -> IndexSet<DomHandle> {
let mut roots = IndexSet::new();
for effect in effects {
match effect {
StyleMutationEffect::DisconnectedSubtrees {
roots: disconnected_roots,
} => {
roots.extend(disconnected_roots.iter().copied());
}
StyleMutationEffect::ChildList { removed_nodes, .. } => {
roots.extend(removed_nodes.iter().copied());
}
StyleMutationEffect::Attribute { .. }
| StyleMutationEffect::ConnectedSubtrees { .. }
| StyleMutationEffect::SlotAssignment { .. }
| StyleMutationEffect::CharacterData { .. } => {}
}
}
roots
}
fn removed_element_dependency_snapshots_for_mutation(
host: &DomHost,
removed_nodes: &[DomHandle],
) -> Vec<StyleElementDependencySnapshot> {
if removed_nodes
.iter()
.map(|&root| style_subtree_element_count(host, root))
.sum::<usize>()
> REMOVED_SUBTREE_SNAPSHOT_NODE_LIMIT
{
return Vec::new();
}
removed_element_dependency_snapshots(host, removed_nodes)
}
fn style_subtree_element_count(host: &DomHost, root: DomHandle) -> usize {
let mut count = 0usize;
let mut stack = vec![root];
while let Some(handle) = stack.pop() {
let Some(node) = host.node(handle) else {
continue;
};
if node.as_element().is_some() {
count += 1;
}
let mut child = node.first_child();
while let Some(current) = child {
stack.push(current);
child = host.next_sibling(current);
}
}
count
}
pub(super) fn style_mutation_effects_are_all_attributes(effects: &[StyleMutationEffect]) -> bool {
!effects.is_empty()
&& effects
.iter()
.all(|effect| matches!(effect, StyleMutationEffect::Attribute { .. }))
}
pub(super) fn style_mutation_effects_are_child_list_structural(
effects: &[StyleMutationEffect],
) -> bool {
!effects.is_empty()
&& effects.iter().all(|effect| {
matches!(
effect,
StyleMutationEffect::ChildList { .. }
| StyleMutationEffect::ConnectedSubtrees { .. }
| StyleMutationEffect::DisconnectedSubtrees { .. }
| StyleMutationEffect::SlotAssignment { .. }
)
})
&& effects
.iter()
.any(|effect| matches!(effect, StyleMutationEffect::ChildList { .. }))
}
pub(super) fn style_mutation_effects_are_all_character_data(
effects: &[StyleMutationEffect],
) -> bool {
!effects.is_empty()
&& effects
.iter()
.all(|effect| matches!(effect, StyleMutationEffect::CharacterData { .. }))
}
pub(super) fn style_mutation_effects_are_all_slot_assignments(
effects: &[StyleMutationEffect],
) -> bool {
!effects.is_empty()
&& effects
.iter()
.all(|effect| matches!(effect, StyleMutationEffect::SlotAssignment { .. }))
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub(super) struct StyleAttributeDependencyChange<'a> {
pub(super) attribute_name: &'a str,
pub(super) removed_class_tokens: Vec<String>,
pub(super) added_class_tokens: Vec<String>,
pub(super) removed_id: Option<String>,
pub(super) added_id: Option<String>,
}
impl<'a> StyleAttributeDependencyChange<'a> {
fn new(attribute_name: &'a str, old_value: Option<&str>, new_value: Option<&str>) -> Self {
let (removed_class_tokens, added_class_tokens) = if attribute_name == "class" {
changed_ascii_whitespace_tokens(old_value, new_value)
} else {
(Vec::new(), Vec::new())
};
let (removed_id, added_id) = if attribute_name == "id" {
changed_identifier(old_value, new_value)
} else {
(None, None)
};
Self {
attribute_name,
removed_class_tokens,
added_class_tokens,
removed_id,
added_id,
}
}
}
fn changed_ascii_whitespace_tokens(
old_value: Option<&str>,
new_value: Option<&str>,
) -> (Vec<String>, Vec<String>) {
let old_tokens = ascii_whitespace_token_set(old_value.unwrap_or_default());
let new_tokens = ascii_whitespace_token_set(new_value.unwrap_or_default());
let removed = old_tokens
.iter()
.filter(|token| !new_tokens.contains(*token))
.cloned()
.collect();
let added = new_tokens
.iter()
.filter(|token| !old_tokens.contains(*token))
.cloned()
.collect();
(removed, added)
}
fn ascii_whitespace_token_set(value: &str) -> IndexSet<String> {
value
.split_ascii_whitespace()
.filter(|token| !token.is_empty())
.map(str::to_owned)
.collect()
}
fn changed_identifier(
old_value: Option<&str>,
new_value: Option<&str>,
) -> (Option<String>, Option<String>) {
if old_value == new_value {
return (None, None);
}
(
old_value
.filter(|value| !value.is_empty())
.map(str::to_owned),
new_value
.filter(|value| !value.is_empty())
.map(str::to_owned),
)
}
#[cfg(test)]
mod tests {
use super::*;
use crate::dom::native::NativeDom;
fn test_host() -> DomHost {
DomHost::from_dom(NativeDom::new_html(
url::Url::parse("https://example.test/").expect("valid test url"),
))
}
#[test]
fn fragment_connection_roots_share_one_batched_child_list_payload() {
let mut host = test_host();
let document = host.document_handle();
let parent = host.create_element("main");
let fragment = host.create_document_fragment();
let first = host.create_element("div");
let second = host.create_element("span");
assert!(host.append_child(document, parent));
assert!(host.append_child(fragment, first));
assert!(host.append_child(fragment, second));
let effects = host.append_child_effects(parent, fragment);
let child_list = effects
.style()
.child_list_mutations()
.iter()
.find(|mutation| mutation.target() == parent)
.expect("fragment insertion should record one child-list mutation");
let shared_added_nodes = child_list.shared_added_nodes();
let style_effects = StyleMutationEffect::from_dom_mutation_effects(&host, &effects);
let connected_batches = style_effects
.iter()
.filter_map(|effect| match effect {
StyleMutationEffect::ConnectedSubtrees { roots } => Some(roots),
_ => None,
})
.collect::<Vec<_>>();
assert_eq!(connected_batches.len(), 1);
assert_eq!(connected_batches[0].as_ref(), [first, second]);
assert!(Arc::ptr_eq(connected_batches[0], &shared_added_nodes));
}
fn collect_native_effects(
output: &mut Vec<StyleMutationEffect>,
host: &DomHost,
effects: &DomMutationEffects,
) {
assert!(effects.did_change());
output.extend(StyleMutationEffect::from_dom_mutation_effects(
host, effects,
));
}
#[test]
fn consumed_fragment_normalization_preserves_real_splices_and_the_effect_limit() {
use crate::style_engine::{
eligibility::child_list_effects_have_current_topology,
scope::style_source_scope_for_mutation_effects,
};
let mut host = test_host();
let parent = host.create_element("div");
assert!(host.append_child(host.document_handle(), parent));
let mut effects = Vec::new();
let mut inserted = Vec::new();
let mut fragments = Vec::new();
// Match textContent + ParentNode.append's native commits, including
// the staging insertion and fragment consumption as separate facts.
for _ in 0..64 {
let child = host.create_element("div");
let text = host.set_text_content_effects(child, "ABCD");
collect_native_effects(&mut effects, &host, &text);
let fragment = host.create_document_fragment();
let staged = host.append_child_effects(fragment, child);
collect_native_effects(&mut effects, &host, &staged);
let consumed = host.append_child_effects(parent, fragment);
collect_native_effects(&mut effects, &host, &consumed);
inserted.push(child);
fragments.push(fragment);
}
assert!(effects.len() > 256);
assert!(!child_list_effects_have_current_topology(&host, &effects));
assert_eq!(
detached_style_subtree_roots_for_mutations(&effects)
.into_iter()
.collect::<Vec<_>>(),
inserted,
"cleanup must see the original removed roots before normalization"
);
let normalized = normalized_deferred_structural_mutation_effects(&host, &effects);
assert!(matches!(&normalized, Cow::Owned(_)));
assert!(normalized.len() <= 256);
assert!(child_list_effects_have_current_topology(&host, &normalized));
assert_eq!(
style_source_scope_for_mutation_effects(&host, &effects),
style_source_scope_for_mutation_effects(&host, &normalized)
);
let real_splices = effects
.iter()
.filter(|effect| match effect {
StyleMutationEffect::ChildList { parent, .. } => !fragments.contains(parent),
_ => false,
})
.cloned()
.collect::<Vec<_>>();
let kept_splices = normalized
.iter()
.filter(|effect| matches!(effect, StyleMutationEffect::ChildList { .. }))
.cloned()
.collect::<Vec<_>>();
assert_eq!(real_splices.len(), 128);
assert_eq!(kept_splices, real_splices);
drop(normalized);
// Normalization must not turn an actually large structural history
// into a small batch. These are 300 distinct, selector-visible splices.
for _ in 0..300 {
let child = host.create_element("span");
let added = host.append_child_effects(parent, child);
collect_native_effects(&mut effects, &host, &added);
}
let normalized = normalized_deferred_structural_mutation_effects(&host, &effects);
assert_eq!(
normalized
.iter()
.filter(|effect| matches!(effect, StyleMutationEffect::ChildList { .. }))
.count(),
428
);
assert!(normalized.len() > 256);
}
#[test]
fn ordinary_element_shadow_and_nonempty_fragment_histories_stay_borrowed() {
use crate::style_engine::eligibility::child_list_effects_have_current_topology;
for parent_kind in ["detached-element", "shadow-root", "nonempty-fragment"] {
let mut host = test_host();
let document = host.document_handle();
let destination = host.create_element("main");
assert!(host.append_child(document, destination));
let old_parent = match parent_kind {
"detached-element" => host.create_element("section"),
"shadow-root" => {
let shadow_host = host.create_element("div");
assert!(host.append_child(document, shadow_host));
host.attach_shadow_root(shadow_host, "open").unwrap()
}
"nonempty-fragment" => {
let fragment = host.create_document_fragment();
let remaining = host.create_element("span");
assert!(host.append_child(fragment, remaining));
fragment
}
_ => unreachable!(),
};
let moved = host.create_element("span");
let mut effects = Vec::new();
let staged = host.append_child_effects(old_parent, moved);
collect_native_effects(&mut effects, &host, &staged);
let relocated = host.append_child_effects(destination, moved);
collect_native_effects(&mut effects, &host, &relocated);
assert!(effects.iter().any(|effect| matches!(
effect,
StyleMutationEffect::ChildList { parent, removed_nodes, .. }
if *parent == old_parent && removed_nodes == &[moved]
)));
let normalized = normalized_deferred_structural_mutation_effects(&host, &effects);
assert!(matches!(&normalized, Cow::Borrowed(_)), "{parent_kind}");
assert_eq!(normalized.as_ref(), effects.as_slice(), "{parent_kind}");
assert!(
!child_list_effects_have_current_topology(&host, &normalized),
"real reparenting must retain the conservative fallback: {parent_kind}"
);
}
}
#[test]
fn consumed_fragment_does_not_erase_an_existing_elements_removal() {
use crate::style_engine::eligibility::child_list_effects_have_current_topology;
let mut host = test_host();
let document = host.document_handle();
let old_parent = host.create_element("section");
let destination = host.create_element("main");
let moved = host.create_element("span");
assert!(host.append_child(document, old_parent));
assert!(host.append_child(document, destination));
assert!(host.append_child(old_parent, moved));
let fragment = host.create_document_fragment();
let mut effects = Vec::new();
let staged = host.append_child_effects(fragment, moved);
collect_native_effects(&mut effects, &host, &staged);
let consumed = host.append_child_effects(destination, fragment);
collect_native_effects(&mut effects, &host, &consumed);
let normalized = normalized_deferred_structural_mutation_effects(&host, &effects);
assert!(matches!(&normalized, Cow::Owned(_)));
assert!(normalized.iter().any(|effect| matches!(
effect,
StyleMutationEffect::ChildList { parent, removed_nodes, .. }
if *parent == old_parent && removed_nodes == &[moved]
)));
assert!(normalized.iter().any(|effect| matches!(
effect,
StyleMutationEffect::ConnectedSubtrees { roots } if roots.contains(&moved)
)));
assert!(normalized.iter().any(|effect| matches!(
effect,
StyleMutationEffect::DisconnectedSubtrees { roots } if roots.contains(&moved)
)));
assert!(
!child_list_effects_have_current_topology(&host, &normalized),
"connected and disconnected facts must not cancel a real element-parent removal"
);
}
}