void_graph/graph/

calc.rs

//! Graph calculation for commit visualization.
//!
//! This module is adapted from [Serie](https://github.com/lusingander/serie)
//! by Kyosuke Fujimoto, licensed under the MIT License. The algorithm
//! calculates x,y positions for commits and edges to visualize the commit DAG.
//!
//! Key changes from Serie:
//! - Uses `CommitCid` instead of `CommitHash`
//! - Uses `VoidCommit` instead of git `Commit`
//! - Simplified repository interface via `GraphContext`

use rustc_hash::FxHashMap;

use crate::void_backend::{CommitCid, VoidCommit};

/// Mapping from commit CID to (x, y) position in the graph.
type CommitPosMap<'a> = FxHashMap<&'a CommitCid, (usize, usize)>;

/// Calculated graph structure for rendering.
#[derive(Debug)]
pub struct Graph<'a> {
    /// Commits in display order (y-axis).
    pub commits: &'a [VoidCommit],
    /// Position mapping: CID -> (x, y).
    pub commit_pos_map: CommitPosMap<'a>,
    /// Edges for each row (indexed by y position).
    pub edges: Vec<Vec<Edge>>,
    /// Maximum x position (graph width).
    pub max_pos_x: usize,
}

/// A visual edge segment in the graph.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct Edge {
    /// Type of edge (determines rendering character).
    pub edge_type: EdgeType,
    /// X position of this edge segment.
    pub pos_x: usize,
    /// X position of the associated vertical line (for coloring).
    pub associated_line_pos_x: usize,
}

impl Edge {
    /// Create a new edge.
    pub fn new(edge_type: EdgeType, pos_x: usize, line_pos_x: usize) -> Self {
        Self {
            edge_type,
            pos_x,
            associated_line_pos_x: line_pos_x,
        }
    }
}

/// Edge type determines the character used for rendering.
#[derive(Debug, Clone, Copy, PartialOrd, Ord, PartialEq, Eq, Hash)]
pub enum EdgeType {
    /// Vertical line: │
    Vertical,
    /// Horizontal line: ─
    Horizontal,
    /// Up connector: ╵
    Up,
    /// Down connector: ╷
    Down,
    /// Left connector: ╴
    Left,
    /// Right connector: ╶
    Right,
    /// Right-top corner: ╮
    RightTop,
    /// Right-bottom corner: ╯
    RightBottom,
    /// Left-top corner: ╭
    LeftTop,
    /// Left-bottom corner: ╰
    LeftBottom,
}

impl EdgeType {
    /// Returns true if this edge is part of a vertical line.
    pub fn is_vertically_related(&self) -> bool {
        matches!(self, EdgeType::Vertical | EdgeType::Up | EdgeType::Down)
    }
}

/// Context providing commit relationships for graph calculation.
///
/// This trait abstracts the repository interface so the graph algorithm
/// can work with different commit sources.
pub trait GraphContext {
    /// Get children CIDs for a commit (commits that have this as parent).
    fn children(&self, cid: &CommitCid) -> Vec<&CommitCid>;

    /// Get parent CIDs for a commit.
    fn parents(&self, cid: &CommitCid) -> Vec<&CommitCid>;

    /// Get a commit by CID (returns None if not in the graph).
    fn commit(&self, cid: &CommitCid) -> Option<&VoidCommit>;
}

/// Simple in-memory graph context built from a commit list.
pub struct SimpleGraphContext<'a> {
    /// All commits in the graph.
    commits: &'a [VoidCommit],
    /// CID -> commit index mapping.
    cid_to_index: FxHashMap<&'a CommitCid, usize>,
    /// CID -> children CIDs mapping.
    children_map: FxHashMap<&'a CommitCid, Vec<&'a CommitCid>>,
}

impl<'a> SimpleGraphContext<'a> {
    /// Build a graph context from a slice of commits.
    pub fn new(commits: &'a [VoidCommit]) -> Self {
        let mut cid_to_index = FxHashMap::default();
        let mut children_map: FxHashMap<&CommitCid, Vec<&CommitCid>> = FxHashMap::default();

        // Build index mapping
        for (i, commit) in commits.iter().enumerate() {
            cid_to_index.insert(&commit.cid, i);
        }

        // Build children mapping (reverse of parent relationship)
        for commit in commits {
            for parent_cid in &commit.parents {
                children_map
                    .entry(parent_cid)
                    .or_default()
                    .push(&commit.cid);
            }
        }

        Self {
            commits,
            cid_to_index,
            children_map,
        }
    }
}

