class DakeResolver

Public Class Methods

new(analyzer) click to toggle source
# File lib/dake/resolver.rb, line 14
def initialize(analyzer)
  @analyzer = analyzer
end

Public Instance Methods

find_steps(target_scheme, tag) click to toggle source
# File lib/dake/resolver.rb, line 149
def find_steps(target_scheme, tag)
  target_name = target_scheme.path
  target_src = target_scheme.src
  if tag
    steps = @analyzer.tag_target_dict[target_name]
    if not steps
      mdata = nil
      _, template_steps = @analyzer.tag_template_dict.detect do |regex, _|
        mdata = regex.match target_name
      end
      if template_steps
        @analyzer.tag_target_dict[target_name] ||= []
        steps = []
        template_steps.each do |template_step|
          if @analyzer.step_template_dict[template_step] and
             @analyzer.step_template_dict[template_step][mdata]
            step = @analyzer.step_template_dict[template_step][mdata]
          else
            step = template_step.dup
            step.targets = template_step.targets.dup
            step.prerequisites = template_step.prerequisites.dup
            step.context = template_step.context.dup
            step.context.merge! mdata.named_captures
            @analyzer.step_template_dict[template_step] ||= {}
            @analyzer.step_template_dict[template_step][mdata] = step
          end
          step.targets.map! do |file|
            if file.scheme.is_a? DakeScheme::Regex and file.scheme.path.match target_name
              new_file = file.dup
              new_file.scheme = DakeScheme::Tag.new('@', target_name, step)
              new_file
            else
              file
            end
          end
          @analyzer.tag_target_dict[target_name] << step
          steps << step
        end
      else
        raise "No step found for building tag `#{target_name}'."
      end
    end
  else
    step = @analyzer.file_target_dict[target_name]
    if step
      steps = [step]
    else
      mdata = nil
      _, template_step = @analyzer.file_template_dict.detect do |regex, _|
        mdata = regex.match target_src
      end
      if template_step
        if @analyzer.step_template_dict[template_step] and
           @analyzer.step_template_dict[template_step][mdata]
          step = @analyzer.step_template_dict[template_step][mdata]
        else
          step = template_step.dup
          step.targets = template_step.targets.dup
          step.prerequisites = template_step.prerequisites.dup
          step.context = template_step.context.dup
          step.context.merge! mdata.named_captures
          @analyzer.step_template_dict[template_step] ||= {}
          @analyzer.step_template_dict[template_step][mdata] = step
        end
        step.targets.map! do |file|
          if file.scheme.is_a? DakeScheme::Regex and file.scheme.path.match target_src
            line, column = @analyzer.text_line_and_column(file.name)
            new_file = file.dup
            new_file.scheme = @analyzer.analyze_scheme(target_name, step, line, column)
            new_file
          else
            file
          end
        end
        @analyzer.file_target_dict[target_name] = step
        steps = [step]
      else
        steps = []
      end
    end
  end
  steps
end
need_execute?(targets, step) click to toggle source

check if a step needs to be executed to produce the given targets

# File lib/dake/resolver.rb, line 110
def need_execute?(targets, step)
  max_mtime = nil
  targets.each do |target|
    # a tag target can be thought as newer than any prerequisite,
    # the step should always be executed to produce the tag target
    return true if target.tag

    # if a target doesn't exist, the step should always be executed to produce it
    return true unless target.scheme.exist?
    target_mtime = target.scheme.mtime

    # find the newest modification time in all targets
    if max_mtime
      max_mtime = target_mtime if target_mtime > max_mtime
    else
      max_mtime = target_mtime
    end
  end

  files = step.prerequisites.reject { |dep| dep.tag }
  files.each do |file|
    next if file.flag == '?'
    # if any required file is newer than the newest target,
    # the step should be executed to update the target
    if file.scheme.exist?
      file_mtime = file.scheme.mtime
      return true if file_mtime > max_mtime
    else
      # if a required file doesn't exist,
      # it means a step should be executed to produce the file,
      # and the newly produced file will be newer than all the targets,
      # therefore this step should also be executed
      return true
    end
  end
  # if not in any case above, the step doesn't need to be executed
  false
end
resolve(target_pairs) click to toggle source

resolve the dependency graph and generate step list for sequential execution

