summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
The sixteenth batch
[git/gitster.git] / cache-tree.c
bloba4bc14ad15c8a077733630960b8f08cb40ae0c4a
1 #define USE_THE_REPOSITORY_VARIABLE
2 #define DISABLE_SIGN_COMPARE_WARNINGS
3
4 #include "git-compat-util.h"
5 #include "gettext.h"
6 #include "hex.h"
7 #include "lockfile.h"
8 #include "tree.h"
9 #include "tree-walk.h"
10 #include "cache-tree.h"
11 #include "bulk-checkin.h"
12 #include "object-file.h"
13 #include "odb.h"
14 #include "read-cache-ll.h"
15 #include "replace-object.h"
16 #include "repository.h"
17 #include "promisor-remote.h"
18 #include "trace.h"
19 #include "trace2.h"
20
21 #ifndef DEBUG_CACHE_TREE
22 #define DEBUG_CACHE_TREE 0
23 #endif
24
25 struct cache_tree *cache_tree(void)
26 {
27 struct cache_tree *it = xcalloc(1, sizeof(struct cache_tree));
28 it->entry_count = -1;
29 return it;
30 }
31
32 void cache_tree_free(struct cache_tree **it_p)
33 {
34 int i;
35 struct cache_tree *it = *it_p;
36
37 if (!it)
38 return;
39 for (i = 0; i < it->subtree_nr; i++)
40 if (it->down[i]) {
41 cache_tree_free(&it->down[i]->cache_tree);
42 free(it->down[i]);
43 }
44 free(it->down);
45 free(it);
46 *it_p = NULL;
47 }
48
49 static int subtree_name_cmp(const char *one, int onelen,
50 const char *two, int twolen)
51 {
52 if (onelen < twolen)
53 return -1;
54 if (twolen < onelen)
55 return 1;
56 return memcmp(one, two, onelen);
57 }
58
59 int cache_tree_subtree_pos(struct cache_tree *it, const char *path, int pathlen)
60 {
61 struct cache_tree_sub **down = it->down;
62 int lo, hi;
63 lo = 0;
64 hi = it->subtree_nr;
65 while (lo < hi) {
66 int mi = lo + (hi - lo) / 2;
67 struct cache_tree_sub *mdl = down[mi];
68 int cmp = subtree_name_cmp(path, pathlen,
69 mdl->name, mdl->namelen);
70 if (!cmp)
71 return mi;
72 if (cmp < 0)
73 hi = mi;
74 else
75 lo = mi + 1;
76 }
77 return -lo-1;
78 }
79
80 static struct cache_tree_sub *find_subtree(struct cache_tree *it,
81 const char *path,
82 int pathlen,
83 int create)
84 {
85 struct cache_tree_sub *down;
86 int pos = cache_tree_subtree_pos(it, path, pathlen);
87 if (0 <= pos)
88 return it->down[pos];
89 if (!create)
90 return NULL;
91
92 pos = -pos-1;
93 ALLOC_GROW(it->down, it->subtree_nr + 1, it->subtree_alloc);
94 it->subtree_nr++;
95
96 FLEX_ALLOC_MEM(down, name, path, pathlen);
97 down->cache_tree = NULL;
98 down->namelen = pathlen;
99
100 if (pos < it->subtree_nr)
101 MOVE_ARRAY(it->down + pos + 1, it->down + pos,
102 it->subtree_nr - pos - 1);
103 it->down[pos] = down;
104 return down;
105 }
106
107 struct cache_tree_sub *cache_tree_sub(struct cache_tree *it, const char *path)
108 {
109 int pathlen = strlen(path);
110 return find_subtree(it, path, pathlen, 1);
111 }
112
113 static int do_invalidate_path(struct cache_tree *it, const char *path)
114 {
115 /* a/b/c
116 * ==> invalidate self
117 * ==> find "a", have it invalidate "b/c"
118 * a
119 * ==> invalidate self
120 * ==> if "a" exists as a subtree, remove it.
121 */
122 const char *slash;
123 int namelen;
124 struct cache_tree_sub *down;
125
126 #if DEBUG_CACHE_TREE
127 fprintf(stderr, "cache-tree invalidate <%s>\n", path);
128 #endif
129
130 if (!it)
131 return 0;
132 slash = strchrnul(path, '/');
133 namelen = slash - path;
134 it->entry_count = -1;
135 if (!*slash) {
136 int pos;
137 pos = cache_tree_subtree_pos(it, path, namelen);
138 if (0 <= pos) {
139 cache_tree_free(&it->down[pos]->cache_tree);
140 free(it->down[pos]);
141 /* 0 1 2 3 4 5
142 * ^ ^subtree_nr = 6
143 * pos
144 * move 4 and 5 up one place (2 entries)
145 * 2 = 6 - 3 - 1 = subtree_nr - pos - 1
146 */
147 MOVE_ARRAY(it->down + pos, it->down + pos + 1,
148 it->subtree_nr - pos - 1);
149 it->subtree_nr--;
150 }
151 return 1;
152 }
153 down = find_subtree(it, path, namelen, 0);
154 if (down)
155 do_invalidate_path(down->cache_tree, slash + 1);
156 return 1;
157 }
158
159 void cache_tree_invalidate_path(struct index_state *istate, const char *path)
160 {
161 if (do_invalidate_path(istate->cache_tree, path))
162 istate->cache_changed |= CACHE_TREE_CHANGED;
163 }
164
165 static int verify_cache(struct index_state *istate, int flags)
166 {
167 unsigned i, funny;
168 int silent = flags & WRITE_TREE_SILENT;
169
170 /* Verify that the tree is merged */
171 funny = 0;
172 for (i = 0; i < istate->cache_nr; i++) {
173 const struct cache_entry *ce = istate->cache[i];
174 if (ce_stage(ce)) {
175 if (silent)
176 return -1;
177 if (10 < ++funny) {
178 fprintf(stderr, "...\n");
179 break;
180 }
181 fprintf(stderr, "%s: unmerged (%s)\n",
182 ce->name, oid_to_hex(&ce->oid));
183 }
184 }
185 if (funny)
186 return -1;
187
188 /* Also verify that the cache does not have path and path/file
189 * at the same time. At this point we know the cache has only
190 * stage 0 entries.
191 */
192 funny = 0;
193 for (i = 0; i + 1 < istate->cache_nr; i++) {
194 /* path/file always comes after path because of the way
195 * the cache is sorted. Also path can appear only once,
196 * which means conflicting one would immediately follow.
197 */
198 const struct cache_entry *this_ce = istate->cache[i];
199 const struct cache_entry *next_ce = istate->cache[i + 1];
200 const char *this_name = this_ce->name;
201 const char *next_name = next_ce->name;
202 int this_len = ce_namelen(this_ce);
203 if (this_len < ce_namelen(next_ce) &&
204 next_name[this_len] == '/' &&
205 strncmp(this_name, next_name, this_len) == 0) {
206 if (10 < ++funny) {
207 fprintf(stderr, "...\n");
208 break;
209 }
210 fprintf(stderr, "You have both %s and %s\n",
211 this_name, next_name);
212 }
213 }
214 if (funny)
215 return -1;
216 return 0;
217 }
218
219 static void discard_unused_subtrees(struct cache_tree *it)
220 {
221 struct cache_tree_sub **down = it->down;
222 int nr = it->subtree_nr;
223 int dst, src;
224 for (dst = src = 0; src < nr; src++) {
225 struct cache_tree_sub *s = down[src];
226 if (s->used)
227 down[dst++] = s;
228 else {
229 cache_tree_free(&s->cache_tree);
230 free(s);
231 it->subtree_nr--;
232 }
233 }
234 }
235
236 int cache_tree_fully_valid(struct cache_tree *it)
237 {
238 int i;
239 if (!it)
240 return 0;
241 if (it->entry_count < 0 ||
242 odb_has_object(the_repository->objects, &it->oid,
243 HAS_OBJECT_RECHECK_PACKED | HAS_OBJECT_FETCH_PROMISOR))
244 return 0;
245 for (i = 0; i < it->subtree_nr; i++) {
246 if (!cache_tree_fully_valid(it->down[i]->cache_tree))
247 return 0;
248 }
249 return 1;
250 }
251
252 static int must_check_existence(const struct cache_entry *ce)
253 {
254 return !(repo_has_promisor_remote(the_repository) && ce_skip_worktree(ce));
255 }
256
257 static int update_one(struct cache_tree *it,
258 struct cache_entry **cache,
259 int entries,
260 const char *base,
261 int baselen,
262 int *skip_count,
263 int flags)
264 {
265 struct strbuf buffer;
266 int missing_ok = flags & WRITE_TREE_MISSING_OK;
267 int dryrun = flags & WRITE_TREE_DRY_RUN;
268 int repair = flags & WRITE_TREE_REPAIR;
269 int to_invalidate = 0;
270 int i;
271
272 assert(!(dryrun && repair));
273
274 *skip_count = 0;
275
276 /*
277 * If the first entry of this region is a sparse directory
278 * entry corresponding exactly to 'base', then this cache_tree
279 * struct is a "leaf" in the data structure, pointing to the
280 * tree OID specified in the entry.
281 */
282 if (entries > 0) {
283 const struct cache_entry *ce = cache[0];
284
285 if (S_ISSPARSEDIR(ce->ce_mode) &&
286 ce->ce_namelen == baselen &&
287 !strncmp(ce->name, base, baselen)) {
288 it->entry_count = 1;
289 oidcpy(&it->oid, &ce->oid);
290 return 1;
291 }
292 }
293
294 if (0 <= it->entry_count &&
295 odb_has_object(the_repository->objects, &it->oid,
296 HAS_OBJECT_RECHECK_PACKED | HAS_OBJECT_FETCH_PROMISOR))
297 return it->entry_count;
298
299 /*
300 * We first scan for subtrees and update them; we start by
301 * marking existing subtrees -- the ones that are unmarked
302 * should not be in the result.
303 */
304 for (i = 0; i < it->subtree_nr; i++)
305 it->down[i]->used = 0;
306
307 /*
308 * Find the subtrees and update them.
309 */
310 i = 0;
311 while (i < entries) {
312 const struct cache_entry *ce = cache[i];
313 struct cache_tree_sub *sub;
314 const char *path, *slash;
315 int pathlen, sublen, subcnt, subskip;
316
317 path = ce->name;
318 pathlen = ce_namelen(ce);
319 if (pathlen <= baselen || memcmp(base, path, baselen))
320 break; /* at the end of this level */
321
322 slash = strchr(path + baselen, '/');
323 if (!slash) {
324 i++;
325 continue;
326 }
327 /*
328 * a/bbb/c (base = a/, slash = /c)
329 * ==>
330 * path+baselen = bbb/c, sublen = 3
331 */
332 sublen = slash - (path + baselen);
333 sub = find_subtree(it, path + baselen, sublen, 1);
334 if (!sub->cache_tree)
335 sub->cache_tree = cache_tree();
336 subcnt = update_one(sub->cache_tree,
337 cache + i, entries - i,
338 path,
339 baselen + sublen + 1,
340 &subskip,
341 flags);
342 if (subcnt < 0)
343 return subcnt;
344 if (!subcnt)
345 die("index cache-tree records empty sub-tree");
346 i += subcnt;
347 sub->count = subcnt; /* to be used in the next loop */
348 *skip_count += subskip;
349 sub->used = 1;
350 }
351
352 discard_unused_subtrees(it);
353
354 /*
355 * Then write out the tree object for this level.
356 */
357 strbuf_init(&buffer, 8192);
358
359 i = 0;
360 while (i < entries) {
361 const struct cache_entry *ce = cache[i];
362 struct cache_tree_sub *sub = NULL;
363 const char *path, *slash;
364 int pathlen, entlen;
365 const struct object_id *oid;
366 unsigned mode;
367 int expected_missing = 0;
368 int contains_ita = 0;
369 int ce_missing_ok;
370
371 path = ce->name;
372 pathlen = ce_namelen(ce);
373 if (pathlen <= baselen || memcmp(base, path, baselen))
374 break; /* at the end of this level */
375
376 slash = strchr(path + baselen, '/');
377 if (slash) {
378 entlen = slash - (path + baselen);
379 sub = find_subtree(it, path + baselen, entlen, 0);
380 if (!sub)
381 die("cache-tree.c: '%.*s' in '%s' not found",
382 entlen, path + baselen, path);
383 i += sub->count;
384 oid = &sub->cache_tree->oid;
385 mode = S_IFDIR;
386 contains_ita = sub->cache_tree->entry_count < 0;
387 if (contains_ita) {
388 to_invalidate = 1;
389 expected_missing = 1;
390 }
391 }
392 else {
393 oid = &ce->oid;
394 mode = ce->ce_mode;
395 entlen = pathlen - baselen;
396 i++;
397 }
398
399 ce_missing_ok = mode == S_IFGITLINK || missing_ok ||
400 !must_check_existence(ce);
401 if (is_null_oid(oid) ||
402 (!ce_missing_ok &&
403 !odb_has_object(the_repository->objects, oid,
404 HAS_OBJECT_RECHECK_PACKED | HAS_OBJECT_FETCH_PROMISOR))) {
405 strbuf_release(&buffer);
406 if (expected_missing)
407 return -1;
408 return error("invalid object %06o %s for '%.*s'",
409 mode, oid_to_hex(oid), entlen+baselen, path);
410 }
411
412 /*
413 * CE_REMOVE entries are removed before the index is
414 * written to disk. Skip them to remain consistent
415 * with the future on-disk index.
416 */
417 if (ce->ce_flags & CE_REMOVE) {
418 *skip_count = *skip_count + 1;
419 continue;
420 }
421
422 /*
423 * CE_INTENT_TO_ADD entries exist in on-disk index but
424 * they are not part of generated trees. Invalidate up
425 * to root to force cache-tree users to read elsewhere.
426 */
427 if (!sub && ce_intent_to_add(ce)) {
428 to_invalidate = 1;
429 continue;
430 }
431
432 /*
433 * "sub" can be an empty tree if all subentries are i-t-a.
434 */
435 if (contains_ita && is_empty_tree_oid(oid, the_repository->hash_algo))
436 continue;
437
438 strbuf_grow(&buffer, entlen + 100);
439 strbuf_addf(&buffer, "%o %.*s%c", mode, entlen, path + baselen, '\0');
440 strbuf_add(&buffer, oid->hash, the_hash_algo->rawsz);
441
442 #if DEBUG_CACHE_TREE
443 fprintf(stderr, "cache-tree update-one %o %.*s\n",
444 mode, entlen, path + baselen);
445 #endif
446 }
447
448 if (repair) {
449 struct object_id oid;
450 hash_object_file(the_hash_algo, buffer.buf, buffer.len,
451 OBJ_TREE, &oid);
452 if (odb_has_object(the_repository->objects, &oid, HAS_OBJECT_RECHECK_PACKED))
453 oidcpy(&it->oid, &oid);
454 else
455 to_invalidate = 1;
456 } else if (dryrun) {
457 hash_object_file(the_hash_algo, buffer.buf, buffer.len,
458 OBJ_TREE, &it->oid);
459 } else if (write_object_file_flags(buffer.buf, buffer.len, OBJ_TREE,
460 &it->oid, NULL, flags & WRITE_TREE_SILENT
461 ? WRITE_OBJECT_FILE_SILENT : 0)) {
462 strbuf_release(&buffer);
463 return -1;
464 }
465
466 strbuf_release(&buffer);
467 it->entry_count = to_invalidate ? -1 : i - *skip_count;
468 #if DEBUG_CACHE_TREE
469 fprintf(stderr, "cache-tree update-one (%d ent, %d subtree) %s\n",
470 it->entry_count, it->subtree_nr,
471 oid_to_hex(&it->oid));
472 #endif
473 return i;
474 }
475
476 int cache_tree_update(struct index_state *istate, int flags)
477 {
478 int skip, i;
479
480 i = verify_cache(istate, flags);
481
482 if (i)
483 return i;
484
485 if (!istate->cache_tree)
486 istate->cache_tree = cache_tree();
487
488 if (!(flags & WRITE_TREE_MISSING_OK) && repo_has_promisor_remote(the_repository))
489 prefetch_cache_entries(istate, must_check_existence);
490
491 trace_performance_enter();
492 trace2_region_enter("cache_tree", "update", the_repository);
493 begin_odb_transaction();
494 i = update_one(istate->cache_tree, istate->cache, istate->cache_nr,
495 "", 0, &skip, flags);
496 end_odb_transaction();
497 trace2_region_leave("cache_tree", "update", the_repository);
498 trace_performance_leave("cache_tree_update");
499 if (i < 0)
500 return i;
501 istate->cache_changed |= CACHE_TREE_CHANGED;
502 return 0;
503 }
504
505 static void write_one(struct strbuf *buffer, struct cache_tree *it,
506 const char *path, int pathlen)
507 {
508 int i;
509
510 /* One "cache-tree" entry consists of the following:
511 * path (NUL terminated)
512 * entry_count, subtree_nr ("%d %d\n")
513 * tree-sha1 (missing if invalid)
514 * subtree_nr "cache-tree" entries for subtrees.
515 */
516 strbuf_grow(buffer, pathlen + 100);
517 strbuf_add(buffer, path, pathlen);
518 strbuf_addf(buffer, "%c%d %d\n", 0, it->entry_count, it->subtree_nr);
519
520 #if DEBUG_CACHE_TREE
521 if (0 <= it->entry_count)
522 fprintf(stderr, "cache-tree <%.*s> (%d ent, %d subtree) %s\n",
523 pathlen, path, it->entry_count, it->subtree_nr,
524 oid_to_hex(&it->oid));
525 else
526 fprintf(stderr, "cache-tree <%.*s> (%d subtree) invalid\n",
527 pathlen, path, it->subtree_nr);
528 #endif
529
530 if (0 <= it->entry_count) {
531 strbuf_add(buffer, it->oid.hash, the_hash_algo->rawsz);
532 }
533 for (i = 0; i < it->subtree_nr; i++) {
534 struct cache_tree_sub *down = it->down[i];
535 if (i) {
536 struct cache_tree_sub *prev = it->down[i-1];
537 if (subtree_name_cmp(down->name, down->namelen,
538 prev->name, prev->namelen) <= 0)
539 die("fatal - unsorted cache subtree");
540 }
541 write_one(buffer, down->cache_tree, down->name, down->namelen);
542 }
543 }
544
545 void cache_tree_write(struct strbuf *sb, struct cache_tree *root)
546 {
547 trace2_region_enter("cache_tree", "write", the_repository);
548 write_one(sb, root, "", 0);
549 trace2_region_leave("cache_tree", "write", the_repository);
550 }
551
552 static struct cache_tree *read_one(const char **buffer, unsigned long *size_p)
553 {
554 const char *buf = *buffer;
555 unsigned long size = *size_p;
556 const char *cp;
557 char *ep;
558 struct cache_tree *it;
559 int i, subtree_nr;
560 const unsigned rawsz = the_hash_algo->rawsz;
561
562 it = NULL;
563 /* skip name, but make sure name exists */
564 while (size && *buf) {
565 size--;
566 buf++;
567 }
568 if (!size)
569 goto free_return;
570 buf++; size--;
571 it = cache_tree();
572
573 cp = buf;
574 it->entry_count = strtol(cp, &ep, 10);
575 if (cp == ep)
576 goto free_return;
577 cp = ep;
578 subtree_nr = strtol(cp, &ep, 10);
579 if (cp == ep)
580 goto free_return;
581 while (size && *buf && *buf != '\n') {
582 size--;
583 buf++;
584 }
585 if (!size)
586 goto free_return;
587 buf++; size--;
588 if (0 <= it->entry_count) {
589 if (size < rawsz)
590 goto free_return;
591 oidread(&it->oid, (const unsigned char *)buf,
592 the_repository->hash_algo);
593 buf += rawsz;
594 size -= rawsz;
595 }
596
597 #if DEBUG_CACHE_TREE
598 if (0 <= it->entry_count)
599 fprintf(stderr, "cache-tree <%s> (%d ent, %d subtree) %s\n",
600 *buffer, it->entry_count, subtree_nr,
601 oid_to_hex(&it->oid));
602 else
603 fprintf(stderr, "cache-tree <%s> (%d subtrees) invalid\n",
604 *buffer, subtree_nr);
605 #endif
606
607 /*
608 * Just a heuristic -- we do not add directories that often but
609 * we do not want to have to extend it immediately when we do,
610 * hence +2.
611 */
612 it->subtree_alloc = subtree_nr + 2;
613 CALLOC_ARRAY(it->down, it->subtree_alloc);
614 for (i = 0; i < subtree_nr; i++) {
615 /* read each subtree */
616 struct cache_tree *sub;
617 struct cache_tree_sub *subtree;
618 const char *name = buf;
619
620 sub = read_one(&buf, &size);
621 if (!sub)
622 goto free_return;
623 subtree = cache_tree_sub(it, name);
624 subtree->cache_tree = sub;
625 }
626 if (subtree_nr != it->subtree_nr)
627 die("cache-tree: internal error");
628 *buffer = buf;
629 *size_p = size;
630 return it;
631
632 free_return:
633 cache_tree_free(&it);
634 return NULL;
635 }
636
637 struct cache_tree *cache_tree_read(const char *buffer, unsigned long size)
638 {
639 struct cache_tree *result;
640
641 if (buffer[0])
642 return NULL; /* not the whole tree */
643
644 trace2_region_enter("cache_tree", "read", the_repository);
645 result = read_one(&buffer, &size);
646 trace2_region_leave("cache_tree", "read", the_repository);
647
648 return result;
649 }
650
651 static struct cache_tree *cache_tree_find(struct cache_tree *it, const char *path)
652 {
653 if (!it)
654 return NULL;
655 while (*path) {
656 const char *slash;
657 struct cache_tree_sub *sub;
658
659 slash = strchrnul(path, '/');
660 /*
661 * Between path and slash is the name of the subtree
662 * to look for.
663 */
664 sub = find_subtree(it, path, slash - path, 0);
665 if (!sub)
666 return NULL;
667 it = sub->cache_tree;
668
669 path = slash;
670 while (*path == '/')
671 path++;
672 }
673 return it;
674 }
675
676 static int write_index_as_tree_internal(struct object_id *oid,
677 struct index_state *index_state,
678 int cache_tree_valid,
679 int flags,
680 const char *prefix)
681 {
682 if (flags & WRITE_TREE_IGNORE_CACHE_TREE) {
683 cache_tree_free(&index_state->cache_tree);
684 cache_tree_valid = 0;
685 }
686
687 if (!cache_tree_valid && cache_tree_update(index_state, flags) < 0)
688 return WRITE_TREE_UNMERGED_INDEX;
689
690 if (prefix) {
691 struct cache_tree *subtree;
692 subtree = cache_tree_find(index_state->cache_tree, prefix);
693 if (!subtree)
694 return WRITE_TREE_PREFIX_ERROR;
695 oidcpy(oid, &subtree->oid);
696 }
697 else
698 oidcpy(oid, &index_state->cache_tree->oid);
699
700 return 0;
701 }
702
703 struct tree* write_in_core_index_as_tree(struct repository *repo) {
704 struct object_id o;
705 int was_valid, ret;
706
707 struct index_state *index_state = repo->index;
708 was_valid = index_state->cache_tree &&
709 cache_tree_fully_valid(index_state->cache_tree);
710
711 ret = write_index_as_tree_internal(&o, index_state, was_valid, 0, NULL);
712 if (ret == WRITE_TREE_UNMERGED_INDEX) {
713 int i;
714 bug("there are unmerged index entries:");
715 for (i = 0; i < index_state->cache_nr; i++) {
716 const struct cache_entry *ce = index_state->cache[i];
717 if (ce_stage(ce))
718 bug("%d %.*s", ce_stage(ce),
719 (int)ce_namelen(ce), ce->name);
720 }
721 BUG("unmerged index entries when writing in-core index");
722 }
723
724 return lookup_tree(repo, &index_state->cache_tree->oid);
725 }
726
727
728 int write_index_as_tree(struct object_id *oid, struct index_state *index_state, const char *index_path, int flags, const char *prefix)
729 {
730 int entries, was_valid;
731 struct lock_file lock_file = LOCK_INIT;
732 int ret;
733
734 hold_lock_file_for_update(&lock_file, index_path, LOCK_DIE_ON_ERROR);
735
736 entries = read_index_from(index_state, index_path,
737 repo_get_git_dir(the_repository));
738 if (entries < 0) {
739 ret = WRITE_TREE_UNREADABLE_INDEX;
740 goto out;
741 }
742
743 was_valid = !(flags & WRITE_TREE_IGNORE_CACHE_TREE) &&
744 index_state->cache_tree &&
745 cache_tree_fully_valid(index_state->cache_tree);
746
747 ret = write_index_as_tree_internal(oid, index_state, was_valid, flags,
748 prefix);
749 if (!ret && !was_valid) {
750 write_locked_index(index_state, &lock_file, COMMIT_LOCK);
751 /* Not being able to write is fine -- we are only interested
752 * in updating the cache-tree part, and if the next caller
753 * ends up using the old index with unupdated cache-tree part
754 * it misses the work we did here, but that is just a
755 * performance penalty and not a big deal.
756 */
757 }
758
759 out:
760 rollback_lock_file(&lock_file);
761 return ret;
762 }
763
764 static void prime_cache_tree_sparse_dir(struct cache_tree *it,
765 struct tree *tree)
766 {
767
768 oidcpy(&it->oid, &tree->object.oid);
769 it->entry_count = 1;
770 }
771
772 static void prime_cache_tree_rec(struct repository *r,
773 struct cache_tree *it,
774 struct tree *tree,
775 struct strbuf *tree_path)
776 {
777 struct tree_desc desc;
778 struct name_entry entry;
779 int cnt;
780 size_t base_path_len = tree_path->len;
781
782 oidcpy(&it->oid, &tree->object.oid);
783
784 init_tree_desc(&desc, &tree->object.oid, tree->buffer, tree->size);
785 cnt = 0;
786 while (tree_entry(&desc, &entry)) {
787 if (!S_ISDIR(entry.mode))
788 cnt++;
789 else {
790 struct cache_tree_sub *sub;
791 struct tree *subtree = lookup_tree(r, &entry.oid);
792
793 if (parse_tree(subtree) < 0)
794 exit(128);
795 sub = cache_tree_sub(it, entry.path);
796 sub->cache_tree = cache_tree();
797
798 /*
799 * Recursively-constructed subtree path is only needed when working
800 * in a sparse index (where it's used to determine whether the
801 * subtree is a sparse directory in the index).
802 */
803 if (r->index->sparse_index) {
804 strbuf_setlen(tree_path, base_path_len);
805 strbuf_add(tree_path, entry.path, entry.pathlen);
806 strbuf_addch(tree_path, '/');
807 }
808
809 /*
810 * If a sparse index is in use, the directory being processed may be
811 * sparse. To confirm that, we can check whether an entry with that
812 * exact name exists in the index. If it does, the created subtree
813 * should be sparse. Otherwise, cache tree expansion should continue
814 * as normal.
815 */
816 if (r->index->sparse_index &&
817 index_entry_exists(r->index, tree_path->buf, tree_path->len))
818 prime_cache_tree_sparse_dir(sub->cache_tree, subtree);
819 else
820 prime_cache_tree_rec(r, sub->cache_tree, subtree, tree_path);
821 cnt += sub->cache_tree->entry_count;
822 }
823 }
824
825 it->entry_count = cnt;
826 }
827
828 void prime_cache_tree(struct repository *r,
829 struct index_state *istate,
830 struct tree *tree)
831 {
832 struct strbuf tree_path = STRBUF_INIT;
833
834 trace2_region_enter("cache-tree", "prime_cache_tree", r);
835 cache_tree_free(&istate->cache_tree);
836 istate->cache_tree = cache_tree();
837
838 prime_cache_tree_rec(r, istate->cache_tree, tree, &tree_path);
839 strbuf_release(&tree_path);
840 istate->cache_changed |= CACHE_TREE_CHANGED;
841 trace2_region_leave("cache-tree", "prime_cache_tree", r);
842 }
843
844 /*
845 * find the cache_tree that corresponds to the current level without
846 * exploding the full path into textual form. The root of the
847 * cache tree is given as "root", and our current level is "info".
848 * (1) When at root level, info->prev is NULL, so it is "root" itself.
849 * (2) Otherwise, find the cache_tree that corresponds to one level
850 * above us, and find ourselves in there.
851 */
852 static struct cache_tree *find_cache_tree_from_traversal(struct cache_tree *root,
853 struct traverse_info *info)
854 {
855 struct cache_tree *our_parent;
856
857 if (!info->prev)
858 return root;
859 our_parent = find_cache_tree_from_traversal(root, info->prev);
860 return cache_tree_find(our_parent, info->name);
861 }
862
863 int cache_tree_matches_traversal(struct cache_tree *root,
864 struct name_entry *ent,
865 struct traverse_info *info)
866 {
867 struct cache_tree *it;
868
869 it = find_cache_tree_from_traversal(root, info);
870 it = cache_tree_find(it, ent->path);
871 if (it && it->entry_count > 0 && oideq(&ent->oid, &it->oid))
872 return it->entry_count;
873 return 0;
874 }
875
876 static int verify_one_sparse(struct index_state *istate,
877 struct strbuf *path,
878 int pos)
879 {
880 struct cache_entry *ce = istate->cache[pos];
881 if (!S_ISSPARSEDIR(ce->ce_mode))
882 return error(_("directory '%s' is present in index, but not sparse"),
883 path->buf);
884 return 0;
885 }
886
887 /*
888 * Returns:
889 * 0 - Verification completed.
890 * 1 - Restart verification - a call to ensure_full_index() freed the cache
891 * tree that is being verified and verification needs to be restarted from
892 * the new toplevel cache tree.
893 * -1 - Verification failed.
894 */
895 static int verify_one(struct repository *r,
896 struct index_state *istate,
897 struct cache_tree *it,
898 struct strbuf *path)
899 {
900 int i, pos, len = path->len;
901 struct strbuf tree_buf = STRBUF_INIT;
902 struct object_id new_oid;
903 int ret;
904
905 for (i = 0; i < it->subtree_nr; i++) {
906 strbuf_addf(path, "%s/", it->down[i]->name);
907 ret = verify_one(r, istate, it->down[i]->cache_tree, path);
908 if (ret)
909 goto out;
910
911 strbuf_setlen(path, len);
912 }
913
914 if (it->entry_count < 0 ||
915 /* no verification on tests (t7003) that replace trees */
916 lookup_replace_object(r, &it->oid) != &it->oid) {
917 ret = 0;
918 goto out;
919 }
920
921 if (path->len) {
922 /*
923 * If the index is sparse and the cache tree is not
924 * index_name_pos() may trigger ensure_full_index() which will
925 * free the tree that is being verified.
926 */
927 int is_sparse = istate->sparse_index;
928 pos = index_name_pos(istate, path->buf, path->len);
929 if (is_sparse && !istate->sparse_index) {
930 ret = 1;
931 goto out;
932 }
933
934 if (pos >= 0) {
935 ret = verify_one_sparse(istate, path, pos);
936 goto out;
937 }
938
939 pos = -pos - 1;
940 } else {
941 pos = 0;
942 }
943
944 if (it->entry_count + pos > istate->cache_nr) {
945 ret = error(_("corrupted cache-tree has entries not present in index"));
946 goto out;
947 }
948
949 i = 0;
950 while (i < it->entry_count) {
951 struct cache_entry *ce = istate->cache[pos + i];
952 const char *slash;
953 struct cache_tree_sub *sub = NULL;
954 const struct object_id *oid;
955 const char *name;
956 unsigned mode;
957 int entlen;
958
959 if (ce->ce_flags & (CE_STAGEMASK | CE_INTENT_TO_ADD | CE_REMOVE)) {
960 ret = error(_("%s with flags 0x%x should not be in cache-tree"),
961 ce->name, ce->ce_flags);
962 goto out;
963 }
964
965 name = ce->name + path->len;
966 slash = strchr(name, '/');
967 if (slash) {
968 entlen = slash - name;
969
970 sub = find_subtree(it, ce->name + path->len, entlen, 0);
971 if (!sub || sub->cache_tree->entry_count < 0) {
972 ret = error(_("bad subtree '%.*s'"), entlen, name);
973 goto out;
974 }
975
976 oid = &sub->cache_tree->oid;
977 mode = S_IFDIR;
978 i += sub->cache_tree->entry_count;
979 } else {
980 oid = &ce->oid;
981 mode = ce->ce_mode;
982 entlen = ce_namelen(ce) - path->len;
983 i++;
984 }
985 strbuf_addf(&tree_buf, "%o %.*s%c", mode, entlen, name, '\0');
986 strbuf_add(&tree_buf, oid->hash, r->hash_algo->rawsz);
987 }
988
989 hash_object_file(r->hash_algo, tree_buf.buf, tree_buf.len, OBJ_TREE,
990 &new_oid);
991
992 if (!oideq(&new_oid, &it->oid)) {
993 ret = error(_("cache-tree for path %.*s does not match. "
994 "Expected %s got %s"), len, path->buf,
995 oid_to_hex(&new_oid), oid_to_hex(&it->oid));
996 goto out;
997 }
998
999 ret = 0;
1000 out:
1001 strbuf_setlen(path, len);
1002 strbuf_release(&tree_buf);
1003 return ret;
1004 }
1005
1006 int cache_tree_verify(struct repository *r, struct index_state *istate)
1007 {
1008 struct strbuf path = STRBUF_INIT;
1009 int ret;
1010
1011 if (!istate->cache_tree) {
1012 ret = 0;
1013 goto out;
1014 }
1015
1016 ret = verify_one(r, istate, istate->cache_tree, &path);
1017 if (ret < 0)
1018 goto out;
1019 if (ret > 0) {
1020 strbuf_reset(&path);
1021
1022 ret = verify_one(r, istate, istate->cache_tree, &path);
1023 if (ret < 0)
1024 goto out;
1025 if (ret > 0)
1026 BUG("ensure_full_index() called twice while verifying cache tree");
1027 }
1028
1029 ret = 0;
1030
1031 out:
1032 strbuf_release(&path);
1033 return ret;
1034 }
Mirror of Junio's Git repository with all the branches