Merge the new object model thing from Daniel Barkalow

This was a real git merge with conflicts. I'll commit the scripts I used
to do the merge next.

Not pretty, but it's half-way functional.

12 files changed, 512 insertions, 160 deletions

diff --git a/Makefile b/Makefile
index 76c4f7ca4f..f446a1f9cf 100644
--- a/Makefile
+++ b/Makefile
@@ -43,8 +43,8 @@ commit-tree: commit-tree.o read-cache.o
 cat-file: cat-file.o read-cache.o
 	$(CC) $(CFLAGS) -o cat-file cat-file.o read-cache.o $(LIBS)
 
-fsck-cache: fsck-cache.o read-cache.o
-	$(CC) $(CFLAGS) -o fsck-cache fsck-cache.o read-cache.o $(LIBS)
+fsck-cache: fsck-cache.o read-cache.o object.o commit.o tree.o blob.o
+	$(CC) $(CFLAGS) -o fsck-cache fsck-cache.o read-cache.o object.o commit.o tree.o blob.o $(LIBS)
 
 checkout-cache: checkout-cache.o read-cache.o
 	$(CC) $(CFLAGS) -o checkout-cache checkout-cache.o read-cache.o $(LIBS)
@@ -52,8 +52,8 @@ checkout-cache: checkout-cache.o read-cache.o
 diff-tree: diff-tree.o read-cache.o
 	$(CC) $(CFLAGS) -o diff-tree diff-tree.o read-cache.o $(LIBS)
 
-rev-tree: rev-tree.o read-cache.o
-	$(CC) $(CFLAGS) -o rev-tree rev-tree.o read-cache.o $(LIBS)
+rev-tree: rev-tree.o read-cache.o object.o commit.o tree.o blob.o
+	$(CC) $(CFLAGS) -o rev-tree rev-tree.o read-cache.o object.o commit.o tree.o blob.o $(LIBS)
 
 show-files: show-files.o read-cache.o
 	$(CC) $(CFLAGS) -o show-files show-files.o read-cache.o $(LIBS)
@@ -64,8 +64,8 @@ check-files: check-files.o read-cache.o
 ls-tree: ls-tree.o read-cache.o
 	$(CC) $(CFLAGS) -o ls-tree ls-tree.o read-cache.o $(LIBS)
 
-merge-base: merge-base.o read-cache.o
-	$(CC) $(CFLAGS) -o merge-base merge-base.o read-cache.o $(LIBS)
+merge-base: merge-base.o read-cache.o object.o commit.o tree.o blob.o
+	$(CC) $(CFLAGS) -o merge-base merge-base.o read-cache.o object.o commit.o tree.o blob.o $(LIBS)
 
 merge-cache: merge-cache.o read-cache.o
 	$(CC) $(CFLAGS) -o merge-cache merge-cache.o read-cache.o $(LIBS)
