/* git-merge-changelog - git "merge" driver for GNU style ChangeLog files.
- Copyright (C) 2008 Bruno Haible <bruno@clisp.org>
+ Copyright (C) 2008-2009 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
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.
+ efforts 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
#include "gl_list.h"
#include "gl_array_list.h"
#include "gl_linkedhash_list.h"
+#include "gl_rbtreehash_list.h"
#include "gl_linked_list.h"
#include "xalloc.h"
#include "xmalloca.h"
{
char *string;
size_t length;
+ /* Cache for the hash code. */
+ bool hashcode_cached;
+ size_t hashcode;
};
+/* Create an entry.
+ The memory region passed by the caller must of indefinite extent. It is
+ *not* copied here. */
+static struct entry *
+entry_create (char *string, size_t length)
+{
+ struct entry *result = XMALLOC (struct entry);
+ result->string = string;
+ result->length = length;
+ result->hashcode_cached = false;
+ return result;
+}
+
/* Compare two entries for equality. */
static bool
entry_equals (const void *elt1, const void *elt2)
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;
+ struct entry *entry = (struct entry *) elt;
+ if (!entry->hashcode_cached)
+ {
+ /* 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)));
+ 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;
+ entry->hashcode = h;
+ entry->hashcode_cached = true;
+ }
+ return entry->hashcode;
}
/* 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. */
+ 0 stands for very distinct, 1 for identical.
+ If the result is < LOWER_BOUND, an arbitrary other value < LOWER_BOUND can
+ be returned. */
static double
-entry_fstrcmp (const struct entry *entry1, const struct entry *entry2)
+entry_fstrcmp (const struct entry *entry1, const struct entry *entry2,
+ double lower_bound)
{
/* fstrcmp works only on NUL terminated strings. */
char *memory;
p += entry2->length;
*p++ = '\0';
}
- similarity = fstrcmp (memory, memory + entry1->length + 1);
+ similarity =
+ fstrcmp_bounded (memory, memory + entry1->length + 1, lower_bound);
freea (memory);
return similarity;
}
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,
+ gl_list_create_empty (GL_RBTREEHASH_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
}
}
- curr = XMALLOC (struct entry);
- curr->string = start;
- curr->length = ptr - start;
+ curr = entry_create (start, ptr - start);
gl_list_add_last (result->entries_list, curr);
gl_list_add_first (result->entries_reversed, curr);
}
}
+/* A mapping (correspondence) between entries of FILE1 and of FILE2. */
+struct entries_mapping
+{
+ struct changelog_file *file1;
+ struct changelog_file *file2;
+ /* Mapping from indices in FILE1 to indices in FILE2.
+ A value -1 means that the entry from FILE1 is not found in FILE2.
+ A value -2 means that it has not yet been computed. */
+ ssize_t *index_mapping;
+ /* Mapping from indices in FILE2 to indices in FILE1.
+ A value -1 means that the entry from FILE2 is not found in FILE1.
+ A value -2 means that it has not yet been computed. */
+ ssize_t *index_mapping_reverse;
+};
+
+/* Look up (or lazily compute) the mapping of an entry in FILE1.
+ i is the index in FILE1.
+ Return the index in FILE2, or -1 when the entry is not found in FILE2. */
+static ssize_t
+entries_mapping_get (struct entries_mapping *mapping, ssize_t i)
+{
+ if (mapping->index_mapping[i] < -1)
+ {
+ struct changelog_file *file1 = mapping->file1;
+ struct changelog_file *file2 = mapping->file2;
+ size_t n1 = file1->num_entries;
+ size_t n2 = file2->num_entries;
+ struct entry *entry_i = file1->entries[i];
+ ssize_t j;
+
+ /* 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 (mapping->index_mapping_reverse[j] < 0)
+ {
+ double similarity =
+ entry_fstrcmp (entry_i, file2->entries[j], best_j_similarity);
+ 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 (mapping->index_mapping[ii] < 0)
+ {
+ double similarity =
+ entry_fstrcmp (file1->entries[ii], entry_j,
+ best_i_similarity);
+ if (similarity > best_i_similarity)
+ {
+ best_i = ii;
+ best_i_similarity = similarity;
+ }
+ }
+ if (best_i_similarity >= FSTRCMP_THRESHOLD && best_i == i)
+ {
+ mapping->index_mapping[i] = best_j;
+ mapping->index_mapping_reverse[best_j] = i;
+ }
+ }
+ if (mapping->index_mapping[i] < -1)
+ /* It does not approximately occur in FILE2.
+ Remember it, for next time. */
+ mapping->index_mapping[i] = -1;
+ }
+ return mapping->index_mapping[i];
+}
+
+/* Look up (or lazily compute) the mapping of an entry in FILE2.
+ j is the index in FILE2.
+ Return the index in FILE1, or -1 when the entry is not found in FILE1. */
+static ssize_t
+entries_mapping_reverse_get (struct entries_mapping *mapping, ssize_t j)
+{
+ if (mapping->index_mapping_reverse[j] < -1)
+ {
+ struct changelog_file *file1 = mapping->file1;
+ struct changelog_file *file2 = mapping->file2;
+ size_t n1 = file1->num_entries;
+ size_t n2 = file2->num_entries;
+ struct entry *entry_j = file2->entries[j];
+ ssize_t i;
+
+ /* Search whether it approximately occurs in file1. */
+ ssize_t best_i = -1;
+ double best_i_similarity = 0.0;
+ for (i = n1 - 1; i >= 0; i--)
+ if (mapping->index_mapping[i] < 0)
+ {
+ double similarity =
+ entry_fstrcmp (file1->entries[i], entry_j, best_i_similarity);
+ if (similarity > best_i_similarity)
+ {
+ best_i = i;
+ best_i_similarity = similarity;
+ }
+ }
+ if (best_i_similarity >= FSTRCMP_THRESHOLD)
+ {
+ /* Found a similar entry in file1. */
+ struct entry *entry_i = file1->entries[best_i];
+ /* Search whether it approximately occurs in file2 at index j. */
+ ssize_t best_j = -1;
+ double best_j_similarity = 0.0;
+ ssize_t jj;
+ for (jj = n2 - 1; jj >= 0; jj--)
+ if (mapping->index_mapping_reverse[jj] < 0)
+ {
+ double similarity =
+ entry_fstrcmp (entry_i, file2->entries[jj],
+ best_j_similarity);
+ if (similarity > best_j_similarity)
+ {
+ best_j = jj;
+ best_j_similarity = similarity;
+ }
+ }
+ if (best_j_similarity >= FSTRCMP_THRESHOLD && best_j == j)
+ {
+ mapping->index_mapping_reverse[j] = best_i;
+ mapping->index_mapping[best_i] = j;
+ }
+ }
+ if (mapping->index_mapping_reverse[j] < -1)
+ /* It does not approximately occur in FILE1.
+ Remember it, for next time. */
+ mapping->index_mapping_reverse[j] = -1;
+ }
+ return mapping->index_mapping_reverse[j];
+}
+
/* 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. */
+ of entries.
+ If FULL is true, the maximum of matching is done up-front. If it is false,
+ it is done in a lazy way through the functions entries_mapping_get and
+ entries_mapping_reverse_get.
+ Return the result in *RESULT. */
static void
compute_mapping (struct changelog_file *file1, struct changelog_file *file2,
- ssize_t *result[2])
+ bool full,
+ struct entries_mapping *result)
{
/* Mapping from indices in file1 to indices in file2. */
ssize_t *index_mapping;
index_mapping = XNMALLOC (n1, ssize_t);
for (i = 0; i < n1; i++)
- index_mapping[i] = -1;
+ index_mapping[i] = -2;
index_mapping_reverse = XNMALLOC (n2, ssize_t);
for (j = 0; j < n2; j++)
- index_mapping_reverse[j] = -1;
+ index_mapping_reverse[j] = -2;
for (i = n1 - 1; i >= 0; i--)
/* Take an entry from file1. */
- if (index_mapping[i] < 0)
+ if (index_mapping[i] < -1)
{
struct entry *entry = file1->entries[i];
/* Search whether it occurs in file2. */
{
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 (;;)
+ /* If index_mapping_reverse[j] >= 0, we have already seen other
+ copies of this entry, and there were more occurrences of it in
+ file1 than in file2. In this case, do nothing. */
+ if (index_mapping_reverse[j] < 0)
+ {
+ index_mapping[i] = j;
+ index_mapping_reverse[j] = i;
+ /* Look for more occurrences of the same entry. Match them
+ as long as they pair up. Unpaired occurrences of the same
+ entry are left without mapping. */
{
- 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;
- }
- }
- }
- }
+ ssize_t curr_i = i;
+ ssize_t curr_j = j;
- 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)
+ for (;;)
{
- best_i = i;
- best_i_similarity = similarity;
+ 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;
}
}
- 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;
+ result->file1 = file1;
+ result->file2 = file2;
+ result->index_mapping = index_mapping;
+ result->index_mapping_reverse = index_mapping_reverse;
+
+ if (full)
+ for (i = n1 - 1; i >= 0; i--)
+ entries_mapping_get (result, i);
}
/* An "edit" is a textual modification performed by the user, that needs to
new_body.string = new_entry->string + split_offset;
new_body.length = new_entry->length - split_offset;
- similarity = entry_fstrcmp (&old_body, &new_body);
+ similarity =
+ entry_fstrcmp (&old_body, &new_body, best_similarity);
if (similarity > best_similarity)
{
best_split_offset = split_offset;
if (best_similarity < FSTRCMP_STRICTER_THRESHOLD)
return false;
- new_split[0] = XMALLOC (struct entry);
- new_split[0]->string = new_entry->string;
- new_split[0]->length = best_split_offset + 1;
+ new_split[0] = entry_create (new_entry->string, best_split_offset + 1);
- new_split[1] = XMALLOC (struct entry);
{
size_t len1 = new_title_len;
size_t len2 = new_entry->length - best_split_offset;
char *combined = XNMALLOC (len1 + len2, char);
memcpy (combined, new_entry->string, len1);
memcpy (combined + len1, new_entry->string + best_split_offset, len2);
- new_split[1]->string = combined;
- new_split[1]->length = len1 + len2;
+ new_split[1] = entry_create (combined, len1 + len2);
}
return true;
/* Long options. */
static const struct option long_options[] =
-{
+{
{ "help", no_argument, NULL, 'h' },
{ "split-merged-entry", no_argument, NULL, CHAR_MAX + 1 },
{ "version", no_argument, NULL, 'V' },
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 entries_mapping mapping;
struct differences diffs;
gl_list_node_t *result_entries_pointers; /* array of pointers into result_entries */
gl_list_t /* <struct entry *> */ result_entries;
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 pull --rebase",
- it is set to 'pull --rebase'.
+ it is set to 'pull --rebase'. During a "git cherry-pick", it is
+ set to 'cherry-pick'.
- During a "git stash apply", there is an environment variable of
the form GITHEAD_<40_hex_digits>='Stashed changes'. */
{
downstream = true;
else
{
- /* "git stash apply", "git rebase" and similar. */
+ /* "git stash apply", "git rebase", "git cherry-pick" and
+ similar. */
downstream = false;
}
}
/* 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_mapping (&ancestor_file, &mainstream_file, false, &mapping);
+ (void) entries_mapping_reverse_get; /* avoid gcc "defined but not" warning */
/* Compute differences between the entries of ancestor_file and of
modified_file. */
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_before = entries_mapping_get (&mapping, i_before);
k_after = (i_after == ancestor_file.num_entries
? mainstream_file.num_entries
- : index_mapping[i_after]);
+ : entries_mapping_get (&mapping, i_after));
if (k_before >= 0 && k_after >= 0 && k_after == k_before + 1)
{
/* Yes, the entry before and after are still neighbours
for (i = edit->i1; i <= edit->i2; i++)
{
struct entry *removed_entry = ancestor_file.entries[i];
- ssize_t k = index_mapping[i];
+ ssize_t k = entries_mapping_get (&mapping, i);
if (k >= 0
&& entry_equals (removed_entry,
mainstream_file.entries[k]))
size_t i;
for (i = edit->i1 + 1; i <= edit->i2; i++)
if (entry_fstrcmp (ancestor_file.entries[i],
- modified_file.entries[i + edit->j2 - edit->i2])
+ modified_file.entries[i + edit->j2 - edit->i2],
+ FSTRCMP_THRESHOLD)
< FSTRCMP_THRESHOLD)
{
simple_merged = false;
? split[1]
: modified_file.entries[j]);
size_t i = j + edit->i2 - edit->j2;
- ssize_t k = index_mapping[i];
+ ssize_t k = entries_mapping_get (&mapping, i);
if (k >= 0
&& entry_equals (ancestor_file.entries[i],
mainstream_file.entries[k]))
result_entries_pointers[k],
changed_entry);
}
- else
+ else if (!entry_equals (ancestor_file.entries[i],
+ changed_entry))
{
struct conflict *c = XMALLOC (struct conflict);
c->num_old_entries = 1;
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])
+ modified_file.entries[i + edit->j2 - edit->i2],
+ FSTRCMP_THRESHOLD)
< FSTRCMP_THRESHOLD)
{
simple = false;
{
struct entry *changed_entry = modified_file.entries[j];
size_t i = j + edit->i2 - edit->j2;
- ssize_t k = index_mapping[i];
+ ssize_t k = entries_mapping_get (&mapping, i);
if (k >= 0
&& entry_equals (ancestor_file.entries[i],
mainstream_file.entries[k]))
}
else
{
- struct conflict *c = XMALLOC (struct conflict);
+ struct conflict *c;
+ ASSERT (!entry_equals (ancestor_file.entries[i],
+ changed_entry));
+ c = XMALLOC (struct conflict);
c->num_old_entries = 1;
c->old_entries =
XNMALLOC (c->num_old_entries, struct entry *);
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];
+ k_before = entries_mapping_get (&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))
+ if (entries_mapping_get (&mapping, i) != k_before + (i - i_before))
{
linear = false;
break;
{
struct entry *changed_entry = modified_file.entries[j];
size_t i = j + edit->i2 - edit->j2;
- ssize_t k = index_mapping[i];
+ ssize_t k = entries_mapping_get (&mapping, i);
ASSERT (k >= 0);
if (entry_equals (ancestor_file.entries[i],
mainstream_file.entries[k]))
}
else
{
- struct conflict *c = XMALLOC (struct conflict);
+ struct conflict *c;
+ ASSERT (!entry_equals (ancestor_file.entries[i],
+ changed_entry));
+ c = XMALLOC (struct conflict);
c->num_old_entries = 1;
c->old_entries =
XNMALLOC (c->num_old_entries, struct entry *);
ssize_t k_first;
bool linear_unchanged;
i_first = edit->i1;
- k_first = index_mapping[i_first];
+ k_first = entries_mapping_get (&mapping, i_first);
linear_unchanged =
(k_first >= 0
&& entry_equals (ancestor_file.entries[i_first],
{
size_t i;
for (i = i_first + 1; i <= edit->i2; i++)
- if (!(index_mapping[i] == k_first + (i - i_first)
+ if (!(entries_mapping_get (&mapping, i) == k_first + (i - i_first)
&& entry_equals (ancestor_file.entries[i],
- mainstream_file.entries[index_mapping[i]])))
+ mainstream_file.entries[entries_mapping_get (&mapping, i)])))
{
linear_unchanged = false;
break;
}
for (i = edit->i1; i <= edit->i2; i++)
{
- ssize_t k = index_mapping[i];
+ ssize_t k = entries_mapping_get (&mapping, i);
ASSERT (k >= 0);
ASSERT (entry_equals (ancestor_file.entries[i],
mainstream_file.entries[k]));
for (i = 0; i < n; i++)
conflict_write (fp, (struct conflict *) gl_list_get_at (result_conflicts, i));
}
+ /* Output the modified and unmodified entries, in order. */
{
- 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));
+ gl_list_iterator_t iter = gl_list_iterator (result_entries);
+ const void *elt;
+ gl_list_node_t node;
+ while (gl_list_iterator_next (&iter, &elt, &node))
+ entry_write (fp, (struct entry *) elt);
+ gl_list_iterator_free (&iter);
}
if (fwriteerror (fp))
projects / gnulib.git / blobdiff