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    efforts 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'.  During a "git cherry-pick", it is
 979            set to 'cherry-pick'.
 980          - During a "git stash apply", there is an environment variable of
 981            the form GITHEAD_<40_hex_digits>='Stashed changes'.  */
 982     {
 983       const char *var;
 984
 985       var = getenv ("GIT_DOWNSTREAM");
 986       if (var != NULL && var[0] != '\0')
 987         downstream = true;
 988       else
 989         {
 990           var = getenv ("GIT_UPSTREAM");
 991           if (var != NULL && var[0] != '\0')
 992             downstream = false;
 993           else
 994             {
 995               var = getenv ("GIT_REFLOG_ACTION");
 996               #if 0 /* Debugging code */
 997               printf ("GIT_REFLOG_ACTION=|%s|\n", var);
 998               #endif
 999               if (var != NULL
1000                   && ((strncmp (var, "pull", 4) == 0
1001                        && c_strstr (var, " --rebase") == NULL)
1002                       || strncmp (var, "merge origin", 12) == 0))
1003                 downstream = true;
1004               else
1005                 {
1006                   /* "git stash apply", "git rebase", "git cherry-pick" and
1007                      similar.  */
1008                   downstream = false;
1009                 }
1010             }
1011         }
1012     }
1013
1014     #if 0 /* Debugging code */
1015     {
1016       char buf[1000];
1017       printf ("First line of %%A:\n");
1018       sprintf (buf, "head -1 %s", destination_file_name); system (buf);
1019       printf ("First line of %%B:\n");
1020       sprintf (buf, "head -1 %s", other_file_name); system (buf);
1021       printf ("Guessing calling convention: %s\n",
1022               downstream
1023               ? "%A = modified by user, %B = upstream"
1024               : "%A = upstream, %B = modified by user");
1025     }
1026     #endif
1027
1028     if (downstream)
1029       {
1030         mainstream_file_name = other_file_name;
1031         modified_file_name = destination_file_name;
1032       }
1033     else
1034       {
1035         mainstream_file_name = destination_file_name;
1036         modified_file_name = other_file_name;
1037       }
1038
1039     /* Read the three files into memory.  */
1040     read_changelog_file (ancestor_file_name, &ancestor_file);
1041     read_changelog_file (mainstream_file_name, &mainstream_file);
1042     read_changelog_file (modified_file_name, &modified_file);
1043
1044     /* Compute correspondence between the entries of ancestor_file and of
1045        mainstream_file.  */
1046     {
1047       ssize_t *result[2];
1048       compute_mapping (&ancestor_file, &mainstream_file, result);
1049       index_mapping = result[0];
1050       index_mapping_reverse = result[1];
1051     }
1052
1053     /* Compute differences between the entries of ancestor_file and of
1054        modified_file.  */
1055     compute_differences (&ancestor_file, &modified_file, &diffs);
1056
1057     /* Compute the result.  */
1058     result_entries_pointers =
1059       XNMALLOC (mainstream_file.num_entries, gl_list_node_t);
1060     result_entries =
1061       gl_list_create_empty (GL_LINKED_LIST, entry_equals, entry_hashcode,
1062                             NULL, true);
1063     {
1064       size_t k;
1065       for (k = 0; k < mainstream_file.num_entries; k++)
1066         result_entries_pointers[k] =
1067           gl_list_add_last (result_entries, mainstream_file.entries[k]);
1068     }
1069     result_conflicts =
1070       gl_list_create_empty (GL_ARRAY_LIST, NULL, NULL, NULL, true);
1071     {
1072       size_t e;
1073       for (e = 0; e < diffs.num_edits; e++)
1074         {
1075           struct edit *edit = diffs.edits[e];
1076           switch (edit->type)
1077             {
1078             case ADDITION:
1079               if (edit->j1 == 0)
1080                 {
1081                   /* An addition to the top of modified_file.
1082                      Apply it to the top of mainstream_file.  */
1083                   ssize_t j;
1084                   for (j = edit->j2; j >= edit->j1; j--)
1085                     {
1086                       struct entry *added_entry = modified_file.entries[j];
1087                       gl_list_add_first (result_entries, added_entry);
1088                     }
1089                 }
1090               else
1091                 {
1092                   ssize_t i_before;
1093                   ssize_t i_after;
1094                   ssize_t k_before;
1095                   ssize_t k_after;
1096                   i_before = diffs.index_mapping_reverse[edit->j1 - 1];
1097                   ASSERT (i_before >= 0);
1098                   i_after = (edit->j2 + 1 == modified_file.num_entries
1099                              ? ancestor_file.num_entries
1100                              : diffs.index_mapping_reverse[edit->j2 + 1]);
1101                   ASSERT (i_after >= 0);
1102                   ASSERT (i_after == i_before + 1);
1103                   /* An addition between ancestor_file.entries[i_before] and
1104                      ancestor_file.entries[i_after].  See whether these two
1105                      entries still exist in mainstream_file and are still
1106                      consecutive.  */
1107                   k_before = index_mapping[i_before];
1108                   k_after = (i_after == ancestor_file.num_entries
1109                              ? mainstream_file.num_entries
1110                              : index_mapping[i_after]);
1111                   if (k_before >= 0 && k_after >= 0 && k_after == k_before + 1)
1112                     {
1113                       /* Yes, the entry before and after are still neighbours
1114                          in mainstream_file.  Apply the addition between
1115                          them.  */
1116                       if (k_after == mainstream_file.num_entries)
1117                         {
1118                           size_t j;
1119                           for (j = edit->j1; j <= edit->j2; j++)
1120                             {
1121                               struct entry *added_entry = modified_file.entries[j];
1122                               gl_list_add_last (result_entries, added_entry);
1123                             }
1124                         }
1125                       else
1126                         {
1127                           gl_list_node_t node_k_after = result_entries_pointers[k_after];
1128                           size_t j;
1129                           for (j = edit->j1; j <= edit->j2; j++)
1130                             {
1131                               struct entry *added_entry = modified_file.entries[j];
1132                               gl_list_add_before (result_entries, node_k_after, added_entry);
1133                             }
1134                         }
1135                     }
1136                   else
1137                     {
1138                       /* It's not clear where the additions should be applied.
1139                          Let the user decide.  */
1140                       struct conflict *c = XMALLOC (struct conflict);
1141                       size_t j;
1142                       c->num_old_entries = 0;
1143                       c->old_entries = NULL;
1144                       c->num_modified_entries = edit->j2 - edit->j1 + 1;
1145                       c->modified_entries =
1146                         XNMALLOC (c->num_modified_entries, struct entry *);
1147                       for (j = edit->j1; j <= edit->j2; j++)
1148                         c->modified_entries[j - edit->j1] = modified_file.entries[j];
1149                       gl_list_add_last (result_conflicts, c);
1150                     }
1151                 }
1152               break;
1153             case REMOVAL:
1154               {
1155                 /* Apply the removals one by one.  */
1156                 size_t i;
1157                 for (i = edit->i1; i <= edit->i2; i++)
1158                   {
1159                     struct entry *removed_entry = ancestor_file.entries[i];
1160                     ssize_t k = index_mapping[i];
1161                     if (k >= 0
1162                         && entry_equals (removed_entry,
1163                                          mainstream_file.entries[k]))
1164                       {
1165                         /* The entry to be removed still exists in
1166                            mainstream_file.  Remove it.  */
1167                         gl_list_node_set_value (result_entries,
1168                                                 result_entries_pointers[k],
1169                                                 &empty_entry);
1170                       }
1171                     else
1172                       {
1173                         /* The entry to be removed was already removed or was
1174                            modified.  This is a conflict.  */
1175                         struct conflict *c = XMALLOC (struct conflict);
1176                         c->num_old_entries = 1;
1177                         c->old_entries =
1178                           XNMALLOC (c->num_old_entries, struct entry *);
1179                         c->old_entries[0] = removed_entry;
1180                         c->num_modified_entries = 0;
1181                         c->modified_entries = NULL;
1182                         gl_list_add_last (result_conflicts, c);
1183                       }
1184                   }
1185               }
1186               break;
1187             case CHANGE:
1188               {
1189                 bool done = false;
1190                 /* When the user usually merges entries from the same day,
1191                    and this edit is at the top of the file:  */
1192                 if (split_merged_entry && edit->j1 == 0)
1193                   {
1194                     /* Test whether the change is "simple merged", i.e. whether
1195                        it consists of additions, followed by an augmentation of
1196                        the first changed entry, followed by small changes of the
1197                        remaining entries:
1198                          entry_1
1199                          entry_2
1200                          ...
1201                          entry_n
1202                        are mapped to
1203                          added_entry
1204                          ...
1205                          added_entry
1206                          augmented_entry_1
1207                          modified_entry_2
1208                          ...
1209                          modified_entry_n.  */
1210                     if (edit->i2 - edit->i1 <= edit->j2 - edit->j1)
1211                       {
1212                         struct entry *split[2];
1213                         bool simple_merged =
1214                           try_split_merged_entry (ancestor_file.entries[edit->i1],
1215                                                   modified_file.entries[edit->i1 + edit->j2 - edit->i2],
1216                                                   split);
1217                         if (simple_merged)
1218                           {
1219                             size_t i;
1220                             for (i = edit->i1 + 1; i <= edit->i2; i++)
1221                               if (entry_fstrcmp (ancestor_file.entries[i],
1222                                                  modified_file.entries[i + edit->j2 - edit->i2])
1223                                   < FSTRCMP_THRESHOLD)
1224                                 {
1225                                   simple_merged = false;
1226                                   break;
1227                                 }
1228                           }
1229                         if (simple_merged)
1230                           {
1231                             /* Apply the additions at the top of modified_file.
1232                                Apply each of the single-entry changes
1233                                separately.  */
1234                             size_t num_changed = edit->i2 - edit->i1 + 1; /* > 0 */
1235                             size_t num_added = (edit->j2 - edit->j1 + 1) - num_changed;
1236                             ssize_t j;
1237                             /* First part of the split modified_file.entries[edit->j2 - edit->i2 + edit->i1]:  */
1238                             gl_list_add_first (result_entries, split[0]);
1239                             /* The additions.  */
1240                             for (j = edit->j1 + num_added - 1; j >= edit->j1; j--)
1241                               {
1242                                 struct entry *added_entry = modified_file.entries[j];
1243                                 gl_list_add_first (result_entries, added_entry);
1244                               }
1245                             /* Now the single-entry changes.  */
1246                             for (j = edit->j1 + num_added; j <= edit->j2; j++)
1247                               {
1248                                 struct entry *changed_entry =
1249                                   (j == edit->j1 + num_added
1250                                    ? split[1]
1251                                    : modified_file.entries[j]);
1252                                 size_t i = j + edit->i2 - edit->j2;
1253                                 ssize_t k = index_mapping[i];
1254                                 if (k >= 0
1255                                     && entry_equals (ancestor_file.entries[i],
1256                                                      mainstream_file.entries[k]))
1257                                   {
1258                                     gl_list_node_set_value (result_entries,
1259                                                             result_entries_pointers[k],
1260                                                             changed_entry);
1261                                   }
1262                                 else if (!entry_equals (ancestor_file.entries[i],
1263                                                         changed_entry))
1264                                   {
1265                                     struct conflict *c = XMALLOC (struct conflict);
1266                                     c->num_old_entries = 1;
1267                                     c->old_entries =
1268                                       XNMALLOC (c->num_old_entries, struct entry *);
1269                                     c->old_entries[0] = ancestor_file.entries[i];
1270                                     c->num_modified_entries = 1;
1271                                     c->modified_entries =
1272                                       XNMALLOC (c->num_modified_entries, struct entry *);
1273                                     c->modified_entries[0] = changed_entry;
1274                                     gl_list_add_last (result_conflicts, c);
1275                                   }
1276                               }
1277                             done = true;
1278                           }
1279                       }
1280                   }
1281                 if (!done)
1282                   {
1283                     bool simple;
1284                     /* Test whether the change is "simple", i.e. whether it
1285                        consists of small changes to the old ChangeLog entries
1286                        and additions before them:
1287                          entry_1
1288                          ...
1289                          entry_n
1290                        are mapped to
1291                          added_entry
1292                          ...
1293                          added_entry
1294                          modified_entry_1
1295                          ...
1296                          modified_entry_n.  */
1297                     if (edit->i2 - edit->i1 <= edit->j2 - edit->j1)
1298                       {
1299                         size_t i;
1300                         simple = true;
1301                         for (i = edit->i1; i <= edit->i2; i++)
1302                           if (entry_fstrcmp (ancestor_file.entries[i],
1303                                              modified_file.entries[i + edit->j2 - edit->i2])
1304                               < FSTRCMP_THRESHOLD)
1305                             {
1306                               simple = false;
1307                               break;
1308                             }
1309                       }
1310                     else
1311                       simple = false;
1312                     if (simple)
1313                       {
1314                         /* Apply the additions and each of the single-entry
1315                            changes separately.  */
1316                         size_t num_changed = edit->i2 - edit->i1 + 1; /* > 0 */
1317                         size_t num_added = (edit->j2 - edit->j1 + 1) - num_changed;
1318                         if (edit->j1 == 0)
1319                           {
1320                             /* A simple change at the top of modified_file.
1321                                Apply it to the top of mainstream_file.  */
1322                             ssize_t j;
1323                             for (j = edit->j1 + num_added - 1; j >= edit->j1; j--)
1324                               {
1325                                 struct entry *added_entry = modified_file.entries[j];
1326                                 gl_list_add_first (result_entries, added_entry);
1327                               }
1328                             for (j = edit->j1 + num_added; j <= edit->j2; j++)
1329                               {
1330                                 struct entry *changed_entry = modified_file.entries[j];
1331                                 size_t i = j + edit->i2 - edit->j2;
1332                                 ssize_t k = index_mapping[i];
1333                                 if (k >= 0
1334                                     && entry_equals (ancestor_file.entries[i],
1335                                                      mainstream_file.entries[k]))
1336                                   {
1337                                     gl_list_node_set_value (result_entries,
1338                                                             result_entries_pointers[k],
1339                                                             changed_entry);
1340                                   }
1341                                 else
1342                                   {
1343                                     struct conflict *c;
1344                                     ASSERT (!entry_equals (ancestor_file.entries[i],
1345                                                            changed_entry));
1346                                     c = XMALLOC (struct conflict);
1347                                     c->num_old_entries = 1;
1348                                     c->old_entries =
1349                                       XNMALLOC (c->num_old_entries, struct entry *);
1350                                     c->old_entries[0] = ancestor_file.entries[i];
1351                                     c->num_modified_entries = 1;
1352                                     c->modified_entries =
1353                                       XNMALLOC (c->num_modified_entries, struct entry *);
1354                                     c->modified_entries[0] = changed_entry;
1355                                     gl_list_add_last (result_conflicts, c);
1356                                   }
1357                               }
1358                             done = true;
1359                           }
1360                         else
1361                           {
1362                             ssize_t i_before;
1363                             ssize_t k_before;
1364                             bool linear;
1365                             i_before = diffs.index_mapping_reverse[edit->j1 - 1];
1366                             ASSERT (i_before >= 0);
1367                             /* A simple change after ancestor_file.entries[i_before].
1368                                See whether this entry and the following num_changed
1369                                entries still exist in mainstream_file and are still
1370                                consecutive.  */
1371                             k_before = index_mapping[i_before];
1372                             linear = (k_before >= 0);
1373                             if (linear)
1374                               {
1375                                 size_t i;
1376                                 for (i = i_before + 1; i <= i_before + num_changed; i++)
1377                                   if (index_mapping[i] != k_before + (i - i_before))
1378                                     {
1379                                       linear = false;
1380                                       break;
1381                                     }
1382                               }
1383                             if (linear)
1384                               {
1385                                 gl_list_node_t node_for_insert =
1386                                   result_entries_pointers[k_before + 1];
1387                                 ssize_t j;
1388                                 for (j = edit->j1 + num_added - 1; j >= edit->j1; j--)
1389                                   {
1390                                     struct entry *added_entry = modified_file.entries[j];
1391                                     gl_list_add_before (result_entries, node_for_insert, added_entry);
1392                                   }
1393                                 for (j = edit->j1 + num_added; j <= edit->j2; j++)
1394                                   {
1395                                     struct entry *changed_entry = modified_file.entries[j];
1396                                     size_t i = j + edit->i2 - edit->j2;
1397                                     ssize_t k = index_mapping[i];
1398                                     ASSERT (k >= 0);
1399                                     if (entry_equals (ancestor_file.entries[i],
1400                                                       mainstream_file.entries[k]))
1401                                       {
1402                                         gl_list_node_set_value (result_entries,
1403                                                                 result_entries_pointers[k],
1404                                                                 changed_entry);
1405                                       }
1406                                     else
1407                                       {
1408                                         struct conflict *c;
1409                                         ASSERT (!entry_equals (ancestor_file.entries[i],
1410                                                                changed_entry));
1411                                         c = XMALLOC (struct conflict);
1412                                         c->num_old_entries = 1;
1413                                         c->old_entries =
1414                                           XNMALLOC (c->num_old_entries, struct entry *);
1415                                         c->old_entries[0] = ancestor_file.entries[i];
1416                                         c->num_modified_entries = 1;
1417                                         c->modified_entries =
1418                                           XNMALLOC (c->num_modified_entries, struct entry *);
1419                                         c->modified_entries[0] = changed_entry;
1420                                         gl_list_add_last (result_conflicts, c);
1421                                       }
1422                                   }
1423                                 done = true;
1424                               }
1425                           }
1426                       }
1427                     else
1428                       {
1429                         /* A big change.
1430                            See whether the num_changed entries still exist
1431                            unchanged in mainstream_file and are still
1432                            consecutive.  */
1433                         ssize_t i_first;
1434                         ssize_t k_first;
1435                         bool linear_unchanged;
1436                         i_first = edit->i1;
1437                         k_first = index_mapping[i_first];
1438                         linear_unchanged =
1439                           (k_first >= 0
1440                            && entry_equals (ancestor_file.entries[i_first],
1441                                             mainstream_file.entries[k_first]));
1442                         if (linear_unchanged)
1443                           {
1444                             size_t i;
1445                             for (i = i_first + 1; i <= edit->i2; i++)
1446                               if (!(index_mapping[i] == k_first + (i - i_first)
1447                                     && entry_equals (ancestor_file.entries[i],
1448                                                      mainstream_file.entries[index_mapping[i]])))
1449                                 {
1450                                   linear_unchanged = false;
1451                                   break;
1452                                 }
1453                           }
1454                         if (linear_unchanged)
1455                           {
1456                             gl_list_node_t node_for_insert =
1457                               result_entries_pointers[k_first];
1458                             ssize_t j;
1459                             size_t i;
1460                             for (j = edit->j2; j >= edit->j1; j--)
1461                               {
1462                                 struct entry *new_entry = modified_file.entries[j];
1463                                 gl_list_add_before (result_entries, node_for_insert, new_entry);
1464                               }
1465                             for (i = edit->i1; i <= edit->i2; i++)
1466                               {
1467                                 ssize_t k = index_mapping[i];
1468                                 ASSERT (k >= 0);
1469                                 ASSERT (entry_equals (ancestor_file.entries[i],
1470                                                       mainstream_file.entries[k]));
1471                                 gl_list_node_set_value (result_entries,
1472                                                         result_entries_pointers[k],
1473                                                         &empty_entry);
1474                               }
1475                             done = true;
1476                           }
1477                       }
1478                   }
1479                 if (!done)
1480                   {
1481                     struct conflict *c = XMALLOC (struct conflict);
1482                     size_t i, j;
1483                     c->num_old_entries = edit->i2 - edit->i1 + 1;
1484                     c->old_entries =
1485                       XNMALLOC (c->num_old_entries, struct entry *);
1486                     for (i = edit->i1; i <= edit->i2; i++)
1487                       c->old_entries[i - edit->i1] = ancestor_file.entries[i];
1488                     c->num_modified_entries = edit->j2 - edit->j1 + 1;
1489                     c->modified_entries =
1490                       XNMALLOC (c->num_modified_entries, struct entry *);
1491                     for (j = edit->j1; j <= edit->j2; j++)
1492                       c->modified_entries[j - edit->j1] = modified_file.entries[j];
1493                     gl_list_add_last (result_conflicts, c);
1494                   }
1495               }
1496               break;
1497             }
1498         }
1499     }
1500
1501     /* Output the result.  */
1502     {
1503       FILE *fp = fopen (destination_file_name, "w");
1504       if (fp == NULL)
1505         {
1506           fprintf (stderr, "could not write file '%s'\n", destination_file_name);
1507           exit (EXIT_FAILURE);
1508         }
1509
1510       /* Output the conflicts at the top.  */
1511       {
1512         size_t n = gl_list_size (result_conflicts);
1513         size_t i;
1514         for (i = 0; i < n; i++)
1515           conflict_write (fp, (struct conflict *) gl_list_get_at (result_conflicts, i));
1516       }
1517       /* Output the modified and unmodified entries, in order.  */
1518       {
1519         gl_list_iterator_t iter = gl_list_iterator (result_entries);
1520         const void *elt;
1521         gl_list_node_t node;
1522         while (gl_list_iterator_next (&iter, &elt, &node))
1523           entry_write (fp, (struct entry *) elt);
1524         gl_list_iterator_free (&iter);
1525       }
1526
1527       if (fwriteerror (fp))
1528         {
1529           fprintf (stderr, "error writing to file '%s'\n", destination_file_name);
1530           exit (EXIT_FAILURE);
1531         }
1532     }
1533
1534     exit (gl_list_size (result_conflicts) > 0 ? EXIT_FAILURE : EXIT_SUCCESS);
1535   }
1536 }