git_diff/tree/
changes.rs

1use std::{borrow::BorrowMut, collections::VecDeque};
2
3use git_hash::{oid, ObjectId};
4
5use crate::{
6    tree,
7    tree::{visit::Change, TreeInfoPair},
8};
9
10/// The error returned by [tree::Changes::needed_to_obtain()].
11#[derive(Debug, thiserror::Error)]
12#[allow(missing_docs)]
13pub enum Error {
14    #[error("The object {oid} referenced by the tree or the tree itself was not found in the database")]
15    FindExisting {
16        oid: ObjectId,
17        source: Box<dyn std::error::Error + Send + Sync + 'static>,
18    },
19    #[error("The delegate cancelled the operation")]
20    Cancelled,
21    #[error(transparent)]
22    EntriesDecode(#[from] git_object::decode::Error),
23}
24
25impl<'a> tree::Changes<'a> {
26    /// Calculate the changes that would need to be applied to `self` to get `other`.
27    ///
28    /// * The `state` maybe owned or mutably borrowed to allow reuses allocated data structures through multiple runs.
29    /// * `locate` is a function `f(object_id, &mut buffer) -> Option<TreeIter>` to return a `TreeIter` for the given object id backing
30    ///   its data in the given buffer. Returning `None` is unexpected as these trees are obtained during iteration, and in a typical
31    ///   database errors are not expected either which is why the error case is omitted. To allow proper error reporting, [`Error::FindExisting`]
32    ///   should be converted into a more telling error.
33    /// * `delegate` will receive the computed changes, see the [`Visit`][`tree::Visit`] trait for more information on what to expect.
34    ///
35    /// # Notes
36    ///
37    /// * To obtain progress, implement it within the `delegate`.
38    /// * Tree entries are expected to be ordered using [`tree-entry-comparison`][git_cmp_c] (the same [in Rust][git_cmp_rs])
39    /// * it does a breadth first iteration as buffer space only fits two trees, the current one on the one we compare with.
40    /// * does not do rename tracking but attempts to reduce allocations to zero (so performance is mostly determined
41    ///   by the delegate implementation which should be as specific as possible. Rename tracking can be computed on top of the changes
42    ///   received by the `delegate`.
43    /// * cycle checking is not performed, but can be performed in the delegate which can return [`tree::visit::Action::Cancel`] to stop the traversal.
44    /// * [std::mem::ManuallyDrop] is used because `Peekable` is needed. When using it as wrapper around our no-drop iterators, all of the sudden
45    ///   borrowcheck complains as Drop is present (even though it's not)
46    ///
47    /// [git_cmp_c]: https://github.com/git/git/blob/311531c9de557d25ac087c1637818bd2aad6eb3a/tree-diff.c#L49:L65
48    /// [git_cmp_rs]: https://github.com/Byron/gitoxide/blob/a4d5f99c8dc99bf814790928a3bf9649cd99486b/git-object/src/mutable/tree.rs#L52-L55
49    pub fn needed_to_obtain<FindFn, R, StateMut, E>(
50        mut self,
51        other: git_object::TreeRefIter<'_>,
52        mut state: StateMut,
53        mut find: FindFn,
54        delegate: &mut R,
55    ) -> Result<(), Error>
56    where
57        FindFn: for<'b> FnMut(&oid, &'b mut Vec<u8>) -> Result<git_object::TreeRefIter<'b>, E>,
58        E: std::error::Error + Send + Sync + 'static,
59        R: tree::Visit,
60        StateMut: BorrowMut<tree::State>,
61    {
62        let state = state.borrow_mut();
63        state.clear();
64        let mut lhs_entries = peekable(self.0.take().unwrap_or_default());
65        let mut rhs_entries = peekable(other);
66        let mut pop_path = false;
67
68        loop {
69            if pop_path {
70                delegate.pop_path_component();
71            }
72            pop_path = true;
73
74            match (lhs_entries.next(), rhs_entries.next()) {
75                (None, None) => {
76                    match state.trees.pop_front() {
77                        Some((None, Some(rhs))) => {
78                            delegate.pop_front_tracked_path_and_set_current();
79                            rhs_entries = peekable(find(&rhs, &mut state.buf2).map_err(|err| Error::FindExisting {
80                                oid: rhs,
81                                source: err.into(),
82                            })?);
83                        }
84                        Some((Some(lhs), Some(rhs))) => {
85                            delegate.pop_front_tracked_path_and_set_current();
86                            lhs_entries = peekable(find(&lhs, &mut state.buf1).map_err(|err| Error::FindExisting {
87                                oid: lhs,
88                                source: err.into(),
89                            })?);
90                            rhs_entries = peekable(find(&rhs, &mut state.buf2).map_err(|err| Error::FindExisting {
91                                oid: rhs,
92                                source: err.into(),
93                            })?);
94                        }
95                        Some((Some(lhs), None)) => {
96                            delegate.pop_front_tracked_path_and_set_current();
97                            lhs_entries = peekable(find(&lhs, &mut state.buf1).map_err(|err| Error::FindExisting {
98                                oid: lhs,
99                                source: err.into(),
100                            })?);
101                        }
102                        Some((None, None)) => unreachable!("BUG: it makes no sense to fill the stack with empties"),
103                        None => return Ok(()),
104                    };
105                    pop_path = false;
106                }
107                (Some(lhs), Some(rhs)) => {
108                    use std::cmp::Ordering::*;
109                    let (lhs, rhs) = (lhs?, rhs?);
110                    match lhs.filename.cmp(rhs.filename) {
111                        Equal => handle_lhs_and_rhs_with_equal_filenames(lhs, rhs, &mut state.trees, delegate)?,
112                        Less => catchup_lhs_with_rhs(&mut lhs_entries, lhs, rhs, &mut state.trees, delegate)?,
113                        Greater => catchup_rhs_with_lhs(&mut rhs_entries, lhs, rhs, &mut state.trees, delegate)?,
114                    }
115                }
116                (Some(lhs), None) => {
117                    let lhs = lhs?;
118                    delete_entry_schedule_recursion(lhs, &mut state.trees, delegate)?;
119                }
120                (None, Some(rhs)) => {
121                    let rhs = rhs?;
122                    add_entry_schedule_recursion(rhs, &mut state.trees, delegate)?;
123                }
124            }
125        }
126    }
127}
128
129fn delete_entry_schedule_recursion<R: tree::Visit>(
130    entry: git_object::tree::EntryRef<'_>,
131    queue: &mut VecDeque<TreeInfoPair>,
132    delegate: &mut R,
133) -> Result<(), Error> {
134    delegate.push_path_component(entry.filename);
135    if delegate
136        .visit(Change::Deletion {
137            entry_mode: entry.mode,
138            oid: entry.oid.to_owned(),
139        })
140        .cancelled()
141    {
142        return Err(Error::Cancelled);
143    }
144    if entry.mode.is_tree() {
145        delegate.pop_path_component();
146        delegate.push_back_tracked_path_component(entry.filename);
147        queue.push_back((Some(entry.oid.to_owned()), None));
148    }
149    Ok(())
150}
151
152fn add_entry_schedule_recursion<R: tree::Visit>(
153    entry: git_object::tree::EntryRef<'_>,
154    queue: &mut VecDeque<TreeInfoPair>,
155    delegate: &mut R,
156) -> Result<(), Error> {
157    delegate.push_path_component(entry.filename);
158    if delegate
159        .visit(Change::Addition {
160            entry_mode: entry.mode,
161            oid: entry.oid.to_owned(),
162        })
163        .cancelled()
164    {
165        return Err(Error::Cancelled);
166    }
167    if entry.mode.is_tree() {
168        delegate.pop_path_component();
169        delegate.push_back_tracked_path_component(entry.filename);
170        queue.push_back((None, Some(entry.oid.to_owned())))
171    }
172    Ok(())
173}
174fn catchup_rhs_with_lhs<R: tree::Visit>(
175    rhs_entries: &mut IteratorType<git_object::TreeRefIter<'_>>,
176    lhs: git_object::tree::EntryRef<'_>,
177    rhs: git_object::tree::EntryRef<'_>,
178    queue: &mut VecDeque<TreeInfoPair>,
179    delegate: &mut R,
180) -> Result<(), Error> {
181    use std::cmp::Ordering::*;
182    add_entry_schedule_recursion(rhs, queue, delegate)?;
183    loop {
184        match rhs_entries.peek() {
185            Some(Ok(rhs)) => match lhs.filename.cmp(rhs.filename) {
186                Equal => {
187                    let rhs = rhs_entries.next().transpose()?.expect("the peeked item to be present");
188                    delegate.pop_path_component();
189                    handle_lhs_and_rhs_with_equal_filenames(lhs, rhs, queue, delegate)?;
190                    break;
191                }
192                Greater => {
193                    let rhs = rhs_entries.next().transpose()?.expect("the peeked item to be present");
194                    delegate.pop_path_component();
195                    add_entry_schedule_recursion(rhs, queue, delegate)?;
196                }
197                Less => {
198                    delegate.pop_path_component();
199                    delete_entry_schedule_recursion(lhs, queue, delegate)?;
200                    break;
201                }
202            },
203            Some(Err(err)) => return Err(Error::EntriesDecode(err.to_owned())),
204            None => {
205                delegate.pop_path_component();
206                delete_entry_schedule_recursion(lhs, queue, delegate)?;
207                break;
208            }
209        }
210    }
211    Ok(())
212}
213
214fn catchup_lhs_with_rhs<R: tree::Visit>(
215    lhs_entries: &mut IteratorType<git_object::TreeRefIter<'_>>,
216    lhs: git_object::tree::EntryRef<'_>,
217    rhs: git_object::tree::EntryRef<'_>,
218    queue: &mut VecDeque<TreeInfoPair>,
219    delegate: &mut R,
220) -> Result<(), Error> {
221    use std::cmp::Ordering::*;
222    delete_entry_schedule_recursion(lhs, queue, delegate)?;
223    loop {
224        match lhs_entries.peek() {
225            Some(Ok(lhs)) => match lhs.filename.cmp(rhs.filename) {
226                Equal => {
227                    let lhs = lhs_entries.next().expect("the peeked item to be present")?;
228                    delegate.pop_path_component();
229                    handle_lhs_and_rhs_with_equal_filenames(lhs, rhs, queue, delegate)?;
230                    break;
231                }
232                Less => {
233                    let lhs = lhs_entries.next().expect("the peeked item to be present")?;
234                    delegate.pop_path_component();
235                    delete_entry_schedule_recursion(lhs, queue, delegate)?;
236                }
237                Greater => {
238                    delegate.pop_path_component();
239                    add_entry_schedule_recursion(rhs, queue, delegate)?;
240                    break;
241                }
242            },
243            Some(Err(err)) => return Err(Error::EntriesDecode(err.to_owned())),
244            None => {
245                delegate.pop_path_component();
246                add_entry_schedule_recursion(rhs, queue, delegate)?;
247                break;
248            }
249        }
250    }
251    Ok(())
252}
253
254fn handle_lhs_and_rhs_with_equal_filenames<R: tree::Visit>(
255    lhs: git_object::tree::EntryRef<'_>,
256    rhs: git_object::tree::EntryRef<'_>,
257    queue: &mut VecDeque<TreeInfoPair>,
258    delegate: &mut R,
259) -> Result<(), Error> {
260    use git_object::tree::EntryMode::*;
261    match (lhs.mode, rhs.mode) {
262        (Tree, Tree) => {
263            delegate.push_back_tracked_path_component(lhs.filename);
264            if lhs.oid != rhs.oid
265                && delegate
266                    .visit(Change::Modification {
267                        previous_entry_mode: lhs.mode,
268                        previous_oid: lhs.oid.to_owned(),
269                        entry_mode: rhs.mode,
270                        oid: rhs.oid.to_owned(),
271                    })
272                    .cancelled()
273            {
274                return Err(Error::Cancelled);
275            }
276            queue.push_back((Some(lhs.oid.to_owned()), Some(rhs.oid.to_owned())));
277        }
278        (lhs_mode, Tree) if lhs_mode.is_no_tree() => {
279            delegate.push_back_tracked_path_component(lhs.filename);
280            if delegate
281                .visit(Change::Deletion {
282                    entry_mode: lhs.mode,
283                    oid: lhs.oid.to_owned(),
284                })
285                .cancelled()
286            {
287                return Err(Error::Cancelled);
288            };
289            if delegate
290                .visit(Change::Addition {
291                    entry_mode: rhs.mode,
292                    oid: rhs.oid.to_owned(),
293                })
294                .cancelled()
295            {
296                return Err(Error::Cancelled);
297            };
298            queue.push_back((None, Some(rhs.oid.to_owned())));
299        }
300        (Tree, rhs_mode) if rhs_mode.is_no_tree() => {
301            delegate.push_back_tracked_path_component(lhs.filename);
302            if delegate
303                .visit(Change::Deletion {
304                    entry_mode: lhs.mode,
305                    oid: lhs.oid.to_owned(),
306                })
307                .cancelled()
308            {
309                return Err(Error::Cancelled);
310            }
311            if delegate
312                .visit(Change::Addition {
313                    entry_mode: rhs.mode,
314                    oid: rhs.oid.to_owned(),
315                })
316                .cancelled()
317            {
318                return Err(Error::Cancelled);
319            };
320            queue.push_back((Some(lhs.oid.to_owned()), None));
321        }
322        (lhs_non_tree, rhs_non_tree) => {
323            delegate.push_path_component(lhs.filename);
324            debug_assert!(lhs_non_tree.is_no_tree() && rhs_non_tree.is_no_tree());
325            if lhs.oid != rhs.oid
326                && delegate
327                    .visit(Change::Modification {
328                        previous_entry_mode: lhs.mode,
329                        previous_oid: lhs.oid.to_owned(),
330                        entry_mode: rhs.mode,
331                        oid: rhs.oid.to_owned(),
332                    })
333                    .cancelled()
334            {
335                return Err(Error::Cancelled);
336            }
337        }
338    };
339    Ok(())
340}
341
342type IteratorType<I> = std::mem::ManuallyDrop<std::iter::Peekable<I>>;
343
344fn peekable<I: Iterator>(iter: I) -> IteratorType<I> {
345    std::mem::ManuallyDrop::new(iter.peekable())
346}
git_diff/tree/changes.rs

git_diff/tree/
changes.rs
