git

1
#include "git-compat-util.h"
2
#include "diffcore.h"
3
#include "line-range.h"
4
#include "hex.h"
5
#include "tag.h"
6
#include "tree.h"
7
#include "diff.h"
8
#include "commit.h"
9
#include "decorate.h"
10
#include "repository.h"
11
#include "revision.h"
12
#include "xdiff-interface.h"
13
#include "strbuf.h"
14
#include "log-tree.h"
15
#include "line-log.h"
16
#include "setup.h"
17
#include "strvec.h"
18
#include "bloom.h"
19
#include "tree-walk.h"
20

21
static void range_set_grow(struct range_set *rs, size_t extra)
22
{
23
	ALLOC_GROW(rs->ranges, rs->nr + extra, rs->alloc);
24
}
25

26
/* Either initialization would be fine */
27
#define RANGE_SET_INIT {0}
28

29
void range_set_init(struct range_set *rs, size_t prealloc)
30
{
31
	rs->alloc = rs->nr = 0;
32
	rs->ranges = NULL;
33
	if (prealloc)
34
		range_set_grow(rs, prealloc);
35
}
36

37
void range_set_release(struct range_set *rs)
38
{
39
	FREE_AND_NULL(rs->ranges);
40
	rs->alloc = rs->nr = 0;
41
}
42

43
/* dst must be uninitialized! */
44
static void range_set_copy(struct range_set *dst, struct range_set *src)
45
{
46
	range_set_init(dst, src->nr);
47
	COPY_ARRAY(dst->ranges, src->ranges, src->nr);
48
	dst->nr = src->nr;
49
}
50

51
static void range_set_move(struct range_set *dst, struct range_set *src)
52
{
53
	range_set_release(dst);
54
	dst->ranges = src->ranges;
55
	dst->nr = src->nr;
56
	dst->alloc = src->alloc;
57
	src->ranges = NULL;
58
	src->alloc = src->nr = 0;
59
}
60

61
/* tack on a _new_ range _at the end_ */
62
void range_set_append_unsafe(struct range_set *rs, long a, long b)
63
{
64
	assert(a <= b);
65
	range_set_grow(rs, 1);
66
	rs->ranges[rs->nr].start = a;
67
	rs->ranges[rs->nr].end = b;
68
	rs->nr++;
69
}
70

71
void range_set_append(struct range_set *rs, long a, long b)
72
{
73
	assert(rs->nr == 0 || rs->ranges[rs->nr-1].end <= a);
74
	range_set_append_unsafe(rs, a, b);
75
}
76

77
static int range_cmp(const void *_r, const void *_s)
78
{
79
	const struct range *r = _r;
80
	const struct range *s = _s;
81

82
	/* this could be simply 'return r.start-s.start', but for the types */
83
	if (r->start == s->start)
84
		return 0;
85
	if (r->start < s->start)
86
		return -1;
87
	return 1;
88
}
89

90
/*
91
 * Check that the ranges are non-empty, sorted and non-overlapping
92
 */
93
static void range_set_check_invariants(struct range_set *rs)
94
{
95
	unsigned int i;
96

97
	if (!rs)
98
		return;
99

100
	if (rs->nr)
101
		assert(rs->ranges[0].start < rs->ranges[0].end);
102

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);
106
	}
107
}
108

109
/*
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
112
 */
113
void sort_and_merge_range_set(struct range_set *rs)
114
{
115
	unsigned int i;
116
	unsigned int o = 0; /* output cursor */
117

118
	QSORT(rs->ranges, rs->nr, range_cmp);
119

120
	for (i = 0; i < rs->nr; i++) {
121
		if (rs->ranges[i].start == rs->ranges[i].end)
122
			continue;
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;
126
		} else {
127
			rs->ranges[o].start = rs->ranges[i].start;
128
			rs->ranges[o].end = rs->ranges[i].end;
129
			o++;
130
		}
131
	}
132
	assert(o <= rs->nr);
133
	rs->nr = o;
134

135
	range_set_check_invariants(rs);
136
}
137

138
/*
139
 * Union of range sets (i.e., sets of line numbers).  Used to merge
140
 * them when searches meet at a common ancestor.
141
 *
142
 * This is also where the ranges are consolidated into canonical form:
143
 * overlapping and adjacent ranges are merged, and empty ranges are
144
 * removed.
145
 */
146
static void range_set_union(struct range_set *out,
147
			     struct range_set *a, struct range_set *b)
148
{
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 */
153

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++];
164
			else
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)
171
			; /* empty range */
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;
176
			out->nr++;
177
		} else if (out->ranges[out->nr-1].end < new_range->end) {
178
			out->ranges[out->nr-1].end = new_range->end;
179
		}
180
	}
181
}
182

183
/*
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.
187
 */
188
static void range_set_difference(struct range_set *out,
189
				  struct range_set *a, struct range_set *b)
190
{
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)
197
				/*
198
				 * a:         |-------
199
				 * b: ------|
200
				 */
201
				j++;
