diff --git a/BUILD b/BUILD
index d5f6b00..3c5aaa8 100644
--- a/BUILD
+++ b/BUILD
@@ -15,6 +15,7 @@
     name = "zuul",
     srcs = glob(["src/main/java/**/*.java"]),
     resources = glob(["src/main/**/*"]),
+    deps = ["@commons-lang3//jar"],
     manifest_entries = [
         "Gerrit-PluginName: zuul",
         "Gerrit-Module: com.googlesource.gerrit.plugins.zuul.Module",
@@ -39,6 +40,7 @@
     visibility = ["//visibility:public"],
     exports = PLUGIN_DEPS + PLUGIN_TEST_DEPS + [
         ":zuul__plugin",
+        "@commons-lang3//jar",
     ],
 )
 
diff --git a/gr-zuul/gr-zuul.js b/gr-zuul/gr-zuul.js
index 4afc62b..89e5527 100644
--- a/gr-zuul/gr-zuul.js
+++ b/gr-zuul/gr-zuul.js
@@ -53,10 +53,48 @@
     return this.plugin.restApi().send('GET', url).then(crd => {
       this._crd = crd;
       this._crd_loaded = true;
-      this.setHidden(!(crd.depends_on.length || crd.needed_by.length));
+      this.setHidden(!(this._isDependsOnSectionVisible()
+                       || crd.needed_by.length));
     });
   }
 
+  // copied from gr-related-changes-list.js, which is inaccessible from here.
+  // Resolved uses of `this.ChangeStatus.[...]`, as that's inaccessible from here too.
+  // Removed _isIndirectAncestor check, as the needed data is inaccessible from here.
+  // Not all code paths are reachable, as we only have shallow ChangeInfo objects. We leave the
+  // code here nonetheless, to allow for easier updating from gr-related-changes-list.js.
+  _computeChangeStatusClass(change) {
+    const classes = ['status'];
+    if (change._revision_number != change._current_revision_number) {
+      classes.push('notCurrent');
+    } else if (change.submittable) {
+      classes.push('submittable');
+    } else if (change.status == 'NEW') {
+      classes.push('hidden');
+    }
+    return classes.join(' ');
+  }
+
+  // copied from gr-related-changes-list.js, which is inaccessible from here.
+  // Resolved uses of `this.ChangeStatus.[...]`, as that's inaccessible from here too.
+  // Removed _isIndirectAncestor check, as the needed data is inaccessible from here.
+  // Not all code paths are reachable, as we only have shallow ChangeInfo objects. We leave the
+  // code here nonetheless, to allow for easier updating from gr-related-changes-list.js.
+  _computeChangeStatus(change) {
+    switch (change.status) {
+      case 'MERGED':
+        return 'Merged';
+      case 'ABANDONED':
+        return 'Abandoned';
+    }
+    if (change._revision_number != change._current_revision_number) {
+      return 'Not current';
+    } else if (change.submittable) {
+      return 'Submittable';
+    }
+    return '';
+  }
+
   setHidden(hidden) {
     if (this.hidden != hidden) {
       this.hidden = hidden;
@@ -68,8 +106,13 @@
     }
   }
 
-  _computeDependencyUrl(changeId) {
-    return Gerrit.Nav.getUrlForSearchQuery(changeId);
+  _computeDependencyUrl(changeInfo) {
+    return Gerrit.Nav.getUrlForSearchQuery(changeInfo.change_id);
+  }
+
+  _isDependsOnSectionVisible() {
+    return !!(this._crd.depends_on_found.length
+              + this._crd.depends_on_missing.length);
   }
 }
 
diff --git a/gr-zuul/gr-zuul_html.js b/gr-zuul/gr-zuul_html.js
index 6827042..5e208d4 100644
--- a/gr-zuul/gr-zuul_html.js
+++ b/gr-zuul/gr-zuul_html.js
@@ -60,19 +60,28 @@
       .dependencyCycleDetected {
         color: #d17171;
       }
+      .missingFromThisServer {
+        color: #d17171;
+      }
+      .hidden {
+        display: none;
+      }
     </style>
     <template is="dom-if" if="[[_crd_loaded]]">
-      <template is="dom-if" if="[[_crd.depends_on.length]]">
+      <template is="dom-if" if="[[_isDependsOnSectionVisible()]]">
         <section class="related-changes-section">
           <h4>Depends on</h4>
-          <template is="dom-repeat" items="[[_crd.depends_on]]">
+          <template is="dom-repeat" items="[[_crd.depends_on_found]]">
             <div class="changeContainer zuulDependencyContainer">
               <a
                 href$="[[_computeDependencyUrl(item)]]"
-                title$="[[item]]"
+                title$="[[item.project]]: [[item.branch]]: [[item.subject]]"
               >
-                [[item]]
+                [[item.project]]: [[item.branch]]: [[item.subject]]
               </a>
+              <span class$="[[_computeChangeStatusClass(item)]]">
+                ([[_computeChangeStatus(item)]])
+              </span>
               <template is="dom-if" if="[[_crd.cycle]]">
                 <span class="status dependencyCycleDetected">
                   (Dependency cycle detected)
@@ -80,6 +89,16 @@
               </template>
             </div>
           </template>
+          <template is="dom-repeat" items="[[_crd.depends_on_missing]]">
+            <div class="changeContainer zuulDependencyContainer">
+              <span>
+                [[item]]
+              </span>
+              <span class="status missingFromThisServer">
+                (Missing from this server)
+              </span>
+            </div>
+          </template>
         </section>
       </template>
       <template is="dom-if" if="[[_crd.needed_by.length]]">
@@ -89,10 +108,13 @@
             <div class="changeContainer zuulDependencyContainer">
               <a
                 href$="[[_computeDependencyUrl(item)]]"
-                title$="[[item]]"
+                title$="[[item.project]]: [[item.branch]]: [[item.subject]]"
               >
-                [[item]]
+                [[item.project]]: [[item.branch]]: [[item.subject]]
               </a>
+              <span class$="[[_computeChangeStatusClass(item)]]">
+                ([[_computeChangeStatus(item)]])
+              </span>
               <template is="dom-if" if="[[_crd.cycle]]">
                 <span class="status dependencyCycleDetected">
                   (Dependency cycle detected)
diff --git a/src/main/java/com/googlesource/gerrit/plugins/zuul/CrdInfo.java b/src/main/java/com/googlesource/gerrit/plugins/zuul/CrdInfo.java
index 3788684..84fbfa4 100644
--- a/src/main/java/com/googlesource/gerrit/plugins/zuul/CrdInfo.java
+++ b/src/main/java/com/googlesource/gerrit/plugins/zuul/CrdInfo.java
@@ -14,10 +14,20 @@
 
 package com.googlesource.gerrit.plugins.zuul;
 
+import com.google.gerrit.extensions.common.ChangeInfo;
 import java.util.List;
 
+/** Cross-repository dependencies of a Change */
 public class CrdInfo {
-  public List<String> dependsOn;
-  public List<String> neededBy;
+  /** Shallow ChangeInfos of changes that depend on this Change and are available on this server */
+  public List<ChangeInfo> dependsOnFound;
+
+  /** Change-Ids of changes that depend on this Change and are not available on this server */
+  public List<String> dependsOnMissing;
+
+  /** Shallow ChangeInfos of changes that depend on this Change */
+  public List<ChangeInfo> neededBy;
+
+  /** true, if this change is contained in a dependency cycle */
   public boolean cycle;
 }
diff --git a/src/main/java/com/googlesource/gerrit/plugins/zuul/GetCrd.java b/src/main/java/com/googlesource/gerrit/plugins/zuul/GetCrd.java
index 6e8b1a7..e536b2a 100644
--- a/src/main/java/com/googlesource/gerrit/plugins/zuul/GetCrd.java
+++ b/src/main/java/com/googlesource/gerrit/plugins/zuul/GetCrd.java
@@ -14,82 +14,59 @@
 
 package com.googlesource.gerrit.plugins.zuul;
 
-import com.google.common.flogger.FluentLogger;
-import com.google.gerrit.entities.Change;
-import com.google.gerrit.entities.Project;
 import com.google.gerrit.extensions.common.ChangeInfo;
 import com.google.gerrit.extensions.restapi.AuthException;
 import com.google.gerrit.extensions.restapi.BadRequestException;
 import com.google.gerrit.extensions.restapi.Response;
 import com.google.gerrit.extensions.restapi.RestReadView;
-import com.google.gerrit.extensions.restapi.TopLevelResource;
 import com.google.gerrit.server.change.RevisionResource;
 import com.google.gerrit.server.permissions.PermissionBackendException;
-import com.google.gerrit.server.restapi.change.ChangesCollection;
-import com.google.gerrit.server.restapi.change.QueryChanges;
 import com.google.inject.Inject;
 import com.google.inject.Singleton;
+import com.googlesource.gerrit.plugins.zuul.util.DependsOnFetcher;
+import com.googlesource.gerrit.plugins.zuul.util.NeededByFetcher;
 import java.io.IOException;
 import java.util.ArrayList;
 import java.util.List;
