[PATCH 0/5] Better merge-base, alternative transport programs

[PATCH 0/5] Better merge-base, alternative transport programs

[Daniel Barkalow]

This series contains three patches to add functionality to the library
routines necessary for the rest of the series, a patch to change the
merge-base implementation such that it always returns one of its arguments
when possible (by way of using the date-based algorithm), and a patch to
support fetching what is needed from a repository by HTTP, and both
pushing and pulling by ssh.

 1: Add some functions for commit lists
 2: Parse tree objects completely
 3: Add some functions related to files
 4: Replace merge-base
 5: Add push and pull programs

	-Daniel
*This .sig left intentionally blank*

[PATCH 1/5] Add some functions for commit lists

[Daniel Barkalow]

This adds a function for inserting an item in a commit list, a function
for sorting a commit list by date, and a function for progressively
scanning a commit history from most recent to least recent.

Signed-Off-By: Daniel Barkalow <barkalow@iabervon.org>
Index: commit.c
===================================================================
--- 329aca984ad6d06eb6d2dffae3933f00ccb8df5a/commit.c  (mode:100644 sha1:9f0668eb68cec56a738a58fe930ae0ae2960e2b2)
+++ e09a6d73a7c6c7a8bfb7e7003a34a507ed97a3b6/commit.c  (mode:100644 sha1:911f6435a74b93f6d25c6852d1814fa8dbaf626e)
@@ -63,12 +63,9 @@
 	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;
+		struct commit *new_parent = lookup_commit(parent);
+		commit_list_insert(new_parent, &item->parents);
+		add_ref(&item->object, &new_parent->object);
 		bufptr += 48;
 	}
 	item->date = parse_commit_date(bufptr);
@@ -76,6 +73,14 @@
 	return 0;
 }
 
+void commit_list_insert(struct commit *item, struct commit_list **list_p)
+{
+	struct commit_list *new_list = malloc(sizeof(struct commit_list));
+	new_list->item = item;
+	new_list->next = *list_p;
+	*list_p = new_list;
+}
+
 void free_commit_list(struct commit_list *list)
 {
 	while (list) {
@@ -84,3 +89,44 @@
 		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;
+	}
+	commit_list_insert(item, pp);
+}
+
+	
+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
===================================================================
--- 329aca984ad6d06eb6d2dffae3933f00ccb8df5a/commit.h  (mode:100644 sha1:4afd27b1095cf9f9203c96db2b9f2b0bba5063d8)
+++ e09a6d73a7c6c7a8bfb7e7003a34a507ed97a3b6/commit.h  (mode:100644 sha1:c8684d1cd07d7c9ed0af06a3f3d9e7b49fbed0a2)
@@ -22,6 +22,15 @@
 
 int parse_commit(struct commit *item);
 
+void commit_list_insert(struct commit *item, struct commit_list **list_p);
+
 void free_commit_list(struct commit_list *list);
 
+void sort_by_date(struct commit_list **list);
+
+/** Removes the first commit from a list sorted by date, and adds all
+ * of its parents.
+ **/
+struct commit *pop_most_recent_commit(struct commit_list **list);
+
 #endif /* COMMIT_H */

[PATCH 2/5] Parse tree objects completely

[Daniel Barkalow]

This adds the contents of trees to struct tree.

Signed-Off-By: Daniel Barkalow <barkalow@iabervon.org>
commit af03ca2bdc01fdc2565c2914285d9c3ccb1205d3
tree 144a13fb75a39538ec4578792d2c374c6ef50f46
parent fda07b139124925a8000207fb1d91feec1fe675d
author Daniel Barkalow <barkalow@iabervon.org> 1114296377 -0400
committer Daniel Barkalow <barkalow@silva-tulga.(none)> 1114296377 -0400

    Parse tree objects completely

Index: tree.c
===================================================================
--- e09a6d73a7c6c7a8bfb7e7003a34a507ed97a3b6/tree.c  (mode:100644 sha1:e988aed6a85d15568dcb93b69035b97a24e30cc9)
+++ 144a13fb75a39538ec4578792d2c374c6ef50f46/tree.c  (mode:100644 sha1:79b9625855c017ce0298f62cc398ed4d16964cb1)
@@ -92,6 +92,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;
@@ -103,8 +104,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, ' ');
@@ -113,6 +116,12 @@
 		    sscanf(bufptr, "%o", &mode) != 1)
 			return -1;
 
