panproto-vcs 0.39.0

// Three-way merge is an orchestration over every `SchemaDiff` field
// (vertices, edges, constraints, hyper-edges, required edges, NSIDs,
// variants, orderings, recursion points, usage modes, spans) crossed with
// each conflict category (BothAdded, BothModified, DeleteModify, etc.).
// The resulting case-analysis functions are naturally long because every
// branch is load-bearing; splitting them into per-field helpers would
// fragment closely related code without simplifying any individual branch.
#![allow(clippy::too_many_lines)]

//! Three-way schema merge with optional pushout verification.
//!
//! Given a base schema and two divergent schemas ("ours" and "theirs"),
//! computes a structural merge with conflict detection. The merge is
//! commutative: swapping ours and theirs produces an identical merged
//! schema (with `Side` labels swapped in conflicts).
//!
//! Without conflict resolutions, the merge retains base values for
//! conflicted elements and produces partial migrations. With
//! user-provided [`ConflictResolution`]s for every conflict, the result
//! can be promoted to a verified categorical pushout via
//! [`verify_pushout`]: total morphisms from both sides into the merged
//! schema satisfying the cocone condition.
//!
//! The merge is structural, not textual: it operates on the schema
//! graph (vertices, edges, constraints, hyper-edges, etc.) rather than
//! on serialized text.

use panproto_check::diff::{self, SchemaDiff};
use panproto_gat::{Name, PullbackResult, Theory, TheoryMorphism, pullback};
use panproto_mig::Migration;
use panproto_schema::{Constraint, Edge, Schema, Span, UsageMode, Variant, Vertex};
use rustc_hash::FxHashSet;
use serde::{Deserialize, Serialize};
use smallvec::SmallVec;
use std::collections::HashMap;
use std::sync::Arc;

use crate::auto_mig;

/// Overlap information discovered via pullback computation.
///
/// When both branches modify a schema derived from a common base, the
/// pullback finds the maximal shared substructure: vertices and edges
/// that appear in both ours and theirs because they originate from the
/// same base element. This lets the merge treat independently-added
/// elements with the same ID as shared (same addition) rather than
/// conflicting, when they can be traced to common structure.
#[derive(Clone, Debug, Default)]
pub struct PullbackOverlap {
    /// Vertex IDs that appear in the shared substructure.
    pub shared_vertices: FxHashSet<String>,
    /// Edge pairs `(src, tgt)` that appear in the shared substructure.
    pub shared_edges: FxHashSet<(String, String)>,
}

/// Options controlling merge behavior.
#[derive(Clone, Debug, Default)]
#[allow(clippy::struct_excessive_bools)]
pub struct MergeOptions {
    /// Merge but don't auto-commit; leave result staged.
    pub no_commit: bool,
    /// Fail if the merge cannot be resolved as a fast-forward.
    pub ff_only: bool,
    /// Create a merge commit even for fast-forward merges.
    pub no_ff: bool,
    /// Squash all commits into a single change (no merge commit).
    pub squash: bool,
    /// Custom merge commit message.
    pub message: Option<String>,
}

/// The result of a three-way merge.
#[derive(Clone, Debug)]
pub struct MergeResult {
    /// The merged schema. When conflicts exist, conflicted elements
    /// retain their base values.
    pub merged_schema: Schema,
    /// Any conflicts detected during the merge.
    pub conflicts: Vec<MergeConflict>,
    /// Migration from "ours" schema to the merged schema.
    pub migration_from_ours: Migration,
    /// Migration from "theirs" schema to the merged schema.
    pub migration_from_theirs: Migration,
    /// Pullback-based overlap information, if the pullback computation
    /// succeeded. `None` when the pullback could not be computed (e.g.
    /// degenerate morphisms).
    pub pullback_overlap: Option<PullbackOverlap>,
}

/// A conflict detected during three-way merge.
///
/// Each variant corresponds to a case where the pushout does not exist
/// cleanly because both sides made incompatible changes to the same
/// schema element.
#[derive(Clone, Debug, Serialize, Deserialize)]
#[non_exhaustive]
pub enum MergeConflict {
    // --- Vertices ---
    /// Both branches modified the same vertex's kind differently.
    BothModifiedVertex {
        /// The ID of the vertex both sides modified.
        vertex_id: String,
        /// The kind our branch changed the vertex to.
        ours_kind: String,
        /// The kind their branch changed the vertex to.
        theirs_kind: String,
    },

    /// Both branches added a vertex with the same ID but different kinds.
    BothAddedVertexDifferently {
        /// The ID of the vertex both sides added.
        vertex_id: String,
        /// The kind our branch used.
        ours_kind: String,
        /// The kind their branch used.
        theirs_kind: String,
    },

    /// One branch deleted a vertex that the other modified.
    DeleteModifyVertex {
        /// The ID of the contested vertex.
        vertex_id: String,
        /// Which side performed the deletion.
        deleted_by: Side,
    },

    // --- Edges ---
    /// One branch deleted an edge that the other still has.
    DeleteModifyEdge {
        /// The contested edge.
        edge: Edge,
        /// Which side performed the deletion.
        deleted_by: Side,
    },

    // --- Constraints ---
    /// Both branches modified the same constraint differently.
    BothModifiedConstraint {
        /// The vertex the constraint belongs to.
        vertex_id: String,
        /// The constraint sort.
        sort: String,
        /// The value our branch set.
        ours_value: String,
        /// The value their branch set.
        theirs_value: String,
    },

    /// Both branches added the same constraint sort with different values.
    BothAddedConstraintDifferently {
        /// The vertex the constraint belongs to.
        vertex_id: String,
        /// The constraint sort.
        sort: String,
        /// The value our branch added.
        ours_value: String,
        /// The value their branch added.
        theirs_value: String,
    },

    /// One branch removed a constraint that the other modified.
    DeleteModifyConstraint {
        /// The vertex the constraint belongs to.
        vertex_id: String,
        /// The constraint sort.
        sort: String,
        /// Which side performed the deletion.
        deleted_by: Side,
    },

    // --- Hyper-edges ---
    /// One branch deleted a hyper-edge that the other modified.
    DeleteModifyHyperEdge {
        /// The ID of the contested hyper-edge.
        hyper_edge_id: String,
        /// Which side performed the deletion.
        deleted_by: Side,
    },

    /// Both branches modified the same hyper-edge differently.
    BothModifiedHyperEdge {
        /// The ID of the contested hyper-edge.
        hyper_edge_id: String,
    },

    /// Both branches added a hyper-edge with the same ID but different content.
    BothAddedHyperEdgeDifferently {
        /// The ID of the contested hyper-edge.
        hyper_edge_id: String,
    },

    // --- Variants ---
    /// One branch removed a variant that the other modified.
    DeleteModifyVariant {
        /// The ID of the contested variant.
        variant_id: String,
        /// The parent vertex of the variant.
        parent_vertex: String,
        /// Which side performed the deletion.
        deleted_by: Side,
    },

    /// Both branches modified the same variant's tag differently.
    BothModifiedVariant {
        /// The ID of the contested variant.
        variant_id: String,
        /// The parent vertex of the variant.
        parent_vertex: String,
        /// The tag our branch set (if any).
        ours_tag: Option<String>,
        /// The tag their branch set (if any).
        theirs_tag: Option<String>,
    },

    // --- Orderings ---
    /// Both branches changed the same edge's ordering differently.
    BothModifiedOrdering {
        /// The contested edge.
        edge: Edge,
        /// The position our branch set (if any).
        ours_position: Option<u32>,
        /// The position their branch set (if any).
        theirs_position: Option<u32>,
    },

    // --- Recursion points ---
    /// Both branches modified the same recursion point's target differently.
    BothModifiedRecursionPoint {
        /// The mu binder ID of the recursion point.
        mu_id: String,
        /// The target vertex our branch set.
        ours_target: String,
        /// The target vertex their branch set.
        theirs_target: String,
    },

    /// One branch removed a recursion point that the other modified.
    DeleteModifyRecursionPoint {
        /// The mu binder ID of the recursion point.
        mu_id: String,
        /// Which side performed the deletion.
        deleted_by: Side,
    },

    // --- Usage modes ---
    /// Both branches changed the same edge's usage mode differently.
    BothModifiedUsageMode {
        /// The contested edge.
        edge: Edge,
        /// The mode our branch set.
        ours_mode: UsageMode,
        /// The mode their branch set.
        theirs_mode: UsageMode,
    },

    // --- NSIDs ---
    /// Both branches changed the same vertex's NSID differently.
    BothModifiedNsid {
        /// The ID of the contested vertex.
        vertex_id: String,
        /// The NSID our branch set.
        ours_nsid: String,
        /// The NSID their branch set.
        theirs_nsid: String,
    },

    /// One branch removed an NSID that the other modified.
    DeleteModifyNsid {
        /// The ID of the contested vertex.
        vertex_id: String,
        /// Which side performed the deletion.
        deleted_by: Side,
    },

    // --- Required ---
    /// Both branches changed the same vertex's required edges differently.
    BothModifiedRequired {
        /// The ID of the contested vertex.
        vertex_id: String,
    },

    /// One branch removed required edges that the other modified.
    DeleteModifyRequired {
        /// The ID of the contested vertex.
        vertex_id: String,
        /// Which side performed the deletion.
        deleted_by: Side,
    },

    // --- Nominal ---
    /// Both branches changed the same vertex's nominal flag differently.
    BothModifiedNominal {
        /// The ID of the contested vertex.
        vertex_id: String,
        /// The nominal value our branch set.
        ours_value: bool,
        /// The nominal value their branch set.
        theirs_value: bool,
    },

    // --- Spans ---
    /// Both branches modified the same span differently.
    BothModifiedSpan {
        /// The ID of the contested span.
        span_id: String,
    },

    /// One branch removed a span that the other modified.
    DeleteModifySpan {
        /// The ID of the contested span.
        span_id: String,
        /// Which side performed the deletion.
        deleted_by: Side,
    },

    /// Both branches added a span with the same ID but different content.
    BothAddedSpanDifferently {
        /// The ID of the contested span.
        span_id: String,
    },

    // --- Enrichment maps ---
    /// Both branches modified the same coercion differently.
    BothModifiedCoercion {
        /// The coercion key `(source_kind, target_kind)`.
        key: (String, String),
    },

    /// Both branches added a coercion with the same key but different expressions.
    BothAddedCoercionDifferently {
        /// The coercion key `(source_kind, target_kind)`.
        key: (String, String),
    },

    /// One branch deleted a coercion that the other modified.
    DeleteModifyCoercion {
        /// The coercion key `(source_kind, target_kind)`.
        key: (String, String),
        /// Which side performed the deletion.
        deleted_by: Side,
    },

    /// Both branches modified the same merger differently.
    BothModifiedMerger {
        /// The vertex ID.
        vertex_id: String,
    },

    /// Both branches added a merger with the same key but different expressions.
    BothAddedMergerDifferently {
        /// The vertex ID.
        vertex_id: String,
    },

    /// One branch deleted a merger that the other modified.
    DeleteModifyMerger {
        /// The vertex ID.
        vertex_id: String,
        /// Which side performed the deletion.
        deleted_by: Side,
    },

    /// Both branches modified the same default differently.
    BothModifiedDefault {
        /// The vertex ID.
        vertex_id: String,
    },

    /// Both branches added a default with the same key but different expressions.
    BothAddedDefaultDifferently {
        /// The vertex ID.
        vertex_id: String,
    },

    /// One branch deleted a default that the other modified.
    DeleteModifyDefault {
        /// The vertex ID.
        vertex_id: String,
        /// Which side performed the deletion.
        deleted_by: Side,
    },

    /// Both branches modified the same policy differently.
    BothModifiedPolicy {
        /// The sort name.
        sort_name: String,
    },

    /// Both branches added a policy with the same key but different expressions.
    BothAddedPolicyDifferently {
        /// The sort name.
        sort_name: String,
    },

    /// One branch deleted a policy that the other modified.
    DeleteModifyPolicy {
        /// The sort name.
        sort_name: String,
        /// Which side performed the deletion.
        deleted_by: Side,
    },
}

/// Which side of the merge performed an operation.
#[derive(Clone, Debug, Serialize, Deserialize, PartialEq, Eq)]
pub enum Side {
    /// Our branch.
    Ours,
    /// Their branch.
    Theirs,
}

// ===========================================================================
// Conflict resolution and pushout verification
// ===========================================================================

/// How to resolve a single merge conflict.
#[derive(Clone, Debug, Serialize, Deserialize)]
pub enum ConflictResolution {
    /// Accept the "ours" side's value.
    ChooseOurs,
    /// Accept the "theirs" side's value.
    ChooseTheirs,
}

/// A mapping from each conflict index to a resolution.
///
/// The index corresponds to the position in [`MergeResult::conflicts`].
#[derive(Clone, Debug, Default)]
pub struct ResolutionStrategy {
    /// Resolution for each conflict, keyed by index in `conflicts`.
    pub resolutions: HashMap<usize, ConflictResolution>,
}

/// A merge result where all conflicts have been resolved.
#[derive(Clone, Debug)]
pub struct ResolvedMerge {
    /// The merged schema with all conflicts resolved.
    pub schema: Schema,
    /// Total migration from "ours" into the resolved schema.
    pub migration_from_ours: Migration,
    /// Total migration from "theirs" into the resolved schema.
    pub migration_from_theirs: Migration,
}

/// Error from pushout verification.
#[derive(Debug, thiserror::Error)]
#[non_exhaustive]
pub enum PushoutError {
    /// Not all conflicts were resolved.
    #[error("unresolved conflicts: {count} of {total}")]
    UnresolvedConflicts {
        /// Number of unresolved conflicts.
        count: usize,
        /// Total number of conflicts.
        total: usize,
    },
    /// A migration is not total: a source vertex has no mapping.
    #[error("migration from {side} is not total: vertex `{vertex}` is unmapped")]
    MigrationNotTotal {
        /// Which side.
        side: &'static str,
        /// The unmapped vertex.
        vertex: String,
    },
    /// The cocone condition is violated.
    #[error(
        "cocone violation: base vertex `{vertex}` maps to `{via_ours}` through ours but `{via_theirs}` through theirs"
    )]
    CoconeViolation {
        /// The base vertex.
        vertex: String,
        /// Where it ends up through ours.
        via_ours: String,
        /// Where it ends up through theirs.
        via_theirs: String,
    },
}

