1 files changed, 218 insertions, 0 deletions
diff --git a/java/com/google/gerrit/server/change/IncludedInResolver.java b/java/com/google/gerrit/server/change/IncludedInResolver.java
new file mode 100644
index 0000000000..09ca258103
--- /dev/null
+++ b/java/com/google/gerrit/server/change/IncludedInResolver.java
@@ -0,0 +1,218 @@
+// 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.change;
+
+import static com.google.common.collect.ImmutableSortedSet.toImmutableSortedSet;
+import static java.util.Comparator.comparing;
+import static java.util.Comparator.naturalOrder;
+import static java.util.stream.Collectors.toList;
+
+import com.google.auto.value.AutoValue;
+import com.google.common.collect.ImmutableSortedSet;
+import com.google.common.collect.LinkedListMultimap;
+import com.google.common.collect.ListMultimap;
+import com.google.common.collect.Lists;
+import com.google.common.flogger.FluentLogger;
+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.Set;
+import org.eclipse.jgit.errors.IncorrectObjectTypeException;
+import org.eclipse.jgit.errors.MissingObjectException;
+import org.eclipse.jgit.lib.Constants;
+import org.eclipse.jgit.lib.Ref;
+import org.eclipse.jgit.lib.RefDatabase;
+import org.eclipse.jgit.lib.Repository;
+import org.eclipse.jgit.revwalk.RevCommit;
+import org.eclipse.jgit.revwalk.RevFlag;
+import org.eclipse.jgit.revwalk.RevWalk;
+
+/** Resolve in which tags and branches a commit is included. */
+public class IncludedInResolver {
+  private static final FluentLogger logger = FluentLogger.forEnclosingClass();
+
+  public static Result resolve(Repository repo, RevWalk rw, RevCommit commit) throws IOException {
+    RevFlag flag = newFlag(rw);
+    try {
+      return new IncludedInResolver(repo, rw, commit, flag).resolve();
+    } finally {
+      rw.disposeFlag(flag);
+    }
+  }
+
+  public static boolean includedInAny(
+      final Repository repo, RevWalk rw, RevCommit commit, Collection<Ref> refs)
+      throws IOException {
+    if (refs.isEmpty()) {
+      return false;
+    }
+    RevFlag flag = newFlag(rw);
+    try {
+      return new IncludedInResolver(repo, rw, commit, flag).includedInOne(refs);
+    } finally {
+      rw.disposeFlag(flag);
+    }
+  }
+
+  private static RevFlag newFlag(RevWalk rw) {
+    return rw.newFlag("CONTAINS_TARGET");
+  }
+
+  private final Repository repo;
+  private final RevWalk rw;
+  private final RevCommit target;
+
+  private final RevFlag containsTarget;
+  private ListMultimap<RevCommit, String> commitToRef;
+  private List<RevCommit> tipsByCommitTime;
+
+  private IncludedInResolver(
+      Repository repo, RevWalk rw, RevCommit target, RevFlag containsTarget) {
+    this.repo = repo;
+    this.rw = rw;
+    this.target = target;
+    this.containsTarget = containsTarget;
+  }
+
+  private Result resolve() throws IOException {
+    RefDatabase refDb = repo.getRefDatabase();
+    Collection<Ref> tags = refDb.getRefsByPrefix(Constants.R_TAGS);
+    Collection<Ref> branches = refDb.getRefsByPrefix(Constants.R_HEADS);
+    List<Ref> allTagsAndBranches = Lists.newArrayListWithCapacity(tags.size() + branches.size());
+    allTagsAndBranches.addAll(tags);
+    allTagsAndBranches.addAll(branches);
+    parseCommits(allTagsAndBranches);
+    Set<String> allMatchingTagsAndBranches = includedIn(tipsByCommitTime, 0);
+
+    return new AutoValue_IncludedInResolver_Result(
+        getMatchingRefNames(allMatchingTagsAndBranches, branches),
+        getMatchingRefNames(allMatchingTagsAndBranches, tags));
+  }
+
+  private boolean includedInOne(Collection<Ref> refs) throws IOException {
+    parseCommits(refs);
+    List<RevCommit> before = new ArrayList<>();
+    List<RevCommit> after = new ArrayList<>();
+    partition(before, after);
+    rw.reset();
+    // It is highly likely that the target is reachable from the "after" set
+    // Within the "before" set we are trying to handle cases arising from clock skew
+    return !includedIn(after, 1).isEmpty() || !includedIn(before, 1).isEmpty();
+  }
+
+  /** Resolves which tip refs include the target commit. */
+  private Set<String> includedIn(Collection<RevCommit> tips, int limit)
+      throws IOException, MissingObjectException, IncorrectObjectTypeException {
+    Set<String> result = new HashSet<>();
+    for (RevCommit tip : tips) {
+      boolean commitFound = false;
+      rw.resetRetain(RevFlag.UNINTERESTING, containsTarget);
+      rw.markStart(tip);
+      for (RevCommit commit : rw) {
+        if (commit.equals(target) || commit.has(containsTarget)) {
+          commitFound = true;
+          tip.add(containsTarget);
+          result.addAll(commitToRef.get(tip));
+          break;
+        }
+      }
+      if (!commitFound) {
+        rw.markUninteresting(tip);
+      } else if (0 < limit && limit < result.size()) {
+        break;
+      }
+    }
+    return result;
+  }
+
+  /**
+   * Partition the reference tips into two sets:
+   *
+   * <ul>
+   *   <li>before = commits with time < target.getCommitTime()
+   *   <li>after = commits with time >= target.getCommitTime()
+   * </ul>
+   *
+   * Each of the before/after lists is sorted by the commit time.
+   *
+   * @param before
+   * @param after
+   */
+  private void partition(List<RevCommit> before, List<RevCommit> after) {
+    int insertionPoint =
+        Collections.binarySearch(tipsByCommitTime, target, comparing(RevCommit::getCommitTime));
+    if (insertionPoint < 0) {
+      insertionPoint = -(insertionPoint + 1);
+    }
+    if (0 < insertionPoint) {
+      before.addAll(tipsByCommitTime.subList(0, insertionPoint));
+    }
+    if (insertionPoint < tipsByCommitTime.size()) {
+      after.addAll(tipsByCommitTime.subList(insertionPoint, tipsByCommitTime.size()));
+    }
+  }
+
+  /**
+   * Returns the short names of refs which are as well in the matchingRefs list as well as in the
+   * allRef list.
+   */
+  private static ImmutableSortedSet<String> getMatchingRefNames(
+      Set<String> matchingRefs, Collection<Ref> allRefs) {
+    return allRefs.stream()
+        .map(Ref::getName)
+        .filter(matchingRefs::contains)
+        .map(Repository::shortenRefName)
+        .collect(toImmutableSortedSet(naturalOrder()));
+  }
+
+  /** Parse commit of ref and store the relation between ref and commit. */
+  private void parseCommits(Collection<Ref> refs) throws IOException {
+    if (commitToRef != null) {
+      return;
+    }
+    commitToRef = LinkedListMultimap.create();
+    for (Ref ref : refs) {
+      final RevCommit commit;
+      try {
+        commit = rw.parseCommit(ref.getObjectId());
+      } catch (IncorrectObjectTypeException notCommit) {
+        // Its OK for a tag reference to point to a blob or a tree, this
+        // is common in the Linux kernel or git.git repository.
+        //
+        continue;
+      } catch (MissingObjectException notHere) {
+        // Log the problem with this branch, but keep processing.
+        //
+        logger.atWarning().log(
+            "Reference %s in %s points to dangling object %s",
+            ref.getName(), repo.getDirectory(), ref.getObjectId());
+        continue;
+      }
+      commitToRef.put(commit, ref.getName());
+    }
+    tipsByCommitTime =
+        commitToRef.keySet().stream().sorted(comparing(RevCommit::getCommitTime)).collect(toList());
+  }
+
+  @AutoValue
+  public abstract static class Result {
+    public abstract ImmutableSortedSet<String> branches();
+
+    public abstract ImmutableSortedSet<String> tags();
+  }
+}