gix_revision/merge_base/
function.rs

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

gix_revision/merge_base/
function.rs
