foch 0.0.1

//! Kernel-neutral per-file dependency graph.
//!
//! DAG-driven N-way merge base resolution (see
//! `docs/dag-merge-design.md`). This module owns dependency topology only;
//! [`super::dag_pipeline`] schedules kernel-specific state construction and
//! joins.
//!
//! Scope of this file:
//! * Build a mod-level dependency DAG from declared `descriptor.mod`
//!   dependencies, resolved against [`ModIdentityIndex`].
//! * Detect cycles via Tarjan's SCC and break them deterministically by
//!   playlist position.
//! * Restrict the global DAG to the subset of mods shipping a particular
//!   file (`induced_file_dag`), lifting edges through skipped nodes.
//! * Apply `replace_path` semantics: drop earlier contributors under the
//!   replaced prefix and mark the replacing contributor in the file DAG.
//! * Expose deterministic ancestry levels for the shared DAG walker.

#![allow(dead_code)]

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

use crate::model::{GamePath, GamePathBuf, ModCandidate};
use crate::playset::dependency::ModIdentityIndex;
use crate::project::DepOverride;

use crate::input::ResolvedInputContributor;

// ---------------------------------------------------------------------------
// Identifiers
// ---------------------------------------------------------------------------

/// Stable identifier for a mod within a single DAG. Currently the same
/// `mod_id` string `ModCandidate` exposes (typically the steam id, or a
/// synthesized id for local mods). Wrapping it as a newtype keeps the API
/// honest: a `ModId` is never confused with an arbitrary `String`.
#[derive(Clone, Debug, Eq, PartialEq, Hash, Ord, PartialOrd)]
pub struct ModId(pub String);

impl ModId {
	pub fn as_str(&self) -> &str {
		&self.0
	}
}

impl From<&str> for ModId {
	fn from(s: &str) -> Self {
		Self(s.to_string())
	}
}

impl From<String> for ModId {
	fn from(s: String) -> Self {
		Self(s)
	}
}

// ---------------------------------------------------------------------------
// Diagnostics
// ---------------------------------------------------------------------------

#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub enum DagDiagnosticSeverity {
	Warning,
	Info,
}

#[derive(Clone, Debug, Eq, PartialEq)]
pub enum DagDiagnosticKind {
	/// `mod_id` declared a dep string that does not resolve in the playset.
	MissingDependency { mod_id: ModId, dep_token: String },
	/// A cycle was detected; lists the mods involved (in topo input order).
	DependencyCycle { members: Vec<ModId> },
	/// An edge was removed to break a cycle.
	BrokenCycleEdge { child: ModId, parent: ModId },
}

#[derive(Clone, Debug, Eq, PartialEq)]
pub struct DagDiagnostic {
	pub severity: DagDiagnosticSeverity,
	pub kind: DagDiagnosticKind,
}

// ---------------------------------------------------------------------------
// ModDag (mod-level)
// ---------------------------------------------------------------------------

#[derive(Clone, Debug, Default)]
pub struct ModDag {
	/// Child → parents (in declaration order, deduplicated).
	parents: HashMap<ModId, Vec<ModId>>,
	/// Parent → children (deterministic order = playlist position of the
	/// child).
	children: HashMap<ModId, Vec<ModId>>,
	/// Topological order (parents before children).
	topo: Vec<ModId>,
	/// Playset position for each mod (stable break tiebreak).
	position: HashMap<ModId, usize>,
	/// Mods declared a dep that wasn't in the playset (collected for
	/// diagnostics; the dep is treated as absent for DAG purposes).
	missing_deps: Vec<(ModId, String)>,
	/// The directories each mod's `replace_path` declares.
	replace_paths: HashMap<ModId, Vec<GamePathBuf>>,
}

impl ModDag {
	pub fn parents_of(&self, mod_id: &ModId) -> &[ModId] {
		self.parents
			.get(mod_id)
			.map(|v| v.as_slice())
			.unwrap_or(&[])
	}

	pub fn children_of(&self, mod_id: &ModId) -> &[ModId] {
		self.children
			.get(mod_id)
			.map(|v| v.as_slice())
			.unwrap_or(&[])
	}

	pub fn topo(&self) -> &[ModId] {
		&self.topo
	}

	pub fn missing_deps(&self) -> &[(ModId, String)] {
		&self.missing_deps
	}

	pub fn position(&self, mod_id: &ModId) -> Option<usize> {
		self.position.get(mod_id).copied()
	}

	pub fn replace_paths(&self, mod_id: &ModId) -> &[GamePathBuf] {
		self.replace_paths
			.get(mod_id)
			.map(|v| v.as_slice())
			.unwrap_or(&[])
	}
}

// ---------------------------------------------------------------------------
// build_mod_dag
// ---------------------------------------------------------------------------

