gitstack 5.3.0

//! Graph construction logic

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

use super::cell::GraphCell;
use super::colors::{ColorContext, PenaltyBasedColorAssigner};
use super::layout::{GraphLayout, GraphRow};
use crate::event::{GitEvent, GitEventKind};

/// Column tracking manager
struct ColumnTracker {
    /// Commit hash being tracked by each column (None means empty column)
    columns: Vec<Option<String>>,
    /// Hash -> color index mapping
    hash_colors: HashMap<String, usize>,
    /// Column -> color index mapping
    column_colors: HashMap<usize, usize>,
    /// Color assignment manager (penalty-based)
    color_assigner: PenaltyBasedColorAssigner,
    /// Commit hash -> fork point hash (for fork point detection)
    fork_points: HashMap<String, String>,
}

impl ColumnTracker {
    fn new() -> Self {
        Self {
            columns: Vec::new(),
            hash_colors: HashMap::new(),
            column_colors: HashMap::new(),
            color_assigner: PenaltyBasedColorAssigner::new(),
            fork_points: HashMap::new(),
        }
    }

    /// Find the column tracking the specified hash
    fn find_column(&self, hash: &str) -> Option<usize> {
        self.columns
            .iter()
            .position(|h| h.as_ref().is_some_and(|h| h == hash))
    }

    /// Find an empty column or create a new one
    fn find_or_create_column(&mut self) -> usize {
        if let Some(pos) = self.columns.iter().position(|h| h.is_none()) {
            pos
        } else {
            self.columns.push(None);
            self.columns.len() - 1
        }
    }

    /// Release a column
    fn release_column(&mut self, col: usize) {
        if col < self.columns.len() {
            self.columns[col] = None;
            self.column_colors.remove(&col);
            self.color_assigner.release_lane(col);
        }
    }

    /// Set a hash to a column
    fn set_column(&mut self, col: usize, hash: String, color_idx: usize) {
        while self.columns.len() <= col {
            self.columns.push(None);
        }
        self.columns[col] = Some(hash.clone());
        self.hash_colors.insert(hash, color_idx);
        self.column_colors.insert(col, color_idx);
    }

    /// Get the color of a column
    fn get_column_color(&self, col: usize) -> Option<usize> {
        self.column_colors.get(&col).copied()
    }

    /// Get the color of a hash
    fn get_hash_color(&self, hash: &str) -> Option<usize> {
        self.hash_colors.get(hash).copied()
    }

    /// Assign main branch color
    fn assign_main_color(&mut self, col: usize) -> usize {
        let ctx = ColorContext::new(col).with_main_branch(true);
        self.color_assigner.assign_with_context(&ctx)
    }

    /// Assign color considering context
    fn assign_color_with_context(
        &mut self,
        col: usize,
        fork_point: Option<String>,
        parent_color: Option<usize>,
    ) -> usize {
        let ctx = ColorContext::new(col)
            .with_fork_point(fork_point)
            .with_parent_color(parent_color);
        self.color_assigner.assign_with_context(&ctx)
    }

    /// Record a fork point
    fn set_fork_point(&mut self, hash: &str, fork_point: &str) {
        self.fork_points
            .insert(hash.to_string(), fork_point.to_string());
    }

    /// Get the fork point
    fn get_fork_point(&self, hash: &str) -> Option<String> {
        self.fork_points.get(hash).cloned()
    }

    /// Maximum index of active columns
    fn max_active_column(&self) -> usize {
        self.columns
            .iter()
            .enumerate()
            .filter(|(_, h)| h.is_some())
            .map(|(i, _)| i)
            .max()
            .unwrap_or(0)
    }
}

/// Build the graph
pub fn build_graph(events: &[GitEvent], head_hash: Option<&str>) -> GraphLayout {
    if events.is_empty() {
        return GraphLayout::empty();
    }

    let mut tracker = ColumnTracker::new();
    let mut rows: Vec<GraphRow> = Vec::new();
    let mut max_column: usize = 0;

    // Hash -> row index mapping
    let hash_to_idx: HashMap<&str, usize> = events
        .iter()
        .enumerate()
        .map(|(i, e)| (e.short_hash.as_str(), i))
        .collect();

    // Hashes of already displayed commits
    let mut shown_commits: HashSet<String> = HashSet::new();

    for (idx, event) in events.iter().enumerate() {
        // Fork point detection: when multiple columns are tracking the same commit,
        // insert a connector row to visualize the convergence
        let converging_columns: Vec<usize> = tracker
            .columns
            .iter()
            .enumerate()
            .filter(|(_, h)| h.as_ref().is_some_and(|h| h == &event.short_hash))
            .map(|(i, _)| i)
            .collect();

        if converging_columns.len() >= 2 {
            // Multiple columns converging: insert a connector row
            // SAFETY: converging_columns.len() >= 2 is guaranteed by the preceding if condition
            let main_col = *converging_columns
                .iter()
                .min()
                .expect("converging_columns is non-empty (len >= 2)");
            let merging_cols: Vec<usize> = converging_columns
                .iter()
                .filter(|&&c| c != main_col)
                .copied()
                .collect();

            // Update maximum column count
            for &col in &merging_cols {
                max_column = max_column.max(col);
            }
            max_column = max_column.max(main_col);

            // Build cells for the connector row
            let connector_cells = build_connector_cells(
                main_col,
                &merging_cols,
                &tracker.columns,
                &tracker.column_colors,
                max_column,
            );

            // Add connector row (no commit information)
            let main_color = tracker.get_column_color(main_col).unwrap_or(0);
            rows.push(GraphRow::new(None, main_col, main_color, connector_cells));

            // Release converged columns (except the main column)
            for col in merging_cols {
                tracker.release_column(col);
            }
        }

        // Find the column tracking this commit
        let commit_col = tracker
            .find_column(&event.short_hash)
            .unwrap_or_else(|| tracker.find_or_create_column());

        // Detect fork point (set if first parent exists)
        if let Some(first_parent) = event.parent_hashes.first() {
            tracker.set_fork_point(&event.short_hash, first_parent);
        }

        // Determine color
        let commit_color = if idx == 0 {
            // First commit (main branch)
            let color = tracker.assign_main_color(commit_col);
            tracker.set_column(commit_col, event.short_hash.clone(), color);
            color
        } else if let Some(color) = tracker.get_column_color(commit_col) {
            // Continue with the existing column's color
            color
        } else {
            // Assign a new color (considering fork point)
            let fork_point = tracker.get_fork_point(&event.short_hash);
            let parent_color = if let Some(first_parent) = event.parent_hashes.first() {
                tracker.get_hash_color(first_parent)
            } else {
                None
            };
            let color = tracker.assign_color_with_context(commit_col, fork_point, parent_color);
            tracker.set_column(commit_col, event.short_hash.clone(), color);
            color
        };

        // Clear this column (commit processing complete)
        if commit_col < tracker.columns.len() {
            tracker.columns[commit_col] = None;
        }

        // Process parent commits
        // (column, color, is being tracked, already shown)
        let mut parent_info: Vec<(usize, usize, bool, bool)> = Vec::new();

        for (parent_idx, parent_hash) in event.parent_hashes.iter().enumerate() {
            // Check if the parent is within the display range
            let in_display_range = hash_to_idx.contains_key(parent_hash.as_str());

            if !in_display_range {
                // Even if parent is outside display range, continue tracking the first parent in the same column (to maintain vertical line)
                if parent_idx == 0 {
                    tracker.set_column(commit_col, parent_hash.clone(), commit_color);
                }
                continue;
            }

            // Find the column tracking the parent
            let existing_col = tracker.find_column(parent_hash);

            // Whether the parent has already been displayed
            let already_shown = shown_commits.contains(parent_hash);

            let (parent_col, parent_color, is_existing) = if let Some(col) = existing_col {
                // An existing column is tracking the parent
                let color = tracker
                    .get_column_color(col)
                    .or_else(|| tracker.get_hash_color(parent_hash))
                    .unwrap_or(col);

                if parent_idx == 0 && col != commit_col {
                    // First parent is being tracked in a different column (branch commit)
                    // -> Start tracking in the current column too (for fork point detection)
                    tracker.set_column(commit_col, parent_hash.clone(), commit_color);
                    // -> Do not draw a horizontal line (return commit_col)
                    //    Fork points are visualized by connector rows
                    (commit_col, commit_color, true)
                } else {
                    // Second parent onwards (merge source), or same column
                    // -> Draw a horizontal line
                    (col, color, true)
                }
            } else if parent_idx == 0 {
                // First parent: continue in the same column
                tracker.set_column(commit_col, parent_hash.clone(), commit_color);
                (commit_col, commit_color, false)
            } else {
                // Second parent onwards: new column (considering fork point)
                let new_col = tracker.find_or_create_column();
                // Record the current commit as the fork point for second parent onwards
                let fork_point = Some(event.short_hash.clone());
                let new_color = tracker.assign_color_with_context(new_col, fork_point, None);
                tracker.set_column(new_col, parent_hash.clone(), new_color);
                (new_col, new_color, false)
            };

            parent_info.push((parent_col, parent_color, is_existing, already_shown));
        }

        // Update maximum column count
        max_column = max_column.max(commit_col).max(tracker.max_active_column());

        // Build cell array
        let cells = build_cells(
            commit_col,
            commit_color,
            &parent_info,
            &tracker.columns,
            &tracker.column_colors,
            max_column,
            event.kind == GitEventKind::Merge,
            head_hash == Some(&event.short_hash),
        );

        // Add row
        let is_head = head_hash == Some(&event.short_hash);
        let row =
            GraphRow::new(Some(event.clone()), commit_col, commit_color, cells).with_head(is_head);
        rows.push(row);

        // Mark this commit as displayed
        shown_commits.insert(event.short_hash.clone());

        // Note: columns are not released here
        // Columns are naturally recycled (cleared during commit processing -> reused by find_or_create_column)
        // Early column release causes a bug where vertical lines disappear when consecutive merges occur
    }

    GraphLayout { rows, max_column }
}

/// Build cell array for a single row
#[allow(clippy::too_many_arguments)]
fn build_cells(
    commit_col: usize,
    commit_color: usize,
    parent_info: &[(usize, usize, bool, bool)], // (column, color, is being tracked, already shown)
    active_columns: &[Option<String>],
    column_colors: &HashMap<usize, usize>,
    max_col: usize,
    is_merge: bool,
    is_head: bool,
) -> Vec<GraphCell> {
    // Cell count: 2 characters per column (one for node and one for spacing)
    let cell_count = (max_col + 1) * 2;
    let mut cells = vec![GraphCell::Empty; cell_count];

    // 1. Draw vertical lines on active columns
    for (col, hash) in active_columns.iter().enumerate() {
        if hash.is_some() && col != commit_col {
            let cell_idx = col * 2;
            if cell_idx < cells.len() {
                // Use the column's color
                let color_idx = column_colors.get(&col).copied().unwrap_or(col % 8);
                cells[cell_idx] = GraphCell::Vertical { color_idx };
            }
        }
    }

    // 2. Draw node at the commit position
    let commit_cell_idx = commit_col * 2;
    if commit_cell_idx < cells.len() {
        cells[commit_cell_idx] = if is_head {
            GraphCell::HeadNode {
                color_idx: commit_color,
            }
        } else if is_merge {
            GraphCell::MergeNode {
                color_idx: commit_color,
            }
        } else {
            GraphCell::Node {
                color_idx: commit_color,
            }
        };
    }

    // 3. Draw connection lines to parents
    for &(parent_col, parent_color, is_existing, already_shown) in parent_info {
        if parent_col == commit_col {
            // Same column: no connection line needed (drawn as vertical line in the next row)
            continue;
        }

        if parent_col > commit_col {
            // Connection to the right
            draw_horizontal_connection(
                &mut cells,
                commit_col,
                parent_col,
                parent_color,
                is_existing,
                already_shown,
                true, // Rightward
            );
        } else {
            // Connection to the left
            draw_horizontal_connection(
                &mut cells,
                parent_col,
                commit_col,
                parent_color,
                is_existing,
                already_shown,
                false, // Leftward
            );
        }
    }

    cells
}

