* Re: [PATCH] several typos in tutorial
From: Alexey Nezhdanov @ 2005-06-02 12:45 UTC (permalink / raw)
To: git; +Cc: Vincent Hanquez, Linus Torvalds
In-Reply-To: <20050602124143.GA31483@snarc.org>
On thursday, 02 June 2005 16:41 Vincent Hanquez wrote:
> On Thu, Jun 02, 2005 at 04:02:07PM +0400, Alexey Nezhdanov wrote:
> > Git arhives are normally totally self-sufficient, and it's worth noting
>
> ^^^^^^^
> and one more here
Why? It's ok to speak about many [existing] archives here.
--
Respectfully
Alexey Nezhdanov
^ permalink raw reply
* Re: [PATCH] several typos in tutorial
From: Vincent Hanquez @ 2005-06-02 12:51 UTC (permalink / raw)
To: Alexey Nezhdanov; +Cc: git, Linus Torvalds
In-Reply-To: <200506021645.15247.snake@penza-gsm.ru>
On Thu, Jun 02, 2005 at 04:45:15PM +0400, Alexey Nezhdanov wrote:
> On thursday, 02 June 2005 16:41 Vincent Hanquez wrote:
> > On Thu, Jun 02, 2005 at 04:02:07PM +0400, Alexey Nezhdanov wrote:
> > > Git arhives are normally totally self-sufficient, and it's worth noting
> >
> > ^^^^^^^
> > and one more here
> Why? It's ok to speak about many [existing] archives here.
it's missing a 'c'
--
Vincent Hanquez
^ permalink raw reply
* cg-push protocol proposal
From: McMullan, Jason @ 2005-06-02 12:54 UTC (permalink / raw)
To: Git Mailing List
[-- Attachment #1: Type: text/plain, Size: 1433 bytes --]
I'd like to propose the following protocol for 'pushes'. Assume that a
'git-daemon' is the 'server', and is talking on stdin/stdout.
Each command is an ascii string, followed by a LF (\n)
Request current head ID:
head <head-name>\n
Responses:
head <head-name> <sha1>\n
error <head-name> <hex-code> <error-string>\n
Request a SHA1 blob from the server
send <sha1>\n
Responses:
send <sha1> <hex-size>\n<bytes...>
error <sha1> <hex-code> <error-string>\n
Update head ID to a SHA1 (the SHA1 may already be in the server's DB)
head <head-name> <old-sha1> <sha1>\n
1) Response if <head-name> is now <sha1>:
head <head-name> <sha1>\n
Response if error, or head locked by someone else updating:
error <head-name> <hex-code> <error-string>\n
Response if <sha1> is not in the database:
send <sha1>\n - Server needs the blob
2) Client response if 'send' is returned:
send <sha1> <hex-size>\n<bytes...>
3) Response if more objects are needed
(ie you sent a commit or tree object)
send <new-sha1>\n - Server needs blob
Remember the SHA1 you sent, 'call' step 2) with new-sha1
Goto 3)
Response if send succeeded:
exists <sha1>\n
Response if send failed:
error <sha1> <hex-code> <error-string>\n
TODO: Tags
--
Jason McMullan <jason.mcmullan@timesys.com>
TimeSys Corporation
[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]
^ permalink raw reply
* Re: [PATCH] several typos in tutorial
From: Alexey Nezhdanov @ 2005-06-02 12:56 UTC (permalink / raw)
To: Linus Torvalds; +Cc: git, Vincent Hanquez
In-Reply-To: <20050602125124.GA31680@snarc.org>
Signed-off-by: Alexey Nezhdanov <snake@penza-gsm.ru>
---
diff --git a/Documentation/tutorial.txt b/Documentation/tutorial.txt
--- a/Documentation/tutorial.txt
+++ b/Documentation/tutorial.txt
@@ -298,7 +298,7 @@ have committed something, we can also le
Unlike "git-diff-files", which showed the difference between the index
file and the working directory, "git-diff-cache" shows the differences
-between a committed _tree_ and the index file. In other words,
+between a committed _tree_ and the working directory. In other words,
git-diff-cache wants a tree to be diffed against, and before we did the
commit, we couldn't do that, because we didn't have anything to diff
against.
@@ -423,10 +423,10 @@ With that, you should now be having some
can explore on your own.
- Copoying archives
- -----------------
+ Copying archives
+ ----------------
-Git arhives are normally totally self-sufficient, and it's worth noting
+Git archives are normally totally self-sufficient, and it's worth noting
that unlike CVS, for example, there is no separate notion of
"repository" and "working tree". A git repository normally _is_ the
working tree, with the local git information hidden in the ".git"
^ permalink raw reply
* Re: [PATCH] several typos in tutorial
From: Alexey Nezhdanov @ 2005-06-02 13:00 UTC (permalink / raw)
To: git; +Cc: Vincent Hanquez
In-Reply-To: <20050602125124.GA31680@snarc.org>
On thursday, 02 June 2005 16:51 Vincent Hanquez wrote:
> On Thu, Jun 02, 2005 at 04:45:15PM +0400, Alexey Nezhdanov wrote:
> > On thursday, 02 June 2005 16:41 Vincent Hanquez wrote:
> > > On Thu, Jun 02, 2005 at 04:02:07PM +0400, Alexey Nezhdanov wrote:
> > > > Git arhives are normally totally self-sufficient, and it's worth
> > > > noting
> > >
> > > ^^^^^^^
> > > and one more here
> >
> > Why? It's ok to speak about many [existing] archives here.
>
> it's missing a 'c'
ok :)
--
Respectfully
Alexey Nezhdanov
^ permalink raw reply
* [PATCH] cg-log: also search the initial commit for files
From: Jonas Fonseca @ 2005-06-02 13:10 UTC (permalink / raw)
To: Petr Baudis; +Cc: git
When restricting the log to a set of files pass --root to git-diff-tree if
no parent is found so the initial commit is also checked.
Signed-off-by: Jonas Fonseca <fonseca@diku.dk>
---
cg-log | 4 +++-
1 files changed, 3 insertions(+), 1 deletions(-)
diff --git a/cg-log b/cg-log
--- a/cg-log
+++ b/cg-log
@@ -167,7 +167,9 @@ $revls | $revsort | while read time comm
[ "$revfmt" = "git-rev-list" ] && commit="$time"
if [ $# -ne 0 ]; then
parent=$(git-cat-file commit $commit | sed -n '2s/parent //p;2Q')
- [ "$parent" ] && [ "$(git-diff-tree -r $commit $parent "$@")" ] || continue
+ diff_ops=
+ [ "$parent" ] || diff_ops=--root
+ [ "$(git-diff-tree -r $diff_ops $commit $parent "$@")" ] || continue
fi
if [ "$user" ]; then
git-cat-file commit $commit | grep -e '^author ' -e '^committer ' | grep -qi "$user" || continue
--
Jonas Fonseca
^ permalink raw reply
* Re: gitk-1.1 out
From: Sean @ 2005-06-02 13:32 UTC (permalink / raw)
To: Paul Mackerras; +Cc: git
In-Reply-To: <17053.35147.52729.794561@cargo.ozlabs.ibm.com>
On Wed, June 1, 2005 6:09 am, Paul Mackerras said:
> The latest version of gitk is at:
>
> http://ozlabs.org/~paulus/gitk/gitk-1.1.tar.gz
>
> (yes, a real tarball this time, with a README even. :)
>
Hi Paul,
Looks really good! Thought i'd share some homespun rpms that upgrade
Fedora TCL/Tk to use anti-aliased fonts for gitk. They make the text
displayed in gitk a little nicer to read. Only tested on Fedora FC3 and
there's no warranty, but they should work for others too.
The rpms and a couple of screenshots are available from:
http://git.homelinux.com
Cheers,
Sean
^ permalink raw reply
* [PATCH] cg-log: cleanup line wrapping by using bash internals
From: Jonas Fonseca @ 2005-06-02 14:46 UTC (permalink / raw)
To: Petr Baudis; +Cc: Junio C Hamano, git
Use ${#var} instead of echo + wc combo. Additionally also gives
a minor speedup.
Signed-off-by: Jonas Fonseca <fonseca@diku.dk>
---
cg-log -f
new code:
real 1m15.462s
user 0m27.195s
sys 0m40.639s
old code:
real 1m38.222s
user 0m32.563s
sys 0m56.034s
BTW, I noticed the following errors:
fatal: internal error in diffcore: unmodified entry remains
fatal: internal error in diffcore: unmodified entry remains
fatal: internal error in diffcore: unmodified entry remains
with both current cogito and git.
To reproduce run either of the following in the cogito repo:
git-diff-tree -r 7c1f9aa894ce91928d982a0b197ab596375825a3 e30dd6c68e576d37bddd011aa7131a6d30297b4c
git-diff-tree -r c49cd3e4f1dfe4ccbf2b8d00188beaa251fee028 9fec8b26eff58e1f595e8619abf1e42c07645ff8
The last one also triggers in the git repo.
The log entries for the two commits are:
commit 6616d1835e81ac0d2304702102d210451c04832a
tree 7c1f9aa894ce91928d982a0b197ab596375825a3
parent e30dd6c68e576d37bddd011aa7131a6d30297b4c
parent e8871e88adca0637eb0299a41d85400beac928bd
author Petr Baudis <pasky@ucw.cz> Sun, 17 Apr 2005 19:30:32 +0200
committer Petr Baudis <xpasky@machine> Sun, 17 Apr 2005 19:30:32 +0200
Merging: d72ff74f5fd172c6ec9630ee8e08895a0525dcfe
Merge with Linus. Nothing particularily interesting.
commit e44794706eeb57f2ee38ed1604821aa38b8ad9d2
tree c49cd3e4f1dfe4ccbf2b8d00188beaa251fee028
parent 9fec8b26eff58e1f595e8619abf1e42c07645ff8
author Linus Torvalds <torvalds@ppc970.osdl.org> Sat, 16 Apr 2005 22:26:31 -0700
committer Linus Torvalds <torvalds@ppc970.osdl.org> Sat, 16 Apr 2005 22:26:31 -0700
Be much more liberal about the file mode bits.
We only really care about the difference between a file being executable
or not (by its owner). Everything else we leave for the user umask to
decide.
Any ideas?
cg-log | 4 ++--
1 files changed, 2 insertions(+), 2 deletions(-)
diff --git a/cg-log b/cg-log
--- a/cg-log
+++ b/cg-log
@@ -129,8 +129,8 @@ list_commit_files()
$list_cmd | cut -f 2- | while read file; do
echo -n "$sep"
sep=", "
- if [ $(echo "$line$sep$file" | wc -c) -le 75 ]; then
- line="$line$sep$file"
+ line="$line$sep$file"
+ if [ "${#line}" -le 74 ]; then
echo -n "$file"
else
line=" $file"
--
Jonas Fonseca
^ permalink raw reply
* Re: [SCRIPT] cg-rpush & locking
From: Linus Torvalds @ 2005-06-02 14:50 UTC (permalink / raw)
To: Tony Lindgren
Cc: Matthias Urlichs, Daniel Barkalow, Thomas Glanzmann,
Nicolas Pitre, git
In-Reply-To: <20050602073205.GA31482@muru.com>
On Thu, 2 Jun 2005, Tony Lindgren wrote:
>
> I don't think locking for the duration of the push really is a problem.
> It is unlikely that there would be so many people pushing that it would
> cause inconvenience... Of course it would be nice to optimize it if
> possible.
I don't think the locking is a _huge_ issue - the only real problem I had
with locking with BK was that readers could block a writer (ie I couldn't
push to my public tree if there were people downloading from it), and git
doesn't have that problem. I only push to trees that are my private ones
anyway.
The real reason I'd prefer to not do locking is that _if_ the remote tree
is actually more than just a CVS-like "public repository", ie if somebody
actually does _development_ in the remote tree (hey, it may be crazy, but
git makes this usage pattern possible), then we should eventually plan on
having all of the regular "git-commit-script" and "git-pull-script" etc
_also_ do locking, since they also change HEAD.
And that's going to be a lot easier if we only do a cmp-xchg and fail at
the end (this concurrent change and "remote repo" usage is really quite
wrong, since it basically mean that you consider somebody's development
tree to be "public", and that's not what git is all about, but whatever..)
But this is not a huge issue. The most important thing is to make sure
that the new HEAD is written last, regardless, so that at least local
readers (including things like "fsck" that can take a _loong_ time) always
see consistent state.
> I would assume the biggest problem for most people is how they can push
> through a firewall. From that point of view it would make sense to do
> the push as a cgi script rather than something over ssh. And with a
> cgi script you can of course optimize the locking and use tmp files
> before renaming which are a bit hard to do with rsync.
Me personally, I want ssh as a major option. There are tons of machines
(every single of my own ones) that I use that don't let anything but ssh
through.
But having alternatives is good. But ssh should be the first and primary
one, since it also means that there can't be any new security issues (ie
you won't be opening up any new holes by installing git on the remote
machine).
Linus
^ permalink raw reply
* Re: I want to release a "git-1.0"
From: Linus Torvalds @ 2005-06-02 14:52 UTC (permalink / raw)
To: Eric W. Biederman; +Cc: Git Mailing List
In-Reply-To: <m18y1tb55c.fsf@ebiederm.dsl.xmission.com>
On Thu, 2 Jun 2005, Eric W. Biederman wrote:
>
> So I need to do a git checkout of the latest version of git to
> read the tutorial? So I can figure out how to use git?
Just use the gitweb thing, it's easy to read off there..
Linus
^ permalink raw reply
* Re: cg-push protocol proposal [update]
From: McMullan, Jason @ 2005-06-02 15:00 UTC (permalink / raw)
To: Git Mailing List
In-Reply-To: <1117716883.32257.42.camel@jmcmullan.timesys>
[-- Attachment #1: Type: text/plain, Size: 469 bytes --]
On Thu, 2005-06-02 at 08:47 -0400, McMullan, Jason wrote:
I'd like to propose the following protocol for 'pushes'. Assume that a
'git-daemon' is the 'server', and is talking on stdin/stdout.
If you want to only do cmp-xchg style head updates, just 'send' the
commit object first (the protocol will request any missing pieces),
then do the 'head <head-id> <old-sha1> <new-sha1>'.
--
Jason McMullan <jason.mcmullan@timesys.com>
TimeSys Corporation
[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]
^ permalink raw reply
* [PATCH] Modify git-rev-list to linearise the commit history in merge order.
From: Jon Seymour @ 2005-06-02 15:16 UTC (permalink / raw)
To: Git Mailing List; +Cc: Linus Torvalds, Paul Mackerras
In-Reply-To: <20050602151332.29183.qmail@blackcubes.dyndns.org>
[PATCH] Modify git-rev-list to linearise the commit history in merge order.
This patch linearises the GIT commit history graph into merge order
which is defined by invariants specified in Documentation/git-rev-list.txt.
The linearisation produced by this patch is superior in an objective sense
to that produced by the existing git-rev-list implementation in that
the linearisation produced is guaranteed to have the minimum number of
discontinuities, where a discontinuity is defined as an adjacent pair of
commits in the output list which are not related in a direct child-parent
relationship.
A test script, t/t5000-rev-list.sh, includes a test which demonstrates
that the linearisation produced by --merge-order has less discontinuities
than the linearisation produced by git-rev-list without the --merge-order
flag specified. To see this, do the following:
cd t
./t5000-rev-list.sh
cd trash
cat actual-default-order
cat actual-merge-order
The existing behaviour of git-rev-list is preserved, by default. To obtain
the modified behaviour, specify --merge-order or --merge-order --show-breaks
on the command line.
This version of the patch has been tested on the git repository and
also on the linux-2.6
repository and has reasonable performance on both.
For more details about this change, refer to Documentation/git-rev-list.txt
and http://blackcubes.dyndns.org/epoch/.
Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
diff --git a/Makefile b/Makefile
--- a/Makefile
+++ b/Makefile
@@ -40,9 +40,9 @@ install: $(PROG) $(SCRIPTS)
$(INSTALL) $(PROG) $(SCRIPTS) $(dest)$(bin)
LIB_OBJS=read-cache.o sha1_file.o usage.o object.o commit.o tree.o blob.o \
- tag.o delta.o date.o index.o diff-delta.o patch-delta.o
+ tag.o delta.o date.o index.o diff-delta.o patch-delta.o epoch.o
LIB_FILE=libgit.a
-LIB_H=cache.h object.h blob.h tree.h commit.h tag.h delta.h
+LIB_H=cache.h object.h blob.h tree.h commit.h tag.h delta.h epoch.h
LIB_H += strbuf.h
LIB_OBJS += strbuf.o
@@ -134,6 +134,7 @@ diffcore-pathspec.o : $(LIB_H) diffcore.
diffcore-pickaxe.o : $(LIB_H) diffcore.h
diffcore-break.o : $(LIB_H) diffcore.h
diffcore-order.o : $(LIB_H) diffcore.h
+epoch.o: $(LIB_H)
test: all
$(MAKE) -C t/ all
diff --git a/commit.c b/commit.c
--- a/commit.c
+++ b/commit.c
@@ -129,7 +129,7 @@ void free_commit_list(struct commit_list
}
}
-static void insert_by_date(struct commit_list **list, struct commit *item)
+void insert_by_date(struct commit_list **list, struct commit *item)
{
struct commit_list **pp = list;
struct commit_list *p;
@@ -254,3 +254,25 @@ unsigned long pretty_print_commit(const
buf[offset] = '\0';
return offset;
}
+
+struct commit *pop_commit(struct commit_list **stack)
+{
+ struct commit_list *top = *stack;
+ struct commit *item = top ? top->item : NULL;
+
+ if (top) {
+ *stack = top->next;
+ free(top);
+ }
+ return item;
+}
+
+int count_parents(struct commit * commit)
+{
+ int count = 0;
+ struct commit_list * parents = commit->parents;
+ for (count=0;parents; parents=parents->next,count++)
+ ;
+ return count;
+}
+
diff --git a/commit.h b/commit.h
--- a/commit.h
+++ b/commit.h
@@ -32,6 +32,8 @@ void free_commit_list(struct commit_list
void sort_by_date(struct commit_list **list);
+void insert_by_date(struct commit_list **list, struct commit *item);
+
extern unsigned long pretty_print_commit(const char *msg, unsigned
long len, char *buf, unsigned long space);
@@ -41,4 +43,7 @@ extern unsigned long pretty_print_commit
struct commit *pop_most_recent_commit(struct commit_list **list,
unsigned int mark);
+struct commit *pop_commit(struct commit_list **stack);
+
+int count_parents(struct commit * commit);
#endif /* COMMIT_H */
diff --git a/epoch.c b/epoch.c
new file mode 100644
--- /dev/null
+++ b/epoch.c
@@ -0,0 +1,454 @@
+/*
+ * Copyright (c) 2005, Jon Seymour
+ *
+ * For more information about epoch theory on which this module is based,
+ * refer to http://blackcubes.dyndns.org/epoch/. That web page defines
+ * terms such as "epoch" and "minimal, non-linear epoch" and provides
rationales
+ * for some of the algorithms used here.
+ *
+ */
+#include <stdlib.h>
+#include <openssl/bn.h> // provides arbitrary
precision integers required to accurately represent fractional mass
+#include "cache.h"
+#include "commit.h"
+#include "epoch.h"
+
+struct fraction {
+ BIGNUM numerator;
+ BIGNUM denominator;
+};
+
+#define HAS_EXACTLY_ONE_PARENT(n) ((n)->parents && !(n)->parents->next)
+
+static BN_CTX *context = NULL;
+static struct fraction *one = NULL;
+static struct fraction *zero = NULL;
+
+static BN_CTX *get_BN_CTX()
+{
+ if (!context) {
+ context = BN_CTX_new();
+ }
+ return context;
+}
+
+static struct fraction *new_zero()
+{
+ struct fraction *result = xmalloc(sizeof(*result));
+ BN_init(&result->numerator);
+ BN_init(&result->denominator);
+ BN_zero(&result->numerator);
+ BN_one(&result->denominator);
+ return result;
+}
+
+static void clear_fraction(struct fraction *fraction)
+{
+ BN_clear(&fraction->numerator);
+ BN_clear(&fraction->denominator);
+}
+
+static struct fraction *divide(struct fraction *result, struct
fraction *fraction, int divisor)
+{
+ BIGNUM bn_divisor;
+
+ BN_init(&bn_divisor);
+ BN_set_word(&bn_divisor, divisor);
+
+ BN_copy(&result->numerator, &fraction->numerator);
+ BN_mul(&result->denominator, &fraction->denominator,
&bn_divisor, get_BN_CTX());
+
+ BN_clear(&bn_divisor);
+ return result;
+}
+
+static struct fraction *init_fraction(struct fraction *fraction)
+{
+ BN_init(&fraction->numerator);
+ BN_init(&fraction->denominator);
+ BN_zero(&fraction->numerator);
+ BN_one(&fraction->denominator);
+ return fraction;
+}
+
+static struct fraction *get_one()
+{
+ if (!one) {
+ one = new_zero();
+ BN_one(&one->numerator);
+ }
+ return one;
+}
+
+static struct fraction *get_zero()
+{
+ if (!zero) {
+ zero = new_zero();
+ }
+ return zero;
+}
+
+static struct fraction *copy(struct fraction *to, struct fraction *from)
+{
+ BN_copy(&to->numerator, &from->numerator);
+ BN_copy(&to->denominator, &from->denominator);
+ return to;
+}
+
+static struct fraction *add(struct fraction *result, struct fraction
*left, struct fraction *right)
+{
+ BIGNUM a, b, gcd;
+
+ BN_init(&a);
+ BN_init(&b);
+ BN_init(&gcd);
+
+ BN_mul(&a, &left->numerator, &right->denominator, get_BN_CTX());
+ BN_mul(&b, &left->denominator, &right->numerator, get_BN_CTX());
+ BN_mul(&result->denominator, &left->denominator,
&right->denominator, get_BN_CTX());
+ BN_add(&result->numerator, &a, &b);
+
+ BN_gcd(&gcd, &result->denominator, &result->numerator, get_BN_CTX());
+ BN_div(&result->denominator, NULL, &result->denominator, &gcd,
get_BN_CTX());
+ BN_div(&result->numerator, NULL, &result->numerator, &gcd,
get_BN_CTX());
+
+ BN_clear(&a);
+ BN_clear(&b);
+ BN_clear(&gcd);
+
+ return result;
+}
+
+static int compare(struct fraction *left, struct fraction *right)
+{
+ BIGNUM a, b;
+
+ int result;
+
+ BN_init(&a);
+ BN_init(&b);
+
+ BN_mul(&a, &left->numerator, &right->denominator, get_BN_CTX());
+ BN_mul(&b, &left->denominator, &right->numerator, get_BN_CTX());
+
+ result = BN_cmp(&a, &b);
+
+ BN_clear(&a);
+ BN_clear(&b);
+
+ return result;
+}
+
+struct mass_counter {
+ struct fraction seen;
+ struct fraction pending;
+};
+
+static struct mass_counter *new_mass_counter(struct commit *commit,
struct fraction *pending)
+{
+ struct mass_counter *mass_counter = xmalloc(sizeof(*mass_counter));
+ memset(mass_counter, 0, sizeof(*mass_counter));
+
+ init_fraction(&mass_counter->seen);
+ init_fraction(&mass_counter->pending);
+
+ copy(&mass_counter->pending, pending);
+ copy(&mass_counter->seen, get_zero());
+
+ commit->object.util = mass_counter;
+
+ return mass_counter;
+}
+
+static void free_mass_counter(struct mass_counter *counter)
+{
+ clear_fraction(&counter->seen);
+ clear_fraction(&counter->pending);
+ free(counter);
+}
+
+//
+// Finds the base node of an epoch.
+//
+// This algorithm uses a conservation of mass approach.
+//
+// The head starts with a weight of 1 and distributes equal portions
+// along each edge to each of its parents. The process continues until
+// one node discovers that it has acquired a total mass of 1 from its
+// descendents. This node is the base node.
+//
+// Importantly the queue of nodes to be processed is sorted in
+// reverse date order and each node occupies at most one
+// position in the queue simultaneously. These two properties
+// do not effect the algorithm's correctness. However assuming most, but
+// not all, timestamps are sane they do prevent the algorithm becoming
+// exponential by ensuring that most nodes are only visited once.
+// This is true because mass is only propagated through the network
+// when we are pretty sure we are not going to see any more coming
+// our way. The occasional bad timestamp will mean that we are
+// wrong, occasionally, but this does not matter too much.
+//
+static int find_base(struct commit *head, struct commit **boundary)
+{
+ int ret = 0;
+
+ struct commit_list *cleaner = NULL;
+ struct commit_list *pending = NULL;
+
+ *boundary = NULL;
+
+ // we inject a mass of 1 unit here
+
+ new_mass_counter(head, get_one());
+
+ commit_list_insert(head, &pending);
+ commit_list_insert(head, &cleaner);
+
+ while (!*boundary && pending && !ret) {
+
+ struct commit *latest = pop_commit(&pending);
+ struct mass_counter *latest_node = (struct
mass_counter *) latest->object.util;
+
+ if ((ret = parse_commit(latest)))
+ continue;
+
+ add(&latest_node->seen, &latest_node->seen,
&latest_node->pending);
+
+ int num_parents = count_parents(latest);
+
+ if (num_parents) {
+
+ struct fraction distribution;
+
+ divide(init_fraction(&distribution),
&latest_node->pending, num_parents);
+
+ struct commit_list *parents;
+
+ for (parents = latest->parents; parents;
parents = parents->next) {
+ struct commit *parent = parents->item;
+ struct mass_counter *parent_node =
(struct mass_counter *) parent->object.util;
+ if (!parent_node) {
+ parent_node =
new_mass_counter(parent, &distribution);
+ commit_list_insert(parent, &cleaner);
+ insert_by_date(&pending, parent);
+ } else {
+ if
(!compare(&parent_node->pending, get_zero())) {
+
copy(&parent_node->pending, &distribution);
+
insert_by_date(&pending, parent);
+ } else {
+
add(&parent_node->pending, &parent_node->pending, &distribution);
+ }
+ }
+ }
+ }
+
+ if (!compare(&latest_node->seen, get_one()) && (latest
!= head)) {
+ // if this node has seen one unit of mass, it
must be the base, so mark
+ // the boundary which will cause the loop to stop.
+ *boundary = latest;
+ }
+
+ copy(&latest_node->pending, get_zero());
+
+ }
+
+ for (; cleaner;) {
+ struct commit *next = pop_commit(&cleaner);
+ free_mass_counter((struct mass_counter *) next->object.util);
+ next->object.util = NULL;
+ }
+
+ if (pending)
+ free_commit_list(pending);
+
+ return ret;
+
+}
+
+//
+// This procedure traverses to the boundary of the first epoch in the epoch
+// sequence of the epoch headed at head_of_epoch. This is either the end of
+// the maximal linear epoch or the base of a minimal non-linear epoch.
+//
+// The queue of pending nodes is sorted in reverse date order and each node
+// is currently in the queue at most once.
+//
+static int find_next_epoch_boundary(struct commit *head_of_epoch,
struct commit **boundary)
+{
+ int ret;
+ struct commit *item = head_of_epoch;
+
+ ret = parse_commit(item);
+ if (ret)
+ return ret;
+
+ if (HAS_EXACTLY_ONE_PARENT(item)) {
+
+ // we are at the start of a maximimal linear epoch ..
traverse to the end
+
+ // traverse to the end of a maximal linear epoch
+ while (HAS_EXACTLY_ONE_PARENT(item) && !ret) {
+ item = item->parents->item;
+ ret = parse_commit(item);
+ }
+ *boundary = item;
+
+ } else {
+
+ // otherwise, we are at the start of a minimal, non-linear
+ // epoch - find the common base of all parents.
+
+ ret = find_base(item, boundary);
+
+ }
+
+ return ret;
+}
+
+//
+// Returns non-zero if parent is known to be a parent of child.
+//
+static int is_parent_of(struct commit *parent, struct commit *child)
+{
+ struct commit_list *parents;
+ for (parents = child->parents; parents; parents = parents->next) {
+ if (!memcmp(parent->object.sha1,
parents->item->object.sha1, sizeof(parents->item->object.sha1)))
+ return 1;
+ }
+ return 0;
+}
+
+static void push_onto_merge_order_stack(struct commit_list **stack,
struct commit *item)
+{
+ struct commit_list *top = *stack;
+ if (top && (top->item->object.flags & MERGE_ORDER_BREAK_FLAG)) {
+ if (is_parent_of(top->item, item)) {
+ top->item->object.flags &= ~MERGE_ORDER_BREAK_FLAG;
+ }
+ }
+ commit_list_insert(item, stack);
+}
+
+//
+// Sorts the nodes of the first epoch of the epoch sequence of the
epoch headed at head
+// into merge order.
+//
+static void sort_first_epoch(struct commit *head, struct commit_list **stack)
+{
+ parse_commit(head);
+
+ head->object.flags |= MERGE_ORDER_VISIT_FLAG;
+
+ struct commit_list *parents;
+
+ struct commit_list *reversed_parents = NULL;
+
+ //
+ // parse_commit builds the parent list in reverse order with
respect to the order of
+ // the git-commit-tree arguments.
+ //
+ // so we need to reverse this list to output the oldest (or
most "local") commits last.
+ //
+
+ for (parents = head->parents; parents; parents = parents->next) {
+ commit_list_insert(parents->item, &reversed_parents);
+ }
+
+ //
+ // todo: by sorting the parents in a different order, we can alter the
+ // merge order to show contemporaneous changes in parallel branches
+ // occurring after "local" changes. This is useful for a developer
+ // when a developer wants to see all changes that were incorporated
+ // into the same merge as her own changes occur after her own
+ // changes.
+ //
+
+ for (; reversed_parents;) {
+ struct commit *parent = pop_commit(&reversed_parents);
+ parse_commit(parent);
+ if (!(parent->object.flags & MERGE_ORDER_VISIT_FLAG)) {
+ if (parent->object.flags & MERGE_ORDER_EPOCH_FLAG) {
+ if (*stack) {
+ die("something else is on the
stack - %s\n", sha1_to_hex((*stack)->item->object.sha1));
+ }
+ push_onto_merge_order_stack(stack, parent);
+ parent->object.flags |= MERGE_ORDER_VISIT_FLAG;
+ } else {
+ sort_first_epoch(parent, stack);
+ if (reversed_parents) {
+ //
+ // this indicates a possible
discontinuity
+ // it may not be be actual
discontinuity if
+ // the head of parent N
happens to be the tail
+ // of parent N+1
+ //
+ // the next push onto the
stack will resolve the question
+ //
+ (*stack)->item->object.flags
|= MERGE_ORDER_BREAK_FLAG;
+ }
+ }
+ }
+ }
+
+ push_onto_merge_order_stack(stack, head);
+}
+
+//
+// Sorts an arbitrary epoch into merge order by sorting each epoch
+// of its epoch sequence into order.
+//
+// Note: this algorithm currently leaves traces of its execution in the
+// object flags of nodes it discovers. This should probably be fixed.
+//
+int sort_in_merge_order(struct commit *head_of_epoch, emitter_func emitter)
+{
+ struct commit *next;
+ int ret = 0;
+ int stop = 0;
+
+ parse_commit(head_of_epoch);
+
+ for (next = head_of_epoch; next && next->parents && !ret && !stop;) {
+
+ struct commit *base = NULL;
+
+ ret = find_next_epoch_boundary(next, &base);
+ if (ret)
+ return ret;
+
+ next->object.flags |= MERGE_ORDER_EPOCH_FLAG;
+ if (base) {
+ base->object.flags |= MERGE_ORDER_EPOCH_FLAG;
+ }
+
+ if (HAS_EXACTLY_ONE_PARENT(next)) {
+
+ while (HAS_EXACTLY_ONE_PARENT(next) && !stop && !ret) {
+ stop = (*emitter) (next);
+ next = next->parents->item;
+ ret = parse_commit(next);
+ }
+
+ } else {
+
+ struct commit_list *stack = NULL;
+ sort_first_epoch(next, &stack);
+ for (; stack && !stop;) {
+ next = pop_commit(&stack);
+ if (stack) {
+ stop = (*emitter) (next);
+ }
+ }
+ if (stack) {
+ free_commit_list(stack);
+ }
+ }
+
+ }
+
+ if (next && !stop) {
+ stop = (*emitter) (next);
+ }
+
+ return ret;
+}
diff --git a/epoch.h b/epoch.h
new file mode 100644
--- /dev/null
+++ b/epoch.h
@@ -0,0 +1,12 @@
+#ifndef EPOCH_H
+#define EPOCH_H
+
+typedef int (*emitter_func) (struct commit *);
+
+int sort_in_merge_order(struct commit *head_of_epoch, emitter_func emitter);
+
+#define MERGE_ORDER_EPOCH_FLAG (1u<<3)
+#define MERGE_ORDER_VISIT_FLAG (1u<<4)
+#define MERGE_ORDER_BREAK_FLAG (1u<<5)
+
+#endif /* EPOCH_H */
diff --git a/object.h b/object.h
--- a/object.h
+++ b/object.h
@@ -15,6 +15,7 @@ struct object {
const char *type;
struct object_list *refs;
struct object_list *attached_deltas;
+ void *util;
};
extern int nr_objs;
diff --git a/rev-list.c b/rev-list.c
--- a/rev-list.c
+++ b/rev-list.c
@@ -1,5 +1,6 @@
#include "cache.h"
#include "commit.h"
+#include "epoch.h"
#define SEEN (1u << 0)
#define INTERESTING (1u << 1)
@@ -11,7 +12,8 @@ static const char rev_list_usage[] =
" --max-age=epoch\n"
" --min-age=epoch\n"
" --header\n"
- " --pretty";
+ " --pretty\n"
+ " --merge-order [ --show-breaks ]";
static void mark_parents_uninteresting(struct commit *commit)
{
@@ -36,18 +38,63 @@ static int everybody_uninteresting(struc
return 1;
}
+static unsigned long max_age = -1;
+static unsigned long min_age = -1;
+static int max_count = -1;
+static int verbose_header = 0, show_parents = 0, pretty_print = 0,
merge_order = 0, show_breaks = 0;
+static const char *prefix = "";
+static int hdr_termination = 0;
+
+static int process_commit(struct commit * commit)
+{
+ if (commit->object.flags & UNINTERESTING)
+ return 0;
+ if (min_age != -1 && (commit->date > min_age))
+ return 0;
+ if (max_age != -1 && (commit->date < max_age))
+ return 1;
+ if (max_count != -1 && !max_count--)
+ return 1;
+
+ if (!show_breaks) {
+ printf("%s%s", prefix, sha1_to_hex(commit->object.sha1));
+ if (show_parents) {
+ struct commit_list *parents = commit->parents;
+ while (parents) {
+ printf(" %s",
sha1_to_hex(parents->item->object.sha1));
+ parents = parents->next;
+ }
+ }
+ putchar('\n');
+ if (verbose_header) {
+ const char *buf = commit->buffer;
+ if (pretty_print) {
+ static char pretty_header[16384];
+ pretty_print_commit(commit->buffer,
~0, pretty_header, sizeof(pretty_header));
+ buf = pretty_header;
+ }
+ printf("%s%c", buf, hdr_termination);
+ }
+ } else {
+ char c='|';
+ if (commit->object.flags & MERGE_ORDER_BREAK_FLAG) {
+ c = '^';
+ } else if (commit->object.flags & MERGE_ORDER_EPOCH_FLAG) {
+ c = '=';
+ }
+ printf("%c %s\n", c, sha1_to_hex(commit->object.sha1));
+ }
+
+ return 0;
+}
+
int main(int argc, char **argv)
{
int nr_sha;
unsigned char sha1[2][20];
struct commit_list *list = NULL;
struct commit *commit, *end;
- int i, verbose_header = 0, show_parents = 0, pretty_print = 0;
- int hdr_termination = 0;
- const char *prefix = "";
- unsigned long max_age = -1;
- unsigned long min_age = -1;
- int max_count = -1;
+ int i;
nr_sha = 0;
for (i = 1 ; i < argc; i++) {
@@ -80,8 +127,16 @@ int main(int argc, char **argv)
show_parents = 1;
continue;
}
+ if (!strncmp(arg, "--merge-order", 13)) {
+ merge_order = 1;
+ continue;
+ }
+ if (!strncmp(arg, "--show-breaks", 13)) {
+ show_breaks = 1;
+ continue;
+ }
- if (nr_sha > 2 || get_sha1(arg, sha1[nr_sha]))
+ if (nr_sha > 2 || get_sha1(arg, sha1[nr_sha])||
(show_breaks && !merge_order))
usage(rev_list_usage);
nr_sha++;
}
@@ -118,36 +173,19 @@ int main(int argc, char **argv)
} while (list);
list = newlist;
}
+
+ if (!merge_order) {
+ while (list) {
+ struct commit *commit =
pop_most_recent_commit(&list, SEEN);
+ if (process_commit(commit)) {
+ break;
+ }
+ }
+ } else {
+ if (sort_in_merge_order(commit, &process_commit)) {
+ die("merge order sort failed\n");
+ }
+ }
- while (list) {
- struct commit *commit = pop_most_recent_commit(&list, SEEN);
-
- if (commit->object.flags & UNINTERESTING)
- continue;
- if (min_age != -1 && (commit->date > min_age))
- continue;
- if (max_age != -1 && (commit->date < max_age))
- break;
- if (max_count != -1 && !max_count--)
- break;
- printf("%s%s", prefix, sha1_to_hex(commit->object.sha1));
- if (show_parents) {
- struct commit_list *parents = commit->parents;
- while (parents) {
- printf(" %s",
sha1_to_hex(parents->item->object.sha1));
- parents = parents->next;
- }
- }
- putchar('\n');
- if (verbose_header) {
- const char *buf = commit->buffer;
- if (pretty_print) {
- static char pretty_header[16384];
- pretty_print_commit(commit->buffer,
~0, pretty_header, sizeof(pretty_header));
- buf = pretty_header;
- }
- printf("%s%c", buf, hdr_termination);
- }
- }
return 0;
}
diff --git a/t/t5000-rev-list.sh b/t/t5000-rev-list.sh
new file mode 100755
--- /dev/null
+++ b/t/t5000-rev-list.sh
@@ -0,0 +1,85 @@
+#!/bin/sh
+#
+# Copyright (c) 2005 Jon Seymour
+#
+
+test_description='Test rev-list --merge-order
+'
+. ./test-lib.sh
+
+function do_commit
+{
+ git-commit-tree "$@" </dev/null
+}
+
+function check_adjacency
+{
+ read previous
+ echo "= $previous"
+ while read next
+ do
+ if ! (git-cat-file commit $previous | grep "^parent $next" >/dev/null)
+ then
+ echo "^ $next"
+ else
+ echo "| $next"
+ fi
+ previous=$next
+ done
+}
+
+function sed_script
+{
+ for c in root a0 a1 a2 a3 a4 b1 b2 b3 b4 c1 c2 c3
+ do
+ echo -n "s/${!c}/$c/;"
+ done
+}
+
+date >path0
+git-update-cache --add path0
+tree=$(git-write-tree)
+root=$(do_commit $tree)
+export GIT_COMMITTER_NAME=foobar # to guarantee that the commit is different
+a0=$(do_commit $tree -p $root)
+a1=$(do_commit $tree -p $a0)
+export GIT_COMMITTER_NAME=foobar2 # to guarantee that the commit is different
+b1=$(do_commit $tree -p $root)
+c1=$(do_commit $tree -p $b1)
+export GIT_COMMITTER_NAME=foobar3 # to guarantee that the commit is different
+b2=$(do_commit $tree -p $b1)
+b3=$(do_commit $tree -p $b2)
+c2=$(do_commit $tree -p $c1 -p $b2)
+c3=$(do_commit $tree -p $c2)
+a2=$(do_commit $tree -p $a1)
+a3=$(do_commit $tree -p $a2)
+b4=$(do_commit $tree -p $b3 -p $a3)
+a4=$(do_commit $tree -p $a3 -p $b4 -p $c3)
+echo $a4 > .git/HEAD
+
+git-rev-list --merge-order --show-breaks HEAD | sed "$(sed_script)" >
actual-merge-order
+cat > expected-merge-order <<EOF
+= a4
+| c3
+| c2
+| c1
+^ b4
+| b3
+| b2
+| b1
+^ a3
+| a2
+| a1
+| a0
+= root
+EOF
+
+git-rev-list HEAD | check_adjacency | sed "$(sed_script)" >
actual-default-order
+normal_adjacency_count=$(git-rev-list HEAD | check_adjacency | grep
-c "\^" | tr -d ' ')
+merge_order_adjacency_count=$(git-rev-list --merge-order HEAD |
check_adjacency | grep -c "\^" | tr -d ' ')
+
+test_expect_success 'Testing that the rev-list has correct number of
entries' '[ $(git-rev-list HEAD | wc -l) -eq 13 ]'
+test_expect_success 'Testing that --merge-order produces the correct
result' 'diff expected-merge-order actual-merge-order'
+test_expect_success 'Testing that --merge-order produces as many or
fewer discontinuities' '[ $merge_order_adjacency_count -le
$normal_adjacency_count ]'
+
+test_done
--
homepage: http://www.zeta.org.au/~jon/
blog: http://orwelliantremors.blogspot.com/
^ permalink raw reply
* [PATCH] Modify git-rev-list to linearise the commit history in merge order. [ pox on the house of gmail ]
From: Jon Seymour @ 2005-06-02 15:31 UTC (permalink / raw)
To: Git Mailing List
In-Reply-To: <2cfc403205060208161bb06662@mail.gmail.com>
Pox on the house of gmail!
A non-wrapped version of the patch can be downloaded from:
http://blackcubes.dyndns.org/epoch/epoch.patch
More info about the patch can be read here:
http://blackcubes.dyndns.org/epoch/
Discussion to the list please.
jon.
---------- Forwarded message ----------
From: Jon Seymour <jon.seymour@gmail.com>
Date: Jun 3, 2005 1:16 AM
Subject: [PATCH] Modify git-rev-list to linearise the commit history
in merge order.
To: Git Mailing List <git@vger.kernel.org>
Cc: Linus Torvalds <torvalds@osdl.org>, Paul Mackerras <paulus@samba.org>
[PATCH] Modify git-rev-list to linearise the commit history in merge order.
This patch linearises the GIT commit history graph into merge order
which is defined by invariants specified in Documentation/git-rev-list.txt.
The linearisation produced by this patch is superior in an objective sense
to that produced by the existing git-rev-list implementation in that
the linearisation produced is guaranteed to have the minimum number of
discontinuities, where a discontinuity is defined as an adjacent pair of
commits in the output list which are not related in a direct child-parent
relationship.
A test script, t/t5000-rev-list.sh, includes a test which demonstrates
that the linearisation produced by --merge-order has less discontinuities
than the linearisation produced by git-rev-list without the --merge-order
flag specified. To see this, do the following:
cd t
./t5000-rev-list.sh
cd trash
cat actual-default-order
cat actual-merge-order
The existing behaviour of git-rev-list is preserved, by default. To obtain
the modified behaviour, specify --merge-order or --merge-order --show-breaks
on the command line.
This version of the patch has been tested on the git repository and
also on the linux-2.6
repository and has reasonable performance on both.
For more details about this change, refer to Documentation/git-rev-list.txt
and http://blackcubes.dyndns.org/epoch/.
Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
diff --git a/Makefile b/Makefile
--- a/Makefile
+++ b/Makefile
@@ -40,9 +40,9 @@ install: $(PROG) $(SCRIPTS)
$(INSTALL) $(PROG) $(SCRIPTS) $(dest)$(bin)
LIB_OBJS=read-cache.o sha1_file.o usage.o object.o commit.o tree.o blob.o \
- tag.o delta.o date.o index.o diff-delta.o patch-delta.o
+ tag.o delta.o date.o index.o diff-delta.o patch-delta.o epoch.o
LIB_FILE=libgit.a
-LIB_H=cache.h object.h blob.h tree.h commit.h tag.h delta.h
+LIB_H=cache.h object.h blob.h tree.h commit.h tag.h delta.h epoch.h
LIB_H += strbuf.h
LIB_OBJS += strbuf.o
@@ -134,6 +134,7 @@ diffcore-pathspec.o : $(LIB_H) diffcore.
diffcore-pickaxe.o : $(LIB_H) diffcore.h
diffcore-break.o : $(LIB_H) diffcore.h
diffcore-order.o : $(LIB_H) diffcore.h
+epoch.o: $(LIB_H)
test: all
$(MAKE) -C t/ all
diff --git a/commit.c b/commit.c
--- a/commit.c
+++ b/commit.c
@@ -129,7 +129,7 @@ void free_commit_list(struct commit_list
}
}
-static void insert_by_date(struct commit_list **list, struct commit *item)
+void insert_by_date(struct commit_list **list, struct commit *item)
{
struct commit_list **pp = list;
struct commit_list *p;
@@ -254,3 +254,25 @@ unsigned long pretty_print_commit(const
buf[offset] = '\0';
return offset;
}
+
+struct commit *pop_commit(struct commit_list **stack)
+{
+ struct commit_list *top = *stack;
+ struct commit *item = top ? top->item : NULL;
+
+ if (top) {
+ *stack = top->next;
+ free(top);
+ }
+ return item;
+}
+
+int count_parents(struct commit * commit)
+{
+ int count = 0;
+ struct commit_list * parents = commit->parents;
+ for (count=0;parents; parents=parents->next,count++)
+ ;
+ return count;
+}
+
diff --git a/commit.h b/commit.h
--- a/commit.h
+++ b/commit.h
@@ -32,6 +32,8 @@ void free_commit_list(struct commit_list
void sort_by_date(struct commit_list **list);
+void insert_by_date(struct commit_list **list, struct commit *item);
+
extern unsigned long pretty_print_commit(const char *msg, unsigned
long len, char *buf, unsigned long space);
@@ -41,4 +43,7 @@ extern unsigned long pretty_print_commit
struct commit *pop_most_recent_commit(struct commit_list **list,
unsigned int mark);
+struct commit *pop_commit(struct commit_list **stack);
+
+int count_parents(struct commit * commit);
#endif /* COMMIT_H */
diff --git a/epoch.c b/epoch.c
new file mode 100644
--- /dev/null
+++ b/epoch.c
@@ -0,0 +1,454 @@
+/*
+ * Copyright (c) 2005, Jon Seymour
+ *
+ * For more information about epoch theory on which this module is based,
+ * refer to http://blackcubes.dyndns.org/epoch/. That web page defines
+ * terms such as "epoch" and "minimal, non-linear epoch" and provides
rationales
+ * for some of the algorithms used here.
+ *
+ */
+#include <stdlib.h>
+#include <openssl/bn.h> // provides arbitrary
precision integers required to accurately represent fractional mass
+#include "cache.h"
+#include "commit.h"
+#include "epoch.h"
+
+struct fraction {
+ BIGNUM numerator;
+ BIGNUM denominator;
+};
+
+#define HAS_EXACTLY_ONE_PARENT(n) ((n)->parents && !(n)->parents->next)
+
+static BN_CTX *context = NULL;
+static struct fraction *one = NULL;
+static struct fraction *zero = NULL;
+
+static BN_CTX *get_BN_CTX()
+{
+ if (!context) {
+ context = BN_CTX_new();
+ }
+ return context;
+}
+
+static struct fraction *new_zero()
+{
+ struct fraction *result = xmalloc(sizeof(*result));
+ BN_init(&result->numerator);
+ BN_init(&result->denominator);
+ BN_zero(&result->numerator);
+ BN_one(&result->denominator);
+ return result;
+}
+
+static void clear_fraction(struct fraction *fraction)
+{
+ BN_clear(&fraction->numerator);
+ BN_clear(&fraction->denominator);
+}
+
+static struct fraction *divide(struct fraction *result, struct
fraction *fraction, int divisor)
+{
+ BIGNUM bn_divisor;
+
+ BN_init(&bn_divisor);
+ BN_set_word(&bn_divisor, divisor);
+
+ BN_copy(&result->numerator, &fraction->numerator);
+ BN_mul(&result->denominator, &fraction->denominator,
&bn_divisor, get_BN_CTX());
+
+ BN_clear(&bn_divisor);
+ return result;
+}
+
+static struct fraction *init_fraction(struct fraction *fraction)
+{
+ BN_init(&fraction->numerator);
+ BN_init(&fraction->denominator);
+ BN_zero(&fraction->numerator);
+ BN_one(&fraction->denominator);
+ return fraction;
+}
+
+static struct fraction *get_one()
+{
+ if (!one) {
+ one = new_zero();
+ BN_one(&one->numerator);
+ }
+ return one;
+}
+
+static struct fraction *get_zero()
+{
+ if (!zero) {
+ zero = new_zero();
+ }
+ return zero;
+}
+
+static struct fraction *copy(struct fraction *to, struct fraction *from)
+{
+ BN_copy(&to->numerator, &from->numerator);
+ BN_copy(&to->denominator, &from->denominator);
+ return to;
+}
+
+static struct fraction *add(struct fraction *result, struct fraction
*left, struct fraction *right)
+{
+ BIGNUM a, b, gcd;
+
+ BN_init(&a);
+ BN_init(&b);
+ BN_init(&gcd);
+
+ BN_mul(&a, &left->numerator, &right->denominator, get_BN_CTX());
+ BN_mul(&b, &left->denominator, &right->numerator, get_BN_CTX());
+ BN_mul(&result->denominator, &left->denominator,
&right->denominator, get_BN_CTX());
+ BN_add(&result->numerator, &a, &b);
+
+ BN_gcd(&gcd, &result->denominator, &result->numerator, get_BN_CTX());
+ BN_div(&result->denominator, NULL, &result->denominator, &gcd,
get_BN_CTX());
+ BN_div(&result->numerator, NULL, &result->numerator, &gcd,
get_BN_CTX());
+
+ BN_clear(&a);
+ BN_clear(&b);
+ BN_clear(&gcd);
+
+ return result;
+}
+
+static int compare(struct fraction *left, struct fraction *right)
+{
+ BIGNUM a, b;
+
+ int result;
+
+ BN_init(&a);
+ BN_init(&b);
+
+ BN_mul(&a, &left->numerator, &right->denominator, get_BN_CTX());
+ BN_mul(&b, &left->denominator, &right->numerator, get_BN_CTX());
+
+ result = BN_cmp(&a, &b);
+
+ BN_clear(&a);
+ BN_clear(&b);
+
+ return result;
+}
+
+struct mass_counter {
+ struct fraction seen;
+ struct fraction pending;
+};
+
+static struct mass_counter *new_mass_counter(struct commit *commit,
struct fraction *pending)
+{
+ struct mass_counter *mass_counter = xmalloc(sizeof(*mass_counter));
+ memset(mass_counter, 0, sizeof(*mass_counter));
+
+ init_fraction(&mass_counter->seen);
+ init_fraction(&mass_counter->pending);
+
+ copy(&mass_counter->pending, pending);
+ copy(&mass_counter->seen, get_zero());
+
+ commit->object.util = mass_counter;
+
+ return mass_counter;
+}
+
+static void free_mass_counter(struct mass_counter *counter)
+{
+ clear_fraction(&counter->seen);
+ clear_fraction(&counter->pending);
+ free(counter);
+}
+
+//
+// Finds the base node of an epoch.
+//
+// This algorithm uses a conservation of mass approach.
+//
+// The head starts with a weight of 1 and distributes equal portions
+// along each edge to each of its parents. The process continues until
+// one node discovers that it has acquired a total mass of 1 from its
+// descendents. This node is the base node.
+//
+// Importantly the queue of nodes to be processed is sorted in
+// reverse date order and each node occupies at most one
+// position in the queue simultaneously. These two properties
+// do not effect the algorithm's correctness. However assuming most, but
+// not all, timestamps are sane they do prevent the algorithm becoming
+// exponential by ensuring that most nodes are only visited once.
+// This is true because mass is only propagated through the network
+// when we are pretty sure we are not going to see any more coming
+// our way. The occasional bad timestamp will mean that we are
+// wrong, occasionally, but this does not matter too much.
+//
+static int find_base(struct commit *head, struct commit **boundary)
+{
+ int ret = 0;
+
+ struct commit_list *cleaner = NULL;
+ struct commit_list *pending = NULL;
+
+ *boundary = NULL;
+
+ // we inject a mass of 1 unit here
+
+ new_mass_counter(head, get_one());
+
+ commit_list_insert(head, &pending);
+ commit_list_insert(head, &cleaner);
+
+ while (!*boundary && pending && !ret) {
+
+ struct commit *latest = pop_commit(&pending);
+ struct mass_counter *latest_node = (struct
mass_counter *) latest->object.util;
+
+ if ((ret = parse_commit(latest)))
+ continue;
+
+ add(&latest_node->seen, &latest_node->seen,
&latest_node->pending);
+
+ int num_parents = count_parents(latest);
+
+ if (num_parents) {
+
+ struct fraction distribution;
+
+ divide(init_fraction(&distribution),
&latest_node->pending, num_parents);
+
+ struct commit_list *parents;
+
+ for (parents = latest->parents; parents;
parents = parents->next) {
+ struct commit *parent = parents->item;
+ struct mass_counter *parent_node =
(struct mass_counter *) parent->object.util;
+ if (!parent_node) {
+ parent_node =
new_mass_counter(parent, &distribution);
+ commit_list_insert(parent, &cleaner);
+ insert_by_date(&pending, parent);
+ } else {
+ if
(!compare(&parent_node->pending, get_zero())) {
+
copy(&parent_node->pending, &distribution);
+
insert_by_date(&pending, parent);
+ } else {
+
add(&parent_node->pending, &parent_node->pending, &distribution);
+ }
+ }
+ }
+ }
+
+ if (!compare(&latest_node->seen, get_one()) && (latest
!= head)) {
+ // if this node has seen one unit of mass, it
must be the base, so mark
+ // the boundary which will cause the loop to stop.
+ *boundary = latest;
+ }
+
+ copy(&latest_node->pending, get_zero());
+
+ }
+
+ for (; cleaner;) {
+ struct commit *next = pop_commit(&cleaner);
+ free_mass_counter((struct mass_counter *) next->object.util);
+ next->object.util = NULL;
+ }
+
+ if (pending)
+ free_commit_list(pending);
+
+ return ret;
+
+}
+
+//
+// This procedure traverses to the boundary of the first epoch in the epoch
+// sequence of the epoch headed at head_of_epoch. This is either the end of
+// the maximal linear epoch or the base of a minimal non-linear epoch.
+//
+// The queue of pending nodes is sorted in reverse date order and each node
+// is currently in the queue at most once.
+//
+static int find_next_epoch_boundary(struct commit *head_of_epoch,
struct commit **boundary)
+{
+ int ret;
+ struct commit *item = head_of_epoch;
+
+ ret = parse_commit(item);
+ if (ret)
+ return ret;
+
+ if (HAS_EXACTLY_ONE_PARENT(item)) {
+
+ // we are at the start of a maximimal linear epoch ..
traverse to the end
+
+ // traverse to the end of a maximal linear epoch
+ while (HAS_EXACTLY_ONE_PARENT(item) && !ret) {
+ item = item->parents->item;
+ ret = parse_commit(item);
+ }
+ *boundary = item;
+
+ } else {
+
+ // otherwise, we are at the start of a minimal, non-linear
+ // epoch - find the common base of all parents.
+
+ ret = find_base(item, boundary);
+
+ }
+
+ return ret;
+}
+
+//
+// Returns non-zero if parent is known to be a parent of child.
+//
+static int is_parent_of(struct commit *parent, struct commit *child)
+{
+ struct commit_list *parents;
+ for (parents = child->parents; parents; parents = parents->next) {
+ if (!memcmp(parent->object.sha1,
parents->item->object.sha1, sizeof(parents->item->object.sha1)))
+ return 1;
+ }
+ return 0;
+}
+
+static void push_onto_merge_order_stack(struct commit_list **stack,
struct commit *item)
+{
+ struct commit_list *top = *stack;
+ if (top && (top->item->object.flags & MERGE_ORDER_BREAK_FLAG)) {
+ if (is_parent_of(top->item, item)) {
+ top->item->object.flags &= ~MERGE_ORDER_BREAK_FLAG;
+ }
+ }
+ commit_list_insert(item, stack);
+}
+
+//
+// Sorts the nodes of the first epoch of the epoch sequence of the
epoch headed at head
+// into merge order.
+//
+static void sort_first_epoch(struct commit *head, struct commit_list **stack)
+{
+ parse_commit(head);
+
+ head->object.flags |= MERGE_ORDER_VISIT_FLAG;
+
+ struct commit_list *parents;
+
+ struct commit_list *reversed_parents = NULL;
+
+ //
+ // parse_commit builds the parent list in reverse order with
respect to the order of
+ // the git-commit-tree arguments.
+ //
+ // so we need to reverse this list to output the oldest (or
most "local") commits last.
+ //
+
+ for (parents = head->parents; parents; parents = parents->next) {
+ commit_list_insert(parents->item, &reversed_parents);
+ }
+
+ //
+ // todo: by sorting the parents in a different order, we can alter the
+ // merge order to show contemporaneous changes in parallel branches
+ // occurring after "local" changes. This is useful for a developer
+ // when a developer wants to see all changes that were incorporated
+ // into the same merge as her own changes occur after her own
+ // changes.
+ //
+
+ for (; reversed_parents;) {
+ struct commit *parent = pop_commit(&reversed_parents);
+ parse_commit(parent);
+ if (!(parent->object.flags & MERGE_ORDER_VISIT_FLAG)) {
+ if (parent->object.flags & MERGE_ORDER_EPOCH_FLAG) {
+ if (*stack) {
+ die("something else is on the
stack - %s\n", sha1_to_hex((*stack)->item->object.sha1));
+ }
+ push_onto_merge_order_stack(stack, parent);
+ parent->object.flags |= MERGE_ORDER_VISIT_FLAG;
+ } else {
+ sort_first_epoch(parent, stack);
+ if (reversed_parents) {
+ //
+ // this indicates a possible
discontinuity
+ // it may not be be actual
discontinuity if
+ // the head of parent N
happens to be the tail
+ // of parent N+1
+ //
+ // the next push onto the
stack will resolve the question
+ //
+ (*stack)->item->object.flags
|= MERGE_ORDER_BREAK_FLAG;
+ }
+ }
+ }
+ }
+
+ push_onto_merge_order_stack(stack, head);
+}
+
+//
+// Sorts an arbitrary epoch into merge order by sorting each epoch
+// of its epoch sequence into order.
+//
+// Note: this algorithm currently leaves traces of its execution in the
+// object flags of nodes it discovers. This should probably be fixed.
+//
+int sort_in_merge_order(struct commit *head_of_epoch, emitter_func emitter)
+{
+ struct commit *next;
+ int ret = 0;
+ int stop = 0;
+
+ parse_commit(head_of_epoch);
+
+ for (next = head_of_epoch; next && next->parents && !ret && !stop;) {
+
+ struct commit *base = NULL;
+
+ ret = find_next_epoch_boundary(next, &base);
+ if (ret)
+ return ret;
+
+ next->object.flags |= MERGE_ORDER_EPOCH_FLAG;
+ if (base) {
+ base->object.flags |= MERGE_ORDER_EPOCH_FLAG;
+ }
+
+ if (HAS_EXACTLY_ONE_PARENT(next)) {
+
+ while (HAS_EXACTLY_ONE_PARENT(next) && !stop && !ret) {
+ stop = (*emitter) (next);
+ next = next->parents->item;
+ ret = parse_commit(next);
+ }
+
+ } else {
+
+ struct commit_list *stack = NULL;
+ sort_first_epoch(next, &stack);
+ for (; stack && !stop;) {
+ next = pop_commit(&stack);
+ if (stack) {
+ stop = (*emitter) (next);
+ }
+ }
+ if (stack) {
+ free_commit_list(stack);
+ }
+ }
+
+ }
+
+ if (next && !stop) {
+ stop = (*emitter) (next);
+ }
+
+ return ret;
+}
diff --git a/epoch.h b/epoch.h
new file mode 100644
--- /dev/null
+++ b/epoch.h
@@ -0,0 +1,12 @@
+#ifndef EPOCH_H
+#define EPOCH_H
+
+typedef int (*emitter_func) (struct commit *);
+
+int sort_in_merge_order(struct commit *head_of_epoch, emitter_func emitter);
+
+#define MERGE_ORDER_EPOCH_FLAG (1u<<3)
+#define MERGE_ORDER_VISIT_FLAG (1u<<4)
+#define MERGE_ORDER_BREAK_FLAG (1u<<5)
+
+#endif /* EPOCH_H */
diff --git a/object.h b/object.h
--- a/object.h
+++ b/object.h
@@ -15,6 +15,7 @@ struct object {
const char *type;
struct object_list *refs;
struct object_list *attached_deltas;
+ void *util;
};
extern int nr_objs;
diff --git a/rev-list.c b/rev-list.c
--- a/rev-list.c
+++ b/rev-list.c
@@ -1,5 +1,6 @@
#include "cache.h"
#include "commit.h"
+#include "epoch.h"
#define SEEN (1u << 0)
#define INTERESTING (1u << 1)
@@ -11,7 +12,8 @@ static const char rev_list_usage[] =
" --max-age=epoch\n"
" --min-age=epoch\n"
" --header\n"
- " --pretty";
+ " --pretty\n"
+ " --merge-order [ --show-breaks ]";
static void mark_parents_uninteresting(struct commit *commit)
{
@@ -36,18 +38,63 @@ static int everybody_uninteresting(struc
return 1;
}
+static unsigned long max_age = -1;
+static unsigned long min_age = -1;
+static int max_count = -1;
+static int verbose_header = 0, show_parents = 0, pretty_print = 0,
merge_order = 0, show_breaks = 0;
+static const char *prefix = "";
+static int hdr_termination = 0;
+
+static int process_commit(struct commit * commit)
+{
+ if (commit->object.flags & UNINTERESTING)
+ return 0;
+ if (min_age != -1 && (commit->date > min_age))
+ return 0;
+ if (max_age != -1 && (commit->date < max_age))
+ return 1;
+ if (max_count != -1 && !max_count--)
+ return 1;
+
+ if (!show_breaks) {
+ printf("%s%s", prefix, sha1_to_hex(commit->object.sha1));
+ if (show_parents) {
+ struct commit_list *parents = commit->parents;
+ while (parents) {
+ printf(" %s",
sha1_to_hex(parents->item->object.sha1));
+ parents = parents->next;
+ }
+ }
+ putchar('\n');
+ if (verbose_header) {
+ const char *buf = commit->buffer;
+ if (pretty_print) {
+ static char pretty_header[16384];
+ pretty_print_commit(commit->buffer,
~0, pretty_header, sizeof(pretty_header));
+ buf = pretty_header;
+ }
+ printf("%s%c", buf, hdr_termination);
+ }
+ } else {
+ char c='|';
+ if (commit->object.flags & MERGE_ORDER_BREAK_FLAG) {
+ c = '^';
+ } else if (commit->object.flags & MERGE_ORDER_EPOCH_FLAG) {
+ c = '=';
+ }
+ printf("%c %s\n", c, sha1_to_hex(commit->object.sha1));
+ }
+
+ return 0;
+}
+
int main(int argc, char **argv)
{
int nr_sha;
unsigned char sha1[2][20];
struct commit_list *list = NULL;
struct commit *commit, *end;
- int i, verbose_header = 0, show_parents = 0, pretty_print = 0;
- int hdr_termination = 0;
- const char *prefix = "";
- unsigned long max_age = -1;
- unsigned long min_age = -1;
- int max_count = -1;
+ int i;
nr_sha = 0;
for (i = 1 ; i < argc; i++) {
@@ -80,8 +127,16 @@ int main(int argc, char **argv)
show_parents = 1;
continue;
}
+ if (!strncmp(arg, "--merge-order", 13)) {
+ merge_order = 1;
+ continue;
+ }
+ if (!strncmp(arg, "--show-breaks", 13)) {
+ show_breaks = 1;
+ continue;
+ }
- if (nr_sha > 2 || get_sha1(arg, sha1[nr_sha]))
+ if (nr_sha > 2 || get_sha1(arg, sha1[nr_sha])||
(show_breaks && !merge_order))
usage(rev_list_usage);
nr_sha++;
}
@@ -118,36 +173,19 @@ int main(int argc, char **argv)
} while (list);
list = newlist;
}
+
+ if (!merge_order) {
+ while (list) {
+ struct commit *commit =
pop_most_recent_commit(&list, SEEN);
+ if (process_commit(commit)) {
+ break;
+ }
+ }
+ } else {
+ if (sort_in_merge_order(commit, &process_commit)) {
+ die("merge order sort failed\n");
+ }
+ }
- while (list) {
- struct commit *commit = pop_most_recent_commit(&list, SEEN);
-
- if (commit->object.flags & UNINTERESTING)
- continue;
- if (min_age != -1 && (commit->date > min_age))
- continue;
- if (max_age != -1 && (commit->date < max_age))
- break;
- if (max_count != -1 && !max_count--)
- break;
- printf("%s%s", prefix, sha1_to_hex(commit->object.sha1));
- if (show_parents) {
- struct commit_list *parents = commit->parents;
- while (parents) {
- printf(" %s",
sha1_to_hex(parents->item->object.sha1));
- parents = parents->next;
- }
- }
- putchar('\n');
- if (verbose_header) {
- const char *buf = commit->buffer;
- if (pretty_print) {
- static char pretty_header[16384];
- pretty_print_commit(commit->buffer,
~0, pretty_header, sizeof(pretty_header));
- buf = pretty_header;
- }
- printf("%s%c", buf, hdr_termination);
- }
- }
return 0;
}
diff --git a/t/t5000-rev-list.sh b/t/t5000-rev-list.sh
new file mode 100755
--- /dev/null
+++ b/t/t5000-rev-list.sh
@@ -0,0 +1,85 @@
+#!/bin/sh
+#
+# Copyright (c) 2005 Jon Seymour
+#
+
+test_description='Test rev-list --merge-order
+'
+. ./test-lib.sh
+
+function do_commit
+{
+ git-commit-tree "$@" </dev/null
+}
+
+function check_adjacency
+{
+ read previous
+ echo "= $previous"
+ while read next
+ do
+ if ! (git-cat-file commit $previous | grep "^parent $next" >/dev/null)
+ then
+ echo "^ $next"
+ else
+ echo "| $next"
+ fi
+ previous=$next
+ done
+}
+
+function sed_script
+{
+ for c in root a0 a1 a2 a3 a4 b1 b2 b3 b4 c1 c2 c3
+ do
+ echo -n "s/${!c}/$c/;"
+ done
+}
+
+date >path0
+git-update-cache --add path0
+tree=$(git-write-tree)
+root=$(do_commit $tree)
+export GIT_COMMITTER_NAME=foobar # to guarantee that the commit is different
+a0=$(do_commit $tree -p $root)
+a1=$(do_commit $tree -p $a0)
+export GIT_COMMITTER_NAME=foobar2 # to guarantee that the commit is different
+b1=$(do_commit $tree -p $root)
+c1=$(do_commit $tree -p $b1)
+export GIT_COMMITTER_NAME=foobar3 # to guarantee that the commit is different
+b2=$(do_commit $tree -p $b1)
+b3=$(do_commit $tree -p $b2)
+c2=$(do_commit $tree -p $c1 -p $b2)
+c3=$(do_commit $tree -p $c2)
+a2=$(do_commit $tree -p $a1)
+a3=$(do_commit $tree -p $a2)
+b4=$(do_commit $tree -p $b3 -p $a3)
+a4=$(do_commit $tree -p $a3 -p $b4 -p $c3)
+echo $a4 > .git/HEAD
+
+git-rev-list --merge-order --show-breaks HEAD | sed "$(sed_script)" >
actual-merge-order
+cat > expected-merge-order <<EOF
+= a4
+| c3
+| c2
+| c1
+^ b4
+| b3
+| b2
+| b1
+^ a3
+| a2
+| a1
+| a0
+= root
+EOF
+
+git-rev-list HEAD | check_adjacency | sed "$(sed_script)" >
actual-default-order
+normal_adjacency_count=$(git-rev-list HEAD | check_adjacency | grep
-c "\^" | tr -d ' ')
+merge_order_adjacency_count=$(git-rev-list --merge-order HEAD |
check_adjacency | grep -c "\^" | tr -d ' ')
+
+test_expect_success 'Testing that the rev-list has correct number of
entries' '[ $(git-rev-list HEAD | wc -l) -eq 13 ]'
+test_expect_success 'Testing that --merge-order produces the correct
result' 'diff expected-merge-order actual-merge-order'
+test_expect_success 'Testing that --merge-order produces as many or
fewer discontinuities' '[ $merge_order_adjacency_count -le
$normal_adjacency_count ]'
+
+test_done
--
homepage: http://www.zeta.org.au/~jon/
blog: http://orwelliantremors.blogspot.com/
--
homepage: http://www.zeta.org.au/~jon/
blog: http://orwelliantremors.blogspot.com/
^ permalink raw reply
* [PATCH] Modify git-rev-list ... [ resend to fix whitespace mangle ]
From: jon @ 2005-06-02 15:49 UTC (permalink / raw)
To: git
[PATCH] Modify git-rev-list to linearise the commit history in merge order.
This patch linearises the GIT commit history graph into merge order
which is defined by invariants specified in Documentation/git-rev-list.txt.
The linearisation produced by this patch is superior in an objective sense
to that produced by the existing git-rev-list implementation in that
the linearisation produced is guaranteed to have the minimum number of
discontinuities, where a discontinuity is defined as an adjacent pair of
commits in the output list which are not related in a direct child-parent
relationship.
A test script, t/t5000-rev-list.sh, includes a test which demonstrates
that the linearisation produced by --merge-order has less discontinuities
than the linearisation produced by git-rev-list without the --merge-order
flag specified. To see this, do the following:
cd t
./t5000-rev-list.sh
cd trash
cat actual-default-order
cat actual-merge-order
The existing behaviour of git-rev-list is preserved, by default. To obtain
the modified behaviour, specify --merge-order or --merge-order --show-breaks
on the command line.
This version of the patch has been tested on the git repository and also on the linux-2.6
repository and has reasonable performance on both.
For more details about this change, refer to Documentation/git-rev-list.txt
and http://blackcubes.dyndns.org/epoch/.
Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
diff --git a/Makefile b/Makefile
--- a/Makefile
+++ b/Makefile
@@ -40,9 +40,9 @@ install: $(PROG) $(SCRIPTS)
$(INSTALL) $(PROG) $(SCRIPTS) $(dest)$(bin)
LIB_OBJS=read-cache.o sha1_file.o usage.o object.o commit.o tree.o blob.o \
- tag.o delta.o date.o index.o diff-delta.o patch-delta.o
+ tag.o delta.o date.o index.o diff-delta.o patch-delta.o epoch.o
LIB_FILE=libgit.a
-LIB_H=cache.h object.h blob.h tree.h commit.h tag.h delta.h
+LIB_H=cache.h object.h blob.h tree.h commit.h tag.h delta.h epoch.h
LIB_H += strbuf.h
LIB_OBJS += strbuf.o
@@ -134,6 +134,7 @@ diffcore-pathspec.o : $(LIB_H) diffcore.
diffcore-pickaxe.o : $(LIB_H) diffcore.h
diffcore-break.o : $(LIB_H) diffcore.h
diffcore-order.o : $(LIB_H) diffcore.h
+epoch.o: $(LIB_H)
test: all
$(MAKE) -C t/ all
diff --git a/commit.c b/commit.c
--- a/commit.c
+++ b/commit.c
@@ -129,7 +129,7 @@ void free_commit_list(struct commit_list
}
}
-static void insert_by_date(struct commit_list **list, struct commit *item)
+void insert_by_date(struct commit_list **list, struct commit *item)
{
struct commit_list **pp = list;
struct commit_list *p;
@@ -254,3 +254,25 @@ unsigned long pretty_print_commit(const
buf[offset] = '\0';
return offset;
}
+
+struct commit *pop_commit(struct commit_list **stack)
+{
+ struct commit_list *top = *stack;
+ struct commit *item = top ? top->item : NULL;
+
+ if (top) {
+ *stack = top->next;
+ free(top);
+ }
+ return item;
+}
+
+int count_parents(struct commit * commit)
+{
+ int count = 0;
+ struct commit_list * parents = commit->parents;
+ for (count=0;parents; parents=parents->next,count++)
+ ;
+ return count;
+}
+
diff --git a/commit.h b/commit.h
--- a/commit.h
+++ b/commit.h
@@ -32,6 +32,8 @@ void free_commit_list(struct commit_list
void sort_by_date(struct commit_list **list);
+void insert_by_date(struct commit_list **list, struct commit *item);
+
extern unsigned long pretty_print_commit(const char *msg, unsigned long len, char *buf, unsigned long space);
@@ -41,4 +43,7 @@ extern unsigned long pretty_print_commit
struct commit *pop_most_recent_commit(struct commit_list **list,
unsigned int mark);
+struct commit *pop_commit(struct commit_list **stack);
+
+int count_parents(struct commit * commit);
#endif /* COMMIT_H */
diff --git a/epoch.c b/epoch.c
new file mode 100644
--- /dev/null
+++ b/epoch.c
@@ -0,0 +1,454 @@
+/*
+ * Copyright (c) 2005, Jon Seymour
+ *
+ * For more information about epoch theory on which this module is based,
+ * refer to http://blackcubes.dyndns.org/epoch/. That web page defines
+ * terms such as "epoch" and "minimal, non-linear epoch" and provides rationales
+ * for some of the algorithms used here.
+ *
+ */
+#include <stdlib.h>
+#include <openssl/bn.h> // provides arbitrary precision integers required to accurately represent fractional mass
+#include "cache.h"
+#include "commit.h"
+#include "epoch.h"
+
+struct fraction {
+ BIGNUM numerator;
+ BIGNUM denominator;
+};
+
+#define HAS_EXACTLY_ONE_PARENT(n) ((n)->parents && !(n)->parents->next)
+
+static BN_CTX *context = NULL;
+static struct fraction *one = NULL;
+static struct fraction *zero = NULL;
+
+static BN_CTX *get_BN_CTX()
+{
+ if (!context) {
+ context = BN_CTX_new();
+ }
+ return context;
+}
+
+static struct fraction *new_zero()
+{
+ struct fraction *result = xmalloc(sizeof(*result));
+ BN_init(&result->numerator);
+ BN_init(&result->denominator);
+ BN_zero(&result->numerator);
+ BN_one(&result->denominator);
+ return result;
+}
+
+static void clear_fraction(struct fraction *fraction)
+{
+ BN_clear(&fraction->numerator);
+ BN_clear(&fraction->denominator);
+}
+
+static struct fraction *divide(struct fraction *result, struct fraction *fraction, int divisor)
+{
+ BIGNUM bn_divisor;
+
+ BN_init(&bn_divisor);
+ BN_set_word(&bn_divisor, divisor);
+
+ BN_copy(&result->numerator, &fraction->numerator);
+ BN_mul(&result->denominator, &fraction->denominator, &bn_divisor, get_BN_CTX());
+
+ BN_clear(&bn_divisor);
+ return result;
+}
+
+static struct fraction *init_fraction(struct fraction *fraction)
+{
+ BN_init(&fraction->numerator);
+ BN_init(&fraction->denominator);
+ BN_zero(&fraction->numerator);
+ BN_one(&fraction->denominator);
+ return fraction;
+}
+
+static struct fraction *get_one()
+{
+ if (!one) {
+ one = new_zero();
+ BN_one(&one->numerator);
+ }
+ return one;
+}
+
+static struct fraction *get_zero()
+{
+ if (!zero) {
+ zero = new_zero();
+ }
+ return zero;
+}
+
+static struct fraction *copy(struct fraction *to, struct fraction *from)
+{
+ BN_copy(&to->numerator, &from->numerator);
+ BN_copy(&to->denominator, &from->denominator);
+ return to;
+}
+
+static struct fraction *add(struct fraction *result, struct fraction *left, struct fraction *right)
+{
+ BIGNUM a, b, gcd;
+
+ BN_init(&a);
+ BN_init(&b);
+ BN_init(&gcd);
+
+ BN_mul(&a, &left->numerator, &right->denominator, get_BN_CTX());
+ BN_mul(&b, &left->denominator, &right->numerator, get_BN_CTX());
+ BN_mul(&result->denominator, &left->denominator, &right->denominator, get_BN_CTX());
+ BN_add(&result->numerator, &a, &b);
+
+ BN_gcd(&gcd, &result->denominator, &result->numerator, get_BN_CTX());
+ BN_div(&result->denominator, NULL, &result->denominator, &gcd, get_BN_CTX());
+ BN_div(&result->numerator, NULL, &result->numerator, &gcd, get_BN_CTX());
+
+ BN_clear(&a);
+ BN_clear(&b);
+ BN_clear(&gcd);
+
+ return result;
+}
+
+static int compare(struct fraction *left, struct fraction *right)
+{
+ BIGNUM a, b;
+
+ int result;
+
+ BN_init(&a);
+ BN_init(&b);
+
+ BN_mul(&a, &left->numerator, &right->denominator, get_BN_CTX());
+ BN_mul(&b, &left->denominator, &right->numerator, get_BN_CTX());
+
+ result = BN_cmp(&a, &b);
+
+ BN_clear(&a);
+ BN_clear(&b);
+
+ return result;
+}
+
+struct mass_counter {
+ struct fraction seen;
+ struct fraction pending;
+};
+
+static struct mass_counter *new_mass_counter(struct commit *commit, struct fraction *pending)
+{
+ struct mass_counter *mass_counter = xmalloc(sizeof(*mass_counter));
+ memset(mass_counter, 0, sizeof(*mass_counter));
+
+ init_fraction(&mass_counter->seen);
+ init_fraction(&mass_counter->pending);
+
+ copy(&mass_counter->pending, pending);
+ copy(&mass_counter->seen, get_zero());
+
+ commit->object.util = mass_counter;
+
+ return mass_counter;
+}
+
+static void free_mass_counter(struct mass_counter *counter)
+{
+ clear_fraction(&counter->seen);
+ clear_fraction(&counter->pending);
+ free(counter);
+}
+
+//
+// Finds the base node of an epoch.
+//
+// This algorithm uses a conservation of mass approach.
+//
+// The head starts with a weight of 1 and distributes equal portions
+// along each edge to each of its parents. The process continues until
+// one node discovers that it has acquired a total mass of 1 from its
+// descendents. This node is the base node.
+//
+// Importantly the queue of nodes to be processed is sorted in
+// reverse date order and each node occupies at most one
+// position in the queue simultaneously. These two properties
+// do not effect the algorithm's correctness. However assuming most, but
+// not all, timestamps are sane they do prevent the algorithm becoming
+// exponential by ensuring that most nodes are only visited once.
+// This is true because mass is only propagated through the network
+// when we are pretty sure we are not going to see any more coming
+// our way. The occasional bad timestamp will mean that we are
+// wrong, occasionally, but this does not matter too much.
+//
+static int find_base(struct commit *head, struct commit **boundary)
+{
+ int ret = 0;
+
+ struct commit_list *cleaner = NULL;
+ struct commit_list *pending = NULL;
+
+ *boundary = NULL;
+
+ // we inject a mass of 1 unit here
+
+ new_mass_counter(head, get_one());
+
+ commit_list_insert(head, &pending);
+ commit_list_insert(head, &cleaner);
+
+ while (!*boundary && pending && !ret) {
+
+ struct commit *latest = pop_commit(&pending);
+ struct mass_counter *latest_node = (struct mass_counter *) latest->object.util;
+
+ if ((ret = parse_commit(latest)))
+ continue;
+
+ add(&latest_node->seen, &latest_node->seen, &latest_node->pending);
+
+ int num_parents = count_parents(latest);
+
+ if (num_parents) {
+
+ struct fraction distribution;
+
+ divide(init_fraction(&distribution), &latest_node->pending, num_parents);
+
+ struct commit_list *parents;
+
+ for (parents = latest->parents; parents; parents = parents->next) {
+ struct commit *parent = parents->item;
+ struct mass_counter *parent_node = (struct mass_counter *) parent->object.util;
+ if (!parent_node) {
+ parent_node = new_mass_counter(parent, &distribution);
+ commit_list_insert(parent, &cleaner);
+ insert_by_date(&pending, parent);
+ } else {
+ if (!compare(&parent_node->pending, get_zero())) {
+ copy(&parent_node->pending, &distribution);
+ insert_by_date(&pending, parent);
+ } else {
+ add(&parent_node->pending, &parent_node->pending, &distribution);
+ }
+ }
+ }
+ }
+
+ if (!compare(&latest_node->seen, get_one()) && (latest != head)) {
+ // if this node has seen one unit of mass, it must be the base, so mark
+ // the boundary which will cause the loop to stop.
+ *boundary = latest;
+ }
+
+ copy(&latest_node->pending, get_zero());
+
+ }
+
+ for (; cleaner;) {
+ struct commit *next = pop_commit(&cleaner);
+ free_mass_counter((struct mass_counter *) next->object.util);
+ next->object.util = NULL;
+ }
+
+ if (pending)
+ free_commit_list(pending);
+
+ return ret;
+
+}
+
+//
+// This procedure traverses to the boundary of the first epoch in the epoch
+// sequence of the epoch headed at head_of_epoch. This is either the end of
+// the maximal linear epoch or the base of a minimal non-linear epoch.
+//
+// The queue of pending nodes is sorted in reverse date order and each node
+// is currently in the queue at most once.
+//
+static int find_next_epoch_boundary(struct commit *head_of_epoch, struct commit **boundary)
+{
+ int ret;
+ struct commit *item = head_of_epoch;
+
+ ret = parse_commit(item);
+ if (ret)
+ return ret;
+
+ if (HAS_EXACTLY_ONE_PARENT(item)) {
+
+ // we are at the start of a maximimal linear epoch .. traverse to the end
+
+ // traverse to the end of a maximal linear epoch
+ while (HAS_EXACTLY_ONE_PARENT(item) && !ret) {
+ item = item->parents->item;
+ ret = parse_commit(item);
+ }
+ *boundary = item;
+
+ } else {
+
+ // otherwise, we are at the start of a minimal, non-linear
+ // epoch - find the common base of all parents.
+
+ ret = find_base(item, boundary);
+
+ }
+
+ return ret;
+}
+
+//
+// Returns non-zero if parent is known to be a parent of child.
+//
+static int is_parent_of(struct commit *parent, struct commit *child)
+{
+ struct commit_list *parents;
+ for (parents = child->parents; parents; parents = parents->next) {
+ if (!memcmp(parent->object.sha1, parents->item->object.sha1, sizeof(parents->item->object.sha1)))
+ return 1;
+ }
+ return 0;
+}
+
+static void push_onto_merge_order_stack(struct commit_list **stack, struct commit *item)
+{
+ struct commit_list *top = *stack;
+ if (top && (top->item->object.flags & MERGE_ORDER_BREAK_FLAG)) {
+ if (is_parent_of(top->item, item)) {
+ top->item->object.flags &= ~MERGE_ORDER_BREAK_FLAG;
+ }
+ }
+ commit_list_insert(item, stack);
+}
+
+//
+// Sorts the nodes of the first epoch of the epoch sequence of the epoch headed at head
+// into merge order.
+//
+static void sort_first_epoch(struct commit *head, struct commit_list **stack)
+{
+ parse_commit(head);
+
+ head->object.flags |= MERGE_ORDER_VISIT_FLAG;
+
+ struct commit_list *parents;
+
+ struct commit_list *reversed_parents = NULL;
+
+ //
+ // parse_commit builds the parent list in reverse order with respect to the order of
+ // the git-commit-tree arguments.
+ //
+ // so we need to reverse this list to output the oldest (or most "local") commits last.
+ //
+
+ for (parents = head->parents; parents; parents = parents->next) {
+ commit_list_insert(parents->item, &reversed_parents);
+ }
+
+ //
+ // todo: by sorting the parents in a different order, we can alter the
+ // merge order to show contemporaneous changes in parallel branches
+ // occurring after "local" changes. This is useful for a developer
+ // when a developer wants to see all changes that were incorporated
+ // into the same merge as her own changes occur after her own
+ // changes.
+ //
+
+ for (; reversed_parents;) {
+ struct commit *parent = pop_commit(&reversed_parents);
+ parse_commit(parent);
+ if (!(parent->object.flags & MERGE_ORDER_VISIT_FLAG)) {
+ if (parent->object.flags & MERGE_ORDER_EPOCH_FLAG) {
+ if (*stack) {
+ die("something else is on the stack - %s\n", sha1_to_hex((*stack)->item->object.sha1));
+ }
+ push_onto_merge_order_stack(stack, parent);
+ parent->object.flags |= MERGE_ORDER_VISIT_FLAG;
+ } else {
+ sort_first_epoch(parent, stack);
+ if (reversed_parents) {
+ //
+ // this indicates a possible discontinuity
+ // it may not be be actual discontinuity if
+ // the head of parent N happens to be the tail
+ // of parent N+1
+ //
+ // the next push onto the stack will resolve the question
+ //
+ (*stack)->item->object.flags |= MERGE_ORDER_BREAK_FLAG;
+ }
+ }
+ }
+ }
+
+ push_onto_merge_order_stack(stack, head);
+}
+
+//
+// Sorts an arbitrary epoch into merge order by sorting each epoch
+// of its epoch sequence into order.
+//
+// Note: this algorithm currently leaves traces of its execution in the
+// object flags of nodes it discovers. This should probably be fixed.
+//
+int sort_in_merge_order(struct commit *head_of_epoch, emitter_func emitter)
+{
+ struct commit *next;
+ int ret = 0;
+ int stop = 0;
+
+ parse_commit(head_of_epoch);
+
+ for (next = head_of_epoch; next && next->parents && !ret && !stop;) {
+
+ struct commit *base = NULL;
+
+ ret = find_next_epoch_boundary(next, &base);
+ if (ret)
+ return ret;
+
+ next->object.flags |= MERGE_ORDER_EPOCH_FLAG;
+ if (base) {
+ base->object.flags |= MERGE_ORDER_EPOCH_FLAG;
+ }
+
+ if (HAS_EXACTLY_ONE_PARENT(next)) {
+
+ while (HAS_EXACTLY_ONE_PARENT(next) && !stop && !ret) {
+ stop = (*emitter) (next);
+ next = next->parents->item;
+ ret = parse_commit(next);
+ }
+
+ } else {
+
+ struct commit_list *stack = NULL;
+ sort_first_epoch(next, &stack);
+ for (; stack && !stop;) {
+ next = pop_commit(&stack);
+ if (stack) {
+ stop = (*emitter) (next);
+ }
+ }
+ if (stack) {
+ free_commit_list(stack);
+ }
+ }
+
+ }
+
+ if (next && !stop) {
+ stop = (*emitter) (next);
+ }
+
+ return ret;
+}
diff --git a/epoch.h b/epoch.h
new file mode 100644
--- /dev/null
+++ b/epoch.h
@@ -0,0 +1,12 @@
+#ifndef EPOCH_H
+#define EPOCH_H
+
+typedef int (*emitter_func) (struct commit *);
+
+int sort_in_merge_order(struct commit *head_of_epoch, emitter_func emitter);
+
+#define MERGE_ORDER_EPOCH_FLAG (1u<<3)
+#define MERGE_ORDER_VISIT_FLAG (1u<<4)
+#define MERGE_ORDER_BREAK_FLAG (1u<<5)
+
+#endif /* EPOCH_H */
diff --git a/object.h b/object.h
--- a/object.h
+++ b/object.h
@@ -15,6 +15,7 @@ struct object {
const char *type;
struct object_list *refs;
struct object_list *attached_deltas;
+ void *util;
};
extern int nr_objs;
diff --git a/rev-list.c b/rev-list.c
--- a/rev-list.c
+++ b/rev-list.c
@@ -1,5 +1,6 @@
#include "cache.h"
#include "commit.h"
+#include "epoch.h"
#define SEEN (1u << 0)
#define INTERESTING (1u << 1)
@@ -11,7 +12,8 @@ static const char rev_list_usage[] =
" --max-age=epoch\n"
" --min-age=epoch\n"
" --header\n"
- " --pretty";
+ " --pretty\n"
+ " --merge-order [ --show-breaks ]";
static void mark_parents_uninteresting(struct commit *commit)
{
@@ -36,18 +38,63 @@ static int everybody_uninteresting(struc
return 1;
}
+static unsigned long max_age = -1;
+static unsigned long min_age = -1;
+static int max_count = -1;
+static int verbose_header = 0, show_parents = 0, pretty_print = 0, merge_order = 0, show_breaks = 0;
+static const char *prefix = "";
+static int hdr_termination = 0;
+
+static int process_commit(struct commit * commit)
+{
+ if (commit->object.flags & UNINTERESTING)
+ return 0;
+ if (min_age != -1 && (commit->date > min_age))
+ return 0;
+ if (max_age != -1 && (commit->date < max_age))
+ return 1;
+ if (max_count != -1 && !max_count--)
+ return 1;
+
+ if (!show_breaks) {
+ printf("%s%s", prefix, sha1_to_hex(commit->object.sha1));
+ if (show_parents) {
+ struct commit_list *parents = commit->parents;
+ while (parents) {
+ printf(" %s", sha1_to_hex(parents->item->object.sha1));
+ parents = parents->next;
+ }
+ }
+ putchar('\n');
+ if (verbose_header) {
+ const char *buf = commit->buffer;
+ if (pretty_print) {
+ static char pretty_header[16384];
+ pretty_print_commit(commit->buffer, ~0, pretty_header, sizeof(pretty_header));
+ buf = pretty_header;
+ }
+ printf("%s%c", buf, hdr_termination);
+ }
+ } else {
+ char c='|';
+ if (commit->object.flags & MERGE_ORDER_BREAK_FLAG) {
+ c = '^';
+ } else if (commit->object.flags & MERGE_ORDER_EPOCH_FLAG) {
+ c = '=';
+ }
+ printf("%c %s\n", c, sha1_to_hex(commit->object.sha1));
+ }
+
+ return 0;
+}
+
int main(int argc, char **argv)
{
int nr_sha;
unsigned char sha1[2][20];
struct commit_list *list = NULL;
struct commit *commit, *end;
- int i, verbose_header = 0, show_parents = 0, pretty_print = 0;
- int hdr_termination = 0;
- const char *prefix = "";
- unsigned long max_age = -1;
- unsigned long min_age = -1;
- int max_count = -1;
+ int i;
nr_sha = 0;
for (i = 1 ; i < argc; i++) {
@@ -80,8 +127,16 @@ int main(int argc, char **argv)
show_parents = 1;
continue;
}
+ if (!strncmp(arg, "--merge-order", 13)) {
+ merge_order = 1;
+ continue;
+ }
+ if (!strncmp(arg, "--show-breaks", 13)) {
+ show_breaks = 1;
+ continue;
+ }
- if (nr_sha > 2 || get_sha1(arg, sha1[nr_sha]))
+ if (nr_sha > 2 || get_sha1(arg, sha1[nr_sha])|| (show_breaks && !merge_order))
usage(rev_list_usage);
nr_sha++;
}
@@ -118,36 +173,19 @@ int main(int argc, char **argv)
} while (list);
list = newlist;
}
+
+ if (!merge_order) {
+ while (list) {
+ struct commit *commit = pop_most_recent_commit(&list, SEEN);
+ if (process_commit(commit)) {
+ break;
+ }
+ }
+ } else {
+ if (sort_in_merge_order(commit, &process_commit)) {
+ die("merge order sort failed\n");
+ }
+ }
- while (list) {
- struct commit *commit = pop_most_recent_commit(&list, SEEN);
-
- if (commit->object.flags & UNINTERESTING)
- continue;
- if (min_age != -1 && (commit->date > min_age))
- continue;
- if (max_age != -1 && (commit->date < max_age))
- break;
- if (max_count != -1 && !max_count--)
- break;
- printf("%s%s", prefix, sha1_to_hex(commit->object.sha1));
- if (show_parents) {
- struct commit_list *parents = commit->parents;
- while (parents) {
- printf(" %s", sha1_to_hex(parents->item->object.sha1));
- parents = parents->next;
- }
- }
- putchar('\n');
- if (verbose_header) {
- const char *buf = commit->buffer;
- if (pretty_print) {
- static char pretty_header[16384];
- pretty_print_commit(commit->buffer, ~0, pretty_header, sizeof(pretty_header));
- buf = pretty_header;
- }
- printf("%s%c", buf, hdr_termination);
- }
- }
return 0;
}
diff --git a/t/t5000-rev-list.sh b/t/t5000-rev-list.sh
new file mode 100755
--- /dev/null
+++ b/t/t5000-rev-list.sh
@@ -0,0 +1,85 @@
+#!/bin/sh
+#
+# Copyright (c) 2005 Jon Seymour
+#
+
+test_description='Test rev-list --merge-order
+'
+. ./test-lib.sh
+
+function do_commit
+{
+ git-commit-tree "$@" </dev/null
+}
+
+function check_adjacency
+{
+ read previous
+ echo "= $previous"
+ while read next
+ do
+ if ! (git-cat-file commit $previous | grep "^parent $next" >/dev/null)
+ then
+ echo "^ $next"
+ else
+ echo "| $next"
+ fi
+ previous=$next
+ done
+}
+
+function sed_script
+{
+ for c in root a0 a1 a2 a3 a4 b1 b2 b3 b4 c1 c2 c3
+ do
+ echo -n "s/${!c}/$c/;"
+ done
+}
+
+date >path0
+git-update-cache --add path0
+tree=$(git-write-tree)
+root=$(do_commit $tree)
+export GIT_COMMITTER_NAME=foobar # to guarantee that the commit is different
+a0=$(do_commit $tree -p $root)
+a1=$(do_commit $tree -p $a0)
+export GIT_COMMITTER_NAME=foobar2 # to guarantee that the commit is different
+b1=$(do_commit $tree -p $root)
+c1=$(do_commit $tree -p $b1)
+export GIT_COMMITTER_NAME=foobar3 # to guarantee that the commit is different
+b2=$(do_commit $tree -p $b1)
+b3=$(do_commit $tree -p $b2)
+c2=$(do_commit $tree -p $c1 -p $b2)
+c3=$(do_commit $tree -p $c2)
+a2=$(do_commit $tree -p $a1)
+a3=$(do_commit $tree -p $a2)
+b4=$(do_commit $tree -p $b3 -p $a3)
+a4=$(do_commit $tree -p $a3 -p $b4 -p $c3)
+echo $a4 > .git/HEAD
+
+git-rev-list --merge-order --show-breaks HEAD | sed "$(sed_script)" > actual-merge-order
+cat > expected-merge-order <<EOF
+= a4
+| c3
+| c2
+| c1
+^ b4
+| b3
+| b2
+| b1
+^ a3
+| a2
+| a1
+| a0
+= root
+EOF
+
+git-rev-list HEAD | check_adjacency | sed "$(sed_script)" > actual-default-order
+normal_adjacency_count=$(git-rev-list HEAD | check_adjacency | grep -c "\^" | tr -d ' ')
+merge_order_adjacency_count=$(git-rev-list --merge-order HEAD | check_adjacency | grep -c "\^" | tr -d ' ')
+
+test_expect_success 'Testing that the rev-list has correct number of entries' '[ $(git-rev-list HEAD | wc -l) -eq 13 ]'
+test_expect_success 'Testing that --merge-order produces the correct result' 'diff expected-merge-order actual-merge-order'
+test_expect_success 'Testing that --merge-order produces as many or fewer discontinuities' '[ $merge_order_adjacency_count -le $normal_adjacency_count ]'
+
+test_done
^ permalink raw reply
* [PATCH] Handle deltified object correctly in git-*-pull family.
From: Junio C Hamano @ 2005-06-02 16:46 UTC (permalink / raw)
To: Linus Torvalds; +Cc: git
In-Reply-To: <7vis0xkjn4.fsf@assigned-by-dhcp.cox.net>
When a remote repository is deltified, we need to get the
objects that a deltified object we want to obtain is based upon.
The initial parts of each retrieved SHA1 file is inflated and
inspected to see if it is deltified, and its base object is
asked from the remote side when it is. Since this partial
inflation and inspection has a small performance hit, it can
optionally be skipped by giving -d flag to git-*-pull commands.
This flag should be used only when the remote repository is
known to have no deltified objects.
Rsync transport does not have this problem since it fetches
everything the remote side has.
Signed-off-by: Junio C Hamano <junkio@cox.net>
---
*** Linus, this uses the new helper you wrote. The interface is
*** much more pleasant to use.
Documentation/git-http-pull.txt | 6 +++++-
Documentation/git-local-pull.txt | 6 +++++-
Documentation/git-rpull.txt | 6 +++++-
cache.h | 3 +++
pull.h | 3 +++
http-pull.c | 4 +++-
local-pull.c | 4 +++-
pull.c | 6 ++++++
rpull.c | 4 +++-
sha1_file.c | 40 ++++++++++++++++++++++++++++++++++++++
10 files changed, 76 insertions(+), 6 deletions(-)
diff --git a/Documentation/git-http-pull.txt b/Documentation/git-http-pull.txt
--- a/Documentation/git-http-pull.txt
+++ b/Documentation/git-http-pull.txt
@@ -9,7 +9,7 @@ git-http-pull - Downloads a remote GIT r
SYNOPSIS
--------
-'git-http-pull' [-c] [-t] [-a] [-v] commit-id url
+'git-http-pull' [-c] [-t] [-a] [-v] [-d] commit-id url
DESCRIPTION
-----------
@@ -21,6 +21,10 @@ Downloads a remote GIT repository via HT
Get trees associated with the commit objects.
-a::
Get all the objects.
+-d::
+ Do not check for delta base objects (use this option
+ only when you know the remote repository is not
+ deltified).
-v::
Report what is downloaded.
diff --git a/Documentation/git-local-pull.txt b/Documentation/git-local-pull.txt
--- a/Documentation/git-local-pull.txt
+++ b/Documentation/git-local-pull.txt
@@ -9,7 +9,7 @@ git-local-pull - Duplicates another GIT
SYNOPSIS
--------
-'git-local-pull' [-c] [-t] [-a] [-l] [-s] [-n] [-v] commit-id path
+'git-local-pull' [-c] [-t] [-a] [-l] [-s] [-n] [-v] [-d] commit-id path
DESCRIPTION
-----------
@@ -23,6 +23,10 @@ OPTIONS
Get trees associated with the commit objects.
-a::
Get all the objects.
+-d::
+ Do not check for delta base objects (use this option
+ only when you know the remote repository is not
+ deltified).
-v::
Report what is downloaded.
diff --git a/Documentation/git-rpull.txt b/Documentation/git-rpull.txt
--- a/Documentation/git-rpull.txt
+++ b/Documentation/git-rpull.txt
@@ -10,7 +10,7 @@ git-rpull - Pulls from a remote reposito
SYNOPSIS
--------
-'git-rpull' [-c] [-t] [-a] [-v] commit-id url
+'git-rpull' [-c] [-t] [-a] [-d] [-v] commit-id url
DESCRIPTION
-----------
@@ -25,6 +25,10 @@ OPTIONS
Get trees associated with the commit objects.
-a::
Get all the objects.
+-d::
+ Do not check for delta base objects (use this option
+ only when you know the remote repository is not
+ deltified).
-v::
Report what is downloaded.
diff --git a/cache.h b/cache.h
--- a/cache.h
+++ b/cache.h
@@ -158,6 +158,9 @@ extern int write_sha1_file(void *buf, un
extern int check_sha1_signature(unsigned char *sha1, void *buf, unsigned long size, const char *type);
+extern int sha1_delta_base(const unsigned char *, unsigned char *);
+
+
/* Read a tree into the cache */
extern int read_tree(void *buffer, unsigned long size, int stage);
diff --git a/pull.h b/pull.h
--- a/pull.h
+++ b/pull.h
@@ -13,6 +13,9 @@ extern int get_history;
/** Set to fetch the trees in the commit history. **/
extern int get_all;
+/* Set to zero to skip the check for delta object base. */
+extern int get_delta;
+
/* Set to be verbose */
extern int get_verbosely;
diff --git a/http-pull.c b/http-pull.c
--- a/http-pull.c
+++ b/http-pull.c
@@ -103,6 +103,8 @@ int main(int argc, char **argv)
get_tree = 1;
} else if (argv[arg][1] == 'c') {
get_history = 1;
+ } else if (argv[arg][1] == 'd') {
+ get_delta = 0;
} else if (argv[arg][1] == 'a') {
get_all = 1;
get_tree = 1;
@@ -113,7 +115,7 @@ int main(int argc, char **argv)
arg++;
}
if (argc < arg + 2) {
- usage("git-http-pull [-c] [-t] [-a] [-v] commit-id url");
+ usage("git-http-pull [-c] [-t] [-a] [-d] [-v] commit-id url");
return 1;
}
commit_id = argv[arg];
diff --git a/local-pull.c b/local-pull.c
--- a/local-pull.c
+++ b/local-pull.c
@@ -74,7 +74,7 @@ int fetch(unsigned char *sha1)
}
static const char *local_pull_usage =
-"git-local-pull [-c] [-t] [-a] [-l] [-s] [-n] [-v] commit-id path";
+"git-local-pull [-c] [-t] [-a] [-l] [-s] [-n] [-v] [-d] commit-id path";
/*
* By default we only use file copy.
@@ -92,6 +92,8 @@ int main(int argc, char **argv)
get_tree = 1;
else if (argv[arg][1] == 'c')
get_history = 1;
+ else if (argv[arg][1] == 'd')
+ get_delta = 0;
else if (argv[arg][1] == 'a') {
get_all = 1;
get_tree = 1;
diff --git a/pull.c b/pull.c
--- a/pull.c
+++ b/pull.c
@@ -6,6 +6,7 @@
int get_tree = 0;
int get_history = 0;
+int get_delta = 1;
int get_all = 0;
int get_verbosely = 0;
static unsigned char current_commit_sha1[20];
@@ -37,6 +38,11 @@ static int make_sure_we_have_it(const ch
status = fetch(sha1);
if (status && what)
report_missing(what, sha1);
+ if (get_delta) {
+ char delta_sha1[20];
+ if (sha1_delta_base(sha1, delta_sha1))
+ status = make_sure_we_have_it(what, delta_sha1);
+ }
return status;
}
diff --git a/rpull.c b/rpull.c
--- a/rpull.c
+++ b/rpull.c
@@ -27,6 +27,8 @@ int main(int argc, char **argv)
get_tree = 1;
} else if (argv[arg][1] == 'c') {
get_history = 1;
+ } else if (argv[arg][1] == 'd') {
+ get_delta = 0;
} else if (argv[arg][1] == 'a') {
get_all = 1;
get_tree = 1;
@@ -37,7 +39,7 @@ int main(int argc, char **argv)
arg++;
}
if (argc < arg + 2) {
- usage("git-rpull [-c] [-t] [-a] [-v] commit-id url");
+ usage("git-rpull [-c] [-t] [-a] [-v] [-d] commit-id url");
return 1;
}
commit_id = argv[arg];
diff --git a/sha1_file.c b/sha1_file.c
--- a/sha1_file.c
+++ b/sha1_file.c
@@ -347,6 +347,46 @@ void * unpack_sha1_file(void *map, unsig
return buf;
}
+int sha1_delta_base(const unsigned char *sha1, unsigned char *delta_sha1)
+{
+ unsigned long mapsize, size;
+ void *map;
+ char type[20];
+ char buffer[200];
+ z_stream stream;
+ int ret, bytes, status;
+
+ map = map_sha1_file(sha1, &mapsize);
+ if (!map)
+ return 0;
+ ret = unpack_sha1_header(&stream, map, mapsize, buffer,
+ sizeof(buffer));
+ status = 0;
+
+ if (ret < Z_OK ||
+ sscanf(buffer, "%10s %lu", type, &size) != 2 ||
+ strcmp(type, "delta"))
+ goto out;
+ bytes = strlen(buffer) + 1;
+ if (size - bytes < 20)
+ goto out;
+
+ memmove(buffer, buffer + bytes, stream.total_out - bytes);
+ bytes = stream.total_out - bytes;
+ if (bytes < 20 && ret == Z_OK) {
+ stream.next_out = buffer + bytes;
+ stream.avail_out = sizeof(buffer) - bytes;
+ while (inflate(&stream, Z_FINISH) == Z_OK)
+ ; /* nothing */
+ }
+ status = 1;
+ memcpy(delta_sha1, buffer, 20);
+ out:
+ inflateEnd(&stream);
+ munmap(map, mapsize);
+ return status;
+}
+
void * read_sha1_file(const unsigned char *sha1, char *type, unsigned long *size)
{
unsigned long mapsize;
------------
^ permalink raw reply
* [PATCH] Use correct U*MAX.
From: Junio C Hamano @ 2005-06-02 16:47 UTC (permalink / raw)
To: Linus Torvalds; +Cc: git
In-Reply-To: <7vis0xkjn4.fsf@assigned-by-dhcp.cox.net>
The largest "unsigned long" value is ULONG_MAX, not UINT_MAX.
Signed-off-by: Junio C Hamano <junkio@cox.net>
---
*** Linus, you may be unable to spell, but I cannot type ;-).
count-delta.c | 4 ++--
diff.c | 4 ++--
diffcore-break.c | 2 +-
diffcore-rename.c | 2 +-
4 files changed, 6 insertions(+), 6 deletions(-)
diff --git a/count-delta.c b/count-delta.c
--- a/count-delta.c
+++ b/count-delta.c
@@ -46,7 +46,7 @@ unsigned long count_delta(void *delta_bu
/* the smallest delta size possible is 6 bytes */
if (delta_size < 6)
- return UINT_MAX;
+ return ULONG_MAX;
data = delta_buf;
top = delta_buf + delta_size;
@@ -83,7 +83,7 @@ unsigned long count_delta(void *delta_bu
/* sanity check */
if (data != top || out != dst_size)
- return UINT_MAX;
+ return ULONG_MAX;
/* delete size is what was _not_ copied from source.
* edit size is that and literal additions.
diff --git a/diff.c b/diff.c
--- a/diff.c
+++ b/diff.c
@@ -256,7 +256,7 @@ static struct sha1_size_cache *locate_si
first = next+1;
}
/* not found */
- if (size == UINT_MAX)
+ if (size == ULONG_MAX)
return NULL;
/* insert to make it at "first" */
if (sha1_size_cache_alloc <= sha1_size_cache_nr) {
@@ -338,7 +338,7 @@ int diff_populate_filespec(struct diff_f
struct sha1_size_cache *e;
if (size_only) {
- e = locate_size_cache(s->sha1, UINT_MAX);
+ e = locate_size_cache(s->sha1, ULONG_MAX);
if (e) {
s->size = e->size;
return 0;
diff --git a/diffcore-break.c b/diffcore-break.c
--- a/diffcore-break.c
+++ b/diffcore-break.c
@@ -63,7 +63,7 @@ static int very_different(struct diff_fi
/* Estimate the edit size by interpreting delta. */
delta_size = count_delta(delta, delta_size);
free(delta);
- if (delta_size == UINT_MAX)
+ if (delta_size == ULONG_MAX)
return 0; /* error in delta computation */
if (base_size < delta_size)
diff --git a/diffcore-rename.c b/diffcore-rename.c
--- a/diffcore-rename.c
+++ b/diffcore-rename.c
@@ -176,7 +176,7 @@ static int estimate_similarity(struct di
/* Estimate the edit size by interpreting delta. */
delta_size = count_delta(delta, delta_size);
free(delta);
- if (delta_size == UINT_MAX)
+ if (delta_size == ULONG_MAX)
return 0;
/*
------------
^ permalink raw reply
* [PATCH] Find size of SHA1 object without inflating everything.
From: Junio C Hamano @ 2005-06-02 16:49 UTC (permalink / raw)
To: Linus Torvalds; +Cc: git
In-Reply-To: <7vis0xkjn4.fsf@assigned-by-dhcp.cox.net>
This adds sha1_file_size() helper function and uses it in the
rename/copy similarity estimator. The helper function handles
deltified object as well.
Signed-off-by: Junio C Hamano <junkio@cox.net>
---
*** Linus, this also uses the new helper you wrote.
cache.h | 2 +-
diff.c | 11 +++++---
sha1_file.c | 78 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 85 insertions(+), 6 deletions(-)
diff --git a/cache.h b/cache.h
--- a/cache.h
+++ b/cache.h
@@ -159,7 +159,7 @@ extern int write_sha1_file(void *buf, un
extern int check_sha1_signature(unsigned char *sha1, void *buf, unsigned long size, const char *type);
extern int sha1_delta_base(const unsigned char *, unsigned char *);
-
+extern int sha1_file_size(const unsigned char *, unsigned long *);
/* Read a tree into the cache */
extern int read_tree(void *buffer, unsigned long size, int stage);
diff --git a/diff.c b/diff.c
--- a/diff.c
+++ b/diff.c
@@ -333,7 +333,6 @@ int diff_populate_filespec(struct diff_f
close(fd);
}
else {
- /* We cannot do size only for SHA1 blobs */
char type[20];
struct sha1_size_cache *e;
@@ -343,11 +342,13 @@ int diff_populate_filespec(struct diff_f
s->size = e->size;
return 0;
}
+ if (!sha1_file_size(s->sha1, &s->size))
+ locate_size_cache(s->sha1, s->size);
+ }
+ else {
+ s->data = read_sha1_file(s->sha1, type, &s->size);
+ s->should_free = 1;
}
- s->data = read_sha1_file(s->sha1, type, &s->size);
- s->should_free = 1;
- if (s->data && size_only)
- locate_size_cache(s->sha1, s->size);
}
return 0;
}
diff --git a/sha1_file.c b/sha1_file.c
--- a/sha1_file.c
+++ b/sha1_file.c
@@ -387,6 +387,84 @@ int sha1_delta_base(const unsigned char
return status;
}
+int sha1_file_size(const unsigned char *sha1, unsigned long *sizep)
+{
+ unsigned long mapsize, size;
+ void *map;
+ char type[20];
+ char buffer[200];
+ z_stream stream;
+ int ret, bytes, status;
+
+ map = map_sha1_file(sha1, &mapsize);
+ if (!map)
+ return 0;
+ ret = unpack_sha1_header(&stream, map, mapsize, buffer,
+ sizeof(buffer));
+ status = -1;
+
+ if (ret < Z_OK || sscanf(buffer, "%10s %lu", type, &size) != 2)
+ goto out;
+ if (strcmp(type, "delta")) {
+ *sizep = size;
+ status = 0;
+ goto out;
+ }
+
+ /* We are dealing with delta object. Inflated, the first 20
+ * bytes hold the base object SHA1, and delta data follows
+ * immediately after it.
+ */
+ bytes = strlen(buffer) + 1;
+ if (size < bytes + 6 + 20)
+ goto out; /* the smallest delta size is 6 bytes */
+
+ memmove(buffer, buffer + bytes, stream.total_out - bytes);
+ bytes = stream.total_out - bytes;
+ if (bytes < sizeof(buffer) && ret == Z_OK) {
+ stream.next_out = buffer + bytes;
+ stream.avail_out = sizeof(buffer) - bytes;
+ while (inflate(&stream, Z_FINISH) == Z_OK)
+ ; /* nothing */
+ }
+
+ /* We have read initial part of the delta, which starts at
+ * buffer+20. Borrow code from patch-delta to read the
+ * result size.
+ */
+ {
+ const unsigned char *data = buffer + 20;
+ unsigned char cmd;
+ int i;
+
+ /* Skip over the source size; we are not interested in
+ * it and we cannot verify it because we do not want
+ * to read the base object.
+ */
+ cmd = *data++;
+ while (cmd) {
+ if (cmd & 1)
+ data++;
+ cmd >>= 1;
+ }
+ /* Read the result size */
+ size = i = 0;
+ cmd = *data++;
+ while (cmd) {
+ if (cmd & 1)
+ size |= *data++ << i;
+ i += 8;
+ cmd >>= 1;
+ }
+ *sizep = size;
+ }
+ status = 0;
+ out:
+ inflateEnd(&stream);
+ munmap(map, mapsize);
+ return status;
+}
+
void * read_sha1_file(const unsigned char *sha1, char *type, unsigned long *size)
{
unsigned long mapsize;
------------
^ permalink raw reply
* Re: [PATCH] Handle deltified object correctly in git-*-pull family.
From: Linus Torvalds @ 2005-06-02 17:03 UTC (permalink / raw)
To: Junio C Hamano; +Cc: git
In-Reply-To: <7v4qcg906f.fsf_-_@assigned-by-dhcp.cox.net>
On Thu, 2 Jun 2005, Junio C Hamano wrote:
>
> *** Linus, this uses the new helper you wrote. The interface is
> *** much more pleasant to use.
Can you update it for the fact that I split things up even more?
In particular, see commit 5180cacc202bb20b15981469487eb8d6b0509997: "Split
up unpack_sha1_file() some more".
You should be able to unpack a delta with just something like this:
int ret;
z_stream stream;
char hdr[100], type[10];
unsigned long size;
ret = unpack_sha1_header(&stream, map, mapsize, hdr, sizeof(hdr));
if (ret < Z_OK)
return NULL;
if (parse_sha1_header(hdr, type, &size) < 0)
return NULL;
if (strcmp("delta", type))
return NULL;
buffer = unpack_sha1_rest(&stream, hdr, size);
if (!buffer)
return NULL;
.. we now have the delta of size "size" in "buffer" ..
ie it now has proper helper functions for every single stage in unpacking
an object.
Linus
^ permalink raw reply
* Re: [PATCH] Handle deltified object correctly in git-*-pull family.
From: McMullan, Jason @ 2005-06-02 17:03 UTC (permalink / raw)
To: Junio C Hamano; +Cc: Linus Torvalds, GIT Mailling list
In-Reply-To: <7v4qcg906f.fsf_-_@assigned-by-dhcp.cox.net>
[-- Attachment #1: Type: text/plain, Size: 1276 bytes --]
On Thu, 2005-06-02 at 09:46 -0700, Junio C Hamano wrote:
> When a remote repository is deltified, we need to get the
> objects that a deltified object we want to obtain is based upon.
> The initial parts of each retrieved SHA1 file is inflated and
> inspected to see if it is deltified, and its base object is
> asked from the remote side when it is. Since this partial
> inflation and inspection has a small performance hit, it can
> optionally be skipped by giving -d flag to git-*-pull commands.
> This flag should be used only when the remote repository is
> known to have no deltified objects.
Eww. Don't you want to attempt to get the referenced sha1 *before*
you stick the delta blob into the repository?
Otherwise, if a transfer fails, there's no good way to recover your
database through the git-*pull interfaces, ie:
Try to pull session 1:
pull tree a
pull delta b (references blob c)
pull blob c -> fails!
Try to pull session 2:
pull tree a
delta b - Found in database!
...
Or do I not understand your code properly?
(I'm working on a similar piece of code for my git-daemon protocol,
which is why I'm worried about this issue)
--
Jason McMullan <jason.mcmullan@timesys.com>
TimeSys Corporation
[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]
^ permalink raw reply
* Re: [SCRIPT] cg-rpush & locking
From: Tony Lindgren @ 2005-06-02 17:54 UTC (permalink / raw)
To: Linus Torvalds
Cc: Matthias Urlichs, Daniel Barkalow, Thomas Glanzmann,
Nicolas Pitre, git
In-Reply-To: <Pine.LNX.4.58.0506020741480.1876@ppc970.osdl.org>
* Linus Torvalds <torvalds@osdl.org> [050602 07:50]:
>
>
> On Thu, 2 Jun 2005, Tony Lindgren wrote:
> >
> > I don't think locking for the duration of the push really is a problem.
> > It is unlikely that there would be so many people pushing that it would
> > cause inconvenience... Of course it would be nice to optimize it if
> > possible.
>
> I don't think the locking is a _huge_ issue - the only real problem I had
> with locking with BK was that readers could block a writer (ie I couldn't
> push to my public tree if there were people downloading from it), and git
> doesn't have that problem. I only push to trees that are my private ones
> anyway.
>
> The real reason I'd prefer to not do locking is that _if_ the remote tree
> is actually more than just a CVS-like "public repository", ie if somebody
> actually does _development_ in the remote tree (hey, it may be crazy, but
> git makes this usage pattern possible), then we should eventually plan on
> having all of the regular "git-commit-script" and "git-pull-script" etc
> _also_ do locking, since they also change HEAD.
Or perhaps a more likely scenario would be automated pulls from other trees
running as cronjobs on the remote server.
> And that's going to be a lot easier if we only do a cmp-xchg and fail at
> the end (this concurrent change and "remote repo" usage is really quite
> wrong, since it basically mean that you consider somebody's development
> tree to be "public", and that's not what git is all about, but whatever..)
>
> But this is not a huge issue. The most important thing is to make sure
> that the new HEAD is written last, regardless, so that at least local
> readers (including things like "fsck" that can take a _loong_ time) always
> see consistent state.
>
> > I would assume the biggest problem for most people is how they can push
> > through a firewall. From that point of view it would make sense to do
> > the push as a cgi script rather than something over ssh. And with a
> > cgi script you can of course optimize the locking and use tmp files
> > before renaming which are a bit hard to do with rsync.
>
> Me personally, I want ssh as a major option. There are tons of machines
> (every single of my own ones) that I use that don't let anything but ssh
> through.
Yeah I prefer ssh too in general. Many corporate firewalls don't allow
ssh through though.
> But having alternatives is good. But ssh should be the first and primary
> one, since it also means that there can't be any new security issues (ie
> you won't be opening up any new holes by installing git on the remote
> machine).
Yeah. Doing it as cgi also has some issues getting the file
permissions right so the repo would still work for ssh users too...
Is anybody planning to work on this? I'm pretty much out of
time and will probably be happy with the rsync script for now.
Tony
^ permalink raw reply
* Re: [PATCH] Handle deltified object correctly in git-*-pull family.
From: Junio C Hamano @ 2005-06-02 18:02 UTC (permalink / raw)
To: McMullan, Jason; +Cc: Linus Torvalds, GIT Mailling list
In-Reply-To: <1117731830.32257.52.camel@jmcmullan.timesys>
>>>>> "JM" == McMullan, Jason <jason.mcmullan@timesys.com> writes:
JM> Eww. Don't you want to attempt to get the referenced sha1 *before*
JM> you stick the delta blob into the repository?
That issue crossed my mind, and I admit I haven't looked at the
issues closely enough, but I suspect that it may not worth it
with the current pull.c structure.
The current pull code fetches and stores a commit object before
it retrieves the tree object associate with it, and similarly a
tree object before its subtree and blobs, which has the same
issue. Adding -r (recover) option to the pull family to not
check for the existence of required object but its dependents
would be necessary if my suspition turns out to be correct, and
delta dependency should be handled the same way commit and tree
dependencies are handled there.
^ permalink raw reply
* [PATCH] git-tar-tree: small doc update (resent)
From: Rene Scharfe @ 2005-06-02 18:50 UTC (permalink / raw)
To: Linus Torvalds; +Cc: git
git-tar-tree: document difference in behaviour w/ regard to tree vs. commit
and correct author information.
Signed-off-by: Rene Scharfe <rene.scharfe@lsrfire.ath.cx>
diff --git a/Documentation/git-tar-tree.txt b/Documentation/git-tar-tree.txt
--- a/Documentation/git-tar-tree.txt
+++ b/Documentation/git-tar-tree.txt
@@ -17,10 +17,17 @@ Creates a tar archive containing the tre
When <base> is specified it is added as a leading path as the files in the
generated tar archive.
+git-tar-tree behaves differently when given a tree ID versus when given
+a commit ID or tag ID. In the first case the current time is used as
+modification time of each file in the archive. In the latter case the
+commit time as recorded in the referenced commit object is used instead.
+Additionally the commit ID is stored in a global extended pax header.
+It can be extracted using git-get-tar-commit-id.
+
Author
------
-Written by Linus Torvalds <torvalds@osdl.org>
+Written by Rene Scharfe.
Documentation
--------------
^ permalink raw reply
* [PATCH] git-tar-tree: add a test case (resent)
From: Rene Scharfe @ 2005-06-02 18:50 UTC (permalink / raw)
To: Linus Torvalds; +Cc: git
git-tar-tree: add a simple test case.
Signed-off-by: Rene Scharfe <rene.scharfe@lsrfire.ath.cx>
diff --git a/t/t3200-tar-tree.sh b/t/t3200-tar-tree.sh
new file mode 100755
--- /dev/null
+++ b/t/t3200-tar-tree.sh
@@ -0,0 +1,106 @@
+#!/bin/sh
+#
+# Copyright (C) 2005 Rene Scharfe
+#
+
+test_description='git-tar-tree and git-get-tar-commit-id test
+
+This test covers the topics of long paths, file contents, commit date
+handling and commit id embedding:
+
+ Paths longer than 100 characters require the use of a pax extended
+ header to store them. The test creates files with pathes both longer
+ and shorter than 100 chars, and also checks symlinks with long and
+ short pathes both as their own name and as target path.
+
+ The contents of the repository is compared to the extracted tar
+ archive. The repository contains simple text files, symlinks and a
+ binary file (/bin/sh).
+
+ git-tar-tree applies the commit date to every file in the archive it
+ creates. The test sets the commit date to a specific value and checks
+ if the tar archive contains that value.
+
+ When giving git-tar-tree a commit id (in contrast to a tree id) it
+ embeds this commit id into the tar archive as a comment. The test
+ checks the ability of git-get-tar-commit-id to figure it out from the
+ tar file.
+
+'
+
+. ./test-lib.sh
+
+test_expect_success \
+ 'populate workdir' \
+ 'mkdir a b c &&
+ p48=1.......10........20........30........40......48 &&
+ p50=1.......10........20........30........40........50 &&
+ p98=${p48}${p50} &&
+ echo simple textfile >a/a &&
+ echo 100 chars in path >a/${p98} &&
+ echo 101 chars in path >a/${p98}x &&
+ echo 102 chars in path >a/${p98}xx &&
+ echo 103 chars in path >a/${p98}xxx &&
+ mkdir a/bin &&
+ cp /bin/sh a/bin/sh &&
+ ln -s a a/l1 &&
+ ln -s ${p98}xx a/l100 &&
+ ln -s ${p98}xxx a/l101 &&
+ ln -s ${p98}xxx a/l${p98} &&
+ (cd a && find .) | sort >a.lst'
+
+test_expect_success \
+ 'add files to repository' \
+ 'find a -type f | xargs git-update-cache --add &&
+ find a -type l | xargs git-update-cache --add &&
+ treeid=`git-write-tree` &&
+ echo $treeid >treeid &&
+ TZ= GIT_COMMITTER_DATE="2005-05-27 22:00:00" \
+ git-commit-tree $treeid </dev/null >.git/HEAD'
+
+test_expect_success \
+ 'git-tar-tree' \
+ 'git-tar-tree HEAD >b.tar'
+
+test_expect_success \
+ 'validate file modification time' \
+ 'tar tvf b.tar a/a | awk \{print\ \$4,\$5\} >b.mtime &&
+ echo "2005-05-27 22:00:00" >expected.mtime &&
+ diff expected.mtime b.mtime'
+
+test_expect_success \
+ 'git-get-tar-commit-id' \
+ 'git-get-tar-commit-id <b.tar >b.commitid &&
+ diff .git/HEAD b.commitid'
+
+test_expect_success \
+ 'extract tar archive' \
+ '(cd b && tar xf -) <b.tar'
+
+test_expect_success \
+ 'validate filenames' \
+ '(cd b/a && find .) | sort >b.lst &&
+ diff a.lst b.lst'
+
+test_expect_success \
+ 'validate file contents' \
+ 'diff -r a b/a'
+
+test_expect_success \
+ 'git-tar-tree with prefix' \
+ 'git-tar-tree HEAD prefix >c.tar'
+
+test_expect_success \
+ 'extract tar archive with prefix' \
+ '(cd c && tar xf -) <c.tar'
+
+test_expect_success \
+ 'validate filenames with prefix' \
+ '(cd c/prefix/a && find .) | sort >c.lst &&
+ diff a.lst c.lst'
+
+test_expect_success \
+ 'validate file contents with prefix' \
+ 'diff -r a c/prefix/a'
+
+test_done
^ permalink raw reply
* [PATCH] git-tar-tree: cleanup write_trailer() (resent)
From: Rene Scharfe @ 2005-06-02 18:50 UTC (permalink / raw)
To: Linus Torvalds; +Cc: git
git-tar-tree: replace open-coded variants of get_record().
Signed-off-by: Rene Scharfe <rene.scharfe@lsrfire.ath.cx>
diff --git a/tar-tree.c b/tar-tree.c
--- a/tar-tree.c
+++ b/tar-tree.c
@@ -73,16 +73,13 @@ static char *get_record(void)
*/
static void write_trailer(void)
{
- memset(block + offset, 0, RECORDSIZE);
- offset += RECORDSIZE;
+ get_record();
write_if_needed();
- memset(block + offset, 0, RECORDSIZE);
- offset += RECORDSIZE;
+ get_record();
write_if_needed();
if (offset) {
- memset(block + offset, 0, BLOCKSIZE - offset);
- reliable_write(block, BLOCKSIZE);
- offset = 0;
+ get_record();
+ write_if_needed();
}
}
^ permalink raw reply
* [PATCH] Handle deltified object correctly in git-*-pull family.
From: Junio C Hamano @ 2005-06-02 18:55 UTC (permalink / raw)
To: Linus Torvalds; +Cc: git
In-Reply-To: <Pine.LNX.4.58.0506020959250.1876@ppc970.osdl.org>
When a remote repository is deltified, we need to get the
objects that a deltified object we want to obtain is based upon.
The initial parts of each retrieved SHA1 file is inflated and
inspected to see if it is deltified, and its base object is
asked from the remote side when it is. Since this partial
inflation and inspection has a small performance hit, it can
optionally be skipped by giving -d flag to git-*-pull commands.
This flag should be used only when the remote repository is
known to have no deltified objects.
Rsync transport does not have this problem since it fetches
everything the remote side has.
Signed-off-by: Junio C Hamano <junkio@cox.net>
---
*** Now uses parse_sha1_header() and unpack_sha1_rest(). I
*** decided not to make it the callers responsibility to check
*** what we have already got and fixed unpack_sha1_rest() to
*** avoid copying more than size bytes.
Documentation/git-http-pull.txt | 6 ++++-
Documentation/git-local-pull.txt | 6 ++++-
Documentation/git-rpull.txt | 6 ++++-
cache.h | 1 +
pull.h | 3 +++
http-pull.c | 4 +++-
local-pull.c | 4 +++-
pull.c | 7 ++++++
rpull.c | 4 +++-
sha1_file.c | 43 +++++++++++++++++++++++++++++++++++++-
10 files changed, 77 insertions(+), 7 deletions(-)
diff --git a/Documentation/git-http-pull.txt b/Documentation/git-http-pull.txt
--- a/Documentation/git-http-pull.txt
+++ b/Documentation/git-http-pull.txt
@@ -9,7 +9,7 @@ git-http-pull - Downloads a remote GIT r
SYNOPSIS
--------
-'git-http-pull' [-c] [-t] [-a] [-v] commit-id url
+'git-http-pull' [-c] [-t] [-a] [-v] [-d] commit-id url
DESCRIPTION
-----------
@@ -21,6 +21,10 @@ Downloads a remote GIT repository via HT
Get trees associated with the commit objects.
-a::
Get all the objects.
+-d::
+ Do not check for delta base objects (use this option
+ only when you know the remote repository is not
+ deltified).
-v::
Report what is downloaded.
diff --git a/Documentation/git-local-pull.txt b/Documentation/git-local-pull.txt
--- a/Documentation/git-local-pull.txt
+++ b/Documentation/git-local-pull.txt
@@ -9,7 +9,7 @@ git-local-pull - Duplicates another GIT
SYNOPSIS
--------
-'git-local-pull' [-c] [-t] [-a] [-l] [-s] [-n] [-v] commit-id path
+'git-local-pull' [-c] [-t] [-a] [-l] [-s] [-n] [-v] [-d] commit-id path
DESCRIPTION
-----------
@@ -23,6 +23,10 @@ OPTIONS
Get trees associated with the commit objects.
-a::
Get all the objects.
+-d::
+ Do not check for delta base objects (use this option
+ only when you know the remote repository is not
+ deltified).
-v::
Report what is downloaded.
diff --git a/Documentation/git-rpull.txt b/Documentation/git-rpull.txt
--- a/Documentation/git-rpull.txt
+++ b/Documentation/git-rpull.txt
@@ -10,7 +10,7 @@ git-rpull - Pulls from a remote reposito
SYNOPSIS
--------
-'git-rpull' [-c] [-t] [-a] [-v] commit-id url
+'git-rpull' [-c] [-t] [-a] [-d] [-v] commit-id url
DESCRIPTION
-----------
@@ -25,6 +25,10 @@ OPTIONS
Get trees associated with the commit objects.
-a::
Get all the objects.
+-d::
+ Do not check for delta base objects (use this option
+ only when you know the remote repository is not
+ deltified).
-v::
Report what is downloaded.
diff --git a/cache.h b/cache.h
--- a/cache.h
+++ b/cache.h
@@ -153,6 +153,7 @@ extern char *sha1_file_name(const unsign
extern void * map_sha1_file(const unsigned char *sha1, unsigned long *size);
extern int unpack_sha1_header(z_stream *stream, void *map, unsigned long mapsize, void *buffer, unsigned long size);
extern int parse_sha1_header(char *hdr, char *type, unsigned long *sizep);
+extern int sha1_delta_base(const unsigned char *, unsigned char *);
extern void * unpack_sha1_file(void *map, unsigned long mapsize, char *type, unsigned long *size);
extern void * read_sha1_file(const unsigned char *sha1, char *type, unsigned long *size);
extern int write_sha1_file(void *buf, unsigned long len, const char *type, unsigned char *return_sha1);
diff --git a/pull.h b/pull.h
--- a/pull.h
+++ b/pull.h
@@ -13,6 +13,9 @@ extern int get_history;
/** Set to fetch the trees in the commit history. **/
extern int get_all;
+/* Set to zero to skip the check for delta object base. */
+extern int get_delta;
+
/* Set to be verbose */
extern int get_verbosely;
diff --git a/http-pull.c b/http-pull.c
--- a/http-pull.c
+++ b/http-pull.c
@@ -103,6 +103,8 @@ int main(int argc, char **argv)
get_tree = 1;
} else if (argv[arg][1] == 'c') {
get_history = 1;
+ } else if (argv[arg][1] == 'd') {
+ get_delta = 0;
} else if (argv[arg][1] == 'a') {
get_all = 1;
get_tree = 1;
@@ -113,7 +115,7 @@ int main(int argc, char **argv)
arg++;
}
if (argc < arg + 2) {
- usage("git-http-pull [-c] [-t] [-a] [-v] commit-id url");
+ usage("git-http-pull [-c] [-t] [-a] [-d] [-v] commit-id url");
return 1;
}
commit_id = argv[arg];
diff --git a/local-pull.c b/local-pull.c
--- a/local-pull.c
+++ b/local-pull.c
@@ -74,7 +74,7 @@ int fetch(unsigned char *sha1)
}
static const char *local_pull_usage =
-"git-local-pull [-c] [-t] [-a] [-l] [-s] [-n] [-v] commit-id path";
+"git-local-pull [-c] [-t] [-a] [-l] [-s] [-n] [-v] [-d] commit-id path";
/*
* By default we only use file copy.
@@ -92,6 +92,8 @@ int main(int argc, char **argv)
get_tree = 1;
else if (argv[arg][1] == 'c')
get_history = 1;
+ else if (argv[arg][1] == 'd')
+ get_delta = 0;
else if (argv[arg][1] == 'a') {
get_all = 1;
get_tree = 1;
diff --git a/pull.c b/pull.c
--- a/pull.c
+++ b/pull.c
@@ -6,6 +6,7 @@
int get_tree = 0;
int get_history = 0;
+int get_delta = 1;
int get_all = 0;
int get_verbosely = 0;
static unsigned char current_commit_sha1[20];
@@ -37,6 +38,12 @@ static int make_sure_we_have_it(const ch
status = fetch(sha1);
if (status && what)
report_missing(what, sha1);
+ if (get_delta) {
+ char delta_sha1[20];
+ status = sha1_delta_base(sha1, delta_sha1);
+ if (0 < status)
+ status = make_sure_we_have_it(what, delta_sha1);
+ }
return status;
}
diff --git a/rpull.c b/rpull.c
--- a/rpull.c
+++ b/rpull.c
@@ -27,6 +27,8 @@ int main(int argc, char **argv)
get_tree = 1;
} else if (argv[arg][1] == 'c') {
get_history = 1;
+ } else if (argv[arg][1] == 'd') {
+ get_delta = 0;
} else if (argv[arg][1] == 'a') {
get_all = 1;
get_tree = 1;
@@ -37,7 +39,7 @@ int main(int argc, char **argv)
arg++;
}
if (argc < arg + 2) {
- usage("git-rpull [-c] [-t] [-a] [-v] commit-id url");
+ usage("git-rpull [-c] [-t] [-a] [-v] [-d] commit-id url");
return 1;
}
commit_id = argv[arg];
diff --git a/sha1_file.c b/sha1_file.c
--- a/sha1_file.c
+++ b/sha1_file.c
@@ -325,7 +325,13 @@ void *unpack_sha1_rest(z_stream *stream,
int bytes = strlen(buffer) + 1;
char *buf = xmalloc(1+size);
- memcpy(buf, buffer + bytes, stream->total_out - bytes);
+ /* (stream->total_out - bytes) is what we already have. The
+ * caller could be asking for something smaller than that.
+ */
+ if (size < stream->total_out - bytes)
+ memcpy(buf, buffer + bytes, size);
+ else
+ memcpy(buf, buffer + bytes, stream->total_out - bytes);
bytes = stream->total_out - bytes;
if (bytes < size) {
stream->next_out = buf + bytes;
@@ -401,6 +407,41 @@ void * unpack_sha1_file(void *map, unsig
return unpack_sha1_rest(&stream, hdr, *size);
}
+int sha1_delta_base(const unsigned char *sha1, unsigned char *base_sha1)
+{
+ int ret;
+ unsigned long mapsize, size;
+ void *map;
+ z_stream stream;
+ char hdr[1024], type[20];
+ void *delta_data_head;
+
+ map = map_sha1_file(sha1, &mapsize);
+ if (!map)
+ return -1;
+ ret = unpack_sha1_header(&stream, map, mapsize, hdr, sizeof(hdr));
+ if (ret < Z_OK || parse_sha1_header(hdr, type, &size) < 0) {
+ ret = -1;
+ goto out;
+ }
+ if (strcmp(type, "delta")) {
+ ret = 0;
+ goto out;
+ }
+ delta_data_head = unpack_sha1_rest(&stream, hdr, 20);
+ if (!delta_data_head) {
+ ret = -1;
+ goto out;
+ }
+ ret = 1;
+ memcpy(base_sha1, delta_data_head, 20);
+ free(delta_data_head);
+ out:
+ inflateEnd(&stream);
+ munmap(map, mapsize);
+ return ret;
+}
+
void * read_sha1_file(const unsigned char *sha1, char *type, unsigned long *size)
{
unsigned long mapsize;
------------
^ permalink raw reply
page: next (older) | prev (newer) | latest
- recent:[subjects (threaded)|topics (new)|topics (active)]
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox