Improve layout of branches in the commit graph

The aim of this change is to place all commits of a branch on the same
lane and commits of other (side) branches on different lanes.

The algorithm treats first parents of a commit specially by placing them
on the same lane as the commit itself. When a commit is the first parent
of multiple children it could be placed on any of these children's
lanes. In this case it is placed on the longest child lane, as this is
usually the lane of the branch the commit actually was made on.

Other (non-first) parents are placed on new lanes. This creates a layout
that should make it easier to see branches and merges and follow linear
branch histories.
This differs from the previous approach, which sometimes plotted the
commits of a side branch on the same lane as the base branch commits and
further commits on the base branch appeared on a different lane.
This made the base branch appear as if it was the side branch and
the side branch appears to be the base branch.

In addition to lane assignment, also the plotting code changed to start
drawing a branch lane from the commit where it forks out. Previously it
started only when the first commit on the branch appeared.

Active lanes are continued with every commit that is processed.
Previously lanes were only continued when the next commit on the lane
was encountered. This could produce (temporarily) dangling commits if
the next commit on the lane was not processed yet.

CQ: 8299
Bug: 419359
Bug: 434945
Change-Id: Ibe547aa24b5948ae264f7d0f56a492a4ef335608
Signed-off-by: Konrad Kügler <swamblumat-eclipsebugs@yahoo.de>
Signed-off-by: Matthias Sohn <matthias.sohn@sap.com>

3 files changed, 257 insertions, 95 deletions

diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revplot/AbstractPlotRenderer.java b/org.eclipse.jgit/src/org/eclipse/jgit/revplot/AbstractPlotRenderer.java
index 2ea65be58a..0fac3af9b9 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/revplot/AbstractPlotRenderer.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/revplot/AbstractPlotRenderer.java
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2008, Shawn O. Pearce <spearce@spearce.org>
+ * Copyright (C) 2008, 2014 Shawn O. Pearce <spearce@spearce.org>
  * and other copyright owners as documented in the project's IP log.
  *
  * This program and the accompanying materials are made available
@@ -105,42 +105,63 @@ public abstract class AbstractPlotRenderer<TLane extends PlotLane, TColor> {
 			maxCenter = Math.max(maxCenter, cx);
 		}
 
+		final int dotX = myLaneX - dotSize / 2 - 1;
+		final int dotY = (h - dotSize) / 2;
+
 		final int nParent = commit.getParentCount();
