From 14df4c41885ea19c9ce263111c6de994a4028601 Mon Sep 17 00:00:00 2001
From: Jim Radford <radford@blackbean.org>
Date: Thu, 10 Nov 2005 11:03:08 -0800
Subject: Add missing git-core and cvsps RPM dependencies.

Signed-off-by: Jim Radford <radford@blackbean.org>
Signed-off-by: Junio C Hamano <junkio@cox.net>
---
 git-core.spec.in | 5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)

diff --git a/git-core.spec.in b/git-core.spec.in
index 26846d0050..ce9acd8713 100644
--- a/git-core.spec.in
+++ b/git-core.spec.in
@@ -22,20 +22,21 @@ elsewhere for tools for ordinary humans layered on top of this.
 %package svn
 Summary:        Git tools for importing Subversion repositories.
 Group:          Development/Tools
-Requires:       subversion
+Requires:       git-core, subversion
 %description svn
 Git tools for importing Subversion repositories.
 
 %package cvs
 Summary:        Git tools for importing CVS repositories.
 Group:          Development/Tools
-Requires:       cvs
+Requires:       git-core, cvs, cvsps
 %description cvs
 Git tools for importing CVS repositories.
 
 %package email
 Summary:        Git tools for sending email.
 Group:          Development/Tools
+Requires:       git-core
 %description email
 Git tools for sending email.
 
-- 
cgit v1.2.3


From ad7db62113368279a1b6994790bf30925fabea33 Mon Sep 17 00:00:00 2001
From: Petr Baudis <pasky@suse.cz>
Date: Thu, 10 Nov 2005 20:55:13 +0100
Subject: Fix confusing git-update-ref error message

When git-update-ref has hit the "Ref %s changed to %s" error, I just stare
at it, left puzzled. This patch attempts to reword that to a more useful
and less confusing error message.

Signed-off-by: Petr Baudis <pasky@suse.cz>
Signed-off-by: Junio C Hamano <junkio@cox.net>
---
 update-ref.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/update-ref.c b/update-ref.c
index 65dc3d6385..d79dc52fd7 100644
--- a/update-ref.c
+++ b/update-ref.c
@@ -42,7 +42,7 @@ int main(int argc, char **argv)
 
 	if (oldval) {
 		if (memcmp(currsha1, oldsha1, 20))
-			die("Ref %s changed to %s", refname, sha1_to_hex(currsha1));
+			die("Ref %s is at %s but expected %s", refname, sha1_to_hex(currsha1), sha1_to_hex(oldsha1));
 		/* Nothing to do? */
 		if (!memcmp(oldsha1, sha1, 20))
 			exit(0);
-- 
cgit v1.2.3


From 66c9ec25553ce7332c46e2017b9c4d7c26310fff Mon Sep 17 00:00:00 2001
From: Josef Weidendorfer <Josef.Weidendorfer@gmx.de>
Date: Thu, 10 Nov 2005 14:12:19 +0100
Subject: Let git-clone/git-fetch follow HTTP redirections

Otherwise, git-clone silently failed to clone a remote
repository where redirections (ie. a response with a
"Location" header line) are used.

This includes the fixes from Nick Hengeveld.

Signed-off-by: Josef Weidendorfer <Josef.Weidendorfer@gmx.de>
Signed-off-by: Junio C Hamano <junkio@cox.net>
---
 git-clone.sh | 2 +-
 git-fetch.sh | 2 +-
 http-fetch.c | 2 ++
 3 files changed, 4 insertions(+), 2 deletions(-)

diff --git a/git-clone.sh b/git-clone.sh
index 4fdd652514..aafcc18aba 100755
--- a/git-clone.sh
+++ b/git-clone.sh
@@ -23,7 +23,7 @@ fi
 
 http_fetch () {
 	# $1 = Remote, $2 = Local
-	curl -nsf $curl_extra_args "$1" >"$2"
+	curl -nsfL $curl_extra_args "$1" >"$2"
 }
 
 clone_dumb_http () {
diff --git a/git-fetch.sh b/git-fetch.sh
index 31e5f4c722..8564cbfd7a 100755
--- a/git-fetch.sh
+++ b/git-fetch.sh
@@ -230,7 +230,7 @@ do
 	    $u =~ s{([^-a-zA-Z0-9/.])}{sprintf"%%%02x",ord($1)}eg;
 	    print "$u";
 	' "$remote_name")
-	head=$(curl -nsf $curl_extra_args "$remote/$remote_name_quoted") &&
+	head=$(curl -nsfL $curl_extra_args "$remote/$remote_name_quoted") &&
 	expr "$head" : "$_x40\$" >/dev/null ||
 		die "Failed to fetch $remote_name from $remote"
 	echo >&2 Fetching "$remote_name from $remote" using http
diff --git a/http-fetch.c b/http-fetch.c
index 88b74b4341..99921cc8da 100644
--- a/http-fetch.c
+++ b/http-fetch.c
@@ -269,6 +269,8 @@ static CURL* get_curl_handle(void)
 				 curl_low_speed_time);
 	}
 
+	curl_easy_setopt(result, CURLOPT_FOLLOWLOCATION, 1);
+
 	return result;
 }
 
-- 
cgit v1.2.3


From 605607cc622478fb2e8dfcab2ff16f54b0995599 Mon Sep 17 00:00:00 2001
From: Junio C Hamano <junkio@cox.net>
Date: Thu, 10 Nov 2005 17:46:20 -0800
Subject: Documentation: "host:path/to/repo" is git native over ssh.

You could also spell it ssh://host:/path/to/repo (or git+ssh,
ssh+git), but without method:// is shorter to type, so mention
only that one in the short and sweet list.

Noticed by Pasky.

Signed-off-by: Junio C Hamano <junkio@cox.net>
---
 Documentation/pull-fetch-param.txt | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/Documentation/pull-fetch-param.txt b/Documentation/pull-fetch-param.txt
index 5c2888e163..ddd5823df7 100644
--- a/Documentation/pull-fetch-param.txt
+++ b/Documentation/pull-fetch-param.txt
@@ -8,7 +8,7 @@
 - Rsync URL:		rsync://remote.machine/path/to/repo.git/
 - HTTP(s) URL:		http://remote.machine/path/to/repo.git/
 - git URL:		git://remote.machine/path/to/repo.git/
-			or remote.machine:/path/to/repo.git/
+- ssh URL:		remote.machine:/path/to/repo.git/
 - Local directory:	/path/to/repo.git/
 ===============================================================
 +
-- 
cgit v1.2.3


From e3e291fc07b49b74bb655ca854bdb19e849e044c Mon Sep 17 00:00:00 2001
From: Junio C Hamano <junkio@cox.net>
Date: Thu, 10 Nov 2005 23:34:08 -0800
Subject: Do not lose author name information to locale gotchas.

I noticed format-patch loses authorship information of Lukas' patch
when I run git tools with LC_LANG set to ja_JP.  It turns out that
the sed script to set environment variables were not working on his
name (encoded in UTF-8), which is unfortunate but technically correct.

Force sed invocation under C locale because we always want literal byte
semantics.

Signed-off-by: Junio C Hamano <junkio@cox.net>
---
 git-commit.sh       | 2 +-
 git-format-patch.sh | 2 +-
 git-revert.sh       | 2 +-
 3 files changed, 3 insertions(+), 3 deletions(-)

diff --git a/git-commit.sh b/git-commit.sh
index daf90f1e58..41955e8e64 100755
--- a/git-commit.sh
+++ b/git-commit.sh
@@ -184,7 +184,7 @@ then
 		}
 		'
 		set_author_env=`git-cat-file commit "$use_commit" |
-		sed -ne "$pick_author_script"`
+		LANG=C LC_ALL=C sed -ne "$pick_author_script"`
 		eval "$set_author_env"
 		export GIT_AUTHOR_NAME
 		export GIT_AUTHOR_EMAIL
diff --git a/git-format-patch.sh b/git-format-patch.sh
index 548d2d5847..7ee5d328c0 100755
--- a/git-format-patch.sh
+++ b/git-format-patch.sh
@@ -201,7 +201,7 @@ process_one () {
 	    ;;
 	esac
 
-	eval "$(sed -ne "$whosepatchScript" $commsg)"
+	eval "$(LANG=C LC_ALL=C sed -ne "$whosepatchScript" $commsg)"
 	test "$author,$au" = ",$me" || {
 		mailScript="$mailScript"'
 	a\
diff --git a/git-revert.sh b/git-revert.sh
index dfd914cf56..4154fe0d15 100755
--- a/git-revert.sh
+++ b/git-revert.sh
@@ -112,7 +112,7 @@ cherry-pick)
 		q
 	}'
 	set_author_env=`git-cat-file commit "$commit" |
-	sed -ne "$pick_author_script"`
+	LANG=C LC_ALL=C sed -ne "$pick_author_script"`
 	eval "$set_author_env"
 	export GIT_AUTHOR_NAME
 	export GIT_AUTHOR_EMAIL
-- 
cgit v1.2.3


From ff56fe1ca7f43087fd84588af87179c2959d0cb3 Mon Sep 17 00:00:00 2001
From: Junio C Hamano <junkio@cox.net>
Date: Wed, 9 Nov 2005 22:15:27 -0800
Subject: Add --pretty=fuller

git log without --pretty showed author and author-date, while
with --pretty=full showed author and committer but no dates.
The new formatting option, --pretty=fuller, shows both name and
timestamp for author and committer.

Signed-off-by: Junio C Hamano <junkio@cox.net>
---
 commit.c | 37 ++++++++++++++++++++++++++++++-------
 commit.h |  1 +
 2 files changed, 31 insertions(+), 7 deletions(-)

diff --git a/commit.c b/commit.c
index a8c9bfc8ba..534c03ea59 100644
--- a/commit.c
+++ b/commit.c
@@ -34,6 +34,8 @@ enum cmit_fmt get_commit_format(const char *arg)
 		return CMIT_FMT_SHORT;
 	if (!strcmp(arg, "=full"))
 		return CMIT_FMT_FULL;
+	if (!strcmp(arg, "=fuller"))
+		return CMIT_FMT_FULLER;
 	if (!strcmp(arg, "=oneline"))
 		return CMIT_FMT_ONELINE;
 	die("invalid --pretty format");
@@ -361,6 +363,7 @@ static int add_user_info(const char *what, enum cmit_fmt fmt, char *buf, const c
 	int namelen;
 	unsigned long time;
 	int tz, ret;
+	const char *filler = "    ";
 
 	if (fmt == CMIT_FMT_ONELINE)
 		return 0;
@@ -371,9 +374,20 @@ static int add_user_info(const char *what, enum cmit_fmt fmt, char *buf, const c
 	time = strtoul(date, &date, 10);
 	tz = strtol(date, NULL, 10);
 
-	ret = sprintf(buf, "%s: %.*s\n", what, namelen, line);
-	if (fmt == CMIT_FMT_MEDIUM)
+	ret = sprintf(buf, "%s: %.*s%.*s\n", what,
+		      (fmt == CMIT_FMT_FULLER) ? 4 : 0,
+		      filler, namelen, line);
+	switch (fmt) {
+	case CMIT_FMT_MEDIUM:
 		ret += sprintf(buf + ret, "Date:   %s\n", show_date(time, tz));
+		break;
+	case CMIT_FMT_FULLER:
+		ret += sprintf(buf + ret, "%sDate: %s\n", what, show_date(time, tz));
+		break;
+	default:
+		/* notin' */
+		break;
+	}
 	return ret;
 }
 
@@ -448,12 +462,21 @@ unsigned long pretty_print_commit(enum cmit_fmt fmt, const char *msg, unsigned l
 					die("bad parent line in commit");
 				offset += add_parent_info(fmt, buf + offset, line, ++parents);
 			}
+
+			/*
+			 * MEDIUM == DEFAULT shows only author with dates.
+			 * FULL shows both authors but not dates.
+			 * FULLER shows both authors and dates.
+			 */
 			if (!memcmp(line, "author ", 7))
-				offset += add_user_info("Author", fmt, buf + offset, line + 7);
-			if (fmt == CMIT_FMT_FULL) {
-				if (!memcmp(line, "committer ", 10))
-					offset += add_user_info("Commit", fmt, buf + offset, line + 10);
-			}
+				offset += add_user_info("Author", fmt,
+							buf + offset,
+							line + 7);
+			if (!memcmp(line, "committer ", 10) &&
+			    (fmt == CMIT_FMT_FULL || fmt == CMIT_FMT_FULLER))
+				offset += add_user_info("Commit", fmt,
+							buf + offset,
+							line + 10);
 			continue;
 		}
 
diff --git a/commit.h b/commit.h
index 30702ca937..6738a696d7 100644
--- a/commit.h
+++ b/commit.h
@@ -43,6 +43,7 @@ enum cmit_fmt {
 	CMIT_FMT_DEFAULT = CMIT_FMT_MEDIUM,
 	CMIT_FMT_SHORT,
 	CMIT_FMT_FULL,
+	CMIT_FMT_FULLER,
 	CMIT_FMT_ONELINE,
 };
 
-- 
cgit v1.2.3


From 17cf939724a244a56e687559fae062a3e6207145 Mon Sep 17 00:00:00 2001
From: Junio C Hamano <junkio@cox.net>
Date: Wed, 9 Nov 2005 22:37:14 -0800
Subject: octopus: do not do AND'ed merge base.

When doing an octopus, we incorrectly used the previous merge
base as the reference to compute next merge base.  This was
unnecessary, because that can never be better than using the
original HEAD.  And that is far simpler as well ;-).

Signed-off-by: Junio C Hamano <junkio@cox.net>
---
 git-merge-octopus.sh | 25 ++++++++++++++++++++-----
 1 file changed, 20 insertions(+), 5 deletions(-)

diff --git a/git-merge-octopus.sh b/git-merge-octopus.sh
index aa1cd2f106..bb58e22a18 100755
--- a/git-merge-octopus.sh
+++ b/git-merge-octopus.sh
@@ -5,6 +5,9 @@
 # Resolve two or more trees.
 #
 
+LF='
+'
+
 # The first parameters up to -- are merge bases; the rest are heads.
 bases= head= remotes= sep_seen=
 for arg
@@ -42,14 +45,18 @@ CNT=1 ;# counting our head
 NON_FF_MERGE=0
 for SHA1 in $remotes
 do
-	common=$(git-merge-base $MRC $SHA1) ||
+	common=$(git-merge-base --all $MRC $SHA1) ||
 		die "Unable to find common commit with $SHA1"
 
-	if test "$common" = $SHA1
-	then
+	case "$common" in
+	?*"$LF"?*)
+		die "Not trivially mergeable."
+		;;
+	$SHA1)
 		echo "Already up-to-date with $SHA1"
 		continue
-	fi
+		;;
+	esac
 
 	CNT=`expr $CNT + 1`
 	PARENT="$PARENT -p $SHA1"
@@ -79,7 +86,15 @@ do
 		exit 2 ; # Automatic merge failed; should not be doing Octopus
 		next=$(git-write-tree 2>/dev/null)
 	fi
-	MRC=$common
+
+	# We have merged the other branch successfully.  Ideally
+	# we could implement OR'ed heads in merge-base, and keep
+	# a list of commits we have merged so far in MRC to feed
+	# them to merge-base, but we approximate it by keep using
+	# the current MRC.  We used to update it to $common, which
+	# was incorrectly doing AND'ed merge-base here, which was
+	# unneeded.
+
 	MRT=$next
 done
 
-- 
cgit v1.2.3


From 601c978c1bc9f6742c18932cb9d4a6910934f785 Mon Sep 17 00:00:00 2001
From: Pavel Roskin <proski@gnu.org>
Date: Thu, 10 Nov 2005 00:30:12 -0500
Subject: Add --no-commit-id option for git-diff-tree, use it in gitk

This patch introduces -no-commit-id option for git-diff-tree, which
suppresses commit ID output.

[jc: dropped gitk part for now.]

Signed-off-by: Pavel Roskin <proski@gnu.org>
Signed-off-by: Junio C Hamano <junkio@cox.net>
---
 Documentation/git-diff-tree.txt | 6 +++++-
 diff-tree.c                     | 8 +++++++-
 2 files changed, 12 insertions(+), 2 deletions(-)

diff --git a/Documentation/git-diff-tree.txt b/Documentation/git-diff-tree.txt
index f57c8d0d81..9a2947e27d 100644
--- a/Documentation/git-diff-tree.txt
+++ b/Documentation/git-diff-tree.txt
@@ -8,7 +8,7 @@ git-diff-tree - Compares the content and mode of blobs found via two tree object
 
 SYNOPSIS
 --------
-'git-diff-tree' [--stdin] [-m] [-s] [-v] [--pretty] [-t] [-r] [--root] [<common diff options>] <tree-ish> [<tree-ish>] [<path>...]
+'git-diff-tree' [--stdin] [-m] [-s] [-v] [--no-commit-id] [--pretty] [-t] [-r] [--root] [<common diff options>] <tree-ish> [<tree-ish>] [<path>...]
 
 DESCRIPTION
 -----------
@@ -74,6 +74,10 @@ separated with a single space are given.
 	commit message.  Without "=<style>", it defaults to
 	medium.
 
+--no-commit-id::
+	git-diff-tree outputs a line with the commit ID when
+	applicable.  This flag suppressed the commit ID output.
+
 
 Limiting Output
 ---------------
diff --git a/diff-tree.c b/diff-tree.c
index ed323d877c..09d16ad661 100644
--- a/diff-tree.c
+++ b/diff-tree.c
@@ -3,6 +3,7 @@
 #include "commit.h"
 
 static int show_root_diff = 0;
+static int no_commit_id = 0;
 static int verbose_header = 0;
 static int ignore_merges = 1;
 static int read_stdin = 0;
@@ -29,7 +30,8 @@ static int call_diff_flush(void)
 		return 0;
 	}
 	if (header) {
-		printf("%s%c", header, diff_options.line_termination);
+		if (!no_commit_id)
+			printf("%s%c", header, diff_options.line_termination);
 		header = NULL;
 	}
 	diff_flush(&diff_options);
@@ -231,6 +233,10 @@ int main(int argc, const char **argv)
 			show_root_diff = 1;
 			continue;
 		}
+		if (!strcmp(arg, "--no-commit-id")) {
+			no_commit_id = 1;
+			continue;
+		}
 		usage(diff_tree_usage);
 	}
 	if (diff_options.output_format == DIFF_FORMAT_PATCH)
-- 
cgit v1.2.3


From 0e9ab02da77fcf59fdb7d8201d3c5546cd346e63 Mon Sep 17 00:00:00 2001
From: Pavel Roskin <proski@gnu.org>
Date: Fri, 11 Nov 2005 00:19:04 -0500
Subject: git-clone: quote destination directory name

git-clone doesn't quote the full path to the destination directory,
which causes it to fail if the path contains spaces or other characters
interpreted by the shell.

[jc: obviously I was not careful enough.  Pavel, thanks for catching.]

Signed-off-by: Pavel Roskin <proski@gnu.org>
Signed-off-by: Junio C Hamano <junkio@cox.net>
---
 git-clone.sh | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/git-clone.sh b/git-clone.sh
index aafcc18aba..f5ef70b8af 100755
--- a/git-clone.sh
+++ b/git-clone.sh
@@ -163,7 +163,7 @@ yes,yes)
 			rm -f "$D/.git/TMP_ALT"
 		if test -f "$D/.git/TMP_ALT"
 		then
-		    ( cd $D &&
+		    ( cd "$D" &&
 		      . git-parse-remote &&
 		      resolve_alternates "$repo" <"./.git/TMP_ALT" ) |
 		    while read alt
@@ -191,7 +191,7 @@ yes,yes)
 	;;
 esac
 
-cd $D || exit
+cd "$D" || exit
 
 if test -f ".git/HEAD"
 then
-- 
cgit v1.2.3


From f84f9d38ebd809ecab89d2d4926c3ff6bc3c60f5 Mon Sep 17 00:00:00 2001
From: Martin Langhoff <martin@catalyst.net.nz>
Date: Fri, 11 Nov 2005 18:00:57 +1300
Subject: archimport: handle pika escaping

Arch uses pika escaping in some places (but not all!). Specifically, commits of
the type 'patch' use pika escaping in the log entries, which we parse to know
what to add/delete and what to commit.

This patch checks for hints of pika escaping and asks tla to unescape for us.

Originally implemented by Penny Leach <penny@catalyst.net.nz>

Signed-off-by: Martin Langhoff <martin@catalyst.net.nz>
Signed-off-by: Junio C Hamano <junkio@cox.net>
---
 git-archimport.perl | 5 +++++
 1 file changed, 5 insertions(+)

diff --git a/git-archimport.perl b/git-archimport.perl
index 980e827b27..e22c81628d 100755
--- a/git-archimport.perl
+++ b/git-archimport.perl
@@ -565,6 +565,11 @@ sub parselog {
             next if $t =~ m!\{arch\}/!;
             next if $t =~ m!\.arch-ids/!;
             next if $t =~ m!\.arch-inventory$!;
+           # tla cat-archive-log will give us filenames with spaces as file\(sp)name - why?
+           # we can assume that any filename with \ indicates some pika escaping that we want to get rid of.
+           if  ($t =~ /\\/ ){
+               $t = `tla escape --unescaped '$t'`;
+           }
             push (@tmp, shell_quote($t));
         }
         @$ref = @tmp;
-- 
cgit v1.2.3


From 0867b0125a7b0ed02c7850486393c56ae8a719e3 Mon Sep 17 00:00:00 2001
From: Chris Wright <chrisw@osdl.org>
Date: Fri, 11 Nov 2005 01:10:29 -0800
Subject: specfile cleanups

Some specfile cleanups after the split.
- zlib dependency fix, current method is inconsistent, you can
  potentially build a package that you can't install on machine you
  built it on
- Add proper defattr
- Remove trailing '.' in summary
- Add docs to split up packages
- Add git-core dependency for each subpackage
- Move arch import to separate package as well

Signed-off-by: Chris Wright <chrisw@osdl.org>
Signed-off-by: Junio C Hamano <junkio@cox.net>
---
 git-core.spec.in | 50 +++++++++++++++++++++++++++++++++++++++-----------
 1 file changed, 39 insertions(+), 11 deletions(-)

diff --git a/git-core.spec.in b/git-core.spec.in
index ce9acd8713..cf7e94232a 100644
--- a/git-core.spec.in
+++ b/git-core.spec.in
@@ -1,4 +1,4 @@
-# Pass --without docs to rpmbuild if you don't want the documetnation
+# Pass --without docs to rpmbuild if you don't want the documentation
 Name: 		git-core
 Version: 	@@VERSION@@
 Release: 	1%{?dist}
@@ -7,7 +7,7 @@ License: 	GPL
 Group: 		Development/Tools
 URL: 		http://kernel.org/pub/software/scm/git/
 Source: 	http://kernel.org/pub/software/scm/git/%{name}-%{version}.tar.gz
-BuildRequires:	zlib-devel, openssl-devel, curl-devel  %{!?_without_docs:, xmlto, asciidoc > 6.0.3}
+BuildRequires:	zlib-devel >= 1.2, openssl-devel, curl-devel  %{!?_without_docs:, xmlto, asciidoc > 6.0.3}
 BuildRoot:	%{_tmppath}/%{name}-%{version}-%{release}-root-%(%{__id_u} -n)
 Requires:	zlib >= 1.2, rsync, rcs, curl, less, openssh-clients, python >= 2.3, tk >= 8.4
 
@@ -20,23 +20,30 @@ rudimentary tools that can be used as a SCM, but you should look
 elsewhere for tools for ordinary humans layered on top of this.
 
 %package svn
-Summary:        Git tools for importing Subversion repositories.
+Summary:        Git tools for importing Subversion repositories
 Group:          Development/Tools
-Requires:       git-core, subversion
+Requires:       git-core = %{version}-%{release}, subversion
 %description svn
 Git tools for importing Subversion repositories.
 
 %package cvs