impl<'a> GraphContext for SimpleGraphContext<'a> {
    fn children(&self, cid: &CommitCid) -> Vec<&CommitCid> {
        self.children_map.get(cid).cloned().unwrap_or_default()
    }

    fn parents(&self, cid: &CommitCid) -> Vec<&CommitCid> {
        self.cid_to_index
            .get(cid)
            .and_then(|&i| self.commits.get(i))
            .map(|c| c.parents.iter().collect())
            .unwrap_or_default()
    }

    fn commit(&self, cid: &CommitCid) -> Option<&VoidCommit> {
        self.cid_to_index
            .get(cid)
            .and_then(|&i| self.commits.get(i))
    }
}

/// Calculate the graph layout for a list of commits.
pub fn calc_graph<'a>(commits: &'a [VoidCommit], ctx: &'a impl GraphContext) -> Graph<'a> {
    let commit_pos_map = calc_commit_positions(commits, ctx);
    let (edges, max_pos_x) = calc_edges(&commit_pos_map, commits, ctx);

    Graph {
        commits,
        commit_pos_map,
        edges,
        max_pos_x,
    }
}

/// Owned graph structure (no lifetime parameter).
///
/// This allows storing the graph alongside commits without lifetime issues.
#[derive(Debug)]
pub struct OwnedGraph {
    /// Position mapping: CID -> (x, y).
    pub commit_pos_map: FxHashMap<CommitCid, (usize, usize)>,
    /// Edges for each row (indexed by y position).
    pub edges: Vec<Vec<Edge>>,
    /// Maximum x position (graph width).
    pub max_pos_x: usize,
}

/// Calculate graph layout and return an owned structure.
///
/// This is the preferred API for widget use since it doesn't require
/// managing lifetimes between the graph and commit data.
pub fn calc_graph_owned(commits: &[VoidCommit]) -> OwnedGraph {
    let ctx = SimpleGraphContext::new(commits);
    let graph = calc_graph(commits, &ctx);

    OwnedGraph {
        commit_pos_map: graph
            .commit_pos_map
            .into_iter()
            .map(|(k, v)| (k.clone(), v))
            .collect(),
        edges: graph.edges,
        max_pos_x: graph.max_pos_x,
    }
}

/// Calculate x,y positions for each commit.
fn calc_commit_positions<'a>(
    commits: &'a [VoidCommit],
    ctx: &impl GraphContext,
) -> CommitPosMap<'a> {
    let mut commit_pos_map: CommitPosMap = FxHashMap::default();
    let mut commit_line_state: Vec<Option<&CommitCid>> = Vec::new();

    for (pos_y, commit) in commits.iter().enumerate() {
        let filtered_children = filtered_children_cid(commit, ctx);
        if filtered_children.is_empty() {
            // Leaf commit - find first vacant line
            let pos_x = get_first_vacant_line(&commit_line_state);
            add_commit_line(commit, &mut commit_line_state, pos_x);
            commit_pos_map.insert(&commit.cid, (pos_x, pos_y));
        } else {
            // Has children - update line state
            let pos_x = update_commit_line(commit, &mut commit_line_state, &filtered_children);
            commit_pos_map.insert(&commit.cid, (pos_x, pos_y));
        }
    }

    commit_pos_map
}

/// Get children that have this commit as their first parent.
fn filtered_children_cid<'a>(
    commit: &'a VoidCommit,
    ctx: &'a impl GraphContext,
) -> Vec<&'a CommitCid> {
    ctx.children(&commit.cid)
        .into_iter()
        .filter(|child_cid| {
            let child_parents = ctx.parents(child_cid);
            !child_parents.is_empty() && *child_parents[0] == commit.cid
        })
        .collect()
}

/// Find the first vacant position in the line state.
fn get_first_vacant_line(commit_line_state: &[Option<&CommitCid>]) -> usize {
    commit_line_state
        .iter()
        .position(|c| c.is_none())
        .unwrap_or(commit_line_state.len())
}

/// Add a commit to the line state at the given position.
fn add_commit_line<'a>(
    commit: &'a VoidCommit,
    commit_line_state: &mut Vec<Option<&'a CommitCid>>,
    pos_x: usize,
) {
    if commit_line_state.len() <= pos_x {
        commit_line_state.push(Some(&commit.cid));
    } else {
        commit_line_state[pos_x] = Some(&commit.cid);
    }
}