-import java.util.regex.Matcher;
-import java.util.regex.Pattern;
+import java.util.stream.Collectors;
+import org.apache.commons.lang3.tuple.Pair;
 import org.eclipse.jgit.errors.RepositoryNotFoundException;
 
 @Singleton
 public class GetCrd implements RestReadView<RevisionResource> {
-  private static final FluentLogger logger = FluentLogger.forEnclosingClass();
-
-  private final ChangesCollection changes;
-  private final CommitMessageFetcher commitMessageFetcher;
+  private final DependsOnFetcher dependsOnFetcher;
+  private final NeededByFetcher neededByFetcher;
 
   @Inject
-  GetCrd(ChangesCollection changes, CommitMessageFetcher commitMessageFetcher) {
-    this.changes = changes;
-    this.commitMessageFetcher = commitMessageFetcher;
+  GetCrd(DependsOnFetcher dependsOnFetcher, NeededByFetcher neededByFetcher) {
+    this.dependsOnFetcher = dependsOnFetcher;
+    this.neededByFetcher = neededByFetcher;
   }
 
   @Override
-  @SuppressWarnings("unchecked")
   public Response<CrdInfo> apply(RevisionResource rsrc)
       throws RepositoryNotFoundException, IOException, BadRequestException, AuthException,
           PermissionBackendException {
     CrdInfo out = new CrdInfo();
-    out.dependsOn = new ArrayList<>();
-    out.neededBy = new ArrayList<>();
+    Pair<List<ChangeInfo>, List<String>> dependsOn = dependsOnFetcher.fetchForRevision(rsrc);
+    out.dependsOnFound = dependsOn.getLeft();
+    out.dependsOnMissing = dependsOn.getRight();
 
-    Change.Key thisId = rsrc.getChange().getKey();
+    out.neededBy = neededByFetcher.fetchForChangeKey(rsrc.getChange().getKey());
 
-    // get depends on info
-    Project.NameKey p = rsrc.getChange().getProject();
-    String rev = rsrc.getPatchSet().commitId().getName();
-    String commitMsg = commitMessageFetcher.fetch(p, rev);
-    Pattern pattern = Pattern.compile("[Dd]epends-[Oo]n:? (I[0-9a-f]{8,40})", Pattern.DOTALL);
-    Matcher matcher = pattern.matcher(commitMsg);
-    while (matcher.find()) {
-      String otherId = matcher.group(1);
-      logger.atFinest().log("Change %s depends on change %s", thisId, otherId);
-      out.dependsOn.add(otherId);
-    }
+    List<String> dependsOnAllKeys = new ArrayList<>(out.dependsOnMissing);
+    dependsOnAllKeys.addAll(
+        out.dependsOnFound.stream()
+            .map(changeInfo -> changeInfo.changeId)
+            .collect(Collectors.toList()));
 
-    // get needed by info
-    QueryChanges query = changes.list();
-    String neededByQuery = "message:" + thisId + " -change:" + thisId;
-    query.addQuery(neededByQuery);
-    Response<List<?>> response = query.apply(TopLevelResource.INSTANCE);
-    List<ChangeInfo> changes = (List<ChangeInfo>) response.value();
-    // check for dependency cycles
-    for (ChangeInfo other : changes) {
-      String otherId = other.changeId;
-      logger.atFinest().log("Change %s needed by %s", thisId, otherId);
-      if (out.dependsOn.contains(otherId)) {
-        logger.atFiner().log(
-            "Detected dependency cycle between changes %s and %s", thisId, otherId);
+    out.cycle = false;
+    for (ChangeInfo changeInfo : out.neededBy) {
+      if (dependsOnAllKeys.contains(changeInfo.changeId)) {
         out.cycle = true;
+        break;
       }
-      out.neededBy.add(otherId);
     }
-
     return Response.ok(out);
   }
 }
diff --git a/src/main/java/com/googlesource/gerrit/plugins/zuul/CommitMessageFetcher.java b/src/main/java/com/googlesource/gerrit/plugins/zuul/util/CommitMessageFetcher.java
similarity index 69%
rename from src/main/java/com/googlesource/gerrit/plugins/zuul/CommitMessageFetcher.java
rename to src/main/java/com/googlesource/gerrit/plugins/zuul/util/CommitMessageFetcher.java
index 961cad8..6bb2d4e 100644
--- a/src/main/java/com/googlesource/gerrit/plugins/zuul/CommitMessageFetcher.java
+++ b/src/main/java/com/googlesource/gerrit/plugins/zuul/util/CommitMessageFetcher.java
@@ -12,9 +12,11 @@
 // See the License for the specific language governing permissions and
 // limitations under the License.
 
-package com.googlesource.gerrit.plugins.zuul;
+package com.googlesource.gerrit.plugins.zuul.util;
 
 import com.google.gerrit.entities.Project;
+import com.google.gerrit.extensions.common.ChangeInfo;
+import com.google.gerrit.extensions.common.CommitInfo;
 import com.google.gerrit.server.git.GitRepositoryManager;
 import com.google.inject.Inject;
 import java.io.IOException;
@@ -40,4 +42,19 @@
       return commit.getFullMessage();
     }
   }
+
+  /**
+   * Extracts the commit message of the most current revision of a change.
+   *
+   * <p>The ChangeInfo must have the {@link CommitInfo} of at least the most current revision
+   * loaded.
+   *
+   * @param changeInfo The ChangeInfo to extract the commit message from
+   * @return the extracted commit message
+   */
+  public String fetch(ChangeInfo changeInfo) {
+    String current = changeInfo.currentRevision;
+    CommitInfo commitInfo = changeInfo.revisions.get(current).commit;
+    return commitInfo.message;
+  }
 }
