vorma 0.86.0-pre.5

//! Document contributions: what view loaders and task middleware contribute to
//! the head and to the `html`, `head`, and `body` attributes, through the
//! document methods of [`crate::Render`] and [`crate::Continue`].
//!
//! Ordinary strings are data. Vorma escapes them for their output context:
//! text for element content and attribute escaping for attribute values.
//! Source and markup pass through only in an explicit `Dangerous*` form, and
//! each form is valid only in its own context, so a bare string never becomes
//! JavaScript, CSS, or markup, and an escape hatch never disables an
//! unrelated protection. [`HeadChild::Json`] supplies the whole content of a
//! script data block. Every attribute value, including a raw one, still
//! receives quotation and attribute escaping, so its contents cannot add
//! attributes.
//!
//! Preparation turns contributed content into lowercase names, attribute
//! values as text, and serialized inner HTML. Head deduplication, the initial
//! document, and the navigation payload all read prepared content, so the two
//! renderings agree.

use std::collections::HashMap;
use std::fmt;

use primitives_rs::html::{
	escape_attr_value, escape_json_text_for_html_script, escape_text_content, is_valid_html_name,
};

/// An attribute value.
///
/// Text is literal and receives attribute escaping. Integers convert to their
/// text. Booleans do not convert, because a boolean HTML attribute is on
/// whenever it is present: a boolean attribute such as `defer` takes `""` to be
/// present or [`AttrValue::Unset`] to be removed, and an enumerated attribute
/// such as `aria-hidden` takes the text `"true"` or `"false"`. Event handler
/// attributes take
/// [`AttrValue::DangerousRawJs`], `style` takes [`AttrValue::DangerousRawCss`],
/// `srcdoc` takes [`AttrValue::DangerousRawHtml`], and a URL attribute takes
/// [`AttrValue::DangerousRawUrl`] to supply a `javascript:` URL.
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum AttrValue {
	/// Literal text.
	Text(String),
	/// Removes the attribute, including a value that an earlier contribution
	/// set, such as an ancestor loader's `class` on `body`.
	Unset,
	/// A URL that bypasses the `javascript:` URL check.
	DangerousRawUrl(String),
	/// Authored JavaScript for an event handler attribute.
	DangerousRawJs(String),
	/// Authored CSS for a `style` attribute.
	DangerousRawCss(String),
	/// Authored HTML for a `srcdoc` attribute.
	DangerousRawHtml(String),
}

impl From<String> for AttrValue {
	fn from(value: String) -> Self {
		Self::Text(value)
	}
}

impl From<&str> for AttrValue {
	fn from(value: &str) -> Self {
		Self::Text(value.to_owned())
	}
}

macro_rules! integer_attr_value {
	($($integer:ty),* $(,)?) => {
		$(
			impl From<$integer> for AttrValue {
				fn from(value: $integer) -> Self {
					Self::Text(value.to_string())
				}
			}
		)*
	};
}

integer_attr_value!(i8, i16, i32, i64, isize, u8, u16, u32, u64, usize);

/// A head element, with the same shape at every depth.
#[derive(Clone, Debug, PartialEq)]
#[must_use]
pub struct HeadEl {
	pub(crate) tag: String,
	pub(crate) attrs: Vec<(String, AttrValue)>,
	pub(crate) children: Vec<HeadChild>,
}

impl HeadEl {
	/// Creates an element without attributes or children.
	pub fn new(tag: impl Into<String>) -> Self {
		Self {
			tag: tag.into(),
			attrs: Vec::new(),
			children: Vec::new(),
		}
	}

	/// Sets an attribute, which replaces an earlier value of that attribute.
	pub fn set_attr(mut self, name: impl Into<String>, value: impl Into<AttrValue>) -> Self {
		self.attrs.push((name.into(), value.into()));
		self
	}

	/// Adds a child after the existing ones.
	pub fn add_child(mut self, child: impl Into<HeadChild>) -> Self {
		self.children.push(child.into());
		self
	}
}

