From: Michael Platings <mich...@platin.gs>

---
 blame.c                | 352 +++++++++++++++++++++++++++++++++++++++++++++++--
 blame.h                |   1 +
 builtin/blame.c        |   3 +
 t/t8020-blame-fuzzy.sh | 264 +++++++++++++++++++++++++++++++++++++
 4 files changed, 609 insertions(+), 11 deletions(-)
 create mode 100755 t/t8020-blame-fuzzy.sh

diff --git a/blame.c b/blame.c
index 5c07dec190..b5a40c8e9f 100644
--- a/blame.c
+++ b/blame.c
@@ -997,6 +997,326 @@ static void pass_blame_to_parent(struct blame_scoreboard 
*sb,
        return;
 }
 
+/* https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel */
+static int bitcount(uint32_t v) {
+       v = v - ((v >> 1) & 0x55555555u);
+       v = (v & 0x33333333u) + ((v >> 2) & 0x33333333u);
+       return ((v + (v >> 4) & 0xf0f0f0fu) * 0x1010101u) >> 24;
+}
+
+#define FINGERPRINT_LENGTH (8*256)
+/* This is just a bitset indicating which byte pairs are present.
+ e.g. the string "good goo" has pairs "go", "oo", "od", "d ", " g"
+ String similarity is calculated as a bitwise or and counting the set bits.
+ TODO for the string lengths we typically deal with, this would probably be
+ implemented more efficiently with a set data structure.
+ */
+struct fingerprint {
+       uint32_t bits[FINGERPRINT_LENGTH];
+};
+
+static void get_fingerprint(struct fingerprint *result,
+                           const char *line_begin, const char *line_end) {
+       memset(result, 0, sizeof(struct fingerprint));
+       for (const char *p = line_begin; p + 1 < line_end; ++p) {
+               unsigned c = tolower(*p) | (tolower(*(p + 1)) << 8);
+               result->bits[c >> 5] |= 1u << (c & 0x1f);
+       }
+}
+
+static int fingerprint_similarity(const struct fingerprint *a,
+                                 const struct fingerprint *b) {
+       int intersection = 0;
+       for (int i = 0; i < FINGERPRINT_LENGTH; ++i) {
+               intersection += bitcount(a->bits[i] & b->bits[i]);
+       }
+       return intersection;
+}
+
+struct fuzzy_blame_parent_data {
+       struct blame_origin *parent;
+       long offset;
+       struct blame_entry **processed_entries;
+       struct blame_entry **target_entries;
+       const char *parent_content;
+       const char *target_content;
+       int *parent_line_starts;
+       int *target_line_starts;
+       int parent_line_count;
+       int target_line_count;
+};
+
+static void get_chunk_fingerprints(struct fingerprint *fingerprints,
+                                  const char *content,
+                                  const int *line_starts,
+                                  long chunk_start,
+                                  long chunk_length) {
+       line_starts += chunk_start;
+       for (int i = 0; i != chunk_length; ++i) {
+               const char* linestart = content + line_starts[i];
+               const char* lineend = content + line_starts[i + 1];
+               get_fingerprint(fingerprints + i, linestart, lineend);
+       }
+}
+
+/* This finds the line that we can match with the most confidence, and
+ uses it as a partition. It then calls itself on the lines on either side of
+ that partition. In this way we avoid lines appearing out of order, and retain
+ a sensible line ordering.
+ TODO: so much optimisation. Currently this does the same work repeatedly.
+ */
+static void fuzzy_find_matching_lines_recurse(
+               const char *content_a, const char *content_b,
+               const int *line_starts_a, const int *line_starts_b,
+               int start_a, int start_b,
+               int length_a, int length_b,
+               int *result,
+               struct fingerprint *fingerprints_a,
+               struct fingerprint *fingerprints_b) {
+
+       int most_certain_line = -1;
+       int most_certain_line_certainty = -1;
+
+       for (int i = 0; i < length_b; ++i) {
+               const struct fingerprint *fingerprint_b = fingerprints_b + i;
+
+               int closest_line_a = (i * 2 + 1) * length_a /
+               (length_b * 2);
+
+               /* Limit range of search to a reasonable number of lines.
+                TODO consider scaling this up if length_a is greater than
+                length_b. */
+               const int MAX_SEARCH_DISTANCE = 5;
+               int search_start = closest_line_a - (MAX_SEARCH_DISTANCE - 1);
+               int search_end = closest_line_a + MAX_SEARCH_DISTANCE;
+               if (search_start < 0) search_start = 0;
+               if (search_end > length_a) search_end = length_a;
+
+               /* Find both the best and 2nd best matches. The match certainty
+                is the difference between these values. */
+               int best_similarity = 0, second_best_similarity = 0;
+               int best_similarity_index = 0;
+
+               for (int j = search_start; j < search_end; ++j) {
+                       int similarity = fingerprint_similarity(
+                                                               fingerprint_b,
+                                                               fingerprints_a 
+ j) *
+                               (1000 - abs(j - closest_line_a));
+
+                       if (similarity > best_similarity) {
+                               second_best_similarity = best_similarity;
+                               best_similarity = similarity;
+                               best_similarity_index = j;
+                       }
+                       else if (similarity > second_best_similarity) {
+                               second_best_similarity = similarity;
+                       }
+               }
+
+               if (best_similarity == 0) {
+                       result[i] = -1;
+                       continue;
+               }
+
+               result[i] = start_a + best_similarity_index;
+
+               int certainty = best_similarity - second_best_similarity;
+               if (certainty > most_certain_line_certainty) {
+                       most_certain_line_certainty = certainty;
+                       most_certain_line = i;
+               }
+       }
+
+       if (most_certain_line == -1) {
+               return;
+       }
+
+       if (most_certain_line > 0) {
+               fuzzy_find_matching_lines_recurse(content_a, content_b, 
line_starts_a, line_starts_b, start_a, start_b, result[most_certain_line] + 1 - 
start_a, most_certain_line, result, fingerprints_a, fingerprints_b);
+       }
+       if (most_certain_line + 1 < length_b) {
+               int second_half_start_a = result[most_certain_line];
+               int second_half_start_b = start_b + most_certain_line + 1;
+               int second_half_length_a = length_a + start_a - 
second_half_start_a;
+               int second_half_length_b = length_b + start_b - 
second_half_start_b;
+               fuzzy_find_matching_lines_recurse(content_a, content_b, 
line_starts_a, line_starts_b, second_half_start_a, second_half_start_b, 
second_half_length_a, second_half_length_b, result + most_certain_line + 1, 
fingerprints_a + second_half_start_a - start_a, fingerprints_b + 
most_certain_line + 1);
+       }
+}
+
+/* Find line numbers in "a" that match with lines in "b"
+ Returns an array of either line indices or -1 where no match is found.
+ The returned array must be free()d after use.
+ */
+static int *fuzzy_find_matching_lines(
+       const char *content_a, const char *content_b,
+       const int *line_starts_a, const int *line_starts_b,
+       int start_a, int start_b,
+       int length_a, int length_b) {
+
+       int *result = malloc(sizeof(int) * length_b);
+
+       struct fingerprint *fingerprints_a =
+               malloc(sizeof(struct fingerprint) * length_a);
+       struct fingerprint *fingerprints_b =
+               malloc(sizeof(struct fingerprint) * length_b);
+
+       get_chunk_fingerprints(fingerprints_a, content_a,
+                              line_starts_a,
+                              start_a, length_a);
+       get_chunk_fingerprints(fingerprints_b, content_b,
+                              line_starts_b,
+                              start_b, length_b);
+
+       fuzzy_find_matching_lines_recurse(content_a, content_b,
+                                           line_starts_a, line_starts_b,
+                                           start_a, start_b,
+                                           length_a, length_b,
+                                           result,
+                                           fingerprints_a,
+                                           fingerprints_b);
+
+       free(fingerprints_a);
+       free(fingerprints_b);
+
+       return result;
+}
+
+static int blame_chunk_fuzzy(long parent_chunk_start,
+                                 long parent_chunk_length,
+                                 long target_chunk_start,
+                                 long target_chunk_length,
+                                 void *data)
+{
+       struct fuzzy_blame_parent_data *d = data;
+
+       if (parent_chunk_start - target_chunk_start != d->offset)
+               die("internal error in blame::blame_chunk_fuzzy");
+
+       int target_chunk_end = target_chunk_start + target_chunk_length;
+
+       struct blame_origin *parent = d->parent;
+       struct blame_entry *e = *d->target_entries;
+       struct blame_entry *parent_tail = NULL;
+       struct blame_entry *target_tail = NULL;
+
+       if (parent_chunk_length == 0) {
+               /* Don't try to blame parent for newly added lines */
+               while (e && e->s_lno < target_chunk_end) {
+                       target_tail = e;
+                       e = e->next;
+               }
+               d->target_entries = &target_tail->next;
+               goto finish;
+       }
+
+       int *matched_lines = fuzzy_find_matching_lines(
+               d->parent_content, d->target_content,
+               d->parent_line_starts, d->target_line_starts,
+               parent_chunk_start, target_chunk_start,
+               parent_chunk_length, target_chunk_length);
+
+       while (e && e->s_lno < target_chunk_end) {
+               struct blame_entry *next = e->next;
+
+               for (int i = 0; i < e->num_lines; ++i) {
+                       struct blame_entry *n =
+                               xcalloc(1, sizeof (struct blame_entry));
+                       n->lno = e->lno + i;
+                       n->num_lines = 1;
+                       n->score = 0;
+
+                       int matched_line = matched_lines[i + e->s_lno -
+                               target_chunk_start];
+
+                       if (matched_line != -1) {
+                               n->suspect = blame_origin_incref(parent);
+                               n->s_lno = matched_line;
+                               n->next = parent_tail;
+                               parent_tail = n;
+                       } else {
+                               n->suspect = blame_origin_incref(e->suspect);
+                               n->s_lno = e->s_lno + i;
+                               n->next = target_tail;
+                               target_tail = n;
+                       }
+               }
+
+               blame_origin_decref(e->suspect);
+               free(e);
+
+               e = next;
+       }
+
+       if (parent_tail) {
+               parent_tail = llist_mergesort(parent_tail, get_next_blame,
+                                             set_next_blame,
+                                             compare_blame_suspect);
+               *d->processed_entries = parent_tail;
+               while (parent_tail->next) parent_tail = parent_tail->next;
+               d->processed_entries = &parent_tail->next;
+       }
+
+       if (target_tail) {
+               target_tail = llist_mergesort(target_tail, get_next_blame,
+                                             set_next_blame,
+                                             compare_blame_suspect);
+               *d->target_entries = target_tail;
+               while (target_tail->next) target_tail = target_tail->next;
+               d->target_entries = &target_tail->next;
+       }
+
+       *d->target_entries = e;
+
+       free(matched_lines);
+
+finish:
+       d->offset = parent_chunk_start + parent_chunk_length -
+               (target_chunk_start + target_chunk_length);
+
+       return 0;
+}
+
+static int find_line_starts(int **line_starts, const char *buf, unsigned long 
len);
+
+static void pass_blame_to_parent_fuzzy(struct blame_scoreboard *sb,
+                                      struct blame_origin *target,
+                                      struct blame_origin *parent)
+{
+       mmfile_t file_p, file_o;
+       struct fuzzy_blame_parent_data d;
+       struct blame_entry *newdest = NULL;
+
+       if (!target->suspects)
+               return; /* nothing remains for this target */
+
+       d.parent = parent;
+       d.offset = 0;
+       d.processed_entries = &newdest;
+       d.target_entries = &target->suspects;
+
+       fill_origin_blob(&sb->revs->diffopt, parent, &file_p, 
&sb->num_read_blob);
+       fill_origin_blob(&sb->revs->diffopt, target, &file_o, 
&sb->num_read_blob);
+       sb->num_get_patch++;
+
+       d.parent_content = file_p.ptr;
+       d.target_content = file_o.ptr;
+       d.parent_line_count = find_line_starts(&d.parent_line_starts, 
file_p.ptr, file_p.size);
+       d.target_line_count = find_line_starts(&d.target_line_starts, 
file_o.ptr, file_o.size);
+
+       if (diff_hunks(&file_p, &file_o, blame_chunk_fuzzy, &d, sb->xdl_opts))
+               die("unable to generate diff (%s -> %s)",
+                       oid_to_hex(&parent->commit->object.oid),
+                       oid_to_hex(&target->commit->object.oid));
+
+       *d.processed_entries = NULL;
+       queue_blames(sb, parent, newdest);
+
+       free(d.target_line_starts);
+       free(d.parent_line_starts);
+
+       return;
+}
+
 /*
  * The lines in blame_entry after splitting blames many times can become
  * very small and trivial, and at some point it becomes pointless to
@@ -1433,7 +1753,7 @@ static void pass_blame(struct blame_scoreboard *sb, 
struct blame_origin *origin,
        struct commit *commit = origin->commit;
        struct commit_list *sg;
        struct blame_origin *sg_buf[MAXSG];
-       struct blame_origin *porigin, **sg_origin = sg_buf;
+       struct blame_origin *porigin = NULL, **sg_origin = sg_buf;
        struct blame_entry *toosmall = NULL;
        struct blame_entry *blames, **blametail = &blames;
 
@@ -1560,6 +1880,11 @@ static void pass_blame(struct blame_scoreboard *sb, 
struct blame_origin *origin,
                *tail = origin->suspects;
                origin->suspects = toosmall;
        }
+
+       if (sb->fuzzy && porigin) {
+               pass_blame_to_parent_fuzzy(sb, origin, porigin);
+       }
+
        for (i = 0; i < num_sg; i++) {
                if (sg_origin[i]) {
                        drop_origin_blob(sg_origin[i]);
@@ -1645,14 +1970,8 @@ static const char *get_next_line(const char *start, 
const char *end)
        return nl ? nl + 1 : end;
 }
 
-/*
- * To allow quick access to the contents of nth line in the
- * final image, prepare an index in the scoreboard.
- */
-static int prepare_lines(struct blame_scoreboard *sb)
+static int find_line_starts(int **line_starts, const char *buf, unsigned long 
len)
 {
-       const char *buf = sb->final_buf;
-       unsigned long len = sb->final_buf_size;
        const char *end = buf + len;
        const char *p;
        int *lineno;
@@ -1661,15 +1980,26 @@ static int prepare_lines(struct blame_scoreboard *sb)
        for (p = buf; p < end; p = get_next_line(p, end))
                num++;
 
-       ALLOC_ARRAY(sb->lineno, num + 1);
-       lineno = sb->lineno;
+       ALLOC_ARRAY(*line_starts, num + 1);
+       lineno = *line_starts;
 
        for (p = buf; p < end; p = get_next_line(p, end))
                *lineno++ = p - buf;
 
        *lineno = len;
 
-       sb->num_lines = num;
+       return num;
+}
+
+/*
+ * To allow quick access to the contents of nth line in the
+ * final image, prepare an index in the scoreboard.
+ */
+static int prepare_lines(struct blame_scoreboard *sb)
+{
+       sb->num_lines = find_line_starts(&sb->lineno,
+                                                                        
sb->final_buf,
+                                                                        
sb->final_buf_size);
        return sb->num_lines;
 }
 
