Merge branch 'jc/conflict-marker-size' into maint
[tgit.git] / tree-walk.c
blob67a9a0c5a5bf7d7125765679318cfcd68c160da7
1 #include "cache.h"
2 #include "tree-walk.h"
3 #include "tree.h"
5 static const char *get_mode(const char *str, unsigned int *modep)
7 unsigned char c;
8 unsigned int mode = 0;
10 if (*str == ' ')
11 return NULL;
13 while ((c = *str++) != ' ') {
14 if (c < '0' || c > '7')
15 return NULL;
16 mode = (mode << 3) + (c - '0');
18 *modep = mode;
19 return str;
22 static void decode_tree_entry(struct tree_desc *desc, const char *buf, unsigned long size)
24 const char *path;
25 unsigned int mode, len;
27 if (size < 24 || buf[size - 21])
28 die("corrupt tree file");
30 path = get_mode(buf, &mode);
31 if (!path || !*path)
32 die("corrupt tree file");
33 len = strlen(path) + 1;
35 /* Initialize the descriptor entry */
36 desc->entry.path = path;
37 desc->entry.mode = mode;
38 desc->entry.sha1 = (const unsigned char *)(path + len);
41 void init_tree_desc(struct tree_desc *desc, const void *buffer, unsigned long size)
43 desc->buffer = buffer;
44 desc->size = size;
45 if (size)
46 decode_tree_entry(desc, buffer, size);
49 void *fill_tree_descriptor(struct tree_desc *desc, const unsigned char *sha1)
51 unsigned long size = 0;
52 void *buf = NULL;
54 if (sha1) {
55 buf = read_object_with_reference(sha1, tree_type, &size, NULL);
56 if (!buf)
57 die("unable to read tree %s", sha1_to_hex(sha1));
59 init_tree_desc(desc, buf, size);
60 return buf;
63 static void entry_clear(struct name_entry *a)
65 memset(a, 0, sizeof(*a));
68 static void entry_extract(struct tree_desc *t, struct name_entry *a)
70 *a = t->entry;
73 void update_tree_entry(struct tree_desc *desc)
75 const void *buf = desc->buffer;
76 const unsigned char *end = desc->entry.sha1 + 20;
77 unsigned long size = desc->size;
78 unsigned long len = end - (const unsigned char *)buf;
80 if (size < len)
81 die("corrupt tree file");
82 buf = end;
83 size -= len;
84 desc->buffer = buf;
85 desc->size = size;
86 if (size)
87 decode_tree_entry(desc, buf, size);
90 int tree_entry(struct tree_desc *desc, struct name_entry *entry)
92 if (!desc->size)
93 return 0;
95 *entry = desc->entry;
96 update_tree_entry(desc);
97 return 1;
100 void setup_traverse_info(struct traverse_info *info, const char *base)
102 int pathlen = strlen(base);
103 static struct traverse_info dummy;
105 memset(info, 0, sizeof(*info));
106 if (pathlen && base[pathlen-1] == '/')
107 pathlen--;
108 info->pathlen = pathlen ? pathlen + 1 : 0;
109 info->name.path = base;
110 info->name.sha1 = (void *)(base + pathlen + 1);
111 if (pathlen)
112 info->prev = &dummy;
115 char *make_traverse_path(char *path, const struct traverse_info *info, const struct name_entry *n)
117 int len = tree_entry_len(n->path, n->sha1);
118 int pathlen = info->pathlen;
120 path[pathlen + len] = 0;
121 for (;;) {
122 memcpy(path + pathlen, n->path, len);
123 if (!pathlen)
124 break;
125 path[--pathlen] = '/';
126 n = &info->name;
127 len = tree_entry_len(n->path, n->sha1);
128 info = info->prev;
129 pathlen -= len;
131 return path;
134 struct tree_desc_skip {
135 struct tree_desc_skip *prev;
136 const void *ptr;
139 struct tree_desc_x {
140 struct tree_desc d;
141 struct tree_desc_skip *skip;
144 static int name_compare(const char *a, int a_len,
145 const char *b, int b_len)
147 int len = (a_len < b_len) ? a_len : b_len;
148 int cmp = memcmp(a, b, len);
149 if (cmp)
150 return cmp;
151 return (a_len - b_len);
154 static int check_entry_match(const char *a, int a_len, const char *b, int b_len)
157 * The caller wants to pick *a* from a tree or nothing.
158 * We are looking at *b* in a tree.
160 * (0) If a and b are the same name, we are trivially happy.
162 * There are three possibilities where *a* could be hiding
163 * behind *b*.
165 * (1) *a* == "t", *b* == "ab" i.e. *b* sorts earlier than *a* no
166 * matter what.
167 * (2) *a* == "t", *b* == "t-2" and "t" is a subtree in the tree;
168 * (3) *a* == "t-2", *b* == "t" and "t-2" is a blob in the tree.
170 * Otherwise we know *a* won't appear in the tree without
171 * scanning further.
174 int cmp = name_compare(a, a_len, b, b_len);
176 /* Most common case first -- reading sync'd trees */
177 if (!cmp)
178 return cmp;
180 if (0 < cmp) {
181 /* a comes after b; it does not matter if it is case (3)
182 if (b_len < a_len && !memcmp(a, b, b_len) && a[b_len] < '/')
183 return 1;
185 return 1; /* keep looking */
188 /* b comes after a; are we looking at case (2)? */
189 if (a_len < b_len && !memcmp(a, b, a_len) && b[a_len] < '/')
190 return 1; /* keep looking */
192 return -1; /* a cannot appear in the tree */
196 * From the extended tree_desc, extract the first name entry, while
197 * paying attention to the candidate "first" name. Most importantly,
198 * when looking for an entry, if there are entries that sorts earlier
199 * in the tree object representation than that name, skip them and
200 * process the named entry first. We will remember that we haven't
201 * processed the first entry yet, and in the later call skip the
202 * entry we processed early when update_extended_entry() is called.
204 * E.g. if the underlying tree object has these entries:
206 * blob "t-1"
207 * blob "t-2"
208 * tree "t"
209 * blob "t=1"
211 * and the "first" asks for "t", remember that we still need to
212 * process "t-1" and "t-2" but extract "t". After processing the
213 * entry "t" from this call, the caller will let us know by calling
214 * update_extended_entry() that we can remember "t" has been processed
215 * already.
218 static void extended_entry_extract(struct tree_desc_x *t,
219 struct name_entry *a,
220 const char *first,
221 int first_len)
223 const char *path;
224 int len;
225 struct tree_desc probe;
226 struct tree_desc_skip *skip;
229 * Extract the first entry from the tree_desc, but skip the
230 * ones that we already returned in earlier rounds.
232 while (1) {
233 if (!t->d.size) {
234 entry_clear(a);
235 break; /* not found */
237 entry_extract(&t->d, a);
238 for (skip = t->skip; skip; skip = skip->prev)
239 if (a->path == skip->ptr)
240 break; /* found */
241 if (!skip)
242 break;
243 /* We have processed this entry already. */
244 update_tree_entry(&t->d);
247 if (!first || !a->path)
248 return;
251 * The caller wants "first" from this tree, or nothing.
253 path = a->path;
254 len = tree_entry_len(a->path, a->sha1);
255 switch (check_entry_match(first, first_len, path, len)) {
256 case -1:
257 entry_clear(a);
258 case 0:
259 return;
260 default:
261 break;
265 * We need to look-ahead -- we suspect that a subtree whose
266 * name is "first" may be hiding behind the current entry "path".
268 probe = t->d;
269 while (probe.size) {
270 entry_extract(&probe, a);
271 path = a->path;
272 len = tree_entry_len(a->path, a->sha1);
273 switch (check_entry_match(first, first_len, path, len)) {
274 case -1:
275 entry_clear(a);
276 case 0:
277 return;
278 default:
279 update_tree_entry(&probe);
280 break;
282 /* keep looking */
284 entry_clear(a);
287 static void update_extended_entry(struct tree_desc_x *t, struct name_entry *a)
289 if (t->d.entry.path == a->path) {
290 update_tree_entry(&t->d);
291 } else {
292 /* we have returned this entry early */
293 struct tree_desc_skip *skip = xmalloc(sizeof(*skip));
294 skip->ptr = a->path;
295 skip->prev = t->skip;
296 t->skip = skip;
300 static void free_extended_entry(struct tree_desc_x *t)
302 struct tree_desc_skip *p, *s;
304 for (s = t->skip; s; s = p) {
305 p = s->prev;
306 free(s);
310 int traverse_trees(int n, struct tree_desc *t, struct traverse_info *info)
312 int ret = 0;
313 struct name_entry *entry = xmalloc(n*sizeof(*entry));
314 int i;
315 struct tree_desc_x *tx = xcalloc(n, sizeof(*tx));
317 for (i = 0; i < n; i++)
318 tx[i].d = t[i];
320 for (;;) {
321 unsigned long mask, dirmask;
322 const char *first = NULL;
323 int first_len = 0;
324 struct name_entry *e;
325 int len;
327 for (i = 0; i < n; i++) {
328 e = entry + i;
329 extended_entry_extract(tx + i, e, NULL, 0);
333 * A tree may have "t-2" at the current location even
334 * though it may have "t" that is a subtree behind it,
335 * and another tree may return "t". We want to grab
336 * all "t" from all trees to match in such a case.
338 for (i = 0; i < n; i++) {
339 e = entry + i;
340 if (!e->path)
341 continue;
342 len = tree_entry_len(e->path, e->sha1);
343 if (!first) {
344 first = e->path;
345 first_len = len;
346 continue;
348 if (name_compare(e->path, len, first, first_len) < 0) {
349 first = e->path;
350 first_len = len;
354 if (first) {
355 for (i = 0; i < n; i++) {
356 e = entry + i;
357 extended_entry_extract(tx + i, e, first, first_len);
358 /* Cull the ones that are not the earliest */
359 if (!e->path)
360 continue;
361 len = tree_entry_len(e->path, e->sha1);
362 if (name_compare(e->path, len, first, first_len))
363 entry_clear(e);
367 /* Now we have in entry[i] the earliest name from the trees */
368 mask = 0;
369 dirmask = 0;
370 for (i = 0; i < n; i++) {
371 if (!entry[i].path)
372 continue;
373 mask |= 1ul << i;
374 if (S_ISDIR(entry[i].mode))
375 dirmask |= 1ul << i;
377 if (!mask)
378 break;
379 ret = info->fn(n, mask, dirmask, entry, info);
380 if (ret < 0)
381 break;
382 mask &= ret;
383 ret = 0;
384 for (i = 0; i < n; i++)
385 if (mask & (1ul << i))
386 update_extended_entry(tx + i, entry + i);
388 free(entry);
389 for (i = 0; i < n; i++)
390 free_extended_entry(tx + i);
391 free(tx);
392 return ret;
395 static int find_tree_entry(struct tree_desc *t, const char *name, unsigned char *result, unsigned *mode)
397 int namelen = strlen(name);
398 while (t->size) {
399 const char *entry;
400 const unsigned char *sha1;
401 int entrylen, cmp;
403 sha1 = tree_entry_extract(t, &entry, mode);
404 update_tree_entry(t);
405 entrylen = tree_entry_len(entry, sha1);
406 if (entrylen > namelen)
407 continue;
408 cmp = memcmp(name, entry, entrylen);
409 if (cmp > 0)
410 continue;
411 if (cmp < 0)
412 break;
413 if (entrylen == namelen) {
414 hashcpy(result, sha1);
415 return 0;
417 if (name[entrylen] != '/')
418 continue;
419 if (!S_ISDIR(*mode))
420 break;
421 if (++entrylen == namelen) {
422 hashcpy(result, sha1);
423 return 0;
425 return get_tree_entry(sha1, name + entrylen, result, mode);
427 return -1;
430 int get_tree_entry(const unsigned char *tree_sha1, const char *name, unsigned char *sha1, unsigned *mode)
432 int retval;
433 void *tree;
434 unsigned long size;
435 struct tree_desc t;
436 unsigned char root[20];
438 tree = read_object_with_reference(tree_sha1, tree_type, &size, root);
439 if (!tree)
440 return -1;
442 if (name[0] == '\0') {
443 hashcpy(sha1, root);
444 free(tree);
445 return 0;
448 init_tree_desc(&t, tree, size);
449 retval = find_tree_entry(&t, name, sha1, mode);
450 free(tree);
451 return retval;