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