+		entry = malloc(sizeof(struct tree_entry_list));
+		entry->name = strdup(path + 1);
+		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;
@@ -121,12 +130,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
===================================================================
--- e09a6d73a7c6c7a8bfb7e7003a34a507ed97a3b6/tree.h  (mode:100644 sha1:4d5496de307999f5ada8412259e0e86d2c8092de)
+++ 144a13fb75a39538ec4578792d2c374c6ef50f46/tree.h  (mode:100644 sha1:19b190565957a7a03c34f7efa68a7fe0c6783d04)
@@ -5,9 +5,21 @@
 
 extern const char *tree_type;
 
+struct tree_entry_list {
+	struct tree_entry_list *next;
+	unsigned directory : 1;
+	unsigned executable : 1;
+	char *name;
+	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);

[PATCH 3/5] Additional functions for the objects database

[Daniel Barkalow]

This adds two functions: one to check if an object is present in the local
database, and one to add an object to the local database by reading it
from a file descriptor and checking its hash.

Signed-Off-By: Daniel Barkalow <barkalow@iabervon.org>
Index: cache.h
===================================================================
--- 144a13fb75a39538ec4578792d2c374c6ef50f46/cache.h  (mode:100644 sha1:bf30ac4741d2eeeb483079f566182505898082f3)
+++ cae140a16189361d8c9f1f7e68ef519956fd26d9/cache.h  (mode:100644 sha1:794d676a5cf5c9a03309c4b368840f8707cfcf46)
@@ -122,11 +122,16 @@
 extern void * unpack_sha1_file(void *map, unsigned long mapsize, char *type, unsigned long *size);
 extern void * read_sha1_file(const unsigned char *sha1, char *type, unsigned long *size);
 extern int write_sha1_file(char *buf, unsigned len, unsigned char *return_sha1);
+
 extern int check_sha1_signature(unsigned char *sha1, void *buf, unsigned long size, const char *type);
 
 /* Read a tree into the cache */
 extern int read_tree(void *buffer, unsigned long size, int stage);
 
+extern int write_sha1_from_fd(const unsigned char *sha1, int fd);
+
+extern int has_sha1_file(const unsigned char *sha1);
+
 /* Convert to/from hex/sha1 representation */
 extern int get_sha1_hex(const char *hex, unsigned char *sha1);
 extern char *sha1_to_hex(const unsigned char *sha1);	/* static buffer result! */
Index: sha1_file.c
===================================================================
--- 144a13fb75a39538ec4578792d2c374c6ef50f46/sha1_file.c  (mode:100644 sha1:66308ede85c2dad6b184fb74a7215b06a173d8f7)
+++ cae140a16189361d8c9f1f7e68ef519956fd26d9/sha1_file.c  (mode:100644 sha1:97a515a073fec5870dfaaa279868ce9330853d3d)
@@ -328,3 +328,75 @@
 	close(fd);
 	return 0;
 }
