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