RevWalk.java

  1. /*
  2.  * Copyright (C) 2007, Robin Rosenberg <robin.rosenberg@dewire.com>
  3.  * Copyright (C) 2008, Shawn O. Pearce <spearce@spearce.org>
  4.  * Copyright (C) 2014, Gustaf Lundh <gustaf.lundh@sonymobile.com> 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.revwalk;

  13. import java.io.IOException;
  14. import java.text.MessageFormat;
  15. import java.util.ArrayList;
  16. import java.util.Collection;
  17. import java.util.EnumSet;
  18. import java.util.Iterator;
  19. import java.util.List;

  20. import org.eclipse.jgit.annotations.NonNull;
  21. import org.eclipse.jgit.annotations.Nullable;
  22. import org.eclipse.jgit.errors.CorruptObjectException;
  23. import org.eclipse.jgit.errors.IncorrectObjectTypeException;
  24. import org.eclipse.jgit.errors.LargeObjectException;
  25. import org.eclipse.jgit.errors.MissingObjectException;
  26. import org.eclipse.jgit.errors.RevWalkException;
  27. import org.eclipse.jgit.internal.JGitText;
  28. import org.eclipse.jgit.lib.AnyObjectId;
  29. import org.eclipse.jgit.lib.AsyncObjectLoaderQueue;
  30. import org.eclipse.jgit.lib.Constants;
  31. import org.eclipse.jgit.lib.MutableObjectId;
  32. import org.eclipse.jgit.lib.NullProgressMonitor;
  33. import org.eclipse.jgit.lib.ObjectId;
  34. import org.eclipse.jgit.lib.ObjectIdOwnerMap;
  35. import org.eclipse.jgit.lib.ObjectLoader;
  36. import org.eclipse.jgit.lib.ObjectReader;
  37. import org.eclipse.jgit.lib.ProgressMonitor;
  38. import org.eclipse.jgit.lib.Ref;
  39. import org.eclipse.jgit.lib.Repository;
  40. import org.eclipse.jgit.revwalk.filter.RevFilter;
  41. import org.eclipse.jgit.treewalk.filter.TreeFilter;
  42. import org.eclipse.jgit.util.References;

  43. /**
  44.  * Walks a commit graph and produces the matching commits in order.
  45.  * <p>
  46.  * A RevWalk instance can only be used once to generate results. Running a
  47.  * second time requires creating a new RevWalk instance, or invoking
  48.  * {@link #reset()} before starting again. Resetting an existing instance may be
  49.  * faster for some applications as commit body parsing can be avoided on the
  50.  * later invocations.
  51.  * <p>
  52.  * RevWalk instances are not thread-safe. Applications must either restrict
  53.  * usage of a RevWalk instance to a single thread, or implement their own
  54.  * synchronization at a higher level.
  55.  * <p>
  56.  * Multiple simultaneous RevWalk instances per
  57.  * {@link org.eclipse.jgit.lib.Repository} are permitted, even from concurrent
  58.  * threads. Equality of {@link org.eclipse.jgit.revwalk.RevCommit}s from two
  59.  * different RevWalk instances is never true, even if their
  60.  * {@link org.eclipse.jgit.lib.ObjectId}s are equal (and thus they describe the
  61.  * same commit).
  62.  * <p>
  63.  * The offered iterator is over the list of RevCommits described by the
  64.  * configuration of this instance. Applications should restrict themselves to
  65.  * using either the provided Iterator or {@link #next()}, but never use both on
  66.  * the same RevWalk at the same time. The Iterator may buffer RevCommits, while
  67.  * {@link #next()} does not.
  68.  */
  69. public class RevWalk implements Iterable<RevCommit>, AutoCloseable {
  70.     private static final int MB = 1 << 20;

  71.     /**
  72.      * Set on objects whose important header data has been loaded.
  73.      * <p>
  74.      * For a RevCommit this indicates we have pulled apart the tree and parent
  75.      * references from the raw bytes available in the repository and translated
  76.      * those to our own local RevTree and RevCommit instances. The raw buffer is
  77.      * also available for message and other header filtering.
  78.      * <p>
  79.      * For a RevTag this indicates we have pulled part the tag references to
  80.      * find out who the tag refers to, and what that object's type is.
  81.      */
  82.     static final int PARSED = 1 << 0;

  83.     /**
  84.      * Set on RevCommit instances added to our {@link #pending} queue.
  85.      * <p>
  86.      * We use this flag to avoid adding the same commit instance twice to our
  87.      * queue, especially if we reached it by more than one path.
  88.      */
  89.     static final int SEEN = 1 << 1;

  90.     /**
  91.      * Set on RevCommit instances the caller does not want output.
  92.      * <p>
  93.      * We flag commits as uninteresting if the caller does not want commits
  94.      * reachable from a commit given to {@link #markUninteresting(RevCommit)}.
  95.      * This flag is always carried into the commit's parents and is a key part
  96.      * of the "rev-list B --not A" feature; A is marked UNINTERESTING.
  97.      */
  98.     static final int UNINTERESTING = 1 << 2;

  99.     /**
  100.      * Set on a RevCommit that can collapse out of the history.
  101.      * <p>
  102.      * If the {@link #treeFilter} concluded that this commit matches his
  103.      * parents' for all of the paths that the filter is interested in then we
  104.      * mark the commit REWRITE. Later we can rewrite the parents of a REWRITE
  105.      * child to remove chains of REWRITE commits before we produce the child to
  106.      * the application.
  107.      *
  108.      * @see RewriteGenerator
  109.      */
  110.     static final int REWRITE = 1 << 3;

  111.     /**
  112.      * Temporary mark for use within generators or filters.
  113.      * <p>
  114.      * This mark is only for local use within a single scope. If someone sets
  115.      * the mark they must unset it before any other code can see the mark.
  116.      */
  117.     static final int TEMP_MARK = 1 << 4;

  118.     /**
  119.      * Temporary mark for use within {@link TopoSortGenerator}.
  120.      * <p>
  121.      * This mark indicates the commit could not produce when it wanted to, as at
  122.      * least one child was behind it. Commits with this flag are delayed until
  123.      * all children have been output first.
  124.      */
  125.     static final int TOPO_DELAY = 1 << 5;

  126.     /**
  127.      * Temporary mark for use within {@link TopoNonIntermixSortGenerator}.
  128.      * <p>
  129.      * This mark indicates the commit has been queued for emission in
  130.      * {@link TopoSortGenerator} and can be produced. This mark is removed when
  131.      * the commit has been produced.
  132.      */
  133.     static final int TOPO_QUEUED = 1 << 6;

  134.     /**
  135.      * Set on a RevCommit when a {@link TreeRevFilter} has been applied.
  136.      * <p>
  137.      * This flag is processed by the {@link RewriteGenerator} to check if a
  138.      * {@link TreeRevFilter} has been applied.
  139.      *
  140.      * @see TreeRevFilter
  141.      * @see RewriteGenerator
  142.      */
  143.     static final int TREE_REV_FILTER_APPLIED = 1 << 7;

  144.     /**
  145.      * Number of flag bits we keep internal for our own use. See above flags.
  146.      */
  147.     static final int RESERVED_FLAGS = 8;

  148.     private static final int APP_FLAGS = -1 & ~((1 << RESERVED_FLAGS) - 1);

  149.     final ObjectReader reader;

  150.     private final boolean closeReader;

  151.     final MutableObjectId idBuffer;

  152.     ObjectIdOwnerMap<RevObject> objects;

  153.     int freeFlags = APP_FLAGS;

  154.     private int delayFreeFlags;

  155.     private int retainOnReset;

  156.     int carryFlags = UNINTERESTING;

  157.     final ArrayList<RevCommit> roots;

  158.     AbstractRevQueue queue;

  159.     Generator pending;

  160.     private final EnumSet<RevSort> sorting;

  161.     private RevFilter filter;

  162.     private TreeFilter treeFilter;

  163.     private boolean retainBody = true;

  164.     private boolean rewriteParents = true;

  165.     private boolean firstParent;

  166.     boolean shallowCommitsInitialized;

  167.     private enum GetMergedIntoStrategy {
  168.         RETURN_ON_FIRST_FOUND, RETURN_ON_FIRST_NOT_FOUND, EVALUATE_ALL
  169.     }

  170.     /**
  171.      * Create a new revision walker for a given repository.
  172.      *
  173.      * @param repo
  174.      *            the repository the walker will obtain data from. An
  175.      *            ObjectReader will be created by the walker, and will be closed
  176.      *            when the walker is closed.
  177.      */
  178.     public RevWalk(Repository repo) {
  179.         this(repo.newObjectReader(), true);
  180.     }

  181.     /**
  182.      * Create a new revision walker for a given repository.
  183.      * <p>
  184.      *
  185.      * @param or
  186.      *            the reader the walker will obtain data from. The reader is not
  187.      *            closed when the walker is closed (but is closed by
  188.      *            {@link #dispose()}.
  189.      */
  190.     public RevWalk(ObjectReader or) {
  191.         this(or, false);
  192.     }

  193.     RevWalk(ObjectReader or, boolean closeReader) {
  194.         reader = or;
  195.         idBuffer = new MutableObjectId();
  196.         objects = new ObjectIdOwnerMap<>();
  197.         roots = new ArrayList<>();
  198.         queue = new DateRevQueue(false);
  199.         pending = new StartGenerator(this);
  200.         sorting = EnumSet.of(RevSort.NONE);
  201.         filter = RevFilter.ALL;
  202.         treeFilter = TreeFilter.ALL;
  203.         this.closeReader = closeReader;
  204.     }

  205.     /**
  206.      * Get the reader this walker is using to load objects.
  207.      *
  208.      * @return the reader this walker is using to load objects.
  209.      */
  210.     public ObjectReader getObjectReader() {
  211.         return reader;
  212.     }

  213.     /**
  214.      * Get a reachability checker for commits over this revwalk.
  215.      *
  216.      * @return the most efficient reachability checker for this repository.
  217.      * @throws IOException
  218.      *             if it cannot open any of the underlying indices.
  219.      *
  220.      * @since 5.4
  221.      * @deprecated use {@code ObjectReader#createReachabilityChecker(RevWalk)}
  222.      *             instead.
  223.      */
  224.     @Deprecated
  225.     public final ReachabilityChecker createReachabilityChecker()
  226.             throws IOException {
  227.         return reader.createReachabilityChecker(this);
  228.     }

  229.     /**
  230.      * {@inheritDoc}
  231.      * <p>
  232.      * Release any resources used by this walker's reader.
  233.      * <p>
  234.      * A walker that has been released can be used again, but may need to be
  235.      * released after the subsequent usage.
  236.      *
  237.      * @since 4.0
  238.      */
  239.     @Override
  240.     public void close() {
  241.         if (closeReader) {
  242.             reader.close();
  243.         }
  244.     }

  245.     /**
  246.      * Mark a commit to start graph traversal from.
  247.      * <p>
  248.      * Callers are encouraged to use {@link #parseCommit(AnyObjectId)} to obtain
  249.      * the commit reference, rather than {@link #lookupCommit(AnyObjectId)}, as
  250.      * this method requires the commit to be parsed before it can be added as a
  251.      * root for the traversal.
  252.      * <p>
  253.      * The method will automatically parse an unparsed commit, but error
  254.      * handling may be more difficult for the application to explain why a
  255.      * RevCommit is not actually a commit. The object pool of this walker would
  256.      * also be 'poisoned' by the non-commit RevCommit.
  257.      *
  258.      * @param c
  259.      *            the commit to start traversing from. The commit passed must be
  260.      *            from this same revision walker.
  261.      * @throws org.eclipse.jgit.errors.MissingObjectException
  262.      *             the commit supplied is not available from the object
  263.      *             database. This usually indicates the supplied commit is
  264.      *             invalid, but the reference was constructed during an earlier
  265.      *             invocation to {@link #lookupCommit(AnyObjectId)}.
  266.      * @throws org.eclipse.jgit.errors.IncorrectObjectTypeException
  267.      *             the object was not parsed yet and it was discovered during
  268.      *             parsing that it is not actually a commit. This usually
  269.      *             indicates the caller supplied a non-commit SHA-1 to
  270.      *             {@link #lookupCommit(AnyObjectId)}.
  271.      * @throws java.io.IOException
  272.      *             a pack file or loose object could not be read.
  273.      */
  274.     public void markStart(RevCommit c) throws MissingObjectException,
  275.             IncorrectObjectTypeException, IOException {
  276.         if ((c.flags & SEEN) != 0)
  277.             return;
  278.         if ((c.flags & PARSED) == 0)
  279.             c.parseHeaders(this);
  280.         c.flags |= SEEN;
  281.         roots.add(c);
  282.         queue.add(c);
  283.     }

  284.     /**
  285.      * Mark commits to start graph traversal from.
  286.      *
  287.      * @param list
  288.      *            commits to start traversing from. The commits passed must be
  289.      *            from this same revision walker.
  290.      * @throws org.eclipse.jgit.errors.MissingObjectException
  291.      *             one of the commits supplied is not available from the object
  292.      *             database. This usually indicates the supplied commit is
  293.      *             invalid, but the reference was constructed during an earlier
  294.      *             invocation to {@link #lookupCommit(AnyObjectId)}.
  295.      * @throws org.eclipse.jgit.errors.IncorrectObjectTypeException
  296.      *             the object was not parsed yet and it was discovered during
  297.      *             parsing that it is not actually a commit. This usually
  298.      *             indicates the caller supplied a non-commit SHA-1 to
  299.      *             {@link #lookupCommit(AnyObjectId)}.
  300.      * @throws java.io.IOException
  301.      *             a pack file or loose object could not be read.
  302.      */
  303.     public void markStart(Collection<RevCommit> list)
  304.             throws MissingObjectException, IncorrectObjectTypeException,
  305.             IOException {
  306.         for (RevCommit c : list)
  307.             markStart(c);
  308.     }

  309.     /**
  310.      * Mark a commit to not produce in the output.
  311.      * <p>
  312.      * Uninteresting commits denote not just themselves but also their entire
  313.      * ancestry chain, back until the merge base of an uninteresting commit and
  314.      * an otherwise interesting commit.
  315.      * <p>
  316.      * Callers are encouraged to use {@link #parseCommit(AnyObjectId)} to obtain
  317.      * the commit reference, rather than {@link #lookupCommit(AnyObjectId)}, as
  318.      * this method requires the commit to be parsed before it can be added as a
  319.      * root for the traversal.
  320.      * <p>
  321.      * The method will automatically parse an unparsed commit, but error
  322.      * handling may be more difficult for the application to explain why a
  323.      * RevCommit is not actually a commit. The object pool of this walker would
  324.      * also be 'poisoned' by the non-commit RevCommit.
  325.      *
  326.      * @param c
  327.      *            the commit to start traversing from. The commit passed must be
  328.      *            from this same revision walker.
  329.      * @throws org.eclipse.jgit.errors.MissingObjectException
  330.      *             the commit supplied is not available from the object
  331.      *             database. This usually indicates the supplied commit is
  332.      *             invalid, but the reference was constructed during an earlier
  333.      *             invocation to {@link #lookupCommit(AnyObjectId)}.
  334.      * @throws org.eclipse.jgit.errors.IncorrectObjectTypeException
  335.      *             the object was not parsed yet and it was discovered during
  336.      *             parsing that it is not actually a commit. This usually
  337.      *             indicates the caller supplied a non-commit SHA-1 to
  338.      *             {@link #lookupCommit(AnyObjectId)}.
  339.      * @throws java.io.IOException
  340.      *             a pack file or loose object could not be read.
  341.      */
  342.     public void markUninteresting(RevCommit c) throws MissingObjectException,
  343.             IncorrectObjectTypeException, IOException {
  344.         c.flags |= UNINTERESTING;
  345.         carryFlagsImpl(c);
  346.         markStart(c);
  347.     }

  348.     /**
  349.      * Determine if a commit is reachable from another commit.
  350.      * <p>
  351.      * A commit <code>base</code> is an ancestor of <code>tip</code> if we can
  352.      * find a path of commits that leads from <code>tip</code> and ends at
  353.      * <code>base</code>.
  354.      * <p>
  355.      * This utility function resets the walker, inserts the two supplied
  356.      * commits, and then executes a walk until an answer can be obtained.
  357.      * Currently allocated RevFlags that have been added to RevCommit instances
  358.      * will be retained through the reset.
  359.      *
  360.      * @param base
  361.      *            commit the caller thinks is reachable from <code>tip</code>.
  362.      * @param tip
  363.      *            commit to start iteration from, and which is most likely a
  364.      *            descendant (child) of <code>base</code>.
  365.      * @return true if there is a path directly from <code>tip</code> to
  366.      *         <code>base</code> (and thus <code>base</code> is fully merged
  367.      *         into <code>tip</code>); false otherwise.
  368.      * @throws org.eclipse.jgit.errors.MissingObjectException
  369.      *             one or more of the next commit's parents are not available
  370.      *             from the object database, but were thought to be candidates
  371.      *             for traversal. This usually indicates a broken link.
  372.      * @throws org.eclipse.jgit.errors.IncorrectObjectTypeException
  373.      *             one or more of the next commit's parents are not actually
  374.      *             commit objects.
  375.      * @throws java.io.IOException
  376.      *             a pack file or loose object could not be read.
  377.      */
  378.     public boolean isMergedInto(RevCommit base, RevCommit tip)
  379.             throws MissingObjectException, IncorrectObjectTypeException,
  380.             IOException {
  381.         final RevFilter oldRF = filter;
  382.         final TreeFilter oldTF = treeFilter;
  383.         try {
  384.             finishDelayedFreeFlags();
  385.             reset(~freeFlags & APP_FLAGS);
  386.             filter = RevFilter.MERGE_BASE;
  387.             treeFilter = TreeFilter.ALL;
  388.             markStart(tip);
  389.             markStart(base);
  390.             RevCommit mergeBase;
  391.             while ((mergeBase = next()) != null) {
  392.                 if (References.isSameObject(mergeBase, base)) {
  393.                     return true;
  394.                 }
  395.             }
  396.             return false;
  397.         } finally {
  398.             filter = oldRF;
  399.             treeFilter = oldTF;
  400.         }
  401.     }

  402.     /**
  403.      * Determine the Refs into which a commit is merged.
  404.      * <p>
  405.      * A commit is merged into a ref if we can find a path of commits that leads
  406.      * from that specific ref and ends at <code>commit</code>.
  407.      * <p>
  408.      *
  409.      * @param commit
  410.      *            commit the caller thinks is reachable from <code>refs</code>.
  411.      * @param refs
  412.      *            refs to start iteration from, and which is most likely a
  413.      *            descendant (child) of <code>commit</code>.
  414.      * @return list of refs that are reachable from <code>commit</code>.
  415.      * @throws java.io.IOException
  416.      *             a pack file or loose object could not be read.
  417.      * @since 5.12
  418.      */
  419.     public List<Ref> getMergedInto(RevCommit commit, Collection<Ref> refs)
  420.             throws IOException {
  421.         return getMergedInto(commit, refs, NullProgressMonitor.INSTANCE);
  422.     }

  423.     /**
  424.      * Determine the Refs into which a commit is merged.
  425.      * <p>
  426.      * A commit is merged into a ref if we can find a path of commits that leads
  427.      * from that specific ref and ends at <code>commit</code>.
  428.      * <p>
  429.      *
  430.      * @param commit
  431.      *            commit the caller thinks is reachable from <code>refs</code>.
  432.      * @param refs
  433.      *            refs to start iteration from, and which is most likely a
  434.      *            descendant (child) of <code>commit</code>.
  435.      * @param monitor
  436.      *            the callback for progress and cancellation
  437.      * @return list of refs that are reachable from <code>commit</code>.
  438.      * @throws java.io.IOException
  439.      *             a pack file or loose object could not be read.
  440.      * @since 5.12
  441.      */
  442.     public List<Ref> getMergedInto(RevCommit commit, Collection<Ref> refs,
  443.             ProgressMonitor monitor) throws IOException {
  444.         return getMergedInto(commit, refs, GetMergedIntoStrategy.EVALUATE_ALL,
  445.                 monitor);
  446.     }

  447.     /**
  448.      * Determine if a <code>commit</code> is merged into any of the given
  449.      * <code>refs</code>.
  450.      *
  451.      * @param commit
  452.      *            commit the caller thinks is reachable from <code>refs</code>.
  453.      * @param refs
  454.      *            refs to start iteration from, and which is most likely a
  455.      *            descendant (child) of <code>commit</code>.
  456.      * @return true if commit is merged into any of the refs; false otherwise.
  457.      * @throws java.io.IOException
  458.      *             a pack file or loose object could not be read.
  459.      * @since 5.12
  460.      */
  461.     public boolean isMergedIntoAny(RevCommit commit, Collection<Ref> refs)
  462.             throws IOException {
  463.         return getMergedInto(commit, refs,
  464.                 GetMergedIntoStrategy.RETURN_ON_FIRST_FOUND,
  465.                 NullProgressMonitor.INSTANCE).size() > 0;
  466.     }

  467.     /**
  468.      * Determine if a <code>commit</code> is merged into all of the given
  469.      * <code>refs</code>.
  470.      *
  471.      * @param commit
  472.      *            commit the caller thinks is reachable from <code>refs</code>.
  473.      * @param refs
  474.      *            refs to start iteration from, and which is most likely a
  475.      *            descendant (child) of <code>commit</code>.
  476.      * @return true if commit is merged into all of the refs; false otherwise.
  477.      * @throws java.io.IOException
  478.      *             a pack file or loose object could not be read.
  479.      * @since 5.12
  480.      */
  481.     public boolean isMergedIntoAll(RevCommit commit, Collection<Ref> refs)
  482.             throws IOException {
  483.         return getMergedInto(commit, refs,
  484.                 GetMergedIntoStrategy.RETURN_ON_FIRST_NOT_FOUND,
  485.                 NullProgressMonitor.INSTANCE).size() == refs.size();
  486.     }

  487.     private List<Ref> getMergedInto(RevCommit needle, Collection<Ref> haystacks,
  488.             Enum returnStrategy, ProgressMonitor monitor) throws IOException {
  489.         List<Ref> result = new ArrayList<>();
  490.         List<RevCommit> uninteresting = new ArrayList<>();
  491.         List<RevCommit> marked = new ArrayList<>();
  492.         RevFilter oldRF = filter;
  493.         TreeFilter oldTF = treeFilter;
  494.         try {
  495.             finishDelayedFreeFlags();
  496.             reset(~freeFlags & APP_FLAGS);
  497.             filter = RevFilter.ALL;
  498.             treeFilter = TreeFilter.ALL;
  499.             for (Ref r : haystacks) {
  500.                 if (monitor.isCancelled()) {
  501.                     return result;
  502.                 }
  503.                 monitor.update(1);
  504.                 RevObject o = peel(parseAny(r.getObjectId()));
  505.                 if (!(o instanceof RevCommit)) {
  506.                     continue;
  507.                 }
  508.                 RevCommit c = (RevCommit) o;
  509.                 reset(UNINTERESTING | TEMP_MARK);
  510.                 markStart(c);
  511.                 boolean commitFound = false;
  512.                 RevCommit next;
  513.                 while ((next = next()) != null) {
  514.                     if (References.isSameObject(next, needle)
  515.                             || (next.flags & TEMP_MARK) != 0) {
  516.                         result.add(r);
  517.                         if (returnStrategy == GetMergedIntoStrategy.RETURN_ON_FIRST_FOUND) {
  518.                             return result;
  519.                         }
  520.                         commitFound = true;
  521.                         c.flags |= TEMP_MARK;
  522.                         marked.add(c);
  523.                         break;
  524.                     }
  525.                 }
  526.                 if (!commitFound) {
  527.                     markUninteresting(c);
  528.                     uninteresting.add(c);
  529.                     if (returnStrategy == GetMergedIntoStrategy.RETURN_ON_FIRST_NOT_FOUND) {
  530.                         return result;
  531.                     }
  532.                 }
  533.             }
  534.         } finally {
  535.             roots.addAll(uninteresting);
  536.             filter = oldRF;
  537.             treeFilter = oldTF;
  538.             for (RevCommit c : marked) {
  539.                 c.flags &= ~TEMP_MARK;
  540.             }
  541.         }
  542.         return result;
  543.     }

  544.     /**
  545.      * Pop the next most recent commit.
  546.      *
  547.      * @return next most recent commit; null if traversal is over.
  548.      * @throws org.eclipse.jgit.errors.MissingObjectException
  549.      *             one or more of the next commit's parents are not available
  550.      *             from the object database, but were thought to be candidates
  551.      *             for traversal. This usually indicates a broken link.
  552.      * @throws org.eclipse.jgit.errors.IncorrectObjectTypeException
  553.      *             one or more of the next commit's parents are not actually
  554.      *             commit objects.
  555.      * @throws java.io.IOException
  556.      *             a pack file or loose object could not be read.
  557.      */
  558.     public RevCommit next() throws MissingObjectException,
  559.             IncorrectObjectTypeException, IOException {
  560.         return pending.next();
  561.     }

  562.     /**
  563.      * Obtain the sort types applied to the commits returned.
  564.      *
  565.      * @return the sorting strategies employed. At least one strategy is always
  566.      *         used, but that strategy may be
  567.      *         {@link org.eclipse.jgit.revwalk.RevSort#NONE}.
  568.      */
  569.     public EnumSet<RevSort> getRevSort() {
  570.         return sorting.clone();
  571.     }

  572.     /**
  573.      * Check whether the provided sorting strategy is enabled.
  574.      *
  575.      * @param sort
  576.      *            a sorting strategy to look for.
  577.      * @return true if this strategy is enabled, false otherwise
  578.      */
  579.     public boolean hasRevSort(RevSort sort) {
  580.         return sorting.contains(sort);
  581.     }

  582.     /**
  583.      * Select a single sorting strategy for the returned commits.
  584.      * <p>
  585.      * Disables all sorting strategies, then enables only the single strategy
  586.      * supplied by the caller.
  587.      *
  588.      * @param s
  589.      *            a sorting strategy to enable.
  590.      */
  591.     public void sort(RevSort s) {
  592.         assertNotStarted();
  593.         sorting.clear();
  594.         sorting.add(s);
  595.     }

  596.     /**
  597.      * Add or remove a sorting strategy for the returned commits.
  598.      * <p>
  599.      * Multiple strategies can be applied at once, in which case some strategies
  600.      * may take precedence over others. As an example,
  601.      * {@link org.eclipse.jgit.revwalk.RevSort#TOPO} must take precedence over
  602.      * {@link org.eclipse.jgit.revwalk.RevSort#COMMIT_TIME_DESC}, otherwise it
  603.      * cannot enforce its ordering.
  604.      *
  605.      * @param s
  606.      *            a sorting strategy to enable or disable.
  607.      * @param use
  608.      *            true if this strategy should be used, false if it should be
  609.      *            removed.
  610.      */
  611.     public void sort(RevSort s, boolean use) {
  612.         assertNotStarted();
  613.         if (use)
  614.             sorting.add(s);
  615.         else
  616.             sorting.remove(s);

  617.         if (sorting.size() > 1)
  618.             sorting.remove(RevSort.NONE);
  619.         else if (sorting.isEmpty())
  620.             sorting.add(RevSort.NONE);
  621.     }

  622.     /**
  623.      * Get the currently configured commit filter.
  624.      *
  625.      * @return the current filter. Never null as a filter is always needed.
  626.      */
  627.     @NonNull
  628.     public RevFilter getRevFilter() {
  629.         return filter;
  630.     }

  631.     /**
  632.      * Set the commit filter for this walker.
  633.      * <p>
  634.      * Multiple filters may be combined by constructing an arbitrary tree of
  635.      * <code>AndRevFilter</code> or <code>OrRevFilter</code> instances to
  636.      * describe the boolean expression required by the application. Custom
  637.      * filter implementations may also be constructed by applications.
  638.      * <p>
  639.      * Note that filters are not thread-safe and may not be shared by concurrent
  640.      * RevWalk instances. Every RevWalk must be supplied its own unique filter,
  641.      * unless the filter implementation specifically states it is (and always
  642.      * will be) thread-safe. Callers may use
  643.      * {@link org.eclipse.jgit.revwalk.filter.RevFilter#clone()} to create a
  644.      * unique filter tree for this RevWalk instance.
  645.      *
  646.      * @param newFilter
  647.      *            the new filter. If null the special
  648.      *            {@link org.eclipse.jgit.revwalk.filter.RevFilter#ALL} filter
  649.      *            will be used instead, as it matches every commit.
  650.      * @see org.eclipse.jgit.revwalk.filter.AndRevFilter
  651.      * @see org.eclipse.jgit.revwalk.filter.OrRevFilter
  652.      */
  653.     public void setRevFilter(RevFilter newFilter) {
  654.         assertNotStarted();
  655.         filter = newFilter != null ? newFilter : RevFilter.ALL;
  656.     }

  657.     /**
  658.      * Get the tree filter used to simplify commits by modified paths.
  659.      *
  660.      * @return the current filter. Never null as a filter is always needed. If
  661.      *         no filter is being applied
  662.      *         {@link org.eclipse.jgit.treewalk.filter.TreeFilter#ALL} is
  663.      *         returned.
  664.      */
  665.     @NonNull
  666.     public TreeFilter getTreeFilter() {
  667.         return treeFilter;
  668.     }

  669.     /**
  670.      * Set the tree filter used to simplify commits by modified paths.
  671.      * <p>
  672.      * If null or {@link org.eclipse.jgit.treewalk.filter.TreeFilter#ALL} the
  673.      * path limiter is removed. Commits will not be simplified.
  674.      * <p>
  675.      * If non-null and not
  676.      * {@link org.eclipse.jgit.treewalk.filter.TreeFilter#ALL} then the tree
  677.      * filter will be installed. Commits will have their ancestry simplified to
  678.      * hide commits that do not contain tree entries matched by the filter,
  679.      * unless {@code setRewriteParents(false)} is called.
  680.      * <p>
  681.      * Usually callers should be inserting a filter graph including
  682.      * {@link org.eclipse.jgit.treewalk.filter.TreeFilter#ANY_DIFF} along with
  683.      * one or more {@link org.eclipse.jgit.treewalk.filter.PathFilter}
  684.      * instances.
  685.      *
  686.      * @param newFilter
  687.      *            new filter. If null the special
  688.      *            {@link org.eclipse.jgit.treewalk.filter.TreeFilter#ALL} filter
  689.      *            will be used instead, as it matches everything.
  690.      * @see org.eclipse.jgit.treewalk.filter.PathFilter
  691.      */
  692.     public void setTreeFilter(TreeFilter newFilter) {
  693.         assertNotStarted();
  694.         treeFilter = newFilter != null ? newFilter : TreeFilter.ALL;
  695.     }

  696.     /**
  697.      * Set whether to rewrite parent pointers when filtering by modified paths.
  698.      * <p>
  699.      * By default, when {@link #setTreeFilter(TreeFilter)} is called with non-
  700.      * null and non-{@link org.eclipse.jgit.treewalk.filter.TreeFilter#ALL}
  701.      * filter, commits will have their ancestry simplified and parents rewritten
  702.      * to hide commits that do not match the filter.
  703.      * <p>
  704.      * This behavior can be bypassed by passing false to this method.
  705.      *
  706.      * @param rewrite
  707.      *            whether to rewrite parents; defaults to true.
  708.      * @since 3.4
  709.      */
  710.     public void setRewriteParents(boolean rewrite) {
  711.         rewriteParents = rewrite;
  712.     }

  713.     boolean getRewriteParents() {
  714.         return rewriteParents;
  715.     }

  716.     /**
  717.      * Should the body of a commit or tag be retained after parsing its headers?
  718.      * <p>
  719.      * Usually the body is always retained, but some application code might not
  720.      * care and would prefer to discard the body of a commit as early as
  721.      * possible, to reduce memory usage.
  722.      * <p>
  723.      * True by default on {@link org.eclipse.jgit.revwalk.RevWalk} and false by
  724.      * default for {@link org.eclipse.jgit.revwalk.ObjectWalk}.
  725.      *
  726.      * @return true if the body should be retained; false it is discarded.
  727.      */
  728.     public boolean isRetainBody() {
  729.         return retainBody;
  730.     }

  731.     /**
  732.      * Set whether or not the body of a commit or tag is retained.
  733.      * <p>
  734.      * If a body of a commit or tag is not retained, the application must call
  735.      * {@link #parseBody(RevObject)} before the body can be safely accessed
  736.      * through the type specific access methods.
  737.      * <p>
  738.      * True by default on {@link org.eclipse.jgit.revwalk.RevWalk} and false by
  739.      * default for {@link org.eclipse.jgit.revwalk.ObjectWalk}.
  740.      *
  741.      * @param retain
  742.      *            true to retain bodies; false to discard them early.
  743.      */
  744.     public void setRetainBody(boolean retain) {
  745.         retainBody = retain;
  746.     }

  747.     /**
  748.      * @return whether only first-parent links should be followed when walking.
  749.      *
  750.      * @since 5.5
  751.      */
  752.     public boolean isFirstParent() {
  753.         return firstParent;
  754.     }

  755.     /**
  756.      * Set whether or not only first parent links should be followed.
  757.      * <p>
  758.      * If set, second- and higher-parent links are not traversed at all.
  759.      * <p>
  760.      * This must be called prior to {@link #markStart(RevCommit)}.
  761.      *
  762.      * @param enable
  763.      *            true to walk only first-parent links.
  764.      *
  765.      * @since 5.5
  766.      */
  767.     public void setFirstParent(boolean enable) {
  768.         assertNotStarted();
  769.         assertNoCommitsMarkedStart();
  770.         firstParent = enable;
  771.         queue = new DateRevQueue(firstParent);
  772.         pending = new StartGenerator(this);
  773.     }

  774.     /**
  775.      * Locate a reference to a blob without loading it.
  776.      * <p>
  777.      * The blob may or may not exist in the repository. It is impossible to tell
  778.      * from this method's return value.
  779.      *
  780.      * @param id
  781.      *            name of the blob object.
  782.      * @return reference to the blob object. Never null.
  783.      */
  784.     @NonNull
  785.     public RevBlob lookupBlob(AnyObjectId id) {
  786.         RevBlob c = (RevBlob) objects.get(id);
  787.         if (c == null) {
  788.             c = new RevBlob(id);
  789.             objects.add(c);
  790.         }
  791.         return c;
  792.     }

  793.     /**
  794.      * Locate a reference to a tree without loading it.
  795.      * <p>
  796.      * The tree may or may not exist in the repository. It is impossible to tell
  797.      * from this method's return value.
  798.      *
  799.      * @param id
  800.      *            name of the tree object.
  801.      * @return reference to the tree object. Never null.
  802.      */
  803.     @NonNull
  804.     public RevTree lookupTree(AnyObjectId id) {
  805.         RevTree c = (RevTree) objects.get(id);
  806.         if (c == null) {
  807.             c = new RevTree(id);
  808.             objects.add(c);
  809.         }
  810.         return c;
  811.     }

  812.     /**
  813.      * Locate a reference to a commit without loading it.
  814.      * <p>
  815.      * The commit may or may not exist in the repository. It is impossible to
  816.      * tell from this method's return value.
  817.      * <p>
  818.      * See {@link #parseHeaders(RevObject)} and {@link #parseBody(RevObject)}
  819.      * for loading contents.
  820.      *
  821.      * @param id
  822.      *            name of the commit object.
  823.      * @return reference to the commit object. Never null.
  824.      */
  825.     @NonNull
  826.     public RevCommit lookupCommit(AnyObjectId id) {
  827.         RevCommit c = (RevCommit) objects.get(id);
  828.         if (c == null) {
  829.             c = createCommit(id);
  830.             objects.add(c);
  831.         }
  832.         return c;
  833.     }

  834.     /**
  835.      * Locate a reference to a tag without loading it.
  836.      * <p>
  837.      * The tag may or may not exist in the repository. It is impossible to tell
  838.      * from this method's return value.
  839.      *
  840.      * @param id
  841.      *            name of the tag object.
  842.      * @return reference to the tag object. Never null.
  843.      */
  844.     @NonNull
  845.     public RevTag lookupTag(AnyObjectId id) {
  846.         RevTag c = (RevTag) objects.get(id);
  847.         if (c == null) {
  848.             c = new RevTag(id);
  849.             objects.add(c);
  850.         }
  851.         return c;
  852.     }

  853.     /**
  854.      * Locate a reference to any object without loading it.
  855.      * <p>
  856.      * The object may or may not exist in the repository. It is impossible to
  857.      * tell from this method's return value.
  858.      *
  859.      * @param id
  860.      *            name of the object.
  861.      * @param type
  862.      *            type of the object. Must be a valid Git object type.
  863.      * @return reference to the object. Never null.
  864.      */
  865.     @NonNull
  866.     public RevObject lookupAny(AnyObjectId id, int type) {
  867.         RevObject r = objects.get(id);
  868.         if (r == null) {
  869.             switch (type) {
  870.             case Constants.OBJ_COMMIT:
  871.                 r = createCommit(id);
  872.                 break;
  873.             case Constants.OBJ_TREE:
  874.                 r = new RevTree(id);
  875.                 break;
  876.             case Constants.OBJ_BLOB:
  877.                 r = new RevBlob(id);
  878.                 break;
  879.             case Constants.OBJ_TAG:
  880.                 r = new RevTag(id);
  881.                 break;
  882.             default:
  883.                 throw new IllegalArgumentException(MessageFormat.format(
  884.                         JGitText.get().invalidGitType, Integer.valueOf(type)));
  885.             }
  886.             objects.add(r);
  887.         }
  888.         return r;
  889.     }

  890.     /**
  891.      * Locate an object that was previously allocated in this walk.
  892.      *
  893.      * @param id
  894.      *            name of the object.
  895.      * @return reference to the object if it has been previously located;
  896.      *         otherwise null.
  897.      */
  898.     public RevObject lookupOrNull(AnyObjectId id) {
  899.         return objects.get(id);
  900.     }

  901.     /**
  902.      * Locate a reference to a commit and immediately parse its content.
  903.      * <p>
  904.      * Unlike {@link #lookupCommit(AnyObjectId)} this method only returns
  905.      * successfully if the commit object exists, is verified to be a commit, and
  906.      * was parsed without error.
  907.      *
  908.      * @param id
  909.      *            name of the commit object.
  910.      * @return reference to the commit object. Never null.
  911.      * @throws org.eclipse.jgit.errors.MissingObjectException
  912.      *             the supplied commit does not exist.
  913.      * @throws org.eclipse.jgit.errors.IncorrectObjectTypeException
  914.      *             the supplied id is not a commit or an annotated tag.
  915.      * @throws java.io.IOException
  916.      *             a pack file or loose object could not be read.
  917.      */
  918.     @NonNull
  919.     public RevCommit parseCommit(AnyObjectId id) throws MissingObjectException,
  920.             IncorrectObjectTypeException, IOException {
  921.         RevObject c = peel(parseAny(id));
  922.         if (!(c instanceof RevCommit))
  923.             throw new IncorrectObjectTypeException(id.toObjectId(),
  924.                     Constants.TYPE_COMMIT);
  925.         return (RevCommit) c;
  926.     }

  927.     /**
  928.      * Locate a reference to a tree.
  929.      * <p>
  930.      * This method only returns successfully if the tree object exists, is
  931.      * verified to be a tree.
  932.      *
  933.      * @param id
  934.      *            name of the tree object, or a commit or annotated tag that may
  935.      *            reference a tree.
  936.      * @return reference to the tree object. Never null.
  937.      * @throws org.eclipse.jgit.errors.MissingObjectException
  938.      *             the supplied tree does not exist.
  939.      * @throws org.eclipse.jgit.errors.IncorrectObjectTypeException
  940.      *             the supplied id is not a tree, a commit or an annotated tag.
  941.      * @throws java.io.IOException
  942.      *             a pack file or loose object could not be read.
  943.      */
  944.     @NonNull
  945.     public RevTree parseTree(AnyObjectId id) throws MissingObjectException,
  946.             IncorrectObjectTypeException, IOException {
  947.         RevObject c = peel(parseAny(id));

  948.         final RevTree t;
  949.         if (c instanceof RevCommit)
  950.             t = ((RevCommit) c).getTree();
  951.         else if (!(c instanceof RevTree))
  952.             throw new IncorrectObjectTypeException(id.toObjectId(),
  953.                     Constants.TYPE_TREE);
  954.         else
  955.             t = (RevTree) c;
  956.         parseHeaders(t);
  957.         return t;
  958.     }

  959.     /**
  960.      * Locate a reference to an annotated tag and immediately parse its content.
  961.      * <p>
  962.      * Unlike {@link #lookupTag(AnyObjectId)} this method only returns
  963.      * successfully if the tag object exists, is verified to be a tag, and was
  964.      * parsed without error.
  965.      *
  966.      * @param id
  967.      *            name of the tag object.
  968.      * @return reference to the tag object. Never null.
  969.      * @throws org.eclipse.jgit.errors.MissingObjectException
  970.      *             the supplied tag does not exist.
  971.      * @throws org.eclipse.jgit.errors.IncorrectObjectTypeException
  972.      *             the supplied id is not a tag or an annotated tag.
  973.      * @throws java.io.IOException
  974.      *             a pack file or loose object could not be read.
  975.      */
  976.     @NonNull
  977.     public RevTag parseTag(AnyObjectId id) throws MissingObjectException,
  978.             IncorrectObjectTypeException, IOException {
  979.         RevObject c = parseAny(id);
  980.         if (!(c instanceof RevTag))
  981.             throw new IncorrectObjectTypeException(id.toObjectId(),
  982.                     Constants.TYPE_TAG);
  983.         return (RevTag) c;
  984.     }

  985.     /**
  986.      * Locate a reference to any object and immediately parse its headers.
  987.      * <p>
  988.      * This method only returns successfully if the object exists and was parsed
  989.      * without error. Parsing an object can be expensive as the type must be
  990.      * determined. For blobs this may mean the blob content was unpacked
  991.      * unnecessarily, and thrown away.
  992.      *
  993.      * @param id
  994.      *            name of the object.
  995.      * @return reference to the object. Never null.
  996.      * @throws org.eclipse.jgit.errors.MissingObjectException
  997.      *             the supplied does not exist.
  998.      * @throws java.io.IOException
  999.      *             a pack file or loose object could not be read.
  1000.      */
  1001.     @NonNull
  1002.     public RevObject parseAny(AnyObjectId id)
  1003.             throws MissingObjectException, IOException {
  1004.         RevObject r = objects.get(id);
  1005.         if (r == null)
  1006.             r = parseNew(id, reader.open(id));
  1007.         else
  1008.             parseHeaders(r);
  1009.         return r;
  1010.     }

  1011.     private RevObject parseNew(AnyObjectId id, ObjectLoader ldr)
  1012.             throws LargeObjectException, CorruptObjectException,
  1013.             MissingObjectException, IOException {
  1014.         RevObject r;
  1015.         int type = ldr.getType();
  1016.         switch (type) {
  1017.         case Constants.OBJ_COMMIT: {
  1018.             final RevCommit c = createCommit(id);
  1019.             c.parseCanonical(this, getCachedBytes(c, ldr));
  1020.             r = c;
  1021.             break;
  1022.         }
  1023.         case Constants.OBJ_TREE: {
  1024.             r = new RevTree(id);
  1025.             r.flags |= PARSED;
  1026.             break;
  1027.         }
  1028.         case Constants.OBJ_BLOB: {
  1029.             r = new RevBlob(id);
  1030.             r.flags |= PARSED;
  1031.             break;
  1032.         }
  1033.         case Constants.OBJ_TAG: {
  1034.             final RevTag t = new RevTag(id);
  1035.             t.parseCanonical(this, getCachedBytes(t, ldr));
  1036.             r = t;
  1037.             break;
  1038.         }
  1039.         default:
  1040.             throw new IllegalArgumentException(MessageFormat.format(
  1041.                     JGitText.get().badObjectType, Integer.valueOf(type)));
  1042.         }
  1043.         objects.add(r);
  1044.         return r;
  1045.     }

  1046.     byte[] getCachedBytes(RevObject obj) throws LargeObjectException,
  1047.             MissingObjectException, IncorrectObjectTypeException, IOException {
  1048.         return getCachedBytes(obj, reader.open(obj, obj.getType()));
  1049.     }

  1050.     byte[] getCachedBytes(RevObject obj, ObjectLoader ldr)
  1051.             throws LargeObjectException, MissingObjectException, IOException {
  1052.         try {
  1053.             return ldr.getCachedBytes(5 * MB);
  1054.         } catch (LargeObjectException tooBig) {
  1055.             tooBig.setObjectId(obj);
  1056.             throw tooBig;
  1057.         }
  1058.     }

  1059.     /**
  1060.      * Asynchronous object parsing.
  1061.      *
  1062.      * @param objectIds
  1063.      *            objects to open from the object store. The supplied collection
  1064.      *            must not be modified until the queue has finished.
  1065.      * @param reportMissing
  1066.      *            if true missing objects are reported by calling failure with a
  1067.      *            MissingObjectException. This may be more expensive for the
  1068.      *            implementation to guarantee. If false the implementation may
  1069.      *            choose to report MissingObjectException, or silently skip over
  1070.      *            the object with no warning.
  1071.      * @return queue to read the objects from.
  1072.      */
  1073.     public <T extends ObjectId> AsyncRevObjectQueue parseAny(
  1074.             Iterable<T> objectIds, boolean reportMissing) {
  1075.         List<T> need = new ArrayList<>();
  1076.         List<RevObject> have = new ArrayList<>();
  1077.         for (T id : objectIds) {
  1078.             RevObject r = objects.get(id);
  1079.             if (r != null && (r.flags & PARSED) != 0)
  1080.                 have.add(r);
  1081.             else
  1082.                 need.add(id);
  1083.         }

  1084.         final Iterator<RevObject> objItr = have.iterator();
  1085.         if (need.isEmpty()) {
  1086.             return new AsyncRevObjectQueue() {
  1087.                 @Override
  1088.                 public RevObject next() {
  1089.                     return objItr.hasNext() ? objItr.next() : null;
  1090.                 }

  1091.                 @Override
  1092.                 public boolean cancel(boolean mayInterruptIfRunning) {
  1093.                     return true;
  1094.                 }

  1095.                 @Override
  1096.                 public void release() {
  1097.                     // In-memory only, no action required.
  1098.                 }
  1099.             };
  1100.         }

  1101.         final AsyncObjectLoaderQueue<T> lItr = reader.open(need, reportMissing);
  1102.         return new AsyncRevObjectQueue() {
  1103.             @Override
  1104.             public RevObject next() throws MissingObjectException,
  1105.                     IncorrectObjectTypeException, IOException {
  1106.                 if (objItr.hasNext())
  1107.                     return objItr.next();
  1108.                 if (!lItr.next())
  1109.                     return null;

  1110.                 ObjectId id = lItr.getObjectId();
  1111.                 ObjectLoader ldr = lItr.open();
  1112.                 RevObject r = objects.get(id);
  1113.                 if (r == null)
  1114.                     r = parseNew(id, ldr);
  1115.                 else if (r instanceof RevCommit) {
  1116.                     byte[] raw = ldr.getCachedBytes();
  1117.                     ((RevCommit) r).parseCanonical(RevWalk.this, raw);
  1118.                 } else if (r instanceof RevTag) {
  1119.                     byte[] raw = ldr.getCachedBytes();
  1120.                     ((RevTag) r).parseCanonical(RevWalk.this, raw);
  1121.                 } else
  1122.                     r.flags |= PARSED;
  1123.                 return r;
  1124.             }

  1125.             @Override
  1126.             public boolean cancel(boolean mayInterruptIfRunning) {
  1127.                 return lItr.cancel(mayInterruptIfRunning);
  1128.             }

  1129.             @Override
  1130.             public void release() {
  1131.                 lItr.release();
  1132.             }
  1133.         };
  1134.     }

  1135.     /**
  1136.      * Ensure the object's critical headers have been parsed.
  1137.      * <p>
  1138.      * This method only returns successfully if the object exists and was parsed
  1139.      * without error.
  1140.      *
  1141.      * @param obj
  1142.      *            the object the caller needs to be parsed.
  1143.      * @throws org.eclipse.jgit.errors.MissingObjectException
  1144.      *             the supplied does not exist.
  1145.      * @throws java.io.IOException
  1146.      *             a pack file or loose object could not be read.
  1147.      */
  1148.     public void parseHeaders(RevObject obj)
  1149.             throws MissingObjectException, IOException {
  1150.         if ((obj.flags & PARSED) == 0)
  1151.             obj.parseHeaders(this);
  1152.     }

  1153.     /**
  1154.      * Ensure the object's full body content is available.
  1155.      * <p>
  1156.      * This method only returns successfully if the object exists and was parsed
  1157.      * without error.
  1158.      *
  1159.      * @param obj
  1160.      *            the object the caller needs to be parsed.
  1161.      * @throws org.eclipse.jgit.errors.MissingObjectException
  1162.      *             the supplied does not exist.
  1163.      * @throws java.io.IOException
  1164.      *             a pack file or loose object could not be read.
  1165.      */
  1166.     public void parseBody(RevObject obj)
  1167.             throws MissingObjectException, IOException {
  1168.         obj.parseBody(this);
  1169.     }

  1170.     /**
  1171.      * Peel back annotated tags until a non-tag object is found.
  1172.      *
  1173.      * @param obj
  1174.      *            the starting object.
  1175.      * @return If {@code obj} is not an annotated tag, {@code obj}. Otherwise
  1176.      *         the first non-tag object that {@code obj} references. The
  1177.      *         returned object's headers have been parsed.
  1178.      * @throws org.eclipse.jgit.errors.MissingObjectException
  1179.      *             a referenced object cannot be found.
  1180.      * @throws java.io.IOException
  1181.      *             a pack file or loose object could not be read.
  1182.      */
  1183.     public RevObject peel(RevObject obj)
  1184.             throws MissingObjectException, IOException {
  1185.         while (obj instanceof RevTag) {
  1186.             parseHeaders(obj);
  1187.             obj = ((RevTag) obj).getObject();
  1188.         }
  1189.         parseHeaders(obj);
  1190.         return obj;
  1191.     }

  1192.     /**
  1193.      * Create a new flag for application use during walking.
  1194.      * <p>
  1195.      * Applications are only assured to be able to create 24 unique flags on any
  1196.      * given revision walker instance. Any flags beyond 24 are offered only if
  1197.      * the implementation has extra free space within its internal storage.
  1198.      *
  1199.      * @param name
  1200.      *            description of the flag, primarily useful for debugging.
  1201.      * @return newly constructed flag instance.
  1202.      * @throws java.lang.IllegalArgumentException
  1203.      *             too many flags have been reserved on this revision walker.
  1204.      */
  1205.     public RevFlag newFlag(String name) {
  1206.         final int m = allocFlag();
  1207.         return new RevFlag(this, name, m);
  1208.     }

  1209.     int allocFlag() {
  1210.         if (freeFlags == 0)
  1211.             throw new IllegalArgumentException(
  1212.                     MessageFormat.format(JGitText.get().flagsAlreadyCreated,
  1213.                             Integer.valueOf(32 - RESERVED_FLAGS)));
  1214.         final int m = Integer.lowestOneBit(freeFlags);
  1215.         freeFlags &= ~m;
  1216.         return m;
  1217.     }

  1218.     /**
  1219.      * Automatically carry a flag from a child commit to its parents.
  1220.      * <p>
  1221.      * A carried flag is copied from the child commit onto its parents when the
  1222.      * child commit is popped from the lowest level of walk's internal graph.
  1223.      *
  1224.      * @param flag
  1225.      *            the flag to carry onto parents, if set on a descendant.
  1226.      */
  1227.     public void carry(RevFlag flag) {
  1228.         if ((freeFlags & flag.mask) != 0)
  1229.             throw new IllegalArgumentException(MessageFormat
  1230.                     .format(JGitText.get().flagIsDisposed, flag.name));
  1231.         if (flag.walker != this)
  1232.             throw new IllegalArgumentException(MessageFormat
  1233.                     .format(JGitText.get().flagNotFromThis, flag.name));
  1234.         carryFlags |= flag.mask;
  1235.     }

  1236.     /**
  1237.      * Automatically carry flags from a child commit to its parents.
  1238.      * <p>
  1239.      * A carried flag is copied from the child commit onto its parents when the
  1240.      * child commit is popped from the lowest level of walk's internal graph.
  1241.      *
  1242.      * @param set
  1243.      *            the flags to carry onto parents, if set on a descendant.
  1244.      */
  1245.     public void carry(Collection<RevFlag> set) {
  1246.         for (RevFlag flag : set)
  1247.             carry(flag);
  1248.     }

  1249.     /**
  1250.      * Preserve a RevFlag during all {@code reset} methods.
  1251.      * <p>
  1252.      * Calling {@code retainOnReset(flag)} avoids needing to pass the flag
  1253.      * during each {@code resetRetain()} invocation on this instance.
  1254.      * <p>
  1255.      * Clearing flags marked retainOnReset requires disposing of the flag with
  1256.      * {@code #disposeFlag(RevFlag)} or disposing of the entire RevWalk by
  1257.      * {@code #dispose()}.
  1258.      *
  1259.      * @param flag
  1260.      *            the flag to retain during all resets.
  1261.      * @since 3.6
  1262.      */
  1263.     public final void retainOnReset(RevFlag flag) {
  1264.         if ((freeFlags & flag.mask) != 0)
  1265.             throw new IllegalArgumentException(MessageFormat
  1266.                     .format(JGitText.get().flagIsDisposed, flag.name));
  1267.         if (flag.walker != this)
  1268.             throw new IllegalArgumentException(MessageFormat
  1269.                     .format(JGitText.get().flagNotFromThis, flag.name));
  1270.         retainOnReset |= flag.mask;
  1271.     }

  1272.     /**
  1273.      * Preserve a set of RevFlags during all {@code reset} methods.
  1274.      * <p>
  1275.      * Calling {@code retainOnReset(set)} avoids needing to pass the flags
  1276.      * during each {@code resetRetain()} invocation on this instance.
  1277.      * <p>
  1278.      * Clearing flags marked retainOnReset requires disposing of the flag with
  1279.      * {@code #disposeFlag(RevFlag)} or disposing of the entire RevWalk by
  1280.      * {@code #dispose()}.
  1281.      *
  1282.      * @param flags
  1283.      *            the flags to retain during all resets.
  1284.      * @since 3.6
  1285.      */
  1286.     public final void retainOnReset(Collection<RevFlag> flags) {
  1287.         for (RevFlag f : flags)
  1288.             retainOnReset(f);
  1289.     }

  1290.     /**
  1291.      * Allow a flag to be recycled for a different use.
  1292.      * <p>
  1293.      * Recycled flags always come back as a different Java object instance when
  1294.      * assigned again by {@link #newFlag(String)}.
  1295.      * <p>
  1296.      * If the flag was previously being carried, the carrying request is
  1297.      * removed. Disposing of a carried flag while a traversal is in progress has
  1298.      * an undefined behavior.
  1299.      *
  1300.      * @param flag
  1301.      *            the to recycle.
  1302.      */
  1303.     public void disposeFlag(RevFlag flag) {
  1304.         freeFlag(flag.mask);
  1305.     }

  1306.     void freeFlag(int mask) {
  1307.         retainOnReset &= ~mask;
  1308.         if (isNotStarted()) {
  1309.             freeFlags |= mask;
  1310.             carryFlags &= ~mask;
  1311.         } else {
  1312.             delayFreeFlags |= mask;
  1313.         }
  1314.     }

  1315.     private void finishDelayedFreeFlags() {
  1316.         if (delayFreeFlags != 0) {
  1317.             freeFlags |= delayFreeFlags;
  1318.             carryFlags &= ~delayFreeFlags;
  1319.             delayFreeFlags = 0;
  1320.         }
  1321.     }

  1322.     /**
  1323.      * Resets internal state and allows this instance to be used again.
  1324.      * <p>
  1325.      * Unlike {@link #dispose()} previously acquired RevObject (and RevCommit)
  1326.      * instances are not invalidated. RevFlag instances are not invalidated, but
  1327.      * are removed from all RevObjects.
  1328.      */
  1329.     public final void reset() {
  1330.         reset(0);
  1331.     }

  1332.     /**
  1333.      * Resets internal state and allows this instance to be used again.
  1334.      * <p>
  1335.      * Unlike {@link #dispose()} previously acquired RevObject (and RevCommit)
  1336.      * instances are not invalidated. RevFlag instances are not invalidated, but
  1337.      * are removed from all RevObjects.
  1338.      *
  1339.      * @param retainFlags
  1340.      *            application flags that should <b>not</b> be cleared from
  1341.      *            existing commit objects.
  1342.      */
  1343.     public final void resetRetain(RevFlagSet retainFlags) {
  1344.         reset(retainFlags.mask);
  1345.     }

  1346.     /**
  1347.      * Resets internal state and allows this instance to be used again.
  1348.      * <p>
  1349.      * Unlike {@link #dispose()} previously acquired RevObject (and RevCommit)
  1350.      * instances are not invalidated. RevFlag instances are not invalidated, but
  1351.      * are removed from all RevObjects.
  1352.      * <p>
  1353.      * See {@link #retainOnReset(RevFlag)} for an alternative that does not
  1354.      * require passing the flags during each reset.
  1355.      *
  1356.      * @param retainFlags
  1357.      *            application flags that should <b>not</b> be cleared from
  1358.      *            existing commit objects.
  1359.      */
  1360.     public final void resetRetain(RevFlag... retainFlags) {
  1361.         int mask = 0;
  1362.         for (RevFlag flag : retainFlags)
  1363.             mask |= flag.mask;
  1364.         reset(mask);
  1365.     }

  1366.     /**
  1367.      * Resets internal state and allows this instance to be used again.
  1368.      * <p>
  1369.      * Unlike {@link #dispose()} previously acquired RevObject (and RevCommit)
  1370.      * instances are not invalidated. RevFlag instances are not invalidated, but
  1371.      * are removed from all RevObjects. The value of {@code firstParent} is
  1372.      * retained.
  1373.      *
  1374.      * @param retainFlags
  1375.      *            application flags that should <b>not</b> be cleared from
  1376.      *            existing commit objects.
  1377.      */
  1378.     protected void reset(int retainFlags) {
  1379.         finishDelayedFreeFlags();
  1380.         retainFlags |= PARSED | retainOnReset;
  1381.         final int clearFlags = ~retainFlags;

  1382.         final FIFORevQueue q = new FIFORevQueue();
  1383.         for (RevCommit c : roots) {
  1384.             if ((c.flags & clearFlags) == 0)
  1385.                 continue;
  1386.             c.flags &= retainFlags;
  1387.             c.reset();
  1388.             q.add(c);
  1389.         }

  1390.         for (;;) {
  1391.             final RevCommit c = q.next();
  1392.             if (c == null)
  1393.                 break;
  1394.             if (c.getParents() == null)
  1395.                 continue;
  1396.             for (RevCommit p : c.getParents()) {
  1397.                 if ((p.flags & clearFlags) == 0)
  1398.                     continue;
  1399.                 p.flags &= retainFlags;
  1400.                 p.reset();
  1401.                 q.add(p);
  1402.             }
  1403.         }

  1404.         roots.clear();
  1405.         queue = new DateRevQueue(firstParent);
  1406.         pending = new StartGenerator(this);
  1407.     }

  1408.     /**
  1409.      * Dispose all internal state and invalidate all RevObject instances.
  1410.      * <p>
  1411.      * All RevObject (and thus RevCommit, etc.) instances previously acquired
  1412.      * from this RevWalk are invalidated by a dispose call. Applications must
  1413.      * not retain or use RevObject instances obtained prior to the dispose call.
  1414.      * All RevFlag instances are also invalidated, and must not be reused.
  1415.      */
  1416.     public void dispose() {
  1417.         reader.close();
  1418.         freeFlags = APP_FLAGS;
  1419.         delayFreeFlags = 0;
  1420.         retainOnReset = 0;
  1421.         carryFlags = UNINTERESTING;
  1422.         firstParent = false;
  1423.         objects.clear();
  1424.         roots.clear();
  1425.         queue = new DateRevQueue(firstParent);
  1426.         pending = new StartGenerator(this);
  1427.         shallowCommitsInitialized = false;
  1428.     }

  1429.     /**
  1430.      * Like {@link #next()}, but if a checked exception is thrown during the
  1431.      * walk it is rethrown as a {@link RevWalkException}.
  1432.      *
  1433.      * @throws RevWalkException
  1434.      *             if an {@link IOException} was thrown.
  1435.      * @return next most recent commit; null if traversal is over.
  1436.      */
  1437.     @Nullable
  1438.     private RevCommit nextForIterator() {
  1439.         try {
  1440.             return next();
  1441.         } catch (IOException e) {
  1442.             throw new RevWalkException(e);
  1443.         }
  1444.     }

  1445.     /**
  1446.      * {@inheritDoc}
  1447.      * <p>
  1448.      * Returns an Iterator over the commits of this walker.
  1449.      * <p>
  1450.      * The returned iterator is only useful for one walk. If this RevWalk gets
  1451.      * reset a new iterator must be obtained to walk over the new results.
  1452.      * <p>
  1453.      * Applications must not use both the Iterator and the {@link #next()} API
  1454.      * at the same time. Pick one API and use that for the entire walk.
  1455.      * <p>
  1456.      * If a checked exception is thrown during the walk (see {@link #next()}) it
  1457.      * is rethrown from the Iterator as a {@link RevWalkException}.
  1458.      *
  1459.      * @see RevWalkException
  1460.      */
  1461.     @Override
  1462.     public Iterator<RevCommit> iterator() {
  1463.         RevCommit first = nextForIterator();

  1464.         return new Iterator<>() {
  1465.             RevCommit next = first;

  1466.             @Override
  1467.             public boolean hasNext() {
  1468.                 return next != null;
  1469.             }

  1470.             @Override
  1471.             public RevCommit next() {
  1472.                 RevCommit r = next;
  1473.                 next = nextForIterator();
  1474.                 return r;
  1475.             }

  1476.             @Override
  1477.             public void remove() {
  1478.                 throw new UnsupportedOperationException();
  1479.             }
  1480.         };
  1481.     }

  1482.     /**
  1483.      * Throws an exception if we have started producing output.
  1484.      */
  1485.     protected void assertNotStarted() {
  1486.         if (isNotStarted())
  1487.             return;
  1488.         throw new IllegalStateException(
  1489.                 JGitText.get().outputHasAlreadyBeenStarted);
  1490.     }

  1491.     /**
  1492.      * Throws an exception if any commits have been marked as start.
  1493.      * <p>
  1494.      * If {@link #markStart(RevCommit)} has already been called,
  1495.      * {@link #reset()} can be called to satisfy this condition.
  1496.      *
  1497.      * @since 5.5
  1498.      */
  1499.     protected void assertNoCommitsMarkedStart() {
  1500.         if (roots.isEmpty())
  1501.             return;
  1502.         throw new IllegalStateException(
  1503.                 JGitText.get().commitsHaveAlreadyBeenMarkedAsStart);
  1504.     }

  1505.     private boolean isNotStarted() {
  1506.         return pending instanceof StartGenerator;
  1507.     }

  1508.     /**
  1509.      * Create and return an {@link org.eclipse.jgit.revwalk.ObjectWalk} using
  1510.      * the same objects.
  1511.      * <p>
  1512.      * Prior to using this method, the caller must reset this RevWalk to clean
  1513.      * any flags that were used during the last traversal.
  1514.      * <p>
  1515.      * The returned ObjectWalk uses the same ObjectReader, internal object pool,
  1516.      * and free RevFlags. Once the ObjectWalk is created, this RevWalk should
  1517.      * not be used anymore.
  1518.      *
  1519.      * @return a new walk, using the exact same object pool.
  1520.      */
  1521.     public ObjectWalk toObjectWalkWithSameObjects() {
  1522.         ObjectWalk ow = new ObjectWalk(reader);
  1523.         RevWalk rw = ow;
  1524.         rw.objects = objects;
  1525.         rw.freeFlags = freeFlags;
  1526.         return ow;
  1527.     }

  1528.     /**
  1529.      * Construct a new unparsed commit for the given object.
  1530.      *
  1531.      * @param id
  1532.      *            the object this walker requires a commit reference for.
  1533.      * @return a new unparsed reference for the object.
  1534.      */
  1535.     protected RevCommit createCommit(AnyObjectId id) {
  1536.         return new RevCommit(id);
  1537.     }

  1538.     void carryFlagsImpl(RevCommit c) {
  1539.         final int carry = c.flags & carryFlags;
  1540.         if (carry != 0)
  1541.             RevCommit.carryFlags(c, carry);
  1542.     }

  1543.     /**
  1544.      * Assume additional commits are shallow (have no parents).
  1545.      * <p>
  1546.      * This method is a No-op if the collection is empty.
  1547.      *
  1548.      * @param ids
  1549.      *            commits that should be treated as shallow commits, in addition
  1550.      *            to any commits already known to be shallow by the repository.
  1551.      * @since 3.3
  1552.      */
  1553.     public void assumeShallow(Collection<? extends ObjectId> ids) {
  1554.         for (ObjectId id : ids)
  1555.             lookupCommit(id).parents = RevCommit.NO_PARENTS;
  1556.     }

  1557.     /**
  1558.      * Reads the "shallow" file and applies it by setting the parents of shallow
  1559.      * commits to an empty array.
  1560.      * <p>
  1561.      * There is a sequencing problem if the first commit being parsed is a
  1562.      * shallow commit, since {@link RevCommit#parseCanonical(RevWalk, byte[])}
  1563.      * calls this method before its callers add the new commit to the
  1564.      * {@link RevWalk#objects} map. That means a call from this method to
  1565.      * {@link #lookupCommit(AnyObjectId)} fails to find that commit and creates
  1566.      * a new one, which is promptly discarded.
  1567.      * <p>
  1568.      * To avoid that, {@link RevCommit#parseCanonical(RevWalk, byte[])} passes
  1569.      * its commit to this method, so that this method can apply the shallow
  1570.      * state to it directly and avoid creating the duplicate commit object.
  1571.      *
  1572.      * @param rc
  1573.      *            the initial commit being parsed
  1574.      * @throws IOException
  1575.      *             if the shallow commits file can't be read
  1576.      */
  1577.     void initializeShallowCommits(RevCommit rc) throws IOException {
  1578.         if (shallowCommitsInitialized) {
  1579.             throw new IllegalStateException(
  1580.                     JGitText.get().shallowCommitsAlreadyInitialized);
  1581.         }

  1582.         shallowCommitsInitialized = true;

  1583.         if (reader == null) {
  1584.             return;
  1585.         }

  1586.         for (ObjectId id : reader.getShallowCommits()) {
  1587.             if (id.equals(rc.getId())) {
  1588.                 rc.parents = RevCommit.NO_PARENTS;
  1589.             } else {
  1590.                 lookupCommit(id).parents = RevCommit.NO_PARENTS;
  1591.             }
  1592.         }
  1593.     }
  1594. }