require "set" unless defined?(Set)
require "molinillo"
require "molinillo/modules/specification_provider"
require_relative "solver/serializer"

module Solve
  class RubySolver
    class << self
      # The timeout (in seconds) to use when resolving graphs. Default is 10. This can be
      # configured by setting the SOLVE_TIMEOUT environment variable.
      #
      # @return [Integer]
      def timeout
        seconds = 30 unless ( seconds = ENV["SOLVE_TIMEOUT"] )
        seconds.to_i * 1_000
      end

      # For optional solver engines, this attempts to load depenencies. The
      # RubySolver is a non-optional component, so this is a no-op
      def activate
        true
      end
    end

    # Graph object with references to all known artifacts and dependency
    # constraints.
    #
    # @return [Solve::Graph]
    attr_reader :graph

    # @example Demands are Arrays of Arrays with an artifact name and optional constraint:
    #   [['nginx', '= 1.0.0'], ['mysql']]
    # @return [Array<String>, Array<Array<String, String>>] demands
    attr_reader :demands_array

    # @example Basic use:
    #   graph = Solve::Graph.new
    #   graph.artifacts("mysql", "1.2.0")
    #   demands = [["mysql"]]
    #   RubySolver.new(graph, demands)
    # @param [Solve::Graph] graph
    # @param [Array<String>, Array<Array<String, String>>] demands
    def initialize(graph, demands, options = {})
      @graph         = graph
      @demands_array = demands
      @timeout_ms    = self.class.timeout

      @ui = options[:ui] # could be nil, but that's okay
      @dependency_source = options[:dependency_source] || "user-specified dependency"

      @molinillo_graph = Molinillo::DependencyGraph.new
      @resolver = Molinillo::Resolver.new(self, self)
    end

    # The problem demands given as Demand model objects
    # @return [Array<Solve::Demand>]
    def demands
      demands_array.map do |name, constraint|
        Demand.new(self, name, constraint)
      end
    end

    # @option options [Boolean] :sorted
    #   return the solution as a sorted list instead of a Hash
    #
    # @return [Hash, List] Returns a hash like { "Artifact Name" => "Version",... }
    #   unless the :sorted option is true, then it returns a list like [["Artifact Name", "Version],...]
    # @raise [Errors::NoSolutionError] when the demands cannot be met for the
    #   given graph.
    # @raise [Errors::UnsortableSolutionError] when the :sorted option is true
    #   and the demands have a solution, but the solution contains a cyclic
    #   dependency
    def resolve(options = {})
      @ui = options[:ui] if options[:ui]

      solved_graph = resolve_with_error_wrapping

      solution = solved_graph.map(&:payload)

      unsorted_solution = solution.inject({}) do |stringified_soln, artifact|
        stringified_soln[artifact.name] = artifact.version.to_s
        stringified_soln
      end

      if options[:sorted]
        build_sorted_solution(unsorted_solution)
      else
        unsorted_solution
      end
    end

    ###
    # Molinillo Callbacks
    #
    # Molinillo calls back to this class to get information about our
    # dependency model objects. An abstract implementation is provided at
    # https://github.com/CocoaPods/Molinillo/blob/master/lib/molinillo/modules/specification_provider.rb
    #
    ###

    # Callback required by Molinillo, called when the solve starts
    # @return [Integer]
    def progress_rate
      1
    end

    # Callback required by Molinillo, called when the solve starts
    # @return nil
    def before_resolution
      @ui.say("Starting dependency resolution") if @ui
    end

    # Callback required by Molinillo, called when the solve is complete.
    # @return nil
    def after_resolution
      @ui.say("Finished dependency resolution") if @ui
    end

    # Callback required by Molinillo, called when resolving every progress_rate
    # @return nil
    def indicate_progress
      nil
    end

    # Callback required by Molinillo, gives debug information about the solution
    # @return nil
    def debug(current_resolver_depth = 0)
      # debug info will be returned if you call yield here, but it seems to be
      # broken in current Molinillo
      @ui.say(yield) if @ui
    end

    include Molinillo::SpecificationProvider

    # Callback required by Molinillo
    # Search for the specifications that match the given dependency.
    # The specifications in the returned array will be considered in reverse
    # order, so the latest version ought to be last.
    # @note This method should be 'pure', i.e. the return value should depend
    #   only on the `dependency` parameter.
    #
    # @param [Object] dependency
    # @return [Array<Solve::Artifact>] the artifacts that match the dependency.
    def search_for(dependency)
      # This array gets mutated by Molinillo; it's okay because sort returns a
      # new array.
      graph.versions(dependency.name, dependency.constraint).sort
    end

    # Callback required by Molinillo
    # Returns the dependencies of `specification`.
    # @note This method should be 'pure', i.e. the return value should depend
    #   only on the `specification` parameter.
    #
    # @param [Object] specification
    # @return [Array<Solve::Dependency>] the dependencies of the given artifact
    def dependencies_for(specification)
      specification.dependencies
    end

    # Callback required by Molinillo
    # Determines whether the given `requirement` is satisfied by the given
    # `spec`, in the context of the current `activated` dependency graph.
    #
    # @param [Object] requirement
    # @param [DependencyGraph] activated the current dependency graph in the
    #   resolution process.
    # @param [Object] spec
    # @return [Boolean] whether `requirement` is satisfied by `spec` in the
    #   context of the current `activated` dependency graph.
    def requirement_satisfied_by?(requirement, activated, spec)
      version = spec.version
      return false unless requirement.constraint.satisfies?(version)

      shared_possibility_versions = possibility_versions(requirement, activated)
      return false if !shared_possibility_versions.empty? && !shared_possibility_versions.include?(version)

      true
    end

    # Searches the current dependency graph to find previously activated
    # requirements for the current artifact.
    #
    # @param [Object] requirement
    # @param [DependencyGraph] activated the current dependency graph in the
    #   resolution process.
    # @return [Array<Semverse::Version> the list of currently activated versions
    # of this requirement
    def possibility_versions(requirement, activated)
      activated.vertices.values.flat_map do |vertex|

        next unless vertex.payload

        next unless vertex.name == requirement.name

        if vertex.payload.respond_to?(:possibilities)
          vertex.payload.possibilities.map(&:version)
        else
          vertex.payload.version
        end
      end.compact
    end
    private :possibility_versions

    # Callback required by Molinillo
    # Returns the name for the given `dependency`.
    # @note This method should be 'pure', i.e. the return value should depend
    #   only on the `dependency` parameter.
    #
    # @param [Object] dependency
    # @return [String] the name for the given `dependency`.
    def name_for(dependency)
      dependency.name
    end

    # Callback required by Molinillo
    # @return [String] the name of the source of explicit dependencies, i.e.
    #   those passed to {Resolver#resolve} directly.
    def name_for_explicit_dependency_source
      @dependency_source
    end

    # Callback required by Molinillo
    # Sort dependencies so that the ones that are easiest to resolve are first.
    # Easiest to resolve is (usually) defined by:
    #   1) Is this dependency already activated?
    #   2) How relaxed are the requirements?
    #   3) Are there any conflicts for this dependency?
    #   4) How many possibilities are there to satisfy this dependency?
    #
    # @param [Array<Object>] dependencies
    # @param [DependencyGraph] activated the current dependency graph in the
    #   resolution process.
    # @param [{String => Array<Conflict>}] conflicts
    # @return [Array<Solve::Dependency>] the dependencies sorted by preference.
    def sort_dependencies(dependencies, activated, conflicts)
      dependencies.sort_by do |dependency|
        name = name_for(dependency)
        [
          activated.vertex_named(name).payload ? 0 : 1,
          conflicts[name] ? 0 : 1,
          search_for(dependency).count,
        ]
      end
    end

    # Callback required by Molinillo
    # Returns whether this dependency, which has no possible matching
    # specifications, can safely be ignored.
    #
    # @param [Object] dependency
    # @return [Boolean] whether this dependency can safely be skipped.
    def allow_missing?(dependency)
      false
    end

    private

    def resolve_with_error_wrapping
      @resolver.resolve(demands, @molinillo_graph)
    rescue Molinillo::VersionConflict, Molinillo::CircularDependencyError => e
      raise Solve::Errors::NoSolutionError.new(e.message)
    end

    def build_sorted_solution(unsorted_solution)
      nodes = {}
      unsorted_solution.each do |name, version|
        nodes[name] = @graph.artifact(name, version).dependencies.map(&:name)
      end

      # Modified from http://ruby-doc.org/stdlib-1.9.3/libdoc/tsort/rdoc/TSort.html
      class << nodes
        include TSort
        alias tsort_each_node each_key
        def tsort_each_child(node, &block)
          fetch(node).each(&block)
        end
      end
      begin
        sorted_names = nodes.tsort
      rescue TSort::Cyclic => e
        raise Solve::Errors::UnsortableSolutionError.new(e, unsorted_solution)
      end

      sorted_names.map do |artifact|
        [artifact, unsorted_solution[artifact]]
      end
    end
  end
end