/// Build the mod-level dependency DAG from `mods` (sorted by playlist
/// position). Returns the DAG plus diagnostics for missing deps and cycles.
pub fn build_mod_dag(mods: &[ModCandidate]) -> (ModDag, Vec<DagDiagnostic>) {
	let identity = ModIdentityIndex::from_mods(mods);
	let mut diagnostics = Vec::new();

	let ids: Vec<ModId> = mods.iter().map(|m| ModId(m.mod_id.clone())).collect();
	let mut position: HashMap<ModId, usize> = HashMap::new();
	for (idx, id) in ids.iter().enumerate() {
		position.insert(id.clone(), idx);
	}

	let mut parents: HashMap<ModId, Vec<ModId>> = HashMap::new();
	let mut missing_deps: Vec<(ModId, String)> = Vec::new();
	let mut replace_paths: HashMap<ModId, Vec<GamePathBuf>> = HashMap::new();

	for (idx, candidate) in mods.iter().enumerate() {
		let me = ids[idx].clone();
		let descriptor = match candidate.descriptor.as_ref() {
			Some(d) => d,
			None => {
				parents.entry(me.clone()).or_default();
				continue;
			}
		};

		// Resolve declared deps.
		let mut my_parents: Vec<ModId> = Vec::new();
		let mut seen: HashSet<ModId> = HashSet::new();
		for dep_token in &descriptor.dependencies {
			match identity.lookup(dep_token) {
				Some(parent_idx) if parent_idx != idx => {
					let parent_id = ids[parent_idx].clone();
					if seen.insert(parent_id.clone()) {
						my_parents.push(parent_id);
					}
				}
				Some(_) => {
					// Self-dep: silently drop (not actionable).
				}
				None => {
					diagnostics.push(DagDiagnostic {
						severity: DagDiagnosticSeverity::Warning,
						kind: DagDiagnosticKind::MissingDependency {
							mod_id: me.clone(),
							dep_token: dep_token.clone(),
						},
					});
					missing_deps.push((me.clone(), dep_token.clone()));
				}
			}
		}
		parents.insert(me.clone(), my_parents);

		if !descriptor.replace_path.is_empty() {
			replace_paths.insert(me.clone(), descriptor.replace_path.clone());
		}
	}

	// Cycle detection + deterministic break.
	break_cycles(&ids, &mut parents, &position, &mut diagnostics);

	// Build children (deterministic by playlist position).
	let mut children: HashMap<ModId, Vec<ModId>> = HashMap::new();
	for child in &ids {
		for parent in parents.get(child).cloned().unwrap_or_default() {
			children.entry(parent).or_default().push(child.clone());
		}
	}
	for v in children.values_mut() {
		v.sort_by_key(|c| position.get(c).copied().unwrap_or(usize::MAX));
		v.dedup();
	}

	// Topological sort using Kahn's algorithm with deterministic ordering by
	// playlist position.
	let topo = topo_sort(&ids, &parents);

	let dag = ModDag {
		parents,
		children,
		topo,
		position,
		missing_deps,
		replace_paths,
	};
	(dag, diagnostics)
}

/// Tarjan SCC: find any cycle, then drop the edge whose *child* has the
/// highest playlist position (loaded latest). Repeat until acyclic.
fn break_cycles(
	ids: &[ModId],
	parents: &mut HashMap<ModId, Vec<ModId>>,
	position: &HashMap<ModId, usize>,
	diagnostics: &mut Vec<DagDiagnostic>,
) {
	loop {
		let sccs = tarjan_sccs(ids, parents);
		// A cycle is any SCC of size ≥ 2, or a self-loop (size 1 with edge
		// to itself — already filtered in build_mod_dag, but defensive).
		let cyclic_scc = sccs.into_iter().find(|s| {
			s.len() > 1
				|| s.iter()
					.any(|m| parents.get(m).is_some_and(|ps| ps.contains(m)))
		});
		let scc = match cyclic_scc {
			Some(s) => s,
			None => return,
		};

		diagnostics.push(DagDiagnostic {
			severity: DagDiagnosticSeverity::Warning,
			kind: DagDiagnosticKind::DependencyCycle {
				members: scc.clone(),
			},
		});

		// Find the child with the highest position whose parents contain a
		// member of the SCC. Drop that edge (child → parent).
		let scc_set: HashSet<&ModId> = scc.iter().collect();
		let mut victim: Option<(ModId, ModId)> = None;
		let mut victim_pos: usize = 0;
		for child in &scc {
			if let Some(ps) = parents.get(child) {
				for p in ps {
					if scc_set.contains(p) {
						let pos = position.get(child).copied().unwrap_or(0);
						if victim.is_none() || pos > victim_pos {
							victim = Some((child.clone(), p.clone()));
							victim_pos = pos;
						}
					}
				}
			}
		}

		let (child, parent) = match victim {
			Some(v) => v,
			None => return, // shouldn't happen
		};

		if let Some(ps) = parents.get_mut(&child) {
			ps.retain(|p| p != &parent);
		}
		diagnostics.push(DagDiagnostic {
			severity: DagDiagnosticSeverity::Info,
			kind: DagDiagnosticKind::BrokenCycleEdge { child, parent },
		});
	}
}

/// Tarjan's SCC algorithm. Iteration order over `ids` is deterministic
/// (= playlist position).
fn tarjan_sccs(ids: &[ModId], parents: &HashMap<ModId, Vec<ModId>>) -> Vec<Vec<ModId>> {
	struct State<'a> {
		index_counter: usize,
		stack: Vec<&'a ModId>,
		on_stack: HashSet<&'a ModId>,
		index: HashMap<&'a ModId, usize>,
		lowlink: HashMap<&'a ModId, usize>,
		sccs: Vec<Vec<ModId>>,
	}

	fn strongconnect<'a>(
		v: &'a ModId,
		state: &mut State<'a>,
		parents: &'a HashMap<ModId, Vec<ModId>>,
	) {
		state.index.insert(v, state.index_counter);
		state.lowlink.insert(v, state.index_counter);
		state.index_counter += 1;
		state.stack.push(v);
		state.on_stack.insert(v);

		if let Some(ps) = parents.get(v) {
			for w in ps {
				if !state.index.contains_key(w) {
					strongconnect(w, state, parents);
					let wl = state.lowlink[w];
					let vl = state.lowlink[v];
					state.lowlink.insert(v, vl.min(wl));
				} else if state.on_stack.contains(w) {
					let widx = state.index[w];
					let vl = state.lowlink[v];
					state.lowlink.insert(v, vl.min(widx));
				}
			}
		}

		if state.lowlink[v] == state.index[v] {
			let mut scc: Vec<ModId> = Vec::new();
			while let Some(w) = state.stack.pop() {
				state.on_stack.remove(w);
				scc.push(w.clone());
				if w == v {
					break;
				}
			}
			state.sccs.push(scc);
		}
	}

	let mut state = State {
		index_counter: 0,
		stack: Vec::new(),
		on_stack: HashSet::new(),
		index: HashMap::new(),
		lowlink: HashMap::new(),
		sccs: Vec::new(),
	};

	for v in ids {
		if !state.index.contains_key(v) {
			strongconnect(v, &mut state, parents);
		}
	}
	state.sccs
}

