[PATCH v6 0/6] blame: add the ability to ignore commits

[PATCH v6 0/6] blame: add the ability to ignore commits

[Barret Rhoden]

This patch set adds the ability to ignore a set of commits and their
changes when blaming.  This can be used to ignore a commit deemed 'not
interesting,' such as reformatting.

The last patch in the series changes the heuristic by which ignored
lines are attributed to specific lines in the parent commit.  This
increases the likelihood of blaming the 'right' commit, where 'right' is
subjective.  Perhaps we want another algorithm.  I'm using a relatively
simple one that uses the basics of Michael's fingerprinting code, but he
has another algorithm.

v5 -> v6
v5: https://public-inbox.org/git/20190403160207.149174-1-brho@google.com/
- The "guess" heuristic can now look anywhere in the parent file for a
  matching line, instead of just looking in the parent chunk.  The
  chunks passed to blame_chunk() are smaller than you'd expect: they are
  just adjacent '-' and '+' sections.  Any diff 'context' is a chunk
  boundary.
- Fixed the parent_len calculation.  I had been basing it off of
  e->num_lines, and treating the blame entry as if it was the target
  chunk, but the individual blame entries are subsets of the chunk.  I
  just pass the parent chunk info all the way through now.
- Use Michael's newest fingerprinting code, which is a large speedup.
- Made a config option to zero the hash for an ignored line when the
  heuristic could not find a line in the parent to blame.  Previously,
  this was always 'on'.
- Moved the for loop variable declarations out of the for ().
- Rebased on master.

v4 -> v5
v4: https://public-inbox.org/git/20190226170648.211847-1-brho@google.com/
- Changed the handling of blame_entries from ignored commits so that you
  can use any algorithm you want to map lines from the diff chunk to
  different parts of the parent commit.
- fill_origin_blob() optionally can track the offsets of the start of
  every line, similar to what we do in the scoreboard for the final
  file.  This can be used by the matching algorithm.  It has no effect
  if you are not ignoring commits.
- RFC of a fuzzy/fingerprinting heuristic, based on Michael Platings RFC
  at https://public-inbox.org/git/20190324235020.49706-2-michael@platin.gs/
- Made the tests that detect unblamable entries more resilient to
  different heuristics.
- Fixed a few bugs:
	- tests were not grepping the line number from --line-porcelain
	  correctly.
	- In the old version, when I passed the "upper" part of the
	  blame entry to the target and marked unblamable, the suspect
	  was incorrectly marked as the parent.  The s_lno was also in
	  the parent's address space.

v3 -> v4
v3: https://public-inbox.org/git/20190212222722.240676-1-brho@google.com/
- Cleaned up the tests, especially removing usage of sed -i.
- Squashed the 'tests' commit into the other blame commits.  Let me know
  if you'd like further squashing.

v2 -> v3
v2: https://public-inbox.org/git/20190117202919.157326-1-brho@google.com/
- SHA-1 -> "object name", and fixed other comments
- Changed error string for oidset_parse_file()
- Adjusted existing fsck tests to handle those string changes
- Return hash of all zeros for lines we know we cannot identify
- Allow repeated options for blame.ignoreRevsFile and
  --ignore-revs-file.  An empty file name resets the list.  Config
  options are parsed before the command line options.
- Rebased to master
- Added regression tests

v1 -> v2
v1: https://public-inbox.org/git/20190107213013.231514-1-brho@google.com/
- extracted the skiplist from fsck to avoid duplicating code
- overhauled the interface and options
- split out markIgnoredFiles
- handled merges


Barret Rhoden (6):
  Move init_skiplist() outside of fsck
  blame: use a helper function in blame_chunk()
  blame: add the ability to ignore commits and their changes
  blame: add config options to handle output for ignored lines
  blame: optionally track line fingerprints during fill_blame_origin()
  blame: use a fingerprint heuristic to match ignored lines

 Documentation/blame-options.txt |  18 ++
 Documentation/config/blame.txt  |  16 ++
 Documentation/git-blame.txt     |   1 +
 blame.c                         | 446 ++++++++++++++++++++++++++++----
 blame.h                         |   6 +
 builtin/blame.c                 |  56 ++++
 fsck.c                          |  37 +--
 oidset.c                        |  35 +++
 oidset.h                        |   8 +
 t/t5504-fetch-receive-strict.sh |  14 +-
 t/t8013-blame-ignore-revs.sh    | 202 +++++++++++++++
 11 files changed, 740 insertions(+), 99 deletions(-)
 create mode 100755 t/t8013-blame-ignore-revs.sh

-- 
2.21.0.392.gf8f6787159e-goog

[PATCH v6 1/6] Move init_skiplist() outside of fsck

[Barret Rhoden]

init_skiplist() took a file consisting of SHA-1s and comments and added
the objects to an oidset.  This functionality is useful for other
commands.

Signed-off-by: Barret Rhoden <brho@google.com>
---
 fsck.c                          | 37 +--------------------------------
 oidset.c                        | 35 +++++++++++++++++++++++++++++++
 oidset.h                        |  8 +++++++
 t/t5504-fetch-receive-strict.sh | 14 ++++++-------
 4 files changed, 51 insertions(+), 43 deletions(-)

diff --git a/fsck.c b/fsck.c
index 2260adb71e7a..d45534ad90f5 100644
--- a/fsck.c
+++ b/fsck.c
@@ -181,41 +181,6 @@ static int fsck_msg_type(enum fsck_msg_id msg_id,
 	return msg_type;
 }
 
-static void init_skiplist(struct fsck_options *options, const char *path)
-{
-	FILE *fp;
-	struct strbuf sb = STRBUF_INIT;
-	struct object_id oid;
-
-	fp = fopen(path, "r");
-	if (!fp)
-		die("Could not open skip list: %s", path);
-	while (!strbuf_getline(&sb, fp)) {
-		const char *p;
-		const char *hash;
-
-		/*
-		 * Allow trailing comments, leading whitespace
-		 * (including before commits), and empty or whitespace
-		 * only lines.
-		 */
-		hash = strchr(sb.buf, '#');
-		if (hash)
-			strbuf_setlen(&sb, hash - sb.buf);
-		strbuf_trim(&sb);
-		if (!sb.len)
-			continue;
-
-		if (parse_oid_hex(sb.buf, &oid, &p) || *p != '\0')
-			die("Invalid SHA-1: %s", sb.buf);
-		oidset_insert(&options->skiplist, &oid);
-	}
-	if (ferror(fp))
-		die_errno("Could not read '%s'", path);
-	fclose(fp);
-	strbuf_release(&sb);
-}
-
 static int parse_msg_type(const char *str)
 {
 	if (!strcmp(str, "error"))
@@ -284,7 +249,7 @@ void fsck_set_msg_types(struct fsck_options *options, const char *values)
 		if (!strcmp(buf, "skiplist")) {
 			if (equal == len)
 				die("skiplist requires a path");
-			init_skiplist(options, buf + equal + 1);
+			oidset_parse_file(&options->skiplist, buf + equal + 1);
 			buf += len + 1;
 			continue;
 		}
diff --git a/oidset.c b/oidset.c
index fe4eb921df81..878a1b56af1c 100644
--- a/oidset.c
+++ b/oidset.c
@@ -35,3 +35,38 @@ void oidset_clear(struct oidset *set)
 	kh_release_oid(&set->set);
 	oidset_init(set, 0);
 }
+
+void oidset_parse_file(struct oidset *set, const char *path)
+{
+	FILE *fp;
+	struct strbuf sb = STRBUF_INIT;
+	struct object_id oid;
+
+	fp = fopen(path, "r");
+	if (!fp)
+		die("Could not open object name list: %s", path);
+	while (!strbuf_getline(&sb, fp)) {
+		const char *p;
+		const char *name;
+
+		/*
+		 * Allow trailing comments, leading whitespace
+		 * (including before commits), and empty or whitespace
+		 * only lines.
+		 */
+		name = strchr(sb.buf, '#');
+		if (name)
+			strbuf_setlen(&sb, name - sb.buf);
+		strbuf_trim(&sb);
+		if (!sb.len)
+			continue;
+
+		if (parse_oid_hex(sb.buf, &oid, &p) || *p != '\0')
+			die("Invalid object name: %s", sb.buf);
+		oidset_insert(set, &oid);
+	}
+	if (ferror(fp))
+		die_errno("Could not read '%s'", path);
+	fclose(fp);
+	strbuf_release(&sb);
+}
diff --git a/oidset.h b/oidset.h
index c9d0f6d3cc8b..c4807749df8d 100644
--- a/oidset.h
+++ b/oidset.h
@@ -73,6 +73,14 @@ int oidset_remove(struct oidset *set, const struct object_id *oid);
  */
 void oidset_clear(struct oidset *set);
 
+/**
+ * Add the contents of the file 'path' to an initialized oidset.  Each line is
+ * an unabbreviated object name.  Comments begin with '#', and trailing comments
+ * are allowed.  Leading whitespace and empty or white-space only lines are
+ * ignored.
+ */
+void oidset_parse_file(struct oidset *set, const char *path);
+
 struct oidset_iter {
 	kh_oid_t *set;
 	khiter_t iter;
diff --git a/t/t5504-fetch-receive-strict.sh b/t/t5504-fetch-receive-strict.sh
index 7bc706873c5b..7184f1d07f90 100755
--- a/t/t5504-fetch-receive-strict.sh
+++ b/t/t5504-fetch-receive-strict.sh
@@ -164,9 +164,9 @@ test_expect_success 'fsck with unsorted skipList' '
 test_expect_success 'fsck with invalid or bogus skipList input' '
 	git -c fsck.skipList=/dev/null -c fsck.missingEmail=ignore fsck &&
 	test_must_fail git -c fsck.skipList=does-not-exist -c fsck.missingEmail=ignore fsck 2>err &&
-	test_i18ngrep "Could not open skip list: does-not-exist" err &&
+	test_i18ngrep "Could not open object name list: does-not-exist" err &&
 	test_must_fail git -c fsck.skipList=.git/config -c fsck.missingEmail=ignore fsck 2>err &&
-	test_i18ngrep "Invalid SHA-1: \[core\]" err
+	test_i18ngrep "Invalid object name: \[core\]" err
 '
 
 test_expect_success 'fsck with other accepted skipList input (comments & empty lines)' '
@@ -193,7 +193,7 @@ test_expect_success 'fsck no garbage output from comments & empty lines errors'
 test_expect_success 'fsck with invalid abbreviated skipList input' '
 	echo $commit | test_copy_bytes 20 >SKIP.abbreviated &&
 	test_must_fail git -c fsck.skipList=SKIP.abbreviated fsck 2>err-abbreviated &&
-	test_i18ngrep "^fatal: Invalid SHA-1: " err-abbreviated
+	test_i18ngrep "^fatal: Invalid object name: " err-abbreviated
 '
 
 test_expect_success 'fsck with exhaustive accepted skipList input (various types of comments etc.)' '
@@ -226,10 +226,10 @@ test_expect_success 'push with receive.fsck.skipList' '
 	test_must_fail git push --porcelain dst bogus &&
 	git --git-dir=dst/.git config receive.fsck.skipList does-not-exist &&
 	test_must_fail git push --porcelain dst bogus 2>err &&
-	test_i18ngrep "Could not open skip list: does-not-exist" err &&
+	test_i18ngrep "Could not open object name list: does-not-exist" err &&
 	git --git-dir=dst/.git config receive.fsck.skipList config &&
 	test_must_fail git push --porcelain dst bogus 2>err &&
-	test_i18ngrep "Invalid SHA-1: \[core\]" err &&
+	test_i18ngrep "Invalid object name: \[core\]" err &&
 
 	git --git-dir=dst/.git config receive.fsck.skipList SKIP &&
 	git push --porcelain dst bogus
@@ -255,10 +255,10 @@ test_expect_success 'fetch with fetch.fsck.skipList' '
 	test_must_fail git --git-dir=dst/.git fetch "file://$(pwd)" $refspec &&
 	git --git-dir=dst/.git config fetch.fsck.skipList does-not-exist &&
 	test_must_fail git --git-dir=dst/.git fetch "file://$(pwd)" $refspec 2>err &&
-	test_i18ngrep "Could not open skip list: does-not-exist" err &&
+	test_i18ngrep "Could not open object name list: does-not-exist" err &&
 	git --git-dir=dst/.git config fetch.fsck.skipList dst/.git/config &&
 	test_must_fail git --git-dir=dst/.git fetch "file://$(pwd)" $refspec 2>err &&
-	test_i18ngrep "Invalid SHA-1: \[core\]" err &&
+	test_i18ngrep "Invalid object name: \[core\]" err &&
 
 	git --git-dir=dst/.git config fetch.fsck.skipList dst/.git/SKIP &&
 	git --git-dir=dst/.git fetch "file://$(pwd)" $refspec
-- 
2.21.0.392.gf8f6787159e-goog

Re: [PATCH v6 1/6] Move init_skiplist() outside of fsck

[Ævar Arnfjörð Bjarmason]

On Wed, Apr 10 2019, Barret Rhoden wrote:

> init_skiplist() took a file consisting of SHA-1s and comments and added
> the objects to an oidset.  This functionality is useful for other
> commands.

This change would be much easier to review if you led with a commit
where you s/Invalid SHA-1/invalid object name/ (lower-case while we're
at it), s/skip list/object name/ etc, and did that rename of the "hash"
to "name" variable if you're so inclined.

Then you'd end up with a small refactoring change that changes the tests
(or even just make the tests grep for e.g. "Could not open.*:
does-not-exist" instead), and the moving of the function would be
entirely caught by the rename detection.

Re: [PATCH v6 1/6] Move init_skiplist() outside of fsck

[Barret Rhoden]

On 4/10/19 3:04 PM, Ævar Arnfjörð Bjarmason wrote:
> 
> On Wed, Apr 10 2019, Barret Rhoden wrote:
> 
>> init_skiplist() took a file consisting of SHA-1s and comments and added
>> the objects to an oidset.  This functionality is useful for other
>> commands.
> 
> This change would be much easier to review if you led with a commit
> where you s/Invalid SHA-1/invalid object name/ (lower-case while we're
> at it), s/skip list/object name/ etc, and did that rename of the "hash"
> to "name" variable if you're so inclined.
> 
> Then you'd end up with a small refactoring change that changes the tests
> (or even just make the tests grep for e.g. "Could not open.*:
> does-not-exist" instead), and the moving of the function would be
> entirely caught by the rename detection.
> 

Can do.  I'll split this up in the next round.

Thanks,

Barret

[PATCH v6 2/6] blame: use a helper function in blame_chunk()

[Barret Rhoden]

The same code for splitting a blame_entry at a particular line was used
twice in blame_chunk(), and I'll use the helper again in an upcoming
patch.

Signed-off-by: Barret Rhoden <brho@google.com>
---
 blame.c | 44 ++++++++++++++++++++++++++++----------------
 1 file changed, 28 insertions(+), 16 deletions(-)

diff --git a/blame.c b/blame.c
index 5c07dec19035..9555a9420836 100644
--- a/blame.c
+++ b/blame.c
@@ -839,6 +839,27 @@ static struct blame_entry *reverse_blame(struct blame_entry *head,
 	return tail;
 }
 
+/*
+ * Splits a blame entry into two entries at 'len' lines.  The original 'e'
+ * consists of len lines, i.e. [e->lno, e->lno + len), and the second part,
+ * which is returned, consists of the remainder: [e->lno + len, e->lno +
+ * e->num_lines).  The caller needs to sort out the reference counting for the
+ * new entry's suspect.
+ */
+static struct blame_entry *split_blame_at(struct blame_entry *e, int len,
+					  struct blame_origin *new_suspect)
+{
+	struct blame_entry *n = xcalloc(1, sizeof(struct blame_entry));
+
+	n->suspect = new_suspect;
+	n->lno = e->lno + len;
+	n->s_lno = e->s_lno + len;
+	n->num_lines = e->num_lines - len;
+	e->num_lines = len;
+	e->score = 0;
+	return n;
+}
+
 /*
  * Process one hunk from the patch between the current suspect for
  * blame_entry e and its parent.  This first blames any unfinished
@@ -865,14 +886,9 @@ static void blame_chunk(struct blame_entry ***dstq, struct blame_entry ***srcq,
 		 */
 		if (e->s_lno + e->num_lines > tlno) {
 			/* Move second half to a new record */
-			int len = tlno - e->s_lno;
-			struct blame_entry *n = xcalloc(1, sizeof (struct blame_entry));
-			n->suspect = e->suspect;
-			n->lno = e->lno + len;
-			n->s_lno = e->s_lno + len;
-			n->num_lines = e->num_lines - len;
-			e->num_lines = len;
-			e->score = 0;
+			struct blame_entry *n;
+
+			n = split_blame_at(e, tlno - e->s_lno, e->suspect);
 			/* Push new record to diffp */
 			n->next = diffp;
 			diffp = n;
@@ -919,14 +935,10 @@ static void blame_chunk(struct blame_entry ***dstq, struct blame_entry ***srcq,
 			 * Move second half to a new record to be
 			 * processed by later chunks
 			 */
-			int len = same - e->s_lno;
-			struct blame_entry *n = xcalloc(1, sizeof (struct blame_entry));
-			n->suspect = blame_origin_incref(e->suspect);
-			n->lno = e->lno + len;
-			n->s_lno = e->s_lno + len;
-			n->num_lines = e->num_lines - len;
-			e->num_lines = len;
-			e->score = 0;
+			struct blame_entry *n;
+
+			n = split_blame_at(e, same - e->s_lno,
+					   blame_origin_incref(e->suspect));
 			/* Push new record to samep */
 			n->next = samep;
 			samep = n;
-- 
2.21.0.392.gf8f6787159e-goog

[PATCH v6 3/6] blame: add the ability to ignore commits and their changes

[Barret Rhoden]

Commits that make formatting changes or function renames are often not
interesting when blaming a file.  A user may deem such a commit as 'not
interesting' and want to ignore and its changes it when assigning blame.

For example, say a file has the following git history / rev-list:

---O---A---X---B---C---D---Y---E---F

Commits X and Y both touch a particular line, and the other commits do
not:

X: "Take a third parameter"
-MyFunc(1, 2);
+MyFunc(1, 2, 3);

Y: "Remove camelcase"
-MyFunc(1, 2, 3);
+my_func(1, 2, 3);

git-blame will blame Y for the change.  I'd like to be able to ignore Y:
both the existence of the commit as well as any changes it made.  This
differs from -S rev-list, which specifies the list of commits to
process for the blame.  We would still process Y, but just don't let the
blame 'stick.'

This patch adds the ability for users to ignore a revision with
--ignore-rev=rev, which may be repeated.  They can specify a set of
files of full object names of revs, e.g. SHA-1 hashes, one per line.  A
single file may be specified with the blame.ignoreRevFile config option
or with --ignore-rev-file=file.  Both the config option and the command
line option may be repeated multiple times.  An empty file name "" will
clear the list of revs from previously processed files.  Config options
are processed before command line options.

For a typical use case, projects will maintain the file containing
revisions for commits that perform mass reformatting, and their users
have the optional to ignore all of the commits in that file.

Additionally, a user can use the --ignore-rev option for one-off
investigation.  To go back to the example above, X was a substantive
change to the function, but not the change the user is interested in.
The user inspected X, but wanted to find the previous change to that
line - perhaps a commit that introduced that function call.

To make this work, we can't simply remove all ignored commits from the
rev-list.  We need to diff the changes introduced by Y so that we can
ignore them.  We let the blames get passed to Y, just like when
processing normally.  When Y is the target, we make sure that Y does not
*keep* any blames.  Any changes that Y is responsible for get passed to
its parent.  Note we make one pass through all of the scapegoats
(parents) to attempt to pass blame normally; we don't know if we *need*
to ignore the commit until we've checked all of the parents.

The blame_entry will get passed up the tree until we find a commit that
has a diff chunk that affects those lines.

One issue is that the ignored commit *did* make some change, and there is
no general solution to finding the line in the parent commit that
corresponds to a given line in the ignored commit.  That makes it hard
to attribute a particular line within an ignored commit's diff
correctly.

For example, the parent of an ignored commit has this, say at line 11:

commit-a 11) #include "a.h"
commit-b 12) #include "b.h"

Commit X, which we will ignore, swaps these lines:

commit-X 11) #include "b.h"
commit-X 12) #include "a.h"

We can pass that blame entry to the parent, but line 11 will be
attributed to commit A, even though "include b.h" came from commit B.
The blame mechanism will be looking at the parent's view of the file at
line number 11.

ignore_blame_entry() is set up to allow alternative algorithms for
guessing per-line blames.  Any line that is not attributed to the parent
is marked as 'unblamable', and we output a hash of all zeros.

The existing algorithm is simple: blame each line on the corresponding
line in the parent's diff chunk.  Any lines beyond that stay with the
target.

For example, the parent of an ignored commit has this, say at line 11:

commit-a 11) void new_func_1(void *x, void *y);
commit-b 12) void new_func_2(void *x, void *y);
commit-c 13) some_line_c
commit-d 14) some_line_d

After a commit 'X', we have:

commit-X 11) void new_func_1(void *x,
commit-X 12)                 void *y);
commit-X 13) void new_func_2(void *x,
commit-X 14)                 void *y);
commit-c 15) some_line_c
commit-d 16) some_line_d

Commit X nets two additionally lines: 13 and 14.  The current
guess_line_blames() algorithm will not attribute these to the parent,
whose diff chunk is only two lines - not four.

