panproto-mig 0.48.6

//! Automatic schema morphism discovery via backtracking search.
//!
//! Given two schemas A and B, enumerate all valid schema morphisms
//! A → B by reducing to a constraint satisfaction problem (CSP) and
//! solving via backtracking with forward checking.
//!
//! This follows the approach of `Catlab.jl` (`AlgebraicJulia`) where
//! C-set homomorphism finding is reduced to CSP with naturality
//! constraints. The MRV (Minimum Remaining Values) heuristic orders
//! variable selection for efficient pruning.
//!
//! # References
//!
//! - AlgebraicJulia/Catlab.jl: backtracking search for C-set
//!   homomorphisms with monic/iso constraints
//! - Spivak 2012: functorial data migration via schema morphisms

use std::collections::HashMap;

use panproto_gat::Name;
use panproto_schema::{Edge, Schema};

/// Options controlling the homomorphism search.
#[derive(Clone, Debug, Default)]
#[allow(clippy::struct_excessive_bools)]
pub struct SearchOptions {
    /// Require injective vertex map (no two source vertices map to
    /// the same target vertex).
    pub monic: bool,
    /// Require surjective vertex map (every target vertex is hit).
    pub epic: bool,
    /// Require bijective vertex map (isomorphism).
    pub iso: bool,
    /// Stop after finding this many morphisms (0 = unlimited).
    pub max_results: usize,
    /// Pre-assigned vertex mappings. The search extends this partial
    /// morphism to a total one.
    pub initial: HashMap<Name, Name>,
    /// When `true`, the CSP relaxes its hard edge-name overlap pruning
    /// for object vertices with large candidate domains. Kind-compatible
    /// targets are kept even when they share no outgoing edge name with
    /// the source vertex. Naturality is still enforced during
    /// backtracking.
    pub relax_edge_name_pruning: bool,
}

/// Additional domain restrictions and scoring overrides for the CSP solver.
///
/// Produced by hint propagation; consumed by [`find_morphisms_constrained`].
#[derive(Clone, Debug, Default)]
pub struct DomainConstraints {
    /// For each source vertex, restrict its domain to these specific targets.
    /// Vertices not in this map are unrestricted (beyond kind-compatibility).
    pub restricted_domains: HashMap<Name, Vec<Name>>,

    /// Target vertices to exclude from ALL domains.
    pub excluded_targets: std::collections::HashSet<Name>,

    /// Source vertices to exclude from the search entirely.
    pub excluded_sources: std::collections::HashSet<Name>,

    /// Override quality scoring component weights.
    /// Order: \[name, edge, property, degree\]. Default: \[0.25, 0.25, 0.3, 0.2\].
    pub scoring_weights: Option<[f64; 4]>,

    /// Minimum name similarity for domain candidates. If set, target
    /// vertices whose normalized name similarity to a source vertex
    /// falls below this threshold are pruned from that source vertex's
    /// domain. Similarity is `1.0 - edit_distance / max_len`.
    pub name_similarity_threshold: Option<f64>,
}

/// A discovered schema morphism with a quality score.
#[derive(Clone, Debug)]
pub struct FoundMorphism {
    /// Vertex mapping: source vertex ID → target vertex ID.
    pub vertex_map: HashMap<Name, Name>,
    /// Edge mapping: source edge → target edge.
    pub edge_map: HashMap<Edge, Edge>,
    /// Quality score in \[0.0, 1.0\], based on name similarity and
    /// structural overlap.
    pub quality: f64,
}

/// Find all valid schema morphisms from `src` to `tgt`.
///
/// Returns morphisms sorted by descending quality score. If
/// `opts.max_results` is non-zero, returns at most that many.
///
/// # Algorithm
///
/// Reduces to CSP:
/// - **Variables**: one per vertex in `src`
/// - **Domains**: compatible vertices in `tgt` (same kind)
/// - **Constraints**: naturality (edge-preserving) + optional
///   monic/epic/iso
///
/// Solves via backtracking with forward checking and MRV heuristic.
#[must_use]
pub fn find_morphisms(src: &Schema, tgt: &Schema, opts: &SearchOptions) -> Vec<FoundMorphism> {
    let mut state = BacktrackState::new(src, tgt, opts);
    let mut results = Vec::new();

    backtrack(&mut state, 0, &mut results, opts);

    // Sort by quality descending. `total_cmp` is a total order on f64
    // (it distinguishes +0 from -0 and handles NaN) so ties are never
    // collapsed to `Equal` the way `partial_cmp().unwrap_or(Equal)`
    // would; that collapse lets the sort retain the randomized arrival
    // order of results when two morphisms share a quality.
    results.sort_by(|a, b| b.quality.total_cmp(&a.quality));

    if opts.max_results > 0 {
        results.truncate(opts.max_results);
    }

    results
}

