summaryrefslogtreecommitdiff
path: root/lib/bundler/resolver.rb
blob: 5ec46acc82cfe265efa8aa1e0bc695cfa0bc0485 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
require 'set'

# This is the latest iteration of the gem dependency resolving algorithm. As of now,
# it can resolve (as a success or failure) any set of gem dependencies we throw at it
# in a reasonable amount of time. The most iterations I've seen it take is about 150.
# The actual implementation of the algorithm is not as good as it could be yet, but that
# can come later.

module Bundler
  class Resolver

    require 'bundler/vendored_molinillo'

    class Molinillo::VersionConflict
      def clean_req(req)
        if req.to_s.include?(">= 0")
          req.to_s.gsub(/ \(.*?\)$/, '')
        else
          req.to_s.gsub(/\, (runtime|development)\)$/, ')')
        end
      end

      def message
        conflicts.values.flatten.reduce('') do |o, conflict|
          o << %(Bundler could not find compatible versions for gem "#{conflict.requirement.name}":\n)
          if conflict.locked_requirement
            o << %(  In snapshot (Gemfile.lock):\n)
            o << %(    #{clean_req conflict.locked_requirement}\n)
            o << %(\n)
          end
          o << %(  In Gemfile:\n)
          o << conflict.requirement_trees.map do |tree|
            t = ''
            depth = 2
            tree.each do |req|
              t << '  ' * depth << %(#{clean_req req})
              t << %( depends on) unless tree[-1] == req
              t << %(\n)
              depth += 1
            end
            t
          end.join("\n")

          if conflict.requirement.name == 'bundler'
            o << %(\n  Current Bundler version:\n    bundler (#{Bundler::VERSION}))
            other_bundler_required = !conflict.requirement.requirement.satisfied_by?(Gem::Version.new Bundler::VERSION)
          end

          if conflict.requirement.name == "bundler" && other_bundler_required
            o << "\n"
            o << "This Gemfile requires a different version of Bundler.\n"
            o << "Perhaps you need to update Bundler by running `gem install bundler`?\n"
          end
          if conflict.locked_requirement
            o << "\n"
            o << %(Running `bundle update` will rebuild your snapshot from scratch, using only\n)
            o << %(the gems in your Gemfile, which may resolve the conflict.\n)
          elsif !conflict.existing
            if conflict.requirement_trees.first.size > 1
              o << "Could not find gem '#{clean_req(conflict.requirement)}', which is required by "
              o << "gem '#{clean_req(conflict.requirement_trees.first[-2])}', in any of the sources."
            else
              o << "Could not find gem '#{clean_req(conflict.requirement)} in any of the sources\n"
            end
          end
          o
        end
      end
    end

    ALL = Bundler::Dependency::PLATFORM_MAP.values.uniq.freeze

    class SpecGroup < Array
      include GemHelpers

      attr_reader :activated, :required_by

      def initialize(a)
        super
        @required_by  = []
        @activated    = []
        @dependencies = nil
        @specs        = {}

        ALL.each do |p|
          @specs[p] = reverse.find { |s| s.match_platform(p) }
        end
      end

      def initialize_copy(o)
        super
        @required_by = o.required_by.dup
        @activated   = o.activated.dup
      end

      def to_specs
        specs = {}

        @activated.each do |p|
          if s = @specs[p]
            platform = generic(Gem::Platform.new(s.platform))
            next if specs[platform]

            lazy_spec = LazySpecification.new(name, version, platform, source)
            lazy_spec.dependencies.replace s.dependencies
            specs[platform] = lazy_spec
          end
        end
        specs.values
      end

      def activate_platform(platform)
        unless @activated.include?(platform)
          if for?(platform)
            @activated << platform
            return __dependencies[platform] || []
          end
        end
        []
      end

      def name
        @name ||= first.name
      end

      def version
        @version ||= first.version
      end

      def source
        @source ||= first.source
      end

      def for?(platform)
        @specs[platform]
      end

      def to_s
        "#{name} (#{version})"
      end

      def dependencies_for_activated_platforms
        @activated.map { |p| __dependencies[p] }.flatten
      end

      def platforms_for_dependency_named(dependency)
        __dependencies.select { |p, deps| deps.map(&:name).include? dependency }.keys
      end

    private

      def __dependencies
        @dependencies ||= begin
          dependencies = {}
          ALL.each do |p|
            if spec = @specs[p]
              dependencies[p] = []
              spec.dependencies.each do |dep|
                next if dep.type == :development
                dependencies[p] << DepProxy.new(dep, p)
              end
            end
          end
          dependencies
        end
      end
    end

    # Figures out the best possible configuration of gems that satisfies
    # the list of passed dependencies and any child dependencies without
    # causing any gem activation errors.
    #
    # ==== Parameters
    # *dependencies<Gem::Dependency>:: The list of dependencies to resolve
    #
    # ==== Returns
    # <GemBundle>,nil:: If the list of dependencies can be resolved, a
    #   collection of gemspecs is returned. Otherwise, nil is returned.
    def self.resolve(requirements, index, source_requirements = {}, base = [])
      base = SpecSet.new(base) unless base.is_a?(SpecSet)
      resolver = new(index, source_requirements, base)
      result = resolver.start(requirements)
      SpecSet.new(result)
    end


    def initialize(index, source_requirements, base)
      @index = index
      @source_requirements = source_requirements
      @base = base
      @resolver = Molinillo::Resolver.new(self, self)
      @search_for = {}
      @prereleases_cache = Hash.new { |h,k| h[k] = k.prerelease? }
      @base_dg = Molinillo::DependencyGraph.new
      @base.each { |ls| @base_dg.add_root_vertex ls.name, Dependency.new(ls.name, ls.version) }
    end

    def start(requirements)
      verify_gemfile_dependencies_are_found!(requirements)
      dg = @resolver.resolve(requirements, @base_dg)
      dg.map(&:payload).map(&:to_specs).flatten
    rescue Molinillo::VersionConflict => e
      raise VersionConflict.new(e.conflicts.keys.uniq, e.message)
    rescue Molinillo::CircularDependencyError => e
      names = e.dependencies.sort_by(&:name).map { |d| "gem '#{d.name}'"}
      raise CyclicDependencyError, "Your Gemfile requires gems that depend" \
        " on each other, creating an infinite loop. Please remove" \
        " #{names.count > 1 ? 'either ' : '' }#{names.join(' or ')}" \
        " and try again."
    end

    include Molinillo::UI

    # Conveys debug information to the user.
    #
    # @param [Integer] depth the current depth of the resolution process.
    # @return [void]
    def debug(depth = 0)
      if debug?
        debug_info = yield
        debug_info = debug_info.inspect unless debug_info.is_a?(String)
        STDERR.puts debug_info.split("\n").map { |s| '  ' * depth + s }
      end
    end

    def debug?
      ENV['DEBUG_RESOLVER'] || ENV['DEBUG_RESOLVER_TREE']
    end

    def before_resolution
      Bundler.ui.info 'Resolving dependencies...', false
    end

    def after_resolution
      Bundler.ui.info ''
    end

    def indicate_progress
      Bundler.ui.info '.', false
    end

    private

    include Molinillo::SpecificationProvider

    def dependencies_for(specification)
      specification.dependencies_for_activated_platforms
    end

    def search_for(dependency)
      platform = dependency.__platform
      dependency = dependency.dep unless dependency.is_a? Gem::Dependency
      search = @search_for[dependency] ||= begin
        index = @source_requirements[dependency.name] || @index
        results = index.search(dependency, @base[dependency.name])
        if vertex = @base_dg.vertex_named(dependency.name)
          locked_requirement = vertex.payload.requirement
        end
        if results.any?
          version = results.first.version
          nested  = [[]]
          results.each do |spec|
            if spec.version != version
              nested << []
              version = spec.version
            end
            nested.last << spec
          end
          groups = nested.map { |a| SpecGroup.new(a) }
          !locked_requirement ? groups : groups.select { |sg| locked_requirement.satisfied_by? sg.version }
        else
          []
        end
      end
      search.select { |sg| sg.for?(platform) }.each { |sg| sg.activate_platform(platform) }
    end

    def name_for(dependency)
      dependency.name
    end

    def name_for_explicit_dependency_source
      'Gemfile'
    end

    def name_for_locking_dependency_source
      'Gemfile.lock'
    end

    def requirement_satisfied_by?(requirement, activated, spec)
      requirement.matches_spec?(spec)
    end

    def sort_dependencies(dependencies, activated, conflicts)
      dependencies.sort_by do |dependency|
        name = name_for(dependency)
        [
          activated.vertex_named(name).payload ? 0 : 1,
          @prereleases_cache[dependency.requirement] ? 0 : 1,
          conflicts[name] ? 0 : 1,
          activated.vertex_named(name).payload ? 0 : search_for(dependency).count,
        ]
      end
    end

    def verify_gemfile_dependencies_are_found!(requirements)
      requirements.each do |requirement|
        next if requirement.name == 'bundler'
        if search_for(requirement).empty?
          if base = @base[requirement.name] and !base.empty?
            version = base.first.version
            message = "You have requested:\n" \
              "  #{requirement.name} #{requirement.requirement}\n\n" \
              "The bundle currently has #{requirement.name} locked at #{version}.\n" \
              "Try running `bundle update #{requirement.name}`"
          elsif requirement.source
            name = requirement.name
            versions = @source_requirements[name][name].map { |s| s.version }
            message  = "Could not find gem '#{requirement}' in #{requirement.source}.\n"
            if versions.any?
              message << "Source contains '#{name}' at: #{versions.join(', ')}"
            else
              message << "Source does not contain any versions of '#{requirement}'"
            end
          else
            message = "Could not find gem '#{requirement}' in any of the gem sources listed in your Gemfile or installed on this machine."
          end
          raise GemNotFound, message
        end
      end
    end

  end
end