{"thread":{"id":"23341","subject":"[PATCH 1/7 (v5)] man page and technical docs","startedAt":"2010-04-05T19:57:55Z","lastAt":"2010-04-05T19:57:55Z","messageCount":1,"participants":["Nick Edelen"],"isPatch":true,"patchVersion":5,"patchTotal":7},"messages":[{"id":"138668","messageId":"4BBA40C3.9080404@gmail.com","threadId":"23341","inReplyTo":null,"subject":"[PATCH 1/7 (v5)] man page and technical docs","fromName":"Nick Edelen","fromEmail":"sirnot@gmail.com","sentAt":"2010-04-05T19:57:55Z","receivedAt":"2010-04-05T19:57:55Z","isPatch":true,"sender":{"key":"sirnot@gmail.com","avatar":null},"body":"Before any code is introduced the full documentation is put forth.  This\nprovides a man page for the porcelain, and a technical doc in technical/.  The\nlatter describes the API, and discusses rev-cache's design, file format and\nmechanics.\n\nSigned-off-by: Nick Edelen <sirnot@gmail.com>\n\n---\n Documentation/git-rev-cache.txt       |  194 ++++++++++\n Documentation/technical/rev-cache.txt |  634 +++++++++++++++++++++++++++++++++\n command-list.txt                      |    1 +\n 3 files changed, 829 insertions(+), 0 deletions(-)\n\ndiff --git a/Documentation/git-rev-cache.txt b/Documentation/git-rev-cache.txt\nnew file mode 100644\nindex 0000000..20d98c6\n--- /dev/null\n+++ b/Documentation/git-rev-cache.txt\n@@ -0,0 +1,194 @@\n+git-rev-cache(1)\n+================\n+\n+NAME\n+----\n+git-rev-cache - Add, walk and maintain revision cache slices\n+\n+SYNOPSIS\n+--------\n+'git-rev-cache' COMMAND [options] [<commit>...]\n+\n+DESCRIPTION\n+-----------\n+The revision cache ('rev-cache') provides a mechanism for significantly\n+speeding up revision traversals.  It does this by creating an efficient\n+database (cache) of commits, their related objects and topological relations.\n+Independant of packs and the object store, this database is composed of\n+rev-cache \"slices\" -- each a different file storing a given segment of commit\n+history.  To map commits to their respective slices, a single index file is\n+kept for the rev-cache.\n+\n+'git-rev-cache' provides a front-end for the rev-cache mechanism, intended for\n+updating and maintaining rev-cache slices in the current repository.  New cache\n+slice files can be 'add'ed, to keep the cache up-to-date; individual slices can\n+be traversed; smaller slices can be 'fuse'd into a larger slice; and the\n+rev-cache index can be regenerated.\n+\n+COMMANDS\n+--------\n+\n+add\n+~~~\n+Add revisions to the cache by creating a new cache slice.  Reads a revision\n+list from the command line, formatted as: `START START ... \\--not END END ...`\n+\n+Options\n+^^^^^^^\n+\n+\\--all::\n+\tInclude all refs in the new cache slice, like the \\--all option in\n+\t'rev-list'.\n+\n+\\--fresh/\\--incremental::\n+\tExclude everything already in the revision cache, analogous to\n+\t\\--incremental in 'pack-objects'.\n+\n+\\--stdin::\n+\tRead newline-seperated revisions from the standard input.  Use \\--not\n+\tto exclude commits, as on the command line.\n+\n+\\--legs/\\--close::\n+\tEnsure newly-generated cache slice has no partial ends, simplifying the\n+definition of 'end' to be the true analog of 'start': having *none* of its\n+parents in the same slice.  99.9% of users can ignore this command.\n++\n+\\--legs will cause 'rev-cache' to expand potential slice end-points (creating\n+\"legs\") until this condition is met, simplifying the cache slice structure.\n+'rev-cache' itself does not care if a slice has legs or not, but the condition\n+may reduce the required complexity of other applications that might use the\n+revision cache.\n+\n+\\--no-objects::\n+\tNon-commit objects are normally included along with the commit with\n+\twhich they were introduced.  This is obviously very benificial, but can\n+\ttake longer in cache slice generation.  Using this option will disable\n+\tnon-commit object caching.\n++\n+\\--no-objects is mainly intended for debugging or development purposes, but may\n+find use in special situations (e.g. common traversal of only commits).  Note\n+that traversal output correctness will not be affected by this option -- it will\n+simply traverse the object trees itself.\n+\n+Output\n+^^^^^^\n+\n+On `stderr` 'add' outputs general information about the generated slice,\n+including the number of objects and paths, and the start/end commits (prefix S\n+indicates start, E an end).  Through `stdout` it emits only the SHA-1 of the\n+slice.\n+\n+walk\n+~~~~\n+Analogous to a slice-oriented 'rev-list', 'walk' will walk commits contained in\n+a region of one cache slice.  Interesting and uninteresting (delimited, as with\n+'rev-list', with \\--not) are specified on the command line, and output is the\n+same as vanilla 'rev-list'.  Note that information outputted is limited by the\n+information contained in the slice.\n+\n+Options\n+^^^^^^^\n+\n+\\--objects::\n+\tLike 'rev-list', 'walk' will normally only list commits.  Use this\n+\toption to list non-commit objects as well, if they are present in the\n+\tcache slice.\n+\n+Output\n+^^^^^^\n+\n+'walk' will simply dump the contents of the output commit list, work list, and\n+pending object array.  The headers are outputted on `stderr`, the object hashes\n+and names on `stdout`.\n+\n+fuse\n+~~~~\n+Merge several cache slices into a single large slice, like 'repack' for\n+'rev-cache'.  On each invocation of 'add' a new file (\"slice\") is added to the\n+revision cache directory, and after several additions the directory may become\n+populated with many, relatively small slices.  Numerous smaller slices will\n+yield poorer performance than a one or two large ones, because of the overhead\n+of loading new slices into memory.\n+\n+Running 'fuse' every once in a while will solve this problem by coalescing all\n+the cache slices into one larger slice.  For very large projects, using\n+\\--ignore-size is advisable to prevent overly large cache slices.  This can be\n+set to run on garbage collection; see 'Automation' for more info.\n+\n+Note that 'fuse' uses the internal revision walker, so the options used in\n+fusion override those of the cache slices upon which it operates.  For example,\n+if some slices were generated with \\--no-objects, yet 'fuse' was performed with\n+non-commit objects, the resulting slice would still contain objects but would\n+take longer to generate.\n+\n+Options\n+^^^^^^^\n+\n+\\--all::\n+\tNormally fuse will only include everything that's already in the\n+\trevision cache.  \\--all tells it to start walking from the branch\n+\theads, effectively a `add --all --fresh; fuse`\n+\t(pseudo-revcache-command).\n+\n+\\--no-objects::\n+\tAs in 'add', this option disables inclusion of non-commit objects.  If\n+\tsome cache slices do contain such objects, the information will be lost.\n+\n+\\--ignore-size[=N]/\\--keep-size[=N]::\n+\tDo not merge cache slices of size >=N (be aware that slices must be\n+\tmapped to memory).  N can have a suffix of \"k\" or \"m\", denoting N as\n+\tkilobytes and megabytes, respectively.  If N is not provided 'fuse'\n+\twill default to a size specified in `revcache.ignoresize`, or ~25MB if\n+\tthe config var is not set.\n+\n+Output\n+^^^^^^\n+\n+This command prints the SHA-1 of the new slice on `stdout`, and information\n+about its work on `stderr` -- specifically which files it's removing.\n+\n+Automation\n+^^^^^^^^^^\n+\n+Set the git configuration variable `gc.revcache` to run 'fuse' on garbage\n+collection.  The arguments passed are `fuse \\--all \\--ignore-size`; i.e. 'gc'\n+will keep everything cached into size-regulated slices.\n+\n+index\n+~~~~~\n+Regenerate the revision cache index.  If the rev-cache index file associating\n+objects with cache slices gets corrupted, lost, or otherwise becomes unusable,\n+'index' will quickly regenerate the file.  It's most likely that this won't be\n+needed in every day use, as it is targeted towards debugging and development,\n+but is a useful fallback.\n+\n+alt\n+~~~\n+Create a cache slice pointer to another slice, identified by its full path:\n+`alt path/to/other/slice`\n+\n+This command is useful if you have several repositories sharing a common\n+history.  Although space requirements for rev-cache are slim anyway, you can in\n+this situation reduce it further by using slice pointers, pointing to relavant\n+slices in other repositories.  Note that only one level of redirection is\n+allowed, and the slice pointer will break if the original slice is removed.\n+'fuse' will not touch slice pointers.\n+\n+NOTES\n+-----\n+In certain circumstances there may be some inconsistencies with object names\n+between cached and non-cached walks.  Specifically, if two objects in a commit\n+tree have the same content (= same SHA-1); or if objects of the same SHA-1 are\n+introduced independantly in parallel branches.\n+\n+In the first case rev-cache will use the name of the youngest file, while\n+vanilla rev-list will return the name of the entry first encountered in walking\n+the tree.  The latter case is a result of rev-cache's internal topological\n+ordering: the difference is the same between sorted and unsorted revision walks.\n+\n+See 'Discussion' for the underlying reasons for the discrepencies.\n+\n+DISCUSSION\n+----------\n+For an explanation of the API and its inner workings, see\n+link:technical/rev-cache.txt[technical info on rev-cache].\ndiff --git a/Documentation/technical/rev-cache.txt b/Documentation/technical/rev-cache.txt\nnew file mode 100644\nindex 0000000..91fce8b\n--- /dev/null\n+++ b/Documentation/technical/rev-cache.txt\n@@ -0,0 +1,634 @@\n+rev-cache\n+=========\n+\n+The revision cache API ('rev-cache') provides a method for efficiently storing\n+and accessing commit branch sections.  Such branch slices are defined by a\n+series of start/top (interesting) and end/bottom (uninteresting) commits.  Each\n+slice contains information on commits in topological order.  Recorded with each\n+commit is:\n+\n+* All intra-slice topological relations, encoded into path \"channels\" (see\n+  'Mechanics' for full explanation).\n+* Object meta-data: type, SHA-1, size, date (for commits).\n+* Objects introduced by that commit, not present in the its cached parents.\n+\n+In addition to the API, basic structures are exported for the possibility of\n+direct access.\n+\n+The API\n+-------\n+You can find the function prototypes in `revision.h`.\n+\n+Data Structures\n+~~~~~~~~~~~~~~~\n+The `rev_cache_info` struct holds all the options and flags for the API.\n+\n+----\n+struct rev_cache_info {\n+\t/* generation flags */\n+\tunsigned objects : 1,\n+\t\tlegs : 1,\n+\t\tmake_index : 1,\n+\t\tfuse_me : 1;\n+\n+\t/* index inclusion */\n+\tunsigned overwrite_all : 1;\n+\n+\t/* traversal flags */\n+\tunsigned add_to_pending : 1;\n+\n+\t/* fuse options */\n+\tunsigned int ignore_size;\n+\n+\t/* reserved */\n+\tstruct rev_cache_slice_map *maps,\n+\t\t*last_map;\n+};\n+----\n+\n+The fields:\n+\n+`objects`::\n+\tAdd non-commit objects to slice.\n+\n+`legs`::\n+\tEnsure end/bottom commits have no children.\n+\n+`make_index`::\n+\tIntegrate newly-made slice into index.\n+\n+`fuse_me`::\n+\tThis is specified if a fuse is occuring, and slices are to be reused.\n+\tThis option requires `maps` and `last_maps` to be initialized.\n+\n+`overwrite_all`::\n+\tWhen a cache slice is added to the index, sometimes overlap occures\n+\tbetween it and other slices.  Normally, original index entries are kept\n+\tunless the new entry represents a start commit (older entries are more\n+\tlikely to lead to greater in-slice traversals).  This options overrides\n+\tthat, and updates all entries of the new slice.\n+\n+`add_to_pending`::\n+\tAppend unique non-commit objects to the `pending` object list in the\n+\tpassed `rev_info` instance.\n+\n+`add_names`::\n+\tInclude non-commit object names in the pending object entries if\n+\t`add_to_pending` is set.\n+\n+`ignore_size`::\n+\tIf non-zero, ignore slices with size greater or equal to this during\n+fusion.\n+\n+`maps`/`last_map`::\n+\tAn array of slice mappings, indexed by their id in the slice index\n+\theader, to be re-used with `fuse_me`.  `last_map` points to the last\n+\tmapping used, and should be initialized to 0.\n+\n+Functions\n+~~~~~~~~~\n+\n+init_rev_cache\n+^^^^^^^^^^^^^^\n+----\n+void init_rev_cache_info(\n+\tstruct rev_cache_info *rci OUT\n+)\n+----\n+\n+Initialize `rci` to default options.\n+\n+make_cache_slice\n+^^^^^^^^^^^^^^^^\n+----\n+int make_cache_slice(\n+\tstruct rev_cache_info *rci IN,\n+\tstruct rev_info *revs IN,\n+\tstruct commit_list **starts IN/OUT,\n+\tstruct commit_list **ends IN/OUT,\n+\tunsigned char *cache_sha1 OUT\n+)\n+----\n+\n+Create a cache slice based on either `revs` (if non-NULL) *or* the `starts` and\n+`ends` lists.  The actual list of start and end commits of the slice may be\n+different from the parameters, based on what defines the branch segment, and\n+this actual list is passed back through `starts` and `ends`.\n+\n+The cache slice is identified via a SHA-1 generated from the actual start/end\n+commit lists.  `cache_sha1`, if non-NULL, can recieve the cache slice name.\n+`rci` is used to specify generation options, but can be NULL if you want\n+`make_cache_slice` to fall back on defaults.  Returns 0 on success, non-zero on\n+failure.\n+\n+make_cache_index\n+^^^^^^^^^^^^^^^^\n+----\n+int make_cache_index(\n+\tstruct rev_cache_info *rci IN,\n+\tunsigned char *cache_sha1 IN,\n+\tint fd IN,\n+\tunsigned int size IN\n+)\n+----\n+\n+Add a slice to the rev-cache index.  `cache_sha1` is the identity hash of the\n+cache slice; `fd` is a file descriptor of the cache slice opened with\n+read/write privileges (the slice is not actually modified); `size` is the size\n+of the cache slice.  Although there are currently no options for index\n+updating, `rci` is a placeholder in case of future options.  Note that this\n+function is normally called by `make_cache_slice`.  Returns 0 on success,\n+non-zero on failure.\n+\n+open_cache_slice\n+^^^^^^^^^^^^^^^^\n+----\n+int open_cache_slice(\n+\tunsigned char *sha1 IN,\n+\tint flags IN\n+)\n+----\n+\n+Returns a file descriptor to a cache slice described by `sha1` hash, using\n+`flags` as the access mode.  This will follow cache slice pointers to one level\n+of indirection.\n+\n+get_cache_slice\n+^^^^^^^^^^^^^^^\n+----\n+unsigned char *get_cache_slice(\n+\tstruct commit *commit IN\n+)\n+----\n+\n+Given a commit object `get_cache_slice` will search the revision cache index\n+and return, if found, the cache slice SHA-1.\n+\n+traverse_cache_slice\n+^^^^^^^^^^^^^^^^^^^^\n+----\n+int traverse_cache_slice(\n+\tstruct rev_info *revs IN/OUT,\n+\tunsigned char *cache_sha1 IN,\n+\tstruct commit *commit IN,\n+\tunsigned long *date_so_far IN/OUT,\n+\tint *slop_so_far IN/OUT,\n+\tstruct commit_list ***queue OUT,\n+\tstruct commit_list **work IN/OUT\n+)\n+----\n+\n+Traverse a specified cache slice.  An explanation of the each field:\n+\n+`revs`::\n+\tThe revision walk instance.  `traverse_cache_slice` uses this for\n+\tgeneral options (e.g. which objects are included) and slice traversal\n+\toptions (in the `rev_cache_info` field).  If the `add_to_pending`\n+\toption is specified, non-commit objects are appended to the `pending`\n+\tobject list field.\n+\n+`cache_sha1`::\n+\tSHA-1 identifying the cache slice to use.  This can be taken directly\n+\tfrom `get_cache_slice`.\n+\n+`commit`::\n+\tThe current commit object in the revision walk, i.e. the commit which\n+\tinspired this slice traversal.  Although theoretically redundant in\n+\tview of the `work` list, this simplifies interaction with normal\n+\trevision walks, which pop commits from `work` before analyzing them.\n+\n+`date_so_far`::\n+\tThe date of the oldest encountered interesting commit.  Passing NULL\n+\twill let `traverse_cache_slice` use defaults.\n+\n+`slop_so_far`::\n+\tThe `slop` value, a la revision.c.  This is a counter used to determine\n+\twhen to stop traversing, based on how many extra uninteresting commits\n+\tshould be encountered.  NULL will enable defaults, as above.\n+\n+`queue`::\n+\tRefers to a pointer to the head of a FIFO commit list, recieving the\n+\tcommits we've seen and added.\n+\n+`work`::\n+\tA date-ordered list of commits that have yet to be processed (i.e. seen\n+\tbut not added).  Commits from here present in the slice are removed\n+\t(and, obviously, used as starting places for traversal), and any end\n+\tcommits encountered are inserted.\n+\n+starts_from_slices\n+^^^^^^^^^^^^^^^^^^\n+----\n+void starts_from_slices(\n+\tstruct rev_info *revs OUT,\n+\tunsigned int flags IN,\n+\tunsigned char *which IN,\n+\tint n IN\n+)\n+----\n+\n+Will mark start-commits in certain rev-cache slices with `flag`, and added them\n+to the pending list of `revs`.  If `n` is zero, `starts_from_slices` will use\n+all slices.  Otherwise `which` will specify an *unseperated* list of cache\n+SHA-1s to use (20 bytes each), and `n` will contain the number of slices (i.e.\n+20 * `n` = size of `which`).\n+\n+fuse_cache_slices\n+^^^^^^^^^^^^^^^^^\n+----\n+int fuse_cache_slices(\n+\tstruct rev_cache_info *rci IN,\n+\tstruct rev_info *revs IN\n+)\n+----\n+\n+Generate a slice based on `revs`, replacing all encountered slices with one\n+(larger) slice.  The `ignore_size` field in `rci`, if non-zero, will dictate\n+which cache slice sizes to ignore in both traversal and replacement.\n+\n+regenerate_cache_index\n+^^^^^^^^^^^^^^^^^^^^^^\n+----\n+int regenerate_cache_index(\n+\tstruct rev_cache_info *rci IN\n+)\n+----\n+\n+Remake the revision cache index, including all the slices.  Currently no\n+options in `rci` exist for index (re)generation, but some may develop in the\n+future.\n+\n+to/from_disked_rc_object/index_entry\n+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n+----\n+struct rc_object/index_entry *from_disked_rc_object/index_entry(\n+\tstruct rc_object/index_entry_ondisk *src IN,\n+\tstruct rc_object/index_entry *dst OUT\n+)\n+\n+struct rc_object/index_entry_ondisk *to_disked_rc_object/index_entry(\n+\tstruct rc_object/index_entry *src IN,\n+\tstruct rc_object/index_entry_ondisk *dst OUT\n+)\n+----\n+\n+Functions to convert between the internal and storage (`_ondisk`) versions of\n+object and index entry structures.  These are necessary for direct access to\n+the cache slices.  If NULL is provided for `dst` a statically allocated\n+structure is used, and a pointer to the struct is returned.  Otherwise the\n+functions return `dst`.\n+\n+Example Usage\n+-------------\n+\n+A few examples to demonstrate usage:\n+\n+.Creating a slice\n+----\n+/* pretend you're a porcelain for rev-cache reading from the command line */\n+struct rev_info revs;\n+struct rev_cache_info rci;\n+\n+init_revisions(&revs, 0);\n+init_rci(&rci);\n+\n+flags = 0;\n+for (i = 1; i < argc; i++) {\n+        if (!strcmp(argv[i], \"--not\"))\n+                flags ^= UNINTERESTING;\n+        else if(!strcmp(argv[i], \"--fresh\"))\n+                starts_from_slices(&revs, UNINTERESTING, 0, 0);\n+        else\n+                handle_revision_arg(argv[i], &revs, flags, 1);\n+}\n+\n+/* we want to explicitly set certain options */\n+rci.objects = 0;\n+\n+if (!make_cache_slice(&rci, &revs, 0, 0, cache_sha1))\n+        printf(\"made slice!  it's called %s\\n\", sha1_to_hex(cache_sha1));\n+----\n+\n+.Traversing a slice\n+----\n+/* let's say you're walking the tree with a 'work' list of current heads and a\n+ * FILO output list 'out' */\n+out = 0;\n+outp = &out;\n+\n+while (work) {\n+        struct commit *commit = pop_commit(&work);\n+        struct object *object = &commit->object;\n+        unsigned char *cache_sha1;\n+\n+        if (cache_sha1 = get_cache_slice(object->sha1)) {\n+                /* note that this will instatiate any topo-relations\n+                 * as it goes */\n+                if (traverse_cache_slice(&revs, cache_sha1,\n+                        commit, 0, 0, /* use defaults */\n+                        &outp, &work) < 0)\n+                        die(\"I'm overreacting to a non-fatal cache error\");\n+        } else {\n+                struct commit_list *parents = commit->parents;\n+\n+                while (parents) {\n+                        struct commit *p = parents->item;\n+                        struct object *po = &p->object;\n+\n+                        parents = parents->next;\n+                        if (po->flags & UNINTERESTING)\n+                                continue;\n+\n+                        if (object->flags & UNINTERESTING)\n+                                po->flags |= UNINTERESTING;\n+                        else if (po->flags & SEEN)\n+                                continue;\n+\n+                        if (!po->parsed)\n+                                parse_commit(p);\n+                        insert_by_date(p, &work);\n+                }\n+\n+                if (object->flags & (SEEN | UNINTERESTING) == 0)\n+                        outp = &commit_list_insert(commit, outp)->next;\n+                object->flags |= SEEN;\n+        }\n+}\n+----\n+\n+Some Internals\n+--------------\n+For more advanced usage, the slice and index file(s) may be accessed directly.\n+Relavant structures are availabe in `rev-cache.h`.\n+\n+File Formats\n+~~~~~~~~~~~~\n+\n+Cache Slices\n+^^^^^^^^^^^^\n+A slice has a basic fixed-size header, followed by a certain number of object\n+entries, then a NULL-seperated list of object names.  Commits are sorted in\n+topo-order, and each commit entry is followed by the objects added in that\n+commit.\n+\n+----\n+         -- +--------------------------------+\n+header      | object number, etc...          |\n+         -- +--------------------------------+\n+commit      | commit info                    |\n+entry       | path data                      |\n+            +--------------------------------+\n+            | tree/blob info                 |\n+            +--------------------------------+\n+            | tree/blob info                 |\n+            +--------------------------------+\n+            | ...                            |\n+         -- +--------------------------------+\n+commit      | commit info                    |\n+entry       | path data                      |\n+            +--------------------------------+\n+            | tree/blob info                 |\n+            +--------------------------------+\n+            | ...                            |\n+         -- +--------------------------------+\n+...         ...\n+         -- +--------------------------------+\n+name list   | \\0some_file_name\\0             |\n+(note       +--------------------------------+\n+preceeding  | another_file\\0                 |\n+null)       ...                              |\n+            +--------------------------------+\n+----\n+\n+Here is the header:\n+\n+----\n+struct rc_cache_slice_header {\n+\tchar signature[8]; /* REVCACHE */\n+\tunsigned char version;\n+\tuint32_t ofs_objects;\n+\n+\tuint32_t object_nr;\n+\tuint16_t path_nr;\n+\tuint32_t size;\n+\n+\tunsigned char sha1[20];\n+\n+\tuint32_t names_size;\n+};\n+----\n+\n+Explanations:\n+\n+`signature`::\n+\tThe identifying signature of cache slice file.  Always \"REVCACHE\".\n+`version`::\n+\tThe version number, currently 1.\n+`ofs_objects`::\n+\tThe byte offset at which the commit/object listing starts.  Always\n+\tpresent at the 10th byte, regardless of file version.\n+`object_nr`::\n+\tThe total number of objects (commit + non-commit objects) present in\n+\tthe slice.\n+`path_nr`::\n+\tThe total number of paths/channels used in encoding the topological\n+\tdata.  Note that paths are reused (see 'Mechanics'), so there will\n+\tnever be more than a few hundred paths (if that) used.\n+`size`::\n+\tThe size of the slice *excluding* the name list.  In other words, the\n+\tsize of the portion mapped to memory.\n+`sha1`::\n+\tThe cache slice SHA-1.\n+`names_size`::\n+\tThe size of the name list.  `size` + `names_size` = size of slice\n+\n+Revision Cache Index\n+^^^^^^^^^^^^^^^^^^^^\n+The index is a single file that associates SHA-1s with cache slices and file\n+positions.  It is somewhat similar to pack-file indexes, containing a fanout\n+table and a list of index entries sorted by hash.\n+\n+----\n+         -- +--------------------------------+\n+header      | object #, cache #, etc.        |\n+         -- +--------------------------------+\n+sha1s of    | SHA-1                          |\n+slices      | ...                            |\n+         -- +--------------------------------+\n+fanout      | fanout[0x00]                   |\n+table       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n+            | fanout[0xff]                   |\n+         -- +--------------------------------+\n+index       | SHA-1 of object                |\n+entries     | index of cache slice SHA-1     |\n+            | position in cache slice        |\n+            +--------------------------------+\n+            |                                |\n+            ...\n+            +--------------------------------+\n+----\n+\n+The header:\n+\n+----\n+struct rc_index_header {\n+\tchar signature[8]; /* REVINDEX */\n+\tunsigned char version;\n+\tuint32_t ofs_objects;\n+\n+\tuint32_t object_nr;\n+\tunsigned char cache_nr;\n+\n+\tuint32_t max_date;\n+};\n+----\n+\n+Explanations:\n+\n+`signature`::\n+\tAlways \"REVINDEX\".\n+`version`::\n+\tVersion number, currently 1.\n+`ofs_objects`::\n+\tOffset at which the entry objects begin.  This is more obviously useful\n+\tin the index because the list of slice SHA-1s is variably-sized.\n+`object_nr`::\n+\tNumber of index entry objects present.\n+`cache_nr`::\n+\tNumber of cache slices to which the index maps, and hence the number of\n+slice SHA-1s listed.\n+`max_date`::\n+\tThe oldest commit represented in the index.  This is used to help speed\n+up lookup times by knowing what range of commits we definitely don't have\n+cached.  Normal usage of 'rev-cache' would leave no \"holes\" in its coverage of\n+commit history -- once a commit is cached, everything reachable from it should\n+be cached as well.  Most of the time refs are added to rev-cache simultaneous\n+as well.  This means that in most situations almost everything <= `max_date`\n+will be cached.\n+\n+Mechanics\n+~~~~~~~~~\n+\n+The most important part of rev-cache is its method of encoding topological\n+relations.  To ensure fluid traversal and reconstruction, commits are related\n+through high-level \"streams\"/\"channels\" rather than individual\n+interconnections.  Intuitively, rev-cache stores history the way gitk shows it:\n+commits strung up on lines, which interconnect at merges and branches.\n+\n+Each commit is associated to a given channel/path via a 'path id', and\n+variable-length fields govern which paths (if any) are closed or opened at that\n+object.  This means that topo-data can be preserved in only a few bytes extra\n+per object entry.  Other information stored per entry is the sha-1 hash, type,\n+date, size, name, and status in cache slice.  Here is format of an object\n+entry, both on-disk and in-memory:\n+\n+----\n+struct object_entry {\n+        unsigned type : 3;\n+        unsigned is_end : 1;\n+        unsigned is_start : 1;\n+        unsigned uninteresting : 1;\n+        unsigned include : 1;\n+        unsigned flags : 1;\n+        unsigned char sha1[20];\n+\n+        unsigned char merge_nr;\n+        unsigned char split_nr;\n+        unsigned size_size : 3;\n+        unsigned name_size : 3;\n+\n+        uint32_t date;\n+        uint16_t path;\n+\n+        /* merge paths */\n+        /* split paths */\n+        /* size */\n+        /* name index */\n+};\n+----\n+\n+An explanation of each field:\n+\n+`type`::\n+\tObject type\n+`is_end`::\n+\tThe commit has some parents outside the cache slice (all if slice has\n+\tlegs)\n+`is_start`::\n+\tThe commit has no children in cache slice\n+`uninteresting`::\n+\tRun-time flag, used in traversal\n+`include`::\n+\tRun-time flag, used in traversal (initialization)\n+`flags`::\n+\tCurrently unused, extra bit\n+`sha1`::\n+\tObject SHA-1 hash\n+\n+`merge_nr`::\n+\tThe number of paths the current channel diverges into; the current path\n+\tends upon any merge.\n+`split_nr`::\n+\tThe number of paths this commit ends; used on both merging and\n+\tbranching.\n+`size_size`::\n+\tNumber of bytes the object size takes up.\n+`name_size`::\n+\tNumber of bytes the name index takes up.\n+\n+`date`::\n+\tThe date of the commit.\n+`path`::\n+\tThe path ID of the channel with which this commit is associated.\n+\n+merge paths::\n+\tThe path IDs (16-bit) that are to be created.  Overflow is not a\n+\tproblem as path IDs are reused, leaving even complicated projects to\n+\tconsume no more than a few hundred IDs.\n+split paths::\n+\tThe path IDs (16-bit) that are to be ended.\n+size::\n+\tThe size split into the minimum number of bytes.  That is, 1-8 bytes\n+\trepresenting the size, least-significant byte first.\n+name index::\n+\tAn offset for the null-seperated, object name list at the end of the\n+\tcache slice.  Also split into the minimum number of bytes.\n+\n+Each path ID refers to an index in a 'path array', which stores the current\n+status (eg. active, interestingness) of each channel.\n+\n+Due to topo-relations and boundary tracking, all of a commit's parents must be\n+encountered before the path is reallocated.  This is achieved by using a\n+counter system per merge: starting at the parent number, the counter is\n+decremented as each parent is encountered (dictated by 'split paths'); at 0 the\n+path is cleared.\n+\n+Boundary tracking is necessary because non-commits are stored relative to the\n+commit in which they were introduced.  If a series of commits is not included\n+in the output, the last interesting commit must be parsed manually to ensure\n+all objects are accounted for.\n+\n+To prevent list-objects from recursing into trees that we've already taken care\n+of, the flag `FACE_VALUE` is introduced.  An object with this flag is not\n+explored (= \"taken at face value\"), significantly reducing I/O and processing\n+time.\n+\n+Notes\n+~~~~~\n+\n+Due to rev-cache's internal storage format, walking may lead to some\n+discrepencies between cached and uncached repositories.  Although noticeable to\n+users directly calling rev-list, these are unused or corner cases and\n+internally a non-issue.\n+\n+First note that rev-cache records commits in topological order.  Large portions\n+of commit history will already be sorted topologically in the revision walk,\n+yielding a different output for unsorted calls to rev-list.  A more obscure\n+consquence occurs when two objects of the same SHA-1, but different name, are\n+introduced seperately in parallel branches: different names might be shown for\n+that object depending on which object entry was encountered first.\n+\n+A similar disparity arises when two objects of same SHA-1/different name are\n+present in the same tree structure.  rev-cache, walking objects as they were\n+introduced, lists the youngest file's name; rev-list, walking the full trees\n+each commit, shows the first file encountered.\ndiff --git a/command-list.txt b/command-list.txt\nindex 95bf18c..21fae3f 100644\n--- a/command-list.txt\n+++ b/command-list.txt\n@@ -100,6 +100,7 @@ git-request-pull                        foreignscminterface\n git-rerere                              ancillaryinterrogators\n git-reset                               mainporcelain common\n git-revert                              mainporcelain\n+git-rev-cache                           plumbingmanipulators\n git-rev-list                            plumbinginterrogators\n git-rev-parse                           ancillaryinterrogators\n git-rm                                  mainporcelain common\n-- \ntg: (11766ca..) t/rc/docs (depends on: master)\n"}]}