More patches

More patches

[Daniel Barkalow]

Here are the things I was saving for after the previous set:

 1: Report the actual contents of trees
 2: Add functions for scanning history by date
 3: Add http-pull, a program to fetch the objects you need by HTTP
 4: Change merge-base to find the most recent common ancestor

1 and 2 are core extensions. 3 might be best for the pasky tree. 4 is
mostly a demo of 2 and because Linus thought it was a better algorithm.

	-Daniel
*This .sig left intentionally blank*

[1/4] Report info from trees

[Daniel Barkalow]

This patch adds actual information to struct tree, making it possible to
tell what sorts of things the referenced objects are. This is needed for
http-pull, and Junio wanted something of the sort.

Signed-Off-By: Daniel Barkalow <barkalow@iabervon.org>
Index: tree.c
===================================================================
--- 1172a9b8f45b2fd640985595cc5258db3b027828/tree.c  (mode:100644 sha1:7c5e5e46f4967b0812b06c0114946c3a6432c8d8)
+++ 7e5a0d93117ecadfb15de3a6bebdb1aa94234fde/tree.c  (mode:100644 sha1:39f9cbd1908e9046c148339f816025c9313ec142)
@@ -27,6 +27,7 @@
 	char type[20];
 	void *buffer, *bufptr;
 	unsigned long size;
+	struct tree_entry_list **list_p;
 	if (item->object.parsed)
 		return 0;
 	item->object.parsed = 1;
@@ -38,8 +39,10 @@
 	if (strcmp(type, tree_type))
 		return error("Object %s not a tree",
 			     sha1_to_hex(item->object.sha1));
+	list_p = &item->entries;
 	while (size) {
 		struct object *obj;
+		struct tree_entry_list *entry;
 		int len = 1+strlen(bufptr);
 		unsigned char *file_sha1 = bufptr + len;
 		char *path = strchr(bufptr, ' ');
@@ -48,6 +51,11 @@
 		    sscanf(bufptr, "%o", &mode) != 1)
 			return -1;
 
+		entry = malloc(sizeof(struct tree_entry_list));
+		entry->directory = S_ISDIR(mode);
+		entry->executable = mode & S_IXUSR;
+		entry->next = NULL;
+
 		/* Warn about trees that don't do the recursive thing.. */
 		if (strchr(path, '/')) {
 			item->has_full_path = 1;
@@ -56,12 +64,17 @@
 		bufptr += len + 20;
 		size -= len + 20;
 
-		if (S_ISDIR(mode)) {
-			obj = &lookup_tree(file_sha1)->object;
+		if (entry->directory) {
+			entry->item.tree = lookup_tree(file_sha1);
+			obj = &entry->item.tree->object;
 		} else {
-			obj = &lookup_blob(file_sha1)->object;
+			entry->item.blob = lookup_blob(file_sha1);
+			obj = &entry->item.blob->object;
 		}
 		add_ref(&item->object, obj);
+
+		*list_p = entry;
+		list_p = &entry->next;
 	}
 	return 0;
 }
Index: tree.h
===================================================================
--- 1172a9b8f45b2fd640985595cc5258db3b027828/tree.h  (mode:100644 sha1:14ebbacded09d5e058c7f94652dcb9e12bc31cae)
+++ 7e5a0d93117ecadfb15de3a6bebdb1aa94234fde/tree.h  (mode:100644 sha1:985500e2a9130fe8c33134ca121838af9320c465)
@@ -5,9 +5,20 @@
 
 extern const char *tree_type;
 
+struct tree_entry_list {
+	struct tree_entry_list *next;
+	unsigned directory : 1;
+	unsigned executable : 1;
+	union {
+		struct tree *tree;
+		struct blob *blob;
+	} item;
+};
+
 struct tree {
 	struct object object;
 	unsigned has_full_path : 1;
+	struct tree_entry_list *entries;
 };
 
 struct tree *lookup_tree(unsigned char *sha1);

Re: [1/4] Report info from trees

[Junio C Hamano]

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

