Re: Merging bug (wrong conflicts)

[Jacob Burckhardt]

Karl Tomlinson writes:
> The problem you mention has been around for a while.  Some attempts have
> been made to improve things.  These have solved some problems and
> created others.
> 
> see http://www.mail-archive.com/bug-cvs%40gnu.org/msg00429.html
> 
> The problem is in diff3, which runs two 2-way diffs and then merges them
> together to make a 3-way diff.  The 2-way diffs do not always represent
> same changes in the same way.  When they are differences, diff3 starts
> reporting conflicts that aren't really there.
> 
> The first step in solving the problem is to change diff3 so that the two
> 2-way diffs both involve the ancestor file as the common file.  (cvs
> version 1.11 uses YOURFILE as the common file.)  This minimizes the
> number of instances where similar changes exist in the two diffs and
> means that the diffs are more likely to represent the intended changes. 
> The attached patch will do this.  See comments in the patch for more
> info.
> 
> There are still problems if the same changes are made on the branch and
> trunk, but this shouldn't happen too often.  The situation can be
> improved by modifying diff to represent the similar changes more
> consistently.  I can supply patches for diffutils to implement this if
> anyone is interested but haven't transfered the changes to cvs yet.  I
> just use pcl-cvs and ediff when there are conflicts to resolve.

I tested your cvs patch and it works great.  Please try to get it into
the official cvs.  I will be glad to help with that.  For example, I
would volunteer to help make your patch follow all of the rules in
the cvs distribution file HACKING.

I have 8 test cases in which either cvs 1.11 or diff3 merges incorrectly.
Seven of these cases were mailed by various people to the cvs mailing
lists, and the 8th case was discovered by my co-worker but I have not
reported it yet.

I manually verified that your patch merges correctly in 7 of these
test cases.  But one of the cases was so hard to verify that I was not
able to thoroughly verify it (but I am still pretty confident that
your patch works even in this case).

Just in case I made a mistake in my manual verification, I also ran each
test case through fmerge and fmerge agrees with your patched cvs on
every test case.  For more info on the fmerge utility, see:

http://www.canb.auug.org.au/~millerp/fhist.html

So please let me know if you would like my help in making your patch
meet the requirements in the file HACKING.