/// Kahn's algorithm with stable ordering = playlist position.
fn topo_sort(ids: &[ModId], parents: &HashMap<ModId, Vec<ModId>>) -> Vec<ModId> {
	// in-degree = number of parents. Nodes with zero parents go first.
	let mut indeg: HashMap<&ModId, usize> = HashMap::new();
	for id in ids {
		indeg.insert(id, parents.get(id).map(|p| p.len()).unwrap_or(0));
	}
	// children index for the iteration.
	let mut child_index: HashMap<&ModId, Vec<&ModId>> = HashMap::new();
	for id in ids {
		if let Some(ps) = parents.get(id) {
			for p in ps {
				child_index.entry(p).or_default().push(id);
			}
		}
	}

	let mut ready: Vec<&ModId> = ids.iter().filter(|id| indeg[id] == 0).collect();
	let mut out: Vec<ModId> = Vec::with_capacity(ids.len());
	while !ready.is_empty() {
		// Stable: pop the lowest playlist position.
		ready.sort_by_key(|id| ids.iter().position(|x| x == *id).unwrap_or(usize::MAX));
		let next = ready.remove(0);
		out.push(next.clone());
		if let Some(cs) = child_index.get(next) {
			for c in cs {
				let e = indeg.get_mut(c).expect("child indeg present");
				*e -= 1;
				if *e == 0 {
					ready.push(*c);
				}
			}
		}
	}
	// If the graph still has cycles (shouldn't after break_cycles), append
	// the leftover in playlist order so callers still get every node.
	if out.len() < ids.len() {
		let placed: HashSet<ModId> = out.iter().cloned().collect();
		for id in ids {
			if !placed.contains(id) {
				out.push(id.clone());
			}
		}
	}
	out
}

// ---------------------------------------------------------------------------
// FileDag (per-file induced subgraph)
// ---------------------------------------------------------------------------

#[derive(Clone, Debug)]
pub struct FileDag {
	pub file_path: GamePathBuf,
	/// Contributing mods in playlist order (after replace_path filtering).
	contributors: Vec<ModId>,
	contributor_set: HashSet<ModId>,
	/// Per-mod parents (lifted ancestor closure restricted to contributors).
	parents: HashMap<ModId, Vec<ModId>>,
	/// Mods whose per-file base is forced empty by their own replace_path.
	replace_path_owners: HashSet<ModId>,
	position: HashMap<ModId, usize>,
}

impl FileDag {
	/// A DAG for `file_path` with no contributors.
	#[cfg(test)]
	pub(crate) fn empty(file_path: GamePathBuf) -> Self {
		Self {
			file_path,
			contributors: Vec::new(),
			contributor_set: HashSet::new(),
			parents: HashMap::new(),
			replace_path_owners: HashSet::new(),
			position: HashMap::new(),
		}
	}

	pub fn file_path(&self) -> &GamePath {
		&self.file_path
	}
	pub fn contributors(&self) -> &[ModId] {
		&self.contributors
	}
	pub fn parents_of(&self, mod_id: &ModId) -> &[ModId] {
		self.parents
			.get(mod_id)
			.map(|v| v.as_slice())
			.unwrap_or(&[])
	}
	pub fn ancestors_of(&self, mod_id: &ModId) -> Vec<ModId> {
		let mut out = Vec::new();
		let mut seen = HashSet::new();
		self.collect_ancestors(mod_id, &mut seen, &mut out);
		out.sort_by_key(|m| self.precedence_of(m));
		out.dedup();
		out
	}
	fn collect_ancestors(&self, mod_id: &ModId, seen: &mut HashSet<ModId>, out: &mut Vec<ModId>) {
		for parent in self.parents_of(mod_id) {
			if seen.insert(parent.clone()) {
				self.collect_ancestors(parent, seen, out);
				out.push(parent.clone());
			}
		}
	}
	pub fn precedence_of(&self, mod_id: &ModId) -> usize {
		self.position.get(mod_id).copied().unwrap_or(usize::MAX)
	}
	pub fn ships(&self, mod_id: &ModId) -> bool {
		self.contributor_set.contains(mod_id)
	}
	pub fn replaces_path(&self, mod_id: &ModId) -> bool {
		self.replace_path_owners.contains(mod_id)
	}
	pub fn has_replace_path_owner(&self) -> bool {
		!self.replace_path_owners.is_empty()
	}
}

pub(crate) fn topo_levels(parents: &BTreeSet<ModId>, file_dag: &FileDag) -> Vec<Vec<ModId>> {
	if parents.is_empty() {
		return Vec::new();
	}

	let parent_set: HashSet<ModId> = parents.iter().cloned().collect();
	let mut indegree: HashMap<ModId, usize> =
		parents.iter().cloned().map(|parent| (parent, 0)).collect();
	let mut children: HashMap<ModId, Vec<ModId>> = HashMap::new();

	for child in parents {
		for ancestor in file_dag.ancestors_of(child) {
			if !parent_set.contains(&ancestor) {
				continue;
			}
			children
				.entry(ancestor.clone())
				.or_default()
				.push(child.clone());
			*indegree
				.get_mut(child)
				.expect("all parent nodes have indegree slots") += 1;
		}
	}

	for children in children.values_mut() {
		children.sort_by_key(|child| file_dag.precedence_of(child));
		children.dedup();
	}

	let mut ready: Vec<ModId> = parents
		.iter()
		.filter(|parent| indegree.get(*parent).copied().unwrap_or(0) == 0)
		.cloned()
		.collect();
	ready.sort_by_key(|parent| file_dag.precedence_of(parent));

	let mut levels = Vec::new();
	let mut placed: HashSet<ModId> = HashSet::new();
	while !ready.is_empty() {
		let level = ready;
		for parent in &level {
			placed.insert(parent.clone());
		}

		let mut next = Vec::new();
		for parent in &level {
			if let Some(children) = children.get(parent) {
				for child in children {
					let child_indegree = indegree
						.get_mut(child)
						.expect("child nodes have indegree slots");
					*child_indegree -= 1;
					if *child_indegree == 0 {
						next.push(child.clone());
					}
				}
			}
		}
		next.sort_by_key(|parent| file_dag.precedence_of(parent));
		next.dedup();
		levels.push(level);
		ready = next;
	}

	if placed.len() < parents.len() {
		let mut leftover: Vec<ModId> = parents
			.iter()
			.filter(|parent| !placed.contains(*parent))
			.cloned()
			.collect();
		leftover.sort_by_key(|parent| file_dag.precedence_of(parent));
		levels.push(leftover);
	}

	levels
}