diff --git a/blob.c b/blob.c
new file mode 100644
index 0000000000..35031af62b
--- /dev/null
+++ b/blob.c
@@ -0,0 +1,24 @@
+#include "blob.h"
+#include "cache.h"
+#include <stdlib.h>
+
+const char *blob_type = "blob";
+
+struct blob *lookup_blob(unsigned char *sha1)
+{
+	struct object *obj = lookup_object(sha1);
+	if (!obj) {
+		struct blob *ret = malloc(sizeof(struct blob));
+		memset(ret, 0, sizeof(struct blob));
+		created_object(sha1, &ret->object);
+		ret->object.type = blob_type;
+		ret->object.parsed = 1;
+		return ret;
+	}
+	if (obj->parsed && obj->type != blob_type) {
+		error("Object %s is a %s, not a blob", 
+		      sha1_to_hex(sha1), obj->type);
+		return NULL;
+	}
+	return (struct blob *) obj;
+}
diff --git a/blob.h b/blob.h
new file mode 100644
index 0000000000..5cbf6d65ee
--- /dev/null
+++ b/blob.h
@@ -0,0 +1,14 @@
+#ifndef BLOB_H
+#define BLOB_H
+
+#include "object.h"
+
+extern const char *blob_type;
+
+struct blob {
+	struct object object;
+};
+
+struct blob *lookup_blob(unsigned char *sha1);
+
+#endif /* BLOB_H */
diff --git a/commit.c b/commit.c
new file mode 100644
index 0000000000..eda45d7e15
--- /dev/null
+++ b/commit.c
@@ -0,0 +1,85 @@
+#include "commit.h"
+#include "cache.h"
+#include <string.h>
+
+const char *commit_type = "commit";
+
+struct commit *lookup_commit(unsigned char *sha1)
+{
+	struct object *obj = lookup_object(sha1);
+	if (!obj) {
+		struct commit *ret = malloc(sizeof(struct commit));
+		memset(ret, 0, sizeof(struct commit));
+		created_object(sha1, &ret->object);
+		return ret;
+	}
+	if (obj->parsed && obj->type != commit_type) {
+		error("Object %s is a %s, not a commit", 
+		      sha1_to_hex(sha1), obj->type);
+		return NULL;
+	}
+	return (struct commit *) obj;
+}
+
+static unsigned long parse_commit_date(const char *buf)
+{
+	unsigned long date;
+
+	if (memcmp(buf, "author", 6))
+		return 0;
+	while (*buf++ != '\n')
+		/* nada */;
+	if (memcmp(buf, "committer", 9))
+		return 0;
+	while (*buf++ != '>')
+		/* nada */;
+	date = strtoul(buf, NULL, 10);
+	if (date == ULONG_MAX)
+		date = 0;
+	return date;
+}
+
+int parse_commit(struct commit *item)
+{
+	char type[20];
+	void * buffer, *bufptr;
+	unsigned long size;
+	unsigned char parent[20];
+	if (item->object.parsed)
+		return 0;
+	item->object.parsed = 1;
+	buffer = bufptr = read_sha1_file(item->object.sha1, type, &size);
+	if (!buffer)
+		return error("Could not read %s",
+			     sha1_to_hex(item->object.sha1));
+	if (strcmp(type, commit_type))
+		return error("Object %s not a commit",
+			     sha1_to_hex(item->object.sha1));
+	item->object.type = commit_type;
+	get_sha1_hex(bufptr + 5, parent);
+	item->tree = lookup_tree(parent);
+	add_ref(&item->object, &item->tree->object);
+	bufptr += 46; /* "tree " + "hex sha1" + "\n" */
+	while (!memcmp(bufptr, "parent ", 7) &&
+	       !get_sha1_hex(bufptr + 7, parent)) {
+		struct commit_list *new_parent = 
+			malloc(sizeof(struct commit_list));
+		new_parent->next = item->parents;
+		new_parent->item = lookup_commit(parent);
+		add_ref(&item->object, &new_parent->item->object);
+		item->parents = new_parent;
+		bufptr += 48;
+	}
+	item->date = parse_commit_date(bufptr);
+	free(buffer);
+	return 0;
+}
+
+void free_commit_list(struct commit_list *list)
+{
+	while (list) {
+		struct commit_list *temp = list;
+		list = temp->next;
+		free(temp);
+	}
+}
diff --git a/commit.h b/commit.h
new file mode 100644
index 0000000000..4afd27b109
--- /dev/null
+++ b/commit.h
@@ -0,0 +1,27 @@
+#ifndef COMMIT_H
+#define COMMIT_H
+
+#include "object.h"
+#include "tree.h"
+
+struct commit_list {
+	struct commit *item;
+	struct commit_list *next;
+};
+
+struct commit {
+	struct object object;
+	unsigned long date;
+	struct commit_list *parents;
+	struct tree *tree;
+};
+
+extern const char *commit_type;
+
+struct commit *lookup_commit(unsigned char *sha1);
+
+int parse_commit(struct commit *item);
+
+void free_commit_list(struct commit_list *list);
+
+#endif /* COMMIT_H */
diff --git a/fsck-cache.c b/fsck-cache.c
index b8b66d7d1d..edaf9e4600 100644
--- a/fsck-cache.c
+++ b/fsck-cache.c
@@ -3,7 +3,11 @@
 #include <sys/types.h>
 #include <dirent.h>
 
-#include "revision.h"
+#include "commit.h"
+#include "tree.h"
+#include "blob.h"
+
+#define REACHABLE 0x0001
 
 static int show_unreachable = 0;
 static unsigned char head_sha1[20];
@@ -13,96 +17,54 @@ static void check_connectivity(void)
 	int i;
 
 	/* Look up all the requirements, warn about missing objects.. */
