[PR #330] Fix: Use BFS to collect all commits in walk_commits_to_base for --rebase-merges support #409

New issue

Closed

opened 2026-03-02 04:13:32 +03:00 by kerem · 0 comments

kerem commented

2026-03-02 04:13:32 +03:00

Owner

Original Pull Request: https://github.com/git-ai-project/git-ai/pull/330

State: closed
Merged: No

Fix: Use BFS to collect all commits in `walk_commits_to_base` for `--rebase-merges` support

Problem

The walk_commits_to_base function only follows parent(0), causing commits from merged branches to be lost during git rebase --rebase-merges. This results in AI authorship data being lost for side branch commits.

Fixes the failing test_rebase_preserve_merges integration test.

Solution

Replace linear traversal with BFS (Breadth-First Search) to traverse all parent commits, ensuring merge commits' second parents are not missed.

Changes

File: src/authorship/rebase_authorship.rs

Before (Lines 823-841):

pub fn walk_commits_to_base(...) {
    let mut commits = Vec::new();
    let mut current = repository.find_commit(head.to_string())?;
    let base_str = base.to_string();

    while current.id().to_string() != base_str {
        commits.push(current.id().to_string());
        current = current.parent(0)?;  // ❌ Only follows first parent
    }

    Ok(commits)
}

After:

pub fn walk_commits_to_base(...) {
    use std::collections::{HashSet, VecDeque};

    let mut commits = Vec::new();
    let mut visited = HashSet::new();
    let mut queue = VecDeque::new();

    let base_str = base.to_string();
    let head_commit = repository.find_commit(head.to_string())?;

    queue.push_back(head_commit);

    while let Some(current) = queue.pop_front() {
        let commit_id = current.id().to_string();

        if commit_id == base_str {
            continue;
        }

        if visited.contains(&commit_id) {
            continue;
        }

        visited.insert(commit_id.clone());
        commits.push(commit_id);

        // ✅ Traverse all parents (handles merge commits)
        let parent_count = current.parent_count().unwrap_or(0);
        for i in 0..parent_count {
            if let Ok(parent) = current.parent(i) {
                queue.push_back(parent);
            }
        }
    }

    Ok(commits)
}

Test Results

Before

$ cargo test test_rebase_preserve_merges
test test_rebase_preserve_merges ... FAILED

Line 1: Expected AI author but got 'Test User'
Expected: ExpectedLine { contents: "// AI side", author_type: Ai }
Actual content: "// AI side"
Full blame output:
f68de6d (Test User 2026-01-07 21:57:30 +0800 1) // AI side

After

$ cargo test test_rebase_preserve_merges
test test_rebase_preserve_merges ... ok

test result: ok. 1 passed; 0 failed

Impact

✅ Fixes --rebase-merges authorship tracking
✅ All existing tests pass
✅ Zero impact on regular rebase (no merge commits)
✅ Fully backward compatible

Checklist

Tests pass locally
No breaking changes
Fixes failing integration test
Code follows existing patterns

Additional Notes

This is a critical fix for users relying on git rebase --rebase-merges to preserve merge commit structure. Without this fix, AI authorship data is silently lost for all commits in merged branches.

**Original Pull Request:** https://github.com/git-ai-project/git-ai/pull/330 **State:** closed **Merged:** No --- # Fix: Use BFS to collect all commits in `walk_commits_to_base` for `--rebase-merges` support ## Problem The `walk_commits_to_base` function only follows `parent(0)`, causing commits from merged branches to be lost during `git rebase --rebase-merges`. This results in AI authorship data being lost for side branch commits. Fixes the failing `test_rebase_preserve_merges` integration test. ## Solution Replace linear traversal with BFS (Breadth-First Search) to traverse all parent commits, ensuring merge commits' second parents are not missed. ### Changes **File**: `src/authorship/rebase_authorship.rs` **Before** (Lines 823-841): ```rust pub fn walk_commits_to_base(...) { let mut commits = Vec::new(); let mut current = repository.find_commit(head.to_string())?; let base_str = base.to_string(); while current.id().to_string() != base_str { commits.push(current.id().to_string()); current = current.parent(0)?; // ❌ Only follows first parent } Ok(commits) } ``` **After**: ```rust pub fn walk_commits_to_base(...) { use std::collections::{HashSet, VecDeque}; let mut commits = Vec::new(); let mut visited = HashSet::new(); let mut queue = VecDeque::new(); let base_str = base.to_string(); let head_commit = repository.find_commit(head.to_string())?; queue.push_back(head_commit); while let Some(current) = queue.pop_front() { let commit_id = current.id().to_string(); if commit_id == base_str { continue; } if visited.contains(&commit_id) { continue; } visited.insert(commit_id.clone()); commits.push(commit_id); // ✅ Traverse all parents (handles merge commits) let parent_count = current.parent_count().unwrap_or(0); for i in 0..parent_count { if let Ok(parent) = current.parent(i) { queue.push_back(parent); } } } Ok(commits) } ``` ## Test Results ### Before ```bash $ cargo test test_rebase_preserve_merges test test_rebase_preserve_merges ... FAILED Line 1: Expected AI author but got 'Test User' Expected: ExpectedLine { contents: "// AI side", author_type: Ai } Actual content: "// AI side" Full blame output: f68de6d (Test User 2026-01-07 21:57:30 +0800 1) // AI side ``` ### After ```bash $ cargo test test_rebase_preserve_merges test test_rebase_preserve_merges ... ok test result: ok. 1 passed; 0 failed ``` ## Impact - ✅ Fixes `--rebase-merges` authorship tracking - ✅ All existing tests pass - ✅ Zero impact on regular rebase (no merge commits) - ✅ Fully backward compatible ## Checklist - [x] Tests pass locally - [x] No breaking changes - [x] Fixes failing integration test - [x] Code follows existing patterns --- ## Additional Notes This is a critical fix for users relying on `git rebase --rebase-merges` to preserve merge commit structure. Without this fix, AI authorship data is silently lost for all commits in merged branches.