/// Update line state when a commit has children.
fn update_commit_line<'a>(
    commit: &'a VoidCommit,
    commit_line_state: &mut [Option<&'a CommitCid>],
    target_commit_cids: &[&CommitCid],
) -> usize {
    if commit_line_state.is_empty() {
        return 0;
    }

    let mut min_pos_x = commit_line_state.len().saturating_sub(1);

    for target_cid in target_commit_cids {
        for (pos_x, commit_cid) in commit_line_state.iter().enumerate() {
            if let Some(cid) = commit_cid {
                if *cid == *target_cid {
                    commit_line_state[pos_x] = None;
                    if min_pos_x > pos_x {
                        min_pos_x = pos_x;
                    }
                    break;
                }
            }
        }
    }

    commit_line_state[min_pos_x] = Some(&commit.cid);
    min_pos_x
}

/// Internal edge wrapper that tracks the parent commit for overlap detection.
#[derive(Debug, Clone)]
struct WrappedEdge<'a> {
    edge: Edge,
    edge_parent_cid: &'a CommitCid,
}

impl<'a> WrappedEdge<'a> {
    fn new(
        edge_type: EdgeType,
        pos_x: usize,
        line_pos_x: usize,
        edge_parent_cid: &'a CommitCid,
    ) -> Self {
        Self {
            edge: Edge::new(edge_type, pos_x, line_pos_x),
            edge_parent_cid,
        }
    }
}

/// Calculate all edges for the graph.
fn calc_edges<'a>(
    commit_pos_map: &CommitPosMap<'a>,
    commits: &'a [VoidCommit],
    ctx: &impl GraphContext,
) -> (Vec<Vec<Edge>>, usize) {
    let mut max_pos_x = 0;
    let mut edges: Vec<Vec<WrappedEdge<'a>>> = vec![vec![]; commits.len()];

    // First pass: draw commit and branch edges
    for commit in commits {
        let (pos_x, pos_y) = commit_pos_map[&commit.cid];
        let cid = &commit.cid;

        for child_cid in ctx.children(cid) {
            let (child_pos_x, child_pos_y) = commit_pos_map[child_cid];

            if pos_x == child_pos_x {
                // Straight commit line
                draw_vertical_edge(&mut edges, pos_x, pos_y, child_pos_y, cid);
            } else {
                let child_commit = ctx.commit(child_cid);
                let child_first_parent = child_commit.and_then(|c| c.parents.first());

                if child_first_parent == Some(cid) {
                    // Branch edge
                    draw_branch_edge(
                        &mut edges,
                        pos_x,
                        pos_y,
                        child_pos_x,
                        child_pos_y,
                        cid,
                    );
                }
                // Merge edges handled in second pass
            }
        }

        if max_pos_x < pos_x {
            max_pos_x = pos_x;
        }

        // Draw trailing edge if parent not in graph
        if let Some(first_parent) = commit.parents.first() {
            if ctx.commit(first_parent).is_none() {
                edges[pos_y].push(WrappedEdge::new(EdgeType::Down, pos_x, pos_x, cid));
                ((pos_y + 1)..commits.len()).for_each(|y| {
                    edges[y].push(WrappedEdge::new(EdgeType::Vertical, pos_x, pos_x, cid));
                });
            }
        }
    }

    // Second pass: draw merge edges with overlap detection
    for commit in commits {
        let (pos_x, pos_y) = commit_pos_map[&commit.cid];
        let cid = &commit.cid;

        for child_cid in ctx.children(cid) {
            let (child_pos_x, child_pos_y) = commit_pos_map[child_cid];

            if pos_x != child_pos_x {
                let child_commit = ctx.commit(child_cid);
                let child_first_parent = child_commit.and_then(|c| c.parents.first());

                if child_first_parent != Some(cid) {
                    // Merge edge
                    draw_merge_edge(
                        &mut edges,
                        commit_pos_map,
                        commits,
                        pos_x,
                        pos_y,
                        child_pos_x,
                        child_pos_y,
                        cid,
                        &mut max_pos_x,
                    );
                }
            }
        }

        if max_pos_x < pos_x {
            max_pos_x = pos_x;
        }
    }

    // Convert wrapped edges to final edges, sort and deduplicate
    let edges: Vec<Vec<Edge>> = edges
        .into_iter()
        .map(|es| {
            let mut es: Vec<Edge> = es.into_iter().map(|e| e.edge).collect();
            es.sort_by_key(|e| (e.associated_line_pos_x, e.pos_x, e.edge_type));
            es.dedup();
            es
        })
        .collect();

    (edges, max_pos_x)
}