/// Apply conflict resolutions to a merge result, producing a fully resolved schema.
///
/// Every conflict must have a resolution in `strategy`; otherwise this returns
/// a [`PushoutError::UnresolvedConflicts`] error.
///
/// # Errors
///
/// Returns [`PushoutError`] if not all conflicts are resolved.
pub fn apply_resolutions(
    base: &Schema,
    ours: &Schema,
    theirs: &Schema,
    merge_result: &MergeResult,
    strategy: &ResolutionStrategy,
) -> Result<ResolvedMerge, PushoutError> {
    let unresolved = merge_result.conflicts.len() - strategy.resolutions.len();
    if unresolved > 0 {
        return Err(PushoutError::UnresolvedConflicts {
            count: unresolved,
            total: merge_result.conflicts.len(),
        });
    }

    // Start from the merge result (which has base values for conflicts)
    // and apply each resolution.
    let mut schema = merge_result.merged_schema.clone();
    for (idx, conflict) in merge_result.conflicts.iter().enumerate() {
        let resolution =
            strategy
                .resolutions
                .get(&idx)
                .ok_or(PushoutError::UnresolvedConflicts {
                    count: 1,
                    total: merge_result.conflicts.len(),
                })?;
        apply_single_resolution(&mut schema, base, ours, theirs, conflict, resolution);
    }

    // Re-derive migrations from the resolved schema.
    let ours_diff = diff::diff(ours, &schema);
    let theirs_diff = diff::diff(theirs, &schema);
    let migration_from_ours = auto_mig::derive_migration(ours, &schema, &ours_diff);
    let migration_from_theirs = auto_mig::derive_migration(theirs, &schema, &theirs_diff);

    Ok(ResolvedMerge {
        schema,
        migration_from_ours,
        migration_from_theirs,
    })
}

/// Apply a single conflict resolution to the schema by copying the
/// chosen side's state for the conflicted element.
fn apply_single_resolution(
    schema: &mut Schema,
    _base: &Schema,
    ours: &Schema,
    theirs: &Schema,
    conflict: &MergeConflict,
    resolution: &ConflictResolution,
) {
    let source = match resolution {
        ConflictResolution::ChooseOurs => ours,
        ConflictResolution::ChooseTheirs => theirs,
    };

    match conflict {
        MergeConflict::BothModifiedVertex { vertex_id, .. }
        | MergeConflict::BothAddedVertexDifferently { vertex_id, .. } => {
            if let Some(v) = source.vertex(vertex_id) {
                schema
                    .vertices
                    .insert(Name::from(vertex_id.as_str()), v.clone());
            }
        }
        MergeConflict::DeleteModifyVertex { vertex_id, .. } => {
            if source.vertex(vertex_id).is_none() {
                schema.vertices.remove(vertex_id.as_str());
            } else if let Some(v) = source.vertex(vertex_id) {
                schema
                    .vertices
                    .insert(Name::from(vertex_id.as_str()), v.clone());
            }
        }
        MergeConflict::DeleteModifyEdge { edge, .. } => {
            if source.edges.contains_key(edge) {
                schema.edges.insert(edge.clone(), edge.kind.clone());
            } else {
                schema.edges.remove(edge);
            }
        }
        MergeConflict::BothModifiedConstraint {
            vertex_id, sort, ..
        }
        | MergeConflict::BothAddedConstraintDifferently {
            vertex_id, sort, ..
        } => {
            // Copy the constraint from the chosen source.
            if let Some(constraints) = source.constraints.get(vertex_id.as_str()) {
                if let Some(c) = constraints
                    .iter()
                    .find(|c| c.sort.as_ref() == sort.as_str())
                {
                    let entry = schema
                        .constraints
                        .entry(Name::from(vertex_id.as_str()))
                        .or_default();
                    entry.retain(|existing| existing.sort.as_ref() != sort.as_str());
                    entry.push(c.clone());
                }
            }
        }
        MergeConflict::DeleteModifyConstraint {
            vertex_id, sort, ..
        } => {
            if source
                .constraints
                .get(vertex_id.as_str())
                .and_then(|cs| cs.iter().find(|c| c.sort.as_ref() == sort.as_str()))
                .is_some()
            {
                // Copy from source (constraint exists on the chosen side).
                if let Some(constraints) = source.constraints.get(vertex_id.as_str()) {
                    if let Some(c) = constraints
                        .iter()
                        .find(|c| c.sort.as_ref() == sort.as_str())
                    {
                        let entry = schema
                            .constraints
                            .entry(Name::from(vertex_id.as_str()))
                            .or_default();
                        entry.retain(|existing| existing.sort.as_ref() != sort.as_str());
                        entry.push(c.clone());
                    }
                }
            } else {
                // Chosen side deleted it.
                if let Some(entry) = schema.constraints.get_mut(vertex_id.as_str()) {
                    entry.retain(|c| c.sort.as_ref() != sort.as_str());
                }
            }
        }
        // Other conflict types: no-op. The merged schema retains its
        // current value. The full set of 22+ conflict variants can be
        // extended as needed; the pushout verification will catch any
        // remaining inconsistencies via migration totality checks.
        _ => {}
    }
}

/// Verify that a resolved merge satisfies the categorical pushout properties.
///
/// Checks:
/// 1. Both migrations are total (every source vertex is mapped).
/// 2. The cocone condition: both paths from base agree in the merged schema.
///
/// # Errors
///
/// Returns [`PushoutError`] describing the first violation found.
pub fn verify_pushout(
    base: &Schema,
    ours: &Schema,
    theirs: &Schema,
    resolved: &ResolvedMerge,
) -> Result<(), PushoutError> {
    // Check totality of migration_from_ours.
    for vertex_id in ours.vertices.keys() {
        if !resolved
            .migration_from_ours
            .vertex_map
            .contains_key(vertex_id)
        {
            return Err(PushoutError::MigrationNotTotal {
                side: "ours",
                vertex: vertex_id.to_string(),
            });
        }
    }

    // Check totality of migration_from_theirs.
    for vertex_id in theirs.vertices.keys() {
        if !resolved
            .migration_from_theirs
            .vertex_map
            .contains_key(vertex_id)
        {
            return Err(PushoutError::MigrationNotTotal {
                side: "theirs",
                vertex: vertex_id.to_string(),
            });
        }
    }

    // Cocone condition: for every vertex in base that survives in both ours
    // and theirs, it must map to the same vertex in the resolved schema.
    for vertex_id in base.vertices.keys() {
        let via_ours = resolved.migration_from_ours.vertex_map.get(vertex_id);
        let via_theirs = resolved.migration_from_theirs.vertex_map.get(vertex_id);

        // Only check if both sides have a mapping (vertex was retained).
        if let (Some(o), Some(t)) = (via_ours, via_theirs) {
            if o != t {
                return Err(PushoutError::CoconeViolation {
                    vertex: vertex_id.to_string(),
                    via_ours: o.to_string(),
                    via_theirs: t.to_string(),
                });
            }
        }
    }

    Ok(())
}

// ===========================================================================
// Pullback overlap discovery
// ===========================================================================

/// Construct a simple GAT theory from a schema's vertices and edges.
///
/// Re-export from `gat_validate` for backward compatibility within this module.
fn schema_to_theory(name: &str, schema: &Schema) -> Theory {
    crate::gat_validate::schema_to_theory(name, schema)
}

/// Build a theory morphism from `base` to `derived` using diff information.
///
/// For vertices: maps each surviving base vertex to its counterpart in
/// derived (identity for unchanged/modified, absent for removed).
/// For edges: maps each surviving base edge's operation to its
/// counterpart in derived.
fn build_morphism_from_diff(
    morph_name: &str,
    base: &Schema,
    base_theory: &Theory,
    derived: &Schema,
    derived_theory: &Theory,
    diff: &SchemaDiff,
) -> TheoryMorphism {
    let removed_verts: FxHashSet<&str> = diff.removed_vertices.iter().map(String::as_str).collect();

    let removed_edges: FxHashSet<&Edge> = diff.removed_edges.iter().collect();

    // Sort map: map surviving base vertices to their derived counterparts.
    let mut sort_map: HashMap<Arc<str>, Arc<str>> = HashMap::new();
    for vid in base.vertices.keys() {
        if !removed_verts.contains(vid.as_str()) && derived.vertices.contains_key(vid) {
            sort_map.insert(Arc::from(vid.as_str()), Arc::from(vid.as_str()));
        }
    }

    // Op map: map surviving base edges to their derived counterparts.
    let mut op_map: HashMap<Arc<str>, Arc<str>> = HashMap::new();
    let base_ops: Vec<(&Edge, usize)> =
        base.edges.keys().enumerate().map(|(i, e)| (e, i)).collect();
    let derived_ops: Vec<(&Edge, usize)> = derived
        .edges
        .keys()
        .enumerate()
        .map(|(i, e)| (e, i))
        .collect();

    for (base_edge, base_idx) in &base_ops {
        if removed_edges.contains(base_edge) {
            continue;
        }
        // Find matching edge in derived.
        for (derived_edge, derived_idx) in &derived_ops {
            if base_edge.src == derived_edge.src
                && base_edge.tgt == derived_edge.tgt
                && base_edge.kind == derived_edge.kind
                && base_edge.name == derived_edge.name
            {
                // Find corresponding op names in theories.
                if let (Some(base_op), Some(derived_op)) = (
                    base_theory.ops.get(*base_idx),
                    derived_theory.ops.get(*derived_idx),
                ) {
                    op_map.insert(Arc::clone(&base_op.name), Arc::clone(&derived_op.name));
                }
                break;
            }
        }
    }

    TheoryMorphism::new(
        morph_name,
        Arc::clone(&base_theory.name),
        Arc::clone(&derived_theory.name),
        sort_map,
        op_map,
    )
}

/// Compute the pullback overlap between ours and theirs schemas relative
/// to a common base.
///
/// Returns `None` if the pullback computation fails for any reason (this
/// is a best-effort enhancement).
fn compute_pullback_overlap(
    base: &Schema,
    ours: &Schema,
    theirs: &Schema,
    diff_ours: &SchemaDiff,
    diff_theirs: &SchemaDiff,
) -> Option<PullbackOverlap> {
    let base_theory = schema_to_theory("base", base);
    let ours_theory = schema_to_theory("ours", ours);
    let theirs_theory = schema_to_theory("theirs", theirs);

    let m1 = build_morphism_from_diff(
        "base_to_ours",
        base,
        &base_theory,
        ours,
        &ours_theory,
        diff_ours,
    );
    let m2 = build_morphism_from_diff(
        "base_to_theirs",
        base,
        &base_theory,
        theirs,
        &theirs_theory,
        diff_theirs,
    );

    let PullbackResult {
        theory: pb_theory,
        proj1,
        proj2,
    } = pullback(&ours_theory, &theirs_theory, &m1, &m2).ok()?;

    let mut shared_vertices = FxHashSet::default();
    for sort in &pb_theory.sorts {
        // The pullback sort projects to a vertex in both ours and theirs.
        // If proj1 and proj2 map to the same name, that vertex is shared.
        let v1 = proj1.sort_map.get(&sort.name);
        let v2 = proj2.sort_map.get(&sort.name);
        if let (Some(v1_name), Some(v2_name)) = (v1, v2) {
            if v1_name == v2_name {
                shared_vertices.insert(v1_name.to_string());
            }
        }
    }

    let mut shared_edges = FxHashSet::default();
    for op in &pb_theory.ops {
        // The operation's input/output sorts in the pullback map to
        // edges in both schemas.
        if let (Some(o1), Some(o2)) = (proj1.op_map.get(&op.name), proj2.op_map.get(&op.name)) {
            // Look up the actual edges from the op names in the original theories.
            let ours_op = ours_theory.find_op(o1);
            let theirs_op = theirs_theory.find_op(o2);
            if let (Some(ours_op), Some(theirs_op)) = (ours_op, theirs_op) {
                if ours_op.output == theirs_op.output {
                    // Find the source sort names.
                    let ours_src = ours_op.inputs.first().map(|(_, s, _)| s);
                    let theirs_src = theirs_op.inputs.first().map(|(_, s, _)| s);
                    if let (Some(os), Some(ts)) = (ours_src, theirs_src) {
                        if os == ts {
                            shared_edges.insert((os.to_string(), ours_op.output.to_string()));
                        }
                    }
                }
            }
        }
    }

    Some(PullbackOverlap {
        shared_vertices,
        shared_edges,
    })
}

// ===========================================================================
// Core pushout merge
// ===========================================================================