202
			if (j >= b->nr || end < b->ranges[j].start) {
203
				/*
204
				 * b exhausted, or
205
				 * a:  ----|
206
				 * b:         |----
207
				 */
208
				range_set_append(out, start, end);
209
				break;
210
			}
211
			if (start >= b->ranges[j].start) {
212
				/*
213
				 * a:     |--????
214
				 * b: |------|
215
				 */
216
				start = b->ranges[j].end;
217
			} else if (end > b->ranges[j].start) {
218
				/*
219
				 * a: |-----|
220
				 * b:    |--?????
221
				 */
222
				if (start < b->ranges[j].start)
223
					range_set_append(out, start, b->ranges[j].start);
224
				start = b->ranges[j].end;
225
			}
226
		}
227
	}
228
}
229

230
static void diff_ranges_init(struct diff_ranges *diff)
231
{
232
	range_set_init(&diff->parent, 0);
233
	range_set_init(&diff->target, 0);
234
}
235

236
static void diff_ranges_release(struct diff_ranges *diff)
237
{
238
	range_set_release(&diff->parent);
239
	range_set_release(&diff->target);
240
}
241

242
static void line_log_data_init(struct line_log_data *r)
243
{
244
	memset(r, 0, sizeof(struct line_log_data));
245
	range_set_init(&r->ranges, 0);
246
}
247

248
static void line_log_data_clear(struct line_log_data *r)
249
{
250
	range_set_release(&r->ranges);
251
	if (r->pair)
252
		diff_free_filepair(r->pair);
253
}
254

255
static void free_line_log_data(struct line_log_data *r)
256
{
257
	while (r) {
258
		struct line_log_data *next = r->next;
259
		line_log_data_clear(r);
260
		free(r);
261
		r = next;
262
	}
263
}
264

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)
268
{
269
	struct line_log_data *p = list;
270
	if (insertion_point)
271
		*insertion_point = NULL;
272
	while (p) {
273
		int cmp = strcmp(p->path, path);
274
		if (!cmp)
275
			return p;
276
		if (insertion_point && cmp < 0)
277
			*insertion_point = p;
278
		p = p->next;
279
	}
280
	return NULL;
281
}
282

283
/*
284
 * Note: takes ownership of 'path', which happens to be what the only
285
 * caller needs.
286
 */
287
static void line_log_data_insert(struct line_log_data **list,
288
				 char *path,
289
				 long begin, long end)
290
{
291
	struct line_log_data *ip;
292
	struct line_log_data *p = search_line_log_data(*list, path, &ip);
293

294
	if (p) {
295
		range_set_append_unsafe(&p->ranges, begin, end);
296
		free(path);
297
		return;
298
	}
299

300
	CALLOC_ARRAY(p, 1);
301
	p->path = path;
302
	range_set_append(&p->ranges, begin, end);
303
	if (ip) {
304
		p->next = ip->next;
305
		ip->next = p;
306
	} else {
307
		p->next = *list;
308
		*list = p;
309
	}
310
}
311

312
struct collect_diff_cbdata {
313
	struct diff_ranges *diff;
314
};
315

316
static int collect_diff_cb(long start_a, long count_a,
317
			   long start_b, long count_b,
318
			   void *data)
319
{
320
	struct collect_diff_cbdata *d = data;
321

322
	if (count_a >= 0)
323
		range_set_append(&d->diff->parent, start_a, start_a + count_a);
324
	if (count_b >= 0)
325
		range_set_append(&d->diff->target, start_b, start_b + count_b);
326

327
	return 0;
328
}
329

330
static int collect_diff(mmfile_t *parent, mmfile_t *target, struct diff_ranges *out)
331
{
332
	struct collect_diff_cbdata cbdata = {NULL};
333
	xpparam_t xpp;
334
	xdemitconf_t xecfg;
335
	xdemitcb_t ecb;
336

337
	memset(&xpp, 0, sizeof(xpp));
338
	memset(&xecfg, 0, sizeof(xecfg));
339
	xecfg.ctxlen = xecfg.interhunkctxlen = 0;
340

341
	cbdata.diff = out;
342
	xecfg.hunk_func = collect_diff_cb;
343
	memset(&ecb, 0, sizeof(ecb));
344
	ecb.priv = &cbdata;
345
	return xdi_diff(parent, target, &xpp, &xecfg, &ecb);
346
}
347

348
/*
349
 * These are handy for debugging.  Removing them with #if 0 silences
350
 * the "unused function" warning.
351
 */
352
#if 0
353
static void dump_range_set(struct range_set *rs, const char *desc)
354
{
355
	int i;
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);
359
}
360

361
static void dump_line_log_data(struct line_log_data *r)
362
{
363
	char buf[4096];
364
	while (r) {
365
		snprintf(buf, 4096, "file %s\n", r->path);
366
		dump_range_set(&r->ranges, buf);
367
		r = r->next;
368
	}
369
}
370

371
static void dump_diff_ranges(struct diff_ranges *diff, const char *desc)
372
{
373
	int i;
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);
383
	}
384
}
385
#endif
386

387

388
static int ranges_overlap(struct range *a, struct range *b)
389
{
390
	return !(a->end <= b->start || b->end <= a->start);
391
}
392

