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
48 import org.eclipse.jgit.errors.IncorrectObjectTypeException;
49 import org.eclipse.jgit.errors.MissingObjectException;
50
51 /**
52 * Replaces a RevCommit's parents until not colored with REWRITE.
53 * <p>
54 * Before a RevCommit is returned to the caller its parents are updated to
55 * create a dense DAG. Instead of reporting the actual parents as recorded when
56 * the commit was created the returned commit will reflect the next closest
57 * commit that matched the revision walker's filters.
58 * <p>
59 * This generator is the second phase of a path limited revision walk and
60 * assumes it is receiving RevCommits from {@link TreeRevFilter},
61 * after they have been fully buffered by {@link AbstractRevQueue}. The full
62 * buffering is necessary to allow the simple loop used within our own
63 * {@link #rewrite(RevCommit)} to pull completely through a strand of
64 * {@link RevWalk#REWRITE} colored commits and come up with a simplification
65 * that makes the DAG dense. Not fully buffering the commits first would cause
66 * this loop to abort early, due to commits not being parsed and colored
67 * correctly.
68 *
69 * @see TreeRevFilter
70 */
71 class RewriteGenerator extends Generator {
72 private static final int REWRITE = RevWalk.REWRITE;
73
74 /** For {@link #cleanup(RevCommit[])} to remove duplicate parents. */
75 private static final int DUPLICATE = RevWalk.TEMP_MARK;
76
77 private final Generator source;
78
79 RewriteGenerator(final Generator s) {
80 source = s;
81 }
82
83 @Override
84 void shareFreeList(final BlockRevQueue q) {
85 source.shareFreeList(q);
86 }
87
88 @Override
89 int outputType() {
90 return source.outputType() & ~NEEDS_REWRITE;
91 }
92
93 @Override
94 RevCommit next() throws MissingObjectException,
95 IncorrectObjectTypeException, IOException {
96 for (;;) {
97 final RevCommit c = source.next();
98 if (c == null)
99 return null;
100
101 boolean rewrote = false;
102 final RevCommit[] pList = c.parents;
103 final int nParents = pList.length;
104 for (int i = 0; i < nParents; i++) {
105 final RevCommit oldp = pList[i];
106 final RevCommit newp = rewrite(oldp);
107 if (oldp != newp) {
108 pList[i] = newp;
109 rewrote = true;
110 }
111 }
112 if (rewrote)
113 c.parents = cleanup(pList);
114
115 return c;
116 }
117 }
118
119 private RevCommit rewrite(RevCommit p) {
120 for (;;) {
121 final RevCommit[] pList = p.parents;
122 if (pList.length > 1) {
123 // This parent is a merge, so keep it.
124 //
125 return p;
126 }
127
128 if ((p.flags & RevWalk.UNINTERESTING) != 0) {
129 // Retain uninteresting parents. They show where the
130 // DAG was cut off because it wasn't interesting.
131 //
132 return p;
133 }
134
135 if ((p.flags & REWRITE) == 0) {
136 // This parent was not eligible for rewriting. We
137 // need to keep it in the DAG.
138 //
139 return p;
140 }
141
142 if (pList.length == 0) {
143 // We can't go back any further, other than to
144 // just delete the parent entirely.
145 //
146 return null;
147 }
148
149 p = pList[0];
150 }
151 }
152
153 private RevCommit[] cleanup(final RevCommit[] oldList) {
154 // Remove any duplicate parents caused due to rewrites (e.g. a merge
155 // with two sides that both simplified back into the merge base).
156 // We also may have deleted a parent by marking it null.
157 //
158 int newCnt = 0;
159 for (int o = 0; o < oldList.length; o++) {
160 final RevCommit p = oldList[o];
161 if (p == null)
162 continue;
163 if ((p.flags & DUPLICATE) != 0) {
164 oldList[o] = null;
165 continue;
166 }
167 p.flags |= DUPLICATE;
168 newCnt++;
169 }
170
171 if (newCnt == oldList.length) {
172 for (final RevCommit p : oldList)
173 p.flags &= ~DUPLICATE;
174 return oldList;
175 }
176
177 final RevCommit[] newList = new RevCommit[newCnt];
178 newCnt = 0;
179 for (final RevCommit p : oldList) {
180 if (p != null) {
181 newList[newCnt++] = p;
182 p.flags &= ~DUPLICATE;
183 }
184 }
185
186 return newList;
187 }
188 }