Improve job dependencies using graph instead of tree

This replaces the job dependency tree with a graph so that we can
indicate that a job should wait until one or more jobs are complete
before starting.

Project pipeline job definitions are now a flat list, with each job
specifying its dependencies as the job attribute 'dependencies'.

Fixes bug #1166937.

Signed-off-by: Fredrik Medley <fredrik.medley@autoliv.com>
Signed-off-by: Fredrik Medley <fredrik.medley@gmail.com>
Signed-off-by: James E. Blair <jeblair@redhat.com>
Co-Authored-By: James E. Blair <jeblair@redhat.com>
Change-Id: I921940cafeea0738c39deb99357cfd7c91592359

49 files changed, 461 insertions, 245 deletions

diff --git a/tests/fixtures/config/ansible/git/common-config/zuul.yaml b/tests/fixtures/config/ansible/git/common-config/zuul.yaml
index aa7005443..50f353d5e 100644
--- a/tests/fixtures/config/ansible/git/common-config/zuul.yaml
+++ b/tests/fixtures/config/ansible/git/common-config/zuul.yaml
@@ -1,8 +1,7 @@
 - pipeline:
     name: check
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: patchset-created
@@ -17,8 +16,7 @@
     name: gate
     manager: dependent
     success-message: Build succeeded (gate).
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: comment-added
@@ -41,7 +39,7 @@
     pre-run: pre
     post-run: post
     vars:
-      flagpath: "{{zuul._test.test_root}}/{{zuul.uuid}}.flag"
+      flagpath: '{{zuul._test.test_root}}/{{zuul.uuid}}.flag'
     roles:
       - zuul: bare-role
 
diff --git a/tests/fixtures/config/ansible/git/org_project/.zuul.yaml b/tests/fixtures/config/ansible/git/org_project/.zuul.yaml
index b38f88e3a..24ba01909 100644
--- a/tests/fixtures/config/ansible/git/org_project/.zuul.yaml
+++ b/tests/fixtures/config/ansible/git/org_project/.zuul.yaml
@@ -4,7 +4,6 @@
 
 - project:
     name: org/project
-
     check:
       jobs:
         - python27
diff --git a/tests/fixtures/config/dependency-graph/git/common-config/playbooks/A.yaml b/tests/fixtures/config/dependency-graph/git/common-config/playbooks/A.yaml
new file mode 100644
index 000000000..f679dceae
--- /dev/null
+++ b/tests/fixtures/config/dependency-graph/git/common-config/playbooks/A.yaml
@@ -0,0 +1,2 @@
+- hosts: all
+  tasks: []
diff --git a/tests/fixtures/config/dependency-graph/git/common-config/playbooks/B.yaml b/tests/fixtures/config/dependency-graph/git/common-config/playbooks/B.yaml
new file mode 100644
index 000000000..f679dceae
--- /dev/null
+++ b/tests/fixtures/config/dependency-graph/git/common-config/playbooks/B.yaml
@@ -0,0 +1,2 @@
+- hosts: all
+  tasks: []
diff --git a/tests/fixtures/config/dependency-graph/git/common-config/playbooks/C.yaml b/tests/fixtures/config/dependency-graph/git/common-config/playbooks/C.yaml
new file mode 100644
index 000000000..f679dceae
--- /dev/null
+++ b/tests/fixtures/config/dependency-graph/git/common-config/playbooks/C.yaml
@@ -0,0 +1,2 @@
+- hosts: all
+  tasks: []
diff --git a/tests/fixtures/config/dependency-graph/git/common-config/playbooks/D.yaml b/tests/fixtures/config/dependency-graph/git/common-config/playbooks/D.yaml
new file mode 100644
index 000000000..f679dceae
--- /dev/null
+++ b/tests/fixtures/config/dependency-graph/git/common-config/playbooks/D.yaml
@@ -0,0 +1,2 @@
+- hosts: all
+  tasks: []
diff --git a/tests/fixtures/config/dependency-graph/git/common-config/playbooks/E.yaml b/tests/fixtures/config/dependency-graph/git/common-config/playbooks/E.yaml
new file mode 100644
index 000000000..f679dceae
--- /dev/null
+++ b/tests/fixtures/config/dependency-graph/git/common-config/playbooks/E.yaml
@@ -0,0 +1,2 @@
+- hosts: all
+  tasks: []
diff --git a/tests/fixtures/config/dependency-graph/git/common-config/playbooks/F.yaml b/tests/fixtures/config/dependency-graph/git/common-config/playbooks/F.yaml
new file mode 100644
index 000000000..f679dceae
--- /dev/null
+++ b/tests/fixtures/config/dependency-graph/git/common-config/playbooks/F.yaml
@@ -0,0 +1,2 @@
+- hosts: all
+  tasks: []
diff --git a/tests/fixtures/config/dependency-graph/git/common-config/playbooks/G.yaml b/tests/fixtures/config/dependency-graph/git/common-config/playbooks/G.yaml
new file mode 100644
index 000000000..f679dceae
--- /dev/null
+++ b/tests/fixtures/config/dependency-graph/git/common-config/playbooks/G.yaml
@@ -0,0 +1,2 @@
+- hosts: all
+  tasks: []
diff --git a/tests/fixtures/config/dependency-graph/git/common-config/playbooks/project-test1.yaml b/tests/fixtures/config/dependency-graph/git/common-config/playbooks/project-test1.yaml
new file mode 100644
index 000000000..f679dceae
--- /dev/null
+++ b/tests/fixtures/config/dependency-graph/git/common-config/playbooks/project-test1.yaml
@@ -0,0 +1,2 @@
+- hosts: all
+  tasks: []
diff --git a/tests/fixtures/config/dependency-graph/git/common-config/zuul.yaml b/tests/fixtures/config/dependency-graph/git/common-config/zuul.yaml
new file mode 100644
index 000000000..60f365165
--- /dev/null
+++ b/tests/fixtures/config/dependency-graph/git/common-config/zuul.yaml
@@ -0,0 +1,73 @@
+- pipeline:
+    name: gate
+    manager: dependent
+    success-message: Build succeeded (gate).
+    source: gerrit
+    trigger:
+      gerrit:
+        - event: comment-added
+          approval:
+            - approved: 1
+    success:
+      gerrit:
+        verified: 2
+        submit: true
+    failure:
+      gerrit:
+        verified: -2
+    start:
+      gerrit:
+        verified: 0
+    precedence: high
+
+- job:
+    name: A
+
+- job:
+    name: B
+
+- job:
+    name: C
+
+- job:
+    name: D
+
+- job:
+    name: E
+
+- job:
+    name: F
+
+- job:
+    name: G
+
+- project:
+    name: org/project
+    gate:
+      jobs:
+        # Job dependencies, starting with A
+        #     A
+        #    / \
+        #   B   C
+        #  / \ / \
+        # D   F   E
+        #     |
+        #     G
+        # This is intentionally not listed in the natural order to
+        # ensure that we can reference dependencies before they are
+        # defined.
+        - E:
+            dependencies: C
+        - A
+        - B:
+            dependencies: A
+        - C:
+            dependencies: A
+        - F:
+            dependencies:
+              - B
+              - C
+        - D:
+            dependencies: B
+        - G:
+            dependencies: F
diff --git a/tests/fixtures/config/dependency-graph/git/org_project/README b/tests/fixtures/config/dependency-graph/git/org_project/README
new file mode 100644
index 000000000..9daeafb98
--- /dev/null
+++ b/tests/fixtures/config/dependency-graph/git/org_project/README
@@ -0,0 +1 @@
+test
diff --git a/tests/fixtures/config/dependency-graph/main.yaml b/tests/fixtures/config/dependency-graph/main.yaml
new file mode 100644
index 000000000..d9868fad0
--- /dev/null
+++ b/tests/fixtures/config/dependency-graph/main.yaml
@@ -0,0 +1,8 @@
+- tenant:
+    name: tenant-one
+    source:
+      gerrit:
+        config-repos:
+          - common-config
+        project-repos:
+          - org/project
diff --git a/tests/fixtures/config/duplicate-pipeline/git/common-config/zuul.yaml b/tests/fixtures/config/duplicate-pipeline/git/common-config/zuul.yaml
index bc88b0617..50051086f 100755
--- a/tests/fixtures/config/duplicate-pipeline/git/common-config/zuul.yaml
+++ b/tests/fixtures/config/duplicate-pipeline/git/common-config/zuul.yaml
@@ -2,8 +2,7 @@
     name: dup1
     manager: independent
     success-message: Build succeeded (dup1).
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: change-restored
@@ -18,8 +17,7 @@
     name: dup2
     manager: independent
     success-message: Build succeeded (dup2).
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: change-restored
@@ -39,7 +37,6 @@
       queue: integrated
       jobs:
         - project-test1
