Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
package at.bhuemer.blog.monad
import scalaz.syntax.plus._
import scalaz.syntax.monad._
import scalaz.{Monad, Functor, MonadPlus}
import scala.collection.immutable.{List, Nil}
object PackageManager {
/**
* Case classes that allow us to represent the different ways one can indicate a dependency version.
*/
trait Version
case class AtLeast(minimum: String) extends Version
case class Between(minimum: String, maximum: String) extends Version
case class Dependency(category: String, name: String, version: Version)
trait Dependencies
case class Single(dependency : Dependency) extends Dependencies
case class AllOf(dependencies : List[Dependencies]) extends Dependencies
case class OneOf(dependencies : List[Dependencies]) extends Dependencies
case class Package(description: String, category: String, name: String, version: String, dependencies: Dependencies)
type System = List[Package]
type Repository = List[Package]
// A set of utility functions that enable me to write Scala code that looks more like Haskell code :)
def pureIf[M[_] : MonadPlus, A](b: Boolean, a : A) : M[A] = if (b) pure(a) else empty
def pure[M[_] : MonadPlus, A](a : A) : M[A] = implicitly[MonadPlus[M]].pure(a)
def empty[M[_] : MonadPlus, A] : M[A] = implicitly[MonadPlus[M]].empty
def guard[M[_] : MonadPlus](b: Boolean) : M[Unit] = pureIf(b, ())
def matchesVersion(version: Version, versionStr: String) : Boolean = version match {
case AtLeast(minimum) => minimum <= versionStr
case Between(minimum, maximum) =>
minimum <= versionStr && versionStr <= maximum
}
/**
* <p>Determines whether or not a given package satisfies a dependency, i.e. whether or not it provides the
* right software in the appropriate version. However, it is not concerned about the packages' dependencies
* in turn (whether there's conflicting dependencies, unresolved ones, etc.). All of that doesn't matter at
* this point.</p>
* @param p the candidate package
* @param d the dependency it has to fulfill
* @return <code>true</code> if it fulfils the dependency; <code>false</code> otherwise
*/
def satisfiesDependency(d: Dependency)(p: Package) : Boolean =
d.category == p.category && d.name == p.name && matchesVersion(d.version, p.version)
def satisfiesDependency(system: System, dependency: Dependency) : Boolean =
system.exists(satisfiesDependency(dependency))
/**
* <p>A conflicting dependency is one where the software being installed is the same (name and category),
* but the versions don't match.<p>
* @param d the dependency we want to check
* @param p the package that this dependency might conflict with
* @return <code>true</code>, if there is a conflict; <code>false</code> otherwise
*/
def conflictsDependency(d: Dependency)(p: Package) : Boolean =
d.category == p.category && d.name == p.name && !matchesVersion(d.version, p.version)
def conflictingDependency(system: System, dependency: Dependency) : Boolean =
system.exists(conflictsDependency(dependency))
/**
* <p>Evaluates the missing dependencies we need to install for the given package.
* @param system current system, i.e. the current set of installed packages
* @param p the package that you want to install
* @tparam M monad type (i.e. either Option or List)
* @return "flattened" dependency structure of the missing dependencies
*/
def missingDependencies[M[_]: MonadPlus](system: System, p: Package) : M[List[Dependency]] =
evaluateDependencies(p.dependencies) map { dependencies =>
// For each list of dependency make sure that we don't include the ones that
// we have installed already (i.e. the system satisfies the dependency already).
// There's no need to install them again.
dependencies.filter((dependency: Dependency) => !satisfiesDependency(system, dependency))
}
/**
* Takes dependency structures such as:
* AllOf [
* Single dep1,
* Single dep2,
* OneOf [
* Single dep3,
* Single dep4
* ]
* ]
* and evaluates the whole thing to return lists of dependencies that satisfy
* the configuration. In this case it would be [ [dep1, dep2, dep3], [dep1,dep2,dep4] ].
* You then need to be able to satisfy one of these lists of dependencies.
*
* @param dependencies dependency configuration that you'd like to "flatten"
* @tparam M monad that you want to use to evaluate them (e.g. Option or List)
* @return "flattened" dependency structure
*/
def evaluateDependencies[M[_]: MonadPlus](dependencies : Dependencies) : M[List[Dependency]] =
dependencies match {
case Single(dependency) => pure(List(dependency))
case OneOf(List()) => empty
case OneOf(d :: ds) =>
evaluateDependencies(d) <+> evaluateDependencies(OneOf(ds))
case AllOf(List()) => pure(List())
case AllOf(d :: ds) => for {
a <- evaluateDependencies(d)
b <- evaluateDependencies(AllOf(ds))
} yield a ++ b
}
/**
* <p>Resolve a package from the given repository that satisfies the given dependency, i.e. if we
* installed that package, we'd be able to satisfy it.</p>
* @param repository repository that contains packages that we can install
* @param dependency dependency that we need to satisfy
* @tparam M monad that you want to use to resolve it (e.g. Option or List)
* @return a package that satisfies the given dependency
*/
def resolve[M[_] : MonadPlus](repository: Repository, dependency: Dependency) : M[Package] =
repository match {
case Nil => empty
case (packageCandidate :: remainingPackages) =>
pureIf(satisfiesDependency(dependency)(packageCandidate), packageCandidate) <+> resolve(remainingPackages, dependency)
}
def installDependencies[M[_] : MonadPlus]
(system: System, repository: Repository, dependencies: List[Dependency]) : M[System] =
dependencies match {
case Nil => pure(system)
case (d :: ds) => for {
systemWithOneDependency <- install(system, repository, d)
systemWithAllDependencies <- installDependencies(systemWithOneDependency, repository, ds)
} yield systemWithAllDependencies
}
/**
* <p>If you've resolved a package already, you can use this method to install it locally. This
* is like running "dpkg -i" on your system. Use this carefully as you can ruin your system by
* installing incorrect packages!</p>
*/
def localInstall[M[_] : MonadPlus](system: System, resolvedPackage: Package) : M[System] =
pure(resolvedPackage :: system)
/**
* <p>Resolves a package from the given repository that fulfills the given dependency and installs it
* and all of its dependency. In the course of doing that, it makes sure that we don't compromise the
* system though (conflicting dependencies, missing dependencies, etc.). Only if we can actually install
* the dependency somehow will this method return a new valid system configuration.</p>
* @return
*/
def install[M[_] : MonadPlus](system : System, repository: Repository, dependency: Dependency) : M[System] = {
if (satisfiesDependency(system, dependency)) return pure(system)
for {
// Make sure that we can install it. If it conflicts with something we have installed already,
// we're not going to uninstall anything automatically. Instead we'll just fail at this point
// to initiate backtracking (monad power to the rescue!)
_ <- guard(!conflictingDependency(system, dependency))
resolvedPackage <- resolve(repository, dependency)
// Install the package at this point already to break circular dependency structures. If we
// can't install one of the dependencies, all of this will be thrown away anyway.
systemWithSoftware <- localInstall(system, resolvedPackage)
// Finally, evaluate the missing dependencies and install them. There might be multiple ways
// one could install missing dependencies, but all of that is being taken care of thanks to
// monads.
dependencies <- missingDependencies(systemWithSoftware, resolvedPackage)
systemWithDependencies <- installDependencies(systemWithSoftware, repository, dependencies)
} yield systemWithDependencies
}
def main(args: Array[String]) {
// Return the empty instance of the monad each time .. as there's no way to install this without anything in the repository.
println(install(List(), List(), Dependency("sys-devel", "gettext", AtLeast("3.0")))(scalaz.std.list.listInstance))
println(install(List(), List(), Dependency("sys-devel", "gettext", AtLeast("3.0")))(scalaz.std.option.optionInstance))
println()
println("Single backtracking evaluation (1): ")
println(install(List(), List(
Package("", "devel", "gcc", "3.0", AllOf(List())),
Package("", "devel", "icc", "4.2", AllOf(List())),
Package("", "utils", "curl", "1.1", OneOf(List(
Single(Dependency("devel", "gcc", AtLeast("2.4"))),
Single(Dependency("devel", "icc", AtLeast("3.6")))
)))), Dependency("utils", "curl", AtLeast("1.0")))(scalaz.std.option.optionInstance))
println()
println("Non-deterministic evaluation (1): ")
println(install(
List(), // Nothing installed yet
List(
Package("", "devel", "gcc", "3.0", AllOf(List())),
Package("", "devel", "icc", "4.2", AllOf(List())),
Package("", "utils", "curl", "1.1", OneOf(List(
Single(Dependency("devel", "gcc", AtLeast("2.4"))),
Single(Dependency("devel", "icc", AtLeast("3.6")))
)))), Dependency("utils", "curl", AtLeast("1.0")))(scalaz.std.list.listInstance))
// This now only includes one possible solution rather than two solutions.
println()
println("Non-deterministic evaluation (2): ")
println(install(
List(), // Nothing installed yet
List( // The repository contains a lot of good stuff though
Package("", "devel", "gcc", "3.0", AllOf(List())),
Package("", "devel", "icc", "4.2", AllOf(List())),
Package("", "utils", "curl", "1.1", OneOf(List(
Single(Dependency("devel", "gcc", AtLeast("3.4"))),
Single(Dependency("devel", "icc", AtLeast("3.6")))
)))),
// This is what we want to install:
Dependency("utils", "curl", AtLeast("1.0")))(scalaz.std.list.listInstance)) // Please give us all of the system configurations!
// println(evaluateDependencies(
// AllOf(List(
// Single(new Dependency("sys-devel", "gettext", AtLeast("3.0"))),
// OneOf(List(
// Single(new Dependency("sys-devel", "gcc", AtLeast("3.0"))),
// Single(new Dependency("sys-devel", "icc", AtLeast("3.0")))
// ))
// ))
// )(scalaz.std.list.listInstance))
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment