org.spearce.jgit/src/org/spearce/jgit/revwalk/PendingGenerator.java

   1 /*
   2  * Copyright (C) 2008, Shawn O. Pearce <spearce@spearce.org>
   3  *
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or
   7  * without modification, are permitted provided that the following
   8  * conditions are met:
   9  *
  10  * - Redistributions of source code must retain the above copyright
  11  *   notice, this list of conditions and the following disclaimer.
  12  *
  13  * - Redistributions in binary form must reproduce the above
  14  *   copyright notice, this list of conditions and the following
  15  *   disclaimer in the documentation and/or other materials provided
  16  *   with the distribution.
  17  *
  18  * - Neither the name of the Git Development Community nor the
  19  *   names of its contributors may be used to endorse or promote
  20  *   products derived from this software without specific prior
  21  *   written permission.
  22  *
  23  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
  24  * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
  25  * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  26  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
  28  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  29  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  30  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  31  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  32  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  33  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  34  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
  35  * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  36  */
  37
  38 package org.spearce.jgit.revwalk;
  39
  40 import java.io.IOException;
  41
  42 import org.spearce.jgit.errors.IncorrectObjectTypeException;
  43 import org.spearce.jgit.errors.MissingObjectException;
  44 import org.spearce.jgit.errors.StopWalkException;
  45 import org.spearce.jgit.lib.ObjectId;
  46 import org.spearce.jgit.revwalk.filter.RevFilter;
  47
  48 /**
  49  * Default (and first pass) RevCommit Generator implementation for RevWalk.
  50  * <p>
  51  * This generator starts from a set of one or more commits and process them in
  52  * descending (newest to oldest) commit time order. Commits automatically cause
  53  * their parents to be enqueued for further processing, allowing the entire
  54  * commit graph to be walked. A {@link RevFilter} may be used to select a subset
  55  * of the commits and return them to the caller.
  56  */
  57 class PendingGenerator extends Generator {
  58         private static final int PARSED = RevWalk.PARSED;
  59
  60         private static final int SEEN = RevWalk.SEEN;
  61
  62         private static final int UNINTERESTING = RevWalk.UNINTERESTING;
  63
  64         /**
  65          * Number of additional commits to scan after we think we are done.
  66          * <p>
  67          * This small buffer of commits is scanned to ensure we didn't miss anything
  68          * as a result of clock skew when the commits were made. We need to set our
  69          * constant to 1 additional commit due to the use of a pre-increment
  70          * operator when accessing the value.
  71          */
  72         static final int OVER_SCAN = 5 + 1;
  73
  74         /** A commit near the end of time, to initialize {@link #last} with. */
  75         private static final RevCommit INIT_LAST;
  76
  77         static {
  78                 INIT_LAST = new RevCommit(ObjectId.zeroId());
  79                 INIT_LAST.commitTime = Integer.MAX_VALUE;
  80         }
  81
  82         private final RevWalk walker;
  83
  84         private final DateRevQueue pending;
  85
  86         private final RevFilter filter;
  87
  88         private final int output;
  89
  90         /** Last commit produced to the caller from {@link #next()}. */
  91         private RevCommit last = INIT_LAST;
  92
  93         /**
  94          * Number of commits we have remaining in our over-scan allotment.
  95          * <p>
  96          * Only relevant if there are {@link #UNINTERESTING} commits in the
  97          * {@link #pending} queue.
  98          */
  99         private int overScan = OVER_SCAN;
 100
 101         boolean canDispose;
 102
 103         PendingGenerator(final RevWalk w, final DateRevQueue p,
 104                         final RevFilter f, final int out) {
 105                 walker = w;
 106                 pending = p;
 107                 filter = f;
 108                 output = out;
 109                 canDispose = true;
 110         }
 111
 112         @Override
 113         int outputType() {
 114                 return output | SORT_COMMIT_TIME_DESC;
 115         }
 116
 117         @Override
 118         RevCommit next() throws MissingObjectException,
 119                         IncorrectObjectTypeException, IOException {
 120                 try {
 121                         for (;;) {
 122                                 final RevCommit c = pending.next();
 123                                 if (c == null) {
 124                                         walker.curs.release();
 125                                         return null;
 126                                 }
 127
 128                                 final boolean produce;
 129                                 if ((c.flags & UNINTERESTING) != 0)
 130                                         produce = false;
 131                                 else
 132                                         produce = filter.include(walker, c);
 133
 134                                 for (final RevCommit p : c.parents) {
 135                                         if ((p.flags & SEEN) != 0)
 136                                                 continue;
 137                                         if ((p.flags & PARSED) == 0)
 138                                                 p.parse(walker);
 139                                         p.flags |= SEEN;
 140                                         pending.add(p);
 141                                 }
 142                                 walker.carryFlagsImpl(c);
 143
 144                                 if ((c.flags & UNINTERESTING) != 0) {
 145                                         if (pending.everbodyHasFlag(UNINTERESTING)) {
 146                                                 final RevCommit n = pending.peek();
 147                                                 if (n != null && n.commitTime >= last.commitTime) {
 148                                                         // This is too close to call. The next commit we
 149                                                         // would pop is dated after the last one produced.
 150                                                         // We have to keep going to ensure that we carry
 151                                                         // flags as much as necessary.
 152                                                         //
 153                                                         overScan = OVER_SCAN;
 154                                                 } else if (--overScan == 0)
 155                                                         throw StopWalkException.INSTANCE;
 156                                         } else {
 157                                                 overScan = OVER_SCAN;
 158                                         }
 159                                         if (canDispose)
 160                                                 c.dispose();
 161                                         continue;
 162                                 }
 163
 164                                 if (produce)
 165                                         return last = c;
 166                                 else if (canDispose)
 167                                         c.dispose();
 168                         }
 169                 } catch (StopWalkException swe) {
 170                         walker.curs.release();
 171                         pending.clear();
 172                         return null;
 173                 }
 174         }
 175 }