* Re: git-rev-list: proper lazy reachability
From: Petr Baudis @ 2005-06-04 19:46 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Junio C Hamano, Git Mailing List
In-Reply-To: <Pine.LNX.4.58.0506040847170.1876@ppc970.osdl.org>
Dear diary, on Sat, Jun 04, 2005 at 05:51:13PM CEST, I got a letter
where Linus Torvalds <torvalds@osdl.org> told me that...
> Would people prefer to have "git-rev-list" take arguments like
>
> git-rev-list a b ^c ^d
>
> the way git-rev-tree does?
Yes, please. I think that usage is more consistent and more flexible.
--
Petr "Pasky" Baudis
Stuff: http://pasky.or.cz/
C++: an octopus made by nailing extra legs onto a dog. -- Steve Taylor
^ permalink raw reply
* Re: git-rev-list: proper lazy reachability
From: Junio C Hamano @ 2005-06-04 19:41 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Git Mailing List
In-Reply-To: <Pine.LNX.4.58.0506040837190.1876@ppc970.osdl.org>
>>>>> "LT" == Linus Torvalds <torvalds@osdl.org> writes:
LT> Yes. The whole thing is written to literally expect to see the "stop here"
LT> thing, and that's when it starts poisoning the well.
LT> Does this fix it for you (untested, of course)?
Yes, it does.
^ permalink raw reply
* Re: git-rev-list: proper lazy reachability
From: Junio C Hamano @ 2005-06-04 19:30 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Git Mailing List
In-Reply-To: <Pine.LNX.4.58.0506040847170.1876@ppc970.osdl.org>
>>>>> "LT" == Linus Torvalds <torvalds@osdl.org> writes:
LT> On Sat, 4 Jun 2005, Linus Torvalds wrote:
>> Does this fix it for you (untested, of course)?
Will check later.
LT> Would people prefer to have "git-rev-list" take arguments like
LT> git-rev-list a b ^c ^d
LT> the way git-rev-tree does?
I do not expect myself to maintain many heads like Jeff, I
cannot comment on how well that "many heads" feature would work
in practice, but I would vote "a ^b" syntax to match
git-rev-tree.
^ permalink raw reply
* Re: [doc]playing with git, and netdev/libata-dev trees
From: Jeff Garzik @ 2005-06-04 18:16 UTC (permalink / raw)
To: Dave Airlie; +Cc: Linux Kernel, Andrew Morton, Git Mailing List, Linus Torvalds
In-Reply-To: <21d7e99705060403312234aa07@mail.gmail.com>
Dave Airlie wrote:
>>>1. when you want to publish your tree what do you do? just rsync it
>>>onto kernel.org?
>>
>>Basically. I copy the attached script into each repo, customize the
>>script for the upload destination.
>>
>>When I publish the tree, I just cd to the toplevel dir on my local
>>workstation, and run "./push"
>>
>>
>>
>>>2. When you are taking things from your queue for Linus do you create
>>>another tree and merge your branches into it or what?
>>
>>Not quite sure what you're asking, but I'll attempt to answer anyway :)
>
>
> Yes that's what I'm asking, mainly the pulling of multiple trees into
> one tree for giving to Linus, for Andrew I'm quite happy to have him
> pull multiple HEADs from the one tree assuming I don't have many
> interdependencies between trees...
>
> Say I want something like this one tree with
>
> drm-2.6 - HEAD <- linus tree
> - drm-via < a via driver
> - drm-initmap
> - drm-savage <- a savage driver that depends on
> the drm-initmap tree
>
> How would I construct such a beast, how does it work out from where to
> branch, can I branch a branch for something like drm-savage so I can
> say send Linus the initmap branch and then have -mm pulling the savage
> one...
You used to use BitKeeper, right?
Well, git works just fine for creating and maintaining separate repos,
where each repo is its own branch. Dependent branches are handled
simply by pulling new changes from the parent (drm-initmap) repo into
the child (drm-savage) repo.
If you just have a few branches, such as your example above, rather than
the 50+ branches I have, then I would recommend _ignoring_ the advice in
my git howto, and instead create a new branch by cloning:
cd /repos
mkdir drm-via
cp -a linux-2.6/.git drm-via
rm -rf drm-via/.git/objects
cp -al linux-2.6/.git/objects drm-via/.git
Once created by the above recipes, or similar, the directory will
function as a repo just like with BK. When you wish to update it from
upstream, update your local linux-2.6 repo and then
cd /repos/drm-via
git-pull-script /repos/linux-2.6/.git
or to pull new changes from initmap into savage:
cd /repos/drm-initmap
# { check in some changes }
cd /repos/drm-savage
git-pull-script /repos/drm-initmap/.git
Does all that make sense? It's really quite similar to BK, if you
ignore the "[jg-specific]" portions of the git howto I wrote.
Jeff
^ permalink raw reply
* Re: git-rev-list: proper lazy reachability
From: Linus Torvalds @ 2005-06-04 15:51 UTC (permalink / raw)
To: Junio C Hamano; +Cc: Git Mailing List
In-Reply-To: <Pine.LNX.4.58.0506040837190.1876@ppc970.osdl.org>
On Sat, 4 Jun 2005, Linus Torvalds wrote:
>
> Does this fix it for you (untested, of course)?
Btw, as shown by this patch, the lazy git-rev-list algorithm is actually
_supposed_ to be able to handle a lot more complicated cases than what the
command line interface allows.
In other words, maybe I should have used the same syntax as for
git-rev-tree, because it _can_ handle things like "show me all revisions
that are reachable from a or b, but are _not_ reachable from c or d or e.
Is that useful? I dunno. It might be useful for somebody like Jeff, who
has lots of different heads, and he could say "ok, show me what is in all
my network driver heads, but isn't in linus' tree".
Would people prefer to have "git-rev-list" take arguments like
git-rev-list a b ^c ^d
the way git-rev-tree does?
Linus
^ permalink raw reply
* Re: git-rev-list: proper lazy reachability
From: Linus Torvalds @ 2005-06-04 15:42 UTC (permalink / raw)
To: Junio C Hamano; +Cc: Git Mailing List
In-Reply-To: <7vekbigo8q.fsf@assigned-by-dhcp.cox.net>
On Sat, 4 Jun 2005, Junio C Hamano wrote:
>
> Linus, what do you think rev-list should do given HEADs from two
> forks, like this?
>
> JC git-rev-list JC LT ????
> |
> | LT
> | |
> \ /
> |
> |
> |
Ahh. Ok, I'll fix it. Indeed, I think it should give everything up to the
merge base.
> Current "proper lazy reachability" version, btw, does something
> very unexpected for my use pattern. If you have more than one
> commits between the fork point and LT HEAD in the above picture,
> everything from the beginning of time to JC is given, or
> something silly like that.
Yes. The whole thing is written to literally expect to see the "stop here"
thing, and that's when it starts poisoning the well.
Does this fix it for you (untested, of course)?
Linus
---
diff --git a/rev-list.c b/rev-list.c
--- a/rev-list.c
+++ b/rev-list.c
@@ -160,6 +160,8 @@ int main(int argc, char **argv)
end = lookup_commit_reference(sha1[1]);
if (!end || parse_commit(end) < 0)
die("bad ending commit object");
+ end->object.flags |= UNINTERESTING;
+ commit_list_insert(end, &list);
}
commit_list_insert(commit, &list);
^ permalink raw reply
* Re: git-rev-list: proper lazy reachability
From: Thomas Glanzmann @ 2005-06-04 15:09 UTC (permalink / raw)
To: Junio C Hamano; +Cc: Linus Torvalds, Git Mailing List
In-Reply-To: <7vekbigo8q.fsf@assigned-by-dhcp.cox.net>
Hello Junio,
I pull the REMOTE_HEAD including objects but don't merge. After that I
run:
system("git-rev-tree HEAD REMOTE_HEAD | sed -e 's/^[0-9]* //' | git-diff-tree --stdin -v ");
for bitkeeper I used the merge base approach (but at that time I only
knew that this gives me any deltas in the current tree not in the remote
tree, but didn't know how it worked).
bkparentdiff is aliased to `bk rset -hr`bk repogca`,+ | grep -v ^BitKeeper | bk gnupatch -du -e -h -T'
Thomas
^ permalink raw reply
* Re: git-rev-list: proper lazy reachability
From: Junio C Hamano @ 2005-06-04 15:01 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Git Mailing List
In-Reply-To: <Pine.LNX.4.58.0505310813540.1876@ppc970.osdl.org>
Linus, what do you think rev-list should do given HEADs from two
forks, like this?
JC git-rev-list JC LT ????
|
| LT
| |
\ /
|
|
|
The above is often the shape of my working repository. I pull
from you, commit a handful on top of your then-HEAD, and when I
am about ready to submit, I pull from you again to find your
HEAD advanced somewhat.
For patch-form submission, I need a list of my commits since I
forked from you. Also I tend to rebase to your head often,
instead of merging inside my working repository (which makes
later e-mail patch-form submission more work for me), so even
when I am not immediately submitting the changes I have in my
fork, I need that list to forward port my changes.
JIT currently uses this to get this list (as a workaround):
git-rev-list JC $(merge-base JC LT)
I am wondering if this "since they forked" is usually what the
user wants. If that is the case then it would be great if I did
not have to do the "merge-base" part outside.
Current "proper lazy reachability" version, btw, does something
very unexpected for my use pattern. If you have more than one
commits between the fork point and LT HEAD in the above picture,
everything from the beginning of time to JC is given, or
something silly like that.
^ permalink raw reply
* [PATCH 10/10] Add -s option to show log summary
From: Jonas Fonseca @ 2005-06-04 14:43 UTC (permalink / raw)
To: Petr Baudis; +Cc: git
In-Reply-To: <20050604143831.GD12615@diku.dk>
When passing -s to cg-log each log entry is summarized in one line. The line
carries info about commit date, author, first log line and the commit id. It
will look something like the following (with only:
2005-05-20 11:46 Linus Torvalds sparse cleanup e99d59ff0bff349ef20...
The result ends up being 130 chars wide however the commit id is placed so
that it can easily be hidden if line wrapping in the pager is enabled.
Signed-off-by: Jonas Fonseca <fonseca@diku.dk>
---
cg-Xlib | 4 +++-
cg-log | 53 ++++++++++++++++++++++++++++++++++++++++++++---------
2 files changed, 47 insertions(+), 10 deletions(-)
diff --git a/cg-Xlib b/cg-Xlib
--- a/cg-Xlib
+++ b/cg-Xlib
@@ -47,10 +47,12 @@ mktemp () {
showdate () {
date="$1"
+ format="$2"
+ [ "$format" ] || format=-R
sec=${date[0]}; tz=${date[1]}
dtz=${tz/+/}
lsec=$(expr $dtz / 100 \* 3600 + $dtz % 100 \* 60 + $sec)
- pdate="$(date -Rud "1970-01-01 UTC + $lsec sec" 2>/dev/null)"
+ pdate="$(date -ud "1970-01-01 UTC + $lsec sec" "$format" 2>/dev/null)"
echo "${pdate/+0000/$tz}"
}
diff --git a/cg-log b/cg-log
--- a/cg-log
+++ b/cg-log
@@ -14,15 +14,21 @@
# cg-log then displays only changes in those files.
#
# -c::
-# Add color to the output. Currently, the colors are:
-# - `author`: 'cyan'
-# - `committer`: 'magenta'
-# - `header`: 'green'
-# - `files`: 'blue'
-# - `signoff`: 'yellow'
+# Colorize to the output. When getting log summary the `date` is
+# colored 'green', the `author` is colored 'cyan', the `commit ID`
+# is colored 'blue' and the special line trimming character (~) is
+# colored 'magenta'. +
+# +
+# When getting the full log the colors are:
+# - `author`: 'cyan'
+# - `committer`: 'magenta'
+# - `header`: 'green'
+# - `files`: 'blue'
+# - `signoff`: 'yellow'
#
# -f::
-# List affected files.
+# List affected files. This option does not make sense when using
+# `-s` to get a log summary.
#
# -r FROM_ID[:TO_ID]::
# Limit the log information to a set of revisions using either
@@ -36,6 +42,12 @@
# End the log listing at the merge base of the -r arguments
# (defaulting to master and origin).
#
+# -s::
+# Show a one line summary for each log entry. The summary contains
+# information about the commit date, the author, the first line
+# of the commit log and the commit ID. Long author and commit log
+# titles are trimmed but marked with an ending tilde (~).
+#
# -uUSERNAME::
# List only commits where author or committer contains 'USERNAME'.
# The search for 'USERNAME' is case-insensitive.
@@ -55,7 +67,7 @@
#
# $ cg-log -r releasetag-0.9:releasetag-0.10
-USAGE="cg-log [-c] [-f] [m] [-uUSERNAME] [-r FROM_ID[:TO_ID] FILE..."
+USAGE="cg-log [-c] [-f] [-m] [-s] [-uUSERNAME] [-r FROM_ID[:TO_ID] FILE..."
. ${COGITO_LIB}cg-Xlib
# Try to fix the annoying "Broken pipe" output. May not help, but apparently
@@ -71,6 +83,7 @@ coldefault=
list_files=
log_start=
log_end=
+summary=
user=
mergebase=
files=()
@@ -107,6 +120,9 @@ while [ "$1" ]; do
-m)
mergebase=1
;;
+ -s)
+ summary=1
+ ;;
*)
files=("$@")
break
@@ -196,6 +212,8 @@ print_commit_log() {
echo -e "author $author\ncommitter $committer" \
| grep -qi "$user" || return
fi
+ [ "$summary" ] && continue
+
echo ${colheader}commit ${commit%:*} $coldefault
echo ${colheader}tree $tree $coldefault
@@ -222,6 +240,23 @@ print_commit_log() {
s/./ &/
'
;;
+ *)
+ # Print summary
+ author="${author% <*}"
+ date=(${committer#*> })
+ date="$(showdate $date '+%F %H:%M')"
+ title="$key $rest"
+ if [ "${#title}" -gt 51 ]; then
+ title="${title:0:50}$colcommitter~"
+ fi
+ if [ "${#author}" -gt 20 ]; then
+ author="${author:0:19}$colcommitter~"
+ fi
+
+ printf "$colheader$date $colauthor%-20s $coldefault%-51s $colfiles${commit%:*}$coldefault\n" \
+ "$author" "$title"
+ return
+ ;;
esac
done
}
@@ -232,6 +267,6 @@ $revls | $revsort | while read time comm
log="$(print_commit_log $commit)"
if [ "$log" ]; then
echo "$log"
- echo
+ [ "$summary" ] || echo
fi
done | pager
--
Jonas Fonseca
^ permalink raw reply
* [PATCH 9/10] Move file matching inside the loop.
From: Jonas Fonseca @ 2005-06-04 14:43 UTC (permalink / raw)
To: Petr Baudis; +Cc: git
In-Reply-To: <20050604143831.GD12615@diku.dk>
Handling of -f is done inide the loop so no extra git-cat-file call is
necessary. Store file arguments to cg-log in an array to make them easier
to access from print_commit_log().
Signed-off-by: Jonas Fonseca <fonseca@diku.dk>
---
cg-log | 14 ++++++++------
1 files changed, 8 insertions(+), 6 deletions(-)
diff --git a/cg-log b/cg-log
--- a/cg-log
+++ b/cg-log
@@ -73,6 +73,7 @@ log_start=
log_end=
user=
mergebase=
+files=()
while [ "$1" ]; do
case "$1" in
@@ -107,6 +108,7 @@ while [ "$1" ]; do
mergebase=1
;;
*)
+ files=("$@")
break
;;
esac
@@ -184,6 +186,12 @@ print_commit_log() {
parents[${#parents[@]}]="$rest"
;;
"")
+ if [ "$files" ]; then
+ parent="${parents[0]}"
+ diff_ops=
+ [ "$parent" ] || diff_ops=--root
+ [ "$(git-diff-tree -r $diff_ops $commit $parent "${files[@]}")" ] || return 1
+ fi
if [ "$user" ]; then
echo -e "author $author\ncommitter $committer" \
| grep -qi "$user" || return
@@ -221,12 +229,6 @@ print_commit_log() {
$revls | $revsort | while read time commit parents; do
trap exit SIGPIPE
[ "$revfmt" = "git-rev-list" ] && commit="$time"
- if [ $# -ne 0 ]; then
- parent=$(git-cat-file commit $commit | sed -n '2s/parent //p;2Q')
- diff_ops=
- [ "$parent" ] || diff_ops=--root
- [ "$(git-diff-tree -r $diff_ops $commit $parent "$@")" ] || continue
- fi
log="$(print_commit_log $commit)"
if [ "$log" ]; then
echo "$log"
--
Jonas Fonseca
^ permalink raw reply
* [PATCH 8/10] Move the username matching inside the loop
From: Jonas Fonseca @ 2005-06-04 14:42 UTC (permalink / raw)
To: Petr Baudis; +Cc: git
In-Reply-To: <20050604143831.GD12615@diku.dk>
By handling -u in the commit parsing loop no extra git-cat-file call is
necessary. Keep the line-based matching scheme so that it is still possible
to restrict searches by using prefixing the search string with either
'author' or 'committer' (e.g. -u'author.*miciah').
This change also magically removes trailing empty lines from commit logs.
Signed-off-by: Jonas Fonseca <fonseca@diku.dk>
---
cg-log | 12 ++++++++----
1 files changed, 8 insertions(+), 4 deletions(-)
diff --git a/cg-log b/cg-log
--- a/cg-log
+++ b/cg-log
@@ -184,6 +184,10 @@ print_commit_log() {
parents[${#parents[@]}]="$rest"
;;
"")
+ if [ "$user" ]; then
+ echo -e "author $author\ncommitter $committer" \
+ | grep -qi "$user" || return
+ fi
echo ${colheader}commit ${commit%:*} $coldefault
echo ${colheader}tree $tree $coldefault
@@ -223,9 +227,9 @@ $revls | $revsort | while read time comm
[ "$parent" ] || diff_ops=--root
[ "$(git-diff-tree -r $diff_ops $commit $parent "$@")" ] || continue
fi
- if [ "$user" ]; then
- git-cat-file commit $commit | grep -e '^author ' -e '^committer ' | grep -qi "$user" || continue
+ log="$(print_commit_log $commit)"
+ if [ "$log" ]; then
+ echo "$log"
+ echo
fi
- print_commit_log $commit
- echo
done | pager
--
Jonas Fonseca
^ permalink raw reply
* [PATCH 7/10] Move log printing to separate function
From: Jonas Fonseca @ 2005-06-04 14:42 UTC (permalink / raw)
To: Petr Baudis; +Cc: git
In-Reply-To: <20050604143831.GD12615@diku.dk>
Each commit log is now handled in the new print_commit_log() function.
Signed-off-by: Jonas Fonseca <fonseca@diku.dk>
---
cg-log | 30 ++++++++++++++++++------------
1 files changed, 18 insertions(+), 12 deletions(-)
diff --git a/cg-log b/cg-log
--- a/cg-log
+++ b/cg-log
@@ -160,22 +160,13 @@ else
revfmt="git-rev-list"
fi
-$revls | $revsort | while read time commit parents; do
- trap exit SIGPIPE
+print_commit_log() {
+ commit="$1"
author=
committer=
tree=
parents=()
- [ "$revfmt" = "git-rev-list" ] && commit="$time"
- if [ $# -ne 0 ]; then
- parent=$(git-cat-file commit $commit | sed -n '2s/parent //p;2Q')
- diff_ops=
- [ "$parent" ] || diff_ops=--root
- [ "$(git-diff-tree -r $diff_ops $commit $parent "$@")" ] || continue
- fi
- if [ "$user" ]; then
- git-cat-file commit $commit | grep -e '^author ' -e '^committer ' | grep -qi "$user" || continue
- fi
+
git-cat-file commit $commit | \
while read key rest; do
trap exit SIGPIPE
@@ -221,5 +212,20 @@ $revls | $revsort | while read time comm
;;
esac
done
+}
+
+$revls | $revsort | while read time commit parents; do
+ trap exit SIGPIPE
+ [ "$revfmt" = "git-rev-list" ] && commit="$time"
+ if [ $# -ne 0 ]; then
+ parent=$(git-cat-file commit $commit | sed -n '2s/parent //p;2Q')
+ diff_ops=
+ [ "$parent" ] || diff_ops=--root
+ [ "$(git-diff-tree -r $diff_ops $commit $parent "$@")" ] || continue
+ fi
+ if [ "$user" ]; then
+ git-cat-file commit $commit | grep -e '^author ' -e '^committer ' | grep -qi "$user" || continue
+ fi
+ print_commit_log $commit
echo
done | pager
--
Jonas Fonseca
^ permalink raw reply
* [PATCH 6/10] Remove the catch all rule
From: Jonas Fonseca @ 2005-06-04 14:41 UTC (permalink / raw)
To: Petr Baudis; +Cc: git
In-Reply-To: <20050604143831.GD12615@diku.dk>
All commit header entries are already be handled so no need for a default
case pattern.
Signed-off-by: Jonas Fonseca <fonseca@diku.dk>
---
cg-log | 4 ----
1 files changed, 0 insertions(+), 4 deletions(-)
diff --git a/cg-log b/cg-log
--- a/cg-log
+++ b/cg-log
@@ -219,11 +219,7 @@ $revls | $revsort | while read time comm
s/./ &/
'
;;
- *)
- echo $colheader$key $rest $coldefault
- ;;
esac
-
done
echo
done | pager
--
Jonas Fonseca
^ permalink raw reply
* [PATCH 5/10] Move printing of the commit info line inside the loop
From: Jonas Fonseca @ 2005-06-04 14:41 UTC (permalink / raw)
To: Petr Baudis; +Cc: git
In-Reply-To: <20050604143831.GD12615@diku.dk>
Printing of all the log headers are now handled the same place.
Signed-off-by: Jonas Fonseca <fonseca@diku.dk>
---
cg-log | 2 +-
1 files changed, 1 insertions(+), 1 deletions(-)
diff --git a/cg-log b/cg-log
--- a/cg-log
+++ b/cg-log
@@ -176,7 +176,6 @@ $revls | $revsort | while read time comm
if [ "$user" ]; then
git-cat-file commit $commit | grep -e '^author ' -e '^committer ' | grep -qi "$user" || continue
fi
- echo $colheader""commit ${commit%:*} $coldefault;
git-cat-file commit $commit | \
while read key rest; do
trap exit SIGPIPE
@@ -194,6 +193,7 @@ $revls | $revsort | while read time comm
parents[${#parents[@]}]="$rest"
;;
"")
+ echo ${colheader}commit ${commit%:*} $coldefault
echo ${colheader}tree $tree $coldefault
for parent in "${parents[@]}"; do
--
Jonas Fonseca
^ permalink raw reply
* [PATCH 4/10] First parse all commit header entries then print them
From: Jonas Fonseca @ 2005-06-04 14:40 UTC (permalink / raw)
To: Petr Baudis; +Cc: git
In-Reply-To: <20050604143831.GD12615@diku.dk>
Change the main loop to first parse all header entries before printing
them. Makes the cg-log output more independent of the order of the git
commit header.
Signed-off-by: Jonas Fonseca <fonseca@diku.dk>
---
cg-log | 26 ++++++++++++++++----------
1 files changed, 16 insertions(+), 10 deletions(-)
diff --git a/cg-log b/cg-log
--- a/cg-log
+++ b/cg-log
@@ -183,27 +183,33 @@ $revls | $revsort | while read time comm
case "$key" in
"author")
author="$rest"
- date=(${author#*> })
- pdate="$(showdate $date)"
- [ "$pdate" ] && author="${author%> *}> $pdate"
- echo $colauthor$key $author $coldefault
;;
"committer")
committer="$rest"
- date=(${committer#*> })
- pdate="$(showdate $date)"
- [ "$pdate" ] && committer="${committer%> *}> $pdate"
- echo $colcommitter$key $committer $coldefault
;;
"tree")
tree="$rest"
- echo $colheader$key $tree $coldefault
;;
"parent")
parents[${#parents[@]}]="$rest"
- echo $colheader$key $rest $coldefault
;;
"")
+ echo ${colheader}tree $tree $coldefault
+
+ for parent in "${parents[@]}"; do
+ echo ${colheader}parent $parent $coldefault
+ done
+
+ date=(${author#*> })
+ pdate="$(showdate $date)"
+ [ "$pdate" ] && author="${author%> *}> $pdate"
+ echo ${colauthor}author $author $coldefault
+
+ date=(${committer#*> })
+ pdate="$(showdate $date)"
+ [ "$pdate" ] && committer="${committer%> *}> $pdate"
+ echo ${colcommitter}committer $committer $coldefault
+
if [ -n "$list_files" ]; then
list_commit_files "$tree" "${parents[0]}"
fi
--
Jonas Fonseca
^ permalink raw reply
* [PATCH 3/10] Separate handling of author and committer in commit headers
From: Jonas Fonseca @ 2005-06-04 14:40 UTC (permalink / raw)
To: Petr Baudis; +Cc: git
In-Reply-To: <20050604143831.GD12615@diku.dk>
Parse and print the author and committer header entries so the color logic
can be removed.
Signed-off-by: Jonas Fonseca <fonseca@diku.dk>
---
cg-log | 24 ++++++++++++++----------
1 files changed, 14 insertions(+), 10 deletions(-)
diff --git a/cg-log b/cg-log
--- a/cg-log
+++ b/cg-log
@@ -162,6 +162,8 @@ fi
$revls | $revsort | while read time commit parents; do
trap exit SIGPIPE
+ author=
+ committer=
tree=
parents=()
[ "$revfmt" = "git-rev-list" ] && commit="$time"
@@ -179,17 +181,19 @@ $revls | $revsort | while read time comm
while read key rest; do
trap exit SIGPIPE
case "$key" in
- "author"|"committer")
- if [ "$key" = "author" ]; then
- color="$colauthor"
- else
- color="$colcommitter"
- fi
-
- date=(${rest#*> })
+ "author")
+ author="$rest"
+ date=(${author#*> })
+ pdate="$(showdate $date)"
+ [ "$pdate" ] && author="${author%> *}> $pdate"
+ echo $colauthor$key $author $coldefault
+ ;;
+ "committer")
+ committer="$rest"
+ date=(${committer#*> })
pdate="$(showdate $date)"
- [ "$pdate" ] && rest="${rest%> *}> $pdate"
- echo $color$key $rest $coldefault
+ [ "$pdate" ] && committer="${committer%> *}> $pdate"
+ echo $colcommitter$key $committer $coldefault
;;
"tree")
tree="$rest"
--
Jonas Fonseca
^ permalink raw reply
* [PATCH 2/10] Separate handling of tree and parent in commit headers
From: Jonas Fonseca @ 2005-06-04 14:39 UTC (permalink / raw)
To: Petr Baudis; +Cc: git
In-Reply-To: <20050604143831.GD12615@diku.dk>
Parse tree and parent commit header entries separately so the logic for
deciding where to save the IDs can be removed. Save all parents in an array.
Signed-off-by: Jonas Fonseca <fonseca@diku.dk>
---
cg-log | 18 +++++++++---------
1 files changed, 9 insertions(+), 9 deletions(-)
diff --git a/cg-log b/cg-log
--- a/cg-log
+++ b/cg-log
@@ -162,8 +162,8 @@ fi
$revls | $revsort | while read time commit parents; do
trap exit SIGPIPE
- tree1=
- tree2=
+ tree=
+ parents=()
[ "$revfmt" = "git-rev-list" ] && commit="$time"
if [ $# -ne 0 ]; then
parent=$(git-cat-file commit $commit | sed -n '2s/parent //p;2Q')
@@ -191,17 +191,17 @@ $revls | $revsort | while read time comm
[ "$pdate" ] && rest="${rest%> *}> $pdate"
echo $color$key $rest $coldefault
;;
- "tree"|"parent")
- if [ -z $tree1 ]; then
- tree1=$rest
- elif [ -z $tree2 ]; then
- tree2=$rest
- fi
+ "tree")
+ tree="$rest"
+ echo $colheader$key $tree $coldefault
+ ;;
+ "parent")
+ parents[${#parents[@]}]="$rest"
echo $colheader$key $rest $coldefault
;;
"")
if [ -n "$list_files" ]; then
- list_commit_files "$tree1" "$tree2"
+ list_commit_files "$tree" "${parents[0]}"
fi
echo; sed -re '
/ *Signed-off-by:.*/Is//'$colsignoff'&'$coldefault'/
--
Jonas Fonseca
^ permalink raw reply
* [PATCH 1/10] Cleanup conversion to human readable date
From: Jonas Fonseca @ 2005-06-04 14:39 UTC (permalink / raw)
To: Petr Baudis; +Cc: git
In-Reply-To: <20050604143831.GD12615@diku.dk>
Simplify the date substitution to reduce code duplication.
Signed-off-by: Jonas Fonseca <fonseca@diku.dk>
---
cg-log | 8 ++------
cg-mkpatch | 7 ++-----
2 files changed, 4 insertions(+), 11 deletions(-)
diff --git a/cg-log b/cg-log
--- a/cg-log
+++ b/cg-log
@@ -188,12 +188,8 @@ $revls | $revsort | while read time comm
date=(${rest#*> })
pdate="$(showdate $date)"
- if [ "$pdate" ]; then
- echo -n $color$key $rest | sed "s/>.*/> $pdate/"
- echo $coldefault
- else
- echo $color$key $rest $coldefault
- fi
+ [ "$pdate" ] && rest="${rest%> *}> $pdate"
+ echo $color$key $rest $coldefault
;;
"tree"|"parent")
if [ -z $tree1 ]; then
diff --git a/cg-mkpatch b/cg-mkpatch
--- a/cg-mkpatch
+++ b/cg-mkpatch
@@ -53,11 +53,8 @@ showpatch () {
"author"|"committer")
date=(${rest#*> })
pdate="$(showdate $date)"
- if [ "$pdate" ]; then
- echo $key $rest | sed "s/>.*/> $pdate/" >>$header
- else
- echo $key $rest >>$header
- fi
+ [ "$pdate" ] && rest="${rest%> *}> $pdate"
+ echo $key $rest >>$header
;;
"")
cat
--
Jonas Fonseca
^ permalink raw reply
* [PATCHSET] cg-log cleanups and enhancements
From: Jonas Fonseca @ 2005-06-04 14:38 UTC (permalink / raw)
To: Petr Baudis; +Cc: git
The patchset contains the following 10 patches:
[PATCH 1/10] Cleanup conversion to human readable date
[PATCH 2/10] Separate handling of tree and parent in commit headers
[PATCH 3/10] Separate handling of author and committer in commit headers
[PATCH 4/10] First parse all commit header entries then print them
[PATCH 5/10] Move printing of the commit info line inside the loop
[PATCH 6/10] Remove the catch all rule
[PATCH 7/10] Move log printing to separate function
[PATCH 8/10] Move the username matching inside the loop
[PATCH 9/10] Move file matching inside the loop.
[PATCH 10/10] Add -s option to show log summary
--
Jonas Fonseca
^ permalink raw reply
* SSH pull problems
From: Radoslaw Szkodzinski @ 2005-06-04 13:05 UTC (permalink / raw)
To: git
I had some problems today with git+ssh protocol.
First, when using cg-clone, it couldn't execute cg-rpush, although it's
there in /usr/local.
Maybe that has something to do with that being added to the path in
/etc/profile.
Second, I don't know how to specify the port number,
the typical notation of git+ssh://xyz:port/repo didn't work.
Anybody knows what to do with these?
SSH would be very useful for me if it worked right.
AstralStorm
^ permalink raw reply
* Re: [doc]playing with git, and netdev/libata-dev trees
From: Dave Airlie @ 2005-06-04 10:31 UTC (permalink / raw)
To: Jeff Garzik; +Cc: Linux Kernel, Andrew Morton, Git Mailing List, Linus Torvalds
In-Reply-To: <42A181C1.3010902@pobox.com>
> > 1. when you want to publish your tree what do you do? just rsync it
> > onto kernel.org?
>
> Basically. I copy the attached script into each repo, customize the
> script for the upload destination.
>
> When I publish the tree, I just cd to the toplevel dir on my local
> workstation, and run "./push"
>
>
> > 2. When you are taking things from your queue for Linus do you create
> > another tree and merge your branches into it or what?
>
> Not quite sure what you're asking, but I'll attempt to answer anyway :)
Yes that's what I'm asking, mainly the pulling of multiple trees into
one tree for giving to Linus, for Andrew I'm quite happy to have him
pull multiple HEADs from the one tree assuming I don't have many
interdependencies between trees...
Say I want something like this one tree with
drm-2.6 - HEAD <- linus tree
- drm-via < a via driver
- drm-initmap
- drm-savage <- a savage driver that depends on
the drm-initmap tree
How would I construct such a beast, how does it work out from where to
branch, can I branch a branch for something like drm-savage so I can
say send Linus the initmap branch and then have -mm pulling the savage
one...
if that makes any sense :-)
Dave.
>
>
> [1] I'm still scared of conflicts in the merge process. Simple and
> automatic merging works just fine, like it did under BitKeeper. But if
> there are conflicts that cause git-pull-script/git-resolve-script to
> bail, then I bail as well: I export a patch, run patch(1), and then
> handle the merge the Old Fashioned Way(tm) by looking at .rej files.
>
> I really wish somebody would write a merge helper for git that places
> the conflicts side-by-side in the code [in the working dir]. BitKeeper
> and CVS both presented conflicts to you in this manner.
>
> The "I resolved this conflict, now let's continue where we left off"
> process is still quite raw in git. I suppose this is something that is
> left for others to script, above the plumbing, but hey...
>
>
>
> #!/bin/sh
>
> rsync -e ssh --verbose --delete --stats --progress -az .git/ master.kernel.org:/pub/scm/linux/kernel/git/jgarzik/misc-2.6.git
>
>
>
^ permalink raw reply
* Re: [doc]playing with git, and netdev/libata-dev trees
From: Jeff Garzik @ 2005-06-04 10:26 UTC (permalink / raw)
To: Dave Airlie; +Cc: Linux Kernel, Andrew Morton, Git Mailing List, Linus Torvalds
In-Reply-To: <21d7e99705060401405cfd5a11@mail.gmail.com>
[-- Attachment #1: Type: text/plain, Size: 2660 bytes --]
Dave Airlie wrote:
>>When I merge a patch for drivers/net/forcedeth.c, I merge it into a
>>brand new 'forcedeth' repository, a peer to the 40+ other such
>>repository. Under BitKeeper, I made these repositories available merged
>>together into one big "netdev-2.6" repository because it was too time
>>consuming to make the individual 50+ trees publicly available. With
>>git, developers have direct access to the individual trees.
>>
>>I thought I would write up a quick guide describing how to mess around
>>with the netdev and libata-dev trees, and with git in general.
>>
>
>
> Thanks for this, I'm starting to get up to speed on git now...
>
> Two questions,
>
> 1. when you want to publish your tree what do you do? just rsync it
> onto kernel.org?
Basically. I copy the attached script into each repo, customize the
script for the upload destination.
When I publish the tree, I just cd to the toplevel dir on my local
workstation, and run "./push"
> 2. When you are taking things from your queue for Linus do you create
> another tree and merge your branches into it or what?
Not quite sure what you're asking, but I'll attempt to answer anyway :)
When I prepare a submission for Linus, I will pull several branches into
a single 'for-linus' conglomeration branch. I do this with the
following incantation, for each branch I am pushing upstream:
git-resolve-script $(cat .git/HEAD) $(cat .git/refs/heads/$branch) \
`pwd` $branch
(Note that I modified my git-resolve-script to take an additional $4
argument, which causes the string " branch $4" to be added to the merge
cset's commit msg)
After I take care of all the merge conflicts[1] from the
git-resolve-script run, I give the big pile of mush a final build and
test, and then run "./push".
For the "please pull" email, I use diffstat, git-diff-tree,
git-changes-script and the newly written git-shortlog.
Jeff
[1] I'm still scared of conflicts in the merge process. Simple and
automatic merging works just fine, like it did under BitKeeper. But if
there are conflicts that cause git-pull-script/git-resolve-script to
bail, then I bail as well: I export a patch, run patch(1), and then
handle the merge the Old Fashioned Way(tm) by looking at .rej files.
I really wish somebody would write a merge helper for git that places
the conflicts side-by-side in the code [in the working dir]. BitKeeper
and CVS both presented conflicts to you in this manner.
The "I resolved this conflict, now let's continue where we left off"
process is still quite raw in git. I suppose this is something that is
left for others to script, above the plumbing, but hey...
[-- Attachment #2: push --]
[-- Type: text/plain, Size: 137 bytes --]
#!/bin/sh
rsync -e ssh --verbose --delete --stats --progress -az .git/ master.kernel.org:/pub/scm/linux/kernel/git/jgarzik/misc-2.6.git
^ permalink raw reply
* Re: [doc]playing with git, and netdev/libata-dev trees
From: Dave Airlie @ 2005-06-04 8:40 UTC (permalink / raw)
To: Linux Kernel; +Cc: Andrew Morton, Git Mailing List
In-Reply-To: <42955DF7.4000805@pobox.com>
>
> When I merge a patch for drivers/net/forcedeth.c, I merge it into a
> brand new 'forcedeth' repository, a peer to the 40+ other such
> repository. Under BitKeeper, I made these repositories available merged
> together into one big "netdev-2.6" repository because it was too time
> consuming to make the individual 50+ trees publicly available. With
> git, developers have direct access to the individual trees.
>
> I thought I would write up a quick guide describing how to mess around
> with the netdev and libata-dev trees, and with git in general.
>
Thanks for this, I'm starting to get up to speed on git now...
Two questions,
1. when you want to publish your tree what do you do? just rsync it
onto kernel.org?
2. When you are taking things from your queue for Linus do you create
another tree and merge your branches into it or what?
Dave.
^ permalink raw reply
* Re: gitweb wishlist
From: Junio C Hamano @ 2005-06-04 8:29 UTC (permalink / raw)
To: Kay Sievers; +Cc: git
In-Reply-To: <1115931627.8465.6.camel@dhcp-188.off.vrfy.org>
>>>>> "KS" == Kay Sievers <kay.sievers@vrfy.org> writes:
KS> On Thu, 2005-05-12 at 13:07 -0700, Junio C Hamano wrote:
>> * [Previous page] [Next page] would be nice in addition to last
>> 10, day, week, etc.
KS> That should be easy to do with the parameters we have now for the
KS> git-rev-list. I will first finish the new browser through the
KS> trees/files, then the project overview page and after that try the
KS> pager,
Is this still on your list of things to do?
^ permalink raw reply
* [PATCH] Modify git-rev-list ... in merge order [ de-nitted ]
From: jon @ 2005-06-04 7:53 UTC (permalink / raw)
To: git, jon.seymour, torvalds; +Cc: junkio
[PATCH] Modify git-rev-list to linearise the commit history in merge order.
This patch linearises the GIT commit history graph into merge order
which is defined by invariants specified in Documentation/git-rev-list.txt.
The linearisation produced by this patch is superior in an objective sense
to that produced by the existing git-rev-list implementation in that
the linearisation produced is guaranteed to have the minimum number of
discontinuities, where a discontinuity is defined as an adjacent pair of
commits in the output list which are not related in a direct child-parent
relationship.
With this patch a graph like this:
a4 ---
| \ \
| b4 |
|/ | |
a3 | |
| | |
a2 | |
| | c3
| | |
| | c2
| b3 |
| | /|
| b2 |
| | c1
| | /
| b1
a1 |
| |
a0 |
| /
root
Sorts like this:
= a4
| c3
| c2
| c1
^ b4
| b3
| b2
| b1
^ a3
| a2
| a1
| a0
= root
Instead of this:
= a4
| c3
^ b4
| a3
^ c2
^ b3
^ a2
^ b2
^ c1
^ a1
^ b1
^ a0
= root
A test script, t/t6000-rev-list.sh, includes a test which demonstrates
that the linearisation produced by --merge-order has less discontinuities
than the linearisation produced by git-rev-list without the --merge-order
flag specified. To see this, do the following:
cd t
./t6000-rev-list.sh
cd trash
cat actual-default-order
cat actual-merge-order
The existing behaviour of git-rev-list is preserved, by default. To obtain
the modified behaviour, specify --merge-order or --merge-order --show-breaks
on the command line.
This version of the patch has been tested on the git repository and also on the linux-2.6
repository and has reasonable performance on both - ~50-100% slower than the original algorithm.
For more details about this change, refer to Documentation/git-rev-list.txt
and http://blackcubes.dyndns.org/epoch/.
Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
diff --git a/Documentation/git-rev-list.txt b/Documentation/git-rev-list.txt
--- a/Documentation/git-rev-list.txt
+++ b/Documentation/git-rev-list.txt
@@ -9,7 +9,7 @@ git-rev-list - Lists commit objects in r
SYNOPSIS
--------
-'git-rev-list' <commit>
+'git-rev-list' [ *--max-count*=number ] [ *--max-age*=timestamp ] [ *--min-age*=timestamp ] [ *--merge-order* [ *--show-breaks* ] ] <commit>
DESCRIPTION
-----------
@@ -17,11 +17,39 @@ Lists commit objects in reverse chronolo
given commit, taking ancestry relationship into account. This is
useful to produce human-readable log output.
+If *--merge-order* is specified, the commit history is decomposed into a unique sequence of minimal, non-linear
+epochs and maximal, linear epochs. Non-linear epochs are then linearised by sorting them into merge order, which
+is described below.
+
+Maximal, linear epochs correspond to periods of sequential development. Minimal, non-linear epochs
+correspond to periods of divergent development followed by a converging merge. The theory of epochs is described
+in more detail at link:http://blackcubes.dyndns.org/epoch/[http://blackcubes.dyndns.org/epoch/].
+
+The merge order for a non-linear epoch is defined as a linearisation for which the following invariants are true:
+
+ 1. if a commit P is reachable from commit N, commit P sorts after commit N in the linearised list.
+ 2. if Pi and Pj are any two parents of a merge M (with i < j), then any commit N, such that N is reachable from Pj
+ but not reachable from Pi, sorts before all commits reachable from Pi.
+
+Invariant 1 states that later commits appear before earlier commits they are derived from.
+
+Invariant 2 states that commits unique to "later" parents in a merge, appear before all commits from "earlier" parents of
+a merge.
+
+If *--show-breaks* is specified, each item of the list is output with a 2-character prefix consisting of one of:
+ (|), (^), (=) followed by a space.
+Commits marked with (=) represent the boundaries of minimal, non-linear epochs and correspond either to the start of a period of divergent development or to the end of such a period.
+Commits marked with (|) are direct parents of commits immediately preceding the marked commit in the list.
+Commits marked with (^) are not parents of the immediately preceding commit. These "breaks" represent necessary discontinuities implied by trying to represent an arbtirary DAG in a linear form.
+
+*--show-breaks* is only valid if *--merge-order* is also specified.
Author
------
Written by Linus Torvalds <torvalds@osdl.org>
+Original *--merge-order* logic by Jon Seymour <jon.seymour@gmail.com>
+
Documentation
--------------
Documentation by David Greaves, Junio C Hamano and the git-list <git@vger.kernel.org>.
diff --git a/Makefile b/Makefile
--- a/Makefile
+++ b/Makefile
@@ -40,9 +40,9 @@ install: $(PROG) $(SCRIPTS)
$(INSTALL) $(PROG) $(SCRIPTS) $(dest)$(bin)
LIB_OBJS=read-cache.o sha1_file.o usage.o object.o commit.o tree.o blob.o \
- tag.o delta.o date.o index.o diff-delta.o patch-delta.o
+ tag.o delta.o date.o index.o diff-delta.o patch-delta.o epoch.o
LIB_FILE=libgit.a
-LIB_H=cache.h object.h blob.h tree.h commit.h tag.h delta.h
+LIB_H=cache.h object.h blob.h tree.h commit.h tag.h delta.h epoch.h
LIB_H += strbuf.h
LIB_OBJS += strbuf.o
@@ -134,6 +134,7 @@ diffcore-pathspec.o : $(LIB_H) diffcore.
diffcore-pickaxe.o : $(LIB_H) diffcore.h
diffcore-break.o : $(LIB_H) diffcore.h
diffcore-order.o : $(LIB_H) diffcore.h
+epoch.o: $(LIB_H)
test: all
$(MAKE) -C t/ all
diff --git a/commit.c b/commit.c
--- a/commit.c
+++ b/commit.c
@@ -129,7 +129,7 @@ void free_commit_list(struct commit_list
}
}
-static void insert_by_date(struct commit_list **list, struct commit *item)
+void insert_by_date(struct commit_list **list, struct commit *item)
{
struct commit_list **pp = list;
struct commit_list *p;
@@ -254,3 +254,25 @@ unsigned long pretty_print_commit(const
buf[offset] = '\0';
return offset;
}
+
+struct commit *pop_commit(struct commit_list **stack)
+{
+ struct commit_list *top = *stack;
+ struct commit *item = top ? top->item : NULL;
+
+ if (top) {
+ *stack = top->next;
+ free(top);
+ }
+ return item;
+}
+
+int count_parents(struct commit * commit)
+{
+ int count = 0;
+ struct commit_list * parents = commit->parents;
+ for (count=0;parents; parents=parents->next,count++)
+ ;
+ return count;
+}
+
diff --git a/commit.h b/commit.h
--- a/commit.h
+++ b/commit.h
@@ -32,6 +32,8 @@ void free_commit_list(struct commit_list
void sort_by_date(struct commit_list **list);
+void insert_by_date(struct commit_list **list, struct commit *item);
+
extern unsigned long pretty_print_commit(const char *msg, unsigned long len, char *buf, unsigned long space);
@@ -41,4 +43,7 @@ extern unsigned long pretty_print_commit
struct commit *pop_most_recent_commit(struct commit_list **list,
unsigned int mark);
+struct commit *pop_commit(struct commit_list **stack);
+
+int count_parents(struct commit * commit);
#endif /* COMMIT_H */
diff --git a/epoch.c b/epoch.c
new file mode 100644
--- /dev/null
+++ b/epoch.c
@@ -0,0 +1,454 @@
+/*
+ * Copyright (c) 2005, Jon Seymour
+ *
+ * For more information about epoch theory on which this module is based,
+ * refer to http://blackcubes.dyndns.org/epoch/. That web page defines
+ * terms such as "epoch" and "minimal, non-linear epoch" and provides rationales
+ * for some of the algorithms used here.
+ *
+ */
+#include <stdlib.h>
+#include <openssl/bn.h> // provides arbitrary precision integers required to accurately represent fractional mass
+#include "cache.h"
+#include "commit.h"
+#include "epoch.h"
+
+struct fraction {
+ BIGNUM numerator;
+ BIGNUM denominator;
+};
+
+#define HAS_EXACTLY_ONE_PARENT(n) ((n)->parents && !(n)->parents->next)
+
+static BN_CTX *context = NULL;
+static struct fraction *one = NULL;
+static struct fraction *zero = NULL;
+
+static BN_CTX *get_BN_CTX()
+{
+ if (!context) {
+ context = BN_CTX_new();
+ }
+ return context;
+}
+
+static struct fraction *new_zero()
+{
+ struct fraction *result = xmalloc(sizeof(*result));
+ BN_init(&result->numerator);
+ BN_init(&result->denominator);
+ BN_zero(&result->numerator);
+ BN_one(&result->denominator);
+ return result;
+}
+
+static void clear_fraction(struct fraction *fraction)
+{
+ BN_clear(&fraction->numerator);
+ BN_clear(&fraction->denominator);
+}
+
+static struct fraction *divide(struct fraction *result, struct fraction *fraction, int divisor)
+{
+ BIGNUM bn_divisor;
+
+ BN_init(&bn_divisor);
+ BN_set_word(&bn_divisor, divisor);
+
+ BN_copy(&result->numerator, &fraction->numerator);
+ BN_mul(&result->denominator, &fraction->denominator, &bn_divisor, get_BN_CTX());
+
+ BN_clear(&bn_divisor);
+ return result;
+}
+
+static struct fraction *init_fraction(struct fraction *fraction)
+{
+ BN_init(&fraction->numerator);
+ BN_init(&fraction->denominator);
+ BN_zero(&fraction->numerator);
+ BN_one(&fraction->denominator);
+ return fraction;
+}
+
+static struct fraction *get_one()
+{
+ if (!one) {
+ one = new_zero();
+ BN_one(&one->numerator);
+ }
+ return one;
+}
+
+static struct fraction *get_zero()
+{
+ if (!zero) {
+ zero = new_zero();
+ }
+ return zero;
+}
+
+static struct fraction *copy(struct fraction *to, struct fraction *from)
+{
+ BN_copy(&to->numerator, &from->numerator);
+ BN_copy(&to->denominator, &from->denominator);
+ return to;
+}
+
+static struct fraction *add(struct fraction *result, struct fraction *left, struct fraction *right)
+{
+ BIGNUM a, b, gcd;
+
+ BN_init(&a);
+ BN_init(&b);
+ BN_init(&gcd);
+
+ BN_mul(&a, &left->numerator, &right->denominator, get_BN_CTX());
+ BN_mul(&b, &left->denominator, &right->numerator, get_BN_CTX());
+ BN_mul(&result->denominator, &left->denominator, &right->denominator, get_BN_CTX());
+ BN_add(&result->numerator, &a, &b);
+
+ BN_gcd(&gcd, &result->denominator, &result->numerator, get_BN_CTX());
+ BN_div(&result->denominator, NULL, &result->denominator, &gcd, get_BN_CTX());
+ BN_div(&result->numerator, NULL, &result->numerator, &gcd, get_BN_CTX());
+
+ BN_clear(&a);
+ BN_clear(&b);
+ BN_clear(&gcd);
+
+ return result;
+}
+
+static int compare(struct fraction *left, struct fraction *right)
+{
+ BIGNUM a, b;
+
+ int result;
+
+ BN_init(&a);
+ BN_init(&b);
+
+ BN_mul(&a, &left->numerator, &right->denominator, get_BN_CTX());
+ BN_mul(&b, &left->denominator, &right->numerator, get_BN_CTX());
+
+ result = BN_cmp(&a, &b);
+
+ BN_clear(&a);
+ BN_clear(&b);
+
+ return result;
+}
+
+struct mass_counter {
+ struct fraction seen;
+ struct fraction pending;
+};
+
+static struct mass_counter *new_mass_counter(struct commit *commit, struct fraction *pending)
+{
+ struct mass_counter *mass_counter = xmalloc(sizeof(*mass_counter));
+ memset(mass_counter, 0, sizeof(*mass_counter));
+
+ init_fraction(&mass_counter->seen);
+ init_fraction(&mass_counter->pending);
+
+ copy(&mass_counter->pending, pending);
+ copy(&mass_counter->seen, get_zero());
+
+ commit->object.util = mass_counter;
+
+ return mass_counter;
+}
+
+static void free_mass_counter(struct mass_counter *counter)
+{
+ clear_fraction(&counter->seen);
+ clear_fraction(&counter->pending);
+ free(counter);
+}
+
+//
+// Finds the base node of an epoch.
+//
+// This algorithm uses a conservation of mass approach.
+//
+// The head starts with a weight of 1 and distributes equal portions
+// along each edge to each of its parents. The process continues until
+// one node discovers that it has acquired a total mass of 1 from its
+// descendents. This node is the base node.
+//
+// Importantly the queue of nodes to be processed is sorted in
+// reverse date order and each node occupies at most one
+// position in the queue simultaneously. These two properties
+// do not effect the algorithm's correctness. However assuming most, but
+// not all, timestamps are sane they do prevent the algorithm becoming
+// exponential by ensuring that most nodes are only visited once.
+// This is true because mass is only propagated through the network
+// when we are pretty sure we are not going to see any more coming
+// our way. The occasional bad timestamp will mean that we are
+// wrong, occasionally, but this does not matter too much.
+//
+static int find_base(struct commit *head, struct commit **boundary)
+{
+ int ret = 0;
+
+ struct commit_list *cleaner = NULL;
+ struct commit_list *pending = NULL;
+
+ *boundary = NULL;
+
+ // we inject a mass of 1 unit here
+
+ new_mass_counter(head, get_one());
+
+ commit_list_insert(head, &pending);
+ commit_list_insert(head, &cleaner);
+
+ while (!*boundary && pending && !ret) {
+
+ struct commit *latest = pop_commit(&pending);
+ struct mass_counter *latest_node = (struct mass_counter *) latest->object.util;
+
+ if ((ret = parse_commit(latest)))
+ continue;
+
+ add(&latest_node->seen, &latest_node->seen, &latest_node->pending);
+
+ int num_parents = count_parents(latest);
+
+ if (num_parents) {
+
+ struct fraction distribution;
+
+ divide(init_fraction(&distribution), &latest_node->pending, num_parents);
+
+ struct commit_list *parents;
+
+ for (parents = latest->parents; parents; parents = parents->next) {
+ struct commit *parent = parents->item;
+ struct mass_counter *parent_node = (struct mass_counter *) parent->object.util;
+ if (!parent_node) {
+ parent_node = new_mass_counter(parent, &distribution);
+ commit_list_insert(parent, &cleaner);
+ insert_by_date(&pending, parent);
+ } else {
+ if (!compare(&parent_node->pending, get_zero())) {
+ copy(&parent_node->pending, &distribution);
+ insert_by_date(&pending, parent);
+ } else {
+ add(&parent_node->pending, &parent_node->pending, &distribution);
+ }
+ }
+ }
+ }
+
+ if (!compare(&latest_node->seen, get_one()) && (latest != head)) {
+ // if this node has seen one unit of mass, it must be the base, so mark
+ // the boundary which will cause the loop to stop.
+ *boundary = latest;
+ }
+
+ copy(&latest_node->pending, get_zero());
+
+ }
+
+ for (; cleaner;) {
+ struct commit *next = pop_commit(&cleaner);
+ free_mass_counter((struct mass_counter *) next->object.util);
+ next->object.util = NULL;
+ }
+
+ if (pending)
+ free_commit_list(pending);
+
+ return ret;
+
+}
+
+//
+// This procedure traverses to the boundary of the first epoch in the epoch
+// sequence of the epoch headed at head_of_epoch. This is either the end of
+// the maximal linear epoch or the base of a minimal non-linear epoch.
+//
+// The queue of pending nodes is sorted in reverse date order and each node
+// is currently in the queue at most once.
+//
+static int find_next_epoch_boundary(struct commit *head_of_epoch, struct commit **boundary)
+{
+ int ret;
+ struct commit *item = head_of_epoch;
+
+ ret = parse_commit(item);
+ if (ret)
+ return ret;
+
+ if (HAS_EXACTLY_ONE_PARENT(item)) {
+
+ // we are at the start of a maximimal linear epoch .. traverse to the end
+
+ // traverse to the end of a maximal linear epoch
+ while (HAS_EXACTLY_ONE_PARENT(item) && !ret) {
+ item = item->parents->item;
+ ret = parse_commit(item);
+ }
+ *boundary = item;
+
+ } else {
+
+ // otherwise, we are at the start of a minimal, non-linear
+ // epoch - find the common base of all parents.
+
+ ret = find_base(item, boundary);
+
+ }
+
+ return ret;
+}
+
+//
+// Returns non-zero if parent is known to be a parent of child.
+//
+static int is_parent_of(struct commit *parent, struct commit *child)
+{
+ struct commit_list *parents;
+ for (parents = child->parents; parents; parents = parents->next) {
+ if (!memcmp(parent->object.sha1, parents->item->object.sha1, sizeof(parents->item->object.sha1)))
+ return 1;
+ }
+ return 0;
+}
+
+static void push_onto_merge_order_stack(struct commit_list **stack, struct commit *item)
+{
+ struct commit_list *top = *stack;
+ if (top && (top->item->object.flags & MERGE_ORDER_BREAK_FLAG)) {
+ if (is_parent_of(top->item, item)) {
+ top->item->object.flags &= ~MERGE_ORDER_BREAK_FLAG;
+ }
+ }
+ commit_list_insert(item, stack);
+}
+
+//
+// Sorts the nodes of the first epoch of the epoch sequence of the epoch headed at head
+// into merge order.
+//
+static void sort_first_epoch(struct commit *head, struct commit_list **stack)
+{
+ parse_commit(head);
+
+ head->object.flags |= MERGE_ORDER_VISIT_FLAG;
+
+ struct commit_list *parents;
+
+ struct commit_list *reversed_parents = NULL;
+
+ //
+ // parse_commit builds the parent list in reverse order with respect to the order of
+ // the git-commit-tree arguments.
+ //
+ // so we need to reverse this list to output the oldest (or most "local") commits last.
+ //
+
+ for (parents = head->parents; parents; parents = parents->next) {
+ commit_list_insert(parents->item, &reversed_parents);
+ }
+
+ //
+ // todo: by sorting the parents in a different order, we can alter the
+ // merge order to show contemporaneous changes in parallel branches
+ // occurring after "local" changes. This is useful for a developer
+ // when a developer wants to see all changes that were incorporated
+ // into the same merge as her own changes occur after her own
+ // changes.
+ //
+
+ for (; reversed_parents;) {
+ struct commit *parent = pop_commit(&reversed_parents);
+ parse_commit(parent);
+ if (!(parent->object.flags & MERGE_ORDER_VISIT_FLAG)) {
+ if (parent->object.flags & MERGE_ORDER_EPOCH_FLAG) {
+ if (*stack) {
+ die("something else is on the stack - %s\n", sha1_to_hex((*stack)->item->object.sha1));
+ }
+ push_onto_merge_order_stack(stack, parent);
+ parent->object.flags |= MERGE_ORDER_VISIT_FLAG;
+ } else {
+ sort_first_epoch(parent, stack);
+ if (reversed_parents) {
+ //
+ // this indicates a possible discontinuity
+ // it may not be be actual discontinuity if
+ // the head of parent N happens to be the tail
+ // of parent N+1
+ //
+ // the next push onto the stack will resolve the question
+ //
+ (*stack)->item->object.flags |= MERGE_ORDER_BREAK_FLAG;
+ }
+ }
+ }
+ }
+
+ push_onto_merge_order_stack(stack, head);
+}
+
+//
+// Sorts an arbitrary epoch into merge order by sorting each epoch
+// of its epoch sequence into order.
+//
+// Note: this algorithm currently leaves traces of its execution in the
+// object flags of nodes it discovers. This should probably be fixed.
+//
+int sort_in_merge_order(struct commit *head_of_epoch, emitter_func emitter)
+{
+ struct commit *next;
+ int ret = 0;
+ int stop = 0;
+
+ parse_commit(head_of_epoch);
+
+ for (next = head_of_epoch; next && next->parents && !ret && !stop;) {
+
+ struct commit *base = NULL;
+
+ ret = find_next_epoch_boundary(next, &base);
+ if (ret)
+ return ret;
+
+ next->object.flags |= MERGE_ORDER_EPOCH_FLAG;
+ if (base) {
+ base->object.flags |= MERGE_ORDER_EPOCH_FLAG;
+ }
+
+ if (HAS_EXACTLY_ONE_PARENT(next)) {
+
+ while (HAS_EXACTLY_ONE_PARENT(next) && !stop && !ret) {
+ stop = (*emitter) (next);
+ next = next->parents->item;
+ ret = parse_commit(next);
+ }
+
+ } else {
+
+ struct commit_list *stack = NULL;
+ sort_first_epoch(next, &stack);
+ for (; stack && !stop;) {
+ next = pop_commit(&stack);
+ if (stack) {
+ stop = (*emitter) (next);
+ }
+ }
+ if (stack) {
+ free_commit_list(stack);
+ }
+ }
+
+ }
+
+ if (next && !stop) {
+ stop = (*emitter) (next);
+ }
+
+ return ret;
+}
diff --git a/epoch.h b/epoch.h
new file mode 100644
--- /dev/null
+++ b/epoch.h
@@ -0,0 +1,12 @@
+#ifndef EPOCH_H
+#define EPOCH_H
+
+typedef int (*emitter_func) (struct commit *);
+
+int sort_in_merge_order(struct commit *head_of_epoch, emitter_func emitter);
+
+#define MERGE_ORDER_EPOCH_FLAG (1u<<3)
+#define MERGE_ORDER_VISIT_FLAG (1u<<4)
+#define MERGE_ORDER_BREAK_FLAG (1u<<5)
+
+#endif /* EPOCH_H */
diff --git a/object.h b/object.h
--- a/object.h
+++ b/object.h
@@ -15,6 +15,7 @@ struct object {
const char *type;
struct object_list *refs;
struct object_list *attached_deltas;
+ void *util;
};
extern int nr_objs;
diff --git a/rev-list.c b/rev-list.c
--- a/rev-list.c
+++ b/rev-list.c
@@ -1,5 +1,6 @@
#include "cache.h"
#include "commit.h"
+#include "epoch.h"
#define SEEN (1u << 0)
#define INTERESTING (1u << 1)
@@ -11,7 +12,8 @@ static const char rev_list_usage[] =
" --max-age=epoch\n"
" --min-age=epoch\n"
" --header\n"
- " --pretty";
+ " --pretty\n"
+ " --merge-order [ --show-breaks ]";
static int verbose_header = 0;
static int show_parents = 0;
@@ -21,27 +23,49 @@ static const char *prefix = "";
static unsigned long max_age = -1;
static unsigned long min_age = -1;
static int max_count = -1;
+static int merge_order = 0;
+static int show_breaks = 0;
-static void show_commit(struct commit *commit)
+static int show_commit(struct commit *commit)
{
- printf("%s%s", prefix, sha1_to_hex(commit->object.sha1));
- if (show_parents) {
- struct commit_list *parents = commit->parents;
- while (parents) {
- printf(" %s", sha1_to_hex(parents->item->object.sha1));
- parents = parents->next;
- }
- }
- putchar('\n');
- if (verbose_header) {
- const char *buf = commit->buffer;
- if (pretty_print) {
- static char pretty_header[16384];
- pretty_print_commit(commit->buffer, ~0, pretty_header, sizeof(pretty_header));
- buf = pretty_header;
- }
- printf("%s%c", buf, hdr_termination);
+ if (commit->object.flags & UNINTERESTING)
+ return 0;
+ if (min_age != -1 && (commit->date > min_age))
+ return 0;
+ if (max_age != -1 && (commit->date < max_age))
+ return 1;
+ if (max_count != -1 && !max_count--)
+ return 1;
+
+ if (!show_breaks) {
+ printf("%s%s", prefix, sha1_to_hex(commit->object.sha1));
+ if (show_parents) {
+ struct commit_list *parents = commit->parents;
+ while (parents) {
+ printf(" %s", sha1_to_hex(parents->item->object.sha1));
+ parents = parents->next;
+ }
+ }
+ putchar('\n');
+ if (verbose_header) {
+ const char *buf = commit->buffer;
+ if (pretty_print) {
+ static char pretty_header[16384];
+ pretty_print_commit(commit->buffer, ~0, pretty_header, sizeof(pretty_header));
+ buf = pretty_header;
+ }
+ printf("%s%c", buf, hdr_termination);
+ }
+ } else {
+ char c='|';
+ if (commit->object.flags & MERGE_ORDER_BREAK_FLAG) {
+ c = '^';
+ } else if (commit->object.flags & MERGE_ORDER_EPOCH_FLAG) {
+ c = '=';
+ }
+ printf("%c %s\n", c, sha1_to_hex(commit->object.sha1));
}
+ return 0;
}
static void show_commit_list(struct commit_list *list)
@@ -49,15 +73,8 @@ static void show_commit_list(struct comm
while (list) {
struct commit *commit = pop_most_recent_commit(&list, SEEN);
- if (commit->object.flags & UNINTERESTING)
- continue;
- if (min_age != -1 && (commit->date > min_age))
- continue;
- if (max_age != -1 && (commit->date < max_age))
- break;
- if (max_count != -1 && !max_count--)
- break;
- show_commit(commit);
+ if (show_commit(commit))
+ break;
}
}
@@ -142,8 +159,16 @@ int main(int argc, char **argv)
show_parents = 1;
continue;
}
+ if (!strncmp(arg, "--merge-order", 13)) {
+ merge_order = 1;
+ continue;
+ }
+ if (!strncmp(arg, "--show-breaks", 13)) {
+ show_breaks = 1;
+ continue;
+ }
- if (nr_sha > 2 || get_sha1(arg, sha1[nr_sha]))
+ if (nr_sha > 2 || get_sha1(arg, sha1[nr_sha])|| (show_breaks && !merge_order))
usage(rev_list_usage);
nr_sha++;
}
@@ -166,6 +191,14 @@ int main(int argc, char **argv)
if (end)
list = limit_list(list, end);
- show_commit_list(list);
+
+ if (!merge_order) {
+ show_commit_list(list);
+ } else {
+ if (sort_in_merge_order(commit, &show_commit)) {
+ die("merge order sort failed\n");
+ }
+ }
+
return 0;
}
diff --git a/t/t6000-rev-list.sh b/t/t6000-rev-list.sh
new file mode 100755
--- /dev/null
+++ b/t/t6000-rev-list.sh
@@ -0,0 +1,85 @@
+#!/bin/sh
+#
+# Copyright (c) 2005 Jon Seymour
+#
+
+test_description='Test rev-list --merge-order
+'
+. ./test-lib.sh
+
+function do_commit
+{
+ git-commit-tree "$@" </dev/null
+}
+
+function check_adjacency
+{
+ read previous
+ echo "= $previous"
+ while read next
+ do
+ if ! (git-cat-file commit $previous | grep "^parent $next" >/dev/null)
+ then
+ echo "^ $next"
+ else
+ echo "| $next"
+ fi
+ previous=$next
+ done
+}
+
+function sed_script
+{
+ for c in root a0 a1 a2 a3 a4 b1 b2 b3 b4 c1 c2 c3
+ do
+ echo -n "s/${!c}/$c/;"
+ done
+}
+
+date >path0
+git-update-cache --add path0
+tree=$(git-write-tree)
+root=$(do_commit $tree)
+export GIT_COMMITTER_NAME=foobar # to guarantee that the commit is different
+a0=$(do_commit $tree -p $root)
+a1=$(do_commit $tree -p $a0)
+export GIT_COMMITTER_NAME=foobar2 # to guarantee that the commit is different
+b1=$(do_commit $tree -p $root)
+c1=$(do_commit $tree -p $b1)
+export GIT_COMMITTER_NAME=foobar3 # to guarantee that the commit is different
+b2=$(do_commit $tree -p $b1)
+b3=$(do_commit $tree -p $b2)
+c2=$(do_commit $tree -p $c1 -p $b2)
+c3=$(do_commit $tree -p $c2)
+a2=$(do_commit $tree -p $a1)
+a3=$(do_commit $tree -p $a2)
+b4=$(do_commit $tree -p $b3 -p $a3)
+a4=$(do_commit $tree -p $a3 -p $b4 -p $c3)
+echo $a4 > .git/HEAD
+
+git-rev-list --merge-order --show-breaks HEAD | sed "$(sed_script)" > actual-merge-order
+cat > expected-merge-order <<EOF
+= a4
+| c3
+| c2
+| c1
+^ b4
+| b3
+| b2
+| b1
+^ a3
+| a2
+| a1
+| a0
+= root
+EOF
+
+git-rev-list HEAD | check_adjacency | sed "$(sed_script)" > actual-default-order
+normal_adjacency_count=$(git-rev-list HEAD | check_adjacency | grep -c "\^" | tr -d ' ')
+merge_order_adjacency_count=$(git-rev-list --merge-order HEAD | check_adjacency | grep -c "\^" | tr -d ' ')
+
+test_expect_success 'Testing that the rev-list has correct number of entries' '[ $(git-rev-list HEAD | wc -l) -eq 13 ]'
+test_expect_success 'Testing that --merge-order produces the correct result' 'diff expected-merge-order actual-merge-order'
+test_expect_success 'Testing that --merge-order produces as many or fewer discontinuities' '[ $merge_order_adjacency_count -le $normal_adjacency_count ]'
+
+test_done
^ permalink raw reply
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