1 /* 2 * Copyright (C) 2008-2009, Google Inc. 3 * Copyright (C) 2008, Marek Zawirski <marek.zawirski@gmail.com> 4 * Copyright (C) 2008, Shawn O. Pearce <spearce@spearce.org> 5 * and other copyright owners as documented in the project's IP log. 6 * 7 * This program and the accompanying materials are made available 8 * under the terms of the Eclipse Distribution License v1.0 which 9 * accompanies this distribution, is reproduced below, and is 10 * available at http://www.eclipse.org/org/documents/edl-v10.php 11 * 12 * All rights reserved. 13 * 14 * Redistribution and use in source and binary forms, with or 15 * without modification, are permitted provided that the following 16 * conditions are met: 17 * 18 * - Redistributions of source code must retain the above copyright 19 * notice, this list of conditions and the following disclaimer. 20 * 21 * - Redistributions in binary form must reproduce the above 22 * copyright notice, this list of conditions and the following 23 * disclaimer in the documentation and/or other materials provided 24 * with the distribution. 25 * 26 * - Neither the name of the Eclipse Foundation, Inc. nor the 27 * names of its contributors may be used to endorse or promote 28 * products derived from this software without specific prior 29 * written permission. 30 * 31 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND 32 * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, 33 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 34 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 35 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR 36 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 37 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 38 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 39 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 40 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 41 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 42 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF 43 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 44 */ 45 46 package org.eclipse.jgit.revwalk; 47 48 import java.io.IOException; 49 import java.text.MessageFormat; 50 51 import org.eclipse.jgit.errors.IncorrectObjectTypeException; 52 import org.eclipse.jgit.errors.MissingObjectException; 53 import org.eclipse.jgit.internal.JGitText; 54 import org.eclipse.jgit.revwalk.filter.AndRevFilter; 55 import org.eclipse.jgit.revwalk.filter.RevFilter; 56 import org.eclipse.jgit.treewalk.filter.TreeFilter; 57 58 /** 59 * Initial RevWalk generator that bootstraps a new walk. 60 * <p> 61 * Initially RevWalk starts with this generator as its chosen implementation. 62 * The first request for a RevCommit from the RevWalk instance calls to our 63 * {@link #next()} method, and we replace ourselves with the best Generator 64 * implementation available based upon the current RevWalk configuration. 65 */ 66 class StartGenerator extends Generator { 67 private final RevWalk walker; 68 69 StartGenerator(RevWalk w) { 70 super(w.isFirstParent()); 71 walker = w; 72 } 73 74 @Override 75 int outputType() { 76 return 0; 77 } 78 79 @Override 80 RevCommit next() throws MissingObjectException, 81 IncorrectObjectTypeException, IOException { 82 Generator g; 83 84 final RevWalk w = walker; 85 RevFilter rf = w.getRevFilter(); 86 final TreeFilter tf = w.getTreeFilter(); 87 AbstractRevQueue q = walker.queue; 88 89 if (rf == RevFilter.MERGE_BASE) { 90 // Computing for merge bases is a special case and does not 91 // use the bulk of the generator pipeline. 92 // 93 if (tf != TreeFilter.ALL) { 94 throw new IllegalStateException(MessageFormat.format( 95 JGitText.get().cannotCombineTreeFilterWithRevFilter, tf, rf)); 96 } 97 if (w.isFirstParent()) { 98 throw new IllegalStateException( 99 JGitText.get().cannotFindMergeBaseUsingFirstParent); 100 } 101 102 final MergeBaseGeneratorerator.html#MergeBaseGenerator">MergeBaseGenerator mbg = new MergeBaseGenerator(w); 103 walker.pending = mbg; 104 walker.queue = AbstractRevQueue.EMPTY_QUEUE; 105 mbg.init(q); 106 return mbg.next(); 107 } 108 109 final boolean uninteresting = q.anybodyHasFlag(RevWalk.UNINTERESTING); 110 boolean boundary = walker.hasRevSort(RevSort.BOUNDARY); 111 112 if (!boundary && walker instanceof ObjectWalk) { 113 // The object walker requires boundary support to color 114 // trees and blobs at the boundary uninteresting so it 115 // does not produce those in the result. 116 // 117 boundary = true; 118 } 119 if (boundary && !uninteresting) { 120 // If we were not fed uninteresting commits we will never 121 // construct a boundary. There is no reason to include the 122 // extra overhead associated with that in our pipeline. 123 // 124 boundary = false; 125 } 126 127 final DateRevQueue pending; 128 int pendingOutputType = 0; 129 if (q instanceof DateRevQueue) 130 pending = (DateRevQueue)q; 131 else 132 pending = new DateRevQueue(q); 133 if (tf != TreeFilter.ALL) { 134 int rewriteFlag; 135 if (w.getRewriteParents()) { 136 pendingOutputType |= HAS_REWRITE | NEEDS_REWRITE; 137 rewriteFlag = RevWalk.REWRITE; 138 } else 139 rewriteFlag = 0; 140 rf = AndRevFilter.create(new TreeRevFilter(w, tf, rewriteFlag), rf); 141 } 142 143 walker.queue = q; 144 145 if (walker instanceof DepthWalk) { 146 DepthWalk dw = (DepthWalk) walker; 147 g = new DepthGenerator(dw, pending); 148 } else { 149 g = new PendingGenerator(w, pending, rf, pendingOutputType); 150 151 if (walker.hasRevSort(RevSort.BOUNDARY)) { 152 // Because the boundary generator may produce uninteresting 153 // commits we cannot allow the pending generator to dispose 154 // of them early. 155 // 156 ((PendingGenerator) g).canDispose = false; 157 } 158 } 159 160 if ((g.outputType() & NEEDS_REWRITE) != 0) { 161 // Correction for an upstream NEEDS_REWRITE is to buffer 162 // fully and then apply a rewrite generator that can 163 // pull through the rewrite chain and produce a dense 164 // output graph. 165 // 166 g = new FIFORevQueue(g); 167 g = new RewriteGenerator(g); 168 } 169 170 if (walker.hasRevSort(RevSort.TOPO) 171 && (g.outputType() & SORT_TOPO) == 0) 172 g = new TopoSortGenerator(g); 173 if (walker.hasRevSort(RevSort.REVERSE)) 174 g = new LIFORevQueue(g); 175 if (boundary) 176 g = new BoundaryGenerator(w, g); 177 else if (uninteresting) { 178 // Try to protect ourselves from uninteresting commits producing 179 // due to clock skew in the commit time stamps. Delay such that 180 // we have a chance at coloring enough of the graph correctly, 181 // and then strip any UNINTERESTING nodes that may have leaked 182 // through early. 183 // 184 if (pending.peek() != null) 185 g = new DelayRevQueue(g); 186 g = new FixUninterestingGenerator(g); 187 } 188 189 w.pending = g; 190 return g.next(); 191 } 192 }