* 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: [PATCH 1/1] Add a topological sort procedure to commit.c
From: Jon Seymour @ 2005-06-30 7:00 UTC (permalink / raw)
To: Junio C Hamano; +Cc: Linus Torvalds, git
In-Reply-To: <7v1x6k5oau.fsf@assigned-by-dhcp.cox.net>
On 6/30/05, Junio C Hamano <junkio@cox.net> wrote:
> 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()?
Oops, yes I do.
>
> + 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?
>
Yes, that is the current assumption. Alternatively, I could save the current
version of object.util in the temporary structure and restore it when done.
Perhaps I'll do that.
> So sort_node->indegree means how many children of it are on the
> *list. Am I reading you correctly so far?
Correct.
>
> + 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)?
True. Should reword the comment to find the tips.
>
> + /* 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.
Correct.
>
> + }
> + 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).
Yep.
>
> + *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 ;-)?
Yep, but can you fix the PATCH 1/1 thing first :-)
I'll rework the patch, incorporating answers to your questions into the comment.
Regards,
jon.
^ permalink raw reply
* Re: [PATCH 1/1] Add a topological sort procedure to commit.c
From: Junio C Hamano @ 2005-06-30 7:13 UTC (permalink / raw)
To: jon; +Cc: Linus Torvalds, git
In-Reply-To: <2cfc403205063000009d149f5@mail.gmail.com>
>>>>> "JS" == Jon Seymour <jon.seymour@gmail.com> writes:
>> By the way, you seem to be using "git format-patch". Do you
>> want to help me pushing it upstream ;-)?
JS> Yep, but can you fix the PATCH 1/1 thing first :-)
Fix how? Only special case 1/1?
That is easy to do, so I would do it, but on the other hand I
always end up editing the line anyway (my [PATCH 2/3] is often
originally [PATCH 4/7] because I have more than one series since
forked from upstream, and I would need to move it to Subject:
line), so it would not help very much, at least in my case.
^ permalink raw reply
* [PATCH] Add a topological sort procedure to commit.c [rev 2]
From: Jon Seymour @ 2005-06-30 7:21 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.
[rev2]
* incorporates Junio's questions/comments as commentary,
* adds object.util save/restore functionality so that no
assumption is made about the pre-existing state of object.util
upon entry to the procedure.
---
commit.c | 117 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
commit.h | 5 +++
2 files changed, 122 insertions(+), 0 deletions(-)
2e031457909e59ac00c3520206256b75a6e08062
diff --git a/commit.c b/commit.c
--- a/commit.c
+++ b/commit.c
@@ -3,6 +3,27 @@
#include "commit.h"
#include "cache.h"
+struct sort_node
+{
+ /*
+ * the number of children of the associated commit
+ * that also occur in the list being sorted.
+ */
+ unsigned int indegree;
+
+ /*
+ * reference to original list item that we will re-use
+ * on output.
+ */
+ struct commit_list * list_item;
+
+ /*
+ * copy of original object.util pointer that is saved
+ * during the topological sort.
+ */
+ void * save_util;
+};
+
const char *commit_type = "commit";
enum cmit_fmt get_commit_format(const char *arg)
@@ -346,3 +367,99 @@ int count_parents(struct commit * commit
return count;
}
+/*
+ * Performs an in-place topological sort on the list supplied
+ *
+ * Invariant of resulting list is:
+ * a reachable from b => ord(b) < ord(a)
+ */
+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 = xcalloc(count, sizeof(*nodes));
+ /* link the list to the array */
+ next_nodes = nodes;
+ next=*list;
+ while (next) {
+ next_nodes->list_item = next;
+ next_nodes->save_util = next->item->object.util;
+ 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 tips
+ *
+ * tips are nodes not reachable from any other node in the list
+ *
+ * the tips serve as a starting set for the work queue.
+ */
+ 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) {
+ /*
+ * parents are only enqueed for emission
+ * when all their children have been emitted thereby
+ * guaranteeing topological order.
+ */
+ pn->indegree--;
+ if (!pn->indegree)
+ commit_list_insert(parent, &work);
+ }
+ parents=parents->next;
+ }
+ /*
+ * work_item is a commit all of whose children
+ * have already been emitted. we can emit it now
+ * and restore its util pointer.
+ */
+ *pptr = work_node->list_item;
+ pptr = &(*pptr)->next;
+ *pptr = NULL;
+ work_item->object.util = work_node->save_util;
+ }
+ 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
* [PATCH] git-format-patch: Prepare patches for e-mail submission.
From: Junio C Hamano @ 2005-06-30 7:36 UTC (permalink / raw)
To: Linus Torvalds; +Cc: jon, git
In-Reply-To: <7vwtoc48rh.fsf@assigned-by-dhcp.cox.net>
This is the script I use to prepare patches for e-mail submission.
Signed-off-by: Junio C Hamano <junkio@cox.net>
---
*** Jon, I made it by default not to say [PATCH N/M] for any M,
*** and you can turn it on with --numbered flag. Even with
*** --numbered, " N/M" is not shown if M==1.
Makefile | 3 +
git-format-patch-script | 122 +++++++++++++++++++++++++++++++++++++++++++++++
2 files changed, 124 insertions(+), 1 deletions(-)
create mode 100755 git-format-patch-script
16daa73282d5aa1cc7d227945aea193553fdfaad
diff --git a/Makefile b/Makefile
--- a/Makefile
+++ b/Makefile
@@ -25,7 +25,8 @@ SCRIPTS=git git-apply-patch-script git-m
git-fetch-script git-status-script git-commit-script \
git-log-script git-shortlog git-cvsimport-script git-diff-script \
git-reset-script git-add-script git-checkout-script git-clone-script \
- gitk git-cherry git-rebase-script git-relink-script
+ gitk git-cherry git-rebase-script git-relink-script \
+ git-format-patch-script
PROG= git-update-cache git-diff-files git-init-db git-write-tree \
git-read-tree git-commit-tree git-cat-file git-fsck-cache \
diff --git a/git-format-patch-script b/git-format-patch-script
new file mode 100755
--- /dev/null
+++ b/git-format-patch-script
@@ -0,0 +1,122 @@
+#!/bin/sh
+#
+# Copyright (c) 2005 Junio C Hamano
+#
+
+usage () {
+ echo >&2 "usage: $0"' [-n] [-o dir] [-<diff options>...] upstream [ our-head ]
+
+Prepare each commit with its patch since our-head forked from upstream,
+one file per patch, for e-mail submission. Each output file is
+numbered sequentially from 1, and uses the first line of the commit
+message (massaged for pathname safety) as the filename.
+
+When -o is specified, output files are created in that directory; otherwise in
+the current working directory.
+
+When -n is specified, instead of "[PATCH] Subject", the first line is formatted
+as "[PATCH N/M] Subject", unless you have only one patch.
+'
+ exit 1
+}
+
+diff_opts=
+IFS='
+'
+LF='
+'
+outdir=./
+
+while case "$#" in 0) break;; esac
+do
+ case "$1" in
+ -n|--n|--nu|--num|--numb|--numbe|--number|--numbere|--numbered)
+ numbered=t ;;
+ -o=*|--o=*|--ou=*|--out=*|--outp=*|--outpu=*|--output=*|--output-=*|\
+ --output-d=*|--output-di=*|--output-dir=*|--output-dire=*|\
+ --output-direc=*|--output-direct=*|--output-directo=*|\
+ --output-director=*|--output-directory=*)
+ outdir=`expr "$1" : '-[^=]*=\(.*\)'` ;;
+ -o|--o|--ou|--out|--outp|--outpu|--output|--output-|--output-d|\
+ --output-di|--output-dir|--output-dire|--output-direc|--output-direct|\
+ --output-directo|--output-director|--output-directory)
+ case "$#" in 1) usage ;; esac; shift
+ outdir="$1" ;;
+ -*) diff_opts="$diff_opts$LF$1" ;;
+ *) break ;;
+ esac
+ shift
+done
+
+case "$#" in
+2) linus="$1" junio="$2" ;;
+1) linus="$1" junio=HEAD ;;
+*) usage ;;
+esac
+
+case "$outdir" in
+*/) ;;
+*) outdir="$outdir/" ;;
+esac
+test -d "$outdir" || mkdir -p "$outdir" || exit
+
+tmp=.tmp-series$$
+trap 'rm -f $tmp-*' 0 1 2 3 15
+
+series=$tmp-series
+
+titleScript='
+ 1,/^$/d
+ : loop
+ /^$/b loop
+ s/[^-a-z.A-Z_0-9]/-/g
+ s/\.\.\.*/\./g
+ s/\.*$//
+ s/--*/-/g
+ s/^-//
+ s/-$//
+ s/$/./
+ q
+'
+
+_x40='[0-9a-f][0-9a-f][0-9a-f][0-9a-f][0-9a-f]'
+_x40="$_x40$_x40$_x40$_x40$_x40$_x40$_x40$_x40"
+stripCommitHead='/^'"$_x40"' (from '"$_x40"')$/d'
+
+git-rev-list "$junio" "^$linus" >$series
+total=`wc -l <$series`
+i=$total
+while read commit
+do
+ title=`git-cat-file commit "$commit" | sed -e "$titleScript"`
+ case "$numbered" in
+ '') num= ;;
+ *)
+ case $total in
+ 1) num= ;;
+ *) num=' '`printf "%d/%d" $i $total` ;;
+ esac
+ esac
+ file=`printf '%04d-%stxt' $i "$title"`
+ i=`expr "$i" - 1`
+ echo "$file"
+ {
+ mailScript='
+ 1,/^$/d
+ : loop
+ /^$/b loop
+ s|^|[PATCH'"$num"'] |
+ : body
+ p
+ n
+ b body'
+
+ git-cat-file commit "$commit" | sed -ne "$mailScript"
+ echo '---'
+ echo
+ git-diff-tree -p $diff_opts "$commit" | git-apply --stat --summary
+ echo
+ git-diff-tree -p $diff_opts "$commit" | sed -e "$stripCommitHead"
+ echo '------------'
+ } >"$outdir$file"
+done <$series
------------
^ permalink raw reply
* [EXPERIMENTAL PATCH] O(n) bisection algorithm
From: Jon Seymour @ 2005-06-30 8:11 UTC (permalink / raw)
To: git; +Cc: torvalds, jon.seymour
This is a rollup of an experimental patch to Linus' HEAD that adds
a O(n) bisection algorithm to git.
For the purposes of comparison, this version:
* enables debugging (-DDEBUG)
* adds a --debug switch to git-rev-list
* adds a --bisect-by-cut switch to git-rev-list
This allows the same git-rev-list binary to be used to compare the existing
O(n^2) behaviour (--bisect) with the O(n) behaviour (--bisect-by-cut).
A measure of complexity of each algorithm can be obtained on stderr,
by using the --debug switch.
My measurements suggest that on a 2000 commit kernel history, this
algorithm is ~ 5 times faster than the O(n^2) algorithm. If this
is true, it should be ~25 times faster on a 10,000 commit kernel history.
This is the difference between a 16 second bisection and a 0.6 second
bisection on that size repository.
This patch also includes my latest topological sort implementation
so there is no need to apply that separately.
Linus: if you are happy to adopt this as the default bisection
algorithm, I'll rework it as a formal patch submission, meaning that I'll:
* remove the Makefile change
* remove --debug switch
* remove the #ifdef'd DEBUG code
* replace --bisect implementation with --bisect-by-cut implementation
and remove --bisect-by-cut switch
Cleanly applies to Linus HEAD e4b5c7fff47d3a794249ea2da6b9ec4e33e157f3.
Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
Linus: this isn't fit for inclusion in the mainline yet. I have
posted it to the list for review purposes only.
---
Makefile | 2
commit.c | 117 ++++++++++++++++++++++++++++
commit.h | 5 +
rev-list.c | 248 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++--
4 files changed, 361 insertions(+), 11 deletions(-)
83df29ec101718325fbb0c6c8e5dcb891a224edf
diff --git a/Makefile b/Makefile
--- a/Makefile
+++ b/Makefile
@@ -10,7 +10,7 @@
# break unless your underlying filesystem supports those sub-second times
# (my ext3 doesn't).
COPTS=-O2
-CFLAGS=-g $(COPTS) -Wall
+CFLAGS=-DDEBUG -g $(COPTS) -Wall
prefix=$(HOME)
bin=$(prefix)/bin
diff --git a/commit.c b/commit.c
--- a/commit.c
+++ b/commit.c
@@ -3,6 +3,27 @@
#include "commit.h"
#include "cache.h"
+struct sort_node
+{
+ /*
+ * the number of children of the associated commit
+ * that also occur in the list being sorted.
+ */
+ unsigned int indegree;
+
+ /*
+ * reference to original list item that we will re-use
+ * on output.
+ */
+ struct commit_list * list_item;
+
+ /*
+ * copy of original object.util pointer that is saved
+ * during the topological sort.
+ */
+ void * save_util;
+};
+
const char *commit_type = "commit";
enum cmit_fmt get_commit_format(const char *arg)
@@ -346,3 +367,99 @@ int count_parents(struct commit * commit
return count;
}
+/*
+ * Performs an in-place topological sort on the list supplied
+ *
+ * Invariant of resulting list is:
+ * a reachable from b => ord(b) < ord(a)
+ */
+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 = xcalloc(count, sizeof(*nodes));
+ /* link the list to the array */
+ next_nodes = nodes;
+ next=*list;
+ while (next) {
+ next_nodes->list_item = next;
+ next_nodes->save_util = next->item->object.util;
+ 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 tips
+ *
+ * tips are nodes not reachable from any other node in the list
+ *
+ * the tips serve as a starting set for the work queue.
+ */
+ 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) {
+ /*
+ * parents are only enqueed for emission
+ * when all their children have been emitted thereby
+ * guaranteeing topological order.
+ */
+ pn->indegree--;
+ if (!pn->indegree)
+ commit_list_insert(parent, &work);
+ }
+ parents=parents->next;
+ }
+ /*
+ * work_item is a commit all of whose children
+ * have already been emitted. we can emit it now
+ * and restore its util pointer.
+ */
+ *pptr = work_node->list_item;
+ pptr = &(*pptr)->next;
+ *pptr = NULL;
+ work_item->object.util = work_node->save_util;
+ }
+ 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 */
diff --git a/rev-list.c b/rev-list.c
--- a/rev-list.c
+++ b/rev-list.c
@@ -5,10 +5,19 @@
#include "blob.h"
#include "epoch.h"
-#define SEEN (1u << 0)
-#define INTERESTING (1u << 1)
-#define COUNTED (1u << 2)
-#define SHOWN (LAST_EPOCH_FLAG << 2)
+#define ABOVE (1u<<1)
+struct bisect_by_cut_node
+{
+ unsigned int flags;
+ unsigned int count;
+ struct commit_list * children;
+ struct commit_list * visible_parents;
+};
+
+#define SEEN (LAST_EPOCH_FLAG << 1)
+#define INTERESTING (LAST_EPOCH_FLAG << 2)
+#define COUNTED (LAST_EPOCH_FLAG << 3)
+#define SHOWN (LAST_EPOCH_FLAG << 4)
static const char rev_list_usage[] =
"usage: git-rev-list [OPTION] commit-id <commit-id>\n"
@@ -34,6 +43,13 @@ static enum cmit_fmt commit_format = CMI
static int merge_order = 0;
static int show_breaks = 0;
static int stop_traversal = 0;
+static int bisect_by_cut_option = 0;
+static struct commit_list * topological_order = NULL;
+static struct commit_list ** t_o_tail = &topological_order;
+#ifdef DEBUG
+static int debug = 0;
+static unsigned int complexity = 0;
+#endif
static void show_commit(struct commit *commit)
{
@@ -95,8 +111,10 @@ static int process_commit(struct commit
return CONTINUE;
}
- show_commit(commit);
-
+ if (!bisect_by_cut_option) {
+ show_commit(commit);
+ } else
+ t_o_tail = &commit_list_insert(commit, t_o_tail)->next;
return CONTINUE;
}
@@ -264,7 +282,7 @@ static int count_distance(struct commit_
while (p) {
nr += count_distance(p);
p = p->next;
- }
+ }
}
}
return nr;
@@ -272,6 +290,9 @@ static int count_distance(struct commit_
static void clear_distance(struct commit_list *list)
{
+#ifdef DEBUG
+ complexity++;
+#endif
while (list) {
struct commit *commit = list->item;
commit->object.flags &= ~COUNTED;
@@ -403,6 +424,196 @@ static struct commit *get_commit_referen
die("%s is unknown object", name);
}
+static inline struct bisect_by_cut_node * get_bisect_by_cut_node(struct commit * commit)
+{
+ return (struct bisect_by_cut_node *)commit->object.util;
+}
+
+#ifdef DEBUG
+static void print_bisect_by_cut_node(struct commit * commit, const char * prefix)
+{
+ struct bisect_by_cut_node * node = get_bisect_by_cut_node(commit);
+ fprintf(stderr, "%s%s %u %d\n", prefix, sha1_to_hex(commit->object.sha1), node->flags, node->count);
+}
+#endif
+
+/*
+ * Find the best bisection point by cutting a topological order in two then
+ * identifying a set of boundary nodes with a reachability known to be
+ * less than the desired bisection point. The boundary is advanced until all nodes
+ * in the boundary have a reachability greater than or equal to the desired
+ * reachability.
+ *
+ * This algorithm is roughly O(kn) where k is a factor related to the typical
+ * amount of parallel branching within the graph and is not related to n.
+ *
+ * The algorithm borrows the notion of making an arbitrary cut in the graph
+ * from the Kernighan-Lin (1969) graph bisection algorithm but differs in
+ * other respects. In particular, by using the topological order to make the
+ * cut the width of the advancing boundary is reduced to some kind of minimum.
+ * Full graph scans (e.g. calls to count_distance()) are avoided except where
+ * absolutely necessary (i.e. a merge node is encountered).
+ */
+struct commit * bisect_by_cut(struct commit_list * topological_order)
+{
+ unsigned int count=0;
+ unsigned int i;
+ struct commit_list * next;
+ struct commit_list * work = NULL;
+ struct commit * best = topological_order->item;
+ struct bisect_by_cut_node * nodes;
+ struct bisect_by_cut_node * next_node;
+ struct commit_list counter;
+ unsigned int fittest, goal;
+
+ counter.next=NULL;
+ /* count the size of the topological order */
+ next=topological_order;
+ while (next) {
+ count++;
+ next = next->next;
+ }
+ fittest=count;
+ i=(count+1)/2;
+ goal=count/2;
+ /* allocate and initialize the bisect_by_cut_node structure */
+ next_node=nodes=xmalloc(sizeof(*nodes)*count);
+ memset(nodes, 0, sizeof(*nodes)*count);
+ /*
+ * initialize the structures for all nodes of interest
+ */
+ next=topological_order;
+ next_node=nodes;
+ while (next) {
+ next->item->object.util=next_node++;
+ next=next->next;
+ }
+ /*
+ * Mark half the nodes as being above the boundary.
+ * Mark nodes that aren't in the topological order as uninteresting.
+ * Initialize lists of visible children and parents.
+ */
+ next=topological_order;
+ next_node=nodes;
+ while (next) {
+ struct commit * next_item = next->item;
+ struct commit_list * parents;
+
+ if (i > 0) {
+ next_node->flags |= ABOVE;
+ i--;
+ }
+ parents=next_item->parents;
+ while (parents) {
+ struct commit * parent = parents->item;
+ struct bisect_by_cut_node * pn = get_bisect_by_cut_node(parent);
+
+ if (pn) {
+ commit_list_insert(next_item, &pn->children);
+ commit_list_insert(parent, &next_node->visible_parents);
+ } else
+ parent->object.flags |= UNINTERESTING;
+ parent->object.flags &= ~COUNTED;
+ parents=parents->next;
+ }
+ next=next->next;
+ next_node++;
+ }
+ /*
+ * Initialize the work queue with commits that are on the boundary
+ * and with <= the desired reachability.
+ *
+ * We know these commits have less than or equal to the desired
+ * reachability because by the definition of the topological order
+ * nodes can only reach nodes to the right of them in the topological
+ * order and by construction, there there are no more than
+ * (count-1)/2 nodes to the right of each node in the boundary.
+ */
+ next=topological_order;
+ next_node=nodes;
+ while (next) {
+ struct commit_list * parents;
+
+ parents=next_node->visible_parents;
+ while (parents) {
+ struct bisect_by_cut_node * pn = get_bisect_by_cut_node(parents->item);
+
+ if ((next_node->flags & ABOVE)
+ && !(pn->flags & ABOVE)
+ && (pn->count == 0)) {
+ counter.item=parents->item;
+ pn->count = count_distance(&counter);
+ clear_distance(topological_order);
+ commit_list_insert(parents->item, &work);
+ }
+ parents=parents->next;
+ }
+ next=next->next;
+ next_node++;
+ }
+ /*
+ * Process the work queue until done.
+ */
+ while (work) {
+ struct commit * work_item = pop_commit(&work);
+ struct bisect_by_cut_node * wn = get_bisect_by_cut_node(work_item);
+ struct commit_list * children = wn->children;
+ unsigned int goal_test = wn->count;
+ unsigned int fitness = (goal_test>goal)?(goal_test-goal):(goal-goal_test);
+
+ if (fitness < fittest) {
+ best = work_item;
+ fittest = fitness;
+ }
+#ifdef DEBUG
+ if (debug) {
+ print_bisect_by_cut_node(work_item, "work ");
+ }
+#endif
+ if (goal_test < goal) {
+ while (children) {
+ struct bisect_by_cut_node * cn
+ = get_bisect_by_cut_node(children->item);
+ if (cn->flags & ABOVE) {
+ /* move the boundary up */
+ cn->flags &= ~ABOVE;
+ if (cn->visible_parents && !cn->visible_parents->next)
+ /*
+ * If the child only has one visible parent
+ * the goal_test increases by one
+ */
+ cn->count = wn->count+1;
+ else {
+ /*
+ * Otherwise, we need to count it explicitly.
+ */
+ counter.item=children->item;
+ cn->count = count_distance(&counter);
+ clear_distance(topological_order);
+ }
+ commit_list_insert(children->item, &work);
+ }
+ children=children->next;
+ }
+ } else if (goal_test > goal)
+ continue;
+ else
+ break; /* can't do better than this */
+ }
+ if (work)
+ free_commit_list(work);
+ /*
+ * reset the util pointers.
+ */
+ next=topological_order;
+ while (next) {
+ next->item->object.util=NULL;
+ next = next->next;
+ }
+ free(nodes);
+ return best;
+}
+
int main(int argc, char **argv)
{
struct commit_list *list = NULL;
@@ -440,6 +651,10 @@ int main(int argc, char **argv)
show_parents = 1;
continue;
}
+ if (!strcmp(arg, "--bisect-by-cut")) {
+ bisect_by_cut_option = 1;
+ continue;
+ }
if (!strcmp(arg, "--bisect")) {
bisect_list = 1;
continue;
@@ -458,7 +673,12 @@ int main(int argc, char **argv)
show_breaks = 1;
continue;
}
-
+#ifdef DEBUG
+ if (!strcmp(arg, "--debug")) {
+ debug = 1;
+ continue;
+ }
+#endif
flags = 0;
if (*arg == '^') {
flags = UNINTERESTING;
@@ -476,12 +696,20 @@ int main(int argc, char **argv)
if (!merge_order) {
if (limited)
list = limit_list(list);
- show_commit_list(list);
+ if (!bisect_by_cut_option)
+ show_commit_list(list);
+ else {
+ sort_in_topological_order(&list);
+ show_commit(bisect_by_cut(list));
+ }
} else {
if (sort_list_in_merge_order(list, &process_commit)) {
die("merge order sort failed\n");
}
}
-
+#ifdef DEBUG
+ if (debug)
+ fprintf(stderr, "complexity=%d\n", complexity);
+#endif
return 0;
}
------------
^ permalink raw reply
* Re: [EXPERIMENTAL PATCH] O(n) bisection algorithm
From: Jon Seymour @ 2005-06-30 9:03 UTC (permalink / raw)
To: git; +Cc: Linus Torvalds
In-Reply-To: <20050630081135.27577.qmail@blackcubes.dyndns.org>
BTW: just in case you are wondering what these variables are for and
why they and the associated code is there...
> +static struct commit_list * topological_order = NULL;
> +static struct commit_list ** t_o_tail = &topological_order;
They are not required. This was a remnant of a previous version that
used the --merge-order code to obtain the topological order. Of
course, the final submission will remove this redundant code.
jon.
^ permalink raw reply
* Re: [PATCH] cvsimport: rewritten in Perl
From: Matthias Urlichs @ 2005-06-30 10:30 UTC (permalink / raw)
To: git
In-Reply-To: <pan.2005.06.29.20.40.37.811830@smurf.noris.de>
Hi, Matthias Urlichs wrote:
> 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.)
>
OK -- pulled, tested.
... though why you'd want the kernel via CVS instead of by direct
BK->GIT import is beyond me. ;-)
>> New scripts/lxdialog/yesno.c: 0 bytes.
>
That's a feature. All the r1.1 CVS versions are zero-byte files, because
they're copied from BK/SCCS 1.0 versions, which are empty too (BK adds
the actual content in revision 1.1).
>> Can't exec "git-update-cache": Argument list too long at
>> /home/nico/bin/git-cvsimport-script line 402, <CVS> line 8254.
>
Fixed; patch mailed separately.
--
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
- -
My mother had a baby once.
-- Jigger
^ permalink raw reply
* [PATCH] cvsimport-in-Perl: Limit the number of arguments to git-update-cache
From: Matthias Urlichs @ 2005-06-30 10:34 UTC (permalink / raw)
To: git
In-Reply-To: <pan.2005.06.28.19.23.08.307486@smurf.noris.de>
A small fix to git-cvsimport-script:
Limit the number of arguments to git-update-cache.
(Limiting their length may make a bit more sense, but I'm lazy.)
Signed-Off-By: Matthias Urlichs <smurf@smurf.noris.de>
---
diff --git a/git-cvsimport-script b/git-cvsimport-script
--- a/git-cvsimport-script
+++ b/git-cvsimport-script
@@ -395,14 +395,32 @@ my $state = 0;
my($patchset,$date,$author,$branch,$ancestor,$tag,$logmsg);
my(@old,@new);
my $commit = sub {
my $pid;
- system("git-update-cache","--force-remove","--",@old) if @old;
- die "Cannot remove files: $?\n" if $?;
- system("git-update-cache","--add","--",@new) if @new;
- die "Cannot add files: $?\n" if $?;
+ while(@old) {
+ my @o2;
+ if(@old > 55) {
+ @o2 = splice(@old,0,50);
+ } else {
+ @o2 = @old;
+ @old = ();
+ }
+ system("git-update-cache","--force-remove","--",@o2);
+ die "Cannot remove files: $?\n" if $?;
+ }
+ while(@new) {
+ my @n2;
+ if(@new > 55) {
+ @n2 = splice(@new,0,50);
+ } else {
+ @n2 = @new;
+ @new = ();
+ }
+ system("git-update-cache","--add","--",@n2);
+ die "Cannot add files: $?\n" if $?;
+ }
$pid = open(C,"-|");
die "Cannot fork: $!" unless defined $pid;
unless($pid) {
exec("git-write-tree");
@@ -478,13 +496,10 @@ my $commit = sub {
or die "Cannot write tag $branch: $!\n";
close(C)
or die "Cannot write tag $branch: $!\n";
print "Created tag '$tag' on '$branch'\n" if $opt_v;
}
-
- @old = ();
- @new = ();
};
while(<CVS>) {
chomp;
if($state == 0 and /^-+$/) {
^ permalink raw reply
* how about this as a basis for git-annotate?
From: lode leroy @ 2005-06-30 12:20 UTC (permalink / raw)
To: git
#!/bin/bash
file="$1"
anno="$file.anno"
prev=""
export GIT_DIFF_OPTS=-u0
rm $anno
touch $anno
revs=`git-rev-list HEAD | tac`
for rev in $revs; do
if [ ! -z "$prev" ]; then
git-diff-tree -p $prev $rev $file \
| sed -e "/^--- /p" \
-e "/^+++ /p" \
-e "/^--- /d" \
-e "/^+++ /d" \
-e "s/^-/-$prev /g" \
-e "s/^+/+$rev /g" | patch $anno
fi
prev=$rev
done
* gives a warning when the diff is empty
* has a problem with "\ No newline at end of file"
^ permalink raw reply
* problem with git-diff-tree -S
From: Paul Mackerras @ 2005-06-30 12:48 UTC (permalink / raw)
To: git
I'm trying to implement a find function in gitk that will find commits
where the patch includes a particular string, using git-diff-tree.
It's not doing what I expect - am I expecting the wrong thing, or is
there a bug in git-diff-tree?
As an example, take commit 92a582ed2757456ca9599f8b4ea2064f2154eb02,
"[IA64] sparse cleanup of TIOCA files". If I put that ID in a file
called id and do:
git-diff-tree --stdin -p <id
the resulting patch includes the lines:
-uint64_t
+static uint64_t
+int sn_topology_open(struct inode *inode, struct file *file);
+int sn_topology_release(struct inode *inode, struct file *file);
+extern struct list_head tioca_list;
Now if I do:
git-diff-tree --stdin -r -s -Ssn_topology <id
I get the ID printed to stdout, but if I do:
git-diff-tree --stdin -r -s -Stioca <id
I get nothing on stdout, and similarly if I use "-Sstatic". What's
going on?
Paul.
^ permalink raw reply
* how about this as a basis for git-annotate?
From: lode leroy @ 2005-06-30 13:55 UTC (permalink / raw)
To: git
#!/bin/bash
file="$1"
anno="$file.anno"
prev=""
export GIT_DIFF_OPTS=-u0
rm $anno
touch $anno
revs=`git-rev-list HEAD | tac`
for rev in $revs; do
if [ ! -z "$prev" ]; then
git-diff-tree -p $prev $rev $file \
| sed -e "/^--- /p" \
-e "/^+++ /p" \
-e "/^--- /d" \
-e "/^+++ /d" \
-e "s/^-/-$prev /g" \
-e "s/^+/+$rev /g" | patch $anno
fi
prev=$rev
done
* gives a warning when the diff is empty
* has a problem with "\ No newline at end of file"
What I tried to do is to reconstruct the file from the diffs,
and prefixing each line with the sha1 of the revision.
After further testing, I see that the implementation I provided does not
work,
because the context is not necessarily from the previous version, but from
/a/ previous version.
Still the idea should work.
So patch needs to ignore the sha1 of the revision.
Maybe git-apply can be modified to do this...?
^ permalink raw reply
* [PATCH] cvsimport: perform string comparison on "HEAD"
From: Sven Verdoolaege @ 2005-06-30 14:55 UTC (permalink / raw)
To: Matthias Urlichs; +Cc: git
In-Reply-To: <pan.2005.06.28.19.23.08.307486@smurf.noris.de>
--
diff --git a/git-cvsimport-script b/git-cvsimport-script
--- a/git-cvsimport-script
+++ b/git-cvsimport-script
@@ -529,7 +529,7 @@ while(<CVS>) {
} elsif($state == 5 and s/^Ancestor branch:\s+//) {
s/\s+$//;
$ancestor = $_;
- $ancestor = $opt_o if $ancestor == "HEAD";
+ $ancestor = $opt_o if $ancestor eq "HEAD";
$state = 6;
} elsif($state == 5) {
$ancestor = undef;
^ permalink raw reply
* Re: [PATCH] cvsimport: rewritten in Perl
From: Sven Verdoolaege @ 2005-06-30 15:02 UTC (permalink / raw)
To: Matthias Urlichs; +Cc: git
In-Reply-To: <pan.2005.06.28.19.23.08.307486@smurf.noris.de>
On Tue, Jun 28, 2005 at 09:23:23PM +0200, Matthias Urlichs wrote:
> I just got my machine blocked from a CVS server which didn't like
> to get hammered with connections.
>
> That was cvs2git's shell script. Which, by the way, is slow as hell.
>
> Appended: a git-cvsimport script, written in Perl, which directly talks
> to the CVS server. If the repository is local, it runs a "cvs server"
> child. It produces the same git repository as Linus' version. It can do
> incremental imports. And it's 20 times faster (on my system, with a
> local CVS repository).
>
Could you try to make the resulting repository compatible
with a repository generated with the old cvs2git ?
This is the original version:
sh-3.00$ git-cat-file commit f6a92a7a774473bce12415200bab2788ea3b18f0
tree a0ec41a61461476c72c3967576225bd4772b6c8f
author risset <risset> 995295631 +0000
committer risset <risset> 995295631 +0000
Initial revision
sh-3.00$
This is your version:
sh-3.00$ git-cat-file commit db3540e3f670d4af4acefc723bab41a077c9300e
tree a0ec41a61461476c72c3967576225bd4772b6c8f
author risset <risset> 995295631 +0000
committer risset <risset> 995295631 +0000
Initial revision
sh-3.00$
Note the extra empty line.
Every commit is now different.
I'd really prefer it if I would not have to do the whole
conversion again.
skimo
^ permalink raw reply
* Re: [PATCH] cvsimport: rewritten in Perl
From: Matthias Urlichs @ 2005-06-30 15:21 UTC (permalink / raw)
To: Sven Verdoolaege; +Cc: git
In-Reply-To: <20050630150239.GA20928@pc117b.liacs.nl>
[-- Attachment #1: Type: text/plain, Size: 610 bytes --]
Hi,
Sven Verdoolaege:
> Could you try to make the resulting repository compatible
> with a repository generated with the old cvs2git ?
>
I believe I did... at least it worked that way two days ago. ;-)
> This is the original version:
Which repository is that?
> I'd really prefer it if I would not have to do the whole
> conversion again.
>
So do I. ;-)
--
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
- -
Imitation is the sincerest form of television.
-- Fred Allen
[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 189 bytes --]
^ permalink raw reply
* Re: [PATCH] cvsimport: perform string comparison on "HEAD"
From: Matthias Urlichs @ 2005-06-30 15:21 UTC (permalink / raw)
To: Sven Verdoolaege; +Cc: git
In-Reply-To: <20050630145528.GA18553@pc117b.liacs.nl>
[-- Attachment #1: Type: text/plain, Size: 518 bytes --]
Hi,
Sven Verdoolaege:
> - $ancestor = $opt_o if $ancestor == "HEAD";
> + $ancestor = $opt_o if $ancestor eq "HEAD";
Duh. Thanks for spotting that. :-/
--
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
- -
I am enough of an artist to draw freely upon my imagination.
Imagination is more important than knowledge.
Knowledge is limited. Imagination encircles the world.
-- Albert Einstein
[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 189 bytes --]
^ permalink raw reply
* Re: [PATCH] cvsimport: rewritten in Perl
From: Sven Verdoolaege @ 2005-06-30 15:44 UTC (permalink / raw)
To: Matthias Urlichs; +Cc: git
In-Reply-To: <20050630152125.GO10850@kiste.smurf.noris.de>
On Thu, Jun 30, 2005 at 05:21:25PM +0200, Matthias Urlichs wrote:
> Sven Verdoolaege:
> > Could you try to make the resulting repository compatible
> > with a repository generated with the old cvs2git ?
> >
> I believe I did... at least it worked that way two days ago. ;-)
>
> > This is the original version:
>
> Which repository is that?
>
That was a private repository, but I tried it on another one
and I see that each commit message has an extra empty line
when compared to both an earlier cvs2git conversion and
"cvs log".
Presumably you have an extraneous "\n" somewhere.
-d :pserver:anonymous@exp-prolog.cs.kuleuven.ac.be:/cvs/dtse/ Polylib
sverdool@pc117b:/local/kul/Polylib> cvs log typemap |tail -n 15
make Polyhedron subclass of Domain
----------------------------
revision 1.2
date: 2001/11/16 16:01:58; author: sven; state: Exp; lines: +15 -1
take array when matrix is needed
----------------------------
revision 1.1
date: 2001/11/06 15:19:44; author: sven; state: Exp;
branches: 1.1.1;
Initial revision
----------------------------
revision 1.1.1.1
date: 2001/11/06 15:19:44; author: sven; state: Exp; lines: +0 -0
=============================================================================
sverdool@pc117b:/local/git/Polylib> cg-log typemap | tail -n 26
commit b53b0121ac62e9fa9cceb2c483e121d6ba1e24ed
tree 8d3d8125b8642a21cb9a5efb4e308f91ede06d56
parent 74d88525870de6c5648580a90920e85f294cae8c
author sven <sven> Mon, 14 Jan 2002 12:48:11 +0000
committer sven <sven> Mon, 14 Jan 2002 12:48:11 +0000
make Polyhedron subclass of Domain
commit df6e38c6efe4f161ee35d60728813ddc0f1cb9cf
tree 43eef31ade1f7a88256e6dff9e66c2e7ca3201db
parent e38797be1f09c649600e681c8c7dc322e2db504d
author sven <sven> Fri, 16 Nov 2001 16:01:58 +0000
committer sven <sven> Fri, 16 Nov 2001 16:01:58 +0000
take array when matrix is needed
commit 4c91382f379478f2ef8b9d875e7c81bddcb3aa57
tree e0ed0e7b11f9fc0341cdddaa95a8872fe5b01a5c
author sven <sven> Tue, 06 Nov 2001 15:19:44 +0000
committer sven <sven> Tue, 06 Nov 2001 15:19:44 +0000
Initial revision
sverdool@pc117b:/local/git/Polylib>
skimo
^ permalink raw reply
* Re: [PATCH] cvsimport: rewritten in Perl
From: Matthias Urlichs @ 2005-06-30 16:10 UTC (permalink / raw)
To: Sven Verdoolaege; +Cc: git
In-Reply-To: <20050630154453.GA26808@pc117b.liacs.nl>
[-- Attachment #1: Type: text/plain, Size: 555 bytes --]
Hi,
Sven Verdoolaege:
> Presumably you have an extraneous "\n" somewhere.
>
Strange.
That must have crept in when I switched from cg-commit to git-commit-tree.
I'll find it. However, you don't actually need to re-import your
existing CVS->GIT trees; as long as the dates and the branch names
match, my script will continue where the other left off.
--
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
- -
You do not have mail.
[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 189 bytes --]
^ permalink raw reply
* Re: [PATCH] cvsimport: rewritten in Perl
From: Sven Verdoolaege @ 2005-06-30 16:14 UTC (permalink / raw)
To: Matthias Urlichs; +Cc: git
In-Reply-To: <20050630161043.GR10850@kiste.smurf.noris.de>
On Thu, Jun 30, 2005 at 06:10:43PM +0200, Matthias Urlichs wrote:
> I'll find it. However, you don't actually need to re-import your
> existing CVS->GIT trees; as long as the dates and the branch names
> match, my script will continue where the other left off.
I wanted to check first whether it would do the right thing.
I'll wait for your update to do further checking.
skimo
^ permalink raw reply
* Re: [PATCH] cvsimport: rewritten in Perl
From: Matthias Urlichs @ 2005-06-30 16:30 UTC (permalink / raw)
To: Sven Verdoolaege; +Cc: git
In-Reply-To: <20050630161423.GC26808@pc117b.liacs.nl>
[-- Attachment #1: Type: text/plain, Size: 528 bytes --]
Hi,
Sven Verdoolaege:
> I'll wait for your update to do further checking.
>
Ah, found it -- that was my slightly modified version of cvsps, which
happens not to print an extra empty line at the end. cvs2git.c dutifully
strips these.
Duh. Will post an incremental patch shortly.
--
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
- -
As I learn to trust the universe, I no longer need to carry a gun.
[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 189 bytes --]
^ permalink raw reply
* [PATCH] cvsimport: Limit the log string to 32k
From: Matthias Urlichs @ 2005-06-30 16:38 UTC (permalink / raw)
To: Sven Verdoolaege; +Cc: git
In-Reply-To: <20050630145528.GA18553@pc117b.liacs.nl>
[-- Attachment #1: Type: text/plain, Size: 674 bytes --]
Teach the new cvsimport script to chop the log string's trailing whitespace.
Limit the log string to 32k, in order to be compatible with the old
cvs2git program.
Signed-Off-By: Matthias Urlichs <smurf@smurf.noris.de>
---
diff --git a/git-cvsimport-script b/git-cvsimport-script
--- a/git-cvsimport-script
+++ b/git-cvsimport-script
@@ -468,7 +468,12 @@ my $commit = sub {
}
$pw->writer();
$pr->reader();
- print $pw $logmsg
+
+ # compatibility with git2cvs
+ substr($logmsg,32767) = "" if length($logmsg) > 32767;
+ $logmsg =~ s/[\s\n]+\z//;
+
+ print $pw "$logmsg\n"
or die "Error writing to git-commit-tree: $!\n";
$pw->close();
[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 189 bytes --]
^ permalink raw reply
* Re: [PATCH] cvsimport: rewritten in Perl
From: Nicolas Pitre @ 2005-06-30 16:48 UTC (permalink / raw)
To: Matthias Urlichs; +Cc: git
In-Reply-To: <pan.2005.06.30.10.30.21.176648@smurf.noris.de>
On Thu, 30 Jun 2005, Matthias Urlichs wrote:
> Hi, Matthias Urlichs wrote:
>
> > 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.)
> >
> OK -- pulled, tested.
>
> ... though why you'd want the kernel via CVS instead of by direct
> BK->GIT import is beyond me. ;-)
That's just a nice big test case.
You could try with, say, the gcc CVS as well for example.
Nicolas
^ permalink raw reply
* Re: [PATCH] cvsimport-in-Perl: Limit the number of arguments to git-update-cache
From: Nicolas Pitre @ 2005-06-30 16:54 UTC (permalink / raw)
To: Matthias Urlichs; +Cc: git
In-Reply-To: <pan.2005.06.30.10.34.00.807346@smurf.noris.de>
On Thu, 30 Jun 2005, Matthias Urlichs wrote:
> A small fix to git-cvsimport-script:
>
> Limit the number of arguments to git-update-cache.
> (Limiting their length may make a bit more sense, but I'm lazy.)
Why not using:
write( "| xargs | git-update-cache --add --", @new)
or the like (I forget what the exact perl incantation is).
Nicolas
^ permalink raw reply
* Re: [PATCH] cvsimport-in-Perl: Limit the number of arguments to git-update-cache
From: Nicolas Pitre @ 2005-06-30 17:15 UTC (permalink / raw)
To: Matthias Urlichs; +Cc: git
In-Reply-To: <Pine.LNX.4.63.0506301249550.1667@localhost.localdomain>
On Thu, 30 Jun 2005, Nicolas Pitre wrote:
> On Thu, 30 Jun 2005, Matthias Urlichs wrote:
>
> > A small fix to git-cvsimport-script:
> >
> > Limit the number of arguments to git-update-cache.
> > (Limiting their length may make a bit more sense, but I'm lazy.)
>
> Why not using:
>
> write( "| xargs | git-update-cache --add --", @new)
That example should be:
write( "| xargs git-update-cache --add --", @new)
of course.
Nicolas
^ permalink raw reply
* Re: [PATCH] cvsimport: rewritten in Perl
From: Nicolas Pitre @ 2005-06-30 17:22 UTC (permalink / raw)
To: Matthias Urlichs; +Cc: Sven Verdoolaege, git
In-Reply-To: <20050630163000.GT10850@kiste.smurf.noris.de>
On Thu, 30 Jun 2005, Matthias Urlichs wrote:
> Duh. Will post an incremental patch shortly.
Until Linus merges it I'd suggest that you post the updated full patch
instead.
Nicolas
^ 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