393
/*
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.
397
 */
398
static void diff_ranges_filter_touched(struct diff_ranges *out,
399
				       struct diff_ranges *diff,
400
				       struct range_set *rs)
401
{
402
	unsigned int i, j = 0;
403

404
	assert(out->target.nr == 0);
405

406
	for (i = 0; i < diff->target.nr; i++) {
407
		while (diff->target.ranges[i].start > rs->ranges[j].end) {
408
			j++;
409
			if (j == rs->nr)
410
				return;
411
		}
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);
419
		}
420
	}
421
}
422

423
/*
424
 * Adjust the line counts in 'rs' to account for the lines
425
 * added/removed in the diff.
426
 */
427
static void range_set_shift_diff(struct range_set *out,
428
				 struct range_set *rs,
429
				 struct diff_ranges *diff)
430
{
431
	unsigned int i, j = 0;
432
	long offset = 0;
433
	struct range *src = rs->ranges;
434
	struct range *target = diff->target.ranges;
435
	struct range *parent = diff->parent.ranges;
436

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);
441
			j++;
442
		}
443
		range_set_append(out, src[i].start+offset, src[i].end+offset);
444
	}
445
}
446

447
/*
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
452
 * its parent side.
453
 */
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)
458
{
459
	struct diff_ranges *touched = xmalloc(sizeof(*touched));
460
	struct range_set tmp1 = RANGE_SET_INIT;
461
	struct range_set tmp2 = RANGE_SET_INIT;
462

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);
470

471
	*touched_out = touched;
472
}
473

474
static struct commit *check_single_commit(struct rev_info *revs)
475
{
476
	struct object *commit = NULL;
477
	int found = -1;
478
	int i;
479

480
	for (i = 0; i < revs->pending.nr; i++) {
481
		struct object *obj = revs->pending.objects[i].item;
482
		if (obj->flags & UNINTERESTING)
483
			continue;
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);
487
		if (commit)
488
			die("More than one commit to dig from: %s and %s?",
489
			    revs->pending.objects[i].name,
490
			    revs->pending.objects[found].name);
491
		commit = obj;
492
		found = i;
493
	}
494

495
	if (!commit)
496
		die("No commit specified?");
497

498
	return (struct commit *) commit;
499
}
500

501
static void fill_blob_sha1(struct repository *r, struct commit *commit,
502
			   struct diff_filespec *spec)
503
{
504
	unsigned short mode;
505
	struct object_id oid;
506

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);
510

511
	return;
512
}
513

514
static void fill_line_ends(struct repository *r,
515
			   struct diff_filespec *spec,
516
			   long *lines,
517
			   unsigned long **line_ends)
518
{
519
	int num = 0, size = 50;
520
	long cur = 0;
521
	unsigned long *ends = NULL;
522
	char *data = NULL;
523

524
	if (diff_populate_filespec(r, spec, NULL))
525
		die("Cannot read blob %s", oid_to_hex(&spec->oid));
526

527
	ALLOC_ARRAY(ends, size);
528
	ends[cur++] = 0;
529
	data = spec->data;
530
	while (num < spec->size) {
531
		if (data[num] == '\n' || num == spec->size - 1) {
532
			ALLOC_GROW(ends, (cur + 1), size);
533
			ends[cur++] = num;
534
		}
535
		num++;
536
	}
537

538
	/* shrink the array to fit the elements */
539
	REALLOC_ARRAY(ends, cur);
540
	*lines = cur-1;
541
	*line_ends = ends;
542
}
543

544
struct nth_line_cb {
545
	struct diff_filespec *spec;
546
	long lines;
547
	unsigned long *line_ends;
548
};
549

550
static const char *nth_line(void *data, long line)
551
{
552
	struct nth_line_cb *d = data;
553
	assert(d && line <= d->lines);
554
	assert(d->spec && d->spec->data);
555

556
	if (line == 0)
557
		return (char *)d->spec->data;
558
	else
559
		return (char *)d->spec->data + d->line_ends[line] + 1;
560
}
561

562
static struct line_log_data *
563
parse_lines(struct repository *r, struct commit *commit,
564
	    const char *prefix, struct string_list *args)
565
{
566
	long lines = 0;
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;
572

573
	for_each_string_list_item(item, args) {
574
		const char *name_part, *range_part;
575
		char *full_name;
576
		struct diff_filespec *spec;
577
		long begin = 0, end = 0;
578
		long anchor;
579

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",
583
			    item->string);
584
		range_part = xstrndup(item->string, name_part - item->string);
585
		name_part++;
586

587
		full_name = prefix_path(prefix, prefix ? strlen(prefix) : 0,
588
					name_part);
589

590
		spec = alloc_filespec(full_name);
591
		fill_blob_sha1(r, commit, spec);
592
		fill_line_ends(r, spec, &lines, &ends);
593
		cb_data.spec = spec;
594
		cb_data.lines = lines;
595
		cb_data.line_ends = ends;
596

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;
600
		else
601
			anchor = 1;
602

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);
609
		if (begin < 1)
610
			begin = 1;
611
		if (end < 1 || lines < end)
