foch 0.0.2

// SPDX-License-Identifier: GPL-3.0-only
//
// Parser-independent adaptation of Mergiraf 0.18.0's matching and GumTree
// implementation (`src/matching.rs`, `src/tree_matcher.rs`, and
// `src/tree_matcher/priority_list.rs`) at upstream revision
// e8e13887b85b8cb56b1dc1624c5f94e3d39182b6.

use std::collections::{BTreeMap, BTreeSet, HashSet};

use serde::{Deserialize, Serialize};

use crate::merge::kernel::{
	ChildCardinality, NodeId, NormalizedNode, NormalizedTree, SemanticKey, SemanticKeyLineage,
	SemanticKeyMatchMode, SemanticKeyScope, SubtreeHash,
};

const ORDERED_POSITIONAL_SCORE: u32 = 575_000;

#[derive(Clone, Copy, Debug, Eq, Ord, PartialEq, PartialOrd, Serialize, Deserialize)]
#[serde(rename_all = "snake_case")]
pub enum MatchKind {
	Exact,
	SemanticAnchor,
	SoftSignature,
	RequiredSlot,
	DescendantSimilarity,
	Recovery,
}

#[derive(Clone, Copy, Debug, Eq, PartialEq, Serialize, Deserialize)]
pub struct MatchRecord {
	pub left: NodeId,
	pub right: NodeId,
	pub kind: MatchKind,
	/// Fixed-point score in millionths. Exact and anchor matches use 1_000_000.
	pub score: u32,
}

#[derive(Clone, Debug, Eq, Hash, PartialEq, Serialize, Deserialize)]
pub struct AmbiguousMatch {
	pub left: NodeId,
	pub candidates: Vec<NodeId>,
	pub score: u32,
}

#[derive(Clone, Debug, Default, Eq, PartialEq, Serialize)]
#[serde(transparent)]
struct Ambiguities {
	entries: Vec<AmbiguousMatch>,
	#[serde(skip)]
	left: BTreeSet<NodeId>,
	#[serde(skip)]
	right: BTreeSet<NodeId>,
	/// `entries` as a set, so recording a known ambiguity again is not a scan.
	#[serde(skip)]
	recorded: HashSet<AmbiguousMatch>,
}

impl Ambiguities {
	fn rebuild_indexes(&mut self) {
		self.left = self.entries.iter().map(|entry| entry.left).collect();
		self.right = self
			.entries
			.iter()
			.flat_map(|entry| entry.candidates.iter().copied())
			.collect();
		self.recorded = self.entries.iter().cloned().collect();
	}

	fn insert(&mut self, ambiguity: AmbiguousMatch) -> bool {
		if !self.recorded.insert(ambiguity.clone()) {
			return false;
		}
		self.left.insert(ambiguity.left);
		self.right.extend(ambiguity.candidates.iter().copied());
		self.entries.push(ambiguity);
		true
	}
}

impl<'de> Deserialize<'de> for Ambiguities {
	fn deserialize<D: serde::Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
		let mut ambiguities = Self {
			entries: Vec::<AmbiguousMatch>::deserialize(deserializer)?,
			..Self::default()
		};
		ambiguities.rebuild_indexes();
		Ok(ambiguities)
	}
}

/// A node whose availability changed: it was matched or marked ambiguous.
#[derive(Clone, Copy, Debug)]
enum Change {
	Left(NodeId),
	Right(NodeId),
}

/// The order in which nodes stopped being available, which lets a pass
/// revisit only the parents a change affects. It is bookkeeping, not part of
/// the matching's value: equality and serialization ignore it.
#[derive(Clone, Debug, Default)]
struct ChangeLog(Vec<Change>);

impl PartialEq for ChangeLog {
	fn eq(&self, _: &Self) -> bool {
		true
	}
}

impl Eq for ChangeLog {}

#[derive(Clone, Debug, Default, Eq, PartialEq, Serialize, Deserialize)]
pub struct Matching {
	by_left: BTreeMap<NodeId, MatchRecord>,
	by_right: BTreeMap<NodeId, NodeId>,
	ambiguous: Ambiguities,
	#[serde(skip)]
	changes: ChangeLog,
}

impl Matching {
	pub fn compose_through_base(base_left: &Self, base_right: &Self) -> Self {
		let mut composed = Self::default();
		for left_record in base_left.records() {
			let Some(right_record) = base_right.record(left_record.left) else {
				continue;
			};
			composed.insert(MatchRecord {
				left: left_record.right,
				right: right_record.right,
				kind: if left_record.kind == MatchKind::Exact
					&& right_record.kind == MatchKind::Exact
				{
					MatchKind::Exact
				} else {
					MatchKind::Recovery
				},
				score: left_record.score.min(right_record.score),
			});
		}
		composed
	}

	pub fn get_from_left(&self, left: NodeId) -> Option<NodeId> {
		self.by_left.get(&left).map(|record| record.right)
	}

	pub fn get_from_right(&self, right: NodeId) -> Option<NodeId> {
		self.by_right.get(&right).copied()
	}

	pub fn record(&self, left: NodeId) -> Option<&MatchRecord> {
		self.by_left.get(&left)
	}

	pub fn records(&self) -> impl ExactSizeIterator<Item = &MatchRecord> {
		self.by_left.values()
	}

	pub fn ambiguities(&self) -> &[AmbiguousMatch] {
		&self.ambiguous.entries
	}

	#[cfg(test)]
	pub fn len(&self) -> usize {
		self.by_left.len()
	}

	fn is_left_matched(&self, left: NodeId) -> bool {
		self.by_left.contains_key(&left)
	}

	fn is_right_matched(&self, right: NodeId) -> bool {
		self.by_right.contains_key(&right)
	}

	fn is_left_ambiguous(&self, left: NodeId) -> bool {
		self.ambiguous.left.contains(&left)
	}

	fn is_right_ambiguous(&self, right: NodeId) -> bool {
		self.ambiguous.right.contains(&right)
	}

	fn insert(&mut self, record: MatchRecord) -> bool {
		if self.is_left_matched(record.left) || self.is_right_matched(record.right) {
			return false;
		}
		self.by_right.insert(record.right, record.left);
		self.by_left.insert(record.left, record);
		self.changes.0.push(Change::Left(record.left));
		self.changes.0.push(Change::Right(record.right));
		true
	}

	fn record_ambiguity(&mut self, ambiguity: AmbiguousMatch) {
		let left = ambiguity.left;
		let candidates = ambiguity.candidates.clone();
		if self.ambiguous.insert(ambiguity) {
			self.changes.0.push(Change::Left(left));
			self.changes
				.0
				.extend(candidates.into_iter().map(Change::Right));
		}
	}
}

#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub struct MatcherConfig {
	pub min_height: u32,
	/// Fixed-point Dice threshold in millionths.
	pub similarity_threshold: u32,
	pub max_recovery_size: usize,
}

impl Default for MatcherConfig {
	fn default() -> Self {
		Self {
			min_height: 1,
			similarity_threshold: 500_000,
			max_recovery_size: 100,
		}
	}
}

#[derive(Clone, Copy, Debug, Default)]
pub struct TreeMatcher {
	config: MatcherConfig,
}

impl TreeMatcher {
	pub fn match_trees(&self, left: &NormalizedTree, right: &NormalizedTree) -> Matching {
		self.match_trees_with_seed(left, right, None)
	}

	pub fn match_trees_with_seed(
		&self,
		left: &NormalizedTree,
		right: &NormalizedTree,
		seed: Option<&Matching>,
	) -> Matching {
		let mut matching = Matching::default();
		let mut work = MatchWork::default();
		let left_root = left.root();
		let right_root = right.root();
		let left_root_node = left.node(left_root).unwrap();
		let right_root_node = right.node(right_root).unwrap();
		if compatible(left_root_node, right_root_node) {
			if isomorphic_subtree(left, right, left_root, right_root) {
				match_isomorphic_subtree(left, right, &mut matching, left_root, right_root);
			} else {
				matching.insert(MatchRecord {
					left: left_root,
					right: right_root,
					kind: MatchKind::Recovery,
					score: 500_000,
				});
			}
		}

		if let Some(seed) = seed {
			for record in seed.records() {
				if left.node(record.left).is_err() || right.node(record.right).is_err() {
					continue;
				}
				if !compatible_at_including_ordered(
					left,
					right,
					&matching,
					record.left,
					record.right,
				) {
					continue;
				}
				let exact = isomorphic_subtree(left, right, record.left, record.right);
				matching.insert(MatchRecord {
					left: record.left,
					right: record.right,
					kind: if exact {
						MatchKind::Exact
					} else {
						MatchKind::Recovery
					},
					score: if exact { 1_000_000 } else { record.score },
				});
			}
		}

		match_unique_anchors(left, right, &mut matching);
		match_required_slots(left, right, &mut matching, &mut work);
		match_parent_scoped_anchors(left, right, &mut matching, &mut work);
		match_ordered_similarity_siblings(
			left,
			right,
			&mut matching,
			self.config.similarity_threshold,
			&mut work,
		);
		match_soft_signatures(left, right, &mut matching, &mut work);
		match_exact_subtrees(left, right, &mut matching, self.config.min_height);
		match_repeated_parent_scoped_siblings(
			left,
			right,
			&mut matching,
			self.config.similarity_threshold,
			&mut work,
		);
		match_parent_scoped_anchors(left, right, &mut matching, &mut work);
		match_ordered_similarity_siblings(
			left,
			right,
			&mut matching,
			self.config.similarity_threshold,
			&mut work,
		);
		match_by_descendants(left, right, &mut matching, self.config.similarity_threshold);
		match_required_slots(left, right, &mut matching, &mut work);
		match_parent_scoped_anchors(left, right, &mut matching, &mut work);
		recover_children(
			left,
			right,
			&mut matching,
			self.config.max_recovery_size,
			&mut work,
		);
		match_parent_scoped_anchors(left, right, &mut matching, &mut work);
		match_repeated_parent_scoped_siblings(
			left,
			right,
			&mut matching,
			self.config.similarity_threshold,
			&mut work,
		);
		match_parent_scoped_anchors(left, right, &mut matching, &mut work);
		match_soft_signatures(left, right, &mut matching, &mut work);
		recover_children(
			left,
			right,
			&mut matching,
			self.config.max_recovery_size,
			&mut work,
		);
		record_unresolved_soft_signature_ambiguities(left, right, &mut matching);

		if let Some(seed) = seed {
			retain_seeded_lineage_matches(left, right, seed, &mut matching);
		}
		matching
	}
}

fn retain_seeded_lineage_matches(
	left: &NormalizedTree,
	right: &NormalizedTree,
	seed: &Matching,
	matching: &mut Matching,
) {
	matching.by_left.retain(|left_id, record| {
		seeded_lineage_pair_is_allowed(left, right, seed, *left_id, record.right)
	});
	matching.by_right = matching
		.by_left
		.values()
		.map(|record| (record.right, record.left))
		.collect();
	for ambiguity in &mut matching.ambiguous.entries {
		let left_id = ambiguity.left;
		ambiguity.candidates.retain(|right_id| {
			seeded_lineage_pair_is_allowed(left, right, seed, left_id, *right_id)
		});
	}
	matching
		.ambiguous
		.entries
		.retain(|ambiguity| !ambiguity.candidates.is_empty());
	matching.ambiguous.rebuild_indexes();
}

fn seeded_lineage_pair_is_allowed(
	left: &NormalizedTree,
	right: &NormalizedTree,
	seed: &Matching,
	left_id: NodeId,
	right_id: NodeId,
) -> bool {
	match (
		nearest_seeded_lineage_root(left, left_id),
		nearest_seeded_lineage_root(right, right_id),
	) {
		(None, None) => true,
		(Some(left_root), Some(right_root)) => seed.get_from_left(left_root) == Some(right_root),
		(Some(_), None) | (None, Some(_)) => false,
	}
}

fn nearest_seeded_lineage_root(tree: &NormalizedTree, mut node: NodeId) -> Option<NodeId> {
	loop {
		let current = tree.node(node).unwrap();
		if current
			.anchor
			.as_ref()
			.is_some_and(|anchor| anchor.lineage == SemanticKeyLineage::Seeded)
		{
			return Some(node);
		}
		node = current.parent?;
	}
}

fn compatible(left: &NormalizedNode, right: &NormalizedNode) -> bool {
	left.kind == right.kind
		&& left.child_cardinality == right.child_cardinality
		&& !anchors_forbid(left.anchor.as_ref(), right.anchor.as_ref())
}

