]>
Commit | Line | Data |
---|---|---|
1b0c7174 JH |
1 | #include "cache.h" |
2 | #include "tree-walk.h" | |
8e440259 | 3 | #include "tree.h" |
1b0c7174 | 4 | |
4651ece8 LT |
5 | static const char *get_mode(const char *str, unsigned int *modep) |
6 | { | |
7 | unsigned char c; | |
8 | unsigned int mode = 0; | |
9 | ||
64cc1c09 MK |
10 | if (*str == ' ') |
11 | return NULL; | |
12 | ||
4651ece8 LT |
13 | while ((c = *str++) != ' ') { |
14 | if (c < '0' || c > '7') | |
15 | return NULL; | |
16 | mode = (mode << 3) + (c - '0'); | |
17 | } | |
18 | *modep = mode; | |
19 | return str; | |
20 | } | |
21 | ||
64cc1c09 | 22 | static void decode_tree_entry(struct tree_desc *desc, const char *buf, unsigned long size) |
4651ece8 LT |
23 | { |
24 | const char *path; | |
25 | unsigned int mode, len; | |
26 | ||
64cc1c09 MK |
27 | if (size < 24 || buf[size - 21]) |
28 | die("corrupt tree file"); | |
29 | ||
4651ece8 | 30 | path = get_mode(buf, &mode); |
64cc1c09 | 31 | if (!path || !*path) |
4651ece8 LT |
32 | die("corrupt tree file"); |
33 | len = strlen(path) + 1; | |
34 | ||
35 | /* Initialize the descriptor entry */ | |
36 | desc->entry.path = path; | |
37 | desc->entry.mode = mode; | |
38 | desc->entry.sha1 = (const unsigned char *)(path + len); | |
39 | } | |
40 | ||
6fda5e51 LT |
41 | void init_tree_desc(struct tree_desc *desc, const void *buffer, unsigned long size) |
42 | { | |
43 | desc->buffer = buffer; | |
44 | desc->size = size; | |
4651ece8 LT |
45 | if (size) |
46 | decode_tree_entry(desc, buffer, size); | |
6fda5e51 LT |
47 | } |
48 | ||
1b0c7174 JH |
49 | void *fill_tree_descriptor(struct tree_desc *desc, const unsigned char *sha1) |
50 | { | |
51 | unsigned long size = 0; | |
52 | void *buf = NULL; | |
53 | ||
54 | if (sha1) { | |
8e440259 | 55 | buf = read_object_with_reference(sha1, tree_type, &size, NULL); |
1b0c7174 JH |
56 | if (!buf) |
57 | die("unable to read tree %s", sha1_to_hex(sha1)); | |
58 | } | |
6fda5e51 | 59 | init_tree_desc(desc, buf, size); |
1b0c7174 JH |
60 | return buf; |
61 | } | |
62 | ||
1b0c7174 JH |
63 | static void entry_clear(struct name_entry *a) |
64 | { | |
65 | memset(a, 0, sizeof(*a)); | |
66 | } | |
67 | ||
68 | static void entry_extract(struct tree_desc *t, struct name_entry *a) | |
69 | { | |
4651ece8 | 70 | *a = t->entry; |
1b0c7174 JH |
71 | } |
72 | ||
73 | void update_tree_entry(struct tree_desc *desc) | |
74 | { | |
6fda5e51 | 75 | const void *buf = desc->buffer; |
4651ece8 | 76 | const unsigned char *end = desc->entry.sha1 + 20; |
1b0c7174 | 77 | unsigned long size = desc->size; |
4651ece8 | 78 | unsigned long len = end - (const unsigned char *)buf; |
1b0c7174 JH |
79 | |
80 | if (size < len) | |
81 | die("corrupt tree file"); | |
4651ece8 LT |
82 | buf = end; |
83 | size -= len; | |
84 | desc->buffer = buf; | |
85 | desc->size = size; | |
86 | if (size) | |
87 | decode_tree_entry(desc, buf, size); | |
1b0c7174 JH |
88 | } |
89 | ||
4c068a98 LT |
90 | int tree_entry(struct tree_desc *desc, struct name_entry *entry) |
91 | { | |
4651ece8 | 92 | if (!desc->size) |
4c068a98 LT |
93 | return 0; |
94 | ||
4651ece8 LT |
95 | *entry = desc->entry; |
96 | update_tree_entry(desc); | |
4c068a98 LT |
97 | return 1; |
98 | } | |
99 | ||
40d934df LT |
100 | void setup_traverse_info(struct traverse_info *info, const char *base) |
101 | { | |
102 | int pathlen = strlen(base); | |
bcbe5a51 | 103 | static struct traverse_info dummy; |
40d934df LT |
104 | |
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); | |
bcbe5a51 LT |
111 | if (pathlen) |
112 | info->prev = &dummy; | |
40d934df LT |
113 | } |
114 | ||
115 | char *make_traverse_path(char *path, const struct traverse_info *info, const struct name_entry *n) | |
116 | { | |
117 | int len = tree_entry_len(n->path, n->sha1); | |
118 | int pathlen = info->pathlen; | |
119 | ||
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; | |
130 | } | |
131 | return path; | |
132 | } | |
133 | ||
1ee26571 JH |
134 | struct tree_desc_skip { |
135 | struct tree_desc_skip *prev; | |
136 | const void *ptr; | |
137 | }; | |
138 | ||
139 | struct tree_desc_x { | |
140 | struct tree_desc d; | |
141 | struct tree_desc_skip *skip; | |
142 | }; | |
143 | ||
144 | static int name_compare(const char *a, int a_len, | |
145 | const char *b, int b_len) | |
146 | { | |
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); | |
152 | } | |
153 | ||
154 | static int check_entry_match(const char *a, int a_len, const char *b, int b_len) | |
155 | { | |
156 | /* | |
157 | * The caller wants to pick *a* from a tree or nothing. | |
158 | * We are looking at *b* in a tree. | |
159 | * | |
160 | * (0) If a and b are the same name, we are trivially happy. | |
161 | * | |
162 | * There are three possibilities where *a* could be hiding | |
163 | * behind *b*. | |
164 | * | |
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. | |
169 | * | |
170 | * Otherwise we know *a* won't appear in the tree without | |
171 | * scanning further. | |
172 | */ | |
173 | ||
174 | int cmp = name_compare(a, a_len, b, b_len); | |
175 | ||
176 | /* Most common case first -- reading sync'd trees */ | |
177 | if (!cmp) | |
178 | return cmp; | |
179 | ||
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; | |
184 | */ | |
185 | return 1; /* keep looking */ | |
186 | } | |
187 | ||
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 */ | |
191 | ||
192 | return -1; /* a cannot appear in the tree */ | |
193 | } | |
194 | ||
195 | /* | |
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. | |
203 | * | |
204 | * E.g. if the underlying tree object has these entries: | |
205 | * | |
206 | * blob "t-1" | |
207 | * blob "t-2" | |
208 | * tree "t" | |
209 | * blob "t=1" | |
210 | * | |
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. | |
216 | */ | |
217 | ||
218 | static void extended_entry_extract(struct tree_desc_x *t, | |
219 | struct name_entry *a, | |
220 | const char *first, | |
221 | int first_len) | |
222 | { | |
223 | const char *path; | |
224 | int len; | |
225 | struct tree_desc probe; | |
226 | struct tree_desc_skip *skip; | |
227 | ||
228 | /* | |
229 | * Extract the first entry from the tree_desc, but skip the | |
230 | * ones that we already returned in earlier rounds. | |
231 | */ | |
232 | while (1) { | |
233 | if (!t->d.size) { | |
234 | entry_clear(a); | |
235 | break; /* not found */ | |
236 | } | |
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); | |
245 | } | |
246 | ||
247 | if (!first || !a->path) | |
248 | return; | |
249 | ||
250 | /* | |
251 | * The caller wants "first" from this tree, or nothing. | |
252 | */ | |
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; | |
262 | } | |
263 | ||
264 | /* | |
265 | * We need to look-ahead -- we suspect that a subtree whose | |
266 | * name is "first" may be hiding behind the current entry "path". | |
267 | */ | |
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; | |
281 | } | |
282 | /* keep looking */ | |
283 | } | |
284 | entry_clear(a); | |
285 | } | |
286 | ||
287 | static void update_extended_entry(struct tree_desc_x *t, struct name_entry *a) | |
288 | { | |
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; | |
297 | } | |
298 | } | |
299 | ||
300 | static void free_extended_entry(struct tree_desc_x *t) | |
301 | { | |
302 | struct tree_desc_skip *p, *s; | |
303 | ||
304 | for (s = t->skip; s; s = p) { | |
305 | p = s->prev; | |
306 | free(s); | |
307 | } | |
308 | } | |
309 | ||
5803c6f8 | 310 | int traverse_trees(int n, struct tree_desc *t, struct traverse_info *info) |
1b0c7174 | 311 | { |
5803c6f8 | 312 | int ret = 0; |
1b0c7174 | 313 | struct name_entry *entry = xmalloc(n*sizeof(*entry)); |
1ee26571 JH |
314 | int i; |
315 | struct tree_desc_x *tx = xcalloc(n, sizeof(*tx)); | |
316 | ||
317 | for (i = 0; i < n; i++) | |
318 | tx[i].d = t[i]; | |
1b0c7174 JH |
319 | |
320 | for (;;) { | |
1ee26571 JH |
321 | unsigned long mask, dirmask; |
322 | const char *first = NULL; | |
323 | int first_len = 0; | |
324 | struct name_entry *e; | |
325 | int len; | |
326 | ||
327 | for (i = 0; i < n; i++) { | |
328 | e = entry + i; | |
329 | extended_entry_extract(tx + i, e, NULL, 0); | |
330 | } | |
1b0c7174 | 331 | |
1ee26571 JH |
332 | /* |
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. | |
337 | */ | |
1b0c7174 | 338 | for (i = 0; i < n; i++) { |
1ee26571 JH |
339 | e = entry + i; |
340 | if (!e->path) | |
1b0c7174 | 341 | continue; |
1ee26571 JH |
342 | len = tree_entry_len(e->path, e->sha1); |
343 | if (!first) { | |
344 | first = e->path; | |
345 | first_len = len; | |
346 | continue; | |
347 | } | |
348 | if (name_compare(e->path, len, first, first_len) < 0) { | |
349 | first = e->path; | |
350 | first_len = len; | |
351 | } | |
352 | } | |
353 | ||
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) | |
1b0c7174 | 360 | continue; |
1ee26571 JH |
361 | len = tree_entry_len(e->path, e->sha1); |
362 | if (name_compare(e->path, len, first, first_len)) | |
363 | entry_clear(e); | |
1b0c7174 | 364 | } |
1ee26571 JH |
365 | } |
366 | ||
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; | |
1b0c7174 | 373 | mask |= 1ul << i; |
91e4f036 LT |
374 | if (S_ISDIR(entry[i].mode)) |
375 | dirmask |= 1ul << i; | |
1b0c7174 JH |
376 | } |
377 | if (!mask) | |
378 | break; | |
91e4f036 | 379 | ret = info->fn(n, mask, dirmask, entry, info); |
5803c6f8 LT |
380 | if (ret < 0) |
381 | break; | |
1ee26571 | 382 | mask &= ret; |
5803c6f8 | 383 | ret = 0; |
1ee26571 | 384 | for (i = 0; i < n; i++) |
5803c6f8 | 385 | if (mask & (1ul << i)) |
1ee26571 | 386 | update_extended_entry(tx + i, entry + i); |
1b0c7174 JH |
387 | } |
388 | free(entry); | |
1ee26571 JH |
389 | for (i = 0; i < n; i++) |
390 | free_extended_entry(tx + i); | |
391 | free(tx); | |
5803c6f8 | 392 | return ret; |
1b0c7174 JH |
393 | } |
394 | ||
4dcff634 JH |
395 | static int find_tree_entry(struct tree_desc *t, const char *name, unsigned char *result, unsigned *mode) |
396 | { | |
397 | int namelen = strlen(name); | |
398 | while (t->size) { | |
399 | const char *entry; | |
400 | const unsigned char *sha1; | |
401 | int entrylen, cmp; | |
402 | ||
403 | sha1 = tree_entry_extract(t, &entry, mode); | |
404 | update_tree_entry(t); | |
304de2d2 | 405 | entrylen = tree_entry_len(entry, sha1); |
4dcff634 JH |
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) { | |
e702496e | 414 | hashcpy(result, sha1); |
4dcff634 JH |
415 | return 0; |
416 | } | |
417 | if (name[entrylen] != '/') | |
418 | continue; | |
419 | if (!S_ISDIR(*mode)) | |
420 | break; | |
421 | if (++entrylen == namelen) { | |
e702496e | 422 | hashcpy(result, sha1); |
4dcff634 JH |
423 | return 0; |
424 | } | |
425 | return get_tree_entry(sha1, name + entrylen, result, mode); | |
426 | } | |
427 | return -1; | |
428 | } | |
429 | ||
430 | int get_tree_entry(const unsigned char *tree_sha1, const char *name, unsigned char *sha1, unsigned *mode) | |
431 | { | |
432 | int retval; | |
433 | void *tree; | |
6fda5e51 | 434 | unsigned long size; |
4dcff634 | 435 | struct tree_desc t; |
d93b7d1c | 436 | unsigned char root[20]; |
4dcff634 | 437 | |
6fda5e51 | 438 | tree = read_object_with_reference(tree_sha1, tree_type, &size, root); |
4dcff634 JH |
439 | if (!tree) |
440 | return -1; | |
d93b7d1c JK |
441 | |
442 | if (name[0] == '\0') { | |
443 | hashcpy(sha1, root); | |
ef006503 | 444 | free(tree); |
d93b7d1c JK |
445 | return 0; |
446 | } | |
447 | ||
6fda5e51 | 448 | init_tree_desc(&t, tree, size); |
4dcff634 JH |
449 | retval = find_tree_entry(&t, name, sha1, mode); |
450 | free(tree); | |
451 | return retval; | |
452 | } |