git

1
#define USE_THE_REPOSITORY_VARIABLE
2

3
#include "git-compat-util.h"
4
#include "refs.h"
5
#include "object-store-ll.h"
6
#include "cache-tree.h"
7
#include "mergesort.h"
8
#include "commit.h"
9
#include "convert.h"
10
#include "diff.h"
11
#include "diffcore.h"
12
#include "gettext.h"
13
#include "hex.h"
14
#include "path.h"
15
#include "read-cache.h"
16
#include "revision.h"
17
#include "setup.h"
18
#include "tag.h"
19
#include "trace2.h"
20
#include "blame.h"
21
#include "alloc.h"
22
#include "commit-slab.h"
23
#include "bloom.h"
24
#include "commit-graph.h"
25

26
define_commit_slab(blame_suspects, struct blame_origin *);
27
static struct blame_suspects blame_suspects;
28

29
struct blame_origin *get_blame_suspects(struct commit *commit)
30
{
31
	struct blame_origin **result;
32

33
	result = blame_suspects_peek(&blame_suspects, commit);
34

35
	return result ? *result : NULL;
36
}
37

38
static void set_blame_suspects(struct commit *commit, struct blame_origin *origin)
39
{
40
	*blame_suspects_at(&blame_suspects, commit) = origin;
41
}
42

43
void blame_origin_decref(struct blame_origin *o)
44
{
45
	if (o && --o->refcnt <= 0) {
46
		struct blame_origin *p, *l = NULL;
47
		if (o->previous)
48
			blame_origin_decref(o->previous);
49
		free(o->file.ptr);
50
		/* Should be present exactly once in commit chain */
51
		for (p = get_blame_suspects(o->commit); p; l = p, p = p->next) {
52
			if (p == o) {
53
				if (l)
54
					l->next = p->next;
55
				else
56
					set_blame_suspects(o->commit, p->next);
57
				free(o);
58
				return;
59
			}
60
		}
61
		die("internal error in blame_origin_decref");
62
	}
63
}
64

65
/*
66
 * Given a commit and a path in it, create a new origin structure.
67
 * The callers that add blame to the scoreboard should use
68
 * get_origin() to obtain shared, refcounted copy instead of calling
69
 * this function directly.
70
 */
71
static struct blame_origin *make_origin(struct commit *commit, const char *path)
72
{
73
	struct blame_origin *o;
74
	FLEX_ALLOC_STR(o, path, path);
75
	o->commit = commit;
76
	o->refcnt = 1;
77
	o->next = get_blame_suspects(commit);
78
	set_blame_suspects(commit, o);
79
	return o;
80
}
81

82
/*
83
 * Locate an existing origin or create a new one.
84
 * This moves the origin to front position in the commit util list.
85
 */
86
static struct blame_origin *get_origin(struct commit *commit, const char *path)
87
{
88
	struct blame_origin *o, *l;
89

90
	for (o = get_blame_suspects(commit), l = NULL; o; l = o, o = o->next) {
91
		if (!strcmp(o->path, path)) {
92
			/* bump to front */
93
			if (l) {
94
				l->next = o->next;
95
				o->next = get_blame_suspects(commit);
96
				set_blame_suspects(commit, o);
97
			}
98
			return blame_origin_incref(o);
99
		}
100
	}
101
	return make_origin(commit, path);
102
}
103

104

105

106
static void verify_working_tree_path(struct repository *r,
107
				     struct commit *work_tree, const char *path)
108
{
109
	struct commit_list *parents;
110
	int pos;
111

112
	for (parents = work_tree->parents; parents; parents = parents->next) {
113
		const struct object_id *commit_oid = &parents->item->object.oid;
114
		struct object_id blob_oid;
115
		unsigned short mode;
116

117
		if (!get_tree_entry(r, commit_oid, path, &blob_oid, &mode) &&
118
		    oid_object_info(r, &blob_oid, NULL) == OBJ_BLOB)
119
			return;
120
	}
121

122
	pos = index_name_pos(r->index, path, strlen(path));
123
	if (pos >= 0)
124
		; /* path is in the index */
125
	else if (-1 - pos < r->index->cache_nr &&
126
		 !strcmp(r->index->cache[-1 - pos]->name, path))
127
		; /* path is in the index, unmerged */
128
	else
129
		die("no such path '%s' in HEAD", path);
130
}
131

132
static struct commit_list **append_parent(struct repository *r,
133
					  struct commit_list **tail,
134
					  const struct object_id *oid)
135
{
136
	struct commit *parent;
137

138
	parent = lookup_commit_reference(r, oid);
139
	if (!parent)
140
		die("no such commit %s", oid_to_hex(oid));
141
	return &commit_list_insert(parent, tail)->next;
142
}
143

144
static void append_merge_parents(struct repository *r,
145
				 struct commit_list **tail)
146
{
147
	int merge_head;
148
	struct strbuf line = STRBUF_INIT;
149

150
	merge_head = open(git_path_merge_head(r), O_RDONLY);
151
	if (merge_head < 0) {
152
		if (errno == ENOENT)
153
			return;
154
		die("cannot open '%s' for reading",
155
		    git_path_merge_head(r));
156
	}
157

158
	while (!strbuf_getwholeline_fd(&line, merge_head, '\n')) {
159
		struct object_id oid;
160
		if (get_oid_hex(line.buf, &oid))
161
			die("unknown line in '%s': %s",
162
			    git_path_merge_head(r), line.buf);
163
		tail = append_parent(r, tail, &oid);
164
	}
165
	close(merge_head);
166
	strbuf_release(&line);
167
}
168

169
/*
170
 * This isn't as simple as passing sb->buf and sb->len, because we
171
 * want to transfer ownership of the buffer to the commit (so we
172
 * must use detach).
173
 */
174
static void set_commit_buffer_from_strbuf(struct repository *r,
175
					  struct commit *c,
176
					  struct strbuf *sb)
177
{
178
	size_t len;
179
	void *buf = strbuf_detach(sb, &len);
180
	set_commit_buffer(r, c, buf, len);
181
}
182

183
/*
184
 * Prepare a dummy commit that represents the work tree (or staged) item.
185
 * Note that annotating work tree item never works in the reverse.
186
 */
187
static struct commit *fake_working_tree_commit(struct repository *r,
188
					       struct diff_options *opt,
189
					       const char *path,
190
					       const char *contents_from,
191
					       struct object_id *oid)
192
{
193
	struct commit *commit;
194
	struct blame_origin *origin;
195
	struct commit_list **parent_tail, *parent;
196
	struct strbuf buf = STRBUF_INIT;
197
	const char *ident;
198
	time_t now;
199
	int len;
200
	struct cache_entry *ce;
201
	unsigned mode;
202
	struct strbuf msg = STRBUF_INIT;
203

204
	repo_read_index(r);
205
	time(&now);
206
	commit = alloc_commit_node(r);
207
	commit->object.parsed = 1;
208
	commit->date = now;
209
	parent_tail = &commit->parents;
210

211
	parent_tail = append_parent(r, parent_tail, oid);
212
	append_merge_parents(r, parent_tail);
213
	verify_working_tree_path(r, commit, path);
214

215
	origin = make_origin(commit, path);
216

217
	if (contents_from)
218
		ident = fmt_ident("External file (--contents)", "external.file",
219
				  WANT_BLANK_IDENT, NULL, 0);
220
	else
221
		ident = fmt_ident("Not Committed Yet", "not.committed.yet",
222
				  WANT_BLANK_IDENT, NULL, 0);
223
	strbuf_addstr(&msg, "tree 0000000000000000000000000000000000000000\n");
224
	for (parent = commit->parents; parent; parent = parent->next)
225
		strbuf_addf(&msg, "parent %s\n",
226
			    oid_to_hex(&parent->item->object.oid));
227
	strbuf_addf(&msg,
228
		    "author %s\n"
229
		    "committer %s\n\n"
230
		    "Version of %s from %s\n",
231
		    ident, ident, path,
232
		    (!contents_from ? path :
233
		     (!strcmp(contents_from, "-") ? "standard input" : contents_from)));
234
	set_commit_buffer_from_strbuf(r, commit, &msg);
235

236
	if (!contents_from || strcmp("-", contents_from)) {
237
		struct stat st;
238
		const char *read_from;
239
		char *buf_ptr;
240
		unsigned long buf_len;
241

242
		if (contents_from) {
243
			if (stat(contents_from, &st) < 0)
244
				die_errno("Cannot stat '%s'", contents_from);
245
			read_from = contents_from;
246
		}
247
		else {
248
			if (lstat(path, &st) < 0)
249
				die_errno("Cannot lstat '%s'", path);
250
			read_from = path;
251
		}
252
		mode = canon_mode(st.st_mode);
253

254
		switch (st.st_mode & S_IFMT) {
255
		case S_IFREG:
256
			if (opt->flags.allow_textconv &&
257
			    textconv_object(r, read_from, mode, null_oid(), 0, &buf_ptr, &buf_len))
258
				strbuf_attach(&buf, buf_ptr, buf_len, buf_len + 1);
259
			else if (strbuf_read_file(&buf, read_from, st.st_size) != st.st_size)
260
				die_errno("cannot open or read '%s'", read_from);
261
			break;
262
		case S_IFLNK:
263
			if (strbuf_readlink(&buf, read_from, st.st_size) < 0)
264
				die_errno("cannot readlink '%s'", read_from);
265
			break;
266
		default:
267
			die("unsupported file type %s", read_from);
268
		}
269
	}
270
	else {
271
		/* Reading from stdin */
272
		mode = 0;
273
		if (strbuf_read(&buf, 0, 0) < 0)
274
			die_errno("failed to read from stdin");
275
	}
276
	convert_to_git(r->index, path, buf.buf, buf.len, &buf, 0);
277
	origin->file.ptr = buf.buf;
278
	origin->file.size = buf.len;
279
	pretend_object_file(buf.buf, buf.len, OBJ_BLOB, &origin->blob_oid);
280

281
	/*
282
	 * Read the current index, replace the path entry with
283
	 * origin->blob_sha1 without mucking with its mode or type
284
	 * bits; we are not going to write this index out -- we just
285
	 * want to run "diff-index --cached".
286
	 */
287
	discard_index(r->index);
288
	repo_read_index(r);
289

290
	len = strlen(path);
291
	if (!mode) {
292
		int pos = index_name_pos(r->index, path, len);
293
		if (0 <= pos)
294
			mode = r->index->cache[pos]->ce_mode;
295
		else
296
			/* Let's not bother reading from HEAD tree */
297
			mode = S_IFREG | 0644;
298
	}
299
	ce = make_empty_cache_entry(r->index, len);
300
	oidcpy(&ce->oid, &origin->blob_oid);
301
	memcpy(ce->name, path, len);
302
	ce->ce_flags = create_ce_flags(0);
303
	ce->ce_namelen = len;
304
	ce->ce_mode = create_ce_mode(mode);
305
	add_index_entry(r->index, ce,
306
			ADD_CACHE_OK_TO_ADD | ADD_CACHE_OK_TO_REPLACE);
307

308
	cache_tree_invalidate_path(r->index, path);
309

310
	return commit;
311
}
312

313

314

315
static int diff_hunks(mmfile_t *file_a, mmfile_t *file_b,
316
		      xdl_emit_hunk_consume_func_t hunk_func, void *cb_data, int xdl_opts)
317
{
318
	xpparam_t xpp = {0};
319
	xdemitconf_t xecfg = {0};
320
	xdemitcb_t ecb = {NULL};
321

322
	xpp.flags = xdl_opts;
323
	xecfg.hunk_func = hunk_func;
324
	ecb.priv = cb_data;
325
	return xdi_diff(file_a, file_b, &xpp, &xecfg, &ecb);
326
}
327

328
static const char *get_next_line(const char *start, const char *end)
329
{
330
	const char *nl = memchr(start, '\n', end - start);
331

332
	return nl ? nl + 1 : end;
333
}
334

335
static int find_line_starts(int **line_starts, const char *buf,
336
			    unsigned long len)
337
{
338
	const char *end = buf + len;
339
	const char *p;
340
	int *lineno;
341
	int num = 0;
342

343
	for (p = buf; p < end; p = get_next_line(p, end))
344
		num++;
345

346
	ALLOC_ARRAY(*line_starts, num + 1);
347
	lineno = *line_starts;
348

349
	for (p = buf; p < end; p = get_next_line(p, end))
350
		*lineno++ = p - buf;
351

352
	*lineno = len;
353

354
	return num;
355
}
356

357
struct fingerprint_entry;
358

359
/* A fingerprint is intended to loosely represent a string, such that two
360
 * fingerprints can be quickly compared to give an indication of the similarity
361
 * of the strings that they represent.
362
 *
363
 * A fingerprint is represented as a multiset of the lower-cased byte pairs in
364
 * the string that it represents. Whitespace is added at each end of the
365
 * string. Whitespace pairs are ignored. Whitespace is converted to '\0'.
366
 * For example, the string "Darth   Radar" will be converted to the following
367
 * fingerprint:
368
 * {"\0d", "da", "da", "ar", "ar", "rt", "th", "h\0", "\0r", "ra", "ad", "r\0"}
369
 *
370
 * The similarity between two fingerprints is the size of the intersection of
371
 * their multisets, including repeated elements. See fingerprint_similarity for
372
 * examples.
373
 *
374
 * For ease of implementation, the fingerprint is implemented as a map
375
 * of byte pairs to the count of that byte pair in the string, instead of
376
 * allowing repeated elements in a set.
377
 */
378
struct fingerprint {
379
	struct hashmap map;
380
	/* As we know the maximum number of entries in advance, it's
381
	 * convenient to store the entries in a single array instead of having
382
	 * the hashmap manage the memory.
383
	 */
384
	struct fingerprint_entry *entries;
385
};
386

387
/* A byte pair in a fingerprint. Stores the number of times the byte pair
388
 * occurs in the string that the fingerprint represents.
389
 */
390
struct fingerprint_entry {
391
	/* The hashmap entry - the hash represents the byte pair in its
392
	 * entirety so we don't need to store the byte pair separately.
393
	 */
394
	struct hashmap_entry entry;
395
	/* The number of times the byte pair occurs in the string that the
396
	 * fingerprint represents.
397
	 */
398
	int count;
399
};
400

