1 /* git-merge-changelog - git "merge" driver for GNU style ChangeLog files.
2 Copyright (C) 2008 Bruno Haible <bruno@clisp.org>
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.
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.
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/>. */
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.
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
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.)
43 $ gnulib-tool --create-testdir --dir=/tmp/testdir123 git-merge-changelog
48 - Add to .git/config of the checkout (or to your $HOME/.gitconfig) the lines
50 [merge "merge-changelog"]
51 name = GNU-style ChangeLog merge driver
52 driver = /usr/local/bin/git-merge-changelog %O %A %B
54 - In every directory that contains a ChangeLog file, add a file
55 '.gitattributes' with this line:
57 ChangeLog merge=merge-changelog
59 (See "man 5 gitattributes" for more info.)
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
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.
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.
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
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
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
105 - Changes are categorized into "simple changes":
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
127 #include <sys/types.h>
130 #include "progname.h"
132 #include "read-file.h"
134 #include "gl_array_list.h"
135 #include "gl_linkedhash_list.h"
136 #include "gl_linked_list.h"
138 #include "xmalloca.h"
141 #include "c-strstr.h"
142 #include "fwriteerror.h"
144 #define ASSERT(expr) \
152 #define FSTRCMP_THRESHOLD 0.6
154 /* Representation of a ChangeLog entry.
155 The string may contain NUL bytes; therefore it is represented as a plain
156 opaque memory region. */
163 /* Compare two entries for equality. */
165 entry_equals (const void *elt1, const void *elt2)
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;
173 /* Return a hash code of the contents of a ChangeLog entry. */
175 entry_hashcode (const void *elt)
177 const struct entry *entry = (const struct entry *) elt;
178 /* See http://www.haible.de/bruno/hashfunc.html. */
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)));
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. */
193 entry_fstrcmp (const struct entry *entry1, const struct entry *entry2)
195 /* fstrcmp works only on NUL terminated strings. */
199 if (memchr (entry1->string, '\0', entry1->length) != NULL)
201 if (memchr (entry2->string, '\0', entry2->length) != NULL)
203 memory = (char *) xmalloca (entry1->length + 1 + entry2->length + 1);
206 memcpy (p, entry1->string, entry1->length);
209 memcpy (p, entry2->string, entry2->length);
213 similarity = fstrcmp (memory, memory + entry1->length + 1);
218 /* This structure represents an entire ChangeLog file, after it was read
220 struct changelog_file
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. */
228 struct entry **entries;
231 /* Read a ChangeLog file into memory.
232 Return the contents in *RESULT. */
234 read_changelog_file (const char *filename, struct changelog_file *result)
236 /* Read the file in text mode, otherwise it's hard to recognize empty
239 char *contents = read_file (filename, &length);
240 if (contents == NULL)
242 fprintf (stderr, "could not read file '%s'\n", filename);
246 result->entries_list =
247 gl_list_create_empty (GL_LINKEDHASH_LIST, entry_equals, entry_hashcode,
249 result->entries_reversed =
250 gl_list_create_empty (GL_LINKEDHASH_LIST, entry_equals, entry_hashcode,
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. */
257 char *contents_end = contents + length;
258 char *start = contents;
259 while (start < contents_end)
261 /* Search the end of the current entry. */
265 while (ptr < contents_end)
267 ptr = memchr (ptr, '\n', contents_end - ptr);
274 if (contents_end - ptr >= 2
276 && !(ptr[1] == '\n' || ptr[1] == '\t' || ptr[1] == ' '))
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);
293 result->num_entries = gl_list_size (result->entries_list);
294 result->entries = XNMALLOC (result->num_entries, struct entry *);
297 gl_list_iterator_t iter = gl_list_iterator (result->entries_list);
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);
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
317 compute_mapping (struct changelog_file *file1, struct changelog_file *file2,
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;
328 index_mapping = XNMALLOC (n1, ssize_t);
329 for (i = 0; i < n1; i++)
330 index_mapping[i] = -1;
332 index_mapping_reverse = XNMALLOC (n2, ssize_t);
333 for (j = 0; j < n2; j++)
334 index_mapping_reverse[j] = -1;
336 for (i = n1 - 1; i >= 0; i--)
337 /* Take an entry from file1. */
338 if (index_mapping[i] < 0)
340 struct entry *entry = file1->entries[i];
341 /* Search whether it occurs in file2. */
342 j = gl_list_indexof (file2->entries_reversed, entry);
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. */
361 gl_list_indexof_from (file1->entries_reversed, n1 - curr_i,
366 gl_list_indexof_from (file2->entries_reversed, n2 - curr_j,
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;
381 for (i = n1 - 1; i >= 0; i--)
382 /* Take an entry from file1. */
383 if (index_mapping[i] < 0)
385 struct entry *entry_i = file1->entries[i];
386 /* Search whether it approximately occurs in file2. */
388 double best_j_similarity = 0.0;
389 for (j = n2 - 1; j >= 0; j--)
390 if (index_mapping_reverse[j] < 0)
392 double similarity = entry_fstrcmp (entry_i, file2->entries[j]);
393 if (similarity > best_j_similarity)
396 best_j_similarity = similarity;
399 if (best_j_similarity >= FSTRCMP_THRESHOLD)
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. */
405 double best_i_similarity = 0.0;
407 for (ii = n1 - 1; ii >= 0; ii--)
408 if (index_mapping[ii] < 0)
411 entry_fstrcmp (file1->entries[ii], entry_j);
412 if (similarity > best_i_similarity)
415 best_i_similarity = similarity;
418 if (best_i_similarity >= FSTRCMP_THRESHOLD && best_i == i)
420 index_mapping[i] = best_j;
421 index_mapping_reverse[best_j] = i;
426 result[0] = index_mapping;
427 result[1] = index_mapping_reverse;
430 /* An "edit" is a textual modification performed by the user, that needs to
431 be applied to the other file. */
434 /* Some consecutive entries were added. */
436 /* Some consecutive entries were removed; some other consecutive entries
437 were added at the same position. (Not necessarily the same number of
440 /* Some consecutive entries were removed. */
444 /* This structure represents an edit. */
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 */
454 /* This structure represents the differences from one file, FILE1, to another
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. */
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
482 /* Compute the differences between the entries of FILE1 and the entries of
485 compute_differences (struct changelog_file *file1, struct changelog_file *file2,
486 struct differences *result)
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. */
494 size_t n1 = file1->num_entries;
495 size_t n2 = file2->num_entries;
498 gl_list_t /* <struct edit *> */ edits;
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;
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);
516 /* Complete the index_mapping and index_mapping_reverse arrays. */
519 while (i < n1 || j < n2)
521 while (i < n1 && ctxt.index_mapping[i] < 0)
523 while (j < n2 && ctxt.index_mapping_reverse[j] < 0)
525 ASSERT ((i < n1) == (j < n2));
526 if (i == n1 && j == n2)
528 ctxt.index_mapping[i] = j;
529 ctxt.index_mapping_reverse[j] = i;
534 /* Create the edits. */
535 edits = gl_list_create_empty (GL_ARRAY_LIST, NULL, NULL, NULL, true);
538 while (i < n1 || j < n2)
544 e = XMALLOC (struct edit);
548 gl_list_add_last (edits, e);
555 e = XMALLOC (struct edit);
559 gl_list_add_last (edits, e);
562 if (ctxt.index_mapping[i] >= 0)
564 if (ctxt.index_mapping_reverse[j] >= 0)
566 ASSERT (ctxt.index_mapping[i] == j);
567 ASSERT (ctxt.index_mapping_reverse[j] == i);
574 ASSERT (ctxt.index_mapping_reverse[j] < 0);
575 e = XMALLOC (struct edit);
580 while (j < n2 && ctxt.index_mapping_reverse[j] < 0);
582 gl_list_add_last (edits, e);
587 if (ctxt.index_mapping_reverse[j] >= 0)
590 ASSERT (ctxt.index_mapping[i] < 0);
591 e = XMALLOC (struct edit);
596 while (i < n1 && ctxt.index_mapping[i] < 0);
598 gl_list_add_last (edits, e);
603 ASSERT (ctxt.index_mapping[i] < 0);
604 ASSERT (ctxt.index_mapping_reverse[j] < 0);
605 e = XMALLOC (struct edit);
610 while (i < n1 && ctxt.index_mapping[i] < 0);
615 while (j < n2 && ctxt.index_mapping_reverse[j] < 0);
617 gl_list_add_last (edits, e);
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 *);
628 gl_list_iterator_t iter = gl_list_iterator (edits);
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);
638 /* An empty entry. */
639 static struct entry empty_entry = { NULL, 0 };
641 /* Write the contents of an entry to the output stream FP. */
643 entry_write (FILE *fp, struct entry *entry)
645 if (entry->length > 0)
646 fwrite (entry->string, 1, entry->length, fp);
649 /* This structure represents a conflict.
650 A conflict can occur for various reasons. */
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;
661 /* Write a conflict to the output stream FP, including markers. */
663 conflict_write (FILE *fp, struct conflict *c)
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);
680 static const struct option long_options[] =
682 { "help", no_argument, NULL, 'h' },
683 { "version", no_argument, NULL, 'V' },
687 /* Print a usage mesage and exit. */
691 if (status != EXIT_SUCCESS)
692 fprintf (stderr, "Try `%s --help' for more information.\n",
696 printf ("Usage: %s [OPTION] O-FILE-NAME A-FILE-NAME B-FILE-NAME\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");
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");
709 fputs ("Report bugs to <bug-gnu-gettext@gnu.org>.\n",
717 main (int argc, char *argv[])
723 /* Set program name for messages. */
724 set_program_name (argv[0]);
726 /* Set default values for variables. */
730 /* Parse command line options. */
731 while ((optchar = getopt_long (argc, argv, "hV", long_options, NULL)) != EOF)
734 case '\0': /* Long option. */
743 usage (EXIT_FAILURE);
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\
756 printf ("Written by %s.\n", "Bruno Haible");
762 /* Help is requested. */
763 usage (EXIT_SUCCESS);
766 /* Test argument count. */
767 if (optind + 3 != argc)
768 error (EXIT_FAILURE, 0, "expected three arguments");
771 const char *ancestor_file_name; /* O-FILE-NAME */
772 const char *destination_file_name; /* A-FILE-NAME */
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;
789 ancestor_file_name = argv[optind];
790 destination_file_name = argv[optind + 1];
791 other_file_name = argv[optind + 2];
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").
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*
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
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.
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'. */
840 var = getenv ("GIT_DOWNSTREAM");
841 if (var != NULL && var[0] != '\0')
845 var = getenv ("GIT_UPSTREAM");
846 if (var != NULL && var[0] != '\0')
850 var = getenv ("GIT_REFLOG_ACTION");
851 #if 0 /* Debugging code */
852 printf ("GIT_REFLOG_ACTION=|%s|\n", var);
855 && ((strncmp (var, "pull", 4) == 0
856 && c_strstr (var, " --rebase") == NULL)
857 || strncmp (var, "merge origin", 12) == 0))
861 /* "git stash apply", "git rebase" and similar. */
868 #if 0 /* Debugging code */
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",
877 ? "%A = modified by user, %B = upstream"
878 : "%A = upstream, %B = modified by user");
884 mainstream_file_name = other_file_name;
885 modified_file_name = destination_file_name;
889 mainstream_file_name = destination_file_name;
890 modified_file_name = other_file_name;
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);
898 /* Compute correspondence between the entries of ancestor_file and of
902 compute_mapping (&ancestor_file, &mainstream_file, result);
903 index_mapping = result[0];
904 index_mapping_reverse = result[1];
907 /* Compute differences between the entries of ancestor_file and of
909 compute_differences (&ancestor_file, &modified_file, &diffs);
911 /* Compute the result. */
912 result_entries_pointers =
913 XNMALLOC (mainstream_file.num_entries, gl_list_node_t);
915 gl_list_create_empty (GL_LINKED_LIST, entry_equals, entry_hashcode,
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]);
924 gl_list_create_empty (GL_ARRAY_LIST, NULL, NULL, NULL, true);
927 for (e = 0; e < diffs.num_edits; e++)
929 struct edit *edit = diffs.edits[e];
935 /* An addition to the top of modified_file.
936 Apply it to the top of mainstream_file. */
938 for (j = edit->j2; j >= edit->j1; j--)
940 struct entry *added_entry = modified_file.entries[j];
941 gl_list_add_first (result_entries, added_entry);
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
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)
967 /* Yes, the entry before and after are still neighbours
968 in mainstream_file. Apply the addition between
970 if (k_after == mainstream_file.num_entries)
973 for (j = edit->j1; j <= edit->j2; j++)
975 struct entry *added_entry = modified_file.entries[j];
976 gl_list_add_last (result_entries, added_entry);
981 gl_list_node_t node_k_after = result_entries_pointers[k_after];
983 for (j = edit->j1; j <= edit->j2; j++)
985 struct entry *added_entry = modified_file.entries[j];
986 gl_list_add_before (result_entries, node_k_after, added_entry);
992 /* It's not clear where the additions should be applied.
993 Let the user decide. */
994 struct conflict *c = XMALLOC (struct conflict);
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);
1009 /* Apply the removals one by one. */
1011 for (i = edit->i1; i <= edit->i2; i++)
1013 struct entry *removed_entry = ancestor_file.entries[i];
1014 ssize_t k = index_mapping[i];
1016 && entry_equals (removed_entry,
1017 mainstream_file.entries[k]))
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],
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;
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);
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:
1050 added_entry ... added_entry modified_entry_1 ... modified_entry_n. */
1051 if (edit->i2 - edit->i1 <= edit->j2 - edit->j1)
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)
1069 /* Apply the additions and each of the single-entry changes
1071 size_t num_changed = edit->i2 - edit->i1 + 1; /* > 0 */
1072 size_t num_added = (edit->j2 - edit->j1 + 1) - num_changed;
1075 /* A simple change at the top of modified_file.
1076 Apply it to the top of mainstream_file. */
1078 for (j = edit->j1 + num_added - 1; j >= edit->j1; j--)
1080 struct entry *added_entry = modified_file.entries[j];
1081 gl_list_add_first (result_entries, added_entry);
1083 for (j = edit->j1 + num_added; j <= edit->j2; j++)
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];
1089 && entry_equals (ancestor_file.entries[i],
1090 mainstream_file.entries[k]))
1092 gl_list_node_set_value (result_entries,
1093 result_entries_pointers[k],
1098 struct conflict *c = XMALLOC (struct conflict);
1099 c->num_old_entries = 1;
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);
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
1123 k_before = index_mapping[i_before];
1124 linear = (k_before >= 0);
1128 for (i = i_before + 1; i <= i_before + num_changed; i++)
1129 if (index_mapping[i] != k_before + (i - i_before))
1137 gl_list_node_t node_for_insert =
1138 result_entries_pointers[k_before + 1];
1140 for (j = edit->j1 + num_added - 1; j >= edit->j1; j--)
1142 struct entry *added_entry = modified_file.entries[j];
1143 gl_list_add_before (result_entries, node_for_insert, added_entry);
1145 for (j = edit->j1 + num_added; j <= edit->j2; j++)
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];
1151 if (entry_equals (ancestor_file.entries[i],
1152 mainstream_file.entries[k]))
1154 gl_list_node_set_value (result_entries,
1155 result_entries_pointers[k],
1160 struct conflict *c = XMALLOC (struct conflict);
1161 c->num_old_entries = 1;
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);
1179 See whether the num_changed entries still exist unchanged
1180 in mainstream_file and are still consecutive. */
1183 bool linear_unchanged;
1185 k_first = index_mapping[i_first];
1188 && entry_equals (ancestor_file.entries[i_first],
1189 mainstream_file.entries[k_first]));
1190 if (linear_unchanged)
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]])))
1198 linear_unchanged = false;
1202 if (linear_unchanged)
1204 gl_list_node_t node_for_insert =
1205 result_entries_pointers[k_first];
1208 for (j = edit->j2; j >= edit->j1; j--)
1210 struct entry *new_entry = modified_file.entries[j];
1211 gl_list_add_before (result_entries, node_for_insert, new_entry);
1213 for (i = edit->i1; i <= edit->i2; i++)
1215 ssize_t k = index_mapping[i];
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],
1228 struct conflict *c = XMALLOC (struct conflict);
1230 c->num_old_entries = edit->i2 - edit->i1 + 1;
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);
1248 /* Output the result. */
1250 FILE *fp = fopen (destination_file_name, "w");
1253 fprintf (stderr, "could not write file '%s'\n", destination_file_name);
1254 exit (EXIT_FAILURE);
1257 /* Output the conflicts at the top. */
1259 size_t n = gl_list_size (result_conflicts);
1261 for (i = 0; i < n; i++)
1262 conflict_write (fp, (struct conflict *) gl_list_get_at (result_conflicts, i));
1265 size_t n = gl_list_size (result_entries);
1267 for (i = 0; i < n; i++)
1268 entry_write (fp, (struct entry *) gl_list_get_at (result_entries, i));
1271 if (fwriteerror (fp))
1273 fprintf (stderr, "error writing to file '%s'\n", destination_file_name);
1274 exit (EXIT_FAILURE);
1278 exit (gl_list_size (result_conflicts) > 0 ? EXIT_FAILURE : EXIT_SUCCESS);