-Summary:        Git tools for importing CVS repositories.
+Summary:        Git tools for importing CVS repositories
 Group:          Development/Tools
-Requires:       git-core, cvs, cvsps
+Requires:       git-core = %{version}-%{release}, cvs, cvsps
 %description cvs
 Git tools for importing CVS repositories.
 
+%package arch
+Summary:        Git tools for importing Arch repositories
+Group:          Development/Tools
+Requires:       git-core = %{version}-%{release}
+%description arch
+Git tools for importing Arch repositories.
+
 %package email
-Summary:        Git tools for sending email.
+Summary:        Git tools for sending email
 Group:          Development/Tools
-Requires:       git-core
+Requires:	git-core = %{version}-%{release} 
 %description email
 Git tools for sending email.
 
@@ -53,33 +60,54 @@ make %{_smp_mflags} DESTDIR=$RPM_BUILD_ROOT WITH_OWN_SUBPROCESS_PY=YesPlease WIT
      prefix=%{_prefix} mandir=%{_mandir} \
      install %{!?_without_docs: install-doc}
 
-(find $RPM_BUILD_ROOT%{_bindir} -type f | grep -vE "svn|cvs|email" | sed -e s@^$RPM_BUILD_ROOT@@)               > bin-man-files
+(find $RPM_BUILD_ROOT%{_bindir} -type f | grep -vE "arch|svn|cvs|email" | sed -e s@^$RPM_BUILD_ROOT@@)               > bin-man-doc-files
 %if %{!?_without_docs:1}0
-(find $RPM_BUILD_ROOT%{_mandir} -type f | grep -vE "svn|cvs|email" | sed -e s@^$RPM_BUILD_ROOT@@ -e 's/$/*/' ) >> bin-man-files
+(find $RPM_BUILD_ROOT%{_mandir} $RPM_BUILD_ROOT/Documentation -type f | grep -vE "arch|svn|git-cvs|email" | sed -e s@^$RPM_BUILD_ROOT@@ -e 's/$/*/' ) >> bin-man-doc-files
 %endif
 
 %clean
 rm -rf $RPM_BUILD_ROOT
 
 %files svn
