Add support for DAG

This implements the support for `needs:` keyword
as part of GitLab CI. That makes some of the jobs
to be run out of order.

3 files changed, 67 insertions, 35 deletions

diff --git a/lib/gitlab/ci/config/entry/job.rb b/lib/gitlab/ci/config/entry/job.rb
index 5ab795359b8..2fd76bc3690 100644
--- a/lib/gitlab/ci/config/entry/job.rb
+++ b/lib/gitlab/ci/config/entry/job.rb
@@ -13,7 +13,7 @@ module Gitlab
 
           ALLOWED_KEYS = %i[tags script only except type image services
                             allow_failure type stage when start_in artifacts cache
-                            dependencies before_script after_script variables
+                            dependencies needs before_script after_script variables
                             environment coverage retry parallel extends].freeze
 
           validations do
@@ -34,11 +34,22 @@ module Gitlab
                              message: 'should be on_success, on_failure, ' \
                                       'always, manual or delayed' }
               validates :dependencies, array_of_strings: true
+              validates :needs, array_of_strings: true
               validates :extends, array_of_strings_or_string: true
             end
 
             validates :start_in, duration: { limit: '1 day' }, if: :delayed?
             validates :start_in, absence: true, unless: :delayed?
+
+            validate do
+              next unless dependencies.present?
+              next unless needs.present?
+
+              missing_needs = dependencies - needs
+              if missing_needs.any?
+                errors.add(:dependencies, "the #{missing_needs.join(", ")} should be part of needs")
+              end
+            end
           end
 
           entry :before_script, Entry::Script,
@@ -95,10 +106,10 @@ module Gitlab
           helpers :before_script, :script, :stage, :type, :after_script,
                   :cache, :image, :services, :only, :except, :variables,
                   :artifacts, :environment, :coverage, :retry,
-                  :parallel
+                  :parallel, :needs
 
           attributes :script, :tags, :allow_failure, :when, :dependencies,
-                     :retry, :parallel, :extends, :start_in
+                     :needs, :retry, :parallel, :extends, :start_in
 
           def self.matching?(name, config)
             !name.to_s.start_with?('.') &&
@@ -178,7 +189,8 @@ module Gitlab
               parallel: parallel_defined? ? parallel_value.to_i : nil,
               artifacts: artifacts_value,
               after_script: after_script_value,
-              ignore: ignored? }
+              ignore: ignored?,
+              needs: needs_defined? ? needs_value : nil }
           end
         end
       end
diff --git a/lib/gitlab/ci/config/normalizer.rb b/lib/gitlab/ci/config/normalizer.rb
index 99356226ef9..09f9bf5f69f 100644
--- a/lib/gitlab/ci/config/normalizer.rb
+++ b/lib/gitlab/ci/config/normalizer.rb
@@ -4,61 +4,63 @@ module Gitlab
   module Ci
     class Config
       class Normalizer
+        include Gitlab::Utils::StrongMemoize
+
         def initialize(jobs_config)
           @jobs_config = jobs_config
         end
 
         def normalize_jobs
-          extract_parallelized_jobs!
-          return @jobs_config if @parallelized_jobs.empty?
+          return @jobs_config if parallelized_jobs.empty?
+
+          expand_parallelize_jobs do |job_name, config|
+            if config[:dependencies]
+              config[:dependencies] = expand_names(config[:dependencies])
+            end
 
-          parallelized_config = parallelize_jobs
-          parallelize_dependencies(parallelized_config)
+            if config[:needs]
+              config[:needs] = expand_names(config[:needs])
+            end
+
+            config
+          end
         end
 
         private
 
-        def extract_parallelized_jobs!
-          @parallelized_jobs = {}
+        def expand_names(job_names)
+          return unless job_names
 
-          @jobs_config.each do |job_name, config|
-            if config[:parallel]
-              @parallelized_jobs[job_name] = self.class.parallelize_job_names(job_name, config[:parallel])
-            end
+          job_names.flat_map do |job_name|
+            parallelized_jobs[job_name.to_sym] || job_name
           end
-
-          @parallelized_jobs
         end
 
-        def parallelize_jobs
-          @jobs_config.each_with_object({}) do |(job_name, config), hash|
-            if @parallelized_jobs.key?(job_name)
-              @parallelized_jobs[job_name].each { |name, index| hash[name.to_sym] = config.merge(name: name, instance: index) }
-            else
-              hash[job_name] = config
-            end
+        def parallelized_jobs
+          strong_memoize(:parallelized_jobs) do
+            @jobs_config.each_with_object({}) do |(job_name, config), hash|
+              next unless config[:parallel]
 
-            hash
+              hash[job_name] = self.class.parallelize_job_names(job_name, config[:parallel])
+            end
           end
         end
 
-        def parallelize_dependencies(parallelized_config)
-          parallelized_job_names = @parallelized_jobs.keys.map(&:to_s)
-          parallelized_config.each_with_object({}) do |(job_name, config), hash|
-            if config[:dependencies] && (intersection = config[:dependencies] & parallelized_job_names).any?
-              parallelized_deps = intersection.flat_map { |dep| @parallelized_jobs[dep.to_sym].map(&:first) }
-              deps = config[:dependencies] - intersection + parallelized_deps
-              hash[job_name] = config.merge(dependencies: deps)
+        def expand_parallelize_jobs
+          @jobs_config.each_with_object({}) do |(job_name, config), hash|
+            if parallelized_jobs.key?(job_name)
+              parallelized_jobs[job_name].each_with_index do |name, index|
+                hash[name.to_sym] =
+                  yield(name, config.merge(name: name, instance: index + 1))
+              end
             else
-              hash[job_name] = config
+              hash[job_name] = yield(job_name, config)
             end
-
-            hash
           end
         end
 
         def self.parallelize_job_names(name, total)
-          Array.new(total) { |index| ["#{name} #{index + 1}/#{total}", index + 1] }
+          Array.new(total) { |index| "#{name} #{index + 1}/#{total}" }
         end
       end
     end
diff --git a/lib/gitlab/ci/yaml_processor.rb b/lib/gitlab/ci/yaml_processor.rb
index a0bbf3c23a2..998130e5bd0 100644
--- a/lib/gitlab/ci/yaml_processor.rb
+++ b/lib/gitlab/ci/yaml_processor.rb
@@ -40,6 +40,7 @@ module Gitlab
           environment: job[:environment_name],
           coverage_regex: job[:coverage],
           yaml_variables: yaml_variables(name),
+          needs_attributes: job[:needs]&.map { |need| { name: need } },
           options: {
             image: job[:image],
             services: job[:services],
@@ -108,6 +109,7 @@ module Gitlab
 
           validate_job_stage!(name, job)
           validate_job_dependencies!(name, job)
+          validate_job_needs!(name, job)
           validate_job_environment!(name, job)
         end
       end
@@ -152,6 +154,22 @@ module Gitlab
         end
       end
 
+      def validate_job_needs!(name, job)
+        return unless job[:needs]
+
+        stage_index = @stages.index(job[:stage])
+
+        job[:needs].each do |need|
+          raise ValidationError, "#{name} job: undefined need: #{need}" unless @jobs[need.to_sym]
+
+          needs_stage_index = @stages.index(@jobs[need.to_sym][:stage])
+
+          unless needs_stage_index.present? && needs_stage_index < stage_index
+            raise ValidationError, "#{name} job: need #{need} is not defined in prior stages"
+          end
+        end
+      end
+
       def validate_job_environment!(name, job)
         return unless job[:environment]
         return unless job[:environment].is_a?(Hash)