diff --git a/blame.h b/blame.h
index be3a895043..eb528f9f80 100644
--- a/blame.h
+++ b/blame.h
@@ -142,6 +142,7 @@ struct blame_scoreboard {
        int xdl_opts;
        int no_whole_file_rename;
        int debug;
+       int fuzzy;
 
        /* callbacks */
        void(*on_sanity_fail)(struct blame_scoreboard *, int);
diff --git a/builtin/blame.c b/builtin/blame.c
index 177c1022a0..d0a0dfff79 100644
--- a/builtin/blame.c
+++ b/builtin/blame.c
@@ -57,6 +57,7 @@ static struct date_mode blame_date_mode = { DATE_ISO8601 };
 static size_t blame_date_width;
 
 static struct string_list mailmap = STRING_LIST_INIT_NODUP;
+static int fuzzy;
 
 #ifndef DEBUG
 #define DEBUG 0
@@ -808,6 +809,7 @@ int cmd_blame(int argc, const char **argv, const char 
*prefix)
                OPT_BIT('w', NULL, &xdl_opts, N_("Ignore whitespace 
differences"), XDF_IGNORE_WHITESPACE),
                OPT_BIT(0, "color-lines", &output_option, N_("color redundant 
metadata from previous line differently"), OUTPUT_COLOR_LINE),
                OPT_BIT(0, "color-by-age", &output_option, N_("color lines by 
age"), OUTPUT_SHOW_AGE_WITH_COLOR),
+               OPT_BOOL('F', "fuzzy", &fuzzy, N_("Try to assign blame to 
similar lines in the parent")),
 
                /*
                 * The following two options are parsed by parse_revision_opt()
@@ -996,6 +998,7 @@ int cmd_blame(int argc, const char **argv, const char 
*prefix)
 
        init_scoreboard(&sb);
        sb.revs = &revs;
+       sb.fuzzy = fuzzy;
        sb.contents_from = contents_from;
        sb.reverse = reverse;
        sb.repo = the_repository;
diff --git a/t/t8020-blame-fuzzy.sh b/t/t8020-blame-fuzzy.sh
new file mode 100755
index 0000000000..d26c945722
--- /dev/null
+++ b/t/t8020-blame-fuzzy.sh
@@ -0,0 +1,264 @@
+#!/bin/sh
+
+test_description='git blame ignore a specific revision'
+. ./test-lib.sh
+
+pick_author='s/^[0-9a-f^]* *(\([^ ]*\) .*/\1/'
+
+file_count=8
+
+# Each test is composed of 4 variables:
+# titleN - the test name
+# aN - the initial content
+# bN - the final content
+# expectedN - the line numbers from aN that we expect git blame
+#             on bN to identify, or "Final" if bN itself should
+#             be identified as the origin of that line.
+
+title1="Expand lines"
+cat <<EOF >a1
+aaa
+bbb
+ccc
+ddd
+eee
+EOF
+cat <<EOF >b1
+aaa
+bbbx
+bbbx
+ccc
+dddx
+dddx
+eee
+EOF
+cat <<EOF >expected1
+1
+2
+2
+3
+4
+4
+5
+EOF
+
+title2="Combine 3 lines into 2"
+cat <<EOF >a2
+if ((maxgrow==0) ||
+    ( single_line_field && (field->dcols < maxgrow)) ||
+    (!single_line_field && (field->drows < maxgrow)))
+EOF
+cat <<EOF >b2
+if ((maxgrow == 0) || (single_line_field && (field->dcols < maxgrow)) ||
+    (!single_line_field && (field->drows < maxgrow))) {
+EOF
+cat <<EOF >expected2
+2
+3
+EOF
+
+title3="Add curly brackets"
+cat <<EOF >a3
+    if (rows) *rows = field->rows;
+    if (cols) *cols = field->cols;
+    if (frow) *frow = field->frow;
+    if (fcol) *fcol = field->fcol;
+EOF
+cat <<EOF >b3
+    if (rows) {
+      *rows = field->rows;
+    }
+    if (cols) {
+      *cols = field->cols;
+    }
+    if (frow) {
+      *frow = field->frow;
+    }
+    if (fcol) {
+      *fcol = field->fcol;
+    }
+EOF
+cat <<EOF >expected3
+1
+1
+Final
+2
+2
+Final
+3
+3
+Final
+4
+4
+Final
+EOF
+
+
+title4="Combine many lines and change case"
+cat <<EOF >a4
+for(row=0,pBuffer=field->buf;
+    row<height;
+    row++,pBuffer+=width )
+  {
+    if ((len = (int)( After_End_Of_Data( pBuffer, width ) - pBuffer )) > 0)
+      {
+        wmove( win, row, 0 );
+        waddnstr( win, pBuffer, len );
+EOF
+cat <<EOF >b4
+for (Row = 0, PBuffer = field->buf; Row < Height; Row++, PBuffer += Width) {
+  if ((Len = (int)(afterEndOfData(PBuffer, Width) - PBuffer)) > 0) {
+    wmove(win, Row, 0);
+    waddnstr(win, PBuffer, Len);
+EOF
+cat <<EOF >expected4
+1
+5
+7
+8
+EOF
+
+title5="Rename and combine lines"
+cat <<EOF >a5
+bool need_visual_update = ((form != (FORM *)0)      &&
+                           (form->status & _POSTED) &&
+                           (form->current==field));
+
+if (need_visual_update)
+  Synchronize_Buffer(form);
+
+if (single_line_field)
+  {
+    growth = field->cols * amount;
+    if (field->maxgrow)
+      growth = Minimum(field->maxgrow - field->dcols,growth);
+    field->dcols += growth;
+    if (field->dcols == field->maxgrow)
+EOF
+cat <<EOF >b5
+bool NeedVisualUpdate = ((Form != (FORM *)0) && (Form->status & _POSTED) &&
+                         (Form->current == field));
+
+if (NeedVisualUpdate) {
+  synchronizeBuffer(Form);
+}
+
+if (SingleLineField) {
+  Growth = field->cols * amount;
+  if (field->maxgrow) {
+    Growth = Minimum(field->maxgrow - field->dcols, Growth);
+  }
+  field->dcols += Growth;
+  if (field->dcols == field->maxgrow) {
+EOF
+cat <<EOF >expected5
+1
+3
+4
+5
+6
+Final
+7
+8
+10
+11
+12
+Final
+13
+14
+EOF
+
+# Both lines match identically so position must be used to tie-break.
+title6="Same line twice"
+cat <<EOF >a6
+abc
+abc
+EOF
+cat <<EOF >b6
+abcd
+abcd
+EOF
+cat <<EOF >expected6
+1
+2
+EOF
+
+title7="Enforce line order"
+cat <<EOF >a7
+abcdef
+ghijkl
+ab
+EOF
+cat <<EOF >b7
+ghijk
+abcd
+EOF
+cat <<EOF >expected7
+2
+3
+EOF
+
+title8="Expand lines and rename variables"
+cat <<EOF >a8
+int myFunction(int ArgumentOne, Thing *ArgTwo, Blah XuglyBug) {
+  Squiggle FabulousResult = squargle(ArgumentOne, *ArgTwo,
+    XuglyBug) + EwwwGlobalWithAReallyLongNameYepTooLong;
+  return FabulousResult * 42;
+}
+EOF
+cat <<EOF >b8
+int myFunction(int argument_one, Thing *arg_asdfgh,
+    Blah xugly_bug) {
+  Squiggle fabulous_result = squargle(argument_one,
+    *arg_asdfgh, xugly_bug)
+    + g_ewww_global_with_a_really_long_name_yep_too_long;
+  return fabulous_result * 42;
+}
+EOF
+cat <<EOF >expected8
+1
+1
+2
+3
+3
+4
+5
+EOF
+
+test_expect_success setup '
+       { for ((i=1;i<=$file_count;i++))
+       do
+               # Append each line in a separate commit to make it easy to
+               # check which original line the blame output relates to.
+
+               line_count=0 &&
+               { while read line
+               do
+                       line_count=$((line_count+1)) &&
+                       echo $line >>"$i" &&
+                       git add "$i" &&
+                       test_tick &&
+                       GIT_AUTHOR_NAME="$line_count" git commit -m 
"$line_count"
+               done } <"a$i"
+       done } &&
+
+       { for ((i=1;i<=$file_count;i++))
+       do
+               # Overwrite the files with the final content.
+               cp b$i $i &&
+               git add $i &&
+               test_tick
+       done } &&
+
+       # Commit the final content all at once so it can all be
+       # referred to with the same commit ID.
+       GIT_AUTHOR_NAME=Final git commit -m Final
+'
+
+for ((i=1;i<=$file_count;i++)); do
+       title="title$i"
+       test_expect_success "${!title}" \
+       "git blame --fuzzy -- $i | sed -e \"$pick_author\" >actual && test_cmp 
expected$i actual"
+done
+
+test_done
-- 
2.14.3 (Apple Git-98)

Reply via email to