-
     dup2:
       queue: integrated
       jobs:
diff --git a/tests/fixtures/config/in-repo/git/common-config/zuul.yaml b/tests/fixtures/config/in-repo/git/common-config/zuul.yaml
index d8b7200f7..55169ce7b 100644
--- a/tests/fixtures/config/in-repo/git/common-config/zuul.yaml
+++ b/tests/fixtures/config/in-repo/git/common-config/zuul.yaml
@@ -1,8 +1,7 @@
 - pipeline:
     name: check
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: patchset-created
@@ -17,8 +16,7 @@
     name: tenant-one-gate
     manager: dependent
     success-message: Build succeeded (tenant-one-gate).
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: comment-added
diff --git a/tests/fixtures/config/merges/git/common-config/zuul.yaml b/tests/fixtures/config/merges/git/common-config/zuul.yaml
index bb91f3a0c..ab4e24c47 100644
--- a/tests/fixtures/config/merges/git/common-config/zuul.yaml
+++ b/tests/fixtures/config/merges/git/common-config/zuul.yaml
@@ -1,8 +1,7 @@
 - pipeline:
     name: check
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: patchset-created
@@ -17,8 +16,7 @@
     name: gate
     manager: dependent
     success-message: Build succeeded (gate).
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: comment-added
@@ -37,16 +35,13 @@
     precedence: high
 
 - job:
-    name:
-      project-test1
+    name: project-test1
 
 - job:
-    name:
-      project-test2
+    name: project-test2
 
 - job:
-    name:
-      project-merge
+    name: project-merge
     hold-following-changes: true
 
 - project:
@@ -75,6 +70,6 @@
     merge-mode: cherry-pick
     gate:
       jobs:
-        - project-merge:
-            jobs:
-              - project-test1
+        - project-merge
+        - project-test1:
+            dependencies: project-merge
diff --git a/tests/fixtures/config/multi-tenant/git/common-config/zuul.yaml b/tests/fixtures/config/multi-tenant/git/common-config/zuul.yaml
index 08117d6d6..004f2df44 100644
--- a/tests/fixtures/config/multi-tenant/git/common-config/zuul.yaml
+++ b/tests/fixtures/config/multi-tenant/git/common-config/zuul.yaml
@@ -1,8 +1,7 @@
 - pipeline:
     name: check
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: patchset-created
@@ -14,8 +13,7 @@
         verified: -1
 
 - job:
-    name:
-      python27
+    name: python27
     nodes:
       - name: controller
         image: ubuntu-trusty
diff --git a/tests/fixtures/config/multi-tenant/git/tenant-one-config/zuul.yaml b/tests/fixtures/config/multi-tenant/git/tenant-one-config/zuul.yaml
index 4a653f6e4..5769cf543 100644
--- a/tests/fixtures/config/multi-tenant/git/tenant-one-config/zuul.yaml
+++ b/tests/fixtures/config/multi-tenant/git/tenant-one-config/zuul.yaml
@@ -2,8 +2,7 @@
     name: tenant-one-gate
     manager: dependent
     success-message: Build succeeded (tenant-one-gate).
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: comment-added
@@ -28,8 +27,7 @@
         image: controller-image
 
 - job:
-    name:
-      project1-test1
+    name: project1-test1
 
 - project:
     name: org/project1
diff --git a/tests/fixtures/config/multi-tenant/git/tenant-two-config/zuul.yaml b/tests/fixtures/config/multi-tenant/git/tenant-two-config/zuul.yaml
index 7c7972095..19782ce45 100644
--- a/tests/fixtures/config/multi-tenant/git/tenant-two-config/zuul.yaml
+++ b/tests/fixtures/config/multi-tenant/git/tenant-two-config/zuul.yaml
@@ -2,8 +2,7 @@
     name: tenant-two-gate
     manager: dependent
     success-message: Build succeeded (tenant-two-gate).
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: comment-added
@@ -28,8 +27,7 @@
         image: controller-image
 
 - job:
-    name:
-      project2-test1
+    name: project2-test1
 
 - project:
     name: org/project2
diff --git a/tests/fixtures/config/one-job-project/git/common-config/zuul.yaml b/tests/fixtures/config/one-job-project/git/common-config/zuul.yaml
index 148ba42c4..4579062ed 100644
--- a/tests/fixtures/config/one-job-project/git/common-config/zuul.yaml
+++ b/tests/fixtures/config/one-job-project/git/common-config/zuul.yaml
@@ -1,8 +1,7 @@
 - pipeline:
     name: check
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: patchset-created
@@ -17,8 +16,7 @@
     name: gate
     manager: dependent
     success-message: Build succeeded (gate).
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: comment-added
@@ -39,8 +37,7 @@
 - pipeline:
     name: post
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: ref-updated
diff --git a/tests/fixtures/config/openstack/git/project-config/zuul.yaml b/tests/fixtures/config/openstack/git/project-config/zuul.yaml
index 420d97946..760adb8e8 100644
--- a/tests/fixtures/config/openstack/git/project-config/zuul.yaml
+++ b/tests/fixtures/config/openstack/git/project-config/zuul.yaml
@@ -1,11 +1,8 @@
-# Pipeline definitions
-
 - pipeline:
     name: check
     manager: independent
     success-message: Build succeeded (check).
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: patchset-created
@@ -20,8 +17,7 @@
     name: gate
     manager: dependent
     success-message: Build succeeded (gate).
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: comment-added
@@ -39,8 +35,6 @@
         verified: 0
     precedence: high
 
-# Job definitions
-
 - job:
     name: base
     timeout: 30
@@ -78,8 +72,6 @@
       - openstack/keystone
       - openstack/nova
 
-# Project definitions
-
 - project:
     name: openstack/nova
     templates:
diff --git a/tests/fixtures/config/requirements/email/git/common-config/zuul.yaml b/tests/fixtures/config/requirements/email/git/common-config/zuul.yaml
index 09e0cc6ef..78d2a18a4 100644
--- a/tests/fixtures/config/requirements/email/git/common-config/zuul.yaml
+++ b/tests/fixtures/config/requirements/email/git/common-config/zuul.yaml
@@ -1,8 +1,7 @@
 - pipeline:
     name: pipeline
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: comment-added
@@ -19,8 +18,7 @@
 - pipeline:
     name: trigger
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: comment-added
diff --git a/tests/fixtures/config/requirements/newer-than/git/common-config/zuul.yaml b/tests/fixtures/config/requirements/newer-than/git/common-config/zuul.yaml
index cd76afd5b..1e84e1807 100644
--- a/tests/fixtures/config/requirements/newer-than/git/common-config/zuul.yaml
+++ b/tests/fixtures/config/requirements/newer-than/git/common-config/zuul.yaml
@@ -1,8 +1,7 @@
 - pipeline:
     name: pipeline
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: comment-added
@@ -20,8 +19,7 @@
 - pipeline:
     name: trigger
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: comment-added
diff --git a/tests/fixtures/config/requirements/older-than/git/common-config/zuul.yaml b/tests/fixtures/config/requirements/older-than/git/common-config/zuul.yaml
index 8dca5e6e6..efbd79a6b 100644
--- a/tests/fixtures/config/requirements/older-than/git/common-config/zuul.yaml
+++ b/tests/fixtures/config/requirements/older-than/git/common-config/zuul.yaml
@@ -1,8 +1,7 @@
 - pipeline:
     name: pipeline
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: comment-added
@@ -20,8 +19,7 @@
 - pipeline:
     name: trigger
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: comment-added
diff --git a/tests/fixtures/config/requirements/reject-username/git/common-config/zuul.yaml b/tests/fixtures/config/requirements/reject-username/git/common-config/zuul.yaml
index 92c7de2b5..7212944e1 100644
--- a/tests/fixtures/config/requirements/reject-username/git/common-config/zuul.yaml
+++ b/tests/fixtures/config/requirements/reject-username/git/common-config/zuul.yaml
@@ -1,11 +1,10 @@
 - pipeline:
     name: pipeline
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     reject:
       approval:
-        - username: 'jenkins'
+        - username: jenkins
     trigger:
       gerrit:
         - event: comment-added
@@ -19,13 +18,12 @@
 - pipeline:
     name: trigger
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: comment-added
           reject-approval:
-            - username: 'jenkins'
+            - username: jenkins
     success:
       gerrit:
         verified: 1
diff --git a/tests/fixtures/config/requirements/reject/git/common-config/zuul.yaml b/tests/fixtures/config/requirements/reject/git/common-config/zuul.yaml
index 12a253829..9f5b12527 100644
--- a/tests/fixtures/config/requirements/reject/git/common-config/zuul.yaml
+++ b/tests/fixtures/config/requirements/reject/git/common-config/zuul.yaml
@@ -1,15 +1,18 @@
 - pipeline:
     name: pipeline
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     require:
       approval:
         - username: jenkins
-          verified: [1, 2]
+          verified:
+            - 1
+            - 2
     reject:
       approval:
-        - verified: [-1, -2]
+        - verified:
+            - -1
+            - -2
     trigger:
       gerrit:
         - event: comment-added
