Mercurial > hg > octave-lyh > gnulib-hg
changeset 9690:521de8c5a745
New module 'git-merge-changelog'.
author | Bruno Haible <bruno@clisp.org> |
---|---|
date | Mon, 11 Feb 2008 01:16:24 +0100 |
parents | 827726e8abb1 |
children | ae73b5517c84 |
files | ChangeLog lib/git-merge-changelog.c modules/git-merge-changelog |
diffstat | 3 files changed, 1315 insertions(+), 0 deletions(-) [+] |
line wrap: on
line diff
--- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,9 @@ +2008-02-10 Bruno Haible <bruno@clisp.org> + + New module 'git-merge-changelog'. + * modules/git-merge-changelog: New file. + * lib/git-merge-changelog.c: New file. + 2008-02-10 Jim Meyering <meyering@redhat.com> useless-if-before-free: New option: --list (-l).
new file mode 100644 --- /dev/null +++ b/lib/git-merge-changelog.c @@ -0,0 +1,1273 @@ +/* git-merge-changelog - git "merge" driver for GNU style ChangeLog files. + Copyright (C) 2008 Bruno Haible <bruno@clisp.org> + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. */ + +/* README: + The default merge driver of 'git' *always* produces conflicts when + pulling public modifications into a privately modified ChangeLog file. + This is because ChangeLog files are always modified at the top; the + default merge driver has no clue how to deal with this. Furthermore + the conflicts are presented with more <<<< ==== >>>> markers than + necessary; this is because the default merge driver makes pointless + effects to look at the individual line changes inside a ChangeLog entry. + + This program serves as a 'git' merge driver that avoids these problems. + 1. It produces no conflict when ChangeLog entries have been inserted + at the top both in the public and in the private modification. It + puts the privately added entries above the publicly added entries. + 2. It respects the structure of ChangeLog files: entries are not split + into lines but kept together. + 3. It also handles the case of small modifications of past ChangeLog + entries, or of removed ChangeLog entries: they are merged as one + would expect it. + 4. Conflicts are presented at the top of the file, rather than where + they occurred, so that the user will see them immediately. (Unlike + for source code written in some programming language, conflict markers + that are located several hundreds lines from the top will not cause + any syntax error and therefore would be likely to remain unnoticed.) + */ + +/* Installation: + $ gnulib-tool --create-testdir --dir=/tmp/testdir123 git-merge-changelog + $ cd /tmp/testdir123 + $ ./configure + $ make + $ make install + - Add to .git/config of the checkout (or to your $HOME/.gitconfig) the lines + + [merge "cl-merge"] + name = GNU-style ChangeLog merge driver + driver = /usr/local/bin/git-merge-changelog %O %A %B + + - In every directory that contains a ChangeLog file, add a file + '.gitattributes' with this line: + + ChangeLog merge=cl-merge + + (See "man 5 gitattributes" for more info.) + */ + +/* Calling convention: + A merge driver is called with three filename arguments: + 1. %O = The common ancestor of %A and %B. + 2. %A = The file's contents from the "current branch". + 3. %B = The file's contents from the "other branch"; this is the contents + being merged in. + + In case of a "git stash apply" or of an upstream pull (e.g. from a subsystem + maintainer to a central maintainer): + 2. %A = The file's newest pulled contents; modified by other committers. + 3. %B = The user's newest copy of the file; modified by the user. + In case of a downstream pull (e.g. from a central repository to the user): + 2. %A = The user's newest copy of the file; modified by the user. + 3. %B = The file's newest pulled contents; modified by other committers. + + It should write its merged output into file %A. It can also echo some + remarks to stdout. It should exit with return code 0 if the merge could + be resolved cleanly, or with non-zero return code if there were conflicts. + */ + +/* How it works: + The structure of a ChangeLog file: It consists of ChangeLog entries. A + ChangeLog entry starts at a line following a blank line and that starts with + a non-whitespace character, or at the beginning of a file. + The merge driver works as follows: It reads the three files into memory and + dissects them into ChangeLog entries. It then finds the differences between + %O and %B. They are classified as: + - removals (some consecutive entries removed), + - changes (some consecutive entries removed, some consecutive entries + added), + - additions (some consecutive entries added). + The driver then attempts to apply the changes to %A. + To this effect, it first computes a correspondence between the entries in %O + and the entries in %A, using fuzzy string matching to still identify changed + entries. + - Removals are applied one by one. If the entry is present in %A, at any + position, it is removed. If not, the removal is marked as a conflict. + - Additions at the top of %B are applied at the top of %A. + - Additions between entry x and entry y (y may be the file end) in %B are + applied between entry x and entry y in %A (if they still exist and are + still consecutive in %A), otherwise the additions are marked as a + conflict. + - Changes are categorized into "simple changes": + entry1 ... entryn + are mapped to + added_entry ... added_entry modified_entry1 ... modified_entryn, + where the correspondence between entry_i and modified_entry_i is still + clear; and "big changes": these are all the rest. Simple changes at the + top of %B are applied by putting the added entries at the top of %A. The + changes in simple changes are applied one by one; possibly leading to + single-entry conflicts. Big changes are applied en bloc, possibly + leading to conflicts spanning multiple entries. + - Conflicts are output at the top of the file and cause an exit status of + 1. + */ + +#include <config.h> + +#include <getopt.h> +#include <limits.h> +#include <stdbool.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <sys/types.h> +#include <unistd.h> + +#include "progname.h" +#include "error.h" +#include "read-file.h" +#include "gl_list.h" +#include "gl_array_list.h" +#include "gl_linkedhash_list.h" +#include "gl_linked_list.h" +#include "xalloc.h" +#include "xmalloca.h" +#include "fstrcmp.h" +#include "minmax.h" +#include "fwriteerror.h" + +#define ASSERT(expr) \ + do \ + { \ + if (!(expr)) \ + abort (); \ + } \ + while (0) + +#define FSTRCMP_THRESHOLD 0.6 + +/* Representation of a ChangeLog entry. + The string may contain NUL bytes; therefore it is represented as a plain + opaque memory region. */ +struct entry +{ + char *string; + size_t length; +}; + +/* Compare two entries for equality. */ +static bool +entry_equals (const void *elt1, const void *elt2) +{ + const struct entry *entry1 = (const struct entry *) elt1; + const struct entry *entry2 = (const struct entry *) elt2; + return entry1->length == entry2->length + && memcmp (entry1->string, entry2->string, entry1->length) == 0; +}; + +/* Return a hash code of the contents of a ChangeLog entry. */ +static size_t +entry_hashcode (const void *elt) +{ + const struct entry *entry = (const struct entry *) elt; + /* See http://www.haible.de/bruno/hashfunc.html. */ + const char *s; + size_t n; + size_t h = 0; + + for (s = entry->string, n = entry->length; n > 0; s++, n--) + h = (unsigned char) *s + ((h << 9) | (h >> (sizeof (size_t) * CHAR_BIT - 9))); + + return h; +} + +/* Perform a fuzzy comparison of two ChangeLog entries. + Return a similarity measure of the two entries, a value between 0 and 1. + 0 stands for very distinct, 1 for identical. */ +static double +entry_fstrcmp (const struct entry *entry1, const struct entry *entry2) +{ + /* fstrcmp works only on NUL terminated strings. */ + char *memory; + double similarity; + + if (memchr (entry1->string, '\0', entry1->length) != NULL) + return 0.0; + if (memchr (entry2->string, '\0', entry2->length) != NULL) + return 0.0; + memory = (char *) xmalloca (entry1->length + 1 + entry2->length + 1); + { + char *p = memory; + memcpy (p, entry1->string, entry1->length); + p += entry1->length; + *p++ = '\0'; + memcpy (p, entry2->string, entry2->length); + p += entry2->length; + *p++ = '\0'; + } + similarity = fstrcmp (memory, memory + entry1->length + 1); + freea (memory); + return similarity; +} + +/* This structure represents an entire ChangeLog file, after it was read + into memory. */ +struct changelog_file +{ + /* The entries, as a list. */ + gl_list_t /* <struct entry *> */ entries_list; + /* The entries, as a list in opposite direction. */ + gl_list_t /* <struct entry *> */ entries_reversed; + /* The entries, as an array. */ + size_t num_entries; + struct entry **entries; +}; + +/* Read a ChangeLog file into memory. + Return the contents in *RESULT. */ +static void +read_changelog_file (const char *filename, struct changelog_file *result) +{ + /* Read the file in text mode, otherwise it's hard to recognize empty + lines. */ + size_t length; + char *contents = read_file (filename, &length); + if (contents == NULL) + { + fprintf (stderr, "could not read file '%s'\n", filename); + exit (EXIT_FAILURE); + } + + result->entries_list = + gl_list_create_empty (GL_LINKEDHASH_LIST, entry_equals, entry_hashcode, + NULL, true); + result->entries_reversed = + gl_list_create_empty (GL_LINKEDHASH_LIST, entry_equals, entry_hashcode, + NULL, true); + /* A ChangeLog file consists of ChangeLog entries. A ChangeLog entry starts + at a line following a blank line and that starts with a non-whitespace + character, or at the beginning of a file. + Split the file contents into entries. */ + { + char *contents_end = contents + length; + char *start = contents; + while (start < contents_end) + { + /* Search the end of the current entry. */ + char *ptr = start; + struct entry *curr; + + while (ptr < contents_end) + { + ptr = memchr (ptr, '\n', contents_end - ptr); + if (ptr == NULL) + { + ptr = contents_end; + break; + } + ptr++; + if (contents_end - ptr >= 2 + && ptr[0] == '\n' + && !(ptr[1] == '\n' || ptr[1] == '\t' || ptr[1] == ' ')) + { + ptr++; + break; + } + } + + curr = XMALLOC (struct entry); + curr->string = start; + curr->length = ptr - start; + gl_list_add_last (result->entries_list, curr); + gl_list_add_first (result->entries_reversed, curr); + + start = ptr; + } + } + + result->num_entries = gl_list_size (result->entries_list); + result->entries = XNMALLOC (result->num_entries, struct entry *); + { + size_t index = 0; + gl_list_iterator_t iter = gl_list_iterator (result->entries_list); + const void *elt; + gl_list_node_t node; + while (gl_list_iterator_next (&iter, &elt, &node)) + result->entries[index++] = (struct entry *) elt; + gl_list_iterator_free (&iter); + ASSERT (index == result->num_entries); + } +} + +/* Compute a mapping (correspondence) between entries of FILE1 and of FILE2. + Return a set of two arrays: + - An array mapping FILE1 indices to FILE2 indices (or -1 when the entry + from FILE1 is not found in FILE2). + - An array mapping FILE2 indices to FILE1 indices (or -1 when the entry + from FILE2 is not found in FILE1). + The correspondence also takes into account small modifications; i.e. the + indicated relation is not equality of entries but best-match similarity + of entries. */ +static void +compute_mapping (struct changelog_file *file1, struct changelog_file *file2, + ssize_t *result[2]) +{ + /* Mapping from indices in file1 to indices in file2. */ + ssize_t *index_mapping; + /* Mapping from indices in file2 to indices in file1. */ + ssize_t *index_mapping_reverse; + size_t n1 = file1->num_entries; + size_t n2 = file2->num_entries; + ssize_t i, j; + + index_mapping = XNMALLOC (n1, ssize_t); + for (i = 0; i < n1; i++) + index_mapping[i] = -1; + + index_mapping_reverse = XNMALLOC (n2, ssize_t); + for (j = 0; j < n2; j++) + index_mapping_reverse[j] = -1; + + for (i = n1 - 1; i >= 0; i--) + /* Take an entry from file1. */ + if (index_mapping[i] < 0) + { + struct entry *entry = file1->entries[i]; + /* Search whether it occurs in file2. */ + j = gl_list_indexof (file2->entries_reversed, entry); + if (j >= 0) + { + j = n2 - 1 - j; + /* Found an exact correspondence. */ + ASSERT (index_mapping_reverse[j] < 0); + index_mapping[i] = j; + index_mapping_reverse[j] = i; + /* Look for more occurrences of the same entry. */ + { + ssize_t curr_i = i; + ssize_t curr_j = j; + + for (;;) + { + ssize_t next_i; + ssize_t next_j; + + next_i = + gl_list_indexof_from (file1->entries_reversed, n1 - curr_i, + entry); + if (next_i < 0) + break; + next_j = + gl_list_indexof_from (file2->entries_reversed, n2 - curr_j, + entry); + if (next_j < 0) + break; + curr_i = n1 - 1 - next_i; + curr_j = n2 - 1 - next_j; + ASSERT (index_mapping[curr_i] < 0); + ASSERT (index_mapping_reverse[curr_j] < 0); + index_mapping[curr_i] = curr_j; + index_mapping_reverse[curr_j] = curr_i; + } + } + } + } + + for (i = n1 - 1; i >= 0; i--) + /* Take an entry from file1. */ + if (index_mapping[i] < 0) + { + struct entry *entry_i = file1->entries[i]; + /* Search whether it approximately occurs in file2. */ + ssize_t best_j = -1; + double best_j_similarity = 0.0; + for (j = n2 - 1; j >= 0; j--) + if (index_mapping_reverse[j] < 0) + { + double similarity = entry_fstrcmp (entry_i, file2->entries[j]); + if (similarity > best_j_similarity) + { + best_j = j; + best_j_similarity = similarity; + } + } + if (best_j_similarity >= FSTRCMP_THRESHOLD) + { + /* Found a similar entry in file2. */ + struct entry *entry_j = file2->entries[best_j]; + /* Search whether it approximately occurs in file1 at index i. */ + ssize_t best_i = -1; + double best_i_similarity = 0.0; + ssize_t ii; + for (ii = n1 - 1; ii >= 0; ii--) + if (index_mapping[ii] < 0) + { + double similarity = + entry_fstrcmp (file1->entries[ii], entry_j); + if (similarity > best_i_similarity) + { + best_i = i; + best_i_similarity = similarity; + } + } + if (best_i_similarity >= FSTRCMP_THRESHOLD && best_i == i) + { + index_mapping[i] = best_j; + index_mapping_reverse[best_j] = i; + } + } + } + + result[0] = index_mapping; + result[1] = index_mapping_reverse; +} + +/* An "edit" is a textual modification performed by the user, that needs to + be applied to the other file. */ +enum edit_type +{ + /* Some consecutive entries were added. */ + ADDITION, + /* Some consecutive entries were removed; some other consecutive entries + were added at the same position. (Not necessarily the same number of + entries.) */ + CHANGE, + /* Some consecutive entries were removed. */ + REMOVAL +}; + +/* This structure represents an edit. */ +struct edit +{ + enum edit_type type; + /* Range of indices into the entries of FILE1. */ + ssize_t i1, i2; /* first, last index; only used for CHANGE, REMOVAL */ + /* Range of indices into the entries of FILE2. */ + ssize_t j1, j2; /* first, last index; only used for ADDITION, CHANGE */ +}; + +/* This structure represents the differences from one file, FILE1, to another + file, FILE2. */ +struct differences +{ + /* An array mapping FILE1 indices to FILE2 indices (or -1 when the entry + from FILE1 is not found in FILE2). */ + ssize_t *index_mapping; + /* An array mapping FILE2 indices to FILE1 indices (or -1 when the entry + from FILE2 is not found in FILE1). */ + ssize_t *index_mapping_reverse; + /* The edits that transform FILE1 into FILE2. */ + size_t num_edits; + struct edit **edits; +}; + +/* Import the difference detection algorithm from GNU diff. */ +#define ELEMENT struct entry * +#define EQUAL entry_equals +#define OFFSET ssize_t +#define EXTRA_CONTEXT_FIELDS \ + ssize_t *index_mapping; \ + ssize_t *index_mapping_reverse; +#define NOTE_DELETE(ctxt, xoff) \ + ctxt->index_mapping[xoff] = -1 +#define NOTE_INSERT(ctxt, yoff) \ + ctxt->index_mapping_reverse[yoff] = -1 +#include "diffseq.h" + +/* Compute the differences between the entries of FILE1 and the entries of + FILE2. */ +static void +compute_differences (struct changelog_file *file1, struct changelog_file *file2, + struct differences *result) +{ + /* Unlike compute_mapping, which mostly ignores the order of the entries and + therefore works well when some entries are permuted, here we use the order. + I think this is needed in order to distinguish changes from + additions+removals; I don't know how to say what is a "change" if the + files are considered as unordered sets of entries. */ + struct context ctxt; + size_t n1 = file1->num_entries; + size_t n2 = file2->num_entries; + ssize_t i; + ssize_t j; + gl_list_t /* <struct edit *> */ edits; + + ctxt.xvec = file1->entries; + ctxt.yvec = file2->entries; + ctxt.index_mapping = XNMALLOC (n1, ssize_t); + for (i = 0; i < n1; i++) + ctxt.index_mapping[i] = 0; + ctxt.index_mapping_reverse = XNMALLOC (n2, ssize_t); + for (j = 0; j < n2; j++) + ctxt.index_mapping_reverse[j] = 0; + ctxt.fdiag = XNMALLOC (2 * (n1 + n2 + 3), ssize_t) + n2 + 1; + ctxt.bdiag = ctxt.fdiag + n1 + n2 + 3; + ctxt.too_expensive = n1 + n2; + + /* Store in ctxt.index_mapping and ctxt.index_mapping_reverse a -1 for + each removed or added entry. */ + compareseq (0, n1, 0, n2, 0, &ctxt); + + /* Complete the index_mapping and index_mapping_reverse arrays. */ + i = 0; + j = 0; + while (i < n1 || j < n2) + { + while (i < n1 && ctxt.index_mapping[i] < 0) + i++; + while (j < n2 && ctxt.index_mapping_reverse[j] < 0) + j++; + ASSERT ((i < n1) == (j < n2)); + if (i == n1 && j == n2) + break; + ctxt.index_mapping[i] = j; + ctxt.index_mapping_reverse[j] = i; + i++; + j++; + } + + /* Create the edits. */ + edits = gl_list_create_empty (GL_ARRAY_LIST, NULL, NULL, NULL, true); + i = 0; + j = 0; + while (i < n1 || j < n2) + { + if (i == n1) + { + struct edit *e; + ASSERT (j < n2); + e = XMALLOC (struct edit); + e->type = ADDITION; + e->j1 = j; + e->j2 = n2 - 1; + gl_list_add_last (edits, e); + break; + } + if (j == n2) + { + struct edit *e; + ASSERT (i < n1); + e = XMALLOC (struct edit); + e->type = REMOVAL; + e->i1 = i; + e->i2 = n1 - 1; + gl_list_add_last (edits, e); + break; + } + if (ctxt.index_mapping[i] >= 0) + { + if (ctxt.index_mapping_reverse[j] >= 0) + { + ASSERT (ctxt.index_mapping[i] == j); + ASSERT (ctxt.index_mapping_reverse[j] == i); + i++; + j++; + } + else + { + struct edit *e; + ASSERT (ctxt.index_mapping_reverse[j] < 0); + e = XMALLOC (struct edit); + e->type = ADDITION; + e->j1 = j; + do + j++; + while (j < n2 && ctxt.index_mapping_reverse[j] < 0); + e->j2 = j - 1; + gl_list_add_last (edits, e); + } + } + else + { + if (ctxt.index_mapping_reverse[j] >= 0) + { + struct edit *e; + ASSERT (ctxt.index_mapping[i] < 0); + e = XMALLOC (struct edit); + e->type = REMOVAL; + e->i1 = i; + do + i++; + while (i < n1 && ctxt.index_mapping[i] < 0); + e->i2 = i - 1; + gl_list_add_last (edits, e); + } + else + { + struct edit *e; + ASSERT (ctxt.index_mapping[i] < 0); + ASSERT (ctxt.index_mapping_reverse[j] < 0); + e = XMALLOC (struct edit); + e->type = CHANGE; + e->i1 = i; + do + i++; + while (i < n1 && ctxt.index_mapping[i] < 0); + e->i2 = i - 1; + e->j1 = j; + do + j++; + while (j < n2 && ctxt.index_mapping_reverse[j] < 0); + e->j2 = j - 1; + gl_list_add_last (edits, e); + } + } + } + + result->index_mapping = ctxt.index_mapping; + result->index_mapping_reverse = ctxt.index_mapping_reverse; + result->num_edits = gl_list_size (edits); + result->edits = XNMALLOC (result->num_edits, struct edit *); + { + size_t index = 0; + gl_list_iterator_t iter = gl_list_iterator (edits); + const void *elt; + gl_list_node_t node; + while (gl_list_iterator_next (&iter, &elt, &node)) + result->edits[index++] = (struct edit *) elt; + gl_list_iterator_free (&iter); + ASSERT (index == result->num_edits); + } +} + +/* An empty entry. */ +static struct entry empty_entry = { NULL, 0 }; + +/* Write the contents of an entry to the output stream FP. */ +static void +entry_write (FILE *fp, struct entry *entry) +{ + if (entry->length > 0) + fwrite (entry->string, 1, entry->length, fp); +} + +/* This structure represents a conflict. + A conflict can occur for various reasons. */ +struct conflict +{ + /* Parts from the ancestor file. */ + size_t num_old_entries; + struct entry **old_entries; + /* Parts of the modified file. */ + size_t num_modified_entries; + struct entry **modified_entries; +}; + +/* Write a conflict to the output stream FP, including markers. */ +static void +conflict_write (FILE *fp, struct conflict *c) +{ + size_t i; + + /* Use the same syntax as git's default merge driver. + Don't indent the contents of the entries (with things like ">" or "-"), + otherwise the user needs more textual editing to resolve the conflict. */ + fputs ("<<<<<<<\n", fp); + for (i = 0; i < c->num_old_entries; i++) + entry_write (fp, c->old_entries[i]); + fputs ("=======\n", fp); + for (i = 0; i < c->num_modified_entries; i++) + entry_write (fp, c->modified_entries[i]); + fputs (">>>>>>>\n", fp); +} + +/* Long options. */ +static const struct option long_options[] = +{ + { "help", no_argument, NULL, 'h' }, + { "version", no_argument, NULL, 'V' }, + { NULL, 0, NULL, 0 } +}; + +/* Print a usage mesage and exit. */ +static void +usage (int status) +{ + if (status != EXIT_SUCCESS) + fprintf (stderr, "Try `%s --help' for more information.\n", + program_name); + else + { + printf ("Usage: %s [OPTION] O-FILE-NAME A-FILE-NAME B-FILE-NAME\n", + program_name); + printf ("\n"); + printf ("Merges independent modifications of a ChangeLog style file.\n"); + printf ("O-FILE-NAME names the original file, the ancestor of the two others.\n"); + printf ("A-FILE-NAME names the publicly modified file.\n"); + printf ("B-FILE-NAME names the user-modified file.\n"); + printf ("Writes the merged file into A-FILE-NAME.\n"); + printf ("\n"); + printf ("Informative output:\n"); + printf (" -h, --help display this help and exit\n"); + printf (" -V, --version output version information and exit\n"); + printf ("\n"); + fputs ("Report bugs to <bug-gnu-gettext@gnu.org>.\n", + stdout); + } + + exit (status); +} + +int +main (int argc, char *argv[]) +{ + int optchar; + bool do_help; + bool do_version; + + /* Set program name for messages. */ + set_program_name (argv[0]); + + /* Set default values for variables. */ + do_help = false; + do_version = false; + + /* Parse command line options. */ + while ((optchar = getopt_long (argc, argv, "hV", long_options, NULL)) != EOF) + switch (optchar) + { + case '\0': /* Long option. */ + break; + case 'h': + do_help = true; + break; + case 'V': + do_version = true; + break; + default: + usage (EXIT_FAILURE); + } + + if (do_version) + { + /* Version information is requested. */ + printf ("%s\n", program_name); + printf ("Copyright (C) %s Free Software Foundation, Inc.\n\ +License GPLv2+: GNU GPL version 2 or later <http://gnu.org/licenses/gpl.html>\n\ +This is free software: you are free to change and redistribute it.\n\ +There is NO WARRANTY, to the extent permitted by law.\n\ +", + "2008"); + printf ("Written by %s.\n", "Bruno Haible"); + exit (EXIT_SUCCESS); + } + + if (do_help) + { + /* Help is requested. */ + usage (EXIT_SUCCESS); + } + + /* Test argument count. */ + if (optind + 3 != argc) + error (EXIT_FAILURE, 0, "expected three arguments"); + + { + const char *ancestor_file_name; /* O-FILE-NAME */ + const char *destination_file_name; /* A-FILE-NAME */ + bool downstream; + const char *other_file_name; /* B-FILE-NAME */ + const char *mainstream_file_name; + const char *modified_file_name; + struct changelog_file ancestor_file; + struct changelog_file mainstream_file; + struct changelog_file modified_file; + /* Mapping from indices in ancestor_file to indices in mainstream_file. */ + ssize_t *index_mapping; + /* Mapping from indices in mainstream_file to indices in ancestor_file. */ + ssize_t *index_mapping_reverse; + struct differences diffs; + gl_list_node_t *result_entries_pointers; /* array of pointers into result_entries */ + gl_list_t /* <struct entry *> */ result_entries; + gl_list_t /* <struct conflict *> */ result_conflicts; + + ancestor_file_name = argv[optind]; + destination_file_name = argv[optind + 1]; + other_file_name = argv[optind + 2]; + + /* Heuristic to determine whether it's a pull in downstream direction + (e.g. pull from a centralized server) or a pull in upstream direction + (e.g. "git stash apply"). + + For ChangeLog this distinction is important. The difference between + an "upstream" and a "downstream" repository is that more people are + looking at the "upstream" repository. They want to be informed about + changes and expect them to be shown at the top of the ChangeLog. + When a user pulls downstream, on the other hand, he has two options: + a) He gets the change entries from the central repository also at the + top of his ChangeLog, and his own changes come after them. + b) He gets the change entries from the central repository after those + he has collected for his branch. His own change entries stay at + the top of the ChangeLog file. + In the case a) he has to reorder the ChangeLog before he can commit. + No one does that. So most people want b). + In other words, the order of entries in a ChangeLog should represent + the order in which they have flown (or will flow) into the *central* + repository. + + But in git this is fundamentally indistinguishable, because when Linus + pulls patches from akpm and akpm pulls patches from Linus, it's not + clear which of the two is more "upstream". Also, when you have many + branches in a repository and pull from one to another, "git" has no way + to know which branch is more "upstream" than the other. The git-tag(1) + manual page also says: + "One important aspect of git is it is distributed, and being + distributed largely means there is no inherent "upstream" or + "downstream" in the system." + Therefore anyone who attempts to produce a ChangeLog from the merge + history will fail. + + Here we allow the user to specify the pull direction through an + environment variable (GIT_UPSTREAM or GIT_DOWNSTREAM). If these two + environment variables are not set, we assume a "simple single user" + usage pattern: He manages local changes through stashes and uses + "git pull" only to pull downstream. + + How to distinguish these situation? There are several hints: + - During a "git stash apply", GIT_REFLOG_ACTION is not set. During + a "git pull", it is set to 'pull'. + - During a "git stash apply", there is an environment variable of + the form GITHEAD_<40_hex_digits>='Stashed changes'. */ + { + const char *var; + + var = getenv ("GIT_DOWNSTREAM"); + if (var != NULL && var[0] != '\0') + downstream = true; + else + { + var = getenv ("GIT_UPSTREAM"); + if (var != NULL && var[0] != '\0') + downstream = false; + else + { + var = getenv ("GIT_REFLOG_ACTION"); + #if 0 /* Debugging code */ + printf ("GIT_REFLOG_ACTION=|%s|\n", var); + #endif + if (var != NULL + && (strncmp (var, "pull", 4) == 0 + || strncmp (var, "merge origin", 12) == 0)) + downstream = true; + else + { + /* "git stash apply", "git rebase" and similar. */ + downstream = false; + } + } + } + } + + #if 0 /* Debugging code */ + { + char buf[1000]; + printf ("First line of %%A:\n"); + sprintf (buf, "head -1 %s", destination_file_name); system (buf); + printf ("First line of %%B:\n"); + sprintf (buf, "head -1 %s", other_file_name); system (buf); + printf ("Guessing direction: %sstream\n", downstream ? "down" : "up"); + } + #endif + + if (downstream) + { + mainstream_file_name = other_file_name; + modified_file_name = destination_file_name; + } + else + { + mainstream_file_name = destination_file_name; + modified_file_name = other_file_name; + } + + /* Read the three files into memory. */ + read_changelog_file (ancestor_file_name, &ancestor_file); + read_changelog_file (mainstream_file_name, &mainstream_file); + read_changelog_file (modified_file_name, &modified_file); + + /* Compute correspondence between the entries of ancestor_file and of + mainstream_file. */ + { + ssize_t *result[2]; + compute_mapping (&ancestor_file, &mainstream_file, result); + index_mapping = result[0]; + index_mapping_reverse = result[1]; + } + + /* Compute differences between the entries of ancestor_file and of + modified_file. */ + compute_differences (&ancestor_file, &modified_file, &diffs); + + /* Compute the result. */ + result_entries_pointers = + XNMALLOC (mainstream_file.num_entries, gl_list_node_t); + result_entries = + gl_list_create_empty (GL_LINKED_LIST, entry_equals, entry_hashcode, + NULL, true); + { + size_t k; + for (k = 0; k < mainstream_file.num_entries; k++) + result_entries_pointers[k] = + gl_list_add_last (result_entries, mainstream_file.entries[k]); + } + result_conflicts = + gl_list_create_empty (GL_ARRAY_LIST, NULL, NULL, NULL, true); + { + size_t e; + for (e = 0; e < diffs.num_edits; e++) + { + struct edit *edit = diffs.edits[e]; + switch (edit->type) + { + case ADDITION: + if (edit->j1 == 0) + { + /* An addition to the top of modified_file. + Apply it to the top of mainstream_file. */ + ssize_t j; + for (j = edit->j2; j >= edit->j1; j--) + { + struct entry *added_entry = modified_file.entries[j]; + gl_list_add_first (result_entries, added_entry); + } + } + else + { + ssize_t i_before; + ssize_t i_after; + ssize_t k_before; + ssize_t k_after; + i_before = diffs.index_mapping_reverse[edit->j1 - 1]; + ASSERT (i_before >= 0); + i_after = (edit->j2 + 1 == modified_file.num_entries + ? ancestor_file.num_entries + : diffs.index_mapping_reverse[edit->j2 + 1]); + ASSERT (i_after >= 0); + ASSERT (i_after == i_before + 1); + /* An addition between ancestor_file.entries[i_before] and + ancestor_file.entries[i_after]. See whether these two + entries still exist in mainstream_file and are still + consecutive. */ + k_before = index_mapping[i_before]; + k_after = (i_after == ancestor_file.num_entries + ? mainstream_file.num_entries + : index_mapping[i_after]); + if (k_before >= 0 && k_after >= 0 && k_after == k_before + 1) + { + /* Yes, the entry before and after are still neighbours + in mainstream_file. Apply the addition between + them. */ + if (k_after == mainstream_file.num_entries) + { + size_t j; + for (j = edit->j1; j <= edit->j2; j++) + { + struct entry *added_entry = modified_file.entries[j]; + gl_list_add_last (result_entries, added_entry); + } + } + else + { + gl_list_node_t node_k_after = result_entries_pointers[k_after]; + size_t j; + for (j = edit->j1; j <= edit->j2; j++) + { + struct entry *added_entry = modified_file.entries[j]; + gl_list_add_before (result_entries, node_k_after, added_entry); + } + } + } + else + { + /* It's not clear where the additions should be applied. + Let the user decide. */ + struct conflict *c = XMALLOC (struct conflict); + size_t j; + c->num_old_entries = 0; + c->old_entries = NULL; + c->num_modified_entries = edit->j2 - edit->j1 + 1; + c->modified_entries = + XNMALLOC (c->num_modified_entries, struct entry *); + for (j = edit->j1; j <= edit->j2; j++) + c->modified_entries[j - edit->j1] = modified_file.entries[j]; + gl_list_add_last (result_conflicts, c); + } + } + break; + case REMOVAL: + { + /* Apply the removals one by one. */ + size_t i; + for (i = edit->i1; i <= edit->i2; i++) + { + struct entry *removed_entry = ancestor_file.entries[i]; + ssize_t k = index_mapping[i]; + if (k >= 0 + && entry_equals (removed_entry, + mainstream_file.entries[k])) + { + /* The entry to be removed still exists in + mainstream_file. Remove it. */ + gl_list_node_set_value (result_entries, + result_entries_pointers[k], + &empty_entry); + } + else + { + /* The entry to be removed was already removed or was + modified. This is a conflict. */ + struct conflict *c = XMALLOC (struct conflict); + c->num_old_entries = 1; + c->old_entries = + XNMALLOC (c->num_old_entries, struct entry *); + c->old_entries[0] = removed_entry; + c->num_modified_entries = 0; + c->modified_entries = NULL; + gl_list_add_last (result_conflicts, c); + } + } + } + break; + case CHANGE: + { + bool simple; + bool done; + /* Test whether the change is "simple", i.e. whether it + consists of small changes to the old ChangeLog entries + and additions before them: + entry_1 ... entry_n + are mapped to + added_entry ... added_entry modified_entry_1 ... modified_entry_n. */ + if (edit->i2 - edit->i1 <= edit->j2 - edit->j1) + { + size_t i; + simple = true; + for (i = edit->i1; i <= edit->i2; i++) + if (entry_fstrcmp (ancestor_file.entries[i], + modified_file.entries[i + edit->j2 - edit->i2]) + < FSTRCMP_THRESHOLD) + { + simple = false; + break; + } + } + else + simple = false; + done = false; + if (simple) + { + /* Apply the additions and each of the single-entry changes + separately. */ + size_t num_changed = edit->i2 - edit->i1 + 1; /* > 0 */ + size_t num_added = (edit->j2 - edit->j1 + 1) - num_changed; + if (edit->j1 == 0) + { + /* A simple change at the top of modified_file. + Apply it to the top of mainstream_file. */ + ssize_t j; + for (j = edit->j1 + num_added - 1; j >= edit->j1; j--) + { + struct entry *added_entry = modified_file.entries[j]; + gl_list_add_first (result_entries, added_entry); + } + for (j = edit->j1 + num_added; j <= edit->j2; j++) + { + struct entry *changed_entry = modified_file.entries[j]; + size_t i = j + edit->i2 - edit->j2; + ssize_t k = index_mapping[i]; + if (k >= 0 + && entry_equals (ancestor_file.entries[i], + mainstream_file.entries[k])) + { + gl_list_node_set_value (result_entries, + result_entries_pointers[k], + changed_entry); + } + else + { + struct conflict *c = XMALLOC (struct conflict); + c->num_old_entries = 1; + c->old_entries = + XNMALLOC (c->num_old_entries, struct entry *); + c->old_entries[0] = ancestor_file.entries[i]; + c->num_modified_entries = 1; + c->modified_entries = + XNMALLOC (c->num_modified_entries, struct entry *); + c->modified_entries[0] = changed_entry; + gl_list_add_last (result_conflicts, c); + } + } + done = true; + } + else + { + ssize_t i_before; + ssize_t k_before; + bool linear; + i_before = diffs.index_mapping_reverse[edit->j1 - 1]; + ASSERT (i_before >= 0); + /* A simple change after ancestor_file.entries[i_before]. + See whether this entry and the following num_changed + entries still exist in mainstream_file and are still + consecutive. */ + k_before = index_mapping[i_before]; + linear = (k_before >= 0); + if (linear) + { + size_t i; + for (i = i_before + 1; i <= i_before + num_changed; i++) + if (index_mapping[i] != k_before + (i - i_before)) + { + linear = false; + break; + } + } + if (linear) + { + gl_list_node_t node_for_insert = + result_entries_pointers[k_before + 1]; + ssize_t j; + for (j = edit->j1 + num_added - 1; j >= edit->j1; j--) + { + struct entry *added_entry = modified_file.entries[j]; + gl_list_add_before (result_entries, node_for_insert, added_entry); + } + for (j = edit->j1 + num_added; j <= edit->j2; j++) + { + struct entry *changed_entry = modified_file.entries[j]; + size_t i = j + edit->i2 - edit->j2; + ssize_t k = index_mapping[i]; + ASSERT (k >= 0); + if (entry_equals (ancestor_file.entries[i], + mainstream_file.entries[k])) + { + gl_list_node_set_value (result_entries, + result_entries_pointers[k], + changed_entry); + } + else + { + struct conflict *c = XMALLOC (struct conflict); + c->num_old_entries = 1; + c->old_entries = + XNMALLOC (c->num_old_entries, struct entry *); + c->old_entries[0] = ancestor_file.entries[i]; + c->num_modified_entries = 1; + c->modified_entries = + XNMALLOC (c->num_modified_entries, struct entry *); + c->modified_entries[0] = changed_entry; + gl_list_add_last (result_conflicts, c); + } + } + done = true; + } + } + } + else + { + /* A big change. + See whether the num_changed entries still exist unchanged + in mainstream_file and are still consecutive. */ + ssize_t i_first; + ssize_t k_first; + bool linear_unchanged; + i_first = edit->i1; + k_first = index_mapping[i_first]; + linear_unchanged = + (k_first >= 0 + && entry_equals (ancestor_file.entries[i_first], + mainstream_file.entries[k_first])); + if (linear_unchanged) + { + size_t i; + for (i = i_first + 1; i <= edit->i2; i++) + if (!(index_mapping[i] == k_first + (i - i_first) + && entry_equals (ancestor_file.entries[i], + mainstream_file.entries[index_mapping[i]]))) + { + linear_unchanged = false; + break; + } + } + if (linear_unchanged) + { + gl_list_node_t node_for_insert = + result_entries_pointers[k_first]; + ssize_t j; + size_t i; + for (j = edit->j2; j >= edit->j1; j--) + { + struct entry *new_entry = modified_file.entries[j]; + gl_list_add_before (result_entries, node_for_insert, new_entry); + } + for (i = edit->i1; i <= edit->i2; i++) + { + ssize_t k = index_mapping[i]; + ASSERT (k >= 0); + ASSERT (entry_equals (ancestor_file.entries[i], + mainstream_file.entries[k])); + gl_list_node_set_value (result_entries, + result_entries_pointers[k], + &empty_entry); + } + done = true; + } + } + if (!done) + { + struct conflict *c = XMALLOC (struct conflict); + size_t i, j; + c->num_old_entries = edit->i2 - edit->i1 + 1; + c->old_entries = + XNMALLOC (c->num_old_entries, struct entry *); + for (i = edit->i1; i <= edit->i2; i++) + c->old_entries[i - edit->i1] = ancestor_file.entries[i]; + c->num_modified_entries = edit->j2 - edit->j1 + 1; + c->modified_entries = + XNMALLOC (c->num_modified_entries, struct entry *); + for (j = edit->j1; j <= edit->j2; j++) + c->modified_entries[j - edit->j1] = modified_file.entries[j]; + gl_list_add_last (result_conflicts, c); + } + } + break; + } + } + } + + /* Output the result. */ + { + FILE *fp = fopen (destination_file_name, "w"); + if (fp == NULL) + { + fprintf (stderr, "could not write file '%s'\n", destination_file_name); + exit (EXIT_FAILURE); + } + + /* Output the conflicts at the top. */ + { + size_t n = gl_list_size (result_conflicts); + size_t i; + for (i = 0; i < n; i++) + conflict_write (fp, (struct conflict *) gl_list_get_at (result_conflicts, i)); + } + { + size_t n = gl_list_size (result_entries); + size_t i; + for (i = 0; i < n; i++) + entry_write (fp, (struct entry *) gl_list_get_at (result_entries, i)); + } + + if (fwriteerror (fp)) + { + fprintf (stderr, "error writing to file '%s'\n", destination_file_name); + exit (EXIT_FAILURE); + } + } + + exit (gl_list_size (result_conflicts) > 0 ? EXIT_FAILURE : EXIT_SUCCESS); + } +}
new file mode 100644 --- /dev/null +++ b/modules/git-merge-changelog @@ -0,0 +1,36 @@ +Description: +git "merge" driver for GNU style ChangeLog files + +Files: +lib/git-merge-changelog.c + +Depends-on: +getopt +stdbool +progname +error +read-file +list +array-list +linkedhash-list +linked-list +xalloc +xmalloca +fstrcmp +minmax +fwriteerror + +configure.ac: + +Makefile.am: +bin_PROGRAMS = git-merge-changelog +git_merge_changelog_LDADD = -L. -lgnu + +Include: + +License: +GPL + +Maintainer: +Bruno Haible +