Add a helper to sort ChangeDatas in RevWalk order
To do this, we have to define the mapping of change -> commit. In the
default case, we just pick the SHA-1 of the latest patch set. In a
more complex case, like listing related changes, we might be
interested in only a subset of patch sets, in which case we pick the
SHA-1 of the latest patch set in that subset.
Once we collect the mapping of change to commit, we can mark each
commit interesting, and do a simple RevWalk until we've seen every
interesting commit. This produces the order of changes within a single
project.
We also have to deal with multiple projects, for example if we want to
sort all changes across all projects matching a particular topic. To
do this, we keep groups by project together, and sort each group based
on the name of the project. This is more stable than alternatives
involving commit or change update time, since those are more likely to
change while a user is navigating among a list of changes in the
project.
Change-Id: I9a1fc7dbf308d1e4bde4d0ff1acf10b8aacb9b0f
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/change/WalkSorter.java b/gerrit-server/src/main/java/com/google/gerrit/server/change/WalkSorter.java
new file mode 100644
index 0000000..56d6677
--- /dev/null
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/change/WalkSorter.java
@@ -0,0 +1,203 @@
+// 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 com.google.auto.value.AutoValue;
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.Function;
+import com.google.common.collect.ArrayListMultimap;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Iterables;
+import com.google.common.collect.Multimap;
+import com.google.common.collect.Ordering;
+import com.google.gerrit.reviewdb.client.PatchSet;
+import com.google.gerrit.reviewdb.client.Project;
+import com.google.gerrit.server.git.GitRepositoryManager;
+import com.google.gerrit.server.query.change.ChangeData;
+import com.google.gwtorm.server.OrmException;
+import com.google.inject.Inject;
+
+import org.eclipse.jgit.errors.IncorrectObjectTypeException;
+import org.eclipse.jgit.errors.MissingObjectException;
+import org.eclipse.jgit.lib.ObjectId;
+import org.eclipse.jgit.lib.Repository;
+import org.eclipse.jgit.revwalk.RevCommit;
+import org.eclipse.jgit.revwalk.RevSort;
+import org.eclipse.jgit.revwalk.RevWalk;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+/**
+ * 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(Set)}. Perform a standard {@link RevWalk} on each
+ * project repository, 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.
+ */
+class WalkSorter {
+ private static final Logger log =
+ LoggerFactory.getLogger(WalkSorter.class);
+
+ private static final Ordering<List<PatchSetData>> PROJECT_LIST_SORTER =
+ Ordering.natural().nullsFirst()
+ .onResultOf(
+ new Function<List<PatchSetData>, Project.NameKey>() {
+ @Override
+ public Project.NameKey apply(List<PatchSetData> in) {
+ if (in == null || in.isEmpty()) {
+ return null;
+ }
+ try {
+ return in.get(0).data().change().getProject();
+ } catch (OrmException 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<>();
+ }
+
+ public WalkSorter includePatchSets(Iterable<PatchSet.Id> patchSets) {
+ Iterables.addAll(includePatchSets, patchSets);
+ return this;
+ }
+
+ public WalkSorter setRetainBody(boolean retainBody) {
+ this.retainBody = retainBody;
+ return this;
+ }
+
+ public Iterable<PatchSetData> sort(Iterable<ChangeData> in)
+ throws OrmException, IOException {
+ Multimap<Project.NameKey, ChangeData> byProject =
+ ArrayListMultimap.create();
+ 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()));
+ }
+ Collections.sort(sortedByProject, PROJECT_LIST_SORTER);
+ return Iterables.concat(sortedByProject);
+ }
+
+ private List<PatchSetData> sortProject(Project.NameKey project,
+ Collection<ChangeData> in) throws OrmException, IOException {
+ try (Repository repo = repoManager.openRepository(project);
+ RevWalk rw = new RevWalk(repo)) {
+ rw.setRetainBody(retainBody);
+ rw.sort(RevSort.TOPO);
+ Multimap<RevCommit, PatchSetData> byCommit = byCommit(rw, in);
+ if (byCommit.isEmpty()) {
+ return ImmutableList.of();
+ }
+
+ // 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.
+ for (RevCommit c : byCommit.keySet()) {
+ rw.markStart(c);
+ }
+
+ int expected = byCommit.keySet().size();
+ int found = 0;
+ RevCommit c;
+ List<PatchSetData> result = new ArrayList<>(expected);
+ while (found < expected && (c = rw.next()) != null) {
+ Collection<PatchSetData> psds = byCommit.get(c);
+ if (!psds.isEmpty()) {
+ found++;
+ for (PatchSetData psd : psds) {
+ result.add(psd);
+ }
+ }
+ }
+ return result;
+ }
+ }
+
+ private Multimap<RevCommit, PatchSetData> byCommit(RevWalk rw,
+ Collection<ChangeData> in) throws OrmException, IOException {
+ Multimap<RevCommit, PatchSetData> byCommit =
+ ArrayListMultimap.create(in.size(), 1);
+ for (ChangeData cd : in) {
+ PatchSet maxPs = null;
+ for (PatchSet ps : cd.patchSets()) {
+ if (shouldInclude(ps)
+ && (maxPs == null || ps.getId().get() > maxPs.getId().get())) {
+ maxPs = ps;
+ }
+ }
+ if (maxPs == null) {
+ continue; // No patch sets matched.
+ }
+ ObjectId id = ObjectId.fromString(maxPs.getRevision().get());
+ try {
+ RevCommit c = rw.parseCommit(id);
+ byCommit.put(c, PatchSetData.create(cd, maxPs, c));
+ } catch (MissingObjectException | IncorrectObjectTypeException e) {
+ log.warn(
+ "missing commit " + id.name() + " for patch set " + maxPs.getId(),
+ e);
+ }
+ }
+ return byCommit;
+ }
+
+ private boolean shouldInclude(PatchSet ps) {
+ return includePatchSets.isEmpty() || includePatchSets.contains(ps.getId());
+ }
+
+ @AutoValue
+ static abstract class PatchSetData {
+ @VisibleForTesting
+ static PatchSetData create(ChangeData cd, PatchSet ps, RevCommit commit) {
+ return new AutoValue_WalkSorter_PatchSetData(cd, ps, commit);
+ }
+
+ abstract ChangeData data();
+ abstract PatchSet patchSet();
+ abstract RevCommit commit();
+ }
+}
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/query/change/ChangeData.java b/gerrit-server/src/main/java/com/google/gerrit/server/query/change/ChangeData.java
index d94921e..5c023e2 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/query/change/ChangeData.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/query/change/ChangeData.java
@@ -172,12 +172,13 @@
/**
* Create an instance for testing only.
* <p>
- * Attempting to lazy load data will fail with NPEs.
+ * Attempting to lazy load data will fail with NPEs. Callers may consider
+ * manually setting fields that can be set.
*
* @param id change ID
* @return instance for testing.
*/
- static ChangeData createForTest(Change.Id id, int currentPatchSetId) {
+ public static ChangeData createForTest(Change.Id id, int currentPatchSetId) {
ChangeData cd = new ChangeData(null, null, null, null, null, null, null,
null, null, null, null, null, null, id);
cd.currentPatchSet = new PatchSet(new PatchSet.Id(id, currentPatchSetId));
diff --git a/gerrit-server/src/test/java/com/google/gerrit/server/change/WalkSorterTest.java b/gerrit-server/src/test/java/com/google/gerrit/server/change/WalkSorterTest.java
new file mode 100644
index 0000000..7b7983c
--- /dev/null
+++ b/gerrit-server/src/test/java/com/google/gerrit/server/change/WalkSorterTest.java
@@ -0,0 +1,267 @@
+// 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.collect.Collections2.permutations;
+import static com.google.common.truth.Truth.assertThat;
+
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
+import com.google.gerrit.reviewdb.client.Account;
+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.client.RevId;
+import com.google.gerrit.server.change.WalkSorter.PatchSetData;
+import com.google.gerrit.server.query.change.ChangeData;
+import com.google.gerrit.testutil.InMemoryRepositoryManager;
+import com.google.gerrit.testutil.InMemoryRepositoryManager.Repo;
+import com.google.gerrit.testutil.TestChanges;
+import com.google.gwtorm.client.KeyUtil;
+import com.google.gwtorm.server.StandardKeyEncoder;
+
+import org.eclipse.jgit.junit.TestRepository;
+import org.eclipse.jgit.lib.ObjectId;
+import org.eclipse.jgit.revwalk.RevCommit;
+import org.eclipse.jgit.revwalk.RevWalk;
+import org.junit.Before;
+import org.junit.Test;
+
+import java.util.ArrayList;
+import java.util.List;
+
+public class WalkSorterTest {
+ static {
+ KeyUtil.setEncoderImpl(new StandardKeyEncoder());
+ }
+
+ private Account.Id userId;
+ private InMemoryRepositoryManager repoManager;
+
+ @Before
+ public void setUp() {
+ userId = new Account.Id(1);
+ repoManager = new InMemoryRepositoryManager();
+ }
+
+ @Test
+ public void seriesOfChanges() throws Exception {
+ TestRepository<Repo> p = newRepo("p");
+ RevCommit c1_1 = p.commit().create();
+ RevCommit c2_1 = p.commit().parent(c1_1).create();
+ RevCommit c3_1 = p.commit().parent(c2_1).create();
+
+ ChangeData cd1 = newChange(p, c1_1);
+ ChangeData cd2 = newChange(p, c2_1);
+ ChangeData cd3 = newChange(p, c3_1);
+
+ List<ChangeData> changes = ImmutableList.of(cd1, cd2, cd3);
+ WalkSorter sorter = new WalkSorter(repoManager);
+
+ assertSorted(sorter, changes, ImmutableList.of(
+ patchSetData(cd3, c3_1),
+ patchSetData(cd2, c2_1),
+ patchSetData(cd1, c1_1)));
+
+ // Add new patch sets whose commits are in reverse order, so output is in
+ // reverse order.
+ RevCommit c3_2 = p.commit().create();
+ RevCommit c2_2 = p.commit().parent(c3_2).create();
+ RevCommit c1_2 = p.commit().parent(c2_2).create();
+
+ addPatchSet(cd1, c1_2);
+ addPatchSet(cd2, c2_2);
+ addPatchSet(cd3, c3_2);
+
+ assertSorted(sorter, changes, ImmutableList.of(
+ patchSetData(cd1, c1_2),
+ patchSetData(cd2, c2_2),
+ patchSetData(cd3, c3_2)));
+ }
+
+ @Test
+ public void seriesOfChangesAtSameTimestamp() throws Exception {
+ TestRepository<Repo> p = newRepo("p");
+ RevCommit c1 = p.commit().tick(0).create();
+ RevCommit c2 = p.commit().tick(0).parent(c1).create();
+ RevCommit c3 = p.commit().tick(0).parent(c2).create();
+ RevCommit c4 = p.commit().tick(0).parent(c3).create();
+
+ RevWalk rw = p.getRevWalk();
+ rw.parseCommit(c1);
+ assertThat(rw.parseCommit(c2).getCommitTime())
+ .isEqualTo(c1.getCommitTime());
+ assertThat(rw.parseCommit(c3).getCommitTime())
+ .isEqualTo(c1.getCommitTime());
+ assertThat(rw.parseCommit(c4).getCommitTime())
+ .isEqualTo(c1.getCommitTime());
+
+ ChangeData cd1 = newChange(p, c1);
+ ChangeData cd2 = newChange(p, c2);
+ ChangeData cd3 = newChange(p, c3);
+ ChangeData cd4 = newChange(p, c4);
+
+ List<ChangeData> changes = ImmutableList.of(cd1, cd2, cd3, cd4);
+ WalkSorter sorter = new WalkSorter(repoManager);
+
+ assertSorted(sorter, changes, ImmutableList.of(
+ patchSetData(cd4, c4),
+ patchSetData(cd3, c3),
+ patchSetData(cd2, c2),
+ patchSetData(cd1, c1)));
+ }
+
+ @Test
+ public void projectsSortedByName() throws Exception {
+ TestRepository<Repo> pa = newRepo("a");
+ TestRepository<Repo> pb = newRepo("b");
+ RevCommit c1 = pa.commit().create();
+ RevCommit c2 = pb.commit().create();
+ RevCommit c3 = pa.commit().parent(c1).create();
+ RevCommit c4 = pb.commit().parent(c2).create();
+
+ ChangeData cd1 = newChange(pa, c1);
+ ChangeData cd2 = newChange(pb, c2);
+ ChangeData cd3 = newChange(pa, c3);
+ ChangeData cd4 = newChange(pb, c4);
+
+ assertSorted(
+ new WalkSorter(repoManager),
+ ImmutableList.of(cd1, cd2, cd3, cd4),
+ ImmutableList.of(
+ patchSetData(cd3, c3),
+ patchSetData(cd1, c1),
+ patchSetData(cd4, c4),
+ patchSetData(cd2, c2)));
+ }
+
+ @Test
+ public void restrictToPatchSets() throws Exception {
+ TestRepository<Repo> p = newRepo("p");
+ RevCommit c1_1 = p.commit().create();
+ RevCommit c2_1 = p.commit().parent(c1_1).create();
+
+ ChangeData cd1 = newChange(p, c1_1);
+ ChangeData cd2 = newChange(p, c2_1);
+
+ // Add new patch sets whose commits are in reverse order.
+ RevCommit c2_2 = p.commit().create();
+ RevCommit c1_2 = p.commit().parent(c2_2).create();
+
+ addPatchSet(cd1, c1_2);
+ addPatchSet(cd2, c2_2);
+
+ List<ChangeData> changes = ImmutableList.of(cd1, cd2);
+ WalkSorter sorter = new WalkSorter(repoManager);
+
+ assertSorted(sorter, changes, ImmutableList.of(
+ patchSetData(cd1, c1_2),
+ patchSetData(cd2, c2_2)));
+
+ // If we restrict to PS1 of each change, the sorter uses that commit.
+ sorter.includePatchSets(ImmutableSet.of(
+ new PatchSet.Id(cd1.getId(), 1),
+ new PatchSet.Id(cd2.getId(), 1)));
+ assertSorted(sorter, changes, ImmutableList.of(
+ patchSetData(cd2, 1, c2_1),
+ patchSetData(cd1, 1, c1_1)));
+ }
+
+ @Test
+ public void restrictToPatchSetsOmittingWholeProject() throws Exception {
+ TestRepository<Repo> pa = newRepo("a");
+ TestRepository<Repo> pb = newRepo("b");
+ RevCommit c1 = pa.commit().create();
+ RevCommit c2 = pa.commit().create();
+
+ ChangeData cd1 = newChange(pa, c1);
+ ChangeData cd2 = newChange(pb, c2);
+
+ List<ChangeData> changes = ImmutableList.of(cd1, cd2);
+ WalkSorter sorter = new WalkSorter(repoManager)
+ .includePatchSets(ImmutableSet.of(cd1.currentPatchSet().getId()));
+
+ assertSorted(sorter, changes, ImmutableList.of(patchSetData(cd1, c1)));
+ }
+
+ @Test
+ public void retainBody() throws Exception {
+ TestRepository<Repo> p = newRepo("p");
+ RevCommit c = p.commit().message("message").create();
+ ChangeData cd = newChange(p, c);
+
+ List<ChangeData> changes = ImmutableList.of(cd);
+ RevCommit actual = new WalkSorter(repoManager)
+ .setRetainBody(true)
+ .sort(changes)
+ .iterator().next()
+ .commit();
+ assertThat(actual.getRawBuffer()).isNotNull();
+ assertThat(actual.getShortMessage()).isEqualTo("message");
+
+ actual = new WalkSorter(repoManager)
+ .setRetainBody(false)
+ .sort(changes)
+ .iterator().next()
+ .commit();
+ assertThat(actual.getRawBuffer()).isNull();
+ }
+
+ private ChangeData newChange(TestRepository<Repo> tr, ObjectId id)
+ throws Exception {
+ Project.NameKey project = tr.getRepository().getDescription().getProject();
+ Change c = TestChanges.newChange(project, userId);
+ ChangeData cd = ChangeData.createForTest(c.getId(), 1);
+ cd.setChange(c);
+ cd.currentPatchSet().setRevision(new RevId(id.name()));
+ cd.setPatchSets(ImmutableList.of(cd.currentPatchSet()));
+ return cd;
+ }
+
+ private PatchSet addPatchSet(ChangeData cd, ObjectId id) throws Exception {
+ TestChanges.incrementPatchSet(cd.change());
+ PatchSet ps = new PatchSet(cd.change().currentPatchSetId());
+ ps.setRevision(new RevId(id.name()));
+ List<PatchSet> patchSets = new ArrayList<>(cd.patchSets());
+ patchSets.add(ps);
+ cd.setPatchSets(patchSets);
+ return ps;
+ }
+
+ private TestRepository<Repo> newRepo(String name)
+ throws Exception {
+ return new TestRepository<>(
+ repoManager.createRepository(new Project.NameKey(name)));
+ }
+
+ private static PatchSetData patchSetData(ChangeData cd, RevCommit commit)
+ throws Exception {
+ return PatchSetData.create(cd, cd.currentPatchSet(), commit);
+ }
+
+ private static PatchSetData patchSetData(ChangeData cd, int psId,
+ RevCommit commit) throws Exception {
+ return PatchSetData.create(
+ cd, cd.patchSet(new PatchSet.Id(cd.getId(), psId)), commit);
+ }
+
+ private static void assertSorted(WalkSorter sorter, List<ChangeData> changes,
+ List<PatchSetData> expected) throws Exception {
+ for (List<ChangeData> list : permutations(changes)) {
+ assertThat(sorter.sort(list))
+ .containsExactlyElementsIn(expected).inOrder();
+ }
+ }
+}
