Merge branch 'sn/doc-update-index-assume-unchanged' into maint-1.7.3
[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 }