Line data Source code
1 : // Copyright (C) 2015 The Android Open Source Project
2 : //
3 : // Licensed under the Apache License, Version 2.0 (the "License");
4 : // you may not use this file except in compliance with the License.
5 : // You may obtain a copy of the License at
6 : //
7 : // http://www.apache.org/licenses/LICENSE-2.0
8 : //
9 : // Unless required by applicable law or agreed to in writing, software
10 : // distributed under the License is distributed on an "AS IS" BASIS,
11 : // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 : // See the License for the specific language governing permissions and
13 : // limitations under the License.
14 :
15 : package com.google.gerrit.server.git;
16 :
17 : import static com.google.common.base.Preconditions.checkState;
18 : import static org.eclipse.jgit.revwalk.RevFlag.UNINTERESTING;
19 :
20 : import com.google.common.annotations.VisibleForTesting;
21 : import com.google.common.collect.ImmutableList;
22 : import com.google.common.collect.ImmutableSet;
23 : import com.google.common.collect.Iterables;
24 : import com.google.common.collect.ListMultimap;
25 : import com.google.common.collect.MultimapBuilder;
26 : import com.google.common.collect.SetMultimap;
27 : import com.google.common.collect.Sets;
28 : import com.google.common.collect.SortedSetMultimap;
29 : import com.google.common.flogger.FluentLogger;
30 : import com.google.gerrit.common.Nullable;
31 : import com.google.gerrit.entities.PatchSet;
32 : import com.google.gerrit.entities.Project;
33 : import com.google.gerrit.server.PatchSetUtil;
34 : import com.google.gerrit.server.change.RevisionResource;
35 : import com.google.gerrit.server.git.receive.ReceivePackRefCache;
36 : import com.google.gerrit.server.notedb.ChangeNotes;
37 : import java.io.IOException;
38 : import java.util.ArrayDeque;
39 : import java.util.Collection;
40 : import java.util.Deque;
41 : import java.util.List;
42 : import java.util.Map;
43 : import java.util.Set;
44 : import java.util.TreeSet;
45 : import org.eclipse.jgit.lib.ObjectId;
46 : import org.eclipse.jgit.revwalk.RevCommit;
47 :
48 : /**
49 : * Helper for assigning groups to commits during {@code ReceiveCommits}.
50 : *
51 : * <p>For each commit encountered along a walk between the branch tip and the tip of the push, the
52 : * group of a commit is defined as follows:
53 : *
54 : * <ul>
55 : * <li>If the commit is an existing patch set of a change, the group is read from the group field
56 : * in the corresponding {@link PatchSet} record.
57 : * <li>If all of a commit's parents are merged into the branch, then its group is its own SHA-1.
58 : * <li>If the commit has a single parent that is not yet merged into the branch, then its group is
59 : * the same as the parent's group.
60 : * <li>
61 : * <li>For a merge commit, choose a parent and use that parent's group. If one of the parents has
62 : * a group from a patch set, use that group, otherwise, use the group from the first parent.
63 : * In addition to setting this merge commit's group, use the chosen group for all commits that
64 : * would otherwise use a group from the parents that were not chosen.
65 : * <li>If a merge commit has multiple parents whose group comes from separate patch sets,
66 : * concatenate the groups from those parents together. This indicates two side branches were
67 : * pushed separately, followed by the merge.
68 : * <li>
69 : * </ul>
70 : *
71 : * <p>Callers must call {@link #visit(RevCommit)} on all commits between the current branch tip and
72 : * the tip of a push, in reverse topo order (parents before children). Once all commits have been
73 : * visited, call {@link #getGroups()} for the result.
74 : */
75 : public class GroupCollector {
76 104 : private static final FluentLogger logger = FluentLogger.forEnclosingClass();
77 :
78 : public static List<String> getDefaultGroups(ObjectId commit) {
79 48 : return ImmutableList.of(commit.name());
80 : }
81 :
82 : public static List<String> getGroups(RevisionResource rsrc) {
83 0 : if (rsrc.getEdit().isPresent()) {
84 : // Groups for an edit are just the base revision's groups, since they have
85 : // the same parent.
86 0 : return rsrc.getEdit().get().getBasePatchSet().groups();
87 : }
88 0 : return rsrc.getPatchSet().groups();
89 : }
90 :
91 : interface Lookup {
92 : List<String> lookup(PatchSet.Id psId);
93 : }
94 :
95 : private final ReceivePackRefCache receivePackRefCache;
96 : private final ListMultimap<ObjectId, String> groups;
97 : private final SetMultimap<String, String> groupAliases;
98 : private final Lookup groupLookup;
99 :
100 : private boolean done;
101 :
102 : /**
103 : * Returns a new {@link GroupCollector} instance.
104 : *
105 : * @see GroupCollector for what this class does.
106 : */
107 : public static GroupCollector create(
108 : ReceivePackRefCache receivePackRefCache,
109 : PatchSetUtil psUtil,
110 : ChangeNotes.Factory notesFactory,
111 : Project.NameKey project) {
112 89 : return new GroupCollector(
113 : receivePackRefCache,
114 : psId -> {
115 : // TODO(dborowitz): Reuse open repository from caller.
116 45 : ChangeNotes notes = notesFactory.createChecked(project, psId.changeId());
117 45 : PatchSet ps = psUtil.get(notes, psId);
118 45 : return ps != null ? ps.groups() : null;
119 : });
120 : }
121 :
122 : /**
123 : * Returns a new {@link GroupCollector} instance.
124 : *
125 : * <p>Used in production code by using {@link com.google.gerrit.server.notedb.ChangeNotes.Factory}
126 : * to get a group SHA1 (40 bytes string representation) from a {@link
127 : * com.google.gerrit.entities.PatchSet.Id}. Unit tests use this method directly by passing their
128 : * own lookup function.
129 : *
130 : * @see GroupCollector for what this class does.
131 : */
132 : @VisibleForTesting
133 90 : GroupCollector(ReceivePackRefCache receivePackRefCache, Lookup groupLookup) {
134 90 : this.receivePackRefCache = receivePackRefCache;
135 90 : this.groupLookup = groupLookup;
136 90 : groups = MultimapBuilder.hashKeys().arrayListValues().build();
137 90 : groupAliases = MultimapBuilder.hashKeys().hashSetValues().build();
138 90 : }
139 :
140 : /**
141 : * Process the given {@link RevCommit}. Callers must call {@link #visit(RevCommit)} on all commits
142 : * between the current branch tip and the tip of a push, in reverse topo order (parents before
143 : * children). Once all commits have been visited, call {@link #getGroups()} for the result.
144 : *
145 : * @see GroupCollector for what this class does.
146 : */
147 : public void visit(RevCommit c) throws IOException {
148 90 : checkState(!done, "visit() called after getGroups()");
149 90 : Set<RevCommit> interestingParents = getInterestingParents(c);
150 :
151 90 : if (interestingParents.isEmpty()) {
152 : // All parents are uninteresting: treat this commit as the root of a new
153 : // group of related changes.
154 90 : groups.put(c, c.name());
155 90 : return;
156 52 : } else if (interestingParents.size() == 1) {
157 : // Only one parent is new in this push. If it is the only parent, just use
158 : // that parent's group. If there are multiple parents, perhaps this commit
159 : // is a merge of a side branch. This commit belongs in that parent's group
160 : // in that case.
161 50 : groups.putAll(c, groups.get(interestingParents.iterator().next()));
162 50 : return;
163 : }
164 :
165 : // Multiple parents, merging at least two branches containing new commits in
166 : // this push.
167 17 : Set<String> thisCommitGroups = new TreeSet<>();
168 17 : Set<String> parentGroupsNewInThisPush =
169 17 : Sets.newLinkedHashSetWithExpectedSize(interestingParents.size());
170 17 : for (RevCommit p : interestingParents) {
171 17 : Collection<String> parentGroups = groups.get(p);
172 17 : if (parentGroups.isEmpty()) {
173 0 : throw new IllegalStateException(
174 0 : String.format("no group assigned to parent %s of commit %s", p.name(), c.name()));
175 : }
176 :
177 17 : for (String parentGroup : parentGroups) {
178 17 : if (isGroupFromExistingPatchSet(p, parentGroup)) {
179 : // This parent's group is from an existing patch set, i.e. the parent
180 : // not new in this push. Use this group for the commit.
181 17 : thisCommitGroups.add(parentGroup);
182 : } else {
183 : // This parent's group is new in this push.
184 5 : parentGroupsNewInThisPush.add(parentGroup);
185 : }
186 17 : }
187 17 : }
188 :
189 : Iterable<String> toAlias;
190 17 : if (thisCommitGroups.isEmpty()) {
191 : // All parent groups were new in this push. Pick the first one and alias
192 : // other parents' groups to this first parent.
193 2 : String firstParentGroup = parentGroupsNewInThisPush.iterator().next();
194 2 : thisCommitGroups = ImmutableSet.of(firstParentGroup);
195 2 : toAlias = Iterables.skip(parentGroupsNewInThisPush, 1);
196 2 : } else {
197 : // For each parent group that was new in this push, alias it to the actual
198 : // computed group(s) for this commit.
199 17 : toAlias = parentGroupsNewInThisPush;
200 : }
201 17 : groups.putAll(c, thisCommitGroups);
202 17 : for (String pg : toAlias) {
203 5 : groupAliases.putAll(pg, thisCommitGroups);
204 5 : }
205 17 : }
206 :
207 : /**
208 : * Returns the groups that got collected from visiting commits using {@link #visit(RevCommit)}.
209 : */
210 : public SortedSetMultimap<ObjectId, String> getGroups() throws IOException {
211 89 : done = true;
212 89 : SortedSetMultimap<ObjectId, String> result =
213 89 : MultimapBuilder.hashKeys(groups.keySet().size()).treeSetValues().build();
214 89 : for (Map.Entry<ObjectId, Collection<String>> e : groups.asMap().entrySet()) {
215 89 : ObjectId id = e.getKey();
216 89 : result.putAll(id.copy(), resolveGroups(id, e.getValue()));
217 89 : }
218 89 : return result;
219 : }
220 :
221 : private Set<RevCommit> getInterestingParents(RevCommit commit) {
222 90 : Set<RevCommit> result = Sets.newLinkedHashSetWithExpectedSize(commit.getParentCount());
223 90 : for (RevCommit p : commit.getParents()) {
224 90 : if (!p.has(UNINTERESTING)) {
225 52 : result.add(p);
226 : }
227 : }
228 90 : return result;
229 : }
230 :
231 : private boolean isGroupFromExistingPatchSet(RevCommit commit, String group) throws IOException {
232 17 : ObjectId id = parseGroup(commit, group);
233 17 : return id != null && !receivePackRefCache.patchSetIdsFromObjectId(id).isEmpty();
234 : }
235 :
236 : private Set<String> resolveGroups(ObjectId forCommit, Collection<String> candidates)
237 : throws IOException {
238 89 : Set<String> actual = Sets.newTreeSet();
239 89 : Set<String> done = Sets.newHashSetWithExpectedSize(candidates.size());
240 89 : Set<String> seen = Sets.newHashSetWithExpectedSize(candidates.size());
241 89 : Deque<String> todo = new ArrayDeque<>(candidates);
242 : // BFS through all aliases to find groups that are not aliased to anything
243 : // else.
244 89 : while (!todo.isEmpty()) {
245 89 : String g = todo.removeFirst();
246 89 : if (!seen.add(g)) {
247 0 : continue;
248 : }
249 89 : Set<String> aliases = groupAliases.get(g);
250 89 : if (aliases.isEmpty()) {
251 89 : if (!done.contains(g)) {
252 89 : Iterables.addAll(actual, resolveGroup(forCommit, g));
253 89 : done.add(g);
254 : }
255 : } else {
256 5 : todo.addAll(aliases);
257 : }
258 89 : }
259 89 : return actual;
260 : }
261 :
262 : @Nullable
263 : private ObjectId parseGroup(ObjectId forCommit, String group) {
264 : try {
265 89 : return ObjectId.fromString(group);
266 0 : } catch (IllegalArgumentException e) {
267 : // Shouldn't happen; some sort of corruption or manual tinkering?
268 0 : logger.atWarning().log("group for commit %s is not a SHA-1: %s", forCommit.name(), group);
269 0 : return null;
270 : }
271 : }
272 :
273 : private Iterable<String> resolveGroup(ObjectId forCommit, String group) throws IOException {
274 89 : ObjectId id = parseGroup(forCommit, group);
275 89 : if (id != null) {
276 89 : PatchSet.Id psId = Iterables.getFirst(receivePackRefCache.patchSetIdsFromObjectId(id), null);
277 89 : if (psId != null) {
278 46 : List<String> groups = groupLookup.lookup(psId);
279 : // Group for existing patch set may be missing, e.g. if group has not
280 : // been migrated yet.
281 46 : if (groups != null && !groups.isEmpty()) {
282 46 : return groups;
283 : }
284 : }
285 : }
286 89 : return ImmutableList.of(group);
287 : }
288 : }
|
