gitstack/graph/

builder.rs

//! グラフ構築ロジック

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

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

/// 列追跡管理
struct ColumnTracker {
    /// 各列が追跡中のコミットハッシュ（Noneは空き列）
    columns: Vec<Option<String>>,
    /// ハッシュ→色インデックスのマッピング
    hash_colors: HashMap<String, usize>,
    /// 列→色インデックスのマッピング
    column_colors: HashMap<usize, usize>,
    /// 色割り当て管理（ペナルティベース）
    color_assigner: PenaltyBasedColorAssigner,
    /// コミットハッシュ→分岐元ハッシュ（fork point検出用）
    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(),
        }
    }

    /// 指定ハッシュを追跡中の列を探す
    fn find_column(&self, hash: &str) -> Option<usize> {
        self.columns
            .iter()
            .position(|h| h.as_ref().is_some_and(|h| h == hash))
    }

    /// 空き列を探すか、新規列を作成
    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
        }
    }

    /// 列を解放
    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);
        }
    }

    /// 列にハッシュを設定
    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);
    }

    /// 列の色を取得
    fn get_column_color(&self, col: usize) -> Option<usize> {
        self.column_colors.get(&col).copied()
    }

    /// ハッシュの色を取得
    fn get_hash_color(&self, hash: &str) -> Option<usize> {
        self.hash_colors.get(hash).copied()
    }

    /// メインブランチ色を割り当て
    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)
    }

    /// コンテキストを考慮して色を割り当て
    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)
    }

    /// 分岐元を記録
    fn set_fork_point(&mut self, hash: &str, fork_point: &str) {
        self.fork_points
            .insert(hash.to_string(), fork_point.to_string());
    }

    /// 分岐元を取得
    fn get_fork_point(&self, hash: &str) -> Option<String> {
        self.fork_points.get(hash).cloned()
    }

    /// アクティブな列の最大インデックス
    fn max_active_column(&self) -> usize {
        self.columns
            .iter()
            .enumerate()
            .filter(|(_, h)| h.is_some())
            .map(|(i, _)| i)
            .max()
            .unwrap_or(0)
    }
}