/// Find the single best schema morphism from `src` to `tgt`.
///
/// Returns `None` if no valid morphism exists.
#[must_use]
pub fn find_best_morphism(
    src: &Schema,
    tgt: &Schema,
    opts: &SearchOptions,
) -> Option<FoundMorphism> {
    let mut search_opts = opts.clone();
    // Find all morphisms to rank them (could optimize with branch-and-bound
    // but schemas are small enough that this is fine)
    search_opts.max_results = 0;
    let results = find_morphisms(src, tgt, &search_opts);
    results.into_iter().next()
}

/// Find all valid schema morphisms with additional domain constraints.
///
/// Like [`find_morphisms`], but applies domain restrictions from
/// [`DomainConstraints`] during state initialization.
///
/// # Warnings
///
/// Prints a warning to stderr if `opts.epic` or `opts.iso` is set
/// while `constraints.excluded_sources` is non-empty, since surjectivity
/// is ill-defined on a sub-schema induced by source exclusion.
#[must_use]
pub fn find_morphisms_constrained(
    src: &Schema,
    tgt: &Schema,
    opts: &SearchOptions,
    constraints: &DomainConstraints,
) -> Vec<FoundMorphism> {
    if (opts.epic || opts.iso) && !constraints.excluded_sources.is_empty() {
        eprintln!(
            "warning: epic/iso constraint combined with excluded_sources; \
             surjectivity check applies to the full target schema but the \
             source is a proper sub-schema, which may yield no results"
        );
    }

    let mut state = BacktrackState::new_constrained(src, tgt, opts, constraints);
    let mut results = Vec::new();

    let weights = constraints.scoring_weights.unwrap_or(DEFAULT_WEIGHTS);
    backtrack_weighted(&mut state, 0, &mut results, opts, weights);

    // See `find_morphisms` for the rationale on `total_cmp`.
    results.sort_by(|a, b| b.quality.total_cmp(&a.quality));

    if opts.max_results > 0 {
        results.truncate(opts.max_results);
    }

    results
}

/// Find the single best schema morphism with domain constraints.
///
/// Like [`find_best_morphism`], but applies [`DomainConstraints`].
#[must_use]
pub fn find_best_morphism_constrained(
    src: &Schema,
    tgt: &Schema,
    opts: &SearchOptions,
    constraints: &DomainConstraints,
) -> Option<FoundMorphism> {
    let mut search_opts = opts.clone();
    search_opts.max_results = 0;
    let results = find_morphisms_constrained(src, tgt, &search_opts, constraints);
    results.into_iter().next()
}

// ---------------------------------------------------------------------------
// Internal: backtracking state
// ---------------------------------------------------------------------------

/// The order in which source vertices will be assigned.
struct VertexOrder {
    /// Source vertex IDs in assignment order (MRV: smallest domain first).
    order: Vec<Name>,
}

/// State for the backtracking search.
struct BacktrackState<'a> {
    src: &'a Schema,
    tgt: &'a Schema,
    /// For each source vertex, the set of compatible target vertices.
    domains: HashMap<Name, Vec<Name>>,
    /// Current partial assignment: source vertex → target vertex.
    assignment: HashMap<Name, Name>,
    /// Assignment order (MRV).
    vertex_order: VertexOrder,
    /// Target vertices already used (for monic constraint).
    used_targets: std::collections::HashSet<Name>,
}

/// Default quality scoring weights: [name, edge, property, degree].
const DEFAULT_WEIGHTS: [f64; 4] = [0.25, 0.25, 0.3, 0.2];

impl<'a> BacktrackState<'a> {
    fn new(src: &'a Schema, tgt: &'a Schema, opts: &SearchOptions) -> Self {
        Self::new_constrained(src, tgt, opts, &DomainConstraints::default())
    }