fn compatible_at(
	left: &NormalizedTree,
	right: &NormalizedTree,
	matching: &Matching,
	left_id: NodeId,
	right_id: NodeId,
) -> bool {
	let left_node = left.node(left_id).unwrap();
	let right_node = right.node(right_id).unwrap();
	if ordered_similarity_anchor(left_node).is_some()
		|| ordered_similarity_anchor(right_node).is_some()
	{
		return false;
	}
	compatible_at_including_ordered(left, right, matching, left_id, right_id)
}

fn compatible_at_including_ordered(
	left: &NormalizedTree,
	right: &NormalizedTree,
	matching: &Matching,
	left_id: NodeId,
	right_id: NodeId,
) -> bool {
	let left_node = left.node(left_id).unwrap();
	let right_node = right.node(right_id).unwrap();
	if !compatible(left_node, right_node) {
		return false;
	}
	let parent_scoped = [left_node.anchor.as_ref(), right_node.anchor.as_ref()]
		.into_iter()
		.flatten()
		.any(|anchor| anchor.scope == SemanticKeyScope::Parent);
	if !parent_scoped {
		return true;
	}
	let (Some(left_parent), Some(right_parent)) = (left_node.parent, right_node.parent) else {
		return false;
	};
	matching.get_from_left(left_parent) == Some(right_parent)
}

fn ordered_similarity_anchor(node: &NormalizedNode) -> Option<&SemanticKey> {
	node.anchor.as_ref().filter(|anchor| {
		matches!(
			anchor.match_mode,
			SemanticKeyMatchMode::OrderedSimilarity
				| SemanticKeyMatchMode::OrderedSimilarityWithPosition
		)
	})
}

fn match_soft_signatures(
	left: &NormalizedTree,
	right: &NormalizedTree,
	matching: &mut Matching,
	work: &mut MatchWork,
) {
	loop {
		match_required_slots(left, right, matching, work);
		let parents = matching.records().copied().collect::<Vec<_>>();
		let mut changed = false;
		for parent in parents {
			let left_parent = left.node(parent.left).unwrap();
			let right_parent = right.node(parent.right).unwrap();
			if left_parent.child_cardinality == ChildCardinality::ExactlyOne
				|| right_parent.child_cardinality == ChildCardinality::ExactlyOne
			{
				continue;
			}
			let left_groups =
				unmatched_signature_groups(left, &left_parent.children, matching, true);
			let right_groups =
				unmatched_signature_groups(right, &right_parent.children, matching, false);
			for (key, left_nodes) in left_groups {
				let Some(right_nodes) = right_groups.get(&key) else {
					continue;
				};
				if let ([left_node], [right_node]) = (left_nodes.as_slice(), right_nodes.as_slice())
					&& compatible_at(left, right, matching, *left_node, *right_node)
				{
					changed |= matching.insert(MatchRecord {
						left: *left_node,
						right: *right_node,
						kind: MatchKind::SoftSignature,
						score: 900_000,
					});
				}
			}
		}
		if !changed {
			break;
		}
	}
}

fn record_unresolved_soft_signature_ambiguities(
	left: &NormalizedTree,
	right: &NormalizedTree,
	matching: &mut Matching,
) {
	let parents = matching.records().copied().collect::<Vec<_>>();
	for parent in parents {
		let left_groups = unmatched_signature_groups(
			left,
			&left.node(parent.left).unwrap().children,
			matching,
			true,
		);
		let right_groups = unmatched_signature_groups(
			right,
			&right.node(parent.right).unwrap().children,
			matching,
			false,
		);
		for (key, left_nodes) in left_groups {
			let Some(right_nodes) = right_groups.get(&key) else {
				continue;
			};
			for left_node in left_nodes {
				matching.record_ambiguity(AmbiguousMatch {
					left: left_node,
					candidates: right_nodes.clone(),
					score: 900_000,
				});
			}
		}
	}
}

fn unmatched_signature_groups(
	tree: &NormalizedTree,
	children: &[NodeId],
	matching: &Matching,
	left_side: bool,
) -> BTreeMap<(String, String), Vec<NodeId>> {
	let mut groups = BTreeMap::new();
	for child in children {
		let unavailable = if left_side {
			matching.is_left_matched(*child) || matching.is_left_ambiguous(*child)
		} else {
			matching.is_right_matched(*child) || matching.is_right_ambiguous(*child)
		};
		if unavailable {
			continue;
		}
		let node = tree.node(*child).unwrap();
		let Some(signature) = &node.signature else {
			continue;
		};
		groups
			.entry((node.kind.clone(), signature.clone()))
			.or_insert_with(Vec::new)
			.push(*child);
	}
	groups
}

fn anchors_forbid(left: Option<&SemanticKey>, right: Option<&SemanticKey>) -> bool {
	matches!(
		(left, right),
		(Some(left), Some(right))
			if left.scope == right.scope
				&& left.namespace == right.namespace
				&& (left.match_mode != right.match_mode
					|| left.lineage != right.lineage
					|| (left.match_mode == SemanticKeyMatchMode::Identity
						&& left.value != right.value))
	)
}

fn match_ordered_similarity_siblings(
	left: &NormalizedTree,
	right: &NormalizedTree,
	matching: &mut Matching,
	threshold: u32,
	work: &mut MatchWork,
) {
	loop {
		match_required_slots(left, right, matching, work);
		match_parent_scoped_anchors(left, right, matching, work);
		if match_unique_ordered_signatures(left, right, matching) {
			continue;
		}
		let parents = matching.records().copied().collect::<Vec<_>>();
		let mut proposals = Vec::new();
		for parent in parents {
			let left_children = &left.node(parent.left).unwrap().children;
			let right_children = &right.node(parent.right).unwrap().children;
			let left_groups = ordered_similarity_groups(left, left_children);
			let right_groups = ordered_similarity_groups(right, right_children);
			for (key, left_nodes) in left_groups {
				let Some(right_nodes) = right_groups.get(&key) else {
					continue;
				};
				align_ordered_similarity_group(
					left,
					right,
					matching,
					left_children,
					right_children,
					&left_nodes,
					right_nodes,
					threshold,
					&mut proposals,
				);
			}
		}

		proposals.sort_by(|left_candidate, right_candidate| {
			left_candidate
				.left
				.cmp(&right_candidate.left)
				.then_with(|| left_candidate.right.cmp(&right_candidate.right))
		});
		proposals.dedup();
		let mut changed = false;
		for proposal in proposals {
			changed |= matching.insert(MatchRecord {
				left: proposal.left,
				right: proposal.right,
				kind: MatchKind::DescendantSimilarity,
				score: proposal.score,
			});
		}
		if !changed {
			break;
		}
	}
}

fn match_unique_ordered_signatures(
	left: &NormalizedTree,
	right: &NormalizedTree,
	matching: &mut Matching,
) -> bool {
	let parents = matching.records().copied().collect::<Vec<_>>();
	let mut proposals = Vec::new();
	for parent in parents {
		let left_groups =
			ordered_similarity_groups(left, &left.node(parent.left).unwrap().children);
		let right_groups =
			ordered_similarity_groups(right, &right.node(parent.right).unwrap().children);
		for (anchor, left_nodes) in left_groups {
			// Position-aware signatures are lineage evidence inside the ordered-gap
			// alignment, where cardinality and similarity can still reject them.
			if anchor.2 == SemanticKeyMatchMode::OrderedSimilarityWithPosition {
				continue;
			}
			let Some(right_nodes) = right_groups.get(&anchor) else {
				continue;
			};
			let mut left_signatures: BTreeMap<String, Vec<NodeId>> = BTreeMap::new();
			for node in left_nodes {
				if matching.is_left_matched(node) || matching.is_left_ambiguous(node) {
					continue;
				}
				if let Some(signature) = &left.node(node).unwrap().signature {
					left_signatures
						.entry(signature.clone())
						.or_default()
						.push(node);
				}
			}
			let mut right_signatures: BTreeMap<String, Vec<NodeId>> = BTreeMap::new();
			for node in right_nodes {
				if matching.is_right_matched(*node) || matching.is_right_ambiguous(*node) {
					continue;
				}
				if let Some(signature) = &right.node(*node).unwrap().signature {
					right_signatures
						.entry(signature.clone())
						.or_default()
						.push(*node);
				}
			}
			for (signature, left_nodes) in left_signatures {
				let Some(right_nodes) = right_signatures.get(&signature) else {
					continue;
				};
				if let ([left_id], [right_id]) = (left_nodes.as_slice(), right_nodes.as_slice())
					&& compatible_at_including_ordered(left, right, matching, *left_id, *right_id)
				{
					proposals.push((*left_id, *right_id));
				}
			}
		}
	}
	proposals.sort_unstable();
	proposals.dedup();
	let mut changed = false;
	for (left, right) in proposals {
		changed |= matching.insert(MatchRecord {
			left,
			right,
			kind: MatchKind::SoftSignature,
			score: 900_000,
		});
	}
	changed
}

fn ordered_similarity_groups(
	tree: &NormalizedTree,
	children: &[NodeId],
) -> BTreeMap<(SemanticKeyScope, String, SemanticKeyMatchMode), Vec<NodeId>> {
	let mut groups = BTreeMap::new();
	for child in children {
		let node = tree.node(*child).unwrap();
		let Some(anchor) = ordered_similarity_anchor(node) else {
			continue;
		};
		groups
			.entry((
				anchor.scope.clone(),
				anchor.namespace.clone(),
				anchor.match_mode,
			))
			.or_insert_with(Vec::new)
			.push(*child);
	}
	groups
}

