PlotCommitList.java

  1. /*
  2.  * Copyright (C) 2008, Shawn O. Pearce <spearce@spearce.org>,
  3.  * Copyright (C) 2010, Christian Halstrick <christian.halstrick@sap.com>
  4.  * Copyright (C) 2014, Konrad Kügler and others
  5.  *
  6.  * This program and the accompanying materials are made available under the
  7.  * terms of the Eclipse Distribution License v. 1.0 which is available at
  8.  * https://www.eclipse.org/org/documents/edl-v10.php.
  9.  *
  10.  * SPDX-License-Identifier: BSD-3-Clause
  11.  */

  12. package org.eclipse.jgit.revplot;

  13. import java.text.MessageFormat;
  14. import java.util.BitSet;
  15. import java.util.Collection;
  16. import java.util.HashMap;
  17. import java.util.HashSet;
  18. import java.util.TreeSet;

  19. import org.eclipse.jgit.internal.JGitText;
  20. import org.eclipse.jgit.revwalk.RevCommitList;
  21. import org.eclipse.jgit.revwalk.RevWalk;

  22. /**
  23.  * An ordered list of {@link org.eclipse.jgit.revplot.PlotCommit} subclasses.
  24.  * <p>
  25.  * Commits are allocated into lanes as they enter the list, based upon their
  26.  * connections between descendant (child) commits and ancestor (parent) commits.
  27.  * <p>
  28.  * The source of the list must be a {@link org.eclipse.jgit.revplot.PlotWalk}
  29.  * and {@link #fillTo(int)} must be used to populate the list.
  30.  *
  31.  * @param <L>
  32.  *            type of lane used by the application.
  33.  */
  34. public class PlotCommitList<L extends PlotLane> extends
  35.         RevCommitList<PlotCommit<L>> {
  36.     static final int MAX_LENGTH = 25;

  37.     private int positionsAllocated;

  38.     private final TreeSet<Integer> freePositions = new TreeSet<>();

  39.     private final HashSet<PlotLane> activeLanes = new HashSet<>(32);

  40.     /** number of (child) commits on a lane */
  41.     private final HashMap<PlotLane, Integer> laneLength = new HashMap<>(
  42.             32);

  43.     /** {@inheritDoc} */
  44.     @Override
  45.     public void clear() {
  46.         super.clear();
  47.         positionsAllocated = 0;
  48.         freePositions.clear();
  49.         activeLanes.clear();
  50.         laneLength.clear();
  51.     }

  52.     /** {@inheritDoc} */
  53.     @Override
  54.     public void source(RevWalk w) {
  55.         if (!(w instanceof PlotWalk))
  56.             throw new ClassCastException(MessageFormat.format(JGitText.get().classCastNotA, PlotWalk.class.getName()));
  57.         super.source(w);
  58.     }

  59.     /**
  60.      * Find the set of lanes passing through a commit's row.
  61.      * <p>
  62.      * Lanes passing through a commit are lanes that the commit is not directly
  63.      * on, but that need to travel through this commit to connect a descendant
  64.      * (child) commit to an ancestor (parent) commit. Typically these lanes will
  65.      * be drawn as lines in the passed commit's box, and the passed commit won't
  66.      * appear to be connected to those lines.
  67.      * <p>
  68.      * This method modifies the passed collection by adding the lanes in any
  69.      * order.
  70.      *
  71.      * @param currCommit
  72.      *            the commit the caller needs to get the lanes from.
  73.      * @param result
  74.      *            collection to add the passing lanes into.
  75.      */
  76.     @SuppressWarnings("unchecked")
  77.     public void findPassingThrough(final PlotCommit<L> currCommit,
  78.             final Collection<L> result) {
  79.         for (PlotLane p : currCommit.passingLanes)
  80.             result.add((L) p);
  81.     }

  82.     /** {@inheritDoc} */
  83.     @SuppressWarnings("ReferenceEquality")
  84.     @Override
  85.     protected void enter(int index, PlotCommit<L> currCommit) {
  86.         setupChildren(currCommit);

  87.         final int nChildren = currCommit.getChildCount();
  88.         if (nChildren == 0) {
  89.             currCommit.lane = nextFreeLane();
  90.         } else if (nChildren == 1
  91.                 && currCommit.children[0].getParentCount() < 2) {
  92.             // Only one child, child has only us as their parent.
  93.             // Stay in the same lane as the child.

  94.             @SuppressWarnings("unchecked")
  95.             final PlotCommit<L> c = currCommit.children[0];
  96.             currCommit.lane = c.lane;
  97.             Integer len = laneLength.get(currCommit.lane);
  98.             len = len != null ? Integer.valueOf(len.intValue() + 1)
  99.                     : Integer.valueOf(0);
  100.             laneLength.put(currCommit.lane, len);
  101.         } else {
  102.             // More than one child, or our child is a merge.

  103.             // We look for the child lane the current commit should continue.
  104.             // Candidate lanes for this are those with children, that have the
  105.             // current commit as their first parent.
  106.             // There can be multiple candidate lanes. In that case the longest
  107.             // lane is chosen, as this is usually the lane representing the
  108.             // branch the commit actually was made on.

  109.             // When there are no candidate lanes (i.e. the current commit has
  110.             // only children whose non-first parent it is) we place the current
  111.             // commit on a new lane.

  112.             // The lane the current commit will be placed on:
  113.             PlotLane reservedLane = null;
  114.             PlotCommit childOnReservedLane = null;
  115.             int lengthOfReservedLane = -1;

  116.             for (int i = 0; i < nChildren; i++) {
  117.                 @SuppressWarnings("unchecked")
  118.                 final PlotCommit<L> c = currCommit.children[i];
  119.                 if (c.getParent(0) == currCommit) {
  120.                     Integer len = laneLength.get(c.lane);
  121.                     // we may be the first parent for multiple lines of
  122.                     // development, try to continue the longest one
  123.                     if (len.intValue() > lengthOfReservedLane) {
  124.                         reservedLane = c.lane;
  125.                         childOnReservedLane = c;
  126.                         lengthOfReservedLane = len.intValue();
  127.                     }
  128.                 }
  129.             }

  130.             if (reservedLane != null) {
  131.                 currCommit.lane = reservedLane;
  132.                 laneLength.put(reservedLane,
  133.                         Integer.valueOf(lengthOfReservedLane + 1));
  134.                 handleBlockedLanes(index, currCommit, childOnReservedLane);
  135.             } else {
  136.                 currCommit.lane = nextFreeLane();
  137.                 handleBlockedLanes(index, currCommit, null);
  138.             }

  139.             // close lanes of children, if there are no first parents that might
  140.             // want to continue the child lanes
  141.             for (int i = 0; i < nChildren; i++) {
  142.                 final PlotCommit c = currCommit.children[i];
  143.                 PlotCommit firstParent = (PlotCommit) c.getParent(0);
  144.                 if (firstParent.lane != null && firstParent.lane != c.lane)
  145.                     closeLane(c.lane);
  146.             }
  147.         }

  148.         continueActiveLanes(currCommit);
  149.         if (currCommit.getParentCount() == 0)
  150.             closeLane(currCommit.lane);
  151.     }

  152.     private void continueActiveLanes(PlotCommit currCommit) {
  153.         for (PlotLane lane : activeLanes)
  154.             if (lane != currCommit.lane)
  155.                 currCommit.addPassingLane(lane);
  156.     }

  157.     /**
  158.      * Sets up fork and merge information in the involved PlotCommits.
  159.      * Recognizes and handles blockades that involve forking or merging arcs.
  160.      *
  161.      * @param index
  162.      *            the index of <code>currCommit</code> in the list
  163.      * @param currCommit
  164.      * @param childOnLane
  165.      *            the direct child on the same lane as <code>currCommit</code>,
  166.      *            may be null if <code>currCommit</code> is the first commit on
  167.      *            the lane
  168.      */
  169.     @SuppressWarnings("ReferenceEquality")
  170.     private void handleBlockedLanes(final int index, final PlotCommit currCommit,
  171.             final PlotCommit childOnLane) {
  172.         for (PlotCommit child : currCommit.children) {
  173.             if (child == childOnLane)
  174.                 continue; // simple continuations of lanes are handled by
  175.                             // continueActiveLanes() calls in enter()

  176.             // Is the child a merge or is it forking off?
  177.             boolean childIsMerge = child.getParent(0) != currCommit;
  178.             if (childIsMerge) {
  179.                 PlotLane laneToUse = currCommit.lane;
  180.                 laneToUse = handleMerge(index, currCommit, childOnLane, child,
  181.                         laneToUse);
  182.                 child.addMergingLane(laneToUse);
  183.             } else {
  184.                 // We want to draw a forking arc in the child's lane.
  185.                 // As an active lane, the child lane already continues
  186.                 // (unblocked) up to this commit, we only need to mark it as
  187.                 // forking off from the current commit.
  188.                 PlotLane laneToUse = child.lane;
  189.                 currCommit.addForkingOffLane(laneToUse);
  190.             }
  191.         }
  192.     }

  193.     // Handles the case where currCommit is a non-first parent of the child
  194.     @SuppressWarnings("ReferenceEquality")
  195.     private PlotLane handleMerge(final int index, final PlotCommit currCommit,
  196.             final PlotCommit childOnLane, PlotCommit child, PlotLane laneToUse) {

  197.         // find all blocked positions between currCommit and this child

  198.         int childIndex = index; // useless initialization, should
  199.                                 // always be set in the loop below
  200.         BitSet blockedPositions = new BitSet();
  201.         for (int r = index - 1; r >= 0; r--) {
  202.             final PlotCommit rObj = get(r);
  203.             if (rObj == child) {
  204.                 childIndex = r;
  205.                 break;
  206.             }
  207.             addBlockedPosition(blockedPositions, rObj);
  208.         }

  209.         // handle blockades

  210.         if (blockedPositions.get(laneToUse.getPosition())) {
  211.             // We want to draw a merging arc in our lane to the child,
  212.             // which is on another lane, but our lane is blocked.

  213.             // Check if childOnLane is beetween commit and the child we
  214.             // are currently processing
  215.             boolean needDetour = false;
  216.             if (childOnLane != null) {
  217.                 for (int r = index - 1; r > childIndex; r--) {
  218.                     final PlotCommit rObj = get(r);
  219.                     if (rObj == childOnLane) {
  220.                         needDetour = true;
  221.                         break;
  222.                     }
  223.                 }
  224.             }

  225.             if (needDetour) {
  226.                 // It is childOnLane which is blocking us. Repositioning
  227.                 // our lane would not help, because this repositions the
  228.                 // child too, keeping the blockade.
  229.                 // Instead, we create a "detour lane" which gets us
  230.                 // around the blockade. That lane has no commits on it.
  231.                 laneToUse = nextFreeLane(blockedPositions);
  232.                 currCommit.addForkingOffLane(laneToUse);
  233.                 closeLane(laneToUse);
  234.             } else {
  235.                 // The blockade is (only) due to other (already closed)
  236.                 // lanes at the current lane's position. In this case we
  237.                 // reposition the current lane.
  238.                 // We are the first commit on this lane, because
  239.                 // otherwise the child commit on this lane would have
  240.                 // kept other lanes from blocking us. Since we are the
  241.                 // first commit, we can freely reposition.
  242.                 int newPos = getFreePosition(blockedPositions);
  243.                 freePositions.add(Integer.valueOf(laneToUse
  244.                         .getPosition()));
  245.                 laneToUse.position = newPos;
  246.             }
  247.         }

  248.         // Actually connect currCommit to the merge child
  249.         drawLaneToChild(index, child, laneToUse);
  250.         return laneToUse;
  251.     }

  252.     /**
  253.      * Connects the commit at commitIndex to the child, using the given lane.
  254.      * All blockades on the lane must be resolved before calling this method.
  255.      *
  256.      * @param commitIndex
  257.      * @param child
  258.      * @param laneToContinue
  259.      */
  260.     @SuppressWarnings("ReferenceEquality")
  261.     private void drawLaneToChild(final int commitIndex, PlotCommit child,
  262.             PlotLane laneToContinue) {
  263.         for (int r = commitIndex - 1; r >= 0; r--) {
  264.             final PlotCommit rObj = get(r);
  265.             if (rObj == child)
  266.                 break;
  267.             if (rObj != null)
  268.                 rObj.addPassingLane(laneToContinue);
  269.         }
  270.     }

  271.     private static void addBlockedPosition(BitSet blockedPositions,
  272.             final PlotCommit rObj) {
  273.         if (rObj != null) {
  274.             PlotLane lane = rObj.getLane();
  275.             // Positions may be blocked by a commit on a lane.
  276.             if (lane != null)
  277.                 blockedPositions.set(lane.getPosition());
  278.             // Positions may also be blocked by forking off and merging lanes.
  279.             // We don't consider passing lanes, because every passing lane forks
  280.             // off and merges at it ends.
  281.             for (PlotLane l : rObj.forkingOffLanes)
  282.                 blockedPositions.set(l.getPosition());
  283.             for (PlotLane l : rObj.mergingLanes)
  284.                 blockedPositions.set(l.getPosition());
  285.         }
  286.     }

  287.     @SuppressWarnings("unchecked")
  288.     private void closeLane(PlotLane lane) {
  289.         if (activeLanes.remove(lane)) {
  290.             recycleLane((L) lane);
  291.             laneLength.remove(lane);
  292.             freePositions.add(Integer.valueOf(lane.getPosition()));
  293.         }
  294.     }

  295.     private void setupChildren(PlotCommit<L> currCommit) {
  296.         final int nParents = currCommit.getParentCount();
  297.         for (int i = 0; i < nParents; i++)
  298.             ((PlotCommit) currCommit.getParent(i)).addChild(currCommit);
  299.     }

  300.     private PlotLane nextFreeLane() {
  301.         return nextFreeLane(null);
  302.     }

  303.     private PlotLane nextFreeLane(BitSet blockedPositions) {
  304.         final PlotLane p = createLane();
  305.         p.position = getFreePosition(blockedPositions);
  306.         activeLanes.add(p);
  307.         laneLength.put(p, Integer.valueOf(1));
  308.         return p;
  309.     }

  310.     /**
  311.      * @param blockedPositions
  312.      *            may be null
  313.      * @return a free lane position
  314.      */
  315.     private int getFreePosition(BitSet blockedPositions) {
  316.         if (freePositions.isEmpty())
  317.             return positionsAllocated++;

  318.         if (blockedPositions != null) {
  319.             for (Integer pos : freePositions)
  320.                 if (!blockedPositions.get(pos.intValue())) {
  321.                     freePositions.remove(pos);
  322.                     return pos.intValue();
  323.                 }
  324.             return positionsAllocated++;
  325.         }
  326.         final Integer min = freePositions.first();
  327.         freePositions.remove(min);
  328.         return min.intValue();
  329.     }

  330.     /**
  331.      * Create a new {@link PlotLane} appropriate for this particular
  332.      * {@link PlotCommitList}.
  333.      *
  334.      * @return a new {@link PlotLane} appropriate for this particular
  335.      *         {@link PlotCommitList}.
  336.      */
  337.     @SuppressWarnings("unchecked")
  338.     protected L createLane() {
  339.         return (L) new PlotLane();
  340.     }

  341.     /**
  342.      * Return colors and other reusable information to the plotter when a lane
  343.      * is no longer needed.
  344.      *
  345.      * @param lane
  346.      *            a lane
  347.      */
  348.     protected void recycleLane(L lane) {
  349.         // Nothing.
  350.     }
  351. }