Speed up approximate search for matching ChangeLog entries.

[pspp] / lib / git-merge-changelog.c

diff --git a/lib/git-merge-changelog.c b/lib/git-merge-changelog.c
index 5f639eff0d8a54ae474ad58b4d01a9dbf6f84f0f..986b8c832dc9c0c0898c3bad3ac14c0d1e8f6eca 100644 (file)
--- a/lib/git-merge-changelog.c
+++ b/lib/git-merge-changelog.c
@@ -21,7 +21,7 @@
    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
@@ -186,7 +186,7 @@ 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
@@ -211,9 +211,12 @@ entry_hashcode (const void *elt)
 
 /* 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;
@@ -233,7 +236,8 @@ entry_fstrcmp (const struct entry *entry1, const struct entry *entry2)
     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;
 }
@@ -410,7 +414,8 @@ compute_mapping (struct changelog_file *file1, struct changelog_file *file2,
        for (j = n2 - 1; j >= 0; j--)
          if (index_mapping_reverse[j] < 0)
            {
-             double similarity = entry_fstrcmp (entry_i, file2->entries[j]);
+             double similarity =
+               entry_fstrcmp (entry_i, file2->entries[j], best_j_similarity);
              if (similarity > best_j_similarity)
                {
                  best_j = j;
@@ -429,7 +434,8 @@ compute_mapping (struct changelog_file *file1, struct changelog_file *file2,
              if (index_mapping[ii] < 0)
                {
                  double similarity =
-                   entry_fstrcmp (file1->entries[ii], entry_j);
+                   entry_fstrcmp (file1->entries[ii], entry_j,
+                                  best_i_similarity);
                  if (similarity > best_i_similarity)
                    {
                      best_i = i;
@@ -729,7 +735,8 @@ try_split_merged_entry (const struct entry *old_entry,
 
       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;
@@ -808,7 +815,7 @@ conflict_write (FILE *fp, struct conflict *c)
 
 /* 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' },
@@ -975,7 +982,8 @@ There is NO WARRANTY, to the extent permitted by law.\n\
        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'.  */
     {
@@ -1002,7 +1010,8 @@ There is NO WARRANTY, to the extent permitted by law.\n\
                downstream = true;
              else
                {
-                 /* "git stash apply", "git rebase" and similar.  */
+                 /* "git stash apply", "git rebase", "git cherry-pick" and
+                    similar.  */
                  downstream = false;
                }
            }
@@ -1217,7 +1226,8 @@ There is NO WARRANTY, to the extent permitted by law.\n\
                            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;
@@ -1257,7 +1267,8 @@ There is NO WARRANTY, to the extent permitted by law.\n\
                                                            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;
@@ -1297,7 +1308,8 @@ There is NO WARRANTY, to the extent permitted by law.\n\
                        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;
@@ -1337,7 +1349,10 @@ There is NO WARRANTY, to the extent permitted by law.\n\
                                  }
                                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 *);
@@ -1399,7 +1414,10 @@ There is NO WARRANTY, to the extent permitted by law.\n\
                                      }
                                    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 *);
@@ -1505,11 +1523,14 @@ There is NO WARRANTY, to the extent permitted by law.\n\
        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))