arrow_graph_git/
history.rs

1//! History DAG — traversal of commit parent_ids to form a directed acyclic graph.
2//!
3//! Provides log (ordered commit history) and ancestors (full BFS traversal).
4
5use crate::commit::{Commit, CommitsTable};
6use std::collections::{HashSet, VecDeque};
7
8/// Return the commit log for a branch: walk parent_ids from the given commit.
9///
10/// Returns commits in reverse chronological order (newest first).
11/// `limit` caps the number of commits returned (0 = unlimited).
12pub fn log<'a>(
13    commits_table: &'a CommitsTable,
14    start_commit_id: &str,
15    limit: usize,
16) -> Vec<&'a Commit> {
17    let mut result = Vec::new();
18    let mut visited = HashSet::new();
19    let mut queue = VecDeque::new();
20
21    queue.push_back(start_commit_id.to_string());
22
23    while let Some(cid) = queue.pop_front() {
24        if !visited.insert(cid.clone()) {
25            continue;
26        }
27
28        if let Some(commit) = commits_table.get(&cid) {
29            result.push(commit);
30
31            if limit > 0 && result.len() >= limit {
32                break;
33            }
34
35            // Enqueue parents (first parent first for linear history)
36            for pid in &commit.parent_ids {
37                if !visited.contains(pid.as_str()) {
38                    queue.push_back(pid.clone());
39                }
40            }
41        }
42    }
43
44    result
45}
46
47/// Return all ancestors of a commit (BFS traversal of the DAG).
48///
49/// Returns all reachable commits including the start commit.
50pub fn ancestors<'a>(commits_table: &'a CommitsTable, commit_id: &str) -> Vec<&'a Commit> {
51    log(commits_table, commit_id, 0)
52}
53
54/// Find the most recent common ancestor of two commits (for 3-way merge).
55///
56/// BFS from both commits simultaneously; first intersection is the common ancestor.
57pub fn find_common_ancestor<'a>(
58    commits_table: &'a CommitsTable,
59    commit_a: &str,
60    commit_b: &str,
61) -> Option<&'a Commit> {
62    let ancestors_a: HashSet<String> = ancestors(commits_table, commit_a)
63        .iter()
64        .map(|c| c.commit_id.clone())
65        .collect();
66
67    // Walk from B, find first commit that's also an ancestor of A
68    let ancestors_b = ancestors(commits_table, commit_b);
69    ancestors_b
70        .into_iter()
71        .find(|commit| ancestors_a.contains(&commit.commit_id))
72}
73
74#[cfg(test)]
75mod tests {
76    use super::*;
77    use crate::commit::Commit;
78
79    fn make_commit(id: &str, parents: Vec<&str>) -> Commit {
80        Commit {
81            commit_id: id.to_string(),
82            parent_ids: parents.into_iter().map(String::from).collect(),
83            timestamp_ms: 0,
84            message: format!("commit {id}"),
85            author: "test".to_string(),
86        }
87    }
88
89    fn build_linear_history() -> CommitsTable {
90        // c1 <- c2 <- c3
91        let mut table = CommitsTable::new();
92        table.append(make_commit("c1", vec![]));
93        table.append(make_commit("c2", vec!["c1"]));
94        table.append(make_commit("c3", vec!["c2"]));
95        table
96    }
97
98    #[test]
99    fn test_log_linear() {
100        let table = build_linear_history();
101        let result = log(&table, "c3", 0);
102        assert_eq!(result.len(), 3);
103        assert_eq!(result[0].commit_id, "c3");
104        assert_eq!(result[1].commit_id, "c2");
105        assert_eq!(result[2].commit_id, "c1");
106    }
107
108    #[test]
109    fn test_log_with_limit() {
110        let table = build_linear_history();
111        let result = log(&table, "c3", 2);
112        assert_eq!(result.len(), 2);
113    }
114
115    #[test]
116    fn test_ancestors() {
117        let table = build_linear_history();
118        let result = ancestors(&table, "c3");
119        assert_eq!(result.len(), 3);
120    }
121
122    #[test]
123    fn test_common_ancestor_linear() {
124        // c1 <- c2 <- c3, common ancestor of c2 and c3 = c2
125        let table = build_linear_history();
126        let ca = find_common_ancestor(&table, "c2", "c3").unwrap();
127        assert_eq!(ca.commit_id, "c2");
128    }
129
130    #[test]
131    fn test_common_ancestor_branched() {
132        // c1 <- c2 <- c3 (main)
133        //    \<- c4 (feature)
134        let mut table = CommitsTable::new();
135        table.append(make_commit("c1", vec![]));
136        table.append(make_commit("c2", vec!["c1"]));
137        table.append(make_commit("c3", vec!["c2"]));
138        table.append(make_commit("c4", vec!["c1"]));
139
140        let ca = find_common_ancestor(&table, "c3", "c4").unwrap();
141        assert_eq!(ca.commit_id, "c1");
142    }
143
144    #[test]
145    fn test_no_common_ancestor() {
146        // Two disconnected commits
147        let mut table = CommitsTable::new();
148        table.append(make_commit("c1", vec![]));
149        table.append(make_commit("c2", vec![]));
150
151        // c1 IS c1's ancestor set, c2 IS c2's ancestor set — no overlap
152        // Actually c1 and c2 both have no parents and are distinct
153        let result = find_common_ancestor(&table, "c1", "c2");
154        assert!(result.is_none());
155    }
156}
arrow_graph_git/history.rs

arrow_graph_git/
history.rs
