gix_object/tree/
editor.rs

1use std::{
2    cmp::Ordering,
3    collections::{HashMap, hash_map},
4    fmt::Formatter,
5};
6
7use bstr::{BStr, BString, ByteSlice, ByteVec};
8use gix_error::{Result, bail, validation};
9use gix_hash::ObjectId;
10
11use crate::{
12    Tree, tree,
13    tree::{Editor, EntryKind},
14};
15
16/// A way to constrain all [tree-edits](Editor) to a given subtree.
17pub struct Cursor<'a, 'find> {
18    /// The underlying editor
19    parent: &'a mut Editor<'find>,
20    /// Our own location, used as prefix for all operations.
21    /// Note that it's assumed to always contain a tree.
22    prefix: BString,
23}
24
25impl std::fmt::Debug for Editor<'_> {
26    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
27        f.debug_struct("Editor")
28            .field("object_hash", &self.object_hash)
29            .field("path_buf", &self.path_buf)
30            .field("trees", &self.trees)
31            .finish()
32    }
33}
34
35/// Lifecycle
36impl<'a> Editor<'a> {
37    /// Create a new editor that uses `root` as base for all edits. Use `find` to lookup existing
38    /// trees when edits are made. Each tree will only be looked-up once and then edited in place from
39    /// that point on.
40    /// `object_hash` denotes the kind of hash to create.
41    pub fn new(root: Tree, find: &'a dyn crate::FindExt, object_hash: gix_hash::Kind) -> Self {
42        Editor {
43            find,
44            object_hash,
45            trees: HashMap::from_iter(Some((empty_path(), root))),
46            path_buf: BString::from(Vec::with_capacity(256)).into(),
47            tree_buf: Vec::with_capacity(512),
48        }
49    }
50}
51
52/// Operations
53impl Editor<'_> {
54    /// Write the entire in-memory state of all changed trees (and only changed trees) to `out`, and remove
55    /// written portions from our state except for the root tree, which affects [`get()`](Editor::get()).
56    /// Note that the returned object id *can* be the empty tree if everything was removed or if nothing
57    /// was added to the tree.
58    ///
59    /// The last call to `out` will be the changed root tree, whose object-id will also be returned.
60    /// `out` is free to do any kind of additional validation, like to assure that all entries in the tree exist.
61    /// We don't assure that as there is no validation that inserted entries are valid object ids.
62    ///
63    /// Future calls to [`upsert`](Self::upsert) or similar will keep working on the last seen state of the
64    /// just-written root-tree.
65    /// If this is not desired, use [set_root()](Self::set_root()).
66    ///
67    /// ### Validation
68    ///
69    /// Note that no additional validation is performed to assure correctness of entry-names.
70    /// It is absolutely and intentionally possible to write out invalid trees with this method.
71    /// Higher layers are expected to perform detailed validation.
72    pub fn write<E>(
73        &mut self,
74        out: impl FnMut(&Tree) -> std::result::Result<ObjectId, E>,
75    ) -> std::result::Result<ObjectId, E> {
76        self.path_buf.borrow_mut().clear();
77        self.write_at_pathbuf(out, WriteMode::Normal)
78    }
79
80    /// Remove the entry at `rela_path`, loading all trees on the path accordingly.
81    /// It's no error if the entry doesn't exist, or if `rela_path` doesn't lead to an existing entry at all.
82    pub fn remove<I, C>(&mut self, rela_path: I) -> Result<&mut Self>
83    where
84        I: IntoIterator<Item = C>,
85        C: AsRef<BStr>,
86    {
87        self.path_buf.borrow_mut().clear();
88        self.upsert_or_remove_at_pathbuf(rela_path, EditMode::Remove(RemoveMode::Any))
89    }
90
91    /// Remove a non-tree entry at `rela_path`, loading all trees on the path accordingly.
92    /// It's no error if the entry doesn't exist, or if `rela_path` doesn't lead to an existing entry at all.
93    ///
94    /// Return a validation error if the entry exists and is a tree, as that would otherwise also remove all entries below it.
95    /// To leave tree entries untouched instead, use [`Self::remove_if_leaf()`].
96    /// Empty path components produce a validation error if reached while loading the path.
97    pub fn remove_leaf<I, C>(&mut self, rela_path: I) -> Result<&mut Self>
98    where
99        I: IntoIterator<Item = C>,
100        C: AsRef<BStr>,
101    {
102        self.path_buf.borrow_mut().clear();
103        self.upsert_or_remove_at_pathbuf(rela_path, EditMode::Remove(RemoveMode::LeafOnly))
104    }
105
106    /// Remove the entry at `rela_path` only if it is not a tree, loading trees along the path as needed.
107    ///
108    /// An existing tree and its descendants are left untouched. It's also no error if the entry doesn't exist.
109    /// Empty path components produce a validation error if reached while loading the path, and tree-loading errors
110    /// are propagated.
111    pub fn remove_if_leaf<I, C>(&mut self, rela_path: I) -> Result<&mut Self>
112    where
113        I: IntoIterator<Item = C>,
114        C: AsRef<BStr>,
115    {
116        self.path_buf.borrow_mut().clear();
117        self.upsert_or_remove_at_pathbuf(rela_path, EditMode::Remove(RemoveMode::IfLeaf))
118    }
119
120    /// Obtain the entry at `rela_path` or return `None` if none was found, or the tree wasn't yet written
121    /// to that point.
122    /// Note that after [writing](Self::write) only the root path remains, all other intermediate trees are removed.
123    /// The entry can be anything that can be stored in a tree, but may have a null-id if it's a newly
124    /// inserted tree. Also, ids of trees might not be accurate as they may have been changed in memory.
125    pub fn get<I, C>(&self, rela_path: I) -> Option<&tree::Entry>
126    where
127        I: IntoIterator<Item = C>,
128        C: AsRef<BStr>,
129    {
130        self.path_buf.borrow_mut().clear();
131        self.get_inner(rela_path)
132    }
133
134    /// Insert a new entry of `kind` with `id` at `rela_path`, an iterator over each path component in the tree,
135    /// like `a/b/c`. Names are matched case-sensitively.
136    ///
137    /// Existing leaf-entries will be overwritten unconditionally, and it is assumed that `id` is available in the object database
138    /// or will be made available at a later point to assure the integrity of the produced tree.
139    ///
140    /// Intermediate trees will be created if they don't exist in the object database, otherwise they will be loaded and entries
141    /// will be inserted into them instead.
142    ///
143    /// Note that `id` can be [null](ObjectId::null()) to create a placeholder. These will not be written, and paths leading
144    /// through them will not be considered a problem.
145    ///
146    /// `id` can also be an empty tree, along with [the respective `kind`](EntryKind::Tree), even though that's normally not allowed
147    /// in Git trees.
148    pub fn upsert<I, C>(&mut self, rela_path: I, kind: EntryKind, id: ObjectId) -> Result<&mut Self>
149    where
150        I: IntoIterator<Item = C>,
151        C: AsRef<BStr>,
152    {
153        self.path_buf.borrow_mut().clear();
154        self.upsert_or_remove_at_pathbuf(rela_path, EditMode::Upsert(kind, id, UpsertMode::Normal))
155    }
156
157    fn get_inner<I, C>(&self, rela_path: I) -> Option<&tree::Entry>
158    where
159        I: IntoIterator<Item = C>,
160        C: AsRef<BStr>,
161    {
162        let mut path_buf = self.path_buf.borrow_mut();
163        let mut cursor = self.trees.get(path_buf.as_bstr()).expect("root is always present");
164        let mut rela_path = rela_path.into_iter().peekable();
165        while let Some(name) = rela_path.next() {
166            let name = name.as_ref();
167            let is_last = rela_path.peek().is_none();
168            match cursor
169                .entries
170                .binary_search_by(|e| cmp_entry_with_name(e, name, true))
171                .or_else(|_| cursor.entries.binary_search_by(|e| cmp_entry_with_name(e, name, false)))
172            {
173                Ok(idx) if is_last => return Some(&cursor.entries[idx]),
174                Ok(idx) => {
175                    if cursor.entries[idx].mode.is_tree() {
176                        push_path_component(&mut path_buf, name);
177                        cursor = self.trees.get(path_buf.as_bstr())?;
178                    } else {
179                        break;
180                    }
181                }
182                Err(_) => break,
183            }
184        }
185        None
186    }
187
188    fn write_at_pathbuf<E>(
189        &mut self,
190        mut out: impl FnMut(&Tree) -> std::result::Result<ObjectId, E>,
191        mode: WriteMode,
192    ) -> std::result::Result<ObjectId, E> {
193        assert_ne!(self.trees.len(), 0, "there is at least the root tree");
194
195        // back is for children, front is for parents.
196        let path_buf = self.path_buf.borrow_mut();
197        let mut parents = vec![(
198            None::<usize>,
199            path_buf.clone(),
200            self.trees
201                .remove(path_buf.as_bstr())
202                .expect("root tree is always present"),
203        )];
204        let mut children = Vec::new();
205        while let Some((parent_idx, mut rela_path, mut tree)) = children.pop().or_else(|| parents.pop()) {
206            let mut all_entries_unchanged_or_written = true;
207            for entry in &tree.entries {
208                if entry.mode.is_tree() {
209                    let prev_len = push_path_component(&mut rela_path, &entry.filename);
210                    if let Some(sub_tree) = self.trees.remove(&rela_path) {
211                        all_entries_unchanged_or_written = false;
212                        let next_parent_idx = parents.len();
213                        children.push((Some(next_parent_idx), rela_path.clone(), sub_tree));
214                    }
215                    rela_path.truncate(prev_len);
216                }
217            }
218            if all_entries_unchanged_or_written {
219                tree.entries.retain(|e| !e.oid.is_null());
220                if let Some((_, _, parent_to_adjust)) =
221                    parent_idx.map(|idx| parents.get_mut(idx).expect("always present, pointing towards zero"))
222                {
223                    let name = filename(rela_path.as_bstr());
224                    let entry_idx = parent_to_adjust
225                        .entries
226                        .binary_search_by(|e| cmp_entry_with_name(e, name, true))
227                        .expect("the parent always knows us by name");
228                    if tree.entries.is_empty() {
229                        parent_to_adjust.entries.remove(entry_idx);
230                    } else {
231                        match out(&tree) {
232                            Ok(id) => {
233                                parent_to_adjust.entries[entry_idx].oid = id;
234                            }
235                            Err(err) => {
236                                let root_tree = parents.into_iter().next().expect("root wasn't consumed yet");
237                                self.trees.insert(root_tree.1, root_tree.2);
238                                return Err(err);
239                            }
240                        }
241                    }
242                } else if parents.is_empty() {
243                    debug_assert!(children.is_empty(), "we consume children before parents");
244                    debug_assert_eq!(rela_path, **path_buf, "this should always be the root tree");
245
246                    // There may be left-over trees if they are replaced with blobs for example.
247                    match out(&tree) {
248                        Ok(id) => {
249                            let root_tree_id = id;
250                            match mode {
251                                WriteMode::Normal => {
252                                    self.trees.clear();
253                                }
254                                WriteMode::FromCursor => {}
255                            }
256                            self.trees.insert(rela_path, tree);
257                            return Ok(root_tree_id);
258                        }
259                        Err(err) => {
260                            self.trees.insert(rela_path, tree);
261                            return Err(err);
262                        }
263                    }
264                } else if !tree.entries.is_empty() {
265                    out(&tree)?;
266                }
267            } else {
268                parents.push((parent_idx, rela_path, tree));
269            }
270        }
271
272        unreachable!("we exit as soon as everything is consumed")
273    }
274
275    fn upsert_or_remove_at_pathbuf<I, C>(&mut self, rela_path: I, edit: EditMode) -> Result<&mut Self>
276    where
277        I: IntoIterator<Item = C>,
278        C: AsRef<BStr>,
279    {
280        let mut path_buf = self.path_buf.borrow_mut();
281        let mut cursor = self.trees.get_mut(path_buf.as_bstr()).expect("root is always present");
282        let mut rela_path = rela_path.into_iter().peekable();
283        let new_kind_is_tree = matches!(edit, EditMode::Upsert(EntryKind::Tree, _, _));
284        while let Some(name) = rela_path.next() {
285            let name = name.as_ref();
286            if name.is_empty() {
287                bail!(validation("Empty path components are not allowed"));
288            }
289            let is_last = rela_path.peek().is_none();
290            let mut needs_sorting = false;
291            let current_level_must_be_tree = !is_last || new_kind_is_tree;
292            let check_type_change = |entry: &tree::Entry| entry.mode.is_tree() != current_level_must_be_tree;
293            let tree_to_lookup = match cursor
294                .entries
295                .binary_search_by(|e| cmp_entry_with_name(e, name, false))
296                .or_else(|file_insertion_idx| {
297                    cursor
298                        .entries
299                        .binary_search_by(|e| cmp_entry_with_name(e, name, true))
300                        .map_err(|dir_insertion_index| {
301                            if current_level_must_be_tree {
302                                dir_insertion_index
303                            } else {
304                                file_insertion_idx
305                            }
306                        })
307                }) {
308                Ok(idx) => {
309                    match edit {
310                        EditMode::Remove(mode) => {
311                            if is_last {
312                                if cursor.entries[idx].mode.is_tree() {
313                                    match mode {
314                                        RemoveMode::Any => {}
315                                        RemoveMode::IfLeaf => break,
316                                        RemoveMode::LeafOnly => {
317                                            let rela_path = path_with_component(path_buf.as_bstr(), name);
318                                            bail!(validation(format!(
319                                                "Cannot remove \"{rela_path}\" as leaf entry because it is a tree"
320                                            )));
321                                        }
322                                    }
323                                }
324                                cursor.entries.remove(idx);
325                                break;
326                            } else {
327                                let entry = &cursor.entries[idx];
328                                if entry.mode.is_tree() {
329                                    Some(entry.oid)
330                                } else {
331                                    break;
332                                }
333                            }
334                        }
335                        EditMode::Upsert(kind, id, _mode) => {
336                            let entry = &mut cursor.entries[idx];
337                            if is_last {
338                                // unconditionally overwrite what's there.
339                                entry.oid = id;
340                                needs_sorting = check_type_change(entry);
341                                entry.mode = kind.into();
342                                None
343                            } else if entry.mode.is_tree() {
344                                // Possibly lookup the existing tree on our way down the path.
345                                Some(entry.oid)
346                            } else {
347                                // it is no tree, but we are traversing a path, so turn it into one.
348                                entry.oid = id.kind().null();
349                                needs_sorting = check_type_change(entry);
350                                entry.mode = EntryKind::Tree.into();
351                                None
352                            }
353                        }
354                    }
355                }
356                Err(insertion_idx) => match edit {
357                    EditMode::Remove(_) => break,
358                    EditMode::Upsert(kind, id, _mode) => {
359                        cursor.entries.insert(
360                            insertion_idx,
361                            tree::Entry {
362                                filename: name.into(),
363                                mode: if is_last { kind.into() } else { EntryKind::Tree.into() },
364                                oid: if is_last { id } else { id.kind().null() },
365                            },
366                        );
367                        None
368                    }
369                },
370            };
371            if needs_sorting {
372                cursor.entries.sort();
373            }
374            if is_last && matches!(edit, EditMode::Upsert(_, _, UpsertMode::Normal)) {
375                break;
376            }
377            let stop_at_unedited_empty_tree =
378                matches!(edit, EditMode::Remove(RemoveMode::LeafOnly | RemoveMode::IfLeaf))
379                    && tree_to_lookup.is_some_and(|id| id.is_empty_tree());
380            push_path_component(&mut path_buf, name);
381            cursor = match self.trees.entry(path_buf.clone()) {
382                hash_map::Entry::Occupied(e) => e.into_mut(),
383                hash_map::Entry::Vacant(_) if stop_at_unedited_empty_tree => break,
384                hash_map::Entry::Vacant(e) => e.insert(
385                    if let Some(tree_id) = tree_to_lookup.filter(|tree_id| !tree_id.is_empty_tree()) {
386                        self.find.find_tree(&tree_id, &mut self.tree_buf)?.into()
387                    } else {
388                        Tree::default()
389                    },
390                ),
391            };
392        }
393        drop(path_buf);
394        Ok(self)
395    }
396
397    /// Set the root tree of the modification to `root`, assuring it has a well-known state.
398    ///
399    /// Note that this erases all previous edits.
400    ///
401    /// This is useful if the same editor is re-used for various trees.
402    pub fn set_root(&mut self, root: Tree) -> &mut Self {
403        self.trees.clear();
404        self.trees.insert(empty_path(), root);
405        self
406    }
407}
408
409mod cursor {
410    use bstr::{BStr, BString};
411
412    use gix_error::Result;
413    use gix_hash::ObjectId;
414
415    use crate::{
416        Tree, tree,
417        tree::{
418            Editor, EntryKind,
419            editor::{Cursor, EditMode, RemoveMode, UpsertMode, WriteMode},
420        },
421    };
422
423    /// Cursor handling
424    impl<'a> Editor<'a> {
425        /// Turn ourselves as a cursor, which points to the same tree as the editor.
426        ///
427        /// This is useful if a method takes a [`Cursor`], not an [`Editor`].
428        pub fn to_cursor(&mut self) -> Cursor<'_, 'a> {
429            Cursor {
430                parent: self,
431                prefix: BString::default(),
432            }
433        }
434
435        /// Create a cursor at the given `rela_path`, which must be a tree or is turned into a tree as its own edit.
436        ///
437        /// The returned cursor will then allow applying edits to the tree at `rela_path` as root.
438        /// If `rela_path` is a single empty string, it is equivalent to using the current instance itself.
439        pub fn cursor_at<I, C>(&mut self, rela_path: I) -> Result<Cursor<'_, 'a>>
440        where
441            I: IntoIterator<Item = C>,
442            C: AsRef<BStr>,
443        {
444            self.path_buf.borrow_mut().clear();
445            self.upsert_or_remove_at_pathbuf(
446                rela_path,
447                EditMode::Upsert(EntryKind::Tree, self.object_hash.null(), UpsertMode::AssureTreeOnly),
448            )?;
449            let prefix = self.path_buf.borrow_mut().clone();
450            Ok(Cursor {
451                prefix, /* set during the upsert call */
452                parent: self,
453            })
454        }
455    }
456
457    impl Cursor<'_, '_> {
458        /// Obtain the entry at `rela_path` or return `None` if none was found, or the tree wasn't yet written
459        /// to that point.
460        /// Note that after [writing](Self::write) only the root path remains, all other intermediate trees are removed.
461        /// The entry can be anything that can be stored in a tree, but may have a null-id if it's a newly
462        /// inserted tree. Also, ids of trees might not be accurate as they may have been changed in memory.
463        pub fn get<I, C>(&self, rela_path: I) -> Option<&tree::Entry>
464        where
465            I: IntoIterator<Item = C>,
466            C: AsRef<BStr>,
467        {
468            self.parent.path_buf.borrow_mut().clone_from(&self.prefix);
469            self.parent.get_inner(rela_path)
470        }
471
472        /// Like [`Editor::upsert()`], but with the constraint of only editing in this cursor's tree.
473        pub fn upsert<I, C>(&mut self, rela_path: I, kind: EntryKind, id: ObjectId) -> Result<&mut Self>
474        where
475            I: IntoIterator<Item = C>,
476            C: AsRef<BStr>,
477        {
478            self.parent.path_buf.borrow_mut().clone_from(&self.prefix);
479            self.parent
480                .upsert_or_remove_at_pathbuf(rela_path, EditMode::Upsert(kind, id, UpsertMode::Normal))?;
481            Ok(self)
482        }
483
484        /// Like [`Editor::remove()`], but with the constraint of only editing in this cursor's tree.
485        pub fn remove<I, C>(&mut self, rela_path: I) -> Result<&mut Self>
486        where
487            I: IntoIterator<Item = C>,
488            C: AsRef<BStr>,
489        {
490            self.parent.path_buf.borrow_mut().clone_from(&self.prefix);
491            self.parent
492                .upsert_or_remove_at_pathbuf(rela_path, EditMode::Remove(RemoveMode::Any))?;
493            Ok(self)
494        }
495
496        /// Like [`Editor::remove_leaf()`], but with the constraint of only editing in this cursor's tree.
497        pub fn remove_leaf<I, C>(&mut self, rela_path: I) -> Result<&mut Self>
498        where
499            I: IntoIterator<Item = C>,
500            C: AsRef<BStr>,
501        {
502            self.parent.path_buf.borrow_mut().clone_from(&self.prefix);
503            self.parent
504                .upsert_or_remove_at_pathbuf(rela_path, EditMode::Remove(RemoveMode::LeafOnly))?;
505            Ok(self)
506        }
507
508        /// Like [`Editor::write()`], but will write only the subtree of the cursor.
509        pub fn write<E>(
510            &mut self,
511            out: impl FnMut(&Tree) -> std::result::Result<ObjectId, E>,
512        ) -> std::result::Result<ObjectId, E> {
513            self.parent.path_buf.borrow_mut().clone_from(&self.prefix);
514            self.parent.write_at_pathbuf(out, WriteMode::FromCursor)
515        }
516    }
517}
518
519#[derive(Copy, Clone, Eq, PartialEq)]
520enum UpsertMode {
521    Normal,
522    /// Only make sure there is a tree at the given location (requires kind tree and null-id)
523    AssureTreeOnly,
524}
525
526#[derive(Copy, Clone, Eq, PartialEq)]
527enum RemoveMode {
528    /// Remove any entry, including entire subtrees.
529    Any,
530    /// Only remove leaf entries, and reject an existing tree at the target path.
531    LeafOnly,
532    /// Only remove leaf entries, leaving an existing tree at the target path untouched.
533    IfLeaf,
534}
535
536#[derive(Copy, Clone)]
537enum EditMode {
538    Remove(RemoveMode),
539    /// Insert or replace an entry of `kind` and `id` according to the given mode.
540    Upsert(EntryKind, ObjectId, UpsertMode),
541}
542
543enum WriteMode {
544    Normal,
545    /// Perform less cleanup to assure parent-editor still stays intact
546    FromCursor,
547}
548
549fn cmp_entry_with_name(a: &tree::Entry, filename: &BStr, is_tree: bool) -> Ordering {
550    tree::name_order(&a.filename, a.mode.is_tree(), filename, is_tree)
551}
552
553fn filename(path: &BStr) -> &BStr {
554    path.rfind_byte(b'/').map_or(path, |pos| &path[pos + 1..])
555}
556
557fn empty_path() -> BString {
558    BString::default()
559}
560
561fn push_path_component(base: &mut BString, component: &[u8]) -> usize {
562    let prev_len = base.len();
563    debug_assert_ne!(base.last(), Some(&b'/'));
564    if !base.is_empty() {
565        base.push_byte(b'/');
566    }
567    base.push_str(component);
568    prev_len
569}
570
571fn path_with_component(base: &BStr, component: &BStr) -> BString {
572    if base.is_empty() {
573        component.into()
574    } else {
575        let mut out = base.to_owned();
576        out.push_byte(b'/');
577        out.push_str(component);
578        out
579    }
580}
gix_object/tree/editor.rs

gix_object/tree/
editor.rs