/// A child of a head element: text, an element, the JSON content of a script
/// data block, complete script or style source, or markup that passes
/// through unchanged.
#[derive(Clone, Debug, PartialEq)]
pub enum HeadChild {
	/// Text, which receives text escaping.
	Text(String),
	/// A nested element.
	El(HeadEl),
	/// The whole content of a `<script>` data block. The script's `type`
	/// remains an ordinary attribute.
	Json(serde_json::Value),
	/// Complete script source, valid only inside `<script>`.
	DangerousRawJs(String),
	/// Complete stylesheet source, valid only inside `<style>`.
	DangerousRawCss(String),
	/// Markup inserted unchanged.
	DangerousRawHtml(String),
}

impl From<&str> for HeadChild {
	fn from(value: &str) -> Self {
		Self::Text(value.to_owned())
	}
}

impl From<String> for HeadChild {
	fn from(value: String) -> Self {
		Self::Text(value)
	}
}

impl From<HeadEl> for HeadChild {
	fn from(value: HeadEl) -> Self {
		Self::El(value)
	}
}

/// One contribution to the head, as a result's `head_items` method returns
/// it: what one call of `add_head_el`, `remove_head_el`, or
/// `add_head_dangerous_raw_html` contributed.
#[derive(Clone, Debug, PartialEq)]
pub enum HeadItem {
	/// An element that `add_head_el` added.
	El(HeadEl),
	/// An identity that `remove_head_el` removes from the elements that were
	/// placed before it.
	Remove(HeadEl),
	/// Markup that `add_head_dangerous_raw_html` added, which passes through
	/// without escaping or deduplication.
	DangerousRawHtml(String),
}

/// One handler's document contribution. Nested loaders' attributes merge one
/// attribute at a time, from parent to child; head items are appended in order
/// and then deduplicated.
#[derive(Clone, Debug, Default, PartialEq)]
pub(crate) struct DocumentParts {
	pub(crate) html_attrs: Vec<(String, AttrValue)>,
	pub(crate) head_attrs: Vec<(String, AttrValue)>,
	pub(crate) head_items: Vec<HeadItem>,
	pub(crate) body_attrs: Vec<(String, AttrValue)>,
}

/// How a head deduplication rule matches one attribute.
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum AttrMatch {
	/// The attribute has exactly this value.
	Exact(String),
	/// The attribute is present with any value.
	Wildcard,
}

impl From<&str> for AttrMatch {
	fn from(value: &str) -> Self {
		Self::Exact(value.to_owned())
	}
}

impl From<String> for AttrMatch {
	fn from(value: String) -> Self {
		Self::Exact(value)
	}
}

/// What a later element with a head identity replaces.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum HeadReplacement {
	/// A later element with the identity replaces the earlier one.
	LatestEl,
	/// The elements with the identity from the latest handler that contributes
	/// any replace all earlier ones, and all of that handler's own elements
	/// stay. The replacing set takes the place of the first element with the
	/// identity.
	LatestContribution,
}

/// One head identity in addition to the built-in identities. Structured
/// elements with this tag and matching attributes occupy one position, and
/// the rule's [`HeadReplacement`] says what a later element replaces there.
///
/// A handler removes an identity's elements with `remove_head_el`, which
/// accepts only an element that matches a built-in identity or one of these
/// rules.
#[derive(Clone, Debug, PartialEq, Eq)]
#[must_use]
pub struct HeadDedupeRule {
	pub(crate) tag: String,
	pub(crate) replacement: HeadReplacement,
	pub(crate) attrs: Vec<(String, AttrMatch)>,
}

impl HeadDedupeRule {
	/// Creates a rule that matches every element with this tag.
	pub fn new(tag: impl Into<String>, replacement: HeadReplacement) -> Self {
		Self {
			tag: tag.into(),
			replacement,
			attrs: Vec::new(),
		}
	}

	/// Sets the requirement for one attribute. A string requires exactly that
	/// value, and [`AttrMatch::Wildcard`] requires the attribute with any
	/// value.
	pub fn set_attr(mut self, name: impl Into<String>, matcher: impl Into<AttrMatch>) -> Self {
		self.attrs.push((name.into(), matcher.into()));
		self
	}
}

