tree_entry_interesting(): refactor into separate smaller functions
[git/git.git] / tree-walk.c
1 #include "cache.h"
2 #include "tree-walk.h"
3 #include "unpack-trees.h"
4 #include "tree.h"
5
6 static const char *get_mode(const char *str, unsigned int *modep)
7 {
8 unsigned char c;
9 unsigned int mode = 0;
10
11 if (*str == ' ')
12 return NULL;
13
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
23 static void decode_tree_entry(struct tree_desc *desc, const char *buf, unsigned long size)
24 {
25 const char *path;
26 unsigned int mode, len;
27
28 if (size < 24 || buf[size - 21])
29 die("corrupt tree file");
30
31 path = get_mode(buf, &mode);
32 if (!path || !*path)
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
42 void init_tree_desc(struct tree_desc *desc, const void *buffer, unsigned long size)
43 {
44 desc->buffer = buffer;
45 desc->size = size;
46 if (size)
47 decode_tree_entry(desc, buffer, size);
48 }
49
50 void *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) {
56 buf = read_object_with_reference(sha1, tree_type, &size, NULL);
57 if (!buf)
58 die("unable to read tree %s", sha1_to_hex(sha1));
59 }
60 init_tree_desc(desc, buf, size);
61 return buf;
62 }
63
64 static void entry_clear(struct name_entry *a)
65 {
66 memset(a, 0, sizeof(*a));
67 }
68
69 static void entry_extract(struct tree_desc *t, struct name_entry *a)
70 {
71 *a = t->entry;
72 }
73
74 void update_tree_entry(struct tree_desc *desc)
75 {
76 const void *buf = desc->buffer;
77 const unsigned char *end = desc->entry.sha1 + 20;
78 unsigned long size = desc->size;
79 unsigned long len = end - (const unsigned char *)buf;
80
81 if (size < len)
82 die("corrupt tree file");
83 buf = end;
84 size -= len;
85 desc->buffer = buf;
86 desc->size = size;
87 if (size)
88 decode_tree_entry(desc, buf, size);
89 }
90
91 int tree_entry(struct tree_desc *desc, struct name_entry *entry)
92 {
93 if (!desc->size)
94 return 0;
95
96 *entry = desc->entry;
97 update_tree_entry(desc);
98 return 1;
99 }
100
101 void setup_traverse_info(struct traverse_info *info, const char *base)
102 {
103 int pathlen = strlen(base);
104 static struct traverse_info dummy;
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);
112 if (pathlen)
113 info->prev = &dummy;
114 }
115
116 char *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
135 struct tree_desc_skip {
136 struct tree_desc_skip *prev;
137 const void *ptr;
138 };
139
140 struct tree_desc_x {
141 struct tree_desc d;
142 struct tree_desc_skip *skip;
143 };
144
145 static 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
155 static 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
219 static 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
288 static 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
301 static 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
311 int traverse_trees(int n, struct tree_desc *t, struct traverse_info *info)
312 {
313 int ret = 0;
314 int error = 0;
315 struct name_entry *entry = xmalloc(n*sizeof(*entry));
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];
321
322 for (;;) {
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 }
333
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 */
340 for (i = 0; i < n; i++) {
341 e = entry + i;
342 if (!e->path)
343 continue;
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)
362 continue;
363 len = tree_entry_len(e->path, e->sha1);
364 if (name_compare(e->path, len, first, first_len))
365 entry_clear(e);
366 }
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;
375 mask |= 1ul << i;
376 if (S_ISDIR(entry[i].mode))
377 dirmask |= 1ul << i;
378 }
379 if (!mask)
380 break;
381 ret = info->fn(n, mask, dirmask, entry, info);
382 if (ret < 0) {
383 error = ret;
384 if (!info->show_all_errors)
385 break;
386 }
387 mask &= ret;
388 ret = 0;
389 for (i = 0; i < n; i++)
390 if (mask & (1ul << i))
391 update_extended_entry(tx + i, entry + i);
392 }
393 free(entry);
394 for (i = 0; i < n; i++)
395 free_extended_entry(tx + i);
396 free(tx);
397 return error;
398 }
399
400 static 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);
410 entrylen = tree_entry_len(entry, sha1);
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) {
419 hashcpy(result, sha1);
420 return 0;
421 }
422 if (name[entrylen] != '/')
423 continue;
424 if (!S_ISDIR(*mode))
425 break;
426 if (++entrylen == namelen) {
427 hashcpy(result, sha1);
428 return 0;
429 }
430 return get_tree_entry(sha1, name + entrylen, result, mode);
431 }
432 return -1;
433 }
434
435 int get_tree_entry(const unsigned char *tree_sha1, const char *name, unsigned char *sha1, unsigned *mode)
436 {
437 int retval;
438 void *tree;
439 unsigned long size;
440 struct tree_desc t;
441 unsigned char root[20];
442
443 tree = read_object_with_reference(tree_sha1, tree_type, &size, root);
444 if (!tree)
445 return -1;
446
447 if (name[0] == '\0') {
448 hashcpy(sha1, root);
449 free(tree);
450 return 0;
451 }
452
453 init_tree_desc(&t, tree, size);
454 retval = find_tree_entry(&t, name, sha1, mode);
455 free(tree);
456 return retval;
457 }
458
459 static int match_entry(const struct name_entry *entry, int pathlen,
460 const char *match, int matchlen,
461 int *never_interesting)
462 {
463 int m = -1; /* signals that we haven't called strncmp() */
464
465 if (*never_interesting) {
466 /*
467 * We have not seen any match that sorts later
468 * than the current path.
469 */
470
471 /*
472 * Does match sort strictly earlier than path
473 * with their common parts?
474 */
475 m = strncmp(match, entry->path,
476 (matchlen < pathlen) ? matchlen : pathlen);
477 if (m < 0)
478 return 0;
479
480 /*
481 * If we come here even once, that means there is at
482 * least one pathspec that would sort equal to or
483 * later than the path we are currently looking at.
484 * In other words, if we have never reached this point
485 * after iterating all pathspecs, it means all
486 * pathspecs are either outside of base, or inside the
487 * base but sorts strictly earlier than the current
488 * one. In either case, they will never match the
489 * subsequent entries. In such a case, we initialized
490 * the variable to -1 and that is what will be
491 * returned, allowing the caller to terminate early.
492 */
493 *never_interesting = 0;
494 }
495
496 if (pathlen > matchlen)
497 return 0;
498
499 if (matchlen > pathlen) {
500 if (match[pathlen] != '/')
501 return 0;
502 if (!S_ISDIR(entry->mode))
503 return 0;
504 }
505
506 if (m == -1)
507 /*
508 * we cheated and did not do strncmp(), so we do
509 * that here.
510 */
511 m = strncmp(match, entry->path, pathlen);
512
513 /*
514 * If common part matched earlier then it is a hit,
515 * because we rejected the case where path is not a
516 * leading directory and is shorter than match.
517 */
518 if (!m)
519 return 1;
520
521 return 0;
522 }
523
524 static int match_dir_prefix(const char *base, int baselen,
525 const char *match, int matchlen)
526 {
527 if (strncmp(base, match, matchlen))
528 return 0;
529
530 /*
531 * If the base is a subdirectory of a path which
532 * was specified, all of them are interesting.
533 */
534 if (!matchlen ||
535 base[matchlen] == '/' ||
536 match[matchlen - 1] == '/')
537 return 1;
538
539 /* Just a random prefix match */
540 return 0;
541 }
542
543 /*
544 * Is a tree entry interesting given the pathspec we have?
545 *
546 * Pre-condition: baselen == 0 || base[baselen-1] == '/'
547 *
548 * Return:
549 * - 2 for "yes, and all subsequent entries will be"
550 * - 1 for yes
551 * - zero for no
552 * - negative for "no, and no subsequent entries will be either"
553 */
554 int tree_entry_interesting(const struct name_entry *entry,
555 const struct strbuf *base,
556 const struct pathspec *ps)
557 {
558 int i;
559 int pathlen, baselen = base->len;
560 int never_interesting = -1;
561
562 if (!ps || !ps->nr)
563 return 2;
564
565 pathlen = tree_entry_len(entry->path, entry->sha1);
566
567 for (i = 0; i < ps->nr; i++) {
568 const struct pathspec_item *item = ps->items+i;
569 const char *match = item->match;
570 int matchlen = item->len;
571
572 if (baselen >= matchlen) {
573 /* If it doesn't match, move along... */
574 if (!match_dir_prefix(base->buf, baselen, match, matchlen))
575 continue;
576 return 2;
577 }
578
579 /* Does the base match? */
580 if (!strncmp(base->buf, match, baselen)) {
581 if (match_entry(entry, pathlen,
582 match + baselen, matchlen - baselen,
583 &never_interesting))
584 return 1;
585 }
586 }
587 return never_interesting; /* No matches */
588 }