gix_revision/merge_base/
function.rs

1use std::cmp::Ordering;
2
3use gix_hash::ObjectId;
4use gix_revwalk::graph;
5
6use super::Error;
7use crate::{merge_base::Flags, Graph, PriorityQueue};
8
9/// Given a commit at `first` id, traverse the commit `graph` and return all possible merge-base between it and `others`,
10/// sorted from best to worst. Returns `None` if there is no merge-base as `first` and `others` don't share history.
11/// If `others` is empty, `Some(first)` is returned.
12///
13/// Note that this function doesn't do any work if `first` is contained in `others`, which is when `first` will be returned
14/// as only merge-base right away. This is even the case if some commits of `others` are disjoint.
15///
16/// Additionally, this function isn't stable and results may differ dependeing on the order in which `first` and `others` are
17/// provided due to its special rules.
18///
19/// If a stable result is needed, use [`merge_base::octopus()`](crate::merge_base::octopus()).
20///
21/// # Performance
22///
23/// For repeated calls, be sure to re-use `graph` as its content will be kept and reused for a great speed-up. The contained flags
24/// will automatically be cleared.
25pub fn merge_base(
26    first: ObjectId,
27    others: &[ObjectId],
28    graph: &mut Graph<'_, '_, graph::Commit<Flags>>,
29) -> Result<Option<Vec<ObjectId>>, Error> {
30    let _span = gix_trace::coarse!("gix_revision::merge_base()", ?first, ?others);
31    if others.is_empty() || others.contains(&first) {
32        return Ok(Some(vec![first]));
33    }
34
35    graph.clear_commit_data(|f| *f = Flags::empty());
36    let bases = paint_down_to_common(first, others, graph)?;
37
38    let bases = remove_redundant(&bases, graph)?;
39    Ok((!bases.is_empty()).then_some(bases))
40}
41
42/// Remove all those commits from `commits` if they are in the history of another commit in `commits`.
43/// That way, we return only the topologically most recent commits in `commits`.
44fn remove_redundant(
45    commits: &[(ObjectId, GenThenTime)],
46    graph: &mut Graph<'_, '_, graph::Commit<Flags>>,
47) -> Result<Vec<ObjectId>, Error> {
48    if commits.is_empty() {
49        return Ok(Vec::new());
50    }
51    graph.clear_commit_data(|f| *f = Flags::empty());
52    let _span = gix_trace::detail!("gix_revision::remove_redundant()", num_commits = %commits.len());
53    let sorted_commits = {
54        let mut v = commits.to_vec();
55        v.sort_by(|a, b| a.1.cmp(&b.1));
56        v
57    };
58    let mut min_gen_pos = 0;
59    let mut min_gen = sorted_commits[min_gen_pos].1.generation;
60
61    let mut walk_start = Vec::with_capacity(commits.len());
62    for (id, _) in commits {
63        let commit = graph.get_mut(id).expect("previously added");
64        commit.data |= Flags::RESULT;
65        for parent_id in commit.parents.clone() {
66            graph.get_or_insert_full_commit(parent_id, |parent| {
67                // prevent double-addition
68                if !parent.data.contains(Flags::STALE) {
69                    parent.data |= Flags::STALE;
70                    walk_start.push((parent_id, GenThenTime::from(&*parent)));
71                }
72            })?;
73        }
74    }
75    walk_start.sort_by(|a, b| a.0.cmp(&b.0));
76    // allow walking everything at first.
77    walk_start
78        .iter_mut()
79        .for_each(|(id, _)| graph.get_mut(id).expect("added previously").data.remove(Flags::STALE));
80    let mut count_still_independent = commits.len();
81
82    let mut stack = Vec::new();
83    while let Some((commit_id, commit_info)) = walk_start.pop().filter(|_| count_still_independent > 1) {
84        stack.clear();
85        graph.get_mut(&commit_id).expect("added").data |= Flags::STALE;
86        stack.push((commit_id, commit_info));
87
88        while let Some((commit_id, commit_info)) = stack.last().copied() {
89            let commit = graph.get_mut(&commit_id).expect("all commits have been added");
90            let commit_parents = commit.parents.clone();
91            if commit.data.contains(Flags::RESULT) {
92                commit.data.remove(Flags::RESULT);
93                count_still_independent -= 1;
94                if count_still_independent <= 1 {
95                    break;
96                }
97                if *commit_id == *sorted_commits[min_gen_pos].0 {
98                    while min_gen_pos < commits.len() - 1
99                        && graph
100                            .get(&sorted_commits[min_gen_pos].0)
101                            .expect("already added")
102                            .data
103                            .contains(Flags::STALE)
104                    {
105                        min_gen_pos += 1;
106                    }
107                    min_gen = sorted_commits[min_gen_pos].1.generation;
108                }
109            }
110
111            if commit_info.generation < min_gen {
112                stack.pop();
113                continue;
114            }
115
116            let previous_len = stack.len();
117            for parent_id in &commit_parents {
118                if graph
119                    .get_or_insert_full_commit(*parent_id, |parent| {
120                        if !parent.data.contains(Flags::STALE) {
121                            parent.data |= Flags::STALE;
122                            stack.push((*parent_id, GenThenTime::from(&*parent)));
123                        }
124                    })?
125                    .is_some()
126                {
127                    break;
128                }
129            }
130
131            if previous_len == stack.len() {
132                stack.pop();
133            }
134        }
135    }
136
137    Ok(commits
138        .iter()
139        .filter_map(|(id, _info)| {
140            graph
141                .get(id)
142                .filter(|commit| !commit.data.contains(Flags::STALE))
143                .map(|_| *id)
144        })
145        .collect())
146}
147
148fn paint_down_to_common(
149    first: ObjectId,
150    others: &[ObjectId],
151    graph: &mut Graph<'_, '_, graph::Commit<Flags>>,
152) -> Result<Vec<(ObjectId, GenThenTime)>, Error> {
153    let mut queue = PriorityQueue::<GenThenTime, ObjectId>::new();
154    graph.get_or_insert_full_commit(first, |commit| {
155        commit.data |= Flags::COMMIT1;
156        queue.insert(GenThenTime::from(&*commit), first);
157    })?;
158
159    for other in others {
160        graph.get_or_insert_full_commit(*other, |commit| {
161            commit.data |= Flags::COMMIT2;
162            queue.insert(GenThenTime::from(&*commit), *other);
163        })?;
164    }
165
166    let mut out = Vec::new();
167    while queue
168        .iter_unordered()
169        .any(|id| graph.get(id).is_some_and(|commit| !commit.data.contains(Flags::STALE)))
170    {
171        let (info, commit_id) = queue.pop().expect("we have non-stale");
172        let commit = graph.get_mut(&commit_id).expect("everything queued is in graph");
173        let mut flags_without_result = commit.data & (Flags::COMMIT1 | Flags::COMMIT2 | Flags::STALE);
174        if flags_without_result == (Flags::COMMIT1 | Flags::COMMIT2) {
175            if !commit.data.contains(Flags::RESULT) {
176                commit.data |= Flags::RESULT;
177                out.push((commit_id, info));
178            }
179            flags_without_result |= Flags::STALE;
180        }
181
182        for parent_id in commit.parents.clone() {
183            graph.get_or_insert_full_commit(parent_id, |parent| {
184                if (parent.data & flags_without_result) != flags_without_result {
185                    parent.data |= flags_without_result;
186                    queue.insert(GenThenTime::from(&*parent), parent_id);
187                }
188            })?;
189        }
190    }
191
192    Ok(out)
193}
194
195// TODO(ST): Should this type be used for `describe` as well?
196#[derive(Debug, Clone, Copy)]
197struct GenThenTime {
198    /// Note that the special [`GENERATION_NUMBER_INFINITY`](gix_commitgraph::GENERATION_NUMBER_INFINITY) is used to indicate
199    /// that no commitgraph is available.
200    generation: gix_revwalk::graph::Generation,
201    time: gix_date::SecondsSinceUnixEpoch,
202}
203
204impl From<&graph::Commit<Flags>> for GenThenTime {
205    fn from(commit: &graph::Commit<Flags>) -> Self {
206        GenThenTime {
207            generation: commit.generation.unwrap_or(gix_commitgraph::GENERATION_NUMBER_INFINITY),
208            time: commit.commit_time,
209        }
210    }
211}
212
213impl Eq for GenThenTime {}
214
215impl PartialEq<Self> for GenThenTime {
216    fn eq(&self, other: &Self) -> bool {
217        self.cmp(other).is_eq()
218    }
219}
220
221impl PartialOrd<Self> for GenThenTime {
222    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
223        Some(self.cmp(other))
224    }
225}
226
227impl Ord for GenThenTime {
228    fn cmp(&self, other: &Self) -> Ordering {
229        self.generation.cmp(&other.generation).then(self.time.cmp(&other.time))
230    }
231}
gix_revision/merge_base/function.rs

gix_revision/merge_base/
function.rs
