Function tree

pub fn tree<'objects, E>(
    base_tree: &oid,
    our_tree: &oid,
    their_tree: &oid,
    labels: Labels<'_>,
    objects: &'objects impl FindObjectOrHeader,
    write_blob_to_odb: impl FnMut(&[u8]) -> Result<ObjectId, E>,
    diff_state: &mut State,
    diff_resource_cache: &mut Platform,
    blob_merge: &mut Platform,
    options: Options,
) -> Result<Outcome<'objects>, Error>
where
    E: Into<Box<dyn Error + Send + Sync + 'static>>,

Perform a merge between our_tree and their_tree, using base_tree as merge-base. Note that base_tree can be an empty tree to indicate ‘no common ancestor between the two sides’.

• labels are relevant for text-merges and will be shown in conflicts.
• objects provides access to trees when diffing them.
• write_blob_to_odb(content) -> Result<ObjectId, E> writes newly merged content into the odb to obtain an id that will be used in merged trees.
• diff_state is state used for diffing trees.
• diff_resource_cache is used for similarity checks.
• blob_merge is a pre-configured platform to merge any content.
  • Note that it shouldn’t be allowed to read from the worktree, given that this is a tree-merge.
• options are used to affect how the merge is performed.

Unbiased (Ours x Theirs == Theirs x Ours)

The algorithm is implemented so that the result is the same no matter how the sides are ordered.

Differences to Merge-ORT

Merge-ORT (Git) defines the desired outcomes where are merely mimicked here. The algorithms are different, and it’s clear that Merge-ORT is significantly more elaborate and general.

It also writes out trees once it’s done with them in a form of reduction process, here an editor is used to keep only the changes, to be written by the caller who receives it as part of the result. This may use more memory in the worst case scenario, but in average shouldn’t perform much worse due to the natural sparsity of the editor.

Our rename-tracking also produces copy information, but we discard it and simply treat it like an addition.

Finally, our algorithm will consider reasonable solutions to merge-conflicts as conflicts that are resolved, leaving only content with conflict markers as unresolved ones.

Performance

Note that objects should have an object cache to greatly accelerate tree-retrieval.