octopus-merge (part 4: rewrite tracking in plumbing)

[Byron]

Integrate everything on plumbing level and create a multi-tree merge with rename support.

Follow-up of #1611.

Tasks

• [x] tree-diff with 'chunked' directory additions/deletions
  • keep more information for later rename tracking
• [x] rename-tracking can handle directories with relations
• [x] rename-tracking built-into tree-diff - pull it down from gix into the lower levels.
  • [x] assure it handles relations - probably there is nothing to do on plumbing level, except for making the information available.
  • [x] port tests
• [x] gix uses lower-level tree-diff with rewrites
  • [x] add diff_tree_to_tree() to make it way easier to figure out how to perform such a diff.
    • this also helps to make future diffs easier, if they make sense, as status() is its own set of diffs and we could see it that way.

Very Next PR

• [ ] baseline tests for tree-merging
• [ ] make tests pass
  • multi-tree traversal (without wildcard support!) - for now, let's just do it 'the simple' way and perform two diffs
  • optimization idea for when there are numbers: a 'brute force' implementation that uses threads would benefit from the ability to re-use object caches of a repo that has seen the base-tree already, but overall, who knows*
  • there is tests for merging merge-bases in diff3-conflict-markers
    • diff3-conflict-markers.sh - be sure to capture the 'empty tree' label , but also other special cases
    • See also, all the merge options

Next PR / Outscoped

• Submodule merges are also possible! Maybe outscope it though! libgit2 also doesn't try it.
• textconv with context, see this gist for details.
  • There seem to be different 'tiers' of tools, some don't get GIT_DIR set, others do.
  • It also seems that diff-programs get too much context right now, but that depends on how much is passed to them by the caller as gix-command::Context.
• How to model virtual-merge-bases? Can be none or many, user should have control over how this is done.
• Actual tree-based merging
• Make blob-merge based conflict handling possible in the tree merge from gix at least. - not needed for now

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
• Note that merge-ORT cannot properly handle renames within renamed directories, ending up with the source of the subdir-rename still present.

  ❯ git ls-tree -r $(git merge-tree main feat)
  100644 blob e69de29bb2d1d6434b8b29ae775ad8c2e48c5391    a
  100644 blob e69de29bb2d1d6434b8b29ae775ad8c2e48c5391    git-sec-renamed/2
  100644 blob e69de29bb2d1d6434b8b29ae775ad8c2e48c5391    git-sec-renamed/7
  100644 blob e69de29bb2d1d6434b8b29ae775ad8c2e48c5391    git-sec-renamed/subdir/6
  100644 blob e69de29bb2d1d6434b8b29ae775ad8c2e48c5391    git-sec/subdir-renamed/6
  100644 blob e69de29bb2d1d6434b8b29ae775ad8c2e48c5391    git-sequencer
  100644 blob e69de29bb2d1d6434b8b29ae775ad8c2e48c5391    gix/5
  100644 blob e69de29bb2d1d6434b8b29ae775ad8c2e48c5391    h

• Must make sure that possible types of conflicts are properly communicated, to not degenerate information
• It puts conflict-markers in the blobs of the result tree, with annotations to provide additional context
• Need resolution configuration, see git2::MergeOptions.
• data stored by path, and is interned in the map to allow pointer-based comparisons
  • merge-info with everything one needs to know, also related to renames
  • or conflict information
  • it uses a memory-pool/arena to get memory for many paths all at once (and also release it like that)
• paths start out as conflicted, and then can later be changed to non-conflicting if a content-based merged succeeded.
  • If it remains conflicts, the meta-data is used to produce an 'as merged as possible' version with conflict markers that can be checked out to the working tree.
• hunks can partially overlap, but can also be resolved line-by line to some extend.