log -L: test merge of parallel modify/rename
[git/git.git] / line-log.c
CommitLineData
12da1d1f
TR
1#include "git-compat-util.h"
2#include "line-range.h"
3#include "cache.h"
4#include "tag.h"
5#include "blob.h"
6#include "tree.h"
7#include "diff.h"
8#include "commit.h"
9#include "decorate.h"
10#include "revision.h"
11#include "xdiff-interface.h"
12#include "strbuf.h"
13#include "log-tree.h"
14#include "graph.h"
13b8f68c 15#include "userdiff.h"
12da1d1f
TR
16#include "line-log.h"
17
18static void range_set_grow(struct range_set *rs, size_t extra)
19{
20 ALLOC_GROW(rs->ranges, rs->nr + extra, rs->alloc);
21}
22
23/* Either initialization would be fine */
24#define RANGE_SET_INIT {0}
25
26static void range_set_init(struct range_set *rs, size_t prealloc)
27{
28 rs->alloc = rs->nr = 0;
29 rs->ranges = NULL;
30 if (prealloc)
31 range_set_grow(rs, prealloc);
32}
33
34static void range_set_release(struct range_set *rs)
35{
36 free(rs->ranges);
37 rs->alloc = rs->nr = 0;
38 rs->ranges = NULL;
39}
40
41/* dst must be uninitialized! */
42static void range_set_copy(struct range_set *dst, struct range_set *src)
43{
44 range_set_init(dst, src->nr);
45 memcpy(dst->ranges, src->ranges, src->nr*sizeof(struct range_set));
46 dst->nr = src->nr;
47}
48static void range_set_move(struct range_set *dst, struct range_set *src)
49{
50 range_set_release(dst);
51 dst->ranges = src->ranges;
52 dst->nr = src->nr;
53 dst->alloc = src->alloc;
54 src->ranges = NULL;
55 src->alloc = src->nr = 0;
56}
57
58/* tack on a _new_ range _at the end_ */
20961886 59static void range_set_append_unsafe(struct range_set *rs, long a, long b)
12da1d1f
TR
60{
61 assert(a <= b);
12da1d1f
TR
62 range_set_grow(rs, 1);
63 rs->ranges[rs->nr].start = a;
64 rs->ranges[rs->nr].end = b;
65 rs->nr++;
66}
67
20961886
TR
68static void range_set_append(struct range_set *rs, long a, long b)
69{
70 assert(rs->nr == 0 || rs->ranges[rs->nr-1].end <= a);
71 range_set_append_unsafe(rs, a, b);
72}
73
12da1d1f
TR
74static int range_cmp(const void *_r, const void *_s)
75{
76 const struct range *r = _r;
77 const struct range *s = _s;
78
79 /* this could be simply 'return r.start-s.start', but for the types */
80 if (r->start == s->start)
81 return 0;
82 if (r->start < s->start)
83 return -1;
84 return 1;
85}
86
4596f190
TR
87/*
88 * Check that the ranges are non-empty, sorted and non-overlapping
89 */
90static void range_set_check_invariants(struct range_set *rs)
91{
92 int i;
93
94 if (!rs)
95 return;
96
97 if (rs->nr)
98 assert(rs->ranges[0].start < rs->ranges[0].end);
99
100 for (i = 1; i < rs->nr; i++) {
101 assert(rs->ranges[i-1].end < rs->ranges[i].start);
102 assert(rs->ranges[i].start < rs->ranges[i].end);
103 }
104}
105
12da1d1f 106/*
20961886
TR
107 * In-place pass of sorting and merging the ranges in the range set,
108 * to establish the invariants when we get the ranges from the user
12da1d1f
TR
109 */
110static void sort_and_merge_range_set(struct range_set *rs)
111{
112 int i;
113 int o = 1; /* output cursor */
114
115 qsort(rs->ranges, rs->nr, sizeof(struct range), range_cmp);
116
117 for (i = 1; i < rs->nr; i++) {
118 if (rs->ranges[i].start <= rs->ranges[o-1].end) {
119 rs->ranges[o-1].end = rs->ranges[i].end;
120 } else {
121 rs->ranges[o].start = rs->ranges[i].start;
122 rs->ranges[o].end = rs->ranges[i].end;
123 o++;
124 }
125 }
126 assert(o <= rs->nr);
127 rs->nr = o;
4596f190
TR
128
129 range_set_check_invariants(rs);
12da1d1f
TR
130}
131
132/*
133 * Union of range sets (i.e., sets of line numbers). Used to merge
134 * them when searches meet at a common ancestor.
135 *
136 * This is also where the ranges are consolidated into canonical form:
137 * overlapping and adjacent ranges are merged, and empty ranges are
138 * removed.
139 */
140static void range_set_union(struct range_set *out,
141 struct range_set *a, struct range_set *b)
142{
143 int i = 0, j = 0, o = 0;
144 struct range *ra = a->ranges;
145 struct range *rb = b->ranges;
146 /* cannot make an alias of out->ranges: it may change during grow */
147
148 assert(out->nr == 0);
149 while (i < a->nr || j < b->nr) {
150 struct range *new;
151 if (i < a->nr && j < b->nr) {
152 if (ra[i].start < rb[j].start)
153 new = &ra[i++];
154 else if (ra[i].start > rb[j].start)
155 new = &rb[j++];
156 else if (ra[i].end < rb[j].end)
157 new = &ra[i++];
158 else
159 new = &rb[j++];
160 } else if (i < a->nr) /* b exhausted */
161 new = &ra[i++];
162 else /* a exhausted */
163 new = &rb[j++];
164 if (new->start == new->end)
165 ; /* empty range */
166 else if (!o || out->ranges[o-1].end < new->start) {
167 range_set_grow(out, 1);
168 out->ranges[o].start = new->start;
169 out->ranges[o].end = new->end;
170 o++;
171 } else if (out->ranges[o-1].end < new->end) {
172 out->ranges[o-1].end = new->end;
173 }
174 }
175 out->nr = o;
176}
177
178/*
179 * Difference of range sets (out = a \ b). Pass the "interesting"
180 * ranges as 'a' and the target side of the diff as 'b': it removes
181 * the ranges for which the commit is responsible.
182 */
183static void range_set_difference(struct range_set *out,
184 struct range_set *a, struct range_set *b)
185{
186 int i, j = 0;
187 for (i = 0; i < a->nr; i++) {
188 long start = a->ranges[i].start;
189 long end = a->ranges[i].end;
190 while (start < end) {
191 while (j < b->nr && start >= b->ranges[j].end)
192 /*
193 * a: |-------
194 * b: ------|
195 */
196 j++;
197 if (j >= b->nr || end < b->ranges[j].start) {
198 /*
199 * b exhausted, or
200 * a: ----|
201 * b: |----
202 */
203 range_set_append(out, start, end);
204 break;
205 }
206 if (start >= b->ranges[j].start) {
207 /*
208 * a: |--????
209 * b: |------|
210 */
211 start = b->ranges[j].end;
212 } else if (end > b->ranges[j].start) {
213 /*
214 * a: |-----|
215 * b: |--?????
216 */
217 if (start < b->ranges[j].start)
218 range_set_append(out, start, b->ranges[j].start);
219 start = b->ranges[j].end;
220 }
221 }
222 }
223}
224
225static void diff_ranges_init(struct diff_ranges *diff)
226{
227 range_set_init(&diff->parent, 0);
228 range_set_init(&diff->target, 0);
229}
230
231static void diff_ranges_release(struct diff_ranges *diff)
232{
233 range_set_release(&diff->parent);
234 range_set_release(&diff->target);
235}
236
237void line_log_data_init(struct line_log_data *r)
238{
239 memset(r, 0, sizeof(struct line_log_data));
240 range_set_init(&r->ranges, 0);
241}
242
243static void line_log_data_clear(struct line_log_data *r)
244{
245 range_set_release(&r->ranges);
246 if (r->pair)
247 diff_free_filepair(r->pair);
248}
249
250static void free_line_log_data(struct line_log_data *r)
251{
252 while (r) {
253 struct line_log_data *next = r->next;
254 line_log_data_clear(r);
255 free(r);
256 r = next;
257 }
258}
259
260static struct line_log_data *
261search_line_log_data(struct line_log_data *list, const char *path,
262 struct line_log_data **insertion_point)
263{
264 struct line_log_data *p = list;
265 if (insertion_point)
266 *insertion_point = NULL;
267 while (p) {
268 int cmp = strcmp(p->spec->path, path);
269 if (!cmp)
270 return p;
271 if (insertion_point && cmp < 0)
272 *insertion_point = p;
273 p = p->next;
274 }
275 return NULL;
276}
277
278static void line_log_data_insert(struct line_log_data **list,
279 struct diff_filespec *spec,
280 long begin, long end)
281{
282 struct line_log_data *ip;
283 struct line_log_data *p = search_line_log_data(*list, spec->path, &ip);
284
285 if (p) {
20961886 286 range_set_append_unsafe(&p->ranges, begin, end);
12da1d1f
TR
287 sort_and_merge_range_set(&p->ranges);
288 free_filespec(spec);
289 return;
290 }
291
292 p = xcalloc(1, sizeof(struct line_log_data));
293 p->spec = spec;
294 range_set_append(&p->ranges, begin, end);
295 if (ip) {
296 p->next = ip->next;
297 ip->next = p;
298 } else {
299 p->next = *list;
300 *list = p;
301 }
302}
303
304struct collect_diff_cbdata {
305 struct diff_ranges *diff;
306};
307
308static int collect_diff_cb(long start_a, long count_a,
309 long start_b, long count_b,
310 void *data)
311{
312 struct collect_diff_cbdata *d = data;
313
314 if (count_a >= 0)
315 range_set_append(&d->diff->parent, start_a, start_a + count_a);
316 if (count_b >= 0)
317 range_set_append(&d->diff->target, start_b, start_b + count_b);
318
319 return 0;
320}
321
322static void collect_diff(mmfile_t *parent, mmfile_t *target, struct diff_ranges *out)
323{
324 struct collect_diff_cbdata cbdata = {NULL};
325 xpparam_t xpp;
326 xdemitconf_t xecfg;
327 xdemitcb_t ecb;
328
329 memset(&xpp, 0, sizeof(xpp));
330 memset(&xecfg, 0, sizeof(xecfg));
331 xecfg.ctxlen = xecfg.interhunkctxlen = 0;
332
333 cbdata.diff = out;
334 xecfg.hunk_func = collect_diff_cb;
335 memset(&ecb, 0, sizeof(ecb));
336 ecb.priv = &cbdata;
337 xdi_diff(parent, target, &xpp, &xecfg, &ecb);
338}
339
340/*
341 * These are handy for debugging. Removing them with #if 0 silences
342 * the "unused function" warning.
343 */
344#if 0
345static void dump_range_set(struct range_set *rs, const char *desc)
346{
347 int i;
348 printf("range set %s (%d items):\n", desc, rs->nr);
349 for (i = 0; i < rs->nr; i++)
350 printf("\t[%ld,%ld]\n", rs->ranges[i].start, rs->ranges[i].end);
351}
352
353static void dump_line_log_data(struct line_log_data *r)
354{
355 char buf[4096];
356 while (r) {
357 snprintf(buf, 4096, "file %s\n", r->spec->path);
358 dump_range_set(&r->ranges, buf);
359 r = r->next;
360 }
361}
362
363static void dump_diff_ranges(struct diff_ranges *diff, const char *desc)
364{
365 int i;
366 assert(diff->parent.nr == diff->target.nr);
367 printf("diff ranges %s (%d items):\n", desc, diff->parent.nr);
368 printf("\tparent\ttarget\n");
369 for (i = 0; i < diff->parent.nr; i++) {
370 printf("\t[%ld,%ld]\t[%ld,%ld]\n",
371 diff->parent.ranges[i].start,
372 diff->parent.ranges[i].end,
373 diff->target.ranges[i].start,
374 diff->target.ranges[i].end);
375 }
376}
377#endif
378
379
380static int ranges_overlap(struct range *a, struct range *b)
381{
382 return !(a->end <= b->start || b->end <= a->start);
383}
384
385/*
386 * Given a diff and the set of interesting ranges, determine all hunks
387 * of the diff which touch (overlap) at least one of the interesting
388 * ranges in the target.
389 */
390static void diff_ranges_filter_touched(struct diff_ranges *out,
391 struct diff_ranges *diff,
392 struct range_set *rs)
393{
394 int i, j = 0;
395
396 assert(out->target.nr == 0);
397
398 for (i = 0; i < diff->target.nr; i++) {
399 while (diff->target.ranges[i].start > rs->ranges[j].end) {
400 j++;
401 if (j == rs->nr)
402 return;
403 }
404 if (ranges_overlap(&diff->target.ranges[i], &rs->ranges[j])) {
405 range_set_append(&out->parent,
406 diff->parent.ranges[i].start,
407 diff->parent.ranges[i].end);
408 range_set_append(&out->target,
409 diff->target.ranges[i].start,
410 diff->target.ranges[i].end);
411 }
412 }
413}
414
415/*
416 * Adjust the line counts in 'rs' to account for the lines
417 * added/removed in the diff.
418 */
419static void range_set_shift_diff(struct range_set *out,
420 struct range_set *rs,
421 struct diff_ranges *diff)
422{
423 int i, j = 0;
424 long offset = 0;
425 struct range *src = rs->ranges;
426 struct range *target = diff->target.ranges;
427 struct range *parent = diff->parent.ranges;
428
429 for (i = 0; i < rs->nr; i++) {
430 while (j < diff->target.nr && src[i].start >= target[j].start) {
431 offset += (parent[j].end-parent[j].start)
432 - (target[j].end-target[j].start);
433 j++;
434 }
435 range_set_append(out, src[i].start+offset, src[i].end+offset);
436 }
437}
438
439/*
440 * Given a diff and the set of interesting ranges, map the ranges
441 * across the diff. That is: observe that the target commit takes
442 * blame for all the + (target-side) ranges. So for every pair of
443 * ranges in the diff that was touched, we remove the latter and add
444 * its parent side.
445 */
446static void range_set_map_across_diff(struct range_set *out,
447 struct range_set *rs,
448 struct diff_ranges *diff,
449 struct diff_ranges **touched_out)
450{
451 struct diff_ranges *touched = xmalloc(sizeof(*touched));
452 struct range_set tmp1 = RANGE_SET_INIT;
453 struct range_set tmp2 = RANGE_SET_INIT;
454
455 diff_ranges_init(touched);
456 diff_ranges_filter_touched(touched, diff, rs);
457 range_set_difference(&tmp1, rs, &touched->target);
458 range_set_shift_diff(&tmp2, &tmp1, diff);
459 range_set_union(out, &tmp2, &touched->parent);
460 range_set_release(&tmp1);
461 range_set_release(&tmp2);
462
463 *touched_out = touched;
464}
465
12da1d1f
TR
466static struct commit *check_single_commit(struct rev_info *revs)
467{
468 struct object *commit = NULL;
469 int found = -1;
470 int i;
471
472 for (i = 0; i < revs->pending.nr; i++) {
473 struct object *obj = revs->pending.objects[i].item;
474 if (obj->flags & UNINTERESTING)
475 continue;
476 while (obj->type == OBJ_TAG)
477 obj = deref_tag(obj, NULL, 0);
478 if (obj->type != OBJ_COMMIT)
479 die("Non commit %s?", revs->pending.objects[i].name);
480 if (commit)
481 die("More than one commit to dig from: %s and %s?",
482 revs->pending.objects[i].name,
483 revs->pending.objects[found].name);
484 commit = obj;
485 found = i;
486 }
487
488 if (!commit)
489 die("No commit specified?");
490
491 return (struct commit *) commit;
492}
493
494static void fill_blob_sha1(struct commit *commit, struct diff_filespec *spec)
495{
496 unsigned mode;
497 unsigned char sha1[20];
498
499 if (get_tree_entry(commit->object.sha1, spec->path,
500 sha1, &mode))
501 die("There is no path %s in the commit", spec->path);
502 fill_filespec(spec, sha1, 1, mode);
503
504 return;
505}
506
507static void fill_line_ends(struct diff_filespec *spec, long *lines,
508 unsigned long **line_ends)
509{
510 int num = 0, size = 50;
511 long cur = 0;
512 unsigned long *ends = NULL;
513 char *data = NULL;
514
515 if (diff_populate_filespec(spec, 0))
516 die("Cannot read blob %s", sha1_to_hex(spec->sha1));
517
518 ends = xmalloc(size * sizeof(*ends));
519 ends[cur++] = 0;
520 data = spec->data;
521 while (num < spec->size) {
522 if (data[num] == '\n' || num == spec->size - 1) {
523 ALLOC_GROW(ends, (cur + 1), size);
524 ends[cur++] = num;
525 }
526 num++;
527 }
528
529 /* shrink the array to fit the elements */
530 ends = xrealloc(ends, cur * sizeof(*ends));
531 *lines = cur-1;
532 *line_ends = ends;
533}
534
535struct nth_line_cb {
536 struct diff_filespec *spec;
537 long lines;
538 unsigned long *line_ends;
539};
540
541static const char *nth_line(void *data, long line)
542{
543 struct nth_line_cb *d = data;
544 assert(d && line <= d->lines);
545 assert(d->spec && d->spec->data);
546
547 if (line == 0)
548 return (char *)d->spec->data;
549 else
550 return (char *)d->spec->data + d->line_ends[line] + 1;
551}
552
553static struct line_log_data *
554parse_lines(struct commit *commit, const char *prefix, struct string_list *args)
555{
556 long lines = 0;
557 unsigned long *ends = NULL;
558 struct nth_line_cb cb_data;
559 struct string_list_item *item;
560 struct line_log_data *ranges = NULL;
561
562 for_each_string_list_item(item, args) {
563 const char *name_part, *range_part;
564 const char *full_name;
565 struct diff_filespec *spec;
566 long begin = 0, end = 0;
567
568 name_part = skip_range_arg(item->string);
569 if (!name_part || *name_part != ':' || !name_part[1])
570 die("-L argument '%s' not of the form start,end:file",
571 item->string);
572 range_part = xstrndup(item->string, name_part - item->string);
573 name_part++;
574
575 full_name = prefix_path(prefix, prefix ? strlen(prefix) : 0,
576 name_part);
577
578 spec = alloc_filespec(full_name);
579 fill_blob_sha1(commit, spec);
580 fill_line_ends(spec, &lines, &ends);
581 cb_data.spec = spec;
582 cb_data.lines = lines;
583 cb_data.line_ends = ends;
584
585 if (parse_range_arg(range_part, nth_line, &cb_data,
13b8f68c
TR
586 lines, &begin, &end,
587 spec->path))
12da1d1f
TR
588 die("malformed -L argument '%s'", range_part);
589 if (begin < 1)
590 begin = 1;
591 if (end < 1)
592 end = lines;
593 begin--;
594 if (lines < end || lines < begin)
595 die("file %s has only %ld lines", name_part, lines);
596 line_log_data_insert(&ranges, spec, begin, end);
597
598 free(ends);
599 ends = NULL;
600 }
601
602 return ranges;
603}
604
605static struct line_log_data *line_log_data_copy_one(struct line_log_data *r)
606{
607 struct line_log_data *ret = xmalloc(sizeof(*ret));
608
609 assert(r);
610 line_log_data_init(ret);
611 range_set_copy(&ret->ranges, &r->ranges);
612
613 ret->spec = r->spec;
614 assert(ret->spec);
615 ret->spec->count++;
616
617 return ret;
618}
619
620static struct line_log_data *
621line_log_data_copy(struct line_log_data *r)
622{
623 struct line_log_data *ret = NULL;
624 struct line_log_data *tmp = NULL, *prev = NULL;
625
626 assert(r);
627 ret = tmp = prev = line_log_data_copy_one(r);
628 r = r->next;
629 while (r) {
630 tmp = line_log_data_copy_one(r);
631 prev->next = tmp;
632 prev = tmp;
633 r = r->next;
634 }
635
636 return ret;
637}
638
639/* merge two range sets across files */
640static struct line_log_data *line_log_data_merge(struct line_log_data *a,
641 struct line_log_data *b)
642{
643 struct line_log_data *head = NULL, **pp = &head;
644
645 while (a || b) {
646 struct line_log_data *src;
647 struct line_log_data *src2 = NULL;
648 struct line_log_data *d;
649 int cmp;
650 if (!a)
651 cmp = 1;
652 else if (!b)
653 cmp = -1;
654 else
655 cmp = strcmp(a->spec->path, b->spec->path);
656 if (cmp < 0) {
657 src = a;
658 a = a->next;
659 } else if (cmp == 0) {
660 src = a;
661 a = a->next;
662 src2 = b;
663 b = b->next;
664 } else {
665 src = b;
666 b = b->next;
667 }
668 d = xmalloc(sizeof(struct line_log_data));
669 line_log_data_init(d);
670 d->spec = src->spec;
671 d->spec->count++;
672 *pp = d;
673 pp = &d->next;
674 if (src2)
675 range_set_union(&d->ranges, &src->ranges, &src2->ranges);
676 else
677 range_set_copy(&d->ranges, &src->ranges);
678 }
679
680 return head;
681}
682
683static void add_line_range(struct rev_info *revs, struct commit *commit,
684 struct line_log_data *range)
685{
686 struct line_log_data *old = NULL;
687 struct line_log_data *new = NULL;
688
689 old = lookup_decoration(&revs->line_log_data, &commit->object);
690 if (old && range) {
691 new = line_log_data_merge(old, range);
692 free_line_log_data(old);
693 } else if (range)
694 new = line_log_data_copy(range);
695
696 if (new)
697 add_decoration(&revs->line_log_data, &commit->object, new);
698}
699
700static void clear_commit_line_range(struct rev_info *revs, struct commit *commit)
701{
702 struct line_log_data *r;
703 r = lookup_decoration(&revs->line_log_data, &commit->object);
704 if (!r)
705 return;
706 free_line_log_data(r);
707 add_decoration(&revs->line_log_data, &commit->object, NULL);
708}
709
710static struct line_log_data *lookup_line_range(struct rev_info *revs,
711 struct commit *commit)
712{
713 struct line_log_data *ret = NULL;
4596f190 714 struct line_log_data *d;
12da1d1f
TR
715
716 ret = lookup_decoration(&revs->line_log_data, &commit->object);
4596f190
TR
717
718 for (d = ret; d; d = d->next)
719 range_set_check_invariants(&d->ranges);
720
12da1d1f
TR
721 return ret;
722}
723
724void line_log_init(struct rev_info *rev, const char *prefix, struct string_list *args)
725{
726 struct commit *commit = NULL;
727 struct line_log_data *range;
728
729 commit = check_single_commit(rev);
730 range = parse_lines(commit, prefix, args);
731 add_line_range(rev, commit, range);
732
733 if (!rev->diffopt.detect_rename) {
734 int i, count = 0;
735 struct line_log_data *r = range;
736 const char **paths;
737 while (r) {
738 count++;
739 r = r->next;
740 }
741 paths = xmalloc((count+1)*sizeof(char *));
742 r = range;
743 for (i = 0; i < count; i++) {
744 paths[i] = xstrdup(r->spec->path);
745 r = r->next;
746 }
747 paths[count] = NULL;
748 init_pathspec(&rev->diffopt.pathspec, paths);
749 free(paths);
750 }
751}
752
753static void load_tree_desc(struct tree_desc *desc, void **tree,
754 const unsigned char *sha1)
755{
756 unsigned long size;
757 *tree = read_object_with_reference(sha1, tree_type, &size, NULL);
758 if (!*tree)
759 die("Unable to read tree (%s)", sha1_to_hex(sha1));
760 init_tree_desc(desc, *tree, size);
761}
762
763static int count_parents(struct commit *commit)
764{
765 struct commit_list *parents = commit->parents;
766 int count = 0;
767 while (parents) {
768 count++;
769 parents = parents->next;
770 }
771 return count;
772}
773
774static void move_diff_queue(struct diff_queue_struct *dst,
775 struct diff_queue_struct *src)
776{
777 assert(src != dst);
778 memcpy(dst, src, sizeof(struct diff_queue_struct));
779 DIFF_QUEUE_CLEAR(src);
780}
781
39410bf0
TR
782static void filter_diffs_for_paths(struct line_log_data *range, int keep_deletions)
783{
784 int i;
785 struct diff_queue_struct outq;
786 DIFF_QUEUE_CLEAR(&outq);
787
788 for (i = 0; i < diff_queued_diff.nr; i++) {
789 struct diff_filepair *p = diff_queued_diff.queue[i];
790 struct line_log_data *rg = NULL;
791
792 if (!DIFF_FILE_VALID(p->two)) {
793 if (keep_deletions)
794 diff_q(&outq, p);
795 else
796 diff_free_filepair(p);
797 continue;
798 }
799 for (rg = range; rg; rg = rg->next) {
800 if (!strcmp(rg->spec->path, p->two->path))
801 break;
802 }
803 if (rg)
804 diff_q(&outq, p);
805 else
806 diff_free_filepair(p);
807 }
808 free(diff_queued_diff.queue);
809 diff_queued_diff = outq;
810}
811
812static inline int diff_might_be_rename(void)
813{
814 int i;
815 for (i = 0; i < diff_queued_diff.nr; i++)
816 if (!DIFF_FILE_VALID(diff_queued_diff.queue[i]->one)) {
817 /* fprintf(stderr, "diff_might_be_rename found creation of: %s\n", */
818 /* diff_queued_diff.queue[i]->two->path); */
819 return 1;
820 }
821 return 0;
822}
823
824static void queue_diffs(struct line_log_data *range,
825 struct diff_options *opt,
12da1d1f
TR
826 struct diff_queue_struct *queue,
827 struct commit *commit, struct commit *parent)
828{
829 void *tree1 = NULL, *tree2 = NULL;
830 struct tree_desc desc1, desc2;
831
832 assert(commit);
833 load_tree_desc(&desc2, &tree2, commit->tree->object.sha1);
834 if (parent)
835 load_tree_desc(&desc1, &tree1, parent->tree->object.sha1);
836 else
837 init_tree_desc(&desc1, "", 0);
838
839 DIFF_QUEUE_CLEAR(&diff_queued_diff);
840 diff_tree(&desc1, &desc2, "", opt);
39410bf0
TR
841 if (opt->detect_rename) {
842 filter_diffs_for_paths(range, 1);
843 if (diff_might_be_rename())
844 diffcore_std(opt);
845 filter_diffs_for_paths(range, 0);
846 }
12da1d1f
TR
847 move_diff_queue(queue, &diff_queued_diff);
848
849 if (tree1)
850 free(tree1);
851 if (tree2)
852 free(tree2);
853}
854
855static char *get_nth_line(long line, unsigned long *ends, void *data)
856{
857 if (line == 0)
858 return (char *)data;
859 else
860 return (char *)data + ends[line] + 1;
861}
862
863static void print_line(const char *prefix, char first,
864 long line, unsigned long *ends, void *data,
865 const char *color, const char *reset)
866{
867 char *begin = get_nth_line(line, ends, data);
868 char *end = get_nth_line(line+1, ends, data);
869 int had_nl = 0;
870
871 if (end > begin && end[-1] == '\n') {
872 end--;
873 had_nl = 1;
874 }
875
876 fputs(prefix, stdout);
877 fputs(color, stdout);
878 putchar(first);
879 fwrite(begin, 1, end-begin, stdout);
880 fputs(reset, stdout);
881 putchar('\n');
882 if (!had_nl)
883 fputs("\\ No newline at end of file\n", stdout);
884}
885
886static char *output_prefix(struct diff_options *opt)
887{
888 char *prefix = "";
889
890 if (opt->output_prefix) {
891 struct strbuf *sb = opt->output_prefix(opt, opt->output_prefix_data);
892 prefix = sb->buf;
893 }
894
895 return prefix;
896}
897
898static void dump_diff_hacky_one(struct rev_info *rev, struct line_log_data *range)
899{
900 int i, j = 0;
901 long p_lines, t_lines;
902 unsigned long *p_ends = NULL, *t_ends = NULL;
903 struct diff_filepair *pair = range->pair;
904 struct diff_ranges *diff = &range->diff;
905
906 struct diff_options *opt = &rev->diffopt;
907 char *prefix = output_prefix(opt);
908 const char *c_reset = diff_get_color(opt->use_color, DIFF_RESET);
909 const char *c_frag = diff_get_color(opt->use_color, DIFF_FRAGINFO);
910 const char *c_meta = diff_get_color(opt->use_color, DIFF_METAINFO);
911 const char *c_old = diff_get_color(opt->use_color, DIFF_FILE_OLD);
912 const char *c_new = diff_get_color(opt->use_color, DIFF_FILE_NEW);
913 const char *c_plain = diff_get_color(opt->use_color, DIFF_PLAIN);
914
915 if (!pair || !diff)
916 return;
917
918 if (pair->one->sha1_valid)
919 fill_line_ends(pair->one, &p_lines, &p_ends);
920 fill_line_ends(pair->two, &t_lines, &t_ends);
921
922 printf("%s%sdiff --git a/%s b/%s%s\n", prefix, c_meta, pair->one->path, pair->two->path, c_reset);
923 printf("%s%s--- %s%s%s\n", prefix, c_meta,
924 pair->one->sha1_valid ? "a/" : "",
925 pair->one->sha1_valid ? pair->one->path : "/dev/null",
926 c_reset);
927 printf("%s%s+++ b/%s%s\n", prefix, c_meta, pair->two->path, c_reset);
928 for (i = 0; i < range->ranges.nr; i++) {
929 long p_start, p_end;
930 long t_start = range->ranges.ranges[i].start;
931 long t_end = range->ranges.ranges[i].end;
932 long t_cur = t_start;
933 int j_last;
934
935 while (j < diff->target.nr && diff->target.ranges[j].end < t_start)
936 j++;
937 if (j == diff->target.nr || diff->target.ranges[j].start > t_end)
938 continue;
939
940 /* Scan ahead to determine the last diff that falls in this range */
941 j_last = j;
942 while (j_last < diff->target.nr && diff->target.ranges[j_last].start < t_end)
943 j_last++;
944 if (j_last > j)
945 j_last--;
946
947 /*
948 * Compute parent hunk headers: we know that the diff
949 * has the correct line numbers (but not all hunks).
950 * So it suffices to shift the start/end according to
951 * the line numbers of the first/last hunk(s) that
952 * fall in this range.
953 */
954 if (t_start < diff->target.ranges[j].start)
955 p_start = diff->parent.ranges[j].start - (diff->target.ranges[j].start-t_start);
956 else
957 p_start = diff->parent.ranges[j].start;
958 if (t_end > diff->target.ranges[j_last].end)
959 p_end = diff->parent.ranges[j_last].end + (t_end-diff->target.ranges[j_last].end);
960 else
961 p_end = diff->parent.ranges[j_last].end;
962
963 if (!p_start && !p_end) {
964 p_start = -1;
965 p_end = -1;
966 }
967
968 /* Now output a diff hunk for this range */
969 printf("%s%s@@ -%ld,%ld +%ld,%ld @@%s\n",
970 prefix, c_frag,
971 p_start+1, p_end-p_start, t_start+1, t_end-t_start,
972 c_reset);
973 while (j < diff->target.nr && diff->target.ranges[j].start < t_end) {
974 int k;
975 for (; t_cur < diff->target.ranges[j].start; t_cur++)
976 print_line(prefix, ' ', t_cur, t_ends, pair->two->data,
977 c_plain, c_reset);
978 for (k = diff->parent.ranges[j].start; k < diff->parent.ranges[j].end; k++)
979 print_line(prefix, '-', k, p_ends, pair->one->data,
980 c_old, c_reset);
981 for (; t_cur < diff->target.ranges[j].end && t_cur < t_end; t_cur++)
982 print_line(prefix, '+', t_cur, t_ends, pair->two->data,
983 c_new, c_reset);
984 j++;
985 }
986 for (; t_cur < t_end; t_cur++)
987 print_line(prefix, ' ', t_cur, t_ends, pair->two->data,
988 c_plain, c_reset);
989 }
990
991 free(p_ends);
992 free(t_ends);
993}
994
995/*
996 * NEEDSWORK: manually building a diff here is not the Right
997 * Thing(tm). log -L should be built into the diff pipeline.
998 */
999static void dump_diff_hacky(struct rev_info *rev, struct line_log_data *range)
1000{
1001 puts(output_prefix(&rev->diffopt));
1002 while (range) {
1003 dump_diff_hacky_one(rev, range);
1004 range = range->next;
1005 }
1006}
1007
1008/*
1009 * Unlike most other functions, this destructively operates on
1010 * 'range'.
1011 */
1012static int process_diff_filepair(struct rev_info *rev,
1013 struct diff_filepair *pair,
1014 struct line_log_data *range,
1015 struct diff_ranges **diff_out)
1016{
1017 struct line_log_data *rg = range;
1018 struct range_set tmp;
1019 struct diff_ranges diff;
1020 mmfile_t file_parent, file_target;
1021
1022 assert(pair->two->path);
1023 while (rg) {
1024 assert(rg->spec->path);
1025 if (!strcmp(rg->spec->path, pair->two->path))
1026 break;
1027 rg = rg->next;
1028 }
1029
1030 if (!rg)
1031 return 0;
1032 if (rg->ranges.nr == 0)
1033 return 0;
1034
1035 assert(pair->two->sha1_valid);
1036 diff_populate_filespec(pair->two, 0);
1037 file_target.ptr = pair->two->data;
1038 file_target.size = pair->two->size;
1039
1040 if (pair->one->sha1_valid) {
1041 diff_populate_filespec(pair->one, 0);
1042 file_parent.ptr = pair->one->data;
1043 file_parent.size = pair->one->size;
1044 } else {
1045 file_parent.ptr = "";
1046 file_parent.size = 0;
1047 }
1048
1049 diff_ranges_init(&diff);
1050 collect_diff(&file_parent, &file_target, &diff);
1051
1052 /* NEEDSWORK should apply some heuristics to prevent mismatches */
1053 rg->spec->path = xstrdup(pair->one->path);
1054
1055 range_set_init(&tmp, 0);
1056 range_set_map_across_diff(&tmp, &rg->ranges, &diff, diff_out);
1057 range_set_release(&rg->ranges);
1058 range_set_move(&rg->ranges, &tmp);
1059
1060 diff_ranges_release(&diff);
1061
1062 return ((*diff_out)->parent.nr > 0);
1063}
1064
1065static struct diff_filepair *diff_filepair_dup(struct diff_filepair *pair)
1066{
1067 struct diff_filepair *new = xmalloc(sizeof(struct diff_filepair));
1068 new->one = pair->one;
1069 new->two = pair->two;
1070 new->one->count++;
1071 new->two->count++;
1072 return new;
1073}
1074
1075static void free_diffqueues(int n, struct diff_queue_struct *dq)
1076{
1077 int i, j;
1078 for (i = 0; i < n; i++)
1079 for (j = 0; j < dq[i].nr; j++)
1080 diff_free_filepair(dq[i].queue[j]);
1081 free(dq);
1082}
1083
1084static int process_all_files(struct line_log_data **range_out,
1085 struct rev_info *rev,
1086 struct diff_queue_struct *queue,
1087 struct line_log_data *range)
1088{
1089 int i, changed = 0;
1090
1091 *range_out = line_log_data_copy(range);
1092
1093 for (i = 0; i < queue->nr; i++) {
1094 struct diff_ranges *pairdiff = NULL;
1095 if (process_diff_filepair(rev, queue->queue[i], *range_out, &pairdiff)) {
1096 struct line_log_data *rg = range;
1097 changed++;
1098 /* NEEDSWORK tramples over data structures not owned here */
1099 while (rg && strcmp(rg->spec->path, queue->queue[i]->two->path))
1100 rg = rg->next;
1101 assert(rg);
1102 rg->pair = diff_filepair_dup(queue->queue[i]);
1103 memcpy(&rg->diff, pairdiff, sizeof(struct diff_ranges));
1104 }
1105 }
1106
1107 return changed;
1108}
1109
1110int line_log_print(struct rev_info *rev, struct commit *commit)
1111{
1112 struct line_log_data *range = lookup_line_range(rev, commit);
1113
1114 show_log(rev);
1115 dump_diff_hacky(rev, range);
1116 return 1;
1117}
1118
1119static int process_ranges_ordinary_commit(struct rev_info *rev, struct commit *commit,
1120 struct line_log_data *range)
1121{
1122 struct commit *parent = NULL;
1123 struct diff_queue_struct queue;
1124 struct line_log_data *parent_range;
1125 int changed;
1126
1127 if (commit->parents)
1128 parent = commit->parents->item;
1129
39410bf0 1130 queue_diffs(range, &rev->diffopt, &queue, commit, parent);
12da1d1f
TR
1131 changed = process_all_files(&parent_range, rev, &queue, range);
1132 if (parent)
1133 add_line_range(rev, parent, parent_range);
1134 return changed;
1135}
1136
1137static int process_ranges_merge_commit(struct rev_info *rev, struct commit *commit,
1138 struct line_log_data *range)
1139{
1140 struct diff_queue_struct *diffqueues;
1141 struct line_log_data **cand;
1142 struct commit **parents;
1143 struct commit_list *p;
1144 int i;
1145 int nparents = count_parents(commit);
1146
1147 diffqueues = xmalloc(nparents * sizeof(*diffqueues));
1148 cand = xmalloc(nparents * sizeof(*cand));
1149 parents = xmalloc(nparents * sizeof(*parents));
1150
1151 p = commit->parents;
1152 for (i = 0; i < nparents; i++) {
1153 parents[i] = p->item;
1154 p = p->next;
39410bf0 1155 queue_diffs(range, &rev->diffopt, &diffqueues[i], commit, parents[i]);
12da1d1f
TR
1156 }
1157
1158 for (i = 0; i < nparents; i++) {
1159 int changed;
1160 cand[i] = NULL;
1161 changed = process_all_files(&cand[i], rev, &diffqueues[i], range);
1162 if (!changed) {
1163 /*
1164 * This parent can take all the blame, so we
1165 * don't follow any other path in history
1166 */
1167 add_line_range(rev, parents[i], cand[i]);
1168 clear_commit_line_range(rev, commit);
1169 commit->parents = xmalloc(sizeof(struct commit_list));
1170 commit->parents->item = parents[i];
1171 commit->parents->next = NULL;
1172 free(parents);
1173 free(cand);
1174 free_diffqueues(nparents, diffqueues);
1175 /* NEEDSWORK leaking like a sieve */
1176 return 0;
1177 }
1178 }
1179
1180 /*
1181 * No single parent took the blame. We add the candidates
1182 * from the above loop to the parents.
1183 */
1184 for (i = 0; i < nparents; i++) {
1185 add_line_range(rev, parents[i], cand[i]);
1186 }
1187
1188 clear_commit_line_range(rev, commit);
1189 free(parents);
1190 free(cand);
1191 free_diffqueues(nparents, diffqueues);
1192 return 1;
1193
1194 /* NEEDSWORK evil merge detection stuff */
1195 /* NEEDSWORK leaking like a sieve */
1196}
1197
1198static int process_ranges_arbitrary_commit(struct rev_info *rev, struct commit *commit)
1199{
1200 struct line_log_data *range = lookup_line_range(rev, commit);
1201 int changed = 0;
1202
1203 if (range) {
1204 if (!commit->parents || !commit->parents->next)
1205 changed = process_ranges_ordinary_commit(rev, commit, range);
1206 else
1207 changed = process_ranges_merge_commit(rev, commit, range);
1208 }
1209
1210 if (!changed)
1211 commit->object.flags |= TREESAME;
1212
1213 return changed;
1214}
1215
1216static enum rewrite_result line_log_rewrite_one(struct rev_info *rev, struct commit **pp)
1217{
1218 for (;;) {
1219 struct commit *p = *pp;
1220 if (p->parents && p->parents->next)
1221 return rewrite_one_ok;
1222 if (p->object.flags & UNINTERESTING)
1223 return rewrite_one_ok;
1224 if (!(p->object.flags & TREESAME))
1225 return rewrite_one_ok;
1226 if (!p->parents)
1227 return rewrite_one_noparents;
1228 *pp = p->parents->item;
1229 }
1230}
1231
1232int line_log_filter(struct rev_info *rev)
1233{
1234 struct commit *commit;
1235 struct commit_list *list = rev->commits;
1236 struct commit_list *out = NULL, **pp = &out;
1237
1238 while (list) {
1239 struct commit_list *to_free = NULL;
1240 commit = list->item;
1241 if (process_ranges_arbitrary_commit(rev, commit)) {
1242 *pp = list;
1243 pp = &list->next;
1244 } else
1245 to_free = list;
1246 list = list->next;
1247 free(to_free);
1248 }
1249 *pp = NULL;
1250
1251 for (list = out; list; list = list->next)
1252 rewrite_parents(rev, list->item, line_log_rewrite_one);
1253
1254 rev->commits = out;
1255
1256 return 0;
1257}