612
			end = lines;
613
		begin--;
614
		line_log_data_insert(&ranges, full_name, begin, end);
615

616
		free_filespec(spec);
617
		FREE_AND_NULL(ends);
618
	}
619

620
	for (p = ranges; p; p = p->next)
621
		sort_and_merge_range_set(&p->ranges);
622

623
	return ranges;
624
}
625

626
static struct line_log_data *line_log_data_copy_one(struct line_log_data *r)
627
{
628
	struct line_log_data *ret = xmalloc(sizeof(*ret));
629

630
	assert(r);
631
	line_log_data_init(ret);
632
	range_set_copy(&ret->ranges, &r->ranges);
633

634
	ret->path = xstrdup(r->path);
635

636
	return ret;
637
}
638

639
static struct line_log_data *
640
line_log_data_copy(struct line_log_data *r)
641
{
642
	struct line_log_data *ret = NULL;
643
	struct line_log_data *tmp = NULL, *prev = NULL;
644

645
	assert(r);
646
	ret = tmp = prev = line_log_data_copy_one(r);
647
	r = r->next;
648
	while (r) {
649
		tmp = line_log_data_copy_one(r);
650
		prev->next = tmp;
651
		prev = tmp;
652
		r = r->next;
653
	}
654

655
	return ret;
656
}
657

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)
661
{
662
	struct line_log_data *head = NULL, **pp = &head;
663

664
	while (a || b) {
665
		struct line_log_data *src;
666
		struct line_log_data *src2 = NULL;
667
		struct line_log_data *d;
668
		int cmp;
669
		if (!a)
670
			cmp = 1;
671
		else if (!b)
672
			cmp = -1;
673
		else
674
			cmp = strcmp(a->path, b->path);
675
		if (cmp < 0) {
676
			src = a;
677
			a = a->next;
678
		} else if (cmp == 0) {
679
			src = a;
680
			a = a->next;
681
			src2 = b;
682
			b = b->next;
683
		} else {
684
			src = b;
685
			b = b->next;
686
		}
687
		d = xmalloc(sizeof(struct line_log_data));
688
		line_log_data_init(d);
689
		d->path = xstrdup(src->path);
690
		*pp = d;
691
		pp = &d->next;
692
		if (src2)
693
			range_set_union(&d->ranges, &src->ranges, &src2->ranges);
694
		else
695
			range_set_copy(&d->ranges, &src->ranges);
696
	}
697

698
	return head;
699
}
700

701
static void add_line_range(struct rev_info *revs, struct commit *commit,
702
			   struct line_log_data *range)
703
{
704
	struct line_log_data *old_line = NULL;
705
	struct line_log_data *new_line = NULL;
706

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);
711
	} else if (range)
712
		new_line = line_log_data_copy(range);
713

714
	if (new_line)
715
		add_decoration(&revs->line_log_data, &commit->object, new_line);
716
}
717

718
static void clear_commit_line_range(struct rev_info *revs, struct commit *commit)
719
{
720
	struct line_log_data *r;
721
	r = lookup_decoration(&revs->line_log_data, &commit->object);
722
	if (!r)
723
		return;
724
	free_line_log_data(r);
725
	add_decoration(&revs->line_log_data, &commit->object, NULL);
726
}
727

728
static struct line_log_data *lookup_line_range(struct rev_info *revs,
729
					       struct commit *commit)
730
{
731
	struct line_log_data *ret = NULL;
732
	struct line_log_data *d;
733

734
	ret = lookup_decoration(&revs->line_log_data, &commit->object);
735

736
	for (d = ret; d; d = d->next)
737
		range_set_check_invariants(&d->ranges);
738

739
	return ret;
740
}
741

742
static int same_paths_in_pathspec_and_range(struct pathspec *pathspec,
743
					    struct line_log_data *range)
744
{
745
	int i;
746
	struct line_log_data *r;
747

748
	for (i = 0, r = range; i < pathspec->nr && r; i++, r = r->next)
749
		if (strcmp(pathspec->items[i].match, r->path))
750
			return 0;
751
	if (i < pathspec->nr || r)
752
		/* different number of pathspec items and ranges */
753
		return 0;
754

755
	return 1;
756
}
757

758
static void parse_pathspec_from_ranges(struct pathspec *pathspec,
759
				       struct line_log_data *range)
760
{
761
	struct line_log_data *r;
762
	struct strvec array = STRVEC_INIT;
763
	const char **paths;
764

765
	for (r = range; r; r = r->next)
766
		strvec_push(&array, r->path);
767
	paths = strvec_detach(&array);
768

769
	parse_pathspec(pathspec, 0, PATHSPEC_PREFER_FULL, "", paths);
770
	/* strings are now owned by pathspec */
771
	free(paths);
772
}
773

774
void line_log_init(struct rev_info *rev, const char *prefix, struct string_list *args)
775
{
776
	struct commit *commit = NULL;
777
	struct line_log_data *range;
778

779
	commit = check_single_commit(rev);
780
	range = parse_lines(rev->diffopt.repo, commit, prefix, args);
781
	add_line_range(rev, commit, range);
782

783
	parse_pathspec_from_ranges(&rev->diffopt.pathspec, range);
784
}
785