401
/* See `struct fingerprint` for an explanation of what a fingerprint is.
402
 * \param result the fingerprint of the string is stored here. This must be
403
 * 		 freed later using free_fingerprint.
404
 * \param line_begin the start of the string
405
 * \param line_end the end of the string
406
 */
407
static void get_fingerprint(struct fingerprint *result,
408
			    const char *line_begin,
409
			    const char *line_end)
410
{
411
	unsigned int hash, c0 = 0, c1;
412
	const char *p;
413
	int max_map_entry_count = 1 + line_end - line_begin;
414
	struct fingerprint_entry *entry = xcalloc(max_map_entry_count,
415
		sizeof(struct fingerprint_entry));
416
	struct fingerprint_entry *found_entry;
417

418
	hashmap_init(&result->map, NULL, NULL, max_map_entry_count);
419
	result->entries = entry;
420
	for (p = line_begin; p <= line_end; ++p, c0 = c1) {
421
		/* Always terminate the string with whitespace.
422
		 * Normalise whitespace to 0, and normalise letters to
423
		 * lower case. This won't work for multibyte characters but at
424
		 * worst will match some unrelated characters.
425
		 */
426
		if ((p == line_end) || isspace(*p))
427
			c1 = 0;
428
		else
429
			c1 = tolower(*p);
430
		hash = c0 | (c1 << 8);
431
		/* Ignore whitespace pairs */
432
		if (hash == 0)
433
			continue;
434
		hashmap_entry_init(&entry->entry, hash);
435

436
		found_entry = hashmap_get_entry(&result->map, entry,
437
						/* member name */ entry, NULL);
438
		if (found_entry) {
439
			found_entry->count += 1;
440
		} else {
441
			entry->count = 1;
442
			hashmap_add(&result->map, &entry->entry);
443
			++entry;
444
		}
445
	}
446
}
447

448
static void free_fingerprint(struct fingerprint *f)
449
{
450
	hashmap_clear(&f->map);
451
	free(f->entries);
452
}
453

454
/* Calculates the similarity between two fingerprints as the size of the
455
 * intersection of their multisets, including repeated elements. See
456
 * `struct fingerprint` for an explanation of the fingerprint representation.
457
 * The similarity between "cat mat" and "father rather" is 2 because "at" is
458
 * present twice in both strings while the similarity between "tim" and "mit"
459
 * is 0.
460
 */
461
static int fingerprint_similarity(struct fingerprint *a, struct fingerprint *b)
462
{
463
	int intersection = 0;
464
	struct hashmap_iter iter;
465
	const struct fingerprint_entry *entry_a, *entry_b;
466

467
	hashmap_for_each_entry(&b->map, &iter, entry_b,
468
				entry /* member name */) {
469
		entry_a = hashmap_get_entry(&a->map, entry_b, entry, NULL);
470
		if (entry_a) {
471
			intersection += entry_a->count < entry_b->count ?
472
					entry_a->count : entry_b->count;
473
		}
474
	}
475
	return intersection;
476
}
477

478
/* Subtracts byte-pair elements in B from A, modifying A in place.
479
 */
480
static void fingerprint_subtract(struct fingerprint *a, struct fingerprint *b)
481
{
482
	struct hashmap_iter iter;
483
	struct fingerprint_entry *entry_a;
484
	const struct fingerprint_entry *entry_b;
485

486
	hashmap_iter_init(&b->map, &iter);
487

488
	hashmap_for_each_entry(&b->map, &iter, entry_b,
489
				entry /* member name */) {
490
		entry_a = hashmap_get_entry(&a->map, entry_b, entry, NULL);
491
		if (entry_a) {
492
			if (entry_a->count <= entry_b->count)
493
				hashmap_remove(&a->map, &entry_b->entry, NULL);
494
			else
495
				entry_a->count -= entry_b->count;
496
		}
497
	}
498
}
499

500
/* Calculate fingerprints for a series of lines.
501
 * Puts the fingerprints in the fingerprints array, which must have been
502
 * preallocated to allow storing line_count elements.
503
 */
504
static void get_line_fingerprints(struct fingerprint *fingerprints,
505
				  const char *content, const int *line_starts,
506
				  long first_line, long line_count)
507
{
508
	int i;
509
	const char *linestart, *lineend;
510

511
	line_starts += first_line;
512
	for (i = 0; i < line_count; ++i) {
513
		linestart = content + line_starts[i];
514
		lineend = content + line_starts[i + 1];
515
		get_fingerprint(fingerprints + i, linestart, lineend);
516
	}
517
}
518

519
static void free_line_fingerprints(struct fingerprint *fingerprints,
520
				   int nr_fingerprints)
521
{
522
	int i;
523

524
	for (i = 0; i < nr_fingerprints; i++)
525
		free_fingerprint(&fingerprints[i]);
526
}
527

528
/* This contains the data necessary to linearly map a line number in one half
529
 * of a diff chunk to the line in the other half of the diff chunk that is
530
 * closest in terms of its position as a fraction of the length of the chunk.
531
 */
532
struct line_number_mapping {
533
	int destination_start, destination_length,
534
		source_start, source_length;
535
};
536

537
/* Given a line number in one range, offset and scale it to map it onto the
538
 * other range.
539
 * Essentially this mapping is a simple linear equation but the calculation is
540
 * more complicated to allow performing it with integer operations.
541
 * Another complication is that if a line could map onto many lines in the
542
 * destination range then we want to choose the line at the center of those
543
 * possibilities.
544
 * Example: if the chunk is 2 lines long in A and 10 lines long in B then the
545
 * first 5 lines in B will map onto the first line in the A chunk, while the
546
 * last 5 lines will all map onto the second line in the A chunk.
547
 * Example: if the chunk is 10 lines long in A and 2 lines long in B then line
548
 * 0 in B will map onto line 2 in A, and line 1 in B will map onto line 7 in A.
549
 */
550
static int map_line_number(int line_number,
551
	const struct line_number_mapping *mapping)
552
{
553
	return ((line_number - mapping->source_start) * 2 + 1) *
554
	       mapping->destination_length /
555
	       (mapping->source_length * 2) +
556
	       mapping->destination_start;
557
}
558

559
/* Get a pointer to the element storing the similarity between a line in A
560
 * and a line in B.
561
 *
562
 * The similarities are stored in a 2-dimensional array. Each "row" in the
563
 * array contains the similarities for a line in B. The similarities stored in
564
 * a row are the similarities between the line in B and the nearby lines in A.
565
 * To keep the length of each row the same, it is padded out with values of -1
566
 * where the search range extends beyond the lines in A.
567
 * For example, if max_search_distance_a is 2 and the two sides of a diff chunk
568
 * look like this:
569
 * a | m
570
 * b | n
571
 * c | o
572
 * d | p
573
 * e | q
574
 * Then the similarity array will contain:
575
 * [-1, -1, am, bm, cm,
576
 *  -1, an, bn, cn, dn,
577
 *  ao, bo, co, do, eo,
578
 *  bp, cp, dp, ep, -1,
579
 *  cq, dq, eq, -1, -1]
580
 * Where similarities are denoted either by -1 for invalid, or the
581
 * concatenation of the two lines in the diff being compared.
582
 *
583
 * \param similarities array of similarities between lines in A and B
584
 * \param line_a the index of the line in A, in the same frame of reference as
585
 *	closest_line_a.
586
 * \param local_line_b the index of the line in B, relative to the first line
587
 *		       in B that similarities represents.
588
 * \param closest_line_a the index of the line in A that is deemed to be
589
 *			 closest to local_line_b. This must be in the same
590
 *			 frame of reference as line_a. This value defines
591
 *			 where similarities is centered for the line in B.
592
 * \param max_search_distance_a maximum distance in lines from the closest line
593
 * 				in A for other lines in A for which
594
 * 				similarities may be calculated.
595
 */
596
static int *get_similarity(int *similarities,
597
			   int line_a, int local_line_b,
598
			   int closest_line_a, int max_search_distance_a)
599
{
600
	assert(abs(line_a - closest_line_a) <=
601
	       max_search_distance_a);
602
	return similarities + line_a - closest_line_a +
603
	       max_search_distance_a +
604
	       local_line_b * (max_search_distance_a * 2 + 1);
605
}
606

607
#define CERTAIN_NOTHING_MATCHES -2
608
#define CERTAINTY_NOT_CALCULATED -1
609

610
/* Given a line in B, first calculate its similarities with nearby lines in A
611
 * if not already calculated, then identify the most similar and second most
612
 * similar lines. The "certainty" is calculated based on those two
613
 * similarities.
614
 *
615
 * \param start_a the index of the first line of the chunk in A
616
 * \param length_a the length in lines of the chunk in A
617
 * \param local_line_b the index of the line in B, relative to the first line
618
 * 		       in the chunk.
619
 * \param fingerprints_a array of fingerprints for the chunk in A
620
 * \param fingerprints_b array of fingerprints for the chunk in B
621
 * \param similarities 2-dimensional array of similarities between lines in A
622
 * 		       and B. See get_similarity() for more details.
623
 * \param certainties array of values indicating how strongly a line in B is
624
 * 		      matched with some line in A.
625
 * \param second_best_result array of absolute indices in A for the second
626
 * 			     closest match of a line in B.
627
 * \param result array of absolute indices in A for the closest match of a line
628
 * 		 in B.
629
 * \param max_search_distance_a maximum distance in lines from the closest line
630
 * 				in A for other lines in A for which
631
 * 				similarities may be calculated.
632
 * \param map_line_number_in_b_to_a parameter to map_line_number().
633
 */
634
static void find_best_line_matches(
635
	int start_a,
636
	int length_a,
637
	int start_b,
638
	int local_line_b,
639
	struct fingerprint *fingerprints_a,
640
	struct fingerprint *fingerprints_b,
641
	int *similarities,
642
	int *certainties,
643
	int *second_best_result,
644
	int *result,
645
	const int max_search_distance_a,
646
	const struct line_number_mapping *map_line_number_in_b_to_a)
647
{
648

649
	int i, search_start, search_end, closest_local_line_a, *similarity,
650
		best_similarity = 0, second_best_similarity = 0,
651
		best_similarity_index = 0, second_best_similarity_index = 0;
652

653
	/* certainty has already been calculated so no need to redo the work */
654
	if (certainties[local_line_b] != CERTAINTY_NOT_CALCULATED)
655
		return;
656

657
	closest_local_line_a = map_line_number(
658
		local_line_b + start_b, map_line_number_in_b_to_a) - start_a;
659

660
	search_start = closest_local_line_a - max_search_distance_a;
661
	if (search_start < 0)
662
		search_start = 0;
663

664
	search_end = closest_local_line_a + max_search_distance_a + 1;
665
	if (search_end > length_a)
666
		search_end = length_a;
667

668
	for (i = search_start; i < search_end; ++i) {
669
		similarity = get_similarity(similarities,
670
					    i, local_line_b,
671
					    closest_local_line_a,
672
					    max_search_distance_a);
673
		if (*similarity == -1) {
674
			/* This value will never exceed 10 but assert just in
675
			 * case
676
			 */
677
			assert(abs(i - closest_local_line_a) < 1000);
678
			/* scale the similarity by (1000 - distance from
679
			 * closest line) to act as a tie break between lines
680
			 * that otherwise are equally similar.
681
			 */
682
			*similarity = fingerprint_similarity(
683
				fingerprints_b + local_line_b,
684
				fingerprints_a + i) *
685
				(1000 - abs(i - closest_local_line_a));
686
		}
687
		if (*similarity > best_similarity) {
688
			second_best_similarity = best_similarity;
689
			second_best_similarity_index = best_similarity_index;
690
			best_similarity = *similarity;
691
			best_similarity_index = i;
692
		} else if (*similarity > second_best_similarity) {
693
			second_best_similarity = *similarity;
694
			second_best_similarity_index = i;
695
		}
696
	}
697

698
	if (best_similarity == 0) {
699
		/* this line definitely doesn't match with anything. Mark it
700
		 * with this special value so it doesn't get invalidated and
701
		 * won't be recalculated.
702
		 */
703
		certainties[local_line_b] = CERTAIN_NOTHING_MATCHES;
704
		result[local_line_b] = -1;
705
	} else {
706
		/* Calculate the certainty with which this line matches.
707
		 * If the line matches well with two lines then that reduces
708
		 * the certainty. However we still want to prioritise matching
709
		 * a line that matches very well with two lines over matching a
710
		 * line that matches poorly with one line, hence doubling
711
		 * best_similarity.
712
		 * This means that if we have
713
		 * line X that matches only one line with a score of 3,
714
		 * line Y that matches two lines equally with a score of 5,
715
		 * and line Z that matches only one line with a score or 2,
716
		 * then the lines in order of certainty are X, Y, Z.
717
		 */
718
		certainties[local_line_b] = best_similarity * 2 -
719
			second_best_similarity;
720

721
		/* We keep both the best and second best results to allow us to
722
		 * check at a later stage of the matching process whether the
723
		 * result needs to be invalidated.
724
		 */
725
		result[local_line_b] = start_a + best_similarity_index;
726
		second_best_result[local_line_b] =
727
			start_a + second_best_similarity_index;
728
	}
729
}
730

731
/*
732
 * This finds the line that we can match with the most confidence, and
733
 * uses it as a partition. It then calls itself on the lines on either side of
734
 * that partition. In this way we avoid lines appearing out of order, and
735
 * retain a sensible line ordering.
736
 * \param start_a index of the first line in A with which lines in B may be
737
 * 		  compared.
738
 * \param start_b index of the first line in B for which matching should be
739
 * 		  done.
740
 * \param length_a number of lines in A with which lines in B may be compared.
741
 * \param length_b number of lines in B for which matching should be done.
742
 * \param fingerprints_a mutable array of fingerprints in A. The first element
743
 * 			 corresponds to the line at start_a.
744
 * \param fingerprints_b array of fingerprints in B. The first element
745
 * 			 corresponds to the line at start_b.
746
 * \param similarities 2-dimensional array of similarities between lines in A
747
 * 		       and B. See get_similarity() for more details.
748
 * \param certainties array of values indicating how strongly a line in B is
749
 * 		      matched with some line in A.
750
 * \param second_best_result array of absolute indices in A for the second
751
 * 			     closest match of a line in B.
752
 * \param result array of absolute indices in A for the closest match of a line
753
 * 		 in B.
754
 * \param max_search_distance_a maximum distance in lines from the closest line
755
 * 			      in A for other lines in A for which
756
 * 			      similarities may be calculated.
757
 * \param max_search_distance_b an upper bound on the greatest possible
758
 * 			      distance between lines in B such that they will
759
 *                              both be compared with the same line in A
760
 * 			      according to max_search_distance_a.
761
 * \param map_line_number_in_b_to_a parameter to map_line_number().
762
 */