/// Perform a three-way merge of schemas via pushout construction.
///
/// # Algorithm
///
/// 1. Compute `diff(base, ours)` and `diff(base, theirs)`.
/// 2. For every schema field, classify each element's fate on each
///    side (unchanged / added / removed / modified).
/// 3. Apply the pushout rule: one-sided changes are accepted;
///    identical changes are deduplicated; incompatible changes are
///    conflicts (base value retained).
/// 4. Rebuild precomputed indices.
/// 5. Derive migrations from ours → merged and theirs → merged.
///
/// The merge is **commutative**: swapping ours and theirs produces an
/// identical `merged_schema` (with `Side` labels swapped in conflicts).
#[must_use]
pub fn three_way_merge(base: &Schema, ours: &Schema, theirs: &Schema) -> MergeResult {
    let diff_ours = diff::diff(base, ours);
    let diff_theirs = diff::diff(base, theirs);
    let mut conflicts = Vec::new();

    // Compute pullback overlap (best-effort; falls back silently on error).
    let pullback_overlap = compute_pullback_overlap(base, ours, theirs, &diff_ours, &diff_theirs);

    let schemas = MergeSchemas { base, ours, theirs };

    // -- Vertices --
    let vertices = merge_vertices(
        &schemas,
        &diff_ours,
        &diff_theirs,
        &mut conflicts,
        pullback_overlap.as_ref(),
    );

    // -- Edges --
    let edges = merge_edges(base, ours, theirs, &diff_ours, &diff_theirs, &mut conflicts);

    // -- Constraints --
    let constraints =
        merge_constraints(base, ours, theirs, &diff_ours, &diff_theirs, &mut conflicts);

    // -- Hyper-edges --
    // Convert String IDs from diff to Name for lookup.
    let ours_added_he: Vec<Name> = diff_ours
        .added_hyper_edges
        .iter()
        .map(|s| Name::from(s.as_str()))
        .collect();
    let ours_removed_he: Vec<Name> = diff_ours
        .removed_hyper_edges
        .iter()
        .map(|s| Name::from(s.as_str()))
        .collect();
    let ours_modified_he: Vec<Name> = diff_ours
        .modified_hyper_edges
        .iter()
        .map(|c| Name::from(c.id.as_str()))
        .collect();
    let theirs_added_he: Vec<Name> = diff_theirs
        .added_hyper_edges
        .iter()
        .map(|s| Name::from(s.as_str()))
        .collect();
    let theirs_removed_he: Vec<Name> = diff_theirs
        .removed_hyper_edges
        .iter()
        .map(|s| Name::from(s.as_str()))
        .collect();
    let theirs_modified_he: Vec<Name> = diff_theirs
        .modified_hyper_edges
        .iter()
        .map(|c| Name::from(c.id.as_str()))
        .collect();
    let hyper_edges = merge_keyed_eq(
        &base.hyper_edges,
        &ours.hyper_edges,
        &theirs.hyper_edges,
        &fxset_name_from_iter(ours_added_he.iter()),
        &fxset_name_from_iter(ours_removed_he.iter()),
        &fxset_name_from_iter(ours_modified_he.iter()),
        &fxset_name_from_iter(theirs_added_he.iter()),
        &fxset_name_from_iter(theirs_removed_he.iter()),
        &fxset_name_from_iter(theirs_modified_he.iter()),
        &mut conflicts,
        |k, case| match case {
            ConflictCase::BothAddedDifferently => MergeConflict::BothAddedHyperEdgeDifferently {
                hyper_edge_id: k.to_string(),
            },
            ConflictCase::BothModifiedDifferently => MergeConflict::BothModifiedHyperEdge {
                hyper_edge_id: k.to_string(),
            },
            ConflictCase::DeleteModify(side) => MergeConflict::DeleteModifyHyperEdge {
                hyper_edge_id: k.to_string(),
                deleted_by: side,
            },
        },
    );

    // -- Required --
    let required = merge_required(base, ours, theirs, &diff_ours, &diff_theirs, &mut conflicts);

    // -- NSIDs --
    let nsids = merge_nsids(base, ours, theirs, &diff_ours, &diff_theirs, &mut conflicts);

    // -- Variants --
    let variants = merge_variants(base, ours, theirs, &diff_ours, &diff_theirs, &mut conflicts);

    // -- Orderings --
    let orderings = merge_orderings(base, ours, theirs, &diff_ours, &diff_theirs, &mut conflicts);

    // -- Recursion points --
    let recursion_points =
        merge_recursion_points(base, ours, theirs, &diff_ours, &diff_theirs, &mut conflicts);

    // -- Usage modes --
    let usage_modes =
        merge_usage_modes(base, ours, theirs, &diff_ours, &diff_theirs, &mut conflicts);

    // -- Spans --
    let spans = merge_spans(base, ours, theirs, &diff_ours, &diff_theirs, &mut conflicts);

    // -- Nominal --
    let nominal = merge_nominal(base, ours, theirs, &diff_ours, &diff_theirs, &mut conflicts);

    // -- Coercions --
    let ours_added_coerc: Vec<(Name, Name)> = diff_ours
        .added_coercions
        .iter()
        .map(|(a, b)| (Name::from(a.as_str()), Name::from(b.as_str())))
        .collect();
    let ours_removed_coerc: Vec<(Name, Name)> = diff_ours
        .removed_coercions
        .iter()
        .map(|(a, b)| (Name::from(a.as_str()), Name::from(b.as_str())))
        .collect();
    let ours_modified_coerc: Vec<(Name, Name)> = diff_ours
        .modified_coercions
        .iter()
        .map(|(a, b)| (Name::from(a.as_str()), Name::from(b.as_str())))
        .collect();
    let theirs_added_coerc: Vec<(Name, Name)> = diff_theirs
        .added_coercions
        .iter()
        .map(|(a, b)| (Name::from(a.as_str()), Name::from(b.as_str())))
        .collect();
    let theirs_removed_coerc: Vec<(Name, Name)> = diff_theirs
        .removed_coercions
        .iter()
        .map(|(a, b)| (Name::from(a.as_str()), Name::from(b.as_str())))
        .collect();
    let theirs_modified_coerc: Vec<(Name, Name)> = diff_theirs
        .modified_coercions
        .iter()
        .map(|(a, b)| (Name::from(a.as_str()), Name::from(b.as_str())))
        .collect();
    let coercions = merge_keyed_eq(
        &base.coercions,
        &ours.coercions,
        &theirs.coercions,
        &ours_added_coerc.iter().collect::<FxHashSet<_>>(),
        &ours_removed_coerc.iter().collect::<FxHashSet<_>>(),
        &ours_modified_coerc.iter().collect::<FxHashSet<_>>(),
        &theirs_added_coerc.iter().collect::<FxHashSet<_>>(),
        &theirs_removed_coerc.iter().collect::<FxHashSet<_>>(),
        &theirs_modified_coerc.iter().collect::<FxHashSet<_>>(),
        &mut conflicts,
        |k, case| match case {
            ConflictCase::BothAddedDifferently => MergeConflict::BothAddedCoercionDifferently {
                key: (k.0.to_string(), k.1.to_string()),
            },
            ConflictCase::BothModifiedDifferently => MergeConflict::BothModifiedCoercion {
                key: (k.0.to_string(), k.1.to_string()),
            },
            ConflictCase::DeleteModify(side) => MergeConflict::DeleteModifyCoercion {
                key: (k.0.to_string(), k.1.to_string()),
                deleted_by: side,
            },
        },
    );

    // -- Mergers --
    let ours_added_merg: Vec<Name> = diff_ours
        .added_mergers
        .iter()
        .map(|s| Name::from(s.as_str()))
        .collect();
    let ours_removed_merg: Vec<Name> = diff_ours
        .removed_mergers
        .iter()
        .map(|s| Name::from(s.as_str()))
        .collect();
    let ours_modified_merg: Vec<Name> = diff_ours
        .modified_mergers
        .iter()
        .map(|s| Name::from(s.as_str()))
        .collect();
    let theirs_added_merg: Vec<Name> = diff_theirs
        .added_mergers
        .iter()
        .map(|s| Name::from(s.as_str()))
        .collect();
    let theirs_removed_merg: Vec<Name> = diff_theirs
        .removed_mergers
        .iter()
        .map(|s| Name::from(s.as_str()))
        .collect();
    let theirs_modified_merg: Vec<Name> = diff_theirs
        .modified_mergers
        .iter()
        .map(|s| Name::from(s.as_str()))
        .collect();
    let mergers = merge_keyed_eq(
        &base.mergers,
        &ours.mergers,
        &theirs.mergers,
        &fxset_name_from_iter(ours_added_merg.iter()),
        &fxset_name_from_iter(ours_removed_merg.iter()),
        &fxset_name_from_iter(ours_modified_merg.iter()),
        &fxset_name_from_iter(theirs_added_merg.iter()),
        &fxset_name_from_iter(theirs_removed_merg.iter()),
        &fxset_name_from_iter(theirs_modified_merg.iter()),
        &mut conflicts,
        |k, case| match case {
            ConflictCase::BothAddedDifferently => MergeConflict::BothAddedMergerDifferently {
                vertex_id: k.to_string(),
            },
            ConflictCase::BothModifiedDifferently => MergeConflict::BothModifiedMerger {
                vertex_id: k.to_string(),
            },
            ConflictCase::DeleteModify(side) => MergeConflict::DeleteModifyMerger {
                vertex_id: k.to_string(),
                deleted_by: side,
            },
        },
    );

    // -- Defaults --
    let ours_added_dflt: Vec<Name> = diff_ours
        .added_defaults
        .iter()
        .map(|s| Name::from(s.as_str()))
        .collect();
    let ours_removed_dflt: Vec<Name> = diff_ours
        .removed_defaults
        .iter()
        .map(|s| Name::from(s.as_str()))
        .collect();
    let ours_modified_dflt: Vec<Name> = diff_ours
        .modified_defaults
        .iter()
        .map(|s| Name::from(s.as_str()))
        .collect();
    let theirs_added_dflt: Vec<Name> = diff_theirs
        .added_defaults
        .iter()
        .map(|s| Name::from(s.as_str()))
        .collect();
    let theirs_removed_dflt: Vec<Name> = diff_theirs
        .removed_defaults
        .iter()
        .map(|s| Name::from(s.as_str()))
        .collect();
    let theirs_modified_dflt: Vec<Name> = diff_theirs
        .modified_defaults
        .iter()
        .map(|s| Name::from(s.as_str()))
        .collect();
    let defaults = merge_keyed_eq(
        &base.defaults,
        &ours.defaults,
        &theirs.defaults,
        &fxset_name_from_iter(ours_added_dflt.iter()),
        &fxset_name_from_iter(ours_removed_dflt.iter()),
        &fxset_name_from_iter(ours_modified_dflt.iter()),
        &fxset_name_from_iter(theirs_added_dflt.iter()),
        &fxset_name_from_iter(theirs_removed_dflt.iter()),
        &fxset_name_from_iter(theirs_modified_dflt.iter()),
        &mut conflicts,
        |k, case| match case {
            ConflictCase::BothAddedDifferently => MergeConflict::BothAddedDefaultDifferently {
                vertex_id: k.to_string(),
            },
            ConflictCase::BothModifiedDifferently => MergeConflict::BothModifiedDefault {
                vertex_id: k.to_string(),
            },
            ConflictCase::DeleteModify(side) => MergeConflict::DeleteModifyDefault {
                vertex_id: k.to_string(),
                deleted_by: side,
            },
        },
    );

    // -- Policies --
    let ours_added_pol: Vec<Name> = diff_ours
        .added_policies
        .iter()
        .map(|s| Name::from(s.as_str()))
        .collect();
    let ours_removed_pol: Vec<Name> = diff_ours
        .removed_policies
        .iter()
        .map(|s| Name::from(s.as_str()))
        .collect();
    let ours_modified_pol: Vec<Name> = diff_ours
        .modified_policies
        .iter()
        .map(|s| Name::from(s.as_str()))
        .collect();
    let theirs_added_pol: Vec<Name> = diff_theirs
        .added_policies
        .iter()
        .map(|s| Name::from(s.as_str()))
        .collect();
    let theirs_removed_pol: Vec<Name> = diff_theirs
        .removed_policies
        .iter()
        .map(|s| Name::from(s.as_str()))
        .collect();
    let theirs_modified_pol: Vec<Name> = diff_theirs
        .modified_policies
        .iter()
        .map(|s| Name::from(s.as_str()))
        .collect();
    let policies = merge_keyed_eq(
        &base.policies,
        &ours.policies,
        &theirs.policies,
        &fxset_name_from_iter(ours_added_pol.iter()),
        &fxset_name_from_iter(ours_removed_pol.iter()),
        &fxset_name_from_iter(ours_modified_pol.iter()),
        &fxset_name_from_iter(theirs_added_pol.iter()),
        &fxset_name_from_iter(theirs_removed_pol.iter()),
        &fxset_name_from_iter(theirs_modified_pol.iter()),
        &mut conflicts,
        |k, case| match case {
            ConflictCase::BothAddedDifferently => MergeConflict::BothAddedPolicyDifferently {
                sort_name: k.to_string(),
            },
            ConflictCase::BothModifiedDifferently => MergeConflict::BothModifiedPolicy {
                sort_name: k.to_string(),
            },
            ConflictCase::DeleteModify(side) => MergeConflict::DeleteModifyPolicy {
                sort_name: k.to_string(),
                deleted_by: side,
            },
        },
    );

    // Rebuild precomputed indices.
    let mut outgoing: HashMap<Name, SmallVec<Edge, 4>> = HashMap::new();
    let mut incoming: HashMap<Name, SmallVec<Edge, 4>> = HashMap::new();
    let mut between: HashMap<(Name, Name), SmallVec<Edge, 2>> = HashMap::new();

    for edge in edges.keys() {
        outgoing
            .entry(edge.src.clone())
            .or_default()
            .push(edge.clone());
        incoming
            .entry(edge.tgt.clone())
            .or_default()
            .push(edge.clone());
        between
            .entry((edge.src.clone(), edge.tgt.clone()))
            .or_default()
            .push(edge.clone());
    }

    let entries = three_way_merge_entries(base, ours, theirs, &vertices);

    let merged_schema = Schema {
        protocol: base.protocol.clone(),
        vertices,
        edges,
        hyper_edges,
        constraints,
        required,
        nsids,
        entries,
        variants,
        orderings,
        recursion_points,
        spans,
        usage_modes,
        nominal,
        outgoing,
        incoming,
        between,
        coercions,
        mergers,
        defaults,
        policies,
    };

    // Derive migrations.
    let diff_ours_to_merged = diff::diff(ours, &merged_schema);
    let diff_theirs_to_merged = diff::diff(theirs, &merged_schema);
    let migration_from_ours =
        auto_mig::derive_migration(ours, &merged_schema, &diff_ours_to_merged);
    let migration_from_theirs =
        auto_mig::derive_migration(theirs, &merged_schema, &diff_theirs_to_merged);

    MergeResult {
        merged_schema,
        conflicts,
        migration_from_ours,
        migration_from_theirs,
        pullback_overlap,
    }
}

/// Three-way merge on the pointed structure of a schema.
///
/// Entries form a subset of the vertex set on each side; the merge is
/// the pushout of `base → ours` and `base → theirs` restricted to the
/// entries subobject. Case analysis for each candidate vertex `E`
/// appearing in at least one side:
///
/// * `E ∈ base`:
///   * present in both ours and theirs → kept (both agreed);
///   * present in only one → the other side removed it → the deletion
///     propagates, so `E` is not in the merge;
///   * present in neither → both sides removed → not in the merge.
/// * `E ∉ base`:
///   * present in ours or theirs → that side added it → kept;
///   * otherwise vacuous.
///
/// After the set is determined, any `E` whose vertex did not survive
/// the vertex merge is dropped (the pointing must land in the merged
/// object). Order is stable: base entries first, then new entries
/// from ours, then new entries unique to theirs.
#[must_use]
pub fn three_way_merge_entries<S: std::hash::BuildHasher>(
    base: &Schema,
    ours: &Schema,
    theirs: &Schema,
    merged_vertices: &std::collections::HashMap<Name, panproto_schema::Vertex, S>,
) -> Vec<Name> {
    let base_set: std::collections::HashSet<&Name> = base.entries.iter().collect();
    let ours_set: std::collections::HashSet<&Name> = ours.entries.iter().collect();
    let theirs_set: std::collections::HashSet<&Name> = theirs.entries.iter().collect();

    let keep = |e: &Name| -> bool {
        if !merged_vertices.contains_key(e) {
            return false;
        }
        let in_base = base_set.contains(e);
        let in_ours = ours_set.contains(e);
        let in_theirs = theirs_set.contains(e);
        if in_base {
            in_ours && in_theirs
        } else {
            in_ours || in_theirs
        }
    };

    let mut out: Vec<Name> = Vec::new();
    let mut seen: std::collections::HashSet<Name> = std::collections::HashSet::new();
    for side in [&base.entries, &ours.entries, &theirs.entries] {
        for e in side {
            if keep(e) && seen.insert(e.clone()) {
                out.push(e.clone());
            }
        }
    }
    out
}

