Merge branch 'so/combine-diff-simplify'
[git] / blame.c
1 #include "cache.h"
2 #include "refs.h"
3 #include "object-store.h"
4 #include "cache-tree.h"
5 #include "mergesort.h"
6 #include "diff.h"
7 #include "diffcore.h"
8 #include "tag.h"
9 #include "blame.h"
10 #include "alloc.h"
11 #include "commit-slab.h"
12 #include "bloom.h"
13 #include "commit-graph.h"
14
15 define_commit_slab(blame_suspects, struct blame_origin *);
16 static struct blame_suspects blame_suspects;
17
18 struct blame_origin *get_blame_suspects(struct commit *commit)
19 {
20         struct blame_origin **result;
21
22         result = blame_suspects_peek(&blame_suspects, commit);
23
24         return result ? *result : NULL;
25 }
26
27 static void set_blame_suspects(struct commit *commit, struct blame_origin *origin)
28 {
29         *blame_suspects_at(&blame_suspects, commit) = origin;
30 }
31
32 void blame_origin_decref(struct blame_origin *o)
33 {
34         if (o && --o->refcnt <= 0) {
35                 struct blame_origin *p, *l = NULL;
36                 if (o->previous)
37                         blame_origin_decref(o->previous);
38                 free(o->file.ptr);
39                 /* Should be present exactly once in commit chain */
40                 for (p = get_blame_suspects(o->commit); p; l = p, p = p->next) {
41                         if (p == o) {
42                                 if (l)
43                                         l->next = p->next;
44                                 else
45                                         set_blame_suspects(o->commit, p->next);
46                                 free(o);
47                                 return;
48                         }
49                 }
50                 die("internal error in blame_origin_decref");
51         }
52 }
53
54 /*
55  * Given a commit and a path in it, create a new origin structure.
56  * The callers that add blame to the scoreboard should use
57  * get_origin() to obtain shared, refcounted copy instead of calling
58  * this function directly.
59  */
60 static struct blame_origin *make_origin(struct commit *commit, const char *path)
61 {
62         struct blame_origin *o;
63         FLEX_ALLOC_STR(o, path, path);
64         o->commit = commit;
65         o->refcnt = 1;
66         o->next = get_blame_suspects(commit);
67         set_blame_suspects(commit, o);
68         return o;
69 }
70
71 /*
72  * Locate an existing origin or create a new one.
73  * This moves the origin to front position in the commit util list.
74  */
75 static struct blame_origin *get_origin(struct commit *commit, const char *path)
76 {
77         struct blame_origin *o, *l;
78
79         for (o = get_blame_suspects(commit), l = NULL; o; l = o, o = o->next) {
80                 if (!strcmp(o->path, path)) {
81                         /* bump to front */
82                         if (l) {
83                                 l->next = o->next;
84                                 o->next = get_blame_suspects(commit);
85                                 set_blame_suspects(commit, o);
86                         }
87                         return blame_origin_incref(o);
88                 }
89         }
90         return make_origin(commit, path);
91 }
92
93
94
95 static void verify_working_tree_path(struct repository *r,
96                                      struct commit *work_tree, const char *path)
97 {
98         struct commit_list *parents;
99         int pos;
100
101         for (parents = work_tree->parents; parents; parents = parents->next) {
102                 const struct object_id *commit_oid = &parents->item->object.oid;
103                 struct object_id blob_oid;
104                 unsigned short mode;
105
106                 if (!get_tree_entry(r, commit_oid, path, &blob_oid, &mode) &&
107                     oid_object_info(r, &blob_oid, NULL) == OBJ_BLOB)
108                         return;
109         }
110
111         pos = index_name_pos(r->index, path, strlen(path));
112         if (pos >= 0)
113                 ; /* path is in the index */
114         else if (-1 - pos < r->index->cache_nr &&
115                  !strcmp(r->index->cache[-1 - pos]->name, path))
116                 ; /* path is in the index, unmerged */
117         else
118                 die("no such path '%s' in HEAD", path);
119 }
120
121 static struct commit_list **append_parent(struct repository *r,
122                                           struct commit_list **tail,
123                                           const struct object_id *oid)
124 {
125         struct commit *parent;
126
127         parent = lookup_commit_reference(r, oid);
128         if (!parent)
129                 die("no such commit %s", oid_to_hex(oid));
130         return &commit_list_insert(parent, tail)->next;
131 }
132
133 static void append_merge_parents(struct repository *r,
134                                  struct commit_list **tail)
135 {
136         int merge_head;
137         struct strbuf line = STRBUF_INIT;
138
139         merge_head = open(git_path_merge_head(r), O_RDONLY);
140         if (merge_head < 0) {
141                 if (errno == ENOENT)
142                         return;
143                 die("cannot open '%s' for reading",
144                     git_path_merge_head(r));
145         }
146
147         while (!strbuf_getwholeline_fd(&line, merge_head, '\n')) {
148                 struct object_id oid;
149                 if (get_oid_hex(line.buf, &oid))
150                         die("unknown line in '%s': %s",
151                             git_path_merge_head(r), line.buf);
152                 tail = append_parent(r, tail, &oid);
153         }
154         close(merge_head);
155         strbuf_release(&line);
156 }
157
158 /*
159  * This isn't as simple as passing sb->buf and sb->len, because we
160  * want to transfer ownership of the buffer to the commit (so we
161  * must use detach).
162  */
163 static void set_commit_buffer_from_strbuf(struct repository *r,
164                                           struct commit *c,
165                                           struct strbuf *sb)
166 {
167         size_t len;
168         void *buf = strbuf_detach(sb, &len);
169         set_commit_buffer(r, c, buf, len);
170 }
171
172 /*
173  * Prepare a dummy commit that represents the work tree (or staged) item.
174  * Note that annotating work tree item never works in the reverse.
175  */
176 static struct commit *fake_working_tree_commit(struct repository *r,
177                                                struct diff_options *opt,
178                                                const char *path,
179                                                const char *contents_from)
180 {
181         struct commit *commit;
182         struct blame_origin *origin;
183         struct commit_list **parent_tail, *parent;
184         struct object_id head_oid;
185         struct strbuf buf = STRBUF_INIT;
186         const char *ident;
187         time_t now;
188         int len;
189         struct cache_entry *ce;
190         unsigned mode;
191         struct strbuf msg = STRBUF_INIT;
192
193         repo_read_index(r);
194         time(&now);
195         commit = alloc_commit_node(r);
196         commit->object.parsed = 1;
197         commit->date = now;
198         parent_tail = &commit->parents;
199
200         if (!resolve_ref_unsafe("HEAD", RESOLVE_REF_READING, &head_oid, NULL))
201                 die("no such ref: HEAD");
202
203         parent_tail = append_parent(r, parent_tail, &head_oid);
204         append_merge_parents(r, parent_tail);
205         verify_working_tree_path(r, commit, path);
206
207         origin = make_origin(commit, path);
208
209         ident = fmt_ident("Not Committed Yet", "not.committed.yet",
210                         WANT_BLANK_IDENT, NULL, 0);
211         strbuf_addstr(&msg, "tree 0000000000000000000000000000000000000000\n");
212         for (parent = commit->parents; parent; parent = parent->next)
213                 strbuf_addf(&msg, "parent %s\n",
214                             oid_to_hex(&parent->item->object.oid));
215         strbuf_addf(&msg,
216                     "author %s\n"
217                     "committer %s\n\n"
218                     "Version of %s from %s\n",
219                     ident, ident, path,
220                     (!contents_from ? path :
221                      (!strcmp(contents_from, "-") ? "standard input" : contents_from)));
222         set_commit_buffer_from_strbuf(r, commit, &msg);
223
224         if (!contents_from || strcmp("-", contents_from)) {
225                 struct stat st;
226                 const char *read_from;
227                 char *buf_ptr;
228                 unsigned long buf_len;
229
230                 if (contents_from) {
231                         if (stat(contents_from, &st) < 0)
232                                 die_errno("Cannot stat '%s'", contents_from);
233                         read_from = contents_from;
234                 }
235                 else {
236                         if (lstat(path, &st) < 0)
237                                 die_errno("Cannot lstat '%s'", path);
238                         read_from = path;
239                 }
240                 mode = canon_mode(st.st_mode);
241
242                 switch (st.st_mode & S_IFMT) {
243                 case S_IFREG:
244                         if (opt->flags.allow_textconv &&
245                             textconv_object(r, read_from, mode, &null_oid, 0, &buf_ptr, &buf_len))
246                                 strbuf_attach(&buf, buf_ptr, buf_len, buf_len + 1);
247                         else if (strbuf_read_file(&buf, read_from, st.st_size) != st.st_size)
248                                 die_errno("cannot open or read '%s'", read_from);
249                         break;
250                 case S_IFLNK:
251                         if (strbuf_readlink(&buf, read_from, st.st_size) < 0)
252                                 die_errno("cannot readlink '%s'", read_from);
253                         break;
254                 default:
255                         die("unsupported file type %s", read_from);
256                 }
257         }
258         else {
259                 /* Reading from stdin */
260                 mode = 0;
261                 if (strbuf_read(&buf, 0, 0) < 0)
262                         die_errno("failed to read from stdin");
263         }
264         convert_to_git(r->index, path, buf.buf, buf.len, &buf, 0);
265         origin->file.ptr = buf.buf;
266         origin->file.size = buf.len;
267         pretend_object_file(buf.buf, buf.len, OBJ_BLOB, &origin->blob_oid);
268
269         /*
270          * Read the current index, replace the path entry with
271          * origin->blob_sha1 without mucking with its mode or type
272          * bits; we are not going to write this index out -- we just
273          * want to run "diff-index --cached".
274          */
275         discard_index(r->index);
276         repo_read_index(r);
277
278         len = strlen(path);
279         if (!mode) {
280                 int pos = index_name_pos(r->index, path, len);
281                 if (0 <= pos)
282                         mode = r->index->cache[pos]->ce_mode;
283                 else
284                         /* Let's not bother reading from HEAD tree */
285                         mode = S_IFREG | 0644;
286         }
287         ce = make_empty_cache_entry(r->index, len);
288         oidcpy(&ce->oid, &origin->blob_oid);
289         memcpy(ce->name, path, len);
290         ce->ce_flags = create_ce_flags(0);
291         ce->ce_namelen = len;
292         ce->ce_mode = create_ce_mode(mode);
293         add_index_entry(r->index, ce,
294                         ADD_CACHE_OK_TO_ADD | ADD_CACHE_OK_TO_REPLACE);
295
296         cache_tree_invalidate_path(r->index, path);
297
298         return commit;
299 }
300
301
302
303 static int diff_hunks(mmfile_t *file_a, mmfile_t *file_b,
304                       xdl_emit_hunk_consume_func_t hunk_func, void *cb_data, int xdl_opts)
305 {
306         xpparam_t xpp = {0};
307         xdemitconf_t xecfg = {0};
308         xdemitcb_t ecb = {NULL};
309
310         xpp.flags = xdl_opts;
311         xecfg.hunk_func = hunk_func;
312         ecb.priv = cb_data;
313         return xdi_diff(file_a, file_b, &xpp, &xecfg, &ecb);
314 }
315
316 static const char *get_next_line(const char *start, const char *end)
317 {
318         const char *nl = memchr(start, '\n', end - start);
319
320         return nl ? nl + 1 : end;
321 }
322
323 static int find_line_starts(int **line_starts, const char *buf,
324                             unsigned long len)
325 {
326         const char *end = buf + len;
327         const char *p;
328         int *lineno;
329         int num = 0;
330
331         for (p = buf; p < end; p = get_next_line(p, end))
332                 num++;
333
334         ALLOC_ARRAY(*line_starts, num + 1);
335         lineno = *line_starts;
336
337         for (p = buf; p < end; p = get_next_line(p, end))
338                 *lineno++ = p - buf;
339
340         *lineno = len;
341
342         return num;
343 }
344
345 struct fingerprint_entry;
346
347 /* A fingerprint is intended to loosely represent a string, such that two
348  * fingerprints can be quickly compared to give an indication of the similarity
349  * of the strings that they represent.
350  *
351  * A fingerprint is represented as a multiset of the lower-cased byte pairs in
352  * the string that it represents. Whitespace is added at each end of the
353  * string. Whitespace pairs are ignored. Whitespace is converted to '\0'.
354  * For example, the string "Darth   Radar" will be converted to the following
355  * fingerprint:
356  * {"\0d", "da", "da", "ar", "ar", "rt", "th", "h\0", "\0r", "ra", "ad", "r\0"}
357  *
358  * The similarity between two fingerprints is the size of the intersection of
359  * their multisets, including repeated elements. See fingerprint_similarity for
360  * examples.
361  *
362  * For ease of implementation, the fingerprint is implemented as a map
363  * of byte pairs to the count of that byte pair in the string, instead of
364  * allowing repeated elements in a set.
365  */
366 struct fingerprint {
367         struct hashmap map;
368         /* As we know the maximum number of entries in advance, it's
369          * convenient to store the entries in a single array instead of having
370          * the hashmap manage the memory.
371          */
372         struct fingerprint_entry *entries;
373 };
374
375 /* A byte pair in a fingerprint. Stores the number of times the byte pair
376  * occurs in the string that the fingerprint represents.
377  */
378 struct fingerprint_entry {
379         /* The hashmap entry - the hash represents the byte pair in its
380          * entirety so we don't need to store the byte pair separately.
381          */
382         struct hashmap_entry entry;
383         /* The number of times the byte pair occurs in the string that the
384          * fingerprint represents.
385          */
386         int count;
387 };
388
389 /* See `struct fingerprint` for an explanation of what a fingerprint is.
390  * \param result the fingerprint of the string is stored here. This must be
391  *               freed later using free_fingerprint.
392  * \param line_begin the start of the string
393  * \param line_end the end of the string
394  */
395 static void get_fingerprint(struct fingerprint *result,
396                             const char *line_begin,
397                             const char *line_end)
398 {
399         unsigned int hash, c0 = 0, c1;
400         const char *p;
401         int max_map_entry_count = 1 + line_end - line_begin;
402         struct fingerprint_entry *entry = xcalloc(max_map_entry_count,
403                 sizeof(struct fingerprint_entry));
404         struct fingerprint_entry *found_entry;
405
406         hashmap_init(&result->map, NULL, NULL, max_map_entry_count);
407         result->entries = entry;
408         for (p = line_begin; p <= line_end; ++p, c0 = c1) {
409                 /* Always terminate the string with whitespace.
410                  * Normalise whitespace to 0, and normalise letters to
411                  * lower case. This won't work for multibyte characters but at
412                  * worst will match some unrelated characters.
413                  */
414                 if ((p == line_end) || isspace(*p))
415                         c1 = 0;
416                 else
417                         c1 = tolower(*p);
418                 hash = c0 | (c1 << 8);
419                 /* Ignore whitespace pairs */
420                 if (hash == 0)
421                         continue;
422                 hashmap_entry_init(&entry->entry, hash);
423
424                 found_entry = hashmap_get_entry(&result->map, entry,
425                                                 /* member name */ entry, NULL);
426                 if (found_entry) {
427                         found_entry->count += 1;
428                 } else {
429                         entry->count = 1;
430                         hashmap_add(&result->map, &entry->entry);
431                         ++entry;
432                 }
433         }
434 }
435
436 static void free_fingerprint(struct fingerprint *f)
437 {
438         hashmap_free(&f->map);
439         free(f->entries);
440 }
441
442 /* Calculates the similarity between two fingerprints as the size of the
443  * intersection of their multisets, including repeated elements. See
444  * `struct fingerprint` for an explanation of the fingerprint representation.
445  * The similarity between "cat mat" and "father rather" is 2 because "at" is
446  * present twice in both strings while the similarity between "tim" and "mit"
447  * is 0.
448  */
449 static int fingerprint_similarity(struct fingerprint *a, struct fingerprint *b)
450 {
451         int intersection = 0;
452         struct hashmap_iter iter;
453         const struct fingerprint_entry *entry_a, *entry_b;
454
455         hashmap_for_each_entry(&b->map, &iter, entry_b,
456                                 entry /* member name */) {
457                 entry_a = hashmap_get_entry(&a->map, entry_b, entry, NULL);
458                 if (entry_a) {
459                         intersection += entry_a->count < entry_b->count ?
460                                         entry_a->count : entry_b->count;
461                 }
462         }
463         return intersection;
464 }
465
466 /* Subtracts byte-pair elements in B from A, modifying A in place.
467  */
468 static void fingerprint_subtract(struct fingerprint *a, struct fingerprint *b)
469 {
470         struct hashmap_iter iter;
471         struct fingerprint_entry *entry_a;
472         const struct fingerprint_entry *entry_b;
473
474         hashmap_iter_init(&b->map, &iter);
475
476         hashmap_for_each_entry(&b->map, &iter, entry_b,
477                                 entry /* member name */) {
478                 entry_a = hashmap_get_entry(&a->map, entry_b, entry, NULL);
479                 if (entry_a) {
480                         if (entry_a->count <= entry_b->count)
481                                 hashmap_remove(&a->map, &entry_b->entry, NULL);
482                         else
483                                 entry_a->count -= entry_b->count;
484                 }
485         }
486 }
487
488 /* Calculate fingerprints for a series of lines.
489  * Puts the fingerprints in the fingerprints array, which must have been
490  * preallocated to allow storing line_count elements.
491  */
492 static void get_line_fingerprints(struct fingerprint *fingerprints,
493                                   const char *content, const int *line_starts,
494                                   long first_line, long line_count)
495 {
496         int i;
497         const char *linestart, *lineend;
498
499         line_starts += first_line;
500         for (i = 0; i < line_count; ++i) {
501                 linestart = content + line_starts[i];
502                 lineend = content + line_starts[i + 1];
503                 get_fingerprint(fingerprints + i, linestart, lineend);
504         }
505 }
506
507 static void free_line_fingerprints(struct fingerprint *fingerprints,
508                                    int nr_fingerprints)
509 {
510         int i;
511
512         for (i = 0; i < nr_fingerprints; i++)
513                 free_fingerprint(&fingerprints[i]);
514 }
515
516 /* This contains the data necessary to linearly map a line number in one half
517  * of a diff chunk to the line in the other half of the diff chunk that is
518  * closest in terms of its position as a fraction of the length of the chunk.
519  */
520 struct line_number_mapping {
521         int destination_start, destination_length,
522                 source_start, source_length;
523 };
524
525 /* Given a line number in one range, offset and scale it to map it onto the
526  * other range.
527  * Essentially this mapping is a simple linear equation but the calculation is
528  * more complicated to allow performing it with integer operations.
529  * Another complication is that if a line could map onto many lines in the
530  * destination range then we want to choose the line at the center of those
531  * possibilities.
532  * Example: if the chunk is 2 lines long in A and 10 lines long in B then the
533  * first 5 lines in B will map onto the first line in the A chunk, while the
534  * last 5 lines will all map onto the second line in the A chunk.
535  * Example: if the chunk is 10 lines long in A and 2 lines long in B then line
536  * 0 in B will map onto line 2 in A, and line 1 in B will map onto line 7 in A.
537  */
538 static int map_line_number(int line_number,
539         const struct line_number_mapping *mapping)
540 {
541         return ((line_number - mapping->source_start) * 2 + 1) *
542                mapping->destination_length /
543                (mapping->source_length * 2) +
544                mapping->destination_start;
545 }
546
547 /* Get a pointer to the element storing the similarity between a line in A
548  * and a line in B.
549  *
550  * The similarities are stored in a 2-dimensional array. Each "row" in the
551  * array contains the similarities for a line in B. The similarities stored in
552  * a row are the similarities between the line in B and the nearby lines in A.
553  * To keep the length of each row the same, it is padded out with values of -1
554  * where the search range extends beyond the lines in A.
555  * For example, if max_search_distance_a is 2 and the two sides of a diff chunk
556  * look like this:
557  * a | m
558  * b | n
559  * c | o
560  * d | p
561  * e | q
562  * Then the similarity array will contain:
563  * [-1, -1, am, bm, cm,
564  *  -1, an, bn, cn, dn,
565  *  ao, bo, co, do, eo,
566  *  bp, cp, dp, ep, -1,
567  *  cq, dq, eq, -1, -1]
568  * Where similarities are denoted either by -1 for invalid, or the
569  * concatenation of the two lines in the diff being compared.
570  *
571  * \param similarities array of similarities between lines in A and B
572  * \param line_a the index of the line in A, in the same frame of reference as
573  *      closest_line_a.
574  * \param local_line_b the index of the line in B, relative to the first line
575  *                     in B that similarities represents.
576  * \param closest_line_a the index of the line in A that is deemed to be
577  *                       closest to local_line_b. This must be in the same
578  *                       frame of reference as line_a. This value defines
579  *                       where similarities is centered for the line in B.
580  * \param max_search_distance_a maximum distance in lines from the closest line
581  *                              in A for other lines in A for which
582  *                              similarities may be calculated.
583  */
584 static int *get_similarity(int *similarities,
585                            int line_a, int local_line_b,
586                            int closest_line_a, int max_search_distance_a)
587 {
588         assert(abs(line_a - closest_line_a) <=
589                max_search_distance_a);
590         return similarities + line_a - closest_line_a +
591                max_search_distance_a +
592                local_line_b * (max_search_distance_a * 2 + 1);
593 }
594
595 #define CERTAIN_NOTHING_MATCHES -2
596 #define CERTAINTY_NOT_CALCULATED -1
597
598 /* Given a line in B, first calculate its similarities with nearby lines in A
599  * if not already calculated, then identify the most similar and second most
600  * similar lines. The "certainty" is calculated based on those two
601  * similarities.
602  *
603  * \param start_a the index of the first line of the chunk in A
604  * \param length_a the length in lines of the chunk in A
605  * \param local_line_b the index of the line in B, relative to the first line
606  *                     in the chunk.
607  * \param fingerprints_a array of fingerprints for the chunk in A
608  * \param fingerprints_b array of fingerprints for the chunk in B
609  * \param similarities 2-dimensional array of similarities between lines in A
610  *                     and B. See get_similarity() for more details.
611  * \param certainties array of values indicating how strongly a line in B is
612  *                    matched with some line in A.
613  * \param second_best_result array of absolute indices in A for the second
614  *                           closest match of a line in B.
615  * \param result array of absolute indices in A for the closest match of a line
616  *               in B.
617  * \param max_search_distance_a maximum distance in lines from the closest line
618  *                              in A for other lines in A for which
619  *                              similarities may be calculated.
620  * \param map_line_number_in_b_to_a parameter to map_line_number().
621  */
622 static void find_best_line_matches(
623         int start_a,
624         int length_a,
625         int start_b,
626         int local_line_b,
627         struct fingerprint *fingerprints_a,
628         struct fingerprint *fingerprints_b,
629         int *similarities,
630         int *certainties,
631         int *second_best_result,
632         int *result,
633         const int max_search_distance_a,
634         const struct line_number_mapping *map_line_number_in_b_to_a)
635 {
636
637         int i, search_start, search_end, closest_local_line_a, *similarity,
638                 best_similarity = 0, second_best_similarity = 0,
639                 best_similarity_index = 0, second_best_similarity_index = 0;
640
641         /* certainty has already been calculated so no need to redo the work */
642         if (certainties[local_line_b] != CERTAINTY_NOT_CALCULATED)
643                 return;
644
645         closest_local_line_a = map_line_number(
646                 local_line_b + start_b, map_line_number_in_b_to_a) - start_a;
647
648         search_start = closest_local_line_a - max_search_distance_a;
649         if (search_start < 0)
650                 search_start = 0;
651
652         search_end = closest_local_line_a + max_search_distance_a + 1;
653         if (search_end > length_a)
654                 search_end = length_a;
655
656         for (i = search_start; i < search_end; ++i) {
657                 similarity = get_similarity(similarities,
658                                             i, local_line_b,
659                                             closest_local_line_a,
660                                             max_search_distance_a);
661                 if (*similarity == -1) {
662                         /* This value will never exceed 10 but assert just in
663                          * case
664                          */
665                         assert(abs(i - closest_local_line_a) < 1000);
666                         /* scale the similarity by (1000 - distance from
667                          * closest line) to act as a tie break between lines
668                          * that otherwise are equally similar.
669                          */
670                         *similarity = fingerprint_similarity(
671                                 fingerprints_b + local_line_b,
672                                 fingerprints_a + i) *
673                                 (1000 - abs(i - closest_local_line_a));
674                 }
675                 if (*similarity > best_similarity) {
676                         second_best_similarity = best_similarity;
677                         second_best_similarity_index = best_similarity_index;
678                         best_similarity = *similarity;
679                         best_similarity_index = i;
680                 } else if (*similarity > second_best_similarity) {
681                         second_best_similarity = *similarity;
682                         second_best_similarity_index = i;
683                 }
684         }
685
686         if (best_similarity == 0) {
687                 /* this line definitely doesn't match with anything. Mark it
688                  * with this special value so it doesn't get invalidated and
689                  * won't be recalculated.
690                  */
691                 certainties[local_line_b] = CERTAIN_NOTHING_MATCHES;
692                 result[local_line_b] = -1;
693         } else {
694                 /* Calculate the certainty with which this line matches.
695                  * If the line matches well with two lines then that reduces
696                  * the certainty. However we still want to prioritise matching
697                  * a line that matches very well with two lines over matching a
698                  * line that matches poorly with one line, hence doubling
699                  * best_similarity.
700                  * This means that if we have
701                  * line X that matches only one line with a score of 3,
702                  * line Y that matches two lines equally with a score of 5,
703                  * and line Z that matches only one line with a score or 2,
704                  * then the lines in order of certainty are X, Y, Z.
705                  */
706                 certainties[local_line_b] = best_similarity * 2 -
707                         second_best_similarity;
708
709                 /* We keep both the best and second best results to allow us to
710                  * check at a later stage of the matching process whether the
711                  * result needs to be invalidated.
712                  */
713                 result[local_line_b] = start_a + best_similarity_index;
714                 second_best_result[local_line_b] =
715                         start_a + second_best_similarity_index;
716         }
717 }
718
719 /*
720  * This finds the line that we can match with the most confidence, and
721  * uses it as a partition. It then calls itself on the lines on either side of
722  * that partition. In this way we avoid lines appearing out of order, and
723  * retain a sensible line ordering.
724  * \param start_a index of the first line in A with which lines in B may be
725  *                compared.
726  * \param start_b index of the first line in B for which matching should be
727  *                done.
728  * \param length_a number of lines in A with which lines in B may be compared.
729  * \param length_b number of lines in B for which matching should be done.
730  * \param fingerprints_a mutable array of fingerprints in A. The first element
731  *                       corresponds to the line at start_a.
732  * \param fingerprints_b array of fingerprints in B. The first element
733  *                       corresponds to the line at start_b.
734  * \param similarities 2-dimensional array of similarities between lines in A
735  *                     and B. See get_similarity() for more details.
736  * \param certainties array of values indicating how strongly a line in B is
737  *                    matched with some line in A.
738  * \param second_best_result array of absolute indices in A for the second
739  *                           closest match of a line in B.
740  * \param result array of absolute indices in A for the closest match of a line
741  *               in B.
742  * \param max_search_distance_a maximum distance in lines from the closest line
743  *                            in A for other lines in A for which
744  *                            similarities may be calculated.
745  * \param max_search_distance_b an upper bound on the greatest possible
746  *                            distance between lines in B such that they will
747  *                              both be compared with the same line in A
748  *                            according to max_search_distance_a.
749  * \param map_line_number_in_b_to_a parameter to map_line_number().
750  */
751 static void fuzzy_find_matching_lines_recurse(
752         int start_a, int start_b,
753         int length_a, int length_b,
754         struct fingerprint *fingerprints_a,
755         struct fingerprint *fingerprints_b,
756         int *similarities,
757         int *certainties,
758         int *second_best_result,
759         int *result,
760         int max_search_distance_a,
761         int max_search_distance_b,
762         const struct line_number_mapping *map_line_number_in_b_to_a)
763 {
764         int i, invalidate_min, invalidate_max, offset_b,
765                 second_half_start_a, second_half_start_b,
766                 second_half_length_a, second_half_length_b,
767                 most_certain_line_a, most_certain_local_line_b = -1,
768                 most_certain_line_certainty = -1,
769                 closest_local_line_a;
770
771         for (i = 0; i < length_b; ++i) {
772                 find_best_line_matches(start_a,
773                                        length_a,
774                                        start_b,
775                                        i,
776                                        fingerprints_a,
777                                        fingerprints_b,
778                                        similarities,
779                                        certainties,
780                                        second_best_result,
781                                        result,
782                                        max_search_distance_a,
783                                        map_line_number_in_b_to_a);
784
785                 if (certainties[i] > most_certain_line_certainty) {
786                         most_certain_line_certainty = certainties[i];
787                         most_certain_local_line_b = i;
788                 }
789         }
790
791         /* No matches. */
792         if (most_certain_local_line_b == -1)
793                 return;
794
795         most_certain_line_a = result[most_certain_local_line_b];
796
797         /*
798          * Subtract the most certain line's fingerprint in B from the matched
799          * fingerprint in A. This means that other lines in B can't also match
800          * the same parts of the line in A.
801          */
802         fingerprint_subtract(fingerprints_a + most_certain_line_a - start_a,
803                              fingerprints_b + most_certain_local_line_b);
804
805         /* Invalidate results that may be affected by the choice of most
806          * certain line.
807          */
808         invalidate_min = most_certain_local_line_b - max_search_distance_b;
809         invalidate_max = most_certain_local_line_b + max_search_distance_b + 1;
810         if (invalidate_min < 0)
811                 invalidate_min = 0;
812         if (invalidate_max > length_b)
813                 invalidate_max = length_b;
814
815         /* As the fingerprint in A has changed, discard previously calculated
816          * similarity values with that fingerprint.
817          */
818         for (i = invalidate_min; i < invalidate_max; ++i) {
819                 closest_local_line_a = map_line_number(
820                         i + start_b, map_line_number_in_b_to_a) - start_a;
821
822                 /* Check that the lines in A and B are close enough that there
823                  * is a similarity value for them.
824                  */
825                 if (abs(most_certain_line_a - start_a - closest_local_line_a) >
826                         max_search_distance_a) {
827                         continue;
828                 }
829
830                 *get_similarity(similarities, most_certain_line_a - start_a,
831                                 i, closest_local_line_a,
832                                 max_search_distance_a) = -1;
833         }
834
835         /* More invalidating of results that may be affected by the choice of
836          * most certain line.
837          * Discard the matches for lines in B that are currently matched with a
838          * line in A such that their ordering contradicts the ordering imposed
839          * by the choice of most certain line.
840          */
841         for (i = most_certain_local_line_b - 1; i >= invalidate_min; --i) {
842                 /* In this loop we discard results for lines in B that are
843                  * before most-certain-line-B but are matched with a line in A
844                  * that is after most-certain-line-A.
845                  */
846                 if (certainties[i] >= 0 &&
847                     (result[i] >= most_certain_line_a ||
848                      second_best_result[i] >= most_certain_line_a)) {
849                         certainties[i] = CERTAINTY_NOT_CALCULATED;
850                 }
851         }
852         for (i = most_certain_local_line_b + 1; i < invalidate_max; ++i) {
853                 /* In this loop we discard results for lines in B that are
854                  * after most-certain-line-B but are matched with a line in A
855                  * that is before most-certain-line-A.
856                  */
857                 if (certainties[i] >= 0 &&
858                     (result[i] <= most_certain_line_a ||
859                      second_best_result[i] <= most_certain_line_a)) {
860                         certainties[i] = CERTAINTY_NOT_CALCULATED;
861                 }
862         }
863
864         /* Repeat the matching process for lines before the most certain line.
865          */
866         if (most_certain_local_line_b > 0) {
867                 fuzzy_find_matching_lines_recurse(
868                         start_a, start_b,
869                         most_certain_line_a + 1 - start_a,
870                         most_certain_local_line_b,
871                         fingerprints_a, fingerprints_b, similarities,
872                         certainties, second_best_result, result,
873                         max_search_distance_a,
874                         max_search_distance_b,
875                         map_line_number_in_b_to_a);
876         }
877         /* Repeat the matching process for lines after the most certain line.
878          */
879         if (most_certain_local_line_b + 1 < length_b) {
880                 second_half_start_a = most_certain_line_a;
881                 offset_b = most_certain_local_line_b + 1;
882                 second_half_start_b = start_b + offset_b;
883                 second_half_length_a =
884                         length_a + start_a - second_half_start_a;
885                 second_half_length_b =
886                         length_b + start_b - second_half_start_b;
887                 fuzzy_find_matching_lines_recurse(
888                         second_half_start_a, second_half_start_b,
889                         second_half_length_a, second_half_length_b,
890                         fingerprints_a + second_half_start_a - start_a,
891                         fingerprints_b + offset_b,
892                         similarities +
893                                 offset_b * (max_search_distance_a * 2 + 1),
894                         certainties + offset_b,
895                         second_best_result + offset_b, result + offset_b,
896                         max_search_distance_a,
897                         max_search_distance_b,
898                         map_line_number_in_b_to_a);
899         }
900 }
901
902 /* Find the lines in the parent line range that most closely match the lines in
903  * the target line range. This is accomplished by matching fingerprints in each
904  * blame_origin, and choosing the best matches that preserve the line ordering.
905  * See struct fingerprint for details of fingerprint matching, and
906  * fuzzy_find_matching_lines_recurse for details of preserving line ordering.
907  *
908  * The performance is believed to be O(n log n) in the typical case and O(n^2)
909  * in a pathological case, where n is the number of lines in the target range.
910  */
911 static int *fuzzy_find_matching_lines(struct blame_origin *parent,
912                                       struct blame_origin *target,
913                                       int tlno, int parent_slno, int same,
914                                       int parent_len)
915 {
916         /* We use the terminology "A" for the left hand side of the diff AKA
917          * parent, and "B" for the right hand side of the diff AKA target. */
918         int start_a = parent_slno;
919         int length_a = parent_len;
920         int start_b = tlno;
921         int length_b = same - tlno;
922
923         struct line_number_mapping map_line_number_in_b_to_a = {
924                 start_a, length_a, start_b, length_b
925         };
926
927         struct fingerprint *fingerprints_a = parent->fingerprints;
928         struct fingerprint *fingerprints_b = target->fingerprints;
929
930         int i, *result, *second_best_result,
931                 *certainties, *similarities, similarity_count;
932
933         /*
934          * max_search_distance_a means that given a line in B, compare it to
935          * the line in A that is closest to its position, and the lines in A
936          * that are no greater than max_search_distance_a lines away from the
937          * closest line in A.
938          *
939          * max_search_distance_b is an upper bound on the greatest possible
940          * distance between lines in B such that they will both be compared
941          * with the same line in A according to max_search_distance_a.
942          */
943         int max_search_distance_a = 10, max_search_distance_b;
944
945         if (length_a <= 0)
946                 return NULL;
947
948         if (max_search_distance_a >= length_a)
949                 max_search_distance_a = length_a ? length_a - 1 : 0;
950
951         max_search_distance_b = ((2 * max_search_distance_a + 1) * length_b
952                                  - 1) / length_a;
953
954         result = xcalloc(sizeof(int), length_b);
955         second_best_result = xcalloc(sizeof(int), length_b);
956         certainties = xcalloc(sizeof(int), length_b);
957
958         /* See get_similarity() for details of similarities. */
959         similarity_count = length_b * (max_search_distance_a * 2 + 1);
960         similarities = xcalloc(sizeof(int), similarity_count);
961
962         for (i = 0; i < length_b; ++i) {
963                 result[i] = -1;
964                 second_best_result[i] = -1;
965                 certainties[i] = CERTAINTY_NOT_CALCULATED;
966         }
967
968         for (i = 0; i < similarity_count; ++i)
969                 similarities[i] = -1;
970
971         fuzzy_find_matching_lines_recurse(start_a, start_b,
972                                           length_a, length_b,
973                                           fingerprints_a + start_a,
974                                           fingerprints_b + start_b,
975                                           similarities,
976                                           certainties,
977                                           second_best_result,
978                                           result,
979                                           max_search_distance_a,
980                                           max_search_distance_b,
981                                           &map_line_number_in_b_to_a);
982
983         free(similarities);
984         free(certainties);
985         free(second_best_result);
986
987         return result;
988 }
989
990 static void fill_origin_fingerprints(struct blame_origin *o)
991 {
992         int *line_starts;
993
994         if (o->fingerprints)
995                 return;
996         o->num_lines = find_line_starts(&line_starts, o->file.ptr,
997                                         o->file.size);
998         o->fingerprints = xcalloc(sizeof(struct fingerprint), o->num_lines);
999         get_line_fingerprints(o->fingerprints, o->file.ptr, line_starts,
1000                               0, o->num_lines);
1001         free(line_starts);
1002 }
1003
1004 static void drop_origin_fingerprints(struct blame_origin *o)
1005 {
1006         if (o->fingerprints) {
1007                 free_line_fingerprints(o->fingerprints, o->num_lines);
1008                 o->num_lines = 0;
1009                 FREE_AND_NULL(o->fingerprints);
1010         }
1011 }
1012
1013 /*
1014  * Given an origin, prepare mmfile_t structure to be used by the
1015  * diff machinery
1016  */
1017 static void fill_origin_blob(struct diff_options *opt,
1018                              struct blame_origin *o, mmfile_t *file,
1019                              int *num_read_blob, int fill_fingerprints)
1020 {
1021         if (!o->file.ptr) {
1022                 enum object_type type;
1023                 unsigned long file_size;
1024
1025                 (*num_read_blob)++;
1026                 if (opt->flags.allow_textconv &&
1027                     textconv_object(opt->repo, o->path, o->mode,
1028                                     &o->blob_oid, 1, &file->ptr, &file_size))
1029                         ;
1030                 else
1031                         file->ptr = read_object_file(&o->blob_oid, &type,
1032                                                      &file_size);
1033                 file->size = file_size;
1034
1035                 if (!file->ptr)
1036                         die("Cannot read blob %s for path %s",
1037                             oid_to_hex(&o->blob_oid),
1038                             o->path);
1039                 o->file = *file;
1040         }
1041         else
1042                 *file = o->file;
1043         if (fill_fingerprints)
1044                 fill_origin_fingerprints(o);
1045 }
1046
1047 static void drop_origin_blob(struct blame_origin *o)
1048 {
1049         FREE_AND_NULL(o->file.ptr);
1050         drop_origin_fingerprints(o);
1051 }
1052
1053 /*
1054  * Any merge of blames happens on lists of blames that arrived via
1055  * different parents in a single suspect.  In this case, we want to
1056  * sort according to the suspect line numbers as opposed to the final
1057  * image line numbers.  The function body is somewhat longish because
1058  * it avoids unnecessary writes.
1059  */
1060
1061 static struct blame_entry *blame_merge(struct blame_entry *list1,
1062                                        struct blame_entry *list2)
1063 {
1064         struct blame_entry *p1 = list1, *p2 = list2,
1065                 **tail = &list1;
1066
1067         if (!p1)
1068                 return p2;
1069         if (!p2)
1070                 return p1;
1071
1072         if (p1->s_lno <= p2->s_lno) {
1073                 do {
1074                         tail = &p1->next;
1075                         if ((p1 = *tail) == NULL) {
1076                                 *tail = p2;
1077                                 return list1;
1078                         }
1079                 } while (p1->s_lno <= p2->s_lno);
1080         }
1081         for (;;) {
1082                 *tail = p2;
1083                 do {
1084                         tail = &p2->next;
1085                         if ((p2 = *tail) == NULL)  {
1086                                 *tail = p1;
1087                                 return list1;
1088                         }
1089                 } while (p1->s_lno > p2->s_lno);
1090                 *tail = p1;
1091                 do {
1092                         tail = &p1->next;
1093                         if ((p1 = *tail) == NULL) {
1094                                 *tail = p2;
1095                                 return list1;
1096                         }
1097                 } while (p1->s_lno <= p2->s_lno);
1098         }
1099 }
1100
1101 static void *get_next_blame(const void *p)
1102 {
1103         return ((struct blame_entry *)p)->next;
1104 }
1105
1106 static void set_next_blame(void *p1, void *p2)
1107 {
1108         ((struct blame_entry *)p1)->next = p2;
1109 }
1110
1111 /*
1112  * Final image line numbers are all different, so we don't need a
1113  * three-way comparison here.
1114  */
1115
1116 static int compare_blame_final(const void *p1, const void *p2)
1117 {
1118         return ((struct blame_entry *)p1)->lno > ((struct blame_entry *)p2)->lno
1119                 ? 1 : -1;
1120 }
1121
1122 static int compare_blame_suspect(const void *p1, const void *p2)
1123 {
1124         const struct blame_entry *s1 = p1, *s2 = p2;
1125         /*
1126          * to allow for collating suspects, we sort according to the
1127          * respective pointer value as the primary sorting criterion.
1128          * The actual relation is pretty unimportant as long as it
1129          * establishes a total order.  Comparing as integers gives us
1130          * that.
1131          */
1132         if (s1->suspect != s2->suspect)
1133                 return (intptr_t)s1->suspect > (intptr_t)s2->suspect ? 1 : -1;
1134         if (s1->s_lno == s2->s_lno)
1135                 return 0;
1136         return s1->s_lno > s2->s_lno ? 1 : -1;
1137 }
1138
1139 void blame_sort_final(struct blame_scoreboard *sb)
1140 {
1141         sb->ent = llist_mergesort(sb->ent, get_next_blame, set_next_blame,
1142                                   compare_blame_final);
1143 }
1144
1145 static int compare_commits_by_reverse_commit_date(const void *a,
1146                                                   const void *b,
1147                                                   void *c)
1148 {
1149         return -compare_commits_by_commit_date(a, b, c);
1150 }
1151
1152 /*
1153  * For debugging -- origin is refcounted, and this asserts that
1154  * we do not underflow.
1155  */
1156 static void sanity_check_refcnt(struct blame_scoreboard *sb)
1157 {
1158         int baa = 0;
1159         struct blame_entry *ent;
1160
1161         for (ent = sb->ent; ent; ent = ent->next) {
1162                 /* Nobody should have zero or negative refcnt */
1163                 if (ent->suspect->refcnt <= 0) {
1164                         fprintf(stderr, "%s in %s has negative refcnt %d\n",
1165                                 ent->suspect->path,
1166                                 oid_to_hex(&ent->suspect->commit->object.oid),
1167                                 ent->suspect->refcnt);
1168                         baa = 1;
1169                 }
1170         }
1171         if (baa)
1172                 sb->on_sanity_fail(sb, baa);
1173 }
1174
1175 /*
1176  * If two blame entries that are next to each other came from
1177  * contiguous lines in the same origin (i.e. <commit, path> pair),
1178  * merge them together.
1179  */
1180 void blame_coalesce(struct blame_scoreboard *sb)
1181 {
1182         struct blame_entry *ent, *next;
1183
1184         for (ent = sb->ent; ent && (next = ent->next); ent = next) {
1185                 if (ent->suspect == next->suspect &&
1186                     ent->s_lno + ent->num_lines == next->s_lno &&
1187                     ent->lno + ent->num_lines == next->lno &&
1188                     ent->ignored == next->ignored &&
1189                     ent->unblamable == next->unblamable) {
1190                         ent->num_lines += next->num_lines;
1191                         ent->next = next->next;
1192                         blame_origin_decref(next->suspect);
1193                         free(next);
1194                         ent->score = 0;
1195                         next = ent; /* again */
1196                 }
1197         }
1198
1199         if (sb->debug) /* sanity */
1200                 sanity_check_refcnt(sb);
1201 }
1202
1203 /*
1204  * Merge the given sorted list of blames into a preexisting origin.
1205  * If there were no previous blames to that commit, it is entered into
1206  * the commit priority queue of the score board.
1207  */
1208
1209 static void queue_blames(struct blame_scoreboard *sb, struct blame_origin *porigin,
1210                          struct blame_entry *sorted)
1211 {
1212         if (porigin->suspects)
1213                 porigin->suspects = blame_merge(porigin->suspects, sorted);
1214         else {
1215                 struct blame_origin *o;
1216                 for (o = get_blame_suspects(porigin->commit); o; o = o->next) {
1217                         if (o->suspects) {
1218                                 porigin->suspects = sorted;
1219                                 return;
1220                         }
1221                 }
1222                 porigin->suspects = sorted;
1223                 prio_queue_put(&sb->commits, porigin->commit);
1224         }
1225 }
1226
1227 /*
1228  * Fill the blob_sha1 field of an origin if it hasn't, so that later
1229  * call to fill_origin_blob() can use it to locate the data.  blob_sha1
1230  * for an origin is also used to pass the blame for the entire file to
1231  * the parent to detect the case where a child's blob is identical to
1232  * that of its parent's.
1233  *
1234  * This also fills origin->mode for corresponding tree path.
1235  */
1236 static int fill_blob_sha1_and_mode(struct repository *r,
1237                                    struct blame_origin *origin)
1238 {
1239         if (!is_null_oid(&origin->blob_oid))
1240                 return 0;
1241         if (get_tree_entry(r, &origin->commit->object.oid, origin->path, &origin->blob_oid, &origin->mode))
1242                 goto error_out;
1243         if (oid_object_info(r, &origin->blob_oid, NULL) != OBJ_BLOB)
1244                 goto error_out;
1245         return 0;
1246  error_out:
1247         oidclr(&origin->blob_oid);
1248         origin->mode = S_IFINVALID;
1249         return -1;
1250 }
1251
1252 struct blame_bloom_data {
1253         /*
1254          * Changed-path Bloom filter keys. These can help prevent
1255          * computing diffs against first parents, but we need to
1256          * expand the list as code is moved or files are renamed.
1257          */
1258         struct bloom_filter_settings *settings;
1259         struct bloom_key **keys;
1260         int nr;
1261         int alloc;
1262 };
1263
1264 static int bloom_count_queries = 0;
1265 static int bloom_count_no = 0;
1266 static int maybe_changed_path(struct repository *r,
1267                               struct blame_origin *origin,
1268                               struct blame_bloom_data *bd)
1269 {
1270         int i;
1271         struct bloom_filter *filter;
1272
1273         if (!bd)
1274                 return 1;
1275
1276         if (commit_graph_generation(origin->commit) == GENERATION_NUMBER_INFINITY)
1277                 return 1;
1278
1279         filter = get_bloom_filter(r, origin->commit);
1280
1281         if (!filter)
1282                 return 1;
1283
1284         bloom_count_queries++;
1285         for (i = 0; i < bd->nr; i++) {
1286                 if (bloom_filter_contains(filter,
1287                                           bd->keys[i],
1288                                           bd->settings))
1289                         return 1;
1290         }
1291
1292         bloom_count_no++;
1293         return 0;
1294 }
1295
1296 static void add_bloom_key(struct blame_bloom_data *bd,
1297                           const char *path)
1298 {
1299         if (!bd)
1300                 return;
1301
1302         if (bd->nr >= bd->alloc) {
1303                 bd->alloc *= 2;
1304                 REALLOC_ARRAY(bd->keys, bd->alloc);
1305         }
1306
1307         bd->keys[bd->nr] = xmalloc(sizeof(struct bloom_key));
1308         fill_bloom_key(path, strlen(path), bd->keys[bd->nr], bd->settings);
1309         bd->nr++;
1310 }
1311
1312 /*
1313  * We have an origin -- check if the same path exists in the
1314  * parent and return an origin structure to represent it.
1315  */
1316 static struct blame_origin *find_origin(struct repository *r,
1317                                         struct commit *parent,
1318                                         struct blame_origin *origin,
1319                                         struct blame_bloom_data *bd)
1320 {
1321         struct blame_origin *porigin;
1322         struct diff_options diff_opts;
1323         const char *paths[2];
1324
1325         /* First check any existing origins */
1326         for (porigin = get_blame_suspects(parent); porigin; porigin = porigin->next)
1327                 if (!strcmp(porigin->path, origin->path)) {
1328                         /*
1329                          * The same path between origin and its parent
1330                          * without renaming -- the most common case.
1331                          */
1332                         return blame_origin_incref (porigin);
1333                 }
1334
1335         /* See if the origin->path is different between parent
1336          * and origin first.  Most of the time they are the
1337          * same and diff-tree is fairly efficient about this.
1338          */
1339         repo_diff_setup(r, &diff_opts);
1340         diff_opts.flags.recursive = 1;
1341         diff_opts.detect_rename = 0;
1342         diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;
1343         paths[0] = origin->path;
1344         paths[1] = NULL;
1345
1346         parse_pathspec(&diff_opts.pathspec,
1347                        PATHSPEC_ALL_MAGIC & ~PATHSPEC_LITERAL,
1348                        PATHSPEC_LITERAL_PATH, "", paths);
1349         diff_setup_done(&diff_opts);
1350
1351         if (is_null_oid(&origin->commit->object.oid))
1352                 do_diff_cache(get_commit_tree_oid(parent), &diff_opts);
1353         else {
1354                 int compute_diff = 1;
1355                 if (origin->commit->parents &&
1356                     oideq(&parent->object.oid,
1357                           &origin->commit->parents->item->object.oid))
1358                         compute_diff = maybe_changed_path(r, origin, bd);
1359
1360                 if (compute_diff)
1361                         diff_tree_oid(get_commit_tree_oid(parent),
1362                                       get_commit_tree_oid(origin->commit),
1363                                       "", &diff_opts);
1364         }
1365         diffcore_std(&diff_opts);
1366
1367         if (!diff_queued_diff.nr) {
1368                 /* The path is the same as parent */
1369                 porigin = get_origin(parent, origin->path);
1370                 oidcpy(&porigin->blob_oid, &origin->blob_oid);
1371                 porigin->mode = origin->mode;
1372         } else {
1373                 /*
1374                  * Since origin->path is a pathspec, if the parent
1375                  * commit had it as a directory, we will see a whole
1376                  * bunch of deletion of files in the directory that we
1377                  * do not care about.
1378                  */
1379                 int i;
1380                 struct diff_filepair *p = NULL;
1381                 for (i = 0; i < diff_queued_diff.nr; i++) {
1382                         const char *name;
1383                         p = diff_queued_diff.queue[i];
1384                         name = p->one->path ? p->one->path : p->two->path;
1385                         if (!strcmp(name, origin->path))
1386                                 break;
1387                 }
1388                 if (!p)
1389                         die("internal error in blame::find_origin");
1390                 switch (p->status) {
1391                 default:
1392                         die("internal error in blame::find_origin (%c)",
1393                             p->status);
1394                 case 'M':
1395                         porigin = get_origin(parent, origin->path);
1396                         oidcpy(&porigin->blob_oid, &p->one->oid);
1397                         porigin->mode = p->one->mode;
1398                         break;
1399                 case 'A':
1400                 case 'T':
1401                         /* Did not exist in parent, or type changed */
1402                         break;
1403                 }
1404         }
1405         diff_flush(&diff_opts);
1406         clear_pathspec(&diff_opts.pathspec);
1407         return porigin;
1408 }
1409
1410 /*
1411  * We have an origin -- find the path that corresponds to it in its
1412  * parent and return an origin structure to represent it.
1413  */
1414 static struct blame_origin *find_rename(struct repository *r,
1415                                         struct commit *parent,
1416                                         struct blame_origin *origin,
1417                                         struct blame_bloom_data *bd)
1418 {
1419         struct blame_origin *porigin = NULL;
1420         struct diff_options diff_opts;
1421         int i;
1422
1423         repo_diff_setup(r, &diff_opts);
1424         diff_opts.flags.recursive = 1;
1425         diff_opts.detect_rename = DIFF_DETECT_RENAME;
1426         diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;
1427         diff_opts.single_follow = origin->path;
1428         diff_setup_done(&diff_opts);
1429
1430         if (is_null_oid(&origin->commit->object.oid))
1431                 do_diff_cache(get_commit_tree_oid(parent), &diff_opts);
1432         else
1433                 diff_tree_oid(get_commit_tree_oid(parent),
1434                               get_commit_tree_oid(origin->commit),
1435                               "", &diff_opts);
1436         diffcore_std(&diff_opts);
1437
1438         for (i = 0; i < diff_queued_diff.nr; i++) {
1439                 struct diff_filepair *p = diff_queued_diff.queue[i];
1440                 if ((p->status == 'R' || p->status == 'C') &&
1441                     !strcmp(p->two->path, origin->path)) {
1442                         add_bloom_key(bd, p->one->path);
1443                         porigin = get_origin(parent, p->one->path);
1444                         oidcpy(&porigin->blob_oid, &p->one->oid);
1445                         porigin->mode = p->one->mode;
1446                         break;
1447                 }
1448         }
1449         diff_flush(&diff_opts);
1450         clear_pathspec(&diff_opts.pathspec);
1451         return porigin;
1452 }
1453
1454 /*
1455  * Append a new blame entry to a given output queue.
1456  */
1457 static void add_blame_entry(struct blame_entry ***queue,
1458                             const struct blame_entry *src)
1459 {
1460         struct blame_entry *e = xmalloc(sizeof(*e));
1461         memcpy(e, src, sizeof(*e));
1462         blame_origin_incref(e->suspect);
1463
1464         e->next = **queue;
1465         **queue = e;
1466         *queue = &e->next;
1467 }
1468
1469 /*
1470  * src typically is on-stack; we want to copy the information in it to
1471  * a malloced blame_entry that gets added to the given queue.  The
1472  * origin of dst loses a refcnt.
1473  */
1474 static void dup_entry(struct blame_entry ***queue,
1475                       struct blame_entry *dst, struct blame_entry *src)
1476 {
1477         blame_origin_incref(src->suspect);
1478         blame_origin_decref(dst->suspect);
1479         memcpy(dst, src, sizeof(*src));
1480         dst->next = **queue;
1481         **queue = dst;
1482         *queue = &dst->next;
1483 }
1484
1485 const char *blame_nth_line(struct blame_scoreboard *sb, long lno)
1486 {
1487         return sb->final_buf + sb->lineno[lno];
1488 }
1489
1490 /*
1491  * It is known that lines between tlno to same came from parent, and e
1492  * has an overlap with that range.  it also is known that parent's
1493  * line plno corresponds to e's line tlno.
1494  *
1495  *                <---- e ----->
1496  *                   <------>
1497  *                   <------------>
1498  *             <------------>
1499  *             <------------------>
1500  *
1501  * Split e into potentially three parts; before this chunk, the chunk
1502  * to be blamed for the parent, and after that portion.
1503  */
1504 static void split_overlap(struct blame_entry *split,
1505                           struct blame_entry *e,
1506                           int tlno, int plno, int same,
1507                           struct blame_origin *parent)
1508 {
1509         int chunk_end_lno;
1510         int i;
1511         memset(split, 0, sizeof(struct blame_entry [3]));
1512
1513         for (i = 0; i < 3; i++) {
1514                 split[i].ignored = e->ignored;
1515                 split[i].unblamable = e->unblamable;
1516         }
1517
1518         if (e->s_lno < tlno) {
1519                 /* there is a pre-chunk part not blamed on parent */
1520                 split[0].suspect = blame_origin_incref(e->suspect);
1521                 split[0].lno = e->lno;
1522                 split[0].s_lno = e->s_lno;
1523                 split[0].num_lines = tlno - e->s_lno;
1524                 split[1].lno = e->lno + tlno - e->s_lno;
1525                 split[1].s_lno = plno;
1526         }
1527         else {
1528                 split[1].lno = e->lno;
1529                 split[1].s_lno = plno + (e->s_lno - tlno);
1530         }
1531
1532         if (same < e->s_lno + e->num_lines) {
1533                 /* there is a post-chunk part not blamed on parent */
1534                 split[2].suspect = blame_origin_incref(e->suspect);
1535                 split[2].lno = e->lno + (same - e->s_lno);
1536                 split[2].s_lno = e->s_lno + (same - e->s_lno);
1537                 split[2].num_lines = e->s_lno + e->num_lines - same;
1538                 chunk_end_lno = split[2].lno;
1539         }
1540         else
1541                 chunk_end_lno = e->lno + e->num_lines;
1542         split[1].num_lines = chunk_end_lno - split[1].lno;
1543
1544         /*
1545          * if it turns out there is nothing to blame the parent for,
1546          * forget about the splitting.  !split[1].suspect signals this.
1547          */
1548         if (split[1].num_lines < 1)
1549                 return;
1550         split[1].suspect = blame_origin_incref(parent);
1551 }
1552
1553 /*
1554  * split_overlap() divided an existing blame e into up to three parts
1555  * in split.  Any assigned blame is moved to queue to
1556  * reflect the split.
1557  */
1558 static void split_blame(struct blame_entry ***blamed,
1559                         struct blame_entry ***unblamed,
1560                         struct blame_entry *split,
1561                         struct blame_entry *e)
1562 {
1563         if (split[0].suspect && split[2].suspect) {
1564                 /* The first part (reuse storage for the existing entry e) */
1565                 dup_entry(unblamed, e, &split[0]);
1566
1567                 /* The last part -- me */
1568                 add_blame_entry(unblamed, &split[2]);
1569
1570                 /* ... and the middle part -- parent */
1571                 add_blame_entry(blamed, &split[1]);
1572         }
1573         else if (!split[0].suspect && !split[2].suspect)
1574                 /*
1575                  * The parent covers the entire area; reuse storage for
1576                  * e and replace it with the parent.
1577                  */
1578                 dup_entry(blamed, e, &split[1]);
1579         else if (split[0].suspect) {
1580                 /* me and then parent */
1581                 dup_entry(unblamed, e, &split[0]);
1582                 add_blame_entry(blamed, &split[1]);
1583         }
1584         else {
1585                 /* parent and then me */
1586                 dup_entry(blamed, e, &split[1]);
1587                 add_blame_entry(unblamed, &split[2]);
1588         }
1589 }
1590
1591 /*
1592  * After splitting the blame, the origins used by the
1593  * on-stack blame_entry should lose one refcnt each.
1594  */
1595 static void decref_split(struct blame_entry *split)
1596 {
1597         int i;
1598
1599         for (i = 0; i < 3; i++)
1600                 blame_origin_decref(split[i].suspect);
1601 }
1602
1603 /*
1604  * reverse_blame reverses the list given in head, appending tail.
1605  * That allows us to build lists in reverse order, then reverse them
1606  * afterwards.  This can be faster than building the list in proper
1607  * order right away.  The reason is that building in proper order
1608  * requires writing a link in the _previous_ element, while building
1609  * in reverse order just requires placing the list head into the
1610  * _current_ element.
1611  */
1612
1613 static struct blame_entry *reverse_blame(struct blame_entry *head,
1614                                          struct blame_entry *tail)
1615 {
1616         while (head) {
1617                 struct blame_entry *next = head->next;
1618                 head->next = tail;
1619                 tail = head;
1620                 head = next;
1621         }
1622         return tail;
1623 }
1624
1625 /*
1626  * Splits a blame entry into two entries at 'len' lines.  The original 'e'
1627  * consists of len lines, i.e. [e->lno, e->lno + len), and the second part,
1628  * which is returned, consists of the remainder: [e->lno + len, e->lno +
1629  * e->num_lines).  The caller needs to sort out the reference counting for the
1630  * new entry's suspect.
1631  */
1632 static struct blame_entry *split_blame_at(struct blame_entry *e, int len,
1633                                           struct blame_origin *new_suspect)
1634 {
1635         struct blame_entry *n = xcalloc(1, sizeof(struct blame_entry));
1636
1637         n->suspect = new_suspect;
1638         n->ignored = e->ignored;
1639         n->unblamable = e->unblamable;
1640         n->lno = e->lno + len;
1641         n->s_lno = e->s_lno + len;
1642         n->num_lines = e->num_lines - len;
1643         e->num_lines = len;
1644         e->score = 0;
1645         return n;
1646 }
1647
1648 struct blame_line_tracker {
1649         int is_parent;
1650         int s_lno;
1651 };
1652
1653 static int are_lines_adjacent(struct blame_line_tracker *first,
1654                               struct blame_line_tracker *second)
1655 {
1656         return first->is_parent == second->is_parent &&
1657                first->s_lno + 1 == second->s_lno;
1658 }
1659
1660 static int scan_parent_range(struct fingerprint *p_fps,
1661                              struct fingerprint *t_fps, int t_idx,
1662                              int from, int nr_lines)
1663 {
1664         int sim, p_idx;
1665         #define FINGERPRINT_FILE_THRESHOLD      10
1666         int best_sim_val = FINGERPRINT_FILE_THRESHOLD;
1667         int best_sim_idx = -1;
1668
1669         for (p_idx = from; p_idx < from + nr_lines; p_idx++) {
1670                 sim = fingerprint_similarity(&t_fps[t_idx], &p_fps[p_idx]);
1671                 if (sim < best_sim_val)
1672                         continue;
1673                 /* Break ties with the closest-to-target line number */
1674                 if (sim == best_sim_val && best_sim_idx != -1 &&
1675                     abs(best_sim_idx - t_idx) < abs(p_idx - t_idx))
1676                         continue;
1677                 best_sim_val = sim;
1678                 best_sim_idx = p_idx;
1679         }
1680         return best_sim_idx;
1681 }
1682
1683 /*
1684  * The first pass checks the blame entry (from the target) against the parent's
1685  * diff chunk.  If that fails for a line, the second pass tries to match that
1686  * line to any part of parent file.  That catches cases where a change was
1687  * broken into two chunks by 'context.'
1688  */
1689 static void guess_line_blames(struct blame_origin *parent,
1690                               struct blame_origin *target,
1691                               int tlno, int offset, int same, int parent_len,
1692                               struct blame_line_tracker *line_blames)
1693 {
1694         int i, best_idx, target_idx;
1695         int parent_slno = tlno + offset;
1696         int *fuzzy_matches;
1697
1698         fuzzy_matches = fuzzy_find_matching_lines(parent, target,
1699                                                   tlno, parent_slno, same,
1700                                                   parent_len);
1701         for (i = 0; i < same - tlno; i++) {
1702                 target_idx = tlno + i;
1703                 if (fuzzy_matches && fuzzy_matches[i] >= 0) {
1704                         best_idx = fuzzy_matches[i];
1705                 } else {
1706                         best_idx = scan_parent_range(parent->fingerprints,
1707                                                      target->fingerprints,
1708                                                      target_idx, 0,
1709                                                      parent->num_lines);
1710                 }
1711                 if (best_idx >= 0) {
1712                         line_blames[i].is_parent = 1;
1713                         line_blames[i].s_lno = best_idx;
1714                 } else {
1715                         line_blames[i].is_parent = 0;
1716                         line_blames[i].s_lno = target_idx;
1717                 }
1718         }
1719         free(fuzzy_matches);
1720 }
1721
1722 /*
1723  * This decides which parts of a blame entry go to the parent (added to the
1724  * ignoredp list) and which stay with the target (added to the diffp list).  The
1725  * actual decision was made in a separate heuristic function, and those answers
1726  * for the lines in 'e' are in line_blames.  This consumes e, essentially
1727  * putting it on a list.
1728  *
1729  * Note that the blame entries on the ignoredp list are not necessarily sorted
1730  * with respect to the parent's line numbers yet.
1731  */
1732 static void ignore_blame_entry(struct blame_entry *e,
1733                                struct blame_origin *parent,
1734                                struct blame_entry **diffp,
1735                                struct blame_entry **ignoredp,
1736                                struct blame_line_tracker *line_blames)
1737 {
1738         int entry_len, nr_lines, i;
1739
1740         /*
1741          * We carve new entries off the front of e.  Each entry comes from a
1742          * contiguous chunk of lines: adjacent lines from the same origin
1743          * (either the parent or the target).
1744          */
1745         entry_len = 1;
1746         nr_lines = e->num_lines;        /* e changes in the loop */
1747         for (i = 0; i < nr_lines; i++) {
1748                 struct blame_entry *next = NULL;
1749
1750                 /*
1751                  * We are often adjacent to the next line - only split the blame
1752                  * entry when we have to.
1753                  */
1754                 if (i + 1 < nr_lines) {
1755                         if (are_lines_adjacent(&line_blames[i],
1756                                                &line_blames[i + 1])) {
1757                                 entry_len++;
1758                                 continue;
1759                         }
1760                         next = split_blame_at(e, entry_len,
1761                                               blame_origin_incref(e->suspect));
1762                 }
1763                 if (line_blames[i].is_parent) {
1764                         e->ignored = 1;
1765                         blame_origin_decref(e->suspect);
1766                         e->suspect = blame_origin_incref(parent);
1767                         e->s_lno = line_blames[i - entry_len + 1].s_lno;
1768                         e->next = *ignoredp;
1769                         *ignoredp = e;
1770                 } else {
1771                         e->unblamable = 1;
1772                         /* e->s_lno is already in the target's address space. */
1773                         e->next = *diffp;
1774                         *diffp = e;
1775                 }
1776                 assert(e->num_lines == entry_len);
1777                 e = next;
1778                 entry_len = 1;
1779         }
1780         assert(!e);
1781 }
1782
1783 /*
1784  * Process one hunk from the patch between the current suspect for
1785  * blame_entry e and its parent.  This first blames any unfinished
1786  * entries before the chunk (which is where target and parent start
1787  * differing) on the parent, and then splits blame entries at the
1788  * start and at the end of the difference region.  Since use of -M and
1789  * -C options may lead to overlapping/duplicate source line number
1790  * ranges, all we can rely on from sorting/merging is the order of the
1791  * first suspect line number.
1792  *
1793  * tlno: line number in the target where this chunk begins
1794  * same: line number in the target where this chunk ends
1795  * offset: add to tlno to get the chunk starting point in the parent
1796  * parent_len: number of lines in the parent chunk
1797  */
1798 static void blame_chunk(struct blame_entry ***dstq, struct blame_entry ***srcq,
1799                         int tlno, int offset, int same, int parent_len,
1800                         struct blame_origin *parent,
1801                         struct blame_origin *target, int ignore_diffs)
1802 {
1803         struct blame_entry *e = **srcq;
1804         struct blame_entry *samep = NULL, *diffp = NULL, *ignoredp = NULL;
1805         struct blame_line_tracker *line_blames = NULL;
1806
1807         while (e && e->s_lno < tlno) {
1808                 struct blame_entry *next = e->next;
1809                 /*
1810                  * current record starts before differing portion.  If
1811                  * it reaches into it, we need to split it up and
1812                  * examine the second part separately.
1813                  */
1814                 if (e->s_lno + e->num_lines > tlno) {
1815                         /* Move second half to a new record */
1816                         struct blame_entry *n;
1817
1818                         n = split_blame_at(e, tlno - e->s_lno, e->suspect);
1819                         /* Push new record to diffp */
1820                         n->next = diffp;
1821                         diffp = n;
1822                 } else
1823                         blame_origin_decref(e->suspect);
1824                 /* Pass blame for everything before the differing
1825                  * chunk to the parent */
1826                 e->suspect = blame_origin_incref(parent);
1827                 e->s_lno += offset;
1828                 e->next = samep;
1829                 samep = e;
1830                 e = next;
1831         }
1832         /*
1833          * As we don't know how much of a common stretch after this
1834          * diff will occur, the currently blamed parts are all that we
1835          * can assign to the parent for now.
1836          */
1837
1838         if (samep) {
1839                 **dstq = reverse_blame(samep, **dstq);
1840                 *dstq = &samep->next;
1841         }
1842         /*
1843          * Prepend the split off portions: everything after e starts
1844          * after the blameable portion.
1845          */
1846         e = reverse_blame(diffp, e);
1847
1848         /*
1849          * Now retain records on the target while parts are different
1850          * from the parent.
1851          */
1852         samep = NULL;
1853         diffp = NULL;
1854
1855         if (ignore_diffs && same - tlno > 0) {
1856                 line_blames = xcalloc(sizeof(struct blame_line_tracker),
1857                                       same - tlno);
1858                 guess_line_blames(parent, target, tlno, offset, same,
1859                                   parent_len, line_blames);
1860         }
1861
1862         while (e && e->s_lno < same) {
1863                 struct blame_entry *next = e->next;
1864
1865                 /*
1866                  * If current record extends into sameness, need to split.
1867                  */
1868                 if (e->s_lno + e->num_lines > same) {
1869                         /*
1870                          * Move second half to a new record to be
1871                          * processed by later chunks
1872                          */
1873                         struct blame_entry *n;
1874
1875                         n = split_blame_at(e, same - e->s_lno,
1876                                            blame_origin_incref(e->suspect));
1877                         /* Push new record to samep */
1878                         n->next = samep;
1879                         samep = n;
1880                 }
1881                 if (ignore_diffs) {
1882                         ignore_blame_entry(e, parent, &diffp, &ignoredp,
1883                                            line_blames + e->s_lno - tlno);
1884                 } else {
1885                         e->next = diffp;
1886                         diffp = e;
1887                 }
1888                 e = next;
1889         }
1890         free(line_blames);
1891         if (ignoredp) {
1892                 /*
1893                  * Note ignoredp is not sorted yet, and thus neither is dstq.
1894                  * That list must be sorted before we queue_blames().  We defer
1895                  * sorting until after all diff hunks are processed, so that
1896                  * guess_line_blames() can pick *any* line in the parent.  The
1897                  * slight drawback is that we end up sorting all blame entries
1898                  * passed to the parent, including those that are unrelated to
1899                  * changes made by the ignored commit.
1900                  */
1901                 **dstq = reverse_blame(ignoredp, **dstq);
1902                 *dstq = &ignoredp->next;
1903         }
1904         **srcq = reverse_blame(diffp, reverse_blame(samep, e));
1905         /* Move across elements that are in the unblamable portion */
1906         if (diffp)
1907                 *srcq = &diffp->next;
1908 }
1909
1910 struct blame_chunk_cb_data {
1911         struct blame_origin *parent;
1912         struct blame_origin *target;
1913         long offset;
1914         int ignore_diffs;
1915         struct blame_entry **dstq;
1916         struct blame_entry **srcq;
1917 };
1918
1919 /* diff chunks are from parent to target */
1920 static int blame_chunk_cb(long start_a, long count_a,
1921                           long start_b, long count_b, void *data)
1922 {
1923         struct blame_chunk_cb_data *d = data;
1924         if (start_a - start_b != d->offset)
1925                 die("internal error in blame::blame_chunk_cb");
1926         blame_chunk(&d->dstq, &d->srcq, start_b, start_a - start_b,
1927                     start_b + count_b, count_a, d->parent, d->target,
1928                     d->ignore_diffs);
1929         d->offset = start_a + count_a - (start_b + count_b);
1930         return 0;
1931 }
1932
1933 /*
1934  * We are looking at the origin 'target' and aiming to pass blame
1935  * for the lines it is suspected to its parent.  Run diff to find
1936  * which lines came from parent and pass blame for them.
1937  */
1938 static void pass_blame_to_parent(struct blame_scoreboard *sb,
1939                                  struct blame_origin *target,
1940                                  struct blame_origin *parent, int ignore_diffs)
1941 {
1942         mmfile_t file_p, file_o;
1943         struct blame_chunk_cb_data d;
1944         struct blame_entry *newdest = NULL;
1945
1946         if (!target->suspects)
1947                 return; /* nothing remains for this target */
1948
1949         d.parent = parent;
1950         d.target = target;
1951         d.offset = 0;
1952         d.ignore_diffs = ignore_diffs;
1953         d.dstq = &newdest; d.srcq = &target->suspects;
1954
1955         fill_origin_blob(&sb->revs->diffopt, parent, &file_p,
1956                          &sb->num_read_blob, ignore_diffs);
1957         fill_origin_blob(&sb->revs->diffopt, target, &file_o,
1958                          &sb->num_read_blob, ignore_diffs);
1959         sb->num_get_patch++;
1960
1961         if (diff_hunks(&file_p, &file_o, blame_chunk_cb, &d, sb->xdl_opts))
1962                 die("unable to generate diff (%s -> %s)",
1963                     oid_to_hex(&parent->commit->object.oid),
1964                     oid_to_hex(&target->commit->object.oid));
1965         /* The rest are the same as the parent */
1966         blame_chunk(&d.dstq, &d.srcq, INT_MAX, d.offset, INT_MAX, 0,
1967                     parent, target, 0);
1968         *d.dstq = NULL;
1969         if (ignore_diffs)
1970                 newdest = llist_mergesort(newdest, get_next_blame,
1971                                           set_next_blame,
1972                                           compare_blame_suspect);
1973         queue_blames(sb, parent, newdest);
1974
1975         return;
1976 }
1977
1978 /*
1979  * The lines in blame_entry after splitting blames many times can become
1980  * very small and trivial, and at some point it becomes pointless to
1981  * blame the parents.  E.g. "\t\t}\n\t}\n\n" appears everywhere in any
1982  * ordinary C program, and it is not worth to say it was copied from
1983  * totally unrelated file in the parent.
1984  *
1985  * Compute how trivial the lines in the blame_entry are.
1986  */
1987 unsigned blame_entry_score(struct blame_scoreboard *sb, struct blame_entry *e)
1988 {
1989         unsigned score;
1990         const char *cp, *ep;
1991
1992         if (e->score)
1993                 return e->score;
1994
1995         score = 1;
1996         cp = blame_nth_line(sb, e->lno);
1997         ep = blame_nth_line(sb, e->lno + e->num_lines);
1998         while (cp < ep) {
1999                 unsigned ch = *((unsigned char *)cp);
2000                 if (isalnum(ch))
2001                         score++;
2002                 cp++;
2003         }
2004         e->score = score;
2005         return score;
2006 }
2007
2008 /*
2009  * best_so_far[] and potential[] are both a split of an existing blame_entry
2010  * that passes blame to the parent.  Maintain best_so_far the best split so
2011  * far, by comparing potential and best_so_far and copying potential into
2012  * bst_so_far as needed.
2013  */
2014 static void copy_split_if_better(struct blame_scoreboard *sb,
2015                                  struct blame_entry *best_so_far,
2016                                  struct blame_entry *potential)
2017 {
2018         int i;
2019
2020         if (!potential[1].suspect)
2021                 return;
2022         if (best_so_far[1].suspect) {
2023                 if (blame_entry_score(sb, &potential[1]) <
2024                     blame_entry_score(sb, &best_so_far[1]))
2025                         return;
2026         }
2027
2028         for (i = 0; i < 3; i++)
2029                 blame_origin_incref(potential[i].suspect);
2030         decref_split(best_so_far);
2031         memcpy(best_so_far, potential, sizeof(struct blame_entry[3]));
2032 }
2033
2034 /*
2035  * We are looking at a part of the final image represented by
2036  * ent (tlno and same are offset by ent->s_lno).
2037  * tlno is where we are looking at in the final image.
2038  * up to (but not including) same match preimage.
2039  * plno is where we are looking at in the preimage.
2040  *
2041  * <-------------- final image ---------------------->
2042  *       <------ent------>
2043  *         ^tlno ^same
2044  *    <---------preimage----->
2045  *         ^plno
2046  *
2047  * All line numbers are 0-based.
2048  */
2049 static void handle_split(struct blame_scoreboard *sb,
2050                          struct blame_entry *ent,
2051                          int tlno, int plno, int same,
2052                          struct blame_origin *parent,
2053                          struct blame_entry *split)
2054 {
2055         if (ent->num_lines <= tlno)
2056                 return;
2057         if (tlno < same) {
2058                 struct blame_entry potential[3];
2059                 tlno += ent->s_lno;
2060                 same += ent->s_lno;
2061                 split_overlap(potential, ent, tlno, plno, same, parent);
2062                 copy_split_if_better(sb, split, potential);
2063                 decref_split(potential);
2064         }
2065 }
2066
2067 struct handle_split_cb_data {
2068         struct blame_scoreboard *sb;
2069         struct blame_entry *ent;
2070         struct blame_origin *parent;
2071         struct blame_entry *split;
2072         long plno;
2073         long tlno;
2074 };
2075
2076 static int handle_split_cb(long start_a, long count_a,
2077                            long start_b, long count_b, void *data)
2078 {
2079         struct handle_split_cb_data *d = data;
2080         handle_split(d->sb, d->ent, d->tlno, d->plno, start_b, d->parent,
2081                      d->split);
2082         d->plno = start_a + count_a;
2083         d->tlno = start_b + count_b;
2084         return 0;
2085 }
2086
2087 /*
2088  * Find the lines from parent that are the same as ent so that
2089  * we can pass blames to it.  file_p has the blob contents for
2090  * the parent.
2091  */
2092 static void find_copy_in_blob(struct blame_scoreboard *sb,
2093                               struct blame_entry *ent,
2094                               struct blame_origin *parent,
2095                               struct blame_entry *split,
2096                               mmfile_t *file_p)
2097 {
2098         const char *cp;
2099         mmfile_t file_o;
2100         struct handle_split_cb_data d;
2101
2102         memset(&d, 0, sizeof(d));
2103         d.sb = sb; d.ent = ent; d.parent = parent; d.split = split;
2104         /*
2105          * Prepare mmfile that contains only the lines in ent.
2106          */
2107         cp = blame_nth_line(sb, ent->lno);
2108         file_o.ptr = (char *) cp;
2109         file_o.size = blame_nth_line(sb, ent->lno + ent->num_lines) - cp;
2110
2111         /*
2112          * file_o is a part of final image we are annotating.
2113          * file_p partially may match that image.
2114          */
2115         memset(split, 0, sizeof(struct blame_entry [3]));
2116         if (diff_hunks(file_p, &file_o, handle_split_cb, &d, sb->xdl_opts))
2117                 die("unable to generate diff (%s)",
2118                     oid_to_hex(&parent->commit->object.oid));
2119         /* remainder, if any, all match the preimage */
2120         handle_split(sb, ent, d.tlno, d.plno, ent->num_lines, parent, split);
2121 }
2122
2123 /* Move all blame entries from list *source that have a score smaller
2124  * than score_min to the front of list *small.
2125  * Returns a pointer to the link pointing to the old head of the small list.
2126  */
2127
2128 static struct blame_entry **filter_small(struct blame_scoreboard *sb,
2129                                          struct blame_entry **small,
2130                                          struct blame_entry **source,
2131                                          unsigned score_min)
2132 {
2133         struct blame_entry *p = *source;
2134         struct blame_entry *oldsmall = *small;
2135         while (p) {
2136                 if (blame_entry_score(sb, p) <= score_min) {
2137                         *small = p;
2138                         small = &p->next;
2139                         p = *small;
2140                 } else {
2141                         *source = p;
2142                         source = &p->next;
2143                         p = *source;
2144                 }
2145         }
2146         *small = oldsmall;
2147         *source = NULL;
2148         return small;
2149 }
2150
2151 /*
2152  * See if lines currently target is suspected for can be attributed to
2153  * parent.
2154  */
2155 static void find_move_in_parent(struct blame_scoreboard *sb,
2156                                 struct blame_entry ***blamed,
2157                                 struct blame_entry **toosmall,
2158                                 struct blame_origin *target,
2159                                 struct blame_origin *parent)
2160 {
2161         struct blame_entry *e, split[3];
2162         struct blame_entry *unblamed = target->suspects;
2163         struct blame_entry *leftover = NULL;
2164         mmfile_t file_p;
2165
2166         if (!unblamed)
2167                 return; /* nothing remains for this target */
2168
2169         fill_origin_blob(&sb->revs->diffopt, parent, &file_p,
2170                          &sb->num_read_blob, 0);
2171         if (!file_p.ptr)
2172                 return;
2173
2174         /* At each iteration, unblamed has a NULL-terminated list of
2175          * entries that have not yet been tested for blame.  leftover
2176          * contains the reversed list of entries that have been tested
2177          * without being assignable to the parent.
2178          */
2179         do {
2180                 struct blame_entry **unblamedtail = &unblamed;
2181                 struct blame_entry *next;
2182                 for (e = unblamed; e; e = next) {
2183                         next = e->next;
2184                         find_copy_in_blob(sb, e, parent, split, &file_p);
2185                         if (split[1].suspect &&
2186                             sb->move_score < blame_entry_score(sb, &split[1])) {
2187                                 split_blame(blamed, &unblamedtail, split, e);
2188                         } else {
2189                                 e->next = leftover;
2190                                 leftover = e;
2191                         }
2192                         decref_split(split);
2193                 }
2194                 *unblamedtail = NULL;
2195                 toosmall = filter_small(sb, toosmall, &unblamed, sb->move_score);
2196         } while (unblamed);
2197         target->suspects = reverse_blame(leftover, NULL);
2198 }
2199
2200 struct blame_list {
2201         struct blame_entry *ent;
2202         struct blame_entry split[3];
2203 };
2204
2205 /*
2206  * Count the number of entries the target is suspected for,
2207  * and prepare a list of entry and the best split.
2208  */
2209 static struct blame_list *setup_blame_list(struct blame_entry *unblamed,
2210                                            int *num_ents_p)
2211 {
2212         struct blame_entry *e;
2213         int num_ents, i;
2214         struct blame_list *blame_list = NULL;
2215
2216         for (e = unblamed, num_ents = 0; e; e = e->next)
2217                 num_ents++;
2218         if (num_ents) {
2219                 blame_list = xcalloc(num_ents, sizeof(struct blame_list));
2220                 for (e = unblamed, i = 0; e; e = e->next)
2221                         blame_list[i++].ent = e;
2222         }
2223         *num_ents_p = num_ents;
2224         return blame_list;
2225 }
2226
2227 /*
2228  * For lines target is suspected for, see if we can find code movement
2229  * across file boundary from the parent commit.  porigin is the path
2230  * in the parent we already tried.
2231  */
2232 static void find_copy_in_parent(struct blame_scoreboard *sb,
2233                                 struct blame_entry ***blamed,
2234                                 struct blame_entry **toosmall,
2235                                 struct blame_origin *target,
2236                                 struct commit *parent,
2237                                 struct blame_origin *porigin,
2238                                 int opt)
2239 {
2240         struct diff_options diff_opts;
2241         int i, j;
2242         struct blame_list *blame_list;
2243         int num_ents;
2244         struct blame_entry *unblamed = target->suspects;
2245         struct blame_entry *leftover = NULL;
2246
2247         if (!unblamed)
2248                 return; /* nothing remains for this target */
2249
2250         repo_diff_setup(sb->repo, &diff_opts);
2251         diff_opts.flags.recursive = 1;
2252         diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;
2253
2254         diff_setup_done(&diff_opts);
2255
2256         /* Try "find copies harder" on new path if requested;
2257          * we do not want to use diffcore_rename() actually to
2258          * match things up; find_copies_harder is set only to
2259          * force diff_tree_oid() to feed all filepairs to diff_queue,
2260          * and this code needs to be after diff_setup_done(), which
2261          * usually makes find-copies-harder imply copy detection.
2262          */
2263         if ((opt & PICKAXE_BLAME_COPY_HARDEST)
2264             || ((opt & PICKAXE_BLAME_COPY_HARDER)
2265                 && (!porigin || strcmp(target->path, porigin->path))))
2266                 diff_opts.flags.find_copies_harder = 1;
2267
2268         if (is_null_oid(&target->commit->object.oid))
2269                 do_diff_cache(get_commit_tree_oid(parent), &diff_opts);
2270         else
2271                 diff_tree_oid(get_commit_tree_oid(parent),
2272                               get_commit_tree_oid(target->commit),
2273                               "", &diff_opts);
2274
2275         if (!diff_opts.flags.find_copies_harder)
2276                 diffcore_std(&diff_opts);
2277
2278         do {
2279                 struct blame_entry **unblamedtail = &unblamed;
2280                 blame_list = setup_blame_list(unblamed, &num_ents);
2281
2282                 for (i = 0; i < diff_queued_diff.nr; i++) {
2283                         struct diff_filepair *p = diff_queued_diff.queue[i];
2284                         struct blame_origin *norigin;
2285                         mmfile_t file_p;
2286                         struct blame_entry potential[3];
2287
2288                         if (!DIFF_FILE_VALID(p->one))
2289                                 continue; /* does not exist in parent */
2290                         if (S_ISGITLINK(p->one->mode))
2291                                 continue; /* ignore git links */
2292                         if (porigin && !strcmp(p->one->path, porigin->path))
2293                                 /* find_move already dealt with this path */
2294                                 continue;
2295
2296                         norigin = get_origin(parent, p->one->path);
2297                         oidcpy(&norigin->blob_oid, &p->one->oid);
2298                         norigin->mode = p->one->mode;
2299                         fill_origin_blob(&sb->revs->diffopt, norigin, &file_p,
2300                                          &sb->num_read_blob, 0);
2301                         if (!file_p.ptr)
2302                                 continue;
2303
2304                         for (j = 0; j < num_ents; j++) {
2305                                 find_copy_in_blob(sb, blame_list[j].ent,
2306                                                   norigin, potential, &file_p);
2307                                 copy_split_if_better(sb, blame_list[j].split,
2308                                                      potential);
2309                                 decref_split(potential);
2310                         }
2311                         blame_origin_decref(norigin);
2312                 }
2313
2314                 for (j = 0; j < num_ents; j++) {
2315                         struct blame_entry *split = blame_list[j].split;
2316                         if (split[1].suspect &&
2317                             sb->copy_score < blame_entry_score(sb, &split[1])) {
2318                                 split_blame(blamed, &unblamedtail, split,
2319                                             blame_list[j].ent);
2320                         } else {
2321                                 blame_list[j].ent->next = leftover;
2322                                 leftover = blame_list[j].ent;
2323                         }
2324                         decref_split(split);
2325                 }
2326                 free(blame_list);
2327                 *unblamedtail = NULL;
2328                 toosmall = filter_small(sb, toosmall, &unblamed, sb->copy_score);
2329         } while (unblamed);
2330         target->suspects = reverse_blame(leftover, NULL);
2331         diff_flush(&diff_opts);
2332         clear_pathspec(&diff_opts.pathspec);
2333 }
2334
2335 /*
2336  * The blobs of origin and porigin exactly match, so everything
2337  * origin is suspected for can be blamed on the parent.
2338  */
2339 static void pass_whole_blame(struct blame_scoreboard *sb,
2340                              struct blame_origin *origin, struct blame_origin *porigin)
2341 {
2342         struct blame_entry *e, *suspects;
2343
2344         if (!porigin->file.ptr && origin->file.ptr) {
2345                 /* Steal its file */
2346                 porigin->file = origin->file;
2347                 origin->file.ptr = NULL;
2348         }
2349         suspects = origin->suspects;
2350         origin->suspects = NULL;
2351         for (e = suspects; e; e = e->next) {
2352                 blame_origin_incref(porigin);
2353                 blame_origin_decref(e->suspect);
2354                 e->suspect = porigin;
2355         }
2356         queue_blames(sb, porigin, suspects);
2357 }
2358
2359 /*
2360  * We pass blame from the current commit to its parents.  We keep saying
2361  * "parent" (and "porigin"), but what we mean is to find scapegoat to
2362  * exonerate ourselves.
2363  */
2364 static struct commit_list *first_scapegoat(struct rev_info *revs, struct commit *commit,
2365                                         int reverse)
2366 {
2367         if (!reverse) {
2368                 if (revs->first_parent_only &&
2369                     commit->parents &&
2370                     commit->parents->next) {
2371                         free_commit_list(commit->parents->next);
2372                         commit->parents->next = NULL;
2373                 }
2374                 return commit->parents;
2375         }
2376         return lookup_decoration(&revs->children, &commit->object);
2377 }
2378
2379 static int num_scapegoats(struct rev_info *revs, struct commit *commit, int reverse)
2380 {
2381         struct commit_list *l = first_scapegoat(revs, commit, reverse);
2382         return commit_list_count(l);
2383 }
2384
2385 /* Distribute collected unsorted blames to the respected sorted lists
2386  * in the various origins.
2387  */
2388 static void distribute_blame(struct blame_scoreboard *sb, struct blame_entry *blamed)
2389 {
2390         blamed = llist_mergesort(blamed, get_next_blame, set_next_blame,
2391                                  compare_blame_suspect);
2392         while (blamed)
2393         {
2394                 struct blame_origin *porigin = blamed->suspect;
2395                 struct blame_entry *suspects = NULL;
2396                 do {
2397                         struct blame_entry *next = blamed->next;
2398                         blamed->next = suspects;
2399                         suspects = blamed;
2400                         blamed = next;
2401                 } while (blamed && blamed->suspect == porigin);
2402                 suspects = reverse_blame(suspects, NULL);
2403                 queue_blames(sb, porigin, suspects);
2404         }
2405 }
2406
2407 #define MAXSG 16
2408
2409 typedef struct blame_origin *(*blame_find_alg)(struct repository *,
2410                                                struct commit *,
2411                                                struct blame_origin *,
2412                                                struct blame_bloom_data *);
2413
2414 static void pass_blame(struct blame_scoreboard *sb, struct blame_origin *origin, int opt)
2415 {
2416         struct rev_info *revs = sb->revs;
2417         int i, pass, num_sg;
2418         struct commit *commit = origin->commit;
2419         struct commit_list *sg;
2420         struct blame_origin *sg_buf[MAXSG];
2421         struct blame_origin *porigin, **sg_origin = sg_buf;
2422         struct blame_entry *toosmall = NULL;
2423         struct blame_entry *blames, **blametail = &blames;
2424
2425         num_sg = num_scapegoats(revs, commit, sb->reverse);
2426         if (!num_sg)
2427                 goto finish;
2428         else if (num_sg < ARRAY_SIZE(sg_buf))
2429                 memset(sg_buf, 0, sizeof(sg_buf));
2430         else
2431                 sg_origin = xcalloc(num_sg, sizeof(*sg_origin));
2432
2433         /*
2434          * The first pass looks for unrenamed path to optimize for
2435          * common cases, then we look for renames in the second pass.
2436          */
2437         for (pass = 0; pass < 2 - sb->no_whole_file_rename; pass++) {
2438                 blame_find_alg find = pass ? find_rename : find_origin;
2439
2440                 for (i = 0, sg = first_scapegoat(revs, commit, sb->reverse);
2441                      i < num_sg && sg;
2442                      sg = sg->next, i++) {
2443                         struct commit *p = sg->item;
2444                         int j, same;
2445
2446                         if (sg_origin[i])
2447                                 continue;
2448                         if (parse_commit(p))
2449                                 continue;
2450                         porigin = find(sb->repo, p, origin, sb->bloom_data);
2451                         if (!porigin)
2452                                 continue;
2453                         if (oideq(&porigin->blob_oid, &origin->blob_oid)) {
2454                                 pass_whole_blame(sb, origin, porigin);
2455                                 blame_origin_decref(porigin);
2456                                 goto finish;
2457                         }
2458                         for (j = same = 0; j < i; j++)
2459                                 if (sg_origin[j] &&
2460                                     oideq(&sg_origin[j]->blob_oid, &porigin->blob_oid)) {
2461                                         same = 1;
2462                                         break;
2463                                 }
2464                         if (!same)
2465                                 sg_origin[i] = porigin;
2466                         else
2467                                 blame_origin_decref(porigin);
2468                 }
2469         }
2470
2471         sb->num_commits++;
2472         for (i = 0, sg = first_scapegoat(revs, commit, sb->reverse);
2473              i < num_sg && sg;
2474              sg = sg->next, i++) {
2475                 struct blame_origin *porigin = sg_origin[i];
2476                 if (!porigin)
2477                         continue;
2478                 if (!origin->previous) {
2479                         blame_origin_incref(porigin);
2480                         origin->previous = porigin;
2481                 }
2482                 pass_blame_to_parent(sb, origin, porigin, 0);
2483                 if (!origin->suspects)
2484                         goto finish;
2485         }
2486
2487         /*
2488          * Pass remaining suspects for ignored commits to their parents.
2489          */
2490         if (oidset_contains(&sb->ignore_list, &commit->object.oid)) {
2491                 for (i = 0, sg = first_scapegoat(revs, commit, sb->reverse);
2492                      i < num_sg && sg;
2493                      sg = sg->next, i++) {
2494                         struct blame_origin *porigin = sg_origin[i];
2495
2496                         if (!porigin)
2497                                 continue;
2498                         pass_blame_to_parent(sb, origin, porigin, 1);
2499                         /*
2500                          * Preemptively drop porigin so we can refresh the
2501                          * fingerprints if we use the parent again, which can
2502                          * occur if you ignore back-to-back commits.
2503                          */
2504                         drop_origin_blob(porigin);
2505                         if (!origin->suspects)
2506                                 goto finish;
2507                 }
2508         }
2509
2510         /*
2511          * Optionally find moves in parents' files.
2512          */
2513         if (opt & PICKAXE_BLAME_MOVE) {
2514                 filter_small(sb, &toosmall, &origin->suspects, sb->move_score);
2515                 if (origin->suspects) {
2516                         for (i = 0, sg = first_scapegoat(revs, commit, sb->reverse);
2517                              i < num_sg && sg;
2518                              sg = sg->next, i++) {
2519                                 struct blame_origin *porigin = sg_origin[i];
2520                                 if (!porigin)
2521                                         continue;
2522                                 find_move_in_parent(sb, &blametail, &toosmall, origin, porigin);
2523                                 if (!origin->suspects)
2524                                         break;
2525                         }
2526                 }
2527         }
2528
2529         /*
2530          * Optionally find copies from parents' files.
2531          */
2532         if (opt & PICKAXE_BLAME_COPY) {
2533                 if (sb->copy_score > sb->move_score)
2534                         filter_small(sb, &toosmall, &origin->suspects, sb->copy_score);
2535                 else if (sb->copy_score < sb->move_score) {
2536                         origin->suspects = blame_merge(origin->suspects, toosmall);
2537                         toosmall = NULL;
2538                         filter_small(sb, &toosmall, &origin->suspects, sb->copy_score);
2539                 }
2540                 if (!origin->suspects)
2541                         goto finish;
2542
2543                 for (i = 0, sg = first_scapegoat(revs, commit, sb->reverse);
2544                      i < num_sg && sg;
2545                      sg = sg->next, i++) {
2546                         struct blame_origin *porigin = sg_origin[i];
2547                         find_copy_in_parent(sb, &blametail, &toosmall,
2548                                             origin, sg->item, porigin, opt);
2549                         if (!origin->suspects)
2550                                 goto finish;
2551                 }
2552         }
2553
2554 finish:
2555         *blametail = NULL;
2556         distribute_blame(sb, blames);
2557         /*
2558          * prepend toosmall to origin->suspects
2559          *
2560          * There is no point in sorting: this ends up on a big
2561          * unsorted list in the caller anyway.
2562          */
2563         if (toosmall) {
2564                 struct blame_entry **tail = &toosmall;
2565                 while (*tail)
2566                         tail = &(*tail)->next;
2567                 *tail = origin->suspects;
2568                 origin->suspects = toosmall;
2569         }
2570         for (i = 0; i < num_sg; i++) {
2571                 if (sg_origin[i]) {
2572                         if (!sg_origin[i]->suspects)
2573                                 drop_origin_blob(sg_origin[i]);
2574                         blame_origin_decref(sg_origin[i]);
2575                 }
2576         }
2577         drop_origin_blob(origin);
2578         if (sg_buf != sg_origin)
2579                 free(sg_origin);
2580 }
2581
2582 /*
2583  * The main loop -- while we have blobs with lines whose true origin
2584  * is still unknown, pick one blob, and allow its lines to pass blames
2585  * to its parents. */
2586 void assign_blame(struct blame_scoreboard *sb, int opt)
2587 {
2588         struct rev_info *revs = sb->revs;
2589         struct commit *commit = prio_queue_get(&sb->commits);
2590
2591         while (commit) {
2592                 struct blame_entry *ent;
2593                 struct blame_origin *suspect = get_blame_suspects(commit);
2594
2595                 /* find one suspect to break down */
2596                 while (suspect && !suspect->suspects)
2597                         suspect = suspect->next;
2598
2599                 if (!suspect) {
2600                         commit = prio_queue_get(&sb->commits);
2601                         continue;
2602                 }
2603
2604                 assert(commit == suspect->commit);
2605
2606                 /*
2607                  * We will use this suspect later in the loop,
2608                  * so hold onto it in the meantime.
2609                  */
2610                 blame_origin_incref(suspect);
2611                 parse_commit(commit);
2612                 if (sb->reverse ||
2613                     (!(commit->object.flags & UNINTERESTING) &&
2614                      !(revs->max_age != -1 && commit->date < revs->max_age)))
2615                         pass_blame(sb, suspect, opt);
2616                 else {
2617                         commit->object.flags |= UNINTERESTING;
2618                         if (commit->object.parsed)
2619                                 mark_parents_uninteresting(commit);
2620                 }
2621                 /* treat root commit as boundary */
2622                 if (!commit->parents && !sb->show_root)
2623                         commit->object.flags |= UNINTERESTING;
2624
2625                 /* Take responsibility for the remaining entries */
2626                 ent = suspect->suspects;
2627                 if (ent) {
2628                         suspect->guilty = 1;
2629                         for (;;) {
2630                                 struct blame_entry *next = ent->next;
2631                                 if (sb->found_guilty_entry)
2632                                         sb->found_guilty_entry(ent, sb->found_guilty_entry_data);
2633                                 if (next) {
2634                                         ent = next;
2635                                         continue;
2636                                 }
2637                                 ent->next = sb->ent;
2638                                 sb->ent = suspect->suspects;
2639                                 suspect->suspects = NULL;
2640                                 break;
2641                         }
2642                 }
2643                 blame_origin_decref(suspect);
2644
2645                 if (sb->debug) /* sanity */
2646                         sanity_check_refcnt(sb);
2647         }
2648 }
2649
2650 /*
2651  * To allow quick access to the contents of nth line in the
2652  * final image, prepare an index in the scoreboard.
2653  */
2654 static int prepare_lines(struct blame_scoreboard *sb)
2655 {
2656         sb->num_lines = find_line_starts(&sb->lineno, sb->final_buf,
2657                                          sb->final_buf_size);
2658         return sb->num_lines;
2659 }
2660
2661 static struct commit *find_single_final(struct rev_info *revs,
2662                                         const char **name_p)
2663 {
2664         int i;
2665         struct commit *found = NULL;
2666         const char *name = NULL;
2667
2668         for (i = 0; i < revs->pending.nr; i++) {
2669                 struct object *obj = revs->pending.objects[i].item;
2670                 if (obj->flags & UNINTERESTING)
2671                         continue;
2672                 obj = deref_tag(revs->repo, obj, NULL, 0);
2673                 if (obj->type != OBJ_COMMIT)
2674                         die("Non commit %s?", revs->pending.objects[i].name);
2675                 if (found)
2676                         die("More than one commit to dig from %s and %s?",
2677                             revs->pending.objects[i].name, name);
2678                 found = (struct commit *)obj;
2679                 name = revs->pending.objects[i].name;
2680         }
2681         if (name_p)
2682                 *name_p = xstrdup_or_null(name);
2683         return found;
2684 }
2685
2686 static struct commit *dwim_reverse_initial(struct rev_info *revs,
2687                                            const char **name_p)
2688 {
2689         /*
2690          * DWIM "git blame --reverse ONE -- PATH" as
2691          * "git blame --reverse ONE..HEAD -- PATH" but only do so
2692          * when it makes sense.
2693          */
2694         struct object *obj;
2695         struct commit *head_commit;
2696         struct object_id head_oid;
2697
2698         if (revs->pending.nr != 1)
2699                 return NULL;
2700
2701         /* Is that sole rev a committish? */
2702         obj = revs->pending.objects[0].item;
2703         obj = deref_tag(revs->repo, obj, NULL, 0);
2704         if (obj->type != OBJ_COMMIT)
2705                 return NULL;
2706
2707         /* Do we have HEAD? */
2708         if (!resolve_ref_unsafe("HEAD", RESOLVE_REF_READING, &head_oid, NULL))
2709                 return NULL;
2710         head_commit = lookup_commit_reference_gently(revs->repo,
2711                                                      &head_oid, 1);
2712         if (!head_commit)
2713                 return NULL;
2714
2715         /* Turn "ONE" into "ONE..HEAD" then */
2716         obj->flags |= UNINTERESTING;
2717         add_pending_object(revs, &head_commit->object, "HEAD");
2718
2719         if (name_p)
2720                 *name_p = revs->pending.objects[0].name;
2721         return (struct commit *)obj;
2722 }
2723
2724 static struct commit *find_single_initial(struct rev_info *revs,
2725                                           const char **name_p)
2726 {
2727         int i;
2728         struct commit *found = NULL;
2729         const char *name = NULL;
2730
2731         /*
2732          * There must be one and only one negative commit, and it must be
2733          * the boundary.
2734          */
2735         for (i = 0; i < revs->pending.nr; i++) {
2736                 struct object *obj = revs->pending.objects[i].item;
2737                 if (!(obj->flags & UNINTERESTING))
2738                         continue;
2739                 obj = deref_tag(revs->repo, obj, NULL, 0);
2740                 if (obj->type != OBJ_COMMIT)
2741                         die("Non commit %s?", revs->pending.objects[i].name);
2742                 if (found)
2743                         die("More than one commit to dig up from, %s and %s?",
2744                             revs->pending.objects[i].name, name);
2745                 found = (struct commit *) obj;
2746                 name = revs->pending.objects[i].name;
2747         }
2748
2749         if (!name)
2750                 found = dwim_reverse_initial(revs, &name);
2751         if (!name)
2752                 die("No commit to dig up from?");
2753
2754         if (name_p)
2755                 *name_p = xstrdup(name);
2756         return found;
2757 }
2758
2759 void init_scoreboard(struct blame_scoreboard *sb)
2760 {
2761         memset(sb, 0, sizeof(struct blame_scoreboard));
2762         sb->move_score = BLAME_DEFAULT_MOVE_SCORE;
2763         sb->copy_score = BLAME_DEFAULT_COPY_SCORE;
2764 }
2765
2766 void setup_scoreboard(struct blame_scoreboard *sb,
2767                       const char *path,
2768                       struct blame_origin **orig)
2769 {
2770         const char *final_commit_name = NULL;
2771         struct blame_origin *o;
2772         struct commit *final_commit = NULL;
2773         enum object_type type;
2774
2775         init_blame_suspects(&blame_suspects);
2776
2777         if (sb->reverse && sb->contents_from)
2778                 die(_("--contents and --reverse do not blend well."));
2779
2780         if (!sb->repo)
2781                 BUG("repo is NULL");
2782
2783         if (!sb->reverse) {
2784                 sb->final = find_single_final(sb->revs, &final_commit_name);
2785                 sb->commits.compare = compare_commits_by_commit_date;
2786         } else {
2787                 sb->final = find_single_initial(sb->revs, &final_commit_name);
2788                 sb->commits.compare = compare_commits_by_reverse_commit_date;
2789         }
2790
2791         if (sb->final && sb->contents_from)
2792                 die(_("cannot use --contents with final commit object name"));
2793
2794         if (sb->reverse && sb->revs->first_parent_only)
2795                 sb->revs->children.name = NULL;
2796
2797         if (!sb->final) {
2798                 /*
2799                  * "--not A B -- path" without anything positive;
2800                  * do not default to HEAD, but use the working tree
2801                  * or "--contents".
2802                  */
2803                 setup_work_tree();
2804                 sb->final = fake_working_tree_commit(sb->repo,
2805                                                      &sb->revs->diffopt,
2806                                                      path, sb->contents_from);
2807                 add_pending_object(sb->revs, &(sb->final->object), ":");
2808         }
2809
2810         if (sb->reverse && sb->revs->first_parent_only) {
2811                 final_commit = find_single_final(sb->revs, NULL);
2812                 if (!final_commit)
2813                         die(_("--reverse and --first-parent together require specified latest commit"));
2814         }
2815
2816         /*
2817          * If we have bottom, this will mark the ancestors of the
2818          * bottom commits we would reach while traversing as
2819          * uninteresting.
2820          */
2821         if (prepare_revision_walk(sb->revs))
2822                 die(_("revision walk setup failed"));
2823
2824         if (sb->reverse && sb->revs->first_parent_only) {
2825                 struct commit *c = final_commit;
2826
2827                 sb->revs->children.name = "children";
2828                 while (c->parents &&
2829                        !oideq(&c->object.oid, &sb->final->object.oid)) {
2830                         struct commit_list *l = xcalloc(1, sizeof(*l));
2831
2832                         l->item = c;
2833                         if (add_decoration(&sb->revs->children,
2834                                            &c->parents->item->object, l))
2835                                 BUG("not unique item in first-parent chain");
2836                         c = c->parents->item;
2837                 }
2838
2839                 if (!oideq(&c->object.oid, &sb->final->object.oid))
2840                         die(_("--reverse --first-parent together require range along first-parent chain"));
2841         }
2842
2843         if (is_null_oid(&sb->final->object.oid)) {
2844                 o = get_blame_suspects(sb->final);
2845                 sb->final_buf = xmemdupz(o->file.ptr, o->file.size);
2846                 sb->final_buf_size = o->file.size;
2847         }
2848         else {
2849                 o = get_origin(sb->final, path);
2850                 if (fill_blob_sha1_and_mode(sb->repo, o))
2851                         die(_("no such path %s in %s"), path, final_commit_name);
2852
2853                 if (sb->revs->diffopt.flags.allow_textconv &&
2854                     textconv_object(sb->repo, path, o->mode, &o->blob_oid, 1, (char **) &sb->final_buf,
2855                                     &sb->final_buf_size))
2856                         ;
2857                 else
2858                         sb->final_buf = read_object_file(&o->blob_oid, &type,
2859                                                          &sb->final_buf_size);
2860
2861                 if (!sb->final_buf)
2862                         die(_("cannot read blob %s for path %s"),
2863                             oid_to_hex(&o->blob_oid),
2864                             path);
2865         }
2866         sb->num_read_blob++;
2867         prepare_lines(sb);
2868
2869         if (orig)
2870                 *orig = o;
2871
2872         free((char *)final_commit_name);
2873 }
2874
2875
2876
2877 struct blame_entry *blame_entry_prepend(struct blame_entry *head,
2878                                         long start, long end,
2879                                         struct blame_origin *o)
2880 {
2881         struct blame_entry *new_head = xcalloc(1, sizeof(struct blame_entry));
2882         new_head->lno = start;
2883         new_head->num_lines = end - start;
2884         new_head->suspect = o;
2885         new_head->s_lno = start;
2886         new_head->next = head;
2887         blame_origin_incref(o);
2888         return new_head;
2889 }
2890
2891 void setup_blame_bloom_data(struct blame_scoreboard *sb,
2892                             const char *path)
2893 {
2894         struct blame_bloom_data *bd;
2895         struct bloom_filter_settings *bs;
2896
2897         if (!sb->repo->objects->commit_graph)
2898                 return;
2899
2900         bs = get_bloom_filter_settings(sb->repo);
2901         if (!bs)
2902                 return;
2903
2904         bd = xmalloc(sizeof(struct blame_bloom_data));
2905
2906         bd->settings = bs;
2907
2908         bd->alloc = 4;
2909         bd->nr = 0;
2910         ALLOC_ARRAY(bd->keys, bd->alloc);
2911
2912         add_bloom_key(bd, path);
2913
2914         sb->bloom_data = bd;
2915 }
2916
2917 void cleanup_scoreboard(struct blame_scoreboard *sb)
2918 {
2919         if (sb->bloom_data) {
2920                 int i;
2921                 for (i = 0; i < sb->bloom_data->nr; i++) {
2922                         free(sb->bloom_data->keys[i]->hashes);
2923                         free(sb->bloom_data->keys[i]);
2924                 }
2925                 free(sb->bloom_data->keys);
2926                 FREE_AND_NULL(sb->bloom_data);
2927
2928                 trace2_data_intmax("blame", sb->repo,
2929                                    "bloom/queries", bloom_count_queries);
2930                 trace2_data_intmax("blame", sb->repo,
2931                                    "bloom/response-no", bloom_count_no);
2932         }
2933 }