763
static void fuzzy_find_matching_lines_recurse(
764
	int start_a, int start_b,
765
	int length_a, int length_b,
766
	struct fingerprint *fingerprints_a,
767
	struct fingerprint *fingerprints_b,
768
	int *similarities,
769
	int *certainties,
770
	int *second_best_result,
771
	int *result,
772
	int max_search_distance_a,
773
	int max_search_distance_b,
774
	const struct line_number_mapping *map_line_number_in_b_to_a)
775
{
776
	int i, invalidate_min, invalidate_max, offset_b,
777
		second_half_start_a, second_half_start_b,
778
		second_half_length_a, second_half_length_b,
779
		most_certain_line_a, most_certain_local_line_b = -1,
780
		most_certain_line_certainty = -1,
781
		closest_local_line_a;
782

783
	for (i = 0; i < length_b; ++i) {
784
		find_best_line_matches(start_a,
785
				       length_a,
786
				       start_b,
787
				       i,
788
				       fingerprints_a,
789
				       fingerprints_b,
790
				       similarities,
791
				       certainties,
792
				       second_best_result,
793
				       result,
794
				       max_search_distance_a,
795
				       map_line_number_in_b_to_a);
796

797
		if (certainties[i] > most_certain_line_certainty) {
798
			most_certain_line_certainty = certainties[i];
799
			most_certain_local_line_b = i;
800
		}
801
	}
802

803
	/* No matches. */
804
	if (most_certain_local_line_b == -1)
805
		return;
806

807
	most_certain_line_a = result[most_certain_local_line_b];
808

809
	/*
810
	 * Subtract the most certain line's fingerprint in B from the matched
811
	 * fingerprint in A. This means that other lines in B can't also match
812
	 * the same parts of the line in A.
813
	 */
814
	fingerprint_subtract(fingerprints_a + most_certain_line_a - start_a,
815
			     fingerprints_b + most_certain_local_line_b);
816

817
	/* Invalidate results that may be affected by the choice of most
818
	 * certain line.
819
	 */
820
	invalidate_min = most_certain_local_line_b - max_search_distance_b;
821
	invalidate_max = most_certain_local_line_b + max_search_distance_b + 1;
822
	if (invalidate_min < 0)
823
		invalidate_min = 0;
824
	if (invalidate_max > length_b)
825
		invalidate_max = length_b;
826

827
	/* As the fingerprint in A has changed, discard previously calculated
828
	 * similarity values with that fingerprint.
829
	 */
830
	for (i = invalidate_min; i < invalidate_max; ++i) {
831
		closest_local_line_a = map_line_number(
832
			i + start_b, map_line_number_in_b_to_a) - start_a;
833

834
		/* Check that the lines in A and B are close enough that there
835
		 * is a similarity value for them.
836
		 */
837
		if (abs(most_certain_line_a - start_a - closest_local_line_a) >
838
			max_search_distance_a) {
839
			continue;
840
		}
841

842
		*get_similarity(similarities, most_certain_line_a - start_a,
843
				i, closest_local_line_a,
844
				max_search_distance_a) = -1;
845
	}
846

847
	/* More invalidating of results that may be affected by the choice of
848
	 * most certain line.
849
	 * Discard the matches for lines in B that are currently matched with a
850
	 * line in A such that their ordering contradicts the ordering imposed
851
	 * by the choice of most certain line.
852
	 */
853
	for (i = most_certain_local_line_b - 1; i >= invalidate_min; --i) {
854
		/* In this loop we discard results for lines in B that are
855
		 * before most-certain-line-B but are matched with a line in A
856
		 * that is after most-certain-line-A.
857
		 */
858
		if (certainties[i] >= 0 &&
859
		    (result[i] >= most_certain_line_a ||
860
		     second_best_result[i] >= most_certain_line_a)) {
861
			certainties[i] = CERTAINTY_NOT_CALCULATED;
862
		}
863
	}
864
	for (i = most_certain_local_line_b + 1; i < invalidate_max; ++i) {
865
		/* In this loop we discard results for lines in B that are
866
		 * after most-certain-line-B but are matched with a line in A
867
		 * that is before most-certain-line-A.
868
		 */
869
		if (certainties[i] >= 0 &&
870
		    (result[i] <= most_certain_line_a ||
871
		     second_best_result[i] <= most_certain_line_a)) {
872
			certainties[i] = CERTAINTY_NOT_CALCULATED;
873
		}
874
	}
875

876
	/* Repeat the matching process for lines before the most certain line.
877
	 */
878
	if (most_certain_local_line_b > 0) {
879
		fuzzy_find_matching_lines_recurse(
880
			start_a, start_b,
881
			most_certain_line_a + 1 - start_a,
882
			most_certain_local_line_b,
883
			fingerprints_a, fingerprints_b, similarities,
884
			certainties, second_best_result, result,
885
			max_search_distance_a,
886
			max_search_distance_b,
887
			map_line_number_in_b_to_a);
888
	}
889
	/* Repeat the matching process for lines after the most certain line.
890
	 */
891
	if (most_certain_local_line_b + 1 < length_b) {
892
		second_half_start_a = most_certain_line_a;
893
		offset_b = most_certain_local_line_b + 1;
894
		second_half_start_b = start_b + offset_b;
895
		second_half_length_a =
896
			length_a + start_a - second_half_start_a;
897
		second_half_length_b =
898
			length_b + start_b - second_half_start_b;
899
		fuzzy_find_matching_lines_recurse(
900
			second_half_start_a, second_half_start_b,
901
			second_half_length_a, second_half_length_b,
902
			fingerprints_a + second_half_start_a - start_a,
903
			fingerprints_b + offset_b,
904
			similarities +
905
				offset_b * (max_search_distance_a * 2 + 1),
906
			certainties + offset_b,
907
			second_best_result + offset_b, result + offset_b,
908
			max_search_distance_a,
909
			max_search_distance_b,
910
			map_line_number_in_b_to_a);
911
	}
912
}
913

914
/* Find the lines in the parent line range that most closely match the lines in
915
 * the target line range. This is accomplished by matching fingerprints in each
916
 * blame_origin, and choosing the best matches that preserve the line ordering.
917
 * See struct fingerprint for details of fingerprint matching, and
918
 * fuzzy_find_matching_lines_recurse for details of preserving line ordering.
919
 *
920
 * The performance is believed to be O(n log n) in the typical case and O(n^2)
921
 * in a pathological case, where n is the number of lines in the target range.
922
 */
923
static int *fuzzy_find_matching_lines(struct blame_origin *parent,
924
				      struct blame_origin *target,
925
				      int tlno, int parent_slno, int same,
926
				      int parent_len)
927
{
928
	/* We use the terminology "A" for the left hand side of the diff AKA
929
	 * parent, and "B" for the right hand side of the diff AKA target. */
930
	int start_a = parent_slno;
931
	int length_a = parent_len;
932
	int start_b = tlno;
933
	int length_b = same - tlno;
934

935
	struct line_number_mapping map_line_number_in_b_to_a = {
936
		start_a, length_a, start_b, length_b
937
	};
938

939
	struct fingerprint *fingerprints_a = parent->fingerprints;
940
	struct fingerprint *fingerprints_b = target->fingerprints;
941

942
	int i, *result, *second_best_result,
943
		*certainties, *similarities, similarity_count;
944

945
	/*
946
	 * max_search_distance_a means that given a line in B, compare it to
947
	 * the line in A that is closest to its position, and the lines in A
948
	 * that are no greater than max_search_distance_a lines away from the
949
	 * closest line in A.
950
	 *
951
	 * max_search_distance_b is an upper bound on the greatest possible
952
	 * distance between lines in B such that they will both be compared
953
	 * with the same line in A according to max_search_distance_a.
954
	 */
955
	int max_search_distance_a = 10, max_search_distance_b;
956

957
	if (length_a <= 0)
958
		return NULL;
959

960
	if (max_search_distance_a >= length_a)
961
		max_search_distance_a = length_a ? length_a - 1 : 0;
962

963
	max_search_distance_b = ((2 * max_search_distance_a + 1) * length_b
964
				 - 1) / length_a;
965

966
	CALLOC_ARRAY(result, length_b);
967
	CALLOC_ARRAY(second_best_result, length_b);
968
	CALLOC_ARRAY(certainties, length_b);
969

970
	/* See get_similarity() for details of similarities. */
971
	similarity_count = length_b * (max_search_distance_a * 2 + 1);
972
	CALLOC_ARRAY(similarities, similarity_count);
973

974
	for (i = 0; i < length_b; ++i) {
975
		result[i] = -1;
976
		second_best_result[i] = -1;
977
		certainties[i] = CERTAINTY_NOT_CALCULATED;
978
	}
979

980
	for (i = 0; i < similarity_count; ++i)
981
		similarities[i] = -1;
982

983
	fuzzy_find_matching_lines_recurse(start_a, start_b,
984
					  length_a, length_b,
985
					  fingerprints_a + start_a,
986
					  fingerprints_b + start_b,
987
					  similarities,
988
					  certainties,
989
					  second_best_result,
990
					  result,
991
					  max_search_distance_a,
992
					  max_search_distance_b,
993
					  &map_line_number_in_b_to_a);
994

995
	free(similarities);
996
	free(certainties);
997
	free(second_best_result);
998

999
	return result;
1000
}
1001

1002
static void fill_origin_fingerprints(struct blame_origin *o)
1003
{
1004
	int *line_starts;
1005

1006
	if (o->fingerprints)
1007
		return;
1008
	o->num_lines = find_line_starts(&line_starts, o->file.ptr,
1009
					o->file.size);
1010
	CALLOC_ARRAY(o->fingerprints, o->num_lines);
1011
	get_line_fingerprints(o->fingerprints, o->file.ptr, line_starts,
1012
			      0, o->num_lines);
1013
	free(line_starts);
1014
}
1015

1016
static void drop_origin_fingerprints(struct blame_origin *o)
1017
{
1018
	if (o->fingerprints) {
1019
		free_line_fingerprints(o->fingerprints, o->num_lines);
1020
		o->num_lines = 0;
1021
		FREE_AND_NULL(o->fingerprints);
1022
	}
1023
}
1024

1025
/*
1026
 * Given an origin, prepare mmfile_t structure to be used by the
1027
 * diff machinery
1028
 */
1029
static void fill_origin_blob(struct diff_options *opt,
1030
			     struct blame_origin *o, mmfile_t *file,
1031
			     int *num_read_blob, int fill_fingerprints)
1032
{
1033
	if (!o->file.ptr) {
1034
		enum object_type type;
1035
		unsigned long file_size;
1036

1037
		(*num_read_blob)++;
1038
		if (opt->flags.allow_textconv &&
1039
		    textconv_object(opt->repo, o->path, o->mode,
1040
				    &o->blob_oid, 1, &file->ptr, &file_size))
1041
			;
1042
		else
1043
			file->ptr = repo_read_object_file(the_repository,
1044
							  &o->blob_oid, &type,
1045
							  &file_size);
1046
		file->size = file_size;
1047

1048
		if (!file->ptr)
1049
			die("Cannot read blob %s for path %s",
1050
			    oid_to_hex(&o->blob_oid),
1051
			    o->path);
1052
		o->file = *file;
1053
	}
1054
	else
1055
		*file = o->file;
1056
	if (fill_fingerprints)
1057
		fill_origin_fingerprints(o);
1058
}
1059

1060
static void drop_origin_blob(struct blame_origin *o)
1061
{
1062
	FREE_AND_NULL(o->file.ptr);
1063
	drop_origin_fingerprints(o);
1064
}
1065

1066
/*
1067
 * Any merge of blames happens on lists of blames that arrived via
1068
 * different parents in a single suspect.  In this case, we want to
1069
 * sort according to the suspect line numbers as opposed to the final
1070
 * image line numbers.  The function body is somewhat longish because
1071
 * it avoids unnecessary writes.
1072
 */
1073

1074
static struct blame_entry *blame_merge(struct blame_entry *list1,
1075
				       struct blame_entry *list2)
1076
{
1077
	struct blame_entry *p1 = list1, *p2 = list2,
1078
		**tail = &list1;
1079

1080
	if (!p1)
1081
		return p2;
1082
	if (!p2)
1083
		return p1;
1084

1085
	if (p1->s_lno <= p2->s_lno) {
1086
		do {
1087
			tail = &p1->next;
1088
			if (!(p1 = *tail)) {
1089
				*tail = p2;
1090
				return list1;
1091
			}
1092
		} while (p1->s_lno <= p2->s_lno);
1093
	}
1094
	for (;;) {
1095
		*tail = p2;
1096
		do {
1097
			tail = &p2->next;
1098
			if (!(p2 = *tail))  {
1099
				*tail = p1;
1100
				return list1;
1101
			}
1102
		} while (p1->s_lno > p2->s_lno);
1103
		*tail = p1;
1104
		do {
1105
			tail = &p1->next;
1106
			if (!(p1 = *tail)) {
1107
				*tail = p2;
1108
				return list1;
1109
			}
1110
		} while (p1->s_lno <= p2->s_lno);
1111
	}
1112
}
1113

1114
DEFINE_LIST_SORT(static, sort_blame_entries, struct blame_entry, next);
1115

1116
/*
1117
 * Final image line numbers are all different, so we don't need a
1118
 * three-way comparison here.
1119
 */
1120

1121
static int compare_blame_final(const struct blame_entry *e1,
1122
			       const struct blame_entry *e2)
1123
{
1124
	return e1->lno > e2->lno ? 1 : -1;
1125
}
1126