@@ -23,16 +26,19 @@
 - pipeline:
     name: trigger
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: comment-added
           require-approval:
             - username: jenkins
-              verified: [1, 2]
+              verified:
+                - 1
+                - 2
           reject-approval:
-            - verified: [-1, -2]
+            - verified:
+                - -1
+                - -2
     success:
       gerrit:
         verified: 1
diff --git a/tests/fixtures/config/requirements/state/git/common-config/zuul.yaml b/tests/fixtures/config/requirements/state/git/common-config/zuul.yaml
index 9491bfff7..01ceb46a9 100644
--- a/tests/fixtures/config/requirements/state/git/common-config/zuul.yaml
+++ b/tests/fixtures/config/requirements/state/git/common-config/zuul.yaml
@@ -1,10 +1,9 @@
 - pipeline:
     name: current-check
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     require:
-      current-patchset: True
+      current-patchset: true
     trigger:
       gerrit:
         - event: patchset-created
@@ -19,10 +18,9 @@
 - pipeline:
     name: open-check
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     require:
-      open: True
+      open: true
     trigger:
       gerrit:
         - event: patchset-created
@@ -37,8 +35,7 @@
 - pipeline:
     name: status-check
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     require:
       status: NEW
     trigger:
diff --git a/tests/fixtures/config/requirements/username/git/common-config/zuul.yaml b/tests/fixtures/config/requirements/username/git/common-config/zuul.yaml
index ca2ff9792..9789e716e 100644
--- a/tests/fixtures/config/requirements/username/git/common-config/zuul.yaml
+++ b/tests/fixtures/config/requirements/username/git/common-config/zuul.yaml
@@ -1,8 +1,7 @@
 - pipeline:
     name: pipeline
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: comment-added
@@ -19,8 +18,7 @@
 - pipeline:
     name: trigger
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: comment-added
diff --git a/tests/fixtures/config/requirements/vote1/git/common-config/zuul.yaml b/tests/fixtures/config/requirements/vote1/git/common-config/zuul.yaml
index 00afe79cf..7989363be 100644
--- a/tests/fixtures/config/requirements/vote1/git/common-config/zuul.yaml
+++ b/tests/fixtures/config/requirements/vote1/git/common-config/zuul.yaml
@@ -1,4 +1,3 @@
-
 - pipeline:
     name: pipeline
     manager: independent
@@ -6,8 +5,7 @@
       approval:
         - username: jenkins
           verified: 1
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: comment-added
@@ -21,8 +19,7 @@
 - pipeline:
     name: trigger
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: comment-added
diff --git a/tests/fixtures/config/requirements/vote2/git/common-config/zuul.yaml b/tests/fixtures/config/requirements/vote2/git/common-config/zuul.yaml
index 73db7a73a..9348afbe5 100644
--- a/tests/fixtures/config/requirements/vote2/git/common-config/zuul.yaml
+++ b/tests/fixtures/config/requirements/vote2/git/common-config/zuul.yaml
@@ -4,9 +4,10 @@
     require:
       approval:
         - username: jenkins
-          verified: [1, 2]
-    source:
-      gerrit
+          verified:
+            - 1
+            - 2
+    source: gerrit
     trigger:
       gerrit:
         - event: comment-added
@@ -20,14 +21,15 @@
 - pipeline:
     name: trigger
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: comment-added
           require-approval:
             - username: jenkins
-              verified: [1, 2]
+              verified:
+                - 1
+                - 2
     success:
       gerrit:
         verified: 1
diff --git a/tests/fixtures/config/single-tenant/git/common-config/zuul.yaml b/tests/fixtures/config/single-tenant/git/common-config/zuul.yaml
index b91bf6f4a..47c173dfc 100644
--- a/tests/fixtures/config/single-tenant/git/common-config/zuul.yaml
+++ b/tests/fixtures/config/single-tenant/git/common-config/zuul.yaml
@@ -1,8 +1,7 @@
 - pipeline:
     name: check
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: patchset-created
@@ -17,8 +16,7 @@
     name: gate
     manager: dependent
     success-message: Build succeeded (gate).
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: comment-added
@@ -39,8 +37,7 @@
 - pipeline:
     name: post
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: ref-updated
@@ -49,8 +46,7 @@
 - pipeline:
     name: experimental
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: patchset-created
@@ -107,23 +103,26 @@
 - job:
     name: project-testfile
     files:
-      - '.*-requires'
+      - .*-requires
 
 - project:
     name: org/project
     check:
       jobs:
-        - project-merge:
-            jobs:
-              - project-test1
-              - project-test2
+        - project-merge
+        - project-test1:
+            dependencies: project-merge
+        - project-test2:
+            dependencies: project-merge
     gate:
       jobs:
-        - project-merge:
-            jobs:
-              - project-test1
-              - project-test2
-              - project-testfile
+        - project-merge
+        - project-test1:
+            dependencies: project-merge
+        - project-test2:
+            dependencies: project-merge
+        - project-testfile:
+            dependencies: project-merge
     post:
       jobs:
         - project-post
@@ -132,48 +131,58 @@
     name: org/project1
     check:
       jobs:
-        - project-merge:
-            jobs:
-              - project-test1
-              - project-test2
-              - project1-project2-integration
+        - project-merge
+        - project-test1:
+            dependencies: project-merge
+        - project-test2:
+            dependencies: project-merge
+        - project1-project2-integration:
+            dependencies: project-merge
     gate:
       queue: integrated
       jobs:
-        - project-merge:
-            jobs:
-              - project-test1
-              - project-test2
-              - project1-project2-integration
+        - project-merge
+        - project-test1:
+            dependencies: project-merge
+        - project-test2:
+            dependencies: project-merge
+        - project1-project2-integration:
+            dependencies: project-merge
 
 - project:
     name: org/project2
     gate:
       queue: integrated
       jobs:
