{"thread":{"id":"20633","subject":"[PATCH 5/6 (v4)] full integration of rev-cache into git, completed test suite","startedAt":"2009-08-17T12:31:32Z","lastAt":"2009-10-19T20:30:26Z","messageCount":10,"participants":["Nick Edelen","Sam Vilain","Chris Johnsen","Johannes Sixt"],"isPatch":true,"patchVersion":4,"patchTotal":6},"messages":[{"id":"120877","messageId":"op.uys3quhbtdk399@sirnot.private","threadId":"20633","inReplyTo":null,"subject":"[PATCH 5/6 (v4)] full integration of rev-cache into git, completed test suite","fromName":"Nick Edelen","fromEmail":"sirnot@gmail.com","sentAt":"2009-08-17T12:31:32Z","receivedAt":"2009-08-17T12:31:32Z","isPatch":true,"sender":{"key":"sirnot@gmail.com","avatar":null},"body":"This patch provides a working integration of rev-cache into the revision \nwalker, along with some touch-ups:\n - integration into revision walker and list-objects\n - tweak of object generation to take advantage of the 'unique' field\n - more fluid handling of damaged cache slices\n - numerous tests for both features from the previous patch, and the \nintegration's integrity\n\n'Integration' is rather broad -- a more detailed description follows for each \naspect:\n - rev-cache\nthe traversal mechanism is updated to handle many of the non-prune options \nrev-list does (date limiting, slop-handling, etc.), and is adjusted to allow \nfor non-fatal cache-traversal failures.\n\n - revision walker\nboth limited and unlimited traversal attempt to use the cache when possible, \nsmoothly falling back if it's not.\n\n - list-objects\nobject listing does not recurse into cached trees, and has been adjusted to \nguarantee commit-tag-tree-blob ordering.\n\nSigned-off-by: Nick Edelen <sirnot@gmail.com>\n\n---\n builtin-rev-cache.c       |   40 ++++++++\n list-objects.c            |   49 ++++++++--\n rev-cache.c               |  228 +++++++++++++++++++++++++++++++++++++++-----\n revision.c                |   88 ++++++++++++++---\n t/t6015-rev-cache-list.sh |  151 ++++++++++++++++++++++++++++-\n 5 files changed, 501 insertions(+), 55 deletions(-)\n\ndiff --git a/builtin-rev-cache.c b/builtin-rev-cache.c\nindex 7ca39c4..a3489ce 100644\n--- a/builtin-rev-cache.c\n+++ b/builtin-rev-cache.c\n@@ -4,6 +4,7 @@\n #include \"diff.h\"\n #include \"revision.h\"\n #include \"rev-cache.h\"\n+#include \"list-objects.h\"\n \n unsigned long default_ignore_size = 50 * 1024 * 1024; /* 50mb */\n \n@@ -78,6 +79,43 @@ static int handle_add(int argc, const char *argv[]) /* args beyond this command\n \treturn 0;\n }\n \n+static void show_commit(struct commit *commit, void *data)\n+{\n+\tprintf(\"%s\\n\", sha1_to_hex(commit->object.sha1));\n+}\n+\n+static void show_object(struct object *obj, const struct name_path *path, const char *last)\n+{\n+\tprintf(\"%s\\n\", sha1_to_hex(obj->sha1));\n+}\n+\n+static int test_rev_list(int argc, const char *argv[])\n+{\n+\tstruct rev_info revs;\n+\tunsigned int flags = 0;\n+\tint i;\n+\n+\tinit_revisions(&revs, 0);\n+\n+\tfor (i = 0; i < argc; i++) {\n+\t\tif (!strcmp(argv[i], \"--not\"))\n+\t\t\tflags ^= UNINTERESTING;\n+\t\telse if (!strcmp(argv[i], \"--objects\"))\n+\t\t\trevs.tree_objects = revs.blob_objects = 1;\n+\t\telse\n+\t\t\thandle_revision_arg(argv[i], &revs, flags, 1);\n+\t}\n+\n+\tsetup_revisions(0, 0, &revs, 0);\n+\trevs.topo_order = 1;\n+\trevs.lifo = 1;\n+\tprepare_revision_walk(&revs);\n+\n+\ttraverse_commit_list(&revs, show_commit, show_object, 0);\n+\n+\treturn 0;\n+}\n+\n static int handle_walk(int argc, const char *argv[])\n {\n \tstruct commit *commit;\n@@ -270,6 +308,8 @@ int cmd_rev_cache(int argc, const char *argv[], const char *prefix)\n \t\tr = handle_walk(argc, argv);\n \telse if (!strcmp(arg, \"index\"))\n \t\tr = handle_index(argc, argv);\n+\telse if (!strcmp(arg, \"test\"))\n+\t\tr = test_rev_list(argc, argv);\n \telse if (!strcmp(arg, \"alt\"))\n \t\tr = handle_alt(argc, argv);\n \telse\ndiff --git a/list-objects.c b/list-objects.c\nindex 8953548..821a290 100644\n--- a/list-objects.c\n+++ b/list-objects.c\n@@ -74,22 +74,33 @@ static void process_tree(struct rev_info *revs,\n \t\tdie(\"bad tree object\");\n \tif (obj->flags & (UNINTERESTING | SEEN))\n \t\treturn;\n-\tif (parse_tree(tree) < 0)\n-\t\tdie(\"bad tree object %s\", sha1_to_hex(obj->sha1));\n+\n \tobj->flags |= SEEN;\n \tshow(obj, path, name);\n+\tif (obj->flags & FACE_VALUE)\n+\t\treturn;\n+\n+\t/* traverse_commit_list is only used for enumeration purposes,\n+\t * ie. nothing relies on trees being parsed in this routine */\n+\tif (parse_tree(tree) < 0)\n+\t\tdie(\"bad tree object %s\", sha1_to_hex(obj->sha1));\n+\n \tme.up = path;\n \tme.elem = name;\n \tme.elem_len = strlen(name);\n-\n \tinit_tree_desc(&desc, tree->buffer, tree->size);\n \n \twhile (tree_entry(&desc, &entry)) {\n-\t\tif (S_ISDIR(entry.mode))\n+\t\tif (S_ISDIR(entry.mode)) {\n+\t\t\tstruct tree *subtree = lookup_tree(entry.sha1);\n+\t\t\tif (!subtree)\n+\t\t\t\tcontinue;\n+\n+\t\t\tsubtree->object.flags &= ~FACE_VALUE;\n \t\t\tprocess_tree(revs,\n-\t\t\t\t     lookup_tree(entry.sha1),\n+\t\t\t\t     subtree,\n \t\t\t\t     show, &me, entry.path);\n-\t\telse if (S_ISGITLINK(entry.mode))\n+\t\t} else if (S_ISGITLINK(entry.mode))\n \t\t\tprocess_gitlink(revs, entry.sha1,\n \t\t\t\t\tshow, &me, entry.path);\n \t\telse\n@@ -136,6 +147,7 @@ void mark_edges_uninteresting(struct commit_list *list,\n \n static void add_pending_tree(struct rev_info *revs, struct tree *tree)\n {\n+\ttree->object.flags &= ~FACE_VALUE;\n \tadd_pending_object(revs, &tree->object, \"\");\n }\n \n@@ -146,17 +158,27 @@ void traverse_commit_list(struct rev_info *revs,\n {\n \tint i;\n \tstruct commit *commit;\n+\tenum object_type what = OBJ_TAG;\n+\tchar face_value = 0;\n \n \twhile ((commit = get_revision(revs)) != NULL) {\n-\t\tadd_pending_tree(revs, commit->tree);\n+\t\tif (!(commit->object.flags & FACE_VALUE))\n+\t\t\tadd_pending_tree(revs, commit->tree);\n+\t\telse\n+\t\t\tface_value = 1;\n \t\tshow_commit(commit, data);\n \t}\n+\n+loop_objects:\n \tfor (i = 0; i < revs->pending.nr; i++) {\n \t\tstruct object_array_entry *pending = revs->pending.objects + i;\n \t\tstruct object *obj = pending->item;\n \t\tconst char *name = pending->name;\n \t\tif (obj->flags & (UNINTERESTING | SEEN))\n \t\t\tcontinue;\n+\t\tif (obj->type != what && face_value)\n+\t\t\tcontinue;\n+\n \t\tif (obj->type == OBJ_TAG) {\n \t\t\tobj->flags |= SEEN;\n \t\t\tshow_object(obj, NULL, name);\n@@ -175,6 +197,19 @@ void traverse_commit_list(struct rev_info *revs,\n \t\tdie(\"unknown pending object %s (%s)\",\n \t\t    sha1_to_hex(obj->sha1), name);\n \t}\n+\tif (face_value) {\n+\t\tswitch (what) {\n+\t\tcase OBJ_TAG :\n+\t\t\twhat = OBJ_TREE;\n+\t\t\tgoto loop_objects;\n+\t\tcase OBJ_TREE :\n+\t\t\twhat = OBJ_BLOB;\n+\t\t\tgoto loop_objects;\n+\t\tdefault :\n+\t\t\tbreak;\n+\t\t}\n+\t}\n+\n \tif (revs->pending.nr) {\n \t\tfree(revs->pending.objects);\n \t\trevs->pending.nr = 0;\ndiff --git a/rev-cache.c b/rev-cache.c\nindex 8eac1f0..7eefd3c 100644\n--- a/rev-cache.c\n+++ b/rev-cache.c\n@@ -11,6 +11,12 @@\n #include \"run-command.h\"\n #include \"string-list.h\"\n \n+\n+struct bad_slice {\n+\tunsigned char sha1[20];\n+\tstruct bad_slice *next;\n+};\n+\n struct cache_slice_pointer {\n \tchar signature[8]; /* REVCOPTR */\n \tchar version;\n@@ -23,8 +29,9 @@ static uint32_t fanout[0xff + 2];\n static unsigned char *idx_map;\n static int idx_size;\n static struct rc_index_header idx_head;\n+static char no_idx, add_to_pending;\n+static struct bad_slice *bad_slices;\n static unsigned char *idx_caches;\n-static char no_idx;\n \n static struct strbuf *acc_buffer;\n \n@@ -119,6 +126,30 @@ struct rc_object_entry_ondisk *to_disked_rc_object_entry(struct rc_object_entry\n \treturn dst;\n }\n \n+static void mark_bad_slice(unsigned char *sha1)\n+{\n+\tstruct bad_slice *bad;\n+\n+\tbad = xcalloc(sizeof(struct bad_slice), 1);\n+\thashcpy(bad->sha1, sha1);\n+\n+\tbad->next = bad_slices;\n+\tbad_slices = bad;\n+}\n+\n+static int is_bad_slice(unsigned char *sha1)\n+{\n+\tstruct bad_slice *bad = bad_slices;\n+\n+\twhile (bad) {\n+\t\tif (!hashcmp(bad->sha1, sha1))\n+\t\t\treturn 1;\n+\t\tbad = bad->next;\n+\t}\n+\n+\treturn 0;\n+}\n+\n static int get_index_head(unsigned char *map, int len, struct rc_index_header *head, uint32_t *fanout, unsigned char **caches)\n {\n \tstruct rc_index_header whead;\n@@ -244,6 +275,7 @@ static struct rc_index_entry *search_index(unsigned char *sha1)\n unsigned char *get_cache_slice(struct commit *commit)\n {\n \tstruct rc_index_entry *ie;\n+\tunsigned char *sha1;\n \n \tif (!idx_map) {\n \t\tif (no_idx)\n@@ -255,8 +287,13 @@ unsigned char *get_cache_slice(struct commit *commit)\n \t\treturn 0;\n \n \tie = search_index(commit->object.sha1);\n-\tif (ie && ie->cache_index < idx_head.cache_nr)\n-\t\treturn idx_caches + ie->cache_index * 20;\n+\tif (ie && ie->cache_index < idx_head.cache_nr) {\n+\t\tsha1 = idx_caches + ie->cache_index * 20;\n+\n+\t\tif (is_bad_slice(sha1))\n+\t\t\treturn 0;\n+\t\treturn sha1;\n+\t}\n \n \treturn 0;\n }\n@@ -266,6 +303,20 @@ unsigned char *get_cache_slice(struct commit *commit)\n \n static unsigned long decode_size(unsigned char *str, int len);\n \n+/* on failure */\n+static void restore_commit(struct commit *commit)\n+{\n+\tcommit->object.flags &= ~(ADDED | SEEN | FACE_VALUE);\n+\n+\tif (!commit->object.parsed) {\n+\t\twhile (pop_commit(&commit->parents))\n+\t\t\t;\n+\n+\t\tparse_commit(commit);\n+\t}\n+\n+}\n+\n static void handle_noncommit(struct rev_info *revs, struct commit *commit, unsigned char *ptr, struct rc_object_entry *entry)\n {\n \tstruct blob *blob;\n@@ -305,23 +356,27 @@ static void handle_noncommit(struct rev_info *revs, struct commit *commit, unsig\n \t}\n \n \tobj->flags |= FACE_VALUE;\n-\tadd_pending_object(revs, obj, \"\");\n+\tif (add_to_pending)\n+\t\tadd_pending_object(revs, obj, \"\");\n }\n \n-static int setup_traversal(struct rc_slice_header *head, unsigned char *map, struct commit *commit, struct commit_list **work)\n+static int setup_traversal(struct rc_slice_header *head, unsigned char *map, struct commit *commit, struct commit_list **work,\n+\tstruct commit_list **unwork, int *ipath_nr, int *upath_nr, char *ioutside)\n {\n \tstruct rc_index_entry *iep;\n \tstruct rc_object_entry *oep;\n \tstruct commit_list *prev, *wp, **wpp;\n \tint retval;\n \n-\tiep = search_index(commit->object.sha1), 0;\n+\tiep = search_index(commit->object.sha1);\n \toep = RC_OBTAIN_OBJECT_ENTRY(map + iep->pos);\n+\tif (commit->object.flags & UNINTERESTING) {\n+\t\t++*upath_nr;\n+\t\toep->uninteresting = 1;\n+\t} else\n+\t\t++*ipath_nr;\n \n-\t/* the .uniniteresting bit isn't strictly necessary, as we check the object during traversal as well,\n-\t * but we might as well initialize it while we're at it */\n \toep->include = 1;\n-\toep->uninteresting = !!(commit->object.flags & UNINTERESTING);\n \tto_disked_rc_object_entry(oep, (struct rc_object_entry_ondisk *)(map + iep->pos));\n \tretval = iep->pos;\n \n@@ -336,6 +391,10 @@ static int setup_traversal(struct rc_slice_header *head, unsigned char *map, str\n \t\t/* is this in our cache slice? */\n \t\tiep = search_index(obj->sha1);\n \t\tif (!iep || hashcmp(idx_caches + iep->cache_index * 20, head->sha1)) {\n+\t\t\t/* there are interesing objects outside the slice */\n+\t\t\tif (!(obj->flags & UNINTERESTING))\n+\t\t\t\t*ioutside = 1;\n+\n \t\t\tprev = wp;\n \t\t\twp = wp->next;\n \t\t\twpp = &wp;\n@@ -352,11 +411,20 @@ static int setup_traversal(struct rc_slice_header *head, unsigned char *map, str\n \t\toep->uninteresting = !!(obj->flags & UNINTERESTING);\n \t\tto_disked_rc_object_entry(oep, (struct rc_object_entry_ondisk *)(map + iep->pos));\n \n+\t\t/* count even if not in slice so we can stop enumerating if possible */\n+\t\tif (obj->flags & UNINTERESTING)\n+\t\t\t++*upath_nr;\n+\t\telse\n+\t\t\t++*ipath_nr;\n+\n \t\t/* remove from work list */\n \t\tco = pop_commit(wpp);\n \t\twp = *wpp;\n \t\tif (prev)\n \t\t\tprev->next = wp;\n+\n+\t\t/* ...and store in temp list so we can restore work on failure */\n+\t\tcommit_list_insert(co, unwork);\n \t}\n \n \treturn retval;\n@@ -373,13 +441,18 @@ static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *m\n \tunsigned long *date_so_far, int *slop_so_far,\n \tstruct commit_list ***queue, struct commit_list **work)\n {\n-\tstruct commit_list *insert_cache = 0;\n+\tstruct commit_list *insert_cache = 0, *myq = 0, **myqp = &myq, *mywork = 0, **myworkp = &mywork, *unwork = 0;\n \tstruct commit **last_objects, *co;\n-\tint i, total_path_nr = head->path_nr, retval = -1;\n-\tchar consume_children = 0;\n+\tunsigned long date = date_so_far ? *date_so_far : ~0ul;\n+\tint i, ipath_nr = 0, upath_nr = 0, orig_obj_nr = 0,\n+\t\ttotal_path_nr = head->path_nr, retval = -1, slop = slop_so_far ? *slop_so_far : SLOP;\n+\tchar consume_children = 0, ioutside = 0;\n \tunsigned char *paths;\n \n-\ti = setup_traversal(head, map, commit, work);\n+\t/* take note in case we need to regress */\n+\torig_obj_nr = revs->pending.nr;\n+\n+\ti = setup_traversal(head, map, commit, work, &unwork, &ipath_nr, &upath_nr, &ioutside);\n \tif (i < 0)\n \t\treturn -1;\n \n@@ -427,6 +500,7 @@ static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *m\n \n \t\tif ((paths[path] & IPATH) && (paths[path] & UPATH)) {\n \t\t\tpaths[path] = UPATH;\n+\t\t\tipath_nr--;\n \n \t\t\t/* mark edge */\n \t\t\tif (last_objects[path]) {\n@@ -437,6 +511,7 @@ static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *m\n \t\t\t\tlast_objects[path]->object.flags &= ~FACE_VALUE;\n \t\t\t\tlast_objects[path] = 0;\n \t\t\t}\n+\t\t\tobj->flags |= BOUNDARY;\n \t\t}\n \n \t\t/* now we gotta re-assess the whole interesting thing... */\n@@ -460,8 +535,10 @@ static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *m\n \t\t\t\t\t\tlast_objects[p]->object.flags &= ~FACE_VALUE;\n \t\t\t\t\t\tlast_objects[p] = 0;\n \t\t\t\t\t}\n-\t\t\t\t} else if (last_objects[p] && !last_objects[p]->object.parsed)\n+\t\t\t\t\tobj->flags |= BOUNDARY;\n+\t\t\t\t} else if (last_objects[p] && !last_objects[p]->object.parsed) {\n \t\t\t\t\tcommit_list_insert(co, &last_objects[p]->parents);\n+\t\t\t\t}\n \n \t\t\t\t/* can't close a merge path until all are parents have been encountered */\n \t\t\t\tif (GET_COUNT(paths[p])) {\n@@ -471,14 +548,33 @@ static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *m\n \t\t\t\t\t\tcontinue;\n \t\t\t\t}\n \n+\t\t\t\tif (paths[p] & IPATH)\n+\t\t\t\t\tipath_nr--;\n+\t\t\t\telse\n+\t\t\t\t\tupath_nr--;\n+\n \t\t\t\tpaths[p] = 0;\n \t\t\t\tlast_objects[p] = 0;\n \t\t\t}\n \t\t}\n \n \t\t/* make topo relations */\n-\t\tif (last_objects[path] && !last_objects[path]->object.parsed)\n+\t\tif (last_objects[path] && !last_objects[path]->object.parsed) {\n \t\t\tcommit_list_insert(co, &last_objects[path]->parents);\n+\t\t}\n+\n+\t\t/* we've been here already */\n+\t\tif (obj->flags & ADDED) {\n+\t\t\tif (entry->uninteresting && !(obj->flags & UNINTERESTING)) {\n+\t\t\t\tobj->flags |= UNINTERESTING;\n+\t\t\t\tmark_parents_uninteresting(co);\n+\t\t\t\tupath_nr--;\n+\t\t\t} else if (!entry->uninteresting)\n+\t\t\t\tipath_nr--;\n+\n+\t\t\tpaths[path] = 0;\n+\t\t\tcontinue;\n+\t\t}\n \n \t\t/* initialize commit */\n \t\tif (!entry->is_end) {\n@@ -491,24 +587,51 @@ static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *m\n \n \t\tif (entry->uninteresting)\n \t\t\tobj->flags |= UNINTERESTING;\n+\t\telse if (co->date < date)\n+\t\t\tdate = co->date;\n \n \t\t/* we need to know what the edges are */\n \t\tlast_objects[path] = co;\n \n \t\t/* add to list */\n-\t\tif (!(obj->flags & UNINTERESTING) || revs->show_all) {\n-\t\t\tif (entry->is_end)\n-\t\t\t\tinsert_by_date_cached(co, work, insert_cache, &insert_cache);\n-\t\t\telse\n-\t\t\t\t*queue = &commit_list_insert(co, *queue)->next;\n+\t\tif (slop && !(revs->min_age != -1 && co->date > revs->min_age)) {\n+\n+\t\t\tif (!(obj->flags & UNINTERESTING) || revs->show_all) {\n+\t\t\t\tif (entry->is_end)\n+\t\t\t\t\tmyworkp = &commit_list_insert(co, myworkp)->next;\n+\t\t\t\telse\n+\t\t\t\t\tmyqp = &commit_list_insert(co, myqp)->next;\n+\n+\t\t\t\t/* add children to list as well */\n+\t\t\t\tif (obj->flags & UNINTERESTING)\n+\t\t\t\t\tconsume_children = 0;\n+\t\t\t\telse\n+\t\t\t\t\tconsume_children = 1;\n+\t\t\t}\n \n-\t\t\t/* add children to list as well */\n-\t\t\tif (obj->flags & UNINTERESTING)\n-\t\t\t\tconsume_children = 0;\n-\t\t\telse\n-\t\t\t\tconsume_children = 1;\n \t\t}\n \n+\t\t/* should we continue? */\n+\t\tif (!slop) {\n+\t\t\tif (!upath_nr) {\n+\t\t\t\tbreak;\n+\t\t\t} else if (ioutside || revs->show_all) {\n+\t\t\t\t/* pass it back to rev-list\n+\t\t\t\t * we purposely ignore everything outside this cache, so we don't needlessly traverse the whole\n+\t\t\t\t * thing on uninteresting, but that does mean that we may need to bounce back\n+\t\t\t\t * and forth a few times with rev-list */\n+\t\t\t\tmyworkp = &commit_list_insert(co, myworkp)->next;\n+\n+\t\t\t\tpaths[path] = 0;\n+\t\t\t\tupath_nr--;\n+\t\t\t} else {\n+\t\t\t\tbreak;\n+\t\t\t}\n+\t\t} else if (!ipath_nr && co->date <= date)\n+\t\t\tslop--;\n+\t\telse\n+\t\t\tslop = SLOP;\n+\n \t\t/* open parents */\n \t\tif (entry->merge_nr) {\n \t\t\tint j, off = index + sizeof(struct rc_object_entry_ondisk);\n@@ -523,6 +646,11 @@ static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *m\n \t\t\t\tif (paths[p] & flag)\n \t\t\t\t\tcontinue;\n \n+\t\t\t\tif (flag == IPATH)\n+\t\t\t\t\tipath_nr++;\n+\t\t\t\telse\n+\t\t\t\t\tupath_nr++;\n+\n \t\t\t\tpaths[p] |= flag;\n \t\t\t}\n \n@@ -532,12 +660,55 @@ static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *m\n \n \t}\n \n+\tif (date_so_far)\n+\t\t*date_so_far = date;\n+\tif (slop_so_far)\n+\t\t*slop_so_far = slop;\n \tretval = 0;\n \n+\t/* success: attach to given lists */\n+\tif (myqp != &myq) {\n+\t\t**queue = myq;\n+\t\t*queue = myqp;\n+\t}\n+\n+\twhile ((co = pop_commit(&mywork)) != 0) {\n+\t\tinsert_by_date_cached(co, work, insert_cache, &insert_cache);\n+\t}\n+\n+\t/* free backup */\n+\twhile (pop_commit(&unwork))\n+\t\t;\n+\n end:\n \tfree(paths);\n \tfree(last_objects);\n \n+\t/* failure: restore work to previous condition\n+\t * (cache corruption should *not* be fatal) */\n+\tif (retval) {\n+\t\twhile ((co = pop_commit(&unwork)) != 0) {\n+\t\t\trestore_commit(co);\n+\t\t\tco->object.flags |= SEEN;\n+\t\t\tinsert_by_date(co, work);\n+\t\t}\n+\n+\t\t/* free lists */\n+\t\twhile ((co = pop_commit(&myq)) != 0)\n+\t\t\trestore_commit(co);\n+\n+\t\twhile ((co = pop_commit(&mywork)) != 0)\n+\t\t\trestore_commit(co);\n+\n+\t\t/* truncate object array */\n+\t\tfor (i = orig_obj_nr; i < revs->pending.nr; i++) {\n+\t\t\tstruct object *obj = revs->pending.objects[i].item;\n+\n+\t\t\tobj->flags &= ~FACE_VALUE;\n+\t\t}\n+\t\trevs->pending.nr = orig_obj_nr;\n+\t}\n+\n \treturn retval;\n }\n \n@@ -628,6 +799,7 @@ int traverse_cache_slice(struct rev_info *revs,\n \n \t/* load options */\n \trci = &revs->rev_cache_info;\n+\tadd_to_pending = rci->add_to_pending;\n \n \tmemset(&head, 0, sizeof(struct rc_slice_header));\n \n@@ -651,6 +823,10 @@ end:\n \tif (fd != -1)\n \t\tclose(fd);\n \n+\t/* remember this! */\n+\tif (retval)\n+\t\tmark_bad_slice(cache_sha1);\n+\n \treturn retval;\n }\n \ndiff --git a/revision.c b/revision.c\nindex 485bf72..4640536 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -12,6 +12,7 @@\n #include \"patch-ids.h\"\n #include \"decorate.h\"\n #include \"log-tree.h\"\n+#include \"rev-cache.h\"\n \n volatile show_early_output_fn_t show_early_output;\n \n@@ -638,6 +639,8 @@ static int limit_list(struct rev_info *revs)\n \tstruct commit_list *list = revs->commits;\n \tstruct commit_list *newlist = NULL;\n \tstruct commit_list **p = &newlist;\n+\tunsigned char *cache_sha1;\n+\tchar used_cache;\n \n \twhile (list) {\n \t\tstruct commit_list *entry = list;\n@@ -650,24 +653,39 @@ static int limit_list(struct rev_info *revs)\n \n \t\tif (revs->max_age != -1 && (commit->date < revs->max_age))\n \t\t\tobj->flags |= UNINTERESTING;\n-\t\tif (add_parents_to_list(revs, commit, &list, NULL) < 0)\n-\t\t\treturn -1;\n-\t\tif (obj->flags & UNINTERESTING) {\n-\t\t\tmark_parents_uninteresting(commit);\n-\t\t\tif (revs->show_all)\n-\t\t\t\tp = &commit_list_insert(commit, p)->next;\n-\t\t\tslop = still_interesting(list, date, slop);\n-\t\t\tif (slop)\n+\n+\t\t/* rev-cache to the rescue!!! */\n+\t\tused_cache = 0;\n+\t\tif (!revs->dont_cache_me && !(obj->flags & ADDED)) {\n+\t\t\tcache_sha1 = get_cache_slice(commit);\n+\t\t\tif (cache_sha1) {\n+\t\t\t\tif (traverse_cache_slice(revs, cache_sha1, commit, &date, &slop, &p, &list) < 0)\n+\t\t\t\t\tused_cache = 0;\n+\t\t\t\telse\n+\t\t\t\t\tused_cache = 1;\n+\t\t\t}\n+\t\t}\n+\n+\t\tif (!used_cache) {\n+\t\t\tif (add_parents_to_list(revs, commit, &list, NULL) < 0)\n+\t\t\t\treturn -1;\n+\t\t\tif (obj->flags & UNINTERESTING) {\n+\t\t\t\tmark_parents_uninteresting(commit); /* ME: why? */\n+\t\t\t\tif (revs->show_all)\n+\t\t\t\t\tp = &commit_list_insert(commit, p)->next;\n+\t\t\t\tslop = still_interesting(list, date, slop);\n+\t\t\t\tif (slop > 0)\n+\t\t\t\t\tcontinue;\n+\t\t\t\t/* If showing all, add the whole pending list to the end */\n+\t\t\t\tif (revs->show_all)\n+\t\t\t\t\t*p = list;\n+\t\t\t\tbreak;\n+\t\t\t}\n+\t\t\tif (revs->min_age != -1 && (commit->date > revs->min_age))\n \t\t\t\tcontinue;\n-\t\t\t/* If showing all, add the whole pending list to the end */\n-\t\t\tif (revs->show_all)\n-\t\t\t\t*p = list;\n-\t\t\tbreak;\n+\t\t\tdate = commit->date;\n+\t\t\tp = &commit_list_insert(commit, p)->next;\n \t\t}\n-\t\tif (revs->min_age != -1 && (commit->date > revs->min_age))\n-\t\t\tcontinue;\n-\t\tdate = commit->date;\n-\t\tp = &commit_list_insert(commit, p)->next;\n \n \t\tshow = show_early_output;\n \t\tif (!show)\n@@ -813,6 +831,8 @@ void init_revisions(struct rev_info *revs, const char *prefix)\n \t\trevs->diffopt.prefix = prefix;\n \t\trevs->diffopt.prefix_length = strlen(prefix);\n \t}\n+\n+\tinit_rev_cache_info(&revs->rev_cache_info);\n }\n \n static void add_pending_commit_list(struct rev_info *revs,\n@@ -1372,6 +1392,11 @@ int setup_revisions(int argc, const char **argv, struct rev_info *revs, const ch\n \tif (revs->reflog_info && revs->graph)\n \t\tdie(\"cannot combine --walk-reflogs with --graph\");\n \n+\t/* limits on caching\n+\t * todo: implement this functionality */\n+\tif (revs->prune || revs->diff)\n+\t\trevs->dont_cache_me = 1;\n+\n \treturn left;\n }\n \n@@ -1654,6 +1679,8 @@ static int commit_match(struct commit *commit, struct rev_info *opt)\n {\n \tif (!opt->grep_filter.pattern_list)\n \t\treturn 1;\n+\tif (!commit->object.parsed)\n+\t\tparse_commit(commit);\n \treturn grep_buffer(&opt->grep_filter,\n \t\t\t   NULL, /* we say nothing, not even filename */\n \t\t\t   commit->buffer, strlen(commit->buffer));\n@@ -1706,6 +1733,7 @@ static struct commit *get_revision_1(struct rev_info *revs)\n \tdo {\n \t\tstruct commit_list *entry = revs->commits;\n \t\tstruct commit *commit = entry->item;\n+\t\tstruct object *obj = &commit->object;\n \n \t\trevs->commits = entry->next;\n \t\tfree(entry);\n@@ -1722,11 +1750,39 @@ static struct commit *get_revision_1(struct rev_info *revs)\n \t\t\tif (revs->max_age != -1 &&\n \t\t\t    (commit->date < revs->max_age))\n \t\t\t\tcontinue;\n+\n+\t\t\tif (!revs->dont_cache_me) {\n+\t\t\t\tstruct commit_list *queue = 0, **queuep = &queue;\n+\t\t\t\tunsigned char *cache_sha1;\n+\n+\t\t\t\tif (obj->flags & ADDED)\n+\t\t\t\t\tgoto skip_parenting;\n+\n+\t\t\t\tcache_sha1 = get_cache_slice(commit);\n+\t\t\t\tif (cache_sha1) {\n+\t\t\t\t\tif (!traverse_cache_slice(revs, cache_sha1, commit, 0, 0, &queuep, &revs->commits)) {\n+\t\t\t\t\t\tstruct commit_list *work = revs->commits;\n+\n+\t\t\t\t\t\t/* attach queue to end of ->commits */\n+\t\t\t\t\t\twhile (work && work->next)\n+\t\t\t\t\t\t\twork = work->next;\n+\n+\t\t\t\t\t\tif (work)\n+\t\t\t\t\t\t\twork->next = queue;\n+\t\t\t\t\t\telse\n+\t\t\t\t\t\t\trevs->commits = queue;\n+\n+\t\t\t\t\t\tgoto skip_parenting;\n+\t\t\t\t\t}\n+\t\t\t\t}\n+\t\t\t}\n+\n \t\t\tif (add_parents_to_list(revs, commit, &revs->commits, NULL) < 0)\n \t\t\t\tdie(\"Failed to traverse parents of commit %s\",\n \t\t\t\t    sha1_to_hex(commit->object.sha1));\n \t\t}\n \n+skip_parenting:\n \t\tswitch (simplify_commit(revs, commit)) {\n \t\tcase commit_ignore:\n \t\t\tcontinue;\ndiff --git a/t/t6015-rev-cache-list.sh b/t/t6015-rev-cache-list.sh\nindex afa0303..fa6df21 100755\n--- a/t/t6015-rev-cache-list.sh\n+++ b/t/t6015-rev-cache-list.sh\n@@ -38,6 +38,7 @@ test_expect_success 'init repo' '\n \tgit add . && \n \tgit commit -m \"omg\" && \n \n+\tsleep 2 && \n \tgit branch b4 && \n \tgit checkout b4 && \n \techo shazam >file8 && \n@@ -46,7 +47,7 @@ test_expect_success 'init repo' '\n \tgit merge -m \"merge b2\" b2 && \n \n \techo bam >smoke/pipe && \n-\tgit add .\n+\tgit add . && \n \tgit commit -m \"bam\" && \n \n \tgit checkout master && \n@@ -71,18 +72,26 @@ test_expect_success 'init repo' '\n \tgit add . && \n \tgit commit -m \"lol\" && \n \n+\tsleep 2 && \n \tgit checkout master && \n \tgit merge -m \"triple merge\" b1 b11 && \n \tgit rm -r d1 &&  \n+\tsleep 2 && \n \tgit commit -a -m \"oh noes\"\n '\n \n-git-rev-list HEAD --not HEAD~3 >proper_commit_list_limited\n-git-rev-list HEAD >proper_commit_list\n-git-rev-list HEAD --objects >proper_object_list\n+max_date=`git-rev-list --timestamp HEAD~1 --max-count=1 | grep -e \"^[0-9]*\" -o`\n+min_date=`git-rev-list --timestamp b4 --max-count=1 | grep -e \"^[0-9]*\" -o`\n+\n+git-rev-list --topo-order HEAD --not HEAD~3 >proper_commit_list_limited\n+git-rev-list --topo-order HEAD --not HEAD~2 >proper_commit_list_limited2\n+git-rev-list --topo-order HEAD >proper_commit_list\n+git-rev-list --objects HEAD >proper_object_list\n+git-rev-list HEAD --max-age=$min_date --min-age=$max_date >proper_list_date_limited\n+\n+cache_sha1=`git-rev-cache add HEAD 2>output.err`\n \n test_expect_success 'make cache slice' '\n-\tgit-rev-cache add HEAD 2>output.err && \n \tgrep \"final return value: 0\" output.err\n '\n \n@@ -102,11 +111,141 @@ test_expect_success 'test rev-caches walker directly (unlimited)' '\n \ttest_cmp_sorted list proper_commit_list\n '\n \n+test_expect_success 'test rev-list traversal (limited)' '\n+\tgit-rev-list HEAD --not HEAD~3 >list && \n+\ttest_cmp list proper_commit_list_limited\n+'\n+\n+test_expect_success 'test rev-list traversal (unlimited)' '\n+\tgit-rev-list HEAD >list && \n+\ttest_cmp list proper_commit_list\n+'\n+\n #do the same for objects\n test_expect_success 'test rev-caches walker with objects' '\n \tgit-rev-cache walk --objects HEAD >list && \n \ttest_cmp_sorted list proper_object_list\n '\n \n-test_done\n+test_expect_success 'test rev-list with objects (topo order)' '\n+\tgit-rev-list --topo-order --objects HEAD >list && \n+\ttest_cmp_sorted list proper_object_list\n+'\n+\n+test_expect_success 'test rev-list with objects (no order)' '\n+\tgit-rev-list --objects HEAD >list && \n+\ttest_cmp_sorted list proper_object_list\n+'\n+\n+#verify age limiting\n+test_expect_success 'test rev-list date limiting (topo order)' '\n+\tgit-rev-list --topo-order --max-age=$min_date --min-age=$max_date HEAD >list && \n+\ttest_cmp_sorted list proper_list_date_limited\n+'\n+\n+test_expect_success 'test rev-list date limiting (no order)' '\n+\tgit-rev-list --max-age=$min_date --min-age=$max_date HEAD >list && \n+\ttest_cmp_sorted list proper_list_date_limited\n+'\n+\n+#check partial cache slice\n+test_expect_success 'saving old cache and generating partial slice' '\n+\tcp \".git/rev-cache/$cache_sha1\" .git/rev-cache/.old && \n+\trm \".git/rev-cache/$cache_sha1\" .git/rev-cache/index && \n+\n+\tgit-rev-cache add HEAD~2 2>output.err && \n+\tgrep \"final return value: 0\" output.err\n+'\n+\n+test_expect_success 'rev-list with wholly interesting partial slice' '\n+\tgit-rev-list --topo-order HEAD >list && \n+\ttest_cmp list proper_commit_list\n+'\n+\n+test_expect_success 'rev-list with partly uninteresting partial slice' '\n+\tgit-rev-list --topo-order HEAD --not HEAD~3 >list && \n+\ttest_cmp list proper_commit_list_limited\n+'\n+\n+test_expect_success 'rev-list with wholly uninteresting partial slice' '\n+\tgit-rev-list --topo-order HEAD --not HEAD~2 >list && \n+\ttest_cmp list proper_commit_list_limited2\n+'\n+\n+#try out index generation and fuse (note that --all == HEAD in this case)\n+#probably should make a test for that too...\n+test_expect_success 'test (non-)fusion of one slice' '\n+\tgit-rev-cache fuse >output.err && \n+\tgrep \"nothing to fuse\" output.err\n+'\n \n+test_expect_success 'make fresh slice' '\n+\tgit-rev-cache add --all --fresh 2>output.err && \n+\tgrep \"final return value: 0\" output.err\n+'\n+\n+test_expect_success 'check dual slices' '\n+\tgit-rev-list --topo-order HEAD~2 HEAD >list && \n+\ttest_cmp list proper_commit_list\n+'\n+\n+test_expect_success 'regenerate index' '\n+\trm .git/rev-cache/index && \n+\tgit-rev-cache index 2>output.err && \n+\tgrep \"final return value: 0\" output.err\n+'\n+\n+test_expect_success 'fuse slices' '\n+\ttest -e .git/rev-cache/.old && \n+\tgit-rev-cache fuse 2>output.err && \n+\tgrep \"final return value: 0\" output.err && \n+\ttest_cmp .git/rev-cache/$cache_sha1 .git/rev-cache/.old\n+'\n+\n+#make sure we can smoothly handle corrupted caches\n+test_expect_success 'corrupt slice' '\n+\techo bla >.git/rev-cache/$cache_sha1\n+'\n+\n+test_expect_success 'test rev-list traversal (limited) (corrupt slice)' '\n+\tgit-rev-list --topo-order HEAD --not HEAD~3 >list && \n+\ttest_cmp list proper_commit_list_limited\n+'\n+\n+test_expect_success 'test rev-list traversal (unlimited) (corrupt slice)' '\n+\tgit-rev-list HEAD >list && \n+\ttest_cmp_sorted list proper_commit_list\n+'\n+\n+test_expect_success 'corrupt index' '\n+\techo blu >.git/rev-cache/index\n+'\n+\n+test_expect_success 'test rev-list traversal (limited) (corrupt index)' '\n+\tgit-rev-list --topo-order HEAD --not HEAD~3 >list && \n+\ttest_cmp list proper_commit_list_limited\n+'\n+\n+test_expect_success 'test rev-list traversal (unlimited) (corrupt index)' '\n+\tgit-rev-list HEAD >list && \n+\ttest_cmp_sorted list proper_commit_list\n+'\n+\n+#test --ignore-size in fuse\n+rm .git/rev-cache/*\n+cache_sha1=`git-rev-cache add HEAD~2 2>output.err`\n+\n+test_expect_success 'make fragmented slices' '\n+\tgit-rev-cache add HEAD~1 --not HEAD~2 2>>output.err && \n+\tgit-rev-cache add HEAD --fresh 2>>output.err && \n+\ttest `grep \"final return value: 0\" output.err | wc -l` -eq 3\n+'\n+\n+cache_size=`wc -c .git/rev-cache/$cache_sha1 | grep -o \"[0-9]*\"`\n+test_expect_success 'test --ignore-size function in fuse' '\n+\tgit-rev-cache fuse --ignore-size=$cache_size 2>output.err && \n+\tgrep \"final return value: 0\" output.err && \n+\ttest -e .git/rev-cache/$cache_sha1\n+'\n+\n+test_done\n-- \ntg: (2f0aff6..) t/revcache/integration (depends on: t/revcache/misc)\n"},{"id":"121086","messageId":"op.uyuwkuoxtdk399@sirnot.private","threadId":"20633","inReplyTo":"op.uys3quhbtdk399@sirnot.private","subject":"Re: [PATCH 5/6 (v4)] full integration of rev-cache into git, completed test suite","fromName":"Nick Edelen","fromEmail":"sirnot@gmail.com","sentAt":"2009-08-18T11:51:56Z","receivedAt":"2009-08-18T11:51:56Z","isPatch":true,"sender":{"key":"sirnot@gmail.com","avatar":null},"body":"This last patch provides a working integration of rev-cache into the revision\nwalker, along with some touch-ups:\n - integration into revision walker and list-objects\n - tweak of object generation to take advantage of the 'unique' field\n - more fluid handling of damaged cache slices\n - numerous tests for both features from the previous patch, and the\nintegration's integrity\n\n'Integration' is rather broad -- a more detailed description follows for each\naspect:\n - rev-cache\nthe traversal mechanism is updated to handle many of the non-prune options\nrev-list does (date limiting, slop-handling, etc.), and is adjusted to allow\nfor non-fatal cache-traversal failures.\n\n - revision walker\nboth limited and unlimited traversal attempt to use the cache when possible,\nsmoothly falling back if it's not.\n\n - list-objects\nobject listing does not recurse into cached trees, and has been adjusted to\nguarantee commit-tag-tree-blob ordering.\n\nSigned-off-by: Nick Edelen <sirnot@gmail.com>\n\n---\n builtin-rev-cache.c       |   40 ++++++++\n list-objects.c            |   49 ++++++++--\n rev-cache.c               |  228 +++++++++++++++++++++++++++++++++++++++-----\n revision.c                |   88 ++++++++++++++---\n t/t6015-rev-cache-list.sh |  153 +++++++++++++++++++++++++++++--\n 5 files changed, 502 insertions(+), 56 deletions(-)\n\ndiff --git a/builtin-rev-cache.c b/builtin-rev-cache.c\nindex b894c54..8f41123 100644\n--- a/builtin-rev-cache.c\n+++ b/builtin-rev-cache.c\n@@ -4,6 +4,7 @@\n #include \"diff.h\"\n #include \"revision.h\"\n #include \"rev-cache.h\"\n+#include \"list-objects.h\"\n \n unsigned long default_ignore_size = 50 * 1024 * 1024; /* 50mb */\n \n@@ -78,6 +79,43 @@ static int handle_add(int argc, const char *argv[]) /* args beyond this command\n \treturn 0;\n }\n \n+static void show_commit(struct commit *commit, void *data)\n+{\n+\tprintf(\"%s\\n\", sha1_to_hex(commit->object.sha1));\n+}\n+\n+static void show_object(struct object *obj, const struct name_path *path, const char *last)\n+{\n+\tprintf(\"%s\\n\", sha1_to_hex(obj->sha1));\n+}\n+\n+static int test_rev_list(int argc, const char *argv[])\n+{\n+\tstruct rev_info revs;\n+\tunsigned int flags = 0;\n+\tint i;\n+\n+\tinit_revisions(&revs, 0);\n+\n+\tfor (i = 0; i < argc; i++) {\n+\t\tif (!strcmp(argv[i], \"--not\"))\n+\t\t\tflags ^= UNINTERESTING;\n+\t\telse if (!strcmp(argv[i], \"--objects\"))\n+\t\t\trevs.tree_objects = revs.blob_objects = 1;\n+\t\telse\n+\t\t\thandle_revision_arg(argv[i], &revs, flags, 1);\n+\t}\n+\n+\tsetup_revisions(0, 0, &revs, 0);\n+\trevs.topo_order = 1;\n+\trevs.lifo = 1;\n+\tprepare_revision_walk(&revs);\n+\n+\ttraverse_commit_list(&revs, show_commit, show_object, 0);\n+\n+\treturn 0;\n+}\n+\n static int handle_walk(int argc, const char *argv[])\n {\n \tstruct commit *commit;\n@@ -271,6 +309,8 @@ int cmd_rev_cache(int argc, const char *argv[], const char *prefix)\n \t\tr = handle_walk(argc, argv);\n \telse if (!strcmp(arg, \"index\"))\n \t\tr = handle_index(argc, argv);\n+\telse if (!strcmp(arg, \"test\"))\n+\t\tr = test_rev_list(argc, argv);\n \telse if (!strcmp(arg, \"alt\"))\n \t\tr = handle_alt(argc, argv);\n \telse\ndiff --git a/list-objects.c b/list-objects.c\nindex 8953548..821a290 100644\n--- a/list-objects.c\n+++ b/list-objects.c\n@@ -74,22 +74,33 @@ static void process_tree(struct rev_info *revs,\n \t\tdie(\"bad tree object\");\n \tif (obj->flags & (UNINTERESTING | SEEN))\n \t\treturn;\n-\tif (parse_tree(tree) < 0)\n-\t\tdie(\"bad tree object %s\", sha1_to_hex(obj->sha1));\n+\n \tobj->flags |= SEEN;\n \tshow(obj, path, name);\n+\tif (obj->flags & FACE_VALUE)\n+\t\treturn;\n+\n+\t/* traverse_commit_list is only used for enumeration purposes,\n+\t * ie. nothing relies on trees being parsed in this routine */\n+\tif (parse_tree(tree) < 0)\n+\t\tdie(\"bad tree object %s\", sha1_to_hex(obj->sha1));\n+\n \tme.up = path;\n \tme.elem = name;\n \tme.elem_len = strlen(name);\n-\n \tinit_tree_desc(&desc, tree->buffer, tree->size);\n \n \twhile (tree_entry(&desc, &entry)) {\n-\t\tif (S_ISDIR(entry.mode))\n+\t\tif (S_ISDIR(entry.mode)) {\n+\t\t\tstruct tree *subtree = lookup_tree(entry.sha1);\n+\t\t\tif (!subtree)\n+\t\t\t\tcontinue;\n+\n+\t\t\tsubtree->object.flags &= ~FACE_VALUE;\n \t\t\tprocess_tree(revs,\n-\t\t\t\t     lookup_tree(entry.sha1),\n+\t\t\t\t     subtree,\n \t\t\t\t     show, &me, entry.path);\n-\t\telse if (S_ISGITLINK(entry.mode))\n+\t\t} else if (S_ISGITLINK(entry.mode))\n \t\t\tprocess_gitlink(revs, entry.sha1,\n \t\t\t\t\tshow, &me, entry.path);\n \t\telse\n@@ -136,6 +147,7 @@ void mark_edges_uninteresting(struct commit_list *list,\n \n static void add_pending_tree(struct rev_info *revs, struct tree *tree)\n {\n+\ttree->object.flags &= ~FACE_VALUE;\n \tadd_pending_object(revs, &tree->object, \"\");\n }\n \n@@ -146,17 +158,27 @@ void traverse_commit_list(struct rev_info *revs,\n {\n \tint i;\n \tstruct commit *commit;\n+\tenum object_type what = OBJ_TAG;\n+\tchar face_value = 0;\n \n \twhile ((commit = get_revision(revs)) != NULL) {\n-\t\tadd_pending_tree(revs, commit->tree);\n+\t\tif (!(commit->object.flags & FACE_VALUE))\n+\t\t\tadd_pending_tree(revs, commit->tree);\n+\t\telse\n+\t\t\tface_value = 1;\n \t\tshow_commit(commit, data);\n \t}\n+\n+loop_objects:\n \tfor (i = 0; i < revs->pending.nr; i++) {\n \t\tstruct object_array_entry *pending = revs->pending.objects + i;\n \t\tstruct object *obj = pending->item;\n \t\tconst char *name = pending->name;\n \t\tif (obj->flags & (UNINTERESTING | SEEN))\n \t\t\tcontinue;\n+\t\tif (obj->type != what && face_value)\n+\t\t\tcontinue;\n+\n \t\tif (obj->type == OBJ_TAG) {\n \t\t\tobj->flags |= SEEN;\n \t\t\tshow_object(obj, NULL, name);\n@@ -175,6 +197,19 @@ void traverse_commit_list(struct rev_info *revs,\n \t\tdie(\"unknown pending object %s (%s)\",\n \t\t    sha1_to_hex(obj->sha1), name);\n \t}\n+\tif (face_value) {\n+\t\tswitch (what) {\n+\t\tcase OBJ_TAG :\n+\t\t\twhat = OBJ_TREE;\n+\t\t\tgoto loop_objects;\n+\t\tcase OBJ_TREE :\n+\t\t\twhat = OBJ_BLOB;\n+\t\t\tgoto loop_objects;\n+\t\tdefault :\n+\t\t\tbreak;\n+\t\t}\n+\t}\n+\n \tif (revs->pending.nr) {\n \t\tfree(revs->pending.objects);\n \t\trevs->pending.nr = 0;\ndiff --git a/rev-cache.c b/rev-cache.c\nindex 8ca97d3..04a9b02 100644\n--- a/rev-cache.c\n+++ b/rev-cache.c\n@@ -11,6 +11,12 @@\n #include \"run-command.h\"\n #include \"string-list.h\"\n \n+\n+struct bad_slice {\n+\tunsigned char sha1[20];\n+\tstruct bad_slice *next;\n+};\n+\n struct cache_slice_pointer {\n \tchar signature[8]; /* REVCOPTR */\n \tchar version;\n@@ -23,8 +29,9 @@ static uint32_t fanout[0xff + 2];\n static unsigned char *idx_map;\n static int idx_size;\n static struct rc_index_header idx_head;\n+static char no_idx, add_to_pending;\n+static struct bad_slice *bad_slices;\n static unsigned char *idx_caches;\n-static char no_idx;\n \n static struct strbuf *acc_buffer;\n \n@@ -121,6 +128,30 @@ struct rc_object_entry_ondisk *to_disked_rc_object_entry(struct rc_object_entry\n \treturn dst;\n }\n \n+static void mark_bad_slice(unsigned char *sha1)\n+{\n+\tstruct bad_slice *bad;\n+\n+\tbad = xcalloc(sizeof(struct bad_slice), 1);\n+\thashcpy(bad->sha1, sha1);\n+\n+\tbad->next = bad_slices;\n+\tbad_slices = bad;\n+}\n+\n+static int is_bad_slice(unsigned char *sha1)\n+{\n+\tstruct bad_slice *bad = bad_slices;\n+\n+\twhile (bad) {\n+\t\tif (!hashcmp(bad->sha1, sha1))\n+\t\t\treturn 1;\n+\t\tbad = bad->next;\n+\t}\n+\n+\treturn 0;\n+}\n+\n static int get_index_head(unsigned char *map, int len, struct rc_index_header *head, uint32_t *fanout, unsigned char **caches)\n {\n \tstruct rc_index_header whead;\n@@ -246,6 +277,7 @@ static struct rc_index_entry *search_index(unsigned char *sha1)\n unsigned char *get_cache_slice(struct commit *commit)\n {\n \tstruct rc_index_entry *ie;\n+\tunsigned char *sha1;\n \n \tif (!idx_map) {\n \t\tif (no_idx)\n@@ -257,8 +289,13 @@ unsigned char *get_cache_slice(struct commit *commit)\n \t\treturn 0;\n \n \tie = search_index(commit->object.sha1);\n-\tif (ie && ie->cache_index < idx_head.cache_nr)\n-\t\treturn idx_caches + ie->cache_index * 20;\n+\tif (ie && ie->cache_index < idx_head.cache_nr) {\n+\t\tsha1 = idx_caches + ie->cache_index * 20;\n+\n+\t\tif (is_bad_slice(sha1))\n+\t\t\treturn 0;\n+\t\treturn sha1;\n+\t}\n \n \treturn 0;\n }\n@@ -268,6 +305,20 @@ unsigned char *get_cache_slice(struct commit *commit)\n \n static unsigned long decode_size(unsigned char *str, int len);\n \n+/* on failure */\n+static void restore_commit(struct commit *commit)\n+{\n+\tcommit->object.flags &= ~(ADDED | SEEN | FACE_VALUE);\n+\n+\tif (!commit->object.parsed) {\n+\t\twhile (pop_commit(&commit->parents))\n+\t\t\t;\n+\n+\t\tparse_commit(commit);\n+\t}\n+\n+}\n+\n static void handle_noncommit(struct rev_info *revs, struct commit *commit, unsigned char *ptr, struct rc_object_entry *entry)\n {\n \tstruct blob *blob;\n@@ -307,23 +358,27 @@ static void handle_noncommit(struct rev_info *revs, struct commit *commit, unsig\n \t}\n \n \tobj->flags |= FACE_VALUE;\n-\tadd_pending_object(revs, obj, \"\");\n+\tif (add_to_pending)\n+\t\tadd_pending_object(revs, obj, \"\");\n }\n \n-static int setup_traversal(struct rc_slice_header *head, unsigned char *map, struct commit *commit, struct commit_list **work)\n+static int setup_traversal(struct rc_slice_header *head, unsigned char *map, struct commit *commit, struct commit_list **work,\n+\tstruct commit_list **unwork, int *ipath_nr, int *upath_nr, char *ioutside)\n {\n \tstruct rc_index_entry *iep;\n \tstruct rc_object_entry *oep;\n \tstruct commit_list *prev, *wp, **wpp;\n \tint retval;\n \n-\tiep = search_index(commit->object.sha1), 0;\n+\tiep = search_index(commit->object.sha1);\n \toep = RC_OBTAIN_OBJECT_ENTRY(map + iep->pos);\n+\tif (commit->object.flags & UNINTERESTING) {\n+\t\t++*upath_nr;\n+\t\toep->uninteresting = 1;\n+\t} else\n+\t\t++*ipath_nr;\n \n-\t/* the .uniniteresting bit isn't strictly necessary, as we check the object during traversal as well,\n-\t * but we might as well initialize it while we're at it */\n \toep->include = 1;\n-\toep->uninteresting = !!(commit->object.flags & UNINTERESTING);\n \tto_disked_rc_object_entry(oep, (struct rc_object_entry_ondisk *)(map + iep->pos));\n \tretval = iep->pos;\n \n@@ -338,6 +393,10 @@ static int setup_traversal(struct rc_slice_header *head, unsigned char *map, str\n \t\t/* is this in our cache slice? */\n \t\tiep = search_index(obj->sha1);\n \t\tif (!iep || hashcmp(idx_caches + iep->cache_index * 20, head->sha1)) {\n+\t\t\t/* there are interesing objects outside the slice */\n+\t\t\tif (!(obj->flags & UNINTERESTING))\n+\t\t\t\t*ioutside = 1;\n+\n \t\t\tprev = wp;\n \t\t\twp = wp->next;\n \t\t\twpp = &wp;\n@@ -354,11 +413,20 @@ static int setup_traversal(struct rc_slice_header *head, unsigned char *map, str\n \t\toep->uninteresting = !!(obj->flags & UNINTERESTING);\n \t\tto_disked_rc_object_entry(oep, (struct rc_object_entry_ondisk *)(map + iep->pos));\n \n+\t\t/* count even if not in slice so we can stop enumerating if possible */\n+\t\tif (obj->flags & UNINTERESTING)\n+\t\t\t++*upath_nr;\n+\t\telse\n+\t\t\t++*ipath_nr;\n+\n \t\t/* remove from work list */\n \t\tco = pop_commit(wpp);\n \t\twp = *wpp;\n \t\tif (prev)\n \t\t\tprev->next = wp;\n+\n+\t\t/* ...and store in temp list so we can restore work on failure */\n+\t\tcommit_list_insert(co, unwork);\n \t}\n \n \treturn retval;\n@@ -375,13 +443,18 @@ static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *m\n \tunsigned long *date_so_far, int *slop_so_far,\n \tstruct commit_list ***queue, struct commit_list **work)\n {\n-\tstruct commit_list *insert_cache = 0;\n+\tstruct commit_list *insert_cache = 0, *myq = 0, **myqp = &myq, *mywork = 0, **myworkp = &mywork, *unwork = 0;\n \tstruct commit **last_objects, *co;\n-\tint i, total_path_nr = head->path_nr, retval = -1;\n-\tchar consume_children = 0;\n+\tunsigned long date = date_so_far ? *date_so_far : ~0ul;\n+\tint i, ipath_nr = 0, upath_nr = 0, orig_obj_nr = 0,\n+\t\ttotal_path_nr = head->path_nr, retval = -1, slop = slop_so_far ? *slop_so_far : SLOP;\n+\tchar consume_children = 0, ioutside = 0;\n \tunsigned char *paths;\n \n-\ti = setup_traversal(head, map, commit, work);\n+\t/* take note in case we need to regress */\n+\torig_obj_nr = revs->pending.nr;\n+\n+\ti = setup_traversal(head, map, commit, work, &unwork, &ipath_nr, &upath_nr, &ioutside);\n \tif (i < 0)\n \t\treturn -1;\n \n@@ -429,6 +502,7 @@ static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *m\n \n \t\tif ((paths[path] & IPATH) && (paths[path] & UPATH)) {\n \t\t\tpaths[path] = UPATH;\n+\t\t\tipath_nr--;\n \n \t\t\t/* mark edge */\n \t\t\tif (last_objects[path]) {\n@@ -439,6 +513,7 @@ static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *m\n \t\t\t\tlast_objects[path]->object.flags &= ~FACE_VALUE;\n \t\t\t\tlast_objects[path] = 0;\n \t\t\t}\n+\t\t\tobj->flags |= BOUNDARY;\n \t\t}\n \n \t\t/* now we gotta re-assess the whole interesting thing... */\n@@ -462,8 +537,10 @@ static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *m\n \t\t\t\t\t\tlast_objects[p]->object.flags &= ~FACE_VALUE;\n \t\t\t\t\t\tlast_objects[p] = 0;\n \t\t\t\t\t}\n-\t\t\t\t} else if (last_objects[p] && !last_objects[p]->object.parsed)\n+\t\t\t\t\tobj->flags |= BOUNDARY;\n+\t\t\t\t} else if (last_objects[p] && !last_objects[p]->object.parsed) {\n \t\t\t\t\tcommit_list_insert(co, &last_objects[p]->parents);\n+\t\t\t\t}\n \n \t\t\t\t/* can't close a merge path until all are parents have been encountered */\n \t\t\t\tif (GET_COUNT(paths[p])) {\n@@ -473,14 +550,33 @@ static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *m\n \t\t\t\t\t\tcontinue;\n \t\t\t\t}\n \n+\t\t\t\tif (paths[p] & IPATH)\n+\t\t\t\t\tipath_nr--;\n+\t\t\t\telse\n+\t\t\t\t\tupath_nr--;\n+\n \t\t\t\tpaths[p] = 0;\n \t\t\t\tlast_objects[p] = 0;\n \t\t\t}\n \t\t}\n \n \t\t/* make topo relations */\n-\t\tif (last_objects[path] && !last_objects[path]->object.parsed)\n+\t\tif (last_objects[path] && !last_objects[path]->object.parsed) {\n \t\t\tcommit_list_insert(co, &last_objects[path]->parents);\n+\t\t}\n+\n+\t\t/* we've been here already */\n+\t\tif (obj->flags & ADDED) {\n+\t\t\tif (entry->uninteresting && !(obj->flags & UNINTERESTING)) {\n+\t\t\t\tobj->flags |= UNINTERESTING;\n+\t\t\t\tmark_parents_uninteresting(co);\n+\t\t\t\tupath_nr--;\n+\t\t\t} else if (!entry->uninteresting)\n+\t\t\t\tipath_nr--;\n+\n+\t\t\tpaths[path] = 0;\n+\t\t\tcontinue;\n+\t\t}\n \n \t\t/* initialize commit */\n \t\tif (!entry->is_end) {\n@@ -493,24 +589,51 @@ static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *m\n \n \t\tif (entry->uninteresting)\n \t\t\tobj->flags |= UNINTERESTING;\n+\t\telse if (co->date < date)\n+\t\t\tdate = co->date;\n \n \t\t/* we need to know what the edges are */\n \t\tlast_objects[path] = co;\n \n \t\t/* add to list */\n-\t\tif (!(obj->flags & UNINTERESTING) || revs->show_all) {\n-\t\t\tif (entry->is_end)\n-\t\t\t\tinsert_by_date_cached(co, work, insert_cache, &insert_cache);\n-\t\t\telse\n-\t\t\t\t*queue = &commit_list_insert(co, *queue)->next;\n+\t\tif (slop && !(revs->min_age != -1 && co->date > revs->min_age)) {\n+\n+\t\t\tif (!(obj->flags & UNINTERESTING) || revs->show_all) {\n+\t\t\t\tif (entry->is_end)\n+\t\t\t\t\tmyworkp = &commit_list_insert(co, myworkp)->next;\n+\t\t\t\telse\n+\t\t\t\t\tmyqp = &commit_list_insert(co, myqp)->next;\n+\n+\t\t\t\t/* add children to list as well */\n+\t\t\t\tif (obj->flags & UNINTERESTING)\n+\t\t\t\t\tconsume_children = 0;\n+\t\t\t\telse\n+\t\t\t\t\tconsume_children = 1;\n+\t\t\t}\n \n-\t\t\t/* add children to list as well */\n-\t\t\tif (obj->flags & UNINTERESTING)\n-\t\t\t\tconsume_children = 0;\n-\t\t\telse\n-\t\t\t\tconsume_children = 1;\n \t\t}\n \n+\t\t/* should we continue? */\n+\t\tif (!slop) {\n+\t\t\tif (!upath_nr) {\n+\t\t\t\tbreak;\n+\t\t\t} else if (ioutside || revs->show_all) {\n+\t\t\t\t/* pass it back to rev-list\n+\t\t\t\t * we purposely ignore everything outside this cache, so we don't needlessly traverse the whole\n+\t\t\t\t * thing on uninteresting, but that does mean that we may need to bounce back\n+\t\t\t\t * and forth a few times with rev-list */\n+\t\t\t\tmyworkp = &commit_list_insert(co, myworkp)->next;\n+\n+\t\t\t\tpaths[path] = 0;\n+\t\t\t\tupath_nr--;\n+\t\t\t} else {\n+\t\t\t\tbreak;\n+\t\t\t}\n+\t\t} else if (!ipath_nr && co->date <= date)\n+\t\t\tslop--;\n+\t\telse\n+\t\t\tslop = SLOP;\n+\n \t\t/* open parents */\n \t\tif (entry->merge_nr) {\n \t\t\tint j, off = index + sizeof(struct rc_object_entry_ondisk);\n@@ -525,6 +648,11 @@ static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *m\n \t\t\t\tif (paths[p] & flag)\n \t\t\t\t\tcontinue;\n \n+\t\t\t\tif (flag == IPATH)\n+\t\t\t\t\tipath_nr++;\n+\t\t\t\telse\n+\t\t\t\t\tupath_nr++;\n+\n \t\t\t\tpaths[p] |= flag;\n \t\t\t}\n \n@@ -534,12 +662,55 @@ static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *m\n \n \t}\n \n+\tif (date_so_far)\n+\t\t*date_so_far = date;\n+\tif (slop_so_far)\n+\t\t*slop_so_far = slop;\n \tretval = 0;\n \n+\t/* success: attach to given lists */\n+\tif (myqp != &myq) {\n+\t\t**queue = myq;\n+\t\t*queue = myqp;\n+\t}\n+\n+\twhile ((co = pop_commit(&mywork)) != 0) {\n+\t\tinsert_by_date_cached(co, work, insert_cache, &insert_cache);\n+\t}\n+\n+\t/* free backup */\n+\twhile (pop_commit(&unwork))\n+\t\t;\n+\n end:\n \tfree(paths);\n \tfree(last_objects);\n \n+\t/* failure: restore work to previous condition\n+\t * (cache corruption should *not* be fatal) */\n+\tif (retval) {\n+\t\twhile ((co = pop_commit(&unwork)) != 0) {\n+\t\t\trestore_commit(co);\n+\t\t\tco->object.flags |= SEEN;\n+\t\t\tinsert_by_date(co, work);\n+\t\t}\n+\n+\t\t/* free lists */\n+\t\twhile ((co = pop_commit(&myq)) != 0)\n+\t\t\trestore_commit(co);\n+\n+\t\twhile ((co = pop_commit(&mywork)) != 0)\n+\t\t\trestore_commit(co);\n+\n+\t\t/* truncate object array */\n+\t\tfor (i = orig_obj_nr; i < revs->pending.nr; i++) {\n+\t\t\tstruct object *obj = revs->pending.objects[i].item;\n+\n+\t\t\tobj->flags &= ~FACE_VALUE;\n+\t\t}\n+\t\trevs->pending.nr = orig_obj_nr;\n+\t}\n+\n \treturn retval;\n }\n \n@@ -630,6 +801,7 @@ int traverse_cache_slice(struct rev_info *revs,\n \n \t/* load options */\n \trci = &revs->rev_cache_info;\n+\tadd_to_pending = rci->add_to_pending;\n \n \tmemset(&head, 0, sizeof(struct rc_slice_header));\n \n@@ -653,6 +825,10 @@ end:\n \tif (fd != -1)\n \t\tclose(fd);\n \n+\t/* remember this! */\n+\tif (retval)\n+\t\tmark_bad_slice(cache_sha1);\n+\n \treturn retval;\n }\n \ndiff --git a/revision.c b/revision.c\nindex 485bf72..4640536 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -12,6 +12,7 @@\n #include \"patch-ids.h\"\n #include \"decorate.h\"\n #include \"log-tree.h\"\n+#include \"rev-cache.h\"\n \n volatile show_early_output_fn_t show_early_output;\n \n@@ -638,6 +639,8 @@ static int limit_list(struct rev_info *revs)\n \tstruct commit_list *list = revs->commits;\n \tstruct commit_list *newlist = NULL;\n \tstruct commit_list **p = &newlist;\n+\tunsigned char *cache_sha1;\n+\tchar used_cache;\n \n \twhile (list) {\n \t\tstruct commit_list *entry = list;\n@@ -650,24 +653,39 @@ static int limit_list(struct rev_info *revs)\n \n \t\tif (revs->max_age != -1 && (commit->date < revs->max_age))\n \t\t\tobj->flags |= UNINTERESTING;\n-\t\tif (add_parents_to_list(revs, commit, &list, NULL) < 0)\n-\t\t\treturn -1;\n-\t\tif (obj->flags & UNINTERESTING) {\n-\t\t\tmark_parents_uninteresting(commit);\n-\t\t\tif (revs->show_all)\n-\t\t\t\tp = &commit_list_insert(commit, p)->next;\n-\t\t\tslop = still_interesting(list, date, slop);\n-\t\t\tif (slop)\n+\n+\t\t/* rev-cache to the rescue!!! */\n+\t\tused_cache = 0;\n+\t\tif (!revs->dont_cache_me && !(obj->flags & ADDED)) {\n+\t\t\tcache_sha1 = get_cache_slice(commit);\n+\t\t\tif (cache_sha1) {\n+\t\t\t\tif (traverse_cache_slice(revs, cache_sha1, commit, &date, &slop, &p, &list) < 0)\n+\t\t\t\t\tused_cache = 0;\n+\t\t\t\telse\n+\t\t\t\t\tused_cache = 1;\n+\t\t\t}\n+\t\t}\n+\n+\t\tif (!used_cache) {\n+\t\t\tif (add_parents_to_list(revs, commit, &list, NULL) < 0)\n+\t\t\t\treturn -1;\n+\t\t\tif (obj->flags & UNINTERESTING) {\n+\t\t\t\tmark_parents_uninteresting(commit); /* ME: why? */\n+\t\t\t\tif (revs->show_all)\n+\t\t\t\t\tp = &commit_list_insert(commit, p)->next;\n+\t\t\t\tslop = still_interesting(list, date, slop);\n+\t\t\t\tif (slop > 0)\n+\t\t\t\t\tcontinue;\n+\t\t\t\t/* If showing all, add the whole pending list to the end */\n+\t\t\t\tif (revs->show_all)\n+\t\t\t\t\t*p = list;\n+\t\t\t\tbreak;\n+\t\t\t}\n+\t\t\tif (revs->min_age != -1 && (commit->date > revs->min_age))\n \t\t\t\tcontinue;\n-\t\t\t/* If showing all, add the whole pending list to the end */\n-\t\t\tif (revs->show_all)\n-\t\t\t\t*p = list;\n-\t\t\tbreak;\n+\t\t\tdate = commit->date;\n+\t\t\tp = &commit_list_insert(commit, p)->next;\n \t\t}\n-\t\tif (revs->min_age != -1 && (commit->date > revs->min_age))\n-\t\t\tcontinue;\n-\t\tdate = commit->date;\n-\t\tp = &commit_list_insert(commit, p)->next;\n \n \t\tshow = show_early_output;\n \t\tif (!show)\n@@ -813,6 +831,8 @@ void init_revisions(struct rev_info *revs, const char *prefix)\n \t\trevs->diffopt.prefix = prefix;\n \t\trevs->diffopt.prefix_length = strlen(prefix);\n \t}\n+\n+\tinit_rev_cache_info(&revs->rev_cache_info);\n }\n \n static void add_pending_commit_list(struct rev_info *revs,\n@@ -1372,6 +1392,11 @@ int setup_revisions(int argc, const char **argv, struct rev_info *revs, const ch\n \tif (revs->reflog_info && revs->graph)\n \t\tdie(\"cannot combine --walk-reflogs with --graph\");\n \n+\t/* limits on caching\n+\t * todo: implement this functionality */\n+\tif (revs->prune || revs->diff)\n+\t\trevs->dont_cache_me = 1;\n+\n \treturn left;\n }\n \n@@ -1654,6 +1679,8 @@ static int commit_match(struct commit *commit, struct rev_info *opt)\n {\n \tif (!opt->grep_filter.pattern_list)\n \t\treturn 1;\n+\tif (!commit->object.parsed)\n+\t\tparse_commit(commit);\n \treturn grep_buffer(&opt->grep_filter,\n \t\t\t   NULL, /* we say nothing, not even filename */\n \t\t\t   commit->buffer, strlen(commit->buffer));\n@@ -1706,6 +1733,7 @@ static struct commit *get_revision_1(struct rev_info *revs)\n \tdo {\n \t\tstruct commit_list *entry = revs->commits;\n \t\tstruct commit *commit = entry->item;\n+\t\tstruct object *obj = &commit->object;\n \n \t\trevs->commits = entry->next;\n \t\tfree(entry);\n@@ -1722,11 +1750,39 @@ static struct commit *get_revision_1(struct rev_info *revs)\n \t\t\tif (revs->max_age != -1 &&\n \t\t\t    (commit->date < revs->max_age))\n \t\t\t\tcontinue;\n+\n+\t\t\tif (!revs->dont_cache_me) {\n+\t\t\t\tstruct commit_list *queue = 0, **queuep = &queue;\n+\t\t\t\tunsigned char *cache_sha1;\n+\n+\t\t\t\tif (obj->flags & ADDED)\n+\t\t\t\t\tgoto skip_parenting;\n+\n+\t\t\t\tcache_sha1 = get_cache_slice(commit);\n+\t\t\t\tif (cache_sha1) {\n+\t\t\t\t\tif (!traverse_cache_slice(revs, cache_sha1, commit, 0, 0, &queuep, &revs->commits)) {\n+\t\t\t\t\t\tstruct commit_list *work = revs->commits;\n+\n+\t\t\t\t\t\t/* attach queue to end of ->commits */\n+\t\t\t\t\t\twhile (work && work->next)\n+\t\t\t\t\t\t\twork = work->next;\n+\n+\t\t\t\t\t\tif (work)\n+\t\t\t\t\t\t\twork->next = queue;\n+\t\t\t\t\t\telse\n+\t\t\t\t\t\t\trevs->commits = queue;\n+\n+\t\t\t\t\t\tgoto skip_parenting;\n+\t\t\t\t\t}\n+\t\t\t\t}\n+\t\t\t}\n+\n \t\t\tif (add_parents_to_list(revs, commit, &revs->commits, NULL) < 0)\n \t\t\t\tdie(\"Failed to traverse parents of commit %s\",\n \t\t\t\t    sha1_to_hex(commit->object.sha1));\n \t\t}\n \n+skip_parenting:\n \t\tswitch (simplify_commit(revs, commit)) {\n \t\tcase commit_ignore:\n \t\t\tcontinue;\ndiff --git a/t/t6015-rev-cache-list.sh b/t/t6015-rev-cache-list.sh\nindex dc0fc07..065f214 100755\n--- a/t/t6015-rev-cache-list.sh\n+++ b/t/t6015-rev-cache-list.sh\n@@ -38,6 +38,7 @@ test_expect_success 'init repo' '\n \tgit add . &&\n \tgit commit -m \"omg\" &&\n \n+\tsleep 2 &&\n \tgit branch b4 &&\n \tgit checkout b4 &&\n \techo shazam >file8 &&\n@@ -46,7 +47,7 @@ test_expect_success 'init repo' '\n \tgit merge -m \"merge b2\" b2 &&\n \n \techo bam >smoke/pipe &&\n-\tgit add .\n+\tgit add . &&\n \tgit commit -m \"bam\" &&\n \n \tgit checkout master &&\n@@ -71,18 +72,26 @@ test_expect_success 'init repo' '\n \tgit add . &&\n \tgit commit -m \"lol\" &&\n \n+\tsleep 2 &&\n \tgit checkout master &&\n \tgit merge -m \"triple merge\" b1 b11 &&\n-\tgit rm -r d1 &&\n+\tgit rm -r d1 && \n+\tsleep 2 &&\n \tgit commit -a -m \"oh noes\"\n '\n \n-git-rev-list HEAD --not HEAD~3 >proper_commit_list_limited\n-git-rev-list HEAD >proper_commit_list\n-git-rev-list HEAD --objects >proper_object_list\n+max_date=`git-rev-list --timestamp HEAD~1 --max-count=1 | grep -e \"^[0-9]*\" -o`\n+min_date=`git-rev-list --timestamp b4 --max-count=1 | grep -e \"^[0-9]*\" -o`\n+\n+git-rev-list --topo-order HEAD --not HEAD~3 >proper_commit_list_limited\n+git-rev-list --topo-order HEAD --not HEAD~2 >proper_commit_list_limited2\n+git-rev-list --topo-order HEAD >proper_commit_list\n+git-rev-list --objects HEAD >proper_object_list\n+git-rev-list HEAD --max-age=$min_date --min-age=$max_date >proper_list_date_limited\n+\n+cache_sha1=`git-rev-cache add HEAD 2>output.err`\n \n test_expect_success 'make cache slice' '\n-\tgit-rev-cache add HEAD 2>output.err &&\n \tgrep \"final return value: 0\" output.err\n '\n \n@@ -102,11 +111,141 @@ test_expect_success 'test rev-caches walker directly (unlimited)' '\n \ttest_cmp_sorted list proper_commit_list\n '\n \n+test_expect_success 'test rev-list traversal (limited)' '\n+\tgit-rev-list HEAD --not HEAD~3 >list &&\n+\ttest_cmp list proper_commit_list_limited\n+'\n+\n+test_expect_success 'test rev-list traversal (unlimited)' '\n+\tgit-rev-list HEAD >list &&\n+\ttest_cmp list proper_commit_list\n+'\n+\n #do the same for objects\n test_expect_success 'test rev-caches walker with objects' '\n \tgit-rev-cache walk --objects HEAD >list &&\n \ttest_cmp_sorted list proper_object_list\n '\n \n-test_done\n+test_expect_success 'test rev-list with objects (topo order)' '\n+\tgit-rev-list --topo-order --objects HEAD >list &&\n+\ttest_cmp_sorted list proper_object_list\n+'\n+\n+test_expect_success 'test rev-list with objects (no order)' '\n+\tgit-rev-list --objects HEAD >list &&\n+\ttest_cmp_sorted list proper_object_list\n+'\n+\n+#verify age limiting\n+test_expect_success 'test rev-list date limiting (topo order)' '\n+\tgit-rev-list --topo-order --max-age=$min_date --min-age=$max_date HEAD >list &&\n+\ttest_cmp_sorted list proper_list_date_limited\n+'\n+\n+test_expect_success 'test rev-list date limiting (no order)' '\n+\tgit-rev-list --max-age=$min_date --min-age=$max_date HEAD >list &&\n+\ttest_cmp_sorted list proper_list_date_limited\n+'\n+\n+#check partial cache slice\n+test_expect_success 'saving old cache and generating partial slice' '\n+\tcp \".git/rev-cache/$cache_sha1\" .git/rev-cache/.old &&\n+\trm \".git/rev-cache/$cache_sha1\" .git/rev-cache/index &&\n+\n+\tgit-rev-cache add HEAD~2 2>output.err &&\n+\tgrep \"final return value: 0\" output.err\n+'\n+\n+test_expect_success 'rev-list with wholly interesting partial slice' '\n+\tgit-rev-list --topo-order HEAD >list &&\n+\ttest_cmp list proper_commit_list\n+'\n+\n+test_expect_success 'rev-list with partly uninteresting partial slice' '\n+\tgit-rev-list --topo-order HEAD --not HEAD~3 >list &&\n+\ttest_cmp list proper_commit_list_limited\n+'\n+\n+test_expect_success 'rev-list with wholly uninteresting partial slice' '\n+\tgit-rev-list --topo-order HEAD --not HEAD~2 >list &&\n+\ttest_cmp list proper_commit_list_limited2\n+'\n+\n+#try out index generation and fuse (note that --all == HEAD in this case)\n+#probably should make a test for that too...\n+test_expect_success 'test (non-)fusion of one slice' '\n+\tgit-rev-cache fuse >output.err &&\n+\tgrep \"nothing to fuse\" output.err\n+'\n \n+test_expect_success 'make fresh slice' '\n+\tgit-rev-cache add --all --fresh 2>output.err &&\n+\tgrep \"final return value: 0\" output.err\n+'\n+\n+test_expect_success 'check dual slices' '\n+\tgit-rev-list --topo-order HEAD~2 HEAD >list &&\n+\ttest_cmp list proper_commit_list\n+'\n+\n+test_expect_success 'regenerate index' '\n+\trm .git/rev-cache/index &&\n+\tgit-rev-cache index 2>output.err &&\n+\tgrep \"final return value: 0\" output.err\n+'\n+\n+test_expect_success 'fuse slices' '\n+\ttest -e .git/rev-cache/.old &&\n+\tgit-rev-cache fuse 2>output.err &&\n+\tgrep \"final return value: 0\" output.err &&\n+\ttest_cmp .git/rev-cache/$cache_sha1 .git/rev-cache/.old\n+'\n+\n+#make sure we can smoothly handle corrupted caches\n+test_expect_success 'corrupt slice' '\n+\techo bla >.git/rev-cache/$cache_sha1\n+'\n+\n+test_expect_success 'test rev-list traversal (limited) (corrupt slice)' '\n+\tgit-rev-list --topo-order HEAD --not HEAD~3 >list &&\n+\ttest_cmp list proper_commit_list_limited\n+'\n+\n+test_expect_success 'test rev-list traversal (unlimited) (corrupt slice)' '\n+\tgit-rev-list HEAD >list &&\n+\ttest_cmp_sorted list proper_commit_list\n+'\n+\n+test_expect_success 'corrupt index' '\n+\techo blu >.git/rev-cache/index\n+'\n+\n+test_expect_success 'test rev-list traversal (limited) (corrupt index)' '\n+\tgit-rev-list --topo-order HEAD --not HEAD~3 >list &&\n+\ttest_cmp list proper_commit_list_limited\n+'\n+\n+test_expect_success 'test rev-list traversal (unlimited) (corrupt index)' '\n+\tgit-rev-list HEAD >list &&\n+\ttest_cmp_sorted list proper_commit_list\n+'\n+\n+#test --ignore-size in fuse\n+rm .git/rev-cache/*\n+cache_sha1=`git-rev-cache add HEAD~2 2>output.err`\n+\n+test_expect_success 'make fragmented slices' '\n+\tgit-rev-cache add HEAD~1 --not HEAD~2 2>>output.err &&\n+\tgit-rev-cache add HEAD --fresh 2>>output.err &&\n+\ttest `grep \"final return value: 0\" output.err | wc -l` -eq 3\n+'\n+\n+cache_size=`wc -c .git/rev-cache/$cache_sha1 | grep -o \"[0-9]*\"`\n+test_expect_success 'test --ignore-size function in fuse' '\n+\tgit-rev-cache fuse --ignore-size=$cache_size 2>output.err &&\n+\tgrep \"final return value: 0\" output.err &&\n+\ttest -e .git/rev-cache/$cache_sha1\n+'\n+\n+test_done\n-- \ntg: (936d7dc..) t/revcache/integration (depends on: t/revcache/misc)\n"},{"id":"121377","messageId":"op.uyzwycxotdk399@sirnot","threadId":"20633","inReplyTo":"op.uyuwkuoxtdk399@sirnot.private","subject":"Re: [PATCH 5/6 (v4)] full integration of rev-cache into git, completed test suite","fromName":"Nick Edelen","fromEmail":"sirnot@gmail.com","sentAt":"2009-08-21T04:48:02Z","receivedAt":"2009-08-21T04:48:02Z","isPatch":true,"sender":{"key":"sirnot@gmail.com","avatar":null},"body":"This last patch provides a working integration of rev-cache into the revision \nwalker, along with some touch-ups:\n - integration into revision walker and list-objects\n - more fluid handling of damaged cache slices\n - numerous tests for both features from the previous patch, and the \nintegration's integrity\n\n'Integration' is rather broad -- a more detailed description follows for each \naspect:\n - rev-cache\nthe traversal mechanism is updated to handle many of the non-prune options \nrev-list does (date limiting, slop-handling, etc.), and is adjusted to allow \nfor non-fatal cache-traversal failures.\n\n - revision walker\nboth limited and unlimited traversal attempt to use the cache when possible, \nsmoothly falling back if it's not.\n\n - list-objects\nobject listing does not recurse into cached trees, and has been adjusted to \nguarantee commit-tag-tree-blob ordering.\n\nSigned-off-by: Nick Edelen <sirnot@gmail.com>\n\n---\nfixed a whitespace error.\n\n builtin-rev-cache.c       |   40 ++++++++\n list-objects.c            |   49 ++++++++--\n rev-cache.c               |  228 +++++++++++++++++++++++++++++++++++++++-----\n revision.c                |   88 ++++++++++++++---\n t/t6015-rev-cache-list.sh |  151 ++++++++++++++++++++++++++++-\n 5 files changed, 501 insertions(+), 55 deletions(-)\n\ndiff --git a/builtin-rev-cache.c b/builtin-rev-cache.c\nindex b894c54..8f41123 100644\n--- a/builtin-rev-cache.c\n+++ b/builtin-rev-cache.c\n@@ -4,6 +4,7 @@\n #include \"diff.h\"\n #include \"revision.h\"\n #include \"rev-cache.h\"\n+#include \"list-objects.h\"\n \n unsigned long default_ignore_size = 50 * 1024 * 1024; /* 50mb */\n \n@@ -78,6 +79,43 @@ static int handle_add(int argc, const char *argv[]) /* args beyond this command\n \treturn 0;\n }\n \n+static void show_commit(struct commit *commit, void *data)\n+{\n+\tprintf(\"%s\\n\", sha1_to_hex(commit->object.sha1));\n+}\n+\n+static void show_object(struct object *obj, const struct name_path *path, const char *last)\n+{\n+\tprintf(\"%s\\n\", sha1_to_hex(obj->sha1));\n+}\n+\n+static int test_rev_list(int argc, const char *argv[])\n+{\n+\tstruct rev_info revs;\n+\tunsigned int flags = 0;\n+\tint i;\n+\n+\tinit_revisions(&revs, 0);\n+\n+\tfor (i = 0; i < argc; i++) {\n+\t\tif (!strcmp(argv[i], \"--not\"))\n+\t\t\tflags ^= UNINTERESTING;\n+\t\telse if (!strcmp(argv[i], \"--objects\"))\n+\t\t\trevs.tree_objects = revs.blob_objects = 1;\n+\t\telse\n+\t\t\thandle_revision_arg(argv[i], &revs, flags, 1);\n+\t}\n+\n+\tsetup_revisions(0, 0, &revs, 0);\n+\trevs.topo_order = 1;\n+\trevs.lifo = 1;\n+\tprepare_revision_walk(&revs);\n+\n+\ttraverse_commit_list(&revs, show_commit, show_object, 0);\n+\n+\treturn 0;\n+}\n+\n static int handle_walk(int argc, const char *argv[])\n {\n \tstruct commit *commit;\n@@ -271,6 +309,8 @@ int cmd_rev_cache(int argc, const char *argv[], const char *prefix)\n \t\tr = handle_walk(argc, argv);\n \telse if (!strcmp(arg, \"index\"))\n \t\tr = handle_index(argc, argv);\n+\telse if (!strcmp(arg, \"test\"))\n+\t\tr = test_rev_list(argc, argv);\n \telse if (!strcmp(arg, \"alt\"))\n \t\tr = handle_alt(argc, argv);\n \telse\ndiff --git a/list-objects.c b/list-objects.c\nindex 8953548..821a290 100644\n--- a/list-objects.c\n+++ b/list-objects.c\n@@ -74,22 +74,33 @@ static void process_tree(struct rev_info *revs,\n \t\tdie(\"bad tree object\");\n \tif (obj->flags & (UNINTERESTING | SEEN))\n \t\treturn;\n-\tif (parse_tree(tree) < 0)\n-\t\tdie(\"bad tree object %s\", sha1_to_hex(obj->sha1));\n+\n \tobj->flags |= SEEN;\n \tshow(obj, path, name);\n+\tif (obj->flags & FACE_VALUE)\n+\t\treturn;\n+\n+\t/* traverse_commit_list is only used for enumeration purposes,\n+\t * ie. nothing relies on trees being parsed in this routine */\n+\tif (parse_tree(tree) < 0)\n+\t\tdie(\"bad tree object %s\", sha1_to_hex(obj->sha1));\n+\n \tme.up = path;\n \tme.elem = name;\n \tme.elem_len = strlen(name);\n-\n \tinit_tree_desc(&desc, tree->buffer, tree->size);\n \n \twhile (tree_entry(&desc, &entry)) {\n-\t\tif (S_ISDIR(entry.mode))\n+\t\tif (S_ISDIR(entry.mode)) {\n+\t\t\tstruct tree *subtree = lookup_tree(entry.sha1);\n+\t\t\tif (!subtree)\n+\t\t\t\tcontinue;\n+\n+\t\t\tsubtree->object.flags &= ~FACE_VALUE;\n \t\t\tprocess_tree(revs,\n-\t\t\t\t     lookup_tree(entry.sha1),\n+\t\t\t\t     subtree,\n \t\t\t\t     show, &me, entry.path);\n-\t\telse if (S_ISGITLINK(entry.mode))\n+\t\t} else if (S_ISGITLINK(entry.mode))\n \t\t\tprocess_gitlink(revs, entry.sha1,\n \t\t\t\t\tshow, &me, entry.path);\n \t\telse\n@@ -136,6 +147,7 @@ void mark_edges_uninteresting(struct commit_list *list,\n \n static void add_pending_tree(struct rev_info *revs, struct tree *tree)\n {\n+\ttree->object.flags &= ~FACE_VALUE;\n \tadd_pending_object(revs, &tree->object, \"\");\n }\n \n@@ -146,17 +158,27 @@ void traverse_commit_list(struct rev_info *revs,\n {\n \tint i;\n \tstruct commit *commit;\n+\tenum object_type what = OBJ_TAG;\n+\tchar face_value = 0;\n \n \twhile ((commit = get_revision(revs)) != NULL) {\n-\t\tadd_pending_tree(revs, commit->tree);\n+\t\tif (!(commit->object.flags & FACE_VALUE))\n+\t\t\tadd_pending_tree(revs, commit->tree);\n+\t\telse\n+\t\t\tface_value = 1;\n \t\tshow_commit(commit, data);\n \t}\n+\n+loop_objects:\n \tfor (i = 0; i < revs->pending.nr; i++) {\n \t\tstruct object_array_entry *pending = revs->pending.objects + i;\n \t\tstruct object *obj = pending->item;\n \t\tconst char *name = pending->name;\n \t\tif (obj->flags & (UNINTERESTING | SEEN))\n \t\t\tcontinue;\n+\t\tif (obj->type != what && face_value)\n+\t\t\tcontinue;\n+\n \t\tif (obj->type == OBJ_TAG) {\n \t\t\tobj->flags |= SEEN;\n \t\t\tshow_object(obj, NULL, name);\n@@ -175,6 +197,19 @@ void traverse_commit_list(struct rev_info *revs,\n \t\tdie(\"unknown pending object %s (%s)\",\n \t\t    sha1_to_hex(obj->sha1), name);\n \t}\n+\tif (face_value) {\n+\t\tswitch (what) {\n+\t\tcase OBJ_TAG :\n+\t\t\twhat = OBJ_TREE;\n+\t\t\tgoto loop_objects;\n+\t\tcase OBJ_TREE :\n+\t\t\twhat = OBJ_BLOB;\n+\t\t\tgoto loop_objects;\n+\t\tdefault :\n+\t\t\tbreak;\n+\t\t}\n+\t}\n+\n \tif (revs->pending.nr) {\n \t\tfree(revs->pending.objects);\n \t\trevs->pending.nr = 0;\ndiff --git a/rev-cache.c b/rev-cache.c\nindex 8ca97d3..04a9b02 100644\n--- a/rev-cache.c\n+++ b/rev-cache.c\n@@ -11,6 +11,12 @@\n #include \"run-command.h\"\n #include \"string-list.h\"\n \n+\n+struct bad_slice {\n+\tunsigned char sha1[20];\n+\tstruct bad_slice *next;\n+};\n+\n struct cache_slice_pointer {\n \tchar signature[8]; /* REVCOPTR */\n \tchar version;\n@@ -23,8 +29,9 @@ static uint32_t fanout[0xff + 2];\n static unsigned char *idx_map;\n static int idx_size;\n static struct rc_index_header idx_head;\n+static char no_idx, add_to_pending;\n+static struct bad_slice *bad_slices;\n static unsigned char *idx_caches;\n-static char no_idx;\n \n static struct strbuf *acc_buffer;\n \n@@ -121,6 +128,30 @@ struct rc_object_entry_ondisk *to_disked_rc_object_entry(struct rc_object_entry\n \treturn dst;\n }\n \n+static void mark_bad_slice(unsigned char *sha1)\n+{\n+\tstruct bad_slice *bad;\n+\n+\tbad = xcalloc(sizeof(struct bad_slice), 1);\n+\thashcpy(bad->sha1, sha1);\n+\n+\tbad->next = bad_slices;\n+\tbad_slices = bad;\n+}\n+\n+static int is_bad_slice(unsigned char *sha1)\n+{\n+\tstruct bad_slice *bad = bad_slices;\n+\n+\twhile (bad) {\n+\t\tif (!hashcmp(bad->sha1, sha1))\n+\t\t\treturn 1;\n+\t\tbad = bad->next;\n+\t}\n+\n+\treturn 0;\n+}\n+\n static int get_index_head(unsigned char *map, int len, struct rc_index_header *head, uint32_t *fanout, unsigned char **caches)\n {\n \tstruct rc_index_header whead;\n@@ -246,6 +277,7 @@ static struct rc_index_entry *search_index(unsigned char *sha1)\n unsigned char *get_cache_slice(struct commit *commit)\n {\n \tstruct rc_index_entry *ie;\n+\tunsigned char *sha1;\n \n \tif (!idx_map) {\n \t\tif (no_idx)\n@@ -257,8 +289,13 @@ unsigned char *get_cache_slice(struct commit *commit)\n \t\treturn 0;\n \n \tie = search_index(commit->object.sha1);\n-\tif (ie && ie->cache_index < idx_head.cache_nr)\n-\t\treturn idx_caches + ie->cache_index * 20;\n+\tif (ie && ie->cache_index < idx_head.cache_nr) {\n+\t\tsha1 = idx_caches + ie->cache_index * 20;\n+\n+\t\tif (is_bad_slice(sha1))\n+\t\t\treturn 0;\n+\t\treturn sha1;\n+\t}\n \n \treturn 0;\n }\n@@ -268,6 +305,20 @@ unsigned char *get_cache_slice(struct commit *commit)\n \n static unsigned long decode_size(unsigned char *str, int len);\n \n+/* on failure */\n+static void restore_commit(struct commit *commit)\n+{\n+\tcommit->object.flags &= ~(ADDED | SEEN | FACE_VALUE);\n+\n+\tif (!commit->object.parsed) {\n+\t\twhile (pop_commit(&commit->parents))\n+\t\t\t;\n+\n+\t\tparse_commit(commit);\n+\t}\n+\n+}\n+\n static void handle_noncommit(struct rev_info *revs, struct commit *commit, unsigned char *ptr, struct rc_object_entry *entry)\n {\n \tstruct blob *blob;\n@@ -307,23 +358,27 @@ static void handle_noncommit(struct rev_info *revs, struct commit *commit, unsig\n \t}\n \n \tobj->flags |= FACE_VALUE;\n-\tadd_pending_object(revs, obj, \"\");\n+\tif (add_to_pending)\n+\t\tadd_pending_object(revs, obj, \"\");\n }\n \n-static int setup_traversal(struct rc_slice_header *head, unsigned char *map, struct commit *commit, struct commit_list **work)\n+static int setup_traversal(struct rc_slice_header *head, unsigned char *map, struct commit *commit, struct commit_list **work,\n+\tstruct commit_list **unwork, int *ipath_nr, int *upath_nr, char *ioutside)\n {\n \tstruct rc_index_entry *iep;\n \tstruct rc_object_entry *oep;\n \tstruct commit_list *prev, *wp, **wpp;\n \tint retval;\n \n-\tiep = search_index(commit->object.sha1), 0;\n+\tiep = search_index(commit->object.sha1);\n \toep = RC_OBTAIN_OBJECT_ENTRY(map + iep->pos);\n+\tif (commit->object.flags & UNINTERESTING) {\n+\t\t++*upath_nr;\n+\t\toep->uninteresting = 1;\n+\t} else\n+\t\t++*ipath_nr;\n \n-\t/* the .uniniteresting bit isn't strictly necessary, as we check the object during traversal as well,\n-\t * but we might as well initialize it while we're at it */\n \toep->include = 1;\n-\toep->uninteresting = !!(commit->object.flags & UNINTERESTING);\n \tto_disked_rc_object_entry(oep, (struct rc_object_entry_ondisk *)(map + iep->pos));\n \tretval = iep->pos;\n \n@@ -338,6 +393,10 @@ static int setup_traversal(struct rc_slice_header *head, unsigned char *map, str\n \t\t/* is this in our cache slice? */\n \t\tiep = search_index(obj->sha1);\n \t\tif (!iep || hashcmp(idx_caches + iep->cache_index * 20, head->sha1)) {\n+\t\t\t/* there are interesing objects outside the slice */\n+\t\t\tif (!(obj->flags & UNINTERESTING))\n+\t\t\t\t*ioutside = 1;\n+\n \t\t\tprev = wp;\n \t\t\twp = wp->next;\n \t\t\twpp = &wp;\n@@ -354,11 +413,20 @@ static int setup_traversal(struct rc_slice_header *head, unsigned char *map, str\n \t\toep->uninteresting = !!(obj->flags & UNINTERESTING);\n \t\tto_disked_rc_object_entry(oep, (struct rc_object_entry_ondisk *)(map + iep->pos));\n \n+\t\t/* count even if not in slice so we can stop enumerating if possible */\n+\t\tif (obj->flags & UNINTERESTING)\n+\t\t\t++*upath_nr;\n+\t\telse\n+\t\t\t++*ipath_nr;\n+\n \t\t/* remove from work list */\n \t\tco = pop_commit(wpp);\n \t\twp = *wpp;\n \t\tif (prev)\n \t\t\tprev->next = wp;\n+\n+\t\t/* ...and store in temp list so we can restore work on failure */\n+\t\tcommit_list_insert(co, unwork);\n \t}\n \n \treturn retval;\n@@ -375,13 +443,18 @@ static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *m\n \tunsigned long *date_so_far, int *slop_so_far,\n \tstruct commit_list ***queue, struct commit_list **work)\n {\n-\tstruct commit_list *insert_cache = 0;\n+\tstruct commit_list *insert_cache = 0, *myq = 0, **myqp = &myq, *mywork = 0, **myworkp = &mywork, *unwork = 0;\n \tstruct commit **last_objects, *co;\n-\tint i, total_path_nr = head->path_nr, retval = -1;\n-\tchar consume_children = 0;\n+\tunsigned long date = date_so_far ? *date_so_far : ~0ul;\n+\tint i, ipath_nr = 0, upath_nr = 0, orig_obj_nr = 0,\n+\t\ttotal_path_nr = head->path_nr, retval = -1, slop = slop_so_far ? *slop_so_far : SLOP;\n+\tchar consume_children = 0, ioutside = 0;\n \tunsigned char *paths;\n \n-\ti = setup_traversal(head, map, commit, work);\n+\t/* take note in case we need to regress */\n+\torig_obj_nr = revs->pending.nr;\n+\n+\ti = setup_traversal(head, map, commit, work, &unwork, &ipath_nr, &upath_nr, &ioutside);\n \tif (i < 0)\n \t\treturn -1;\n \n@@ -429,6 +502,7 @@ static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *m\n \n \t\tif ((paths[path] & IPATH) && (paths[path] & UPATH)) {\n \t\t\tpaths[path] = UPATH;\n+\t\t\tipath_nr--;\n \n \t\t\t/* mark edge */\n \t\t\tif (last_objects[path]) {\n@@ -439,6 +513,7 @@ static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *m\n \t\t\t\tlast_objects[path]->object.flags &= ~FACE_VALUE;\n \t\t\t\tlast_objects[path] = 0;\n \t\t\t}\n+\t\t\tobj->flags |= BOUNDARY;\n \t\t}\n \n \t\t/* now we gotta re-assess the whole interesting thing... */\n@@ -462,8 +537,10 @@ static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *m\n \t\t\t\t\t\tlast_objects[p]->object.flags &= ~FACE_VALUE;\n \t\t\t\t\t\tlast_objects[p] = 0;\n \t\t\t\t\t}\n-\t\t\t\t} else if (last_objects[p] && !last_objects[p]->object.parsed)\n+\t\t\t\t\tobj->flags |= BOUNDARY;\n+\t\t\t\t} else if (last_objects[p] && !last_objects[p]->object.parsed) {\n \t\t\t\t\tcommit_list_insert(co, &last_objects[p]->parents);\n+\t\t\t\t}\n \n \t\t\t\t/* can't close a merge path until all are parents have been encountered */\n \t\t\t\tif (GET_COUNT(paths[p])) {\n@@ -473,14 +550,33 @@ static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *m\n \t\t\t\t\t\tcontinue;\n \t\t\t\t}\n \n+\t\t\t\tif (paths[p] & IPATH)\n+\t\t\t\t\tipath_nr--;\n+\t\t\t\telse\n+\t\t\t\t\tupath_nr--;\n+\n \t\t\t\tpaths[p] = 0;\n \t\t\t\tlast_objects[p] = 0;\n \t\t\t}\n \t\t}\n \n \t\t/* make topo relations */\n-\t\tif (last_objects[path] && !last_objects[path]->object.parsed)\n+\t\tif (last_objects[path] && !last_objects[path]->object.parsed) {\n \t\t\tcommit_list_insert(co, &last_objects[path]->parents);\n+\t\t}\n+\n+\t\t/* we've been here already */\n+\t\tif (obj->flags & ADDED) {\n+\t\t\tif (entry->uninteresting && !(obj->flags & UNINTERESTING)) {\n+\t\t\t\tobj->flags |= UNINTERESTING;\n+\t\t\t\tmark_parents_uninteresting(co);\n+\t\t\t\tupath_nr--;\n+\t\t\t} else if (!entry->uninteresting)\n+\t\t\t\tipath_nr--;\n+\n+\t\t\tpaths[path] = 0;\n+\t\t\tcontinue;\n+\t\t}\n \n \t\t/* initialize commit */\n \t\tif (!entry->is_end) {\n@@ -493,24 +589,51 @@ static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *m\n \n \t\tif (entry->uninteresting)\n \t\t\tobj->flags |= UNINTERESTING;\n+\t\telse if (co->date < date)\n+\t\t\tdate = co->date;\n \n \t\t/* we need to know what the edges are */\n \t\tlast_objects[path] = co;\n \n \t\t/* add to list */\n-\t\tif (!(obj->flags & UNINTERESTING) || revs->show_all) {\n-\t\t\tif (entry->is_end)\n-\t\t\t\tinsert_by_date_cached(co, work, insert_cache, &insert_cache);\n-\t\t\telse\n-\t\t\t\t*queue = &commit_list_insert(co, *queue)->next;\n+\t\tif (slop && !(revs->min_age != -1 && co->date > revs->min_age)) {\n+\n+\t\t\tif (!(obj->flags & UNINTERESTING) || revs->show_all) {\n+\t\t\t\tif (entry->is_end)\n+\t\t\t\t\tmyworkp = &commit_list_insert(co, myworkp)->next;\n+\t\t\t\telse\n+\t\t\t\t\tmyqp = &commit_list_insert(co, myqp)->next;\n+\n+\t\t\t\t/* add children to list as well */\n+\t\t\t\tif (obj->flags & UNINTERESTING)\n+\t\t\t\t\tconsume_children = 0;\n+\t\t\t\telse\n+\t\t\t\t\tconsume_children = 1;\n+\t\t\t}\n \n-\t\t\t/* add children to list as well */\n-\t\t\tif (obj->flags & UNINTERESTING)\n-\t\t\t\tconsume_children = 0;\n-\t\t\telse\n-\t\t\t\tconsume_children = 1;\n \t\t}\n \n+\t\t/* should we continue? */\n+\t\tif (!slop) {\n+\t\t\tif (!upath_nr) {\n+\t\t\t\tbreak;\n+\t\t\t} else if (ioutside || revs->show_all) {\n+\t\t\t\t/* pass it back to rev-list\n+\t\t\t\t * we purposely ignore everything outside this cache, so we don't needlessly traverse the whole\n+\t\t\t\t * thing on uninteresting, but that does mean that we may need to bounce back\n+\t\t\t\t * and forth a few times with rev-list */\n+\t\t\t\tmyworkp = &commit_list_insert(co, myworkp)->next;\n+\n+\t\t\t\tpaths[path] = 0;\n+\t\t\t\tupath_nr--;\n+\t\t\t} else {\n+\t\t\t\tbreak;\n+\t\t\t}\n+\t\t} else if (!ipath_nr && co->date <= date)\n+\t\t\tslop--;\n+\t\telse\n+\t\t\tslop = SLOP;\n+\n \t\t/* open parents */\n \t\tif (entry->merge_nr) {\n \t\t\tint j, off = index + sizeof(struct rc_object_entry_ondisk);\n@@ -525,6 +648,11 @@ static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *m\n \t\t\t\tif (paths[p] & flag)\n \t\t\t\t\tcontinue;\n \n+\t\t\t\tif (flag == IPATH)\n+\t\t\t\t\tipath_nr++;\n+\t\t\t\telse\n+\t\t\t\t\tupath_nr++;\n+\n \t\t\t\tpaths[p] |= flag;\n \t\t\t}\n \n@@ -534,12 +662,55 @@ static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *m\n \n \t}\n \n+\tif (date_so_far)\n+\t\t*date_so_far = date;\n+\tif (slop_so_far)\n+\t\t*slop_so_far = slop;\n \tretval = 0;\n \n+\t/* success: attach to given lists */\n+\tif (myqp != &myq) {\n+\t\t**queue = myq;\n+\t\t*queue = myqp;\n+\t}\n+\n+\twhile ((co = pop_commit(&mywork)) != 0) {\n+\t\tinsert_by_date_cached(co, work, insert_cache, &insert_cache);\n+\t}\n+\n+\t/* free backup */\n+\twhile (pop_commit(&unwork))\n+\t\t;\n+\n end:\n \tfree(paths);\n \tfree(last_objects);\n \n+\t/* failure: restore work to previous condition\n+\t * (cache corruption should *not* be fatal) */\n+\tif (retval) {\n+\t\twhile ((co = pop_commit(&unwork)) != 0) {\n+\t\t\trestore_commit(co);\n+\t\t\tco->object.flags |= SEEN;\n+\t\t\tinsert_by_date(co, work);\n+\t\t}\n+\n+\t\t/* free lists */\n+\t\twhile ((co = pop_commit(&myq)) != 0)\n+\t\t\trestore_commit(co);\n+\n+\t\twhile ((co = pop_commit(&mywork)) != 0)\n+\t\t\trestore_commit(co);\n+\n+\t\t/* truncate object array */\n+\t\tfor (i = orig_obj_nr; i < revs->pending.nr; i++) {\n+\t\t\tstruct object *obj = revs->pending.objects[i].item;\n+\n+\t\t\tobj->flags &= ~FACE_VALUE;\n+\t\t}\n+\t\trevs->pending.nr = orig_obj_nr;\n+\t}\n+\n \treturn retval;\n }\n \n@@ -630,6 +801,7 @@ int traverse_cache_slice(struct rev_info *revs,\n \n \t/* load options */\n \trci = &revs->rev_cache_info;\n+\tadd_to_pending = rci->add_to_pending;\n \n \tmemset(&head, 0, sizeof(struct rc_slice_header));\n \n@@ -653,6 +825,10 @@ end:\n \tif (fd != -1)\n \t\tclose(fd);\n \n+\t/* remember this! */\n+\tif (retval)\n+\t\tmark_bad_slice(cache_sha1);\n+\n \treturn retval;\n }\n \ndiff --git a/revision.c b/revision.c\nindex 485bf72..4640536 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -12,6 +12,7 @@\n #include \"patch-ids.h\"\n #include \"decorate.h\"\n #include \"log-tree.h\"\n+#include \"rev-cache.h\"\n \n volatile show_early_output_fn_t show_early_output;\n \n@@ -638,6 +639,8 @@ static int limit_list(struct rev_info *revs)\n \tstruct commit_list *list = revs->commits;\n \tstruct commit_list *newlist = NULL;\n \tstruct commit_list **p = &newlist;\n+\tunsigned char *cache_sha1;\n+\tchar used_cache;\n \n \twhile (list) {\n \t\tstruct commit_list *entry = list;\n@@ -650,24 +653,39 @@ static int limit_list(struct rev_info *revs)\n \n \t\tif (revs->max_age != -1 && (commit->date < revs->max_age))\n \t\t\tobj->flags |= UNINTERESTING;\n-\t\tif (add_parents_to_list(revs, commit, &list, NULL) < 0)\n-\t\t\treturn -1;\n-\t\tif (obj->flags & UNINTERESTING) {\n-\t\t\tmark_parents_uninteresting(commit);\n-\t\t\tif (revs->show_all)\n-\t\t\t\tp = &commit_list_insert(commit, p)->next;\n-\t\t\tslop = still_interesting(list, date, slop);\n-\t\t\tif (slop)\n+\n+\t\t/* rev-cache to the rescue!!! */\n+\t\tused_cache = 0;\n+\t\tif (!revs->dont_cache_me && !(obj->flags & ADDED)) {\n+\t\t\tcache_sha1 = get_cache_slice(commit);\n+\t\t\tif (cache_sha1) {\n+\t\t\t\tif (traverse_cache_slice(revs, cache_sha1, commit, &date, &slop, &p, &list) < 0)\n+\t\t\t\t\tused_cache = 0;\n+\t\t\t\telse\n+\t\t\t\t\tused_cache = 1;\n+\t\t\t}\n+\t\t}\n+\n+\t\tif (!used_cache) {\n+\t\t\tif (add_parents_to_list(revs, commit, &list, NULL) < 0)\n+\t\t\t\treturn -1;\n+\t\t\tif (obj->flags & UNINTERESTING) {\n+\t\t\t\tmark_parents_uninteresting(commit); /* ME: why? */\n+\t\t\t\tif (revs->show_all)\n+\t\t\t\t\tp = &commit_list_insert(commit, p)->next;\n+\t\t\t\tslop = still_interesting(list, date, slop);\n+\t\t\t\tif (slop > 0)\n+\t\t\t\t\tcontinue;\n+\t\t\t\t/* If showing all, add the whole pending list to the end */\n+\t\t\t\tif (revs->show_all)\n+\t\t\t\t\t*p = list;\n+\t\t\t\tbreak;\n+\t\t\t}\n+\t\t\tif (revs->min_age != -1 && (commit->date > revs->min_age))\n \t\t\t\tcontinue;\n-\t\t\t/* If showing all, add the whole pending list to the end */\n-\t\t\tif (revs->show_all)\n-\t\t\t\t*p = list;\n-\t\t\tbreak;\n+\t\t\tdate = commit->date;\n+\t\t\tp = &commit_list_insert(commit, p)->next;\n \t\t}\n-\t\tif (revs->min_age != -1 && (commit->date > revs->min_age))\n-\t\t\tcontinue;\n-\t\tdate = commit->date;\n-\t\tp = &commit_list_insert(commit, p)->next;\n \n \t\tshow = show_early_output;\n \t\tif (!show)\n@@ -813,6 +831,8 @@ void init_revisions(struct rev_info *revs, const char *prefix)\n \t\trevs->diffopt.prefix = prefix;\n \t\trevs->diffopt.prefix_length = strlen(prefix);\n \t}\n+\n+\tinit_rev_cache_info(&revs->rev_cache_info);\n }\n \n static void add_pending_commit_list(struct rev_info *revs,\n@@ -1372,6 +1392,11 @@ int setup_revisions(int argc, const char **argv, struct rev_info *revs, const ch\n \tif (revs->reflog_info && revs->graph)\n \t\tdie(\"cannot combine --walk-reflogs with --graph\");\n \n+\t/* limits on caching\n+\t * todo: implement this functionality */\n+\tif (revs->prune || revs->diff)\n+\t\trevs->dont_cache_me = 1;\n+\n \treturn left;\n }\n \n@@ -1654,6 +1679,8 @@ static int commit_match(struct commit *commit, struct rev_info *opt)\n {\n \tif (!opt->grep_filter.pattern_list)\n \t\treturn 1;\n+\tif (!commit->object.parsed)\n+\t\tparse_commit(commit);\n \treturn grep_buffer(&opt->grep_filter,\n \t\t\t   NULL, /* we say nothing, not even filename */\n \t\t\t   commit->buffer, strlen(commit->buffer));\n@@ -1706,6 +1733,7 @@ static struct commit *get_revision_1(struct rev_info *revs)\n \tdo {\n \t\tstruct commit_list *entry = revs->commits;\n \t\tstruct commit *commit = entry->item;\n+\t\tstruct object *obj = &commit->object;\n \n \t\trevs->commits = entry->next;\n \t\tfree(entry);\n@@ -1722,11 +1750,39 @@ static struct commit *get_revision_1(struct rev_info *revs)\n \t\t\tif (revs->max_age != -1 &&\n \t\t\t    (commit->date < revs->max_age))\n \t\t\t\tcontinue;\n+\n+\t\t\tif (!revs->dont_cache_me) {\n+\t\t\t\tstruct commit_list *queue = 0, **queuep = &queue;\n+\t\t\t\tunsigned char *cache_sha1;\n+\n+\t\t\t\tif (obj->flags & ADDED)\n+\t\t\t\t\tgoto skip_parenting;\n+\n+\t\t\t\tcache_sha1 = get_cache_slice(commit);\n+\t\t\t\tif (cache_sha1) {\n+\t\t\t\t\tif (!traverse_cache_slice(revs, cache_sha1, commit, 0, 0, &queuep, &revs->commits)) {\n+\t\t\t\t\t\tstruct commit_list *work = revs->commits;\n+\n+\t\t\t\t\t\t/* attach queue to end of ->commits */\n+\t\t\t\t\t\twhile (work && work->next)\n+\t\t\t\t\t\t\twork = work->next;\n+\n+\t\t\t\t\t\tif (work)\n+\t\t\t\t\t\t\twork->next = queue;\n+\t\t\t\t\t\telse\n+\t\t\t\t\t\t\trevs->commits = queue;\n+\n+\t\t\t\t\t\tgoto skip_parenting;\n+\t\t\t\t\t}\n+\t\t\t\t}\n+\t\t\t}\n+\n \t\t\tif (add_parents_to_list(revs, commit, &revs->commits, NULL) < 0)\n \t\t\t\tdie(\"Failed to traverse parents of commit %s\",\n \t\t\t\t    sha1_to_hex(commit->object.sha1));\n \t\t}\n \n+skip_parenting:\n \t\tswitch (simplify_commit(revs, commit)) {\n \t\tcase commit_ignore:\n \t\t\tcontinue;\ndiff --git a/t/t6015-rev-cache-list.sh b/t/t6015-rev-cache-list.sh\nindex dc0fc07..f2e34b1 100755\n--- a/t/t6015-rev-cache-list.sh\n+++ b/t/t6015-rev-cache-list.sh\n@@ -38,6 +38,7 @@ test_expect_success 'init repo' '\n \tgit add . &&\n \tgit commit -m \"omg\" &&\n \n+\tsleep 2 &&\n \tgit branch b4 &&\n \tgit checkout b4 &&\n \techo shazam >file8 &&\n@@ -46,7 +47,7 @@ test_expect_success 'init repo' '\n \tgit merge -m \"merge b2\" b2 &&\n \n \techo bam >smoke/pipe &&\n-\tgit add .\n+\tgit add . &&\n \tgit commit -m \"bam\" &&\n \n \tgit checkout master &&\n@@ -71,18 +72,26 @@ test_expect_success 'init repo' '\n \tgit add . &&\n \tgit commit -m \"lol\" &&\n \n+\tsleep 2 &&\n \tgit checkout master &&\n \tgit merge -m \"triple merge\" b1 b11 &&\n \tgit rm -r d1 &&\n+\tsleep 2 &&\n \tgit commit -a -m \"oh noes\"\n '\n \n-git-rev-list HEAD --not HEAD~3 >proper_commit_list_limited\n-git-rev-list HEAD >proper_commit_list\n-git-rev-list HEAD --objects >proper_object_list\n+max_date=`git-rev-list --timestamp HEAD~1 --max-count=1 | grep -e \"^[0-9]*\" -o`\n+min_date=`git-rev-list --timestamp b4 --max-count=1 | grep -e \"^[0-9]*\" -o`\n+\n+git-rev-list --topo-order HEAD --not HEAD~3 >proper_commit_list_limited\n+git-rev-list --topo-order HEAD --not HEAD~2 >proper_commit_list_limited2\n+git-rev-list --topo-order HEAD >proper_commit_list\n+git-rev-list --objects HEAD >proper_object_list\n+git-rev-list HEAD --max-age=$min_date --min-age=$max_date >proper_list_date_limited\n+\n+cache_sha1=`git-rev-cache add HEAD 2>output.err`\n \n test_expect_success 'make cache slice' '\n-\tgit-rev-cache add HEAD 2>output.err &&\n \tgrep \"final return value: 0\" output.err\n '\n \n@@ -102,11 +111,141 @@ test_expect_success 'test rev-caches walker directly (unlimited)' '\n \ttest_cmp_sorted list proper_commit_list\n '\n \n+test_expect_success 'test rev-list traversal (limited)' '\n+\tgit-rev-list HEAD --not HEAD~3 >list &&\n+\ttest_cmp list proper_commit_list_limited\n+'\n+\n+test_expect_success 'test rev-list traversal (unlimited)' '\n+\tgit-rev-list HEAD >list &&\n+\ttest_cmp list proper_commit_list\n+'\n+\n #do the same for objects\n test_expect_success 'test rev-caches walker with objects' '\n \tgit-rev-cache walk --objects HEAD >list &&\n \ttest_cmp_sorted list proper_object_list\n '\n \n-test_done\n+test_expect_success 'test rev-list with objects (topo order)' '\n+\tgit-rev-list --topo-order --objects HEAD >list &&\n+\ttest_cmp_sorted list proper_object_list\n+'\n+\n+test_expect_success 'test rev-list with objects (no order)' '\n+\tgit-rev-list --objects HEAD >list &&\n+\ttest_cmp_sorted list proper_object_list\n+'\n+\n+#verify age limiting\n+test_expect_success 'test rev-list date limiting (topo order)' '\n+\tgit-rev-list --topo-order --max-age=$min_date --min-age=$max_date HEAD >list &&\n+\ttest_cmp_sorted list proper_list_date_limited\n+'\n+\n+test_expect_success 'test rev-list date limiting (no order)' '\n+\tgit-rev-list --max-age=$min_date --min-age=$max_date HEAD >list &&\n+\ttest_cmp_sorted list proper_list_date_limited\n+'\n+\n+#check partial cache slice\n+test_expect_success 'saving old cache and generating partial slice' '\n+\tcp \".git/rev-cache/$cache_sha1\" .git/rev-cache/.old &&\n+\trm \".git/rev-cache/$cache_sha1\" .git/rev-cache/index &&\n+\n+\tgit-rev-cache add HEAD~2 2>output.err &&\n+\tgrep \"final return value: 0\" output.err\n+'\n+\n+test_expect_success 'rev-list with wholly interesting partial slice' '\n+\tgit-rev-list --topo-order HEAD >list &&\n+\ttest_cmp list proper_commit_list\n+'\n+\n+test_expect_success 'rev-list with partly uninteresting partial slice' '\n+\tgit-rev-list --topo-order HEAD --not HEAD~3 >list &&\n+\ttest_cmp list proper_commit_list_limited\n+'\n+\n+test_expect_success 'rev-list with wholly uninteresting partial slice' '\n+\tgit-rev-list --topo-order HEAD --not HEAD~2 >list &&\n+\ttest_cmp list proper_commit_list_limited2\n+'\n+\n+#try out index generation and fuse (note that --all == HEAD in this case)\n+#probably should make a test for that too...\n+test_expect_success 'test (non-)fusion of one slice' '\n+\tgit-rev-cache fuse >output.err &&\n+\tgrep \"nothing to fuse\" output.err\n+'\n \n+test_expect_success 'make fresh slice' '\n+\tgit-rev-cache add --all --fresh 2>output.err &&\n+\tgrep \"final return value: 0\" output.err\n+'\n+\n+test_expect_success 'check dual slices' '\n+\tgit-rev-list --topo-order HEAD~2 HEAD >list &&\n+\ttest_cmp list proper_commit_list\n+'\n+\n+test_expect_success 'regenerate index' '\n+\trm .git/rev-cache/index &&\n+\tgit-rev-cache index 2>output.err &&\n+\tgrep \"final return value: 0\" output.err\n+'\n+\n+test_expect_success 'fuse slices' '\n+\ttest -e .git/rev-cache/.old &&\n+\tgit-rev-cache fuse 2>output.err &&\n+\tgrep \"final return value: 0\" output.err &&\n+\ttest_cmp .git/rev-cache/$cache_sha1 .git/rev-cache/.old\n+'\n+\n+#make sure we can smoothly handle corrupted caches\n+test_expect_success 'corrupt slice' '\n+\techo bla >.git/rev-cache/$cache_sha1\n+'\n+\n+test_expect_success 'test rev-list traversal (limited) (corrupt slice)' '\n+\tgit-rev-list --topo-order HEAD --not HEAD~3 >list &&\n+\ttest_cmp list proper_commit_list_limited\n+'\n+\n+test_expect_success 'test rev-list traversal (unlimited) (corrupt slice)' '\n+\tgit-rev-list HEAD >list &&\n+\ttest_cmp_sorted list proper_commit_list\n+'\n+\n+test_expect_success 'corrupt index' '\n+\techo blu >.git/rev-cache/index\n+'\n+\n+test_expect_success 'test rev-list traversal (limited) (corrupt index)' '\n+\tgit-rev-list --topo-order HEAD --not HEAD~3 >list &&\n+\ttest_cmp list proper_commit_list_limited\n+'\n+\n+test_expect_success 'test rev-list traversal (unlimited) (corrupt index)' '\n+\tgit-rev-list HEAD >list &&\n+\ttest_cmp_sorted list proper_commit_list\n+'\n+\n+#test --ignore-size in fuse\n+rm .git/rev-cache/*\n+cache_sha1=`git-rev-cache add HEAD~2 2>output.err`\n+\n+test_expect_success 'make fragmented slices' '\n+\tgit-rev-cache add HEAD~1 --not HEAD~2 2>>output.err &&\n+\tgit-rev-cache add HEAD --fresh 2>>output.err &&\n+\ttest `grep \"final return value: 0\" output.err | wc -l` -eq 3\n+'\n+\n+cache_size=`wc -c .git/rev-cache/$cache_sha1 | grep -o \"[0-9]*\"`\n+test_expect_success 'test --ignore-size function in fuse' '\n+\tgit-rev-cache fuse --ignore-size=$cache_size 2>output.err &&\n+\tgrep \"final return value: 0\" output.err &&\n+\ttest -e .git/rev-cache/$cache_sha1\n+'\n+\n+test_done\n-- \ntg: (146af28..) t/revcache/integration (depends on: t/revcache/misc)\n"},{"id":"122626","messageId":"op.uzv4covmtdk399@sirnot.private","threadId":"20633","inReplyTo":"op.uyzwycxotdk399@sirnot","subject":"Re: [PATCH 5/6 (v4)] full integration of rev-cache into git, completed test suite","fromName":"Nick Edelen","fromEmail":"sirnot@gmail.com","sentAt":"2009-09-07T14:11:02Z","receivedAt":"2009-09-07T14:11:02Z","isPatch":true,"sender":{"key":"sirnot@gmail.com","avatar":null},"body":"This last patch provides a working integration of rev-cache into the revision \nwalker, along with some touch-ups:\n - integration into revision walker and list-objects\n - tweak of object generation\n - more fluid handling of damaged cache slices\n - numerous tests for both features from the previous patch, and the \nintegration's integrity\n\n'Integration' is rather broad -- a more detailed description follows for each \naspect:\n - rev-cache\nthe traversal mechanism is updated to handle many of the non-prune options \nrev-list does (date limiting, slop-handling, etc.), and is adjusted to allow \nfor non-fatal cache-traversal failures.\n\n - revision walker\nboth limited and unlimited traversal attempt to use the cache when possible, \nsmoothly falling back if it's not.\n\n - list-objects\nobject listing does not recurse into cached trees, and has been adjusted to \nguarantee commit-tag-tree-blob ordering.\n\nSigned-off-by: Nick Edelen <sirnot@gmail.com>\n\n---\nFixed issue with upload-pack test.  It was a simple matter of event ordering\n(printing trees before/after attempting to parse them).\n\n builtin-rev-cache.c       |   40 ++++++++\n list-objects.c            |   46 ++++++++-\n rev-cache.c               |  230 +++++++++++++++++++++++++++++++++++++++-----\n revision.c                |   88 ++++++++++++++---\n t/t6017-rev-cache-list.sh |  151 ++++++++++++++++++++++++++++-\n 5 files changed, 501 insertions(+), 54 deletions(-)\n\ndiff --git a/builtin-rev-cache.c b/builtin-rev-cache.c\nindex b894c54..8f41123 100644\n--- a/builtin-rev-cache.c\n+++ b/builtin-rev-cache.c\n@@ -4,6 +4,7 @@\n #include \"diff.h\"\n #include \"revision.h\"\n #include \"rev-cache.h\"\n+#include \"list-objects.h\"\n \n unsigned long default_ignore_size = 50 * 1024 * 1024; /* 50mb */\n \n@@ -78,6 +79,43 @@ static int handle_add(int argc, const char *argv[]) /* args beyond this command\n \treturn 0;\n }\n \n+static void show_commit(struct commit *commit, void *data)\n+{\n+\tprintf(\"%s\\n\", sha1_to_hex(commit->object.sha1));\n+}\n+\n+static void show_object(struct object *obj, const struct name_path *path, const char *last)\n+{\n+\tprintf(\"%s\\n\", sha1_to_hex(obj->sha1));\n+}\n+\n+static int test_rev_list(int argc, const char *argv[])\n+{\n+\tstruct rev_info revs;\n+\tunsigned int flags = 0;\n+\tint i;\n+\n+\tinit_revisions(&revs, 0);\n+\n+\tfor (i = 0; i < argc; i++) {\n+\t\tif (!strcmp(argv[i], \"--not\"))\n+\t\t\tflags ^= UNINTERESTING;\n+\t\telse if (!strcmp(argv[i], \"--objects\"))\n+\t\t\trevs.tree_objects = revs.blob_objects = 1;\n+\t\telse\n+\t\t\thandle_revision_arg(argv[i], &revs, flags, 1);\n+\t}\n+\n+\tsetup_revisions(0, 0, &revs, 0);\n+\trevs.topo_order = 1;\n+\trevs.lifo = 1;\n+\tprepare_revision_walk(&revs);\n+\n+\ttraverse_commit_list(&revs, show_commit, show_object, 0);\n+\n+\treturn 0;\n+}\n+\n static int handle_walk(int argc, const char *argv[])\n {\n \tstruct commit *commit;\n@@ -271,6 +309,8 @@ int cmd_rev_cache(int argc, const char *argv[], const char *prefix)\n \t\tr = handle_walk(argc, argv);\n \telse if (!strcmp(arg, \"index\"))\n \t\tr = handle_index(argc, argv);\n+\telse if (!strcmp(arg, \"test\"))\n+\t\tr = test_rev_list(argc, argv);\n \telse if (!strcmp(arg, \"alt\"))\n \t\tr = handle_alt(argc, argv);\n \telse\ndiff --git a/list-objects.c b/list-objects.c\nindex 8953548..59df8c7 100644\n--- a/list-objects.c\n+++ b/list-objects.c\n@@ -74,22 +74,34 @@ static void process_tree(struct rev_info *revs,\n \t\tdie(\"bad tree object\");\n \tif (obj->flags & (UNINTERESTING | SEEN))\n \t\treturn;\n+\tif (obj->flags & FACE_VALUE) {\n+\t\tobj->flags |= SEEN;\n+\t\tshow(obj, path, name);\n+\t\t/* not parsing the tree saves a lot of time! */\n+\t\treturn;\n+\t}\n+\n \tif (parse_tree(tree) < 0)\n \t\tdie(\"bad tree object %s\", sha1_to_hex(obj->sha1));\n \tobj->flags |= SEEN;\n \tshow(obj, path, name);\n+\n \tme.up = path;\n \tme.elem = name;\n \tme.elem_len = strlen(name);\n-\n \tinit_tree_desc(&desc, tree->buffer, tree->size);\n \n \twhile (tree_entry(&desc, &entry)) {\n-\t\tif (S_ISDIR(entry.mode))\n+\t\tif (S_ISDIR(entry.mode)) {\n+\t\t\tstruct tree *subtree = lookup_tree(entry.sha1);\n+\t\t\tif (!subtree)\n+\t\t\t\tcontinue;\n+\n+\t\t\tsubtree->object.flags &= ~FACE_VALUE;\n \t\t\tprocess_tree(revs,\n-\t\t\t\t     lookup_tree(entry.sha1),\n+\t\t\t\t     subtree,\n \t\t\t\t     show, &me, entry.path);\n-\t\telse if (S_ISGITLINK(entry.mode))\n+\t\t} else if (S_ISGITLINK(entry.mode))\n \t\t\tprocess_gitlink(revs, entry.sha1,\n \t\t\t\t\tshow, &me, entry.path);\n \t\telse\n@@ -136,6 +148,7 @@ void mark_edges_uninteresting(struct commit_list *list,\n \n static void add_pending_tree(struct rev_info *revs, struct tree *tree)\n {\n+\ttree->object.flags &= ~FACE_VALUE;\n \tadd_pending_object(revs, &tree->object, \"\");\n }\n \n@@ -146,17 +159,27 @@ void traverse_commit_list(struct rev_info *revs,\n {\n \tint i;\n \tstruct commit *commit;\n+\tenum object_type what = OBJ_TAG;\n+\tchar face_value = 0;\n \n \twhile ((commit = get_revision(revs)) != NULL) {\n-\t\tadd_pending_tree(revs, commit->tree);\n+\t\tif (!(commit->object.flags & FACE_VALUE))\n+\t\t\tadd_pending_tree(revs, commit->tree);\n+\t\telse\n+\t\t\tface_value = 1;\n \t\tshow_commit(commit, data);\n \t}\n+\n+loop_objects:\n \tfor (i = 0; i < revs->pending.nr; i++) {\n \t\tstruct object_array_entry *pending = revs->pending.objects + i;\n \t\tstruct object *obj = pending->item;\n \t\tconst char *name = pending->name;\n \t\tif (obj->flags & (UNINTERESTING | SEEN))\n \t\t\tcontinue;\n+\t\tif (obj->type != what && face_value)\n+\t\t\tcontinue;\n+\n \t\tif (obj->type == OBJ_TAG) {\n \t\t\tobj->flags |= SEEN;\n \t\t\tshow_object(obj, NULL, name);\n@@ -175,6 +198,19 @@ void traverse_commit_list(struct rev_info *revs,\n \t\tdie(\"unknown pending object %s (%s)\",\n \t\t    sha1_to_hex(obj->sha1), name);\n \t}\n+\tif (face_value) {\n+\t\tswitch (what) {\n+\t\tcase OBJ_TAG :\n+\t\t\twhat = OBJ_TREE;\n+\t\t\tgoto loop_objects;\n+\t\tcase OBJ_TREE :\n+\t\t\twhat = OBJ_BLOB;\n+\t\t\tgoto loop_objects;\n+\t\tdefault :\n+\t\t\tbreak;\n+\t\t}\n+\t}\n+\n \tif (revs->pending.nr) {\n \t\tfree(revs->pending.objects);\n \t\trevs->pending.nr = 0;\ndiff --git a/rev-cache.c b/rev-cache.c\nindex 8ca97d3..6becd4b 100644\n--- a/rev-cache.c\n+++ b/rev-cache.c\n@@ -11,6 +11,12 @@\n #include \"run-command.h\"\n #include \"string-list.h\"\n \n+\n+struct bad_slice {\n+\tunsigned char sha1[20];\n+\tstruct bad_slice *next;\n+};\n+\n struct cache_slice_pointer {\n \tchar signature[8]; /* REVCOPTR */\n \tchar version;\n@@ -23,8 +29,9 @@ static uint32_t fanout[0xff + 2];\n static unsigned char *idx_map;\n static int idx_size;\n static struct rc_index_header idx_head;\n+static char no_idx, add_to_pending;\n+static struct bad_slice *bad_slices;\n static unsigned char *idx_caches;\n-static char no_idx;\n \n static struct strbuf *acc_buffer;\n \n@@ -121,6 +128,30 @@ struct rc_object_entry_ondisk *to_disked_rc_object_entry(struct rc_object_entry\n \treturn dst;\n }\n \n+static void mark_bad_slice(unsigned char *sha1)\n+{\n+\tstruct bad_slice *bad;\n+\n+\tbad = xcalloc(sizeof(struct bad_slice), 1);\n+\thashcpy(bad->sha1, sha1);\n+\n+\tbad->next = bad_slices;\n+\tbad_slices = bad;\n+}\n+\n+static int is_bad_slice(unsigned char *sha1)\n+{\n+\tstruct bad_slice *bad = bad_slices;\n+\n+\twhile (bad) {\n+\t\tif (!hashcmp(bad->sha1, sha1))\n+\t\t\treturn 1;\n+\t\tbad = bad->next;\n+\t}\n+\n+\treturn 0;\n+}\n+\n static int get_index_head(unsigned char *map, int len, struct rc_index_header *head, uint32_t *fanout, unsigned char **caches)\n {\n \tstruct rc_index_header whead;\n@@ -246,6 +277,7 @@ static struct rc_index_entry *search_index(unsigned char *sha1)\n unsigned char *get_cache_slice(struct commit *commit)\n {\n \tstruct rc_index_entry *ie;\n+\tunsigned char *sha1;\n \n \tif (!idx_map) {\n \t\tif (no_idx)\n@@ -257,8 +289,13 @@ unsigned char *get_cache_slice(struct commit *commit)\n \t\treturn 0;\n \n \tie = search_index(commit->object.sha1);\n-\tif (ie && ie->cache_index < idx_head.cache_nr)\n-\t\treturn idx_caches + ie->cache_index * 20;\n+\tif (ie && ie->cache_index < idx_head.cache_nr) {\n+\t\tsha1 = idx_caches + ie->cache_index * 20;\n+\n+\t\tif (is_bad_slice(sha1))\n+\t\t\treturn 0;\n+\t\treturn sha1;\n+\t}\n \n \treturn 0;\n }\n@@ -268,6 +305,20 @@ unsigned char *get_cache_slice(struct commit *commit)\n \n static unsigned long decode_size(unsigned char *str, int len);\n \n+/* on failure */\n+static void restore_commit(struct commit *commit)\n+{\n+\tcommit->object.flags &= ~(ADDED | SEEN | FACE_VALUE);\n+\n+\tif (!commit->object.parsed) {\n+\t\twhile (pop_commit(&commit->parents))\n+\t\t\t;\n+\n+\t\tparse_commit(commit);\n+\t}\n+\n+}\n+\n static void handle_noncommit(struct rev_info *revs, struct commit *commit, unsigned char *ptr, struct rc_object_entry *entry)\n {\n \tstruct blob *blob;\n@@ -307,23 +358,27 @@ static void handle_noncommit(struct rev_info *revs, struct commit *commit, unsig\n \t}\n \n \tobj->flags |= FACE_VALUE;\n-\tadd_pending_object(revs, obj, \"\");\n+\tif (add_to_pending)\n+\t\tadd_pending_object(revs, obj, \"\");\n }\n \n-static int setup_traversal(struct rc_slice_header *head, unsigned char *map, struct commit *commit, struct commit_list **work)\n+static int setup_traversal(struct rc_slice_header *head, unsigned char *map, struct commit *commit, struct commit_list **work,\n+\tstruct commit_list **unwork, int *ipath_nr, int *upath_nr, char *ioutside)\n {\n \tstruct rc_index_entry *iep;\n \tstruct rc_object_entry *oep;\n \tstruct commit_list *prev, *wp, **wpp;\n \tint retval;\n \n-\tiep = search_index(commit->object.sha1), 0;\n+\tiep = search_index(commit->object.sha1);\n \toep = RC_OBTAIN_OBJECT_ENTRY(map + iep->pos);\n+\tif (commit->object.flags & UNINTERESTING) {\n+\t\t++*upath_nr;\n+\t\toep->uninteresting = 1;\n+\t} else\n+\t\t++*ipath_nr;\n \n-\t/* the .uniniteresting bit isn't strictly necessary, as we check the object during traversal as well,\n-\t * but we might as well initialize it while we're at it */\n \toep->include = 1;\n-\toep->uninteresting = !!(commit->object.flags & UNINTERESTING);\n \tto_disked_rc_object_entry(oep, (struct rc_object_entry_ondisk *)(map + iep->pos));\n \tretval = iep->pos;\n \n@@ -338,6 +393,10 @@ static int setup_traversal(struct rc_slice_header *head, unsigned char *map, str\n \t\t/* is this in our cache slice? */\n \t\tiep = search_index(obj->sha1);\n \t\tif (!iep || hashcmp(idx_caches + iep->cache_index * 20, head->sha1)) {\n+\t\t\t/* there are interesing objects outside the slice */\n+\t\t\tif (!(obj->flags & UNINTERESTING))\n+\t\t\t\t*ioutside = 1;\n+\n \t\t\tprev = wp;\n \t\t\twp = wp->next;\n \t\t\twpp = &wp;\n@@ -354,11 +413,20 @@ static int setup_traversal(struct rc_slice_header *head, unsigned char *map, str\n \t\toep->uninteresting = !!(obj->flags & UNINTERESTING);\n \t\tto_disked_rc_object_entry(oep, (struct rc_object_entry_ondisk *)(map + iep->pos));\n \n+\t\t/* count even if not in slice so we can stop enumerating if possible */\n+\t\tif (obj->flags & UNINTERESTING)\n+\t\t\t++*upath_nr;\n+\t\telse\n+\t\t\t++*ipath_nr;\n+\n \t\t/* remove from work list */\n \t\tco = pop_commit(wpp);\n \t\twp = *wpp;\n \t\tif (prev)\n \t\t\tprev->next = wp;\n+\n+\t\t/* ...and store in temp list so we can restore work on failure */\n+\t\tcommit_list_insert(co, unwork);\n \t}\n \n \treturn retval;\n@@ -375,13 +443,18 @@ static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *m\n \tunsigned long *date_so_far, int *slop_so_far,\n \tstruct commit_list ***queue, struct commit_list **work)\n {\n-\tstruct commit_list *insert_cache = 0;\n+\tstruct commit_list *insert_cache = 0, *myq = 0, **myqp = &myq, *mywork = 0, **myworkp = &mywork, *unwork = 0;\n \tstruct commit **last_objects, *co;\n-\tint i, total_path_nr = head->path_nr, retval = -1;\n-\tchar consume_children = 0;\n+\tunsigned long date = date_so_far ? *date_so_far : ~0ul;\n+\tint i, ipath_nr = 0, upath_nr = 0, orig_obj_nr = 0,\n+\t\ttotal_path_nr = head->path_nr, retval = -1, slop = slop_so_far ? *slop_so_far : SLOP;\n+\tchar consume_children = 0, ioutside = 0;\n \tunsigned char *paths;\n \n-\ti = setup_traversal(head, map, commit, work);\n+\t/* take note in case we need to regress */\n+\torig_obj_nr = revs->pending.nr;\n+\n+\ti = setup_traversal(head, map, commit, work, &unwork, &ipath_nr, &upath_nr, &ioutside);\n \tif (i < 0)\n \t\treturn -1;\n \n@@ -429,6 +502,7 @@ static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *m\n \n \t\tif ((paths[path] & IPATH) && (paths[path] & UPATH)) {\n \t\t\tpaths[path] = UPATH;\n+\t\t\tipath_nr--;\n \n \t\t\t/* mark edge */\n \t\t\tif (last_objects[path]) {\n@@ -439,6 +513,7 @@ static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *m\n \t\t\t\tlast_objects[path]->object.flags &= ~FACE_VALUE;\n \t\t\t\tlast_objects[path] = 0;\n \t\t\t}\n+\t\t\tobj->flags |= BOUNDARY;\n \t\t}\n \n \t\t/* now we gotta re-assess the whole interesting thing... */\n@@ -462,8 +537,10 @@ static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *m\n \t\t\t\t\t\tlast_objects[p]->object.flags &= ~FACE_VALUE;\n \t\t\t\t\t\tlast_objects[p] = 0;\n \t\t\t\t\t}\n-\t\t\t\t} else if (last_objects[p] && !last_objects[p]->object.parsed)\n+\t\t\t\t\tobj->flags |= BOUNDARY;\n+\t\t\t\t} else if (last_objects[p] && !last_objects[p]->object.parsed) {\n \t\t\t\t\tcommit_list_insert(co, &last_objects[p]->parents);\n+\t\t\t\t}\n \n \t\t\t\t/* can't close a merge path until all are parents have been encountered */\n \t\t\t\tif (GET_COUNT(paths[p])) {\n@@ -473,14 +550,33 @@ static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *m\n \t\t\t\t\t\tcontinue;\n \t\t\t\t}\n \n+\t\t\t\tif (paths[p] & IPATH)\n+\t\t\t\t\tipath_nr--;\n+\t\t\t\telse\n+\t\t\t\t\tupath_nr--;\n+\n \t\t\t\tpaths[p] = 0;\n \t\t\t\tlast_objects[p] = 0;\n \t\t\t}\n \t\t}\n \n \t\t/* make topo relations */\n-\t\tif (last_objects[path] && !last_objects[path]->object.parsed)\n+\t\tif (last_objects[path] && !last_objects[path]->object.parsed) {\n \t\t\tcommit_list_insert(co, &last_objects[path]->parents);\n+\t\t}\n+\n+\t\t/* we've been here already */\n+\t\tif (obj->flags & ADDED) {\n+\t\t\tif (entry->uninteresting && !(obj->flags & UNINTERESTING)) {\n+\t\t\t\tobj->flags |= UNINTERESTING;\n+\t\t\t\tmark_parents_uninteresting(co);\n+\t\t\t\tupath_nr--;\n+\t\t\t} else if (!entry->uninteresting)\n+\t\t\t\tipath_nr--;\n+\n+\t\t\tpaths[path] = 0;\n+\t\t\tcontinue;\n+\t\t}\n \n \t\t/* initialize commit */\n \t\tif (!entry->is_end) {\n@@ -493,24 +589,51 @@ static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *m\n \n \t\tif (entry->uninteresting)\n \t\t\tobj->flags |= UNINTERESTING;\n+\t\telse if (co->date < date)\n+\t\t\tdate = co->date;\n \n \t\t/* we need to know what the edges are */\n \t\tlast_objects[path] = co;\n \n \t\t/* add to list */\n-\t\tif (!(obj->flags & UNINTERESTING) || revs->show_all) {\n-\t\t\tif (entry->is_end)\n-\t\t\t\tinsert_by_date_cached(co, work, insert_cache, &insert_cache);\n-\t\t\telse\n-\t\t\t\t*queue = &commit_list_insert(co, *queue)->next;\n+\t\tif (slop && !(revs->min_age != -1 && co->date > revs->min_age)) {\n+\n+\t\t\tif (!(obj->flags & UNINTERESTING) || revs->show_all) {\n+\t\t\t\tif (entry->is_end)\n+\t\t\t\t\tmyworkp = &commit_list_insert(co, myworkp)->next;\n+\t\t\t\telse\n+\t\t\t\t\tmyqp = &commit_list_insert(co, myqp)->next;\n+\n+\t\t\t\t/* add children to list as well */\n+\t\t\t\tif (obj->flags & UNINTERESTING)\n+\t\t\t\t\tconsume_children = 0;\n+\t\t\t\telse\n+\t\t\t\t\tconsume_children = 1;\n+\t\t\t}\n \n-\t\t\t/* add children to list as well */\n-\t\t\tif (obj->flags & UNINTERESTING)\n-\t\t\t\tconsume_children = 0;\n-\t\t\telse\n-\t\t\t\tconsume_children = 1;\n \t\t}\n \n+\t\t/* should we continue? */\n+\t\tif (!slop) {\n+\t\t\tif (!upath_nr) {\n+\t\t\t\tbreak;\n+\t\t\t} else if (ioutside || revs->show_all) {\n+\t\t\t\t/* pass it back to rev-list\n+\t\t\t\t * we purposely ignore everything outside this cache, so we don't needlessly traverse the whole\n+\t\t\t\t * thing on uninteresting, but that does mean that we may need to bounce back\n+\t\t\t\t * and forth a few times with rev-list */\n+\t\t\t\tmyworkp = &commit_list_insert(co, myworkp)->next;\n+\n+\t\t\t\tpaths[path] = 0;\n+\t\t\t\tupath_nr--;\n+\t\t\t} else {\n+\t\t\t\tbreak;\n+\t\t\t}\n+\t\t} else if (!ipath_nr && co->date <= date)\n+\t\t\tslop--;\n+\t\telse\n+\t\t\tslop = SLOP;\n+\n \t\t/* open parents */\n \t\tif (entry->merge_nr) {\n \t\t\tint j, off = index + sizeof(struct rc_object_entry_ondisk);\n@@ -525,6 +648,11 @@ static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *m\n \t\t\t\tif (paths[p] & flag)\n \t\t\t\t\tcontinue;\n \n+\t\t\t\tif (flag == IPATH)\n+\t\t\t\t\tipath_nr++;\n+\t\t\t\telse\n+\t\t\t\t\tupath_nr++;\n+\n \t\t\t\tpaths[p] |= flag;\n \t\t\t}\n \n@@ -534,12 +662,55 @@ static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *m\n \n \t}\n \n+\tif (date_so_far)\n+\t\t*date_so_far = date;\n+\tif (slop_so_far)\n+\t\t*slop_so_far = slop;\n \tretval = 0;\n \n+\t/* success: attach to given lists */\n+\tif (myqp != &myq) {\n+\t\t**queue = myq;\n+\t\t*queue = myqp;\n+\t}\n+\n+\twhile ((co = pop_commit(&mywork)) != 0) {\n+\t\tinsert_by_date_cached(co, work, insert_cache, &insert_cache);\n+\t}\n+\n+\t/* free backup */\n+\twhile (pop_commit(&unwork))\n+\t\t;\n+\n end:\n \tfree(paths);\n \tfree(last_objects);\n \n+\t/* failure: restore work to previous condition\n+\t * (cache corruption should *not* be fatal) */\n+\tif (retval) {\n+\t\twhile ((co = pop_commit(&unwork)) != 0) {\n+\t\t\trestore_commit(co);\n+\t\t\tco->object.flags |= SEEN;\n+\t\t\tinsert_by_date(co, work);\n+\t\t}\n+\n+\t\t/* free lists */\n+\t\twhile ((co = pop_commit(&myq)) != 0)\n+\t\t\trestore_commit(co);\n+\n+\t\twhile ((co = pop_commit(&mywork)) != 0)\n+\t\t\trestore_commit(co);\n+\n+\t\t/* truncate object array */\n+\t\tfor (i = orig_obj_nr; i < revs->pending.nr; i++) {\n+\t\t\tstruct object *obj = revs->pending.objects[i].item;\n+\n+\t\t\tobj->flags &= ~FACE_VALUE;\n+\t\t}\n+\t\trevs->pending.nr = orig_obj_nr;\n+\t}\n+\n \treturn retval;\n }\n \n@@ -630,6 +801,7 @@ int traverse_cache_slice(struct rev_info *revs,\n \n \t/* load options */\n \trci = &revs->rev_cache_info;\n+\tadd_to_pending = rci->add_to_pending;\n \n \tmemset(&head, 0, sizeof(struct rc_slice_header));\n \n@@ -653,6 +825,10 @@ end:\n \tif (fd != -1)\n \t\tclose(fd);\n \n+\t/* remember this! */\n+\tif (retval)\n+\t\tmark_bad_slice(cache_sha1);\n+\n \treturn retval;\n }\n \n@@ -1128,7 +1304,7 @@ static int add_objects_verbatim_1(struct rev_cache_slice_map *mapping, int *inde\n \twhile (i < mapping->size) {\n \t\tint pos = i;\n \n-\t\tentry = RC_OBTAIN_OBJECT_ENTRY(map + i;\n+\t\tentry = RC_OBTAIN_OBJECT_ENTRY(map + i);\n \t\ti += RC_ACTUAL_OBJECT_ENTRY_SIZE(entry);\n \n \t\tif (entry->type == OBJ_COMMIT) {\ndiff --git a/revision.c b/revision.c\nindex c7fd35f..ed21885 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -12,6 +12,7 @@\n #include \"patch-ids.h\"\n #include \"decorate.h\"\n #include \"log-tree.h\"\n+#include \"rev-cache.h\"\n \n volatile show_early_output_fn_t show_early_output;\n \n@@ -638,6 +639,8 @@ static int limit_list(struct rev_info *revs)\n \tstruct commit_list *list = revs->commits;\n \tstruct commit_list *newlist = NULL;\n \tstruct commit_list **p = &newlist;\n+\tunsigned char *cache_sha1;\n+\tchar used_cache;\n \n \twhile (list) {\n \t\tstruct commit_list *entry = list;\n@@ -650,24 +653,39 @@ static int limit_list(struct rev_info *revs)\n \n \t\tif (revs->max_age != -1 && (commit->date < revs->max_age))\n \t\t\tobj->flags |= UNINTERESTING;\n-\t\tif (add_parents_to_list(revs, commit, &list, NULL) < 0)\n-\t\t\treturn -1;\n-\t\tif (obj->flags & UNINTERESTING) {\n-\t\t\tmark_parents_uninteresting(commit);\n-\t\t\tif (revs->show_all)\n-\t\t\t\tp = &commit_list_insert(commit, p)->next;\n-\t\t\tslop = still_interesting(list, date, slop);\n-\t\t\tif (slop)\n+\n+\t\t/* rev-cache to the rescue!!! */\n+\t\tused_cache = 0;\n+\t\tif (!revs->dont_cache_me && !(obj->flags & ADDED)) {\n+\t\t\tcache_sha1 = get_cache_slice(commit);\n+\t\t\tif (cache_sha1) {\n+\t\t\t\tif (traverse_cache_slice(revs, cache_sha1, commit, &date, &slop, &p, &list) < 0)\n+\t\t\t\t\tused_cache = 0;\n+\t\t\t\telse\n+\t\t\t\t\tused_cache = 1;\n+\t\t\t}\n+\t\t}\n+\n+\t\tif (!used_cache) {\n+\t\t\tif (add_parents_to_list(revs, commit, &list, NULL) < 0)\n+\t\t\t\treturn -1;\n+\t\t\tif (obj->flags & UNINTERESTING) {\n+\t\t\t\tmark_parents_uninteresting(commit); /* ME: why? */\n+\t\t\t\tif (revs->show_all)\n+\t\t\t\t\tp = &commit_list_insert(commit, p)->next;\n+\t\t\t\tslop = still_interesting(list, date, slop);\n+\t\t\t\tif (slop > 0)\n+\t\t\t\t\tcontinue;\n+\t\t\t\t/* If showing all, add the whole pending list to the end */\n+\t\t\t\tif (revs->show_all)\n+\t\t\t\t\t*p = list;\n+\t\t\t\tbreak;\n+\t\t\t}\n+\t\t\tif (revs->min_age != -1 && (commit->date > revs->min_age))\n \t\t\t\tcontinue;\n-\t\t\t/* If showing all, add the whole pending list to the end */\n-\t\t\tif (revs->show_all)\n-\t\t\t\t*p = list;\n-\t\t\tbreak;\n+\t\t\tdate = commit->date;\n+\t\t\tp = &commit_list_insert(commit, p)->next;\n \t\t}\n-\t\tif (revs->min_age != -1 && (commit->date > revs->min_age))\n-\t\t\tcontinue;\n-\t\tdate = commit->date;\n-\t\tp = &commit_list_insert(commit, p)->next;\n \n \t\tshow = show_early_output;\n \t\tif (!show)\n@@ -813,6 +831,8 @@ void init_revisions(struct rev_info *revs, const char *prefix)\n \t\trevs->diffopt.prefix = prefix;\n \t\trevs->diffopt.prefix_length = strlen(prefix);\n \t}\n+\n+\tinit_rev_cache_info(&revs->rev_cache_info);\n }\n \n static void add_pending_commit_list(struct rev_info *revs,\n@@ -1372,6 +1392,11 @@ int setup_revisions(int argc, const char **argv, struct rev_info *revs, const ch\n \tif (revs->reflog_info && revs->graph)\n \t\tdie(\"cannot combine --walk-reflogs with --graph\");\n \n+\t/* limits on caching\n+\t * todo: implement this functionality */\n+\tif (revs->prune || revs->diff)\n+\t\trevs->dont_cache_me = 1;\n+\n \treturn left;\n }\n \n@@ -1654,6 +1679,8 @@ static int commit_match(struct commit *commit, struct rev_info *opt)\n {\n \tif (!opt->grep_filter.pattern_list)\n \t\treturn 1;\n+\tif (!commit->object.parsed)\n+\t\tparse_commit(commit);\n \treturn grep_buffer(&opt->grep_filter,\n \t\t\t   NULL, /* we say nothing, not even filename */\n \t\t\t   commit->buffer, strlen(commit->buffer));\n@@ -1717,6 +1744,7 @@ static struct commit *get_revision_1(struct rev_info *revs)\n \tdo {\n \t\tstruct commit_list *entry = revs->commits;\n \t\tstruct commit *commit = entry->item;\n+\t\tstruct object *obj = &commit->object;\n \n \t\trevs->commits = entry->next;\n \t\tfree(entry);\n@@ -1733,11 +1761,39 @@ static struct commit *get_revision_1(struct rev_info *revs)\n \t\t\tif (revs->max_age != -1 &&\n \t\t\t    (commit->date < revs->max_age))\n \t\t\t\tcontinue;\n+\n+\t\t\tif (!revs->dont_cache_me) {\n+\t\t\t\tstruct commit_list *queue = 0, **queuep = &queue;\n+\t\t\t\tunsigned char *cache_sha1;\n+\n+\t\t\t\tif (obj->flags & ADDED)\n+\t\t\t\t\tgoto skip_parenting;\n+\n+\t\t\t\tcache_sha1 = get_cache_slice(commit);\n+\t\t\t\tif (cache_sha1) {\n+\t\t\t\t\tif (!traverse_cache_slice(revs, cache_sha1, commit, 0, 0, &queuep, &revs->commits)) {\n+\t\t\t\t\t\tstruct commit_list *work = revs->commits;\n+\n+\t\t\t\t\t\t/* attach queue to end of ->commits */\n+\t\t\t\t\t\twhile (work && work->next)\n+\t\t\t\t\t\t\twork = work->next;\n+\n+\t\t\t\t\t\tif (work)\n+\t\t\t\t\t\t\twork->next = queue;\n+\t\t\t\t\t\telse\n+\t\t\t\t\t\t\trevs->commits = queue;\n+\n+\t\t\t\t\t\tgoto skip_parenting;\n+\t\t\t\t\t}\n+\t\t\t\t}\n+\t\t\t}\n+\n \t\t\tif (add_parents_to_list(revs, commit, &revs->commits, NULL) < 0)\n \t\t\t\tdie(\"Failed to traverse parents of commit %s\",\n \t\t\t\t    sha1_to_hex(commit->object.sha1));\n \t\t}\n \n+skip_parenting:\n \t\tswitch (simplify_commit(revs, commit)) {\n \t\tcase commit_ignore:\n \t\t\tcontinue;\ndiff --git a/t/t6017-rev-cache-list.sh b/t/t6017-rev-cache-list.sh\nindex dc0fc07..f2e34b1 100755\n--- a/t/t6017-rev-cache-list.sh\n+++ b/t/t6017-rev-cache-list.sh\n@@ -38,6 +38,7 @@ test_expect_success 'init repo' '\n \tgit add . &&\n \tgit commit -m \"omg\" &&\n \n+\tsleep 2 &&\n \tgit branch b4 &&\n \tgit checkout b4 &&\n \techo shazam >file8 &&\n@@ -46,7 +47,7 @@ test_expect_success 'init repo' '\n \tgit merge -m \"merge b2\" b2 &&\n \n \techo bam >smoke/pipe &&\n-\tgit add .\n+\tgit add . &&\n \tgit commit -m \"bam\" &&\n \n \tgit checkout master &&\n@@ -71,18 +72,26 @@ test_expect_success 'init repo' '\n \tgit add . &&\n \tgit commit -m \"lol\" &&\n \n+\tsleep 2 &&\n \tgit checkout master &&\n \tgit merge -m \"triple merge\" b1 b11 &&\n \tgit rm -r d1 &&\n+\tsleep 2 &&\n \tgit commit -a -m \"oh noes\"\n '\n \n-git-rev-list HEAD --not HEAD~3 >proper_commit_list_limited\n-git-rev-list HEAD >proper_commit_list\n-git-rev-list HEAD --objects >proper_object_list\n+max_date=`git-rev-list --timestamp HEAD~1 --max-count=1 | grep -e \"^[0-9]*\" -o`\n+min_date=`git-rev-list --timestamp b4 --max-count=1 | grep -e \"^[0-9]*\" -o`\n+\n+git-rev-list --topo-order HEAD --not HEAD~3 >proper_commit_list_limited\n+git-rev-list --topo-order HEAD --not HEAD~2 >proper_commit_list_limited2\n+git-rev-list --topo-order HEAD >proper_commit_list\n+git-rev-list --objects HEAD >proper_object_list\n+git-rev-list HEAD --max-age=$min_date --min-age=$max_date >proper_list_date_limited\n+\n+cache_sha1=`git-rev-cache add HEAD 2>output.err`\n \n test_expect_success 'make cache slice' '\n-\tgit-rev-cache add HEAD 2>output.err &&\n \tgrep \"final return value: 0\" output.err\n '\n \n@@ -102,11 +111,141 @@ test_expect_success 'test rev-caches walker directly (unlimited)' '\n \ttest_cmp_sorted list proper_commit_list\n '\n \n+test_expect_success 'test rev-list traversal (limited)' '\n+\tgit-rev-list HEAD --not HEAD~3 >list &&\n+\ttest_cmp list proper_commit_list_limited\n+'\n+\n+test_expect_success 'test rev-list traversal (unlimited)' '\n+\tgit-rev-list HEAD >list &&\n+\ttest_cmp list proper_commit_list\n+'\n+\n #do the same for objects\n test_expect_success 'test rev-caches walker with objects' '\n \tgit-rev-cache walk --objects HEAD >list &&\n \ttest_cmp_sorted list proper_object_list\n '\n \n-test_done\n+test_expect_success 'test rev-list with objects (topo order)' '\n+\tgit-rev-list --topo-order --objects HEAD >list &&\n+\ttest_cmp_sorted list proper_object_list\n+'\n+\n+test_expect_success 'test rev-list with objects (no order)' '\n+\tgit-rev-list --objects HEAD >list &&\n+\ttest_cmp_sorted list proper_object_list\n+'\n+\n+#verify age limiting\n+test_expect_success 'test rev-list date limiting (topo order)' '\n+\tgit-rev-list --topo-order --max-age=$min_date --min-age=$max_date HEAD >list &&\n+\ttest_cmp_sorted list proper_list_date_limited\n+'\n+\n+test_expect_success 'test rev-list date limiting (no order)' '\n+\tgit-rev-list --max-age=$min_date --min-age=$max_date HEAD >list &&\n+\ttest_cmp_sorted list proper_list_date_limited\n+'\n+\n+#check partial cache slice\n+test_expect_success 'saving old cache and generating partial slice' '\n+\tcp \".git/rev-cache/$cache_sha1\" .git/rev-cache/.old &&\n+\trm \".git/rev-cache/$cache_sha1\" .git/rev-cache/index &&\n+\n+\tgit-rev-cache add HEAD~2 2>output.err &&\n+\tgrep \"final return value: 0\" output.err\n+'\n+\n+test_expect_success 'rev-list with wholly interesting partial slice' '\n+\tgit-rev-list --topo-order HEAD >list &&\n+\ttest_cmp list proper_commit_list\n+'\n+\n+test_expect_success 'rev-list with partly uninteresting partial slice' '\n+\tgit-rev-list --topo-order HEAD --not HEAD~3 >list &&\n+\ttest_cmp list proper_commit_list_limited\n+'\n+\n+test_expect_success 'rev-list with wholly uninteresting partial slice' '\n+\tgit-rev-list --topo-order HEAD --not HEAD~2 >list &&\n+\ttest_cmp list proper_commit_list_limited2\n+'\n+\n+#try out index generation and fuse (note that --all == HEAD in this case)\n+#probably should make a test for that too...\n+test_expect_success 'test (non-)fusion of one slice' '\n+\tgit-rev-cache fuse >output.err &&\n+\tgrep \"nothing to fuse\" output.err\n+'\n \n+test_expect_success 'make fresh slice' '\n+\tgit-rev-cache add --all --fresh 2>output.err &&\n+\tgrep \"final return value: 0\" output.err\n+'\n+\n+test_expect_success 'check dual slices' '\n+\tgit-rev-list --topo-order HEAD~2 HEAD >list &&\n+\ttest_cmp list proper_commit_list\n+'\n+\n+test_expect_success 'regenerate index' '\n+\trm .git/rev-cache/index &&\n+\tgit-rev-cache index 2>output.err &&\n+\tgrep \"final return value: 0\" output.err\n+'\n+\n+test_expect_success 'fuse slices' '\n+\ttest -e .git/rev-cache/.old &&\n+\tgit-rev-cache fuse 2>output.err &&\n+\tgrep \"final return value: 0\" output.err &&\n+\ttest_cmp .git/rev-cache/$cache_sha1 .git/rev-cache/.old\n+'\n+\n+#make sure we can smoothly handle corrupted caches\n+test_expect_success 'corrupt slice' '\n+\techo bla >.git/rev-cache/$cache_sha1\n+'\n+\n+test_expect_success 'test rev-list traversal (limited) (corrupt slice)' '\n+\tgit-rev-list --topo-order HEAD --not HEAD~3 >list &&\n+\ttest_cmp list proper_commit_list_limited\n+'\n+\n+test_expect_success 'test rev-list traversal (unlimited) (corrupt slice)' '\n+\tgit-rev-list HEAD >list &&\n+\ttest_cmp_sorted list proper_commit_list\n+'\n+\n+test_expect_success 'corrupt index' '\n+\techo blu >.git/rev-cache/index\n+'\n+\n+test_expect_success 'test rev-list traversal (limited) (corrupt index)' '\n+\tgit-rev-list --topo-order HEAD --not HEAD~3 >list &&\n+\ttest_cmp list proper_commit_list_limited\n+'\n+\n+test_expect_success 'test rev-list traversal (unlimited) (corrupt index)' '\n+\tgit-rev-list HEAD >list &&\n+\ttest_cmp_sorted list proper_commit_list\n+'\n+\n+#test --ignore-size in fuse\n+rm .git/rev-cache/*\n+cache_sha1=`git-rev-cache add HEAD~2 2>output.err`\n+\n+test_expect_success 'make fragmented slices' '\n+\tgit-rev-cache add HEAD~1 --not HEAD~2 2>>output.err &&\n+\tgit-rev-cache add HEAD --fresh 2>>output.err &&\n+\ttest `grep \"final return value: 0\" output.err | wc -l` -eq 3\n+'\n+\n+cache_size=`wc -c .git/rev-cache/$cache_sha1 | grep -o \"[0-9]*\"`\n+test_expect_success 'test --ignore-size function in fuse' '\n+\tgit-rev-cache fuse --ignore-size=$cache_size 2>output.err &&\n+\tgrep \"final return value: 0\" output.err &&\n+\ttest -e .git/rev-cache/$cache_sha1\n+'\n+\n+test_done\n-- \ntg: (e9374fc..) t/revcache/integration (depends on: t/revcache/misc)\n"},{"id":"122642","messageId":"1252357564.5969.4.camel@maia.lan","threadId":"20633","inReplyTo":"op.uzv4covmtdk399@sirnot.private","subject":"Re: [PATCH 5/6 (v4)] full integration of rev-cache into git, completed test suite","fromName":"Sam Vilain","fromEmail":"sam@vilain.net","sentAt":"2009-09-07T21:06:04Z","receivedAt":"2009-09-07T21:06:04Z","isPatch":true,"sender":{"key":"sam@vilain.net","avatar":"https://gravatar.com/avatar/8fc840ca854dbf6f7065b4335e3b934951c1dca3b11db688e95e471901f8f4a8?d=mp&s=160"},"body":"On Mon, 2009-09-07 at 16:11 +0200, Nick Edelen wrote:\n> This last patch \n\n^^ You don't need to write comments like \"This patch\"; in the history\nsuch words are meaningless.\n\n> provides a working integration of rev-cache into the revision \n> walker, along with some touch-ups:\n>  - integration into revision walker and list-objects\n>  - tweak of object generation\n\n\"tweak\" ?\n\n>  - more fluid handling of damaged cache slices\n\nWhat does this mean?\n\n>  - numerous tests for both features from the previous patch, and the \n> integration's integrity\n> 'Integration' is rather broad -- a more detailed description follows for each \n> aspect:\n>  - rev-cache\n> the traversal mechanism is updated to handle many of the non-prune options \n> rev-list does (date limiting, slop-handling, etc.), and is adjusted to allow \n> for non-fatal cache-traversal failures.\n> \n>  - revision walker\n> both limited and unlimited traversal attempt to use the cache when possible, \n> smoothly falling back if it's not.\n> \n>  - list-objects\n> object listing does not recurse into cached trees, and has been adjusted to \n> guarantee commit-tag-tree-blob ordering.\n\nThis is quite a long commit message.  Is the above detail all useful?\nCan it be split into one patch for each of the above integrations?\n\n> Signed-off-by: Nick Edelen <sirnot@gmail.com>\n\nSam\n"},{"id":"122740","messageId":"c77435a80909081524i493603efhb32dee77c1e7223b@mail.gmail.com","threadId":"20633","inReplyTo":"1252357564.5969.4.camel@maia.lan","subject":"Re: [PATCH 5/6 (v4)] full integration of rev-cache into git, completed test suite","fromName":"Nick Edelen","fromEmail":"sirnot@gmail.com","sentAt":"2009-09-08T22:24:22Z","receivedAt":"2009-09-08T22:24:22Z","isPatch":true,"sender":{"key":"sirnot@gmail.com","avatar":null},"body":"> ^^ You don't need to write comments like \"This patch\"; in the history\n> such words are meaningless.\n\nI had meant to delete that...\n\n> \"tweak\" ?\n\nYeah I had modified the messages and didn't replace the additional\ninfo I deleted.  It's not really important, as it's modified again\n(for the last time) in the name-related patch, but here it's revised\nto take advantage of the size storage.\n\n>>  - more fluid handling of damaged cache slices\n>\n> What does this mean?\n\nThat it remembers/is aware of bad slices, instead of dumbly attempting\nto load them upon each commit.\n\n> This is quite a long commit message.  Is the above detail all useful?\n> Can it be split into one patch for each of the above integrations?\n\nErm, I suppose they could be split, but the changes to revision and\nlist-objects aren't very big, so I figured it'd be easier/cleaner to\njust put everything required for smooth integration into a single\npatch.  I dunno, it dosn't seem hugely necessary; the bits modifying\ngit code are relatively small and already obviously seperate in the\npatch.\n"},{"id":"124021","messageId":"1254297229-14806-1-git-send-email-chris_johnsen@pobox.com","threadId":"20633","inReplyTo":"op.uzv4covmtdk399@sirnot.private","subject":"Re: [PATCH 5/6 (v4)] full integration of rev-cache into git, completed test suite","fromName":"Chris Johnsen","fromEmail":"chris_johnsen@pobox.com","sentAt":"2009-09-30T07:53:49Z","receivedAt":"2009-09-30T07:53:49Z","isPatch":true,"sender":{"key":"chris_johnsen@pobox.com","avatar":"https://avatars.githubusercontent.com/u/107071?v=4"},"body":"(The Cc list of the parent message was truncated.\n The Cc list of this message was adopted from later messages.)\n\nI needed something like the following to get the tests to pass.\nIf you like it, squash it into 5/6.\n\n-->8--\nSubject: [PATCH] t6017: use 'tr -d' to strip spaces from 'wc -c' output\n\nThe previous use of 'grep -o \"[0-9]*\"' was producing an empty string\n(GNU grep 2.5.1 on Mac OS X 10.4.11). Additionally, since 'wc' echos\nits filename arguments when stdin is not the source, the 'grep -o'\nmight have also extracted additional decimal strings embedded in the\nfilename (a SHA-1 hash value).\n\nThis 'tr -d' style is used in git-filter-branch.sh, and t6003.\nAnother alternative (in t1006) is to use 'sed' to strip off the\nleading spaces.\n\nSigned-off-by: Chris Johnsen <chris_johnsen@pobox.com>\n---\n t/t6017-rev-cache-list.sh |    2 +-\n 1 files changed, 1 insertions(+), 1 deletions(-)\n\ndiff --git a/t/t6017-rev-cache-list.sh b/t/t6017-rev-cache-list.sh\nindex 6ada7ac..3f49cb3 100755\n--- a/t/t6017-rev-cache-list.sh\n+++ b/t/t6017-rev-cache-list.sh\n@@ -246,7 +246,7 @@ test_expect_success 'make fragmented slices' '\n \ttest `grep \"final return value: 0\" output.err | wc -l` -eq 3\n '\n \n-cache_size=`wc -c .git/rev-cache/$cache_sha1 | grep -o \"[0-9]*\"`\n+cache_size=`wc -c < .git/rev-cache/$cache_sha1 | tr -d ' '`\n test_expect_success 'test --ignore-size function in fuse' '\n \tgit-rev-cache fuse --ignore-size=$cache_size 2>output.err &&\n \tgrep \"final return value: 0\" output.err &&\n-- \n1.6.5.rc1.183.g23fa6\n"},{"id":"124023","messageId":"4AC31239.609@viscovery.net","threadId":"20633","inReplyTo":"1254297229-14806-1-git-send-email-chris_johnsen@pobox.com","subject":"Re: [PATCH 5/6 (v4)] full integration of rev-cache into git, completed test suite","fromName":"Johannes Sixt","fromEmail":"j.sixt@viscovery.net","sentAt":"2009-09-30T08:09:29Z","receivedAt":"2009-09-30T08:09:29Z","isPatch":true,"sender":{"key":"j6t@kdbg.org","avatar":"https://avatars.githubusercontent.com/u/14810926?v=4"},"body":"Chris Johnsen schrieb:\n> -cache_size=`wc -c .git/rev-cache/$cache_sha1 | grep -o \"[0-9]*\"`\n> +cache_size=`wc -c < .git/rev-cache/$cache_sha1 | tr -d ' '`\n>  test_expect_success 'test --ignore-size function in fuse' '\n>  \tgit-rev-cache fuse --ignore-size=$cache_size 2>output.err &&\n>  \tgrep \"final return value: 0\" output.err &&\n\nYou can also have the shell strip the blanks:\n\ncache_size=$(wc -c < .git/rev-cache/$cache_sha1)\ntest_expect_success 'test --ignore-size function in fuse' '\n\tgit-rev-cache fuse --ignore-size=${cache_size##* } 2>output.err &&\n\tgrep \"final return value: 0\" output.err &&\n\n-- Hannes\n"},{"id":"124154","messageId":"op.u061bkzjtdk399@sirnot.ed.ac.uk","threadId":"20633","inReplyTo":"op.uyuwkuoxtdk399@sirnot.private","subject":"Re: [PATCH 5/6 (v4)] full integration of rev-cache into git, completed test suite","fromName":"Nick Edelen","fromEmail":"sirnot@gmail.com","sentAt":"2009-10-02T22:12:46Z","receivedAt":"2009-10-02T22:12:46Z","isPatch":true,"sender":{"key":"sirnot@gmail.com","avatar":null},"body":"This patch provides a working integration of rev-cache into the revision\nwalker, along with some touch-ups:\n  - integration into revision walker and list-objects\n  - refactor object generation for more coherent code structure\n  - more fluid handling of damaged cache slices (remembering bad slices)\n  - numerous tests for both features from the previous patch, and the\nintegration's integrity\n\n'Integration' is rather broad -- a more detailed description follows for each\naspect:\n  - rev-cache\nthe traversal mechanism is updated to handle many of the non-prune options\nrev-list does (date limiting, slop-handling, etc.), and is adjusted to allow\nfor non-fatal cache-traversal failures.\n\n  - revision walker\nboth limited and unlimited traversal attempt to use the cache when possible,\nsmoothly falling back if it's not.\n\n  - list-objects\nobject listing does not recurse into cached trees, and has been adjusted to\nguarantee commit-tag-tree-blob ordering.\n\nSigned-off-by: Nick Edelen <sirnot@gmail.com>\n\n---\ntweak test for compatability.\n\n  builtin-rev-cache.c       |   40 ++++++++\n  list-objects.c            |   46 ++++++++-\n  rev-cache.c               |  231 +++++++++++++++++++++++++++++++++++++++------\n  revision.c                |   88 ++++++++++++++---\n  t/t6017-rev-cache-list.sh |  151 ++++++++++++++++++++++++++++-\n  5 files changed, 501 insertions(+), 55 deletions(-)\n\ndiff --git a/builtin-rev-cache.c b/builtin-rev-cache.c\nindex b894c54..8f41123 100644\n--- a/builtin-rev-cache.c\n+++ b/builtin-rev-cache.c\n@@ -4,6 +4,7 @@\n  #include \"diff.h\"\n  #include \"revision.h\"\n  #include \"rev-cache.h\"\n+#include \"list-objects.h\"\n\n  unsigned long default_ignore_size = 50 * 1024 * 1024; /* 50mb */\n\n@@ -78,6 +79,43 @@ static int handle_add(int argc, const char *argv[]) /* args beyond this command\n  \treturn 0;\n  }\n\n+static void show_commit(struct commit *commit, void *data)\n+{\n+\tprintf(\"%s\\n\", sha1_to_hex(commit->object.sha1));\n+}\n+\n+static void show_object(struct object *obj, const struct name_path *path, const char *last)\n+{\n+\tprintf(\"%s\\n\", sha1_to_hex(obj->sha1));\n+}\n+\n+static int test_rev_list(int argc, const char *argv[])\n+{\n+\tstruct rev_info revs;\n+\tunsigned int flags = 0;\n+\tint i;\n+\n+\tinit_revisions(&revs, 0);\n+\n+\tfor (i = 0; i < argc; i++) {\n+\t\tif (!strcmp(argv[i], \"--not\"))\n+\t\t\tflags ^= UNINTERESTING;\n+\t\telse if (!strcmp(argv[i], \"--objects\"))\n+\t\t\trevs.tree_objects = revs.blob_objects = 1;\n+\t\telse\n+\t\t\thandle_revision_arg(argv[i], &revs, flags, 1);\n+\t}\n+\n+\tsetup_revisions(0, 0, &revs, 0);\n+\trevs.topo_order = 1;\n+\trevs.lifo = 1;\n+\tprepare_revision_walk(&revs);\n+\n+\ttraverse_commit_list(&revs, show_commit, show_object, 0);\n+\n+\treturn 0;\n+}\n+\n  static int handle_walk(int argc, const char *argv[])\n  {\n  \tstruct commit *commit;\n@@ -271,6 +309,8 @@ int cmd_rev_cache(int argc, const char *argv[], const char *prefix)\n  \t\tr = handle_walk(argc, argv);\n  \telse if (!strcmp(arg, \"index\"))\n  \t\tr = handle_index(argc, argv);\n+\telse if (!strcmp(arg, \"test\"))\n+\t\tr = test_rev_list(argc, argv);\n  \telse if (!strcmp(arg, \"alt\"))\n  \t\tr = handle_alt(argc, argv);\n  \telse\ndiff --git a/list-objects.c b/list-objects.c\nindex 8953548..b8c3370 100644\n--- a/list-objects.c\n+++ b/list-objects.c\n@@ -74,22 +74,34 @@ static void process_tree(struct rev_info *revs,\n  \t\tdie(\"bad tree object\");\n  \tif (obj->flags & (UNINTERESTING | SEEN))\n  \t\treturn;\n+\tif (obj->flags & FACE_VALUE) {\n+\t\tobj->flags |= SEEN;\n+\t\tshow(obj, path, name);\n+\t\t/* not parsing the tree saves a lot of time! */\n+\t\treturn;\n+\t}\n+\n  \tif (parse_tree(tree) < 0)\n  \t\tdie(\"bad tree object %s\", sha1_to_hex(obj->sha1));\n  \tobj->flags |= SEEN;\n  \tshow(obj, path, name);\n+\n  \tme.up = path;\n  \tme.elem = name;\n  \tme.elem_len = strlen(name);\n-\n  \tinit_tree_desc(&desc, tree->buffer, tree->size);\n\n  \twhile (tree_entry(&desc, &entry)) {\n-\t\tif (S_ISDIR(entry.mode))\n+\t\tif (S_ISDIR(entry.mode)) {\n+\t\t\tstruct tree *subtree = lookup_tree(entry.sha1);\n+\t\t\tif (!subtree)\n+\t\t\t\tcontinue;\n+\n+\t\t\tsubtree->object.flags &= ~FACE_VALUE;\n  \t\t\tprocess_tree(revs,\n-\t\t\t\t     lookup_tree(entry.sha1),\n+\t\t\t\t     subtree,\n  \t\t\t\t     show, &me, entry.path);\n-\t\telse if (S_ISGITLINK(entry.mode))\n+\t\t} else if (S_ISGITLINK(entry.mode))\n  \t\t\tprocess_gitlink(revs, entry.sha1,\n  \t\t\t\t\tshow, &me, entry.path);\n  \t\telse\n@@ -136,6 +148,7 @@ void mark_edges_uninteresting(struct commit_list *list,\n\n  static void add_pending_tree(struct rev_info *revs, struct tree *tree)\n  {\n+\ttree->object.flags &= ~FACE_VALUE;\n  \tadd_pending_object(revs, &tree->object, \"\");\n  }\n\n@@ -146,17 +159,27 @@ void traverse_commit_list(struct rev_info *revs,\n  {\n  \tint i;\n  \tstruct commit *commit;\n+\tenum object_type what = OBJ_TAG;\n+\tchar face_value = 0;\n\n  \twhile ((commit = get_revision(revs)) != NULL) {\n-\t\tadd_pending_tree(revs, commit->tree);\n+\t\tif (!(commit->object.flags & FACE_VALUE))\n+\t\t\tadd_pending_tree(revs, commit->tree);\n+\t\telse\n+\t\t\tface_value = 1;\n  \t\tshow_commit(commit, data);\n  \t}\n+\n+loop_objects:\n  \tfor (i = 0; i < revs->pending.nr; i++) {\n  \t\tstruct object_array_entry *pending = revs->pending.objects + i;\n  \t\tstruct object *obj = pending->item;\n  \t\tconst char *name = pending->name;\n  \t\tif (obj->flags & (UNINTERESTING | SEEN))\n  \t\t\tcontinue;\n+\t\tif (obj->type != what && face_value)\n+\t\t\tcontinue;\n+\n  \t\tif (obj->type == OBJ_TAG) {\n  \t\t\tobj->flags |= SEEN;\n  \t\t\tshow_object(obj, NULL, name);\n@@ -175,6 +198,19 @@ void traverse_commit_list(struct rev_info *revs,\n  \t\tdie(\"unknown pending object %s (%s)\",\n  \t\t    sha1_to_hex(obj->sha1), name);\n  \t}\n+\tif (face_value) {\n+\t\tswitch (what) {\n+\t\tcase OBJ_TAG:\n+\t\t\twhat = OBJ_TREE;\n+\t\t\tgoto loop_objects;\n+\t\tcase OBJ_TREE:\n+\t\t\twhat = OBJ_BLOB;\n+\t\t\tgoto loop_objects;\n+\t\tdefault:\n+\t\t\tbreak;\n+\t\t}\n+\t}\n+\n  \tif (revs->pending.nr) {\n  \t\tfree(revs->pending.objects);\n  \t\trevs->pending.nr = 0;\ndiff --git a/rev-cache.c b/rev-cache.c\nindex e401978..4ef5287 100644\n--- a/rev-cache.c\n+++ b/rev-cache.c\n@@ -11,6 +11,12 @@\n  #include \"run-command.h\"\n  #include \"string-list.h\"\n\n+\n+struct bad_slice {\n+\tunsigned char sha1[20];\n+\tstruct bad_slice *next;\n+};\n+\n  struct cache_slice_pointer {\n  \tchar signature[8]; /* REVCOPTR */\n  \tchar version;\n@@ -23,8 +29,9 @@ static uint32_t fanout[0xff + 2];\n  static unsigned char *idx_map;\n  static int idx_size;\n  static struct rc_index_header idx_head;\n+static char no_idx, add_to_pending;\n+static struct bad_slice *bad_slices;\n  static unsigned char *idx_caches;\n-static char no_idx;\n\n  static struct strbuf *acc_buffer;\n\n@@ -121,6 +128,30 @@ struct rc_object_entry_ondisk *to_disked_rc_object_entry(struct rc_object_entry\n  \treturn dst;\n  }\n\n+static void mark_bad_slice(unsigned char *sha1)\n+{\n+\tstruct bad_slice *bad;\n+\n+\tbad = xcalloc(sizeof(struct bad_slice), 1);\n+\thashcpy(bad->sha1, sha1);\n+\n+\tbad->next = bad_slices;\n+\tbad_slices = bad;\n+}\n+\n+static int is_bad_slice(unsigned char *sha1)\n+{\n+\tstruct bad_slice *bad = bad_slices;\n+\n+\twhile (bad) {\n+\t\tif (!hashcmp(bad->sha1, sha1))\n+\t\t\treturn 1;\n+\t\tbad = bad->next;\n+\t}\n+\n+\treturn 0;\n+}\n+\n  static int get_index_head(unsigned char *map, int len, struct rc_index_header *head, uint32_t *fanout, unsigned char **caches)\n  {\n  \tstruct rc_index_header whead;\n@@ -246,6 +277,7 @@ static struct rc_index_entry *search_index(unsigned char *sha1)\n  unsigned char *get_cache_slice(struct commit *commit)\n  {\n  \tstruct rc_index_entry *ie;\n+\tunsigned char *sha1;\n\n  \tif (!idx_map) {\n  \t\tif (no_idx)\n@@ -257,8 +289,13 @@ unsigned char *get_cache_slice(struct commit *commit)\n  \t\treturn 0;\n\n  \tie = search_index(commit->object.sha1);\n-\tif (ie && ie->cache_index < idx_head.cache_nr)\n-\t\treturn idx_caches + ie->cache_index * 20;\n+\tif (ie && ie->cache_index < idx_head.cache_nr) {\n+\t\tsha1 = idx_caches + ie->cache_index * 20;\n+\n+\t\tif (is_bad_slice(sha1))\n+\t\t\treturn 0;\n+\t\treturn sha1;\n+\t}\n\n  \treturn 0;\n  }\n@@ -268,6 +305,20 @@ unsigned char *get_cache_slice(struct commit *commit)\n\n  static unsigned long decode_size(unsigned char *str, int len);\n\n+/* on failure */\n+static void restore_commit(struct commit *commit)\n+{\n+\tcommit->object.flags &= ~(ADDED | SEEN | FACE_VALUE);\n+\n+\tif (!commit->object.parsed) {\n+\t\twhile (pop_commit(&commit->parents))\n+\t\t\t;\n+\n+\t\tparse_commit(commit);\n+\t}\n+\n+}\n+\n  static void handle_noncommit(struct rev_info *revs, struct commit *commit, unsigned char *ptr, struct rc_object_entry *entry)\n  {\n  \tstruct blob *blob;\n@@ -307,23 +358,27 @@ static void handle_noncommit(struct rev_info *revs, struct commit *commit, unsig\n  \t}\n\n  \tobj->flags |= FACE_VALUE;\n-\tadd_pending_object(revs, obj, \"\");\n+\tif (add_to_pending)\n+\t\tadd_pending_object(revs, obj, \"\");\n  }\n\n-static int setup_traversal(struct rc_slice_header *head, unsigned char *map, struct commit *commit, struct commit_list **work)\n+static int setup_traversal(struct rc_slice_header *head, unsigned char *map, struct commit *commit, struct commit_list **work,\n+\tstruct commit_list **unwork, int *ipath_nr, int *upath_nr, char *ioutside)\n  {\n  \tstruct rc_index_entry *iep;\n  \tstruct rc_object_entry *oep;\n  \tstruct commit_list *prev, *wp, **wpp;\n  \tint retval;\n\n-\tiep = search_index(commit->object.sha1), 0;\n+\tiep = search_index(commit->object.sha1);\n  \toep = RC_OBTAIN_OBJECT_ENTRY(map + iep->pos);\n+\tif (commit->object.flags & UNINTERESTING) {\n+\t\t++*upath_nr;\n+\t\toep->uninteresting = 1;\n+\t} else\n+\t\t++*ipath_nr;\n\n-\t/* the .uniniteresting bit isn't strictly necessary, as we check the object during traversal as well,\n-\t * but we might as well initialize it while we're at it */\n  \toep->include = 1;\n-\toep->uninteresting = !!(commit->object.flags & UNINTERESTING);\n  \tto_disked_rc_object_entry(oep, (struct rc_object_entry_ondisk *)(map + iep->pos));\n  \tretval = iep->pos;\n\n@@ -338,6 +393,10 @@ static int setup_traversal(struct rc_slice_header *head, unsigned char *map, str\n  \t\t/* is this in our cache slice? */\n  \t\tiep = search_index(obj->sha1);\n  \t\tif (!iep || hashcmp(idx_caches + iep->cache_index * 20, head->sha1)) {\n+\t\t\t/* there are interesing objects outside the slice */\n+\t\t\tif (!(obj->flags & UNINTERESTING))\n+\t\t\t\t*ioutside = 1;\n+\n  \t\t\tprev = wp;\n  \t\t\twp = wp->next;\n  \t\t\twpp = &wp;\n@@ -354,11 +413,20 @@ static int setup_traversal(struct rc_slice_header *head, unsigned char *map, str\n  \t\toep->uninteresting = !!(obj->flags & UNINTERESTING);\n  \t\tto_disked_rc_object_entry(oep, (struct rc_object_entry_ondisk *)(map + iep->pos));\n\n+\t\t/* count even if not in slice so we can stop enumerating if possible */\n+\t\tif (obj->flags & UNINTERESTING)\n+\t\t\t++*upath_nr;\n+\t\telse\n+\t\t\t++*ipath_nr;\n+\n  \t\t/* remove from work list */\n  \t\tco = pop_commit(wpp);\n  \t\twp = *wpp;\n  \t\tif (prev)\n  \t\t\tprev->next = wp;\n+\n+\t\t/* ...and store in temp list so we can restore work on failure */\n+\t\tcommit_list_insert(co, unwork);\n  \t}\n\n  \treturn retval;\n@@ -375,13 +443,18 @@ static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *m\n  \tunsigned long *date_so_far, int *slop_so_far,\n  \tstruct commit_list ***queue, struct commit_list **work)\n  {\n-\tstruct commit_list *insert_cache = 0;\n+\tstruct commit_list *insert_cache = 0, *myq = 0, **myqp = &myq, *mywork = 0, **myworkp = &mywork, *unwork = 0;\n  \tstruct commit **last_objects, *co;\n-\tint i, total_path_nr = head->path_nr, retval = -1;\n-\tchar consume_children = 0;\n+\tunsigned long date = date_so_far ? *date_so_far : ~0ul;\n+\tint i, ipath_nr = 0, upath_nr = 0, orig_obj_nr = 0,\n+\t\ttotal_path_nr = head->path_nr, retval = -1, slop = slop_so_far ? *slop_so_far : SLOP;\n+\tchar consume_children = 0, ioutside = 0;\n  \tunsigned char *paths;\n\n-\ti = setup_traversal(head, map, commit, work);\n+\t/* take note in case we need to regress */\n+\torig_obj_nr = revs->pending.nr;\n+\n+\ti = setup_traversal(head, map, commit, work, &unwork, &ipath_nr, &upath_nr, &ioutside);\n  \tif (i < 0)\n  \t\treturn -1;\n\n@@ -429,6 +502,7 @@ static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *m\n\n  \t\tif ((paths[path] & IPATH) && (paths[path] & UPATH)) {\n  \t\t\tpaths[path] = UPATH;\n+\t\t\tipath_nr--;\n\n  \t\t\t/* mark edge */\n  \t\t\tif (last_objects[path]) {\n@@ -439,6 +513,7 @@ static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *m\n  \t\t\t\tlast_objects[path]->object.flags &= ~FACE_VALUE;\n  \t\t\t\tlast_objects[path] = 0;\n  \t\t\t}\n+\t\t\tobj->flags |= BOUNDARY;\n  \t\t}\n\n  \t\t/* now we gotta re-assess the whole interesting thing... */\n@@ -462,8 +537,10 @@ static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *m\n  \t\t\t\t\t\tlast_objects[p]->object.flags &= ~FACE_VALUE;\n  \t\t\t\t\t\tlast_objects[p] = 0;\n  \t\t\t\t\t}\n-\t\t\t\t} else if (last_objects[p] && !last_objects[p]->object.parsed)\n+\t\t\t\t\tobj->flags |= BOUNDARY;\n+\t\t\t\t} else if (last_objects[p] && !last_objects[p]->object.parsed) {\n  \t\t\t\t\tcommit_list_insert(co, &last_objects[p]->parents);\n+\t\t\t\t}\n\n  \t\t\t\t/* can't close a merge path until all are parents have been encountered */\n  \t\t\t\tif (GET_COUNT(paths[p])) {\n@@ -473,14 +550,33 @@ static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *m\n  \t\t\t\t\t\tcontinue;\n  \t\t\t\t}\n\n+\t\t\t\tif (paths[p] & IPATH)\n+\t\t\t\t\tipath_nr--;\n+\t\t\t\telse\n+\t\t\t\t\tupath_nr--;\n+\n  \t\t\t\tpaths[p] = 0;\n  \t\t\t\tlast_objects[p] = 0;\n  \t\t\t}\n  \t\t}\n\n  \t\t/* make topo relations */\n-\t\tif (last_objects[path] && !last_objects[path]->object.parsed)\n+\t\tif (last_objects[path] && !last_objects[path]->object.parsed) {\n  \t\t\tcommit_list_insert(co, &last_objects[path]->parents);\n+\t\t}\n+\n+\t\t/* we've been here already */\n+\t\tif (obj->flags & ADDED) {\n+\t\t\tif (entry->uninteresting && !(obj->flags & UNINTERESTING)) {\n+\t\t\t\tobj->flags |= UNINTERESTING;\n+\t\t\t\tmark_parents_uninteresting(co);\n+\t\t\t\tupath_nr--;\n+\t\t\t} else if (!entry->uninteresting)\n+\t\t\t\tipath_nr--;\n+\n+\t\t\tpaths[path] = 0;\n+\t\t\tcontinue;\n+\t\t}\n\n  \t\t/* initialize commit */\n  \t\tif (!entry->is_end) {\n@@ -493,24 +589,51 @@ static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *m\n\n  \t\tif (entry->uninteresting)\n  \t\t\tobj->flags |= UNINTERESTING;\n+\t\telse if (co->date < date)\n+\t\t\tdate = co->date;\n\n  \t\t/* we need to know what the edges are */\n  \t\tlast_objects[path] = co;\n\n  \t\t/* add to list */\n-\t\tif (!(obj->flags & UNINTERESTING) || revs->show_all) {\n-\t\t\tif (entry->is_end)\n-\t\t\t\tinsert_by_date_cached(co, work, insert_cache, &insert_cache);\n-\t\t\telse\n-\t\t\t\t*queue = &commit_list_insert(co, *queue)->next;\n+\t\tif (slop && !(revs->min_age != -1 && co->date > revs->min_age)) {\n+\n+\t\t\tif (!(obj->flags & UNINTERESTING) || revs->show_all) {\n+\t\t\t\tif (entry->is_end)\n+\t\t\t\t\tmyworkp = &commit_list_insert(co, myworkp)->next;\n+\t\t\t\telse\n+\t\t\t\t\tmyqp = &commit_list_insert(co, myqp)->next;\n+\n+\t\t\t\t/* add children to list as well */\n+\t\t\t\tif (obj->flags & UNINTERESTING)\n+\t\t\t\t\tconsume_children = 0;\n+\t\t\t\telse\n+\t\t\t\t\tconsume_children = 1;\n+\t\t\t}\n\n-\t\t\t/* add children to list as well */\n-\t\t\tif (obj->flags & UNINTERESTING)\n-\t\t\t\tconsume_children = 0;\n-\t\t\telse\n-\t\t\t\tconsume_children = 1;\n  \t\t}\n\n+\t\t/* should we continue? */\n+\t\tif (!slop) {\n+\t\t\tif (!upath_nr) {\n+\t\t\t\tbreak;\n+\t\t\t} else if (ioutside || revs->show_all) {\n+\t\t\t\t/* pass it back to rev-list\n+\t\t\t\t * we purposely ignore everything outside this cache, so we don't needlessly traverse the whole\n+\t\t\t\t * thing on uninteresting, but that does mean that we may need to bounce back\n+\t\t\t\t * and forth a few times with rev-list */\n+\t\t\t\tmyworkp = &commit_list_insert(co, myworkp)->next;\n+\n+\t\t\t\tpaths[path] = 0;\n+\t\t\t\tupath_nr--;\n+\t\t\t} else {\n+\t\t\t\tbreak;\n+\t\t\t}\n+\t\t} else if (!ipath_nr && co->date <= date)\n+\t\t\tslop--;\n+\t\telse\n+\t\t\tslop = SLOP;\n+\n  \t\t/* open parents */\n  \t\tif (entry->merge_nr) {\n  \t\t\tint j, off = index + sizeof(struct rc_object_entry_ondisk);\n@@ -525,6 +648,11 @@ static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *m\n  \t\t\t\tif (paths[p] & flag)\n  \t\t\t\t\tcontinue;\n\n+\t\t\t\tif (flag == IPATH)\n+\t\t\t\t\tipath_nr++;\n+\t\t\t\telse\n+\t\t\t\t\tupath_nr++;\n+\n  \t\t\t\tpaths[p] |= flag;\n  \t\t\t}\n\n@@ -534,12 +662,54 @@ static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *m\n\n  \t}\n\n+\tif (date_so_far)\n+\t\t*date_so_far = date;\n+\tif (slop_so_far)\n+\t\t*slop_so_far = slop;\n  \tretval = 0;\n\n+\t/* success: attach to given lists */\n+\tif (myqp != &myq) {\n+\t\t**queue = myq;\n+\t\t*queue = myqp;\n+\t}\n+\n+\twhile ((co = pop_commit(&mywork)) != 0)\n+\t\tinsert_by_date_cached(co, work, insert_cache, &insert_cache);\n+\n+\t/* free backup */\n+\twhile (pop_commit(&unwork))\n+\t\t;\n+\n  end:\n  \tfree(paths);\n  \tfree(last_objects);\n\n+\t/* failure: restore work to previous condition\n+\t * (cache corruption should *not* be fatal) */\n+\tif (retval) {\n+\t\twhile ((co = pop_commit(&unwork)) != 0) {\n+\t\t\trestore_commit(co);\n+\t\t\tco->object.flags |= SEEN;\n+\t\t\tinsert_by_date(co, work);\n+\t\t}\n+\n+\t\t/* free lists */\n+\t\twhile ((co = pop_commit(&myq)) != 0)\n+\t\t\trestore_commit(co);\n+\n+\t\twhile ((co = pop_commit(&mywork)) != 0)\n+\t\t\trestore_commit(co);\n+\n+\t\t/* truncate object array */\n+\t\tfor (i = orig_obj_nr; i < revs->pending.nr; i++) {\n+\t\t\tstruct object *obj = revs->pending.objects[i].item;\n+\n+\t\t\tobj->flags &= ~FACE_VALUE;\n+\t\t}\n+\t\trevs->pending.nr = orig_obj_nr;\n+\t}\n+\n  \treturn retval;\n  }\n\n@@ -630,6 +800,7 @@ int traverse_cache_slice(struct rev_info *revs,\n\n  \t/* load options */\n  \trci = &revs->rev_cache_info;\n+\tadd_to_pending = rci->add_to_pending;\n\n  \tmemset(&head, 0, sizeof(struct rc_slice_header));\n\n@@ -653,6 +824,10 @@ end:\n  \tif (fd != -1)\n  \t\tclose(fd);\n\n+\t/* remember this! */\n+\tif (retval)\n+\t\tmark_bad_slice(cache_sha1);\n+\n  \treturn retval;\n  }\n\n@@ -811,7 +986,7 @@ static void handle_paths(struct commit *commit, struct rc_object_entry *object,\n  \tint child_nr, parent_nr, open_parent_nr, this_path;\n  \tstruct commit_list *list;\n  \tstruct commit *first_parent;\n-\tstruct pa\\th_track **ppt, *pt;\n+\tstruct path_track **ppt, *pt;\n\n  \t/* we can only re-use a closed path once all it's children have been encountered,\n  \t * as we need to keep track of commit boundaries */\n@@ -1128,7 +1303,7 @@ static int add_objects_verbatim_1(struct rev_cache_slice_map *mapping, int *inde\n  \twhile (i < mapping->size) {\n  \t\tint pos = i;\n\n-\t\tentry = RC_OBTAIN_OBJECT_ENTRY(map + i;\n+\t\tentry = RC_OBTAIN_OBJECT_ENTRY(map + i);\n  \t\ti += RC_ACTUAL_OBJECT_ENTRY_SIZE(entry);\n\n  \t\tif (entry->type == OBJ_COMMIT) {\ndiff --git a/revision.c b/revision.c\nindex c7fd35f..ed21885 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -12,6 +12,7 @@\n  #include \"patch-ids.h\"\n  #include \"decorate.h\"\n  #include \"log-tree.h\"\n+#include \"rev-cache.h\"\n\n  volatile show_early_output_fn_t show_early_output;\n\n@@ -638,6 +639,8 @@ static int limit_list(struct rev_info *revs)\n  \tstruct commit_list *list = revs->commits;\n  \tstruct commit_list *newlist = NULL;\n  \tstruct commit_list **p = &newlist;\n+\tunsigned char *cache_sha1;\n+\tchar used_cache;\n\n  \twhile (list) {\n  \t\tstruct commit_list *entry = list;\n@@ -650,24 +653,39 @@ static int limit_list(struct rev_info *revs)\n\n  \t\tif (revs->max_age != -1 && (commit->date < revs->max_age))\n  \t\t\tobj->flags |= UNINTERESTING;\n-\t\tif (add_parents_to_list(revs, commit, &list, NULL) < 0)\n-\t\t\treturn -1;\n-\t\tif (obj->flags & UNINTERESTING) {\n-\t\t\tmark_parents_uninteresting(commit);\n-\t\t\tif (revs->show_all)\n-\t\t\t\tp = &commit_list_insert(commit, p)->next;\n-\t\t\tslop = still_interesting(list, date, slop);\n-\t\t\tif (slop)\n+\n+\t\t/* rev-cache to the rescue!!! */\n+\t\tused_cache = 0;\n+\t\tif (!revs->dont_cache_me && !(obj->flags & ADDED)) {\n+\t\t\tcache_sha1 = get_cache_slice(commit);\n+\t\t\tif (cache_sha1) {\n+\t\t\t\tif (traverse_cache_slice(revs, cache_sha1, commit, &date, &slop, &p, &list) < 0)\n+\t\t\t\t\tused_cache = 0;\n+\t\t\t\telse\n+\t\t\t\t\tused_cache = 1;\n+\t\t\t}\n+\t\t}\n+\n+\t\tif (!used_cache) {\n+\t\t\tif (add_parents_to_list(revs, commit, &list, NULL) < 0)\n+\t\t\t\treturn -1;\n+\t\t\tif (obj->flags & UNINTERESTING) {\n+\t\t\t\tmark_parents_uninteresting(commit); /* ME: why? */\n+\t\t\t\tif (revs->show_all)\n+\t\t\t\t\tp = &commit_list_insert(commit, p)->next;\n+\t\t\t\tslop = still_interesting(list, date, slop);\n+\t\t\t\tif (slop > 0)\n+\t\t\t\t\tcontinue;\n+\t\t\t\t/* If showing all, add the whole pending list to the end */\n+\t\t\t\tif (revs->show_all)\n+\t\t\t\t\t*p = list;\n+\t\t\t\tbreak;\n+\t\t\t}\n+\t\t\tif (revs->min_age != -1 && (commit->date > revs->min_age))\n  \t\t\t\tcontinue;\n-\t\t\t/* If showing all, add the whole pending list to the end */\n-\t\t\tif (revs->show_all)\n-\t\t\t\t*p = list;\n-\t\t\tbreak;\n+\t\t\tdate = commit->date;\n+\t\t\tp = &commit_list_insert(commit, p)->next;\n  \t\t}\n-\t\tif (revs->min_age != -1 && (commit->date > revs->min_age))\n-\t\t\tcontinue;\n-\t\tdate = commit->date;\n-\t\tp = &commit_list_insert(commit, p)->next;\n\n  \t\tshow = show_early_output;\n  \t\tif (!show)\n@@ -813,6 +831,8 @@ void init_revisions(struct rev_info *revs, const char *prefix)\n  \t\trevs->diffopt.prefix = prefix;\n  \t\trevs->diffopt.prefix_length = strlen(prefix);\n  \t}\n+\n+\tinit_rev_cache_info(&revs->rev_cache_info);\n  }\n\n  static void add_pending_commit_list(struct rev_info *revs,\n@@ -1372,6 +1392,11 @@ int setup_revisions(int argc, const char **argv, struct rev_info *revs, const ch\n  \tif (revs->reflog_info && revs->graph)\n  \t\tdie(\"cannot combine --walk-reflogs with --graph\");\n\n+\t/* limits on caching\n+\t * todo: implement this functionality */\n+\tif (revs->prune || revs->diff)\n+\t\trevs->dont_cache_me = 1;\n+\n  \treturn left;\n  }\n\n@@ -1654,6 +1679,8 @@ static int commit_match(struct commit *commit, struct rev_info *opt)\n  {\n  \tif (!opt->grep_filter.pattern_list)\n  \t\treturn 1;\n+\tif (!commit->object.parsed)\n+\t\tparse_commit(commit);\n  \treturn grep_buffer(&opt->grep_filter,\n  \t\t\t   NULL, /* we say nothing, not even filename */\n  \t\t\t   commit->buffer, strlen(commit->buffer));\n@@ -1717,6 +1744,7 @@ static struct commit *get_revision_1(struct rev_info *revs)\n  \tdo {\n  \t\tstruct commit_list *entry = revs->commits;\n  \t\tstruct commit *commit = entry->item;\n+\t\tstruct object *obj = &commit->object;\n\n  \t\trevs->commits = entry->next;\n  \t\tfree(entry);\n@@ -1733,11 +1761,39 @@ static struct commit *get_revision_1(struct rev_info *revs)\n  \t\t\tif (revs->max_age != -1 &&\n  \t\t\t    (commit->date < revs->max_age))\n  \t\t\t\tcontinue;\n+\n+\t\t\tif (!revs->dont_cache_me) {\n+\t\t\t\tstruct commit_list *queue = 0, **queuep = &queue;\n+\t\t\t\tunsigned char *cache_sha1;\n+\n+\t\t\t\tif (obj->flags & ADDED)\n+\t\t\t\t\tgoto skip_parenting;\n+\n+\t\t\t\tcache_sha1 = get_cache_slice(commit);\n+\t\t\t\tif (cache_sha1) {\n+\t\t\t\t\tif (!traverse_cache_slice(revs, cache_sha1, commit, 0, 0, &queuep, &revs->commits)) {\n+\t\t\t\t\t\tstruct commit_list *work = revs->commits;\n+\n+\t\t\t\t\t\t/* attach queue to end of ->commits */\n+\t\t\t\t\t\twhile (work && work->next)\n+\t\t\t\t\t\t\twork = work->next;\n+\n+\t\t\t\t\t\tif (work)\n+\t\t\t\t\t\t\twork->next = queue;\n+\t\t\t\t\t\telse\n+\t\t\t\t\t\t\trevs->commits = queue;\n+\n+\t\t\t\t\t\tgoto skip_parenting;\n+\t\t\t\t\t}\n+\t\t\t\t}\n+\t\t\t}\n+\n  \t\t\tif (add_parents_to_list(revs, commit, &revs->commits, NULL) < 0)\n  \t\t\t\tdie(\"Failed to traverse parents of commit %s\",\n  \t\t\t\t    sha1_to_hex(commit->object.sha1));\n  \t\t}\n\n+skip_parenting:\n  \t\tswitch (simplify_commit(revs, commit)) {\n  \t\tcase commit_ignore:\n  \t\t\tcontinue;\ndiff --git a/t/t6017-rev-cache-list.sh b/t/t6017-rev-cache-list.sh\nindex dc0fc07..982fb15 100755\n--- a/t/t6017-rev-cache-list.sh\n+++ b/t/t6017-rev-cache-list.sh\n@@ -38,6 +38,7 @@ test_expect_success 'init repo' '\n  \tgit add . &&\n  \tgit commit -m \"omg\" &&\n\n+\tsleep 2 &&\n  \tgit branch b4 &&\n  \tgit checkout b4 &&\n  \techo shazam >file8 &&\n@@ -46,7 +47,7 @@ test_expect_success 'init repo' '\n  \tgit merge -m \"merge b2\" b2 &&\n\n  \techo bam >smoke/pipe &&\n-\tgit add .\n+\tgit add . &&\n  \tgit commit -m \"bam\" &&\n\n  \tgit checkout master &&\n@@ -71,18 +72,26 @@ test_expect_success 'init repo' '\n  \tgit add . &&\n  \tgit commit -m \"lol\" &&\n\n+\tsleep 2 &&\n  \tgit checkout master &&\n  \tgit merge -m \"triple merge\" b1 b11 &&\n  \tgit rm -r d1 &&\n+\tsleep 2 &&\n  \tgit commit -a -m \"oh noes\"\n  '\n\n-git-rev-list HEAD --not HEAD~3 >proper_commit_list_limited\n-git-rev-list HEAD >proper_commit_list\n-git-rev-list HEAD --objects >proper_object_list\n+max_date=`git-rev-list --timestamp HEAD~1 --max-count=1 | grep -e \"^[0-9]*\" -o`\n+min_date=`git-rev-list --timestamp b4 --max-count=1 | grep -e \"^[0-9]*\" -o`\n+\n+git-rev-list --topo-order HEAD --not HEAD~3 >proper_commit_list_limited\n+git-rev-list --topo-order HEAD --not HEAD~2 >proper_commit_list_limited2\n+git-rev-list --topo-order HEAD >proper_commit_list\n+git-rev-list --objects HEAD >proper_object_list\n+git-rev-list HEAD --max-age=$min_date --min-age=$max_date >proper_list_date_limited\n+\n+cache_sha1=`git-rev-cache add HEAD 2>output.err`\n\n  test_expect_success 'make cache slice' '\n-\tgit-rev-cache add HEAD 2>output.err &&\n  \tgrep \"final return value: 0\" output.err\n  '\n\n@@ -102,11 +111,141 @@ test_expect_success 'test rev-caches walker directly (unlimited)' '\n  \ttest_cmp_sorted list proper_commit_list\n  '\n\n+test_expect_success 'test rev-list traversal (limited)' '\n+\tgit-rev-list HEAD --not HEAD~3 >list &&\n+\ttest_cmp list proper_commit_list_limited\n+'\n+\n+test_expect_success 'test rev-list traversal (unlimited)' '\n+\tgit-rev-list HEAD >list &&\n+\ttest_cmp list proper_commit_list\n+'\n+\n  #do the same for objects\n  test_expect_success 'test rev-caches walker with objects' '\n  \tgit-rev-cache walk --objects HEAD >list &&\n  \ttest_cmp_sorted list proper_object_list\n  '\n\n-test_done\n+test_expect_success 'test rev-list with objects (topo order)' '\n+\tgit-rev-list --topo-order --objects HEAD >list &&\n+\ttest_cmp_sorted list proper_object_list\n+'\n+\n+test_expect_success 'test rev-list with objects (no order)' '\n+\tgit-rev-list --objects HEAD >list &&\n+\ttest_cmp_sorted list proper_object_list\n+'\n+\n+#verify age limiting\n+test_expect_success 'test rev-list date limiting (topo order)' '\n+\tgit-rev-list --topo-order --max-age=$min_date --min-age=$max_date HEAD >list &&\n+\ttest_cmp_sorted list proper_list_date_limited\n+'\n+\n+test_expect_success 'test rev-list date limiting (no order)' '\n+\tgit-rev-list --max-age=$min_date --min-age=$max_date HEAD >list &&\n+\ttest_cmp_sorted list proper_list_date_limited\n+'\n+\n+#check partial cache slice\n+test_expect_success 'saving old cache and generating partial slice' '\n+\tcp \".git/rev-cache/$cache_sha1\" .git/rev-cache/.old &&\n+\trm \".git/rev-cache/$cache_sha1\" .git/rev-cache/index &&\n+\n+\tgit-rev-cache add HEAD~2 2>output.err &&\n+\tgrep \"final return value: 0\" output.err\n+'\n+\n+test_expect_success 'rev-list with wholly interesting partial slice' '\n+\tgit-rev-list --topo-order HEAD >list &&\n+\ttest_cmp list proper_commit_list\n+'\n+\n+test_expect_success 'rev-list with partly uninteresting partial slice' '\n+\tgit-rev-list --topo-order HEAD --not HEAD~3 >list &&\n+\ttest_cmp list proper_commit_list_limited\n+'\n+\n+test_expect_success 'rev-list with wholly uninteresting partial slice' '\n+\tgit-rev-list --topo-order HEAD --not HEAD~2 >list &&\n+\ttest_cmp list proper_commit_list_limited2\n+'\n+\n+#try out index generation and fuse (note that --all == HEAD in this case)\n+#probably should make a test for that too...\n+test_expect_success 'test (non-)fusion of one slice' '\n+\tgit-rev-cache fuse >output.err &&\n+\tgrep \"nothing to fuse\" output.err\n+'\n\n+test_expect_success 'make fresh slice' '\n+\tgit-rev-cache add --all --fresh 2>output.err &&\n+\tgrep \"final return value: 0\" output.err\n+'\n+\n+test_expect_success 'check dual slices' '\n+\tgit-rev-list --topo-order HEAD~2 HEAD >list &&\n+\ttest_cmp list proper_commit_list\n+'\n+\n+test_expect_success 'regenerate index' '\n+\trm .git/rev-cache/index &&\n+\tgit-rev-cache index 2>output.err &&\n+\tgrep \"final return value: 0\" output.err\n+'\n+\n+test_expect_success 'fuse slices' '\n+\ttest -e .git/rev-cache/.old &&\n+\tgit-rev-cache fuse 2>output.err &&\n+\tgrep \"final return value: 0\" output.err &&\n+\ttest_cmp .git/rev-cache/$cache_sha1 .git/rev-cache/.old\n+'\n+\n+#make sure we can smoothly handle corrupted caches\n+test_expect_success 'corrupt slice' '\n+\techo bla >.git/rev-cache/$cache_sha1\n+'\n+\n+test_expect_success 'test rev-list traversal (limited) (corrupt slice)' '\n+\tgit-rev-list --topo-order HEAD --not HEAD~3 >list &&\n+\ttest_cmp list proper_commit_list_limited\n+'\n+\n+test_expect_success 'test rev-list traversal (unlimited) (corrupt slice)' '\n+\tgit-rev-list HEAD >list &&\n+\ttest_cmp_sorted list proper_commit_list\n+'\n+\n+test_expect_success 'corrupt index' '\n+\techo blu >.git/rev-cache/index\n+'\n+\n+test_expect_success 'test rev-list traversal (limited) (corrupt index)' '\n+\tgit-rev-list --topo-order HEAD --not HEAD~3 >list &&\n+\ttest_cmp list proper_commit_list_limited\n+'\n+\n+test_expect_success 'test rev-list traversal (unlimited) (corrupt index)' '\n+\tgit-rev-list HEAD >list &&\n+\ttest_cmp_sorted list proper_commit_list\n+'\n+\n+#test --ignore-size in fuse\n+rm .git/rev-cache/*\n+cache_sha1=`git-rev-cache add HEAD~2 2>output.err`\n+\n+test_expect_success 'make fragmented slices' '\n+\tgit-rev-cache add HEAD~1 --not HEAD~2 2>>output.err &&\n+\tgit-rev-cache add HEAD --fresh 2>>output.err &&\n+\ttest `grep \"final return value: 0\" output.err | wc -l` -eq 3\n+'\n+\n+cache_size=$(wc -c < .git/rev-cache/$cache_sha1)\n+test_expect_success 'test --ignore-size function in fuse' '\n+\tgit-rev-cache fuse --ignore-size=$cache_size 2>output.err &&\n+\tgrep \"final return value: 0\" output.err &&\n+\ttest -e .git/rev-cache/$cache_sha1\n+'\n+\n+test_done\n-- \ntg: (13365da..) t/revcache/integration (depends on: t/revcache/misc)\n"},{"id":"125420","messageId":"4ADCCC62.8060601@gmail.com","threadId":"20633","inReplyTo":"op.uys3quhbtdk399@sirnot.private","subject":"Re: [PATCH 5/6 (v4)] full integration of rev-cache into git, completed test suite","fromName":"Nick Edelen","fromEmail":"sirnot@gmail.com","sentAt":"2009-10-19T20:30:26Z","receivedAt":"2009-10-19T20:30:26Z","isPatch":true,"sender":{"key":"sirnot@gmail.com","avatar":null},"body":"This patch provides a working integration of rev-cache into the revision \nwalker, along with some touch-ups:\n - integration into revision walker and list-objects\n - tweak of object generation\n - more fluid handling of damaged cache slices\n - numerous tests for both features from the previous patch, and the \nintegration's integrity\n\n'Integration' is rather broad -- a more detailed description follows for each \naspect:\n - rev-cache\nthe traversal mechanism is updated to handle many of the non-prune options \nrev-list does (date limiting, slop-handling, etc.), and is adjusted to allow \nfor non-fatal cache-traversal failures.\n\n - revision walker\nboth limited and unlimited traversal attempt to use the cache when possible, \nsmoothly falling back if it's not.\n\n - list-objects\nobject listing does not recurse into cached trees, and has been adjusted to \nguarantee commit-tag-tree-blob ordering.\n\nSigned-off-by: Nick Edelen <sirnot@gmail.com>\n\n---\ntweak test for compatability.\n\n builtin-rev-cache.c       |   40 ++++++++\n list-objects.c            |   46 ++++++++-\n rev-cache.c               |  229 +++++++++++++++++++++++++++++++++++++++------\n revision.c                |   88 ++++++++++++++---\n t/t6017-rev-cache-list.sh |  151 ++++++++++++++++++++++++++++-\n 5 files changed, 500 insertions(+), 54 deletions(-)\n\ndiff --git a/builtin-rev-cache.c b/builtin-rev-cache.c\nindex b894c54..8f41123 100644\n--- a/builtin-rev-cache.c\n+++ b/builtin-rev-cache.c\n@@ -4,6 +4,7 @@\n #include \"diff.h\"\n #include \"revision.h\"\n #include \"rev-cache.h\"\n+#include \"list-objects.h\"\n \n unsigned long default_ignore_size = 50 * 1024 * 1024; /* 50mb */\n \n@@ -78,6 +79,43 @@ static int handle_add(int argc, const char *argv[]) /* args beyond this command\n \treturn 0;\n }\n \n+static void show_commit(struct commit *commit, void *data)\n+{\n+\tprintf(\"%s\\n\", sha1_to_hex(commit->object.sha1));\n+}\n+\n+static void show_object(struct object *obj, const struct name_path *path, const char *last)\n+{\n+\tprintf(\"%s\\n\", sha1_to_hex(obj->sha1));\n+}\n+\n+static int test_rev_list(int argc, const char *argv[])\n+{\n+\tstruct rev_info revs;\n+\tunsigned int flags = 0;\n+\tint i;\n+\n+\tinit_revisions(&revs, 0);\n+\n+\tfor (i = 0; i < argc; i++) {\n+\t\tif (!strcmp(argv[i], \"--not\"))\n+\t\t\tflags ^= UNINTERESTING;\n+\t\telse if (!strcmp(argv[i], \"--objects\"))\n+\t\t\trevs.tree_objects = revs.blob_objects = 1;\n+\t\telse\n+\t\t\thandle_revision_arg(argv[i], &revs, flags, 1);\n+\t}\n+\n+\tsetup_revisions(0, 0, &revs, 0);\n+\trevs.topo_order = 1;\n+\trevs.lifo = 1;\n+\tprepare_revision_walk(&revs);\n+\n+\ttraverse_commit_list(&revs, show_commit, show_object, 0);\n+\n+\treturn 0;\n+}\n+\n static int handle_walk(int argc, const char *argv[])\n {\n \tstruct commit *commit;\n@@ -271,6 +309,8 @@ int cmd_rev_cache(int argc, const char *argv[], const char *prefix)\n \t\tr = handle_walk(argc, argv);\n \telse if (!strcmp(arg, \"index\"))\n \t\tr = handle_index(argc, argv);\n+\telse if (!strcmp(arg, \"test\"))\n+\t\tr = test_rev_list(argc, argv);\n \telse if (!strcmp(arg, \"alt\"))\n \t\tr = handle_alt(argc, argv);\n \telse\ndiff --git a/list-objects.c b/list-objects.c\nindex 8953548..b8c3370 100644\n--- a/list-objects.c\n+++ b/list-objects.c\n@@ -74,22 +74,34 @@ static void process_tree(struct rev_info *revs,\n \t\tdie(\"bad tree object\");\n \tif (obj->flags & (UNINTERESTING | SEEN))\n \t\treturn;\n+\tif (obj->flags & FACE_VALUE) {\n+\t\tobj->flags |= SEEN;\n+\t\tshow(obj, path, name);\n+\t\t/* not parsing the tree saves a lot of time! */\n+\t\treturn;\n+\t}\n+\n \tif (parse_tree(tree) < 0)\n \t\tdie(\"bad tree object %s\", sha1_to_hex(obj->sha1));\n \tobj->flags |= SEEN;\n \tshow(obj, path, name);\n+\n \tme.up = path;\n \tme.elem = name;\n \tme.elem_len = strlen(name);\n-\n \tinit_tree_desc(&desc, tree->buffer, tree->size);\n \n \twhile (tree_entry(&desc, &entry)) {\n-\t\tif (S_ISDIR(entry.mode))\n+\t\tif (S_ISDIR(entry.mode)) {\n+\t\t\tstruct tree *subtree = lookup_tree(entry.sha1);\n+\t\t\tif (!subtree)\n+\t\t\t\tcontinue;\n+\n+\t\t\tsubtree->object.flags &= ~FACE_VALUE;\n \t\t\tprocess_tree(revs,\n-\t\t\t\t     lookup_tree(entry.sha1),\n+\t\t\t\t     subtree,\n \t\t\t\t     show, &me, entry.path);\n-\t\telse if (S_ISGITLINK(entry.mode))\n+\t\t} else if (S_ISGITLINK(entry.mode))\n \t\t\tprocess_gitlink(revs, entry.sha1,\n \t\t\t\t\tshow, &me, entry.path);\n \t\telse\n@@ -136,6 +148,7 @@ void mark_edges_uninteresting(struct commit_list *list,\n \n static void add_pending_tree(struct rev_info *revs, struct tree *tree)\n {\n+\ttree->object.flags &= ~FACE_VALUE;\n \tadd_pending_object(revs, &tree->object, \"\");\n }\n \n@@ -146,17 +159,27 @@ void traverse_commit_list(struct rev_info *revs,\n {\n \tint i;\n \tstruct commit *commit;\n+\tenum object_type what = OBJ_TAG;\n+\tchar face_value = 0;\n \n \twhile ((commit = get_revision(revs)) != NULL) {\n-\t\tadd_pending_tree(revs, commit->tree);\n+\t\tif (!(commit->object.flags & FACE_VALUE))\n+\t\t\tadd_pending_tree(revs, commit->tree);\n+\t\telse\n+\t\t\tface_value = 1;\n \t\tshow_commit(commit, data);\n \t}\n+\n+loop_objects:\n \tfor (i = 0; i < revs->pending.nr; i++) {\n \t\tstruct object_array_entry *pending = revs->pending.objects + i;\n \t\tstruct object *obj = pending->item;\n \t\tconst char *name = pending->name;\n \t\tif (obj->flags & (UNINTERESTING | SEEN))\n \t\t\tcontinue;\n+\t\tif (obj->type != what && face_value)\n+\t\t\tcontinue;\n+\n \t\tif (obj->type == OBJ_TAG) {\n \t\t\tobj->flags |= SEEN;\n \t\t\tshow_object(obj, NULL, name);\n@@ -175,6 +198,19 @@ void traverse_commit_list(struct rev_info *revs,\n \t\tdie(\"unknown pending object %s (%s)\",\n \t\t    sha1_to_hex(obj->sha1), name);\n \t}\n+\tif (face_value) {\n+\t\tswitch (what) {\n+\t\tcase OBJ_TAG:\n+\t\t\twhat = OBJ_TREE;\n+\t\t\tgoto loop_objects;\n+\t\tcase OBJ_TREE:\n+\t\t\twhat = OBJ_BLOB;\n+\t\t\tgoto loop_objects;\n+\t\tdefault:\n+\t\t\tbreak;\n+\t\t}\n+\t}\n+\n \tif (revs->pending.nr) {\n \t\tfree(revs->pending.objects);\n \t\trevs->pending.nr = 0;\ndiff --git a/rev-cache.c b/rev-cache.c\nindex 6e19fbb..4ef5287 100644\n--- a/rev-cache.c\n+++ b/rev-cache.c\n@@ -11,6 +11,12 @@\n #include \"run-command.h\"\n #include \"string-list.h\"\n \n+\n+struct bad_slice {\n+\tunsigned char sha1[20];\n+\tstruct bad_slice *next;\n+};\n+\n struct cache_slice_pointer {\n \tchar signature[8]; /* REVCOPTR */\n \tchar version;\n@@ -23,8 +29,9 @@ static uint32_t fanout[0xff + 2];\n static unsigned char *idx_map;\n static int idx_size;\n static struct rc_index_header idx_head;\n+static char no_idx, add_to_pending;\n+static struct bad_slice *bad_slices;\n static unsigned char *idx_caches;\n-static char no_idx;\n \n static struct strbuf *acc_buffer;\n \n@@ -121,6 +128,30 @@ struct rc_object_entry_ondisk *to_disked_rc_object_entry(struct rc_object_entry\n \treturn dst;\n }\n \n+static void mark_bad_slice(unsigned char *sha1)\n+{\n+\tstruct bad_slice *bad;\n+\n+\tbad = xcalloc(sizeof(struct bad_slice), 1);\n+\thashcpy(bad->sha1, sha1);\n+\n+\tbad->next = bad_slices;\n+\tbad_slices = bad;\n+}\n+\n+static int is_bad_slice(unsigned char *sha1)\n+{\n+\tstruct bad_slice *bad = bad_slices;\n+\n+\twhile (bad) {\n+\t\tif (!hashcmp(bad->sha1, sha1))\n+\t\t\treturn 1;\n+\t\tbad = bad->next;\n+\t}\n+\n+\treturn 0;\n+}\n+\n static int get_index_head(unsigned char *map, int len, struct rc_index_header *head, uint32_t *fanout, unsigned char **caches)\n {\n \tstruct rc_index_header whead;\n@@ -246,6 +277,7 @@ static struct rc_index_entry *search_index(unsigned char *sha1)\n unsigned char *get_cache_slice(struct commit *commit)\n {\n \tstruct rc_index_entry *ie;\n+\tunsigned char *sha1;\n \n \tif (!idx_map) {\n \t\tif (no_idx)\n@@ -257,8 +289,13 @@ unsigned char *get_cache_slice(struct commit *commit)\n \t\treturn 0;\n \n \tie = search_index(commit->object.sha1);\n-\tif (ie && ie->cache_index < idx_head.cache_nr)\n-\t\treturn idx_caches + ie->cache_index * 20;\n+\tif (ie && ie->cache_index < idx_head.cache_nr) {\n+\t\tsha1 = idx_caches + ie->cache_index * 20;\n+\n+\t\tif (is_bad_slice(sha1))\n+\t\t\treturn 0;\n+\t\treturn sha1;\n+\t}\n \n \treturn 0;\n }\n@@ -268,6 +305,20 @@ unsigned char *get_cache_slice(struct commit *commit)\n \n static unsigned long decode_size(unsigned char *str, int len);\n \n+/* on failure */\n+static void restore_commit(struct commit *commit)\n+{\n+\tcommit->object.flags &= ~(ADDED | SEEN | FACE_VALUE);\n+\n+\tif (!commit->object.parsed) {\n+\t\twhile (pop_commit(&commit->parents))\n+\t\t\t;\n+\n+\t\tparse_commit(commit);\n+\t}\n+\n+}\n+\n static void handle_noncommit(struct rev_info *revs, struct commit *commit, unsigned char *ptr, struct rc_object_entry *entry)\n {\n \tstruct blob *blob;\n@@ -307,23 +358,27 @@ static void handle_noncommit(struct rev_info *revs, struct commit *commit, unsig\n \t}\n \n \tobj->flags |= FACE_VALUE;\n-\tadd_pending_object(revs, obj, \"\");\n+\tif (add_to_pending)\n+\t\tadd_pending_object(revs, obj, \"\");\n }\n \n-static int setup_traversal(struct rc_slice_header *head, unsigned char *map, struct commit *commit, struct commit_list **work)\n+static int setup_traversal(struct rc_slice_header *head, unsigned char *map, struct commit *commit, struct commit_list **work,\n+\tstruct commit_list **unwork, int *ipath_nr, int *upath_nr, char *ioutside)\n {\n \tstruct rc_index_entry *iep;\n \tstruct rc_object_entry *oep;\n \tstruct commit_list *prev, *wp, **wpp;\n \tint retval;\n \n-\tiep = search_index(commit->object.sha1), 0;\n+\tiep = search_index(commit->object.sha1);\n \toep = RC_OBTAIN_OBJECT_ENTRY(map + iep->pos);\n+\tif (commit->object.flags & UNINTERESTING) {\n+\t\t++*upath_nr;\n+\t\toep->uninteresting = 1;\n+\t} else\n+\t\t++*ipath_nr;\n \n-\t/* the .uniniteresting bit isn't strictly necessary, as we check the object during traversal as well,\n-\t * but we might as well initialize it while we're at it */\n \toep->include = 1;\n-\toep->uninteresting = !!(commit->object.flags & UNINTERESTING);\n \tto_disked_rc_object_entry(oep, (struct rc_object_entry_ondisk *)(map + iep->pos));\n \tretval = iep->pos;\n \n@@ -338,6 +393,10 @@ static int setup_traversal(struct rc_slice_header *head, unsigned char *map, str\n \t\t/* is this in our cache slice? */\n \t\tiep = search_index(obj->sha1);\n \t\tif (!iep || hashcmp(idx_caches + iep->cache_index * 20, head->sha1)) {\n+\t\t\t/* there are interesing objects outside the slice */\n+\t\t\tif (!(obj->flags & UNINTERESTING))\n+\t\t\t\t*ioutside = 1;\n+\n \t\t\tprev = wp;\n \t\t\twp = wp->next;\n \t\t\twpp = &wp;\n@@ -354,11 +413,20 @@ static int setup_traversal(struct rc_slice_header *head, unsigned char *map, str\n \t\toep->uninteresting = !!(obj->flags & UNINTERESTING);\n \t\tto_disked_rc_object_entry(oep, (struct rc_object_entry_ondisk *)(map + iep->pos));\n \n+\t\t/* count even if not in slice so we can stop enumerating if possible */\n+\t\tif (obj->flags & UNINTERESTING)\n+\t\t\t++*upath_nr;\n+\t\telse\n+\t\t\t++*ipath_nr;\n+\n \t\t/* remove from work list */\n \t\tco = pop_commit(wpp);\n \t\twp = *wpp;\n \t\tif (prev)\n \t\t\tprev->next = wp;\n+\n+\t\t/* ...and store in temp list so we can restore work on failure */\n+\t\tcommit_list_insert(co, unwork);\n \t}\n \n \treturn retval;\n@@ -375,13 +443,18 @@ static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *m\n \tunsigned long *date_so_far, int *slop_so_far,\n \tstruct commit_list ***queue, struct commit_list **work)\n {\n-\tstruct commit_list *insert_cache = 0;\n+\tstruct commit_list *insert_cache = 0, *myq = 0, **myqp = &myq, *mywork = 0, **myworkp = &mywork, *unwork = 0;\n \tstruct commit **last_objects, *co;\n-\tint i, total_path_nr = head->path_nr, retval = -1;\n-\tchar consume_children = 0;\n+\tunsigned long date = date_so_far ? *date_so_far : ~0ul;\n+\tint i, ipath_nr = 0, upath_nr = 0, orig_obj_nr = 0,\n+\t\ttotal_path_nr = head->path_nr, retval = -1, slop = slop_so_far ? *slop_so_far : SLOP;\n+\tchar consume_children = 0, ioutside = 0;\n \tunsigned char *paths;\n \n-\ti = setup_traversal(head, map, commit, work);\n+\t/* take note in case we need to regress */\n+\torig_obj_nr = revs->pending.nr;\n+\n+\ti = setup_traversal(head, map, commit, work, &unwork, &ipath_nr, &upath_nr, &ioutside);\n \tif (i < 0)\n \t\treturn -1;\n \n@@ -429,6 +502,7 @@ static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *m\n \n \t\tif ((paths[path] & IPATH) && (paths[path] & UPATH)) {\n \t\t\tpaths[path] = UPATH;\n+\t\t\tipath_nr--;\n \n \t\t\t/* mark edge */\n \t\t\tif (last_objects[path]) {\n@@ -439,6 +513,7 @@ static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *m\n \t\t\t\tlast_objects[path]->object.flags &= ~FACE_VALUE;\n \t\t\t\tlast_objects[path] = 0;\n \t\t\t}\n+\t\t\tobj->flags |= BOUNDARY;\n \t\t}\n \n \t\t/* now we gotta re-assess the whole interesting thing... */\n@@ -462,8 +537,10 @@ static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *m\n \t\t\t\t\t\tlast_objects[p]->object.flags &= ~FACE_VALUE;\n \t\t\t\t\t\tlast_objects[p] = 0;\n \t\t\t\t\t}\n-\t\t\t\t} else if (last_objects[p] && !last_objects[p]->object.parsed)\n+\t\t\t\t\tobj->flags |= BOUNDARY;\n+\t\t\t\t} else if (last_objects[p] && !last_objects[p]->object.parsed) {\n \t\t\t\t\tcommit_list_insert(co, &last_objects[p]->parents);\n+\t\t\t\t}\n \n \t\t\t\t/* can't close a merge path until all are parents have been encountered */\n \t\t\t\tif (GET_COUNT(paths[p])) {\n@@ -473,14 +550,33 @@ static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *m\n \t\t\t\t\t\tcontinue;\n \t\t\t\t}\n \n+\t\t\t\tif (paths[p] & IPATH)\n+\t\t\t\t\tipath_nr--;\n+\t\t\t\telse\n+\t\t\t\t\tupath_nr--;\n+\n \t\t\t\tpaths[p] = 0;\n \t\t\t\tlast_objects[p] = 0;\n \t\t\t}\n \t\t}\n \n \t\t/* make topo relations */\n-\t\tif (last_objects[path] && !last_objects[path]->object.parsed)\n+\t\tif (last_objects[path] && !last_objects[path]->object.parsed) {\n \t\t\tcommit_list_insert(co, &last_objects[path]->parents);\n+\t\t}\n+\n+\t\t/* we've been here already */\n+\t\tif (obj->flags & ADDED) {\n+\t\t\tif (entry->uninteresting && !(obj->flags & UNINTERESTING)) {\n+\t\t\t\tobj->flags |= UNINTERESTING;\n+\t\t\t\tmark_parents_uninteresting(co);\n+\t\t\t\tupath_nr--;\n+\t\t\t} else if (!entry->uninteresting)\n+\t\t\t\tipath_nr--;\n+\n+\t\t\tpaths[path] = 0;\n+\t\t\tcontinue;\n+\t\t}\n \n \t\t/* initialize commit */\n \t\tif (!entry->is_end) {\n@@ -493,24 +589,51 @@ static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *m\n \n \t\tif (entry->uninteresting)\n \t\t\tobj->flags |= UNINTERESTING;\n+\t\telse if (co->date < date)\n+\t\t\tdate = co->date;\n \n \t\t/* we need to know what the edges are */\n \t\tlast_objects[path] = co;\n \n \t\t/* add to list */\n-\t\tif (!(obj->flags & UNINTERESTING) || revs->show_all) {\n-\t\t\tif (entry->is_end)\n-\t\t\t\tinsert_by_date_cached(co, work, insert_cache, &insert_cache);\n-\t\t\telse\n-\t\t\t\t*queue = &commit_list_insert(co, *queue)->next;\n+\t\tif (slop && !(revs->min_age != -1 && co->date > revs->min_age)) {\n+\n+\t\t\tif (!(obj->flags & UNINTERESTING) || revs->show_all) {\n+\t\t\t\tif (entry->is_end)\n+\t\t\t\t\tmyworkp = &commit_list_insert(co, myworkp)->next;\n+\t\t\t\telse\n+\t\t\t\t\tmyqp = &commit_list_insert(co, myqp)->next;\n+\n+\t\t\t\t/* add children to list as well */\n+\t\t\t\tif (obj->flags & UNINTERESTING)\n+\t\t\t\t\tconsume_children = 0;\n+\t\t\t\telse\n+\t\t\t\t\tconsume_children = 1;\n+\t\t\t}\n \n-\t\t\t/* add children to list as well */\n-\t\t\tif (obj->flags & UNINTERESTING)\n-\t\t\t\tconsume_children = 0;\n-\t\t\telse\n-\t\t\t\tconsume_children = 1;\n \t\t}\n \n+\t\t/* should we continue? */\n+\t\tif (!slop) {\n+\t\t\tif (!upath_nr) {\n+\t\t\t\tbreak;\n+\t\t\t} else if (ioutside || revs->show_all) {\n+\t\t\t\t/* pass it back to rev-list\n+\t\t\t\t * we purposely ignore everything outside this cache, so we don't needlessly traverse the whole\n+\t\t\t\t * thing on uninteresting, but that does mean that we may need to bounce back\n+\t\t\t\t * and forth a few times with rev-list */\n+\t\t\t\tmyworkp = &commit_list_insert(co, myworkp)->next;\n+\n+\t\t\t\tpaths[path] = 0;\n+\t\t\t\tupath_nr--;\n+\t\t\t} else {\n+\t\t\t\tbreak;\n+\t\t\t}\n+\t\t} else if (!ipath_nr && co->date <= date)\n+\t\t\tslop--;\n+\t\telse\n+\t\t\tslop = SLOP;\n+\n \t\t/* open parents */\n \t\tif (entry->merge_nr) {\n \t\t\tint j, off = index + sizeof(struct rc_object_entry_ondisk);\n@@ -525,6 +648,11 @@ static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *m\n \t\t\t\tif (paths[p] & flag)\n \t\t\t\t\tcontinue;\n \n+\t\t\t\tif (flag == IPATH)\n+\t\t\t\t\tipath_nr++;\n+\t\t\t\telse\n+\t\t\t\t\tupath_nr++;\n+\n \t\t\t\tpaths[p] |= flag;\n \t\t\t}\n \n@@ -534,12 +662,54 @@ static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *m\n \n \t}\n \n+\tif (date_so_far)\n+\t\t*date_so_far = date;\n+\tif (slop_so_far)\n+\t\t*slop_so_far = slop;\n \tretval = 0;\n \n+\t/* success: attach to given lists */\n+\tif (myqp != &myq) {\n+\t\t**queue = myq;\n+\t\t*queue = myqp;\n+\t}\n+\n+\twhile ((co = pop_commit(&mywork)) != 0)\n+\t\tinsert_by_date_cached(co, work, insert_cache, &insert_cache);\n+\n+\t/* free backup */\n+\twhile (pop_commit(&unwork))\n+\t\t;\n+\n end:\n \tfree(paths);\n \tfree(last_objects);\n \n+\t/* failure: restore work to previous condition\n+\t * (cache corruption should *not* be fatal) */\n+\tif (retval) {\n+\t\twhile ((co = pop_commit(&unwork)) != 0) {\n+\t\t\trestore_commit(co);\n+\t\t\tco->object.flags |= SEEN;\n+\t\t\tinsert_by_date(co, work);\n+\t\t}\n+\n+\t\t/* free lists */\n+\t\twhile ((co = pop_commit(&myq)) != 0)\n+\t\t\trestore_commit(co);\n+\n+\t\twhile ((co = pop_commit(&mywork)) != 0)\n+\t\t\trestore_commit(co);\n+\n+\t\t/* truncate object array */\n+\t\tfor (i = orig_obj_nr; i < revs->pending.nr; i++) {\n+\t\t\tstruct object *obj = revs->pending.objects[i].item;\n+\n+\t\t\tobj->flags &= ~FACE_VALUE;\n+\t\t}\n+\t\trevs->pending.nr = orig_obj_nr;\n+\t}\n+\n \treturn retval;\n }\n \n@@ -630,6 +800,7 @@ int traverse_cache_slice(struct rev_info *revs,\n \n \t/* load options */\n \trci = &revs->rev_cache_info;\n+\tadd_to_pending = rci->add_to_pending;\n \n \tmemset(&head, 0, sizeof(struct rc_slice_header));\n \n@@ -653,6 +824,10 @@ end:\n \tif (fd != -1)\n \t\tclose(fd);\n \n+\t/* remember this! */\n+\tif (retval)\n+\t\tmark_bad_slice(cache_sha1);\n+\n \treturn retval;\n }\n \n@@ -1128,7 +1303,7 @@ static int add_objects_verbatim_1(struct rev_cache_slice_map *mapping, int *inde\n \twhile (i < mapping->size) {\n \t\tint pos = i;\n \n-\t\tentry = RC_OBTAIN_OBJECT_ENTRY(map + i;\n+\t\tentry = RC_OBTAIN_OBJECT_ENTRY(map + i);\n \t\ti += RC_ACTUAL_OBJECT_ENTRY_SIZE(entry);\n \n \t\tif (entry->type == OBJ_COMMIT) {\ndiff --git a/revision.c b/revision.c\nindex de9e2e3..155db70 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -12,6 +12,7 @@\n #include \"patch-ids.h\"\n #include \"decorate.h\"\n #include \"log-tree.h\"\n+#include \"rev-cache.h\"\n \n volatile show_early_output_fn_t show_early_output;\n \n@@ -638,6 +639,8 @@ static int limit_list(struct rev_info *revs)\n \tstruct commit_list *list = revs->commits;\n \tstruct commit_list *newlist = NULL;\n \tstruct commit_list **p = &newlist;\n+\tunsigned char *cache_sha1;\n+\tchar used_cache;\n \n \twhile (list) {\n \t\tstruct commit_list *entry = list;\n@@ -650,24 +653,39 @@ static int limit_list(struct rev_info *revs)\n \n \t\tif (revs->max_age != -1 && (commit->date < revs->max_age))\n \t\t\tobj->flags |= UNINTERESTING;\n-\t\tif (add_parents_to_list(revs, commit, &list, NULL) < 0)\n-\t\t\treturn -1;\n-\t\tif (obj->flags & UNINTERESTING) {\n-\t\t\tmark_parents_uninteresting(commit);\n-\t\t\tif (revs->show_all)\n-\t\t\t\tp = &commit_list_insert(commit, p)->next;\n-\t\t\tslop = still_interesting(list, date, slop);\n-\t\t\tif (slop)\n+\n+\t\t/* rev-cache to the rescue!!! */\n+\t\tused_cache = 0;\n+\t\tif (!revs->dont_cache_me && !(obj->flags & ADDED)) {\n+\t\t\tcache_sha1 = get_cache_slice(commit);\n+\t\t\tif (cache_sha1) {\n+\t\t\t\tif (traverse_cache_slice(revs, cache_sha1, commit, &date, &slop, &p, &list) < 0)\n+\t\t\t\t\tused_cache = 0;\n+\t\t\t\telse\n+\t\t\t\t\tused_cache = 1;\n+\t\t\t}\n+\t\t}\n+\n+\t\tif (!used_cache) {\n+\t\t\tif (add_parents_to_list(revs, commit, &list, NULL) < 0)\n+\t\t\t\treturn -1;\n+\t\t\tif (obj->flags & UNINTERESTING) {\n+\t\t\t\tmark_parents_uninteresting(commit); /* ME: why? */\n+\t\t\t\tif (revs->show_all)\n+\t\t\t\t\tp = &commit_list_insert(commit, p)->next;\n+\t\t\t\tslop = still_interesting(list, date, slop);\n+\t\t\t\tif (slop > 0)\n+\t\t\t\t\tcontinue;\n+\t\t\t\t/* If showing all, add the whole pending list to the end */\n+\t\t\t\tif (revs->show_all)\n+\t\t\t\t\t*p = list;\n+\t\t\t\tbreak;\n+\t\t\t}\n+\t\t\tif (revs->min_age != -1 && (commit->date > revs->min_age))\n \t\t\t\tcontinue;\n-\t\t\t/* If showing all, add the whole pending list to the end */\n-\t\t\tif (revs->show_all)\n-\t\t\t\t*p = list;\n-\t\t\tbreak;\n+\t\t\tdate = commit->date;\n+\t\t\tp = &commit_list_insert(commit, p)->next;\n \t\t}\n-\t\tif (revs->min_age != -1 && (commit->date > revs->min_age))\n-\t\t\tcontinue;\n-\t\tdate = commit->date;\n-\t\tp = &commit_list_insert(commit, p)->next;\n \n \t\tshow = show_early_output;\n \t\tif (!show)\n@@ -813,6 +831,8 @@ void init_revisions(struct rev_info *revs, const char *prefix)\n \t\trevs->diffopt.prefix = prefix;\n \t\trevs->diffopt.prefix_length = strlen(prefix);\n \t}\n+\n+\tinit_rev_cache_info(&revs->rev_cache_info);\n }\n \n static void add_pending_commit_list(struct rev_info *revs,\n@@ -1374,6 +1394,11 @@ int setup_revisions(int argc, const char **argv, struct rev_info *revs, const ch\n \tif (revs->reflog_info && revs->graph)\n \t\tdie(\"cannot combine --walk-reflogs with --graph\");\n \n+\t/* limits on caching\n+\t * todo: implement this functionality */\n+\tif (revs->prune || revs->diff)\n+\t\trevs->dont_cache_me = 1;\n+\n \treturn left;\n }\n \n@@ -1656,6 +1681,8 @@ static int commit_match(struct commit *commit, struct rev_info *opt)\n {\n \tif (!opt->grep_filter.pattern_list)\n \t\treturn 1;\n+\tif (!commit->object.parsed)\n+\t\tparse_commit(commit);\n \treturn grep_buffer(&opt->grep_filter,\n \t\t\t   NULL, /* we say nothing, not even filename */\n \t\t\t   commit->buffer, strlen(commit->buffer));\n@@ -1719,6 +1746,7 @@ static struct commit *get_revision_1(struct rev_info *revs)\n \tdo {\n \t\tstruct commit_list *entry = revs->commits;\n \t\tstruct commit *commit = entry->item;\n+\t\tstruct object *obj = &commit->object;\n \n \t\trevs->commits = entry->next;\n \t\tfree(entry);\n@@ -1735,11 +1763,39 @@ static struct commit *get_revision_1(struct rev_info *revs)\n \t\t\tif (revs->max_age != -1 &&\n \t\t\t    (commit->date < revs->max_age))\n \t\t\t\tcontinue;\n+\n+\t\t\tif (!revs->dont_cache_me) {\n+\t\t\t\tstruct commit_list *queue = 0, **queuep = &queue;\n+\t\t\t\tunsigned char *cache_sha1;\n+\n+\t\t\t\tif (obj->flags & ADDED)\n+\t\t\t\t\tgoto skip_parenting;\n+\n+\t\t\t\tcache_sha1 = get_cache_slice(commit);\n+\t\t\t\tif (cache_sha1) {\n+\t\t\t\t\tif (!traverse_cache_slice(revs, cache_sha1, commit, 0, 0, &queuep, &revs->commits)) {\n+\t\t\t\t\t\tstruct commit_list *work = revs->commits;\n+\n+\t\t\t\t\t\t/* attach queue to end of ->commits */\n+\t\t\t\t\t\twhile (work && work->next)\n+\t\t\t\t\t\t\twork = work->next;\n+\n+\t\t\t\t\t\tif (work)\n+\t\t\t\t\t\t\twork->next = queue;\n+\t\t\t\t\t\telse\n+\t\t\t\t\t\t\trevs->commits = queue;\n+\n+\t\t\t\t\t\tgoto skip_parenting;\n+\t\t\t\t\t}\n+\t\t\t\t}\n+\t\t\t}\n+\n \t\t\tif (add_parents_to_list(revs, commit, &revs->commits, NULL) < 0)\n \t\t\t\tdie(\"Failed to traverse parents of commit %s\",\n \t\t\t\t    sha1_to_hex(commit->object.sha1));\n \t\t}\n \n+skip_parenting:\n \t\tswitch (simplify_commit(revs, commit)) {\n \t\tcase commit_ignore:\n \t\t\tcontinue;\ndiff --git a/t/t6017-rev-cache-list.sh b/t/t6017-rev-cache-list.sh\nindex dc0fc07..982fb15 100755\n--- a/t/t6017-rev-cache-list.sh\n+++ b/t/t6017-rev-cache-list.sh\n@@ -38,6 +38,7 @@ test_expect_success 'init repo' '\n \tgit add . &&\n \tgit commit -m \"omg\" &&\n \n+\tsleep 2 &&\n \tgit branch b4 &&\n \tgit checkout b4 &&\n \techo shazam >file8 &&\n@@ -46,7 +47,7 @@ test_expect_success 'init repo' '\n \tgit merge -m \"merge b2\" b2 &&\n \n \techo bam >smoke/pipe &&\n-\tgit add .\n+\tgit add . &&\n \tgit commit -m \"bam\" &&\n \n \tgit checkout master &&\n@@ -71,18 +72,26 @@ test_expect_success 'init repo' '\n \tgit add . &&\n \tgit commit -m \"lol\" &&\n \n+\tsleep 2 &&\n \tgit checkout master &&\n \tgit merge -m \"triple merge\" b1 b11 &&\n \tgit rm -r d1 &&\n+\tsleep 2 &&\n \tgit commit -a -m \"oh noes\"\n '\n \n-git-rev-list HEAD --not HEAD~3 >proper_commit_list_limited\n-git-rev-list HEAD >proper_commit_list\n-git-rev-list HEAD --objects >proper_object_list\n+max_date=`git-rev-list --timestamp HEAD~1 --max-count=1 | grep -e \"^[0-9]*\" -o`\n+min_date=`git-rev-list --timestamp b4 --max-count=1 | grep -e \"^[0-9]*\" -o`\n+\n+git-rev-list --topo-order HEAD --not HEAD~3 >proper_commit_list_limited\n+git-rev-list --topo-order HEAD --not HEAD~2 >proper_commit_list_limited2\n+git-rev-list --topo-order HEAD >proper_commit_list\n+git-rev-list --objects HEAD >proper_object_list\n+git-rev-list HEAD --max-age=$min_date --min-age=$max_date >proper_list_date_limited\n+\n+cache_sha1=`git-rev-cache add HEAD 2>output.err`\n \n test_expect_success 'make cache slice' '\n-\tgit-rev-cache add HEAD 2>output.err &&\n \tgrep \"final return value: 0\" output.err\n '\n \n@@ -102,11 +111,141 @@ test_expect_success 'test rev-caches walker directly (unlimited)' '\n \ttest_cmp_sorted list proper_commit_list\n '\n \n+test_expect_success 'test rev-list traversal (limited)' '\n+\tgit-rev-list HEAD --not HEAD~3 >list &&\n+\ttest_cmp list proper_commit_list_limited\n+'\n+\n+test_expect_success 'test rev-list traversal (unlimited)' '\n+\tgit-rev-list HEAD >list &&\n+\ttest_cmp list proper_commit_list\n+'\n+\n #do the same for objects\n test_expect_success 'test rev-caches walker with objects' '\n \tgit-rev-cache walk --objects HEAD >list &&\n \ttest_cmp_sorted list proper_object_list\n '\n \n-test_done\n+test_expect_success 'test rev-list with objects (topo order)' '\n+\tgit-rev-list --topo-order --objects HEAD >list &&\n+\ttest_cmp_sorted list proper_object_list\n+'\n+\n+test_expect_success 'test rev-list with objects (no order)' '\n+\tgit-rev-list --objects HEAD >list &&\n+\ttest_cmp_sorted list proper_object_list\n+'\n+\n+#verify age limiting\n+test_expect_success 'test rev-list date limiting (topo order)' '\n+\tgit-rev-list --topo-order --max-age=$min_date --min-age=$max_date HEAD >list &&\n+\ttest_cmp_sorted list proper_list_date_limited\n+'\n+\n+test_expect_success 'test rev-list date limiting (no order)' '\n+\tgit-rev-list --max-age=$min_date --min-age=$max_date HEAD >list &&\n+\ttest_cmp_sorted list proper_list_date_limited\n+'\n+\n+#check partial cache slice\n+test_expect_success 'saving old cache and generating partial slice' '\n+\tcp \".git/rev-cache/$cache_sha1\" .git/rev-cache/.old &&\n+\trm \".git/rev-cache/$cache_sha1\" .git/rev-cache/index &&\n+\n+\tgit-rev-cache add HEAD~2 2>output.err &&\n+\tgrep \"final return value: 0\" output.err\n+'\n+\n+test_expect_success 'rev-list with wholly interesting partial slice' '\n+\tgit-rev-list --topo-order HEAD >list &&\n+\ttest_cmp list proper_commit_list\n+'\n+\n+test_expect_success 'rev-list with partly uninteresting partial slice' '\n+\tgit-rev-list --topo-order HEAD --not HEAD~3 >list &&\n+\ttest_cmp list proper_commit_list_limited\n+'\n+\n+test_expect_success 'rev-list with wholly uninteresting partial slice' '\n+\tgit-rev-list --topo-order HEAD --not HEAD~2 >list &&\n+\ttest_cmp list proper_commit_list_limited2\n+'\n+\n+#try out index generation and fuse (note that --all == HEAD in this case)\n+#probably should make a test for that too...\n+test_expect_success 'test (non-)fusion of one slice' '\n+\tgit-rev-cache fuse >output.err &&\n+\tgrep \"nothing to fuse\" output.err\n+'\n \n+test_expect_success 'make fresh slice' '\n+\tgit-rev-cache add --all --fresh 2>output.err &&\n+\tgrep \"final return value: 0\" output.err\n+'\n+\n+test_expect_success 'check dual slices' '\n+\tgit-rev-list --topo-order HEAD~2 HEAD >list &&\n+\ttest_cmp list proper_commit_list\n+'\n+\n+test_expect_success 'regenerate index' '\n+\trm .git/rev-cache/index &&\n+\tgit-rev-cache index 2>output.err &&\n+\tgrep \"final return value: 0\" output.err\n+'\n+\n+test_expect_success 'fuse slices' '\n+\ttest -e .git/rev-cache/.old &&\n+\tgit-rev-cache fuse 2>output.err &&\n+\tgrep \"final return value: 0\" output.err &&\n+\ttest_cmp .git/rev-cache/$cache_sha1 .git/rev-cache/.old\n+'\n+\n+#make sure we can smoothly handle corrupted caches\n+test_expect_success 'corrupt slice' '\n+\techo bla >.git/rev-cache/$cache_sha1\n+'\n+\n+test_expect_success 'test rev-list traversal (limited) (corrupt slice)' '\n+\tgit-rev-list --topo-order HEAD --not HEAD~3 >list &&\n+\ttest_cmp list proper_commit_list_limited\n+'\n+\n+test_expect_success 'test rev-list traversal (unlimited) (corrupt slice)' '\n+\tgit-rev-list HEAD >list &&\n+\ttest_cmp_sorted list proper_commit_list\n+'\n+\n+test_expect_success 'corrupt index' '\n+\techo blu >.git/rev-cache/index\n+'\n+\n+test_expect_success 'test rev-list traversal (limited) (corrupt index)' '\n+\tgit-rev-list --topo-order HEAD --not HEAD~3 >list &&\n+\ttest_cmp list proper_commit_list_limited\n+'\n+\n+test_expect_success 'test rev-list traversal (unlimited) (corrupt index)' '\n+\tgit-rev-list HEAD >list &&\n+\ttest_cmp_sorted list proper_commit_list\n+'\n+\n+#test --ignore-size in fuse\n+rm .git/rev-cache/*\n+cache_sha1=`git-rev-cache add HEAD~2 2>output.err`\n+\n+test_expect_success 'make fragmented slices' '\n+\tgit-rev-cache add HEAD~1 --not HEAD~2 2>>output.err &&\n+\tgit-rev-cache add HEAD --fresh 2>>output.err &&\n+\ttest `grep \"final return value: 0\" output.err | wc -l` -eq 3\n+'\n+\n+cache_size=$(wc -c < .git/rev-cache/$cache_sha1)\n+test_expect_success 'test --ignore-size function in fuse' '\n+\tgit-rev-cache fuse --ignore-size=$cache_size 2>output.err &&\n+\tgrep \"final return value: 0\" output.err &&\n+\ttest -e .git/rev-cache/$cache_sha1\n+'\n+\n+test_done\n-- \ntg: (1d78545..) t/revcache/integration (depends on: t/revcache/misc)\n"}]}