/// Contributed document content that is invalid for its output context.
#[derive(Clone, Debug, PartialEq, Eq)]
pub(crate) struct DocumentError {
	/// Where the content was contributed, such as `head_children[2].children[0]`.
	pub(crate) path: String,
	pub(crate) message: String,
}

impl fmt::Display for DocumentError {
	fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
		write!(formatter, "{}: {}", self.path, self.message)
	}
}

impl std::error::Error for DocumentError {}

/// A structured head element after preparation.
#[derive(Clone, Debug, PartialEq, Eq)]
pub(crate) struct PreparedEl {
	pub(crate) tag: String,
	/// Attribute values as text, in authored order.
	pub(crate) attrs: Vec<(String, String)>,
	pub(crate) inner_html: String,
}

impl PreparedEl {
	/// Returns the element with this inner HTML.
	pub(crate) fn with_inner_html(mut self, inner_html: &str) -> Self {
		self.inner_html = inner_html.to_owned();
		self
	}
}

/// A prepared head item. Raw HTML passes through without deduplication.
#[derive(Clone, Debug, PartialEq, Eq)]
pub(crate) enum PreparedHeadItem {
	El(PreparedEl),
	RawHtml(String),
}

/// A change to the head: placing an item, or removing an identity that
/// earlier contributions placed.
#[derive(Clone, Debug, PartialEq, Eq)]
pub(crate) enum HeadChange {
	Place(PreparedHeadItem),
	/// The element carries an identity's tag and attributes.
	Remove(PreparedEl),
}

/// A head change with the position of the contribution that made it, in
/// plan order.
#[derive(Clone, Debug, PartialEq, Eq)]
pub(crate) struct ContributedHeadChange {
	contribution: usize,
	change: HeadChange,
}

/// Attribute settings in first-set order. `None` records `Unset`, so that a
/// later merge can remove an earlier value, and a later setting replaces an
/// earlier one in place.
#[derive(Clone, Debug, Default, PartialEq, Eq)]
pub(crate) struct AttrSettings(Vec<(String, Option<String>)>);

impl AttrSettings {
	fn set(&mut self, name: String, value: Option<String>) {
		match self.0.iter_mut().find(|(existing, _)| *existing == name) {
			Some(entry) => entry.1 = value,
			None => self.0.push((name, value)),
		}
	}

	fn merge(&mut self, later: Self) {
		for (name, value) in later.0 {
			self.set(name, value);
		}
	}

	/// The resolved attributes, without removed ones.
	pub(crate) fn resolve(&self) -> impl Iterator<Item = (&str, &str)> {
		self.0
			.iter()
			.filter_map(|(name, value)| value.as_deref().map(|value| (name.as_str(), value)))
	}
}

/// Prepared document contributions, merged in plan order.
#[derive(Clone, Debug, Default, PartialEq, Eq)]
pub(crate) struct PreparedDocument {
	pub(crate) html_attrs: AttrSettings,
	pub(crate) head_attrs: AttrSettings,
	pub(crate) body_attrs: AttrSettings,
	head_changes: Vec<ContributedHeadChange>,
	/// How many handlers' contributions the document merges.
	contribution_count: usize,
}

impl PreparedDocument {
	/// Merges a later contribution: attributes one at a time, head changes
	/// appended with the later contributions numbered after the earlier ones.
	pub(crate) fn merge(&mut self, later: Self) {
		self.html_attrs.merge(later.html_attrs);
		self.head_attrs.merge(later.head_attrs);
		self.body_attrs.merge(later.body_attrs);
		let offset = self.contribution_count;
		self.head_changes
			.extend(
				later
					.head_changes
					.into_iter()
					.map(|change| ContributedHeadChange {
						contribution: change.contribution + offset,
						change: change.change,
					}),
			);
		self.contribution_count += later.contribution_count;
	}

	pub(crate) fn head_changes(&self) -> &[ContributedHeadChange] {
		&self.head_changes
	}
}