-        - project-merge:
-            jobs:
-              - project-test1
-              - project-test2
-              - project1-project2-integration
+        - project-merge
+        - project-test1:
+            dependencies: project-merge
+        - project-test2:
+            dependencies: project-merge
+        - project1-project2-integration:
+            dependencies: project-merge
 
 - project:
     name: org/project3
     check:
       jobs:
-        - project-merge:
-            jobs:
-              - project-test1
-              - project-test2
-              - project1-project2-integration
+        - project-merge
+        - project-test1:
+            dependencies: project-merge
+        - project-test2:
+            dependencies: project-merge
+        - project1-project2-integration:
+            dependencies: project-merge
     gate:
       queue: integrated
       jobs:
-        - project-merge:
-            jobs:
-              - project-test1
-              - project-test2
-              - project1-project2-integration
+        - project-merge
+        - project-test1:
+            dependencies: project-merge
+        - project-test2:
+            dependencies: project-merge
+        - project1-project2-integration:
+            dependencies: project-merge
     post:
       jobs:
         - project-post
@@ -182,9 +191,9 @@
     name: org/experimental-project
     experimental:
       jobs:
-        - project-merge:
-            jobs:
-              - experimental-project-test
+        - project-merge
+        - experimental-project-test:
+            dependencies: project-merge
 
 - project:
     name: org/noop-project
@@ -199,16 +208,18 @@
     name: org/nonvoting-project
     check:
       jobs:
-        - nonvoting-project-merge:
-            jobs:
-              - nonvoting-project-test1
-              - nonvoting-project-test2
+        - nonvoting-project-merge
+        - nonvoting-project-test1:
+            dependencies: nonvoting-project-merge
+        - nonvoting-project-test2:
+            dependencies: nonvoting-project-merge
     gate:
       jobs:
-        - nonvoting-project-merge:
-            jobs:
-              - nonvoting-project-test1
-              - nonvoting-project-test2
+        - nonvoting-project-merge
+        - nonvoting-project-test1:
+            dependencies: nonvoting-project-merge
+        - nonvoting-project-test2:
+            dependencies: nonvoting-project-merge
 
 - project:
     name: org/no-jobs-project
diff --git a/tests/fixtures/config/single-tenant/git/layout-disabled-at/zuul.yaml b/tests/fixtures/config/single-tenant/git/layout-disabled-at/zuul.yaml
index 4cf6f1616..bdc19ac63 100644
--- a/tests/fixtures/config/single-tenant/git/layout-disabled-at/zuul.yaml
+++ b/tests/fixtures/config/single-tenant/git/layout-disabled-at/zuul.yaml
@@ -1,8 +1,7 @@
 - pipeline:
     name: check
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: patchset-created
diff --git a/tests/fixtures/config/single-tenant/git/layout-dont-ignore-ref-deletes/zuul.yaml b/tests/fixtures/config/single-tenant/git/layout-dont-ignore-ref-deletes/zuul.yaml
index 30e574ab5..334d9ac88 100644
--- a/tests/fixtures/config/single-tenant/git/layout-dont-ignore-ref-deletes/zuul.yaml
+++ b/tests/fixtures/config/single-tenant/git/layout-dont-ignore-ref-deletes/zuul.yaml
@@ -1,13 +1,12 @@
 - pipeline:
     name: post
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: ref-updated
           ref: ^(?!refs/).*$
-          ignore-deletes: False
+          ignore-deletes: false
 
 - job:
     name: project-post
@@ -20,4 +19,3 @@
     post:
       jobs:
         - project-post
-
diff --git a/tests/fixtures/config/single-tenant/git/layout-footer-message/zuul.yaml b/tests/fixtures/config/single-tenant/git/layout-footer-message/zuul.yaml
index 0c040705b..c69837866 100644
--- a/tests/fixtures/config/single-tenant/git/layout-footer-message/zuul.yaml
+++ b/tests/fixtures/config/single-tenant/git/layout-footer-message/zuul.yaml
@@ -2,8 +2,7 @@
     name: gate
     manager: dependent
     success-message: Build succeeded (gate).
-    source:
-      gerrit
+    source: gerrit
     failure-message: Build failed.  For information on how to proceed, see http://wiki.example.org/Test_Failures
     footer-message: For CI problems and help debugging, contact ci@example.org
     trigger:
@@ -35,4 +34,3 @@
     gate:
       jobs:
         - project-test1
-
diff --git a/tests/fixtures/config/single-tenant/git/layout-idle/zuul.yaml b/tests/fixtures/config/single-tenant/git/layout-idle/zuul.yaml
index f71f3e4b8..d1fa04bc5 100644
--- a/tests/fixtures/config/single-tenant/git/layout-idle/zuul.yaml
+++ b/tests/fixtures/config/single-tenant/git/layout-idle/zuul.yaml
@@ -1,8 +1,7 @@
 - pipeline:
     name: periodic
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       timer:
         - time: '* * * * * */1'
diff --git a/tests/fixtures/config/single-tenant/git/layout-inheritance/zuul.yaml b/tests/fixtures/config/single-tenant/git/layout-inheritance/zuul.yaml
index 3070af066..ab8c9a518 100644
--- a/tests/fixtures/config/single-tenant/git/layout-inheritance/zuul.yaml
+++ b/tests/fixtures/config/single-tenant/git/layout-inheritance/zuul.yaml
@@ -1,8 +1,7 @@
 - pipeline:
     name: check
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: patchset-created
@@ -13,7 +12,6 @@
       gerrit:
         verified: -1
 
-
 - job:
     name: project-test-irrelevant-starts-empty
 
diff --git a/tests/fixtures/config/single-tenant/git/layout-irrelevant-files/zuul.yaml b/tests/fixtures/config/single-tenant/git/layout-irrelevant-files/zuul.yaml
index f243bccb1..5d72fc090 100644
--- a/tests/fixtures/config/single-tenant/git/layout-irrelevant-files/zuul.yaml
+++ b/tests/fixtures/config/single-tenant/git/layout-irrelevant-files/zuul.yaml
@@ -1,8 +1,7 @@
 - pipeline:
     name: check
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: patchset-created
@@ -13,7 +12,6 @@
       gerrit:
         verified: -1
 