#[allow(clippy::too_many_arguments)]
fn align_ordered_similarity_group(
	left: &NormalizedTree,
	right: &NormalizedTree,
	matching: &mut Matching,
	left_siblings: &[NodeId],
	right_siblings: &[NodeId],
	left_nodes: &[NodeId],
	right_nodes: &[NodeId],
	threshold: u32,
	proposals: &mut Vec<RecoveryCandidate>,
) {
	let left_positions = left_siblings
		.iter()
		.enumerate()
		.map(|(index, id)| (*id, index))
		.collect::<BTreeMap<_, _>>();
	let right_positions = right_siblings
		.iter()
		.enumerate()
		.map(|(index, id)| (*id, index))
		.collect::<BTreeMap<_, _>>();
	let mut fixed = left_siblings
		.iter()
		.enumerate()
		.filter_map(|(left_index, left_id)| {
			let right_id = matching.get_from_left(*left_id)?;
			Some((left_index, *right_positions.get(&right_id)?))
		})
		.collect::<Vec<_>>();
	fixed.sort_unstable();
	let fixed = order_preserving_frame(left, left_siblings, &fixed);

	let left_unmatched = left_nodes
		.iter()
		.copied()
		.filter(|id| !matching.is_left_matched(*id) && !matching.is_left_ambiguous(*id))
		.map(|id| (left_positions[&id], id))
		.collect::<Vec<_>>();
	let right_unmatched = right_nodes
		.iter()
		.copied()
		.filter(|id| !matching.is_right_matched(*id) && !matching.is_right_ambiguous(*id))
		.map(|id| (right_positions[&id], id))
		.collect::<Vec<_>>();
	// Identity does not depend on order: a sibling whose whole subtree occurs
	// exactly once on each side is the same sibling wherever it now stands.
	let (left_unmatched, right_unmatched) = match_unique_identical_siblings(
		left,
		right,
		matching,
		left_unmatched,
		right_unmatched,
		proposals,
	);
	if left_unmatched.is_empty() || right_unmatched.is_empty() {
		return;
	}
	let gap_index = |position: usize, left_side: bool| {
		fixed.partition_point(|(left_position, right_position)| {
			if left_side {
				*left_position < position
			} else {
				*right_position < position
			}
		})
	};
	let mut left_gap_counts = vec![0usize; fixed.len() + 1];
	for (position, _) in &left_unmatched {
		left_gap_counts[gap_index(*position, true)] += 1;
	}
	let mut right_gap_counts = vec![0usize; fixed.len() + 1];
	for (position, _) in &right_unmatched {
		right_gap_counts[gap_index(*position, false)] += 1;
	}

	let left_features = left_unmatched
		.iter()
		.map(|(_, id)| subtree_features(left, *id))
		.collect::<Vec<_>>();
	let right_features = right_unmatched
		.iter()
		.map(|(_, id)| subtree_features(right, *id))
		.collect::<Vec<_>>();
	let left_lineage_hashes = left_unmatched
		.iter()
		.map(|(_, id)| subtree_lineage_hashes(left, *id))
		.collect::<Vec<_>>();
	let right_lineage_hashes = right_unmatched
		.iter()
		.map(|(_, id)| subtree_lineage_hashes(right, *id))
		.collect::<Vec<_>>();
	let mut left_hash_owners = BTreeMap::<(usize, SubtreeHash), Option<usize>>::new();
	for (index, ((position, _), hashes)) in
		left_unmatched.iter().zip(&left_lineage_hashes).enumerate()
	{
		let gap = gap_index(*position, true);
		for hash in hashes {
			left_hash_owners
				.entry((gap, *hash))
				.and_modify(|owner| *owner = None)
				.or_insert(Some(index));
		}
	}
	let mut right_hash_owners = BTreeMap::<(usize, SubtreeHash), Option<usize>>::new();
	for (index, ((position, _), hashes)) in right_unmatched
		.iter()
		.zip(&right_lineage_hashes)
		.enumerate()
	{
		let gap = gap_index(*position, false);
		for hash in hashes {
			right_hash_owners
				.entry((gap, *hash))
				.and_modify(|owner| *owner = None)
				.or_insert(Some(index));
		}
	}
	let mut left_signature_owners = BTreeMap::<(usize, String), Option<usize>>::new();
	for (index, (position, id)) in left_unmatched.iter().enumerate() {
		let Some(signature) = &left.node(*id).unwrap().signature else {
			continue;
		};
		left_signature_owners
			.entry((gap_index(*position, true), signature.clone()))
			.and_modify(|owner| *owner = None)
			.or_insert(Some(index));
	}
	let mut right_signature_owners = BTreeMap::<(usize, String), Option<usize>>::new();
	for (index, (position, id)) in right_unmatched.iter().enumerate() {
		let Some(signature) = &right.node(*id).unwrap().signature else {
			continue;
		};
		right_signature_owners
			.entry((gap_index(*position, false), signature.clone()))
			.and_modify(|owner| *owner = None)
			.or_insert(Some(index));
	}
	let mut discriminative_pairs = vec![vec![false; right_unmatched.len()]; left_unmatched.len()];
	for (key, left_owner) in &left_hash_owners {
		let Some(left_index) = left_owner else {
			continue;
		};
		if let Some(Some(right_index)) = right_hash_owners.get(key) {
			discriminative_pairs[*left_index][*right_index] = true;
		}
	}
	for (key, left_owner) in &left_signature_owners {
		let Some(left_index) = left_owner else {
			continue;
		};
		if let Some(Some(right_index)) = right_signature_owners.get(key) {
			discriminative_pairs[*left_index][*right_index] = true;
		}
	}
	for (left_index, (_, left_id)) in left_unmatched.iter().enumerate() {
		for (right_index, (_, right_id)) in right_unmatched.iter().enumerate() {
			if discriminative_pairs[left_index][right_index]
				&& !compatible_at_including_ordered(left, right, matching, *left_id, *right_id)
			{
				discriminative_pairs[left_index][right_index] = false;
			}
		}
	}
	let left_evidence_degrees = discriminative_pairs
		.iter()
		.map(|row| row.iter().filter(|evidence| **evidence).count())
		.collect::<Vec<_>>();
	let right_evidence_degrees = (0..right_unmatched.len())
		.map(|right_index| {
			discriminative_pairs
				.iter()
				.filter(|row| row[right_index])
				.count()
		})
		.collect::<Vec<_>>();
	let scores = left_unmatched
		.iter()
		.enumerate()
		.map(|(left_index, (left_position, left_id))| {
			let left_node = left.node(*left_id).unwrap();
			let match_mode = ordered_similarity_anchor(left_node)
				.expect("ordered groups contain ordered anchors")
				.match_mode;
			right_unmatched
				.iter()
				.enumerate()
				.map(|(right_index, (right_position, right_id))| {
					let left_gap = gap_index(*left_position, true);
					let right_gap = gap_index(*right_position, false);
					if left_gap != right_gap
						|| !compatible_at_including_ordered(
							left, right, matching, *left_id, *right_id,
						) {
						return None;
					}
					// Position only identifies a sibling when insertions and removals have
					// not shifted the two sides of this fixed-anchor gap.
					let positional_fallback_is_safe =
						left_gap_counts[left_gap] == right_gap_counts[right_gap];
					let discriminative_evidence = discriminative_pairs[left_index][right_index]
						&& left_evidence_degrees[left_index] == 1
						&& right_evidence_degrees[right_index] == 1;
					let similarity = raw_subtree_similarity(
						&left_features[left_index],
						&right_features[right_index],
					);
					ordered_pair_score(
						match_mode,
						left_node,
						right.node(*right_id).unwrap(),
						similarity,
						threshold,
						positional_fallback_is_safe,
						discriminative_evidence,
					)
				})
				.collect::<Vec<_>>()
		})
		.collect::<Vec<_>>();
	let alignments = best_ordered_alignments(&scores);
	if alignments.paths.len() == 1 {
		proposals.extend(alignments.paths[0].iter().map(|(left_index, right_index)| {
			RecoveryCandidate {
				left: left_unmatched[*left_index].1,
				right: right_unmatched[*right_index].1,
				score: scores[*left_index][*right_index]
					.expect("alignment pairs have a score")
					.reported,
			}
		}));
		return;
	}

	for (left_index, (_, left_id)) in left_unmatched.iter().enumerate() {
		let placements = alignments
			.paths
			.iter()
			.map(|path| {
				path.iter().find_map(|(candidate, right_index)| {
					(*candidate == left_index).then_some(*right_index)
				})
			})
			.collect::<BTreeSet<_>>();
		if placements.len() < 2 {
			continue;
		}
		let candidates = placements
			.iter()
			.flatten()
			.map(|right_index| right_unmatched[*right_index].1)
			.collect::<Vec<_>>();
		if candidates.is_empty() {
			continue;
		}
		let score = placements
			.iter()
			.flatten()
			.filter_map(|right_index| scores[left_index][*right_index])
			.map(|score| score.reported)
			.max()
			.unwrap_or(ORDERED_POSITIONAL_SCORE);
		matching.record_ambiguity(AmbiguousMatch {
			left: *left_id,
			candidates,
			score,
		});
	}
}

type PositionedSiblings = Vec<(usize, NodeId)>;

fn match_unique_identical_siblings(
	left: &NormalizedTree,
	right: &NormalizedTree,
	matching: &Matching,
	left_unmatched: PositionedSiblings,
	right_unmatched: PositionedSiblings,
	proposals: &mut Vec<RecoveryCandidate>,
) -> (PositionedSiblings, PositionedSiblings) {
	let hash_owners = |tree: &NormalizedTree, siblings: &PositionedSiblings| {
		let mut owners = BTreeMap::<SubtreeHash, Option<NodeId>>::new();
		for (_, id) in siblings {
			owners
				.entry(tree.node(*id).unwrap().subtree_hash)
				.and_modify(|owner| *owner = None)
				.or_insert(Some(*id));
		}
		owners
	};
	let left_owners = hash_owners(left, &left_unmatched);
	let right_owners = hash_owners(right, &right_unmatched);
	let mut paired = BTreeSet::new();
	for (hash, left_owner) in &left_owners {
		if let (Some(left_id), Some(Some(right_id))) = (left_owner, right_owners.get(hash))
			&& compatible_at_including_ordered(left, right, matching, *left_id, *right_id)
		{
			proposals.push(RecoveryCandidate {
				left: *left_id,
				right: *right_id,
				score: 1_000_000,
			});
			paired.insert((*left_id, true));
			paired.insert((*right_id, false));
		}
	}
	(
		left_unmatched
			.into_iter()
			.filter(|(_, id)| !paired.contains(&(*id, true)))
			.collect(),
		right_unmatched
			.into_iter()
			.filter(|(_, id)| !paired.contains(&(*id, false)))
			.collect(),
	)
}

/// The heaviest subset of matched sibling pairs whose order agrees on both
/// sides. A sibling that moved crosses the others; it stays matched but must
/// not frame the gaps, or one moved line would separate every unchanged
/// sibling it passed from its counterpart.
fn order_preserving_frame(
	left: &NormalizedTree,
	left_siblings: &[NodeId],
	fixed: &[(usize, usize)],
) -> Vec<(usize, usize)> {
	if fixed.windows(2).all(|pair| pair[0].1 < pair[1].1) {
		return fixed.to_vec();
	}
	let weight = |left_index: usize| {
		u64::from(
			left.node(left_siblings[left_index])
				.unwrap()
				.descendant_count,
		) + 1
	};
	// best[i]: heaviest increasing chain ending at fixed[i]; ties keep the
	// earliest predecessor so the frame is deterministic.
	let mut best = Vec::<(u64, Option<usize>)>::with_capacity(fixed.len());
	for (index, (left_index, right_index)) in fixed.iter().enumerate() {
		let mut chain = (weight(*left_index), None);
		for (previous, (_, previous_right)) in fixed[..index].iter().enumerate() {
			let candidate = best[previous].0 + weight(*left_index);
			if previous_right < right_index && candidate > chain.0 {
				chain = (candidate, Some(previous));
			}
		}
		best.push(chain);
	}
	let mut end = None;
	for (index, (total, _)) in best.iter().enumerate() {
		if end.is_none_or(|end: usize| *total > best[end].0) {
			end = Some(index);
		}
	}
	let mut frame = Vec::new();
	while let Some(index) = end {
		frame.push(fixed[index]);
		end = best[index].1;
	}
	frame.reverse();
	frame
}

fn ordered_pair_score(
	match_mode: SemanticKeyMatchMode,
	left: &NormalizedNode,
	right: &NormalizedNode,
	similarity: u32,
	threshold: u32,
	positional_fallback_is_safe: bool,
	discriminative_evidence: bool,
) -> Option<OrderedScore> {
	match match_mode {
		SemanticKeyMatchMode::OrderedSimilarity => {
			let high_confidence =
				threshold.saturating_add(1_000_000u32.saturating_sub(threshold) / 2);
			let same_signature = left.signature.is_some() && left.signature == right.signature;
			if !same_signature && similarity <= high_confidence {
				return None;
			}
			let score = if same_signature {
				similarity.max(900_000)
			} else {
				similarity
			};
			Some(OrderedScore {
				weight: u64::from(score),
				reported: score,
			})
		}
		SemanticKeyMatchMode::OrderedSimilarityWithPosition => {
			if !positional_fallback_is_safe && (!discriminative_evidence || similarity <= threshold)
			{
				return None;
			}
			Some(OrderedScore {
				weight: if similarity > threshold {
					u64::from(similarity)
				} else {
					1
				},
				reported: if similarity > threshold {
					similarity
				} else {
					ORDERED_POSITIONAL_SCORE
				},
			})
		}
		SemanticKeyMatchMode::Identity => None,
	}
}

#[derive(Clone, Copy, Debug)]
struct OrderedScore {
	weight: u64,
	reported: u32,
}

#[derive(Clone)]
struct OrderedAlignments {
	weight: u64,
	paths: Vec<Vec<(usize, usize)>>,
}

fn best_ordered_alignments(scores: &[Vec<Option<OrderedScore>>]) -> OrderedAlignments {
	let left_len = scores.len();
	let right_len = scores.first().map_or(0, Vec::len);
	let empty = OrderedAlignments {
		weight: 0,
		paths: vec![Vec::new()],
	};
	let mut best = vec![vec![empty; right_len + 1]; left_len + 1];
	for left_index in (0..left_len).rev() {
		for right_index in (0..right_len).rev() {
			let mut options = vec![
				best[left_index + 1][right_index].clone(),
				best[left_index][right_index + 1].clone(),
			];
			if let Some(score) = scores[left_index][right_index] {
				let mut matched = best[left_index + 1][right_index + 1].clone();
				matched.weight = matched.weight.saturating_add(score.weight);
				for path in &mut matched.paths {
					path.insert(0, (left_index, right_index));
				}
				options.push(matched);
			}
			let weight = options
				.iter()
				.map(|option| option.weight)
				.max()
				.unwrap_or_default();
			let mut paths = options
				.into_iter()
				.filter(|option| option.weight == weight)
				.flat_map(|option| option.paths)
				.collect::<Vec<_>>();
			paths.sort();
			paths.dedup();
			paths.truncate(2);
			best[left_index][right_index] = OrderedAlignments { weight, paths };
		}
	}
	best[0][0].clone()
}
fn match_unique_anchors(left: &NormalizedTree, right: &NormalizedTree, matching: &mut Matching) {
	let left_anchors = anchors_by_key(left);
	let right_anchors = anchors_by_key(right);
	for (key, left_nodes) in left_anchors {
		let Some(right_nodes) = right_anchors.get(&key) else {
			continue;
		};
		if let ([left_id], [right_id]) = (left_nodes.as_slice(), right_nodes.as_slice())
			&& compatible(left.node(*left_id).unwrap(), right.node(*right_id).unwrap())
		{
			matching.insert(MatchRecord {
				left: *left_id,
				right: *right_id,
				kind: MatchKind::SemanticAnchor,
				score: 1_000_000,
			});
		}
	}
}

