[RFC] General object parsing

[RFC] General object parsing

[Daniel Barkalow]

After the fiasco with confusing struct revision for a struct commit, I've
worked out something that makes more sense. I've actually ported
fsck-cache, rev-tree, and my merge-base to it, so it should at least be
comprehensive.

The design is as follows:

There is a struct object for each object in the database, although they
are only created on demand. It contains the type and sha1 of the
object, as well as a flag for whether the object contents have been read,
more flags for general use, a list of objects which it references, and a
flag for whether any objects reference it.

Each struct object is embedded in a type-specific struct, which contains
further information. For example, struct commit has the date, the parents,
and the tree.

Parsing objects is progressive; objects are created in an unread state
(with no disk access), and functions can be called to parse each object as
it is determined to be interesting. This should generally allow for only
the necessary portions of a large set of object references to be read.

Any comment on the design, or should I send my implementation?

	-Daniel
*This .sig left intentionally blank*

Re: [RFC] General object parsing

[Linus Torvalds]

On Sun, 17 Apr 2005, Daniel Barkalow wrote:
> 
> Any comment on the design, or should I send my implementation?

Show the patches, and maybe I (and others) can make comments on the 
thing.. It doesn't sound broken by design, the only question is how much 
harder (if any) it is to use than the rather trivial "revision.h" which 
gets us really small files.

In particular, is there some easy way to walk backwards by time? "git log"  
definitely needs that, and merge-base clearly wants something similar. I
also pretty much guarantee that visualization tools want that - creating a
visual representation of the dag by time.

If you need to read the whole thing to get that representation, then 
trying to be clever isn't even worth it - it's such a common thing that I 
bet rev-tree + caches is actually way superior.

But if there are simple helper functions to get the "next backwards in 
time" case (by looking at the parent dates in a merge), then that should 
be ok to do incrementally.

			Linus

Re: [RFC] General object parsing

[Daniel Barkalow]

On Sun, 17 Apr 2005, Linus Torvalds wrote:

> On Sun, 17 Apr 2005, Daniel Barkalow wrote:
> > 
> > Any comment on the design, or should I send my implementation?
> 
> Show the patches, and maybe I (and others) can make comments on the 
> thing.. It doesn't sound broken by design, the only question is how much 
> harder (if any) it is to use than the rather trivial "revision.h" which 
> gets us really small files.

I don't think it's much different in difficulty, plus it handles more
(parsing the objects more completely). They'll follow.

> In particular, is there some easy way to walk backwards by time? "git log"  
> definitely needs that, and merge-base clearly wants something similar. I
> also pretty much guarantee that visualization tools want that - creating a
> visual representation of the dag by time.

I think that should be easy, although I haven't written code to do it. If
you output the whole history, sorted by date, you obviously need to get 
the whole history, but I expect people will have some sort of pruning to
keep it down to a size they care about.

> But if there are simple helper functions to get the "next backwards in 
> time" case (by looking at the parent dates in a merge), then that should 
> be ok to do incrementally.

Haven't written that yet, but I can do so.

	-Daniel
*This .sig left intentionally blank*

[0/5] Parsers for git objects, porting some programs

[Daniel Barkalow]

This series introduces common parsers for objects, and ports the programs
that currently use revision.h to them.

 1: the header files
 2: the implementations
 3: port rev-tree
 4: port fsck-cache
 5: port merge-base

	-Daniel
*This .sig left intentionally blank*

[1/5] Header files for object parsing

[Daniel Barkalow]

This adds the structs and function declarations for parsing git objects.

Signed-Off-By: Daniel Barkalow <barkalow@iabervon.org>
Index: blob.h
===================================================================
--- /dev/null  (tree:5ca133e1b74aee39b2124c0ec9fd51539babb5e0)
+++ 1172a9b8f45b2fd640985595cc5258db3b027828/blob.h  (mode:100644 sha1:9a23db3a7deca67981b67ceb768411e31f723715)
@@ -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 */
Index: commit.h
===================================================================
--- /dev/null  (tree:5ca133e1b74aee39b2124c0ec9fd51539babb5e0)
+++ 1172a9b8f45b2fd640985595cc5258db3b027828/commit.h  (mode:100644 sha1:8cd20b046875f5f7e534b0607fdd97f330f53272)
@@ -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 */
Index: object.h
===================================================================
--- /dev/null  (tree:5ca133e1b74aee39b2124c0ec9fd51539babb5e0)
+++ 1172a9b8f45b2fd640985595cc5258db3b027828/object.h  (mode:100644 sha1:20f879e0867b8d6a052c458d9230fbc7786d2864)
@@ -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 */
Index: tree.h
===================================================================
--- /dev/null  (tree:5ca133e1b74aee39b2124c0ec9fd51539babb5e0)
+++ 1172a9b8f45b2fd640985595cc5258db3b027828/tree.h  (mode:100644 sha1:14ebbacded09d5e058c7f94652dcb9e12bc31cae)
@@ -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 */