/// Draw a vertical edge between two y positions.
fn draw_vertical_edge<'a>(
    edges: &mut [Vec<WrappedEdge<'a>>],
    pos_x: usize,
    pos_y: usize,
    child_pos_y: usize,
    cid: &'a CommitCid,
) {
    edges[pos_y].push(WrappedEdge::new(EdgeType::Up, pos_x, pos_x, cid));
    for y in ((child_pos_y + 1)..pos_y).rev() {
        edges[y].push(WrappedEdge::new(EdgeType::Vertical, pos_x, pos_x, cid));
    }
    edges[child_pos_y].push(WrappedEdge::new(EdgeType::Down, pos_x, pos_x, cid));
}

/// Draw a branch edge (horizontal + vertical).
fn draw_branch_edge<'a>(
    edges: &mut [Vec<WrappedEdge<'a>>],
    pos_x: usize,
    pos_y: usize,
    child_pos_x: usize,
    child_pos_y: usize,
    cid: &'a CommitCid,
) {
    if pos_x < child_pos_x {
        // Branch goes right
        edges[pos_y].push(WrappedEdge::new(EdgeType::Right, pos_x, child_pos_x, cid));
        for x in (pos_x + 1)..child_pos_x {
            edges[pos_y].push(WrappedEdge::new(EdgeType::Horizontal, x, child_pos_x, cid));
        }
        edges[pos_y].push(WrappedEdge::new(
            EdgeType::RightBottom,
            child_pos_x,
            child_pos_x,
            cid,
        ));
    } else {
        // Branch goes left
        edges[pos_y].push(WrappedEdge::new(EdgeType::Left, pos_x, child_pos_x, cid));
        for x in (child_pos_x + 1)..pos_x {
            edges[pos_y].push(WrappedEdge::new(EdgeType::Horizontal, x, child_pos_x, cid));
        }
        edges[pos_y].push(WrappedEdge::new(
            EdgeType::LeftBottom,
            child_pos_x,
            child_pos_x,
            cid,
        ));
    }

    // Vertical portion
    for y in ((child_pos_y + 1)..pos_y).rev() {
        edges[y].push(WrappedEdge::new(
            EdgeType::Vertical,
            child_pos_x,
            child_pos_x,
            cid,
        ));
    }
    edges[child_pos_y].push(WrappedEdge::new(
        EdgeType::Down,
        child_pos_x,
        child_pos_x,
        cid,
    ));
}

