Add commit needed-by

In order to find reverse dependencies specified by cross-repo
"Depends-On" headers, search for the occurance of a given change-id
in commit messages, and then filter the result set for "Depends-On"
headers.

Add those cross-repo reverse dependencies to the already supplied
Gerrit git reverse dependencies.  This should cause behaviors
such as automatic enqueuing of reverse dependencies on merges to
apply to CRD as well as git-dependencies.

When collecting reverse CRD, update cached Zuul change records.
This corrects a bug where if change A depends on B in a different
repo, and change B is updated with a new patchset, Zuul's cached
record for change A will still point to the old patchset of change
B.  This change corrects that by causing B to trigger a refresh of
A when the reverse CRD is noted.

Change-Id: I1bcf1f0fa0ea1c20b01ea478a83f179b612a0ae9
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):