| /* |
| * 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 others |
| * |
| * This program and the accompanying materials are made available under the |
| * terms of the Eclipse Distribution License v. 1.0 which is available at |
| * https://www.eclipse.org/org/documents/edl-v10.php. |
| * |
| * SPDX-License-Identifier: BSD-3-Clause |
| */ |
| |
| 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; |
| |
| import org.eclipse.jgit.internal.JGitText; |
| import org.eclipse.jgit.revwalk.RevCommitList; |
| import org.eclipse.jgit.revwalk.RevWalk; |
| |
| /** |
| * An ordered list of {@link org.eclipse.jgit.revplot.PlotCommit} subclasses. |
| * <p> |
| * Commits are allocated into lanes as they enter the list, based upon their |
| * connections between descendant (child) commits and ancestor (parent) commits. |
| * <p> |
| * The source of the list must be a {@link org.eclipse.jgit.revplot.PlotWalk} |
| * and {@link #fillTo(int)} must be used to populate the list. |
| * |
| * @param <L> |
| * type of lane used by the application. |
| */ |
| public class PlotCommitList<L extends PlotLane> extends |
| RevCommitList<PlotCommit<L>> { |
| static final int MAX_LENGTH = 25; |
| |
| private int positionsAllocated; |
| |
| private final TreeSet<Integer> freePositions = new TreeSet<>(); |
| |
| private final HashSet<PlotLane> activeLanes = new HashSet<>(32); |
| |
| /** number of (child) commits on a lane */ |
| private final HashMap<PlotLane, Integer> laneLength = new HashMap<>( |
| 32); |
| |
| /** {@inheritDoc} */ |
| @Override |
| public void clear() { |
| super.clear(); |
| positionsAllocated = 0; |
| freePositions.clear(); |
| activeLanes.clear(); |
| laneLength.clear(); |
| } |
| |
| /** {@inheritDoc} */ |
| @Override |
| public void source(RevWalk w) { |
| if (!(w instanceof PlotWalk)) |
| throw new ClassCastException(MessageFormat.format(JGitText.get().classCastNotA, PlotWalk.class.getName())); |
| super.source(w); |
| } |
| |
| /** |
| * Find the set of lanes passing through a commit's row. |
| * <p> |
| * Lanes passing through a commit are lanes that the commit is not directly |
| * on, but that need to travel through this commit to connect a descendant |
| * (child) commit to an ancestor (parent) commit. Typically these lanes will |
| * be drawn as lines in the passed commit's box, and the passed commit won't |
| * appear to be connected to those lines. |
| * <p> |
| * This method modifies the passed collection by adding the lanes in any |
| * order. |
| * |
| * @param currCommit |
| * the commit the caller needs to get the lanes from. |
| * @param result |
| * collection to add the passing lanes into. |
| */ |
| @SuppressWarnings("unchecked") |
| public void findPassingThrough(final PlotCommit<L> currCommit, |
| final Collection<L> result) { |
| for (PlotLane p : currCommit.passingLanes) |
| result.add((L) p); |
| } |
| |
| /** {@inheritDoc} */ |
| @Override |
| protected void enter(int index, PlotCommit<L> currCommit) { |
| setupChildren(currCommit); |
| |
| final int nChildren = currCommit.getChildCount(); |
| if (nChildren == 0) { |
| currCommit.lane = nextFreeLane(); |
| } else 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. |
| |
| @SuppressWarnings("unchecked") |
| final PlotCommit<L> c = currCommit.children[0]; |
| currCommit.lane = c.lane; |
| Integer len = laneLength.get(currCommit.lane); |
| len = len != null ? Integer.valueOf(len.intValue() + 1) |
| : Integer.valueOf(0); |
| laneLength.put(currCommit.lane, len); |
| } else { |
| // More than one child, or our child is a merge. |
| |
| // 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++) { |
| @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(); |
| } |
| } |
| } |
| |
| 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); |
| } |
| |
| // 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); |
| if (currCommit.getParentCount() == 0) |
| closeLane(currCommit.lane); |
| } |
| |
| private void continueActiveLanes(PlotCommit currCommit) { |
| for (PlotLane lane : activeLanes) |
| if (lane != currCommit.lane) |
| currCommit.addPassingLane(lane); |
| } |
| |
| /** |
| * Sets up fork and merge information in the involved PlotCommits. |
| * Recognizes and handles blockades that involve forking or merging arcs. |
| * |
| * @param index |
| * 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 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 (rObj == child) { |
| childIndex = r; |
| break; |
| } |
| addBlockedPosition(blockedPositions, rObj); |
| } |
| |
| // 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; |
| } |
| } |
| |
| // 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); |
| } |
| } |
| |
| private static void addBlockedPosition(BitSet blockedPositions, |
| final PlotCommit rObj) { |
| if (rObj != null) { |
| PlotLane lane = rObj.getLane(); |
| // 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()); |
| } |
| } |
| |
| @SuppressWarnings("unchecked") |
| private void closeLane(PlotLane lane) { |
| if (activeLanes.remove(lane)) { |
| recycleLane((L) lane); |
| laneLength.remove(lane); |
| freePositions.add(Integer.valueOf(lane.getPosition())); |
| } |
| } |
| |
| private void setupChildren(PlotCommit<L> currCommit) { |
| final int nParents = currCommit.getParentCount(); |
| for (int i = 0; i < nParents; i++) |
| ((PlotCommit) currCommit.getParent(i)).addChild(currCommit); |
| } |
| |
| private PlotLane nextFreeLane() { |
| return nextFreeLane(null); |
| } |
| |
| private PlotLane nextFreeLane(BitSet blockedPositions) { |
| final PlotLane p = createLane(); |
| p.position = getFreePosition(blockedPositions); |
| activeLanes.add(p); |
| laneLength.put(p, Integer.valueOf(1)); |
| return p; |
| } |
| |
| /** |
| * @param blockedPositions |
| * may be null |
| * @return a free lane position |
| */ |
| private int getFreePosition(BitSet blockedPositions) { |
| if (freePositions.isEmpty()) |
| return positionsAllocated++; |
| |
| if (blockedPositions != null) { |
| for (Integer pos : freePositions) |
| if (!blockedPositions.get(pos.intValue())) { |
| freePositions.remove(pos); |
| return pos.intValue(); |
| } |
| return positionsAllocated++; |
| } |
| final Integer min = freePositions.first(); |
| freePositions.remove(min); |
| return min.intValue(); |
| } |
| |
| /** |
| * Create a new {@link PlotLane} appropriate for this particular |
| * {@link PlotCommitList}. |
| * |
| * @return a new {@link PlotLane} appropriate for this particular |
| * {@link PlotCommitList}. |
| */ |
| @SuppressWarnings("unchecked") |
| protected L createLane() { |
| return (L) new PlotLane(); |
| } |
| |
| /** |
| * Return colors and other reusable information to the plotter when a lane |
| * is no longer needed. |
| * |
| * @param lane |
| * a lane |
| */ |
| protected void recycleLane(L lane) { |
| // Nothing. |
| } |
| } |