[RFC/PATCH 4/4] rev-cache: tentative integration into rev-list + tests

[RFC/PATCH 4/4] rev-cache: tentative integration into rev-list + tests

[Nick Edelen]

[-- Attachment #1: Type: text/plain, Size: 1037 bytes --]

This patch introduces a tentative step towards integrating rev-cache into the internal revision walker.  Cache traversal is added to both limited and unlimited revision walks, and FACE_VALUEd objects are handled in list-objects.  Furthermore the unique object_list field is added to commit objects, to allow runtime association with a commit's cached 'unique' object list.

The traversal mechanism in rev-cache is updated to reflect the limiting methods used in rev-list.  Tests for coagulation and index generation are included, in addition to several verifying the correctness of integration.

Signed-off-by: Nick Edelen <sirnot@gmail.com>

---
 builtin-rev-cache.c       |   44 +++++++-
 commit.c                  |    2 +-
 commit.h                  |    1 +
 list-objects.c            |   19 +++-
 rev-cache.c               |  299 +++++++++++++++++++++++++++++++++++++++------
 revision.c                |   91 +++++++++++---
 t/t6015-rev-cache-list.sh |  120 +++++++++++++++++--
 7 files changed, 505 insertions(+), 71 deletions(-)

[-- Attachment #2: patch_int.diff --]
[-- Type: application/octet-stream, Size: 31007 bytes --]

This patch introduces a tentative step towards integrating rev-cache into the internal revision walker.  Cache traversal is added to both limited and unlimited revision walks, and FACE_VALUEd objects are handled in list-objects.  Furthermore the unique object_list field is added to commit objects, to allow runtime association with a commit's cached 'unique' object list.

The traversal mechanism in rev-cache is updated to reflect the limiting methods used in rev-list.  Tests for coagulation and index generation are included, in addition to several verifying the correctness of integration.

Signed-off-by: Nick Edelen <sirnot@gmail.com>

---
 builtin-rev-cache.c       |   44 +++++++-
 commit.c                  |    2 +-
 commit.h                  |    1 +
 list-objects.c            |   19 +++-
 rev-cache.c               |  299 +++++++++++++++++++++++++++++++++++++++------
 revision.c                |   91 +++++++++++---
 t/t6015-rev-cache-list.sh |  120 +++++++++++++++++--
 7 files changed, 505 insertions(+), 71 deletions(-)

diff --git a/builtin-rev-cache.c b/builtin-rev-cache.c
index 380818f..c0c0d97 100755
--- a/builtin-rev-cache.c
+++ b/builtin-rev-cache.c
@@ -3,6 +3,7 @@
 #include "commit.h"
 #include "diff.h"
 #include "revision.h"
+#include "list-objects.h"
 
 #define DEFAULT_IGNORE_SLICE_SIZE		5000000 /* in bytes */
 
@@ -69,10 +70,46 @@ static int handle_add(int argc, const char *argv[]) /* args beyond this command
 	return 0;
 }
 
+static void show_commit(struct commit *commit, void *data)
+{
+	printf("%s\n", sha1_to_hex(commit->object.sha1));
+}
+
+static void show_object(struct object *obj, const struct name_path *path, const char *last)
+{
+	printf("%s\n", sha1_to_hex(obj->sha1));
+}
+
+static int test_rev_list(int argc, const char *argv[])
+{
+	struct rev_info revs;
+	unsigned int flags = 0;
+	int i;
+	
+	init_revisions(&revs, 0);
+	
+	for (i = 0; i < argc; i++) {
+		if (!strcmp(argv[i], "--not"))
+			flags ^= UNINTERESTING;
+		else if (!strcmp(argv[i], "--objects"))
+			revs.tree_objects = revs.blob_objects = 1;
+		else
+			handle_revision_arg(argv[i], &revs, flags, 1);
+	}
+	
+	setup_revisions(0, 0, &revs, 0);
+	prepare_revision_walk(&revs);
+	
+	traverse_commit_list(&revs, show_commit, show_object, 0);
+	
+	return 0;
+}
+
 static int handle_walk(int argc, const char *argv[])
 {
 	struct commit *commit;
 	struct rev_info revs;
+	struct rev_cache_info rci;
 	struct commit_list *queue, *work, **qp;
 	unsigned char *sha1p, *sha1pt;
 	unsigned long date = 0;
@@ -80,6 +117,7 @@ static int handle_walk(int argc, const char *argv[])
 	int retval, slop = 5, i;
 	
 	init_revisions(&revs, 0);
+	init_rci(&rci);
 	
 	for (i = 0; i < argc; i++) {
 		if (!strcmp(argv[i], "--not"))
@@ -113,7 +151,7 @@ static int handle_walk(int argc, const char *argv[])
 	queue = 0;
 	qp = &queue;
 	commit = pop_commit(&work);
-	retval = traverse_cache_slice(0, sha1p, &revs, commit, &date, &slop, &qp, &work);
+	retval = traverse_cache_slice(&rci, sha1p, &revs, commit, &date, &slop, &qp, &work);
 	if (retval < 0)
 		return retval;
 	
@@ -181,7 +219,7 @@ static int handle_fuse(int argc, const char *argv[])
 
 static int handle_index(int argc, const char *argv[])
 {
-	return regenerate_cache_index();
+	return regenerate_cache_index(0);
 }
 
 static int handle_help(void)
@@ -235,6 +273,8 @@ int cmd_rev_cache(int argc, const char *argv[], const char *prefix)
 		r = handle_walk(argc, argv);
 	else if (!strcmp(arg, "index"))
 		r = handle_index(argc, argv);
+	else if (!strcmp(arg, "test"))
+		r = test_rev_list(argc, argv);
 	else
 		return handle_help();
 	
diff --git a/commit.c b/commit.c
index d9778ba..92459bd 100644
--- a/commit.c
+++ b/commit.c
@@ -256,7 +256,7 @@ int parse_commit_buffer(struct commit *item, void *buffer, unsigned long size)
 			     sha1_to_hex(item->object.sha1));
 	item->tree = lookup_tree(parent);
 	bufptr += 46; /* "tree " + "hex sha1" + "\n" */
- 	pptr = &item->parents;
+	pptr = &item->parents;
 	while (pop_commit(pptr))
 		; /* clear anything from cache */
 
diff --git a/commit.h b/commit.h
index 0529fcf..7c50a7f 100644
--- a/commit.h
+++ b/commit.h
@@ -20,6 +20,7 @@ struct commit {
 	struct tree *tree;
 	char *buffer;
 	unsigned long size;
+	struct object_list *unique;
 };
 
 extern int save_commit_buffer;
diff --git a/list-objects.c b/list-objects.c
index 8953548..2b4becb 100644
--- a/list-objects.c
+++ b/list-objects.c
@@ -78,6 +78,10 @@ static void process_tree(struct rev_info *revs,
 		die("bad tree object %s", sha1_to_hex(obj->sha1));
 	obj->flags |= SEEN;
 	show(obj, path, name);
+
+	if (obj->flags & FACE_VALUE)
+		return;
+
 	me.up = path;
 	me.elem = name;
 	me.elem_len = strlen(name);
@@ -85,11 +89,16 @@ static void process_tree(struct rev_info *revs,
 	init_tree_desc(&desc, tree->buffer, tree->size);
 
 	while (tree_entry(&desc, &entry)) {
-		if (S_ISDIR(entry.mode))
+		if (S_ISDIR(entry.mode)) {
+			struct tree *subtree = lookup_tree(entry.sha1);
+			if (!subtree)
+				continue;
+			
+			subtree->object.flags &= ~FACE_VALUE;
 			process_tree(revs,
-				     lookup_tree(entry.sha1),
+				     subtree,
 				     show, &me, entry.path);
-		else if (S_ISGITLINK(entry.mode))
+		} else if (S_ISGITLINK(entry.mode))
 			process_gitlink(revs, entry.sha1,
 					show, &me, entry.path);
 		else
@@ -136,6 +145,7 @@ void mark_edges_uninteresting(struct commit_list *list,
 
 static void add_pending_tree(struct rev_info *revs, struct tree *tree)
 {
+	tree->object.flags &= ~FACE_VALUE;
 	add_pending_object(revs, &tree->object, "");
 }
 
@@ -148,7 +158,8 @@ void traverse_commit_list(struct rev_info *revs,
 	struct commit *commit;
 
 	while ((commit = get_revision(revs)) != NULL) {
-		add_pending_tree(revs, commit->tree);
+		if (!(commit->object.flags & FACE_VALUE))
+			add_pending_tree(revs, commit->tree);
 		show_commit(commit, data);
 	}
 	for (i = 0; i < revs->pending.nr; i++) {
diff --git a/rev-cache.c b/rev-cache.c
index 602cec6..5f6fb95 100755
--- a/rev-cache.c
+++ b/rev-cache.c
@@ -83,13 +83,19 @@ struct object_entry {
 	/* size */
 };
 
+struct bad_slice {
+	unsigned char sha1[20];
+	struct bad_slice *next;
+};
+
 /* list resembles pack index format */
 static uint32_t fanout[0xff + 2];
 
 static unsigned char *idx_map = 0;
 static int idx_size;
 static struct index_header idx_head;
-static char no_idx = 0;
+static char no_idx = 0, save_unique = 0, add_to_pending = 0;
+static struct bad_slice *bad_slices;
 
 static struct strbuf *g_buffer;
 
@@ -108,10 +114,36 @@ static struct strbuf *g_buffer;
 #define ACTUAL_OBJECT_ENTRY_SIZE(e)		(OE_SIZE + PATH_SIZE((e)->merge_nr + (e)->split_nr) + (e)->size_size)
 #define ENTRY_SIZE_OFFSET(e)			(ACTUAL_OBJECT_ENTRY_SIZE(e) - (e)->size_size)
 
-#define SLOP		5
+#define SLOP			5
+
+#define HAS_UNIQUES		FACE_VALUE
 
 /* initialization */
 
+static void mark_bad_slice(unsigned char *sha1)
+{
+	struct bad_slice *bad;
+	
+	bad = xcalloc(sizeof(struct bad_slice), 1);
+	hashcpy(bad->sha1, sha1);
+	
+	bad->next = bad_slices;
+	bad_slices = bad;
+}
+
+static int is_bad_slice(unsigned char *sha1)
+{
+	struct bad_slice *bad = bad_slices;
+	
+	while (bad) {
+		if (!hashcmp(bad->sha1, sha1))
+			return 1;
+		bad = bad->next;
+	}
+	
+	return 0;
+}
+
 static int get_index_head(unsigned char *map, int len, struct index_header *head, uint32_t *fanout)
 {
 	struct index_header_ondisk whead;
@@ -228,6 +260,7 @@ static struct index_entry *search_index(unsigned char *sha1)
 unsigned char *get_cache_slice(struct commit *commit)
 {
 	struct index_entry *ie;
+	unsigned char *sha1;
 	
 	if (!idx_map) {
 		if (no_idx)
@@ -239,8 +272,13 @@ unsigned char *get_cache_slice(struct commit *commit)
 		return 0;
 	
 	ie = search_index(commit->object.sha1);
-	if (ie && ie->cache_index < idx_head.caches)
-		return idx_head.cache_sha1s + ie->cache_index * 20;
+	if (ie && ie->cache_index < idx_head.caches) {
+		sha1 = idx_head.cache_sha1s + ie->cache_index * 20;
+		
+		if (is_bad_slice(sha1))
+			return 0;
+		return sha1;
+	}
 	
 	return 0;
 }
@@ -250,8 +288,29 @@ unsigned char *get_cache_slice(struct commit *commit)
 
 static unsigned long decode_size(unsigned char *str, int len);
 
+/* on failure */
+static void restore_commit(struct commit *commit)
+{
+	if (commit->unique) {
+		free(commit->unique);
+		commit->unique = 0;
+	}
+	
+	commit->object.flags &= ~(ADDED | SEEN | FACE_VALUE);
+	
+	if (!commit->object.parsed) {
+		while (pop_commit(&commit->parents)) 
+			;
+		
+		parse_commit(commit);
+	}
+	
+}
+
 static void handle_noncommit(struct rev_info *revs, struct commit *commit, struct object_entry *entry)
 {
+	static struct commit *last_commit = 0;
+	static struct object_list **last_unique = 0;
 	struct blob *blob;
 	struct tree *tree;
 	struct object *obj;
@@ -289,11 +348,27 @@ static void handle_noncommit(struct rev_info *revs, struct commit *commit, struc
 		return;
 	}
 	
+	/* add to unique list if we're not a start */
+	if (save_unique && (commit->object.flags & FACE_VALUE)) {
+		if (last_commit != commit) {
+			last_commit = commit;
+			last_unique = 0;
+		}
+		
+		if (!last_unique)
+			last_unique = &commit->unique;
+		
+		object_list_append(obj, last_unique);
+		last_unique = &(*last_unique)->next;
+	}
+	
 	obj->flags |= FACE_VALUE;
-	add_pending_object(revs, obj, "");
+	if (add_to_pending)
+		add_pending_object(revs, obj, "");
 }
 
-static int setup_traversal(struct cache_slice_header *head, unsigned char *map, struct commit *commit, struct commit_list **work)
+static int setup_traversal(struct cache_slice_header *head, unsigned char *map, struct commit *commit, struct commit_list **work, 
+	struct commit_list **unwork, int *ipath_nr, int *upath_nr, char *ioutside)
 {
 	struct index_entry *iep;
 	struct object_entry *oep;
@@ -302,6 +377,11 @@ static int setup_traversal(struct cache_slice_header *head, unsigned char *map,
 	
 	iep = search_index(commit->object.sha1);
 	oep = OE_CAST(map + ntohl(iep->pos));
+	if (commit->object.flags & UNINTERESTING) {
+		++*upath_nr;
+		oep->uninteresting = 1;
+	} else
+		++*ipath_nr;
 	oep->include = 1;
 	retval = ntohl(iep->pos);
 	
@@ -316,10 +396,14 @@ static int setup_traversal(struct cache_slice_header *head, unsigned char *map,
 		
 		iep = search_index(obj->sha1);
 		if (!iep || hashcmp(idx_head.cache_sha1s + iep->cache_index * 20, head->sha1)) {
+			/* there are interesing objects outside the slice */
+			if (!(obj->flags & UNINTERESTING))
+				*ioutside = 1;
+			
 			prev = wp;
 			wp = wp->next;
 			wpp = &wp;
- 			continue;
+			continue;
 		}
 		
 		t = ntohl(iep->pos);
@@ -330,11 +414,20 @@ static int setup_traversal(struct cache_slice_header *head, unsigned char *map,
 		if (t < retval)
 			retval = t;
 		
+		/* count even if not in slice so we can stop enumerating if possible */
+		if (obj->flags & UNINTERESTING)
+			++*upath_nr;
+		else
+			++*ipath_nr;
+		
 		/* remove from work list */
 		co = pop_commit(wpp);
 		wp = *wpp;
 		if (prev)
 			prev->next = wp;
+		
+		/* ...and store in temp list so we can restore work on failure */
+		commit_list_insert(co, unwork);
 	}
 	
 	return retval;
@@ -351,16 +444,21 @@ static int traverse_cache_slice_1(struct cache_slice_header *head, unsigned char
 	unsigned long *date_so_far, int *slop_so_far, 
 	struct commit_list ***queue, struct commit_list **work)
 {
-	struct commit_list *insert_cache = 0;
+	struct commit_list *insert_cache = 0, *myq = 0, **myqp = &myq, *mywork = 0, **myworkp = &mywork, *unwork = 0;
 	struct commit **last_objects, *co;
-	int i, total_path_nr = head->path_nr, retval = -1;
-	char consume_children = 0;
+	unsigned long date = date_so_far ? *date_so_far : ~0ul;
+	int i, ipath_nr = 0, upath_nr = 0, orig_obj_nr = 0, 
+		total_path_nr = head->path_nr, retval = -1, slop = slop_so_far ? *slop_so_far : SLOP;
+	char consume_children = 0, ioutside = 0;
 	unsigned char *paths;
 	
+	/* take note in case we need to regress */
+	orig_obj_nr = revs->pending.nr;
+	
 	paths = xcalloc(total_path_nr, PATH_WIDTH);
 	last_objects = xcalloc(total_path_nr, sizeof(struct commit *));
 	
-	i = setup_traversal(head, map, commit, work);
+	i = setup_traversal(head, map, commit, work, &unwork, &ipath_nr, &upath_nr, &ioutside);
 	
 	/* i already set */
 	while (i < head->size) {
@@ -403,6 +501,7 @@ static int traverse_cache_slice_1(struct cache_slice_header *head, unsigned char
 		
 		if ((paths[path] & IPATH) && (paths[path] & UPATH)) {
 			paths[path] = UPATH;
+			ipath_nr--;
 			
 			/* mark edge */
 			if (last_objects[path]) {
@@ -413,6 +512,7 @@ static int traverse_cache_slice_1(struct cache_slice_header *head, unsigned char
 				last_objects[path]->object.flags &= ~FACE_VALUE;
 				last_objects[path] = 0;
 			}
+			obj->flags |= BOUNDARY;
 		}
 		
 		/* now we gotta re-assess the whole interesting thing... */
@@ -436,8 +536,10 @@ static int traverse_cache_slice_1(struct cache_slice_header *head, unsigned char
 						last_objects[p]->object.flags &= ~FACE_VALUE;
 						last_objects[p] = 0;
 					}
-				} else if (last_objects[p] && !last_objects[p]->object.parsed)
+					obj->flags |= BOUNDARY;
+				} else if (last_objects[p] && !last_objects[p]->object.parsed) {
 					commit_list_insert(co, &last_objects[p]->parents);
+				}
 				
 				/* can't close a merge path until all are parents have been encountered */
 				if (GET_COUNT(paths[p])) {
@@ -447,44 +549,90 @@ static int traverse_cache_slice_1(struct cache_slice_header *head, unsigned char
 						continue;
 				}
 				
+				if (paths[p] & IPATH)
+					ipath_nr--;
+				else
+					upath_nr--;
+				
 				paths[p] = 0;
 				last_objects[p] = 0;
 			}
 		}
 		
 		/* make topo relations */
-		if (last_objects[path] && !last_objects[path]->object.parsed)
+		if (last_objects[path] && !last_objects[path]->object.parsed) {
 			commit_list_insert(co, &last_objects[path]->parents);
+		}
+		
+		/* we've been here already */
+		if (obj->flags & ADDED) {
+			if (entry->uninteresting && !(obj->flags & UNINTERESTING)) {
+				obj->flags |= UNINTERESTING;
+				mark_parents_uninteresting(co);
+				upath_nr--;
+			} else if (!entry->uninteresting)
+				ipath_nr--;
+			
+			paths[path] = 0;
+			continue;
+		}
 		
 		/* initialize commit */
 		if (!entry->is_start) {
 			co->date = ntohl(entry->date);
- 			obj->flags |= ADDED | FACE_VALUE;
+			obj->flags |= ADDED | FACE_VALUE;
 		} else
 			parse_commit(co);
 		
 		obj->flags |= SEEN;
- 		
- 		if (entry->uninteresting)
- 			obj->flags |= UNINTERESTING;
+		
+		if (entry->uninteresting)
+			obj->flags |= UNINTERESTING;
+		else if (co->date < date)
+			date = co->date;
 		
 		/* we need to know what the edges are */
 		last_objects[path] = co;
 		
 		/* add to list */
-		if (!(obj->flags & UNINTERESTING) || revs->show_all) {
-			if (entry->is_start)
-				insert_by_date_cached(co, work, insert_cache, &insert_cache);
-			else
-				*queue = &commit_list_insert(co, *queue)->next;
+		if (slop && !(revs->min_age != -1 && co->date > revs->min_age)) {
+			
+			if (!(obj->flags & UNINTERESTING) || revs->show_all) {
+				if (entry->is_start)
+					myworkp = &commit_list_insert(co, myworkp)->next;
+				else
+					myqp = &commit_list_insert(co, myqp)->next;
+				
+				/* add children to list as well */
+				if (obj->flags & UNINTERESTING)
+					consume_children = 0;
+				else
+					consume_children = 1;
+			}
 			
-			/* add children to list as well */
-			if (obj->flags & UNINTERESTING)
-				consume_children = 0;
-			else 
-				consume_children = 1;
 		}
 		
+		/* should we continue? */
+		if (!slop) {
+			if (!upath_nr) {
+				break;
+			} else if (ioutside || revs->show_all) {
+				/* pass it back to rev-list
+				 * we purposely ignore everything outside this cache, so we don't needlessly traverse the whole 
+				 * thing on uninteresting, but that does mean that we may need to bounce back 
+				 * and forth a few times with rev-list */
+				myworkp = &commit_list_insert(co, myworkp)->next;
+				
+				paths[path] = 0;
+				upath_nr--;
+			} else {
+				break;
+			}
+		} else if (!ipath_nr && co->date <= date)
+			slop--;
+		else
+			slop = SLOP;
+		
 		/* open parents */
 		if (entry->merge_nr) {
 			int j, off = index + OE_SIZE;
@@ -499,6 +647,11 @@ static int traverse_cache_slice_1(struct cache_slice_header *head, unsigned char
 				if (paths[p] & flag)
 					continue;
 				
+				if (flag == IPATH)
+					ipath_nr++;
+				else
+					upath_nr++;
+				
 				paths[p] |= flag;
 			}
 			
@@ -508,12 +661,55 @@ static int traverse_cache_slice_1(struct cache_slice_header *head, unsigned char
 		
 	}
 	
+	if (date_so_far)
+		*date_so_far = date;
+	if (slop_so_far)
+		*slop_so_far = slop;
 	retval = 0;
 	
+	/* success: attach to given lists */
+	if (myqp != &myq) {
+		**queue = myq;
+		*queue = myqp;
+	}
+	
+	while ((co = pop_commit(&mywork)) != 0) {
+		insert_by_date_cached(co, work, insert_cache, &insert_cache);
+	}
+	
+	/* free backup */
+	while (pop_commit(&unwork)) 
+		;
+	
 end:
 	free(paths);
 	free(last_objects);
 	
+	/* failure: restore work to previous condition
+	 * (cache corruption should *not* be fatal) */
+	if (retval) {
+		while ((co = pop_commit(&unwork)) != 0) {
+			restore_commit(co);
+			co->object.flags |= SEEN;
+			insert_by_date(co, work);
+		}
+		
+		/* free lists */
+		while ((co = pop_commit(&myq)) != 0)
+			restore_commit(co);
+		
+		while ((co = pop_commit(&mywork)) != 0)
+			restore_commit(co);
+		
+		/* truncate object array */
+		for (i = orig_obj_nr; i < revs->pending.nr; i++) {
+			struct object *obj = revs->pending.objects[i].item;
+			
+			obj->flags &= ~FACE_VALUE;
+		}
+		revs->pending.nr = orig_obj_nr;
+	}
+	
 	return retval;
 }
 
@@ -550,6 +746,7 @@ int traverse_cache_slice(struct rev_cache_info *rci, unsigned char *cache_sha1,
 	int fd = -1, retval = -3;
 	struct stat fi;
 	struct cache_slice_header head;
+	struct rev_cache_info def_rci;
 	unsigned char *map = MAP_FAILED;
 	
 	/* the index should've been loaded already to find cache_sha1, but it's good 
@@ -559,6 +756,15 @@ int traverse_cache_slice(struct rev_cache_info *rci, unsigned char *cache_sha1,
 	if (!idx_map)
 		return -1;
 	
+	/* load options */
+	if (!rci) {
+		rci = &def_rci;
+		init_rci(rci);
+	}
+	
+	save_unique = rci->save_unique;
+	add_to_pending = rci->add_to_pending;
+	
 	memset(&head, 0, sizeof(struct cache_slice_header));
 	
 	fd = open(git_path("rev-cache/%s", sha1_to_hex(cache_sha1)), O_RDONLY);
@@ -581,6 +787,10 @@ end:
 	if (fd != -1)
 		close(fd);
 	
+	/* remember this! */
+	if (retval)
+		mark_bad_slice(cache_sha1);
+	
 	return retval;
 }
 
@@ -775,6 +985,7 @@ static void handle_paths(struct commit *commit, struct object_entry *object, str
 		if (pt->commit == commit) {
 			if (paths[pt->path] != PATH_IN_USE)
 				paths[pt->path]--;
+			
 			remove_path_track(ppt, 0);
 			pt = *ppt;
 		} else {
@@ -1034,6 +1245,21 @@ static int add_unique_objects(struct commit *commit)
 	int i, j, next;
 	char is_first = 1;
 	
+	/* but wait!  is this itself from a slice? */
+	if (commit->unique) {
+		struct object_list *olist;
+		
+		olist = commit->unique;
+		i = 0;
+		while (olist) {
+			add_object_entry(olist->item->sha1, 0, 0, 0);
+			i++;
+			olist = olist->next;
+		}
+		
+		return i;
+	}
+	
 	/* ...no, calculate unique objects */
 	strbuf_init(&os, 0);
 	strbuf_init(&ost, 0);
@@ -1087,10 +1313,13 @@ static int add_unique_objects(struct commit *commit)
 	for (i = 0; i < os.len; i += 20)
 		add_object_entry((unsigned char *)(os.buf + i), 0, 0, 0);
 	
+	/* last but not least, the main tree */
+	add_object_entry(commit->tree->object.sha1, 0, 0, 0);
+	
 	strbuf_release(&ost);
 	strbuf_release(&os);
 	
-	return i / 20;
+	return i / 20 + 1;
 }
 
 static void init_revcache_directory(void)
@@ -1171,6 +1400,7 @@ int make_cache_slice(struct rev_cache_info *rci,
 	revs->blob_objects = 1;
 	revs->topo_order = 1;
 	revs->lifo = 1;
+	save_unique = 1; /* re-use info from other caches if possible */
 	
 	setup_revisions(0, 0, revs, 0);
 	if (prepare_revision_walk(revs))
@@ -1203,14 +1433,8 @@ int make_cache_slice(struct rev_cache_info *rci,
 		add_object_entry(0, &object, &merge_paths, &split_paths);
 		object_nr++;
 		
-		if (rci->objects && !(commit->object.flags & TREESAME)) {
-			/* add all unique children for this commit */
-			add_object_entry(commit->tree->object.sha1, 0, 0, 0);
-			object_nr++;
-			
-			if (!object.is_start)
-				object_nr += add_unique_objects(commit);
-		}
+		if (rci->objects && !(commit->object.flags & TREESAME) && !object.is_start)
+			object_nr += add_unique_objects(commit);
 		
 		/* print every ~1MB or so */
 		if (buffer.len > 1000000) {
@@ -1497,7 +1721,6 @@ void ends_from_slices(struct rev_info *revs, unsigned int flags, unsigned char *
 	
 }
 
-
 /* the most work-intensive attributes in the cache are the unique objects and size, both 
  * of which can be re-used.  although path structures will be isomorphic, path generation is 
  * not particularly expensive, and at any rate we need to re-sort the commits */
@@ -1626,4 +1849,4 @@ int regenerate_cache_index(struct rev_cache_info *rci)
 	}
 	
 	return 0;
-}
\ No newline at end of file
+}
diff --git a/revision.c b/revision.c
index d85abae..9fb5809 100644
--- a/revision.c
+++ b/revision.c
@@ -638,7 +638,11 @@ static int limit_list(struct rev_info *revs)
 	struct commit_list *list = revs->commits;
 	struct commit_list *newlist = NULL;
 	struct commit_list **p = &newlist;
+	unsigned char *cache_sha1;
+	struct rev_cache_info rci;
+	char used_cache;
 
+	init_rci(&rci);
 	while (list) {
 		struct commit_list *entry = list;
 		struct commit *commit = list->item;
@@ -650,24 +654,39 @@ static int limit_list(struct rev_info *revs)
 
 		if (revs->max_age != -1 && (commit->date < revs->max_age))
 			obj->flags |= UNINTERESTING;
-		if (add_parents_to_list(revs, commit, &list, NULL) < 0)
-			return -1;
-		if (obj->flags & UNINTERESTING) {
-			mark_parents_uninteresting(commit);
-			if (revs->show_all)
-				p = &commit_list_insert(commit, p)->next;
-			slop = still_interesting(list, date, slop);
-			if (slop)
+		
+		/* rev-cache to the rescue!!! */
+		used_cache = 0;
+		if (!revs->dont_cache_me && !(obj->flags & ADDED)) {
+			cache_sha1 = get_cache_slice(commit);
+			if (cache_sha1) {
+				if (traverse_cache_slice(&rci, cache_sha1, revs, commit, &date, &slop, &p, &list) < 0)
+					used_cache = 0;
+				else
+					used_cache = 1;
+			}
+		}
+		
+		if (!used_cache) {
+			if (add_parents_to_list(revs, commit, &list, NULL) < 0)
+				return -1;
+			if (obj->flags & UNINTERESTING) {
+				mark_parents_uninteresting(commit); /* ME: why? */
+				if (revs->show_all)
+					p = &commit_list_insert(commit, p)->next;
+				slop = still_interesting(list, date, slop);
+				if (slop > 0)
+					continue;
+				/* If showing all, add the whole pending list to the end */
+				if (revs->show_all)
+					*p = list;
+				break;
+			}
+			if (revs->min_age != -1 && (commit->date > revs->min_age))
 				continue;
-			/* If showing all, add the whole pending list to the end */
-			if (revs->show_all)
-				*p = list;
-			break;
+			date = commit->date;
+			p = &commit_list_insert(commit, p)->next;
 		}
-		if (revs->min_age != -1 && (commit->date > revs->min_age))
-			continue;
-		date = commit->date;
-		p = &commit_list_insert(commit, p)->next;
 
 		show = show_early_output;
 		if (!show)
@@ -1372,6 +1391,11 @@ int setup_revisions(int argc, const char **argv, struct rev_info *revs, const ch
 	if (revs->reflog_info && revs->graph)
 		die("cannot combine --walk-reflogs with --graph");
 
+	/* limits on caching
+	 * todo: implement this functionality */
+	if (revs->prune || revs->diff)
+		revs->dont_cache_me = 1;
+
 	return left;
 }
 
@@ -1654,6 +1678,8 @@ static int commit_match(struct commit *commit, struct rev_info *opt)
 {
 	if (!opt->grep_filter.pattern_list)
 		return 1;
+	if (!commit->object.parsed)
+		parse_commit(commit);
 	return grep_buffer(&opt->grep_filter,
 			   NULL, /* we say nothing, not even filename */
 			   commit->buffer, strlen(commit->buffer));
@@ -1706,6 +1732,7 @@ static struct commit *get_revision_1(struct rev_info *revs)
 	do {
 		struct commit_list *entry = revs->commits;
 		struct commit *commit = entry->item;
+		struct object *obj = &commit->object;
 
 		revs->commits = entry->next;
 		free(entry);
@@ -1722,11 +1749,43 @@ static struct commit *get_revision_1(struct rev_info *revs)
 			if (revs->max_age != -1 &&
 			    (commit->date < revs->max_age))
 				continue;
+			
+			if (!revs->dont_cache_me) {
+				struct commit_list *queue = 0, **queuep = &queue;;
+				unsigned char *cache_sha1;
+				
+				if (obj->flags & ADDED)
+					goto skip_parenting;
+				
+				cache_sha1 = get_cache_slice(commit);
+				if (cache_sha1) {
+					struct rev_cache_info rci;
+					
+					init_rci(&rci);
+					
+					if (!traverse_cache_slice(&rci, cache_sha1, revs, commit, 0, 0, &queuep, &revs->commits)) {
+						struct commit_list *work = revs->commits;
+						
+						/* attach queue to end of ->commits */
+						while (work && work->next)
+							work = work->next;
+						
+						if (work)
+							work->next = queue;
+						else
+							revs->commits = queue;
+						
+						goto skip_parenting;
+					}
+				}
+			}
+			
 			if (add_parents_to_list(revs, commit, &revs->commits, NULL) < 0)
 				die("Failed to traverse parents of commit %s",
 				    sha1_to_hex(commit->object.sha1));
 		}
 
+skip_parenting:
 		switch (simplify_commit(revs, commit)) {
 		case commit_ignore:
 			continue;
diff --git a/t/t6015-rev-cache-list.sh b/t/t6015-rev-cache-list.sh
index 9cd722a..b702ce9 100755
--- a/t/t6015-rev-cache-list.sh
+++ b/t/t6015-rev-cache-list.sh
@@ -33,7 +33,8 @@ test_expect_success 'init repo' '
 	echo omg >smoke/bong && 
 	git add . && 
 	git commit -m "omg" && 
-	
+
+	sleep 2 && 
 	git branch b4 && 
 	git checkout b4 && 
 	echo shazam >file8 && 
@@ -42,9 +43,9 @@ test_expect_success 'init repo' '
 	git merge -m "merge b2" b2 && 
 	
 	echo bam >smoke/pipe && 
-	git add .
+	git add . && 
 	git commit -m "bam" && 
-	
+
 	git checkout master && 
 	echo pow >file7 && 
 	git add . && 
@@ -67,18 +68,26 @@ test_expect_success 'init repo' '
 	git add . && 
 	git commit -m "lol" && 
 
+	sleep 2 && 
 	git checkout master && 
 	git merge -m "triple merge" b1 b11 && 
 	git rm -r d1 &&  
+	sleep 2 && 
 	git commit -a -m "oh noes"
 '
 
-git-rev-list HEAD --not HEAD~3 >proper_commit_list_limited
-git-rev-list HEAD >proper_commit_list
-git-rev-list HEAD --objects >proper_object_list
+max_date=`git-rev-list --timestamp HEAD~1 --max-count=1 | grep -e "^[0-9]*" -o`
+min_date=`git-rev-list --timestamp b4 --max-count=1 | grep -e "^[0-9]*" -o`
+
+git-rev-list --topo-order HEAD --not HEAD~3 >proper_commit_list_limited
+git-rev-list --topo-order HEAD --not HEAD~2 >proper_commit_list_limited2
+git-rev-list --topo-order HEAD >proper_commit_list
+git-rev-list --objects HEAD >proper_object_list
+git-rev-list HEAD --max-age=$min_date --min-age=$max_date >proper_list_date_limited
+
+cache_sha1=`git-rev-cache add HEAD 2>output.err`
 
 test_expect_success 'make cache slice' '
-	git-rev-cache add HEAD 2>output.err && 
 	grep "final return value: 0" output.err
 '
 
@@ -98,7 +107,7 @@ test_expect_success 'test rev-caches walker directly (unlimited)' '
 	test -z `$sha1diff list proper_commit_list`
 '
 
-test_expect_success 'test rev-list rev-list traversal (limited)' '
+test_expect_success 'test rev-list traversal (limited)' '
 	git-rev-list HEAD --not HEAD~3 >list && 
 	test -z `$sha1diff list proper_commit_list_limited`
 '
@@ -114,15 +123,106 @@ test_expect_success 'test rev-caches walker with objects' '
 	test -z `$sha1diff list proper_object_list`
 '
 
-test_expect_success 'test rev-list with objects (limited)' '
+test_expect_success 'test rev-list with objects (topo order)' '
 	git-rev-list --topo-order --objects HEAD >list && 
 	test -z `$sha1diff list proper_object_list`
 '
 
-test_expect_success 'test rev-list with objects (unlimited)' '
+test_expect_success 'test rev-list with objects (no order)' '
 	git-rev-list --objects HEAD >list && 
 	test -z `$sha1diff list proper_object_list`
 '
 
+#verify age limiting
+test_expect_success 'test rev-list date limiting (topo order)' '
+	git-rev-list --topo-order --max-age=$min_date --min-age=$max_date HEAD >list && 
+	test -z `$sha1diff list proper_list_date_limited`
+'
+
+test_expect_success 'test rev-list date limiting (no order)' '
+	git-rev-list --max-age=$min_date --min-age=$max_date HEAD >list && 
+	test -z `sha1diff list proper_list_date_limited`
+'
+
+#check partial cache slice
+test_expect_success 'saving old cache and generating partial slice' '
+	cp ".git/rev-cache/$cache_sha1" .git/rev-cache/.old && 
+	rm ".git/rev-cache/$cache_sha1" .git/rev-cache/index && 
+
+	git-rev-cache add HEAD~2 2>output.err && 
+	grep "final return value: 0" output.err
+'
+
+test_expect_success 'rev-list with wholly interesting partial slice' '
+	git-rev-list --topo-order HEAD >list &&
+	test_cmp list proper_commit_list
+'
+
+test_expect_success 'rev-list with partly uninteresting partial slice' '
+	git-rev-list --topo-order HEAD --not HEAD~3 >list && 
+	test_cmp list proper_commit_list_limited
+'
+
+test_expect_success 'rev-list with wholly uninteresting partial slice' '
+	git-rev-list --topo-order HEAD --not HEAD~2 >list && 
+	test_cmp list proper_commit_list_limited2
+'
+
+#try out index generation and fuse (note that --all == HEAD in this case)
+#probably should make a test for that too...
+test_expect_success 'make fresh slice' '
+	git-rev-cache add --all --fresh 2>output.err && 
+	grep "final return value: 0" output.err
+'
+
+test_expect_success 'check dual slices' '
+	git-rev-list --topo-order HEAD~2 HEAD >list && 
+	test_cmp list proper_commit_list
+'
+
+test_expect_success 'regenerate index' '
+	rm .git/rev-cache/index && 
+	git-rev-cache index 2>output.err && 
+	grep "final return value: 0" output.err
+'
+
+test_expect_success 'fuse slices' '
+	test -e .git/rev-cache/.old && 
+	git-rev-cache fuse 2>output.err && 
+	grep "final return value: 0" output.err && 
+	test_cmp .git/rev-cache/$cache_sha1 .git/rev-cache/.old
+'
+
+#make sure we can smoothly handle corrupted caches
+test_expect_success 'corrupt slice' '
+	echo bla >.git/rev-cache/$cache_sha1
+'
+
+test_expect_success 'test rev-list traversal (limited) (corrupt slice)' '
+	git-rev-list HEAD --not HEAD~3 >list && 
+	test -z `$sha1diff list proper_commit_list_limited`
+'
+
+test_expect_success 'test rev-list traversal (unlimited) (corrupt slice)' '
+	git-rev-list HEAD >list && 
+	test -z `$sha1diff list proper_commit_list`
+'
+
+test_expect_success 'corrupt index' '
+	echo blu >.git/rev-cache/index
+'
+
+test_expect_success 'test rev-list traversal (limited) (corrupt index)' '
+	git-rev-list HEAD --not HEAD~3 >list && 
+	test -z `$sha1diff list proper_commit_list_limited`
+'
+
+test_expect_success 'test rev-list traversal (unlimited) (corrupt index)' '
+	git-rev-list HEAD >list && 
+	test -z `$sha1diff list proper_commit_list`
+'
+
+#todo: test --ignore-size in fuse
+
 test_done
 
-- 
tg: (de9a466..) t/revcache/integration (depends on: t/revcache/misc)