[2/5] Implementations of parsing functions

[Daniel Barkalow]

This implements the parsing functions.

Signed-Off-By: Daniel Barkalow <barkalow@iabervon.org>
Index: blob.c
===================================================================
--- /dev/null  (tree:5ca133e1b74aee39b2124c0ec9fd51539babb5e0)
+++ 1172a9b8f45b2fd640985595cc5258db3b027828/blob.c  (mode:100644 sha1:04e0c1da9b1f4cdb1d1c5881b785babd3b0ceb09)
@@ -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));
+		bzero(ret, 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;
+}
Index: commit.c
===================================================================
--- /dev/null  (tree:5ca133e1b74aee39b2124c0ec9fd51539babb5e0)
+++ 1172a9b8f45b2fd640985595cc5258db3b027828/commit.c  (mode:100644 sha1:0099baa63971d86ee30ef2a7da25057f0f45a964)
@@ -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));
+		bzero(ret, 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);
+	}
+}
Index: object.c
===================================================================
--- /dev/null  (tree:5ca133e1b74aee39b2124c0ec9fd51539babb5e0)
+++ 1172a9b8f45b2fd640985595cc5258db3b027828/object.c  (mode:100644 sha1:986624ac7a7fd9229e05e1f181fd500640298d9e)
@@ -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;
+	}
+}
Index: tree.c
===================================================================
--- /dev/null  (tree:5ca133e1b74aee39b2124c0ec9fd51539babb5e0)
+++ 1172a9b8f45b2fd640985595cc5258db3b027828/tree.c  (mode:100644 sha1:7c5e5e46f4967b0812b06c0114946c3a6432c8d8)
@@ -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));
+		bzero(ret, 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;
+}

[3/5] Port rev-tree to parsing functions

[Daniel Barkalow]

This ports rev-tree to use the parsing functions introduced in the
previous patches.

Signed-Off-By: Daniel Barkalow <barkalow@iabervon.org>
Index: Makefile
===================================================================
--- 5ca133e1b74aee39b2124c0ec9fd51539babb5e0/Makefile  (mode:100644 sha1:773166a462f88b1c69930ce36d336d3d7badc319)
+++ 1172a9b8f45b2fd640985595cc5258db3b027828/Makefile  (mode:100644 sha1:c8908268d3c2253d3905671de5cabe4c84674128)
@@ -52,8 +52,8 @@
 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)