diff --git a/src/main/java/com/googlesource/gerrit/plugins/zuul/util/DependsOnExtractor.java b/src/main/java/com/googlesource/gerrit/plugins/zuul/util/DependsOnExtractor.java
new file mode 100644
index 0000000..5860940
--- /dev/null
+++ b/src/main/java/com/googlesource/gerrit/plugins/zuul/util/DependsOnExtractor.java
@@ -0,0 +1,36 @@
+// Copyright (C) 2020 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.googlesource.gerrit.plugins.zuul.util;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.regex.Matcher;
+import java.util.regex.Pattern;
+
+/** Extracts dependency information from texts. */
+public class DependsOnExtractor {
+  public List<String> extract(String commitMessage) {
+    // TODO Add support for URL based `Depends-On` references.
+    List<String> dependsOn = new ArrayList<>();
+    Pattern pattern =
+        Pattern.compile(
+            "^Depends-On: (I[0-9a-f]{40})\\s*$", Pattern.MULTILINE | Pattern.CASE_INSENSITIVE);
+    Matcher matcher = pattern.matcher(commitMessage);
+    while (matcher.find()) {
+      String key = matcher.group(1);
+      dependsOn.add(key);
+    }
+    return dependsOn;
+  }
+}
diff --git a/src/main/java/com/googlesource/gerrit/plugins/zuul/util/DependsOnFetcher.java b/src/main/java/com/googlesource/gerrit/plugins/zuul/util/DependsOnFetcher.java
new file mode 100644
index 0000000..0d599a1
--- /dev/null
+++ b/src/main/java/com/googlesource/gerrit/plugins/zuul/util/DependsOnFetcher.java
@@ -0,0 +1,95 @@
+// Copyright (C) 2020 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.googlesource.gerrit.plugins.zuul.util;
+
+import com.google.common.collect.Lists;
+import com.google.gerrit.entities.Project;
+import com.google.gerrit.extensions.common.ChangeInfo;
+import com.google.gerrit.extensions.restapi.AuthException;
+import com.google.gerrit.extensions.restapi.BadRequestException;
+import com.google.gerrit.extensions.restapi.Response;
+import com.google.gerrit.extensions.restapi.TopLevelResource;
+import com.google.gerrit.server.change.RevisionResource;
+import com.google.gerrit.server.permissions.PermissionBackendException;
+import com.google.gerrit.server.restapi.change.ChangesCollection;
+import com.google.gerrit.server.restapi.change.QueryChanges;
+import com.google.inject.Inject;
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+import org.apache.commons.lang3.tuple.ImmutablePair;
+import org.apache.commons.lang3.tuple.Pair;
+import org.eclipse.jgit.errors.RepositoryNotFoundException;
+
+/** Fetches the Depends-On part of cross repository dependencies. */
+public class DependsOnFetcher {
+  private final ChangesCollection changes;
+  private final CommitMessageFetcher commitMessageFetcher;
+  private final DependsOnExtractor dependsOnExtractor;
+
+  @Inject
+  public DependsOnFetcher(
+      ChangesCollection changes,
+      CommitMessageFetcher commitMessageFetcher,
+      DependsOnExtractor dependsOnExtractor) {
+    this.changes = changes;
+    this.commitMessageFetcher = commitMessageFetcher;
+    this.dependsOnExtractor = dependsOnExtractor;
+  }
+
+  @SuppressWarnings("unchecked")
+  private List<ChangeInfo> fetchChangeInfosForChangeKeys(List<String> keys)
+      throws BadRequestException, AuthException, PermissionBackendException {
+    List<ChangeInfo> ret;
+    if (keys.isEmpty()) {
+      ret = new ArrayList<>();
+    } else {
+      QueryChanges query = changes.list();
+      String queryString = "change:" + String.join(" OR change:", keys);
+      query.addQuery(queryString);
+      Response<List<?>> response = query.apply(TopLevelResource.INSTANCE);
+      ret = (List<ChangeInfo>) response.value();
+    }
+    return ret;
+  }
+
+  public Pair<List<ChangeInfo>, List<String>> fetchForRevision(RevisionResource rsrc)
+      throws RepositoryNotFoundException, IOException, BadRequestException, AuthException,
+          PermissionBackendException {
+    Project.NameKey p = rsrc.getChange().getProject();
+    String rev = rsrc.getPatchSet().commitId().getName();
+    String commitMsg = commitMessageFetcher.fetch(p, rev);
+
+    List<String> extractedChangeKeys = dependsOnExtractor.extract(commitMsg);
+    List<ChangeInfo> foundChangeInfos = fetchChangeInfosForChangeKeys(extractedChangeKeys);
+
+    // `extracted` and `found` need not agree in size. It might be that a Change-Id from
+    // `extracted` matches more than one Change (E.g.: cherry-picked to different branch). And it
+    // might be that a Change-Id from `extracted` does not yield a result.
+    // So we need to check that `found` holds at least one ChangeInfo for each Change-Id in
+    // `extractedDependsOn`.
+
+    List<String> resultMissing = Lists.newArrayList(extractedChangeKeys);
+    List<ChangeInfo> resultFound = new ArrayList<>(extractedChangeKeys.size());
+
+    for (ChangeInfo changeInfo : foundChangeInfos) {
+      String changeId = changeInfo.changeId.toString();
+      if (extractedChangeKeys.contains(changeId)) {
+        resultMissing.remove(changeId);
+        resultFound.add(changeInfo);
+      }
+    }
+    return new ImmutablePair<>(resultFound, resultMissing);
+  }
+}
diff --git a/src/main/java/com/googlesource/gerrit/plugins/zuul/util/NeededByFetcher.java b/src/main/java/com/googlesource/gerrit/plugins/zuul/util/NeededByFetcher.java
new file mode 100644
index 0000000..7475fb4
--- /dev/null
+++ b/src/main/java/com/googlesource/gerrit/plugins/zuul/util/NeededByFetcher.java
@@ -0,0 +1,72 @@
+// Copyright (C) 2020 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.googlesource.gerrit.plugins.zuul.util;
+
+import com.google.gerrit.entities.Change;
+import com.google.gerrit.extensions.client.ListChangesOption;
+import com.google.gerrit.extensions.common.ChangeInfo;
+import com.google.gerrit.extensions.restapi.AuthException;
+import com.google.gerrit.extensions.restapi.BadRequestException;
+import com.google.gerrit.extensions.restapi.Response;
+import com.google.gerrit.extensions.restapi.TopLevelResource;
+import com.google.gerrit.server.permissions.PermissionBackendException;
+import com.google.gerrit.server.restapi.change.ChangesCollection;
+import com.google.gerrit.server.restapi.change.QueryChanges;
+import com.google.inject.Inject;
+import java.util.ArrayList;
+import java.util.List;
+
+/** Fetches the Needed-By part of cross repository dependencies. */
+public class NeededByFetcher {
+  private final ChangesCollection changes;
+  private final CommitMessageFetcher commitMessageFetcher;
+  private final DependsOnExtractor dependsOnExtractor;
+
+  @Inject
+  public NeededByFetcher(
+      ChangesCollection changes,
+      CommitMessageFetcher commitMessageFetcher,
+      DependsOnExtractor dependsOnExtractor) {
+    this.changes = changes;
+    this.commitMessageFetcher = commitMessageFetcher;
+    this.dependsOnExtractor = dependsOnExtractor;
+  }
+
+  public List<ChangeInfo> fetchForChangeKey(Change.Key key)
+      throws BadRequestException, AuthException, PermissionBackendException {
+    // TODO Add support for URL based `Depends-On` references.
+    String keyString = key.toString();
+    List<ChangeInfo> neededBy = new ArrayList<>();
+
+    QueryChanges query = changes.list();
+    String neededByQuery = "message:" + keyString + " -change:" + keyString;
+    query.addOption(ListChangesOption.CURRENT_REVISION);
+    query.addOption(ListChangesOption.CURRENT_COMMIT);
+    query.addQuery(neededByQuery);
+    Response<List<?>> response = query.apply(TopLevelResource.INSTANCE);
+    @SuppressWarnings("unchecked")
+    List<ChangeInfo> changes = (List<ChangeInfo>) response.value();
+    for (ChangeInfo changeInfo : changes) {
+      // The search found the key somewhere in the commit message. But this need not be a
+      // `Depends-On`. `key` might be mentioned for a completely different reason. So we need to
+      // check if `key` occurs in a `Depends-On`.
+      String commitMessage = commitMessageFetcher.fetch(changeInfo);
+      List<String> dependencies = dependsOnExtractor.extract(commitMessage);
+      if (dependencies.contains(keyString)) {
+        neededBy.add(changeInfo);
+      }
+    }
+    return neededBy;
+  }
+}
diff --git a/src/main/resources/Documentation/about.md b/src/main/resources/Documentation/about.md
index 19d67ec..dfa5148 100644
--- a/src/main/resources/Documentation/about.md
+++ b/src/main/resources/Documentation/about.md
@@ -1,5 +1,21 @@
-The @PLUGIN@ plugin detects Zuul [cross repository dependencies] (CRD) in
-commit messages.
+The @PLUGIN@ plugin detects Zuul [cross repository dependencies]&nbsp;(CRD) in
+commit messages and displays them on the Gerrit UI as "Depends on" and "Needed
+by" sections in the related changes section.
 
-[cross repository dependencies]: http://docs.openstack.org/infra/zuul/gating.html#cross-repository-dependencies
-[Cycles]: http://docs.openstack.org/infra/zuul/gating.html#cycles
+![user interface overview](images/overview.png)
+
+[Dependency cycles] (although currently only direct dependencies are considered) get highlighted
+
+![cycles screenshot](images/cycles.png)
+
+And dependencies that are not available on the server get highlighted too.
+
+![missing dependencies screenshot](images/missing.png)
+
+The cross repository dependencies are also exposed through the [REST API](rest-api-changes.html).
+
+This plugin currently does not support URL based dependencies, but only
+`Change-Id` dependencies, which got deprecated in Zuul v3.
+
+[cross repository dependencies]: https://zuul-ci.org/docs/zuul/discussion/gating.html#cross-project-dependencies
+[Dependency cycles]: https://zuul-ci.org/docs/zuul/discussion/gating.html#cycles
diff --git a/src/main/resources/Documentation/images/cycles.png b/src/main/resources/Documentation/images/cycles.png
new file mode 100644
index 0000000..8cad8b3
--- /dev/null
+++ b/src/main/resources/Documentation/images/cycles.png
Binary files differ
diff --git a/src/main/resources/Documentation/images/missing.png b/src/main/resources/Documentation/images/missing.png
new file mode 100644
index 0000000..2fc4516
--- /dev/null
+++ b/src/main/resources/Documentation/images/missing.png
Binary files differ
diff --git a/src/main/resources/Documentation/images/overview.png b/src/main/resources/Documentation/images/overview.png
new file mode 100644
index 0000000..172112e
--- /dev/null
+++ b/src/main/resources/Documentation/images/overview.png
Binary files differ
diff --git a/src/main/resources/Documentation/rest-api-changes.md b/src/main/resources/Documentation/rest-api-changes.md
index 4f24231..9095d96 100644
--- a/src/main/resources/Documentation/rest-api-changes.md
+++ b/src/main/resources/Documentation/rest-api-changes.md
@@ -12,7 +12,7 @@
 
 ### <a id="get-crd"> Get CRD
 
