diff --git a/tests/base.py b/tests/base.py
index 18d5f5a..08b3cab 100755
--- a/tests/base.py
+++ b/tests/base.py
@@ -378,6 +378,8 @@
 
 
 class FakeGerrit(object):
+    log = logging.getLogger("zuul.test.FakeGerrit")
+
     def __init__(self, *args, **kw):
         self.event_queue = Queue.Queue()
         self.fixture_dir = os.path.join(FIXTURE_DIR, 'gerrit')
@@ -418,12 +420,18 @@
         return {}
 
     def simpleQuery(self, query):
+        self.log.debug("simpleQuery: %s" % query)
         self.queries.append(query)
         if query.startswith('change:'):
             # Query a specific changeid
             changeid = query[len('change:'):]
             l = [change.query() for change in self.changes.values()
                  if change.data['id'] == changeid]
+        elif query.startswith('message:'):
+            # Query the content of a commit message
+            msg = query[len('message:'):].strip()
+            l = [change.query() for change in self.changes.values()
+                 if msg in change.data['commitMessage']]
         else:
             # Query all open changes
             l = [change.query() for change in self.changes.values()]
diff --git a/tests/test_scheduler.py b/tests/test_scheduler.py
index b44dba6..8e0a54b 100755
--- a/tests/test_scheduler.py
+++ b/tests/test_scheduler.py
@@ -3282,6 +3282,45 @@
         self.assertEqual(A.data['status'], 'MERGED')
         self.assertEqual(A.reported, 2)
 
+    def test_crd_gate_reverse(self):
+        "Test reverse cross-repo dependencies"
+        A = self.fake_gerrit.addFakeChange('org/project1', 'master', 'A')
+        B = self.fake_gerrit.addFakeChange('org/project2', 'master', 'B')
+        A.addApproval('CRVW', 2)
+        B.addApproval('CRVW', 2)
+
+        # A Depends-On: B
+
+        A.data['commitMessage'] = '%s\n\nDepends-On: %s\n' % (
+            A.subject, B.data['id'])
+
+        self.fake_gerrit.addEvent(A.addApproval('APRV', 1))
+        self.waitUntilSettled()
+
+        self.assertEqual(A.data['status'], 'NEW')
+        self.assertEqual(B.data['status'], 'NEW')
+
+        self.worker.hold_jobs_in_build = True
+        A.addApproval('APRV', 1)
+        self.fake_gerrit.addEvent(B.addApproval('APRV', 1))
+        self.waitUntilSettled()
+
+        self.worker.release('.*-merge')
+        self.waitUntilSettled()
+        self.worker.release('.*-merge')
+        self.waitUntilSettled()
+        self.worker.hold_jobs_in_build = False
+        self.worker.release()
+        self.waitUntilSettled()
+
+        self.assertEqual(A.data['status'], 'MERGED')
+        self.assertEqual(B.data['status'], 'MERGED')
+        self.assertEqual(A.reported, 2)
+        self.assertEqual(B.reported, 2)
+
+        self.assertEqual(self.getJobFromHistory('project1-merge').changes,
+                         '2,1 1,1')
+
     def test_crd_cycle(self):
         "Test cross-repo dependency cycles"
         A = self.fake_gerrit.addFakeChange('org/project1', 'master', 'A')
@@ -3501,3 +3540,43 @@
         # Each job should have tested exactly one change
         for job in self.history:
             self.assertEqual(len(job.changes.split()), 1)
