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