> 
> Karl.
> 
> Index: ccvs/diff/ChangeLog
> diff -c ccvs/diff/ChangeLog:1.1 ccvs/diff/ChangeLog:1.2
> *** ccvs/diff/ChangeLog:1.1   Fri Jun 30 14:33:00 2000
> --- ccvs/diff/ChangeLog       Wed Jul 26 15:14:56 2000
> ***************
> *** 1,3 ****
> --- 1,18 ----
> + 2000-07-26  Karl Tomlinson  <k.tomlinson@auckland.ac.nz>
> + 
> +     * diff3.c (main): changed the common file of the two diffs to
> +     OLDFILE for merges and edscripts so that the diffs are more likely
> +     to contain the intended changes.  Not changing the horizon-lines
> +     arg for the second diff.  If the two diffs have the same parameters
> +     equal changes in each diff are more likely to appear the same.
> + 
> +     * analyze.c (shift_boundaries): undid Paul Eggert's patch to fix
> +     the diff3 merge bug described in ccvs/doc/DIFFUTILS-2.7-BUG.  The
> +     patch is no longer necessary now that diff3 does its differences
> +     differently.  I think the hunk merges provide a better indication
> +     of the area modified by the user now that the diffs are actually
> +     done between the appropriate revisions.
> + 
>   1999-12-29  Jim Kingdon  <http://developer.redhat.com/>
>   
>       * diff.c (compare_files): Use explicit braces with if-if-else, per
> Index: ccvs/diff/analyze.c
> diff -c ccvs/diff/analyze.c:1.1 ccvs/diff/analyze.c:1.2
> *** ccvs/diff/analyze.c:1.1   Fri Jun 30 14:33:01 2000
> --- ccvs/diff/analyze.c       Wed Jul 26 15:10:46 2000
> ***************
> *** 621,627 ****
>        struct file_data filevec[];
>   {
>     int f;
> !   int inhibit_hunk_merge = horizon_lines != context;
>   
>     for (f = 0; f < 2; f++)
>       {
> --- 621,629 ----
>        struct file_data filevec[];
>   {
>     int f;
> ! 
> !   if (inhibit)
> !     return;
>   
>     for (f = 0; f < 2; f++)
>       {
> ***************
> *** 664,684 ****
>                we can later determine whether the run has grown.  */
>             runlength = i - start;
>   
> !           if (! inhibit_hunk_merge)
>               {
> !               /* Move the changed region back, so long as the
> !                  previous unchanged line matches the last changed one.
> !                  This merges with previous changed regions.  */
> ! 
> !               while (start && equivs[start - 1] == equivs[i - 1])
> !                 {
> !                   changed[--start] = 1;
> !                   changed[--i] = 0;
> !                   while (changed[start - 1])
> !                     start--;
> !                   while (other_changed[--j])
> !                     continue;
> !                 }
>               }
>   
>             /* Set CORRESPONDING to the end of the changed run, at the last
> --- 666,683 ----
>                we can later determine whether the run has grown.  */
>             runlength = i - start;
>   
> !           /* Move the changed region back, so long as the
> !              previous unchanged line matches the last changed one.
> !              This merges with previous changed regions.  */
> ! 
> !           while (start && equivs[start - 1] == equivs[i - 1])
>               {
> !               changed[--start] = 1;
> !               changed[--i] = 0;
> !               while (changed[start - 1])
> !                 start--;
> !               while (other_changed[--j])
> !                 continue;
>               }
>   
>             /* Set CORRESPONDING to the end of the changed run, at the last
> ***************
> *** 686,700 ****
>                CORRESPONDING == I_END means no such point has been found.  */
>             corresponding = other_changed[j - 1] ? i : i_end;
>   
> !           /* Shift the changed region forward, so long as the
> !              first changed line matches the following unchanged one,
> !              but if INHIBIT_HUNK_MERGE is 1 do not shift if
> !              this would merge with another changed region.
>                Do this second, so that if there are no merges,
>                the changed region is moved forward as far as possible.  */
>   
> !           while (i != i_end && equivs[start] == equivs[i]
> !                  && ! (inhibit_hunk_merge & other_changed[j + 1]))
>               {
>                 changed[start++] = 0;
>                 changed[i++] = 1;
> --- 685,697 ----
>                CORRESPONDING == I_END means no such point has been found.  */
>             corresponding = other_changed[j - 1] ? i : i_end;
>   
> !           /* Move the changed region forward, so long as the
> !              first changed line matches the following unchanged one.
> !              This merges with following changed regions.
>                Do this second, so that if there are no merges,
>                the changed region is moved forward as far as possible.  */
>   
> !           while (i != i_end && equivs[start] == equivs[i])
>               {
>                 changed[start++] = 0;
>                 changed[i++] = 1;
> Index: ccvs/diff/diff3.c
> diff -c ccvs/diff/diff3.c:1.1 ccvs/diff/diff3.c:1.2
> *** ccvs/diff/diff3.c:1.1     Fri Jun 30 14:33:01 2000
> --- ccvs/diff/diff3.c Wed Jul 26 15:10:46 2000
> ***************
> *** 169,175 ****
>   static int flagging;
>   
>   /* Number of lines to keep in identical prefix and suffix.  */
> ! static int horizon_lines = 10;
>   
>   /* Use a tab to align output lines (-T).  */
>   static int tab_align_flag;
> --- 169,175 ----
>   static int flagging;
>   
>   /* Number of lines to keep in identical prefix and suffix.  */
> ! static int const horizon_lines = 10;
>   
>   /* Use a tab to align output lines (-T).  */
>   static int tab_align_flag;
> ***************
> *** 368,395 ****
>        file0-file1 diffs didn't line up with the file0-file2 diffs
>        (which is entirely possible since we don't use diff's -n option),
>        diff3 might report phantom changes from file1 to file2.  */
>   
> !   if (strcmp (file[2], "-") == 0)
> !     {
> !       /* Sigh.  We've got standard input as the last arg.  We can't
> !      call diff twice on stdin.  Use the middle arg as the common
> !      file instead.  */
> !       if (strcmp (file[0], "-") == 0 || strcmp (file[1], "-") == 0)
> !         {
> !       diff_error ("%s", "`-' specified for more than one input file", 0);
> !       return 2;
> !         }
> !       mapping[0] = 0;
> !       mapping[1] = 2;
> !       mapping[2] = 1;
> !     }
> !   else
> !     {
> !       /* Normal, what you'd expect */
> !       mapping[0] = 0;
> !       mapping[1] = 1;
> !       mapping[2] = 2;
> !     }
>   
>     for (i = 0; i < 3; i++)
>       rev_mapping[mapping[i]] = i;
> --- 368,411 ----
>        file0-file1 diffs didn't line up with the file0-file2 diffs
>        (which is entirely possible since we don't use diff's -n option),
>        diff3 might report phantom changes from file1 to file2.  */
> +   /* Also try to compare file0 to file1 because this is the where
> +      changes are expected to come from.  Diffing between these pairs
> +      of files is is most likely to return the intended changes.  There
> +      can also be the same problem with phantom changes from file0 to
> +      file1. */
> +   /* Historically, the default common file was file2.  Ediff for emacs
> +      and possibly other applications, have therefore made file2 the
> +      ancestor.  So, for compatibility, if this is simply a three
> +      way diff (not a merge or edscript) then use the old way with
> +      file2 as the common file. */
> + 
> +   {
> +     int common;
> +     if (edscript || merge )
> +       {
> +     common = 1;
> +       }
> +     else
> +       {
> +     common = 2;
> +       }
> +     if (strcmp (file[common], "-") == 0)
> +       {
> +     /* Sigh.  We've got standard input as the arg corresponding to
> +        the desired common file.  We can't call diff twice on
> +        stdin.  Use another arg as the common file instead.  */
> +     common = 3 - common;
> +     if (strcmp (file[0], "-") == 0 || strcmp (file[common], "-") == 0)
> +       {
> +         diff_error ("%s", "`-' specified for more than one input file", 0);
> +         return 2;
> +       }
> +       }
>   
> !     mapping[0] = 0;
> !     mapping[1] = 3 - common;
> !     mapping[2] = common;
> !   }
>   
>     for (i = 0; i < 3; i++)
>       rev_mapping[mapping[i]] = i;
> ***************
> *** 442,453 ****
> --- 458,475 ----
>     commonname = file[rev_mapping[FILEC]];
>     thread1 = process_diff (file[rev_mapping[FILE1]], commonname, &last_block,
>                         &content1);
> +   /* What is the intention behind determining horizon_lines from first
> +      diff?  I think it is better to use the same parameters for each
> +      diff so that equal differences in each diff will appear the
> +      same. */
> +   /*
>     if (thread1)
>       for (i = 0; i < 2; i++)
>         {
>       horizon_lines = max (horizon_lines, D_NUMLINES (thread1, i));
>       horizon_lines = max (horizon_lines, D_NUMLINES (last_block, i));
>         }
> +   */
>     thread0 = process_diff (file[rev_mapping[FILE0]], commonname, &last_block,
>                         &content0);
>     diff3 = make_3way_diff (thread0, thread1);
> ***************
> *** 1853,1859 ****
>     always_text = 0;
>     edscript = 0;
>     flagging = 0;
> -   horizon_lines = 10;
>     tab_align_flag = 0;
>     simple_only = 0;
>     overlap_only = 0;
> --- 1875,1880 ----