From: Junio C Hamano <junkio@cox.net>
Date: Sat, 25 Feb 2006 05:55:23 +0000 (-0800)
Subject: Merge branches 'jc/rev-list' and 'jc/pack-thin'
X-Git-Tag: v1.3.0-rc1~141
X-Git-Url: https://git.lorimer.id.au/gitweb.git/diff_plain/f0b0af1b04f558b684cae2a3b805ca4bab84d45f?ds=inline;hp=-c

Merge branches 'jc/rev-list' and 'jc/pack-thin'

* jc/rev-list:
rev-list --objects: use full pathname to help hashing.
rev-list --objects-edge: remove duplicated edge commit output.
rev-list --objects-edge

* jc/pack-thin:
pack-objects: hash basename and direname a bit differently.
pack-objects: allow "thin" packs to exceed depth limits
pack-objects: use full pathname to help hashing with "thin" pack.
pack-objects: thin pack micro-optimization.
Use thin pack transfer in "git fetch".
Add git-push --thin.
send-pack --thin: use "thin pack" delta transfer.
Thin pack - create packfile with missing delta base.

Conflicts:

pack-objects.c (taking "next")
send-pack.c (taking "next")
---

f0b0af1b04f558b684cae2a3b805ca4bab84d45f
diff --combined git-fetch.sh
index fcc24f85c3,b4325d9d98,23d965f327..de4f011e26
--- a/git-fetch.sh
+++ b/git-fetch.sh
@@@@ -320,7 -320,7 -320,7 +320,7 @@@@ fetch_main () 
       ( : subshell because we muck with IFS
         IFS=" 	$LF"
         (
-- 	  git-fetch-pack $exec $keep "$remote" $rref || echo failed "$remote"
++ 	  git-fetch-pack $exec $keep --thin "$remote" $rref || echo failed "$remote"
         ) |
         while read sha1 remote_name
         do
@@@@ -368,25 -368,20 -368,20 +368,25 @@@@ fetch_main "$reflist
   # automated tag following
   case "$no_tags$tags" in
   '')
 --	taglist=$(IFS=" " &&
 --	git-ls-remote $upload_pack --tags "$remote" |
 --	sed -ne 's|^\([0-9a-f]*\)[ 	]\(refs/tags/.*\)^{}$|\1 \2|p' |
 --	while read sha1 name
 --	do
 --		test -f "$GIT_DIR/$name" && continue
 --	  	git-check-ref-format "$name" || {
 --			echo >&2 "warning: tag ${name} ignored"
 --			continue
 --		}
 --		git-cat-file -t "$sha1" >/dev/null 2>&1 || continue
 --		echo >&2 "Auto-following $name"
 --		echo ".${name}:${name}"
 --	done)
 ++	case "$reflist" in
 ++	*:refs/*)
 ++		# effective only when we are following remote branch
 ++		# using local tracking branch.
 ++		taglist=$(IFS=" " &&
 ++		git-ls-remote $upload_pack --tags "$remote" |
 ++		sed -ne 's|^\([0-9a-f]*\)[ 	]\(refs/tags/.*\)^{}$|\1 \2|p' |
 ++		while read sha1 name
 ++		do
 ++			test -f "$GIT_DIR/$name" && continue
 ++			git-check-ref-format "$name" || {
 ++				echo >&2 "warning: tag ${name} ignored"
 ++				continue
 ++			}
 ++			git-cat-file -t "$sha1" >/dev/null 2>&1 || continue
 ++			echo >&2 "Auto-following $name"
 ++			echo ".${name}:${name}"
 ++		done)
 ++	esac
   	case "$taglist" in
   	'') ;;
   	?*)
diff --combined pack-objects.c
index 8f352aa6c1,c5a5e61605,095bcb8286..be7a2008c5
--- a/pack-objects.c
+++ b/pack-objects.c
@@@@ -3,188 -3,31 -3,194 +3,196 @@@@
   #include "delta.h"
   #include "pack.h"
   #include "csum-file.h"
++ #include "diff.h"
   #include <sys/time.h>
 ++#include <signal.h>
   
 - static const char pack_usage[] = "git-pack-objects [-q] [--non-empty] [--local] [--incremental] [--window=N] [--depth=N] {--stdout | base-name} < object-list";
 + static const char pack_usage[] = "git-pack-objects [-q] [--no-reuse-delta] [--non-empty] [--local] [--incremental] [--window=N] [--depth=N] {--stdout | base-name} < object-list";
   
   struct object_entry {
   	unsigned char sha1[20];
 - 	unsigned long size;
 - 	unsigned long offset;
 - 	unsigned int depth;
 - 	unsigned int hash;
 + 	unsigned long size;	/* uncompressed size */
 + 	unsigned long offset;	/* offset into the final pack file;
 + 				 * nonzero if already written.
 + 				 */
 + 	unsigned int depth;	/* delta depth */
 + 	unsigned int delta_limit;	/* base adjustment for in-pack delta */
 + 	unsigned int hash;	/* name hint hash */
   	enum object_type type;
 - 	unsigned long delta_size;
 - 	struct object_entry *delta;
 + 	enum object_type in_pack_type;	/* could be delta */
 + 	unsigned long delta_size;	/* delta data size (uncompressed) */
 + 	struct object_entry *delta;	/* delta base object */
 + 	struct packed_git *in_pack; 	/* already in pack */
 + 	unsigned int in_pack_offset;
 + 	struct object_entry *delta_child; /* delitified objects who bases me */
 + 	struct object_entry *delta_sibling; /* other deltified objects who
 + 					     * uses the same base as me
 + 					     */
++ 	int preferred_base;	/* we do not pack this, but is encouraged to
++ 				 * be used as the base objectto delta huge
++ 				 * objects against.
++ 				 */
++ 	int based_on_preferred;	/* current delta candidate is a preferred
++ 				 * one, or delta against a preferred one.
++ 				 */
   };
   
 + /*
 +  * Objects we are going to pack are colected in objects array (dynamically
 +  * expanded).  nr_objects & nr_alloc controls this array.  They are stored
 +  * in the order we see -- typically rev-list --objects order that gives us
 +  * nice "minimum seek" order.
 +  *
 +  * sorted-by-sha ans sorted-by-type are arrays of pointers that point at
 +  * elements in the objects array.  The former is used to build the pack
 +  * index (lists object names in the ascending order to help offset lookup),
 +  * and the latter is used to group similar things together by try_delta()
 +  * heuristics.
 +  */
 + 
   static unsigned char object_list_sha1[20];
   static int non_empty = 0;
 + static int no_reuse_delta = 0;
   static int local = 0;
   static int incremental = 0;
   static struct object_entry **sorted_by_sha, **sorted_by_type;
   static struct object_entry *objects = NULL;