When we ignore with the current algorithm, we get:

commit-a 11) void new_func_1(void *x,
commit-b 12)                 void *y);
00000000 13) void new_func_2(void *x,
00000000 14)                 void *y);
commit-c 15) some_line_c
commit-d 16) some_line_d

Note that line 12 was blamed on B, though B was the commit for
new_func_2(), not new_func_1().  Even when guess_line_blames() finds a
line in the parent, it may still be incorrect.

Signed-off-by: Barret Rhoden <brho@google.com>
---
 Documentation/blame-options.txt |  14 +++
 Documentation/config/blame.txt  |   7 ++
 Documentation/git-blame.txt     |   1 +
 blame.c                         | 181 ++++++++++++++++++++++++++++++--
 blame.h                         |   3 +
 builtin/blame.c                 |  42 ++++++++
 t/t8013-blame-ignore-revs.sh    | 168 +++++++++++++++++++++++++++++
 7 files changed, 406 insertions(+), 10 deletions(-)
 create mode 100755 t/t8013-blame-ignore-revs.sh

diff --git a/Documentation/blame-options.txt b/Documentation/blame-options.txt
index dc41957afab2..8f155196c6fe 100644
--- a/Documentation/blame-options.txt
+++ b/Documentation/blame-options.txt
@@ -110,5 +110,19 @@ commit. And the default value is 40. If there are more than one
 `-C` options given, the <num> argument of the last `-C` will
 take effect.
 
+--ignore-rev <rev>::
+	Ignore changes made by the revision when assigning blame, as if the
+	change never happened.  Lines that were changed or added by an ignored
+	commit will be blamed on the previous commit that changed that line or
+	nearby lines.  This option may be specified multiple times to ignore
+	more than one revision.
+
+--ignore-revs-file <file>::
+	Ignore revisions listed in `file`, one unabbreviated object name per line.
+	Whitespace and comments beginning with `#` are ignored.  This option may be
+	repeated, and these files will be processed after any files specified with
+	the `blame.ignoreRevsFile` config option.  An empty file name, `""`, will
+	clear the list of revs from previously processed files.
+
 -h::
 	Show help message.
diff --git a/Documentation/config/blame.txt b/Documentation/config/blame.txt
index 67b5c1d1e02a..4da2788f306d 100644
--- a/Documentation/config/blame.txt
+++ b/Documentation/config/blame.txt
@@ -19,3 +19,10 @@ blame.showEmail::
 blame.showRoot::
 	Do not treat root commits as boundaries in linkgit:git-blame[1].
 	This option defaults to false.
+
+blame.ignoreRevsFile::
+	Ignore revisions listed in the file, one unabbreviated object name per
+	line, in linkgit:git-blame[1].  Whitespace and comments beginning with
+	`#` are ignored.  This option may be repeated multiple times.  Empty
+	file names will reset the list of ignored revisions.  This option will
+	be handled before the command line option `--ignore-revs-file`.
diff --git a/Documentation/git-blame.txt b/Documentation/git-blame.txt
index 16323eb80e31..7e8154199635 100644
--- a/Documentation/git-blame.txt
+++ b/Documentation/git-blame.txt
@@ -10,6 +10,7 @@ SYNOPSIS
 [verse]
 'git blame' [-c] [-b] [-l] [--root] [-t] [-f] [-n] [-s] [-e] [-p] [-w] [--incremental]
 	    [-L <range>] [-S <revs-file>] [-M] [-C] [-C] [-C] [--since=<date>]
+	    [--ignore-rev <rev>] [--ignore-revs-file <file>]
 	    [--progress] [--abbrev=<n>] [<rev> | --contents <file> | --reverse <rev>..<rev>]
 	    [--] <file>
 
