Fix infinite loops when walking project hierarchy Always walk up the tree using a special iterator that knows how to track visited project names and breaks any cycle, ensuring All-Projects is always reached. Change-Id: Ib6ad9505b3225bfa40ba067c799ce18130eafd29
diff --git a/gerrit-httpd/src/main/java/com/google/gerrit/httpd/rpc/project/ProjectDetailFactory.java b/gerrit-httpd/src/main/java/com/google/gerrit/httpd/rpc/project/ProjectDetailFactory.java index 0e9c9fd..2533feb 100644 --- a/gerrit-httpd/src/main/java/com/google/gerrit/httpd/rpc/project/ProjectDetailFactory.java +++ b/gerrit-httpd/src/main/java/com/google/gerrit/httpd/rpc/project/ProjectDetailFactory.java
@@ -14,6 +14,7 @@ package com.google.gerrit.httpd.rpc.project; +import com.google.common.collect.Iterables; import com.google.gerrit.common.data.ProjectDetail; import com.google.gerrit.httpd.rpc.Handler; import com.google.gerrit.reviewdb.client.InheritedBoolean; @@ -78,7 +79,7 @@ useSignedOffBy.setValue(projectState.getProject().getUseSignedOffBy()); useContentMerge.setValue(projectState.getProject().getUseContentMerge()); requireChangeID.setValue(projectState.getProject().getRequireChangeID()); - final ProjectState parentState = projectState.getParentState(); + ProjectState parentState = Iterables.getFirst(projectState.parents(), null); if (parentState != null) { useContributorAgreements.setInheritedValue(parentState .isUseContributorAgreements());
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/mail/ChangeEmail.java b/gerrit-server/src/main/java/com/google/gerrit/server/mail/ChangeEmail.java index 2fcdb2c..e05f71c 100644 --- a/gerrit-server/src/main/java/com/google/gerrit/server/mail/ChangeEmail.java +++ b/gerrit-server/src/main/java/com/google/gerrit/server/mail/ChangeEmail.java
@@ -375,8 +375,7 @@ } } - ProjectState state = projectState; - while (state != null) { + for (ProjectState state : projectState.tree()) { for (NotifyConfig nc : state.getConfig().getNotifyConfigs()) { if (nc.isNotify(type)) { try { @@ -389,7 +388,6 @@ } } } - state = state.getParentState(); } return matching;
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/project/DashboardsCollection.java b/gerrit-server/src/main/java/com/google/gerrit/server/project/DashboardsCollection.java index 22c3007..ee4ffc6 100644 --- a/gerrit-server/src/main/java/com/google/gerrit/server/project/DashboardsCollection.java +++ b/gerrit-server/src/main/java/com/google/gerrit/server/project/DashboardsCollection.java
@@ -21,7 +21,6 @@ import com.google.common.base.Splitter; import com.google.common.base.Strings; import com.google.common.collect.Lists; -import com.google.common.collect.Sets; import com.google.gerrit.extensions.registration.DynamicMap; import com.google.gerrit.extensions.restapi.AcceptsCreate; import com.google.gerrit.extensions.restapi.ChildCollection; @@ -30,6 +29,7 @@ import com.google.gerrit.extensions.restapi.RestModifyView; import com.google.gerrit.extensions.restapi.RestView; import com.google.gerrit.reviewdb.client.Project; +import com.google.gerrit.server.CurrentUser; import com.google.gerrit.server.UrlEncoded; import com.google.gerrit.server.git.GitRepositoryManager; import com.google.gerrit.server.util.Url; @@ -49,7 +49,6 @@ import java.io.IOException; import java.io.UnsupportedEncodingException; import java.util.List; -import java.util.Set; class DashboardsCollection implements ChildCollection<ProjectResource, DashboardResource>, @@ -99,13 +98,12 @@ throw new ResourceNotFoundException(id); } + CurrentUser user = myCtl.getCurrentUser(); String ref = Url.decode(parts.get(0)); String path = Url.decode(parts.get(1)); - ProjectControl ctl = myCtl; - Set<Project.NameKey> seen = Sets.newHashSet(ctl.getProject().getNameKey()); - for (;;) { + for (ProjectState ps : myCtl.getProjectState().tree()) { try { - return parse(ctl, ref, path, myCtl); + return parse(ps.controlFor(user), ref, path, myCtl); } catch (AmbiguousObjectException e) { throw new ResourceNotFoundException(id); } catch (IncorrectObjectTypeException e) { @@ -113,14 +111,10 @@ } catch (ConfigInvalidException e) { throw new ResourceNotFoundException(id); } catch (ResourceNotFoundException e) { - ProjectState ps = ctl.getProjectState().getParentState(); - if (ps != null && seen.add(ps.getProject().getNameKey())) { - ctl = ps.controlFor(ctl.getCurrentUser()); - continue; - } throw new ResourceNotFoundException(id); } } + throw new ResourceNotFoundException(id); } private DashboardResource parse(ProjectControl ctl, String ref, String path,
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/project/GetDashboard.java b/gerrit-server/src/main/java/com/google/gerrit/server/project/GetDashboard.java index 77a4de05..72b9de6 100644 --- a/gerrit-server/src/main/java/com/google/gerrit/server/project/GetDashboard.java +++ b/gerrit-server/src/main/java/com/google/gerrit/server/project/GetDashboard.java
@@ -17,10 +17,8 @@ import static com.google.gerrit.server.git.GitRepositoryManager.REFS_DASHBOARDS; import com.google.common.base.Strings; -import com.google.common.collect.Sets; import com.google.gerrit.extensions.restapi.ResourceNotFoundException; import com.google.gerrit.extensions.restapi.RestReadView; -import com.google.gerrit.reviewdb.client.Project; import com.google.gerrit.server.project.DashboardsCollection.DashboardInfo; import com.google.inject.Inject; @@ -28,7 +26,6 @@ import org.kohsuke.args4j.Option; import java.io.IOException; -import java.util.Set; class GetDashboard implements RestReadView<DashboardResource> { private final DashboardsCollection dashboards; @@ -78,10 +75,7 @@ throw new ResourceNotFoundException(); } - Set<Project.NameKey> seen = Sets.newHashSet(); - seen.add(ctl.getProject().getNameKey()); - ProjectState ps = ctl.getProjectState().getParentState(); - while (ps != null && seen.add(ps.getProject().getNameKey())) { + for (ProjectState ps : ctl.getProjectState().tree()) { id = ps.getProject().getDefaultDashboard(); if ("default".equals(id)) { throw new ResourceNotFoundException(); @@ -89,7 +83,6 @@ ctl = ps.controlFor(ctl.getCurrentUser()); return dashboards.parse(new ProjectResource(ctl), id); } - ps = ps.getParentState(); } throw new ResourceNotFoundException(); }
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/project/ListDashboards.java b/gerrit-server/src/main/java/com/google/gerrit/server/project/ListDashboards.java index 429007d..c063618 100644 --- a/gerrit-server/src/main/java/com/google/gerrit/server/project/ListDashboards.java +++ b/gerrit-server/src/main/java/com/google/gerrit/server/project/ListDashboards.java
@@ -17,7 +17,6 @@ import static com.google.gerrit.server.git.GitRepositoryManager.REFS_DASHBOARDS; import com.google.common.collect.Lists; -import com.google.common.collect.Sets; import com.google.gerrit.extensions.restapi.ResourceNotFoundException; import com.google.gerrit.extensions.restapi.RestReadView; import com.google.gerrit.reviewdb.client.Project; @@ -39,7 +38,6 @@ import java.io.IOException; import java.util.List; -import java.util.Set; class ListDashboards implements RestReadView<ProjectResource> { private static final Logger log = LoggerFactory.getLogger(DashboardsCollection.class); @@ -57,16 +55,16 @@ @Override public Object apply(ProjectResource resource) throws ResourceNotFoundException, IOException { - ProjectControl ctl = resource.getControl(); + ProjectControl ctl = resource.getControl(); String project = ctl.getProject().getName(); if (!inherited) { return scan(resource.getControl(), project, true); } List<List<DashboardInfo>> all = Lists.newArrayList(); - Set<Project.NameKey> seen = Sets.newHashSet(); boolean setDefault = true; - for (;;) { + for (ProjectState ps : ctl.getProjectState().tree()) { + ctl = ps.controlFor(ctl.getCurrentUser()); if (ctl.isVisible()) { List<DashboardInfo> list = scan(ctl, project, setDefault); for (DashboardInfo d : list) { @@ -78,12 +76,6 @@ all.add(list); } } - - ProjectState ps = ctl.getProjectState().getParentState(); - if (ps == null || !seen.add(ps.getProject().getNameKey())) { - break; - } - ctl = ps.controlFor(ctl.getCurrentUser()); } return all; }
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/project/ListProjects.java b/gerrit-server/src/main/java/com/google/gerrit/server/project/ListProjects.java index 001a0c3..405b1d4 100644 --- a/gerrit-server/src/main/java/com/google/gerrit/server/project/ListProjects.java +++ b/gerrit-server/src/main/java/com/google/gerrit/server/project/ListProjects.java
@@ -239,7 +239,7 @@ ProjectInfo info = new ProjectInfo(); if (type == FilterType.PARENT_CANDIDATES) { - ProjectState parentState = e.getParentState(); + ProjectState parentState = Iterables.getFirst(e.parents(), null); if (parentState != null && !output.keySet().contains(parentState.getProject().getName()) && !rejected.contains(parentState.getProject().getName())) { @@ -272,7 +272,7 @@ info.setName(projectName.get()); if (showTree && format.isJson()) { - ProjectState parent = e.getParentState(); + ProjectState parent = Iterables.getFirst(e.parents(), null); if (parent != null) { ProjectControl parentCtrl = parent.controlFor(currentUser); if (parentCtrl.isVisible() || parentCtrl.isOwner()) {
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/project/ProjectHierarchyIterator.java b/gerrit-server/src/main/java/com/google/gerrit/server/project/ProjectHierarchyIterator.java new file mode 100644 index 0000000..0724ce9 --- /dev/null +++ b/gerrit-server/src/main/java/com/google/gerrit/server/project/ProjectHierarchyIterator.java
@@ -0,0 +1,107 @@ +// Copyright (C) 2013 The Android Open Source Project +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +package com.google.gerrit.server.project; + +import com.google.common.base.Joiner; +import com.google.common.collect.Lists; +import com.google.common.collect.Sets; +import com.google.gerrit.reviewdb.client.Project; +import com.google.gerrit.server.config.AllProjectsName; + +import org.slf4j.Logger; +import org.slf4j.LoggerFactory; + +import java.util.Iterator; +import java.util.List; +import java.util.NoSuchElementException; +import java.util.Set; + +/** + * Iterates from a project up through its parents to All-Projects. + * <p> + * If a cycle is detected the cycle is broken and All-Projects is visited. + */ +class ProjectHierarchyIterator implements Iterator<ProjectState> { + private static final Logger log = LoggerFactory.getLogger(ProjectHierarchyIterator.class); + + private final ProjectCache cache; + private final AllProjectsName allProjectsName; + private final Set<Project.NameKey> seen; + private ProjectState next; + + ProjectHierarchyIterator(ProjectCache c, + AllProjectsName all, + ProjectState firstResult) { + cache = c; + allProjectsName = all; + + seen = Sets.newLinkedHashSet(); + seen.add(firstResult.getProject().getNameKey()); + next = firstResult; + } + + @Override + public boolean hasNext() { + return next != null; + } + + @Override + public ProjectState next() { + ProjectState n = next; + if (n == null) { + throw new NoSuchElementException(); + } + next = computeNext(n); + return n; + } + + private ProjectState computeNext(ProjectState n) { + Project.NameKey parentName = n.getProject().getParent(); + if (parentName != null && visit(parentName)) { + ProjectState p = cache.get(parentName); + if (p != null) { + return p; + } + } + + // Parent does not exist or was already visited. + // Fall back to visit All-Projects exactly once. + if (seen.add(allProjectsName)) { + return cache.get(allProjectsName); + } + return null; + } + + private boolean visit(Project.NameKey parentName) { + if (seen.add(parentName)) { + return true; + } + + List<String> order = Lists.newArrayListWithCapacity(seen.size() + 1); + for (Project.NameKey p : seen) { + order.add(p.get()); + } + int idx = order.lastIndexOf(parentName.get()); + order.add(parentName.get()); + log.warn("Cycle detected in projects: " + + Joiner.on(" -> ").join(order.subList(idx, order.size()))); + return false; + } + + @Override + public void remove() { + throw new UnsupportedOperationException(); + } +}
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/project/ProjectState.java b/gerrit-server/src/main/java/com/google/gerrit/server/project/ProjectState.java index 7523d75..413cbeb 100644 --- a/gerrit-server/src/main/java/com/google/gerrit/server/project/ProjectState.java +++ b/gerrit-server/src/main/java/com/google/gerrit/server/project/ProjectState.java
@@ -15,8 +15,9 @@ package com.google.gerrit.server.project; import com.google.common.base.Function; +import com.google.common.base.Predicate; +import com.google.common.collect.Iterables; import com.google.common.collect.Lists; -import com.google.common.collect.Sets; import com.google.gerrit.common.data.AccessSection; import com.google.gerrit.common.data.GroupReference; import com.google.gerrit.common.data.Permission; @@ -47,6 +48,7 @@ import java.util.Collection; import java.util.Collections; import java.util.HashSet; +import java.util.Iterator; import java.util.List; import java.util.Set; @@ -230,23 +232,9 @@ return getLocalAccessSections(); } - List<SectionMatcher> all = new ArrayList<SectionMatcher>(); - Set<Project.NameKey> seen = new HashSet<Project.NameKey>(); - ProjectState allProjects = projectCache.getAllProjects(); - seen.add(getProject().getNameKey()); - - ProjectState s = this; - do { + List<SectionMatcher> all = Lists.newArrayList(); + for (ProjectState s : tree()) { all.addAll(s.getLocalAccessSections()); - - Project.NameKey parent = s.getProject().getParent(); - if (parent == null || !seen.add(parent)) { - break; - } - s = projectCache.get(parent); - } while (s != null); - if (seen.add(allProjects.getProject().getNameKey())) { - all.addAll(allProjects.getLocalAccessSections()); } return all; } @@ -258,16 +246,11 @@ * that has local owners are returned */ public Set<AccountGroup.UUID> getOwners() { - Project.NameKey parentName = getProject().getParent(); - if (!localOwners.isEmpty() || parentName == null || isAllProjects) { - return localOwners; + for (ProjectState p : tree()) { + if (!p.localOwners.isEmpty()) { + return p.localOwners; + } } - - ProjectState parent = projectCache.get(parentName); - if (parent != null) { - return parent.getOwners(); - } - return Collections.emptySet(); } @@ -275,23 +258,13 @@ * @return true if any of the groups listed in {@code groups} was declared to * be an owner of this project, or one of its parent projects.. */ - boolean isOwner(GroupMembership groups) { - Set<Project.NameKey> seen = new HashSet<Project.NameKey>(); - seen.add(getProject().getNameKey()); - - ProjectState s = this; - do { - if (groups.containsAnyOf(s.localOwners)) { - return true; + boolean isOwner(final GroupMembership groups) { + return Iterables.any(tree(), new Predicate<ProjectState>() { + @Override + public boolean apply(ProjectState in) { + return groups.containsAnyOf(in.localOwners); } - - Project.NameKey parent = s.getProject().getParent(); - if (parent == null || !seen.add(parent)) { - break; - } - s = projectCache.get(parent); - } while (s != null); - return false; + }); } public ProjectControl controlFor(final CurrentUser user) { @@ -299,15 +272,28 @@ } /** - * @return ProjectState of project's parent. If the project does not have a - * parent, return state of the top level project, All-Projects. If - * this project is All-Projects, return null. + * @return an iterable that walks through this project and then the parents of + * this project. Starts from this project and progresses up the + * hierarchy to All-Projects. */ - public ProjectState getParentState() { - if (isAllProjects) { - return null; - } - return projectCache.get(getProject().getParent(allProjectsName)); + public Iterable<ProjectState> tree() { + return new Iterable<ProjectState>() { + @Override + public Iterator<ProjectState> iterator() { + return new ProjectHierarchyIterator( + projectCache, allProjectsName, + ProjectState.this); + } + }; + } + + /** + * @return an iterable that walks through the parents of this project. Starts + * from the immediate parent of this project and progresses up the + * hierarchy to All-Projects. + */ + public Iterable<ProjectState> parents() { + return Iterables.skip(tree(), 1); } public boolean isAllProjects() { @@ -351,10 +337,7 @@ } private boolean getInheritableBoolean(Function<Project, InheritableBoolean> func) { - Set<Project.NameKey> seen = Sets.newHashSet(); - seen.add(getProject().getNameKey()); - ProjectState s = this; - do { + for (ProjectState s : tree()) { switch (func.apply(s.getProject())) { case TRUE: return true; @@ -362,14 +345,9 @@ return false; case INHERIT: default: - Project.NameKey parent = s.getProject().getParent(allProjectsName); - if (parent != null && seen.add(parent)) { - s = projectCache.get(parent); - } else { - s = null; - } + continue; } - } while (s != null); + } return false; } } \ No newline at end of file
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/project/SubmitRuleEvaluator.java b/gerrit-server/src/main/java/com/google/gerrit/server/project/SubmitRuleEvaluator.java index c99e3ac..bcea2c9 100644 --- a/gerrit-server/src/main/java/com/google/gerrit/server/project/SubmitRuleEvaluator.java +++ b/gerrit-server/src/main/java/com/google/gerrit/server/project/SubmitRuleEvaluator.java
@@ -16,7 +16,6 @@ import com.google.gerrit.reviewdb.client.Change; import com.google.gerrit.reviewdb.client.PatchSet; -import com.google.gerrit.reviewdb.client.Project; import com.google.gerrit.reviewdb.server.ReviewDb; import com.google.gerrit.rules.PrologEnvironment; import com.google.gerrit.rules.StoredValues; @@ -31,9 +30,7 @@ import java.io.InputStream; import java.util.ArrayList; -import java.util.HashSet; import java.util.List; -import java.util.Set; import javax.annotation.Nullable; @@ -184,16 +181,8 @@ private Term runSubmitFilters(Term results, PrologEnvironment env) throws RuleEvalException { ProjectState projectState = projectControl.getProjectState(); - ProjectState parentState = projectState.getParentState(); PrologEnvironment childEnv = env; - Set<Project.NameKey> projectsSeen = new HashSet<Project.NameKey>(); - projectsSeen.add(projectState.getProject().getNameKey()); - - while (parentState != null) { - if (!projectsSeen.add(parentState.getProject().getNameKey())) { - // parent has been seen before, stop walk up inheritance tree - break; - } + for (ProjectState parentState : projectState.parents()) { PrologEnvironment parentEnv; try { parentEnv = parentState.newPrologEnvironment(); @@ -223,11 +212,8 @@ + " on change " + change.getId() + " of " + parentState.getProject().getName(), err); } - - parentState = parentState.getParentState(); childEnv = parentEnv; } - return results; }
diff --git a/gerrit-sshd/src/main/java/com/google/gerrit/sshd/commands/AdminSetParent.java b/gerrit-sshd/src/main/java/com/google/gerrit/sshd/commands/AdminSetParent.java index 6483e24..4697bd6 100644 --- a/gerrit-sshd/src/main/java/com/google/gerrit/sshd/commands/AdminSetParent.java +++ b/gerrit-sshd/src/main/java/com/google/gerrit/sshd/commands/AdminSetParent.java
@@ -14,6 +14,9 @@ package com.google.gerrit.sshd.commands; +import com.google.common.base.Function; +import com.google.common.collect.ImmutableSet; +import com.google.common.collect.Iterables; import com.google.gerrit.common.data.GlobalCapability; import com.google.gerrit.extensions.annotations.RequiresCapability; import com.google.gerrit.reviewdb.client.Project; @@ -35,6 +38,7 @@ import java.io.IOException; import java.util.ArrayList; +import java.util.Collections; import java.util.HashSet; import java.util.List; import java.util.Set; @@ -197,17 +201,15 @@ } private Set<Project.NameKey> getAllParents(final Project.NameKey projectName) { - final Set<Project.NameKey> parents = new HashSet<Project.NameKey>(); - Project.NameKey p = projectName; - while (p != null && parents.add(p)) { - final ProjectState e = projectCache.get(p); - if (e == null) { - // If we can't get it from the cache, pretend it's not present. - break; - } - p = e.getProject().getParent(allProjectsName); - } - return parents; + ProjectState ps = projectCache.get(projectName); + return ImmutableSet.copyOf(Iterables.transform( + ps != null ? ps.parents() : Collections.<ProjectState> emptySet(), + new Function<ProjectState, Project.NameKey> () { + @Override + public Project.NameKey apply(ProjectState in) { + return in.getProject().getNameKey(); + } + })); } private List<Project> getChildren(final Project.NameKey parentName) {