* Re: [PATCH] Fix rename/copy when dealing with temporarily broken pairs.
From: Petr Baudis @ 2005-06-13 17:58 UTC (permalink / raw)
To: Jon Seymour; +Cc: Junio C Hamano, git
In-Reply-To: <2cfc4032050613092462d3a456@mail.gmail.com>
Dear diary, on Mon, Jun 13, 2005 at 06:24:16PM CEST, I got a letter
where Jon Seymour <jon.seymour@gmail.com> told me that...
> diff --git a/epoch.c b/traversal.c
> similarity index 100%
> rename from epoch.c
> rename to traversal.c
> What tool am I meant to be using to apply the patch?
>
> I am currently using "patch -p1"
Try git-apply.
--
Petr "Pasky" Baudis
Stuff: http://pasky.or.cz/
<Espy> be careful, some twit might quote you out of context..
^ permalink raw reply
* Re: [zooko@zooko.com: [Revctrl] colliding md5 hashes of human-meaningful
From: linux @ 2005-06-13 19:50 UTC (permalink / raw)
To: git, torvalds
> So the problem is totally different from the way git uses a hash. In the
> git model, an attacker by definition cannot control both versions of a
> file, since if he controls just _one_ version, he doesn't need to do the
> attack in the first place!
You are insufficiently paranoid, Grasshopper.
The basic attack goes like this:
- I construct two .c files with identical hashes. One is something
useful; perhaps a device driver for some piece of hardware that my
desired target has. The other is similar, but includes a remote
root explot.
(With an n-bit hash and an automated way to make harmless changes
to source files, I can generate 2^(n/2) variants of each and expect to
get a match, even in the absence of a better attack.)
- I submit the first one to the Linux kernel. It's valid and gets
merged.
- A kernel release, including the "interesting" driver, gets made and
sprinkled with holy penguin pee. Signatures, hashes, and all that.
- Through various means (possibly just running a kernel download mirror,
or possibly by splicing into my target's upstream Internet connection),
I substitute the malware file for the real source code.
- My target verifies all the hashes and signatures, decides that this "Linus"
person signing it is trustworthy, and compiles and installs the kernel.
- I walk in my back door and do suitable rude things.
The point is, it *is* possible for an attacker to control both versions of
a file. The reason he needs to do the attack is that one version looks
legitimate and the other includes a Nasty Surprise.
^ permalink raw reply
* Re: [zooko@zooko.com: [Revctrl] colliding md5 hashes of human-meaningful
From: Linus Torvalds @ 2005-06-13 20:08 UTC (permalink / raw)
To: linux; +Cc: git
In-Reply-To: <20050613195038.9191.qmail@science.horizon.com>
On Mon, 13 Jun 2005 linux@horizon.com wrote:
>
> You are insufficiently paranoid, Grasshopper.
No, I just am not lettign paranoia mean that I sit around shivering all
day long.
> The basic attack goes like this:
>
> - I construct two .c files with identical hashes.
Ok, I have a better plan.
- you learn to fly by flapping your arms fast enough
- you then learn to pee burning gasoline
- then, you fly around New York, setting everybody you see on fire, until
people make you emperor.
Sounds like a good plan, no?
But perhaps slightly impractical.
Now, let's go back to your plan. Why do you think your plan is any better
than mine?
Linus
^ permalink raw reply
* Re: [zooko@zooko.com: [Revctrl] colliding md5 hashes of human-meaningful
From: Jason McMullan @ 2005-06-13 20:17 UTC (permalink / raw)
To: GIT Mailling list
In-Reply-To: <Pine.LNX.4.58.0506131305550.8487@ppc970.osdl.org>
[-- Attachment #1: Type: text/plain, Size: 458 bytes --]
On Mon, 2005-06-13 at 13:08 -0700, Linus Torvalds wrote:
> Ok, I have a better plan.
>
> - you learn to fly by flapping your arms fast enough
> - you then learn to pee burning gasoline
> - then, you fly around New York, setting everybody you see on fire,
> until
> people make you emperor.
Can't... stop... laughing....
"Cryptology - It's a comedy goldmine!"
--
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: [zooko@zooko.com: [Revctrl] colliding md5 hashes of human-meaningful
From: Junio C Hamano @ 2005-06-13 20:46 UTC (permalink / raw)
To: linux; +Cc: git
In-Reply-To: <20050613195038.9191.qmail@science.horizon.com>
>> So the problem is totally different from the way git uses a hash. In the
>> git model, an attacker by definition cannot control both versions of a
>> file, since if he controls just _one_ version, he doesn't need to do the
>> attack in the first place!
> You are insufficiently paranoid, Grasshopper.
> The basic attack goes like this:
> - I construct two .c files with identical hashes. One is something
> useful; perhaps a device driver for some piece of hardware that my
> desired target has. The other is similar, but includes a remote
> root explot.
> (With an n-bit hash and an automated way to make harmless changes
> to source files, I can generate 2^(n/2) variants of each and expect to
> get a match, even in the absence of a better attack.)
> - I submit the first one to the Linux kernel. It's valid and gets
> merged.
I doubt that this part would work in practice.
Wouldn't you have to have some "garbage" in the early part of
that driver source, probably in a C comment block or an
otherwise unused string constant, that serves no apparent
purpose, which is inserted by your "automated harmless changes"
machinery?
Wouldn't that catch people's attention and cause them to
question and reject that patch in the first place?
Wouldn't that mean you do not have control over even _one_
version, let alone _both_ versions?
^ permalink raw reply
* Re: [Revctrl] colliding md5 hashes of human-meaningful
From: Radoslaw Szkodzinski @ 2005-06-13 20:52 UTC (permalink / raw)
To: linux; +Cc: git, torvalds
In-Reply-To: <20050613195038.9191.qmail@science.horizon.com>
linux@horizon.com wrote:
>>So the problem is totally different from the way git uses a hash. In the
>>git model, an attacker by definition cannot control both versions of a
>>file, since if he controls just _one_ version, he doesn't need to do the
>>attack in the first place!
>>
>>
>
>You are insufficiently paranoid, Grasshopper.
>
>The basic attack goes like this:
>
>- I construct two .c files with identical hashes. One is something
> useful; perhaps a device driver for some piece of hardware that my
> desired target has. The other is similar, but includes a remote
> root explot.
>
> (With an n-bit hash and an automated way to make harmless changes
> to source files, I can generate 2^(n/2) variants of each and expect to
> get a match, even in the absence of a better attack.)
>
>
>
And you get lots of nonsense in the new file.
>- I submit the first one to the Linux kernel. It's valid and gets
> merged.
>
>
>
And funny as it is, when the hole is found you're busted. Or at least
the first person responsible.
You probably couldn't shadow yourself enough not to get caught.
>- A kernel release, including the "interesting" driver, gets made and
> sprinkled with holy penguin pee. Signatures, hashes, and all that.
>
>
>
Which mean that you can't change your name on the project. See above.
>- Through various means (possibly just running a kernel download mirror,
> or possibly by splicing into my target's upstream Internet connection),
> I substitute the malware file for the real source code.
>
>
>
If you can splice into the connection, you can put there anything you want,
including another kernel and any amount of exploits. Even with SSH.
Ever heard of man-in-the-middle attacks?
With high-grade security you won't be able to splice into the connection,
as it'll be fully encrypted (with HTH key exchange) and/or randomised using things like EFF's Tor.
Then they can check with kernel.org or any other mirror.
>- My target verifies all the hashes and signatures, decides that this "Linus"
> person signing it is trustworthy, and compiles and installs the kernel.
>
>
And they're so unforseeing that they don't check the sources of the
drivers they use.
Funny. And if they don't use it, you'll have a problem with enabling
your exploit.
Your best target would be a scheduler, but that's heavily scrutinised.
>- I walk in my back door and do suitable rude things.
>
>
>
Like going to jail.
>The point is, it *is* possible for an attacker to control both versions of
>a file. The reason he needs to do the attack is that one version looks
>legitimate and the other includes a Nasty Surprise.
>
>
It is in theory. Tell someone when you mount such an attack on anybody.
AstralStorm
^ permalink raw reply
* Re: [zooko@zooko.com: [Revctrl] colliding md5 hashes of human-meaningful
From: linux @ 2005-06-13 21:03 UTC (permalink / raw)
To: torvalds; +Cc: git, linux
In-Reply-To: <Pine.LNX.4.58.0506131305550.8487@ppc970.osdl.org>
> No, I just am not letting paranoia mean that I sit around shivering all
> day long.
I'm sorry if I implied that. I meant "paranoid" in the sense of
"imagining attack"; you were saying there is no way to attack git via
a collision attack on the underlying hash, and I objected.
I agree with you that:
- The attack is still wildly impractical, and
- Anything is better than the unauthenticated TCP we use these days!
>> The basic attack goes like this:
>>
>> - I construct two .c files with identical hashes.
> Ok, I have a better plan.
>
> - you learn to fly by flapping your arms fast enough
> - you then learn to pee burning gasoline
> - then, you fly around New York, setting everybody you see on fire, until
> people make you emperor.
>
> Sounds like a good plan, no?
ROFL! Oh my. That's worthy of reprinting. I was pleased with myself
for making fun of the "what if there's an accidental hash collision"
theory by assuming that kernel development would continue uninterrupted
until the sun went nova, but this is truly masterful scorn.
> But perhaps slightly impractical.
There are just few laws of physics it violates.
Not to mention that New York is still a trifle touchy about the combination
of flying and burning fossil fuels, and this poses problems for step 3.
> Now, let's go back to your plan. Why do you think your plan is any better
> than mine?
I was trying to point out that a collision attack is possible. That is,
*if* we assume that someone can has the ability to find a hash collision,
*then* they can use that to break git's authenticity guarantees.
I wasn't addressing the plausibility of the "if" part. I agree that
requiring the hashed text to be plausible C source makes all current
attacks (including the MD5 ones) irrelevant, and reduces you to straight
brute force, which is quite implausible.
But it *is* a collsion attack, not a preimage attack, and it *is* at
least consistent with all known laws of physics.
I did *not* say, or mean to imply, that there was anything wrong with
git's hashing.
^ permalink raw reply
* Re: [PATCH] Fix rename/copy when dealing with temporarily broken pairs.
From: Junio C Hamano @ 2005-06-13 21:01 UTC (permalink / raw)
To: jon; +Cc: git
In-Reply-To: <2cfc4032050613092462d3a456@mail.gmail.com>
>>>>> "JS" == Jon Seymour <jon.seymour@gmail.com> writes:
JS> I've got a patch series that renames a file, but the patches
JS> generated by your git-format-patch-script fail to rename the
JS> file to the new name.
JS> I wondered if this patch might fix it, but it doesn't seem to.
I doubt the problem you have is related to the problem this
patch addresses. This is a fix for a case that the machinery
sometimes says rename when it should say copy.
Regular "patch" cannot grok either copy or rename. If your
recipient uses "patch", then you must not use -C nor -M when you
are preparing a diff for his consumption.
JS> What tool am I meant to be using to apply the patch?
JS> I am currently using "patch -p1"
As Petr already responded, the git-apply program from the King
Penguin himself should work [*1*].
One thing I just want to make sure is this. You are not
reporting that the patch you sent that said "rename" should have
been "copy", are you?
I understand that your change creates traversal.c out of
epoch.c. Say the output is from between commitA and commitB.
What I would like to know is if commitB still contains epoch.c,
or it does not have epoch.c anymore [*2*]. If it is the former
then I think you spotted a bug in the patch your message is a
response to. I hope that is not the case.
P.S. I will be offline shortly and will not be able to offer
further help until perhaps late next week.
[Footnote]
*1* Find the thread in the mailing list archive that contains
this message, which I think would be of help too.
Date: Sun, 5 Jun 2005 16:17:56 -0700 (PDT)
From: Linus Torvalds <torvalds@osdl.org>
To: Junio C Hamano <junkio@cox.net>
cc: Daniel Barkalow <barkalow@iabervon.org>, git@vger.kernel.org
Subject: Re: [PATCH-CAREFUL/RENAME] rename git-rpush and git-rpull to git-ssh-push and git-ssh-pull
Message-ID: <Pine.LNX.4.58.0506051613370.1876@ppc970.osdl.org>
References: <7vk6l9flzr.fsf@assigned-by-dhcp.cox.net>
<Pine.LNX.4.21.0506050132590.30848-100000@iabervon.org>
<7vfyvxb89m.fsf_-_@assigned-by-dhcp.cox.net> <Pine.LNX.4.58.0506051427280.1876@ppc970.osdl.org>
<7vmzq4zata.fsf@assigned-by-dhcp.cox.net>
On Sun, 5 Jun 2005, Junio C Hamano wrote:
>
> Here is a rebase. To apply with git-apply, you need the "Yes,
> sir" patch to grok "rename from/to".
Seems to have applied correctly. Very nice.
Linus
^ permalink raw reply
* [PATCH] opml output for gitweb
From: Erik van Konijnenburg @ 2005-06-13 22:53 UTC (permalink / raw)
To: Kay Sievers; +Cc: Git Mailing List
Gitweb currently has a nice orange thingy at the footer of
every page, except for the title page.
The attached patch addresses that lacuna with an OPML link,
a file format to import and export RSS collections from
feed readers. Using this link, you can subscribe to all
RSS feeds on a git site in one go.
The patch was prepared against ftp://ehlo.org/gitweb2.cgi
and manually edited to undo localisation to my test tree.
It's only lightly tested: exporting a feed collection from
gitweb and importing it in Sage and liferea seems to work.
Regards,
Erik
Signed-off-by: Erik van Konijnenburg <ekonijn@xs4all.nl>
--- /home/konijn/gitweb2.cgi 2005-06-13 21:58:39.000000000 +0200
+++ gitweb.cgi 2005-06-14 00:31:24.000000000 +0200
@@ -50,6 +50,9 @@
if ($action eq "git-logo.png") {
git_logo();
exit;
+ } elsif ($action eq "opml") {
+ git_opml();
+ exit;
}
} else {
$action = "summary";
@@ -243,7 +246,8 @@
div.diff_info { font-family:monospace; color:#000099; background-color:#edece6; font-style:italic; }
div.index_include { border:solid #d9d8d1; border-width:0px 0px 1px; padding:12px 8px; }
div.search { margin:4px 8px; position:absolute; top:56px; right:12px }
-a.rss_logo { float:right; padding:3px 0px; width:35px; line-height:10px;
+a.rss_logo {
+ float:right; padding:3px 0px; width:35px; line-height:10px;
border:1px solid; border-color:#fcc7a5 #7d3302 #3e1a01 #ff954e;
color:#ffffff; background-color:#ff6600;
font-weight:bold; font-family:sans-serif; font-size:10px;
@@ -289,6 +293,9 @@
}
print $cgi->a({-href => "$my_uri?p=$project;a=rss", -class => "rss_logo"}, "RSS") . "\n";
}
+ else {
+ print $cgi->a({-href => "$my_uri?a=opml", -class => "rss_logo"}, "OPML") . "\n";
+ }
print "</div>\n" .
"</body>\n" .
"</html>";
@@ -1197,6 +1204,83 @@
git_footer_html();
}
+sub git_opml {
+ my @list;
+ if (-d $projects_list) {
+ # search in directory
+ my $dir = $projects_list;
+ opendir my $dh, $dir or return undef;
+ while (my $dir = readdir($dh)) {
+ if (-e "$projectroot/$dir/HEAD") {
+ my $pr = {
+ path => $dir,
+ };
+ push @list, $pr
+ }
+ }
+ closedir($dh);
+ } elsif (-f $projects_list) {
+ # read from file(url-encoded):
+ # 'git%2Fgit.git Linus+Torvalds'
+ # 'libs%2Fklibc%2Fklibc.git H.+Peter+Anvin'
+ # 'linux%2Fhotplug%2Fudev.git Greg+Kroah-Hartman'
+ open my $fd , $projects_list or return undef;
+ while (my $line = <$fd>) {
+ chomp $line;
+ my ($path, $owner) = split ' ', $line;
+ $path = unescape($path);
+ $owner = unescape($owner);
+ if (!defined $path) {
+ next;
+ }
+ if (-e "$projectroot/$path/HEAD") {
+ my $pr = {
+ path => $path,
+ owner => $owner,
+ };
+ push @list, $pr
+ }
+ }
+ close $fd;
+ }
+
+ if (!@list) {
+ die_error(undef, "No project found.");
+ }
+ @list = sort {$a->{'path'} cmp $b->{'path'}} @list;
+
+
+ print $cgi->header(-type => 'text/xml', -charset => 'utf-8');
+ print "<?xml version=\"1.0\" encoding=\"utf-8\"?>\n".
+ "<opml version=\"1.0\">\n".
+ "<head>".
+ " <title>Git OPML Export</title>\n".
+ "</head>\n".
+ "<body>\n".
+ " <outline text=\"Git RSS Feeds\">\n";
+
+ foreach my $pr (@list) {
+ my %proj = %$pr;
+ my $head = git_read_hash("$proj{'path'}/HEAD");
+ if (!defined $head) {
+ next;
+ }
+ $ENV{'GIT_OBJECT_DIRECTORY'} = "$projectroot/$proj{'path'}/objects";
+ my %co = git_read_commit($head);
+ if (!%co) {
+ next;
+ }
+
+ my $path = escapeHTML(chop_str($proj{'path'}, 25, 5));
+ my $rss = "$my_url?p=$proj{'path'};a=rss";
+ my $html = "$my_url?p=$proj{'path'};a=log";
+ print "<outline type=\"rss\" text=\"$path\" title=\"$path\" xmlUrl=\"$rss\" htmlUrl=\"$html\"/>\n";
+ }
+ print " </outline>\n".
+ "</body>\n".
+ "</opml>\n";
+}
+
sub git_rss {
# http://www.notestips.com/80256B3A007F2692/1/NAMO5P9UPQ
open my $fd, "-|", "$gitbin/git-rev-list --max-count=20 " . git_read_hash("$project/HEAD") or die_error(undef, "Open failed.");
^ permalink raw reply
* Re: [zooko@zooko.com: [Revctrl] colliding md5 hashes of human-meaningful
From: linux @ 2005-06-13 23:03 UTC (permalink / raw)
To: torvalds; +Cc: git, linux
In-Reply-To: <Pine.LNX.4.58.0506131434260.8487@ppc970.osdl.org>
Oh, for heaven's sake. This is getting to be entirely too big
an issue. For the record, I believe:
- There are far easier ways to back-door the public Linux kernel.
(See the recent "subtly malicious code" contest.)
- There are far easier ways to back-door a particular target's
kernel.
- There are easier ways than back-dooring their kernel to attack
a particular target's computer.
- A 2^80 work factor is sufficient protection for quite a few
years, especially as the processor speed growth curve finally
seems to be flattening.
All I was trying to point out is that a sqrt(n) hash collision
attack *exists*. Not that it's practical or anything.
For the quantity of computers required, it would be *cheaper* to start a
factory making my own line of PCI bus master network cards that included
remote memory sniffing features on-board!
> Yeah, yeah. You avoided a few laws of phsyics of your own.
>
> For example, when you say
>
> "(With an n-bit hash and an automated way to make harmless changes
> to source files, I can generate 2^(n/2) variants of each and expect to
> get a match, even in the absence of a better attack.)"
>
> you kind of ignore the fact that "n" here is 160, and so you're going to
> be searching for quite a few versions of each. Also, you have to compare
> the sha's of all of those 2**80 versions against each other which is a lot
> of work in itself.
I am most definitely NOT ignoring it. That's what makes the attack infeasible.
(But I insist that 2^80 is a hell of a long way from violating any laws
of physics.)
As for the comparison, if the two texts have the same form, there are
well-known ways to reduce the storage requirements by large factors
like 2^40. For texts of different form, regular Pollard's rho doesn't
work, but maybe something ingenious is possible.
All I was trying to say is that a sqrt(2^160) attack exists. Remember
the original statement?
>>> So the problem is totally different from the way git uses a hash. In the
>>> git model, an attacker by definition cannot control both versions of a
>>> file, since if he controls just _one_ version, he doesn't need to do the
>>> attack in the first place!
>>>
>>> Put another way: you could use this exact example for a version of git
>>> that uses md5-sums instead of sha1's, but it wouldn't show anything at all
>>> about a git vulnerability even so.
*That's* what I was responding to. It basically says "there is no
collision attack on the way git uses the hash", a statement I disagree
with. I didn't say it was a realistic attack, because the whole reason
that SHA is 160 bits is so that it's resistant to a hash collision attack!
> Finally, you have to make sure that al the versions make sense, and that
> people will take them 100% unmodified.
Making them all make sense isn't hard; I can come up with 80 binary
variants on a piece of code by changing order of helper functions,
order of variable declarations, order of statements, comments,
spacing, and whatnot without even having to get into trailing
or redundant whitespace.
Making sure that nobody messes with it is trickier. That would be
easier with a small patch, but that would in turn make the problem
of generating 2^80 plausible variants harder.
I'm reaching a bit, but hey, it was a quick description, not a
fully-fledged Cunning Plan.
> My plan was more interesting, I feel.
Oh for you, sure. But as the one you had nominated to carry it
out, I'd like to object!
For plausibility, I prefer mine for manufacturing network cards with
built-in back doors. There's a chance I could even get the Chinese
government to help fund it.
^ permalink raw reply
* Re: [PATCH] Fix rename/copy when dealing with temporarily broken pairs.
From: Jon Seymour @ 2005-06-13 22:17 UTC (permalink / raw)
To: Junio C Hamano; +Cc: git, Petr Baudis
In-Reply-To: <7vis0ic6ot.fsf@assigned-by-dhcp.cox.net>
On 6/14/05, Junio C Hamano <junkio@cox.net> wrote:
> JS> I wondered if this patch might fix it, but it doesn't seem to.
> Regular "patch" cannot grok either copy or rename. If your
> recipient uses "patch", then you must not use -C nor -M when you
> are preparing a diff for his consumption.
Ok, there was no problem other than me not understanding what
git-apply did - thank you Pasky for bringing light to the dark regions
of my sleep-deprived brain!
jon.
^ permalink raw reply
* Re: [zooko@zooko.com: [Revctrl] colliding md5 hashes of human-meaningful
From: Linus Torvalds @ 2005-06-13 21:39 UTC (permalink / raw)
To: linux; +Cc: git
In-Reply-To: <20050613210318.18965.qmail@science.horizon.com>
On Mon, 13 Jun 2005 linux@horizon.com wrote:
>
> > But perhaps slightly impractical.
>
> There are just few laws of physics it violates.
Yeah, yeah. You avoided a few laws of phsyics of your own.
For example, when you say
"(With an n-bit hash and an automated way to make harmless changes
to source files, I can generate 2^(n/2) variants of each and expect to
get a match, even in the absence of a better attack.)"
you kind of ignore the fact that "n" here is 160, and so you're going to
be searching for quite a few versions of each. Also, you have to compare
the sha's of all of those 2**80 versions against each other which is a lot
of work in itself.
Finally, you have to make sure that al the versions make sense, and that
people will take them 100% unmodified.
My plan was more interesting, I feel.
Linus
^ permalink raw reply
* Re: porcelain question: state of the art for undo-redo?
From: Daniel Barkalow @ 2005-06-14 1:25 UTC (permalink / raw)
To: jon; +Cc: Git Mailing List
In-Reply-To: <2cfc40320506110151624b3ec1@mail.gmail.com>
On Sat, 11 Jun 2005, Jon Seymour wrote:
> What porcelain layer solutions currently exist for effective undo-edit-redo?
>
> For example, if you are working on a series of patches in a series,
> then realise there is a mistake in a patch early in the series, how
> does one mod that patch, then reapply all the following patches to
> produce a slightly modified patch series with as little stuffing
> around as possible?
I personally commit changes as I make them (essentially, and time I'm
about to make a change that might not work out, I commit the previous
state). Once I'm completely satisfied with the results, I redo the whole
thing as a series of commits from the base as self-contained changes.
To do this, I get a repository which contains the base (as master) and the
result of my previous work. Then I repeat the following steps:
Diff the work against the head into a temporary file.
Remove all of the hunks I don't want yet from the file.
Apply the file.
Commit.
I stop when the diff is either empty or contains only junk I didn't
actually mean to include.
Then I submit the series thus created.
I generally then diff once more, remove anything I actually don't want to
have (as opposed to wanting to have but not submit), apply and commit to
form a new work head. Then I throw away the old work head.
If I screw this up, I just start over, since I have all the actual content
safe.
-Daniel
*This .sig left intentionally blank*
^ permalink raw reply
* [PATCH] Adding Correct Useage Notification and -h Help flag
From: James Purser @ 2005-06-14 1:47 UTC (permalink / raw)
To: Git Mailing List
[-- Attachment #1: Type: text/plain, Size: 355 bytes --]
okay this is my first patch so take it easy on me.
I have added both a Correct Useage notification when git is called on
its own without any other parameters and a -h help flag which lists
available scripts for the git command.
Signed-off-by: James Purser <purserj@k-sit.com>
--
James Purser
Winnet Developer
+61 2 4223 4131
http://www.winnet.com.au
[-- Attachment #2: git_patch --]
[-- Type: text/plain, Size: 1021 bytes --]
Added a couple of lines to the git wrapper. Includes Correct Useage and available scripts
---
commit bfe72d41d70f9e4c0a6ab0ec6cf49347f980f4de
tree a8eed80ea2ac00ffee0b4f12ed4c931ca7761000
parent 940c1bb0181cb20454bf3573134175f86983a0ce
author James Purser <purserj@k-sit.com> Tue, 14 Jun 2005 11:40:20 +1000
committer James Purser <purserj@k-sit.com> Tue, 14 Jun 2005 11:40:20 +1000
git | 31 ++++++++++++++++++++++++++++---
1 files changed, 28 insertions(+), 3 deletions(-)
diff --git a/git b/git
--- a/git
+++ b/git
@@ -1,4 +1,29 @@
#!/bin/sh
-cmd="git-$1-script"
-shift
-exec $cmd "$@"
+if [ "$1" = "" ]
+then
+ echo "Correct Useage: git [-h] [SCRIPT]";
+else
+ if [ "$1" = "-h" ]
+ then
+ echo "This is a basic script wrapper for certain git functions. The available commands are:
+
+git apply-patch
+git commit
+git cvsimport
+git deltafy
+git diff
+git fetch
+git log
+git merge-one-file
+git prune
+git pull
+git status
+git tag
+";
+ else
+ cmd="git-$1-script";
+ shift;
+ exec $cmd "$@";
+ fi
+fi
+
^ permalink raw reply
* Re: [zooko@zooko.com: [Revctrl] colliding md5 hashes of human-meaningful
From: Benjamin Herrenschmidt @ 2005-06-14 1:49 UTC (permalink / raw)
To: linux; +Cc: torvalds, git
In-Reply-To: <20050613230324.32002.qmail@science.horizon.com>
> Oh for you, sure. But as the one you had nominated to carry it
> out, I'd like to object!
>
> For plausibility, I prefer mine for manufacturing network cards with
> built-in back doors. There's a chance I could even get the Chinese
> government to help fund it.
Be careful with architectures that have a semi-decent iommu though :)
Ben.
^ permalink raw reply
* [PATCH 1/7] Additional --merge-order tests and general cleanup of t/t6001-rev-list-merge-order.sh
From: Jon Seymour @ 2005-06-14 2:04 UTC (permalink / raw)
To: git; +Cc: jon.seymour
Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
This series of patches is intended to apply on top of:
[PATCH 1/2] Changes to non-epoch.c code required for author-oriented
git-rev-list changes
[PATCH 2/2] Add support for author-oriented git-rev-list switches [rev 11]
This series of 7 patches ultimately splits epoch.c into two and
re-renders the --merge-order sort support into a generalized
facility for performing incremental topological sorts on git
commit graphs. This facility can be used by any tool that needs
a topological sort simply by customizing the traversal methods
in the epoch_methods structure [ which is later renamed to
traversal ].
As part of this refactorisation, this change also achieves
a better separation of concerns between the epoch.c and rev-list.c.
In particular, all knowledge of the --show-breaks and output limiting
is now in rev-list.c, close to where the tool is configured, leaving
the traversal algorithms themselves relatively pure.
Assuming these patches are accepted into the mainline, I intend to use
these new facilities to build algorithms that:
- list a unique path between two commits (useful for undo/redo logic)
- list the segments in the graph (useful for building visualisations)
---
t/t6001-rev-list-merge-order.sh | 240 +++++++++++++++++++++++++--------------
1 files changed, 156 insertions(+), 84 deletions(-)
diff --git a/t/t6001-rev-list-merge-order.sh b/t/t6001-rev-list-merge-order.sh
old mode 100644
new mode 100755
--- a/t/t6001-rev-list-merge-order.sh
+++ b/t/t6001-rev-list-merge-order.sh
@@ -3,77 +3,74 @@
# Copyright (c) 2005 Jon Seymour
#
-test_description='Test rev-list --merge-order
-'
+test_description='Tests git-rev-list --merge-order functionality'
+
. ./test-lib.sh
+
+#
+# TODO: move the following block (upto --- end ...) into testlib.sh
+#
[ -d .git/refs/tags ] || mkdir -p .git/refs/tags
sed_script="";
+# Answer the sha1 has associated with the tag. The tag must exist in .git or .git/refs/tags
function tag
{
- local _tag=$1
+ _tag=$1
[ -f .git/refs/tags/$_tag ] || error "tag: \"$_tag\" does not exist"
cat .git/refs/tags/$_tag
}
-function commit
+# Generate a commit using the text specified to make it unique and the tree
+# named by the tag specified.
+function unique_commit
{
- local _tag=$1
- local _tree=$2
+ _text=$1
+ _tree=$2
shift 2
- echo $_tag | git-commit-tree $(tag $_tree) "$@"
+ echo $_text | git-commit-tree $(tag $_tree) "$@"
}
+# Save the output of a command into the tag specified. Prepend
+# a substitution script for the tag onto the front of $sed_script
function save_tag
{
- local _tag=$1
- [ -n "$_tag" ] || error "usage: do_commit tag commit-args ..."
+ _tag=$1
+ [ -n "$_tag" ] || error "usage: save_tag tag commit-args ..."
shift 1
"$@" >.git/refs/tags/$_tag
sed_script="s/$(tag $_tag)/$_tag/g${sed_script+;}$sed_script"
}
+# Replace unhelpful sha1 hashses with their symbolic equivalents
function entag
{
sed "$sed_script"
}
+# Execute a command after first saving, then setting the GIT_AUTHOR_EMAIL
+# tag to a specified value. Restore the original value on return.
function as_author
{
- local _author=$1
+ _author=$1
shift 1
- local _save=$GIT_AUTHOR_EMAIL
+ _save=$GIT_AUTHOR_EMAIL
export GIT_AUTHOR_EMAIL="$_author"
"$@"
export GIT_AUTHOR_EMAIL="$_save"
}
+# Execute a command and suppress any error output.
function hide_error
{
"$@" 2>/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 check_output
{
- local _name=$1
+ _name=$1
shift 1
if "$@" | entag > $_name.actual
then
@@ -84,64 +81,99 @@ function check_output
}
+# Turn a reasonable test description into a reasonable test name.
+# All alphanums translated into -'s which are then compressed and stripped
+# from front and back.
function name_from_description
{
- tr "'" '.' | tr '~`!@#$%^&*()_+={}[]|\;:"<>,/?-' '.' | tr -s '.' | tr ' ' '-' | tr '[A-Z]' '[a-z]' | sed "s/^\.*//"
+ tr "'" '-' | tr '~`!@#$%^&*()_+={}[]|\;:"<>,/? ' '-' | tr -s '-' | tr '[A-Z]' '[a-z]' | sed "s/^-*//;s/-*\$//"
}
-#
-# stdin contains expected result
-#
+
+# Execute the test described by the first argument, by eval'ing
+# command line specified in the 2nd argument. Check the status code
+# is zero and that the output matches the stream read from
+# stdin.
function test_output_expect_success
{
- local _description=$1
- shift 1
- local _name=$(echo $_description | name_from_description)
+ _description=$1
+ _test=$2
+ [ $# -eq 2 ] || error "usage: test_output_expect_success description test <<EOF ... EOF"
+ _name=$(echo $_description | name_from_description)
cat > $_name.expected
- test_expect_success "$_description" "check_output $_name $*"
+ test_expect_success "$_description" "check_output $_name $_test"
+}
+
+# --- end of stuff to move ---
+
+# test-case specific test function
+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
}
+
date >path0
git-update-cache --add path0
save_tag tree git-write-tree
-hide_error save_tag root commit root tree
-save_tag l0 commit l0 tree -p root
-save_tag l1 commit l1 tree -p l0
-save_tag l2 commit l2 tree -p l1
-save_tag a0 commit a0 tree -p l2
-save_tag a1 commit a1 tree -p a0
-save_tag b1 commit b1 tree -p a0
-save_tag c1 commit c1 tree -p b1
-as_author foobar@example.com save_tag b2 commit b2 tree -p b1
-save_tag b3 commit b2 tree -p b2
-save_tag c2 commit c2 tree -p c1 -p b2
-save_tag c3 commit c3 tree -p c2
-save_tag a2 commit a2 tree -p a1
-save_tag a3 commit a3 tree -p a2
-save_tag b4 commit b4 tree -p b3 -p a3
-save_tag a4 commit a4 tree -p a3 -p b4 -p c3
-save_tag l3 commit l3 tree -p a4
-save_tag l4 commit l4 tree -p l3
-save_tag l5 commit l5 tree -p l4
-hide_error save_tag e1 as_author e@example.com commit e1 tree
-save_tag e2 as_author e@example.com commit e2 tree -p e1
-save_tag f1 as_author f@example.com commit f1 tree -p e1
-save_tag e3 as_author e@example.com commit e3 tree -p e2
-save_tag f2 as_author f@example.com commit f2 tree -p f1
-save_tag e4 as_author e@example.com commit e4 tree -p e3 -p f2
-save_tag e5 as_author e@example.com commit e5 tree -p e4
-save_tag f3 as_author f@example.com commit f3 tree -p f2
-save_tag f4 as_author f@example.com commit f4 tree -p f3
-save_tag e6 as_author e@example.com commit e6 tree -p e5 -p f4
-save_tag f5 as_author f@example.com commit f5 tree -p f4
-save_tag f6 as_author f@example.com commit f6 tree -p f5 -p e6
-save_tag e7 as_author e@example.com commit e7 tree -p e6
-save_tag e8 as_author e@example.com commit e8 tree -p e7
-save_tag e9 as_author e@example.com commit e9 tree -p e8
-save_tag f7 as_author f@example.com commit f7 tree -p f6
-save_tag f8 as_author f@example.com commit f8 tree -p f7
-save_tag f9 as_author f@example.com commit f9 tree -p f8
-save_tag e10 as_author e@example.com commit e1 tree -p e9 -p f8
+hide_error save_tag root unique_commit root tree
+save_tag l0 unique_commit l0 tree -p root
+save_tag l1 unique_commit l1 tree -p l0
+save_tag l2 unique_commit l2 tree -p l1
+save_tag a0 unique_commit a0 tree -p l2
+save_tag a1 unique_commit a1 tree -p a0
+save_tag b1 unique_commit b1 tree -p a0
+save_tag c1 unique_commit c1 tree -p b1
+as_author foobar@example.com save_tag b2 unique_commit b2 tree -p b1
+save_tag b3 unique_commit b2 tree -p b2
+save_tag c2 unique_commit c2 tree -p c1 -p b2
+save_tag c3 unique_commit c3 tree -p c2
+save_tag a2 unique_commit a2 tree -p a1
+save_tag a3 unique_commit a3 tree -p a2
+save_tag b4 unique_commit b4 tree -p b3 -p a3
+save_tag a4 unique_commit a4 tree -p a3 -p b4 -p c3
+save_tag l3 unique_commit l3 tree -p a4
+save_tag l4 unique_commit l4 tree -p l3
+save_tag l5 unique_commit l5 tree -p l4
+hide_error save_tag e1 as_author e@example.com unique_commit e1 tree
+save_tag e2 as_author e@example.com unique_commit e2 tree -p e1
+save_tag f1 as_author f@example.com unique_commit f1 tree -p e1
+save_tag e3 as_author e@example.com unique_commit e3 tree -p e2
+save_tag f2 as_author f@example.com unique_commit f2 tree -p f1
+save_tag e4 as_author e@example.com unique_commit e4 tree -p e3 -p f2
+save_tag e5 as_author e@example.com unique_commit e5 tree -p e4
+save_tag f3 as_author f@example.com unique_commit f3 tree -p f2
+save_tag f4 as_author f@example.com unique_commit f4 tree -p f3
+save_tag e6 as_author e@example.com unique_commit e6 tree -p e5 -p f4
+save_tag f5 as_author f@example.com unique_commit f5 tree -p f4
+save_tag f6 as_author f@example.com unique_commit f6 tree -p f5 -p e6
+save_tag e7 as_author e@example.com unique_commit e7 tree -p e6
+save_tag e8 as_author e@example.com unique_commit e8 tree -p e7
+save_tag e9 as_author e@example.com unique_commit e9 tree -p e8
+save_tag f7 as_author f@example.com unique_commit f7 tree -p f6
+save_tag f8 as_author f@example.com unique_commit f8 tree -p f7
+save_tag f9 as_author f@example.com unique_commit f9 tree -p f8
+save_tag e10 as_author e@example.com unique_commit e1 tree -p e9 -p f8
+
+hide_error save_tag g0 unique_commit g0 tree
+save_tag g1 unique_commit g1 tree -p g0
+save_tag h1 unique_commit g2 tree -p g0
+save_tag g2 unique_commit g3 tree -p g1 -p h1
+save_tag h2 unique_commit g4 tree -p g2
+save_tag g3 unique_commit g5 tree -p g2
+save_tag g4 unique_commit g6 tree -p g3 -p h2
+
tag l5 > .git/HEAD
#
@@ -153,15 +185,15 @@ tag l5 > .git/HEAD
#
echo $sed_script > sed.script
-test_expect_success 'Testing that the rev-list has correct number of entries' 'git-rev-list HEAD | wc -l | tr -s " "' <<EOF
+test_expect_success 'rev-list has correct number of entries' 'git-rev-list HEAD | wc -l | tr -s " "' <<EOF
19
EOF
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 --merge-order produces as many or fewer discontinuities' '[ $merge_order_adjacency_count -le $normal_adjacency_count ]'
+test_expect_success '--merge-order produces as many or fewer discontinuities' '[ $merge_order_adjacency_count -le $normal_adjacency_count ]'
-test_output_expect_success 'Simple Merge Order Test' 'git-rev-list --merge-order --show-breaks HEAD' <<EOF
+test_output_expect_success 'simple merge order' 'git-rev-list --merge-order --show-breaks HEAD' <<EOF
= l5
| l4
| l3
@@ -183,7 +215,17 @@ test_output_expect_success 'Simple Merge
= root
EOF
-test_output_expect_success 'Multiple heads' 'git-rev-list --merge-order a3 b3 c3' <<EOF
+test_output_expect_success 'two diamonds merge order (g6)' 'git-rev-list --merge-order --show-breaks g4' <<EOF
+= g4
+| h2
+^ g3
+= g2
+| h1
+^ g1
+= g0
+EOF
+
+test_output_expect_success 'multiple heads' 'git-rev-list --merge-order a3 b3 c3' <<EOF
c3
c2
c1
@@ -200,7 +242,7 @@ l0
root
EOF
-test_output_expect_success 'Prune at a1' 'git-rev-list --merge-order a3 b3 c3 ^a1' <<EOF
+test_output_expect_success 'multiple heads, prune at a1' 'git-rev-list --merge-order a3 b3 c3 ^a1' <<EOF
c3
c2
c1
@@ -211,7 +253,7 @@ a3
a2
EOF
-test_output_expect_success 'Prune at l1' 'git-rev-list --merge-order a3 b3 c3 ^l1' <<EOF
+test_output_expect_success 'multiple heads, prune at l1' 'git-rev-list --merge-order a3 b3 c3 ^l1' <<EOF
c3
c2
c1
@@ -225,7 +267,7 @@ a0
l2
EOF
-test_output_expect_success 'Head at l5, Prune at l1' 'git-rev-list --merge-order l5 ^l1' <<EOF
+test_output_expect_success 'cross-epoch, head at l5, prune at l1' 'git-rev-list --merge-order l5 ^l1' <<EOF
l5
l4
l3
@@ -244,7 +286,7 @@ a0
l2
EOF
-test_output_expect_success 'Duplicated head arguments' 'git-rev-list --merge-order l5 l5 ^l1' <<EOF
+test_output_expect_success 'duplicated head arguments' 'git-rev-list --merge-order l5 l5 ^l1' <<EOF
l5
l4
l3
@@ -263,7 +305,7 @@ a0
l2
EOF
-test_output_expect_success 'Prune near merge' 'git-rev-list --merge-order a4 ^c3' <<EOF
+test_output_expect_success 'prune near merge' 'git-rev-list --merge-order a4 ^c3' <<EOF
a4
b4
b3
@@ -294,7 +336,7 @@ test_output_expect_success '--wrt-author
= root
EOF
-test_output_expect_success "Prune at foobar@example.com" 'git-rev-list --show-breaks --wrt-author --author=foobar@example.com --prune-at-author HEAD' <<EOF
+test_output_expect_success "prune at foobar@example.com" 'git-rev-list --show-breaks --wrt-author --author=foobar@example.com --prune-at-author HEAD' <<EOF
= l5
| l4
| l3
@@ -392,6 +434,36 @@ test_output_expect_success "three nodes
= root
EOF
+test_output_expect_success "linear prune l2 ^root" 'git-rev-list --show-breaks l2 ^root' <<EOF
+= l2
+| l1
+| l0
+EOF
+
+test_output_expect_success "linear prune l2 ^l0" 'git-rev-list --show-breaks l2 ^l0' <<EOF
+= l2
+| l1
+EOF
+
+test_output_expect_success "linear prune l2 ^l1" 'git-rev-list --show-breaks l2 ^l1' <<EOF
+= l2
+EOF
+
+test_output_expect_success "linear prune l5 ^a4" 'git-rev-list --show-breaks l5 ^a4' <<EOF
+= l5
+| l4
+| l3
+EOF
+
+test_output_expect_success "linear prune l5 ^l3" 'git-rev-list --show-breaks l5 ^l3' <<EOF
+= l5
+| l4
+EOF
+
+test_output_expect_success "linear prune l5 ^l4" 'git-rev-list --show-breaks l5 ^l4' <<EOF
+= l5
+EOF
+
test_expect_failure "all heads uninteresting" 'git-rev-list --show-breaks a3 ^a3'
#
#
------------
^ permalink raw reply
* [PATCH 2/7] Introduce new methods into the epoch_methods structure.
From: Jon Seymour @ 2005-06-14 2:04 UTC (permalink / raw)
To: git; +Cc: jon.seymour
The epoch_methods in epoch.h is modified to include several new methods:
visit_commit - This method is called during the sort phase of a merge order traversal.
Implementors may allocate resources and reference them by object.util during this call.
visit_edge - This method is called each time an edge is visited during the sort phase
of a merge order traversal.
clean_commit - This method allows implementors to cleanup and release any resources
allocated during visit_commit.
This change starts to move responsibility for output limiting back into rev-list.c and
starts to generalize epoch.c as a general purpose commit graph traversal algorithm.
sort_list_in_merge_order now clears all flags it uses (masked by EPOCH_FLAGS),
rather than leaving them in an undefined state as it did previously.
Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
epoch.c | 145 ++++++++++++++++++++++++++++++++++++++++--------------------
epoch.h | 35 ++++++++++++--
rev-list.c | 66 +++++++++++++++------------
3 files changed, 163 insertions(+), 83 deletions(-)
diff --git a/epoch.c b/epoch.c
--- a/epoch.c
+++ b/epoch.c
@@ -197,17 +197,65 @@ static void free_mass_counter(struct mas
free(counter);
}
-static void mark_commit(struct epoch_methods * methods, struct commit * commit)
+/*
+ * This function calls the supplied commit_visitor method, if there is one.
+ */
+static void visit_commit(struct epoch_methods * methods, struct commit * commit, int first_visit)
{
- if (methods->marker)
- (*(methods->marker))(commit);
+ /*
+ * pre-condition:
+ * first_visit => object.util == NULL
+ */
+ if (methods->commit_visitor)
+ (*(methods->commit_visitor))(commit, first_visit);
}
+/*
+ * This function is called as each edge in the graph is identified. It
+ * will always be called after visit_commit(...,from, 1). No guarantees
+ * are offered about when this call will be made w.r.t. to the call
+ * to visit_commit(..., to, 1)
+ */
+static void visit_edge(struct epoch_methods * methods, struct commit * from, struct commit * to)
+{
+ /*
+ * pre-condition:
+ * from->object.flags & VISITED &&
+ * to->object.util => (to->object.flags & VISITED)
+ */
+ if (methods->edge_visitor)
+ (*(methods->edge_visitor))(from, to);
+}
+
+/*
+ * This function is called exactly once for each commit discovered during
+ * the merge order traversal. If it ever returns a non-zero value, the
+ * merge order traversal will not continue past the current epoch boundary.
+ * It may, however, continue to emit nodes up until the epoch boundary.
+ * It is the implementer's responsibility to perform output limiting if
+ * that is required.
+ */
static int emit_commit(struct epoch_methods * methods, struct commit * commit)
{
return (*(methods->emitter))(commit);
}
+/*
+ * Invoke a call back method to allow the tactics to release and storage
+ * allocated during a previous visit_commit or visit_edge call.
+ */
+static void clean_commit(struct epoch_methods * methods, struct commit * commit)
+{
+ if (methods->clean)
+ (*(methods->clean))(commit);
+ commit->object.util = NULL;
+ commit->object.flags &= ~(EPOCH_FLAGS);
+ /*
+ * post-condition:
+ * commit->object.util == NULL && !(commit->object.flag & EPOCH_FLAGS)
+ */
+}
+
void init_epoch_methods(struct epoch_methods * methods)
{
memset(methods, 0, sizeof(*methods));
@@ -410,7 +458,7 @@ static void mark_ancestors_uninteresting
* all uninteresting, unvisited parents as they are visited
* so there is no need to duplicate that traversal here.
*
- * Similarly, if we are already marked uninteresting
+ * Similarly, if the commit is already marked uninteresting
* then either all ancestors have already been marked
* uninteresting or will be once the sort_unvisited
* traverse reaches them.
@@ -432,10 +480,13 @@ static void sort_unvisited(
struct commit_list *parents = NULL;
struct commit * top = *stack?(*stack)->item:NULL;
- if (IS_VISITED(head))
+ if (IS_VISITED(head)) {
+ if (!IS_BASE(head)) {
+ visit_commit(methods, head, 0);
+ }
return;
+ }
head->object.flags |= VISITED;
- mark_commit(methods, head);
if (IS_BASE(head)) {
ASSERT(!top, "stack empty on visit to base", head);
} else {
@@ -445,57 +496,40 @@ static void sort_unvisited(
parents = (struct commit_list *)head->object.util;
head->object.util = NULL;
}
+ visit_commit(methods, head, 1);
while (parents) {
struct commit *parent = pop_commit(&parents);
if (IS_UNINTERESTING(head)) {
mark_ancestors_uninteresting(parent);
}
+ visit_edge(methods, head, parent);
sort_unvisited(parent, stack, methods);
}
+ top=(*stack)?(*stack)->item:NULL;
+ if (top && !is_parent_of(top, head)) {
+ top->object.flags |= DISCONTINUITY;
+ }
+ commit_list_insert(head, stack);
}
- top=(*stack)?(*stack)->item:NULL;
- if (top && !is_parent_of(top, head)) {
- top->object.flags |= DISCONTINUITY;
- }
- commit_list_insert(head, stack);
}
/*
* Emit the contents of the stack.
* The stack is freed and replaced by NULL.
- * Sets the return value to STOP if no further output should be generated.
+ * Sets the return value to STOP if the traversal should stop.
*/
static int emit_stack(struct commit_list **stack, struct epoch_methods * methods)
{
- unsigned int seen = 0;
- int action = CONTINUE;
+ int stop = 0;
- while (*stack && (action != STOP)) {
+ while (*stack) {
struct commit *next = pop_commit(stack);
- seen |= next->object.flags;
- if (*stack)
- action = emit_commit(methods, next);
- }
- if (*stack) {
- free_commit_list(*stack);
- *stack = NULL;
- }
- if (seen & UNINTERESTING) {
- /**
- * We stop at the base of the stack, rather than
- * when we encounter the first UNINTERESTING flag.
- *
- * The reason is that there may still be interesting stuff
- * on the stack but once we reach the base there can be no
- * more interesting stuff by definition of what the base
- * of an epoch is - everything reachable from the base is
- * also reachable from the UNINTERESTING node and hence
- * is uninteresting.
- */
- action = STOP;
+
+ stop = (emit_commit(methods, next)==STOP) || (next->object.flags & UNINTERESTING) || stop ;
+ clean_commit(methods, next);
}
- return action;
+ return stop ? STOP : CONTINUE;
}
/*
@@ -558,6 +592,7 @@ static unsigned int sort_local_branches_
*/
if (!IS_BASE(item) && !item->object.util) {
struct commit_list ** copied;
+
if ((*(methods->local_test)) (item))
item->object.flags |= LOCAL;
copied=copy_and_store_parents(item);
@@ -587,16 +622,33 @@ static unsigned int sort_local_branches_
* reach the base and emitting as we go. We don't emit the base
* now.
*/
-static int sort_maximal_linear_epoch(struct commit *next, struct epoch_methods * methods)
+static int sort_maximal_linear_epoch(struct commit *head, struct epoch_methods * methods)
{
- while (!IS_BASE(next)) {
- mark_commit(methods, next);
- if (!IS_UNINTERESTING(next) && (emit_commit(methods, next) != STOP))
- next = next->parents->item;
- else
- return STOP;
+ struct commit * next;
+ struct commit * base;
+ int stop = 0;
+
+ /* invoke the visitors, if any */
+ if (methods->commit_visitor || methods->edge_visitor) {
+ for (next = head; !IS_BASE(next); next = next->parents->item) {
+ visit_commit(methods, next, 1);
+ visit_edge(methods, next, next->parents->item);
+ }
+ }
+ /* now emit the nodes, and mark the base*/
+ for (next = head; !IS_BASE(next); next = next->parents->item) {
+ stop = (emit_commit(methods, next)==STOP) || stop;
+ if (IS_UNINTERESTING(next)) {
+ next->parents->item->object.flags |= UNINTERESTING;
+ stop = 1;
+ }
}
- return CONTINUE;
+ base = next;
+ /* then clean the nodes */
+ for (next = head; next != base; next = next->parents->item)
+ clean_commit(methods, next);
+
+ return stop ? STOP : CONTINUE;
}
/*
@@ -617,9 +669,6 @@ static int sort_minimal_non_linear_epoch
/*
* 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.
*/
static int sort_in_merge_order(struct commit *head, struct epoch_methods * methods)
{
diff --git a/epoch.h b/epoch.h
--- a/epoch.h
+++ b/epoch.h
@@ -11,6 +11,9 @@
#define DUPCHECK (1u<<6)
#define LOCAL (1u<<7)
#define BASE (1u<<8)
+#define FORK (1u<<9)
+
+#define EPOCH_FLAGS (UNINTERESTING|BOUNDARY|VISITED|DISCONTINUITY|DUPCHECK|LOCAL|BASE)
/**
* Return codes for emitter method. Also used by rev-list.c
@@ -28,13 +31,33 @@ struct epoch_methods {
* Returns non-zero if the commit is regarded "local", 0 otherwise.
*/
int (*local_test)(struct commit *);
- /*
- * Implementers may use this method to mark commits uninteresting
- * according to some locally determined criteria. The tree
- * will be pruned at any commit so marked.
+
+ /*
+ * If defined, called on each visit to a vertex during the
+ * sort phase of the traversal. first_visit will be
+ * non-zero on the first visit, zero otherwise.
+ *
+ * object.util is available for use by the visitor.
+ */
+ void (*commit_visitor)(struct commit *, int first_visit);
+
+ /*
+ * Called at some point prior to visiting 'to' from 'from'.
+ * commit_visitor will already have been called at least once for
+ * from node. It may or may not have already been called for the
+ * to node.
+ */
+ void (*edge_visitor)(struct commit * from, struct commit * to);
+
+ /*
+ * Called sometime after the emitter function has been called.
+ * Once this call completes the object.util pointer will be set to NULL.
+ * Implementers should use this call to free any data structure
+ * allocated by the commit_visitor method.
*/
- void (*marker)(struct commit *);
-};
+ void (*clean)(struct commit *);
+}
+;
/**
* Initializes an epoch_methods structure which
diff --git a/rev-list.c b/rev-list.c
--- a/rev-list.c
+++ b/rev-list.c
@@ -18,7 +18,7 @@ static const char rev_list_usage[] =
" --wrt-author\n"
" --prune-at-author\n"
" --author=author@domain\n"
- " --show-breaks ]";
+ " --show-breaks";
static int verbose_header = 0;
static int show_parents = 0;
@@ -167,9 +167,9 @@ static int is_local_author(struct commit
return 0;
}
-static void mark_authors_own_uninteresting(struct commit * commit)
+static void mark_authors_own_uninteresting(struct commit * commit, int first_visit)
{
- if (is_local_author(commit)) {
+ if (first_visit && is_local_author(commit)) {
struct commit_list * parents = commit->parents;
for (;parents;parents=parents->next) {
parents->item->object.flags |= UNINTERESTING;
@@ -177,6 +177,34 @@ static void mark_authors_own_uninteresti
}
}
+static void merge_order_traversal(struct commit_list * list)
+{
+ struct epoch_methods methods;
+
+ init_epoch_methods(&methods);
+ if ((prune_at_author|wrt_author) && !local_author) {
+ local_author = gitenv("GIT_AUTHOR_EMAIL") ? : NULL;
+ if (!local_author)
+ get_real_identity(&local_author, NULL);
+ else
+ local_author = strdup(local_author);
+ }
+ if (local_author) {
+ /* add delimiters to improve accuracy of match */
+ char * tmp=xmalloc(strlen(local_author)+3);
+ sprintf(tmp, "<%s>", local_author);
+ free(local_author);
+ local_author = tmp;
+ }
+ methods.emitter = &process_commit;
+ if (wrt_author)
+ methods.local_test = &is_local_author;
+ if (prune_at_author)
+ methods.commit_visitor = &mark_authors_own_uninteresting;
+ if (sort_list_in_merge_order(list, &methods))
+ die("merge order sort failed\n");
+}
+
int main(int argc, char **argv)
{
struct commit_list *list = NULL;
@@ -254,38 +282,18 @@ int main(int argc, char **argv)
if (!list)
usage(rev_list_usage);
- if (!merge_order)
- merge_order = wrt_author || prune_at_author || show_breaks;
+ merge_order =
+ merge_order
+ || wrt_author
+ || prune_at_author
+ || show_breaks;
if (!merge_order) {
if (limited)
list = limit_list(list);
show_commit_list(list);
} else {
- struct epoch_methods methods;
-
- init_epoch_methods(&methods);
- if ((prune_at_author|wrt_author) && !local_author) {
- local_author = gitenv("GIT_AUTHOR_EMAIL") ? : NULL;
- if (!local_author)
- get_real_identity(&local_author, NULL);
- else
- local_author = strdup(local_author);
- }
- if (local_author) {
- /* add delimiters to improve accuracy of match */
- char * tmp=xmalloc(strlen(local_author)+3);
- sprintf(tmp, "<%s>", local_author);
- free(local_author);
- local_author = tmp;
- }
- methods.emitter = &process_commit;
- if (wrt_author)
- methods.local_test = &is_local_author;
- if (prune_at_author)
- methods.marker = &mark_authors_own_uninteresting;
- if (sort_list_in_merge_order(list, &methods))
- die("merge order sort failed\n");
+ merge_order_traversal(list);
}
return 0;
------------
^ permalink raw reply
* [PATCH 3/7] Rename epoch.c entry points as traverse_* methods/stuctures
From: Jon Seymour @ 2005-06-14 2:04 UTC (permalink / raw)
To: git; +Cc: jon.seymour
The entry points in epoch.c have been renamed to reflect the
fact that they are actually traversal methods rather than
sorting methods.
Also, struct epoch_methods has been renamed as struct traversal.
A future change will rename epoch.[ch] as traversal.[ch]
Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
epoch.c | 107 ++++++++++++++++++++++++++++++------------------------------
epoch.h | 32 +++++++++++-------
rev-list.c | 12 +++----
3 files changed, 80 insertions(+), 71 deletions(-)
diff --git a/epoch.c b/epoch.c
--- a/epoch.c
+++ b/epoch.c
@@ -200,14 +200,14 @@ static void free_mass_counter(struct mas
/*
* This function calls the supplied commit_visitor method, if there is one.
*/
-static void visit_commit(struct epoch_methods * methods, struct commit * commit, int first_visit)
+static void visit_commit(struct traversal * traversal, struct commit * commit, int first_visit)
{
/*
* pre-condition:
* first_visit => object.util == NULL
*/
- if (methods->commit_visitor)
- (*(methods->commit_visitor))(commit, first_visit);
+ if (traversal->commit_visitor)
+ (*(traversal->commit_visitor))(commit, first_visit);
}
/*
@@ -216,15 +216,15 @@ static void visit_commit(struct epoch_me
* are offered about when this call will be made w.r.t. to the call
* to visit_commit(..., to, 1)
*/
-static void visit_edge(struct epoch_methods * methods, struct commit * from, struct commit * to)
+static void visit_edge(struct traversal * traversal, struct commit * from, struct commit * to)
{
/*
* pre-condition:
* from->object.flags & VISITED &&
* to->object.util => (to->object.flags & VISITED)
*/
- if (methods->edge_visitor)
- (*(methods->edge_visitor))(from, to);
+ if (traversal->edge_visitor)
+ (*(traversal->edge_visitor))(from, to);
}
/*
@@ -235,19 +235,19 @@ static void visit_edge(struct epoch_meth
* It is the implementer's responsibility to perform output limiting if
* that is required.
*/
-static int emit_commit(struct epoch_methods * methods, struct commit * commit)
+static int emit_commit(struct traversal * traversal, struct commit * commit)
{
- return (*(methods->emitter))(commit);
+ return (*(traversal->emitter))(commit);
}
/*
* Invoke a call back method to allow the tactics to release and storage
* allocated during a previous visit_commit or visit_edge call.
*/
-static void clean_commit(struct epoch_methods * methods, struct commit * commit)
+static void clean_commit(struct traversal * traversal, struct commit * commit)
{
- if (methods->clean)
- (*(methods->clean))(commit);
+ if (traversal->clean)
+ (*(traversal->clean))(commit);
commit->object.util = NULL;
commit->object.flags &= ~(EPOCH_FLAGS);
/*
@@ -256,9 +256,9 @@ static void clean_commit(struct epoch_me
*/
}
-void init_epoch_methods(struct epoch_methods * methods)
+void init_traversal(struct traversal * traversal)
{
- memset(methods, 0, sizeof(*methods));
+ memset(traversal, 0, sizeof(*traversal));
}
/*
@@ -475,14 +475,14 @@ static void mark_ancestors_uninteresting
static void sort_unvisited(
struct commit *head,
struct commit_list **stack,
- struct epoch_methods * methods)
+ struct traversal * traversal)
{
struct commit_list *parents = NULL;
struct commit * top = *stack?(*stack)->item:NULL;
if (IS_VISITED(head)) {
if (!IS_BASE(head)) {
- visit_commit(methods, head, 0);
+ visit_commit(traversal, head, 0);
}
return;
}
@@ -496,15 +496,15 @@ static void sort_unvisited(
parents = (struct commit_list *)head->object.util;
head->object.util = NULL;
}
- visit_commit(methods, head, 1);
+ visit_commit(traversal, head, 1);
while (parents) {
struct commit *parent = pop_commit(&parents);
if (IS_UNINTERESTING(head)) {
mark_ancestors_uninteresting(parent);
}
- visit_edge(methods, head, parent);
- sort_unvisited(parent, stack, methods);
+ visit_edge(traversal, head, parent);
+ sort_unvisited(parent, stack, traversal);
}
top=(*stack)?(*stack)->item:NULL;
if (top && !is_parent_of(top, head)) {
@@ -519,15 +519,15 @@ static void sort_unvisited(
* The stack is freed and replaced by NULL.
* Sets the return value to STOP if the traversal should stop.
*/
-static int emit_stack(struct commit_list **stack, struct epoch_methods * methods)
+static int emit_stack(struct commit_list **stack, struct traversal * traversal)
{
int stop = 0;
while (*stack) {
struct commit *next = pop_commit(stack);
- stop = (emit_commit(methods, next)==STOP) || (next->object.flags & UNINTERESTING) || stop ;
- clean_commit(methods, next);
+ stop = (emit_commit(traversal, next)==STOP) || (next->object.flags & UNINTERESTING) || stop ;
+ clean_commit(traversal, next);
}
return stop ? STOP : CONTINUE;
}
@@ -573,13 +573,13 @@ static struct commit_list ** move(struct
* The return value contains LOCAL if any of the list is local or had a
* local ancestor.
*/
-static unsigned int sort_local_branches_first(struct commit_list ** list, struct epoch_methods * methods)
+static unsigned int sort_local_branches_first(struct commit_list ** list, struct traversal * traversal)
{
struct commit_list *local = NULL;
struct commit_list **local_tail = &local;
struct commit_list **non_local_ptr;
- ASSERT(methods->local_test, "local_test method is defined", NULL);
+ ASSERT(traversal->local_test, "local_test method is defined", NULL);
if (!*list) {
return 0;
}
@@ -593,11 +593,11 @@ static unsigned int sort_local_branches_
if (!IS_BASE(item) && !item->object.util) {
struct commit_list ** copied;
- if ((*(methods->local_test)) (item))
+ if ((*(traversal->local_test)) (item))
item->object.flags |= LOCAL;
copied=copy_and_store_parents(item);
item->object.flags
- |= sort_local_branches_first(copied, methods);
+ |= sort_local_branches_first(copied, traversal);
}
/**
* Move local items onto their own list.
@@ -622,22 +622,22 @@ static unsigned int sort_local_branches_
* reach the base and emitting as we go. We don't emit the base
* now.
*/
-static int sort_maximal_linear_epoch(struct commit *head, struct epoch_methods * methods)
+static int sort_maximal_linear_epoch(struct commit *head, struct traversal * traversal)
{
struct commit * next;
struct commit * base;
int stop = 0;
/* invoke the visitors, if any */
- if (methods->commit_visitor || methods->edge_visitor) {
+ if (traversal->commit_visitor || traversal->edge_visitor) {
for (next = head; !IS_BASE(next); next = next->parents->item) {
- visit_commit(methods, next, 1);
- visit_edge(methods, next, next->parents->item);
+ visit_commit(traversal, next, 1);
+ visit_edge(traversal, next, next->parents->item);
}
}
/* now emit the nodes, and mark the base*/
for (next = head; !IS_BASE(next); next = next->parents->item) {
- stop = (emit_commit(methods, next)==STOP) || stop;
+ stop = (emit_commit(traversal, next)==STOP) || stop;
if (IS_UNINTERESTING(next)) {
next->parents->item->object.flags |= UNINTERESTING;
stop = 1;
@@ -646,7 +646,7 @@ static int sort_maximal_linear_epoch(str
base = next;
/* then clean the nodes */
for (next = head; next != base; next = next->parents->item)
- clean_commit(methods, next);
+ clean_commit(traversal, next);
return stop ? STOP : CONTINUE;
}
@@ -657,20 +657,20 @@ static int sort_maximal_linear_epoch(str
* parents of each commit in the epoch, if required, then emitting
* the stack.
*/
-static int sort_minimal_non_linear_epoch(struct commit *head, struct epoch_methods * methods)
+static int sort_minimal_non_linear_epoch(struct commit *head, struct traversal * traversal)
{
struct commit_list *stack = NULL;
- if (methods->local_test)
- sort_local_branches_first(copy_and_store_parents(head), methods);
- sort_unvisited(head, &stack, methods);
- return emit_stack(&stack, methods);
+ if (traversal->local_test)
+ sort_local_branches_first(copy_and_store_parents(head), traversal);
+ sort_unvisited(head, &stack, traversal);
+ return emit_stack(&stack, traversal);
}
+
/*
- * Sorts an arbitrary epoch into merge order by sorting each epoch
- * of its epoch sequence into order.
+ * see epoch.h
*/
-static int sort_in_merge_order(struct commit *head, struct epoch_methods * methods)
+int traverse_from_head(struct commit *head, struct traversal * traversal)
{
struct commit *next = head;
int ret = 0;
@@ -699,9 +699,9 @@ static int sort_in_merge_order(struct co
/* sort with the optimal algorithm */
if (HAS_EXACTLY_ONE_PARENT(next))
- next_action = sort_maximal_linear_epoch(next, methods);
+ next_action = sort_maximal_linear_epoch(next, traversal);
else
- next_action = sort_minimal_non_linear_epoch(next, methods);
+ next_action = sort_minimal_non_linear_epoch(next, traversal);
/* stop or iterate */
if (next_action == STOP)
@@ -710,26 +710,27 @@ static int sort_in_merge_order(struct co
next = base;
}
if (next)
- emit_commit(methods, next);
+ emit_commit(traversal, next);
return 0;
}
/*
- * Sorts the nodes reachable from a starting list in merge order, we
+ * see epoch.h
+ * Traverses the nodes reachable from a starting list in merge order, we
* first find the base for the starting list and then sort all nodes
* in this subgraph using the sort_unvisited algorithm. Once we have
- * reached the base we can continue sorting using sort_in_merge_order.
+ * reached the base we can continue sorting using traverse_from_head.
*/
-int sort_list_in_merge_order(struct commit_list *list, struct epoch_methods * methods)
+int traverse_from_list(struct commit_list *list, struct traversal * traversal)
{
struct commit_list *stack = NULL;
struct commit_list *filtered = NULL;
struct commit *base;
int ret = 0;
- if (!methods)
- die("methods argument must not be null");
- if (!methods->emitter)
+ if (!traversal)
+ die("traversal argument must not be null");
+ if (!traversal->emitter)
die("an emitter method must be supplied");
/**
* Remove duplicates and uninteresting items.
@@ -765,15 +766,15 @@ int sort_list_in_merge_order(struct comm
base->object.flags |= (BOUNDARY|BASE);
/* sort local branches first, so they print last */
- if (methods->local_test)
- sort_local_branches_first(&filtered, methods);
+ if (traversal->local_test)
+ sort_local_branches_first(&filtered, traversal);
/* sort the unvisited part of the epoch in merge order */
while (filtered)
- sort_unvisited(pop_commit(&filtered), &stack, methods);
+ sort_unvisited(pop_commit(&filtered), &stack, traversal);
/* output the stack */
- if (emit_stack(&stack, methods) == STOP)
+ if (emit_stack(&stack, traversal) == STOP)
return STOP;
} else {
/*
@@ -786,6 +787,6 @@ int sort_list_in_merge_order(struct comm
/* sort the rest with the sort_in_merge_order algorithm. */
if (base)
- ret = sort_in_merge_order(base, methods);
+ ret = traverse_from_head(base, traversal);
return ret;
}
diff --git a/epoch.h b/epoch.h
--- a/epoch.h
+++ b/epoch.h
@@ -22,11 +22,12 @@
#define CONTINUE 1
#define DO 2
-struct epoch_methods {
+struct traversal {
/*
* Returns 0 if traversal should stop, non-zero if it should continue.
*/
int (*emitter)(struct commit *);
+
/*
* Returns non-zero if the commit is regarded "local", 0 otherwise.
*/
@@ -60,20 +61,27 @@ struct epoch_methods {
;
/**
- * Initializes an epoch_methods structure which
+ * Initializes a traversal structure which
* may be customized by the caller by overriding any of the method pointers.
*/
-extern void init_epoch_methods(struct epoch_methods *);
+extern void init_traversal(struct traversal *);
+
+/**
+ * Traverses the commit graph from the commits listed.
+ *
+ * The traversal is performed in (optionally localised) merge order
+ * which is defined by invariants specified in Documentation/git-rev-list.txt
+ *
+ * The tactics used during the traversal can be customized
+ * by configuring the traversal structure with appropriately
+ * defined method pointers.
+
+ */
+extern int traverse_from_list(struct commit_list *list, struct traversal * traversal);
/**
- * Sorts the list of commits in merge order, using the methods specified
- * to customize the tactics of the search.
- *
- * The prune points should be marked with the UNINTERESTING flags.
- *
- * Note: this algorithm is dirty in the sense that it leaves traces
- * of its execution in the object.flags word of some or all of the commits
- * visited.
+ * Traverses the commit graph from the head commit listed. In other
+ * respects, like traverse_from_list.
*/
-extern int sort_list_in_merge_order(struct commit_list *list, struct epoch_methods * methods);
+extern int traverse_from_head(struct commit *head, struct traversal * traversal);
#endif /* EPOCH_H */
diff --git a/rev-list.c b/rev-list.c
--- a/rev-list.c
+++ b/rev-list.c
@@ -179,9 +179,9 @@ static void mark_authors_own_uninteresti
static void merge_order_traversal(struct commit_list * list)
{
- struct epoch_methods methods;
+ struct traversal traversal;
- init_epoch_methods(&methods);
+ init_traversal(&traversal);
if ((prune_at_author|wrt_author) && !local_author) {
local_author = gitenv("GIT_AUTHOR_EMAIL") ? : NULL;
if (!local_author)
@@ -196,12 +196,12 @@ static void merge_order_traversal(struct
free(local_author);
local_author = tmp;
}
- methods.emitter = &process_commit;
+ traversal.emitter = &process_commit;
if (wrt_author)
- methods.local_test = &is_local_author;
+ traversal.local_test = &is_local_author;
if (prune_at_author)
- methods.commit_visitor = &mark_authors_own_uninteresting;
- if (sort_list_in_merge_order(list, &methods))
+ traversal.commit_visitor = &mark_authors_own_uninteresting;
+ if (traverse_from_list(list, &traversal))
die("merge order sort failed\n");
}
------------
^ permalink raw reply
* [PATCH 4/7] Move two general purpose commit-related functions into commit.[ch]
From: Jon Seymour @ 2005-06-14 2:04 UTC (permalink / raw)
To: git; +Cc: jon.seymour
Moved is_parent_of and move_commit from epoch.c into commit.c
is_parent_of returns a non-zero value if the left argument
is a parent of the right argument.
move_commit implements the slightly complicated pointer
arithmetic required to remove an element from the middle
of a singly-linked list. It is moved into commit.c
because a future change to rev-list.c will need to
use logic originally implemented in epoch.c
Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
commit.c | 23 +++++++++++++++++++++++
commit.h | 31 +++++++++++++++++++++++++++++++
epoch.c | 31 ++-----------------------------
3 files changed, 56 insertions(+), 29 deletions(-)
diff --git a/commit.c b/commit.c
--- a/commit.c
+++ b/commit.c
@@ -374,3 +374,26 @@ struct commit_list * copy_parents_in_hea
}
return result;
}
+
+int is_parent_of(struct commit *parent, struct commit *child)
+{
+ struct commit_list *parents;
+
+ for (parents = child->parents; parents; parents = parents->next)
+ if (parent==parents->item)
+ return 1;
+ return 0;
+}
+
+/**
+ * pre-condition: src && dst && *src && !(*dst)
+ * post-condition: result && !(*result) && src && dst && *dst
+ */
+struct commit_list ** move_commit(struct commit_list ** dst, struct commit_list ** src)
+{
+ *dst = *src;
+ *src = (*src)->next;
+ (*dst)->next = NULL;
+ return &(*dst)->next;
+}
+
diff --git a/commit.h b/commit.h
--- a/commit.h
+++ b/commit.h
@@ -84,4 +84,35 @@ int copy_author(struct commit * commit,
* they are finished with it.
*/
struct commit_list * copy_parents_in_header_order(struct commit * commit);
+
+/*
+ * Return a non-zero value if "commit" is a parent of "child", zero otherwise.
+ */
+int is_parent_of(struct commit *commit, struct commit *child);
+
+
+/**
+ * Move an item pointed to by *src_ptr onto the tail of a list pointed
+ * to by dst_tail and return the updated tail pointer. *src_ptr is
+ * updated to refer to the next element on the source list
+ * or NULL if there is no such element.
+ *
+ * Example:
+ *
+ * struct commit_list * src = ...;
+ * struct commit_list * dst = NULL;
+ * struct commit_list ** dst_tail = &dst;
+ * struct commit_list ** src_ptr = &src;
+ *
+ * while (*src_ptr) {
+ * if (is_moveable(*src_ptr)) {
+ * dst_tail = move_commit(dst_tail, src_ptr);
+ * else {
+ * src_ptr=&(*src_ptr)->next;
+ * }
+ * }
+ */
+struct commit_list ** move_commit(struct commit_list ** dst_tail, struct commit_list ** src_ptr);
+
#endif /* COMMIT_H */
+
diff --git a/epoch.c b/epoch.c
--- a/epoch.c
+++ b/epoch.c
@@ -417,19 +417,6 @@ static int find_next_epoch_boundary(stru
}
/*
- * 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 (parent==parents->item)
- return 1;
- return 0;
-}
-
-/*
* Marks all interesting, visited commits reachable from this commit
* as uninteresting. We stop recursing when we reach the epoch boundary,
* an unvisited node or a node that has already been marked uninteresting.
@@ -544,21 +531,6 @@ static struct commit_list ** copy_and_st
return (struct commit_list **)&commit->object.util;
}
-/**
- * Move an item pointed to by *src onto the tail of a list pointed to by dst
- * and return the updated tail pointer. *src is updated to refer to the
- * next element on the source list or NULL if there is no such element.
- */
-static struct commit_list ** move(struct commit_list ** dst, struct commit_list ** src)
-{
- ASSERT(*src, "*src is never NULL", NULL);
- ASSERT(!*dst || !(*dst)->next, "*dst is NULL or (*dst)->next is NULL", NULL);
- *dst = *src;
- *src = (*src)->next;
- (*dst)->next = NULL;
- return &(*dst)->next;
-}
-
/*
* Sort a list of commits in local first order. A commit is "local"
* if any of its ancestors (except the base) causes (*local_test)() to
@@ -603,7 +575,7 @@ static unsigned int sort_local_branches_
* Move local items onto their own list.
*/
if (IS_LOCAL(item))
- local_tail = move(local_tail, non_local_ptr);
+ local_tail = move_commit(local_tail, non_local_ptr);
else
non_local_ptr = &(*non_local_ptr)->next;
}
@@ -790,3 +762,4 @@ int traverse_from_list(struct commit_lis
ret = traverse_from_head(base, traversal);
return ret;
}
+
------------
^ permalink raw reply
* [PATCH 5/7] Move knowledge of UNINTERESTING flag into rev-list.c
From: Jon Seymour @ 2005-06-14 2:04 UTC (permalink / raw)
To: git; +Cc: jon.seymour
This patch moves all knowledge of output limiting into rev-list.c
even for merge order traversals.
A new method, continue_traversal, is added to the traversal
structure to permit tools to control how far into the graph
the traversal proceeds.
A future modification will do the same for the DISCONTINUITY
and DUPCHECK flags and then remove all these flags from the
epoch.h header.
Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
epoch.c | 112 ++++++++++++++++++------------------------------------------
epoch.h | 14 +++++---
rev-list.c | 91 +++++++++++++++++++++++++++++++++++++++++++++++--
3 files changed, 131 insertions(+), 86 deletions(-)
diff --git a/epoch.c b/epoch.c
--- a/epoch.c
+++ b/epoch.c
@@ -256,6 +256,17 @@ static void clean_commit(struct traversa
*/
}
+/**
+ * Ask the tactics if we should traverse into the epoch headed at head.
+ */
+static int continue_traversal(struct traversal * traversal, struct commit * head)
+{
+ if (traversal->continue_traversal)
+ return (*(traversal->continue_traversal))(head);
+ else
+ return 1;
+}
+
void init_traversal(struct traversal * traversal)
{
memset(traversal, 0, sizeof(*traversal));
@@ -417,46 +428,6 @@ static int find_next_epoch_boundary(stru
}
/*
- * Marks all interesting, visited commits reachable from this commit
- * as uninteresting. We stop recursing when we reach the epoch boundary,
- * an unvisited node or a node that has already been marked uninteresting.
- *
- * This doesn't actually mark all ancestors between the start node and the
- * epoch boundary uninteresting, but does ensure that they will eventually
- * be marked uninteresting when the main sort_unvisited() traversal
- * eventually reaches them.
- */
-static void mark_ancestors_uninteresting(struct commit *commit)
-{
- unsigned int flags = commit->object.flags;
- int visited = flags & VISITED;
- int boundary = flags & BOUNDARY;
- int uninteresting = flags & UNINTERESTING;
- struct commit_list *next;
-
- commit->object.flags |= UNINTERESTING;
- /*
- * We only need to recurse if
- * we are not on the boundary and
- * we have not already been marked uninteresting and
- * we have already been visited.
- *
- * The main sort_unvisited traverse will mark unreachable
- * all uninteresting, unvisited parents as they are visited
- * so there is no need to duplicate that traversal here.
- *
- * Similarly, if the commit is already marked uninteresting
- * then either all ancestors have already been marked
- * uninteresting or will be once the sort_unvisited
- * traverse reaches them.
- */
- if (uninteresting || boundary || !visited)
- return;
- for (next = commit->parents; next; next = next->next)
- mark_ancestors_uninteresting(next->item);
-}
-
-/*
* Sort the epoch in (adjusted) merge order.
*/
static void sort_unvisited(
@@ -487,9 +458,6 @@ static void sort_unvisited(
while (parents) {
struct commit *parent = pop_commit(&parents);
- if (IS_UNINTERESTING(head)) {
- mark_ancestors_uninteresting(parent);
- }
visit_edge(traversal, head, parent);
sort_unvisited(parent, stack, traversal);
}
@@ -513,7 +481,7 @@ static int emit_stack(struct commit_list
while (*stack) {
struct commit *next = pop_commit(stack);
- stop = (emit_commit(traversal, next)==STOP) || (next->object.flags & UNINTERESTING) || stop ;
+ stop = stop || (emit_commit(traversal, next)==STOP);
clean_commit(traversal, next);
}
return stop ? STOP : CONTINUE;
@@ -597,7 +565,6 @@ static unsigned int sort_local_branches_
static int sort_maximal_linear_epoch(struct commit *head, struct traversal * traversal)
{
struct commit * next;
- struct commit * base;
int stop = 0;
/* invoke the visitors, if any */
@@ -609,17 +576,9 @@ static int sort_maximal_linear_epoch(str
}
/* now emit the nodes, and mark the base*/
for (next = head; !IS_BASE(next); next = next->parents->item) {
- stop = (emit_commit(traversal, next)==STOP) || stop;
- if (IS_UNINTERESTING(next)) {
- next->parents->item->object.flags |= UNINTERESTING;
- stop = 1;
- }
- }
- base = next;
- /* then clean the nodes */
- for (next = head; next != base; next = next->parents->item)
+ stop = stop || (emit_commit(traversal, next)==STOP);
clean_commit(traversal, next);
-
+ }
return stop ? STOP : CONTINUE;
}
@@ -651,7 +610,7 @@ int traverse_from_head(struct commit *he
if (ret)
return ret;
next->object.flags |= BOUNDARY;
- while (next && next->parents) {
+ while (next && next->parents && continue_traversal(traversal, next)) {
struct commit *base = NULL;
int next_action = CONTINUE;
@@ -681,8 +640,10 @@ int traverse_from_head(struct commit *he
else
next = base;
}
- if (next)
+ if (next) {
emit_commit(traversal, next);
+ clean_commit(traversal, next);
+ }
return 0;
}
@@ -696,7 +657,6 @@ int traverse_from_head(struct commit *he
int traverse_from_list(struct commit_list *list, struct traversal * traversal)
{
struct commit_list *stack = NULL;
- struct commit_list *filtered = NULL;
struct commit *base;
int ret = 0;
@@ -704,32 +664,26 @@ int traverse_from_list(struct commit_lis
die("traversal argument must not be null");
if (!traversal->emitter)
die("an emitter method must be supplied");
- /**
- * Remove duplicates and uninteresting items.
- * Duplicates are not allowed by find_base_for_list and
- * uninteresting items may prevent us identifying the
- * right type of traversal to do.
- */
- for (; list; list = list->next) {
- struct commit *next = list->item;
+ if (list->next) {
+ struct commit_list * copy=NULL;
- if (!(next->object.flags & (UNINTERESTING|DUPCHECK))) {
- next->object.flags |= DUPCHECK;
- commit_list_insert(list->item, &filtered);
+ /*
+ * Make a copy of the list we can sort.
+ */
+ for(;list;list=list->next) {
+ commit_list_insert(list->item, ©);
}
- }
- if (!filtered)
- die("no uninteresting heads were specified\n");
- if (filtered->next) {
+ list=copy;
+
/*
* With multiple items to start the search with,
* we first sort the list into local order (if required)
*
* This behaves as if a commit was performed which
- * referenced the filtered list as parents. This
+ * referenced the list as parents. This
* would create a minimal, non-linear epoch.
*/
- ret = find_base_for_list(filtered, &base);
+ ret = find_base_for_list(list, &base);
if (ret)
return ret; /* parsing failure */
@@ -739,11 +693,11 @@ int traverse_from_list(struct commit_lis
/* sort local branches first, so they print last */
if (traversal->local_test)
- sort_local_branches_first(&filtered, traversal);
+ sort_local_branches_first(&list, traversal);
/* sort the unvisited part of the epoch in merge order */
- while (filtered)
- sort_unvisited(pop_commit(&filtered), &stack, traversal);
+ while (list)
+ sort_unvisited(pop_commit(&list), &stack, traversal);
/* output the stack */
if (emit_stack(&stack, traversal) == STOP)
@@ -754,7 +708,7 @@ int traverse_from_list(struct commit_lis
* sort in merge order which handles maximal
* linear epochs as well as minimal, non-linear epochs.
*/
- base = filtered->item;
+ base = list->item;
}
/* sort the rest with the sort_in_merge_order algorithm. */
diff --git a/epoch.h b/epoch.h
--- a/epoch.h
+++ b/epoch.h
@@ -11,16 +11,15 @@
#define DUPCHECK (1u<<6)
#define LOCAL (1u<<7)
#define BASE (1u<<8)
-#define FORK (1u<<9)
#define EPOCH_FLAGS (UNINTERESTING|BOUNDARY|VISITED|DISCONTINUITY|DUPCHECK|LOCAL|BASE)
/**
* Return codes for emitter method. Also used by rev-list.c
*/
-#define STOP 0
-#define CONTINUE 1
-#define DO 2
+#define STOP 0
+#define CONTINUE 1
+#define DO 2
struct traversal {
/*
@@ -57,6 +56,13 @@ struct traversal {
* allocated by the commit_visitor method.
*/
void (*clean)(struct commit *);
+
+ /*
+ * Called at each epoch boundary. Implementers may return
+ * non-zero if the traversal into the next epoch should
+ * be stopped.
+ */
+ int (*continue_traversal)(struct commit *);
}
;
diff --git a/rev-list.c b/rev-list.c
--- a/rev-list.c
+++ b/rev-list.c
@@ -33,6 +33,7 @@ static int show_breaks = 0;
static char * local_author = NULL;
static int prune_at_author = 0;
static int wrt_author = 0;
+static int stop_traversal = 0;
static void show_commit(struct commit *commit)
{
@@ -74,11 +75,19 @@ static int filter_commit(struct commit *
return DO;
}
+static int continue_traversal(struct commit * commit)
+{
+ return !stop_traversal;
+}
+
static int process_commit(struct commit * commit)
{
int action=filter_commit(commit);
- if (action == STOP) {
+ if (commit->object.flags & UNINTERESTING)
+ stop_traversal = 1;
+
+ if (action & STOP) {
return STOP;
}
@@ -177,10 +186,79 @@ static void mark_authors_own_uninteresti
}
}
-static void merge_order_traversal(struct commit_list * list)
+/*
+ * Marks all interesting, visited commits reachable from this commit
+ * as uninteresting. We stop recursing when we reach the epoch boundary,
+ * an unvisited node or a node that has already been marked uninteresting.
+ *
+ * This doesn't actually mark all ancestors between the start node and the
+ * epoch boundary uninteresting, but does ensure that they will eventually
+ * be marked uninteresting when the main sort_unvisited() traversal
+ * eventually reaches them.
+ */
+static void mark_ancestors_uninteresting(struct commit * head, struct commit *parent)
+{
+ unsigned int flags, visited, boundary, uninteresting;
+ struct commit_list *next;
+
+ if (!(head->object.flags & UNINTERESTING)) {
+ return;
+ }
+
+ flags = parent->object.flags;
+ visited = flags & VISITED;
+ boundary = flags & BOUNDARY;
+ uninteresting = flags & UNINTERESTING;
+
+ parent->object.flags |= UNINTERESTING;
+ /*
+ * We only need to recurse if
+ * we are not on the boundary and
+ * we have not already been marked uninteresting and
+ * we have already been visited.
+ *
+ * The main sort_unvisited traverse will mark unreachable
+ * all uninteresting, unvisited parents as they are visited
+ * so there is no need to duplicate that traversal here.
+ *
+ * Similarly, if the parent is already marked uninteresting
+ * then either all ancestors have already been marked
+ * uninteresting or will be once the sort_unvisited
+ * traverse reaches them.
+ */
+ if (uninteresting || boundary || !visited)
+ return;
+ for (next = parent->parents; next; next = next->next)
+ mark_ancestors_uninteresting(parent, next->item);
+}
+
+static void merge_order_traversal(struct commit_list * list, int limited)
{
struct traversal traversal;
+ struct commit_list * elided = NULL;
+ struct commit_list ** elided_tail = &elided;
+ struct commit_list ** ptr=&list;
+
+ /**
+ * Remove duplicates and uninteresting items.
+ */
+ for (; *ptr; ) {
+ if ((*ptr)->item->object.flags & (UNINTERESTING|DUPCHECK))
+ elided_tail = move_commit(elided_tail, ptr);
+ else {
+ (*ptr)->item->object.flags |= DUPCHECK;
+ ptr = &(*ptr)->next;
+ }
+ }
+ if (elided)
+ free_commit_list(elided);
+ if (!list) {
+ die("all of the specified heads are interesting - nothing to do");
+ }
+ /*
+ * Setup the traversal
+ */
init_traversal(&traversal);
if ((prune_at_author|wrt_author) && !local_author) {
local_author = gitenv("GIT_AUTHOR_EMAIL") ? : NULL;
@@ -197,10 +275,17 @@ static void merge_order_traversal(struct
local_author = tmp;
}
traversal.emitter = &process_commit;
+ traversal.continue_traversal = &continue_traversal;
+ if (limited || prune_at_author)
+ traversal.edge_visitor = &mark_ancestors_uninteresting;
if (wrt_author)
traversal.local_test = &is_local_author;
if (prune_at_author)
traversal.commit_visitor = &mark_authors_own_uninteresting;
+
+ /*
+ * Do it.
+ */
if (traverse_from_list(list, &traversal))
die("merge order sort failed\n");
}
@@ -293,7 +378,7 @@ int main(int argc, char **argv)
list = limit_list(list);
show_commit_list(list);
} else {
- merge_order_traversal(list);
+ merge_order_traversal(list, limited);
}
return 0;
------------
^ permalink raw reply
* [PATCH 6/7] Remove DUPCHECK, UNINTERESTING flags from epoch.h
From: Jon Seymour @ 2005-06-14 2:04 UTC (permalink / raw)
To: git; +Cc: jon.seymour
This change:
* moves --show-breaks detection into show_commit of rev-list.c,
thereby cleaning up the logic in epoch.c
* replaces epoch.c's use of VISITED flag with the SEEN flag
* removes UNINTERESTING, DUPCHECK and DISCONTINUITY flags
from epoch.h
* defines a new flag, LAST_TRAVERSAL_FLAG to allow other modules
to use flags not used by epoch.c
* redefines flags private to rev-list.c in terms of LAST_TRAVERSAL_FLAG
Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
epoch.c | 22 ++++++++--------------
epoch.h | 14 ++++++--------
rev-list.c | 26 +++++++++++++++-----------
traversal.h | 1 +
4 files changed, 30 insertions(+), 33 deletions(-)
diff --git a/epoch.c b/epoch.c
--- a/epoch.c
+++ b/epoch.c
@@ -26,11 +26,9 @@ static struct fraction *one = NULL;
static struct fraction *zero = NULL;
#define HAS_EXACTLY_ONE_PARENT(n) ((n)->parents && !(n)->parents->next)
-#define IS_UNINTERESTING(c) ((c)->object.flags & UNINTERESTING)
-#define IS_VISITED(c) ((c)->object.flags & VISITED)
+#define IS_SEEN(c) ((c)->object.flags & SEEN)
#define IS_BASE(c) ((c)->object.flags & BASE)
#define IS_LOCAL(c) ((c)->object.flags & LOCAL)
-#define IS_DISCONTINUITY(c) ((c)->object.flags & DISCONTINUITY)
/* leave the assertions defined for now, maybe null def them later */
#define ASSERT(x,m,c) if (!(x)) { assertion_failed(__LINE__, __FUNCTION__, m, c); } else {}
@@ -220,8 +218,8 @@ static void visit_edge(struct traversal
{
/*
* pre-condition:
- * from->object.flags & VISITED &&
- * to->object.util => (to->object.flags & VISITED)
+ * from->object.flags & SEEN &&
+ * to->object.util => (to->object.flags & SEEN)
*/
if (traversal->edge_visitor)
(*(traversal->edge_visitor))(from, to);
@@ -249,10 +247,10 @@ static void clean_commit(struct traversa
if (traversal->clean)
(*(traversal->clean))(commit);
commit->object.util = NULL;
- commit->object.flags &= ~(EPOCH_FLAGS);
+ commit->object.flags &= ~(TRAVERSAL_FLAGS);
/*
* post-condition:
- * commit->object.util == NULL && !(commit->object.flag & EPOCH_FLAGS)
+ * commit->object.util == NULL && !(commit->object.flag & TRAVERSAL_FLAGS)
*/
}
@@ -438,13 +436,13 @@ static void sort_unvisited(
struct commit_list *parents = NULL;
struct commit * top = *stack?(*stack)->item:NULL;
- if (IS_VISITED(head)) {
+ if (IS_SEEN(head)) {
if (!IS_BASE(head)) {
visit_commit(traversal, head, 0);
}
return;
}
- head->object.flags |= VISITED;
+ head->object.flags |= SEEN;
if (IS_BASE(head)) {
ASSERT(!top, "stack empty on visit to base", head);
} else {
@@ -461,10 +459,6 @@ static void sort_unvisited(
visit_edge(traversal, head, parent);
sort_unvisited(parent, stack, traversal);
}
- top=(*stack)?(*stack)->item:NULL;
- if (top && !is_parent_of(top, head)) {
- top->object.flags |= DISCONTINUITY;
- }
commit_list_insert(head, stack);
}
}
@@ -626,7 +620,7 @@ int traverse_from_head(struct commit *he
base->object.flags |= (BOUNDARY|BASE);
/* reset flags set by last iteration */
- next->object.flags &= ~(BASE|VISITED);
+ next->object.flags &= ~(BASE|SEEN);
/* sort with the optimal algorithm */
if (HAS_EXACTLY_ONE_PARENT(next))
diff --git a/epoch.h b/epoch.h
--- a/epoch.h
+++ b/epoch.h
@@ -4,15 +4,13 @@
/**
* Flags used by merge order logic and also by rev-list.c
*/
-#define UNINTERESTING (1u<<2)
-#define BOUNDARY (1u<<3)
-#define VISITED (1u<<4)
-#define DISCONTINUITY (1u<<5)
-#define DUPCHECK (1u<<6)
-#define LOCAL (1u<<7)
-#define BASE (1u<<8)
+#define SEEN (1u<<0)
+#define BOUNDARY (SEEN<<1)
+#define LOCAL (BOUNDARY<<1)
+#define BASE (LOCAL<<1)
+#define LAST_TRAVERSAL_FLAG (BASE)
-#define EPOCH_FLAGS (UNINTERESTING|BOUNDARY|VISITED|DISCONTINUITY|DUPCHECK|LOCAL|BASE)
+#define TRAVERSAL_FLAGS (BOUNDARY|SEEN|LOCAL|BASE)
/**
* Return codes for emitter method. Also used by rev-list.c
diff --git a/rev-list.c b/rev-list.c
--- a/rev-list.c
+++ b/rev-list.c
@@ -3,8 +3,9 @@
#include "epoch.h"
#include "user.h"
-#define SEEN (1u << 0)
-#define INTERESTING (1u << 1)
+#define INTERESTING (LAST_TRAVERSAL_FLAG << 1)
+#define UNINTERESTING (INTERESTING << 1)
+#define DUPCHECK (UNINTERESTING << 1)
static const char rev_list_usage[] =
"usage: git-rev-list [OPTION] commit-id <commit-id>\n"
@@ -34,16 +35,18 @@ static char * local_author = NULL;
static int prune_at_author = 0;
static int wrt_author = 0;
static int stop_traversal = 0;
+static struct commit * last_printed = NULL;
static void show_commit(struct commit *commit)
{
+
if (show_breaks) {
prefix = "| ";
- if (commit->object.flags & DISCONTINUITY) {
- prefix = "^ ";
- } else if (commit->object.flags & BOUNDARY) {
+ if (commit->object.flags & BOUNDARY) {
prefix = "= ";
- }
+ } else if (last_printed && !is_parent_of(commit, last_printed)) {
+ prefix = "^ ";
+ }
}
printf("%s%s", prefix, sha1_to_hex(commit->object.sha1));
if (show_parents) {
@@ -59,6 +62,7 @@ static void show_commit(struct commit *c
pretty_print_commit(commit_format, commit->buffer, ~0, pretty_header, sizeof(pretty_header));
printf("%s%c", pretty_header, hdr_termination);
}
+ last_printed = commit;
}
static int filter_commit(struct commit * commit)
@@ -198,7 +202,7 @@ static void mark_authors_own_uninteresti
*/
static void mark_ancestors_uninteresting(struct commit * head, struct commit *parent)
{
- unsigned int flags, visited, boundary, uninteresting;
+ unsigned int flags, seen, boundary, uninteresting;
struct commit_list *next;
if (!(head->object.flags & UNINTERESTING)) {
@@ -206,7 +210,7 @@ static void mark_ancestors_uninteresting
}
flags = parent->object.flags;
- visited = flags & VISITED;
+ seen = flags & SEEN;
boundary = flags & BOUNDARY;
uninteresting = flags & UNINTERESTING;
@@ -215,9 +219,9 @@ static void mark_ancestors_uninteresting
* We only need to recurse if
* we are not on the boundary and
* we have not already been marked uninteresting and
- * we have already been visited.
+ * we have already been seen.
*
- * The main sort_unvisited traverse will mark unreachable
+ * The main traversal will mark unreachable
* all uninteresting, unvisited parents as they are visited
* so there is no need to duplicate that traversal here.
*
@@ -226,7 +230,7 @@ static void mark_ancestors_uninteresting
* uninteresting or will be once the sort_unvisited
* traverse reaches them.
*/
- if (uninteresting || boundary || !visited)
+ if (uninteresting || boundary || !seen)
return;
for (next = parent->parents; next; next = next->next)
mark_ancestors_uninteresting(parent, next->item);
diff --git a/traversal.h b/traversal.h
new file mode 100644
--- /dev/null
+++ b/traversal.h
@@ -0,0 +1 @@
+/* workaround for git-apply issue */
------------
^ permalink raw reply
* [PATCH 7/7] Move traversal parts of epoch.[ch] into traversal.[ch]
From: Jon Seymour @ 2005-06-14 2:04 UTC (permalink / raw)
To: git; +Cc: jon.seymour
This change splits the non-epoch related parts of
the traversal algorithm into traversal.[ch] which
become the public interfaces for the traversal
algorithms. The strictly epoch-related code using
fractions, bignums etc., which are implementation
details of the traversal algorithms are left
in epoch.[ch]
This reduces the size of the epoch module thereby
enhancing the maintainability of both it and the
new traversal modules.
Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
Makefile | 7 +
epoch.c | 411 ++---------------------------------------------------------
epoch.h | 107 ++++-----------
rev-list.c | 2
traversal.c | 395 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
traversal.h | 92 +++++++++++++
6 files changed, 533 insertions(+), 481 deletions(-)
diff --git a/Makefile b/Makefile
--- a/Makefile
+++ b/Makefile
@@ -42,9 +42,9 @@ install: $(PROG) $(SCRIPTS)
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 entry.o \
- epoch.o refs.o user.o
+ traversal.o refs.o user.o epoch.o
LIB_FILE=libgit.a
-LIB_H=cache.h object.h blob.h tree.h commit.h tag.h delta.h epoch.h user.h
+LIB_H=cache.h object.h blob.h tree.h commit.h tag.h delta.h traversal.h user.h
LIB_H += strbuf.h
LIB_OBJS += strbuf.o
@@ -140,8 +140,9 @@ 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)
+traversal.o: $(LIB_H)
user.o: $(LIB_H)
+epoch.o: $(LIB_H)
test: all
$(MAKE) -C t/ all
diff --git a/epoch.c b/epoch.c
--- a/epoch.c
+++ b/epoch.c
@@ -7,43 +7,29 @@
* for some of the algorithms used here.
*
*/
-#include <stdlib.h>
+#include "commit.h"
+#include "epoch.h"
/* Provides arbitrary precision integers required to accurately represent
* fractional mass: */
#include <openssl/bn.h>
-#include "cache.h"
-#include "commit.h"
-#include "epoch.h"
+
+#define ASSERT(x,m,c) /* not currently used - documentation only */
struct fraction {
BIGNUM numerator;
BIGNUM denominator;
};
+struct mass_counter {
+ struct fraction seen;
+ struct fraction pending;
+};
+
static BN_CTX *context = NULL;
static struct fraction *one = NULL;
static struct fraction *zero = NULL;
-#define HAS_EXACTLY_ONE_PARENT(n) ((n)->parents && !(n)->parents->next)
-#define IS_SEEN(c) ((c)->object.flags & SEEN)
-#define IS_BASE(c) ((c)->object.flags & BASE)
-#define IS_LOCAL(c) ((c)->object.flags & LOCAL)
-
-/* leave the assertions defined for now, maybe null def them later */
-#define ASSERT(x,m,c) if (!(x)) { assertion_failed(__LINE__, __FUNCTION__, m, c); } else {}
-
-static void assertion_failed(int line, char * function, char * message, struct commit * item)
-{
- die( "%s:%d:%s: assertion_failed: %s: commit %s, flags %x",
- __FILE__,
- line,
- function,
- message,
- item ? sha1_to_hex(item->object.sha1) : "[]",
- item ? item->object.flags : 0xFFFFFFFF);
-}
-
static BN_CTX *get_BN_CTX()
{
if (!context)
@@ -168,11 +154,6 @@ static int compare(struct fraction *left
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));
@@ -196,81 +177,6 @@ static void free_mass_counter(struct mas
}
/*
- * This function calls the supplied commit_visitor method, if there is one.
- */
-static void visit_commit(struct traversal * traversal, struct commit * commit, int first_visit)
-{
- /*
- * pre-condition:
- * first_visit => object.util == NULL
- */
- if (traversal->commit_visitor)
- (*(traversal->commit_visitor))(commit, first_visit);
-}
-
-/*
- * This function is called as each edge in the graph is identified. It
- * will always be called after visit_commit(...,from, 1). No guarantees
- * are offered about when this call will be made w.r.t. to the call
- * to visit_commit(..., to, 1)
- */
-static void visit_edge(struct traversal * traversal, struct commit * from, struct commit * to)
-{
- /*
- * pre-condition:
- * from->object.flags & SEEN &&
- * to->object.util => (to->object.flags & SEEN)
- */
- if (traversal->edge_visitor)
- (*(traversal->edge_visitor))(from, to);
-}
-
-/*
- * This function is called exactly once for each commit discovered during
- * the merge order traversal. If it ever returns a non-zero value, the
- * merge order traversal will not continue past the current epoch boundary.
- * It may, however, continue to emit nodes up until the epoch boundary.
- * It is the implementer's responsibility to perform output limiting if
- * that is required.
- */
-static int emit_commit(struct traversal * traversal, struct commit * commit)
-{
- return (*(traversal->emitter))(commit);
-}
-
-/*
- * Invoke a call back method to allow the tactics to release and storage
- * allocated during a previous visit_commit or visit_edge call.
- */
-static void clean_commit(struct traversal * traversal, struct commit * commit)
-{
- if (traversal->clean)
- (*(traversal->clean))(commit);
- commit->object.util = NULL;
- commit->object.flags &= ~(TRAVERSAL_FLAGS);
- /*
- * post-condition:
- * commit->object.util == NULL && !(commit->object.flag & TRAVERSAL_FLAGS)
- */
-}
-
-/**
- * Ask the tactics if we should traverse into the epoch headed at head.
- */
-static int continue_traversal(struct traversal * traversal, struct commit * head)
-{
- if (traversal->continue_traversal)
- return (*(traversal->continue_traversal))(head);
- else
- return 1;
-}
-
-void init_traversal(struct traversal * traversal)
-{
- memset(traversal, 0, sizeof(*traversal));
-}
-
-/*
* Finds the base commit of a list of commits.
*
* One property of the commit being searched for is that every commit reachable
@@ -307,7 +213,7 @@ void init_traversal(struct traversal * t
* non-zero if, and only if, there was a problem parsing one of the
* commits discovered during the traversal.
*/
-static int find_base_for_list(struct commit_list *list, struct commit **boundary)
+int find_base_for_list(struct commit_list *list, struct commit **boundary)
{
int ret = 0;
struct commit_list *cleaner = NULL;
@@ -320,10 +226,10 @@ static int find_base_for_list(struct com
struct commit *item = list->item;
ASSERT(!item->object.util, "no duplicates in list", item);
- new_mass_counter(list->item, get_one());
+ new_mass_counter(item, get_one());
inc(&injected, get_one());
- commit_list_insert(list->item, &cleaner);
- commit_list_insert(list->item, &pending);
+ commit_list_insert(item, &cleaner);
+ commit_list_insert(item, &pending);
}
while (!*boundary && pending && !ret) {
struct commit *latest = pop_commit(&pending);
@@ -378,7 +284,7 @@ static int find_base_for_list(struct com
* Finds the base of an minimal, non-linear epoch, headed at head, by
* applying the find_base_for_list to a list consisting of the parents
*/
-static int find_base(struct commit *head, struct commit **boundary)
+int find_base(struct commit *head, struct commit **boundary)
{
int ret = 0;
struct commit_list *pending = NULL;
@@ -397,7 +303,7 @@ static int find_base(struct commit *head
* 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.
*/
-static int find_next_epoch_boundary(struct commit *head_of_epoch, struct commit **boundary)
+int find_next_epoch_boundary(struct commit *head_of_epoch, struct commit **boundary)
{
struct commit *item = head_of_epoch;
int ret;
@@ -424,290 +330,3 @@ static int find_next_epoch_boundary(stru
}
return ret;
}
-
-/*
- * Sort the epoch in (adjusted) merge order.
- */
-static void sort_unvisited(
- struct commit *head,
- struct commit_list **stack,
- struct traversal * traversal)
-{
- struct commit_list *parents = NULL;
- struct commit * top = *stack?(*stack)->item:NULL;
-
- if (IS_SEEN(head)) {
- if (!IS_BASE(head)) {
- visit_commit(traversal, head, 0);
- }
- return;
- }
- head->object.flags |= SEEN;
- if (IS_BASE(head)) {
- ASSERT(!top, "stack empty on visit to base", head);
- } else {
- if (!head->object.util) {
- parents = copy_parents_in_header_order(head);
- } else {
- parents = (struct commit_list *)head->object.util;
- head->object.util = NULL;
- }
- visit_commit(traversal, head, 1);
- while (parents) {
- struct commit *parent = pop_commit(&parents);
-
- visit_edge(traversal, head, parent);
- sort_unvisited(parent, stack, traversal);
- }
- commit_list_insert(head, stack);
- }
-}
-
-/*
- * Emit the contents of the stack.
- * The stack is freed and replaced by NULL.
- * Sets the return value to STOP if the traversal should stop.
- */
-static int emit_stack(struct commit_list **stack, struct traversal * traversal)
-{
- int stop = 0;
-
- while (*stack) {
- struct commit *next = pop_commit(stack);
-
- stop = stop || (emit_commit(traversal, next)==STOP);
- clean_commit(traversal, next);
- }
- return stop ? STOP : CONTINUE;
-}
-
-/*
- * Copy the parents of the commit and store the head of the list
- * in object.util. Return the address of object.util itself.
- */
-static struct commit_list ** copy_and_store_parents(struct commit * commit)
-{
- struct commit_list * copied=copy_parents_in_header_order(commit);
-
- commit->object.util = copied;
- return (struct commit_list **)&commit->object.util;
-}
-
-/*
- * Sort a list of commits in local first order. A commit is "local"
- * if any of its ancestors (except the base) causes (*local_test)() to
- * return a non-zero value.
- *
- * The sorted list is returned in *sorted. A side effect of this function
- * is to set each object.util pointer in each ancestor up until the base
- * to a list of parents is sorted in local first order.
- *
- * Does nothing if the list is empty.
- *
- * The return value contains LOCAL if any of the list is local or had a
- * local ancestor.
- */
-static unsigned int sort_local_branches_first(struct commit_list ** list, struct traversal * traversal)
-{
- struct commit_list *local = NULL;
- struct commit_list **local_tail = &local;
- struct commit_list **non_local_ptr;
-
- ASSERT(traversal->local_test, "local_test method is defined", NULL);
- if (!*list) {
- return 0;
- }
- for (non_local_ptr = list; *non_local_ptr; ) {
- struct commit *item = (*non_local_ptr)->item;
-
- /*
- * We don't descend past the base or visit
- * a commit we have already visited.
- */
- if (!IS_BASE(item) && !item->object.util) {
- struct commit_list ** copied;
-
- if ((*(traversal->local_test)) (item))
- item->object.flags |= LOCAL;
- copied=copy_and_store_parents(item);
- item->object.flags
- |= sort_local_branches_first(copied, traversal);
- }
- /**
- * Move local items onto their own list.
- */
- if (IS_LOCAL(item))
- local_tail = move_commit(local_tail, non_local_ptr);
- else
- non_local_ptr = &(*non_local_ptr)->next;
- }
- /*
- * Splice the non-local list onto the end of the local
- * list, set head of the list to the head of the local list
- * return if the LOCAL flag set if we have any local branches
- */
- *local_tail = *list;
- *list = local;
- return ((*list)->item->object.flags & LOCAL);
-}
-
-/*
- * Sorting a maximal linear epoch involves traversing until we
- * reach the base and emitting as we go. We don't emit the base
- * now.
- */
-static int sort_maximal_linear_epoch(struct commit *head, struct traversal * traversal)
-{
- struct commit * next;
- int stop = 0;
-
- /* invoke the visitors, if any */
- if (traversal->commit_visitor || traversal->edge_visitor) {
- for (next = head; !IS_BASE(next); next = next->parents->item) {
- visit_commit(traversal, next, 1);
- visit_edge(traversal, next, next->parents->item);
- }
- }
- /* now emit the nodes, and mark the base*/
- for (next = head; !IS_BASE(next); next = next->parents->item) {
- stop = stop || (emit_commit(traversal, next)==STOP);
- clean_commit(traversal, next);
- }
- return stop ? STOP : CONTINUE;
-}
-
-/*
- * Sorting a minimal non-linear epoch involves recursively apply
- * sort_unvisited after doing a local_branches_first sort to the
- * parents of each commit in the epoch, if required, then emitting
- * the stack.
- */
-static int sort_minimal_non_linear_epoch(struct commit *head, struct traversal * traversal)
-{
- struct commit_list *stack = NULL;
-
- if (traversal->local_test)
- sort_local_branches_first(copy_and_store_parents(head), traversal);
- sort_unvisited(head, &stack, traversal);
- return emit_stack(&stack, traversal);
-}
-
-/*
- * see epoch.h
- */
-int traverse_from_head(struct commit *head, struct traversal * traversal)
-{
- struct commit *next = head;
- int ret = 0;
-
- ret = parse_commit(next);
- if (ret)
- return ret;
- next->object.flags |= BOUNDARY;
- while (next && next->parents && continue_traversal(traversal, next)) {
- struct commit *base = NULL;
- int next_action = CONTINUE;
-
- /* scan to the base of the current epoch */
- ret = find_next_epoch_boundary(next, &base);
-
- /* abort if we detected a parsing error */
- if (ret)
- return ret; /* parsing failure */
-
- /* mark the new base so we know when to stop sorting */
- if (base)
- base->object.flags |= (BOUNDARY|BASE);
-
- /* reset flags set by last iteration */
- next->object.flags &= ~(BASE|SEEN);
-
- /* sort with the optimal algorithm */
- if (HAS_EXACTLY_ONE_PARENT(next))
- next_action = sort_maximal_linear_epoch(next, traversal);
- else
- next_action = sort_minimal_non_linear_epoch(next, traversal);
-
- /* stop or iterate */
- if (next_action == STOP)
- return 0;
- else
- next = base;
- }
- if (next) {
- emit_commit(traversal, next);
- clean_commit(traversal, next);
- }
- return 0;
-}
-
-/*
- * see epoch.h
- * Traverses the nodes reachable from a starting list in merge order, we
- * first find the base for the starting list and then sort all nodes
- * in this subgraph using the sort_unvisited algorithm. Once we have
- * reached the base we can continue sorting using traverse_from_head.
- */
-int traverse_from_list(struct commit_list *list, struct traversal * traversal)
-{
- struct commit_list *stack = NULL;
- struct commit *base;
- int ret = 0;
-
- if (!traversal)
- die("traversal argument must not be null");
- if (!traversal->emitter)
- die("an emitter method must be supplied");
- if (list->next) {
- struct commit_list * copy=NULL;
-
- /*
- * Make a copy of the list we can sort.
- */
- for(;list;list=list->next) {
- commit_list_insert(list->item, ©);
- }
- list=copy;
-
- /*
- * With multiple items to start the search with,
- * we first sort the list into local order (if required)
- *
- * This behaves as if a commit was performed which
- * referenced the list as parents. This
- * would create a minimal, non-linear epoch.
- */
- ret = find_base_for_list(list, &base);
- if (ret)
- return ret; /* parsing failure */
-
- /* mark the termination condition*/
- if (base)
- base->object.flags |= (BOUNDARY|BASE);
-
- /* sort local branches first, so they print last */
- if (traversal->local_test)
- sort_local_branches_first(&list, traversal);
-
- /* sort the unvisited part of the epoch in merge order */
- while (list)
- sort_unvisited(pop_commit(&list), &stack, traversal);
-
- /* output the stack */
- if (emit_stack(&stack, traversal) == STOP)
- return STOP;
- } else {
- /*
- * With only one item on the list, we just use
- * sort in merge order which handles maximal
- * linear epochs as well as minimal, non-linear epochs.
- */
- base = list->item;
- }
-
- /* sort the rest with the sort_in_merge_order algorithm. */
- if (base)
- ret = traverse_from_head(base, traversal);
- return ret;
-}
-
diff --git a/epoch.h b/epoch.h
--- a/epoch.h
+++ b/epoch.h
@@ -1,91 +1,38 @@
+/*
+ * 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.
+ *
+ */
#ifndef EPOCH_H
#define EPOCH_H
-/**
- * Flags used by merge order logic and also by rev-list.c
- */
-#define SEEN (1u<<0)
-#define BOUNDARY (SEEN<<1)
-#define LOCAL (BOUNDARY<<1)
-#define BASE (LOCAL<<1)
-#define LAST_TRAVERSAL_FLAG (BASE)
-
-#define TRAVERSAL_FLAGS (BOUNDARY|SEEN|LOCAL|BASE)
-
-/**
- * Return codes for emitter method. Also used by rev-list.c
- */
-#define STOP 0
-#define CONTINUE 1
-#define DO 2
-
-struct traversal {
- /*
- * Returns 0 if traversal should stop, non-zero if it should continue.
- */
- int (*emitter)(struct commit *);
-
- /*
- * Returns non-zero if the commit is regarded "local", 0 otherwise.
- */
- int (*local_test)(struct commit *);
-
- /*
- * If defined, called on each visit to a vertex during the
- * sort phase of the traversal. first_visit will be
- * non-zero on the first visit, zero otherwise.
- *
- * object.util is available for use by the visitor.
- */
- void (*commit_visitor)(struct commit *, int first_visit);
-
- /*
- * Called at some point prior to visiting 'to' from 'from'.
- * commit_visitor will already have been called at least once for
- * from node. It may or may not have already been called for the
- * to node.
- */
- void (*edge_visitor)(struct commit * from, struct commit * to);
+#include "cache.h"
- /*
- * Called sometime after the emitter function has been called.
- * Once this call completes the object.util pointer will be set to NULL.
- * Implementers should use this call to free any data structure
- * allocated by the commit_visitor method.
- */
- void (*clean)(struct commit *);
+#define HAS_EXACTLY_ONE_PARENT(n) ((n)->parents && !(n)->parents->next)
- /*
- * Called at each epoch boundary. Implementers may return
- * non-zero if the traversal into the next epoch should
- * be stopped.
- */
- int (*continue_traversal)(struct commit *);
-}
-;
-
-/**
- * Initializes a traversal structure which
- * may be customized by the caller by overriding any of the method pointers.
+/*
+ * Find the next articulation point in the graph
*/
-extern void init_traversal(struct traversal *);
+int find_base_for_list(struct commit_list *list, struct commit **boundary);
-/**
- * Traverses the commit graph from the commits listed.
- *
- * The traversal is performed in (optionally localised) merge order
- * which is defined by invariants specified in Documentation/git-rev-list.txt
+/*
+ * Find the base of the minimal, non-linear epoch headed at head.
*
- * The tactics used during the traversal can be customized
- * by configuring the traversal structure with appropriately
- * defined method pointers.
-
+ * The base is the first articulation point of the graph reachable from head
+ * such that the only paths between the head and commits reachable from the
+ * base are paths that include the base itself.
*/
-extern int traverse_from_list(struct commit_list *list, struct traversal * traversal);
+int find_base(struct commit *head, struct commit **boundary);
-/**
- * Traverses the commit graph from the head commit listed. In other
- * respects, like traverse_from_list.
+/*
+ * Find the boundary of the next epoch in the unique epoch sequence
+ * for the graph reachable from head. This is either the
+ * end of the base of a minimal, non-linear epoch (if head has >1 parents)
+ * or the end of a maximal, linear epoch (if head has exactly 1 parent)
*/
-extern int traverse_from_head(struct commit *head, struct traversal * traversal);
-#endif /* EPOCH_H */
+int find_next_epoch_boundary(struct commit *head, struct commit **boundary);
+#endif /* EPOCH_H */
diff --git a/rev-list.c b/rev-list.c
--- a/rev-list.c
+++ b/rev-list.c
@@ -1,6 +1,6 @@
#include "cache.h"
#include "commit.h"
-#include "epoch.h"
+#include "traversal.h"
#include "user.h"
#define INTERESTING (LAST_TRAVERSAL_FLAG << 1)
diff --git a/traversal.c b/traversal.c
new file mode 100644
--- /dev/null
+++ b/traversal.c
@@ -0,0 +1,395 @@
+/*
+ * 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 "cache.h"
+#include "commit.h"
+#include "traversal.h"
+#include "epoch.h"
+
+#define IS_SEEN(c) ((c)->object.flags & SEEN)
+#define IS_BASE(c) ((c)->object.flags & BASE)
+#define IS_LOCAL(c) ((c)->object.flags & LOCAL)
+
+/* leave the assertions defined for now, maybe null def them later */
+#define ASSERT(x,m,c) if (!(x)) { assertion_failed(__LINE__, __FUNCTION__, m, c); } else {}
+
+static void assertion_failed(int line, char * function, char * message, struct commit * item)
+{
+ die( "%s:%d:%s: assertion_failed: %s: commit %s, flags %x",
+ __FILE__,
+ line,
+ function,
+ message,
+ item ? sha1_to_hex(item->object.sha1) : "[]",
+ item ? item->object.flags : 0xFFFFFFFF);
+}
+
+/*
+ * This function calls the supplied commit_visitor method, if there is one.
+ */
+static void visit_commit(struct traversal * traversal, struct commit * commit, int first_visit)
+{
+ /*
+ * pre-condition:
+ * first_visit => object.util == NULL
+ */
+ if (traversal->commit_visitor)
+ (*(traversal->commit_visitor))(commit, first_visit);
+}
+
+/*
+ * This function is called as each edge in the graph is identified. It
+ * will always be called after visit_commit(...,from, 1). No guarantees
+ * are offered about when this call will be made w.r.t. to the call
+ * to visit_commit(..., to, 1)
+ */
+static void visit_edge(struct traversal * traversal, struct commit * from, struct commit * to)
+{
+ /*
+ * pre-condition:
+ * from->object.flags & SEEN &&
+ * to->object.util => (to->object.flags & SEEN)
+ */
+ if (traversal->edge_visitor)
+ (*(traversal->edge_visitor))(from, to);
+}
+
+/*
+ * This function is called exactly once for each commit discovered during
+ * the merge order traversal. If it ever returns a non-zero value, the
+ * merge order traversal will not continue past the current epoch boundary.
+ * It may, however, continue to emit nodes up until the epoch boundary.
+ * It is the implementer's responsibility to perform output limiting if
+ * that is required.
+ */
+static int emit_commit(struct traversal * traversal, struct commit * commit)
+{
+ return (*(traversal->emitter))(commit);
+}
+
+/*
+ * Invoke a call back method to allow the tactics to release and storage
+ * allocated during a previous visit_commit or visit_edge call.
+ */
+static void clean_commit(struct traversal * traversal, struct commit * commit)
+{
+ if (traversal->clean)
+ (*(traversal->clean))(commit);
+ commit->object.util = NULL;
+ commit->object.flags &= ~(TRAVERSAL_FLAGS);
+ /*
+ * post-condition:
+ * commit->object.util == NULL && !(commit->object.flag & TRAVERSAL_FLAGS)
+ */
+}
+
+/**
+ * Ask the tactics if we should traverse into the epoch headed at head.
+ */
+static int continue_traversal(struct traversal * traversal, struct commit * head)
+{
+ if (traversal->continue_traversal)
+ return (*(traversal->continue_traversal))(head);
+ else
+ return 1;
+}
+
+void init_traversal(struct traversal * traversal)
+{
+ memset(traversal, 0, sizeof(*traversal));
+}
+
+/*
+ * Sort the epoch in (adjusted) merge order.
+ */
+static void sort_unvisited(
+ struct commit *head,
+ struct commit_list **stack,
+ struct traversal * traversal)
+{
+ struct commit_list *parents = NULL;
+ struct commit * top = *stack?(*stack)->item:NULL;
+
+ if (IS_SEEN(head)) {
+ if (!IS_BASE(head)) {
+ visit_commit(traversal, head, 0);
+ }
+ return;
+ }
+ head->object.flags |= SEEN;
+ if (IS_BASE(head)) {
+ ASSERT(!top, "stack empty on visit to base", head);
+ } else {
+ if (!head->object.util) {
+ parents = copy_parents_in_header_order(head);
+ } else {
+ parents = (struct commit_list *)head->object.util;
+ head->object.util = NULL;
+ }
+ visit_commit(traversal, head, 1);
+ while (parents) {
+ struct commit *parent = pop_commit(&parents);
+
+ visit_edge(traversal, head, parent);
+ sort_unvisited(parent, stack, traversal);
+ }
+ commit_list_insert(head, stack);
+ }
+}
+
+/*
+ * Emit the contents of the stack.
+ * The stack is freed and replaced by NULL.
+ * Sets the return value to STOP if the traversal should stop.
+ */
+static int emit_stack(struct commit_list **stack, struct traversal * traversal)
+{
+ int stop = 0;
+
+ while (*stack) {
+ struct commit *next = pop_commit(stack);
+
+ stop = stop || (emit_commit(traversal, next)==STOP);
+ clean_commit(traversal, next);
+ }
+ return stop ? STOP : CONTINUE;
+}
+
+/*
+ * Copy the parents of the commit and store the head of the list
+ * in object.util. Return the address of object.util itself.
+ */
+static struct commit_list ** copy_and_store_parents(struct commit * commit)
+{
+ struct commit_list * copied=copy_parents_in_header_order(commit);
+
+ commit->object.util = copied;
+ return (struct commit_list **)&commit->object.util;
+}
+
+/*
+ * Sort a list of commits in local first order. A commit is "local"
+ * if any of its ancestors (except the base) causes (*local_test)() to
+ * return a non-zero value.
+ *
+ * The sorted list is returned in *sorted. A side effect of this function
+ * is to set each object.util pointer in each ancestor up until the base
+ * to a list of parents is sorted in local first order.
+ *
+ * Does nothing if the list is empty.
+ *
+ * The return value contains LOCAL if any of the list is local or had a
+ * local ancestor.
+ */
+static unsigned int sort_local_branches_first(struct commit_list ** list, struct traversal * traversal)
+{
+ struct commit_list *local = NULL;
+ struct commit_list **local_tail = &local;
+ struct commit_list **non_local_ptr;
+
+ ASSERT(traversal->local_test, "local_test method is defined", NULL);
+ if (!*list) {
+ return 0;
+ }
+ for (non_local_ptr = list; *non_local_ptr; ) {
+ struct commit *item = (*non_local_ptr)->item;
+
+ /*
+ * We don't descend past the base or visit
+ * a commit we have already visited.
+ */
+ if (!IS_BASE(item) && !item->object.util) {
+ struct commit_list ** copied;
+
+ if ((*(traversal->local_test)) (item))
+ item->object.flags |= LOCAL;
+ copied=copy_and_store_parents(item);
+ item->object.flags
+ |= sort_local_branches_first(copied, traversal);
+ }
+ /**
+ * Move local items onto their own list.
+ */
+ if (IS_LOCAL(item))
+ local_tail = move_commit(local_tail, non_local_ptr);
+ else
+ non_local_ptr = &(*non_local_ptr)->next;
+ }
+ /*
+ * Splice the non-local list onto the end of the local
+ * list, set head of the list to the head of the local list
+ * return if the LOCAL flag set if we have any local branches
+ */
+ *local_tail = *list;
+ *list = local;
+ return ((*list)->item->object.flags & LOCAL);
+}
+
+/*
+ * Sorting a maximal linear epoch involves traversing until we
+ * reach the base and emitting as we go. We don't emit the base
+ * now.
+ */
+static int sort_maximal_linear_epoch(struct commit *head, struct traversal * traversal)
+{
+ struct commit * next;
+ int stop = 0;
+
+ /* invoke the visitors, if any */
+ if (traversal->commit_visitor || traversal->edge_visitor) {
+ for (next = head; !IS_BASE(next); next = next->parents->item) {
+ visit_commit(traversal, next, 1);
+ visit_edge(traversal, next, next->parents->item);
+ }
+ }
+ /* now emit the nodes, and mark the base*/
+ for (next = head; !IS_BASE(next); next = next->parents->item) {
+ stop = stop || (emit_commit(traversal, next)==STOP);
+ clean_commit(traversal, next);
+ }
+ return stop ? STOP : CONTINUE;
+}
+
+/*
+ * Sorting a minimal non-linear epoch involves recursively apply
+ * sort_unvisited after doing a local_branches_first sort to the
+ * parents of each commit in the epoch, if required, then emitting
+ * the stack.
+ */
+static int sort_minimal_non_linear_epoch(struct commit *head, struct traversal * traversal)
+{
+ struct commit_list *stack = NULL;
+
+ if (traversal->local_test)
+ sort_local_branches_first(copy_and_store_parents(head), traversal);
+ sort_unvisited(head, &stack, traversal);
+ return emit_stack(&stack, traversal);
+}
+
+/*
+ * see commit-graph.h
+ */
+int traverse_from_head(struct commit *head, struct traversal * traversal)
+{
+ struct commit *next = head;
+ int ret = 0;
+
+ ret = parse_commit(next);
+ if (ret)
+ return ret;
+ next->object.flags |= BOUNDARY;
+ while (next && next->parents && continue_traversal(traversal, next)) {
+ struct commit *base = NULL;
+ int next_action = CONTINUE;
+
+ /* scan to the base of the current epoch */
+ ret = find_next_epoch_boundary(next, &base);
+
+ /* abort if we detected a parsing error */
+ if (ret)
+ return ret; /* parsing failure */
+
+ /* mark the new base so we know when to stop sorting */
+ if (base)
+ base->object.flags |= (BOUNDARY|BASE);
+
+ /* reset flags set by last iteration */
+ next->object.flags &= ~(BASE|SEEN);
+
+ /* sort with the optimal algorithm */
+ if (HAS_EXACTLY_ONE_PARENT(next))
+ next_action = sort_maximal_linear_epoch(next, traversal);
+ else
+ next_action = sort_minimal_non_linear_epoch(next, traversal);
+
+ /* stop or iterate */
+ if (next_action == STOP)
+ return 0;
+ else
+ next = base;
+ }
+ if (next) {
+ emit_commit(traversal, next);
+ clean_commit(traversal, next);
+ }
+ return 0;
+}
+
+/*
+ * see commit-graph.h
+ *
+ * Traverses the nodes reachable from a starting list in merge order, we
+ * first find the base for the starting list and then sort all nodes
+ * in this subgraph using the sort_unvisited algorithm. Once we have
+ * reached the base we can continue sorting using traverse_from_head.
+ */
+int traverse_from_list(struct commit_list *list, struct traversal * traversal)
+{
+ struct commit_list *stack = NULL;
+ struct commit *base;
+ int ret = 0;
+
+ if (!traversal)
+ die("traversal argument must not be null");
+ if (!traversal->emitter)
+ die("an emitter method must be supplied");
+ if (list->next) {
+ struct commit_list * copy=NULL;
+
+ /*
+ * Make a copy of the list we can sort.
+ */
+ for(;list;list=list->next) {
+ commit_list_insert(list->item, ©);
+ }
+ list=copy;
+
+ /*
+ * With multiple items to start the search with,
+ * we first sort the list into local order (if required)
+ *
+ * This behaves as if a commit was performed which
+ * referenced the list as parents. This
+ * would create a minimal, non-linear epoch.
+ */
+ ret = find_base_for_list(list, &base);
+ if (ret)
+ return ret; /* parsing failure */
+
+ /* mark the termination condition*/
+ if (base)
+ base->object.flags |= (BOUNDARY|BASE);
+
+ /* sort local branches first, so they print last */
+ if (traversal->local_test)
+ sort_local_branches_first(&list, traversal);
+
+ /* sort the unvisited part of the epoch in merge order */
+ while (list)
+ sort_unvisited(pop_commit(&list), &stack, traversal);
+
+ /* output the stack */
+ if (emit_stack(&stack, traversal) == STOP)
+ return STOP;
+ } else {
+ /*
+ * With only one item on the list, we just use
+ * sort in merge order which handles maximal
+ * linear epochs as well as minimal, non-linear epochs.
+ */
+ base = list->item;
+ }
+
+ /* sort the rest with the sort_in_merge_order algorithm. */
+ if (base)
+ ret = traverse_from_head(base, traversal);
+ return ret;
+}
+
diff --git a/traversal.h b/traversal.h
--- a/traversal.h
+++ b/traversal.h
@@ -1 +1,91 @@
-/* workaround for git-apply issue */
+#ifndef TRAVERSAL_H
+#define TRAVERSAL_H
+
+/**
+ * Flags used by merge order logic and also by rev-list.c
+ */
+#define SEEN (1u<<0)
+#define BOUNDARY (SEEN<<1)
+#define LOCAL (BOUNDARY<<1)
+#define BASE (LOCAL<<1)
+#define LAST_TRAVERSAL_FLAG (BASE)
+
+#define TRAVERSAL_FLAGS (BOUNDARY|SEEN|LOCAL|BASE)
+
+/**
+ * Return codes for emitter method. Also used by rev-list.c
+ */
+#define STOP 0
+#define CONTINUE 1
+#define DO 2
+
+struct traversal {
+ /*
+ * Returns 0 if traversal should stop, non-zero if it should continue.
+ */
+ int (*emitter)(struct commit *);
+
+ /*
+ * Returns non-zero if the commit is regarded "local", 0 otherwise.
+ */
+ int (*local_test)(struct commit *);
+
+ /*
+ * If defined, called on each visit to a vertex during the
+ * sort phase of the traversal. first_visit will be
+ * non-zero on the first visit, zero otherwise.
+ *
+ * object.util is available for use by the visitor.
+ */
+ void (*commit_visitor)(struct commit *, int first_visit);
+
+ /*
+ * Called at some point prior to visiting 'to' from 'from'.
+ * commit_visitor will already have been called at least once for
+ * from node. It may or may not have already been called for the
+ * to node.
+ */
+ void (*edge_visitor)(struct commit * from, struct commit * to);
+
+ /*
+ * Called sometime after the emitter function has been called.
+ * Once this call completes the object.util pointer will be set to NULL.
+ * Implementers should use this call to free any data structure
+ * allocated by the commit_visitor method.
+ */
+ void (*clean)(struct commit *);
+
+ /*
+ * Called at each epoch boundary. Implementers may return
+ * non-zero if the traversal into the next epoch should
+ * be stopped.
+ */
+ int (*continue_traversal)(struct commit *);
+}
+;
+
+/**
+ * Initializes a traversal structure which
+ * may be customized by the caller by overriding any of the method pointers.
+ */
+extern void init_traversal(struct traversal *);
+
+/**
+ * Traverses the commit graph from the commits listed.
+ *
+ * The traversal is performed in (optionally localised) merge order
+ * which is defined by invariants specified in Documentation/git-rev-list.txt
+ *
+ * The tactics used during the traversal can be customized
+ * by configuring the traversal structure with appropriately
+ * defined method pointers.
+
+ */
+extern int traverse_from_list(struct commit_list *list, struct traversal * traversal);
+
+/**
+ * Traverses the commit graph from the head commit listed. In other
+ * respects, like traverse_from_list.
+ */
+extern int traverse_from_head(struct commit *head, struct traversal * traversal);
+#endif /* TRAVERSAL_H */
------------
^ permalink raw reply
* Re: [zooko@zooko.com: [Revctrl] colliding md5 hashes of human-meaningful documents]
From: Daniel Barkalow @ 2005-06-14 2:06 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Petr Baudis, git
In-Reply-To: <Pine.LNX.4.58.0506120949150.2286@ppc970.osdl.org>
On Sun, 12 Jun 2005, Linus Torvalds wrote:
> Put another way: you could use this exact example for a version of git
> that uses md5-sums instead of sha1's, but it wouldn't show anything at all
> about a git vulnerability even so.
You couldn't use this exact example for an md5 git; git compresses the
files before hashing, which means that you don't have an md5 block of
arbitrary data you can replace with a different arbitrary block because it
wouldn't decompress.
Of course, if zlib has a way of saying, "if bytes 256-511 match 512-767,
decompress the first of the two records starting at 768, otherwise
decompress the second" then the attack would work, and we should all by
worried (and disturbed by zlib in general). Chances are that it would be
impractical to find a pair of blocks such that they are both valid in the
same part of a zlib record and both leave the compression context such
that the same remaining content decompresses successfully and both have
the same md5 hash, let alone getting the results in both cases to be valid
C that depends on the difference between the blocks. It's possible that
you could get it to work with only a moderately large number of weak
collisions between very similar blocks, but it's not nearly so easy a
task.
-Daniel
*This .sig left intentionally blank*
^ permalink raw reply
* Re: [PATCH] Adding Correct Useage Notification and -h Help flag
From: Junio C Hamano @ 2005-06-14 2:23 UTC (permalink / raw)
To: purserj; +Cc: git
In-Reply-To: <1118713641.8712.10.camel@localhost.localdomain>
>>Added a couple of lines to the git wrapper. Includes Correct
>>Useage and available scripts
I like the general direction of making "git" wrapper novice
friendly, but have some suggestions to the implementation.
(0) Do not mention that only certain subset is accessible.
Just saying "Available commands are:" would be enough, and
would not leave the end user wondering what he is missing.
(1) Instead of explicitly checking for -h, you may want to
structure it like this:
#!/bin/sh
cmd="git-$1-script";
shift;
exec $cmd "$@";
echo "Usage: git <subcommand> [<param>...]"
echo 'Available commands are:"
git bar
git foo
...
'
exit 1
Alternatively, you could say:
#!/bin/sh
case "$1" in
-h)
echo "Usage: git <subcommand> [<param>...]"
echo 'Available commands are:
git bar
git foo
...
'
exit 0 ;;
esac
cmd="git-$1-script";
shift;
exec $cmd "$@";
git -h
exit 1
(2) Maintaining the list of commands by hand in git script
itself have an advantage that you _could_ describe the
options and parameters they take, but you are not doing
that in your patch (hint, hint).
If all you give is the list of subcommand names, have
git.in as a source file, and create the "list of available
commands" from the Makefile, like this:
=== Makefile ===
...
git : git.in
/bin/sh ls -1 git-*-script | \
sed -e 's/git-\(.*\)-script/git \1/' >.git-cmd-list
sed -e '/@@LIST_OF_COMMANDS@@/{s/.*//;r .git-cmd-list;}' <$@.in >$@
rm -f .git-cmd-list
=== git.in ===
#!/bin/sh
cmd="git-$1-script";
shift;
exec $cmd "$@";
echo "Usage: git <subcommand> [<param>...]"
echo 'Available commands are:
@@LIST_OF_COMMANDS@@
'
^ permalink raw reply
* Re: [zooko@zooko.com: [Revctrl] colliding md5 hashes of human-meaningfuldocuments]
From: Daniel Barkalow @ 2005-06-14 2:23 UTC (permalink / raw)
To: git; +Cc: Linus Torvalds, petr
On Mon, 13 Jun 2005, David Lang wrote:
> Daniel, I thought that git changed to hash the uncompressed data so that
> you don't spend the time compressing all the data just to find out what's
> already known.
That's right; never mind.
-Daniel
*This .sig left intentionally blank*
^ 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