diff --git a/blame.c b/blame.c
index 9555a9420836..0bbb86ad5985 100644
--- a/blame.c
+++ b/blame.c
@@ -480,7 +480,8 @@ void blame_coalesce(struct blame_scoreboard *sb)
 
 	for (ent = sb->ent; ent && (next = ent->next); ent = next) {
 		if (ent->suspect == next->suspect &&
-		    ent->s_lno + ent->num_lines == next->s_lno) {
+		    ent->s_lno + ent->num_lines == next->s_lno &&
+		    ent->unblamable == next->unblamable) {
 			ent->num_lines += next->num_lines;
 			ent->next = next->next;
 			blame_origin_decref(next->suspect);
@@ -732,6 +733,10 @@ static void split_overlap(struct blame_entry *split,
 	int chunk_end_lno;
 	memset(split, 0, sizeof(struct blame_entry [3]));
 
+	split[0].unblamable = e->unblamable;
+	split[1].unblamable = e->unblamable;
+	split[2].unblamable = e->unblamable;
+
 	if (e->s_lno < tlno) {
 		/* there is a pre-chunk part not blamed on parent */
 		split[0].suspect = blame_origin_incref(e->suspect);
@@ -852,6 +857,7 @@ static struct blame_entry *split_blame_at(struct blame_entry *e, int len,
 	struct blame_entry *n = xcalloc(1, sizeof(struct blame_entry));
 
 	n->suspect = new_suspect;
+	n->unblamable = e->unblamable;
 	n->lno = e->lno + len;
 	n->s_lno = e->s_lno + len;
 	n->num_lines = e->num_lines - len;
@@ -860,6 +866,109 @@ static struct blame_entry *split_blame_at(struct blame_entry *e, int len,
 	return n;
 }
 
+struct blame_line_tracker {
+	int is_parent;
+	int s_lno;
+};
+
+static int are_lines_adjacent(struct blame_line_tracker *first,
+			      struct blame_line_tracker *second)
+{
+	return first->is_parent == second->is_parent &&
+	       first->s_lno + 1 == second->s_lno;
+}
+
+/*
+ * This cheap heuristic assigns lines in the chunk to their relative location in
+ * the parent's chunk.  Any additional lines are left with the target.
+ */
+static void guess_line_blames(struct blame_entry *e,
+			      struct blame_origin *parent,
+			      struct blame_origin *target,
+			      int offset, int parent_slno, int parent_len,
+			      struct blame_line_tracker *line_blames)
+{
+	int i, parent_idx;
+
+	for (i = 0; i < e->num_lines; i++) {
+		parent_idx = e->s_lno + i + offset;
+		if (parent_slno <= parent_idx &&
+		    parent_idx < parent_slno + parent_len) {
+			line_blames[i].is_parent = 1;
+			line_blames[i].s_lno = parent_idx;
+		} else {
+			line_blames[i].is_parent = 0;
+			line_blames[i].s_lno = e->s_lno + i;
+		}
+	}
+}
+
+/*
+ * This decides which parts of a blame entry go to the parent (added to the
+ * ignoredp list) and which stay with the target (added to the diffp list).  The
+ * actual decision is made in a separate heuristic function.  This consumes e,
+ * essentially putting it on a list.
+ *
+ * Note that the blame entries on the ignoredp list are not necessarily sorted
+ * with respect to the parent's line numbers yet.
+ */
+static void ignore_blame_entry(struct blame_entry *e,
+			       struct blame_origin *parent,
+			       struct blame_origin *target,
+			       int offset, int parent_slno, int parent_len,
+			       struct blame_entry **diffp,
+			       struct blame_entry **ignoredp)
+{
+	struct blame_line_tracker *line_blames;
+	int entry_len, nr_lines, i;
+
+	line_blames = xcalloc(sizeof(struct blame_line_tracker),
+			      e->num_lines);
+	guess_line_blames(e, parent, target, offset, parent_slno, parent_len,
+			  line_blames);
+	/*
+	 * We carve new entries off the front of e.  Each entry comes from a
+	 * contiguous chunk of lines: adjacent lines from the same origin
+	 * (either the parent or the target).
+	 */
+	entry_len = 1;
+	nr_lines = e->num_lines;	// e changes in the loop
+	for (i = 0; i < nr_lines; i++) {
+		struct blame_entry *next = NULL;
+
+		/*
+		 * We are often adjacent to the next line - only split the blame
+		 * entry when we have to.
+		 */
+		if (i + 1 < nr_lines) {
+			if (are_lines_adjacent(&line_blames[i],
+					       &line_blames[i + 1])) {
+				entry_len++;
+				continue;
+			}
+			next = split_blame_at(e, entry_len,
+					      blame_origin_incref(e->suspect));
+		}
+		if (line_blames[i].is_parent) {
+			blame_origin_decref(e->suspect);
+			e->suspect = blame_origin_incref(parent);
+			e->s_lno = line_blames[i - entry_len + 1].s_lno;
+			e->next = *ignoredp;
+			*ignoredp = e;
+		} else {
+			e->unblamable = 1;
+			/* e->s_lno is already in the target's address space. */
+			e->next = *diffp;
+			*diffp = e;
+		}
+		assert(e->num_lines == entry_len);
+		e = next;
+		entry_len = 1;
+	}
+	assert(!e);
+	free(line_blames);
+}
+
 /*
  * Process one hunk from the patch between the current suspect for
  * blame_entry e and its parent.  This first blames any unfinished
@@ -869,13 +978,19 @@ static struct blame_entry *split_blame_at(struct blame_entry *e, int len,
  * -C options may lead to overlapping/duplicate source line number
  * ranges, all we can rely on from sorting/merging is the order of the
  * first suspect line number.
+ *
+ * tlno: line number in the target where this chunk begins
+ * same: line number in the target where this chunk ends
+ * offset: add to tlno to get the chunk starting point in the parent
+ * parent_len: number of lines in the parent chunk
  */
 static void blame_chunk(struct blame_entry ***dstq, struct blame_entry ***srcq,
-			int tlno, int offset, int same,
-			struct blame_origin *parent)
+			int tlno, int offset, int same, int parent_len,
+			struct blame_origin *parent,
+			struct blame_origin *target, int ignore_diffs)
 {
 	struct blame_entry *e = **srcq;
-	struct blame_entry *samep = NULL, *diffp = NULL;
+	struct blame_entry *samep = NULL, *diffp = NULL, *ignoredp = NULL;
 
 	while (e && e->s_lno < tlno) {
 		struct blame_entry *next = e->next;
@@ -943,10 +1058,29 @@ static void blame_chunk(struct blame_entry ***dstq, struct blame_entry ***srcq,
 			n->next = samep;
 			samep = n;
 		}
-		e->next = diffp;
-		diffp = e;
+		if (ignore_diffs) {
+			ignore_blame_entry(e, parent, target, offset,
+					   tlno + offset, parent_len, &diffp,
+					   &ignoredp);
+		} else {
+			e->next = diffp;
+			diffp = e;
+		}
 		e = next;
 	}
+	if (ignoredp) {
+		/*
+		 * Note ignoredp is not sorted yet, and thus neither is dstq.
+		 * That list must be sorted before we queue_blames().  We defer
+		 * sorting until after all diff hunks are processed, so that
+		 * guess_line_blames() can pick *any* line in the parent.  The
+		 * slight drawback is that we end up sorting all blame entries
+		 * passed to the parent, including those that are unrelated to
+		 * changes made by the ignored commit.
+		 */
+		**dstq = reverse_blame(ignoredp, **dstq);
+		*dstq = &ignoredp->next;
+	}
 	**srcq = reverse_blame(diffp, reverse_blame(samep, e));
 	/* Move across elements that are in the unblamable portion */
 	if (diffp)
@@ -955,7 +1089,9 @@ static void blame_chunk(struct blame_entry ***dstq, struct blame_entry ***srcq,
 
 struct blame_chunk_cb_data {
 	struct blame_origin *parent;
+	struct blame_origin *target;
 	long offset;
+	int ignore_diffs;
 	struct blame_entry **dstq;
 	struct blame_entry **srcq;
 };
@@ -968,7 +1104,8 @@ static int blame_chunk_cb(long start_a, long count_a,
 	if (start_a - start_b != d->offset)
 		die("internal error in blame::blame_chunk_cb");
 	blame_chunk(&d->dstq, &d->srcq, start_b, start_a - start_b,
-		    start_b + count_b, d->parent);
+		    start_b + count_b, count_a, d->parent, d->target,
+		    d->ignore_diffs);
 	d->offset = start_a + count_a - (start_b + count_b);
 	return 0;
 }
@@ -980,7 +1117,7 @@ static int blame_chunk_cb(long start_a, long count_a,
  */
 static void pass_blame_to_parent(struct blame_scoreboard *sb,
 				 struct blame_origin *target,
-				 struct blame_origin *parent)
+				 struct blame_origin *parent, int ignore_diffs)
 {
 	mmfile_t file_p, file_o;
 	struct blame_chunk_cb_data d;
@@ -990,7 +1127,9 @@ static void pass_blame_to_parent(struct blame_scoreboard *sb,
 		return; /* nothing remains for this target */
 
 	d.parent = parent;
+	d.target = target;
 	d.offset = 0;
+	d.ignore_diffs = ignore_diffs;
 	d.dstq = &newdest; d.srcq = &target->suspects;
 
 	fill_origin_blob(&sb->revs->diffopt, parent, &file_p, &sb->num_read_blob);
@@ -1002,8 +1141,13 @@ static void pass_blame_to_parent(struct blame_scoreboard *sb,
 		    oid_to_hex(&parent->commit->object.oid),
 		    oid_to_hex(&target->commit->object.oid));
 	/* The rest are the same as the parent */
-	blame_chunk(&d.dstq, &d.srcq, INT_MAX, d.offset, INT_MAX, parent);
+	blame_chunk(&d.dstq, &d.srcq, INT_MAX, d.offset, INT_MAX, 0,
+		    parent, target, 0);
 	*d.dstq = NULL;
+	if (ignore_diffs)
+		newdest = llist_mergesort(newdest, get_next_blame,
+					  set_next_blame,
+					  compare_blame_suspect);
 	queue_blames(sb, parent, newdest);
 
 	return;
@@ -1507,11 +1651,28 @@ static void pass_blame(struct blame_scoreboard *sb, struct blame_origin *origin,
 			blame_origin_incref(porigin);
 			origin->previous = porigin;
 		}
-		pass_blame_to_parent(sb, origin, porigin);
+		pass_blame_to_parent(sb, origin, porigin, 0);
 		if (!origin->suspects)
 			goto finish;
 	}
 
+	/*
+	 * Pass remaining suspects for ignored commits to their parents.
+	 */
+	if (oidset_contains(&sb->ignore_list, &commit->object.oid)) {
+		for (i = 0, sg = first_scapegoat(revs, commit, sb->reverse);
+		     i < num_sg && sg;
+		     sg = sg->next, i++) {
+			struct blame_origin *porigin = sg_origin[i];
+
+			if (!porigin)
+				continue;
+			pass_blame_to_parent(sb, origin, porigin, 1);
+			if (!origin->suspects)
+				goto finish;
+		}
+	}
+
 	/*
 	 * Optionally find moves in parents' files.
 	 */
diff --git a/blame.h b/blame.h
index be3a895043e0..91664913d7c4 100644
--- a/blame.h
+++ b/blame.h
@@ -92,6 +92,7 @@ struct blame_entry {
 	 * scanning the lines over and over.
 	 */
 	unsigned score;
+	int unblamable;
 };
 
 /*
@@ -117,6 +118,8 @@ struct blame_scoreboard {
 	/* linked list of blames */
 	struct blame_entry *ent;
 
+	struct oidset ignore_list;
+
 	/* look-up a line in the final buffer */
 	int num_lines;
 	int *lineno;
diff --git a/builtin/blame.c b/builtin/blame.c
index 177c1022a0c4..b48842d8459b 100644
--- a/builtin/blame.c
+++ b/builtin/blame.c
@@ -52,6 +52,7 @@ static int no_whole_file_rename;
 static int show_progress;
 static char repeated_meta_color[COLOR_MAXLEN];
 static int coloring_mode;
+static struct string_list ignore_revs_file_list = STRING_LIST_INIT_NODUP;
 
 static struct date_mode blame_date_mode = { DATE_ISO8601 };
 static size_t blame_date_width;
@@ -346,6 +347,8 @@ static void emit_porcelain(struct blame_scoreboard *sb, struct blame_entry *ent,
 	char hex[GIT_MAX_HEXSZ + 1];
 
 	oid_to_hex_r(hex, &suspect->commit->object.oid);
+	if (ent->unblamable)
+		memset(hex, '0', strlen(hex));
 	printf("%s %d %d %d\n",
 	       hex,
 	       ent->s_lno + 1,
@@ -479,6 +482,8 @@ static void emit_other(struct blame_scoreboard *sb, struct blame_entry *ent, int
 			}
 		}
 
+		if (ent->unblamable)
+			memset(hex, '0', length);
 		printf("%.*s", length, hex);
 		if (opt & OUTPUT_ANNOTATE_COMPAT) {
 			const char *name;
@@ -695,6 +700,16 @@ static int git_blame_config(const char *var, const char *value, void *cb)
 		parse_date_format(value, &blame_date_mode);
 		return 0;
 	}
+	if (!strcmp(var, "blame.ignorerevsfile")) {
+		const char *str;
+		int ret;
+
+		ret = git_config_pathname(&str, var, value);
+		if (ret)
+			return ret;
+		string_list_insert(&ignore_revs_file_list, str);
+		return 0;
+	}
 	if (!strcmp(var, "color.blame.repeatedlines")) {
 		if (color_parse_mem(value, strlen(value), repeated_meta_color))
 			warning(_("invalid color '%s' in color.blame.repeatedLines"),
@@ -774,6 +789,27 @@ static int is_a_rev(const char *name)
 	return OBJ_NONE < oid_object_info(the_repository, &oid, NULL);
 }
 
+static void build_ignorelist(struct blame_scoreboard *sb,
+			     struct string_list *ignore_revs_file_list,
+			     struct string_list *ignore_rev_list)
+{
+	struct string_list_item *i;
+	struct object_id oid;
+
+	oidset_init(&sb->ignore_list, 0);
+	for_each_string_list_item(i, ignore_revs_file_list) {
+		if (!strcmp(i->string, ""))
+			oidset_clear(&sb->ignore_list);
+		else
+			oidset_parse_file(&sb->ignore_list, i->string);
+	}
+	for_each_string_list_item(i, ignore_rev_list) {
+		if (get_oid_committish(i->string, &oid))
+			die(_("Cannot find revision %s to ignore"), i->string);
+		oidset_insert(&sb->ignore_list, &oid);
+	}
+}
+
 int cmd_blame(int argc, const char **argv, const char *prefix)
 {
 	struct rev_info revs;
@@ -785,6 +821,7 @@ int cmd_blame(int argc, const char **argv, const char *prefix)
 	struct progress_info pi = { NULL, 0 };
 
 	struct string_list range_list = STRING_LIST_INIT_NODUP;
+	struct string_list ignore_rev_list = STRING_LIST_INIT_NODUP;
 	int output_option = 0, opt = 0;
 	int show_stats = 0;
 	const char *revs_file = NULL;
@@ -806,6 +843,8 @@ int cmd_blame(int argc, const char **argv, const char *prefix)
 		OPT_BIT('s', NULL, &output_option, N_("Suppress author name and timestamp (Default: off)"), OUTPUT_NO_AUTHOR),
 		OPT_BIT('e', "show-email", &output_option, N_("Show author email instead of name (Default: off)"), OUTPUT_SHOW_EMAIL),
 		OPT_BIT('w', NULL, &xdl_opts, N_("Ignore whitespace differences"), XDF_IGNORE_WHITESPACE),
+		OPT_STRING_LIST(0, "ignore-rev", &ignore_rev_list, N_("rev"), N_("Ignore <rev> when blaming")),
+		OPT_STRING_LIST(0, "ignore-revs-file", &ignore_revs_file_list, N_("file"), N_("Ignore revisions from <file>")),
 		OPT_BIT(0, "color-lines", &output_option, N_("color redundant metadata from previous line differently"), OUTPUT_COLOR_LINE),
 		OPT_BIT(0, "color-by-age", &output_option, N_("color lines by age"), OUTPUT_SHOW_AGE_WITH_COLOR),
 
@@ -999,6 +1038,9 @@ int cmd_blame(int argc, const char **argv, const char *prefix)
 	sb.contents_from = contents_from;
 	sb.reverse = reverse;
 	sb.repo = the_repository;
+	build_ignorelist(&sb, &ignore_revs_file_list, &ignore_rev_list);
+	string_list_clear(&ignore_revs_file_list, 0);
+	string_list_clear(&ignore_rev_list, 0);
 	setup_scoreboard(&sb, path, &o);
 	lno = sb.num_lines;
 
diff --git a/t/t8013-blame-ignore-revs.sh b/t/t8013-blame-ignore-revs.sh
new file mode 100755
index 000000000000..df4993f98682
--- /dev/null
+++ b/t/t8013-blame-ignore-revs.sh
@@ -0,0 +1,168 @@
+#!/bin/sh
+
+test_description='ignore revisions when blaming'
+. ./test-lib.sh
+
+# Creates:
+# 	A--B--X
+# A added line 1 and B added line 2.  X makes changes to those lines.  Sanity
+# check that X is blamed for both lines.
+test_expect_success setup '
+	test_commit A file line1 &&
+
+	echo line2 >>file &&
+	git add file &&
+	test_tick &&
+	git commit -m B &&
+	git tag B &&
+
+	test_write_lines line-one line-two >file &&
+	git add file &&
+	test_tick &&
+	git commit -m X &&
+	git tag X &&
+
+	git blame --line-porcelain file >blame_raw &&
+
+	grep "^[0-9a-f]\+ [0-9]\+ 1" blame_raw | sed -e "s/ .*//" >actual &&
+	git rev-parse X >expect &&
+	test_cmp expect actual &&
+
+	grep "^[0-9a-f]\+ [0-9]\+ 2" blame_raw | sed -e "s/ .*//" >actual &&
+	git rev-parse X >expect &&
+	test_cmp expect actual
+	'
+
+# Ignore X, make sure A is blamed for line 1 and B for line 2.
+test_expect_success ignore_rev_changing_lines '
+	git blame --line-porcelain --ignore-rev X file >blame_raw &&
+
+	grep "^[0-9a-f]\+ [0-9]\+ 1" blame_raw | sed -e "s/ .*//" >actual &&
+	git rev-parse A >expect &&
+	test_cmp expect actual &&
+
+	grep "^[0-9a-f]\+ [0-9]\+ 2" blame_raw | sed -e "s/ .*//" >actual &&
+	git rev-parse B >expect &&
+	test_cmp expect actual
+	'
+
+# For ignored revs that have added 'unblamable' lines, blame those lines on an
+# all-zeros rev.
+# 	A--B--X--Y
+# Where Y changes lines 1 and 2, and adds lines 3 and 4.  The added lines ought
+# to have nothing in common with "line-one" or "line-two", to keep any
+# heuristics from matching them with any lines in the parent.
+test_expect_success ignore_rev_adding_unblamable_lines '
+	test_write_lines line-one-change line-two-changed y3 y4 >file &&
+	git add file &&
+	test_tick &&
+	git commit -m Y &&
+	git tag Y &&
+
+	git rev-parse Y >y_rev &&
+	sed -e "s/[0-9a-f]/0/g" y_rev >expect &&
+	git blame --line-porcelain file --ignore-rev Y >blame_raw &&
+
+	grep "^[0-9a-f]\+ [0-9]\+ 3" blame_raw | sed -e "s/ .*//" >actual &&
+	test_cmp expect actual &&
+
+	grep "^[0-9a-f]\+ [0-9]\+ 4" blame_raw | sed -e "s/ .*//" >actual &&
+	test_cmp expect actual
+	'
+
+# Ignore X and Y, both in separate files.  Lines 1 == A, 2 == B.
+test_expect_success ignore_revs_from_files '
+	git rev-parse X >ignore_x &&
+	git rev-parse Y >ignore_y &&
+	git blame --line-porcelain file --ignore-revs-file ignore_x --ignore-revs-file ignore_y >blame_raw &&
+
+	grep "^[0-9a-f]\+ [0-9]\+ 1" blame_raw | sed -e "s/ .*//" >actual &&
+	git rev-parse A >expect &&
+	test_cmp expect actual &&
+
+	grep "^[0-9a-f]\+ [0-9]\+ 2" blame_raw | sed -e "s/ .*//" >actual &&
+	git rev-parse B >expect &&
+	test_cmp expect actual
+	'
+
+# Ignore X from the config option, Y from a file.
+test_expect_success ignore_revs_from_configs_and_files '
+	git config --add blame.ignoreRevsFile ignore_x &&
+	git blame --line-porcelain file --ignore-revs-file ignore_y >blame_raw &&
+
+	grep "^[0-9a-f]\+ [0-9]\+ 1" blame_raw | sed -e "s/ .*//" >actual &&
+	git rev-parse A >expect &&
+	test_cmp expect actual &&
+
+	grep "^[0-9a-f]\+ [0-9]\+ 2" blame_raw | sed -e "s/ .*//" >actual &&
+	git rev-parse B >expect &&
+	test_cmp expect actual
+	'
+
+# Override blame.ignoreRevsFile (ignore_x) with an empty string.  X should be
+# blamed now for lines 1 and 2, since we are no longer ignoring X.
+test_expect_success override_ignore_revs_file '
+	git blame --line-porcelain file --ignore-revs-file "" --ignore-revs-file ignore_y >blame_raw &&
+	git rev-parse X >expect &&
+
+	grep "^[0-9a-f]\+ [0-9]\+ 1" blame_raw | sed -e "s/ .*//" >actual &&
+	test_cmp expect actual &&
+
+	grep "^[0-9a-f]\+ [0-9]\+ 2" blame_raw | sed -e "s/ .*//" >actual &&
+	test_cmp expect actual
+	'
+test_expect_success bad_files_and_revs '
+	test_must_fail git blame file --ignore-rev NOREV 2>err &&
+	test_i18ngrep "Cannot find revision NOREV to ignore" err &&
+
+	test_must_fail git blame file --ignore-revs-file NOFILE 2>err &&
+	test_i18ngrep "Could not open object name list: NOFILE" err &&
+
+	echo NOREV >ignore_norev &&
+	test_must_fail git blame file --ignore-revs-file ignore_norev 2>err &&
+	test_i18ngrep "Invalid object name: NOREV" err
+	'
+
+# Resetting the repo and creating:
+#
+# A--B--M
+#  \   /
+#   C-+
+#
+# 'A' creates a file.  B changes line 1, and C changes line 9.  M merges.
+test_expect_success ignore_merge '
+	rm -rf .git/ &&
+	git init &&
+
+	test_write_lines L1 L2 L3 L4 L5 L6 L7 L8 L9 >file &&
+	git add file &&
+	test_tick &&
+	git commit -m A &&
+	git tag A &&
+
+	test_write_lines BB L2 L3 L4 L5 L6 L7 L8 L9 >file &&
+	git add file &&
+	test_tick &&
+	git commit -m B &&
+	git tag B &&
+
+	git reset --hard A &&
+	test_write_lines L1 L2 L3 L4 L5 L6 L7 L8 CC >file &&
+	git add file &&
+	test_tick &&
+	git commit -m C &&
+	git tag C &&
+
+	test_merge M B &&
+	git blame --line-porcelain file --ignore-rev M >blame_raw &&
+
+	grep "^[0-9a-f]\+ [0-9]\+ 1" blame_raw | sed -e "s/ .*//" >actual &&
+	git rev-parse B >expect &&
+	test_cmp expect actual &&
+
+	grep "^[0-9a-f]\+ [0-9]\+ 9" blame_raw | sed -e "s/ .*//" >actual &&
+	git rev-parse C >expect &&
+	test_cmp expect actual
+	'
+
+test_done
-- 
2.21.0.392.gf8f6787159e-goog

Re: [PATCH v6 3/6] blame: add the ability to ignore commits and their changes

[Ævar Arnfjörð Bjarmason]

On Wed, Apr 10 2019, Barret Rhoden wrote:

(Just skimming)

> revisions for commits that perform mass reformatting, and their users
> have the optional to ignore all of the commits in that file.

s/have the optional/have the option/

> +--ignore-revs-file <file>::
> +	Ignore revisions listed in `file`, one unabbreviated object name per line.
> +	Whitespace and comments beginning with `#` are ignored.

Maybe just say "Ignore revisions listed in `file`, which is expected to
be in the same format as an `fsck.skipList`.".

> +	the `blame.ignoreRevsFile` config option.  An empty file name, `""`, will
> +	clear the list of revs from previously processed files.

Maybe I haven't read this carefully enough but the use-case for this
doesn't seem to be explained, you need this for the option, but the
config file too? If I want to override fsck.skipList I do
`fsck.skipList=/dev/zero`. Isn't that enough for this use-case without
introducing config state-machine magic?

> +	split[0].unblamable = e->unblamable;
> +	split[1].unblamable = e->unblamable;
> +	split[2].unblamable = e->unblamable;

I wonder what the comfort level for people in general is before turning
this sort of thing into a for-loop, 4? :)

> +	nr_lines = e->num_lines;	// e changes in the loop

A C++-like trailing comment.

> +	grep "^[0-9a-f]\+ [0-9]\+ 1" blame_raw | sed -e "s/ .*//" >actual &&
> +	git rev-parse X >expect &&
> +	test_cmp expect actual &&
> +
> +	grep "^[0-9a-f]\+ [0-9]\+ 2" blame_raw | sed -e "s/ .*//" >actual &&
> +	git rev-parse X >expect &&
> +	test_cmp expect actual

The grep here is a bug. See my 4abf20f004 ("tests: fix unportable "\?"
and "\+" regex syntax", 2019-02-21).

Re: [PATCH v6 3/6] blame: add the ability to ignore commits and their changes

[Michael Platings]

> > +     the `blame.ignoreRevsFile` config option.  An empty file name, `""`, will
> > +     clear the list of revs from previously processed files.
>
> Maybe I haven't read this carefully enough but the use-case for this
> doesn't seem to be explained, you need this for the option, but the
> config file too? If I want to override fsck.skipList I do
> `fsck.skipList=/dev/zero`. Isn't that enough for this use-case without
> introducing config state-machine magic?

The difference between blame.ignoreRevsFile and fsck.skipList is that
ignoreRevsFile can be specified repeatedly. This is useful if you have
one file listing reformatting commits, another listing renaming
commits etc. Or maybe a checked-in list of commits to ignore, and a
personal list of commits to ignore. However sometimes you're going to
want to *not* ignore those commits, so you need a way to discard the
previously specified options. To accommodate all operating systems an
empty string seems the best way to do this.

Re: [PATCH v6 3/6] blame: add the ability to ignore commits and their changes

[Barret Rhoden]

On 4/14/19 6:42 AM, Michael Platings wrote:
>>> +     the `blame.ignoreRevsFile` config option.  An empty file name, `""`, will
>>> +     clear the list of revs from previously processed files.
>>
>> Maybe I haven't read this carefully enough but the use-case for this
>> doesn't seem to be explained, you need this for the option, but the
>> config file too? If I want to override fsck.skipList I do
>> `fsck.skipList=/dev/zero`. Isn't that enough for this use-case without
>> introducing config state-machine magic?
> 
> The difference between blame.ignoreRevsFile and fsck.skipList is that
> ignoreRevsFile can be specified repeatedly. This is useful if you have
> one file listing reformatting commits, another listing renaming
> commits etc. Or maybe a checked-in list of commits to ignore, and a
> personal list of commits to ignore. However sometimes you're going to
> want to *not* ignore those commits, so you need a way to discard the
> previously specified options. To accommodate all operating systems an
> empty string seems the best way to do this.
> 

In a previous round of reviews[1], this style was recommended.  It's 
based on what credential.helper does.

The main thing I've been using the --ignore-revs-file="" for is to turn 
off my default ignore list for debugging.  =)

Thanks,

Barret


[1] 
https://public-inbox.org/git/nycvar.QRO.7.76.6.1901181038540.41@tvgsbejvaqbjf.bet/

Re: [PATCH v6 3/6] blame: add the ability to ignore commits and their changes

[Barret Rhoden]

On 4/10/19 3:00 PM, Ævar Arnfjörð Bjarmason wrote:
[snip]

>> +	split[0].unblamable = e->unblamable;
>> +	split[1].unblamable = e->unblamable;
>> +	split[2].unblamable = e->unblamable;
> 
> I wonder what the comfort level for people in general is before turning
> this sort of thing into a for-loop, 4? :)

4 sounds good to me.  =)

>> +	nr_lines = e->num_lines;	// e changes in the loop
> 
> A C++-like trailing comment.
> 
>> +	grep "^[0-9a-f]\+ [0-9]\+ 1" blame_raw | sed -e "s/ .*//" >actual &&
>> +	git rev-parse X >expect &&
>> +	test_cmp expect actual &&
>> +
>> +	grep "^[0-9a-f]\+ [0-9]\+ 2" blame_raw | sed -e "s/ .*//" >actual &&
>> +	git rev-parse X >expect &&
>> +	test_cmp expect actual
> 
> The grep here is a bug. See my 4abf20f004 ("tests: fix unportable "\?"
> and "\+" regex syntax", 2019-02-21).

Thanks - will fix up this stuff in the next round.

[PATCH v6 4/6] blame: add config options to handle output for ignored lines

[Barret Rhoden]

When ignoring commits, the commit that is blamed might not be
responsible for the change.  Users might want to know when a particular
line has a potentially inaccurate blame.  Furthermore, they might never
want to see the object hash of an ignored commit.

This patch adds two config options to control the output behavior.

The first option can identify ignored lines by specifying
blame.markIgnoredFiles.  When this option is set, each blame line is
marked with an '*'.

For example:
	278b6158d6fdb (Barret Rhoden  2016-04-11 13:57:54 -0400 26)
appears as:
	*278b6158d6fd (Barret Rhoden  2016-04-11 13:57:54 -0400 26)

where the '*' is placed before the commit, and the hash has one fewer
characters.

Sometimes we are unable to even guess at what commit touched a line.
These lines are 'unblamable.'  The second option,
blame.maskIgnoredUnblamables, will zero the hash of any unblamable line.

For example, say we ignore e5e8d36d04cbe:
	e5e8d36d04cbe (Barret Rhoden  2016-04-11 13:57:54 -0400 26)
appears as:
	0000000000000 (Barret Rhoden  2016-04-11 13:57:54 -0400 26)

Signed-off-by: Barret Rhoden <brho@google.com>
---
 Documentation/blame-options.txt |  6 +++++-
 Documentation/config/blame.txt  |  9 +++++++++
 blame.c                         |  4 ++++
 blame.h                         |  1 +
 builtin/blame.c                 | 18 +++++++++++++++--
 t/t8013-blame-ignore-revs.sh    | 34 +++++++++++++++++++++++++++++++++
 6 files changed, 69 insertions(+), 3 deletions(-)

diff --git a/Documentation/blame-options.txt b/Documentation/blame-options.txt
index 8f155196c6fe..e7b8b5e4b87b 100644
--- a/Documentation/blame-options.txt
+++ b/Documentation/blame-options.txt
@@ -115,7 +115,11 @@ take effect.
 	change never happened.  Lines that were changed or added by an ignored
 	commit will be blamed on the previous commit that changed that line or
 	nearby lines.  This option may be specified multiple times to ignore
-	more than one revision.
+	more than one revision.  If the `blame.markIgnoredLines` config option
+	is set, then lines that were changed by an ignored commit will be
+	marked with a `*` in the blame output.  If the
+	`blame.maskIgnoredUnblamables` config option is set, then those lines that
+	we could not attribute to another revision are outputted as all zeros.
 
 --ignore-revs-file <file>::
 	Ignore revisions listed in `file`, one unabbreviated object name per line.
diff --git a/Documentation/config/blame.txt b/Documentation/config/blame.txt
index 4da2788f306d..bb6674227da1 100644
--- a/Documentation/config/blame.txt
+++ b/Documentation/config/blame.txt
@@ -26,3 +26,12 @@ blame.ignoreRevsFile::
 	`#` are ignored.  This option may be repeated multiple times.  Empty
 	file names will reset the list of ignored revisions.  This option will
 	be handled before the command line option `--ignore-revs-file`.
+
+blame.maskIgnoredUnblamables::
+	Output an object hash of all zeros for lines that were changed by an ignored
+	revision and that we could not attribute to another revision in the output
+	of linkgit:git-blame[1].
+
+blame.markIgnoredLines::
+	Mark lines that were changed by an ignored revision with a '*' in the
+	output of linkgit:git-blame[1].
diff --git a/blame.c b/blame.c
index 0bbb86ad5985..a98ae00e2cfc 100644
--- a/blame.c
+++ b/blame.c
@@ -481,6 +481,7 @@ void blame_coalesce(struct blame_scoreboard *sb)
 	for (ent = sb->ent; ent && (next = ent->next); ent = next) {
 		if (ent->suspect == next->suspect &&
 		    ent->s_lno + ent->num_lines == next->s_lno &&
+		    ent->ignored == next->ignored &&
 		    ent->unblamable == next->unblamable) {
 			ent->num_lines += next->num_lines;
 			ent->next = next->next;
@@ -733,6 +734,7 @@ static void split_overlap(struct blame_entry *split,
 	int chunk_end_lno;
 	memset(split, 0, sizeof(struct blame_entry [3]));
 
+	split[0].ignored = split[1].ignored = split[2].ignored = e->ignored;
 	split[0].unblamable = e->unblamable;
 	split[1].unblamable = e->unblamable;
 	split[2].unblamable = e->unblamable;
@@ -857,6 +859,7 @@ static struct blame_entry *split_blame_at(struct blame_entry *e, int len,
 	struct blame_entry *n = xcalloc(1, sizeof(struct blame_entry));
 
 	n->suspect = new_suspect;
+	n->ignored = e->ignored;
 	n->unblamable = e->unblamable;
 	n->lno = e->lno + len;
 	n->s_lno = e->s_lno + len;
@@ -922,6 +925,7 @@ static void ignore_blame_entry(struct blame_entry *e,
 	struct blame_line_tracker *line_blames;
 	int entry_len, nr_lines, i;
 
+	e->ignored = 1;
 	line_blames = xcalloc(sizeof(struct blame_line_tracker),
 			      e->num_lines);
 	guess_line_blames(e, parent, target, offset, parent_slno, parent_len,
diff --git a/blame.h b/blame.h
index 91664913d7c4..53df8b4c5b3f 100644
--- a/blame.h
+++ b/blame.h
@@ -92,6 +92,7 @@ struct blame_entry {
 	 * scanning the lines over and over.
 	 */
 	unsigned score;
+	int ignored;
 	int unblamable;
 };
 
diff --git a/builtin/blame.c b/builtin/blame.c
index b48842d8459b..c10a6a802240 100644
--- a/builtin/blame.c
+++ b/builtin/blame.c
@@ -53,6 +53,8 @@ static int show_progress;
 static char repeated_meta_color[COLOR_MAXLEN];
 static int coloring_mode;
 static struct string_list ignore_revs_file_list = STRING_LIST_INIT_NODUP;
+static int mask_ignored_unblamables;
+static int mark_ignored_lines;
 
 static struct date_mode blame_date_mode = { DATE_ISO8601 };
 static size_t blame_date_width;
@@ -347,7 +349,7 @@ static void emit_porcelain(struct blame_scoreboard *sb, struct blame_entry *ent,
 	char hex[GIT_MAX_HEXSZ + 1];
 
 	oid_to_hex_r(hex, &suspect->commit->object.oid);
-	if (ent->unblamable)
+	if (mask_ignored_unblamables && ent->unblamable)
 		memset(hex, '0', strlen(hex));
 	printf("%s %d %d %d\n",
 	       hex,
@@ -482,7 +484,11 @@ static void emit_other(struct blame_scoreboard *sb, struct blame_entry *ent, int
 			}
 		}
 
-		if (ent->unblamable)
+		if (mark_ignored_lines && ent->ignored) {
+			length--;
+			putchar('*');
+		}
+		if (mask_ignored_unblamables && ent->unblamable)
 			memset(hex, '0', length);
 		printf("%.*s", length, hex);
 		if (opt & OUTPUT_ANNOTATE_COMPAT) {
@@ -710,6 +716,14 @@ static int git_blame_config(const char *var, const char *value, void *cb)
 		string_list_insert(&ignore_revs_file_list, str);
 		return 0;
 	}
+	if (!strcmp(var, "blame.maskignoredunblamables")) {
+		mask_ignored_unblamables = git_config_bool(var, value);
+		return 0;
+	}
+	if (!strcmp(var, "blame.markignoredlines")) {
+		mark_ignored_lines = git_config_bool(var, value);
+		return 0;
+	}
 	if (!strcmp(var, "color.blame.repeatedlines")) {
 		if (color_parse_mem(value, strlen(value), repeated_meta_color))
 			warning(_("invalid color '%s' in color.blame.repeatedLines"),
diff --git a/t/t8013-blame-ignore-revs.sh b/t/t8013-blame-ignore-revs.sh
index df4993f98682..cc049a390b0d 100755
--- a/t/t8013-blame-ignore-revs.sh
+++ b/t/t8013-blame-ignore-revs.sh
@@ -53,6 +53,7 @@ test_expect_success ignore_rev_changing_lines '
 # to have nothing in common with "line-one" or "line-two", to keep any
 # heuristics from matching them with any lines in the parent.
 test_expect_success ignore_rev_adding_unblamable_lines '
+	git config --add blame.maskIgnoredUnblamables true &&
 	test_write_lines line-one-change line-two-changed y3 y4 >file &&
 	git add file &&
 	test_tick &&
@@ -123,6 +124,39 @@ test_expect_success bad_files_and_revs '
 	test_i18ngrep "Invalid object name: NOREV" err
 	'
 
+# Commit Z will touch the first two lines.  Y touched all four.
+# 	A--B--X--Y--Z
+# The blame output when ignoring Z should be:
+# ^Y ... 1)
+# ^Y ... 2)
+# Y  ... 3)
+# Y  ... 4)
+# We're checking only the first character
+test_expect_success mark_ignored_lines '
+	git config --add blame.markIgnoredLines true &&
+
+	test_write_lines line-one-Z line-two-Z y3 y4 >file &&
+	git add file &&
+	test_tick &&
+	git commit -m Z &&
+	git tag Z &&
+
+	git blame --ignore-rev Z file >blame_raw &&
+	echo "*" >expect &&
+
+	sed -n "1p" blame_raw | cut -c1 >actual &&
+	test_cmp expect actual &&
+
+	sed -n "2p" blame_raw | cut -c1 >actual &&
+	test_cmp expect actual &&
+
+	sed -n "3p" blame_raw | cut -c1 >actual &&
+	! test_cmp expect actual &&
+
+	sed -n "4p" blame_raw | cut -c1 >actual &&
+	! test_cmp expect actual
+	'
+
 # Resetting the repo and creating:
 #
 # A--B--M
-- 
2.21.0.392.gf8f6787159e-goog

Re: [PATCH v6 4/6] blame: add config options to handle output for ignored lines

[Junio C Hamano]

Barret Rhoden <brho@google.com> writes:

> Sometimes we are unable to even guess at what commit touched a line.
> These lines are 'unblamable.'  The second option,
> blame.maskIgnoredUnblamables, will zero the hash of any unblamable line.
>
> For example, say we ignore e5e8d36d04cbe:
> 	e5e8d36d04cbe (Barret Rhoden  2016-04-11 13:57:54 -0400 26)
> appears as:
> 	0000000000000 (Barret Rhoden  2016-04-11 13:57:54 -0400 26)

Wouldn't this make it impossible to tell between what's done by such
a commit that was marked to be ignored, and what's done locally only
in the working tree, which the users have long accustomed to see
with the ^0*$ object name?  I think it would make a lot more sense
to show the object name of the "ignored" commit, which would be
recognizable by the user who fed such an object name to the command
in the first place.  Alternatively, perhaps the same idea as replacing
one of the hexdigits with '*' used by the other configuration can be
applied to this as well?

Re: [PATCH v6 4/6] blame: add config options to handle output for ignored lines

[Michael Platings]

On Sun, 14 Apr 2019 at 04:45, Junio C Hamano <gitster@pobox.com> wrote:
> Wouldn't this make it impossible to tell between what's done by such
> a commit that was marked to be ignored, and what's done locally only
> in the working tree, which the users have long accustomed to see
> with the ^0*$ object name?  I think it would make a lot more sense
> to show the object name of the "ignored" commit, which would be
> recognizable by the user who fed such an object name to the command
> in the first place.  Alternatively, perhaps the same idea as replacing
> one of the hexdigits with '*' used by the other configuration can be
> applied to this as well?

I had the same objection to zeroing out hashes, but this option is off
by default so I think it's OK.
If you enable both blame.markIgnoredLines and
blame.maskIgnoredUnblamables then the hash does appear as
"*0000000000" like you suggest. I think it's appropriate that the '*'
is only added if you opt in with the markIgnoredLines option.

If you only enable blame.markIgnoredLines then the hash for
"unblamable" lines appears as e.g. "*3252488f5" - this doesn't seem
right to me because the commit *wasn't* ignored, it is in fact the
commit in which that line was added. I think '*' should denote "this
information may be inaccurate" as that's what a typical user needs to
be aware of. However given that "unblamable" lines tend to be either
empty or a single character I'm not going to insist :)

Re: [PATCH v6 4/6] blame: add config options to handle output for ignored lines

[Junio C Hamano]

Michael Platings <michael@platin.gs> writes:

> If you only enable blame.markIgnoredLines then the hash for
> "unblamable" lines appears as e.g. "*3252488f5" - this doesn't seem
> right to me because the commit *wasn't* ignored,

I think you misunderstood me.  I was merely suggesting to use the
approach to mark the line in a way other than using the NULLed out
object name that has been reserved for something totally different,
and hinting with "the same *idea*".

And that idea is not even original to this series; the "^" marker
that is used to say "the line is attributed to this commit, but that
may only be because you blamed with commit range A..B and we reached
the bottom of the range---if you dug further, you might find the
line originates from another commit" is the origin of the same idea,
and this topic borrows it and uses a different mark, i.e. '*', for
the "we are not certain---take this with grain of salt" mark.

If you ended up hitting the commit the user wanted to ignore,
perhaps you can find another character that is different from '^' or
'*' and use that, following the same idea.

That is what I meant.  So you shouldn't be worried about using the
same '*' making the result ambiguous.

By the way, a configuration only feature is something we usually do
not accept.  A feature must be guarded with --command-line-option
and then optionally can have a corresponding configuration once the
option proves to be useful enough that it becomes useful to be able
to say "in this repository (or to this user), the feature is on by
default".

Re: [PATCH v6 4/6] blame: add config options to handle output for ignored lines

[Michael Platings]

On Sun, 14 Apr 2019 at 11:24, Junio C Hamano <gitster@pobox.com> wrote:
> > If you only enable blame.markIgnoredLines then the hash for
> > "unblamable" lines appears as e.g. "*3252488f5" - this doesn't seem
> > right to me because the commit *wasn't* ignored,
>
> I think you misunderstood me.  I was merely suggesting to use the
> approach to mark the line in a way other than using the NULLed out
> object name that has been reserved for something totally different,
> and hinting with "the same *idea*".

Hi Junio, that paragraph wasn't targetted at yourself, more a comment
on the functionality as it exists in the latest patch series. Sorry
for not making that clear.

> the "^" marker
> that is used to say "the line is attributed to this commit, but that
> may only be because you blamed with commit range A..B and we reached
> the bottom of the range---if you dug further, you might find the
> line originates from another commit" is the origin of the same idea,
> and this topic borrows it and uses a different mark, i.e. '*', for
> the "we are not certain---take this with grain of salt" mark.

So it sounds like we have many types of blame to consider:

1) This commit is truly the last one to touch this line, and you
didn't ask to ignore it.
2) This commit is truly the last one to touch this line, but you asked
to ignore it (AKA "unblamable").
3) This commit is at the bottom of the range of commits (^)
4) The "true" commit was ignored but we guess this is the one you're
actually interested in (*)
5) The "true" commit was ignored and we've reached the bottom of the
range of commits (^*)?
6) This commit is at the bottom of the range of commits, and you asked
to ignore it.

> If you ended up hitting the commit the user wanted to ignore,
> perhaps you can find another character that is different from '^' or
> '*' and use that, following the same idea.

I personally don't find the "unblamable" lines interesting enough to
justify giving them a symbol. But if Barret strongly feels that such
lines should get a '*' then I won't fight it - these lines tend to be
as simple as "}".

> By the way, a configuration only feature is something we usually do
> not accept.  A feature must be guarded with --command-line-option
> and then optionally can have a corresponding configuration once the
> option proves to be useful enough that it becomes useful to be able
> to say "in this repository (or to this user), the feature is on by
> default".

In that case we definitely need a --mark-ignored-lines option to git
blame, and I would strongly prefer that we also keep the
blame.markIgnoredLines option as I for one will be switching it on.

Re: [PATCH v6 4/6] blame: add config options to handle output for ignored lines

[Barret Rhoden]

Hi -

On 4/14/19 7:27 AM, Michael Platings wrote:
> On Sun, 14 Apr 2019 at 11:24, Junio C Hamano <gitster@pobox.com> wrote:
>>> If you only enable blame.markIgnoredLines then the hash for
>>> "unblamable" lines appears as e.g. "*3252488f5" - this doesn't seem
>>> right to me because the commit *wasn't* ignored,
>>
>> I think you misunderstood me.  I was merely suggesting to use the
>> approach to mark the line in a way other than using the NULLed out
>> object name that has been reserved for something totally different,
>> and hinting with "the same *idea*".
> 
> Hi Junio, that paragraph wasn't targetted at yourself, more a comment
> on the functionality as it exists in the latest patch series. Sorry
> for not making that clear.
> 
>> the "^" marker
>> that is used to say "the line is attributed to this commit, but that
>> may only be because you blamed with commit range A..B and we reached
>> the bottom of the range---if you dug further, you might find the
>> line originates from another commit" is the origin of the same idea,
>> and this topic borrows it and uses a different mark, i.e. '*', for
>> the "we are not certain---take this with grain of salt" mark.
> 
> So it sounds like we have many types of blame to consider:
> 
> 1) This commit is truly the last one to touch this line, and you
> didn't ask to ignore it.
> 2) This commit is truly the last one to touch this line, but you asked
> to ignore it (AKA "unblamable").
> 3) This commit is at the bottom of the range of commits (^)
> 4) The "true" commit was ignored but we guess this is the one you're
> actually interested in (*)
> 5) The "true" commit was ignored and we've reached the bottom of the
> range of commits (^*)?
> 6) This commit is at the bottom of the range of commits, and you asked
> to ignore it.
> 
>> If you ended up hitting the commit the user wanted to ignore,
>> perhaps you can find another character that is different from '^' or
>> '*' and use that, following the same idea.
> 
> I personally don't find the "unblamable" lines interesting enough to
> justify giving them a symbol. But if Barret strongly feels that such
> lines should get a '*' then I won't fight it - these lines tend to be
> as simple as "}".

I'm fine with not zeroing the hash, so long as there's some way to mark it.

We could mark with another *, such that if we mark-ignored and 
mark-unblamable you get "**hash".  You can't have an unblamable that 
isn't from an ignored commit, so a single '*' has only one meaning, 
based on your config options.

If that works for you all, I can change this to markIgnoredUnblamables 
(instead of 'mask') in the next version.

>> By the way, a configuration only feature is something we usually do
>> not accept.  A feature must be guarded with --command-line-option
>> and then optionally can have a corresponding configuration once the
>> option proves to be useful enough that it becomes useful to be able
>> to say "in this repository (or to this user), the feature is on by
>> default".
> 
> In that case we definitely need a --mark-ignored-lines option to git
> blame, and I would strongly prefer that we also keep the
> blame.markIgnoredLines option as I for one will be switching it on.

I'd also keep this set.  I think the whole reason for these config 
options was that everyone has a different preference, but that 
preference rarely changes.  I don't want to have to type 
--mark-ignored-lines every time I run git blame.  If I had to, I'd have 
to alias git blame or something.

I think having config options for these sorts of things is fine, since 
we know already that for a given user+repo, we want the feature on (or 
off).  But if I have to remove it, then let me know.

Thanks,

Barret

[PATCH v6 5/6] blame: optionally track line fingerprints during fill_blame_origin()

[Barret Rhoden]

fill_blame_origin() is a convenient place to store data that we will use
throughout the lifetime of a blame_origin.  Some heuristics for
ignoring commits during a blame session can make use of this storage.
In particular, we will calculate a fingerprint for each line of a file
for blame_origins involved in an ignored commit.

In this commit, we only calculate the line_starts, reusing the existing
code from the scoreboard's line_starts.  In an upcoming commit, we will
actually compute the fingerprints.

This feature will be used when we attempt to pass blame entries to
parents when we "ignore" a commit.  Most uses of fill_blame_origin()
will not require this feature, hence the flag parameter.  Multiple calls
to fill_blame_origin() are idempotent, and any of them can request the
creation of the fingerprints structure.

Suggested-by: Michael Platings <michael@platin.gs>
Signed-off-by: Barret Rhoden <brho@google.com>
---
 blame.c | 95 +++++++++++++++++++++++++++++++++++++++------------------
 blame.h |  2 ++
 2 files changed, 67 insertions(+), 30 deletions(-)

diff --git a/blame.c b/blame.c
index a98ae00e2cfc..a42dff80b1a5 100644
--- a/blame.c
+++ b/blame.c
@@ -311,12 +311,63 @@ static int diff_hunks(mmfile_t *file_a, mmfile_t *file_b,
 	return xdi_diff(file_a, file_b, &xpp, &xecfg, &ecb);
 }
 
+static const char *get_next_line(const char *start, const char *end)
+{
+	const char *nl = memchr(start, '\n', end - start);
+
+	return nl ? nl + 1 : end;
+}
+
+static int find_line_starts(int **line_starts, const char *buf,
+			    unsigned long len)
+{
+	const char *end = buf + len;
+	const char *p;
+	int *lineno;
+	int num = 0;
+
+	for (p = buf; p < end; p = get_next_line(p, end))
+		num++;
+
+	ALLOC_ARRAY(*line_starts, num + 1);
+	lineno = *line_starts;
+
+	for (p = buf; p < end; p = get_next_line(p, end))
+		*lineno++ = p - buf;
+
+	*lineno = len;
+
+	return num;
+}
+
+static void fill_origin_fingerprints(struct blame_origin *o, mmfile_t *file)
+{
+	int *line_starts;
+
+	if (o->fingerprints)
+		return;
+	o->num_lines = find_line_starts(&line_starts, o->file.ptr,
+					o->file.size);
+	/* TODO: Will fill in fingerprints in a future commit */
+	o->fingerprints = xcalloc(sizeof(struct fingerprint), o->num_lines);
+	free(line_starts);
+}
+
+static void drop_origin_fingerprints(struct blame_origin *o)
+{
+	if (o->fingerprints) {
+		o->num_lines = 0;
+		FREE_AND_NULL(o->fingerprints);
+	}
+}
+
 /*
  * Given an origin, prepare mmfile_t structure to be used by the
  * diff machinery
  */
 static void fill_origin_blob(struct diff_options *opt,
-			     struct blame_origin *o, mmfile_t *file, int *num_read_blob)
+			     struct blame_origin *o, mmfile_t *file,
+			     int *num_read_blob, int fill_fingerprints)
 {
 	if (!o->file.ptr) {
 		enum object_type type;
@@ -340,11 +391,14 @@ static void fill_origin_blob(struct diff_options *opt,
 	}
 	else
 		*file = o->file;
+	if (fill_fingerprints)
+		fill_origin_fingerprints(o, file);
 }
 
 static void drop_origin_blob(struct blame_origin *o)
 {
 	FREE_AND_NULL(o->file.ptr);
+	drop_origin_fingerprints(o);
 }
 
 /*
@@ -1136,8 +1190,10 @@ static void pass_blame_to_parent(struct blame_scoreboard *sb,
 	d.ignore_diffs = ignore_diffs;
 	d.dstq = &newdest; d.srcq = &target->suspects;
 
-	fill_origin_blob(&sb->revs->diffopt, parent, &file_p, &sb->num_read_blob);
-	fill_origin_blob(&sb->revs->diffopt, target, &file_o, &sb->num_read_blob);
+	fill_origin_blob(&sb->revs->diffopt, parent, &file_p,
+			 &sb->num_read_blob, ignore_diffs);
+	fill_origin_blob(&sb->revs->diffopt, target, &file_o,
+			 &sb->num_read_blob, ignore_diffs);
 	sb->num_get_patch++;
 
 	if (diff_hunks(&file_p, &file_o, blame_chunk_cb, &d, sb->xdl_opts))
@@ -1348,7 +1404,8 @@ static void find_move_in_parent(struct blame_scoreboard *sb,
 	if (!unblamed)
 		return; /* nothing remains for this target */
 
-	fill_origin_blob(&sb->revs->diffopt, parent, &file_p, &sb->num_read_blob);
+	fill_origin_blob(&sb->revs->diffopt, parent, &file_p,
+			 &sb->num_read_blob, 0);
 	if (!file_p.ptr)
 		return;
 
@@ -1477,7 +1534,8 @@ static void find_copy_in_parent(struct blame_scoreboard *sb,
 			norigin = get_origin(parent, p->one->path);
 			oidcpy(&norigin->blob_oid, &p->one->oid);
 			norigin->mode = p->one->mode;
-			fill_origin_blob(&sb->revs->diffopt, norigin, &file_p, &sb->num_read_blob);
+			fill_origin_blob(&sb->revs->diffopt, norigin, &file_p,
+					 &sb->num_read_blob, 0);
 			if (!file_p.ptr)
 				continue;
 
@@ -1816,37 +1874,14 @@ void assign_blame(struct blame_scoreboard *sb, int opt)
 	}
 }
 
-static const char *get_next_line(const char *start, const char *end)
-{
-	const char *nl = memchr(start, '\n', end - start);
-	return nl ? nl + 1 : end;
-}
-
 /*
  * To allow quick access to the contents of nth line in the
  * final image, prepare an index in the scoreboard.
  */
 static int prepare_lines(struct blame_scoreboard *sb)
 {
-	const char *buf = sb->final_buf;
-	unsigned long len = sb->final_buf_size;
-	const char *end = buf + len;
-	const char *p;
-	int *lineno;
-	int num = 0;
-
-	for (p = buf; p < end; p = get_next_line(p, end))
-		num++;
-
-	ALLOC_ARRAY(sb->lineno, num + 1);
-	lineno = sb->lineno;
-
-	for (p = buf; p < end; p = get_next_line(p, end))
-		*lineno++ = p - buf;
-
-	*lineno = len;
-
-	sb->num_lines = num;
+	sb->num_lines = find_line_starts(&sb->lineno, sb->final_buf,
+					 sb->final_buf_size);
 	return sb->num_lines;
 }
 
diff --git a/blame.h b/blame.h
index 53df8b4c5b3f..5dd877bb78fc 100644
--- a/blame.h
+++ b/blame.h
@@ -51,6 +51,8 @@ struct blame_origin {
 	 */
 	struct blame_entry *suspects;
 	mmfile_t file;
+	int num_lines;
+	void *fingerprints;
 	struct object_id blob_oid;
 	unsigned mode;
 	/* guilty gets set when shipping any suspects to the final
-- 
2.21.0.392.gf8f6787159e-goog

[PATCH v6 6/6] blame: use a fingerprint heuristic to match ignored lines

[Barret Rhoden]

This replaces the heuristic used to identify lines from ignored commits
with one that finds likely candidate lines in the parent's version of
the file.

The old heuristic simply assigned lines in the target to the same line
number (plus offset) in the parent.  The new function uses a
fingerprinting algorithm to detect similarity between lines.

The fingerprint code and the idea to use them for blame came from
Michael Platings <michael@platin.gs>.

For each line changed in the target, i.e. in a blame_entry touched by a
target's diff, guess_line_blames() finds the best line in the parent,
above a magic threshold.  Ties are broken by proximity of the parent
line number to the target's line.

We actually make two passes.  The first pass checks in the diff chunk
associated with the blame entry - specifically from blame_chunk().
Often times, those diff chunks are small; any 'context' in a normal diff
chunk is broken up into multiple calls to blame_chunk().  We make a
second pass over the entire parent, with a slightly higher threshold.

Here's an example of the difference the fingerprinting makes.  Consider
a file with four commits:

	commit-a 11) void new_func_1(void *x, void *y);
	commit-b 12) void new_func_2(void *x, void *y);
	commit-c 13) some_line_c
	commit-d 14) some_line_d

After a commit 'X', we have:

	commit-X 11) void new_func_1(void *x,
	commit-X 12)                 void *y);
	commit-X 13) void new_func_2(void *x,
	commit-X 14)                 void *y);
	commit-c 15) some_line_c
	commit-d 16) some_line_d

When we blame-ignored with the old algorithm, we get:

	commit-a 11) void new_func_1(void *x,
	commit-b 12)                 void *y);
	00000000 13) void new_func_2(void *x,
	00000000 14)                 void *y);
	commit-c 15) some_line_c
	commit-d 16) some_line_d

Where commit-b is blamed for 12 instead of 13.  With the fingerprint
algorithm, we get:

	commit-a 11) void new_func_1(void *x,
	commit-b 12)                 void *y);
	commit-b 13) void new_func_2(void *x,
	commit-b 14)                 void *y);
	commit-c 15) some_line_c
	commit-d 16) some_line_d

Note both lines 12 and 14 are given to commit b.  Their match is above
the FINGERPRINT_CHUNK_THRESHOLD, and they tied.  Specifically, parent
lines 11 and 12 both match these lines.  The algorithm chose parent line
12, since that was closest to the target line numbers of 12 and 14.

If we increase the threshold, say to 10, those two lines won't match,
and will be treated as 'unblamable.'

For an example of scanning the entire parent for a match, consider:

	commit-a 30) #include <sys/header_a.h>
	commit-b 31) #include <header_b.h>
	commit-c 32) #include <header_c.h>

Then commit X alphabetizes them:

	commit-X 30) #include <header_b.h>
	commit-X 31) #include <header_c.h>
	commit-X 32) #include <sys/header_a.h>

If we just check the parent's chunk (i.e. the first pass), we'd get:

	commit-b 30) #include <header_b.h>
	commit-c 31) #include <header_c.h>
	00000000 32) #include <sys/header_a.h>

That's because commit X consists of two chunks: one chunk is removing
sys/header_a.h, then some context, and the second chunk is adding
sys/header_a.h.

If we scan the entire parent file, we get:

	commit-b 30) #include <header_b.h>
	commit-c 31) #include <header_c.h>
	commit-a 32) #include <sys/header_a.h>

Suggested-by: Michael Platings <michael@platin.gs>
Signed-off-by: Barret Rhoden <brho@google.com>
---
 blame.c | 140 ++++++++++++++++++++++++++++++++++++++++++++++++++++----
 1 file changed, 131 insertions(+), 9 deletions(-)

diff --git a/blame.c b/blame.c
index a42dff80b1a5..da2d664b38af 100644
--- a/blame.c
+++ b/blame.c
@@ -340,6 +340,84 @@ static int find_line_starts(int **line_starts, const char *buf,
 	return num;
 }
 
+struct fingerprint {
+	struct hashmap map;
+	struct hashmap_entry *entries;
+};
+
+static void get_fingerprint(struct fingerprint *result,
+			    const char *line_begin,
+			    const char *line_end)
+{
+	unsigned int hash;
+	char c0, c1;
+	const char *p;
+	int map_entry_count = line_end - line_begin - 1;
+	struct hashmap_entry *entry = xcalloc(map_entry_count,
+					      sizeof(struct hashmap_entry));
+
+	hashmap_init(&result->map, NULL, NULL, map_entry_count);
+	result->entries = entry;
+	for (p = line_begin; p + 1 < line_end; ++p, ++entry) {
+		c0 = *p;
+		c1 = *(p + 1);
+		/* Ignore whitespace pairs */
+		if (isspace(c0) && isspace(c1))
+			continue;
+		hash = tolower(c0) | (tolower(c1) << 8);
+		hashmap_entry_init(entry, hash);
+		hashmap_put(&result->map, entry);
+	}
+}
+
+static void free_fingerprint(struct fingerprint *f)
+{
+	hashmap_free(&f->map, 0);
+	free(f->entries);
+}
+
+static int fingerprint_similarity(struct fingerprint *a,
+				  struct fingerprint *b)
+{
+	int intersection = 0;
+	struct hashmap_iter iter;
+	struct hashmap_entry *entry;
+
+	hashmap_iter_init(&b->map, &iter);
+
+	while ((entry = hashmap_iter_next(&iter))) {
+		if (hashmap_get(&a->map, entry, NULL))
+			++intersection;
+	}
+	return intersection;
+}
+
+static void get_line_fingerprints(struct fingerprint *fingerprints,
+				  const char *content,
+				  const int *line_starts,
+				  int first_line,
+				  int nr_lines)
+{
+	int i;
+
+	line_starts += first_line;
+	for (i = 0; i < nr_lines; ++i) {
+		const char *linestart = content + line_starts[i];
+		const char *lineend = content + line_starts[i + 1];
+
+		get_fingerprint(fingerprints + i, linestart, lineend);
+	}
+}
+
+static void free_chunk_fingerprints(struct fingerprint *fingerprints,
+				    int nr_fingerprints)
+{
+	int i;
+
+	for (i = 0; i < nr_fingerprints; i++)
+		free_fingerprint(&fingerprints[i]);
+}
+
 static void fill_origin_fingerprints(struct blame_origin *o, mmfile_t *file)
 {
 	int *line_starts;
@@ -348,14 +426,16 @@ static void fill_origin_fingerprints(struct blame_origin *o, mmfile_t *file)
 		return;
 	o->num_lines = find_line_starts(&line_starts, o->file.ptr,
 					o->file.size);
-	/* TODO: Will fill in fingerprints in a future commit */
 	o->fingerprints = xcalloc(sizeof(struct fingerprint), o->num_lines);
+	get_line_fingerprints(o->fingerprints, o->file.ptr, line_starts,
+			      0, o->num_lines);
 	free(line_starts);
 }
 
 static void drop_origin_fingerprints(struct blame_origin *o)
 {
 	if (o->fingerprints) {
+		free_chunk_fingerprints(o->fingerprints, o->num_lines);
 		o->num_lines = 0;
 		FREE_AND_NULL(o->fingerprints);
 	}
@@ -935,27 +1015,69 @@ static int are_lines_adjacent(struct blame_line_tracker *first,
 	       first->s_lno + 1 == second->s_lno;
 }
 
+static void scan_parent_range(struct fingerprint *p_fps,
+			      struct fingerprint *t_fps, int t_idx,
+			      int from, int nr_lines,
+			      int *best_sim_val, int *best_sim_idx)
+{
+	int sim, p_idx;
+
+	for (p_idx = from; p_idx < from + nr_lines; p_idx++) {
+		sim = fingerprint_similarity(&t_fps[t_idx], &p_fps[p_idx]);
+		if (sim < *best_sim_val)
+			continue;
+		/* Break ties with the closest-to-target line number */
+		if (sim == *best_sim_val && *best_sim_idx != -1 &&
+		    abs(*best_sim_idx - t_idx) < abs(p_idx - t_idx))
+			continue;
+		*best_sim_val = sim;
+		*best_sim_idx = p_idx;
+	}
+}
+
 /*
- * This cheap heuristic assigns lines in the chunk to their relative location in
- * the parent's chunk.  Any additional lines are left with the target.
+ * The CHUNK threshold is for how similar we must be within a diff chunk, which
+ * is typically the adjacent '-' and '+' sections in a diff, separated by the
+ * ' ' context.
+ *
+ * We have a greater threshold for similarity for lines in any part of the
+ * parent's file.  If no line in the parent meets the appropriate threshold,
+ * then the blame_entry will stay with the target and be considered
+ * 'unblamable'.
  */
+#define FINGERPRINT_CHUNK_THRESHOLD	1
+#define FINGERPRINT_FILE_THRESHOLD	10
+
 static void guess_line_blames(struct blame_entry *e,
 			      struct blame_origin *parent,
 			      struct blame_origin *target,
 			      int offset, int parent_slno, int parent_len,
 			      struct blame_line_tracker *line_blames)
 {
-	int i, parent_idx;
+	int i, target_idx;
 
 	for (i = 0; i < e->num_lines; i++) {
-		parent_idx = e->s_lno + i + offset;
-		if (parent_slno <= parent_idx &&
-		    parent_idx < parent_slno + parent_len) {
+		int best_val = FINGERPRINT_CHUNK_THRESHOLD;
+		int best_idx = -1;
+
+		target_idx = e->s_lno + i;
+		scan_parent_range(parent->fingerprints,
+				  target->fingerprints, target_idx,
+				  parent_slno, parent_len,
+				  &best_val, &best_idx);
+		if (best_idx == -1) {
+			best_val = FINGERPRINT_FILE_THRESHOLD;
+			scan_parent_range(parent->fingerprints,
+					  target->fingerprints, target_idx,
+					  0, parent->num_lines,
+					  &best_val, &best_idx);
+		}
+		if (best_idx >= 0) {
 			line_blames[i].is_parent = 1;
-			line_blames[i].s_lno = parent_idx;
+			line_blames[i].s_lno = best_idx;
 		} else {
 			line_blames[i].is_parent = 0;
-			line_blames[i].s_lno = e->s_lno + i;
+			line_blames[i].s_lno = target_idx;
 		}
 	}
 }
-- 
2.21.0.392.gf8f6787159e-goog

Re: [PATCH v6 6/6] blame: use a fingerprint heuristic to match ignored lines

[Junio C Hamano]

Barret Rhoden <brho@google.com> writes:

> This replaces the heuristic used to identify lines from ignored commits
> with one that finds likely candidate lines in the parent's version of
> the file.
>
> The old heuristic simply assigned lines in the target to the same line
> number (plus offset) in the parent.  The new function uses a
> fingerprinting algorithm to detect similarity between lines.
>
> The fingerprint code and the idea to use them for blame came from
> Michael Platings <michael@platin.gs>.
>
> For each line changed in the target, i.e. in a blame_entry touched by a
> target's diff, guess_line_blames() finds the best line in the parent,
> above a magic threshold.  Ties are broken by proximity of the parent
> line number to the target's line.
>
> We actually make two passes.  The first pass checks in the diff chunk
> associated with the blame entry - specifically from blame_chunk().
> Often times, those diff chunks are small; any 'context' in a normal diff
> chunk is broken up into multiple calls to blame_chunk().  We make a
> second pass over the entire parent, with a slightly higher threshold.

Two thoughts.

 - Unless the 'old heuristic' is still available as an option after
   this step, a series that first begins with the 'old heuristic'
   and then later replaces it with the 'new heuristic' feels
   somewhat wasteful of reviewer resources, as the 'old heuristic'
   does not contribute an iota to the end result.

   It is OK while the series is still in RFC/WIP stage, though.  But
   because I got an impression that this is close to completion, so...

 - I wonder if the hash used here can replace what is used in
   diffcore-delta.c as an improvement (or obviously vice versa), as
   using two (or more) ad-hoc fingerprinting function without having
   a clear reason why we need two instead of a unified one feels
   like a bad idea.

Re: [PATCH v6 6/6] blame: use a fingerprint heuristic to match ignored lines

[Michael Platings]

>  - I wonder if the hash used here can replace what is used in
>    diffcore-delta.c as an improvement (or obviously vice versa), as
>    using two (or more) ad-hoc fingerprinting function without having
>    a clear reason why we need two instead of a unified one feels
>    like a bad idea.

Hi Junio,
If I understand correctly, the algorithm in diffcore-delta.c is
intended to match files that contain identical lines (or 64-byte
chunks). The fingerprinting that Barret & I are talking about is
intended to match lines that contain identical byte pairs.
With significant refactoring, you could make the diffcore-delta
algorithm apply in both cases but I think the end result would be
longer and more complicated than keeping the two separate.
Unlike hashing a line, hashing a byte pair is trivial. Unlike hashing
lines, all except the first and last bytes are included in two
"hashes" - "hello" is hashed to "he", "el", "ll", "lo".
So based on my limited understanding of diffcore-delta.c I think the
two are algorithms are sufficiently different in intent and in
implementation that it's appropriate to keep them separate.

Regarding the "old heuristic" I think there may still be a use case
for that but I'll expand on that later.

Thanks,
-Michael

Re: [PATCH v6 6/6] blame: use a fingerprint heuristic to match ignored lines

[Barret Rhoden]

On 4/13/19 11:54 PM, Junio C Hamano wrote:
> Two thoughts.
> 
>   - Unless the 'old heuristic' is still available as an option after
>     this step, a series that first begins with the 'old heuristic'
>     and then later replaces it with the 'new heuristic' feels
>     somewhat wasteful of reviewer resources, as the 'old heuristic'
>     does not contribute an iota to the end result.
> 
>     It is OK while the series is still in RFC/WIP stage, though.  But
>     because I got an impression that this is close to completion, so...

Can do.  I wasn't sure yet where things were going, but in the final 
version, I can yank out the old heuristic from the patch set.

Though the old heuristic is pretty basic - really just a couple lines - 
and it may help to see it before looking at a more complicated version. 
Especially since it helps break the commit up into "infrastructure to 
ignore commits" and "brains to find the right commit to blame" while 
still being functional between the commits.

Thanks,

Barret

Re: [PATCH v6 6/6] blame: use a fingerprint heuristic to match ignored lines

[Junio C Hamano]

Barret Rhoden <brho@google.com> writes:

> Though the old heuristic is pretty basic - really just a couple lines
> - 
> and it may help to see it before looking at a more complicated
> version.

OK, then.

Thanks.

Re: [PATCH v6 0/6] blame: add the ability to ignore commits

[Michael Platings]

Hi Barret,

This works pretty well for the typical reformatting use case now. I've
run it over every commit of every .c file in the git project root,
both forwards and backwards with every combination of -w/-M/-C and
can't get it to crash so I think it's good in that respect.

However, it can still attribute lines to the wrong parent line. See
https://pypi.org/project/autopep8/#usage for an example reformatting
that it gets a bit confused on. The patch I submitted handles this
case correctly because it uses information about the more similar
lines to decide how more ambiguous lines should be matched.

You also gave an example of:

        commit-a 11) void new_func_1(void *x, void *y);
        commit-b 12) void new_func_2(void *x, void *y);

Being reformatted to:

        commit-a 11) void new_func_1(void *x,
        commit-b 12)                 void *y);
        commit-b 13) void new_func_2(void *x,
        commit-b 14)                 void *y);