1127
static int compare_blame_suspect(const struct blame_entry *s1,
1128
				 const struct blame_entry *s2)
1129
{
1130
	/*
1131
	 * to allow for collating suspects, we sort according to the
1132
	 * respective pointer value as the primary sorting criterion.
1133
	 * The actual relation is pretty unimportant as long as it
1134
	 * establishes a total order.  Comparing as integers gives us
1135
	 * that.
1136
	 */
1137
	if (s1->suspect != s2->suspect)
1138
		return (intptr_t)s1->suspect > (intptr_t)s2->suspect ? 1 : -1;
1139
	if (s1->s_lno == s2->s_lno)
1140
		return 0;
1141
	return s1->s_lno > s2->s_lno ? 1 : -1;
1142
}
1143

1144
void blame_sort_final(struct blame_scoreboard *sb)
1145
{
1146
	sort_blame_entries(&sb->ent, compare_blame_final);
1147
}
1148

1149
static int compare_commits_by_reverse_commit_date(const void *a,
1150
						  const void *b,
1151
						  void *c)
1152
{
1153
	return -compare_commits_by_commit_date(a, b, c);
1154
}
1155

1156
/*
1157
 * For debugging -- origin is refcounted, and this asserts that
1158
 * we do not underflow.
1159
 */
1160
static void sanity_check_refcnt(struct blame_scoreboard *sb)
1161
{
1162
	int baa = 0;
1163
	struct blame_entry *ent;
1164

1165
	for (ent = sb->ent; ent; ent = ent->next) {
1166
		/* Nobody should have zero or negative refcnt */
1167
		if (ent->suspect->refcnt <= 0) {
1168
			fprintf(stderr, "%s in %s has negative refcnt %d\n",
1169
				ent->suspect->path,
1170
				oid_to_hex(&ent->suspect->commit->object.oid),
1171
				ent->suspect->refcnt);
1172
			baa = 1;
1173
		}
1174
	}
1175
	if (baa)
1176
		sb->on_sanity_fail(sb, baa);
1177
}
1178

1179
/*
1180
 * If two blame entries that are next to each other came from
1181
 * contiguous lines in the same origin (i.e. <commit, path> pair),
1182
 * merge them together.
1183
 */
1184
void blame_coalesce(struct blame_scoreboard *sb)
1185
{
1186
	struct blame_entry *ent, *next;
1187

1188
	for (ent = sb->ent; ent && (next = ent->next); ent = next) {
1189
		if (ent->suspect == next->suspect &&
1190
		    ent->s_lno + ent->num_lines == next->s_lno &&
1191
		    ent->lno + ent->num_lines == next->lno &&
1192
		    ent->ignored == next->ignored &&
1193
		    ent->unblamable == next->unblamable) {
1194
			ent->num_lines += next->num_lines;
1195
			ent->next = next->next;
1196
			blame_origin_decref(next->suspect);
1197
			free(next);
1198
			ent->score = 0;
1199
			next = ent; /* again */
1200
		}
1201
	}
1202

1203
	if (sb->debug) /* sanity */
1204
		sanity_check_refcnt(sb);
1205
}
1206

1207
/*
1208
 * Merge the given sorted list of blames into a preexisting origin.
1209
 * If there were no previous blames to that commit, it is entered into
1210
 * the commit priority queue of the score board.
1211
 */
1212

1213
static void queue_blames(struct blame_scoreboard *sb, struct blame_origin *porigin,
1214
			 struct blame_entry *sorted)
1215
{
1216
	if (porigin->suspects)
1217
		porigin->suspects = blame_merge(porigin->suspects, sorted);
1218
	else {
1219
		struct blame_origin *o;
1220
		for (o = get_blame_suspects(porigin->commit); o; o = o->next) {
1221
			if (o->suspects) {
1222
				porigin->suspects = sorted;
1223
				return;
1224
			}
1225
		}
1226
		porigin->suspects = sorted;
1227
		prio_queue_put(&sb->commits, porigin->commit);
1228
	}
1229
}
1230

1231
/*
1232
 * Fill the blob_sha1 field of an origin if it hasn't, so that later
1233
 * call to fill_origin_blob() can use it to locate the data.  blob_sha1
1234
 * for an origin is also used to pass the blame for the entire file to
1235
 * the parent to detect the case where a child's blob is identical to
1236
 * that of its parent's.
1237
 *
1238
 * This also fills origin->mode for corresponding tree path.
1239
 */
1240
static int fill_blob_sha1_and_mode(struct repository *r,
1241
				   struct blame_origin *origin)
1242
{
1243
	if (!is_null_oid(&origin->blob_oid))
1244
		return 0;
1245
	if (get_tree_entry(r, &origin->commit->object.oid, origin->path, &origin->blob_oid, &origin->mode))
1246
		goto error_out;
1247
	if (oid_object_info(r, &origin->blob_oid, NULL) != OBJ_BLOB)
1248
		goto error_out;
1249
	return 0;
1250
 error_out:
1251
	oidclr(&origin->blob_oid, the_repository->hash_algo);
1252
	origin->mode = S_IFINVALID;
1253
	return -1;
1254
}
1255

1256
struct blame_bloom_data {
1257
	/*
1258
	 * Changed-path Bloom filter keys. These can help prevent
1259
	 * computing diffs against first parents, but we need to
1260
	 * expand the list as code is moved or files are renamed.
1261
	 */
1262
	struct bloom_filter_settings *settings;
1263
	struct bloom_key **keys;
1264
	int nr;
1265
	int alloc;
1266
};
1267

1268
static int bloom_count_queries = 0;
1269
static int bloom_count_no = 0;
1270
static int maybe_changed_path(struct repository *r,
1271
			      struct blame_origin *origin,
1272
			      struct blame_bloom_data *bd)
1273
{
1274
	int i;
1275
	struct bloom_filter *filter;
1276

1277
	if (!bd)
1278
		return 1;
1279

1280
	if (commit_graph_generation(origin->commit) == GENERATION_NUMBER_INFINITY)
1281
		return 1;
1282

1283
	filter = get_bloom_filter(r, origin->commit);
1284

1285
	if (!filter)
1286
		return 1;
1287

1288
	bloom_count_queries++;
1289
	for (i = 0; i < bd->nr; i++) {
1290
		if (bloom_filter_contains(filter,
1291
					  bd->keys[i],
1292
					  bd->settings))
1293
			return 1;
1294
	}
1295

1296
	bloom_count_no++;
1297
	return 0;
1298
}
1299

1300
static void add_bloom_key(struct blame_bloom_data *bd,
1301
			  const char *path)
1302
{
1303
	if (!bd)
1304
		return;
1305

1306
	if (bd->nr >= bd->alloc) {
1307
		bd->alloc *= 2;
1308
		REALLOC_ARRAY(bd->keys, bd->alloc);
1309
	}
1310

1311
	bd->keys[bd->nr] = xmalloc(sizeof(struct bloom_key));
1312
	fill_bloom_key(path, strlen(path), bd->keys[bd->nr], bd->settings);
1313
	bd->nr++;
1314
}
1315

1316
/*
1317
 * We have an origin -- check if the same path exists in the
1318
 * parent and return an origin structure to represent it.
1319
 */
1320
static struct blame_origin *find_origin(struct repository *r,
1321
					struct commit *parent,
1322
					struct blame_origin *origin,
1323
					struct blame_bloom_data *bd)
1324
{
1325
	struct blame_origin *porigin;
1326
	struct diff_options diff_opts;
1327
	const char *paths[2];
1328

1329
	/* First check any existing origins */
1330
	for (porigin = get_blame_suspects(parent); porigin; porigin = porigin->next)
1331
		if (!strcmp(porigin->path, origin->path)) {
1332
			/*
1333
			 * The same path between origin and its parent
1334
			 * without renaming -- the most common case.
1335
			 */
1336
			return blame_origin_incref (porigin);
1337
		}
1338

1339
	/* See if the origin->path is different between parent
1340
	 * and origin first.  Most of the time they are the
1341
	 * same and diff-tree is fairly efficient about this.
1342
	 */
1343
	repo_diff_setup(r, &diff_opts);
1344
	diff_opts.flags.recursive = 1;
1345
	diff_opts.detect_rename = 0;
1346
	diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;
1347
	paths[0] = origin->path;
1348
	paths[1] = NULL;
1349

1350
	parse_pathspec(&diff_opts.pathspec,
1351
		       PATHSPEC_ALL_MAGIC & ~PATHSPEC_LITERAL,
1352
		       PATHSPEC_LITERAL_PATH, "", paths);
1353
	diff_setup_done(&diff_opts);
1354

1355
	if (is_null_oid(&origin->commit->object.oid))
1356
		do_diff_cache(get_commit_tree_oid(parent), &diff_opts);
1357
	else {
1358
		int compute_diff = 1;
1359
		if (origin->commit->parents &&
1360
		    oideq(&parent->object.oid,
1361
			  &origin->commit->parents->item->object.oid))
1362
			compute_diff = maybe_changed_path(r, origin, bd);
1363

1364
		if (compute_diff)
1365
			diff_tree_oid(get_commit_tree_oid(parent),
1366
				      get_commit_tree_oid(origin->commit),
1367
				      "", &diff_opts);
1368
	}
1369
	diffcore_std(&diff_opts);
1370

1371
	if (!diff_queued_diff.nr) {
1372
		/* The path is the same as parent */
1373
		porigin = get_origin(parent, origin->path);
1374
		oidcpy(&porigin->blob_oid, &origin->blob_oid);
1375
		porigin->mode = origin->mode;
1376
	} else {
1377
		/*
1378
		 * Since origin->path is a pathspec, if the parent
1379
		 * commit had it as a directory, we will see a whole
1380
		 * bunch of deletion of files in the directory that we
1381
		 * do not care about.
1382
		 */
1383
		int i;
1384
		struct diff_filepair *p = NULL;
1385
		for (i = 0; i < diff_queued_diff.nr; i++) {
1386
			const char *name;
1387
			p = diff_queued_diff.queue[i];
1388
			name = p->one->path ? p->one->path : p->two->path;
1389
			if (!strcmp(name, origin->path))
1390
				break;
1391
		}
1392
		if (!p)
1393
			die("internal error in blame::find_origin");
1394
		switch (p->status) {
1395
		default:
1396
			die("internal error in blame::find_origin (%c)",
1397
			    p->status);
1398
		case 'M':
1399
			porigin = get_origin(parent, origin->path);
1400
			oidcpy(&porigin->blob_oid, &p->one->oid);
1401
			porigin->mode = p->one->mode;
1402
			break;
1403
		case 'A':
1404
		case 'T':
1405
			/* Did not exist in parent, or type changed */
1406
			break;
1407
		}
1408
	}
1409
	diff_flush(&diff_opts);
1410
	return porigin;
1411
}
1412

1413
/*
1414
 * We have an origin -- find the path that corresponds to it in its
1415
 * parent and return an origin structure to represent it.
1416
 */
1417
static struct blame_origin *find_rename(struct repository *r,
1418
					struct commit *parent,
1419
					struct blame_origin *origin,
1420
					struct blame_bloom_data *bd)
1421
{
1422
	struct blame_origin *porigin = NULL;
1423
	struct diff_options diff_opts;
1424
	int i;
1425

1426
	repo_diff_setup(r, &diff_opts);
1427
	diff_opts.flags.recursive = 1;
1428
	diff_opts.detect_rename = DIFF_DETECT_RENAME;
1429
	diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;
1430
	diff_opts.single_follow = origin->path;
1431
	diff_setup_done(&diff_opts);
1432

1433
	if (is_null_oid(&origin->commit->object.oid))
1434
		do_diff_cache(get_commit_tree_oid(parent), &diff_opts);
1435
	else
1436
		diff_tree_oid(get_commit_tree_oid(parent),
1437
			      get_commit_tree_oid(origin->commit),
1438
			      "", &diff_opts);
1439
	diffcore_std(&diff_opts);
1440

1441
	for (i = 0; i < diff_queued_diff.nr; i++) {
1442
		struct diff_filepair *p = diff_queued_diff.queue[i];
1443
		if ((p->status == 'R' || p->status == 'C') &&
1444
		    !strcmp(p->two->path, origin->path)) {
1445
			add_bloom_key(bd, p->one->path);
1446
			porigin = get_origin(parent, p->one->path);
1447
			oidcpy(&porigin->blob_oid, &p->one->oid);
1448
			porigin->mode = p->one->mode;
1449
			break;
1450
		}
1451
	}
1452
	diff_flush(&diff_opts);
1453
	return porigin;
1454
}
1455

1456
/*
1457
 * Append a new blame entry to a given output queue.
1458
 */
1459
static void add_blame_entry(struct blame_entry ***queue,
1460
			    const struct blame_entry *src)
1461
{
1462
	struct blame_entry *e = xmalloc(sizeof(*e));
1463
	memcpy(e, src, sizeof(*e));
1464
	blame_origin_incref(e->suspect);
1465

1466
	e->next = **queue;
1467
	**queue = e;
1468
	*queue = &e->next;
1469
}
1470

1471
/*
1472
 * src typically is on-stack; we want to copy the information in it to
1473
 * a malloced blame_entry that gets added to the given queue.  The
1474
 * origin of dst loses a refcnt.
1475
 */
1476
static void dup_entry(struct blame_entry ***queue,
1477
		      struct blame_entry *dst, struct blame_entry *src)
1478
{
1479
	blame_origin_incref(src->suspect);
1480
	blame_origin_decref(dst->suspect);
1481
	memcpy(dst, src, sizeof(*src));
1482
	dst->next = **queue;
1483
	**queue = dst;
1484
	*queue = &dst->next;
1485
}
1486

1487
const char *blame_nth_line(struct blame_scoreboard *sb, long lno)
1488
{
1489
	return sb->final_buf + sb->lineno[lno];
1490
}
1491

1492
/*
1493
 * It is known that lines between tlno to same came from parent, and e
1494
 * has an overlap with that range.  it also is known that parent's
1495
 * line plno corresponds to e's line tlno.
1496
 *
1497
 *                <---- e ----->
1498
 *                   <------>
1499
 *                   <------------>
1500
 *             <------------>
1501
 *             <------------------>
1502
 *
1503
 * Split e into potentially three parts; before this chunk, the chunk
1504
 * to be blamed for the parent, and after that portion.
1505
 */
