<commit_before>require 'set'

module Plines
  # Represents a dependency graph of Plines steps. This graph contains
  # Jobs (i.e. Step classes paired with data). The graph
  # takes care of preventing duplicate step instances.
  class DependencyGraph
    attr_reader :steps # FYI, steps is not ordered according to dependencies

    # Raised when a circular dependency is detected.
    class CircularDependencyError < StandardError; end

    def initialize(pipeline, batch_data)
      step_classes = pipeline.step_classes
      @steps = Job.accumulate_instances do
        step_classes.each do |step_klass|
          step_klass.jobs_for(batch_data).each do |job|
            job.add_dependencies_for(batch_data)
          end
        end

        @terminal_jobs = pipeline.terminal_step.jobs_for(batch_data)
      end

      cleanup_and_validate_dependencies!
    end

    def ordered_steps
      visited = Set.new
      Enumerator.new do |yielder|
        steps.each do |step|
          yield_next_ordered_step_for(step, visited, yielder)
        end
      end
    end

  private

    def cleanup_and_validate_dependencies!
      @visited_steps = Set.new

      @steps.each do |step|
        next if @visited_steps.include?(step)
        depth_first_search_from(step)
      end
    end

    def depth_first_search_from(step, current_stack=Set.new)
      @visited_steps << step
      add_terminal_job_dependencies(step)

      if current_stack.include?(step)
        raise CircularDependencyError,
          "Your graph appears to have a circular dependency: " +
          current_stack.inspect
      end

      step.dependencies.each do |dep|
        depth_first_search_from(dep, current_stack | [step])
      end
    end

    def add_terminal_job_dependencies(job)
      if job.dependents.none? && !@terminal_jobs.include?(job)
        @terminal_jobs.each { |term_job| term_job.add_dependency(job) }
      end
    end

    def yield_next_ordered_step_for(step, visited, yielder)
      return if visited.include?(step)

      step.dependencies.each do |dependency|
        yield_next_ordered_step_for(dependency, visited, yielder)
      end

      visited << step
      yielder.yield step<commit_msg>Refactor: move terminal step setup out of the DFS.<commit_after>require 'set'

module Plines
  # Represents a dependency graph of Plines steps. This graph contains
  # Jobs (i.e. Step classes paired with data). The graph
  # takes care of preventing duplicate step instances.
  class DependencyGraph
    attr_reader :steps # FYI, steps is not ordered according to dependencies

    # Raised when a circular dependency is detected.
    class CircularDependencyError < StandardError; end

    def initialize(pipeline, batch_data)
      step_classes = pipeline.step_classes

      @steps = Job.accumulate_instances do
        step_classes.each do |step_klass|
          step_klass.jobs_for(batch_data).each do |job|
            job.add_dependencies_for(batch_data)
          end
        end

        @terminal_jobs = pipeline.terminal_step.jobs_for(batch_data)
      end

      setup_terminal_dependencies
      cleanup_and_validate_dependencies!
    end

    def ordered_steps
      visited = Set.new
      Enumerator.new do |yielder|
        steps.each do |step|
          yield_next_ordered_step_for(step, visited, yielder)
        end
      end
    end

  private

    def cleanup_and_validate_dependencies!
      @visited_steps = Set.new

      @steps.each do |step|
        next if @visited_steps.include?(step)
        depth_first_search_from(step)
      end
    end

    def depth_first_search_from(step, current_stack=Set.new)
      @visited_steps << step

      if current_stack.include?(step)
        raise CircularDependencyError,
          "Your graph appears to have a circular dependency: " +
          current_stack.inspect
      end

      step.dependencies.each do |dep|
        depth_first_search_from(dep, current_stack | [step])
      end
    end

    def setup_terminal_dependencies
      @steps.each do |job|
        if job.dependents.none? && !@terminal_jobs.include?(job)
          @terminal_jobs.each { |term_job| term_job.add_dependency(job) }
        end
      end
    end

    def yield_next_ordered_step_for(step, visited, yielder)
      return if visited.include?(step)

      step.dependencies.each do |dependency|
        yield_next_ordered_step_for(dependency, visited, yielder)
      end

      visited << step
      yielder.yield step
{'fraction_non_alphanumeric': 0.06624888093106536, 'fraction_numerical': 0.0, 'mean_word_length': 2.7241666666666666, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7366520', 'n_tokens_mistral': 1360, 'n_tokens_neox': 1280, 'n_words': 333}