PackageManager.scala

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

}