/// グラフを構築
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;

    // ハッシュ→行インデックスのマッピング
    let hash_to_idx: HashMap<&str, usize> = events
        .iter()
        .enumerate()
        .map(|(i, e)| (e.short_hash.as_str(), i))
        .collect();

    // 既に表示されたコミットのハッシュ
    let mut shown_commits: HashSet<String> = HashSet::new();

    for (idx, event) in events.iter().enumerate() {
        // 分岐点検出：複数の列が同じコミットを追跡している場合
        // コネクタ行を挿入して合流を視覚化
        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 {
            // 複数列が合流：コネクタ行を挿入
            let main_col = *converging_columns.iter().min().unwrap();
            let merging_cols: Vec<usize> = converging_columns
                .iter()
                .filter(|&&c| c != main_col)
                .copied()
                .collect();

            // 最大列数を更新
            for &col in &merging_cols {
                max_column = max_column.max(col);
            }
            max_column = max_column.max(main_col);

            // コネクタ行のセルを構築
            let connector_cells = build_connector_cells(
                main_col,
                &merging_cols,
                &tracker.columns,
                &tracker.column_colors,
                max_column,
            );

            // コネクタ行を追加（コミット情報なし）
            let main_color = tracker.get_column_color(main_col).unwrap_or(0);
            rows.push(GraphRow::new(None, main_col, main_color, connector_cells));

            // 合流した列を解放（メイン列以外）
            for col in merging_cols {
                tracker.release_column(col);
            }
        }

        // このコミットを追跡中の列を探す
        let commit_col = tracker
            .find_column(&event.short_hash)
            .unwrap_or_else(|| tracker.find_or_create_column());

        // 分岐元を検出（第1親があれば設定）
        if let Some(first_parent) = event.parent_hashes.first() {
            tracker.set_fork_point(&event.short_hash, first_parent);
        }

        // 色を決定
        let commit_color = if idx == 0 {
            // 最初のコミット（メインブランチ）
            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) {
            // 既存の列の色を継続
            color
        } else {
            // 新しい色を割り当て（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
        };

        // この列をクリア（コミット処理完了）
        if commit_col < tracker.columns.len() {
            tracker.columns[commit_col] = None;
        }

        // 親コミットの処理
        // (列, 色, 既存追跡中か, 既に表示されたか)
        let mut parent_info: Vec<(usize, usize, bool, bool)> = Vec::new();

        for (parent_idx, parent_hash) in event.parent_hashes.iter().enumerate() {
            // 親が表示範囲内にあるか確認
            let in_display_range = hash_to_idx.contains_key(parent_hash.as_str());

            if !in_display_range {
                // 親が表示範囲外でも、第1親は同じ列で追跡を続ける（縦線継続のため）
                if parent_idx == 0 {
                    tracker.set_column(commit_col, parent_hash.clone(), commit_color);
                }
                continue;
            }

            // 親を追跡中の列を探す
            let existing_col = tracker.find_column(parent_hash);

            // 親が既に表示されたか
            let already_shown = shown_commits.contains(parent_hash);

            let (parent_col, parent_color, is_existing) = if let Some(col) = existing_col {
                // 既存の列が親を追跡している
                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 {
                    // 第1親が別の列で追跡されている場合（分岐コミット）
                    // → 現在の列でも追跡を開始（分岐点検出のため）
                    tracker.set_column(commit_col, parent_hash.clone(), commit_color);
                    // → 横線は描画しない（commit_colを返す）
                    //   分岐点はコネクタ行で視覚化される
                    (commit_col, commit_color, true)
                } else {
                    // 第2親以降（マージ元）、または同じ列の場合
                    // → 横線を描画する
                    (col, color, true)
                }
            } else if parent_idx == 0 {
                // 第1親: 同じ列で継続
                tracker.set_column(commit_col, parent_hash.clone(), commit_color);
                (commit_col, commit_color, false)
            } else {
                // 第2親以降: 新しい列（fork pointを考慮）
                let new_col = tracker.find_or_create_column();
                // 第2親以降は現在のコミットを分岐元として記録
                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));
        }

        // 最大列数を更新
        max_column = max_column.max(commit_col).max(tracker.max_active_column());

        // セル配列を構築
        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),
        );

        // 行を追加
        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);

        // このコミットを表示済みとしてマーク
        shown_commits.insert(event.short_hash.clone());

        // 注: 列解放はここでは行わない
        // 列は自然にリサイクルされる（コミット処理時にクリア → find_or_create_columnで再利用）
        // 早期の列解放は、複数マージが連続する場合に縦線が消えるバグを引き起こす
    }

    GraphLayout { rows, max_column }
}

/// 1行分のセル配列を構築
#[allow(clippy::too_many_arguments)]
fn build_cells(
    commit_col: usize,
    commit_color: usize,
    parent_info: &[(usize, usize, bool, bool)], // (列, 色, 既存追跡中か, 既に表示されたか)
    active_columns: &[Option<String>],
    column_colors: &HashMap<usize, usize>,
    max_col: usize,
    is_merge: bool,
    is_head: bool,
) -> Vec<GraphCell> {
    // セル数: 各列に2文字分（ノード用と間隔用）
    let cell_count = (max_col + 1) * 2;
    let mut cells = vec![GraphCell::Empty; cell_count];

    // 1. アクティブ列に縦線を描画
    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() {
                // 列の色を使用
                let color_idx = column_colors.get(&col).copied().unwrap_or(col % 8);
                cells[cell_idx] = GraphCell::Vertical { color_idx };
            }
        }
    }

    // 2. コミット位置にノードを描画
    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. 親への接続線を描画
    for &(parent_col, parent_color, is_existing, already_shown) in parent_info {
        if parent_col == commit_col {
            // 同じ列: 接続線不要（次の行で縦線として描画）
            continue;
        }

        if parent_col > commit_col {
            // 右への接続
            draw_horizontal_connection(
                &mut cells,
                commit_col,
                parent_col,
                parent_color,
                is_existing,
                already_shown,
                true, // 右向き
            );
        } else {
            // 左への接続
            draw_horizontal_connection(
                &mut cells,
                parent_col,
                commit_col,
                parent_color,
                is_existing,
                already_shown,
                false, // 左向き
            );
        }
    }

    cells
}