+
+int write_sha1_from_fd(const unsigned char *sha1, int fd)
+{
+	char *filename = sha1_file_name(sha1);
+
+	int local;
+	z_stream stream;
+	unsigned char real_sha1[20];
+	char buf[4096];
+	char discard[4096];
+	int ret;
+	SHA_CTX c;
+
+	local = open(filename, O_WRONLY | O_CREAT | O_EXCL, 0666);
+
+	if (local < 0)
+		return error("Couldn't open %s\n", filename);
+
+	memset(&stream, 0, sizeof(stream));
+
+	inflateInit(&stream);
+
+	SHA1_Init(&c);
+
+	do {
+		ssize_t size;
+		size = read(fd, buf, 4096);
+		if (size <= 0) {
+			close(local);
+			unlink(filename);
+			if (!size)
+				return error("Connection closed?");
+			perror("Reading from connection");
+			return -1;
+		}
+		write(local, buf, size);
+		stream.avail_in = size;
+		stream.next_in = buf;
+		do {
+			stream.next_out = discard;
+			stream.avail_out = sizeof(discard);
+			ret = inflate(&stream, Z_SYNC_FLUSH);
+			SHA1_Update(&c, discard, sizeof(discard) -
+				    stream.avail_out);
+		} while (stream.avail_in && ret == Z_OK);
+		
+	} while (ret == Z_OK);
+	inflateEnd(&stream);
+
+	close(local);
+	SHA1_Final(real_sha1, &c);
+	if (ret != Z_STREAM_END) {
+		unlink(filename);
+		return error("File %s corrupted", sha1_to_hex(sha1));
+	}
+	if (memcmp(sha1, real_sha1, 20)) {
+		unlink(filename);
+		return error("File %s has bad hash\n", sha1_to_hex(sha1));
+	}
+	
+	return 0;
+}
+
+int has_sha1_file(const unsigned char *sha1)
+{
+	char *filename = sha1_file_name(sha1);
+	struct stat st;
+
+	if (!stat(filename, &st))
+		return 1;
+	return 0;
+}

[PATCH 4/5] Replace merge-base implementation

[Daniel Barkalow]

The old implementation was a nice algorithm, but, unfortunately, it could
be confused in some cases and would not necessarily do the obvious thing
if one argument was decended from the other. This version fixes that by
changing the criterion to the most recent common ancestor.

Signed-Off-By: Daniel Barkalow <barkalow@iabervon.org>
Index: merge-base.c
===================================================================
--- cae140a16189361d8c9f1f7e68ef519956fd26d9/merge-base.c  (mode:100644 sha1:ac1153bc5646cb2d515ff206b759f4a79e90273a)
+++ 9b75904eab1300d83264a1840d396160482fee88/merge-base.c  (mode:100644 sha1:0e4c58ede915aca5719bbd12ecd1945f2f300590)
@@ -5,67 +5,63 @@
 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;
 }
 
 struct commit *common_ancestor(struct commit *rev1, struct commit *rev2)
 {
-	struct commit_list *rev1list = malloc(sizeof(struct commit_list));
-	struct commit_list *rev2list = malloc(sizeof(struct commit_list));
+	struct commit_list *rev1list = NULL;
+	struct commit_list *rev2list = NULL;
 
-	rev1list->item = rev1;
-	rev1list->next = NULL;
+	commit_list_insert(rev1, &rev1list);
+	commit_list_insert(rev2, &rev2list);
 
-	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;
 		}
 	}

[PATCH 5/5] Various transport programs

[Daniel Barkalow]

This patch adds three similar and related programs. http-pull downloads
objects from an HTTP server; rpull downloads objects by using ssh and
rpush on the other side; and rpush uploads objects by using ssh and rpull
on the other side.

The algorithm should be sufficient to make the network throughput required
depend only on how much content is new, not at all on how much content the
repository contains.

The combination should enable people to have remote repositories by way of
ssh login for authenticated users and HTTP for anonymous access.

Signed-Off-By: Daniel Barkalow <barkalow@iabervon.org>
Index: Makefile
===================================================================
--- 9b75904eab1300d83264a1840d396160482fee88/Makefile  (mode:100644 sha1:57e70239503466fb3a77f1f2618ee64377e8e04b)
+++ a56d8adaecc49ce7f26536f9f5d54ec813072e4f/Makefile  (mode:100644 sha1:b60d8eb691f4edd56d5b310b0dd670e98c852228)
@@ -16,7 +16,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 git-export \
-	diff-cache convert-cache
+	diff-cache convert-cache http-pull rpush rpull
 
 all: $(PROG)
 
@@ -51,7 +51,13 @@
 init-db: init-db.o
 
 %: %.o $(LIB_FILE)
-	$(CC) $(CFLAGS) -o $@ $< $(LIBS)
+	$(CC) $(CFLAGS) -o $@ $(filter %.o,$^) $(LIBS)
+
+rpush: rsh.o
+
+rpull: rsh.o
+
+http-pull: LIBS += -lcurl
 
 blob.o: $(LIB_H)
 cat-file.o: $(LIB_H)
