meta-ast 0.7.0

//! Cut-edge detection and annotation for deployment planning.
//!
//! When an SCC straddles a language boundary or a same-language
//! pod exceeds the maximum size threshold, the weakest edge
//! (lowest confidence) is cut and annotated. The cut edge represents
//! a point where a direct call must be converted to an RPC stub;
//! the petgraph itself is never mutated - only the deployment plan
//! is annotated.

use std::collections::HashSet;
use std::path::Path;

use crate::deploy::pod::{Pod, PodPartition, node_to_file_id};
use crate::graph::scc::SccAnalysis;
use crate::graph::{CodeGraph, NodeData};
use crate::language::LangId;
use crate::model::FileId;

/// Reason the edge was selected for cutting.
#[derive(Debug, Clone, serde::Serialize)]
#[non_exhaustive]
pub enum CutReason {
    CrossLanguageScc,
    OversizedPod { pod_size: usize, max_size: usize },
}

/// Path spelling written into a manifest annotation.
///
/// The two constructors are the only ways to make one, so an annotation never
/// carries a raw platform path. Serialized transparently: the manifest keeps
/// writing plain strings.
#[derive(Debug, Clone, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
#[serde(transparent)]
pub struct PortablePath(String);

impl PortablePath {
    /// Portable spelling of a project path.
    pub fn from_path(path: &Path) -> Self {
        Self(crate::input::portable_path(path))
    }

    /// Synthetic endpoint for a file that has no node in the graph.
    pub fn anchor(file_id: FileId) -> Self {
        Self(format!("file#{}", file_id.to_raw()))
    }

    /// The endpoint as written into the manifest.
    pub fn as_str(&self) -> &str {
        &self.0
    }
}

impl std::fmt::Display for PortablePath {
    fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        formatter.write_str(&self.0)
    }
}

/// Annotation attached to a cut edge in the manifest.
#[derive(Debug, Clone, serde::Serialize)]
pub struct CutAnnotation {
    pub from_file: PortablePath,
    pub to_file: PortablePath,
    pub cut_reason: CutReason,
    pub original_confidence: f32,
}

/// A recorded cut edge that must appear as an RPC stub in the manifest.
#[derive(Debug, Clone)]
pub struct CutEdge {
    pub from_pod: usize,
    pub to_pod: usize,
    pub annotation: CutAnnotation,
}

/// Default maximum pod size (in files) before rebalancing is triggered.
pub const DEFAULT_MAX_POD_SIZE: usize = 20;

/// Detect cross-language SCC edges that must be cut.
///
/// For each SCC spanning multiple languages, find the single lowest-
/// confidence cross-language internal edge and mark it for RPC conversion.
/// Pod IDs are resolved from the partition so the manifest generator
/// can place cuts correctly.
pub fn find_cross_language_cuts(
    scc: &SccAnalysis,
    graph: &CodeGraph,
    file_languages: &std::collections::HashMap<FileId, LangId>,
    partition: &PodPartition,
) -> Vec<CutEdge> {
    // Build FileId -> pod_id lookup for resolving cut pod membership.
    let mut file_to_pod: std::collections::HashMap<FileId, usize> =
        std::collections::HashMap::new();
    for pod in &partition.pods {
        for &fid in &pod.files {
            file_to_pod.insert(fid, pod.id);
        }
    }

    let mut cuts = Vec::new();
    let g = graph.graph();

    for comp in &scc.components {
        if !comp.is_cyclic {
            continue;
        }

        // Build a HashSet of component nodes for O(1) membership tests.
        let comp_nodes: HashSet<_> = comp.nodes.iter().copied().collect();

        // Determine languages present in this component. Import edges connect
        // File->File (and File->External) directly, so a cross-language cycle can
        // be composed entirely of File nodes with no Symbol nodes; match every
        // NodeData variant that carries a language to avoid missing such cycles.
        let mut langs = HashSet::new();
        for &node_idx in &comp.nodes {
            match g.node_weight(node_idx) {
                Some(NodeData::Symbol(s)) => {
                    if let Some(&lang) = file_languages.get(&s.file_id) {
                        langs.insert(lang);
                    }
                }
                Some(NodeData::File(f)) => {
                    langs.insert(f.language);
                }
                Some(NodeData::External(e)) => {
                    langs.insert(e.language);
                }
                Some(NodeData::Data(_)) => {}
                None => {}
            }
        }
        if langs.len() <= 1 {
            continue;
        }

        // Find the lowest-confidence cross-language edge inside this SCC.
        let mut best_edge: Option<(FileId, FileId, f32)> = None;
        for edge_idx in g.edge_indices() {
            let weight = &g[edge_idx];
            if !weight.participates_in_scc() {
                continue;
            }
            let Some((u, v)) = g.edge_endpoints(edge_idx) else {
                continue;
            };
            if !comp_nodes.contains(&u) || !comp_nodes.contains(&v) {
                continue;
            }
            let Some(src_fid) = node_to_file_id(&g[u]) else {
                continue;
            };
            let Some(dst_fid) = node_to_file_id(&g[v]) else {
                continue;
            };
            if file_languages.get(&src_fid) != file_languages.get(&dst_fid) {
                let conf = weight.confidence;
                if conf < best_edge.map_or(f32::MAX, |(_, _, c)| c) {
                    best_edge = Some((src_fid, dst_fid, conf));
                }
            }
        }

        if let Some((src, dst, conf)) = best_edge {
            let (Some(&from_pod), Some(&to_pod)) = (file_to_pod.get(&src), file_to_pod.get(&dst))
            else {
                // A cut anchored at pod zero would blame an unrelated pod.
                tracing::warn!(
                    from = src.to_raw(),
                    to = dst.to_raw(),
                    "cut skipped: an endpoint has no pod"
                );
                continue;
            };
            cuts.push(CutEdge {
                from_pod,
                to_pod,
                annotation: CutAnnotation {
                    from_file: file_label(graph, src),
                    to_file: file_label(graph, dst),
                    cut_reason: CutReason::CrossLanguageScc,
                    original_confidence: conf,
                },
            });
        }
    }

    cuts
}