-	for (i = 0; i < nr_revs; i++) {
-		struct revision *rev = revs[i];
+	for (i = 0; i < nr_objs; i++) {
+		struct object *obj = objs[i];
 
-		if (show_unreachable && !(rev->flags & REACHABLE)) {
-			printf("unreachable %s %s\n", rev->tag, sha1_to_hex(rev->sha1));
+		if (show_unreachable && !(obj->flags & REACHABLE)) {
+			printf("unreachable %s\n", sha1_to_hex(obj->sha1));
 			continue;
 		}
 
-		switch (rev->flags & (SEEN | USED)) {
-		case 0:
-			printf("bad %s %s\n", rev->tag, sha1_to_hex(rev->sha1));
-			break;
-		case USED:
-			printf("missing %s, %s\n", rev->tag, sha1_to_hex(rev->sha1));
-			break;
-		case SEEN:
-			printf("dangling %s %s\n", rev->tag, sha1_to_hex(rev->sha1));
-			break;
+		if (!obj->parsed) {
+			printf("missing %s %s\n", obj->type, 
+			       sha1_to_hex(obj->sha1));
+		}
+		if (!obj->used) {
+			printf("dangling %s %s\n", obj->type, 
+			       sha1_to_hex(obj->sha1));
 		}
 	}
 }
 
-static void mark_needs_sha1(unsigned char *parent, const char *ptag, unsigned char *child, const char *ctag)
-{
-	struct revision * child_rev = add_relationship(lookup_rev(parent, ptag), child, ctag);
-	child_rev->flags |= USED;
-}
-
-static int mark_sha1_seen(unsigned char *sha1, const char *tag)
-{
-	struct revision *rev = lookup_rev(sha1, tag);
-
-	rev->flags |= SEEN;
-	return 0;
-}
-
 static int fsck_tree(unsigned char *sha1, void *data, unsigned long size)
 {
-	int warn_old_tree = 1;
-
-	while (size) {
-		int len = 1+strlen(data);
-		unsigned char *file_sha1 = data + len;
-		char *path = strchr(data, ' ');
-		unsigned int mode;
-		if (size < len + 20 || !path || sscanf(data, "%o", &mode) != 1)
-			return -1;
-
-		/* Warn about trees that don't do the recursive thing.. */
-		if (warn_old_tree && strchr(path, '/')) {
-			fprintf(stderr, "warning: fsck-cache: tree %s has full pathnames in it\n", sha1_to_hex(sha1));
-			warn_old_tree = 0;
-		}
-
-		data += len + 20;
-		size -= len + 20;
-		mark_needs_sha1(sha1, "tree", file_sha1, S_ISDIR(mode) ? "tree" : "blob");
+	struct tree *item = lookup_tree(sha1);
+	if (parse_tree(item))
+		return -1;
+	if (item->has_full_path) {
+		fprintf(stderr, "warning: fsck-cache: tree %s "
+			"has full pathnames in it\n", sha1_to_hex(sha1));
 	}
 	return 0;
 }
 
 static int fsck_commit(unsigned char *sha1, void *data, unsigned long size)
 {
-	int parents;
-	unsigned char tree_sha1[20];
-	unsigned char parent_sha1[20];
-
-	if (memcmp(data, "tree ", 5))
+	struct commit *commit = lookup_commit(sha1);
+	if (parse_commit(commit))
 		return -1;
-	if (get_sha1_hex(data + 5, tree_sha1) < 0)
+	if (!commit->tree)
 		return -1;
-	mark_needs_sha1(sha1, "commit", tree_sha1, "tree");
-	data += 5 + 40 + 1;	/* "tree " + <hex sha1> + '\n' */
-	parents = 0;
-	while (!memcmp(data, "parent ", 7)) {
-		if (get_sha1_hex(data + 7, parent_sha1) < 0)
-			return -1;
-		mark_needs_sha1(sha1, "commit", parent_sha1, "commit");
-		data += 7 + 40 + 1; 	/* "parent " + <hex sha1> + '\n' */
-		parents++;
-	}
-	if (!parents)
+	if (!commit->parents)
 		printf("root %s\n", sha1_to_hex(sha1));
 	return 0;
 }
 
-static int fsck_entry(unsigned char *sha1, char *tag, void *data, unsigned long size)
+static int fsck_entry(unsigned char *sha1, char *tag, void *data, 
+		      unsigned long size)
 {
 	if (!strcmp(tag, "blob")) {
-		/* Nothing to check */;
+		lookup_blob(sha1); /* Nothing to check; but notice it. */
 	} else if (!strcmp(tag, "tree")) {
 		if (fsck_tree(sha1, data, size) < 0)
 			return -1;
@@ -111,7 +73,7 @@ static int fsck_entry(unsigned char *sha1, char *tag, void *data, unsigned long
 			return -1;
 	} else
 		return -1;
-	return mark_sha1_seen(sha1, tag);
+	return 0;
 }
 
 static int fsck_name(char *hex)
@@ -125,7 +87,8 @@ static int fsck_name(char *hex)
 			unsigned long size;
 			void *buffer = NULL;
 			if (!check_sha1_signature(sha1, map, mapsize))
-				buffer = unpack_sha1_file(map, mapsize, type, &size);
+				buffer = unpack_sha1_file(map, mapsize, type,
+							  &size);
 			munmap(map, mapsize);
 			if (buffer && !fsck_entry(sha1, type, buffer, size))
 				return 0;
@@ -186,7 +149,9 @@ int main(int argc, char **argv)
 			continue;
 		}
 		if (!get_sha1_hex(argv[i], head_sha1)) {
-			mark_reachable(lookup_rev(head_sha1, "commit"), REACHABLE);
+			struct object *obj = &lookup_commit(head_sha1)->object;
+			obj->used = 1;
+			mark_reachable(obj, REACHABLE);
 			heads++;
 			continue;
 		}
diff --git a/merge-base.c b/merge-base.c
index dac5e4b5e0..ac1153bc56 100644
--- a/merge-base.c
+++ b/merge-base.c
@@ -1,54 +1,92 @@
+#include <stdlib.h>
 #include "cache.h"
-#include "revision.h"
+#include "commit.h"
 
-/*
- * This is stupid. We could have much better heurstics, I bet.
- */
-static int better(struct revision *new, struct revision *old)
+static struct commit *process_list(struct commit_list **list_p, int this_mark,
+				   int other_mark)
 {
-	return new->date > old->date;
+	struct commit_list *parent, *temp;
+	struct commit_list *posn = *list_p;
+	*list_p = NULL;
+	while (posn) {
+		parse_commit(posn->item);
+		if (posn->item->object.flags & this_mark) {
+			/*
+			  printf("%d already seen %s %x\n",
+			  this_mark
+			  sha1_to_hex(posn->parent->sha1),
+			  posn->parent->flags);
+			*/
+			/* do nothing; this indicates that this side
+			 * split and reformed, and we only need to
+			 * mark it once.
+			 */
+		} else if (posn->item->object.flags & other_mark) {
+			return posn->item;
+		} else {
+			/*
+			  printf("%d based on %s\n",
+			  this_mark,
+			  sha1_to_hex(posn->parent->sha1));
+			*/
+			posn->item->object.flags |= this_mark;
+			
+			parent = posn->item->parents;
+			while (parent) {
+				temp = malloc(sizeof(struct commit_list));
+				temp->next = *list_p;
+				temp->item = parent->item;
+				*list_p = temp;
+				parent = parent->next;
+			}
+		}
+		posn = posn->next;
+	}
+	return NULL;
 }
 
-static struct revision *common_parent(struct revision *rev1, struct revision *rev2)
+struct commit *common_ancestor(struct commit *rev1, struct commit *rev2)
 {
-	int i;
-	struct revision *best = NULL;
+	struct commit_list *rev1list = malloc(sizeof(struct commit_list));
+	struct commit_list *rev2list = malloc(sizeof(struct commit_list));
+
+	rev1list->item = rev1;
+	rev1list->next = NULL;
+
+	rev2list->item = rev2;
+	rev2list->next = NULL;
 
-	mark_reachable(rev1, 1);
-	mark_reachable(rev2, 2);
-	for (i = 0; i < nr_revs ;i++) {
-		struct revision *rev = revs[i];
-		if ((rev->flags & 3) != 3)
-			continue;
-		if (!best) {
-			best = rev;
-			continue;
+	while (rev1list || rev2list) {
+		struct commit *ret;
+		ret = process_list(&rev1list, 0x1, 0x2);
+		if (ret) {
+			/* XXXX free lists */
+			return ret;
+		}
+		ret = process_list(&rev2list, 0x2, 0x1);
+		if (ret) {
+			/* XXXX free lists */
+			return ret;
 		}
-		if (better(rev, best))
-			best = rev;
 	}
-	return best;
+	return NULL;
 }
 
 int main(int argc, char **argv)
 {
-	unsigned char rev1[20], rev2[20];
-	struct revision *common;
-
-	if (argc != 3 || get_sha1_hex(argv[1], rev1) || get_sha1_hex(argv[2], rev2))
-		usage("merge-base <commit1> <commit2>");
+	struct commit *rev1, *rev2, *ret;
+	unsigned char rev1key[20], rev2key[20];
 
-	/*
-	 * We will eventually want to include a revision cache file
-	 * that "rev-tree.c" has generated, since this is going to
-	 * otherwise be quite expensive for big trees..
-	 *
-	 * That's some time off, though, and in the meantime we know
-	 * that we have a solution to the eventual expense.
-	 */
-	common = common_parent(parse_commit(rev1), parse_commit(rev2));
-	if (!common)
-		die("no common parent found");
-	printf("%s\n", sha1_to_hex(common->sha1));
+	if (argc != 3 ||
+	    get_sha1_hex(argv[1], rev1key) ||
+	    get_sha1_hex(argv[2], rev2key)) {
+		usage("merge-base <commit-id> <commit-id>");
+	}
+	rev1 = lookup_commit(rev1key);
+	rev2 = lookup_commit(rev2key);
+	ret = common_ancestor(rev1, rev2);
+	if (!ret)
+		return 1;
+	printf("%s\n", sha1_to_hex(ret->object.sha1));
 	return 0;
 }
diff --git a/object.c b/object.c
new file mode 100644
index 0000000000..cfa2337641
--- /dev/null
+++ b/object.c
@@ -0,0 +1,96 @@
+#include "object.h"
+#include "cache.h"
+#include <stdlib.h>
+#include <string.h>
+
+struct object **objs;
+int nr_objs;
+static int obj_allocs;
+
+static int find_object(unsigned char *sha1)
+{
+	int first = 0, last = nr_objs;
+
+        while (first < last) {
+                int next = (first + last) / 2;
+                struct object *obj = objs[next];
+                int cmp;
+
+                cmp = memcmp(sha1, obj->sha1, 20);
+                if (!cmp)
+                        return next;
+                if (cmp < 0) {
+                        last = next;
+                        continue;
+                }
+                first = next+1;
+        }
+        return -first-1;
+}
+
+struct object *lookup_object(unsigned char *sha1)
+{
+	int pos = find_object(sha1);
+	if (pos >= 0)
+		return objs[pos];
+	return NULL;
+}
+
+void created_object(unsigned char *sha1, struct object *obj)
+{
+	int pos = find_object(sha1);
+
+	obj->parsed = 0;
+	memcpy(obj->sha1, sha1, 20);
+	obj->type = NULL;
+	obj->refs = NULL;
+	obj->used = 0;
+
+	if (pos >= 0)
+		die("Inserting %s twice\n", sha1_to_hex(sha1));
+	pos = -pos-1;
+
+	if (obj_allocs == nr_objs) {
+		obj_allocs = alloc_nr(obj_allocs);
+		objs = realloc(objs, obj_allocs * sizeof(struct object *));
+	}
+
+	/* Insert it into the right place */
+	memmove(objs + pos + 1, objs + pos, (nr_objs - pos) * 
+		sizeof(struct object *));
+
+	objs[pos] = obj;
+	nr_objs++;
+}
+
+void add_ref(struct object *refer, struct object *target)
+{
+	struct object_list **pp = &refer->refs;
+	struct object_list *p;
+	
+	while ((p = *pp) != NULL) {
+		if (p->item == target)
+			return;
+		pp = &p->next;
+	}
+
+	target->used = 1;
+	p = malloc(sizeof(*p));
+	p->item = target;
+	p->next = NULL;
+	*pp = p;
+}
+
+void mark_reachable(struct object *obj, unsigned int mask)
+{
+	struct object_list *p = obj->refs;
+
+	/* If we've been here already, don't bother */
+	if (obj->flags & mask)
+		return;
+	obj->flags |= mask;
+	while (p) {
+		mark_reachable(p->item, mask);
+		p = p->next;
+	}
+}
diff --git a/object.h b/object.h
new file mode 100644
index 0000000000..bc607fd55f
--- /dev/null
+++ b/object.h
@@ -0,0 +1,29 @@
+#ifndef OBJECT_H
+#define OBJECT_H
+
+struct object_list {
+	struct object *item;
+	struct object_list *next;
+};
+
+struct object {
+	unsigned parsed : 1;
+	unsigned used : 1;
+	unsigned int flags;
+	unsigned char sha1[20];
+	const char *type;
+	struct object_list *refs;
+};
+
+int nr_objs;
+struct object **objs;
+
+struct object *lookup_object(unsigned char *sha1);
+
+void created_object(unsigned char *sha1, struct object *obj);
+
+void add_ref(struct object *refer, struct object *target);
+
+void mark_reachable(struct object *obj, unsigned int mask);
+
+#endif /* OBJECT_H */
diff --git a/rev-tree.c b/rev-tree.c
index 3c54769258..c3884e3595 100644
--- a/rev-tree.c
+++ b/rev-tree.c
@@ -4,7 +4,7 @@
 #include <ctype.h>
 
 #include "cache.h"
-#include "revision.h"
+#include "commit.h"
 
 /*
  * revision.h leaves the low 16 bits of the "flags" field of the
@@ -18,38 +18,7 @@ static int basemask = 0;
 
 static void read_cache_file(const char *path)
 {
-	FILE *file = fopen(path, "r");
-	char line[500];
-
-	if (!file)
-		die("bad revtree cache file (%s)", path);
-
-	while (fgets(line, sizeof(line), file)) {
-		unsigned long date;
-		unsigned char sha1[20];
-		struct revision *rev;
-		const char *buf;
-
-		if (sscanf(line, "%lu", &date) != 1)
-			break;
-		buf = strchr(line, ' ');
-		if (!buf)
-			break;
-		if (get_sha1_hex(buf+1, sha1))
-			break;
-		rev = lookup_rev(sha1, "commit");
-		rev->flags |= SEEN;
-		rev->date = date;
-
-		/* parents? */
-		while ((buf = strchr(buf+1, ' ')) != NULL) {
-			unsigned char parent[20];
-			if (get_sha1_hex(buf + 1, parent))
-				break;
-			add_relationship(rev, parent, "commit");
-		}
-	}
-	fclose(file);
+	die("no revtree cache file yet");
 }
 
 /*
@@ -61,16 +30,16 @@ static void read_cache_file(const char *path)
  * And sometimes we're only interested in "edge" commits, ie
  * places where the marking changes between parent and child.
  */
-static int interesting(struct revision *rev)
+static int interesting(struct commit *rev)
 {
-	unsigned mask = marked(rev);
+	unsigned mask = rev->object.flags;
 
 	if (!mask)
 		return 0;
 	if (show_edges) {
-		struct parent *p = rev->parent;
+		struct commit_list *p = rev->parents;
 		while (p) {
-			if (mask != marked(p->parent))
+			if (mask != p->item->object.flags)
 				return 1;
 			p = p->next;
 		}
@@ -82,6 +51,19 @@ static int interesting(struct revision *rev)
 	return 1;
 }
 
+void process_commit(unsigned char *sha1)
+{
+	struct commit_list *parents;
+	struct commit *obj = lookup_commit(sha1);
+	parse_commit(obj);
+	
+	parents = obj->parents;
+	while (parents) {
+		process_commit(parents->item->object.sha1);
+		parents = parents->next;
+	}
+}
+
 /*
  * Usage: rev-tree [--edges] [--cache <cache-file>] <commit-id> [<commit-id2>]
  *
@@ -119,7 +101,7 @@ int main(int argc, char **argv)
 		}
 		if (nr >= MAX_COMMITS || get_sha1_hex(arg, sha1[nr]))
 			usage("rev-tree [--edges] [--cache <cache-file>] <commit-id> [<commit-id>]");
-		parse_commit(sha1[nr]);
+		process_commit(sha1[nr]);
 		nr++;
 	}
 
@@ -127,22 +109,30 @@ int main(int argc, char **argv)
 	 * Now we have the maximal tree. Walk the different sha files back to the root.
 	 */
 	for (i = 0; i < nr; i++)
-		mark_reachable(lookup_rev(sha1[i], "commit"), 1 << i);
+		mark_reachable(&lookup_commit(sha1[i])->object, 1 << i);
 
 	/*
 	 * Now print out the results..
 	 */
-	for (i = 0; i < nr_revs; i++) {
-		struct revision *rev = revs[i];
-		struct parent *p;
+	for (i = 0; i < nr_objs; i++) {
+		struct object *obj = objs[i];
+		struct commit *commit;
+		struct commit_list *p;
+
+		if (obj->type != commit_type)
+			continue;
+
+		commit = (struct commit *) obj;
 
-		if (!interesting(rev))
+		if (!interesting(commit))
 			continue;
 
-		printf("%lu %s:%d", rev->date, sha1_to_hex(rev->sha1), marked(rev));
-		p = rev->parent;
+		printf("%lu %s:%d", commit->date, sha1_to_hex(obj->sha1), 
+		       obj->flags);
+		p = commit->parents;
 		while (p) {
-			printf(" %s:%d", sha1_to_hex(p->parent->sha1), marked(p->parent));
+			printf(" %s:%d", sha1_to_hex(p->item->object.sha1), 
+			       p->item->object.flags);
 			p = p->next;
 		}
 		printf("\n");
diff --git a/tree.c b/tree.c
new file mode 100644
index 0000000000..1aee098117
--- /dev/null
+++ b/tree.c
@@ -0,0 +1,67 @@
+#include "tree.h"
+#include "blob.h"
+#include "cache.h"
+#include <stdlib.h>
+
+const char *tree_type = "tree";
+
+struct tree *lookup_tree(unsigned char *sha1)
+{
+	struct object *obj = lookup_object(sha1);
+	if (!obj) {
+		struct tree *ret = malloc(sizeof(struct tree));
+		memset(ret, 0, sizeof(struct tree));
+		created_object(sha1, &ret->object);
+		return ret;
+	}
+	if (obj->parsed && obj->type != tree_type) {
+		error("Object %s is a %s, not a tree", 
+		      sha1_to_hex(sha1), obj->type);
+		return NULL;
+	}
+	return (struct tree *) obj;
+}
+
+int parse_tree(struct tree *item)
+{
+	char type[20];
+	void *buffer, *bufptr;
+	unsigned long size;
+	if (item->object.parsed)
+		return 0;
+	item->object.parsed = 1;
+	item->object.type = tree_type;
+	buffer = bufptr = read_sha1_file(item->object.sha1, type, &size);
+	if (!buffer)
+		return error("Could not read %s",
+			     sha1_to_hex(item->object.sha1));
+	if (strcmp(type, tree_type))
+		return error("Object %s not a tree",
+			     sha1_to_hex(item->object.sha1));
+	while (size) {
+		struct object *obj;
+		int len = 1+strlen(bufptr);
+		unsigned char *file_sha1 = bufptr + len;
+		char *path = strchr(bufptr, ' ');
+		unsigned int mode;
+		if (size < len + 20 || !path || 
+		    sscanf(bufptr, "%o", &mode) != 1)
+			return -1;
+
+		/* Warn about trees that don't do the recursive thing.. */
+		if (strchr(path, '/')) {
+			item->has_full_path = 1;
+		}
+
+		bufptr += len + 20;
+		size -= len + 20;
+
+		if (S_ISDIR(mode)) {
+			obj = &lookup_tree(file_sha1)->object;
+		} else {
+			obj = &lookup_blob(file_sha1)->object;
+		}
+		add_ref(&item->object, obj);
+	}
+	return 0;
+}
diff --git a/tree.h b/tree.h
new file mode 100644
index 0000000000..4d5496de30
--- /dev/null
+++ b/tree.h
@@ -0,0 +1,17 @@
+#ifndef TREE_H
+#define TREE_H
+
+#include "object.h"
+
+extern const char *tree_type;
+
+struct tree {
+	struct object object;
+	unsigned has_full_path : 1;
+};
+
+struct tree *lookup_tree(unsigned char *sha1);
+
+int parse_tree(struct tree *tree);
+
+#endif /* TREE_H */