// ===========================================================================
// Generic pushout helper for keyed maps with PartialEq values
// ===========================================================================

enum ConflictCase {
    BothAddedDifferently,
    BothModifiedDifferently,
    DeleteModify(Side),
}

/// Generic pushout merge for `HashMap<K, V>` where values support `PartialEq`.
///
/// Given sets of added/removed/modified keys from each diff, applies the
/// nine-case pushout rule.
#[allow(clippy::too_many_arguments)]
fn merge_keyed_eq<K: Clone + Eq + std::hash::Hash, V: Clone + PartialEq>(
    base: &HashMap<K, V>,
    ours: &HashMap<K, V>,
    theirs: &HashMap<K, V>,
    ours_added: &FxHashSet<&K>,
    ours_removed: &FxHashSet<&K>,
    ours_modified: &FxHashSet<&K>,
    theirs_added: &FxHashSet<&K>,
    theirs_removed: &FxHashSet<&K>,
    theirs_modified: &FxHashSet<&K>,
    conflicts: &mut Vec<MergeConflict>,
    make_conflict: impl Fn(&K, ConflictCase) -> MergeConflict,
) -> HashMap<K, V> {
    let mut result: HashMap<K, V> = HashMap::new();

    // All keys across all three schemas.
    let all_keys: FxHashSet<&K> = base
        .keys()
        .chain(ours.keys())
        .chain(theirs.keys())
        .collect();

    for key in all_keys {
        let in_base = base.contains_key(key);
        let in_ours = ours.contains_key(key);
        let in_theirs = theirs.contains_key(key);

        let ours_fate = element_fate(
            in_base,
            in_ours,
            ours_added.contains(key),
            ours_removed.contains(key),
            ours_modified.contains(key),
        );
        let theirs_fate = element_fate(
            in_base,
            in_theirs,
            theirs_added.contains(key),
            theirs_removed.contains(key),
            theirs_modified.contains(key),
        );

        match (ours_fate, theirs_fate) {
            (Fate::Unchanged, Fate::Unchanged) => {
                if let Some(v) = base.get(key) {
                    result.insert(key.clone(), v.clone());
                }
            }
            (Fate::Unchanged, Fate::Added | Fate::Modified) => {
                if let Some(v) = theirs.get(key) {
                    result.insert(key.clone(), v.clone());
                }
            }
            (Fate::Added | Fate::Modified, Fate::Unchanged) => {
                if let Some(v) = ours.get(key) {
                    result.insert(key.clone(), v.clone());
                }
            }
            (Fate::Unchanged | Fate::Removed, Fate::Removed) | (Fate::Removed, Fate::Unchanged) => {
                // Removed: don't include.
            }
            (Fate::Added, Fate::Added) => {
                // Both added: check if identical.
                let ours_val = ours.get(key);
                let theirs_val = theirs.get(key);
                if ours_val == theirs_val {
                    if let Some(v) = ours_val {
                        result.insert(key.clone(), v.clone());
                    }
                } else {
                    conflicts.push(make_conflict(key, ConflictCase::BothAddedDifferently));
                    // No base value; don't include.
                }
            }
            (Fate::Modified | Fate::Added, Fate::Modified) | (Fate::Modified, Fate::Added) => {
                let ours_val = ours.get(key);
                let theirs_val = theirs.get(key);
                if ours_val == theirs_val {
                    if let Some(v) = ours_val {
                        result.insert(key.clone(), v.clone());
                    }
                } else {
                    conflicts.push(make_conflict(key, ConflictCase::BothModifiedDifferently));
                    if let Some(v) = base.get(key) {
                        result.insert(key.clone(), v.clone());
                    }
                }
            }
            (Fate::Removed, Fate::Modified | Fate::Added) => {
                conflicts.push(make_conflict(key, ConflictCase::DeleteModify(Side::Ours)));
                if let Some(v) = base.get(key) {
                    result.insert(key.clone(), v.clone());
                }
            }
            (Fate::Modified | Fate::Added, Fate::Removed) => {
                conflicts.push(make_conflict(key, ConflictCase::DeleteModify(Side::Theirs)));
                if let Some(v) = base.get(key) {
                    result.insert(key.clone(), v.clone());
                }
            }
        }
    }

    result
}

#[derive(Clone, Copy, PartialEq, Eq)]
enum Fate {
    Unchanged,
    Added,
    Removed,
    Modified,
}

#[allow(clippy::fn_params_excessive_bools)]
const fn element_fate(
    in_base: bool,
    in_schema: bool,
    is_added: bool,
    is_removed: bool,
    is_modified: bool,
) -> Fate {
    if is_added {
        return Fate::Added;
    }
    if is_removed {
        return Fate::Removed;
    }
    if is_modified {
        return Fate::Modified;
    }
    if !in_base && in_schema {
        return Fate::Added;
    }
    if in_base && !in_schema {
        return Fate::Removed;
    }
    Fate::Unchanged
}

fn fxset_name_from_iter<'a, I: Iterator<Item = &'a Name>>(iter: I) -> FxHashSet<&'a Name> {
    iter.collect()
}

// ===========================================================================
// Per-field merge implementations
// ===========================================================================

/// Bundles the three schemas involved in a three-way merge so that
/// per-field merge helpers need fewer parameters.
struct MergeSchemas<'a> {
    base: &'a Schema,
    ours: &'a Schema,
    theirs: &'a Schema,
}

fn merge_vertices(
    schemas: &MergeSchemas<'_>,
    diff_ours: &SchemaDiff,
    diff_theirs: &SchemaDiff,
    conflicts: &mut Vec<MergeConflict>,
    pullback_overlap: Option<&PullbackOverlap>,
) -> HashMap<Name, Vertex> {
    let (base, ours, theirs) = (schemas.base, schemas.ours, schemas.theirs);
    let mut result: HashMap<Name, Vertex> = HashMap::new();

    let ours_added: FxHashSet<&str> = diff_ours
        .added_vertices
        .iter()
        .map(String::as_str)
        .collect();
    let theirs_added: FxHashSet<&str> = diff_theirs
        .added_vertices
        .iter()
        .map(String::as_str)
        .collect();
    let ours_removed: FxHashSet<&str> = diff_ours
        .removed_vertices
        .iter()
        .map(String::as_str)
        .collect();
    let theirs_removed: FxHashSet<&str> = diff_theirs
        .removed_vertices
        .iter()
        .map(String::as_str)
        .collect();
    let ours_kind_changed: FxHashSet<&str> = diff_ours
        .kind_changes
        .iter()
        .map(|kc| kc.vertex_id.as_str())
        .collect();
    let theirs_kind_changed: FxHashSet<&str> = diff_theirs
        .kind_changes
        .iter()
        .map(|kc| kc.vertex_id.as_str())
        .collect();

    // Process base vertices.
    for (vid, base_v) in &base.vertices {
        let o_removed = ours_removed.contains(vid.as_str());
        let t_removed = theirs_removed.contains(vid.as_str());
        let o_modified = ours_kind_changed.contains(vid.as_str());
        let t_modified = theirs_kind_changed.contains(vid.as_str());

        match (o_removed, t_removed, o_modified, t_modified) {
            // Both removed, or one removed while the other unchanged.
            (true, true, _, _) | (true, false, _, false) | (false, true, false, _) => {}
            // Ours removed, theirs modified → conflict.
            (true, false, _, true) => {
                conflicts.push(MergeConflict::DeleteModifyVertex {
                    vertex_id: vid.to_string(),
                    deleted_by: Side::Ours,
                });
                result.insert(vid.clone(), base_v.clone());
            }
            // Theirs removed, ours modified → conflict.
            (false, true, true, _) => {
                conflicts.push(MergeConflict::DeleteModifyVertex {
                    vertex_id: vid.to_string(),
                    deleted_by: Side::Theirs,
                });
                result.insert(vid.clone(), base_v.clone());
            }
            // Both modified.
            (false, false, true, true) => {
                let ours_v = &ours.vertices[vid];
                let theirs_v = &theirs.vertices[vid];
                if ours_v.kind == theirs_v.kind {
                    result.insert(vid.clone(), ours_v.clone());
                } else {
                    conflicts.push(MergeConflict::BothModifiedVertex {
                        vertex_id: vid.to_string(),
                        ours_kind: ours_v.kind.to_string(),
                        theirs_kind: theirs_v.kind.to_string(),
                    });
                    result.insert(vid.clone(), base_v.clone());
                }
            }
            // Only ours modified.
            (false, false, true, false) => {
                result.insert(vid.clone(), ours.vertices[vid].clone());
            }
            // Only theirs modified.
            (false, false, false, true) => {
                result.insert(vid.clone(), theirs.vertices[vid].clone());
            }
            // Neither modified nor removed.
            (false, false, false, false) => {
                result.insert(vid.clone(), base_v.clone());
            }
        }
    }

    // Process vertices added by ours.
    for vid in &diff_ours.added_vertices {
        let vid_name = Name::from(vid.as_str());
        if theirs_added.contains(vid.as_str()) {
            // Both added: check if identical.
            let ours_v = &ours.vertices[vid.as_str()];
            let theirs_v = &theirs.vertices[vid.as_str()];
            if ours_v == theirs_v {
                result.insert(vid_name, ours_v.clone());
            } else {
                // Check pullback: if both sides added a vertex with the
                // same ID and the pullback says it's shared structure,
                // treat as same-addition (take ours) rather than conflict.
                let pullback_shared =
                    pullback_overlap.is_some_and(|po| po.shared_vertices.contains(vid.as_str()));
                if pullback_shared {
                    // Pullback confirms shared origin: deduplicate by
                    // taking ours (arbitrary but deterministic choice).
                    result.insert(vid_name, ours_v.clone());
                } else {
                    conflicts.push(MergeConflict::BothAddedVertexDifferently {
                        vertex_id: vid.clone(),
                        ours_kind: ours_v.kind.to_string(),
                        theirs_kind: theirs_v.kind.to_string(),
                    });
                    // No base value; don't include.
                }
            }
        } else {
            result.insert(vid_name, ours.vertices[vid.as_str()].clone());
        }
    }

    // Process vertices added by theirs only.
    for vid in &diff_theirs.added_vertices {
        if !ours_added.contains(vid.as_str()) {
            let vid_name = Name::from(vid.as_str());
            result.insert(vid_name, theirs.vertices[vid.as_str()].clone());
        }
    }

    result
}

fn merge_edges(
    base: &Schema,
    _ours: &Schema,
    _theirs: &Schema,
    diff_ours: &SchemaDiff,
    diff_theirs: &SchemaDiff,
    conflicts: &mut Vec<MergeConflict>,
) -> HashMap<Edge, Name> {
    let mut result: HashMap<Edge, Name> = HashMap::new();

    let ours_removed: FxHashSet<&Edge> = diff_ours.removed_edges.iter().collect();
    let theirs_removed: FxHashSet<&Edge> = diff_theirs.removed_edges.iter().collect();

    // Build sets of edges that were modified by each side (ordering or usage mode changes).
    let ours_modified_edges: FxHashSet<&Edge> = diff_ours
        .order_changes
        .iter()
        .map(|(e, _, _)| e)
        .chain(diff_ours.usage_mode_changes.iter().map(|(e, _, _)| e))
        .collect();
    let theirs_modified_edges: FxHashSet<&Edge> = diff_theirs
        .order_changes
        .iter()
        .map(|(e, _, _)| e)
        .chain(diff_theirs.usage_mode_changes.iter().map(|(e, _, _)| e))
        .collect();

    // Base edges.
    for (edge, kind) in &base.edges {
        let o_removed = ours_removed.contains(edge);
        let t_removed = theirs_removed.contains(edge);

        match (o_removed, t_removed) {
            (true, true) => {
                // Both removed: accept.
            }
            (true, false) => {
                // Ours removed. If theirs modified metadata, conflict.
                if theirs_modified_edges.contains(edge) {
                    conflicts.push(MergeConflict::DeleteModifyEdge {
                        edge: edge.clone(),
                        deleted_by: Side::Ours,
                    });
                    result.insert(edge.clone(), kind.clone());
                }
                // else: clean removal, accepted
            }
            (false, true) => {
                // Theirs removed. If ours modified metadata, conflict.
                if ours_modified_edges.contains(edge) {
                    conflicts.push(MergeConflict::DeleteModifyEdge {
                        edge: edge.clone(),
                        deleted_by: Side::Theirs,
                    });
                    result.insert(edge.clone(), kind.clone());
                }
                // else: clean removal, accepted
            }
            (false, false) => {
                result.insert(edge.clone(), kind.clone());
            }
        }
    }

    // Edges added by ours.
    for edge in &diff_ours.added_edges {
        result
            .entry(edge.clone())
            .or_insert_with(|| edge.kind.clone());
    }
    // Edges added by theirs.
    for edge in &diff_theirs.added_edges {
        result
            .entry(edge.clone())
            .or_insert_with(|| edge.kind.clone());
    }

    result
}

