# Update dependencies without a configured build or a C compiler:
#   ruby tool/mkdepend.rb --scope=all --sources --inplace
# Expand source mappings into full dependencies:
#   ruby tool/mkdepend.rb --scope=all --inplace
# Check committed source mappings without modifying files:
#   ruby tool/mkdepend.rb --scope=all --sources --check
# The command can be run from either the source or a build directory.
# Known Make variables can be supplied as +VAR=value+.  The
# <tt>--thread-model=MODEL</tt> option is equivalent to
# +THREAD_MODEL=MODEL+.
#
# Dependency files can declare inputs that do not exist in the source tree:
#
#   # mkdepend: scan NAME => SOURCE
#     Scan SOURCE in place of a generated source or included header NAME.
#     `*` and `**` patterns are expanded from matching SOURCE files and
#     substituted into NAME.  Both sides must have the same pattern count.
#
#   # mkdepend: depends NAME => DEPENDENCY...
#     Associate NAME with dependencies.  They replace NAME when it is
#     included and are added when NAME is a source being scanned.  Make
#     A DEPENDENCY beginning with a Make variable reference is emitted
#     without path conversion.
#     `$(THREAD_MODEL)` in SOURCE is resolved as `pthread` by default.
#     When a thread model is supplied, it is resolved in SOURCE and
#     DEPENDENCY.
#
#   # mkdepend: define SOURCE => MACRO...
#   # mkdepend: undef SOURCE => MACRO...
#     Treat preprocessor MACROs as defined or undefined while scanning SOURCE.
#
# Declarations in the top-level depend file apply to all dependency files.
# A declaration in a more specific dependency file overrides one with the
# same name and kind.  An invalid `# mkdepend:` declaration is an error.

require 'set'
require 'tempfile'
require 'fileutils'
require 'optparse'
require 'pathname'

# Namespace for +mkmf+ extension-building helpers.
module MakeMakefile
end