1506
static void split_overlap(struct blame_entry *split,
1507
			  struct blame_entry *e,
1508
			  int tlno, int plno, int same,
1509
			  struct blame_origin *parent)
1510
{
1511
	int chunk_end_lno;
1512
	int i;
1513
	memset(split, 0, sizeof(struct blame_entry [3]));
1514

1515
	for (i = 0; i < 3; i++) {
1516
		split[i].ignored = e->ignored;
1517
		split[i].unblamable = e->unblamable;
1518
	}
1519

1520
	if (e->s_lno < tlno) {
1521
		/* there is a pre-chunk part not blamed on parent */
1522
		split[0].suspect = blame_origin_incref(e->suspect);
1523
		split[0].lno = e->lno;
1524
		split[0].s_lno = e->s_lno;
1525
		split[0].num_lines = tlno - e->s_lno;
1526
		split[1].lno = e->lno + tlno - e->s_lno;
1527
		split[1].s_lno = plno;
1528
	}
1529
	else {
1530
		split[1].lno = e->lno;
1531
		split[1].s_lno = plno + (e->s_lno - tlno);
1532
	}
1533

1534
	if (same < e->s_lno + e->num_lines) {
1535
		/* there is a post-chunk part not blamed on parent */
1536
		split[2].suspect = blame_origin_incref(e->suspect);
1537
		split[2].lno = e->lno + (same - e->s_lno);
1538
		split[2].s_lno = e->s_lno + (same - e->s_lno);
1539
		split[2].num_lines = e->s_lno + e->num_lines - same;
1540
		chunk_end_lno = split[2].lno;
1541
	}
1542
	else
1543
		chunk_end_lno = e->lno + e->num_lines;
1544
	split[1].num_lines = chunk_end_lno - split[1].lno;
1545

1546
	/*
1547
	 * if it turns out there is nothing to blame the parent for,
1548
	 * forget about the splitting.  !split[1].suspect signals this.
1549
	 */
1550
	if (split[1].num_lines < 1)
1551
		return;
1552
	split[1].suspect = blame_origin_incref(parent);
1553
}
1554

1555
/*
1556
 * split_overlap() divided an existing blame e into up to three parts
1557
 * in split.  Any assigned blame is moved to queue to
1558
 * reflect the split.
1559
 */
1560
static void split_blame(struct blame_entry ***blamed,
1561
			struct blame_entry ***unblamed,
1562
			struct blame_entry *split,
1563
			struct blame_entry *e)
1564
{
1565
	if (split[0].suspect && split[2].suspect) {
1566
		/* The first part (reuse storage for the existing entry e) */
1567
		dup_entry(unblamed, e, &split[0]);
1568

1569
		/* The last part -- me */
1570
		add_blame_entry(unblamed, &split[2]);
1571

1572
		/* ... and the middle part -- parent */
1573
		add_blame_entry(blamed, &split[1]);
1574
	}
1575
	else if (!split[0].suspect && !split[2].suspect)
1576
		/*
1577
		 * The parent covers the entire area; reuse storage for
1578
		 * e and replace it with the parent.
1579
		 */
1580
		dup_entry(blamed, e, &split[1]);
1581
	else if (split[0].suspect) {
1582
		/* me and then parent */
1583
		dup_entry(unblamed, e, &split[0]);
1584
		add_blame_entry(blamed, &split[1]);
1585
	}
1586
	else {
1587
		/* parent and then me */
1588
		dup_entry(blamed, e, &split[1]);
1589
		add_blame_entry(unblamed, &split[2]);
1590
	}
1591
}
1592

1593
/*
1594
 * After splitting the blame, the origins used by the
1595
 * on-stack blame_entry should lose one refcnt each.
1596
 */
1597
static void decref_split(struct blame_entry *split)
1598
{
1599
	int i;
1600

1601
	for (i = 0; i < 3; i++)
1602
		blame_origin_decref(split[i].suspect);
1603
}
1604

1605
/*
1606
 * reverse_blame reverses the list given in head, appending tail.
1607
 * That allows us to build lists in reverse order, then reverse them
1608
 * afterwards.  This can be faster than building the list in proper
1609
 * order right away.  The reason is that building in proper order
1610
 * requires writing a link in the _previous_ element, while building
1611
 * in reverse order just requires placing the list head into the
1612
 * _current_ element.
1613
 */
1614

1615
static struct blame_entry *reverse_blame(struct blame_entry *head,
1616
					 struct blame_entry *tail)
1617
{
1618
	while (head) {
1619
		struct blame_entry *next = head->next;
1620
		head->next = tail;
1621
		tail = head;
1622
		head = next;
1623
	}
1624
	return tail;
1625
}
1626

1627
/*
1628
 * Splits a blame entry into two entries at 'len' lines.  The original 'e'
1629
 * consists of len lines, i.e. [e->lno, e->lno + len), and the second part,
1630
 * which is returned, consists of the remainder: [e->lno + len, e->lno +
1631
 * e->num_lines).  The caller needs to sort out the reference counting for the
1632
 * new entry's suspect.
1633
 */
1634
static struct blame_entry *split_blame_at(struct blame_entry *e, int len,
1635
					  struct blame_origin *new_suspect)
1636
{
1637
	struct blame_entry *n = xcalloc(1, sizeof(struct blame_entry));
1638

1639
	n->suspect = new_suspect;
1640
	n->ignored = e->ignored;
1641
	n->unblamable = e->unblamable;
1642
	n->lno = e->lno + len;
1643
	n->s_lno = e->s_lno + len;
1644
	n->num_lines = e->num_lines - len;
1645
	e->num_lines = len;
1646
	e->score = 0;
1647
	return n;
1648
}
1649

1650
struct blame_line_tracker {
1651
	int is_parent;
1652
	int s_lno;
1653
};
1654

1655
static int are_lines_adjacent(struct blame_line_tracker *first,
1656
			      struct blame_line_tracker *second)
1657
{
1658
	return first->is_parent == second->is_parent &&
1659
	       first->s_lno + 1 == second->s_lno;
1660
}
1661

1662
static int scan_parent_range(struct fingerprint *p_fps,
1663
			     struct fingerprint *t_fps, int t_idx,
1664
			     int from, int nr_lines)
1665
{
1666
	int sim, p_idx;
1667
	#define FINGERPRINT_FILE_THRESHOLD	10
1668
	int best_sim_val = FINGERPRINT_FILE_THRESHOLD;
1669
	int best_sim_idx = -1;
1670

1671
	for (p_idx = from; p_idx < from + nr_lines; p_idx++) {
1672
		sim = fingerprint_similarity(&t_fps[t_idx], &p_fps[p_idx]);
1673
		if (sim < best_sim_val)
1674
			continue;
1675
		/* Break ties with the closest-to-target line number */
1676
		if (sim == best_sim_val && best_sim_idx != -1 &&
1677
		    abs(best_sim_idx - t_idx) < abs(p_idx - t_idx))
1678
			continue;
1679
		best_sim_val = sim;
1680
		best_sim_idx = p_idx;
1681
	}
1682
	return best_sim_idx;
1683
}
1684

1685
/*
1686
 * The first pass checks the blame entry (from the target) against the parent's
1687
 * diff chunk.  If that fails for a line, the second pass tries to match that
1688
 * line to any part of parent file.  That catches cases where a change was
1689
 * broken into two chunks by 'context.'
1690
 */
1691
static void guess_line_blames(struct blame_origin *parent,
1692
			      struct blame_origin *target,
1693
			      int tlno, int offset, int same, int parent_len,
1694
			      struct blame_line_tracker *line_blames)
1695
{
1696
	int i, best_idx, target_idx;
1697
	int parent_slno = tlno + offset;
1698
	int *fuzzy_matches;
1699

1700
	fuzzy_matches = fuzzy_find_matching_lines(parent, target,
1701
						  tlno, parent_slno, same,
1702
						  parent_len);
1703
	for (i = 0; i < same - tlno; i++) {
1704
		target_idx = tlno + i;
1705
		if (fuzzy_matches && fuzzy_matches[i] >= 0) {
1706
			best_idx = fuzzy_matches[i];
1707
		} else {
1708
			best_idx = scan_parent_range(parent->fingerprints,
1709
						     target->fingerprints,
1710
						     target_idx, 0,
1711
						     parent->num_lines);
1712
		}
1713
		if (best_idx >= 0) {
1714
			line_blames[i].is_parent = 1;
1715
			line_blames[i].s_lno = best_idx;
1716
		} else {
1717
			line_blames[i].is_parent = 0;
1718
			line_blames[i].s_lno = target_idx;
1719
		}
1720
	}
1721
	free(fuzzy_matches);
1722
}
1723

1724
/*
1725
 * This decides which parts of a blame entry go to the parent (added to the
1726
 * ignoredp list) and which stay with the target (added to the diffp list).  The
1727
 * actual decision was made in a separate heuristic function, and those answers
1728
 * for the lines in 'e' are in line_blames.  This consumes e, essentially
1729
 * putting it on a list.
1730
 *
1731
 * Note that the blame entries on the ignoredp list are not necessarily sorted
1732
 * with respect to the parent's line numbers yet.
1733
 */
1734
static void ignore_blame_entry(struct blame_entry *e,
1735
			       struct blame_origin *parent,
1736
			       struct blame_entry **diffp,
1737
			       struct blame_entry **ignoredp,
1738
			       struct blame_line_tracker *line_blames)
1739
{
1740
	int entry_len, nr_lines, i;
1741

1742
	/*
1743
	 * We carve new entries off the front of e.  Each entry comes from a
1744
	 * contiguous chunk of lines: adjacent lines from the same origin
1745
	 * (either the parent or the target).
1746
	 */
1747
	entry_len = 1;
1748
	nr_lines = e->num_lines;	/* e changes in the loop */
1749
	for (i = 0; i < nr_lines; i++) {
1750
		struct blame_entry *next = NULL;
1751

1752
		/*
1753
		 * We are often adjacent to the next line - only split the blame
1754
		 * entry when we have to.
1755
		 */
1756
		if (i + 1 < nr_lines) {
1757
			if (are_lines_adjacent(&line_blames[i],
1758
					       &line_blames[i + 1])) {
1759
				entry_len++;
1760
				continue;
1761
			}
1762
			next = split_blame_at(e, entry_len,
1763
					      blame_origin_incref(e->suspect));
1764
		}
1765
		if (line_blames[i].is_parent) {
1766
			e->ignored = 1;
1767
			blame_origin_decref(e->suspect);
1768
			e->suspect = blame_origin_incref(parent);
1769
			e->s_lno = line_blames[i - entry_len + 1].s_lno;
1770
			e->next = *ignoredp;
1771
			*ignoredp = e;
1772
		} else {
1773
			e->unblamable = 1;
1774
			/* e->s_lno is already in the target's address space. */
1775
			e->next = *diffp;
1776
			*diffp = e;
1777
		}
1778
		assert(e->num_lines == entry_len);
1779
		e = next;
1780
		entry_len = 1;
1781
	}
1782
	assert(!e);
1783
}
1784

1785
/*
1786
 * Process one hunk from the patch between the current suspect for
1787
 * blame_entry e and its parent.  This first blames any unfinished
1788
 * entries before the chunk (which is where target and parent start
1789
 * differing) on the parent, and then splits blame entries at the
1790
 * start and at the end of the difference region.  Since use of -M and
1791
 * -C options may lead to overlapping/duplicate source line number
1792
 * ranges, all we can rely on from sorting/merging is the order of the
1793
 * first suspect line number.
1794
 *
1795
 * tlno: line number in the target where this chunk begins
1796
 * same: line number in the target where this chunk ends
1797
 * offset: add to tlno to get the chunk starting point in the parent
1798
 * parent_len: number of lines in the parent chunk
1799
 */
1800
static void blame_chunk(struct blame_entry ***dstq, struct blame_entry ***srcq,
1801
			int tlno, int offset, int same, int parent_len,
1802
			struct blame_origin *parent,
1803
			struct blame_origin *target, int ignore_diffs)
1804
{
1805
	struct blame_entry *e = **srcq;
1806
	struct blame_entry *samep = NULL, *diffp = NULL, *ignoredp = NULL;
1807
	struct blame_line_tracker *line_blames = NULL;
1808

1809
	while (e && e->s_lno < tlno) {
1810
		struct blame_entry *next = e->next;
1811
		/*
1812
		 * current record starts before differing portion.  If
1813
		 * it reaches into it, we need to split it up and
1814
		 * examine the second part separately.
1815
		 */
1816
		if (e->s_lno + e->num_lines > tlno) {
1817
			/* Move second half to a new record */
1818
			struct blame_entry *n;
1819

1820
			n = split_blame_at(e, tlno - e->s_lno, e->suspect);
1821
			/* Push new record to diffp */
1822
			n->next = diffp;
1823
			diffp = n;
1824
		} else
1825
			blame_origin_decref(e->suspect);
1826
		/* Pass blame for everything before the differing
1827
		 * chunk to the parent */
1828
		e->suspect = blame_origin_incref(parent);
1829
		e->s_lno += offset;
1830
		e->next = samep;
1831
		samep = e;
1832
		e = next;
1833
	}
1834
	/*
1835
	 * As we don't know how much of a common stretch after this
1836
	 * diff will occur, the currently blamed parts are all that we
1837
	 * can assign to the parent for now.
1838
	 */
1839

1840
	if (samep) {
1841
		**dstq = reverse_blame(samep, **dstq);
1842
		*dstq = &samep->next;
1843
	}
1844
	/*
1845
	 * Prepend the split off portions: everything after e starts
1846
	 * after the blameable portion.
1847
	 */
1848
	e = reverse_blame(diffp, e);
1849

1850
	/*
1851
	 * Now retain records on the target while parts are different
1852
	 * from the parent.
1853
	 */
1854
	samep = NULL;
1855
	diffp = NULL;
1856

1857
	if (ignore_diffs && same - tlno > 0) {
1858
		CALLOC_ARRAY(line_blames, same - tlno);
1859
		guess_line_blames(parent, target, tlno, offset, same,
1860
				  parent_len, line_blames);
1861
	}
1862

1863
	while (e && e->s_lno < same) {
1864
		struct blame_entry *next = e->next;
1865

1866
		/*
1867
		 * If current record extends into sameness, need to split.
1868
		 */
1869
		if (e->s_lno + e->num_lines > same) {
1870
			/*
1871
			 * Move second half to a new record to be
1872
			 * processed by later chunks
1873
			 */
1874
			struct blame_entry *n;
1875

1876
			n = split_blame_at(e, same - e->s_lno,
1877
					   blame_origin_incref(e->suspect));
1878
			/* Push new record to samep */
1879
			n->next = samep;
1880
			samep = n;
1881
		}
1882
		if (ignore_diffs) {
1883
			ignore_blame_entry(e, parent, &diffp, &ignoredp,
1884
					   line_blames + e->s_lno - tlno);
1885
		} else {
1886
			e->next = diffp;
1887
			diffp = e;
1888
		}
1889
		e = next;
1890
	}
1891
	free(line_blames);
1892
	if (ignoredp) {
1893
		/*
1894
		 * Note ignoredp is not sorted yet, and thus neither is dstq.
1895
		 * That list must be sorted before we queue_blames().  We defer
1896
		 * sorting until after all diff hunks are processed, so that
1897
		 * guess_line_blames() can pick *any* line in the parent.  The
1898
		 * slight drawback is that we end up sorting all blame entries
1899
		 * passed to the parent, including those that are unrelated to
1900
		 * changes made by the ignored commit.
1901
		 */
1902
		**dstq = reverse_blame(ignoredp, **dstq);
1903
		*dstq = &ignoredp->next;
1904
	}
1905
	**srcq = reverse_blame(diffp, reverse_blame(samep, e));
1906
	/* Move across elements that are in the unblamable portion */
1907
	if (diffp)
1908
		*srcq = &diffp->next;
1909
}
1910