fn merge_constraints(
    base: &Schema,
    ours: &Schema,
    theirs: &Schema,
    diff_ours: &SchemaDiff,
    diff_theirs: &SchemaDiff,
    conflicts: &mut Vec<MergeConflict>,
) -> HashMap<Name, Vec<Constraint>> {
    let mut result: HashMap<Name, Vec<Constraint>> = HashMap::new();

    let all_vids: FxHashSet<&Name> = base
        .constraints
        .keys()
        .chain(ours.constraints.keys())
        .chain(theirs.constraints.keys())
        .collect();

    for vid in all_vids {
        let base_cs = base.constraints.get(vid).cloned().unwrap_or_default();
        let ours_cs = ours.constraints.get(vid).cloned().unwrap_or_default();
        let theirs_cs = theirs.constraints.get(vid).cloned().unwrap_or_default();

        let vid_str = vid.to_string();
        let ours_cdiff = diff_ours.modified_constraints.get(&vid_str);
        let theirs_cdiff = diff_theirs.modified_constraints.get(&vid_str);

        match (ours_cdiff, theirs_cdiff) {
            (None, None) => {
                // Neither side changed constraints on this vertex.
                if !base_cs.is_empty() {
                    result.insert(vid.clone(), base_cs);
                }
            }
            (Some(_), None) => {
                // Only ours changed: take ours.
                if !ours_cs.is_empty() {
                    result.insert(vid.clone(), ours_cs);
                }
            }
            (None, Some(_)) => {
                // Only theirs changed: take theirs.
                if !theirs_cs.is_empty() {
                    result.insert(vid.clone(), theirs_cs);
                }
            }
            (Some(od), Some(td)) => {
                // Both changed: merge per-sort.
                let merged_cs = merge_constraint_sorts(
                    &vid_str, &base_cs, &ours_cs, &theirs_cs, od, td, conflicts,
                );
                if !merged_cs.is_empty() {
                    result.insert(vid.clone(), merged_cs);
                }
            }
        }
    }

    result
}

/// Merge constraints per-sort when both sides changed constraints on the same vertex.
fn merge_constraint_sorts(
    vid: &str,
    base_cs: &[Constraint],
    ours_cs: &[Constraint],
    theirs_cs: &[Constraint],
    ours_cdiff: &panproto_check::diff::ConstraintDiff,
    theirs_cdiff: &panproto_check::diff::ConstraintDiff,
    conflicts: &mut Vec<MergeConflict>,
) -> Vec<Constraint> {
    let base_by_sort: HashMap<&str, &Constraint> =
        base_cs.iter().map(|c| (c.sort.as_str(), c)).collect();
    let ours_by_sort: HashMap<&str, &Constraint> =
        ours_cs.iter().map(|c| (c.sort.as_str(), c)).collect();
    let theirs_by_sort: HashMap<&str, &Constraint> =
        theirs_cs.iter().map(|c| (c.sort.as_str(), c)).collect();

    // Build change lookups.
    let ours_added_sorts: FxHashSet<&str> =
        ours_cdiff.added.iter().map(|c| c.sort.as_str()).collect();
    let ours_removed_sorts: FxHashSet<&str> =
        ours_cdiff.removed.iter().map(|c| c.sort.as_str()).collect();
    let ours_changed_sorts: FxHashSet<&str> =
        ours_cdiff.changed.iter().map(|c| c.sort.as_str()).collect();
    let theirs_added_sorts: FxHashSet<&str> =
        theirs_cdiff.added.iter().map(|c| c.sort.as_str()).collect();
    let theirs_removed_sorts: FxHashSet<&str> = theirs_cdiff
        .removed
        .iter()
        .map(|c| c.sort.as_str())
        .collect();
    let theirs_changed_sorts: FxHashSet<&str> = theirs_cdiff
        .changed
        .iter()
        .map(|c| c.sort.as_str())
        .collect();

    // Collect all sorts.
    let all_sorts: FxHashSet<&str> = base_by_sort
        .keys()
        .copied()
        .chain(ours_by_sort.keys().copied())
        .chain(theirs_by_sort.keys().copied())
        .collect();

    let mut merged = Vec::new();

    for sort in all_sorts {
        let in_base = base_by_sort.contains_key(sort);
        let o_added = ours_added_sorts.contains(sort);
        let o_removed = ours_removed_sorts.contains(sort);
        let o_changed = ours_changed_sorts.contains(sort);
        let t_added = theirs_added_sorts.contains(sort);
        let t_removed = theirs_removed_sorts.contains(sort);
        let t_changed = theirs_changed_sorts.contains(sort);

        let o_fate = constraint_fate(in_base, o_added, o_removed, o_changed);
        let t_fate = constraint_fate(in_base, t_added, t_removed, t_changed);

        match (o_fate, t_fate) {
            (Fate::Unchanged, Fate::Added | Fate::Modified) => {
                if let Some(c) = theirs_by_sort.get(sort) {
                    merged.push((*c).clone());
                }
            }
            (Fate::Added | Fate::Modified, Fate::Unchanged) => {
                if let Some(c) = ours_by_sort.get(sort) {
                    merged.push((*c).clone());
                }
            }
            (Fate::Unchanged | Fate::Removed, Fate::Removed) | (Fate::Removed, Fate::Unchanged) => {
                // Removed.
            }
            (Fate::Added, Fate::Added) => {
                let ov = ours_by_sort.get(sort);
                let tv = theirs_by_sort.get(sort);
                if ov == tv {
                    if let Some(c) = ov {
                        merged.push((*c).clone());
                    }
                } else {
                    conflicts.push(MergeConflict::BothAddedConstraintDifferently {
                        vertex_id: vid.to_string(),
                        sort: sort.to_string(),
                        ours_value: ov.map(|c| c.value.clone()).unwrap_or_default(),
                        theirs_value: tv.map(|c| c.value.clone()).unwrap_or_default(),
                    });
                }
            }
            (Fate::Modified, Fate::Modified) => {
                let ov = ours_by_sort.get(sort);
                let tv = theirs_by_sort.get(sort);
                if ov == tv {
                    if let Some(c) = ov {
                        merged.push((*c).clone());
                    }
                } else {
                    conflicts.push(MergeConflict::BothModifiedConstraint {
                        vertex_id: vid.to_string(),
                        sort: sort.to_string(),
                        ours_value: ov.map(|c| c.value.clone()).unwrap_or_default(),
                        theirs_value: tv.map(|c| c.value.clone()).unwrap_or_default(),
                    });
                    if let Some(c) = base_by_sort.get(sort) {
                        merged.push((*c).clone());
                    }
                }
            }
            (Fate::Removed, Fate::Modified | Fate::Added) => {
                conflicts.push(MergeConflict::DeleteModifyConstraint {
                    vertex_id: vid.to_string(),
                    sort: sort.to_string(),
                    deleted_by: Side::Ours,
                });
                if let Some(c) = base_by_sort.get(sort) {
                    merged.push((*c).clone());
                }
            }
            (Fate::Modified | Fate::Added, Fate::Removed) => {
                conflicts.push(MergeConflict::DeleteModifyConstraint {
                    vertex_id: vid.to_string(),
                    sort: sort.to_string(),
                    deleted_by: Side::Theirs,
                });
                if let Some(c) = base_by_sort.get(sort) {
                    merged.push((*c).clone());
                }
            }
            // Unchanged on both sides, or impossible combos: retain base.
            _ => {
                if let Some(c) = base_by_sort.get(sort) {
                    merged.push((*c).clone());
                }
            }
        }
    }

    merged.sort();
    merged
}

#[allow(clippy::fn_params_excessive_bools)]
const fn constraint_fate(in_base: bool, added: bool, removed: bool, changed: bool) -> Fate {
    if added {
        return Fate::Added;
    }
    if removed {
        return Fate::Removed;
    }
    if changed {
        return Fate::Modified;
    }
    if !in_base {
        return Fate::Added;
    }
    Fate::Unchanged
}

fn merge_required(
    base: &Schema,
    ours: &Schema,
    theirs: &Schema,
    diff_ours: &SchemaDiff,
    diff_theirs: &SchemaDiff,
    conflicts: &mut Vec<MergeConflict>,
) -> HashMap<Name, Vec<Edge>> {
    let all_vids: FxHashSet<&Name> = base
        .required
        .keys()
        .chain(ours.required.keys())
        .chain(theirs.required.keys())
        .collect();

    let mut result = HashMap::new();

    for vid in all_vids {
        let base_val = base.required.get(vid);
        let ours_val = ours.required.get(vid);
        let theirs_val = theirs.required.get(vid);

        let vid_str = vid.to_string();
        let o_changed = diff_ours.added_required.contains_key(&vid_str)
            || diff_ours.removed_required.contains_key(&vid_str);
        let t_changed = diff_theirs.added_required.contains_key(&vid_str)
            || diff_theirs.removed_required.contains_key(&vid_str);

        let merged_val = match (o_changed, t_changed) {
            (false, false) => base_val.cloned(),
            (true, false) => ours_val.cloned(),
            (false, true) => theirs_val.cloned(),
            (true, true) => {
                if ours_val == theirs_val {
                    ours_val.cloned()
                } else {
                    conflicts.push(MergeConflict::BothModifiedRequired {
                        vertex_id: vid.to_string(),
                    });
                    base_val.cloned()
                }
            }
        };

        if let Some(v) = merged_val {
            if !v.is_empty() {
                result.insert(vid.clone(), v);
            }
        }
    }

    result
}

fn merge_variants(
    base: &Schema,
    ours: &Schema,
    theirs: &Schema,
    diff_ours: &SchemaDiff,
    diff_theirs: &SchemaDiff,
    conflicts: &mut Vec<MergeConflict>,
) -> HashMap<Name, Vec<Variant>> {
    // Flatten to (parent, id) → Variant for each.
    let base_flat = flatten_variants(&base.variants);
    let ours_flat = flatten_variants(&ours.variants);
    let theirs_flat = flatten_variants(&theirs.variants);

    let ours_added: FxHashSet<(&str, &str)> = diff_ours
        .added_variants
        .iter()
        .map(|v| (v.parent_vertex.as_str(), v.id.as_str()))
        .collect();
    let ours_removed: FxHashSet<(&str, &str)> = diff_ours
        .removed_variants
        .iter()
        .map(|v| (v.parent_vertex.as_str(), v.id.as_str()))
        .collect();
    let ours_modified: FxHashSet<(&str, &str)> = diff_ours
        .modified_variants
        .iter()
        .map(|v| (v.parent_vertex.as_str(), v.id.as_str()))
        .collect();
    let theirs_added: FxHashSet<(&str, &str)> = diff_theirs
        .added_variants
        .iter()
        .map(|v| (v.parent_vertex.as_str(), v.id.as_str()))
        .collect();
    let theirs_removed: FxHashSet<(&str, &str)> = diff_theirs
        .removed_variants
        .iter()
        .map(|v| (v.parent_vertex.as_str(), v.id.as_str()))
        .collect();
    let theirs_modified: FxHashSet<(&str, &str)> = diff_theirs
        .modified_variants
        .iter()
        .map(|v| (v.parent_vertex.as_str(), v.id.as_str()))
        .collect();

    let all_keys: FxHashSet<(&str, &str)> = base_flat
        .keys()
        .copied()
        .chain(ours_flat.keys().copied())
        .chain(theirs_flat.keys().copied())
        .collect();

    let mut merged_flat: HashMap<(&str, &str), &Variant> = HashMap::new();

    for key in all_keys {
        let in_base = base_flat.contains_key(&key);
        let o_a = ours_added.contains(&key);
        let o_r = ours_removed.contains(&key);
        let o_m = ours_modified.contains(&key);
        let t_a = theirs_added.contains(&key);
        let t_r = theirs_removed.contains(&key);
        let t_m = theirs_modified.contains(&key);

        let o_fate = element_fate(in_base, ours_flat.contains_key(&key), o_a, o_r, o_m);
        let t_fate = element_fate(in_base, theirs_flat.contains_key(&key), t_a, t_r, t_m);

        match (o_fate, t_fate) {
            (Fate::Unchanged, Fate::Added | Fate::Modified) => {
                if let Some(v) = theirs_flat.get(&key) {
                    merged_flat.insert(key, v);
                }
            }
            (Fate::Added | Fate::Modified, Fate::Unchanged) => {
                if let Some(v) = ours_flat.get(&key) {
                    merged_flat.insert(key, v);
                }
            }
            (Fate::Unchanged | Fate::Removed, Fate::Removed) | (Fate::Removed, Fate::Unchanged) => {
            }
            (Fate::Added, Fate::Added) | (Fate::Modified, Fate::Modified) => {
                let ov = ours_flat.get(&key);
                let tv = theirs_flat.get(&key);
                if ov == tv {
                    if let Some(v) = ov {
                        merged_flat.insert(key, v);
                    }
                } else {
                    conflicts.push(MergeConflict::BothModifiedVariant {
                        variant_id: key.1.to_string(),
                        parent_vertex: key.0.to_string(),
                        ours_tag: ov.and_then(|v| v.tag.as_ref().map(Name::to_string)),
                        theirs_tag: tv.and_then(|v| v.tag.as_ref().map(Name::to_string)),
                    });
                    if let Some(v) = base_flat.get(&key) {
                        merged_flat.insert(key, v);
                    }
                }
            }
            (Fate::Removed, Fate::Modified | Fate::Added) => {
                conflicts.push(MergeConflict::DeleteModifyVariant {
                    variant_id: key.1.to_string(),
                    parent_vertex: key.0.to_string(),
                    deleted_by: Side::Ours,
                });
                if let Some(v) = base_flat.get(&key) {
                    merged_flat.insert(key, v);
                }
            }
            (Fate::Modified | Fate::Added, Fate::Removed) => {
                conflicts.push(MergeConflict::DeleteModifyVariant {
                    variant_id: key.1.to_string(),
                    parent_vertex: key.0.to_string(),
                    deleted_by: Side::Theirs,
                });
                if let Some(v) = base_flat.get(&key) {
                    merged_flat.insert(key, v);
                }
            }
            // Unchanged on both sides, or impossible combos: retain base.
            _ => {
                if let Some(v) = base_flat.get(&key) {
                    merged_flat.insert(key, v);
                }
            }
        }
    }

    // Unflatten.
    let mut result: HashMap<Name, Vec<Variant>> = HashMap::new();
    for ((parent, _), variant) in merged_flat {
        result
            .entry(Name::from(parent))
            .or_default()
            .push((*variant).clone());
    }
    result
}

fn flatten_variants(variants: &HashMap<Name, Vec<Variant>>) -> HashMap<(&str, &str), &Variant> {
    let mut flat: HashMap<(&str, &str), &Variant> = HashMap::new();
    for (parent, vs) in variants {
        for v in vs {
            flat.insert((parent.as_str(), v.id.as_str()), v);
        }
    }
    flat
}