impl DocumentParts {
	/// Checks every value against its output context and serializes the
	/// content that does not depend on other contributions. A removal must
	/// name one of `head_rules`' identities.
	pub(crate) fn prepare(self, head_rules: &HeadRules) -> Result<PreparedDocument, DocumentError> {
		let mut head_changes = Vec::with_capacity(self.head_items.len());
		for (index, item) in self.head_items.into_iter().enumerate() {
			let path = format!("head[{index}]");
			let change = match item {
				HeadItem::DangerousRawHtml(html) => {
					HeadChange::Place(PreparedHeadItem::RawHtml(html))
				}
				HeadItem::El(el) => HeadChange::Place(PreparedHeadItem::El(prepare_el(el, &path)?)),
				HeadItem::Remove(el) => HeadChange::Remove(prepare_removal(el, head_rules, &path)?),
			};
			head_changes.push(ContributedHeadChange {
				contribution: 0,
				change,
			});
		}
		Ok(PreparedDocument {
			html_attrs: prepare_document_attrs("html", self.html_attrs)?,
			head_attrs: prepare_document_attrs("head", self.head_attrs)?,
			body_attrs: prepare_document_attrs("body", self.body_attrs)?,
			head_changes,
			contribution_count: 1,
		})
	}
}

fn document_error(path: String, message: impl Into<String>) -> DocumentError {
	DocumentError {
		path,
		message: message.into(),
	}
}

const VOID_ELS: &[&str] = &[
	"area", "base", "br", "col", "embed", "hr", "img", "input", "link", "meta", "source", "track",
	"wbr",
];

/// Attributes with a value that is one URL. Composite grammars, such as `srcset`
/// and `ping`, are not URLs.
const URL_ATTRS: &[&str] = &[
	"action",
	"background",
	"cite",
	"codebase",
	"data",
	"formaction",
	"href",
	"longdesc",
	"manifest",
	"poster",
	"profile",
	"src",
	"xlink:href",
];

/// Where an element is: its tag and the path that messages name.
#[derive(Clone, Copy)]
struct ElSite<'a> {
	tag: &'a str,
	path: &'a str,
}

fn is_void_el(tag: &str) -> bool {
	VOID_ELS.contains(&tag)
}

#[derive(Clone, Copy, PartialEq, Eq)]
enum AttrCtx {
	Url,
	Js,
	Css,
	Html,
	Text,
}

impl AttrCtx {
	fn of(name: &str) -> Self {
		if URL_ATTRS.contains(&name) {
			Self::Url
		} else if name.starts_with("on") {
			Self::Js
		} else if name == "style" {
			Self::Css
		} else if name == "srcdoc" {
			Self::Html
		} else {
			Self::Text
		}
	}

	fn raw_form(self) -> &'static str {
		match self {
			Self::Url => "DangerousRawUrl",
			Self::Js => "DangerousRawJs",
			Self::Css => "DangerousRawCss",
			Self::Html | Self::Text => "DangerousRawHtml",
		}
	}
}

/// Recognizes a `javascript:` URL as browsers parse one: leading C0 controls
/// and spaces are ignored, ASCII tabs and newlines inside the scheme are
/// removed, and the scheme is case-insensitive. This is React's recognizer.
fn is_javascript_url(value: &str) -> bool {
	let mut characters = value
		.trim_start_matches(|character: char| character <= '\u{1F}' || character == ' ')
		.chars()
		.filter(|character| !matches!(character, '\r' | '\n' | '\t'));
	"javascript:".chars().all(|expected| {
		characters
			.next()
			.is_some_and(|actual| actual.eq_ignore_ascii_case(&expected))
	})
}