/// 横方向の接続線を描画
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, // コミットから見て右方向か
) {
    let start_idx = left_col * 2 + 1;
    let end_idx = right_col * 2;

    // 横線を描画
    for idx in start_idx..end_idx {
        if idx < cells.len() {
            match cells[idx] {
                GraphCell::Vertical { color_idx: v_color } => {
                    // 縦線との交差
                    cells[idx] = GraphCell::Cross {
                        h_color: color_idx,
                        v_color,
                    };
                }
                GraphCell::Empty => {
                    cells[idx] = GraphCell::Horizontal { color_idx };
                }
                _ => {}
            }
        }
    }

    // 端点の記号を決定
    // keifuのロジック参考:
    // - is_existing && already_shown: 親が既に表示済み → マージ終了 (╯/╰)
    // - is_existing && !already_shown: 親がまだ表示されていない → T字接続 (┤/├)
    // - !is_existing: 新しいブランチ開始 → 曲線 (╮/╭)
    if is_right_direction {
        // 右端の記号
        if end_idx < cells.len() {
            cells[end_idx] = if is_existing && already_shown {
                GraphCell::CurveDownLeft { color_idx } // ╯ マージ終了
            } else if is_existing {
                GraphCell::TeeLeft { color_idx } // ┤ T字接続（下に続く）
            } else {
                GraphCell::CurveUpLeft { color_idx } // ╮ 新しいブランチ開始
            };
        }
    } else {
        // 左端の記号
        let left_idx = left_col * 2;
        if left_idx < cells.len() {
            cells[left_idx] = if is_existing && already_shown {
                GraphCell::CurveDownRight { color_idx } // ╰ マージ終了
            } else if is_existing {
                GraphCell::TeeRight { color_idx } // ├ T字接続（下に続く）
            } else {
                GraphCell::CurveUpRight { color_idx } // ╭ 新しいブランチ開始
            };
        }
    }
}

