Class: Grimoire::Solver

Inherits:
Utility show all
Includes:
Bogo::Memoization
Defined in:
lib/grimoire/solver.rb

Overview

Requirement solver

Constant Summary collapse

MAX_GENERATION_LOOPS =

Ceiling for number of loops allowed during path generation

100000

Instance Attribute Summary collapse

Instance Method Summary collapse

Methods inherited from Utility

#debug, #to_json

Constructor Details

#initialize(*_) ⇒ Solver

Returns a new instance of Solver.



28
29
30
31
32
33
34
35
36
37
38
39
 
# File 'lib/grimoire/solver.rb', line 28

def initialize(*_)
  super
  @world = System.new
  @new_world = nil
  @log = []
  if(restrictions)
    apply_restrictions!
  end
  build_world(requirements.requirements, world, system)
  @log.clear
  world.scrub!
end

Instance Attribute Details

#new_world ⇒ System, NilClass (readonly)

Returns new system subset when pruning.

Returns:

  • (System, NilClass) —

    new system subset when pruning



26
27
28
 
# File 'lib/grimoire/solver.rb', line 26

def new_world
  @new_world
end

#world ⇒ System (readonly)

Returns subset of full system based on requirements.

Returns:

  • (System) —

    subset of full system based on requirements



24
25
26
 
# File 'lib/grimoire/solver.rb', line 24

def world
  @world
end

Instance Method Details

#apply_restrictions! ⇒ self

Restrictions are simply an implicit expansion of the requirements that. When restrictions are provided, it serves to further restrict the valid units available for solutions

Returns:

  • (self) 


46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
 
# File 'lib/grimoire/solver.rb', line 46

def apply_restrictions!
  restrictions.requirements.each do |rst|
    req = requirements.requirements.detect do |r|
      r.name == rst.name
    end
    if(req)
      new_req = req.merge(rst)
      requirements.requirements.delete(req)
      requirements.requirements.push(new_req)
    else
      requirements.requirements.push(rst)
    end
  end
  self
end

#build_world(deps = nil, my_world = nil, root = nil) ⇒ Object

Build the world required for the solver (the subset of the entire system required by the requirements)

Parameters:

  • deps (DEPENDENCY_CLASS) (defaults to: nil) —

    dependencies required to resolve

  • my_world (System) (defaults to: nil) —

    system to populate with units

  • root (System) (defaults to: nil) —

    superset system to extract units



116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
 
# File 'lib/grimoire/solver.rb', line 116

def build_world(deps=nil, my_world=nil, root = nil)
  deps = requirement.requirements unless deps
  my_world = world unless my_world
  root = system unless root
  deps.each do |dep|
    units = root.subset(dep.name, dep.requirement)
    sha = Digest::SHA256.hexdigest(MultiJson.dump(units))
    if(@log.include?(sha))
      debug "Units checksum already added to world. Skipping. (`#{sha}`)"
      next
    end
    debug "Logging units checksum for world addition. (`#{sha}`)"
    @log.push(sha)
    units.each do |unit|
      build_world(unit.dependencies, my_world, root)
    end
    debug "Units added to world: #{MultiJson.dump(units.map{|u| {u.name => u.version} })}"
    my_world.add_unit(units)
  end
end

#create_queue ⇒ Bogo::PriorityQueue

Returns:

  • (Bogo::PriorityQueue) 


138
139
140
141
142
143
144
 
# File 'lib/grimoire/solver.rb', line 138

def create_queue
  if(score_keeper)
    Bogo::PriorityQueue.new(score_keeper.preferred_score)
  else
    Bogo::PriorityQueue.new
  end
end

#generate! ⇒ Bogo::PriorityQueue<Path>

Generate valid constraint paths

Returns:

  • (Bogo::PriorityQueue<Path>) 


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
 
# File 'lib/grimoire/solver.rb', line 270

def generate!
  if(requirements.requirements.empty?)
    raise ArgumentError.new 'No cookbook constraints provided within Batali file!'
  end
  custom_unit = Unit.new(
    :name => '~_SOLVER_UNIT_~',
    :version => '1.0.0',
    :dependencies => requirements.requirements
  )
  count = 0
  debug "Solver Unit: #{MultiJson.dump(custom_unit)}"
  debug{ "Solver world context of unit system: #{world.inspect}" }
  results = Bogo::PriorityQueue.new
  begin
    until(count >= result_limit)
      result = resolve(nil, custom_unit)
      results.push(Path.new(:units => result.slice(1, result.size)), count)
      count += 1
    end
  rescue Error::UnitUnavailable => e
    debug "Failed to locate unit: #{e}"
    count = nil
  end
  if(results.empty?)
    raise Error::NoSolution.new("Failed to generate valid path for requirements: `#{custom_unit.dependencies}`")
  else
    results
  end
end

#populate_queue(p_queue, units) ⇒ Bogo::PriorityQueue

Populate queue with units

Parameters:

  • p_queue (Bogo::PriorityQueue)
  • units (Array<Unit>)

Returns:

  • (Bogo::PriorityQueue) 


164
165
166
167
168
169
170
171
 
# File 'lib/grimoire/solver.rb', line 164