/// One attribute value as text, or `None` for `Unset`. A raw form must match
/// the attribute's context, a source context requires its raw form, and a
/// URL attribute refuses a `javascript:` URL unless it is `DangerousRawUrl`.
fn prepare_attr_value(
	site: ElSite<'_>,
	name: &str,
	value: AttrValue,
) -> Result<Option<String>, DocumentError> {
	let ElSite { tag: el, path } = site;
	let location = format!("{path}.{name}");
	if !is_valid_html_name(name) {
		return Err(document_error(
			location,
			format!("{name:?} is not an attribute name"),
		));
	}
	let ctx = AttrCtx::of(name);
	let (form_ctx, text) = match value {
		AttrValue::Unset => return Ok(None),
		AttrValue::Text(text) => (None, text),
		AttrValue::DangerousRawUrl(text) => (Some(AttrCtx::Url), text),
		AttrValue::DangerousRawJs(text) => (Some(AttrCtx::Js), text),
		AttrValue::DangerousRawCss(text) => (Some(AttrCtx::Css), text),
		AttrValue::DangerousRawHtml(text) => (Some(AttrCtx::Html), text),
	};
	match form_ctx {
		Some(form_ctx) if form_ctx == ctx => Ok(Some(text)),
		Some(form_ctx) => Err(document_error(
			location,
			format!(
				"{} is not valid for the {name} attribute of <{el}>",
				form_ctx.raw_form()
			),
		)),
		None if matches!(ctx, AttrCtx::Js | AttrCtx::Css | AttrCtx::Html) => Err(document_error(
			location,
			format!(
				"the {name} attribute of <{el}> takes {}, not text",
				ctx.raw_form()
			),
		)),
		None if ctx == AttrCtx::Url && is_javascript_url(&text) => Err(document_error(
			location,
			format!(
				"the {name} attribute of <{el}> cannot be a javascript: URL; use DangerousRawUrl to supply one intentionally"
			),
		)),
		None => Ok(Some(text)),
	}
}

fn prepare_document_attrs(
	el: &str,
	attrs: Vec<(String, AttrValue)>,
) -> Result<AttrSettings, DocumentError> {
	let path = format!("{el}_attrs");
	let mut settings = AttrSettings::default();
	for (authored_name, value) in attrs {
		let name = authored_name.to_ascii_lowercase();
		let prepared = prepare_attr_value(
			ElSite {
				tag: el,
				path: &path,
			},
			&name,
			value,
		)?;
		settings.set(name, prepared);
	}
	Ok(settings)
}

/// An element's attributes as text, in authored order, without `Unset` ones.
fn prepare_el_attrs(
	site: ElSite<'_>,
	attrs: Vec<(String, AttrValue)>,
) -> Result<Vec<(String, String)>, DocumentError> {
	let mut settings = AttrSettings::default();
	for (authored_name, value) in attrs {
		let name = authored_name.to_ascii_lowercase();
		let prepared = prepare_attr_value(site, &name, value)?;
		settings.set(name, prepared);
	}
	Ok(settings
		.0
		.into_iter()
		.filter_map(|(name, value)| value.map(|value| (name, value)))
		.collect())
}

#[derive(Clone, Copy, PartialEq, Eq)]
enum ContentCtx {
	Script,
	Style,
	EscapableText,
	Markup,
}

impl ContentCtx {
	fn of(tag: &str) -> Self {
		match tag {
			"script" => Self::Script,
			"style" => Self::Style,
			"title" | "textarea" => Self::EscapableText,
			_ => Self::Markup,
		}
	}
}

fn prepare_el(el: HeadEl, path: &str) -> Result<PreparedEl, DocumentError> {
	let tag = el.tag.to_ascii_lowercase();
	if !is_valid_html_name(&tag) {
		return Err(document_error(
			path.to_owned(),
			format!("{:?} is not an element name", el.tag),
		));
	}
	let attrs = prepare_el_attrs(
		ElSite {
			tag: &tag,
			path: &format!("{path}.attrs"),
		},
		el.attrs,
	)?;
	let inner_html = render_children(ElSite { tag: &tag, path }, el.children)?;
	Ok(PreparedEl {
		tag,
		attrs,
		inner_html,
	})
}

