diff options
author | jon@blackcubes.dyndns.org <jon@blackcubes.dyndns.org> | 2005-06-06 19:39:40 +0400 |
---|---|---|
committer | Linus Torvalds <torvalds@ppc970.osdl.org> | 2005-06-06 20:07:26 +0400 |
commit | a3437b8c26a63d971437c8b6ac6f6d4f632be548 (patch) | |
tree | 0e99213a652fbf3fbe2fa6e3d2562808fc776543 /Documentation | |
parent | d925ffbd064802bc8a6ab0bccf0c43b00a7fe710 (diff) |
[PATCH] Modify git-rev-list to linearise the commit history in merge order.
This patch linearises the GIT commit history graph into merge order
which is defined by invariants specified in Documentation/git-rev-list.txt.
The linearisation produced by this patch is superior in an objective sense
to that produced by the existing git-rev-list implementation in that
the linearisation produced is guaranteed to have the minimum number of
discontinuities, where a discontinuity is defined as an adjacent pair of
commits in the output list which are not related in a direct child-parent
relationship.
With this patch a graph like this:
a4 ---
| \ \
| b4 |
|/ | |
a3 | |
| | |
a2 | |
| | c3
| | |
| | c2
| b3 |
| | /|
| b2 |
| | c1
| | /
| b1
a1 |
| |
a0 |
| /
root
Sorts like this:
= a4
| c3
| c2
| c1
^ b4
| b3
| b2
| b1
^ a3
| a2
| a1
| a0
= root
Instead of this:
= a4
| c3
^ b4
| a3
^ c2
^ b3
^ a2
^ b2
^ c1
^ a1
^ b1
^ a0
= root
A test script, t/t6000-rev-list.sh, includes a test which demonstrates
that the linearisation produced by --merge-order has less discontinuities
than the linearisation produced by git-rev-list without the --merge-order
flag specified. To see this, do the following:
cd t
./t6000-rev-list.sh
cd trash
cat actual-default-order
cat actual-merge-order
The existing behaviour of git-rev-list is preserved, by default. To obtain
the modified behaviour, specify --merge-order or --merge-order --show-breaks
on the command line.
This version of the patch has been tested on the git repository and also on the linux-2.6
repository and has reasonable performance on both - ~50-100% slower than the original algorithm.
This version of the patch has incorporated a functional equivalent of the Linus' output limiting
algorithm into the merge-order algorithm itself. This operates per the notes associated
with Linus' commit 337cb3fb8da45f10fe9a0c3cf571600f55ead2ce.
This version has incorporated Linus' feedback regarding proposed changes to rev-list.c.
(see: [PATCH] Factor out filtering in rev-list.c)
This version has improved the way sort_first_epoch marks commits as uninteresting.
For more details about this change, refer to Documentation/git-rev-list.txt
and http://blackcubes.dyndns.org/epoch/.
Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
Signed-off-by: Linus Torvalds <torvalds@osdl.org>
Diffstat (limited to 'Documentation')
-rw-r--r-- | Documentation/git-rev-list.txt | 30 |
1 files changed, 29 insertions, 1 deletions
diff --git a/Documentation/git-rev-list.txt b/Documentation/git-rev-list.txt index f2c5fa9f4c..3cfa58b5bd 100644 --- a/Documentation/git-rev-list.txt +++ b/Documentation/git-rev-list.txt @@ -9,7 +9,7 @@ git-rev-list - Lists commit objects in reverse chronological order 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 chronological order starting at the 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>. |