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.change;
16 :
17 : import static com.google.common.base.Preconditions.checkState;
18 :
19 : import com.google.auto.value.AutoValue;
20 : import com.google.common.annotations.VisibleForTesting;
21 : import com.google.common.collect.ImmutableList;
22 : import com.google.common.collect.Iterables;
23 : import com.google.common.collect.ListMultimap;
24 : import com.google.common.collect.MultimapBuilder;
25 : import com.google.common.collect.Ordering;
26 : import com.google.common.flogger.FluentLogger;
27 : import com.google.gerrit.entities.PatchSet;
28 : import com.google.gerrit.entities.Project;
29 : import com.google.gerrit.exceptions.StorageException;
30 : import com.google.gerrit.server.git.GitRepositoryManager;
31 : import com.google.gerrit.server.query.change.ChangeData;
32 : import com.google.inject.Inject;
33 : import java.io.IOException;
34 : import java.util.ArrayDeque;
35 : import java.util.ArrayList;
36 : import java.util.Collection;
37 : import java.util.Deque;
38 : import java.util.HashSet;
39 : import java.util.List;
40 : import java.util.Map;
41 : import java.util.Set;
42 : import org.eclipse.jgit.errors.IncorrectObjectTypeException;
43 : import org.eclipse.jgit.errors.MissingObjectException;
44 : import org.eclipse.jgit.lib.Repository;
45 : import org.eclipse.jgit.revwalk.RevCommit;
46 : import org.eclipse.jgit.revwalk.RevFlag;
47 : import org.eclipse.jgit.revwalk.RevWalk;
48 :
49 : /**
50 : * Helper to sort {@link ChangeData}s based on {@link RevWalk} ordering.
51 : *
52 : * <p>Split changes by project, and map each change to a single commit based on the latest patch
53 : * set. The set of patch sets considered may be limited by calling {@link
54 : * #includePatchSets(Iterable)}. Perform a standard {@link RevWalk} on each project repository, do
55 : * an approximate topo sort, and record the order in which each change's commit is seen.
56 : *
57 : * <p>Once an order within each project is determined, groups of changes are sorted based on the
58 : * project name. This is slightly more stable than sorting on something like the commit or change
59 : * timestamp, as it will not unexpectedly reorder large groups of changes on subsequent calls if one
60 : * of the changes was updated.
61 : */
62 : public class WalkSorter {
63 91 : private static final FluentLogger logger = FluentLogger.forEnclosingClass();
64 :
65 91 : private static final Ordering<List<PatchSetData>> PROJECT_LIST_SORTER =
66 91 : Ordering.natural()
67 91 : .nullsFirst()
68 91 : .onResultOf(
69 : (List<PatchSetData> in) -> {
70 2 : if (in == null || in.isEmpty()) {
71 1 : return null;
72 : }
73 : try {
74 2 : return in.get(0).data().change().getProject();
75 0 : } catch (StorageException e) {
76 0 : throw new IllegalStateException(e);
77 : }
78 : });
79 :
80 : private final GitRepositoryManager repoManager;
81 : private final Set<PatchSet.Id> includePatchSets;
82 : private boolean retainBody;
83 :
84 : @Inject
85 91 : WalkSorter(GitRepositoryManager repoManager) {
86 91 : this.repoManager = repoManager;
87 91 : includePatchSets = new HashSet<>();
88 91 : }
89 :
90 : public WalkSorter includePatchSets(Iterable<PatchSet.Id> patchSets) {
91 1 : Iterables.addAll(includePatchSets, patchSets);
92 1 : return this;
93 : }
94 :
95 : public WalkSorter setRetainBody(boolean retainBody) {
96 1 : this.retainBody = retainBody;
97 1 : return this;
98 : }
99 :
100 : public Iterable<PatchSetData> sort(Iterable<ChangeData> in) throws IOException {
101 : ListMultimap<Project.NameKey, ChangeData> byProject =
102 11 : MultimapBuilder.hashKeys().arrayListValues().build();
103 11 : for (ChangeData cd : in) {
104 11 : byProject.put(cd.change().getProject(), cd);
105 11 : }
106 :
107 11 : List<List<PatchSetData>> sortedByProject = new ArrayList<>(byProject.keySet().size());
108 11 : for (Map.Entry<Project.NameKey, Collection<ChangeData>> e : byProject.asMap().entrySet()) {
109 11 : sortedByProject.add(sortProject(e.getKey(), e.getValue()));
110 11 : }
111 11 : sortedByProject.sort(PROJECT_LIST_SORTER);
112 11 : return Iterables.concat(sortedByProject);
113 : }
114 :
115 : private ImmutableList<PatchSetData> sortProject(
116 : Project.NameKey project, Collection<ChangeData> in) throws IOException {
117 11 : try (Repository repo = repoManager.openRepository(project);
118 11 : RevWalk rw = new RevWalk(repo)) {
119 11 : rw.setRetainBody(retainBody);
120 11 : ListMultimap<RevCommit, PatchSetData> byCommit = byCommit(rw, in);
121 11 : if (byCommit.isEmpty()) {
122 1 : return ImmutableList.of();
123 11 : } else if (byCommit.size() == 1) {
124 2 : return ImmutableList.of(byCommit.values().iterator().next());
125 : }
126 :
127 : // Walk from all patch set SHA-1s, and terminate as soon as we've found
128 : // everything we're looking for. This is equivalent to just sorting the
129 : // list of commits by the RevWalk's configured order.
130 : //
131 : // Partially topo sort the list, ensuring no parent is emitted before a
132 : // direct child that is also in the input set. This preserves the stable,
133 : // expected sort in the case where many commits share the same timestamp,
134 : // e.g. a quick rebase. It also avoids JGit's topo sort, which slurps all
135 : // interesting commits at the beginning, which is a problem since we don't
136 : // know which commits to mark as uninteresting. Finding a reasonable set
137 : // of commits to mark uninteresting (the "rootmost" set) is at least as
138 : // difficult as just implementing this partial topo sort ourselves.
139 : //
140 : // (This is slightly less efficient than JGit's topo sort, which uses a
141 : // private in-degree field in RevCommit rather than multimaps. We assume
142 : // the input size is small enough that this is not an issue.)
143 :
144 11 : Set<RevCommit> commits = byCommit.keySet();
145 11 : ListMultimap<RevCommit, RevCommit> children = collectChildren(commits);
146 : ListMultimap<RevCommit, RevCommit> pending =
147 11 : MultimapBuilder.hashKeys().arrayListValues().build();
148 11 : Deque<RevCommit> todo = new ArrayDeque<>();
149 :
150 11 : RevFlag done = rw.newFlag("done");
151 11 : markStart(rw, commits);
152 11 : int expected = commits.size();
153 11 : int found = 0;
154 : RevCommit c;
155 11 : List<PatchSetData> result = new ArrayList<>(expected);
156 11 : while (found < expected && (c = rw.next()) != null) {
157 11 : if (!commits.contains(c)) {
158 4 : continue;
159 : }
160 11 : todo.clear();
161 11 : todo.add(c);
162 11 : int i = 0;
163 11 : while (!todo.isEmpty()) {
164 : // Sanity check: we can't pop more than N pending commits, otherwise
165 : // we have an infinite loop due to programmer error or something.
166 11 : checkState(++i <= commits.size(), "Too many pending steps while sorting %s", commits);
167 11 : RevCommit t = todo.removeFirst();
168 11 : if (t.has(done)) {
169 0 : continue;
170 : }
171 11 : boolean ready = true;
172 11 : for (RevCommit child : children.get(t)) {
173 11 : if (!child.has(done)) {
174 2 : pending.put(child, t);
175 2 : ready = false;
176 : }
177 11 : }
178 11 : if (ready) {
179 11 : found += emit(t, byCommit, result, done);
180 11 : todo.addAll(pending.get(t));
181 : }
182 11 : }
183 11 : }
184 11 : return ImmutableList.copyOf(result);
185 2 : }
186 : }
187 :
188 : private static ListMultimap<RevCommit, RevCommit> collectChildren(Set<RevCommit> commits) {
189 : ListMultimap<RevCommit, RevCommit> children =
190 11 : MultimapBuilder.hashKeys().arrayListValues().build();
191 11 : for (RevCommit c : commits) {
192 11 : for (RevCommit p : c.getParents()) {
193 11 : if (commits.contains(p)) {
194 11 : children.put(p, c);
195 : }
196 : }
197 11 : }
198 11 : return children;
199 : }
200 :
201 : private static int emit(
202 : RevCommit c,
203 : ListMultimap<RevCommit, PatchSetData> byCommit,
204 : List<PatchSetData> result,
205 : RevFlag done) {
206 11 : if (c.has(done)) {
207 0 : return 0;
208 : }
209 11 : c.add(done);
210 11 : Collection<PatchSetData> psds = byCommit.get(c);
211 11 : if (!psds.isEmpty()) {
212 11 : result.addAll(psds);
213 11 : return 1;
214 : }
215 0 : return 0;
216 : }
217 :
218 : private ListMultimap<RevCommit, PatchSetData> byCommit(RevWalk rw, Collection<ChangeData> in)
219 : throws IOException {
220 11 : ListMultimap<RevCommit, PatchSetData> byCommit =
221 11 : MultimapBuilder.hashKeys(in.size()).arrayListValues(1).build();
222 11 : for (ChangeData cd : in) {
223 11 : PatchSet maxPs = null;
224 11 : for (PatchSet ps : cd.patchSets()) {
225 11 : if (shouldInclude(ps) && (maxPs == null || ps.id().get() > maxPs.id().get())) {
226 11 : maxPs = ps;
227 : }
228 11 : }
229 11 : if (maxPs == null) {
230 1 : continue; // No patch sets matched.
231 : }
232 : try {
233 11 : RevCommit c = rw.parseCommit(maxPs.commitId());
234 11 : byCommit.put(c, PatchSetData.create(cd, maxPs, c));
235 0 : } catch (MissingObjectException | IncorrectObjectTypeException e) {
236 0 : logger.atWarning().withCause(e).log(
237 0 : "missing commit %s for patch set %s", maxPs.commitId().name(), maxPs.id());
238 11 : }
239 11 : }
240 11 : return byCommit;
241 : }
242 :
243 : private boolean shouldInclude(PatchSet ps) {
244 11 : return includePatchSets.isEmpty() || includePatchSets.contains(ps.id());
245 : }
246 :
247 : private static void markStart(RevWalk rw, Iterable<RevCommit> commits) throws IOException {
248 11 : for (RevCommit c : commits) {
249 11 : rw.markStart(c);
250 11 : }
251 11 : }
252 :
253 : @AutoValue
254 11 : public abstract static class PatchSetData {
255 : @VisibleForTesting
256 : static PatchSetData create(ChangeData cd, PatchSet ps, RevCommit commit) {
257 11 : return new AutoValue_WalkSorter_PatchSetData(cd, ps, commit);
258 : }
259 :
260 : public abstract ChangeData data();
261 :
262 : abstract PatchSet patchSet();
263 :
264 : abstract RevCommit commit();
265 : }
266 : }
|