fn anchors_by_key(tree: &NormalizedTree) -> BTreeMap<SemanticKey, Vec<NodeId>> {
	let mut anchors = BTreeMap::new();
	for (id, node) in tree.nodes() {
		if let Some(anchor) = &node.anchor
			&& anchor.scope == SemanticKeyScope::Global
		{
			anchors
				.entry(anchor.clone())
				.or_insert_with(Vec::new)
				.push(id);
		}
	}
	anchors
}

/// Work state of one `match_trees` run for the passes that revisit matched
/// parents until nothing changes.
///
/// What such a pass does for one matched parent depends only on the parent's
/// match and on which of its children are still available on each side, and
/// within a run availability only shrinks: no phase unmatches a node. A pass
/// therefore revisits only the parents whose children changed since its last
/// visit; every other parent would repeat a visit that matched nothing new.
#[derive(Default)]
struct MatchWork {
	required_slots: DirtyParents,
	parent_anchors: DirtyParents,
}

#[derive(Default)]
struct DirtyParents {
	started: bool,
	cursor: usize,
	pending: BTreeSet<NodeId>,
}

impl DirtyParents {
	/// The matched parents, by left node, to visit now: every one on the
	/// first visit, then those that were matched or had a child change since.
	fn take(
		&mut self,
		left: &NormalizedTree,
		right: &NormalizedTree,
		matching: &Matching,
	) -> Vec<MatchRecord> {
		let changes = &matching.changes.0;
		if !self.started {
			self.started = true;
			self.cursor = changes.len();
			return matching.records().copied().collect();
		}
		for change in &changes[self.cursor..] {
			match *change {
				Change::Left(node) => {
					self.pending.insert(node);
					if let Some(parent) = left.node(node).unwrap().parent {
						self.pending.insert(parent);
					}
				}
				Change::Right(node) => {
					if let Some(parent) = right.node(node).unwrap().parent
						&& let Some(left_parent) = matching.get_from_right(parent)
					{
						self.pending.insert(left_parent);
					}
				}
			}
		}
		self.cursor = changes.len();
		std::mem::take(&mut self.pending)
			.into_iter()
			.filter_map(|parent| matching.record(parent).copied())
			.collect()
	}
}

fn match_parent_scoped_anchors(
	left: &NormalizedTree,
	right: &NormalizedTree,
	matching: &mut Matching,
	work: &mut MatchWork,
) {
	loop {
		match_required_slots(left, right, matching, work);
		let parents = work.parent_anchors.take(left, right, matching);
		let mut changed = false;
		for parent in parents {
			let left_groups = unmatched_parent_anchor_groups(
				left,
				&left.node(parent.left).unwrap().children,
				matching,
				true,
			);
			if left_groups.free.is_empty() {
				continue;
			}
			let right_groups = unmatched_parent_anchor_groups(
				right,
				&right.node(parent.right).unwrap().children,
				matching,
				false,
			);
			for (key, left_nodes) in &left_groups.free {
				let Some(right_nodes) = right_groups.free.get(key) else {
					continue;
				};
				if left_groups.repeats(key) || right_groups.repeats(key) {
					continue;
				}
				if let ([left_node], [right_node]) = (left_nodes.as_slice(), right_nodes.as_slice())
					&& compatible_at(left, right, matching, *left_node, *right_node)
				{
					changed |= matching.insert(MatchRecord {
						left: *left_node,
						right: *right_node,
						kind: MatchKind::SemanticAnchor,
						score: 1_000_000,
					});
				}
			}
		}
		if !changed {
			break;
		}
	}
}

/// The parent-scoped anchors among one parent's children: the free
/// children grouped by anchor, and the anchors more than one child carries,
/// matched or not.
struct ParentAnchorGroups<'tree> {
	free: BTreeMap<&'tree SemanticKey, Vec<NodeId>>,
	repeated: BTreeSet<&'tree SemanticKey>,
}

impl ParentAnchorGroups<'_> {
	fn repeats(&self, anchor: &SemanticKey) -> bool {
		self.repeated.contains(anchor)
	}
}

fn unmatched_parent_anchor_groups<'tree>(
	tree: &'tree NormalizedTree,
	children: &[NodeId],
	matching: &Matching,
	left_side: bool,
) -> ParentAnchorGroups<'tree> {
	let mut free = BTreeMap::new();
	let mut seen = BTreeSet::new();
	let mut repeated = BTreeSet::new();
	for child in children {
		let Some(anchor) = tree.node(*child).unwrap().anchor.as_ref() else {
			continue;
		};
		if anchor.scope != SemanticKeyScope::Parent {
			continue;
		}
		if !seen.insert(anchor) {
			repeated.insert(anchor);
		}
		let unavailable = if left_side {
			matching.is_left_matched(*child) || matching.is_left_ambiguous(*child)
		} else {
			matching.is_right_matched(*child) || matching.is_right_ambiguous(*child)
		};
		if !unavailable {
			free.entry(anchor).or_insert_with(Vec::new).push(*child);
		}
	}
	ParentAnchorGroups { free, repeated }
}

fn match_repeated_parent_scoped_siblings(
	left: &NormalizedTree,
	right: &NormalizedTree,
	matching: &mut Matching,
	threshold: u32,
	work: &mut MatchWork,
) {
	loop {
		let parents = matching.records().copied().collect::<Vec<_>>();
		let mut proposals = Vec::new();
		for parent in parents {
			let left_groups = unmatched_parent_anchor_groups(
				left,
				&left.node(parent.left).unwrap().children,
				matching,
				true,
			);
			let right_groups = unmatched_parent_anchor_groups(
				right,
				&right.node(parent.right).unwrap().children,
				matching,
				false,
			);
			for (key, left_nodes) in &left_groups.free {
				let Some(right_nodes) = right_groups.free.get(key) else {
					continue;
				};
				let repeated = left_groups.repeats(key) || right_groups.repeats(key);
				if !repeated {
					continue;
				}
				let candidates = repeated_sibling_candidates(
					left,
					right,
					matching,
					left_nodes,
					right_nodes,
					threshold,
				);
				proposals.extend(candidates.mutual_unique_best());
			}
		}

		proposals.sort_by(|left_candidate, right_candidate| {
			right_candidate
				.score
				.cmp(&left_candidate.score)
				.then_with(|| left_candidate.left.cmp(&right_candidate.left))
				.then_with(|| left_candidate.right.cmp(&right_candidate.right))
		});
		let mut changed = false;
		for proposal in proposals {
			changed |= matching.insert(MatchRecord {
				left: proposal.left,
				right: proposal.right,
				kind: MatchKind::DescendantSimilarity,
				score: proposal.score,
			});
		}
		if !changed {
			break;
		}
		match_required_slots(left, right, matching, work);
		match_parent_scoped_anchors(left, right, matching, work);
	}

	record_unresolved_repeated_sibling_ambiguities(left, right, matching, threshold);
}

fn repeated_sibling_candidates(
	left: &NormalizedTree,
	right: &NormalizedTree,
	matching: &Matching,
	left_nodes: &[NodeId],
	right_nodes: &[NodeId],
	threshold: u32,
) -> SiblingCandidates {
	let left_features = left_nodes
		.iter()
		.map(|id| (*id, subtree_features(left, *id)))
		.collect::<BTreeMap<_, _>>();
	let right_features = right_nodes
		.iter()
		.map(|id| (*id, subtree_features(right, *id)))
		.collect::<BTreeMap<_, _>>();
	let mut candidates = SiblingCandidates::default();
	for left_id in left_nodes {
		for right_id in right_nodes {
			if !compatible_at(left, right, matching, *left_id, *right_id) {
				continue;
			}
			let score = raw_subtree_similarity(
				left_features.get(left_id).expect("left features collected"),
				right_features
					.get(right_id)
					.expect("right features collected"),
			);
			if score > threshold {
				candidates.insert(RecoveryCandidate {
					left: *left_id,
					right: *right_id,
					score,
				});
			}
		}
	}
	candidates
}

#[derive(Default)]
struct BestCandidates {
	score: u32,
	peers: Vec<NodeId>,
}

impl BestCandidates {
	fn insert(&mut self, peer: NodeId, score: u32) {
		if score > self.score {
			self.score = score;
			self.peers.clear();
		}
		if score == self.score {
			self.peers.push(peer);
		}
	}
}

/// Accumulate best scores and ties while scoring pairs. Never rescan the full
/// candidate relation for each pair: a dense sibling group already has O(L*R)
/// pairs before selecting mutually unique maxima.
#[derive(Default)]
struct SiblingCandidates {
	left: BTreeMap<NodeId, BestCandidates>,
	right: BTreeMap<NodeId, BestCandidates>,
}

impl SiblingCandidates {
	fn insert(&mut self, candidate: RecoveryCandidate) {
		self.left
			.entry(candidate.left)
			.or_default()
			.insert(candidate.right, candidate.score);
		self.right
			.entry(candidate.right)
			.or_default()
			.insert(candidate.left, candidate.score);
	}

	fn mutual_unique_best(&self) -> impl Iterator<Item = RecoveryCandidate> + '_ {
		self.left.iter().filter_map(|(left, best)| {
			let [right] = best.peers.as_slice() else {
				return None;
			};
			let reverse = self.right.get(right)?;
			(reverse.score == best.score && reverse.peers.as_slice() == [*left]).then_some(
				RecoveryCandidate {
					left: *left,
					right: *right,
					score: best.score,
				},
			)
		})
	}
}

fn subtree_features(
	tree: &NormalizedTree,
	root: NodeId,
) -> BTreeMap<(String, Option<String>), usize> {
	let mut features = BTreeMap::new();
	let mut stack = vec![root];
	while let Some(id) = stack.pop() {
		let node = tree.node(id).unwrap();
		*features
			.entry((node.kind.clone(), node.value.clone()))
			.or_default() += 1;
		stack.extend(node.children.iter().rev().copied());
	}
	features
}

fn subtree_lineage_hashes(tree: &NormalizedTree, root: NodeId) -> BTreeSet<SubtreeHash> {
	let mut hashes = BTreeSet::new();
	let mut stack = vec![root];
	while let Some(id) = stack.pop() {
		let node = tree.node(id).unwrap();
		// Scalars are often shared boilerplate and are too weak to establish lineage.
		// An exact non-leaf root, however, is stronger evidence than a descendant.
		if !node.children.is_empty() {
			hashes.insert(node.subtree_hash);
		}
		stack.extend(node.children.iter().rev().copied());
	}
	hashes
}

fn raw_subtree_similarity(
	left: &BTreeMap<(String, Option<String>), usize>,
	right: &BTreeMap<(String, Option<String>), usize>,
) -> u32 {
	let left_size = left.values().sum::<usize>();
	let right_size = right.values().sum::<usize>();
	let denominator = left_size + right_size;
	if denominator == 0 {
		return 0;
	}
	let overlap = left
		.iter()
		.map(|(feature, left_count)| left_count.min(right.get(feature).unwrap_or(&0)))
		.sum::<usize>();
	u32::try_from((2_000_000usize.saturating_mul(overlap)) / denominator).unwrap_or(1_000_000)
}

fn record_unresolved_repeated_sibling_ambiguities(
	left: &NormalizedTree,
	right: &NormalizedTree,
	matching: &mut Matching,
	threshold: u32,
) {
	let parents = matching.records().copied().collect::<Vec<_>>();
	for parent in parents {
		let left_groups = unmatched_parent_anchor_groups(
			left,
			&left.node(parent.left).unwrap().children,
			matching,
			true,
		);
		let right_groups = unmatched_parent_anchor_groups(
			right,
			&right.node(parent.right).unwrap().children,
			matching,
			false,
		);
		for (key, left_nodes) in &left_groups.free {
			let Some(right_nodes) = right_groups.free.get(key) else {
				continue;
			};
			let repeated = left_groups.repeats(key) || right_groups.repeats(key);
			if !repeated {
				continue;
			}
			let mut candidates = repeated_sibling_candidates(
				left,
				right,
				matching,
				left_nodes,
				right_nodes,
				threshold,
			);
			for &left_node in left_nodes {
				let Some(best) = candidates.left.remove(&left_node) else {
					continue;
				};
				matching.record_ambiguity(AmbiguousMatch {
					left: left_node,
					candidates: best.peers,
					score: best.score,
				});
			}
		}
	}
}