1911
struct blame_chunk_cb_data {
1912
	struct blame_origin *parent;
1913
	struct blame_origin *target;
1914
	long offset;
1915
	int ignore_diffs;
1916
	struct blame_entry **dstq;
1917
	struct blame_entry **srcq;
1918
};
1919

1920
/* diff chunks are from parent to target */
1921
static int blame_chunk_cb(long start_a, long count_a,
1922
			  long start_b, long count_b, void *data)
1923
{
1924
	struct blame_chunk_cb_data *d = data;
1925
	if (start_a - start_b != d->offset)
1926
		die("internal error in blame::blame_chunk_cb");
1927
	blame_chunk(&d->dstq, &d->srcq, start_b, start_a - start_b,
1928
		    start_b + count_b, count_a, d->parent, d->target,
1929
		    d->ignore_diffs);
1930
	d->offset = start_a + count_a - (start_b + count_b);
1931
	return 0;
1932
}
1933

1934
/*
1935
 * We are looking at the origin 'target' and aiming to pass blame
1936
 * for the lines it is suspected to its parent.  Run diff to find
1937
 * which lines came from parent and pass blame for them.
1938
 */
1939
static void pass_blame_to_parent(struct blame_scoreboard *sb,
1940
				 struct blame_origin *target,
1941
				 struct blame_origin *parent, int ignore_diffs)
1942
{
1943
	mmfile_t file_p, file_o;
1944
	struct blame_chunk_cb_data d;
1945
	struct blame_entry *newdest = NULL;
1946

1947
	if (!target->suspects)
1948
		return; /* nothing remains for this target */
1949

1950
	d.parent = parent;
1951
	d.target = target;
1952
	d.offset = 0;
1953
	d.ignore_diffs = ignore_diffs;
1954
	d.dstq = &newdest; d.srcq = &target->suspects;
1955

1956
	fill_origin_blob(&sb->revs->diffopt, parent, &file_p,
1957
			 &sb->num_read_blob, ignore_diffs);
1958
	fill_origin_blob(&sb->revs->diffopt, target, &file_o,
1959
			 &sb->num_read_blob, ignore_diffs);
1960
	sb->num_get_patch++;
1961

1962
	if (diff_hunks(&file_p, &file_o, blame_chunk_cb, &d, sb->xdl_opts))
1963
		die("unable to generate diff (%s -> %s)",
1964
		    oid_to_hex(&parent->commit->object.oid),
1965
		    oid_to_hex(&target->commit->object.oid));
1966
	/* The rest are the same as the parent */
1967
	blame_chunk(&d.dstq, &d.srcq, INT_MAX, d.offset, INT_MAX, 0,
1968
		    parent, target, 0);
1969
	*d.dstq = NULL;
1970
	if (ignore_diffs)
1971
		sort_blame_entries(&newdest, compare_blame_suspect);
1972
	queue_blames(sb, parent, newdest);
1973

1974
	return;
1975
}
1976

1977
/*
1978
 * The lines in blame_entry after splitting blames many times can become
1979
 * very small and trivial, and at some point it becomes pointless to
1980
 * blame the parents.  E.g. "\t\t}\n\t}\n\n" appears everywhere in any
1981
 * ordinary C program, and it is not worth to say it was copied from
1982
 * totally unrelated file in the parent.
1983
 *
1984
 * Compute how trivial the lines in the blame_entry are.
1985
 */
1986
unsigned blame_entry_score(struct blame_scoreboard *sb, struct blame_entry *e)
1987
{
1988
	unsigned score;
1989
	const char *cp, *ep;
1990

1991
	if (e->score)
1992
		return e->score;
1993

1994
	score = 1;
1995
	cp = blame_nth_line(sb, e->lno);
1996
	ep = blame_nth_line(sb, e->lno + e->num_lines);
1997
	while (cp < ep) {
1998
		unsigned ch = *((unsigned char *)cp);
1999
		if (isalnum(ch))
2000
			score++;
2001
		cp++;
2002
	}
2003
	e->score = score;
2004
	return score;
2005
}
2006

2007
/*
2008
 * best_so_far[] and potential[] are both a split of an existing blame_entry
2009
 * that passes blame to the parent.  Maintain best_so_far the best split so
2010
 * far, by comparing potential and best_so_far and copying potential into
2011
 * bst_so_far as needed.
2012
 */
2013
static void copy_split_if_better(struct blame_scoreboard *sb,
2014
				 struct blame_entry *best_so_far,
2015
				 struct blame_entry *potential)
2016
{
2017
	int i;
2018

2019
	if (!potential[1].suspect)
2020
		return;
2021
	if (best_so_far[1].suspect) {
2022
		if (blame_entry_score(sb, &potential[1]) <
2023
		    blame_entry_score(sb, &best_so_far[1]))
2024
			return;
2025
	}
2026

2027
	for (i = 0; i < 3; i++)
2028
		blame_origin_incref(potential[i].suspect);
2029
	decref_split(best_so_far);
2030
	memcpy(best_so_far, potential, sizeof(struct blame_entry[3]));
2031
}
2032

2033
/*
2034
 * We are looking at a part of the final image represented by
2035
 * ent (tlno and same are offset by ent->s_lno).
2036
 * tlno is where we are looking at in the final image.
2037
 * up to (but not including) same match preimage.
2038
 * plno is where we are looking at in the preimage.
2039
 *
2040
 * <-------------- final image ---------------------->
2041
 *       <------ent------>
2042
 *         ^tlno ^same
2043
 *    <---------preimage----->
2044
 *         ^plno
2045
 *
2046
 * All line numbers are 0-based.
2047
 */
2048
static void handle_split(struct blame_scoreboard *sb,
2049
			 struct blame_entry *ent,
2050
			 int tlno, int plno, int same,
2051
			 struct blame_origin *parent,
2052
			 struct blame_entry *split)
2053
{
2054
	if (ent->num_lines <= tlno)
2055
		return;
2056
	if (tlno < same) {
2057
		struct blame_entry potential[3];
2058
		tlno += ent->s_lno;
2059
		same += ent->s_lno;
2060
		split_overlap(potential, ent, tlno, plno, same, parent);
2061
		copy_split_if_better(sb, split, potential);
2062
		decref_split(potential);
2063
	}
2064
}
2065

2066
struct handle_split_cb_data {
2067
	struct blame_scoreboard *sb;
2068
	struct blame_entry *ent;
2069
	struct blame_origin *parent;
2070
	struct blame_entry *split;
2071
	long plno;
2072
	long tlno;
2073
};
2074

2075
static int handle_split_cb(long start_a, long count_a,
2076
			   long start_b, long count_b, void *data)
2077
{
2078
	struct handle_split_cb_data *d = data;
2079
	handle_split(d->sb, d->ent, d->tlno, d->plno, start_b, d->parent,
2080
		     d->split);
2081
	d->plno = start_a + count_a;
2082
	d->tlno = start_b + count_b;
2083
	return 0;
2084
}
2085

2086
/*
2087
 * Find the lines from parent that are the same as ent so that
2088
 * we can pass blames to it.  file_p has the blob contents for
2089
 * the parent.
2090
 */
2091
static void find_copy_in_blob(struct blame_scoreboard *sb,
2092
			      struct blame_entry *ent,
2093
			      struct blame_origin *parent,
2094
			      struct blame_entry *split,
2095
			      mmfile_t *file_p)
2096
{
2097
	const char *cp;
2098
	mmfile_t file_o;
2099
	struct handle_split_cb_data d;
2100

2101
	memset(&d, 0, sizeof(d));
2102
	d.sb = sb; d.ent = ent; d.parent = parent; d.split = split;
2103
	/*
2104
	 * Prepare mmfile that contains only the lines in ent.
2105
	 */
2106
	cp = blame_nth_line(sb, ent->lno);
2107
	file_o.ptr = (char *) cp;
2108
	file_o.size = blame_nth_line(sb, ent->lno + ent->num_lines) - cp;
2109

2110
	/*
2111
	 * file_o is a part of final image we are annotating.
2112
	 * file_p partially may match that image.
2113
	 */
2114
	memset(split, 0, sizeof(struct blame_entry [3]));
2115
	if (diff_hunks(file_p, &file_o, handle_split_cb, &d, sb->xdl_opts))
2116
		die("unable to generate diff (%s)",
2117
		    oid_to_hex(&parent->commit->object.oid));
2118
	/* remainder, if any, all match the preimage */
2119
	handle_split(sb, ent, d.tlno, d.plno, ent->num_lines, parent, split);
2120
}
2121

2122
/* Move all blame entries from list *source that have a score smaller
2123
 * than score_min to the front of list *small.
2124
 * Returns a pointer to the link pointing to the old head of the small list.
2125
 */
2126

2127
static struct blame_entry **filter_small(struct blame_scoreboard *sb,
2128
					 struct blame_entry **small,
2129
					 struct blame_entry **source,
2130
					 unsigned score_min)
2131
{
2132
	struct blame_entry *p = *source;
2133
	struct blame_entry *oldsmall = *small;
2134
	while (p) {
2135
		if (blame_entry_score(sb, p) <= score_min) {
2136
			*small = p;
2137
			small = &p->next;
2138
			p = *small;
2139
		} else {
2140
			*source = p;
2141
			source = &p->next;
2142
			p = *source;
2143
		}
2144
	}
2145
	*small = oldsmall;
2146
	*source = NULL;
2147
	return small;
2148
}
2149

2150
/*
2151
 * See if lines currently target is suspected for can be attributed to
2152
 * parent.
2153
 */
2154
static void find_move_in_parent(struct blame_scoreboard *sb,
2155
				struct blame_entry ***blamed,
2156
				struct blame_entry **toosmall,
2157
				struct blame_origin *target,
2158
				struct blame_origin *parent)
2159
{
2160
	struct blame_entry *e, split[3];
2161
	struct blame_entry *unblamed = target->suspects;
2162
	struct blame_entry *leftover = NULL;
2163
	mmfile_t file_p;
2164

2165
	if (!unblamed)
2166
		return; /* nothing remains for this target */
2167

2168
	fill_origin_blob(&sb->revs->diffopt, parent, &file_p,
2169
			 &sb->num_read_blob, 0);
2170
	if (!file_p.ptr)
2171
		return;
2172

2173
	/* At each iteration, unblamed has a NULL-terminated list of
2174
	 * entries that have not yet been tested for blame.  leftover
2175
	 * contains the reversed list of entries that have been tested
2176
	 * without being assignable to the parent.
2177
	 */
2178
	do {
2179
		struct blame_entry **unblamedtail = &unblamed;
2180
		struct blame_entry *next;
2181
		for (e = unblamed; e; e = next) {
2182
			next = e->next;
2183
			find_copy_in_blob(sb, e, parent, split, &file_p);
2184
			if (split[1].suspect &&
2185
			    sb->move_score < blame_entry_score(sb, &split[1])) {
2186
				split_blame(blamed, &unblamedtail, split, e);
2187
			} else {
2188
				e->next = leftover;
2189
				leftover = e;
2190
			}
2191
			decref_split(split);
2192
		}
2193
		*unblamedtail = NULL;
2194
		toosmall = filter_small(sb, toosmall, &unblamed, sb->move_score);
2195
	} while (unblamed);
2196
	target->suspects = reverse_blame(leftover, NULL);
2197
}
2198

2199
struct blame_list {
2200
	struct blame_entry *ent;
2201
	struct blame_entry split[3];
2202
};
2203

2204
/*
2205
 * Count the number of entries the target is suspected for,
2206
 * and prepare a list of entry and the best split.
2207
 */
2208
static struct blame_list *setup_blame_list(struct blame_entry *unblamed,
2209
					   int *num_ents_p)
2210
{
2211
	struct blame_entry *e;
2212
	int num_ents, i;
2213
	struct blame_list *blame_list = NULL;
2214

2215
	for (e = unblamed, num_ents = 0; e; e = e->next)
2216
		num_ents++;
2217
	if (num_ents) {
2218
		CALLOC_ARRAY(blame_list, num_ents);
2219
		for (e = unblamed, i = 0; e; e = e->next)
2220
			blame_list[i++].ent = e;
2221
	}
2222
	*num_ents_p = num_ents;
2223
	return blame_list;
2224
}
2225

2226
/*
2227
 * For lines target is suspected for, see if we can find code movement
2228
 * across file boundary from the parent commit.  porigin is the path
2229
 * in the parent we already tried.
2230
 */
