aboutsummaryrefslogtreecommitdiff
path: root/Documentation
diff options
context:
space:
mode:
authorjon@blackcubes.dyndns.org <jon@blackcubes.dyndns.org>2005-06-06 15:39:40 +0000
committerLinus Torvalds <torvalds@ppc970.osdl.org>2005-06-06 09:07:26 -0700
commita3437b8c26a63d971437c8b6ac6f6d4f632be548 (patch)
tree0e99213a652fbf3fbe2fa6e3d2562808fc776543 /Documentation
parentd925ffbd064802bc8a6ab0bccf0c43b00a7fe710 (diff)
downloadgit-a3437b8c26a63d971437c8b6ac6f6d4f632be548.tar.gz
git-a3437b8c26a63d971437c8b6ac6f6d4f632be548.tar.xz
[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.txt30
1 files changed, 29 insertions, 1 deletions
diff --git a/Documentation/git-rev-list.txt b/Documentation/git-rev-list.txt
index f2c5fa9f4..3cfa58b5b 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>.