The patch I submitted handles this case correctly, assigning line 12
to commit-a because it scales the parent line numbers according to the
relative diff chunk sizes instead of assuming a 1-1 mapping.

So I do ask that you incorporate more of my patch, including the test
code. It is more complex but I hope this demonstrates that there are
reasons for that. Happy to provide more examples or explanation if it
would help. On the other hand if you have examples where it falls
short then I'd be interested to know.

The other major use case that I'm interested in is renaming. In this
case, the git-hyper-blame approach of mapping line numbers 1-1 works
perfectly. Here's an example. Before:

        commit-a 11) Position MyClass::location(Offset O) {
        commit-b 12)    return P + O;
        commit-c 13) }

After:

        commit-a 11) Position MyClass::location(Offset offset) {
        commit-a 12)    return position + offset;
        commit-c 13) }

With the fuzzy matching, line 12 gets incorrectly matched to parent
line 11 because the similarity of "position" and "offset" outweighs
the similarity of "return". I'm considering adding even more
complexity to my patch such that parts of a line that have already
been matched can't be matched again by other lines.

But the other possibility is that we let the user choose the
heuristic. For a commit where they know that line numbers haven't
changed they could choose 1-1 matching, while for a reformatting
commit they could use fuzzy matching. I welcome your thoughts.