/// Configuration for `replace_path` semantics. The merge CLI exposes the
/// all-mods override as `--ignore-replace-path`.
#[derive(Clone, Debug, Default)]
pub enum IgnoreReplacePath {
	#[default]
	None,
	Mods(HashSet<ModId>),
	All,
}

impl IgnoreReplacePath {
	fn applies_to(&self, mod_id: &ModId) -> bool {
		match self {
			IgnoreReplacePath::None => false,
			IgnoreReplacePath::All => true,
			IgnoreReplacePath::Mods(ms) => ms.contains(mod_id),
		}
	}
}

/// Build the per-file induced subgraph. `contributors` is the file
/// inventory entry (already sorted by precedence; base-game and synthetic
/// base entries are filtered out by the caller — they are *not* part of
/// the DAG node set).
pub fn induced_file_dag(
	global: &ModDag,
	file_path: &GamePath,
	contributors: &[ResolvedInputContributor],
	ignore: &IgnoreReplacePath,
) -> FileDag {
	induced_file_dag_with_overrides(global, file_path, contributors, ignore, &[])
}

pub fn induced_file_dag_with_overrides(
	global: &ModDag,
	file_path: &GamePath,
	contributors: &[ResolvedInputContributor],
	ignore: &IgnoreReplacePath,
	dep_overrides: &[DepOverride],
) -> FileDag {
	// Initial contributor list (mod ids only — base-game/synthetic dropped).
	let mut active: Vec<(ModId, usize)> = contributors
		.iter()
		.filter(|c| !c.is_base_game && !c.is_synthetic_base)
		.map(|c| (ModId(c.mod_id.clone()), c.precedence))
		.collect();
	active.sort_by_key(|(_, p)| *p);

	// Apply replace_path filtering: for any mod M in `active` that owns a
	// replace_path covering file_path, drop earlier-precedence contributors.
	// Higher-precedence contributors stay (loader semantics).
	let mut replace_path_owners: HashSet<ModId> = HashSet::new();
	let mut drop_before: Option<usize> = None;
	for (mid, prec) in &active {
		if ignore.applies_to(mid) {
			continue;
		}
		if global
			.replace_paths(mid)
			.iter()
			.any(|prefix| file_path.starts_with(prefix))
		{
			replace_path_owners.insert(mid.clone());
			// Drop everything with strictly lower precedence than `prec`
			// from active. Track the highest such cut-off.
			drop_before = Some(drop_before.map_or(*prec, |c| c.max(*prec)));
		}
	}
	if let Some(cutoff) = drop_before {
		active.retain(|(mid, prec)| *prec >= cutoff || replace_path_owners.contains(mid));
	}

	let contributor_set: HashSet<ModId> = active.iter().map(|(m, _)| m.clone()).collect();
	let contributors_ordered: Vec<ModId> = active.iter().map(|(m, _)| m.clone()).collect();
	let mut position: HashMap<ModId, usize> = HashMap::new();
	for (m, precedence) in &active {
		position.insert(m.clone(), *precedence);
	}

	// Lift edges through skipped (non-contributing) ancestors.
	let dep_override_set = DepOverrideSet::new(dep_overrides);
	let mut parents: HashMap<ModId, Vec<ModId>> = HashMap::new();
	for child in &contributors_ordered {
		if replace_path_owners.contains(child) {
			// Replace_path means "fresh start" — no parents.
			parents.insert(child.clone(), Vec::new());
			continue;
		}
		let lifted = lift_ancestor_edges(global, child, &contributor_set, &dep_override_set);
		parents.insert(child.clone(), lifted);
	}

	FileDag {
		file_path: file_path.to_owned(),
		contributors: contributors_ordered,
		contributor_set,
		parents,
		replace_path_owners,
		position,
	}
}

#[derive(Clone, Debug, Default)]
struct DepOverrideSet {
	edges: HashSet<(ModId, ModId)>,
}

impl DepOverrideSet {
	fn new(overrides: &[DepOverride]) -> Self {
		Self {
			edges: overrides
				.iter()
				.map(|item| (ModId(item.mod_id.clone()), ModId(item.dep_id.clone())))
				.collect(),
		}
	}

	fn contains(&self, child: &ModId, parent: &ModId) -> bool {
		self.edges.contains(&(child.clone(), parent.clone()))
	}
}

/// Walk up `child`'s ancestors in the global DAG. For each ancestor that is
/// also a contributor, record it as a (lifted) parent and stop. For
/// non-contributing ancestors, recurse through *their* parents — this
/// implements the transitive ancestor closure restricted to `members`.
fn lift_ancestor_edges(
	global: &ModDag,
	child: &ModId,
	members: &HashSet<ModId>,
	dep_overrides: &DepOverrideSet,
) -> Vec<ModId> {
	let mut out: Vec<ModId> = Vec::new();
	let mut seen: HashSet<ModId> = HashSet::new();
	let mut stack: Vec<(ModId, ModId)> = global
		.parents_of(child)
		.iter()
		.cloned()
		.map(|parent| (child.clone(), parent))
		.collect();
	while let Some((edge_child, parent)) = stack.pop() {
		if dep_overrides.contains(&edge_child, &parent) {
			continue;
		}
		if !seen.insert(parent.clone()) {
			continue;
		}
		if members.contains(&parent) {
			out.push(parent);
		} else {
			for grandparent in global.parents_of(&parent) {
				stack.push((parent.clone(), grandparent.clone()));
			}
		}
	}
	// Deterministic ordering: by topo position in `global`.
	let topo_pos: HashMap<&ModId, usize> = global
		.topo()
		.iter()
		.enumerate()
		.map(|(i, m)| (m, i))
		.collect();
	out.sort_by_key(|m| topo_pos.get(m).copied().unwrap_or(usize::MAX));
	out.dedup();
	out
}