-
 - job:
     name: project-test-irrelevant-files
 
diff --git a/tests/fixtures/config/single-tenant/git/layout-mutex-reconfiguration/zuul.yaml b/tests/fixtures/config/single-tenant/git/layout-mutex-reconfiguration/zuul.yaml
index 12f174758..0e332e4ba 100644
--- a/tests/fixtures/config/single-tenant/git/layout-mutex-reconfiguration/zuul.yaml
+++ b/tests/fixtures/config/single-tenant/git/layout-mutex-reconfiguration/zuul.yaml
@@ -1,8 +1,7 @@
 - pipeline:
     name: check
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: patchset-created
diff --git a/tests/fixtures/config/single-tenant/git/layout-mutex/zuul.yaml b/tests/fixtures/config/single-tenant/git/layout-mutex/zuul.yaml
index e91903a59..bb92b7a94 100644
--- a/tests/fixtures/config/single-tenant/git/layout-mutex/zuul.yaml
+++ b/tests/fixtures/config/single-tenant/git/layout-mutex/zuul.yaml
@@ -1,8 +1,7 @@
 - pipeline:
     name: check
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: patchset-created
diff --git a/tests/fixtures/config/single-tenant/git/layout-no-timer/zuul.yaml b/tests/fixtures/config/single-tenant/git/layout-no-timer/zuul.yaml
index f754e376a..ab919a46a 100644
--- a/tests/fixtures/config/single-tenant/git/layout-no-timer/zuul.yaml
+++ b/tests/fixtures/config/single-tenant/git/layout-no-timer/zuul.yaml
@@ -1,8 +1,7 @@
 - pipeline:
     name: check
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: patchset-created
@@ -18,8 +17,7 @@
     manager: independent
     # Trigger is required, set it to one that is a noop
     # during tests that check the timer trigger.
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: ref-updated
diff --git a/tests/fixtures/config/single-tenant/git/layout-repo-deleted/zuul.yaml b/tests/fixtures/config/single-tenant/git/layout-repo-deleted/zuul.yaml
index 2bffc3ed0..5851d7551 100644
--- a/tests/fixtures/config/single-tenant/git/layout-repo-deleted/zuul.yaml
+++ b/tests/fixtures/config/single-tenant/git/layout-repo-deleted/zuul.yaml
@@ -1,8 +1,7 @@
 - pipeline:
     name: check
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: patchset-created
@@ -17,8 +16,7 @@
     name: gate
     manager: dependent
     success-message: Build succeeded (gate).
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: comment-added
@@ -60,13 +58,15 @@
     name: org/delete-project
     check:
       jobs:
-        - project-merge:
-            jobs:
-              - project-test1
-              - project-test2
+        - project-merge
+        - project-test1:
+            dependencies: project-merge
+        - project-test2:
+            dependencies: project-merge
     gate:
       jobs:
-        - project-merge:
-            jobs:
-              - project-test1
-              - project-test2
+        - project-merge
+        - project-test1:
+            dependencies: project-merge
+        - project-test2:
+            dependencies: project-merge
diff --git a/tests/fixtures/config/single-tenant/git/layout-smtp/zuul.yaml b/tests/fixtures/config/single-tenant/git/layout-smtp/zuul.yaml
index 9effb1fea..be90d48ae 100644
--- a/tests/fixtures/config/single-tenant/git/layout-smtp/zuul.yaml
+++ b/tests/fixtures/config/single-tenant/git/layout-smtp/zuul.yaml
@@ -1,8 +1,7 @@
 - pipeline:
     name: check
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: patchset-created
@@ -23,8 +22,7 @@
     name: gate
     manager: dependent
     success-message: Build succeeded (gate).
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: comment-added
@@ -69,13 +67,15 @@
     name: org/project
     check:
       jobs:
-        - project-merge:
-            jobs:
-              - project-test1
-              - project-test2
+        - project-merge
+        - project-test1:
+            dependencies: project-merge
+        - project-test2:
+            dependencies: project-merge
     gate:
       jobs:
-        - project-merge:
-            jobs:
-              - project-test1
-              - project-test2
+        - project-merge
+        - project-test1:
+            dependencies: project-merge
+        - project-test2:
+            dependencies: project-merge
diff --git a/tests/fixtures/config/single-tenant/git/layout-tags/zuul.yaml b/tests/fixtures/config/single-tenant/git/layout-tags/zuul.yaml
index c921c909f..07f06572b 100644
--- a/tests/fixtures/config/single-tenant/git/layout-tags/zuul.yaml
+++ b/tests/fixtures/config/single-tenant/git/layout-tags/zuul.yaml
@@ -1,8 +1,7 @@
 - pipeline:
     name: check
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: patchset-created
@@ -34,19 +33,23 @@
     check:
       jobs:
         - merge:
-            jobs:
-              - test1
-              - test2
-              - integration
             tags:
               - extratag
+        - test1:
+            dependencies: merge
+        - test2:
+            dependencies: merge
+        - integration:
+            dependencies: merge
 
 - project:
     name: org/project2
     check:
       jobs:
-        - merge:
-            jobs:
-              - test1
-              - test2
-              - integration
+        - merge
+        - test1:
+            dependencies: merge
+        - test2:
+            dependencies: merge
+        - integration:
+            dependencies: merge
diff --git a/tests/fixtures/config/single-tenant/git/layout-timer-smtp/zuul.yaml b/tests/fixtures/config/single-tenant/git/layout-timer-smtp/zuul.yaml
index 4a14107e7..2a2eca5fe 100644
--- a/tests/fixtures/config/single-tenant/git/layout-timer-smtp/zuul.yaml
+++ b/tests/fixtures/config/single-tenant/git/layout-timer-smtp/zuul.yaml
@@ -1,8 +1,7 @@
 - pipeline:
     name: periodic
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       timer:
         - time: '* * * * * */1'
