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



102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
 
# File 'lib/grimoire/solver.rb', line 102

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) 


124
125
126
127
128
129
130
 
# File 'lib/grimoire/solver.rb', line 124

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>) 


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

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) 


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

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

def prune_world!
  @new_world = System.new
  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}>) 


133
134
135
136
137
138
139
140
141
142
143
 
# File 'lib/grimoire/solver.rb', line 133

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) 


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

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:



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

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



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

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:



190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
 
# File 'lib/grimoire/solver.rb', line 190

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