#--
# Copyright 2006 by Chad Fowler, Rich Kilmer, Jim Weirich and others.
# All rights reserved.
# See LICENSE.txt for permissions.
#++

require 'tsort'

class Gem::DependencyList

  include TSort

  def self.from_source_index(src_index)
    deps = new

    src_index.each do |full_name, spec|
      deps.add spec
    end

    deps
  end

  def initialize
    @specs = []
  end

  # Adds +gemspecs+ to the dependency list.
  def add(*gemspecs)
    @specs.push(*gemspecs)
  end

  # Return a list of the specifications in the dependency list,
  # sorted in order so that no spec in the list depends on a gem
  # earlier in the list.
  #
  # This is useful when removing gems from a set of installed gems.
  # By removing them in the returned order, you don't get into as
  # many dependency issues.
  #
  # If there are circular dependencies (yuck!), then gems will be
  # returned in order until only the circular dependents and anything
  # they reference are left.  Then arbitrary gemspecs will be returned
  # until the circular dependency is broken, after which gems will be
  # returned in dependency order again.
  def dependency_order
    sorted = strongly_connected_components.flatten

    result = []
    seen = {}

    sorted.each do |spec|
      if index = seen[spec.name] then
        if result[index].version < spec.version then
          result[index] = spec
        end
      else
        seen[spec.name] = result.length
        result << spec
      end
    end

    result.reverse
  end

  def find_name(full_name)
    @specs.find { |spec| spec.full_name == full_name }
  end

  # Are all the dependencies in the list satisfied?
  def ok?
    @specs.all? do |spec|
      spec.runtime_dependencies.all? do |dep|
        @specs.find { |s| s.satisfies_requirement? dep }
      end
    end
  end

  # Is is ok to remove a gem from the dependency list?
  #
  # If removing the gemspec creates breaks a currently ok dependency,
  # then it is NOT ok to remove the gem.
  def ok_to_remove?(full_name)
    gem_to_remove = find_name full_name

    siblings = @specs.find_all { |s|
      s.name == gem_to_remove.name &&
        s.full_name != gem_to_remove.full_name
    }

    deps = []

    @specs.each do |spec|
      spec.dependencies.each do |dep|
        deps << dep if gem_to_remove.satisfies_requirement?(dep)
      end
    end

    deps.all? { |dep|
      siblings.any? { |s|
        s.satisfies_requirement? dep
      }
    }
  end

  def remove_by_name(full_name)
    @specs.delete_if { |spec| spec.full_name == full_name }
  end

  # Return a hash of predecessors.  <tt>result[spec]</tt> is an
  # Array of gemspecs that have a dependency satisfied by the named
  # spec.
  def spec_predecessors
    result = Hash.new { |h,k| h[k] = [] }

    specs = @specs.sort.reverse

    specs.each do |spec|
      specs.each do |other|
        next if spec == other

        other.dependencies.each do |dep|
          if spec.satisfies_requirement? dep then
            result[spec] << other
          end
        end
      end
    end

    result
  end

  def tsort_each_node(&block)
    @specs.each(&block)
  end

  def tsort_each_child(node, &block)
    specs = @specs.sort.reverse

    node.dependencies.each do |dep|
      specs.each do |spec|
        if spec.satisfies_requirement? dep then
          begin
            yield spec
          rescue TSort::Cyclic
          end
          break
        end
      end
    end
  end

  private

  # Count the number of gemspecs in the list +specs+ that are not in
  # +ignored+.
  def active_count(specs, ignored)
    result = 0
    specs.each do |spec|
      result += 1 unless ignored[spec.full_name]
    end
    result
  end

end