* Re: [PATCH 1/1] Add a topological sort procedure to commit.c
From: Junio C Hamano @ 2005-06-30 6:52 UTC (permalink / raw)
To: Jon Seymour; +Cc: Linus Torvalds, git
In-Reply-To: <20050630055821.1329.qmail@blackcubes.dyndns.org>
Interesting idea. Help me understand the code.
@@ -346,3 +352,79 @@ int count_parents(struct commit * commit
return count;
}
+/*
+ * Performs an in-place topological sort on the list supplied
+ */
+void sort_in_topological_order(struct commit_list ** list)
+{
+ ...
+ /* allocate an array to help sort the list */
+ nodes = xmalloc(sizeof(*nodes) * count);
+ /* link the list to the array */
+ next_nodes = nodes;
+ next=*list;
+ while (next) {
+ next_nodes->list_item = next;
+ next->item->object.util = next_nodes;
+ next_nodes++;
+ next = next->next;
+ }
+ /* update the indegree */
Don't you want to initialize before update? Either in the above
while(next) loop or just after xmalloc() with a single
memset(0), or xcalloc()?
+ next=*list;
+ while (next) {
+ struct commit_list * parents = next->item->parents;
+ while (parents) {
+ struct commit * parent=parents->item;
+ struct sort_node * pn = (struct sort_node *)parent->object.util;
+
+ if (pn)
+ pn->indegree++;
I take this to mean that not all commits are on *list and such
commits not on *list have object.util set to NULL. Who
initializes object.util (this is not a nitpick but a question as
a user)? commit.c::lookup_commit() uses memset(0) and when
sort_in_topological_order() function is called everybody (not
limited to the ones on *list but all commits reachable from
them) are supposed to have object.util set to NULL?
So sort_node->indegree means how many children of it are on the
*list. Am I reading you correctly so far?
+ parents=parents->next;
+ }
+ next=next->next;
+ }
+ /* find the roots */
+ next=*list;
+ while (next) {
+ struct sort_node * node = (struct sort_node *)next->item->object.util;
+
+ if (node->indegree == 0) {
+ commit_list_insert(next->item, &work);
+ }
+ next=next->next;
+ }
You say "find the roots", but this sounds more like finding the
tips of forests. You are finding people without children,
right (again, not a nitpick but trying to understand the code)?
+ /* process the list in topological order */
+ while (work) {
+ struct commit * work_item = pop_commit(&work);
+ struct sort_node * work_node = (struct sort_node *)work_item->object.util;
+ struct commit_list * parents = work_item->parents;
+
+ while (parents) {
+ struct commit * parent=parents->item;
+ struct sort_node * pn = (struct sort_node *)parent->object.util;
+
+ if (pn) {
+ pn->indegree--;
+ if (!pn->indegree)
+ commit_list_insert(parent, &work);
And when you look at each parent, and push the parent into work
queue when you have seen all its children.
+ }
+ parents=parents->next;
+ }
And at this point work_item, popped from your work queue, is
guaranteed to be a commit all of whose children have been
processed (i.e. pushed into the original *list).
+ *pptr = work_node->list_item;
+ work_node->list_item->next = NULL;
+ pptr = &(*pptr)->next;
+ work_item->object.util = NULL;
+ }
+ free(nodes);
+}
By the way, you seem to be using "git format-patch". Do you
want to help me pushing it upstream ;-)?
^ permalink raw reply
* Re: new features in gitk
From: Junio C Hamano @ 2005-06-30 6:20 UTC (permalink / raw)
To: Paul Mackerras; +Cc: git
In-Reply-To: <17088.31798.17291.605567@cargo.ozlabs.ibm.com>
Finally I started converting my workflow of day-job I do on my
home machine from darcs to git, so I started running cvs2git
over ssh slurping from my office environment (sloooooooooow).
While I was watching the import going, I started up gitk on the
halfway imported repository, and it showed Japanese characters
in the source correctly without any special configuration (the
only thing I have is LC_CTYPE=ja_JP). Very often GUIish
software would not work properly for me with Japanese
characters, and this was a pleasant surprise.
The credit is probably owed more to tk, not something you do
special in gitk, but nevertheless I am impressed and happy ;-).
^ permalink raw reply
* [PATCH 1/1] Add a topological sort procedure to commit.c
From: Jon Seymour @ 2005-06-30 5:58 UTC (permalink / raw)
To: git; +Cc: torvalds, jon.seymour
This patch introduces an in-place topological sort procedure to commit.c
Given a list of commits, sort_in_topological_order() will perform an in-place
topological sort of that list.
The invariant that applies to the resulting list is:
a reachable from b => ord(b) < ord(a)
This invariant is weaker than the --merge-order invariant, but is cheaper
to calculate (assuming the list has been identified) and will serve any
purpose where only a minimal topological order guarantee is required.
Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
Note: this patch currently has no observable consequences since nothing
in this patch calls it. A future patch will use this algorithm to provide
an O(n) bisection algorithm as a suggested replacement for the
existing O(n^2) bisection algorithm.
---
commit.c | 82 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
commit.h | 5 ++++
2 files changed, 87 insertions(+), 0 deletions(-)
9beb76a20443b8d5ee6010bf0bd55344e5b39546
diff --git a/commit.c b/commit.c
--- a/commit.c
+++ b/commit.c
@@ -3,6 +3,12 @@
#include "commit.h"
#include "cache.h"
+struct sort_node
+{
+ unsigned int indegree;
+ struct commit_list * list_item;
+};
+
const char *commit_type = "commit";
enum cmit_fmt get_commit_format(const char *arg)
@@ -346,3 +352,79 @@ int count_parents(struct commit * commit
return count;
}
+/*
+ * Performs an in-place topological sort on the list supplied
+ */
+void sort_in_topological_order(struct commit_list ** list)
+{
+ struct commit_list * next = *list;
+ struct commit_list * work = NULL;
+ struct commit_list ** pptr = list;
+ struct sort_node * nodes;
+ struct sort_node * next_nodes;
+ int count = 0;
+
+ /* determine the size of the list */
+ while (next) {
+ next = next->next;
+ count++;
+ }
+ /* allocate an array to help sort the list */
+ nodes = xmalloc(sizeof(*nodes) * count);
+ /* link the list to the array */
+ next_nodes = nodes;
+ next=*list;
+ while (next) {
+ next_nodes->list_item = next;
+ next->item->object.util = next_nodes;
+ next_nodes++;
+ next = next->next;
+ }
+ /* update the indegree */
+ next=*list;
+ while (next) {
+ struct commit_list * parents = next->item->parents;
+ while (parents) {
+ struct commit * parent=parents->item;
+ struct sort_node * pn = (struct sort_node *)parent->object.util;
+
+ if (pn)
+ pn->indegree++;
+ parents=parents->next;
+ }
+ next=next->next;
+ }
+ /* find the roots */
+ next=*list;
+ while (next) {
+ struct sort_node * node = (struct sort_node *)next->item->object.util;
+
+ if (node->indegree == 0) {
+ commit_list_insert(next->item, &work);
+ }
+ next=next->next;
+ }
+ /* process the list in topological order */
+ while (work) {
+ struct commit * work_item = pop_commit(&work);
+ struct sort_node * work_node = (struct sort_node *)work_item->object.util;
+ struct commit_list * parents = work_item->parents;
+
+ while (parents) {
+ struct commit * parent=parents->item;
+ struct sort_node * pn = (struct sort_node *)parent->object.util;
+
+ if (pn) {
+ pn->indegree--;
+ if (!pn->indegree)
+ commit_list_insert(parent, &work);
+ }
+ parents=parents->next;
+ }
+ *pptr = work_node->list_item;
+ work_node->list_item->next = NULL;
+ pptr = &(*pptr)->next;
+ work_item->object.util = NULL;
+ }
+ free(nodes);
+}
diff --git a/commit.h b/commit.h
--- a/commit.h
+++ b/commit.h
@@ -55,4 +55,9 @@ struct commit *pop_most_recent_commit(st
struct commit *pop_commit(struct commit_list **stack);
int count_parents(struct commit * commit);
+
+/*
+ * Performs an in-place topological sort of list supplied.
+ */
+void sort_in_topological_order(struct commit_list ** list);
#endif /* COMMIT_H */
------------
^ permalink raw reply
* Re: [PATCH 2/2] Fix for git-rev-list --merge-order B ^A (A,B share common base)
From: Jon Seymour @ 2005-06-30 2:47 UTC (permalink / raw)
To: Junio C Hamano; +Cc: torvalds, git
In-Reply-To: <2cfc403205062918336a55e8da@mail.gmail.com>
> > Also if you are changing t6001, could you also merge Mark
> > Allen's BSD portability fix while you are at it?
> >
> > Message-ID: <20050628014337.18986.qmail@web41205.mail.yahoo.com>
> >
> >
>
> Ok.
>
Sorry, forgot to do this. However, Mark's patch should still apply as
it is (or will do so with minimal edits), so I'll leave that to Linus'
discretion.
jon.
--
homepage: http://www.zeta.org.au/~jon/
blog: http://orwelliantremors.blogspot.com/
^ permalink raw reply
* [PATCH 3/3] Remove unnecessary sort from t6001 testcase
From: Jon Seymour @ 2005-06-30 2:41 UTC (permalink / raw)
To: git; +Cc: torvalds, jon.seymour
This patch removes an unnecessary sort from the t6001 testcase.
Sorts were previously necessary when testing non --merge-order cases because the output order wasn't
entirely deterministic unless commit date was fixed.
However, commit dates are now fixed, so the need for a sort has disappeared. So the sort
has been removed.
Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
t/t6001-rev-list-merge-order.sh | 16 ++++++++--------
1 files changed, 8 insertions(+), 8 deletions(-)
4a4c2a209c0121314aa444c1c5e361ad43f1848a
diff --git a/t/t6001-rev-list-merge-order.sh b/t/t6001-rev-list-merge-order.sh
--- a/t/t6001-rev-list-merge-order.sh
+++ b/t/t6001-rev-list-merge-order.sh
@@ -408,17 +408,17 @@ test_output_expect_success "max-count 10
| b2
EOF
-test_output_expect_success "max-count 10 - non merge order" 'git-rev-list --max-count=10 l5 | entag | sort' <<EOF
-a2
-a3
+test_output_expect_success "max-count 10 - non merge order" 'git-rev-list --max-count=10 l5' <<EOF
+l5
+l4
+l3
a4
-b3
b4
-c2
+a3
+a2
c3
-l3
-l4
-l5
+c2
+b3
EOF
test_output_expect_success '--max-age=c3, no --merge-order' "git-rev-list --max-age=$(commit_date c3) l5" <<EOF
------------
^ permalink raw reply
* [PATCH 2/3] Fix broken t6001 test case
From: Jon Seymour @ 2005-06-30 2:41 UTC (permalink / raw)
To: git; +Cc: torvalds, jon.seymour
This fix fixes a t/t6001 test case break that was hidden by a bug in the test case infrastructure.
Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
t/t6001-rev-list-merge-order.sh | 6 +++---
1 files changed, 3 insertions(+), 3 deletions(-)
91f6943f32af5ef8057049ca551957c0f8e7816d
diff --git a/t/t6001-rev-list-merge-order.sh b/t/t6001-rev-list-merge-order.sh
--- a/t/t6001-rev-list-merge-order.sh
+++ b/t/t6001-rev-list-merge-order.sh
@@ -408,12 +408,12 @@ test_output_expect_success "max-count 10
| b2
EOF
-test_output_expect_success "max-count 10 - non merge order" 'git-rev-list --max-count=10 l5 | sort' <<EOF
+test_output_expect_success "max-count 10 - non merge order" 'git-rev-list --max-count=10 l5 | entag | sort' <<EOF
+a2
+a3
a4
-b2
b3
b4
-c1
c2
c3
l3
------------
^ permalink raw reply
* [PATCH 1/3] Demonstrate broken t6001 test case function
From: Jon Seymour @ 2005-06-30 2:41 UTC (permalink / raw)
To: git; +Cc: torvalds, jon.seymour
Junio discovered a problem where an actual test case break was hidden because pipelines
are not handled properly by the test infrastructure in t6001.
This patch fixes the broken infrastructure (and demonstrates the break explicitly).
A subsequent patch in this series will fix the test case so that it doesn't fail.
Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
This patch set:
* demonstrates and fixes some broken test infrastructure
* fixes a broken test case that was previously hidden by the broken infrastructure
* simplifies the test case to remove an unnecessary sort.
Although all patches in the set touch the same file, I have broken it into
three smaller patches to highlight the 3 different changes.
This patch set patches assumes that this series has been applied:
[PATCH 1/2] Test case that demonstrates problem with --merge-order ^ processing
[PATCH 2/2] Fix for git-rev-list --merge-order B ^A (A,B share common base) [rev 2]
t/t6001-rev-list-merge-order.sh | 5 ++---
1 files changed, 2 insertions(+), 3 deletions(-)
0b0041e1fdb1b25757b0c861a0832c54b922440b
diff --git a/t/t6001-rev-list-merge-order.sh b/t/t6001-rev-list-merge-order.sh
--- a/t/t6001-rev-list-merge-order.sh
+++ b/t/t6001-rev-list-merge-order.sh
@@ -85,13 +85,12 @@ check_output()
{
_name=$1
shift 1
- if "$@" | entag > $_name.actual
+ if eval "$*" | entag > $_name.actual
then
diff $_name.expected $_name.actual
else
return 1;
fi
-
}
# Turn a reasonable test description into a reasonable test name.
@@ -114,7 +113,7 @@ test_output_expect_success()
[ $# -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"
+ test_expect_success "$_description" "check_output $_name \"$_test\""
}
# --- end of stuff to move ---
------------
^ permalink raw reply
* [PATCH 2/2] Fix for git-rev-list --merge-order B ^A (A,B share common base) [rev 2]
From: Jon Seymour @ 2005-06-30 1:51 UTC (permalink / raw)
To: git; +Cc: torvalds, jon.seymour
This patch makes --merge-order produce the same list as git-rev-list
without --merge-order specified.
In particular, if the graph looks like this:
A
| B
|/
C
|
D
The both git-rev-list B ^A and git-rev-list --merge-order will produce B.
The unit tests have been changed to reflect the fact that the prune
points are now formally part of the start list that is used to perform
the --merge-order sort.
That is: git-rev-list --merge-order A ^D used to produce
= A
| C
It now produces:
^ A
| C
Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
epoch.c | 8 +++-----
t/t6001-rev-list-merge-order.sh | 12 ++++++------
2 files changed, 9 insertions(+), 11 deletions(-)
d402f03f56475c30c3b62577c5a42af09f6b95b8
diff --git a/epoch.c b/epoch.c
--- a/epoch.c
+++ b/epoch.c
@@ -585,11 +585,9 @@ int sort_list_in_merge_order(struct comm
for (; list; list = list->next) {
struct commit *next = list->item;
- if (!(next->object.flags & UNINTERESTING)) {
- if (!(next->object.flags & DUPCHECK)) {
- next->object.flags |= DUPCHECK;
- commit_list_insert(list->item, &reversed);
- }
+ if (!(next->object.flags & DUPCHECK)) {
+ next->object.flags |= DUPCHECK;
+ commit_list_insert(list->item, &reversed);
}
}
diff --git a/t/t6001-rev-list-merge-order.sh b/t/t6001-rev-list-merge-order.sh
--- a/t/t6001-rev-list-merge-order.sh
+++ b/t/t6001-rev-list-merge-order.sh
@@ -367,33 +367,33 @@ test_output_expect_success "three nodes
EOF
test_output_expect_success "linear prune l2 ^root" 'git-rev-list --merge-order --show-breaks l2 ^root' <<EOF
-= l2
+^ l2
| l1
| l0
EOF
test_output_expect_success "linear prune l2 ^l0" 'git-rev-list --merge-order --show-breaks l2 ^l0' <<EOF
-= l2
+^ l2
| l1
EOF
test_output_expect_success "linear prune l2 ^l1" 'git-rev-list --merge-order --show-breaks l2 ^l1' <<EOF
-= l2
+^ l2
EOF
test_output_expect_success "linear prune l5 ^a4" 'git-rev-list --merge-order --show-breaks l5 ^a4' <<EOF
-= l5
+^ l5
| l4
| l3
EOF
test_output_expect_success "linear prune l5 ^l3" 'git-rev-list --merge-order --show-breaks l5 ^l3' <<EOF
-= l5
+^ l5
| l4
EOF
test_output_expect_success "linear prune l5 ^l4" 'git-rev-list --merge-order --show-breaks l5 ^l4' <<EOF
-= l5
+^ l5
EOF
test_output_expect_success "max-count 10 - merge order" 'git-rev-list --merge-order --show-breaks --max-count=10 l5' <<EOF
------------
^ permalink raw reply
* Re: [PATCH 2/2] Fix for git-rev-list --merge-order B ^A (A,B share common base)
From: Jon Seymour @ 2005-06-30 1:33 UTC (permalink / raw)
To: Junio C Hamano; +Cc: torvalds, git
In-Reply-To: <7v1x6k1z6c.fsf@assigned-by-dhcp.cox.net>
On 6/30/05, Junio C Hamano <junkio@cox.net> wrote:
> >>>>> "JS" == Jon Seymour <jon.seymour@gmail.com> writes:
>
> I am puzzled about this part.
>
> JS> The unit test changes in this patch remove use of the --show-breaks
> JS> flags from certain unit tests. The changed --merge-order behaviour
> JS> changed the annotation that --show-breaks prints for certain test cases.
> JS> The new behaviour is reasonable and irrelevant to the intent of the tests
> JS> so that tests have been changed to eliminate the spurious behaviour.
>
> If the behaviour of --show-breaks subtly changes, and if that
> changed behaviour is something still acceptable, why not update
> the test to show the new expected results since you are updating
> the test anyway?
I can do it this way, if you prefer. The issue was that the expected output was:
= l2
| l1
| l0
but became:
^ l2
| l1
| l0
The annotation changes because there is no longer a single head in the
start list. There are now multiple heads, it just happens that one of
the heads is also a prune point.
>
> Showing that "subtle" change in the diff may draw people's
> attention and would help you to verify that the behaviour change
> is not something that would be unacceptable to them.
Fair enough, I'll resubmit with a less drastic change to the test case.
>
> Also if you are changing t6001, could you also merge Mark
> Allen's BSD portability fix while you are at it?
>
> Message-ID: <20050628014337.18986.qmail@web41205.mail.yahoo.com>
>
>
Ok.
jon.
^ permalink raw reply
* Re: [PATCH 2/2] Fix for git-rev-list --merge-order B ^A (A,B share common base)
From: Junio C Hamano @ 2005-06-30 0:11 UTC (permalink / raw)
To: Jon Seymour; +Cc: torvalds, git
In-Reply-To: <20050629234533.28709.qmail@blackcubes.dyndns.org>
>>>>> "JS" == Jon Seymour <jon.seymour@gmail.com> writes:
I am puzzled about this part.
JS> The unit test changes in this patch remove use of the --show-breaks
JS> flags from certain unit tests. The changed --merge-order behaviour
JS> changed the annotation that --show-breaks prints for certain test cases.
JS> The new behaviour is reasonable and irrelevant to the intent of the tests
JS> so that tests have been changed to eliminate the spurious behaviour.
If the behaviour of --show-breaks subtly changes, and if that
changed behaviour is something still acceptable, why not update
the test to show the new expected results since you are updating
the test anyway?
Showing that "subtle" change in the diff may draw people's
attention and would help you to verify that the behaviour change
is not something that would be unacceptable to them.
Also if you are changing t6001, could you also merge Mark
Allen's BSD portability fix while you are at it?
Message-ID: <20050628014337.18986.qmail@web41205.mail.yahoo.com>
^ permalink raw reply
* [PATCH 2/2] Fix for git-rev-list --merge-order B ^A (A,B share common base)
From: Jon Seymour @ 2005-06-29 23:45 UTC (permalink / raw)
To: git; +Cc: torvalds, jon.seymour
This patch makes --merge-order produce the same list as git-rev-list
without --merge-order specified.
In particular, if the graph looks like this:
A
| B
|/
C
|
D
The both git-rev-list B ^A and git-rev-list --merge-order will produce B.
The unit test changes in this patch remove use of the --show-breaks
flags from certain unit tests. The changed --merge-order behaviour
changed the annotation that --show-breaks prints for certain test cases.
The new behaviour is reasonable and irrelevant to the intent of the tests
so that tests have been changed to eliminate the spurious behaviour.
Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
epoch.c | 8 +++-----
t/t6001-rev-list-merge-order.sh | 36 ++++++++++++++++++------------------
2 files changed, 21 insertions(+), 23 deletions(-)
26783f6660e58cc2e988b92050707a6a417cc6ae
diff --git a/epoch.c b/epoch.c
--- a/epoch.c
+++ b/epoch.c
@@ -585,11 +585,9 @@ int sort_list_in_merge_order(struct comm
for (; list; list = list->next) {
struct commit *next = list->item;
- if (!(next->object.flags & UNINTERESTING)) {
- if (!(next->object.flags & DUPCHECK)) {
- next->object.flags |= DUPCHECK;
- commit_list_insert(list->item, &reversed);
- }
+ if (!(next->object.flags & DUPCHECK)) {
+ next->object.flags |= DUPCHECK;
+ commit_list_insert(list->item, &reversed);
}
}
diff --git a/t/t6001-rev-list-merge-order.sh b/t/t6001-rev-list-merge-order.sh
--- a/t/t6001-rev-list-merge-order.sh
+++ b/t/t6001-rev-list-merge-order.sh
@@ -366,34 +366,34 @@ test_output_expect_success "three nodes
= root
EOF
-test_output_expect_success "linear prune l2 ^root" 'git-rev-list --merge-order --show-breaks l2 ^root' <<EOF
-= l2
-| l1
-| l0
+test_output_expect_success "linear prune l2 ^root" 'git-rev-list --merge-order l2 ^root' <<EOF
+l2
+l1
+l0
EOF
-test_output_expect_success "linear prune l2 ^l0" 'git-rev-list --merge-order --show-breaks l2 ^l0' <<EOF
-= l2
-| l1
+test_output_expect_success "linear prune l2 ^l0" 'git-rev-list --merge-order l2 ^l0' <<EOF
+l2
+l1
EOF
-test_output_expect_success "linear prune l2 ^l1" 'git-rev-list --merge-order --show-breaks l2 ^l1' <<EOF
-= l2
+test_output_expect_success "linear prune l2 ^l1" 'git-rev-list --merge-order l2 ^l1' <<EOF
+l2
EOF
-test_output_expect_success "linear prune l5 ^a4" 'git-rev-list --merge-order --show-breaks l5 ^a4' <<EOF
-= l5
-| l4
-| l3
+test_output_expect_success "linear prune l5 ^a4" 'git-rev-list --merge-order l5 ^a4' <<EOF
+l5
+l4
+l3
EOF
-test_output_expect_success "linear prune l5 ^l3" 'git-rev-list --merge-order --show-breaks l5 ^l3' <<EOF
-= l5
-| l4
+test_output_expect_success "linear prune l5 ^l3" 'git-rev-list --merge-order l5 ^l3' <<EOF
+l5
+l4
EOF
-test_output_expect_success "linear prune l5 ^l4" 'git-rev-list --merge-order --show-breaks l5 ^l4' <<EOF
-= l5
+test_output_expect_success "linear prune l5 ^l4" 'git-rev-list --merge-order l5 ^l4' <<EOF
+l5
EOF
test_output_expect_success "max-count 10 - merge order" 'git-rev-list --merge-order --show-breaks --max-count=10 l5' <<EOF
------------
^ permalink raw reply
* [PATCH 1/2] Test case that demonstrates problem with --merge-order ^ processing
From: Jon Seymour @ 2005-06-29 23:45 UTC (permalink / raw)
To: git; +Cc: torvalds, jon.seymour
Added a test case that shows that --merge-order doesn't produce the
correct result in the following case.
A
|
| B
|/
C
|
D
git-rev-list --merge-order A ^B should produce just A. Instead
it produces BCD.
A subsequent patch will fix this defect.
Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
t/t6001-rev-list-merge-order.sh | 5 +++++
1 files changed, 5 insertions(+), 0 deletions(-)
444e7b2e2491309cd7101bd48881743a35837a56
diff --git a/t/t6001-rev-list-merge-order.sh b/t/t6001-rev-list-merge-order.sh
--- a/t/t6001-rev-list-merge-order.sh
+++ b/t/t6001-rev-list-merge-order.sh
@@ -543,6 +543,11 @@ test_output_expect_success 'simple merge
= alt_root
EOF
+test_output_expect_success "don't print things unreachable from one branch" "git-rev-list a3 ^b3 --merge-order" <<EOF
+a3
+a2
+a1
+EOF
#
#
------------
^ permalink raw reply
* Re: git-rev-list --merge-order bug?
From: Jon Seymour @ 2005-06-29 22:40 UTC (permalink / raw)
To: gitzilla; +Cc: Linus Torvalds, Git Mailing List
In-Reply-To: <42C2F30A.7030102@gmail.com>
>
> git-rev-list ee28152d03f2cf4b5e3ebc25f7f03f9654d3aa0d \
> ^aa03413467a2f2ada900817dc2a8e3904549b5fe |wc -l
>
> git-rev-list ee28152d03f2cf4b5e3ebc25f7f03f9654d3aa0d \
> ^aa03413467a2f2ada900817dc2a8e3904549b5fe --merge-order |wc -l
>
> The first git-rev-list returns 4 commits and the second returns 304.
>
I'll look at it.
It appears to do in cases that look like this:
A
| B
| |
| /
C
git-rev-list B ^A --merge-order
jon.
--
homepage: http://www.zeta.org.au/~jon/
blog: http://orwelliantremors.blogspot.com/
^ permalink raw reply
* Re: CAREFUL! No more delta object support!
From: Daniel Barkalow @ 2005-06-29 22:24 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Junio C Hamano, Git Mailing List
In-Reply-To: <Pine.LNX.4.58.0506291435310.14331@ppc970.osdl.org>
On Wed, 29 Jun 2005, Linus Torvalds wrote:
> On Wed, 29 Jun 2005, Daniel Barkalow wrote:
> > The one thing I can think of is whether things will blow up if the target
> > repository has heads that aren't in the source
>
> Right. I think that's a "feature" of pushing: you cannot push to an
> archive that has state that you don't know about. Ie you can only push to
> something that is a proper subset of what you are (on a per-branch basis,
> of course - not necessarily on a "global" stage - so you could push just
> _one_ branch, even if another branch was ahead of where you are).
The issue is really distinguishing the "other" branches I don't care about
from the one that I do care about. With -w, I almost certainly care about
the ref I'm writing, but that doesn't help for refs that are new (new
branches or tags), for which I care about some other thing. Also, the
failure is a bit hard to detect, I think, in that I could find I do
recognize some ancient thing that's barely useful for exclusion, and miss
something that should exclude almost everything but it's been updated. In
any case, when things go wrong we simply send stuff the recipient already
has, so it's not the end of the world. (And there's probably some clever
way of dealing with it)
-Daniel
*This .sig left intentionally blank*
^ permalink raw reply
* Re: Today's kernel git snapshot broke.
From: David Woodhouse @ 2005-06-29 21:53 UTC (permalink / raw)
To: Jeff Garzik; +Cc: git
In-Reply-To: <42C31504.3030502@pobox.com>
On Wed, 2005-06-29 at 17:39 -0400, Jeff Garzik wrote:
> This. Linus uploaded a tag in .git/tags/v2.6.13-rc1, but did not
> upload the associated tag object.
That was naughty of him.
--
dwmw2
^ permalink raw reply
* Re: Today's kernel git snapshot broke.
From: Jeff Garzik @ 2005-06-29 21:39 UTC (permalink / raw)
To: David Woodhouse; +Cc: git
In-Reply-To: <1120078535.3690.12.camel@localhost.localdomain>
David Woodhouse wrote:
> /pub/scm/linux/kernel/git/torvalds/linux-2.6.git/objects/73/3ad933f62e82ebc92fed988c7f0795e64dea62: No such file or directory
> fatal: git-cat-file 733ad933f62e82ebc92fed988c7f0795e64dea62: bad file
> Invalid id: 733ad933f62e82ebc92fed988c7f0795e64dea62
This. Linus uploaded a tag in .git/tags/v2.6.13-rc1, but did not upload
the associated tag object.
Jeff
^ permalink raw reply
* Re: CAREFUL! No more delta object support!
From: Linus Torvalds @ 2005-06-29 21:38 UTC (permalink / raw)
To: Daniel Barkalow; +Cc: Junio C Hamano, Git Mailing List
In-Reply-To: <Pine.LNX.4.21.0506291644120.30848-100000@iabervon.org>
On Wed, 29 Jun 2005, Daniel Barkalow wrote:
>
> > Of course, you can do this one branch at a time, too, if you want to, but
> > the above was meant as an example of how you can actually do all the
> > branches in one single pack-file, which is a lot more efficient (if you do
> > it one branch at a time, you'll quite possible end up transferring objects
> > that are reachable in other branches multiple times, while the "all in one
> > go" thing will pack each object just once).
>
> It should transfer each only once if you recalculate "refs_in_b" after
> each push, right?
Yes, you can do it that way too. It will possibly not pack as well due to
giving you fewer opportunities for deltas, but that's likely not a huge
issue.
> The one thing I can think of is whether things will blow up if the target
> repository has heads that aren't in the source
Right. I think that's a "feature" of pushing: you cannot push to an
archive that has state that you don't know about. Ie you can only push to
something that is a proper subset of what you are (on a per-branch basis,
of course - not necessarily on a "global" stage - so you could push just
_one_ branch, even if another branch was ahead of where you are).
Linus
^ permalink raw reply
* Re: Stacked GIT 0.1 (a.k.a. quilt for git)
From: Paul Jackson @ 2005-06-29 21:28 UTC (permalink / raw)
To: Catalin Marinas; +Cc: git
In-Reply-To: <tnxwtoeiysf.fsf@arm.com>
Catalin wrote:
> Does this make it closer to quilt in functionality?
It could - right now I'm playing with Matt Mackall's Mercurial. Sorry.
--
I won't rest till it's the best ...
Programmer, Linux Scalability
Paul Jackson <pj@sgi.com> 1.925.600.0401
^ permalink raw reply
* [PATCH] Handle commit messages without new line at end correctly
From: Fredrik Kuivinen @ 2005-06-29 21:24 UTC (permalink / raw)
To: git; +Cc: torvalds
Currently, if a commit message doesn't end with a new line the last
line in the message is omitted from the output. The following patch
fixes this bug.
Signed-Off-By: Fredrik Kuivinen <freku045@student.liu.se>
---
diff --git a/commit.c b/commit.c
--- a/commit.c
+++ b/commit.c
@@ -202,11 +202,11 @@ static int get_one_line(const char *msg,
while (len--) {
char c = *msg++;
+ if (!c)
+ break;
ret++;
if (c == '\n')
break;
- if (!c)
- return 0;
}
return ret;
}
^ permalink raw reply
* Re: CAREFUL! No more delta object support!
From: Daniel Barkalow @ 2005-06-29 21:05 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Junio C Hamano, Git Mailing List
In-Reply-To: <Pine.LNX.4.58.0506291142510.14331@ppc970.osdl.org>
On Wed, 29 Jun 2005, Linus Torvalds wrote:
> and you now have moved over _all_ the objects that were referenced in "a",
> but not in "b". Including tags etc. So after that last stage, when you've
> unpacked the objects, the only thing left to do is to make the refs in "b"
> point to the new references from "a" (which basically boils down to a
> "cp", except it would be good to verify that the refs in "b" still have
> the same values as they did before we did the object push).
>
> Daniel (or anybody else), interested? Please?
I'll probably get to this over the weekend.
> Of course, you can do this one branch at a time, too, if you want to, but
> the above was meant as an example of how you can actually do all the
> branches in one single pack-file, which is a lot more efficient (if you do
> it one branch at a time, you'll quite possible end up transferring objects
> that are reachable in other branches multiple times, while the "all in one
> go" thing will pack each object just once).
It should transfer each only once if you recalculate "refs_in_b" after
each push, right? Or is the marking for "--objects ^commit" still not
tight wrt object and tree files? I think branch-at-a-time is preferable
for the case where the source doesn't want to send quite everything, and
the target doesn't necessarily want everything named the same.
> Now, have I actually _tested_ the above? Hell no. But all the heavy
> lifting should now be done for doing an efficient "git push" that pushes
> all branches in one go (or one at a time, it's your choice on how you end
> up using git-rev-list).
The one thing I can think of is whether things will blow up if the target
repository has heads that aren't in the source, at which point the source
has no clue what to exclude. I.e.:
parent -- new-b
\
new-a
If I've moved the head on b forward to new-b, and a wants to push new-a
(as a new branch, perhaps), refs_in_b has only new-b, refs_in_a has parent
and new-a, and git-rev-list in a can't see that b has parent (and
everything upwards of that). You probably just don't want to do this, but
I bet that some people will (e.g. projects that synchronize through a
shared-owner repository).
-Daniel
*This .sig left intentionally blank*
^ permalink raw reply
* Today's kernel git snapshot broke.
From: David Woodhouse @ 2005-06-29 20:55 UTC (permalink / raw)
To: git
[-- Attachment #1: Type: text/plain, Size: 86 bytes --]
What happened here...
(Script at http://david.woodhou.se/git-snapshot.sh)
--
dwmw2
[-- Attachment #2: Forwarded message - Cron <dwmw2@hera> /home/dwmw2/bin/git-snapshot.sh --]
[-- Type: message/rfc822, Size: 7070 bytes --]
From: root@hera.kernel.org (Cron Daemon)
To: dwmw2@hera.kernel.org
Subject: Cron <dwmw2@hera> /home/dwmw2/bin/git-snapshot.sh
Date: Wed, 29 Jun 2005 02:01:02 -0700
Message-ID: <200506290901.j5T91219026133@hera.kernel.org>
+ case `hostname` in
++ hostname
+ export PATH=/home/dwmw2/cogito:/usr/bin:/bin
+ PATH=/home/dwmw2/cogito:/usr/bin:/bin
+ export BASE_DIRECTORY=/pub/scm/linux/kernel/git/torvalds/linux-2.6.git
+ BASE_DIRECTORY=/pub/scm/linux/kernel/git/torvalds/linux-2.6.git
+ STAGINGLOCK=/staging/upload.lock
+ FINAL=/pub/linux/kernel/v2.6/snapshots
+ '[' '!' -d /pub/scm/linux/kernel/git/torvalds/linux-2.6.git ']'
+ export WORK_DIRECTORY=/home/dwmw2/snapshots/2.6
+ WORK_DIRECTORY=/home/dwmw2/snapshots/2.6
+ export SNAP_TAG_DIRECTORY=/home/dwmw2/snapshots/2.6/tags
+ SNAP_TAG_DIRECTORY=/home/dwmw2/snapshots/2.6/tags
+ export STAGE=/home/dwmw2/snapshots/2.6/stage
+ STAGE=/home/dwmw2/snapshots/2.6/stage
+ export SHA1_FILE_DIRECTORY=/pub/scm/linux/kernel/git/torvalds/linux-2.6.git/objects
+ SHA1_FILE_DIRECTORY=/pub/scm/linux/kernel/git/torvalds/linux-2.6.git/objects
++ ls -rt /pub/scm/linux/kernel/git/torvalds/linux-2.6.git/refs/tags/v2.6.11 /pub/scm/linux/kernel/git/torvalds/linux-2.6.git/refs/tags/v2.6.11-tree /pub/scm/linux/kernel/git/torvalds/linux-2.6.git/refs/tags/v2.6.12 /pub/scm/linux/kernel/git/torvalds/linux-2.6.git/refs/tags/v2.6.12-rc2 /pub/scm/linux/kernel/git/torvalds/linux-2.6.git/refs/tags/v2.6.12-rc3 /pub/scm/linux/kernel/git/torvalds/linux-2.6.git/refs/tags/v2.6.12-rc4 /pub/scm/linux/kernel/git/torvalds/linux-2.6.git/refs/tags/v2.6.12-rc5 /pub/scm/linux/kernel/git/torvalds/linux-2.6.git/refs/tags/v2.6.12-rc6 /pub/scm/linux/kernel/git/torvalds/linux-2.6.git/refs/tags/v2.6.13-rc1
++ tail -n1
++ sed s:/pub/scm/linux/kernel/git/torvalds/linux-2.6.git/refs/tags/v::
+ RELNAME=2.6.13-rc1
++ cat /pub/scm/linux/kernel/git/torvalds/linux-2.6.git/refs/tags/v2.6.13-rc1
+ RELOBJ=733ad933f62e82ebc92fed988c7f0795e64dea62
++ tail -n1
++ sed s:/home/dwmw2/snapshots/2.6/tags/v::
++ ls -rt '/home/dwmw2/snapshots/2.6/tags/v2.6.13-rc1-git*'
ls: /home/dwmw2/snapshots/2.6/tags/v2.6.13-rc1-git*: No such file or directory
+ SNAPNAME=
+ '[' '' == '' ']'
+ LASTOBJ=733ad933f62e82ebc92fed988c7f0795e64dea62
+ CURNAME=2.6.13-rc1-git1
++ tree-id 733ad933f62e82ebc92fed988c7f0795e64dea62
/pub/scm/linux/kernel/git/torvalds/linux-2.6.git/objects/73/3ad933f62e82ebc92fed988c7f0795e64dea62: No such file or directory
fatal: git-cat-file 733ad933f62e82ebc92fed988c7f0795e64dea62: bad file
Invalid id: 733ad933f62e82ebc92fed988c7f0795e64dea62
usage: git-cat-file [-t | tagname] <sha1>
usage: git-cat-file [-t | tagname] <sha1>
Invalid id:
+ LASTTREE=
++ cat /pub/scm/linux/kernel/git/torvalds/linux-2.6.git/HEAD
+ CURCOMM=4c91aedb75d1b87deccf16d58f67fb46402d7d44
++ tree-id 4c91aedb75d1b87deccf16d58f67fb46402d7d44
+ CURTREE=9fba45e2b1a769b0f984fa7b780020256ed3b9ba
++ tree-id 733ad933f62e82ebc92fed988c7f0795e64dea62
/pub/scm/linux/kernel/git/torvalds/linux-2.6.git/objects/73/3ad933f62e82ebc92fed988c7f0795e64dea62: No such file or directory
fatal: git-cat-file 733ad933f62e82ebc92fed988c7f0795e64dea62: bad file
Invalid id: 733ad933f62e82ebc92fed988c7f0795e64dea62
usage: git-cat-file [-t | tagname] <sha1>
usage: git-cat-file [-t | tagname] <sha1>
Invalid id:
+ RELTREE=
+ echo release 2.6.13-rc1 commit tree
release 2.6.13-rc1 commit tree
++ git-cat-file -t 733ad933f62e82ebc92fed988c7f0795e64dea62
/pub/scm/linux/kernel/git/torvalds/linux-2.6.git/objects/73/3ad933f62e82ebc92fed988c7f0795e64dea62: No such file or directory
fatal: git-cat-file 733ad933f62e82ebc92fed988c7f0795e64dea62: bad file
+ echo last 733ad933f62e82ebc92fed988c7f0795e64dea62 tree
last 733ad933f62e82ebc92fed988c7f0795e64dea62 tree
+ echo head 4c91aedb75d1b87deccf16d58f67fb46402d7d44 tree 9fba45e2b1a769b0f984fa7b780020256ed3b9ba
head 4c91aedb75d1b87deccf16d58f67fb46402d7d44 tree 9fba45e2b1a769b0f984fa7b780020256ed3b9ba
+ '[' '' == 9fba45e2b1a769b0f984fa7b780020256ed3b9ba ']'
++ echo 2.6.13-rc1-git1
++ cut -f2- -d-
+ EXTRAVERSION=-rc1-git1
+ cd /home/dwmw2/snapshots/2.6/stage
+ rm -rf tmp-empty-tree
+ mkdir -p tmp-empty-tree/.git
+ cd tmp-empty-tree
+ git-read-tree 4c91aedb75d1b87deccf16d58f67fb46402d7d44
+ git-checkout-cache Makefile
+ perl -pi -e 's/EXTRAVERSION =.*/EXTRAVERSION = -rc1-git1/' Makefile
+ git-diff-cache -m -p
+ gzip -9
usage: diff-cache [-r] [-z] [-p] [-i] [--cached] <tree sha1>
+ echo 4c91aedb75d1b87deccf16d58f67fb46402d7d44
+ cg-log 733ad933f62e82ebc92fed988c7f0795e64dea62:4c91aedb75d1b87deccf16d58f67fb46402d7d44
mv: cannot stat `.git/heads': No such file or directory
mv: cannot stat `.git/tags': No such file or directory
/pub/scm/linux/kernel/git/torvalds/linux-2.6.git/objects/73/3ad933f62e82ebc92fed988c7f0795e64dea62: No such file or directory
fatal: git-cat-file 733ad933f62e82ebc92fed988c7f0795e64dea62: bad file
Invalid id: 733ad933f62e82ebc92fed988c7f0795e64dea62
+ echo 4c91aedb75d1b87deccf16d58f67fb46402d7d44
+ echo New Snapshot 2.6.13-rc1-git1
New Snapshot 2.6.13-rc1-git1
+ '[' -z /pub/linux/kernel/v2.6/snapshots ']'
+ '[' -r /staging/upload.lock ']'
+ exec
+ flock -s 200
+ mv -v /home/dwmw2/snapshots/2.6/stage/patch-2.6.13-rc1-git1.gz /home/dwmw2/snapshots/2.6/stage/patch-2.6.13-rc1-git1.id /home/dwmw2/snapshots/2.6/stage/patch-2.6.13-rc1-git1.log /pub/linux/kernel/v2.6/snapshots
`/home/dwmw2/snapshots/2.6/stage/patch-2.6.13-rc1-git1.gz' -> `/pub/linux/kernel/v2.6/snapshots/patch-2.6.13-rc1-git1.gz'
`/home/dwmw2/snapshots/2.6/stage/patch-2.6.13-rc1-git1.id' -> `/pub/linux/kernel/v2.6/snapshots/patch-2.6.13-rc1-git1.id'
`/home/dwmw2/snapshots/2.6/stage/patch-2.6.13-rc1-git1.log' -> `/pub/linux/kernel/v2.6/snapshots/patch-2.6.13-rc1-git1.log'
^ permalink raw reply
* Re: [PATCH] cvsimport: rewritten in Perl
From: Matthias Urlichs @ 2005-06-29 20:40 UTC (permalink / raw)
To: git
In-Reply-To: <Pine.LNX.4.63.0506291048140.1667@localhost.localdomain>
Hi, Nicolas Pitre wrote:
> ftp.kernel.org/pub/scm/linux/kernel/bkcvs/linux-2.5/
Oh well, I'll have a look. (I never bothered with bk2cvs; there's a
better tool which does bk2git directly.)
> New scripts/lxdialog/yesno.c: 0 bytes.
0-byte files are quite common in real-world repositories, so
throwing an error when I see one won't work.
> Can't exec "git-update-cache": Argument list too long at
> /home/nico/bin/git-cvsimport-script line 402, <CVS> line 8254.
That, at least, is easily fixable, I'll do a followup patch.
--
Matthias Urlichs | {M:U} IT Design @ m-u-it.de | smurf@smurf.noris.de
Disclaimer: The quote was selected randomly. Really. | http://smurf.noris.de
- -
"A 'meaning of life' removes the overriding fear that existance is
useless -- while denying the fact that living is its own greatest reward."
[Fredric Rice, HolySmoke, December 1996]
^ permalink raw reply
* git-rev-list --merge-order bug?
From: A Large Angry SCM @ 2005-06-29 19:14 UTC (permalink / raw)
To: git
I've noticed that git-rev-list will sometimes return a different
*number* of commit objects depending on whether the "--merge-order"
switch was used.
For example:
Get a copy of Linus' git git repository from rsync.kernel.org and try
the following:
git-rev-list ee28152d03f2cf4b5e3ebc25f7f03f9654d3aa0d \
^aa03413467a2f2ada900817dc2a8e3904549b5fe |wc -l
git-rev-list ee28152d03f2cf4b5e3ebc25f7f03f9654d3aa0d \
^aa03413467a2f2ada900817dc2a8e3904549b5fe --merge-order |wc -l
The first git-rev-list returns 4 commits and the second returns 304.
Those commits are dated 2005-05-03 and 2005-05-02. If you use gitk,
search for ``builtin'' which will jump to the merge base of the 2 branches.
^ permalink raw reply
* Re: CAREFUL! No more delta object support!
From: Linus Torvalds @ 2005-06-29 18:59 UTC (permalink / raw)
To: Junio C Hamano; +Cc: Git Mailing List, Daniel Barkalow
In-Reply-To: <Pine.LNX.4.58.0506271910390.19755@ppc970.osdl.org>
On Mon, 27 Jun 2005, Linus Torvalds wrote:
>
> On Mon, 27 Jun 2005, Junio C Hamano wrote:
> >
> > Shouldn't feeding "git-rev-list --object" output plus
> > handcrafted list of objects in 2.6.11 tree object to
> > git-pack-objects just work???
>
> You could do that. And yes, we can add support for "tag" objects too
> (which the packing doesn't do at all right now. So this is not a
> "fundamental" problem, it's just a practical one right now.
Ok, I've added the logic to "git-rev-list --object" to handle arbitrary
object dependencies.
So you can do things like this, if you want to:
git-rev-list --object HEAD ^v2.6.11-tree
which basically generates the complete list of every object reachable from
HEAD, but not reachable from the v2.6.11 tree. It also understands about
tags, so if you do
git-rev-list --object v2.6.12 ^v2.6.11-tree
the end result will have the "v2.6.12" tag in it (along with all the
objects reachable from it, but not reachable from v2.6.11-tree).
What does this mean? It means that you can do a "push" from repository "a"
to repository "b" by doing
- in "b", do
refs_in_b=($(find .git/refs -type f | xargs cat))
- in "a" do
refs_in_a=($(find .git/refs -type f | xargs cat))
- then, in "a", do
git-rev-list "${refs_in_a[@]}" --not "${refs_in_b[@]}" |
git-pack-objects --stdout > push.pack
to generate the objects pack in "push.pack"
- then, in "b", do
git-unpack-objects < push.pack
and you now have moved over _all_ the objects that were referenced in "a",
but not in "b". Including tags etc. So after that last stage, when you've
unpacked the objects, the only thing left to do is to make the refs in "b"
point to the new references from "a" (which basically boils down to a
"cp", except it would be good to verify that the refs in "b" still have
the same values as they did before we did the object push).
Daniel (or anybody else), interested? Please?
Of course, you can do this one branch at a time, too, if you want to, but
the above was meant as an example of how you can actually do all the
branches in one single pack-file, which is a lot more efficient (if you do
it one branch at a time, you'll quite possible end up transferring objects
that are reachable in other branches multiple times, while the "all in one
go" thing will pack each object just once).
Now, have I actually _tested_ the above? Hell no. But all the heavy
lifting should now be done for doing an efficient "git push" that pushes
all branches in one go (or one at a time, it's your choice on how you end
up using git-rev-list).
Linus
^ permalink raw reply
* Re: [PATCH] Add git-verify-pack command.
From: Linus Torvalds @ 2005-06-29 16:15 UTC (permalink / raw)
To: Junio C Hamano; +Cc: git
In-Reply-To: <7vvf3xcwyo.fsf_-_@assigned-by-dhcp.cox.net>
On Wed, 29 Jun 2005, Junio C Hamano wrote:
>
> *** Linus, what would be the practical/recommended/sane limit
> *** for mmap regions we would want to use? Currently I start
> *** throwing away mapped packs when the total size of mapped
> *** packs exceeds 64MB.
Hey, anybody who ever used BK had better have had 1GB of memory for any
real development. So 64MB is peanuts, but it sounds like a good guess.
> *** Oh, again, Linus, what is your preferred way to get a
> *** cover-letter material (like this) for a single patch?
I don't want cover-letters for single patches, or necessarily even for
short series (1-3 entries). The cover letter is more interesting for large
series, or even with small series if the early patches don't make much
sense on their own: then the cover-letter ends up being a useful place to
explain what the _sequence_ does, and why patch #2 that seems to be
totally useless and removes a feature is actually good ("we'll
re-implement it better in #5 after we've cleaned the code up").
So generally commentaries after the three dashes is good, if the
commentary is "local", ie related not to a series. Only with non-local
explanations does a separate [0/N] thing make sense to me.
Linus
^ 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