Do a cross-project merge of Paul Mackerras' gitk visualizer
[git/git.git] / README
1 ////////////////////////////////////////////////////////////////
2
3 GIT - the stupid content tracker
4
5 ////////////////////////////////////////////////////////////////
6 "git" can mean anything, depending on your mood.
7
8 - random three-letter combination that is pronounceable, and not
9 actually used by any common UNIX command. The fact that it is a
10 mispronunciation of "get" may or may not be relevant.
11 - stupid. contemptible and despicable. simple. Take your pick from the
12 dictionary of slang.
13 - "global information tracker": you're in a good mood, and it actually
14 works for you. Angels sing, and a light suddenly fills the room.
15 - "goddamn idiotic truckload of sh*t": when it breaks
16
17 This is a stupid (but extremely fast) directory content manager. It
18 doesn't do a whole lot, but what it _does_ do is track directory
19 contents efficiently.
20
21 There are two object abstractions: the "object database", and the
22 "current directory cache" aka "index".
23
24 The Object Database
25 ~~~~~~~~~~~~~~~~~~~
26 The object database is literally just a content-addressable collection
27 of objects. All objects are named by their content, which is
28 approximated by the SHA1 hash of the object itself. Objects may refer
29 to other objects (by referencing their SHA1 hash), and so you can
30 build up a hierarchy of objects.
31
32 All objects have a statically determined "type" aka "tag", which is
33 determined at object creation time, and which identifies the format of
34 the object (i.e. how it is used, and how it can refer to other
35 objects). There are currently five different object types: "blob",
36 "tree", "commit", "tag" and "delta"
37
38 A "blob" object cannot refer to any other object, and is, like the tag
39 implies, a pure storage object containing some user data. It is used to
40 actually store the file data, i.e. a blob object is associated with some
41 particular version of some file.
42
43 A "tree" object is an object that ties one or more "blob" objects into a
44 directory structure. In addition, a tree object can refer to other tree
45 objects, thus creating a directory hierarchy.
46
47 A "commit" object ties such directory hierarchies together into
48 a DAG of revisions - each "commit" is associated with exactly one tree
49 (the directory hierarchy at the time of the commit). In addition, a
50 "commit" refers to one or more "parent" commit objects that describe the
51 history of how we arrived at that directory hierarchy.
52
53 As a special case, a commit object with no parents is called the "root"
54 object, and is the point of an initial project commit. Each project
55 must have at least one root, and while you can tie several different
56 root objects together into one project by creating a commit object which
57 has two or more separate roots as its ultimate parents, that's probably
58 just going to confuse people. So aim for the notion of "one root object
59 per project", even if git itself does not enforce that.
60
61 A "tag" object symbolically identifies and can be used to sign other
62 objects. It contains the identifier and type of another object, a
63 symbolic name (of course!) and, optionally, a signature.
64
65 A "delta" object is used internally by the object database to minimise
66 disk usage. Instead of storing the entire contents of a revision, git
67 can behave in a similar manner to RCS et al and simply store a delta.
68
69 Regardless of object type, all objects share the following
70 characteristics: they are all deflated with zlib, and have a header
71 that not only specifies their tag, but also provides size information
72 about the data in the object. It's worth noting that the SHA1 hash
73 that is used to name the object is the hash of the original data or
74 the delta. (Historical note: in the dawn of the age of git the hash
75 was the sha1 of the _compressed_ object)
76
77 As a result, the general consistency of an object can always be tested
78 independently of the contents or the type of the object: all objects can
79 be validated by verifying that (a) their hashes match the content of the
80 file and (b) the object successfully inflates to a stream of bytes that
81 forms a sequence of <ascii tag without space> + <space> + <ascii decimal
82 size> + <byte\0> + <binary object data>.
83
84 The structured objects can further have their structure and
85 connectivity to other objects verified. This is generally done with
86 the "git-fsck-cache" program, which generates a full dependency graph
87 of all objects, and verifies their internal consistency (in addition
88 to just verifying their superficial consistency through the hash).
89
90 The object types in some more detail:
91
92 Blob Object
93 ~~~~~~~~~~~
94 A "blob" object is nothing but a binary blob of data, and doesn't
95 refer to anything else. There is no signature or any other
96 verification of the data, so while the object is consistent (it _is_
97 indexed by its sha1 hash, so the data itself is certainly correct), it
98 has absolutely no other attributes. No name associations, no
99 permissions. It is purely a blob of data (i.e. normally "file
100 contents").
101
102 In particular, since the blob is entirely defined by its data, if two
103 files in a directory tree (or in multiple different versions of the
104 repository) have the same contents, they will share the same blob
105 object. The object is totally independent of it's location in the
106 directory tree, and renaming a file does not change the object that
107 file is associated with in any way.
108
109 A blob is created with link:git-write-blob.html[git-write-blob] and
110 it's data can be accessed by link:git-cat-file.html[git-cat-file]
111
112 Tree Object
113 ~~~~~~~~~~~
114 The next hierarchical object type is the "tree" object. A tree object
115 is a list of mode/name/blob data, sorted by name. Alternatively, the
116 mode data may specify a directory mode, in which case instead of
117 naming a blob, that name is associated with another TREE object.
118
119 Like the "blob" object, a tree object is uniquely determined by the
120 set contents, and so two separate but identical trees will always
121 share the exact same object. This is true at all levels, i.e. it's
122 true for a "leaf" tree (which does not refer to any other trees, only
123 blobs) as well as for a whole subdirectory.
124
125 For that reason a "tree" object is just a pure data abstraction: it
126 has no history, no signatures, no verification of validity, except
127 that since the contents are again protected by the hash itself, we can
128 trust that the tree is immutable and its contents never change.
129
130 So you can trust the contents of a tree to be valid, the same way you
131 can trust the contents of a blob, but you don't know where those
132 contents _came_ from.
133
134 Side note on trees: since a "tree" object is a sorted list of
135 "filename+content", you can create a diff between two trees without
136 actually having to unpack two trees. Just ignore all common parts,
137 and your diff will look right. In other words, you can effectively
138 (and efficiently) tell the difference between any two random trees by
139 O(n) where "n" is the size of the difference, rather than the size of
140 the tree.
141
142 Side note 2 on trees: since the name of a "blob" depends entirely and
143 exclusively on its contents (i.e. there are no names or permissions
144 involved), you can see trivial renames or permission changes by
145 noticing that the blob stayed the same. However, renames with data
146 changes need a smarter "diff" implementation.
147
148 A tree is created with link:git-write-tree.html[git-write-tree] and
149 it's data can be accessed by link:git-ls-tree.html[git-ls-tree]
150
151 Commit Object
152 ~~~~~~~~~~~~~
153 The "commit" object is an object that introduces the notion of
154 history into the picture. In contrast to the other objects, it
155 doesn't just describe the physical state of a tree, it describes how
156 we got there, and why.
157
158 A "commit" is defined by the tree-object that it results in, the
159 parent commits (zero, one or more) that led up to that point, and a
160 comment on what happened. Again, a commit is not trusted per se:
161 the contents are well-defined and "safe" due to the cryptographically
162 strong signatures at all levels, but there is no reason to believe
163 that the tree is "good" or that the merge information makes sense.
164 The parents do not have to actually have any relationship with the
165 result, for example.
166
167 Note on commits: unlike real SCM's, commits do not contain
168 rename information or file mode chane information. All of that is
169 implicit in the trees involved (the result tree, and the result trees
170 of the parents), and describing that makes no sense in this idiotic
171 file manager.
172
173 A commit is created with link:git-commit-tree.html[git-commit-tree] and
174 it's data can be accessed by link:git-cat-file.html[git-cat-file]
175
176 Trust
177 ~~~~~
178 An aside on the notion of "trust". Trust is really outside the scope
179 of "git", but it's worth noting a few things. First off, since
180 everything is hashed with SHA1, you _can_ trust that an object is
181 intact and has not been messed with by external sources. So the name
182 of an object uniquely identifies a known state - just not a state that
183 you may want to trust.
184
185 Furthermore, since the SHA1 signature of a commit refers to the
186 SHA1 signatures of the tree it is associated with and the signatures
187 of the parent, a single named commit specifies uniquely a whole set
188 of history, with full contents. You can't later fake any step of the
189 way once you have the name of a commit.
190
191 So to introduce some real trust in the system, the only thing you need
192 to do is to digitally sign just _one_ special note, which includes the
193 name of a top-level commit. Your digital signature shows others
194 that you trust that commit, and the immutability of the history of
195 commits tells others that they can trust the whole history.
196
197 In other words, you can easily validate a whole archive by just
198 sending out a single email that tells the people the name (SHA1 hash)
199 of the top commit, and digitally sign that email using something
200 like GPG/PGP.
201
202 To assist in this, git also provides the tag object...
203
204 Tag Object
205 ~~~~~~~~~~
206 Git provides the "tag" object to simplify creating, managing and
207 exchanging symbolic and signed tokens. The "tag" object at its
208 simplest simply symbolically identifies another object by containing
209 the sha1, type and symbolic name.
210
211 However it can optionally contain additional signature information
212 (which git doesn't care about as long as there's less than 8k of
213 it). This can then be verified externally to git.
214
215 Note that despite the tag features, "git" itself only handles content
216 integrity; the trust framework (and signature provision and
217 verification) has to come from outside.
218
219 A tag is created with link:git-mktag.html[git-mktag] and
220 it's data can be accessed by link:git-cat-file.html[git-cat-file]
221
222 Delta Object
223 ~~~~~~~~~~~~
224
225 The "delta" object is used internally by the object database to
226 minimise storage usage by using xdeltas (byte level diffs). Deltas can
227 form chains of arbitrary length as RCS does (although this is
228 configureable at creation time). Most operations won't see or even be
229 aware of delta objects as they are automatically 'applied' and appear
230 as 'real' git objects In other words, if you write your own routines
231 to look at the contents of the object database then you need to know
232 about this - otherwise you don't. Actually, that's not quite true -
233 one important area where deltas are likely to prove very valuable is
234 in reducing bandwidth loads - so the more sophisticated network tools
235 for git repositories will be aware of them too.
236
237 Finally, git repositories can (and must) be deltafied in the
238 background - the work to calculate the differences does not take place
239 automatically at commit time.
240
241 A delta can be created (or undeltafied) with
242 link:git-mkdelta.html[git-mkdelta] it's raw data cannot be accessed at
243 present.
244
245
246 The "index" aka "Current Directory Cache"
247 -----------------------------------------
248 The index is a simple binary file, which contains an efficient
249 representation of a virtual directory content at some random time. It
250 does so by a simple array that associates a set of names, dates,
251 permissions and content (aka "blob") objects together. The cache is
252 always kept ordered by name, and names are unique (with a few very
253 specific rules) at any point in time, but the cache has no long-term
254 meaning, and can be partially updated at any time.
255
256 In particular, the index certainly does not need to be consistent with
257 the current directory contents (in fact, most operations will depend on
258 different ways to make the index _not_ be consistent with the directory
259 hierarchy), but it has three very important attributes:
260
261 '(a) it can re-generate the full state it caches (not just the
262 directory structure: it contains pointers to the "blob" objects so
263 that it can regenerate the data too)'
264
265 As a special case, there is a clear and unambiguous one-way mapping
266 from a current directory cache to a "tree object", which can be
267 efficiently created from just the current directory cache without
268 actually looking at any other data. So a directory cache at any one
269 time uniquely specifies one and only one "tree" object (but has
270 additional data to make it easy to match up that tree object with what
271 has happened in the directory)
272
273 '(b) it has efficient methods for finding inconsistencies between that
274 cached state ("tree object waiting to be instantiated") and the
275 current state.'
276
277 '(c) it can additionally efficiently represent information about merge
278 conflicts between different tree objects, allowing each pathname to be
279 associated with sufficient information about the trees involved that
280 you can create a three-way merge between them.'
281
282 Those are the three ONLY things that the directory cache does. It's a
283 cache, and the normal operation is to re-generate it completely from a
284 known tree object, or update/compare it with a live tree that is being
285 developed. If you blow the directory cache away entirely, you generally
286 haven't lost any information as long as you have the name of the tree
287 that it described.
288
289 At the same time, the directory index is at the same time also the
290 staging area for creating new trees, and creating a new tree always
291 involves a controlled modification of the index file. In particular,
292 the index file can have the representation of an intermediate tree that
293 has not yet been instantiated. So the index can be thought of as a
294 write-back cache, which can contain dirty information that has not yet
295 been written back to the backing store.
296
297
298
299 The Workflow
300 ------------
301 Generally, all "git" operations work on the index file. Some operations
302 work *purely* on the index file (showing the current state of the
303 index), but most operations move data to and from the index file. Either
304 from the database or from the working directory. Thus there are four
305 main combinations:
306
307 1) working directory -> index
308 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
309
310 You update the index with information from the working directory with
311 the link:git-update-cache.html[git-update-cache] command. You
312 generally update the index information by just specifying the filename
313 you want to update, like so:
314
315 git-update-cache filename
316
317 but to avoid common mistakes with filename globbing etc, the command
318 will not normally add totally new entries or remove old entries,
319 i.e. it will normally just update existing cache entries.
320
321 To tell git that yes, you really do realize that certain files no
322 longer exist in the archive, or that new files should be added, you
323 should use the "--remove" and "--add" flags respectively.
324
325 NOTE! A "--remove" flag does _not_ mean that subsequent filenames will
326 necessarily be removed: if the files still exist in your directory
327 structure, the index will be updated with their new status, not
328 removed. The only thing "--remove" means is that update-cache will be
329 considering a removed file to be a valid thing, and if the file really
330 does not exist any more, it will update the index accordingly.
331
332 As a special case, you can also do "git-update-cache --refresh", which
333 will refresh the "stat" information of each index to match the current
334 stat information. It will _not_ update the object status itself, and
335 it will only update the fields that are used to quickly test whether
336 an object still matches its old backing store object.
337
338 2) index -> object database
339 ~~~~~~~~~~~~~~~~~~~~~~~~~~~
340
341 You write your current index file to a "tree" object with the program
342
343 git-write-tree
344
345 that doesn't come with any options - it will just write out the
346 current index into the set of tree objects that describe that state,
347 and it will return the name of the resulting top-level tree. You can
348 use that tree to re-generate the index at any time by going in the
349 other direction:
350
351 3) object database -> index
352 ~~~~~~~~~~~~~~~~~~~~~~~~~~~
353
354 You read a "tree" file from the object database, and use that to
355 populate (and overwrite - don't do this if your index contains any
356 unsaved state that you might want to restore later!) your current
357 index. Normal operation is just
358
359 git-read-tree <sha1 of tree>
360
361 and your index file will now be equivalent to the tree that you saved
362 earlier. However, that is only your _index_ file: your working
363 directory contents have not been modified.
364
365 4) index -> working directory
366 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
367
368 You update your working directory from the index by "checking out"
369 files. This is not a very common operation, since normally you'd just
370 keep your files updated, and rather than write to your working
371 directory, you'd tell the index files about the changes in your
372 working directory (i.e. "git-update-cache").
373
374 However, if you decide to jump to a new version, or check out somebody
375 else's version, or just restore a previous tree, you'd populate your
376 index file with read-tree, and then you need to check out the result
377 with
378 git-checkout-cache filename
379
380 or, if you want to check out all of the index, use "-a".
381
382 NOTE! git-checkout-cache normally refuses to overwrite old files, so
383 if you have an old version of the tree already checked out, you will
384 need to use the "-f" flag (_before_ the "-a" flag or the filename) to
385 _force_ the checkout.
386
387
388 Finally, there are a few odds and ends which are not purely moving
389 from one representation to the other:
390
391 5) Tying it all together
392 ~~~~~~~~~~~~~~~~~~~~~~~~
393 To commit a tree you have instantiated with "git-write-tree", you'd
394 create a "commit" object that refers to that tree and the history
395 behind it - most notably the "parent" commits that preceded it in
396 history.
397
398 Normally a "commit" has one parent: the previous state of the tree
399 before a certain change was made. However, sometimes it can have two
400 or more parent commits, in which case we call it a "merge", due to the
401 fact that such a commit brings together ("merges") two or more
402 previous states represented by other commits.
403
404 In other words, while a "tree" represents a particular directory state
405 of a working directory, a "commit" represents that state in "time",
406 and explains how we got there.
407
408 You create a commit object by giving it the tree that describes the
409 state at the time of the commit, and a list of parents:
410
411 git-commit-tree <tree> -p <parent> [-p <parent2> ..]
412
413 and then giving the reason for the commit on stdin (either through
414 redirection from a pipe or file, or by just typing it at the tty).
415
416 git-commit-tree will return the name of the object that represents
417 that commit, and you should save it away for later use. Normally,
418 you'd commit a new "HEAD" state, and while git doesn't care where you
419 save the note about that state, in practice we tend to just write the
420 result to the file ".git/HEAD", so that we can always see what the
421 last committed state was.
422
423 6) Examining the data
424 ~~~~~~~~~~~~~~~~~~~~~
425
426 You can examine the data represented in the object database and the
427 index with various helper tools. For every object, you can use
428 link:git-cat-file.html[git-cat-file] to examine details about the
429 object:
430
431 git-cat-file -t <objectname>
432
433 shows the type of the object, and once you have the type (which is
434 usually implicit in where you find the object), you can use
435
436 git-cat-file blob|tree|commit <objectname>
437
438 to show its contents. NOTE! Trees have binary content, and as a result
439 there is a special helper for showing that content, called
440 "git-ls-tree", which turns the binary content into a more easily
441 readable form.
442
443 It's especially instructive to look at "commit" objects, since those
444 tend to be small and fairly self-explanatory. In particular, if you
445 follow the convention of having the top commit name in ".git/HEAD",
446 you can do
447
448 git-cat-file commit $(cat .git/HEAD)
449
450 to see what the top commit was.
451
452 7) Merging multiple trees
453 ~~~~~~~~~~~~~~~~~~~~~~~~~
454
455 Git helps you do a three-way merge, which you can expand to n-way by
456 repeating the merge procedure arbitrary times until you finally
457 "commit" the state. The normal situation is that you'd only do one
458 three-way merge (two parents), and commit it, but if you like to, you
459 can do multiple parents in one go.
460
461 To do a three-way merge, you need the two sets of "commit" objects
462 that you want to merge, use those to find the closest common parent (a
463 third "commit" object), and then use those commit objects to find the
464 state of the directory ("tree" object) at these points.
465
466 To get the "base" for the merge, you first look up the common parent
467 of two commits with
468
469 git-merge-base <commit1> <commit2>
470
471 which will return you the commit they are both based on. You should
472 now look up the "tree" objects of those commits, which you can easily
473 do with (for example)
474
475 git-cat-file commit <commitname> | head -1
476
477 since the tree object information is always the first line in a commit
478 object.
479
480 Once you know the three trees you are going to merge (the one
481 "original" tree, aka the common case, and the two "result" trees, aka
482 the branches you want to merge), you do a "merge" read into the
483 index. This will throw away your old index contents, so you should
484 make sure that you've committed those - in fact you would normally
485 always do a merge against your last commit (which should thus match
486 what you have in your current index anyway).
487
488 To do the merge, do
489
490 git-read-tree -m <origtree> <target1tree> <target2tree>
491
492 which will do all trivial merge operations for you directly in the
493 index file, and you can just write the result out with
494 "git-write-tree".
495
496 NOTE! Because the merge is done in the index file, and not in your
497 working directory, your working directory will no longer match your
498 index. You can use "git-checkout-cache -f -a" to make the effect of
499 the merge be seen in your working directory.
500
501 NOTE2! Sadly, many merges aren't trivial. If there are files that have
502 been added.moved or removed, or if both branches have modified the
503 same file, you will be left with an index tree that contains "merge
504 entries" in it. Such an index tree can _NOT_ be written out to a tree
505 object, and you will have to resolve any such merge clashes using
506 other tools before you can write out the result.
507
508
509 [ fixme: talk about resolving merges here ]