def populate_queue(p_queue, units)
  i = 0
  units = units.map do |unit|
    [unit, score_unit(unit, i += 1)]
  end
  p_queue.multi_push(units)
  p_queue
end

#prune_world! ⇒ self

Note:

This must be called explicitly and is provided for resolving an entire system, not a single resolution path

After the world has been generated extraneous units will be included as a result of dependency constraints that may be too loose and are not actually required by any resolution that would be requested. This will run a second pass and remove extraneous items not required.

Returns:

  • (self) 


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
 
# File 'lib/grimoire/solver.rb', line 71

def prune_world!
  @new_world = System.new
  requirements.requirements.each do |req|
    unless(world.units[req.name])
      debug "No units available matching requirement name `#{req.name}`! (#{req.inspect})"
      exception = Error::UnitUnavailable.new "No units available for requirement `#{req.name}`"
      exception.unit_name = req.name
      raise exception
    end
    world.units[req.name].delete_if do |r_unit|
      unless(req.requirement.satisfied_by?(r_unit.version))
        debug "Pruning unit due to root requirement satisfaction failure - #{req.name}: #{req.requirement} not satisfied by #{r_unit.name} @ #{r_unit.version}"
        true
      end
    end
  end
  requirements.requirements.each do |req|
    world.units[req.name].each do |r_unit|
      begin
        req_list = RequirementList.new(
          :name => :world_pruner,
          :requirements => [[r_unit.name, r_unit.version.version]]
        )
        path = Solver.new(
          :requirements => req_list,
          :system => world,
          :score_keeper => score_keeper
        ).generate!.pop
        new_world.add_unit(*path.units)
      rescue Error::NoSolution => e
        debug "Failed to generate valid path for: #{r_unit.name}-#{r_unit.version}"
      end
    end
  end
  @world = new_world
  @new_world = nil
  self
end

#queues ⇒ Smash<{Unit#name:Bogo::PriorityQueue}>

Returns:

  • (Smash<{Unit#name:Bogo::PriorityQueue}>) 


147
148
149
150
151
152
153
154
155
156
157
 
# File 'lib/grimoire/solver.rb', line 147

def queues
  memoize(:queues) do
    Smash[
      world.units.map do |name, items|
        queue = create_queue
        populate_queue(queue, items)
        [name, queue]
      end
    ]
  end
end

#reset_queue(name) ⇒ self

Repopulate the given queue

Parameters:

  • name (String)

Returns:

  • (self) 


190
191
192
193
194
195
196
197
 
# File 'lib/grimoire/solver.rb', line 190

def reset_queue(name)
  queue = populate_queue(
    create_queue,
    world.units.fetch(name, [])
  )
  queues[name] = queue
  self
end

#resolve(dep, given = nil, current = []) ⇒ Array<Unit>

Resolve path for a given dependency

Parameters:

Returns:



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
 
# File 'lib/grimoire/solver.rb', line 227

def resolve(dep, given=nil, current=[])
  unit = given || unit_for(dep)
  if(unit.dependencies.empty?)
    [unit]
  else
    deps = [unit]
    begin
      unit.dependencies.map do |u_dep|
        existing = (current + deps).detect{|d| d.name == u_dep.name}
        if(existing)
          if(u_dep.requirement.satisfied_by?(existing.version))
            next
          else
            deps.delete(existing)
            reset_queue(u_dep.name) unless given
          end
        else
          reset_queue(u_dep.name) unless given
        end
        deps += resolve(u_dep, nil, current + deps)
        deps.compact!
        u_dep
      end.compact.map do |u_dep|  # validator
        existing = deps.detect{|d| d.name == u_dep.name}
        if(existing)
          unless(u_dep.requirement.satisfied_by?(existing.version))
            deps.delete(existing)
            reset_queue(u_dep.name)
            raise Error::ResolutionPathInvalid.new("Unit <#{existing.inspect}> does not satisfy <#{u_dep.inspect}>")
          end
        end
      end
    rescue Error::ResolutionPathInvalid => e
      debug "Resolution path deadend: #{e} (trying new path)"
      retry
    end
    deps.uniq
  end
end

#score_unit(unit, score) ⇒ Numeric

Provide score for given unit

Parameters:

  • unit (Unit)
  • score (Integer) —

    current score

Returns:

  • (Numeric) —

    score



178
179
180
181
182
183
184
 
# File 'lib/grimoire/solver.rb', line 178

def score_unit(unit, score)
  if(score_keeper)
    score_keeper.score_for(unit, score, :solver => self) || score
  else
    score
  end
end

#unit_for(dep) ⇒ Unit

Provide Unit acceptable for given dependency

Parameters:

Returns:



204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
 
# File 'lib/grimoire/solver.rb', line 204

def unit_for(dep)
  unit = nil
  if(queues[dep.name].nil?)
    raise KeyError.new "No valid units for requested name found within system! (`#{dep.name}`)"
  end
  until(unit || queues[dep.name].empty?)
    unit = queues[dep.name].pop
    unit = nil unless dep.requirement.satisfied_by?(unit.version)
  end
  unless(unit)
    error = Error::UnitUnavailable.new("Failed to locate valid unit for: #{dep.inspect}")
    error.unit_name = dep.name
    raise error
  end
  unit
end