fn match_required_slots(
	left: &NormalizedTree,
	right: &NormalizedTree,
	matching: &mut Matching,
	work: &mut MatchWork,
) {
	loop {
		let parents = work.required_slots.take(left, right, matching);
		let mut changed = false;
		for parent in parents {
			let left_parent = left.node(parent.left).unwrap();
			let right_parent = right.node(parent.right).unwrap();
			if left_parent.child_cardinality != ChildCardinality::ExactlyOne
				|| right_parent.child_cardinality != ChildCardinality::ExactlyOne
			{
				continue;
			}
			let ([left_child], [right_child]) = (
				left_parent.children.as_slice(),
				right_parent.children.as_slice(),
			) else {
				continue;
			};
			if !compatible_at(left, right, matching, *left_child, *right_child) {
				continue;
			}
			let matched_right = matching.get_from_left(*left_child);
			let matched_left = matching.get_from_right(*right_child);
			if matched_right.is_some_and(|matched| matched != *right_child)
				|| matched_left.is_some_and(|matched| matched != *left_child)
			{
				matching.record_ambiguity(AmbiguousMatch {
					left: *left_child,
					candidates: vec![*right_child],
					score: 1_000_000,
				});
				continue;
			}
			if matched_right == Some(*right_child) {
				continue;
			}
			changed |= matching.insert(MatchRecord {
				left: *left_child,
				right: *right_child,
				kind: MatchKind::RequiredSlot,
				score: 1_000_000,
			});
		}
		if !changed {
			break;
		}
	}
}

fn match_exact_subtrees(
	left: &NormalizedTree,
	right: &NormalizedTree,
	matching: &mut Matching,
	min_height: u32,
) {
	let mut right_by_hash: BTreeMap<SubtreeHash, Vec<NodeId>> = BTreeMap::new();
	for (right_id, right_node) in right.nodes() {
		if right_node.height >= min_height
			&& !matching.is_right_matched(right_id)
			&& !child_of_unmatched_required_parent(right, right_id, matching, false)
		{
			right_by_hash
				.entry(right_node.subtree_hash)
				.or_default()
				.push(right_id);
		}
	}
	let mut left_nodes = left
		.nodes()
		.filter(|(id, node)| {
			node.height >= min_height
				&& !matching.is_left_matched(*id)
				&& !child_of_unmatched_required_parent(left, *id, matching, true)
		})
		.collect::<Vec<_>>();
	left_nodes.sort_by(|(left_id, left_node), (right_id, right_node)| {
		right_node
			.height
			.cmp(&left_node.height)
			.then_with(|| left_id.cmp(right_id))
	});
	for (left_id, left_node) in left_nodes {
		let Some(candidates) = right_by_hash.get(&left_node.subtree_hash) else {
			continue;
		};
		let mut ranked = candidates
			.iter()
			.copied()
			.filter(|right_id| !matching.is_right_matched(*right_id))
			.filter(|right_id| compatible_at(left, right, matching, left_id, *right_id))
			.map(|right_id| {
				(
					right_id,
					exact_context_score(left, right, matching, left_id, right_id),
				)
			})
			.collect::<Vec<_>>();
		ranked.sort_by(|(left_id, left_score), (right_id, right_score)| {
			right_score
				.cmp(left_score)
				.then_with(|| left_id.cmp(right_id))
		});
		let Some((right_id, _)) = ranked.first().copied() else {
			continue;
		};
		match_isomorphic_subtree(left, right, matching, left_id, right_id);
	}
}

fn child_of_unmatched_required_parent(
	tree: &NormalizedTree,
	id: NodeId,
	matching: &Matching,
	left_side: bool,
) -> bool {
	let Some(parent) = tree.node(id).unwrap().parent else {
		return false;
	};
	if tree.node(parent).unwrap().child_cardinality != ChildCardinality::ExactlyOne {
		return false;
	}
	if left_side {
		!matching.is_left_matched(parent)
	} else {
		!matching.is_right_matched(parent)
	}
}

fn exact_context_score(
	left: &NormalizedTree,
	right: &NormalizedTree,
	matching: &Matching,
	left_id: NodeId,
	right_id: NodeId,
) -> u32 {
	let left_node = left.node(left_id).unwrap();
	let right_node = right.node(right_id).unwrap();
	let mut score = 0;
	if let (Some(left_parent), Some(right_parent)) = (left_node.parent, right_node.parent)
		&& matching.get_from_left(left_parent) == Some(right_parent)
	{
		score += 100;
		let left_index = child_index(left, left_parent, left_id);
		let right_index = child_index(right, right_parent, right_id);
		if left_index == right_index {
			score += 20;
		}
	}
	score
}

fn child_index(tree: &NormalizedTree, parent: NodeId, child: NodeId) -> Option<usize> {
	tree.node(parent)
		.unwrap()
		.children
		.iter()
		.position(|candidate| *candidate == child)
}

fn match_isomorphic_subtree(
	left: &NormalizedTree,
	right: &NormalizedTree,
	matching: &mut Matching,
	left_id: NodeId,
	right_id: NodeId,
) {
	let Some(child_pairs) = isomorphic_child_pairs(left, right, left_id, right_id) else {
		return;
	};
	matching.insert(MatchRecord {
		left: left_id,
		right: right_id,
		kind: MatchKind::Exact,
		score: 1_000_000,
	});
	for (left_child, right_child) in child_pairs {
		match_isomorphic_subtree(left, right, matching, left_child, right_child);
	}
}

fn isomorphic_subtree(
	left: &NormalizedTree,
	right: &NormalizedTree,
	left_id: NodeId,
	right_id: NodeId,
) -> bool {
	isomorphic_child_pairs(left, right, left_id, right_id).is_some()
}

fn isomorphic_child_pairs(
	left: &NormalizedTree,
	right: &NormalizedTree,
	left_id: NodeId,
	right_id: NodeId,
) -> Option<Vec<(NodeId, NodeId)>> {
	let left_node = left.node(left_id).ok()?;
	let right_node = right.node(right_id).ok()?;
	if left_node.subtree_hash != right_node.subtree_hash
		|| !shallow_tree_eq(left_node, right_node)
		|| left_node.children.len() != right_node.children.len()
	{
		return None;
	}
	if left_node.child_order == crate::merge::kernel::ChildOrder::Ordered {
		let pairs = left_node
			.children
			.iter()
			.copied()
			.zip(right_node.children.iter().copied())
			.collect::<Vec<_>>();
		return pairs
			.iter()
			.all(|(left_child, right_child)| {
				isomorphic_subtree(left, right, *left_child, *right_child)
			})
			.then_some(pairs);
	}

	let mut remaining = right_node.children.clone();
	let mut pairs = Vec::with_capacity(left_node.children.len());
	for left_child in &left_node.children {
		let left_hash = left.node(*left_child).ok()?.subtree_hash;
		let index = remaining.iter().position(|right_child| {
			right
				.node(*right_child)
				.is_ok_and(|node| node.subtree_hash == left_hash)
				&& isomorphic_subtree(left, right, *left_child, *right_child)
		})?;
		pairs.push((*left_child, remaining.remove(index)));
	}
	Some(pairs)
}

fn shallow_tree_eq(left: &NormalizedNode, right: &NormalizedNode) -> bool {
	left.kind == right.kind
		&& left.value == right.value
		&& left.anchor == right.anchor
		&& left.signature == right.signature
		&& left.child_order == right.child_order
		&& left.child_cardinality == right.child_cardinality
}

fn match_by_descendants(
	left: &NormalizedTree,
	right: &NormalizedTree,
	matching: &mut Matching,
	threshold: u32,
) {
	let mut right_by_kind: BTreeMap<&str, Vec<NodeId>> = BTreeMap::new();
	for (id, node) in right.nodes() {
		right_by_kind.entry(&node.kind).or_default().push(id);
	}
	let mut changed = true;
	while changed {
		changed = false;
		let mut left_nodes = left
			.nodes()
			.filter(|(id, node)| {
				!node.children.is_empty()
					&& !matching.is_left_matched(*id)
					&& !matching.is_left_ambiguous(*id)
					&& !child_of_unmatched_required_parent(left, *id, matching, true)
			})
			.collect::<Vec<_>>();
		left_nodes.sort_by(|(left_id, left_node), (right_id, right_node)| {
			left_node
				.height
				.cmp(&right_node.height)
				.then_with(|| left_id.cmp(right_id))
		});
		for (left_id, left_node) in left_nodes {
			let mut candidates =
				descendant_candidate_nodes(left_node, right, matching, &right_by_kind)
					.iter()
					.copied()
					.filter(|right_id| {
						!matching.is_right_matched(*right_id)
							&& !matching.is_right_ambiguous(*right_id)
							&& !child_of_unmatched_required_parent(
								right, *right_id, matching, false,
							) && compatible_at(left, right, matching, left_id, *right_id)
					})
					.map(|right_id| {
						(
							right_id,
							descendant_similarity(left, right, matching, left_id, right_id),
						)
					})
					.filter(|(_, score)| *score >= threshold)
					.collect::<Vec<_>>();
			candidates.sort_by(|(left_id, left_score), (right_id, right_score)| {
				right_score
					.cmp(left_score)
					.then_with(|| left_id.cmp(right_id))
			});
			let Some((right_id, best_score)) = candidates.first().copied() else {
				continue;
			};
			let tied = candidates
				.iter()
				.take_while(|(_, score)| *score == best_score)
				.map(|(candidate, _)| *candidate)
				.collect::<Vec<_>>();
			if tied.len() > 1 {
				matching.record_ambiguity(AmbiguousMatch {
					left: left_id,
					candidates: tied,
					score: best_score,
				});
				continue;
			}
			changed |= matching.insert(MatchRecord {
				left: left_id,
				right: right_id,
				kind: MatchKind::DescendantSimilarity,
				score: best_score,
			});
		}
	}
}

fn descendant_candidate_nodes<'a>(
	left: &NormalizedNode,
	right: &'a NormalizedTree,
	matching: &Matching,
	right_by_kind: &'a BTreeMap<&str, Vec<NodeId>>,
) -> &'a [NodeId] {
	// Parent-scoped anchors can only match children of an already corresponding
	// parent. Do not scan an entire file to rediscover that restriction per node.
	if left
		.anchor
		.as_ref()
		.is_some_and(|anchor| anchor.scope == SemanticKeyScope::Parent)
	{
		return left
			.parent
			.and_then(|parent| matching.get_from_left(parent))
			.and_then(|parent| right.node(parent).ok())
			.map_or(&[], |parent| parent.children.as_slice());
	}
	right_by_kind
		.get(left.kind.as_str())
		.map(Vec::as_slice)
		.unwrap_or_default()
}

fn descendant_similarity(
	left: &NormalizedTree,
	right: &NormalizedTree,
	matching: &Matching,
	left_root: NodeId,
	right_root: NodeId,
) -> u32 {
	let left_descendants = descendants(left, left_root);
	let right_descendants = descendants(right, right_root);
	let right_set = right_descendants.iter().copied().collect::<BTreeSet<_>>();
	let overlap = left_descendants
		.iter()
		.filter_map(|left_id| matching.get_from_left(*left_id))
		.filter(|right_id| right_set.contains(right_id))
		.count();
	let denominator = left_descendants.len() + right_descendants.len() + 2;
	if denominator == 0 {
		return 0;
	}
	u32::try_from((2_000_000usize.saturating_mul(overlap)) / denominator).unwrap_or(1_000_000)
}

fn descendants(tree: &NormalizedTree, root: NodeId) -> Vec<NodeId> {
	let mut descendants = Vec::new();
	let mut stack = tree.node(root).unwrap().children.clone();
	while let Some(node) = stack.pop() {
		descendants.push(node);
		stack.extend(tree.node(node).unwrap().children.iter().rev().copied());
	}
	descendants
}

#[derive(Clone, Copy, Debug, Eq, PartialEq)]
struct RecoveryCandidate {
	left: NodeId,
	right: NodeId,
	score: u32,
}

