]>
Commit | Line | Data |
---|---|---|
ac1b3d12 LT |
1 | /* |
2 | * Helper functions for tree diff generation | |
3 | */ | |
4 | #include "cache.h" | |
5 | #include "diff.h" | |
750f7b66 | 6 | #include "diffcore.h" |
8e440259 | 7 | #include "tree.h" |
ac1b3d12 | 8 | |
72441af7 KS |
9 | /* |
10 | * internal mode marker, saying a tree entry != entry of tp[imin] | |
11 | * (see ll_diff_tree_paths for what it means there) | |
12 | * | |
13 | * we will update/use/emit entry for diff only with it unset. | |
14 | */ | |
15 | #define S_IFXMIN_NEQ S_DIFFTREE_IFXMIN_NEQ | |
16 | ||
b9081a65 | 17 | |
72441af7 KS |
18 | static struct combine_diff_path *ll_diff_tree_paths( |
19 | struct combine_diff_path *p, const unsigned char *sha1, | |
20 | const unsigned char **parents_sha1, int nparent, | |
21 | struct strbuf *base, struct diff_options *opt); | |
b9081a65 | 22 | static int ll_diff_tree_sha1(const unsigned char *old, const unsigned char *new, |
12cd8174 | 23 | struct strbuf *base, struct diff_options *opt); |
b9081a65 | 24 | |
9bc06196 KS |
25 | /* |
26 | * Compare two tree entries, taking into account only path/S_ISDIR(mode), | |
27 | * but not their sha1's. | |
28 | * | |
29 | * NOTE files and directories *always* compare differently, even when having | |
30 | * the same name - thanks to base_name_compare(). | |
6ca844e9 KS |
31 | * |
32 | * NOTE empty (=invalid) descriptor(s) take part in comparison as +infty, | |
33 | * so that they sort *after* valid tree entries. | |
34 | * | |
35 | * Due to this convention, if trees are scanned in sorted order, all | |
36 | * non-empty descriptors will be processed first. | |
9bc06196 KS |
37 | */ |
38 | static int tree_entry_pathcmp(struct tree_desc *t1, struct tree_desc *t2) | |
ac1b3d12 | 39 | { |
1a27a154 KS |
40 | struct name_entry *e1, *e2; |
41 | int cmp; | |
ac1b3d12 | 42 | |
6ca844e9 KS |
43 | /* empty descriptors sort after valid tree entries */ |
44 | if (!t1->size) | |
45 | return t2->size ? 1 : 0; | |
46 | else if (!t2->size) | |
47 | return -1; | |
48 | ||
1a27a154 KS |
49 | e1 = &t1->entry; |
50 | e2 = &t2->entry; | |
51 | cmp = base_name_compare(e1->path, tree_entry_len(e1), e1->mode, | |
52 | e2->path, tree_entry_len(e2), e2->mode); | |
903bba68 | 53 | return cmp; |
d00e980c KS |
54 | } |
55 | ||
56 | ||
72441af7 KS |
57 | /* |
58 | * convert path -> opt->diff_*() callbacks | |
59 | * | |
60 | * emits diff to first parent only, and tells diff tree-walker that we are done | |
61 | * with p and it can be freed. | |
62 | */ | |
63 | static int emit_diff_first_parent_only(struct diff_options *opt, struct combine_diff_path *p) | |
d00e980c | 64 | { |
72441af7 KS |
65 | struct combine_diff_parent *p0 = &p->parent[0]; |
66 | if (p->mode && p0->mode) { | |
67 | opt->change(opt, p0->mode, p->mode, p0->sha1, p->sha1, | |
68 | 1, 1, p->path, 0, 0); | |
d00e980c KS |
69 | } |
70 | else { | |
71 | const unsigned char *sha1; | |
72 | unsigned int mode; | |
73 | int addremove; | |
74 | ||
72441af7 | 75 | if (p->mode) { |
d00e980c | 76 | addremove = '+'; |
72441af7 KS |
77 | sha1 = p->sha1; |
78 | mode = p->mode; | |
d00e980c KS |
79 | } else { |
80 | addremove = '-'; | |
72441af7 KS |
81 | sha1 = p0->sha1; |
82 | mode = p0->mode; | |
fd55a19e | 83 | } |
d00e980c | 84 | |
72441af7 | 85 | opt->add_remove(opt, addremove, mode, sha1, 1, p->path, 0); |
ac1b3d12 | 86 | } |
72441af7 KS |
87 | |
88 | return 0; /* we are done with p */ | |
ac1b3d12 LT |
89 | } |
90 | ||
d00e980c | 91 | |
72441af7 KS |
92 | /* |
93 | * Make a new combine_diff_path from path/mode/sha1 | |
94 | * and append it to paths list tail. | |
95 | * | |
96 | * Memory for created elements could be reused: | |
97 | * | |
98 | * - if last->next == NULL, the memory is allocated; | |
99 | * | |
100 | * - if last->next != NULL, it is assumed that p=last->next was returned | |
101 | * earlier by this function, and p->next was *not* modified. | |
102 | * The memory is then reused from p. | |
103 | * | |
104 | * so for clients, | |
105 | * | |
106 | * - if you do need to keep the element | |
107 | * | |
108 | * p = path_appendnew(p, ...); | |
109 | * process(p); | |
110 | * p->next = NULL; | |
111 | * | |
112 | * - if you don't need to keep the element after processing | |
113 | * | |
114 | * pprev = p; | |
115 | * p = path_appendnew(p, ...); | |
116 | * process(p); | |
117 | * p = pprev; | |
118 | * ; don't forget to free tail->next in the end | |
119 | * | |
120 | * p->parent[] remains uninitialized. | |
121 | */ | |
122 | static struct combine_diff_path *path_appendnew(struct combine_diff_path *last, | |
123 | int nparent, const struct strbuf *base, const char *path, int pathlen, | |
124 | unsigned mode, const unsigned char *sha1) | |
125 | { | |
126 | struct combine_diff_path *p; | |
127 | int len = base->len + pathlen; | |
128 | int alloclen = combine_diff_path_size(nparent, len); | |
129 | ||
130 | /* if last->next is !NULL - it is a pre-allocated memory, we can reuse */ | |
131 | p = last->next; | |
132 | if (p && (alloclen > (intptr_t)p->next)) { | |
133 | free(p); | |
134 | p = NULL; | |
135 | } | |
136 | ||
137 | if (!p) { | |
138 | p = xmalloc(alloclen); | |
139 | ||
140 | /* | |
141 | * until we go to it next round, .next holds how many bytes we | |
142 | * allocated (for faster realloc - we don't need copying old data). | |
143 | */ | |
144 | p->next = (struct combine_diff_path *)(intptr_t)alloclen; | |
145 | } | |
146 | ||
147 | last->next = p; | |
148 | ||
149 | p->path = (char *)&(p->parent[nparent]); | |
150 | memcpy(p->path, base->buf, base->len); | |
151 | memcpy(p->path + base->len, path, pathlen); | |
152 | p->path[len] = 0; | |
153 | p->mode = mode; | |
154 | hashcpy(p->sha1, sha1 ? sha1 : null_sha1); | |
155 | ||
156 | return p; | |
157 | } | |
158 | ||
159 | /* | |
160 | * new path should be added to combine diff | |
d00e980c KS |
161 | * |
162 | * 3 cases on how/when it should be called and behaves: | |
163 | * | |
72441af7 KS |
164 | * t, !tp -> path added, all parents lack it |
165 | * !t, tp -> path removed from all parents | |
166 | * t, tp -> path modified/added | |
167 | * (M for tp[i]=tp[imin], A otherwise) | |
d00e980c | 168 | */ |
72441af7 KS |
169 | static struct combine_diff_path *emit_path(struct combine_diff_path *p, |
170 | struct strbuf *base, struct diff_options *opt, int nparent, | |
171 | struct tree_desc *t, struct tree_desc *tp, | |
172 | int imin) | |
ac1b3d12 LT |
173 | { |
174 | unsigned mode; | |
175 | const char *path; | |
72441af7 | 176 | const unsigned char *sha1; |
d00e980c | 177 | int pathlen; |
48932677 | 178 | int old_baselen = base->len; |
72441af7 | 179 | int i, isdir, recurse = 0, emitthis = 1; |
d00e980c KS |
180 | |
181 | /* at least something has to be valid */ | |
72441af7 | 182 | assert(t || tp); |
d00e980c | 183 | |
72441af7 | 184 | if (t) { |
d00e980c | 185 | /* path present in resulting tree */ |
72441af7 KS |
186 | sha1 = tree_entry_extract(t, &path, &mode); |
187 | pathlen = tree_entry_len(&t->entry); | |
d00e980c KS |
188 | isdir = S_ISDIR(mode); |
189 | } else { | |
190 | /* | |
72441af7 KS |
191 | * a path was removed - take path from imin parent. Also take |
192 | * mode from that parent, to decide on recursion(1). | |
193 | * | |
194 | * 1) all modes for tp[i]=tp[imin] should be the same wrt | |
195 | * S_ISDIR, thanks to base_name_compare(). | |
d00e980c | 196 | */ |
72441af7 KS |
197 | tree_entry_extract(&tp[imin], &path, &mode); |
198 | pathlen = tree_entry_len(&tp[imin].entry); | |
d00e980c KS |
199 | |
200 | isdir = S_ISDIR(mode); | |
72441af7 | 201 | sha1 = NULL; |
d00e980c KS |
202 | mode = 0; |
203 | } | |
204 | ||
205 | if (DIFF_OPT_TST(opt, RECURSIVE) && isdir) { | |
206 | recurse = 1; | |
207 | emitthis = DIFF_OPT_TST(opt, TREE_IN_RECURSIVE); | |
208 | } | |
ac1b3d12 | 209 | |
72441af7 KS |
210 | if (emitthis) { |
211 | int keep; | |
212 | struct combine_diff_path *pprev = p; | |
213 | p = path_appendnew(p, nparent, base, path, pathlen, mode, sha1); | |
214 | ||
215 | for (i = 0; i < nparent; ++i) { | |
216 | /* | |
217 | * tp[i] is valid, if present and if tp[i]==tp[imin] - | |
218 | * otherwise, we should ignore it. | |
219 | */ | |
220 | int tpi_valid = tp && !(tp[i].entry.mode & S_IFXMIN_NEQ); | |
221 | ||
222 | const unsigned char *sha1_i; | |
223 | unsigned mode_i; | |
224 | ||
225 | p->parent[i].status = | |
226 | !t ? DIFF_STATUS_DELETED : | |
227 | tpi_valid ? | |
228 | DIFF_STATUS_MODIFIED : | |
229 | DIFF_STATUS_ADDED; | |
230 | ||
231 | if (tpi_valid) { | |
232 | sha1_i = tp[i].entry.sha1; | |
233 | mode_i = tp[i].entry.mode; | |
234 | } | |
235 | else { | |
236 | sha1_i = NULL; | |
237 | mode_i = 0; | |
238 | } | |
239 | ||
240 | p->parent[i].mode = mode_i; | |
241 | hashcpy(p->parent[i].sha1, sha1_i ? sha1_i : null_sha1); | |
242 | } | |
df533f34 | 243 | |
72441af7 KS |
244 | keep = 1; |
245 | if (opt->pathchange) | |
246 | keep = opt->pathchange(opt, p); | |
247 | ||
248 | /* | |
249 | * If a path was filtered or consumed - we don't need to add it | |
250 | * to the list and can reuse its memory, leaving it as | |
251 | * pre-allocated element on the tail. | |
252 | * | |
253 | * On the other hand, if path needs to be kept, we need to | |
254 | * correct its .next to NULL, as it was pre-initialized to how | |
255 | * much memory was allocated. | |
256 | * | |
257 | * see path_appendnew() for details. | |
258 | */ | |
259 | if (!keep) | |
260 | p = pprev; | |
261 | else | |
262 | p->next = NULL; | |
263 | } | |
d00e980c KS |
264 | |
265 | if (recurse) { | |
72441af7 KS |
266 | const unsigned char **parents_sha1; |
267 | ||
268 | parents_sha1 = xalloca(nparent * sizeof(parents_sha1[0])); | |
269 | for (i = 0; i < nparent; ++i) { | |
270 | /* same rule as in emitthis */ | |
271 | int tpi_valid = tp && !(tp[i].entry.mode & S_IFXMIN_NEQ); | |
272 | ||
273 | parents_sha1[i] = tpi_valid ? tp[i].entry.sha1 | |
274 | : NULL; | |
275 | } | |
276 | ||
277 | strbuf_add(base, path, pathlen); | |
48932677 | 278 | strbuf_addch(base, '/'); |
72441af7 KS |
279 | p = ll_diff_tree_paths(p, sha1, parents_sha1, nparent, base, opt); |
280 | xalloca_free(parents_sha1); | |
d00e980c | 281 | } |
48932677 NTND |
282 | |
283 | strbuf_setlen(base, old_baselen); | |
72441af7 | 284 | return p; |
ac1b3d12 LT |
285 | } |
286 | ||
48932677 | 287 | static void skip_uninteresting(struct tree_desc *t, struct strbuf *base, |
e9066121 | 288 | struct diff_options *opt) |
5d865017 | 289 | { |
e9066121 KS |
290 | enum interesting match; |
291 | ||
5d865017 | 292 | while (t->size) { |
e9066121 KS |
293 | match = tree_entry_interesting(&t->entry, base, 0, &opt->pathspec); |
294 | if (match) { | |
295 | if (match == all_entries_not_interesting) | |
97d0b74a NTND |
296 | t->size = 0; |
297 | break; | |
5d865017 | 298 | } |
97d0b74a | 299 | update_tree_entry(t); |
5d865017 LT |
300 | } |
301 | } | |
302 | ||
72441af7 KS |
303 | |
304 | /* | |
305 | * generate paths for combined diff D(sha1,parents_sha1[]) | |
306 | * | |
307 | * Resulting paths are appended to combine_diff_path linked list, and also, are | |
308 | * emitted on the go via opt->pathchange() callback, so it is possible to | |
309 | * process the result as batch or incrementally. | |
310 | * | |
311 | * The paths are generated scanning new tree and all parents trees | |
312 | * simultaneously, similarly to what diff_tree() was doing for 2 trees. | |
313 | * The theory behind such scan is as follows: | |
314 | * | |
315 | * | |
316 | * D(T,P1...Pn) calculation scheme | |
317 | * ------------------------------- | |
318 | * | |
319 | * D(T,P1...Pn) = D(T,P1) ^ ... ^ D(T,Pn) (regarding resulting paths set) | |
320 | * | |
321 | * D(T,Pj) - diff between T..Pj | |
322 | * D(T,P1...Pn) - combined diff from T to parents P1,...,Pn | |
323 | * | |
324 | * | |
325 | * We start from all trees, which are sorted, and compare their entries in | |
326 | * lock-step: | |
327 | * | |
328 | * T P1 Pn | |
329 | * - - - | |
330 | * |t| |p1| |pn| | |
331 | * |-| |--| ... |--| imin = argmin(p1...pn) | |
332 | * | | | | | | | |
333 | * |-| |--| |--| | |
334 | * |.| |. | |. | | |
335 | * . . . | |
336 | * . . . | |
337 | * | |
338 | * at any time there could be 3 cases: | |
339 | * | |
340 | * 1) t < p[imin]; | |
341 | * 2) t > p[imin]; | |
342 | * 3) t = p[imin]. | |
343 | * | |
344 | * Schematic deduction of what every case means, and what to do, follows: | |
345 | * | |
346 | * 1) t < p[imin] -> ∀j t ∉ Pj -> "+t" ∈ D(T,Pj) -> D += "+t"; t↓ | |
347 | * | |
348 | * 2) t > p[imin] | |
349 | * | |
350 | * 2.1) ∃j: pj > p[imin] -> "-p[imin]" ∉ D(T,Pj) -> D += ø; ∀ pi=p[imin] pi↓ | |
351 | * 2.2) ∀i pi = p[imin] -> pi ∉ T -> "-pi" ∈ D(T,Pi) -> D += "-p[imin]"; ∀i pi↓ | |
352 | * | |
353 | * 3) t = p[imin] | |
354 | * | |
355 | * 3.1) ∃j: pj > p[imin] -> "+t" ∈ D(T,Pj) -> only pi=p[imin] remains to investigate | |
356 | * 3.2) pi = p[imin] -> investigate δ(t,pi) | |
357 | * | | |
358 | * | | |
359 | * v | |
360 | * | |
361 | * 3.1+3.2) looking at δ(t,pi) ∀i: pi=p[imin] - if all != ø -> | |
362 | * | |
363 | * ⎧δ(t,pi) - if pi=p[imin] | |
364 | * -> D += ⎨ | |
365 | * ⎩"+t" - if pi>p[imin] | |
366 | * | |
367 | * | |
368 | * in any case t↓ ∀ pi=p[imin] pi↓ | |
369 | * | |
370 | * | |
371 | * ~~~~~~~~ | |
372 | * | |
373 | * NOTE | |
374 | * | |
375 | * Usual diff D(A,B) is by definition the same as combined diff D(A,[B]), | |
376 | * so this diff paths generator can, and is used, for plain diffs | |
377 | * generation too. | |
378 | * | |
379 | * Please keep attention to the common D(A,[B]) case when working on the | |
380 | * code, in order not to slow it down. | |
381 | * | |
382 | * NOTE | |
383 | * nparent must be > 0. | |
384 | */ | |
385 | ||
386 | ||
387 | /* ∀ pi=p[imin] pi↓ */ | |
388 | static inline void update_tp_entries(struct tree_desc *tp, int nparent) | |
ac1b3d12 | 389 | { |
72441af7 KS |
390 | int i; |
391 | for (i = 0; i < nparent; ++i) | |
392 | if (!(tp[i].entry.mode & S_IFXMIN_NEQ)) | |
393 | update_tree_entry(&tp[i]); | |
394 | } | |
304de2d2 | 395 | |
72441af7 KS |
396 | static struct combine_diff_path *ll_diff_tree_paths( |
397 | struct combine_diff_path *p, const unsigned char *sha1, | |
398 | const unsigned char **parents_sha1, int nparent, | |
399 | struct strbuf *base, struct diff_options *opt) | |
400 | { | |
401 | struct tree_desc t, *tp; | |
402 | void *ttree, **tptree; | |
403 | int i; | |
404 | ||
405 | tp = xalloca(nparent * sizeof(tp[0])); | |
406 | tptree = xalloca(nparent * sizeof(tptree[0])); | |
407 | ||
408 | /* | |
409 | * load parents first, as they are probably already cached. | |
410 | * | |
411 | * ( log_tree_diff() parses commit->parent before calling here via | |
412 | * diff_tree_sha1(parent, commit) ) | |
413 | */ | |
414 | for (i = 0; i < nparent; ++i) | |
415 | tptree[i] = fill_tree_descriptor(&tp[i], parents_sha1[i]); | |
416 | ttree = fill_tree_descriptor(&t, sha1); | |
52894e70 | 417 | |
bc96cc87 NTND |
418 | /* Enable recursion indefinitely */ |
419 | opt->pathspec.recursive = DIFF_OPT_TST(opt, RECURSIVE); | |
bc96cc87 | 420 | |
5d865017 | 421 | for (;;) { |
72441af7 | 422 | int imin, cmp; |
903bba68 | 423 | |
28b9264d | 424 | if (diff_can_quit_early(opt)) |
822cac01 | 425 | break; |
72441af7 | 426 | |
66f13625 | 427 | if (opt->pathspec.nr) { |
72441af7 KS |
428 | skip_uninteresting(&t, base, opt); |
429 | for (i = 0; i < nparent; i++) | |
430 | skip_uninteresting(&tp[i], base, opt); | |
431 | } | |
432 | ||
433 | /* comparing is finished when all trees are done */ | |
434 | if (!t.size) { | |
435 | int done = 1; | |
436 | for (i = 0; i < nparent; ++i) | |
437 | if (tp[i].size) { | |
438 | done = 0; | |
439 | break; | |
440 | } | |
441 | if (done) | |
442 | break; | |
443 | } | |
444 | ||
445 | /* | |
446 | * lookup imin = argmin(p1...pn), | |
447 | * mark entries whether they =p[imin] along the way | |
448 | */ | |
449 | imin = 0; | |
450 | tp[0].entry.mode &= ~S_IFXMIN_NEQ; | |
451 | ||
452 | for (i = 1; i < nparent; ++i) { | |
453 | cmp = tree_entry_pathcmp(&tp[i], &tp[imin]); | |
454 | if (cmp < 0) { | |
455 | imin = i; | |
456 | tp[i].entry.mode &= ~S_IFXMIN_NEQ; | |
457 | } | |
458 | else if (cmp == 0) { | |
459 | tp[i].entry.mode &= ~S_IFXMIN_NEQ; | |
460 | } | |
461 | else { | |
462 | tp[i].entry.mode |= S_IFXMIN_NEQ; | |
463 | } | |
ac1b3d12 | 464 | } |
5dfb2bbd | 465 | |
72441af7 KS |
466 | /* fixup markings for entries before imin */ |
467 | for (i = 0; i < imin; ++i) | |
468 | tp[i].entry.mode |= S_IFXMIN_NEQ; /* pi > p[imin] */ | |
5dfb2bbd | 469 | |
903bba68 | 470 | |
72441af7 KS |
471 | |
472 | /* compare t vs p[imin] */ | |
473 | cmp = tree_entry_pathcmp(&t, &tp[imin]); | |
474 | ||
475 | /* t = p[imin] */ | |
476 | if (cmp == 0) { | |
477 | /* are either pi > p[imin] or diff(t,pi) != ø ? */ | |
478 | if (!DIFF_OPT_TST(opt, FIND_COPIES_HARDER)) { | |
479 | for (i = 0; i < nparent; ++i) { | |
480 | /* p[i] > p[imin] */ | |
481 | if (tp[i].entry.mode & S_IFXMIN_NEQ) | |
482 | continue; | |
483 | ||
484 | /* diff(t,pi) != ø */ | |
485 | if (hashcmp(t.entry.sha1, tp[i].entry.sha1) || | |
486 | (t.entry.mode != tp[i].entry.mode)) | |
487 | continue; | |
488 | ||
489 | goto skip_emit_t_tp; | |
490 | } | |
491 | } | |
492 | ||
493 | /* D += {δ(t,pi) if pi=p[imin]; "+a" if pi > p[imin]} */ | |
494 | p = emit_path(p, base, opt, nparent, | |
495 | &t, tp, imin); | |
496 | ||
497 | skip_emit_t_tp: | |
498 | /* t↓, ∀ pi=p[imin] pi↓ */ | |
499 | update_tree_entry(&t); | |
500 | update_tp_entries(tp, nparent); | |
5dfb2bbd KS |
501 | } |
502 | ||
72441af7 | 503 | /* t < p[imin] */ |
5dfb2bbd | 504 | else if (cmp < 0) { |
72441af7 KS |
505 | /* D += "+t" */ |
506 | p = emit_path(p, base, opt, nparent, | |
507 | &t, /*tp=*/NULL, -1); | |
508 | ||
509 | /* t↓ */ | |
510 | update_tree_entry(&t); | |
5dfb2bbd KS |
511 | } |
512 | ||
72441af7 | 513 | /* t > p[imin] */ |
5dfb2bbd | 514 | else { |
72441af7 KS |
515 | /* ∀i pi=p[imin] -> D += "-p[imin]" */ |
516 | if (!DIFF_OPT_TST(opt, FIND_COPIES_HARDER)) { | |
517 | for (i = 0; i < nparent; ++i) | |
518 | if (tp[i].entry.mode & S_IFXMIN_NEQ) | |
519 | goto skip_emit_tp; | |
520 | } | |
521 | ||
522 | p = emit_path(p, base, opt, nparent, | |
523 | /*t=*/NULL, tp, imin); | |
524 | ||
525 | skip_emit_tp: | |
526 | /* ∀ pi=p[imin] pi↓ */ | |
527 | update_tp_entries(tp, nparent); | |
ac1b3d12 | 528 | } |
ac1b3d12 | 529 | } |
48932677 | 530 | |
72441af7 KS |
531 | free(ttree); |
532 | for (i = nparent-1; i >= 0; i--) | |
533 | free(tptree[i]); | |
534 | xalloca_free(tptree); | |
535 | xalloca_free(tp); | |
536 | ||
537 | return p; | |
538 | } | |
539 | ||
540 | struct combine_diff_path *diff_tree_paths( | |
541 | struct combine_diff_path *p, const unsigned char *sha1, | |
542 | const unsigned char **parents_sha1, int nparent, | |
543 | struct strbuf *base, struct diff_options *opt) | |
544 | { | |
545 | p = ll_diff_tree_paths(p, sha1, parents_sha1, nparent, base, opt); | |
546 | ||
547 | /* | |
548 | * free pre-allocated last element, if any | |
549 | * (see path_appendnew() for details about why) | |
550 | */ | |
551 | if (p->next) { | |
552 | free(p->next); | |
553 | p->next = NULL; | |
554 | } | |
555 | ||
556 | return p; | |
ac1b3d12 LT |
557 | } |
558 | ||
750f7b66 LT |
559 | /* |
560 | * Does it look like the resulting diff might be due to a rename? | |
561 | * - single entry | |
562 | * - not a valid previous file | |
563 | */ | |
564 | static inline int diff_might_be_rename(void) | |
565 | { | |
566 | return diff_queued_diff.nr == 1 && | |
567 | !DIFF_FILE_VALID(diff_queued_diff.queue[0]->one); | |
568 | } | |
569 | ||
12cd8174 | 570 | static void try_to_follow_renames(const unsigned char *old, const unsigned char *new, struct strbuf *base, struct diff_options *opt) |
750f7b66 LT |
571 | { |
572 | struct diff_options diff_opts; | |
9f38e1ef LT |
573 | struct diff_queue_struct *q = &diff_queued_diff; |
574 | struct diff_filepair *choice; | |
750f7b66 LT |
575 | int i; |
576 | ||
8f4f8f45 NTND |
577 | /* |
578 | * follow-rename code is very specific, we need exactly one | |
579 | * path. Magic that matches more than one path is not | |
580 | * supported. | |
581 | */ | |
5c6933d2 | 582 | GUARD_PATHSPEC(&opt->pathspec, PATHSPEC_FROMTOP | PATHSPEC_LITERAL); |
8f4f8f45 NTND |
583 | #if 0 |
584 | /* | |
585 | * We should reject wildcards as well. Unfortunately we | |
586 | * haven't got a reliable way to detect that 'foo\*bar' in | |
587 | * fact has no wildcards. nowildcard_len is merely a hint for | |
588 | * optimization. Let it slip for now until wildmatch is taught | |
589 | * about dry-run mode and returns wildcard info. | |
590 | */ | |
591 | if (opt->pathspec.has_wildcard) | |
592 | die("BUG:%s:%d: wildcards are not supported", | |
593 | __FILE__, __LINE__); | |
594 | #endif | |
595 | ||
9f38e1ef LT |
596 | /* Remove the file creation entry from the diff queue, and remember it */ |
597 | choice = q->queue[0]; | |
598 | q->nr = 0; | |
599 | ||
750f7b66 | 600 | diff_setup(&diff_opts); |
8f67f8ae | 601 | DIFF_OPT_SET(&diff_opts, RECURSIVE); |
0cdca133 | 602 | DIFF_OPT_SET(&diff_opts, FIND_COPIES_HARDER); |
750f7b66 | 603 | diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT; |
61588ccf | 604 | diff_opts.single_follow = opt->pathspec.items[0].match; |
6dd4b66f | 605 | diff_opts.break_opt = opt->break_opt; |
dd98d88b | 606 | diff_opts.rename_score = opt->rename_score; |
28452655 | 607 | diff_setup_done(&diff_opts); |
52894e70 | 608 | ll_diff_tree_sha1(old, new, base, &diff_opts); |
750f7b66 | 609 | diffcore_std(&diff_opts); |
bd1928df | 610 | free_pathspec(&diff_opts.pathspec); |
750f7b66 | 611 | |
9f38e1ef | 612 | /* Go through the new set of filepairing, and see if we find a more interesting one */ |
44c48a90 | 613 | opt->found_follow = 0; |
9f38e1ef LT |
614 | for (i = 0; i < q->nr; i++) { |
615 | struct diff_filepair *p = q->queue[i]; | |
750f7b66 LT |
616 | |
617 | /* | |
618 | * Found a source? Not only do we use that for the new | |
9f38e1ef | 619 | * diff_queued_diff, we will also use that as the path in |
750f7b66 LT |
620 | * the future! |
621 | */ | |
66f13625 | 622 | if ((p->status == 'R' || p->status == 'C') && |
61588ccf | 623 | !strcmp(p->two->path, opt->pathspec.items[0].match)) { |
9a087274 NTND |
624 | const char *path[2]; |
625 | ||
9f38e1ef LT |
626 | /* Switch the file-pairs around */ |
627 | q->queue[i] = choice; | |
628 | choice = p; | |
629 | ||
630 | /* Update the path we use from now on.. */ | |
9a087274 NTND |
631 | path[0] = p->one->path; |
632 | path[1] = NULL; | |
bd1928df | 633 | free_pathspec(&opt->pathspec); |
4a2d5ae2 NTND |
634 | parse_pathspec(&opt->pathspec, |
635 | PATHSPEC_ALL_MAGIC & ~PATHSPEC_LITERAL, | |
636 | PATHSPEC_LITERAL_PATH, "", path); | |
44c48a90 JH |
637 | |
638 | /* | |
639 | * The caller expects us to return a set of vanilla | |
640 | * filepairs to let a later call to diffcore_std() | |
641 | * it makes to sort the renames out (among other | |
642 | * things), but we already have found renames | |
643 | * ourselves; signal diffcore_std() not to muck with | |
644 | * rename information. | |
645 | */ | |
646 | opt->found_follow = 1; | |
750f7b66 LT |
647 | break; |
648 | } | |
649 | } | |
650 | ||
651 | /* | |
3ea3c215 | 652 | * Then, discard all the non-relevant file pairs... |
9f38e1ef LT |
653 | */ |
654 | for (i = 0; i < q->nr; i++) { | |
655 | struct diff_filepair *p = q->queue[i]; | |
656 | diff_free_filepair(p); | |
657 | } | |
658 | ||
659 | /* | |
660 | * .. and re-instate the one we want (which might be either the | |
661 | * original one, or the rename/copy we found) | |
750f7b66 | 662 | */ |
9f38e1ef LT |
663 | q->queue[0] = choice; |
664 | q->nr = 1; | |
750f7b66 LT |
665 | } |
666 | ||
72441af7 KS |
667 | static int ll_diff_tree_sha1(const unsigned char *old, const unsigned char *new, |
668 | struct strbuf *base, struct diff_options *opt) | |
669 | { | |
670 | struct combine_diff_path phead, *p; | |
671 | pathchange_fn_t pathchange_old = opt->pathchange; | |
672 | ||
673 | phead.next = NULL; | |
674 | opt->pathchange = emit_diff_first_parent_only; | |
675 | diff_tree_paths(&phead, new, &old, 1, base, opt); | |
676 | ||
677 | for (p = phead.next; p;) { | |
678 | struct combine_diff_path *pprev = p; | |
679 | p = p->next; | |
680 | free(pprev); | |
681 | } | |
682 | ||
683 | opt->pathchange = pathchange_old; | |
684 | return 0; | |
685 | } | |
686 | ||
12cd8174 | 687 | int diff_tree_sha1(const unsigned char *old, const unsigned char *new, const char *base_str, struct diff_options *opt) |
ac1b3d12 | 688 | { |
12cd8174 | 689 | struct strbuf base; |
ac1b3d12 LT |
690 | int retval; |
691 | ||
12cd8174 KS |
692 | strbuf_init(&base, PATH_MAX); |
693 | strbuf_addstr(&base, base_str); | |
694 | ||
695 | retval = ll_diff_tree_sha1(old, new, &base, opt); | |
696 | if (!*base_str && DIFF_OPT_TST(opt, FOLLOW_RENAMES) && diff_might_be_rename()) | |
697 | try_to_follow_renames(old, new, &base, opt); | |
698 | ||
699 | strbuf_release(&base); | |
52894e70 | 700 | |
ac1b3d12 LT |
701 | return retval; |
702 | } | |
703 | ||
2b60356d RS |
704 | int diff_root_tree_sha1(const unsigned char *new, const char *base, struct diff_options *opt) |
705 | { | |
0b707c33 | 706 | return diff_tree_sha1(NULL, new, base, opt); |
2b60356d | 707 | } |