+
+    def test_crd_check_transitive(self):
+        "Test transitive cross-repo dependencies"
+        # Specifically, if A -> B -> C, and C gets a new patchset and
+        # A gets a new patchset, ensure the test of A,2 includes B,1
+        # and C,2 (not C,1 which would indicate stale data in the
+        # cache for B).
+        A = self.fake_gerrit.addFakeChange('org/project1', 'master', 'A')
+        B = self.fake_gerrit.addFakeChange('org/project2', 'master', 'B')
+        C = self.fake_gerrit.addFakeChange('org/project3', 'master', 'C')
+
+        # A Depends-On: B
+        A.data['commitMessage'] = '%s\n\nDepends-On: %s\n' % (
+            A.subject, B.data['id'])
+
+        # B Depends-On: C
+        B.data['commitMessage'] = '%s\n\nDepends-On: %s\n' % (
+            B.subject, C.data['id'])
+
+        self.fake_gerrit.addEvent(A.getPatchsetCreatedEvent(1))
+        self.waitUntilSettled()
+        self.assertEqual(self.history[-1].changes, '3,1 2,1 1,1')
+
+        self.fake_gerrit.addEvent(B.getPatchsetCreatedEvent(1))
+        self.waitUntilSettled()
+        self.assertEqual(self.history[-1].changes, '3,1 2,1')
+
+        self.fake_gerrit.addEvent(C.getPatchsetCreatedEvent(1))
+        self.waitUntilSettled()
+        self.assertEqual(self.history[-1].changes, '3,1')
+
+        C.addPatchset()
+        self.fake_gerrit.addEvent(C.getPatchsetCreatedEvent(2))
+        self.waitUntilSettled()
+        self.assertEqual(self.history[-1].changes, '3,2')
+
+        A.addPatchset()
+        self.fake_gerrit.addEvent(A.getPatchsetCreatedEvent(2))
+        self.waitUntilSettled()
+        self.assertEqual(self.history[-1].changes, '3,2 2,1 1,2')
diff --git a/tests/test_zuultrigger.py b/tests/test_zuultrigger.py
index a26fa86..2f0e4f0 100644
--- a/tests/test_zuultrigger.py
+++ b/tests/test_zuultrigger.py
@@ -111,8 +111,8 @@
             "merged with the current state of the repository. Please rebase "
             "your change and upload a new patchset.")
 
-        self.assertEqual(self.fake_gerrit.queries[0],
-                         "project:org/project status:open")
+        self.assertTrue("project:org/project status:open" in
+                        self.fake_gerrit.queries)
 
         # Reconfigure and run the test again.  This is a regression
         # check to make sure that we don't end up with a stale trigger
diff --git a/zuul/trigger/gerrit.py b/zuul/trigger/gerrit.py
index c5fdf9a..7d970ad 100644
--- a/zuul/trigger/gerrit.py
+++ b/zuul/trigger/gerrit.py
@@ -362,6 +362,27 @@
             records.extend(self.gerrit.simpleQuery(query))
         return records
 
+    def _getNeededByFromCommit(self, change_id):
+        records = []
+        seen = set()
+        query = 'message:%s' % change_id
+        self.log.debug("Running query %s to find changes needed-by" %
+                       (query,))
+        results = self.gerrit.simpleQuery(query)
+        for result in results:
+            for match in self.depends_on_re.findall(
+                result['commitMessage']):
+                if match != change_id:
+                    continue
+                key = (result['number'], result['currentPatchSet']['number'])
+                if key in seen:
+                    continue
+                self.log.debug("Found change %s,%s needs %s from commit" %
+                               (key[0], key[1], change_id))
+                seen.add(key)
+                records.append(result)
+        return records
+
     def updateChange(self, change, history=None):
         self.log.info("Updating information for %s,%s" %
                       (change.number, change.patchset))
@@ -442,6 +463,19 @@
                 if (not dep.is_merged) and dep.is_current_patchset:
                     change.needed_by_changes.append(dep)
 
+        for record in self._getNeededByFromCommit(data['id']):
+            dep_num = record['number']
+            dep_ps = record['currentPatchSet']['number']
+            self.log.debug("Getting commit-needed change %s,%s" %
+                           (dep_num, dep_ps))
+            # Because a commit needed-by may be a cross-repo
+            # dependency, cause that change to refresh so that it will
+            # reference the latest patchset of its Depends-On (this
+            # change).
+            dep = self._getChange(dep_num, dep_ps, refresh=True)
+            if (not dep.is_merged) and dep.is_current_patchset:
+                change.needed_by_changes.append(dep)
+
         return change
 
     def getGitUrl(self, project):