fn recover_children(
	left: &NormalizedTree,
	right: &NormalizedTree,
	matching: &mut Matching,
	max_recovery_size: usize,
	work: &mut MatchWork,
) {
	let mut processed = BTreeSet::new();
	loop {
		match_required_slots(left, right, matching, work);
		let mut parents = matching
			.records()
			.copied()
			.filter(|record| processed.insert((record.left, record.right)))
			.collect::<Vec<_>>();
		if parents.is_empty() {
			break;
		}
		parents.sort_by(|left_record, right_record| {
			left.node(left_record.left)
				.unwrap()
				.height
				.cmp(&left.node(right_record.left).unwrap().height)
				.then_with(|| left_record.left.cmp(&right_record.left))
		});
		for parent in parents {
			let left_parent = left.node(parent.left).unwrap();
			let right_parent = right.node(parent.right).unwrap();
			let left_children = left_parent.children.clone();
			let right_children = right_parent.children.clone();
			if left_parent.child_cardinality == ChildCardinality::ExactlyOne
				&& right_parent.child_cardinality == ChildCardinality::ExactlyOne
			{
				continue;
			}
			if left_children.len().saturating_mul(right_children.len())
				> max_recovery_size.saturating_mul(max_recovery_size)
			{
				continue;
			}
			let mut candidates = Vec::new();
			for (left_index, left_id) in left_children.iter().copied().enumerate() {
				if matching.is_left_matched(left_id) || matching.is_left_ambiguous(left_id) {
					continue;
				}
				for (right_index, right_id) in right_children.iter().copied().enumerate() {
					if matching.is_right_matched(right_id) || matching.is_right_ambiguous(right_id)
					{
						continue;
					}
					let Some(score) = recovery_score(
						left,
						right,
						matching,
						left_id,
						right_id,
						left_index,
						right_index,
					) else {
						continue;
					};
					candidates.push(RecoveryCandidate {
						left: left_id,
						right: right_id,
						score,
					});
				}
			}
			candidates.sort_by(|left_candidate, right_candidate| {
				right_candidate
					.score
					.cmp(&left_candidate.score)
					.then_with(|| left_candidate.left.cmp(&right_candidate.left))
					.then_with(|| left_candidate.right.cmp(&right_candidate.right))
			});
			for candidate in candidates {
				matching.insert(MatchRecord {
					left: candidate.left,
					right: candidate.right,
					kind: MatchKind::Recovery,
					score: candidate.score,
				});
			}
		}
	}
}

#[allow(clippy::too_many_arguments)]
fn recovery_score(
	left: &NormalizedTree,
	right: &NormalizedTree,
	matching: &Matching,
	left_id: NodeId,
	right_id: NodeId,
	left_index: usize,
	right_index: usize,
) -> Option<u32> {
	let left_node = left.node(left_id).unwrap();
	let right_node = right.node(right_id).unwrap();
	if !compatible_at(left, right, matching, left_id, right_id) {
		return None;
	}
	if let (Some(left_anchor), Some(right_anchor)) = (&left_node.anchor, &right_node.anchor)
		&& left_anchor == right_anchor
	{
		if left_anchor.scope == SemanticKeyScope::Parent
			&& (anchor_repeats_under_parent(left, left_id, left_anchor)
				|| anchor_repeats_under_parent(right, right_id, right_anchor))
		{
			return None;
		}
		return Some(1_000_000);
	}
	if left_node.subtree_hash == right_node.subtree_hash
		&& isomorphic_subtree(left, right, left_id, right_id)
	{
		return Some(950_000);
	}
	let similarity = descendant_similarity(left, right, matching, left_id, right_id);
	if similarity > 0 {
		return Some(600_000u32.saturating_add(similarity / 3));
	}
	if left_index == right_index
		&& left_node.signature.is_some()
		&& right_node.signature.is_some()
		&& left_node.signature != right_node.signature
	{
		return Some(575_000);
	}
	if left_node.children.is_empty() && right_node.children.is_empty() && left_index == right_index
	{
		return Some(if left_node.value == right_node.value {
			550_000
		} else {
			500_000
		});
	}
	None
}

fn anchor_repeats_under_parent(tree: &NormalizedTree, id: NodeId, anchor: &SemanticKey) -> bool {
	let Some(parent) = tree.node(id).unwrap().parent else {
		return false;
	};
	tree.node(parent)
		.unwrap()
		.children
		.iter()
		.filter(|child| tree.node(**child).unwrap().anchor.as_ref() == Some(anchor))
		.count()
		> 1
}

#[cfg(test)]
mod tests {
	use super::*;
	use crate::merge::kernel::TreeNode;

	fn scalar(value: &str) -> TreeNode {
		TreeNode::leaf("scalar", value)
	}

	fn block(kind: &str, children: Vec<TreeNode>) -> TreeNode {
		TreeNode::branch(kind, children)
	}

	#[test]
	fn descendant_candidate_index_preserves_all_compatible_pairs() {
		let fixture = |value: &str| {
			NormalizedTree::from_root(block(
				"root",
				(0..16)
					.map(|_| {
						block(
							"parent",
							vec![
								block("entry", vec![scalar(value)])
									.with_parent_scoped_anchor("entry.key", "shared"),
								block("entry", vec![scalar(value)]),
								block("other", vec![scalar(value)]),
							],
						)
					})
					.collect(),
			))
			.unwrap()
		};
		let left = fixture("left");
		let right = fixture("right");
		let mut right_by_kind: BTreeMap<&str, Vec<NodeId>> = BTreeMap::new();
		for (id, node) in right.nodes() {
			right_by_kind.entry(&node.kind).or_default().push(id);
		}
		for mapped_parents in [false, true] {
			let mut matching = Matching::default();
			if mapped_parents {
				for (left, right) in left
					.node(left.root())
					.unwrap()
					.children
					.iter()
					.zip(right.node(right.root()).unwrap().children.iter().rev())
				{
					matching.insert(MatchRecord {
						left: *left,
						right: *right,
						kind: MatchKind::Recovery,
						score: 500_000,
					});
				}
			}
			for (id, node) in left.nodes() {
				let expected: Vec<_> = right
					.nodes()
					.map(|(id, _)| id)
					.filter(|right_id| compatible_at(&left, &right, &matching, id, *right_id))
					.collect();
				let candidates =
					descendant_candidate_nodes(node, &right, &matching, &right_by_kind);
				let actual: Vec<_> = candidates
					.iter()
					.copied()
					.filter(|right_id| compatible_at(&left, &right, &matching, id, *right_id))
					.collect();
				assert_eq!(
					actual, expected,
					"node {id:?}, parents mapped: {mapped_parents}"
				);
				if node
					.anchor
					.as_ref()
					.is_some_and(|anchor| anchor.scope == SemanticKeyScope::Parent)
				{
					assert!(
						candidates.len() <= 3,
						"parent-scoped lookup must not scan other parents"
					);
				}
			}
		}
	}

	#[test]
	fn ambiguity_membership_preserves_wire_format_and_rebuilds_on_decode() {
		let mut matching = Matching::default();
		let first = AmbiguousMatch {
			left: NodeId::new(1),
			candidates: vec![NodeId::new(3), NodeId::new(4)],
			score: 700_000,
		};
		matching.record_ambiguity(first.clone());
		matching.record_ambiguity(first);
		matching.record_ambiguity(AmbiguousMatch {
			left: NodeId::new(2),
			candidates: vec![NodeId::new(4)],
			score: 800_000,
		});
		assert_eq!(matching.ambiguities().len(), 2);
		let encoded = serde_json::to_value(&matching).unwrap();
		assert!(encoded["ambiguous"].is_array());
		let decoded: Matching = serde_json::from_value(encoded).unwrap();
		assert_eq!(decoded, matching);
		for node in 0..6 {
			let node = NodeId::new(node);
			assert_eq!(
				decoded.is_left_ambiguous(node),
				matching
					.ambiguities()
					.iter()
					.any(|entry| entry.left == node)
			);
			assert_eq!(
				decoded.is_right_ambiguous(node),
				matching
					.ambiguities()
					.iter()
					.any(|entry| entry.candidates.contains(&node))
			);
		}
	}

	#[test]
	fn sibling_candidate_summary_matches_exhaustive_pair_selection_and_ties() {
		// All 3x3 relations with absent, low and high scores, including asymmetric
		// competition and ties. The oracle deliberately scans the small relation.
		for relation in 0..3_u32.pow(9) {
			let mut encoded = relation;
			let mut all: Vec<RecoveryCandidate> = Vec::new();
			let mut summary = SiblingCandidates::default();
			for left in 0..3 {
				for right in 0..3 {
					let score = encoded % 3;
					encoded /= 3;
					if score == 0 {
						continue;
					}
					let candidate = RecoveryCandidate {
						left: NodeId::new(left),
						right: NodeId::new(right),
						score,
					};
					all.push(candidate);
					summary.insert(candidate);
				}
			}
			let expected: Vec<_> = all
				.iter()
				.copied()
				.filter(|candidate| {
					let competes = |other: &&RecoveryCandidate| {
						other.left == candidate.left || other.right == candidate.right
					};
					all.iter()
						.filter(competes)
						.all(|other| other == candidate || other.score < candidate.score)
				})
				.collect();
			assert_eq!(
				summary.mutual_unique_best().collect::<Vec<_>>(),
				expected,
				"relation {relation}"
			);
			for left in 0..3 {
				let left = NodeId::new(left);
				let best_score = all
					.iter()
					.filter(|candidate| candidate.left == left)
					.map(|candidate| candidate.score)
					.max();
				assert_eq!(summary.left.get(&left).map(|best| best.score), best_score);
				if let Some(best) = summary.left.get(&left) {
					let ties: Vec<_> = all
						.iter()
						.filter(|candidate| candidate.left == left && candidate.score == best.score)
						.map(|candidate| candidate.right)
						.collect();
					assert_eq!(best.peers, ties, "ties for relation {relation}");
				}
			}
		}
	}

	#[test]
	fn dense_sibling_candidates_retain_only_endpoint_maxima() {
		const COUNT: u32 = 256;
		let mut summary = SiblingCandidates::default();
		for left in 0..COUNT {
			for right in 0..COUNT {
				summary.insert(RecoveryCandidate {
					left: NodeId::new(left),
					right: NodeId::new(right),
					score: if left == right { 900_000 } else { 600_000 },
				});
			}
		}
		assert_eq!(summary.left.len(), COUNT as usize);
		assert_eq!(summary.right.len(), COUNT as usize);
		assert_eq!(
			summary
				.left
				.values()
				.chain(summary.right.values())
				.map(|best| best.peers.len())
				.sum::<usize>(),
			2 * COUNT as usize
		);
		let selected: Vec<_> = summary.mutual_unique_best().collect();
		assert_eq!(selected.len(), COUNT as usize);
		assert!(
			selected
				.iter()
				.all(|candidate| candidate.left == candidate.right && candidate.score == 900_000)
		);
	}

	fn seeded_lineage_block(child: TreeNode) -> TreeNode {
		let mut node = block("condition", vec![child]);
		node.anchor = Some(
			SemanticKey::parent_scoped("condition.tooltip", "shared").requiring_seeded_lineage(),
		);
		node
	}

	#[test]
	fn exact_subtrees_match_recursively() {
		let left = NormalizedTree::from_root(block(
			"root",
			vec![block("entry", vec![scalar("a"), scalar("b")])],
		))
		.unwrap();
		let right = left.clone();
		let matching = TreeMatcher::default().match_trees(&left, &right);

		assert_eq!(matching.len(), left.len());
		assert!(
			matching
				.records()
				.all(|record| record.kind == MatchKind::Exact)
		);
	}

	#[test]
	fn semantic_anchors_match_modified_subtrees() {
		let left = NormalizedTree::from_root(block(
			"root",
			vec![block("option", vec![scalar("old")]).with_anchor("option.name", "A")],
		))
		.unwrap();
		let right = NormalizedTree::from_root(block(
			"root",
			vec![block("option", vec![scalar("new")]).with_anchor("option.name", "A")],
		))
		.unwrap();
		let matching = TreeMatcher::default().match_trees(&left, &right);

		assert_eq!(matching.get_from_left(NodeId::new(1)), Some(NodeId::new(1)));
		assert_eq!(
			matching.record(NodeId::new(1)).unwrap().kind,
			MatchKind::SemanticAnchor
		);
	}

	#[test]
	fn parent_scoped_anchors_only_match_within_corresponding_parents() {
		let parent = |name: &str, value: &str| {
			block(
				"parent",
				vec![
					block("entry", vec![scalar(value)])
						.with_parent_scoped_anchor("entry.name", "shared"),
				],
			)
			.with_anchor("parent.name", name)
		};
		let left = NormalizedTree::from_root(block(
			"root",
			vec![parent("A", "left-a"), parent("B", "left-b")],
		))
		.unwrap();
		let right = NormalizedTree::from_root(block(
			"root",
			vec![parent("B", "right-b"), parent("A", "right-a")],
		))
		.unwrap();

		let matching = TreeMatcher::default().match_trees(&left, &right);

		assert_eq!(matching.get_from_left(NodeId::new(2)), Some(NodeId::new(5)));
		assert_eq!(matching.get_from_left(NodeId::new(5)), Some(NodeId::new(2)));
		assert_eq!(
			matching.record(NodeId::new(2)).unwrap().kind,
			MatchKind::SemanticAnchor
		);
	}

