| 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 |