Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Newer
Older
100644 453 lines (401 sloc) 10.354 kB
1b0c717 tree/diff header cleanup.
Junio C Hamano authored
1 #include "cache.h"
2 #include "tree-walk.h"
8e44025 Use blob_, commit_, tag_, and tree_type throughout.
Peter Eriksen authored
3 #include "tree.h"
1b0c717 tree/diff header cleanup.
Junio C Hamano authored
4
4651ece @torvalds Switch over tree descriptors to contain a pre-parsed entry
torvalds authored
5 static const char *get_mode(const char *str, unsigned int *modep)
6 {
7 unsigned char c;
8 unsigned int mode = 0;
9
64cc1c0 tree-walk: don't parse incorrect entries
Martin Koegler authored
10 if (*str == ' ')
11 return NULL;
12
4651ece @torvalds Switch over tree descriptors to contain a pre-parsed entry
torvalds authored
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
64cc1c0 tree-walk: don't parse incorrect entries
Martin Koegler authored
22 static void decode_tree_entry(struct tree_desc *desc, const char *buf, unsigned long size)
4651ece @torvalds Switch over tree descriptors to contain a pre-parsed entry
torvalds authored
23 {
24 const char *path;
25 unsigned int mode, len;
26
64cc1c0 tree-walk: don't parse incorrect entries
Martin Koegler authored
27 if (size < 24 || buf[size - 21])
28 die("corrupt tree file");
29
4651ece @torvalds Switch over tree descriptors to contain a pre-parsed entry
torvalds authored
30 path = get_mode(buf, &mode);
64cc1c0 tree-walk: don't parse incorrect entries
Martin Koegler authored
31 if (!path || !*path)
4651ece @torvalds Switch over tree descriptors to contain a pre-parsed entry
torvalds authored
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
6fda5e5 @torvalds Initialize tree descriptors with a helper function rather than by hand.
torvalds authored
41 void init_tree_desc(struct tree_desc *desc, const void *buffer, unsigned long size)
42 {
43 desc->buffer = buffer;
44 desc->size = size;
4651ece @torvalds Switch over tree descriptors to contain a pre-parsed entry
torvalds authored
45 if (size)
46 decode_tree_entry(desc, buffer, size);
6fda5e5 @torvalds Initialize tree descriptors with a helper function rather than by hand.
torvalds authored
47 }
48
1b0c717 tree/diff header cleanup.
Junio C Hamano authored
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) {
8e44025 Use blob_, commit_, tag_, and tree_type throughout.
Peter Eriksen authored
55 buf = read_object_with_reference(sha1, tree_type, &size, NULL);
1b0c717 tree/diff header cleanup.
Junio C Hamano authored
56 if (!buf)
57 die("unable to read tree %s", sha1_to_hex(sha1));
58 }
6fda5e5 @torvalds Initialize tree descriptors with a helper function rather than by hand.
torvalds authored
59 init_tree_desc(desc, buf, size);
1b0c717 tree/diff header cleanup.
Junio C Hamano authored
60 return buf;
61 }
62
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 {
4651ece @torvalds Switch over tree descriptors to contain a pre-parsed entry
torvalds authored
70 *a = t->entry;
1b0c717 tree/diff header cleanup.
Junio C Hamano authored
71 }
72
73 void update_tree_entry(struct tree_desc *desc)
74 {
6fda5e5 @torvalds Initialize tree descriptors with a helper function rather than by hand.
torvalds authored
75 const void *buf = desc->buffer;
4651ece @torvalds Switch over tree descriptors to contain a pre-parsed entry
torvalds authored
76 const unsigned char *end = desc->entry.sha1 + 20;
1b0c717 tree/diff header cleanup.
Junio C Hamano authored
77 unsigned long size = desc->size;
4651ece @torvalds Switch over tree descriptors to contain a pre-parsed entry
torvalds authored
78 unsigned long len = end - (const unsigned char *)buf;
1b0c717 tree/diff header cleanup.
Junio C Hamano authored
79
80 if (size < len)
81 die("corrupt tree file");
4651ece @torvalds Switch over tree descriptors to contain a pre-parsed entry
torvalds authored
82 buf = end;
83 size -= len;
84 desc->buffer = buf;
85 desc->size = size;
86 if (size)
87 decode_tree_entry(desc, buf, size);
1b0c717 tree/diff header cleanup.
Junio C Hamano authored
88 }
89
4c068a9 tree_entry(): new tree-walking helper function
Linus Torvalds authored
90 int tree_entry(struct tree_desc *desc, struct name_entry *entry)
91 {
4651ece @torvalds Switch over tree descriptors to contain a pre-parsed entry
torvalds authored
92 if (!desc->size)
4c068a9 tree_entry(): new tree-walking helper function
Linus Torvalds authored
93 return 0;
94
4651ece @torvalds Switch over tree descriptors to contain a pre-parsed entry
torvalds authored
95 *entry = desc->entry;
96 update_tree_entry(desc);
4c068a9 tree_entry(): new tree-walking helper function
Linus Torvalds authored
97 return 1;
98 }
99
40d934d @torvalds Make 'traverse_tree()' use linked structure rather than 'const char *…
torvalds authored
100 void setup_traverse_info(struct traverse_info *info, const char *base)
101 {
102 int pathlen = strlen(base);
bcbe5a5 @torvalds Fix tree-walking compare_entry() in the presense of --prefix
torvalds authored
103 static struct traverse_info dummy;
40d934d @torvalds Make 'traverse_tree()' use linked structure rather than 'const char *…
torvalds authored
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);
bcbe5a5 @torvalds Fix tree-walking compare_entry() in the presense of --prefix
torvalds authored
111 if (pathlen)
112 info->prev = &dummy;
40d934d @torvalds Make 'traverse_tree()' use linked structure rather than 'const char *…
torvalds authored
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
1ee2657 @gitster traverse_trees(): handle D/F conflict case sanely
gitster authored
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
5803c6f @torvalds Add return value to 'traverse_tree()' callback
torvalds authored
310 int traverse_trees(int n, struct tree_desc *t, struct traverse_info *info)
1b0c717 tree/diff header cleanup.
Junio C Hamano authored
311 {
5803c6f @torvalds Add return value to 'traverse_tree()' callback
torvalds authored
312 int ret = 0;
1b0c717 tree/diff header cleanup.
Junio C Hamano authored
313 struct name_entry *entry = xmalloc(n*sizeof(*entry));
1ee2657 @gitster traverse_trees(): handle D/F conflict case sanely
gitster authored
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];
1b0c717 tree/diff header cleanup.
Junio C Hamano authored
319
320 for (;;) {
1ee2657 @gitster traverse_trees(): handle D/F conflict case sanely
gitster authored
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 }
1b0c717 tree/diff header cleanup.
Junio C Hamano authored
331
1ee2657 @gitster traverse_trees(): handle D/F conflict case sanely
gitster authored
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 */
1b0c717 tree/diff header cleanup.
Junio C Hamano authored
338 for (i = 0; i < n; i++) {
1ee2657 @gitster traverse_trees(): handle D/F conflict case sanely
gitster authored
339 e = entry + i;
340 if (!e->path)
1b0c717 tree/diff header cleanup.
Junio C Hamano authored
341 continue;
1ee2657 @gitster traverse_trees(): handle D/F conflict case sanely
gitster authored
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)
1b0c717 tree/diff header cleanup.
Junio C Hamano authored
360 continue;
1ee2657 @gitster traverse_trees(): handle D/F conflict case sanely
gitster authored
361 len = tree_entry_len(e->path, e->sha1);
362 if (name_compare(e->path, len, first, first_len))
363 entry_clear(e);
1b0c717 tree/diff header cleanup.
Junio C Hamano authored
364 }
1ee2657 @gitster traverse_trees(): handle D/F conflict case sanely
gitster authored
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;
1b0c717 tree/diff header cleanup.
Junio C Hamano authored
373 mask |= 1ul << i;
91e4f03 @torvalds Make 'traverse_trees()' traverse conflicting DF entries in parallel
torvalds authored
374 if (S_ISDIR(entry[i].mode))
375 dirmask |= 1ul << i;
1b0c717 tree/diff header cleanup.
Junio C Hamano authored
376 }
377 if (!mask)
378 break;
91e4f03 @torvalds Make 'traverse_trees()' traverse conflicting DF entries in parallel
torvalds authored
379 ret = info->fn(n, mask, dirmask, entry, info);
5803c6f @torvalds Add return value to 'traverse_tree()' callback
torvalds authored
380 if (ret < 0)
381 break;
1ee2657 @gitster traverse_trees(): handle D/F conflict case sanely
gitster authored
382 mask &= ret;
5803c6f @torvalds Add return value to 'traverse_tree()' callback
torvalds authored
383 ret = 0;
1ee2657 @gitster traverse_trees(): handle D/F conflict case sanely
gitster authored
384 for (i = 0; i < n; i++)
5803c6f @torvalds Add return value to 'traverse_tree()' callback
torvalds authored
385 if (mask & (1ul << i))
1ee2657 @gitster traverse_trees(): handle D/F conflict case sanely
gitster authored
386 update_extended_entry(tx + i, entry + i);
1b0c717 tree/diff header cleanup.
Junio C Hamano authored
387 }
388 free(entry);
1ee2657 @gitster traverse_trees(): handle D/F conflict case sanely
gitster authored
389 for (i = 0; i < n; i++)
390 free_extended_entry(tx + i);
391 free(tx);
5803c6f @torvalds Add return value to 'traverse_tree()' callback
torvalds authored
392 return ret;
1b0c717 tree/diff header cleanup.
Junio C Hamano authored
393 }
394
4dcff63 get_tree_entry(): make it available from tree-walk
Junio C Hamano authored
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);
304de2d @torvalds Avoid unnecessary strlen() calls
torvalds authored
405 entrylen = tree_entry_len(entry, sha1);
4dcff63 get_tree_entry(): make it available from tree-walk
Junio C Hamano authored
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) {
e702496 @spearce Convert memcpy(a,b,20) to hashcpy(a,b).
spearce authored
414 hashcpy(result, sha1);
4dcff63 get_tree_entry(): make it available from tree-walk
Junio C Hamano authored
415 return 0;
416 }
417 if (name[entrylen] != '/')
418 continue;
419 if (!S_ISDIR(*mode))
420 break;
421 if (++entrylen == namelen) {
e702496 @spearce Convert memcpy(a,b,20) to hashcpy(a,b).
spearce authored
422 hashcpy(result, sha1);
4dcff63 get_tree_entry(): make it available from tree-walk
Junio C Hamano authored
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;
6fda5e5 @torvalds Initialize tree descriptors with a helper function rather than by hand.
torvalds authored
434 unsigned long size;
4dcff63 get_tree_entry(): make it available from tree-walk
Junio C Hamano authored
435 struct tree_desc t;
d93b7d1 @peff get_tree_entry: map blank requested entry to tree root
peff authored
436 unsigned char root[20];
4dcff63 get_tree_entry(): make it available from tree-walk
Junio C Hamano authored
437
6fda5e5 @torvalds Initialize tree descriptors with a helper function rather than by hand.
torvalds authored
438 tree = read_object_with_reference(tree_sha1, tree_type, &size, root);
4dcff63 get_tree_entry(): make it available from tree-walk
Junio C Hamano authored
439 if (!tree)
440 return -1;
d93b7d1 @peff get_tree_entry: map blank requested entry to tree root
peff authored
441
442 if (name[0] == '\0') {
443 hashcpy(sha1, root);
ef00650 fix minor memory leak in get_tree_entry()
René Scharfe authored
444 free(tree);
d93b7d1 @peff get_tree_entry: map blank requested entry to tree root
peff authored
445 return 0;
446 }
447
6fda5e5 @torvalds Initialize tree descriptors with a helper function rather than by hand.
torvalds authored
448 init_tree_desc(&t, tree, size);
4dcff63 get_tree_entry(): make it available from tree-walk
Junio C Hamano authored
449 retval = find_tree_entry(&t, name, sha1, mode);
450 free(tree);
451 return retval;
452 }
Something went wrong with that request. Please try again.