Portable alloca for Git
[git/git.git] / tree-diff.c
CommitLineData
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
b9081a65
KS
9
10static int ll_diff_tree_sha1(const unsigned char *old, const unsigned char *new,
12cd8174 11 struct strbuf *base, struct diff_options *opt);
b9081a65 12
9bc06196
KS
13/*
14 * Compare two tree entries, taking into account only path/S_ISDIR(mode),
15 * but not their sha1's.
16 *
17 * NOTE files and directories *always* compare differently, even when having
18 * the same name - thanks to base_name_compare().
6ca844e9
KS
19 *
20 * NOTE empty (=invalid) descriptor(s) take part in comparison as +infty,
21 * so that they sort *after* valid tree entries.
22 *
23 * Due to this convention, if trees are scanned in sorted order, all
24 * non-empty descriptors will be processed first.
9bc06196
KS
25 */
26static int tree_entry_pathcmp(struct tree_desc *t1, struct tree_desc *t2)
ac1b3d12 27{
1a27a154
KS
28 struct name_entry *e1, *e2;
29 int cmp;
ac1b3d12 30
6ca844e9
KS
31 /* empty descriptors sort after valid tree entries */
32 if (!t1->size)
33 return t2->size ? 1 : 0;
34 else if (!t2->size)
35 return -1;
36
1a27a154
KS
37 e1 = &t1->entry;
38 e2 = &t2->entry;
39 cmp = base_name_compare(e1->path, tree_entry_len(e1), e1->mode,
40 e2->path, tree_entry_len(e2), e2->mode);
903bba68 41 return cmp;
d00e980c
KS
42}
43
44
45/* convert path, t1/t2 -> opt->diff_*() callbacks */
46static void emit_diff(struct diff_options *opt, struct strbuf *path,
47 struct tree_desc *t1, struct tree_desc *t2)
48{
49 unsigned int mode1 = t1 ? t1->entry.mode : 0;
50 unsigned int mode2 = t2 ? t2->entry.mode : 0;
51
52 if (mode1 && mode2) {
53 opt->change(opt, mode1, mode2, t1->entry.sha1, t2->entry.sha1,
54 1, 1, path->buf, 0, 0);
55 }
56 else {
57 const unsigned char *sha1;
58 unsigned int mode;
59 int addremove;
60
61 if (mode2) {
62 addremove = '+';
63 sha1 = t2->entry.sha1;
64 mode = mode2;
65 } else {
66 addremove = '-';
67 sha1 = t1->entry.sha1;
68 mode = mode1;
fd55a19e 69 }
d00e980c
KS
70
71 opt->add_remove(opt, addremove, mode, sha1, 1, path->buf, 0);
ac1b3d12 72 }
ac1b3d12
LT
73}
74
d00e980c
KS
75
76/* new path should be added to diff
77 *
78 * 3 cases on how/when it should be called and behaves:
79 *
80 * !t1, t2 -> path added, parent lacks it
81 * t1, !t2 -> path removed from parent
82 * t1, t2 -> path modified
83 */
84static void show_path(struct strbuf *base, struct diff_options *opt,
85 struct tree_desc *t1, struct tree_desc *t2)
ac1b3d12
LT
86{
87 unsigned mode;
88 const char *path;
d00e980c 89 int pathlen;
48932677 90 int old_baselen = base->len;
d00e980c
KS
91 int isdir, recurse = 0, emitthis = 1;
92
93 /* at least something has to be valid */
94 assert(t1 || t2);
95
96 if (t2) {
97 /* path present in resulting tree */
98 tree_entry_extract(t2, &path, &mode);
99 pathlen = tree_entry_len(&t2->entry);
100 isdir = S_ISDIR(mode);
101 } else {
102 /*
103 * a path was removed - take path from parent. Also take
104 * mode from parent, to decide on recursion.
105 */
106 tree_entry_extract(t1, &path, &mode);
107 pathlen = tree_entry_len(&t1->entry);
108
109 isdir = S_ISDIR(mode);
110 mode = 0;
111 }
112
113 if (DIFF_OPT_TST(opt, RECURSIVE) && isdir) {
114 recurse = 1;
115 emitthis = DIFF_OPT_TST(opt, TREE_IN_RECURSIVE);
116 }
ac1b3d12 117
48932677 118 strbuf_add(base, path, pathlen);
df533f34 119
d00e980c
KS
120 if (emitthis)
121 emit_diff(opt, base, t1, t2);
122
123 if (recurse) {
48932677 124 strbuf_addch(base, '/');
b9081a65 125 ll_diff_tree_sha1(t1 ? t1->entry.sha1 : NULL,
12cd8174 126 t2 ? t2->entry.sha1 : NULL, base, opt);
d00e980c 127 }
48932677
NTND
128
129 strbuf_setlen(base, old_baselen);
ac1b3d12
LT
130}
131
48932677 132static void skip_uninteresting(struct tree_desc *t, struct strbuf *base,
e9066121 133 struct diff_options *opt)
5d865017 134{
e9066121
KS
135 enum interesting match;
136
5d865017 137 while (t->size) {
e9066121
KS
138 match = tree_entry_interesting(&t->entry, base, 0, &opt->pathspec);
139 if (match) {
140 if (match == all_entries_not_interesting)
97d0b74a
NTND
141 t->size = 0;
142 break;
5d865017 143 }
97d0b74a 144 update_tree_entry(t);
5d865017
LT
145 }
146}
147
52894e70 148static int ll_diff_tree_sha1(const unsigned char *old, const unsigned char *new,
12cd8174 149 struct strbuf *base, struct diff_options *opt)
ac1b3d12 150{
52894e70
KS
151 struct tree_desc t1, t2;
152 void *t1tree, *t2tree;
304de2d2 153
52894e70
KS
154 t1tree = fill_tree_descriptor(&t1, old);
155 t2tree = fill_tree_descriptor(&t2, new);
156
bc96cc87
NTND
157 /* Enable recursion indefinitely */
158 opt->pathspec.recursive = DIFF_OPT_TST(opt, RECURSIVE);
bc96cc87 159
5d865017 160 for (;;) {
903bba68
KS
161 int cmp;
162
28b9264d 163 if (diff_can_quit_early(opt))
822cac01 164 break;
66f13625 165 if (opt->pathspec.nr) {
12cd8174
KS
166 skip_uninteresting(&t1, base, opt);
167 skip_uninteresting(&t2, base, opt);
ac1b3d12 168 }
52894e70 169 if (!t1.size && !t2.size)
6ca844e9 170 break;
5dfb2bbd 171
52894e70 172 cmp = tree_entry_pathcmp(&t1, &t2);
5dfb2bbd
KS
173
174 /* t1 = t2 */
175 if (cmp == 0) {
903bba68 176 if (DIFF_OPT_TST(opt, FIND_COPIES_HARDER) ||
52894e70
KS
177 hashcmp(t1.entry.sha1, t2.entry.sha1) ||
178 (t1.entry.mode != t2.entry.mode))
12cd8174 179 show_path(base, opt, &t1, &t2);
903bba68 180
52894e70
KS
181 update_tree_entry(&t1);
182 update_tree_entry(&t2);
5dfb2bbd
KS
183 }
184
185 /* t1 < t2 */
186 else if (cmp < 0) {
12cd8174 187 show_path(base, opt, &t1, /*t2=*/NULL);
52894e70 188 update_tree_entry(&t1);
5dfb2bbd
KS
189 }
190
191 /* t1 > t2 */
192 else {
12cd8174 193 show_path(base, opt, /*t1=*/NULL, &t2);
52894e70 194 update_tree_entry(&t2);
ac1b3d12 195 }
ac1b3d12 196 }
48932677 197
52894e70
KS
198 free(t2tree);
199 free(t1tree);
ac1b3d12
LT
200 return 0;
201}
202
750f7b66
LT
203/*
204 * Does it look like the resulting diff might be due to a rename?
205 * - single entry
206 * - not a valid previous file
207 */
208static inline int diff_might_be_rename(void)
209{
210 return diff_queued_diff.nr == 1 &&
211 !DIFF_FILE_VALID(diff_queued_diff.queue[0]->one);
212}
213
12cd8174 214static void try_to_follow_renames(const unsigned char *old, const unsigned char *new, struct strbuf *base, struct diff_options *opt)
750f7b66
LT
215{
216 struct diff_options diff_opts;
9f38e1ef
LT
217 struct diff_queue_struct *q = &diff_queued_diff;
218 struct diff_filepair *choice;
750f7b66
LT
219 int i;
220
8f4f8f45
NTND
221 /*
222 * follow-rename code is very specific, we need exactly one
223 * path. Magic that matches more than one path is not
224 * supported.
225 */
5c6933d2 226 GUARD_PATHSPEC(&opt->pathspec, PATHSPEC_FROMTOP | PATHSPEC_LITERAL);
8f4f8f45
NTND
227#if 0
228 /*
229 * We should reject wildcards as well. Unfortunately we
230 * haven't got a reliable way to detect that 'foo\*bar' in
231 * fact has no wildcards. nowildcard_len is merely a hint for
232 * optimization. Let it slip for now until wildmatch is taught
233 * about dry-run mode and returns wildcard info.
234 */
235 if (opt->pathspec.has_wildcard)
236 die("BUG:%s:%d: wildcards are not supported",
237 __FILE__, __LINE__);
238#endif
239
9f38e1ef
LT
240 /* Remove the file creation entry from the diff queue, and remember it */
241 choice = q->queue[0];
242 q->nr = 0;
243
750f7b66 244 diff_setup(&diff_opts);
8f67f8ae 245 DIFF_OPT_SET(&diff_opts, RECURSIVE);
0cdca133 246 DIFF_OPT_SET(&diff_opts, FIND_COPIES_HARDER);
750f7b66 247 diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;
61588ccf 248 diff_opts.single_follow = opt->pathspec.items[0].match;
6dd4b66f 249 diff_opts.break_opt = opt->break_opt;
dd98d88b 250 diff_opts.rename_score = opt->rename_score;
28452655 251 diff_setup_done(&diff_opts);
52894e70 252 ll_diff_tree_sha1(old, new, base, &diff_opts);
750f7b66 253 diffcore_std(&diff_opts);
bd1928df 254 free_pathspec(&diff_opts.pathspec);
750f7b66 255
9f38e1ef 256 /* Go through the new set of filepairing, and see if we find a more interesting one */
44c48a90 257 opt->found_follow = 0;
9f38e1ef
LT
258 for (i = 0; i < q->nr; i++) {
259 struct diff_filepair *p = q->queue[i];
750f7b66
LT
260
261 /*
262 * Found a source? Not only do we use that for the new
9f38e1ef 263 * diff_queued_diff, we will also use that as the path in
750f7b66
LT
264 * the future!
265 */
66f13625 266 if ((p->status == 'R' || p->status == 'C') &&
61588ccf 267 !strcmp(p->two->path, opt->pathspec.items[0].match)) {
9a087274
NTND
268 const char *path[2];
269
9f38e1ef
LT
270 /* Switch the file-pairs around */
271 q->queue[i] = choice;
272 choice = p;
273
274 /* Update the path we use from now on.. */
9a087274
NTND
275 path[0] = p->one->path;
276 path[1] = NULL;
bd1928df 277 free_pathspec(&opt->pathspec);
4a2d5ae2
NTND
278 parse_pathspec(&opt->pathspec,
279 PATHSPEC_ALL_MAGIC & ~PATHSPEC_LITERAL,
280 PATHSPEC_LITERAL_PATH, "", path);
44c48a90
JH
281
282 /*
283 * The caller expects us to return a set of vanilla
284 * filepairs to let a later call to diffcore_std()
285 * it makes to sort the renames out (among other
286 * things), but we already have found renames
287 * ourselves; signal diffcore_std() not to muck with
288 * rename information.
289 */
290 opt->found_follow = 1;
750f7b66
LT
291 break;
292 }
293 }
294
295 /*
3ea3c215 296 * Then, discard all the non-relevant file pairs...
9f38e1ef
LT
297 */
298 for (i = 0; i < q->nr; i++) {
299 struct diff_filepair *p = q->queue[i];
300 diff_free_filepair(p);
301 }
302
303 /*
304 * .. and re-instate the one we want (which might be either the
305 * original one, or the rename/copy we found)
750f7b66 306 */
9f38e1ef
LT
307 q->queue[0] = choice;
308 q->nr = 1;
750f7b66
LT
309}
310
12cd8174 311int diff_tree_sha1(const unsigned char *old, const unsigned char *new, const char *base_str, struct diff_options *opt)
ac1b3d12 312{
12cd8174 313 struct strbuf base;
ac1b3d12
LT
314 int retval;
315
12cd8174
KS
316 strbuf_init(&base, PATH_MAX);
317 strbuf_addstr(&base, base_str);
318
319 retval = ll_diff_tree_sha1(old, new, &base, opt);
320 if (!*base_str && DIFF_OPT_TST(opt, FOLLOW_RENAMES) && diff_might_be_rename())
321 try_to_follow_renames(old, new, &base, opt);
322
323 strbuf_release(&base);
52894e70 324
ac1b3d12
LT
325 return retval;
326}
327
2b60356d
RS
328int diff_root_tree_sha1(const unsigned char *new, const char *base, struct diff_options *opt)
329{
0b707c33 330 return diff_tree_sha1(NULL, new, base, opt);
2b60356d 331}