@@ -80,6 +86,9 @@
 usage.o: $(LIB_H)
 unpack-file.o: $(LIB_H)
 write-tree.o: $(LIB_H)
+http-pull.o: $(LIB_H)
+rpull.o: $(LIB_H)
+rpush.o: $(LIB_H)
 
 clean:
 	rm -f *.o mozilla-sha1/*.o ppc/*.o $(PROG) $(LIB_FILE)
Index: http-pull.c
===================================================================
--- /dev/null  (tree:9b75904eab1300d83264a1840d396160482fee88)
+++ a56d8adaecc49ce7f26536f9f5d54ec813072e4f/http-pull.c  (mode:100644 sha1:a17225719c53508a37905618c624ad8c4d0372ec)
@@ -0,0 +1,204 @@
+#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 SHA_CTX c;
+static z_stream stream;
+
+static int local;
+static int zret;
+
+static size_t fwrite_sha1_file(void *ptr, size_t eltsize, size_t nmemb, 
+			       void *data) {
+	char expn[4096];
+	size_t size = eltsize * nmemb;
+	int posn = 0;
+	do {
+		ssize_t retval = write(local, ptr + posn, size - posn);
+		if (retval < 0)
+			return posn;
+		posn += retval;
+	} while (posn < size);
+
+	stream.avail_in = size;
+	stream.next_in = ptr;
+	do {
+		stream.next_out = expn;
+		stream.avail_out = sizeof(expn);
+		zret = inflate(&stream, Z_SYNC_FLUSH);
+		SHA1_Update(&c, expn, sizeof(expn) - stream.avail_out);
+	} while (stream.avail_in && zret == Z_OK);
+	return size;
+}
+
+static int fetch(unsigned char *sha1)
+{
+	char *hex = sha1_to_hex(sha1);
+	char *filename = sha1_file_name(sha1);
+	char real_sha1[20];
+	char *url;
+	char *posn;
+
+	if (has_sha1_file(sha1)) {
+		return 0;
+	}
+
+	local = open(filename, O_WRONLY | O_CREAT | O_EXCL, 0666);
+
+	if (local < 0)
+		return error("Couldn't open %s\n", filename);
+
+	memset(&stream, 0, sizeof(stream));
+
+	inflateInit(&stream);
+
+	SHA1_Init(&c);
+
+	curl_easy_setopt(curl, CURLOPT_FILE, NULL);
+	curl_easy_setopt(curl, CURLOPT_WRITEFUNCTION, fwrite_sha1_file);
+
+	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);
+
+	close(local);
+	inflateEnd(&stream);
+	SHA1_Final(real_sha1, &c);
+	if (zret != Z_STREAM_END) {
+		unlink(filename);
+		return error("File %s (%s) corrupt\n", hex, url);
+	}
+	if (memcmp(sha1, real_sha1, 20)) {
+		unlink(filename);
+		return error("File %s has bad hash\n", hex);
+	}
+	
+	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_sha1_file(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;
+}
Index: rpull.c
===================================================================
--- /dev/null  (tree:9b75904eab1300d83264a1840d396160482fee88)
+++ a56d8adaecc49ce7f26536f9f5d54ec813072e4f/rpull.c  (mode:100644 sha1:c27af2c2464de28732b8ad1fff3ed8a0804250d6)
@@ -0,0 +1,128 @@
+#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 "rsh.h"
+
+static int tree = 0;
+static int commits = 0;
+static int all = 0;
+
+static int fd_in;
+static int fd_out;
+
+static int fetch(unsigned char *sha1)
+{
+	if (has_sha1_file(sha1))
+		return 0;
+	write(fd_out, sha1, 20);
+	return write_sha1_from_fd(sha1, fd_in);
+}
+
+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) {
+		/*
+		  fprintf(stderr, "Tree %s ", sha1_to_hex(sha1));
+		  fprintf(stderr, "needs %s\n", 
+		  sha1_to_hex(entries->item.tree->object.sha1));
+		*/
+		if (fetch(entries->item.tree->object.sha1)) {
+			return error("Missing item %s",
+				     sha1_to_hex(entries->item.tree->object.sha1));
+		}
+		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 error("Fetching %s", sha1_to_hex(sha1));
+	}
+
+	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_sha1_file(parents->item->object.sha1))
+				continue;
+			if (fetch(parents->item->object.sha1)) {
+				/* The server might not have it, and
+				 * we don't mind. 
+				 */
+				error("Missing tree %s; continuing", 
+				      sha1_to_hex(parents->item->object.sha1));
+				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("rpull [-c] [-t] [-a] commit-id url");
+		return 1;
+	}
+	commit_id = argv[arg];
+	url = argv[arg + 1];
+
+	if (setup_connection(&fd_in, &fd_out, "rpush", url, arg, argv + 1))
+		return 1;
+
+	get_sha1_hex(commit_id, sha1);
+
+	if (fetch(sha1))
+		return 1;
+	if (process_commit(sha1))
+		return 1;
+
+	return 0;
+}
Index: rpush.c
===================================================================
--- /dev/null  (tree:9b75904eab1300d83264a1840d396160482fee88)
+++ a56d8adaecc49ce7f26536f9f5d54ec813072e4f/rpush.c  (mode:100644 sha1:0293a1a46311d7e20b13177143741ab9d6d0d201)
@@ -0,0 +1,69 @@
+#include "cache.h"
+#include "rsh.h"
+#include <sys/socket.h>
+#include <errno.h>
+
+void service(int fd_in, int fd_out) {
+	ssize_t size;
+	int posn;
+	char sha1[20];
+	unsigned long objsize;
+	void *buf;
+	do {
+		posn = 0;
+		do {
+			size = read(fd_in, sha1 + posn, 20 - posn);
+			if (size < 0) {
+				perror("rpush: read ");
+				return;
+			}
+			if (!size)
+				return;
+			posn += size;
+		} while (posn < 20);
+
+		/* fprintf(stderr, "Serving %s\n", sha1_to_hex(sha1)); */
+
+		buf = map_sha1_file(sha1, &objsize);
+		if (!buf) {
+			fprintf(stderr, "rpush: could not find %s\n", 
+				sha1_to_hex(sha1));
+			return;
+		}
+		posn = 0;
+		do {
+			size = write(fd_out, buf + posn, objsize - posn);
+			if (size <= 0) {
+				if (!size) {
+					fprintf(stderr, "rpush: write closed");
+				} else {
+					perror("rpush: write ");
+				}
+				return;
+			}
+			posn += size;
+		} while (posn < objsize);
+	} while (1);
+}
+
+int main(int argc, char **argv)
+{
+	int arg = 1;
+        char *commit_id;
+        char *url;
+	int fd_in, fd_out;
+	while (arg < argc && argv[arg][0] == '-') {
+                arg++;
+        }
+        if (argc < arg + 2) {
+                usage("rpush [-c] [-t] [-a] commit-id url");
+                return 1;
+        }
+	commit_id = argv[arg];
+	url = argv[arg + 1];
+	if (setup_connection(&fd_in, &fd_out, "rpull", url, arg, argv + 1))
+		return 1;
+
+	service(fd_in, fd_out);
+	return 0;
+}
Index: rsh.c
===================================================================
--- /dev/null  (tree:9b75904eab1300d83264a1840d396160482fee88)
+++ a56d8adaecc49ce7f26536f9f5d54ec813072e4f/rsh.c  (mode:100644 sha1:4d6a90bf6c1b290975fb2ac22f25979be56cb476)
@@ -0,0 +1,63 @@
+#include "rsh.h"
+
+#include <string.h>
+#include <sys/socket.h>
+
+#include "cache.h"
+
+#define COMMAND_SIZE 4096
+
+int setup_connection(int *fd_in, int *fd_out, char *remote_prog, 
+		     char *url, int rmt_argc, char **rmt_argv)
+{
+	char *host;
+	char *path;
+	int sv[2];
+	char command[COMMAND_SIZE];
+	char *posn;
+	int i;
+
+	if (!strcmp(url, "-")) {
+		*fd_in = 0;
+		*fd_out = 1;
+		return 0;
+	}
+
+	host = strstr(url, "//");
+	if (!host) {
+		return error("Bad URL: %s", url);
+	}
+	host += 2;
+	path = strchr(host, '/');
+	if (!path) {
+		return error("Bad URL: %s", url);
+	}
+	*(path++) = '\0';
+	/* ssh <host> 'cd /<path>; stdio-pull <arg...> <commit-id>' */
+	snprintf(command, COMMAND_SIZE, 
+		 "cd /%s; SHA1_FILE_DIRECTORY=objects %s",
+		 path, remote_prog);
+	posn = command + strlen(command);
+	for (i = 0; i < rmt_argc; i++) {
+		*(posn++) = ' ';
+		strncpy(posn, rmt_argv[i], COMMAND_SIZE - (posn - command));
+		posn += strlen(rmt_argv[i]);
+		if (posn - command + 4 >= COMMAND_SIZE) {
+			return error("Command line too long");
+		}
+	}
+	strcpy(posn, " -");
+	if (socketpair(AF_LOCAL, SOCK_STREAM, 0, sv)) {
+		return error("Couldn't create socket");
+	}
+	if (!fork()) {
+		close(sv[1]);
+		dup2(sv[0], 0);
+		dup2(sv[0], 1);
+		execlp("ssh", "ssh", host, command, NULL);
+	}
+	close(sv[0]);
+	*fd_in = sv[1];
+	*fd_out = sv[1];
+	return 0;
+}
Index: rsh.h
===================================================================
--- /dev/null  (tree:9b75904eab1300d83264a1840d396160482fee88)
+++ a56d8adaecc49ce7f26536f9f5d54ec813072e4f/rsh.h  (mode:100644 sha1:97e4f20b2b80662269827d77f3104025143087e7)
@@ -0,0 +1,7 @@
+#ifndef RSH_H
+#define RSH_H
+
+int setup_connection(int *fd_in, int *fd_out, char *remote_prog, 
+		     char *url, int rmt_argc, char **rmt_argv);
+
+#endif

