lib/git-merge-changelog.c

   1 /* git-merge-changelog - git "merge" driver for GNU style ChangeLog files.
   2    Copyright (C) 2008 Bruno Haible <bruno@clisp.org>
   3
   4    This program is free software: you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation; either version 2 of the License, or
   7    (at your option) any later version.
   8
   9    This program is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12    GNU General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
  16
  17 /* README:
  18    The default merge driver of 'git' *always* produces conflicts when
  19    pulling public modifications into a privately modified ChangeLog file.
  20    This is because ChangeLog files are always modified at the top; the
  21    default merge driver has no clue how to deal with this. Furthermore
  22    the conflicts are presented with more <<<< ==== >>>> markers than
  23    necessary; this is because the default merge driver makes pointless
  24    effects to look at the individual line changes inside a ChangeLog entry.
  25
  26    This program serves as a 'git' merge driver that avoids these problems.
  27    1. It produces no conflict when ChangeLog entries have been inserted
  28       at the top both in the public and in the private modification. It
  29       puts the privately added entries above the publicly added entries.
  30    2. It respects the structure of ChangeLog files: entries are not split
  31       into lines but kept together.
  32    3. It also handles the case of small modifications of past ChangeLog
  33       entries, or of removed ChangeLog entries: they are merged as one
  34       would expect it.
  35    4. Conflicts are presented at the top of the file, rather than where
  36       they occurred, so that the user will see them immediately. (Unlike
  37       for source code written in some programming language, conflict markers
  38       that are located several hundreds lines from the top will not cause
  39       any syntax error and therefore would be likely to remain unnoticed.)
  40  */
  41
  42 /* Installation:
  43    $ gnulib-tool --create-testdir --dir=/tmp/testdir123 git-merge-changelog
  44    $ cd /tmp/testdir123
  45    $ ./configure
  46    $ make
  47    $ make install
  48    - Add to .git/config of the checkout (or to your $HOME/.gitconfig) the lines
  49
  50         [merge "merge-changelog"]
  51                 name = GNU-style ChangeLog merge driver
  52                 driver = /usr/local/bin/git-merge-changelog %O %A %B
  53
  54    - In every directory that contains a ChangeLog file, add a file
  55      '.gitattributes' with this line:
  56
  57         ChangeLog    merge=merge-changelog
  58
  59      (See "man 5 gitattributes" for more info.)
  60  */
  61
  62 /* Calling convention:
  63    A merge driver is called with three filename arguments:
  64      1. %O = The common ancestor of %A and %B.
  65      2. %A = The file's contents from the "current branch".
  66      3. %B = The file's contents from the "other branch"; this is the contents
  67         being merged in.
  68
  69    In case of a "git stash apply" or of an upstream pull (e.g. from a subsystem
  70    maintainer to a central maintainer) or of a downstream pull with --rebase:
  71      2. %A = The file's newest pulled contents; modified by other committers.
  72      3. %B = The user's newest copy of the file; modified by the user.
  73    In case of a downstream pull (e.g. from a central repository to the user)
  74    or of an upstream pull with --rebase:
  75      2. %A = The user's newest copy of the file; modified by the user.
  76      3. %B = The file's newest pulled contents; modified by other committers.
  77
  78    It should write its merged output into file %A. It can also echo some
  79    remarks to stdout.  It should exit with return code 0 if the merge could
  80    be resolved cleanly, or with non-zero return code if there were conflicts.
  81  */
  82
  83 /* How it works:
  84    The structure of a ChangeLog file: It consists of ChangeLog entries. A
  85    ChangeLog entry starts at a line following a blank line and that starts with
  86    a non-whitespace character, or at the beginning of a file.
  87    The merge driver works as follows: It reads the three files into memory and
  88    dissects them into ChangeLog entries. It then finds the differences between
  89    %O and %B. They are classified as:
  90      - removals (some consecutive entries removed),
  91      - changes (some consecutive entries removed, some consecutive entries
  92        added),
  93      - additions (some consecutive entries added).
  94    The driver then attempts to apply the changes to %A.
  95    To this effect, it first computes a correspondence between the entries in %O
  96    and the entries in %A, using fuzzy string matching to still identify changed
  97    entries.
  98      - Removals are applied one by one. If the entry is present in %A, at any
  99        position, it is removed. If not, the removal is marked as a conflict.
 100      - Additions at the top of %B are applied at the top of %A.
 101      - Additions between entry x and entry y (y may be the file end) in %B are
 102        applied between entry x and entry y in %A (if they still exist and are
 103        still consecutive in %A), otherwise the additions are marked as a
 104        conflict.
 105      - Changes are categorized into "simple changes":
 106          entry1 ... entryn
 107        are mapped to
 108          added_entry ... added_entry modified_entry1 ... modified_entryn,
 109        where the correspondence between entry_i and modified_entry_i is still
 110        clear; and "big changes": these are all the rest. Simple changes at the
 111        top of %B are applied by putting the added entries at the top of %A. The
 112        changes in simple changes are applied one by one; possibly leading to
 113        single-entry conflicts. Big changes are applied en bloc, possibly
 114        leading to conflicts spanning multiple entries.
 115      - Conflicts are output at the top of the file and cause an exit status of
 116        1.
 117  */
 118
 119 #include <config.h>
 120
 121 #include <getopt.h>
 122 #include <limits.h>
 123 #include <stdbool.h>
 124 #include <stdio.h>
 125 #include <stdlib.h>
 126 #include <string.h>
 127 #include <sys/types.h>
 128 #include <unistd.h>
 129
 130 #include "progname.h"
 131 #include "error.h"
 132 #include "read-file.h"
 133 #include "gl_list.h"
 134 #include "gl_array_list.h"
 135 #include "gl_linkedhash_list.h"
 136 #include "gl_rbtreehash_list.h"
 137 #include "gl_linked_list.h"
 138 #include "xalloc.h"
 139 #include "xmalloca.h"
 140 #include "fstrcmp.h"
 141 #include "minmax.h"
 142 #include "c-strstr.h"
 143 #include "fwriteerror.h"
 144
 145 #define ASSERT(expr) \
 146   do                                                                         \
 147     {                                                                        \
 148       if (!(expr))                                                           \
 149         abort ();                                                            \
 150     }                                                                        \
 151   while (0)
 152
 153 #define FSTRCMP_THRESHOLD 0.6
 154 #define FSTRCMP_STRICTER_THRESHOLD 0.8
 155
 156 /* Representation of a ChangeLog entry.
 157    The string may contain NUL bytes; therefore it is represented as a plain
 158    opaque memory region.  */
 159 struct entry
 160 {
 161   char *string;
 162   size_t length;
 163   /* Cache for the hash code.  */
 164   bool hashcode_cached;
 165   size_t hashcode;
 166 };
 167
 168 /* Create an entry.
 169    The memory region passed by the caller must of indefinite extent.  It is
 170    *not* copied here.  */
 171 static struct entry *
 172 entry_create (char *string, size_t length)
 173 {
 174   struct entry *result = XMALLOC (struct entry);
 175   result->string = string;
 176   result->length = length;
 177   result->hashcode_cached = false;
 178   return result;
 179 }
 180
 181 /* Compare two entries for equality.  */
 182 static bool
 183 entry_equals (const void *elt1, const void *elt2)
 184 {
 185   const struct entry *entry1 = (const struct entry *) elt1;
 186   const struct entry *entry2 = (const struct entry *) elt2;
 187   return entry1->length == entry2->length
 188          && memcmp (entry1->string, entry2->string, entry1->length) == 0;
 189 }
 190
 191 /* Return a hash code of the contents of a ChangeLog entry.  */
 192 static size_t
 193 entry_hashcode (const void *elt)
 194 {
 195   struct entry *entry = (struct entry *) elt;
 196   if (!entry->hashcode_cached)
 197     {
 198       /* See http://www.haible.de/bruno/hashfunc.html.  */
 199       const char *s;
 200       size_t n;
 201       size_t h = 0;
 202
 203       for (s = entry->string, n = entry->length; n > 0; s++, n--)
 204         h = (unsigned char) *s + ((h << 9) | (h >> (sizeof (size_t) * CHAR_BIT - 9)));
 205
 206       entry->hashcode = h;
 207       entry->hashcode_cached = true;
 208     }
 209   return entry->hashcode;
 210 }
 211
 212 /* Perform a fuzzy comparison of two ChangeLog entries.
 213    Return a similarity measure of the two entries, a value between 0 and 1.
 214    0 stands for very distinct, 1 for identical.  */
 215 static double
 216 entry_fstrcmp (const struct entry *entry1, const struct entry *entry2)
 217 {
 218   /* fstrcmp works only on NUL terminated strings.  */
 219   char *memory;
 220   double similarity;
 221
 222   if (memchr (entry1->string, '\0', entry1->length) != NULL)
 223     return 0.0;
 224   if (memchr (entry2->string, '\0', entry2->length) != NULL)
 225     return 0.0;
 226   memory = (char *) xmalloca (entry1->length + 1 + entry2->length + 1);
 227   {
 228     char *p = memory;
 229     memcpy (p, entry1->string, entry1->length);
 230     p += entry1->length;
 231     *p++ = '\0';
 232     memcpy (p, entry2->string, entry2->length);
 233     p += entry2->length;
 234     *p++ = '\0';
 235   }
 236   similarity = fstrcmp (memory, memory + entry1->length + 1);
 237   freea (memory);
 238   return similarity;
 239 }
 240
 241 /* This structure represents an entire ChangeLog file, after it was read
 242    into memory.  */
 243 struct changelog_file
 244 {
 245   /* The entries, as a list.  */
 246   gl_list_t /* <struct entry *> */ entries_list;
 247   /* The entries, as a list in opposite direction.  */
 248   gl_list_t /* <struct entry *> */ entries_reversed;
 249   /* The entries, as an array.  */
 250   size_t num_entries;
 251   struct entry **entries;
 252 };
 253
 254 /* Read a ChangeLog file into memory.
 255    Return the contents in *RESULT.  */
 256 static void
 257 read_changelog_file (const char *filename, struct changelog_file *result)
 258 {
 259   /* Read the file in text mode, otherwise it's hard to recognize empty
 260      lines.  */
 261   size_t length;
 262   char *contents = read_file (filename, &length);
 263   if (contents == NULL)
 264     {
 265       fprintf (stderr, "could not read file '%s'\n", filename);
 266       exit (EXIT_FAILURE);
 267     }
 268
 269   result->entries_list =
 270     gl_list_create_empty (GL_LINKEDHASH_LIST, entry_equals, entry_hashcode,
 271                           NULL, true);
 272   result->entries_reversed =
 273     gl_list_create_empty (GL_RBTREEHASH_LIST, entry_equals, entry_hashcode,
 274                           NULL, true);
 275   /* A ChangeLog file consists of ChangeLog entries.  A ChangeLog entry starts
 276      at a line following a blank line and that starts with a non-whitespace
 277      character, or at the beginning of a file.
 278      Split the file contents into entries.  */
 279   {
 280     char *contents_end = contents + length;
 281     char *start = contents;
 282     while (start < contents_end)
 283       {
 284         /* Search the end of the current entry.  */
 285         char *ptr = start;
 286         struct entry *curr;
 287
 288         while (ptr < contents_end)
 289           {
 290             ptr = memchr (ptr, '\n', contents_end - ptr);
 291             if (ptr == NULL)
 292               {
 293                 ptr = contents_end;
 294                 break;
 295               }
 296             ptr++;
 297             if (contents_end - ptr >= 2
 298                 && ptr[0] == '\n'
 299                 && !(ptr[1] == '\n' || ptr[1] == '\t' || ptr[1] == ' '))
 300               {
 301                 ptr++;
 302                 break;
 303               }
 304           }
 305
 306         curr = entry_create (start, ptr - start);
 307         gl_list_add_last (result->entries_list, curr);
 308         gl_list_add_first (result->entries_reversed, curr);
 309
 310         start = ptr;
 311       }
 312   }
 313
 314   result->num_entries = gl_list_size (result->entries_list);
 315   result->entries = XNMALLOC (result->num_entries, struct entry *);
 316   {
 317     size_t index = 0;
 318     gl_list_iterator_t iter = gl_list_iterator (result->entries_list);
 319     const void *elt;
 320     gl_list_node_t node;
 321     while (gl_list_iterator_next (&iter, &elt, &node))
 322       result->entries[index++] = (struct entry *) elt;
 323     gl_list_iterator_free (&iter);
 324     ASSERT (index == result->num_entries);
 325   }
 326 }
 327
 328 /* Compute a mapping (correspondence) between entries of FILE1 and of FILE2.
 329    Return a set of two arrays:
 330      - An array mapping FILE1 indices to FILE2 indices (or -1 when the entry
 331        from FILE1 is not found in FILE2).
 332      - An array mapping FILE2 indices to FILE1 indices (or -1 when the entry
 333        from FILE2 is not found in FILE1).
 334    The correspondence also takes into account small modifications; i.e. the
 335    indicated relation is not equality of entries but best-match similarity
 336    of entries.  */
 337 static void
 338 compute_mapping (struct changelog_file *file1, struct changelog_file *file2,
 339                  ssize_t *result[2])
 340 {
 341   /* Mapping from indices in file1 to indices in file2.  */
 342   ssize_t *index_mapping;
 343   /* Mapping from indices in file2 to indices in file1.  */
 344   ssize_t *index_mapping_reverse;
 345   size_t n1 = file1->num_entries;
 346   size_t n2 = file2->num_entries;
 347   ssize_t i, j;
 348
 349   index_mapping = XNMALLOC (n1, ssize_t);
 350   for (i = 0; i < n1; i++)
 351     index_mapping[i] = -1;
 352
 353   index_mapping_reverse = XNMALLOC (n2, ssize_t);
 354   for (j = 0; j < n2; j++)
 355     index_mapping_reverse[j] = -1;
 356
 357   for (i = n1 - 1; i >= 0; i--)
 358     /* Take an entry from file1.  */
 359     if (index_mapping[i] < 0)
 360       {
 361         struct entry *entry = file1->entries[i];
 362         /* Search whether it occurs in file2.  */
 363         j = gl_list_indexof (file2->entries_reversed, entry);
 364         if (j >= 0)
 365           {
 366             j = n2 - 1 - j;
 367             /* Found an exact correspondence.  */
 368             ASSERT (index_mapping_reverse[j] < 0);
 369             index_mapping[i] = j;
 370             index_mapping_reverse[j] = i;
 371             /* Look for more occurrences of the same entry.  */
 372             {
 373               ssize_t curr_i = i;
 374               ssize_t curr_j = j;
 375
 376               for (;;)
 377                 {
 378                   ssize_t next_i;
 379                   ssize_t next_j;
 380
 381                   next_i =
 382                     gl_list_indexof_from (file1->entries_reversed, n1 - curr_i,
 383                                           entry);
 384                   if (next_i < 0)
 385                     break;
 386                   next_j =
 387                     gl_list_indexof_from (file2->entries_reversed, n2 - curr_j,
 388                                           entry);
 389                   if (next_j < 0)
 390                     break;
 391                   curr_i = n1 - 1 - next_i;
 392                   curr_j = n2 - 1 - next_j;
 393                   ASSERT (index_mapping[curr_i] < 0);
 394                   ASSERT (index_mapping_reverse[curr_j] < 0);
 395                   index_mapping[curr_i] = curr_j;
 396                   index_mapping_reverse[curr_j] = curr_i;
 397                 }
 398             }
 399           }
 400       }
 401
 402   for (i = n1 - 1; i >= 0; i--)
 403     /* Take an entry from file1.  */
 404     if (index_mapping[i] < 0)
 405       {
 406         struct entry *entry_i = file1->entries[i];
 407         /* Search whether it approximately occurs in file2.  */
 408         ssize_t best_j = -1;
 409         double best_j_similarity = 0.0;
 410         for (j = n2 - 1; j >= 0; j--)
 411           if (index_mapping_reverse[j] < 0)
 412             {
 413               double similarity = entry_fstrcmp (entry_i, file2->entries[j]);
 414               if (similarity > best_j_similarity)
 415                 {
 416                   best_j = j;
 417                   best_j_similarity = similarity;
 418                 }
 419             }
 420         if (best_j_similarity >= FSTRCMP_THRESHOLD)
 421           {
 422             /* Found a similar entry in file2.  */
 423             struct entry *entry_j = file2->entries[best_j];
 424             /* Search whether it approximately occurs in file1 at index i.  */
 425             ssize_t best_i = -1;
 426             double best_i_similarity = 0.0;
 427             ssize_t ii;
 428             for (ii = n1 - 1; ii >= 0; ii--)
 429               if (index_mapping[ii] < 0)
 430                 {
 431                   double similarity =
 432                     entry_fstrcmp (file1->entries[ii], entry_j);
 433                   if (similarity > best_i_similarity)
 434                     {
 435                       best_i = i;
 436                       best_i_similarity = similarity;
 437                     }
 438                 }
 439             if (best_i_similarity >= FSTRCMP_THRESHOLD && best_i == i)
 440               {
 441                 index_mapping[i] = best_j;
 442                 index_mapping_reverse[best_j] = i;
 443               }
 444           }
 445       }
 446
 447   result[0] = index_mapping;
 448   result[1] = index_mapping_reverse;
 449 }
 450
 451 /* An "edit" is a textual modification performed by the user, that needs to
 452    be applied to the other file.  */
 453 enum edit_type
 454 {
 455   /* Some consecutive entries were added.  */
 456   ADDITION,
 457   /* Some consecutive entries were removed; some other consecutive entries
 458      were added at the same position.  (Not necessarily the same number of
 459      entries.)  */
 460   CHANGE,
 461   /* Some consecutive entries were removed.  */
 462   REMOVAL
 463 };
 464
 465 /* This structure represents an edit.  */
 466 struct edit
 467 {
 468   enum edit_type type;
 469   /* Range of indices into the entries of FILE1.  */
 470   ssize_t i1, i2;       /* first, last index; only used for CHANGE, REMOVAL */
 471   /* Range of indices into the entries of FILE2.  */
 472   ssize_t j1, j2;       /* first, last index; only used for ADDITION, CHANGE */
 473 };
 474
 475 /* This structure represents the differences from one file, FILE1, to another
 476    file, FILE2.  */
 477 struct differences
 478 {
 479   /* An array mapping FILE1 indices to FILE2 indices (or -1 when the entry
 480      from FILE1 is not found in FILE2).  */
 481   ssize_t *index_mapping;
 482   /* An array mapping FILE2 indices to FILE1 indices (or -1 when the entry
 483      from FILE2 is not found in FILE1).  */
 484   ssize_t *index_mapping_reverse;
 485   /* The edits that transform FILE1 into FILE2.  */
 486   size_t num_edits;
 487   struct edit **edits;
 488 };
 489
 490 /* Import the difference detection algorithm from GNU diff.  */
 491 #define ELEMENT struct entry *
 492 #define EQUAL entry_equals
 493 #define OFFSET ssize_t
 494 #define EXTRA_CONTEXT_FIELDS \
 495   ssize_t *index_mapping; \
 496   ssize_t *index_mapping_reverse;
 497 #define NOTE_DELETE(ctxt, xoff) \
 498   ctxt->index_mapping[xoff] = -1
 499 #define NOTE_INSERT(ctxt, yoff) \
 500   ctxt->index_mapping_reverse[yoff] = -1
 501 #include "diffseq.h"
 502
 503 /* Compute the differences between the entries of FILE1 and the entries of
 504    FILE2.  */
 505 static void
 506 compute_differences (struct changelog_file *file1, struct changelog_file *file2,
 507                      struct differences *result)
 508 {
 509   /* Unlike compute_mapping, which mostly ignores the order of the entries and
 510      therefore works well when some entries are permuted, here we use the order.
 511      I think this is needed in order to distinguish changes from
 512      additions+removals; I don't know how to say what is a "change" if the
 513      files are considered as unordered sets of entries.  */
 514   struct context ctxt;
 515   size_t n1 = file1->num_entries;
 516   size_t n2 = file2->num_entries;
 517   ssize_t i;
 518   ssize_t j;
 519   gl_list_t /* <struct edit *> */ edits;
 520
 521   ctxt.xvec = file1->entries;
 522   ctxt.yvec = file2->entries;
 523   ctxt.index_mapping = XNMALLOC (n1, ssize_t);
 524   for (i = 0; i < n1; i++)
 525     ctxt.index_mapping[i] = 0;
 526   ctxt.index_mapping_reverse = XNMALLOC (n2, ssize_t);
 527   for (j = 0; j < n2; j++)
 528     ctxt.index_mapping_reverse[j] = 0;
 529   ctxt.fdiag = XNMALLOC (2 * (n1 + n2 + 3), ssize_t) + n2 + 1;
 530   ctxt.bdiag = ctxt.fdiag + n1 + n2 + 3;
 531   ctxt.too_expensive = n1 + n2;
 532
 533   /* Store in ctxt.index_mapping and ctxt.index_mapping_reverse a -1 for
 534      each removed or added entry.  */
 535   compareseq (0, n1, 0, n2, 0, &ctxt);
 536
 537   /* Complete the index_mapping and index_mapping_reverse arrays.  */
 538   i = 0;
 539   j = 0;
 540   while (i < n1 || j < n2)
 541     {
 542       while (i < n1 && ctxt.index_mapping[i] < 0)
 543         i++;
 544       while (j < n2 && ctxt.index_mapping_reverse[j] < 0)
 545         j++;
 546       ASSERT ((i < n1) == (j < n2));
 547       if (i == n1 && j == n2)
 548         break;
 549       ctxt.index_mapping[i] = j;
 550       ctxt.index_mapping_reverse[j] = i;
 551       i++;
 552       j++;
 553     }
 554
 555   /* Create the edits.  */
 556   edits = gl_list_create_empty (GL_ARRAY_LIST, NULL, NULL, NULL, true);
 557   i = 0;
 558   j = 0;
 559   while (i < n1 || j < n2)
 560     {
 561       if (i == n1)
 562         {
 563           struct edit *e;
 564           ASSERT (j < n2);
 565           e = XMALLOC (struct edit);
 566           e->type = ADDITION;
 567           e->j1 = j;
 568           e->j2 = n2 - 1;
 569           gl_list_add_last (edits, e);
 570           break;
 571         }
 572       if (j == n2)
 573         {
 574           struct edit *e;
 575           ASSERT (i < n1);
 576           e = XMALLOC (struct edit);
 577           e->type = REMOVAL;
 578           e->i1 = i;
 579           e->i2 = n1 - 1;
 580           gl_list_add_last (edits, e);
 581           break;
 582         }
 583       if (ctxt.index_mapping[i] >= 0)
 584         {
 585           if (ctxt.index_mapping_reverse[j] >= 0)
 586             {
 587               ASSERT (ctxt.index_mapping[i] == j);
 588               ASSERT (ctxt.index_mapping_reverse[j] == i);
 589               i++;
 590               j++;
 591             }
 592           else
 593             {
 594               struct edit *e;
 595               ASSERT (ctxt.index_mapping_reverse[j] < 0);
 596               e = XMALLOC (struct edit);
 597               e->type = ADDITION;
 598               e->j1 = j;
 599               do
 600                 j++;
 601               while (j < n2 && ctxt.index_mapping_reverse[j] < 0);
 602               e->j2 = j - 1;
 603               gl_list_add_last (edits, e);
 604             }
 605         }
 606       else
 607         {
 608           if (ctxt.index_mapping_reverse[j] >= 0)
 609             {
 610               struct edit *e;
 611               ASSERT (ctxt.index_mapping[i] < 0);
 612               e = XMALLOC (struct edit);
 613               e->type = REMOVAL;
 614               e->i1 = i;
 615               do
 616                 i++;
 617               while (i < n1 && ctxt.index_mapping[i] < 0);
 618               e->i2 = i - 1;
 619               gl_list_add_last (edits, e);
 620             }
 621           else
 622             {
 623               struct edit *e;
 624               ASSERT (ctxt.index_mapping[i] < 0);
 625               ASSERT (ctxt.index_mapping_reverse[j] < 0);
 626               e = XMALLOC (struct edit);
 627               e->type = CHANGE;
 628               e->i1 = i;
 629               do
 630                 i++;
 631               while (i < n1 && ctxt.index_mapping[i] < 0);
 632               e->i2 = i - 1;
 633               e->j1 = j;
 634               do
 635                 j++;
 636               while (j < n2 && ctxt.index_mapping_reverse[j] < 0);
 637               e->j2 = j - 1;
 638               gl_list_add_last (edits, e);
 639             }
 640         }
 641     }
 642
 643   result->index_mapping = ctxt.index_mapping;
 644   result->index_mapping_reverse = ctxt.index_mapping_reverse;
 645   result->num_edits = gl_list_size (edits);
 646   result->edits = XNMALLOC (result->num_edits, struct edit *);
 647   {
 648     size_t index = 0;
 649     gl_list_iterator_t iter = gl_list_iterator (edits);
 650     const void *elt;
 651     gl_list_node_t node;
 652     while (gl_list_iterator_next (&iter, &elt, &node))
 653       result->edits[index++] = (struct edit *) elt;
 654     gl_list_iterator_free (&iter);
 655     ASSERT (index == result->num_edits);
 656   }
 657 }
 658
 659 /* An empty entry.  */
 660 static struct entry empty_entry = { NULL, 0 };
 661
 662 /* Return the end a paragraph.
 663    ENTRY is an entry.
 664    OFFSET is an offset into the entry, OFFSET <= ENTRY->length.
 665    Return the offset of the end of paragraph, as an offset <= ENTRY->length;
 666    it is the start of a blank line or the end of the entry.  */
 667 static size_t
 668 find_paragraph_end (const struct entry *entry, size_t offset)
 669 {
 670   const char *string = entry->string;
 671   size_t length = entry->length;
 672
 673   for (;;)
 674     {
 675       const char *nl = memchr (string + offset, '\n', length - offset);
 676       if (nl == NULL)
 677         return length;
 678       offset = (nl - string) + 1;
 679       if (offset < length && string[offset] == '\n')
 680         return offset;
 681     }
 682 }
 683
 684 /* Split a merged entry.
 685    Given an old entry of the form
 686        TITLE
 687        BODY
 688    and a new entry of the form
 689        TITLE
 690        BODY1
 691        BODY'
 692    where the two titles are the same and BODY and BODY' are very similar,
 693    this computes two new entries
 694        TITLE
 695        BODY1
 696    and
 697        TITLE
 698        BODY'
 699    and returns true.
 700    If the entries don't have this form, it returns false.  */
 701 static bool
 702 try_split_merged_entry (const struct entry *old_entry,
 703                         const struct entry *new_entry,
 704                         struct entry *new_split[2])
 705 {
 706   size_t old_title_len = find_paragraph_end (old_entry, 0);
 707   size_t new_title_len = find_paragraph_end (new_entry, 0);
 708   struct entry old_body;
 709   struct entry new_body;
 710   size_t best_split_offset;
 711   double best_similarity;
 712   size_t split_offset;
 713
 714   /* Same title? */
 715   if (!(old_title_len == new_title_len
 716         && memcmp (old_entry->string, new_entry->string, old_title_len) == 0))
 717     return false;
 718
 719   old_body.string = old_entry->string + old_title_len;
 720   old_body.length = old_entry->length - old_title_len;
 721
 722   /* Determine where to split the new entry.
 723      This is done by maximizing the similarity between BODY and BODY'.  */
 724   best_split_offset = split_offset = new_title_len;
 725   best_similarity = 0.0;
 726   for (;;)
 727     {
 728       double similarity;
 729
 730       new_body.string = new_entry->string + split_offset;
 731       new_body.length = new_entry->length - split_offset;
 732       similarity = entry_fstrcmp (&old_body, &new_body);
 733       if (similarity > best_similarity)
 734         {
 735           best_split_offset = split_offset;
 736           best_similarity = similarity;
 737         }
 738       if (best_similarity == 1.0)
 739         /* It cannot get better.  */
 740         break;
 741
 742       if (split_offset < new_entry->length)
 743         split_offset = find_paragraph_end (new_entry, split_offset + 1);
 744       else
 745         break;
 746     }
 747
 748   /* BODY' should not be empty.  */
 749   if (best_split_offset == new_entry->length)
 750     return false;
 751   ASSERT (new_entry->string[best_split_offset] == '\n');
 752
 753   /* A certain similarity between BODY and BODY' is required.  */
 754   if (best_similarity < FSTRCMP_STRICTER_THRESHOLD)
 755     return false;
 756
 757   new_split[0] = entry_create (new_entry->string, best_split_offset + 1);
 758
 759   {
 760     size_t len1 = new_title_len;
 761     size_t len2 = new_entry->length - best_split_offset;
 762     char *combined = XNMALLOC (len1 + len2, char);
 763     memcpy (combined, new_entry->string, len1);
 764     memcpy (combined + len1, new_entry->string + best_split_offset, len2);
 765     new_split[1] = entry_create (combined, len1 + len2);
 766   }
 767
 768   return true;
 769 }
 770
 771 /* Write the contents of an entry to the output stream FP.  */
 772 static void
 773 entry_write (FILE *fp, struct entry *entry)
 774 {
 775   if (entry->length > 0)
 776     fwrite (entry->string, 1, entry->length, fp);
 777 }
 778
 779 /* This structure represents a conflict.
 780    A conflict can occur for various reasons.  */
 781 struct conflict
 782 {
 783   /* Parts from the ancestor file.  */
 784   size_t num_old_entries;
 785   struct entry **old_entries;
 786   /* Parts of the modified file.  */
 787   size_t num_modified_entries;
 788   struct entry **modified_entries;
 789 };
 790
 791 /* Write a conflict to the output stream FP, including markers.  */
 792 static void
 793 conflict_write (FILE *fp, struct conflict *c)
 794 {
 795   size_t i;
 796
 797   /* Use the same syntax as git's default merge driver.
 798      Don't indent the contents of the entries (with things like ">" or "-"),
 799      otherwise the user needs more textual editing to resolve the conflict.  */
 800   fputs ("<<<<<<<\n", fp);
 801   for (i = 0; i < c->num_old_entries; i++)
 802     entry_write (fp, c->old_entries[i]);
 803   fputs ("=======\n", fp);
 804   for (i = 0; i < c->num_modified_entries; i++)
 805     entry_write (fp, c->modified_entries[i]);
 806   fputs (">>>>>>>\n", fp);
 807 }
 808
 809 /* Long options.  */
 810 static const struct option long_options[] =
 811 {
 812   { "help", no_argument, NULL, 'h' },
 813   { "split-merged-entry", no_argument, NULL, CHAR_MAX + 1 },
 814   { "version", no_argument, NULL, 'V' },
 815   { NULL, 0, NULL, 0 }
 816 };
 817
 818 /* Print a usage mesage and exit.  */
 819 static void
 820 usage (int status)
 821 {
 822   if (status != EXIT_SUCCESS)
 823     fprintf (stderr, "Try `%s --help' for more information.\n",
 824              program_name);
 825   else
 826     {
 827       printf ("Usage: %s [OPTION] O-FILE-NAME A-FILE-NAME B-FILE-NAME\n",
 828               program_name);
 829       printf ("\n");
 830       printf ("Merges independent modifications of a ChangeLog style file.\n");
 831       printf ("O-FILE-NAME names the original file, the ancestor of the two others.\n");
 832       printf ("A-FILE-NAME names the publicly modified file.\n");
 833       printf ("B-FILE-NAME names the user-modified file.\n");
 834       printf ("Writes the merged file into A-FILE-NAME.\n");
 835       printf ("\n");
 836       printf ("Operation modifiers:\n");
 837       printf ("\
 838       --split-merged-entry    Possibly split a merged entry between paragraphs.\n\
 839                               Use this if you have the habit to merge unrelated\n\
 840                               entries into a single one, separated only by a\n\
 841                               newline, just because they happened on the same\n\
 842                               date.\n");
 843       printf ("\n");
 844       printf ("Informative output:\n");
 845       printf ("  -h, --help                  display this help and exit\n");
 846       printf ("  -V, --version               output version information and exit\n");
 847       printf ("\n");
 848       fputs ("Report bugs to <bug-gnu-gettext@gnu.org>.\n",
 849              stdout);
 850     }
 851
 852   exit (status);
 853 }
 854
 855 int
 856 main (int argc, char *argv[])
 857 {
 858   int optchar;
 859   bool do_help;
 860   bool do_version;
 861   bool split_merged_entry;
 862
 863   /* Set program name for messages.  */
 864   set_program_name (argv[0]);
 865
 866   /* Set default values for variables.  */
 867   do_help = false;
 868   do_version = false;
 869   split_merged_entry = false;
 870
 871   /* Parse command line options.  */
 872   while ((optchar = getopt_long (argc, argv, "hV", long_options, NULL)) != EOF)
 873     switch (optchar)
 874     {
 875     case '\0':          /* Long option.  */
 876       break;
 877     case 'h':
 878       do_help = true;
 879       break;
 880     case 'V':
 881       do_version = true;
 882       break;
 883     case CHAR_MAX + 1:  /* --split-merged-entry */
 884       split_merged_entry = true;
 885       break;
 886     default:
 887       usage (EXIT_FAILURE);
 888     }
 889
 890   if (do_version)
 891     {
 892       /* Version information is requested.  */
 893       printf ("%s\n", program_name);
 894       printf ("Copyright (C) %s Free Software Foundation, Inc.\n\
 895 License GPLv2+: GNU GPL version 2 or later <http://gnu.org/licenses/gpl.html>\n\
 896 This is free software: you are free to change and redistribute it.\n\
 897 There is NO WARRANTY, to the extent permitted by law.\n\
 898 ",
 899               "2008");
 900       printf ("Written by %s.\n", "Bruno Haible");
 901       exit (EXIT_SUCCESS);
 902     }
 903
 904   if (do_help)
 905     {
 906       /* Help is requested.  */
 907       usage (EXIT_SUCCESS);
 908     }
 909
 910   /* Test argument count.  */
 911   if (optind + 3 != argc)
 912     error (EXIT_FAILURE, 0, "expected three arguments");
 913
 914   {
 915     const char *ancestor_file_name; /* O-FILE-NAME */
 916     const char *destination_file_name; /* A-FILE-NAME */
 917     bool downstream;
 918     const char *other_file_name; /* B-FILE-NAME */
 919     const char *mainstream_file_name;
 920     const char *modified_file_name;
 921     struct changelog_file ancestor_file;
 922     struct changelog_file mainstream_file;
 923     struct changelog_file modified_file;
 924     /* Mapping from indices in ancestor_file to indices in mainstream_file.  */
 925     ssize_t *index_mapping;
 926     /* Mapping from indices in mainstream_file to indices in ancestor_file.  */
 927     ssize_t *index_mapping_reverse;
 928     struct differences diffs;
 929     gl_list_node_t *result_entries_pointers; /* array of pointers into result_entries */
 930     gl_list_t /* <struct entry *> */ result_entries;
 931     gl_list_t /* <struct conflict *> */ result_conflicts;
 932
 933     ancestor_file_name = argv[optind];
 934     destination_file_name = argv[optind + 1];
 935     other_file_name = argv[optind + 2];
 936
 937     /* Heuristic to determine whether it's a pull in downstream direction
 938        (e.g. pull from a centralized server) or a pull in upstream direction
 939        (e.g. "git stash apply").
 940
 941        For ChangeLog this distinction is important. The difference between
 942        an "upstream" and a "downstream" repository is that more people are
 943        looking at the "upstream" repository.  They want to be informed about
 944        changes and expect them to be shown at the top of the ChangeLog.
 945        When a user pulls downstream, on the other hand, he has two options:
 946          a) He gets the change entries from the central repository also at the
 947             top of his ChangeLog, and his own changes come after them.
 948          b) He gets the change entries from the central repository after those
 949             he has collected for his branch.  His own change entries stay at
 950             the top of the ChangeLog file.
 951        In the case a) he has to reorder the ChangeLog before he can commit.
 952        No one does that.  So most people want b).
 953        In other words, the order of entries in a ChangeLog should represent
 954        the order in which they have flown (or will flow) into the *central*
 955        repository.
 956
 957        But in git this is fundamentally indistinguishable, because when Linus
 958        pulls patches from akpm and akpm pulls patches from Linus, it's not
 959        clear which of the two is more "upstream".  Also, when you have many
 960        branches in a repository and pull from one to another, "git" has no way
 961        to know which branch is more "upstream" than the other.  The git-tag(1)
 962        manual page also says:
 963          "One important aspect of git is it is distributed, and being
 964           distributed largely means there is no inherent "upstream" or
 965           "downstream" in the system."
 966        Therefore anyone who attempts to produce a ChangeLog from the merge
 967        history will fail.
 968
 969        Here we allow the user to specify the pull direction through an
 970        environment variable (GIT_UPSTREAM or GIT_DOWNSTREAM).  If these two
 971        environment variables are not set, we assume a "simple single user"
 972        usage pattern: He manages local changes through stashes and uses
 973        "git pull" only to pull downstream.
 974
 975        How to distinguish these situation? There are several hints:
 976          - During a "git stash apply", GIT_REFLOG_ACTION is not set.  During
 977            a "git pull", it is set to 'pull '. During a "git pull --rebase",
 978            it is set to 'pull --rebase'.
 979          - During a "git stash apply", there is an environment variable of
 980            the form GITHEAD_<40_hex_digits>='Stashed changes'.  */
 981     {
 982       const char *var;
 983
 984       var = getenv ("GIT_DOWNSTREAM");
 985       if (var != NULL && var[0] != '\0')
 986         downstream = true;
 987       else
 988         {
 989           var = getenv ("GIT_UPSTREAM");
 990           if (var != NULL && var[0] != '\0')
 991             downstream = false;
 992           else
 993             {
 994               var = getenv ("GIT_REFLOG_ACTION");
 995               #if 0 /* Debugging code */
 996               printf ("GIT_REFLOG_ACTION=|%s|\n", var);
 997               #endif
 998               if (var != NULL
 999                   && ((strncmp (var, "pull", 4) == 0
1000                        && c_strstr (var, " --rebase") == NULL)
1001                       || strncmp (var, "merge origin", 12) == 0))
1002                 downstream = true;
1003               else
1004                 {
1005                   /* "git stash apply", "git rebase" and similar.  */
1006                   downstream = false;
1007                 }
1008             }
1009         }
1010     }
1011
1012     #if 0 /* Debugging code */
1013     {
1014       char buf[1000];
1015       printf ("First line of %%A:\n");
1016       sprintf (buf, "head -1 %s", destination_file_name); system (buf);
1017       printf ("First line of %%B:\n");
1018       sprintf (buf, "head -1 %s", other_file_name); system (buf);
1019       printf ("Guessing calling convention: %s\n",
1020               downstream
1021               ? "%A = modified by user, %B = upstream"
1022               : "%A = upstream, %B = modified by user");
1023     }
1024     #endif
1025
1026     if (downstream)
1027       {
1028         mainstream_file_name = other_file_name;
1029         modified_file_name = destination_file_name;
1030       }
1031     else
1032       {
1033         mainstream_file_name = destination_file_name;
1034         modified_file_name = other_file_name;
1035       }
1036
1037     /* Read the three files into memory.  */
1038     read_changelog_file (ancestor_file_name, &ancestor_file);
1039     read_changelog_file (mainstream_file_name, &mainstream_file);
1040     read_changelog_file (modified_file_name, &modified_file);
1041
1042     /* Compute correspondence between the entries of ancestor_file and of
1043        mainstream_file.  */
1044     {
1045       ssize_t *result[2];
1046       compute_mapping (&ancestor_file, &mainstream_file, result);
1047       index_mapping = result[0];
1048       index_mapping_reverse = result[1];
1049     }
1050
1051     /* Compute differences between the entries of ancestor_file and of
1052        modified_file.  */
1053     compute_differences (&ancestor_file, &modified_file, &diffs);
1054
1055     /* Compute the result.  */
1056     result_entries_pointers =
1057       XNMALLOC (mainstream_file.num_entries, gl_list_node_t);
1058     result_entries =
1059       gl_list_create_empty (GL_LINKED_LIST, entry_equals, entry_hashcode,
1060                             NULL, true);
1061     {
1062       size_t k;
1063       for (k = 0; k < mainstream_file.num_entries; k++)
1064         result_entries_pointers[k] =
1065           gl_list_add_last (result_entries, mainstream_file.entries[k]);
1066     }
1067     result_conflicts =
1068       gl_list_create_empty (GL_ARRAY_LIST, NULL, NULL, NULL, true);
1069     {
1070       size_t e;
1071       for (e = 0; e < diffs.num_edits; e++)
1072         {
1073           struct edit *edit = diffs.edits[e];
1074           switch (edit->type)
1075             {
1076             case ADDITION:
1077               if (edit->j1 == 0)
1078                 {
1079                   /* An addition to the top of modified_file.
1080                      Apply it to the top of mainstream_file.  */
1081                   ssize_t j;
1082                   for (j = edit->j2; j >= edit->j1; j--)
1083                     {
1084                       struct entry *added_entry = modified_file.entries[j];
1085                       gl_list_add_first (result_entries, added_entry);
1086                     }
1087                 }
1088               else
1089                 {
1090                   ssize_t i_before;
1091                   ssize_t i_after;
1092                   ssize_t k_before;
1093                   ssize_t k_after;
1094                   i_before = diffs.index_mapping_reverse[edit->j1 - 1];
1095                   ASSERT (i_before >= 0);
1096                   i_after = (edit->j2 + 1 == modified_file.num_entries
1097                              ? ancestor_file.num_entries
1098                              : diffs.index_mapping_reverse[edit->j2 + 1]);
1099                   ASSERT (i_after >= 0);
1100                   ASSERT (i_after == i_before + 1);
1101                   /* An addition between ancestor_file.entries[i_before] and
1102                      ancestor_file.entries[i_after].  See whether these two
1103                      entries still exist in mainstream_file and are still
1104                      consecutive.  */
1105                   k_before = index_mapping[i_before];
1106                   k_after = (i_after == ancestor_file.num_entries
1107                              ? mainstream_file.num_entries
1108                              : index_mapping[i_after]);
1109                   if (k_before >= 0 && k_after >= 0 && k_after == k_before + 1)
1110                     {
1111                       /* Yes, the entry before and after are still neighbours
1112                          in mainstream_file.  Apply the addition between
1113                          them.  */
1114                       if (k_after == mainstream_file.num_entries)
1115                         {
1116                           size_t j;
1117                           for (j = edit->j1; j <= edit->j2; j++)
1118                             {
1119                               struct entry *added_entry = modified_file.entries[j];
1120                               gl_list_add_last (result_entries, added_entry);
1121                             }
1122                         }
1123                       else
1124                         {
1125                           gl_list_node_t node_k_after = result_entries_pointers[k_after];
1126                           size_t j;
1127                           for (j = edit->j1; j <= edit->j2; j++)
1128                             {
1129                               struct entry *added_entry = modified_file.entries[j];
1130                               gl_list_add_before (result_entries, node_k_after, added_entry);
1131                             }
1132                         }
1133                     }
1134                   else
1135                     {
1136                       /* It's not clear where the additions should be applied.
1137                          Let the user decide.  */
1138                       struct conflict *c = XMALLOC (struct conflict);
1139                       size_t j;
1140                       c->num_old_entries = 0;
1141                       c->old_entries = NULL;
1142                       c->num_modified_entries = edit->j2 - edit->j1 + 1;
1143                       c->modified_entries =
1144                         XNMALLOC (c->num_modified_entries, struct entry *);
1145                       for (j = edit->j1; j <= edit->j2; j++)
1146                         c->modified_entries[j - edit->j1] = modified_file.entries[j];
1147                       gl_list_add_last (result_conflicts, c);
1148                     }
1149                 }
1150               break;
1151             case REMOVAL:
1152               {
1153                 /* Apply the removals one by one.  */
1154                 size_t i;
1155                 for (i = edit->i1; i <= edit->i2; i++)
1156                   {
1157                     struct entry *removed_entry = ancestor_file.entries[i];
1158                     ssize_t k = index_mapping[i];
1159                     if (k >= 0
1160                         && entry_equals (removed_entry,
1161                                          mainstream_file.entries[k]))
1162                       {
1163                         /* The entry to be removed still exists in
1164                            mainstream_file.  Remove it.  */
1165                         gl_list_node_set_value (result_entries,
1166                                                 result_entries_pointers[k],
1167                                                 &empty_entry);
1168                       }
1169                     else
1170                       {
1171                         /* The entry to be removed was already removed or was
1172                            modified.  This is a conflict.  */
1173                         struct conflict *c = XMALLOC (struct conflict);
1174                         c->num_old_entries = 1;
1175                         c->old_entries =
1176                           XNMALLOC (c->num_old_entries, struct entry *);
1177                         c->old_entries[0] = removed_entry;
1178                         c->num_modified_entries = 0;
1179                         c->modified_entries = NULL;
1180                         gl_list_add_last (result_conflicts, c);
1181                       }
1182                   }
1183               }
1184               break;
1185             case CHANGE:
1186               {
1187                 bool done = false;
1188                 /* When the user usually merges entries from the same day,
1189                    and this edit is at the top of the file:  */
1190                 if (split_merged_entry && edit->j1 == 0)
1191                   {
1192                     /* Test whether the change is "simple merged", i.e. whether
1193                        it consists of additions, followed by an augmentation of
1194                        the first changed entry, followed by small changes of the
1195                        remaining entries:
1196                          entry_1
1197                          entry_2
1198                          ...
1199                          entry_n
1200                        are mapped to
1201                          added_entry
1202                          ...
1203                          added_entry
1204                          augmented_entry_1
1205                          modified_entry_2
1206                          ...
1207                          modified_entry_n.  */
1208                     if (edit->i2 - edit->i1 <= edit->j2 - edit->j1)
1209                       {
1210                         struct entry *split[2];
1211                         bool simple_merged =
1212                           try_split_merged_entry (ancestor_file.entries[edit->i1],
1213                                                   modified_file.entries[edit->i1 + edit->j2 - edit->i2],
1214                                                   split);
1215                         if (simple_merged)
1216                           {
1217                             size_t i;
1218                             for (i = edit->i1 + 1; i <= edit->i2; i++)
1219                               if (entry_fstrcmp (ancestor_file.entries[i],
1220                                                  modified_file.entries[i + edit->j2 - edit->i2])
1221                                   < FSTRCMP_THRESHOLD)
1222                                 {
1223                                   simple_merged = false;
1224                                   break;
1225                                 }
1226                           }
1227                         if (simple_merged)
1228                           {
1229                             /* Apply the additions at the top of modified_file.
1230                                Apply each of the single-entry changes
1231                                separately.  */
1232                             size_t num_changed = edit->i2 - edit->i1 + 1; /* > 0 */
1233                             size_t num_added = (edit->j2 - edit->j1 + 1) - num_changed;
1234                             ssize_t j;
1235                             /* First part of the split modified_file.entries[edit->j2 - edit->i2 + edit->i1]:  */
1236                             gl_list_add_first (result_entries, split[0]);
1237                             /* The additions.  */
1238                             for (j = edit->j1 + num_added - 1; j >= edit->j1; j--)
1239                               {
1240                                 struct entry *added_entry = modified_file.entries[j];
1241                                 gl_list_add_first (result_entries, added_entry);
1242                               }
1243                             /* Now the single-entry changes.  */
1244                             for (j = edit->j1 + num_added; j <= edit->j2; j++)
1245                               {
1246                                 struct entry *changed_entry =
1247                                   (j == edit->j1 + num_added
1248                                    ? split[1]
1249                                    : modified_file.entries[j]);
1250                                 size_t i = j + edit->i2 - edit->j2;
1251                                 ssize_t k = index_mapping[i];
1252                                 if (k >= 0
1253                                     && entry_equals (ancestor_file.entries[i],
1254                                                      mainstream_file.entries[k]))
1255                                   {
1256                                     gl_list_node_set_value (result_entries,
1257                                                             result_entries_pointers[k],
1258                                                             changed_entry);
1259                                   }
1260                                 else if (!entry_equals (ancestor_file.entries[i],
1261                                                         changed_entry))
1262                                   {
1263                                     struct conflict *c = XMALLOC (struct conflict);
1264                                     c->num_old_entries = 1;
1265                                     c->old_entries =
1266                                       XNMALLOC (c->num_old_entries, struct entry *);
1267                                     c->old_entries[0] = ancestor_file.entries[i];
1268                                     c->num_modified_entries = 1;
1269                                     c->modified_entries =
1270                                       XNMALLOC (c->num_modified_entries, struct entry *);
1271                                     c->modified_entries[0] = changed_entry;
1272                                     gl_list_add_last (result_conflicts, c);
1273                                   }
1274                               }
1275                             done = true;
1276                           }
1277                       }
1278                   }
1279                 if (!done)
1280                   {
1281                     bool simple;
1282                     /* Test whether the change is "simple", i.e. whether it
1283                        consists of small changes to the old ChangeLog entries
1284                        and additions before them:
1285                          entry_1
1286                          ...
1287                          entry_n
1288                        are mapped to
1289                          added_entry
1290                          ...
1291                          added_entry
1292                          modified_entry_1
1293                          ...
1294                          modified_entry_n.  */
1295                     if (edit->i2 - edit->i1 <= edit->j2 - edit->j1)
1296                       {
1297                         size_t i;
1298                         simple = true;
1299                         for (i = edit->i1; i <= edit->i2; i++)
1300                           if (entry_fstrcmp (ancestor_file.entries[i],
1301                                              modified_file.entries[i + edit->j2 - edit->i2])
1302                               < FSTRCMP_THRESHOLD)
1303                             {
1304                               simple = false;
1305                               break;
1306                             }
1307                       }
1308                     else
1309                       simple = false;
1310                     if (simple)
1311                       {
1312                         /* Apply the additions and each of the single-entry
1313                            changes separately.  */
1314                         size_t num_changed = edit->i2 - edit->i1 + 1; /* > 0 */
1315                         size_t num_added = (edit->j2 - edit->j1 + 1) - num_changed;
1316                         if (edit->j1 == 0)
1317                           {
1318                             /* A simple change at the top of modified_file.
1319                                Apply it to the top of mainstream_file.  */
1320                             ssize_t j;
1321                             for (j = edit->j1 + num_added - 1; j >= edit->j1; j--)
1322                               {
1323                                 struct entry *added_entry = modified_file.entries[j];
1324                                 gl_list_add_first (result_entries, added_entry);
1325                               }
1326                             for (j = edit->j1 + num_added; j <= edit->j2; j++)
1327                               {
1328                                 struct entry *changed_entry = modified_file.entries[j];
1329                                 size_t i = j + edit->i2 - edit->j2;
1330                                 ssize_t k = index_mapping[i];
1331                                 if (k >= 0
1332                                     && entry_equals (ancestor_file.entries[i],
1333                                                      mainstream_file.entries[k]))
1334                                   {
1335                                     gl_list_node_set_value (result_entries,
1336                                                             result_entries_pointers[k],
1337                                                             changed_entry);
1338                                   }
1339                                 else
1340                                   {
1341                                     struct conflict *c;
1342                                     ASSERT (!entry_equals (ancestor_file.entries[i],
1343                                                            changed_entry));
1344                                     c = XMALLOC (struct conflict);
1345                                     c->num_old_entries = 1;
1346                                     c->old_entries =
1347                                       XNMALLOC (c->num_old_entries, struct entry *);
1348                                     c->old_entries[0] = ancestor_file.entries[i];
1349                                     c->num_modified_entries = 1;
1350                                     c->modified_entries =
1351                                       XNMALLOC (c->num_modified_entries, struct entry *);
1352                                     c->modified_entries[0] = changed_entry;
1353                                     gl_list_add_last (result_conflicts, c);
1354                                   }
1355                               }
1356                             done = true;
1357                           }
1358                         else
1359                           {
1360                             ssize_t i_before;
1361                             ssize_t k_before;
1362                             bool linear;
1363                             i_before = diffs.index_mapping_reverse[edit->j1 - 1];
1364                             ASSERT (i_before >= 0);
1365                             /* A simple change after ancestor_file.entries[i_before].
1366                                See whether this entry and the following num_changed
1367                                entries still exist in mainstream_file and are still
1368                                consecutive.  */
1369                             k_before = index_mapping[i_before];
1370                             linear = (k_before >= 0);
1371                             if (linear)
1372                               {
1373                                 size_t i;
1374                                 for (i = i_before + 1; i <= i_before + num_changed; i++)
1375                                   if (index_mapping[i] != k_before + (i - i_before))
1376                                     {
1377                                       linear = false;
1378                                       break;
1379                                     }
1380                               }
1381                             if (linear)
1382                               {
1383                                 gl_list_node_t node_for_insert =
1384                                   result_entries_pointers[k_before + 1];
1385                                 ssize_t j;
1386                                 for (j = edit->j1 + num_added - 1; j >= edit->j1; j--)
1387                                   {
1388                                     struct entry *added_entry = modified_file.entries[j];
1389                                     gl_list_add_before (result_entries, node_for_insert, added_entry);
1390                                   }
1391                                 for (j = edit->j1 + num_added; j <= edit->j2; j++)
1392                                   {
1393                                     struct entry *changed_entry = modified_file.entries[j];
1394                                     size_t i = j + edit->i2 - edit->j2;
1395                                     ssize_t k = index_mapping[i];
1396                                     ASSERT (k >= 0);
1397                                     if (entry_equals (ancestor_file.entries[i],
1398                                                       mainstream_file.entries[k]))
1399                                       {
1400                                         gl_list_node_set_value (result_entries,
1401                                                                 result_entries_pointers[k],
1402                                                                 changed_entry);
1403                                       }
1404                                     else
1405                                       {
1406                                         struct conflict *c;
1407                                         ASSERT (!entry_equals (ancestor_file.entries[i],
1408                                                                changed_entry));
1409                                         c = XMALLOC (struct conflict);
1410                                         c->num_old_entries = 1;
1411                                         c->old_entries =
1412                                           XNMALLOC (c->num_old_entries, struct entry *);
1413                                         c->old_entries[0] = ancestor_file.entries[i];
1414                                         c->num_modified_entries = 1;
1415                                         c->modified_entries =
1416                                           XNMALLOC (c->num_modified_entries, struct entry *);
1417                                         c->modified_entries[0] = changed_entry;
1418                                         gl_list_add_last (result_conflicts, c);
1419                                       }
1420                                   }
1421                                 done = true;
1422                               }
1423                           }
1424                       }
1425                     else
1426                       {
1427                         /* A big change.
1428                            See whether the num_changed entries still exist
1429                            unchanged in mainstream_file and are still
1430                            consecutive.  */
1431                         ssize_t i_first;
1432                         ssize_t k_first;
1433                         bool linear_unchanged;
1434                         i_first = edit->i1;
1435                         k_first = index_mapping[i_first];
1436                         linear_unchanged =
1437                           (k_first >= 0
1438                            && entry_equals (ancestor_file.entries[i_first],
1439                                             mainstream_file.entries[k_first]));
1440                         if (linear_unchanged)
1441                           {
1442                             size_t i;
1443                             for (i = i_first + 1; i <= edit->i2; i++)
1444                               if (!(index_mapping[i] == k_first + (i - i_first)
1445                                     && entry_equals (ancestor_file.entries[i],
1446                                                      mainstream_file.entries[index_mapping[i]])))
1447                                 {
1448                                   linear_unchanged = false;
1449                                   break;
1450                                 }
1451                           }
1452                         if (linear_unchanged)
1453                           {
1454                             gl_list_node_t node_for_insert =
1455                               result_entries_pointers[k_first];
1456                             ssize_t j;
1457                             size_t i;
1458                             for (j = edit->j2; j >= edit->j1; j--)
1459                               {
1460                                 struct entry *new_entry = modified_file.entries[j];
1461                                 gl_list_add_before (result_entries, node_for_insert, new_entry);
1462                               }
1463                             for (i = edit->i1; i <= edit->i2; i++)
1464                               {
1465                                 ssize_t k = index_mapping[i];
1466                                 ASSERT (k >= 0);
1467                                 ASSERT (entry_equals (ancestor_file.entries[i],
1468                                                       mainstream_file.entries[k]));
1469                                 gl_list_node_set_value (result_entries,
1470                                                         result_entries_pointers[k],
1471                                                         &empty_entry);
1472                               }
1473                             done = true;
1474                           }
1475                       }
1476                   }
1477                 if (!done)
1478                   {
1479                     struct conflict *c = XMALLOC (struct conflict);
1480                     size_t i, j;
1481                     c->num_old_entries = edit->i2 - edit->i1 + 1;
1482                     c->old_entries =
1483                       XNMALLOC (c->num_old_entries, struct entry *);
1484                     for (i = edit->i1; i <= edit->i2; i++)
1485                       c->old_entries[i - edit->i1] = ancestor_file.entries[i];
1486                     c->num_modified_entries = edit->j2 - edit->j1 + 1;
1487                     c->modified_entries =
1488                       XNMALLOC (c->num_modified_entries, struct entry *);
1489                     for (j = edit->j1; j <= edit->j2; j++)
1490                       c->modified_entries[j - edit->j1] = modified_file.entries[j];
1491                     gl_list_add_last (result_conflicts, c);
1492                   }
1493               }
1494               break;
1495             }
1496         }
1497     }
1498
1499     /* Output the result.  */
1500     {
1501       FILE *fp = fopen (destination_file_name, "w");
1502       if (fp == NULL)
1503         {
1504           fprintf (stderr, "could not write file '%s'\n", destination_file_name);
1505           exit (EXIT_FAILURE);
1506         }
1507
1508       /* Output the conflicts at the top.  */
1509       {
1510         size_t n = gl_list_size (result_conflicts);
1511         size_t i;
1512         for (i = 0; i < n; i++)
1513           conflict_write (fp, (struct conflict *) gl_list_get_at (result_conflicts, i));
1514       }
1515       /* Output the modified and unmodified entries, in order.  */
1516       {
1517         gl_list_iterator_t iter = gl_list_iterator (result_entries);
1518         const void *elt;
1519         gl_list_node_t node;
1520         while (gl_list_iterator_next (&iter, &elt, &node))
1521           entry_write (fp, (struct entry *) elt);
1522         gl_list_iterator_free (&iter);
1523       }
1524
1525       if (fwriteerror (fp))
1526         {
1527           fprintf (stderr, "error writing to file '%s'\n", destination_file_name);
1528           exit (EXIT_FAILURE);
1529         }
1530     }
1531
1532     exit (gl_list_size (result_conflicts) > 0 ? EXIT_FAILURE : EXIT_SUCCESS);
1533   }
1534 }