gix_diff/tree/
function.rs

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

gix_diff/tree/
function.rs