-		for (int i = 0; i < nParent; i++) {
-			final PlotCommit<TLane> p;
-			final TLane pLane;
-			final TColor pColor;
-			final int cx;
+		if (nParent > 0) {
+			drawLine(myColor, myLaneX, h, myLaneX, (h + dotSize) / 2,
+					LINE_WIDTH);
 
-			p = (PlotCommit<TLane>) commit.getParent(i);
-			pLane = p.getLane();
-			if (pLane == null)
-				continue;
+			for (int i = 0; i < commit.mergingLanes.length; i++) {
+				@SuppressWarnings("unchecked")
+				final TLane pLane = (TLane) commit.mergingLanes[i];
+				final TColor pColor = laneColor(pLane);
+				final int cx = laneC(pLane);
 
-			pColor = laneColor(pLane);
-			cx = laneC(pLane);
+				if (Math.abs(myLaneX - cx) > LANE_WIDTH) {
+					final int ix;
+					if (myLaneX < cx)
+						ix = cx - LANE_WIDTH / 2;
+					else
+						ix = cx + LANE_WIDTH / 2;
 
-			if (Math.abs(myLaneX - cx) > LANE_WIDTH) {
-				if (myLaneX < cx) {
-					final int ix = cx - LANE_WIDTH / 2;
 					drawLine(pColor, myLaneX, h / 2, ix, h / 2, LINE_WIDTH);
 					drawLine(pColor, ix, h / 2, cx, h, LINE_WIDTH);
-				} else {
-					final int ix = cx + LANE_WIDTH / 2;
-					drawLine(pColor, myLaneX, h / 2, ix, h / 2, LINE_WIDTH);
-					drawLine(pColor, ix, h / 2, cx, h, LINE_WIDTH);
-				}
-			} else {
-				drawLine(pColor, myLaneX, h / 2, cx, h, LINE_WIDTH);
+				} else
+					drawLine(pColor, myLaneX, h / 2, cx, h, LINE_WIDTH);
+
+				maxCenter = Math.max(maxCenter, cx);
 			}
-			maxCenter = Math.max(maxCenter, cx);
 		}
 
-		final int dotX = myLaneX - dotSize / 2 - 1;
-		final int dotY = (h - dotSize) / 2;
 
-		if (commit.getChildCount() > 0)
-			drawLine(myColor, myLaneX, 0, myLaneX, dotY, LINE_WIDTH);
+		if (commit.getChildCount() > 0) {
+			for (int i = 0; i < commit.forkingOffLanes.length; i++) {
+				@SuppressWarnings("unchecked")
+				final TLane childLane = (TLane) commit.forkingOffLanes[i];
+				final TColor cColor = laneColor(childLane);
+				final int cx = laneC(childLane);
+				if (Math.abs(myLaneX - cx) > LANE_WIDTH) {
+					final int ix;
+					if (myLaneX < cx)
+						ix = cx - LANE_WIDTH / 2;
+					else
+						ix = cx + LANE_WIDTH / 2;
+
+					drawLine(cColor, myLaneX, h / 2, ix, h / 2, LINE_WIDTH);
+					drawLine(cColor, ix, h / 2, cx, 0, LINE_WIDTH);
+				} else {
+					drawLine(cColor, myLaneX, h / 2, cx, 0, LINE_WIDTH);
+				}
+				maxCenter = Math.max(maxCenter, cx);
+			}
+
+			int nonForkingChildren = commit.getChildCount()
+					- commit.forkingOffLanes.length;
+			if (nonForkingChildren > 0)
+						drawLine(myColor, myLaneX, 0, myLaneX, dotY, LINE_WIDTH);
+		}
 
 		if (commit.has(RevFlag.UNINTERESTING))
 			drawBoundaryDot(dotX, dotY, dotSize, dotSize);
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revplot/PlotCommit.java b/org.eclipse.jgit/src/org/eclipse/jgit/revplot/PlotCommit.java
index 4a413c306a..dba68465c2 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/revplot/PlotCommit.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/revplot/PlotCommit.java
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2008, Shawn O. Pearce <spearce@spearce.org>
+ * Copyright (C) 2008, 2014 Shawn O. Pearce <spearce@spearce.org>
  * and other copyright owners as documented in the project's IP log.
  *
  * This program and the accompanying materials are made available
@@ -61,8 +61,12 @@ public class PlotCommit<L extends PlotLane> extends RevCommit {
 
 	static final Ref[] NO_REFS = {};
 
+	PlotLane[] forkingOffLanes;
+
 	PlotLane[] passingLanes;
 
+	PlotLane[] mergingLanes;
+
 	PlotLane lane;
 
 	PlotCommit[] children;
@@ -77,23 +81,38 @@ public class PlotCommit<L extends PlotLane> extends RevCommit {
 	 */
 	protected PlotCommit(final AnyObjectId id) {
 		super(id);
+		forkingOffLanes = NO_LANES;
 		passingLanes = NO_LANES;
+		mergingLanes = NO_LANES;
 		children = NO_CHILDREN;
 		refs = NO_REFS;
 	}
 
+	void addForkingOffLane(final PlotLane f) {
+		forkingOffLanes = addLane(f, forkingOffLanes);
+	}
+
 	void addPassingLane(final PlotLane c) {
-		final int cnt = passingLanes.length;
+		passingLanes = addLane(c, passingLanes);
+	}
+
+	void addMergingLane(final PlotLane m) {
+		mergingLanes = addLane(m, mergingLanes);
+	}
+
+	private static PlotLane[] addLane(final PlotLane l, PlotLane[] lanes) {
+		final int cnt = lanes.length;
 		if (cnt == 0)
-			passingLanes = new PlotLane[] { c };
+			lanes = new PlotLane[] { l };
 		else if (cnt == 1)
-			passingLanes = new PlotLane[] { passingLanes[0], c };
+			lanes = new PlotLane[] { lanes[0], l };
 		else {
 			final PlotLane[] n = new PlotLane[cnt + 1];
-			System.arraycopy(passingLanes, 0, n, 0, cnt);
-			n[cnt] = c;
-			passingLanes = n;
+			System.arraycopy(lanes, 0, n, 0, cnt);
+			n[cnt] = l;
+			lanes = n;
 		}
+		return lanes;
 	}
 
 	void addChild(final PlotCommit c) {
@@ -185,7 +204,9 @@ public class PlotCommit<L extends PlotLane> extends RevCommit {
 
 	@Override
 	public void reset() {
+		forkingOffLanes = NO_LANES;
 		passingLanes = NO_LANES;
+		mergingLanes = NO_LANES;
 		children = NO_CHILDREN;
 		lane = null;
 		super.reset();
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revplot/PlotCommitList.java b/org.eclipse.jgit/src/org/eclipse/jgit/revplot/PlotCommitList.java
index 9cbd94e26f..36e4b4b3fa 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/revplot/PlotCommitList.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/revplot/PlotCommitList.java
@@ -1,6 +1,7 @@
 /*
  * Copyright (C) 2008, Shawn O. Pearce <spearce@spearce.org>,
  * Copyright (C) 2010, Christian Halstrick <christian.halstrick@sap.com>
+ * Copyright (C) 2014, Konrad Kügler
  * and other copyright owners as documented in the project's IP log.
  *
  * This program and the accompanying materials are made available
@@ -47,6 +48,7 @@ package org.eclipse.jgit.revplot;
 import java.text.MessageFormat;
 import java.util.BitSet;
 import java.util.Collection;
+import java.util.HashMap;
 import java.util.HashSet;
 import java.util.TreeSet;
 
@@ -76,12 +78,17 @@ public class PlotCommitList<L extends PlotLane> extends
 
 	private final HashSet<PlotLane> activeLanes = new HashSet<PlotLane>(32);
 
+	/** number of (child) commits on a lane */
+	private final HashMap<PlotLane, Integer> laneLength = new HashMap<PlotLane, Integer>(
+			32);
+
 	@Override
 	public void clear() {
 		super.clear();
 		positionsAllocated = 0;
 		freePositions.clear();
 		activeLanes.clear();
+		laneLength.clear();
 	}
 
 	@Override
@@ -121,97 +128,201 @@ public class PlotCommitList<L extends PlotLane> extends
 		final int nChildren = currCommit.getChildCount();
 		if (nChildren == 0) {
 			currCommit.lane = nextFreeLane();
-			closeLane(currCommit.lane);
+			continueActiveLanes(currCommit);
 			return;
 		}
 
 		if (nChildren == 1 && currCommit.children[0].getParentCount() < 2) {
 			// Only one child, child has only us as their parent.
 			// Stay in the same lane as the child.
-			//
-			final PlotCommit c = currCommit.children[0];
-			for (int r = index - 1; r >= 0; r--) {
-				final PlotCommit rObj = get(r);
-				if (rObj == c)
-					break;
-				rObj.addPassingLane(c.lane);
-			}
 
+			@SuppressWarnings("unchecked")
+			final PlotCommit<L> c = currCommit.children[0];
 			currCommit.lane = c.lane;
-			handleBlockedLanes(index, currCommit, nChildren);
+			Integer len = laneLength.get(currCommit.lane);
+			len = Integer.valueOf(len.intValue() + 1);
+			laneLength.put(currCommit.lane, len);
 		} else {
 			// More than one child, or our child is a merge.
-			// Use a different lane.
-			//
-
-			// Process all our children. Especially important when there is more
-			// than one child (e.g. a commit is processed where other branches
-			// fork out). For each child the following is done
-			// 1. If no lane was assigned to the child a new lane is created and
-			// assigned
-			// 2. The lane of the child is closed. If this frees a position,
-			// this position will be added freePositions list.
-			// If we have multiple children which where previously not on a lane
-			// each such child will get his own new lane but all those new lanes
-			// will be on the same position. We have to take care that not
-			// multiple newly created (in step 1) lanes occupy that position on
-			// which the
-			// parent's lane will be on. Therefore we delay closing the lane
-			// with the parents position until all children are processed.
-
-			// The lane on that position the current commit will be on
+
+			// We look for the child lane the current commit should continue.
+			// Candidate lanes for this are those with children, that have the
+			// current commit as their first parent.
+			// There can be multiple candidate lanes. In that case the longest
+			// lane is chosen, as this is usually the lane representing the
+			// branch the commit actually was made on.
+
+			// When there are no candidate lanes (i.e. the current commit has
+			// only children whose non-first parent it is) we place the current
+			// commit on a new lane.
+
+			// The lane the current commit will be placed on:
 			PlotLane reservedLane = null;
+			PlotCommit childOnReservedLane = null;
+			int lengthOfReservedLane = -1;
 
 			for (int i = 0; i < nChildren; i++) {
-				final PlotCommit c = currCommit.children[i];
-				if (reservedLane == null && activeLanes.contains(c.lane))
-					reservedLane = c.lane;
-				else
-					closeLane(c.lane);
+				@SuppressWarnings("unchecked")
+				final PlotCommit<L> c = currCommit.children[i];
+				if (c.getParent(0) == currCommit) {
+					Integer len = laneLength.get(c.lane);
+					// we may be the first parent for multiple lines of
+					// development, try to continue the longest one
+					if (len.intValue() > lengthOfReservedLane) {
+						reservedLane = c.lane;
+						childOnReservedLane = c;
+						lengthOfReservedLane = len.intValue();
+					}
+				}
 			}
 
-			// finally all children are processed. We can close the lane on that
-			// position our current commit will be on.
-			if (reservedLane != null)
-				closeLane(reservedLane);
-
-			currCommit.lane = nextFreeLane();
+			if (reservedLane != null) {
+				currCommit.lane = reservedLane;
+				laneLength.put(reservedLane,
+						Integer.valueOf(lengthOfReservedLane + 1));
+				handleBlockedLanes(index, currCommit, childOnReservedLane);
+			} else {
+				currCommit.lane = nextFreeLane();
+				handleBlockedLanes(index, currCommit, null);
+			}
 
-			handleBlockedLanes(index, currCommit, nChildren);
+			// close lanes of children, if there are no first parents that might
+			// want to continue the child lanes
+			for (int i = 0; i < nChildren; i++) {
+				final PlotCommit c = currCommit.children[i];
+				PlotCommit firstParent = (PlotCommit) c.getParent(0);
+				if (firstParent.lane != null && firstParent.lane != c.lane)
+					closeLane(c.lane);
+			}
 		}
+		continueActiveLanes(currCommit);
+	}
+
+	private void continueActiveLanes(final PlotCommit currCommit) {
+		for (PlotLane lane : activeLanes)
+			if (lane != currCommit.lane)
+				currCommit.addPassingLane(lane);
 	}
 
 	/**
-	 * when connecting a plotcommit to the child make sure that you will not be
-	 * located on a lane on which a passed commit is located on. Otherwise we
-	 * would have to draw a line through a commit.
+	 * Sets up fork and merge information in the involved PlotCommits.
+	 * Recognizes and handles blockades that involve forking or merging arcs.
 	 *
 	 * @param index
-	 * @param commit
-	 * @param nChildren
+	 *            the index of <code>currCommit</code> in the list
+	 * @param currCommit
+	 * @param childOnLane
+	 *            the direct child on the same lane as <code>currCommit</code>,
+	 *            may be null if <code>currCommit</code> is the first commit on
+	 *            the lane
 	 */
-	private void handleBlockedLanes(final int index,
-			final PlotCommit<L> commit, final int nChildren) {
-		// take care:
-		int remaining = nChildren;
+	private void handleBlockedLanes(final int index, final PlotCommit currCommit,
+			final PlotCommit childOnLane) {
+		for (PlotCommit child : currCommit.children) {
+			if (child == childOnLane)
+				continue; // simple continuations of lanes are handled by
+							// continueActiveLanes() calls in enter()
+
+			// Is the child a merge or is it forking off?
+			boolean childIsMerge = child.getParent(0) != currCommit;
+			if (childIsMerge) {
+				PlotLane laneToUse = currCommit.lane;
+				laneToUse = handleMerge(index, currCommit, childOnLane, child,
+						laneToUse);
+				child.addMergingLane(laneToUse);
+			} else {
+				// We want to draw a forking arc in the child's lane.
+				// As an active lane, the child lane already continues
+				// (unblocked) up to this commit, we only need to mark it as
+				// forking off from the current commit.
+				PlotLane laneToUse = child.lane;
+				currCommit.addForkingOffLane(laneToUse);
+			}
+		}
+	}
+
+	// Handles the case where currCommit is a non-first parent of the child
+	private PlotLane handleMerge(final int index, final PlotCommit currCommit,
+			final PlotCommit childOnLane, PlotCommit child, PlotLane laneToUse) {
+
+		// find all blocked positions between currCommit and this child
+
+		int childIndex = index; // useless initialization, should
+								// always be set in the loop below
 		BitSet blockedPositions = new BitSet();
 		for (int r = index - 1; r >= 0; r--) {
 			final PlotCommit rObj = get(r);
-			if (commit.isChild(rObj)) {
-				if (--remaining == 0)
-					break;
+			if (rObj == child) {
+				childIndex = r;
+				break;
 			}
 			addBlockedPosition(blockedPositions, rObj);
-			if (rObj != null) {
-				rObj.addPassingLane(commit.lane);
+		}
+
+		// handle blockades
+
+		if (blockedPositions.get(laneToUse.getPosition())) {
+			// We want to draw a merging arc in our lane to the child,
+			// which is on another lane, but our lane is blocked.
+
+			// Check if childOnLane is beetween commit and the child we
+			// are currently processing
+			boolean needDetour = false;
+			if (childOnLane != null) {
+				for (int r = index - 1; r > childIndex; r--) {
+					final PlotCommit rObj = get(r);
+					if (rObj == childOnLane) {
+						needDetour = true;
+						break;
+					}
+				}
+			}
+
+			if (needDetour) {
+				// It is childOnLane which is blocking us. Repositioning
+				// our lane would not help, because this repositions the
+				// child too, keeping the blockade.
+				// Instead, we create a "detour lane" which gets us
+				// around the blockade. That lane has no commits on it.
+				laneToUse = nextFreeLane(blockedPositions);
+				currCommit.addForkingOffLane(laneToUse);
+				closeLane(laneToUse);
+			} else {
+				// The blockade is (only) due to other (already closed)
+				// lanes at the current lane's position. In this case we
+				// reposition the current lane.
+				// We are the first commit on this lane, because
+				// otherwise the child commit on this lane would have
+				// kept other lanes from blocking us. Since we are the
+				// first commit, we can freely reposition.
+				int newPos = getFreePosition(blockedPositions);
+				freePositions.add(Integer.valueOf(laneToUse
+						.getPosition()));
+				laneToUse.position = newPos;
 			}
 		}
-		// Now let's check whether we have to reposition the lane
-		if (blockedPositions.get(commit.lane.getPosition())) {
-			int newPos = getFreePosition(blockedPositions);
-			freePositions.add(Integer.valueOf(commit.lane.getPosition()));
-			commit.lane.position = newPos;
-			activeLanes.add(commit.lane);
+
+		// Actually connect currCommit to the merge child
+		drawLaneToChild(index, child, laneToUse);
+		return laneToUse;
+	}
+
+	/**
+	 * Connects the commit at commitIndex to the child, using the given lane.
+	 * All blockades on the lane must be resolved before calling this method.
+	 *
+	 * @param commitIndex
+	 * @param child
+	 * @param laneToContinue
+	 */
+	private void drawLaneToChild(final int commitIndex, PlotCommit child,
+			PlotLane laneToContinue) {
+		for (int r = commitIndex - 1; r >= 0; r--) {
+			final PlotCommit rObj = get(r);
+			if (rObj == child)
+				break;
+			if (rObj != null)
+				rObj.addPassingLane(laneToContinue);
 		}
 	}
 
@@ -222,12 +333,20 @@ public class PlotCommitList<L extends PlotLane> extends
 			// Positions may be blocked by a commit on a lane.
 			if (lane != null)
 				blockedPositions.set(lane.getPosition());
+			// Positions may also be blocked by forking off and merging lanes.
+			// We don't consider passing lanes, because every passing lane forks
+			// off and merges at it ends.
+			for (PlotLane l : rObj.forkingOffLanes)
+				blockedPositions.set(l.getPosition());
+			for (PlotLane l : rObj.mergingLanes)
+				blockedPositions.set(l.getPosition());
 		}
 	}
 
 	private void closeLane(PlotLane lane) {
 		if (activeLanes.remove(lane)) {
 			recycleLane((L) lane);
+			laneLength.remove(lane);
 			freePositions.add(Integer.valueOf(lane.getPosition()));
 		}
 	}
@@ -246,6 +365,7 @@ public class PlotCommitList<L extends PlotLane> extends
 		final PlotLane p = createLane();
 		p.position = getFreePosition(blockedPositions);
 		activeLanes.add(p);
+		laneLength.put(p, Integer.valueOf(1));
 		return p;
 	}