use std::{    cmp::Ordering,    collections::{hash_map, HashMap},    fmt::Formatter,}; use bstr::{BStr, BString, ByteSlice, ByteVec};use gix_hash::ObjectId; use crate::{    tree,    tree::{Editor, EntryKind},    Tree,}; /// A way to constrain all [tree-edits](Editor) to a given subtree.pub struct Cursor<'a, 'find> {    /// The underlying editor    parent: &'a mut Editor<'find>,    /// Our own location, used as prefix for all operations.    /// Note that it's assumed to always contain a tree.    prefix: BString,} impl std::fmt::Debug for Editor<'_> {    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {        f.debug_struct("Editor")            .field("object_hash", &self.object_hash)            .field("path_buf", &self.path_buf)            .field("trees", &self.trees)            .finish()    }} /// The error returned by [Editor] or [Cursor] edit operation.#[derive(Debug, thiserror::Error)]#[allow(missing_docs)]pub enum Error {    #[error("Empty path components are not allowed")]    EmptyPathComponent,    #[error(transparent)]    FindExistingObject(#[from] crate::find::existing_object::Error),} /// Lifecycleimpl<'a> Editor<'a> {    /// Create a new editor that uses `root` as base for all edits. Use `find` to lookup existing    /// trees when edits are made. Each tree will only be looked-up once and then edited in place from    /// that point on.    /// `object_hash` denotes the kind of hash to create.    pub fn new(root: Tree, find: &'a dyn crate::FindExt, object_hash: gix_hash::Kind) -> Self {        Editor {            find,            object_hash,            trees: HashMap::from_iter(Some((empty_path(), root))),            path_buf: BString::from(Vec::with_capacity(256)).into(),            tree_buf: Vec::with_capacity(512),        }    }} /// Operationsimpl Editor<'_> {    /// Write the entire in-memory state of all changed trees (and only changed trees) to `out`, and remove    /// written portions from our state except for the root tree, which affects [`get()`](Editor::get()).    /// Note that the returned object id *can* be the empty tree if everything was removed or if nothing    /// was added to the tree.    ///    /// The last call to `out` will be the changed root tree, whose object-id will also be returned.    /// `out` is free to do any kind of additional validation, like to assure that all entries in the tree exist.    /// We don't assure that as there is no validation that inserted entries are valid object ids.    ///    /// Future calls to [`upsert`](Self::upsert) or similar will keep working on the last seen state of the    /// just-written root-tree.    /// If this is not desired, use [set_root()](Self::set_root()).    ///    /// ### Validation    ///    /// Note that no additional validation is performed to assure correctness of entry-names.    /// It is absolutely and intentionally possible to write out invalid trees with this method.    /// Higher layers are expected to perform detailed validation.    pub fn write<E>(&mut self, out: impl FnMut(&Tree) -> Result<ObjectId, E>) -> Result<ObjectId, E> {        self.path_buf.borrow_mut().clear();        self.write_at_pathbuf(out, WriteMode::Normal)    }     /// Remove the entry at `rela_path`, loading all trees on the path accordingly.    /// It's no error if the entry doesn't exist, or if `rela_path` doesn't lead to an existing entry at all.    ///    /// Note that trying to remove a path with an empty component is also forbidden.    pub fn remove<I, C>(&mut self, rela_path: I) -> Result<&mut Self, Error>    where        I: IntoIterator<Item = C>,        C: AsRef<BStr>,    {        self.path_buf.borrow_mut().clear();        self.upsert_or_remove_at_pathbuf(rela_path, None)    }     /// Obtain the entry at `rela_path` or return `None` if none was found, or the tree wasn't yet written    /// to that point.    /// Note that after [writing](Self::write) only the root path remains, all other intermediate trees are removed.    /// The entry can be anything that can be stored in a tree, but may have a null-id if it's a newly    /// inserted tree. Also, ids of trees might not be accurate as they may have been changed in memory.    pub fn get<I, C>(&self, rela_path: I) -> Option<&tree::Entry>    where        I: IntoIterator<Item = C>,        C: AsRef<BStr>,    {        self.path_buf.borrow_mut().clear();        self.get_inner(rela_path)    }     /// Insert a new entry of `kind` with `id` at `rela_path`, an iterator over each path component in the tree,    /// like `a/b/c`. Names are matched case-sensitively.    ///    /// Existing leaf-entries will be overwritten unconditionally, and it is assumed that `id` is available in the object database    /// or will be made available at a later point to assure the integrity of the produced tree.    ///    /// Intermediate trees will be created if they don't exist in the object database, otherwise they will be loaded and entries    /// will be inserted into them instead.    ///    /// Note that `id` can be [null](ObjectId::null()) to create a placeholder. These will not be written, and paths leading    /// through them will not be considered a problem.    ///    /// `id` can also be an empty tree, along with [the respective `kind`](EntryKind::Tree), even though that's normally not allowed    /// in Git trees.    pub fn upsert<I, C>(&mut self, rela_path: I, kind: EntryKind, id: ObjectId) -> Result<&mut Self, Error>    where        I: IntoIterator<Item = C>,        C: AsRef<BStr>,    {        self.path_buf.borrow_mut().clear();        self.upsert_or_remove_at_pathbuf(rela_path, Some((kind, id, UpsertMode::Normal)))    }     fn get_inner<I, C>(&self, rela_path: I) -> Option<&tree::Entry>    where        I: IntoIterator<Item = C>,        C: AsRef<BStr>,    {        let mut path_buf = self.path_buf.borrow_mut();        let mut cursor = self.trees.get(path_buf.as_bstr()).expect("root is always present");        let mut rela_path = rela_path.into_iter().peekable();        while let Some(name) = rela_path.next() {            let name = name.as_ref();            let is_last = rela_path.peek().is_none();            match cursor                .entries                .binary_search_by(|e| cmp_entry_with_name(e, name, true))                .or_else(|_| cursor.entries.binary_search_by(|e| cmp_entry_with_name(e, name, false)))            {                Ok(idx) if is_last => return Some(&cursor.entries[idx]),                Ok(idx) => {                    if cursor.entries[idx].mode.is_tree() {                        push_path_component(&mut path_buf, name);                        cursor = self.trees.get(path_buf.as_bstr())?;                    } else {                        break;                    }                }                Err(_) => break,            }        }        None    }     fn write_at_pathbuf<E>(        &mut self,        mut out: impl FnMut(&Tree) -> Result<ObjectId, E>,        mode: WriteMode,    ) -> Result<ObjectId, E> {        assert_ne!(self.trees.len(), 0, "there is at least the root tree");         // back is for children, front is for parents.        let path_buf = self.path_buf.borrow_mut();        let mut parents = vec![(            None::<usize>,            path_buf.clone(),            self.trees                .remove(path_buf.as_bstr())                .expect("root tree is always present"),        )];        let mut children = Vec::new();        while let Some((parent_idx, mut rela_path, mut tree)) = children.pop().or_else(|| parents.pop()) {            let mut all_entries_unchanged_or_written = true;            for entry in &tree.entries {                if entry.mode.is_tree() {                    let prev_len = push_path_component(&mut rela_path, &entry.filename);                    if let Some(sub_tree) = self.trees.remove(&rela_path) {                        all_entries_unchanged_or_written = false;                        let next_parent_idx = parents.len();                        children.push((Some(next_parent_idx), rela_path.clone(), sub_tree));                    }                    rela_path.truncate(prev_len);                }            }            if all_entries_unchanged_or_written {                tree.entries.retain(|e| !e.oid.is_null());                if let Some((_, _, parent_to_adjust)) =                    parent_idx.map(|idx| parents.get_mut(idx).expect("always present, pointing towards zero"))                {                    let name = filename(rela_path.as_bstr());                    let entry_idx = parent_to_adjust                        .entries                        .binary_search_by(|e| cmp_entry_with_name(e, name, true))                        .expect("the parent always knows us by name");                    if tree.entries.is_empty() {                        parent_to_adjust.entries.remove(entry_idx);                    } else {                        match out(&tree) {                            Ok(id) => {                                parent_to_adjust.entries[entry_idx].oid = id;                            }                            Err(err) => {                                let root_tree = parents.into_iter().next().expect("root wasn't consumed yet");                                self.trees.insert(root_tree.1, root_tree.2);                                return Err(err);                            }                        }                    }                } else if parents.is_empty() {                    debug_assert!(children.is_empty(), "we consume children before parents");                    debug_assert_eq!(rela_path, **path_buf, "this should always be the root tree");                     // There may be left-over trees if they are replaced with blobs for example.                    match out(&tree) {                        Ok(id) => {                            let root_tree_id = id;                            match mode {                                WriteMode::Normal => {                                    self.trees.clear();                                }                                WriteMode::FromCursor => {}                            }                            self.trees.insert(rela_path, tree);                            return Ok(root_tree_id);                        }                        Err(err) => {                            self.trees.insert(rela_path, tree);                            return Err(err);                        }                    }                } else if !tree.entries.is_empty() {                    out(&tree)?;                }            } else {                parents.push((parent_idx, rela_path, tree));            }        }         unreachable!("we exit as soon as everything is consumed")    }     fn upsert_or_remove_at_pathbuf<I, C>(        &mut self,        rela_path: I,        kind_and_id: Option<(EntryKind, ObjectId, UpsertMode)>,    ) -> Result<&mut Self, Error>    where        I: IntoIterator<Item = C>,        C: AsRef<BStr>,    {        let mut path_buf = self.path_buf.borrow_mut();        let mut cursor = self.trees.get_mut(path_buf.as_bstr()).expect("root is always present");        let mut rela_path = rela_path.into_iter().peekable();        let new_kind_is_tree = kind_and_id.is_some_and(|(kind, _, _)| kind == EntryKind::Tree);        while let Some(name) = rela_path.next() {            let name = name.as_ref();            if name.is_empty() {                return Err(Error::EmptyPathComponent);            }            let is_last = rela_path.peek().is_none();            let mut needs_sorting = false;            let current_level_must_be_tree = !is_last || new_kind_is_tree;            let check_type_change = |entry: &tree::Entry| entry.mode.is_tree() != current_level_must_be_tree;            let tree_to_lookup = match cursor                .entries                .binary_search_by(|e| cmp_entry_with_name(e, name, false))                .or_else(|file_insertion_idx| {                    cursor                        .entries                        .binary_search_by(|e| cmp_entry_with_name(e, name, true))                        .map_err(|dir_insertion_index| {                            if current_level_must_be_tree {                                dir_insertion_index                            } else {                                file_insertion_idx                            }                        })                }) {                Ok(idx) => {                    match kind_and_id {                        None => {                            if is_last {                                cursor.entries.remove(idx);                                break;                            } else {                                let entry = &cursor.entries[idx];                                if entry.mode.is_tree() {                                    Some(entry.oid)                                } else {                                    break;                                }                            }                        }                        Some((kind, id, _mode)) => {                            let entry = &mut cursor.entries[idx];                            if is_last {                                // unconditionally overwrite what's there.                                entry.oid = id;                                needs_sorting = check_type_change(entry);                                entry.mode = kind.into();                                None                            } else if entry.mode.is_tree() {                                // Possibly lookup the existing tree on our way down the path.                                Some(entry.oid)                            } else {                                // it is no tree, but we are traversing a path, so turn it into one.                                entry.oid = id.kind().null();                                needs_sorting = check_type_change(entry);                                entry.mode = EntryKind::Tree.into();                                None                            }                        }                    }                }                Err(insertion_idx) => match kind_and_id {                    None => break,                    Some((kind, id, _mode)) => {                        cursor.entries.insert(                            insertion_idx,                            tree::Entry {                                filename: name.into(),                                mode: if is_last { kind.into() } else { EntryKind::Tree.into() },                                oid: if is_last { id } else { id.kind().null() },                            },                        );                        None                    }                },            };            if needs_sorting {                cursor.entries.sort();            }            if is_last && kind_and_id.is_some_and(|(_, _, mode)| mode == UpsertMode::Normal) {                break;            }            push_path_component(&mut path_buf, name);            cursor = match self.trees.entry(path_buf.clone()) {                hash_map::Entry::Occupied(e) => e.into_mut(),                hash_map::Entry::Vacant(e) => e.insert(                    if let Some(tree_id) = tree_to_lookup.filter(|tree_id| !tree_id.is_empty_tree()) {                        self.find.find_tree(&tree_id, &mut self.tree_buf)?.into()                    } else {                        Tree::default()                    },                ),            };        }        drop(path_buf);        Ok(self)    }     /// Set the root tree of the modification to `root`, assuring it has a well-known state.    ///    /// Note that this erases all previous edits.    ///    /// This is useful if the same editor is re-used for various trees.    pub fn set_root(&mut self, root: Tree) -> &mut Self {        self.trees.clear();        self.trees.insert(empty_path(), root);        self    }} mod cursor {    use bstr::{BStr, BString};    use gix_hash::ObjectId;     use crate::{        tree,        tree::{            editor::{Cursor, UpsertMode, WriteMode},            Editor, EntryKind,        },        Tree,    };     /// Cursor handling    impl<'a> Editor<'a> {        /// Turn ourselves as a cursor, which points to the same tree as the editor.        ///        /// This is useful if a method takes a [`Cursor`], not an [`Editor`].        pub fn to_cursor(&mut self) -> Cursor<'_, 'a> {            Cursor {                parent: self,                prefix: BString::default(),            }        }         /// Create a cursor at the given `rela_path`, which must be a tree or is turned into a tree as its own edit.        ///        /// The returned cursor will then allow applying edits to the tree at `rela_path` as root.        /// If `rela_path` is a single empty string, it is equivalent to using the current instance itself.        pub fn cursor_at<I, C>(&mut self, rela_path: I) -> Result<Cursor<'_, 'a>, super::Error>        where            I: IntoIterator<Item = C>,            C: AsRef<BStr>,        {            self.path_buf.borrow_mut().clear();            self.upsert_or_remove_at_pathbuf(                rela_path,                Some((EntryKind::Tree, self.object_hash.null(), UpsertMode::AssureTreeOnly)),            )?;            let prefix = self.path_buf.borrow_mut().clone();            Ok(Cursor {                prefix, /* set during the upsert call */                parent: self,            })        }    }     impl Cursor<'_, '_> {        /// Obtain the entry at `rela_path` or return `None` if none was found, or the tree wasn't yet written        /// to that point.        /// Note that after [writing](Self::write) only the root path remains, all other intermediate trees are removed.        /// The entry can be anything that can be stored in a tree, but may have a null-id if it's a newly        /// inserted tree. Also, ids of trees might not be accurate as they may have been changed in memory.        pub fn get<I, C>(&self, rela_path: I) -> Option<&tree::Entry>        where            I: IntoIterator<Item = C>,            C: AsRef<BStr>,        {            self.parent.path_buf.borrow_mut().clone_from(&self.prefix);            self.parent.get_inner(rela_path)        }         /// Like [`Editor::upsert()`], but with the constraint of only editing in this cursor's tree.        pub fn upsert<I, C>(&mut self, rela_path: I, kind: EntryKind, id: ObjectId) -> Result<&mut Self, super::Error>        where            I: IntoIterator<Item = C>,            C: AsRef<BStr>,        {            self.parent.path_buf.borrow_mut().clone_from(&self.prefix);            self.parent                .upsert_or_remove_at_pathbuf(rela_path, Some((kind, id, UpsertMode::Normal)))?;            Ok(self)        }         /// Like [`Editor::remove()`], but with the constraint of only editing in this cursor's tree.        pub fn remove<I, C>(&mut self, rela_path: I) -> Result<&mut Self, super::Error>        where            I: IntoIterator<Item = C>,            C: AsRef<BStr>,        {            self.parent.path_buf.borrow_mut().clone_from(&self.prefix);            self.parent.upsert_or_remove_at_pathbuf(rela_path, None)?;            Ok(self)        }         /// Like [`Editor::write()`], but will write only the subtree of the cursor.        pub fn write<E>(&mut self, out: impl FnMut(&Tree) -> Result<ObjectId, E>) -> Result<ObjectId, E> {            self.parent.path_buf.borrow_mut().clone_from(&self.prefix);            self.parent.write_at_pathbuf(out, WriteMode::FromCursor)        }    }} #[derive(Copy, Clone, Eq, PartialEq)]enum UpsertMode {    Normal,    /// Only make sure there is a tree at the given location (requires kind tree and null-id)    AssureTreeOnly,} enum WriteMode {    Normal,    /// Perform less cleanup to assure parent-editor still stays intact    FromCursor,} fn cmp_entry_with_name(a: &tree::Entry, filename: &BStr, is_tree: bool) -> Ordering {    let common = a.filename.len().min(filename.len());    a.filename[..common].cmp(&filename[..common]).then_with(|| {        let a = a.filename.get(common).or_else(|| a.mode.is_tree().then_some(&b'/'));        let b = filename.get(common).or_else(|| is_tree.then_some(&b'/'));        a.cmp(&b)    })} fn filename(path: &BStr) -> &BStr {    path.rfind_byte(b'/').map_or(path, |pos| &path[pos + 1..])} fn empty_path() -> BString {    BString::default()} fn push_path_component(base: &mut BString, component: &[u8]) -> usize {

Lines 1–500 of 508. Load more