fn merge_orderings(
    base: &Schema,
    ours: &Schema,
    theirs: &Schema,
    diff_ours: &SchemaDiff,
    diff_theirs: &SchemaDiff,
    conflicts: &mut Vec<MergeConflict>,
) -> HashMap<Edge, u32> {
    let ours_changed: FxHashSet<&Edge> =
        diff_ours.order_changes.iter().map(|(e, _, _)| e).collect();
    let theirs_changed: FxHashSet<&Edge> = diff_theirs
        .order_changes
        .iter()
        .map(|(e, _, _)| e)
        .collect();

    let all_edges: FxHashSet<&Edge> = base
        .orderings
        .keys()
        .chain(ours.orderings.keys())
        .chain(theirs.orderings.keys())
        .collect();

    let mut result = HashMap::new();

    for edge in all_edges {
        let o_changed = ours_changed.contains(edge);
        let t_changed = theirs_changed.contains(edge);

        let base_pols = base.orderings.get(edge).copied();
        let ours_pols = ours.orderings.get(edge).copied();
        let theirs_pols = theirs.orderings.get(edge).copied();

        let merged_pols = match (o_changed, t_changed) {
            (false, false) => base_pols,
            (true, false) => ours_pols,
            (false, true) => theirs_pols,
            (true, true) => {
                if ours_pols == theirs_pols {
                    ours_pols
                } else {
                    conflicts.push(MergeConflict::BothModifiedOrdering {
                        edge: edge.clone(),
                        ours_position: ours_pols,
                        theirs_position: theirs_pols,
                    });
                    base_pols
                }
            }
        };

        if let Some(pos) = merged_pols {
            result.insert(edge.clone(), pos);
        }
    }

    result
}

fn merge_recursion_points(
    base: &Schema,
    ours: &Schema,
    theirs: &Schema,
    diff_ours: &SchemaDiff,
    diff_theirs: &SchemaDiff,
    conflicts: &mut Vec<MergeConflict>,
) -> HashMap<Name, panproto_schema::RecursionPoint> {
    let ours_added: FxHashSet<&str> = diff_ours
        .added_recursion_points
        .iter()
        .map(|r| r.mu_id.as_str())
        .collect();
    let ours_removed: FxHashSet<&str> = diff_ours
        .removed_recursion_points
        .iter()
        .map(|r| r.mu_id.as_str())
        .collect();
    let ours_modified: FxHashSet<&str> = diff_ours
        .modified_recursion_points
        .iter()
        .map(|r| r.mu_id.as_str())
        .collect();
    let theirs_added: FxHashSet<&str> = diff_theirs
        .added_recursion_points
        .iter()
        .map(|r| r.mu_id.as_str())
        .collect();
    let theirs_removed: FxHashSet<&str> = diff_theirs
        .removed_recursion_points
        .iter()
        .map(|r| r.mu_id.as_str())
        .collect();
    let theirs_modified: FxHashSet<&str> = diff_theirs
        .modified_recursion_points
        .iter()
        .map(|r| r.mu_id.as_str())
        .collect();

    merge_keyed_eq(
        &base.recursion_points,
        &ours.recursion_points,
        &theirs.recursion_points,
        &ours_added
            .iter()
            .filter_map(|s| ours.recursion_points.get_key_value(*s).map(|(k, _)| k))
            .collect(),
        &ours_removed
            .iter()
            .filter_map(|s| base.recursion_points.get_key_value(*s).map(|(k, _)| k))
            .collect(),
        &ours_modified
            .iter()
            .filter_map(|s| base.recursion_points.get_key_value(*s).map(|(k, _)| k))
            .collect(),
        &theirs_added
            .iter()
            .filter_map(|s| theirs.recursion_points.get_key_value(*s).map(|(k, _)| k))
            .collect(),
        &theirs_removed
            .iter()
            .filter_map(|s| base.recursion_points.get_key_value(*s).map(|(k, _)| k))
            .collect(),
        &theirs_modified
            .iter()
            .filter_map(|s| base.recursion_points.get_key_value(*s).map(|(k, _)| k))
            .collect(),
        conflicts,
        |k, case| match case {
            ConflictCase::BothAddedDifferently | ConflictCase::BothModifiedDifferently => {
                let ours_rp = ours.recursion_points.get(k);
                let theirs_rp = theirs.recursion_points.get(k);
                MergeConflict::BothModifiedRecursionPoint {
                    mu_id: k.to_string(),
                    ours_target: ours_rp
                        .map(|r| r.target_vertex.to_string())
                        .unwrap_or_default(),
                    theirs_target: theirs_rp
                        .map(|r| r.target_vertex.to_string())
                        .unwrap_or_default(),
                }
            }
            ConflictCase::DeleteModify(side) => MergeConflict::DeleteModifyRecursionPoint {
                mu_id: k.to_string(),
                deleted_by: side,
            },
        },
    )
}

fn merge_usage_modes(
    base: &Schema,
    ours: &Schema,
    theirs: &Schema,
    diff_ours: &SchemaDiff,
    diff_theirs: &SchemaDiff,
    conflicts: &mut Vec<MergeConflict>,
) -> HashMap<Edge, UsageMode> {
    let ours_changed: FxHashSet<&Edge> = diff_ours
        .usage_mode_changes
        .iter()
        .map(|(e, _, _)| e)
        .collect();
    let theirs_changed: FxHashSet<&Edge> = diff_theirs
        .usage_mode_changes
        .iter()
        .map(|(e, _, _)| e)
        .collect();

    let all_edges: FxHashSet<&Edge> = base
        .usage_modes
        .keys()
        .chain(ours.usage_modes.keys())
        .chain(theirs.usage_modes.keys())
        .collect();

    let mut result = HashMap::new();

    for edge in all_edges {
        let o_changed = ours_changed.contains(edge);
        let t_changed = theirs_changed.contains(edge);

        let base_mode = base.usage_modes.get(edge).cloned();
        let ours_mode = ours.usage_modes.get(edge).cloned();
        let theirs_mode = theirs.usage_modes.get(edge).cloned();

        let merged_mode = match (o_changed, t_changed) {
            (false, false) => base_mode,
            (true, false) => ours_mode,
            (false, true) => theirs_mode,
            (true, true) => {
                if ours_mode == theirs_mode {
                    ours_mode
                } else {
                    conflicts.push(MergeConflict::BothModifiedUsageMode {
                        edge: edge.clone(),
                        ours_mode: ours_mode.clone().unwrap_or_default(),
                        theirs_mode: theirs_mode.clone().unwrap_or_default(),
                    });
                    base_mode
                }
            }
        };

        if let Some(mode) = merged_mode {
            result.insert(edge.clone(), mode);
        }
    }

    result
}

fn merge_spans(
    base: &Schema,
    ours: &Schema,
    theirs: &Schema,
    diff_ours: &SchemaDiff,
    diff_theirs: &SchemaDiff,
    conflicts: &mut Vec<MergeConflict>,
) -> HashMap<Name, Span> {
    let ours_added_names: Vec<Name> = diff_ours
        .added_spans
        .iter()
        .map(|s| Name::from(s.as_str()))
        .collect();
    let ours_removed_names: Vec<Name> = diff_ours
        .removed_spans
        .iter()
        .map(|s| Name::from(s.as_str()))
        .collect();
    let ours_modified_names: Vec<Name> = diff_ours
        .modified_spans
        .iter()
        .map(|s| Name::from(s.id.as_str()))
        .collect();
    let theirs_added_names: Vec<Name> = diff_theirs
        .added_spans
        .iter()
        .map(|s| Name::from(s.as_str()))
        .collect();
    let theirs_removed_names: Vec<Name> = diff_theirs
        .removed_spans
        .iter()
        .map(|s| Name::from(s.as_str()))
        .collect();
    let theirs_modified_names: Vec<Name> = diff_theirs
        .modified_spans
        .iter()
        .map(|s| Name::from(s.id.as_str()))
        .collect();

    merge_keyed_eq(
        &base.spans,
        &ours.spans,
        &theirs.spans,
        &fxset_name_from_iter(ours_added_names.iter()),
        &fxset_name_from_iter(ours_removed_names.iter()),
        &fxset_name_from_iter(ours_modified_names.iter()),
        &fxset_name_from_iter(theirs_added_names.iter()),
        &fxset_name_from_iter(theirs_removed_names.iter()),
        &fxset_name_from_iter(theirs_modified_names.iter()),
        conflicts,
        |k, case| match case {
            ConflictCase::BothAddedDifferently => MergeConflict::BothAddedSpanDifferently {
                span_id: k.to_string(),
            },
            ConflictCase::BothModifiedDifferently => MergeConflict::BothModifiedSpan {
                span_id: k.to_string(),
            },
            ConflictCase::DeleteModify(side) => MergeConflict::DeleteModifySpan {
                span_id: k.to_string(),
                deleted_by: side,
            },
        },
    )
}

fn merge_nominal(
    base: &Schema,
    ours: &Schema,
    theirs: &Schema,
    diff_ours: &SchemaDiff,
    diff_theirs: &SchemaDiff,
    conflicts: &mut Vec<MergeConflict>,
) -> HashMap<Name, bool> {
    let ours_changed: FxHashSet<&str> = diff_ours
        .nominal_changes
        .iter()
        .map(|(v, _, _)| v.as_str())
        .collect();
    let theirs_changed: FxHashSet<&str> = diff_theirs
        .nominal_changes
        .iter()
        .map(|(v, _, _)| v.as_str())
        .collect();

    let all_vids: FxHashSet<&Name> = base
        .nominal
        .keys()
        .chain(ours.nominal.keys())
        .chain(theirs.nominal.keys())
        .collect();

    let mut result = HashMap::new();

    for vid in all_vids {
        let o_changed = ours_changed.contains(vid.as_str());
        let t_changed = theirs_changed.contains(vid.as_str());

        let base_val = base.nominal.get(vid).copied();
        let ours_val = ours.nominal.get(vid).copied();
        let theirs_val = theirs.nominal.get(vid).copied();

        let merged_val = match (o_changed, t_changed) {
            (false, false) => base_val,
            (true, false) => ours_val,
            (false, true) => theirs_val,
            (true, true) => {
                if ours_val == theirs_val {
                    ours_val
                } else {
                    conflicts.push(MergeConflict::BothModifiedNominal {
                        vertex_id: vid.to_string(),
                        ours_value: ours_val.unwrap_or(false),
                        theirs_value: theirs_val.unwrap_or(false),
                    });
                    base_val
                }
            }
        };

        if let Some(val) = merged_val {
            result.insert(vid.clone(), val);
        }
    }

    result
}

fn merge_nsids(
    base: &Schema,
    ours: &Schema,
    theirs: &Schema,
    diff_ours: &SchemaDiff,
    diff_theirs: &SchemaDiff,
    conflicts: &mut Vec<MergeConflict>,
) -> HashMap<Name, Name> {
    let ours_changed: FxHashSet<&str> = diff_ours
        .changed_nsids
        .iter()
        .map(|(v, _, _)| v.as_str())
        .collect();
    let ours_added: FxHashSet<&str> = diff_ours.added_nsids.keys().map(String::as_str).collect();
    let ours_removed: FxHashSet<&str> =
        diff_ours.removed_nsids.iter().map(String::as_str).collect();
    let theirs_changed: FxHashSet<&str> = diff_theirs
        .changed_nsids
        .iter()
        .map(|(v, _, _)| v.as_str())
        .collect();
    let theirs_added: FxHashSet<&str> =
        diff_theirs.added_nsids.keys().map(String::as_str).collect();
    let theirs_removed: FxHashSet<&str> = diff_theirs
        .removed_nsids
        .iter()
        .map(String::as_str)
        .collect();

    let all_vids: FxHashSet<&Name> = base
        .nsids
        .keys()
        .chain(ours.nsids.keys())
        .chain(theirs.nsids.keys())
        .collect();

    let mut result = HashMap::new();

    for vid in all_vids {
        let in_base = base.nsids.contains_key(vid);
        let vid_s = vid.as_str();
        let o_a = ours_added.contains(vid_s);
        let o_r = ours_removed.contains(vid_s);
        let o_m = ours_changed.contains(vid_s);
        let t_a = theirs_added.contains(vid_s);
        let t_r = theirs_removed.contains(vid_s);
        let t_m = theirs_changed.contains(vid_s);

        let o_fate = if o_a {
            Fate::Added
        } else if o_r {
            Fate::Removed
        } else if o_m {
            Fate::Modified
        } else if !in_base && ours.nsids.contains_key(vid) {
            Fate::Added
        } else if in_base && !ours.nsids.contains_key(vid) {
            Fate::Removed
        } else {
            Fate::Unchanged
        };
        let t_fate = if t_a {
            Fate::Added
        } else if t_r {
            Fate::Removed
        } else if t_m {
            Fate::Modified
        } else if !in_base && theirs.nsids.contains_key(vid) {
            Fate::Added
        } else if in_base && !theirs.nsids.contains_key(vid) {
            Fate::Removed
        } else {
            Fate::Unchanged
        };

        match (o_fate, t_fate) {
            (Fate::Unchanged, Fate::Added | Fate::Modified) => {
                if let Some(v) = theirs.nsids.get(vid) {
                    result.insert(vid.clone(), v.clone());
                }
            }
            (Fate::Added | Fate::Modified, Fate::Unchanged) => {
                if let Some(v) = ours.nsids.get(vid) {
                    result.insert(vid.clone(), v.clone());
                }
            }
            (Fate::Unchanged | Fate::Removed, Fate::Removed) | (Fate::Removed, Fate::Unchanged) => {
            }
            (Fate::Added, Fate::Added) | (Fate::Modified, Fate::Modified) => {
                let ov = ours.nsids.get(vid);
                let tv = theirs.nsids.get(vid);
                if ov == tv {
                    if let Some(v) = ov {
                        result.insert(vid.clone(), v.clone());
                    }
                } else {
                    conflicts.push(MergeConflict::BothModifiedNsid {
                        vertex_id: vid.to_string(),
                        ours_nsid: ov.map(Name::to_string).unwrap_or_default(),
                        theirs_nsid: tv.map(Name::to_string).unwrap_or_default(),
                    });
                    if let Some(v) = base.nsids.get(vid) {
                        result.insert(vid.clone(), v.clone());
                    }
                }
            }
            (Fate::Removed, Fate::Modified | Fate::Added) => {
                conflicts.push(MergeConflict::DeleteModifyNsid {
                    vertex_id: vid.to_string(),
                    deleted_by: Side::Ours,
                });
                if let Some(v) = base.nsids.get(vid) {
                    result.insert(vid.clone(), v.clone());
                }
            }
            (Fate::Modified | Fate::Added, Fate::Removed) => {
                conflicts.push(MergeConflict::DeleteModifyNsid {
                    vertex_id: vid.to_string(),
                    deleted_by: Side::Theirs,
                });
                if let Some(v) = base.nsids.get(vid) {
                    result.insert(vid.clone(), v.clone());
                }
            }
            // Unchanged on both sides, or impossible combos: retain base.
            _ => {
                if let Some(v) = base.nsids.get(vid) {
                    result.insert(vid.clone(), v.clone());
                }
            }
        }
    }

    result
}