-Michael

Re: [PATCH v6 0/6] blame: add the ability to ignore commits

[Barret Rhoden]

Hi Michael -

On 4/14/19 5:10 PM, Michael Platings wrote:
> Hi Barret,
> 
> This works pretty well for the typical reformatting use case now. I've
> run it over every commit of every .c file in the git project root,
> both forwards and backwards with every combination of -w/-M/-C and
> can't get it to crash so I think it's good in that respect.
> 
> However, it can still attribute lines to the wrong parent line. See
> https://pypi.org/project/autopep8/#usage for an example reformatting
> that it gets a bit confused on. The patch I submitted handles this
> case correctly because it uses information about the more similar
> lines to decide how more ambiguous lines should be matched.

Yeah - I ran your tests against it and noticed a few cases weren't handled.

> You also gave an example of:
> 
>          commit-a 11) void new_func_1(void *x, void *y);
>          commit-b 12) void new_func_2(void *x, void *y);
> 
> Being reformatted to:
> 
>          commit-a 11) void new_func_1(void *x,
>          commit-b 12)                 void *y);
>          commit-b 13) void new_func_2(void *x,
>          commit-b 14)                 void *y);
> 
> The patch I submitted handles this case correctly, assigning line 12
> to commit-a because it scales the parent line numbers according to the
> relative diff chunk sizes instead of assuming a 1-1 mapping.
> 
> So I do ask that you incorporate more of my patch, including the test
> code. It is more complex but I hope this demonstrates that there are
> reasons for that. Happy to provide more examples or explanation if it
> would help. On the other hand if you have examples where it falls
> short then I'd be interested to know.

My main concerns:
- Can your version reach outside of a diff chunk?  such as in my "header 
moved" case.  That was a simplified version of something that pops up in 
a major file reformatting of mine, where a "return 0;" was matched as 
context and broke a diff chunk up into two blame_chunk() calls.  I tend 
to think of this as the "split diff chunk."

- Complexity and possibly performance.  The recursive stuff made me 
wonder about it a bit.  It's no reason not to use it, just need to check 
it more closely.

Is the latest version of your stuff still the one you posted last week 
or so?  If we had a patch applied onto this one with something like an 
ifdef or a dirt-simple toggle, we can play with both of them in the same 
codebase.

Similarly, do you think the "two pass" approach I have (check the chunk, 
then check the parent file) would work with your recursive partitioning 
style?  That might make yours able to handle the "split diff chunk" case.

> The other major use case that I'm interested in is renaming. In this
> case, the git-hyper-blame approach of mapping line numbers 1-1 works
> perfectly. Here's an example. Before:
> 
>          commit-a 11) Position MyClass::location(Offset O) {
>          commit-b 12)    return P + O;
>          commit-c 13) }
> 
> After:
> 
>          commit-a 11) Position MyClass::location(Offset offset) {
>          commit-a 12)    return position + offset;
>          commit-c 13) }
> 
> With the fuzzy matching, line 12 gets incorrectly matched to parent
> line 11 because the similarity of "position" and "offset" outweighs
> the similarity of "return". I'm considering adding even more
> complexity to my patch such that parts of a line that have already
> been matched can't be matched again by other lines.
> 
> But the other possibility is that we let the user choose the
> heuristic. For a commit where they know that line numbers haven't
> changed they could choose 1-1 matching, while for a reformatting
> commit they could use fuzzy matching. I welcome your thoughts.

No algorithm will work for all cases.  The one you just gave had the 
simple heuristic working better than a complex one.  We could make it 
more complex, but then another example may be worse.  I can live with 
some inaccuracy in exchange for simplicity.

I ran into something similar with the THRESHOLD #defines.  You want it 
to be able to match certain things, but not other things.  How similar 
does something have to be?  Should it depend on how far away the 
matching line is from the source line?  I went with a "close enough is 
good enough" approach, since we're marking with a '*' or something 
anyways, so the user should know to not trust it 100%.

Thanks,

Barret

Re: [PATCH v6 0/6] blame: add the ability to ignore commits

[Michael Platings]

> My main concerns:
> - Can your version reach outside of a diff chunk?

Currently no. It's optimised for reformatting and renaming, both of
which preserve ordering. I could look into allowing disordered matches
where the similarity is high, while still being biased towards ordered
matches. If you can post more examples that would be helpful.

> - Complexity and possibly performance.  The recursive stuff made me
> wonder about it a bit.  It's no reason not to use it, just need to check
> it more closely.

Complexity I can't deny, I can only mitigate it with
documentation/comments. I optimised the code pretty heavily and tested
on some contrived worst-case scenarios and the performance was still
good so I'm not worried about that.

> Is the latest version of your stuff still the one you posted last week
> or so?

Yes. But reaching outside the chunk might lead to a significantly
different API in the next version...

> Similarly, do you think the "two pass" approach I have (check the chunk,
> then check the parent file) would work with your recursive partitioning
> style?  That might make yours able to handle the "split diff chunk" case.

Yes, should do. I'll see what I can come up with this week.

> No algorithm will work for all cases.  The one you just gave had the
> simple heuristic working better than a complex one.  We could make it
> more complex, but then another example may be worse.  I can live with
> some inaccuracy in exchange for simplicity.

Exactly, no algorithm will work for all cases. So what I'm suggesting
is that it might be best to let the user choose which heuristic is
appropriate for a given commit. If they know that the simple heuristic
works best then perhaps we should let them choose that rather than
only offering a one-size-fits-all option. But if we do want to go for
one-size-fits-all then I'm very keen to make sure it at least solves
the specific cases that we know about.

RE: [PATCH v6 0/6] blame: add the ability to ignore commits

[michael]

From: Michael Platings <michael@platin.gs>

Hi Barret,

This patch is on top of your patch v6 4/6.

Previously I pointed out that my code couldn't handle this case correctly:
Before:

        commit-a 11) Position MyClass::location(Offset O) {
        commit-b 12)    return P + O;
        commit-c 13) }

After:

        commit-a 11) Position MyClass::location(Offset offset) {
        commit-a 12)    return position + offset;
        commit-c 13) }

With this patch, line 12 is now correctly matched to commit-b even though it is
more similar to line 11.

The significant change here is that when a line is matched, its fingerprint is
subtracted from the matched parent line's fingerprint. This prevents two lines
matching the same part of a parent line.

This algorithm is now very good at matching lines *as long as line ordering is
unchanged*. When matching lines in a single diff chunk it makes sense to assume
that lines are ordered because if they're not then there's a good chance the
true match is outside the chunk. I'm very happy with how this algorithm behaves
and I'm struggling to fault it for the refactoring & renaming use cases.

To address reordered lines I suggest a combination of this algorithm and your
algorithm - in the first path my algorithm tries to match lines within a
single chunk, and in the second pass your algorithm tries to find matches for
unblamed lines out of order and outside their chunk.

It would also be possible to adapt my algorithm to not assume that lines are
ordered, but I think that would make it O(n^2) whereas it's typically
O(n log n) right now. But I could dig into that more if you prefer.

Thanks,
-Michael
---
 Makefile |   1 +
 blame.c  |  95 +++++++-----
 blame.h  |   2 +
 fuzzy.c  | 434 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
 fuzzy.h  |  18 +++
 5 files changed, 515 insertions(+), 35 deletions(-)
 create mode 100644 fuzzy.c
 create mode 100644 fuzzy.h

diff --git a/Makefile b/Makefile
index 3e03290d8f..4725060c54 100644
--- a/Makefile
+++ b/Makefile
@@ -893,6 +893,7 @@ LIB_OBJS += fetch-object.o
 LIB_OBJS += fetch-pack.o
 LIB_OBJS += fsck.o
 LIB_OBJS += fsmonitor.o
+LIB_OBJS += fuzzy.o
 LIB_OBJS += gettext.o
 LIB_OBJS += gpg-interface.o
 LIB_OBJS += graph.o
diff --git a/blame.c b/blame.c
index a98ae00e2c..43cdfcc259 100644
--- a/blame.c
+++ b/blame.c
@@ -9,6 +9,7 @@
 #include "blame.h"
 #include "alloc.h"
 #include "commit-slab.h"
+#include "fuzzy.h"
 
 define_commit_slab(blame_suspects, struct blame_origin *);
 static struct blame_suspects blame_suspects;
@@ -311,12 +312,42 @@ static int diff_hunks(mmfile_t *file_a, mmfile_t *file_b,
 	return xdi_diff(file_a, file_b, &xpp, &xecfg, &ecb);
 }
 