// ---------------------------------------------------------------------------
// Tests
// ---------------------------------------------------------------------------

#[cfg(test)]
mod tests {
	use super::*;
	use crate::playset::PlaysetEntry;
	use crate::playset::descriptor::ModDescriptor;
	use std::path::PathBuf;

	fn mod_with(
		mod_id: &str,
		name: &str,
		dependencies: Vec<&str>,
		replace_path: Vec<&str>,
	) -> ModCandidate {
		let descriptor = ModDescriptor {
			name: name.to_string(),
			dependencies: dependencies.into_iter().map(str::to_string).collect(),
			replace_path: replace_path
				.into_iter()
				.map(|path| GamePathBuf::parse(path).expect("valid game path"))
				.collect(),
			..ModDescriptor::default()
		};
		let entry = PlaysetEntry {
			steam_id: Some(mod_id.to_string()),
			..PlaysetEntry::default()
		};
		ModCandidate {
			entry,
			mod_id: mod_id.to_string(),
			root_path: None,
			descriptor_path: None,
			descriptor: Some(descriptor),
			workshop_identity: None,
			descriptor_error: None,
			files: Vec::new(),
		}
	}

	fn mid(s: &str) -> ModId {
		ModId(s.to_string())
	}

	fn game_path(text: &str) -> &GamePath {
		GamePath::new(text).expect("valid game path")
	}

	fn file_contributor(mod_id: &str, precedence: usize) -> ResolvedInputContributor {
		ResolvedInputContributor {
			mod_id: mod_id.to_string(),
			root_path: PathBuf::from(format!("/mods/{mod_id}")),
			relative_path: crate::model::GamePathBuf::parse("common/foo.txt")
				.expect("valid game path"),
			precedence,
			is_base_game: false,
			is_synthetic_base: false,
			parse_ok_hint: None,
			mod_hash: Some(format!("hash-{mod_id}")),
		}
	}

	// -----------------------------------------------------------------------
	// Design §F.1 cases
	// -----------------------------------------------------------------------

	#[test]
	fn independent_mods_have_no_file_parents() {
		let mods = vec![
			mod_with("a", "A", vec![], vec![]),
			mod_with("b", "B", vec![], vec![]),
			mod_with("c", "C", vec![], vec![]),
		];
		let (dag, diags) = build_mod_dag(&mods);
		assert!(diags.is_empty());
		assert_eq!(dag.parents_of(&mid("a")), &[] as &[ModId]);
		assert_eq!(dag.parents_of(&mid("b")), &[] as &[ModId]);
		assert_eq!(dag.parents_of(&mid("c")), &[] as &[ModId]);

		let contribs = vec![
			file_contributor("a", 1),
			file_contributor("b", 2),
			file_contributor("c", 3),
		];
		let fdag = induced_file_dag(
			&dag,
			game_path("common/foo.txt"),
			&contribs,
			&IgnoreReplacePath::None,
		);
		for m in ["a", "b", "c"] {
			assert!(fdag.parents_of(&mid(m)).is_empty(), "{m}");
			assert!(fdag.ancestors_of(&mid(m)).is_empty(), "{m}");
		}
	}

	#[test]
	fn single_dep() {
		let mods = vec![
			mod_with("a", "A", vec![], vec![]),
			mod_with("b", "B", vec!["A"], vec![]),
		];
		let (dag, diags) = build_mod_dag(&mods);
		assert!(diags.is_empty());
		assert_eq!(dag.parents_of(&mid("b")), &[mid("a")]);
		assert_eq!(dag.children_of(&mid("a")), &[mid("b")]);

		let contribs = vec![file_contributor("a", 1), file_contributor("b", 2)];
		let fdag = induced_file_dag(
			&dag,
			game_path("common/foo.txt"),
			&contribs,
			&IgnoreReplacePath::None,
		);
		assert!(fdag.parents_of(&mid("a")).is_empty());
		assert_eq!(fdag.parents_of(&mid("b")), &[mid("a")]);
		assert_eq!(fdag.ancestors_of(&mid("b")), vec![mid("a")]);
	}

	#[test]
	fn dep_override_drops_file_edge_and_restores_vanilla_base() {
		let mods = vec![
			mod_with("a", "A", vec![], vec![]),
			mod_with("b", "B", vec!["A"], vec![]),
			mod_with("c", "C", vec![], vec![]),
		];
		let (dag, diags) = build_mod_dag(&mods);
		assert!(diags.is_empty());
		assert_eq!(dag.parents_of(&mid("b")), &[mid("a")]);

		let contribs = vec![
			file_contributor("a", 1),
			file_contributor("b", 2),
			file_contributor("c", 3),
		];
		let overrides = vec![DepOverride::new("b", "a")];
		let fdag = induced_file_dag_with_overrides(
			&dag,
			game_path("common/foo.txt"),
			&contribs,
			&IgnoreReplacePath::None,
			&overrides,
		);

		assert_eq!(fdag.parents_of(&mid("b")), &[] as &[ModId]);
		assert!(fdag.ancestors_of(&mid("b")).is_empty());
	}

	#[test]
	fn two_deps_diamond() {
		let mods = vec![
			mod_with("a", "A", vec![], vec![]),
			mod_with("b", "B", vec![], vec![]),
			mod_with("d", "D", vec!["A", "B"], vec![]),
		];
		let (dag, diags) = build_mod_dag(&mods);
		assert!(diags.is_empty());
		// D's parents are A and B (in declaration order).
		assert_eq!(dag.parents_of(&mid("d")), &[mid("a"), mid("b")]);

		let contribs = vec![
			file_contributor("a", 1),
			file_contributor("b", 2),
			file_contributor("d", 3),
		];
		let fdag = induced_file_dag(
			&dag,
			game_path("common/foo.txt"),
			&contribs,
			&IgnoreReplacePath::None,
		);
		assert_eq!(fdag.parents_of(&mid("d")), &[mid("a"), mid("b")]);
		assert_eq!(fdag.ancestors_of(&mid("d")), vec![mid("a"), mid("b")]);
	}