/// A removal's element: only the tag and the attributes that the matched
/// identity names, without children.
fn prepare_removal(
	el: HeadEl,
	head_rules: &HeadRules,
	path: &str,
) -> Result<PreparedEl, DocumentError> {
	if !el.children.is_empty() {
		return Err(document_error(
			format!("{path}.children"),
			"an element to remove carries no children",
		));
	}
	let prepared = prepare_el(el, path)?;
	let Some(rule) = head_rules.find_rule(&prepared) else {
		return Err(document_error(
			path.to_owned(),
			format!(
				"<{}> with these attributes matches no head identity; declare a HeadDedupeRule to make it removable",
				prepared.tag
			),
		));
	};
	if let Some((name, _)) = prepared.attrs.iter().find(|(name, _)| {
		!rule
			.attrs
			.iter()
			.any(|(identity_name, _)| identity_name == name)
	}) {
		return Err(document_error(
			format!("{path}.attrs.{name}"),
			format!(
				"the {name} attribute is not part of the head identity of <{}>",
				prepared.tag
			),
		));
	}
	Ok(prepared)
}

/// The serialized children of one element, checked against the element's
/// content context.
fn render_children(site: ElSite<'_>, children: Vec<HeadChild>) -> Result<String, DocumentError> {
	let ElSite { tag, path } = site;
	if !children.is_empty() && is_void_el(tag) {
		return Err(document_error(
			format!("{path}.children"),
			format!("<{tag}> cannot have children"),
		));
	}
	let ctx = ContentCtx::of(tag);
	let count = children.len();
	let mut rendered = String::new();
	for (index, child) in children.into_iter().enumerate() {
		let location = format!("{path}.children[{index}]");
		match child {
			HeadChild::Json(value) => {
				if ctx != ContentCtx::Script {
					return Err(document_error(
						location,
						format!("a Json child is valid only in <script>, not <{tag}>"),
					));
				}
				if count != 1 {
					return Err(document_error(
						location,
						"a Json child must be the only child of its <script>",
					));
				}
				rendered.push_str(&escape_json_text_for_html_script(&value.to_string()));
			}
			HeadChild::DangerousRawJs(source) => {
				if ctx != ContentCtx::Script {
					return Err(document_error(
						location,
						format!("DangerousRawJs is valid only in <script>, not <{tag}>"),
					));
				}
				rendered.push_str(&source);
			}
			HeadChild::DangerousRawCss(source) => {
				if ctx != ContentCtx::Style {
					return Err(document_error(
						location,
						format!("DangerousRawCss is valid only in <style>, not <{tag}>"),
					));
				}
				rendered.push_str(&source);
			}
			HeadChild::DangerousRawHtml(markup) => {
				if ctx != ContentCtx::Markup {
					return Err(document_error(
						location,
						format!("DangerousRawHtml is not valid in <{tag}>"),
					));
				}
				rendered.push_str(&markup);
			}
			HeadChild::Text(text) => match ctx {
				ContentCtx::Script => {
					return Err(document_error(
						location,
						"<script> content takes DangerousRawJs or Json, not text",
					));
				}
				ContentCtx::Style => {
					return Err(document_error(
						location,
						"<style> content takes DangerousRawCss, not text",
					));
				}
				ContentCtx::EscapableText | ContentCtx::Markup => {
					rendered.push_str(&escape_text_content(&text));
				}
			},
			HeadChild::El(el) => {
				if ctx != ContentCtx::Markup {
					return Err(document_error(
						location,
						format!("<{tag}> cannot contain elements"),
					));
				}
				rendered.push_str(&render_el(&prepare_el(el, &location)?));
			}
		}
	}
	Ok(rendered)
}

/// Serializes a prepared element; its attribute values are escaped once, here.
pub(crate) fn render_el(el: &PreparedEl) -> String {
	let mut html = format!("<{}", el.tag);
	write_attrs(
		&mut html,
		el.attrs
			.iter()
			.map(|(name, value)| (name.as_str(), value.as_str())),
	);
	html.push('>');
	if !is_void_el(&el.tag) {
		html.push_str(&el.inner_html);
		html.push_str("</");
		html.push_str(&el.tag);
		html.push('>');
	}
	html
}