Index: rev-tree.c
===================================================================
--- 5ca133e1b74aee39b2124c0ec9fd51539babb5e0/rev-tree.c  (mode:100644 sha1:2d331b04c8243baab9546611ced07ba3439ab8ae)
+++ 1172a9b8f45b2fd640985595cc5258db3b027828/rev-tree.c  (mode:100644 sha1:38e992ac027c733f38b18932caa4032849936d05)
@@ -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 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);
-		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);
-		}
-	}
-	fclose(file);
+	die("no revtree cache file yet");
 }
 
 /*
@@ -61,16 +30,16 @@
  * 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,18 @@
 	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 +100,7 @@
 		}
 		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 +108,30 @@
 	 * 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]), 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");

[4/5] Port fsck-cache to use parsing functions

[Daniel Barkalow]

This ports fsck-cache to use parsing functions. Note that performance
could be improved here by only reading each object once, but this requires
somewhat more complicated flow control.

Signed-Off-By: Daniel Barkalow <barkalow@iabervon.org>
Index: Makefile
===================================================================
--- 499f6cf77edad6935da0106cca4472e50fdbde34/Makefile  (mode:100644 sha1:f00a9c3c1cdbfef7e96cfa98256aad35e63131e7)
+++ 1172a9b8f45b2fd640985595cc5258db3b027828/Makefile  (mode:100644 sha1:c8908268d3c2253d3905671de5cabe4c84674128)
@@ -43,8 +43,8 @@
 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)
Index: fsck-cache.c
===================================================================
--- 499f6cf77edad6935da0106cca4472e50fdbde34/fsck-cache.c  (mode:100644 sha1:cff04ce34e9445cd57db9c1026040d56f045e5e7)
+++ 1172a9b8f45b2fd640985595cc5258db3b027828/fsck-cache.c  (mode:100644 sha1:2000f16efc84911a51a40664fef8a637c90e2dcc)
@@ -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 @@
 	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\n", 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\n", sha1_to_hex(rev->sha1));
-			break;
-		case USED:
-			printf("missing %s\n", sha1_to_hex(rev->sha1));
-			break;
-		case SEEN:
-			printf("dangling %s\n", 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 * tag, unsigned char *child)
-{
-	struct revision * child_rev = add_relationship(lookup_rev(parent), child);
-	child_rev->flags |= USED;
-}
-
-static int mark_sha1_seen(unsigned char *sha1, char *tag)
-{
-	struct revision *rev = lookup_rev(sha1);
-
-	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, S_ISDIR(mode) ? "tree" : "blob", file_sha1);
+	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, "tree", tree_sha1);
-	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);
-		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 @@
 			return -1;
 	} else
 		return -1;
-	return mark_sha1_seen(sha1, tag);
+	return 0;
 }
 
 static int fsck_name(char *hex)
@@ -125,7 +87,8 @@
 			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,10 @@
 			continue;
 		}
 		if (!get_sha1_hex(argv[i], head_sha1)) {
-			mark_reachable(lookup_rev(head_sha1), REACHABLE);
+			struct object *obj =
+				&lookup_commit(head_sha1)->object;
+			obj->used = 1;
+			mark_reachable(obj, REACHABLE);
 			heads++;
 			continue;
 		}

[5/5] Switch implementations of merge-base, port to parsing

[Daniel Barkalow]

This switches to my implementation of merge-base, but with the new parsing
library.

Signed-Off-By: Daniel Barkalow <barkalow@iabervon.org>
Index: Makefile
===================================================================
--- 108bfb69c14c55c3c6e30a298307390c82cf1b3b/Makefile  (mode:100644 sha1:affc0e96030d4514f8306ee29020ca6bb320648f)
+++ 1172a9b8f45b2fd640985595cc5258db3b027828/Makefile  (mode:100644 sha1:c8908268d3c2253d3905671de5cabe4c84674128)
@@ -64,8 +64,8 @@
 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)
 
 read-cache.o: cache.h
 show-diff.o: cache.h
Index: merge-base.c
===================================================================
--- 108bfb69c14c55c3c6e30a298307390c82cf1b3b/merge-base.c  (mode:100644 sha1:c98cad0befcf7e04fcc329d9bb7cb550506a4574)
+++ 1172a9b8f45b2fd640985595cc5258db3b027828/merge-base.c  (mode:100644 sha1:414ff419c679dba122b2f21b698c1e2c8abdd965)
@@ -1,57 +1,95 @@
+#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.
-	 */
-	parse_commit(rev1);
-	parse_commit(rev2);
-
-	common = common_parent(lookup_rev(rev1), lookup_rev(rev2));
-	if (!common)
-		die("no common parent found");
-	printf("%s\n", sha1_to_hex(common->sha1));
-	return 0;
+	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) {
+		printf("%s\n", sha1_to_hex(ret->object.sha1));
+		return 0;
+	} else {
+		return 1;
+	}
+	
 }

Re: [RFC] General object parsing

[Daniel Barkalow]

On Sun, 17 Apr 2005, Daniel Barkalow wrote:

> > But if there are simple helper functions to get the "next backwards in 
> > time" case (by looking at the parent dates in a merge), then that should 
> > be ok to do incrementally.
> 
> Haven't written that yet, but I can do so.

