{"thread":{"id":"50971","subject":"RE: [PATCH v6 0/6] blame: add the ability to ignore commits","startedAt":"2019-04-22T22:28:25Z","lastAt":"2019-04-24T21:07:10Z","messageCount":6,"participants":["michael@platin.gs","Barret Rhoden"],"isPatch":true,"patchVersion":6,"patchTotal":6},"messages":[{"id":"374275","messageId":"20190422222647.48628-1-michael@platin.gs","threadId":"50971","inReplyTo":null,"subject":"RE: [PATCH v6 0/6] blame: add the ability to ignore commits","fromName":"","fromEmail":"michael@platin.gs","sentAt":"2019-04-22T22:26:47Z","receivedAt":"2019-04-22T22:28:25Z","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,\n\nThis patch is on top of your patch v6 4/6.\n\nPreviously I pointed out that my code couldn't handle this case correctly:\nBefore:\n\n        commit-a 11) Position MyClass::location(Offset O) {\n        commit-b 12)    return P + O;\n        commit-c 13) }\n\nAfter:\n\n        commit-a 11) Position MyClass::location(Offset offset) {\n        commit-a 12)    return position + offset;\n        commit-c 13) }\n\nWith this patch, line 12 is now correctly matched to commit-b even though it is\nmore similar to line 11.\n\nThe significant change here is that when a line is matched, its fingerprint is\nsubtracted from the matched parent line's fingerprint. This prevents two lines\nmatching the same part of a parent line.\n\nThis algorithm is now very good at matching lines *as long as line ordering is\nunchanged*. When matching lines in a single diff chunk it makes sense to assume\nthat lines are ordered because if they're not then there's a good chance the\ntrue match is outside the chunk. I'm very happy with how this algorithm behaves\nand I'm struggling to fault it for the refactoring & renaming use cases.\n\nTo address reordered lines I suggest a combination of this algorithm and your\nalgorithm - in the first path my algorithm tries to match lines within a\nsingle chunk, and in the second pass your algorithm tries to find matches for\nunblamed lines out of order and outside their chunk.\n\nIt would also be possible to adapt my algorithm to not assume that lines are\nordered, but I think that would make it O(n^2) whereas it's typically\nO(n log n) right now. But I could dig into that more if you prefer.\n\nThanks,\n-Michael\n---\n Makefile |   1 +\n blame.c  |  95 +++++++-----\n blame.h  |   2 +\n fuzzy.c  | 434 +++++++++++++++++++++++++++++++++++++++++++++++++++++++\n fuzzy.h  |  18 +++\n 5 files changed, 515 insertions(+), 35 deletions(-)\n create mode 100644 fuzzy.c\n create mode 100644 fuzzy.h\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 a98ae00e2c..43cdfcc259 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@@ -311,12 +312,42 @@ static int diff_hunks(mmfile_t *file_a, mmfile_t *file_b,\n \treturn xdi_diff(file_a, file_b, &xpp, &xecfg, &ecb);\n }\n \n+static const char *get_next_line(const char *start, const char *end)\n+{\n+\tconst char *nl = memchr(start, '\\n', end - start);\n+\n+\treturn nl ? nl + 1 : end;\n+}\n+\n+static int find_line_starts(int **line_starts, const char *buf,\n+\t\t\t    unsigned long len)\n+{\n+\tconst char *end = buf + len;\n+\tconst char *p;\n+\tint *lineno;\n+\tint num = 0;\n+\n+\tfor (p = buf; p < end; p = get_next_line(p, end))\n+\t\tnum++;\n+\n+\tALLOC_ARRAY(*line_starts, num + 1);\n+\tlineno = *line_starts;\n+\n+\tfor (p = buf; p < end; p = get_next_line(p, end))\n+\t\t*lineno++ = p - buf;\n+\n+\t*lineno = len;\n+\n+\treturn num;\n+}\n+\n /*\n  * Given an origin, prepare mmfile_t structure to be used by the\n  * diff machinery\n  */\n static void fill_origin_blob(struct diff_options *opt,\n-\t\t\t     struct blame_origin *o, mmfile_t *file, int *num_read_blob)\n+\t\t\t     struct blame_origin *o, mmfile_t *file,\n+\t\t\t     int *num_read_blob, int fill_line_starts)\n {\n \tif (!o->file.ptr) {\n \t\tenum object_type type;\n@@ -340,11 +371,16 @@ static void fill_origin_blob(struct diff_options *opt,\n \t}\n \telse\n \t\t*file = o->file;\n+\tif (fill_line_starts && !o->line_starts)\n+\t\to->num_lines = find_line_starts(&o->line_starts, o->file.ptr,\n+\t\t\t\t\t\to->file.size);\n }\n \n static void drop_origin_blob(struct blame_origin *o)\n {\n \tFREE_AND_NULL(o->file.ptr);\n+\tFREE_AND_NULL(o->line_starts);\n+\to->num_lines = 0;\n }\n \n /*\n@@ -891,19 +927,27 @@ static void guess_line_blames(struct blame_entry *e,\n \t\t\t      int offset, int parent_slno, int parent_len,\n \t\t\t      struct blame_line_tracker *line_blames)\n {\n-\tint i, parent_idx;\n+\tint i;\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\tparent_len,\n+\t\t\t\t\t\t\te->num_lines);\n \n \tfor (i = 0; i < e->num_lines; i++) {\n-\t\tparent_idx = e->s_lno + i + offset;\n-\t\tif (parent_slno <= parent_idx &&\n-\t\t    parent_idx < parent_slno + parent_len) {\n+\t\tif (matching_lines[i] >= 0) {\n \t\t\tline_blames[i].is_parent = 1;\n-\t\t\tline_blames[i].s_lno = parent_idx;\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 /*\n@@ -1136,8 +1180,10 @@ static void pass_blame_to_parent(struct blame_scoreboard *sb,\n \td.ignore_diffs = ignore_diffs;\n \td.dstq = &newdest; d.srcq = &target->suspects;\n \n-\tfill_origin_blob(&sb->revs->diffopt, parent, &file_p, &sb->num_read_blob);\n-\tfill_origin_blob(&sb->revs->diffopt, target, &file_o, &sb->num_read_blob);\n+\tfill_origin_blob(&sb->revs->diffopt, parent, &file_p,\n+\t\t\t &sb->num_read_blob, ignore_diffs);\n+\tfill_origin_blob(&sb->revs->diffopt, target, &file_o,\n+\t\t\t &sb->num_read_blob, ignore_diffs);\n \tsb->num_get_patch++;\n \n \tif (diff_hunks(&file_p, &file_o, blame_chunk_cb, &d, sb->xdl_opts))\n@@ -1348,7 +1394,8 @@ static void find_move_in_parent(struct blame_scoreboard *sb,\n \tif (!unblamed)\n \t\treturn; /* nothing remains for this target */\n \n-\tfill_origin_blob(&sb->revs->diffopt, parent, &file_p, &sb->num_read_blob);\n+\tfill_origin_blob(&sb->revs->diffopt, parent, &file_p,\n+\t\t\t &sb->num_read_blob, 0);\n \tif (!file_p.ptr)\n \t\treturn;\n \n@@ -1477,7 +1524,8 @@ static void find_copy_in_parent(struct blame_scoreboard *sb,\n \t\t\tnorigin = get_origin(parent, p->one->path);\n \t\t\toidcpy(&norigin->blob_oid, &p->one->oid);\n \t\t\tnorigin->mode = p->one->mode;\n-\t\t\tfill_origin_blob(&sb->revs->diffopt, norigin, &file_p, &sb->num_read_blob);\n+\t\t\tfill_origin_blob(&sb->revs->diffopt, norigin, &file_p,\n+\t\t\t\t\t &sb->num_read_blob, 0);\n \t\t\tif (!file_p.ptr)\n \t\t\t\tcontinue;\n \n@@ -1816,37 +1864,14 @@ void assign_blame(struct blame_scoreboard *sb, int opt)\n \t}\n }\n \n-static const char *get_next_line(const char *start, const char *end)\n-{\n-\tconst char *nl = memchr(start, '\\n', end - start);\n-\treturn nl ? nl + 1 : end;\n-}\n-\n /*\n  * To allow quick access to the contents of nth line in the\n  * final image, prepare an index in the scoreboard.\n  */\n static int prepare_lines(struct blame_scoreboard *sb)\n {\n-\tconst char *buf = sb->final_buf;\n-\tunsigned long len = sb->final_buf_size;\n-\tconst char *end = buf + len;\n-\tconst char *p;\n-\tint *lineno;\n-\tint num = 0;\n-\n-\tfor (p = buf; p < end; p = get_next_line(p, end))\n-\t\tnum++;\n-\n-\tALLOC_ARRAY(sb->lineno, num + 1);\n-\tlineno = sb->lineno;\n-\n-\tfor (p = buf; p < end; p = get_next_line(p, end))\n-\t\t*lineno++ = p - buf;\n-\n-\t*lineno = len;\n-\n-\tsb->num_lines = num;\n+\tsb->num_lines = find_line_starts(&sb->lineno, sb->final_buf,\n+\t\t\t\t\t sb->final_buf_size);\n \treturn sb->num_lines;\n }\n \ndiff --git a/blame.h b/blame.h\nindex 53df8b4c5b..f7755920c9 100644\n--- a/blame.h\n+++ b/blame.h\n@@ -51,6 +51,8 @@ struct blame_origin {\n \t */\n \tstruct blame_entry *suspects;\n \tmmfile_t file;\n+\tint num_lines;\n+\tint *line_starts;\n \tstruct object_id blob_oid;\n \tunsigned mode;\n \t/* guilty gets set when shipping any suspects to the final\ndiff --git a/fuzzy.c b/fuzzy.c\nnew file mode 100644\nindex 0000000000..c5b09a0eb7\n--- /dev/null\n+++ b/fuzzy.c\n@@ -0,0 +1,434 @@\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_entry {\n+\tstruct hashmap_entry entry;\n+\tint count;\n+};\n+struct fingerprint {\n+\tstruct hashmap map;\n+\tstruct fingerprint_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 fingerprint_entry *entry = xcalloc(map_entry_count,\n+\t\tsizeof(struct fingerprint_entry));\n+\tstruct fingerprint_entry *found_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+\n+\t\tif ((found_entry = hashmap_get(&result->map, entry, NULL))) {\n+\t\t\tfound_entry->count += 1;\n+\t\t}\n+\t\telse {\n+\t\t\tentry->count = 1;\n+\t\t\thashmap_add(&result->map, entry);\n+\t\t}\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+\tconst struct fingerprint_entry *entry_a, *entry_b;\n+\thashmap_iter_init(&b->map, &iter);\n+\n+\twhile ((entry_b = hashmap_iter_next(&iter))) {\n+\t\tif ((entry_a = hashmap_get(&a->map, entry_b, NULL))) {\n+\t\t\tintersection += entry_a->count < entry_b->count ?\n+\t\t\t\t\tentry_a->count : entry_b->count;\n+\t\t}\n+\t}\n+\treturn intersection;\n+}\n+\n+static void fingerprint_subtract(struct fingerprint *a,\n+\t\t\t\t struct fingerprint *b) {\n+\tstruct hashmap_iter iter;\n+\tstruct fingerprint_entry *entry_a;\n+\tconst struct fingerprint_entry *entry_b;\n+\thashmap_iter_init(&b->map, &iter);\n+\n+\twhile ((entry_b = hashmap_iter_next(&iter))) {\n+\t\tif ((entry_a = hashmap_get(&a->map, entry_b, NULL))) {\n+\t\t\tif (entry_a->count <= entry_b->count) {\n+\t\t\t\thashmap_remove(&a->map, entry_b, NULL);\n+\t\t\t}\n+\t\t\telse {\n+\t\t\t\tentry_a->count -= entry_b->count;\n+\t\t\t}\n+\t\t}\n+\t}\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_local_line(int start_a,\n+\t\t\t    int local_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 ((local_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+static int *get_similarity(int *similarities, int max_search_distance_a,\n+\t\t\t   int local_line_a, int local_line_b,\n+\t\t\t   int closest_local_line_a) {\n+\tassert(abs(local_line_a - closest_local_line_a) <= max_search_distance_a);\n+\treturn similarities + local_line_a - closest_local_line_a +\n+\t\tmax_search_distance_a +\n+\t\tlocal_line_b * (max_search_distance_a * 2 + 1);\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_a,\n+\t\t\t\t   int start_a,\n+\t\t\t\t   int length_a,\n+\t\t\t\t   int local_line_b,\n+\t\t\t\t   struct fingerprint *fingerprints_a,\n+\t\t\t\t   struct fingerprint *fingerprints_b,\n+\t\t\t\t   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_local_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[local_line_b] != CERTAINTY_NOT_CALCULATED)\n+\t\treturn;\n+\n+\tclosest_local_line_a = get_closest_local_line(start_a,\n+\t\t\t\t\t  local_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_local_line_a - max_search_distance_a;\n+\tif (search_start < 0)\n+\t\tsearch_start = 0;\n+\n+\tsearch_end = closest_local_line_a + max_search_distance_a + 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 = get_similarity(similarities, max_search_distance_a,\n+\t\t\t\t\t    i, local_line_b,\n+\t\t\t\t\t    closest_local_line_a);\n+\t\tif (*similarity == -1) {\n+\t\t\t*similarity = fingerprint_similarity(\n+\t\t\t\tfingerprints_b + local_line_b,\n+\t\t\t\tfingerprints_a + i) *\n+\t\t\t\t(1000 - abs(i - closest_local_line_a));\n+\t\t}\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[local_line_b] = CERTAIN_NOTHING_MATCHES;\n+\t\tresult[local_line_b] = -1;\n+\t}\n+\telse {\n+\t\tcertainties[local_line_b] = best_similarity * 2 -\n+\t\t\tsecond_best_similarity;\n+\t\tresult[local_line_b] = start_a + best_similarity_index;\n+\t\tsecond_best_result[local_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+\tint max_search_distance_a,\n+\tint max_search_distance_b,\n+\tint start_a, int start_b,\n+\tint length_a, int length_b,\n+\tstruct fingerprint *fingerprints_a,\n+\tstruct fingerprint *fingerprints_b,\n+\tint *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_min, invalidate_max, 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_a, most_certain_local_line_b = -1,\n+\t\tmost_certain_line_certainty = -1,\n+\t\tclosest_local_line_a;\n+\n+\tfor (i = 0; i < length_b; ++i) {\n+\t\tfind_best_line_matches(max_search_distance_a,\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       fingerprints_a,\n+\t\t\t\t       fingerprints_b,\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_local_line_b = i;\n+\t\t}\n+\t}\n+\n+\tif (most_certain_local_line_b == -1) {\n+\t\treturn;\n+\t}\n+\n+\tmost_certain_line_a = result[most_certain_local_line_b];\n+\n+\t/* Subtract the most certain line's fingerprint in b from the\n+\t matched fingerprint in a. This means that other lines in b can't also\n+\t match the same parts of the line in a. */\n+\tfingerprint_subtract(fingerprints_a + most_certain_line_a - start_a,\n+\t\t\t     fingerprints_b + most_certain_local_line_b);\n+\n+\n+\t/* Invalidate results that may be affected by the choice of pivot. */\n+\tinvalidate_min = most_certain_local_line_b - max_search_distance_b;\n+\tinvalidate_max = most_certain_local_line_b + max_search_distance_b + 1;\n+\tif (invalidate_min < 0)\n+\t\tinvalidate_min = 0;\n+\tif (invalidate_max > length_b)\n+\t\tinvalidate_max = length_b;\n+\n+\tfor (i = invalidate_min; i < invalidate_max; ++i) {\n+\t\tclosest_local_line_a = get_closest_local_line(\n+\t\t\tstart_a, i,\n+\t\t\tclosest_line_calc_offset1,\n+\t\t\tclosest_line_calc_offset2,\n+\t\t\tclosest_line_calc_numerator,\n+\t\t\tclosest_line_calc_denominator);\n+\t\t*get_similarity(similarities, max_search_distance_a,\n+\t\t\t\tmost_certain_line_a - start_a, i,\n+\t\t\t\tclosest_local_line_a) = -1;\n+\t}\n+\n+\tbarrier = most_certain_line_a;\n+\n+\tfor (i = most_certain_local_line_b - 1; i >= invalidate_min; --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_min = i - max_search_distance_b;\n+\t\t\t    if (invalidate_min < 0)\n+\t\t\t\t    invalidate_min = 0;\n+\t\t    }\n+\t}\n+\n+\tbarrier = most_certain_line_a;\n+\n+\tfor (i = most_certain_local_line_b + 1; i < invalidate_max; ++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_max = i + max_search_distance_b + 1;\n+\t\t\t    if (invalidate_max > length_b)\n+\t\t\t\t    invalidate_max = length_b;\n+\t\t    }\n+\t}\n+\n+\n+\tif (most_certain_local_line_b > 0) {\n+\t\tfuzzy_find_matching_lines_recurse(\n+\t\t\tmax_search_distance_a,\n+\t\t\tmax_search_distance_b,\n+\t\t\tstart_a, start_b,\n+\t\t\tmost_certain_line_a + 1 - start_a,\n+\t\t\tmost_certain_local_line_b,\n+\t\t\tfingerprints_a, fingerprints_b, 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_local_line_b + 1 < length_b) {\n+\t\tsecond_half_start_a = most_certain_line_a;\n+\t\toffset_b = most_certain_local_line_b + 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_a,\n+\t\t\tmax_search_distance_b,\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\tfingerprints_a + second_half_start_a - start_a,\n+\t\t\tfingerprints_b + offset_b,\n+\t\t\tsimilarities +\n+\t\t\t\toffset_b * (max_search_distance_a * 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, *result, *second_best_result,\n+\t\t*certainties, *similarities, similarity_count;\n+\tstruct fingerprint *fingerprints_a, *fingerprints_b;\n+\n+\t/* max_search_distance_a means that given a line in `b`, compare it to\n+\tthe line in `a` that is closest to its position, and the lines in `a`\n+\tthat are no greater than max_search_distance_a lines away from the\n+\tclosest line in `a`.\n+\tmax_search_distance_b is an upper bound on the greatest possible\n+\tdistance between lines in `b` such that they will both be compared with\n+\tthe same line in `a` according to max_search_distance_a. */\n+\tint max_search_distance_a = 10, max_search_distance_b;\n+\n+\tif (max_search_distance_a >= length_a)\n+\t\tmax_search_distance_a = length_a ? length_a - 1 : 0;\n+\n+\tif (length_a == 0) {\n+\t\tmax_search_distance_b = 0;\n+\t}\n+\telse {\n+\t\tmax_search_distance_b = ((2 * max_search_distance_a + 1) *\n+\t\t\tlength_b - 1) / length_a;\n+\t}\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+\tsimilarity_count = length_b * (max_search_distance_a * 2 + 1);\n+\tsimilarities = malloc(sizeof(int) * similarity_count);\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+\tfor (i = 0; i < similarity_count; ++i) {\n+\t\tsimilarities[i] = -1;\n+\t}\n+\n+\tfingerprints_a = xmalloc(sizeof(struct fingerprint) * length_a);\n+\tfingerprints_b = xmalloc(sizeof(struct fingerprint) * length_b);\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+\tget_line_fingerprints(fingerprints_b, content_b,\n+\t\t\t      line_starts_b,\n+\t\t\t      start_b, length_b);\n+\n+\tfuzzy_find_matching_lines_recurse(max_search_distance_a,\n+\t\t\t\t\t  max_search_distance_b,\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  fingerprints_a,\n+\t\t\t\t\t  fingerprints_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+\tfor (i = 0; i < length_b; ++i) {\n+\t\tfree_fingerprint(fingerprints_b + i);\n+\t}\n+\tfor (i = 0; i < length_a; ++i) {\n+\t\tfree_fingerprint(fingerprints_a + i);\n+\t}\n+\tfree(fingerprints_b);\n+\tfree(fingerprints_a);\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\n-- \n2.21.0\n\n"},{"id":"374317","messageId":"cc1466bc-0610-784b-e57b-8612c2e8569f@google.com","threadId":"50971","inReplyTo":"20190422222647.48628-1-michael@platin.gs","subject":"Re: [PATCH v6 0/6] blame: add the ability to ignore commits","fromName":"Barret Rhoden","fromEmail":"brho@google.com","sentAt":"2019-04-23T14:23:44Z","receivedAt":"2019-04-23T14:23:51Z","isPatch":true,"sender":{"key":"brho@google.com","avatar":null},"body":"On 4/22/19 6:26 PM, michael@platin.gs wrote:\n> From: Michael Platings <michael@platin.gs>\n> \n> Hi Barret,\n> \n> This patch is on top of your patch v6 4/6.\n\nThanks, I'll take a look.  I was working on taking your old version and \nintegrating it with my v6 6/6.  That way it gets the \norigin-fingerprint-filling code and can be easily compared to my 6/6 style.\n\n[snip]\n\n> \n> To address reordered lines I suggest a combination of this algorithm and your\n> algorithm - in the first path my algorithm tries to match lines within a\n> single chunk, and in the second pass your algorithm tries to find matches for\n> unblamed lines out of order and outside their chunk.\n\nI was thinking something similar.  Yesterday I did this with your older \npatch set - applied on my 6/6.  Two passes, one with your fuzzy matcher, \nthen if we didn't find anything, do a scan of the entire parent (as my \n6/6 does now).\n\nThis approached worked for the cases I had (e.g. \"header reordering\"). \nI ran into an issue last night where your scan was finding matches where \nit shouldn't - might have been an issue with how I hooked it up.  I'll \ntry your latest code and see how it goes.\n\nThanks,\n\nBarret\n\n"},{"id":"374322","messageId":"533f7721-2af6-1137-17c1-065837e1321d@google.com","threadId":"50971","inReplyTo":"20190422222647.48628-1-michael@platin.gs","subject":"Re: [PATCH v6 0/6] blame: add the ability to ignore commits","fromName":"Barret Rhoden","fromEmail":"brho@google.com","sentAt":"2019-04-23T18:13:05Z","receivedAt":"2019-04-23T18:13:11Z","isPatch":true,"sender":{"key":"brho@google.com","avatar":null},"body":"Hi Michael -\n\nOn 4/22/19 6:26 PM, michael@platin.gs wrote:\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\tparent_len,\n> +\t\t\t\t\t\t\te->num_lines);\n\nHere was the issue I ran into, and it's due to translations between \ne->s_lno and the parent's \"address space\".\n\nThe short version is that \"e->s_lno + offset\" is not always the \nparent_slno, and parent_len is based off of parent_slno.\n\nguess_line_blames() gives you parent_slno and parent_len, as well as \noffset.  'offset' is how you convert from the target's space to the \nparent's.  parent_slno and parent_len describe the whole chunk given to \nus from the diff engine.  However, there may be multiple blame_entries \ncovering that chunk.\n\nSo e->s_lno is in the target, but it's not necessarily the beginning of \nthe entire diff chunk.  This is related to that page fault you found a \nwhile back.\n\nPassing e->s_lno + offset for where fuzzy() starts looking in the parent \nis fine, but then the length in the parent needs to be adjusted.  For \ninstance, I have this at the top of my modified \nfuzzy_find_matching_lines() (changed to take the origins and variables \nfrom guess_line_blames()):\n\n         // XXX conversions to michael's variable names\n\tint start_a = e->s_lno + offset;\n         //int length_a = parent_len;    // XXX this fails the test\n         int length_a = (parent_slno + parent_len) - (e->s_lno + offset);\n\n\tint start_b = e->s_lno;\n         int length_b = e->num_lines;\n\nPlus we need a check for length_a <= 0.  I had to work to make it be \nnegative, but it's possible.  parent_slno = tlno + offset, so we're \nlooking at:\n\n\tlength_a = tlno + parent_len - e->s_lno;\n\nThat just requires a blame entry split such that e->s_lno > tlno, and a \nparent chunk that had 0 lines.  I found a case that did that.  Basically \nin one commit you add a bunch of lines.  In another, you change one line \nin the middle of that bunch.  That causes a split of the diff chunk into \nmore than one, such that e->s_lno > tlno.  That original commit only \nadded lines, so parent_len == 0.\n\nThe intuition for the \"negative length_a\" isn't that the parent_len is \nnegative, it's that the e->s_lno chunk (when offset) is outside the \nwindow of the parent's change.  I have a simple test for this.\n\nOh, and we have to length_a == 0, due to this:\n\n\tmax_search_distance = length_a - 1;\n\nAnyway, I'll take what I've got and apply your latest and see what I \ncome up with.  =)  Plus, I have fixes for all of the other stuff brought \nup in the v6 discussion.\n\nBarret\n\n"},{"id":"374329","messageId":"04385e9f-f0e1-240e-4473-df87076ae630@google.com","threadId":"50971","inReplyTo":"20190422222647.48628-1-michael@platin.gs","subject":"Re: [PATCH v6 0/6] blame: add the ability to ignore commits","fromName":"Barret Rhoden","fromEmail":"brho@google.com","sentAt":"2019-04-23T20:17:43Z","receivedAt":"2019-04-23T20:17:49Z","isPatch":true,"sender":{"key":"brho@google.com","avatar":null},"body":"Hi Michael -\n\nFYI, here are a few style nits that I changed in my version, based on a \nquick scan.  Not sure if these are all Git's style, but I think it's \nmostly linux-kernel style.\n\nI mention this mostly for future reference - specifically if we keep \nseparate versions of this code.  Hopefully we won't.  =)\n\nI also did all the fingerprint prep in fill_origin_blob, which you can \nsee in an upcoming patch.\n\nOn 4/22/19 6:26 PM, michael@platin.gs wrote:\n> diff --git a/fuzzy.c b/fuzzy.c\n> new file mode 100644\n> index 0000000000..c5b09a0eb7\n> --- /dev/null\n> +++ b/fuzzy.c\n> @@ -0,0 +1,434 @@\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_entry {\n> +\tstruct hashmap_entry entry;\n> +\tint count;\n> +};\n> +struct fingerprint {\n> +\tstruct hashmap map;\n> +\tstruct fingerprint_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                                                  ^newline here, so { is \nat the start of a line.  (on all of the functions)\n\n> +\tunsigned hash;\n                 ^int\n\n> +\tchar c0, c1;\n> +\tint map_entry_count = line_end - line_begin - 1;\n> +\tstruct fingerprint_entry *entry = xcalloc(map_entry_count,\n> +\t\tsizeof(struct fingerprint_entry));\n> +\tstruct fingerprint_entry *found_entry;\n\nBlank line here, between declarations and code.  Did this for all of the \nfunctions.\n\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              ^moved this declaration outside the for loop\n\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> +\n> +\t\tif ((found_entry = hashmap_get(&result->map, entry, NULL))) {\n                     ^moved this assignment outside the if ()\n> +\t\t\tfound_entry->count += 1;\n> +\t\t}\n> +\t\telse {\n                 ^ made this } else {.\n\nAlso in a couple other places below.\n\n> +\t\t\tentry->count = 1;\n> +\t\t\thashmap_add(&result->map, entry);\n> +\t\t}\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\nput fingerprint b on the same line as a (within 80 chars).  made similar \nchanges wherever that was possible and looked nice.\n\n> +\tint intersection = 0;\n> +\tstruct hashmap_iter iter;\n> +\tconst struct fingerprint_entry *entry_a, *entry_b;\n> +\thashmap_iter_init(&b->map, &iter);\n> +\n> +\twhile ((entry_b = hashmap_iter_next(&iter))) {\n> +\t\tif ((entry_a = hashmap_get(&a->map, entry_b, NULL))) {\n> +\t\t\tintersection += entry_a->count < entry_b->count ?\n> +\t\t\t\t\tentry_a->count : entry_b->count;\n> +\t\t}\n> +\t}\n> +\treturn intersection;\n> +}\n> +\n> +static void fingerprint_subtract(struct fingerprint *a,\n> +\t\t\t\t struct fingerprint *b) {\n> +\tstruct hashmap_iter iter;\n> +\tstruct fingerprint_entry *entry_a;\n> +\tconst struct fingerprint_entry *entry_b;\n> +\thashmap_iter_init(&b->map, &iter);\n> +\n> +\twhile ((entry_b = hashmap_iter_next(&iter))) {\n> +\t\tif ((entry_a = hashmap_get(&a->map, entry_b, NULL))) {\n> +\t\t\tif (entry_a->count <= entry_b->count) {\n> +\t\t\t\thashmap_remove(&a->map, entry_b, NULL);\n> +\t\t\t}\n> +\t\t\telse {\n> +\t\t\t\tentry_a->count -= entry_b->count;\n> +\t\t\t}\n> +\t\t}\n> +\t}\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                       ^ any reason for '!=' versus '<'  ?\n\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_local_line(int start_a,\n> +\t\t\t    int local_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 ((local_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                ^ i moved these three lines one space left, so that they \ndon't line up with the open paren.  o/w it looked like they may be \ninside the '('.\n\n\n> +}\n> +\n> +static int *get_similarity(int *similarities, int max_search_distance_a,\n> +\t\t\t   int local_line_a, int local_line_b,\n> +\t\t\t   int closest_local_line_a) {\n> +\tassert(abs(local_line_a - closest_local_line_a) <= max_search_distance_a);\n> +\treturn similarities + local_line_a - closest_local_line_a +\n> +\t\tmax_search_distance_a +\n> +\t\tlocal_line_b * (max_search_distance_a * 2 + 1);\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_a,\n> +\t\t\t\t   int start_a,\n> +\t\t\t\t   int length_a,\n> +\t\t\t\t   int local_line_b,\n> +\t\t\t\t   struct fingerprint *fingerprints_a,\n> +\t\t\t\t   struct fingerprint *fingerprints_b,\n> +\t\t\t\t   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                                    ^intense number of arguments.  =)\n\nNot sure if there's much to do about that.  It does make some of the \ncallsites busier.\n\n> +\n> +\tint i, search_start, search_end, closest_local_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[local_line_b] != CERTAINTY_NOT_CALCULATED)\n> +\t\treturn;\n> +\n> +\tclosest_local_line_a = get_closest_local_line(start_a,\n> +\t\t\t\t\t  local_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_local_line_a - max_search_distance_a;\n> +\tif (search_start < 0)\n> +\t\tsearch_start = 0;\n> +\n> +\tsearch_end = closest_local_line_a + max_search_distance_a + 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 = get_similarity(similarities, max_search_distance_a,\n> +\t\t\t\t\t    i, local_line_b,\n> +\t\t\t\t\t    closest_local_line_a);\n> +\t\tif (*similarity == -1) {\n> +\t\t\t*similarity = fingerprint_similarity(\n> +\t\t\t\tfingerprints_b + local_line_b,\n> +\t\t\t\tfingerprints_a + i) *\n> +\t\t\t\t(1000 - abs(i - closest_local_line_a));\n> +\t\t}\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[local_line_b] = CERTAIN_NOTHING_MATCHES;\n> +\t\tresult[local_line_b] = -1;\n> +\t}\n> +\telse {\n> +\t\tcertainties[local_line_b] = best_similarity * 2 -\n> +\t\t\tsecond_best_similarity;\n> +\t\tresult[local_line_b] = start_a + best_similarity_index;\n> +\t\tsecond_best_result[local_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> +\tint max_search_distance_a,\n> +\tint max_search_distance_b,\n> +\tint start_a, int start_b,\n> +\tint length_a, int length_b,\n> +\tstruct fingerprint *fingerprints_a,\n> +\tstruct fingerprint *fingerprints_b,\n> +\tint *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_min, invalidate_max, 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_a, most_certain_local_line_b = -1,\n> +\t\tmost_certain_line_certainty = -1,\n> +\t\tclosest_local_line_a;\n> +\n> +\tfor (i = 0; i < length_b; ++i) {\n> +\t\tfind_best_line_matches(max_search_distance_a,\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       fingerprints_a,\n> +\t\t\t\t       fingerprints_b,\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_local_line_b = i;\n> +\t\t}\n> +\t}\n> +\n> +\tif (most_certain_local_line_b == -1) {\n> +\t\treturn;\n> +\t}\n         ^ removed the {} for a single-line if block.\n\n> +\n> +\tmost_certain_line_a = result[most_certain_local_line_b];\n> +\n> +\t/* Subtract the most certain line's fingerprint in b from the\n> +\t matched fingerprint in a. This means that other lines in b can't also\n> +\t match the same parts of the line in a. */\n         ^ multiline block commits as such:\n         /*\n          * foo\n          * bar\n          */\n> +\tfingerprint_subtract(fingerprints_a + most_certain_line_a - start_a,\n> +\t\t\t     fingerprints_b + most_certain_local_line_b);\n> +\n> +\n> +\t/* Invalidate results that may be affected by the choice of pivot. */\n> +\tinvalidate_min = most_certain_local_line_b - max_search_distance_b;\n> +\tinvalidate_max = most_certain_local_line_b + max_search_distance_b + 1;\n> +\tif (invalidate_min < 0)\n> +\t\tinvalidate_min = 0;\n> +\tif (invalidate_max > length_b)\n> +\t\tinvalidate_max = length_b;\n> +\n> +\tfor (i = invalidate_min; i < invalidate_max; ++i) {\n> +\t\tclosest_local_line_a = get_closest_local_line(\n> +\t\t\tstart_a, i,\n> +\t\t\tclosest_line_calc_offset1,\n> +\t\t\tclosest_line_calc_offset2,\n> +\t\t\tclosest_line_calc_numerator,\n> +\t\t\tclosest_line_calc_denominator);\n> +\t\t*get_similarity(similarities, max_search_distance_a,\n> +\t\t\t\tmost_certain_line_a - start_a, i,\n> +\t\t\t\tclosest_local_line_a) = -1;\n> +\t}\n> +\n> +\tbarrier = most_certain_line_a;\n> +\n> +\tfor (i = most_certain_local_line_b - 1; i >= invalidate_min; --i) {\n> +\t\tif (certainties[i] >= 0 &&\n> +\t\t    (result[i] >= barrier || second_best_result[i] >= barrier)) {\n\nover 80 chars (same below)\n\n> +\t\t\t    certainties[i] = CERTAINTY_NOT_CALCULATED;\n> +\t\t\t    barrier = result[i];\n> +\t\t\t    invalidate_min = i - max_search_distance_b;\n> +\t\t\t    if (invalidate_min < 0)\n> +\t\t\t\t    invalidate_min = 0;\n> +\t\t    }\n> +\t}\n> +\n> +\tbarrier = most_certain_line_a;\n> +\n> +\tfor (i = most_certain_local_line_b + 1; i < invalidate_max; ++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_max = i + max_search_distance_b + 1;\n> +\t\t\t    if (invalidate_max > length_b)\n> +\t\t\t\t    invalidate_max = length_b;\n> +\t\t    }\n> +\t}\n> +\n> +\n> +\tif (most_certain_local_line_b > 0) {\n> +\t\tfuzzy_find_matching_lines_recurse(\n> +\t\t\tmax_search_distance_a,\n> +\t\t\tmax_search_distance_b,\n> +\t\t\tstart_a, start_b,\n> +\t\t\tmost_certain_line_a + 1 - start_a,\n> +\t\t\tmost_certain_local_line_b,\n> +\t\t\tfingerprints_a, fingerprints_b, 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_local_line_b + 1 < length_b) {\n> +\t\tsecond_half_start_a = most_certain_line_a;\n> +\t\toffset_b = most_certain_local_line_b + 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_a,\n> +\t\t\tmax_search_distance_b,\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\tfingerprints_a + second_half_start_a - start_a,\n> +\t\t\tfingerprints_b + offset_b,\n> +\t\t\tsimilarities +\n> +\t\t\t\toffset_b * (max_search_distance_a * 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, *result, *second_best_result,\n> +\t\t*certainties, *similarities, similarity_count;\n> +\tstruct fingerprint *fingerprints_a, *fingerprints_b;\n> +\n> +\t/* max_search_distance_a means that given a line in `b`, compare it to\n> +\tthe line in `a` that is closest to its position, and the lines in `a`\n> +\tthat are no greater than max_search_distance_a lines away from the\n> +\tclosest line in `a`.\n> +\tmax_search_distance_b is an upper bound on the greatest possible\n> +\tdistance between lines in `b` such that they will both be compared with\n> +\tthe same line in `a` according to max_search_distance_a. */\n> +\tint max_search_distance_a = 10, max_search_distance_b;\n> +\n> +\tif (max_search_distance_a >= length_a)\n> +\t\tmax_search_distance_a = length_a ? length_a - 1 : 0;\n> +\n> +\tif (length_a == 0) {\n> +\t\tmax_search_distance_b = 0;\n> +\t}\n> +\telse {\n> +\t\tmax_search_distance_b = ((2 * max_search_distance_a + 1) *\n> +\t\t\tlength_b - 1) / length_a;\n> +\t}\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> +\tsimilarity_count = length_b * (max_search_distance_a * 2 + 1);\n> +\tsimilarities = malloc(sizeof(int) * similarity_count);\n\nxcalloc(x, y) instead of malloc (x * y).  or at least xmalloc.\n\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> +\tfor (i = 0; i < similarity_count; ++i) {\n> +\t\tsimilarities[i] = -1;\n> +\t}\n\t^ removed {}, as as with the 'if' statements\n\n\nBarret\n\n\n\n> +\n> +\tfingerprints_a = xmalloc(sizeof(struct fingerprint) * length_a);\n> +\tfingerprints_b = xmalloc(sizeof(struct fingerprint) * length_b);\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> +\tget_line_fingerprints(fingerprints_b, content_b,\n> +\t\t\t      line_starts_b,\n> +\t\t\t      start_b, length_b);\n> +\n> +\tfuzzy_find_matching_lines_recurse(max_search_distance_a,\n> +\t\t\t\t\t  max_search_distance_b,\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  fingerprints_a,\n> +\t\t\t\t\t  fingerprints_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> +\tfor (i = 0; i < length_b; ++i) {\n> +\t\tfree_fingerprint(fingerprints_b + i);\n> +\t}\n> +\tfor (i = 0; i < length_a; ++i) {\n> +\t\tfree_fingerprint(fingerprints_a + i);\n> +\t}\n> +\tfree(fingerprints_b);\n> +\tfree(fingerprints_a);\n> +\tfree(similarities);\n> +\tfree(certainties);\n> +\tfree(second_best_result);\n> +\n> +\treturn result;\n> +}\n> +\n"},{"id":"374332","messageId":"f6e2d990-e7c8-9636-ae2a-c824e140cebb@google.com","threadId":"50971","inReplyTo":"20190422222647.48628-1-michael@platin.gs","subject":"Re: [PATCH v6 0/6] blame: add the ability to ignore commits","fromName":"Barret Rhoden","fromEmail":"brho@google.com","sentAt":"2019-04-23T21:21:52Z","receivedAt":"2019-04-23T21:21:59Z","isPatch":true,"sender":{"key":"brho@google.com","avatar":null},"body":"Hi Michael -\n\nI cobbled something together that passes my old git tests and all but \none of your tests, though an assertion fails when I use it for real. \nSee below.\n\nOn 4/22/19 6:26 PM, michael@platin.gs wrote:\n[snip]\n> +static int *get_similarity(int *similarities, int max_search_distance_a,\n> +\t\t\t   int local_line_a, int local_line_b,\n> +\t\t\t   int closest_local_line_a) {\n> +\tassert(abs(local_line_a - closest_local_line_a) <= max_search_distance_a);\n\nThis assert fails.  In my example,\n\tlocal_line_a = 1\n\tclosest_local_line_a = 12\n\tmax_search_distance_a = 10\n\nBacktrace tells me it was called here:\n\n> +static void fuzzy_find_matching_lines_recurse(\n\n[snip]\n\n> +\tfor (i = invalidate_min; i < invalidate_max; ++i) {\n> +\t\tclosest_local_line_a = get_closest_local_line(\n> +\t\t\tstart_a, i,\n> +\t\t\tclosest_line_calc_offset1,\n> +\t\t\tclosest_line_calc_offset2,\n> +\t\t\tclosest_line_calc_numerator,\n> +\t\t\tclosest_line_calc_denominator);\n> +\t\t*get_similarity(similarities, max_search_distance_a,\n> +\t\t\t\tmost_certain_line_a - start_a, i,\n> +\t\t\t\tclosest_local_line_a) = -1;\n> +\t}\n\nSo it looks like that '12' came from get_closest_local_line(),  The args \nto that call were:\n\n\tstart_a 258, i 3, off1 0, off2 258 num 83, denom 23\n\nThe equation reduces to 12 + off2 - start_a = 12\n\nI don't know what those values mean, but it looks like A's values affect \noff2 and start_a, but those are only used at the very end of the \ncalculation.  Does 'A' affect off1, numer, or denom?\n\nAny thoughts?  What all is going on here?\n\nIf you want to play with it, it's at\n\n\tgit@github.com:brho/git.git (master)\n\n(Beware the push -f / forced update.  And I figured the repo would be \npreferable to spamming with unrelated patches).\n\nIf you want an example commit the assert fails on, it's this repo:\n\t\n\tgit@github.com:brho/akaros.git\n\tmaster branch\n\tignore-rev-file=.git-blame-ignore-revs\n\tfile user/vmm/virtio_mmio.c\n\nOn an unrelated note:\n\n > The significant change here is that when a line is matched, its \n      > fingerprint is subtracted from the matched parent line's \nfingerprint. > This prevents two lines matching the same part of a \nparent line.\n\nDoes this limit us so that our second pass (the fallback when fuzzy \nfailed) won't be able to match to a parent line that was already matched?\n\n\nThe test that is failing is your Expand Lines test.  The 'final' diff was:\n\n--- a/1\n+++ b/1\n@@ -1,5 +1,7 @@\n  aaa\n-bbb\n+bbbx\n+bbbx\n  ccc\n-ddd\n+dddx\n+dddx\n  eee\n\nWhich should be two diff chunks and two calls to guess_line_blames().\n\nAnd the 'actual' was:\n\n1\n2\nFinal  (not 2)\n3\n4\nFinal  (not 2)\n5\n\nI didn't dig much, but your older stuff (when merged with mine) also \ndidn't pass that test.  Maybe something with the offset/parent_slno stuff.\n\nThanks,\n\nBarret\n\n"},{"id":"374425","messageId":"f3149591-443f-8378-5221-ce4a1879d4af@google.com","threadId":"50971","inReplyTo":"20190422222647.48628-1-michael@platin.gs","subject":"Re: [PATCH v6 0/6] blame: add the ability to ignore commits","fromName":"Barret Rhoden","fromEmail":"brho@google.com","sentAt":"2019-04-24T21:07:01Z","receivedAt":"2019-04-24T21:07:10Z","isPatch":true,"sender":{"key":"brho@google.com","avatar":null},"body":"\nHi Michael -\n\nI dug into the code a bit more and have some more comments below.  Take \nanything I say with a grain of salt; I'm still trying to understand how \nit all works.  =)\n\nIf you do have updates to your patch, see if you can make it apply onto \nmy branch at https://github.com/brho/git/commits/master.  I have a \ncommit there called \"WIP-michael-fuzzy\", which is mostly all of your \nstuff plus the style changes and whatnot I was talking about.  Though if \nyou give me something else, I can make that work too.\n\nAll in all, I think we're pretty close to having something cool.  =)\n\nOn 4/22/19 6:26 PM, michael@platin.gs wrote:\n\n> @@ -0,0 +1,434 @@\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_entry {\n> +\tstruct hashmap_entry entry;\n> +\tint count;\n> +};\n> +struct fingerprint {\n> +\tstruct hashmap map;\n> +\tstruct fingerprint_entry *entries;\n> +};\n> +\n\nThe whole fingerprinting section could use a good comment.  What is a \nfingerprint, why/how we use them, what it means to be similar, etc.\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 fingerprint_entry *entry = xcalloc(map_entry_count,\n> +\t\tsizeof(struct fingerprint_entry));\n> +\tstruct fingerprint_entry *found_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> +\n> +\t\tif ((found_entry = hashmap_get(&result->map, entry, NULL))) {\n> +\t\t\tfound_entry->count += 1;\n> +\t\t}\n> +\t\telse {\n> +\t\t\tentry->count = 1;\n> +\t\t\thashmap_add(&result->map, entry);\n> +\t\t}\n> +\t}\n> +}\n\n[snip]\n\n\n\n\n\n> +static int get_closest_local_line(int start_a,\n> +\t\t\t    int local_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 ((local_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\nOverall, I found the final four parameters (offset1, offset2, numer, and \ndenom) to be confusing, used here and passed through all of the functions.\n\nWhat are they exactly?  Do they ever change from the first invocation of \nfuzzy_find_matching_lines_recurse()?  The only one I saw that changed \nwas 'closest_line_calc_offset1 + offset_b' in the upper half of the \nrecursive call.\n\nSo if I'm following it correctly, closest_line_calc_offset2 is always == \nstart_a, so then in what 'file space' does the return val from \nget_closest_local_line() reside?  A's space?  Relative number to the \nbeginning of start_a?\n\nWhat all is the closest_local_line?  The line in A that corresponds to \nthe line in B, for some mapping function?  Maybe the corresponding \nfractional bit?  (hence the division, but there's also that *2 in there)\n\nThe assertion that trips for me is related to this - we get a \nclosest_local_line_a that is farther than max_search_distance_a from \nlocal_line_a.\n\nOn a related note, any 1-1 offsetting between A and B seems precarious. \nIt's the 'offset' variable passed in from guess_line_blames().  But if \nyou're calculating it from start_b - start_a, that is a little brittle. \nstart_b is the tiny window of e->s_lno.  If we ever change things to \nlook into the entire diff chunk (the one passed to guess_line_blames()), \nthen that will break.  Not sure if you're offsetting in this manner or \nnot.  (looks like 'no').\n\n> +\n> +static int *get_similarity(int *similarities, int max_search_distance_a,\n> +\t\t\t   int local_line_a, int local_line_b,\n> +\t\t\t   int closest_local_line_a) {\n> +\tassert(abs(local_line_a - closest_local_line_a) <= max_search_distance_a);\n> +\treturn similarities + local_line_a - closest_local_line_a +\n> +\t\tmax_search_distance_a +\n> +\t\tlocal_line_b * (max_search_distance_a * 2 + 1);\n> +}\n\nThis needs some sort of comment.  From it's allocation below (and from \nstaring at the code long enough), I gather the similarities array is a \n2D array, \"each line in B\" by \"each line in a window (of size X) in A \ncentered on some line in A mapping to B\", where X is \n(max_search_distance_a * 2 + 1), and 'some line' is closest_local_line_a.\n\nIs this something like \"for line b, get sim for local_line a\"?  Is it \nlocal_line_a or closest_local_line_a that we are getting?  It's not \nclear from the prototype alone.\n\nMaybe the 'closest_local_line_a' ought to be decided inside this \nfunction, so it's a simpler-looking 'getter.'  Or better yet, maybe \nthere's a lookup array mapping B -> \"window in A\".  (more on this later).\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_a,\n> +\t\t\t\t   int start_a,\n> +\t\t\t\t   int length_a,\n> +\t\t\t\t   int local_line_b,\n> +\t\t\t\t   struct fingerprint *fingerprints_a,\n> +\t\t\t\t   struct fingerprint *fingerprints_b,\n\nI was a little worried about keeping track of what offset / \"address \nspace\" we're in.  The fingerprint arrays passed in are both set so the \n0th member corresponds to the FP for start_a or start_b, with length_a \nor length_b members.\n\nstart_a and local_line_b are in different types spaces: start_a is \nabsolute in 'A' and local_line_b is relative in 'B'.  Eventually, I \nfigured out that that is what 'local' meant.  Seeing both start_a \n(absolute) and local_line_b (relative) passed in made me worry a little \nabout whether or not there was a bug.  Maybe compute and pass in the \nlocal_a_line instead?\n\nI see later on that you use start_a in this function so you can store \nresult[] and second_best_result[] in A's absolute space.\n\nIt might make sense to pick a space (absolute or relative) and use it \nthroughout.\n\n> +\t\t\t\t   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_local_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[local_line_b] != CERTAINTY_NOT_CALCULATED)\n> +\t\treturn;\n> +\n> +\tclosest_local_line_a = get_closest_local_line(start_a,\n> +\t\t\t\t\t  local_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_local_line_a - max_search_distance_a;\n> +\tif (search_start < 0)\n> +\t\tsearch_start = 0;\n> +\n> +\tsearch_end = closest_local_line_a + max_search_distance_a + 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 = get_similarity(similarities, max_search_distance_a,\n> +\t\t\t\t\t    i, local_line_b,\n> +\t\t\t\t\t    closest_local_line_a);\n> +\t\tif (*similarity == -1) {\n> +\t\t\t*similarity = fingerprint_similarity(\n> +\t\t\t\tfingerprints_b + local_line_b,\n> +\t\t\t\tfingerprints_a + i) *\n> +\t\t\t\t(1000 - abs(i - closest_local_line_a));\n\nNeed some assertion that \"1000 > 2*max_search_distance_a + 1\" or \nsomething?  I know that number is '21', but it's based on a hard-coded \ninteger somewhere else.\n\n> +\t\t}\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[local_line_b] = CERTAIN_NOTHING_MATCHES;\n> +\t\tresult[local_line_b] = -1;\n> +\t}\n> +\telse {\n> +\t\tcertainties[local_line_b] = best_similarity * 2 -\n> +\t\t\tsecond_best_similarity;\n> +\t\tresult[local_line_b] = start_a + best_similarity_index;\n> +\t\tsecond_best_result[local_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> +\tint max_search_distance_a,\n> +\tint max_search_distance_b,\n> +\tint start_a, int start_b,\n> +\tint length_a, int length_b,\n> +\tstruct fingerprint *fingerprints_a,\n> +\tstruct fingerprint *fingerprints_b,\n> +\tint *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\nFor all of the arguments that never change, which seem to be the last \nthree args and the search distances, you could consider putting them in \na struct and passing that along.  Similarly, the only time the \nfingerprints and the four int arrays change is in the upper half of the \nrecursive call.\n\nYou might be able to put most all of those array args into the args \nstruct too, such that that struct always represents the original window \n(or even the absolute numbers?), and then pass along the offsets. \nYou're somewhat doing that already when you pass second_half_start_a, \nsecond_half_start_b (which includes offset_b), etc, down below.\n\n> +\n> +\tint i, barrier, invalidate_min, invalidate_max, 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_a, most_certain_local_line_b = -1,\n> +\t\tmost_certain_line_certainty = -1,\n> +\t\tclosest_local_line_a;\n> +\n> +\tfor (i = 0; i < length_b; ++i) {\n> +\t\tfind_best_line_matches(max_search_distance_a,\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       fingerprints_a,\n> +\t\t\t\t       fingerprints_b,\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_local_line_b = i;\n> +\t\t}\n> +\t}\n> +\n> +\tif (most_certain_local_line_b == -1) {\n> +\t\treturn;\n> +\t}\n> +\n> +\tmost_certain_line_a = result[most_certain_local_line_b];\n> +\n> +\t/* Subtract the most certain line's fingerprint in b from the\n> +\t matched fingerprint in a. This means that other lines in b can't also\n> +\t match the same parts of the line in a. */\n> +\tfingerprint_subtract(fingerprints_a + most_certain_line_a - start_a,\n> +\t\t\t     fingerprints_b + most_certain_local_line_b);\n\nFYI, if I comment out fingerprint_subtract, this will pass your test 2 \n(currently failing), but fail test 5 (currently passing).\n\n> +\n> +\n> +\t/* Invalidate results that may be affected by the choice of pivot. */\n> +\tinvalidate_min = most_certain_local_line_b - max_search_distance_b;\n> +\tinvalidate_max = most_certain_local_line_b + max_search_distance_b + 1;\n> +\tif (invalidate_min < 0)\n> +\t\tinvalidate_min = 0;\n> +\tif (invalidate_max > length_b)\n> +\t\tinvalidate_max = length_b;\n> +\n> +\tfor (i = invalidate_min; i < invalidate_max; ++i) {\n> +\t\tclosest_local_line_a = get_closest_local_line(\n> +\t\t\tstart_a, i,\n> +\t\t\tclosest_line_calc_offset1,\n> +\t\t\tclosest_line_calc_offset2,\n> +\t\t\tclosest_line_calc_numerator,\n> +\t\t\tclosest_line_calc_denominator);\n> +\t\t*get_similarity(similarities, max_search_distance_a,\n> +\t\t\t\tmost_certain_line_a - start_a, i,\n> +\t\t\t\tclosest_local_line_a) = -1;\n\nThe assert in get_similarity fails on my example when called from here. \nI guess something went wrong with finding the window center.\n\n> +\t}\n> +\n> +\tbarrier = most_certain_line_a;\n> +\n> +\tfor (i = most_certain_local_line_b - 1; i >= invalidate_min; --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_min = i - max_search_distance_b;\n> +\t\t\t    if (invalidate_min < 0)\n> +\t\t\t\t    invalidate_min = 0;\n> +\t\t    }\n> +\t}\n\nIs it important for this function (above) to go in descending order, and \nthe next to go in ascending order?  If you can go i = 0; i<foo; i++ for \nboth, then maybe a helper function can replace both of these functions \n(above and below this comment).\n\n> +\n> +\tbarrier = most_certain_line_a;\n> +\n> +\tfor (i = most_certain_local_line_b + 1; i < invalidate_max; ++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_max = i + max_search_distance_b + 1;\n> +\t\t\t    if (invalidate_max > length_b)\n> +\t\t\t\t    invalidate_max = length_b;\n> +\t\t    }\n> +\t}\n\nWhat's the intuition behind the steps to invalidate the results?\n\nIt looks like you want to reset the similarity calculations for any \nother line in B that was compared to the matching A line, so that that A \nline is not matched again until its similarity is recomputed (due to the \n\"fingerprint subtraction\"?).\n\nYou limit it to invalidate_min and max, then clamp those to the real \nmin/max (0, length_b).  Initially, I thought that's a performance \noptimization (vs correctness) since you want to limit recalculations. \nThough I think the assumption is that you'll never ask for a \nget_similarity(a, b) where A is outside the reachable radius of B \n(max_search_distance_b).\n\nWhat about with the certainties?  It seems like you're trying to limit \nwhich ones get reset.  Why do you check result[i] <= barrier, instead of \njust equality?\n\n> +\n> +\n> +\tif (most_certain_local_line_b > 0) {\n> +\t\tfuzzy_find_matching_lines_recurse(\n> +\t\t\tmax_search_distance_a,\n> +\t\t\tmax_search_distance_b,\n> +\t\t\tstart_a, start_b,\n> +\t\t\tmost_certain_line_a + 1 - start_a,\n> +\t\t\tmost_certain_local_line_b,\n> +\t\t\tfingerprints_a, fingerprints_b, 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_local_line_b + 1 < length_b) {\n> +\t\tsecond_half_start_a = most_certain_line_a;\n> +\t\toffset_b = most_certain_local_line_b + 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_a,\n> +\t\t\tmax_search_distance_b,\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\tfingerprints_a + second_half_start_a - start_a,\n> +\t\t\tfingerprints_b + offset_b,\n> +\t\t\tsimilarities +\n> +\t\t\t\toffset_b * (max_search_distance_a * 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, *result, *second_best_result,\n> +\t\t*certainties, *similarities, similarity_count;\n> +\tstruct fingerprint *fingerprints_a, *fingerprints_b;\n> +\n> +\t/* max_search_distance_a means that given a line in `b`, compare it to\n> +\tthe line in `a` that is closest to its position, and the lines in `a`\n> +\tthat are no greater than max_search_distance_a lines away from the\n> +\tclosest line in `a`.\n> +\tmax_search_distance_b is an upper bound on the greatest possible\n> +\tdistance between lines in `b` such that they will both be compared with\n> +\tthe same line in `a` according to max_search_distance_a. */\n> +\tint max_search_distance_a = 10, max_search_distance_b;\n> +\n> +\tif (max_search_distance_a >= length_a)\n> +\t\tmax_search_distance_a = length_a ? length_a - 1 : 0;\n> +\n> +\tif (length_a == 0) {\n> +\t\tmax_search_distance_b = 0;\n> +\t}\n> +\telse {\n> +\t\tmax_search_distance_b = ((2 * max_search_distance_a + 1) *\n> +\t\t\tlength_b - 1) / length_a;\n> +\t}\n\nA few questions / comments about these search distances:\n\n- max_search_distance_a and _b sounds like different concepts.  maybe \ndifferent names?  it's also hard to follow how you get these numbers, \nespecially since it seems there is some scaling involved when converting \nfrom A space to B space.\n\n- is the max_search_distance_a limited to 10 for performance reasons? \nconceptually, it'd be easier the similarities array was length_b * \nlength_a.  instead, it sounds like every line B has a (potentially) \nseparate window into A.  maybe it'd be simpler to have another array \nthat tracks for each B, which line in A is the *start* of its window. \nthat'd also make me rest easier when worrying about odd numbers, \ndivision, and off-by-one issues.\n\n- the (2 * max_search_distance_a + 1) comes up a lot.  similarly, that \ncalculation involving dividing by length_a comes up too.  maybe \nencapsulate those in some other smaller set of functions, so it's clear \nwhen they are being used for the same purpose.  i'm having a hard time \nconvincing myself there aren't off-by-one issues.  (not that there are).\n\nThanks,\n\nBarret\n\n"}]}