    fn new_constrained(
        src: &'a Schema,
        tgt: &'a Schema,
        opts: &SearchOptions,
        constraints: &DomainConstraints,
    ) -> Self {
        // Compute initial domains: for each source vertex, find all
        // target vertices with compatible kind.
        let mut domains: HashMap<Name, Vec<Name>> = HashMap::new();

        for (src_id, src_vertex) in &src.vertices {
            let compatible: Vec<Name> = opts.initial.get(src_id).map_or_else(
                || {
                    let mut candidates: Vec<Name> = tgt
                        .vertices
                        .iter()
                        .filter(|(_, tv)| tv.kind == src_vertex.kind)
                        .map(|(tid, _)| tid.clone())
                        .collect();
                    // `tgt.vertices` is a HashMap with a randomized hasher;
                    // iterating it directly lets the candidate order drift
                    // across runs, which in turn drifts the CSP
                    // backtracking order and the composite-score tiebreak
                    // between equally-qualified morphisms. Pin it by name.
                    candidates.sort_by(|a, b| a.as_str().cmp(b.as_str()));

                    // Property-name domain pruning: for "object" vertices with
                    // large domains, restrict to targets sharing ≥1 edge name.
                    // This anchors alignment on shared structure (e.g., both
                    // have byteStart/byteEnd children). Skipped when
                    // `relax_edge_name_pruning` is set: callers who supplied
                    // alias/token-similarity anchors don't want the CSP
                    // pruning out kind-compatible candidates that the
                    // strategies seeded.
                    if candidates.len() > 5 && !opts.relax_edge_name_pruning {
                        let src_edge_names: std::collections::HashSet<&str> = src
                            .outgoing_edges(src_id)
                            .iter()
                            .filter_map(|e| e.name.as_deref())
                            .collect();
                        if !src_edge_names.is_empty() {
                            let pruned: Vec<Name> = candidates
                                .iter()
                                .filter(|tid| {
                                    let tgt_edge_names: std::collections::HashSet<&str> = tgt
                                        .outgoing_edges(tid)
                                        .iter()
                                        .filter_map(|e| e.name.as_deref())
                                        .collect();
                                    src_edge_names
                                        .intersection(&tgt_edge_names)
                                        .next()
                                        .is_some()
                                })
                                .cloned()
                                .collect();
                            if !pruned.is_empty() {
                                candidates = pruned;
                            }
                        }
                    }

                    candidates
                },
                |tgt_id| vec![tgt_id.clone()],
            );
            domains.insert(src_id.clone(), compatible);
        }

        // Apply domain constraints: excluded sources, excluded targets,
        // and restricted domains.
        for src_id in &constraints.excluded_sources {
            domains.remove(src_id);
        }
        if !constraints.excluded_targets.is_empty() {
            for domain in domains.values_mut() {
                domain.retain(|t| !constraints.excluded_targets.contains(t));
            }
        }
        for (src_id, restricted) in &constraints.restricted_domains {
            if let Some(domain) = domains.get_mut(src_id) {
                let allowed: std::collections::HashSet<&Name> = restricted.iter().collect();
                domain.retain(|t| allowed.contains(t));
            }
        }
        // Name similarity threshold: prune candidates whose normalized
        // name similarity (1 - edit_distance/max_len) is below threshold.
        if let Some(threshold) = constraints.name_similarity_threshold {
            for (src_id, domain) in &mut domains {
                if opts.initial.contains_key(src_id) {
                    continue; // Don't filter pre-assigned vertices
                }
                domain.retain(|tgt_id| {
                    let dist = edit_distance(src_id.as_str(), tgt_id.as_str());
                    let max_len = src_id.len().max(tgt_id.len()).max(1);
                    #[allow(clippy::cast_precision_loss)]
                    let similarity = 1.0 - (dist as f64 / max_len as f64);
                    similarity >= threshold
                });
            }
        }

        // MRV order: sort source vertices by domain size (smallest first).
        // `domains` is a HashMap, so collecting its keys gives a
        // randomized order; `sort_by_key` is stable, so ties on
        // `domain.len()` would otherwise retain that randomized order
        // and drift the backtracking exploration across runs. Pre-sort
        // by name to lock the tiebreak, then re-sort by domain length.
        let mut order: Vec<Name> = domains.keys().cloned().collect();
        order.sort_by(|a, b| a.as_str().cmp(b.as_str()));
        order.sort_by_key(|v| domains.get(v).map_or(0, Vec::len));

        let assignment: HashMap<Name, Name> = opts.initial.clone();
        let used_targets: std::collections::HashSet<Name> =
            opts.initial.values().cloned().collect();

        BacktrackState {
            src,
            tgt,
            domains,
            assignment,
            vertex_order: VertexOrder { order },
            used_targets,
        }
    }
}

/// Recursive backtracking search.
fn backtrack(
    state: &mut BacktrackState<'_>,
    depth: usize,
    results: &mut Vec<FoundMorphism>,
    opts: &SearchOptions,
) {
    // Check result limit
    if opts.max_results > 0 && results.len() >= opts.max_results {
        return;
    }

    // Base case: all vertices assigned
    if depth >= state.vertex_order.order.len() {
        // Check epic constraint
        if opts.epic || opts.iso {
            let assigned_targets: std::collections::HashSet<&Name> =
                state.assignment.values().collect();
            if assigned_targets.len() != state.tgt.vertices.len() {
                return; // Not surjective
            }
        }

        // Build the edge map from the vertex assignment
        if let Some(morphism) = build_morphism(state) {
            results.push(morphism);
        }
        return;
    }

    let src_vertex = state.vertex_order.order[depth].clone();

    // Skip if already assigned (from initial)
    if state.assignment.contains_key(&src_vertex) {
        backtrack(state, depth + 1, results, opts);
        return;
    }

    // Try each value in the domain
    let domain = state.domains.get(&src_vertex).cloned().unwrap_or_default();
    for tgt_vertex in domain {
        // Monic check: target not already used
        if (opts.monic || opts.iso) && state.used_targets.contains(&tgt_vertex) {
            continue;
        }

        // Forward check: does this assignment leave valid domains for
        // all unassigned neighbors?
        if !forward_check(state, &src_vertex, &tgt_vertex, depth) {
            continue;
        }

        // Assign
        state
            .assignment
            .insert(src_vertex.clone(), tgt_vertex.clone());
        state.used_targets.insert(tgt_vertex.clone());

        // Recurse
        backtrack(state, depth + 1, results, opts);

        // Unassign
        state.assignment.remove(&src_vertex);
        state.used_targets.remove(&tgt_vertex);

        if opts.max_results > 0 && results.len() >= opts.max_results {
            return;
        }
    }
}

