glossary: define pathspec
[git/git.git] / tree-walk.c
CommitLineData
1b0c7174
JH
1#include "cache.h"
2#include "tree-walk.h"
e6c111b4 3#include "unpack-trees.h"
8e440259 4#include "tree.h"
1b0c7174 5
4651ece8
LT
6static const char *get_mode(const char *str, unsigned int *modep)
7{
8 unsigned char c;
9 unsigned int mode = 0;
10
64cc1c09
MK
11 if (*str == ' ')
12 return NULL;
13
4651ece8
LT
14 while ((c = *str++) != ' ') {
15 if (c < '0' || c > '7')
16 return NULL;
17 mode = (mode << 3) + (c - '0');
18 }
19 *modep = mode;
20 return str;
21}
22
64cc1c09 23static void decode_tree_entry(struct tree_desc *desc, const char *buf, unsigned long size)
4651ece8
LT
24{
25 const char *path;
26 unsigned int mode, len;
27
64cc1c09
MK
28 if (size < 24 || buf[size - 21])
29 die("corrupt tree file");
30
4651ece8 31 path = get_mode(buf, &mode);
64cc1c09 32 if (!path || !*path)
4651ece8
LT
33 die("corrupt tree file");
34 len = strlen(path) + 1;
35
36 /* Initialize the descriptor entry */
37 desc->entry.path = path;
38 desc->entry.mode = mode;
39 desc->entry.sha1 = (const unsigned char *)(path + len);
40}
41
6fda5e51
LT
42void init_tree_desc(struct tree_desc *desc, const void *buffer, unsigned long size)
43{
44 desc->buffer = buffer;
45 desc->size = size;
4651ece8
LT
46 if (size)
47 decode_tree_entry(desc, buffer, size);
6fda5e51
LT
48}
49
1b0c7174
JH
50void *fill_tree_descriptor(struct tree_desc *desc, const unsigned char *sha1)
51{
52 unsigned long size = 0;
53 void *buf = NULL;
54
55 if (sha1) {
8e440259 56 buf = read_object_with_reference(sha1, tree_type, &size, NULL);
1b0c7174
JH
57 if (!buf)
58 die("unable to read tree %s", sha1_to_hex(sha1));
59 }
6fda5e51 60 init_tree_desc(desc, buf, size);
1b0c7174
JH
61 return buf;
62}
63
1b0c7174
JH
64static void entry_clear(struct name_entry *a)
65{
66 memset(a, 0, sizeof(*a));
67}
68
69static void entry_extract(struct tree_desc *t, struct name_entry *a)
70{
4651ece8 71 *a = t->entry;
1b0c7174
JH
72}
73
74void update_tree_entry(struct tree_desc *desc)
75{
6fda5e51 76 const void *buf = desc->buffer;
4651ece8 77 const unsigned char *end = desc->entry.sha1 + 20;
1b0c7174 78 unsigned long size = desc->size;
4651ece8 79 unsigned long len = end - (const unsigned char *)buf;
1b0c7174
JH
80
81 if (size < len)
82 die("corrupt tree file");
4651ece8
LT
83 buf = end;
84 size -= len;
85 desc->buffer = buf;
86 desc->size = size;
87 if (size)
88 decode_tree_entry(desc, buf, size);
1b0c7174
JH
89}
90
4c068a98
LT
91int tree_entry(struct tree_desc *desc, struct name_entry *entry)
92{
4651ece8 93 if (!desc->size)
4c068a98
LT
94 return 0;
95
4651ece8
LT
96 *entry = desc->entry;
97 update_tree_entry(desc);
4c068a98
LT
98 return 1;
99}
100
40d934df
LT
101void setup_traverse_info(struct traverse_info *info, const char *base)
102{
103 int pathlen = strlen(base);
bcbe5a51 104 static struct traverse_info dummy;
40d934df
LT
105
106 memset(info, 0, sizeof(*info));
107 if (pathlen && base[pathlen-1] == '/')
108 pathlen--;
109 info->pathlen = pathlen ? pathlen + 1 : 0;
110 info->name.path = base;
111 info->name.sha1 = (void *)(base + pathlen + 1);
bcbe5a51
LT
112 if (pathlen)
113 info->prev = &dummy;
40d934df
LT
114}
115
116char *make_traverse_path(char *path, const struct traverse_info *info, const struct name_entry *n)
117{
118 int len = tree_entry_len(n->path, n->sha1);
119 int pathlen = info->pathlen;
120
121 path[pathlen + len] = 0;
122 for (;;) {
123 memcpy(path + pathlen, n->path, len);
124 if (!pathlen)
125 break;
126 path[--pathlen] = '/';
127 n = &info->name;
128 len = tree_entry_len(n->path, n->sha1);
129 info = info->prev;
130 pathlen -= len;
131 }
132 return path;
133}
134
1ee26571
JH
135struct tree_desc_skip {
136 struct tree_desc_skip *prev;
137 const void *ptr;
138};
139
140struct tree_desc_x {
141 struct tree_desc d;
142 struct tree_desc_skip *skip;
143};
144
145static int name_compare(const char *a, int a_len,
146 const char *b, int b_len)
147{
148 int len = (a_len < b_len) ? a_len : b_len;
149 int cmp = memcmp(a, b, len);
150 if (cmp)
151 return cmp;
152 return (a_len - b_len);
153}
154
155static int check_entry_match(const char *a, int a_len, const char *b, int b_len)
156{
157 /*
158 * The caller wants to pick *a* from a tree or nothing.
159 * We are looking at *b* in a tree.
160 *
161 * (0) If a and b are the same name, we are trivially happy.
162 *
163 * There are three possibilities where *a* could be hiding
164 * behind *b*.
165 *
166 * (1) *a* == "t", *b* == "ab" i.e. *b* sorts earlier than *a* no
167 * matter what.
168 * (2) *a* == "t", *b* == "t-2" and "t" is a subtree in the tree;
169 * (3) *a* == "t-2", *b* == "t" and "t-2" is a blob in the tree.
170 *
171 * Otherwise we know *a* won't appear in the tree without
172 * scanning further.
173 */
174
175 int cmp = name_compare(a, a_len, b, b_len);
176
177 /* Most common case first -- reading sync'd trees */
178 if (!cmp)
179 return cmp;
180
181 if (0 < cmp) {
182 /* a comes after b; it does not matter if it is case (3)
183 if (b_len < a_len && !memcmp(a, b, b_len) && a[b_len] < '/')
184 return 1;
185 */
186 return 1; /* keep looking */
187 }
188
189 /* b comes after a; are we looking at case (2)? */
190 if (a_len < b_len && !memcmp(a, b, a_len) && b[a_len] < '/')
191 return 1; /* keep looking */
192
193 return -1; /* a cannot appear in the tree */
194}
195
196/*
197 * From the extended tree_desc, extract the first name entry, while
198 * paying attention to the candidate "first" name. Most importantly,
199 * when looking for an entry, if there are entries that sorts earlier
200 * in the tree object representation than that name, skip them and
201 * process the named entry first. We will remember that we haven't
202 * processed the first entry yet, and in the later call skip the
203 * entry we processed early when update_extended_entry() is called.
204 *
205 * E.g. if the underlying tree object has these entries:
206 *
207 * blob "t-1"
208 * blob "t-2"
209 * tree "t"
210 * blob "t=1"
211 *
212 * and the "first" asks for "t", remember that we still need to
213 * process "t-1" and "t-2" but extract "t". After processing the
214 * entry "t" from this call, the caller will let us know by calling
215 * update_extended_entry() that we can remember "t" has been processed
216 * already.
217 */
218
219static void extended_entry_extract(struct tree_desc_x *t,
220 struct name_entry *a,
221 const char *first,
222 int first_len)
223{
224 const char *path;
225 int len;
226 struct tree_desc probe;
227 struct tree_desc_skip *skip;
228
229 /*
230 * Extract the first entry from the tree_desc, but skip the
231 * ones that we already returned in earlier rounds.
232 */
233 while (1) {
234 if (!t->d.size) {
235 entry_clear(a);
236 break; /* not found */
237 }
238 entry_extract(&t->d, a);
239 for (skip = t->skip; skip; skip = skip->prev)
240 if (a->path == skip->ptr)
241 break; /* found */
242 if (!skip)
243 break;
244 /* We have processed this entry already. */
245 update_tree_entry(&t->d);
246 }
247
248 if (!first || !a->path)
249 return;
250
251 /*
252 * The caller wants "first" from this tree, or nothing.
253 */
254 path = a->path;
255 len = tree_entry_len(a->path, a->sha1);
256 switch (check_entry_match(first, first_len, path, len)) {
257 case -1:
258 entry_clear(a);
259 case 0:
260 return;
261 default:
262 break;
263 }
264
265 /*
266 * We need to look-ahead -- we suspect that a subtree whose
267 * name is "first" may be hiding behind the current entry "path".
268 */
269 probe = t->d;
270 while (probe.size) {
271 entry_extract(&probe, a);
272 path = a->path;
273 len = tree_entry_len(a->path, a->sha1);
274 switch (check_entry_match(first, first_len, path, len)) {
275 case -1:
276 entry_clear(a);
277 case 0:
278 return;
279 default:
280 update_tree_entry(&probe);
281 break;
282 }
283 /* keep looking */
284 }
285 entry_clear(a);
286}
287
288static void update_extended_entry(struct tree_desc_x *t, struct name_entry *a)
289{
290 if (t->d.entry.path == a->path) {
291 update_tree_entry(&t->d);
292 } else {
293 /* we have returned this entry early */
294 struct tree_desc_skip *skip = xmalloc(sizeof(*skip));
295 skip->ptr = a->path;
296 skip->prev = t->skip;
297 t->skip = skip;
298 }
299}
300
301static void free_extended_entry(struct tree_desc_x *t)
302{
303 struct tree_desc_skip *p, *s;
304
305 for (s = t->skip; s; s = p) {
306 p = s->prev;
307 free(s);
308 }
309}
310
5803c6f8 311int traverse_trees(int n, struct tree_desc *t, struct traverse_info *info)
1b0c7174 312{
5803c6f8 313 int ret = 0;
e6c111b4 314 int error = 0;
1b0c7174 315 struct name_entry *entry = xmalloc(n*sizeof(*entry));
1ee26571
JH
316 int i;
317 struct tree_desc_x *tx = xcalloc(n, sizeof(*tx));
318
319 for (i = 0; i < n; i++)
320 tx[i].d = t[i];
1b0c7174
JH
321
322 for (;;) {
1ee26571
JH
323 unsigned long mask, dirmask;
324 const char *first = NULL;
325 int first_len = 0;
326 struct name_entry *e;
327 int len;
328
329 for (i = 0; i < n; i++) {
330 e = entry + i;
331 extended_entry_extract(tx + i, e, NULL, 0);
332 }
1b0c7174 333
1ee26571
JH
334 /*
335 * A tree may have "t-2" at the current location even
336 * though it may have "t" that is a subtree behind it,
337 * and another tree may return "t". We want to grab
338 * all "t" from all trees to match in such a case.
339 */
1b0c7174 340 for (i = 0; i < n; i++) {
1ee26571
JH
341 e = entry + i;
342 if (!e->path)
1b0c7174 343 continue;
1ee26571
JH
344 len = tree_entry_len(e->path, e->sha1);
345 if (!first) {
346 first = e->path;
347 first_len = len;
348 continue;
349 }
350 if (name_compare(e->path, len, first, first_len) < 0) {
351 first = e->path;
352 first_len = len;
353 }
354 }
355
356 if (first) {
357 for (i = 0; i < n; i++) {
358 e = entry + i;
359 extended_entry_extract(tx + i, e, first, first_len);
360 /* Cull the ones that are not the earliest */
361 if (!e->path)
1b0c7174 362 continue;
1ee26571
JH
363 len = tree_entry_len(e->path, e->sha1);
364 if (name_compare(e->path, len, first, first_len))
365 entry_clear(e);
1b0c7174 366 }
1ee26571
JH
367 }
368
369 /* Now we have in entry[i] the earliest name from the trees */
370 mask = 0;
371 dirmask = 0;
372 for (i = 0; i < n; i++) {
373 if (!entry[i].path)
374 continue;
1b0c7174 375 mask |= 1ul << i;
91e4f036
LT
376 if (S_ISDIR(entry[i].mode))
377 dirmask |= 1ul << i;
1b0c7174
JH
378 }
379 if (!mask)
380 break;
91e4f036 381 ret = info->fn(n, mask, dirmask, entry, info);
e6c111b4
MM
382 if (ret < 0) {
383 error = ret;
384 if (!info->show_all_errors)
385 break;
386 }
1ee26571 387 mask &= ret;
5803c6f8 388 ret = 0;
1ee26571 389 for (i = 0; i < n; i++)
5803c6f8 390 if (mask & (1ul << i))
1ee26571 391 update_extended_entry(tx + i, entry + i);
1b0c7174
JH
392 }
393 free(entry);
1ee26571
JH
394 for (i = 0; i < n; i++)
395 free_extended_entry(tx + i);
396 free(tx);
e6c111b4 397 return error;
1b0c7174
JH
398}
399
4dcff634
JH
400static int find_tree_entry(struct tree_desc *t, const char *name, unsigned char *result, unsigned *mode)
401{
402 int namelen = strlen(name);
403 while (t->size) {
404 const char *entry;
405 const unsigned char *sha1;
406 int entrylen, cmp;
407
408 sha1 = tree_entry_extract(t, &entry, mode);
409 update_tree_entry(t);
304de2d2 410 entrylen = tree_entry_len(entry, sha1);
4dcff634
JH
411 if (entrylen > namelen)
412 continue;
413 cmp = memcmp(name, entry, entrylen);
414 if (cmp > 0)
415 continue;
416 if (cmp < 0)
417 break;
418 if (entrylen == namelen) {
e702496e 419 hashcpy(result, sha1);
4dcff634
JH
420 return 0;
421 }
422 if (name[entrylen] != '/')
423 continue;
424 if (!S_ISDIR(*mode))
425 break;
426 if (++entrylen == namelen) {
e702496e 427 hashcpy(result, sha1);
4dcff634
JH
428 return 0;
429 }
430 return get_tree_entry(sha1, name + entrylen, result, mode);
431 }
432 return -1;
433}
434
435int get_tree_entry(const unsigned char *tree_sha1, const char *name, unsigned char *sha1, unsigned *mode)
436{
437 int retval;
438 void *tree;
6fda5e51 439 unsigned long size;
4dcff634 440 struct tree_desc t;
d93b7d1c 441 unsigned char root[20];
4dcff634 442
6fda5e51 443 tree = read_object_with_reference(tree_sha1, tree_type, &size, root);
4dcff634
JH
444 if (!tree)
445 return -1;
d93b7d1c
JK
446
447 if (name[0] == '\0') {
448 hashcpy(sha1, root);
ef006503 449 free(tree);
d93b7d1c
JK
450 return 0;
451 }
452
6fda5e51 453 init_tree_desc(&t, tree, size);
4dcff634
JH
454 retval = find_tree_entry(&t, name, sha1, mode);
455 free(tree);
456 return retval;
457}
2c389fc8
NTND
458
459/*
460 * Is a tree entry interesting given the pathspec we have?
461 *
462 * Pre-condition: baselen == 0 || base[baselen-1] == '/'
463 *
464 * Return:
465 * - 2 for "yes, and all subsequent entries will be"
466 * - 1 for yes
467 * - zero for no
468 * - negative for "no, and no subsequent entries will be either"
469 */
470int tree_entry_interesting(const struct name_entry *entry,
471 const char *base, int baselen,
472 const struct pathspec *ps)
473{
474 int i;
475 int pathlen;
476 int never_interesting = -1;
477
478 if (!ps || !ps->nr)
479 return 2;
480
481 pathlen = tree_entry_len(entry->path, entry->sha1);
482
483 for (i = 0; i < ps->nr; i++) {
484 const struct pathspec_item *item = ps->items+i;
485 const char *match = item->match;
486 int matchlen = item->len;
487 int m = -1; /* signals that we haven't called strncmp() */
488
489 if (baselen >= matchlen) {
490 /* If it doesn't match, move along... */
491 if (strncmp(base, match, matchlen))
492 continue;
493
494 /*
495 * If the base is a subdirectory of a path which
496 * was specified, all of them are interesting.
497 */
498 if (!matchlen ||
499 base[matchlen] == '/' ||
500 match[matchlen - 1] == '/')
501 return 2;
502
503 /* Just a random prefix match */
504 continue;
505 }
506
507 /* Does the base match? */
508 if (strncmp(base, match, baselen))
509 continue;
510
511 match += baselen;
512 matchlen -= baselen;
513
514 if (never_interesting) {
515 /*
516 * We have not seen any match that sorts later
517 * than the current path.
518 */
519
520 /*
521 * Does match sort strictly earlier than path
522 * with their common parts?
523 */
524 m = strncmp(match, entry->path,
525 (matchlen < pathlen) ? matchlen : pathlen);
526 if (m < 0)
527 continue;
528
529 /*
530 * If we come here even once, that means there is at
531 * least one pathspec that would sort equal to or
532 * later than the path we are currently looking at.
533 * In other words, if we have never reached this point
534 * after iterating all pathspecs, it means all
535 * pathspecs are either outside of base, or inside the
536 * base but sorts strictly earlier than the current
537 * one. In either case, they will never match the
538 * subsequent entries. In such a case, we initialized
539 * the variable to -1 and that is what will be
540 * returned, allowing the caller to terminate early.
541 */
542 never_interesting = 0;
543 }
544
545 if (pathlen > matchlen)
546 continue;
547
548 if (matchlen > pathlen) {
549 if (match[pathlen] != '/')
550 continue;
551 if (!S_ISDIR(entry->mode))
552 continue;
553 }
554
555 if (m == -1)
556 /*
557 * we cheated and did not do strncmp(), so we do
558 * that here.
559 */
560 m = strncmp(match, entry->path, pathlen);
561
562 /*
563 * If common part matched earlier then it is a hit,
564 * because we rejected the case where path is not a
565 * leading directory and is shorter than match.
566 */
567 if (!m)
568 return 1;
569 }
570 return never_interesting; /* No matches */
571}