1 #include "git-compat-util.h"
3 #include "line-range.h"
12 #include "xdiff-interface.h"
21 static void range_set_grow(struct range_set
*rs
, size_t extra
)
23 ALLOC_GROW(rs
->ranges
, rs
->nr
+ extra
, rs
->alloc
);
26 /* Either initialization would be fine */
27 #define RANGE_SET_INIT {0}
29 void range_set_init(struct range_set
*rs
, size_t prealloc
)
31 rs
->alloc
= rs
->nr
= 0;
34 range_set_grow(rs
, prealloc
);
37 void range_set_release(struct range_set
*rs
)
39 FREE_AND_NULL(rs
->ranges
);
40 rs
->alloc
= rs
->nr
= 0;
43 /* dst must be uninitialized! */
44 static void range_set_copy(struct range_set
*dst
, struct range_set
*src
)
46 range_set_init(dst
, src
->nr
);
47 COPY_ARRAY(dst
->ranges
, src
->ranges
, src
->nr
);
51 static void range_set_move(struct range_set
*dst
, struct range_set
*src
)
53 range_set_release(dst
);
54 dst
->ranges
= src
->ranges
;
56 dst
->alloc
= src
->alloc
;
58 src
->alloc
= src
->nr
= 0;
61 /* tack on a _new_ range _at the end_ */
62 void range_set_append_unsafe(struct range_set
*rs
, long a
, long b
)
65 range_set_grow(rs
, 1);
66 rs
->ranges
[rs
->nr
].start
= a
;
67 rs
->ranges
[rs
->nr
].end
= b
;
71 void range_set_append(struct range_set
*rs
, long a
, long b
)
73 assert(rs
->nr
== 0 || rs
->ranges
[rs
->nr
-1].end
<= a
);
74 range_set_append_unsafe(rs
, a
, b
);
77 static int range_cmp(const void *_r
, const void *_s
)
79 const struct range
*r
= _r
;
80 const struct range
*s
= _s
;
82 /* this could be simply 'return r.start-s.start', but for the types */
83 if (r
->start
== s
->start
)
85 if (r
->start
< s
->start
)
91 * Check that the ranges are non-empty, sorted and non-overlapping
93 static void range_set_check_invariants(struct range_set
*rs
)
101 assert(rs
->ranges
[0].start
< rs
->ranges
[0].end
);
103 for (i
= 1; i
< rs
->nr
; i
++) {
104 assert(rs
->ranges
[i
-1].end
< rs
->ranges
[i
].start
);
105 assert(rs
->ranges
[i
].start
< rs
->ranges
[i
].end
);
110 * In-place pass of sorting and merging the ranges in the range set,
111 * to establish the invariants when we get the ranges from the user
113 void sort_and_merge_range_set(struct range_set
*rs
)
116 unsigned int o
= 0; /* output cursor */
118 QSORT(rs
->ranges
, rs
->nr
, range_cmp
);
120 for (i
= 0; i
< rs
->nr
; i
++) {
121 if (rs
->ranges
[i
].start
== rs
->ranges
[i
].end
)
123 if (o
> 0 && rs
->ranges
[i
].start
<= rs
->ranges
[o
-1].end
) {
124 if (rs
->ranges
[o
-1].end
< rs
->ranges
[i
].end
)
125 rs
->ranges
[o
-1].end
= rs
->ranges
[i
].end
;
127 rs
->ranges
[o
].start
= rs
->ranges
[i
].start
;
128 rs
->ranges
[o
].end
= rs
->ranges
[i
].end
;
135 range_set_check_invariants(rs
);
139 * Union of range sets (i.e., sets of line numbers). Used to merge
140 * them when searches meet at a common ancestor.
142 * This is also where the ranges are consolidated into canonical form:
143 * overlapping and adjacent ranges are merged, and empty ranges are
146 static void range_set_union(struct range_set
*out
,
147 struct range_set
*a
, struct range_set
*b
)
149 unsigned int i
= 0, j
= 0;
150 struct range
*ra
= a
->ranges
;
151 struct range
*rb
= b
->ranges
;
152 /* cannot make an alias of out->ranges: it may change during grow */
154 assert(out
->nr
== 0);
155 while (i
< a
->nr
|| j
< b
->nr
) {
156 struct range
*new_range
;
157 if (i
< a
->nr
&& j
< b
->nr
) {
158 if (ra
[i
].start
< rb
[j
].start
)
159 new_range
= &ra
[i
++];
160 else if (ra
[i
].start
> rb
[j
].start
)
161 new_range
= &rb
[j
++];
162 else if (ra
[i
].end
< rb
[j
].end
)
163 new_range
= &ra
[i
++];
165 new_range
= &rb
[j
++];
166 } else if (i
< a
->nr
) /* b exhausted */
167 new_range
= &ra
[i
++];
168 else /* a exhausted */
169 new_range
= &rb
[j
++];
170 if (new_range
->start
== new_range
->end
)
172 else if (!out
->nr
|| out
->ranges
[out
->nr
-1].end
< new_range
->start
) {
173 range_set_grow(out
, 1);
174 out
->ranges
[out
->nr
].start
= new_range
->start
;
175 out
->ranges
[out
->nr
].end
= new_range
->end
;
177 } else if (out
->ranges
[out
->nr
-1].end
< new_range
->end
) {
178 out
->ranges
[out
->nr
-1].end
= new_range
->end
;
184 * Difference of range sets (out = a \ b). Pass the "interesting"
185 * ranges as 'a' and the target side of the diff as 'b': it removes
186 * the ranges for which the commit is responsible.
188 static void range_set_difference(struct range_set
*out
,
189 struct range_set
*a
, struct range_set
*b
)
191 unsigned int i
, j
= 0;
192 for (i
= 0; i
< a
->nr
; i
++) {
193 long start
= a
->ranges
[i
].start
;
194 long end
= a
->ranges
[i
].end
;
195 while (start
< end
) {
196 while (j
< b
->nr
&& start
>= b
->ranges
[j
].end
)
202 if (j
>= b
->nr
|| end
< b
->ranges
[j
].start
) {
208 range_set_append(out
, start
, end
);
211 if (start
>= b
->ranges
[j
].start
) {
216 start
= b
->ranges
[j
].end
;
217 } else if (end
> b
->ranges
[j
].start
) {
222 if (start
< b
->ranges
[j
].start
)
223 range_set_append(out
, start
, b
->ranges
[j
].start
);
224 start
= b
->ranges
[j
].end
;
230 static void diff_ranges_init(struct diff_ranges
*diff
)
232 range_set_init(&diff
->parent
, 0);
233 range_set_init(&diff
->target
, 0);
236 static void diff_ranges_release(struct diff_ranges
*diff
)
238 range_set_release(&diff
->parent
);
239 range_set_release(&diff
->target
);
242 static void line_log_data_init(struct line_log_data
*r
)
244 memset(r
, 0, sizeof(struct line_log_data
));
245 range_set_init(&r
->ranges
, 0);
248 static void line_log_data_clear(struct line_log_data
*r
)
250 range_set_release(&r
->ranges
);
252 diff_free_filepair(r
->pair
);
255 static void free_line_log_data(struct line_log_data
*r
)
258 struct line_log_data
*next
= r
->next
;
259 line_log_data_clear(r
);
265 static struct line_log_data
*
266 search_line_log_data(struct line_log_data
*list
, const char *path
,
267 struct line_log_data
**insertion_point
)
269 struct line_log_data
*p
= list
;
271 *insertion_point
= NULL
;
273 int cmp
= strcmp(p
->path
, path
);
276 if (insertion_point
&& cmp
< 0)
277 *insertion_point
= p
;
284 * Note: takes ownership of 'path', which happens to be what the only
287 static void line_log_data_insert(struct line_log_data
**list
,
289 long begin
, long end
)
291 struct line_log_data
*ip
;
292 struct line_log_data
*p
= search_line_log_data(*list
, path
, &ip
);
295 range_set_append_unsafe(&p
->ranges
, begin
, end
);
302 range_set_append(&p
->ranges
, begin
, end
);
312 struct collect_diff_cbdata
{
313 struct diff_ranges
*diff
;
316 static int collect_diff_cb(long start_a
, long count_a
,
317 long start_b
, long count_b
,
320 struct collect_diff_cbdata
*d
= data
;
323 range_set_append(&d
->diff
->parent
, start_a
, start_a
+ count_a
);
325 range_set_append(&d
->diff
->target
, start_b
, start_b
+ count_b
);
330 static int collect_diff(mmfile_t
*parent
, mmfile_t
*target
, struct diff_ranges
*out
)
332 struct collect_diff_cbdata cbdata
= {NULL
};
337 memset(&xpp
, 0, sizeof(xpp
));
338 memset(&xecfg
, 0, sizeof(xecfg
));
339 xecfg
.ctxlen
= xecfg
.interhunkctxlen
= 0;
342 xecfg
.hunk_func
= collect_diff_cb
;
343 memset(&ecb
, 0, sizeof(ecb
));
345 return xdi_diff(parent
, target
, &xpp
, &xecfg
, &ecb
);
349 * These are handy for debugging. Removing them with #if 0 silences
350 * the "unused function" warning.
353 static void dump_range_set(struct range_set
*rs
, const char *desc
)
356 printf("range set %s (%d items):\n", desc
, rs
->nr
);
357 for (i
= 0; i
< rs
->nr
; i
++)
358 printf("\t[%ld,%ld]\n", rs
->ranges
[i
].start
, rs
->ranges
[i
].end
);
361 static void dump_line_log_data(struct line_log_data
*r
)
365 snprintf(buf
, 4096, "file %s\n", r
->path
);
366 dump_range_set(&r
->ranges
, buf
);
371 static void dump_diff_ranges(struct diff_ranges
*diff
, const char *desc
)
374 assert(diff
->parent
.nr
== diff
->target
.nr
);
375 printf("diff ranges %s (%d items):\n", desc
, diff
->parent
.nr
);
376 printf("\tparent\ttarget\n");
377 for (i
= 0; i
< diff
->parent
.nr
; i
++) {
378 printf("\t[%ld,%ld]\t[%ld,%ld]\n",
379 diff
->parent
.ranges
[i
].start
,
380 diff
->parent
.ranges
[i
].end
,
381 diff
->target
.ranges
[i
].start
,
382 diff
->target
.ranges
[i
].end
);
388 static int ranges_overlap(struct range
*a
, struct range
*b
)
390 return !(a
->end
<= b
->start
|| b
->end
<= a
->start
);
394 * Given a diff and the set of interesting ranges, determine all hunks
395 * of the diff which touch (overlap) at least one of the interesting
396 * ranges in the target.
398 static void diff_ranges_filter_touched(struct diff_ranges
*out
,
399 struct diff_ranges
*diff
,
400 struct range_set
*rs
)
402 unsigned int i
, j
= 0;
404 assert(out
->target
.nr
== 0);
406 for (i
= 0; i
< diff
->target
.nr
; i
++) {
407 while (diff
->target
.ranges
[i
].start
> rs
->ranges
[j
].end
) {
412 if (ranges_overlap(&diff
->target
.ranges
[i
], &rs
->ranges
[j
])) {
413 range_set_append(&out
->parent
,
414 diff
->parent
.ranges
[i
].start
,
415 diff
->parent
.ranges
[i
].end
);
416 range_set_append(&out
->target
,
417 diff
->target
.ranges
[i
].start
,
418 diff
->target
.ranges
[i
].end
);
424 * Adjust the line counts in 'rs' to account for the lines
425 * added/removed in the diff.
427 static void range_set_shift_diff(struct range_set
*out
,
428 struct range_set
*rs
,
429 struct diff_ranges
*diff
)
431 unsigned int i
, j
= 0;
433 struct range
*src
= rs
->ranges
;
434 struct range
*target
= diff
->target
.ranges
;
435 struct range
*parent
= diff
->parent
.ranges
;
437 for (i
= 0; i
< rs
->nr
; i
++) {
438 while (j
< diff
->target
.nr
&& src
[i
].start
>= target
[j
].start
) {
439 offset
+= (parent
[j
].end
-parent
[j
].start
)
440 - (target
[j
].end
-target
[j
].start
);
443 range_set_append(out
, src
[i
].start
+offset
, src
[i
].end
+offset
);
448 * Given a diff and the set of interesting ranges, map the ranges
449 * across the diff. That is: observe that the target commit takes
450 * blame for all the + (target-side) ranges. So for every pair of
451 * ranges in the diff that was touched, we remove the latter and add
454 static void range_set_map_across_diff(struct range_set
*out
,
455 struct range_set
*rs
,
456 struct diff_ranges
*diff
,
457 struct diff_ranges
**touched_out
)
459 struct diff_ranges
*touched
= xmalloc(sizeof(*touched
));
460 struct range_set tmp1
= RANGE_SET_INIT
;
461 struct range_set tmp2
= RANGE_SET_INIT
;
463 diff_ranges_init(touched
);
464 diff_ranges_filter_touched(touched
, diff
, rs
);
465 range_set_difference(&tmp1
, rs
, &touched
->target
);
466 range_set_shift_diff(&tmp2
, &tmp1
, diff
);
467 range_set_union(out
, &tmp2
, &touched
->parent
);
468 range_set_release(&tmp1
);
469 range_set_release(&tmp2
);
471 *touched_out
= touched
;
474 static struct commit
*check_single_commit(struct rev_info
*revs
)
476 struct object
*commit
= NULL
;
480 for (i
= 0; i
< revs
->pending
.nr
; i
++) {
481 struct object
*obj
= revs
->pending
.objects
[i
].item
;
482 if (obj
->flags
& UNINTERESTING
)
484 obj
= deref_tag(revs
->repo
, obj
, NULL
, 0);
485 if (!obj
|| obj
->type
!= OBJ_COMMIT
)
486 die("Non commit %s?", revs
->pending
.objects
[i
].name
);
488 die("More than one commit to dig from: %s and %s?",
489 revs
->pending
.objects
[i
].name
,
490 revs
->pending
.objects
[found
].name
);
496 die("No commit specified?");
498 return (struct commit
*) commit
;
501 static void fill_blob_sha1(struct repository
*r
, struct commit
*commit
,
502 struct diff_filespec
*spec
)
505 struct object_id oid
;
507 if (get_tree_entry(r
, &commit
->object
.oid
, spec
->path
, &oid
, &mode
))
508 die("There is no path %s in the commit", spec
->path
);
509 fill_filespec(spec
, &oid
, 1, mode
);
514 static void fill_line_ends(struct repository
*r
,
515 struct diff_filespec
*spec
,
517 unsigned long **line_ends
)
519 int num
= 0, size
= 50;
521 unsigned long *ends
= NULL
;
524 if (diff_populate_filespec(r
, spec
, NULL
))
525 die("Cannot read blob %s", oid_to_hex(&spec
->oid
));
527 ALLOC_ARRAY(ends
, size
);
530 while (num
< spec
->size
) {
531 if (data
[num
] == '\n' || num
== spec
->size
- 1) {
532 ALLOC_GROW(ends
, (cur
+ 1), size
);
538 /* shrink the array to fit the elements */
539 REALLOC_ARRAY(ends
, cur
);
545 struct diff_filespec
*spec
;
547 unsigned long *line_ends
;
550 static const char *nth_line(void *data
, long line
)
552 struct nth_line_cb
*d
= data
;
553 assert(d
&& line
<= d
->lines
);
554 assert(d
->spec
&& d
->spec
->data
);
557 return (char *)d
->spec
->data
;
559 return (char *)d
->spec
->data
+ d
->line_ends
[line
] + 1;
562 static struct line_log_data
*
563 parse_lines(struct repository
*r
, struct commit
*commit
,
564 const char *prefix
, struct string_list
*args
)
567 unsigned long *ends
= NULL
;
568 struct nth_line_cb cb_data
;
569 struct string_list_item
*item
;
570 struct line_log_data
*ranges
= NULL
;
571 struct line_log_data
*p
;
573 for_each_string_list_item(item
, args
) {
574 const char *name_part
, *range_part
;
576 struct diff_filespec
*spec
;
577 long begin
= 0, end
= 0;
580 name_part
= skip_range_arg(item
->string
, r
->index
);
581 if (!name_part
|| *name_part
!= ':' || !name_part
[1])
582 die("-L argument not 'start,end:file' or ':funcname:file': %s",
584 range_part
= xstrndup(item
->string
, name_part
- item
->string
);
587 full_name
= prefix_path(prefix
, prefix
? strlen(prefix
) : 0,
590 spec
= alloc_filespec(full_name
);
591 fill_blob_sha1(r
, commit
, spec
);
592 fill_line_ends(r
, spec
, &lines
, &ends
);
594 cb_data
.lines
= lines
;
595 cb_data
.line_ends
= ends
;
597 p
= search_line_log_data(ranges
, full_name
, NULL
);
598 if (p
&& p
->ranges
.nr
)
599 anchor
= p
->ranges
.ranges
[p
->ranges
.nr
- 1].end
+ 1;
603 if (parse_range_arg(range_part
, nth_line
, &cb_data
,
604 lines
, anchor
, &begin
, &end
,
605 full_name
, r
->index
))
606 die("malformed -L argument '%s'", range_part
);
607 if ((!lines
&& (begin
|| end
)) || lines
< begin
)
608 die("file %s has only %lu lines", name_part
, lines
);
611 if (end
< 1 || lines
< end
)
614 line_log_data_insert(&ranges
, full_name
, begin
, end
);
620 for (p
= ranges
; p
; p
= p
->next
)
621 sort_and_merge_range_set(&p
->ranges
);
626 static struct line_log_data
*line_log_data_copy_one(struct line_log_data
*r
)
628 struct line_log_data
*ret
= xmalloc(sizeof(*ret
));
631 line_log_data_init(ret
);
632 range_set_copy(&ret
->ranges
, &r
->ranges
);
634 ret
->path
= xstrdup(r
->path
);
639 static struct line_log_data
*
640 line_log_data_copy(struct line_log_data
*r
)
642 struct line_log_data
*ret
= NULL
;
643 struct line_log_data
*tmp
= NULL
, *prev
= NULL
;
646 ret
= tmp
= prev
= line_log_data_copy_one(r
);
649 tmp
= line_log_data_copy_one(r
);
658 /* merge two range sets across files */
659 static struct line_log_data
*line_log_data_merge(struct line_log_data
*a
,
660 struct line_log_data
*b
)
662 struct line_log_data
*head
= NULL
, **pp
= &head
;
665 struct line_log_data
*src
;
666 struct line_log_data
*src2
= NULL
;
667 struct line_log_data
*d
;
674 cmp
= strcmp(a
->path
, b
->path
);
678 } else if (cmp
== 0) {
687 d
= xmalloc(sizeof(struct line_log_data
));
688 line_log_data_init(d
);
689 d
->path
= xstrdup(src
->path
);
693 range_set_union(&d
->ranges
, &src
->ranges
, &src2
->ranges
);
695 range_set_copy(&d
->ranges
, &src
->ranges
);
701 static void add_line_range(struct rev_info
*revs
, struct commit
*commit
,
702 struct line_log_data
*range
)
704 struct line_log_data
*old_line
= NULL
;
705 struct line_log_data
*new_line
= NULL
;
707 old_line
= lookup_decoration(&revs
->line_log_data
, &commit
->object
);
708 if (old_line
&& range
) {
709 new_line
= line_log_data_merge(old_line
, range
);
710 free_line_log_data(old_line
);
712 new_line
= line_log_data_copy(range
);
715 add_decoration(&revs
->line_log_data
, &commit
->object
, new_line
);
718 static void clear_commit_line_range(struct rev_info
*revs
, struct commit
*commit
)
720 struct line_log_data
*r
;
721 r
= lookup_decoration(&revs
->line_log_data
, &commit
->object
);
724 free_line_log_data(r
);
725 add_decoration(&revs
->line_log_data
, &commit
->object
, NULL
);
728 static struct line_log_data
*lookup_line_range(struct rev_info
*revs
,
729 struct commit
*commit
)
731 struct line_log_data
*ret
= NULL
;
732 struct line_log_data
*d
;
734 ret
= lookup_decoration(&revs
->line_log_data
, &commit
->object
);
736 for (d
= ret
; d
; d
= d
->next
)
737 range_set_check_invariants(&d
->ranges
);
742 static int same_paths_in_pathspec_and_range(struct pathspec
*pathspec
,
743 struct line_log_data
*range
)
746 struct line_log_data
*r
;
748 for (i
= 0, r
= range
; i
< pathspec
->nr
&& r
; i
++, r
= r
->next
)
749 if (strcmp(pathspec
->items
[i
].match
, r
->path
))
751 if (i
< pathspec
->nr
|| r
)
752 /* different number of pathspec items and ranges */
758 static void parse_pathspec_from_ranges(struct pathspec
*pathspec
,
759 struct line_log_data
*range
)
761 struct line_log_data
*r
;
762 struct strvec array
= STRVEC_INIT
;
765 for (r
= range
; r
; r
= r
->next
)
766 strvec_push(&array
, r
->path
);
767 paths
= strvec_detach(&array
);
769 parse_pathspec(pathspec
, 0, PATHSPEC_PREFER_FULL
, "", paths
);
770 /* strings are now owned by pathspec */
774 void line_log_init(struct rev_info
*rev
, const char *prefix
, struct string_list
*args
)
776 struct commit
*commit
= NULL
;
777 struct line_log_data
*range
;
779 commit
= check_single_commit(rev
);
780 range
= parse_lines(rev
->diffopt
.repo
, commit
, prefix
, args
);
781 add_line_range(rev
, commit
, range
);
783 parse_pathspec_from_ranges(&rev
->diffopt
.pathspec
, range
);
786 static void move_diff_queue(struct diff_queue_struct
*dst
,
787 struct diff_queue_struct
*src
)
790 memcpy(dst
, src
, sizeof(struct diff_queue_struct
));
791 DIFF_QUEUE_CLEAR(src
);
794 static void filter_diffs_for_paths(struct line_log_data
*range
, int keep_deletions
)
797 struct diff_queue_struct outq
;
798 DIFF_QUEUE_CLEAR(&outq
);
800 for (i
= 0; i
< diff_queued_diff
.nr
; i
++) {
801 struct diff_filepair
*p
= diff_queued_diff
.queue
[i
];
802 struct line_log_data
*rg
= NULL
;
804 if (!DIFF_FILE_VALID(p
->two
)) {
808 diff_free_filepair(p
);
811 for (rg
= range
; rg
; rg
= rg
->next
) {
812 if (!strcmp(rg
->path
, p
->two
->path
))
818 diff_free_filepair(p
);
820 free(diff_queued_diff
.queue
);
821 diff_queued_diff
= outq
;
824 static inline int diff_might_be_rename(void)
827 for (i
= 0; i
< diff_queued_diff
.nr
; i
++)
828 if (!DIFF_FILE_VALID(diff_queued_diff
.queue
[i
]->one
)) {
829 /* fprintf(stderr, "diff_might_be_rename found creation of: %s\n", */
830 /* diff_queued_diff.queue[i]->two->path); */
836 static void queue_diffs(struct line_log_data
*range
,
837 struct diff_options
*opt
,
838 struct diff_queue_struct
*queue
,
839 struct commit
*commit
, struct commit
*parent
)
841 struct object_id
*tree_oid
, *parent_tree_oid
;
845 tree_oid
= get_commit_tree_oid(commit
);
846 parent_tree_oid
= parent
? get_commit_tree_oid(parent
) : NULL
;
848 if (opt
->detect_rename
&&
849 !same_paths_in_pathspec_and_range(&opt
->pathspec
, range
)) {
850 clear_pathspec(&opt
->pathspec
);
851 parse_pathspec_from_ranges(&opt
->pathspec
, range
);
853 DIFF_QUEUE_CLEAR(&diff_queued_diff
);
854 diff_tree_oid(parent_tree_oid
, tree_oid
, "", opt
);
855 if (opt
->detect_rename
&& diff_might_be_rename()) {
856 /* must look at the full tree diff to detect renames */
857 clear_pathspec(&opt
->pathspec
);
858 DIFF_QUEUE_CLEAR(&diff_queued_diff
);
860 diff_tree_oid(parent_tree_oid
, tree_oid
, "", opt
);
862 filter_diffs_for_paths(range
, 1);
864 filter_diffs_for_paths(range
, 0);
866 move_diff_queue(queue
, &diff_queued_diff
);
869 static char *get_nth_line(long line
, unsigned long *ends
, void *data
)
874 return (char *)data
+ ends
[line
] + 1;
877 static void print_line(const char *prefix
, char first
,
878 long line
, unsigned long *ends
, void *data
,
879 const char *color
, const char *reset
, FILE *file
)
881 char *begin
= get_nth_line(line
, ends
, data
);
882 char *end
= get_nth_line(line
+1, ends
, data
);
885 if (end
> begin
&& end
[-1] == '\n') {
893 fwrite(begin
, 1, end
-begin
, file
);
897 fputs("\\ No newline at end of file\n", file
);
900 static char *output_prefix(struct diff_options
*opt
)
904 if (opt
->output_prefix
) {
905 struct strbuf
*sb
= opt
->output_prefix(opt
, opt
->output_prefix_data
);
912 static void dump_diff_hacky_one(struct rev_info
*rev
, struct line_log_data
*range
)
914 unsigned int i
, j
= 0;
915 long p_lines
, t_lines
;
916 unsigned long *p_ends
= NULL
, *t_ends
= NULL
;
917 struct diff_filepair
*pair
= range
->pair
;
918 struct diff_ranges
*diff
= &range
->diff
;
920 struct diff_options
*opt
= &rev
->diffopt
;
921 char *prefix
= output_prefix(opt
);
922 const char *c_reset
= diff_get_color(opt
->use_color
, DIFF_RESET
);
923 const char *c_frag
= diff_get_color(opt
->use_color
, DIFF_FRAGINFO
);
924 const char *c_meta
= diff_get_color(opt
->use_color
, DIFF_METAINFO
);
925 const char *c_old
= diff_get_color(opt
->use_color
, DIFF_FILE_OLD
);
926 const char *c_new
= diff_get_color(opt
->use_color
, DIFF_FILE_NEW
);
927 const char *c_context
= diff_get_color(opt
->use_color
, DIFF_CONTEXT
);
932 if (pair
->one
->oid_valid
)
933 fill_line_ends(rev
->diffopt
.repo
, pair
->one
, &p_lines
, &p_ends
);
934 fill_line_ends(rev
->diffopt
.repo
, pair
->two
, &t_lines
, &t_ends
);
936 fprintf(opt
->file
, "%s%sdiff --git a/%s b/%s%s\n", prefix
, c_meta
, pair
->one
->path
, pair
->two
->path
, c_reset
);
937 fprintf(opt
->file
, "%s%s--- %s%s%s\n", prefix
, c_meta
,
938 pair
->one
->oid_valid
? "a/" : "",
939 pair
->one
->oid_valid
? pair
->one
->path
: "/dev/null",
941 fprintf(opt
->file
, "%s%s+++ b/%s%s\n", prefix
, c_meta
, pair
->two
->path
, c_reset
);
942 for (i
= 0; i
< range
->ranges
.nr
; i
++) {
944 long t_start
= range
->ranges
.ranges
[i
].start
;
945 long t_end
= range
->ranges
.ranges
[i
].end
;
946 long t_cur
= t_start
;
949 while (j
< diff
->target
.nr
&& diff
->target
.ranges
[j
].end
< t_start
)
951 if (j
== diff
->target
.nr
|| diff
->target
.ranges
[j
].start
> t_end
)
954 /* Scan ahead to determine the last diff that falls in this range */
956 while (j_last
< diff
->target
.nr
&& diff
->target
.ranges
[j_last
].start
< t_end
)
962 * Compute parent hunk headers: we know that the diff
963 * has the correct line numbers (but not all hunks).
964 * So it suffices to shift the start/end according to
965 * the line numbers of the first/last hunk(s) that
966 * fall in this range.
968 if (t_start
< diff
->target
.ranges
[j
].start
)
969 p_start
= diff
->parent
.ranges
[j
].start
- (diff
->target
.ranges
[j
].start
-t_start
);
971 p_start
= diff
->parent
.ranges
[j
].start
;
972 if (t_end
> diff
->target
.ranges
[j_last
].end
)
973 p_end
= diff
->parent
.ranges
[j_last
].end
+ (t_end
-diff
->target
.ranges
[j_last
].end
);
975 p_end
= diff
->parent
.ranges
[j_last
].end
;
977 if (!p_start
&& !p_end
) {
982 /* Now output a diff hunk for this range */
983 fprintf(opt
->file
, "%s%s@@ -%ld,%ld +%ld,%ld @@%s\n",
985 p_start
+1, p_end
-p_start
, t_start
+1, t_end
-t_start
,
987 while (j
< diff
->target
.nr
&& diff
->target
.ranges
[j
].start
< t_end
) {
989 for (; t_cur
< diff
->target
.ranges
[j
].start
; t_cur
++)
990 print_line(prefix
, ' ', t_cur
, t_ends
, pair
->two
->data
,
991 c_context
, c_reset
, opt
->file
);
992 for (k
= diff
->parent
.ranges
[j
].start
; k
< diff
->parent
.ranges
[j
].end
; k
++)
993 print_line(prefix
, '-', k
, p_ends
, pair
->one
->data
,
994 c_old
, c_reset
, opt
->file
);
995 for (; t_cur
< diff
->target
.ranges
[j
].end
&& t_cur
< t_end
; t_cur
++)
996 print_line(prefix
, '+', t_cur
, t_ends
, pair
->two
->data
,
997 c_new
, c_reset
, opt
->file
);
1000 for (; t_cur
< t_end
; t_cur
++)
1001 print_line(prefix
, ' ', t_cur
, t_ends
, pair
->two
->data
,
1002 c_context
, c_reset
, opt
->file
);
1010 * NEEDSWORK: manually building a diff here is not the Right
1011 * Thing(tm). log -L should be built into the diff pipeline.
1013 static void dump_diff_hacky(struct rev_info
*rev
, struct line_log_data
*range
)
1015 fprintf(rev
->diffopt
.file
, "%s\n", output_prefix(&rev
->diffopt
));
1017 dump_diff_hacky_one(rev
, range
);
1018 range
= range
->next
;
1023 * Unlike most other functions, this destructively operates on
1026 static int process_diff_filepair(struct rev_info
*rev
,
1027 struct diff_filepair
*pair
,
1028 struct line_log_data
*range
,
1029 struct diff_ranges
**diff_out
)
1031 struct line_log_data
*rg
= range
;
1032 struct range_set tmp
;
1033 struct diff_ranges diff
;
1034 mmfile_t file_parent
, file_target
;
1036 assert(pair
->two
->path
);
1039 if (!strcmp(rg
->path
, pair
->two
->path
))
1046 if (rg
->ranges
.nr
== 0)
1049 assert(pair
->two
->oid_valid
);
1050 diff_populate_filespec(rev
->diffopt
.repo
, pair
->two
, NULL
);
1051 file_target
.ptr
= pair
->two
->data
;
1052 file_target
.size
= pair
->two
->size
;
1054 if (pair
->one
->oid_valid
) {
1055 diff_populate_filespec(rev
->diffopt
.repo
, pair
->one
, NULL
);
1056 file_parent
.ptr
= pair
->one
->data
;
1057 file_parent
.size
= pair
->one
->size
;
1059 file_parent
.ptr
= "";
1060 file_parent
.size
= 0;
1063 diff_ranges_init(&diff
);
1064 if (collect_diff(&file_parent
, &file_target
, &diff
))
1065 die("unable to generate diff for %s", pair
->one
->path
);
1067 /* NEEDSWORK should apply some heuristics to prevent mismatches */
1069 rg
->path
= xstrdup(pair
->one
->path
);
1071 range_set_init(&tmp
, 0);
1072 range_set_map_across_diff(&tmp
, &rg
->ranges
, &diff
, diff_out
);
1073 range_set_release(&rg
->ranges
);
1074 range_set_move(&rg
->ranges
, &tmp
);
1076 diff_ranges_release(&diff
);
1078 return ((*diff_out
)->parent
.nr
> 0);
1081 static struct diff_filepair
*diff_filepair_dup(struct diff_filepair
*pair
)
1083 struct diff_filepair
*new_filepair
= xmalloc(sizeof(struct diff_filepair
));
1084 new_filepair
->one
= pair
->one
;
1085 new_filepair
->two
= pair
->two
;
1086 new_filepair
->one
->count
++;
1087 new_filepair
->two
->count
++;
1088 return new_filepair
;
1091 static void free_diffqueues(int n
, struct diff_queue_struct
*dq
)
1093 for (int i
= 0; i
< n
; i
++)
1094 diff_free_queue(&dq
[i
]);
1098 static int process_all_files(struct line_log_data
**range_out
,
1099 struct rev_info
*rev
,
1100 struct diff_queue_struct
*queue
,
1101 struct line_log_data
*range
)
1105 *range_out
= line_log_data_copy(range
);
1107 for (i
= 0; i
< queue
->nr
; i
++) {
1108 struct diff_ranges
*pairdiff
= NULL
;
1109 struct diff_filepair
*pair
= queue
->queue
[i
];
1110 if (process_diff_filepair(rev
, pair
, *range_out
, &pairdiff
)) {
1112 * Store away the diff for later output. We
1113 * tuck it in the ranges we got as _input_,
1114 * since that's the commit that caused the
1117 * NEEDSWORK not enough when we get around to
1118 * doing something interesting with merges;
1119 * currently each invocation on a merge parent
1120 * trashes the previous one's diff.
1122 * NEEDSWORK tramples over data structures not owned here
1124 struct line_log_data
*rg
= range
;
1126 while (rg
&& strcmp(rg
->path
, pair
->two
->path
))
1129 rg
->pair
= diff_filepair_dup(queue
->queue
[i
]);
1130 memcpy(&rg
->diff
, pairdiff
, sizeof(struct diff_ranges
));
1138 int line_log_print(struct rev_info
*rev
, struct commit
*commit
)
1142 if (!(rev
->diffopt
.output_format
& DIFF_FORMAT_NO_OUTPUT
)) {
1143 struct line_log_data
*range
= lookup_line_range(rev
, commit
);
1144 dump_diff_hacky(rev
, range
);
1149 static int bloom_filter_check(struct rev_info
*rev
,
1150 struct commit
*commit
,
1151 struct line_log_data
*range
)
1153 struct bloom_filter
*filter
;
1154 struct bloom_key key
;
1157 if (!commit
->parents
)
1160 if (!rev
->bloom_filter_settings
||
1161 !(filter
= get_bloom_filter(rev
->repo
, commit
)))
1167 while (!result
&& range
) {
1168 fill_bloom_key(range
->path
, strlen(range
->path
), &key
, rev
->bloom_filter_settings
);
1170 if (bloom_filter_contains(filter
, &key
, rev
->bloom_filter_settings
))
1173 clear_bloom_key(&key
);
1174 range
= range
->next
;
1180 static int process_ranges_ordinary_commit(struct rev_info
*rev
, struct commit
*commit
,
1181 struct line_log_data
*range
)
1183 struct commit
*parent
= NULL
;
1184 struct diff_queue_struct queue
;
1185 struct line_log_data
*parent_range
;
1188 if (commit
->parents
)
1189 parent
= commit
->parents
->item
;
1191 queue_diffs(range
, &rev
->diffopt
, &queue
, commit
, parent
);
1192 changed
= process_all_files(&parent_range
, rev
, &queue
, range
);
1195 add_line_range(rev
, parent
, parent_range
);
1196 free_line_log_data(parent_range
);
1197 diff_free_queue(&queue
);
1201 static int process_ranges_merge_commit(struct rev_info
*rev
, struct commit
*commit
,
1202 struct line_log_data
*range
)
1204 struct diff_queue_struct
*diffqueues
;
1205 struct line_log_data
**cand
;
1206 struct commit
**parents
;
1207 struct commit_list
*p
;
1209 int nparents
= commit_list_count(commit
->parents
);
1211 if (nparents
> 1 && rev
->first_parent_only
)
1214 ALLOC_ARRAY(diffqueues
, nparents
);
1215 ALLOC_ARRAY(cand
, nparents
);
1216 ALLOC_ARRAY(parents
, nparents
);
1218 p
= commit
->parents
;
1219 for (i
= 0; i
< nparents
; i
++) {
1220 parents
[i
] = p
->item
;
1222 queue_diffs(range
, &rev
->diffopt
, &diffqueues
[i
], commit
, parents
[i
]);
1225 for (i
= 0; i
< nparents
; i
++) {
1228 changed
= process_all_files(&cand
[i
], rev
, &diffqueues
[i
], range
);
1231 * This parent can take all the blame, so we
1232 * don't follow any other path in history
1234 add_line_range(rev
, parents
[i
], cand
[i
]);
1235 clear_commit_line_range(rev
, commit
);
1236 commit_list_append(parents
[i
], &commit
->parents
);
1239 free_diffqueues(nparents
, diffqueues
);
1240 /* NEEDSWORK leaking like a sieve */
1246 * No single parent took the blame. We add the candidates
1247 * from the above loop to the parents.
1249 for (i
= 0; i
< nparents
; i
++) {
1250 add_line_range(rev
, parents
[i
], cand
[i
]);
1253 clear_commit_line_range(rev
, commit
);
1256 free_diffqueues(nparents
, diffqueues
);
1259 /* NEEDSWORK evil merge detection stuff */
1260 /* NEEDSWORK leaking like a sieve */
1263 int line_log_process_ranges_arbitrary_commit(struct rev_info
*rev
, struct commit
*commit
)
1265 struct line_log_data
*range
= lookup_line_range(rev
, commit
);
1269 if (commit
->parents
&& !bloom_filter_check(rev
, commit
, range
)) {
1270 struct line_log_data
*prange
= line_log_data_copy(range
);
1271 add_line_range(rev
, commit
->parents
->item
, prange
);
1272 clear_commit_line_range(rev
, commit
);
1273 } else if (!commit
->parents
|| !commit
->parents
->next
)
1274 changed
= process_ranges_ordinary_commit(rev
, commit
, range
);
1276 changed
= process_ranges_merge_commit(rev
, commit
, range
);
1280 commit
->object
.flags
|= TREESAME
;
1285 static enum rewrite_result
line_log_rewrite_one(struct rev_info
*rev
, struct commit
**pp
)
1288 struct commit
*p
= *pp
;
1289 if (p
->parents
&& p
->parents
->next
)
1290 return rewrite_one_ok
;
1291 if (p
->object
.flags
& UNINTERESTING
)
1292 return rewrite_one_ok
;
1293 if (!(p
->object
.flags
& TREESAME
))
1294 return rewrite_one_ok
;
1296 return rewrite_one_noparents
;
1297 *pp
= p
->parents
->item
;
1301 int line_log_filter(struct rev_info
*rev
)
1303 struct commit
*commit
;
1304 struct commit_list
*list
= rev
->commits
;
1305 struct commit_list
*out
= NULL
, **pp
= &out
;
1308 struct commit_list
*to_free
= NULL
;
1309 commit
= list
->item
;
1310 if (line_log_process_ranges_arbitrary_commit(rev
, commit
)) {
1320 for (list
= out
; list
; list
= list
->next
)
1321 rewrite_parents(rev
, list
->item
, line_log_rewrite_one
);