	#[test]
	fn transitive_chain() {
		let mods = vec![
			mod_with("a", "A", vec![], vec![]),
			mod_with("b", "B", vec!["A"], vec![]),
			mod_with("c", "C", vec!["B"], vec![]),
		];
		let (dag, diags) = build_mod_dag(&mods);
		assert!(diags.is_empty());
		// Topo order respects parents-before-children.
		let topo = dag.topo();
		let pos = |m: &str| topo.iter().position(|x| x == &mid(m)).unwrap();
		assert!(pos("a") < pos("b"));
		assert!(pos("b") < pos("c"));

		// Per-file: C's induced parents include only B (direct); A is
		// transitive through B and not a direct parent in the file DAG.
		let contribs = vec![
			file_contributor("a", 1),
			file_contributor("b", 2),
			file_contributor("c", 3),
		];
		let fdag = induced_file_dag(
			&dag,
			game_path("common/foo.txt"),
			&contribs,
			&IgnoreReplacePath::None,
		);
		assert_eq!(fdag.parents_of(&mid("c")), &[mid("b")]);
		assert_eq!(fdag.parents_of(&mid("b")), &[mid("a")]);
		assert_eq!(fdag.parents_of(&mid("a")), &[] as &[ModId]);
	}

	#[test]
	fn cycle_break() {
		let mods = vec![
			mod_with("a", "A", vec!["B"], vec![]),
			mod_with("b", "B", vec!["A"], vec![]),
		];
		let (dag, diags) = build_mod_dag(&mods);
		// Diagnostics should contain a cycle warning + a break-edge info.
		let has_cycle = diags
			.iter()
			.any(|d| matches!(d.kind, DagDiagnosticKind::DependencyCycle { .. }));
		let has_break = diags
			.iter()
			.any(|d| matches!(d.kind, DagDiagnosticKind::BrokenCycleEdge { .. }));
		assert!(has_cycle, "expected cycle diagnostic, got {:?}", diags);
		assert!(
			has_break,
			"expected broken-edge diagnostic, got {:?}",
			diags
		);
		// The higher-position child (b) is the victim → the edge B→A is
		// dropped, leaving A→B intact.
		assert_eq!(dag.parents_of(&mid("a")), &[mid("b")]);
		assert_eq!(dag.parents_of(&mid("b")), &[] as &[ModId]);
	}

	#[test]
	fn dep_not_in_playset() {
		let mods = vec![mod_with("b", "B", vec!["Ghost"], vec![])];
		let (dag, diags) = build_mod_dag(&mods);
		assert!(matches!(
			diags[0].kind,
			DagDiagnosticKind::MissingDependency { .. }
		));
		assert_eq!(dag.parents_of(&mid("b")), &[] as &[ModId]);
		assert_eq!(dag.missing_deps().len(), 1);
	}

	#[test]
	fn dep_does_not_ship_file() {
		// B depends on A; only B ships the file.
		let mods = vec![
			mod_with("a", "A", vec![], vec![]),
			mod_with("b", "B", vec!["A"], vec![]),
		];
		let (dag, _diags) = build_mod_dag(&mods);
		// Only B is in the file inventory.
		let contribs = vec![file_contributor("b", 2)];
		let fdag = induced_file_dag(
			&dag,
			game_path("common/foo.txt"),
			&contribs,
			&IgnoreReplacePath::None,
		);
		// A is not a contributor → B's per-file parents are empty →
		// the shared DAG walker starts B from the root state.
		assert_eq!(fdag.parents_of(&mid("b")), &[] as &[ModId]);
		assert!(fdag.ancestors_of(&mid("b")).is_empty());
	}

	#[test]
	fn replace_path_drops_priors() {
		// C declares replace_path="common"; A and B (earlier precedence)
		// also ship common/foo.txt → they're dropped.
		let mods = vec![
			mod_with("a", "A", vec![], vec![]),
			mod_with("b", "B", vec![], vec![]),
			mod_with("c", "C", vec![], vec!["common"]),
		];
		let (dag, _diags) = build_mod_dag(&mods);
		let contribs = vec![
			file_contributor("a", 1),
			file_contributor("b", 2),
			file_contributor("c", 3),
		];
		let fdag = induced_file_dag(
			&dag,
			game_path("common/foo.txt"),
			&contribs,
			&IgnoreReplacePath::None,
		);
		// Only C remains as a contributor.
		assert_eq!(fdag.contributors(), &[mid("c")]);
		assert!(fdag.replaces_path(&mid("c")));
		assert!(fdag.parents_of(&mid("c")).is_empty());
	}

	#[test]
	fn replace_path_ignored_when_overridden() {
		let mods = vec![
			mod_with("a", "A", vec![], vec![]),
			mod_with("b", "B", vec![], vec![]),
			mod_with("c", "C", vec![], vec!["common"]),
		];
		let (dag, _diags) = build_mod_dag(&mods);
		let contribs = vec![
			file_contributor("a", 1),
			file_contributor("b", 2),
			file_contributor("c", 3),
		];
		// All replace_path overrides → priors stay.
		let fdag = induced_file_dag(
			&dag,
			game_path("common/foo.txt"),
			&contribs,
			&IgnoreReplacePath::All,
		);
		assert_eq!(fdag.contributors(), &[mid("a"), mid("b"), mid("c")]);
		assert!(!fdag.replaces_path(&mid("c")));
	}