@@ -10,7 +9,7 @@
       smtp:
         to: alternative_me@example.com
         from: zuul_from@example.com
-        subject: 'Periodic check for {change.project} succeeded'
+        subject: Periodic check for {change.project} succeeded
 
 - job:
     name: project-bitrot-stable-old
diff --git a/tests/fixtures/config/single-tenant/git/layout-timer/zuul.yaml b/tests/fixtures/config/single-tenant/git/layout-timer/zuul.yaml
index f69a91da4..80726445f 100644
--- a/tests/fixtures/config/single-tenant/git/layout-timer/zuul.yaml
+++ b/tests/fixtures/config/single-tenant/git/layout-timer/zuul.yaml
@@ -1,8 +1,7 @@
 - pipeline:
     name: check
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: patchset-created
@@ -16,8 +15,7 @@
 - pipeline:
     name: periodic
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       timer:
         - time: '* * * * * */1'
diff --git a/tests/fixtures/config/success-url/git/common-config/zuul.yaml b/tests/fixtures/config/success-url/git/common-config/zuul.yaml
index 7edb340d8..f2d5251fa 100644
--- a/tests/fixtures/config/success-url/git/common-config/zuul.yaml
+++ b/tests/fixtures/config/success-url/git/common-config/zuul.yaml
@@ -1,8 +1,7 @@
 - pipeline:
     name: check
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: patchset-created
@@ -18,7 +17,6 @@
       gerrit:
         verified: -1
 
-
 - job:
     name: docs-draft-test
     success-url: http://docs-draft.example.org/{build.parameters[LOG_PATH]}/publish-docs/
diff --git a/tests/fixtures/config/templated-project/git/common-config/zuul.yaml b/tests/fixtures/config/templated-project/git/common-config/zuul.yaml
index 22a2d6d90..8d2c8a047 100644
--- a/tests/fixtures/config/templated-project/git/common-config/zuul.yaml
+++ b/tests/fixtures/config/templated-project/git/common-config/zuul.yaml
@@ -1,8 +1,7 @@
 - pipeline:
     name: check
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: patchset-created
@@ -17,8 +16,7 @@
     name: gate
     manager: dependent
     success-message: Build succeeded (gate).
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: comment-added
@@ -39,8 +37,7 @@
 - pipeline:
     name: post
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: ref-updated
@@ -56,15 +53,15 @@
 - project-template:
     name: test-three-and-four
     check:
-       jobs:
-         - layered-project-test3
-         - layered-project-test4
+      jobs:
+        - layered-project-test3
+        - layered-project-test4
 
 - project-template:
     name: test-five
     check:
       jobs:
-         - layered-project-foo-test5
+        - layered-project-foo-test5
 
 - job:
     name: project-test1
diff --git a/tests/unit/test_model.py b/tests/unit/test_model.py
index 04d147381..ee7c6abe7 100644
--- a/tests/unit/test_model.py
+++ b/tests/unit/test_model.py
@@ -225,7 +225,7 @@ class TestJob(BaseTestCase):
         self.assertFalse(python27diablo.changeMatches(change))
         self.assertFalse(python27essex.changeMatches(change))
 
-        item.freezeJobTree()
+        item.freezeJobGraph()
         self.assertEqual(len(item.getJobs()), 1)
         job = item.getJobs()[0]
         self.assertEqual(job.name, 'python27')
@@ -253,7 +253,7 @@ class TestJob(BaseTestCase):
         self.assertTrue(python27diablo.changeMatches(change))
         self.assertFalse(python27essex.changeMatches(change))
 
-        item.freezeJobTree()
+        item.freezeJobGraph()
         self.assertEqual(len(item.getJobs()), 1)
         job = item.getJobs()[0]
         self.assertEqual(job.name, 'python27')
@@ -282,7 +282,7 @@ class TestJob(BaseTestCase):
         self.assertFalse(python27diablo.changeMatches(change))
         self.assertTrue(python27essex.changeMatches(change))
 
-        item.freezeJobTree()
+        item.freezeJobGraph()
         self.assertEqual(len(item.getJobs()), 1)
         job = item.getJobs()[0]
         self.assertEqual(job.name, 'python27')
@@ -439,7 +439,7 @@ class TestJob(BaseTestCase):
         self.assertTrue(python27.changeMatches(change))
         self.assertFalse(python27diablo.changeMatches(change))
 
-        item.freezeJobTree()
+        item.freezeJobGraph()
         self.assertEqual(len(item.getJobs()), 1)
         job = item.getJobs()[0]
         self.assertEqual(job.name, 'python27')
@@ -453,7 +453,7 @@ class TestJob(BaseTestCase):
         self.assertTrue(python27.changeMatches(change))
         self.assertTrue(python27diablo.changeMatches(change))
 
-        item.freezeJobTree()
+        item.freezeJobGraph()
         self.assertEqual(len(item.getJobs()), 1)
         job = item.getJobs()[0]
         self.assertEqual(job.name, 'python27')
@@ -506,7 +506,7 @@ class TestJob(BaseTestCase):
         self.assertTrue(base.changeMatches(change))
         self.assertFalse(python27.changeMatches(change))
 
-        item.freezeJobTree()
+        item.freezeJobGraph()
         self.assertEqual([], item.getJobs())
 
     def test_job_source_project(self):
@@ -609,3 +609,56 @@ class TestTimeDataBase(BaseTestCase):
         for x in range(10):
             self.db.update('job-name', 100, 'SUCCESS')
         self.assertEqual(self.db.getEstimatedTime('job-name'), 100)