/// Writes ` name="value"` for each attribute, escaping each value once.
pub(crate) fn write_attrs<'a>(html: &mut String, attrs: impl Iterator<Item = (&'a str, &'a str)>) {
	for (name, value) in attrs {
		html.push(' ');
		html.push_str(name);
		html.push_str("=\"");
		html.push_str(&escape_attr_value(value));
		html.push('"');
	}
}

pub(crate) fn render_head_item(item: &PreparedHeadItem) -> String {
	match item {
		PreparedHeadItem::El(el) => render_el(el),
		PreparedHeadItem::RawHtml(html) => html.clone(),
	}
}

/// The deduplicated head: the title, the meta elements, and every other item
/// in order.
#[derive(Clone, Debug, Default, PartialEq, Eq)]
pub(crate) struct PreparedHead {
	pub(crate) title: Option<PreparedEl>,
	pub(crate) meta: Vec<PreparedEl>,
	pub(crate) rest: Vec<PreparedHeadItem>,
}

struct CompiledHeadRule {
	priority: usize,
	replacement: HeadReplacement,
	attrs: Vec<(String, AttrMatch)>,
}

/// The built-in head identities followed by the application's rules, by tag.
pub(crate) struct HeadRules(HashMap<String, Vec<CompiledHeadRule>>);

fn built_in_head_rules() -> Vec<HeadDedupeRule> {
	use HeadReplacement::{LatestContribution, LatestEl};
	let mut rules = vec![HeadDedupeRule::new("title", LatestEl)];
	for name in ["description", "viewport", "robots"] {
		rules.push(
			HeadDedupeRule::new("meta", LatestEl)
				.set_attr("name", AttrMatch::Exact(name.to_owned())),
		);
	}
	rules.push(HeadDedupeRule::new("meta", LatestEl).set_attr("charset", AttrMatch::Wildcard));
	rules.push(
		HeadDedupeRule::new("link", LatestContribution)
			.set_attr("rel", AttrMatch::Exact("icon".to_owned())),
	);
	rules.push(
		HeadDedupeRule::new("link", LatestEl)
			.set_attr("rel", AttrMatch::Exact("canonical".to_owned())),
	);
	for property in [
		"og:title",
		"og:description",
		"og:url",
		"og:type",
		"og:locale",
		"og:site_name",
		"og:determiner",
	] {
		rules.push(
			HeadDedupeRule::new("meta", LatestEl)
				.set_attr("property", AttrMatch::Exact(property.to_owned())),
		);
	}
	rules
}

/// What identifies a structured head element: the rule that matches it, or
/// its whole shape when no rule matches.
#[derive(Clone, Debug, PartialEq, Eq, Hash)]
enum HeadIdentity {
	Rule(usize),
	Shape(ElShape),
}

/// The elements that one identity holds, in a position of the head. `els` is
/// empty after a removal, and the position stays for a later element.
struct IdentitySlot {
	contribution: usize,
	els: Vec<PreparedEl>,
}

enum HeadSlot {
	Raw(String),
	Identity(IdentitySlot),
}

impl HeadRules {
	/// Compiles the built-in rules and then the application's, preserving
	/// priority within each tag.
	pub(crate) fn new(application_rules: &[HeadDedupeRule]) -> Self {
		let mut by_tag: HashMap<String, Vec<CompiledHeadRule>> = HashMap::new();
		let rules = built_in_head_rules()
			.into_iter()
			.chain(application_rules.iter().cloned());
		for (priority, rule) in rules.enumerate() {
			by_tag
				.entry(rule.tag.to_ascii_lowercase())
				.or_default()
				.push(CompiledHeadRule {
					priority,
					replacement: rule.replacement,
					attrs: rule
						.attrs
						.into_iter()
						.map(|(name, value)| (name.to_ascii_lowercase(), value))
						.collect(),
				});
		}
		Self(by_tag)
	}