DB> This patch adds actual information to struct tree, making it possible to
DB> tell what sorts of things the referenced objects are. This is needed for
DB> http-pull, and Junio wanted something of the sort.

Thanks for keeping me in the loop, but...

DB> --- 1172a9b8f45b2fd640985595cc5258db3b027828/tree.h  (mode:100644 sha1:14ebbacded09d5e058c7f94652dcb9e12bc31cae)
DB> +++ 7e5a0d93117ecadfb15de3a6bebdb1aa94234fde/tree.h  (mode:100644 sha1:985500e2a9130fe8c33134ca121838af9320c465)
DB> @@ -5,9 +5,20 @@
 
DB>  extern const char *tree_type;
 
DB> +struct tree_entry_list {
DB> +	struct tree_entry_list *next;
DB> +	unsigned directory : 1;
DB> +	unsigned executable : 1;
DB> +	union {
DB> +		struct tree *tree;
DB> +		struct blob *blob;
DB> +	} item;
DB> +};
DB> +
DB>  struct tree {
DB>  	struct object object;
DB>  	unsigned has_full_path : 1;
DB> +	struct tree_entry_list *entries;
DB>  };
 
... what about names?  When somebody other than connectivity
checker walks a tree, it would be more likely than not that 
it wants to know what each entry is called, wound't it?

I can get the type of the object, either tree or blob, from
tree->object.type, so I do not think the single-bit are needed.

Instead, how about something simpler like this?

    struct tree {
        struct object object; /* the tree node itself as an object */
        unsigned child_nr;
        unsigned child_alloc;
        struct {
            struct object *object;
            char *name;
        } **child;
    };

The tree->child[n].object would point at the same object as one
of the object_list elements in tree->object.refs chain (i.e. you
do not need to read the same object twice).  Before the tree is
parsed, tree->child would be NULL.  You do not need child_alloc
if the intended use of this API is only parsing existing object
tree.  Otherwise keep that and realloc tree->child as needed.

Re: [1/4] Report info from trees

[Daniel Barkalow]

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

> ... what about names?  When somebody other than connectivity
> checker walks a tree, it would be more likely than not that 
> it wants to know what each entry is called, wound't it?

Yes; just add the name to the tree_entry_list.

> I can get the type of the object, either tree or blob, from
> tree->object.type, so I do not think the single-bit are needed.

You still need the mode bit (executable or not); also, the current code
can't create an object without being told in advance what it is, so you
need to use the directory bit.

> Instead, how about something simpler like this?
> 
>     struct tree {
>         struct object object; /* the tree node itself as an object */
>         unsigned child_nr;
>         unsigned child_alloc;
>         struct {
>             struct object *object;
>             char *name;
>         } **child;
>     };

I think the linked list is easier to deal with, and matches the other code
better.

> The tree->child[n].object would point at the same object as one
> of the object_list elements in tree->object.refs chain (i.e. you
> do not need to read the same object twice). 

The object code handles causing lookup_* to return the same object every
time, so this isn't an issue. Note that each struct object has to be
embedded in a struct <type> of the appropriate type, which means that we
can only create a struct object by either knowing what type it is supposed
to be or actually reading the file to find out what it actually is.

	-Daniel
*This .sig left intentionally blank*

[2/4] Sorting commits by date

[Daniel Barkalow]

Functions for a date-ordered queue of commits, progressively pulled out of
the history incrementally. Linus wanted this for finding the most recent
common ancestor, and it might be relevant to logging.

Signed-Off-By: Daniel Barkalow <barkalow@iabervon.org>
Index: commit.c
===================================================================
--- b3cf8daf9b619ae9f06a28f42a4ae01b69729206/commit.c  (mode:100644 sha1:0099baa63971d86ee30ef2a7da25057f0f45a964)
+++ 7e5a0d93117ecadfb15de3a6bebdb1aa94234fde/commit.c  (mode:100644 sha1:ef9af397471817837e1799d72f6707e0ccc949b9)
@@ -83,3 +83,47 @@
 		free(temp);
 	}
 }