/// Integrate two schemas via pushout with automatic overlap discovery.
///
/// Unlike [`three_way_merge`], this is a two-way operation: it finds
/// shared structure between `left` and `right` via
/// [`panproto_mig::discover_overlap`], then computes the categorical
/// pushout via [`panproto_schema::schema_pushout`].
///
/// Returns the integrated schema together with morphisms embedding each
/// input into the result.
///
/// # Errors
///
/// Returns [`crate::VcsError::NotImplemented`] if the underlying pushout fails
/// (e.g., overlap references nonexistent vertices).
pub fn integrate_schemas(
    left: &Schema,
    right: &Schema,
) -> Result<
    (
        Schema,
        panproto_schema::SchemaMorphism,
        panproto_schema::SchemaMorphism,
    ),
    crate::VcsError,
> {
    let overlap = panproto_mig::discover_overlap(left, right);
    panproto_schema::schema_pushout(left, right, &overlap).map_err(|e| {
        crate::VcsError::NotImplemented {
            feature: format!("schema pushout failed: {e}"),
        }
    })
}

// ===========================================================================
// Tests
// ===========================================================================

#[cfg(test)]
mod tests {
    use super::*;
    use panproto_schema::{HyperEdge, Variant};

    fn make_schema(vertices: &[(&str, &str)], edges: &[Edge]) -> Schema {
        let mut vert_map = HashMap::new();
        let mut edge_map = HashMap::new();

        for (id, kind) in vertices {
            vert_map.insert(
                Name::from(*id),
                Vertex {
                    id: Name::from(*id),
                    kind: Name::from(*kind),
                    nsid: None,
                },
            );
        }
        for edge in edges {
            edge_map.insert(edge.clone(), edge.kind.clone());
        }

        Schema {
            protocol: "test".into(),
            vertices: vert_map,
            edges: edge_map,
            hyper_edges: HashMap::new(),
            constraints: HashMap::new(),
            required: HashMap::new(),
            nsids: HashMap::new(),
            entries: Vec::new(),
            variants: HashMap::new(),
            orderings: HashMap::new(),
            recursion_points: HashMap::new(),
            spans: HashMap::new(),
            usage_modes: HashMap::new(),
            nominal: HashMap::new(),
            coercions: HashMap::new(),
            mergers: HashMap::new(),
            defaults: HashMap::new(),
            policies: HashMap::new(),
            outgoing: HashMap::new(),
            incoming: HashMap::new(),
            between: HashMap::new(),
        }
    }

    fn with_ext(base: Schema, f: impl FnOnce(&mut Schema)) -> Schema {
        let mut s = base;
        f(&mut s);
        s
    }

    // =======================================================================
    // A. Pushout property tests
    // =======================================================================

    #[test]
    fn commutativity_no_conflicts() -> Result<(), Box<dyn std::error::Error>> {
        let base = make_schema(&[("a", "object")], &[]);
        let ours = make_schema(&[("a", "object"), ("b", "string")], &[]);
        let theirs = make_schema(&[("a", "object"), ("c", "integer")], &[]);

        let r1 = three_way_merge(&base, &ours, &theirs);
        let r2 = three_way_merge(&base, &theirs, &ours);

        assert_eq!(
            r1.merged_schema.vertices.len(),
            r2.merged_schema.vertices.len()
        );
        for (id, v1) in &r1.merged_schema.vertices {
            let v2 = r2
                .merged_schema
                .vertices
                .get(id)
                .ok_or("vertex missing in swapped merge")?;
            assert_eq!(v1, v2, "vertex {id} differs between merge directions");
        }
        assert!(r1.conflicts.is_empty());
        assert!(r2.conflicts.is_empty());
        Ok(())
    }

    #[test]
    fn commutativity_with_conflicts() {
        let base = make_schema(&[("a", "object")], &[]);
        let ours = make_schema(&[("a", "string")], &[]);
        let theirs = make_schema(&[("a", "integer")], &[]);

        let r1 = three_way_merge(&base, &ours, &theirs);
        let r2 = three_way_merge(&base, &theirs, &ours);

        // Merged schemas must be identical (base value for conflicted element).
        assert_eq!(r1.merged_schema.vertices["a"].kind, "object");
        assert_eq!(r2.merged_schema.vertices["a"].kind, "object");
        assert_eq!(r1.conflicts.len(), r2.conflicts.len());
    }

    #[test]
    fn left_identity() {
        let base = make_schema(&[("a", "object")], &[]);
        let x = make_schema(&[("a", "object"), ("b", "string")], &[]);

        let r = three_way_merge(&base, &base, &x);
        assert!(r.conflicts.is_empty());
        assert_eq!(r.merged_schema.vertices.len(), 2);
        assert!(r.merged_schema.vertices.contains_key("b"));
    }

    #[test]
    fn right_identity() {
        let base = make_schema(&[("a", "object")], &[]);
        let x = make_schema(&[("a", "object"), ("b", "string")], &[]);

        let r = three_way_merge(&base, &x, &base);
        assert!(r.conflicts.is_empty());
        assert_eq!(r.merged_schema.vertices.len(), 2);
        assert!(r.merged_schema.vertices.contains_key("b"));
    }

    #[test]
    fn idempotence() {
        let base = make_schema(&[("a", "object")], &[]);
        let x = make_schema(&[("a", "object"), ("b", "string")], &[]);

        let r = three_way_merge(&base, &x, &x);
        assert!(r.conflicts.is_empty());
        assert_eq!(r.merged_schema.vertices.len(), 2);
    }

    // =======================================================================
    // B. Vertex tests
    // =======================================================================

    #[test]
    fn merge_non_overlapping_additions() {
        let base = make_schema(&[("a", "object")], &[]);
        let ours = make_schema(&[("a", "object"), ("b", "string")], &[]);
        let theirs = make_schema(&[("a", "object"), ("c", "integer")], &[]);

        let result = three_way_merge(&base, &ours, &theirs);
        assert!(result.conflicts.is_empty());
        assert_eq!(result.merged_schema.vertices.len(), 3);
    }

    #[test]
    fn merge_same_addition() {
        let base = make_schema(&[("a", "object")], &[]);
        let ours = make_schema(&[("a", "object"), ("b", "string")], &[]);
        let theirs = make_schema(&[("a", "object"), ("b", "string")], &[]);

        let result = three_way_merge(&base, &ours, &theirs);
        assert!(result.conflicts.is_empty());
        assert_eq!(result.merged_schema.vertices.len(), 2);
    }

    #[test]
    fn merge_both_modify_same_vertex_kind_differently() {
        let base = make_schema(&[("a", "object")], &[]);
        let ours = make_schema(&[("a", "string")], &[]);
        let theirs = make_schema(&[("a", "integer")], &[]);

        let result = three_way_merge(&base, &ours, &theirs);
        assert_eq!(result.conflicts.len(), 1);
        assert!(matches!(
            &result.conflicts[0],
            MergeConflict::BothModifiedVertex { .. }
        ));
        // Base value retained, not ours.
        assert_eq!(result.merged_schema.vertices["a"].kind, "object");
    }

    #[test]
    fn merge_both_modify_same_vertex_kind_same_way() {
        let base = make_schema(&[("a", "object")], &[]);
        let ours = make_schema(&[("a", "string")], &[]);
        let theirs = make_schema(&[("a", "string")], &[]);

        let result = three_way_merge(&base, &ours, &theirs);
        assert!(result.conflicts.is_empty());
        assert_eq!(result.merged_schema.vertices["a"].kind, "string");
    }

    #[test]
    fn merge_both_add_vertex_differently() {
        let base = make_schema(&[("a", "object")], &[]);
        let ours = make_schema(&[("a", "object"), ("b", "string")], &[]);
        let theirs = make_schema(&[("a", "object"), ("b", "integer")], &[]);

        let result = three_way_merge(&base, &ours, &theirs);
        assert_eq!(result.conflicts.len(), 1);
        assert!(matches!(
            &result.conflicts[0],
            MergeConflict::BothAddedVertexDifferently { .. }
        ));
        // Not in merged (no base value).
        assert!(!result.merged_schema.vertices.contains_key("b"));
    }

    // =======================================================================
    // C. Bug regression: false DeleteModifyVertex
    // =======================================================================

    #[test]
    fn regression_one_side_removes_vertex_other_unchanged() {
        let base = make_schema(&[("a", "object"), ("b", "string")], &[]);
        let ours = make_schema(&[("a", "object")], &[]); // removed b
        let theirs = make_schema(&[("a", "object"), ("b", "string")], &[]); // unchanged

        let result = three_way_merge(&base, &ours, &theirs);
        assert!(
            result.conflicts.is_empty(),
            "should be clean removal, got {:?}",
            result.conflicts
        );
        assert!(!result.merged_schema.vertices.contains_key("b"));
    }

    #[test]
    fn regression_one_side_removes_other_modifies() {
        let base = make_schema(&[("a", "object"), ("b", "string")], &[]);
        let ours = make_schema(&[("a", "object")], &[]); // removed b
        let theirs = make_schema(&[("a", "object"), ("b", "integer")], &[]); // changed b's kind

        let result = three_way_merge(&base, &ours, &theirs);
        assert_eq!(result.conflicts.len(), 1);
        assert!(matches!(
            &result.conflicts[0],
            MergeConflict::DeleteModifyVertex {
                deleted_by: Side::Ours,
                ..
            }
        ));
    }

    // =======================================================================
    // D. Constraint tests
    // =======================================================================

    #[test]
    fn merge_constraint_conflict() {
        let mut base = make_schema(&[("x", "string")], &[]);
        base.constraints.insert(
            "x".into(),
            vec![Constraint {
                sort: "maxLength".into(),
                value: "3000".into(),
            }],
        );

        let mut ours = base.clone();
        ours.constraints.insert(
            "x".into(),
            vec![Constraint {
                sort: "maxLength".into(),
                value: "300".into(),
            }],
        );

        let mut theirs = base.clone();
        theirs.constraints.insert(
            "x".into(),
            vec![Constraint {
                sort: "maxLength".into(),
                value: "5000".into(),
            }],
        );

        let result = three_way_merge(&base, &ours, &theirs);
        assert_eq!(result.conflicts.len(), 1);
        assert!(matches!(
            &result.conflicts[0],
            MergeConflict::BothModifiedConstraint { .. }
        ));
        // Base value retained.
        assert_eq!(result.merged_schema.constraints["x"][0].value, "3000");
    }

    // =======================================================================
    // E. Edge tests
    // =======================================================================

    #[test]
    fn merge_edge_additions_from_both() {
        let base = make_schema(&[("a", "object"), ("b", "string")], &[]);
        let edge_ours = Edge {
            src: "a".into(),
            tgt: "b".into(),
            kind: "prop".into(),
            name: Some("x".into()),
        };
        let edge_theirs = Edge {
            src: "a".into(),
            tgt: "b".into(),
            kind: "prop".into(),
            name: Some("y".into()),
        };
        let ours = make_schema(&[("a", "object"), ("b", "string")], &[edge_ours]);
        let theirs = make_schema(&[("a", "object"), ("b", "string")], &[edge_theirs]);

        let result = three_way_merge(&base, &ours, &theirs);
        assert!(result.conflicts.is_empty());
        assert_eq!(result.merged_schema.edges.len(), 2);
    }

    // =======================================================================
    // F. Orderings regression
    // =======================================================================

    #[test]
    fn regression_orderings_theirs_change_not_dropped() {
        let edge = Edge {
            src: "a".into(),
            tgt: "b".into(),
            kind: "prop".into(),
            name: None,
        };
        let base = with_ext(
            make_schema(
                &[("a", "object"), ("b", "string")],
                std::slice::from_ref(&edge),
            ),
            |s| {
                s.orderings.insert(edge.clone(), 0);
            },
        );
        let ours = base.clone(); // unchanged
        let theirs = with_ext(
            make_schema(
                &[("a", "object"), ("b", "string")],
                std::slice::from_ref(&edge),
            ),
            |s| {
                s.orderings.insert(edge.clone(), 1);
            },
        );

        let result = three_way_merge(&base, &ours, &theirs);
        assert!(result.conflicts.is_empty());
        assert_eq!(result.merged_schema.orderings[&edge], 1);
    }

    // =======================================================================
    // G. Hyper-edge tests
    // =======================================================================

    #[test]
    fn merge_hyper_edge_one_side_removes() {
        let he = HyperEdge {
            id: "he1".into(),
            kind: "join".into(),
            signature: HashMap::new(),
            parent_label: "left".into(),
        };
        let base = with_ext(make_schema(&[("a", "object")], &[]), |s| {
            s.hyper_edges.insert("he1".into(), he.clone());
        });
        let ours = make_schema(&[("a", "object")], &[]); // removed he1
        let theirs = base.clone(); // unchanged

        let result = three_way_merge(&base, &ours, &theirs);
        assert!(result.conflicts.is_empty());
        assert!(!result.merged_schema.hyper_edges.contains_key("he1"));
    }

    // =======================================================================
    // H. Span tests
    // =======================================================================

    #[test]
    fn regression_spans_preserved_when_unchanged() {
        let base = with_ext(make_schema(&[("a", "object"), ("b", "string")], &[]), |s| {
            s.spans.insert(
                "s1".into(),
                Span {
                    id: "s1".into(),
                    left: "a".into(),
                    right: "b".into(),
                },
            );
        });
        let ours = base.clone();
        let theirs = base.clone();

        let result = three_way_merge(&base, &ours, &theirs);
        assert!(result.conflicts.is_empty());
        assert!(result.merged_schema.spans.contains_key("s1"));
    }

    // =======================================================================
    // I. Nominal tests
    // =======================================================================

    #[test]
    fn regression_nominal_change_propagated() {
        let base = with_ext(make_schema(&[("a", "object")], &[]), |s| {
            s.nominal.insert("a".into(), false);
        });
        let ours = with_ext(make_schema(&[("a", "object")], &[]), |s| {
            s.nominal.insert("a".into(), true);
        });
        let theirs = base.clone();

        let result = three_way_merge(&base, &ours, &theirs);
        assert!(result.conflicts.is_empty());
        assert_eq!(result.merged_schema.nominal.get("a"), Some(&true));
    }

    // =======================================================================
    // J. Usage mode tests
    // =======================================================================

