Debian Codegraph @

plumbing/format/index/doc.go

raw
1 // Package index implements encoding and decoding of index format files.
2 //
3 // Git index format
4 // ================
5 //
6 // == The Git index file has the following format
7 //
8 // All binary numbers are in network byte order. Version 2 is described
9 // here unless stated otherwise.
10 //
11 // - A 12-byte header consisting of
12 //
13 // 4-byte signature:
14 // The signature is { 'D', 'I', 'R', 'C' } (stands for "dircache")
15 //
16 // 4-byte version number:
17 // The current supported versions are 2, 3 and 4.
18 //
19 // 32-bit number of index entries.
20 //
21 // - A number of sorted index entries (see below).
22 //
23 // - Extensions
24 //
25 // Extensions are identified by signature. Optional extensions can
26 // be ignored if Git does not understand them.
27 //
28 // Git currently supports cached tree and resolve undo extensions.
29 //
30 // 4-byte extension signature. If the first byte is 'A'..'Z' the
31 // extension is optional and can be ignored.
32 //
33 // 32-bit size of the extension
34 //
35 // Extension data
36 //
37 // - 160-bit SHA-1 over the content of the index file before this
38 // checksum.
39 //
40 // == Index entry
41 //
42 // Index entries are sorted in ascending order on the name field,
43 // interpreted as a string of unsigned bytes (i.e. memcmp() order, no
44 // localization, no special casing of directory separator '/'). Entries
45 // with the same name are sorted by their stage field.
46 //
47 // 32-bit ctime seconds, the last time a file's metadata changed
48 // this is stat(2) data
49 //
50 // 32-bit ctime nanosecond fractions
51 // this is stat(2) data
52 //
53 // 32-bit mtime seconds, the last time a file's data changed
54 // this is stat(2) data
55 //
56 // 32-bit mtime nanosecond fractions
57 // this is stat(2) data
58 //
59 // 32-bit dev
60 // this is stat(2) data
61 //
62 // 32-bit ino
63 // this is stat(2) data
64 //
65 // 32-bit mode, split into (high to low bits)
66 //
67 // 4-bit object type
68 // valid values in binary are 1000 (regular file), 1010 (symbolic link)
69 // and 1110 (gitlink)
70 //
71 // 3-bit unused
72 //
73 // 9-bit unix permission. Only 0755 and 0644 are valid for regular files.
74 // Symbolic links and gitlinks have value 0 in this field.
75 //
76 // 32-bit uid
77 // this is stat(2) data
78 //
79 // 32-bit gid
80 // this is stat(2) data
81 //
82 // 32-bit file size
83 // This is the on-disk size from stat(2), truncated to 32-bit.
84 //
85 // 160-bit SHA-1 for the represented object
86 //
87 // A 16-bit 'flags' field split into (high to low bits)
88 //
89 // 1-bit assume-valid flag
90 //
91 // 1-bit extended flag (must be zero in version 2)
92 //
93 // 2-bit stage (during merge)
94 //
95 // 12-bit name length if the length is less than 0xFFF; otherwise 0xFFF
96 // is stored in this field.
97 //
98 // (Version 3 or later) A 16-bit field, only applicable if the
99 // "extended flag" above is 1, split into (high to low bits).
100 //
101 // 1-bit reserved for future
102 //
103 // 1-bit skip-worktree flag (used by sparse checkout)
104 //
105 // 1-bit intent-to-add flag (used by "git add -N")
106 //
107 // 13-bit unused, must be zero
108 //
109 // Entry path name (variable length) relative to top level directory
110 // (without leading slash). '/' is used as path separator. The special
111 // path components ".", ".." and ".git" (without quotes) are disallowed.
112 // Trailing slash is also disallowed.
113 //
114 // The exact encoding is undefined, but the '.' and '/' characters
115 // are encoded in 7-bit ASCII and the encoding cannot contain a NUL
116 // byte (iow, this is a UNIX pathname).
117 //
118 // (Version 4) In version 4, the entry path name is prefix-compressed
119 // relative to the path name for the previous entry (the very first
120 // entry is encoded as if the path name for the previous entry is an
121 // empty string). At the beginning of an entry, an integer N in the
122 // variable width encoding (the same encoding as the offset is encoded
123 // for OFS_DELTA pack entries; see pack-format.txt) is stored, followed
124 // by a NUL-terminated string S. Removing N bytes from the end of the
125 // path name for the previous entry, and replacing it with the string S
126 // yields the path name for this entry.
127 //
128 // 1-8 nul bytes as necessary to pad the entry to a multiple of eight bytes
129 // while keeping the name NUL-terminated.
130 //
131 // (Version 4) In version 4, the padding after the pathname does not
132 // exist.
133 //
134 // Interpretation of index entries in split index mode is completely
135 // different. See below for details.
136 //
137 // == Extensions
138 //
139 // === Cached tree
140 //
141 // Cached tree extension contains pre-computed hashes for trees that can
142 // be derived from the index. It helps speed up tree object generation
143 // from index for a new commit.
144 //
145 // When a path is updated in index, the path must be invalidated and
146 // removed from tree cache.
147 //
148 // The signature for this extension is { 'T', 'R', 'E', 'E' }.
149 //
150 // A series of entries fill the entire extension; each of which
151 // consists of:
152 //
153 // - NUL-terminated path component (relative to its parent directory);
154 //
155 // - ASCII decimal number of entries in the index that is covered by the
156 // tree this entry represents (entry_count);
157 //
158 // - A space (ASCII 32);
159 //
160 // - ASCII decimal number that represents the number of subtrees this
161 // tree has;
162 //
163 // - A newline (ASCII 10); and
164 //
165 // - 160-bit object name for the object that would result from writing
166 // this span of index as a tree.
167 //
168 // An entry can be in an invalidated state and is represented by having
169 // a negative number in the entry_count field. In this case, there is no
170 // object name and the next entry starts immediately after the newline.
171 // When writing an invalid entry, -1 should always be used as entry_count.
172 //
173 // The entries are written out in the top-down, depth-first order. The
174 // first entry represents the root level of the repository, followed by the
175 // first subtree--let's call this A--of the root level (with its name
176 // relative to the root level), followed by the first subtree of A (with
177 // its name relative to A), ...
178 //
179 // === Resolve undo
180 //
181 // A conflict is represented in the index as a set of higher stage entries.
182 // When a conflict is resolved (e.g. with "git add path"), these higher
183 // stage entries will be removed and a stage-0 entry with proper resolution
184 // is added.
185 //
186 // When these higher stage entries are removed, they are saved in the
187 // resolve undo extension, so that conflicts can be recreated (e.g. with
188 // "git checkout -m"), in case users want to redo a conflict resolution
189 // from scratch.
190 //
191 // The signature for this extension is { 'R', 'E', 'U', 'C' }.
192 //
193 // A series of entries fill the entire extension; each of which
194 // consists of:
195 //
196 // - NUL-terminated pathname the entry describes (relative to the root of
197 // the repository, i.e. full pathname);
198 //
199 // - Three NUL-terminated ASCII octal numbers, entry mode of entries in
200 // stage 1 to 3 (a missing stage is represented by "0" in this field);
201 // and
202 //
203 // - At most three 160-bit object names of the entry in stages from 1 to 3
204 // (nothing is written for a missing stage).
205 //
206 // === Split index
207 //
208 // In split index mode, the majority of index entries could be stored
209 // in a separate file. This extension records the changes to be made on
210 // top of that to produce the final index.
211 //
212 // The signature for this extension is { 'l', 'i', 'n', 'k' }.
213 //
214 // The extension consists of:
215 //
216 // - 160-bit SHA-1 of the shared index file. The shared index file path
217 // is $GIT_DIR/sharedindex.<SHA-1>. If all 160 bits are zero, the
218 // index does not require a shared index file.
219 //
220 // - An ewah-encoded delete bitmap, each bit represents an entry in the
221 // shared index. If a bit is set, its corresponding entry in the
222 // shared index will be removed from the final index. Note, because
223 // a delete operation changes index entry positions, but we do need
224 // original positions in replace phase, it's best to just mark
225 // entries for removal, then do a mass deletion after replacement.
226 //
227 // - An ewah-encoded replace bitmap, each bit represents an entry in
228 // the shared index. If a bit is set, its corresponding entry in the
229 // shared index will be replaced with an entry in this index
230 // file. All replaced entries are stored in sorted order in this
231 // index. The first "1" bit in the replace bitmap corresponds to the
232 // first index entry, the second "1" bit to the second entry and so
233 // on. Replaced entries may have empty path names to save space.
234 //
235 // The remaining index entries after replaced ones will be added to the
236 // final index. These added entries are also sorted by entry name then
237 // stage.
238 //
239 // == Untracked cache
240 //
241 // Untracked cache saves the untracked file list and necessary data to
242 // verify the cache. The signature for this extension is { 'U', 'N',
243 // 'T', 'R' }.
244 //
245 // The extension starts with
246 //
247 // - A sequence of NUL-terminated strings, preceded by the size of the
248 // sequence in variable width encoding. Each string describes the
249 // environment where the cache can be used.
250 //
251 // - Stat data of $GIT_DIR/info/exclude. See "Index entry" section from
252 // ctime field until "file size".
253 //
254 // - Stat data of plumbing.excludesfile
255 //
256 // - 32-bit dir_flags (see struct dir_struct)
257 //
258 // - 160-bit SHA-1 of $GIT_DIR/info/exclude. Null SHA-1 means the file
259 // does not exist.
260 //
261 // - 160-bit SHA-1 of plumbing.excludesfile. Null SHA-1 means the file does
262 // not exist.
263 //
264 // - NUL-terminated string of per-dir exclude file name. This usually
265 // is ".gitignore".
266 //
267 // - The number of following directory blocks, variable width
268 // encoding. If this number is zero, the extension ends here with a
269 // following NUL.
270 //
271 // - A number of directory blocks in depth-first-search order, each
272 // consists of
273 //
274 // - The number of untracked entries, variable width encoding.
275 //
276 // - The number of sub-directory blocks, variable width encoding.
277 //
278 // - The directory name terminated by NUL.
279 //
280 // - A number of untracked file/dir names terminated by NUL.
281 //
282 // The remaining data of each directory block is grouped by type:
283 //
284 // - An ewah bitmap, the n-th bit marks whether the n-th directory has
285 // valid untracked cache entries.
286 //
287 // - An ewah bitmap, the n-th bit records "check-only" bit of
288 // read_directory_recursive() for the n-th directory.
289 //
290 // - An ewah bitmap, the n-th bit indicates whether SHA-1 and stat data
291 // is valid for the n-th directory and exists in the next data.
292 //
293 // - An array of stat data. The n-th data corresponds with the n-th
294 // "one" bit in the previous ewah bitmap.
295 //
296 // - An array of SHA-1. The n-th SHA-1 corresponds with the n-th "one" bit
297 // in the previous ewah bitmap.
298 //
299 // - One NUL.
300 //
301 // == File System Monitor cache
302 //
303 // The file system monitor cache tracks files for which the core.fsmonitor
304 // hook has told us about changes. The signature for this extension is
305 // { 'F', 'S', 'M', 'N' }.
306 //
307 // The extension starts with
308 //
309 // - 32-bit version number: the current supported version is 1.
310 //
311 // - 64-bit time: the extension data reflects all changes through the given
312 // time which is stored as the nanoseconds elapsed since midnight,
313 // January 1, 1970.
314 //
315 // - 32-bit bitmap size: the size of the CE_FSMONITOR_VALID bitmap.
316 //
317 // - An ewah bitmap, the n-th bit indicates whether the n-th index entry
318 // is not CE_FSMONITOR_VALID.
319 //
320 // == End of Index Entry
321 //
322 // The End of Index Entry (EOIE) is used to locate the end of the variable
323 // length index entries and the begining of the extensions. Code can take
324 // advantage of this to quickly locate the index extensions without having
325 // to parse through all of the index entries.
326 //
327 // Because it must be able to be loaded before the variable length cache
328 // entries and other index extensions, this extension must be written last.
329 // The signature for this extension is { 'E', 'O', 'I', 'E' }.
330 //
331 // The extension consists of:
332 //
333 // - 32-bit offset to the end of the index entries
334 //
335 // - 160-bit SHA-1 over the extension types and their sizes (but not
336 // their contents). E.g. if we have "TREE" extension that is N-bytes
337 // long, "REUC" extension that is M-bytes long, followed by "EOIE",
338 // then the hash would be:
339 //
340 // SHA-1("TREE" + <binary representation of N> +
341 // "REUC" + <binary representation of M>)
342 //
343 // == Index Entry Offset Table
344 //
345 // The Index Entry Offset Table (IEOT) is used to help address the CPU
346 // cost of loading the index by enabling multi-threading the process of
347 // converting cache entries from the on-disk format to the in-memory format.
348 // The signature for this extension is { 'I', 'E', 'O', 'T' }.
349 //
350 // The extension consists of:
351 //
352 // - 32-bit version (currently 1)
353 //
354 // - A number of index offset entries each consisting of:
355 //
356 // - 32-bit offset from the begining of the file to the first cache entry
357 // in this block of entries.
358 //
359 // - 32-bit count of cache entries in this blockpackage index
360 package index