+
+static void insert_by_date(struct commit_list **list, struct commit *item)
+{
+	struct commit_list **pp = list;
+	struct commit_list *p;
+	while ((p = *pp) != NULL) {
+		if (p->item->date < item->date) {
+			break;
+		}
+		pp = &p->next;
+	}
+	struct commit_list *insert = malloc(sizeof(struct commit_list));
+	insert->next = *pp;
+	*pp = insert;
+	insert->item = item;
+}
+
+	
+void sort_by_date(struct commit_list **list)
+{
+	struct commit_list *ret = NULL;
+	while (*list) {
+		insert_by_date(&ret, (*list)->item);
+		*list = (*list)->next;
+	}
+	*list = ret;
+}
+
+struct commit *pop_most_recent_commit(struct commit_list **list)
+{
+	struct commit *ret = (*list)->item;
+	struct commit_list *parents = ret->parents;
+	struct commit_list *old = *list;
+
+	*list = (*list)->next;
+	free(old);
+
+	while (parents) {
+		parse_commit(parents->item);
+		insert_by_date(list, parents->item);
+		parents = parents->next;
+	}
+	return ret;
+}
Index: commit.h
===================================================================
--- b3cf8daf9b619ae9f06a28f42a4ae01b69729206/commit.h  (mode:100644 sha1:8cd20b046875f5f7e534b0607fdd97f330f53272)
+++ 7e5a0d93117ecadfb15de3a6bebdb1aa94234fde/commit.h  (mode:100644 sha1:35679482132ae5a6b7d72bbb684f21472470717c)
@@ -24,4 +24,8 @@
 
 void free_commit_list(struct commit_list *list);
 
+void sort_by_date(struct commit_list **list);
+
+struct commit *pop_most_recent_commit(struct commit_list **list);
+
 #endif /* COMMIT_H */

Re: [2/4] Sorting commits by date

[Petr Baudis]

Dear diary, on Tue, Apr 19, 2005 at 03:54:56AM CEST, I got a letter
where Daniel Barkalow <barkalow@iabervon.org> told me that...
> Index: commit.c
> ===================================================================
> --- b3cf8daf9b619ae9f06a28f42a4ae01b69729206/commit.c  (mode:100644 sha1:0099baa63971d86ee30ef2a7da25057f0f45a964)
> +++ 7e5a0d93117ecadfb15de3a6bebdb1aa94234fde/commit.c  (mode:100644 sha1:ef9af397471817837e1799d72f6707e0ccc949b9)
> @@ -83,3 +83,47 @@
>  		free(temp);
>  	}
>  }
> +
> +static void insert_by_date(struct commit_list **list, struct commit *item)
> +{
> +	struct commit_list **pp = list;
> +	struct commit_list *p;
> +	while ((p = *pp) != NULL) {
> +		if (p->item->date < item->date) {
> +			break;
> +		}
> +		pp = &p->next;
> +	}
> +	struct commit_list *insert = malloc(sizeof(struct commit_list));
> +	insert->next = *pp;
> +	*pp = insert;
> +	insert->item = item;
> +}

Note that you are breaking gcc-2.95 compatibility when using declarator
in the middle of a block. Not that it might be a necessarily bad thing
;-) (although I still use gcc-2.95 a lot), just to ring a bell so that
it doesn't slip through unnoticed and we can decide on a policy
regarding this.

-- 
				Petr "Pasky" Baudis
Stuff: http://pasky.or.cz/
C++: an octopus made by nailing extra legs onto a dog. -- Steve Taylor

Re: [2/4] Sorting commits by date

[David A. Wheeler]

Petr Baudis wrote:
> [Re: Daniel Barkalow <barkalow@iabervon.org>'s patch] 
> Note that you are breaking gcc-2.95 compatibility when using declarator
> in the middle of a block. Not that it might be a necessarily bad thing
> ;-) (although I still use gcc-2.95 a lot), just to ring a bell so that
> it doesn't slip through unnoticed and we can decide on a policy
> regarding this.