/// Recursive backtracking search with configurable quality weights.
fn backtrack_weighted(
    state: &mut BacktrackState<'_>,
    depth: usize,
    results: &mut Vec<FoundMorphism>,
    opts: &SearchOptions,
    weights: [f64; 4],
) {
    if opts.max_results > 0 && results.len() >= opts.max_results {
        return;
    }

    if depth >= state.vertex_order.order.len() {
        if opts.epic || opts.iso {
            let assigned_targets: std::collections::HashSet<&Name> =
                state.assignment.values().collect();
            if assigned_targets.len() != state.tgt.vertices.len() {
                return;
            }
        }

        if let Some(morphism) = build_morphism_weighted(state, weights) {
            results.push(morphism);
        }
        return;
    }

    let src_vertex = state.vertex_order.order[depth].clone();

    if state.assignment.contains_key(&src_vertex) {
        backtrack_weighted(state, depth + 1, results, opts, weights);
        return;
    }

    let domain = state.domains.get(&src_vertex).cloned().unwrap_or_default();
    for tgt_vertex in domain {
        if (opts.monic || opts.iso) && state.used_targets.contains(&tgt_vertex) {
            continue;
        }

        if !forward_check(state, &src_vertex, &tgt_vertex, depth) {
            continue;
        }

        state
            .assignment
            .insert(src_vertex.clone(), tgt_vertex.clone());
        state.used_targets.insert(tgt_vertex.clone());

        backtrack_weighted(state, depth + 1, results, opts, weights);

        state.assignment.remove(&src_vertex);
        state.used_targets.remove(&tgt_vertex);

        if opts.max_results > 0 && results.len() >= opts.max_results {
            return;
        }
    }
}

/// Forward checking: verify that assigning `src_v → tgt_v` doesn't
/// make any unassigned neighbor's domain empty.
fn forward_check(state: &BacktrackState<'_>, src_v: &Name, tgt_v: &Name, depth: usize) -> bool {
    // Check edges: for every edge from src_v, there must exist a
    // compatible edge from tgt_v in the target schema.
    for src_edge in state.src.outgoing_edges(src_v) {
        let neighbor = &src_edge.tgt;
        if let Some(assigned_tgt) = state.assignment.get(neighbor) {
            // Neighbor already assigned; check that a compatible edge exists
            if !has_compatible_edge(state.tgt, tgt_v, assigned_tgt, src_edge) {
                return false;
            }
        } else {
            // Neighbor unassigned; check that at least one domain value
            // has a compatible edge from tgt_v
            let neighbor_domain = state.domains.get(neighbor);
            if let Some(domain) = neighbor_domain {
                let has_any = domain
                    .iter()
                    .any(|candidate| has_compatible_edge(state.tgt, tgt_v, candidate, src_edge));
                if !has_any {
                    return false;
                }
            }
        }
    }

    // Check incoming edges to src_v
    for src_edge in state.src.incoming_edges(src_v) {
        let neighbor = &src_edge.src;
        if let Some(assigned_tgt) = state.assignment.get(neighbor) {
            if !has_compatible_edge(state.tgt, assigned_tgt, tgt_v, src_edge) {
                return false;
            }
        } else {
            let neighbor_domain = state.domains.get(neighbor);
            if let Some(domain) = neighbor_domain {
                let has_any = domain
                    .iter()
                    .any(|candidate| has_compatible_edge(state.tgt, candidate, tgt_v, src_edge));
                if !has_any {
                    return false;
                }
            }
        }
    }

    // Check that unassigned vertices later in the order still have non-empty domains
    // given the monic constraint (if the target is now used up)
    if state.used_targets.len() + 1 > state.tgt.vertices.len() {
        // More assignments needed than available targets (with monic)
        // This is caught by domain emptiness above
    }

    let _ = depth; // Used for potential future optimizations
    true
}

/// Check if the target schema has an edge compatible with `src_edge`
/// from `tgt_src` to `tgt_tgt`.
///
/// An edge is compatible if it has the same kind. Names don't need to
/// match; a morphism can map an edge to a different-named edge (this
/// is what renaming IS). Name matching only affects quality scoring.
fn has_compatible_edge(
    tgt_schema: &Schema,
    tgt_src: &Name,
    tgt_tgt: &Name,
    src_edge: &Edge,
) -> bool {
    tgt_schema
        .edges_between(tgt_src, tgt_tgt)
        .iter()
        .any(|tgt_edge| tgt_edge.kind == src_edge.kind)
}

/// Build a complete morphism from the vertex assignment by deriving
/// the edge map.
fn build_morphism(state: &BacktrackState<'_>) -> Option<FoundMorphism> {
    build_morphism_weighted(state, DEFAULT_WEIGHTS)
}