/// Draw horizontal connection lines
fn draw_horizontal_connection(
    cells: &mut [GraphCell],
    left_col: usize,
    right_col: usize,
    color_idx: usize,
    is_existing: bool,
    already_shown: bool,
    is_right_direction: bool, // Whether direction is rightward from the commit
) {
    let start_idx = left_col * 2 + 1;
    let end_idx = right_col * 2;

    // Draw horizontal lines
    for idx in start_idx..end_idx {
        if idx < cells.len() {
            match cells[idx] {
                GraphCell::Vertical { color_idx: v_color } => {
                    // Crossing with vertical line
                    cells[idx] = GraphCell::Cross {
                        h_color: color_idx,
                        v_color,
                    };
                }
                GraphCell::Empty => {
                    cells[idx] = GraphCell::Horizontal { color_idx };
                }
                _ => {}
            }
        }
    }

    // Determine endpoint symbols
    // Based on keifu's logic:
    // - is_existing && already_shown: parent already displayed -> merge end (╯/╰)
    // - is_existing && !already_shown: parent not yet displayed -> tee connection (┤/├)
    // - !is_existing: new branch start -> curve (╮/╭)
    if is_right_direction {
        // Right endpoint symbol
        if end_idx < cells.len() {
            cells[end_idx] = if is_existing && already_shown {
                GraphCell::CurveDownLeft { color_idx } // ╯ merge end
            } else if is_existing {
                GraphCell::TeeLeft { color_idx } // ┤ tee connection (continues below)
            } else {
                GraphCell::CurveUpLeft { color_idx } // ╮ new branch start
            };
        }
    } else {
        // Left endpoint symbol
        let left_idx = left_col * 2;
        if left_idx < cells.len() {
            cells[left_idx] = if is_existing && already_shown {
                GraphCell::CurveDownRight { color_idx } // ╰ merge end
            } else if is_existing {
                GraphCell::TeeRight { color_idx } // ├ tee connection (continues below)
            } else {
                GraphCell::CurveUpRight { color_idx } // ╭ new branch start
            };
        }
    }
}