# Generates dependency rules for Ruby and C extension sources.
#
# An extension project can update the autogenerated section of its
# +depend+ file while running +extconf.rb+:
#
#   ruby extconf.rb --update-depend
#
# The +depend+ file must contain these markers:
#
#   # AUTOGENERATED DEPENDENCIES START
#   # AUTOGENERATED DEPENDENCIES END
#
# MakeMakefile::Depend scans each source and the headers it includes without
# invoking a compiler.  When updating an extension project, files outside the
# project tree, such as system and installed Ruby headers, are omitted.  Use
# <tt>--depend-root=DIR</tt> when the project root cannot be detected from a
# +.git+ directory.
class MakeMakefile::Depend
  DEFAULT_ROOT = File.expand_path("../..", __dir__) # :nodoc:

  Declarations = Struct.new(
    :scan, :dependencies, :defines, :undefines,
  ) # :nodoc:

  private_constant :DEFAULT_ROOT, :Declarations

  class Scanner # :nodoc:
    attr_reader :accessed, :unresolved

    def initialize(root:, include_dirs:, quote_dirs: [], macros: {},
                   targets: [], aliases: {}, dependencies: {}, defined: [],
                   undefined: [], cache: {})
      @root = File.expand_path(root)
      @include_dirs = include_dirs.map {|dir| File.expand_path(dir, @root)}
      @quote_dirs = quote_dirs.map {|dir| File.expand_path(dir, @root)}
      @macros = macros
      @targets = targets.to_set
      @aliases = aliases
      @dependencies = dependencies
      @defined = defined.to_set
      @undefined = undefined.to_set
      @accessed = Set.new
      @unresolved = Set.new
      @cache = cache
    end

    def scan(source)
      dependencies = Set.new
      visit(File.expand_path(source, @root), dependencies, Set.new)
      dependencies.to_a.sort
    end

    private

    def visit(path, dependencies, visited, record: true)
      path = File.expand_path(path)
      return if visited.include?(path)
      directives = source_directives(path)
      return unless directives
      visited.add(path)
      dependencies.add(relative(path)) if record

      conditions = []
      directives.each do |directive|
        case directive
        when /\Aifdef\s+(\w+)/
          conditions << symbol_condition($1)
        when /\Aifndef\s+(\w+)/
          condition = symbol_condition($1)
          conditions << (condition == :all ? :all : !condition)
        when /\Aif\s+(.+)/
          conditions << expression_condition($1)
        when /\Aelif\s+(.+)/
          conditions[-1] = if conditions[-1] == true
            false
          elsif conditions[-1] == false
            expression_condition($1)
          else
            :all
          end
        when /\Aelse\b/
          conditions[-1] = !conditions[-1] if [true, false].include?(conditions[-1])
        when /\Aendif\b/
          conditions.pop
        else
          next if conditions.include?(false)
          case directive
          when /\A(?:line\s+)?\d+\s+"([^"<>]+)"/
            dependencies.add($1.delete_prefix("./"))
          when /\Ainclude(?:_next)?\s+(.+)/
            scan_include($1, path, dependencies, visited)
          end
        end
      end
    end

    def source_directives(path)
      path = File.expand_path(path)
      @accessed.add(path)
      return @cache[path] if @cache.key?(path)

      @cache[path] = if File.file?(path)
        File.open(path, "rb") do |file|
          directives = []
          logical_line = "".b
          file.each_line do |line|
            logical_line << line
            next if logical_line.sub!(/\\\r?\n\z/, "")

            if directive = logical_line[/\A\s*#\s*\K.*/]
              directives << directive
            end
            logical_line.clear
          end
          unless logical_line.empty?
            if directive = logical_line[/\A\s*#\s*\K.*/]
              directives << directive
            end
          end
          directives
        end
      end
    end

    def symbol_condition(symbol)
      return true if @defined.include?(symbol)
      return false if @undefined.include?(symbol)
      :all
    end

    def expression_condition(expression)
      case expression.sub(%r{/\*.*}, '').strip
      when /\A0+[LU]*(?:\z|\s*&&)/i
        return false
      when /\A1+[LU]*(?:\z|\s*\|\|)/i
        return true
      when /\A(!?)\s*defined\s*(?:\(\s*)?(\w+)/
        condition = symbol_condition($2)
        return condition if condition == :all
        return $1.empty? ? condition : !condition
      when /\A(!?)(\w+)\z/
        condition = symbol_condition($2)
        return condition if condition == :all
        return $1.empty? ? condition : !condition
      end
      :all
    end

    def scan_include(argument, current, dependencies, visited)
      case argument.sub(%r{//.*\z}, '').strip
      when /\A([<"])([^<>"]+)[>"]/
        quoted = $1 == '"'
        name = $2
      when /\A([A-Za-z_]\w*)/
        name = $1
        unless @aliases.key?(name) || @dependencies.key?(name) ||
            @targets.include?(name)
          name = @macros[name]
        end
        quoted = true
      end
      return unless name

      if alias_path = @aliases[name]
        if virtual = @dependencies[name]
          dependencies.merge(virtual)
        else
          dependencies.add(name)
        end
        visit(File.expand_path(alias_path, @root), dependencies, visited, record: false)
        return
      end

      if virtual = @dependencies[name]
        dependencies.merge(virtual)
      elsif name.end_with?(".inc", ".rbinc", ".rbbin")
        dependencies.add(name)
      elsif path = resolve(name, current, quoted)
        visit(path, dependencies, visited)
      elsif @targets.include?(name)
        dependencies.add(name)
      else
        @unresolved.add(name)
      end
    end

    def resolve(name, current, quoted)
      dirs = []
      dirs << File.dirname(current) if quoted
      dirs.concat(@quote_dirs) if quoted
      dirs.concat(@include_dirs)
      dirs.each do |dir|
        path = File.expand_path(name, dir)
        return path if source_directives(path)
      end
      nil
    end

    def relative(path)
      prefix = @root + File::SEPARATOR
      path.start_with?(prefix) ? path.delete_prefix(prefix) : path
    end
  end

  private_constant :Scanner

  # Source tree root used to resolve dependency paths.
  attr_reader :root

  class << self
    # Runs the command-line interface with +argv+.
    #
    # Returns whether the requested update or check succeeded.
    def main(argv = ARGV, err: $stderr)
      options, inputs = parse_options(argv)
    rescue OptionParser::ParseError => error
      err.puts "#{File.basename($0)}: #{error.message}"
      err.puts "Try '#{File.basename($0)} --help' for more information."
      false
    else
      execute(inputs, **options)
    end

    # Finds the nearest ancestor of +path+ containing +.git+.
    #
    # Returns +path+ itself when no repository root can be found.
    def find_root(path)
      path = File.expand_path(path)
      root = path
      loop do
        return path if File.exist?(File.join(path, ".git"))
        parent = File.dirname(path)
        break if parent == path
        path = parent
      end
      root
    end

    private

    # Parses command-line arguments into runner options and input paths.
    def parse_options(argv)
      options = {}
      make_variables = {}
      output = nil
      select_mode = proc do |mode|
        options[:mode] = mode
      end
      parser = OptionParser.new do |opts|
        opts.banner =
          "Usage: #{File.basename($0)} [options] [VAR=value ...] [files]"
        opts.separator ""
        opts.separator "Input selection:"
        opts.on("--root=DIR", "source tree root") {|value| options[:root] = value}
        opts.on(
          "--thread-model=MODEL",
          String,
          "thread model (same as THREAD_MODEL=MODEL)",
        ) do |value|
          make_variables["THREAD_MODEL"] = value
        end
        opts.on(
          "--scope=SCOPE", [:all, :core, :extensions],
          "dependency files to process (all, core, extensions)",
        ) do |value|
          options[:scope] = value
        end

        opts.separator ""
        opts.separator "Update mode (last one wins; default: stdout):"
        opts.on("--output=DIR", "write dependencies under DIR") do |value|
          select_mode[:output]
          output = value
        end
        opts.on("--inplace", "update dependency files in place") do
          select_mode[:inplace]
        end
        opts.on("--check", "check dependency files without updating") do
          select_mode[:check]
        end

        opts.separator ""
        opts.separator "Output options:"
        opts.on("--nmake", "emit NMake dependency rules") do
          options[:nmake] = true
        end
        opts.on("--sources", "emit source mappings") do
          options[:sources] = true
        end
        opts.on("-v", "--verbose", "show scanned sources") do
          options[:verbose] = true
        end
      end
      inputs = []
      rest = parser.order(argv) do |arg|
        if /\A([A-Za-z_]\w*)=(.*)\z/m =~ arg
          make_variables[$1] = $2
        else
          inputs << arg
        end
      end
      inputs.concat(rest)
      options[:make_variables] = make_variables unless make_variables.empty?
      options[:output] = output if options[:mode] == :output
      [options, inputs]
    end

    # Creates an updater and runs it with the parsed command-line options.
    def execute(inputs, root: DEFAULT_ROOT, **options)
      new(root: root).run(inputs, **options)
    end
  end

  # Creates a dependency updater for +root+.
  def initialize(root: DEFAULT_ROOT)
    @root = File.expand_path(root)
    @make_variables = {}
    @dependency_declarations = {}
    @dependency_targets = {}
    @dependency_contents = {}
    @source_cache = {}
    @stat_cache = {}
  end

  private

  # Selects known Make variable values used during dependency generation.
  def select_make_variables(make_variables)
    make_variables = make_variables.to_h do |name, value|
      [name.to_s, Array(value).map(&:to_s)]
    end
    return if @make_variables == make_variables

    @make_variables = make_variables
    @dependency_declarations.clear
  end

  # Expands known Make variables embedded in +value+.
  def expand_make_variables(value, defaults: {})
    value.gsub(/\$\((\w+)\)/) do |variable|
      name = $1
      values = if @make_variables.key?(name)
        @make_variables[name]
      elsif defaults.key?(name)
        Array(defaults[name])
      else
        next variable
      end
      unless values.one?
        raise ArgumentError, "#{name} is not a scalar Make variable"
      end
      values.first.to_s
    end
  end

  # Expands known Make variables that stand for dependency lists.
  def expand_dependency_variables(dependencies)
    dependencies.flat_map do |dependency|
      if /\A\$\((\w+)\)\z/ =~ dependency &&
          (values = @make_variables[$1])
        values.flat_map(&:split)
      else
        expand_make_variables(dependency)
      end
    end
  end

  # Expands matching wildcards in a +scan+ declaration.
  #
  # Returns a generated-name to source-path mapping.
  def expand_scan_declaration(name, source)
    source_parts = source.split(/(\*\*|\*)/)
    captures = source_parts.count {|part| part == "*" || part == "**"}
    return unless captures == name.scan(/\*\*|\*/).size
    return {name => source} if captures.zero?

    pattern = source_parts.map do |part|
      case part
      when "**" then "(.*)"
      when "*" then "([^/]*)"
      else Regexp.escape(part)
      end
    end.join
    pattern = /\A#{pattern}\z/
    Dir.glob(File.join(@root, source)).sort.each_with_object({}) do |path, map|
      path = relative_source(path)
      match = pattern.match(path) or next
      values = match.captures
      generated = name.gsub(/\*\*|\*/) {values.shift}
      map[generated] = path
    end
  end

  # Parses +mkdepend+ declarations from +path+ or the supplied +content+.
  def parse_dependency_declarations(path, content = nil)
    declarations = Declarations.new({}, {}, {}, {})
    content ||= File.read(path) if File.file?(path)
    return declarations unless content

    lineno = 0
    content.each_line do |line|
      lineno += 1
      case line[/\A#\s*mkdepend:\s*\K.*/]
      when nil
        next
      when /\Ascan\s+(\S+)\s*=>\s*(\S+)\s*\z/
        scan = expand_scan_declaration($1, $2)
        unless scan && (!scan.empty? || !$2.include?("*"))
          raise "#{path}:#{lineno}: invalid mkdepend declaration: #{line.strip}"
        end
        declarations.scan.update(scan)
      when /\Adepends\s+(\S+)\s*=>\s*(.+?)\s*\z/
        name, dependencies = $1, $2.split
        if declarations.dependencies.key?(name)
          raise "#{path}:#{lineno}: duplicate mkdepend declaration: #{name}"
        end
        declarations.dependencies[name] = dependencies
      when /\Adefine\s+(\S+)\s*=>\s*(.+?)\s*\z/
        declarations.defines[$1] = $2.split
      when /\Aundef\s+(\S+)\s*=>\s*(.+?)\s*\z/
        declarations.undefines[$1] = $2.split
      else
        raise "#{path}:#{lineno}: invalid mkdepend declaration: #{line.strip}"
      end
    end
    declarations.scan.transform_values! do |source|
      expand_make_variables(source, defaults: {"THREAD_MODEL" => "pthread"})
    end
    declarations.dependencies.transform_values! do |dependencies|
      expand_dependency_variables(dependencies)
    end
    declarations
  end

  # Reads and caches a dependency file, or caches supplied +content+.
  def dependency_file_content(path, content = nil)
    path = File.expand_path(path, @root)
    if content
      @dependency_contents[path] = content
    elsif @dependency_contents.key?(path)
      @dependency_contents[path]
    elsif File.file?(path)
      @dependency_contents[path] = File.read(path)
    end
  end

  # Returns merged global and file-local declarations for an input or source.
  def dependency_declarations(input = nil, source: nil, content: nil)
    input ||= dependency_input(source)
    input = relative_source(input || "depend")
    @dependency_declarations[input] ||= begin
      if input == "depend"
        path = File.join(@root, input)
        parse_dependency_declarations(path, dependency_file_content(path, content))
      else
        global = dependency_declarations(File.join(@root, "depend"))
        path = File.absolute_path?(input) ? input : File.join(@root, input)
        local = parse_dependency_declarations(
          path, dependency_file_content(path, content),
        )
        Declarations.new(
          global.scan.merge(local.scan),
          global.dependencies.merge(local.dependencies),
          global.defines.merge(local.defines),
          global.undefines.merge(local.undefines),
        )
      end
    end
  end

  # Returns the dependency file that governs +source+.
  def dependency_input(source)
    return "depend" unless source
    source = relative_source(source)
    if source.start_with?("ext/")
      dir = File.dirname(source)
      until dir == "." || dir == "ext"
        return File.join(dir, "depend") if File.file?(File.join(@root, dir, "depend"))
        dir = File.dirname(dir)
      end
    elsif source.start_with?("enc/")
      return "enc/depend"
    end
    "depend"
  end

  # Finds the declaration for +name+, accounting for an input-relative name.
  def declaration(map, name, input = nil)
    candidates = [name]
    if input
      dir = File.dirname(relative_source(input))
      candidates << name.delete_prefix(dir + "/") unless dir == "."
    end
    key = candidates.uniq.find {|candidate| map.key?(candidate)}
    [key, map[key]] if key
  end

  # Returns generated targets declared outside the marked section of +input+.
  def dependency_targets(input, content = nil)
    input = relative_source(input)
    @dependency_targets[input] ||= begin
      targets = []
      path = File.absolute_path?(input) ? input : File.join(@root, input)
      content = dependency_file_content(path, content)
      if content
        content.each_line do |line|
          if line.start_with?(MARK_START)..line.start_with?(MARK_END)
            next
          elsif target = line[/\A[^\s#][^:=]*?(?=\s*:(?!=))/]
            targets.concat(target.split)
          end
        end
      end
      targets.uniq
    end
  end

  # Finds the declared target matching +name+ in +input+.
  def dependency_target(name, input)
    input = relative_source(input)
    targets = dependency_targets(input)
    candidates = [name]
    dir = File.dirname(input)
    candidates << name.delete_prefix(dir + "/") unless dir == "."
    candidates.uniq.find {|candidate| targets.include?(candidate)}
  end

  # Makes +path+ relative to #root when it refers to a source-tree file.
  def relative_source(path)
    expanded = File.expand_path(path)
    expanded = File.expand_path(path, @root) unless File.exist?(expanded)
    prefix = @root + File::SEPARATOR
    expanded.start_with?(prefix) ? expanded.delete_prefix(prefix) : path
  end

  # Makes +path+ relative to #root without consulting the current
  # directory.  Unlike #relative_source, a relative name that does not
  # refer to a source-tree file is kept as-is: generated dependencies
  # such as builtin_binary.rbbin live in the build directory, and must
  # keep the name their Make rules use even when the tool runs in a
  # build directory nested inside the source tree.
  def relative_dependency(path)
    expanded = File.expand_path(path, @root)
    prefix = @root + File::SEPARATOR
    if expanded.start_with?(prefix) &&
        (File.absolute_path?(path) || File.exist?(expanded))
      expanded.delete_prefix(prefix)
    else
      path
    end
  end

  # Converts an extension dependency to the Make variable path it requires.
  def extension_dependency(file, source_dir)
    case file
    when %r[\A(?:#{Regexp.escape(source_dir)}/)?extconf\.h\z]
      "$(RUBY_EXTCONF_H)"
    when 'config.h'
      "$(arch_hdrdir)/ruby/config.h"
    when %r[\Ainclude/]
      "$(hdrdir)/#$'"
    when 'probes.h'
    else
      if file.start_with?(prefix = source_dir + "/")
        file.delete_prefix(prefix)
      elsif file.start_with?(prefix = File.dirname(source_dir) + "/")
        "$(srcdir)/../#{file.delete_prefix(prefix)}"
      elsif !file.include?("/") && File.file?(File.join(@root, source_dir, file))
        file
      elsif /\.e?rb\z/.match?(file)
        nil
      else
        "$(top_srcdir)/#{file}"
      end
    end
  end

  # Converts a standalone project's file to a dependency relative to its source.
  def project_dependency(file, source_dir)
    source_dir = File.join(@root, source_dir)
    path = File.expand_path(file, @root)
    prefix = @root + File::SEPARATOR
    return unless path.start_with?(prefix)

    dependency = Pathname.new(path).relative_path_from(
      Pathname.new(source_dir)
    ).to_s.tr(File::SEPARATOR, "/")
    return dependency unless dependency.start_with?("../")
    "$(srcdir)/#{dependency}"
  end

  # Converts scanned +files+ into sorted Make dependencies for +source+.
  def depends(files, vpath, source: nil, input: nil, declarations: nil,
              project: false)
    declaration_input = input || dependency_input(source)
    declarations ||= dependency_declarations(declaration_input, source: source)
    extension_dir = File.dirname(source) if source&.start_with?("ext/")
    project_dir = File.dirname(source) if project
    expand = lambda do |file, expanded|
      if !expanded.include?(file) &&
          (dependencies = declaration(declarations.dependencies, file,
                                      declaration_input))
        dependencies[1].flat_map {|dep| expand.call(dep, expanded | [file])}
      else
        file
      end
    end
    files = files.flat_map {|file| expand.call(file, [])}
    files.each_with_object([]) do |file, deps|
      file = relative_dependency(file)
      dep = if file.start_with?('$(', '{$(')
        file
      elsif target = dependency_target(file, declaration_input)
        target
      elsif project_dir
        project_dependency(file, project_dir)
      elsif extension_dir
        extension_dependency(file, extension_dir)
      else
        case file
        when %r[\Aenc/unicode/[\d.]+/]
          "$(UNICODE_HDR_DIR)/#$'"
        when 'encindex.h', 'transcode_data.h', /\Areg(?!ex\b)\w+\.h\z/
          "#{vpath || '$(top_srcdir)/'}#{file}"
        when /\.e?rb\z/
        when %r[\Atool/]
          "$(top_srcdir)/#{file}"
        when %r[\Ainclude/\Kruby(?:/ruby|/version)?\.h\z]
          "$(hdrdir)/#$&"
        when %r[\A(?:internal|prism)\/]
          "$(top_srcdir)/#{file}"
        when %r[\Accan/]
          "$(CCAN_DIR)/#$'"
        when %r[\Aenc/]
          "#{vpath}#{file}"
        when %r[\Ainclude/ruby/], %r[\Amissing/]
          "#{vpath}#$'"
        else
          "#{vpath}#{file}"
        end
      end
      deps << dep if dep
    end.uniq.sort
  end

  # Returns the Make object name for source path +src+.
  def object_name(src)
    stem = src.sub(/\.[cy]\z/, "")
    if src.start_with?("ext/")
      "#{File.basename(stem)}.o"
    else
      "#{stem.delete_prefix('missing/')}.$(OBJEXT)"
    end
  end

  # Returns the VPATH prefix used for dependencies of +source+.
  def dependency_vpath(input, source)
    return if source.start_with?("enc/") &&
      (!input || relative_source(input) == "enc/depend")
    "{$(VPATH)}"
  end

  # Returns whether +source+ is declared as generated or otherwise resolvable.
  def dependency_source?(source, input = nil)
    declarations = dependency_declarations(input, source: source)
    declaration(declarations.scan, source, input) ||
      declaration(declarations.dependencies, source, input) ||
      dependency_target(source, input || dependency_input(source))
  end

  # Builds a Scanner configured by the declarations governing +src+.
  def dependency_scanner(src, declarations, input)
    macros = {}
    macros["RUBY_EXTCONF_H"] = "extconf.h" if src.start_with?("ext/")
    defined = declaration(declarations.defines, src, input)&.last || []
    undefined = %w[__cplusplus]
    if undefined_macros = declaration(declarations.undefines, src, input)
      undefined.concat(undefined_macros[1])
    end
    Scanner.new(
      root: @root,
      include_dirs: [
        @root,
        File.join(@root, "include"),
        File.join(@root, "prism"),
        File.dirname(src),
      ],
      macros: macros,
      targets: dependency_targets(input),
      aliases: declarations.scan,
      dependencies: declarations.dependencies,
      defined: defined,
      undefined: undefined,
      cache: @source_cache,
    )
  end

  # Appends Make dependency rules for +src+ to +out+ and returns +out+.
  def makedepend(src, out = [], target: nil, input: nil, project: false,
                 accessed: nil)
    src = relative_dependency(src)
    declaration_input = input || dependency_input(src)
    declarations = dependency_declarations(declaration_input, source: src)
    vpath = dependency_vpath(input, src)
    scanner = dependency_scanner(src, declarations, declaration_input)
    scan_source = if mapping = declaration(declarations.scan, src,
                                           declaration_input)
      mapping[1]
    else
      src
    end
    files = scanner.scan(scan_source)
    accessed&.merge(scanner.accessed)
    if dependencies = declaration(declarations.dependencies, src,
                                  declaration_input)
      files.concat(dependencies[1])
    end
    files << src if scan_source != src
    files << src.sub(/\.y\z/, ".c") if src.end_with?(".y")
    obj = if target
      src.start_with?("ext/") ? "#{target}.o" : "#{target}.$(OBJEXT)"
    else
      object_name(src)
    end
    depends(files, vpath, source: src, input: input,
            declarations: declarations, project: project).each do |dep|
      out << "#{obj}: #{dep}\n"
    end
    out
  end

  # Sorts and deduplicates +rules+, optionally grouping targets by dependency.
  def compact_dependencies(rules, group: true)
    return rules.lines.uniq.sort.join unless group

    grouped = Hash.new {|hash, dependency| hash[dependency] = []}
    lines = []
    rules.each_line do |line|
      unless /\A(\S+):\s+(\S+)\s*\z/ =~ line
        lines << line
        next
      end
      target, dependency = $1, $2
      if dependency.end_with?(".c", ".y")
        lines << "#{target}: #{dependency}\n"
      else
        grouped[dependency] << target
      end
    end
    grouped.each do |dependency, targets|
      targets.uniq.sort.each_slice(8) do |slice|
        lines << "#{slice.join(' ')}: #{dependency}\n"
      end
    end
    lines.uniq.sort.join
  end

  # Returns target and dependency pairs from Make rules.
  def dependency_pairs(rules)
    rules = normalize_dependency_rules(rules)
    rules.each_line.each_with_object(Set.new) do |line, pairs|
      next unless /\A(\S+(?:\s+\S+)*):\s*(.*?)\s*\z/ =~ line

      targets = $1.split
      dependencies = expand_dependency_variables($2.split).map do |dependency|
        normalize_dependency_rules(dependency)
      end
      targets.product(dependencies) {|pair| pairs << pair}
    end
  end

  # Removes generated dependencies already covered by +manual_rules+.
  def remove_manual_dependencies(generated, manual_rules)
    manual = dependency_pairs(manual_rules)
    generated.each_line.reject do |line|
      normalized = normalize_dependency_rules(line)
      /\A(\S+):\s+(\S+)\s*\z/ =~ normalized &&
        manual.include?([$1, $2])
    end.join
  end

  # Removes VPATH markers that are unnecessary in build-directory output.
  def normalize_dependency_rules(rules)
    rules.gsub(/\{(?:\.;)?\$\(VPATH\)\}/, '')
  end

  # Returns whether two rule sets differ only by removable VPATH markers.
  def same_dependency_rules?(left, right)
    normalize_dependency_rules(left) == normalize_dependency_rules(right)
  end

  MARK_START = "# AUTOGENERATED DEPENDENCIES START" # :nodoc:
  MARK_END = "# AUTOGENERATED DEPENDENCIES END" # :nodoc:
  MARK_SECTION =
    /^#{Regexp.escape(MARK_START)}[^\S\n]*(?:\z|\n\K(?m:.*?)(?=(^#{Regexp.escape(MARK_END)}(?:\n|\z))|\z))/ # :nodoc:

  private_constant :MARK_START, :MARK_END, :MARK_SECTION

  # Returns marked dependency files selected by +scope+.
  def dependency_files(scope = :all)
    Dir.chdir(@root) do
      files = case scope
      when :all
        %w[depend enc/depend].concat(Dir.glob("ext/**/depend"))
      when :core
        %w[depend enc/depend]
      when :extensions
        Dir.glob("ext/**/depend")
      else
        raise ArgumentError, "unknown dependency scope: #{scope}"
      end
      files.select do |file|
        next false unless File.file?(file)
        content = File.read(file)
        next false unless content.include?(MARK_START)
        dependency_file_content(file, content)
        true
      end
    end
  end

  # Extracts the best source rule for each object target in +rules+.
  def dependency_source_rules(rules, input)
    input = relative_source(input)
    srcs = {}
    rules.each_line do |line|
      next unless %r[\A([-.\w/]+)\.(?:\$\(OBJEXT\)|o):\s+(.+?)\s*\z] =~ line
      target, dependency = $1, $2
      next unless src = dependency[%r{[-.\w/]+\.[cy]\z}]
      src = src.delete_prefix("/")
      source_name = File.basename(src, ".*")
      target_name = File.basename(target)
      next unless target_name == source_name || target_name.end_with?("-#{source_name}")
      local = input.start_with?("ext/") && !dependency.include?("$(top_srcdir)")
      src = File.join(File.dirname(input), src) if local && !src.start_with?("ext/")
      rank = src.end_with?(".y") ? 2 : local ? 1 : 0
      current = srcs[target]
      srcs[target] = [rank, src, line] if !current || rank >= current.first
    end
    srcs.sort.to_h
  end

  # Returns an object-target to source-path mapping extracted from +rules+.
  def dependency_source_map(rules, input)
    dependency_source_rules(rules, input).each_with_object({}) do |(target, data), result|
      result[target] = data[1]
    end
  end

  # Returns the source paths identified by +rules+.
  def dependency_sources(rules, input)
    dependency_source_map(rules, input).values
  end

  # Resolves +src+ to an existing, missing-library, or declared source path.
  def resolve_dependency_source(src, input)
    return src if File.file?(File.join(@root, src))

    missing = "missing/#{src}"
    return missing if File.file?(File.join(@root, missing))
    return src if dependency_source?(src, input)

    raise "source file not found: #{src} in #{input}"
  end

  # Reduces +rules+ to source mappings needed to regenerate dependencies.
  def minimize_deps(rules, input)
    sources = dependency_source_rules(rules, input)
    targets = rules.scan(%r[^([-\.\w/]+)\.(?:\$\(OBJEXT\)|o):]).flatten.uniq
    unless (missing = targets - sources.keys).empty?
      raise "no source files for #{missing.join(', ')} in #{input}"
    end
    sources.each_value {|_, src| resolve_dependency_source(src, input)}
    minimal = sources.values.map(&:last)
    if relative_source(input).start_with?("ext/")
      rules.each_line do |line|
        minimal << line if /\A.*:\s+\$\(srcdir\)\//.match?(line)
      end
    end
    minimal.uniq.sort.join
  end

  # Regenerates dependency +rules+ for the sources identified in +input+.
  def update_deps(rules, input, group: true, verbose: false, accessed: nil)
    sources = dependency_source_map(rules, input)
    targets = rules.scan(%r[^([-.\w/]+)\.(?:\$\(OBJEXT\)|o):]).flatten.uniq
    unless (missing = targets - sources.keys).empty?
      raise "no source files for #{missing.join(', ')} in #{input}"
    end
    generated = []
    sources.each do |target, src|
      src = resolve_dependency_source(src, input)
      warn "dependencies for #{src}:" if verbose
      makedepend(
        src, generated, target: target, input: input, accessed: accessed,
      )
    end
    compact_dependencies(generated.join, group: group)
  end

  public

  # Updates the marked dependency section in extension file +input+.
  #
  # +source_map+ maps object targets to source paths.  +make_variables+
  # supplies values of Make variables used by manual dependency rules.
  # Returns +true+ when the file changed and +false+ when its dependencies
  # were already current.
  def update_extension(input, source_map, make_variables: {}, nmake: false,
                       verbose: false)
    select_make_variables(make_variables)
    input = File.expand_path(input)
    deps = File.read(input) if File.file?(input)
    match = MARK_SECTION.match(deps) if deps
    unless match
      raise "#{input}: no autogenerated dependency section"
    end
    raise "missing #{MARK_END} in #{input}" unless match.begin(1)

    dependency_declarations(input, content: deps)
    dependency_targets(input, deps)
    generated = []
    source_map.each do |target, source|
      source = relative_source(source)
      warn "dependencies for #{source}:" if verbose
      makedepend(
        source, generated, target: target, input: input, project: true
      )
    end
    manual = match.pre_match + match.post_match
    generated = remove_manual_dependencies(generated.join, manual)
    expected = compact_dependencies(generated, group: !nmake)
    updated = match.pre_match + expected + match.post_match
    return false if same_dependency_rules?(match[0], expected)

    replace_file(input, updated)
    true
  end

  private

  # Atomically replaces +path+ with +content+, preserving its file mode.
  def replace_file(path, content)
    dir = File.dirname(path)
    FileUtils.mkdir_p(dir)
    mode = File.exist?(path) ? File.stat(path).mode & 0777 : 0644
    Tempfile.create([File.basename(path), ".tmp"], dir) do |file|
      file.binmode
      file.write(content)
      file.flush
      file.chmod(mode)
      file.close
      File.rename(file.path, path)
    end
  end

  DEPENDENCY_CACHE_VERSION = 1 # :nodoc:
  private_constant :DEPENDENCY_CACHE_VERSION

  # Returns the cache signature for options affecting generated dependencies.
  def dependency_cache_signature(nmake:, sources:)
    [DEPENDENCY_CACHE_VERSION, nmake, sources, @make_variables.sort].inspect
  end

  # Returns cached stat information, or +false+ when +path+ does not exist.
  def dependency_stat(path)
    path = File.expand_path(path)
    return @stat_cache[path] if @stat_cache.key?(path)

    @stat_cache[path] = File.stat(path)
  rescue Errno::ENOENT, Errno::ENOTDIR
    @stat_cache[path] = false
  end

  # Returns whether +destination+ and all recorded scan inputs are unchanged.
  def dependency_output_fresh?(destination, signature)
    cache_path = destination + ".mkdepend"
    return false unless (output_stat = dependency_stat(destination))
    return false unless File.file?(cache_path)

    lines = File.readlines(cache_path, chomp: true)
    header = lines.shift&.split("\t", 5)
    return false unless header == [
      "mkdepend", signature, output_stat.size.to_s,
      output_stat.mtime.to_i.to_s, output_stat.mtime.nsec.to_s,
    ]

    lines.all? do |line|
      state, path = line.split("\t", 2)
      next false unless path

      stat = dependency_stat(path)
      state == "+" ? stat && stat.mtime <= output_stat.mtime : !stat
    end
  rescue Errno::ENOENT
    false
  end

  # Records scan inputs used to produce +destination+.
  def write_dependency_cache(destination, signature, paths)
    output_stat = File.stat(destination)
    lines = [
      [
        "mkdepend", signature, output_stat.size,
        output_stat.mtime.to_i, output_stat.mtime.nsec,
      ].join("\t") + "\n",
    ]
    paths.sort.each do |path|
      exists = if @source_cache.key?(path)
        @source_cache[path]
      else
        File.file?(path)
      end
      lines << "#{exists ? '+' : '-'}\t#{path}\n"
    end
    replace_file(destination + ".mkdepend", lines.join)
  end

  # Reports how dependency rules in +input+ differ from +expected+.
  def report_outdated_dependencies(input, current, expected, err: $stderr)
    current_lines = current.lines
    expected_lines = expected.lines
    label = relative_source(input)
    err.puts "#{label}: dependencies are outdated"
    if current_lines.size <= 20
      err.puts "  current dependency rules:"
      current_lines.each {|line| err.puts "    #{line.chomp}"}
    else
      current_word = current_lines.one? ? "rule" : "rules"
      expected_word = expected_lines.one? ? "source rule" : "source rules"
      err.puts "  current section has #{current_lines.size} #{current_word}; " \
               "expected #{expected_lines.size} #{expected_word}"
    end
    err.puts "  expected source rules:"
    expected_lines.each {|line| err.puts "    #{line.chomp}"}
  end

  public

  # Processes dependency +inputs+ according to the selected update +mode+.
  #
  # +make_variables+ supplies values for Make variables in declarations.
  # +thread_model+ is a shortcut for its <tt>THREAD_MODEL</tt> entry.
  #
  # Returns +false+ only when check mode finds an outdated dependency file.
  def run(inputs = ARGV, out: $stdout, err: $stderr, mode: :stdout,
          output: nil, make_variables: {}, nmake: false, sources: false,
          scope: nil, thread_model: nil, verbose: false)
    @source_cache.clear
    @stat_cache.clear
    case mode
    when :output
      raise ArgumentError, "output directory is missing" unless output
    when :stdout, :inplace, :check
      raise ArgumentError, "output requires output mode" if output
    else
      raise ArgumentError, "unknown update mode: #{mode.inspect}"
    end
    unless thread_model.nil?
      if thread_model.empty?
        raise ArgumentError, "thread model must not be empty"
      end
      make_variables = make_variables.merge("THREAD_MODEL" => thread_model)
    end
    select_make_variables(make_variables)
    if scope
      inputs = dependency_files(scope).map {|file| File.join(@root, file)}
    end
    output = File.expand_path(output) if output
    cache_signature = dependency_cache_signature(
      nmake: nmake, sources: sources,
    )
    changed = false
    inputs.each do |input|
      if input.end_with?(".c", ".y")
        out.puts makedepend(relative_source(input))
      else
        deps = dependency_file_content(input) || File.read(input)
        dependency_declarations(input, content: deps)
        dependency_targets(input, deps)
        match = MARK_SECTION.match(deps)
        next unless match
        raise "missing #{MARK_END} in #{input}" unless match.begin(1)

        destination = File.join(output, relative_source(input)) if output
        if destination && dependency_output_fresh?(destination, cache_signature)
          next
        end

        current_rules = match[0]
        accessed = Set.new
        expected = update_deps(
          current_rules, input, group: !nmake, verbose: verbose,
          accessed: accessed,
        )
        expected = minimize_deps(expected, input) if sources
        updated = match.pre_match + expected + match.post_match
        if mode == :output
          updated = normalize_dependency_rules(updated) unless nmake
          replace_file(destination, updated)
          accessed.add(File.expand_path(input))
          accessed.add(File.join(@root, "depend"))
          accessed.add(File.expand_path(__FILE__))
          accessed.add(File.join(@root, "tool/mkdepend.rb"))
          write_dependency_cache(destination, cache_signature, accessed)
        elsif same_dependency_rules?(current_rules, expected)
          next
        elsif mode == :inplace
          replace_file(input, updated)
          changed = true
        elsif mode == :check
          report_outdated_dependencies(input, current_rules, expected, err: err)
          changed = true
        else
          out.puts updated
          changed = true
        end
      end
    end
    if mode == :check && changed
      options = " --sources" if sources
      err.puts "\nupdate with:"
      err.puts "  ruby tool/mkdepend.rb --scope=all#{options} --inplace"
    end
    mode != :check || !changed
  end
end
