octopus-merge

[Byron]

Implement an octopus merge based on trees, and (mostly) equivalent to merge-ORT in Git.

Related to https://github.com/gitbutlerapp/gitbutler/pull/4793.

Tasks

• [ ] TBD

Research

Everything is about MergeORT.

• it uses an empty tree if there is no merge-base - we must allow the same.
• it allows for multiple merge-bases, creating a virtual one by merging all merge-bases together using the same algorithm, recursively.
• merges can have conflicts without a individual files being involved, for instance when directory renames clash
• Must make sure that possible types of conflicts are properly communicated, to not degenerate information
• It puts conflict-markers in the result tree, with annotations to provide additional context
• Need resolution configuration, see git2::MergeOptions.

Handle Special Cases

• A file was renamed differently
• deal with "merge.directoryRenames"

Questions

Is git2::merge_trees() a trivial merge? Does it handle all the cases of MergeORT?

How does rename-tracking affect a tree-merge?

How is an octopus merge implemented, particularly with Merge ORT?

References

• https://git-scm.com/docs/git-merge-tree