2231
static void find_copy_in_parent(struct blame_scoreboard *sb,
2232
				struct blame_entry ***blamed,
2233
				struct blame_entry **toosmall,
2234
				struct blame_origin *target,
2235
				struct commit *parent,
2236
				struct blame_origin *porigin,
2237
				int opt)
2238
{
2239
	struct diff_options diff_opts;
2240
	int i, j;
2241
	struct blame_list *blame_list;
2242
	int num_ents;
2243
	struct blame_entry *unblamed = target->suspects;
2244
	struct blame_entry *leftover = NULL;
2245

2246
	if (!unblamed)
2247
		return; /* nothing remains for this target */
2248

2249
	repo_diff_setup(sb->repo, &diff_opts);
2250
	diff_opts.flags.recursive = 1;
2251
	diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;
2252

2253
	diff_setup_done(&diff_opts);
2254

2255
	/* Try "find copies harder" on new path if requested;
2256
	 * we do not want to use diffcore_rename() actually to
2257
	 * match things up; find_copies_harder is set only to
2258
	 * force diff_tree_oid() to feed all filepairs to diff_queue,
2259
	 * and this code needs to be after diff_setup_done(), which
2260
	 * usually makes find-copies-harder imply copy detection.
2261
	 */
2262
	if ((opt & PICKAXE_BLAME_COPY_HARDEST)
2263
	    || ((opt & PICKAXE_BLAME_COPY_HARDER)
2264
		&& (!porigin || strcmp(target->path, porigin->path))))
2265
		diff_opts.flags.find_copies_harder = 1;
2266

2267
	if (is_null_oid(&target->commit->object.oid))
2268
		do_diff_cache(get_commit_tree_oid(parent), &diff_opts);
2269
	else
2270
		diff_tree_oid(get_commit_tree_oid(parent),
2271
			      get_commit_tree_oid(target->commit),
2272
			      "", &diff_opts);
2273

2274
	if (!diff_opts.flags.find_copies_harder)
2275
		diffcore_std(&diff_opts);
2276

2277
	do {
2278
		struct blame_entry **unblamedtail = &unblamed;
2279
		blame_list = setup_blame_list(unblamed, &num_ents);
2280

2281
		for (i = 0; i < diff_queued_diff.nr; i++) {
2282
			struct diff_filepair *p = diff_queued_diff.queue[i];
2283
			struct blame_origin *norigin;
2284
			mmfile_t file_p;
2285
			struct blame_entry potential[3];
2286

2287
			if (!DIFF_FILE_VALID(p->one))
2288
				continue; /* does not exist in parent */
2289
			if (S_ISGITLINK(p->one->mode))
2290
				continue; /* ignore git links */
2291
			if (porigin && !strcmp(p->one->path, porigin->path))
2292
				/* find_move already dealt with this path */
2293
				continue;
2294

2295
			norigin = get_origin(parent, p->one->path);
2296
			oidcpy(&norigin->blob_oid, &p->one->oid);
2297
			norigin->mode = p->one->mode;
2298
			fill_origin_blob(&sb->revs->diffopt, norigin, &file_p,
2299
					 &sb->num_read_blob, 0);
2300
			if (!file_p.ptr)
2301
				continue;
2302

2303
			for (j = 0; j < num_ents; j++) {
2304
				find_copy_in_blob(sb, blame_list[j].ent,
2305
						  norigin, potential, &file_p);
2306
				copy_split_if_better(sb, blame_list[j].split,
2307
						     potential);
2308
				decref_split(potential);
2309
			}
2310
			blame_origin_decref(norigin);
2311
		}
2312

2313
		for (j = 0; j < num_ents; j++) {
2314
			struct blame_entry *split = blame_list[j].split;
2315
			if (split[1].suspect &&
2316
			    sb->copy_score < blame_entry_score(sb, &split[1])) {
2317
				split_blame(blamed, &unblamedtail, split,
2318
					    blame_list[j].ent);
2319
			} else {
2320
				blame_list[j].ent->next = leftover;
2321
				leftover = blame_list[j].ent;
2322
			}
2323
			decref_split(split);
2324
		}
2325
		free(blame_list);
2326
		*unblamedtail = NULL;
2327
		toosmall = filter_small(sb, toosmall, &unblamed, sb->copy_score);
2328
	} while (unblamed);
2329
	target->suspects = reverse_blame(leftover, NULL);
2330
	diff_flush(&diff_opts);
2331
}
2332

2333
/*
2334
 * The blobs of origin and porigin exactly match, so everything
2335
 * origin is suspected for can be blamed on the parent.
2336
 */
2337
static void pass_whole_blame(struct blame_scoreboard *sb,
2338
			     struct blame_origin *origin, struct blame_origin *porigin)
2339
{
2340
	struct blame_entry *e, *suspects;
2341

2342
	if (!porigin->file.ptr && origin->file.ptr) {
2343
		/* Steal its file */
2344
		porigin->file = origin->file;
2345
		origin->file.ptr = NULL;
2346
	}
2347
	suspects = origin->suspects;
2348
	origin->suspects = NULL;
2349
	for (e = suspects; e; e = e->next) {
2350
		blame_origin_incref(porigin);
2351
		blame_origin_decref(e->suspect);
2352
		e->suspect = porigin;
2353
	}
2354
	queue_blames(sb, porigin, suspects);
2355
}
2356

2357
/*
2358
 * We pass blame from the current commit to its parents.  We keep saying
2359
 * "parent" (and "porigin"), but what we mean is to find scapegoat to
2360
 * exonerate ourselves.
2361
 */
2362
static struct commit_list *first_scapegoat(struct rev_info *revs, struct commit *commit,
2363
					int reverse)
2364
{
2365
	if (!reverse) {
2366
		if (revs->first_parent_only &&
2367
		    commit->parents &&
2368
		    commit->parents->next) {
2369
			free_commit_list(commit->parents->next);
2370
			commit->parents->next = NULL;
2371
		}
2372
		return commit->parents;
2373
	}
2374
	return lookup_decoration(&revs->children, &commit->object);
2375
}
2376

2377
static int num_scapegoats(struct rev_info *revs, struct commit *commit, int reverse)
2378
{
2379
	struct commit_list *l = first_scapegoat(revs, commit, reverse);
2380
	return commit_list_count(l);
2381
}
2382

2383
/* Distribute collected unsorted blames to the respected sorted lists
2384
 * in the various origins.
2385
 */
2386
static void distribute_blame(struct blame_scoreboard *sb, struct blame_entry *blamed)
2387
{
2388
	sort_blame_entries(&blamed, compare_blame_suspect);
2389
	while (blamed)
2390
	{
2391
		struct blame_origin *porigin = blamed->suspect;
2392
		struct blame_entry *suspects = NULL;
2393
		do {
2394
			struct blame_entry *next = blamed->next;
2395
			blamed->next = suspects;
2396
			suspects = blamed;
2397
			blamed = next;
2398
		} while (blamed && blamed->suspect == porigin);
2399
		suspects = reverse_blame(suspects, NULL);
2400
		queue_blames(sb, porigin, suspects);
2401
	}
2402
}
2403

2404
#define MAXSG 16
2405

2406
typedef struct blame_origin *(*blame_find_alg)(struct repository *,
2407
					       struct commit *,
2408
					       struct blame_origin *,
2409
					       struct blame_bloom_data *);
2410

2411
static void pass_blame(struct blame_scoreboard *sb, struct blame_origin *origin, int opt)
2412
{
2413
	struct rev_info *revs = sb->revs;
2414
	int i, pass, num_sg;
2415
	struct commit *commit = origin->commit;
2416
	struct commit_list *sg;
2417
	struct blame_origin *sg_buf[MAXSG];
2418
	struct blame_origin *porigin, **sg_origin = sg_buf;
2419
	struct blame_entry *toosmall = NULL;
2420
	struct blame_entry *blames, **blametail = &blames;
2421

2422
	num_sg = num_scapegoats(revs, commit, sb->reverse);
2423
	if (!num_sg)
2424
		goto finish;
2425
	else if (num_sg < ARRAY_SIZE(sg_buf))
2426
		memset(sg_buf, 0, sizeof(sg_buf));
2427
	else
2428
		CALLOC_ARRAY(sg_origin, num_sg);
2429

2430
	/*
2431
	 * The first pass looks for unrenamed path to optimize for
2432
	 * common cases, then we look for renames in the second pass.
2433
	 */
2434
	for (pass = 0; pass < 2 - sb->no_whole_file_rename; pass++) {
2435
		blame_find_alg find = pass ? find_rename : find_origin;
2436

2437
		for (i = 0, sg = first_scapegoat(revs, commit, sb->reverse);
2438
		     i < num_sg && sg;
2439
		     sg = sg->next, i++) {
2440
			struct commit *p = sg->item;
2441
			int j, same;
2442

2443
			if (sg_origin[i])
2444
				continue;
2445
			if (repo_parse_commit(the_repository, p))
2446
				continue;
2447
			porigin = find(sb->repo, p, origin, sb->bloom_data);
2448
			if (!porigin)
2449
				continue;
2450
			if (oideq(&porigin->blob_oid, &origin->blob_oid)) {
2451
				pass_whole_blame(sb, origin, porigin);
2452
				blame_origin_decref(porigin);
2453
				goto finish;
2454
			}
2455
			for (j = same = 0; j < i; j++)
2456
				if (sg_origin[j] &&
2457
				    oideq(&sg_origin[j]->blob_oid, &porigin->blob_oid)) {
2458
					same = 1;
2459
					break;
2460
				}
2461
			if (!same)
2462
				sg_origin[i] = porigin;
2463
			else
2464
				blame_origin_decref(porigin);
2465
		}
2466
	}
2467

2468
	sb->num_commits++;
2469
	for (i = 0, sg = first_scapegoat(revs, commit, sb->reverse);
2470
	     i < num_sg && sg;
2471
	     sg = sg->next, i++) {
2472
		struct blame_origin *porigin = sg_origin[i];
2473
		if (!porigin)
2474
			continue;
2475
		if (!origin->previous) {
2476
			blame_origin_incref(porigin);
2477
			origin->previous = porigin;
2478
		}
2479
		pass_blame_to_parent(sb, origin, porigin, 0);
2480
		if (!origin->suspects)
2481
			goto finish;
2482
	}
2483

2484
	/*
2485
	 * Pass remaining suspects for ignored commits to their parents.
2486
	 */
2487
	if (oidset_contains(&sb->ignore_list, &commit->object.oid)) {
2488
		for (i = 0, sg = first_scapegoat(revs, commit, sb->reverse);
2489
		     i < num_sg && sg;
2490
		     sg = sg->next, i++) {
2491
			struct blame_origin *porigin = sg_origin[i];
2492

2493
			if (!porigin)
2494
				continue;
2495
			pass_blame_to_parent(sb, origin, porigin, 1);
2496
			/*
2497
			 * Preemptively drop porigin so we can refresh the
2498
			 * fingerprints if we use the parent again, which can
2499
			 * occur if you ignore back-to-back commits.
2500
			 */
2501
			drop_origin_blob(porigin);
2502
			if (!origin->suspects)
2503
				goto finish;
2504
		}
2505
	}
2506

2507
	/*
2508
	 * Optionally find moves in parents' files.
2509
	 */
2510
	if (opt & PICKAXE_BLAME_MOVE) {
2511
		filter_small(sb, &toosmall, &origin->suspects, sb->move_score);
2512
		if (origin->suspects) {
2513
			for (i = 0, sg = first_scapegoat(revs, commit, sb->reverse);
2514
			     i < num_sg && sg;
2515
			     sg = sg->next, i++) {
2516
				struct blame_origin *porigin = sg_origin[i];
2517
				if (!porigin)
2518
					continue;
2519
				find_move_in_parent(sb, &blametail, &toosmall, origin, porigin);
2520
				if (!origin->suspects)
2521
					break;
2522
			}
2523
		}
2524
	}
2525

2526
	/*
2527
	 * Optionally find copies from parents' files.
2528
	 */
2529
	if (opt & PICKAXE_BLAME_COPY) {
2530
		if (sb->copy_score > sb->move_score)
2531
			filter_small(sb, &toosmall, &origin->suspects, sb->copy_score);
2532
		else if (sb->copy_score < sb->move_score) {
2533
			origin->suspects = blame_merge(origin->suspects, toosmall);
2534
			toosmall = NULL;
2535
			filter_small(sb, &toosmall, &origin->suspects, sb->copy_score);
2536
		}
2537
		if (!origin->suspects)
2538
			goto finish;
2539

2540
		for (i = 0, sg = first_scapegoat(revs, commit, sb->reverse);
2541
		     i < num_sg && sg;
2542
		     sg = sg->next, i++) {
2543
			struct blame_origin *porigin = sg_origin[i];
2544
			find_copy_in_parent(sb, &blametail, &toosmall,
2545
					    origin, sg->item, porigin, opt);
2546
			if (!origin->suspects)
2547
				goto finish;
2548
		}
2549
	}
2550

2551
finish:
2552
	*blametail = NULL;
2553
	distribute_blame(sb, blames);
2554
	/*
2555
	 * prepend toosmall to origin->suspects
2556
	 *
2557
	 * There is no point in sorting: this ends up on a big
2558
	 * unsorted list in the caller anyway.
2559
	 */
2560
	if (toosmall) {
2561
		struct blame_entry **tail = &toosmall;
2562
		while (*tail)
2563
			tail = &(*tail)->next;
2564
		*tail = origin->suspects;
2565
		origin->suspects = toosmall;
2566
	}
2567
	for (i = 0; i < num_sg; i++) {
2568
		if (sg_origin[i]) {
2569
			if (!sg_origin[i]->suspects)
2570
				drop_origin_blob(sg_origin[i]);
2571
			blame_origin_decref(sg_origin[i]);
2572
		}
2573
	}
2574
	drop_origin_blob(origin);
2575
	if (sg_buf != sg_origin)
2576
		free(sg_origin);
2577
}
2578

2579
/*
2580
 * The main loop -- while we have blobs with lines whose true origin
2581
 * is still unknown, pick one blob, and allow its lines to pass blames
2582
 * to its parents. */
