<commit_before>require 'tsort'

require 'librarian/helpers/debug'

require 'librarian/dependency'

module Librarian
  class Resolver

    class GraphHash < Hash
      include TSort
      alias tsort_each_node each_key
      def tsort_each_child(node, &block)
        self[node].each(&block)
      end
    end

    class Implementation
      include Helpers::Debug

      attr_reader :resolver, :source, :dependency_source_map

      def initialize(resolver, spec)
        @resolver = resolver
        @source = spec.source
        @dependency_source_map = Hash[spec.dependencies.map{|d| [d.name, d.source]}]
        @level = 0
      end

      def resolve(dependencies)
        resolution = recursive_resolve([], {}, dependencies.dup)
        resolution ? resolution[1] : nil
      end

      def recursive_resolve(dependencies, manifests, queue)
        if dependencies.empty?
          queue.each do |dependency|
            debug { "Scheduling #{dependency}" }
          end
        end
        failure = false
        until failure || queue.empty?
          dependency = queue.shift
          dependencies << dependency
          debug { "Resolving #{dependency}" }
          scope do
            if manifests.key?(dependency.name)
              unless dependency.satisfied_by?(manifests[dependency.name])
                debug { "Conflicts with #{manifests[dependency.name]}" }
                failure = true
              else
                debug { "Accords with all prior constraints" }
                # nothing left to do
              end
            else
              debug { "No known prior constraints" }
              resolution = nil
              related_dependencies = dependencies.select{|d| d.name == dependency.name}
              unless dependency.manifests && dependency.manifests.first
                debug { "No known manifests" }
              else
                debug { "Checking manifests" }
                scope do
                  dependency.manifests.each do |manifest|
                    unless resolution
                      debug { "Checking #{manifest}" }
                      scope do
                        if related_dependencies.all?{|d| d.satisfied_by?(manifest)}
                          d = dependencies.dup
                          m = manifests.merge(dependency.name => manifest)
                          a = manifest.dependencies.map { |d|
                            d.source ? d :
                            !dependency_source_map.key?(d.name) ?
                            Dependency.new(d.name, d.requirement, source) :
                            Dependency.new(d.name, d.requirement, dependency_source_map[d.name])
                          }
                          a.each do |d|
                            debug { "Scheduling #{d}" }
                          end
                          q = queue + a
                          resolution = recursive_resolve(d, m, q)
                        end
                        if resolution
                          debug { "Resolved #{dependency} at #{manifest}" }
                        else
                          debug { "Backtracking from #{manifest}" }
                        end
                      end
                    end
                  end
                end
                if resolution
                  debug { "Resolved #{dependency}" }
                else
                  debug { "Failed to resolve #{dependency}" }
                end
              end
              unless resolution
                failure = true
              else
                dependencies, manifests, queue = *resolution
              end
            end
          end
        end
        failure ? nil : [dependencies, manifests, queue]
      end
<commit_msg>Fix for 1.8.7.<commit_after>require 'tsort'

require 'librarian/helpers/debug'

require 'librarian/dependency'

module Librarian
  class Resolver

    class GraphHash < Hash
      include TSort
      alias tsort_each_node each_key
      def tsort_each_child(node, &block)
        self[node].each(&block)
      end
    end

    class Implementation
      include Helpers::Debug

      attr_reader :resolver, :source, :dependency_source_map

      def initialize(resolver, spec)
        @resolver = resolver
        @source = spec.source
        @dependency_source_map = Hash[spec.dependencies.map{|d| [d.name, d.source]}]
        @level = 0
      end

      def resolve(dependencies)
        resolution = recursive_resolve([], {}, dependencies.dup)
        resolution ? resolution[1] : nil
      end

      def recursive_resolve(dependencies, manifests, queue)
        if dependencies.empty?
          queue.each do |dependency|
            debug { "Scheduling #{dependency}" }
          end
        end
        failure = false
        until failure || queue.empty?
          dependency = queue.shift
          dependencies << dependency
          debug { "Resolving #{dependency}" }
          scope do
            if manifests.key?(dependency.name)
              unless dependency.satisfied_by?(manifests[dependency.name])
                debug { "Conflicts with #{manifests[dependency.name]}" }
                failure = true
              else
                debug { "Accords with all prior constraints" }
                # nothing left to do
              end
            else
              debug { "No known prior constraints" }
              resolution = nil
              related_dependencies = dependencies.select{|d| d.name == dependency.name}
              unless dependency.manifests && dependency.manifests.first
                debug { "No known manifests" }
              else
                debug { "Checking manifests" }
                scope do
                  dependency.manifests.each do |manifest|
                    unless resolution
                      debug { "Checking #{manifest}" }
                      scope do
                        if related_dependencies.all?{|d| d.satisfied_by?(manifest)}
                          m = manifests.merge(dependency.name => manifest)
                          a = manifest.dependencies.map { |d|
                            d.source ? d :
                            !dependency_source_map.key?(d.name) ?
                            Dependency.new(d.name, d.requirement, source) :
                            Dependency.new(d.name, d.requirement, dependency_source_map[d.name])
                          }
                          a.each do |d|
                            debug { "Scheduling #{d}" }
                          end
                          q = queue + a
                          resolution = recursive_resolve(dependencies.dup, m, q)
                        end
                        if resolution
                          debug { "Resolved #{dependency} at #{manifest}" }
                        else
                          debug { "Backtracking from #{manifest}" }
                        end
                      end
                    end
                  end
                end
                if resolution
                  debug { "Resolved #{dependency}" }
                else
                  debug { "Failed to resolve #{dependency}" }
                end
              end
              unless resolution
                failure = true
              else
                dependencies, manifests, queue = *resolution
              end
            end
          end
        end
        failure ? nil : [dependencies, manifests, queue]
      end

{'fraction_non_alphanumeric': 0.0753016041362853, 'fraction_numerical': 0.000928012727031685, 'mean_word_length': 1.2052031569716457, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 5, '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': '2455347', 'n_tokens_mistral': 1835, 'n_tokens_neox': 1662, 'n_words': 448}