Re: [PATCH 0/2] RFC: implement new zdiff3 conflict style

[Elijah Newren <newren@gmail.com>]

On Tue, Jun 15, 2021 at 11:16 PM Johannes Sixt <j6t@kdbg.org> wrote:
>
> Am 15.06.21 um 23:45 schrieb Elijah Newren:
> > On Tue, Jun 15, 2021 at 2:36 PM Johannes Sixt <j6t@kdbg.org> wrote:
> >>
> >> Am 15.06.21 um 07:16 schrieb Elijah Newren via GitGitGadget:
> >>> Implement a zealous diff3, or "zdiff3". This new mode is identical to
> >>> ordinary diff3 except that it allows compaction of common lines between the
> >>> two sides of history, if those common lines occur at the beginning or end of
> >>> a conflict hunk.
> >>
> >> As a data point, I tried this series (cf9d93e547 en/zdiff3) on my
> >> criss-cross merge test case that started this adventure, and it produces
> >> the very same output as diff3; cf.
> >> https://lore.kernel.org/git/60883e1b-787f-5ec2-a9af-f2f6757d3c43@kdbg.org/
> >
> > That's good to hear; your two sides had no common text at the
> > beginning or end of the conflict hunk, so I wouldn't expect zdiff3 to
> > change that particular example.
> >
> > The XDL_MERGE_FAVOR_BASE idea (cf.
> > https://lore.kernel.org/git/20210611190235.1970106-1-newren@gmail.com/),
> > though would I think simplify the diff3 conflict markers in your
> > example to
> >
> > <<<<<<< HEAD
> >     CClustering ComputeSSLClusters(double threshPercent, const
> > CDataInfo* scale) const override;
> >     void ComputeDist(DistFunc distFunc, CDoubleArray& dist,
> >         double& minDist, double& maxDist) const;
> >     double EstimateNodeDist2() const override;
> >     std::vector<double> EstimateNeighborMinDist() const override;
> > ||||||| merged common ancestors
> >     CClustering ComputeClusters(const double* dist, double threshold,
> >         const CDataInfo* scale) const override;
> >     virtual void ComputeDist(DistFunc distFunc, CDoubleArray& dist,
> >         double& minDist, double& maxDist);
> >     virtual void ComputeUMatrix();
> >     virtual void ComputeKNearest(int K, const double*,
> >         Neighborhood& result) const;
> > =======
> >     CClustering ComputeSSLClusters(double threshPercent,
> >         const CDoubleArray& compWeights, const CDataInfo* scale) const override;
> >     static void ComputeDist(const CNetNodeHolder& vecs, CDoubleArray& dist,
> >         double& minDist, double& maxDist);
> >>>>>>>> no-compweights-in-cnet
> >
> > That seems like it might be nicer, but I don't do many criss-cross
> > merges myself so it'd be nice to get opinions of others like you who
> > do.
>
> That *is* nicer as it is just the regular conflict with some base
> context. Does that mean that the regular recursive merge is a bit sloppy
> because it throws away too many conflicts that occur in virtual
> ancestors? Even if that is the case, I couldn't tell whether that is a
> disadvantage or not, as I've actually never seen nested conflicts in the
> past; the diff3 test was the first time I saw one.
>
> With the referenced patch applied (after a small tweak around needs_cr
> to make it compile), my testcase does indeed produce the above conflict
> under zdiff3 mode. The diff3 mode, OTOH, produces an exceedingly large
> non-nested and obviously incorrect conflict (I'm not going to post it
> here): our and their side are large and share a lot of text, but the
> base part is identical to the above and is far too small.

The thing about XDL_MERGE_FAVOR_BASE in combination with a recursive
merge, is that if you have two merge-bases, then XDL_MERGE_FAVOR_BASE
will put the text from the merge base of the merge-bases in the
"original text" region.  If your merge bases themselves had multiple
merge-bases, and those merge bases in turn had multiple merge-bases,
etc., so that you end up with a deeply nested recursive merge, then
XDL_MERGE_FAVOR_BASE will cause you to get the "original text" filled
by the text from some ancient ancestor.  The net result is that it
makes it look like you have done a three-way merge between the two
sides you expect with a really ancient merge base.  So, a really small
original text is probably something to be expected from the
XDL_MERGE_FAVOR_BASE patch.

The fact that zdiff3 shrinks it down considerably reflects the fact
that your two sides had long sections of code that matched at the
beginning and end of the conflict hunk.  So it sounds to me like both
pieces were behaving implementationally as designed for your testcase.

Whether using "ancient original text" makes sense in general rather
than using a "more recent original text" (in the form of an attempted
merge of the merge-bases complete with conflict markers), feels like
it's one of those tradeoff things that I figured those who do lots of
criss-cross merges should weigh in on rather than me.