786
static void move_diff_queue(struct diff_queue_struct *dst,
787
			    struct diff_queue_struct *src)
788
{
789
	assert(src != dst);
790
	memcpy(dst, src, sizeof(struct diff_queue_struct));
791
	DIFF_QUEUE_CLEAR(src);
792
}
793

794
static void filter_diffs_for_paths(struct line_log_data *range, int keep_deletions)
795
{
796
	int i;
797
	struct diff_queue_struct outq;
798
	DIFF_QUEUE_CLEAR(&outq);
799

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;
803

804
		if (!DIFF_FILE_VALID(p->two)) {
805
			if (keep_deletions)
806
				diff_q(&outq, p);
807
			else
808
				diff_free_filepair(p);
809
			continue;
810
		}
811
		for (rg = range; rg; rg = rg->next) {
812
			if (!strcmp(rg->path, p->two->path))
813
				break;
814
		}
815
		if (rg)
816
			diff_q(&outq, p);
817
		else
818
			diff_free_filepair(p);
819
	}
820
	free(diff_queued_diff.queue);
821
	diff_queued_diff = outq;
822
}
823

824
static inline int diff_might_be_rename(void)
825
{
826
	int i;
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); */
831
			return 1;
832
		}
833
	return 0;
834
}
835

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)
840
{
841
	struct object_id *tree_oid, *parent_tree_oid;
842

843
	assert(commit);
844

845
	tree_oid = get_commit_tree_oid(commit);
846
	parent_tree_oid = parent ? get_commit_tree_oid(parent) : NULL;
847

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);
852
	}
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);
859

860
		diff_tree_oid(parent_tree_oid, tree_oid, "", opt);
861

862
		filter_diffs_for_paths(range, 1);
863
		diffcore_std(opt);
864
		filter_diffs_for_paths(range, 0);
865
	}
866
	move_diff_queue(queue, &diff_queued_diff);
867
}
868

869
static char *get_nth_line(long line, unsigned long *ends, void *data)
870
{
871
	if (line == 0)
872
		return (char *)data;
873
	else
874
		return (char *)data + ends[line] + 1;
875
}
876

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)
880
{
881
	char *begin = get_nth_line(line, ends, data);
882
	char *end = get_nth_line(line+1, ends, data);
883
	int had_nl = 0;
884

885
	if (end > begin && end[-1] == '\n') {
886
		end--;
887
		had_nl = 1;
888
	}
889

890
	fputs(prefix, file);
891
	fputs(color, file);
892
	putc(first, file);
893
	fwrite(begin, 1, end-begin, file);
894
	fputs(reset, file);
895
	putc('\n', file);
896
	if (!had_nl)
897
		fputs("\\ No newline at end of file\n", file);
898
}
899

900
static char *output_prefix(struct diff_options *opt)
901
{
902
	if (opt->output_prefix) {
903
		struct strbuf *sb = opt->output_prefix(opt, opt->output_prefix_data);
904
		return sb->buf;
905
	} else {
906
		return xstrdup("");
907
	}
908
}
909