	fn find_rule(&self, el: &PreparedEl) -> Option<&CompiledHeadRule> {
		self.0.get(&el.tag)?.iter().find(|rule| {
			rule.attrs.iter().all(|(name, expected)| {
				el.attrs
					.iter()
					.find(|(actual_name, _)| actual_name == name)
					.is_some_and(|(_, actual)| match expected {
						AttrMatch::Exact(expected) => actual == expected,
						AttrMatch::Wildcard => true,
					})
			})
		})
	}

	/// Applies the head changes in order, then classifies the result.
	///
	/// A structured element takes the position of its identity. A
	/// `LatestEl` identity holds one element, which a later element
	/// replaces. A `LatestContribution` identity holds the elements of one
	/// contribution, which a later contribution's element replaces; the later
	/// contribution's other elements with the identity join it. A removal
	/// empties the identity and keeps its
	/// position. An element that no rule matches is identified by its whole
	/// shape. Raw HTML passes through in order.
	pub(crate) fn deduplicate(&self, changes: &[ContributedHeadChange]) -> PreparedHead {
		let mut slots: Vec<HeadSlot> = Vec::with_capacity(changes.len());
		let mut slot_by_identity: HashMap<HeadIdentity, usize> = HashMap::new();
		for ContributedHeadChange {
			contribution,
			change,
		} in changes
		{
			match change {
				HeadChange::Place(PreparedHeadItem::RawHtml(html)) => {
					slots.push(HeadSlot::Raw(html.clone()));
				}
				HeadChange::Place(PreparedHeadItem::El(el)) => {
					let (identity, replacement) = match self.find_rule(el) {
						Some(rule) => (HeadIdentity::Rule(rule.priority), rule.replacement),
						None => (
							HeadIdentity::Shape(ElShape::of(el)),
							HeadReplacement::LatestEl,
						),
					};
					match slot_by_identity.get(&identity) {
						None => {
							slot_by_identity.insert(identity, slots.len());
							slots.push(HeadSlot::Identity(IdentitySlot {
								contribution: *contribution,
								els: vec![el.clone()],
							}));
						}
						Some(&index) => {
							let HeadSlot::Identity(slot) = &mut slots[index] else {
								unreachable!("an identity maps to an identity slot");
							};
							let joins = replacement == HeadReplacement::LatestContribution
								&& !slot.els.is_empty() && slot.contribution
								== *contribution;
							if joins {
								slot.els.push(el.clone());
							} else {
								slot.contribution = *contribution;
								slot.els = vec![el.clone()];
							}
						}
					}
				}
				HeadChange::Remove(el) => {
					let Some(rule) = self.find_rule(el) else {
						continue;
					};
					if let Some(&index) = slot_by_identity.get(&HeadIdentity::Rule(rule.priority)) {
						let HeadSlot::Identity(slot) = &mut slots[index] else {
							unreachable!("an identity maps to an identity slot");
						};
						slot.els.clear();
					}
				}
			}
		}
		let mut head = PreparedHead::default();
		let items = slots.into_iter().flat_map(|slot| match slot {
			HeadSlot::Raw(html) => vec![PreparedHeadItem::RawHtml(html)],
			HeadSlot::Identity(slot) => slot.els.into_iter().map(PreparedHeadItem::El).collect(),
		});
		for item in items {
			match item {
				PreparedHeadItem::El(el) if el.tag == "title" => head.title = Some(el),
				PreparedHeadItem::El(el) if el.tag == "meta" => head.meta.push(el),
				item => head.rest.push(item),
			}
		}
		head
	}
}

/// A structural identity for an element, independent of attribute order.
#[derive(Clone, Debug, PartialEq, Eq, Hash)]
struct ElShape {
	tag: String,
	attrs: Vec<(String, String)>,
	inner_html: String,
}

impl ElShape {
	fn of(el: &PreparedEl) -> Self {
		let mut attrs = el.attrs.clone();
		attrs.sort_by(|left, right| left.0.cmp(&right.0));
		Self {
			tag: el.tag.clone(),
			attrs,
			inner_html: el.inner_html.clone(),
		}
	}
}