/// Build a complete morphism with configurable quality weights.
///
/// Only considers edges in the induced sub-schema: edges where both
/// endpoints are in `state.assignment`. Edges touching vertices that
/// were excluded from the search (not in `state.domains`) are skipped.
/// This correctly implements morphism construction on the sub-schema
/// induced by the assigned vertex set.
fn build_morphism_weighted(state: &BacktrackState<'_>, weights: [f64; 4]) -> Option<FoundMorphism> {
    let mut edge_map: HashMap<Edge, Edge> = HashMap::new();

    for src_edge in state.src.edges.keys() {
        let Some(tgt_src) = state.assignment.get(&src_edge.src) else {
            // Source endpoint not assigned (excluded from search).
            // Skip: this edge is not in the induced sub-schema.
            continue;
        };
        let Some(tgt_tgt) = state.assignment.get(&src_edge.tgt) else {
            continue;
        };

        // Find a compatible target edge (same kind between mapped vertices).
        // Prefer name-matching edges, fall back to any kind-matching edge.
        let candidates = state.tgt.edges_between(tgt_src, tgt_tgt);
        let tgt_edge = candidates
            .iter()
            .find(|te| te.kind == src_edge.kind && te.name == src_edge.name)
            .or_else(|| candidates.iter().find(|te| te.kind == src_edge.kind))?;

        edge_map.insert(src_edge.clone(), tgt_edge.clone());
    }

    let quality =
        compute_quality_weighted(&state.assignment, &edge_map, state.src, state.tgt, weights);

    Some(FoundMorphism {
        vertex_map: state.assignment.clone(),
        edge_map,
        quality,
    })
}

/// Compute a quality score for a morphism.
///
/// Higher is better. Four components:
/// 1. **Name similarity** (0.25): 1.0 - (avg edit distance / max name length)
/// 2. **Edge name preservation** (0.25): fraction of edges with matching names
/// 3. **Property-name Jaccard** (0.3): for each mapped vertex pair, Jaccard
///    similarity of their outgoing edge names, rewarding structural alignment
/// 4. **Degree similarity** (0.2): penalizes mappings where vertex degrees
///    differ significantly
fn compute_quality_weighted(
    vertex_map: &HashMap<Name, Name>,
    edge_map: &HashMap<Edge, Edge>,
    src: &Schema,
    tgt: &Schema,
    weights: [f64; 4],
) -> f64 {
    if vertex_map.is_empty() {
        return 1.0;
    }

    // IEEE-754 f64 addition is not associative, so summing over a
    // `HashMap` (randomized iteration order) would let the least
    // significant bits of each component score drift across process
    // instances. Two morphisms whose true scores differ only at the
    // lsb would then swap sort order nondeterministically. Sort the
    // vertex pairs once by source name so every reduction below runs
    // in a canonical order.
    let mut vm_pairs: Vec<(&Name, &Name)> = vertex_map.iter().collect();
    vm_pairs.sort_by(|a, b| a.0.as_str().cmp(b.0.as_str()));

    // 1. Name similarity component (weight 0.25)
    let name_score: f64 = {
        let mut total = 0.0;
        for (src_id, tgt_id) in &vm_pairs {
            let dist = edit_distance(src_id.as_str(), tgt_id.as_str());
            let max_len = src_id.len().max(tgt_id.len()).max(1);
            #[allow(clippy::cast_precision_loss)]
            {
                total += 1.0 - (dist as f64 / max_len as f64);
            }
        }
        #[allow(clippy::cast_precision_loss)]
        {
            total / vertex_map.len() as f64
        }
    };

    // 2. Edge name preservation component (weight 0.25)
    let edge_score: f64 = if edge_map.is_empty() {
        1.0
    } else {
        let matching = edge_map
            .iter()
            .filter(|(src_e, tgt_e)| src_e.name == tgt_e.name)
            .count();
        #[allow(clippy::cast_precision_loss)]
        {
            matching as f64 / edge_map.len() as f64
        }
    };

    // 3. Property-name Jaccard similarity (weight 0.3)
    let prop_score: f64 = {
        let mut total = 0.0;
        let mut count = 0;
        for (src_id, tgt_id) in &vm_pairs {
            let src_names: std::collections::HashSet<&str> = src
                .outgoing_edges(src_id)
                .iter()
                .filter_map(|e| e.name.as_deref())
                .collect();
            let tgt_names: std::collections::HashSet<&str> = tgt
                .outgoing_edges(tgt_id)
                .iter()
                .filter_map(|e| e.name.as_deref())
                .collect();
            if !src_names.is_empty() || !tgt_names.is_empty() {
                let intersection = src_names.intersection(&tgt_names).count();
                let union = src_names.union(&tgt_names).count();
                if union > 0 {
                    #[allow(clippy::cast_precision_loss)]
                    {
                        total += intersection as f64 / union as f64;
                    }
                    count += 1;
                }
            }
        }
        if count > 0 {
            total / f64::from(count)
        } else {
            1.0
        }
    };

    // 4. Degree similarity (weight 0.2)
    let degree_score: f64 = {
        let mut total = 0.0;
        for (src_id, tgt_id) in &vm_pairs {
            let src_deg = src.outgoing_edges(src_id).len();
            let tgt_deg = tgt.outgoing_edges(tgt_id).len();
            let max_deg = src_deg.max(tgt_deg);
            if max_deg > 0 {
                let diff = src_deg.abs_diff(tgt_deg);
                #[allow(clippy::cast_precision_loss)]
                {
                    total += 1.0 - (diff as f64 / max_deg as f64);
                }
            } else {
                total += 1.0;
            }
        }
        #[allow(clippy::cast_precision_loss)]
        {
            total / vertex_map.len() as f64
        }
    };

    #[allow(clippy::suboptimal_flops)]
    let score = weights[0] * name_score
        + weights[1] * edge_score
        + weights[2] * prop_score
        + weights[3] * degree_score;
    score
}