	#[test]
	fn name_alternates() {
		// B declares two names; both resolve. (Here only one is present
		// in the playset; the other is a missing-dep diagnostic.)
		let mods = vec![
			mod_with("me_new", "Missions Expanded", vec![], vec![]),
			mod_with(
				"b",
				"B",
				vec!["Missions Expanded", "Missions Expanded (old)"],
				vec![],
			),
		];
		let (dag, diags) = build_mod_dag(&mods);
		assert_eq!(dag.parents_of(&mid("b")), &[mid("me_new")]);
		// The "(old)" alternate is missing → one diagnostic.
		assert_eq!(
			diags
				.iter()
				.filter(|d| matches!(d.kind, DagDiagnosticKind::MissingDependency { .. }))
				.count(),
			1
		);

		// Now both alternates present → both edges, deduped if same target.
		let mods = vec![
			mod_with("me_new", "Missions Expanded", vec![], vec![]),
			mod_with("me_old", "Missions Expanded (old)", vec![], vec![]),
			mod_with(
				"b",
				"B",
				vec!["Missions Expanded", "Missions Expanded (old)"],
				vec![],
			),
		];
		let (dag, _) = build_mod_dag(&mods);
		assert_eq!(dag.parents_of(&mid("b")), &[mid("me_new"), mid("me_old")]);
	}

	#[test]
	fn chain_regression_achievements() {
		// Reproduces the 371-conflict pattern: mod_a (Europa Expanded) ships
		// achievements.txt, mod_b independently ships an effectively-vanilla
		// achievements.txt, and there is no declared dep between them.
		// A linear chain forces mod_b to inherit mod_a and creates 371 phantom
		// removes. The file DAG keeps both contributors independent.
		let mods = vec![
			mod_with("ee", "Europa Expanded", vec![], vec![]),
			mod_with("bx", "Independent Mod B", vec![], vec![]),
		];
		let (dag, diags) = build_mod_dag(&mods);
		assert!(diags.is_empty());
		let contribs = vec![file_contributor("ee", 1), file_contributor("bx", 2)];
		let fdag = induced_file_dag(
			&dag,
			game_path("common/achievements.txt"),
			&contribs,
			&IgnoreReplacePath::None,
		);
		assert!(fdag.parents_of(&mid("ee")).is_empty());
		assert!(fdag.parents_of(&mid("bx")).is_empty());
		assert!(fdag.ancestors_of(&mid("bx")).is_empty());
	}

	#[test]
	fn ancestors_include_transitive_file_parents() {
		let mods = vec![
			mod_with("a", "A", vec![], vec![]),
			mod_with("b", "B", vec!["A"], vec![]),
			mod_with("c", "C", vec!["B"], vec![]),
		];
		let (dag, diags) = build_mod_dag(&mods);
		assert!(diags.is_empty());
		let contribs = vec![
			file_contributor("a", 1),
			file_contributor("b", 2),
			file_contributor("c", 3),
		];
		let fdag = induced_file_dag(
			&dag,
			game_path("common/foo.txt"),
			&contribs,
			&IgnoreReplacePath::None,
		);
		assert_eq!(fdag.ancestors_of(&mid("c")), vec![mid("a"), mid("b")]);
	}

	#[test]
	fn diamond_ancestors_include_shared_ancestor_once() {
		let mods = vec![
			mod_with("a", "A", vec![], vec![]),
			mod_with("b", "B", vec!["A"], vec![]),
			mod_with("c", "C", vec!["A"], vec![]),
			mod_with("d", "D", vec!["B", "C"], vec![]),
		];
		let (dag, diags) = build_mod_dag(&mods);
		assert!(diags.is_empty());
		let contribs = vec![
			file_contributor("a", 1),
			file_contributor("b", 2),
			file_contributor("c", 3),
			file_contributor("d", 4),
		];
		let fdag = induced_file_dag(
			&dag,
			game_path("common/foo.txt"),
			&contribs,
			&IgnoreReplacePath::None,
		);
		assert_eq!(
			fdag.ancestors_of(&mid("d")),
			vec![mid("a"), mid("b"), mid("c")]
		);
	}

	#[test]
	fn file_edges_lift_through_dependency_that_does_not_ship_the_file() {
		let mods = vec![
			mod_with("a", "A", vec![], vec![]),
			mod_with("b", "B", vec!["A"], vec![]),
			mod_with("c", "C", vec!["B"], vec![]),
		];
		let (dag, diags) = build_mod_dag(&mods);
		assert!(diags.is_empty());
		let contribs = vec![file_contributor("a", 1), file_contributor("c", 3)];
		let fdag = induced_file_dag(
			&dag,
			game_path("common/foo.txt"),
			&contribs,
			&IgnoreReplacePath::None,
		);
		assert_eq!(fdag.parents_of(&mid("c")), &[mid("a")]);
		assert_eq!(fdag.ancestors_of(&mid("c")), vec![mid("a")]);
	}

	#[test]
	fn replace_path_parent_becomes_the_file_dag_root() {
		let mods = vec![
			mod_with("a", "A", vec![], vec![]),
			mod_with("b", "B", vec!["A"], vec!["common"]),
			mod_with("c", "C", vec!["B"], vec![]),
		];
		let (dag, diags) = build_mod_dag(&mods);
		assert!(diags.is_empty());
		let contribs = vec![
			file_contributor("a", 1),
			file_contributor("b", 2),
			file_contributor("c", 3),
		];
		let fdag = induced_file_dag(
			&dag,
			game_path("common/foo.txt"),
			&contribs,
			&IgnoreReplacePath::None,
		);
		assert_eq!(fdag.contributors(), &[mid("b"), mid("c")]);
		assert!(fdag.replaces_path(&mid("b")));
		assert!(fdag.parents_of(&mid("b")).is_empty());
		assert_eq!(fdag.parents_of(&mid("c")), &[mid("b")]);
	}

	#[test]
	fn ignore_replace_path_restores_pruned_file_ancestry() {
		let mods = vec![
			mod_with("a", "A", vec![], vec![]),
			mod_with("b", "B", vec!["A"], vec!["common"]),
			mod_with("c", "C", vec!["B"], vec![]),
		];
		let (dag, diags) = build_mod_dag(&mods);
		assert!(diags.is_empty());
		let contribs = vec![
			file_contributor("a", 1),
			file_contributor("b", 2),
			file_contributor("c", 3),
		];
		let fdag = induced_file_dag(
			&dag,
			game_path("common/foo.txt"),
			&contribs,
			&IgnoreReplacePath::All,
		);
		assert_eq!(fdag.contributors(), &[mid("a"), mid("b"), mid("c")]);
		assert!(!fdag.replaces_path(&mid("b")));
		assert_eq!(fdag.ancestors_of(&mid("c")), vec![mid("a"), mid("b")]);
	}