+%defattr(-,root,root)
 %{_bindir}/*svn*
+%doc Documentation/*svn*.txt
 %{!?_without_docs: %{_mandir}/man1/*svn*.1*}
+%{!?_without_docs: %doc Documentation/*svn*.html }
 
 %files cvs
+%defattr(-,root,root)
+%doc Documentation/*git-cvs*.txt
 %{_bindir}/*cvs*
 %{!?_without_docs: %{_mandir}/man1/*cvs*.1*}
+%{!?_without_docs: %doc Documentation/*git-cvs*.html }
+
+%files arch
+%defattr(-,root,root)
+%doc Documentation/*arch*.txt
+%{_bindir}/*arch*
+%{!?_without_docs: %{_mandir}/man1/*arch*.1*}
+%{!?_without_docs: %doc Documentation/*arch*.html }
 
 %files email
+%defattr(-,root,root)
+%doc Documentation/*email*.txt
 %{_bindir}/*email*
 %{!?_without_docs: %{_mandir}/man1/*email*.1*}
+%{!?_without_docs: %doc Documentation/*email*.html }
 
-%files -f bin-man-files
+%files -f bin-man-doc-files
 %defattr(-,root,root)
 %{_datadir}/git-core/
 %doc README COPYING Documentation/*.txt
 %{!?_without_docs: %doc Documentation/*.html }
 
 %changelog
+* Thu Nov 10 2005 Chris Wright <chrisw@osdl.org> 0.99.9g-1
+- zlib dependency fix
+- Minor cleanups from split
+- Move arch import to separate package as well
+
 * Tue Sep 27 2005 Jim Radford <radford@blackbean.org>
 - Move programs with non-standard dependencies (svn, cvs, email)
   into separate packages
-- 
cgit v1.2.3


From 0879aa28708dcdfa255fff631781e5178755498e Mon Sep 17 00:00:00 2001
From: Andreas Ericsson <exon@op5.se>
Date: Thu, 10 Nov 2005 12:58:08 +0100
Subject: git-clone: Keep remote names when cloning unless explicitly told not
 to.

With this patch the following commands all clone into the local directory
"repo". If repo exists, it will still barf.

	git-clone git://host.xz/repo.git
	git-clone /path/to/repo/.git
	git-clone host.xz:repo.git

I ended up doing the same source-to-target sed'ing for all our company
projects, so it was easier to add it directly to git-clone.

Signed-off-by: Andreas Ericsson <ae@op5.se>
Signed-off-by: Junio C Hamano <junkio@cox.net>
---
 Documentation/git-clone.txt | 12 +++++++-----
 git-clone.sh                |  2 ++
 2 files changed, 9 insertions(+), 5 deletions(-)

diff --git a/Documentation/git-clone.txt b/Documentation/git-clone.txt
index fefd2985f3..83f58ae536 100644
--- a/Documentation/git-clone.txt
+++ b/Documentation/git-clone.txt
@@ -8,7 +8,7 @@ git-clone - Clones a repository.
 
 SYNOPSIS
 --------
-'git-clone' [-l [-s]] [-q] [-n] [-u <upload-pack>] <repository> <directory>
+'git-clone' [-l [-s]] [-q] [-n] [-u <upload-pack>] <repository> [<directory>]
 
 DESCRIPTION
 -----------
@@ -68,9 +68,11 @@ OPTIONS
 	be any URL git-fetch supports.
 
 <directory>::
-	The name of a new directory to be cloned into.  It is an
-	error to specify an existing directory.
-
+	The name of a new directory to clone into.  The	"humanish"
+	part of the source repository is used if no directory is
+	explicitly given ("repo" for "/path/to/repo.git" and "foo"
+	for "host.xz:foo/.git").  Cloning into an existing directory
+	is not allowed.
 
 Author
 ------
@@ -78,7 +80,7 @@ Written by Linus Torvalds <torvalds@osdl.org>
 
 Documentation
 --------------
-Documentation by Junio C Hamano.
+Documentation by Junio C Hamano and the git-list <git@vger.kernel.org>.
 
 
 GIT
diff --git a/git-clone.sh b/git-clone.sh
index f5ef70b8af..8e7150127a 100755
--- a/git-clone.sh
+++ b/git-clone.sh
@@ -96,6 +96,8 @@ if base=$(get_repo_base "$repo"); then
 fi
 
 dir="$2"
+# Try using "humanish" part of source repo if user didn't specify one
+[ -z "$dir" ] && dir=$(echo "$repo" | sed -e 's|/$||' -e 's|:*/*\.git$||' -e 's|.*/||g')
 mkdir "$dir" &&
 D=$(
 	(cd "$dir" && git-init-db && pwd)
-- 
cgit v1.2.3


From 7f10f7c4e4943fefbc8b8310d1d1d7753f5e3aff Mon Sep 17 00:00:00 2001
From: Andreas Ericsson <exon@op5.se>
Date: Thu, 10 Nov 2005 12:58:08 +0100
Subject: git-clone: Allow cloning into directories other than child of current
 dir.

This patch adds -p to mkdir and an explicit check to see if the target
directory exists (since mkdir -p doesn't throw an error if it does).

Signed-off-by: Andreas Ericsson <ae@op5.se>
Signed-off-by: Junio C Hamano <junkio@cox.net>
---
 git-clone.sh | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/git-clone.sh b/git-clone.sh
index 8e7150127a..f99e0adf86 100755
--- a/git-clone.sh
+++ b/git-clone.sh
@@ -98,7 +98,8 @@ fi
 dir="$2"
 # Try using "humanish" part of source repo if user didn't specify one
 [ -z "$dir" ] && dir=$(echo "$repo" | sed -e 's|/$||' -e 's|:*/*\.git$||' -e 's|.*/||g')
-mkdir "$dir" &&
+[ -e "$dir" ] && $(echo "$dir already exists."; usage)
+mkdir -p "$dir" &&
 D=$(
 	(cd "$dir" && git-init-db && pwd)
 ) &&
-- 
cgit v1.2.3


From 592ee97d8fffa2318960074057e044709163abf7 Mon Sep 17 00:00:00 2001
From: Junio C Hamano <junkio@cox.net>
Date: Fri, 11 Nov 2005 09:31:38 -0800
Subject: RPM: arch submodule needs tla.

Noticed by Horst von Brand.

Signed-off-by: Junio C Hamano <junkio@cox.net>
---
 git-core.spec.in | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/git-core.spec.in b/git-core.spec.in
index cf7e94232a..6a482ad1f1 100644
--- a/git-core.spec.in
+++ b/git-core.spec.in
@@ -36,7 +36,7 @@ Git tools for importing CVS repositories.
 %package arch
 Summary:        Git tools for importing Arch repositories
 Group:          Development/Tools
-Requires:       git-core = %{version}-%{release}
+Requires:       git-core = %{version}-%{release}, tla
 %description arch
 Git tools for importing Arch repositories.
 
-- 
cgit v1.2.3


From ed9a540b2b351ea305e26bb0d9028f21c976b67c Mon Sep 17 00:00:00 2001
From: Junio C Hamano <junkio@cox.net>
Date: Thu, 10 Nov 2005 17:21:54 -0800
Subject: merge-base: fully contaminate the well.

The discussion on the list demonstrated a pathological case where
an ancestor of a merge-base can be left interesting.  This commit
introduces a postprocessing phase to fix it.

Signed-off-by: Junio C Hamano <junkio@cox.net>
---
 merge-base.c | 78 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 77 insertions(+), 1 deletion(-)

diff --git a/merge-base.c b/merge-base.c
index 286bf0e8d1..43a6818369 100644
--- a/merge-base.c
+++ b/merge-base.c
@@ -80,6 +80,45 @@ static struct commit *interesting(struct commit_list *list)
  * Now, list does not have any interesting commit.  So we find the newest
  * commit from the result list that is not marked uninteresting.  Which is
  * commit B.
+ *
+ *
+ * Another pathological example how this thing can fail to mark an ancestor
+ * of a merge base as UNINTERESTING without the postprocessing phase.
+ *
+ *		  2
+ *		  H
+ *	    1    / \
+ *	    G   A   \
+ *	    |\ /     \ 
+ *	    | B       \
+ *	    |  \       \
+ *	     \  C       F
+ *	      \  \     / 
+ *	       \  D   /   
+ *		\ |  /
+ *		 \| /
+ *		  E
+ *
+ *	 list			A B C D E F G H
+ *	 G1 H2			- - - - - - 1 2
+ *	 H2 E1 B1		- 1 - - 1 - 1 2
+ *	 F2 E1 B1 A2		2 1 - - 1 2 1 2
+ *	 E3 B1 A2		2 1 - - 3 2 1 2
+ *	 B1 A2			2 1 - - 3 2 1 2
+ *	 C1 A2			2 1 1 - 3 2 1 2
+ *	 D1 A2			2 1 1 1 3 2 1 2
+ *	 A2			2 1 1 1 3 2 1 2
+ *	 B3			2 3 1 1 3 2 1 2
+ *	 C7			2 3 7 1 3 2 1 2
+ *
+ * At this point, unfortunately, everybody in the list is
+ * uninteresting, so we fail to complete the following two
+ * steps to fully marking uninteresting commits.
+ *
+ *	 D7			2 3 7 7 3 2 1 2
+ *	 E7			2 3 7 7 7 2 1 2
+ *
+ * and we end up showing E as an interesting merge base.
  */
 
 static int show_all = 0;
@@ -88,6 +127,7 @@ static int merge_base(struct commit *rev1, struct commit *rev2)
 {
 	struct commit_list *list = NULL;
 	struct commit_list *result = NULL;
+	struct commit_list *tmp = NULL;
 
 	if (rev1 == rev2) {
 		printf("%s\n", sha1_to_hex(rev1->object.sha1));
@@ -104,9 +144,10 @@ static int merge_base(struct commit *rev1, struct commit *rev2)
 
 	while (interesting(list)) {
 		struct commit *commit = list->item;
-		struct commit_list *tmp = list, *parents;
+		struct commit_list *parents;
 		int flags = commit->object.flags & 7;
 
+		tmp = list;
 		list = list->next;
 		free(tmp);
 		if (flags == 3) {
@@ -130,6 +171,41 @@ static int merge_base(struct commit *rev1, struct commit *rev2)
 	if (!result)
 		return 1;
 
+	/*
+	 * Postprocess to fully contaminate the well.
+	 */
+	for (tmp = result; tmp; tmp = tmp->next) {
+		struct commit *c = tmp->item;
+		/* Reinject uninteresting ones to list,
+		 * so we can scan their parents.
+		 */
+		if (c->object.flags & UNINTERESTING)
+			commit_list_insert(c, &list);
+	}
+	while (list) {
+		struct commit *c = list->item;
+		struct commit_list *parents;
+
+		tmp = list;
+		list = list->next;
+		free(tmp);
+
+		/* Anything taken out of the list is uninteresting, so
+		 * mark all its parents uninteresting.  We do not
+		 * parse new ones (we already parsed all the relevant
+		 * ones).
+		 */
+		parents = c->parents;
+		while (parents) {
+			struct commit *p = parents->item;
+			parents = parents->next;
+			if (!(p->object.flags & UNINTERESTING)) {
+				p->object.flags |= UNINTERESTING;
+				commit_list_insert(p, &list);
+			}
+		}
+	}
+
 	while (result) {
 		struct commit *commit = result->item;
 		result = result->next;
-- 
cgit v1.2.3


From 9e5f4a5539fe0e6ed31f26f34f1832a729facf4b Mon Sep 17 00:00:00 2001
From: Junio C Hamano <junkio@cox.net>
Date: Thu, 10 Nov 2005 22:41:44 -0800
Subject: merge-base: avoid unnecessary postprocessing.

When we have only one merge-base candidates in the result list,
there is no point going back to mark the reachable commits
again.  And that is the most common case, so try not to waste
time on it.  Suggested by Linus.

Signed-off-by: Junio C Hamano <junkio@cox.net>
---
 merge-base.c | 77 +++++++++++++++++++++++++++++++++---------------------------
 1 file changed, 43 insertions(+), 34 deletions(-)

diff --git a/merge-base.c b/merge-base.c
index 43a6818369..751c3c281b 100644
--- a/merge-base.c
+++ b/merge-base.c
@@ -123,6 +123,47 @@ static struct commit *interesting(struct commit_list *list)
 
 static int show_all = 0;
 
+static void mark_reachable_commits(struct commit_list *result,
+				   struct commit_list *list)
+{
+	struct commit_list *tmp;
+
+	/*
+	 * Postprocess to fully contaminate the well.
+	 */
+	for (tmp = result; tmp; tmp = tmp->next) {
+		struct commit *c = tmp->item;
+		/* Reinject uninteresting ones to list,
+		 * so we can scan their parents.
+		 */
+		if (c->object.flags & UNINTERESTING)
+			commit_list_insert(c, &list);
+	}
+	while (list) {
+		struct commit *c = list->item;
+		struct commit_list *parents;
+
+		tmp = list;
+		list = list->next;
+		free(tmp);
+
+		/* Anything taken out of the list is uninteresting, so
+		 * mark all its parents uninteresting.  We do not
+		 * parse new ones (we already parsed all the relevant
+		 * ones).
+		 */
+		parents = c->parents;
+		while (parents) {
+			struct commit *p = parents->item;
+			parents = parents->next;
+			if (!(p->object.flags & UNINTERESTING)) {
+				p->object.flags |= UNINTERESTING;
+				commit_list_insert(p, &list);
+			}
+		}
+	}
+}
+
 static int merge_base(struct commit *rev1, struct commit *rev2)
 {
 	struct commit_list *list = NULL;
@@ -171,40 +212,8 @@ static int merge_base(struct commit *rev1, struct commit *rev2)
 	if (!result)
 		return 1;
 
-	/*
-	 * Postprocess to fully contaminate the well.
-	 */
-	for (tmp = result; tmp; tmp = tmp->next) {
-		struct commit *c = tmp->item;
-		/* Reinject uninteresting ones to list,
-		 * so we can scan their parents.
-		 */
-		if (c->object.flags & UNINTERESTING)
-			commit_list_insert(c, &list);
-	}
-	while (list) {
-		struct commit *c = list->item;
-		struct commit_list *parents;
-
-		tmp = list;
-		list = list->next;
-		free(tmp);
-
-		/* Anything taken out of the list is uninteresting, so
-		 * mark all its parents uninteresting.  We do not
-		 * parse new ones (we already parsed all the relevant
-		 * ones).
-		 */
-		parents = c->parents;
-		while (parents) {
-			struct commit *p = parents->item;
-			parents = parents->next;
-			if (!(p->object.flags & UNINTERESTING)) {
-				p->object.flags |= UNINTERESTING;
-				commit_list_insert(p, &list);
-			}
-		}
-	}
+	if (result->next && list)
+		mark_reachable_commits(result, list);
 
 	while (result) {
 		struct commit *commit = result->item;
-- 
cgit v1.2.3


From 53de71f88b0d5a55892c19b412688548f5797f0b Mon Sep 17 00:00:00 2001
From: Junio C Hamano <junkio@cox.net>
Date: Fri, 11 Nov 2005 01:00:52 -0800
Subject: Add test case for merge-base.

Although it was shown that the "full contamination" was not really full
during the list discussion, the series improves things without incurring
extra parsing cost, and here is a test to check that.

Signed-off-by: Junio C Hamano <junkio@cox.net>
---
 t/t6010-merge-base.sh | 59 +++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 59 insertions(+)
 create mode 100755 t/t6010-merge-base.sh

diff --git a/t/t6010-merge-base.sh b/t/t6010-merge-base.sh
new file mode 100755
index 0000000000..c3a9680e2e
--- /dev/null
+++ b/t/t6010-merge-base.sh
@@ -0,0 +1,59 @@
+#!/bin/sh
+#
+# Copyright (c) 2005 Junio C Hamano
+#
+
+test_description='Merge base computation.
+'
+
+. ./test-lib.sh
+
+T=$(git-write-tree)
+
+M=1130000000
+Z=+0000
+
+export GIT_COMMITTER_EMAIL=git@comm.iter.xz
+export GIT_COMMITTER_NAME='C O Mmiter'
+export GIT_AUTHOR_NAME='A U Thor'
+export GIT_AUTHOR_EMAIL=git@au.thor.xz
+
+doit() {
+	OFFSET=$1; shift
+	NAME=$1; shift
+	PARENTS=
+	for P
+	do
+		PARENTS="${PARENTS}-p $P "
+	done
+	GIT_COMMITTER_DATE="$(($M + $OFFSET)) $Z"
+	GIT_AUTHOR_DATE=$GIT_COMMITTER_DATE
+	export GIT_COMMITTER_DATE GIT_AUTHOR_DATE
+	commit=$(echo $NAME | git-commit-tree $T $PARENTS)
+	echo $commit >.git/refs/tags/$NAME
+	echo $commit
+}
+
+# Setup...
+E=$(doit 5 E)
+D=$(doit 4 D $E)
+F=$(doit 6 F $E)
+C=$(doit 3 C $D)
+B=$(doit 2 B $C)
+A=$(doit 1 A $B)
+G=$(doit 7 G $B $E)
+H=$(doit 8 H $A $F)
+
+test_expect_success 'compute merge-base (single)' \
+    'MB=$(git-merge-base G H) &&
+     expr "$(git-name-rev "$MB")" : "[0-9a-f]* B"'
+
+test_expect_success 'compute merge-base (all)' \
+    'MB=$(git-merge-base --all G H) &&
+     expr "$(git-name-rev "$MB")" : "[0-9a-f]* B"'
+
+test_expect_success 'compute merge-base with show-branch' \
+    'MB=$(git-show-branch --merge-base G H) &&
+     expr "$(git-name-rev "$MB")" : "[0-9a-f]* B"'
+
+test_done
-- 
cgit v1.2.3


From 9ce7028531fd7ce1ca8d75a5c4f9a941ef79c9d4 Mon Sep 17 00:00:00 2001
From: Junio C Hamano <junkio@cox.net>
Date: Wed, 9 Nov 2005 23:36:15 -0800
Subject: git-show-branch: tighten merge-base computation.

This makes the merge-base computation resistant to the pathological
case discussed on the list earlier, by doing the same logic as
git-merge-base.  As a side effect, it breaks the command's primary
function to list non-merge commit sequences, which needs to be fixed
separately.

Signed-off-by: Junio C Hamano <junkio@cox.net>
---
 show-branch.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/show-branch.c b/show-branch.c
index 70120005be..714e7f8ca3 100644
--- a/show-branch.c
+++ b/show-branch.c
@@ -181,11 +181,11 @@ static void join_revs(struct commit_list **list_p,
 
 	while (*list_p) {
 		struct commit_list *parents;
+		int still_interesting = !!interesting(*list_p);
 		struct commit *commit = pop_one_commit(list_p);
 		int flags = commit->object.flags & all_mask;
-		int still_interesting = !!interesting(*list_p);
 
-		if (!still_interesting && extra < 0)
+		if (!still_interesting && extra <= 0)
 			break;
 
 		mark_seen(commit, seen_p);
-- 
cgit v1.2.3


From 6b209d473378cc25708ab9839d0edd493afc1e8f Mon Sep 17 00:00:00 2001
From: Junio C Hamano <junkio@cox.net>
Date: Thu, 10 Nov 2005 15:47:58 -0800
Subject: Fully detect uninteresting commits.

With the change in the previous round, we are guaranteed to come up
with the list of all relevant merge bases, but sometimes we do not
fully mark unintersting ones due to a horizon effect.  Add a phase to
postprocess, so that we mark all ancestor of "interesting" commit.

This also changes the default ordering of shown commits back to
chronological order, and adds --topo-order flag to show them in
topological order.

Signed-off-by: Junio C Hamano <junkio@cox.net>
---
 show-branch.c | 64 +++++++++++++++++++++++++++++++++++++++++++++++++----------
 1 file changed, 53 insertions(+), 11 deletions(-)

diff --git a/show-branch.c b/show-branch.c
index 714e7f8ca3..631336cd9d 100644
--- a/show-branch.c
+++ b/show-branch.c
@@ -199,18 +199,58 @@ static void join_revs(struct commit_list **list_p,
 			parents = parents->next;
 			if ((this_flag & flags) == flags)
 				continue;
-			parse_commit(p);
+			if (!p->object.parsed)
+				parse_commit(p);
 			if (mark_seen(p, seen_p) && !still_interesting)
 				extra--;
 			p->object.flags |= flags;
 			insert_by_date(p, list_p);
 		}
 	}
+
+	/*
+	 * Postprocess to complete well-poisoning.
+	 *
+	 * At this point we have all the commits we have seen in
+	 * seen_p list (which happens to be sorted chronologically but
+	 * it does not really matter).  Mark anything that can be
+	 * reached from uninteresting commits not interesting.
+	 */
+	for (;;) {
+		int changed = 0;
+		struct commit_list *s;
+		for (s = *seen_p; s; s = s->next) {
+			struct commit *c = s->item;
+			struct commit_list *parents;
+
+			if (((c->object.flags & all_revs) != all_revs) &&
+			    !(c->object.flags & UNINTERESTING))
+				continue;
+
+			/* The current commit is either a merge base or
+			 * already uninteresting one.  Mark its parents
+			 * as uninteresting commits _only_ if they are
+			 * already parsed.  No reason to find new ones
+			 * here.
+			 */
+			parents = c->parents;
+			while (parents) {
+				struct commit *p = parents->item;
+				parents = parents->next;
+				if (!(p->object.flags & UNINTERESTING)) {
+					p->object.flags |= UNINTERESTING;
+					changed = 1;
+				}
+			}
+		}
+		if (!changed)
+			break;
+	}
 }
 
 static void show_one_commit(struct commit *commit, int no_name)
 {
-	char pretty[128], *cp;
+	char pretty[256], *cp;
 	struct commit_name *name = commit->object.util;
 	if (commit->object.parsed)
 		pretty_print_commit(CMIT_FMT_ONELINE, commit->buffer, ~0,
@@ -360,7 +400,7 @@ int main(int ac, char **av)
 	unsigned int rev_mask[MAX_REVS];
 	int num_rev, i, extra = 0;
 	int all_heads = 0, all_tags = 0;
-	int all_mask, all_revs, shown_merge_point;
+	int all_mask, all_revs;
 	char head_path[128];
 	const char *head_path_p;
 	int head_path_len;
@@ -369,6 +409,8 @@ int main(int ac, char **av)
 	int independent = 0;
 	int no_name = 0;
 	int sha1_name = 0;
+	int shown_merge_point = 0;
+	int topo_order = 0;
 
 	setup_git_directory();
 
@@ -394,6 +436,8 @@ int main(int ac, char **av)
 			merge_base = 1;
 		else if (!strcmp(arg, "--independent"))
 			independent = 1;
+		else if (!strcmp(arg, "--topo-order"))
+			topo_order = 1;
 		else
 			usage(show_branch_usage);
 		ac--; av++;
@@ -496,7 +540,8 @@ int main(int ac, char **av)
 		exit(0);
 
 	/* Sort topologically */
-	sort_in_topological_order(&seen);
+	if (topo_order)
+		sort_in_topological_order(&seen);
 
 	/* Give names to commits */
 	if (!sha1_name && !no_name)
@@ -504,15 +549,12 @@ int main(int ac, char **av)
 
 	all_mask = ((1u << (REV_SHIFT + num_rev)) - 1);
 	all_revs = all_mask & ~((1u << REV_SHIFT) - 1);
-	shown_merge_point = 0;
 
 	while (seen) {
 		struct commit *commit = pop_one_commit(&seen);
 		int this_flag = commit->object.flags;
-		int is_merge_point = (this_flag & all_revs) == all_revs;
 
-		if (is_merge_point)
-			shown_merge_point = 1;
+		shown_merge_point |= ((this_flag & all_revs) == all_revs);
 
 		if (1 < num_rev) {
 			for (i = 0; i < num_rev; i++)
@@ -521,9 +563,9 @@ int main(int ac, char **av)
 			putchar(' ');
 		}
 		show_one_commit(commit, no_name);
-		if (shown_merge_point && is_merge_point)
-			if (--extra < 0)
-				break;
+
+		if (shown_merge_point && --extra < 0)
+			break;
 	}
 	return 0;
 }
-- 
cgit v1.2.3


From 4bc51db0feb4a93a285d6333f206cad77c83ed57 Mon Sep 17 00:00:00 2001
From: Junio C Hamano <junkio@cox.net>
Date: Thu, 10 Nov 2005 18:27:44 -0800
Subject: t1200: use --topo-order to keep the show-branch output stable.

Because a batch-oriented script creates many commits within a second
on a fast machine, show-branch output of the test results are unstable
without topo-order.

Signed-off-by: Junio C Hamano <junkio@cox.net>
---
 t/t1200-tutorial.sh | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/t/t1200-tutorial.sh b/t/t1200-tutorial.sh
index 35db799edf..d7562e9748 100644
--- a/t/t1200-tutorial.sh
+++ b/t/t1200-tutorial.sh
@@ -122,7 +122,7 @@ cat > show-branch.expect << EOF
 ++ [mybranch] Some work.
 EOF
 
-git show-branch master mybranch > show-branch.output
+git show-branch --topo-order master mybranch > show-branch.output
 test_expect_success 'git show-branch' 'cmp show-branch.expect show-branch.output'
 
 git checkout mybranch
@@ -145,7 +145,7 @@ cat > show-branch2.expect << EOF
 ++ [master] Merged "mybranch" changes.
 EOF
 
-git show-branch master mybranch > show-branch2.output
+git show-branch --topo-order master mybranch > show-branch2.output
 test_expect_success 'git show-branch' 'cmp show-branch2.expect show-branch2.output'
 
 # TODO: test git fetch
-- 
cgit v1.2.3


From 3cab3594e9cfd5e98cbcb819b1bed91a7b3a974b Mon Sep 17 00:00:00 2001
From: Junio C Hamano <junkio@cox.net>
Date: Fri, 11 Nov 2005 11:27:03 -0800
Subject: INSTALL: duplicate python requirements from Makefile

... and refer the reader to Makefile for other things that can be
tweaked.

Signed-off-by: Junio C Hamano <junkio@cox.net>
---
 INSTALL | 12 ++++++++++++
 1 file changed, 12 insertions(+)

diff --git a/INSTALL b/INSTALL
index 06b11e104c..63ccf62ae9 100644
--- a/INSTALL
+++ b/INSTALL
@@ -75,3 +75,15 @@ Issues of note:
           history graphically
 
 	- "ssh" is used to push and pull over the net
+
+	- "perl" and POSIX-compliant shells are needed to use most of
+	  the barebone Porcelainish scripts.
+
+	- "python" 2.3 or more recent; if you have 2.3, you may need
+          to build with "make WITH_OWN_SUBPROCESS_PY=YesPlease".
+
+ - Some platform specific issues are dealt with Makefile rules,
+   but depending on your specific installation, you may not
+   have all the libraries/tools needed, or you may have
+   necessary libraries at unusual locations.  Please look at the
+   top of the Makefile to see what can be adjusted for your needs.
-- 
cgit v1.2.3


From 5f3aa197ac03eabbc45046cd3b9dbcfbda0426d9 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Lukas=5FSandstr=C3=B6m?= <lukass@etek.chalmers.se>
Date: Fri, 11 Nov 2005 02:12:27 +0100
Subject: Change 'cache' to 'index' in the docs
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

This patch makes the documentation refer to the index
as index instead of cache, but some references still
remain. (e.g. git-update-index.txt)

Signed-off-by: Lukas Sandström <lukass@etek.chalmers.se>
Signed-off-by: Junio C Hamano <junkio@cox.net>
---
 Documentation/diff-format.txt        |  8 ++++----
 Documentation/diff-options.txt       |  2 +-
 Documentation/git-checkout-index.txt | 14 +++++++-------
 Documentation/git-cvsimport.txt      |  2 +-
 Documentation/git-diff-files.txt     |  6 +++---
 Documentation/git-diff-index.txt     | 14 +++++++-------
 Documentation/git-fsck-objects.txt   |  4 ++--
 Documentation/git-hash-object.txt    |  2 +-
 Documentation/git-ls-files.txt       |  2 +-
 Documentation/git-merge-index.txt    |  4 ++--
 Documentation/git-read-tree.txt      | 20 ++++++++++----------
 Documentation/git-svnimport.txt      |  2 +-
 Documentation/git-update-index.txt   | 24 ++++++++++++------------
 Documentation/git-write-tree.txt     |  8 ++++----
 Documentation/git.txt                | 18 +++++++++---------
 Documentation/glossary.txt           |  6 +++---
 Documentation/tutorial.txt           |  6 +++---
 17 files changed, 71 insertions(+), 71 deletions(-)

diff --git a/Documentation/diff-format.txt b/Documentation/diff-format.txt
index d1d0d2d3dc..b426a14f5e 100644
--- a/Documentation/diff-format.txt
+++ b/Documentation/diff-format.txt
@@ -8,13 +8,13 @@ git-diff-index <tree-ish>::
         compares the <tree-ish> and the files on the filesystem.
 
 git-diff-index --cached <tree-ish>::
-        compares the <tree-ish> and the cache.
+        compares the <tree-ish> and the index.
 
 git-diff-tree [-r] <tree-ish-1> <tree-ish-2> [<pattern>...]::
         compares the trees named by the two arguments.
 
 git-diff-files [<pattern>...]::
-        compares the cache and the files on the filesystem.
+        compares the index and the files on the filesystem.
 
 
 An output line is formatted this way:
@@ -47,7 +47,7 @@ That is, from the left to the right:
 . an LF or a NUL when '-z' option is used, to terminate the record.
 
 <sha1> is shown as all 0's if a file is new on the filesystem
-and it is out of sync with the cache.
+and it is out of sync with the index.
 
 Example:
 
@@ -104,7 +104,7 @@ where:
 The file parameters can point at the user's working file
 (e.g. `new-file` in "git-diff-files"), `/dev/null` (e.g. `old-file`
 when a new file is added), or a temporary file (e.g. `old-file` in the
-cache).  'GIT_EXTERNAL_DIFF' should not worry about unlinking the
+index).  'GIT_EXTERNAL_DIFF' should not worry about unlinking the
 temporary file --- it is removed when 'GIT_EXTERNAL_DIFF' exits.
 
 For a path that is unmerged, 'GIT_EXTERNAL_DIFF' is called with 1
diff --git a/Documentation/diff-options.txt b/Documentation/diff-options.txt
index 32005b03f3..8eef86e474 100644
--- a/Documentation/diff-options.txt
+++ b/Documentation/diff-options.txt
@@ -50,7 +50,7 @@
 	<orderfile>, which has one shell glob pattern per line.
 
 -R::
-	Swap two inputs; that is, show differences from cache or
+	Swap two inputs; that is, show differences from index or
 	on-disk file to tree contents.
 
 For more detailed explanation on these common options, see also
diff --git a/Documentation/git-checkout-index.txt b/Documentation/git-checkout-index.txt
index 589dc9ad12..94b283a6bf 100644
--- a/Documentation/git-checkout-index.txt
+++ b/Documentation/git-checkout-index.txt
@@ -3,7 +3,7 @@ git-checkout-index(1)
 
 NAME
 ----
-git-checkout-index - Copy files from the cache to the working directory
+git-checkout-index - Copy files from the index to the working directory
 
 
 SYNOPSIS
@@ -13,23 +13,23 @@ SYNOPSIS
 
 DESCRIPTION
 -----------
-Will copy all files listed from the cache to the working directory
+Will copy all files listed from the index to the working directory
 (not overwriting existing files).
 
 OPTIONS
 -------
 -u::
 	update stat information for the checked out entries in
-	the cache file.
+	the index file.
 
 -q::
-	be quiet if files exist or are not in the cache
+	be quiet if files exist or are not in the index
 
 -f::
 	forces overwrite of existing files
 
 -a::
-	checks out all files in the cache.  Cannot be used
+	checks out all files in the index.  Cannot be used
 	together with explicit filenames.
 
 -n::
@@ -57,7 +57,7 @@ supposed to be able to do things like:
 
 which will force all existing `*.h` files to be replaced with their
 cached copies. If an empty command line implied "all", then this would
-force-refresh everything in the cache, which was not the point.
+force-refresh everything in the index, which was not the point.
 
 To update and refresh only the files already checked out:
 
@@ -74,7 +74,7 @@ desired tree into the index, and do a
 
         git-checkout-index --prefix=git-export-dir/ -a
 
-and git-checkout-index will "export" the cache into the specified
+and git-checkout-index will "export" the index into the specified
 directory.
 
 NOTE The final "/" is important. The exported name is literally just
diff --git a/Documentation/git-cvsimport.txt b/Documentation/git-cvsimport.txt
index 4b62256a79..88bd3b0f17 100644
--- a/Documentation/git-cvsimport.txt
+++ b/Documentation/git-cvsimport.txt
@@ -35,7 +35,7 @@ OPTIONS
 
 -i::
 	Import-only: don't perform a checkout after importing.  This option
-	ensures the working directory and cache remain untouched and will
+	ensures the working directory and index remain untouched and will
 	not create them if they do not exist.
 
 -k::
diff --git a/Documentation/git-diff-files.txt b/Documentation/git-diff-files.txt
index e3873888f2..3b04bfeec6 100644
--- a/Documentation/git-diff-files.txt
+++ b/Documentation/git-diff-files.txt
@@ -3,7 +3,7 @@ git-diff-files(1)
 
 NAME
 ----
-git-diff-files - Compares files in the working tree and the cache
+git-diff-files - Compares files in the working tree and the index
 
 
 SYNOPSIS
@@ -12,9 +12,9 @@ SYNOPSIS
 
 DESCRIPTION
 -----------
-Compares the files in the working tree and the cache.  When paths
+Compares the files in the working tree and the index.  When paths
 are specified, compares only those named paths.  Otherwise all
-entries in the cache are compared.  The output format is the
+entries in the index are compared.  The output format is the
 same as "git-diff-index" and "git-diff-tree".
 
 OPTIONS
diff --git a/Documentation/git-diff-index.txt b/Documentation/git-diff-index.txt
index 2fc3eed710..d8fc78fab9 100644
--- a/Documentation/git-diff-index.txt
+++ b/Documentation/git-diff-index.txt
@@ -3,7 +3,7 @@ git-diff-index(1)
 
 NAME
 ----
-git-diff-index - Compares content and mode of blobs between the cache and repository
+git-diff-index - Compares content and mode of blobs between the index and repository
 
 
 SYNOPSIS
@@ -13,10 +13,10 @@ SYNOPSIS
 DESCRIPTION
 -----------
 Compares the content and mode of the blobs found via a tree
-object with the content of the current cache and, optionally
+object with the content of the current index and, optionally
 ignoring the stat state of the file on disk.  When paths are
 specified, compares only those named paths.  Otherwise all
-entries in the cache are compared.
+entries in the index are compared.
 
 OPTIONS
 -------
@@ -49,11 +49,11 @@ Cached Mode
 -----------
 If '--cached' is specified, it allows you to ask:
 
-	show me the differences between HEAD and the current cache
+	show me the differences between HEAD and the current index
 	contents (the ones I'd write with a "git-write-tree")
 
 For example, let's say that you have worked on your working directory, updated
-some files in the cache and are ready to commit. You want to see eactly
+some files in the index and are ready to commit. You want to see eactly
 *what* you are going to commit is without having to write a new tree
 object and compare it that way, and to do that, you just do
 
@@ -92,7 +92,7 @@ which is obviously a very useful question too, since that tells you what
 you *could* commit. Again, the output matches the "git-diff-tree -r"
 output to a tee, but with a twist.
 
-The twist is that if some file doesn't match the cache, we don't have
+The twist is that if some file doesn't match the index, we don't have
 a backing store thing for it, and we use the magic "all-zero" sha1 to
 show that. So let's say that you have edited `kernel/sched.c`, but
 have not actually done a "git-update-index" on it yet - there is no
@@ -110,7 +110,7 @@ NOTE: As with other commands of this type, "git-diff-index" does not
 actually look at the contents of the file at all. So maybe
 `kernel/sched.c` hasn't actually changed, and it's just that you
 touched it. In either case, it's a note that you need to
-"git-upate-cache" it to make the cache be in sync.
+"git-upate-index" it to make the index be in sync.
 
 NOTE: You can have a mixture of files show up as "has been updated"
 and "is still dirty in the working directory" together. You can always
diff --git a/Documentation/git-fsck-objects.txt b/Documentation/git-fsck-objects.txt
index 5dc9dbdd78..37e8055d21 100644
--- a/Documentation/git-fsck-objects.txt
+++ b/Documentation/git-fsck-objects.txt
@@ -33,7 +33,7 @@ index file and all SHA1 references in .git/refs/* as heads.
 	Report tags.
 
 --cache::
-	Consider any object recorded in the cache also as a head node for
+	Consider any object recorded in the index also as a head node for
 	an unreachability trace.
 
 --standalone::
@@ -125,7 +125,7 @@ GIT_OBJECT_DIRECTORY::
 	used to specify the object database root (usually $GIT_DIR/objects)
 
 GIT_INDEX_FILE::
-	used to specify the index file of the cache
+	used to specify the index file of the index
 
 GIT_ALTERNATE_OBJECT_DIRECTORIES::
 	used to specify additional object database roots (usually unset)
diff --git a/Documentation/git-hash-object.txt b/Documentation/git-hash-object.txt
index 9239f11135..07d2c427c5 100644
--- a/Documentation/git-hash-object.txt
+++ b/Documentation/git-hash-object.txt
@@ -16,7 +16,7 @@ Computes the object ID value for an object with specified type
 with the contents of the named file (which can be outside of the
 work tree), and optionally writes the resulting object into the
 object database.  Reports its object ID to its standard output.
-This is used by "git-cvsimport" to update the cache
+This is used by "git-cvsimport" to update the index
 without modifying files in the work tree.  When <type> is not
 specified, it defaults to "blob". 
 
diff --git a/Documentation/git-ls-files.txt b/Documentation/git-ls-files.txt
index 8c1784d2e3..2f308ecda9 100644
--- a/Documentation/git-ls-files.txt
+++ b/Documentation/git-ls-files.txt
@@ -3,7 +3,7 @@ git-ls-files(1)
 
 NAME
 ----
-git-ls-files - Information about files in the cache/working directory
+git-ls-files - Information about files in the index/working directory
 
 
 SYNOPSIS
diff --git a/Documentation/git-merge-index.txt b/Documentation/git-merge-index.txt
index d072fdaa4f..60306429fb 100644
--- a/Documentation/git-merge-index.txt
+++ b/Documentation/git-merge-index.txt
@@ -12,7 +12,7 @@ SYNOPSIS
 
 DESCRIPTION
 -----------
-This looks up the <file>(s) in the cache and, if there are any merge
+This looks up the <file>(s) in the index and, if there are any merge
 entries, passes the SHA1 hash for those files as arguments 1, 2, 3 (empty
 argument if no file), and <file> as argument 4.  File modes for the three
 files are passed as arguments 5, 6 and 7.
@@ -23,7 +23,7 @@ OPTIONS
 	Interpret all following arguments as filenames.
 
 -a::
-	Run merge against all files in the cache that need merging.
+	Run merge against all files in the index that need merging.
 
 -o::
 	Instead of stopping at the first failed merge, do all of them
diff --git a/Documentation/git-read-tree.txt b/Documentation/git-read-tree.txt
index 7db5fb5795..e219c6a788 100644
--- a/Documentation/git-read-tree.txt
+++ b/Documentation/git-read-tree.txt
@@ -3,7 +3,7 @@ git-read-tree(1)
 
 NAME
 ----
-git-read-tree - Reads tree information into the directory cache
+git-read-tree - Reads tree information into the index
 
 
 SYNOPSIS
@@ -13,11 +13,11 @@ SYNOPSIS
 
 DESCRIPTION
 -----------
-Reads the tree information given by <tree-ish> into the directory cache,
+Reads the tree information given by <tree-ish> into the index,
 but does not actually *update* any of the files it "caches". (see:
 git-checkout-index)
 
-Optionally, it can merge a tree into the cache, perform a
+Optionally, it can merge a tree into the index, perform a
 fast-forward (i.e. 2-way) merge, or a 3-way merge, with the -m
 flag.  When used with -m, the -u flag causes it to also update
 the files in the work tree with the result of the merge.
@@ -59,10 +59,10 @@ provided.
 Single Tree Merge
 ~~~~~~~~~~~~~~~~~
 If only 1 tree is specified, git-read-tree operates as if the user did not
-specify '-m', except that if the original cache has an entry for a
+specify '-m', except that if the original index has an entry for a
 given pathname, and the contents of the path matches with the tree
-being read, the stat info from the cache is used. (In other words, the
-cache's stat()s take precedence over the merged tree's).
+being read, the stat info from the index is used. (In other words, the
+index's stat()s take precedence over the merged tree's).
 
 That means that if you do a "git-read-tree -m <newtree>" followed by a
 "git-checkout-index -f -u -a", the "git-checkout-index" only checks out
@@ -96,7 +96,7 @@ Here are the "carry forward" rules:
        -------------------------------------------------------
       0 nothing             nothing  nothing  (does not happen)
       1 nothing             nothing  exists   use M
-      2 nothing             exists   nothing  remove path from cache
+      2 nothing             exists   nothing  remove path from index
       3 nothing             exists   exists   use M
 
         clean I==H  I==M
@@ -109,7 +109,7 @@ Here are the "carry forward" rules:
       8 yes   N/A   no      nothing  exists   fail
       9 no    N/A   no      nothing  exists   fail
 
-     10 yes   yes   N/A     exists   nothing  remove path from cache
+     10 yes   yes   N/A     exists   nothing  remove path from index
      11 no    yes   N/A     exists   nothing  fail
      12 yes   no    N/A     exists   nothing  fail
      13 no    no    N/A     exists   nothing  fail
@@ -128,7 +128,7 @@ Here are the "carry forward" rules:
      20 yes   yes   no      exists   exists   use M
      21 no    yes   no      exists   exists   fail
 
-In all "keep index" cases, the cache entry stays as in the
+In all "keep index" cases, the index entry stays as in the
 original index file.  If the entry were not up to date,
 git-read-tree keeps the copy in the work tree intact when
 operating under the -u flag.
@@ -245,7 +245,7 @@ since you pulled from him:
 
 Your work tree is still based on your HEAD ($JC), but you have
 some edits since.  Three-way merge makes sure that you have not
-added or modified cache entries since $JC, and if you haven't,
+added or modified index entries since $JC, and if you haven't,
 then does the right thing.  So with the following sequence:
 
     $ git-read-tree -m -u `git-merge-base $JC $LT` $JC $LT
diff --git a/Documentation/git-svnimport.txt b/Documentation/git-svnimport.txt
index 88bdc08eb4..fcc79fa93a 100644
--- a/Documentation/git-svnimport.txt
+++ b/Documentation/git-svnimport.txt
@@ -44,7 +44,7 @@ When importing incementally, you might need to edit the .git/svn2git file.
 
 -i::
 	Import-only: don't perform a checkout after importing.  This option
-	ensures the working directory and cache remain untouched and will
+	ensures the working directory and index remain untouched and will
 	not create them if they do not exist.
 
 -t <trunk_subdir>::
diff --git a/Documentation/git-update-index.txt b/Documentation/git-update-index.txt
index 58b9e49af5..52874c8562 100644
--- a/Documentation/git-update-index.txt
+++ b/Documentation/git-update-index.txt
@@ -21,7 +21,7 @@ SYNOPSIS
 DESCRIPTION
 -----------
 Modifies the index or directory cache. Each file mentioned is updated
-into the cache and any 'unmerged' or 'needs updating' state is
+into the index and any 'unmerged' or 'needs updating' state is
 cleared.
 
 The way "git-update-index" handles files it is told about can be modified
@@ -30,26 +30,26 @@ using the various options:
 OPTIONS
 -------
 --add::
-	If a specified file isn't in the cache already then it's
+	If a specified file isn't in the index already then it's
 	added.
 	Default behaviour is to ignore new files.
 
 --remove::
-	If a specified file is in the cache but is missing then it's
+	If a specified file is in the index but is missing then it's
 	removed.
 	Default behaviour is to ignore removed file.
 
 --refresh::
-	Looks at the current cache and checks to see if merges or
+	Looks at the current index and checks to see if merges or
 	updates are needed by checking stat() information.
 
 -q::
-        Quiet.  If --refresh finds that the cache needs an update, the
+        Quiet.  If --refresh finds that the index needs an update, the
         default behavior is to error out.  This option makes
         git-update-index continue anyway.
 
 --unmerged::
-        If --refresh finds unmerged changes in the cache, the default 
+        If --refresh finds unmerged changes in the index, the default
         behavior is to error out.  This option makes git-update-index 
         continue anyway.
 
@@ -57,7 +57,7 @@ OPTIONS
 	Ignores missing files during a --refresh
 
 --cacheinfo <mode> <object> <path>::
-	Directly insert the specified info into the cache.
+	Directly insert the specified info into the index.
 	
 --index-info::
         Read index info from stdin.
@@ -68,7 +68,7 @@ OPTIONS
 --info-only::
 	Do not create objects in the object database for all
 	<file> arguments that follow this flag; just insert
-	their object IDs into the cache.
+	their object IDs into the index.
 
 --force-remove::
 	Remove the file from the index even when the working directory
@@ -106,14 +106,14 @@ OPTIONS
 
 Using --refresh
 ---------------
-'--refresh' does not calculate a new sha1 file or bring the cache
+'--refresh' does not calculate a new sha1 file or bring the index
 up-to-date for mode/content changes. But what it *does* do is to
-"re-match" the stat information of a file with the cache, so that you
-can refresh the cache for a file that hasn't been changed but where
+"re-match" the stat information of a file with the index, so that you
+can refresh the index for a file that hasn't been changed but where
 the stat entry is out of date.
 
 For example, you'd want to do this after doing a "git-read-tree", to link
-up the stat cache details with the proper files.
+up the stat index details with the proper files.
 
 Using --cacheinfo or --info-only
 --------------------------------
diff --git a/Documentation/git-write-tree.txt b/Documentation/git-write-tree.txt
index 51be44d1f2..abee05f6f5 100644
--- a/Documentation/git-write-tree.txt
+++ b/Documentation/git-write-tree.txt
@@ -3,7 +3,7 @@ git-write-tree(1)
 
 NAME
 ----
-git-write-tree - Creates a tree object from the current cache
+git-write-tree - Creates a tree object from the current index
 
 
 SYNOPSIS
@@ -12,11 +12,11 @@ SYNOPSIS
 
 DESCRIPTION
 -----------
-Creates a tree object using the current cache.
+Creates a tree object using the current index.
 
-The cache must be merged.
+The index must be merged.
 
-Conceptually, "git-write-tree" sync()s the current directory cache contents
+Conceptually, "git-write-tree" sync()s the current index contents
 into a set of tree files.
 In order to have that match what is actually in your directory right
 now, you need to have done a "git-update-index" phase before you did the
diff --git a/Documentation/git.txt b/Documentation/git.txt
index 2f9622f5ac..b7bc4fb231 100644
--- a/Documentation/git.txt
+++ b/Documentation/git.txt
@@ -40,7 +40,7 @@ reflect recent changes.
 Commands Overview
 -----------------
 The git commands can helpfully be split into those that manipulate
-the repository, the cache and the working fileset, those that
+the repository, the index and the working fileset, those that
 interrogate and compare them, and those that moves objects and
 references between repositories.
 
@@ -59,7 +59,7 @@ gitlink:git-apply[1]::
 	applies it to the working tree.
 
 gitlink:git-checkout-index[1]::
-	Copy files from the cache to the working directory
+	Copy files from the index to the working directory
 
 gitlink:git-commit-tree[1]::
 	Creates a new commit object
@@ -86,7 +86,7 @@ gitlink:git-prune-packed[1]::
 	Remove extra objects that are already in pack files.
 
 gitlink:git-read-tree[1]::
-	Reads tree information into the directory cache
+	Reads tree information into the directory index
 
 gitlink:git-unpack-objects[1]::
 	Unpacks objects out of a packed archive.
@@ -95,7 +95,7 @@ gitlink:git-update-index[1]::
 	Modifies the index or directory cache
 
 gitlink:git-write-tree[1]::
-	Creates a tree from the current cache
+	Creates a tree from the current index
 
 
 Interrogation commands
@@ -105,10 +105,10 @@ gitlink:git-cat-file[1]::
 	Provide content or type information for repository objects
 
 gitlink:git-diff-index[1]::
-	Compares content and mode of blobs between the cache and repository
+	Compares content and mode of blobs between the index and repository
 
 gitlink:git-diff-files[1]::
-	Compares files in the working tree and the cache
+	Compares files in the working tree and the index
 
 gitlink:git-diff-stages[1]::
 	Compares two "merge stages" in the index file.
@@ -120,7 +120,7 @@ gitlink:git-fsck-objects[1]::
 	Verifies the connectivity and validity of the objects in the database
 
 gitlink:git-ls-files[1]::
-	Information about files in the cache/working directory
+	Information about files in the index/working directory
 
 gitlink:git-ls-tree[1]::
 	Displays a tree object in human readable form
@@ -490,8 +490,8 @@ git so take care if using Cogito etc
 
 'GIT_INDEX_FILE'::
 	This environment allows the specification of an alternate
-	cache/index file. If not specified, the default of
-	`$GIT_DIR/index` is used.
+	index file. If not specified, the default of `$GIT_DIR/index`
+	is used.
 
 'GIT_OBJECT_DIRECTORY'::
 	If the object storage directory is specified via this
diff --git a/Documentation/glossary.txt b/Documentation/glossary.txt
index eb7b471024..07df6b48be 100644
--- a/Documentation/glossary.txt
+++ b/Documentation/glossary.txt
@@ -43,14 +43,14 @@ DAG::
 
 index::
 	A collection of files with stat information, whose contents are
-	stored as objects. The cache is a stored version of your working
+	stored as objects. The index is a stored version of your working
 	tree. Truth be told, it can also contain a second, and even a third
 	version of a working tree, which are used when merging.
 
 index entry::
 	The information regarding a particular file, stored in the index.
 	An index entry can be unmerged, if a merge was started, but not
-	yet finished (i.e. if the cache contains multiple versions of
+	yet finished (i.e. if the index contains multiple versions of
 	that file).
 
 unmerged index:
@@ -75,7 +75,7 @@ checkout::
 	stored in the object database.
 
 commit::
-	As a verb: The action of storing the current state of the cache in the
+	As a verb: The action of storing the current state of the index in the
 	object database. The result is a revision.
 	As a noun: Short hand for commit object.
 
diff --git a/Documentation/tutorial.txt b/Documentation/tutorial.txt
index 95ed852f26..03eb4216f3 100644
--- a/Documentation/tutorial.txt
+++ b/Documentation/tutorial.txt
@@ -131,7 +131,7 @@ actually check in your hard work, you will have to go through two steps:
 The first step is trivial: when you want to tell git about any changes
 to your working tree, you use the `git-update-index` program. That
 program normally just takes a list of filenames you want to update, but
-to avoid trivial mistakes, it refuses to add new entries to the cache
+to avoid trivial mistakes, it refuses to add new entries to the index
 (or remove existing ones) unless you explicitly tell it that you're
 adding a new entry with the `\--add` flag (or removing an entry with the
 `\--remove`) flag.
@@ -199,7 +199,7 @@ was just to show that `git-update-index` did something magical, and
 actually saved away the contents of your files into the git object
 database.
 
-Updating the cache did something else too: it created a `.git/index`
+Updating the index did something else too: it created a `.git/index`
 file. This is the index that describes your current working tree, and
 something you should be very aware of. Again, you normally never worry
 about the index file itself, but you should be aware of the fact that
@@ -440,7 +440,7 @@ a bit about what you have done.
 Write whatever message you want, and all the lines that start with '#'
 will be pruned out, and the rest will be used as the commit message for
 the change. If you decide you don't want to commit anything after all at
-this point (you can continue to edit things and update the cache), you
+this point (you can continue to edit things and update the index), you
 can just leave an empty message. Otherwise `git commit` will commit
 the change for you.
 
-- 
cgit v1.2.3


From 46e651743ae5c0938c4ff076a0453ecc9611a520 Mon Sep 17 00:00:00 2001
From: Fredrik Kuivinen <freku045@student.liu.se>
Date: Sat, 12 Nov 2005 00:53:07 +0100
Subject: merge-recursive: Indent the output properly

If we have multiple common ancestors and have to recursively merge
them then the output will be much more readable with this commit.

Signed-off-by: Fredrik Kuivinen <freku045@student.liu.se>
Signed-off-by: Junio C Hamano <junkio@cox.net>
---
 git-merge-recursive.py | 130 ++++++++++++++++++++++++++-----------------------
 1 file changed, 69 insertions(+), 61 deletions(-)

diff --git a/git-merge-recursive.py b/git-merge-recursive.py
index 90e889c300..e6cbdde71a 100755
--- a/git-merge-recursive.py
+++ b/git-merge-recursive.py
@@ -7,6 +7,11 @@ from sets import Set
 sys.path.append('''@@GIT_PYTHON_PATH@@''')
 from gitMergeCommon import *
 
+outputIndent = 0
+def output(*args):
+    sys.stdout.write('  '*outputIndent)
+    printList(args)
+
 originalIndexFile = os.environ.get('GIT_INDEX_FILE',
                                    os.environ.get('GIT_DIR', '.git') + '/index')
 temporaryIndexFile = os.environ.get('GIT_DIR', '.git') + \
@@ -41,27 +46,27 @@ def merge(h1, h2, branch1Name, branch2Name, graph, callDepth=0):
     assert(isinstance(h1, Commit) and isinstance(h2, Commit))
     assert(isinstance(graph, Graph))
 
-    def infoMsg(*args):
-        sys.stdout.write('  '*callDepth)
-        printList(args)
+    global outputIndent
 
-    infoMsg('Merging:')
-    infoMsg(h1)
-    infoMsg(h2)
+    output('Merging:')
+    output(h1)
+    output(h2)
     sys.stdout.flush()
 
     ca = getCommonAncestors(graph, h1, h2)
-    infoMsg('found', len(ca), 'common ancestor(s):')
+    output('found', len(ca), 'common ancestor(s):')
     for x in ca:
-        infoMsg(x)
+        output(x)
     sys.stdout.flush()
 
     mergedCA = ca[0]
     for h in ca[1:]:
+        outputIndent = callDepth+1
         [mergedCA, dummy] = merge(mergedCA, h,
-                                  'Temporary shared merge branch 1',
-                                  'Temporary shared merge branch 2',
+                                  'Temporary merge branch 1',
+                                  'Temporary merge branch 2',
                                   graph, callDepth+1)
+        outputIndent = callDepth
         assert(isinstance(mergedCA, Commit))
 
     global cacheOnly
@@ -116,7 +121,7 @@ def mergeTrees(head, merge, common, branch1Name, branch2Name):
     assert(isSha(head) and isSha(merge) and isSha(common))
 
     if common == merge:
-        print 'Already uptodate!'
+        output('Already uptodate!')
         return [head, True]
 
     if cacheOnly:
@@ -554,23 +559,24 @@ def processRenames(renamesA, renamesB, branchNameA, branchNameB):
             ren2.processed = True
 
             if ren1.dstName != ren2.dstName:
-                print 'CONFLICT (rename/rename): Rename', \
-                      fmtRename(path, ren1.dstName), 'in branch', branchName1, \
-                      'rename', fmtRename(path, ren2.dstName), 'in', branchName2
+                output('CONFLICT (rename/rename): Rename',
+                       fmtRename(path, ren1.dstName), 'in branch', branchName1,
+                       'rename', fmtRename(path, ren2.dstName), 'in',
+                       branchName2)
                 cleanMerge = False
 
                 if ren1.dstName in currentDirectorySet:
                     dstName1 = uniquePath(ren1.dstName, branchName1)
-                    print ren1.dstName, 'is a directory in', branchName2, \
-                          'adding as', dstName1, 'instead.'
+                    output(ren1.dstName, 'is a directory in', branchName2,
+                           'adding as', dstName1, 'instead.')
                     removeFile(False, ren1.dstName)
                 else:
                     dstName1 = ren1.dstName
 
                 if ren2.dstName in currentDirectorySet:
                     dstName2 = uniquePath(ren2.dstName, branchName2)
-                    print ren2.dstName, 'is a directory in', branchName1, \
-                          'adding as', dstName2, 'instead.'
+                    output(ren2.dstName, 'is a directory in', branchName1,
+                           'adding as', dstName2, 'instead.')
                     removeFile(False, ren2.dstName)
                 else:
                     dstName2 = ren1.dstName
@@ -585,13 +591,14 @@ def processRenames(renamesA, renamesB, branchNameA, branchNameB):
                                    branchName1, branchName2)
 
                 if merge or not clean:
-                    print 'Renaming', fmtRename(path, ren1.dstName)
+                    output('Renaming', fmtRename(path, ren1.dstName))
 
                 if merge:
-                    print 'Auto-merging', ren1.dstName
+                    output('Auto-merging', ren1.dstName)
 
                 if not clean:
-                    print 'CONFLICT (content): merge conflict in', ren1.dstName
+                    output('CONFLICT (content): merge conflict in',
+                           ren1.dstName)
                     cleanMerge = False
 
                     if not cacheOnly:
@@ -615,25 +622,25 @@ def processRenames(renamesA, renamesB, branchNameA, branchNameB):
             
             if ren1.dstName in currentDirectorySet:
                 newPath = uniquePath(ren1.dstName, branchName1)
-                print 'CONFLICT (rename/directory): Rename', \
-                      fmtRename(ren1.srcName, ren1.dstName), 'in', branchName1,\
-                      'directory', ren1.dstName, 'added in', branchName2
-                print 'Renaming', ren1.srcName, 'to', newPath, 'instead'
+                output('CONFLICT (rename/directory): Rename',
+                       fmtRename(ren1.srcName, ren1.dstName), 'in', branchName1,
+                       'directory', ren1.dstName, 'added in', branchName2)
+                output('Renaming', ren1.srcName, 'to', newPath, 'instead')
                 cleanMerge = False
                 removeFile(False, ren1.dstName)
                 updateFile(False, ren1.dstSha, ren1.dstMode, newPath)
             elif srcShaOtherBranch == None:
-                print 'CONFLICT (rename/delete): Rename', \
-                      fmtRename(ren1.srcName, ren1.dstName), 'in', \
-                      branchName1, 'and deleted in', branchName2
+                output('CONFLICT (rename/delete): Rename',
+                       fmtRename(ren1.srcName, ren1.dstName), 'in',
+                       branchName1, 'and deleted in', branchName2)
                 cleanMerge = False
                 updateFile(False, ren1.dstSha, ren1.dstMode, ren1.dstName)
             elif dstShaOtherBranch:
                 newPath = uniquePath(ren1.dstName, branchName2)
-                print 'CONFLICT (rename/add): Rename', \
-                      fmtRename(ren1.srcName, ren1.dstName), 'in', \
-                      branchName1 + '.', ren1.dstName, 'added in', branchName2
-                print 'Adding as', newPath, 'instead'
+                output('CONFLICT (rename/add): Rename',
+                       fmtRename(ren1.srcName, ren1.dstName), 'in',
+                       branchName1 + '.', ren1.dstName, 'added in', branchName2)
+                output('Adding as', newPath, 'instead')
                 updateFile(False, dstShaOtherBranch, dstModeOtherBranch, newPath)
                 cleanMerge = False
                 tryMerge = True
@@ -641,12 +648,12 @@ def processRenames(renamesA, renamesB, branchNameA, branchNameB):
                 dst2 = renames2.getDst(ren1.dstName)
                 newPath1 = uniquePath(ren1.dstName, branchName1)
                 newPath2 = uniquePath(dst2.dstName, branchName2)
-                print 'CONFLICT (rename/rename): Rename', \
-                      fmtRename(ren1.srcName, ren1.dstName), 'in', \
-                      branchName1+'. Rename', \
-                      fmtRename(dst2.srcName, dst2.dstName), 'in', branchName2
-                print 'Renaming', ren1.srcName, 'to', newPath1, 'and', \
-                      dst2.srcName, 'to', newPath2, 'instead'
+                output('CONFLICT (rename/rename): Rename',
+                       fmtRename(ren1.srcName, ren1.dstName), 'in',
+                       branchName1+'. Rename',
+                       fmtRename(dst2.srcName, dst2.dstName), 'in', branchName2)
+                output('Renaming', ren1.srcName, 'to', newPath1, 'and',
+                       dst2.srcName, 'to', newPath2, 'instead')
                 removeFile(False, ren1.dstName)
                 updateFile(False, ren1.dstSha, ren1.dstMode, newPath1)
                 updateFile(False, dst2.dstSha, dst2.dstMode, newPath2)
@@ -663,13 +670,14 @@ def processRenames(renamesA, renamesB, branchNameA, branchNameB):
                                    branchName1, branchName2)
 
                 if merge or not clean:
-                    print 'Renaming', fmtRename(ren1.srcName, ren1.dstName)
+                    output('Renaming', fmtRename(ren1.srcName, ren1.dstName))
 
                 if merge:
-                    print 'Auto-merging', ren1.dstName
+                    output('Auto-merging', ren1.dstName)
 
                 if not clean:
-                    print 'CONFLICT (rename/modify): Merge conflict in', ren1.dstName
+                    output('CONFLICT (rename/modify): Merge conflict in',
+                           ren1.dstName)
                     cleanMerge = False
 
                     if not cacheOnly:
@@ -714,21 +722,21 @@ def processEntry(entry, branch1Name, branch2Name):
            (not aSha     and bSha == oSha):
     # Deleted in both or deleted in one and unchanged in the other
             if aSha:
-                print 'Removing', path
+                output('Removing', path)
             removeFile(True, path)
         else:
     # Deleted in one and changed in the other
             cleanMerge = False
             if not aSha:
-                print 'CONFLICT (delete/modify):', path, 'deleted in', \
-                      branch1Name, 'and modified in', branch2Name + '.', \
-                      'Version', branch2Name, 'of', path, 'left in tree.'
+                output('CONFLICT (delete/modify):', path, 'deleted in',
+                       branch1Name, 'and modified in', branch2Name + '.',
+                       'Version', branch2Name, 'of', path, 'left in tree.')
                 mode = bMode
                 sha = bSha
             else:
-                print 'CONFLICT (modify/delete):', path, 'deleted in', \
-                      branch2Name, 'and modified in', branch1Name + '.', \
-                      'Version', branch1Name, 'of', path, 'left in tree.'
+                output('CONFLICT (modify/delete):', path, 'deleted in',
+                       branch2Name, 'and modified in', branch1Name + '.',
+                       'Version', branch1Name, 'of', path, 'left in tree.')
                 mode = aMode
                 sha = aSha
 
@@ -755,14 +763,14 @@ def processEntry(entry, branch1Name, branch2Name):
         if path in currentDirectorySet:
             cleanMerge = False
             newPath = uniquePath(path, addBranch)
-            print 'CONFLICT (' + conf + '):', \
-                  'There is a directory with name', path, 'in', \
-                  otherBranch + '. Adding', path, 'as', newPath
+            output('CONFLICT (' + conf + '):',
+                   'There is a directory with name', path, 'in',
+                   otherBranch + '. Adding', path, 'as', newPath)
 
             removeFile(False, path)
             updateFile(False, sha, mode, newPath)
         else:
-            print 'Adding', path
+            output('Adding', path)
             updateFile(True, sha, mode, path)
     
     elif not oSha and aSha and bSha:
@@ -772,10 +780,10 @@ def processEntry(entry, branch1Name, branch2Name):
         if aSha == bSha:
             if aMode != bMode:
                 cleanMerge = False
-                print 'CONFLICT: File', path, \
-                      'added identically in both branches, but permissions', \
-                      'conflict', '0%o' % aMode, '->', '0%o' % bMode
-                print 'CONFLICT: adding with permission:', '0%o' % aMode
+                output('CONFLICT: File', path,
+                       'added identically in both branches, but permissions',
+                       'conflict', '0%o' % aMode, '->', '0%o' % bMode)
+                output('CONFLICT: adding with permission:', '0%o' % aMode)
 
                 updateFile(False, aSha, aMode, path)
             else:
@@ -785,9 +793,9 @@ def processEntry(entry, branch1Name, branch2Name):
             cleanMerge = False
             newPath1 = uniquePath(path, branch1Name)
             newPath2 = uniquePath(path, branch2Name)
-            print 'CONFLICT (add/add): File', path, \
-                  'added non-identically in both branches. Adding as', \
-                  newPath1, 'and', newPath2, 'instead.'
+            output('CONFLICT (add/add): File', path,
+                   'added non-identically in both branches. Adding as',
+                   newPath1, 'and', newPath2, 'instead.')
             removeFile(False, path)
             updateFile(False, aSha, aMode, newPath1)
             updateFile(False, bSha, bMode, newPath2)
@@ -796,7 +804,7 @@ def processEntry(entry, branch1Name, branch2Name):
     #
     # case D: Modified in both, but differently.
     #
-        print 'Auto-merging', path
+        output('Auto-merging', path)
         [sha, mode, clean, dummy] = \
               mergeFile(path, oSha, oMode,
                         path, aSha, aMode,
@@ -806,7 +814,7 @@ def processEntry(entry, branch1Name, branch2Name):
             updateFile(True, sha, mode, path)
         else:
             cleanMerge = False
-            print 'CONFLICT (content): Merge conflict in', path
+            output('CONFLICT (content): Merge conflict in', path)
 
             if cacheOnly:
                 updateFile(False, sha, mode, path)
-- 
cgit v1.2.3


From 857f26d2f41e16170e48076758d974820af685ff Mon Sep 17 00:00:00 2001
From: Fredrik Kuivinen <freku045@student.liu.se>
Date: Sat, 12 Nov 2005 00:54:55 +0100
Subject: merge-recursive: Add copyright notice

Signed-off-by: Fredrik Kuivinen <freku045@student.liu.se>
Signed-off-by: Junio C Hamano <junkio@cox.net>
---
 git-merge-recursive.py | 3 +++
 gitMergeCommon.py      | 4 ++++
 2 files changed, 7 insertions(+)

diff --git a/git-merge-recursive.py b/git-merge-recursive.py
index e6cbdde71a..21f1e924f0 100755
--- a/git-merge-recursive.py
+++ b/git-merge-recursive.py
@@ -1,4 +1,7 @@
 #!/usr/bin/python
+#
+# Copyright (C) 2005 Fredrik Kuivinen
+#
 
 import sys, math, random, os, re, signal, tempfile, stat, errno, traceback
 from heapq import heappush, heappop
diff --git a/gitMergeCommon.py b/gitMergeCommon.py
index 1b5bddd467..ff6f58a07c 100644
--- a/gitMergeCommon.py
+++ b/gitMergeCommon.py
@@ -1,3 +1,7 @@
+#
+# Copyright (C) 2005 Fredrik Kuivinen
+#
+
 import sys, re, os, traceback
 from sets import Set
 
-- 
cgit v1.2.3


From e9af60c88bbd152ad04640ddb93dc927fc7a10b6 Mon Sep 17 00:00:00 2001
From: Fredrik Kuivinen <freku045@student.liu.se>
Date: Sat, 12 Nov 2005 00:55:36 +0100
Subject: merge-recursive: Use '~' instead of '_' to separate file names from
 branch names

Makes it less probable that we get a clash with an existing file,
furthermore Cogito already uses '~' for this purpose.

Signed-off-by: Fredrik Kuivinen <freku045@student.liu.se>
Signed-off-by: Junio C Hamano <junkio@cox.net>
---
 git-merge-recursive.py | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/git-merge-recursive.py b/git-merge-recursive.py
index 21f1e924f0..1bf73f336d 100755
--- a/git-merge-recursive.py
+++ b/git-merge-recursive.py
@@ -304,13 +304,13 @@ def uniquePath(path, branch):
                 raise
 
     branch = branch.replace('/', '_')
-    newPath = path + '_' + branch
+    newPath = path + '~' + branch
     suffix = 0
     while newPath in currentFileSet or \
           newPath in currentDirectorySet  or \
           fileExists(newPath):
         suffix += 1
-        newPath = path + '_' + branch + '_' + str(suffix)
+        newPath = path + '~' + branch + '_' + str(suffix)
     currentFileSet.add(newPath)
     return newPath
 
-- 
cgit v1.2.3


From 6fd72e39af8a69615d32c3fd4d5fe0788f54a2ea Mon Sep 17 00:00:00 2001
From: Petr Baudis <pasky@suse.cz>
Date: Sat, 12 Nov 2005 01:49:59 +0100
Subject: Show URL in the "Getting <foo> list" http-fetch messages

Signed-off-by: Petr Baudis <pasky@suse.cz>
Signed-off-by: Junio C Hamano <junkio@cox.net>
---
 http-fetch.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/http-fetch.c b/http-fetch.c
index 99921cc8da..f39e748fc0 100644
--- a/http-fetch.c
+++ b/http-fetch.c
@@ -788,7 +788,7 @@ static int fetch_alternates(char *base)
 	buffer.buffer = data;
 
 	if (get_verbosely)
-		fprintf(stderr, "Getting alternates list\n");
+		fprintf(stderr, "Getting alternates list for %s\n", base);
 	
 	url = xmalloc(strlen(base) + 31);
 	sprintf(url, "%s/objects/info/http-alternates", base);
@@ -911,7 +911,7 @@ static int fetch_indices(struct alt_base *repo)
 	buffer.buffer = data;
 
 	if (get_verbosely)
-		fprintf(stderr, "Getting pack list\n");
+		fprintf(stderr, "Getting pack list for %s\n", repo->base);
 	
 	url = xmalloc(strlen(repo->base) + 21);
 	sprintf(url, "%s/objects/info/packs", repo->base);
-- 
cgit v1.2.3


From f7d24bbefb06c40f7738f471dda561ab45496d24 Mon Sep 17 00:00:00 2001
From: Junio C Hamano <junkio@cox.net>
Date: Mon, 7 Nov 2005 22:03:46 -0800
Subject: merge with /dev/null as base, instead of punting O==empty case

Instead of leaving the path unmerged in a case where each side
adds different version of the same path, attempt to merge it
with empty base and leave "our" version in the index file, just
like we do for the case in conflicting merge.

Signed-off-by: Junio C Hamano <junkio@cox.net>
---
 git-merge-one-file.sh | 20 ++++++++++++++++----
 1 file changed, 16 insertions(+), 4 deletions(-)

diff --git a/git-merge-one-file.sh b/git-merge-one-file.sh
index 5419e598c5..32e17cbc61 100755
--- a/git-merge-one-file.sh
+++ b/git-merge-one-file.sh
@@ -40,7 +40,7 @@ case "${1:-.}${2:-.}${3:-.}" in
 	;;
 
 #
-# Added in both (check for same permissions).
+# Added in both, identically (check for same permissions).
 #
 ".$3$2")
 	if [ "$6" != "$7" ]; then
@@ -56,9 +56,18 @@ case "${1:-.}${2:-.}${3:-.}" in
 #
 # Modified in both, but differently.
 #
-"$1$2$3")
-	echo "Auto-merging $4."
-	orig=`git-unpack-file $1`
+"$1$2$3" | ".$2$3")
+	case "$1" in
+	'')
+		echo "Added $4 in both, but differently."
+		orig=`git-unpack-file $2`
+		: >$orig
+		;;
+	*)
+		echo "Auto-merging $4."
+		orig=`git-unpack-file $1`
+		;;
+	esac
 	src2=`git-unpack-file $3`
 
 	# We reset the index to the first branch, making
@@ -73,6 +82,9 @@ case "${1:-.}${2:-.}${3:-.}" in
 		echo "ERROR: Permissions conflict: $5->$6,$7."
 		ret=1
 	fi
+	if [ "$1" = '' ]; then
+		ret=1
+	fi
 
 	if [ $ret -ne 0 ]; then
 		echo "ERROR: Merge conflict in $4."
-- 
cgit v1.2.3


From cb93c19365760d939f05d9a3c2ef4499f0d5ce16 Mon Sep 17 00:00:00 2001
From: Junio C Hamano <junkio@cox.net>
Date: Wed, 9 Nov 2005 20:38:33 -0800
Subject: merge-one-file: use common as base, instead of emptiness.

Unlike the previous round that merged the path added differently
in each branches using emptiness as the base, compute a common
version and use it as input to 'merge' program.

This would show the resulting (still conflicting) file left in
the working tree as:

	common file contents...
	<<<<<< FILENAME
	version from our branch...
	======
	version from their branch...
	>>>>>> .merge_file_XXXXXX
	more common file contents...

when both sides added similar contents.

Signed-off-by: Junio C Hamano <junkio@cox.net>
---
 apply.c               | 11 +++++++++--
 git-merge-one-file.sh |  6 ++++--
 2 files changed, 13 insertions(+), 4 deletions(-)

diff --git a/apply.c b/apply.c
index cf8aa87a28..472bcdc369 100644
--- a/apply.c
+++ b/apply.c
@@ -23,6 +23,7 @@ static int numstat = 0;
 static int summary = 0;
 static int check = 0;
 static int apply = 1;
+static int no_add = 0;
 static int show_index_info = 0;
 static int line_termination = '\n';
 static const char apply_usage[] =
@@ -1112,8 +1113,10 @@ static int apply_one_fragment(struct buffer_desc *desc, struct fragment *frag)
 				break;
 		/* Fall-through for ' ' */
 		case '+':
-			memcpy(new + newsize, patch + 1, plen);
-			newsize += plen;
+			if (*patch != '+' || !no_add) {
+				memcpy(new + newsize, patch + 1, plen);
+				newsize += plen;
+			}
 			break;
 		case '@': case '\\':
 			/* Ignore it, we already handled it */
@@ -1710,6 +1713,10 @@ int main(int argc, char **argv)
 			excludes = x;
 			continue;
 		}
+		if (!strcmp(arg, "--no-add")) {
+			no_add = 1;
+			continue;
+		}
 		if (!strcmp(arg, "--stat")) {
 			apply = 0;
 			diffstat = 1;
diff --git a/git-merge-one-file.sh b/git-merge-one-file.sh
index 32e17cbc61..d9ee458150 100755
--- a/git-merge-one-file.sh
+++ b/git-merge-one-file.sh
@@ -57,18 +57,20 @@ case "${1:-.}${2:-.}${3:-.}" in
 # Modified in both, but differently.
 #
 "$1$2$3" | ".$2$3")
+	src2=`git-unpack-file $3`
 	case "$1" in
 	'')
 		echo "Added $4 in both, but differently."
+		# This extracts OUR file in $orig, and uses git-apply to
+		# remove lines that are unique to ours.
 		orig=`git-unpack-file $2`
-		: >$orig
+		diff -u -La/$orig -Lb/$orig $orig $src2 | git-apply --no-add 
 		;;
 	*)
 		echo "Auto-merging $4."
 		orig=`git-unpack-file $1`
 		;;
 	esac
-	src2=`git-unpack-file $3`
 
 	# We reset the index to the first branch, making
 	# git-diff-file useful
-- 
cgit v1.2.3


From e433705dd4dc52c45e5d82b615f07b5a4b27f185 Mon Sep 17 00:00:00 2001
From: Junio C Hamano <junkio@cox.net>
Date: Wed, 9 Nov 2005 20:53:54 -0800
Subject: Documentation: git-apply --no-add

This is a specialized hack to help no-base merges, but other
people might find it useful, so let's document it.

Signed-off-by: Junio C Hamano <junkio@cox.net>
---
 Documentation/git-apply.txt | 8 +++++++-
 apply.c                     | 2 +-
 2 files changed, 8 insertions(+), 2 deletions(-)

diff --git a/Documentation/git-apply.txt b/Documentation/git-apply.txt
index eb8f906837..6702a18c7e 100644
--- a/Documentation/git-apply.txt
+++ b/Documentation/git-apply.txt
@@ -8,7 +8,7 @@ git-apply - Apply patch on a git index file and a work tree
 
 SYNOPSIS
 --------
-'git-apply' [--stat] [--numstat] [--summary] [--check] [--index] [--apply] [--index-info] [-z] [<patch>...]
+'git-apply' [--stat] [--numstat] [--summary] [--check] [--index] [--apply] [--no-add] [--index-info] [-z] [<patch>...]
 
 DESCRIPTION
 -----------
@@ -72,6 +72,12 @@ OPTIONS
 	patch.  Give this flag after those flags to also apply
 	the patch.
 
+--no-add::
+	When applying a patch, ignore additions made by the
+	patch.  This can be used to extract common part between
+	two files by first running `diff` on them and applying
+	the result with this option, which would apply the
+	deletion part but not addition part.
 
 Author
 ------
diff --git a/apply.c b/apply.c
index 472bcdc369..34181188b8 100644
--- a/apply.c
+++ b/apply.c
@@ -27,7 +27,7 @@ static int no_add = 0;
 static int show_index_info = 0;
 static int line_termination = '\n';
 static const char apply_usage[] =
-"git-apply [--stat] [--numstat] [--summary] [--check] [--index] [--apply] [--index-info] [-z] <patch>...";
+"git-apply [--stat] [--numstat] [--summary] [--check] [--index] [--apply] [--no-add] [--index-info] [-z] <patch>...";
 
 /*
  * For "diff-stat" like behaviour, we keep track of the biggest change
-- 
cgit v1.2.3


From fd66dbf5297a4badec8c2accf8a0f9bd72e3f693 Mon Sep 17 00:00:00 2001
From: Junio C Hamano <junkio@cox.net>
Date: Thu, 10 Nov 2005 19:30:23 -0800
Subject: merge-one-file: use empty- or common-base condintionally in two-stage
 merge.

If two sides added the same path completely different thing, it is
easier to see the merge pivoting on /dev/null.  So check the size of
the common section we have found, and empty it if it is too small.

Signed-off-by: Junio C Hamano <junkio@cox.net>
---
 git-merge-one-file.sh | 6 ++++++
 1 file changed, 6 insertions(+)

diff --git a/git-merge-one-file.sh b/git-merge-one-file.sh
index d9ee458150..b08597de29 100755
--- a/git-merge-one-file.sh
+++ b/git-merge-one-file.sh
@@ -64,7 +64,13 @@ case "${1:-.}${2:-.}${3:-.}" in
 		# This extracts OUR file in $orig, and uses git-apply to
 		# remove lines that are unique to ours.
 		orig=`git-unpack-file $2`
+		sz0=`wc -c <"$orig"`
 		diff -u -La/$orig -Lb/$orig $orig $src2 | git-apply --no-add 
+		sz1=`wc -c <"$orig"`
+
+		# If we do not have enough common material, it is not
+		# worth trying two-file merge using common subsections.
+		expr "$sz0" \< "$sz1" \* 2 >/dev/null || : >$orig
 		;;
 	*)
 		echo "Auto-merging $4."
-- 
cgit v1.2.3


From c283ab21c1b8198fe2297cca678aa2fa3dd76e75 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Lukas=5FSandstr=C3=B6m?= <lukass@etek.chalmers.se>
Date: Wed, 9 Nov 2005 02:22:40 +0100
Subject: Add git-pack-intersect
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

This patch adds the program git-pack-intersect. It is
used to find redundant packs in git repositories.

Signed-off-by: Lukas Sandström <lukass@etek.chalmers.se>
Signed-off-by: Junio C Hamano <junkio@cox.net>
---
 Makefile         |   2 +-
 pack-intersect.c | 577 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
 sha1_file.c      |   3 +
 3 files changed, 581 insertions(+), 1 deletion(-)
 create mode 100644 pack-intersect.c

diff --git a/Makefile b/Makefile
index b202be177b..4c646c9e84 100644
--- a/Makefile
+++ b/Makefile
@@ -122,7 +122,7 @@ PROGRAMS = \
 	git-unpack-objects$X git-update-index$X git-update-server-info$X \
 	git-upload-pack$X git-verify-pack$X git-write-tree$X \
 	git-update-ref$X git-symbolic-ref$X git-check-ref-format$X \
-	git-name-rev$X $(SIMPLE_PROGRAMS)
+	git-name-rev$X git-pack-intersect$X $(SIMPLE_PROGRAMS)
 
 # Backward compatibility -- to be removed after 1.0
 PROGRAMS += git-ssh-pull$X git-ssh-push$X
diff --git a/pack-intersect.c b/pack-intersect.c
new file mode 100644
index 0000000000..2267478c36
--- /dev/null
+++ b/pack-intersect.c
@@ -0,0 +1,577 @@
+/*
+*
+* Copyright 2005, Lukas Sandstrom <lukass@etek.chalmers.se>
+*
+* This file is licensed under the GPL v2.
+*
+*/
+
+#include "cache.h"
+
+static const char pack_intersect_usage[] =
+"git-pack-intersect [ -v ]  < -a | <.pack filename> ...>";
+
+int all = 0, verbose = 0;
+
+struct llist_item {
+	struct llist_item *next;
+	char *sha1;
+};
+struct llist {
+	struct llist_item *front;
+	struct llist_item *back;
+	size_t size;
+} *all_objects;
+
+struct pack_list {
+	struct pack_list *next;
+	struct packed_git *pack;
+	struct llist *unique_objects;
+	struct llist *all_objects;
+} *pack_list;
+
+struct pll {
+	struct pll *next;
+	struct pack_list *pl;
+};
+
+inline void llist_free(struct llist *list)
+{
+	while((list->back = list->front)) {
+		list->front = list->front->next;
+		free(list->back);
+	}
+	free(list);
+}
+
+inline void llist_init(struct llist **list)
+{
+	*list = xmalloc(sizeof(struct llist));
+	(*list)->front = (*list)->back = NULL;
+	(*list)->size = 0;
+}
+
+struct llist * llist_copy(struct llist *list)
+{
+	struct llist *ret;
+	struct llist_item *new, *old, *prev;
+	
+	llist_init(&ret);
+
+	if ((ret->size = list->size) == 0)
+		return ret;
+
+	new = ret->front = xmalloc(sizeof(struct llist_item));
+	new->sha1 = list->front->sha1;
+
+	old = list->front->next;
+	while (old) {
+		prev = new;
+		new = xmalloc(sizeof(struct llist_item));
+		prev->next = new;
+		new->sha1 = old->sha1;
+		old = old->next;
+	}
+	new->next = NULL;
+	ret->back = new;
+	
+	return ret;
+}
+
+inline struct llist_item * llist_insert(struct llist *list,
+					struct llist_item *after, char *sha1)
+{
+	struct llist_item *new = xmalloc(sizeof(struct llist_item));
+	new->sha1 = sha1;
+	new->next = NULL;
+
+	if (after != NULL) {
+		new->next = after->next;
+		after->next = new;
+		if (after == list->back)
+			list->back = new;
+	} else {/* insert in front */
+		if (list->size == 0)
+			list->back = new;
+		else
+			new->next = list->front;
+		list->front = new;
+	}
+	list->size++;
+	return new;
+}
+
+inline struct llist_item * llist_insert_back(struct llist *list, char *sha1)
+{
+	return llist_insert(list, list->back, sha1);
+}
+
+inline struct llist_item * llist_insert_sorted_unique(struct llist *list,
+					char *sha1, struct llist_item *hint)
+{
+	struct llist_item *prev = NULL, *l;
+
+	l = (hint == NULL) ? list->front : hint;
+	while (l) {
+		int cmp = memcmp(l->sha1, sha1, 20);
+		if (cmp > 0) { /* we insert before this entry */
+			return llist_insert(list, prev, sha1);
+		}
+		if(!cmp) { /* already exists */
+			return l;
+		}
+		prev = l;
+		l = l->next;
+	}
+	/* insert at the end */
+	return llist_insert_back(list, sha1);
+}
+
+/* computes A\B */
+struct llist * llist_sorted_difference(struct llist_item *A,
+				       struct llist_item *B)
+{
+	struct llist *ret;
+	llist_init(&ret);
+
+	while (A != NULL && B != NULL) {
+		int cmp = memcmp(A->sha1, B->sha1, 20);
+		if (!cmp) {
+			A = A->next;
+			B = B->next;
+			continue;
+		}
+		if(cmp > 0) { /* we'll never find this B */
+			B = B->next;
+			continue;
+		}
+		/* A has the object, B doesn't */
+		llist_insert_back(ret, A->sha1);
+		A = A->next;
+	}
+	while (A != NULL) {
+		llist_insert_back(ret, A->sha1);
+		A = A->next;
+	}
+	return ret;
+}
+
+/* returns a pointer to an item in front of sha1 */
+inline struct llist_item * llist_sorted_remove(struct llist *list, char *sha1,
+					       struct llist_item *hint)
+{
+	struct llist_item *prev, *l;
+
+redo_from_start:
+	l = (hint == NULL) ? list->front : hint;
+	prev = NULL;
+	while (l) {
+		int cmp = memcmp(l->sha1, sha1, 20);
+		if (cmp > 0) /* not in list, since sorted */
+			return prev;
+		if(!cmp) { /* found */
+			if (prev == NULL) {
+				if (hint != NULL && hint != list->front) {
+					/* we don't know the previous element */
+					hint = NULL;
+					goto redo_from_start;
+				}
+				list->front = l->next;
+			} else
+				prev->next = l->next;
+			if (l == list->back)
+				list->back = prev;
+			free(l);
+			list->size--;
+			return prev;
+		}
+		prev = l;
+		l = l->next;
+	}
+	return prev;
+}
+
+inline struct pack_list * pack_list_insert(struct pack_list **pl,
+					   struct pack_list *entry)
+{
+	struct pack_list *p = xmalloc(sizeof(struct pack_list));
+	memcpy(p, entry, sizeof(struct pack_list));
+	p->next = *pl;
+	*pl = p;
+	return p;
+}
+
+struct pack_list * pack_list_difference(struct pack_list *A,
+					struct pack_list *B)
+{
+	struct pack_list *ret, *pl;
+
+	if (A == NULL)
+		return NULL;
+
+	pl = B;
+	while (pl != NULL) {
+		if (A->pack == pl->pack)
+			return pack_list_difference(A->next, B);
+		pl = pl->next;
+	}
+	ret = xmalloc(sizeof(struct pack_list));
+	memcpy(ret, A, sizeof(struct pack_list));
+	ret->next = pack_list_difference(A->next, B);
+	return ret;
+}
+
+void cmp_two_packs(struct pack_list *p1, struct pack_list *p2)
+{
+	int p1_off, p2_off;
+	void *p1_base, *p2_base;
+	struct llist_item *p1_hint = NULL, *p2_hint = NULL;
+	
+	p1_off = p2_off = 256 * 4 + 4;
+	p1_base = (void *)p1->pack->index_base;
+	p2_base = (void *)p2->pack->index_base;
+
+	while (p1_off <= p1->pack->index_size - 3 * 20 &&
+	       p2_off <= p2->pack->index_size - 3 * 20)
+	{
+		int cmp = memcmp(p1_base + p1_off, p2_base + p2_off, 20);
+		/* cmp ~ p1 - p2 */
+		if (cmp == 0) {
+			p1_hint = llist_sorted_remove(p1->unique_objects,
+					p1_base + p1_off, p1_hint);
+			p2_hint = llist_sorted_remove(p2->unique_objects,
+					p1_base + p1_off, p2_hint);
+			p1_off+=24;
+			p2_off+=24;
+			continue;
+		}
+		if (cmp < 0) { /* p1 has the object, p2 doesn't */
+			p1_off+=24;
+		} else { /* p2 has the object, p1 doesn't */
+			p2_off+=24;
+		}
+	}
+}
+
+/* all the permutations have to be free()d at the same time,
+ * since they refer to each other
+ */
+struct pll * get_all_permutations(struct pack_list *list)
+{
+	struct pll *subset, *pll, *new_pll = NULL; /*silence warning*/
+
+	if (list == NULL)
+		return NULL;
+
+	if (list->next == NULL) {
+		new_pll = xmalloc(sizeof(struct pll));
+		new_pll->next = NULL;
+		new_pll->pl = list;
+		return new_pll;
+	}
+
+	pll = subset = get_all_permutations(list->next);
+	while (pll) {
+		new_pll = xmalloc(sizeof(struct pll));
+		new_pll->next = pll->next;
+		pll->next = new_pll;
+
+		new_pll->pl = xmalloc(sizeof(struct pack_list));
+		memcpy(new_pll->pl, list, sizeof(struct pack_list));
+		new_pll->pl->next = pll->pl;
+
+		pll = new_pll->next;
+	}
+	/* add ourself to the end */
+	new_pll->next = xmalloc(sizeof(struct pll));
+	new_pll->next->pl = xmalloc(sizeof(struct pack_list));
+	new_pll->next->next = NULL;
+	memcpy(new_pll->next->pl, list, sizeof(struct pack_list));
+	new_pll->next->pl->next = NULL;
+
+	return subset;
+}
+
+int is_superset(struct pack_list *pl, struct llist *list)
+{
+	struct llist *diff, *old;
+
+	diff = llist_copy(list);
+
+	while (pl) {
+		old = diff;
+		diff = llist_sorted_difference(diff->front,
+					       pl->all_objects->front);
+		llist_free(old);
+		if (diff->size == 0) { /* we're done */
+			llist_free(diff);
+			return 1;
+		}
+		pl = pl->next;
+	}
+	llist_free(diff);
+	return 0;
+}
+
+size_t sizeof_union(struct packed_git *p1, struct packed_git *p2)
+{
+	size_t ret = 0;
+	int p1_off, p2_off;
+	void *p1_base, *p2_base;
+
+	p1_off = p2_off = 256 * 4 + 4;
+	p1_base = (void *)p1->index_base;
+	p2_base = (void *)p2->index_base;
+
+	while (p1_off <= p1->index_size - 3 * 20 &&
+	       p2_off <= p2->index_size - 3 * 20)
+	{
+		int cmp = memcmp(p1_base + p1_off, p2_base + p2_off, 20);
+		/* cmp ~ p1 - p2 */
+		if (cmp == 0) {
+			ret++;
+			p1_off+=24;
+			p2_off+=24;
+			continue;
+		}
+		if (cmp < 0) { /* p1 has the object, p2 doesn't */
+			p1_off+=24;
+		} else { /* p2 has the object, p1 doesn't */
+			p2_off+=24;
+		}
+	}
+	return ret;
+}
+
+/* another O(n^2) function ... */
+size_t get_pack_redundancy(struct pack_list *pl)
+{
+	struct pack_list *subset;
+	size_t ret = 0;
+	while ((subset = pl->next)) {
+		while(subset) {
+			ret += sizeof_union(pl->pack, subset->pack);
+			subset = subset->next;
+		}
+		pl = pl->next;
+	}
+	return ret;
+}
+
+inline size_t pack_set_bytecount(struct pack_list *pl)
+{
+	size_t ret = 0;
+	while (pl) {
+		ret += pl->pack->pack_size;
+		ret += pl->pack->index_size;
+		pl = pl->next;
+	}
+	return ret;
+}
+
+void minimize(struct pack_list **min)
+{
+	struct pack_list *pl, *unique = NULL,
+		*non_unique = NULL, *min_perm = NULL;
+	struct pll *perm, *perm_all, *perm_ok = NULL, *new_perm;
+	struct llist *missing, *old;
+	size_t min_perm_size = (size_t)-1, perm_size;
+
+	pl = pack_list;
+	while (pl) {
+		if(pl->unique_objects->size)
+			pack_list_insert(&unique, pl);
+		else
+			pack_list_insert(&non_unique, pl);
+		pl = pl->next;
+	}
+	/* find out which objects are missing from the set of unique packs */
+	missing = llist_copy(all_objects);
+	pl = unique;
+	while (pl) {
+		old = missing;
+		missing = llist_sorted_difference(missing->front,
+						  pl->all_objects->front);
+		llist_free(old);
+		pl = pl->next;
+	}
+
+	if (missing->size == 0) {
+		*min = unique;
+		return;
+	}
+
+	/* find the permutations which contain all missing objects */
+	perm_all = perm = get_all_permutations(non_unique);
+	while (perm) {
+		if (is_superset(perm->pl, missing)) {
+			new_perm = xmalloc(sizeof(struct pll));
+			new_perm->pl = perm->pl;
+			new_perm->next = perm_ok;
+			perm_ok = new_perm;
+		}
+		perm = perm->next;
+	}
+	
+	if (perm_ok == NULL)
+		die("Internal error: No complete sets found!\n");
+
+	/* find the permutation with the smallest size */
+	perm = perm_ok;
+	while (perm) {
+		perm_size = pack_set_bytecount(perm->pl);
+		if (min_perm_size > perm_size) {
+			min_perm_size = perm_size;
+			min_perm = perm->pl;
+		}
+		perm = perm->next;
+	}
+	*min = min_perm;
+	/* add the unique packs to the list */
+	pl = unique;
+	while(pl) {
+		pack_list_insert(min, pl);
+		pl = pl->next;
+	}
+}
+
+void load_all_objects()
+{
+	struct pack_list *pl = pack_list;
+	struct llist_item *hint, *l;
+	int i;
+
+	llist_init(&all_objects);
+
+	while (pl) {
+		i = 0;
+		hint = NULL;
+		l = pl->all_objects->front;
+		while (l) {
+			hint = llist_insert_sorted_unique(all_objects,
+							  l->sha1, hint);
+			l = l->next;
+		}
+		pl = pl->next;
+	}
+}
+
+/* this scales like O(n^2) */
+void cmp_packs()
+{
+	struct pack_list *subset, *curr = pack_list;
+
+	while ((subset = curr)) {
+		while((subset = subset->next))
+			cmp_two_packs(curr, subset);
+		curr = curr->next;
+	}
+}
+
+struct pack_list * add_pack(struct packed_git *p)
+{
+	struct pack_list l;
+	size_t off;
+	void *base;
+
+	l.pack = p;
+	llist_init(&l.all_objects);
+
+	off = 256 * 4 + 4;
+	base = (void *)p->index_base;
+	while (off <= p->index_size - 3 * 20) {
+		llist_insert_back(l.all_objects, base + off);
+		off+=24;
+	}
+	/* this list will be pruned in cmp_two_packs later */
+	l.unique_objects = llist_copy(l.all_objects);
+	return pack_list_insert(&pack_list, &l);
+}
+
+struct pack_list * add_pack_file(char *filename)
+{
+	struct packed_git *p = packed_git;
+
+	if (strlen(filename) < 40)
+		die("Bad pack filename: %s\n", filename);
+
+	while (p) {
+		if (strstr(p->pack_name, filename))
+			/* this will silently ignore packs in alt-odb */
+			return add_pack(p);
+		p = p->next;
+	}
+	die("Filename %s not found in packed_git\n", filename);
+}
+
+void load_all()
+{
+	struct packed_git *p = packed_git;
+
+	while (p) {
+		if (p->pack_local) /* ignore alt-odb for now */
+			add_pack(p);
+		p = p->next;
+	}
+}
+
+int main(int argc, char **argv)
+{
+	int i;
+	struct pack_list *min, *red, *pl;
+
+	for (i = 1; i < argc; i++) {
+		const char *arg = argv[i];
+		if(!strcmp(arg, "--"))
+			break;
+		if(!strcmp(arg, "-a")) {
+			all = 1;
+			continue;
+		}
+		if(!strcmp(arg, "-v")) {
+			verbose = 1;
+			continue;
+		}
+		if(*arg == '-')
+			usage(pack_intersect_usage);
+		else
+			break;
+	}
+
+	prepare_packed_git();
+
+	if(all)
+		load_all();
+	else
+		while (*(argv + i) != NULL)
+			add_pack_file(*(argv + i++));
+
+	if (pack_list == NULL)
+		die("Zero packs found!\n");
+
+	cmp_packs();
+
+	load_all_objects();
+
+	minimize(&min);
+	if (verbose) {
+		fprintf(stderr, "The smallest (bytewise) set of packs is:\n");
+		pl = min;
+		while (pl) {
+			fprintf(stderr, "\t%s\n", pl->pack->pack_name);
+			pl = pl->next;
+		}
+		fprintf(stderr, "containing %ld duplicate objects "
+				"with a total size of %ldkb.\n",
+			get_pack_redundancy(min), pack_set_bytecount(min)/1024);
+		fprintf(stderr, "Redundant packs (with indexes):\n");
+	}
+	pl = red = pack_list_difference(pack_list, min);
+	while (pl) {
+		printf("%s\n%s\n",
+		       sha1_pack_index_name(pl->pack->sha1), pl->pack->pack_name);
+		pl = pl->next;
+	}
+
+	return 0;
+}
diff --git a/sha1_file.c b/sha1_file.c
index 946a35346b..cd814d7233 100644
--- a/sha1_file.c
+++ b/sha1_file.c
@@ -424,6 +424,7 @@ struct packed_git *add_packed_git(char *path, int path_len, int local)
 	struct packed_git *p;
 	unsigned long idx_size;
 	void *idx_map;
+	char sha1[20];
 
 	if (check_packed_git_idx(path, &idx_size, &idx_map))
 		return NULL;
@@ -447,6 +448,8 @@ struct packed_git *add_packed_git(char *path, int path_len, int local)
 	p->pack_last_used = 0;
 	p->pack_use_cnt = 0;
 	p->pack_local = local;
+	if (!get_sha1_hex(path + path_len - 40 - 4, sha1))
+		memcpy(p->sha1, sha1, 20);
 	return p;
 }
 
-- 
cgit v1.2.3


From 2a444781b1a9de1eb8e2cd24eea36a0f635519fe Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Lukas=5FSandstr=C3=B6m?= <lukass@etek.chalmers.se>
Date: Wed, 9 Nov 2005 02:23:55 +0100
Subject: Add documentation for git-pack-intersect
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

Signed-off-by: Lukas Sandström <lukass@etek.chalmers.se>
Signed-off-by: Junio C Hamano <junkio@cox.net>
---
 Documentation/git-pack-intersect.txt | 47 ++++++++++++++++++++++++++++++++++++
 1 file changed, 47 insertions(+)
 create mode 100644 Documentation/git-pack-intersect.txt

diff --git a/Documentation/git-pack-intersect.txt b/Documentation/git-pack-intersect.txt
new file mode 100644
index 0000000000..e5d6fc7d3d
--- /dev/null
+++ b/Documentation/git-pack-intersect.txt
@@ -0,0 +1,47 @@
+git-pack-intersect(1)
+=====================
+
+NAME
+----
+git-pack-intersect - Program used to find redundant pack files.
+
+
+SYNOPSIS
+--------
+'git-pack-intersect [ -v ] < -a | .pack filename ... >'
+
+DESCRIPTION
+-----------
+This program computes which packs in your repository
+are redundant. The output is suitable for piping to
+'xargs rm' if you are in the root of the repository.
+
+OPTIONS
+-------
+
+-v::
+	Verbose. Outputs some statistics to stderr.
+	Has a small performance penalty.
+
+-a::
+	All. Processes all the local packs. Any filenames on
+	the commandline are ignored.
+
+Author
+------
+Written by Lukas Sandström <lukass@etek.chalmers.se>
+
+Documentation
+--------------
+Documentation by Lukas Sandström <lukass@etek.chalmers.se>
+
+See-Also
+--------
+gitlink:git-pack-objects[1]
+gitlink:git-repack[1]
+gitlink:git-prune-packed[1]
+
+GIT
+---
+Part of the gitlink:git[7] suite
+
-- 
cgit v1.2.3


From 523114820233f87b663513ee0bf52a6f7fdd9cfc Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Lukas=5FSandstr=C3=B6m?= <lukass@etek.chalmers.se>
Date: Wed, 9 Nov 2005 02:24:51 +0100
Subject: Add git-pack-intersect to .gitignore
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

Signed-off-by: Lukas Sandström <lukass@etek.chalmers.se>
Signed-off-by: Junio C Hamano <junkio@cox.net>
---
 .gitignore | 1 +
 1 file changed, 1 insertion(+)

diff --git a/.gitignore b/.gitignore
index 716c340a22..6ff25300e1 100644
--- a/.gitignore
+++ b/.gitignore
@@ -60,6 +60,7 @@ git-mktag
 git-name-rev
 git-mv
 git-octopus
+git-pack-intersect
 git-pack-objects
 git-parse-remote
 git-patch-id
-- 
cgit v1.2.3


From b4ad3552de8b3231b55f5ee32ee2178202708118 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Lukas=5FSandstr=C3=B6m?= <lukass@etek.chalmers.se>
Date: Wed, 9 Nov 2005 02:25:48 +0100
Subject: Make git-repack use git-pack-intersect.
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

Signed-off-by: Lukas Sandström <lukass@etek.chalmers.se>
Signed-off-by: Junio C Hamano <junkio@cox.net>
---
 git-repack.sh | 30 ++++++++++++------------------
 1 file changed, 12 insertions(+), 18 deletions(-)

diff --git a/git-repack.sh b/git-repack.sh
index d341966efb..3f28300566 100755
--- a/git-repack.sh
+++ b/git-repack.sh
@@ -32,10 +32,6 @@ case ",$all_into_one," in
 	rev_list=
 	rev_parse='--all'
 	pack_objects=
-	# This part is a stop-gap until we have proper pack redundancy
-	# checker.
-	existing=`cd "$PACKDIR" && \
-	    find . -type f \( -name '*.pack' -o -name '*.idx' \) -print`
 	;;
 esac
 if [ "$local" ]; then
@@ -46,6 +42,14 @@ name=$(git-rev-list --objects $rev_list $(git-rev-parse $rev_parse) |
 	exit 1
 if [ -z "$name" ]; then
 	echo Nothing new to pack.
+	if test "$remove_redandant" = t ; then
+		echo "Removing redundant packs."
+		sync
+		redundant=$(git-pack-intersect -a)
+		if test "$redundant" != "" ; then
+			echo $redundant | xargs rm
+		fi
+	fi
 	exit 0
 fi
 echo "Pack pack-$name created."
@@ -58,20 +62,10 @@ exit
 
 if test "$remove_redandant" = t
 then
-	# We know $existing are all redandant only when
-	# all-into-one is used.
-	if test "$all_into_one" != '' && test "$existing" != ''
-	then
-		sync
-		( cd "$PACKDIR" &&
-		  for e in $existing
-		  do
-			case "$e" in
-			./pack-$name.pack | ./pack-$name.idx) ;;
-			*)	rm -f $e ;;
-			esac
-		  done
-		)
+	sync
+	redundant=$(git-pack-intersect -a)
+	if test "$redundant" != "" ; then
+		echo $redundant | xargs rm
 	fi
 fi
 
-- 
cgit v1.2.3


From 9bc0f32c77b755b8d77d215cc47fafff53cad6f5 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Lukas=5FSandstr=C3=B6m?= <lukass@etek.chalmers.se>
Date: Thu, 10 Nov 2005 00:16:13 +0100
Subject: Rename git-pack-intersect to git-pack-redundant
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

This patch renames git-pack-intersect to git-pack-redundant
as suggested by Petr Baudis. The new name reflects what the
program does, rather than how it does it.

Also fix a small argument parsing bug.

Signed-off-by: Lukas Sandström <lukass@etek.chalmers.se>
Signed-off-by: Junio C Hamano <junkio@cox.net>
---
 .gitignore                           |   2 +-
 Documentation/git-pack-intersect.txt |  47 ---
 Documentation/git-pack-redundant.txt |  47 +++
 Makefile                             |   2 +-
 git-repack.sh                        |   4 +-
 pack-intersect.c                     | 577 ----------------------------------
 pack-redundant.c                     | 579 +++++++++++++++++++++++++++++++++++
 7 files changed, 630 insertions(+), 628 deletions(-)
 delete mode 100644 Documentation/git-pack-intersect.txt
 create mode 100644 Documentation/git-pack-redundant.txt
 delete mode 100644 pack-intersect.c
 create mode 100644 pack-redundant.c

diff --git a/.gitignore b/.gitignore
index 6ff25300e1..1d1aa57676 100644
--- a/.gitignore
+++ b/.gitignore
@@ -60,7 +60,7 @@ git-mktag
 git-name-rev
 git-mv
 git-octopus
-git-pack-intersect
+git-pack-redundant
 git-pack-objects
 git-parse-remote
 git-patch-id
diff --git a/Documentation/git-pack-intersect.txt b/Documentation/git-pack-intersect.txt
deleted file mode 100644
index e5d6fc7d3d..0000000000
--- a/Documentation/git-pack-intersect.txt
+++ /dev/null
@@ -1,47 +0,0 @@
-git-pack-intersect(1)
-=====================
-
-NAME
-----
-git-pack-intersect - Program used to find redundant pack files.
-
-
-SYNOPSIS
---------
-'git-pack-intersect [ -v ] < -a | .pack filename ... >'
-
-DESCRIPTION
------------
-This program computes which packs in your repository
-are redundant. The output is suitable for piping to
-'xargs rm' if you are in the root of the repository.
-
-OPTIONS
--------
-
--v::
-	Verbose. Outputs some statistics to stderr.
-	Has a small performance penalty.
-
--a::
-	All. Processes all the local packs. Any filenames on
-	the commandline are ignored.
-
-Author
-------
-Written by Lukas Sandström <lukass@etek.chalmers.se>
-
-Documentation
---------------
-Documentation by Lukas Sandström <lukass@etek.chalmers.se>
-
-See-Also
---------
-gitlink:git-pack-objects[1]
-gitlink:git-repack[1]
-gitlink:git-prune-packed[1]
-
-GIT
----
-Part of the gitlink:git[7] suite
-
diff --git a/Documentation/git-pack-redundant.txt b/Documentation/git-pack-redundant.txt
new file mode 100644
index 0000000000..55c0d48bf1
--- /dev/null
+++ b/Documentation/git-pack-redundant.txt
@@ -0,0 +1,47 @@
+git-pack-redundant(1)
+=====================
+
+NAME
+----
+git-pack-redundant - Program used to find redundant pack files.
+
+
+SYNOPSIS
+--------
+'git-pack-redundant [ -v ] < -a | .pack filename ... >'
+
+DESCRIPTION
+-----------
+This program computes which packs in your repository
+are redundant. The output is suitable for piping to
+'xargs rm' if you are in the root of the repository.
+
+OPTIONS
+-------
+
+-v::
+	Verbose. Outputs some statistics to stderr.
+	Has a small performance penalty.
+
+-a::
+	All. Processes all the local packs. Any filenames on
+	the commandline are ignored.
+
+Author
+------
+Written by Lukas Sandström <lukass@etek.chalmers.se>
+
+Documentation
+--------------
+Documentation by Lukas Sandström <lukass@etek.chalmers.se>
+
+See-Also
+--------
+gitlink:git-pack-objects[1]
+gitlink:git-repack[1]
+gitlink:git-prune-packed[1]
+
+GIT
+---
+Part of the gitlink:git[7] suite
+
diff --git a/Makefile b/Makefile
index 4c646c9e84..b4dca5f228 100644
--- a/Makefile
+++ b/Makefile
@@ -122,7 +122,7 @@ PROGRAMS = \
 	git-unpack-objects$X git-update-index$X git-update-server-info$X \
 	git-upload-pack$X git-verify-pack$X git-write-tree$X \
 	git-update-ref$X git-symbolic-ref$X git-check-ref-format$X \
-	git-name-rev$X git-pack-intersect$X $(SIMPLE_PROGRAMS)
+	git-name-rev$X git-pack-redundant$X $(SIMPLE_PROGRAMS)
 
 # Backward compatibility -- to be removed after 1.0
 PROGRAMS += git-ssh-pull$X git-ssh-push$X
diff --git a/git-repack.sh b/git-repack.sh
index 3f28300566..4ce00225da 100755
--- a/git-repack.sh
+++ b/git-repack.sh
@@ -45,7 +45,7 @@ if [ -z "$name" ]; then
 	if test "$remove_redandant" = t ; then
 		echo "Removing redundant packs."
 		sync
-		redundant=$(git-pack-intersect -a)
+		redundant=$(git-pack-redundant -a)
 		if test "$redundant" != "" ; then
 			echo $redundant | xargs rm
 		fi
@@ -63,7 +63,7 @@ exit
 if test "$remove_redandant" = t
 then
 	sync
-	redundant=$(git-pack-intersect -a)
+	redundant=$(git-pack-redundant -a)
 	if test "$redundant" != "" ; then
 		echo $redundant | xargs rm
 	fi
diff --git a/pack-intersect.c b/pack-intersect.c
deleted file mode 100644
index 2267478c36..0000000000
--- a/pack-intersect.c
+++ /dev/null
@@ -1,577 +0,0 @@
-/*
-*
-* Copyright 2005, Lukas Sandstrom <lukass@etek.chalmers.se>
-*
-* This file is licensed under the GPL v2.
-*
-*/
-
-#include "cache.h"
-
-static const char pack_intersect_usage[] =
-"git-pack-intersect [ -v ]  < -a | <.pack filename> ...>";
-
-int all = 0, verbose = 0;
-
-struct llist_item {
-	struct llist_item *next;
-	char *sha1;
-};
-struct llist {
-	struct llist_item *front;
-	struct llist_item *back;
-	size_t size;
-} *all_objects;
-
-struct pack_list {
-	struct pack_list *next;
-	struct packed_git *pack;
-	struct llist *unique_objects;
-	struct llist *all_objects;
-} *pack_list;
-
-struct pll {
-	struct pll *next;
-	struct pack_list *pl;
-};
-
-inline void llist_free(struct llist *list)
-{
-	while((list->back = list->front)) {
-		list->front = list->front->next;
-		free(list->back);
-	}
-	free(list);
-}
-
-inline void llist_init(struct llist **list)
-{
-	*list = xmalloc(sizeof(struct llist));
-	(*list)->front = (*list)->back = NULL;
-	(*list)->size = 0;
-}
-
-struct llist * llist_copy(struct llist *list)
-{
-	struct llist *ret;
-	struct llist_item *new, *old, *prev;
-	
-	llist_init(&ret);
-
-	if ((ret->size = list->size) == 0)
-		return ret;
-
-	new = ret->front = xmalloc(sizeof(struct llist_item));
-	new->sha1 = list->front->sha1;
-
-	old = list->front->next;
-	while (old) {
-		prev = new;
-		new = xmalloc(sizeof(struct llist_item));
-		prev->next = new;
-		new->sha1 = old->sha1;
-		old = old->next;
-	}
-	new->next = NULL;
-	ret->back = new;
-	
-	return ret;
-}
-
-inline struct llist_item * llist_insert(struct llist *list,
-					struct llist_item *after, char *sha1)
-{
-	struct llist_item *new = xmalloc(sizeof(struct llist_item));
-	new->sha1 = sha1;
-	new->next = NULL;
-
-	if (after != NULL) {
-		new->next = after->next;
-		after->next = new;
-		if (after == list->back)
-			list->back = new;
-	} else {/* insert in front */
-		if (list->size == 0)
-			list->back = new;
-		else
-			new->next = list->front;
-		list->front = new;
-	}
-	list->size++;
-	return new;
-}
-
-inline struct llist_item * llist_insert_back(struct llist *list, char *sha1)
-{
-	return llist_insert(list, list->back, sha1);
-}
-
-inline struct llist_item * llist_insert_sorted_unique(struct llist *list,
-					char *sha1, struct llist_item *hint)
-{
-	struct llist_item *prev = NULL, *l;
-
-	l = (hint == NULL) ? list->front : hint;
-	while (l) {
-		int cmp = memcmp(l->sha1, sha1, 20);
-		if (cmp > 0) { /* we insert before this entry */
-			return llist_insert(list, prev, sha1);
-		}
-		if(!cmp) { /* already exists */
-			return l;
-		}
-		prev = l;
-		l = l->next;
-	}
-	/* insert at the end */
-	return llist_insert_back(list, sha1);
-}
-
-/* computes A\B */
-struct llist * llist_sorted_difference(struct llist_item *A,
-				       struct llist_item *B)
-{
-	struct llist *ret;
-	llist_init(&ret);
-
-	while (A != NULL && B != NULL) {
-		int cmp = memcmp(A->sha1, B->sha1, 20);
-		if (!cmp) {
-			A = A->next;
-			B = B->next;
-			continue;
-		}
-		if(cmp > 0) { /* we'll never find this B */
-			B = B->next;
-			continue;
-		}
-		/* A has the object, B doesn't */
-		llist_insert_back(ret, A->sha1);
-		A = A->next;
-	}
-	while (A != NULL) {
-		llist_insert_back(ret, A->sha1);
-		A = A->next;
-	}
-	return ret;
-}
-
-/* returns a pointer to an item in front of sha1 */
-inline struct llist_item * llist_sorted_remove(struct llist *list, char *sha1,
-					       struct llist_item *hint)
-{
-	struct llist_item *prev, *l;
-
-redo_from_start:
-	l = (hint == NULL) ? list->front : hint;
-	prev = NULL;
-	while (l) {
-		int cmp = memcmp(l->sha1, sha1, 20);
-		if (cmp > 0) /* not in list, since sorted */
-			return prev;
-		if(!cmp) { /* found */
-			if (prev == NULL) {
-				if (hint != NULL && hint != list->front) {
-					/* we don't know the previous element */
-					hint = NULL;
-					goto redo_from_start;
-				}
-				list->front = l->next;
-			} else
-				prev->next = l->next;
-			if (l == list->back)
-				list->back = prev;
-			free(l);
-			list->size--;
-			return prev;
-		}
-		prev = l;
-		l = l->next;
-	}
-	return prev;
-}
-
-inline struct pack_list * pack_list_insert(struct pack_list **pl,
-					   struct pack_list *entry)
-{
-	struct pack_list *p = xmalloc(sizeof(struct pack_list));
-	memcpy(p, entry, sizeof(struct pack_list));
-	p->next = *pl;
-	*pl = p;
-	return p;
-}
-
-struct pack_list * pack_list_difference(struct pack_list *A,
-					struct pack_list *B)
-{
-	struct pack_list *ret, *pl;
-
-	if (A == NULL)
-		return NULL;
-
-	pl = B;
-	while (pl != NULL) {
-		if (A->pack == pl->pack)
-			return pack_list_difference(A->next, B);
-		pl = pl->next;
-	}
-	ret = xmalloc(sizeof(struct pack_list));
-	memcpy(ret, A, sizeof(struct pack_list));
-	ret->next = pack_list_difference(A->next, B);
-	return ret;
-}
-
-void cmp_two_packs(struct pack_list *p1, struct pack_list *p2)
-{
-	int p1_off, p2_off;
-	void *p1_base, *p2_base;
-	struct llist_item *p1_hint = NULL, *p2_hint = NULL;
-	
-	p1_off = p2_off = 256 * 4 + 4;
-	p1_base = (void *)p1->pack->index_base;
-	p2_base = (void *)p2->pack->index_base;
-
-	while (p1_off <= p1->pack->index_size - 3 * 20 &&
-	       p2_off <= p2->pack->index_size - 3 * 20)
-	{
-		int cmp = memcmp(p1_base + p1_off, p2_base + p2_off, 20);
-		/* cmp ~ p1 - p2 */
-		if (cmp == 0) {
-			p1_hint = llist_sorted_remove(p1->unique_objects,
-					p1_base + p1_off, p1_hint);
-			p2_hint = llist_sorted_remove(p2->unique_objects,
-					p1_base + p1_off, p2_hint);
-			p1_off+=24;
-			p2_off+=24;
-			continue;
-		}
-		if (cmp < 0) { /* p1 has the object, p2 doesn't */
-			p1_off+=24;
-		} else { /* p2 has the object, p1 doesn't */
-			p2_off+=24;
-		}
-	}
-}
-
-/* all the permutations have to be free()d at the same time,
- * since they refer to each other
- */
-struct pll * get_all_permutations(struct pack_list *list)
-{
-	struct pll *subset, *pll, *new_pll = NULL; /*silence warning*/
-
-	if (list == NULL)
-		return NULL;
-
-	if (list->next == NULL) {
-		new_pll = xmalloc(sizeof(struct pll));
-		new_pll->next = NULL;
-		new_pll->pl = list;
-		return new_pll;
-	}
-
-	pll = subset = get_all_permutations(list->next);
-	while (pll) {
-		new_pll = xmalloc(sizeof(struct pll));
-		new_pll->next = pll->next;
-		pll->next = new_pll;
-
-		new_pll->pl = xmalloc(sizeof(struct pack_list));
-		memcpy(new_pll->pl, list, sizeof(struct pack_list));
-		new_pll->pl->next = pll->pl;
-
-		pll = new_pll->next;
-	}
-	/* add ourself to the end */
-	new_pll->next = xmalloc(sizeof(struct pll));
-	new_pll->next->pl = xmalloc(sizeof(struct pack_list));
-	new_pll->next->next = NULL;
-	memcpy(new_pll->next->pl, list, sizeof(struct pack_list));
-	new_pll->next->pl->next = NULL;
-
-	return subset;
-}
-
-int is_superset(struct pack_list *pl, struct llist *list)
-{
-	struct llist *diff, *old;
-
-	diff = llist_copy(list);
-
-	while (pl) {
-		old = diff;
-		diff = llist_sorted_difference(diff->front,
-					       pl->all_objects->front);
-		llist_free(old);
-		if (diff->size == 0) { /* we're done */
-			llist_free(diff);
-			return 1;
-		}
-		pl = pl->next;
-	}
-	llist_free(diff);
-	return 0;
-}
-
-size_t sizeof_union(struct packed_git *p1, struct packed_git *p2)
-{
-	size_t ret = 0;
-	int p1_off, p2_off;
-	void *p1_base, *p2_base;
-
-	p1_off = p2_off = 256 * 4 + 4;
-	p1_base = (void *)p1->index_base;
-	p2_base = (void *)p2->index_base;
-
-	while (p1_off <= p1->index_size - 3 * 20 &&
-	       p2_off <= p2->index_size - 3 * 20)
-	{
-		int cmp = memcmp(p1_base + p1_off, p2_base + p2_off, 20);
-		/* cmp ~ p1 - p2 */
-		if (cmp == 0) {
-			ret++;
-			p1_off+=24;
-			p2_off+=24;
-			continue;
-		}
-		if (cmp < 0) { /* p1 has the object, p2 doesn't */
-			p1_off+=24;
-		} else { /* p2 has the object, p1 doesn't */
-			p2_off+=24;
-		}
-	}
-	return ret;
-}
-
-/* another O(n^2) function ... */
-size_t get_pack_redundancy(struct pack_list *pl)
-{
-	struct pack_list *subset;
-	size_t ret = 0;
-	while ((subset = pl->next)) {
-		while(subset) {
-			ret += sizeof_union(pl->pack, subset->pack);
-			subset = subset->next;
-		}
-		pl = pl->next;
-	}
-	return ret;
-}
-
-inline size_t pack_set_bytecount(struct pack_list *pl)
-{
-	size_t ret = 0;
-	while (pl) {
-		ret += pl->pack->pack_size;
-		ret += pl->pack->index_size;
-		pl = pl->next;
-	}
-	return ret;
-}
-
-void minimize(struct pack_list **min)
-{
-	struct pack_list *pl, *unique = NULL,
-		*non_unique = NULL, *min_perm = NULL;
-	struct pll *perm, *perm_all, *perm_ok = NULL, *new_perm;
-	struct llist *missing, *old;
-	size_t min_perm_size = (size_t)-1, perm_size;
-
-	pl = pack_list;
-	while (pl) {
-		if(pl->unique_objects->size)
-			pack_list_insert(&unique, pl);
-		else
-			pack_list_insert(&non_unique, pl);
-		pl = pl->next;
-	}
-	/* find out which objects are missing from the set of unique packs */
-	missing = llist_copy(all_objects);
-	pl = unique;
-	while (pl) {
-		old = missing;
-		missing = llist_sorted_difference(missing->front,
-						  pl->all_objects->front);
-		llist_free(old);
-		pl = pl->next;
-	}
-
-	if (missing->size == 0) {
-		*min = unique;
-		return;
-	}
-
-	/* find the permutations which contain all missing objects */
-	perm_all = perm = get_all_permutations(non_unique);
-	while (perm) {
-		if (is_superset(perm->pl, missing)) {
-			new_perm = xmalloc(sizeof(struct pll));
-			new_perm->pl = perm->pl;
-			new_perm->next = perm_ok;
-			perm_ok = new_perm;
-		}
-		perm = perm->next;
-	}
-	
-	if (perm_ok == NULL)
-		die("Internal error: No complete sets found!\n");
-
-	/* find the permutation with the smallest size */
-	perm = perm_ok;
-	while (perm) {
-		perm_size = pack_set_bytecount(perm->pl);
-		if (min_perm_size > perm_size) {
-			min_perm_size = perm_size;
-			min_perm = perm->pl;
-		}
-		perm = perm->next;
-	}
-	*min = min_perm;
-	/* add the unique packs to the list */
-	pl = unique;
-	while(pl) {
-		pack_list_insert(min, pl);
-		pl = pl->next;
-	}
-}
-
-void load_all_objects()
-{
-	struct pack_list *pl = pack_list;
-	struct llist_item *hint, *l;
-	int i;
-
-	llist_init(&all_objects);
-
-	while (pl) {
-		i = 0;
-		hint = NULL;
-		l = pl->all_objects->front;
-		while (l) {
-			hint = llist_insert_sorted_unique(all_objects,
-							  l->sha1, hint);
-			l = l->next;
-		}
-		pl = pl->next;
-	}
-}
-
-/* this scales like O(n^2) */
-void cmp_packs()
-{
-	struct pack_list *subset, *curr = pack_list;
-
-	while ((subset = curr)) {
-		while((subset = subset->next))
-			cmp_two_packs(curr, subset);
-		curr = curr->next;
-	}
-}
-
-struct pack_list * add_pack(struct packed_git *p)
-{
-	struct pack_list l;
-	size_t off;
-	void *base;
-
-	l.pack = p;
-	llist_init(&l.all_objects);
-
-	off = 256 * 4 + 4;
-	base = (void *)p->index_base;
-	while (off <= p->index_size - 3 * 20) {
-		llist_insert_back(l.all_objects, base + off);
-		off+=24;
-	}
-	/* this list will be pruned in cmp_two_packs later */
-	l.unique_objects = llist_copy(l.all_objects);
-	return pack_list_insert(&pack_list, &l);
-}
-
-struct pack_list * add_pack_file(char *filename)
-{
-	struct packed_git *p = packed_git;
-
-	if (strlen(filename) < 40)
-		die("Bad pack filename: %s\n", filename);
-
-	while (p) {
-		if (strstr(p->pack_name, filename))
-			/* this will silently ignore packs in alt-odb */
-			return add_pack(p);
-		p = p->next;
-	}
-	die("Filename %s not found in packed_git\n", filename);
-}
-
-void load_all()
-{
-	struct packed_git *p = packed_git;
-
-	while (p) {
-		if (p->pack_local) /* ignore alt-odb for now */
-			add_pack(p);
-		p = p->next;
-	}
-}
-
-int main(int argc, char **argv)
-{
-	int i;
-	struct pack_list *min, *red, *pl;
-
-	for (i = 1; i < argc; i++) {
-		const char *arg = argv[i];
-		if(!strcmp(arg, "--"))
-			break;
-		if(!strcmp(arg, "-a")) {
-			all = 1;
-			continue;
-		}
-		if(!strcmp(arg, "-v")) {
-			verbose = 1;
-			continue;
-		}
-		if(*arg == '-')
-			usage(pack_intersect_usage);
-		else
-			break;
-	}
-
-	prepare_packed_git();
-
-	if(all)
-		load_all();
-	else
-		while (*(argv + i) != NULL)
-			add_pack_file(*(argv + i++));
-
-	if (pack_list == NULL)
-		die("Zero packs found!\n");
-
-	cmp_packs();
-
-	load_all_objects();
-
-	minimize(&min);
-	if (verbose) {
-		fprintf(stderr, "The smallest (bytewise) set of packs is:\n");
-		pl = min;
-		while (pl) {
-			fprintf(stderr, "\t%s\n", pl->pack->pack_name);
-			pl = pl->next;
-		}
-		fprintf(stderr, "containing %ld duplicate objects "
-				"with a total size of %ldkb.\n",
-			get_pack_redundancy(min), pack_set_bytecount(min)/1024);
-		fprintf(stderr, "Redundant packs (with indexes):\n");
-	}
-	pl = red = pack_list_difference(pack_list, min);
-	while (pl) {
-		printf("%s\n%s\n",
-		       sha1_pack_index_name(pl->pack->sha1), pl->pack->pack_name);
-		pl = pl->next;
-	}
-
-	return 0;
-}
diff --git a/pack-redundant.c b/pack-redundant.c
new file mode 100644
index 0000000000..db3dcde22a
--- /dev/null
+++ b/pack-redundant.c
@@ -0,0 +1,579 @@
+/*
+*
+* Copyright 2005, Lukas Sandstrom <lukass@etek.chalmers.se>
+*
+* This file is licensed under the GPL v2.
+*
+*/
+
+#include "cache.h"
+
+static const char pack_redundant_usage[] =
+"git-pack-redundant [ -v ]  < -a | <.pack filename> ...>";
+
+int all = 0, verbose = 0;
+
+struct llist_item {
+	struct llist_item *next;
+	char *sha1;
+};
+struct llist {
+	struct llist_item *front;
+	struct llist_item *back;
+	size_t size;
+} *all_objects;
+
+struct pack_list {
+	struct pack_list *next;
+	struct packed_git *pack;
+	struct llist *unique_objects;
+	struct llist *all_objects;
+} *pack_list;
+
+struct pll {
+	struct pll *next;
+	struct pack_list *pl;
+};
+
+inline void llist_free(struct llist *list)
+{
+	while((list->back = list->front)) {
+		list->front = list->front->next;
+		free(list->back);
+	}
+	free(list);
+}
+
+inline void llist_init(struct llist **list)
+{
+	*list = xmalloc(sizeof(struct llist));
+	(*list)->front = (*list)->back = NULL;
+	(*list)->size = 0;
+}
+
+struct llist * llist_copy(struct llist *list)
+{
+	struct llist *ret;
+	struct llist_item *new, *old, *prev;
+	
+	llist_init(&ret);
+
+	if ((ret->size = list->size) == 0)
+		return ret;
+
+	new = ret->front = xmalloc(sizeof(struct llist_item));
+	new->sha1 = list->front->sha1;
+
+	old = list->front->next;
+	while (old) {
+		prev = new;
+		new = xmalloc(sizeof(struct llist_item));
+		prev->next = new;
+		new->sha1 = old->sha1;
+		old = old->next;
+	}
+	new->next = NULL;
+	ret->back = new;
+	
+	return ret;
+}
+
+inline struct llist_item * llist_insert(struct llist *list,
+					struct llist_item *after, char *sha1)
+{
+	struct llist_item *new = xmalloc(sizeof(struct llist_item));
+	new->sha1 = sha1;
+	new->next = NULL;
+
+	if (after != NULL) {
+		new->next = after->next;
+		after->next = new;
+		if (after == list->back)
+			list->back = new;
+	} else {/* insert in front */
+		if (list->size == 0)
+			list->back = new;
+		else
+			new->next = list->front;
+		list->front = new;
+	}
+	list->size++;
+	return new;
+}
+
+inline struct llist_item * llist_insert_back(struct llist *list, char *sha1)
+{
+	return llist_insert(list, list->back, sha1);
+}
+
+inline struct llist_item * llist_insert_sorted_unique(struct llist *list,
+					char *sha1, struct llist_item *hint)
+{
+	struct llist_item *prev = NULL, *l;
+
+	l = (hint == NULL) ? list->front : hint;
+	while (l) {
+		int cmp = memcmp(l->sha1, sha1, 20);
+		if (cmp > 0) { /* we insert before this entry */
+			return llist_insert(list, prev, sha1);
+		}
+		if(!cmp) { /* already exists */
+			return l;
+		}
+		prev = l;
+		l = l->next;
+	}
+	/* insert at the end */
+	return llist_insert_back(list, sha1);
+}
+
+/* computes A\B */
+struct llist * llist_sorted_difference(struct llist_item *A,
+				       struct llist_item *B)
+{
+	struct llist *ret;
+	llist_init(&ret);
+
+	while (A != NULL && B != NULL) {
+		int cmp = memcmp(A->sha1, B->sha1, 20);
+		if (!cmp) {
+			A = A->next;
+			B = B->next;
+			continue;
+		}
+		if(cmp > 0) { /* we'll never find this B */
+			B = B->next;
+			continue;
+		}
+		/* A has the object, B doesn't */
+		llist_insert_back(ret, A->sha1);
+		A = A->next;
+	}
+	while (A != NULL) {
+		llist_insert_back(ret, A->sha1);
+		A = A->next;
+	}
+	return ret;
+}
+
+/* returns a pointer to an item in front of sha1 */
+inline struct llist_item * llist_sorted_remove(struct llist *list, char *sha1,
+					       struct llist_item *hint)
+{
+	struct llist_item *prev, *l;
+
+redo_from_start:
+	l = (hint == NULL) ? list->front : hint;
+	prev = NULL;
+	while (l) {
+		int cmp = memcmp(l->sha1, sha1, 20);
+		if (cmp > 0) /* not in list, since sorted */
+			return prev;
+		if(!cmp) { /* found */
+			if (prev == NULL) {
+				if (hint != NULL && hint != list->front) {
+					/* we don't know the previous element */
+					hint = NULL;
+					goto redo_from_start;
+				}
+				list->front = l->next;
+			} else
+				prev->next = l->next;
+			if (l == list->back)
+				list->back = prev;
+			free(l);
+			list->size--;
+			return prev;
+		}
+		prev = l;
+		l = l->next;
+	}
+	return prev;
+}
+
+inline struct pack_list * pack_list_insert(struct pack_list **pl,
+					   struct pack_list *entry)
+{
+	struct pack_list *p = xmalloc(sizeof(struct pack_list));
+	memcpy(p, entry, sizeof(struct pack_list));
+	p->next = *pl;
+	*pl = p;
+	return p;
+}
+
+struct pack_list * pack_list_difference(struct pack_list *A,
+					struct pack_list *B)
+{
+	struct pack_list *ret, *pl;
+
+	if (A == NULL)
+		return NULL;
+
+	pl = B;
+	while (pl != NULL) {
+		if (A->pack == pl->pack)
+			return pack_list_difference(A->next, B);
+		pl = pl->next;
+	}
+	ret = xmalloc(sizeof(struct pack_list));
+	memcpy(ret, A, sizeof(struct pack_list));
+	ret->next = pack_list_difference(A->next, B);
+	return ret;
+}
+
+void cmp_two_packs(struct pack_list *p1, struct pack_list *p2)
+{
+	int p1_off, p2_off;
+	void *p1_base, *p2_base;
+	struct llist_item *p1_hint = NULL, *p2_hint = NULL;
+	
+	p1_off = p2_off = 256 * 4 + 4;
+	p1_base = (void *)p1->pack->index_base;
+	p2_base = (void *)p2->pack->index_base;
+
+	while (p1_off <= p1->pack->index_size - 3 * 20 &&
+	       p2_off <= p2->pack->index_size - 3 * 20)
+	{
+		int cmp = memcmp(p1_base + p1_off, p2_base + p2_off, 20);
+		/* cmp ~ p1 - p2 */
+		if (cmp == 0) {
+			p1_hint = llist_sorted_remove(p1->unique_objects,
+					p1_base + p1_off, p1_hint);
+			p2_hint = llist_sorted_remove(p2->unique_objects,
+					p1_base + p1_off, p2_hint);
+			p1_off+=24;
+			p2_off+=24;
+			continue;
+		}
+		if (cmp < 0) { /* p1 has the object, p2 doesn't */
+			p1_off+=24;
+		} else { /* p2 has the object, p1 doesn't */
+			p2_off+=24;
+		}
+	}
+}
+
+/* all the permutations have to be free()d at the same time,
+ * since they refer to each other
+ */
+struct pll * get_all_permutations(struct pack_list *list)
+{
+	struct pll *subset, *pll, *new_pll = NULL; /*silence warning*/
+
+	if (list == NULL)
+		return NULL;
+
+	if (list->next == NULL) {
+		new_pll = xmalloc(sizeof(struct pll));
+		new_pll->next = NULL;
+		new_pll->pl = list;
+		return new_pll;
+	}
+
+	pll = subset = get_all_permutations(list->next);
+	while (pll) {
+		new_pll = xmalloc(sizeof(struct pll));
+		new_pll->next = pll->next;
+		pll->next = new_pll;
+
+		new_pll->pl = xmalloc(sizeof(struct pack_list));
+		memcpy(new_pll->pl, list, sizeof(struct pack_list));
+		new_pll->pl->next = pll->pl;
+
+		pll = new_pll->next;
+	}
+	/* add ourself to the end */
+	new_pll->next = xmalloc(sizeof(struct pll));
+	new_pll->next->pl = xmalloc(sizeof(struct pack_list));
+	new_pll->next->next = NULL;
+	memcpy(new_pll->next->pl, list, sizeof(struct pack_list));
+	new_pll->next->pl->next = NULL;
+
+	return subset;
+}
+
+int is_superset(struct pack_list *pl, struct llist *list)
+{
+	struct llist *diff, *old;
+
+	diff = llist_copy(list);
+
+	while (pl) {
+		old = diff;
+		diff = llist_sorted_difference(diff->front,
+					       pl->all_objects->front);
+		llist_free(old);
+		if (diff->size == 0) { /* we're done */
+			llist_free(diff);
+			return 1;
+		}
+		pl = pl->next;
+	}
+	llist_free(diff);
+	return 0;
+}
+
+size_t sizeof_union(struct packed_git *p1, struct packed_git *p2)
+{
+	size_t ret = 0;
+	int p1_off, p2_off;
+	void *p1_base, *p2_base;
+
+	p1_off = p2_off = 256 * 4 + 4;
+	p1_base = (void *)p1->index_base;
+	p2_base = (void *)p2->index_base;
+
+	while (p1_off <= p1->index_size - 3 * 20 &&
+	       p2_off <= p2->index_size - 3 * 20)
+	{
+		int cmp = memcmp(p1_base + p1_off, p2_base + p2_off, 20);
+		/* cmp ~ p1 - p2 */
+		if (cmp == 0) {
+			ret++;
+			p1_off+=24;
+			p2_off+=24;
+			continue;
+		}
+		if (cmp < 0) { /* p1 has the object, p2 doesn't */
+			p1_off+=24;
+		} else { /* p2 has the object, p1 doesn't */
+			p2_off+=24;
+		}
+	}
+	return ret;
+}
+
+/* another O(n^2) function ... */
+size_t get_pack_redundancy(struct pack_list *pl)
+{
+	struct pack_list *subset;
+	size_t ret = 0;
+	while ((subset = pl->next)) {
+		while(subset) {
+			ret += sizeof_union(pl->pack, subset->pack);
+			subset = subset->next;
+		}
+		pl = pl->next;
+	}
+	return ret;
+}
+
+inline size_t pack_set_bytecount(struct pack_list *pl)
+{
+	size_t ret = 0;
+	while (pl) {
+		ret += pl->pack->pack_size;
+		ret += pl->pack->index_size;
+		pl = pl->next;
+	}
+	return ret;
+}
+
+void minimize(struct pack_list **min)
+{
+	struct pack_list *pl, *unique = NULL,
+		*non_unique = NULL, *min_perm = NULL;
+	struct pll *perm, *perm_all, *perm_ok = NULL, *new_perm;
+	struct llist *missing, *old;
+	size_t min_perm_size = (size_t)-1, perm_size;
+
+	pl = pack_list;
+	while (pl) {
+		if(pl->unique_objects->size)
+			pack_list_insert(&unique, pl);
+		else
+			pack_list_insert(&non_unique, pl);
+		pl = pl->next;
+	}
+	/* find out which objects are missing from the set of unique packs */
+	missing = llist_copy(all_objects);
+	pl = unique;
+	while (pl) {
+		old = missing;
+		missing = llist_sorted_difference(missing->front,
+						  pl->all_objects->front);
+		llist_free(old);
+		pl = pl->next;
+	}
+
+	if (missing->size == 0) {
+		*min = unique;
+		return;
+	}
+
+	/* find the permutations which contain all missing objects */
+	perm_all = perm = get_all_permutations(non_unique);
+	while (perm) {
+		if (is_superset(perm->pl, missing)) {
+			new_perm = xmalloc(sizeof(struct pll));
+			new_perm->pl = perm->pl;
+			new_perm->next = perm_ok;
+			perm_ok = new_perm;
+		}
+		perm = perm->next;
+	}
+	
+	if (perm_ok == NULL)
+		die("Internal error: No complete sets found!\n");
+
+	/* find the permutation with the smallest size */
+	perm = perm_ok;
+	while (perm) {
+		perm_size = pack_set_bytecount(perm->pl);
+		if (min_perm_size > perm_size) {
+			min_perm_size = perm_size;
+			min_perm = perm->pl;
+		}
+		perm = perm->next;
+	}
+	*min = min_perm;
+	/* add the unique packs to the list */
+	pl = unique;
+	while(pl) {
+		pack_list_insert(min, pl);
+		pl = pl->next;
+	}
+}
+
+void load_all_objects()
+{
+	struct pack_list *pl = pack_list;
+	struct llist_item *hint, *l;
+	int i;
+
+	llist_init(&all_objects);
+
+	while (pl) {
+		i = 0;
+		hint = NULL;
+		l = pl->all_objects->front;
+		while (l) {
+			hint = llist_insert_sorted_unique(all_objects,
+							  l->sha1, hint);
+			l = l->next;
+		}
+		pl = pl->next;
+	}
+}
+
+/* this scales like O(n^2) */
+void cmp_packs()
+{
+	struct pack_list *subset, *curr = pack_list;
+
+	while ((subset = curr)) {
+		while((subset = subset->next))
+			cmp_two_packs(curr, subset);
+		curr = curr->next;
+	}
+}
+
+struct pack_list * add_pack(struct packed_git *p)
+{
+	struct pack_list l;
+	size_t off;
+	void *base;
+
+	l.pack = p;
+	llist_init(&l.all_objects);
+
+	off = 256 * 4 + 4;
+	base = (void *)p->index_base;
+	while (off <= p->index_size - 3 * 20) {
+		llist_insert_back(l.all_objects, base + off);
+		off+=24;
+	}
+	/* this list will be pruned in cmp_two_packs later */
+	l.unique_objects = llist_copy(l.all_objects);
+	return pack_list_insert(&pack_list, &l);
+}
+
+struct pack_list * add_pack_file(char *filename)
+{
+	struct packed_git *p = packed_git;
+
+	if (strlen(filename) < 40)
+		die("Bad pack filename: %s\n", filename);
+
+	while (p) {
+		if (strstr(p->pack_name, filename))
+			/* this will silently ignore packs in alt-odb */
+			return add_pack(p);
+		p = p->next;
+	}
+	die("Filename %s not found in packed_git\n", filename);
+}
+
+void load_all()
+{
+	struct packed_git *p = packed_git;
+
+	while (p) {
+		if (p->pack_local) /* ignore alt-odb for now */
+			add_pack(p);
+		p = p->next;
+	}
+}
+
+int main(int argc, char **argv)
+{
+	int i;
+	struct pack_list *min, *red, *pl;
+
+	for (i = 1; i < argc; i++) {
+		const char *arg = argv[i];
+		if(!strcmp(arg, "--")) {
+			i++;
+			break;
+		}
+		if(!strcmp(arg, "-a")) {
+			all = 1;
+			continue;
+		}
+		if(!strcmp(arg, "-v")) {
+			verbose = 1;
+			continue;
+		}
+		if(*arg == '-')
+			usage(pack_redundant_usage);
+		else
+			break;
+	}
+
+	prepare_packed_git();
+
+	if(all)
+		load_all();
+	else
+		while (*(argv + i) != NULL)
+			add_pack_file(*(argv + i++));
+
+	if (pack_list == NULL)
+		die("Zero packs found!\n");
+
+	cmp_packs();
+
+	load_all_objects();
+
+	minimize(&min);
+	if (verbose) {
+		fprintf(stderr, "The smallest (bytewise) set of packs is:\n");
+		pl = min;
+		while (pl) {
+			fprintf(stderr, "\t%s\n", pl->pack->pack_name);
+			pl = pl->next;
+		}
+		fprintf(stderr, "containing %ld duplicate objects "
+				"with a total size of %ldkb.\n",
+			get_pack_redundancy(min), pack_set_bytecount(min)/1024);
+		fprintf(stderr, "Redundant packs (with indexes):\n");
+	}
+	pl = red = pack_list_difference(pack_list, min);
+	while (pl) {
+		printf("%s\n%s\n",
+		       sha1_pack_index_name(pl->pack->sha1), pl->pack->pack_name);
+		pl = pl->next;
+	}
+
+	return 0;
+}
-- 
cgit v1.2.3


From 1c3039e8f1eb01766cff976793c8f439095967f6 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Lukas=5FSandstr=C3=B6m?= <lukass@etek.chalmers.se>
Date: Fri, 11 Nov 2005 01:25:04 +0100
Subject: Make git-pack-redundant consider alt-odbs
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

This patch changes git-pack-redundant so that packfiles
in alternate object directories also are considered when
deciding which objects are redundant.

This functionality is controlled by the flag '--alt-odb'.

Also convert the other flags to the long form, and update
docs and git-repack accordingly.

Signed-off-by: Lukas Sandström <lukass@etek.chalmers.se>
Signed-off-by: Junio C Hamano <junkio@cox.net>
---
 Documentation/git-pack-redundant.txt |  17 ++--
 git-repack.sh                        |   4 +-
 pack-redundant.c                     | 147 ++++++++++++++++++++++-------------
 3 files changed, 106 insertions(+), 62 deletions(-)

diff --git a/Documentation/git-pack-redundant.txt b/Documentation/git-pack-redundant.txt
index 55c0d48bf1..5ba9272837 100644
--- a/Documentation/git-pack-redundant.txt
+++ b/Documentation/git-pack-redundant.txt
@@ -8,7 +8,7 @@ git-pack-redundant - Program used to find redundant pack files.
 
 SYNOPSIS
 --------
-'git-pack-redundant [ -v ] < -a | .pack filename ... >'
+'git-pack-redundant [ --verbose ] [ --alt-odb ] < --all | .pack filename ... >'
 
 DESCRIPTION
 -----------
@@ -19,13 +19,16 @@ are redundant. The output is suitable for piping to
 OPTIONS
 -------
 
--v::
-	Verbose. Outputs some statistics to stderr.
-	Has a small performance penalty.
 
--a::
-	All. Processes all the local packs. Any filenames on
-	the commandline are ignored.
+--all::
+	Processes all packs. Any filenames on the commandline are ignored.
+
+--alt-odb::
+	Don't require objects present in packs from alternate object
+	directories to be present in local packs.
+
+--verbose::
+	Outputs some statistics to stderr. Has a small performance penalty.
 
 Author
 ------
diff --git a/git-repack.sh b/git-repack.sh
index 4ce00225da..f34720701b 100755
--- a/git-repack.sh
+++ b/git-repack.sh
@@ -45,7 +45,7 @@ if [ -z "$name" ]; then
 	if test "$remove_redandant" = t ; then
 		echo "Removing redundant packs."
 		sync
-		redundant=$(git-pack-redundant -a)
+		redundant=$(git-pack-redundant --all)
 		if test "$redundant" != "" ; then
 			echo $redundant | xargs rm
 		fi
@@ -63,7 +63,7 @@ exit
 if test "$remove_redandant" = t
 then
 	sync
-	redundant=$(git-pack-redundant -a)
+	redundant=$(git-pack-redundant --all)
 	if test "$redundant" != "" ; then
 		echo $redundant | xargs rm
 	fi
diff --git a/pack-redundant.c b/pack-redundant.c
index db3dcde22a..1f8c577391 100644
--- a/pack-redundant.c
+++ b/pack-redundant.c
@@ -9,9 +9,9 @@
 #include "cache.h"
 
 static const char pack_redundant_usage[] =
-"git-pack-redundant [ -v ]  < -a | <.pack filename> ...>";
+"git-pack-redundant [ --verbose ] [ --alt-odb ] < --all | <.pack filename> ...>";
 
-int all = 0, verbose = 0;
+int load_all_packs = 0, verbose = 0, alt_odb = 0;
 
 struct llist_item {
 	struct llist_item *next;
@@ -21,14 +21,14 @@ struct llist {
 	struct llist_item *front;
 	struct llist_item *back;
 	size_t size;
-} *all_objects;
+} *all_objects; /* all objects which must be present in local packfiles */
 
 struct pack_list {
 	struct pack_list *next;
 	struct packed_git *pack;
 	struct llist *unique_objects;
 	struct llist *all_objects;
-} *pack_list;
+} *local_packs = NULL, *altodb_packs = NULL;
 
 struct pll {
 	struct pll *next;
@@ -128,32 +128,35 @@ inline struct llist_item * llist_insert_sorted_unique(struct llist *list,
 }
 
 /* computes A\B */
-struct llist * llist_sorted_difference(struct llist_item *A,
-				       struct llist_item *B)
+void llist_sorted_difference_inplace(struct llist *A,
+				     struct llist *B)
 {
-	struct llist *ret;
-	llist_init(&ret);
+	struct llist_item *prev, *a, *b, *x;
 
-	while (A != NULL && B != NULL) {
-		int cmp = memcmp(A->sha1, B->sha1, 20);
+	prev = a = A->front;
+	b = B->front;
+
+	while (a != NULL && b != NULL) {
+		int cmp = memcmp(a->sha1, b->sha1, 20);
 		if (!cmp) {
-			A = A->next;
-			B = B->next;
-			continue;
-		}
-		if(cmp > 0) { /* we'll never find this B */
-			B = B->next;
-			continue;
-		}
-		/* A has the object, B doesn't */
-		llist_insert_back(ret, A->sha1);
-		A = A->next;
-	}
-	while (A != NULL) {
-		llist_insert_back(ret, A->sha1);
-		A = A->next;
+			x = a;
+			if (a == A->front)
+				A->front = a->next;
+			a = prev->next = a->next;
+
+			if (a == NULL) /* end of list */
+				A->back = prev;
+			A->size--;
+			free(x);
+			b = b->next;
+		} else
+			if (cmp > 0)
+				b = b->next;
+			else {
+				prev = a;
+				a = a->next;
+			}
 	}
-	return ret;
 }
 
 /* returns a pointer to an item in front of sha1 */
@@ -201,6 +204,16 @@ inline struct pack_list * pack_list_insert(struct pack_list **pl,
 	return p;
 }
 
+inline size_t pack_list_size(struct pack_list *pl)
+{
+	size_t ret = 0;
+	while(pl) {
+		ret++;
+		pl = pl->next;
+	}
+	return ret;
+}
+
 struct pack_list * pack_list_difference(struct pack_list *A,
 					struct pack_list *B)
 {
@@ -294,15 +307,13 @@ struct pll * get_all_permutations(struct pack_list *list)
 
 int is_superset(struct pack_list *pl, struct llist *list)
 {
-	struct llist *diff, *old;
+	struct llist *diff;
 
 	diff = llist_copy(list);
 
 	while (pl) {
-		old = diff;
-		diff = llist_sorted_difference(diff->front,
-					       pl->all_objects->front);
-		llist_free(old);
+		llist_sorted_difference_inplace(diff,
+						pl->all_objects);
 		if (diff->size == 0) { /* we're done */
 			llist_free(diff);
 			return 1;
@@ -347,6 +358,10 @@ size_t sizeof_union(struct packed_git *p1, struct packed_git *p2)
 size_t get_pack_redundancy(struct pack_list *pl)
 {
 	struct pack_list *subset;
+
+	if (pl == NULL)
+		return 0;
+
 	size_t ret = 0;
 	while ((subset = pl->next)) {
 		while(subset) {
@@ -374,10 +389,10 @@ void minimize(struct pack_list **min)
 	struct pack_list *pl, *unique = NULL,
 		*non_unique = NULL, *min_perm = NULL;
 	struct pll *perm, *perm_all, *perm_ok = NULL, *new_perm;
-	struct llist *missing, *old;
+	struct llist *missing;
 	size_t min_perm_size = (size_t)-1, perm_size;
 
-	pl = pack_list;
+	pl = local_packs;
 	while (pl) {
 		if(pl->unique_objects->size)
 			pack_list_insert(&unique, pl);
@@ -389,13 +404,12 @@ void minimize(struct pack_list **min)
 	missing = llist_copy(all_objects);
 	pl = unique;
 	while (pl) {
-		old = missing;
-		missing = llist_sorted_difference(missing->front,
-						  pl->all_objects->front);
-		llist_free(old);
+		llist_sorted_difference_inplace(missing,
+						pl->all_objects);
 		pl = pl->next;
 	}
 
+	/* return if there are no objects missing from the unique set */
 	if (missing->size == 0) {
 		*min = unique;
 		return;
@@ -437,7 +451,7 @@ void minimize(struct pack_list **min)
 
 void load_all_objects()
 {
-	struct pack_list *pl = pack_list;
+	struct pack_list *pl = local_packs;
 	struct llist_item *hint, *l;
 	int i;
 
@@ -454,17 +468,34 @@ void load_all_objects()
 		}
 		pl = pl->next;
 	}
+	/* remove objects present in remote packs */
+	pl = altodb_packs;
+	while (pl) {
+		llist_sorted_difference_inplace(all_objects, pl->all_objects);
+		pl = pl->next;
+	}
 }
 
 /* this scales like O(n^2) */
 void cmp_packs()
 {
-	struct pack_list *subset, *curr = pack_list;
+	struct pack_list *subset, *pl = local_packs;
 
-	while ((subset = curr)) {
+	while ((subset = pl)) {
 		while((subset = subset->next))
-			cmp_two_packs(curr, subset);
-		curr = curr->next;
+			cmp_two_packs(pl, subset);
+		pl = pl->next;
+	}
+
+	pl = altodb_packs;
+	while (pl) {
+		subset = local_packs;
+		while (subset) {
+			llist_sorted_difference_inplace(subset->unique_objects,
+							pl->all_objects);
+			subset = subset->next;
+		}
+		pl = pl->next;
 	}
 }
 
@@ -485,7 +516,10 @@ struct pack_list * add_pack(struct packed_git *p)
 	}
 	/* this list will be pruned in cmp_two_packs later */
 	l.unique_objects = llist_copy(l.all_objects);
-	return pack_list_insert(&pack_list, &l);
+	if (p->pack_local)
+		return pack_list_insert(&local_packs, &l);
+	else
+		return alt_odb ? pack_list_insert(&altodb_packs, &l) : NULL;
 }
 
 struct pack_list * add_pack_file(char *filename)
@@ -497,7 +531,6 @@ struct pack_list * add_pack_file(char *filename)
 
 	while (p) {
 		if (strstr(p->pack_name, filename))
-			/* this will silently ignore packs in alt-odb */
 			return add_pack(p);
 		p = p->next;
 	}
@@ -509,8 +542,7 @@ void load_all()
 	struct packed_git *p = packed_git;
 
 	while (p) {
-		if (p->pack_local) /* ignore alt-odb for now */
-			add_pack(p);
+		add_pack(p);
 		p = p->next;
 	}
 }
@@ -526,14 +558,18 @@ int main(int argc, char **argv)
 			i++;
 			break;
 		}
-		if(!strcmp(arg, "-a")) {
-			all = 1;
+		if(!strcmp(arg, "--all")) {
+			load_all_packs = 1;
 			continue;
 		}
-		if(!strcmp(arg, "-v")) {
+		if(!strcmp(arg, "--verbose")) {
 			verbose = 1;
 			continue;
 		}
+		if(!strcmp(arg, "--alt-odb")) {
+			alt_odb = 1;
+			continue;
+		}
 		if(*arg == '-')
 			usage(pack_redundant_usage);
 		else
@@ -542,13 +578,13 @@ int main(int argc, char **argv)
 
 	prepare_packed_git();
 
-	if(all)
+	if (load_all_packs)
 		load_all();
 	else
 		while (*(argv + i) != NULL)
 			add_pack_file(*(argv + i++));
 
-	if (pack_list == NULL)
+	if (local_packs == NULL)
 		die("Zero packs found!\n");
 
 	cmp_packs();
@@ -557,6 +593,8 @@ int main(int argc, char **argv)
 
 	minimize(&min);
 	if (verbose) {
+		fprintf(stderr, "There are %ld packs available in alt-odbs.\n",
+			pack_list_size(altodb_packs));
 		fprintf(stderr, "The smallest (bytewise) set of packs is:\n");
 		pl = min;
 		while (pl) {
@@ -566,12 +604,15 @@ int main(int argc, char **argv)
 		fprintf(stderr, "containing %ld duplicate objects "
 				"with a total size of %ldkb.\n",
 			get_pack_redundancy(min), pack_set_bytecount(min)/1024);
+		fprintf(stderr, "A total of %ld unique objects were considered.\n",
+			all_objects->size);
 		fprintf(stderr, "Redundant packs (with indexes):\n");
 	}
-	pl = red = pack_list_difference(pack_list, min);
+	pl = red = pack_list_difference(local_packs, min);
 	while (pl) {
 		printf("%s\n%s\n",
-		       sha1_pack_index_name(pl->pack->sha1), pl->pack->pack_name);
+		       sha1_pack_index_name(pl->pack->sha1),
+		       pl->pack->pack_name);
 		pl = pl->next;
 	}
 
-- 
cgit v1.2.3


From d7b1a1ddbece22c99d52ea45bdecefdb9f17a613 Mon Sep 17 00:00:00 2001
From: Junio C Hamano <junkio@cox.net>
Date: Fri, 11 Nov 2005 10:41:53 -0800
Subject: git-prune: prune redundant packs

Signed-off-by: Junio C Hamano <junkio@cox.net>
---
 git-prune.sh | 11 +++++++++++
 1 file changed, 11 insertions(+)

diff --git a/git-prune.sh b/git-prune.sh
index ef31bd2a68..aa79807313 100755
--- a/git-prune.sh
+++ b/git-prune.sh
@@ -27,3 +27,14 @@ sed -ne '/unreachable /{
 }
 
 git-prune-packed $dryrun
+
+redundant=$(git-pack-redundant --all)
+if test "" != "$redundant"
+then
+	if test "" = $dryrun
+	then
+		echo "$redundant" | xargs rm -f
+	else
+		echo rm -f "$redundant"
+	fi
+fi
-- 
cgit v1.2.3


From 04e7ca1a1bd05e733236734bd7078b4cde1f7ce5 Mon Sep 17 00:00:00 2001
From: Junio C Hamano <junkio@cox.net>
Date: Mon, 7 Nov 2005 15:15:34 -0800
Subject: git-lost+found

This command helps you resurrect accidentally lost tags and commits.

Signed-off-by: Junio C Hamano <junkio@cox.net>
---
 Documentation/git-lost+found.txt | 78 ++++++++++++++++++++++++++++++++++++++++
 Documentation/git.txt            |  3 ++
 Makefile                         |  3 +-
 git-lost+found.sh                | 23 ++++++++++++
 4 files changed, 106 insertions(+), 1 deletion(-)
 create mode 100644 Documentation/git-lost+found.txt
 create mode 100755 git-lost+found.sh

diff --git a/Documentation/git-lost+found.txt b/Documentation/git-lost+found.txt
new file mode 100644
index 0000000000..0cb8e3bbfe
--- /dev/null
+++ b/Documentation/git-lost+found.txt
@@ -0,0 +1,78 @@
+git-lost+found(1)
+=================
+
+NAME
+----
+git-lost+found - Recover lost refs that luckily have not yet been pruned.
+
+SYNOPSIS
+--------
+'git-lost+found'
+
+DESCRIPTION
+-----------
+Finds dangling commits and tags from the object database, and
+creates refs to them in .git/lost+found/ directory.  Commits and
+tags that dereference to commits go to .git/lost+found/commit
+and others are stored in .git/lost+found/other directory.
+
+
+OUTPUT
+------
+One line description from the commit and tag found along with
+their object name are printed on the standard output.
+
+
+EXAMPLE
+-------
+
+Suppose you run 'git tag -f' and mistyped the tag to overwrite.
+The ref to your tag is overwritten, but until you run 'git
+prune', it is still there.
+
+------------
+$ git lost+found
+[1ef2b196d909eed523d4f3c9bf54b78cdd6843c6] GIT 0.99.9c
+...
+------------
+
+Also you can use gitk to browse how they relate to each other
+and existing (probably old) tags.
+
+------------
+$ gitk $(cd .git/lost+found/commit && echo ??*)
+------------
+
+After making sure that it is the object you are looking for, you
+can reconnect it to your regular .git/refs hierarchy.
+
+------------
+$ git cat-file -t 1ef2b196
+tag
+$ git cat-file tag 1ef2b196
+object fa41bbce8e38c67a218415de6cfa510c7e50032a
+type commit
+tag v0.99.9c
+tagger Junio C Hamano <junkio@cox.net> 1131059594 -0800
+
+GIT 0.99.9c
+
+This contains the following changes from the "master" branch, since
+...
+$ git update-ref refs/tags/not-lost-anymore 1ef2b196
+$ git rev-parse not-lost-anymore
+1ef2b196d909eed523d4f3c9bf54b78cdd6843c6
+------------
+
+Author
+------
+Written by Junio C Hamano <junkio@cox.net>
+
+Documentation
+--------------
+Documentation by Junio C Hamano and the git-list <git@vger.kernel.org>.
+
+
+GIT
+---
+Part of the gitlink:git[7] suite
diff --git a/Documentation/git.txt b/Documentation/git.txt
index b7bc4fb231..a9d47c115c 100644
--- a/Documentation/git.txt
+++ b/Documentation/git.txt
@@ -309,6 +309,9 @@ gitlink:git-convert-objects[1]::
 gitlink:git-cvsimport[1]::
 	Salvage your data out of another SCM people love to hate.
 
+gitlink:git-lost+found[1]::
+	Recover lost refs that luckily have not yet been pruned.
+
 gitlink:git-merge-one-file[1]::
 	The standard helper program to use with "git-merge-index"
 
diff --git a/Makefile b/Makefile
index b4dca5f228..b75cb13787 100644
--- a/Makefile
+++ b/Makefile
@@ -89,7 +89,8 @@ SCRIPT_SH = \
 	git-tag.sh git-verify-tag.sh git-whatchanged.sh git.sh \
 	git-applymbox.sh git-applypatch.sh git-am.sh \
 	git-merge.sh git-merge-stupid.sh git-merge-octopus.sh \
-	git-merge-resolve.sh git-merge-ours.sh git-grep.sh
+	git-merge-resolve.sh git-merge-ours.sh git-grep.sh \
+	git-lost+found.sh
 
 SCRIPT_PERL = \
 	git-archimport.perl git-cvsimport.perl git-relink.perl \
diff --git a/git-lost+found.sh b/git-lost+found.sh
new file mode 100755
index 0000000000..b6b2616e45
--- /dev/null
+++ b/git-lost+found.sh
@@ -0,0 +1,23 @@
+#!/bin/sh
+
+. git-sh-setup || die "Not a git archive."
+
+laf="$GIT_DIR/lost+found"
+rm -fr "$laf" && mkdir -p "$laf/commit" "$laf/other" || exit
+
+git fsck-objects |
+while read dangling type sha1
+do
+	case "$dangling" in
+	dangling)
+		if git-rev-parse --verify "$sha1^0" >/dev/null 2>/dev/null
+		then
+			dir="$laf/commit"
+			git-show-branch "$sha1"
+		else
+			dir="$laf/other"
+		fi
+		echo "$sha1" >"$dir/$sha1"
+		;;
+	esac
+done
-- 
cgit v1.2.3


From 07203659d0dae619f78773d3caea6b58907a1ba5 Mon Sep 17 00:00:00 2001
From: Junio C Hamano <junkio@cox.net>
Date: Thu, 10 Nov 2005 19:16:26 -0800
Subject: Rename .git/lost+found to .git/lost-found.

Just to avoid confusion that scripts poorly written by somebody
else ;-) might mistake this as a mount point, or backup tools
ignoring the directory.  The latter is probably not a big loss,
however, considering that this directory's contents are to be
used while fresh anyway.

Signed-off-by: Junio C Hamano <junkio@cox.net>
---
 Documentation/git-lost+found.txt | 8 ++++----
 git-lost+found.sh                | 2 +-
 2 files changed, 5 insertions(+), 5 deletions(-)

diff --git a/Documentation/git-lost+found.txt b/Documentation/git-lost+found.txt
index 0cb8e3bbfe..660e90b109 100644
--- a/Documentation/git-lost+found.txt
+++ b/Documentation/git-lost+found.txt
@@ -12,9 +12,9 @@ SYNOPSIS
 DESCRIPTION
 -----------
 Finds dangling commits and tags from the object database, and
-creates refs to them in .git/lost+found/ directory.  Commits and
-tags that dereference to commits go to .git/lost+found/commit
-and others are stored in .git/lost+found/other directory.
+creates refs to them in .git/lost-found/ directory.  Commits and
+tags that dereference to commits go to .git/lost-found/commit
+and others are stored in .git/lost-found/other directory.
 
 
 OUTPUT
@@ -40,7 +40,7 @@ Also you can use gitk to browse how they relate to each other
 and existing (probably old) tags.
 
 ------------
-$ gitk $(cd .git/lost+found/commit && echo ??*)
+$ gitk $(cd .git/lost-found/commit && echo ??*)
 ------------
 
 After making sure that it is the object you are looking for, you
diff --git a/git-lost+found.sh b/git-lost+found.sh
index b6b2616e45..3892f52005 100755
--- a/git-lost+found.sh
+++ b/git-lost+found.sh
@@ -2,7 +2,7 @@
 
 . git-sh-setup || die "Not a git archive."
 
-laf="$GIT_DIR/lost+found"
+laf="$GIT_DIR/lost-found"
 rm -fr "$laf" && mkdir -p "$laf/commit" "$laf/other" || exit
 
 git fsck-objects |
-- 
cgit v1.2.3


From e6bd23911efd0a2bd756c77d9e7ba6576eb739a1 Mon Sep 17 00:00:00 2001
From: Junio C Hamano <junkio@cox.net>
Date: Fri, 11 Nov 2005 22:16:59 -0800
Subject: Documentation: asciidoc sources are utf-8

git-pack-redundant documentation was encoded in latin1, which caused
asciidoc to barf, which expected to see utf-8.  Run tcs to re-encode
it in utf-8.

Also just for fun try my name in Japanese in git-lost+found
documentation ;-)

Signed-off-by: Junio C Hamano <junkio@cox.net>
---
 Documentation/git-lost+found.txt     | 2 +-
 Documentation/git-pack-redundant.txt | 4 ++--
 2 files changed, 3 insertions(+), 3 deletions(-)

diff --git a/Documentation/git-lost+found.txt b/Documentation/git-lost+found.txt
index 660e90b109..a8cc5739d7 100644
--- a/Documentation/git-lost+found.txt
+++ b/Documentation/git-lost+found.txt
@@ -66,7 +66,7 @@ $ git rev-parse not-lost-anymore
 
 Author
 ------
-Written by Junio C Hamano <junkio@cox.net>
+Written by Junio C Hamano 濱野 純 <junkio@cox.net>
 
 Documentation
 --------------
diff --git a/Documentation/git-pack-redundant.txt b/Documentation/git-pack-redundant.txt
index 5ba9272837..2e23cbc0f5 100644
--- a/Documentation/git-pack-redundant.txt
+++ b/Documentation/git-pack-redundant.txt
@@ -32,11 +32,11 @@ OPTIONS
 
 Author
 ------
-Written by Lukas Sandström <lukass@etek.chalmers.se>
+Written by Lukas Sandström <lukass@etek.chalmers.se>
 
 Documentation
 --------------
-Documentation by Lukas Sandström <lukass@etek.chalmers.se>
+Documentation by Lukas Sandström <lukass@etek.chalmers.se>
 
 See-Also
 --------
-- 
cgit v1.2.3


From 7765e7ebda7e273bca34e87110be899447068b58 Mon Sep 17 00:00:00 2001
From: Junio C Hamano <junkio@cox.net>
Date: Fri, 11 Nov 2005 22:28:03 -0800
Subject: Ignore built git-lost+found.

Signed-off-by: Junio C Hamano <junkio@cox.net>
---
 .gitignore | 1 +
 1 file changed, 1 insertion(+)

diff --git a/.gitignore b/.gitignore
index 1d1aa57676..328b399f9f 100644
--- a/.gitignore
+++ b/.gitignore
@@ -42,6 +42,7 @@ git-index-pack
 git-init-db
 git-local-fetch
 git-log
+git-lost+found
 git-ls-files
 git-ls-remote
 git-ls-tree
-- 
cgit v1.2.3