{"thread":{"id":"23345","subject":"[PATCH 5/7 (v5)] integration into revision walker","startedAt":"2010-04-05T19:58:32Z","lastAt":"2010-04-05T19:58:32Z","messageCount":1,"participants":["Nick Edelen"],"isPatch":true,"patchVersion":5,"patchTotal":7},"messages":[{"id":"138672","messageId":"4BBA40E8.1050204@gmail.com","threadId":"23345","inReplyTo":null,"subject":"[PATCH 5/7 (v5)] integration into revision walker","fromName":"Nick Edelen","fromEmail":"sirnot@gmail.com","sentAt":"2010-04-05T19:58:32Z","receivedAt":"2010-04-05T19:58:32Z","isPatch":true,"sender":{"key":"sirnot@gmail.com","avatar":null},"body":"Provides a working integration of rev-cache into the revision walker, along\nwith 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            |   46 ++++++++-\n rev-cache.c               |  225 ++++++++++++++++++++++++++++++++++++++++-----\n revision.c                |   88 ++++++++++++++---\n t/t6019-rev-cache-list.sh |  150 +++++++++++++++++++++++++++++-\n 5 files changed, 498 insertions(+), 51 deletions(-)\n\ndiff --git a/builtin/rev-cache.c b/builtin/rev-cache.c\nindex d6cd57b..7a79007 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@@ -277,6 +315,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 27e3b40..af1a704 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@@ -183,6 +190,30 @@ unsigned char *to_disked_rc_object_entry(struct rc_object_entry *src, unsigned c\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 \tint i, index = INDEX_HEADER_SIZE;\n@@ -306,6 +337,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@@ -317,8 +349,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@@ -328,6 +365,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@@ -367,7 +418,8 @@ 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 struct entrance_point {\n@@ -389,7 +441,8 @@ static int eps_sort_callback(const void *a, const void *b)\n }\n \n static int setup_traversal(struct rc_slice_header *head, struct entrance_point **peps, int *peplen,\n-\tstruct commit *commit, struct commit_list **work)\n+\tstruct 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 commit_list *prev, *wp, **wpp;\n@@ -398,11 +451,13 @@ static int setup_traversal(struct rc_slice_header *head, struct entrance_point *\n \n \teps = xcalloc(1, eplen * sizeof(struct entrance_point));\n \tiep = search_index(commit->object.sha1);\n+\tif (commit->object.flags & UNINTERESTING) {\n+\t\t++*upath_nr;\n+\t\teps[0].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 \teps[0].pos = iep->pos;\n-\teps[0].uninteresting = !!(commit->object.flags & UNINTERESTING);\n \tretval = iep->pos;\n \n \t/* include any others in the work array */\n@@ -416,6 +471,10 @@ static int setup_traversal(struct rc_slice_header *head, struct entrance_point *\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@@ -435,11 +494,20 @@ static int setup_traversal(struct rc_slice_header *head, struct entrance_point *\n \t\teps[curep].uninteresting = !!(obj->flags & UNINTERESTING);\n \t\tcurep++;\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 \tqsort(eps, curep, sizeof(struct entrance_point), eps_sort_callback);\n@@ -459,15 +527,20 @@ 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 \tstruct entrance_point *eps;\n \tint eplen, curep = 0;\n \n-\ti = setup_traversal(head, &eps, &eplen, 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, &eps, &eplen, commit, work, &unwork, &ipath_nr, &upath_nr, &ioutside);\n \tif (i < 0)\n \t\treturn -1;\n \n@@ -516,6 +589,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@@ -526,6 +600,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@@ -549,8 +624,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@@ -560,14 +637,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 (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 (!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@@ -582,24 +678,51 @@ static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *m\n \n \t\tif (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 + OBJECT_ENTRY_SIZE;\n@@ -614,6 +737,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@@ -623,13 +751,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+\n+\t/* free backup */\n+\twhile (pop_commit(&unwork))\n+\t\t;\n+\n end:\n \tfree(paths);\n \tfree(last_objects);\n \tfree(eps);\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@@ -723,6 +893,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@@ -746,6 +917,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 cd3dba8..201407c 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -13,6 +13,7 @@\n #include \"decorate.h\"\n #include \"log-tree.h\"\n #include \"string-list.h\"\n+#include \"rev-cache.h\"\n \n volatile show_early_output_fn_t show_early_output;\n \n@@ -653,6 +654,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@@ -665,24 +668,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@@ -835,6 +853,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@@ -1547,6 +1567,11 @@ int setup_revisions(int argc, const char **argv, struct rev_info *revs, struct s\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@@ -1829,6 +1854,8 @@ static int commit_match(struct commit *commit, struct rev_info *opt)\n {\n \tif (!opt->grep_filter.pattern_list && !opt->grep_filter.header_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@@ -1892,6 +1919,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@@ -1908,11 +1936,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/t6019-rev-cache-list.sh b/t/t6019-rev-cache-list.sh\nindex b6cf6fc..77cd191 100644\n--- a/t/t6019-rev-cache-list.sh\n+++ b/t/t6019-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,142 @@ 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_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 \n-- \ntg: (c8f0b1d..) t/rc/int (depends on: t/rc/misc)\n"}]}