Okay, I wrote this. I now have a merge-base that will find the most recent
ancestor while never looking at any parents of any commit older than the
answer. (But I'll let the previous stuff get reviewed first)

	-Daniel
*This .sig left intentionally blank*

Re: [RFC] General object parsing

[David Woodhouse]

On Sun, 2005-04-17 at 18:15 -0700, Linus Torvalds wrote:
> In particular, is there some easy way to walk backwards by time? "git log"  
> definitely needs that, and merge-base clearly wants something similar. 

Actually the ideal output of 'git log' isn't strictly chronological.
IIRC my bkexport scripts used to make a chronologically sorted list, and
I ended up changing it.

Simple example: if there are changesets which have been lurking in some
tree for months waiting for you to pull, and the only thing you did
since I ran 'git log' on your tree yesterday is pull from that tree,
then those changesets are what I want to see at the top of 'git log'
output.

In fact this probably means that the depth-first tree walking of the
original gitlog.sh is probably the right thing to do, but when we hit a
merge we want to try to make sure we process the _remote_ parent first.

Are we sorting the 'parent' links in merges so that two merges of the
same branches are guaranteed to be identical (assuming identical
contents otherwise)? Or is it just that we didn't think about it, and so
merges are putting the local and remote parents in the 'wrong' order by
coincidence?

-- 
dwmw2

Re: [0/5] Parsers for git objects, porting some programs

[Linus Torvalds]

On Sun, 17 Apr 2005, Daniel Barkalow wrote:
>
> This series introduces common parsers for objects, and ports the programs
> that currently use revision.h to them.
> 
>  1: the header files
>  2: the implementations
>  3: port rev-tree
>  4: port fsck-cache
>  5: port merge-base

Ok, having now looked at the code, I don't have any objections at all. 
Could you clarify the "fsck" issue about reading the same object twice? 
When does that happen?

		Linus

Re: [0/5] Parsers for git objects, porting some programs

[Daniel Barkalow]

On Mon, 18 Apr 2005, Linus Torvalds wrote:

> On Sun, 17 Apr 2005, Daniel Barkalow wrote:
> >
> > This series introduces common parsers for objects, and ports the programs
> > that currently use revision.h to them.
> > 
> >  1: the header files
> >  2: the implementations
> >  3: port rev-tree
> >  4: port fsck-cache
> >  5: port merge-base
> 
> Ok, having now looked at the code, I don't have any objections at all. 
> Could you clarify the "fsck" issue about reading the same object twice? 
> When does that happen?

Currently, the fsck-cache code is unpacking the objects to find out what
type they are, and the old code would pass the unpacked objects to the
parsing code. The new code doesn't take the unpacked objects, so it
unpacks them again. (I.e., fsck-cache will look at each object exactly
twice). The right solution is to have the internals reorganized slightly
such that a "parse_object" method, which does what fsck-cache wants (i.e.,
parse this object regardless of what type it is, and tell me the type),
could be fit in efficiently. But it doesn't affect the header file
interface, and it's only relevant to fsck-cache, which wants to look at
random junk that it doesn't have a reference to.

	-Daniel
*This .sig left intentionally blank*

Re: [0/5] Parsers for git objects, porting some programs

[Junio C Hamano]

>>>>> "DB" == Daniel Barkalow <barkalow@iabervon.org> writes:

DB> On Mon, 18 Apr 2005, Linus Torvalds wrote:
>> On Sun, 17 Apr 2005, Daniel Barkalow wrote:
>> >
>> > This series introduces common parsers for objects, and ports the programs
>> > that currently use revision.h to them.
>> > 
>> >  1: the header files
>> >  2: the implementations
>> >  3: port rev-tree
>> >  4: port fsck-cache
>> >  5: port merge-base
>> 
>> Ok, having now looked at the code, I don't have any objections at all. 

I was looking at the tree part and am thinking that it would
make it much nicer if your tree object records path for each
entry.  Currently it just borrows from object.refs to represent
its children, which is good enough for the applications listed
above (none of them would care where in the tree the object
belongs to), but I was thinking about an incremental dumper I
talked about in another thread and noticed that I cannot use the
current struct tree as is to compare two trees to find related
sha1 files (then I would inflate both, run diff and record the
output as a recipe to create one sha1 object from the other).

Or am I misreading the code that parses tree objects?

Re: [0/5] Parsers for git objects, porting some programs

[Daniel Barkalow]

On Mon, 18 Apr 2005, Junio C Hamano wrote:

> I was looking at the tree part and am thinking that it would
> make it much nicer if your tree object records path for each
> entry. 

You're entirely right, and I've actually now written the code that does
it. I'm planning to send out a patch for that shortly.

> Currently it just borrows from object.refs to represent
> its children

Note that object.refs needs to get filled out for those
applications, even if the information is also included in the
parse; object.refs is for finding what you can reach without worrying
about how you do it.

	-Daniel
*This .sig left intentionally blank*

Re: [0/5] Parsers for git objects, porting some programs

[Daniel Barkalow]

On Mon, 18 Apr 2005, Junio C Hamano wrote:

> >>>>> "DB" == Daniel Barkalow <barkalow@iabervon.org> writes:
> 
> DB> On Mon, 18 Apr 2005, Linus Torvalds wrote:
> >> On Sun, 17 Apr 2005, Daniel Barkalow wrote:
> >> >
> >> > This series introduces common parsers for objects, and ports the programs
> >> > that currently use revision.h to them.
> >> > 
> >> >  1: the header files
> >> >  2: the implementations
> >> >  3: port rev-tree
> >> >  4: port fsck-cache
> >> >  5: port merge-base
> >> 
> >> Ok, having now looked at the code, I don't have any objections at all. 
> 
> I was looking at the tree part and am thinking that it would
> make it much nicer if your tree object records path for each
> entry.

As it turns out, the code I just doesn't actually record the path; it does
everything else, and it should be easy to add the path to those entries. I
mainly wanted object type (i.e., do I have to recurse into the object), so
I skipped that one. But it should now be clear what you need to add.

	-Daniel
*This .sig left intentionally blank*