+
+
+class TestGraph(BaseTestCase):
+    def test_job_graph_disallows_multiple_jobs_with_same_name(self):
+        graph = model.JobGraph()
+        job1 = model.Job('job')
+        job2 = model.Job('job')
+        graph.addJob(job1)
+        with testtools.ExpectedException(Exception,
+                                         "Job job already added"):
+            graph.addJob(job2)
+
+    def test_job_graph_disallows_circular_dependencies(self):
+        graph = model.JobGraph()
+        jobs = [model.Job('job%d' % i) for i in range(0, 10)]
+        prevjob = None
+        for j in jobs[:3]:
+            if prevjob:
+                j.dependencies = frozenset([prevjob.name])
+            graph.addJob(j)
+            prevjob = j
+        # 0 triggers 1 triggers 2 triggers 3...
+
+        # Cannot depend on itself
+        with testtools.ExpectedException(
+                Exception,
+                "Dependency cycle detected in job jobX"):
+            j = model.Job('jobX')
+            j.dependencies = frozenset([j.name])
+            graph.addJob(j)
+
+        # Disallow circular dependencies
+        with testtools.ExpectedException(
+                Exception,
+                "Dependency cycle detected in job job3"):
+            jobs[4].dependencies = frozenset([jobs[3].name])
+            graph.addJob(jobs[4])
+            jobs[3].dependencies = frozenset([jobs[4].name])
+            graph.addJob(jobs[3])
+
+        jobs[5].dependencies = frozenset([jobs[4].name])
+        graph.addJob(jobs[5])
+
+        with testtools.ExpectedException(
+                Exception,
+                "Dependency cycle detected in job job3"):
+            jobs[3].dependencies = frozenset([jobs[5].name])
+            graph.addJob(jobs[3])
+
+        jobs[3].dependencies = frozenset([jobs[2].name])
+        graph.addJob(jobs[3])
+        jobs[6].dependencies = frozenset([jobs[2].name])
+        graph.addJob(jobs[6])
diff --git a/tests/unit/test_scheduler.py b/tests/unit/test_scheduler.py
index e32e41bc0..a923ff15f 100755
--- a/tests/unit/test_scheduler.py
+++ b/tests/unit/test_scheduler.py
@@ -4478,6 +4478,117 @@ For CI problems and help debugging, contact ci@example.org"""
         self.assertIn('project-test2 : SKIPPED', A.messages[1])
 
 
+class TestDependencyGraph(ZuulTestCase):
+    tenant_config_file = 'config/dependency-graph/main.yaml'
+
+    def test_dependeny_graph_dispatch_jobs_once(self):
+        "Test a job in a dependency graph is queued only once"
+        # Job dependencies, starting with A
+        #     A
+        #    / \
+        #   B   C
+        #  / \ / \
+        # D   F   E
+        #     |
+        #     G
+
+        self.executor_server.hold_jobs_in_build = True
+        change = self.fake_gerrit.addFakeChange(
+            'org/project', 'master', 'change')
+        change.addApproval('code-review', 2)
+        self.fake_gerrit.addEvent(change.addApproval('approved', 1))
+
+        self.waitUntilSettled()
+        self.assertEqual([b.name for b in self.builds], ['A'])
+
+        self.executor_server.release('A')
+        self.waitUntilSettled()
+        self.assertEqual(sorted(b.name for b in self.builds), ['B', 'C'])
+
+        self.executor_server.release('B')
+        self.waitUntilSettled()
+        self.assertEqual(sorted(b.name for b in self.builds), ['C', 'D'])
+
+        self.executor_server.release('D')
+        self.waitUntilSettled()
+        self.assertEqual([b.name for b in self.builds], ['C'])
+
+        self.executor_server.release('C')
+        self.waitUntilSettled()
+        self.assertEqual(sorted(b.name for b in self.builds), ['E', 'F'])
+
+        self.executor_server.release('F')
+        self.waitUntilSettled()
+        self.assertEqual(sorted(b.name for b in self.builds), ['E', 'G'])
+
+        self.executor_server.release('G')
+        self.waitUntilSettled()
+        self.assertEqual([b.name for b in self.builds], ['E'])
+
+        self.executor_server.release('E')
+        self.waitUntilSettled()
+        self.assertEqual(len(self.builds), 0)
+
+        self.executor_server.hold_jobs_in_build = False
+        self.executor_server.release()
+        self.waitUntilSettled()
+
+        self.assertEqual(len(self.builds), 0)
+        self.assertEqual(len(self.history), 7)
+
+        self.assertEqual(change.data['status'], 'MERGED')
+        self.assertEqual(change.reported, 2)
+
+    def test_jobs_launched_only_if_all_dependencies_are_successful(self):
+        "Test that a job waits till all dependencies are successful"
+        # Job dependencies, starting with A
+        #     A
+        #    / \
+        #   B   C*
+        #  / \ / \
+        # D   F   E
+        #     |
+        #     G
+
+        self.executor_server.hold_jobs_in_build = True
+        change = self.fake_gerrit.addFakeChange(
+            'org/project', 'master', 'change')
+        change.addApproval('code-review', 2)
+
+        self.executor_server.failJob('C', change)
+
+        self.fake_gerrit.addEvent(change.addApproval('approved', 1))
+
+        self.waitUntilSettled()
+        self.assertEqual([b.name for b in self.builds], ['A'])
+
+        self.executor_server.release('A')
+        self.waitUntilSettled()
+        self.assertEqual(sorted(b.name for b in self.builds), ['B', 'C'])
+
+        self.executor_server.release('B')
+        self.waitUntilSettled()
+        self.assertEqual(sorted(b.name for b in self.builds), ['C', 'D'])
+
+        self.executor_server.release('D')
+        self.waitUntilSettled()
+        self.assertEqual([b.name for b in self.builds], ['C'])
+
+        self.executor_server.release('C')
+        self.waitUntilSettled()
+        self.assertEqual(len(self.builds), 0)
+
+        self.executor_server.hold_jobs_in_build = False
+        self.executor_server.release()
+        self.waitUntilSettled()
+
+        self.assertEqual(len(self.builds), 0)
+        self.assertEqual(len(self.history), 4)
+
+        self.assertEqual(change.data['status'], 'NEW')
+        self.assertEqual(change.reported, 2)
+
+
 class TestDuplicatePipeline(ZuulTestCase):
     tenant_config_file = 'config/duplicate-pipeline/main.yaml'