	#[test]
	fn topo_levels_order_a_pure_chain_sequentially() {
		let mods = vec![
			mod_with("a", "A", vec![], vec![]),
			mod_with("b", "B", vec!["A"], vec![]),
			mod_with("c", "C", vec!["B"], vec![]),
		];
		let (dag, diags) = build_mod_dag(&mods);
		assert!(diags.is_empty());
		let contribs = vec![
			file_contributor("a", 1),
			file_contributor("b", 2),
			file_contributor("c", 3),
		];
		let fdag = induced_file_dag(
			&dag,
			game_path("common/foo.txt"),
			&contribs,
			&IgnoreReplacePath::None,
		);
		let parents = BTreeSet::from([mid("a"), mid("b"), mid("c")]);
		assert_eq!(
			topo_levels(&parents, &fdag),
			vec![vec![mid("a")], vec![mid("b")], vec![mid("c")]]
		);
	}

	#[test]
	fn topo_levels_group_a_pure_antichain() {
		let mods = vec![
			mod_with("a", "A", vec![], vec![]),
			mod_with("b", "B", vec![], vec![]),
			mod_with("c", "C", vec![], vec![]),
		];
		let (dag, diags) = build_mod_dag(&mods);
		assert!(diags.is_empty());
		let contribs = vec![
			file_contributor("a", 1),
			file_contributor("b", 2),
			file_contributor("c", 3),
		];
		let fdag = induced_file_dag(
			&dag,
			game_path("common/foo.txt"),
			&contribs,
			&IgnoreReplacePath::None,
		);
		let parents = BTreeSet::from([mid("c"), mid("a"), mid("b")]);
		assert_eq!(
			topo_levels(&parents, &fdag),
			vec![vec![mid("a"), mid("b"), mid("c")]]
		);
	}

	#[test]
	fn topo_levels_diamond_groups_shared_ancestor_then_siblings() {
		let mods = vec![
			mod_with("a", "A", vec![], vec![]),
			mod_with("b", "B", vec!["A"], vec![]),
			mod_with("c", "C", vec!["A"], vec![]),
			mod_with("d", "D", vec!["B", "C"], vec![]),
		];
		let (dag, diags) = build_mod_dag(&mods);
		assert!(diags.is_empty());
		let contribs = vec![
			file_contributor("a", 1),
			file_contributor("b", 2),
			file_contributor("c", 3),
			file_contributor("d", 4),
		];
		let fdag = induced_file_dag(
			&dag,
			game_path("common/foo.txt"),
			&contribs,
			&IgnoreReplacePath::None,
		);
		let parents = BTreeSet::from([mid("a"), mid("b"), mid("c")]);
		assert_eq!(
			topo_levels(&parents, &fdag),
			vec![vec![mid("a")], vec![mid("b"), mid("c")]]
		);
	}

	#[test]
	fn deterministic_ordering_across_runs() {
		// Build a non-trivial DAG twice in identical order; the topo and
		// children lists must match exactly (no HashMap iteration leaking
		// into output).
		let make_mods = || {
			vec![
				mod_with("a", "A", vec![], vec![]),
				mod_with("b", "B", vec!["A"], vec![]),
				mod_with("c", "C", vec!["A"], vec![]),
				mod_with("d", "D", vec!["B", "C"], vec![]),
			]
		};
		let (dag1, _) = build_mod_dag(&make_mods());
		let (dag2, _) = build_mod_dag(&make_mods());
		assert_eq!(dag1.topo(), dag2.topo());
		for m in [mid("a"), mid("b"), mid("c"), mid("d")] {
			assert_eq!(dag1.parents_of(&m), dag2.parents_of(&m));
			assert_eq!(dag1.children_of(&m), dag2.children_of(&m));
		}
		// children_of(A) must be deterministic [B, C] (playlist order).
		assert_eq!(dag1.children_of(&mid("a")), &[mid("b"), mid("c")]);

		// Same FileDag determinism.
		let mods = make_mods();
		let (dag, _) = build_mod_dag(&mods);
		let contribs = vec![
			file_contributor("a", 1),
			file_contributor("b", 2),
			file_contributor("c", 3),
			file_contributor("d", 4),
		];
		let f1 = induced_file_dag(
			&dag,
			game_path("common/foo.txt"),
			&contribs,
			&IgnoreReplacePath::None,
		);
		let f2 = induced_file_dag(
			&dag,
			game_path("common/foo.txt"),
			&contribs,
			&IgnoreReplacePath::None,
		);
		assert_eq!(f1.contributors(), f2.contributors());
		for m in [mid("a"), mid("b"), mid("c"), mid("d")] {
			assert_eq!(f1.parents_of(&m), f2.parents_of(&m));
		}
	}

	/// A mod's `replace_path` drops earlier contributors of every file in the
	/// directory it names and below, compared by whole components, and of
	/// nothing else.
	#[test]
	fn replace_path_owns_the_files_in_and_below_its_directory_only() {
		let mods = vec![
			mod_with("a", "A", vec![], vec![]),
			mod_with("b", "B", vec![], vec!["common/ideas"]),
		];
		let (dag, _) = build_mod_dag(&mods);
		let contribs = vec![file_contributor("a", 1), file_contributor("b", 2)];
		for (file, owned) in [
			("common/ideas/x.txt", true),
			("common/ideas/nested/x.txt", true),
			("common/ideas", true),
			("common/ideas_extra/x.txt", false),
			("common/idea/x.txt", false),
		] {
			let fdag = induced_file_dag(&dag, game_path(file), &contribs, &IgnoreReplacePath::None);
			assert_eq!(fdag.replaces_path(&mid("b")), owned, "{file}");
			assert_eq!(fdag.ships(&mid("a")), !owned, "{file}");
		}
	}
}