/// Build cells for fork point connector rows
/// Visualization when multiple columns converge to the same commit
/// Example: ├─┴─╯ (tee from main column, intermediate ┴, rightmost ╯)
fn build_connector_cells(
    main_col: usize,
    merging_cols: &[usize],
    active_columns: &[Option<String>],
    column_colors: &HashMap<usize, usize>,
    max_col: usize,
) -> Vec<GraphCell> {
    let cell_count = (max_col + 1) * 2;
    let mut cells = vec![GraphCell::Empty; cell_count];

    // Sort merging columns (process left to right)
    let mut sorted_merging: Vec<usize> = merging_cols.to_vec();
    sorted_merging.sort();

    // Rightmost merging column
    let rightmost_col = sorted_merging.last().copied().unwrap_or(main_col);

    // 1. Draw vertical lines on active columns (except main and merging columns)
    for (col, hash) in active_columns.iter().enumerate() {
        if hash.is_some() && col != main_col && !sorted_merging.contains(&col) {
            let cell_idx = col * 2;
            if cell_idx < cells.len() {
                let color_idx = column_colors.get(&col).copied().unwrap_or(col % 8);
                cells[cell_idx] = GraphCell::Vertical { color_idx };
            }
        }
    }

    // 2. Draw tee-right (├) on the main column
    let main_color = column_colors.get(&main_col).copied().unwrap_or(0);
    let main_cell_idx = main_col * 2;
    if main_cell_idx < cells.len() {
        cells[main_cell_idx] = GraphCell::TeeRight {
            color_idx: main_color,
        };
    }

    // 3. Draw horizontal lines from main column to each merging column
    for &merge_col in &sorted_merging {
        let merge_color = column_colors
            .get(&merge_col)
            .copied()
            .unwrap_or(merge_col % 8);

        // Horizontal line from main column to merging column
        let start_idx = main_col * 2 + 1;
        let end_idx = merge_col * 2;

        for idx in start_idx..end_idx {
            if idx < cells.len() {
                match cells[idx] {
                    GraphCell::Vertical { color_idx: v_color } => {
                        // Crossing with vertical line
                        cells[idx] = GraphCell::Cross {
                            h_color: merge_color,
                            v_color,
                        };
                    }
                    GraphCell::Empty => {
                        cells[idx] = GraphCell::Horizontal {
                            color_idx: merge_color,
                        };
                    }
                    GraphCell::Horizontal { .. } => {
                        // Keep existing horizontal line as-is
                    }
                    _ => {}
                }
            }
        }

        // Endpoint symbol for merging column
        if end_idx < cells.len() {
            if merge_col == rightmost_col {
                // Rightmost column: ╯ (merge end)
                cells[end_idx] = GraphCell::CurveDownLeft {
                    color_idx: merge_color,
                };
            } else {
                // Intermediate column: ┴ (tee-up, continues rightward)
                cells[end_idx] = GraphCell::TeeUp {
                    color_idx: merge_color,
                };
            }
        }
    }

    cells
}

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

    fn create_event(hash: &str, parents: Vec<&str>) -> GitEvent {
        let mut event = GitEvent::commit(
            hash.to_string(),
            format!("commit {}", hash),
            "author".to_string(),
            Local::now(),
            0,
            0,
        );
        event.parent_hashes = parents.into_iter().map(|s| s.to_string()).collect();
        event
    }

    #[test]
    fn test_build_graph_empty() {
        let layout = build_graph(&[], None);
        assert!(layout.is_empty());
    }

    #[test]
    fn test_build_graph_single_commit() {
        let events = vec![create_event("abc1234", vec![])];
        let layout = build_graph(&events, None);
        assert_eq!(layout.len(), 1);
        assert_eq!(layout.rows[0].column, 0);
    }

    #[test]
    fn test_build_graph_linear_history() {
        let events = vec![
            create_event("commit3", vec!["commit2"]),
            create_event("commit2", vec!["commit1"]),
            create_event("commit1", vec![]),
        ];
        let layout = build_graph(&events, None);
        assert_eq!(layout.len(), 3);
        // All in the same column
        assert_eq!(layout.rows[0].column, 0);
        assert_eq!(layout.rows[1].column, 0);
        assert_eq!(layout.rows[2].column, 0);
    }

    #[test]
    fn test_build_graph_with_merge() {
        // Create a merge commit (with 2 parents)
        let mut merge_event = create_event("merge", vec!["main2", "feat1"]);
        merge_event.kind = GitEventKind::Merge;

        let events = vec![
            merge_event,
            create_event("feat1", vec!["main1"]),
            create_event("main2", vec!["main1"]),
            create_event("main1", vec![]),
        ];
        let layout = build_graph(&events, None);
        // 4 event rows (connector rows may also be added)
        let event_rows: Vec<_> = layout.rows.iter().filter(|r| r.event.is_some()).collect();
        assert_eq!(event_rows.len(), 4);
        // Merge commit should have MergeNode in its cells
        assert!(event_rows[0]
            .cells
            .iter()
            .any(|c| matches!(c, GraphCell::MergeNode { .. })));
    }

    #[test]
    fn test_build_graph_head_marker() {
        let events = vec![create_event("abc1234", vec![])];
        let layout = build_graph(&events, Some("abc1234"));
        assert!(layout.rows[0].is_head);
        assert!(layout.rows[0]
            .cells
            .iter()
            .any(|c| matches!(c, GraphCell::HeadNode { .. })));
    }

    #[test]
    fn test_column_tracker_find_or_create() {
        let mut tracker = ColumnTracker::new();
        let col1 = tracker.find_or_create_column();
        tracker.set_column(col1, "hash1".to_string(), 0);
        let col2 = tracker.find_or_create_column();
        assert_ne!(col1, col2);
    }

    #[test]
    fn test_column_tracker_release() {
        let mut tracker = ColumnTracker::new();
        let col = tracker.find_or_create_column();
        tracker.set_column(col, "hash1".to_string(), 0);
        tracker.release_column(col);
        assert!(tracker.find_column("hash1").is_none());
    }

    /// Test for parallel branches
    ///
    /// Commit history:
    /// ```
    /// merge ─┬─ main2 ─┬─ base
    ///        └─ feat1 ─┘
    /// ```
    #[test]
    fn test_parallel_branches() {
        let mut merge_event = create_event("merge", vec!["main2", "feat1"]);
        merge_event.kind = GitEventKind::Merge;

        let events = vec![
            merge_event,
            create_event("main2", vec!["base"]),
            create_event("feat1", vec!["base"]),
            create_event("base", vec![]),
        ];
        let layout = build_graph(&events, None);
        // 4 event rows (connector rows may also be added)
        let event_rows: Vec<_> = layout.rows.iter().filter(|r| r.event.is_some()).collect();
        assert_eq!(event_rows.len(), 4);

        // main2 and feat1 should be placed in different columns
        let main2_row = event_rows
            .iter()
            .find(|r| r.event.as_ref().is_some_and(|e| e.short_hash == "main2"))
            .unwrap();
        let feat1_row = event_rows
            .iter()
            .find(|r| r.event.as_ref().is_some_and(|e| e.short_hash == "feat1"))
            .unwrap();
        assert_ne!(main2_row.column, feat1_row.column);
    }

    /// Test for fork points (multiple branches diverge from the same commit)
    ///
    /// Commit history:
    /// ```
    /// feat2 ─┐
    /// feat1 ─┼─ base
    /// main  ─┘
    /// ```
    #[test]
    fn test_fork_point() {
        let events = vec![
            create_event("feat2", vec!["base"]),
            create_event("feat1", vec!["base"]),
            create_event("main", vec!["base"]),
            create_event("base", vec![]),
        ];
        let layout = build_graph(&events, None);
        // 4 event rows (connector rows may also be added)
        let event_rows: Vec<_> = layout.rows.iter().filter(|r| r.event.is_some()).collect();
        assert_eq!(event_rows.len(), 4);

        // Commits sharing base as parent are placed in different columns or consolidated into base
        // base should be placed in column 0
        let base_row = event_rows
            .iter()
            .find(|r| r.event.as_ref().is_some_and(|e| e.short_hash == "base"))
            .unwrap();
        assert_eq!(base_row.column, 0);
    }

    /// Test for uniqueness of color assignment
    #[test]
    fn test_color_assignment_unique() {
        let mut merge_event = create_event("merge", vec!["main2", "feat1"]);
        merge_event.kind = GitEventKind::Merge;

        let events = vec![
            merge_event,
            create_event("main2", vec!["base"]),
            create_event("feat1", vec!["base"]),
            create_event("base", vec![]),
        ];
        let layout = build_graph(&events, None);

        // Extract only event rows
        let event_rows: Vec<_> = layout.rows.iter().filter(|r| r.event.is_some()).collect();

        // Get event rows for main2 and feat1
        let main2_row = event_rows
            .iter()
            .find(|r| r.event.as_ref().is_some_and(|e| e.short_hash == "main2"))
            .unwrap();
        let feat1_row = event_rows
            .iter()
            .find(|r| r.event.as_ref().is_some_and(|e| e.short_hash == "feat1"))
            .unwrap();

        // Commits in different columns should have different colors
        // feat1 is placed in a new column, so a different color should be assigned
        if main2_row.column != feat1_row.column {
            assert_ne!(main2_row.color_idx, feat1_row.color_idx);
        }
    }

    /// Test for long merge chains
    #[test]
    fn test_long_merge_chain() {
        let mut merge1 = create_event("merge1", vec!["main3", "feat1"]);
        merge1.kind = GitEventKind::Merge;

        let events = vec![
            merge1,
            create_event("main3", vec!["main2"]),
            create_event("feat1", vec!["main1"]),
            create_event("main2", vec!["main1"]),
            create_event("main1", vec![]),
        ];
        let layout = build_graph(&events, Some("merge1"));
        // 5 event rows (connector rows may also be added)
        let event_rows: Vec<_> = layout.rows.iter().filter(|r| r.event.is_some()).collect();
        assert_eq!(event_rows.len(), 5);

        // Merge commit (first event row) should have HeadNode
        assert!(event_rows[0]
            .cells
            .iter()
            .any(|c| matches!(c, GraphCell::HeadNode { .. })));
    }

    /// Test for horizontal connections
    #[test]
    fn test_horizontal_connection() {
        let mut merge_event = create_event("merge", vec!["main", "feat"]);
        merge_event.kind = GitEventKind::Merge;

        let events = vec![
            merge_event,
            create_event("main", vec!["base"]),
            create_event("feat", vec!["base"]),
            create_event("base", vec![]),
        ];
        let layout = build_graph(&events, None);

        // Merge commit should contain horizontal lines (Horizontal) or curves (Curve)
        let has_connection = layout.rows[0].cells.iter().any(|c| {
            matches!(
                c,
                GraphCell::Horizontal { .. }
                    | GraphCell::CurveUpRight { .. }
                    | GraphCell::CurveUpLeft { .. }
                    | GraphCell::CurveDownRight { .. }
                    | GraphCell::CurveDownLeft { .. }
            )
        });
        assert!(has_connection);
    }

    /// Test for fork point connector rows
    /// When multiple branches diverge from the same commit, connector rows are inserted
    ///
    /// Commit history:
    /// ```
    /// feat2 ─┐
    /// feat1 ─┼─ base
    /// ```
    #[test]
    fn test_convergence_connector_row() {
        // feat1 and feat2 diverge from the same base
        let events = vec![
            create_event("feat2", vec!["base"]),
            create_event("feat1", vec!["base"]),
            create_event("base", vec![]),
        ];
        let layout = build_graph(&events, None);

        // 4 rows: feat2, feat1, connector row, base
        // Row count becomes 4 when a connector row is inserted
        assert_eq!(
            layout.len(),
            4,
            "Expected 4 rows (feat2, feat1, connector, base)"
        );

        // Connector rows should contain TeeRight
        let connector_row = layout.rows.iter().find(|row| row.event.is_none());
        assert!(
            connector_row.is_some(),
            "Expected a connector row (event=None)"
        );

        let connector_row = connector_row.unwrap();
        let has_tee_right = connector_row
            .cells
            .iter()
            .any(|c| matches!(c, GraphCell::TeeRight { .. }));
        assert!(has_tee_right, "Connector row should have TeeRight symbol");

        // The base row must always exist
        let has_base = layout
            .rows
            .iter()
            .any(|row| row.event.as_ref().is_some_and(|e| e.short_hash == "base"));
        assert!(has_base);
    }

    /// Strictly verify the cell layout of connector rows
    /// Connector rows follow the format of TeeRight on the main column, horizontal lines, and CurveDownLeft on the right end
    #[test]
    fn test_connector_row_cell_layout() {
        let events = vec![
            create_event("feat2", vec!["base"]),
            create_event("feat1", vec!["base"]),
            create_event("base", vec![]),
        ];
        let layout = build_graph(&events, None);

        // Get the connector row
        let connector_row = layout
            .rows
            .iter()
            .find(|row| row.event.is_none())
            .expect("Connector row should exist");

        // Convert cell array to string and verify
        let cells_str: String = connector_row.cells.iter().map(|c| c.to_char()).collect();

        // Contains TeeRight
        assert!(
            cells_str.contains('├'),
            "Connector row should contain TeeRight (├): got '{}'",
            cells_str
        );

        // Contains CurveDownLeft (rightmost merging column)
        assert!(
            cells_str.contains('╯'),
            "Connector row should contain CurveDownLeft (╯): got '{}'",
            cells_str
        );
    }

    /// Strictly verify horizontal line connections for merge commits
    /// Merge commits contain horizontal lines to the second parent and curves (CurveUpLeft)
    #[test]
    fn test_merge_commit_horizontal_line() {
        let mut merge_event = create_event("merge", vec!["main", "feat"]);
        merge_event.kind = GitEventKind::Merge;

        let events = vec![
            merge_event,
            create_event("main", vec!["base"]),
            create_event("feat", vec!["base"]),
            create_event("base", vec![]),
        ];
        let layout = build_graph(&events, None);

        // Get the merge row
        let merge_row = layout
            .rows
            .iter()
            .find(|r| r.event.as_ref().is_some_and(|e| e.short_hash == "merge"))
            .expect("Merge row should exist");

        // MergeNode or HeadNode exists
        let has_merge_or_head_node = merge_row
            .cells
            .iter()
            .any(|c| matches!(c, GraphCell::MergeNode { .. } | GraphCell::HeadNode { .. }));
        assert!(has_merge_or_head_node, "Merge row should have MergeNode");

        // Horizontal line exists
        let has_horizontal = merge_row
            .cells
            .iter()
            .any(|c| matches!(c, GraphCell::Horizontal { .. }));
        assert!(
            has_horizontal,
            "Merge row should have Horizontal line for second parent"
        );

        // Curve (CurveUpLeft) exists (new branch start)
        let has_curve = merge_row
            .cells
            .iter()
            .any(|c| matches!(c, GraphCell::CurveUpLeft { .. }));
        assert!(
            has_curve,
            "Merge row should have CurveUpLeft for branch start"
        );
    }

    /// Verify that branch commits do not have horizontal lines
    /// Commits on a branched-off path use only vertical lines in the same column as the parent
    #[test]
    fn test_branch_commit_no_horizontal_line() {
        // feat branch forked from main
        // main: base -> main1
        // feat: base -> feat1 (branch commit)
        let events = vec![
            create_event("feat1", vec!["base"]),
            create_event("main1", vec!["base"]),
            create_event("base", vec![]),
        ];
        let layout = build_graph(&events, None);

        // Get the feat1 row
        let feat1_row = layout
            .rows
            .iter()
            .find(|r| r.event.as_ref().is_some_and(|e| e.short_hash == "feat1"))
            .expect("feat1 row should exist");

        // feat1 row should not have horizontal lines
        // Branch commits do not draw horizontal lines
        let has_horizontal = feat1_row
            .cells
            .iter()
            .any(|c| matches!(c, GraphCell::Horizontal { .. }));
        assert!(
            !has_horizontal,
            "Branch commit should NOT have Horizontal line"
        );
    }

    /// Verify that vertical lines continue even when a parent is outside the display range
    #[test]
    fn test_parent_outside_display_range() {
        // commit2's parent commit1 is within the display range, but commit1's parent is outside
        let events = vec![
            create_event("commit2", vec!["commit1"]),
            create_event("commit1", vec!["outside_parent"]), // outside_parent is out of range
        ];
        let layout = build_graph(&events, None);

        assert_eq!(layout.len(), 2);

        // Vertical line continues even on commit1's row (column is being tracked)
        // The column is tracked even when the parent is outside the range
        let commit1_row = layout
            .rows
            .iter()
            .find(|r| r.event.as_ref().is_some_and(|e| e.short_hash == "commit1"))
            .expect("commit1 row should exist");

        // commit1 is placed in column 0
        assert_eq!(commit1_row.column, 0);
    }

    /// Test for three or more parallel branches
    #[test]
    fn test_three_parallel_branches() {
        let mut merge = create_event("merge", vec!["main3", "feat1", "feat2"]);
        merge.kind = GitEventKind::Merge;

        let events = vec![
            merge,
            create_event("main3", vec!["main2"]),
            create_event("feat1", vec!["main1"]),
            create_event("feat2", vec!["main1"]),
            create_event("main2", vec!["main1"]),
            create_event("main1", vec![]),
        ];
        let layout = build_graph(&events, None);

        // There should be 6 event rows
        let event_rows: Vec<_> = layout.rows.iter().filter(|r| r.event.is_some()).collect();
        assert_eq!(event_rows.len(), 6);

        // Maximum column count should be at least 2 (3 parallel branches)
        assert!(
            layout.max_column >= 2,
            "Should have at least 3 columns for 3 parallel branches"
        );
    }

    /// In linear history, all commits are placed in the same column
    #[test]
    fn test_linear_history_same_column() {
        let events = vec![
            create_event("c5", vec!["c4"]),
            create_event("c4", vec!["c3"]),
            create_event("c3", vec!["c2"]),
            create_event("c2", vec!["c1"]),
            create_event("c1", vec![]),
        ];
        let layout = build_graph(&events, None);

        // All commits should be in column 0
        for row in &layout.rows {
            assert_eq!(
                row.column, 0,
                "All commits in linear history should be in column 0"
            );
        }

        // No connector rows (no branches)
        let connector_count = layout.rows.iter().filter(|r| r.event.is_none()).count();
        assert_eq!(
            connector_count, 0,
            "Linear history should have no connector rows"
        );
    }

    /// Verify that vertical line colors are correct
    #[test]
    fn test_vertical_line_colors() {
        let mut merge = create_event("merge", vec!["main", "feat"]);
        merge.kind = GitEventKind::Merge;

        let events = vec![
            merge,
            create_event("feat", vec!["base"]),
            create_event("main", vec!["base"]),
            create_event("base", vec![]),
        ];
        let layout = build_graph(&events, None);

        // Verify vertical line colors in each row
        for row in layout.rows.iter().filter(|r| r.event.is_some()) {
            for cell in &row.cells {
                if let GraphCell::Vertical { color_idx } = cell {
                    // Color index is within valid range
                    assert!(*color_idx < 8, "Color index should be < 8");
                }
            }
        }
    }

    /// Verify that cross cells are generated correctly
    #[test]
    fn test_cross_generation() {
        // Case where crossing occurs in a complex merge
        // main: base -> main1 -> main2
        // feat1: base -> feat1
        // feat2: base -> feat2
        // merge: main2 + feat1 + feat2
        let mut merge = create_event("merge", vec!["main2", "feat1", "feat2"]);
        merge.kind = GitEventKind::Merge;

        let events = vec![
            merge,
            create_event("main2", vec!["main1"]),
            create_event("feat1", vec!["base"]),
            create_event("feat2", vec!["base"]),
            create_event("main1", vec!["base"]),
            create_event("base", vec![]),
        ];
        let layout = build_graph(&events, None);

        // Check if cross cells exist
        // Note: whether crossing occurs depends on the configuration
        let has_cross = layout
            .rows
            .iter()
            .any(|r| r.cells.iter().any(|c| matches!(c, GraphCell::Cross { .. })));

        // If crossing exists, h_color and v_color should be set
        if has_cross {
            for row in &layout.rows {
                for cell in &row.cells {
                    if let GraphCell::Cross { h_color, v_color } = cell {
                        assert!(*h_color < 8, "h_color should be valid");
                        assert!(*v_color < 8, "v_color should be valid");
                    }
                }
            }
        }
    }

    /// Verify column release after merge
    #[test]
    fn test_column_release_after_merge() {
        let mut merge1 = create_event("merge1", vec!["main2", "feat1"]);
        merge1.kind = GitEventKind::Merge;

        let events = vec![
            merge1,
            create_event("feat1", vec!["main1"]),
            create_event("main2", vec!["main1"]),
            create_event("main1", vec![]),
            create_event("after_merge", vec!["main1"]), // Commit after merge
        ];
        let layout = build_graph(&events, None);

        // After merge, columns are released and reused
        // max_column should not grow excessively
        assert!(
            layout.max_column <= 2,
            "Columns should be reused after merge"
        );
    }

    /// Verify that node types are set correctly
    #[test]
    fn test_node_types() {
        let mut merge = create_event("merge", vec!["main", "feat"]);
        merge.kind = GitEventKind::Merge;

        let events = vec![
            merge,
            create_event("main", vec!["base"]),
            create_event("base", vec![]),
        ];

        // Without HEAD
        let layout_no_head = build_graph(&events, None);
        let merge_row = layout_no_head
            .rows
            .iter()
            .find(|r| r.event.as_ref().is_some_and(|e| e.short_hash == "merge"))
            .unwrap();
        assert!(
            merge_row
                .cells
                .iter()
                .any(|c| matches!(c, GraphCell::MergeNode { .. })),
            "Merge commit without HEAD should have MergeNode"
        );

        // With HEAD
        let layout_with_head = build_graph(&events, Some("merge"));
        let merge_row_head = layout_with_head
            .rows
            .iter()
            .find(|r| r.event.as_ref().is_some_and(|e| e.short_hash == "merge"))
            .unwrap();
        assert!(
            merge_row_head
                .cells
                .iter()
                .any(|c| matches!(c, GraphCell::HeadNode { .. })),
            "Merge commit with HEAD should have HeadNode"
        );

        // Normal commit
        let normal_row = layout_no_head
            .rows
            .iter()
            .find(|r| r.event.as_ref().is_some_and(|e| e.short_hash == "main"))
            .unwrap();
        assert!(
            normal_row
                .cells
                .iter()
                .any(|c| matches!(c, GraphCell::Node { .. })),
            "Normal commit should have Node"
        );
    }

    /// Verify TeeLeft generation
    #[test]
    fn test_tee_left_generation() {
        let mut merge = create_event("merge", vec!["main", "feat"]);
        merge.kind = GitEventKind::Merge;

        let events = vec![
            merge,
            // Place feat first and connect merge leftward
            create_event("feat", vec!["base"]),
            create_event("main", vec!["base"]),
            create_event("base", vec![]),
        ];
        let layout = build_graph(&events, None);

        // TeeLeft or CurveUpLeft should exist
        let has_tee_or_curve = layout.rows.iter().any(|r| {
            r.cells
                .iter()
                .any(|c| matches!(c, GraphCell::TeeLeft { .. } | GraphCell::CurveUpLeft { .. }))
        });
        assert!(
            has_tee_or_curve,
            "Should have TeeLeft or CurveUpLeft for rightward connection"
        );
    }

    /// Verify no panic with empty event list
    #[test]
    fn test_empty_events_no_panic() {
        let layout = build_graph(&[], None);
        assert!(layout.is_empty());
        assert_eq!(layout.max_column, 0);
    }

    /// Verify no panic with a single commit
    #[test]
    fn test_single_commit_no_panic() {
        let events = vec![create_event("only", vec![])];
        let layout = build_graph(&events, Some("only"));

        assert_eq!(layout.len(), 1);
        assert!(layout.rows[0].is_head);
        assert!(layout.rows[0]
            .cells
            .iter()
            .any(|c| matches!(c, GraphCell::HeadNode { .. })));
    }

    /// Verify that vertical lines are drawn correctly when consecutive merges occur
    /// (Bug fix in v2.10.3: prevent vertical line disappearance due to early column release)
    #[test]
    fn test_consecutive_merges_vertical_lines_preserved() {
        // Structure:
        // merge2 ─┬─ feat2 ─────────┐
        //         │                 │
        //         └─ main2 ─┬─ merge1
        //                   └─ feat1
        let mut merge2 = create_event("merge2", vec!["main2", "feat2"]);
        merge2.kind = GitEventKind::Merge;
        let mut merge1 = create_event("merge1", vec!["base", "feat1"]);
        merge1.kind = GitEventKind::Merge;

        let events = vec![
            merge2,
            create_event("feat2", vec!["merge1"]),
            create_event("main2", vec!["merge1"]),
            merge1,
            create_event("feat1", vec!["base"]),
            create_event("base", vec![]),
        ];
        let layout = build_graph(&events, None);

        // If connector rows exist between feat2 and main2, check for vertical lines
        // Count vertical line cells across all rows
        let mut vertical_count = 0;
        for row in &layout.rows {
            for cell in &row.cells {
                if matches!(cell, GraphCell::Vertical { .. }) {
                    vertical_count += 1;
                }
            }
        }

        // Confirm vertical lines are drawn properly (non-zero is OK)
        assert!(
            vertical_count > 0,
            "Vertical lines should be preserved between consecutive merges"
        );

        // Also confirm columns do not grow excessively
        assert!(
            layout.max_column <= 3,
            "Columns should be reused efficiently, got max_column={}",
            layout.max_column
        );
    }

    /// Verify that 10 or more parallel branches are drawn correctly
    #[test]
    fn test_many_parallel_branches() {
        // Structure: 12 branches fork from the same base and eventually merge
        //
        // final_merge ─┬─ branch01 ─┐
        //              ├─ branch02 ─┤
        //              ├─ branch03 ─┤
        //              ├─ branch04 ─┤
        //              ├─ branch05 ─┤
        //              ├─ branch06 ─┤
        //              ├─ branch07 ─┤
        //              ├─ branch08 ─┤
        //              ├─ branch09 ─┤
        //              ├─ branch10 ─┤
        //              ├─ branch11 ─┤
        //              └─ branch12 ─┴─ base

        let mut events = vec![];

        // final_merge: merge 12 branches
        let mut final_merge = create_event(
            "final",
            vec![
                "branch01", "branch02", "branch03", "branch04", "branch05", "branch06", "branch07",
                "branch08", "branch09", "branch10", "branch11", "branch12",
            ],
        );
        final_merge.kind = GitEventKind::Merge;
        events.push(final_merge);

        // Each branch (all having the same base as parent)
        for i in 1..=12 {
            events.push(create_event(&format!("branch{:02}", i), vec!["base"]));
        }

        // base commit
        events.push(create_event("base", vec![]));

        let layout = build_graph(&events, None);

        // Confirm completion without panic
        assert!(!layout.rows.is_empty());

        // Confirm each branch is placed in a different column
        let mut branch_columns: Vec<usize> = vec![];
        for row in &layout.rows {
            if let Some(ref event) = row.event {
                if event.short_hash.starts_with("branch") {
                    branch_columns.push(row.column);
                }
            }
        }
        // 12 branch columns should exist
        assert_eq!(branch_columns.len(), 12);

        // max_column should be at least 11 (columns 0-11 for 12 branches)
        assert!(
            layout.max_column >= 11,
            "Expected at least 12 columns for 12 parallel branches, got max_column={}",
            layout.max_column
        );
    }

    /// Verify that complex cross patterns are drawn correctly
    #[test]
    fn test_complex_cross_pattern() {
        // Structure: pattern where left and right branches cross
        //
        // merge_left ─┬─ left_branch ─────┬─ base
        //             └─ middle ─┬─ right_branch
        //                        └─ right2
        //
        // Lines of left_branch and right_branch cross each other

        let mut merge_left = create_event("merge_left", vec!["left_branch", "middle"]);
        merge_left.kind = GitEventKind::Merge;

        let mut middle = create_event("middle", vec!["right_branch", "right2"]);
        middle.kind = GitEventKind::Merge;

        let events = vec![
            merge_left,
            create_event("left_branch", vec!["base"]),
            middle,
            create_event("right_branch", vec!["base"]),
            create_event("right2", vec!["base"]),
            create_event("base", vec![]),
        ];

        let layout = build_graph(&events, None);

        // Completed without panic
        assert!(!layout.rows.is_empty());

        // Check if cross cells exist (when crossing occurs)
        let has_any_horizontal = layout.rows.iter().any(|row| {
            row.cells.iter().any(|c| {
                matches!(
                    c,
                    GraphCell::Horizontal { .. }
                        | GraphCell::Cross { .. }
                        | GraphCell::TeeLeft { .. }
                        | GraphCell::TeeRight { .. }
                )
            })
        });
        // Merges should have horizontal connection cells
        assert!(
            has_any_horizontal,
            "Complex merge pattern should have horizontal connections"
        );
    }

    /// Verify correct behavior with color wraparound for branches exceeding 16 colors
    #[test]
    fn test_color_wraparound_with_many_branches() {
        // Create 20 branches (exceeding the 16-color palette)
        let events: Vec<GitEvent> = (1..=20)
            .map(|i| {
                let hash = format!("commit{:02}", i);
                let parent = if i == 1 {
                    vec![]
                } else {
                    vec![format!("commit{:02}", i - 1)]
                };
                let mut event = GitEvent::commit(
                    hash.clone(),
                    format!("commit {}", hash),
                    "author".to_string(),
                    Local::now(),
                    0,
                    0,
                );
                event.parent_hashes = parent;
                event
            })
            .collect();

        let layout = build_graph(&events, None);

        // Completed without panic
        assert_eq!(layout.rows.len(), 20);

        // Confirm color indices are within palette size
        for row in &layout.rows {
            assert!(
                row.color_idx < 16,
                "Color index {} should be within palette size",
                row.color_idx
            );
        }
    }

    /// Verify that deeply nested merges are handled correctly
    #[test]
    fn test_deeply_nested_merges() {
        // Structure: chain of consecutive merges
        //
        // merge5 ─┬─ merge4 ─┬─ merge3 ─┬─ merge2 ─┬─ merge1 ─┬─ main
        //         │          │          │          │          └─ branch1
        //         │          │          │          └─ branch2
        //         │          │          └─ branch3
        //         │          └─ branch4
        //         └─ branch5

        let mut events = vec![];

        for i in (1..=5).rev() {
            let parent1 = if i == 1 {
                "main".to_string()
            } else {
                format!("merge{}", i - 1)
            };
            let parent2 = format!("branch{}", i);
            let mut merge = create_event(&format!("merge{}", i), vec![]);
            merge.parent_hashes = vec![parent1, parent2];
            merge.kind = GitEventKind::Merge;
            events.push(merge);
        }

        for i in (1..=5).rev() {
            events.push(create_event(&format!("branch{}", i), vec!["base"]));
        }
        events.push(create_event("main", vec!["base"]));
        events.push(create_event("base", vec![]));

        let layout = build_graph(&events, None);

        // Completed without panic
        assert!(!layout.rows.is_empty());

        // Confirm 5 merge nodes exist
        let merge_count = layout
            .rows
            .iter()
            .filter(|row| {
                row.cells
                    .iter()
                    .any(|c| matches!(c, GraphCell::MergeNode { .. }))
            })
            .count();
        assert_eq!(merge_count, 5, "Should have 5 merge nodes");
    }

    /// Verify that lines are not broken even when diamond patterns (branch then merge) occur consecutively
    #[test]
    fn test_diamond_pattern_chain() {
        // Structure: 3 consecutive diamond patterns
        //
        // merge3 ─┬─ feat3 ─┬─ merge2 ─┬─ feat2 ─┬─ merge1 ─┬─ feat1 ─┬─ base
        //         └─────────┘          └─────────┘          └─────────┘
        //
        // Each diamond involves branching, parallel development, and merging

        let mut events = vec![];

        // 3 diamond patterns
        for i in (1..=3).rev() {
            let parent = if i == 3 {
                "base".to_string()
            } else {
                format!("merge{}", i + 1)
            };

            // Merge commit
            let mut merge = create_event(&format!("merge{}", i), vec![]);
            merge.parent_hashes = vec![format!("feat{}", i), parent.clone()];
            merge.kind = GitEventKind::Merge;
            events.push(merge);

            // Feature branch
            events.push(create_event(&format!("feat{}", i), vec![&parent]));
        }

        events.push(create_event("base", vec![]));

        let layout = build_graph(&events, None);

        // Completed without panic
        assert!(!layout.rows.is_empty());

        // 3 merge nodes
        let merge_count = layout
            .rows
            .iter()
            .filter(|row| {
                row.cells
                    .iter()
                    .any(|c| matches!(c, GraphCell::MergeNode { .. }))
            })
            .count();
        assert_eq!(merge_count, 3, "Should have 3 merge nodes");

        // Vertical lines should exist (tree structure is preserved)
        let vertical_count: usize = layout
            .rows
            .iter()
            .map(|row| {
                row.cells
                    .iter()
                    .filter(|c| matches!(c, GraphCell::Vertical { .. }))
                    .count()
            })
            .sum();

        assert!(
            vertical_count > 0,
            "Vertical lines should exist in diamond pattern chain"
        );
    }

    /// Verify that lines are not broken even with alternating merge patterns (merging alternately from left and right)
    #[test]
    fn test_alternating_merge_pattern() {
        // Structure: pattern where merges alternate from left and right
        //
        // final ─┬─ right3 ───────────────────────────┐
        //        │                                    │
        //        └─ merge_r2 ─┬─ left2 ───────────────┼─┐
        //                     │                       │ │
        //                     └─ merge_l1 ─┬─ right1 ─┘ │
        //                                  │            │
        //                                  └─ left1 ────┴─ base

        let mut final_merge = create_event("final", vec!["merge_r2", "right3"]);
        final_merge.kind = GitEventKind::Merge;

        let mut merge_r2 = create_event("merge_r2", vec!["merge_l1", "left2"]);
        merge_r2.kind = GitEventKind::Merge;

        let mut merge_l1 = create_event("merge_l1", vec!["left1", "right1"]);
        merge_l1.kind = GitEventKind::Merge;

        let events = vec![
            final_merge,
            create_event("right3", vec!["base"]),
            merge_r2,
            create_event("left2", vec!["base"]),
            merge_l1,
            create_event("right1", vec!["base"]),
            create_event("left1", vec!["base"]),
            create_event("base", vec![]),
        ];

        let layout = build_graph(&events, None);

        // Completed without panic
        assert!(!layout.rows.is_empty());

        // 3 merge nodes
        let merge_count = layout
            .rows
            .iter()
            .filter(|row| {
                row.cells
                    .iter()
                    .any(|c| matches!(c, GraphCell::MergeNode { .. }))
            })
            .count();
        assert_eq!(merge_count, 3, "Should have 3 merge nodes");

        // All expected commits should exist
        let hashes: Vec<_> = layout
            .rows
            .iter()
            .filter_map(|row| row.event.as_ref().map(|e| e.short_hash.as_str()))
            .collect();

        assert!(hashes.contains(&"final"));
        assert!(hashes.contains(&"right3"));
        assert!(hashes.contains(&"merge_r2"));
        assert!(hashes.contains(&"left2"));
        assert!(hashes.contains(&"merge_l1"));
        assert!(hashes.contains(&"right1"));
        assert!(hashes.contains(&"left1"));
        assert!(hashes.contains(&"base"));
    }

    /// Verify that tree structure is preserved (row order and connectivity)
    #[test]
    fn test_tree_structure_preserved() {
        // Complex tree structure
        //
        // root ─┬─ child1 ─┬─ grandchild1
        //       │          └─ grandchild2
        //       └─ child2 ─┬─ grandchild3
        //                  └─ grandchild4

        let mut root = create_event("root", vec!["child1", "child2"]);
        root.kind = GitEventKind::Merge;

        let mut child1 = create_event("child1", vec!["grandchild1", "grandchild2"]);
        child1.kind = GitEventKind::Merge;

        let mut child2 = create_event("child2", vec!["grandchild3", "grandchild4"]);
        child2.kind = GitEventKind::Merge;

        let events = vec![
            root,
            child1,
            create_event("grandchild1", vec!["base"]),
            create_event("grandchild2", vec!["base"]),
            child2,
            create_event("grandchild3", vec!["base"]),
            create_event("grandchild4", vec!["base"]),
            create_event("base", vec![]),
        ];

        let layout = build_graph(&events, None);

        // Completed without panic
        assert!(!layout.rows.is_empty());

        // All commits should exist
        let event_count = layout.rows.iter().filter(|r| r.event.is_some()).count();
        assert_eq!(event_count, 8, "All 8 commits should be present");

        // Vertical and horizontal lines exist appropriately (tree structure connections)
        let has_vertical = layout.rows.iter().any(|row| {
            row.cells
                .iter()
                .any(|c| matches!(c, GraphCell::Vertical { .. }))
        });
        let has_horizontal = layout.rows.iter().any(|row| {
            row.cells.iter().any(|c| {
                matches!(
                    c,
                    GraphCell::Horizontal { .. }
                        | GraphCell::CurveUpLeft { .. }
                        | GraphCell::CurveUpRight { .. }
                        | GraphCell::CurveDownLeft { .. }
                        | GraphCell::CurveDownRight { .. }
                )
            })
        });

        assert!(has_vertical, "Tree should have vertical connections");
        assert!(has_horizontal, "Tree should have horizontal connections");

        // Columns are used efficiently (not excessively many)
        assert!(
            layout.max_column <= 5,
            "Columns should be reused efficiently, got max_column={}",
            layout.max_column
        );
    }
}