gix_diff/tree/
function.rs

1use std::{borrow::BorrowMut, collections::VecDeque};
2
3use gix_object::{FindExt, TreeRefIter, tree::EntryRef};
4
5use crate::tree::{
6    Error, State, TreeInfoTuple, Visit,
7    visit::{Change, ChangeId, Relation},
8};
9
10/// Calculate the changes that would need to be applied to `lhs` to get `rhs` using `objects` to obtain objects as needed for traversal.
11/// `state` can be used between multiple calls to re-use memory.
12///
13/// * The `state` maybe owned or mutably borrowed to allow reuses allocated data structures through multiple runs.
14/// * `delegate` will receive the computed changes, see the [`Visit`] trait for more information on what to expect.
15///
16/// # Notes
17///
18/// * `lhs` can be an empty tree to simulate what would happen if the left-hand side didn't exist.
19/// * To obtain progress, implement it within the `delegate`.
20/// * Tree entries are expected to be ordered using [`tree-entry-comparison`][git_cmp_c] (the same [in Rust][git_cmp_rs])
21/// * it does a breadth first iteration as buffer space only fits two trees, the current one on the one we compare with.
22/// * does not do rename tracking but attempts to reduce allocations to zero (so performance is mostly determined
23///   by the delegate implementation which should be as specific as possible. Rename tracking can be computed on top of the changes
24///   received by the `delegate`.
25/// * cycle checking is not performed, but can be performed in the delegate which can return
26///   [`std::ops::ControlFlow::Break`] to stop the traversal.
27///
28/// [git_cmp_c]: https://github.com/git/git/blob/ef8ce8f3d4344fd3af049c17eeba5cd20d98b69f/tree-diff.c#L72-L88
29/// [git_cmp_rs]: https://github.com/GitoxideLabs/gitoxide/blob/795962b107d86f58b1f7c75006da256d19cc80ad/gix-object/src/tree/mod.rs#L263-L273
30#[doc(alias = "diff_tree_to_tree", alias = "git2")]
31pub fn diff<StateMut>(
32    lhs: TreeRefIter<'_>,
33    rhs: TreeRefIter<'_>,
34    mut state: StateMut,
35    objects: impl gix_object::Find,
36    delegate: &mut impl Visit,
37) -> Result<(), Error>
38where
39    StateMut: BorrowMut<State>,
40{
41    let state = state.borrow_mut();
42    state.clear();
43    let mut lhs_entries = peekable(lhs);
44    let mut rhs_entries = peekable(rhs);
45    let mut relation = None;
46    let mut pop_path = false;
47
48    loop {
49        if pop_path {
50            delegate.pop_path_component();
51        }
52        pop_path = true;
53
54        match (lhs_entries.next(), rhs_entries.next()) {
55            (None, None) => {
56                match state.trees.pop_front() {
57                    Some((None, Some(rhs), relation_to_propagate)) => {
58                        delegate.pop_front_tracked_path_and_set_current();
59                        relation = relation_to_propagate;
60                        rhs_entries = peekable(objects.find_tree_iter(&rhs, &mut state.buf2)?);
61                    }
62                    Some((Some(lhs), Some(rhs), relation_to_propagate)) => {
63                        delegate.pop_front_tracked_path_and_set_current();
64                        lhs_entries = peekable(objects.find_tree_iter(&lhs, &mut state.buf1)?);
65                        rhs_entries = peekable(objects.find_tree_iter(&rhs, &mut state.buf2)?);
66                        relation = relation_to_propagate;
67                    }
68                    Some((Some(lhs), None, relation_to_propagate)) => {
69                        delegate.pop_front_tracked_path_and_set_current();
70                        lhs_entries = peekable(objects.find_tree_iter(&lhs, &mut state.buf1)?);
71                        relation = relation_to_propagate;
72                    }
73                    Some((None, None, _)) => unreachable!("BUG: it makes no sense to fill the stack with empties"),
74                    None => return Ok(()),
75                }
76                pop_path = false;
77            }
78            (Some(lhs), Some(rhs)) => {
79                use std::cmp::Ordering::*;
80                let (lhs, rhs) = (lhs?, rhs?);
81                match compare(&lhs, &rhs) {
82                    Equal => handle_lhs_and_rhs_with_equal_filenames(
83                        lhs,
84                        rhs,
85                        &mut state.trees,
86                        &mut state.change_id,
87                        relation,
88                        delegate,
89                    )?,
90                    Less => catchup_lhs_with_rhs(
91                        &mut lhs_entries,
92                        lhs,
93                        rhs,
94                        &mut state.trees,
95                        &mut state.change_id,
96                        relation,
97                        delegate,
98                    )?,
99                    Greater => catchup_rhs_with_lhs(
100                        &mut rhs_entries,
101                        lhs,
102                        rhs,
103                        &mut state.trees,
104                        &mut state.change_id,
105                        relation,
106                        delegate,
107                    )?,
108                }
109            }
110            (Some(lhs), None) => {
111                let lhs = lhs?;
112                delete_entry_schedule_recursion(lhs, &mut state.trees, &mut state.change_id, relation, delegate)?;
113            }
114            (None, Some(rhs)) => {
115                let rhs = rhs?;
116                add_entry_schedule_recursion(rhs, &mut state.trees, &mut state.change_id, relation, delegate)?;
117            }
118        }
119    }
120}
121
122fn compare(a: &EntryRef<'_>, b: &EntryRef<'_>) -> std::cmp::Ordering {
123    gix_object::tree::name_order(a.filename, a.mode.is_tree(), b.filename, b.mode.is_tree())
124}
125
126fn delete_entry_schedule_recursion(
127    entry: EntryRef<'_>,
128    queue: &mut VecDeque<TreeInfoTuple>,
129    change_id: &mut ChangeId,
130    relation_to_propagate: Option<Relation>,
131    delegate: &mut impl Visit,
132) -> Result<(), Error> {
133    delegate.push_path_component(entry.filename);
134    let relation = relation_to_propagate.or_else(|| {
135        entry.mode.is_tree().then(|| {
136            *change_id += 1;
137            Relation::Parent(*change_id)
138        })
139    });
140    let is_cancelled = delegate
141        .visit(Change::Deletion {
142            entry_mode: entry.mode,
143            oid: entry.oid.to_owned(),
144            relation,
145        })
146        .is_break();
147    if is_cancelled {
148        return Err(Error::Cancelled);
149    }
150    if entry.mode.is_tree() {
151        delegate.pop_path_component();
152        delegate.push_back_tracked_path_component(entry.filename);
153        queue.push_back((Some(entry.oid.to_owned()), None, to_child(relation)));
154    }
155    Ok(())
156}
157
158fn add_entry_schedule_recursion(
159    entry: EntryRef<'_>,
160    queue: &mut VecDeque<TreeInfoTuple>,
161    change_id: &mut ChangeId,
162    relation_to_propagate: Option<Relation>,
163    delegate: &mut impl Visit,
164) -> Result<(), Error> {
165    delegate.push_path_component(entry.filename);
166    let relation = relation_to_propagate.or_else(|| {
167        entry.mode.is_tree().then(|| {
168            *change_id += 1;
169            Relation::Parent(*change_id)
170        })
171    });
172    if delegate
173        .visit(Change::Addition {
174            entry_mode: entry.mode,
175            oid: entry.oid.to_owned(),
176            relation,
177        })
178        .is_break()
179    {
180        return Err(Error::Cancelled);
181    }
182    if entry.mode.is_tree() {
183        delegate.pop_path_component();
184        delegate.push_back_tracked_path_component(entry.filename);
185        queue.push_back((None, Some(entry.oid.to_owned()), to_child(relation)));
186    }
187    Ok(())
188}
189
190fn catchup_rhs_with_lhs(
191    rhs_entries: &mut IteratorType<TreeRefIter<'_>>,
192    lhs: EntryRef<'_>,
193    rhs: EntryRef<'_>,
194    queue: &mut VecDeque<TreeInfoTuple>,
195    change_id: &mut ChangeId,
196    relation_to_propagate: Option<Relation>,
197    delegate: &mut impl Visit,
198) -> Result<(), Error> {
199    use std::cmp::Ordering::*;
200    add_entry_schedule_recursion(rhs, queue, change_id, relation_to_propagate, delegate)?;
201    loop {
202        match rhs_entries.peek() {
203            Some(Ok(rhs)) => match compare(&lhs, rhs) {
204                Equal => {
205                    let rhs = rhs_entries.next().transpose()?.expect("the peeked item to be present");
206                    delegate.pop_path_component();
207                    handle_lhs_and_rhs_with_equal_filenames(
208                        lhs,
209                        rhs,
210                        queue,
211                        change_id,
212                        relation_to_propagate,
213                        delegate,
214                    )?;
215                    break;
216                }
217                Greater => {
218                    let rhs = rhs_entries.next().transpose()?.expect("the peeked item to be present");
219                    delegate.pop_path_component();
220                    add_entry_schedule_recursion(rhs, queue, change_id, relation_to_propagate, delegate)?;
221                }
222                Less => {
223                    delegate.pop_path_component();
224                    delete_entry_schedule_recursion(lhs, queue, change_id, relation_to_propagate, delegate)?;
225                    break;
226                }
227            },
228            Some(Err(err)) => return Err(Error::EntriesDecode(err.to_owned())),
229            None => {
230                delegate.pop_path_component();
231                delete_entry_schedule_recursion(lhs, queue, change_id, relation_to_propagate, delegate)?;
232                break;
233            }
234        }
235    }
236    Ok(())
237}
238
239fn catchup_lhs_with_rhs(
240    lhs_entries: &mut IteratorType<TreeRefIter<'_>>,
241    lhs: EntryRef<'_>,
242    rhs: EntryRef<'_>,
243    queue: &mut VecDeque<TreeInfoTuple>,
244    change_id: &mut ChangeId,
245    relation_to_propagate: Option<Relation>,
246    delegate: &mut impl Visit,
247) -> Result<(), Error> {
248    use std::cmp::Ordering::*;
249    delete_entry_schedule_recursion(lhs, queue, change_id, relation_to_propagate, delegate)?;
250    loop {
251        match lhs_entries.peek() {
252            Some(Ok(lhs)) => match compare(lhs, &rhs) {
253                Equal => {
254                    let lhs = lhs_entries.next().expect("the peeked item to be present")?;
255                    delegate.pop_path_component();
256                    handle_lhs_and_rhs_with_equal_filenames(
257                        lhs,
258                        rhs,
259                        queue,
260                        change_id,
261                        relation_to_propagate,
262                        delegate,
263                    )?;
264                    break;
265                }
266                Less => {
267                    let lhs = lhs_entries.next().expect("the peeked item to be present")?;
268                    delegate.pop_path_component();
269                    delete_entry_schedule_recursion(lhs, queue, change_id, relation_to_propagate, delegate)?;
270                }
271                Greater => {
272                    delegate.pop_path_component();
273                    add_entry_schedule_recursion(rhs, queue, change_id, relation_to_propagate, delegate)?;
274                    break;
275                }
276            },
277            Some(Err(err)) => return Err(Error::EntriesDecode(err.to_owned())),
278            None => {
279                delegate.pop_path_component();
280                add_entry_schedule_recursion(rhs, queue, change_id, relation_to_propagate, delegate)?;
281                break;
282            }
283        }
284    }
285    Ok(())
286}
287
288fn handle_lhs_and_rhs_with_equal_filenames(
289    lhs: EntryRef<'_>,
290    rhs: EntryRef<'_>,
291    queue: &mut VecDeque<TreeInfoTuple>,
292    change_id: &mut ChangeId,
293    relation_to_propagate: Option<Relation>,
294    delegate: &mut impl Visit,
295) -> Result<(), Error> {
296    match (lhs.mode.is_tree(), rhs.mode.is_tree()) {
297        (true, true) => {
298            if lhs.oid == rhs.oid {
299                // If the tree oids are identical, we won't bother recursing
300                // into this subtree as the entire tree is identical.
301                // For path management purposes, treat it like a skipped blob.
302                delegate.push_path_component(lhs.filename);
303            } else {
304                delegate.push_back_tracked_path_component(lhs.filename);
305                if delegate
306                    .visit(Change::Modification {
307                        previous_entry_mode: lhs.mode,
308                        previous_oid: lhs.oid.to_owned(),
309                        entry_mode: rhs.mode,
310                        oid: rhs.oid.to_owned(),
311                    })
312                    .is_break()
313                {
314                    return Err(Error::Cancelled);
315                }
316                queue.push_back((
317                    Some(lhs.oid.to_owned()),
318                    Some(rhs.oid.to_owned()),
319                    relation_to_propagate,
320                ));
321            }
322        }
323        (_, true) => {
324            delegate.push_back_tracked_path_component(lhs.filename);
325            if delegate
326                .visit(Change::Deletion {
327                    entry_mode: lhs.mode,
328                    oid: lhs.oid.to_owned(),
329                    relation: None,
330                })
331                .is_break()
332            {
333                return Err(Error::Cancelled);
334            }
335
336            let relation = relation_to_propagate.or_else(|| {
337                *change_id += 1;
338                Some(Relation::Parent(*change_id))
339            });
340            if delegate
341                .visit(Change::Addition {
342                    entry_mode: rhs.mode,
343                    oid: rhs.oid.to_owned(),
344                    relation,
345                })
346                .is_break()
347            {
348                return Err(Error::Cancelled);
349            }
350            queue.push_back((None, Some(rhs.oid.to_owned()), to_child(relation)));
351        }
352        (true, _) => {
353            delegate.push_back_tracked_path_component(lhs.filename);
354            let relation = relation_to_propagate.or_else(|| {
355                *change_id += 1;
356                Some(Relation::Parent(*change_id))
357            });
358            if delegate
359                .visit(Change::Deletion {
360                    entry_mode: lhs.mode,
361                    oid: lhs.oid.to_owned(),
362                    relation,
363                })
364                .is_break()
365            {
366                return Err(Error::Cancelled);
367            }
368            if delegate
369                .visit(Change::Addition {
370                    entry_mode: rhs.mode,
371                    oid: rhs.oid.to_owned(),
372                    relation: None,
373                })
374                .is_break()
375            {
376                return Err(Error::Cancelled);
377            }
378            queue.push_back((Some(lhs.oid.to_owned()), None, to_child(relation)));
379        }
380        (false, false) => {
381            delegate.push_path_component(lhs.filename);
382            debug_assert!(lhs.mode.is_no_tree() && lhs.mode.is_no_tree());
383            if (lhs.oid != rhs.oid || lhs.mode != rhs.mode)
384                && delegate
385                    .visit(Change::Modification {
386                        previous_entry_mode: lhs.mode,
387                        previous_oid: lhs.oid.to_owned(),
388                        entry_mode: rhs.mode,
389                        oid: rhs.oid.to_owned(),
390                    })
391                    .is_break()
392            {
393                return Err(Error::Cancelled);
394            }
395        }
396    }
397    Ok(())
398}
399
400type IteratorType<I> = std::iter::Peekable<I>;
401
402fn to_child(r: Option<Relation>) -> Option<Relation> {
403    r.map(|r| match r {
404        Relation::Parent(id) => Relation::ChildOfParent(id),
405        Relation::ChildOfParent(id) => Relation::ChildOfParent(id),
406    })
407}
408
409fn peekable<I: Iterator>(iter: I) -> IteratorType<I> {
410    iter.peekable()
411}
412
413#[cfg(test)]
414mod tests {
415    use std::cmp::Ordering;
416
417    use gix_object::tree::EntryKind;
418
419    use super::*;
420
421    #[test]
422    fn compare_select_samples() {
423        let null = gix_testtools::object_hash().null();
424        let actual = compare(
425            &EntryRef {
426                mode: EntryKind::Blob.into(),
427                filename: "plumbing-cli.rs".into(),
428                oid: &null,
429            },
430            &EntryRef {
431                mode: EntryKind::Tree.into(),
432                filename: "plumbing".into(),
433                oid: &null,
434            },
435        );
436        assert_eq!(actual, Ordering::Less);
437        let actual = compare(
438            &EntryRef {
439                mode: EntryKind::Tree.into(),
440                filename: "plumbing-cli.rs".into(),
441                oid: &null,
442            },
443            &EntryRef {
444                mode: EntryKind::Blob.into(),
445                filename: "plumbing".into(),
446                oid: &null,
447            },
448        );
449        assert_eq!(actual, Ordering::Greater);
450    }
451}
gix_diff/tree/function.rs

gix_diff/tree/
function.rs