+static const char *get_next_line(const char *start, const char *end)
+{
+	const char *nl = memchr(start, '\n', end - start);
+
+	return nl ? nl + 1 : end;
+}
+
+static int find_line_starts(int **line_starts, const char *buf,
+			    unsigned long len)
+{
+	const char *end = buf + len;
+	const char *p;
+	int *lineno;
+	int num = 0;
+
+	for (p = buf; p < end; p = get_next_line(p, end))
+		num++;
+
+	ALLOC_ARRAY(*line_starts, num + 1);
+	lineno = *line_starts;
+
+	for (p = buf; p < end; p = get_next_line(p, end))
+		*lineno++ = p - buf;
+
+	*lineno = len;
+
+	return num;
+}
+
 /*
  * Given an origin, prepare mmfile_t structure to be used by the
  * diff machinery
  */
 static void fill_origin_blob(struct diff_options *opt,
-			     struct blame_origin *o, mmfile_t *file, int *num_read_blob)
+			     struct blame_origin *o, mmfile_t *file,
+			     int *num_read_blob, int fill_line_starts)
 {
 	if (!o->file.ptr) {
 		enum object_type type;
@@ -340,11 +371,16 @@ static void fill_origin_blob(struct diff_options *opt,
 	}
 	else
 		*file = o->file;
+	if (fill_line_starts && !o->line_starts)
+		o->num_lines = find_line_starts(&o->line_starts, o->file.ptr,
+						o->file.size);
 }
 
 static void drop_origin_blob(struct blame_origin *o)
 {
 	FREE_AND_NULL(o->file.ptr);
+	FREE_AND_NULL(o->line_starts);
+	o->num_lines = 0;
 }
 
 /*
@@ -891,19 +927,27 @@ static void guess_line_blames(struct blame_entry *e,
 			      int offset, int parent_slno, int parent_len,
 			      struct blame_line_tracker *line_blames)
 {
-	int i, parent_idx;
+	int i;
+	int *matching_lines = fuzzy_find_matching_lines(parent->file.ptr,
+							target->file.ptr,
+							parent->line_starts,
+							target->line_starts,
+							e->s_lno + offset,
+							e->s_lno,
+							parent_len,
+							e->num_lines);
 
 	for (i = 0; i < e->num_lines; i++) {
-		parent_idx = e->s_lno + i + offset;
-		if (parent_slno <= parent_idx &&
-		    parent_idx < parent_slno + parent_len) {
+		if (matching_lines[i] >= 0) {
 			line_blames[i].is_parent = 1;
-			line_blames[i].s_lno = parent_idx;
+			line_blames[i].s_lno = matching_lines[i];
 		} else {
 			line_blames[i].is_parent = 0;
 			line_blames[i].s_lno = e->s_lno + i;
 		}
 	}
+
+	free(matching_lines);
 }
 
 /*
@@ -1136,8 +1180,10 @@ static void pass_blame_to_parent(struct blame_scoreboard *sb,
 	d.ignore_diffs = ignore_diffs;
 	d.dstq = &newdest; d.srcq = &target->suspects;
 
-	fill_origin_blob(&sb->revs->diffopt, parent, &file_p, &sb->num_read_blob);
-	fill_origin_blob(&sb->revs->diffopt, target, &file_o, &sb->num_read_blob);
+	fill_origin_blob(&sb->revs->diffopt, parent, &file_p,
+			 &sb->num_read_blob, ignore_diffs);
+	fill_origin_blob(&sb->revs->diffopt, target, &file_o,
+			 &sb->num_read_blob, ignore_diffs);
 	sb->num_get_patch++;
 
 	if (diff_hunks(&file_p, &file_o, blame_chunk_cb, &d, sb->xdl_opts))
@@ -1348,7 +1394,8 @@ static void find_move_in_parent(struct blame_scoreboard *sb,
 	if (!unblamed)
 		return; /* nothing remains for this target */
 
-	fill_origin_blob(&sb->revs->diffopt, parent, &file_p, &sb->num_read_blob);
+	fill_origin_blob(&sb->revs->diffopt, parent, &file_p,
+			 &sb->num_read_blob, 0);
 	if (!file_p.ptr)
 		return;
 
@@ -1477,7 +1524,8 @@ static void find_copy_in_parent(struct blame_scoreboard *sb,
 			norigin = get_origin(parent, p->one->path);
 			oidcpy(&norigin->blob_oid, &p->one->oid);
 			norigin->mode = p->one->mode;
-			fill_origin_blob(&sb->revs->diffopt, norigin, &file_p, &sb->num_read_blob);
+			fill_origin_blob(&sb->revs->diffopt, norigin, &file_p,
+					 &sb->num_read_blob, 0);
 			if (!file_p.ptr)
 				continue;
 
@@ -1816,37 +1864,14 @@ void assign_blame(struct blame_scoreboard *sb, int opt)
 	}
 }
 
-static const char *get_next_line(const char *start, const char *end)
-{
-	const char *nl = memchr(start, '\n', end - start);
-	return nl ? nl + 1 : end;
-}
-
 /*
  * To allow quick access to the contents of nth line in the
  * final image, prepare an index in the scoreboard.
  */
 static int prepare_lines(struct blame_scoreboard *sb)
 {
-	const char *buf = sb->final_buf;
-	unsigned long len = sb->final_buf_size;
-	const char *end = buf + len;
-	const char *p;
-	int *lineno;
-	int num = 0;
-
-	for (p = buf; p < end; p = get_next_line(p, end))
-		num++;
-
-	ALLOC_ARRAY(sb->lineno, num + 1);
-	lineno = sb->lineno;
-
-	for (p = buf; p < end; p = get_next_line(p, end))
-		*lineno++ = p - buf;
-
-	*lineno = len;
-
-	sb->num_lines = num;
+	sb->num_lines = find_line_starts(&sb->lineno, sb->final_buf,
+					 sb->final_buf_size);
 	return sb->num_lines;
 }
 
diff --git a/blame.h b/blame.h
index 53df8b4c5b..f7755920c9 100644
--- a/blame.h
+++ b/blame.h
@@ -51,6 +51,8 @@ struct blame_origin {
 	 */
 	struct blame_entry *suspects;
 	mmfile_t file;
+	int num_lines;
+	int *line_starts;
 	struct object_id blob_oid;
 	unsigned mode;
 	/* guilty gets set when shipping any suspects to the final
diff --git a/fuzzy.c b/fuzzy.c
new file mode 100644
index 0000000000..c5b09a0eb7
--- /dev/null
+++ b/fuzzy.c
@@ -0,0 +1,434 @@
+#include "fuzzy.h"
+#include <ctype.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include <string.h>
+#include "git-compat-util.h"
+#include "hashmap.h"
+
+struct fingerprint_entry {
+	struct hashmap_entry entry;
+	int count;
+};
+struct fingerprint {
+	struct hashmap map;
+	struct fingerprint_entry *entries;
+};
+
+static void get_fingerprint(struct fingerprint *result,
+			    const char *line_begin,
+			    const char *line_end) {
+	unsigned hash;
+	char c0, c1;
+	int map_entry_count = line_end - line_begin - 1;
+	struct fingerprint_entry *entry = xcalloc(map_entry_count,
+		sizeof(struct fingerprint_entry));
+	struct fingerprint_entry *found_entry;
+	hashmap_init(&result->map, NULL, NULL, map_entry_count);
+	result->entries = entry;
+	for (const char *p = line_begin; p + 1 < line_end; ++p, ++entry) {
+		c0 = *p;
+		c1 = *(p + 1);
+		/* Ignore whitespace pairs */
+		if (isspace(c0) && isspace(c1))
+			continue;
+		hash = tolower(c0) | (tolower(c1) << 8);
+		hashmap_entry_init(entry, hash);
+
+		if ((found_entry = hashmap_get(&result->map, entry, NULL))) {
+			found_entry->count += 1;
+		}
+		else {
+			entry->count = 1;
+			hashmap_add(&result->map, entry);
+		}
+	}
+}
+
+static void free_fingerprint(struct fingerprint *f) {
+	hashmap_free(&f->map, 0);
+	free(f->entries);
+}
+
+static int fingerprint_similarity(struct fingerprint *a,
+				  struct fingerprint *b) {
+	int intersection = 0;
+	struct hashmap_iter iter;
+	const struct fingerprint_entry *entry_a, *entry_b;
+	hashmap_iter_init(&b->map, &iter);
+
+	while ((entry_b = hashmap_iter_next(&iter))) {
+		if ((entry_a = hashmap_get(&a->map, entry_b, NULL))) {
+			intersection += entry_a->count < entry_b->count ?
+					entry_a->count : entry_b->count;
+		}
+	}
+	return intersection;
+}
+
+static void fingerprint_subtract(struct fingerprint *a,
+				 struct fingerprint *b) {
+	struct hashmap_iter iter;
+	struct fingerprint_entry *entry_a;
+	const struct fingerprint_entry *entry_b;
+	hashmap_iter_init(&b->map, &iter);
+
+	while ((entry_b = hashmap_iter_next(&iter))) {
+		if ((entry_a = hashmap_get(&a->map, entry_b, NULL))) {
+			if (entry_a->count <= entry_b->count) {
+				hashmap_remove(&a->map, entry_b, NULL);
+			}
+			else {
+				entry_a->count -= entry_b->count;
+			}
+		}
+	}
+}
+
+static void get_line_fingerprints(struct fingerprint *fingerprints,
+				  const char *content,
+				  const int *line_starts,
+				  long chunk_start,
+				  long chunk_length) {
+	int i;
+	const char *linestart, *lineend;
+	line_starts += chunk_start;
+	for (i = 0; i != chunk_length; ++i) {
+		linestart = content + line_starts[i];
+		lineend = content + line_starts[i + 1];
+		get_fingerprint(fingerprints + i, linestart, lineend);
+	}
+}
+
+static int get_closest_local_line(int start_a,
+			    int local_line_b,
+			    int closest_line_calc_offset1,
+			    int closest_line_calc_offset2,
+			    int closest_line_calc_numerator,
+			    int closest_line_calc_denominator) {
+	return ((local_line_b + closest_line_calc_offset1) * 2 + 1) *
+		closest_line_calc_numerator /
+		(closest_line_calc_denominator * 2) +
+		closest_line_calc_offset2 - start_a;
+}
+
+static int *get_similarity(int *similarities, int max_search_distance_a,
+			   int local_line_a, int local_line_b,
+			   int closest_local_line_a) {
+	assert(abs(local_line_a - closest_local_line_a) <= max_search_distance_a);
+	return similarities + local_line_a - closest_local_line_a +
+		max_search_distance_a +
+		local_line_b * (max_search_distance_a * 2 + 1);
+}
+
+#define CERTAIN_NOTHING_MATCHES -2
+#define CERTAINTY_NOT_CALCULATED -1
+
+static void find_best_line_matches(const int max_search_distance_a,
+				   int start_a,
+				   int length_a,
+				   int local_line_b,
+				   struct fingerprint *fingerprints_a,
+				   struct fingerprint *fingerprints_b,
+				   int *similarities,
+				   int *certainties,
+				   int *second_best_result,
+				   int *result,
+				   int closest_line_calc_offset1,
+				   int closest_line_calc_offset2,
+				   int closest_line_calc_numerator,
+				   int closest_line_calc_denominator) {
+
+	int i, search_start, search_end, closest_local_line_a, *similarity,
+		best_similarity = 0, second_best_similarity = 0,
+		best_similarity_index = 0, second_best_similarity_index = 0;
+
+	if (certainties[local_line_b] != CERTAINTY_NOT_CALCULATED)
+		return;
+
+	closest_local_line_a = get_closest_local_line(start_a,
+					  local_line_b,
+					  closest_line_calc_offset1,
+					  closest_line_calc_offset2,
+					  closest_line_calc_numerator,
+					  closest_line_calc_denominator);
+
+	search_start = closest_local_line_a - max_search_distance_a;
+	if (search_start < 0)
+		search_start = 0;
+
+	search_end = closest_local_line_a + max_search_distance_a + 1;
+	if (search_end > length_a)
+		search_end = length_a;
+
+	for (i = search_start; i < search_end; ++i) {
+		similarity = get_similarity(similarities, max_search_distance_a,
+					    i, local_line_b,
+					    closest_local_line_a);
+		if (*similarity == -1) {
+			*similarity = fingerprint_similarity(
+				fingerprints_b + local_line_b,
+				fingerprints_a + i) *
+				(1000 - abs(i - closest_local_line_a));
+		}
+		if (*similarity > best_similarity) {
+			second_best_similarity = best_similarity;
+			second_best_similarity_index = best_similarity_index;
+			best_similarity = *similarity;
+			best_similarity_index = i;
+		}
+		else if (*similarity > second_best_similarity) {
+			second_best_similarity = *similarity;
+			second_best_similarity_index = i;
+		}
+	}
+
+	if (best_similarity == 0) {
+		certainties[local_line_b] = CERTAIN_NOTHING_MATCHES;
+		result[local_line_b] = -1;
+	}
+	else {
+		certainties[local_line_b] = best_similarity * 2 -
+			second_best_similarity;
+		result[local_line_b] = start_a + best_similarity_index;
+		second_best_result[local_line_b] =
+			start_a + second_best_similarity_index;
+	}
+}
+
+/*
+ * This finds the line that we can match with the most confidence, and
+ * uses it as a partition. It then calls itself on the lines on either side of
+ * that partition. In this way we avoid lines appearing out of order, and
+ * retain a sensible line ordering.
+ */
+static void fuzzy_find_matching_lines_recurse(
+	int max_search_distance_a,
+	int max_search_distance_b,
+	int start_a, int start_b,
+	int length_a, int length_b,
+	struct fingerprint *fingerprints_a,
+	struct fingerprint *fingerprints_b,
+	int *similarities,
+	int *certainties,
+	int *second_best_result,
+	int *result,
+	int closest_line_calc_offset1,
+	int closest_line_calc_offset2,
+	int closest_line_calc_numerator,
+	int closest_line_calc_denominator) {
+
+	int i, barrier, invalidate_min, invalidate_max, offset_b,
+		second_half_start_a, second_half_start_b,
+		second_half_length_a, second_half_length_b,
+		most_certain_line_a, most_certain_local_line_b = -1,
+		most_certain_line_certainty = -1,
+		closest_local_line_a;
+
+	for (i = 0; i < length_b; ++i) {
+		find_best_line_matches(max_search_distance_a,
+				       start_a,
+				       length_a,
+				       i,
+				       fingerprints_a,
+				       fingerprints_b,
+				       similarities,
+				       certainties,
+				       second_best_result,
+				       result,
+				       closest_line_calc_offset1,
+				       closest_line_calc_offset2,
+				       closest_line_calc_numerator,
+				       closest_line_calc_denominator);
+
+		if (certainties[i] > most_certain_line_certainty) {
+			most_certain_line_certainty = certainties[i];
+			most_certain_local_line_b = i;
+		}
+	}
+
+	if (most_certain_local_line_b == -1) {
+		return;
+	}
+
+	most_certain_line_a = result[most_certain_local_line_b];
+
+	/* Subtract the most certain line's fingerprint in b from the
+	 matched fingerprint in a. This means that other lines in b can't also
+	 match the same parts of the line in a. */
+	fingerprint_subtract(fingerprints_a + most_certain_line_a - start_a,
+			     fingerprints_b + most_certain_local_line_b);
+
+
+	/* Invalidate results that may be affected by the choice of pivot. */
+	invalidate_min = most_certain_local_line_b - max_search_distance_b;
+	invalidate_max = most_certain_local_line_b + max_search_distance_b + 1;
+	if (invalidate_min < 0)
+		invalidate_min = 0;
+	if (invalidate_max > length_b)
+		invalidate_max = length_b;
+
+	for (i = invalidate_min; i < invalidate_max; ++i) {
+		closest_local_line_a = get_closest_local_line(
+			start_a, i,
+			closest_line_calc_offset1,
+			closest_line_calc_offset2,
+			closest_line_calc_numerator,
+			closest_line_calc_denominator);
+		*get_similarity(similarities, max_search_distance_a,
+				most_certain_line_a - start_a, i,
+				closest_local_line_a) = -1;
+	}
+
+	barrier = most_certain_line_a;
+
+	for (i = most_certain_local_line_b - 1; i >= invalidate_min; --i) {
+		if (certainties[i] >= 0 &&
+		    (result[i] >= barrier || second_best_result[i] >= barrier)) {
+			    certainties[i] = CERTAINTY_NOT_CALCULATED;
+			    barrier = result[i];
+			    invalidate_min = i - max_search_distance_b;
+			    if (invalidate_min < 0)
+				    invalidate_min = 0;
+		    }
+	}
+
+	barrier = most_certain_line_a;
+
+	for (i = most_certain_local_line_b + 1; i < invalidate_max; ++i) {
+		if (certainties[i] >= 0 &&
+		    (result[i] <= barrier || second_best_result[i] <= barrier)) {
+			    certainties[i] = CERTAINTY_NOT_CALCULATED;
+			    barrier = result[i];
+			    invalidate_max = i + max_search_distance_b + 1;
+			    if (invalidate_max > length_b)
+				    invalidate_max = length_b;
+		    }
+	}
+
+
+	if (most_certain_local_line_b > 0) {
+		fuzzy_find_matching_lines_recurse(
+			max_search_distance_a,
+			max_search_distance_b,
+			start_a, start_b,
+			most_certain_line_a + 1 - start_a,
+			most_certain_local_line_b,
+			fingerprints_a, fingerprints_b, similarities,
+			certainties, second_best_result, result,
+			closest_line_calc_offset1, closest_line_calc_offset2,
+			closest_line_calc_numerator,
+			closest_line_calc_denominator);
+	}
+	if (most_certain_local_line_b + 1 < length_b) {
+		second_half_start_a = most_certain_line_a;
+		offset_b = most_certain_local_line_b + 1;
+		second_half_start_b = start_b + offset_b;
+		second_half_length_a =
+			length_a + start_a - second_half_start_a;
+		second_half_length_b =
+			length_b + start_b - second_half_start_b;
+		fuzzy_find_matching_lines_recurse(
+			max_search_distance_a,
+			max_search_distance_b,
+			second_half_start_a, second_half_start_b,
+			second_half_length_a, second_half_length_b,
+			fingerprints_a + second_half_start_a - start_a,
+			fingerprints_b + offset_b,
+			similarities +
+				offset_b * (max_search_distance_a * 2 + 1),
+			certainties + offset_b,
+			second_best_result + offset_b, result + offset_b,
+			closest_line_calc_offset1 + offset_b,
+			closest_line_calc_offset2,
+			closest_line_calc_numerator,
+			closest_line_calc_denominator);
+	}
+}
+
+int *fuzzy_find_matching_lines(const char *content_a,
+			       const char *content_b,
+			       const int *line_starts_a,
+			       const int *line_starts_b,
+			       int start_a,
+			       int start_b,
+			       int length_a,
+			       int length_b) {
+
+	int i, *result, *second_best_result,
+		*certainties, *similarities, similarity_count;
+	struct fingerprint *fingerprints_a, *fingerprints_b;
+
+	/* max_search_distance_a means that given a line in `b`, compare it to
+	the line in `a` that is closest to its position, and the lines in `a`
+	that are no greater than max_search_distance_a lines away from the
+	closest line in `a`.
+	max_search_distance_b is an upper bound on the greatest possible
+	distance between lines in `b` such that they will both be compared with
+	the same line in `a` according to max_search_distance_a. */
+	int max_search_distance_a = 10, max_search_distance_b;
+
+	if (max_search_distance_a >= length_a)
+		max_search_distance_a = length_a ? length_a - 1 : 0;
+
+	if (length_a == 0) {
+		max_search_distance_b = 0;
+	}
+	else {
+		max_search_distance_b = ((2 * max_search_distance_a + 1) *
+			length_b - 1) / length_a;
+	}
+
+	result = malloc(sizeof(int) * length_b);
+	second_best_result = malloc(sizeof(int) * length_b);
+	certainties = malloc(sizeof(int) * length_b);
+	similarity_count = length_b * (max_search_distance_a * 2 + 1);
+	similarities = malloc(sizeof(int) * similarity_count);
+
+	for (i = 0; i < length_b; ++i) {
+		result[i] = -1;
+		second_best_result[i] = -1;
+		certainties[i] = CERTAINTY_NOT_CALCULATED;
+	}
+
+	for (i = 0; i < similarity_count; ++i) {
+		similarities[i] = -1;
+	}
+
+	fingerprints_a = xmalloc(sizeof(struct fingerprint) * length_a);
+	fingerprints_b = xmalloc(sizeof(struct fingerprint) * length_b);
+
+	get_line_fingerprints(fingerprints_a, content_a,
+			      line_starts_a,
+			      start_a, length_a);
+	get_line_fingerprints(fingerprints_b, content_b,
+			      line_starts_b,
+			      start_b, length_b);
+
+	fuzzy_find_matching_lines_recurse(max_search_distance_a,
+					  max_search_distance_b,
+					  start_a, start_b,
+					  length_a, length_b,
+					  fingerprints_a,
+					  fingerprints_b,
+					  similarities,
+					  certainties,
+					  second_best_result,
+					  result,
+					  0, start_a, length_a, length_b);
+
+	for (i = 0; i < length_b; ++i) {
+		free_fingerprint(fingerprints_b + i);
+	}
+	for (i = 0; i < length_a; ++i) {
+		free_fingerprint(fingerprints_a + i);
+	}
+	free(fingerprints_b);
+	free(fingerprints_a);
+	free(similarities);
+	free(certainties);
+	free(second_best_result);
+
+	return result;
+}
+
diff --git a/fuzzy.h b/fuzzy.h
new file mode 100644
index 0000000000..bd6d86ae45
--- /dev/null
+++ b/fuzzy.h
@@ -0,0 +1,18 @@
+#ifndef FUZZY_H
+#define FUZZY_H
+
+/*
+ * Find line numbers in "a" that match with lines in "b"
+ * Returns an array of either line indices or -1 where no match is found.
+ * The returned array must be free()d after use.
+ */
+int *fuzzy_find_matching_lines(const char *content_a,
+			       const char *content_b,
+			       const int *line_starts_a,
+			       const int *line_starts_b,
+			       int start_a,
+			       int start_b,
+			       int length_a,
+			       int length_b);
+
+#endif
-- 
2.21.0

Re: [PATCH v6 0/6] blame: add the ability to ignore commits

[Barret Rhoden]

On 4/22/19 6:26 PM, michael@platin.gs wrote:
> From: Michael Platings <michael@platin.gs>
> 
> Hi Barret,
> 
> This patch is on top of your patch v6 4/6.

