* Re: [PATCH] Modify git-rev-list ... in merge order [ repost with bug fixes ]
From: Jon Seymour @ 2005-06-06 1:09 UTC (permalink / raw)
To: Linus Torvalds; +Cc: git
In-Reply-To: <Pine.LNX.4.58.0506051741190.1876@ppc970.osdl.org>
On 6/6/05, Linus Torvalds <torvalds@osdl.org> wrote:
>
>
> On Sun, 5 Jun 2005 jon@blackcubes.dyndns.org wrote:
> >
> > -static void show_commit(struct commit *commit)
> > +static int show_commit(struct commit *commit)
>
> Ick. You've mixed "show_commit()" to be three totally independent things
> - deciding whether to show at all
> - showing the commit in traditional format
> - showing the commit tree in the new "break" format
>
> I really hate functions that do totally unrelated things, and I'm so much
> happier with the new show_commit() than the old "everything in one big
> function" thing, that I'm unhappy about mixing the thing up again.
>
> Please leave show_commit() to just show the commit, and make the other
> decisions be independent of that.
My rationale was to re-use both the filtering logic currently in the
show_commit_list while loop and the display logic, since I need both
in order to maximise compatibility with the standard algorithm.
However, I understand your concerns.
My plan, therefore, is to split the filtering logic from
show_commit_list's while loop into a separate function and create a
third function which calls the filtering logic, then show_commit. I'll
pass a pointer to the third function to sort_list_in_merge_order. I
can leave the show_breaks functionality in show_commit (it is, after
all, display functionality) or I can move it into the third function.
Is that ok by you?
jon.
^ permalink raw reply
* Re: [PATCH] Modify git-rev-list ... in merge order [ repost with bug fixes ]
From: Linus Torvalds @ 2005-06-06 1:43 UTC (permalink / raw)
To: jon; +Cc: git
In-Reply-To: <2cfc4032050605180958fcf395@mail.gmail.com>
On Mon, 6 Jun 2005, Jon Seymour wrote:
>
> My rationale was to re-use both the filtering logic currently in the
> show_commit_list while loop and the display logic, since I need both
> in order to maximise compatibility with the standard algorithm.
It's obviously ok to re-use the filtering, I'm just objecting to putting
it into a function that is really unrelated to filtering..
> My plan, therefore, is to split the filtering logic from
> show_commit_list's while loop into a separate function and create a
> third function which calls the filtering logic, then show_commit.
Yes.
Linus
^ permalink raw reply
* Re: Last mile for 1.0
From: Thomas Glanzmann @ 2005-06-06 5:43 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Junio C Hamano, git
In-Reply-To: <Pine.LNX.4.58.0506051658100.1876@ppc970.osdl.org>
Hello,
> > - "What happens when a merge goes wrong" helper script Jeff
> > wanted to have in *4*.
> Does anybody have any suggestions? Preferably with a reasonable
> test-case, so that people can try it out.. Maybe just leaving the merge
> failures where they are?
I think the simplest and effectivies way to handle this is the
following: Add a flag to the current merge script which indicates that
on conflicts the user will be dropped to a shell per conflict to solve:
- Checkout filename.LOCAL, filename.REMOTE, filename.GCA (with
sanitychecks of course (eg not overwriting existing files)
- Run merga -A on them and maybe wiggle and write the product in
filename
- If the user resolves the conflict drop him a note to
'update-cache' the resolved conflict and exit the subshell.
I also have at the moment a very nice perl merge script which works with
multiple heads, duplicates and stuff. Maybe I should write this down in
bash.
The above approach worked out very good at least for me. I often had to
resolve 'simple' conflicts when pulling in upstream changes from Linus
repo.
Thomas
^ permalink raw reply
* Problem with Cogito repository?
From: Philip Pokorny @ 2005-06-06 6:08 UTC (permalink / raw)
To: Git Mailing List
I've just updated my tree with cg-pull from
rsync://rsync.kernel.org/pub/scm/cogito/cogito.git
There seems to be a problem with the repository object for tag
"pull_from_pasky"
[philip@xray cogito]$ git-fsck-cache
bad sha1 entry '11ed64c1b141c9ba397a1ca76aef2cd250976007'
error: .git/refs/tags/pull_from_pasky: invalid sha1 pointer
11ed64c1b141c9ba397a1ca76aef2cd250976007
And in fact 11ed64... _is_ bad:
[philip@xray cogito]$ ls -l
.git/objects/11/ed64c1b141c9ba397a1ca76aef2cd250976007
-rw-r--r-- 1 philip philip 0 Jun 5 22:58
.git/objects/11/ed64c1b141c9ba397a1ca76aef2cd250976007
Note the files is 0 bytes in size.
Or am I doing something wrong?
^ permalink raw reply
* Re: Last mile for 1.0
From: Linus Torvalds @ 2005-06-06 6:13 UTC (permalink / raw)
To: Thomas Glanzmann; +Cc: Junio C Hamano, git
In-Reply-To: <20050606054356.GB3669@cip.informatik.uni-erlangen.de>
On Mon, 6 Jun 2005, Thomas Glanzmann wrote:
>
> I think the simplest and effectivies way to handle this is the
> following: Add a flag to the current merge script which indicates that
> on conflicts the user will be dropped to a shell per conflict to solve:
Well, there was actually a much more fundamental problem, which is that
the merge script depended on being able to do
git-checkout-cache -f -u -a
which in turn obviously meant that _whatever_ it did, it would end up
overwriting any dirty state in the working tree.
And you can't remove the git-checkout-cache, because after the merge we've
lost the original state anyway, so there's no way to know whether whatever
you had in the working directory was dirty or not.
So I've actually been working now to make the very low-level git-read-tree
Do The Right Thing (tm), and I think I'm getting there. It basically
depends on "git-read-tree" noticing when the state is dirty enough that we
can't safely do the merge, and then for the safe cases it can actually
update anything it merged properly. As a result, there's never any need
for git-checkout-cache, and the only thing that needs updating in the
working directory is the stuff that we end up merging by hand _outside_ of
git-read-tree.
There's two cases: fast-forward and a real merge. And the thing is, to do
even just the fast-forward safely, it actually needs to know what the base
tree was (otherwise it can only tell that the file was up-to-date in the
index, but it can't know whether the index actually matched the original
HEAD..). So now the fast-forward case is actually a two-way merge:
git-read-tree -u -m HEAD NEW_HEAD
where "-u" stands for "update", and tells read-tree that it should check
out the files it merges up.
And now git-read-tree also tries to be very careful: if one of the files
that needs to be updated is already dirty, or it doesn't match the
original HEAD, then git-read-tree will just exit with an error and not do
anything at all.
But for a file that wasn't touched at all by the merge, we can leave it
dirty in the index, since whatever dirty index state was valid before the
merge is obviously valid after it too. So now you can have dirty state in
your tree, and merges will complain only if it matters to them.
Same goes for the (much more complex) three-way merge, of course. There
the rules are a bit more complicated, and I'll have to double-check this
thing, but it all looks like even if the current state might be buggy, the
basic _notion_ looks fine.
So now we have a one-way merge for "just update to this tree", a two-way
merge for "update from this tree to that tree", and a three-way merge for
"merge these two trees with that third tree as a base".
By now, I'd really like to have some test-cases. Things like "file dirty
in working directory, removed by merge" would be good.
And the "git-merge-one-file-script" thing needs to be updated to keep the
tree updated as it merges things by hand, since it can't depend on the
git-checkout-cache fixing things up any more. Anybody?
Linus
^ permalink raw reply
* Re: Last mile for 1.0
From: Junio C Hamano @ 2005-06-06 6:35 UTC (permalink / raw)
To: Linus Torvalds; +Cc: git
In-Reply-To: <Pine.LNX.4.58.0506052300350.1876@ppc970.osdl.org>
>>>>> "LT" == Linus Torvalds <torvalds@osdl.org> writes:
LT> And the "git-merge-one-file-script" thing needs to be updated to keep the
LT> tree updated as it merges things by hand, since it can't depend on the
LT> git-checkout-cache fixing things up any more. Anybody?
I'd love to bite. One problem I have been having for the last
30 minutes or so is that t1000 test (merge from h*ll) does not
show that read-tree resolving even the trivial ones anymore, and
I do not know if you want make it that the responsibility of
git-merge-one-file-script, or if it is just an oversight.
I might have leave that to Europeans, though, due to timezone
differences ;-).
^ permalink raw reply
* Re: Last mile for 1.0
From: Linus Torvalds @ 2005-06-06 6:44 UTC (permalink / raw)
To: Junio C Hamano; +Cc: git
In-Reply-To: <7vpsv0uh5d.fsf@assigned-by-dhcp.cox.net>
On Sun, 5 Jun 2005, Junio C Hamano wrote:
> >>>>> "LT" == Linus Torvalds <torvalds@osdl.org> writes:
>
> LT> And the "git-merge-one-file-script" thing needs to be updated to keep the
> LT> tree updated as it merges things by hand, since it can't depend on the
> LT> git-checkout-cache fixing things up any more. Anybody?
>
> I'd love to bite. One problem I have been having for the last
> 30 minutes or so is that t1000 test (merge from h*ll) does not
> show that read-tree resolving even the trivial ones anymore, and
> I do not know if you want make it that the responsibility of
> git-merge-one-file-script, or if it is just an oversight.
It was just two really stupid bugs, both due to me trying to make the
three different merge loops look a bit more like each other, and that had
broken the three-way case in two different ways.
Should be fixed, as soon as the mirroring pushes out the last off-by-one
fix.
Linus
^ permalink raw reply
* Re: Last mile for 1.0
From: Thomas Glanzmann @ 2005-06-06 6:44 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Junio C Hamano, git
In-Reply-To: <Pine.LNX.4.58.0506052300350.1876@ppc970.osdl.org>
Hello,
> Well, there was actually a much more fundamental problem, which is that
> the merge script depended on being able to do
> git-checkout-cache -f -u -a
> which in turn obviously meant that _whatever_ it did, it would end up
> overwriting any dirty state in the working tree.
true. But I don't see the problem. Just ensure that there are no
uncommitted data and no dirty files before proceeding with the merge by
calling:
git-diff-files -z -r (but ignore the deleted)
git-diff-cache -r --cached HEAD
> And you can't remove the git-checkout-cache, because after the merge we've
> lost the original state anyway, so there's no way to know whether whatever
> you had in the working directory was dirty or not.
> So I've actually been working now to make the very low-level git-read-tree
> Do The Right Thing (tm), and I think I'm getting there. It basically
> depends on "git-read-tree" noticing when the state is dirty enough that we
> can't safely do the merge, and then for the safe cases it can actually
> update anything it merged properly. As a result, there's never any need
> for git-checkout-cache, and the only thing that needs updating in the
> working directory is the stuff that we end up merging by hand _outside_ of
> git-read-tree.
> There's two cases: fast-forward and a real merge. And the thing is, to do
> even just the fast-forward safely, it actually needs to know what the base
> tree was (otherwise it can only tell that the file was up-to-date in the
> index, but it can't know whether the index actually matched the original
> HEAD..). So now the fast-forward case is actually a two-way merge:
> git-read-tree -u -m HEAD NEW_HEAD
> where "-u" stands for "update", and tells read-tree that it should check
> out the files it merges up.
> And now git-read-tree also tries to be very careful: if one of the files
> that needs to be updated is already dirty, or it doesn't match the
> original HEAD, then git-read-tree will just exit with an error and not do
> anything at all.
Now I see your point. And a cmp-and-xchg HEAD would be useful here, too. What
if a user tries to shoot himself in the head by pull from two trees
simultaneous?
> But for a file that wasn't touched at all by the merge, we can leave it
> dirty in the index, since whatever dirty index state was valid before the
> merge is obviously valid after it too. So now you can have dirty state in
> your tree, and merges will complain only if it matters to them.
Nice to have. :-)
> ...
> And the "git-merge-one-file-script" thing needs to be updated to keep the
> tree updated as it merges things by hand, since it can't depend on the
> git-checkout-cache fixing things up any more. Anybody?
I can't follow you there. AFAIK it retrieves all his files from
git-merge-cache and just calls git-update-cache to update the index.
Thomas
^ permalink raw reply
* Re: Last mile for 1.0
From: Junio C Hamano @ 2005-06-06 6:45 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Thomas Glanzmann, git
In-Reply-To: <Pine.LNX.4.58.0506052300350.1876@ppc970.osdl.org>
>>>>> "LT" == Linus Torvalds <torvalds@osdl.org> writes:
LT> By now, I'd really like to have some test-cases. Things like "file dirty
LT> in working directory, removed by merge" would be good.
Is test 44 in t1000 (the first one in t1000 after the lib-
read-tree-m-3way prepares the test trees) good enough? Or do
you want more specific tests to make sure the logic catches
individual cases right?
^ permalink raw reply
* Re: Last mile for 1.0
From: Linus Torvalds @ 2005-06-06 6:57 UTC (permalink / raw)
To: Thomas Glanzmann; +Cc: Junio C Hamano, git
In-Reply-To: <20050606064456.GC3669@cip.informatik.uni-erlangen.de>
On Mon, 6 Jun 2005, Thomas Glanzmann wrote:
>
> true. But I don't see the problem. Just ensure that there are no
> uncommitted data and no dirty files before proceeding with the merge by
> calling:
The thing is, I historically _often_ have uncommitted data, and it's been
one of the biggest bummers for me that a merge of a totally unrelated
thing will crap all over my debugging patch..
> > And now git-read-tree also tries to be very careful: if one of the files
> > that needs to be updated is already dirty, or it doesn't match the
> > original HEAD, then git-read-tree will just exit with an error and not do
> > anything at all.
>
> Now I see your point. And a cmp-and-xchg HEAD would be useful here, too. What
> if a user tries to shoot himself in the head by pull from two trees
> simultaneous?
If he uses the same index file, he'll be protected by the index lock.
> > And the "git-merge-one-file-script" thing needs to be updated to keep the
> > tree updated as it merges things by hand, since it can't depend on the
> > git-checkout-cache fixing things up any more. Anybody?
>
> I can't follow you there. AFAIK it retrieves all his files from
> git-merge-cache and just calls git-update-cache to update the index.
Not exactly. It updates the index directly, without necessarily updating
the working directory. For example:
"$1.." | "$1.$1" | "$1$1.")
echo "Removing $4"
exec git-update-cache --force-remove "$4" ;;
it _says_ "removing $4", but it never actually does so, so the working
directory still has the file ;)
Same goes with added files or even updated files, where it uses
"--cacheinfo" to update the cache without even touching the working
directory.
Anyway, git-resovle-script needs to be made to use "git-merge-cache -o"
too, methinks. And it needs a test-case or two.
Linus
^ permalink raw reply
* Re: Last mile for 1.0
From: Linus Torvalds @ 2005-06-06 7:03 UTC (permalink / raw)
To: Junio C Hamano; +Cc: Thomas Glanzmann, git
In-Reply-To: <7vis0sugp7.fsf@assigned-by-dhcp.cox.net>
On Sun, 5 Jun 2005, Junio C Hamano wrote:
>
> Is test 44 in t1000 (the first one in t1000 after the lib-
> read-tree-m-3way prepares the test trees) good enough? Or do
> you want more specific tests to make sure the logic catches
> individual cases right?
I was more thinking of all the individual cases, and also the 2-way merge
issue (which _should_ be a lot easier, but hey, I had tons of bugs there
too).
For example, what should happen if you do a merge and you have a file in
the index that isn't mentioned by any of the trees involved. I consider
that a failure, since the merge will remove the file, and since it wasn't
committed, it's now a "data lost" issue. But did I actually get it right?
I have no idea.
Linus
^ permalink raw reply
* Re: Last mile for 1.0
From: Thomas Glanzmann @ 2005-06-06 7:01 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Junio C Hamano, git
In-Reply-To: <Pine.LNX.4.58.0506052351470.1876@ppc970.osdl.org>
Hello,
> The thing is, I historically _often_ have uncommitted data, and it's been
> one of the biggest bummers for me that a merge of a totally unrelated
> thing will crap all over my debugging patch..
got the point. I useally work like that, too. But I never did it with a
distributed SCM just with CVS.
> If he uses the same index file, he'll be protected by the index lock.
I see.
> Not exactly. It updates the index directly, without necessarily updating
> the working directory. For example:
> "$1.." | "$1.$1" | "$1$1.")
> echo "Removing $4"
> exec git-update-cache --force-remove "$4" ;;
> it _says_ "removing $4", but it never actually does so, so the working
> directory still has the file ;)
> Same goes with added files or even updated files, where it uses
> "--cacheinfo" to update the cache without even touching the working
> directory.
Now I see your point.
> Anyway, git-resovle-script needs to be made to use "git-merge-cache
> -o" too, methinks. And it needs a test-case or two.
Yes, it does. In my merge script in perl it already does that. :-)
Thomas
^ permalink raw reply
* Re: Last mile for 1.0
From: Junio C Hamano @ 2005-06-06 7:05 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Thomas Glanzmann, git
In-Reply-To: <Pine.LNX.4.58.0506052351470.1876@ppc970.osdl.org>
>>>>> "LT" == Linus Torvalds <torvalds@osdl.org> writes:
LT> Not exactly. It updates the index directly, without necessarily updating
LT> the working directory. For example:
LT> "$1.." | "$1.$1" | "$1$1.")
LT> echo "Removing $4"
LT> exec git-update-cache --force-remove "$4" ;;
LT> it _says_ "removing $4", but it never actually does so, so the working
LT> directory still has the file ;)
Yes, this was done from your explicit request not to touch the
working directory while it works AFAICR. At least back then,
not touching the working tree was the _requirement_.
So is "the new merge world order" you mentioned in the log
message now require (and assume) the work tree more-or-less
matches the first head being merged?
^ permalink raw reply
* [PATCH] Factor out filtering in rev-list.c
From: jon @ 2005-06-06 7:17 UTC (permalink / raw)
To: git; +Cc: jon.seymour, torvalds
[PATCH] Factor out filtering in rev-list.c
This patch:
* factors out the filtering logic in show_commit_list into filter_commit.
* groups calls to filter_commit and show_commit into process_commit.
* replaces the body of the show_commit_list while loop with a call to process_commit.
* fixes a compiler warning by adding a return statement to get_commit_format.
The purpose of these changes is to faciliate a future merge with Jon Seymour's --merge-order patch which
will pass pointer to process_commit to another module.
Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
This patch can also be downloaded from: http://blackcubes.dyndns.org/epoch/rev-list.patch .
Diverged from 000182eacf99cde27d5916aa415921924b82972c by Linus Torvalds <torvalds@ppc970.osdl.org>
---
diff --git a/rev-list.c b/rev-list.c
--- a/rev-list.c
+++ b/rev-list.c
@@ -40,20 +40,48 @@ static void show_commit(struct commit *c
}
}
+#define STOP 0
+#define CONTINUE 1
+#define DO 2
+
+static int filter_commit(struct commit * commit)
+{
+ if (commit->object.flags & UNINTERESTING)
+ return CONTINUE;
+ if (min_age != -1 && (commit->date > min_age))
+ return CONTINUE;
+ if (max_age != -1 && (commit->date < max_age))
+ return STOP;
+ if (max_count != -1 && !max_count--)
+ return STOP;
+
+ return DO;
+}
+
+static int process_commit(struct commit * commit)
+{
+ int action=filter_commit(commit);
+
+ if (action == STOP) {
+ return STOP;
+ }
+
+ if (action == CONTINUE) {
+ return CONTINUE;
+ }
+
+ show_commit(commit);
+
+ return CONTINUE;
+}
+
static void show_commit_list(struct commit_list *list)
{
while (list) {
struct commit *commit = pop_most_recent_commit(&list, SEEN);
- if (commit->object.flags & UNINTERESTING)
- continue;
- if (min_age != -1 && (commit->date > min_age))
- continue;
- if (max_age != -1 && (commit->date < max_age))
+ if (process_commit(commit) == STOP)
break;
- if (max_count != -1 && !max_count--)
- break;
- show_commit(commit);
}
}
@@ -110,6 +138,8 @@ static enum cmit_fmt get_commit_format(c
if (!strcmp(arg, "=short"))
return CMIT_FMT_SHORT;
usage(rev_list_usage);
+
+ return CMIT_FMT_DEFAULT;
}
^ permalink raw reply
* new read-tree questions.
From: Junio C Hamano @ 2005-06-06 8:43 UTC (permalink / raw)
To: Linus Torvalds; +Cc: git
I am trying to understand the new git-read-tree, by using
git-resolve-script as an example and also reading read-tree.c; I
am somewhat confused.
* two-way merge (git-read-tree -m $H $M)
My understanding is that the current index is allowed to be
empty, but if it is not, they are kept at stage0, and each of
them must match $H and must be up-to-date if the merge involves
them.
To summarize my understanding of what should happen for each
path:
stage0 (index) stage1 ($H) stage2 ($M)
------------------------------------------------------------
no such path no such path no such path
* this does not happen (the code would not see such thing).
----------------------------------------------------------
no such path no such path exists
* take $M without complaining.
----------------------------------------------------------
no such path exists (does not matter) *0*
* although index does not match $H, we do not reject, so
that a merge can happen on an empty cache. We take $M.
----------------------------------------------------------
exists no such path no such path
* reject, because index does not match $H.
----------------------------------------------------------
exists no such path exists (index!=$M)
* reject, because index does not match $H.
----------------------------------------------------------
exists no such path exists (index=$M) *1*
* take $M (same as "keep stage0").
----------------------------------------------------------
exists exists (index!=$H) (does not matter)
* reject, because index does not match $H.
----------------------------------------------------------
exists exists (index=$H) no such path *2*
* path is removed.
----------------------------------------------------------
exists exists (index=$H) exists
* take stage2.
----------------------------------------------------------
Does the above matrix represent the intended behaviour?
I think I understand why we would want *0*, but this asymmetry
feels wrong.
I am having trouble with the case *1*. This would call
twoway_check with !seen_stage1 and it says OK, because the
merged tree has the same contents as what we started with. Is
it to help the case where" the merged tree changes things the
same way we already have as our local change" case?
Also I am not sure if the code does the right thing for case
*2*. If I am reading the code right, for such a path, we will
see stage0 and stage1, and at that point say seen_stage1 = 1 and
keep stage0 entry in "old". Then we continue on to the next
path. When it happens to be:
- stage0: we barf because we still have our "old".
- stage1: we barf because our "old" does not match the new
path; !path_matches(old,ce) triggers.
- stage2: we barf because our "old" does not match the new
path; twoway_check(old, seen_stage1, ce) triggers.
Only when such a "exists-exists-removed" were the last entry,
the control falls out of the loop and "unmatched with a new
entry?" check takes care of it without barfing. The path is
removed which is what I understand you want to happen in the
case *2*.
Maybe my version of intended behaviour for case *2* is wrong,
but then I do not understand why.
I'll do a similar matrix for three-way merge case later and
probably ask more questions.
^ permalink raw reply
* Re: Last mile for 1.0
From: McMullan, Jason @ 2005-06-06 13:29 UTC (permalink / raw)
To: Junio C Hamano; +Cc: GIT Mailling list
In-Reply-To: <7vzmu4weod.fsf@assigned-by-dhcp.cox.net>
[-- Attachment #1: Type: text/plain, Size: 989 bytes --]
On Sun, 2005-06-05 at 16:45 -0700, Junio C Hamano wrote:
> I did not mention git-sync by Jason McMullan on my list of "what
> I want to have in 1.0", but that was not because I object to the
> idea of having a sync mechanism that knows and takes advantage
> of how GIT works. Quite the contrary.
>
> [snip snip]
>
> I just do not feel, judging from its current protocol command
> set, it offers enough improvements over what git-ssh-push/pull
> pairs already give us; I'd be happy to be corrected, of course,
> if this is a misconception.
Oh, I definitely agree. git-sync is *not* 1.0 material. The protocol
and feature set are still being worked on, and git-ssh-* may even
be a better fix than git-sync for many scenarios.
What I *do* want to get into git 1.0 is a merge of git-sync's
verify-before-write update semantics into pull.c. I should be
able to get that to you before tomorrow.
--
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
* Database consistency after a successful pull
From: McMullan, Jason @ 2005-06-06 13:50 UTC (permalink / raw)
To: Daniel Barkalow; +Cc: Junio C Hamano, Linus Torvalds, GIT Mailling list
In-Reply-To: <Pine.LNX.4.21.0506051523280.30848-100000@iabervon.org>
[-- Attachment #1: Type: text/plain, Size: 1146 bytes --]
Subject Was: [PATCH] pull: gracefu[PAlly recover from delta retrieval
failure.]
[snip lots of really good information about the thinking
behind the design of the pull mechanisms ]
Ok, so would I be correct in the following assumptions
about the validity of a 'consistent' .git/objects database:
============================================================
Commits:
* May have the tree they refer to in the database
* Must have their parents in the database
Trees:
* Must have the blobs they refer to in the database
* Must have the trees they refer to in the database
Deltas:
* Must have the referred to object in the database
Blobs:
* No references to check
============================================================
In short, the database would contain:
* The entire commit history
* Selected commits would have the entire tree available
Correct, or totally mistaken? If mistaken, what are the consitency
rules?
[Oh, and does PGP signing my messages bug anybody? If so, I can stop
doing that on this list]
--
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: Last mile for 1.0
From: Linus Torvalds @ 2005-06-06 14:37 UTC (permalink / raw)
To: Junio C Hamano; +Cc: Thomas Glanzmann, git
In-Reply-To: <7vekbgufra.fsf@assigned-by-dhcp.cox.net>
On Mon, 6 Jun 2005, Junio C Hamano wrote:
>
> Yes, this was done from your explicit request not to touch the
> working directory while it works AFAICR. At least back then,
> not touching the working tree was the _requirement_.
Yes. Now that read-tree verifies that the working directory is clean (at
least for any non-identity files), it's a non-issue.
> So is "the new merge world order" you mentioned in the log
> message now require (and assume) the work tree more-or-less
> matches the first head being merged?
Well, without "-u" you should see the old "order doesn't matter" case, but
yes, the theory is that the three trees are <base> <current> <merge> for
the three-way case, and <current> <new> for the two-way one.
You can get the old behaviour by using
git-read-tree -m <cur>
git-read-tree -m <base> <cur> <merge>
where the first read-tree ends up just makign sure that the index file
matches the current head (use "-u" or not as you like).
(Side note: the actual read-tree phase should be totally agnostic about
whether the current tree is the first, second or third of the trees, since
it will happily say "oh, we saw this exact directory entry in _one_ of the
trees, so we know it hasn't gotten lost". So for now, order still is left
to the final user, but I don't think you should depend on that).
Linus
^ permalink raw reply
* Re: Last mile for 1.0
From: Linus Torvalds @ 2005-06-06 14:47 UTC (permalink / raw)
To: Junio C Hamano; +Cc: Git Mailing List
In-Reply-To: <7vacm4ufnl.fsf@assigned-by-dhcp.cox.net>
[ git list added back in, since I migth as well explain the thinking here ]
On Mon, 6 Jun 2005, Junio C Hamano wrote:
>
> I've sent you a reply in another thread, but I really think you
> need to make this "new merge world order" a bit more explicit.
> My understanding of your (earlier) wish was that you wanted the
> merge not to touch and look at any work tree material, but it
> appears to me that this round you actually expect the work tree
> be populated and more-or-less match the first head being merged.
Actually, no. I expect the old _index_ to be at least not _more_ populated
than the trees I merge. That's not a working tree issue, that's a "we
don't want to drop information from the index".
And yes, if you use "-u", it will populate the working tree too, but
that's really totally unimportant from the algorithm itself.
But you can very much do everything in-index as before, if you want to. A
pure index merge would be done usually in a new temporary index file,
something like
rm -f .git/tmp_index
GIT_INDEX_FILE=.git/tmp_index git-read-tree -m <base> <merge1> <merge2>
and the new changes don't change that.
HOWEVER, it's all set up to be very clever indeed. My immediate goal is to
make the current git-resolve-script be more easily usable, and that
implies that it has to work in the current working directory and resolve
conflicts there. I still think that the _long-term_ plan is to make sure
that we don't do that, and the new thing actually supports that too.
For example, notice how I lifted all the "checkout" code from the
checkout-cache thing? Including very much the code that supports
"--prefix"? I didn't add the command line, but imagine just adding that,
which updates "state.base_dir", and doing
mkdir -p MERGE_DIR/.git
cp .git/index MERGE_DIR/.git/index
GIT_INDEX_FILE=MERGE_DIR/.git/index git-read-tree -u --prefix=MERGE_DIR/ <base> <merge1> <merge2>
and voila, you're basically now 75% of the way to where I wanted the thing
to be in a separate directory.
So I've given up on the separate directory for 1.0 - because it's clearly
not going to happen - but I've not given up on the basic idea.
Linus
^ permalink raw reply
* Re: new read-tree questions.
From: Linus Torvalds @ 2005-06-06 15:04 UTC (permalink / raw)
To: Junio C Hamano; +Cc: git
In-Reply-To: <7v64wrvpt4.fsf@assigned-by-dhcp.cox.net>
On Mon, 6 Jun 2005, Junio C Hamano wrote:
>
> I am trying to understand the new git-read-tree, by using
> git-resolve-script as an example and also reading read-tree.c; I
> am somewhat confused.
It _is_ a confusing piece of code. You don't see it in the revision
history, but I threw away a lot of trials that were crapola.
> * two-way merge (git-read-tree -m $H $M)
>
> My understanding is that the current index is allowed to be
> empty, but if it is not, they are kept at stage0, and each of
> them must match $H and must be up-to-date if the merge involves
> them.
The rule really boils down to: "no information that only existed in the
old 'stag0' must be lost".
So that means that an empty old stage0 is always fine.
It also means that if the old stage0 exactly matches the result, then
that's also always fine (regardless of the state of the actual checked out
file: we've not _changed_ anything).
But it means that if the old stage0 gets deleted or over-written, then the
information that the old stage0 _used_ to have needs to be encoded either
in the result _or_ it needs to have been there in the original tree, ie
the "loss" of information needs to be in the merge itself.
See? It's ok to drop information if that drop is encoded in the merge
itself ("we're merging a delete"), but it's _not_ ok to drop information
that wasn't part of the merge ("we're merging a delete where the index
file described something more than what was in the original tree")
Does that clarify what I'm aiming for? It may not clarify the code (which
may or may not match my aims ;), but at least it hopefully clarifies what
the _point_ of the code was supposed to be.
> To summarize my understanding of what should happen for each
> path:
>
> stage0 (index) stage1 ($H) stage2 ($M)
> ------------------------------------------------------------
> no such path no such path no such path
> * this does not happen (the code would not see such thing).
Yeah, I htink I get this right ;)
> ----------------------------------------------------------
> no such path no such path exists
> * take $M without complaining.
Yes.
> ----------------------------------------------------------
> no such path exists (does not matter) *0*
> * although index does not match $H, we do not reject, so
> that a merge can happen on an empty cache. We take $M.
Right. We didn't lose anything hugely important.
In theory this could be a delete that we've missed, and we could add a
flag to actually reject this case. However, it's always easy to "recover"
deletes (just delete it again ;), so the loss of information is absolutely
minimal, and it allows starting from an empty index file.
But this is debatable. We could reject it if you prefer that, and if you
want to make it a command line flag I'll definitely apply the patch.
> ----------------------------------------------------------
> exists no such path no such path
> * reject, because index does not match $H.
Exactly. The end result would have dropped the existing data, and the
_merge_ didn't contain that drop, so we reject that.
> ----------------------------------------------------------
> exists no such path exists (index!=$M)
> * reject, because index does not match $H.
Yes.
> ----------------------------------------------------------
> exists no such path exists (index=$M) *1*
> * take $M (same as "keep stage0").
This one is questionable. I think it should be accepted simply because
there's no point in not accepting it.
> ----------------------------------------------------------
> exists exists (index!=$H) (does not matter)
> * reject, because index does not match $H.
Yes.
> ----------------------------------------------------------
> exists exists (index=$H) no such path *2*
> * path is removed.
Yes. This drops the information, but since the merge contained that
_exact_ drop, that's what we want it to do. This one is not questionable
at all (except I got it wrong at one stage ;)
> ----------------------------------------------------------
> exists exists (index=$H) exists
> * take stage2.
Yes.
> Does the above matrix represent the intended behaviour?
>
> I think I understand why we would want *0*, but this asymmetry
> feels wrong.
Yup, you got it.
> I am having trouble with the case *1*.
The fact that you're having trouble is good, it means you realize that
reversing the merge doesn't get you the original state.
> Also I am not sure if the code does the right thing for case
> *2*. If I am reading the code right, for such a path, we will
> see stage0 and stage1, and at that point say seen_stage1 = 1 and
> keep stage0 entry in "old". Then we continue on to the next
> path. When it happens to be:
You're right. I messed up. Again. And the test-case I used for this
happened to not care (I think it may have been the only file, and as such
the next path never happened).
Anyway, you definitely get the idea.
Another way of encoding the rules: we _should_ eventually aim for a
situation where if a git-read-tree succeeds (even if it leaves crap
entries in the tree), we should be able to do a
git-read-tree -u -m <OLDHEAD>
and get back to the old state - or at least "close enough" (right now "-u"
doesn't do anything for the single-tree case, and "-m" complains about
unmerged entries, but the point isn't that it works today, the point is
what should be possible at some point ;)
Linus
^ permalink raw reply
* 7fb9de4a830dd8969bc17a219c509a76dd3c9aad
From: jon @ 2005-06-06 15:39 UTC (permalink / raw)
To: git; +Cc: jon.seymour, torvalds
[PATCH] Modify git-rev-list to linearise the commit history in merge order.
This patch linearises the GIT commit history graph into merge order
which is defined by invariants specified in Documentation/git-rev-list.txt.
The linearisation produced by this patch is superior in an objective sense
to that produced by the existing git-rev-list implementation in that
the linearisation produced is guaranteed to have the minimum number of
discontinuities, where a discontinuity is defined as an adjacent pair of
commits in the output list which are not related in a direct child-parent
relationship.
With this patch a graph like this:
a4 ---
| \ \
| b4 |
|/ | |
a3 | |
| | |
a2 | |
| | c3
| | |
| | c2
| b3 |
| | /|
| b2 |
| | c1
| | /
| b1
a1 |
| |
a0 |
| /
root
Sorts like this:
= a4
| c3
| c2
| c1
^ b4
| b3
| b2
| b1
^ a3
| a2
| a1
| a0
= root
Instead of this:
= a4
| c3
^ b4
| a3
^ c2
^ b3
^ a2
^ b2
^ c1
^ a1
^ b1
^ a0
= root
A test script, t/t6000-rev-list.sh, includes a test which demonstrates
that the linearisation produced by --merge-order has less discontinuities
than the linearisation produced by git-rev-list without the --merge-order
flag specified. To see this, do the following:
cd t
./t6000-rev-list.sh
cd trash
cat actual-default-order
cat actual-merge-order
The existing behaviour of git-rev-list is preserved, by default. To obtain
the modified behaviour, specify --merge-order or --merge-order --show-breaks
on the command line.
This version of the patch has been tested on the git repository and also on the linux-2.6
repository and has reasonable performance on both - ~50-100% slower than the original algorithm.
This version of the patch has incorporated a functional equivalent of the Linus' output limiting
algorithm into the merge-order algorithm itself. This operates per the notes associated
with Linus' commit 337cb3fb8da45f10fe9a0c3cf571600f55ead2ce.
This version has incorporated Linus' feedback regarding proposed changes to rev-list.c.
(see: [PATCH] Factor out filtering in rev-list.c)
This version has improved the way sort_first_epoch marks commits as uninteresting.
For more details about this change, refer to Documentation/git-rev-list.txt
and http://blackcubes.dyndns.org/epoch/.
Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
Diverged from d925ffbd064802bc8a6ab0bccf0c43b00a7fe710 by Linus Torvalds <torvalds@ppc970.osdl.org>
---
diff --git a/Documentation/git-rev-list.txt b/Documentation/git-rev-list.txt
--- a/Documentation/git-rev-list.txt
+++ b/Documentation/git-rev-list.txt
@@ -9,7 +9,7 @@ git-rev-list - Lists commit objects in r
SYNOPSIS
--------
-'git-rev-list' <commit>
+'git-rev-list' [ *--max-count*=number ] [ *--max-age*=timestamp ] [ *--min-age*=timestamp ] [ *--merge-order* [ *--show-breaks* ] ] <commit>
DESCRIPTION
-----------
@@ -17,11 +17,39 @@ Lists commit objects in reverse chronolo
given commit, taking ancestry relationship into account. This is
useful to produce human-readable log output.
+If *--merge-order* is specified, the commit history is decomposed into a unique sequence of minimal, non-linear
+epochs and maximal, linear epochs. Non-linear epochs are then linearised by sorting them into merge order, which
+is described below.
+
+Maximal, linear epochs correspond to periods of sequential development. Minimal, non-linear epochs
+correspond to periods of divergent development followed by a converging merge. The theory of epochs is described
+in more detail at link:http://blackcubes.dyndns.org/epoch/[http://blackcubes.dyndns.org/epoch/].
+
+The merge order for a non-linear epoch is defined as a linearisation for which the following invariants are true:
+
+ 1. if a commit P is reachable from commit N, commit P sorts after commit N in the linearised list.
+ 2. if Pi and Pj are any two parents of a merge M (with i < j), then any commit N, such that N is reachable from Pj
+ but not reachable from Pi, sorts before all commits reachable from Pi.
+
+Invariant 1 states that later commits appear before earlier commits they are derived from.
+
+Invariant 2 states that commits unique to "later" parents in a merge, appear before all commits from "earlier" parents of
+a merge.
+
+If *--show-breaks* is specified, each item of the list is output with a 2-character prefix consisting of one of:
+ (|), (^), (=) followed by a space.
+Commits marked with (=) represent the boundaries of minimal, non-linear epochs and correspond either to the start of a period of divergent development or to the end of such a period.
+Commits marked with (|) are direct parents of commits immediately preceding the marked commit in the list.
+Commits marked with (^) are not parents of the immediately preceding commit. These "breaks" represent necessary discontinuities implied by trying to represent an arbtirary DAG in a linear form.
+
+*--show-breaks* is only valid if *--merge-order* is also specified.
Author
------
Written by Linus Torvalds <torvalds@osdl.org>
+Original *--merge-order* logic by Jon Seymour <jon.seymour@gmail.com>
+
Documentation
--------------
Documentation by David Greaves, Junio C Hamano and the git-list <git@vger.kernel.org>.
diff --git a/Makefile b/Makefile
--- a/Makefile
+++ b/Makefile
@@ -40,9 +40,9 @@ install: $(PROG) $(SCRIPTS)
$(INSTALL) $(PROG) $(SCRIPTS) $(dest)$(bin)
LIB_OBJS=read-cache.o sha1_file.o usage.o object.o commit.o tree.o blob.o \
- tag.o delta.o date.o index.o diff-delta.o patch-delta.o entry.o
+ tag.o delta.o date.o index.o diff-delta.o patch-delta.o entry.o epoch.o
LIB_FILE=libgit.a
-LIB_H=cache.h object.h blob.h tree.h commit.h tag.h delta.h
+LIB_H=cache.h object.h blob.h tree.h commit.h tag.h delta.h epoch.h
LIB_H += strbuf.h
LIB_OBJS += strbuf.o
@@ -135,6 +135,7 @@ diffcore-pathspec.o : $(LIB_H) diffcore.
diffcore-pickaxe.o : $(LIB_H) diffcore.h
diffcore-break.o : $(LIB_H) diffcore.h
diffcore-order.o : $(LIB_H) diffcore.h
+epoch.o: $(LIB_H)
test: all
$(MAKE) -C t/ all
diff --git a/commit.c b/commit.c
--- a/commit.c
+++ b/commit.c
@@ -130,7 +130,7 @@ void free_commit_list(struct commit_list
}
}
-static void insert_by_date(struct commit_list **list, struct commit *item)
+void insert_by_date(struct commit_list **list, struct commit *item)
{
struct commit_list **pp = list;
struct commit_list *p;
@@ -280,3 +280,25 @@ unsigned long pretty_print_commit(enum c
buf[offset] = '\0';
return offset;
}
+
+struct commit *pop_commit(struct commit_list **stack)
+{
+ struct commit_list *top = *stack;
+ struct commit *item = top ? top->item : NULL;
+
+ if (top) {
+ *stack = top->next;
+ free(top);
+ }
+ return item;
+}
+
+int count_parents(struct commit * commit)
+{
+ int count = 0;
+ struct commit_list * parents = commit->parents;
+ for (count=0;parents; parents=parents->next,count++)
+ ;
+ return count;
+}
+
diff --git a/commit.h b/commit.h
--- a/commit.h
+++ b/commit.h
@@ -42,6 +42,7 @@ enum cmit_fmt {
extern unsigned long pretty_print_commit(enum cmit_fmt fmt, const char *msg, unsigned long len, char *buf, unsigned long space);
+void insert_by_date(struct commit_list **list, struct commit *item);
/** Removes the first commit from a list sorted by date, and adds all
* of its parents.
@@ -49,4 +50,7 @@ extern unsigned long pretty_print_commit
struct commit *pop_most_recent_commit(struct commit_list **list,
unsigned int mark);
+struct commit *pop_commit(struct commit_list **stack);
+
+int count_parents(struct commit * commit);
#endif /* COMMIT_H */
diff --git a/epoch.c b/epoch.c
new file mode 100644
--- /dev/null
+++ b/epoch.c
@@ -0,0 +1,693 @@
+/*
+ * Copyright (c) 2005, Jon Seymour
+ *
+ * For more information about epoch theory on which this module is based,
+ * refer to http://blackcubes.dyndns.org/epoch/. That web page defines
+ * terms such as "epoch" and "minimal, non-linear epoch" and provides rationales
+ * for some of the algorithms used here.
+ *
+ */
+#include <stdlib.h>
+#include <openssl/bn.h> // provides arbitrary precision integers
+ // required to accurately represent fractional
+ //mass
+
+#include "cache.h"
+#include "commit.h"
+#include "epoch.h"
+
+struct fraction {
+ BIGNUM numerator;
+ BIGNUM denominator;
+};
+
+#define HAS_EXACTLY_ONE_PARENT(n) ((n)->parents && !(n)->parents->next)
+
+static BN_CTX *context = NULL;
+static struct fraction *one = NULL;
+static struct fraction *zero = NULL;
+
+static BN_CTX *get_BN_CTX()
+{
+ if (!context) {
+ context = BN_CTX_new();
+ }
+ return context;
+}
+
+static struct fraction *new_zero()
+{
+ struct fraction *result = xmalloc(sizeof(*result));
+ BN_init(&result->numerator);
+ BN_init(&result->denominator);
+ BN_zero(&result->numerator);
+ BN_one(&result->denominator);
+ return result;
+}
+
+static void clear_fraction(struct fraction *fraction)
+{
+ BN_clear(&fraction->numerator);
+ BN_clear(&fraction->denominator);
+}
+
+static struct fraction *divide(struct fraction *result, struct fraction *fraction, int divisor)
+{
+ BIGNUM bn_divisor;
+
+ BN_init(&bn_divisor);
+ BN_set_word(&bn_divisor, divisor);
+
+ BN_copy(&result->numerator, &fraction->numerator);
+ BN_mul(&result->denominator, &fraction->denominator, &bn_divisor, get_BN_CTX());
+
+ BN_clear(&bn_divisor);
+ return result;
+}
+
+static struct fraction *init_fraction(struct fraction *fraction)
+{
+ BN_init(&fraction->numerator);
+ BN_init(&fraction->denominator);
+ BN_zero(&fraction->numerator);
+ BN_one(&fraction->denominator);
+ return fraction;
+}
+
+static struct fraction *get_one()
+{
+ if (!one) {
+ one = new_zero();
+ BN_one(&one->numerator);
+ }
+ return one;
+}
+
+static struct fraction *get_zero()
+{
+ if (!zero) {
+ zero = new_zero();
+ }
+ return zero;
+}
+
+static struct fraction *copy(struct fraction *to, struct fraction *from)
+{
+ BN_copy(&to->numerator, &from->numerator);
+ BN_copy(&to->denominator, &from->denominator);
+ return to;
+}
+
+static struct fraction *add(struct fraction *result, struct fraction *left, struct fraction *right)
+{
+ BIGNUM a, b, gcd;
+
+ BN_init(&a);
+ BN_init(&b);
+ BN_init(&gcd);
+
+ BN_mul(&a, &left->numerator, &right->denominator, get_BN_CTX());
+ BN_mul(&b, &left->denominator, &right->numerator, get_BN_CTX());
+ BN_mul(&result->denominator, &left->denominator, &right->denominator, get_BN_CTX());
+ BN_add(&result->numerator, &a, &b);
+
+ BN_gcd(&gcd, &result->denominator, &result->numerator, get_BN_CTX());
+ BN_div(&result->denominator, NULL, &result->denominator, &gcd, get_BN_CTX());
+ BN_div(&result->numerator, NULL, &result->numerator, &gcd, get_BN_CTX());
+
+ BN_clear(&a);
+ BN_clear(&b);
+ BN_clear(&gcd);
+
+ return result;
+}
+
+static int compare(struct fraction *left, struct fraction *right)
+{
+ BIGNUM a, b;
+
+ int result;
+
+ BN_init(&a);
+ BN_init(&b);
+
+ BN_mul(&a, &left->numerator, &right->denominator, get_BN_CTX());
+ BN_mul(&b, &left->denominator, &right->numerator, get_BN_CTX());
+
+ result = BN_cmp(&a, &b);
+
+ BN_clear(&a);
+ BN_clear(&b);
+
+ return result;
+}
+
+struct mass_counter {
+ struct fraction seen;
+ struct fraction pending;
+};
+
+static struct mass_counter *new_mass_counter(struct commit *commit, struct fraction *pending)
+{
+ struct mass_counter *mass_counter = xmalloc(sizeof(*mass_counter));
+ memset(mass_counter, 0, sizeof(*mass_counter));
+
+ init_fraction(&mass_counter->seen);
+ init_fraction(&mass_counter->pending);
+
+ copy(&mass_counter->pending, pending);
+ copy(&mass_counter->seen, get_zero());
+
+ if (commit->object.util) {
+ die("multiple attempts to initialize mass counter for %s\n", sha1_to_hex(commit->object.sha1));
+ }
+
+ commit->object.util = mass_counter;
+
+ return mass_counter;
+}
+
+static void free_mass_counter(struct mass_counter *counter)
+{
+ clear_fraction(&counter->seen);
+ clear_fraction(&counter->pending);
+ free(counter);
+}
+
+//
+// Finds the base commit of a list of commits.
+//
+// One property of the commit being searched for is that every commit reachable
+// from the base commit is reachable from the commits in the starting list only
+// via paths that include the base commit.
+//
+// This algorithm uses a conservation of mass approach to find the base commit.
+//
+// We start by injecting one unit of mass into the graph at each
+// of the commits in the starting list. Injecting mass into a commit
+// is achieved by adding to its pending mass counter and, if it is not already
+// enqueued, enqueuing the commit in a list of pending commits, in latest
+// commit date first order.
+//
+// The algorithm then preceeds to visit each commit in the pending queue.
+// Upon each visit, the pending mass is added to the mass already seen for that
+// commit and then divided into N equal portions, where N is the number of
+// parents of the commit being visited. The divided portions are then injected
+// into each of the parents.
+//
+// The algorithm continues until we discover a commit which has seen all the
+// mass originally injected or until we run out of things to do.
+//
+// If we find a commit that has seen all the original mass, we have found
+// the common base of all the commits in the starting list.
+//
+// The algorithm does _not_ depend on accurate timestamps for correct operation.
+// However, reasonably sane (e.g. non-random) timestamps are required in order
+// to prevent an exponential performance characteristic. The occasional
+// timestamp inaccuracy will not dramatically affect performance but may
+// result in more nodes being processed than strictly necessary.
+//
+// This procedure sets *boundary to the address of the base commit. It returns
+// 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 ret = 0;
+
+ struct commit_list *cleaner = NULL;
+ struct commit_list *pending = NULL;
+
+ *boundary = NULL;
+
+ struct fraction injected;
+
+ init_fraction(&injected);
+
+ for (; list; list = list->next) {
+
+ struct commit *item = list->item;
+
+ if (item->object.util || (item->object.flags & UNINTERESTING)) {
+ die("%s:%d:%s: logic error: this should not have happened - commit %s\n",
+ __FILE__, __LINE__, __FUNCTION__, sha1_to_hex(item->object.sha1));
+ }
+
+ new_mass_counter(list->item, get_one());
+ add(&injected, &injected, get_one());
+
+ commit_list_insert(list->item, &cleaner);
+ commit_list_insert(list->item, &pending);
+ }
+
+ while (!*boundary && pending && !ret) {
+
+ struct commit *latest = pop_commit(&pending);
+
+ struct mass_counter *latest_node = (struct mass_counter *) latest->object.util;
+
+ if ((ret = parse_commit(latest)))
+ continue;
+
+ add(&latest_node->seen, &latest_node->seen, &latest_node->pending);
+
+ int num_parents = count_parents(latest);
+
+ if (num_parents) {
+
+ struct fraction distribution;
+ struct commit_list *parents;
+
+ divide(init_fraction(&distribution), &latest_node->pending, num_parents);
+
+ for (parents = latest->parents; parents; parents = parents->next) {
+
+ struct commit *parent = parents->item;
+ struct mass_counter *parent_node = (struct mass_counter *) parent->object.util;
+
+ if (!parent_node) {
+
+ parent_node = new_mass_counter(parent, &distribution);
+
+ insert_by_date(&pending, parent);
+ commit_list_insert(parent, &cleaner);
+
+ } else {
+
+ if (!compare(&parent_node->pending, get_zero())) {
+ insert_by_date(&pending, parent);
+ }
+ add(&parent_node->pending, &parent_node->pending, &distribution);
+
+ }
+ }
+
+ clear_fraction(&distribution);
+
+ }
+
+ if (!compare(&latest_node->seen, &injected)) {
+ *boundary = latest;
+ }
+
+ copy(&latest_node->pending, get_zero());
+
+ }
+
+ while (cleaner) {
+
+ struct commit *next = pop_commit(&cleaner);
+ free_mass_counter((struct mass_counter *) next->object.util);
+ next->object.util = NULL;
+
+ }
+
+ if (pending)
+ free_commit_list(pending);
+
+ clear_fraction(&injected);
+
+ return ret;
+
+}
+
+
+//
+// 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 ret = 0;
+ struct commit_list *pending = NULL;
+ struct commit_list *next;
+
+ commit_list_insert(head, &pending);
+ for (next = head->parents; next; next = next->next) {
+ commit_list_insert(next->item, &pending);
+ }
+ ret = find_base_for_list(pending, boundary);
+ free_commit_list(pending);
+
+ return ret;
+}
+
+//
+// This procedure traverses to the boundary of the first epoch in the epoch
+// sequence of the epoch headed at head_of_epoch. This is either the end of
+// the maximal linear epoch or the base of a minimal non-linear epoch.
+//
+// The queue of pending nodes is sorted in reverse date order and each node
+// is currently in the queue at most once.
+//
+static int find_next_epoch_boundary(struct commit *head_of_epoch, struct commit **boundary)
+{
+ int ret;
+ struct commit *item = head_of_epoch;
+
+ ret = parse_commit(item);
+ if (ret)
+ return ret;
+
+ if (HAS_EXACTLY_ONE_PARENT(item)) {
+
+ // we are at the start of a maximimal linear epoch .. traverse to the end
+
+ // traverse to the end of a maximal linear epoch
+ while (HAS_EXACTLY_ONE_PARENT(item) && !ret) {
+ item = item->parents->item;
+ ret = parse_commit(item);
+ }
+ *boundary = item;
+
+ } else {
+
+ // otherwise, we are at the start of a minimal, non-linear
+ // epoch - find the common base of all parents.
+
+ ret = find_base(item, boundary);
+
+ }
+
+ return ret;
+}
+
+//
+// Returns non-zero if parent is known to be a parent of child.
+//
+static int is_parent_of(struct commit *parent, struct commit *child)
+{
+ struct commit_list *parents;
+ for (parents = child->parents; parents; parents = parents->next) {
+ if (!memcmp(parent->object.sha1, parents->item->object.sha1, sizeof(parents->item->object.sha1)))
+ return 1;
+ }
+ return 0;
+}
+
+//
+// Pushes an item onto the merge order stack. If the top of the stack is
+// marked as being a possible "break", we check to see whether it actually
+// is a break.
+//
+static void push_onto_merge_order_stack(struct commit_list **stack, struct commit *item)
+{
+ struct commit_list *top = *stack;
+ if (top && (top->item->object.flags & DISCONTINUITY)) {
+ if (is_parent_of(top->item, item)) {
+ top->item->object.flags &= ~DISCONTINUITY;
+ }
+ }
+ commit_list_insert(item, stack);
+}
+
+//
+// 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 marking 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_first_epoch
+// 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;
+
+ if (uninteresting || boundary || !visited) {
+ commit->object.flags |= UNINTERESTING;
+ return;
+
+ // 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_first_epoch traverse will
+ // mark unreachable 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
+ // then either all ancestors have already been marked
+ // uninteresting or will be once the sort_first_epoch
+ // traverse reaches them.
+ //
+ }
+
+ struct commit_list *next;
+
+ for (next = commit->parents; next; next = next->next)
+ mark_ancestors_uninteresting(next->item);
+}
+
+//
+// Sorts the nodes of the first epoch of the epoch sequence of the epoch headed at head
+// into merge order.
+//
+static void sort_first_epoch(struct commit *head, struct commit_list **stack)
+{
+ struct commit_list *parents;
+ struct commit_list *reversed_parents = NULL;
+
+ head->object.flags |= VISITED;
+
+ //
+ // parse_commit builds the parent list in reverse order with respect to the order of
+ // the git-commit-tree arguments.
+ //
+ // so we need to reverse this list to output the oldest (or most "local") commits last.
+ //
+
+ for (parents = head->parents; parents; parents = parents->next)
+ commit_list_insert(parents->item, &reversed_parents);
+
+ //
+ // todo: by sorting the parents in a different order, we can alter the
+ // merge order to show contemporaneous changes in parallel branches
+ // occurring after "local" changes. This is useful for a developer
+ // when a developer wants to see all changes that were incorporated
+ // into the same merge as her own changes occur after her own
+ // changes.
+ //
+
+ while (reversed_parents) {
+
+ struct commit *parent = pop_commit(&reversed_parents);
+
+ if (head->object.flags & UNINTERESTING) {
+ // propagates the uninteresting bit to
+ // all parents. if we have already visited
+ // this parent, then the uninteresting bit
+ // will be propagated to each reachable
+ // commit that is still not marked uninteresting
+ // and won't otherwise be reached.
+ mark_ancestors_uninteresting(parent);
+ }
+
+ if (!(parent->object.flags & VISITED)) {
+ if (parent->object.flags & BOUNDARY) {
+
+ if (*stack) {
+ die("something else is on the stack - %s\n", sha1_to_hex((*stack)->item->object.sha1));
+ }
+
+ push_onto_merge_order_stack(stack, parent);
+ parent->object.flags |= VISITED;
+
+ } else {
+
+ sort_first_epoch(parent, stack);
+
+ if (reversed_parents) {
+ //
+ // this indicates a possible discontinuity
+ // it may not be be actual discontinuity if
+ // the head of parent N happens to be the tail
+ // of parent N+1
+ //
+ // the next push onto the stack will resolve the
+ // question
+ //
+ (*stack)->item->object.flags |= DISCONTINUITY;
+ }
+ }
+ }
+ }
+
+ push_onto_merge_order_stack(stack, head);
+}
+
+//
+// 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.
+//
+static int emit_stack(struct commit_list **stack, emitter_func emitter)
+{
+ unsigned int seen = 0;
+ int action = CONTINUE;
+
+ while (*stack && (action != STOP)) {
+
+ struct commit *next = pop_commit(stack);
+
+ seen |= next->object.flags;
+
+ if (*stack) {
+ action = (*emitter) (next);
+ }
+ }
+
+ if (*stack) {
+ free_commit_list(*stack);
+ *stack = NULL;
+ }
+
+ return (action == STOP || (seen & UNINTERESTING)) ? STOP : CONTINUE;
+}
+
+//
+// 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_of_epoch, emitter_func emitter)
+{
+ struct commit *next = head_of_epoch;
+ int ret = 0;
+ int action = CONTINUE;
+
+ ret = parse_commit(head_of_epoch);
+
+ while (next && next->parents && !ret && (action != STOP)) {
+
+ struct commit *base = NULL;
+
+ if ((ret = find_next_epoch_boundary(next, &base)))
+ return ret;
+
+ next->object.flags |= BOUNDARY;
+ if (base) {
+ base->object.flags |= BOUNDARY;
+ }
+
+ if (HAS_EXACTLY_ONE_PARENT(next)) {
+
+ while (HAS_EXACTLY_ONE_PARENT(next)
+ && (action != STOP)
+ && !ret) {
+
+ if (next->object.flags & UNINTERESTING) {
+ action = STOP;
+ } else {
+ action = (*emitter) (next);
+ }
+
+ if (action != STOP) {
+ next = next->parents->item;
+ ret = parse_commit(next);
+ }
+ }
+
+ } else {
+
+ struct commit_list *stack = NULL;
+ sort_first_epoch(next, &stack);
+ action = emit_stack(&stack, emitter);
+ next = base;
+
+ }
+
+ }
+
+ if (next && (action != STOP) && !ret) {
+ (*emitter) (next);
+ }
+
+ return ret;
+}
+
+//
+// Sorts 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_first_epoch algorithm. Once we have reached the base
+// we can continue sorting using sort_in_merge_order.
+//
+int sort_list_in_merge_order(struct commit_list *list, emitter_func emitter)
+{
+ struct commit_list *stack = NULL;
+ struct commit *base;
+
+ int ret = 0;
+ int action = CONTINUE;
+
+ struct commit_list *reversed = NULL;
+
+ for (; list; list = list->next) {
+
+ struct commit *next = list->item;
+
+ if (!(next->object.flags & UNINTERESTING)) {
+ if (next->object.flags & DUPCHECK) {
+ fprintf(stderr, "%s: duplicate commit %s ignored\n", __FUNCTION__, sha1_to_hex(next->object.sha1));
+ } else {
+ next->object.flags |= DUPCHECK;
+ commit_list_insert(list->item, &reversed);
+ }
+ }
+ }
+
+ if (!reversed->next) {
+
+ // if there is only one element in the list, we can sort it using
+ // sort_in_merge_order.
+
+ base = reversed->item;
+
+ } else {
+
+ // otherwise, we search for the base of the list
+
+ if ((ret = find_base_for_list(reversed, &base)))
+ return ret;
+
+ if (base) {
+ base->object.flags |= BOUNDARY;
+ }
+
+ while (reversed) {
+ sort_first_epoch(pop_commit(&reversed), &stack);
+ if (reversed) {
+ //
+ // if we have more commits to push, then the
+ // first push for the next parent may (or may not)
+ // represent a discontinuity with respect to the
+ // parent currently on the top of the stack.
+ //
+ // mark it for checking here, and check it
+ // with the next push...see sort_first_epoch for
+ // more details.
+ //
+ stack->item->object.flags |= DISCONTINUITY;
+ }
+ }
+
+ action = emit_stack(&stack, emitter);
+ }
+
+ if (base && (action != STOP)) {
+ ret = sort_in_merge_order(base, emitter);
+ }
+
+ return ret;
+}
diff --git a/epoch.h b/epoch.h
new file mode 100644
--- /dev/null
+++ b/epoch.h
@@ -0,0 +1,20 @@
+#ifndef EPOCH_H
+#define EPOCH_H
+
+
+// return codes for emitter_func
+#define STOP 0
+#define CONTINUE 1
+#define DO 2
+typedef int (*emitter_func) (struct commit *);
+
+int sort_list_in_merge_order(struct commit_list *list, emitter_func emitter);
+
+#define UNINTERESTING (1u<<2)
+#define BOUNDARY (1u<<3)
+#define VISITED (1u<<4)
+#define DISCONTINUITY (1u<<5)
+#define DUPCHECK (1u<<6)
+
+
+#endif /* EPOCH_H */
diff --git a/object.h b/object.h
--- a/object.h
+++ b/object.h
@@ -15,6 +15,7 @@ struct object {
const char *type;
struct object_list *refs;
struct object_list *attached_deltas;
+ void *util;
};
extern int nr_objs;
diff --git a/rev-list.c b/rev-list.c
--- a/rev-list.c
+++ b/rev-list.c
@@ -1,9 +1,9 @@
#include "cache.h"
#include "commit.h"
+#include "epoch.h"
#define SEEN (1u << 0)
#define INTERESTING (1u << 1)
-#define UNINTERESTING (1u << 2)
static const char rev_list_usage[] =
"usage: git-rev-list [OPTION] commit-id <commit-id>\n"
@@ -11,7 +11,8 @@ static const char rev_list_usage[] =
" --max-age=epoch\n"
" --min-age=epoch\n"
" --header\n"
- " --pretty";
+ " --pretty\n"
+ " --merge-order [ --show-breaks ]";
static int verbose_header = 0;
static int show_parents = 0;
@@ -21,9 +22,19 @@ static unsigned long max_age = -1;
static unsigned long min_age = -1;
static int max_count = -1;
static enum cmit_fmt commit_format = CMIT_FMT_RAW;
+static int merge_order = 0;
+static int show_breaks = 0;
static void show_commit(struct commit *commit)
{
+ if (show_breaks) {
+ prefix = "| ";
+ if (commit->object.flags & DISCONTINUITY) {
+ prefix = "^ ";
+ } else if (commit->object.flags & BOUNDARY) {
+ prefix = "= ";
+ }
+ }
printf("%s%s", prefix, sha1_to_hex(commit->object.sha1));
if (show_parents) {
struct commit_list *parents = commit->parents;
@@ -37,7 +48,38 @@ static void show_commit(struct commit *c
static char pretty_header[16384];
pretty_print_commit(commit_format, commit->buffer, ~0, pretty_header, sizeof(pretty_header));
printf("%s%c", pretty_header, hdr_termination);
+ }
+}
+
+static int filter_commit(struct commit * commit)
+{
+ if (commit->object.flags & UNINTERESTING)
+ return CONTINUE;
+ if (min_age != -1 && (commit->date > min_age))
+ return CONTINUE;
+ if (max_age != -1 && (commit->date < max_age))
+ return STOP;
+ if (max_count != -1 && !max_count--)
+ return STOP;
+
+ return DO;
+}
+
+static int process_commit(struct commit * commit)
+{
+ int action=filter_commit(commit);
+
+ if (action == STOP) {
+ return STOP;
+ }
+
+ if (action == CONTINUE) {
+ return CONTINUE;
}
+
+ show_commit(commit);
+
+ return CONTINUE;
}
static void show_commit_list(struct commit_list *list)
@@ -45,15 +87,8 @@ static void show_commit_list(struct comm
while (list) {
struct commit *commit = pop_most_recent_commit(&list, SEEN);
- if (commit->object.flags & UNINTERESTING)
- continue;
- if (min_age != -1 && (commit->date > min_age))
- continue;
- if (max_age != -1 && (commit->date < max_age))
+ if (process_commit(commit) == STOP)
break;
- if (max_count != -1 && !max_count--)
- break;
- show_commit(commit);
}
}
@@ -110,6 +145,8 @@ static enum cmit_fmt get_commit_format(c
if (!strcmp(arg, "=short"))
return CMIT_FMT_SHORT;
usage(rev_list_usage);
+
+ return CMIT_FMT_DEFAULT;
}
@@ -151,6 +188,14 @@ int main(int argc, char **argv)
show_parents = 1;
continue;
}
+ if (!strncmp(arg, "--merge-order", 13)) {
+ merge_order = 1;
+ continue;
+ }
+ if (!strncmp(arg, "--show-breaks", 13)) {
+ show_breaks = 1;
+ continue;
+ }
flags = 0;
if (*arg == '^') {
@@ -158,7 +203,7 @@ int main(int argc, char **argv)
arg++;
limited = 1;
}
- if (get_sha1(arg, sha1))
+ if (get_sha1(arg, sha1) || (show_breaks && !merge_order))
usage(rev_list_usage);
commit = lookup_commit_reference(sha1);
if (!commit || parse_commit(commit) < 0)
@@ -170,9 +215,19 @@ int main(int argc, char **argv)
if (!list)
usage(rev_list_usage);
- if (limited)
- list = limit_list(list);
+ if (!merge_order) {
+
+ if (limited)
+ list = limit_list(list);
+ show_commit_list(list);
+
+ } else {
+
+ if (sort_list_in_merge_order(list, &process_commit)) {
+ die("merge order sort failed\n");
+ }
+
+ }
- show_commit_list(list);
return 0;
}
^ permalink raw reply
* Re: 7fb9de4a830dd8969bc17a219c509a76dd3c9aad [ or: the --merge-order patch ]
From: Jon Seymour @ 2005-06-06 15:44 UTC (permalink / raw)
To: git; +Cc: torvalds
In-Reply-To: <20050606153940.20039.qmail@blackcubes.dyndns.org>
Sorry about the Subject: - my patch submission script is obviously a
little buggy.
Anyway, the referenced e-mail contains the latest --merge-order patch
which is synced with Linus' head and incorporates my earlier
rev-list.c patch.
jon.
^ permalink raw reply
* Re: 7fb9de4a830dd8969bc17a219c509a76dd3c9aad
From: Linus Torvalds @ 2005-06-06 16:01 UTC (permalink / raw)
To: jon; +Cc: git, jon.seymour
In-Reply-To: <20050606153940.20039.qmail@blackcubes.dyndns.org>
On Mon, 6 Jun 2005 jon@blackcubes.dyndns.org wrote:
>
> [PATCH] Modify git-rev-list to linearise the commit history in merge order.
Much nicer. Will apply after testing, however, not this part:
> @@ -110,6 +145,8 @@ static enum cmit_fmt get_commit_format(c
> if (!strcmp(arg, "=short"))
> return CMIT_FMT_SHORT;
> usage(rev_list_usage);
> +
> + return CMIT_FMT_DEFAULT;
> }
>
>
If you're bothered by a compiler warning (that I don't see, wonder why?),
please mark usage() and die() with "__attribute__ ((__noreturn__))". Make
it depend on GCC, ie
#ifdef __GCC__
#define NO_RETURN __attribute__((__noreturn__))
#else
#define NO_RETURN
#endif
and then do
extern void die(const char *, ...) NO_RETURN;
or something like that.
Anyway, that's indepdendent of this patch, but just fyi.
Linus
^ permalink raw reply
* Re: Database consistency after a successful pull
From: Daniel Barkalow @ 2005-06-06 16:21 UTC (permalink / raw)
To: McMullan, Jason; +Cc: Junio C Hamano, Linus Torvalds, GIT Mailling list
In-Reply-To: <1118065849.8970.37.camel@jmcmullan.timesys>
On Mon, 6 Jun 2005, McMullan, Jason wrote:
> Subject Was: [PATCH] pull: gracefu[PAlly recover from delta retrieval
> failure.]
>
> [snip lots of really good information about the thinking
> behind the design of the pull mechanisms ]
>
> Ok, so would I be correct in the following assumptions
> about the validity of a 'consistent' .git/objects database:
>
> ============================================================
>
> Commits:
> * May have the tree they refer to in the database
> * Must have their parents in the database
May have their parents in the database; we want to be able to drop ancient
history from non-archival sites at some point, if nothing else.
> Trees:
> * Must have the blobs they refer to in the database
> * Must have the trees they refer to in the database
It's probably true that there's no point to having a tree available if you
don't have its contents, although that's a convenient intermediate stage,
so that you can look up the contents of the tree with the ordinary parsing
code. On the other hand, I could imagine an ARM developer completely
ignoring arch/i386 (and just having write-tree use the parent tree's value
for it).
> Deltas:
> * Must have the referred to object in the database
Yes. Can't unpack without them.
> Blobs:
> * No references to check
Right.
Also, tags reference objects of unknown type; it's probably not vital to
have the object.
My bias is to call a database consistent with only deltas having the
referents; the rest goes towards completeness, since you have and can read
everything that you have anything for (but may not be able to do some
particular operation).
-Daniel
*This .sig left intentionally blank*
^ permalink raw reply
* Re: Database consistency after a successful pull
From: McMullan, Jason @ 2005-06-06 18:30 UTC (permalink / raw)
To: Daniel Barkalow; +Cc: Junio C Hamano, Linus Torvalds, GIT Mailling list
In-Reply-To: <Pine.LNX.4.21.0506061000531.30848-100000@iabervon.org>
[-- Attachment #1: Type: text/plain, Size: 532 bytes --]
On Mon, 2005-06-06 at 12:21 -0400, Daniel Barkalow wrote:
> [snip snip]
>
> My bias is to call a database consistent with only deltas having the
> referents; the rest goes towards completeness, since you have and can read
> everything that you have anything for (but may not be able to do some
> particular operation).
Now, if we had consistent URIs for the .git/branches/* files, we could
do 'lazy-pull' and really have our cake and eat it too.
--
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
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