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