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.



21
22
23
24
25
26
27
28
 
# File 'lib/grimoire/solver.rb', line 21

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

Instance Attribute Details

#world ⇒ System (readonly)

Returns subset of full system based on requirements.

Returns:

  • (System) —

    subset of full system based on requirements



19
20
21
 
# File 'lib/grimoire/solver.rb', line 19

def world
  @world
end

Instance Method Details

#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



36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
 
# File 'lib/grimoire/solver.rb', line 36

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

#generate! ⇒ Bogo::PriorityQueue<Path>

Generate valid constraint paths

Returns:

  • (Bogo::PriorityQueue<Path>) 


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

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


75
76
77
78
79
80
81
82
 
# File 'lib/grimoire/solver.rb', line 75

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

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

Returns:

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


58
59
60
61
62
63
64
65
66
67
68
 
# File 'lib/grimoire/solver.rb', line 58

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

#reset_queue(name) ⇒ self

Repopulate the given queue

Parameters:

  • name (String)

Returns:

  • (self) 


101
102
103
104
105
106
107
108
 
# File 'lib/grimoire/solver.rb', line 101

def reset_queue(name)
  queue = populate_queue(
    Bogo::PriorityQueue.new,
    world.units[name]
  )
  queues[name] = queue
  self
end

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

Resolve path for a given dependency

Parameters:

Returns:



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

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



89
90
91
92
93
94
95
 
# File 'lib/grimoire/solver.rb', line 89

def score_unit(unit, score)
  if(score_keeper)
    score_keeper.score_for(unit) || score
  else
    score
  end
end

#unit_for(dep) ⇒ Unit

Provide Unit acceptable for given dependency

Parameters:

Returns:



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

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