910
static void dump_diff_hacky_one(struct rev_info *rev, struct line_log_data *range)
911
{
912
	unsigned int i, j = 0;
913
	long p_lines, t_lines;
914
	unsigned long *p_ends = NULL, *t_ends = NULL;
915
	struct diff_filepair *pair = range->pair;
916
	struct diff_ranges *diff = &range->diff;
917

918
	struct diff_options *opt = &rev->diffopt;
919
	char *prefix = output_prefix(opt);
920
	const char *c_reset = diff_get_color(opt->use_color, DIFF_RESET);
921
	const char *c_frag = diff_get_color(opt->use_color, DIFF_FRAGINFO);
922
	const char *c_meta = diff_get_color(opt->use_color, DIFF_METAINFO);
923
	const char *c_old = diff_get_color(opt->use_color, DIFF_FILE_OLD);
924
	const char *c_new = diff_get_color(opt->use_color, DIFF_FILE_NEW);
925
	const char *c_context = diff_get_color(opt->use_color, DIFF_CONTEXT);
926

927
	if (!pair || !diff)
928
		goto out;
929

930
	if (pair->one->oid_valid)
931
		fill_line_ends(rev->diffopt.repo, pair->one, &p_lines, &p_ends);
932
	fill_line_ends(rev->diffopt.repo, pair->two, &t_lines, &t_ends);
933

934
	fprintf(opt->file, "%s%sdiff --git a/%s b/%s%s\n", prefix, c_meta, pair->one->path, pair->two->path, c_reset);
935
	fprintf(opt->file, "%s%s--- %s%s%s\n", prefix, c_meta,
936
	       pair->one->oid_valid ? "a/" : "",
937
	       pair->one->oid_valid ? pair->one->path : "/dev/null",
938
	       c_reset);
939
	fprintf(opt->file, "%s%s+++ b/%s%s\n", prefix, c_meta, pair->two->path, c_reset);
940
	for (i = 0; i < range->ranges.nr; i++) {
941
		long p_start, p_end;
942
		long t_start = range->ranges.ranges[i].start;
943
		long t_end = range->ranges.ranges[i].end;
944
		long t_cur = t_start;
945
		unsigned int j_last;
946

947
		while (j < diff->target.nr && diff->target.ranges[j].end < t_start)
948
			j++;
949
		if (j == diff->target.nr || diff->target.ranges[j].start > t_end)
950
			continue;
951

952
		/* Scan ahead to determine the last diff that falls in this range */
953
		j_last = j;
954
		while (j_last < diff->target.nr && diff->target.ranges[j_last].start < t_end)
955
			j_last++;
956
		if (j_last > j)
957
			j_last--;
958

959
		/*
960
		 * Compute parent hunk headers: we know that the diff
961
		 * has the correct line numbers (but not all hunks).
962
		 * So it suffices to shift the start/end according to
963
		 * the line numbers of the first/last hunk(s) that
964
		 * fall in this range.
965
		 */
966
		if (t_start < diff->target.ranges[j].start)
967
			p_start = diff->parent.ranges[j].start - (diff->target.ranges[j].start-t_start);
968
		else
969
			p_start = diff->parent.ranges[j].start;
970
		if (t_end > diff->target.ranges[j_last].end)
971
			p_end = diff->parent.ranges[j_last].end + (t_end-diff->target.ranges[j_last].end);
972
		else
973
			p_end = diff->parent.ranges[j_last].end;
974

975
		if (!p_start && !p_end) {
976
			p_start = -1;
977
			p_end = -1;
978
		}
979

980
		/* Now output a diff hunk for this range */
981
		fprintf(opt->file, "%s%s@@ -%ld,%ld +%ld,%ld @@%s\n",
982
		       prefix, c_frag,
983
		       p_start+1, p_end-p_start, t_start+1, t_end-t_start,
984
		       c_reset);
985
		while (j < diff->target.nr && diff->target.ranges[j].start < t_end) {
986
			int k;
987
			for (; t_cur < diff->target.ranges[j].start; t_cur++)
988
				print_line(prefix, ' ', t_cur, t_ends, pair->two->data,
989
					   c_context, c_reset, opt->file);
990
			for (k = diff->parent.ranges[j].start; k < diff->parent.ranges[j].end; k++)
991
				print_line(prefix, '-', k, p_ends, pair->one->data,
992
					   c_old, c_reset, opt->file);
993
			for (; t_cur < diff->target.ranges[j].end && t_cur < t_end; t_cur++)
994
				print_line(prefix, '+', t_cur, t_ends, pair->two->data,
995
					   c_new, c_reset, opt->file);
996
			j++;
997
		}
998
		for (; t_cur < t_end; t_cur++)
999
			print_line(prefix, ' ', t_cur, t_ends, pair->two->data,
1000
				   c_context, c_reset, opt->file);
1001
	}
1002

1003
out:
1004
	free(p_ends);
1005
	free(t_ends);
1006
	free(prefix);
1007
}
1008

1009
/*
1010
 * NEEDSWORK: manually building a diff here is not the Right
1011
 * Thing(tm).  log -L should be built into the diff pipeline.
1012
 */
1013
static void dump_diff_hacky(struct rev_info *rev, struct line_log_data *range)
1014
{
1015
	char *prefix = output_prefix(&rev->diffopt);
1016

1017
	fprintf(rev->diffopt.file, "%s\n", prefix);
1018
	free(prefix);
1019

1020
	while (range) {
1021
		dump_diff_hacky_one(rev, range);
1022
		range = range->next;
1023
	}
1024
}
1025

1026
/*
1027
 * Unlike most other functions, this destructively operates on
1028
 * 'range'.
1029
 */
1030
static int process_diff_filepair(struct rev_info *rev,
1031
				 struct diff_filepair *pair,
1032
				 struct line_log_data *range,
1033
				 struct diff_ranges **diff_out)
1034
{
1035
	struct line_log_data *rg = range;
1036
	struct range_set tmp;
1037
	struct diff_ranges diff;
1038
	mmfile_t file_parent, file_target;
1039
	char *parent_data_to_free = NULL;
1040

1041
	assert(pair->two->path);
1042
	while (rg) {
1043
		assert(rg->path);
1044
		if (!strcmp(rg->path, pair->two->path))
1045
			break;
1046
		rg = rg->next;
1047
	}
1048

1049
	if (!rg)
1050
		return 0;
1051
	if (rg->ranges.nr == 0)
1052
		return 0;
1053

1054
	assert(pair->two->oid_valid);
1055
	diff_populate_filespec(rev->diffopt.repo, pair->two, NULL);
1056
	file_target.ptr = pair->two->data;
1057
	file_target.size = pair->two->size;
1058

1059
	if (pair->one->oid_valid) {
1060
		diff_populate_filespec(rev->diffopt.repo, pair->one, NULL);
1061
		file_parent.ptr = pair->one->data;
1062
		file_parent.size = pair->one->size;
1063
	} else {
1064
		file_parent.ptr = parent_data_to_free = xstrdup("");
1065
		file_parent.size = 0;
1066
	}
1067

1068
	diff_ranges_init(&diff);
1069
	if (collect_diff(&file_parent, &file_target, &diff))
1070
		die("unable to generate diff for %s", pair->one->path);
1071

1072
	/* NEEDSWORK should apply some heuristics to prevent mismatches */
1073
	free(rg->path);
1074
	rg->path = xstrdup(pair->one->path);
1075

1076
	range_set_init(&tmp, 0);
1077
	range_set_map_across_diff(&tmp, &rg->ranges, &diff, diff_out);
1078
	range_set_release(&rg->ranges);
1079
	range_set_move(&rg->ranges, &tmp);
1080

1081
	diff_ranges_release(&diff);
1082

1083
	free(parent_data_to_free);
1084
	return ((*diff_out)->parent.nr > 0);
1085
}
1086

