{"thread":{"id":"20428","subject":"[PATCH 1/5] revision caching documentation: man page and technical discussion","startedAt":"2009-08-06T09:55:23Z","lastAt":"2009-08-07T21:58:14Z","messageCount":5,"participants":["Nick Edelen","Sam Vilain","Rogan Dawes","Johannes Schindelin"],"isPatch":true,"patchVersion":1,"patchTotal":5},"messages":[{"id":"119765","messageId":"op.ux8i6lq9tdk399@sirnot.private","threadId":"20428","inReplyTo":null,"subject":"[PATCH 1/5] revision caching documentation: man page and technical discussion","fromName":"Nick Edelen","fromEmail":"sirnot@gmail.com","sentAt":"2009-08-06T09:55:23Z","receivedAt":"2009-08-06T09:55:23Z","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/rev-cache.txt           |   51 +++++\n Documentation/technical/rev-cache.txt |  336 +++++++++++++++++++++++++++++++++\n 2 files changed, 387 insertions(+), 0 deletions(-)\n\ndiff --git a/Documentation/rev-cache.txt b/Documentation/rev-cache.txt\nnew file mode 100755\nindex 0000000..64bd051\n--- /dev/null\n+++ b/Documentation/rev-cache.txt\n@@ -0,0 +1,51 @@\n+rev-cache porcelain\n+===================\n+\n+A front end for the rev-cache API is provided with the builtin utility \n+`rev-cache`.  It is mainly intended for cache slice generation and maintenance, \n+but can also walk commits within a slice.  At the moment it is not particularly \n+advanced, but is sufficient for repository administration.\n+\n+It's general syntax is:\n+\n+`git-rev-cache COMMAND [options] [<commit-id>...]`\n+\n+With the commands:\n+\n+`add`::\n+\tAdd revisions to the cache.  Reads commit ids from stdin, formatted as:\n+\t`END END ... \\--not START START ...`\n++\n+Options:\n+\n+`\\--all`:: Include all heads as ends.\n+`\\--fresh`:: Exclude everything already in a cache slice.\n+`\\--stdin`:: Also read commit ids from stdin (seperated by newline, `\\--not` \n+also valid).\n+`\\--legs`:: Ensure branch has no \"dangling\" starts (ie. is self-contained).\n+`\\--noobjects`:: Don't include non-commit objects.\n+\n+`walk`::\n+\tWalk a cache slice based on set of commits; formatted as add.\n++\n+Options:\n+\n+`\\--objects`:: Include non-commit objects in traversal.\n+\n+`fuse`::\n+\tCoagulate several cache slices into a single large slice.\n++\n+Options:\n+\n+`\\--all`:: Include all objects in repository.  Will only traverse as of cache \n+ends if this is not specified.\n+`\\--noobjects`:: Don't include non-commit objects.\n+`\\--ignore-size[=N]`:: Do not fuse slices of file size >= `N`.  If `N` is not \n+given the cutoff size defaults to ~5MB.\n+\n+`index`::\n+\tRegenerate the cache index.\n+\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 100755\nindex 0000000..e95ec89\n--- /dev/null\n+++ b/Documentation/technical/rev-cache.txt\n@@ -0,0 +1,336 @@\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 top (interesting) and bottom (uninteresting) commits.  Each slice \n+contains, per commit:\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 in that commit, relative to slice (ie. only for non-start \n+  commits).\n+\n+Storage data structures are not exported, in part to keep git's global scope \n+clean, but largely because they're pretty much useless outside of rev-cache.\n+\n+The API\n+-------\n+\n+The API for 'rev-cache' is quite simple.  You can find the function prototypes \n+in `revision.h`.\n+\n+Data Structures\n+~~~~~~~~~~~~~~~\n+\n+The `rev_cache_info` struct holds all the options and flags for the API.\n+\n+----\n+struct rev_cache_info {\n+        /* generation flags */\n+        unsigned objects : 1, \n+                legs : 1, \n+                make_index : 1;\n+        \n+        /* traversal flags */\n+        unsigned save_unique : 1, \n+                add_to_pending : 1;\n+        \n+        /* fuse options */\n+        unsigned int ignore_size;\n+};\n+----\n+\n+The fields:\n+\n+`objects`:: Add non-commit objects to slice.\n+`legs`:: Ensure bottoms have no childrens.\n+`make_index`:: Integrate newly-made slice into index.\n+`save_unique`:: Load unique non-commit objects into `unique` field of each \n+`commit` object.\n+`add_to_pending`:: Append unique non-commit objects to the `pending` object \n+list in the passed `rev_info` instance.\n+`ignore_size`:: If non-zero, ignore slices with size greater or equal to this.\n+\n+Functions\n+~~~~~~~~~\n+\n+`init_rci`::\n+\n+        Initiate a `rev_cache_info` struct to default options.  \n+\n+`make_cache_slice`::\n+\n+        Create a cache based on an a `rev_info` instance or `commit_list` s of \n+        \"tops\" and \"bottoms\" (defaulting to latter if `rev_info` pointer is \n+        NULL), copying the cache SHA-1 into a passed pointer if non-zero.  A \n+        `rev_cache_info` struct pointer can be passed to set options, while \n+        passing NULL will set default options.  A last parameter can \n+        optionally recieve the final cache hash.\n+\n+`make_cache_index`::\n+\n+        Add a slice to the cache index.  Requires a file descriptor, the cache \n+        hash and the file size.  Note that this is normally called by \n+        `make_cache_slice` under the `make_index` option.\n+\n+`get_cache_slice`::\n+\n+        Given a commit SHA-1 `get_cache_slice` will search the slice index and \n+        return, if found, the cache-identifying SHA-1.\n+\n+`traverse_cache_slice`::\n+\n+        Traverse a specified cache slice based on:\n+\n+        * `rev_cache_info` instance (optional)\n+        * cache SHA-1 identifier\n+        * `rev_info` instance\n+        * a starting commit and commit work list\n+        * date of oldest encountered interesting commit\n+        * current `slop` (this and above mainly used in integration with \n+          revision walker)\n+        \n++\n+The output is sent to a FILO `commit_list` \"queue\", while any bottom commits \n+are passed back into the work list.  If the walk is not contained within the \n+slice, commit boundaries are also inserted into \"work\".\n+\n+`tops_from_slices`::\n+\n+        Will mark all top-commits in the specified cache slices with a given \n+        flag, and add them to the rev pending list.  Will include all if no \n+        slices are specified.\n+\n+`coagulate_cache_slices`::\n+\n+        Generate a slice based on the passed `rev_info` instance, replacing all \n+        encountered slices with one (larger) slice.  The `ignore_size` field in \n+        `rci`, if non-zero, will dictate which cache slice sizes to ignore in \n+        both traversal and replacement.\n+\n+`regenerate_index`::\n+\n+        Remake cache index.\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);\n+                object->flags |= SEEN;\n+        }\n+}\n+----\n+\n+Some Internals\n+--------------\n+\n+Although you really don't need to know anything about how rev-cache actually \n+does its magic shizz, a bit of background may go a long way if you're wading \n+through the source.\n+\n+File Formats\n+~~~~~~~~~~~~\n+\n+A slice has a basic fixed-size header, followed by a certain number of object \n+entries.  Commits are sorted in topo-order, and each commit entry is followed \n+by the objects added in that 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+----\n+\n+The index is somewhat similar to pack-file indexes, containing a fanout table \n+and a list of index entries sorted by hash.\n+\n+----\n+         -- +--------------------------------+\n+header      | object #, cache #, etc.        |\n+         -- +--------------------------------+\n+cache       | SHA-1                          |\n+sha1s       | ...                            |\n+         -- +--------------------------------+\n+fanout      | fanout[0x00]                   |\n+table       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n+            | fanout[0xff]                   |\n+         -- +--------------------------------+\n+index       | entry SHA-1                    |\n+entries     | cache sha1 index               |\n+            +--------------------------------+\n+            |                                |\n+            ...                               \n+            +--------------------------------+\n+----\n+\n+All the relavant structures are readily accessible in `rev-cache.c`\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, and status in cache slice.  Here is format of an object entry, both \n+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 merge_nr : 6;\n+        unsigned split_nr : 7;\n+        unsigned size_size : 3;\n+        \n+\tuint32_t date;\n+\tuint16_t path;\n+        \n+        /* merge paths */\n+        /* split paths */\n+        /* size */\n+};\n+----\n+\n+An explanation of each field:\n+\n+`type`:: Object type\n+`is_end`:: The commit has some parents outside the cache slice (all if slice \n+has legs)\n+`is_start`:: The commit has no children in cache slice\n+`uninteresting`:: Run-time flag, used in traversal\n+`include`:: Run-time flag, used in traversal (initialization)\n+`flags`:: Currently unused, extra bit\n+`sha`:: Object SHA-1 hash\n+\n+`merge_nr`:: The number of paths the current channel diverges into; the current \n+path ends upon any merge.\n+`split_nr`:: The number of paths this commit ends; used on both merging and \n+branching.\n+`size_size`:: Number of bytes the object size takes up.\n+\n+merge paths:: The path IDs (16-bit) that are to be created.\n+split paths:: The path IDs (16-bit) that are to be ended.\n+size:: The size 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+(NSE)\n-- \n"},{"id":"119875","messageId":"4A7B9ACA.1060601@vilain.net","threadId":"20428","inReplyTo":"op.ux8i6lq9tdk399@sirnot.private","subject":"Re: [PATCH 1/5] revision caching documentation: man page and technical discussion","fromName":"Sam Vilain","fromEmail":"sam@vilain.net","sentAt":"2009-08-07T03:08:58Z","receivedAt":"2009-08-07T03:08:58Z","isPatch":true,"sender":{"key":"sam@vilain.net","avatar":"https://gravatar.com/avatar/8fc840ca854dbf6f7065b4335e3b934951c1dca3b11db688e95e471901f8f4a8?d=mp&s=160"},"body":"Nick Edelen wrote:\n> Before any code is introduced the full documentation is put forth.  This \n> provides a man page for the porcelain, and a technical doc in technical/.  The \n> latter describes the API, and discusses rev-cache's design, file format and \n> mechanics.\n>\n> Signed-off-by: Nick Edelen <sirnot@gmail.com>\n>\n> ---\n>  Documentation/rev-cache.txt           |   51 +++++\n>  Documentation/technical/rev-cache.txt |  336 +++++++++++++++++++++++++++++++++\n>  2 files changed, 387 insertions(+), 0 deletions(-)\n>   \n\nA couple of minor nits here:\n\n1. Documentation/rev-cache.txt should be\nDocumentation/git-rev-cache.txt, because it documents that command.\n\n2. there are many whitespace errors:\n\nwilber:~/src/git$ git am \\[PATCH\\ 1_5\\]\\ revision\\ caching\\\ndocumentation\\:\\ man\\ page\\ and\\ technical\\ discussion.eml\nApplying: revision caching documentation: man page and technical discussion\n/home/samv/src/git/.git/rebase-apply/patch:15: trailing whitespace.\nA front end for the rev-cache API is provided with the builtin utility\n/home/samv/src/git/.git/rebase-apply/patch:16: trailing whitespace.\n`rev-cache`.  It is mainly intended for cache slice generation and\nmaintenance,\n/home/samv/src/git/.git/rebase-apply/patch:17: trailing whitespace.\nbut can also walk commits within a slice.  At the moment it is not\nparticularly\n/home/samv/src/git/.git/rebase-apply/patch:34: trailing whitespace.\n`\\--stdin`:: Also read commit ids from stdin (seperated by newline,\n`\\--not`\n/home/samv/src/git/.git/rebase-apply/patch:51: trailing whitespace.\n`\\--all`:: Include all objects in repository.  Will only traverse as of\ncache\nwarning: squelched 166 whitespace errors\nwarning: 171 lines add whitespace errors.\n\nBe sure to check the patch doesn't do that...\n\n> diff --git a/Documentation/rev-cache.txt b/Documentation/rev-cache.txt\n> new file mode 100755\n> index 0000000..64bd051\n> --- /dev/null\n> +++ b/Documentation/rev-cache.txt\n> @@ -0,0 +1,51 @@\n> +rev-cache porcelain\n> +===================\n> +\n> +A front end for the rev-cache API is provided with the builtin utility \n> +`rev-cache`.  It is mainly intended for cache slice generation and maintenance, \n> +but can also walk commits within a slice.  At the moment it is not particularly \n> +advanced, but is sufficient for repository administration.\n>   \n\nThat last sentence is a bit unnecessarily self-doubting; \"It currently\nprovides basic functionality\" would be fine.\n\n> +\n> +It's general syntax is:\n> +\n> +`git-rev-cache COMMAND [options] [<commit-id>...]`\n> +\n> +With the commands:\n>   \n\nYou should use the same structure and headings of this file as the other\nman pages which are found under Documentation/git-*.txt\n\n> +\n> +`add`::\n> +\tAdd revisions to the cache.  Reads commit ids from stdin, formatted as:\n> +\t`END END ... \\--not START START ...`\n>   \n\nReally, it's reading a revision list; might be better to call it that. \nCan it accept the same options as git-rev-list here or just a list of\nstarting points/tips?  And \"END\" and \"START\" are still backwards to the\nrest of git core!\n\n> ++\n> +Options:\n> +\n> +`\\--all`:: Include all heads as ends.\n> +`\\--fresh`:: Exclude everything already in a cache slice.\n>   \n\nIf you use the paragraph layout used by other commands you can explain a\nlittle bit more about what you mean here.  By \"Cache Slice\" do you mean\n\"Revision Cache\"?  Does that --fresh imply that all of the revisions\nwhich were not indexed will automatically get indexed?\n\n> +`\\--stdin`:: Also read commit ids from stdin (seperated by newline, `\\--not` \n> +also valid).\n> +`\\--legs`:: Ensure branch has no \"dangling\" starts (ie. is self-contained).\n>   \n\nThe --legs term is a little too 'cute', is there a better way to\ndescribe this?  And \"starts\" is not a real word in that context; if you\nare using a technical term, you should define it..\n\n> +`\\--noobjects`:: Don't include non-commit objects.\n> +\n> +`walk`::\n> +\tWalk a cache slice based on set of commits; formatted as add.\n>   \n\nSo, this works like 'rev-list' ?\n\n\"Formatted\" is wrong there I think; do you mean it 'accepts the same\narguments as add' ?\n\n> ++\n> +Options:\n> +\n> +`\\--objects`:: Include non-commit objects in traversal.\n> +\n>   \n\nWhich was the default?  --objects or --no-objects?\n\n> +`fuse`::\n> +\tCoagulate several cache slices into a single large slice.\n>   \n\nCoagulate?  You mean, the revision caches will stop being liquid and go\ngluggy, like a pool of blood clotting?\n\nHow about \"combine\" :-) - and the option might be better called\nsomething simple like that, too.\n\n> ++\n> +Options:\n> +\n> +`\\--all`:: Include all objects in repository.  Will only traverse as of cache \n> +ends if this is not specified.\n>   \n\nThat sentence doesn't quite read well to me.\n\n> +`\\--noobjects`:: Don't include non-commit objects.\n> +`\\--ignore-size[=N]`:: Do not fuse slices of file size >= `N`.  If `N` is not \n> +given the cutoff size defaults to ~5MB.\n> +\n> +`index`::\n> +\tRegenerate the cache index.\n> +\n> +\n> +For an explanation of the API and its inner workings, see \n> +link:technical/rev-cache.txt[technical info on rev-cache]\n> diff --git a/Documentation/technical/rev-cache.txt b/Documentation/technical/rev-cache.txt\n> new file mode 100755\n> index 0000000..e95ec89\n> --- /dev/null\n> +++ b/Documentation/technical/rev-cache.txt\n> @@ -0,0 +1,336 @@\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 top (interesting) and bottom (uninteresting) commits.  Each slice \n> +contains, per commit:\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 in that commit, relative to slice (ie. only for non-start \n> +  commits).\n> +\n> +Storage data structures are not exported, in part to keep git's global scope \n> +clean, but largely because they're pretty much useless outside of rev-cache.\n> +\n> +The API\n> +-------\n> +\n> +The API for 'rev-cache' is quite simple.  You can find the function prototypes \n> +in `revision.h`.\n> +\n> +Data Structures\n> +~~~~~~~~~~~~~~~\n> +\n> +The `rev_cache_info` struct holds all the options and flags for the API.\n> +\n> +----\n> +struct rev_cache_info {\n> +        /* generation flags */\n> +        unsigned objects : 1, \n> +                legs : 1, \n> +                make_index : 1;\n> +        \n> +        /* traversal flags */\n> +        unsigned save_unique : 1, \n> +                add_to_pending : 1;\n> +        \n> +        /* fuse options */\n> +        unsigned int ignore_size;\n> +};\n> +----\n> +\n> +The fields:\n> +\n> +`objects`:: Add non-commit objects to slice.\n> +`legs`:: Ensure bottoms have no childrens.\n>   \n\n\"children\" is already plural and needs no 's'\n\n> +`make_index`:: Integrate newly-made slice into index.\n> +`save_unique`:: Load unique non-commit objects into `unique` field of each \n> +`commit` object.\n>   \n\nUnique how?  Do you mean, that they were introduced in this slice and\nnot reachable from any of the bottom/end commits?\n\n> +`add_to_pending`:: Append unique non-commit objects to the `pending` object \n> +list in the passed `rev_info` instance.\n>   \n\nThat doesn't make much sense to me either.  What does that mean?  Well,\nI'll read on.\n\n> +`ignore_size`:: If non-zero, ignore slices with size greater or equal to this.\n>   \n\nWhat will this ignoring mean?\n\n> +Functions\n> +~~~~~~~~~\n> +\n> +`init_rci`::\n> +\n> +        Initiate a `rev_cache_info` struct to default options.  \n> +\n> +`make_cache_slice`::\n> +\n> +        Create a cache based on an a `rev_info` instance or `commit_list` s of \n> +        \"tops\" and \"bottoms\" (defaulting to latter if `rev_info` pointer is \n> +        NULL), copying the cache SHA-1 into a passed pointer if non-zero.  A \n> +        `rev_cache_info` struct pointer can be passed to set options, while \n> +        passing NULL will set default options.  A last parameter can \n> +        optionally recieve the final cache hash.\n> +\n> +`make_cache_index`::\n> +\n> +        Add a slice to the cache index.  Requires a file descriptor, the cache \n> +        hash and the file size.  Note that this is normally called by \n> +        `make_cache_slice` under the `make_index` option.\n> +\n> +`get_cache_slice`::\n> +\n> +        Given a commit SHA-1 `get_cache_slice` will search the slice index and \n> +        return, if found, the cache-identifying SHA-1.\n> +\n> +`traverse_cache_slice`::\n> +\n> +        Traverse a specified cache slice based on:\n> +\n> +        * `rev_cache_info` instance (optional)\n> +        * cache SHA-1 identifier\n> +        * `rev_info` instance\n> +        * a starting commit and commit work list\n> +        * date of oldest encountered interesting commit\n> +        * current `slop` (this and above mainly used in integration with \n> +          revision walker)\n>   \n\nHmm what's a 'slop' ?\n\n> +        \n> ++\n> +The output is sent to a FILO `commit_list` \"queue\", while any bottom commits \n> +are passed back into the work list.  If the walk is not contained within the \n> +slice, commit boundaries are also inserted into \"work\".\n> +\n> +`tops_from_slices`::\n> +\n> +        Will mark all top-commits in the specified cache slices with a given \n> +        flag, and add them to the rev pending list.  Will include all if no \n> +        slices are specified.\n> +\n> +`coagulate_cache_slices`::\n> +\n> +        Generate a slice based on the passed `rev_info` instance, replacing all \n> +        encountered slices with one (larger) slice.  The `ignore_size` field in \n> +        `rci`, if non-zero, will dictate which cache slice sizes to ignore in \n> +        both traversal and replacement.\n> +\n> +`regenerate_index`::\n> +\n> +        Remake cache index.\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\nHeh, normally it's acceptable to let examples in documentation not be\ncomplete working programs :)\n\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);\n> +                object->flags |= SEEN;\n> +        }\n> +}\n> +----\n>   \n\nOk, good - perhaps needs a comment or two - not much, it's already long.\n\n> +\n> +Some Internals\n> +--------------\n> +\n> +Although you really don't need to know anything about how rev-cache actually \n> +does its magic shizz, a bit of background may go a long way if you're wading \n> +through the source.\n>   \n\n\"does its work\" will do nicely..\n\n> +\n> +File Formats\n> +~~~~~~~~~~~~\n> +\n> +A slice has a basic fixed-size header, followed by a certain number of object \n> +entries.  Commits are sorted in topo-order, and each commit entry is followed \n> +by the objects added in that commit.\n>   \n\nStarting from the top or the bottom?  And it might pay to clarify which\nobjects are included or not; ie objects reachable from \"bottom\" commits\nor not.\n\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> +----\n> +\n> +The index is somewhat similar to pack-file indexes, containing a fanout table \n> +and a list of index entries sorted by hash.\n> +\n> +----\n> +         -- +--------------------------------+\n> +header      | object #, cache #, etc.        |\n> +         -- +--------------------------------+\n> +cache       | SHA-1                          |\n> +sha1s       | ...                            |\n> +         -- +--------------------------------+\n> +fanout      | fanout[0x00]                   |\n> +table       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n> +            | fanout[0xff]                   |\n> +         -- +--------------------------------+\n> +index       | entry SHA-1                    |\n> +entries     | cache sha1 index               |\n> +            +--------------------------------+\n> +            |                                |\n> +            ...                               \n> +            +--------------------------------+\n> +----\n> +\n> +All the relavant structures are readily accessible in `rev-cache.c`\n> +\n>   \n\nOk right so which is the on-disk container format?  The index or the\nslice?  I'm a little confused..\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,\n\nIs it still fluid after coagulation?  ;-)\n\n>  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, and status in cache slice.  Here is format of an object entry, both \n> +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 merge_nr : 6;\n> +        unsigned split_nr : 7;\n> +        unsigned size_size : 3;\n> +        \n> +\tuint32_t date;\n> +\tuint16_t path;\n> +        \n> +        /* merge paths */\n> +        /* split paths */\n> +        /* size */\n> +};\n> +----\n> +\n> +An explanation of each field:\n> +\n> +`type`:: Object type\n> +`is_end`:: The commit has some parents outside the cache slice (all if slice \n> +has legs)\n> +`is_start`:: The commit has no children in cache slice\n> +`uninteresting`:: Run-time flag, used in traversal\n> +`include`:: Run-time flag, used in traversal (initialization)\n> +`flags`:: Currently unused, extra bit\n> +`sha`:: Object SHA-1 hash\n> +\n> +`merge_nr`:: The number of paths the current channel diverges into; the current \n> +path ends upon any merge.\n> +`split_nr`:: The number of paths this commit ends; used on both merging and \n> +branching.\n> +`size_size`:: Number of bytes the object size takes up.\n> +\n> +merge paths:: The path IDs (16-bit) that are to be created.\n> +split paths:: The path IDs (16-bit) that are to be ended.\n> +size:: The size 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> +(NSE)\n>   \n\ntl;dr but that's ok it's magic shizz.\n\nAnyway looking nice ... see what I can say about the next patches.\n\nsam\n"},{"id":"119900","messageId":"4A7C18F2.2000905@dawes.za.net","threadId":"20428","inReplyTo":"4A7B9ACA.1060601@vilain.net","subject":"Re: [PATCH 1/5] revision caching documentation: man page and technical discussion","fromName":"Rogan Dawes","fromEmail":"discard@dawes.za.net","sentAt":"2009-08-07T12:07:14Z","receivedAt":"2009-08-07T12:07:14Z","isPatch":true,"sender":{"key":"discard@dawes.za.net","avatar":null},"body":"Sam Vilain wrote:\n\n>> +`fuse`::\n>> +\tCoagulate several cache slices into a single large slice.\n>>   \n> \n> Coagulate?  You mean, the revision caches will stop being liquid and go\n> gluggy, like a pool of blood clotting?\n> \n> How about \"combine\" :-) - and the option might be better called\n> something simple like that, too.\n\nI think the word he had in mind was \"coalesce\".\n\nRogan\n"},{"id":"119901","messageId":"alpine.DEB.1.00.0908071419590.8306@pacific.mpi-cbg.de","threadId":"20428","inReplyTo":"4A7C18F2.2000905@dawes.za.net","subject":"Re: [PATCH 1/5] revision caching documentation: man page and technical discussion","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2009-08-07T12:20:40Z","receivedAt":"2009-08-07T12:20:40Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Fri, 7 Aug 2009, Rogan Dawes wrote:\n\n> Sam Vilain wrote:\n> \n> >> +`fuse`::\n> >> +\tCoagulate several cache slices into a single large slice.\n> >>   \n> > \n> > Coagulate?  You mean, the revision caches will stop being liquid and go\n> > gluggy, like a pool of blood clotting?\n> > \n> > How about \"combine\" :-) - and the option might be better called\n> > something simple like that, too.\n> \n> I think the word he had in mind was \"coalesce\".\n\nAs Git users typically have a quite good idea what a \"merge\" is, I'd \nprefer that word anyway.\n\nCiao,\nDscho\n"},{"id":"119939","messageId":"1249682294.6221.2.camel@maia.lan","threadId":"20428","inReplyTo":"alpine.DEB.1.00.0908071419590.8306@pacific.mpi-cbg.de","subject":"Re: [PATCH 1/5] revision caching documentation: man page and technical discussion","fromName":"Sam Vilain","fromEmail":"sam@vilain.net","sentAt":"2009-08-07T21:58:14Z","receivedAt":"2009-08-07T21:58:14Z","isPatch":true,"sender":{"key":"sam@vilain.net","avatar":"https://gravatar.com/avatar/8fc840ca854dbf6f7065b4335e3b934951c1dca3b11db688e95e471901f8f4a8?d=mp&s=160"},"body":"On Fri, 2009-08-07 at 14:20 +0200, Johannes Schindelin wrote:\n> > I think the word he had in mind was \"coalesce\".\n> As Git users typically have a quite good idea what a \"merge\" is, I'd \n> prefer that word anyway.\n\nI don't like that so much, given that \"merge\" has quite a specific\nmeaning.  But not really that fussed.  In this case it's more like a\n'gc' or 'repack'; an internal reshuffle of an index to make it a single\none and not many.\n\nSam\n"}]}