Re: [PATCH 1/5] Add some functions for commit lists

[Linus Torvalds]

On Sat, 23 Apr 2005, Daniel Barkalow wrote:
>
> This adds a function for inserting an item in a commit list, a function
> for sorting a commit list by date, and a function for progressively
> scanning a commit history from most recent to least recent.

Ok. This is more in like with what I was hoping for, looks good.

All patches applied and pushed out, and I wrote a trivial "rev-list" thing 
that is kind of a cut-down rev-tree which just lists the commits in the 
order the "fake time order".

The "fake time order" just uses this progressive commit history scan, 
which is different from the old "sort by date" in that it still takes 
parenthood into account, and always shows the child first.

It turns out that since git is so damn fast, when I commit a mbox of 
patches, they often all get the same date, since we "only" do dates with a 
one-second granularity. So sorting by date ends up doing strange things, 
when some of the entries have no sort order.

Daniel's date-based incremental scanning solves this problem, and also 
means that we get output immediately without having to parse the whole 
tree down to the root.

So with this, git-pasky should probably do the following..

			Linus

-
Make gitlog.sh use the new simple time-based commit traversal
helpers.

Signed-off-by: Linus Torvalds <torvalds@osdl.org>

gitlog.sh: a496a864f9586e47a4d7bd3ae0af0b3e07b7deb8
--- a/gitlog.sh
+++ b/gitlog.sh
@@ -11,7 +11,7 @@
 
 base=$(gitXnormid.sh -c $1) || exit 1
 