/// 分岐点コネクタ行のセルを構築
/// 複数の列が同じコミットに合流する際の視覚化
/// 例: ├─┴─╯ （メイン列からT字、中間は┴、最右は╯）
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];

    // 合流列をソート（左から右へ処理）
    let mut sorted_merging: Vec<usize> = merging_cols.to_vec();
    sorted_merging.sort();

    // 最右の合流列
    let rightmost_col = sorted_merging.last().copied().unwrap_or(main_col);

    // 1. アクティブ列に縦線を描画（メイン列と合流列以外）
    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. メイン列にT字右（├）を描画
    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. メイン列から各合流列へ横線を描画
    for &merge_col in &sorted_merging {
        let merge_color = column_colors
            .get(&merge_col)
            .copied()
            .unwrap_or(merge_col % 8);

        // メイン列から合流列への横線
        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 } => {
                        // 縦線との交差
                        cells[idx] = GraphCell::Cross {
                            h_color: merge_color,
                            v_color,
                        };
                    }
                    GraphCell::Empty => {
                        cells[idx] = GraphCell::Horizontal {
                            color_idx: merge_color,
                        };
                    }
                    GraphCell::Horizontal { .. } => {
                        // 既に横線がある場合はそのまま
                    }
                    _ => {}
                }
            }
        }

        // 合流列の終端記号
        if end_idx < cells.len() {
            if merge_col == rightmost_col {
                // 最右列は╯（合流終了）
                cells[end_idx] = GraphCell::CurveDownLeft {
                    color_idx: merge_color,
                };
            } else {
                // 中間列は┴（T字上、さらに右へ続く）
                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);
        // 全て同じ列
        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() {
        // マージコミットを作成（2つの親を持つ）
        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つ（コネクタ行が追加される可能性あり）
        let event_rows: Vec<_> = layout.rows.iter().filter(|r| r.event.is_some()).collect();
        assert_eq!(event_rows.len(), 4);
        // マージコミットはセルにMergeNodeを持つ
        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());
    }

    /// 複数ブランチが並行する場合のテスト
    ///
    /// コミット履歴:
    /// ```
    /// 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つ（コネクタ行が追加される可能性あり）
        let event_rows: Vec<_> = layout.rows.iter().filter(|r| r.event.is_some()).collect();
        assert_eq!(event_rows.len(), 4);

        // main2と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();
        assert_ne!(main2_row.column, feat1_row.column);
    }

    /// 分岐点のテスト（同じコミットから複数ブランチが分岐）
    ///
    /// コミット履歴:
    /// ```
    /// 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つ（コネクタ行が追加される可能性あり）
        let event_rows: Vec<_> = layout.rows.iter().filter(|r| r.event.is_some()).collect();
        assert_eq!(event_rows.len(), 4);

        // 全てbaseを親に持つコミットは異なる列またはbaseに統合される
        // baseは列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]
    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);

        // イベント行のみを抽出
        let event_rows: Vec<_> = layout.rows.iter().filter(|r| r.event.is_some()).collect();

        // main2と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();

        // 異なる列のコミットは異なる色を持つはず
        // feat1は新しい列に配置されるので、異なる色が割り当てられる
        if main2_row.column != feat1_row.column {
            assert_ne!(main2_row.color_idx, feat1_row.color_idx);
        }
    }

    /// 長いマージチェーンのテスト
    #[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つ（コネクタ行が追加される可能性あり）
        let event_rows: Vec<_> = layout.rows.iter().filter(|r| r.event.is_some()).collect();
        assert_eq!(event_rows.len(), 5);

        // マージコミット（最初のイベント行）はHeadNodeを持つ
        assert!(event_rows[0]
            .cells
            .iter()
            .any(|c| matches!(c, GraphCell::HeadNode { .. })));
    }

    /// 横線接続のテスト
    #[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);

        // マージコミットは横線（Horizontal）または曲線（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);
    }

    /// 分岐点コネクタ行のテスト
    /// 複数のブランチが同じコミットから分岐する場合、コネクタ行が挿入される
    ///
    /// コミット履歴:
    /// ```
    /// feat2 ─┐
    /// feat1 ─┼─ base
    /// ```
    #[test]
    fn test_convergence_connector_row() {
        // feat1とfeat2が同じbaseから分岐
        let events = vec![
            create_event("feat2", vec!["base"]),
            create_event("feat1", vec!["base"]),
            create_event("base", vec![]),
        ];
        let layout = build_graph(&events, None);

        // feat2, feat1, コネクタ行, base の4行
        // コネクタ行が挿入されている場合、行数が4になる
        assert_eq!(
            layout.len(),
            4,
            "Expected 4 rows (feat2, feat1, connector, base)"
        );

        // コネクタ行があれば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");

        // baseの行は必ず存在
        let has_base = layout
            .rows
            .iter()
            .any(|row| row.event.as_ref().is_some_and(|e| e.short_hash == "base"));
        assert!(has_base);
    }

    /// コネクタ行のセル配置を厳密に検証
    /// コネクタ行は ├─╯ の形式で、メイン列にTeeRight、横線、右端にCurveDownLeft
    #[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);

        // コネクタ行を取得
        let connector_row = layout
            .rows
            .iter()
            .find(|row| row.event.is_none())
            .expect("Connector row should exist");

        // セル配列を文字列に変換して検証
        let cells_str: String = connector_row.cells.iter().map(|c| c.to_char()).collect();

        // TeeRight (├) が含まれる
        assert!(
            cells_str.contains('├'),
            "Connector row should contain TeeRight (├): got '{}'",
            cells_str
        );

        // CurveDownLeft (╯) が含まれる（最右の合流列）
        assert!(
            cells_str.contains('╯'),
            "Connector row should contain CurveDownLeft (╯): got '{}'",
            cells_str
        );
    }

    /// マージコミットの横線接続を厳密に検証
    /// マージコミットは第2親への横線（Horizontal）と曲線（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);

        // マージ行を取得
        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またはHeadNodeが存在
        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）が存在
        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"
        );

        // 曲線（CurveUpLeft）が存在（新しいブランチ開始）
        let has_curve = merge_row
            .cells
            .iter()
            .any(|c| matches!(c, GraphCell::CurveUpLeft { .. }));
        assert!(
            has_curve,
            "Merge row should have CurveUpLeft for branch start"
        );
    }

    /// 分岐コミットでは横線が描画されないことを検証
    /// ブランチを切った先のコミットは親と同じ列で縦線のみ
    #[test]
    fn test_branch_commit_no_horizontal_line() {
        // mainから分岐したfeatブランチ
        // main: base -> main1
        // feat: base -> feat1 (分岐コミット)
        let events = vec![
            create_event("feat1", vec!["base"]),
            create_event("main1", vec!["base"]),
            create_event("base", vec![]),
        ];
        let layout = build_graph(&events, None);

        // feat1の行を取得
        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行には横線（Horizontal）がない
        // 分岐コミットは横線を描画しない
        let has_horizontal = feat1_row
            .cells
            .iter()
            .any(|c| matches!(c, GraphCell::Horizontal { .. }));
        assert!(
            !has_horizontal,
            "Branch commit should NOT have Horizontal line"
        );
    }

    /// 親が表示範囲外の場合でも縦線が継続することを検証
    #[test]
    fn test_parent_outside_display_range() {
        // commit2の親commit1は表示範囲内だが、commit1の親は範囲外
        let events = vec![
            create_event("commit2", vec!["commit1"]),
            create_event("commit1", vec!["outside_parent"]), // outside_parentは範囲外
        ];
        let layout = build_graph(&events, None);

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

        // commit1の行でも縦線が継続している（列が追跡されている）
        // 親が範囲外でも列は追跡される
        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は列0に配置
        assert_eq!(commit1_row.column, 0);
    }

    /// 3つ以上のブランチが並行する場合のテスト
    #[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);

        // イベント行は6つ
        let event_rows: Vec<_> = layout.rows.iter().filter(|r| r.event.is_some()).collect();
        assert_eq!(event_rows.len(), 6);

        // 最大列数が2以上（3つのブランチが並行）
        assert!(
            layout.max_column >= 2,
            "Should have at least 3 columns for 3 parallel branches"
        );
    }

    /// 線形履歴では全てのコミットが同じ列に配置される
    #[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);

        // 全てのコミットが列0
        for row in &layout.rows {
            assert_eq!(
                row.column, 0,
                "All commits in linear history should be in column 0"
            );
        }

        // コネクタ行がない（分岐がない）
        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"
        );
    }

    /// 縦線（Vertical）の色が正しいことを検証
    #[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);

        // 各行の縦線の色を確認
        for row in layout.rows.iter().filter(|r| r.event.is_some()) {
            for cell in &row.cells {
                if let GraphCell::Vertical { color_idx } = cell {
                    // 色インデックスは有効な範囲内
                    assert!(*color_idx < 8, "Color index should be < 8");
                }
            }
        }
    }

    /// Cross（交差）が正しく生成されることを検証
    #[test]
    fn test_cross_generation() {
        // 複雑なマージで交差が発生するケース
        // 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);

        // 交差（Cross）が存在するか確認
        // 注: 交差が発生するかどうかは構成による
        let has_cross = layout
            .rows
            .iter()
            .any(|r| r.cells.iter().any(|c| matches!(c, GraphCell::Cross { .. })));

        // 交差がある場合、h_colorとv_colorが設定されている
        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");
                    }
                }
            }
        }
    }

    /// マージ後の列解放を検証
    #[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"]), // マージ後のコミット
        ];
        let layout = build_graph(&events, None);

        // マージ後は列が解放され、再利用される
        // max_columnが過度に大きくならない
        assert!(
            layout.max_column <= 2,
            "Columns should be reused after merge"
        );
    }

    /// ノード種別が正しく設定されることを検証
    #[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![]),
        ];

        // 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"
        );

        // 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"
        );

        // 通常コミット
        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"
        );
    }

    /// TeeLeft (┤) の生成を検証
    #[test]
    fn test_tee_left_generation() {
        let mut merge = create_event("merge", vec!["main", "feat"]);
        merge.kind = GitEventKind::Merge;

        let events = vec![
            merge,
            // featを先に配置して左方向にmergeを接続
            create_event("feat", vec!["base"]),
            create_event("main", vec!["base"]),
            create_event("base", vec![]),
        ];
        let layout = build_graph(&events, None);

        // TeeLeft (┤) または CurveUpLeft (╮) が存在
        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"
        );
    }

    /// 空のイベントリストでパニックしないことを検証
    #[test]
    fn test_empty_events_no_panic() {
        let layout = build_graph(&[], None);
        assert!(layout.is_empty());
        assert_eq!(layout.max_column, 0);
    }

    /// 単一コミットでパニックしないことを検証
    #[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 { .. })));
    }

    /// 複数マージが連続する場合、縦線が正しく描画されることを検証
    /// (v2.10.3でのバグ修正: 早期列解放による縦線消失の防止)
    #[test]
    fn test_consecutive_merges_vertical_lines_preserved() {
        // 構造:
        // 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);

        // feat2とmain2の間のコネクタ行があれば、縦線が存在するか確認
        // 全行で縦線セルの数をカウント
        let mut vertical_count = 0;
        for row in &layout.rows {
            for cell in &row.cells {
                if matches!(cell, GraphCell::Vertical { .. }) {
                    vertical_count += 1;
                }
            }
        }

        // 縦線が適切に描画されていることを確認（0でなければOK）
        assert!(
            vertical_count > 0,
            "Vertical lines should be preserved between consecutive merges"
        );

        // 列が過度に大きくならないことも確認
        assert!(
            layout.max_column <= 3,
            "Columns should be reused efficiently, got max_column={}",
            layout.max_column
        );
    }

    /// 10本以上の並列ブランチが正しく描画されることを検証
    #[test]
    fn test_many_parallel_branches() {
        // 構造: 12本のブランチが同じbaseから分岐し、最終的にマージ
        //
        // final_merge ─┬─ branch01 ─┐
        //              ├─ branch02 ─┤
        //              ├─ branch03 ─┤
        //              ├─ branch04 ─┤
        //              ├─ branch05 ─┤
        //              ├─ branch06 ─┤
        //              ├─ branch07 ─┤
        //              ├─ branch08 ─┤
        //              ├─ branch09 ─┤
        //              ├─ branch10 ─┤
        //              ├─ branch11 ─┤
        //              └─ branch12 ─┴─ base

        let mut events = vec![];

        // final_merge: 12本のブランチをマージ
        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);

        // 各ブランチ（全て同じbaseを親に持つ）
        for i in 1..=12 {
            events.push(create_event(&format!("branch{:02}", i), vec!["base"]));
        }

        // base コミット
        events.push(create_event("base", vec![]));

        let layout = build_graph(&events, None);

        // パニックせずに完了することを確認
        assert!(!layout.rows.is_empty());

        // 各ブランチが異なる列に配置されていることを確認
        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本のブランチ列が存在
        assert_eq!(branch_columns.len(), 12);

        // max_columnが少なくとも11（0から11で12列）以上
        assert!(
            layout.max_column >= 11,
            "Expected at least 12 columns for 12 parallel branches, got max_column={}",
            layout.max_column
        );
    }

    /// 複雑な交差パターンが正しく描画されることを検証
    #[test]
    fn test_complex_cross_pattern() {
        // 構造: 左右のブランチが交差するパターン
        //
        // merge_left ─┬─ left_branch ─────┬─ base
        //             └─ middle ─┬─ right_branch
        //                        └─ right2
        //
        // left_branchとright_branchの線が交差する

        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);

        // パニックせずに完了
        assert!(!layout.rows.is_empty());

        // 交差セル（Cross）が存在するか確認（交差がある場合）
        let has_any_horizontal = layout.rows.iter().any(|row| {
            row.cells.iter().any(|c| {
                matches!(
                    c,
                    GraphCell::Horizontal { .. }
                        | GraphCell::Cross { .. }
                        | GraphCell::TeeLeft { .. }
                        | GraphCell::TeeRight { .. }
                )
            })
        });
        // マージがあれば横線関連のセルが存在するはず
        assert!(
            has_any_horizontal,
            "Complex merge pattern should have horizontal connections"
        );
    }

    /// 16色を超えるブランチでもラップアラウンドで正しく動作することを検証
    #[test]
    fn test_color_wraparound_with_many_branches() {
        // 20本のブランチを作成（16色パレットを超える）
        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);

        // パニックせずに完了
        assert_eq!(layout.rows.len(), 20);

        // 色インデックスがパレットサイズ内に収まっていることを確認
        for row in &layout.rows {
            assert!(
                row.color_idx < 16,
                "Color index {} should be within palette size",
                row.color_idx
            );
        }
    }

    /// 深いネストのマージが正しく処理されることを検証
    #[test]
    fn test_deeply_nested_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);

        // パニックせずに完了
        assert!(!layout.rows.is_empty());

        // マージノードが5つ存在することを確認
        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");
    }

    /// ダイヤモンドパターン（分岐→マージ）が連続しても線が途切れないことを検証
    #[test]
    fn test_diamond_pattern_chain() {
        // 構造: ダイヤモンドパターンが3回連続
        //
        // merge3 ─┬─ feat3 ─┬─ merge2 ─┬─ feat2 ─┬─ merge1 ─┬─ feat1 ─┬─ base
        //         └─────────┘          └─────────┘          └─────────┘
        //
        // 各ダイヤモンドで分岐→並行→マージが発生

        let mut events = vec![];

        // 3つのダイヤモンドパターン
        for i in (1..=3).rev() {
            let parent = if i == 3 {
                "base".to_string()
            } else {
                format!("merge{}", i + 1)
            };

            // マージコミット
            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);

            // フィーチャーブランチ
            events.push(create_event(&format!("feat{}", i), vec![&parent]));
        }

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

        let layout = build_graph(&events, None);

        // パニックせずに完了
        assert!(!layout.rows.is_empty());

        // マージノードが3つ
        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");

        // 縦線が存在すること（ツリー構造が保持されている）
        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"
        );
    }

    /// 交互マージパターン（左右から交互にマージ）でも線が途切れないことを検証
    #[test]
    fn test_alternating_merge_pattern() {
        // 構造: 左右から交互にマージされるパターン
        //
        // 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);

        // パニックせずに完了
        assert!(!layout.rows.is_empty());

        // マージノードが3つ
        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");

        // 全ての期待するコミットが存在
        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"));
    }

    /// ツリー構造が保持されることを検証（行の順序と接続性）
    #[test]
    fn test_tree_structure_preserved() {
        // 複雑なツリー構造
        //
        // 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);

        // パニックせずに完了
        assert!(!layout.rows.is_empty());

        // 全コミットが存在
        let event_count = layout.rows.iter().filter(|r| r.event.is_some()).count();
        assert_eq!(event_count, 8, "All 8 commits should be present");

        // 縦線と横線が適切に存在（ツリー構造の接続）
        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");

        // 列が効率的に使用されている（過度に多くない）
        assert!(
            layout.max_column <= 5,
            "Columns should be reused efficiently, got max_column={}",
            layout.max_column
        );
    }
}