diff options
Diffstat (limited to 'builtin-blame.c')
| -rw-r--r-- | builtin-blame.c | 1889 |
1 files changed, 1889 insertions, 0 deletions
diff --git a/builtin-blame.c b/builtin-blame.c new file mode 100644 index 0000000000..16660221c3 --- /dev/null +++ b/builtin-blame.c @@ -0,0 +1,1889 @@ +/* + * Pickaxe + * + * Copyright (c) 2006, Junio C Hamano + */ + +#include "cache.h" +#include "builtin.h" +#include "blob.h" +#include "commit.h" +#include "tag.h" +#include "tree-walk.h" +#include "diff.h" +#include "diffcore.h" +#include "revision.h" +#include "xdiff-interface.h" + +#include <time.h> +#include <sys/time.h> +#include <regex.h> + +static char blame_usage[] = +"git-blame [-c] [-l] [-t] [-f] [-n] [-p] [-L n,m] [-S <revs-file>] [-M] [-C] [-C] [commit] [--] file\n" +" -c, --compatibility Use the same output mode as git-annotate (Default: off)\n" +" -l, --long Show long commit SHA1 (Default: off)\n" +" -t, --time Show raw timestamp (Default: off)\n" +" -f, --show-name Show original filename (Default: auto)\n" +" -n, --show-number Show original linenumber (Default: off)\n" +" -p, --porcelain Show in a format designed for machine consumption\n" +" -L n,m Process only line range n,m, counting from 1\n" +" -M, -C Find line movements within and across files\n" +" -S revs-file Use revisions from revs-file instead of calling git-rev-list\n"; + +static int longest_file; +static int longest_author; +static int max_orig_digits; +static int max_digits; +static int max_score_digits; + +#ifndef DEBUG +#define DEBUG 0 +#endif + +/* stats */ +static int num_read_blob; +static int num_get_patch; +static int num_commits; + +#define PICKAXE_BLAME_MOVE 01 +#define PICKAXE_BLAME_COPY 02 +#define PICKAXE_BLAME_COPY_HARDER 04 + +/* + * blame for a blame_entry with score lower than these thresholds + * is not passed to the parent using move/copy logic. + */ +static unsigned blame_move_score; +static unsigned blame_copy_score; +#define BLAME_DEFAULT_MOVE_SCORE 20 +#define BLAME_DEFAULT_COPY_SCORE 40 + +/* bits #0..7 in revision.h, #8..11 used for merge_bases() in commit.c */ +#define METAINFO_SHOWN (1u<<12) +#define MORE_THAN_ONE_PATH (1u<<13) + +/* + * One blob in a commit that is being suspected + */ +struct origin { + int refcnt; + struct commit *commit; + mmfile_t file; + unsigned char blob_sha1[20]; + char path[FLEX_ARRAY]; +}; + +static char *fill_origin_blob(struct origin *o, mmfile_t *file) +{ + if (!o->file.ptr) { + char type[10]; + num_read_blob++; + file->ptr = read_sha1_file(o->blob_sha1, type, + (unsigned long *)(&(file->size))); + o->file = *file; + } + else + *file = o->file; + return file->ptr; +} + +static inline struct origin *origin_incref(struct origin *o) +{ + if (o) + o->refcnt++; + return o; +} + +static void origin_decref(struct origin *o) +{ + if (o && --o->refcnt <= 0) { + if (o->file.ptr) + free(o->file.ptr); + memset(o, 0, sizeof(*o)); + free(o); + } +} + +struct blame_entry { + struct blame_entry *prev; + struct blame_entry *next; + + /* the first line of this group in the final image; + * internally all line numbers are 0 based. + */ + int lno; + + /* how many lines this group has */ + int num_lines; + + /* the commit that introduced this group into the final image */ + struct origin *suspect; + + /* true if the suspect is truly guilty; false while we have not + * checked if the group came from one of its parents. + */ + char guilty; + + /* the line number of the first line of this group in the + * suspect's file; internally all line numbers are 0 based. + */ + int s_lno; + + /* how significant this entry is -- cached to avoid + * scanning the lines over and over + */ + unsigned score; +}; + +struct scoreboard { + /* the final commit (i.e. where we started digging from) */ + struct commit *final; + + const char *path; + + /* the contents in the final; pointed into by buf pointers of + * blame_entries + */ + const char *final_buf; + unsigned long final_buf_size; + + /* linked list of blames */ + struct blame_entry *ent; + + /* look-up a line in the final buffer */ + int num_lines; + int *lineno; +}; + +static int cmp_suspect(struct origin *a, struct origin *b) +{ + int cmp = hashcmp(a->commit->object.sha1, b->commit->object.sha1); + if (cmp) + return cmp; + return strcmp(a->path, b->path); +} + +#define cmp_suspect(a, b) ( ((a)==(b)) ? 0 : cmp_suspect(a,b) ) + +static void sanity_check_refcnt(struct scoreboard *); + +static void coalesce(struct scoreboard *sb) +{ + struct blame_entry *ent, *next; + + for (ent = sb->ent; ent && (next = ent->next); ent = next) { + if (!cmp_suspect(ent->suspect, next->suspect) && + ent->guilty == next->guilty && + ent->s_lno + ent->num_lines == next->s_lno) { + ent->num_lines += next->num_lines; + ent->next = next->next; + if (ent->next) + ent->next->prev = ent; + origin_decref(next->suspect); + free(next); + ent->score = 0; + next = ent; /* again */ + } + } + + if (DEBUG) /* sanity */ + sanity_check_refcnt(sb); +} + +static struct origin *make_origin(struct commit *commit, const char *path) +{ + struct origin *o; + o = xcalloc(1, sizeof(*o) + strlen(path) + 1); + o->commit = commit; + o->refcnt = 1; + strcpy(o->path, path); + return o; +} + +static struct origin *get_origin(struct scoreboard *sb, + struct commit *commit, + const char *path) +{ + struct blame_entry *e; + + for (e = sb->ent; e; e = e->next) { + if (e->suspect->commit == commit && + !strcmp(e->suspect->path, path)) + return origin_incref(e->suspect); + } + return make_origin(commit, path); +} + +static int fill_blob_sha1(struct origin *origin) +{ + unsigned mode; + char type[10]; + + if (!is_null_sha1(origin->blob_sha1)) + return 0; + if (get_tree_entry(origin->commit->object.sha1, + origin->path, + origin->blob_sha1, &mode)) + goto error_out; + if (sha1_object_info(origin->blob_sha1, type, NULL) || + strcmp(type, blob_type)) + goto error_out; + return 0; + error_out: + hashclr(origin->blob_sha1); + return -1; +} + +static struct origin *find_origin(struct scoreboard *sb, + struct commit *parent, + struct origin *origin) +{ + struct origin *porigin = NULL; + struct diff_options diff_opts; + const char *paths[2]; + + if (parent->util) { + /* This is a freestanding copy of origin and not + * refcounted. + */ + struct origin *cached = parent->util; + if (!strcmp(cached->path, origin->path)) { + porigin = get_origin(sb, parent, cached->path); + if (porigin->refcnt == 1) + hashcpy(porigin->blob_sha1, cached->blob_sha1); + return porigin; + } + /* otherwise it was not very useful; free it */ + free(parent->util); + parent->util = NULL; + } + + /* See if the origin->path is different between parent + * and origin first. Most of the time they are the + * same and diff-tree is fairly efficient about this. + */ + diff_setup(&diff_opts); + diff_opts.recursive = 1; + diff_opts.detect_rename = 0; + diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT; + paths[0] = origin->path; + paths[1] = NULL; + + diff_tree_setup_paths(paths, &diff_opts); + if (diff_setup_done(&diff_opts) < 0) + die("diff-setup"); + diff_tree_sha1(parent->tree->object.sha1, + origin->commit->tree->object.sha1, + "", &diff_opts); + diffcore_std(&diff_opts); + + /* It is either one entry that says "modified", or "created", + * or nothing. + */ + if (!diff_queued_diff.nr) { + /* The path is the same as parent */ + porigin = get_origin(sb, parent, origin->path); + hashcpy(porigin->blob_sha1, origin->blob_sha1); + } + else if (diff_queued_diff.nr != 1) + die("internal error in blame::find_origin"); + else { + struct diff_filepair *p = diff_queued_diff.queue[0]; + switch (p->status) { + default: + die("internal error in blame::find_origin (%c)", + p->status); + case 'M': + porigin = get_origin(sb, parent, origin->path); + hashcpy(porigin->blob_sha1, p->one->sha1); + break; + case 'A': + case 'T': + /* Did not exist in parent, or type changed */ + break; + } + } + diff_flush(&diff_opts); + if (porigin) { + struct origin *cached; + cached = make_origin(porigin->commit, porigin->path); + hashcpy(cached->blob_sha1, porigin->blob_sha1); + parent->util = cached; + } + return porigin; +} + +static struct origin *find_rename(struct scoreboard *sb, + struct commit *parent, + struct origin *origin) +{ + struct origin *porigin = NULL; + struct diff_options diff_opts; + int i; + const char *paths[2]; + + diff_setup(&diff_opts); + diff_opts.recursive = 1; + diff_opts.detect_rename = DIFF_DETECT_RENAME; + diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT; + diff_opts.single_follow = origin->path; + paths[0] = NULL; + diff_tree_setup_paths(paths, &diff_opts); + if (diff_setup_done(&diff_opts) < 0) + die("diff-setup"); + diff_tree_sha1(parent->tree->object.sha1, + origin->commit->tree->object.sha1, + "", &diff_opts); + diffcore_std(&diff_opts); + + for (i = 0; i < diff_queued_diff.nr; i++) { + struct diff_filepair *p = diff_queued_diff.queue[i]; + if ((p->status == 'R' || p->status == 'C') && + !strcmp(p->two->path, origin->path)) { + porigin = get_origin(sb, parent, p->one->path); + hashcpy(porigin->blob_sha1, p->one->sha1); + break; + } + } + diff_flush(&diff_opts); + return porigin; +} + +struct chunk { + /* line number in postimage; up to but not including this + * line is the same as preimage + */ + int same; + + /* preimage line number after this chunk */ + int p_next; + + /* postimage line number after this chunk */ + int t_next; +}; + +struct patch { + struct chunk *chunks; + int num; +}; + +struct blame_diff_state { + struct xdiff_emit_state xm; + struct patch *ret; + unsigned hunk_post_context; + unsigned hunk_in_pre_context : 1; +}; + +static void process_u_diff(void *state_, char *line, unsigned long len) +{ + struct blame_diff_state *state = state_; + struct chunk *chunk; + int off1, off2, len1, len2, num; + + num = state->ret->num; + if (len < 4 || line[0] != '@' || line[1] != '@') { + if (state->hunk_in_pre_context && line[0] == ' ') + state->ret->chunks[num - 1].same++; + else { + state->hunk_in_pre_context = 0; + if (line[0] == ' ') + state->hunk_post_context++; + else + state->hunk_post_context = 0; + } + return; + } + + if (num && state->hunk_post_context) { + chunk = &state->ret->chunks[num - 1]; + chunk->p_next -= state->hunk_post_context; + chunk->t_next -= state->hunk_post_context; + } + state->ret->num = ++num; + state->ret->chunks = xrealloc(state->ret->chunks, + sizeof(struct chunk) * num); + chunk = &state->ret->chunks[num - 1]; + if (parse_hunk_header(line, len, &off1, &len1, &off2, &len2)) { + state->ret->num--; + return; + } + + /* Line numbers in patch output are one based. */ + off1--; + off2--; + + chunk->same = len2 ? off2 : (off2 + 1); + + chunk->p_next = off1 + (len1 ? len1 : 1); + chunk->t_next = chunk->same + len2; + state->hunk_in_pre_context = 1; + state->hunk_post_context = 0; +} + +static struct patch *compare_buffer(mmfile_t *file_p, mmfile_t *file_o, + int context) +{ + struct blame_diff_state state; + xpparam_t xpp; + xdemitconf_t xecfg; + xdemitcb_t ecb; + + xpp.flags = XDF_NEED_MINIMAL; + xecfg.ctxlen = context; + xecfg.flags = 0; + ecb.outf = xdiff_outf; + ecb.priv = &state; + memset(&state, 0, sizeof(state)); + state.xm.consume = process_u_diff; + state.ret = xmalloc(sizeof(struct patch)); + state.ret->chunks = NULL; + state.ret->num = 0; + + xdl_diff(file_p, file_o, &xpp, &xecfg, &ecb); + + if (state.ret->num) { + struct chunk *chunk; + chunk = &state.ret->chunks[state.ret->num - 1]; + chunk->p_next -= state.hunk_post_context; + chunk->t_next -= state.hunk_post_context; + } + return state.ret; +} + +static struct patch *get_patch(struct origin *parent, struct origin *origin) +{ + mmfile_t file_p, file_o; + struct patch *patch; + + fill_origin_blob(parent, &file_p); + fill_origin_blob(origin, &file_o); + if (!file_p.ptr || !file_o.ptr) + return NULL; + patch = compare_buffer(&file_p, &file_o, 0); + num_get_patch++; + return patch; +} + +static void free_patch(struct patch *p) +{ + free(p->chunks); + free(p); +} + +static void add_blame_entry(struct scoreboard *sb, struct blame_entry *e) +{ + struct blame_entry *ent, *prev = NULL; + + origin_incref(e->suspect); + + for (ent = sb->ent; ent && ent->lno < e->lno; ent = ent->next) + prev = ent; + + /* prev, if not NULL, is the last one that is below e */ + e->prev = prev; + if (prev) { + e->next = prev->next; + prev->next = e; + } + else { + e->next = sb->ent; + sb->ent = e; + } + if (e->next) + e->next->prev = e; +} + +static void dup_entry(struct blame_entry *dst, struct blame_entry *src) +{ + struct blame_entry *p, *n; + + p = dst->prev; + n = dst->next; + origin_incref(src->suspect); + origin_decref(dst->suspect); + memcpy(dst, src, sizeof(*src)); + dst->prev = p; + dst->next = n; + dst->score = 0; +} + +static const char *nth_line(struct scoreboard *sb, int lno) +{ + return sb->final_buf + sb->lineno[lno]; +} + +static void split_overlap(struct blame_entry *split, + struct blame_entry *e, + int tlno, int plno, int same, + struct origin *parent) +{ + /* it is known that lines between tlno to same came from + * parent, and e has an overlap with that range. it also is + * known that parent's line plno corresponds to e's line tlno. + * + * <---- e -----> + * <------> + * <------------> + * <------------> + * <------------------> + * + * Potentially we need to split e into three parts; before + * this chunk, the chunk to be blamed for parent, and after + * that portion. + */ + int chunk_end_lno; + memset(split, 0, sizeof(struct blame_entry [3])); + + if (e->s_lno < tlno) { + /* there is a pre-chunk part not blamed on parent */ + split[0].suspect = origin_incref(e->suspect); + split[0].lno = e->lno; + split[0].s_lno = e->s_lno; + split[0].num_lines = tlno - e->s_lno; + split[1].lno = e->lno + tlno - e->s_lno; + split[1].s_lno = plno; + } + else { + split[1].lno = e->lno; + split[1].s_lno = plno + (e->s_lno - tlno); + } + + if (same < e->s_lno + e->num_lines) { + /* there is a post-chunk part not blamed on parent */ + split[2].suspect = origin_incref(e->suspect); + split[2].lno = e->lno + (same - e->s_lno); + split[2].s_lno = e->s_lno + (same - e->s_lno); + split[2].num_lines = e->s_lno + e->num_lines - same; + chunk_end_lno = split[2].lno; + } + else + chunk_end_lno = e->lno + e->num_lines; + split[1].num_lines = chunk_end_lno - split[1].lno; + + if (split[1].num_lines < 1) + return; + split[1].suspect = origin_incref(parent); +} + +static void split_blame(struct scoreboard *sb, + struct blame_entry *split, + struct blame_entry *e) +{ + struct blame_entry *new_entry; + + if (split[0].suspect && split[2].suspect) { + /* we need to split e into two and add another for parent */ + dup_entry(e, &split[0]); + + new_entry = xmalloc(sizeof(*new_entry)); + memcpy(new_entry, &(split[2]), sizeof(struct blame_entry)); + add_blame_entry(sb, new_entry); + + new_entry = xmalloc(sizeof(*new_entry)); + memcpy(new_entry, &(split[1]), sizeof(struct blame_entry)); + add_blame_entry(sb, new_entry); + } + else if (!split[0].suspect && !split[2].suspect) + /* parent covers the entire area */ + dup_entry(e, &split[1]); + else if (split[0].suspect) { + dup_entry(e, &split[0]); + + new_entry = xmalloc(sizeof(*new_entry)); + memcpy(new_entry, &(split[1]), sizeof(struct blame_entry)); + add_blame_entry(sb, new_entry); + } + else { + dup_entry(e, &split[1]); + + new_entry = xmalloc(sizeof(*new_entry)); + memcpy(new_entry, &(split[2]), sizeof(struct blame_entry)); + add_blame_entry(sb, new_entry); + } + + if (DEBUG) { /* sanity */ + struct blame_entry *ent; + int lno = sb->ent->lno, corrupt = 0; + + for (ent = sb->ent; ent; ent = ent->next) { + if (lno != ent->lno) + corrupt = 1; + if (ent->s_lno < 0) + corrupt = 1; + lno += ent->num_lines; + } + if (corrupt) { + lno = sb->ent->lno; + for (ent = sb->ent; ent; ent = ent->next) { + printf("L %8d l %8d n %8d\n", + lno, ent->lno, ent->num_lines); + lno = ent->lno + ent->num_lines; + } + die("oops"); + } + } +} + +static void decref_split(struct blame_entry *split) +{ + int i; + + for (i = 0; i < 3; i++) + origin_decref(split[i].suspect); +} + +static void blame_overlap(struct scoreboard *sb, struct blame_entry *e, + int tlno, int plno, int same, + struct origin *parent) +{ + struct blame_entry split[3]; + + split_overlap(split, e, tlno, plno, same, parent); + if (split[1].suspect) + split_blame(sb, split, e); + decref_split(split); +} + +static int find_last_in_target(struct scoreboard *sb, struct origin *target) +{ + struct blame_entry *e; + int last_in_target = -1; + + for (e = sb->ent; e; e = e->next) { + if (e->guilty || cmp_suspect(e->suspect, target)) + continue; + if (last_in_target < e->s_lno + e->num_lines) + last_in_target = e->s_lno + e->num_lines; + } + return last_in_target; +} + +static void blame_chunk(struct scoreboard *sb, + int tlno, int plno, int same, + struct origin *target, struct origin *parent) +{ + struct blame_entry *e; + + for (e = sb->ent; e; e = e->next) { + if (e->guilty || cmp_suspect(e->suspect, target)) + continue; + if (same <= e->s_lno) + continue; + if (tlno < e->s_lno + e->num_lines) + blame_overlap(sb, e, tlno, plno, same, parent); + } +} + +static int pass_blame_to_parent(struct scoreboard *sb, + struct origin *target, + struct origin *parent) +{ + int i, last_in_target, plno, tlno; + struct patch *patch; + + last_in_target = find_last_in_target(sb, target); + if (last_in_target < 0) + return 1; /* nothing remains for this target */ + + patch = get_patch(parent, target); + plno = tlno = 0; + for (i = 0; i < patch->num; i++) { + struct chunk *chunk = &patch->chunks[i]; + + blame_chunk(sb, tlno, plno, chunk->same, target, parent); + plno = chunk->p_next; + tlno = chunk->t_next; + } + /* rest (i.e. anything above tlno) are the same as parent */ + blame_chunk(sb, tlno, plno, last_in_target, target, parent); + + free_patch(patch); + return 0; +} + +static unsigned ent_score(struct scoreboard *sb, struct blame_entry *e) +{ + unsigned score; + const char *cp, *ep; + + if (e->score) + return e->score; + + score = 1; + cp = nth_line(sb, e->lno); + ep = nth_line(sb, e->lno + e->num_lines); + while (cp < ep) { + unsigned ch = *((unsigned char *)cp); + if (isalnum(ch)) + score++; + cp++; + } + e->score = score; + return score; +} + +static void copy_split_if_better(struct scoreboard *sb, + struct blame_entry *best_so_far, + struct blame_entry *this) +{ + int i; + + if (!this[1].suspect) + return; + if (best_so_far[1].suspect) { + if (ent_score(sb, &this[1]) < ent_score(sb, &best_so_far[1])) + return; + } + + for (i = 0; i < 3; i++) + origin_incref(this[i].suspect); + decref_split(best_so_far); + memcpy(best_so_far, this, sizeof(struct blame_entry [3])); +} + +static void find_copy_in_blob(struct scoreboard *sb, + struct blame_entry *ent, + struct origin *parent, + struct blame_entry *split, + mmfile_t *file_p) +{ + const char *cp; + int cnt; + mmfile_t file_o; + struct patch *patch; + int i, plno, tlno; + + cp = nth_line(sb, ent->lno); + file_o.ptr = (char*) cp; + cnt = ent->num_lines; + + while (cnt && cp < sb->final_buf + sb->final_buf_size) { + if (*cp++ == '\n') + cnt--; + } + file_o.size = cp - file_o.ptr; + + patch = compare_buffer(file_p, &file_o, 1); + + memset(split, 0, sizeof(struct blame_entry [3])); + plno = tlno = 0; + for (i = 0; i < patch->num; i++) { + struct chunk *chunk = &patch->chunks[i]; + + /* tlno to chunk->same are the same as ent */ + if (ent->num_lines <= tlno) + break; + if (tlno < chunk->same) { + struct blame_entry this[3]; + split_overlap(this, ent, + tlno + ent->s_lno, plno, + chunk->same + ent->s_lno, + parent); + copy_split_if_better(sb, split, this); + decref_split(this); + } + plno = chunk->p_next; + tlno = chunk->t_next; + } + free_patch(patch); +} + +static int find_move_in_parent(struct scoreboard *sb, + struct origin *target, + struct origin *parent) +{ + int last_in_target, made_progress; + struct blame_entry *e, split[3]; + mmfile_t file_p; + + last_in_target = find_last_in_target(sb, target); + if (last_in_target < 0) + return 1; /* nothing remains for this target */ + + fill_origin_blob(parent, &file_p); + if (!file_p.ptr) + return 0; + + made_progress = 1; + while (made_progress) { + made_progress = 0; + for (e = sb->ent; e; e = e->next) { + if (e->guilty || cmp_suspect(e->suspect, target)) + continue; + find_copy_in_blob(sb, e, parent, split, &file_p); + if (split[1].suspect && + blame_move_score < ent_score(sb, &split[1])) { + split_blame(sb, split, e); + made_progress = 1; + } + decref_split(split); + } + } + return 0; +} + + +struct blame_list { + struct blame_entry *ent; + struct blame_entry split[3]; +}; + +static struct blame_list *setup_blame_list(struct scoreboard *sb, + struct origin *target, + int *num_ents_p) +{ + struct blame_entry *e; + int num_ents, i; + struct blame_list *blame_list = NULL; + + /* Count the number of entries the target is suspected for, + * and prepare a list of entry and the best split. + */ + for (e = sb->ent, num_ents = 0; e; e = e->next) + if (!e->guilty && !cmp_suspect(e->suspect, target)) + num_ents++; + if (num_ents) { + blame_list = xcalloc(num_ents, sizeof(struct blame_list)); + for (e = sb->ent, i = 0; e; e = e->next) + if (!e->guilty && !cmp_suspect(e->suspect, target)) + blame_list[i++].ent = e; + } + *num_ents_p = num_ents; + return blame_list; +} + +static int find_copy_in_parent(struct scoreboard *sb, + struct origin *target, + struct commit *parent, + struct origin *porigin, + int opt) +{ + struct diff_options diff_opts; + const char *paths[1]; + int i, j; + int retval; + struct blame_list *blame_list; + int num_ents; + + blame_list = setup_blame_list(sb, target, &num_ents); + if (!blame_list) + return 1; /* nothing remains for this target */ + + diff_setup(&diff_opts); + diff_opts.recursive = 1; + diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT; + + paths[0] = NULL; + diff_tree_setup_paths(paths, &diff_opts); + if (diff_setup_done(&diff_opts) < 0) + die("diff-setup"); + + /* Try "find copies harder" on new path if requested; + * we do not want to use diffcore_rename() actually to + * match things up; find_copies_harder is set only to + * force diff_tree_sha1() to feed all filepairs to diff_queue, + * and this code needs to be after diff_setup_done(), which + * usually makes find-copies-harder imply copy detection. + */ + if ((opt & PICKAXE_BLAME_COPY_HARDER) && + (!porigin || strcmp(target->path, porigin->path))) + diff_opts.find_copies_harder = 1; + + diff_tree_sha1(parent->tree->object.sha1, + target->commit->tree->object.sha1, + "", &diff_opts); + + if (!diff_opts.find_copies_harder) + diffcore_std(&diff_opts); + + retval = 0; + while (1) { + int made_progress = 0; + + for (i = 0; i < diff_queued_diff.nr; i++) { + struct diff_filepair *p = diff_queued_diff.queue[i]; + struct origin *norigin; + mmfile_t file_p; + struct blame_entry this[3]; + + if (!DIFF_FILE_VALID(p->one)) + continue; /* does not exist in parent */ + if (porigin && !strcmp(p->one->path, porigin->path)) + /* find_move already dealt with this path */ + continue; + + norigin = get_origin(sb, parent, p->one->path); + hashcpy(norigin->blob_sha1, p->one->sha1); + fill_origin_blob(norigin, &file_p); + if (!file_p.ptr) + continue; + + for (j = 0; j < num_ents; j++) { + find_copy_in_blob(sb, blame_list[j].ent, + norigin, this, &file_p); + copy_split_if_better(sb, blame_list[j].split, + this); + decref_split(this); + } + origin_decref(norigin); + } + + for (j = 0; j < num_ents; j++) { + struct blame_entry *split = blame_list[j].split; + if (split[1].suspect && + blame_copy_score < ent_score(sb, &split[1])) { + split_blame(sb, split, blame_list[j].ent); + made_progress = 1; + } + decref_split(split); + } + free(blame_list); + + if (!made_progress) + break; + blame_list = setup_blame_list(sb, target, &num_ents); + if (!blame_list) { + retval = 1; + break; + } + } + diff_flush(&diff_opts); + + return retval; +} + +/* The blobs of origin and porigin exactly match, so everything + * origin is suspected for can be blamed on the parent. + */ +static void pass_whole_blame(struct scoreboard *sb, + struct origin *origin, struct origin *porigin) +{ + struct blame_entry *e; + + if (!porigin->file.ptr && origin->file.ptr) { + /* Steal its file */ + porigin->file = origin->file; + origin->file.ptr = NULL; + } + for (e = sb->ent; e; e = e->next) { + if (cmp_suspect(e->suspect, origin)) + continue; + origin_incref(porigin); + origin_decref(e->suspect); + e->suspect = porigin; + } +} + +#define MAXPARENT 16 + +static void pass_blame(struct scoreboard *sb, struct origin *origin, int opt) +{ + int i, pass; + struct commit *commit = origin->commit; + struct commit_list *parent; + struct origin *parent_origin[MAXPARENT], *porigin; + + memset(parent_origin, 0, sizeof(parent_origin)); + + /* The first pass looks for unrenamed path to optimize for + * common cases, then we look for renames in the second pass. + */ + for (pass = 0; pass < 2; pass++) { + struct origin *(*find)(struct scoreboard *, + struct commit *, struct origin *); + find = pass ? find_rename : find_origin; + + for (i = 0, parent = commit->parents; + i < MAXPARENT && parent; + parent = parent->next, i++) { + struct commit *p = parent->item; + int j, same; + + if (parent_origin[i]) + continue; + if (parse_commit(p)) + continue; + porigin = find(sb, p, origin); + if (!porigin) + continue; + if (!hashcmp(porigin->blob_sha1, origin->blob_sha1)) { + pass_whole_blame(sb, origin, porigin); + origin_decref(porigin); + goto finish; + } + for (j = same = 0; j < i; j++) + if (parent_origin[j] && + !hashcmp(parent_origin[j]->blob_sha1, + porigin->blob_sha1)) { + same = 1; + break; + } + if (!same) + parent_origin[i] = porigin; + else + origin_decref(porigin); + } + } + + num_commits++; + for (i = 0, parent = commit->parents; + i < MAXPARENT && parent; + parent = parent->next, i++) { + struct origin *porigin = parent_origin[i]; + if (!porigin) + continue; + if (pass_blame_to_parent(sb, origin, porigin)) + goto finish; + } + + /* + * Optionally run "miff" to find moves in parents' files here. + */ + if (opt & PICKAXE_BLAME_MOVE) + for (i = 0, parent = commit->parents; + i < MAXPARENT && parent; + parent = parent->next, i++) { + struct origin *porigin = parent_origin[i]; + if (!porigin) + continue; + if (find_move_in_parent(sb, origin, porigin)) + goto finish; + } + + /* + * Optionally run "ciff" to find copies from parents' files here. + */ + if (opt & PICKAXE_BLAME_COPY) + for (i = 0, parent = commit->parents; + i < MAXPARENT && parent; + parent = parent->next, i++) { + struct origin *porigin = parent_origin[i]; + if (find_copy_in_parent(sb, origin, parent->item, + porigin, opt)) + goto finish; + } + + finish: + for (i = 0; i < MAXPARENT; i++) + origin_decref(parent_origin[i]); +} + +static void assign_blame(struct scoreboard *sb, struct rev_info *revs, int opt) +{ + while (1) { + struct blame_entry *ent; + struct commit *commit; + struct origin *suspect = NULL; + + /* find one suspect to break down */ + for (ent = sb->ent; !suspect && ent; ent = ent->next) + if (!ent->guilty) + suspect = ent->suspect; + if (!suspect) + return; /* all done */ + + origin_incref(suspect); + commit = suspect->commit; + if (!commit->object.parsed) + parse_commit(commit); + if (!(commit->object.flags & UNINTERESTING) && + !(revs->max_age != -1 && commit->date < revs->max_age)) + pass_blame(sb, suspect, opt); + + /* Take responsibility for the remaining entries */ + for (ent = sb->ent; ent; ent = ent->next) + if (!cmp_suspect(ent->suspect, suspect)) + ent->guilty = 1; + origin_decref(suspect); + + if (DEBUG) /* sanity */ + sanity_check_refcnt(sb); + } +} + +static const char *format_time(unsigned long time, const char *tz_str, + int show_raw_time) +{ + static char time_buf[128]; + time_t t = time; + int minutes, tz; + struct tm *tm; + + if (show_raw_time) { + sprintf(time_buf, "%lu %s", time, tz_str); + return time_buf; + } + + tz = atoi(tz_str); + minutes = tz < 0 ? -tz : tz; + minutes = (minutes / 100)*60 + (minutes % 100); + minutes = tz < 0 ? -minutes : minutes; + t = time + minutes * 60; + tm = gmtime(&t); + + strftime(time_buf, sizeof(time_buf), "%Y-%m-%d %H:%M:%S ", tm); + strcat(time_buf, tz_str); + return time_buf; +} + +struct commit_info +{ + char *author; + char *author_mail; + unsigned long author_time; + char *author_tz; + + /* filled only when asked for details */ + char *committer; + char *committer_mail; + unsigned long committer_time; + char *committer_tz; + + char *summary; +}; + +static void get_ac_line(const char *inbuf, const char *what, + int bufsz, char *person, char **mail, + unsigned long *time, char **tz) +{ + int len; + char *tmp, *endp; + + tmp = strstr(inbuf, what); + if (!tmp) + goto error_out; + tmp += strlen(what); + endp = strchr(tmp, '\n'); + if (!endp) + len = strlen(tmp); + else + len = endp - tmp; + if (bufsz <= len) { + error_out: + /* Ugh */ + person = *mail = *tz = "(unknown)"; + *time = 0; + return; + } + memcpy(person, tmp, len); + + tmp = person; + tmp += len; + *tmp = 0; + while (*tmp != ' ') + tmp--; + *tz = tmp+1; + + *tmp = 0; + while (*tmp != ' ') + tmp--; + *time = strtoul(tmp, NULL, 10); + + *tmp = 0; + while (*tmp != ' ') + tmp--; + *mail = tmp + 1; + *tmp = 0; +} + +static void get_commit_info(struct commit *commit, + struct commit_info *ret, + int detailed) +{ + int len; + char *tmp, *endp; + static char author_buf[1024]; + static char committer_buf[1024]; + static char summary_buf[1024]; + + /* We've operated without save_commit_buffer, so + * we now need to populate them for output. + */ + if (!commit->buffer) { + char type[20]; + unsigned long size; + commit->buffer = + read_sha1_file(commit->object.sha1, type, &size); + } + ret->author = author_buf; + get_ac_line(commit->buffer, "\nauthor ", + sizeof(author_buf), author_buf, &ret->author_mail, + &ret->author_time, &ret->author_tz); + + if (!detailed) + return; + + ret->committer = committer_buf; + get_ac_line(commit->buffer, "\ncommitter ", + sizeof(committer_buf), committer_buf, &ret->committer_mail, + &ret->committer_time, &ret->committer_tz); + + ret->summary = summary_buf; + tmp = strstr(commit->buffer, "\n\n"); + if (!tmp) { + error_out: + sprintf(summary_buf, "(%s)", sha1_to_hex(commit->object.sha1)); + return; + } + tmp += 2; + endp = strchr(tmp, '\n'); + if (!endp) + goto error_out; + len = endp - tmp; + if (len >= sizeof(summary_buf)) + goto error_out; + memcpy(summary_buf, tmp, len); + summary_buf[len] = 0; +} + +#define OUTPUT_ANNOTATE_COMPAT 001 +#define OUTPUT_LONG_OBJECT_NAME 002 |