	#[test]
	fn repeated_parent_scoped_siblings_match_by_subtree_content() {
		let repeated = |identity: &str, revision: &str| {
			block("entry", vec![scalar(identity), scalar(revision)])
				.with_parent_scoped_anchor("entry.kind", "modifier")
		};
		let left = NormalizedTree::from_root(block(
			"root",
			vec![repeated("a", "left-a"), repeated("b", "left-b")],
		))
		.unwrap();
		let right = NormalizedTree::from_root(block(
			"root",
			vec![repeated("b", "right-b"), repeated("a", "right-a")],
		))
		.unwrap();

		let matching = TreeMatcher::default().match_trees(&left, &right);

		assert_eq!(matching.get_from_left(NodeId::new(1)), Some(NodeId::new(4)));
		assert_eq!(matching.get_from_left(NodeId::new(4)), Some(NodeId::new(1)));
	}

	#[test]
	fn ordered_similarity_siblings_align_around_an_insertion() {
		let item = |identity: &str, revision: &str| {
			block(
				"chain",
				vec![block("identity", vec![scalar(identity)]), scalar(revision)],
			)
			.with_parent_scoped_ordered_similarity_position_anchor("sequence", "open_chain")
		};
		let left = NormalizedTree::from_root(block(
			"root",
			vec![
				item("x", "left-x"),
				item("a", "left-a"),
				item("b", "left-b"),
				item("c", "same-c"),
			],
		))
		.unwrap();
		let right = NormalizedTree::from_root(block(
			"root",
			vec![
				item("a", "right-a"),
				item("b", "right-b"),
				item("c", "same-c"),
			],
		))
		.unwrap();

		let matching = TreeMatcher::default().match_trees(&left, &right);

		assert_eq!(matching.get_from_left(NodeId::new(1)), None);
		assert_eq!(matching.get_from_left(NodeId::new(5)), Some(NodeId::new(1)));
		assert_eq!(matching.get_from_left(NodeId::new(9)), Some(NodeId::new(5)));
		assert_eq!(
			matching.get_from_left(NodeId::new(13)),
			Some(NodeId::new(9))
		);
		assert!(matching.ambiguities().is_empty());
	}

	#[test]
	fn ordered_similarity_anchor_values_are_soft_identity() {
		let item = |anchor: &str, value: &str| {
			block("chain", vec![scalar(value)])
				.with_parent_scoped_ordered_similarity_position_anchor("sequence", anchor)
		};
		let left = NormalizedTree::from_root(block(
			"root",
			vec![item("old-a", "left-a"), item("old-b", "left-b")],
		))
		.unwrap();
		let right = NormalizedTree::from_root(block(
			"root",
			vec![item("new-a", "right-a"), item("new-b", "right-b")],
		))
		.unwrap();

		let matching = TreeMatcher::default().match_trees(&left, &right);

		assert_eq!(matching.get_from_left(NodeId::new(1)), Some(NodeId::new(1)));
		assert_eq!(matching.get_from_left(NodeId::new(3)), Some(NodeId::new(3)));
		assert!(matching.ambiguities().is_empty());
	}

	#[test]
	fn positional_fallback_does_not_force_unequal_dissimilar_siblings_to_match() {
		let item = |value: &str| {
			block("chain", vec![scalar(value)])
				.with_parent_scoped_ordered_similarity_position_anchor("sequence", "open_chain")
		};
		let left =
			NormalizedTree::from_root(block("root", vec![item("left-a"), item("left-b")])).unwrap();
		let right = NormalizedTree::from_root(block("root", vec![item("right-only")])).unwrap();

		let matching = TreeMatcher::default().match_trees(&left, &right);

		assert_eq!(matching.get_from_left(NodeId::new(1)), None);
		assert_eq!(matching.get_from_left(NodeId::new(3)), None);
		assert_eq!(matching.get_from_right(NodeId::new(1)), None);
		assert!(matching.ambiguities().is_empty());
	}

	#[test]
	fn unequal_gaps_reject_weak_similarity_above_the_similarity_threshold() {
		let item = |identity: &str, changed: &[&str]| {
			let children = std::iter::once(block("shared", vec![scalar("same")]))
				.chain(changed.iter().map(|value| scalar(value)))
				.collect();
			block("chain", children)
				.with_parent_scoped_ordered_similarity_position_anchor("sequence", "open_chain")
				.with_signature(identity)
		};
		let left = NormalizedTree::from_root(block(
			"root",
			vec![
				item("left-a", &["left", "left-extra"]),
				item("left-b", &["unrelated", "left-only"]),
			],
		))
		.unwrap();
		let right = NormalizedTree::from_root(block(
			"root",
			vec![item("right", &["right", "additional", "right-extra"])],
		))
		.unwrap();

		let matching = TreeMatcher::default().match_trees(&left, &right);

		assert_eq!(matching.get_from_left(NodeId::new(1)), None);
		assert_eq!(matching.get_from_right(NodeId::new(1)), None);
		assert!(matching.ambiguities().is_empty());
	}

	#[test]
	fn unique_signature_does_not_bypass_unequal_gap_evidence_threshold() {
		let item = |signature: &str, value: &str| {
			block("chain", vec![scalar(value)])
				.with_parent_scoped_ordered_similarity_position_anchor("sequence", "open_chain")
				.with_signature(signature)
		};
		let left = NormalizedTree::from_root(block(
			"root",
			vec![
				item("shared-id", "left-value"),
				item("inserted-id", "inserted-value"),
			],
		))
		.unwrap();
		let right =
			NormalizedTree::from_root(block("root", vec![item("shared-id", "right-value")]))
				.unwrap();

		let matching = TreeMatcher::default().match_trees(&left, &right);

		assert_eq!(matching.get_from_left(NodeId::new(1)), None);
		assert_eq!(matching.get_from_right(NodeId::new(1)), None);
	}

	#[test]
	fn unequal_gap_keeps_a_strong_modified_sibling_match() {
		let item = |signature: &str, children: Vec<TreeNode>| {
			block("chain", children)
				.with_parent_scoped_ordered_similarity_position_anchor("sequence", "open_chain")
				.with_signature(signature)
		};
		let left = NormalizedTree::from_root(block(
			"root",
			vec![
				item(
					"inserted",
					vec![
						block("insert-only", vec![scalar("new")]),
						scalar("unrelated"),
					],
				),
				item(
					"left-edited",
					vec![block("shared", vec![scalar("same")]), scalar("left-change")],
				),
			],
		))
		.unwrap();
		let right = NormalizedTree::from_root(block(
			"root",
			vec![item(
				"right-edited",
				vec![
					block("shared", vec![scalar("same")]),
					scalar("right-change"),
					scalar("right-extra"),
				],
			)],
		))
		.unwrap();

		let matching = TreeMatcher::default().match_trees(&left, &right);

		assert_eq!(matching.get_from_left(NodeId::new(1)), None);
		assert_eq!(matching.get_from_left(NodeId::new(5)), Some(NodeId::new(1)));
		assert_eq!(
			matching.record(NodeId::new(5)).unwrap().kind,
			MatchKind::DescendantSimilarity
		);
		assert!(matching.ambiguities().is_empty());
	}

	#[test]
	fn unequal_gap_prefers_unique_lineage_evidence_over_a_higher_dice_insertion() {
		let item = |children: Vec<TreeNode>| {
			block("chain", children)
				.with_parent_scoped_ordered_similarity_position_anchor("sequence", "open_chain")
		};
		let marker = |value: &str| block("field", vec![scalar(value)]);
		let left = NormalizedTree::from_root(block(
			"root",
			vec![
				item(vec![
					marker("common-a"),
					marker("common-b"),
					marker("common-c"),
					marker("inserted-change"),
				]),
				item(vec![
					marker("common-a"),
					marker("common-b"),
					marker("common-c"),
					marker("lineage-marker"),
					marker("edited-a"),
					marker("edited-b"),
					marker("edited-c"),
					marker("edited-d"),
					marker("edited-e"),
					marker("edited-f"),
				]),
			],
		))
		.unwrap();
		let right = NormalizedTree::from_root(block(
			"root",
			vec![item(vec![
				marker("common-a"),
				marker("common-b"),
				marker("common-c"),
				marker("lineage-marker"),
				marker("right-change"),
			])],
		))
		.unwrap();
		let inserted_score = raw_subtree_similarity(
			&subtree_features(&left, NodeId::new(1)),
			&subtree_features(&right, NodeId::new(1)),
		);
		let edited_score = raw_subtree_similarity(
			&subtree_features(&left, NodeId::new(10)),
			&subtree_features(&right, NodeId::new(1)),
		);
		assert!(
			inserted_score > edited_score,
			"{inserted_score} <= {edited_score}"
		);
		assert!(edited_score > 500_000, "{edited_score}");

		let matching = TreeMatcher::default().match_trees(&left, &right);

		assert_eq!(matching.get_from_left(NodeId::new(1)), None);
		assert_eq!(
			matching.get_from_left(NodeId::new(10)),
			Some(NodeId::new(1))
		);
		assert!(matching.ambiguities().is_empty());
	}

	#[test]
	fn ordered_similarity_siblings_respect_interleaved_matches() {
		let open_chain = |identity: &str| {
			block("open_chain", vec![scalar(identity)])
				.with_parent_scoped_ordered_similarity_position_anchor("sequence", "open_chain")
		};
		let closed_chain = || {
			block("closed_chain", vec![scalar("ruler")])
				.with_parent_scoped_anchor("chain.effect", "ruler")
		};
		let left = NormalizedTree::from_root(block(
			"root",
			vec![
				open_chain("left_only"),
				closed_chain(),
				open_chain("shared"),
			],
		))
		.unwrap();
		let right = NormalizedTree::from_root(block(
			"root",
			vec![
				closed_chain(),
				open_chain("right_only"),
				open_chain("shared"),
			],
		))
		.unwrap();

		let matching = TreeMatcher::default().match_trees(&left, &right);

		assert_eq!(matching.get_from_left(NodeId::new(1)), None);
		assert_eq!(matching.get_from_right(NodeId::new(3)), None);
		assert_eq!(matching.get_from_left(NodeId::new(3)), Some(NodeId::new(1)));
		assert_eq!(matching.get_from_left(NodeId::new(5)), Some(NodeId::new(5)));
		assert!(matching.ambiguities().is_empty());
	}

	#[test]
	fn ordered_similarity_siblings_cross_only_as_identical_subtrees() {
		let item = |values: &[&str]| {
			block("chain", values.iter().map(|value| scalar(value)).collect())
				.with_parent_scoped_ordered_similarity_position_anchor("sequence", "open_chain")
		};
		// A chain whose whole subtree occurs once on each side moved.
		let left =
			NormalizedTree::from_root(block("root", vec![item(&["a"]), item(&["b"])])).unwrap();
		let right =
			NormalizedTree::from_root(block("root", vec![item(&["b"]), item(&["a"])])).unwrap();
		let matching = TreeMatcher::default().match_trees(&left, &right);
		assert_eq!(matching.get_from_left(NodeId::new(1)), Some(NodeId::new(3)));
		assert_eq!(matching.get_from_left(NodeId::new(3)), Some(NodeId::new(1)));
		assert!(matching.ambiguities().is_empty());

		// Edited chains are only similar, so their alignment stays monotonic.
		let left = NormalizedTree::from_root(block(
			"root",
			vec![item(&["a", "x", "y", "1"]), item(&["b", "x", "y", "1"])],
		))
		.unwrap();
		let right = NormalizedTree::from_root(block(
			"root",
			vec![item(&["b", "x", "y", "2"]), item(&["a", "x", "y", "2"])],
		))
		.unwrap();
		let matching = TreeMatcher::default().match_trees(&left, &right);
		let crossed = matching.get_from_left(NodeId::new(1)) == Some(NodeId::new(6))
			&& matching.get_from_left(NodeId::new(6)) == Some(NodeId::new(1));
		assert!(!crossed, "{matching:?}");
	}

	#[test]
	fn ordered_similarity_siblings_follow_unique_signatures_across_reorder() {
		let item = |identity: &str, revision: &str| {
			block("case", vec![scalar(identity), scalar(revision)])
				.with_parent_scoped_ordered_similarity_anchor("sequence", "guarded_case")
				.with_signature(identity)
		};
		let left = NormalizedTree::from_root(block(
			"root",
			vec![item("a", "left-a"), item("b", "left-b")],
		))
		.unwrap();
		let right = NormalizedTree::from_root(block(
			"root",
			vec![item("b", "right-b"), item("a", "right-a")],
		))
		.unwrap();

		let matching = TreeMatcher::default().match_trees(&left, &right);

		assert_eq!(matching.get_from_left(NodeId::new(1)), Some(NodeId::new(4)));
		assert_eq!(matching.get_from_left(NodeId::new(4)), Some(NodeId::new(1)));
		assert!(matching.ambiguities().is_empty());
	}