-- static int nr_objects = 0, nr_alloc = 0;
++ static int nr_objects = 0, nr_alloc = 0, nr_result = 0;
   static const char *base_name;
   static unsigned char pack_file_sha1[20];
   static int progress = 1;
 ++static volatile int progress_update = 0;
 + 
 + /*
 +  * The object names in objects array are hashed with this hashtable,
 +  * to help looking up the entry by object name.  Binary search from
 +  * sorted_by_sha is also possible but this was easier to code and faster.
 +  * This hashtable is built after all the objects are seen.
 +  */
 + static int *object_ix = NULL;
 + static int object_ix_hashsz = 0;
 + 
 + /*
 +  * Pack index for existing packs give us easy access to the offsets into
 +  * corresponding pack file where each object's data starts, but the entries
 +  * do not store the size of the compressed representation (uncompressed
 +  * size is easily available by examining the pack entry header).  We build
 +  * a hashtable of existing packs (pack_revindex), and keep reverse index
 +  * here -- pack index file is sorted by object name mapping to offset; this
 +  * pack_revindex[].revindex array is an ordered list of offsets, so if you
 +  * know the offset of an object, next offset is where its packed
 +  * representation ends.
 +  */
 + struct pack_revindex {
 + 	struct packed_git *p;
 + 	unsigned long *revindex;
 + } *pack_revindex = NULL;
 + static int pack_revindex_hashsz = 0;
 + 
 + /*
 +  * stats
 +  */
 + static int written = 0;
 + static int written_delta = 0;
 + static int reused = 0;
 + static int reused_delta = 0;
 + 
 + static int pack_revindex_ix(struct packed_git *p)
 + {
 + 	unsigned int ui = (unsigned int) p;
 + 	int i;
 + 
 + 	ui = ui ^ (ui >> 16); /* defeat structure alignment */
 + 	i = (int)(ui % pack_revindex_hashsz);
 + 	while (pack_revindex[i].p) {
 + 		if (pack_revindex[i].p == p)
 + 			return i;
 + 		if (++i == pack_revindex_hashsz)
 + 			i = 0;
 + 	}
 + 	return -1 - i;
 + }
 + 
 + static void prepare_pack_ix(void)
 + {
 + 	int num;
 + 	struct packed_git *p;
 + 	for (num = 0, p = packed_git; p; p = p->next)
 + 		num++;
 + 	if (!num)
 + 		return;
 + 	pack_revindex_hashsz = num * 11;
 + 	pack_revindex = xcalloc(sizeof(*pack_revindex), pack_revindex_hashsz);
 + 	for (p = packed_git; p; p = p->next) {
 + 		num = pack_revindex_ix(p);
 + 		num = - 1 - num;
 + 		pack_revindex[num].p = p;
 + 	}
 + 	/* revindex elements are lazily initialized */
 + }
 + 
 + static int cmp_offset(const void *a_, const void *b_)
 + {
 + 	unsigned long a = *(unsigned long *) a_;
 + 	unsigned long b = *(unsigned long *) b_;
 + 	if (a < b)
 + 		return -1;
 + 	else if (a == b)
 + 		return 0;
 + 	else
 + 		return 1;
 + }
 + 
 + /*
 +  * Ordered list of offsets of objects in the pack.
 +  */
 + static void prepare_pack_revindex(struct pack_revindex *rix)
 + {
 + 	struct packed_git *p = rix->p;
 + 	int num_ent = num_packed_objects(p);
 + 	int i;
 + 	void *index = p->index_base + 256;
 + 
 + 	rix->revindex = xmalloc(sizeof(unsigned long) * (num_ent + 1));
 + 	for (i = 0; i < num_ent; i++) {
 + 		long hl = *((long *)(index + 24 * i));
 + 		rix->revindex[i] = ntohl(hl);
 + 	}
 + 	/* This knows the pack format -- the 20-byte trailer
 + 	 * follows immediately after the last object data.
 + 	 */
 + 	rix->revindex[num_ent] = p->pack_size - 20;
 + 	qsort(rix->revindex, num_ent, sizeof(unsigned long), cmp_offset);
 + }
 + 
 + static unsigned long find_packed_object_size(struct packed_git *p,
 + 					     unsigned long ofs)
 + {
 + 	int num;
 + 	int lo, hi;
 + 	struct pack_revindex *rix;
 + 	unsigned long *revindex;
 + 	num = pack_revindex_ix(p);
 + 	if (num < 0)
 + 		die("internal error: pack revindex uninitialized");
 + 	rix = &pack_revindex[num];
 + 	if (!rix->revindex)
 + 		prepare_pack_revindex(rix);
 + 	revindex = rix->revindex;
 + 	lo = 0;
 + 	hi = num_packed_objects(p) + 1;
 + 	do {
 + 		int mi = (lo + hi) / 2;
 + 		if (revindex[mi] == ofs) {
 + 			return revindex[mi+1] - ofs;
 + 		}
 + 		else if (ofs < revindex[mi])
 + 			hi = mi;
 + 		else
 + 			lo = mi + 1;
 + 	} while (lo < hi);
 + 	die("internal error: pack revindex corrupt");
 + }
   
   static void *delta_against(void *buf, unsigned long size, struct object_entry *entry)
   {
@@@@ -231,73 -74,39 -237,77 +239,77 @@@@ static int encode_header(enum object_ty
   	return n;
   }
   
-- static unsigned long write_object(struct sha1file *f, struct object_entry *entry)
++ static unsigned long write_object(struct sha1file *f,
++ 				  struct object_entry *entry)
   {
   	unsigned long size;
   	char type[10];
 - 	void *buf = read_sha1_file(entry->sha1, type, &size);
 + 	void *buf;
   	unsigned char header[10];
   	unsigned hdrlen, datalen;
   	enum object_type obj_type;
 + 	int to_reuse = 0;
   
 - 	if (!buf)
 - 		die("unable to read %s", sha1_to_hex(entry->sha1));
 - 	if (size != entry->size)
 - 		die("object %s size inconsistency (%lu vs %lu)", sha1_to_hex(entry->sha1), size, entry->size);
++ 	if (entry->preferred_base)
++ 		return 0;
+  
 - 	/*
 - 	 * The object header is a byte of 'type' followed by zero or
 - 	 * more bytes of length.  For deltas, the 20 bytes of delta sha1
 - 	 * follows that.
 - 	 */
   	obj_type = entry->type;
 - 	if (entry->delta) {
 - 		buf = delta_against(buf, size, entry);
 - 		size = entry->delta_size;
 - 		obj_type = OBJ_DELTA;
 - 	}
 - 	hdrlen = encode_header(obj_type, size, header);
 - 	sha1write(f, header, hdrlen);
 - 	if (entry->delta) {
 - 		sha1write(f, entry->delta, 20);
 - 		hdrlen += 20;
 - 	}
 - 	datalen = sha1write_compressed(f, buf, size);
 - 	free(buf);
 + 	if (! entry->in_pack)
 + 		to_reuse = 0;	/* can't reuse what we don't have */
 + 	else if (obj_type == OBJ_DELTA)
 + 		to_reuse = 1;	/* check_object() decided it for us */
 + 	else if (obj_type != entry->in_pack_type)
 + 		to_reuse = 0;	/* pack has delta which is unusable */
 + 	else if (entry->delta)
 + 		to_reuse = 0;	/* we want to pack afresh */
 + 	else
 + 		to_reuse = 1;	/* we have it in-pack undeltified,
 + 				 * and we do not need to deltify it.
 + 				 */
 + 
 + 	if (! to_reuse) {
 + 		buf = read_sha1_file(entry->sha1, type, &size);
 + 		if (!buf)
 + 			die("unable to read %s", sha1_to_hex(entry->sha1));
 + 		if (size != entry->size)
 + 			die("object %s size inconsistency (%lu vs %lu)",
 + 			    sha1_to_hex(entry->sha1), size, entry->size);
 + 		if (entry->delta) {
 + 			buf = delta_against(buf, size, entry);
 + 			size = entry->delta_size;
 + 			obj_type = OBJ_DELTA;
 + 		}
 + 		/*
 + 		 * The object header is a byte of 'type' followed by zero or
 + 		 * more bytes of length.  For deltas, the 20 bytes of delta
 + 		 * sha1 follows that.
 + 		 */
 + 		hdrlen = encode_header(obj_type, size, header);
 + 		sha1write(f, header, hdrlen);
 + 
 + 		if (entry->delta) {
 + 			sha1write(f, entry->delta, 20);
 + 			hdrlen += 20;
 + 		}
 + 		datalen = sha1write_compressed(f, buf, size);
 + 		free(buf);
 + 	}
 + 	else {
 + 		struct packed_git *p = entry->in_pack;
 + 		use_packed_git(p);
 + 
 + 		datalen = find_packed_object_size(p, entry->in_pack_offset);
 + 		buf = p->pack_base + entry->in_pack_offset;
 + 		sha1write(f, buf, datalen);
 + 		unuse_packed_git(p);
 + 		hdrlen = 0; /* not really */
 + 		if (obj_type == OBJ_DELTA)
 + 			reused_delta++;
 + 		reused++;
 + 	}
 + 	if (obj_type == OBJ_DELTA)
 + 		written_delta++;
 + 	written++;
   	return hdrlen + datalen;
   }
   
@@@@ -323,49 -132,32 -333,31 +335,52 @@@@ static void write_pack_file(void
   	int i;
   	struct sha1file *f;
   	unsigned long offset;
 - 	unsigned long mb;
   	struct pack_header hdr;
 ++	unsigned last_percent = 999;
 ++	int do_progress = 0;
   
   	if (!base_name)
   		f = sha1fd(1, "<stdout>");
 --	else
 - 		f = sha1create("%s-%s.%s", base_name, sha1_to_hex(object_list_sha1), "pack");
 ++	else {
 + 		f = sha1create("%s-%s.%s", base_name,
 + 			       sha1_to_hex(object_list_sha1), "pack");
 ++		do_progress = progress;
 ++	}
 ++	if (do_progress)
-  		fprintf(stderr, "Writing %d objects.\n", nr_objects);
+++		fprintf(stderr, "Writing %d objects.\n", nr_result);
 ++
   	hdr.hdr_signature = htonl(PACK_SIGNATURE);
   	hdr.hdr_version = htonl(PACK_VERSION);
-- 	hdr.hdr_entries = htonl(nr_objects);
++ 	hdr.hdr_entries = htonl(nr_result);
   	sha1write(f, &hdr, sizeof(hdr));
   	offset = sizeof(hdr);
 --	for (i = 0; i < nr_objects; i++)
+++	if (!nr_result)
+++		goto done;
 ++	for (i = 0; i < nr_objects; i++) {
   		offset = write_one(f, objects + i, offset);
 --
 ++		if (do_progress) {
-  			unsigned percent = written * 100 / nr_objects;
+++			unsigned percent = written * 100 / nr_result;
 ++			if (progress_update || percent != last_percent) {
 ++				fprintf(stderr, "%4u%% (%u/%u) done\r",
-  					percent, written, nr_objects);
+++					percent, written, nr_result);
 ++				progress_update = 0;
 ++				last_percent = percent;
 ++			}
 ++		}
 ++	}
 ++	if (do_progress)
 ++		fputc('\n', stderr);
-  
+++ done:
   	sha1close(f, pack_file_sha1, 1);
 - 	mb = offset >> 20;
 - 	offset &= 0xfffff;
   }
   
   static void write_index_file(void)
   {
   	int i;
-- 	struct sha1file *f = sha1create("%s-%s.%s", base_name, sha1_to_hex(object_list_sha1), "idx");
++ 	struct sha1file *f = sha1create("%s-%s.%s", base_name,
++ 					sha1_to_hex(object_list_sha1), "idx");
   	struct object_entry **list = sorted_by_sha;
-- 	struct object_entry **last = list + nr_objects;
++ 	struct object_entry **last = list + nr_result;
   	unsigned int array[256];
   
   	/*
@@@@ -390,7 -182,7 -382,7 +405,7 @@@@
   	 * Write the actual SHA1 entries..
   	 */
   	list = sorted_by_sha;
-- 	for (i = 0; i < nr_objects; i++) {
++ 	for (i = 0; i < nr_result; i++) {
   		struct object_entry *entry = *list++;
   		unsigned int offset = htonl(entry->offset);
   		sha1write(f, &offset, 4);
@@@@ -400,27 -192,25 -392,139 +415,139 @@@@
   	sha1close(f, NULL, 1);
   }
   
-- static int add_object_entry(unsigned char *sha1, unsigned int hash)
++ static int locate_object_entry_hash(const unsigned char *sha1)
++ {
++ 	int i;
++ 	unsigned int ui;
++ 	memcpy(&ui, sha1, sizeof(unsigned int));
++ 	i = ui % object_ix_hashsz;
++ 	while (0 < object_ix[i]) {
++ 		if (!memcmp(sha1, objects[object_ix[i]-1].sha1, 20))
++ 			return i;
++ 		if (++i == object_ix_hashsz)
++ 			i = 0;
++ 	}
++ 	return -1 - i;
++ }
++ 
++ static struct object_entry *locate_object_entry(const unsigned char *sha1)
++ {
++ 	int i;
++ 
++ 	if (!object_ix_hashsz)
++ 		return NULL;
++ 
++ 	i = locate_object_entry_hash(sha1);
++ 	if (0 <= i)
++ 		return &objects[object_ix[i]-1];
++ 	return NULL;
++ }
++ 
++ static void rehash_objects(void)
++ {
++ 	int i;
++ 	struct object_entry *oe;
++ 
++ 	object_ix_hashsz = nr_objects * 3;
++ 	if (object_ix_hashsz < 1024)
++ 		object_ix_hashsz = 1024;
++ 	object_ix = xrealloc(object_ix, sizeof(int) * object_ix_hashsz);
++ 	object_ix = memset(object_ix, 0, sizeof(int) * object_ix_hashsz);
++ 	for (i = 0, oe = objects; i < nr_objects; i++, oe++) {
++ 		int ix = locate_object_entry_hash(oe->sha1);
++ 		if (0 <= ix)
++ 			continue;
++ 		ix = -1 - ix;
++ 		object_ix[ix] = i + 1;
++ 	}
++ }
++ 
++ struct name_path {
++ 	struct name_path *up;
++ 	const char *elem;
++ 	int len;
++ };
++ 
++ #define DIRBITS 12
++ 
++ static unsigned name_hash(struct name_path *path, const char *name)
++ {
++ 	struct name_path *p = path;
++ 	const char *n = name + strlen(name);
++ 	unsigned hash = 0, name_hash = 0, name_done = 0;
++ 
++ 	if (n != name && n[-1] == '\n')
++ 		n--;
++ 	while (name <= --n) {
++ 		unsigned char c = *n;
++ 		if (c == '/' && !name_done) {
++ 			name_hash = hash;
++ 			name_done = 1;
++ 			hash = 0;
++ 		}
++ 		hash = hash * 11 + c;
++ 	}
++ 	if (!name_done) {
++ 		name_hash = hash;
++ 		hash = 0;
++ 	}
++ 	for (p = path; p; p = p->up) {
++ 		hash = hash * 11 + '/';
++ 		n = p->elem + p->len;
++ 		while (p->elem <= --n) {
++ 			unsigned char c = *n;
++ 			hash = hash * 11 + c;
++ 		}
++ 	}
++ 	/*
++ 	 * Make sure "Makefile" and "t/Makefile" are hashed separately
++ 	 * but close enough.
++ 	 */
++ 	hash = (name_hash<<DIRBITS) | (hash & ((1U<<DIRBITS )-1));
++ 
++ 	if (0) { /* debug */
++ 		n = name + strlen(name);
++ 		if (n != name && n[-1] == '\n')
++ 			n--;
++ 		while (name <= --n)
++ 			fputc(*n, stderr);
++ 		for (p = path; p; p = p->up) {
++ 			fputc('/', stderr);
++ 			n = p->elem + p->len;
++ 			while (p->elem <= --n)
++ 				fputc(*n, stderr);
++ 		}
++ 		fprintf(stderr, "\t%08x\n", hash);
++ 	}
++ 	return hash;
++ }
++ 
++ static int add_object_entry(const unsigned char *sha1, unsigned hash, int exclude)
   {
   	unsigned int idx = nr_objects;
   	struct object_entry *entry;
 + 	struct packed_git *p;
 + 	unsigned int found_offset = 0;
 + 	struct packed_git *found_pack = NULL;
-  
-  	for (p = packed_git; p; p = p->next) {
-  		struct pack_entry e;
-  		if (find_pack_entry_one(sha1, &e, p)) {
-  			if (incremental)
-  				return 0;
-  			if (local && !p->pack_local)
-  				return 0;
-  			if (!found_pack) {
-  				found_offset = e.offset;
-  				found_pack = e.p;
++ 	int ix, status = 0;
+  
 - 	if (incremental || local) {
 - 		struct packed_git *p;
 - 
++ 	if (!exclude) {
+  		for (p = packed_git; p; p = p->next) {
+  			struct pack_entry e;
 - 
+  			if (find_pack_entry_one(sha1, &e, p)) {
+  				if (incremental)
+  					return 0;
+  				if (local && !p->pack_local)
+  					return 0;
++ 				if (!found_pack) {
++ 					found_offset = e.offset;
++ 					found_pack = e.p;
++ 				}
   			}
   		}
   	}
++ 	if ((entry = locate_object_entry(sha1)) != NULL)
++ 		goto already_added;
   
   	if (idx >= nr_alloc) {
   		unsigned int needed = (idx + 1024) * 3 / 2;
@@@@ -428,146 -218,42 -532,185 +555,189 @@@@
   		nr_alloc = needed;
   	}
   	entry = objects + idx;
++ 	nr_objects = idx + 1;
   	memset(entry, 0, sizeof(*entry));
   	memcpy(entry->sha1, sha1, 20);
   	entry->hash = hash;
-  	if (found_pack) {
-  		entry->in_pack = found_pack;
-  		entry->in_pack_offset = found_offset;
 - 	nr_objects = idx+1;
 - 	return 1;
++ 
++ 	if (object_ix_hashsz * 3 <= nr_objects * 4)
++ 		rehash_objects();
++ 	else {
++ 		ix = locate_object_entry_hash(entry->sha1);
++ 		if (0 <= ix)
++ 			die("internal error in object hashing.");
++ 		object_ix[-1 - ix] = idx + 1;
 + 	}
-  	nr_objects = idx+1;
-  	return 1;
++ 	status = 1;
++ 
++  already_added:
+++	if (progress_update) {
+++		fprintf(stderr, "Counting objects...%d\r", nr_objects);
+++		progress_update = 0;
+++	}
++ 	if (exclude)
++ 		entry->preferred_base = 1;
++ 	else {
++ 		if (found_pack) {
++ 			entry->in_pack = found_pack;
++ 			entry->in_pack_offset = found_offset;
++ 		}
++ 	}
++ 	return status;
 + }
 + 
-  static int locate_object_entry_hash(unsigned char *sha1)
++ static void add_pbase_tree(struct tree_desc *tree, struct name_path *up)
 + {
-  	int i;
-  	unsigned int ui;
-  	memcpy(&ui, sha1, sizeof(unsigned int));
-  	i = ui % object_ix_hashsz;
-  	while (0 < object_ix[i]) {
-  		if (!memcmp(sha1, objects[object_ix[i]-1].sha1, 20))
-  			return i;
-  		if (++i == object_ix_hashsz)
-  			i = 0;
++ 	while (tree->size) {
++ 		const unsigned char *sha1;
++ 		const char *name;
++ 		unsigned mode, hash;
++ 		unsigned long size;
++ 		char type[20];
++ 
++ 		sha1 = tree_entry_extract(tree, &name, &mode);
++ 		update_tree_entry(tree);
++ 		if (!has_sha1_file(sha1))
++ 			continue;
++ 		if (sha1_object_info(sha1, type, &size))
++ 			continue;
++ 
++ 		hash = name_hash(up, name);
++ 		if (!add_object_entry(sha1, hash, 1))
++ 			continue;
++ 
++ 		if (!strcmp(type, "tree")) {
++ 			struct tree_desc sub;
++ 			void *elem;
++ 			struct name_path me;
++ 
++ 			elem = read_sha1_file(sha1, type, &sub.size);
++ 			sub.buf = elem;
++ 			if (sub.buf) {
++ 				me.up = up;
++ 				me.elem = name;
++ 				me.len = strlen(name);
++ 				add_pbase_tree(&sub, &me);
++ 				free(elem);
++ 			}
++ 		}
 + 	}
-  	return -1 - i;
 + }
 + 
-  static struct object_entry *locate_object_entry(unsigned char *sha1)
++ static void add_preferred_base(unsigned char *sha1)
 + {
-  	int i = locate_object_entry_hash(sha1);
-  	if (0 <= i)
-  		return &objects[object_ix[i]-1];
-  	return NULL;
++ 	struct tree_desc tree;
++ 	void *elem;
++ 
++ 	elem = read_object_with_reference(sha1, "tree", &tree.size, NULL);
++ 	tree.buf = elem;
++ 	if (!tree.buf)
++ 		return;
++ 	if (add_object_entry(sha1, name_hash(NULL, ""), 1))
++ 		add_pbase_tree(&tree, NULL);
++ 	free(elem);
   }
   
   static void check_object(struct object_entry *entry)
   {
   	char type[20];
   
-  	if (entry->in_pack) {
 - 	if (!sha1_object_info(entry->sha1, type, &entry->size)) {
 - 		if (!strcmp(type, "commit")) {
 - 			entry->type = OBJ_COMMIT;
 - 		} else if (!strcmp(type, "tree")) {
 - 			entry->type = OBJ_TREE;
 - 		} else if (!strcmp(type, "blob")) {
 - 			entry->type = OBJ_BLOB;
 - 		} else if (!strcmp(type, "tag")) {
 - 			entry->type = OBJ_TAG;
 - 		} else
 - 			die("unable to pack object %s of type %s",
 - 			    sha1_to_hex(entry->sha1), type);
++ 	if (entry->in_pack && !entry->preferred_base) {
 + 		unsigned char base[20];
 + 		unsigned long size;
 + 		struct object_entry *base_entry;
 + 
 + 		/* We want in_pack_type even if we do not reuse delta.
 + 		 * There is no point not reusing non-delta representations.
 + 		 */
 + 		check_reuse_pack_delta(entry->in_pack,
 + 				       entry->in_pack_offset,
 + 				       base, &size,
 + 				       &entry->in_pack_type);
 + 
 + 		/* Check if it is delta, and the base is also an object
 + 		 * we are going to pack.  If so we will reuse the existing
 + 		 * delta.
 + 		 */
 + 		if (!no_reuse_delta &&
 + 		    entry->in_pack_type == OBJ_DELTA &&
-  		    (base_entry = locate_object_entry(base))) {
++ 		    (base_entry = locate_object_entry(base)) &&
++ 		    (!base_entry->preferred_base)) {
 + 
 + 			/* Depth value does not matter - find_deltas()
 + 			 * will never consider reused delta as the
 + 			 * base object to deltify other objects
 + 			 * against, in order to avoid circular deltas.
 + 			 */
 + 
 + 			/* uncompressed size of the delta data */
 + 			entry->size = entry->delta_size = size;
 + 			entry->delta = base_entry;
 + 			entry->type = OBJ_DELTA;
 + 
 + 			entry->delta_sibling = base_entry->delta_child;
 + 			base_entry->delta_child = entry;
 + 
 + 			return;
 + 		}
 + 		/* Otherwise we would do the usual */
   	}
 - 	else
 + 
 + 	if (sha1_object_info(entry->sha1, type, &entry->size))
   		die("unable to get type of object %s",
   		    sha1_to_hex(entry->sha1));
 + 
 + 	if (!strcmp(type, "commit")) {
 + 		entry->type = OBJ_COMMIT;
 + 	} else if (!strcmp(type, "tree")) {
 + 		entry->type = OBJ_TREE;
 + 	} else if (!strcmp(type, "blob")) {
 + 		entry->type = OBJ_BLOB;
 + 	} else if (!strcmp(type, "tag")) {
 + 		entry->type = OBJ_TAG;
 + 	} else
 + 		die("unable to pack object %s of type %s",
 + 		    sha1_to_hex(entry->sha1), type);
 + }
 + 
-  static void hash_objects(void)
-  {
-  	int i;
-  	struct object_entry *oe;
-  
-  	object_ix_hashsz = nr_objects * 2;
-  	object_ix = xcalloc(sizeof(int), object_ix_hashsz);
-  	for (i = 0, oe = objects; i < nr_objects; i++, oe++) {
-  		int ix = locate_object_entry_hash(oe->sha1);
-  		if (0 <= ix) {
-  			error("the same object '%s' added twice",
-  			      sha1_to_hex(oe->sha1));
-  			continue;
-  		}
-  		ix = -1 - ix;
-  		object_ix[ix] = i + 1;
-  	}
-  }
-  
 + static unsigned int check_delta_limit(struct object_entry *me, unsigned int n)
 + {
 + 	struct object_entry *child = me->delta_child;
 + 	unsigned int m = n;
 + 	while (child) {
 + 		unsigned int c = check_delta_limit(child, n + 1);
 + 		if (m < c)
 + 			m = c;
 + 		child = child->delta_sibling;
 + 	}
 + 	return m;
   }
   
   static void get_object_details(void)
   {
   	int i;
 - 	struct object_entry *entry = objects;
 + 	struct object_entry *entry;
   
-  	hash_objects();
 - 	for (i = 0; i < nr_objects; i++)
 - 		check_object(entry++);
 + 	prepare_pack_ix();
 + 	for (i = 0, entry = objects; i < nr_objects; i++, entry++)
 + 		check_object(entry);
-  	for (i = 0, entry = objects; i < nr_objects; i++, entry++)
-  		if (!entry->delta && entry->delta_child)
-  			entry->delta_limit =
-  				check_delta_limit(entry, 1);
++ 
++ 	if (nr_objects == nr_result) {
++ 		/*
++ 		 * Depth of objects that depend on the entry -- this
++ 		 * is subtracted from depth-max to break too deep
++ 		 * delta chain because of delta data reusing.
++ 		 * However, we loosen this restriction when we know we
++ 		 * are creating a thin pack -- it will have to be
++ 		 * expanded on the other end anyway, so do not
++ 		 * artificially cut the delta chain and let it go as
++ 		 * deep as it wants.
++ 		 */
++ 		for (i = 0, entry = objects; i < nr_objects; i++, entry++)
++ 			if (!entry->delta && entry->delta_child)
++ 				entry->delta_limit =
++ 					check_delta_limit(entry, 1);
++ 	}
   }
   
   typedef int (*entry_sort_t)(const struct object_entry *, const struct object_entry *);
@@@@ -598,6 -284,6 -741,24 +768,24 @@@@ static int sha1_sort(const struct objec
   	return memcmp(a->sha1, b->sha1, 20);
   }
   
++ static struct object_entry **create_final_object_list()
++ {
++ 	struct object_entry **list;
++ 	int i, j;
++ 
++ 	for (i = nr_result = 0; i < nr_objects; i++)
++ 		if (!objects[i].preferred_base)
++ 			nr_result++;
++ 	list = xmalloc(nr_result * sizeof(struct object_entry *));
++ 	for (i = j = 0; i < nr_objects; i++) {
++ 		if (!objects[i].preferred_base)
++ 			list[j++] = objects + i;
++ 	}
++ 	current_sort = sha1_sort;
++ 	qsort(list, nr_result, sizeof(struct object_entry *), sort_comparator);
++ 	return list;
++ }
++ 
   static int type_size_sort(const struct object_entry *a, const struct object_entry *b)
   {
   	if (a->type < b->type)
@@@@ -608,6 -294,6 -769,10 +796,10 @@@@
   		return -1;
   	if (a->hash > b->hash)
   		return 1;
++ 	if (a->preferred_base < b->preferred_base)
++ 		return -1;
++ 	if (a->preferred_base > b->preferred_base)
++ 		return 1;
   	if (a->size < b->size)
   		return -1;
   	if (a->size > b->size)
@@@@ -632,6 -318,6 -797,8 +824,8 @@@@ static int try_delta(struct unpacked *c
   {
   	struct object_entry *cur_entry = cur->entry;
   	struct object_entry *old_entry = old->entry;
++ 	int old_preferred = (old_entry->preferred_base ||
++ 			     old_entry->based_on_preferred);
   	unsigned long size, oldsize, delta_size, sizediff;
   	long max_size;
   	void *delta_buf;
@@@@ -640,22 -326,12 -807,28 +834,27 @@@@
   	if (cur_entry->type != old_entry->type)
   		return -1;
   
-  	/* If the current object is at edge, take the depth the objects
-  	 * that depend on the current object into account -- otherwise
-  	 * they would become too deep.
 - 	size = cur_entry->size;
 - 	if (size < 50)
++ 	/* We do not compute delta to *create* objects we are not
++ 	 * going to pack.
++ 	 */
++ 	if (cur_entry->preferred_base)
+  		return -1;
++ 
++ 	/* If the current object is at pack edge, take the depth the
++ 	 * objects that depend on the current object into account --
++ 	 * otherwise they would become too deep.
 + 	 */
 + 	if (cur_entry->delta_child) {
 + 		if (max_depth <= cur_entry->delta_limit)
 + 			return 0;
 + 		max_depth -= cur_entry->delta_limit;
 + 	}
 + 
 + 	size = cur_entry->size;
- -	if (size < 50)
- -		return -1;
   	oldsize = old_entry->size;
   	sizediff = oldsize > size ? oldsize - size : size - oldsize;
---	if (sizediff > size / 8)
+++
+++	if (size < 50)
   		return -1;
   	if (old_entry->depth >= max_depth)
   		return 0;
@@@@ -668,8 -344,8 -841,27 +867,27 @@@@
   	 * delete).
   	 */
   	max_size = size / 2 - 20;
-- 	if (cur_entry->delta)
-- 		max_size = cur_entry->delta_size-1;
++ 	if (cur_entry->delta) {
++ 		if (cur_entry->based_on_preferred) {
++ 			if (old_preferred)
++ 				max_size = cur_entry->delta_size-1;
++ 			else
++ 				/* trying with non-preferred one when we
++ 				 * already have a delta based on preferred
++ 				 * one is pointless.
++ 				 */
++ 				return -1;
++ 		}
++ 		else if (!old_preferred)
++ 			max_size = cur_entry->delta_size-1;
++ 		else
++ 			/* otherwise...  even if delta with a
++ 			 * preferred one produces a bigger result than
++ 			 * what we currently have, which is based on a
++ 			 * non-preferred one, it is OK.
++ 			 */
++ 			;
++ 	}
   	if (sizediff >= max_size)
   		return -1;
   	delta_buf = diff_delta(old->data, oldsize,
@@@@ -679,29 -355,21 -871,22 +897,30 @@@@
   	cur_entry->delta = old_entry;
   	cur_entry->delta_size = delta_size;
   	cur_entry->depth = old_entry->depth + 1;
++ 	cur_entry->based_on_preferred = old_preferred;
   	free(delta_buf);
   	return 0;
   }
   
 ++static void progress_interval(int signum)
 ++{
 ++	signal(SIGALRM, progress_interval);
 ++	progress_update = 1;
 ++}
 ++
   static void find_deltas(struct object_entry **list, int window, int depth)
   {
   	int i, idx;
   	unsigned int array_size = window * sizeof(struct unpacked);
   	struct unpacked *array = xmalloc(array_size);
 --	int eye_candy;
 ++	unsigned processed = 0;
 ++	unsigned last_percent = 999;
   
   	memset(array, 0, array_size);
   	i = nr_objects;
   	idx = 0;
 --	eye_candy = i - (nr_objects / 20);
 ++	if (progress)
-  		fprintf(stderr, "Deltifying %d objects.\n", nr_objects);
+++		fprintf(stderr, "Deltifying %d objects.\n", nr_result);
   
   	while (--i >= 0) {
   		struct object_entry *entry = list[i];
@@@@ -710,29 -378,15 -895,23 +929,31 @@@@
   		char type[10];
   		int j;
   
-  		processed++;
 --		if (progress && i <= eye_candy) {
 --			eye_candy -= nr_objects / 20;
 --			fputc('.', stderr);
+++		if (!entry->preferred_base)
+++			processed++;
+++
 ++		if (progress) {
-  			unsigned percent = processed * 100 / nr_objects;
+++			unsigned percent = processed * 100 / nr_result;
 ++			if (percent != last_percent || progress_update) {
 ++				fprintf(stderr, "%4u%% (%u/%u) done\r",
-  					percent, processed, nr_objects);
+++					percent, processed, nr_result);
 ++				progress_update = 0;
 ++				last_percent = percent;
 ++			}
   		}
 + 
 + 		if (entry->delta)
 + 			/* This happens if we decided to reuse existing
 + 			 * delta from a pack.  "!no_reuse_delta &&" is implied.
 + 			 */
 + 			continue;
 + 
   		free(n->data);
   		n->entry = entry;
   		n->data = read_sha1_file(entry->sha1, type, &size);
   		if (size != entry->size)
   			die("object %s inconsistent object length (%lu vs %lu)", sha1_to_hex(entry->sha1), size, entry->size);
 + 
   		j = window;
   		while (--j > 0) {
   			unsigned int other_idx = idx + j;
@@@@ -750,9 -404,6 -929,6 +971,9 @@@@
   			idx = 0;
   	}
   
 ++	if (progress)
 ++		fputc('\n', stderr);
 ++
   	for (i = 0; i < window; ++i)
   		free(array[i].data);
   	free(array);
@@@@ -760,10 -411,16 -936,18 +981,10 @@@@
   
   static void prepare_pack(int window, int depth)
   {
  -	if (progress)
  -		fprintf(stderr, "Packing %d objects", nr_result);
   	get_object_details();
 - 
 --	if (progress)
 - 		fprintf(stderr, "Packing %d objects", nr_objects);
  -		fputc('.', stderr);
  -
   	sorted_by_type = create_sorted_list(type_size_sort);
   	if (window && depth)
   		find_deltas(sorted_by_type, window+1, depth);
 --	if (progress)
 --		fputc('\n', stderr);
 --	write_pack_file();
   }
   
   static int reuse_cached_pack(unsigned char *sha1, int pack_to_stdout)
@@@@ -786,9 -443,8 -970,9 +1007,9 @@@@
   		}
   	}
   
 - 	fprintf(stderr, "Reusing %d objects pack %s\n", nr_objects,
 - 		sha1_to_hex(sha1));
 + 	if (progress)
 + 		fprintf(stderr, "Reusing %d objects pack %s\n", nr_objects,
 + 			sha1_to_hex(sha1));
   
   	if (pack_to_stdout) {
   		if (copy_fd(ifd, 1))
@@@@ -827,6 -483,10 -1011,10 +1048,6 @@@@ int main(int argc, char **argv
   	int window = 10, depth = 10, pack_to_stdout = 0;
   	struct object_entry **list;
   	int i;
 --	struct timeval prev_tv;
 --	int eye_candy = 0;
 --	int eye_candy_incr = 500;
 --
   
   	setup_git_directory();
   
@@@@ -864,10 -524,6 -1052,10 +1085,10 @@@@
   				progress = 0;
   				continue;
   			}
 + 			if (!strcmp("--no-reuse-delta", arg)) {
 + 				no_reuse_delta = 1;
 + 				continue;
 + 			}
   			if (!strcmp("--stdout", arg)) {
   				pack_to_stdout = 1;
   				continue;
@@@@ -883,71 -539,65 -1071,67 +1104,67 @@@@
   		usage(pack_usage);
   
   	prepare_packed_git();
 ++
   	if (progress) {
 ++		struct itimerval v;
 ++		v.it_interval.tv_sec = 1;
 ++		v.it_interval.tv_usec = 0;
 ++		v.it_value = v.it_interval;
 ++		signal(SIGALRM, progress_interval);
 ++		setitimer(ITIMER_REAL, &v, NULL);
   		fprintf(stderr, "Generating pack...\n");
 --		gettimeofday(&prev_tv, NULL);
   	}
 ++
   	while (fgets(line, sizeof(line), stdin) != NULL) {
-- 		unsigned int hash;
-- 		char *p;
   		unsigned char sha1[20];
   
-  		if (progress_update) {
 --		if (progress && (eye_candy <= nr_objects)) {
---			fprintf(stderr, "Counting objects...%d\r", nr_objects);
-  			progress_update = 0;
 --			if (eye_candy && (50 <= eye_candy_incr)) {
 --				struct timeval tv;
 --				int time_diff;
 --				gettimeofday(&tv, NULL);
 --				time_diff = (tv.tv_sec - prev_tv.tv_sec);
 --				time_diff <<= 10;
 --				time_diff += (tv.tv_usec - prev_tv.tv_usec);
 --				if ((1 << 9) < time_diff)
 --					eye_candy_incr += 50;
 --				else if (50 < eye_candy_incr)
 --					eye_candy_incr -= 50;
 --			}
 --			eye_candy += eye_candy_incr;
  -		}
++ 		if (line[0] == '-') {
++ 			if (get_sha1_hex(line+1, sha1))
++ 				die("expected edge sha1, got garbage:\n %s",
++ 				    line+1);
++ 			add_preferred_base(sha1);
++ 			continue;
   		}
   		if (get_sha1_hex(line, sha1))
   			die("expected sha1, got garbage:\n %s", line);
-- 		hash = 0;
-- 		p = line+40;
-- 		while (*p) {
-- 			unsigned char c = *p++;
-- 			if (isspace(c))
-- 				continue;
-- 			hash = hash * 11 + c;
-- 		}
-- 		add_object_entry(sha1, hash);
++ 		add_object_entry(sha1, name_hash(NULL, line+41), 0);
   	}
   	if (progress)
   		fprintf(stderr, "Done counting %d objects.\n", nr_objects);
---	if (non_empty && !nr_objects)
+++	sorted_by_sha = create_final_object_list();
+++	if (non_empty && !nr_result)
   		return 0;
   
-- 	sorted_by_sha = create_sorted_list(sha1_sort);
  -	sorted_by_sha = create_final_object_list();
   	SHA1_Init(&ctx);
   	list = sorted_by_sha;
-- 	for (i = 0; i < nr_objects; i++) {
++ 	for (i = 0; i < nr_result; i++) {
   		struct object_entry *entry = *list++;
   		SHA1_Update(&ctx, entry->sha1, 20);
   	}
   	SHA1_Final(object_list_sha1, &ctx);
++ 	if (progress && (nr_objects != nr_result))
++ 		fprintf(stderr, "Result has %d objects.\n", nr_result);
   
   	if (reuse_cached_pack(object_list_sha1, pack_to_stdout))
   		;
   	else {
---		prepare_pack(window, depth);
+++		if (nr_result)
+++			prepare_pack(window, depth);
 ++		if (progress && pack_to_stdout) {
 ++			/* the other end usually displays progress itself */
 ++			struct itimerval v = {{0,},};
 ++			setitimer(ITIMER_REAL, &v, NULL);
 ++			signal(SIGALRM, SIG_IGN );
 ++			progress_update = 0;
 ++		}
 ++		write_pack_file();
   		if (!pack_to_stdout) {
   			write_index_file();
   			puts(sha1_to_hex(object_list_sha1));
   		}
   	}
 + 	if (progress)
 + 		fprintf(stderr, "Total %d, written %d (delta %d), reused %d (delta %d)\n",
-  			nr_objects, written, written_delta, reused, reused_delta);
++ 			nr_result, written, written_delta, reused, reused_delta);
   	return 0;
   }
diff --combined rev-list.c
index ee5f15ae4e,dda6fcaa96,63391fc113..67d2a483fc
--- a/rev-list.c
+++ b/rev-list.c
@@@@ -27,10 -27,10 -27,9 +27,10 @@@@ static const char rev_list_usage[] 
   "  ordering output:\n"
   "    --merge-order [ --show-breaks ]\n"
   "    --topo-order\n"
  +"    --date-order\n"
   "  formatting output:\n"
   "    --parents\n"
- -"    --objects\n"
+ +"    --objects | --objects-edge\n"
   "    --unpacked\n"
   "    --header | --pretty\n"
   "    --abbrev=nr | --no-abbrev\n"
@@@@ -44,6 -44,7 -43,6 +44,7 @@@@ static int bisect_list = 0
   static int tag_objects = 0;
   static int tree_objects = 0;
   static int blob_objects = 0;
+ +static int edge_hint = 0;
   static int verbose_header = 0;
   static int abbrev = DEFAULT_ABBREV;
   static int show_parents = 0;
@@@@ -57,11 -58,41 -56,10 +58,41 @@@@ static int merge_order = 0
   static int show_breaks = 0;
   static int stop_traversal = 0;
   static int topo_order = 0;
  +static int lifo = 1;
   static int no_merges = 0;
   static const char **paths = NULL;
   static int remove_empty_trees = 0;
   
+ +struct name_path {
+ +	struct name_path *up;
+ +	int elem_len;
+ +	const char *elem;
+ +};
+ +
+ +static char *path_name(struct name_path *path, const char *name)
+ +{
+ +	struct name_path *p;
+ +	char *n, *m;
+ +	int nlen = strlen(name);
+ +	int len = nlen + 1;
+ +
+ +	for (p = path; p; p = p->up) {
+ +		if (p->elem_len)
+ +			len += p->elem_len + 1;
+ +	}
+ +	n = xmalloc(len);
+ +	m = n + len - (nlen + 1);
+ +	strcpy(m, name);
+ +	for (p = path; p; p = p->up) {
+ +		if (p->elem_len) {
+ +			m -= p->elem_len + 1;
+ +			memcpy(m, p->elem, p->elem_len);
+ +			m[p->elem_len] = '/';
+ +		}
+ +	}
+ +	return n;
+ +}
+ +
   static void show_commit(struct commit *commit)
   {
   	commit->object.flags |= SHOWN;
@@@@ -173,17 -204,23 -171,17 +204,23 @@@@ static int process_commit(struct commi
   	return CONTINUE;
   }
   
- -static struct object_list **add_object(struct object *obj, struct object_list **p, const char *name)
+ +static struct object_list **add_object(struct object *obj,
+ +				       struct object_list **p,
+ +				       struct name_path *path,
+ +				       const char *name)
   {
   	struct object_list *entry = xmalloc(sizeof(*entry));
   	entry->item = obj;
   	entry->next = *p;
- -	entry->name = name;
+ +	entry->name = path_name(path, name);
   	*p = entry;
   	return &entry->next;
   }
   
- -static struct object_list **process_blob(struct blob *blob, struct object_list **p, const char *name)
+ +static struct object_list **process_blob(struct blob *blob,
+ +					 struct object_list **p,
+ +					 struct name_path *path,
+ +					 const char *name)
   {
   	struct object *obj = &blob->object;
   
@@@@ -192,13 -229,17 -190,13 +229,17 @@@@
   	if (obj->flags & (UNINTERESTING | SEEN))
   		return p;
   	obj->flags |= SEEN;
- -	return add_object(obj, p, name);
+ +	return add_object(obj, p, path, name);
   }
   
- -static struct object_list **process_tree(struct tree *tree, struct object_list **p, const char *name)
+ +static struct object_list **process_tree(struct tree *tree,
+ +					 struct object_list **p,
+ +					 struct name_path *path,
+ +					 const char *name)
   {
   	struct object *obj = &tree->object;
   	struct tree_entry_list *entry;
+ +	struct name_path me;
   
   	if (!tree_objects)
   		return p;
@@@@ -207,15 -248,18 -205,15 +248,18 @@@@
   	if (parse_tree(tree) < 0)
   		die("bad tree object %s", sha1_to_hex(obj->sha1));
   	obj->flags |= SEEN;
- -	p = add_object(obj, p, name);
+ +	p = add_object(obj, p, path, name);
+ +	me.up = path;
+ +	me.elem = name;
+ +	me.elem_len = strlen(name);
   	entry = tree->entries;
   	tree->entries = NULL;
   	while (entry) {
   		struct tree_entry_list *next = entry->next;
   		if (entry->directory)
- -			p = process_tree(entry->item.tree, p, entry->name);
+ +			p = process_tree(entry->item.tree, p, &me, entry->name);
   		else
- -			p = process_blob(entry->item.blob, p, entry->name);
+ +			p = process_blob(entry->item.blob, p, &me, entry->name);
   		free(entry);
   		entry = next;
   	}
@@@@ -230,7 -274,7 -228,7 +274,7 @@@@ static void show_commit_list(struct com
   	while (list) {
   		struct commit *commit = pop_most_recent_commit(&list, SEEN);
   
- -		p = process_tree(commit->tree, p, "");
+ +		p = process_tree(commit->tree, p, NULL, "");
   		if (process_commit(commit) == STOP)
   			break;
   	}
@@@@ -241,22 -285,22 -239,22 +285,22 @@@@
   			continue;
   		if (obj->type == tag_type) {
   			obj->flags |= SEEN;
- -			p = add_object(obj, p, name);
+ +			p = add_object(obj, p, NULL, name);
   			continue;
   		}
   		if (obj->type == tree_type) {
- -			p = process_tree((struct tree *)obj, p, name);
+ +			p = process_tree((struct tree *)obj, p, NULL, name);
   			continue;
   		}
   		if (obj->type == blob_type) {
- -			p = process_blob((struct blob *)obj, p, name);
+ +			p = process_blob((struct blob *)obj, p, NULL, name);
   			continue;
   		}
   		die("unknown pending object %s (%s)", sha1_to_hex(obj->sha1), name);
   	}
   	while (objects) {
 --		/* An object with name "foo\n0000000000000000000000000000000000000000"
 --		 * can be used confuse downstream git-pack-objects very badly.
 ++		/* An object with name "foo\n0000000..." can be used to
 ++		 * confuse downstream git-pack-objects very badly.
   		 */
   		const char *ep = strchr(objects->name, '\n');
   		if (ep) {
@@@@ -430,16 -474,32 -428,16 +474,32 @@@@ static struct commit_list *find_bisecti
   	return best;
   }
   
+ +static void mark_edge_parents_uninteresting(struct commit *commit)
+ +{
+ +	struct commit_list *parents;
+ +
+ +	for (parents = commit->parents; parents; parents = parents->next) {
+ +		struct commit *parent = parents->item;
+ +		if (!(parent->object.flags & UNINTERESTING))
+ +			continue;
+ +		mark_tree_uninteresting(parent->tree);
+ +		if (edge_hint && !(parent->object.flags & SHOWN)) {
+ +			parent->object.flags |= SHOWN;
+ +			printf("-%s\n", sha1_to_hex(parent->object.sha1));
+ +		}
+ +	}
+ +}
+ +
   static void mark_edges_uninteresting(struct commit_list *list)
   {
   	for ( ; list; list = list->next) {
- -		struct commit_list *parents = list->item->parents;
+ +		struct commit *commit = list->item;
   
- -		for ( ; parents; parents = parents->next) {
- -			struct commit *commit = parents->item;
- -			if (commit->object.flags & UNINTERESTING)
- -				mark_tree_uninteresting(commit->tree);
+ +		if (commit->object.flags & UNINTERESTING) {
+ +			mark_tree_uninteresting(commit->tree);
+ +			continue;
   		}
+ +		mark_edge_parents_uninteresting(commit);
   	}
   }
   
@@@@ -657,7 -717,7 -655,7 +717,7 @@@@ static struct commit_list *limit_list(s
   
   static void add_pending_object(struct object *obj, const char *name)
   {
- -	add_object(obj, &pending_objects, name);
+ +	add_object(obj, &pending_objects, NULL, name);
   }
   
   static struct commit *get_commit_reference(const char *name, const unsigned char *sha1, unsigned int flags)
@@@@ -843,6 -903,13 -841,6 +903,13 @@@@ int main(int argc, const char **argv
   			blob_objects = 1;
   			continue;
   		}
+ +		if (!strcmp(arg, "--objects-edge")) {
+ +			tag_objects = 1;
+ +			tree_objects = 1;
+ +			blob_objects = 1;
+ +			edge_hint = 1;
+ +			continue;
+ +		}
   		if (!strcmp(arg, "--unpacked")) {
   			unpacked = 1;
   			limited = 1;
@@@@ -858,13 -925,13 -856,6 +925,13 @@@@
   		}
   		if (!strcmp(arg, "--topo-order")) {
   		        topo_order = 1;
  +			lifo = 1;
  +		        limited = 1;
  +			continue;
  +		}
  +		if (!strcmp(arg, "--date-order")) {
  +		        topo_order = 1;
  +			lifo = 0;
   		        limited = 1;
   			continue;
   		}
@@@@ -949,7 -1016,7 -940,7 +1016,7 @@@@
   	        if (limited)
   			list = limit_list(list);
   		if (topo_order)
  -			sort_in_topological_order(&list);
  +			sort_in_topological_order(&list, lifo);
   		show_commit_list(list);
   	} else {
   #ifndef NO_OPENSSL
diff --combined send-pack.c
index b58bbabc15,990be3f1a3,ad22da56e9..f558386143
--- a/send-pack.c
+++ b/send-pack.c
@@@@ -12,6 -12,6 -12,7 +12,7 @@@@ static const char *exec = "git-receive-
   static int verbose = 0;
   static int send_all = 0;
   static int force_update = 0;
++ static int use_thin_pack = 0;
   
   static int is_zero_sha1(const unsigned char *sha1)
   {
@@@@ -37,44 -37,26 -38,29 +38,47 @@@@ static void exec_pack_objects(void
   
   static void exec_rev_list(struct ref *refs)
   {
 ++	struct ref *ref;
   	static char *args[1000];
 --	int i = 0;
 ++	int i = 0, j;
   
   	args[i++] = "rev-list";	/* 0 */
-- 	args[i++] = "--objects";	/* 1 */
 - 	while (refs) {
 - 		char *buf = malloc(100);
 - 		if (i > 900)
++ 	if (use_thin_pack)	/* 1 */
++ 		args[i++] = "--objects-edge";
++ 	else
++ 		args[i++] = "--objects";
  -	while (refs) {
  -		char *buf = malloc(100);
  -		if (i > 900)
 ++
 ++	/* First send the ones we care about most */
 ++	for (ref = refs; ref; ref = ref->next) {
 ++		if (900 < i)
   			die("git-rev-list environment overflow");
 --		if (!is_zero_sha1(refs->old_sha1) &&
 --		    has_sha1_file(refs->old_sha1)) {
 ++		if (!is_zero_sha1(ref->new_sha1)) {
 ++			char *buf = malloc(100);
   			args[i++] = buf;
 --			snprintf(buf, 50, "^%s", sha1_to_hex(refs->old_sha1));
 ++			snprintf(buf, 50, "%s", sha1_to_hex(ref->new_sha1));
   			buf += 50;
 ++			if (!is_zero_sha1(ref->old_sha1) &&
 ++			    has_sha1_file(ref->old_sha1)) {
 ++				args[i++] = buf;
 ++				snprintf(buf, 50, "^%s",
 ++					 sha1_to_hex(ref->old_sha1));
 ++			}
   		}
 --		if (!is_zero_sha1(refs->new_sha1)) {
 ++	}
 ++
 ++	/* Then a handful of the remainder
 ++	 * NEEDSWORK: we would be better off if used the newer ones first.
 ++	 */
 ++	for (ref = refs, j = i + 16;
 ++	     i < 900 && i < j && ref;
 ++	     ref = ref->next) {
 ++		if (is_zero_sha1(ref->new_sha1) &&
 ++		    !is_zero_sha1(ref->old_sha1) &&
 ++		    has_sha1_file(ref->old_sha1)) {
 ++			char *buf = malloc(42);
   			args[i++] = buf;
 --			snprintf(buf, 50, "%s", sha1_to_hex(refs->new_sha1));
 ++			snprintf(buf, 42, "^%s", sha1_to_hex(ref->old_sha1));
   		}
 --		refs = refs->next;
   	}
   	args[i] = NULL;
   	execv_git_cmd(args);
@@@@ -379,6 -361,6 -365,10 +383,10 @@@@ int main(int argc, char **argv
   				verbose = 1;
   				continue;
   			}
++ 			if (!strcmp(arg, "--thin")) {
++ 				use_thin_pack = 1;
++ 				continue;
++ 			}
   			usage(send_pack_usage);
   		}
   		if (!dest) {
diff --combined upload-pack.c
index 3606529f61,3606529f61,3cdf4288b8..635abb371d
--- a/upload-pack.c
+++ b/upload-pack.c
@@@@ -14,6 -14,6 -14,7 +14,7 @@@@ static const char upload_pack_usage[] 
   #define MAX_HAS 256
   #define MAX_NEEDS 256
   static int nr_has = 0, nr_needs = 0, multi_ack = 0, nr_our_refs = 0;
++ static int use_thin_pack = 0;
   static unsigned char has_sha1[MAX_HAS][20];
   static unsigned char needs_sha1[MAX_NEEDS][20];
   static unsigned int timeout = 0;
@@@@ -49,8 -49,8 -50,10 +50,10 @@@@ static void create_pack_file(void
   		char *buf;
   		char **p;
   
-- 		if (create_full_pack)
++ 		if (create_full_pack) {
   			args = 10;
++ 			use_thin_pack = 0; /* no point doing it */
++ 		}
   		else
   			args = nr_has + nr_needs + 5;
   		argv = xmalloc(args * sizeof(char *));
@@@@ -62,7 -62,7 -65,7 +65,7 @@@@
   		close(fd[0]);
   		close(fd[1]);
   		*p++ = "rev-list";
-- 		*p++ = "--objects";
++ 		*p++ = use_thin_pack ? "--objects-edge" : "--objects";
   		if (create_full_pack || MAX_NEEDS <= nr_needs)
   			*p++ = "--all";
   		else {
@@@@ -192,6 -192,6 -195,8 +195,8 @@@@ static int receive_needs(void
   			    "expected to get sha, not '%s'", line);
   		if (strstr(line+45, "multi_ack"))
   			multi_ack = 1;
++ 		if (strstr(line+45, "thin-pack"))
++ 			use_thin_pack = 1;
   
   		/* We have sent all our refs already, and the other end
   		 * should have chosen out of them; otherwise they are
@@@@ -213,12 -213,12 -218,9 +218,12 @@@@
   
   static int send_ref(const char *refname, const unsigned char *sha1)
   {
-- 	static char *capabilities = "multi_ack";
++ 	static char *capabilities = "multi_ack thin-pack";
   	struct object *o = parse_object(sha1);
   
  +	if (!o)
  +		die("git-upload-pack: cannot find object %s:", sha1_to_hex(sha1));
  +
   	if (capabilities)
   		packet_write(1, "%s %s%c%s\n", sha1_to_hex(sha1), refname,
   			0, capabilities);