-__GET__ /changes/{change-id}/revisions/{revision-id}/@PLUGIN@~crd
+'GET /changes/[\{change-id\}](../../../Documentation/rest-api-changes.html#change-id)/revisions/[\{revision-id\}](../../../Documentation/rest-api-changes.html#revision-id)/crd'
 
 Gets the zuul [CRD](#crd-info) for a change.  Please refer to the
 general [changes rest api](../../../Documentation/rest-api-changes.html#get-review)
@@ -21,9 +21,11 @@
 #### Request
 
 ```
-  GET /changes/myProject~master~I8473b95934b5732ac55d26311a706c9c2bde9940/revisions/674ac754f91e64a0efb8087e59a176484bd534d1/@PLUGIN@~crd HTTP/1.0
+  GET /changes/myProject~master~I8473b95934b5732ac55d26311a706c9c2bde9940/revisions/674ac754f91e64a0efb8087e59a176484bd534d1/crd HTTP/1.0
 ```
 
+As response a [CrdInfo](#crd-info) entity is returned that describes the cross-repository dependencies.
+
 #### Response
 
 ```
@@ -33,12 +35,25 @@
 
   )]}'
   {
-    "depends_on": [
-      "Ic79ed94daa9b58527139aadba1b0d59d1f54754b",
-      "I66853bf0c18e60f8de14d44dfb7c2ca1c3793111"
+    "depends_on_found": [
+      {
+        "id": "repo1~master~Ic0f5bcc8f998dfc0f1b7164de7a824f7832d4abe",
+        "project": "zuul/repo1",
+        "branch": "master",
+        [...]
+      }
+    ],
+    "depends_on_missing": [
+      "Ib01834990d3791330d65c469e9a3f93db6eb41f0",
+      "Ic0f5bcc8f998dfc0f1b7164de7a824f7832d4abe",
     ],
     "needed_by": [
-      "I66853bf0c18e60f8de14d44dfb7c2ca1c379311d"
+      {
+        "id": "another%2Frepo~master~I8944323ed34d55af7a17a48c8d8509f3cf62b6bf",
+        "project": "zuul/repo1",
+        "branch": "master",
+        [...]
+      }
     ],
     "cycle": false
   }
@@ -51,11 +66,12 @@
 
 The `CrdInfo` entity shows zuul dependencies on a patch set.
 
-|Field Name |Description|
-|:----------|:----------|
-|depends_on |List of changes that this change depends on|
-|needed_by  |List of changes that is dependent on this change|
-|cycle      |Whether this change is in a circular dependency chain|
+|Field Name         |Description|
+|:------------------|:----------|
+|depends_on_found   |List of shallow [ChangeInfo](../../../Documentation/rest-api-changes.html#change-info) entities. One for each Change that is available on this server and this change depends on|
+|depends_on_missing |List of Change-Ids. One for each change that is not available on this server although this change depends on|
+|needed_by          |List of shallow [ChangeInfo](../../../Documentation/rest-api-changes.html#change-info) entities. One for each change that is dependent on this change|
+|cycle              |Whether this change is in a circular dependency chain|
 
 
 SEE ALSO
diff --git a/src/test/java/com/googlesource/gerrit/plugins/zuul/GetCrdTest.java b/src/test/java/com/googlesource/gerrit/plugins/zuul/GetCrdTest.java
index 019f5c3..71a46ee 100644
--- a/src/test/java/com/googlesource/gerrit/plugins/zuul/GetCrdTest.java
+++ b/src/test/java/com/googlesource/gerrit/plugins/zuul/GetCrdTest.java
@@ -14,210 +14,242 @@
 package com.googlesource.gerrit.plugins.zuul;
 
 import static com.google.common.truth.Truth.assertThat;
-import static org.mockito.Mockito.doAnswer;
 import static org.mockito.Mockito.mock;
 import static org.mockito.Mockito.when;
 
-import com.google.gerrit.entities.Account;
-import com.google.gerrit.entities.BranchNameKey;
 import com.google.gerrit.entities.Change;
-import com.google.gerrit.entities.PatchSet;
-import com.google.gerrit.entities.Project;
 import com.google.gerrit.extensions.common.ChangeInfo;
 import com.google.gerrit.extensions.restapi.Response;
-import com.google.gerrit.extensions.restapi.TopLevelResource;
 import com.google.gerrit.server.change.RevisionResource;
-import com.google.gerrit.server.restapi.change.ChangesCollection;
-import com.google.gerrit.server.restapi.change.QueryChanges;
-import java.sql.Timestamp;
+import com.googlesource.gerrit.plugins.zuul.util.DependsOnFetcher;
+import com.googlesource.gerrit.plugins.zuul.util.NeededByFetcher;
 import java.util.ArrayList;
+import java.util.HashMap;
 import java.util.List;
-import java.util.concurrent.atomic.AtomicBoolean;
-import org.eclipse.jgit.lib.ObjectId;
+import java.util.Map;
+import org.apache.commons.lang3.tuple.ImmutablePair;
 import org.junit.Test;
-import org.mockito.invocation.InvocationOnMock;
-import org.mockito.stubbing.Answer;
 
 public class GetCrdTest {
-  private ChangesCollection changes;
-  private CommitMessageFetcher commitMessageFetcher;
   private RevisionResource rsrc;
+  private DependsOnFetcher dependsOnFetcher;
+  private NeededByFetcher neededByFetcher;
+  private Map<Integer, ChangeInfo> changeInfos = new HashMap<>();
 
   @Test
   public void testNoDependencies() throws Exception {
-    String commitMessage = "subject";
-    configureMocks(commitMessage, new ArrayList<>());
+    configureMocks(new ArrayList<>(), new ArrayList<>(), new ArrayList<>());
 
     GetCrd getCrd = createGetCrd();
     Response<CrdInfo> response = getCrd.apply(rsrc);
 
     assertThat(response.statusCode()).isEqualTo(200);
     CrdInfo crdInfo = response.value();
-    assertThat(crdInfo.dependsOn).isEmpty();
+    assertThat(crdInfo.dependsOnFound).isEmpty();
+    assertThat(crdInfo.dependsOnMissing).isEmpty();
     assertThat(crdInfo.neededBy).isEmpty();
     assertThat(crdInfo.cycle).isFalse();
   }
 
   @Test
-  public void testSingleDependsOn() throws Exception {
-    String commitMessage = "subject\nDepends-On: I00000000";
-    configureMocks(commitMessage, new ArrayList<>());
+  public void testSingleFoundDependsOn() throws Exception {
+    ArrayList<ChangeInfo> dependsOnFound = new ArrayList<>();
+    dependsOnFound.add(getChangeInfo(0));
+
+    configureMocks(dependsOnFound, new ArrayList<>(), new ArrayList<>());
 
     GetCrd getCrd = createGetCrd();
     Response<CrdInfo> response = getCrd.apply(rsrc);
 
     assertThat(response.statusCode()).isEqualTo(200);
     CrdInfo crdInfo = response.value();
-    assertThat(crdInfo.dependsOn).containsExactly("I00000000");
+    assertThat(crdInfo.dependsOnFound).containsExactly(getChangeInfo(0));
+    assertThat(crdInfo.dependsOnMissing).isEmpty();
     assertThat(crdInfo.neededBy).isEmpty();
     assertThat(crdInfo.cycle).isFalse();
   }
 
   @Test
-  public void testMultipleDependsOn() throws Exception {
-    String commitMessage =
-        "subject\nDepends-On: I00000000\nDepends-On: I00000002\nDepends-On: I00000004";
-    configureMocks(commitMessage, new ArrayList<>());
+  public void testSingleMissingDependsOn() throws Exception {
+    ArrayList<String> dependsOnMissing = new ArrayList<>();
+    dependsOnMissing.add(getChangeKey(0));
+
+    configureMocks(new ArrayList<>(), dependsOnMissing, new ArrayList<>());
 
     GetCrd getCrd = createGetCrd();
     Response<CrdInfo> response = getCrd.apply(rsrc);
 
     assertThat(response.statusCode()).isEqualTo(200);
     CrdInfo crdInfo = response.value();
-    assertThat(crdInfo.dependsOn).containsExactly("I00000000", "I00000002", "I00000004");
+    assertThat(crdInfo.dependsOnFound).isEmpty();
+    assertThat(crdInfo.dependsOnMissing).containsExactly(getChangeKey(0));
+    assertThat(crdInfo.neededBy).isEmpty();
+    assertThat(crdInfo.cycle).isFalse();
+  }
+
+  @Test
+  public void testMultipleFoundDependsOn() throws Exception {
+    ArrayList<ChangeInfo> dependsOnFound = new ArrayList<>();
+    dependsOnFound.add(getChangeInfo(0));
+    dependsOnFound.add(getChangeInfo(2));
+    dependsOnFound.add(getChangeInfo(4));
+
+    configureMocks(dependsOnFound, new ArrayList<>(), new ArrayList<>());
+
+    GetCrd getCrd = createGetCrd();
+    Response<CrdInfo> response = getCrd.apply(rsrc);
+
+    assertThat(response.statusCode()).isEqualTo(200);
+    CrdInfo crdInfo = response.value();
+    assertThat(crdInfo.dependsOnFound)
+        .containsExactly(getChangeInfo(0), getChangeInfo(2), getChangeInfo(4));
+    assertThat(crdInfo.dependsOnMissing).isEmpty();
+    assertThat(crdInfo.neededBy).isEmpty();
+    assertThat(crdInfo.cycle).isFalse();
+  }
+
+  @Test
+  public void testMultipleMissingDependsOn() throws Exception {
+    ArrayList<String> dependsOnMissing = new ArrayList<>();
+    dependsOnMissing.add(getChangeKey(0));
+    dependsOnMissing.add(getChangeKey(2));
+    dependsOnMissing.add(getChangeKey(4));
+
+    configureMocks(new ArrayList<>(), dependsOnMissing, new ArrayList<>());
+
+    GetCrd getCrd = createGetCrd();
+    Response<CrdInfo> response = getCrd.apply(rsrc);
+
+    assertThat(response.statusCode()).isEqualTo(200);
+    CrdInfo crdInfo = response.value();
+    assertThat(crdInfo.dependsOnFound).isEmpty();
+    assertThat(crdInfo.dependsOnMissing)
+        .containsExactly(getChangeKey(0), getChangeKey(2), getChangeKey(4));
     assertThat(crdInfo.neededBy).isEmpty();
     assertThat(crdInfo.cycle).isFalse();
   }
 
   @Test
   public void testSingleNeededBy() throws Exception {
-    String commitMessage = "subject";
-    List<ChangeInfo> searchResults = new ArrayList<>();
-    searchResults.add(changeInfo("I00000001"));
-    configureMocks(commitMessage, searchResults);
+    List<ChangeInfo> neededBy = new ArrayList<>();
+    neededBy.add(getChangeInfo(1));
+
+    configureMocks(new ArrayList<>(), new ArrayList<>(), neededBy);
 
     GetCrd getCrd = createGetCrd();
     Response<CrdInfo> response = getCrd.apply(rsrc);
 
     assertThat(response.statusCode()).isEqualTo(200);
     CrdInfo crdInfo = response.value();
-    assertThat(crdInfo.dependsOn).isEmpty();
-    assertThat(crdInfo.neededBy).containsExactly("I00000001");
+    assertThat(crdInfo.dependsOnFound).isEmpty();
+    assertThat(crdInfo.dependsOnMissing).isEmpty();
+    assertThat(crdInfo.neededBy).containsExactly(getChangeInfo(1));
     assertThat(crdInfo.cycle).isFalse();
   }
 
   @Test
   public void testMultipleNeededBy() throws Exception {
-    String commitMessage = "subject";
-    List<ChangeInfo> searchResults = new ArrayList<>();
-    searchResults.add(changeInfo("I00000001"));
-    searchResults.add(changeInfo("I00000003"));
-    searchResults.add(changeInfo("I00000005"));
-    configureMocks(commitMessage, searchResults);
+    List<ChangeInfo> neededBy = new ArrayList<>();
+    neededBy.add(getChangeInfo(1));
+    neededBy.add(getChangeInfo(3));
+    neededBy.add(getChangeInfo(5));
+
+    configureMocks(new ArrayList<>(), new ArrayList<>(), neededBy);
 
     GetCrd getCrd = createGetCrd();
     Response<CrdInfo> response = getCrd.apply(rsrc);
 
     assertThat(response.statusCode()).isEqualTo(200);
     CrdInfo crdInfo = response.value();
-    assertThat(crdInfo.dependsOn).isEmpty();
-    assertThat(crdInfo.neededBy).containsExactly("I00000001", "I00000003", "I00000005");
+    assertThat(crdInfo.dependsOnFound).isEmpty();
+    assertThat(crdInfo.dependsOnMissing).isEmpty();
+    assertThat(crdInfo.neededBy)
+        .containsExactly(getChangeInfo(1), getChangeInfo(3), getChangeInfo(5));
     assertThat(crdInfo.cycle).isFalse();
   }
 
   @Test
   public void testMixed() throws Exception {
-    String commitMessage = "subject\nDepends-On: I00000002\nDepends-On: I00000004";
-    List<ChangeInfo> searchResults = new ArrayList<>();
-    searchResults.add(changeInfo("I00000001"));
-    searchResults.add(changeInfo("I00000003"));
-    configureMocks(commitMessage, searchResults);
+    List<ChangeInfo> dependsOnFound = new ArrayList<>();
+    dependsOnFound.add(getChangeInfo(2));
+    dependsOnFound.add(getChangeInfo(4));
+
+    List<String> dependsOnMissing = new ArrayList<>();
+    dependsOnMissing.add(getChangeKey(5));
+    dependsOnMissing.add(getChangeKey(6));
+
+    List<ChangeInfo> neededBy = new ArrayList<>();
+    neededBy.add(getChangeInfo(1));
+    neededBy.add(getChangeInfo(3));
+
+    configureMocks(dependsOnFound, dependsOnMissing, neededBy);
 
     GetCrd getCrd = createGetCrd();
     Response<CrdInfo> response = getCrd.apply(rsrc);
 
     assertThat(response.statusCode()).isEqualTo(200);
     CrdInfo crdInfo = response.value();
-    assertThat(crdInfo.dependsOn).containsExactly("I00000002", "I00000004");
-    assertThat(crdInfo.neededBy).containsExactly("I00000001", "I00000003");
+    assertThat(crdInfo.dependsOnFound).containsExactly(getChangeInfo(2), getChangeInfo(4));
+    assertThat(crdInfo.dependsOnMissing).containsExactly(getChangeKey(5), getChangeKey(6));
+    assertThat(crdInfo.neededBy).containsExactly(getChangeInfo(1), getChangeInfo(3));
     assertThat(crdInfo.cycle).isFalse();
   }
 
   @Test
   public void testSimpleCycle() throws Exception {
-    String commitMessage = "subject\nDepends-On: I00000001";
-    List<ChangeInfo> searchResults = new ArrayList<>();
-    searchResults.add(changeInfo("I00000001"));
-    configureMocks(commitMessage, searchResults);
+    List<ChangeInfo> dependsOn = new ArrayList<>();
+    dependsOn.add(getChangeInfo(1));
+
+    List<ChangeInfo> neededBy = new ArrayList<>();
+    neededBy.add(getChangeInfo(1));
+
+    configureMocks(dependsOn, new ArrayList<>(), neededBy);
 
     GetCrd getCrd = createGetCrd();
     Response<CrdInfo> response = getCrd.apply(rsrc);
 
     assertThat(response.statusCode()).isEqualTo(200);
     CrdInfo crdInfo = response.value();
-    assertThat(crdInfo.dependsOn).containsExactly("I00000001");
-    assertThat(crdInfo.neededBy).containsExactly("I00000001");
+    assertThat(crdInfo.dependsOnFound).containsExactly(getChangeInfo(1));
+    assertThat(crdInfo.dependsOnMissing).isEmpty();
+    assertThat(crdInfo.neededBy).containsExactly(getChangeInfo(1));
     assertThat(crdInfo.cycle).isTrue();
   }
 
-  public void configureMocks(String commitMessage, final List<ChangeInfo> searchResult)
+  public void configureMocks(
+      final List<ChangeInfo> dependsOnFound,
+      final List<String> dependsOnMissing,
+      final List<ChangeInfo> neededBy)
       throws Exception {
-    String commitId = "0123456789012345678901234567890123456789";
-
-    Project.NameKey projectNameKey = Project.nameKey("projectFoo");
-
-    PatchSet patchSet = mock(PatchSet.class);
-    when(patchSet.commitId()).thenReturn(ObjectId.fromString(commitId));
-
-    Change change =
-        new Change(
-            Change.key("I0123456789"),
-            Change.id(4711),
-            Account.id(23),
-            BranchNameKey.create(projectNameKey, "branchBar"),
-            new Timestamp(0));
-
+    Change.Key changeKey = Change.key("I0123456789");
+    Change change = new Change(changeKey, null, null, null, null);
     rsrc = mock(RevisionResource.class);
     when(rsrc.getChange()).thenReturn(change);
-    when(rsrc.getPatchSet()).thenReturn(patchSet);
 
-    QueryChanges queryChanges = mock(QueryChanges.class);
-    final AtomicBoolean addedQuery = new AtomicBoolean(false);
-    doAnswer(
-            new Answer<Void>() {
-              @Override
-              public Void answer(InvocationOnMock invocation) throws Throwable {
-                addedQuery.getAndSet(true);
-                return null;
-              }
-            })
-        .when(queryChanges)
-        .addQuery("message:I0123456789 -change:I0123456789");
-    when(queryChanges.apply(TopLevelResource.INSTANCE))
-        .thenAnswer(
-            new Answer<Response<List<ChangeInfo>>>() {
+    dependsOnFetcher = mock(DependsOnFetcher.class);
+    when(dependsOnFetcher.fetchForRevision(rsrc))
+        .thenReturn(new ImmutablePair<>(dependsOnFound, dependsOnMissing));
 
-              @Override
-              public Response<List<ChangeInfo>> answer(InvocationOnMock invocation)
-                  throws Throwable {
-                return Response.ok(addedQuery.get() ? searchResult : null);
-              }
-            });
-
-    changes = mock(ChangesCollection.class);
-    when(changes.list()).thenReturn(queryChanges);
-
-    commitMessageFetcher = mock(CommitMessageFetcher.class);
-    when(commitMessageFetcher.fetch(projectNameKey, commitId)).thenReturn(commitMessage);
+    neededByFetcher = mock(NeededByFetcher.class);
+    when(neededByFetcher.fetchForChangeKey(changeKey)).thenReturn(neededBy);
   }
 
-  private ChangeInfo changeInfo(String changeId) {
-    ChangeInfo changeInfo = new ChangeInfo();
-    changeInfo.changeId = changeId;
-    return changeInfo;
+  private String getChangeKey(int keyEnding) {
+    return "I0123456789abcdef0000000000000000000" + (10000 + keyEnding);
+  }
+
+  private ChangeInfo getChangeInfo(int keyEnding) {
+    return changeInfos.computeIfAbsent(
+        keyEnding,
+        neededKeyEnding -> {
+          ChangeInfo changeInfo = new ChangeInfo();
+          changeInfo.changeId = getChangeKey(neededKeyEnding);
+          changeInfo._number = neededKeyEnding;
+          return changeInfo;
+        });
   }
 
   private GetCrd createGetCrd() {
-    return new GetCrd(changes, commitMessageFetcher);
+    return new GetCrd(dependsOnFetcher, neededByFetcher);
   }
 }
diff --git a/src/test/java/com/googlesource/gerrit/plugins/zuul/CommitMessageFetcherTest.java b/src/test/java/com/googlesource/gerrit/plugins/zuul/util/CommitMessageFetcherTest.java
similarity index 76%
rename from src/test/java/com/googlesource/gerrit/plugins/zuul/CommitMessageFetcherTest.java
rename to src/test/java/com/googlesource/gerrit/plugins/zuul/util/CommitMessageFetcherTest.java
index edda09e..905683c 100644
--- a/src/test/java/com/googlesource/gerrit/plugins/zuul/CommitMessageFetcherTest.java
+++ b/src/test/java/com/googlesource/gerrit/plugins/zuul/util/CommitMessageFetcherTest.java
@@ -11,7 +11,7 @@
 // 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.googlesource.gerrit.plugins.zuul;
+package com.googlesource.gerrit.plugins.zuul.util;
 
 import static com.google.common.truth.Truth.assertThat;
 import static com.google.gerrit.testing.GerritJUnit.assertThrows;
@@ -21,9 +21,13 @@
 import static org.mockito.Mockito.when;
 
 import com.google.gerrit.entities.Project;
+import com.google.gerrit.extensions.common.ChangeInfo;
+import com.google.gerrit.extensions.common.CommitInfo;
+import com.google.gerrit.extensions.common.RevisionInfo;
 import com.google.gerrit.server.git.GitRepositoryManager;
 import java.io.IOException;
 import java.math.BigInteger;
+import java.util.HashMap;
 import java.util.HashSet;
 import java.util.Set;
 import org.eclipse.jgit.errors.MissingObjectException;
@@ -84,6 +88,34 @@
     assertThat(commitMessage).isEqualTo("CommitMsg\n");
   }
 
+  @Test
+  public void testFetchChangeInfoSingleRevision() {
+    ChangeInfo changeInfo = new ChangeInfo();
+    changeInfo.currentRevision = "foo";
+    changeInfo.revisions = new HashMap<>();
+    changeInfo.revisions.put("foo", createRevisionInfo("CommitMsg"));
+
+    CommitMessageFetcher fetcher = createCommitMessageFetcher();
+    String commitMessage = fetcher.fetch(changeInfo);
+
+    assertThat(commitMessage).isEqualTo("CommitMsg");
+  }
+
+  @Test
+  public void testFetchChangeInfoMultipleRevisions() {
+    ChangeInfo changeInfo = new ChangeInfo();
+    changeInfo.currentRevision = "bar";
+    changeInfo.revisions = new HashMap<>();
+    changeInfo.revisions.put("foo", createRevisionInfo("CommitMsgFoo"));
+    changeInfo.revisions.put("bar", createRevisionInfo("CommitMsgBar"));
+    changeInfo.revisions.put("baz", createRevisionInfo("CommitMsgBaz"));
+
+    CommitMessageFetcher fetcher = createCommitMessageFetcher();
+    String commitMessage = fetcher.fetch(changeInfo);
+
+    assertThat(commitMessage).isEqualTo("CommitMsgBar");
+  }
+
   @Before
   public void setUp() throws Exception {
     ObjectLoader objectLoaderBlob = mock(ObjectLoader.class);
@@ -117,6 +149,16 @@
     when(repoManager.openRepository(eq(Project.nameKey("ProjectFoo")))).thenReturn(repo);
   }
 
+  private RevisionInfo createRevisionInfo(String commitMessage) {
+    CommitInfo commitInfo = new CommitInfo();
+    commitInfo.message = commitMessage;
+
+    RevisionInfo revisionInfo = new RevisionInfo();
+    revisionInfo.commit = commitInfo;
+
+    return revisionInfo;
+  }
+
   private CommitMessageFetcher createCommitMessageFetcher() {
     return new CommitMessageFetcher(repoManager);
   }
diff --git a/src/test/java/com/googlesource/gerrit/plugins/zuul/util/DependsOnExtractorTest.java b/src/test/java/com/googlesource/gerrit/plugins/zuul/util/DependsOnExtractorTest.java
new file mode 100644
index 0000000..70344f7
--- /dev/null
+++ b/src/test/java/com/googlesource/gerrit/plugins/zuul/util/DependsOnExtractorTest.java
@@ -0,0 +1,112 @@
+// Copyright (C) 2020 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.googlesource.gerrit.plugins.zuul.util;
+
+import static com.google.common.truth.Truth.assertThat;
+
+import com.google.gerrit.entities.Change;
+import java.util.List;
+import org.junit.Test;
+
+public class DependsOnExtractorTest {
+  @Test
+  public void testExtractNoDependies() throws Exception {
+    DependsOnExtractor extractor = new DependsOnExtractor();
+
+    List<String> extracted = extractor.extract("foo");
+
+    assertThat(extracted).isEmpty();
+  }
+
+  @Test
+  public void testExtractNoDependencyTooShortChangeId() throws Exception {
+    DependsOnExtractor extractor = new DependsOnExtractor();
+    String commitMessage = "subject\n\nDepends-On: I123456789112345678921234567893123456789";
+
+    List<String> extracted = extractor.extract(commitMessage);
+
+    assertThat(extracted).isEmpty();
+  }
+
+  @Test
+  public void testExtractNoDependencyTooLongChangeId() throws Exception {
+    DependsOnExtractor extractor = new DependsOnExtractor();
+    String commitMessage = "subject\n\nDepends-On: I12345678911234567892123456789312345678941";
+
+    List<String> extracted = extractor.extract(commitMessage);
+
+    assertThat(extracted).isEmpty();
+  }
+
+  @Test
+  public void testExtractSingleDependencyLineEnd() throws Exception {
+    DependsOnExtractor extractor = new DependsOnExtractor();
+    String commitMessage = "subject\n\nDepends-On: " + getChangeKey(1);
+
+    List<String> extracted = extractor.extract(commitMessage);
+
+    assertThat(extracted).containsExactly(getChangeKey(1));
+  }
+
+  @Test
+  public void testExtractSingleDependencyContinuedLine() throws Exception {
+    DependsOnExtractor extractor = new DependsOnExtractor();
+    String commitMessage = "subject\n\nDepends-On: " + getChangeKey(1) + " ";
+
+    List<String> extracted = extractor.extract(commitMessage);
+
+    assertThat(extracted).containsExactly(getChangeKey(1));
+  }
+
+  @Test
+  public void testExtractMultipleDependencies() throws Exception {
+    DependsOnExtractor extractor = new DependsOnExtractor();
+    String commitMessage =
+        "subject\n\nDepends-On: "
+            + getChangeKey(1)
+            + "\nDepends-On: "
+            + getChangeKey(2)
+            + "\nDepends-On: "
+            + getChangeKey(3);
+
+    List<String> extracted = extractor.extract(commitMessage);
+
+    assertThat(extracted).containsExactly(getChangeKey(1), getChangeKey(2), getChangeKey(3));
+  }
+
+  @Test
+  public void testExtractLowerCase() throws Exception {
+    DependsOnExtractor extractor = new DependsOnExtractor();
+    String commitMessage = "subject\n\ndepends-on: " + getChangeKey(1);
+
+    List<String> extracted = extractor.extract(commitMessage);
+
+    assertThat(extracted).containsExactly(getChangeKey(1));
+  }
+
+  @Test
+  public void testExtractMixedCases() throws Exception {
+    DependsOnExtractor extractor = new DependsOnExtractor();
+    String commitMessage =
+        "subject\n\ndepends-On: " + getChangeKey(1) + "\nDePeNds-on: " + getChangeKey(2);
+
+    List<String> extracted = extractor.extract(commitMessage);
+
+    assertThat(extracted).containsExactly(getChangeKey(1), getChangeKey(2));
+  }
+
+  private String getChangeKey(int keyEnding) {
+    return Change.key("I0123456789abcdef0000000000000000000" + (10000 + keyEnding)).toString();
+  }
+}
diff --git a/src/test/java/com/googlesource/gerrit/plugins/zuul/util/DependsOnFetcherTest.java b/src/test/java/com/googlesource/gerrit/plugins/zuul/util/DependsOnFetcherTest.java
new file mode 100644
index 0000000..75247df
--- /dev/null
+++ b/src/test/java/com/googlesource/gerrit/plugins/zuul/util/DependsOnFetcherTest.java
@@ -0,0 +1,264 @@
+// Copyright (C) 2020 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.googlesource.gerrit.plugins.zuul.util;
+
+import static com.google.common.truth.Truth.assertThat;
+import static org.junit.Assert.fail;
+import static org.mockito.Mockito.doAnswer;
+import static org.mockito.Mockito.mock;
+import static org.mockito.Mockito.when;
+
+import com.google.gerrit.entities.BranchNameKey;
+import com.google.gerrit.entities.Change;
+import com.google.gerrit.entities.PatchSet;
+import com.google.gerrit.entities.Project;
+import com.google.gerrit.extensions.common.ChangeInfo;
+import com.google.gerrit.extensions.restapi.AuthException;
+import com.google.gerrit.extensions.restapi.BadRequestException;
+import com.google.gerrit.extensions.restapi.Response;
+import com.google.gerrit.extensions.restapi.TopLevelResource;
+import com.google.gerrit.server.change.RevisionResource;
+import com.google.gerrit.server.permissions.PermissionBackendException;
+import com.google.gerrit.server.restapi.change.ChangesCollection;
+import com.google.gerrit.server.restapi.change.QueryChanges;
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.concurrent.atomic.AtomicBoolean;
+import org.apache.commons.lang3.tuple.Pair;
+import org.eclipse.jgit.errors.RepositoryNotFoundException;
+import org.eclipse.jgit.lib.ObjectId;
+import org.junit.Test;
+import org.mockito.invocation.InvocationOnMock;
+import org.mockito.stubbing.Answer;
+
+public class DependsOnFetcherTest {
+  private ChangesCollection changes;
+  private CommitMessageFetcher commitMessageFetcher;
+  private DependsOnExtractor dependsOnExtractor;
+  private RevisionResource rsrc;
+  private Map<Integer, ChangeInfo> changeInfos = new HashMap<>();
+
+  @Test
+  public void testExtractNoDependencies() throws Exception {
+    configureMocks(new ArrayList<>(), new ArrayList<>());
+
+    DependsOnFetcher fetcher = createFetcher();
+    Pair<List<ChangeInfo>, List<String>> dependsOn = fetcher.fetchForRevision(rsrc);
+
+    assertThat(dependsOn.getLeft()).isEmpty();
+    assertThat(dependsOn.getRight()).isEmpty();
+  }
+
+  @Test
+  public void testExtractSingleFoundDependency() throws Exception {
+    List<String> extracted = new ArrayList<>();
+    extracted.add(getChangeKey(1));
+
+    List<ChangeInfo> searchResult = new ArrayList<>();
+    searchResult.add(getChangeInfo(1));
+    configureMocks(extracted, searchResult);
+
+    DependsOnFetcher fetcher = createFetcher();
+    Pair<List<ChangeInfo>, List<String>> dependsOn = fetcher.fetchForRevision(rsrc);
+
+    assertThat(dependsOn.getLeft()).containsExactly(getChangeInfo(1));
+    assertThat(dependsOn.getRight()).isEmpty();
+  }
+
+  @Test
+  public void testExtractMultipleFoundDependencies() throws Exception {
+    List<String> extracted = new ArrayList<>();
+    extracted.add(getChangeKey(1));
+    extracted.add(getChangeKey(2));
+    extracted.add(getChangeKey(3));
+    List<ChangeInfo> searchResult = new ArrayList<>();
+    searchResult.add(getChangeInfo(1));
+    searchResult.add(getChangeInfo(2));
+    searchResult.add(getChangeInfo(3));
+    configureMocks(extracted, searchResult);
+
+    DependsOnFetcher fetcher = createFetcher();
+    Pair<List<ChangeInfo>, List<String>> dependsOn = fetcher.fetchForRevision(rsrc);
+
+    assertThat(dependsOn.getLeft())
+        .containsExactly(getChangeInfo(1), getChangeInfo(2), getChangeInfo(3));
+    assertThat(dependsOn.getRight()).isEmpty();
+  }
+
+  @Test
+  public void testExtractSingleMissingDependency() throws Exception {
+    List<String> extracted = new ArrayList<>();
+    extracted.add(getChangeKey(1));
+
+    configureMocks(extracted, new ArrayList<>());
+
+    DependsOnFetcher fetcher = createFetcher();
+    Pair<List<ChangeInfo>, List<String>> dependsOn = fetcher.fetchForRevision(rsrc);
+
+    assertThat(dependsOn.getLeft()).isEmpty();
+    assertThat(dependsOn.getRight()).containsExactly(getChangeKey(1));
+  }
+
+  @Test
+  public void testExtractMultipleMissingDependencies() throws Exception {
+    List<String> extracted = new ArrayList<>();
+    extracted.add(getChangeKey(1));
+    extracted.add(getChangeKey(2));
+    extracted.add(getChangeKey(3));
+    configureMocks(extracted, new ArrayList<>());
+
+    DependsOnFetcher fetcher = createFetcher();
+    Pair<List<ChangeInfo>, List<String>> dependsOn = fetcher.fetchForRevision(rsrc);
+
+    assertThat(dependsOn.getLeft()).isEmpty();
+    assertThat(dependsOn.getRight())
+        .containsExactly(getChangeKey(1), getChangeKey(2), getChangeKey(3));
+  }
+
+  @Test
+  public void testExtractMultipleDependenciesMultipleResultsForChangeId() throws Exception {
+    List<String> extracted = new ArrayList<>();
+    extracted.add(getChangeKey(1));
+    extracted.add(getChangeKey(2));
+    extracted.add(getChangeKey(3));
+
+    List<ChangeInfo> searchResult = new ArrayList<>();
+    searchResult.add(getChangeInfo(1));
+    searchResult.add(getChangeInfo(2));
+    searchResult.add(getChangeInfo(3));
+
+    ChangeInfo changeInfo = getChangeInfo(102);
+    changeInfo.changeId = getChangeInfo(2).changeId;
+    searchResult.add(changeInfo);
+
+    configureMocks(extracted, searchResult);
+
+    DependsOnFetcher fetcher = createFetcher();
+    Pair<List<ChangeInfo>, List<String>> dependsOn = fetcher.fetchForRevision(rsrc);
+
+    assertThat(dependsOn.getLeft())
+        .containsExactly(getChangeInfo(1), getChangeInfo(2), getChangeInfo(3), getChangeInfo(102));
+    assertThat(dependsOn.getRight()).isEmpty();
+  }
+
+  @Test
+  public void testExtractMixed() throws Exception {
+    List<String> extracted = new ArrayList<>();
+    extracted.add(getChangeKey(1));
+    extracted.add(getChangeKey(2));
+    extracted.add(getChangeKey(3));
+    extracted.add(getChangeKey(4));
+
+    List<ChangeInfo> searchResult = new ArrayList<>();
+    searchResult.add(getChangeInfo(2));
+    searchResult.add(getChangeInfo(3));
+
+    ChangeInfo changeInfo = getChangeInfo(102);
+    changeInfo.changeId = getChangeInfo(2).changeId;
+    searchResult.add(changeInfo);
+
+    configureMocks(extracted, searchResult);
+
+    DependsOnFetcher fetcher = createFetcher();
+    Pair<List<ChangeInfo>, List<String>> dependsOn = fetcher.fetchForRevision(rsrc);
+
+    assertThat(dependsOn.getLeft())
+        .containsExactly(getChangeInfo(2), getChangeInfo(102), getChangeInfo(3));
+    assertThat(dependsOn.getRight()).containsExactly(getChangeKey(1), getChangeKey(4));
+  }
+
+  private void configureMocks(
+      List<String> extractedDependsOn, List<ChangeInfo> searchResultDependsOn)
+      throws RepositoryNotFoundException, IOException, BadRequestException, AuthException,
+          PermissionBackendException {
+    String commitId = "0123456789012345678901234567890123456789";
+
+    Project.NameKey projectNameKey = Project.nameKey("projectFoo");
+
+    PatchSet patchSet = mock(PatchSet.class);
+    when(patchSet.commitId()).thenReturn(ObjectId.fromString(commitId));
+
+    BranchNameKey branchNameKey = BranchNameKey.create(projectNameKey, "branchBar");
+
+    Change.Key changeKey = Change.key("I0123456789");
+    Change change = new Change(changeKey, null, null, branchNameKey, null);
+
+    rsrc = mock(RevisionResource.class);
+    when(rsrc.getChange()).thenReturn(change);
+    when(rsrc.getPatchSet()).thenReturn(patchSet);
+
+    commitMessageFetcher = mock(CommitMessageFetcher.class);
+    when(commitMessageFetcher.fetch(projectNameKey, commitId)).thenReturn("commitMsgFoo");
+
+    dependsOnExtractor = mock(DependsOnExtractor.class);
+    when(dependsOnExtractor.extract("commitMsgFoo")).thenReturn(extractedDependsOn);
+
+    QueryChanges queryChanges = mock(QueryChanges.class);
+    final AtomicBoolean addedQuery = new AtomicBoolean(false);
+
+    if (!extractedDependsOn.isEmpty()) {
+      doAnswer(
+              new Answer<Void>() {
+                @Override
+                public Void answer(InvocationOnMock invocation) throws Throwable {
+                  if (addedQuery.getAndSet(true)) {
+                    fail("flag has already been set");
+                  }
+                  return null;
+                }
+              })
+          .when(queryChanges)
+          .addQuery("change:" + String.join(" OR change:", extractedDependsOn));
+
+      when(queryChanges.apply(TopLevelResource.INSTANCE))
+          .thenAnswer(
+              new Answer<Response<List<ChangeInfo>>>() {
+
+                @Override
+                public Response<List<ChangeInfo>> answer(InvocationOnMock invocation)
+                    throws Throwable {
+                  if (!addedQuery.get()) {
+                    fail("executed query before all options were set");
+                  }
+                  return Response.ok(searchResultDependsOn);
+                }
+              });
+    }
+
+    changes = mock(ChangesCollection.class);
+    when(changes.list()).thenReturn(queryChanges);
+  }
+
+  private String getChangeKey(int keyEnding) {
+    return "I0123456789abcdef0000000000000000000" + (10000 + keyEnding);
+  }
+
+  private ChangeInfo getChangeInfo(int keyEnding) {
+    return changeInfos.computeIfAbsent(
+        keyEnding,
+        neededKeyEnding -> {
+          ChangeInfo changeInfo = new ChangeInfo();
+          changeInfo.changeId = getChangeKey(neededKeyEnding);
+          changeInfo._number = neededKeyEnding;
+          return changeInfo;
+        });
+  }
+
+  private DependsOnFetcher createFetcher() {
+    return new DependsOnFetcher(changes, commitMessageFetcher, dependsOnExtractor);
+  }
+}
diff --git a/src/test/java/com/googlesource/gerrit/plugins/zuul/util/NeededByFetcherTest.java b/src/test/java/com/googlesource/gerrit/plugins/zuul/util/NeededByFetcherTest.java
new file mode 100644
index 0000000..69c6977
--- /dev/null
+++ b/src/test/java/com/googlesource/gerrit/plugins/zuul/util/NeededByFetcherTest.java
@@ -0,0 +1,232 @@
+// Copyright (C) 2020 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.googlesource.gerrit.plugins.zuul.util;
+
+import static com.google.common.truth.Truth.assertThat;
+import static org.junit.Assert.fail;
+import static org.mockito.ArgumentMatchers.any;
+import static org.mockito.Mockito.doAnswer;
+import static org.mockito.Mockito.mock;
+import static org.mockito.Mockito.when;
+
+import com.google.gerrit.entities.Change;
+import com.google.gerrit.extensions.client.ListChangesOption;
+import com.google.gerrit.extensions.common.ChangeInfo;
+import com.google.gerrit.extensions.restapi.Response;
+import com.google.gerrit.extensions.restapi.TopLevelResource;
+import com.google.gerrit.server.restapi.change.ChangesCollection;
+import com.google.gerrit.server.restapi.change.QueryChanges;
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.concurrent.atomic.AtomicBoolean;
+import org.junit.Test;
+import org.mockito.invocation.InvocationOnMock;
+import org.mockito.stubbing.Answer;
+
+public class NeededByFetcherTest {
+  private ChangesCollection changes;
+  private CommitMessageFetcher commitMessageFetcher;
+  private DependsOnExtractor dependsOnExtractor;
+  private Change.Key changeKey = getChangeKey(1);
+  private Map<Integer, ChangeInfo> changeInfos = new HashMap<>();
+
+  @Test
+  public void testFetchForChangeKeyNoResults() throws Exception {
+    List<ChangeInfo> searchResult = new ArrayList<>();
+
+    configureMocks(searchResult);
+
+    NeededByFetcher fetcher = createFetcher();
+
+    List<ChangeInfo> neededBy = fetcher.fetchForChangeKey(changeKey);
+
+    assertThat(neededBy).isEmpty();
+  }
+
+  @Test
+  public void testFetchForChangeKeySingleResult() throws Exception {
+    List<ChangeInfo> searchResult = new ArrayList<>();
+    searchResult.add(getChangeInfo(2));
+
+    configureMocks(searchResult);
+
+    NeededByFetcher fetcher = createFetcher();
+
+    List<ChangeInfo> neededBy = fetcher.fetchForChangeKey(changeKey);
+
+    assertThat(neededBy).containsExactly(getChangeInfo(2));
+  }
+
+  @Test
+  public void testFetchForChangeKeySingleResultUnmatchedEmpty() throws Exception {
+    List<ChangeInfo> searchResult = new ArrayList<>();
+    searchResult.add(getChangeInfo(2));
+
+    configureMocks(searchResult);
+    when(dependsOnExtractor.extract("commitMessage2")).thenReturn(new ArrayList<>());
+
+    NeededByFetcher fetcher = createFetcher();
+
+    List<ChangeInfo> neededBy = fetcher.fetchForChangeKey(changeKey);
+
+    assertThat(neededBy).isEmpty();
+  }
+
+  @Test
+  public void testFetchForChangeKeySingleResultUnmatchedDifferent() throws Exception {
+    List<ChangeInfo> searchResult = new ArrayList<>();
+    searchResult.add(getChangeInfo(2));
+
+    configureMocks(searchResult);
+    List<String> extracted = new ArrayList<>();
+    extracted.add(getChangeKey(3).toString());
+    when(dependsOnExtractor.extract("commitMessage2")).thenReturn(extracted);
+
+    NeededByFetcher fetcher = createFetcher();
+
+    List<ChangeInfo> neededBy = fetcher.fetchForChangeKey(changeKey);
+
+    assertThat(neededBy).isEmpty();
+  }
+
+  @Test
+  public void testFetchForChangeKeyMultipleResults() throws Exception {
+    List<ChangeInfo> searchResult = new ArrayList<>();
+    searchResult.add(getChangeInfo(2));
+    searchResult.add(getChangeInfo(3));
+
+    configureMocks(searchResult);
+
+    NeededByFetcher fetcher = createFetcher();
+
+    List<ChangeInfo> neededBy = fetcher.fetchForChangeKey(changeKey);
+
+    assertThat(neededBy).containsExactly(getChangeInfo(2), getChangeInfo(3));
+  }
+
+  @Test
+  public void testFetchForChangeKeyMultipleResultsSomeUnmatched() throws Exception {
+    List<ChangeInfo> searchResult = new ArrayList<>();
+    searchResult.add(getChangeInfo(2));
+    searchResult.add(getChangeInfo(3));
+    searchResult.add(getChangeInfo(4));
+    searchResult.add(getChangeInfo(5));
+
+    configureMocks(searchResult);
+    when(dependsOnExtractor.extract("commitMessage3")).thenReturn(new ArrayList<>());
+    when(dependsOnExtractor.extract("commitMessage4")).thenReturn(new ArrayList<>());
+
+    NeededByFetcher fetcher = createFetcher();
+
+    List<ChangeInfo> neededBy = fetcher.fetchForChangeKey(changeKey);
+
+    assertThat(neededBy).containsExactly(getChangeInfo(2), getChangeInfo(5));
+  }
+
+  /**
+   * Sets up mocks for a given search result.
+   *
+   * <p>Each search result is configured to have a `Depends-On` to the changeKey per default. To
+   * refine, override the extraction for ("commitMessage" + number) to the desired list of
+   * Change-Ids.
+   *
+   * @param searchResult The search result to configure.
+   * @throws Exception thrown upon issues.
+   */
+  public void configureMocks(final List<ChangeInfo> searchResult) throws Exception {
+    QueryChanges queryChanges = mock(QueryChanges.class);
+    final AtomicBoolean addedQuery = new AtomicBoolean(false);
+    final AtomicBoolean addedOptionCurrentRevision = new AtomicBoolean(false);
+    final AtomicBoolean addedOptionCurrentCommit = new AtomicBoolean(false);
+
+    mockQueryChangesWithSwitch(queryChanges, addedOptionCurrentCommit)
+        .addOption(ListChangesOption.CURRENT_COMMIT);
+    mockQueryChangesWithSwitch(queryChanges, addedOptionCurrentRevision)
+        .addOption(ListChangesOption.CURRENT_REVISION);
+    mockQueryChangesWithSwitch(queryChanges, addedQuery)
+        .addQuery("message:" + changeKey + " -change:" + changeKey);
+    when(queryChanges.apply(TopLevelResource.INSTANCE))
+        .thenAnswer(
+            new Answer<Response<List<ChangeInfo>>>() {
+
+              @Override
+              public Response<List<ChangeInfo>> answer(InvocationOnMock invocation)
+                  throws Throwable {
+                boolean ready =
+                    addedOptionCurrentRevision.get()
+                        && addedOptionCurrentCommit.get()
+                        && addedQuery.get();
+                if (!ready) {
+                  fail("executed query before all options were set");
+                }
+                return Response.ok(searchResult);
+              }
+            });
+
+    changes = mock(ChangesCollection.class);
+    when(changes.list()).thenReturn(queryChanges);
+
+    commitMessageFetcher = mock(CommitMessageFetcher.class);
+    when(commitMessageFetcher.fetch(any(ChangeInfo.class)))
+        .thenAnswer(
+            new Answer<String>() {
+              @Override
+              public String answer(InvocationOnMock invocation) throws Throwable {
+                ChangeInfo changeInfo = invocation.getArgument(0);
+                return "commitMessage" + changeInfo._number;
+              }
+            });
+
+    dependsOnExtractor = mock(DependsOnExtractor.class);
+    List<String> extractedMatchList = new ArrayList<>();
+    extractedMatchList.add(changeKey.toString());
+    when(dependsOnExtractor.extract(any(String.class))).thenReturn(extractedMatchList);
+  }
+
+  private QueryChanges mockQueryChangesWithSwitch(
+      QueryChanges queryChanges, AtomicBoolean booleanSwitch) {
+    return doAnswer(
+            new Answer<Void>() {
+              @Override
+              public Void answer(InvocationOnMock invocation) throws Throwable {
+                if (booleanSwitch.getAndSet(true)) {
+                  fail("flag has already been set");
+                }
+                return null;
+              }
+            })
+        .when(queryChanges);
+  }
+
+  private Change.Key getChangeKey(int keyEnding) {
+    return Change.key("I0123456789abcdef0000000000000000000" + (10000 + keyEnding));
+  }
+
+  private ChangeInfo getChangeInfo(int keyEnding) {
+    return changeInfos.computeIfAbsent(
+        keyEnding,
+        neededKeyEnding -> {
+          ChangeInfo changeInfo = new ChangeInfo();
+          changeInfo.changeId = getChangeKey(neededKeyEnding).toString();
+          changeInfo._number = neededKeyEnding;
+          return changeInfo;
+        });
+  }
+
+  private NeededByFetcher createFetcher() {
+    return new NeededByFetcher(changes, commitMessageFetcher, dependsOnExtractor);
+  }
+}