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