	#[test]
	fn ambiguous_repeated_parent_scoped_siblings_do_not_fall_back_to_position() {
		let repeated = |value: &str| {
			block("entry", vec![scalar("shared"), scalar(value)])
				.with_parent_scoped_anchor("entry.kind", "modifier")
		};
		let left =
			NormalizedTree::from_root(block("root", vec![repeated("left-a"), repeated("left-b")]))
				.unwrap();
		let right = NormalizedTree::from_root(block(
			"root",
			vec![repeated("right-a"), repeated("right-b")],
		))
		.unwrap();

		let matching = TreeMatcher::default().match_trees(&left, &right);

		assert_eq!(matching.get_from_left(NodeId::new(1)), None);
		assert_eq!(matching.get_from_left(NodeId::new(4)), None);
		assert_eq!(matching.ambiguities().len(), 2);
	}

	#[test]
	fn dissimilar_repeated_parent_scoped_siblings_remain_independent() {
		let repeated = |child_kind: &str, value: &str| {
			block("entry", vec![block(child_kind, vec![scalar(value)])])
				.with_parent_scoped_anchor("entry.kind", "modifier")
		};
		let left = NormalizedTree::from_root(block(
			"root",
			vec![repeated("left-a", "one"), repeated("left-b", "two")],
		))
		.unwrap();
		let right = NormalizedTree::from_root(block(
			"root",
			vec![repeated("right-a", "three"), repeated("right-b", "four")],
		))
		.unwrap();

		let matching = TreeMatcher::default().match_trees(&left, &right);

		assert_eq!(matching.get_from_left(NodeId::new(1)), None);
		assert_eq!(matching.get_from_left(NodeId::new(4)), None);
		assert!(matching.ambiguities().is_empty());
	}

	#[test]
	fn residual_repeated_siblings_do_not_fall_back_to_key_only_matching() {
		let repeated = |value: &str| {
			block("entry", vec![scalar(value)])
				.with_parent_scoped_anchor("entry.kind", "trade_goods")
		};
		let left =
			NormalizedTree::from_root(block("root", vec![repeated("ivory"), repeated("cloves")]))
				.unwrap();
		let right =
			NormalizedTree::from_root(block("root", vec![repeated("ivory"), repeated("fur")]))
				.unwrap();

		let matching = TreeMatcher::default().match_trees(&left, &right);

		assert_eq!(matching.get_from_left(NodeId::new(1)), Some(NodeId::new(1)));
		assert_eq!(matching.get_from_left(NodeId::new(3)), None);
		assert_eq!(matching.get_from_right(NodeId::new(3)), None);
		assert!(matching.ambiguities().is_empty());
	}

	#[test]
	fn required_slot_matches_divergent_compatible_children() {
		let slot = |field: &str| {
			NormalizedTree::from_root(
				block(
					"slot",
					vec![block("block", vec![block(field, vec![scalar("yes")])])],
				)
				.with_child_cardinality(ChildCardinality::ExactlyOne),
			)
			.unwrap()
		};
		let left = slot("left_only");
		let right = slot("right_only");

		let matching = TreeMatcher::default().match_trees(&left, &right);

		assert_eq!(matching.get_from_left(NodeId::new(1)), Some(NodeId::new(1)));
		assert_eq!(
			matching.record(NodeId::new(1)).unwrap().kind,
			MatchKind::RequiredSlot
		);
	}

	#[test]
	fn required_slot_reports_a_preexisting_inconsistent_child_match() {
		let tree = || {
			NormalizedTree::from_root(block(
				"root",
				vec![
					block("slot", vec![block("block", vec![scalar("value")])])
						.with_child_cardinality(ChildCardinality::ExactlyOne),
					block("block", vec![scalar("other")]),
				],
			))
			.unwrap()
		};
		let left = tree();
		let right = tree();
		let mut matching = Matching::default();
		for (left, right) in [(0, 0), (1, 1), (2, 4)] {
			matching.insert(MatchRecord {
				left: NodeId::new(left),
				right: NodeId::new(right),
				kind: MatchKind::Recovery,
				score: 500_000,
			});
		}

		match_required_slots(&left, &right, &mut matching, &mut MatchWork::default());

		assert_eq!(matching.ambiguities().len(), 1);
		assert_eq!(matching.ambiguities()[0].left, NodeId::new(2));
		assert_eq!(matching.ambiguities()[0].candidates, vec![NodeId::new(2)]);
	}

	#[test]
	fn incompatible_semantic_anchors_never_match() {
		let left = NormalizedTree::from_root(block(
			"root",
			vec![block("option", vec![scalar("same")]).with_anchor("option.name", "A")],
		))
		.unwrap();
		let right = NormalizedTree::from_root(block(
			"root",
			vec![block("option", vec![scalar("same")]).with_anchor("option.name", "B")],
		))
		.unwrap();
		let matching = TreeMatcher::default().match_trees(&left, &right);

		assert_eq!(matching.get_from_left(NodeId::new(1)), None);
	}

	#[test]
	fn repeated_control_flow_matches_by_descendant_overlap() {
		let left = NormalizedTree::from_root(block(
			"option",
			vec![
				block("if", vec![scalar("republican"), scalar("adm")]),
				block("if", vec![scalar("old_candidate"), scalar("loyalty")]),
			],
		))
		.unwrap();
		let right = NormalizedTree::from_root(block(
			"option",
			vec![
				block("if", vec![scalar("republican"), scalar("adm")]),
				block("if", vec![scalar("upgraded_candidate"), scalar("mil")]),
				block("if", vec![scalar("spread_target"), scalar("support")]),
			],
		))
		.unwrap();
		let matching = TreeMatcher::default().match_trees(&left, &right);

		assert_eq!(matching.get_from_left(NodeId::new(1)), Some(NodeId::new(1)));
		assert_ne!(matching.get_from_left(NodeId::new(4)), Some(NodeId::new(1)));
	}

	#[test]
	fn equal_soft_signatures_match_changed_siblings() {
		let left = NormalizedTree::from_root(block(
			"root",
			vec![block("chain", vec![scalar("left")]).with_signature("guard:a")],
		))
		.unwrap();
		let right = NormalizedTree::from_root(block(
			"root",
			vec![
				block("chain", vec![scalar("unrelated")]).with_signature("guard:b"),
				block("chain", vec![scalar("right")]).with_signature("guard:a"),
			],
		))
		.unwrap();

		let matching = TreeMatcher::default().match_trees(&left, &right);

		assert_eq!(matching.get_from_left(NodeId::new(1)), Some(NodeId::new(3)));
	}

	#[test]
	fn duplicate_soft_signatures_are_reported_as_ambiguous() {
		let left = NormalizedTree::from_root(block(
			"root",
			vec![block("chain", vec![scalar("left")]).with_signature("guard:a")],
		))
		.unwrap();
		let right = NormalizedTree::from_root(block(
			"root",
			vec![
				block("chain", vec![scalar("right-1")]).with_signature("guard:a"),
				block("chain", vec![scalar("right-2")]).with_signature("guard:a"),
			],
		))
		.unwrap();

		let matching = TreeMatcher::default().match_trees(&left, &right);

		assert_eq!(matching.get_from_left(NodeId::new(1)), None);
		assert_eq!(matching.ambiguities().len(), 1);
	}

	#[test]
	fn competing_left_soft_signatures_are_reported_as_ambiguous() {
		let left = NormalizedTree::from_root(block(
			"root",
			vec![
				block("chain", vec![scalar("left-1")]).with_signature("guard:a"),
				block("chain", vec![scalar("left-2")]).with_signature("guard:a"),
			],
		))
		.unwrap();
		let right = NormalizedTree::from_root(block(
			"root",
			vec![block("chain", vec![scalar("right")]).with_signature("guard:a")],
		))
		.unwrap();

		let matching = TreeMatcher::default().match_trees(&left, &right);

		assert_eq!(matching.get_from_left(NodeId::new(1)), None);
		assert_eq!(matching.get_from_left(NodeId::new(3)), None);
		assert_eq!(matching.ambiguities().len(), 2);
	}

	#[test]
	fn positional_recovery_matches_a_fully_rewritten_signed_child() {
		let left = NormalizedTree::from_root(block(
			"root",
			vec![block("branch", vec![scalar("left")]).with_signature("guard:left")],
		))
		.unwrap();
		let right = NormalizedTree::from_root(block(
			"root",
			vec![block("branch", vec![scalar("right")]).with_signature("guard:right")],
		))
		.unwrap();

		let matching = TreeMatcher::default().match_trees(&left, &right);

		assert_eq!(matching.get_from_left(NodeId::new(1)), Some(NodeId::new(1)));
		assert_eq!(
			matching.record(NodeId::new(1)).unwrap().kind,
			MatchKind::Recovery
		);
	}

	#[test]
	fn changed_root_is_linked_without_claiming_an_exact_match() {
		let left = NormalizedTree::from_root(block("root", vec![scalar("left")])).unwrap();
		let right = NormalizedTree::from_root(block("root", vec![scalar("right")])).unwrap();

		let matching = TreeMatcher::default().match_trees(&left, &right);

		assert_eq!(matching.get_from_left(left.root()), Some(right.root()));
		assert_eq!(
			matching.record(left.root()).unwrap().kind,
			MatchKind::Recovery
		);
	}

	#[test]
	fn base_matchings_compose_into_a_left_right_seed() {
		let base = NormalizedTree::from_root(block(
			"root",
			vec![block("entry", vec![scalar("old")]).with_anchor("entry", "a")],
		))
		.unwrap();
		let left = NormalizedTree::from_root(block(
			"root",
			vec![block("entry", vec![scalar("left")]).with_anchor("entry", "a")],
		))
		.unwrap();
		let right = NormalizedTree::from_root(block(
			"root",
			vec![block("entry", vec![scalar("right")]).with_anchor("entry", "a")],
		))
		.unwrap();
		let matcher = TreeMatcher::default();
		let seed = Matching::compose_through_base(
			&matcher.match_trees(&base, &left),
			&matcher.match_trees(&base, &right),
		);

		assert_eq!(seed.get_from_left(NodeId::new(1)), Some(NodeId::new(1)));
		assert_eq!(
			seed.record(NodeId::new(1)).unwrap().kind,
			MatchKind::Recovery
		);
	}

	#[test]
	fn seeded_lineage_keeps_unbased_identical_insertions_separate() {
		let base = NormalizedTree::from_root(block("root", vec![])).unwrap();
		let left = NormalizedTree::from_root(block(
			"root",
			vec![seeded_lineage_block(scalar("identical"))],
		))
		.unwrap();
		let right = left.clone();
		let matcher = TreeMatcher::default();
		let seed = Matching::compose_through_base(
			&matcher.match_trees(&base, &left),
			&matcher.match_trees(&base, &right),
		);

		let matching = matcher.match_trees_with_seed(&left, &right, Some(&seed));

		assert_eq!(matching.get_from_left(left.root()), Some(right.root()));
		assert_eq!(matching.get_from_left(NodeId::new(1)), None);
		assert_eq!(matching.get_from_left(NodeId::new(2)), None);
		assert!(matching.ambiguities().is_empty());
	}

	#[test]
	fn seeded_lineage_correlates_children_from_the_same_base_node() {
		let base = NormalizedTree::from_root(block(
			"root",
			vec![seeded_lineage_block(block("base-body", vec![]))],
		))
		.unwrap();
		let left = NormalizedTree::from_root(block(
			"root",
			vec![seeded_lineage_block(block("left-body", vec![]))],
		))
		.unwrap();
		let right = NormalizedTree::from_root(block(
			"root",
			vec![seeded_lineage_block(block("right-body", vec![]))],
		))
		.unwrap();
		let matcher = TreeMatcher::default();
		let seed = Matching::compose_through_base(
			&matcher.match_trees(&base, &left),
			&matcher.match_trees(&base, &right),
		);

		let matching = matcher.match_trees_with_seed(&left, &right, Some(&seed));

		assert_eq!(seed.get_from_left(NodeId::new(1)), Some(NodeId::new(1)));
		assert_eq!(matching.get_from_left(NodeId::new(1)), Some(NodeId::new(1)));
	}

	#[test]
	fn matching_is_deterministic() {
		let left = NormalizedTree::from_root(block(
			"root",
			vec![
				block("if", vec![scalar("a")]),
				block("if", vec![scalar("b")]),
			],
		))
		.unwrap();
		let right = NormalizedTree::from_root(block(
			"root",
			vec![
				block("if", vec![scalar("b")]),
				block("if", vec![scalar("a")]),
			],
		))
		.unwrap();
		let matcher = TreeMatcher::default();

		assert_eq!(
			matcher.match_trees(&left, &right),
			matcher.match_trees(&left, &right)
		);
	}
}