-rev-tree $base | sort -rn | while read time commit parents; do
+rev-list $base | while read commit; do
 	echo commit ${commit%:*};
 	cat-file commit $commit | \
 		while read key rest; do

Re: [PATCH 1/5] Add some functions for commit lists

[Linus Torvalds]

On Sat, 23 Apr 2005, Linus Torvalds wrote:
> 
> Ok. This is more in like with what I was hoping for, looks good.

Oh, Daniel, I notice that you have the same old bug: it will happily add 
the same parent to the list several times. You need to prune them out, and 
ignore things you've seen.

I pushed out the fix (don't parse and add parents to the list that were 
already parsed).

		Linus

Re: [PATCH 1/5] Add some functions for commit lists

[Daniel Barkalow]

On Sat, 23 Apr 2005, Linus Torvalds wrote:

> 
> 
> On Sat, 23 Apr 2005, Linus Torvalds wrote:
> > 
> > Ok. This is more in like with what I was hoping for, looks good.
> 
> Oh, Daniel, I notice that you have the same old bug: it will happily add 
> the same parent to the list several times. You need to prune them out, and 
> ignore things you've seen.
>
> I pushed out the fix (don't parse and add parents to the list that were 
> already parsed).

This won't actually work for merge-base, which wants to run two of these,
one for each head, in parallel, and find the first commit on both lists. I
think making insert_by_date() ignore items already in the list is a better
solution, although that might run into problems if there's a complicated
graph of commits all with the same time.

