A program to resolve dependencies, written in Ruby.
From the command line, pipe the contents of a package listing file to the
executable bin/dagger
script as follows:
$ cat data/sample_input.txt | bin/dagger
# KittenService, Ice, Cyberportal, Leetmeme, CamelCaser, Fraudstream
Input files are expected to be in the following format:
KittenService:
Leetmeme: Cyberportal
Cyberportal: Ice
CamelCaser: KittenService
Fraudstream: Leetmeme
Ice:
A coordinator class that performs dependency resolution via a depth-first search through the dependency graph.
# lib/dagger/dependency_resolver.rb L17-L24 (cc9ca72f)
def gather_dependencies(package, deps = [])
raise Dagger::CyclicDependencyError.new(package, deps) if deps.include?(package)
deps.unshift(package)
return deps if package.dependency.nil?
gather_dependencies(package.dependency, deps)
end
lib/dagger/dependency_resolver.rb#L17-L24 (cc9ca72f)
A model class containing data for a given package and a reference to its dependency, if it exists.
A type method, .build_collection_from_list
, provides a factory method
accepting a list of String
instances and returning a list of Package
instances.
# lib/dagger/package.rb L13-L22 (cc9ca72f)
def self.build_collection_from_list(strings)
list_hash = strings.each_with_object({}) do |entry, memo|
name, dep_name = entry.scan(PACKAGE_ENTRY_FORMAT).flatten
memo[name] = new(name, dep_name)
end
list_hash.values.each do |package|
package.dependency = list_hash[package.dependency_name]
end
end
lib/dagger/package.rb#L13-L22 (cc9ca72f)
Provides an ordered set implementation used to build the package manifest (i.e., the list of packages to be installed, topologically sorted).
# lib/dagger/package_list.rb L12-L21 (cc9ca72f)
def add(packages)
Array(packages).each do |package|
next if package_set.include?(package)
package_set << package
package_list << package
end
self
end
lib/dagger/package_list.rb#L12-L21 (cc9ca72f)
The test suite is written in RSpec. An “RSpec-y” (i.e., DSL-heavy) style is intentionally avoided in favor of a more traditional xUnit four-phase test style.
# spec/dagger/package_list_spec.rb L29-L45 (bc062558)
it "adds entries idempotently" do
list = described_class.new
list.add(1)
list.add(1)
expect(list.to_a).to eq [1]
end
it "maintains insertion order" do
list = described_class.new
list.add([5, 1, 2, 3])
list.add([2, 3, 4])
expect(list.to_a).to eq [5, 1, 2, 3, 4]
end
spec/dagger/package_list_spec.rb#L29-L45 (bc062558)
The coordinator class’s #resolve
method accepts an array of strings, each
with the format PACKAGE: [DEPENDENCY]
.
[
"KittenService: ",
"Leetmeme: Cyberportal",
"Cyberportal: Ice",
"CamelCaser: KittenService",
"Fraudstream: Leetmeme",
"Ice: "
]
"KittenService, Ice, Cyberportal, Leetmeme, CamelCaser, Fraudstream"
Dependency graphs containing cycles will raise a CyclicDependencyError
.
[
"KittenService: ",
"Leetmeme: Cyberportal",
"Cyberportal: Ice",
"CamelCaser: KittenService",
"Fraudstream: ",
"Ice: Leetmeme"
]
Dagger::CyclicDependencyError:
Package 'Leetmeme' has cyclic dependencies: [Ice <Leetmeme>, Cyberportal <Ice>, Leetmeme <Cyberportal>]