/// A portable path for a file node. A missing node keeps the identifier form so
/// the anomaly is visible instead of silently pointing at another file.
fn file_label(graph: &CodeGraph, file_id: FileId) -> PortablePath {
    graph
        .file_node(file_id)
        .map(|file| PortablePath::from_path(&file.path))
        .unwrap_or_else(|| PortablePath::anchor(file_id))
}

/// Find the weakest internal edge in an oversized pod and mark it for splitting.
///
/// Greedy approach: for a pod exceeding `max_size`, find the
/// internal edge with the lowest confidence and cut it.
/// Iterates graph edges once (O(edges)) instead of per-file.
pub fn find_oversized_pod_cut(pod: &Pod, graph: &CodeGraph, max_size: usize) -> Option<CutEdge> {
    if pod.files.len() <= max_size {
        return None;
    }

    let files_set: HashSet<FileId> = pod.files.iter().copied().collect();
    let mut best_edge: Option<(FileId, FileId, f32)> = None;
    let g = graph.graph();

    // Single pass over all edges -- filter to intra-pod edges only.
    for edge_idx in g.edge_indices() {
        let weight = &g[edge_idx];
        if !weight.participates_in_scc() {
            continue;
        }
        let Some((u, v)) = g.edge_endpoints(edge_idx) else {
            continue;
        };
        let Some(src_fid) = node_to_file_id(&g[u]) else {
            continue;
        };
        let Some(dst_fid) = node_to_file_id(&g[v]) else {
            continue;
        };
        // Only edges where both endpoints are in this pod.
        if !files_set.contains(&src_fid) || !files_set.contains(&dst_fid) {
            continue;
        }
        let conf = weight.confidence;
        if conf < best_edge.map_or(f32::MAX, |(_, _, c)| c) {
            best_edge = Some((src_fid, dst_fid, conf));
        }
    }

    best_edge.map(|(src, dst, conf)| CutEdge {
        from_pod: pod.id,
        to_pod: pod.id,
        annotation: CutAnnotation {
            from_file: file_label(graph, src),
            to_file: file_label(graph, dst),
            cut_reason: CutReason::OversizedPod {
                pod_size: pod.files.len(),
                max_size,
            },
            original_confidence: conf,
        },
    })
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::deploy::pod::partition_into_pods;
    use crate::graph::edge::EdgeKind;
    use crate::graph::node::{FileNode, NodeData};
    use crate::graph::scc::SccAnalysis;
    use crate::language::LangId;
    use crate::model::ids::{FileId, SnapshotId};
    use petgraph::graph::NodeIndex;
    use std::collections::HashMap;
    use std::path::PathBuf;

    /// Build a pod of `n` same-language files (f0..f{n-1}.py) where each file
    /// imports the next, plus a deliberately weak edge from the first to the
    /// last, to exercise `find_oversized_pod_cut`.
    fn build_chain_pod(n: usize) -> (Pod, CodeGraph) {
        let mut graph = CodeGraph::new(SnapshotId::new(1).unwrap());
        let mut fids = Vec::with_capacity(n);
        for i in 0..n {
            let id = FileId::new(i as u32 + 1).unwrap();
            let idx = graph.add_node(NodeData::File(FileNode::new(
                id,
                PathBuf::from(format!("f{i}.py")),
                LangId::Python,
                SnapshotId::new(1).unwrap(),
            )));
            graph.file_to_index.insert(id, idx);
            fids.push(id);
        }

        let idx_of = |fid: FileId| -> NodeIndex { *graph.file_to_index.get(&fid).unwrap() };
        // Precompute edge endpoints first: idx_of borrows graph immutably
        // and cannot coexist with the &mut graph of add_edge_normalized.
        let weak_edge = if n >= 2 {
            Some((idx_of(fids[0]), idx_of(fids[n - 1])))
        } else {
            None
        };
        let mut link_edges: Vec<(NodeIndex, NodeIndex)> = Vec::new();
        for i in 0..n.saturating_sub(1) {
            link_edges.push((idx_of(fids[i]), idx_of(fids[i + 1])));
        }
        for (src, dst) in &link_edges {
            graph.add_edge_normalized(*src, *dst, EdgeKind::Import, 1.0);
        }
        if let Some((src, dst)) = weak_edge {
            graph.add_edge_normalized(src, dst, EdgeKind::Import, 0.3);
        }

        let pod = Pod {
            id: 0,
            files: fids,
            language: LangId::Python,
        };
        (pod, graph)
    }

    #[test]
    fn oversized_pod_cut_fires_below_threshold() {
        let (pod, graph) = build_chain_pod(4);
        let cut = find_oversized_pod_cut(&pod, &graph, 3);
        let cut = cut.expect("oversized pod should produce a cut");
        assert_eq!(cut.from_pod, 0);
        assert_eq!(cut.to_pod, 0);
        match &cut.annotation.cut_reason {
            CutReason::OversizedPod { pod_size, max_size } => {
                assert_eq!(*pod_size, 4);
                assert_eq!(*max_size, 3);
            }
            other => panic!("expected OversizedPod, got {other:?}"),
        }
        assert_eq!(cut.annotation.original_confidence, 0.3);
    }

    #[test]
    fn small_pod_no_oversized_cut() {
        let (pod, graph) = build_chain_pod(2);
        assert!(
            find_oversized_pod_cut(&pod, &graph, 3).is_none(),
            "pod within threshold must not be cut"
        );
    }

    #[test]
    fn cross_language_cut_names_the_files_not_ids() {
        let mut graph = CodeGraph::new(SnapshotId::new(1).unwrap());
        let py_id = FileId::new(1).unwrap();
        let go_id = FileId::new(2).unwrap();
        let py_idx = graph.add_node(NodeData::File(FileNode::new(
            py_id,
            PathBuf::from("orch.py"),
            LangId::Python,
            SnapshotId::new(1).unwrap(),
        )));
        let go_idx = graph.add_node(NodeData::File(FileNode::new(
            go_id,
            PathBuf::from("auth.go"),
            LangId::Go,
            SnapshotId::new(1).unwrap(),
        )));
        graph.file_to_index.insert(py_id, py_idx);
        graph.file_to_index.insert(go_id, go_idx);
        graph.add_edge_normalized(py_idx, go_idx, EdgeKind::Import, 1.0);
        graph.add_edge_normalized(go_idx, py_idx, EdgeKind::Import, 1.0);

        let scc = SccAnalysis::analyze(graph.graph());
        let mut file_languages: HashMap<FileId, LangId> = HashMap::new();
        file_languages.insert(py_id, LangId::Python);
        file_languages.insert(go_id, LangId::Go);
        let partition = partition_into_pods(&graph);
        let cuts = find_cross_language_cuts(&scc, &graph, &file_languages, &partition);
        let cut = cuts
            .into_iter()
            .find(|c| matches!(c.annotation.cut_reason, CutReason::CrossLanguageScc))
            .expect("cross-language cycle must produce a CrossLanguageScc cut");

        // ADR 0003 traceability: the annotation must name the cut files so a
        // reader can find them. A numeric FileId is not traceable.
        assert!(
            cut.annotation.from_file.as_str().ends_with("orch.py"),
            "from_file must be the source path, got {}",
            cut.annotation.from_file
        );
        assert!(
            cut.annotation.to_file.as_str().ends_with("auth.go"),
            "to_file must be the target path, got {}",
            cut.annotation.to_file
        );
    }

    #[test]
    fn cross_language_cycle_produces_scc_cut() {
        let mut graph = CodeGraph::new(SnapshotId::new(1).unwrap());
        let py_id = FileId::new(1).unwrap();
        let go_id = FileId::new(2).unwrap();
        let py_idx = graph.add_node(NodeData::File(FileNode::new(
            py_id,
            PathBuf::from("orch.py"),
            LangId::Python,
            SnapshotId::new(1).unwrap(),
        )));
        let go_idx = graph.add_node(NodeData::File(FileNode::new(
            go_id,
            PathBuf::from("auth.go"),
            LangId::Go,
            SnapshotId::new(1).unwrap(),
        )));
        graph.file_to_index.insert(py_id, py_idx);
        graph.file_to_index.insert(go_id, go_idx);

        graph.add_edge_normalized(py_idx, go_idx, EdgeKind::Import, 1.0);
        graph.add_edge_normalized(go_idx, py_idx, EdgeKind::Import, 1.0);

        let scc = SccAnalysis::analyze(graph.graph());
        let mut file_languages: HashMap<FileId, LangId> = HashMap::new();
        for (&fid, &idx) in &graph.file_to_index {
            if let NodeData::File(f) = &graph.graph()[idx] {
                file_languages.insert(fid, f.language);
            }
        }
        let partition = partition_into_pods(&graph);
        let cuts = find_cross_language_cuts(&scc, &graph, &file_languages, &partition);
        let cut = cuts
            .into_iter()
            .find(|c| matches!(c.annotation.cut_reason, CutReason::CrossLanguageScc))
            .expect("cross-language cycle must produce a CrossLanguageScc cut");
        assert!(matches!(
            cut.annotation.cut_reason,
            CutReason::CrossLanguageScc
        ));
    }
}