/// Simple edit distance (Levenshtein).
fn edit_distance(a: &str, b: &str) -> usize {
    let a_bytes = a.as_bytes();
    let b_bytes = b.as_bytes();
    let m = a_bytes.len();
    let n = b_bytes.len();

    let mut prev = (0..=n).collect::<Vec<_>>();
    let mut curr = vec![0; n + 1];

    for i in 1..=m {
        curr[0] = i;
        for j in 1..=n {
            let cost = usize::from(a_bytes[i - 1] != b_bytes[j - 1]);
            curr[j] = (prev[j] + 1).min(curr[j - 1] + 1).min(prev[j - 1] + cost);
        }
        std::mem::swap(&mut prev, &mut curr);
    }

    prev[n]
}

/// Convert a [`FoundMorphism`] into a [`crate::Migration`].
#[must_use]
pub fn morphism_to_migration(found: &FoundMorphism) -> crate::Migration {
    crate::Migration {
        vertex_map: found.vertex_map.clone(),
        edge_map: found.edge_map.clone(),
        hyper_edge_map: HashMap::new(),
        label_map: HashMap::new(),
        resolver: HashMap::new(),
        hyper_resolver: HashMap::new(),
        expr_resolvers: HashMap::new(),
    }
}

#[cfg(test)]
#[allow(clippy::unwrap_used)]
mod tests {
    use super::*;
    use panproto_schema::{Protocol, Schema, SchemaBuilder};

    fn test_protocol() -> Protocol {
        Protocol {
            name: "test".into(),
            schema_theory: "ThTest".into(),
            instance_theory: "ThWType".into(),
            edge_rules: vec![],
            obj_kinds: vec!["object".into(), "string".into(), "integer".into()],
            constraint_sorts: vec![],
            ..Protocol::default()
        }
    }

    fn build_schema(vertices: &[(&str, &str)], edges: &[(&str, &str, &str, &str)]) -> Schema {
        let proto = test_protocol();
        let mut builder = SchemaBuilder::new(&proto);
        for (id, kind) in vertices {
            builder = builder.vertex(id, kind, None::<&str>).unwrap();
        }
        for (src, tgt, kind, name) in edges {
            builder = builder.edge(src, tgt, kind, Some(*name)).unwrap();
        }
        builder.build().unwrap()
    }

    #[test]
    fn identity_morphism_found() {
        let schema = build_schema(
            &[("root", "object"), ("root.name", "string")],
            &[("root", "root.name", "prop", "name")],
        );

        let results = find_morphisms(&schema, &schema, &SearchOptions::default());
        assert!(!results.is_empty(), "should find at least the identity");

        // The identity morphism should be among the results
        let has_identity = results.iter().any(|m| {
            m.vertex_map
                .iter()
                .all(|(src, tgt)| src.as_str() == tgt.as_str())
        });
        assert!(has_identity, "identity morphism should be found");
    }

    #[test]
    fn renamed_schema_morphism() {
        let old = build_schema(
            &[("root", "object"), ("root.text", "string")],
            &[("root", "root.text", "prop", "text")],
        );
        let new = build_schema(
            &[("root", "object"), ("root.body", "string")],
            &[("root", "root.body", "prop", "body")],
        );

        let results = find_morphisms(&old, &new, &SearchOptions::default());
        assert!(
            !results.is_empty(),
            "should find morphism for renamed schema"
        );

        // root should map to root (same kind, has outgoing edges)
        let best = &results[0];
        assert_eq!(
            best.vertex_map.get("root").map(Name::as_str),
            Some("root"),
            "root should map to root"
        );
    }

    #[test]
    fn no_morphism_incompatible() {
        let a = build_schema(
            &[("root", "object"), ("root.x", "string")],
            &[("root", "root.x", "prop", "x")],
        );
        // b has no string vertex, so no valid mapping for root.x
        let b = build_schema(
            &[("root", "object"), ("root.y", "integer")],
            &[("root", "root.y", "prop", "y")],
        );

        let results = find_morphisms(&a, &b, &SearchOptions::default());
        assert!(
            results.is_empty(),
            "no morphism should exist between incompatible schemas"
        );
    }