I, at least, would REALLY like to see _highly_ portable C code;
I'm looking at git as a potential long-term useful SCM tool for
LOTS of projects, and if you're going to write C, it'd be nice
to just write it portably to start with. There's certainly
no crisis in using separate declarators.

In fact, in the LONG term I'd like to see the shell code
replaced with code that easily runs "everywhere" (Windows, etc.),
again, for portability's sake.  I think that would be unwise to
do that right now; the shell is an excellent prototyping tool.
But once things have settled down & there's been some experience
with the tools, the pieces could be slowly recoded.
(Yes, I know of & use Cygwin. And I prefer Python over Perl,
but I'm really uninterested in language wars.)

--- David A. Wheeler

Re: [2/4] Sorting commits by date

[Daniel Barkalow]

On Mon, 18 Apr 2005, David A. Wheeler wrote:

> Petr Baudis wrote:
> > [Re: Daniel Barkalow <barkalow@iabervon.org>'s patch] 
> > Note that you are breaking gcc-2.95 compatibility when using declarator
> > in the middle of a block. Not that it might be a necessarily bad thing
> > ;-) (although I still use gcc-2.95 a lot), just to ring a bell so that
> > it doesn't slip through unnoticed and we can decide on a policy
> > regarding this.
> 
> I, at least, would REALLY like to see _highly_ portable C code;
> I'm looking at git as a potential long-term useful SCM tool for
> LOTS of projects, and if you're going to write C, it'd be nice
> to just write it portably to start with. There's certainly
> no crisis in using separate declarators.

Mixing declarations and code is the least of portability issues; it's in
the current C standard unlike a number of other things. I've personally
never found a system where -lz has deflateBound but gcc doesn't support
C99, although they obviously exist. I have no problem with fixing things
up for old GCC, although I'm going to have a hard time finding such things
because I can't find a way to make recent GCC reject C99 features but not
old GNU extensions.

	-Daniel
*This .sig left intentionally blank*

Re: [2/4] Sorting commits by date

[Petr Baudis]

Dear diary, on Tue, Apr 19, 2005 at 04:52:26AM CEST, I got a letter
where Daniel Barkalow <barkalow@iabervon.org> told me that...
> because I can't find a way to make recent GCC reject C99 features but not
> old GNU extensions.

Do we use any?

-- 
				Petr "Pasky" Baudis
Stuff: http://pasky.or.cz/
C++: an octopus made by nailing extra legs onto a dog. -- Steve Taylor

Re: [2/4] Sorting commits by date

[Daniel Barkalow]

On Tue, 19 Apr 2005, Petr Baudis wrote:

> Dear diary, on Tue, Apr 19, 2005 at 04:52:26AM CEST, I got a letter
> where Daniel Barkalow <barkalow@iabervon.org> told me that...
> > because I can't find a way to make recent GCC reject C99 features but not
> > old GNU extensions.
> 
> Do we use any?

Quite a few: "?:", arithmetic on void pointers, C++/99-style comments in
places (if we aren't being C99), zero-size arrays. They're the usual
things that building Linux requires, so I think they are common extensions
beyond gcc.

	-Daniel
*This .sig left intentionally blank*

[3/4] Add http-pull

[Daniel Barkalow]

This adds a command to pull a commit and dependant objects from an HTTP
server.

Signed-Off-By: Daniel Barkalow <barkalow@iabervon.org>
Index: Makefile
===================================================================
--- 50afb5dd4184842d8da1da8dcb9ca6a591dfc5b0/Makefile  (mode:100644 sha1:803f1d49c436efa570d779db6d350efbceb29ddd)
+++ f7f62e0d2a822ad0937fd98a826f65ac7f938217/Makefile  (mode:100644 sha1:a3d26213c085e8b6bbc1ec352df0996e558e7c38)
@@ -15,7 +15,7 @@
 
 PROG=   update-cache show-diff init-db write-tree read-tree commit-tree \
 	cat-file fsck-cache checkout-cache diff-tree rev-tree show-files \
-	check-files ls-tree merge-base merge-cache unpack-file
+	check-files ls-tree merge-base merge-cache unpack-file http-pull
 
 all: $(PROG)
 
@@ -81,6 +81,11 @@
 unpack-file: unpack-file.o $(LIB_FILE)
 	$(CC) $(CFLAGS) -o unpack-file unpack-file.o $(LIBS)
 
+http-pull: LIBS += -lcurl
+
+http-pull: http-pull.o $(LIB_FILE)
+	$(CC) $(CFLAGS) -o http-pull http-pull.o $(LIBS)
+
 blob.o: $(LIB_H)
 cat-file.o: $(LIB_H)
 check-files.o: $(LIB_H)
@@ -105,6 +110,7 @@
 usage.o: $(LIB_H)
 unpack-file.o: $(LIB_H)
 write-tree.o: $(LIB_H)
+http-pull.o: $(LIB_H)
 
 clean:
 	rm -f *.o $(PROG) $(LIB_FILE)
Index: http-pull.c
===================================================================
--- /dev/null  (tree:50afb5dd4184842d8da1da8dcb9ca6a591dfc5b0)
+++ f7f62e0d2a822ad0937fd98a826f65ac7f938217/http-pull.c  (mode:100644 sha1:bd251f9e0748784bbd2cd5cf720f126d852fe888)
@@ -0,0 +1,170 @@
+#include <fcntl.h>
+#include <unistd.h>
+#include <string.h>
+#include <stdlib.h>
+#include "cache.h"
+#include "commit.h"
+#include <errno.h>
+#include <stdio.h>
+
+#include <curl/curl.h>
+#include <curl/easy.h>
+
+static CURL *curl;
+
+static char *base;
+
+static int tree = 0;
+static int commits = 0;
+static int all = 0;
+
+static int has(unsigned char *sha1)
+{
+	char *filename = sha1_file_name(sha1);
+	struct stat st;
+
+	if (!stat(filename, &st))
+		return 1;
+	return 0;
+}
+
+static int fetch(unsigned char *sha1)
+{
+	char *hex = sha1_to_hex(sha1);
+	char *filename = sha1_file_name(sha1);
+
+	char *url;
+	char *posn;
+	FILE *local;
+	struct stat st;
+
+	if (!stat(filename, &st)) {
+		return 0;
+	}
+
+	local = fopen(filename, "w");
+
+	if (!local)
+		return error("Couldn't open %s\n", filename);
+
+	curl_easy_setopt(curl, CURLOPT_FILE, local);
+
+	url = malloc(strlen(base) + 50);
+	strcpy(url, base);
+	posn = url + strlen(base);
+	strcpy(posn, "objects/");
+	posn += 8;
+	memcpy(posn, hex, 2);
+	posn += 2;
+	*(posn++) = '/';
+	strcpy(posn, hex + 2);
+
+	curl_easy_setopt(curl, CURLOPT_URL, url);
+
+	printf("Getting %s\n", hex);
+
+	if (curl_easy_perform(curl))
+		return error("Couldn't get %s for %s\n", url, hex);
+
+	fclose(local);
+	
+	return 0;
+}
+
+static int process_tree(unsigned char *sha1)
+{
+	struct tree *tree = lookup_tree(sha1);
+	struct tree_entry_list *entries;
+
+	if (parse_tree(tree))
+		return -1;
+
+	for (entries = tree->entries; entries; entries = entries->next) {
+		if (fetch(entries->item.tree->object.sha1))
+			return -1;
+		if (entries->directory) {
+			if (process_tree(entries->item.tree->object.sha1))
+				return -1;
+		}
+	}
+	return 0;
+}
+
+static int process_commit(unsigned char *sha1)
+{
+	struct commit *obj = lookup_commit(sha1);
+
+	if (fetch(sha1))
+		return -1;
+
+	if (parse_commit(obj))
+		return -1;
+
+	if (tree) {
+		if (fetch(obj->tree->object.sha1))
+			return -1;
+		if (process_tree(obj->tree->object.sha1))
+			return -1;
+		if (!all)
+			tree = 0;
+	}
+	if (commits) {
+		struct commit_list *parents = obj->parents;
+		for (; parents; parents = parents->next) {
+			if (has(parents->item->object.sha1))
+				continue;
+			if (fetch(parents->item->object.sha1)) {
+				/* The server might not have it, and
+				 * we don't mind. 
+				 */
+				continue;
+			}
+			if (process_commit(parents->item->object.sha1))
+				return -1;
+		}
+	}
+	return 0;
+}
+
+int main(int argc, char **argv)
+{
+	char *commit_id;
+	char *url;
+	int arg = 1;
+	unsigned char sha1[20];
+
+	while (arg < argc && argv[arg][0] == '-') {
+		if (argv[arg][1] == 't') {
+			tree = 1;
+		} else if (argv[arg][1] == 'c') {
+			commits = 1;
+		} else if (argv[arg][1] == 'a') {
+			all = 1;
+			tree = 1;
+			commits = 1;
+		}
+		arg++;
+	}
+	if (argc < arg + 2) {
+		usage("http-pull [-c] [-t] [-a] commit-id url");
+		return 1;
+	}
+	commit_id = argv[arg];
+	url = argv[arg + 1];
+
+	get_sha1_hex(commit_id, sha1);
+
+	curl_global_init(CURL_GLOBAL_ALL);
+
+	curl = curl_easy_init();
+
+	base = url;
+
+	if (fetch(sha1))
+		return 1;
+	if (process_commit(sha1))
+		return 1;
+
+	curl_global_cleanup();
+	return 0;
+}

[4/4] Make merge-base use dates to find answer

[Daniel Barkalow]

This changes merge-base to use the dates of commit to search the
history. It will find the most recent common ancestor, rather than the one
the fewest generations away. It also demonstrates scanning the history by
date.

Signed-Off-By: Daniel Barkalow <barkalow@iabervon.org>
Index: merge-base.c
===================================================================
--- fb7b671eb0da01b9a9998ab58b3717da9f983456/merge-base.c  (mode:100644 sha1:414ff419c679dba122b2f21b698c1e2c8abdd965)
+++ 7e5a0d93117ecadfb15de3a6bebdb1aa94234fde/merge-base.c  (mode:100644 sha1:61e408e5d158f3dde6153ccbe9ee6fbbf1136225)
@@ -5,42 +5,30 @@
 static struct commit *process_list(struct commit_list **list_p, int this_mark,
 				   int other_mark)
 {
-	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;
+	struct commit *item = (*list_p)->item;
+	
+	if (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.
+		 */
+		*list_p = (*list_p)->next;
+	} else if (item->object.flags & other_mark) {
+		return item;
+	} else {
+		/*
+		  printf("%d based on %s\n",
+		  this_mark,
+		  sha1_to_hex(posn->parent->sha1));
+		*/
+		pop_most_recent_commit(list_p);
+		item->object.flags |= this_mark;
 	}
 	return NULL;
 }
@@ -56,16 +44,27 @@
 	rev2list->item = rev2;
 	rev2list->next = NULL;
 
+	parse_commit(rev1);
+	parse_commit(rev2);
+
 	while (rev1list || rev2list) {
 		struct commit *ret;
-		ret = process_list(&rev1list, 0x1, 0x2);
-		if (ret) {
-			/* XXXX free lists */
-			return ret;
+		if (!rev1list) {
+			// process 2
+			ret = process_list(&rev2list, 0x2, 0x1);
+		} else if (!rev2list) {
+			// process 1
+			ret = process_list(&rev1list, 0x1, 0x2);
+		} else if (rev1list->item->date < rev2list->item->date) {
+			// process 2
+			ret = process_list(&rev2list, 0x2, 0x1);
+		} else {
+			// process 1
+			ret = process_list(&rev1list, 0x1, 0x2);
 		}
-		ret = process_list(&rev2list, 0x2, 0x1);
 		if (ret) {
-			/* XXXX free lists */
+			free_commit_list(rev1list);
+			free_commit_list(rev2list);
 			return ret;
 		}
 	}