/// Draw a merge edge with overlap detection and detouring.
#[allow(clippy::too_many_arguments)]
fn draw_merge_edge<'a>(
    edges: &mut [Vec<WrappedEdge<'a>>],
    commit_pos_map: &CommitPosMap,
    commits: &'a [VoidCommit],
    pos_x: usize,
    pos_y: usize,
    child_pos_x: usize,
    child_pos_y: usize,
    cid: &'a CommitCid,
    max_pos_x: &mut usize,
) {
    let mut overlap = false;
    let mut new_pos_x = pos_x;

    // Check if we can draw straight or need to detour
    let mut skip_judge_overlap = true;
    for y in (child_pos_y + 1)..pos_y {
        let processing_commit_pos_x = commit_pos_map.get(&commits[y].cid).unwrap().0;
        if processing_commit_pos_x == new_pos_x {
            skip_judge_overlap = false;
            break;
        }
        if edges[y]
            .iter()
            .filter(|e| e.edge.pos_x == pos_x)
            .filter(|e| matches!(e.edge.edge_type, EdgeType::Vertical))
            .any(|e| e.edge_parent_cid != cid)
        {
            skip_judge_overlap = false;
            break;
        }
    }

    if !skip_judge_overlap {
        // Check for overlaps and find detour position
        for y in (child_pos_y + 1)..pos_y {
            let processing_commit_pos_x = commit_pos_map.get(&commits[y].cid).unwrap().0;
            if processing_commit_pos_x == new_pos_x {
                overlap = true;
                if new_pos_x < processing_commit_pos_x + 1 {
                    new_pos_x = processing_commit_pos_x + 1;
                }
            }
            for edge in &edges[y] {
                if edge.edge.pos_x >= new_pos_x
                    && edge.edge_parent_cid != cid
                    && matches!(edge.edge.edge_type, EdgeType::Vertical)
                {
                    overlap = true;
                    if new_pos_x < edge.edge.pos_x + 1 {
                        new_pos_x = edge.edge.pos_x + 1;
                    }
                }
            }
        }
    }

    if overlap {
        // Detour path: go right, up, then left to child
        edges[pos_y].push(WrappedEdge::new(EdgeType::Right, pos_x, pos_x, cid));
        for x in (pos_x + 1)..new_pos_x {
            edges[pos_y].push(WrappedEdge::new(EdgeType::Horizontal, x, pos_x, cid));
        }
        edges[pos_y].push(WrappedEdge::new(
            EdgeType::RightBottom,
            new_pos_x,
            pos_x,
            cid,
        ));
        for y in ((child_pos_y + 1)..pos_y).rev() {
            edges[y].push(WrappedEdge::new(EdgeType::Vertical, new_pos_x, pos_x, cid));
        }
        edges[child_pos_y].push(WrappedEdge::new(EdgeType::RightTop, new_pos_x, pos_x, cid));
        for x in (child_pos_x + 1)..new_pos_x {
            edges[child_pos_y].push(WrappedEdge::new(EdgeType::Horizontal, x, pos_x, cid));
        }
        edges[child_pos_y].push(WrappedEdge::new(EdgeType::Right, child_pos_x, pos_x, cid));

        if *max_pos_x < new_pos_x {
            *max_pos_x = new_pos_x;
        }
    } else {
        // Straight path
        edges[pos_y].push(WrappedEdge::new(EdgeType::Up, pos_x, pos_x, cid));
        for y in ((child_pos_y + 1)..pos_y).rev() {
            edges[y].push(WrappedEdge::new(EdgeType::Vertical, pos_x, pos_x, cid));
        }

        if pos_x < child_pos_x {
            edges[child_pos_y].push(WrappedEdge::new(EdgeType::LeftTop, pos_x, pos_x, cid));
            for x in (pos_x + 1)..child_pos_x {
                edges[child_pos_y].push(WrappedEdge::new(EdgeType::Horizontal, x, pos_x, cid));
            }
            edges[child_pos_y].push(WrappedEdge::new(EdgeType::Left, child_pos_x, pos_x, cid));
        } else {
            edges[child_pos_y].push(WrappedEdge::new(EdgeType::RightTop, pos_x, pos_x, cid));
            for x in (child_pos_x + 1)..pos_x {
                edges[child_pos_y].push(WrappedEdge::new(EdgeType::Horizontal, x, pos_x, cid));
            }
            edges[child_pos_y].push(WrappedEdge::new(EdgeType::Right, child_pos_x, pos_x, cid));
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    fn make_commit(cid: &str, parents: Vec<&str>) -> VoidCommit {
        VoidCommit {
            cid: CommitCid(cid.to_string()),
            parents: parents.into_iter().map(|p| CommitCid(p.to_string())).collect(),
            message: String::new(),
            timestamp_ms: 0,
            is_signed: false,
            signature_valid: None,
            author: None,
        }
    }

    #[test]
    fn test_linear_graph() {
        // c3 -> c2 -> c1
        let commits = vec![
            make_commit("c3", vec!["c2"]),
            make_commit("c2", vec!["c1"]),
            make_commit("c1", vec![]),
        ];
        let ctx = SimpleGraphContext::new(&commits);
        let graph = calc_graph(&commits, &ctx);

        // All commits should be on the same x position (0)
        for commit in &commits {
            let (x, _) = graph.commit_pos_map[&commit.cid];
            assert_eq!(x, 0);
        }
    }

    #[test]
    fn test_branch_graph() {
        // c3 (main) -> c1
        // c2 (branch) -> c1
        let commits = vec![
            make_commit("c3", vec!["c1"]),
            make_commit("c2", vec!["c1"]),
            make_commit("c1", vec![]),
        ];
        let ctx = SimpleGraphContext::new(&commits);
        let graph = calc_graph(&commits, &ctx);

        // c3 and c2 should be on different x positions
        let (x3, _) = graph.commit_pos_map[&commits[0].cid];
        let (x2, _) = graph.commit_pos_map[&commits[1].cid];
        assert_ne!(x3, x2);
    }

    #[test]
    fn test_linear_edges() {
        // Linear: c1 -> c2 -> c3
        let commits = vec![
            make_commit("c1", vec!["c2"]),
            make_commit("c2", vec!["c3"]),
            make_commit("c3", vec![]),
        ];
        let ctx = SimpleGraphContext::new(&commits);
        let graph = calc_graph(&commits, &ctx);

        // Check edges
        println!("edges[0]: {:?}", graph.edges[0]);
        println!("edges[1]: {:?}", graph.edges[1]);
        println!("edges[2]: {:?}", graph.edges[2]);
        println!("max_pos_x: {}", graph.max_pos_x);

        // Row 1 should have a vertical edge at x=0
        assert!(!graph.edges[1].is_empty(), "middle row should have edges");
    }
}