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