1087
static struct diff_filepair *diff_filepair_dup(struct diff_filepair *pair)
1088
{
1089
	struct diff_filepair *new_filepair = xmalloc(sizeof(struct diff_filepair));
1090
	new_filepair->one = pair->one;
1091
	new_filepair->two = pair->two;
1092
	new_filepair->one->count++;
1093
	new_filepair->two->count++;
1094
	return new_filepair;
1095
}
1096

1097
static void free_diffqueues(int n, struct diff_queue_struct *dq)
1098
{
1099
	for (int i = 0; i < n; i++)
1100
		diff_free_queue(&dq[i]);
1101
	free(dq);
1102
}
1103

1104
static int process_all_files(struct line_log_data **range_out,
1105
			     struct rev_info *rev,
1106
			     struct diff_queue_struct *queue,
1107
			     struct line_log_data *range)
1108
{
1109
	int i, changed = 0;
1110

1111
	*range_out = line_log_data_copy(range);
1112

1113
	for (i = 0; i < queue->nr; i++) {
1114
		struct diff_ranges *pairdiff = NULL;
1115
		struct diff_filepair *pair = queue->queue[i];
1116
		if (process_diff_filepair(rev, pair, *range_out, &pairdiff)) {
1117
			/*
1118
			 * Store away the diff for later output.  We
1119
			 * tuck it in the ranges we got as _input_,
1120
			 * since that's the commit that caused the
1121
			 * diff.
1122
			 *
1123
			 * NEEDSWORK not enough when we get around to
1124
			 * doing something interesting with merges;
1125
			 * currently each invocation on a merge parent
1126
			 * trashes the previous one's diff.
1127
			 *
1128
			 * NEEDSWORK tramples over data structures not owned here
1129
			 */
1130
			struct line_log_data *rg = range;
1131
			changed++;
1132
			while (rg && strcmp(rg->path, pair->two->path))
1133
				rg = rg->next;
1134
			assert(rg);
1135
			rg->pair = diff_filepair_dup(queue->queue[i]);
1136
			memcpy(&rg->diff, pairdiff, sizeof(struct diff_ranges));
1137
		}
1138
		free(pairdiff);
1139
	}
1140

1141
	return changed;
1142
}
1143

1144
int line_log_print(struct rev_info *rev, struct commit *commit)
1145
{
1146

1147
	show_log(rev);
1148
	if (!(rev->diffopt.output_format & DIFF_FORMAT_NO_OUTPUT)) {
1149
		struct line_log_data *range = lookup_line_range(rev, commit);
1150
		dump_diff_hacky(rev, range);
1151
	}
1152
	return 1;
1153
}
1154

1155
static int bloom_filter_check(struct rev_info *rev,
1156
			      struct commit *commit,
1157
			      struct line_log_data *range)
1158
{
1159
	struct bloom_filter *filter;
1160
	struct bloom_key key;
1161
	int result = 0;
1162

1163
	if (!commit->parents)
1164
		return 1;
1165

1166
	if (!rev->bloom_filter_settings ||
1167
	    !(filter = get_bloom_filter(rev->repo, commit)))
1168
		return 1;
1169

1170
	if (!range)
1171
		return 0;
1172

1173
	while (!result && range) {
1174
		fill_bloom_key(range->path, strlen(range->path), &key, rev->bloom_filter_settings);
1175

1176
		if (bloom_filter_contains(filter, &key, rev->bloom_filter_settings))
1177
			result = 1;
1178

1179
		clear_bloom_key(&key);
1180
		range = range->next;
1181
	}
1182

1183
	return result;
1184
}
1185

1186
static int process_ranges_ordinary_commit(struct rev_info *rev, struct commit *commit,
1187
					  struct line_log_data *range)
1188
{
1189
	struct commit *parent = NULL;
1190
	struct diff_queue_struct queue;
1191
	struct line_log_data *parent_range;
1192
	int changed;
1193

1194
	if (commit->parents)
1195
		parent = commit->parents->item;
1196

1197
	queue_diffs(range, &rev->diffopt, &queue, commit, parent);
1198
	changed = process_all_files(&parent_range, rev, &queue, range);
1199

1200
	if (parent)
1201
		add_line_range(rev, parent, parent_range);
1202
	free_line_log_data(parent_range);
1203
	diff_free_queue(&queue);
1204
	return changed;
1205
}
1206

