java/com/google/gerrit/server/change/WalkSorter.java - gerrit.git - 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.checkState;

 import com.google.auto.value.AutoValue;
 import com.google.common.annotations.VisibleForTesting;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.Iterables;
 import com.google.common.collect.ListMultimap;
 import com.google.common.collect.MultimapBuilder;
 import com.google.common.collect.Ordering;
 import com.google.common.collect.SetMultimap;
 import com.google.common.flogger.FluentLogger;
 import com.google.errorprone.annotations.CanIgnoreReturnValue;
 import com.google.gerrit.entities.PatchSet;
 import com.google.gerrit.entities.Project;
 import com.google.gerrit.exceptions.StorageException;
 import com.google.gerrit.server.git.GitRepositoryManager;
 import com.google.gerrit.server.query.change.ChangeData;
 import com.google.inject.Inject;
 import java.io.IOException;
 import java.util.ArrayDeque;
 import java.util.ArrayList;
 import java.util.Collection;
 import java.util.Deque;
 import java.util.HashSet;
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
 import org.eclipse.jgit.errors.IncorrectObjectTypeException;
 import org.eclipse.jgit.errors.MissingObjectException;
 import org.eclipse.jgit.lib.Repository;
 import org.eclipse.jgit.revwalk.RevCommit;
 import org.eclipse.jgit.revwalk.RevFlag;
 import org.eclipse.jgit.revwalk.RevWalk;

 /**
  * Helper to sort {@link ChangeData}s based on {@link RevWalk} ordering.
  *
  * <p>Split changes by project, and map each change to a single commit based on the latest patch
  * set. The set of patch sets considered may be limited by calling {@link
  * #includePatchSets(Iterable)}. Perform a standard {@link RevWalk} on each project repository, do
  * an approximate topo sort, and record the order in which each change's commit is seen.
  *
  * <p>Once an order within each project is determined, groups of changes are sorted based on the
  * project name. This is slightly more stable than sorting on something like the commit or change
  * timestamp, as it will not unexpectedly reorder large groups of changes on subsequent calls if one
  * of the changes was updated.
  */
 public class WalkSorter {
   private static final FluentLogger logger = FluentLogger.forEnclosingClass();

   private static final Ordering<List<PatchSetData>> PROJECT_LIST_SORTER =
       Ordering.natural()
           .nullsFirst()
           .onResultOf(
               (List<PatchSetData> in) -> {
                 if (in == null || in.isEmpty()) {
                   return null;
                 }
                 try {
                   return in.get(0).data().change().getProject();
                 } catch (StorageException e) {
                   throw new IllegalStateException(e);
                 }
               });

   private final GitRepositoryManager repoManager;
   private final Set<PatchSet.Id> includePatchSets;
   private boolean retainBody;

   @Inject
   WalkSorter(GitRepositoryManager repoManager) {
     this.repoManager = repoManager;
     includePatchSets = new HashSet<>();
   }

   @CanIgnoreReturnValue
   public WalkSorter includePatchSets(Iterable<PatchSet.Id> patchSets) {
     Iterables.addAll(includePatchSets, patchSets);
     return this;
   }

   @CanIgnoreReturnValue
   public WalkSorter setRetainBody(boolean retainBody) {
     this.retainBody = retainBody;
     return this;
   }

   public Iterable<PatchSetData> sort(Iterable<ChangeData> in) throws IOException {
     ListMultimap<Project.NameKey, ChangeData> byProject =
         MultimapBuilder.hashKeys().arrayListValues().build();
     for (ChangeData cd : in) {
       byProject.put(cd.change().getProject(), cd);
     }

     List<List<PatchSetData>> sortedByProject = new ArrayList<>(byProject.keySet().size());
     for (Map.Entry<Project.NameKey, Collection<ChangeData>> e : byProject.asMap().entrySet()) {
       sortedByProject.add(sortProject(e.getKey(), e.getValue()));
     }
     sortedByProject.sort(PROJECT_LIST_SORTER);
     return Iterables.concat(sortedByProject);
   }

   private ImmutableList<PatchSetData> sortProject(
       Project.NameKey project, Collection<ChangeData> in) throws IOException {
     try (Repository repo = repoManager.openRepository(project);
         RevWalk rw = new RevWalk(repo)) {
       rw.setRetainBody(retainBody);
       ListMultimap<RevCommit, PatchSetData> byCommit = byCommit(rw, in);
       if (byCommit.isEmpty()) {
         return ImmutableList.of();
       } else if (byCommit.size() == 1) {
         return ImmutableList.of(byCommit.values().iterator().next());
       }

       // Walk from all patch set SHA-1s, and terminate as soon as we've found
       // everything we're looking for. This is equivalent to just sorting the
       // list of commits by the RevWalk's configured order.
       //
       // Partially topo sort the list, ensuring no parent is emitted before a
       // direct child that is also in the input set. This preserves the stable,
       // expected sort in the case where many commits share the same timestamp,
       // e.g. a quick rebase. It also avoids JGit's topo sort, which slurps all
       // interesting commits at the beginning, which is a problem since we don't
       // know which commits to mark as uninteresting. Finding a reasonable set
       // of commits to mark uninteresting (the "rootmost" set) is at least as
       // difficult as just implementing this partial topo sort ourselves.
       //
       // (This is slightly less efficient than JGit's topo sort, which uses a
       // private in-degree field in RevCommit rather than multimaps. We assume
       // the input size is small enough that this is not an issue.)

       Set<RevCommit> commits = byCommit.keySet();
       ListMultimap<RevCommit, RevCommit> children = collectChildren(commits);
       SetMultimap<RevCommit, RevCommit> pending =
           MultimapBuilder.hashKeys().hashSetValues().build();
       Deque<RevCommit> todo = new ArrayDeque<>();

       RevFlag done = rw.newFlag("done");
       markStart(rw, commits);
       int expected = commits.size();
       int found = 0;
       RevCommit c;
       List<PatchSetData> result = new ArrayList<>(expected);
       int maxPopSize = commits.size() * commits.size();
       while (found < expected && (c = rw.next()) != null) {
         if (!commits.contains(c)) {
           continue;
         }
         todo.clear();
         todo.add(c);
         int i = 0;
         while (!todo.isEmpty()) {
           // Sanity check: in the worst case scenario, each commit can add all previous commits in
           // the todo queue. This can lead to (n-1) + (n-2) + ... +1 iterations of the algorithm.
           // So, in the worst case we can't pop more than N^2 pending commits, otherwise
           // we have an infinite loop due to programmer error or something. (actually, it is
           // (N-1) + (N-2) + (N-3) + (1) + 1 = N/2*(N-1)+1, but N^2 is enough for us.)
           checkState(
               ++i <= maxPopSize,
               "Too many pending steps while sorting %s - can be a problem in the algorithm.",
               commits);
           RevCommit t = todo.removeFirst();
           if (t.has(done)) {
             continue;
           }
           boolean ready = true;
           for (RevCommit child : children.get(t)) {
             if (!child.has(done)) {
               pending.put(child, t);
               ready = false;
             }
           }
           if (ready) {
             found += emit(t, byCommit, result, done);
             todo.addAll(pending.get(t));
           }
         }
       }
       return ImmutableList.copyOf(result);
     }
   }

   private static ListMultimap<RevCommit, RevCommit> collectChildren(Set<RevCommit> commits) {
     ListMultimap<RevCommit, RevCommit> children =
         MultimapBuilder.hashKeys().arrayListValues().build();
     for (RevCommit c : commits) {
       for (RevCommit p : c.getParents()) {
         if (commits.contains(p)) {
           children.put(p, c);
         }
       }
     }
     return children;
   }

   private static int emit(
       RevCommit c,
       ListMultimap<RevCommit, PatchSetData> byCommit,
       List<PatchSetData> result,
       RevFlag done) {
     if (c.has(done)) {
       return 0;
     }
     c.add(done);
     List<PatchSetData> psds = byCommit.get(c);
     if (!psds.isEmpty()) {
       result.addAll(psds);
       return 1;
     }
     return 0;
   }

   private ListMultimap<RevCommit, PatchSetData> byCommit(RevWalk rw, Collection<ChangeData> in)
       throws IOException {
     ListMultimap<RevCommit, PatchSetData> byCommit =
         MultimapBuilder.hashKeys(in.size()).arrayListValues(1).build();
     for (ChangeData cd : in) {
       PatchSet maxPs = null;
       for (PatchSet ps : cd.patchSets()) {
         if (shouldInclude(ps) && (maxPs == null || ps.id().get() > maxPs.id().get())) {
           maxPs = ps;
         }
       }
       if (maxPs == null) {
         continue; // No patch sets matched.
       }
       try {
         RevCommit c = rw.parseCommit(maxPs.commitId());
         byCommit.put(c, PatchSetData.create(cd, maxPs, c));
       } catch (MissingObjectException | IncorrectObjectTypeException e) {
         logger.atWarning().withCause(e).log(
             "missing commit %s for patch set %s", maxPs.commitId().name(), maxPs.id());
       }
     }
     return byCommit;
   }

   private boolean shouldInclude(PatchSet ps) {
     return includePatchSets.isEmpty() || includePatchSets.contains(ps.id());
   }

   private static void markStart(RevWalk rw, Iterable<RevCommit> commits) throws IOException {
     for (RevCommit c : commits) {
       rw.markStart(c);
     }
   }

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

     public abstract ChangeData data();

     abstract PatchSet patchSet();

     abstract RevCommit 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.checkState;

	import com.google.auto.value.AutoValue;
	import com.google.common.annotations.VisibleForTesting;
	import com.google.common.collect.ImmutableList;
	import com.google.common.collect.Iterables;
	import com.google.common.collect.ListMultimap;
	import com.google.common.collect.MultimapBuilder;
	import com.google.common.collect.Ordering;
	import com.google.common.collect.SetMultimap;
	import com.google.common.flogger.FluentLogger;
	import com.google.errorprone.annotations.CanIgnoreReturnValue;
	import com.google.gerrit.entities.PatchSet;
	import com.google.gerrit.entities.Project;
	import com.google.gerrit.exceptions.StorageException;
	import com.google.gerrit.server.git.GitRepositoryManager;
	import com.google.gerrit.server.query.change.ChangeData;
	import com.google.inject.Inject;
	import java.io.IOException;
	import java.util.ArrayDeque;
	import java.util.ArrayList;
	import java.util.Collection;
	import java.util.Deque;
	import java.util.HashSet;
	import java.util.List;
	import java.util.Map;
	import java.util.Set;
	import org.eclipse.jgit.errors.IncorrectObjectTypeException;
	import org.eclipse.jgit.errors.MissingObjectException;
	import org.eclipse.jgit.lib.Repository;
	import org.eclipse.jgit.revwalk.RevCommit;
	import org.eclipse.jgit.revwalk.RevFlag;
	import org.eclipse.jgit.revwalk.RevWalk;

	/**
	* Helper to sort {@link ChangeData}s based on {@link RevWalk} ordering.
	*
	* <p>Split changes by project, and map each change to a single commit based on the latest patch
	* set. The set of patch sets considered may be limited by calling {@link
	* #includePatchSets(Iterable)}. Perform a standard {@link RevWalk} on each project repository, do
	* an approximate topo sort, and record the order in which each change's commit is seen.
	*
	* <p>Once an order within each project is determined, groups of changes are sorted based on the
	* project name. This is slightly more stable than sorting on something like the commit or change
	* timestamp, as it will not unexpectedly reorder large groups of changes on subsequent calls if one
	* of the changes was updated.
	*/
	public class WalkSorter {
	private static final FluentLogger logger = FluentLogger.forEnclosingClass();

	private static final Ordering<List<PatchSetData>> PROJECT_LIST_SORTER =
	Ordering.natural()
	.nullsFirst()
	.onResultOf(
	(List<PatchSetData> in) -> {
	if (in == null \|\| in.isEmpty()) {
	return null;
	}
	try {
	return in.get(0).data().change().getProject();
	} catch (StorageException e) {
	throw new IllegalStateException(e);
	}
	});

	private final GitRepositoryManager repoManager;
	private final Set<PatchSet.Id> includePatchSets;
	private boolean retainBody;

	@Inject
	WalkSorter(GitRepositoryManager repoManager) {
	this.repoManager = repoManager;
	includePatchSets = new HashSet<>();
	}

	@CanIgnoreReturnValue
	public WalkSorter includePatchSets(Iterable<PatchSet.Id> patchSets) {
	Iterables.addAll(includePatchSets, patchSets);
	return this;
	}

	@CanIgnoreReturnValue
	public WalkSorter setRetainBody(boolean retainBody) {
	this.retainBody = retainBody;
	return this;
	}

	public Iterable<PatchSetData> sort(Iterable<ChangeData> in) throws IOException {
	ListMultimap<Project.NameKey, ChangeData> byProject =
	MultimapBuilder.hashKeys().arrayListValues().build();
	for (ChangeData cd : in) {
	byProject.put(cd.change().getProject(), cd);
	}

	List<List<PatchSetData>> sortedByProject = new ArrayList<>(byProject.keySet().size());
	for (Map.Entry<Project.NameKey, Collection<ChangeData>> e : byProject.asMap().entrySet()) {
	sortedByProject.add(sortProject(e.getKey(), e.getValue()));
	}
	sortedByProject.sort(PROJECT_LIST_SORTER);
	return Iterables.concat(sortedByProject);
	}

	private ImmutableList<PatchSetData> sortProject(
	Project.NameKey project, Collection<ChangeData> in) throws IOException {
	try (Repository repo = repoManager.openRepository(project);
	RevWalk rw = new RevWalk(repo)) {
	rw.setRetainBody(retainBody);
	ListMultimap<RevCommit, PatchSetData> byCommit = byCommit(rw, in);
	if (byCommit.isEmpty()) {
	return ImmutableList.of();
	} else if (byCommit.size() == 1) {
	return ImmutableList.of(byCommit.values().iterator().next());
	}

	// Walk from all patch set SHA-1s, and terminate as soon as we've found
	// everything we're looking for. This is equivalent to just sorting the
	// list of commits by the RevWalk's configured order.
	//
	// Partially topo sort the list, ensuring no parent is emitted before a
	// direct child that is also in the input set. This preserves the stable,
	// expected sort in the case where many commits share the same timestamp,
	// e.g. a quick rebase. It also avoids JGit's topo sort, which slurps all
	// interesting commits at the beginning, which is a problem since we don't
	// know which commits to mark as uninteresting. Finding a reasonable set
	// of commits to mark uninteresting (the "rootmost" set) is at least as
	// difficult as just implementing this partial topo sort ourselves.
	//
	// (This is slightly less efficient than JGit's topo sort, which uses a
	// private in-degree field in RevCommit rather than multimaps. We assume
	// the input size is small enough that this is not an issue.)

	Set<RevCommit> commits = byCommit.keySet();
	ListMultimap<RevCommit, RevCommit> children = collectChildren(commits);
	SetMultimap<RevCommit, RevCommit> pending =
	MultimapBuilder.hashKeys().hashSetValues().build();
	Deque<RevCommit> todo = new ArrayDeque<>();

	RevFlag done = rw.newFlag("done");
	markStart(rw, commits);
	int expected = commits.size();
	int found = 0;
	RevCommit c;
	List<PatchSetData> result = new ArrayList<>(expected);
	int maxPopSize = commits.size() * commits.size();
	while (found < expected && (c = rw.next()) != null) {
	if (!commits.contains(c)) {
	continue;
	}
	todo.clear();
	todo.add(c);
	int i = 0;
	while (!todo.isEmpty()) {
	// Sanity check: in the worst case scenario, each commit can add all previous commits in
	// the todo queue. This can lead to (n-1) + (n-2) + ... +1 iterations of the algorithm.
	// So, in the worst case we can't pop more than N^2 pending commits, otherwise
	// we have an infinite loop due to programmer error or something. (actually, it is
	// (N-1) + (N-2) + (N-3) + (1) + 1 = N/2*(N-1)+1, but N^2 is enough for us.)
	checkState(
	++i <= maxPopSize,
	"Too many pending steps while sorting %s - can be a problem in the algorithm.",
	commits);
	RevCommit t = todo.removeFirst();
	if (t.has(done)) {
	continue;
	}
	boolean ready = true;
	for (RevCommit child : children.get(t)) {
	if (!child.has(done)) {
	pending.put(child, t);
	ready = false;
	}
	}
	if (ready) {
	found += emit(t, byCommit, result, done);
	todo.addAll(pending.get(t));
	}
	}
	}
	return ImmutableList.copyOf(result);
	}
	}

	private static ListMultimap<RevCommit, RevCommit> collectChildren(Set<RevCommit> commits) {
	ListMultimap<RevCommit, RevCommit> children =
	MultimapBuilder.hashKeys().arrayListValues().build();
	for (RevCommit c : commits) {
	for (RevCommit p : c.getParents()) {
	if (commits.contains(p)) {
	children.put(p, c);
	}
	}
	}
	return children;
	}

	private static int emit(
	RevCommit c,
	ListMultimap<RevCommit, PatchSetData> byCommit,
	List<PatchSetData> result,
	RevFlag done) {
	if (c.has(done)) {
	return 0;
	}
	c.add(done);
	List<PatchSetData> psds = byCommit.get(c);
	if (!psds.isEmpty()) {
	result.addAll(psds);
	return 1;
	}
	return 0;
	}

	private ListMultimap<RevCommit, PatchSetData> byCommit(RevWalk rw, Collection<ChangeData> in)
	throws IOException {
	ListMultimap<RevCommit, PatchSetData> byCommit =
	MultimapBuilder.hashKeys(in.size()).arrayListValues(1).build();
	for (ChangeData cd : in) {
	PatchSet maxPs = null;
	for (PatchSet ps : cd.patchSets()) {
	if (shouldInclude(ps) && (maxPs == null \|\| ps.id().get() > maxPs.id().get())) {
	maxPs = ps;
	}
	}
	if (maxPs == null) {
	continue; // No patch sets matched.
	}
	try {
	RevCommit c = rw.parseCommit(maxPs.commitId());
	byCommit.put(c, PatchSetData.create(cd, maxPs, c));
	} catch (MissingObjectException \| IncorrectObjectTypeException e) {
	logger.atWarning().withCause(e).log(
	"missing commit %s for patch set %s", maxPs.commitId().name(), maxPs.id());
	}
	}
	return byCommit;
	}

	private boolean shouldInclude(PatchSet ps) {
	return includePatchSets.isEmpty() \|\| includePatchSets.contains(ps.id());
	}

	private static void markStart(RevWalk rw, Iterable<RevCommit> commits) throws IOException {
	for (RevCommit c : commits) {
	rw.markStart(c);
	}
	}

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

	public abstract ChangeData data();

	abstract PatchSet patchSet();

	abstract RevCommit commit();
	}
	}