Line data Source code
1 : // Copyright (C) 2020 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.submit;
16 :
17 : import static com.google.gerrit.server.project.ProjectCache.illegalState;
18 :
19 : import com.google.common.collect.ImmutableList;
20 : import com.google.common.collect.ImmutableSet;
21 : import com.google.common.collect.ImmutableSetMultimap;
22 : import com.google.common.collect.MultimapBuilder;
23 : import com.google.common.collect.SetMultimap;
24 : import com.google.common.flogger.FluentLogger;
25 : import com.google.gerrit.common.UsedAt;
26 : import com.google.gerrit.entities.BranchNameKey;
27 : import com.google.gerrit.entities.Project;
28 : import com.google.gerrit.entities.RefNames;
29 : import com.google.gerrit.entities.SubmoduleSubscription;
30 : import com.google.gerrit.entities.SubscribeSection;
31 : import com.google.gerrit.exceptions.StorageException;
32 : import com.google.gerrit.server.project.NoSuchProjectException;
33 : import com.google.gerrit.server.project.ProjectCache;
34 : import com.google.gerrit.server.submit.MergeOpRepoManager.OpenRepo;
35 : import com.google.inject.AbstractModule;
36 : import com.google.inject.Inject;
37 : import java.io.IOException;
38 : import java.util.ArrayDeque;
39 : import java.util.ArrayList;
40 : import java.util.Collection;
41 : import java.util.Deque;
42 : import java.util.HashMap;
43 : import java.util.HashSet;
44 : import java.util.LinkedHashSet;
45 : import java.util.List;
46 : import java.util.Map;
47 : import java.util.Set;
48 : import org.eclipse.jgit.lib.ObjectId;
49 : import org.eclipse.jgit.lib.Ref;
50 :
51 : /**
52 : * A container which stores subscription relationship. A SubscriptionGraph is calculated every time
53 : * changes are pushed. Some branches are updated in these changes, and if these branches are
54 : * subscribed by other projects, SubscriptionGraph would record information about these updated
55 : * branches and branches/projects affected.
56 : */
57 : public class SubscriptionGraph {
58 : /** Branches updated as part of the enclosing submit or push batch. */
59 : private final ImmutableSet<BranchNameKey> updatedBranches;
60 :
61 : /**
62 : * All branches affected, including those in superprojects and submodules, sorted by submodule
63 : * traversal order. To support nested subscriptions, GitLink commits need to be updated in order.
64 : * The closer to topological "leaf", the earlier a commit should be updated.
65 : *
66 : * <p>For example, there are three projects, top level project p1 subscribed to p2, p2 subscribed
67 : * to bottom level project p3. When submit a change for p3. We need update both p2 and p1. To be
68 : * more precise, we need update p2 first and then update p1.
69 : */
70 : private final ImmutableSet<BranchNameKey> sortedBranches;
71 :
72 : /** Multimap of superproject branch to submodule subscriptions contained in that branch. */
73 : private final ImmutableSetMultimap<BranchNameKey, SubmoduleSubscription> targets;
74 :
75 : /**
76 : * Multimap of superproject name to all branch names within that superproject which have submodule
77 : * subscriptions.
78 : */
79 : private final ImmutableSetMultimap<Project.NameKey, BranchNameKey> branchesByProject;
80 :
81 : /** All branches subscribed by other projects. */
82 : private final ImmutableSet<BranchNameKey> subscribedBranches;
83 :
84 : public SubscriptionGraph(
85 : Set<BranchNameKey> updatedBranches,
86 : SetMultimap<BranchNameKey, SubmoduleSubscription> targets,
87 : SetMultimap<Project.NameKey, BranchNameKey> branchesByProject,
88 : Set<BranchNameKey> subscribedBranches,
89 69 : Set<BranchNameKey> sortedBranches) {
90 69 : this.updatedBranches = ImmutableSet.copyOf(updatedBranches);
91 69 : this.targets = ImmutableSetMultimap.copyOf(targets);
92 69 : this.branchesByProject = ImmutableSetMultimap.copyOf(branchesByProject);
93 69 : this.subscribedBranches = ImmutableSet.copyOf(subscribedBranches);
94 69 : this.sortedBranches = ImmutableSet.copyOf(sortedBranches);
95 69 : }
96 :
97 : /** Returns an empty {@code SubscriptionGraph}. */
98 : static SubscriptionGraph createEmptyGraph(Set<BranchNameKey> updatedBranches) {
99 1 : return new SubscriptionGraph(
100 : updatedBranches,
101 1 : ImmutableSetMultimap.of(),
102 1 : ImmutableSetMultimap.of(),
103 1 : ImmutableSet.of(),
104 1 : ImmutableSet.of());
105 : }
106 :
107 : /** Get branches updated as part of the enclosing submit or push batch. */
108 : public ImmutableSet<BranchNameKey> getUpdatedBranches() {
109 68 : return updatedBranches;
110 : }
111 :
112 : /** Get all superprojects affected. */
113 : public ImmutableSet<Project.NameKey> getAffectedSuperProjects() {
114 69 : return branchesByProject.keySet();
115 : }
116 :
117 : /** See if a {@code project} is a superproject affected. */
118 : boolean isAffectedSuperProject(Project.NameKey project) {
119 68 : return branchesByProject.containsKey(project);
120 : }
121 :
122 : /**
123 : * Returns all branches within the superproject {@code project} which have submodule
124 : * subscriptions.
125 : */
126 : public ImmutableSet<BranchNameKey> getAffectedSuperBranches(Project.NameKey project) {
127 3 : return branchesByProject.get(project);
128 : }
129 :
130 : /**
131 : * Get all affected branches, including the submodule branches and superproject branches, sorted
132 : * by traversal order.
133 : *
134 : * @see SubscriptionGraph#sortedBranches
135 : */
136 : public ImmutableSet<BranchNameKey> getSortedSuperprojectAndSubmoduleBranches() {
137 54 : return sortedBranches;
138 : }
139 :
140 : /** Check if a {@code branch} is a submodule of a superproject. */
141 : @UsedAt(UsedAt.Project.PLUGIN_DELETE_PROJECT)
142 : public boolean hasSuperproject(BranchNameKey branch) {
143 1 : return subscribedBranches.contains(branch);
144 : }
145 :
146 : /** See if a {@code branch} is a superproject branch affected. */
147 : public boolean hasSubscription(BranchNameKey branch) {
148 53 : return targets.containsKey(branch);
149 : }
150 :
151 : /** Get all related {@code SubmoduleSubscription}s whose super branch is {@code branch}. */
152 : public ImmutableSet<SubmoduleSubscription> getSubscriptions(BranchNameKey branch) {
153 3 : return targets.get(branch);
154 : }
155 :
156 : public interface Factory {
157 : SubscriptionGraph compute(Set<BranchNameKey> updatedBranches, MergeOpRepoManager orm)
158 : throws SubmoduleConflictException;
159 : }
160 :
161 152 : public static class SubscriptionGraphModule extends AbstractModule {
162 : @Override
163 : protected void configure() {
164 152 : bind(Factory.class).annotatedWith(VanillaSubscriptionGraph.class).to(DefaultFactory.class);
165 152 : }
166 : }
167 :
168 : public static class DefaultFactory implements Factory {
169 143 : private static final FluentLogger logger = FluentLogger.forEnclosingClass();
170 : private final ProjectCache projectCache;
171 : private final GitModules.Factory gitmodulesFactory;
172 :
173 : @Inject
174 143 : DefaultFactory(GitModules.Factory gitmodulesFactory, ProjectCache projectCache) {
175 143 : this.gitmodulesFactory = gitmodulesFactory;
176 143 : this.projectCache = projectCache;
177 143 : }
178 :
179 : @Override
180 : public SubscriptionGraph compute(Set<BranchNameKey> updatedBranches, MergeOpRepoManager orm)
181 : throws SubmoduleConflictException {
182 69 : Map<BranchNameKey, GitModules> branchGitModules = new HashMap<>();
183 : // All affected branches, including those in superprojects and submodules.
184 69 : Set<BranchNameKey> affectedBranches = new HashSet<>();
185 :
186 : // See SubscriptionGraph#targets.
187 : SetMultimap<BranchNameKey, SubmoduleSubscription> targets =
188 69 : MultimapBuilder.hashKeys().hashSetValues().build();
189 :
190 : // See SubscriptionGraph#branchesByProject.
191 : SetMultimap<Project.NameKey, BranchNameKey> branchesByProject =
192 69 : MultimapBuilder.hashKeys().hashSetValues().build();
193 :
194 : // See SubscriptionGraph#subscribedBranches.
195 69 : Set<BranchNameKey> subscribedBranches = new HashSet<>();
196 :
197 69 : Set<BranchNameKey> sortedBranches =
198 69 : calculateSubscriptionMaps(
199 : updatedBranches,
200 : affectedBranches,
201 : targets,
202 : branchesByProject,
203 : subscribedBranches,
204 : branchGitModules,
205 : orm);
206 :
207 69 : return new SubscriptionGraph(
208 : updatedBranches, targets, branchesByProject, subscribedBranches, sortedBranches);
209 : }
210 :
211 : /**
212 : * Calculate the internal maps used by the operation.
213 : *
214 : * <p>In addition to the return value, the following fields are populated as a side effect:
215 : *
216 : * <ul>
217 : * <li>{@code affectedBranches}
218 : * <li>{@code targets}
219 : * <li>{@code branchesByProject}
220 : * <li>{@code subscribedBranches}
221 : * </ul>
222 : *
223 : * @return the ordered set to be stored in {@link #sortedBranches}.
224 : */
225 : private Set<BranchNameKey> calculateSubscriptionMaps(
226 : Set<BranchNameKey> updatedBranches,
227 : Set<BranchNameKey> affectedBranches,
228 : SetMultimap<BranchNameKey, SubmoduleSubscription> targets,
229 : SetMultimap<Project.NameKey, BranchNameKey> branchesByProject,
230 : Set<BranchNameKey> subscribedBranches,
231 : Map<BranchNameKey, GitModules> branchGitModules,
232 : MergeOpRepoManager orm)
233 : throws SubmoduleConflictException {
234 69 : LinkedHashSet<BranchNameKey> allVisited = new LinkedHashSet<>();
235 69 : for (BranchNameKey updatedBranch : updatedBranches) {
236 69 : if (allVisited.contains(updatedBranch)) {
237 1 : continue;
238 : }
239 :
240 69 : searchForSuperprojects(
241 : updatedBranch,
242 : new LinkedHashSet<>(),
243 : allVisited,
244 : affectedBranches,
245 : targets,
246 : branchesByProject,
247 : subscribedBranches,
248 : branchGitModules,
249 : orm);
250 69 : }
251 :
252 : // Since the searchForSuperprojects will add all branches (related or
253 : // unrelated) and ensure the superproject's branches get added first before
254 : // a submodule branch. Need remove all unrelated branches and reverse
255 : // the order.
256 69 : allVisited.retainAll(affectedBranches);
257 69 : reverse(allVisited);
258 69 : return allVisited;
259 : }
260 :
261 : private void searchForSuperprojects(
262 : BranchNameKey current,
263 : LinkedHashSet<BranchNameKey> currentVisited,
264 : LinkedHashSet<BranchNameKey> allVisited,
265 : Set<BranchNameKey> affectedBranches,
266 : SetMultimap<BranchNameKey, SubmoduleSubscription> targets,
267 : SetMultimap<Project.NameKey, BranchNameKey> branchesByProject,
268 : Set<BranchNameKey> subscribedBranches,
269 : Map<BranchNameKey, GitModules> branchGitModules,
270 : MergeOpRepoManager orm)
271 : throws SubmoduleConflictException {
272 69 : logger.atFine().log("Now processing %s", current);
273 :
274 69 : if (currentVisited.contains(current)) {
275 3 : throw new SubmoduleConflictException(
276 : "Branch level circular subscriptions detected: "
277 3 : + CircularPathFinder.printCircularPath(currentVisited, current));
278 : }
279 :
280 69 : if (allVisited.contains(current)) {
281 3 : return;
282 : }
283 :
284 69 : currentVisited.add(current);
285 : try {
286 69 : Collection<SubmoduleSubscription> subscriptions =
287 69 : superProjectSubscriptionsForSubmoduleBranch(current, branchGitModules, orm);
288 69 : for (SubmoduleSubscription sub : subscriptions) {
289 3 : BranchNameKey superBranch = sub.getSuperProject();
290 3 : searchForSuperprojects(
291 : superBranch,
292 : currentVisited,
293 : allVisited,
294 : affectedBranches,
295 : targets,
296 : branchesByProject,
297 : subscribedBranches,
298 : branchGitModules,
299 : orm);
300 3 : targets.put(superBranch, sub);
301 3 : branchesByProject.put(superBranch.project(), superBranch);
302 3 : affectedBranches.add(superBranch);
303 3 : affectedBranches.add(sub.getSubmodule());
304 3 : subscribedBranches.add(sub.getSubmodule());
305 3 : }
306 0 : } catch (IOException e) {
307 0 : throw new StorageException("Cannot find superprojects for " + current, e);
308 69 : }
309 69 : currentVisited.remove(current);
310 69 : allVisited.add(current);
311 69 : }
312 :
313 : private Collection<BranchNameKey> getDestinationBranches(
314 : BranchNameKey src, SubscribeSection s, MergeOpRepoManager orm) throws IOException {
315 : OpenRepo or;
316 : try {
317 3 : or = orm.getRepo(s.project());
318 1 : } catch (NoSuchProjectException e) {
319 : // A project listed a non existent project to be allowed
320 : // to subscribe to it. Allow this for now, i.e. no exception is
321 : // thrown.
322 1 : return s.getDestinationBranches(src, ImmutableList.of());
323 3 : }
324 :
325 3 : List<Ref> refs = or.repo.getRefDatabase().getRefsByPrefix(RefNames.REFS_HEADS);
326 3 : return s.getDestinationBranches(src, refs);
327 : }
328 :
329 : private Collection<SubmoduleSubscription> superProjectSubscriptionsForSubmoduleBranch(
330 : BranchNameKey srcBranch,
331 : Map<BranchNameKey, GitModules> branchGitModules,
332 : MergeOpRepoManager orm)
333 : throws IOException {
334 69 : Collection<SubmoduleSubscription> ret = new ArrayList<>();
335 69 : if (RefNames.isGerritRef(srcBranch.branch())) return ret;
336 :
337 66 : Project.NameKey srcProject = srcBranch.project();
338 : for (SubscribeSection s :
339 : projectCache
340 66 : .get(srcProject)
341 66 : .orElseThrow(illegalState(srcProject))
342 66 : .getSubscribeSections(srcBranch)) {
343 3 : Collection<BranchNameKey> branches = getDestinationBranches(srcBranch, s, orm);
344 3 : for (BranchNameKey targetBranch : branches) {
345 3 : Project.NameKey targetProject = targetBranch.project();
346 : try {
347 3 : OpenRepo or = orm.getRepo(targetProject);
348 3 : ObjectId id = or.repo.resolve(targetBranch.branch());
349 3 : if (id == null) {
350 1 : logger.atFine().log("SubscribeSection %s: branch %s doesn't exist.", s, targetBranch);
351 1 : continue;
352 : }
353 1 : } catch (NoSuchProjectException e) {
354 1 : logger.atFine().log("SubscribeSection %s: project %s doesn't exist", s, targetProject);
355 1 : continue;
356 3 : }
357 :
358 3 : GitModules m = branchGitModules.get(targetBranch);
359 3 : if (m == null) {
360 3 : m = gitmodulesFactory.create(targetBranch, orm);
361 3 : branchGitModules.put(targetBranch, m);
362 : }
363 3 : ret.addAll(m.subscribedTo(srcBranch));
364 3 : }
365 3 : }
366 66 : logger.atFine().log("Calculated superprojects for %s are %s", srcBranch, ret);
367 66 : return ret;
368 : }
369 :
370 : private static <T> void reverse(LinkedHashSet<T> set) {
371 69 : if (set == null) {
372 0 : return;
373 : }
374 :
375 69 : Deque<T> q = new ArrayDeque<>(set);
376 69 : set.clear();
377 :
378 69 : while (!q.isEmpty()) {
379 3 : set.add(q.removeLast());
380 : }
381 69 : }
382 : }
383 : }
|
