Class: Ruber::ComponentManager::DepsSolver

Inherits:

Object

Object
Ruber::ComponentManager::DepsSolver

show all

Defined in:

lib/ruber/component_manager.rb

Overview

Helper class which contains the methods needed to find all the plugins needed to satisfy the dependencies of a given set of plugins.

The difference between this class and PluginSorter is that the latter needs to know all the plugins which should be loaded, while this class has the job of finding out which ones need to be loaded.

Instance Method Summary (collapse)

- (DepsSolver) initialize(to_load, availlable) constructor
Creates a new DepsSolver.
- (Object) remove_unneeded_deps private
Attempts to remove from the list of needed dependencies all those dependencies.
- (Object) solve
Tries to resolve the dependencies for the given plugins, returning an array.
- (Object) solve_for(pl, errors, stack) private
Recursively finds all the dependencies for the plugin described by the PluginSpecification.

Constructor Details

- (DepsSolver) initialize(to_load, availlable)

Creates a new DepsSolver.

to_load is an array containing the PluginSpecification corresponding describing the plugins to load, while availlable is an array containing the PluginSpecification which can be used to resolve dependencies.

# File 'lib/ruber/component_manager.rb', line 201

def initialize to_load, availlable
  @to_load = to_load.map{|i| [i.name, i]}.to_h
  @availlable = availlable.map{|i| [i.name, i]}.to_h
  @loaded_features = to_load.inject({}) do |res, i|
    i.features.each{|f| (res[f] ||= []) << i}
    res
  end
  @availlable_plugins = availlable.map{|i| [i.name, i]}.to_h
  @availlable_features = availlable.inject({}) do |res, i|
    i.features.each{|f| (res[f] ||= []) << i}
    res
  end
  # @res is an array containing the result, that is the list of names of
  # the plugins to load to satisfy all dependencies.
  # @deps is a hash containing the reasons for which a given plugin should
  # be loaded. Each key is the name of a plugin, while each value is an array
  # containing the list of plugins directly depending on the key. If the key
  # is in the list of plugins to load (that is in the first argument passed
  # to the constructor), the array contains nil.
  @res = []
  @deps = Hash.new{|h, k| h[k] = []}
end

Instance Method Details

- (Object) remove_unneeded_deps (private)

Attempts to remove from the list of needed dependencies all those dependencies which are there only to provide features already provided by other plugins.

For example, if the list of needed plugins includes both the plugin :a and the plugin :b, which provides the feature :a, then the plugin :a whould be removed from the list. If after removing plugins as described above, the list contains plugins which aren’t needed anymore, because they were there only to satisfy the dependencies of plugins which have already been removed, they’re also removed.

# File 'lib/ruber/component_manager.rb', line 305

def remove_unneeded_deps
  h = Hash.new{|hash, k| hash[k] = []}
  #A hash having the features as keys and the plugins providing them
  #as values
  deps_features = @res.inject(h) do |res, i|
    @availlable_plugins[i].features.each{|f| res[f] << i}
    res
  end
  to_delete = @res.find{|i| !@deps[i].include?(nil) and !deps_features[i].uniq.only? i}
  until to_delete.nil?
    @res.delete to_delete
    deps_features.each_value{|i| i.delete to_delete}
    new = deps_features[to_delete]
    @deps[new] += @deps[to_delete]
    @deps.delete to_delete
    @deps.each_value{|i| i.delete to_delete}
    to_delete = @res.find{|i| !@deps.include?(nil) and !deps_features[i].only? i}
    to_delete = @deps.find{|k, v| v.empty?}[0] rescue nil unless to_delete
  end
end

- (Object) solve

Tries to resolve the dependencies for the given plugins, returning an array containing the plugins needed to satisfy all the dependencies. When a plugin depends on a feature f, then f is included in the list of needed plugins, together with its dependencies, unless another required plugin already provides that feature.

If some dependencies can’t be satisfied, UnresolvedDep is raised. If there are circular dependencies, CircularDep is raised.

# File 'lib/ruber/component_manager.rb', line 234

def solve
  errors = {:missing => {}, :circular => []}
  @res = @to_load.values.inject([]) do |r, i| 
    @deps[i.name] << nil
    r + solve_for(i, errors, [])
  end
  if !errors[:missing].empty? then raise UnresolvedDep.new errors[:missing]
  elsif !errors[:circular].empty? then raise CircularDep.new errors[:circular]
  end
  remove_unneeded_deps
  @res
end

- (Object) solve_for(pl, errors, stack) (private)

Recursively finds all the dependencies for the plugin described by the PluginSpecification pl.

errors is a hash used to store missing dependencies and circular dependencies. It should have a :circular and a :missing key. The corresponding values should be an array and a hash. stack is an array containing the names of the plugins whose dependencies are being solved and is used to detect circular dependencies. For example, if stack is: [:a, :b, :c], it would mean that we’re resolving the dependencies of the plugin :c, which is a dependency of the plugin :b, which is a dependency of the plugin :a. If this array contains pl.name, then there’s a circular dependency. Note: this method doesn’t raise exceptions if there are circular or missing dependencies. Rather, it adds them to errors and goes on (this means that it skips both missing and circular dependencies).

# File 'lib/ruber/component_manager.rb', line 268

def solve_for pl, errors, stack
  deps = []
  if stack.include? pl.name
    errors[:circular] << [stack.at(stack.index(pl.name + 1)), pl.name]
    return deps
  end
  stack << pl.name
  unless pl.deps.empty?
    pl.deps.each do |dep|
      next if @loaded_features.include? dep
      new_pl = @availlable_plugins[dep]
      if new_pl
        deps << dep
        @deps[dep] << pl.name
        deps += solve_for new_pl, errors, stack
      else
        (errors[:missing][dep] ||= []) << pl.name
        return []
      end
    end
  end
  stack.pop
  deps
end