diff options
Diffstat (limited to 'line-log.c')
| -rw-r--r-- | line-log.c | 1325 |
1 files changed, 1325 insertions, 0 deletions
diff --git a/line-log.c b/line-log.c new file mode 100644 index 0000000..a7f3e7f --- /dev/null +++ b/line-log.c @@ -0,0 +1,1325 @@ +#include "git-compat-util.h" +#include "line-range.h" +#include "cache.h" +#include "tag.h" +#include "blob.h" +#include "tree.h" +#include "diff.h" +#include "commit.h" +#include "decorate.h" +#include "revision.h" +#include "xdiff-interface.h" +#include "strbuf.h" +#include "log-tree.h" +#include "graph.h" +#include "userdiff.h" +#include "line-log.h" +#include "strvec.h" +#include "bloom.h" + +static void range_set_grow(struct range_set *rs, size_t extra) +{ + ALLOC_GROW(rs->ranges, rs->nr + extra, rs->alloc); +} + +/* Either initialization would be fine */ +#define RANGE_SET_INIT {0} + +void range_set_init(struct range_set *rs, size_t prealloc) +{ + rs->alloc = rs->nr = 0; + rs->ranges = NULL; + if (prealloc) + range_set_grow(rs, prealloc); +} + +void range_set_release(struct range_set *rs) +{ + FREE_AND_NULL(rs->ranges); + rs->alloc = rs->nr = 0; +} + +/* dst must be uninitialized! */ +static void range_set_copy(struct range_set *dst, struct range_set *src) +{ + range_set_init(dst, src->nr); + COPY_ARRAY(dst->ranges, src->ranges, src->nr); + dst->nr = src->nr; +} + +static void range_set_move(struct range_set *dst, struct range_set *src) +{ + range_set_release(dst); + dst->ranges = src->ranges; + dst->nr = src->nr; + dst->alloc = src->alloc; + src->ranges = NULL; + src->alloc = src->nr = 0; +} + +/* tack on a _new_ range _at the end_ */ +void range_set_append_unsafe(struct range_set *rs, long a, long b) +{ + assert(a <= b); + range_set_grow(rs, 1); + rs->ranges[rs->nr].start = a; + rs->ranges[rs->nr].end = b; + rs->nr++; +} + +void range_set_append(struct range_set *rs, long a, long b) +{ + assert(rs->nr == 0 || rs->ranges[rs->nr-1].end <= a); + range_set_append_unsafe(rs, a, b); +} + +static int range_cmp(const void *_r, const void *_s) +{ + const struct range *r = _r; + const struct range *s = _s; + + /* this could be simply 'return r.start-s.start', but for the types */ + if (r->start == s->start) + return 0; + if (r->start < s->start) + return -1; + return 1; +} + +/* + * Check that the ranges are non-empty, sorted and non-overlapping + */ +static void range_set_check_invariants(struct range_set *rs) +{ + unsigned int i; + + if (!rs) + return; + + if (rs->nr) + assert(rs->ranges[0].start < rs->ranges[0].end); + + for (i = 1; i < rs->nr; i++) { + assert(rs->ranges[i-1].end < rs->ranges[i].start); + assert(rs->ranges[i].start < rs->ranges[i].end); + } +} + +/* + * In-place pass of sorting and merging the ranges in the range set, + * to establish the invariants when we get the ranges from the user + */ +void sort_and_merge_range_set(struct range_set *rs) +{ + unsigned int i; + unsigned int o = 0; /* output cursor */ + + QSORT(rs->ranges, rs->nr, range_cmp); + + for (i = 0; i < rs->nr; i++) { + if (rs->ranges[i].start == rs->ranges[i].end) + continue; + if (o > 0 && rs->ranges[i].start <= rs->ranges[o-1].end) { + if (rs->ranges[o-1].end < rs->ranges[i].end) + rs->ranges[o-1].end = rs->ranges[i].end; + } else { + rs->ranges[o].start = rs->ranges[i].start; + rs->ranges[o].end = rs->ranges[i].end; + o++; + } + } + assert(o <= rs->nr); + rs->nr = o; + + range_set_check_invariants(rs); +} + +/* + * Union of range sets (i.e., sets of line numbers). Used to merge + * them when searches meet at a common ancestor. + * + * This is also where the ranges are consolidated into canonical form: + * overlapping and adjacent ranges are merged, and empty ranges are + * removed. + */ +static void range_set_union(struct range_set *out, + struct range_set *a, struct range_set *b) +{ + unsigned int i = 0, j = 0; + struct range *ra = a->ranges; + struct range *rb = b->ranges; + /* cannot make an alias of out->ranges: it may change during grow */ + + assert(out->nr == 0); + while (i < a->nr || j < b->nr) { + struct range *new_range; + if (i < a->nr && j < b->nr) { + if (ra[i].start < rb[j].start) + new_range = &ra[i++]; + else if (ra[i].start > rb[j].start) + new_range = &rb[j++]; + else if (ra[i].end < rb[j].end) + new_range = &ra[i++]; + else + new_range = &rb[j++]; + } else if (i < a->nr) /* b exhausted */ + new_range = &ra[i++]; + else /* a exhausted */ + new_range = &rb[j++]; + if (new_range->start == new_range->end) + ; /* empty range */ + else if (!out->nr || out->ranges[out->nr-1].end < new_range->start) { + range_set_grow(out, 1); + out->ranges[out->nr].start = new_range->start; + out->ranges[out->nr].end = new_range->end; + out->nr++; + } else if (out->ranges[out->nr-1].end < new_range->end) { + out->ranges[out->nr-1].end = new_range->end; + } + } +} + +/* + * Difference of range sets (out = a \ b). Pass the "interesting" + * ranges as 'a' and the target side of the diff as 'b': it removes + * the ranges for which the commit is responsible. + */ +static void range_set_difference(struct range_set *out, + struct range_set *a, struct range_set *b) +{ + unsigned int i, j = 0; + for (i = 0; i < a->nr; i++) { + long start = a->ranges[i].start; + long end = a->ranges[i].end; + while (start < end) { + while (j < b->nr && start >= b->ranges[j].end) + /* + * a: |------- + * b: ------| + */ + j++; + if (j >= b->nr || end < b->ranges[j].start) { + /* + * b exhausted, or + * a: ----| + * b: |---- + */ + range_set_append(out, start, end); + break; + } + if (start >= b->ranges[j].start) { + /* + * a: |--???? + * b: |------| + */ + start = b->ranges[j].end; + } else if (end > b->ranges[j].start) { + /* + * a: |-----| + * b: |--????? + */ + if (start < b->ranges[j].start) + range_set_append(out, start, b->ranges[j].start); + start = b->ranges[j].end; + } + } + } +} + +static void diff_ranges_init(struct diff_ranges *diff) +{ + range_set_init(&diff->parent, 0); + range_set_init(&diff->target, 0); +} + +static void diff_ranges_release(struct diff_ranges *diff) +{ + range_set_release(&diff->parent); + range_set_release(&diff->target); +} + +static void line_log_data_init(struct line_log_data *r) +{ + memset(r, 0, sizeof(struct line_log_data)); + range_set_init(&r->ranges, 0); +} + +static void line_log_data_clear(struct line_log_data *r) +{ + range_set_release(&r->ranges); + if (r->pair) + diff_free_filepair(r->pair); +} + +static void free_line_log_data(struct line_log_data *r) +{ + while (r) { + struct line_log_data *next = r->next; + line_log_data_clear(r); + free(r); + r = next; + } +} + +static struct line_log_data * +search_line_log_data(struct line_log_data *list, const char *path, + struct line_log_data **insertion_point) +{ + struct line_log_data *p = list; + if (insertion_point) + *insertion_point = NULL; + while (p) { + int cmp = strcmp(p->path, path); + if (!cmp) + return p; + if (insertion_point && cmp < 0) + *insertion_point = p; + p = p->next; + } + return NULL; +} + +/* + * Note: takes ownership of 'path', which happens to be what the only + * caller needs. + */ +static void line_log_data_insert(struct line_log_data **list, + char *path, + long begin, long end) +{ + struct line_log_data *ip; + struct line_log_data *p = search_line_log_data(*list, path, &ip); + + if (p) { + range_set_append_unsafe(&p->ranges, begin, end); + free(path); + return; + } + + CALLOC_ARRAY(p, 1); + p->path = path; + range_set_append(&p->ranges, begin, end); + if (ip) { + p->next = ip->next; + ip->next = p; + } else { + p->next = *list; + *list = p; + } +} + +struct collect_diff_cbdata { + struct diff_ranges *diff; +}; + +static int collect_diff_cb(long start_a, long count_a, + long start_b, long count_b, + void *data) +{ + struct collect_diff_cbdata *d = data; + + if (count_a >= 0) + range_set_append(&d->diff->parent, start_a, start_a + count_a); + if (count_b >= 0) + range_set_append(&d->diff->target, start_b, start_b + count_b); + + return 0; +} + +static int collect_diff(mmfile_t *parent, mmfile_t *target, struct diff_ranges *out) +{ + struct collect_diff_cbdata cbdata = {NULL}; + xpparam_t xpp; + xdemitconf_t xecfg; + xdemitcb_t ecb; + + memset(&xpp, 0, sizeof(xpp)); + memset(&xecfg, 0, sizeof(xecfg)); + xecfg.ctxlen = xecfg.interhunkctxlen = 0; + + cbdata.diff = out; + xecfg.hunk_func = collect_diff_cb; + memset(&ecb, 0, sizeof(ecb)); + ecb.priv = &cbdata; + return xdi_diff(parent, target, &xpp, &xecfg, &ecb); +} + +/* + * These are handy for debugging. Removing them with #if 0 silences + * the "unused function" warning. + */ +#if 0 +static void dump_range_set(struct range_set *rs, const char *desc) +{ + int i; + printf("range set %s (%d items):\n", desc, rs->nr); + for (i = 0; i < rs->nr; i++) + printf("\t[%ld,%ld]\n", rs->ranges[i].start, rs->ranges[i].end); +} + +static void dump_line_log_data(struct line_log_data *r) +{ + char buf[4096]; + while (r) { + snprintf(buf, 4096, "file %s\n", r->path); + dump_range_set(&r->ranges, buf); + r = r->next; + } +} + +static void dump_diff_ranges(struct diff_ranges *diff, const char *desc) +{ + int i; + assert(diff->parent.nr == diff->target.nr); + printf("diff ranges %s (%d items):\n", desc, diff->parent.nr); + printf("\tparent\ttarget\n"); + for (i = 0; i < diff->parent.nr; i++) { + printf("\t[%ld,%ld]\t[%ld,%ld]\n", + diff->parent.ranges[i].start, + diff->parent.ranges[i].end, + diff->target.ranges[i].start, + diff->target.ranges[i].end); + } +} +#endif + + +static int ranges_overlap(struct range *a, struct range *b) +{ + return !(a->end <= b->start || b->end <= a->start); +} + +/* + * Given a diff and the set of interesting ranges, determine all hunks + * of the diff which touch (overlap) at least one of the interesting + * ranges in the target. + */ +static void diff_ranges_filter_touched(struct diff_ranges *out, + struct diff_ranges *diff, + struct range_set *rs) +{ + unsigned int i, j = 0; + + assert(out->target.nr == 0); + + for (i = 0; i < diff->target.nr; i++) { + while (diff->target.ranges[i].start > rs->ranges[j].end) { + j++; + if (j == rs->nr) + return; + } + if (ranges_overlap(&diff->target.ranges[i], &rs->ranges[j])) { + range_set_append(&out->parent, + diff->parent.ranges[i].start, + diff->parent.ranges[i].end); + range_set_append(&out->target, + diff->target.ranges[i].start, + diff->target.ranges[i].end); + } + } +} + +/* + * Adjust the line counts in 'rs' to account for the lines + * added/removed in the diff. + */ +static void range_set_shift_diff(struct range_set *out, + struct range_set *rs, + struct diff_ranges *diff) +{ + unsigned int i, j = 0; + long offset = 0; + struct range *src = rs->ranges; + struct range *target = diff->target.ranges; + struct range *parent = diff->parent.ranges; + + for (i = 0; i < rs->nr; i++) { + while (j < diff->target.nr && src[i].start >= target[j].start) { + offset += (parent[j].end-parent[j].start) + - (target[j].end-target[j].start); + j++; + } + range_set_append(out, src[i].start+offset, src[i].end+offset); + } +} + +/* + * Given a diff and the set of interesting ranges, map the ranges + * across the diff. That is: observe that the target commit takes + * blame for all the + (target-side) ranges. So for every pair of + * ranges in the diff that was touched, we remove the latter and add + * its parent side. + */ +static void range_set_map_across_diff(struct range_set *out, + struct range_set *rs, + struct diff_ranges *diff, + struct diff_ranges **touched_out) +{ + struct diff_ranges *touched = xmalloc(sizeof(*touched)); + struct range_set tmp1 = RANGE_SET_INIT; + struct range_set tmp2 = RANGE_SET_INIT; + + diff_ranges_init(touched); + diff_ranges_filter_touched(touched, diff, rs); + range_set_difference(&tmp1, rs, &touched->target); + range_set_shift_diff(&tmp2, &tmp1, diff); + range_set_union(out, &tmp2, &touched->parent); + range_set_release(&tmp1); + range_set_release(&tmp2); + + *touched_out = touched; +} + +static struct commit *check_single_commit(struct rev_info *revs) +{ + struct object *commit = NULL; + int found = -1; + int i; + + for (i = 0; i < revs->pending.nr; i++) { + struct object *obj = revs->pending.objects[i].item; + if (obj->flags & UNINTERESTING) + continue; + obj = deref_tag(revs->repo, obj, NULL, 0); + if (!obj || obj->type != OBJ_COMMIT) + die("Non commit %s?", revs->pending.objects[i].name); + if (commit) + die("More than one commit to dig from: %s and %s?", + revs->pending.objects[i].name, + revs->pending.objects[found].name); + commit = obj; + found = i; + } + + if (!commit) + die("No commit specified?"); + + return (struct commit *) commit; +} + +static void fill_blob_sha1(struct repository *r, struct commit *commit, + struct diff_filespec *spec) +{ + unsigned short mode; + struct object_id oid; + + if (get_tree_entry(r, &commit->object.oid, spec->path, &oid, &mode)) + die("There is no path %s in the commit", spec->path); + fill_filespec(spec, &oid, 1, mode); + + return; +} + +static void fill_line_ends(struct repository *r, + struct diff_filespec *spec, + long *lines, + unsigned long **line_ends) +{ + int num = 0, size = 50; + long cur = 0; + unsigned long *ends = NULL; + char *data = NULL; + + if (diff_populate_filespec(r, spec, NULL)) + die("Cannot read blob %s", oid_to_hex(&spec->oid)); + + ALLOC_ARRAY(ends, size); + ends[cur++] = 0; + data = spec->data; + while (num < spec->size) { + if (data[num] == '\n' || num == spec->size - 1) { + ALLOC_GROW(ends, (cur + 1), size); + ends[cur++] = num; + } + num++; + } + + /* shrink the array to fit the elements */ + REALLOC_ARRAY(ends, cur); + *lines = cur-1; + *line_ends = ends; +} + +struct nth_line_cb { + struct diff_filespec *spec; + long lines; + unsigned long *line_ends; +}; + +static const char *nth_line(void *data, long line) +{ + struct nth_line_cb *d = data; + assert(d && line <= d->lines); + assert(d->spec && d->spec->data); + + if (line == 0) + return (char *)d->spec->data; + else + return (char *)d->spec->data + d->line_ends[line] + 1; +} + +static struct line_log_data * +parse_lines(struct repository *r, struct commit *commit, + const char *prefix, struct string_list *args) +{ + long lines = 0; + unsigned long *ends = NULL; + struct nth_line_cb cb_data; + struct string_list_item *item; + struct line_log_data *ranges = NULL; + struct line_log_data *p; + + for_each_string_list_item(item, args) { + const char *name_part, *range_part; + char *full_name; + struct diff_filespec *spec; + long begin = 0, end = 0; + long anchor; + + name_part = skip_range_arg(item->string, r->index); + if (!name_part || *name_part != ':' || !name_part[1]) + die("-L argument not 'start,end:file' or ':funcname:file': %s", + item->string); + range_part = xstrndup(item->string, name_part - item->string); + name_part++; + + full_name = prefix_path(prefix, prefix ? strlen(prefix) : 0, + name_part); + + spec = alloc_filespec(full_name); + fill_blob_sha1(r, commit, spec); + fill_line_ends(r, spec, &lines, &ends); + cb_data.spec = spec; + cb_data.lines = lines; + cb_data.line_ends = ends; + + p = search_line_log_data(ranges, full_name, NULL); + if (p && p->ranges.nr) + anchor = p->ranges.ranges[p->ranges.nr - 1].end + 1; + else + anchor = 1; + + if (parse_range_arg(range_part, nth_line, &cb_data, + lines, anchor, &begin, &end, + full_name, r->index)) + die("malformed -L argument '%s'", range_part); + if ((!lines && (begin || end)) || lines < begin) + die("file %s has only %lu lines", name_part, lines); + if (begin < 1) + begin = 1; + if (end < 1 || lines < end) + end = lines; + begin--; + line_log_data_insert(&ranges, full_name, begin, end); + + free_filespec(spec); + FREE_AND_NULL(ends); + } + + for (p = ranges; p; p = p->next) + sort_and_merge_range_set(&p->ranges); + + return ranges; +} + +static struct line_log_data *line_log_data_copy_one(struct line_log_data *r) +{ + struct line_log_data *ret = xmalloc(sizeof(*ret)); + + assert(r); + line_log_data_init(ret); + range_set_copy(&ret->ranges, &r->ranges); + + ret->path = xstrdup(r->path); + + return ret; +} + +static struct line_log_data * +line_log_data_copy(struct line_log_data *r) +{ + struct line_log_data *ret = NULL; + struct line_log_data *tmp = NULL, *prev = NULL; + + assert(r); + ret = tmp = prev = line_log_data_copy_one(r); + r = r->next; + while (r) { + tmp = line_log_data_copy_one(r); + prev->next = tmp; + prev = tmp; + r = r->next; + } + + return ret; +} + +/* merge two range sets across files */ +static struct line_log_data *line_log_data_merge(struct line_log_data *a, + struct line_log_data *b) +{ + struct line_log_data *head = NULL, **pp = &head; + + while (a || b) { + struct line_log_data *src; + struct line_log_data *src2 = NULL; + struct line_log_data *d; + int cmp; + if (!a) + cmp = 1; + else if (!b) + cmp = -1; + else + cmp = strcmp(a->path, b->path); + if (cmp < 0) { + src = a; + a = a->next; + } else if (cmp == 0) { + src = a; + a = a->next; + src2 = b; + b = b->next; + } else { + src = b; + b = b->next; + } + d = xmalloc(sizeof(struct line_log_data)); + line_log_data_init(d); + d->path = xstrdup(src->path); + *pp = d; + pp = &d->next; + if (src2) + range_set_union(&d->ranges, &src->ranges, &src2->ranges); + else + range_set_copy(&d->ranges, &src->ranges); + } + + return head; +} + +static void add_line_range(struct rev_info *revs, struct commit *commit, + struct line_log_data *range) +{ + struct line_log_data *old_line = NULL; + struct line_log_data *new_line = NULL; + + old_line = lookup_decoration(&revs->line_log_data, &commit->object); + if (old_line && range) { + new_line = line_log_data_merge(old_line, range); + free_line_log_data(old_line); + } else if (range) + new_line = line_log_data_copy(range); + + if (new_line) + add_decoration(&revs->line_log_data, &commit->object, new_line); +} + +static void clear_commit_line_range(struct rev_info *revs, struct commit *commit) +{ + struct line_log_data *r; + r = lookup_decoration(&revs->line_log_data, &commit->object); + if (!r) + return; + free_line_log_data(r); + add_decoration(&revs->line_log_data, &commit->object, NULL); +} + +static struct line_log_data *lookup_line_range(struct rev_info *revs, + struct commit *commit) +{ + struct line_log_data *ret = NULL; + struct line_log_data *d; + + ret = lookup_decoration(&revs->line_log_data, &commit->object); + + for (d = ret; d; d = d->next) + range_set_check_invariants(&d->ranges); + + return ret; +} + +static int same_paths_in_pathspec_and_range(struct pathspec *pathspec, + struct line_log_data *range) +{ + int i; + struct line_log_data *r; + + for (i = 0, r = range; i < pathspec->nr && r; i++, r = r->next) + if (strcmp(pathspec->items[i].match, r->path)) + return 0; + if (i < pathspec->nr || r) + /* different number of pathspec items and ranges */ + return 0; + + return 1; +} + +static void parse_pathspec_from_ranges(struct pathspec *pathspec, + struct line_log_data *range) +{ + struct line_log_data *r; + struct strvec array = STRVEC_INIT; + const char **paths; + + for (r = range; r; r = r->next) + strvec_push(&array, r->path); + paths = strvec_detach(&array); + + parse_pathspec(pathspec, 0, PATHSPEC_PREFER_FULL, "", paths); + /* strings are now owned by pathspec */ + free(paths); +} + +void line_log_init(struct rev_info *rev, const char *prefix, struct string_list *args) +{ + struct commit *commit = NULL; + struct line_log_data *range; + + commit = check_single_commit(rev); + range = parse_lines(rev->diffopt.repo, commit, prefix, args); + add_line_range(rev, commit, range); + + parse_pathspec_from_ranges(&rev->diffopt.pathspec, range); +} + +static void move_diff_queue(struct diff_queue_struct *dst, + struct diff_queue_struct *src) +{ + assert(src != dst); + memcpy(dst, src, sizeof(struct diff_queue_struct)); + DIFF_QUEUE_CLEAR(src); +} + +static void filter_diffs_for_paths(struct line_log_data *range, int keep_deletions) +{ + int i; + struct diff_queue_struct outq; + DIFF_QUEUE_CLEAR(&outq); + + for (i = 0; i < diff_queued_diff.nr; i++) { + struct diff_filepair *p = diff_queued_diff.queue[i]; + struct line_log_data *rg = NULL; + + if (!DIFF_FILE_VALID(p->two)) { + if (keep_deletions) + diff_q(&outq, p); + else + diff_free_filepair(p); + continue; + } + for (rg = range; rg; rg = rg->next) { + if (!strcmp(rg->path, p->two->path)) + break; + } + if (rg) + diff_q(&outq, p); + else + diff_free_filepair(p); + } + free(diff_queued_diff.queue); + diff_queued_diff = outq; +} + +static inline int diff_might_be_rename(void) +{ + int i; + for (i = 0; i < diff_queued_diff.nr; i++) + if (!DIFF_FILE_VALID(diff_queued_diff.queue[i]->one)) { + /* fprintf(stderr, "diff_might_be_rename found creation of: %s\n", */ + /* diff_queued_diff.queue[i]->two->path); */ + return 1; + } + return 0; +} + +static void queue_diffs(struct line_log_data *range, + struct diff_options *opt, + struct diff_queue_struct *queue, + struct commit *commit, struct commit *parent) +{ + struct object_id *tree_oid, *parent_tree_oid; + + assert(commit); + + tree_oid = get_commit_tree_oid(commit); + parent_tree_oid = parent ? get_commit_tree_oid(parent) : NULL; + + if (opt->detect_rename && + !same_paths_in_pathspec_and_range(&opt->pathspec, range)) { + clear_pathspec(&opt->pathspec); + parse_pathspec_from_ranges(&opt->pathspec, range); + } + DIFF_QUEUE_CLEAR(&diff_queued_diff); + diff_tree_oid(parent_tree_oid, tree_oid, "", opt); + if (opt->detect_rename && diff_might_be_rename()) { + /* must look at the full tree diff to detect renames */ + clear_pathspec(&opt->pathspec); + DIFF_QUEUE_CLEAR(&diff_queued_diff); + + diff_tree_oid(parent_tree_oid, tree_oid, "", opt); + + filter_diffs_for_paths(range, 1); + diffcore_std(opt); + filter_diffs_for_paths(range, 0); + } + move_diff_queue(queue, &diff_queued_diff); +} + +static char *get_nth_line(long line, unsigned long *ends, void *data) +{ + if (line == 0) + return (char *)data; + else + return (char *)data + ends[line] + 1; +} + +static void print_line(const char *prefix, char first, + long line, unsigned long *ends, void *data, + const char *color, const char *reset, FILE *file) +{ + char *begin = get_nth_line(line, ends, data); + char *end = get_nth_line(line+1, ends, data); + int had_nl = 0; + + if (end > begin && end[-1] == '\n') { + end--; + had_nl = 1; + } + + fputs(prefix, file); + fputs(color, file); + putc(first, file); + fwrite(begin, 1, end-begin, file); + fputs(reset, file); + putc('\n', file); + if (!had_nl) + fputs("\\ No newline at end of file\n", file); +} + +static char *output_prefix(struct diff_options *opt) +{ + char *prefix = ""; + + if (opt->output_prefix) { + struct strbuf *sb = opt->output_prefix(opt, opt->output_prefix_data); + prefix = sb->buf; + } + + return prefix; +} + +static void dump_diff_hacky_one(struct rev_info *rev, struct line_log_data *range) +{ + unsigned int i, j = 0; + long p_lines, t_lines; + unsigned long *p_ends = NULL, *t_ends = NULL; + struct diff_filepair *pair = range->pair; + struct diff_ranges *diff = &range->diff; + + struct diff_options *opt = &rev->diffopt; + char *prefix = output_prefix(opt); + const char *c_reset = diff_get_color(opt->use_color, DIFF_RESET); + const char *c_frag = diff_get_color(opt->use_color, DIFF_FRAGINFO); + const char *c_meta = diff_get_color(opt->use_color, DIFF_METAINFO); + const char *c_old = diff_get_color(opt->use_color, DIFF_FILE_OLD); + const char *c_new = diff_get_color(opt->use_color, DIFF_FILE_NEW); + const char *c_context = diff_get_color(opt->use_color, DIFF_CONTEXT); + + if (!pair || !diff) + return; + + if (pair->one->oid_valid) + fill_line_ends(rev->diffopt.repo, pair->one, &p_lines, &p_ends); + fill_line_ends(rev->diffopt.repo, pair->two, &t_lines, &t_ends); + + fprintf(opt->file, "%s%sdiff --git a/%s b/%s%s\n", prefix, c_meta, pair->one->path, pair->two->path, c_reset); + fprintf(opt->file, "%s%s--- %s%s%s\n", prefix, c_meta, + pair->one->oid_valid ? "a/" : "", + pair->one->oid_valid ? pair->one->path : "/dev/null", + c_reset); + fprintf(opt->file, "%s%s+++ b/%s%s\n", prefix, c_meta, pair->two->path, c_reset); + for (i = 0; i < range->ranges.nr; i++) { + long p_start, p_end; + long t_start = range->ranges.ranges[i].start; + long t_end = range->ranges.ranges[i].end; + long t_cur = t_start; + unsigned int j_last; + + while (j < diff->target.nr && diff->target.ranges[j].end < t_start) + j++; + if (j == diff->target.nr || diff->target.ranges[j].start > t_end) + continue; + + /* Scan ahead to determine the last diff that falls in this range */ + j_last = j; + while (j_last < diff->target.nr && diff->target.ranges[j_last].start < t_end) + j_last++; + if (j_last > j) + j_last--; + + /* + * Compute parent hunk headers: we know that the diff + * has the correct line numbers (but not all hunks). + * So it suffices to shift the start/end according to + * the line numbers of the first/last hunk(s) that + * fall in this range. + */ + if (t_start < diff->target.ranges[j].start) + p_start = diff->parent.ranges[j].start - (diff->target.ranges[j].start-t_start); + else + p_start = diff->parent.ranges[j].start; + if (t_end > diff->target.ranges[j_last].end) + p_end = diff->parent.ranges[j_last].end + (t_end-diff->target.ranges[j_last].end); + else + p_end = diff->parent.ranges[j_last].end; + + if (!p_start && !p_end) { + p_start = -1; + p_end = -1; + } + + /* Now output a diff hunk for this range */ + fprintf(opt->file, "%s%s@@ -%ld,%ld +%ld,%ld @@%s\n", + prefix, c_frag, + p_start+1, p_end-p_start, t_start+1, t_end-t_start, + c_reset); + while (j < diff->target.nr && diff->target.ranges[j].start < t_end) { + int k; + for (; t_cur < diff->target.ranges[j].start; t_cur++) + print_line(prefix, ' ', t_cur, t_ends, pair->two->data, + c_context, c_reset, opt->file); + for (k = diff->parent.ranges[j].start; k < diff->parent.ranges[j].end; k++) + print_line(prefix, '-', k, p_ends, pair->one->data, + c_old, c_reset, opt->file); + for (; t_cur < diff->target.ranges[j].end && t_cur < t_end; t_cur++) + print_line(prefix, '+', t_cur, t_ends, pair->two->data, + c_new, c_reset, opt->file); + j++; + } + for (; t_cur < t_end; t_cur++) + print_line(prefix, ' ', t_cur, t_ends, pair->two->data, + c_context, c_reset, opt->file); + } + + free(p_ends); + free(t_ends); +} + +/* + * NEEDSWORK: manually building a diff here is not the Right + * Thing(tm). log -L should be built into the diff pipeline. + */ +static void dump_diff_hacky(struct rev_info *rev, struct line_log_data *range) +{ + fprintf(rev->diffopt.file, "%s\n", output_prefix(&rev->diffopt)); + while (range) { + dump_diff_hacky_one(rev, range); + range = range->next; + } +} + +/* + * Unlike most other functions, this destructively operates on + * 'range'. + */ +static int process_diff_filepair(struct rev_info *rev, + struct diff_filepair *pair, + struct line_log_data *range, + struct diff_ranges **diff_out) +{ + struct line_log_data *rg = range; + struct range_set tmp; + struct diff_ranges diff; + mmfile_t file_parent, file_target; + + assert(pair->two->path); + while (rg) { + assert(rg->path); + if (!strcmp(rg->path, pair->two->path)) + break; + rg = rg->next; + } + + if (!rg) + return 0; + if (rg->ranges.nr == 0) + return 0; + + assert(pair->two->oid_valid); + diff_populate_filespec(rev->diffopt.repo, pair->two, NULL); + file_target.ptr = pair->two->data; + file_target.size = pair->two->size; + + if (pair->one->oid_valid) { + diff_populate_filespec(rev->diffopt.repo, pair->one, NULL); + file_parent.ptr = pair->one->data; + file_parent.size = pair->one->size; + } else { + file_parent.ptr = ""; + file_parent.size = 0; + } + + diff_ranges_init(&diff); + if (collect_diff(&file_parent, &file_target, &diff)) + die("unable to generate diff for %s", pair->one->path); + + /* NEEDSWORK should apply some heuristics to prevent mismatches */ + free(rg->path); + rg->path = xstrdup(pair->one->path); + + range_set_init(&tmp, 0); + range_set_map_across_diff(&tmp, &rg->ranges, &diff, diff_out); + range_set_release(&rg->ranges); + range_set_move(&rg->ranges, &tmp); + + diff_ranges_release(&diff); + + return ((*diff_out)->parent.nr > 0); +} + +static struct diff_filepair *diff_filepair_dup(struct diff_filepair *pair) +{ + struct diff_filepair *new_filepair = xmalloc(sizeof(struct diff_filepair)); + new_filepair->one = pair->one; + new_filepair->two = pair->two; + new_filepair->one->count++; + new_filepair->two->count++; + return new_filepair; +} + +static void free_diffqueues(int n, struct diff_queue_struct *dq) +{ + for (int i = 0; i < n; i++) + diff_free_queue(&dq[i]); + free(dq); +} + +static int process_all_files(struct line_log_data **range_out, + struct rev_info *rev, + struct diff_queue_struct *queue, + struct line_log_data *range) +{ + int i, changed = 0; + + *range_out = line_log_data_copy(range); + + for (i = 0; i < queue->nr; i++) { + struct diff_ranges *pairdiff = NULL; + struct diff_filepair *pair = queue->queue[i]; + if (process_diff_filepair(rev, pair, *range_out, &pairdiff)) { + /* + * Store away the diff for later output. We + * tuck it in the ranges we got as _input_, + * since that's the commit that caused the + * diff. + * + * NEEDSWORK not enough when we get around to + * doing something interesting with merges; + * currently each invocation on a merge parent + * trashes the previous one's diff. + * + * NEEDSWORK tramples over data structures not owned here + */ + struct line_log_data *rg = range; + changed++; + while (rg && strcmp(rg->path, pair->two->path)) + rg = rg->next; + assert(rg); + rg->pair = diff_filepair_dup(queue->queue[i]); + memcpy(&rg->diff, pairdiff, sizeof(struct diff_ranges)); + } + free(pairdiff); + } + + return changed; +} + +int line_log_print(struct rev_info *rev, struct commit *commit) +{ + + show_log(rev); + if (!(rev->diffopt.output_format & DIFF_FORMAT_NO_OUTPUT)) { + struct line_log_data *range = lookup_line_range(rev, commit); + dump_diff_hacky(rev, range); + } + return 1; +} + +static int bloom_filter_check(struct rev_info *rev, + struct commit *commit, + struct line_log_data *range) +{ + struct bloom_filter *filter; + struct bloom_key key; + int result = 0; + + if (!commit->parents) + return 1; + + if (!rev->bloom_filter_settings || + !(filter = get_bloom_filter(rev->repo, commit))) + return 1; + + if (!range) + return 0; + + while (!result && range) { + fill_bloom_key(range->path, strlen(range->path), &key, rev->bloom_filter_settings); + + if (bloom_filter_contains(filter, &key, rev->bloom_filter_settings)) + result = 1; + + clear_bloom_key(&key); + range = range->next; + } + + return result; +} + +static int process_ranges_ordinary_commit(struct rev_info *rev, struct commit *commit, + struct line_log_data *range) +{ + struct commit *parent = NULL; + struct diff_queue_struct queue; + struct line_log_data *parent_range; + int changed; + + if (commit->parents) + parent = commit->parents->item; + + queue_diffs(range, &rev->diffopt, &queue, commit, parent); + changed = process_all_files(&parent_range, rev, &queue, range); + + if (parent) + add_line_range(rev, parent, parent_range); + free_line_log_data(parent_range); + diff_free_queue(&queue); + return changed; +} + +static int process_ranges_merge_commit(struct rev_info *rev, struct commit *commit, + struct line_log_data *range) +{ + struct diff_queue_struct *diffqueues; + struct line_log_data **cand; + struct commit **parents; + struct commit_list *p; + int i; + int nparents = commit_list_count(commit->parents); + + if (nparents > 1 && rev->first_parent_only) + nparents = 1; + + ALLOC_ARRAY(diffqueues, nparents); + ALLOC_ARRAY(cand, nparents); + ALLOC_ARRAY(parents, nparents); + + p = commit->parents; + for (i = 0; i < nparents; i++) { + parents[i] = p->item; + p = p->next; + queue_diffs(range, &rev->diffopt, &diffqueues[i], commit, parents[i]); + } + + for (i = 0; i < nparents; i++) { + int changed; + cand[i] = NULL; + changed = process_all_files(&cand[i], rev, &diffqueues[i], range); + if (!changed) { + /* + * This parent can take all the blame, so we + * don't follow any other path in history + */ + add_line_range(rev, parents[i], cand[i]); + clear_commit_line_range(rev, commit); + commit_list_append(parents[i], &commit->parents); + free(parents); + free(cand); + free_diffqueues(nparents, diffqueues); + /* NEEDSWORK leaking like a sieve */ + return 0; + } + } + + /* + * No single parent took the blame. We add the candidates + * from the above loop to the parents. + */ + for (i = 0; i < nparents; i++) { + add_line_range(rev, parents[i], cand[i]); + } + + clear_commit_line_range(rev, commit); + free(parents); + free(cand); + free_diffqueues(nparents, diffqueues); + return 1; + + /* NEEDSWORK evil merge detection stuff */ + /* NEEDSWORK leaking like a sieve */ +} + +int line_log_process_ranges_arbitrary_commit(struct rev_info *rev, struct commit *commit) +{ + struct line_log_data *range = lookup_line_range(rev, commit); + int changed = 0; + + if (range) { + if (commit->parents && !bloom_filter_check(rev, commit, range)) { + struct line_log_data *prange = line_log_data_copy(range); + add_line_range(rev, commit->parents->item, prange); + clear_commit_line_range(rev, commit); + } else if (!commit->parents || !commit->parents->next) + changed = process_ranges_ordinary_commit(rev, commit, range); + else + changed = process_ranges_merge_commit(rev, commit, range); + } + + if (!changed) + commit->object.flags |= TREESAME; + + return changed; +} + +static enum rewrite_result line_log_rewrite_one(struct rev_info *rev, struct commit **pp) +{ + for (;;) { + struct commit *p = *pp; + if (p->parents && p->parents->next) + return rewrite_one_ok; + if (p->object.flags & UNINTERESTING) + return rewrite_one_ok; + if (!(p->object.flags & TREESAME)) + return rewrite_one_ok; + if (!p->parents) + return rewrite_one_noparents; + *pp = p->parents->item; + } +} + +int line_log_filter(struct rev_info *rev) +{ + struct commit *commit; + struct commit_list *list = rev->commits; + struct commit_list *out = NULL, **pp = &out; + + while (list) { + struct commit_list *to_free = NULL; + commit = list->item; + if (line_log_process_ranges_arbitrary_commit(rev, commit)) { + *pp = list; + pp = &list->next; + } else + to_free = list; + list = list->next; + free(to_free); + } + *pp = NULL; + + for (list = out; list; list = list->next) + rewrite_parents(rev, list->item, line_log_rewrite_one); + + rev->commits = out; + + return 0; +} |