From: Derrick Stolee <dstolee@xxxxxxxxxxxxx>
I had difficulty in my efforts to learn about the cached tree extension
based on the documentation and code because I had an incorrect
assumption about how it behaved. This might be due to some ambiguity in
the documentation, so this change modifies the beginning of the cached
tree format by expanding the description of the feature.
My hope is that this documentation clarifies a few things:
1. There is an in-memory recursive tree structure that is constructed
from the extension data. This structure has a few differences, such
as where the name is stored.
2. What does it mean for an entry to be invalid?
3. When exactly are "new" trees created?
Signed-off-by: Derrick Stolee <dstolee@xxxxxxxxxxxxx>
---
Documentation/technical/index-format.txt | 36 ++++++++++++++++++++----
1 file changed, 30 insertions(+), 6 deletions(-)
diff --git a/Documentation/technical/index-format.txt b/Documentation/technical/index-format.txt
index 69edf46c031..c614e136e24 100644
--- a/Documentation/technical/index-format.txt
+++ b/Documentation/technical/index-format.txt
@@ -138,12 +138,36 @@ Git index format
=== Cached tree
- Cached tree extension contains pre-computed hashes for trees that can
- be derived from the index. It helps speed up tree object generation
- from index for a new commit.
-
- When a path is updated in index, the path must be invalidated and
- removed from tree cache.
+ Since the index does not record entries for directories, the cache
+ entries cannot describe tree objects that already exist in the object
+ database for regions of the index that are unchanged from an existing
+ commit. The cached tree extension stores a recursive tree structure that
+ describes the trees that already exist and completely match sections of
+ the cache entries. This speeds up tree object generation from the index
+ for a new commit by only computing the trees that are "new" to that
+ commit.
+
+ The recursive tree structure uses nodes that store a number of cache
+ entries, a list of subnodes, and an object ID (OID). The OID references
+ the exising tree for that node, if it is known to exist. The subnodes
+ correspond to subdirectories that themselves have cached tree nodes. The
+ number of cache entries corresponds to the number of cache entries in
+ the index that describe paths within that tree's directory.
+
+ Note that the path for a given tree is part of the parent node in-memory
+ but is part of the child in the file format. The root tree has an empty
+ string for its name and its name does not exist in-memory.
+
+ When a path is updated in index, Git invalidates all nodes of the
+ recurisive cached tree corresponding to the parent directories of that
+ path. We store these tree nodes as being "invalid" by using "-1" as the
+ number of cache entries. To create trees corresponding to the current
+ index, Git only walks the invalid tree nodes and uses the cached OIDs
+ for the valid trees to construct new trees. In this way, Git only
+ constructs trees on the order of the number of changed paths (and their
+ depth in the working directory). This comes at a cost of tracking the
+ full directory structure in the cached tree extension, but this is
+ generally smaller than the full cache entry list in the index.
The signature for this extension is { 'T', 'R', 'E', 'E' }.
--
gitgitgadget
