java/com/google/gerrit/server/change/RelatedChangesSorter.java - gerrit - Git at Google

 // Copyright (C) 2015 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.change;

 import static com.google.common.base.Preconditions.checkArgument;
 import static java.util.Objects.requireNonNull;
 import static java.util.stream.Collectors.toMap;

 import com.google.auto.value.AutoValue;
 import com.google.auto.value.extension.memoized.Memoized;
 import com.google.common.annotations.VisibleForTesting;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ListMultimap;
 import com.google.common.collect.Lists;
 import com.google.common.collect.Maps;
 import com.google.common.collect.MultimapBuilder;
 import com.google.gerrit.entities.Change;
 import com.google.gerrit.entities.PatchSet;
 import com.google.gerrit.entities.Project;
 import com.google.gerrit.server.git.GitRepositoryManager;
 import com.google.gerrit.server.permissions.ChangePermission;
 import com.google.gerrit.server.permissions.PermissionBackend;
 import com.google.gerrit.server.permissions.PermissionBackendException;
 import com.google.gerrit.server.project.ProjectCache;
 import com.google.gerrit.server.project.ProjectState;
 import com.google.gerrit.server.query.change.ChangeData;
 import com.google.inject.Inject;
 import com.google.inject.Singleton;
 import java.io.IOException;
 import java.util.ArrayDeque;
 import java.util.ArrayList;
 import java.util.Collection;
 import java.util.Deque;
 import java.util.HashMap;
 import java.util.HashSet;
 import java.util.LinkedHashSet;
 import java.util.List;
 import java.util.Map;
 import java.util.Objects;
 import java.util.Set;
 import org.eclipse.jgit.lib.ObjectId;
 import org.eclipse.jgit.lib.Repository;
 import org.eclipse.jgit.revwalk.RevCommit;
 import org.eclipse.jgit.revwalk.RevWalk;

 @Singleton
 public class RelatedChangesSorter {
   private final GitRepositoryManager repoManager;
   private final PermissionBackend permissionBackend;
   private final ProjectCache projectCache;

   @Inject
   RelatedChangesSorter(
       GitRepositoryManager repoManager,
       PermissionBackend permissionBackend,
       ProjectCache projectCache) {
     this.repoManager = repoManager;
     this.permissionBackend = permissionBackend;
     this.projectCache = projectCache;
   }

   public List<PatchSetData> sort(List<ChangeData> in, PatchSet startPs)
       throws IOException, PermissionBackendException {
     checkArgument(!in.isEmpty(), "Input may not be empty");
     // Map of all patch sets, keyed by commit SHA-1.
     Map<ObjectId, PatchSetData> byId = collectById(in);
     PatchSetData start = byId.get(startPs.commitId());
     requireNonNull(
         start,
         () ->
             String.format(
                 "commit %s of patch set %s not found in %s",
                 startPs.commitId().name(),
                 startPs.id(),
                 byId.entrySet().stream()
                     .collect(toMap(e -> e.getKey().name(), e -> e.getValue().patchSet().id()))));

     // Map of patch set -> immediate parent.
     ListMultimap<PatchSetData, PatchSetData> parents =
         MultimapBuilder.hashKeys(in.size()).arrayListValues(3).build();
     // Map of patch set -> immediate children.
     ListMultimap<PatchSetData, PatchSetData> children =
         MultimapBuilder.hashKeys(in.size()).arrayListValues(3).build();
     // All other patch sets of the same change as startPs.
     List<PatchSetData> otherPatchSetsOfStart = new ArrayList<>();

     for (ChangeData cd : in) {
       for (PatchSet ps : cd.patchSets()) {
         PatchSetData thisPsd = requireNonNull(byId.get(ps.commitId()));
         if (cd.getId().equals(start.id()) && !ps.id().equals(start.psId())) {
           otherPatchSetsOfStart.add(thisPsd);
         }
         for (RevCommit p : thisPsd.commit().getParents()) {
           PatchSetData parentPsd = byId.get(p);
           if (parentPsd != null) {
             parents.put(thisPsd, parentPsd);
             children.put(parentPsd, thisPsd);
           }
         }
       }
     }

     Collection<PatchSetData> ancestors = walkAncestors(parents, start);
     List<PatchSetData> descendants =
         walkDescendants(children, start, otherPatchSetsOfStart, ancestors);
     List<PatchSetData> result = new ArrayList<>(ancestors.size() + descendants.size() - 1);
     result.addAll(Lists.reverse(descendants));
     result.addAll(ancestors);
     return result;
   }

   private Map<ObjectId, PatchSetData> collectById(List<ChangeData> in) throws IOException {
     Project.NameKey project = in.get(0).change().getProject();
     Map<ObjectId, PatchSetData> result = Maps.newHashMapWithExpectedSize(in.size() * 3);
     try (Repository repo = repoManager.openRepository(project);
         RevWalk rw = new RevWalk(repo)) {
       rw.setRetainBody(true);
       for (ChangeData cd : in) {
         checkArgument(
             cd.change().getProject().equals(project),
             "Expected change %s in project %s, found %s",
             cd.getId(),
             project,
             cd.change().getProject());
         for (PatchSet ps : cd.patchSets()) {
           RevCommit c = rw.parseCommit(ps.commitId());
           PatchSetData psd = PatchSetData.create(cd, ps, c);
           result.put(ps.commitId(), psd);
         }
       }
     }
     return result;
   }

   private Collection<PatchSetData> walkAncestors(
       ListMultimap<PatchSetData, PatchSetData> parents, PatchSetData start)
       throws PermissionBackendException {
     LinkedHashSet<PatchSetData> result = new LinkedHashSet<>();
     Deque<PatchSetData> pending = new ArrayDeque<>();
     pending.add(start);
     while (!pending.isEmpty()) {
       PatchSetData psd = pending.remove();
       if (result.contains(psd) || !isVisible(psd)) {
         continue;
       }
       result.add(psd);
       pending.addAll(Lists.reverse(parents.get(psd)));
     }
     return result;
   }

   private List<PatchSetData> walkDescendants(
       ListMultimap<PatchSetData, PatchSetData> children,
       PatchSetData start,
       List<PatchSetData> otherPatchSetsOfStart,
       Iterable<PatchSetData> ancestors)
       throws PermissionBackendException {
     Set<Change.Id> alreadyEmittedChanges = new HashSet<>();
     addAllChangeIds(alreadyEmittedChanges, ancestors);

     // Prefer descendants found by following the original patch set passed in.
     List<PatchSetData> result =
         walkDescendentsImpl(alreadyEmittedChanges, children, ImmutableList.of(start));
     addAllChangeIds(alreadyEmittedChanges, result);

     // Then, go back and add new indirect descendants found by following any
     // other patch sets of start. These show up after all direct descendants,
     // because we wouldn't know where in the walk to insert them.
     result.addAll(walkDescendentsImpl(alreadyEmittedChanges, children, otherPatchSetsOfStart));
     return result;
   }

   private static void addAllChangeIds(
       Collection<Change.Id> changeIds, Iterable<PatchSetData> psds) {
     for (PatchSetData psd : psds) {
       changeIds.add(psd.id());
     }
   }

   private List<PatchSetData> walkDescendentsImpl(
       Set<Change.Id> alreadyEmittedChanges,
       ListMultimap<PatchSetData, PatchSetData> children,
       List<PatchSetData> start)
       throws PermissionBackendException {
     if (start.isEmpty()) {
       return new ArrayList<>();
     }
     Map<Change.Id, PatchSet.Id> maxPatchSetIds = new HashMap<>();
     Set<PatchSetData> seen = new HashSet<>();
     List<PatchSetData> allPatchSets = new ArrayList<>();
     Deque<PatchSetData> pending = new ArrayDeque<>();
     pending.addAll(start);
     while (!pending.isEmpty()) {
       PatchSetData psd = pending.remove();
       if (seen.contains(psd) || !isVisible(psd)) {
         continue;
       }
       seen.add(psd);
       if (!alreadyEmittedChanges.contains(psd.id())) {
         // Don't emit anything for changes that were previously emitted, even
         // though different patch sets might show up later. However, do
         // continue walking through them for the purposes of finding indirect
         // descendants.
         PatchSet.Id oldMax = maxPatchSetIds.get(psd.id());
         if (oldMax == null || psd.psId().get() > oldMax.get()) {
           maxPatchSetIds.put(psd.id(), psd.psId());
         }
         allPatchSets.add(psd);
       }
       // Depth-first search with newest children first.
       for (PatchSetData child : children.get(psd)) {
         pending.addFirst(child);
       }
     }

     // If we saw the same change multiple times, prefer the latest patch set.
     List<PatchSetData> result = new ArrayList<>(allPatchSets.size());
     for (PatchSetData psd : allPatchSets) {
       if (requireNonNull(maxPatchSetIds.get(psd.id())).equals(psd.psId())) {
         result.add(psd);
       }
     }
     return result;
   }

   private boolean isVisible(PatchSetData psd) throws PermissionBackendException {
     PermissionBackend.WithUser perm = permissionBackend.currentUser();
     return perm.change(psd.data()).test(ChangePermission.READ)
         && projectCache.get(psd.data().project()).map(ProjectState::statePermitsRead).orElse(false);
   }

   @AutoValue
   public abstract static class PatchSetData {
     @VisibleForTesting
     static PatchSetData create(ChangeData cd, PatchSet ps, RevCommit commit) {
       return new AutoValue_RelatedChangesSorter_PatchSetData(cd, ps, commit);
     }

     public abstract ChangeData data();

     public abstract PatchSet patchSet();

     public abstract RevCommit commit();

     public PatchSet.Id psId() {
       return patchSet().id();
     }

     public Change.Id id() {
       return psId().changeId();
     }

     @Memoized
     @Override
     public int hashCode() {
       return Objects.hash(patchSet().id(), commit());
     }

     @Override
     public final boolean equals(Object obj) {
       if (!(obj instanceof PatchSetData)) {
         return false;
       }
       PatchSetData o = (PatchSetData) obj;
       return Objects.equals(patchSet().id(), o.patchSet().id())
           && Objects.equals(commit(), o.commit());
     }
   }
 }
	// Copyright (C) 2015 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.change;

	import static com.google.common.base.Preconditions.checkArgument;
	import static java.util.Objects.requireNonNull;
	import static java.util.stream.Collectors.toMap;

	import com.google.auto.value.AutoValue;
	import com.google.auto.value.extension.memoized.Memoized;
	import com.google.common.annotations.VisibleForTesting;
	import com.google.common.collect.ImmutableList;
	import com.google.common.collect.ListMultimap;
	import com.google.common.collect.Lists;
	import com.google.common.collect.Maps;
	import com.google.common.collect.MultimapBuilder;
	import com.google.gerrit.entities.Change;
	import com.google.gerrit.entities.PatchSet;
	import com.google.gerrit.entities.Project;
	import com.google.gerrit.server.git.GitRepositoryManager;
	import com.google.gerrit.server.permissions.ChangePermission;
	import com.google.gerrit.server.permissions.PermissionBackend;
	import com.google.gerrit.server.permissions.PermissionBackendException;
	import com.google.gerrit.server.project.ProjectCache;
	import com.google.gerrit.server.project.ProjectState;
	import com.google.gerrit.server.query.change.ChangeData;
	import com.google.inject.Inject;
	import com.google.inject.Singleton;
	import java.io.IOException;
	import java.util.ArrayDeque;
	import java.util.ArrayList;
	import java.util.Collection;
	import java.util.Deque;
	import java.util.HashMap;
	import java.util.HashSet;
	import java.util.LinkedHashSet;
	import java.util.List;
	import java.util.Map;
	import java.util.Objects;
	import java.util.Set;
	import org.eclipse.jgit.lib.ObjectId;
	import org.eclipse.jgit.lib.Repository;
	import org.eclipse.jgit.revwalk.RevCommit;
	import org.eclipse.jgit.revwalk.RevWalk;

	@Singleton
	public class RelatedChangesSorter {
	private final GitRepositoryManager repoManager;
	private final PermissionBackend permissionBackend;
	private final ProjectCache projectCache;

	@Inject
	RelatedChangesSorter(
	GitRepositoryManager repoManager,
	PermissionBackend permissionBackend,
	ProjectCache projectCache) {
	this.repoManager = repoManager;
	this.permissionBackend = permissionBackend;
	this.projectCache = projectCache;
	}

	public List<PatchSetData> sort(List<ChangeData> in, PatchSet startPs)
	throws IOException, PermissionBackendException {
	checkArgument(!in.isEmpty(), "Input may not be empty");
	// Map of all patch sets, keyed by commit SHA-1.
	Map<ObjectId, PatchSetData> byId = collectById(in);
	PatchSetData start = byId.get(startPs.commitId());
	requireNonNull(
	start,
	() ->
	String.format(
	"commit %s of patch set %s not found in %s",
	startPs.commitId().name(),
	startPs.id(),
	byId.entrySet().stream()
	.collect(toMap(e -> e.getKey().name(), e -> e.getValue().patchSet().id()))));

	// Map of patch set -> immediate parent.
	ListMultimap<PatchSetData, PatchSetData> parents =
	MultimapBuilder.hashKeys(in.size()).arrayListValues(3).build();
	// Map of patch set -> immediate children.
	ListMultimap<PatchSetData, PatchSetData> children =
	MultimapBuilder.hashKeys(in.size()).arrayListValues(3).build();
	// All other patch sets of the same change as startPs.
	List<PatchSetData> otherPatchSetsOfStart = new ArrayList<>();

	for (ChangeData cd : in) {
	for (PatchSet ps : cd.patchSets()) {
	PatchSetData thisPsd = requireNonNull(byId.get(ps.commitId()));
	if (cd.getId().equals(start.id()) && !ps.id().equals(start.psId())) {
	otherPatchSetsOfStart.add(thisPsd);
	}
	for (RevCommit p : thisPsd.commit().getParents()) {
	PatchSetData parentPsd = byId.get(p);
	if (parentPsd != null) {
	parents.put(thisPsd, parentPsd);
	children.put(parentPsd, thisPsd);
	}
	}
	}
	}

	Collection<PatchSetData> ancestors = walkAncestors(parents, start);
	List<PatchSetData> descendants =
	walkDescendants(children, start, otherPatchSetsOfStart, ancestors);
	List<PatchSetData> result = new ArrayList<>(ancestors.size() + descendants.size() - 1);
	result.addAll(Lists.reverse(descendants));
	result.addAll(ancestors);
	return result;
	}

	private Map<ObjectId, PatchSetData> collectById(List<ChangeData> in) throws IOException {
	Project.NameKey project = in.get(0).change().getProject();
	Map<ObjectId, PatchSetData> result = Maps.newHashMapWithExpectedSize(in.size() * 3);
	try (Repository repo = repoManager.openRepository(project);
	RevWalk rw = new RevWalk(repo)) {
	rw.setRetainBody(true);
	for (ChangeData cd : in) {
	checkArgument(
	cd.change().getProject().equals(project),
	"Expected change %s in project %s, found %s",
	cd.getId(),
	project,
	cd.change().getProject());
	for (PatchSet ps : cd.patchSets()) {
	RevCommit c = rw.parseCommit(ps.commitId());
	PatchSetData psd = PatchSetData.create(cd, ps, c);
	result.put(ps.commitId(), psd);
	}
	}
	}
	return result;
	}

	private Collection<PatchSetData> walkAncestors(
	ListMultimap<PatchSetData, PatchSetData> parents, PatchSetData start)
	throws PermissionBackendException {
	LinkedHashSet<PatchSetData> result = new LinkedHashSet<>();
	Deque<PatchSetData> pending = new ArrayDeque<>();
	pending.add(start);
	while (!pending.isEmpty()) {
	PatchSetData psd = pending.remove();
	if (result.contains(psd) \|\| !isVisible(psd)) {
	continue;
	}
	result.add(psd);
	pending.addAll(Lists.reverse(parents.get(psd)));
	}
	return result;
	}

	private List<PatchSetData> walkDescendants(
	ListMultimap<PatchSetData, PatchSetData> children,
	PatchSetData start,
	List<PatchSetData> otherPatchSetsOfStart,
	Iterable<PatchSetData> ancestors)
	throws PermissionBackendException {
	Set<Change.Id> alreadyEmittedChanges = new HashSet<>();
	addAllChangeIds(alreadyEmittedChanges, ancestors);

	// Prefer descendants found by following the original patch set passed in.
	List<PatchSetData> result =
	walkDescendentsImpl(alreadyEmittedChanges, children, ImmutableList.of(start));
	addAllChangeIds(alreadyEmittedChanges, result);

	// Then, go back and add new indirect descendants found by following any
	// other patch sets of start. These show up after all direct descendants,
	// because we wouldn't know where in the walk to insert them.
	result.addAll(walkDescendentsImpl(alreadyEmittedChanges, children, otherPatchSetsOfStart));
	return result;
	}

	private static void addAllChangeIds(
	Collection<Change.Id> changeIds, Iterable<PatchSetData> psds) {
	for (PatchSetData psd : psds) {
	changeIds.add(psd.id());
	}
	}

	private List<PatchSetData> walkDescendentsImpl(
	Set<Change.Id> alreadyEmittedChanges,
	ListMultimap<PatchSetData, PatchSetData> children,
	List<PatchSetData> start)
	throws PermissionBackendException {
	if (start.isEmpty()) {
	return new ArrayList<>();
	}
	Map<Change.Id, PatchSet.Id> maxPatchSetIds = new HashMap<>();
	Set<PatchSetData> seen = new HashSet<>();
	List<PatchSetData> allPatchSets = new ArrayList<>();
	Deque<PatchSetData> pending = new ArrayDeque<>();
	pending.addAll(start);
	while (!pending.isEmpty()) {
	PatchSetData psd = pending.remove();
	if (seen.contains(psd) \|\| !isVisible(psd)) {
	continue;
	}
	seen.add(psd);
	if (!alreadyEmittedChanges.contains(psd.id())) {
	// Don't emit anything for changes that were previously emitted, even
	// though different patch sets might show up later. However, do
	// continue walking through them for the purposes of finding indirect
	// descendants.
	PatchSet.Id oldMax = maxPatchSetIds.get(psd.id());
	if (oldMax == null \|\| psd.psId().get() > oldMax.get()) {
	maxPatchSetIds.put(psd.id(), psd.psId());
	}
	allPatchSets.add(psd);
	}
	// Depth-first search with newest children first.
	for (PatchSetData child : children.get(psd)) {
	pending.addFirst(child);
	}
	}

	// If we saw the same change multiple times, prefer the latest patch set.
	List<PatchSetData> result = new ArrayList<>(allPatchSets.size());
	for (PatchSetData psd : allPatchSets) {
	if (requireNonNull(maxPatchSetIds.get(psd.id())).equals(psd.psId())) {
	result.add(psd);
	}
	}
	return result;
	}

	private boolean isVisible(PatchSetData psd) throws PermissionBackendException {
	PermissionBackend.WithUser perm = permissionBackend.currentUser();
	return perm.change(psd.data()).test(ChangePermission.READ)
	&& projectCache.get(psd.data().project()).map(ProjectState::statePermitsRead).orElse(false);
	}

	@AutoValue
	public abstract static class PatchSetData {
	@VisibleForTesting
	static PatchSetData create(ChangeData cd, PatchSet ps, RevCommit commit) {
	return new AutoValue_RelatedChangesSorter_PatchSetData(cd, ps, commit);
	}

	public abstract ChangeData data();

	public abstract PatchSet patchSet();

	public abstract RevCommit commit();

	public PatchSet.Id psId() {
	return patchSet().id();
	}

	public Change.Id id() {
	return psId().changeId();
	}

	@Memoized
	@Override
	public int hashCode() {
	return Objects.hash(patchSet().id(), commit());
	}

	@Override
	public final boolean equals(Object obj) {
	if (!(obj instanceof PatchSetData)) {
	return false;
	}
	PatchSetData o = (PatchSetData) obj;
	return Objects.equals(patchSet().id(), o.patchSet().id())
	&& Objects.equals(commit(), o.commit());
	}
	}
	}