{"thread":{"id":"50891","subject":"RE: [PATCH v5 6/6] RFC blame: use a fingerprint heuristic to match ignored lines","startedAt":"2019-04-07T21:47:05Z","lastAt":"2019-04-09T19:10:53Z","messageCount":7,"participants":["michael@platin.gs","David Kastrup","Michael Platings","Barret Rhoden","Junio C Hamano"],"isPatch":true,"patchVersion":5,"patchTotal":6},"messages":[{"id":"373371","messageId":"20190407214635.12984-1-michael@platin.gs","threadId":"50891","inReplyTo":null,"subject":"RE: [PATCH v5 6/6] RFC blame: use a fingerprint heuristic to match ignored lines","fromName":"","fromEmail":"michael@platin.gs","sentAt":"2019-04-07T21:46:35Z","receivedAt":"2019-04-07T21:47:05Z","isPatch":true,"sender":{"key":"michael@platin.gs","avatar":"https://avatars.githubusercontent.com/u/1112348?v=4"},"body":"From: Michael Platings <michael@platin.gs>\n\nHi Barret,\nThis is the updated fuzzy matching algorithm, sorry for the delay. It does\nhighlight a bug in the calculation for the number of lines (\"int nr_parent_lines\n = e->num_lines - delta;\") - if you apply the patch, build it, then try to\n./git blame --ignore-rev <the patch commit ID> blame.c then you'll get a segfault\nbecause nr_parent_lines is a negative number. I haven't had time to investigate further\nbut I have confirmed that the bug is not due to my patch.\n\nThe matching algorithm might not be obvious so it could do with more commenting.\nIn the mean time I hope the tests will make the intent clear. In particular I\nwant to avoid lines being reordered, because for the interesting use cases\nusually sequences are unchanged even if they shift across different lines.\n\nRegarding the existing implementation I've got to say I find it unhelpful\nmarking \"unblameable\" lines with a 000000 commit ID. That commit ID already has\na meaning - lines that aren't yet committed. Further, the purpose of ignoring\ncommits should be to avoid obscuring other useful information, not to absolutely\nrefuse to show that commit at all. If there's no other commit to show then it's\nharmless to show the commit that would otherwise be ignored.\n\n- How about matching *outside* the parent's diff hunk?\nI'd like to know what the use case would be for that. For the use case of\nlooking \"through\" a reformatting or renaming commit I think it would be unhelpful.\n\n- Fix up this commit + message.  I'd be up for splitting it more,\nparticularly if Michael wants his contributions/fingerprinting in his\nown commit.\nThanks, maybe once we've got things into a robust state.\n\n-Michael\n---\n Makefile                           |   1 +\n blame.c                            |  16 +-\n fuzzy.c                            | 346 +++++++++++++++++++++++++++++\n fuzzy.h                            |  18 ++\n t/t8014-blame-ignore-revs-fuzzy.sh | 333 +++++++++++++++++++++++++++\n 5 files changed, 712 insertions(+), 2 deletions(-)\n create mode 100644 fuzzy.c\n create mode 100644 fuzzy.h\n create mode 100755 t/t8014-blame-ignore-revs-fuzzy.sh\n\ndiff --git a/Makefile b/Makefile\nindex 3e03290d8f..4725060c54 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -893,6 +893,7 @@ LIB_OBJS += fetch-object.o\n LIB_OBJS += fetch-pack.o\n LIB_OBJS += fsck.o\n LIB_OBJS += fsmonitor.o\n+LIB_OBJS += fuzzy.o\n LIB_OBJS += gettext.o\n LIB_OBJS += gpg-interface.o\n LIB_OBJS += graph.o\ndiff --git a/blame.c b/blame.c\nindex d20c13e6f8..0a7c231102 100644\n--- a/blame.c\n+++ b/blame.c\n@@ -9,6 +9,7 @@\n #include \"blame.h\"\n #include \"alloc.h\"\n #include \"commit-slab.h\"\n+#include \"fuzzy.h\"\n \n define_commit_slab(blame_suspects, struct blame_origin *);\n static struct blame_suspects blame_suspects;\n@@ -928,15 +929,26 @@ static void guess_line_blames(struct blame_entry *e,\n {\n \tint nr_parent_lines = e->num_lines - delta;\n \n+\tint *matching_lines = fuzzy_find_matching_lines(parent->file.ptr,\n+\t\t\t\t\t\t\ttarget->file.ptr,\n+\t\t\t\t\t\t\tparent->line_starts,\n+\t\t\t\t\t\t\ttarget->line_starts,\n+\t\t\t\t\t\t\te->s_lno + offset,\n+\t\t\t\t\t\t\te->s_lno,\n+\t\t\t\t\t\t\tnr_parent_lines,\n+\t\t\t\t\t\t\te->num_lines);\n+\n \tfor (int i = 0; i < e->num_lines; i++) {\n-\t\tif (i < nr_parent_lines) {\n+\t\tif (matching_lines[i] >= 0) {\n \t\t\tline_blames[i].is_parent = 1;\n-\t\t\tline_blames[i].s_lno = e->s_lno + i + offset;\n+\t\t\tline_blames[i].s_lno = matching_lines[i];\n \t\t} else {\n \t\t\tline_blames[i].is_parent = 0;\n \t\t\tline_blames[i].s_lno = e->s_lno + i;\n \t\t}\n \t}\n+\n+\tfree(matching_lines);\n }\n \n /*\ndiff --git a/fuzzy.c b/fuzzy.c\nnew file mode 100644\nindex 0000000000..b5ecb921b2\n--- /dev/null\n+++ b/fuzzy.c\n@@ -0,0 +1,346 @@\n+#include \"fuzzy.h\"\n+#include <ctype.h>\n+#include <stdint.h>\n+#include <stdlib.h>\n+#include <string.h>\n+#include \"git-compat-util.h\"\n+#include \"hashmap.h\"\n+\n+struct fingerprint {\n+\tstruct hashmap map;\n+\tstruct hashmap_entry *entries;\n+};\n+\n+static void get_fingerprint(struct fingerprint *result,\n+\t\t\t    const char *line_begin,\n+\t\t\t    const char *line_end) {\n+\tunsigned hash;\n+\tchar c0, c1;\n+\tint map_entry_count = line_end - line_begin - 1;\n+\tstruct hashmap_entry *entry = malloc(map_entry_count *\n+\t\t\t\t\t     sizeof(struct hashmap_entry));\n+\thashmap_init(&result->map, NULL, NULL, map_entry_count);\n+\tresult->entries = entry;\n+\tfor (const char *p = line_begin; p + 1 < line_end; ++p, ++entry) {\n+\t\tc0 = *p;\n+\t\tc1 = *(p + 1);\n+\t\t/* Ignore whitespace pairs */\n+\t\tif (isspace(c0) && isspace(c1))\n+\t\t\tcontinue;\n+\t\thash = tolower(c0) | (tolower(c1) << 8);\n+\t\thashmap_entry_init(entry, hash);\n+\t\thashmap_put(&result->map, entry);\n+\t}\n+}\n+\n+static void free_fingerprint(struct fingerprint *f) {\n+\thashmap_free(&f->map, 0);\n+\tfree(f->entries);\n+}\n+\n+static int fingerprint_similarity(struct fingerprint *a,\n+\t\t\t\t  struct fingerprint *b) {\n+\tint intersection = 0;\n+\tstruct hashmap_iter iter;\n+\tstruct hashmap_entry *entry;\n+\thashmap_iter_init(&b->map, &iter);\n+\n+\twhile ((entry = hashmap_iter_next(&iter))) {\n+\t\tif (hashmap_get(&a->map, entry, NULL)) {\n+\t\t\t++intersection;\n+\t\t}\n+\t}\n+\treturn intersection;\n+}\n+\n+static void get_line_fingerprints(struct fingerprint *fingerprints,\n+\t\t\t\t  const char *content,\n+\t\t\t\t  const int *line_starts,\n+\t\t\t\t  long chunk_start,\n+\t\t\t\t  long chunk_length) {\n+\tint i;\n+\tconst char *linestart, *lineend;\n+\tline_starts += chunk_start;\n+\tfor (i = 0; i != chunk_length; ++i) {\n+\t\tlinestart = content + line_starts[i];\n+\t\tlineend = content + line_starts[i + 1];\n+\t\tget_fingerprint(fingerprints + i, linestart, lineend);\n+\t}\n+}\n+\n+static int get_closest_line(int start_a,\n+\t\t\t    int chunk_line_b,\n+\t\t\t    int closest_line_calc_offset1,\n+\t\t\t    int closest_line_calc_offset2,\n+\t\t\t    int closest_line_calc_numerator,\n+\t\t\t    int closest_line_calc_denominator) {\n+\treturn ((chunk_line_b + closest_line_calc_offset1) * 2 + 1) *\n+\t\tclosest_line_calc_numerator /\n+\t\t(closest_line_calc_denominator * 2) +\n+\t\tclosest_line_calc_offset2 - start_a;\n+}\n+\n+#define CERTAIN_NOTHING_MATCHES -2\n+#define CERTAINTY_NOT_CALCULATED -1\n+\n+static void find_best_line_matches(const int max_search_distance,\n+\t\t\t\t   int start_a,\n+\t\t\t\t   int length_a,\n+\t\t\t\t   int chunk_line_b,\n+\t\t\t\t   const int *similarities,\n+\t\t\t\t   int *certainties,\n+\t\t\t\t   int *second_best_result,\n+\t\t\t\t   int *result,\n+\t\t\t\t   int closest_line_calc_offset1,\n+\t\t\t\t   int closest_line_calc_offset2,\n+\t\t\t\t   int closest_line_calc_numerator,\n+\t\t\t\t   int closest_line_calc_denominator) {\n+\n+\tint i, search_start, search_end, closest_line_a, similarity,\n+\t\tbest_similarity = 0, second_best_similarity = 0,\n+\t\tbest_similarity_index = 0, second_best_similarity_index = 0;\n+\n+\tif (certainties[chunk_line_b] != CERTAINTY_NOT_CALCULATED)\n+\t\treturn;\n+\n+\tclosest_line_a = get_closest_line(start_a,\n+\t\t\t\t\t  chunk_line_b,\n+\t\t\t\t\t  closest_line_calc_offset1,\n+\t\t\t\t\t  closest_line_calc_offset2,\n+\t\t\t\t\t  closest_line_calc_numerator,\n+\t\t\t\t\t  closest_line_calc_denominator);\n+\n+\tsearch_start = closest_line_a - max_search_distance;\n+\tif (search_start < 0)\n+\t\tsearch_start = 0;\n+\n+\tsearch_end = closest_line_a + max_search_distance + 1;\n+\tif (search_end > length_a)\n+\t\tsearch_end = length_a;\n+\n+\tfor (i = search_start; i < search_end; ++i) {\n+\t\tsimilarity = similarities[(i - closest_line_a) +\n+\t\t\tmax_search_distance +\n+\t\t\tchunk_line_b * (max_search_distance * 2 + 1)];\n+\t\tif (similarity > best_similarity) {\n+\t\t\tsecond_best_similarity = best_similarity;\n+\t\t\tsecond_best_similarity_index = best_similarity_index;\n+\t\t\tbest_similarity = similarity;\n+\t\t\tbest_similarity_index = i;\n+\t\t}\n+\t\telse if (similarity > second_best_similarity) {\n+\t\t\tsecond_best_similarity = similarity;\n+\t\t\tsecond_best_similarity_index = i;\n+\t\t}\n+\t}\n+\n+\tif (best_similarity == 0) {\n+\t\tcertainties[chunk_line_b] = CERTAIN_NOTHING_MATCHES;\n+\t\tresult[chunk_line_b] = -1;\n+\t}\n+\telse {\n+\t\tcertainties[chunk_line_b] = best_similarity * 2 -\n+\t\t\tsecond_best_similarity;\n+\t\tresult[chunk_line_b] = start_a + best_similarity_index;\n+\t\tsecond_best_result[chunk_line_b] =\n+\t\t\tstart_a + second_best_similarity_index;\n+\t}\n+}\n+\n+/*\n+ * This finds the line that we can match with the most confidence, and\n+ * uses it as a partition. It then calls itself on the lines on either side of\n+ * that partition. In this way we avoid lines appearing out of order, and\n+ * retain a sensible line ordering.\n+ */\n+static void fuzzy_find_matching_lines_recurse(\n+\tconst int max_search_distance,\n+\tint start_a, int start_b,\n+\tint length_a, int length_b,\n+\tconst int *similarities,\n+\tint *certainties,\n+\tint *second_best_result,\n+\tint *result,\n+\tint closest_line_calc_offset1,\n+\tint closest_line_calc_offset2,\n+\tint closest_line_calc_numerator,\n+\tint closest_line_calc_denominator) {\n+\n+\tint i, barrier, invalidate_extent, offset_b,\n+\t\tsecond_half_start_a, second_half_start_b,\n+\t\tsecond_half_length_a, second_half_length_b,\n+\t\tmost_certain_line = -1,\n+\t\tmost_certain_line_certainty = -1;\n+\n+\tfor (i = 0; i < length_b; ++i) {\n+\t\tfind_best_line_matches(max_search_distance,\n+\t\t\t\t       start_a,\n+\t\t\t\t       length_a,\n+\t\t\t\t       i,\n+\t\t\t\t       similarities,\n+\t\t\t\t       certainties,\n+\t\t\t\t       second_best_result,\n+\t\t\t\t       result,\n+\t\t\t\t       closest_line_calc_offset1,\n+\t\t\t\t       closest_line_calc_offset2,\n+\t\t\t\t       closest_line_calc_numerator,\n+\t\t\t\t       closest_line_calc_denominator);\n+\n+\t\tif (certainties[i] > most_certain_line_certainty) {\n+\t\t\tmost_certain_line_certainty = certainties[i];\n+\t\t\tmost_certain_line = i;\n+\t\t}\n+\t}\n+\n+\tif (most_certain_line == -1) {\n+\t\treturn;\n+\t}\n+\n+\t/* Invalidate results that may be affected by the choice of pivot. */\n+\tbarrier = result[most_certain_line];\n+\tinvalidate_extent = most_certain_line - max_search_distance;\n+\tif (invalidate_extent < 0)\n+\t\tinvalidate_extent = 0;\n+\tfor (i = most_certain_line - 1; i >= invalidate_extent; --i) {\n+\t\tif (certainties[i] >= 0 &&\n+\t\t    (result[i] > barrier || second_best_result[i] > barrier)) {\n+\t\t\t    certainties[i] = CERTAINTY_NOT_CALCULATED;\n+\t\t\t    barrier = result[i];\n+\t\t\t    invalidate_extent = i - max_search_distance;\n+\t\t\t    if (invalidate_extent < 0)\n+\t\t\t\t    invalidate_extent = 0;\n+\t\t    }\n+\t}\n+\n+\tbarrier = result[most_certain_line];\n+\tinvalidate_extent = most_certain_line + max_search_distance + 1;\n+\tif (invalidate_extent > length_b)\n+\t\tinvalidate_extent = length_b;\n+\tfor (i = most_certain_line + 1; i < invalidate_extent; ++i) {\n+\t\tif (certainties[i] >= 0 &&\n+\t\t    (result[i] < barrier || second_best_result[i] < barrier)) {\n+\t\t\t    certainties[i] = CERTAINTY_NOT_CALCULATED;\n+\t\t\t    barrier = result[i];\n+\t\t\t    invalidate_extent = i + max_search_distance + 1;\n+\t\t\t    if (invalidate_extent > length_b)\n+\t\t\t\t    invalidate_extent = length_b;\n+\t\t    }\n+\t}\n+\n+\tif (most_certain_line > 0) {\n+\t\tfuzzy_find_matching_lines_recurse(\n+\t\t\tmax_search_distance,\n+\t\t\tstart_a, start_b,\n+\t\t\tresult[most_certain_line] + 1 - start_a,\n+\t\t\tmost_certain_line, similarities,\n+\t\t\tcertainties, second_best_result, result,\n+\t\t\tclosest_line_calc_offset1, closest_line_calc_offset2,\n+\t\t\tclosest_line_calc_numerator,\n+\t\t\tclosest_line_calc_denominator);\n+\t}\n+\tif (most_certain_line + 1 < length_b) {\n+\t\tsecond_half_start_a = result[most_certain_line];\n+\t\toffset_b = most_certain_line + 1;\n+\t\tsecond_half_start_b = start_b + offset_b;\n+\t\tsecond_half_length_a =\n+\t\t\tlength_a + start_a - second_half_start_a;\n+\t\tsecond_half_length_b =\n+\t\t\tlength_b + start_b - second_half_start_b;\n+\t\tfuzzy_find_matching_lines_recurse(\n+\t\t\tmax_search_distance,\n+\t\t\tsecond_half_start_a, second_half_start_b,\n+\t\t\tsecond_half_length_a, second_half_length_b,\n+\t\t\tsimilarities +\n+\t\t\t\toffset_b * (max_search_distance * 2 + 1),\n+\t\t\tcertainties + offset_b,\n+\t\t\tsecond_best_result + offset_b, result + offset_b,\n+\t\t\tclosest_line_calc_offset1 + offset_b,\n+\t\t\tclosest_line_calc_offset2,\n+\t\t\tclosest_line_calc_numerator,\n+\t\t\tclosest_line_calc_denominator);\n+\t}\n+}\n+\n+int *fuzzy_find_matching_lines(const char *content_a,\n+\t\t\t       const char *content_b,\n+\t\t\t       const int *line_starts_a,\n+\t\t\t       const int *line_starts_b,\n+\t\t\t       int start_a,\n+\t\t\t       int start_b,\n+\t\t\t       int length_a,\n+\t\t\t       int length_b) {\n+\n+\tint i, j, closest_line_a, line_a, *result, *second_best_result,\n+\t\t*certainties, *similarities, *similarity;\n+\tstruct fingerprint *fingerprints_a, fingerprint_b;\n+\n+\tint max_search_distance = 10;\n+\tif (max_search_distance >= length_a)\n+\t\tmax_search_distance = length_a - 1;\n+\n+\tresult = malloc(sizeof(int) * length_b);\n+\tsecond_best_result = malloc(sizeof(int) * length_b);\n+\tcertainties = malloc(sizeof(int) * length_b);\n+\tsimilarities = malloc(sizeof(int) * length_b *\n+\t\t\t      (max_search_distance * 2 + 1));\n+\n+\tfor (i = 0; i < length_b; ++i) {\n+\t\tresult[i] = -1;\n+\t\tsecond_best_result[i] = -1;\n+\t\tcertainties[i] = CERTAINTY_NOT_CALCULATED;\n+\t}\n+\n+\tfingerprints_a = malloc(sizeof(struct fingerprint) * length_a);\n+\n+\tget_line_fingerprints(fingerprints_a, content_a,\n+\t\t\t      line_starts_a,\n+\t\t\t      start_a, length_a);\n+\n+\tfor (i = 0; i < length_b; ++i) {\n+\t\tget_fingerprint(&fingerprint_b,\n+\t\t\t\tcontent_b + line_starts_b[i + start_b],\n+\t\t\t\tcontent_b + line_starts_b[i + start_b + 1]);\n+\n+\t\tclosest_line_a = get_closest_line(start_a, i, 0, start_a,\n+\t\t\t\t\t\t  length_a, length_b);\n+\n+\t\tfor (j = -max_search_distance; j <= max_search_distance; ++j) {\n+\t\t\tsimilarity = similarities + j + max_search_distance +\n+\t\t\t\ti * (max_search_distance * 2 + 1);\n+\t\t\tline_a = closest_line_a + j;\n+\t\t\tif (line_a < 0 || line_a >= length_a) {\n+\t\t\t\t*similarity = -1;\n+\t\t\t}\n+\t\t\telse {\n+\t\t\t\t*similarity = fingerprint_similarity(\n+\t\t\t\t\t&fingerprint_b,\n+\t\t\t\t\tfingerprints_a + line_a) *\n+\t\t\t\t\t(1000 - abs(j));\n+\t\t\t}\n+\t\t}\n+\n+\t\tfree_fingerprint(&fingerprint_b);\n+\t}\n+\n+\tfor (i = 0; i < length_a; ++i) {\n+\t\tfree_fingerprint(fingerprints_a + i);\n+\t}\n+\n+\tfree(fingerprints_a);\n+\n+\tfuzzy_find_matching_lines_recurse(max_search_distance,\n+\t\t\t\t\t  start_a, start_b,\n+\t\t\t\t\t  length_a, length_b,\n+\t\t\t\t\t  similarities,\n+\t\t\t\t\t  certainties,\n+\t\t\t\t\t  second_best_result,\n+\t\t\t\t\t  result,\n+\t\t\t\t\t  0, start_a, length_a, length_b);\n+\n+\tfree(similarities);\n+\tfree(certainties);\n+\tfree(second_best_result);\n+\n+\treturn result;\n+}\n+\ndiff --git a/fuzzy.h b/fuzzy.h\nnew file mode 100644\nindex 0000000000..bd6d86ae45\n--- /dev/null\n+++ b/fuzzy.h\n@@ -0,0 +1,18 @@\n+#ifndef FUZZY_H\n+#define FUZZY_H\n+\n+/*\n+ * Find line numbers in \"a\" that match with lines in \"b\"\n+ * Returns an array of either line indices or -1 where no match is found.\n+ * The returned array must be free()d after use.\n+ */\n+int *fuzzy_find_matching_lines(const char *content_a,\n+\t\t\t       const char *content_b,\n+\t\t\t       const int *line_starts_a,\n+\t\t\t       const int *line_starts_b,\n+\t\t\t       int start_a,\n+\t\t\t       int start_b,\n+\t\t\t       int length_a,\n+\t\t\t       int length_b);\n+\n+#endif\ndiff --git a/t/t8014-blame-ignore-revs-fuzzy.sh b/t/t8014-blame-ignore-revs-fuzzy.sh\nnew file mode 100755\nindex 0000000000..1537a2b92c\n--- /dev/null\n+++ b/t/t8014-blame-ignore-revs-fuzzy.sh\n@@ -0,0 +1,333 @@\n+#!/bin/sh\n+\n+test_description='git blame ignore a specific revision'\n+. ./test-lib.sh\n+\n+pick_author='s/^[0-9a-f^]* *(\\([^ ]*\\) .*/\\1/'\n+\n+file_count=11\n+\n+# Each test is composed of 4 variables:\n+# titleN - the test name\n+# aN - the initial content\n+# bN - the final content\n+# expectedN - the line numbers from aN that we expect git blame\n+#             on bN to identify, or \"Final\" if bN itself should\n+#             be identified as the origin of that line.\n+\n+title1=\"Expand lines\"\n+cat <<EOF >a1\n+aaa\n+bbb\n+ccc\n+ddd\n+eee\n+EOF\n+cat <<EOF >b1\n+aaa\n+bbbx\n+bbbx\n+ccc\n+dddx\n+dddx\n+eee\n+EOF\n+cat <<EOF >expected1\n+1\n+2\n+2\n+3\n+4\n+4\n+5\n+EOF\n+\n+title2=\"Combine 3 lines into 2\"\n+cat <<EOF >a2\n+if ((maxgrow==0) ||\n+\t( single_line_field && (field->dcols < maxgrow)) ||\n+\t(!single_line_field && (field->drows < maxgrow)))\n+EOF\n+cat <<EOF >b2\n+if ((maxgrow == 0) || (single_line_field && (field->dcols < maxgrow)) ||\n+\t(!single_line_field && (field->drows < maxgrow))) {\n+EOF\n+cat <<EOF >expected2\n+2\n+3\n+EOF\n+\n+title3=\"Add curly brackets\"\n+cat <<EOF >a3\n+\tif (rows) *rows = field->rows;\n+\tif (cols) *cols = field->cols;\n+\tif (frow) *frow = field->frow;\n+\tif (fcol) *fcol = field->fcol;\n+EOF\n+cat <<EOF >b3\n+\tif (rows) {\n+\t\t*rows = field->rows;\n+\t}\n+\tif (cols) {\n+\t\t*cols = field->cols;\n+\t}\n+\tif (frow) {\n+\t\t*frow = field->frow;\n+\t}\n+\tif (fcol) {\n+\t\t*fcol = field->fcol;\n+\t}\n+EOF\n+cat <<EOF >expected3\n+1\n+1\n+Final\n+2\n+2\n+Final\n+3\n+3\n+Final\n+4\n+4\n+Final\n+EOF\n+\n+\n+title4=\"Combine many lines and change case\"\n+cat <<EOF >a4\n+for(row=0,pBuffer=field->buf;\n+\trow<height;\n+\trow++,pBuffer+=width )\n+{\n+\tif ((len = (int)( After_End_Of_Data( pBuffer, width ) - pBuffer )) > 0)\n+\t{\n+\t\twmove( win, row, 0 );\n+\t\twaddnstr( win, pBuffer, len );\n+EOF\n+cat <<EOF >b4\n+for (Row = 0, PBuffer = field->buf; Row < Height; Row++, PBuffer += Width) {\n+\tif ((Len = (int)(afterEndOfData(PBuffer, Width) - PBuffer)) > 0) {\n+\t\twmove(win, Row, 0);\n+\t\twaddnstr(win, PBuffer, Len);\n+EOF\n+cat <<EOF >expected4\n+1\n+5\n+7\n+8\n+EOF\n+\n+title5=\"Rename and combine lines\"\n+cat <<EOF >a5\n+bool need_visual_update = ((form != (FORM *)0)      &&\n+\t(form->status & _POSTED) &&\n+\t(form->current==field));\n+\n+if (need_visual_update)\n+\tSynchronize_Buffer(form);\n+\n+if (single_line_field)\n+{\n+\tgrowth = field->cols * amount;\n+\tif (field->maxgrow)\n+\t\tgrowth = Minimum(field->maxgrow - field->dcols,growth);\n+\tfield->dcols += growth;\n+\tif (field->dcols == field->maxgrow)\n+EOF\n+cat <<EOF >b5\n+bool NeedVisualUpdate = ((Form != (FORM *)0) && (Form->status & _POSTED) &&\n+\t(Form->current == field));\n+\n+if (NeedVisualUpdate) {\n+\tsynchronizeBuffer(Form);\n+}\n+\n+if (SingleLineField) {\n+\tGrowth = field->cols * amount;\n+\tif (field->maxgrow) {\n+\t\tGrowth = Minimum(field->maxgrow - field->dcols, Growth);\n+\t}\n+\tfield->dcols += Growth;\n+\tif (field->dcols == field->maxgrow) {\n+EOF\n+cat <<EOF >expected5\n+1\n+3\n+4\n+5\n+6\n+Final\n+7\n+8\n+10\n+11\n+12\n+Final\n+13\n+14\n+EOF\n+\n+# Both lines match identically so position must be used to tie-break.\n+title6=\"Same line twice\"\n+cat <<EOF >a6\n+abc\n+abc\n+EOF\n+cat <<EOF >b6\n+abcd\n+abcd\n+EOF\n+cat <<EOF >expected6\n+1\n+2\n+EOF\n+\n+title7=\"Enforce line order\"\n+cat <<EOF >a7\n+abcdef\n+ghijkl\n+ab\n+EOF\n+cat <<EOF >b7\n+ghijk\n+abcd\n+EOF\n+cat <<EOF >expected7\n+2\n+3\n+EOF\n+\n+title8=\"Expand lines and rename variables\"\n+cat <<EOF >a8\n+int myFunction(int ArgumentOne, Thing *ArgTwo, Blah XuglyBug) {\n+\tSquiggle FabulousResult = squargle(ArgumentOne, *ArgTwo,\n+\t\tXuglyBug) + EwwwGlobalWithAReallyLongNameYepTooLong;\n+\treturn FabulousResult * 42;\n+}\n+EOF\n+cat <<EOF >b8\n+int myFunction(int argument_one, Thing *arg_asdfgh,\n+\tBlah xugly_bug) {\n+\tSquiggle fabulous_result = squargle(argument_one,\n+\t\t*arg_asdfgh, xugly_bug)\n+\t\t+ g_ewww_global_with_a_really_long_name_yep_too_long;\n+\treturn fabulous_result * 42;\n+}\n+EOF\n+cat <<EOF >expected8\n+1\n+1\n+2\n+3\n+3\n+4\n+5\n+EOF\n+\n+title9=\"Two close matches versus one less close match\"\n+cat <<EOF >a9\n+abcdef\n+abcdef\n+ghijkl\n+EOF\n+cat <<EOF >b9\n+gh\n+abcdefx\n+EOF\n+cat <<EOF >expected9\n+Final\n+2\n+EOF\n+\n+# The first line of b matches best with the last line of a, but the overall\n+# match is better if we match it with the the first line of a.\n+title10=\"Piggy in the middle\"\n+cat <<EOF >a10\n+abcdefg\n+ijklmn\n+abcdefgh\n+EOF\n+cat <<EOF >b10\n+abcdefghx\n+ijklm\n+EOF\n+cat <<EOF >expected10\n+1\n+2\n+EOF\n+\n+title11=\"No trailing newline\"\n+printf \"abc\\ndef\" >a11\n+printf \"abx\\nstu\" >b11\n+cat <<EOF >expected11\n+1\n+Final\n+EOF\n+\n+test_expect_success setup '\n+\t{ for ((i=1;i<=$file_count;i++))\n+\tdo\n+\t\t# Append each line in a separate commit to make it easy to\n+\t\t# check which original line the blame output relates to.\n+\n+\t\tline_count=0 &&\n+\t\t{ while IFS= read line\n+\t\tdo\n+\t\t\tline_count=$((line_count+1)) &&\n+\t\t\techo \"$line\" >>\"$i\" &&\n+\t\t\tgit add \"$i\" &&\n+\t\t\ttest_tick &&\n+\t\t\tGIT_AUTHOR_NAME=\"$line_count\" git commit -m \"$line_count\"\n+\t\tdone } <\"a$i\"\n+\tdone } &&\n+\n+\t{ for ((i=1;i<=$file_count;i++))\n+\tdo\n+\t\t# Overwrite the files with the final content.\n+\t\tcp b$i $i &&\n+\t\tgit add $i\n+\tdone } &&\n+\ttest_tick &&\n+\n+\t# Commit the final content all at once so it can all be\n+\t# referred to with the same commit ID.\n+\tGIT_AUTHOR_NAME=Final git commit -m Final &&\n+\n+\tIGNOREME=$(git rev-parse HEAD)\n+'\n+\n+for ((i=1;i<=$file_count;i++)); do\n+\ttitle=\"title$i\"\n+\ttest_expect_success \"${!title}\" \\\n+\t\"git blame --ignore-rev $IGNOREME $i | sed -e \\\"$pick_author\\\" >actual && test_cmp expected$i actual\"\n+done\n+\n+# This invoked a null pointer dereference when the chunk callback was called\n+# with a zero length parent chunk and there were no more suspects.\n+test_expect_success 'Diff chunks with no suspects' '\n+\ttest_write_lines xy1 A B C xy1 >file &&\n+\tgit add file &&\n+\ttest_tick &&\n+\tGIT_AUTHOR_NAME=1 git commit -m 1 &&\n+\n+\ttest_write_lines xy2 A B xy2 C xy2 >file &&\n+\tgit add file &&\n+\ttest_tick &&\n+\tGIT_AUTHOR_NAME=2 git commit -m 2 &&\n+\tREV_2=$(git rev-parse HEAD) &&\n+\n+\ttest_write_lines xy3 A >file &&\n+\tgit add file &&\n+\ttest_tick &&\n+\tGIT_AUTHOR_NAME=3 git commit -m 3 &&\n+\tREV_3=$(git rev-parse HEAD) &&\n+\n+\ttest_write_lines 1 1 >expected &&\n+\n+\tgit blame --ignore-rev $REV_2 --ignore-rev $REV_3 file | sed -e \"$pick_author\" >actual &&\n+\n+\ttest_cmp expected actual\n+\t'\n+\n+test_done\n-- \n2.21.0\n\n"},{"id":"373372","messageId":"8736mtqy9n.fsf@fencepost.gnu.org","threadId":"50891","inReplyTo":"20190407214635.12984-1-michael@platin.gs","subject":"Re: [PATCH v5 6/6] RFC blame: use a fingerprint heuristic to match ignored lines","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2019-04-07T21:52:04Z","receivedAt":"2019-04-07T21:52:12Z","isPatch":true,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"michael@platin.gs writes:\n\n> From: Michael Platings <michael@platin.gs>\n>\n> Hi Barret,\n> This is the updated fuzzy matching algorithm, sorry for the delay. It does\n> highlight a bug in the calculation for the number of lines (\"int nr_parent_lines\n>  = e->num_lines - delta;\") - if you apply the patch, build it, then try to\n> ./git blame --ignore-rev <the patch commit ID> blame.c then you'll get a segfault\n> because nr_parent_lines is a negative number. I haven't had time to investigate further\n> but I have confirmed that the bug is not due to my patch.\n\nIf you segfault with the patch and don't segfault with the patch, there\nis not much of a point in declaring this \"somebody else's problem\", is\nthere?  It has to be fixed anyway in order to make the patch get in.\n\nOr am I fundamentally misunderstanding something here?\n\n-- \nDavid Kastrup\n"},{"id":"373406","messageId":"CAJDYR9TXL_9JpWvNv9ahK1aYV4isduHhvzvobCJ16q7LWhPRcA@mail.gmail.com","threadId":"50891","inReplyTo":"8736mtqy9n.fsf@fencepost.gnu.org","subject":"Re: [PATCH v5 6/6] RFC blame: use a fingerprint heuristic to match ignored lines","fromName":"Michael Platings","fromEmail":"michael@platin.gs","sentAt":"2019-04-08T09:48:23Z","receivedAt":"2019-04-08T09:48:38Z","isPatch":true,"sender":{"key":"michael@platin.gs","avatar":"https://avatars.githubusercontent.com/u/1112348?v=4"},"body":"Hi David,\nYou also get an out-of-memory error with the patch Barret posted at\nthe start of this thread.\nI'm sorry you interpreted my message as declaring it somebody else's\nproblem, that definitely wasn't my intent. I merely ran out of time to\ninvestigate further and I figure Barret is going to be interested in\nthis issue and would prefer that I let him know sooner rather than\nlater.\n-Michael\n(resending in plain text, sorry for the spam again)\n\nOn Sun, 7 Apr 2019 at 23:52, David Kastrup <dak@gnu.org> wrote:\n>\n> michael@platin.gs writes:\n>\n> > From: Michael Platings <michael@platin.gs>\n> >\n> > Hi Barret,\n> > This is the updated fuzzy matching algorithm, sorry for the delay. It does\n> > highlight a bug in the calculation for the number of lines (\"int nr_parent_lines\n> >  = e->num_lines - delta;\") - if you apply the patch, build it, then try to\n> > ./git blame --ignore-rev <the patch commit ID> blame.c then you'll get a segfault\n> > because nr_parent_lines is a negative number. I haven't had time to investigate further\n> > but I have confirmed that the bug is not due to my patch.\n>\n> If you segfault with the patch and don't segfault with the patch, there\n> is not much of a point in declaring this \"somebody else's problem\", is\n> there?  It has to be fixed anyway in order to make the patch get in.\n>\n> Or am I fundamentally misunderstanding something here?\n>\n> --\n> David Kastrup\n"},{"id":"373431","messageId":"6752a735-2e7b-7d13-799f-a42e6995498c@google.com","threadId":"50891","inReplyTo":"CAJDYR9TXL_9JpWvNv9ahK1aYV4isduHhvzvobCJ16q7LWhPRcA@mail.gmail.com","subject":"Re: [PATCH v5 6/6] RFC blame: use a fingerprint heuristic to match ignored lines","fromName":"Barret Rhoden","fromEmail":"brho@google.com","sentAt":"2019-04-08T16:03:29Z","receivedAt":"2019-04-08T16:03:35Z","isPatch":true,"sender":{"key":"brho@google.com","avatar":null},"body":"On 4/8/19 5:48 AM, Michael Platings wrote:\n> Hi David,\n> You also get an out-of-memory error with the patch Barret posted at\n> the start of this thread.\n\nI think I see the issue, and will fix it when I repost the patch set.\n\nBarret\n"},{"id":"373497","messageId":"xmqqftqr42a3.fsf@gitster-ct.c.googlers.com","threadId":"50891","inReplyTo":"6752a735-2e7b-7d13-799f-a42e6995498c@google.com","subject":"Re: [PATCH v5 6/6] RFC blame: use a fingerprint heuristic to match ignored lines","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2019-04-09T15:38:28Z","receivedAt":"2019-04-09T15:38:33Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Barret Rhoden <brho@google.com> writes:\n\n> On 4/8/19 5:48 AM, Michael Platings wrote:\n>> Hi David,\n>> You also get an out-of-memory error with the patch Barret posted at\n>> the start of this thread.\n>\n> I think I see the issue, and will fix it when I repost the patch set.\n\nThanks.\n"},{"id":"373500","messageId":"2747b3b2-0447-0d03-dc7e-c7fa460a303b@google.com","threadId":"50891","inReplyTo":"20190407214635.12984-1-michael@platin.gs","subject":"Re: [PATCH v5 6/6] RFC blame: use a fingerprint heuristic to match ignored lines","fromName":"Barret Rhoden","fromEmail":"brho@google.com","sentAt":"2019-04-09T15:56:55Z","receivedAt":"2019-04-09T15:57:02Z","isPatch":true,"sender":{"key":"brho@google.com","avatar":null},"body":"Hi -\n\nOn 4/7/19 5:46 PM, michael@platin.gs wrote:\n> From: Michael Platings <michael@platin.gs>\n> \n> Hi Barret,\n> This is the updated fuzzy matching algorithm, sorry for the delay. It does\n> highlight a bug in the calculation for the number of lines (\"int nr_parent_lines\n>   = e->num_lines - delta;\") - if you apply the patch, build it, then try to\n> ./git blame --ignore-rev <the patch commit ID> blame.c then you'll get a segfault\n> because nr_parent_lines is a negative number. I haven't had time to investigate further\n> but I have confirmed that the bug is not due to my patch.\n\nAlthough I couldn't recreate this, I saw how it could happen.  I have an \nupdated version that fixes it.  Short version: I just pass through \nparent_len instead of trying to recreate it with 'delta.'  Recreating \ncan go awry because e->num_lines may be less than a chunk size.\n\n> The matching algorithm might not be obvious so it could do with more commenting.\n> In the mean time I hope the tests will make the intent clear. In particular I\n> want to avoid lines being reordered, because for the interesting use cases\n> usually sequences are unchanged even if they shift across different lines.\n\nI thought you wanted to detect similarity across potentially reordered \nlines.  E.g.\n\ncommit a 10) #include <sys/a.h>\ncommit b 11) #include <foo/b.h>\ncommit c 12) #include <bar/c.h>\ncommit d 13) #include <dir/d.h>\n\nWhere commit X (to be ignored) alphabetized them (or something):\n\ncommit X 10) #include <bar/c.h>\ncommit X 11) #include <dir/d.h>\ncommit X 12) #include <foo/b.h>\ncommit X 13) #include <sys/a.h>\n\nIn this case, you want to find the line number in the parent that \ncorresponds to each line in the target (X is the target, in the relevant \nblame code).  The mapping is: (target -> parent)\n\n10 -> 12\n11 -> 13\n12 -> 11\n13 -> 10\n\nAnd the parent's line numbers are out of order.  But that's fine - at \nleast with the infrastructure from my patch, since it sorts the ignored \nqueue at the end of blame_chunk().  The rule in blame.c is that blame \nentries attached to a suspect need to be sorted by s_lno.  (At least \nbased on a comment, and my reading of the code).\n\nMaybe we have a different definition of reordering or are having \ndifferent issues regarding line numbers?  TBH, I didn't follow the \nrecursion and partitioning strategy too closely.\n\n> Regarding the existing implementation I've got to say I find it unhelpful\n> marking \"unblameable\" lines with a 000000 commit ID. That commit ID already has\n> a meaning - lines that aren't yet committed. Further, the purpose of ignoring\n> commits should be to avoid obscuring other useful information, not to absolutely\n> refuse to show that commit at all. If there's no other commit to show then it's\n> harmless to show the commit that would otherwise be ignored.\n\nFor me, if I tell git blame to not tell me about a commit, then I don't \nwant to hear about it.  My typical blame session involves running blame, \nthen digging up the commit it pointed to.  If it points to the commit I \nalready told it to not show, then it'll just annoy me.   All 0s made \nsense to me as in \"don't bother looking this up.\"\n\nIf you *did* want to see the ignored commit, then I'd run it with \n--ignore-revs-file=\"\", to disable ignore.\n\nThat being said, I realize this is a preference of mine, and I can make \na blame config option to control this.  Probably \nblame.maskIgnoredCommits or something.\n\n> - How about matching *outside* the parent's diff hunk?\n> I'd like to know what the use case would be for that. For the use case of\n> looking \"through\" a reformatting or renaming commit I think it would be unhelpful.\n\nI noticed that I have some commits where a hunk in a diff is broken up \ninto multiple calls to blame_chunk.  So a better way to prhase it would \nbe \"looking outside a blame_chunk()'s chunk.\"\n\nFor example, I have a hunk like this (modified to show the contiguous \nlines of context, subtraction, addition):\n\n@@ -256,99 +260,99 @@\n   3 context\n-83 subtract\n+23 addition\n   1 context\n- 2 sub\n+16 add\n   1 context\n- 5 sub\n+ 6 add\n   1 context\n+45 add\n   3 context\n\nblame_chunk() sees that as four separate calls, broken up by the lines \nof context:\n\n\tblame_chunk tlno 262 off -4 same 285 plen 83 enl 23\n\tblame_chunk tlno 286 off 56 same 302 plen 2 enl 16\n\tblame_chunk tlno 303 off 42 same 309 plen 5 enl 6\n\tblame_chunk tlno 310 off 41 same 355 plen 0 enl 45\n\nFor a lot of those lines, the source of the change was in another diff \nhunk - especially that 45 line addition with nothing from the parent.\n\nPart of the reason for that large diff is whitespace changes, so I can \nrun blame with -w.  But there are other scenarios.  Here's another one: \nthe header file alphabetizing case:\n\n@@ -4,9 +4,9 @@\n   3 context\n- 1 #include <header.h>\n   2 context (other headers)\n+ 1 #include <header.h>\n   3 context\n\nThat shows up as two blame chunks:\n\tblame_chunk tlno 6 off 0 same 6 plen 1 enl 0\n\tblame_chunk tlno 8 off 1 same 9 plen 0 enl 1\n\nWhat's funny about it is that if the commit we're ignoring did more \ndamage to the file (changed every line, for instance), it'd be easier to \nfind the right line in the parent, since we'd have the entire diff hunk.\n\nAnyway, being able to look outside the current blame_chunk would help in \nthose scenarios.  Specifically, I'm talking about letting blame_chunk() \npoint anywhere in the parent.  Right now, it can only look in the \nparent's part of the chunk passed to blame_chunk, which can be \nrelatively small.\n\nBarret\n\n"},{"id":"373528","messageId":"0e53bcba-e27c-228d-a36d-6d3575605d7a@google.com","threadId":"50891","inReplyTo":"2747b3b2-0447-0d03-dc7e-c7fa460a303b@google.com","subject":"Re: [PATCH v5 6/6] RFC blame: use a fingerprint heuristic to match ignored lines","fromName":"Barret Rhoden","fromEmail":"brho@google.com","sentAt":"2019-04-09T19:10:46Z","receivedAt":"2019-04-09T19:10:53Z","isPatch":true,"sender":{"key":"brho@google.com","avatar":null},"body":"On 4/9/19 11:56 AM, Barret Rhoden wrote:\n> Anyway, being able to look outside the current blame_chunk would help in \n> those scenarios.  Specifically, I'm talking about letting blame_chunk() \n> point anywhere in the parent.  Right now, it can only look in the \n> parent's part of the chunk passed to blame_chunk, which can be \n> relatively small.\n\nI hacked up the ability to look outside of a diff chunk.  The change to \nthe heuristic-independent part of the code was very minor, both in code \nand in performance.\n\nThe change to make the fingerprinting algorithm from my RFC patch look \nat the entire parent was pretty minor too - I can also cache the \nfingerprints.  The main drawback is performance, but Michael's new \nfingerprinting code alleviates this.\n\nHere's a quick analysis.  When run on a 1000 line C file, with large \nchanges from an ignored commit, after the file has been paged in (so, \nrun twice):\n\nnot ignoring at all:\n-------------\nreal\t0m0.062s\nuser\t0m0.042s\nsys\t0m0.021s\n\nscan only in the parent chunk:\n----------------------------\nreal\t0m0.097s\nuser\t0m0.085s\nsys\t0m0.012s\n\nscan parent chunk, scan entire parent on failure:\n-------------------------\nreal\t0m1.773s\nuser\t0m1.752s\nsys\t0m0.021s\n\nscan the entire parent:\n-----------------------\nreal\t0m3.049s\nuser\t0m3.024s\nsys\t0m0.024s\n\nScanning the parent chunk first helped a lot.  Scanning the entire \nparent is O(nr_parent_lines * nr_lines_changed).  In my test file, \nthat's about 1000 * 600.\n\nIt still takes a little while even when checking the parent chunk first. \n  Let's call that one the 'smaller scan.'\n\nCaching the fingerprints (meaning, calculate once and attach to the \nblame_origin) didn't help much here.  It's actually worse, possibly due \nto fingerprinting more than I needed to.\n\nsmaller scan, without caching:\n----------------\nreal\t0m1.651s\nuser\t0m1.626s\nsys\t0m0.025s\n\nsmaller scan, with caching:\n----------------\nreal\t0m1.774s\nuser\t0m1.753s\nsys\t0m0.021s\n\n\nLet's try Michael's new fingerprinting code (get_fingerprint() and \nfingerprint_similarity())\n\nsmaller scan, caching:\n-------------------\nreal\t0m0.240s\nuser\t0m0.215s\nsys\t0m0.025s\n\nsmaller scan, no caching:\n----------------------\nreal\t0m0.295s\nuser\t0m0.266s\nsys\t0m0.029s\n\nfull parent scan, caching:\n--------------------------\nreal\t0m0.377s\nuser\t0m0.356s\nsys\t0m0.021s\n\nfull parent scan, no caching:\n-----------------------------\nreal\t0m0.458s\nuser\t0m0.430s\nsys\t0m0.028s\n\nAnd for completenesss,\n\nscan only in the parent chunk:\n------------------------------\nreal\t0m0.072s\nuser\t0m0.048s\nsys\t0m0.024s\n\n\nSo first off, Michael's new fingerprinting is much better.  Caching the \nfingerprints also helps.  Overall, it's fast enough now that I don't \nnotice the delay.\n\nI'll reroll the patchset with the ability to find lines in the entire \nparent, and see what you all think.\n\nBarret\n\n\n\n"}]}