Merge branch 'nd/unpack-trees-with-cache-tree'

The unpack_trees() API used in checking out a branch and merging
walks one or more trees along with the index.  When the cache-tree
in the index tells us that we are walking a tree whose flattened
contents is known (i.e. matches a span in the index), as linearly
scanning a span in the index is much more efficient than having to
open tree objects recursively and listing their entries, the walk
can be optimized, which is done in this topic.

* nd/unpack-trees-with-cache-tree:
Document update for nd/unpack-trees-with-cache-tree
cache-tree: verify valid cache-tree in the test suite
unpack-trees: add missing cache invalidation
unpack-trees: reuse (still valid) cache-tree from src_index
unpack-trees: reduce malloc in cache-tree walk
unpack-trees: optimize walking same trees with cache-tree
unpack-trees: add performance tracing
trace.h: support nested performance tracing

diff --cc cache-tree.c
index 16ea022c46d3b281d04a3956f865d8a886a5b714,c3c206427cccbd0a468974eb59d4b41b6bd84b43..490a25adf06e4e1fcd70530943f604bc7c9f1b58
--- 1/cache-tree.c
--- 2/cache-tree.c
+++ b/cache-tree.c
@@@ -718,3 -726,87 +721,80 @@@ int cache_tree_matches_traversal(struc
                return it->entry_count;
        return 0;
  }
 -int update_main_cache_tree(int flags)
 -{
 -      if (!the_index.cache_tree)
 -              the_index.cache_tree = cache_tree();
 -      return cache_tree_update(&the_index, flags);
 -}
 -
+ 
+ static void verify_one(struct index_state *istate,
+                      struct cache_tree *it,
+                      struct strbuf *path)
+ {
+       int i, pos, len = path->len;
+       struct strbuf tree_buf = STRBUF_INIT;
+       struct object_id new_oid;
+ 
+       for (i = 0; i < it->subtree_nr; i++) {
+               strbuf_addf(path, "%s/", it->down[i]->name);
+               verify_one(istate, it->down[i]->cache_tree, path);
+               strbuf_setlen(path, len);
+       }
+ 
+       if (it->entry_count < 0 ||
+           /* no verification on tests (t7003) that replace trees */
+           lookup_replace_object(the_repository, &it->oid) != &it->oid)
+               return;
+ 
+       if (path->len) {
+               pos = index_name_pos(istate, path->buf, path->len);
+               pos = -pos - 1;
+       } else {
+               pos = 0;
+       }
+ 
+       i = 0;
+       while (i < it->entry_count) {
+               struct cache_entry *ce = istate->cache[pos + i];
+               const char *slash;
+               struct cache_tree_sub *sub = NULL;
+               const struct object_id *oid;
+               const char *name;
+               unsigned mode;
+               int entlen;
+ 
+               if (ce->ce_flags & (CE_STAGEMASK | CE_INTENT_TO_ADD | CE_REMOVE))
+                       BUG("%s with flags 0x%x should not be in cache-tree",
+                           ce->name, ce->ce_flags);
+               name = ce->name + path->len;
+               slash = strchr(name, '/');
+               if (slash) {
+                       entlen = slash - name;
+                       sub = find_subtree(it, ce->name + path->len, entlen, 0);
+                       if (!sub || sub->cache_tree->entry_count < 0)
+                               BUG("bad subtree '%.*s'", entlen, name);
+                       oid = &sub->cache_tree->oid;
+                       mode = S_IFDIR;
+                       i += sub->cache_tree->entry_count;
+               } else {
+                       oid = &ce->oid;
+                       mode = ce->ce_mode;
+                       entlen = ce_namelen(ce) - path->len;
+                       i++;
+               }
+               strbuf_addf(&tree_buf, "%o %.*s%c", mode, entlen, name, '\0');
+               strbuf_add(&tree_buf, oid->hash, the_hash_algo->rawsz);
+       }
+       hash_object_file(tree_buf.buf, tree_buf.len, tree_type, &new_oid);
+       if (oidcmp(&new_oid, &it->oid))
+               BUG("cache-tree for path %.*s does not match. "
+                   "Expected %s got %s", len, path->buf,
+                   oid_to_hex(&new_oid), oid_to_hex(&it->oid));
+       strbuf_setlen(path, len);
+       strbuf_release(&tree_buf);
+ }
+ 
+ void cache_tree_verify(struct index_state *istate)
+ {
+       struct strbuf path = STRBUF_INIT;
+ 
+       if (!istate->cache_tree)
+               return;
+       verify_one(istate, istate->cache_tree, &path);
+       strbuf_release(&path);
+ }

diff --cc cache-tree.h
index fc0c842e773f648d64858d1891f64d222633fc3a,c1fde531f9e3353de823c7934628a1faf74dffba..0ab6784ffea5da0581c905738aaa66215266b5f9
--- 1/cache-tree.h
--- 2/cache-tree.h
+++ b/cache-tree.h
@@@ -32,7 -32,10 +32,8 @@@ struct cache_tree *cache_tree_read(cons
  
  int cache_tree_fully_valid(struct cache_tree *);
  int cache_tree_update(struct index_state *, int);
+ void cache_tree_verify(struct index_state *);
  
 -int update_main_cache_tree(int);
 -
  /* bitmasks to write_cache_as_tree flags */
  #define WRITE_TREE_MISSING_OK 1
  #define WRITE_TREE_IGNORE_CACHE_TREE 2

diff --cc diff-lib.c
Simple merge

diff --cc dir.c
Simple merge

diff --cc preload-index.c
Simple merge

diff --cc read-cache.c
Simple merge

diff --cc t/README
index 9028b47d923ca027a146da82060dae395d3f7999,0e7cc2373419a7297a73978e01319e8ccc23402c..204b9f4cc5cbf8ad265423f6062cd99c24dd33d3
--- 1/t/README
--- 2/t/README
+++ b/t/README
@@@ -315,10 -315,10 +315,14 @@@ packs on demand. This normally only hap
  over 2GB. This variable forces the code path on any object larger than
  <n> bytes.
  
 +GIT_TEST_OE_DELTA_SIZE=<n> exercises the uncomon pack-objects code
 +path where deltas larger than this limit require extra memory
 +allocation for bookkeeping.
 +
+ GIT_TEST_VALIDATE_INDEX_CACHE_ENTRIES=<boolean> checks that cache-tree
+ records are valid when the index is written out or after a merge. This
+ is mostly to catch missing invalidation. Default is true.
+ 
  Naming Tests
  ------------
  

diff --cc t/test-lib.sh
Simple merge

diff --cc unpack-trees.c
index cfa88bb6ec8238a6a6a41d32d646610fd2699048,515c37437308b097c7f26442de19bb35d92c8da8..55f864ac577e5951db5345c358a0ec8bb8291919
--- 1/unpack-trees.c
--- 2/unpack-trees.c
+++ b/unpack-trees.c
@@@ -456,11 -414,8 +457,12 @@@ static int check_updates(struct unpack_
        stop_progress(&progress);
        errs |= finish_delayed_checkout(&state);
        if (o->update)
 -              git_attr_set_direction(GIT_ATTR_CHECKIN, NULL);
 +              git_attr_set_direction(GIT_ATTR_CHECKIN);
 +
 +      if (o->clone)
 +              report_collided_checkout(index);
 +
+       trace_performance_leave("check_updates");
        return errs != 0;
  }