Thanks, I'll take a look.  I was working on taking your old version and 
integrating it with my v6 6/6.  That way it gets the 
origin-fingerprint-filling code and can be easily compared to my 6/6 style.

[snip]

> 
> To address reordered lines I suggest a combination of this algorithm and your
> algorithm - in the first path my algorithm tries to match lines within a
> single chunk, and in the second pass your algorithm tries to find matches for
> unblamed lines out of order and outside their chunk.

I was thinking something similar.  Yesterday I did this with your older 
patch set - applied on my 6/6.  Two passes, one with your fuzzy matcher, 
then if we didn't find anything, do a scan of the entire parent (as my 
6/6 does now).

This approached worked for the cases I had (e.g. "header reordering"). 
I ran into an issue last night where your scan was finding matches where 
it shouldn't - might have been an issue with how I hooked it up.  I'll 
try your latest code and see how it goes.

Thanks,

Barret

Re: [PATCH v6 0/6] blame: add the ability to ignore commits

[Barret Rhoden]

Hi Michael -

On 4/22/19 6:26 PM, michael@platin.gs wrote:
> +	int *matching_lines = fuzzy_find_matching_lines(parent->file.ptr,
> +							target->file.ptr,
> +							parent->line_starts,
> +							target->line_starts,
> +							e->s_lno + offset,
> +							e->s_lno,
> +							parent_len,
> +							e->num_lines);

Here was the issue I ran into, and it's due to translations between 
e->s_lno and the parent's "address space".

The short version is that "e->s_lno + offset" is not always the 
parent_slno, and parent_len is based off of parent_slno.

guess_line_blames() gives you parent_slno and parent_len, as well as 
offset.  'offset' is how you convert from the target's space to the 
parent's.  parent_slno and parent_len describe the whole chunk given to 
us from the diff engine.  However, there may be multiple blame_entries 
covering that chunk.

So e->s_lno is in the target, but it's not necessarily the beginning of 
the entire diff chunk.  This is related to that page fault you found a 
while back.

Passing e->s_lno + offset for where fuzzy() starts looking in the parent 
is fine, but then the length in the parent needs to be adjusted.  For 
instance, I have this at the top of my modified 
fuzzy_find_matching_lines() (changed to take the origins and variables 
from guess_line_blames()):

         // XXX conversions to michael's variable names
	int start_a = e->s_lno + offset;
         //int length_a = parent_len;    // XXX this fails the test
         int length_a = (parent_slno + parent_len) - (e->s_lno + offset);

	int start_b = e->s_lno;
         int length_b = e->num_lines;

Plus we need a check for length_a <= 0.  I had to work to make it be 
negative, but it's possible.  parent_slno = tlno + offset, so we're 
looking at:

	length_a = tlno + parent_len - e->s_lno;

That just requires a blame entry split such that e->s_lno > tlno, and a 
parent chunk that had 0 lines.  I found a case that did that.  Basically 
in one commit you add a bunch of lines.  In another, you change one line 
in the middle of that bunch.  That causes a split of the diff chunk into 
more than one, such that e->s_lno > tlno.  That original commit only 
added lines, so parent_len == 0.

The intuition for the "negative length_a" isn't that the parent_len is 
negative, it's that the e->s_lno chunk (when offset) is outside the 
window of the parent's change.  I have a simple test for this.

Oh, and we have to length_a == 0, due to this:

	max_search_distance = length_a - 1;

Anyway, I'll take what I've got and apply your latest and see what I 
come up with.  =)  Plus, I have fixes for all of the other stuff brought 
up in the v6 discussion.

Barret

Re: [PATCH v6 0/6] blame: add the ability to ignore commits

[Barret Rhoden]

Hi Michael -

FYI, here are a few style nits that I changed in my version, based on a 
quick scan.  Not sure if these are all Git's style, but I think it's 
mostly linux-kernel style.

I mention this mostly for future reference - specifically if we keep 
separate versions of this code.  Hopefully we won't.  =)

I also did all the fingerprint prep in fill_origin_blob, which you can 
see in an upcoming patch.

On 4/22/19 6:26 PM, michael@platin.gs wrote:
> diff --git a/fuzzy.c b/fuzzy.c
> new file mode 100644
> index 0000000000..c5b09a0eb7
> --- /dev/null
> +++ b/fuzzy.c
> @@ -0,0 +1,434 @@
> +#include "fuzzy.h"
> +#include <ctype.h>
> +#include <stdint.h>
> +#include <stdlib.h>
> +#include <string.h>
> +#include "git-compat-util.h"
> +#include "hashmap.h"
> +
> +struct fingerprint_entry {
> +	struct hashmap_entry entry;
> +	int count;
> +};
> +struct fingerprint {
> +	struct hashmap map;
> +	struct fingerprint_entry *entries;
> +};
> +
> +static void get_fingerprint(struct fingerprint *result,
> +			    const char *line_begin,
> +			    const char *line_end) {
                                                  ^newline here, so { is 
at the start of a line.  (on all of the functions)

> +	unsigned hash;
                 ^int

> +	char c0, c1;
> +	int map_entry_count = line_end - line_begin - 1;
> +	struct fingerprint_entry *entry = xcalloc(map_entry_count,
> +		sizeof(struct fingerprint_entry));
> +	struct fingerprint_entry *found_entry;

Blank line here, between declarations and code.  Did this for all of the 
functions.

> +	hashmap_init(&result->map, NULL, NULL, map_entry_count);
> +	result->entries = entry;
> +	for (const char *p = line_begin; p + 1 < line_end; ++p, ++entry) {
              ^moved this declaration outside the for loop

> +		c0 = *p;
> +		c1 = *(p + 1);
> +		/* Ignore whitespace pairs */
> +		if (isspace(c0) && isspace(c1))
> +			continue;
> +		hash = tolower(c0) | (tolower(c1) << 8);
> +		hashmap_entry_init(entry, hash);
> +
> +		if ((found_entry = hashmap_get(&result->map, entry, NULL))) {
                     ^moved this assignment outside the if ()
> +			found_entry->count += 1;
> +		}
> +		else {
                 ^ made this } else {.

Also in a couple other places below.

> +			entry->count = 1;
> +			hashmap_add(&result->map, entry);
> +		}
> +	}
> +}
> +
> +static void free_fingerprint(struct fingerprint *f) {
> +	hashmap_free(&f->map, 0);
> +	free(f->entries);
> +}
> +
> +static int fingerprint_similarity(struct fingerprint *a,
> +				  struct fingerprint *b) {

put fingerprint b on the same line as a (within 80 chars).  made similar 
changes wherever that was possible and looked nice.

> +	int intersection = 0;
> +	struct hashmap_iter iter;
> +	const struct fingerprint_entry *entry_a, *entry_b;
> +	hashmap_iter_init(&b->map, &iter);
> +
> +	while ((entry_b = hashmap_iter_next(&iter))) {
> +		if ((entry_a = hashmap_get(&a->map, entry_b, NULL))) {
> +			intersection += entry_a->count < entry_b->count ?
> +					entry_a->count : entry_b->count;
> +		}
> +	}
> +	return intersection;
> +}
> +
> +static void fingerprint_subtract(struct fingerprint *a,
> +				 struct fingerprint *b) {
> +	struct hashmap_iter iter;
> +	struct fingerprint_entry *entry_a;
> +	const struct fingerprint_entry *entry_b;
> +	hashmap_iter_init(&b->map, &iter);
> +
> +	while ((entry_b = hashmap_iter_next(&iter))) {
> +		if ((entry_a = hashmap_get(&a->map, entry_b, NULL))) {
> +			if (entry_a->count <= entry_b->count) {
> +				hashmap_remove(&a->map, entry_b, NULL);
> +			}
> +			else {
> +				entry_a->count -= entry_b->count;
> +			}
> +		}
> +	}
> +}
> +
> +static void get_line_fingerprints(struct fingerprint *fingerprints,
> +				  const char *content,
> +				  const int *line_starts,
> +				  long chunk_start,
> +				  long chunk_length) {
> +	int i;
> +	const char *linestart, *lineend;
> +	line_starts += chunk_start;
> +	for (i = 0; i != chunk_length; ++i) {
                       ^ any reason for '!=' versus '<'  ?

> +		linestart = content + line_starts[i];
> +		lineend = content + line_starts[i + 1];
> +		get_fingerprint(fingerprints + i, linestart, lineend);
> +	}
> +}
> +
> +static int get_closest_local_line(int start_a,
> +			    int local_line_b,
> +			    int closest_line_calc_offset1,
> +			    int closest_line_calc_offset2,
> +			    int closest_line_calc_numerator,
> +			    int closest_line_calc_denominator) {
> +	return ((local_line_b + closest_line_calc_offset1) * 2 + 1) *
> +		closest_line_calc_numerator /
> +		(closest_line_calc_denominator * 2) +
> +		closest_line_calc_offset2 - start_a;
                ^ i moved these three lines one space left, so that they 
don't line up with the open paren.  o/w it looked like they may be 
inside the '('.


> +}
> +
> +static int *get_similarity(int *similarities, int max_search_distance_a,
> +			   int local_line_a, int local_line_b,
> +			   int closest_local_line_a) {
> +	assert(abs(local_line_a - closest_local_line_a) <= max_search_distance_a);
> +	return similarities + local_line_a - closest_local_line_a +
> +		max_search_distance_a +
> +		local_line_b * (max_search_distance_a * 2 + 1);
> +}
> +
> +#define CERTAIN_NOTHING_MATCHES -2
> +#define CERTAINTY_NOT_CALCULATED -1
> +
> +static void find_best_line_matches(const int max_search_distance_a,
> +				   int start_a,
> +				   int length_a,
> +				   int local_line_b,
> +				   struct fingerprint *fingerprints_a,
> +				   struct fingerprint *fingerprints_b,
> +				   int *similarities,
> +				   int *certainties,
> +				   int *second_best_result,
> +				   int *result,
> +				   int closest_line_calc_offset1,
> +				   int closest_line_calc_offset2,
> +				   int closest_line_calc_numerator,
> +				   int closest_line_calc_denominator) {

                                    ^intense number of arguments.  =)

Not sure if there's much to do about that.  It does make some of the 
callsites busier.

> +
> +	int i, search_start, search_end, closest_local_line_a, *similarity,
> +		best_similarity = 0, second_best_similarity = 0,
> +		best_similarity_index = 0, second_best_similarity_index = 0;
> +
> +	if (certainties[local_line_b] != CERTAINTY_NOT_CALCULATED)
> +		return;
> +
> +	closest_local_line_a = get_closest_local_line(start_a,
> +					  local_line_b,
> +					  closest_line_calc_offset1,
> +					  closest_line_calc_offset2,
> +					  closest_line_calc_numerator,
> +					  closest_line_calc_denominator);
> +
> +	search_start = closest_local_line_a - max_search_distance_a;
> +	if (search_start < 0)
> +		search_start = 0;
> +
> +	search_end = closest_local_line_a + max_search_distance_a + 1;
> +	if (search_end > length_a)
> +		search_end = length_a;
> +
> +	for (i = search_start; i < search_end; ++i) {
> +		similarity = get_similarity(similarities, max_search_distance_a,
> +					    i, local_line_b,
> +					    closest_local_line_a);
> +		if (*similarity == -1) {
> +			*similarity = fingerprint_similarity(
> +				fingerprints_b + local_line_b,
> +				fingerprints_a + i) *
> +				(1000 - abs(i - closest_local_line_a));
> +		}
> +		if (*similarity > best_similarity) {
> +			second_best_similarity = best_similarity;
> +			second_best_similarity_index = best_similarity_index;
> +			best_similarity = *similarity;
> +			best_similarity_index = i;
> +		}
> +		else if (*similarity > second_best_similarity) {
> +			second_best_similarity = *similarity;
> +			second_best_similarity_index = i;
> +		}
> +	}
> +
> +	if (best_similarity == 0) {
> +		certainties[local_line_b] = CERTAIN_NOTHING_MATCHES;
> +		result[local_line_b] = -1;
> +	}
> +	else {
> +		certainties[local_line_b] = best_similarity * 2 -
> +			second_best_similarity;
> +		result[local_line_b] = start_a + best_similarity_index;
> +		second_best_result[local_line_b] =
> +			start_a + second_best_similarity_index;
> +	}
> +}
> +
> +/*
> + * This finds the line that we can match with the most confidence, and
> + * uses it as a partition. It then calls itself on the lines on either side of
> + * that partition. In this way we avoid lines appearing out of order, and
> + * retain a sensible line ordering.
> + */
> +static void fuzzy_find_matching_lines_recurse(
> +	int max_search_distance_a,
> +	int max_search_distance_b,
> +	int start_a, int start_b,
> +	int length_a, int length_b,
> +	struct fingerprint *fingerprints_a,
> +	struct fingerprint *fingerprints_b,
> +	int *similarities,
> +	int *certainties,
> +	int *second_best_result,
> +	int *result,
> +	int closest_line_calc_offset1,
> +	int closest_line_calc_offset2,
> +	int closest_line_calc_numerator,
> +	int closest_line_calc_denominator) {
> +
> +	int i, barrier, invalidate_min, invalidate_max, offset_b,
> +		second_half_start_a, second_half_start_b,
> +		second_half_length_a, second_half_length_b,
> +		most_certain_line_a, most_certain_local_line_b = -1,
> +		most_certain_line_certainty = -1,
> +		closest_local_line_a;
> +
> +	for (i = 0; i < length_b; ++i) {
> +		find_best_line_matches(max_search_distance_a,
> +				       start_a,
> +				       length_a,
> +				       i,
> +				       fingerprints_a,
> +				       fingerprints_b,
> +				       similarities,
> +				       certainties,
> +				       second_best_result,
> +				       result,
> +				       closest_line_calc_offset1,
> +				       closest_line_calc_offset2,
> +				       closest_line_calc_numerator,
> +				       closest_line_calc_denominator);
> +
> +		if (certainties[i] > most_certain_line_certainty) {
> +			most_certain_line_certainty = certainties[i];
> +			most_certain_local_line_b = i;
> +		}
> +	}
> +
> +	if (most_certain_local_line_b == -1) {
> +		return;
> +	}
         ^ removed the {} for a single-line if block.

> +
> +	most_certain_line_a = result[most_certain_local_line_b];
> +
> +	/* Subtract the most certain line's fingerprint in b from the
> +	 matched fingerprint in a. This means that other lines in b can't also
> +	 match the same parts of the line in a. */
         ^ multiline block commits as such:
         /*
          * foo
          * bar
          */
> +	fingerprint_subtract(fingerprints_a + most_certain_line_a - start_a,
> +			     fingerprints_b + most_certain_local_line_b);
> +
> +
> +	/* Invalidate results that may be affected by the choice of pivot. */
> +	invalidate_min = most_certain_local_line_b - max_search_distance_b;
> +	invalidate_max = most_certain_local_line_b + max_search_distance_b + 1;
> +	if (invalidate_min < 0)
> +		invalidate_min = 0;
> +	if (invalidate_max > length_b)
> +		invalidate_max = length_b;
> +
> +	for (i = invalidate_min; i < invalidate_max; ++i) {
> +		closest_local_line_a = get_closest_local_line(
> +			start_a, i,
> +			closest_line_calc_offset1,
> +			closest_line_calc_offset2,
> +			closest_line_calc_numerator,
> +			closest_line_calc_denominator);
> +		*get_similarity(similarities, max_search_distance_a,
> +				most_certain_line_a - start_a, i,
> +				closest_local_line_a) = -1;
> +	}
> +
> +	barrier = most_certain_line_a;
> +
> +	for (i = most_certain_local_line_b - 1; i >= invalidate_min; --i) {
> +		if (certainties[i] >= 0 &&
> +		    (result[i] >= barrier || second_best_result[i] >= barrier)) {

over 80 chars (same below)

> +			    certainties[i] = CERTAINTY_NOT_CALCULATED;
> +			    barrier = result[i];
> +			    invalidate_min = i - max_search_distance_b;
> +			    if (invalidate_min < 0)
> +				    invalidate_min = 0;
> +		    }
> +	}
> +
> +	barrier = most_certain_line_a;
> +
> +	for (i = most_certain_local_line_b + 1; i < invalidate_max; ++i) {
> +		if (certainties[i] >= 0 &&
> +		    (result[i] <= barrier || second_best_result[i] <= barrier)) {
> +			    certainties[i] = CERTAINTY_NOT_CALCULATED;
> +			    barrier = result[i];
> +			    invalidate_max = i + max_search_distance_b + 1;
> +			    if (invalidate_max > length_b)
> +				    invalidate_max = length_b;
> +		    }
> +	}
> +
> +
> +	if (most_certain_local_line_b > 0) {
> +		fuzzy_find_matching_lines_recurse(
> +			max_search_distance_a,
> +			max_search_distance_b,
> +			start_a, start_b,
> +			most_certain_line_a + 1 - start_a,
> +			most_certain_local_line_b,
> +			fingerprints_a, fingerprints_b, similarities,
> +			certainties, second_best_result, result,
> +			closest_line_calc_offset1, closest_line_calc_offset2,
> +			closest_line_calc_numerator,
> +			closest_line_calc_denominator);
> +	}
> +	if (most_certain_local_line_b + 1 < length_b) {
> +		second_half_start_a = most_certain_line_a;
> +		offset_b = most_certain_local_line_b + 1;
> +		second_half_start_b = start_b + offset_b;
> +		second_half_length_a =
> +			length_a + start_a - second_half_start_a;
> +		second_half_length_b =
> +			length_b + start_b - second_half_start_b;
> +		fuzzy_find_matching_lines_recurse(
> +			max_search_distance_a,
> +			max_search_distance_b,
> +			second_half_start_a, second_half_start_b,
> +			second_half_length_a, second_half_length_b,
> +			fingerprints_a + second_half_start_a - start_a,
> +			fingerprints_b + offset_b,
> +			similarities +
> +				offset_b * (max_search_distance_a * 2 + 1),
> +			certainties + offset_b,
> +			second_best_result + offset_b, result + offset_b,
> +			closest_line_calc_offset1 + offset_b,
> +			closest_line_calc_offset2,
> +			closest_line_calc_numerator,
> +			closest_line_calc_denominator);
> +	}
> +}
> +
> +int *fuzzy_find_matching_lines(const char *content_a,
> +			       const char *content_b,
> +			       const int *line_starts_a,
> +			       const int *line_starts_b,
> +			       int start_a,
> +			       int start_b,
> +			       int length_a,
> +			       int length_b) {
> +
> +	int i, *result, *second_best_result,
> +		*certainties, *similarities, similarity_count;
> +	struct fingerprint *fingerprints_a, *fingerprints_b;
> +
> +	/* max_search_distance_a means that given a line in `b`, compare it to
> +	the line in `a` that is closest to its position, and the lines in `a`
> +	that are no greater than max_search_distance_a lines away from the
> +	closest line in `a`.
> +	max_search_distance_b is an upper bound on the greatest possible
> +	distance between lines in `b` such that they will both be compared with
> +	the same line in `a` according to max_search_distance_a. */
> +	int max_search_distance_a = 10, max_search_distance_b;
> +
> +	if (max_search_distance_a >= length_a)
> +		max_search_distance_a = length_a ? length_a - 1 : 0;
> +
> +	if (length_a == 0) {
> +		max_search_distance_b = 0;
> +	}
> +	else {
> +		max_search_distance_b = ((2 * max_search_distance_a + 1) *
> +			length_b - 1) / length_a;
> +	}
> +
> +	result = malloc(sizeof(int) * length_b);
> +	second_best_result = malloc(sizeof(int) * length_b);
> +	certainties = malloc(sizeof(int) * length_b);
> +	similarity_count = length_b * (max_search_distance_a * 2 + 1);
> +	similarities = malloc(sizeof(int) * similarity_count);

xcalloc(x, y) instead of malloc (x * y).  or at least xmalloc.

> +
> +	for (i = 0; i < length_b; ++i) {
> +		result[i] = -1;
> +		second_best_result[i] = -1;
> +		certainties[i] = CERTAINTY_NOT_CALCULATED;
> +	}
> +
> +	for (i = 0; i < similarity_count; ++i) {
> +		similarities[i] = -1;
> +	}
	^ removed {}, as as with the 'if' statements


Barret



> +
> +	fingerprints_a = xmalloc(sizeof(struct fingerprint) * length_a);
> +	fingerprints_b = xmalloc(sizeof(struct fingerprint) * length_b);
> +
> +	get_line_fingerprints(fingerprints_a, content_a,
> +			      line_starts_a,
> +			      start_a, length_a);
> +	get_line_fingerprints(fingerprints_b, content_b,
> +			      line_starts_b,
> +			      start_b, length_b);
> +
> +	fuzzy_find_matching_lines_recurse(max_search_distance_a,
> +					  max_search_distance_b,
> +					  start_a, start_b,
> +					  length_a, length_b,
> +					  fingerprints_a,
> +					  fingerprints_b,
> +					  similarities,
> +					  certainties,
> +					  second_best_result,
> +					  result,
> +					  0, start_a, length_a, length_b);
> +
> +	for (i = 0; i < length_b; ++i) {
> +		free_fingerprint(fingerprints_b + i);
> +	}
> +	for (i = 0; i < length_a; ++i) {
> +		free_fingerprint(fingerprints_a + i);
> +	}
> +	free(fingerprints_b);
> +	free(fingerprints_a);
> +	free(similarities);
> +	free(certainties);
> +	free(second_best_result);
> +
> +	return result;
> +}
> +

