java/com/google/gerrit/server/change/RelatedChangesSorter.java

// 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 = getCheckedPatchSetData(byId, startPs);

    // 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;
  }

  public List<PatchSetData> sortAncestors(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 = getCheckedPatchSetData(byId, startPs);

    // Map of patch set -> immediate parent.
    ListMultimap<PatchSetData, PatchSetData> parents =
        MultimapBuilder.hashKeys(in.size()).arrayListValues(3).build();

    for (ChangeData cd : in) {
      for (PatchSet ps : cd.patchSets()) {
        PatchSetData thisPsd = requireNonNull(byId.get(ps.commitId()));

        for (RevCommit p : thisPsd.commit().getParents()) {
          PatchSetData parentPsd = byId.get(p);
          if (parentPsd != null) {
            parents.put(thisPsd, parentPsd);
          }
        }
      }
    }

    Collection<PatchSetData> ancestors = walkAncestors(parents, start);
    return List.copyOf(ancestors);
  }

  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 PatchSetData getCheckedPatchSetData(Map<ObjectId, PatchSetData> byId, PatchSet ps) {
    PatchSetData psData = byId.get(ps.commitId());
    return requireNonNull(
        psData,
        () ->
            String.format(
                "commit %s of patch set %s not found in %s",
                ps.commitId().name(),
                ps.id(),
                byId.entrySet().stream()
                    .collect(toMap(e -> e.getKey().name(), e -> e.getValue().patchSet().id()))));
  }

  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());
    }
  }
}