1 /*
2 * Copyright (C) 2008, Shawn O. Pearce <spearce@spearce.org>
3 * and other copyright owners as documented in the project's IP log.
4 *
5 * This program and the accompanying materials are made available
6 * under the terms of the Eclipse Distribution License v1.0 which
7 * accompanies this distribution, is reproduced below, and is
8 * available at http://www.eclipse.org/org/documents/edl-v10.php
9 *
10 * All rights reserved.
11 *
12 * Redistribution and use in source and binary forms, with or
13 * without modification, are permitted provided that the following
14 * conditions are met:
15 *
16 * - Redistributions of source code must retain the above copyright
17 * notice, this list of conditions and the following disclaimer.
18 *
19 * - Redistributions in binary form must reproduce the above
20 * copyright notice, this list of conditions and the following
21 * disclaimer in the documentation and/or other materials provided
22 * with the distribution.
23 *
24 * - Neither the name of the Eclipse Foundation, Inc. nor the
25 * names of its contributors may be used to endorse or promote
26 * products derived from this software without specific prior
27 * written permission.
28 *
29 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
30 * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
31 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
32 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
33 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
34 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
35 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
36 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
37 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
38 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
39 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
40 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
41 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
42 */
43
44 package org.eclipse.jgit.revwalk;
45
46 import java.io.IOException;
47 import java.util.List;
48
49 import org.eclipse.jgit.diff.DiffConfig;
50 import org.eclipse.jgit.diff.DiffEntry;
51 import org.eclipse.jgit.diff.DiffEntry.ChangeType;
52 import org.eclipse.jgit.diff.RenameDetector;
53 import org.eclipse.jgit.errors.CorruptObjectException;
54 import org.eclipse.jgit.errors.IncorrectObjectTypeException;
55 import org.eclipse.jgit.errors.MissingObjectException;
56 import org.eclipse.jgit.errors.StopWalkException;
57 import org.eclipse.jgit.lib.ObjectId;
58 import org.eclipse.jgit.revwalk.filter.RevFilter;
59 import org.eclipse.jgit.treewalk.TreeWalk;
60 import org.eclipse.jgit.treewalk.filter.TreeFilter;
61
62 /**
63 * Filter applying a {@link org.eclipse.jgit.treewalk.filter.TreeFilter} against
64 * changed paths in each commit.
65 * <p>
66 * Each commit is differenced concurrently against all of its parents to look
67 * for tree entries that are interesting to the
68 * {@link org.eclipse.jgit.treewalk.filter.TreeFilter}.
69 *
70 * @since 3.5
71 */
72 public class TreeRevFilter extends RevFilter {
73 private static final int PARSED = RevWalk.PARSED;
74
75 private static final int UNINTERESTING = RevWalk.UNINTERESTING;
76
77 private final int rewriteFlag;
78 private final TreeWalk pathFilter;
79
80 /**
81 * Create a {@link org.eclipse.jgit.revwalk.filter.RevFilter} from a
82 * {@link org.eclipse.jgit.treewalk.filter.TreeFilter}.
83 *
84 * @param walker
85 * walker used for reading trees.
86 * @param t
87 * filter to compare against any changed paths in each commit. If
88 * a {@link org.eclipse.jgit.revwalk.FollowFilter}, will be
89 * replaced with a new filter following new paths after a rename.
90 * @since 3.5
91 */
92 public TreeRevFilter(RevWalk walker, TreeFilter t) {
93 this(walker, t, 0);
94 }
95
96
97 /**
98 * Create a filter for the first phase of a parent-rewriting limited revision
99 * walk.
100 * <p>
101 * This filter is ANDed to evaluate before all other filters and ties the
102 * configured {@link TreeFilter} into the revision walking process.
103 * <p>
104 * If no interesting tree entries are found the commit is colored with
105 * {@code rewriteFlag}, allowing a later pass implemented by
106 * {@link RewriteGenerator} to remove those colored commits from the DAG.
107 *
108 * @see RewriteGenerator
109 *
110 * @param walker
111 * walker used for reading trees.
112 * @param t
113 * filter to compare against any changed paths in each commit. If a
114 * {@link FollowFilter}, will be replaced with a new filter
115 * following new paths after a rename.
116 * @param rewriteFlag
117 * flag to color commits to be removed from the simplified DAT.
118 */
119 TreeRevFilter(final RevWalk walker, final TreeFilter t,
120 final int rewriteFlag) {
121 pathFilter = new TreeWalk(walker.reader);
122 pathFilter.setFilter(t);
123 pathFilter.setRecursive(t.shouldBeRecursive());
124 this.rewriteFlag = rewriteFlag;
125 }
126
127 /** {@inheritDoc} */
128 @Override
129 public RevFilter clone() {
130 throw new UnsupportedOperationException();
131 }
132
133 /** {@inheritDoc} */
134 @Override
135 public boolean include(RevWalk walker, RevCommit c)
136 throws StopWalkException, MissingObjectException,
137 IncorrectObjectTypeException, IOException {
138 // Reset the tree filter to scan this commit and parents.
139 //
140 final RevCommit[] pList = c.parents;
141 final int nParents = pList.length;
142 final TreeWalk tw = pathFilter;
143 final ObjectId[] trees = new ObjectId[nParents + 1];
144 for (int i = 0; i < nParents; i++) {
145 final RevCommit p = c.parents[i];
146 if ((p.flags & PARSED) == 0)
147 p.parseHeaders(walker);
148 trees[i] = p.getTree();
149 }
150 trees[nParents] = c.getTree();
151 tw.reset(trees);
152
153 if (nParents == 1) {
154 // We have exactly one parent. This is a very common case.
155 //
156 int chgs = 0, adds = 0;
157 while (tw.next()) {
158 chgs++;
159 if (tw.getRawMode(0) == 0 && tw.getRawMode(1) != 0)
160 adds++;
161 else
162 break; // no point in looking at this further.
163 }
164
165 if (chgs == 0) {
166 // No changes, so our tree is effectively the same as
167 // our parent tree. We pass the buck to our parent.
168 //
169 c.flags |= rewriteFlag;
170 return false;
171 } else {
172 // We have interesting items, but neither of the special
173 // cases denoted above.
174 //
175 if (adds > 0 && tw.getFilter() instanceof FollowFilter) {
176 // One of the paths we care about was added in this
177 // commit. We need to update our filter to its older
178 // name, if we can discover it. Find out what that is.
179 //
180 updateFollowFilter(trees, ((FollowFilter) tw.getFilter()).cfg);
181 }
182 return true;
183 }
184 } else if (nParents == 0) {
185 // We have no parents to compare against. Consider us to be
186 // REWRITE only if we have no paths matching our filter.
187 //
188 if (tw.next())
189 return true;
190 c.flags |= rewriteFlag;
191 return false;
192 }
193
194 // We are a merge commit. We can only be REWRITE if we are same
195 // to _all_ parents. We may also be able to eliminate a parent if
196 // it does not contribute changes to us. Such a parent may be an
197 // uninteresting side branch.
198 //
199 final int[] chgs = new int[nParents];
200 final int[] adds = new int[nParents];
201 while (tw.next()) {
202 final int myMode = tw.getRawMode(nParents);
203 for (int i = 0; i < nParents; i++) {
204 final int pMode = tw.getRawMode(i);
205 if (myMode == pMode && tw.idEqual(i, nParents))
206 continue;
207
208 chgs[i]++;
209 if (pMode == 0 && myMode != 0)
210 adds[i]++;
211 }
212 }
213
214 boolean same = false;
215 boolean diff = false;
216 for (int i = 0; i < nParents; i++) {
217 if (chgs[i] == 0) {
218 // No changes, so our tree is effectively the same as
219 // this parent tree. We pass the buck to only this one
220 // parent commit.
221 //
222
223 final RevCommit p = pList[i];
224 if ((p.flags & UNINTERESTING) != 0) {
225 // This parent was marked as not interesting by the
226 // application. We should look for another parent
227 // that is interesting.
228 //
229 same = true;
230 continue;
231 }
232
233 c.flags |= rewriteFlag;
234 c.parents = new RevCommit[] { p };
235 return false;
236 }
237
238 if (chgs[i] == adds[i]) {
239 // All of the differences from this parent were because we
240 // added files that they did not have. This parent is our
241 // "empty tree root" and thus their history is not relevant.
242 // Cut our grandparents to be an empty list.
243 //
244 pList[i].parents = RevCommit.NO_PARENTS;
245 }
246
247 // We have an interesting difference relative to this parent.
248 //
249 diff = true;
250 }
251
252 if (diff && !same) {
253 // We did not abort above, so we are different in at least one
254 // way from all of our parents. We have to take the blame for
255 // that difference.
256 //
257 return true;
258 }
259
260 // We are the same as all of our parents. We must keep them
261 // as they are and allow those parents to flow into pending
262 // for further scanning.
263 //
264 c.flags |= rewriteFlag;
265 return false;
266 }
267
268 /** {@inheritDoc} */
269 @Override
270 public boolean requiresCommitBody() {
271 return false;
272 }
273
274 private void updateFollowFilter(ObjectId[] trees, DiffConfig cfg)
275 throws MissingObjectException, IncorrectObjectTypeException,
276 CorruptObjectException, IOException {
277 TreeWalk tw = pathFilter;
278 FollowFilter oldFilter = (FollowFilter) tw.getFilter();
279 tw.setFilter(TreeFilter.ANY_DIFF);
280 tw.reset(trees);
281
282 List<DiffEntry> files = DiffEntry.scan(tw);
283 RenameDetector rd = new RenameDetector(tw.getObjectReader(), cfg);
284 rd.addAll(files);
285 files = rd.compute();
286
287 TreeFilter newFilter = oldFilter;
288 for (DiffEntry ent : files) {
289 if (isRename(ent) && ent.getNewPath().equals(oldFilter.getPath())) {
290 newFilter = FollowFilter.create(ent.getOldPath(), cfg);
291 RenameCallback callback = oldFilter.getRenameCallback();
292 if (callback != null) {
293 callback.renamed(ent);
294 // forward the callback to the new follow filter
295 ((FollowFilter) newFilter).setRenameCallback(callback);
296 }
297 break;
298 }
299 }
300 tw.setFilter(newFilter);
301 }
302
303 private static boolean isRename(DiffEntry ent) {
304 return ent.getChangeType() == ChangeType.RENAME
305 || ent.getChangeType() == ChangeType.COPY;
306 }
307 }