Re: [PATCH v6 0/6] blame: add the ability to ignore commits

[Barret Rhoden]

Hi Michael -

I cobbled something together that passes my old git tests and all but 
one of your tests, though an assertion fails when I use it for real. 
See below.

On 4/22/19 6:26 PM, michael@platin.gs wrote:
[snip]
> +static int *get_similarity(int *similarities, int max_search_distance_a,
> +			   int local_line_a, int local_line_b,
> +			   int closest_local_line_a) {
> +	assert(abs(local_line_a - closest_local_line_a) <= max_search_distance_a);

This assert fails.  In my example,
	local_line_a = 1
	closest_local_line_a = 12
	max_search_distance_a = 10

Backtrace tells me it was called here:

> +static void fuzzy_find_matching_lines_recurse(

[snip]

> +	for (i = invalidate_min; i < invalidate_max; ++i) {
> +		closest_local_line_a = get_closest_local_line(
> +			start_a, i,
> +			closest_line_calc_offset1,
> +			closest_line_calc_offset2,
> +			closest_line_calc_numerator,
> +			closest_line_calc_denominator);
> +		*get_similarity(similarities, max_search_distance_a,
> +				most_certain_line_a - start_a, i,
> +				closest_local_line_a) = -1;
> +	}

So it looks like that '12' came from get_closest_local_line(),  The args 
to that call were:

	start_a 258, i 3, off1 0, off2 258 num 83, denom 23

The equation reduces to 12 + off2 - start_a = 12

I don't know what those values mean, but it looks like A's values affect 
off2 and start_a, but those are only used at the very end of the 
calculation.  Does 'A' affect off1, numer, or denom?

Any thoughts?  What all is going on here?

If you want to play with it, it's at

	git@github.com:brho/git.git (master)

(Beware the push -f / forced update.  And I figured the repo would be 
preferable to spamming with unrelated patches).

If you want an example commit the assert fails on, it's this repo:
	
	git@github.com:brho/akaros.git
	master branch
	ignore-rev-file=.git-blame-ignore-revs
	file user/vmm/virtio_mmio.c

On an unrelated note:

 > The significant change here is that when a line is matched, its 
      > fingerprint is subtracted from the matched parent line's 
fingerprint. > This prevents two lines matching the same part of a 
parent line.

Does this limit us so that our second pass (the fallback when fuzzy 
failed) won't be able to match to a parent line that was already matched?


The test that is failing is your Expand Lines test.  The 'final' diff was:

--- a/1
+++ b/1
@@ -1,5 +1,7 @@
  aaa
-bbb
+bbbx
+bbbx
  ccc
-ddd
+dddx
+dddx
  eee

Which should be two diff chunks and two calls to guess_line_blames().

And the 'actual' was:

1
2
Final  (not 2)
3
4
Final  (not 2)
5

I didn't dig much, but your older stuff (when merged with mine) also 
didn't pass that test.  Maybe something with the offset/parent_slno stuff.

Thanks,

Barret

Re: [PATCH v6 0/6] blame: add the ability to ignore commits

[Barret Rhoden]

Hi Michael -

I dug into the code a bit more and have some more comments below.  Take 
anything I say with a grain of salt; I'm still trying to understand how 
it all works.  =)

If you do have updates to your patch, see if you can make it apply onto 
my branch at https://github.com/brho/git/commits/master.  I have a 
commit there called "WIP-michael-fuzzy", which is mostly all of your 
stuff plus the style changes and whatnot I was talking about.  Though if 
you give me something else, I can make that work too.

All in all, I think we're pretty close to having something cool.  =)

On 4/22/19 6:26 PM, michael@platin.gs wrote:

> @@ -0,0 +1,434 @@
> +#include "fuzzy.h"
> +#include <ctype.h>
> +#include <stdint.h>
> +#include <stdlib.h>
> +#include <string.h>
> +#include "git-compat-util.h"
> +#include "hashmap.h"
> +
> +struct fingerprint_entry {
> +	struct hashmap_entry entry;
> +	int count;
> +};
> +struct fingerprint {
> +	struct hashmap map;
> +	struct fingerprint_entry *entries;
> +};
> +

The whole fingerprinting section could use a good comment.  What is a 
fingerprint, why/how we use them, what it means to be similar, etc.

> +static void get_fingerprint(struct fingerprint *result,
> +			    const char *line_begin,
> +			    const char *line_end) {
> +	unsigned hash;
> +	char c0, c1;
> +	int map_entry_count = line_end - line_begin - 1;
> +	struct fingerprint_entry *entry = xcalloc(map_entry_count,
> +		sizeof(struct fingerprint_entry));
> +	struct fingerprint_entry *found_entry;
> +	hashmap_init(&result->map, NULL, NULL, map_entry_count);
> +	result->entries = entry;
> +	for (const char *p = line_begin; p + 1 < line_end; ++p, ++entry) {
> +		c0 = *p;
> +		c1 = *(p + 1);
> +		/* Ignore whitespace pairs */
> +		if (isspace(c0) && isspace(c1))
> +			continue;
> +		hash = tolower(c0) | (tolower(c1) << 8);
> +		hashmap_entry_init(entry, hash);
> +
> +		if ((found_entry = hashmap_get(&result->map, entry, NULL))) {
> +			found_entry->count += 1;
> +		}
> +		else {
> +			entry->count = 1;
> +			hashmap_add(&result->map, entry);
> +		}
> +	}
> +}

[snip]





> +static int get_closest_local_line(int start_a,
> +			    int local_line_b,
> +			    int closest_line_calc_offset1,
> +			    int closest_line_calc_offset2,
> +			    int closest_line_calc_numerator,
> +			    int closest_line_calc_denominator) {
> +	return ((local_line_b + closest_line_calc_offset1) * 2 + 1) *
> +		closest_line_calc_numerator /
> +		(closest_line_calc_denominator * 2) +
> +		closest_line_calc_offset2 - start_a;
> +}

Overall, I found the final four parameters (offset1, offset2, numer, and 
denom) to be confusing, used here and passed through all of the functions.

What are they exactly?  Do they ever change from the first invocation of 
fuzzy_find_matching_lines_recurse()?  The only one I saw that changed 
was 'closest_line_calc_offset1 + offset_b' in the upper half of the 
recursive call.

So if I'm following it correctly, closest_line_calc_offset2 is always == 
start_a, so then in what 'file space' does the return val from 
get_closest_local_line() reside?  A's space?  Relative number to the 
beginning of start_a?

What all is the closest_local_line?  The line in A that corresponds to 
the line in B, for some mapping function?  Maybe the corresponding 
fractional bit?  (hence the division, but there's also that *2 in there)

The assertion that trips for me is related to this - we get a 
closest_local_line_a that is farther than max_search_distance_a from 
local_line_a.

On a related note, any 1-1 offsetting between A and B seems precarious. 
It's the 'offset' variable passed in from guess_line_blames().  But if 
you're calculating it from start_b - start_a, that is a little brittle. 
start_b is the tiny window of e->s_lno.  If we ever change things to 
look into the entire diff chunk (the one passed to guess_line_blames()), 
then that will break.  Not sure if you're offsetting in this manner or 
not.  (looks like 'no').

> +
> +static int *get_similarity(int *similarities, int max_search_distance_a,
> +			   int local_line_a, int local_line_b,
> +			   int closest_local_line_a) {
> +	assert(abs(local_line_a - closest_local_line_a) <= max_search_distance_a);
> +	return similarities + local_line_a - closest_local_line_a +
> +		max_search_distance_a +
> +		local_line_b * (max_search_distance_a * 2 + 1);
> +}

This needs some sort of comment.  From it's allocation below (and from 
staring at the code long enough), I gather the similarities array is a 
2D array, "each line in B" by "each line in a window (of size X) in A 
centered on some line in A mapping to B", where X is 
(max_search_distance_a * 2 + 1), and 'some line' is closest_local_line_a.

Is this something like "for line b, get sim for local_line a"?  Is it 
local_line_a or closest_local_line_a that we are getting?  It's not 
clear from the prototype alone.

Maybe the 'closest_local_line_a' ought to be decided inside this 
function, so it's a simpler-looking 'getter.'  Or better yet, maybe 
there's a lookup array mapping B -> "window in A".  (more on this later).

> +
> +#define CERTAIN_NOTHING_MATCHES -2
> +#define CERTAINTY_NOT_CALCULATED -1
> +
> +static void find_best_line_matches(const int max_search_distance_a,
> +				   int start_a,
> +				   int length_a,
> +				   int local_line_b,
> +				   struct fingerprint *fingerprints_a,
> +				   struct fingerprint *fingerprints_b,

I was a little worried about keeping track of what offset / "address 
space" we're in.  The fingerprint arrays passed in are both set so the 
0th member corresponds to the FP for start_a or start_b, with length_a 
or length_b members.

start_a and local_line_b are in different types spaces: start_a is 
absolute in 'A' and local_line_b is relative in 'B'.  Eventually, I 
figured out that that is what 'local' meant.  Seeing both start_a 
(absolute) and local_line_b (relative) passed in made me worry a little 
about whether or not there was a bug.  Maybe compute and pass in the 
local_a_line instead?

I see later on that you use start_a in this function so you can store 
result[] and second_best_result[] in A's absolute space.

It might make sense to pick a space (absolute or relative) and use it 
throughout.

> +				   int *similarities,
> +				   int *certainties,
> +				   int *second_best_result,
> +				   int *result,
> +				   int closest_line_calc_offset1,
> +				   int closest_line_calc_offset2,
> +				   int closest_line_calc_numerator,
> +				   int closest_line_calc_denominator) {
> +
> +	int i, search_start, search_end, closest_local_line_a, *similarity,
> +		best_similarity = 0, second_best_similarity = 0,
> +		best_similarity_index = 0, second_best_similarity_index = 0;
> +
> +	if (certainties[local_line_b] != CERTAINTY_NOT_CALCULATED)
> +		return;
> +
> +	closest_local_line_a = get_closest_local_line(start_a,
> +					  local_line_b,
> +					  closest_line_calc_offset1,
> +					  closest_line_calc_offset2,
> +					  closest_line_calc_numerator,
> +					  closest_line_calc_denominator);
> +
> +	search_start = closest_local_line_a - max_search_distance_a;
> +	if (search_start < 0)
> +		search_start = 0;
> +
> +	search_end = closest_local_line_a + max_search_distance_a + 1;
> +	if (search_end > length_a)
> +		search_end = length_a;
> +
> +	for (i = search_start; i < search_end; ++i) {
> +		similarity = get_similarity(similarities, max_search_distance_a,
> +					    i, local_line_b,
> +					    closest_local_line_a);
> +		if (*similarity == -1) {
> +			*similarity = fingerprint_similarity(
> +				fingerprints_b + local_line_b,
> +				fingerprints_a + i) *
> +				(1000 - abs(i - closest_local_line_a));

Need some assertion that "1000 > 2*max_search_distance_a + 1" or 
something?  I know that number is '21', but it's based on a hard-coded 
integer somewhere else.

> +		}
> +		if (*similarity > best_similarity) {
> +			second_best_similarity = best_similarity;
> +			second_best_similarity_index = best_similarity_index;
> +			best_similarity = *similarity;
> +			best_similarity_index = i;
> +		}
> +		else if (*similarity > second_best_similarity) {
> +			second_best_similarity = *similarity;
> +			second_best_similarity_index = i;
> +		}
> +	}
> +
> +	if (best_similarity == 0) {
> +		certainties[local_line_b] = CERTAIN_NOTHING_MATCHES;
> +		result[local_line_b] = -1;
> +	}
> +	else {
> +		certainties[local_line_b] = best_similarity * 2 -
> +			second_best_similarity;
> +		result[local_line_b] = start_a + best_similarity_index;
> +		second_best_result[local_line_b] =
> +			start_a + second_best_similarity_index;
> +	}
> +}
> +
> +/*
> + * This finds the line that we can match with the most confidence, and
> + * uses it as a partition. It then calls itself on the lines on either side of
> + * that partition. In this way we avoid lines appearing out of order, and
> + * retain a sensible line ordering.
> + */
> +static void fuzzy_find_matching_lines_recurse(
> +	int max_search_distance_a,
> +	int max_search_distance_b,
> +	int start_a, int start_b,
> +	int length_a, int length_b,
> +	struct fingerprint *fingerprints_a,
> +	struct fingerprint *fingerprints_b,
> +	int *similarities,
> +	int *certainties,
> +	int *second_best_result,
> +	int *result,
> +	int closest_line_calc_offset1,
> +	int closest_line_calc_offset2,
> +	int closest_line_calc_numerator,
> +	int closest_line_calc_denominator) {

For all of the arguments that never change, which seem to be the last 
three args and the search distances, you could consider putting them in 
a struct and passing that along.  Similarly, the only time the 
fingerprints and the four int arrays change is in the upper half of the 
recursive call.

You might be able to put most all of those array args into the args 
struct too, such that that struct always represents the original window 
(or even the absolute numbers?), and then pass along the offsets. 
You're somewhat doing that already when you pass second_half_start_a, 
second_half_start_b (which includes offset_b), etc, down below.

> +
> +	int i, barrier, invalidate_min, invalidate_max, offset_b,
> +		second_half_start_a, second_half_start_b,
> +		second_half_length_a, second_half_length_b,
> +		most_certain_line_a, most_certain_local_line_b = -1,
> +		most_certain_line_certainty = -1,
> +		closest_local_line_a;
> +
> +	for (i = 0; i < length_b; ++i) {
> +		find_best_line_matches(max_search_distance_a,
> +				       start_a,
> +				       length_a,
> +				       i,
> +				       fingerprints_a,
> +				       fingerprints_b,
> +				       similarities,
> +				       certainties,
> +				       second_best_result,
> +				       result,
> +				       closest_line_calc_offset1,
> +				       closest_line_calc_offset2,
> +				       closest_line_calc_numerator,
> +				       closest_line_calc_denominator);
> +
> +		if (certainties[i] > most_certain_line_certainty) {
> +			most_certain_line_certainty = certainties[i];
> +			most_certain_local_line_b = i;
> +		}
> +	}
> +
> +	if (most_certain_local_line_b == -1) {
> +		return;
> +	}
> +
> +	most_certain_line_a = result[most_certain_local_line_b];
> +
> +	/* Subtract the most certain line's fingerprint in b from the
> +	 matched fingerprint in a. This means that other lines in b can't also
> +	 match the same parts of the line in a. */
> +	fingerprint_subtract(fingerprints_a + most_certain_line_a - start_a,
> +			     fingerprints_b + most_certain_local_line_b);

FYI, if I comment out fingerprint_subtract, this will pass your test 2 
(currently failing), but fail test 5 (currently passing).

> +
> +
> +	/* Invalidate results that may be affected by the choice of pivot. */
> +	invalidate_min = most_certain_local_line_b - max_search_distance_b;
> +	invalidate_max = most_certain_local_line_b + max_search_distance_b + 1;
> +	if (invalidate_min < 0)
> +		invalidate_min = 0;
> +	if (invalidate_max > length_b)
> +		invalidate_max = length_b;
> +
> +	for (i = invalidate_min; i < invalidate_max; ++i) {
> +		closest_local_line_a = get_closest_local_line(
> +			start_a, i,
> +			closest_line_calc_offset1,
> +			closest_line_calc_offset2,
> +			closest_line_calc_numerator,
> +			closest_line_calc_denominator);
> +		*get_similarity(similarities, max_search_distance_a,
> +				most_certain_line_a - start_a, i,
> +				closest_local_line_a) = -1;

The assert in get_similarity fails on my example when called from here. 
I guess something went wrong with finding the window center.

> +	}
> +
> +	barrier = most_certain_line_a;
> +
> +	for (i = most_certain_local_line_b - 1; i >= invalidate_min; --i) {
> +		if (certainties[i] >= 0 &&
> +		    (result[i] >= barrier || second_best_result[i] >= barrier)) {
> +			    certainties[i] = CERTAINTY_NOT_CALCULATED;
> +			    barrier = result[i];
> +			    invalidate_min = i - max_search_distance_b;
> +			    if (invalidate_min < 0)
> +				    invalidate_min = 0;
> +		    }
> +	}

Is it important for this function (above) to go in descending order, and 
the next to go in ascending order?  If you can go i = 0; i<foo; i++ for 
both, then maybe a helper function can replace both of these functions 
(above and below this comment).

> +
> +	barrier = most_certain_line_a;
> +
> +	for (i = most_certain_local_line_b + 1; i < invalidate_max; ++i) {
> +		if (certainties[i] >= 0 &&
> +		    (result[i] <= barrier || second_best_result[i] <= barrier)) {
> +			    certainties[i] = CERTAINTY_NOT_CALCULATED;
> +			    barrier = result[i];
> +			    invalidate_max = i + max_search_distance_b + 1;
> +			    if (invalidate_max > length_b)
> +				    invalidate_max = length_b;
> +		    }
> +	}

What's the intuition behind the steps to invalidate the results?

It looks like you want to reset the similarity calculations for any 
other line in B that was compared to the matching A line, so that that A 
line is not matched again until its similarity is recomputed (due to the 
"fingerprint subtraction"?).

You limit it to invalidate_min and max, then clamp those to the real 
min/max (0, length_b).  Initially, I thought that's a performance 
optimization (vs correctness) since you want to limit recalculations. 
Though I think the assumption is that you'll never ask for a 
get_similarity(a, b) where A is outside the reachable radius of B 
(max_search_distance_b).

What about with the certainties?  It seems like you're trying to limit 
which ones get reset.  Why do you check result[i] <= barrier, instead of 
just equality?

> +
> +
> +	if (most_certain_local_line_b > 0) {
> +		fuzzy_find_matching_lines_recurse(
> +			max_search_distance_a,
> +			max_search_distance_b,
> +			start_a, start_b,
> +			most_certain_line_a + 1 - start_a,
> +			most_certain_local_line_b,
> +			fingerprints_a, fingerprints_b, similarities,
> +			certainties, second_best_result, result,
> +			closest_line_calc_offset1, closest_line_calc_offset2,
> +			closest_line_calc_numerator,
> +			closest_line_calc_denominator);
> +	}
> +	if (most_certain_local_line_b + 1 < length_b) {
> +		second_half_start_a = most_certain_line_a;
> +		offset_b = most_certain_local_line_b + 1;
> +		second_half_start_b = start_b + offset_b;
> +		second_half_length_a =
> +			length_a + start_a - second_half_start_a;
> +		second_half_length_b =
> +			length_b + start_b - second_half_start_b;
> +		fuzzy_find_matching_lines_recurse(
> +			max_search_distance_a,
> +			max_search_distance_b,
> +			second_half_start_a, second_half_start_b,
> +			second_half_length_a, second_half_length_b,
> +			fingerprints_a + second_half_start_a - start_a,
> +			fingerprints_b + offset_b,
> +			similarities +
> +				offset_b * (max_search_distance_a * 2 + 1),
> +			certainties + offset_b,
> +			second_best_result + offset_b, result + offset_b,
> +			closest_line_calc_offset1 + offset_b,
> +			closest_line_calc_offset2,
> +			closest_line_calc_numerator,
> +			closest_line_calc_denominator);
> +	}
> +}
> +
> +int *fuzzy_find_matching_lines(const char *content_a,
> +			       const char *content_b,
> +			       const int *line_starts_a,
> +			       const int *line_starts_b,
> +			       int start_a,
> +			       int start_b,
> +			       int length_a,
> +			       int length_b) {
> +
> +	int i, *result, *second_best_result,
> +		*certainties, *similarities, similarity_count;
> +	struct fingerprint *fingerprints_a, *fingerprints_b;
> +
> +	/* max_search_distance_a means that given a line in `b`, compare it to
> +	the line in `a` that is closest to its position, and the lines in `a`
> +	that are no greater than max_search_distance_a lines away from the
> +	closest line in `a`.
> +	max_search_distance_b is an upper bound on the greatest possible
> +	distance between lines in `b` such that they will both be compared with
> +	the same line in `a` according to max_search_distance_a. */
> +	int max_search_distance_a = 10, max_search_distance_b;
> +
> +	if (max_search_distance_a >= length_a)
> +		max_search_distance_a = length_a ? length_a - 1 : 0;
> +
> +	if (length_a == 0) {
> +		max_search_distance_b = 0;
> +	}
> +	else {
> +		max_search_distance_b = ((2 * max_search_distance_a + 1) *
> +			length_b - 1) / length_a;
> +	}

A few questions / comments about these search distances:

- max_search_distance_a and _b sounds like different concepts.  maybe 
different names?  it's also hard to follow how you get these numbers, 
especially since it seems there is some scaling involved when converting 
from A space to B space.

- is the max_search_distance_a limited to 10 for performance reasons? 
conceptually, it'd be easier the similarities array was length_b * 
length_a.  instead, it sounds like every line B has a (potentially) 
separate window into A.  maybe it'd be simpler to have another array 
that tracks for each B, which line in A is the *start* of its window. 
that'd also make me rest easier when worrying about odd numbers, 
division, and off-by-one issues.

- the (2 * max_search_distance_a + 1) comes up a lot.  similarly, that 
calculation involving dividing by length_a comes up too.  maybe 
encapsulate those in some other smaller set of functions, so it's clear 
when they are being used for the same purpose.  i'm having a hard time 
convincing myself there aren't off-by-one issues.  (not that there are).

Thanks,

Barret