# File lib/dake/resolver.rb, line 234
def resolve(target_pairs)
  step_list = []
  visited = Set.new
  path_visited = Set.new
  target_steps = Set.new
  succ_step_dict = {}
  dep_step_dict = {}
  dep_step_list = {}
  succ_target_dict = {}
  step_prereq_dict = {}

  target_pairs.each do |target_name, target_opts|
    if target_opts.tag
      dummy_step = Step.new([], [], [], {}, nil, nil, @analyzer.variable_dict, nil, nil)
      scheme = DakeScheme::Tag.new('@', target_name, dummy_step)
    else
      scheme = @analyzer.analyze_scheme(target_name, nil, nil, nil)
    end
    dep_steps = find_steps(scheme, target_opts.tag)
    dep_steps.each do |dep_step|
      target = dep_step.targets.find { |target| target.scheme.path == scheme.path }
      succ_target_dict[dep_step] ||= Set.new
      succ_target_dict[dep_step] << target
      target_steps << dep_step
      succ_step_dict[dep_step] ||= Set.new
    end
  end

  target_steps.each do |target_step|
    stack = []
    stack.push target_step unless visited.include? target_step
    until stack.empty?
      step = stack.last
      visited << step
      path_visited << step
      unless dep_step_dict[step]
        dep_step_dict[step] = Set.new
        step.prerequisites.map! { |file| @analyzer.analyze_file(file, :prerequisites, step) }.flatten!
        step.prerequisites.each do |dep|
          dep_steps = find_steps(dep.scheme, dep.tag)
          if dep_steps.empty?
            step_prereq_dict[step] ||= Set.new
            step_prereq_dict[step] << dep
          end
          dep_steps.each do |dep_step|
            dep_step_dict[step] << dep_step
            succ_step_dict[dep_step] ||= Set.new
            succ_step_dict[dep_step] << step
            succ_target_dict[dep_step] ||= Set.new
            succ_target_dict[dep_step] << dep
            if path_visited.include? dep_step
              ofile = dep_step.targets.find { |prev_target| prev_target.scheme.path == dep.scheme.path }
              ln1, col1 = ofile.tag ? ofile.name.line_and_column : @analyzer.text_line_and_column(ofile.name)
              ln2, col2 = dep.tag ? dep.name.line_and_column : @analyzer.text_line_and_column(dep.name)
              STDERR.puts 'Cyclical dependency detected.'
              raise "Output `#{dep.scheme.path}' defined in #{dep_step.src_file} at #{ln1}:#{col1} " +
                        "is defined as Input in #{step.src_file} at #{ln2}:#{col2}."
            end
          end
        end
        dep_step_list[step] = dep_step_dict[step].to_a
      end
      while next_step = dep_step_list[step].pop
        break unless visited.include? next_step
      end
      if next_step
        stack.push next_step
      else
        stack.pop
        path_visited.delete step
        step_list << step
      end
    end
  end
  root_steps = target_steps.select { |step| succ_step_dict[step].empty? }.to_set
  DepGraph.new(succ_step_dict, dep_step_dict, step_list, root_steps, step_prereq_dict, succ_target_dict)
end
target_rebuild_set(target_pairs, dep_graph) click to toggle source
# File lib/dake/resolver.rb, line 18
def target_rebuild_set(target_pairs, dep_graph)
  rebuild_set = Set.new
  target_pairs.each do |target_name, target_opts|
    if target_opts.tag
      dummy_step = Step.new([], [], [], {}, nil, nil, @analyzer.variable_dict, nil, nil)
      scheme = DakeScheme::Tag.new('@', target_name, dummy_step)
    else
      scheme = @analyzer.analyze_scheme(target_name, nil, nil, nil)
    end
    target_steps = find_steps(scheme, target_opts.tag).to_set
    if target_steps.empty? and not scheme.exist?
      raise "No step found for building file `#{target_name}'."
    end

    visited = Set.new
    path_visited = Set.new
    down_tree_steps = Set.new
    up_tree_steps = Set.new
    need_rebuild = Set.new
    up_tree = 0
    dep_step_list = {}

    init_steps = (target_opts.tree_mode == :down_tree ? dep_graph.root_step : target_steps)
    init_steps.each do |init_step|
      stack = [init_step]

      until stack.empty?
        step = stack.last
        visited << step
        path_visited << step
        up_tree_steps << step if up_tree > 0 or target_steps.include? step

        dep_step_list[step] ||= dep_graph.dep_step[step].to_a
        while next_step = dep_step_list[step].pop
          break unless visited.include? next_step
        end
        if next_step
          stack.push next_step
          up_tree += 1 if target_steps.include? step
        else
          stack.pop

          if dep_graph.step_prereq[step]
            dep_graph.step_prereq[step].each do |prereq|
              if prereq.flag != '?' and not prereq.scheme.exist?
                raise "No step found for building file `#{prereq.scheme.path}'."
              end
            end
          end

          if target_steps.include? step or dep_graph.dep_step[step].any? { |s| down_tree_steps.include? s }
            down_tree_steps << step
          end

          if target_opts.build_mode == :check and (up_tree_steps.include? step or down_tree_steps.include? step)
            if dep_graph.dep_step[step].any? { |dep_step| need_rebuild.include? dep_step }
              need_rebuild << step
            else
              need_rebuild << step if need_execute?(dep_graph.step_target[step], step)
            end
          end

          up_tree -= 1 if target_steps.include? step
          path_visited.delete step
        end
      end
    end
    case target_opts.build_mode
    when :forced
      case target_opts.tree_mode
      when :up_tree then rebuild_set |= up_tree_steps
      when :down_tree then rebuild_set |= down_tree_steps
      when :target_only then rebuild_set |= target_steps
      end
    when :exclusion
      case target_opts.tree_mode
      when :up_tree then rebuild_set -= up_tree_steps
      when :down_tree then rebuild_set -= down_tree_steps
      when :target_only then rebuild_set -= target_steps
      end
    when :check
      case target_opts.tree_mode
      when :up_tree then rebuild_set |= (up_tree_steps & need_rebuild)
      when :down_tree then rebuild_set |= (down_tree_steps & need_rebuild)
      when :target_only then rebuild_set |= (target_steps & need_rebuild)
      end
    end
  end
  rebuild_set
end