    #[test]
    fn monic_rejects_non_injective() {
        // Two source string vertices, one target string vertex
        let src = build_schema(
            &[
                ("root", "object"),
                ("root.a", "string"),
                ("root.b", "string"),
            ],
            &[
                ("root", "root.a", "prop", "a"),
                ("root", "root.b", "prop", "b"),
            ],
        );
        let tgt = build_schema(
            &[("root", "object"), ("root.x", "string")],
            &[("root", "root.x", "prop", "x")],
        );

        let opts = SearchOptions {
            monic: true,
            ..SearchOptions::default()
        };
        let results = find_morphisms(&src, &tgt, &opts);
        // With monic, both root.a and root.b can't map to root.x
        assert!(results.is_empty(), "monic should reject non-injective maps");
    }

    #[test]
    fn iso_finds_isomorphism() {
        let a = build_schema(
            &[("root", "object"), ("root.x", "string")],
            &[("root", "root.x", "prop", "x")],
        );
        let b = build_schema(
            &[("root", "object"), ("root.y", "string")],
            &[("root", "root.y", "prop", "y")],
        );

        let opts = SearchOptions {
            iso: true,
            ..SearchOptions::default()
        };
        let results = find_morphisms(&a, &b, &opts);
        assert!(
            !results.is_empty(),
            "isomorphism should exist between structurally identical schemas"
        );
    }

    #[test]
    fn initial_assignment_respected() {
        let schema = build_schema(
            &[
                ("root", "object"),
                ("root.a", "string"),
                ("root.b", "string"),
            ],
            &[
                ("root", "root.a", "prop", "a"),
                ("root", "root.b", "prop", "b"),
            ],
        );

        let mut initial = HashMap::new();
        initial.insert(Name::from("root.a"), Name::from("root.b"));
        initial.insert(Name::from("root.b"), Name::from("root.a"));
        initial.insert(Name::from("root"), Name::from("root"));

        let opts = SearchOptions {
            initial,
            ..SearchOptions::default()
        };
        let results = find_morphisms(&schema, &schema, &opts);
        assert!(
            !results.is_empty(),
            "should find morphism with initial assignment"
        );

        let m = &results[0];
        assert_eq!(m.vertex_map.get("root.a").map(Name::as_str), Some("root.b"));
        assert_eq!(m.vertex_map.get("root.b").map(Name::as_str), Some("root.a"));
    }

    #[test]
    fn quality_scoring_prefers_name_match() {
        let src = build_schema(
            &[("root", "object"), ("root.name", "string")],
            &[("root", "root.name", "prop", "name")],
        );
        // Target has two string vertices, one with matching name
        let tgt = build_schema(
            &[
                ("root", "object"),
                ("root.name", "string"),
                ("root.other", "string"),
            ],
            &[
                ("root", "root.name", "prop", "name"),
                ("root", "root.other", "prop", "other"),
            ],
        );

        let results = find_morphisms(&src, &tgt, &SearchOptions::default());
        assert!(results.len() >= 2, "should find multiple morphisms");

        // Best morphism should map root.name → root.name (exact name match)
        let best = &results[0];
        assert_eq!(
            best.vertex_map.get("root.name").map(Name::as_str),
            Some("root.name"),
            "best morphism should prefer name-matching target"
        );
    }

    #[test]
    fn morphism_to_migration_conversion() {
        let schema = build_schema(
            &[("root", "object"), ("root.x", "string")],
            &[("root", "root.x", "prop", "x")],
        );

        let results = find_morphisms(&schema, &schema, &SearchOptions::default());
        assert!(!results.is_empty());

        let mig = morphism_to_migration(&results[0]);
        assert_eq!(mig.vertex_map.len(), 2);
        assert_eq!(mig.edge_map.len(), 1);
    }

    #[test]
    fn empty_schema_morphism() {
        let empty = Schema {
            protocol: "test".into(),
            vertices: HashMap::new(),
            edges: HashMap::new(),
            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(),
        };

        let results = find_morphisms(&empty, &empty, &SearchOptions::default());
        assert_eq!(
            results.len(),
            1,
            "empty schema has exactly one self-morphism"
        );
    }

    #[test]
    fn find_best_returns_highest_quality() {
        let src = build_schema(
            &[("root", "object"), ("root.name", "string")],
            &[("root", "root.name", "prop", "name")],
        );
        let tgt = build_schema(
            &[
                ("root", "object"),
                ("root.name", "string"),
                ("root.other", "string"),
            ],
            &[
                ("root", "root.name", "prop", "name"),
                ("root", "root.other", "prop", "other"),
            ],
        );

        let best = find_best_morphism(&src, &tgt, &SearchOptions::default());
        assert!(best.is_some());
        let m = best.unwrap();
        // Should pick the name-matching one
        assert_eq!(
            m.vertex_map.get("root.name").map(Name::as_str),
            Some("root.name")
        );
    }