1207
static int process_ranges_merge_commit(struct rev_info *rev, struct commit *commit,
1208
				       struct line_log_data *range)
1209
{
1210
	struct diff_queue_struct *diffqueues;
1211
	struct line_log_data **cand;
1212
	struct commit **parents;
1213
	struct commit_list *p;
1214
	int i;
1215
	int nparents = commit_list_count(commit->parents);
1216

1217
	if (nparents > 1 && rev->first_parent_only)
1218
		nparents = 1;
1219

1220
	ALLOC_ARRAY(diffqueues, nparents);
1221
	ALLOC_ARRAY(cand, nparents);
1222
	ALLOC_ARRAY(parents, nparents);
1223

1224
	p = commit->parents;
1225
	for (i = 0; i < nparents; i++) {
1226
		parents[i] = p->item;
1227
		p = p->next;
1228
		queue_diffs(range, &rev->diffopt, &diffqueues[i], commit, parents[i]);
1229
	}
1230

1231
	for (i = 0; i < nparents; i++) {
1232
		int changed;
1233
		cand[i] = NULL;
1234
		changed = process_all_files(&cand[i], rev, &diffqueues[i], range);
1235
		if (!changed) {
1236
			/*
1237
			 * This parent can take all the blame, so we
1238
			 * don't follow any other path in history
1239
			 */
1240
			add_line_range(rev, parents[i], cand[i]);
1241
			clear_commit_line_range(rev, commit);
1242
			commit_list_append(parents[i], &commit->parents);
1243
			free(parents);
1244
			free(cand);
1245
			free_diffqueues(nparents, diffqueues);
1246
			/* NEEDSWORK leaking like a sieve */
1247
			return 0;
1248
		}
1249
	}
1250

1251
	/*
1252
	 * No single parent took the blame.  We add the candidates
1253
	 * from the above loop to the parents.
1254
	 */
1255
	for (i = 0; i < nparents; i++) {
1256
		add_line_range(rev, parents[i], cand[i]);
1257
	}
1258

1259
	clear_commit_line_range(rev, commit);
1260
	free(parents);
1261
	free(cand);
1262
	free_diffqueues(nparents, diffqueues);
1263
	return 1;
1264

1265
	/* NEEDSWORK evil merge detection stuff */
1266
	/* NEEDSWORK leaking like a sieve */
1267
}
1268

1269
int line_log_process_ranges_arbitrary_commit(struct rev_info *rev, struct commit *commit)
1270
{
1271
	struct line_log_data *range = lookup_line_range(rev, commit);
1272
	int changed = 0;
1273

1274
	if (range) {
1275
		if (commit->parents && !bloom_filter_check(rev, commit, range)) {
1276
			struct line_log_data *prange = line_log_data_copy(range);
1277
			add_line_range(rev, commit->parents->item, prange);
1278
			clear_commit_line_range(rev, commit);
1279
		} else if (!commit->parents || !commit->parents->next)
1280
			changed = process_ranges_ordinary_commit(rev, commit, range);
1281
		else
1282
			changed = process_ranges_merge_commit(rev, commit, range);
1283
	}
1284

1285
	if (!changed)
1286
		commit->object.flags |= TREESAME;
1287

1288
	return changed;
1289
}
1290

1291
static enum rewrite_result line_log_rewrite_one(struct rev_info *rev UNUSED,
1292
						struct commit **pp)
1293
{
1294
	for (;;) {
1295
		struct commit *p = *pp;
1296
		if (p->parents && p->parents->next)
1297
			return rewrite_one_ok;
1298
		if (p->object.flags & UNINTERESTING)
1299
			return rewrite_one_ok;
1300
		if (!(p->object.flags & TREESAME))
1301
			return rewrite_one_ok;
1302
		if (!p->parents)
1303
			return rewrite_one_noparents;
1304
		*pp = p->parents->item;
1305
	}
1306
}
1307

1308
int line_log_filter(struct rev_info *rev)
1309
{
1310
	struct commit *commit;
1311
	struct commit_list *list = rev->commits;
1312
	struct commit_list *out = NULL, **pp = &out;
1313

1314
	while (list) {
1315
		struct commit_list *to_free = NULL;
1316
		commit = list->item;
1317
		if (line_log_process_ranges_arbitrary_commit(rev, commit)) {
1318
			*pp = list;
1319
			pp = &list->next;
1320
		} else
1321
			to_free = list;
1322
		list = list->next;
1323
		free(to_free);
1324
	}
1325
	*pp = NULL;
1326

1327
	for (list = out; list; list = list->next)
1328
		rewrite_parents(rev, list->item, line_log_rewrite_one);
1329

1330
	rev->commits = out;
1331

1332
	return 0;
1333
}
1334

1335
static void free_void_line_log_data(void *data)
1336
{
1337
	free_line_log_data(data);
1338
}
1339

1340
void line_log_free(struct rev_info *rev)
1341
{
1342
	clear_decoration(&rev->line_log_data, free_void_line_log_data);
1343
}
1344