Another option is to specify a object.flags bit to mark for each commit
and ignore commits that are already marked.

	-Daniel
*This .sig left intentionally blank*

[PATCH] Allow multiple date-ordered lists

[Daniel Barkalow]

Make pop_most_recent_commit() return the same objects multiple times, but only
if called with different bits to mark.

This is necessary to make merge-base work again.

Signed-Off-By: Daniel Barkalow <barkalow@iabervon.org>

---
commit 58ec99a22e3a8dac158d9949b0a704752991ac8a
tree 6f24c9b481d76e067d64bac1a8dbd5cf5d0dfb05
parent f4adf2687593e8d6e58ac1c4710e0385a82500e5
author Daniel Barkalow <barkalow@iabervon.org> 1114311416 -0400
committer Daniel Barkalow <barkalow@silva-tulga.(none)> 1114311416 -0400

Index: commit.c
===================================================================
--- 34933617a2e8284ffca6ab2a1b2f00d6996a58e7/commit.c  (mode:100644 sha1:0243e77cb8e839e2972a2882bb1d0719f6e3cff1)
+++ 6f24c9b481d76e067d64bac1a8dbd5cf5d0dfb05/commit.c  (mode:100644 sha1:2502688262819033f5b8ed60a7bef5eed0aa2d6a)
@@ -114,7 +114,8 @@
 	*list = ret;
 }
 