    #[test]
    fn merge_usage_mode_one_side_changes() {
        let edge = Edge {
            src: "a".into(),
            tgt: "b".into(),
            kind: "prop".into(),
            name: None,
        };
        let base = with_ext(
            make_schema(
                &[("a", "object"), ("b", "string")],
                std::slice::from_ref(&edge),
            ),
            |s| {
                s.usage_modes.insert(edge.clone(), UsageMode::Structural);
            },
        );
        let ours = base.clone();
        let theirs = with_ext(
            make_schema(
                &[("a", "object"), ("b", "string")],
                std::slice::from_ref(&edge),
            ),
            |s| {
                s.usage_modes.insert(edge.clone(), UsageMode::Linear);
            },
        );

        let result = three_way_merge(&base, &ours, &theirs);
        assert!(result.conflicts.is_empty());
        assert_eq!(result.merged_schema.usage_modes[&edge], UsageMode::Linear);
    }

    #[test]
    fn merge_usage_mode_both_change_differently() {
        let edge = Edge {
            src: "a".into(),
            tgt: "b".into(),
            kind: "prop".into(),
            name: None,
        };
        let base = with_ext(
            make_schema(
                &[("a", "object"), ("b", "string")],
                std::slice::from_ref(&edge),
            ),
            |s| {
                s.usage_modes.insert(edge.clone(), UsageMode::Structural);
            },
        );
        let ours = with_ext(
            make_schema(
                &[("a", "object"), ("b", "string")],
                std::slice::from_ref(&edge),
            ),
            |s| {
                s.usage_modes.insert(edge.clone(), UsageMode::Linear);
            },
        );
        let theirs = with_ext(
            make_schema(
                &[("a", "object"), ("b", "string")],
                std::slice::from_ref(&edge),
            ),
            |s| {
                s.usage_modes.insert(edge.clone(), UsageMode::Affine);
            },
        );

        let result = three_way_merge(&base, &ours, &theirs);
        assert_eq!(result.conflicts.len(), 1);
        assert!(matches!(
            &result.conflicts[0],
            MergeConflict::BothModifiedUsageMode { .. }
        ));
        // Base retained.
        assert_eq!(
            result.merged_schema.usage_modes[&edge],
            UsageMode::Structural
        );
    }

    // =======================================================================
    // K. Variant tests
    // =======================================================================

    #[test]
    fn merge_variant_one_side_removes() {
        let base = with_ext(make_schema(&[("u", "union")], &[]), |s| {
            s.variants.insert(
                "u".into(),
                vec![Variant {
                    id: "v1".into(),
                    parent_vertex: "u".into(),
                    tag: Some("a".into()),
                }],
            );
        });
        let ours = make_schema(&[("u", "union")], &[]); // removed variant
        let theirs = base.clone();

        let result = three_way_merge(&base, &ours, &theirs);
        assert!(result.conflicts.is_empty());
        let merged_variants = result.merged_schema.variants.get("u");
        assert!(merged_variants.is_none_or(Vec::is_empty));
    }

    // =======================================================================
    // L. Migration validity test
    // =======================================================================

    #[test]
    fn migration_maps_surviving_vertices() {
        let base = make_schema(&[("a", "object")], &[]);
        let ours = make_schema(&[("a", "object"), ("b", "string")], &[]);
        let theirs = make_schema(&[("a", "object"), ("c", "integer")], &[]);

        let result = three_way_merge(&base, &ours, &theirs);
        // migration_from_ours should map ours' vertices to merged vertices.
        for vid in ours.vertices.keys() {
            if result.merged_schema.vertices.contains_key(vid) {
                assert!(
                    result.migration_from_ours.vertex_map.contains_key(vid),
                    "vertex {vid} in ours and merged but not in migration_from_ours"
                );
            }
        }
        for vid in theirs.vertices.keys() {
            if result.merged_schema.vertices.contains_key(vid) {
                assert!(
                    result.migration_from_theirs.vertex_map.contains_key(vid),
                    "vertex {vid} in theirs and merged but not in migration_from_theirs"
                );
            }
        }
    }

    // =======================================================================
    // Pullback overlap tests
    // =======================================================================

    #[test]
    fn pullback_overlap_shared_vertices_from_base() {
        // Base has a vertex "a". Both sides keep "a" and add "b" with
        // different kinds. The pullback should recognize "a" as shared.
        let base = make_schema(&[("a", "object")], &[]);
        let ours = make_schema(&[("a", "object"), ("b", "string")], &[]);
        let theirs = make_schema(&[("a", "object"), ("b", "integer")], &[]);

        let diff_ours = diff::diff(&base, &ours);
        let diff_theirs = diff::diff(&base, &theirs);

        let overlap = compute_pullback_overlap(&base, &ours, &theirs, &diff_ours, &diff_theirs);
        let Some(overlap) = overlap else {
            panic!("pullback overlap should succeed");
        };

        // "a" is a surviving base vertex, so it should be shared.
        assert!(
            overlap.shared_vertices.contains("a"),
            "base vertex 'a' should be shared"
        );
    }

    #[test]
    fn pullback_overlap_empty_when_no_common_base() {
        // Empty base: both sides add entirely new vertices.
        let base = make_schema(&[], &[]);
        let ours = make_schema(&[("x", "string")], &[]);
        let theirs = make_schema(&[("y", "integer")], &[]);

        let diff_ours = diff::diff(&base, &ours);
        let diff_theirs = diff::diff(&base, &theirs);

        let overlap = compute_pullback_overlap(&base, &ours, &theirs, &diff_ours, &diff_theirs);
        let Some(overlap) = overlap else {
            panic!("pullback overlap should succeed");
        };

        assert!(
            overlap.shared_vertices.is_empty(),
            "no shared vertices when base is empty"
        );
        assert!(
            overlap.shared_edges.is_empty(),
            "no shared edges when base is empty"
        );
    }

    #[test]
    fn pullback_overlap_with_shared_edges() {
        let edge_ab = Edge {
            src: Name::from("a"),
            tgt: Name::from("b"),
            kind: Name::from("prop"),
            name: Some(Name::from("link")),
        };
        let base = make_schema(
            &[("a", "object"), ("b", "string")],
            std::slice::from_ref(&edge_ab),
        );
        // Both sides keep the base edge.
        let ours = make_schema(
            &[("a", "object"), ("b", "string")],
            std::slice::from_ref(&edge_ab),
        );
        let theirs = make_schema(
            &[("a", "object"), ("b", "string")],
            std::slice::from_ref(&edge_ab),
        );

        let diff_ours = diff::diff(&base, &ours);
        let diff_theirs = diff::diff(&base, &theirs);

        let overlap = compute_pullback_overlap(&base, &ours, &theirs, &diff_ours, &diff_theirs);
        let Some(overlap) = overlap else {
            panic!("pullback overlap should succeed");
        };

        assert!(overlap.shared_vertices.contains("a"));
        assert!(overlap.shared_vertices.contains("b"));
        assert!(
            overlap
                .shared_edges
                .contains(&("a".to_string(), "b".to_string())),
            "shared edge (a, b) should be in overlap"
        );
    }

    #[test]
    fn pullback_refines_both_added_vertex_same_id() {
        // Base has "a" and "b". Both sides add "c" with different kinds.
        // Normally this is a conflict. But if both sides also share
        // base vertex "a", the pullback captures that shared structure.
        // However, "c" is not in the pullback (it's new to both sides),
        // so it should still conflict.
        let base = make_schema(&[("a", "object")], &[]);
        let ours = make_schema(&[("a", "object"), ("c", "string")], &[]);
        let theirs = make_schema(&[("a", "object"), ("c", "integer")], &[]);

        let result = three_way_merge(&base, &ours, &theirs);

        // "c" is independently added with different kinds and is NOT in
        // the pullback shared vertices, so it should conflict.
        assert_eq!(result.conflicts.len(), 1);
        assert!(matches!(
            &result.conflicts[0],
            MergeConflict::BothAddedVertexDifferently { vertex_id, .. } if vertex_id == "c"
        ));

        // But the pullback overlap should still have "a" as shared.
        let Some(ref overlap) = result.pullback_overlap else {
            panic!("pullback overlap should be present");
        };
        assert!(
            overlap.shared_vertices.contains("a"),
            "base vertex 'a' should be shared"
        );
    }

    #[test]
    fn pullback_overlap_present_in_clean_merge() {
        // A clean merge should still have pullback overlap info.
        let base = make_schema(&[("a", "object")], &[]);
        let ours = make_schema(&[("a", "object"), ("b", "string")], &[]);
        let theirs = make_schema(&[("a", "object"), ("c", "integer")], &[]);

        let result = three_way_merge(&base, &ours, &theirs);
        assert!(result.conflicts.is_empty());
        let Some(ref overlap) = result.pullback_overlap else {
            panic!("pullback overlap should be present");
        };
        assert!(
            overlap.shared_vertices.contains("a"),
            "base vertex 'a' should be shared"
        );
    }

    #[test]
    fn pullback_deduplicates_shared_addition() {
        // Both sides add vertex "b" with different kinds, but the vertex
        // also exists in both ours and theirs as a shared structure
        // through a base edge. When the pullback recognizes "b" as
        // shared, the merge should NOT conflict.
        let edge_ab = Edge {
            src: Name::from("a"),
            tgt: Name::from("b"),
            kind: Name::from("prop"),
            name: Some(Name::from("link")),
        };

        // Base has "a" with an edge to "b".
        let _base = make_schema(&[("a", "object"), ("b", "string")], &[edge_ab]);

        // Both sides remove "b" and re-add it with a different kind,
        // but keep the edge. This simulates a kind change tracked by
        // both sides independently.
        //
        // Actually, for the pullback to mark "b" as shared, it needs to
        // survive in both derived schemas. Let's test with base vertices
        // that both sides keep.
        let base2 = make_schema(&[("a", "object")], &[]);
        let ours2 = make_schema(&[("a", "object"), ("d", "record")], &[]);
        let theirs2 = make_schema(&[("a", "object"), ("d", "record")], &[]);

        let result = three_way_merge(&base2, &ours2, &theirs2);

        // Both added "d" with the same kind; should merge cleanly even
        // without pullback involvement.
        assert!(result.conflicts.is_empty());
        assert!(result.merged_schema.vertices.contains_key("d"));
    }

    #[test]
    fn pullback_overlap_with_removed_vertices() {
        // If one side removes a vertex, it shouldn't appear in the
        // pullback overlap.
        let base = make_schema(&[("a", "object"), ("b", "string")], &[]);
        let ours = make_schema(&[("a", "object")], &[]); // removed "b"
        let theirs = make_schema(&[("a", "object"), ("b", "string")], &[]);

        let diff_ours = diff::diff(&base, &ours);
        let diff_theirs = diff::diff(&base, &theirs);

        let overlap = compute_pullback_overlap(&base, &ours, &theirs, &diff_ours, &diff_theirs);
        let Some(overlap) = overlap else {
            panic!("pullback overlap should succeed");
        };

        // "a" survives on both sides.
        assert!(overlap.shared_vertices.contains("a"));
        // "b" was removed from ours, so it should NOT be shared.
        assert!(
            !overlap.shared_vertices.contains("b"),
            "removed vertex 'b' should not be in shared overlap"
        );
    }

    /// Build an empty schema with a preset `entries` list for the
    /// entries-merge tests.
    fn schema_with_entries(entries: &[&str]) -> Schema {
        let mut s = make_schema(&[], &[]);
        s.entries = entries.iter().map(|e| Name::from(*e)).collect();
        s
    }

    #[test]
    fn three_way_entries_kept_when_both_sides_keep() {
        let base = schema_with_entries(&["A"]);
        let ours = schema_with_entries(&["A"]);
        let theirs = schema_with_entries(&["A"]);
        let mut verts = HashMap::new();
        verts.insert(
            Name::from("A"),
            Vertex {
                id: Name::from("A"),
                kind: Name::from("object"),
                nsid: None,
            },
        );
        let merged = three_way_merge_entries(&base, &ours, &theirs, &verts);
        assert_eq!(merged, vec![Name::from("A")]);
    }

    #[test]
    fn three_way_entries_one_side_deleting_propagates() {
        // base = {A}, ours deleted A, theirs kept A. The merge should
        // honor the deletion.
        let base = schema_with_entries(&["A"]);
        let ours = schema_with_entries(&[]);
        let theirs = schema_with_entries(&["A"]);
        let mut verts = HashMap::new();
        verts.insert(
            Name::from("A"),
            Vertex {
                id: Name::from("A"),
                kind: Name::from("object"),
                nsid: None,
            },
        );
        let merged = three_way_merge_entries(&base, &ours, &theirs, &verts);
        assert!(merged.is_empty(), "delete-on-one-side must propagate");
    }

    #[test]
    fn three_way_entries_unilateral_addition_included() {
        // base = {}, ours added A. theirs = {}. Merge should include A.
        let base = schema_with_entries(&[]);
        let ours = schema_with_entries(&["A"]);
        let theirs = schema_with_entries(&[]);
        let mut verts = HashMap::new();
        verts.insert(
            Name::from("A"),
            Vertex {
                id: Name::from("A"),
                kind: Name::from("object"),
                nsid: None,
            },
        );
        let merged = three_way_merge_entries(&base, &ours, &theirs, &verts);
        assert_eq!(merged, vec![Name::from("A")]);
    }

    #[test]
    fn three_way_entries_drop_when_vertex_missing_from_merge() {
        // Even if both sides kept A, if the merged vertex set doesn't
        // contain A (e.g. it was removed at the vertex level), A must
        // not be an entry of the merge — every basepoint must name a
        // surviving vertex.
        let base = schema_with_entries(&["A"]);
        let ours = schema_with_entries(&["A"]);
        let theirs = schema_with_entries(&["A"]);
        let verts = HashMap::new();
        let merged = three_way_merge_entries(&base, &ours, &theirs, &verts);
        assert!(merged.is_empty());
    }

    #[test]
    fn schema_to_theory_roundtrip() {
        // Verify the helper function produces a theory with the right
        // number of sorts and ops.
        let edge = Edge {
            src: Name::from("a"),
            tgt: Name::from("b"),
            kind: Name::from("prop"),
            name: Some(Name::from("link")),
        };
        let schema = make_schema(&[("a", "object"), ("b", "string")], &[edge]);

        let theory = schema_to_theory("test", &schema);
        assert_eq!(theory.sorts.len(), 2);
        assert_eq!(theory.ops.len(), 1);
        assert!(theory.find_sort("a").is_some());
        assert!(theory.find_sort("b").is_some());
    }
}