blame: add the ability to ignore commits
v5 cover blame: add the ability to ignore commits
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 is an RFC, and the others could be merged without it. That last patch 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.
The last patch needs a little work still - there's a TODO section in its commit message. It includes some of Michael's code, so if we are going to keep it, I'd like to sort out authorship correctly.
v4 -> v5
v4: https://public-inbox.org/git/[email protected]/
- 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/[email protected]/
- 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/[email protected]/
- 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/[email protected]/
- 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/[email protected]/
- 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: optionally track the line starts during fill_blame_origin()
blame: add the ability to ignore commits and their changes
blame: add a config option to mark ignored lines
RFC blame: use a fingerprint heuristic to match ignored lines
Documentation/blame-options.txt | 16 ++ Documentation/config/blame.txt | 11 + Documentation/git-blame.txt | 1 + blame.c | 384 +++++++++++++++++++++++++++----- blame.h | 6 + builtin/blame.c | 51 +++++ fsck.c | 37 +-- oidset.c | 35 +++ oidset.h | 8 + t/t5504-fetch-receive-strict.sh | 14 +- t/t8013-blame-ignore-revs.sh | 201 +++++++++++++++++ 11 files changed, 665 insertions(+), 99 deletions(-) create mode 100755 t/t8013-blame-ignore-revs.sh
Signature · 1 line
2.21.0.392.gf8f6787159e-goog
PATCH v5 1/6 Move init_skiplist() outside of fsck
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.
--- fsck.c | 37 +-------------------------------- oidset.c | 35 +++++++++++++++++++++++++++++++ oidset.h | 8 +++++++ t/t5504-fetch-receive-strict.sh | 14 ++++++------- 4 files changed, 51 insertions(+), 43 deletions(-)
fsck.c +1 -36
@@ -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 ; }
oidset.c +35 -0
@@ -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); +}
oidset.h +8 -0
@@ -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;
t/t5504-fetch-receive-strict.sh +7 -7
@@ -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
Signature · 1 line
2.21.0.392.gf8f6787159e-goog
PATCH v5 2/6 blame: use a helper function in blame_chunk()
In reply to Barret RhodenThe 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.
--- blame.c | 44 ++++++++++++++++++++++++++++---------------- 1 file changed, 28 insertions(+), 16 deletions(-)
blame.c +28 -16
@@ -838,6 +838,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
@@ -864,14 +885,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;
@@ -918,14 +934,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;
Signature · 1 line
2.21.0.392.gf8f6787159e-goog
PATCH v5 5/6 blame: add a config option to mark ignored lines
In reply to Barret RhodenWhen 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.
This patch adds a config option to identify these 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.
--- Documentation/config/blame.txt | 4 ++++ blame.c | 4 ++++ blame.h | 1 + builtin/blame.c | 9 +++++++++ t/t8013-blame-ignore-revs.sh | 33 +++++++++++++++++++++++++++++++++ 5 files changed, 51 insertions(+)
Documentation/config/blame.txt +4 -0
@@ -26,3 +26,7 @@ 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.markIgnoredLines:: + Mark lines that were changed by an ignored revision with a '*' in the + output of linkgit:git-blame[1].
blame.c +4 -0
@@ -515,6 +515,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;
@@ -767,6 +768,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;
@@ -891,6 +893,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;
@@ -954,6 +957,7 @@ static void ignore_blame_entry(struct blame_entry *e,struct blame_line_tracker *line_blames;int entry_len, nr_lines; + e->ignored =1 ; line_blames =xcalloc (sizeof (struct blame_line_tracker ), e->num_lines);guess_line_blames (e, parent, target, offset, delta, line_blames);
blame.h +1 -0
@@ -94,6 +94,7 @@ struct blame_entry {* scanning the lines over and over. */ unsigned score; +int ignored;int unblamable; };
builtin/blame.c +9 -0
@@ -53,6 +53,7 @@ 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 mark_ignored_lines;static struct date_mode blame_date_mode = {DATE_ISO8601 };static size_t blame_date_width;
@@ -482,6 +483,10 @@ static void emit_other(struct blame_scoreboard *sb, struct blame_entry *ent, int } } +if (mark_ignored_lines && ent->ignored) { + length--; +putchar ('*' ); + }if (ent->unblamable)memset (hex,'0' , length);printf ("%.*s" , length, hex);
@@ -710,6 +715,10 @@ 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.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"),
t/t8013-blame-ignore-revs.sh +33 -0
@@ -123,6 +123,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
Signature · 1 line
2.21.0.392.gf8f6787159e-goog
PATCH v5 3/6 blame: optionally track the line starts during fill_blame_origin()
In reply to Barret RhodenThe line_starts array is an index of line number to file offset, so that we can quickly find where a particular line begins in a file. Prior to this commit, we only tracked this information for the final file image, i.e. the current version of the file.
This commit adds the ability to track this information for any version of the file throughout the file's history. In particular, we track this info when we load the file's image into memory: fill_blame_origin().
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 line_starts array.
--- blame.c | 76 ++++++++++++++++++++++++++++++++++----------------------- blame.h | 2 ++ 2 files changed, 48 insertions(+), 30 deletions(-)
blame.c +46 -30
@@ -310,12 +310,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;
@@ -339,11 +369,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 ; }/*
@@ -992,8 +1027,10 @@ static void pass_blame_to_parent(struct blame_scoreboard *sb, d.offset =0 ; 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,0 ); +fill_origin_blob (&sb->revs->diffopt, target, &file_o, + &sb->num_read_blob,0 ); sb->num_get_patch++;if (diff_hunks (&file_p, &file_o, blame_chunk_cb, &d, sb->xdl_opts))
@@ -1199,7 +1236,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 ;
@@ -1328,7 +1366,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 ;
@@ -1650,37 +1689,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; }
blame.h +2 -0
@@ -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
Signature · 1 line
2.21.0.392.gf8f6787159e-goog
PATCH v5 6/6 RFC blame: use a fingerprint heuristic to match ignored lines
In reply to Barret RhodenThis 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 fingerprinting based on the sum of the bitwise-ORed bits in a string.
The fingerprint code and the idea to use them for blame came from Michael Platings <[email protected]>.
For each line in the target, guess_line_blames() finds the best line in the parent, above a magic threshold (1 byte pair, currently). Ties are broken by proximity of the parent line number to the target's line.
Here's an example of the difference between algorithms. 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_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.'
TODO:
- Is '1' a decent threshold? Add another user option?
- Can we decrease that FINGERPRINT_LENGTH? Or do something about the TODO about using a set data structure?
- How about matching *outside* the parent's diff hunk? Right now, this just looks in the parent's hunk for a match. But a better match may be elsewhere in the file. This might happen when the diff has too small of a -M. If we do this, then consider caching the fingerprints for a parent's entire file, since multiple target blame_entries may check the entire parent's space. Also, if we do this, we probably need to sort the parent's blame list (again), since the spliced entries point outside of the diff hunk's range in the parent's address space.
- If we never intend to match outside the parent's diff hunk, then we might be able to short-circuit guess_line_blames() when the parent's chunk length is 0. Doing this somewhat limits the algorithms, and would be a performance optimization, which I didn't want to do without numbers saying we needed it.
- Fix up this commit + message. I'd be up for splitting it more, particularly if Michael wants his contributions/fingerprinting in his own commit.
--- blame.c | 92 +++++++++++++++++++++++++++++++++++++++++++++++++++++---- 1 file changed, 87 insertions(+), 5 deletions(-)
blame.c +87 -5
@@ -915,27 +915,109 @@ static int are_lines_adjacent(struct blame_line_tracker *first, 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. +/* https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel */ +static int bitcount (uint32_t v) +{ + v = v - ((v >>1 ) &0x55555555u ); + v = (v &0x33333333u ) + ((v >>2 ) &0x33333333u ); +return (((v + (v >>4 )) &0xf0f0f0fu ) *0x1010101u ) >>24 ; +} + +#define FINGERPRINT_LENGTH (8 * 256) +#define FINGERPRINT_THRESHOLD 1 +/* This is just a bitset indicating which byte pairs are present. +* e.g. the string "good goo" has pairs "go", "oo", "od", "d ", " g" +* String similarity is calculated as a bitwise or and counting the set bits. +* +* TODO for the string lengths we typically deal with, this would probably be +* implemented more efficiently with a set data structure. */ +struct fingerprint { +uint32_t bits[FINGERPRINT_LENGTH ]; +}; + +static void get_fingerprint (struct fingerprint *result,const char *line_begin, +const char *line_end) +{ +for (const char *p = line_begin; p +1 < line_end; ++p) { +unsigned int c =tolower (*p) | (tolower (*(p +1 )) <<8 ); + + result->bits[c >>5 ] |=1u << (c &0x1f ); + } +} + +static int fingerprint_similarity (const struct fingerprint *a, +const struct fingerprint *b) +{ +int intersection =0 ; + +for (int i =0 ; i <FINGERPRINT_LENGTH ; ++i) + intersection +=bitcount (a->bits[i] & b->bits[i]); +return intersection; +} + +static void get_chunk_fingerprints (struct fingerprint *fingerprints, +const char *content, +const int *line_starts, +long chunk_start, +long chunk_length) +{ + line_starts += chunk_start; +for (int i =0 ; i != chunk_length; ++i) { +const char *linestart = content + line_starts[i]; +const char *lineend = content + line_starts[i +1 ]; + +get_fingerprint (fingerprints + i, linestart, lineend); + } +} +static void guess_line_blames (struct blame_entry *e,struct blame_origin *parent,struct blame_origin *target,int offset,int delta,struct blame_line_tracker *line_blames) { +struct fingerprint *fp_parent, *fp_target;int nr_parent_lines = e->num_lines - delta; + fp_parent =xcalloc (sizeof (struct fingerprint ), nr_parent_lines); + fp_target =xcalloc (sizeof (struct fingerprint ), e->num_lines); + +get_chunk_fingerprints (fp_parent, parent->file.ptr, + parent->line_starts, + e->s_lno + offset, nr_parent_lines); +get_chunk_fingerprints (fp_target, target->file.ptr, + target->line_starts, + e->s_lno, e->num_lines); +for (int i =0 ; i < e->num_lines; i++) { -if (i < nr_parent_lines) { +int best_sim_val =FINGERPRINT_THRESHOLD ; +int best_sim_idx =-1 ; +int sim; + +for (int j =0 ; j < nr_parent_lines; j++) { + sim =fingerprint_similarity (&fp_target[i], + &fp_parent[j]); +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 - i) <abs (j - i)) +continue ; + best_sim_val = sim; + best_sim_idx = j; + } +if (best_sim_idx >=0 ) { line_blames[i].is_parent =1 ; - line_blames[i].s_lno = e->s_lno + i + offset; + line_blames[i].s_lno = e->s_lno + offset + best_sim_idx; }else { line_blames[i].is_parent =0 ; line_blames[i].s_lno = e->s_lno + i; } } + +free (fp_parent); +free (fp_target); }/*
Signature · 1 line
2.21.0.392.gf8f6787159e-goog
PATCH v5 4/6 blame: add the ability to ignore commits and their changes
In reply to Barret RhodenCommits 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.
--- Documentation/blame-options.txt | 16 +++ Documentation/config/blame.txt | 7 ++ Documentation/git-blame.txt | 1 + blame.c | 182 +++++++++++++++++++++++++++++--- blame.h | 3 + builtin/blame.c | 42 ++++++++ t/t8013-blame-ignore-revs.sh | 168 +++++++++++++++++++++++++++++ 7 files changed, 407 insertions(+), 12 deletions(-) create mode 100755 t/t8013-blame-ignore-revs.sh
Documentation/blame-options.txt +16 -0
@@ -110,5 +110,21 @@ 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. 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. + +--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.
Documentation/config/blame.txt +7 -0
@@ -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`.
Documentation/git-blame.txt +1 -0
@@ -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>
blame.c +170 -12
270 lines not on this page · raw message
blame.h +3 -0
@@ -94,6 +94,7 @@ struct blame_entry {* scanning the lines over and over. */ unsigned score; +int unblamable; };/*
@@ -119,6 +120,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;
builtin/blame.c +42 -0
90 lines not on this page · raw message
t/t8013-blame-ignore-revs.sh new file +168 -0
168 lines not on this page · raw message
Signature · 1 line
2.21.0.392.gf8f6787159e-goog
Re: [PATCH v5 6/6] RFC blame: use a fingerprint heuristic to match ignored lines
In reply to Barret RhodenQuoted 26 lines · Barret Rhoden
blame.c +15
-3@@ -915,27 +915,109 @@ static int are_lines_adjacent(struct blame_line_tracker *first, 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. +/* https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel */ +static int bitcount (uint32_t v) +{ + v = v - ((v >>1 ) &0x55555555u ); + v = (v &0x33333333u ) + ((v >>2 ) &0x33333333u ); +return (((v + (v >>4 )) &0xf0f0f0fu ) *0x1010101u ) >>24 ; +} + +#define FINGERPRINT_LENGTH (8 * 256) +#define FINGERPRINT_THRESHOLD 1 +/* This is just a bitset indicating which byte pairs are present. +* e.g. the string "good goo" has pairs "go", "oo", "od", "d ", " g" +* String similarity is calculated as a bitwise or and counting the set bits. +* +* TODO for the string lengths we typically deal with, this would probably be
blame.c static int are_lines_adjacent(struct blame_line_tracker *first, · line 942
Quoted 10 lines
blame.c +9
-0+* implemented more efficiently with a set data structure. */ +struct fingerprint { +uint32_t bits[FINGERPRINT_LENGTH ]; +}; + +static void get_fingerprint (struct fingerprint *result,const char *line_begin, +const char *line_end) +{ +for (const char *p = line_begin; p +1 < line_end; ++p) {
We still stick to C89, which doesn't support for loop initial declarations yet. Please declare the loop variable as a regular local variable. This also applies to the several 'for (int i = 0; ...)' loops in the functions below.
Quoted 86 lines
blame.c +63
-2+unsigned int c =tolower (*p) | (tolower (*(p +1 )) <<8 ); + + result->bits[c >>5 ] |=1u << (c &0x1f ); + } +} + +static int fingerprint_similarity (const struct fingerprint *a, +const struct fingerprint *b) +{ +int intersection =0 ; + +for (int i =0 ; i <FINGERPRINT_LENGTH ; ++i) + intersection +=bitcount (a->bits[i] & b->bits[i]); +return intersection; +} + +static void get_chunk_fingerprints (struct fingerprint *fingerprints, +const char *content, +const int *line_starts, +long chunk_start, +long chunk_length) +{ + line_starts += chunk_start; +for (int i =0 ; i != chunk_length; ++i) { +const char *linestart = content + line_starts[i]; +const char *lineend = content + line_starts[i +1 ]; + +get_fingerprint (fingerprints + i, linestart, lineend); + } +} +static void guess_line_blames (struct blame_entry *e,struct blame_origin *parent,struct blame_origin *target,int offset,int delta,struct blame_line_tracker *line_blames) { +struct fingerprint *fp_parent, *fp_target;int nr_parent_lines = e->num_lines - delta; + fp_parent =xcalloc (sizeof (struct fingerprint ), nr_parent_lines); + fp_target =xcalloc (sizeof (struct fingerprint ), e->num_lines); + +get_chunk_fingerprints (fp_parent, parent->file.ptr, + parent->line_starts, + e->s_lno + offset, nr_parent_lines); +get_chunk_fingerprints (fp_target, target->file.ptr, + target->line_starts, + e->s_lno, e->num_lines); +for (int i =0 ; i < e->num_lines; i++) { -if (i < nr_parent_lines) { +int best_sim_val =FINGERPRINT_THRESHOLD ; +int best_sim_idx =-1 ; +int sim; + +for (int j =0 ; j < nr_parent_lines; j++) { + sim =fingerprint_similarity (&fp_target[i], + &fp_parent[j]); +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 - i) <abs (j - i)) +continue ; + best_sim_val = sim; + best_sim_idx = j; + } +if (best_sim_idx >=0 ) { line_blames[i].is_parent =1 ; - line_blames[i].s_lno = e->s_lno + i + offset; + line_blames[i].s_lno = e->s_lno + offset + best_sim_idx; }else { line_blames[i].is_parent =0 ; line_blames[i].s_lno = e->s_lno + i; } } + +free (fp_parent); +free (fp_target); }/* Signature · 1 line
2.21.0.392.gf8f6787159e-goog