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 : package com.google.gerrit.server.change;
15 :
16 : import static com.google.common.base.Preconditions.checkArgument;
17 : import static java.util.Objects.requireNonNull;
18 : import static java.util.stream.Collectors.toMap;
19 :
20 : import com.google.auto.value.AutoValue;
21 : import com.google.auto.value.extension.memoized.Memoized;
22 : import com.google.common.annotations.VisibleForTesting;
23 : import com.google.common.collect.ImmutableList;
24 : import com.google.common.collect.ListMultimap;
25 : import com.google.common.collect.Lists;
26 : import com.google.common.collect.Maps;
27 : import com.google.common.collect.MultimapBuilder;
28 : import com.google.gerrit.entities.Change;
29 : import com.google.gerrit.entities.PatchSet;
30 : import com.google.gerrit.entities.Project;
31 : import com.google.gerrit.server.git.GitRepositoryManager;
32 : import com.google.gerrit.server.permissions.ChangePermission;
33 : import com.google.gerrit.server.permissions.PermissionBackend;
34 : import com.google.gerrit.server.permissions.PermissionBackendException;
35 : import com.google.gerrit.server.project.ProjectCache;
36 : import com.google.gerrit.server.project.ProjectState;
37 : import com.google.gerrit.server.query.change.ChangeData;
38 : import com.google.inject.Inject;
39 : import com.google.inject.Singleton;
40 : import java.io.IOException;
41 : import java.util.ArrayDeque;
42 : import java.util.ArrayList;
43 : import java.util.Collection;
44 : import java.util.Deque;
45 : import java.util.HashMap;
46 : import java.util.HashSet;
47 : import java.util.LinkedHashSet;
48 : import java.util.List;
49 : import java.util.Map;
50 : import java.util.Objects;
51 : import java.util.Set;
52 : import org.eclipse.jgit.lib.ObjectId;
53 : import org.eclipse.jgit.lib.Repository;
54 : import org.eclipse.jgit.revwalk.RevCommit;
55 : import org.eclipse.jgit.revwalk.RevWalk;
56 :
57 : @Singleton
58 : public class RelatedChangesSorter {
59 : private final GitRepositoryManager repoManager;
60 : private final PermissionBackend permissionBackend;
61 : private final ProjectCache projectCache;
62 :
63 : @Inject
64 : RelatedChangesSorter(
65 : GitRepositoryManager repoManager,
66 : PermissionBackend permissionBackend,
67 145 : ProjectCache projectCache) {
68 145 : this.repoManager = repoManager;
69 145 : this.permissionBackend = permissionBackend;
70 145 : this.projectCache = projectCache;
71 145 : }
72 :
73 : public List<PatchSetData> sort(List<ChangeData> in, PatchSet startPs)
74 : throws IOException, PermissionBackendException {
75 5 : checkArgument(!in.isEmpty(), "Input may not be empty");
76 : // Map of all patch sets, keyed by commit SHA-1.
77 5 : Map<ObjectId, PatchSetData> byId = collectById(in);
78 5 : PatchSetData start = byId.get(startPs.commitId());
79 5 : requireNonNull(
80 : start,
81 : () ->
82 0 : String.format(
83 : "commit %s of patch set %s not found in %s",
84 0 : startPs.commitId().name(),
85 0 : startPs.id(),
86 0 : byId.entrySet().stream()
87 0 : .collect(toMap(e -> e.getKey().name(), e -> e.getValue().patchSet().id()))));
88 :
89 : // Map of patch set -> immediate parent.
90 5 : ListMultimap<PatchSetData, PatchSetData> parents =
91 5 : MultimapBuilder.hashKeys(in.size()).arrayListValues(3).build();
92 : // Map of patch set -> immediate children.
93 5 : ListMultimap<PatchSetData, PatchSetData> children =
94 5 : MultimapBuilder.hashKeys(in.size()).arrayListValues(3).build();
95 : // All other patch sets of the same change as startPs.
96 5 : List<PatchSetData> otherPatchSetsOfStart = new ArrayList<>();
97 :
98 5 : for (ChangeData cd : in) {
99 5 : for (PatchSet ps : cd.patchSets()) {
100 5 : PatchSetData thisPsd = requireNonNull(byId.get(ps.commitId()));
101 5 : if (cd.getId().equals(start.id()) && !ps.id().equals(start.psId())) {
102 2 : otherPatchSetsOfStart.add(thisPsd);
103 : }
104 5 : for (RevCommit p : thisPsd.commit().getParents()) {
105 5 : PatchSetData parentPsd = byId.get(p);
106 5 : if (parentPsd != null) {
107 5 : parents.put(thisPsd, parentPsd);
108 5 : children.put(parentPsd, thisPsd);
109 : }
110 : }
111 5 : }
112 5 : }
113 :
114 5 : Collection<PatchSetData> ancestors = walkAncestors(parents, start);
115 5 : List<PatchSetData> descendants =
116 5 : walkDescendants(children, start, otherPatchSetsOfStart, ancestors);
117 5 : List<PatchSetData> result = new ArrayList<>(ancestors.size() + descendants.size() - 1);
118 5 : result.addAll(Lists.reverse(descendants));
119 5 : result.addAll(ancestors);
120 5 : return result;
121 : }
122 :
123 : private Map<ObjectId, PatchSetData> collectById(List<ChangeData> in) throws IOException {
124 5 : Project.NameKey project = in.get(0).change().getProject();
125 5 : Map<ObjectId, PatchSetData> result = Maps.newHashMapWithExpectedSize(in.size() * 3);
126 5 : try (Repository repo = repoManager.openRepository(project);
127 5 : RevWalk rw = new RevWalk(repo)) {
128 5 : rw.setRetainBody(true);
129 5 : for (ChangeData cd : in) {
130 5 : checkArgument(
131 5 : cd.change().getProject().equals(project),
132 : "Expected change %s in project %s, found %s",
133 5 : cd.getId(),
134 : project,
135 5 : cd.change().getProject());
136 5 : for (PatchSet ps : cd.patchSets()) {
137 5 : RevCommit c = rw.parseCommit(ps.commitId());
138 5 : PatchSetData psd = PatchSetData.create(cd, ps, c);
139 5 : result.put(ps.commitId(), psd);
140 5 : }
141 5 : }
142 : }
143 5 : return result;
144 : }
145 :
146 : private Collection<PatchSetData> walkAncestors(
147 : ListMultimap<PatchSetData, PatchSetData> parents, PatchSetData start)
148 : throws PermissionBackendException {
149 5 : LinkedHashSet<PatchSetData> result = new LinkedHashSet<>();
150 5 : Deque<PatchSetData> pending = new ArrayDeque<>();
151 5 : pending.add(start);
152 5 : while (!pending.isEmpty()) {
153 5 : PatchSetData psd = pending.remove();
154 5 : if (result.contains(psd) || !isVisible(psd)) {
155 0 : continue;
156 : }
157 5 : result.add(psd);
158 5 : pending.addAll(Lists.reverse(parents.get(psd)));
159 5 : }
160 5 : return result;
161 : }
162 :
163 : private List<PatchSetData> walkDescendants(
164 : ListMultimap<PatchSetData, PatchSetData> children,
165 : PatchSetData start,
166 : List<PatchSetData> otherPatchSetsOfStart,
167 : Iterable<PatchSetData> ancestors)
168 : throws PermissionBackendException {
169 5 : Set<Change.Id> alreadyEmittedChanges = new HashSet<>();
170 5 : addAllChangeIds(alreadyEmittedChanges, ancestors);
171 :
172 : // Prefer descendants found by following the original patch set passed in.
173 5 : List<PatchSetData> result =
174 5 : walkDescendentsImpl(alreadyEmittedChanges, children, ImmutableList.of(start));
175 5 : addAllChangeIds(alreadyEmittedChanges, result);
176 :
177 : // Then, go back and add new indirect descendants found by following any
178 : // other patch sets of start. These show up after all direct descendants,
179 : // because we wouldn't know where in the walk to insert them.
180 5 : result.addAll(walkDescendentsImpl(alreadyEmittedChanges, children, otherPatchSetsOfStart));
181 5 : return result;
182 : }
183 :
184 : private static void addAllChangeIds(
185 : Collection<Change.Id> changeIds, Iterable<PatchSetData> psds) {
186 5 : for (PatchSetData psd : psds) {
187 5 : changeIds.add(psd.id());
188 5 : }
189 5 : }
190 :
191 : private List<PatchSetData> walkDescendentsImpl(
192 : Set<Change.Id> alreadyEmittedChanges,
193 : ListMultimap<PatchSetData, PatchSetData> children,
194 : List<PatchSetData> start)
195 : throws PermissionBackendException {
196 5 : if (start.isEmpty()) {
197 4 : return new ArrayList<>();
198 : }
199 5 : Map<Change.Id, PatchSet.Id> maxPatchSetIds = new HashMap<>();
200 5 : Set<PatchSetData> seen = new HashSet<>();
201 5 : List<PatchSetData> allPatchSets = new ArrayList<>();
202 5 : Deque<PatchSetData> pending = new ArrayDeque<>();
203 5 : pending.addAll(start);
204 5 : while (!pending.isEmpty()) {
205 5 : PatchSetData psd = pending.remove();
206 5 : if (seen.contains(psd) || !isVisible(psd)) {
207 0 : continue;
208 : }
209 5 : seen.add(psd);
210 5 : if (!alreadyEmittedChanges.contains(psd.id())) {
211 : // Don't emit anything for changes that were previously emitted, even
212 : // though different patch sets might show up later. However, do
213 : // continue walking through them for the purposes of finding indirect
214 : // descendants.
215 4 : PatchSet.Id oldMax = maxPatchSetIds.get(psd.id());
216 4 : if (oldMax == null || psd.psId().get() > oldMax.get()) {
217 4 : maxPatchSetIds.put(psd.id(), psd.psId());
218 : }
219 4 : allPatchSets.add(psd);
220 : }
221 : // Depth-first search with newest children first.
222 5 : for (PatchSetData child : children.get(psd)) {
223 4 : pending.addFirst(child);
224 4 : }
225 5 : }
226 :
227 : // If we saw the same change multiple times, prefer the latest patch set.
228 5 : List<PatchSetData> result = new ArrayList<>(allPatchSets.size());
229 5 : for (PatchSetData psd : allPatchSets) {
230 4 : if (requireNonNull(maxPatchSetIds.get(psd.id())).equals(psd.psId())) {
231 4 : result.add(psd);
232 : }
233 4 : }
234 5 : return result;
235 : }
236 :
237 : private boolean isVisible(PatchSetData psd) throws PermissionBackendException {
238 5 : PermissionBackend.WithUser perm = permissionBackend.currentUser();
239 5 : return perm.change(psd.data()).test(ChangePermission.READ)
240 5 : && projectCache.get(psd.data().project()).map(ProjectState::statePermitsRead).orElse(false);
241 : }
242 :
243 : @AutoValue
244 5 : public abstract static class PatchSetData {
245 : @VisibleForTesting
246 : static PatchSetData create(ChangeData cd, PatchSet ps, RevCommit commit) {
247 5 : return new AutoValue_RelatedChangesSorter_PatchSetData(cd, ps, commit);
248 : }
249 :
250 : public abstract ChangeData data();
251 :
252 : public abstract PatchSet patchSet();
253 :
254 : public abstract RevCommit commit();
255 :
256 : public PatchSet.Id psId() {
257 5 : return patchSet().id();
258 : }
259 :
260 : public Change.Id id() {
261 5 : return psId().changeId();
262 : }
263 :
264 : @Memoized
265 : @Override
266 : public int hashCode() {
267 5 : return Objects.hash(patchSet().id(), commit());
268 : }
269 :
270 : @Override
271 : public final boolean equals(Object obj) {
272 0 : if (!(obj instanceof PatchSetData)) {
273 0 : return false;
274 : }
275 0 : PatchSetData o = (PatchSetData) obj;
276 0 : return Objects.equals(patchSet().id(), o.patchSet().id())
277 0 : && Objects.equals(commit(), o.commit());
278 : }
279 : }
280 : }
|
