Class: Version::Resolver

Inherits:
Object
  • Object
show all
Defined in:
lib/versus/resolver.rb

Overview

Version resolution takes a requirements list and can reduce it to a best fit list.

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(*available) ⇒ Resolver

Initialize new Resolver.

Parameters:

  • available (Array) —

    List of name, version and requirements for each possible library.



14
15
16
17
18
19
20
 
# File 'lib/versus/resolver.rb', line 14

def initialize(*available)
  @libraries = Hash.new{ |h,k| h[k] = {} }

  available.each do |name, version, requirements|
    add(name, version, requirements || {})
  end
end

Instance Attribute Details

#libraries ⇒ Object (readonly)

Map of dependencies by name and version to requirements.



25
26
27
 
# File 'lib/versus/resolver.rb', line 25

def libraries
  @libraries
end

Instance Method Details

#add(name, version, requirements = {}) ⇒ Object

Add available library.

Parameters:

  • name (String) —

    The name of the library.

  • version (String, Version::Number) —

    Version number of library.

  • requirements (Hash) (defaults to: {}) —

    Requirements for the library in the form of ‘name=>version_constraint`.



45
46
47
48
49
50
51
52
53
54
55
 
# File 'lib/versus/resolver.rb', line 45

def add(name, version, requirements={})
  name     = name.to_s
  number   = Number.parse(version)
  requires = {}

  requirements.each do |n,c|
    requires[n.to_s] = Constraint.parse(c)
  end

  @libraries[name][number] = requires
end

#cached(name, number, sheet) ⇒ Object (private) 



164
165
166
167
 
# File 'lib/versus/resolver.rb', line 164

def cached(name, number, sheet)
  @cache[[name, number]] = true
  sheet
end

#possibilities(name, constraint) ⇒ Object

Returns possibilities sorted in descending order.



68
69
70
71
72
73
74
75
76
77
78
79
80
 
# File 'lib/versus/resolver.rb', line 68

def possibilities(name, constraint)
  name       = name.to_s
  constraint = Constraint.parse(constraint)

  list = []
  @libraries[name].each do |version, _|
    if constraint.match?(version)
      list << [name, version]
    end
  end

  list.sort!{ |a,b| b[1] <=> a[1] }
end

#product(*list) ⇒ Object (private) 



195
196
197
198
199
 
# File 'lib/versus/resolver.rb', line 195

def product(*list)
  return [] if list.empty?
  head, *rest = *list
  head.product(*rest)
end

#reduce(*constraints) ⇒ Object (private) 



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
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
 
# File 'lib/versus/resolver.rb', line 304

def reduce(*constraints)
  exact, least, most = nil , nil, nil

  constraints.each do |c|
    case c.op
    when '==', '='
      if exact
        if exact != c.number
          exact, least, most = nil, nil, nil
          break
        end
      else
        exact = c
      end
    when '<'
      if least
        if c.number <= least.number
          least = c
        end
      else
        least = c
      end
    when '>'
      if most
        if c.number >= most.number
          most = c
        end
      else
        most = c
      end
    when '<='
      if least
        if c.number < least.number
          least = c
        end
      else
        least = c
      end
    when '>='
      if most
        if c.number > most.number
          most = c
        end
      else
        most = c
      end
    when '=~', '~>'
      # TODO
    end
  end

  # there be only one!
  return nil if exact && least
  return nil if exact && most
  return nil if least && most

  exact || least || most
end

#requirements(name, number) ⇒ Object

Look-up requirements for a given name and version.



60
61
62
63
 
# File 'lib/versus/resolver.rb', line 60

def requirements(name, number)
  number = Version::Number.parse(number) #unless Version::Number === number
  @libraries[name][number]
end

#resolve(name, number) ⇒ Object

TODO: support resolution of multiple [name, versions] at once.



85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
 
# File 'lib/versus/resolver.rb', line 85

def resolve(name, number)
  name   = name.to_s
  number = Number.parse(number)

  @cache    = {}
  @failures = []

  sheet = {}

  result = resolve_(name, number, sheet)

  #list.each do |name, version|
  #  name   = name.to_s
  #  number = Number.parse(version)
  #
  #  resolve_(name, number, sheet)
  #end
  result ? sheet : nil
end

#resolve_(name, number, sheet = {}) ⇒ Object (private) 



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
 
# File 'lib/versus/resolver.rb', line 127

def resolve_(name, number, sheet={})
  # prevent infinite recursion
  return sheet if @cache[[name,number]]
  @cache[[name,number]] = true

  return false unless settle(name, number, sheet)

  requirements = requirements(name, number)

  # there are no requirements to resolve
  return sheet if requirements.empty?

  # what possibilites exist for resolving all the requirements
  potents = requirements.map do |(n, c)|
              possibilities(n,c)
            end

  # TODO: I think this might be a mistake, if there are no possibilities then is it not
  #       a failed resolution? Consider adding to failures and returning false instead.
  return sheet if potents.empty?

  vectors = product(*potents)

  success = vectors.find do |vector|
              resolve_vector(vector, sheet)
            end

  unless success
    @failures << [name, number] unless @failures.include?([name, number])
  end

  return success
end

#resolve_vector(vector, sheet) ⇒ Object (private) 



172
173
174
175
176
177
178
 
# File 'lib/versus/resolver.rb', line 172

def resolve_vector(vector, sheet)
  vector.each do |(n,v)|
    r = resolve_(n, v, sheet)
    return false unless r
  end
  return sheet
end

#settle(name, number, sheet = {}) ⇒ Object (private) 



183
184
185
186
187
188
189
190
 
# File 'lib/versus/resolver.rb', line 183

def settle(name, number, sheet={})
  if sheet[name]
    return false if sheet[name] != number
  else
    sheet[name] = number
  end
  return true
end

#unresolved ⇒ Hash

Returns a mapping of unresolvable requirements. The key of the Hash is the library that has the requirements and the value of the Hash is an Array of the requirements that could be not be found in the library list.

Returns:

  • (Hash) —

    Unresolved requirements



112
113
114
115
116
117
118
119
120
 
# File 'lib/versus/resolver.rb', line 112

def unresolved
  list = Hash.new{ |h,k| h[k] = [] }
  @failures.each do |name, number|
    requirements(name, number).each do |rname, rnumber|
      list[[name,number]] << [rname, rnumber] if possibilities(rname, rnumber.to_s).empty?
    end
  end
  list
end