Merge branch 'master' into next
[git/dscho.git] / tree-walk.c
bloba9bbf4e2354df5ce6b010873b419731343a12c7d
1 #include "cache.h"
2 #include "tree-walk.h"
3 #include "unpack-trees.h"
4 #include "tree.h"
6 static const char *get_mode(const char *str, unsigned int *modep)
8 unsigned char c;
9 unsigned int mode = 0;
11 if (*str == ' ')
12 return NULL;
14 while ((c = *str++) != ' ') {
15 if (c < '0' || c > '7')
16 return NULL;
17 mode = (mode << 3) + (c - '0');
19 *modep = mode;
20 return str;
23 static void decode_tree_entry(struct tree_desc *desc, const char *buf, unsigned long size)
25 const char *path;
26 unsigned int mode, len;
28 if (size < 24 || buf[size - 21])
29 die("corrupt tree file");
31 path = get_mode(buf, &mode);
32 if (!path || !*path)
33 die("corrupt tree file");
34 len = strlen(path) + 1;
36 /* Initialize the descriptor entry */
37 desc->entry.path = path;
38 desc->entry.mode = mode;
39 desc->entry.sha1 = (const unsigned char *)(path + len);
42 void init_tree_desc(struct tree_desc *desc, const void *buffer, unsigned long size)
44 desc->buffer = buffer;
45 desc->size = size;
46 if (size)
47 decode_tree_entry(desc, buffer, size);
50 void *fill_tree_descriptor(struct tree_desc *desc, const unsigned char *sha1)
52 unsigned long size = 0;
53 void *buf = NULL;
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));
60 init_tree_desc(desc, buf, size);
61 return buf;
64 static void entry_clear(struct name_entry *a)
66 memset(a, 0, sizeof(*a));
69 static void entry_extract(struct tree_desc *t, struct name_entry *a)
71 *a = t->entry;
74 void update_tree_entry(struct tree_desc *desc)
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;
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);
91 int tree_entry(struct tree_desc *desc, struct name_entry *entry)
93 if (!desc->size)
94 return 0;
96 *entry = desc->entry;
97 update_tree_entry(desc);
98 return 1;
101 void setup_traverse_info(struct traverse_info *info, const char *base)
103 int pathlen = strlen(base);
104 static struct traverse_info dummy;
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;
116 char *make_traverse_path(char *path, const struct traverse_info *info, const struct name_entry *n)
118 int len = tree_entry_len(n->path, n->sha1);
119 int pathlen = info->pathlen;
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;
132 return path;
135 struct tree_desc_skip {
136 struct tree_desc_skip *prev;
137 const void *ptr;
140 struct tree_desc_x {
141 struct tree_desc d;
142 struct tree_desc_skip *skip;
145 static int name_compare(const char *a, int a_len,
146 const char *b, int b_len)
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);
155 static int check_entry_match(const char *a, int a_len, const char *b, int b_len)
158 * The caller wants to pick *a* from a tree or nothing.
159 * We are looking at *b* in a tree.
161 * (0) If a and b are the same name, we are trivially happy.
163 * There are three possibilities where *a* could be hiding
164 * behind *b*.
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.
171 * Otherwise we know *a* won't appear in the tree without
172 * scanning further.
175 int cmp = name_compare(a, a_len, b, b_len);
177 /* Most common case first -- reading sync'd trees */
178 if (!cmp)
179 return cmp;
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;
186 return 1; /* keep looking */
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 */
193 return -1; /* a cannot appear in the tree */
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.
205 * E.g. if the underlying tree object has these entries:
207 * blob "t-1"
208 * blob "t-2"
209 * tree "t"
210 * blob "t=1"
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.
219 static void extended_entry_extract(struct tree_desc_x *t,
220 struct name_entry *a,
221 const char *first,
222 int first_len)
224 const char *path;
225 int len;
226 struct tree_desc probe;
227 struct tree_desc_skip *skip;
230 * Extract the first entry from the tree_desc, but skip the
231 * ones that we already returned in earlier rounds.
233 while (1) {
234 if (!t->d.size) {
235 entry_clear(a);
236 break; /* not found */
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);
248 if (!first || !a->path)
249 return;
252 * The caller wants "first" from this tree, or nothing.
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;
266 * We need to look-ahead -- we suspect that a subtree whose
267 * name is "first" may be hiding behind the current entry "path".
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;
283 /* keep looking */
285 entry_clear(a);
288 static void update_extended_entry(struct tree_desc_x *t, struct name_entry *a)
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;
301 static void free_extended_entry(struct tree_desc_x *t)
303 struct tree_desc_skip *p, *s;
305 for (s = t->skip; s; s = p) {
306 p = s->prev;
307 free(s);
311 int traverse_trees(int n, struct tree_desc *t, struct traverse_info *info)
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));
319 for (i = 0; i < n; i++)
320 tx[i].d = t[i];
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;
329 for (i = 0; i < n; i++) {
330 e = entry + i;
331 extended_entry_extract(tx + i, e, NULL, 0);
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.
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;
350 if (name_compare(e->path, len, first, first_len) < 0) {
351 first = e->path;
352 first_len = len;
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);
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;
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;
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);
393 free(entry);
394 for (i = 0; i < n; i++)
395 free_extended_entry(tx + i);
396 free(tx);
397 return error;
400 static int find_tree_entry(struct tree_desc *t, const char *name, unsigned char *result, unsigned *mode)
402 int namelen = strlen(name);
403 while (t->size) {
404 const char *entry;
405 const unsigned char *sha1;
406 int entrylen, cmp;
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;
422 if (name[entrylen] != '/')
423 continue;
424 if (!S_ISDIR(*mode))
425 break;
426 if (++entrylen == namelen) {
427 hashcpy(result, sha1);
428 return 0;
430 return get_tree_entry(sha1, name + entrylen, result, mode);
432 return -1;
435 int get_tree_entry(const unsigned char *tree_sha1, const char *name, unsigned char *sha1, unsigned *mode)
437 int retval;
438 void *tree;
439 unsigned long size;
440 struct tree_desc t;
441 unsigned char root[20];
443 tree = read_object_with_reference(tree_sha1, tree_type, &size, root);
444 if (!tree)
445 return -1;
447 if (name[0] == '\0') {
448 hashcpy(sha1, root);
449 free(tree);
450 return 0;
453 init_tree_desc(&t, tree, size);
454 retval = find_tree_entry(&t, name, sha1, mode);
455 free(tree);
456 return retval;