-struct commit *pop_most_recent_commit(struct commit_list **list)
+struct commit *pop_most_recent_commit(struct commit_list **list,
+				      unsigned int mark)
 {
 	struct commit *ret = (*list)->item;
 	struct commit_list *parents = ret->parents;
@@ -125,8 +126,9 @@
 
 	while (parents) {
 		struct commit *commit = parents->item;
-		if (!commit->object.parsed) {
-			parse_commit(commit);
+		parse_commit(commit);
+		if (!(commit->object.flags & mark)) {
+			commit->object.flags |= mark;
 			insert_by_date(list, commit);
 		}
 		parents = parents->next;
Index: commit.h
===================================================================
--- 34933617a2e8284ffca6ab2a1b2f00d6996a58e7/commit.h  (mode:100644 sha1:c8684d1cd07d7c9ed0af06a3f3d9e7b49fbed0a2)
+++ 6f24c9b481d76e067d64bac1a8dbd5cf5d0dfb05/commit.h  (mode:100644 sha1:d61d084c89c72f4fe79c654db721df31c4f04224)
@@ -31,6 +31,7 @@
 /** Removes the first commit from a list sorted by date, and adds all
  * of its parents.
  **/
-struct commit *pop_most_recent_commit(struct commit_list **list);
+struct commit *pop_most_recent_commit(struct commit_list **list, 
+				      unsigned int mark);
 
 #endif /* COMMIT_H */
Index: merge-base.c
===================================================================
--- 34933617a2e8284ffca6ab2a1b2f00d6996a58e7/merge-base.c  (mode:100644 sha1:0e4c58ede915aca5719bbd12ecd1945f2f300590)
+++ 6f24c9b481d76e067d64bac1a8dbd5cf5d0dfb05/merge-base.c  (mode:100644 sha1:2c40881302e586366f03ae6ac6e7c0035847e2f0)
@@ -6,29 +6,11 @@
 				   int other_mark)
 {
 	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) {
+
+	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;
+		pop_most_recent_commit(list_p, this_mark);
 	}
 	return NULL;
 }
@@ -39,7 +21,9 @@
 	struct commit_list *rev2list = NULL;
 
 	commit_list_insert(rev1, &rev1list);
+	rev1->object.flags |= 0x1;
 	commit_list_insert(rev2, &rev2list);
+	rev2->object.flags |= 0x2;
 
 	parse_commit(rev1);
 	parse_commit(rev2);
Index: rev-list.c
===================================================================
--- 34933617a2e8284ffca6ab2a1b2f00d6996a58e7/rev-list.c  (mode:100644 sha1:1c797d24a91b44994dc11180dd61c3ecf8f93349)
+++ 6f24c9b481d76e067d64bac1a8dbd5cf5d0dfb05/rev-list.c  (mode:100644 sha1:77bfc29db1aad08ba9d7d87ce08d33d4a88e74e3)
@@ -16,7 +16,7 @@
 
 	commit_list_insert(commit, &list);
 	do {
-		struct commit *commit = pop_most_recent_commit(&list);
+		struct commit *commit = pop_most_recent_commit(&list, 0x1);
 		printf("%s\n", sha1_to_hex(commit->object.sha1));
 	} while (list);
 	return 0;

[PATCH] Add -u option to diff-cache to show UNCHANGED files

[Andreas Gal]

With -u diff-cache shows unchanged files, instead of files that changed. 
This is useful to implement a "git clean" command that throws away all 
checked out files that have not changed (yes, I really would like to 
have that). One could also do show-files and then substract the 
diff-cache output from it, but thats slow and clumsy. 

Signed-off-by: Andreas Gal <gal@uci.edu>

--- b407d753e520fa0b1523d770d98b3015af197275/diff-cache.c
+++ diff-cache.c
@@ -2,6 +2,7 @@
 
 static int cached_only = 0;
 static int line_termination = '\n';
+static int show_unchanged = 0;
 
 /* A file entry went away or appeared */
 static void show_file(const char *prefix, struct cache_entry *ce)
@@ -32,7 +33,7 @@
 	}
 
 	oldmode = ntohl(old->ce_mode);
-	if (mode == oldmode && !memcmp(sha1, old->sha1, 20))
+	if ((mode == oldmode && !memcmp(sha1, old->sha1, 20)) != show_unchanged)
 		return 0;
 
 	strcpy(old_sha1_hex, sha1_to_hex(old->sha1));
@@ -85,7 +86,7 @@
 	}
 }
 
-static char *diff_cache_usage = "diff-cache [-r] [-z] [--cached] <tree sha1>";
+static char *diff_cache_usage = "diff-cache [-r] [-u] [-z] [--cached] <tree sha1>";
 
 int main(int argc, char **argv)
 {
@@ -102,6 +103,10 @@
 			/* We accept the -r flag just to look like diff-tree */
 			continue;
 		}
+		if (!strcmp(arg, "-u")) {
+			show_unchanged = 1;
+			continue;
+		}
 		if (!strcmp(arg, "-z")) {
 			line_termination = '\0';
 			continue;

Re: [PATCH] Add -u option to diff-cache to show UNCHANGED files

[Petr Baudis]

Dear diary, on Sun, Apr 24, 2005 at 05:28:17AM CEST, I got a letter
where Andreas Gal <gal@uci.edu> told me that...
> With -u diff-cache shows unchanged files, instead of files that changed. 
> This is useful to implement a "git clean" command that throws away all 
> checked out files that have not changed (yes, I really would like to 
> have that). One could also do show-files and then substract the 
> diff-cache output from it, but thats slow and clumsy. 
> 
> Signed-off-by: Andreas Gal <gal@uci.edu>

I don't think this fits to diff-cache (since the output is basically
nonsensical apart of the filename, right?). Maybe rather show-files?

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