    #[test]
    fn relax_edge_name_pruning_rescues_valid_target_with_disjoint_edge_names() {
        // Build a source "root" object with >5 candidate targets, all
        // kind-compatible but sharing zero edge-name overlap with the
        // source's outgoing edges. With the pruner on (relax=false)
        // the pruner suppresses them all because none share an edge
        // name. With relax=true the candidates survive and a morphism
        // is found.
        let src = build_schema(
            &[
                ("s_root", "object"),
                ("s_a", "string"),
                ("s_b", "string"),
                ("s_c", "string"),
                ("s_d", "string"),
                ("s_e", "string"),
                ("s_f", "string"),
            ],
            &[
                ("s_root", "s_a", "prop", "src_alpha"),
                ("s_root", "s_b", "prop", "src_beta"),
                ("s_root", "s_c", "prop", "src_gamma"),
                ("s_root", "s_d", "prop", "src_delta"),
                ("s_root", "s_e", "prop", "src_epsilon"),
                ("s_root", "s_f", "prop", "src_zeta"),
            ],
        );
        // Target objects (>5) each with a disjoint set of edge names:
        // no overlap with the source's `src_*` names.
        let tgt = build_schema(
            &[
                ("t_root_a", "object"),
                ("t_root_b", "object"),
                ("t_root_c", "object"),
                ("t_root_d", "object"),
                ("t_root_e", "object"),
                ("t_root_f", "object"),
                ("t_leaf_a", "string"),
                ("t_leaf_b", "string"),
                ("t_leaf_c", "string"),
                ("t_leaf_d", "string"),
                ("t_leaf_e", "string"),
                ("t_leaf_f", "string"),
            ],
            &[
                ("t_root_a", "t_leaf_a", "prop", "tgt_one"),
                ("t_root_b", "t_leaf_b", "prop", "tgt_two"),
                ("t_root_c", "t_leaf_c", "prop", "tgt_three"),
                ("t_root_d", "t_leaf_d", "prop", "tgt_four"),
                ("t_root_e", "t_leaf_e", "prop", "tgt_five"),
                ("t_root_f", "t_leaf_f", "prop", "tgt_six"),
            ],
        );

        // Strict-style pruner ON: no morphism honors all source edges,
        // so the CSP cannot extend to a total assignment via pruned
        // object domains. Best-found (if any) is low quality.
        let strict_opts = SearchOptions::default();
        let strict = find_best_morphism(&src, &tgt, &strict_opts);

        // Relaxed: kind-compatible targets are preserved even with no
        // edge-name overlap; the CSP can now explore them.
        let relaxed_opts = SearchOptions {
            relax_edge_name_pruning: true,
            ..Default::default()
        };
        let relaxed = find_best_morphism(&src, &tgt, &relaxed_opts);

        assert!(
            relaxed.is_some(),
            "relaxed pruning should find a morphism between kind-compatible schemas"
        );
        if let (Some(s), Some(r)) = (strict.as_ref(), relaxed.as_ref()) {
            assert!(
                r.vertex_map.len() >= s.vertex_map.len(),
                "relaxed pruning should match at least as many vertices"
            );
        }
    }

    #[test]
    fn relax_edge_name_pruning_composes_with_excluded_sources() {
        // When `relax_edge_name_pruning` is on AND `excluded_sources`
        // names some source vertices, the CSP must (a) keep
        // kind-compatible candidates that would otherwise be pruned
        // for lack of edge-name overlap, AND (b) still drop the named
        // source vertices from every domain.
        let src = build_schema(
            &[
                ("s_root", "object"),
                ("s_a", "string"),
                ("s_b", "string"),
                ("s_c", "string"),
                ("s_d", "string"),
                ("s_e", "string"),
                ("s_f", "string"),
                ("s_excluded", "string"),
            ],
            &[
                ("s_root", "s_a", "prop", "src_alpha"),
                ("s_root", "s_b", "prop", "src_beta"),
                ("s_root", "s_c", "prop", "src_gamma"),
                ("s_root", "s_d", "prop", "src_delta"),
                ("s_root", "s_e", "prop", "src_epsilon"),
                ("s_root", "s_f", "prop", "src_zeta"),
                ("s_root", "s_excluded", "prop", "src_excluded"),
            ],
        );
        let tgt = build_schema(
            &[
                ("t_root_a", "object"),
                ("t_root_b", "object"),
                ("t_root_c", "object"),
                ("t_root_d", "object"),
                ("t_root_e", "object"),
                ("t_root_f", "object"),
                ("t_leaf_a", "string"),
                ("t_leaf_b", "string"),
            ],
            &[
                ("t_root_a", "t_leaf_a", "prop", "tgt_one"),
                ("t_root_b", "t_leaf_b", "prop", "tgt_two"),
            ],
        );
        let opts = SearchOptions {
            relax_edge_name_pruning: true,
            ..Default::default()
        };
        let mut constraints = DomainConstraints::default();
        constraints
            .excluded_sources
            .insert(Name::from("s_excluded"));
        let results = find_morphisms_constrained(&src, &tgt, &opts, &constraints);
        // Relaxation must not reintroduce the excluded source.
        for r in &results {
            assert!(
                !r.vertex_map.contains_key(&Name::from("s_excluded")),
                "excluded_sources must win over relax_edge_name_pruning; \
                 vertex_map leaked excluded source"
            );
        }
    }
}