2583
void assign_blame(struct blame_scoreboard *sb, int opt)
2584
{
2585
	struct rev_info *revs = sb->revs;
2586
	struct commit *commit = prio_queue_get(&sb->commits);
2587

2588
	while (commit) {
2589
		struct blame_entry *ent;
2590
		struct blame_origin *suspect = get_blame_suspects(commit);
2591

2592
		/* find one suspect to break down */
2593
		while (suspect && !suspect->suspects)
2594
			suspect = suspect->next;
2595

2596
		if (!suspect) {
2597
			commit = prio_queue_get(&sb->commits);
2598
			continue;
2599
		}
2600

2601
		assert(commit == suspect->commit);
2602

2603
		/*
2604
		 * We will use this suspect later in the loop,
2605
		 * so hold onto it in the meantime.
2606
		 */
2607
		blame_origin_incref(suspect);
2608
		repo_parse_commit(the_repository, commit);
2609
		if (sb->reverse ||
2610
		    (!(commit->object.flags & UNINTERESTING) &&
2611
		     !(revs->max_age != -1 && commit->date < revs->max_age)))
2612
			pass_blame(sb, suspect, opt);
2613
		else {
2614
			commit->object.flags |= UNINTERESTING;
2615
			if (commit->object.parsed)
2616
				mark_parents_uninteresting(sb->revs, commit);
2617
		}
2618
		/* treat root commit as boundary */
2619
		if (!commit->parents && !sb->show_root)
2620
			commit->object.flags |= UNINTERESTING;
2621

2622
		/* Take responsibility for the remaining entries */
2623
		ent = suspect->suspects;
2624
		if (ent) {
2625
			suspect->guilty = 1;
2626
			for (;;) {
2627
				struct blame_entry *next = ent->next;
2628
				if (sb->found_guilty_entry)
2629
					sb->found_guilty_entry(ent, sb->found_guilty_entry_data);
2630
				if (next) {
2631
					ent = next;
2632
					continue;
2633
				}
2634
				ent->next = sb->ent;
2635
				sb->ent = suspect->suspects;
2636
				suspect->suspects = NULL;
2637
				break;
2638
			}
2639
		}
2640
		blame_origin_decref(suspect);
2641

2642
		if (sb->debug) /* sanity */
2643
			sanity_check_refcnt(sb);
2644
	}
2645
}
2646

2647
/*
2648
 * To allow quick access to the contents of nth line in the
2649
 * final image, prepare an index in the scoreboard.
2650
 */
2651
static int prepare_lines(struct blame_scoreboard *sb)
2652
{
2653
	sb->num_lines = find_line_starts(&sb->lineno, sb->final_buf,
2654
					 sb->final_buf_size);
2655
	return sb->num_lines;
2656
}
2657

2658
static struct commit *find_single_final(struct rev_info *revs,
2659
					const char **name_p)
2660
{
2661
	int i;
2662
	struct commit *found = NULL;
2663
	const char *name = NULL;
2664

2665
	for (i = 0; i < revs->pending.nr; i++) {
2666
		struct object *obj = revs->pending.objects[i].item;
2667
		if (obj->flags & UNINTERESTING)
2668
			continue;
2669
		obj = deref_tag(revs->repo, obj, NULL, 0);
2670
		if (!obj || obj->type != OBJ_COMMIT)
2671
			die("Non commit %s?", revs->pending.objects[i].name);
2672
		if (found)
2673
			die("More than one commit to dig from %s and %s?",
2674
			    revs->pending.objects[i].name, name);
2675
		found = (struct commit *)obj;
2676
		name = revs->pending.objects[i].name;
2677
	}
2678
	if (name_p)
2679
		*name_p = xstrdup_or_null(name);
2680
	return found;
2681
}
2682

2683
static struct commit *dwim_reverse_initial(struct rev_info *revs,
2684
					   const char **name_p)
2685
{
2686
	/*
2687
	 * DWIM "git blame --reverse ONE -- PATH" as
2688
	 * "git blame --reverse ONE..HEAD -- PATH" but only do so
2689
	 * when it makes sense.
2690
	 */
2691
	struct object *obj;
2692
	struct commit *head_commit;
2693
	struct object_id head_oid;
2694

2695
	if (revs->pending.nr != 1)
2696
		return NULL;
2697

2698
	/* Is that sole rev a committish? */
2699
	obj = revs->pending.objects[0].item;
2700
	obj = deref_tag(revs->repo, obj, NULL, 0);
2701
	if (!obj || obj->type != OBJ_COMMIT)
2702
		return NULL;
2703

2704
	/* Do we have HEAD? */
2705
	if (!refs_resolve_ref_unsafe(get_main_ref_store(the_repository), "HEAD", RESOLVE_REF_READING, &head_oid, NULL))
2706
		return NULL;
2707
	head_commit = lookup_commit_reference_gently(revs->repo,
2708
						     &head_oid, 1);
2709
	if (!head_commit)
2710
		return NULL;
2711

2712
	/* Turn "ONE" into "ONE..HEAD" then */
2713
	obj->flags |= UNINTERESTING;
2714
	add_pending_object(revs, &head_commit->object, "HEAD");
2715

2716
	if (name_p)
2717
		*name_p = revs->pending.objects[0].name;
2718
	return (struct commit *)obj;
2719
}
2720

2721
static struct commit *find_single_initial(struct rev_info *revs,
2722
					  const char **name_p)
2723
{
2724
	int i;
2725
	struct commit *found = NULL;
2726
	const char *name = NULL;
2727

2728
	/*
2729
	 * There must be one and only one negative commit, and it must be
2730
	 * the boundary.
2731
	 */
2732
	for (i = 0; i < revs->pending.nr; i++) {
2733
		struct object *obj = revs->pending.objects[i].item;
2734
		if (!(obj->flags & UNINTERESTING))
2735
			continue;
2736
		obj = deref_tag(revs->repo, obj, NULL, 0);
2737
		if (!obj || obj->type != OBJ_COMMIT)
2738
			die("Non commit %s?", revs->pending.objects[i].name);
2739
		if (found)
2740
			die("More than one commit to dig up from, %s and %s?",
2741
			    revs->pending.objects[i].name, name);
2742
		found = (struct commit *) obj;
2743
		name = revs->pending.objects[i].name;
2744
	}
2745

2746
	if (!name)
2747
		found = dwim_reverse_initial(revs, &name);
2748
	if (!name)
2749
		die("No commit to dig up from?");
2750

2751
	if (name_p)
2752
		*name_p = xstrdup(name);
2753
	return found;
2754
}
2755

2756
void init_scoreboard(struct blame_scoreboard *sb)
2757
{
2758
	memset(sb, 0, sizeof(struct blame_scoreboard));
2759
	sb->move_score = BLAME_DEFAULT_MOVE_SCORE;
2760
	sb->copy_score = BLAME_DEFAULT_COPY_SCORE;
2761
}
2762

2763
void setup_scoreboard(struct blame_scoreboard *sb,
2764
		      struct blame_origin **orig)
2765
{
2766
	const char *final_commit_name = NULL;
2767
	struct blame_origin *o;
2768
	struct commit *final_commit = NULL;
2769
	enum object_type type;
2770

2771
	init_blame_suspects(&blame_suspects);
2772

2773
	if (sb->reverse && sb->contents_from)
2774
		die(_("--contents and --reverse do not blend well."));
2775

2776
	if (!sb->repo)
2777
		BUG("repo is NULL");
2778

2779
	if (!sb->reverse) {
2780
		sb->final = find_single_final(sb->revs, &final_commit_name);
2781
		sb->commits.compare = compare_commits_by_commit_date;
2782
	} else {
2783
		sb->final = find_single_initial(sb->revs, &final_commit_name);
2784
		sb->commits.compare = compare_commits_by_reverse_commit_date;
2785
	}
2786

2787
	if (sb->reverse && sb->revs->first_parent_only)
2788
		sb->revs->children.name = NULL;
2789

2790
	if (sb->contents_from || !sb->final) {
2791
		struct object_id head_oid, *parent_oid;
2792

2793
		/*
2794
		 * Build a fake commit at the top of the history, when
2795
		 * (1) "git blame [^A] --path", i.e. with no positive end
2796
		 *     of the history range, in which case we build such
2797
		 *     a fake commit on top of the HEAD to blame in-tree
2798
		 *     modifications.
2799
		 * (2) "git blame --contents=file [A] -- path", with or
2800
		 *     without positive end of the history range but with
2801
		 *     --contents, in which case we pretend that there is
2802
		 *     a fake commit on top of the positive end (defaulting to
2803
		 *     HEAD) that has the given contents in the path.
2804
		 */
2805
		if (sb->final) {
2806
			parent_oid = &sb->final->object.oid;
2807
		} else {
2808
			if (!refs_resolve_ref_unsafe(get_main_ref_store(the_repository), "HEAD", RESOLVE_REF_READING, &head_oid, NULL))
2809
				die("no such ref: HEAD");
2810
			parent_oid = &head_oid;
2811
		}
2812

2813
		if (!sb->contents_from)
2814
			setup_work_tree();
2815

2816
		sb->final = fake_working_tree_commit(sb->repo,
2817
						     &sb->revs->diffopt,
2818
						     sb->path, sb->contents_from,
2819
						     parent_oid);
2820
		add_pending_object(sb->revs, &(sb->final->object), ":");
2821
	}
2822

2823
	if (sb->reverse && sb->revs->first_parent_only) {
2824
		final_commit = find_single_final(sb->revs, NULL);
2825
		if (!final_commit)
2826
			die(_("--reverse and --first-parent together require specified latest commit"));
2827
	}
2828

2829
	/*
2830
	 * If we have bottom, this will mark the ancestors of the
2831
	 * bottom commits we would reach while traversing as
2832
	 * uninteresting.
2833
	 */
2834
	if (prepare_revision_walk(sb->revs))
2835
		die(_("revision walk setup failed"));
2836

2837
	if (sb->reverse && sb->revs->first_parent_only) {
2838
		struct commit *c = final_commit;
2839

2840
		sb->revs->children.name = "children";
2841
		while (c->parents &&
2842
		       !oideq(&c->object.oid, &sb->final->object.oid)) {
2843
			struct commit_list *l = xcalloc(1, sizeof(*l));
2844

2845
			l->item = c;
2846
			if (add_decoration(&sb->revs->children,
2847
					   &c->parents->item->object, l))
2848
				BUG("not unique item in first-parent chain");
2849
			c = c->parents->item;
2850
		}
2851

2852
		if (!oideq(&c->object.oid, &sb->final->object.oid))
2853
			die(_("--reverse --first-parent together require range along first-parent chain"));
2854
	}
2855

2856
	if (is_null_oid(&sb->final->object.oid)) {
2857
		o = get_blame_suspects(sb->final);
2858
		sb->final_buf = xmemdupz(o->file.ptr, o->file.size);
2859
		sb->final_buf_size = o->file.size;
2860
	}
2861
	else {
2862
		o = get_origin(sb->final, sb->path);
2863
		if (fill_blob_sha1_and_mode(sb->repo, o))
2864
			die(_("no such path %s in %s"), sb->path, final_commit_name);
2865

2866
		if (sb->revs->diffopt.flags.allow_textconv &&
2867
		    textconv_object(sb->repo, sb->path, o->mode, &o->blob_oid, 1, (char **) &sb->final_buf,
2868
				    &sb->final_buf_size))
2869
			;
2870
		else
2871
			sb->final_buf = repo_read_object_file(the_repository,
2872
							      &o->blob_oid,
2873
							      &type,
2874
							      &sb->final_buf_size);
2875

2876
		if (!sb->final_buf)
2877
			die(_("cannot read blob %s for path %s"),
2878
			    oid_to_hex(&o->blob_oid),
2879
			    sb->path);
2880
	}
2881
	sb->num_read_blob++;
2882
	prepare_lines(sb);
2883

2884
	if (orig)
2885
		*orig = o;
2886

2887
	free((char *)final_commit_name);
2888
}
2889

2890

2891

2892
struct blame_entry *blame_entry_prepend(struct blame_entry *head,
2893
					long start, long end,
2894
					struct blame_origin *o)
2895
{
2896
	struct blame_entry *new_head = xcalloc(1, sizeof(struct blame_entry));
2897
	new_head->lno = start;
2898
	new_head->num_lines = end - start;
2899
	new_head->suspect = o;
2900
	new_head->s_lno = start;
2901
	new_head->next = head;
2902
	blame_origin_incref(o);
2903
	return new_head;
2904
}
2905

2906
void setup_blame_bloom_data(struct blame_scoreboard *sb)
2907
{
2908
	struct blame_bloom_data *bd;
2909
	struct bloom_filter_settings *bs;
2910

2911
	if (!sb->repo->objects->commit_graph)
2912
		return;
2913

2914
	bs = get_bloom_filter_settings(sb->repo);
2915
	if (!bs)
2916
		return;
2917

2918
	bd = xmalloc(sizeof(struct blame_bloom_data));
2919

2920
	bd->settings = bs;
2921

2922
	bd->alloc = 4;
2923
	bd->nr = 0;
2924
	ALLOC_ARRAY(bd->keys, bd->alloc);
2925

2926
	add_bloom_key(bd, sb->path);
2927

2928
	sb->bloom_data = bd;
2929
}
2930

2931
void cleanup_scoreboard(struct blame_scoreboard *sb)
2932
{
2933
	free(sb->lineno);
2934
	clear_prio_queue(&sb->commits);
2935
	oidset_clear(&sb->ignore_list);
2936

2937
	if (sb->bloom_data) {
2938
		int i;
2939
		for (i = 0; i < sb->bloom_data->nr; i++) {
2940
			free(sb->bloom_data->keys[i]->hashes);
2941
			free(sb->bloom_data->keys[i]);
2942
		}
2943
		free(sb->bloom_data->keys);
2944
		FREE_AND_NULL(sb->bloom_data);
2945

2946
		trace2_data_intmax("blame", sb->repo,
2947
				   "bloom/queries", bloom_count_queries);
2948
		trace2_data_intmax("blame", sb->repo,
2949
				   "bloom/response-no", bloom_count_no);
2950
	}
2951
}
2952