Package resolution algorithm


Paket uses the paket.dependencies file to specify project dependencies. Usually only direct dependencies are specified and often a broad range of package versions is allowed. During paket install Paket needs to figure out concrete versions of the specified packages and their transitive dependencies. These versions are then persisted to the paket.lock file.

In order to figure out the concrete versions Paket needs to solve the following constraint satisfaction problem:

  • Select the latest version for each of the packages in the paket.dependencies file, plus all their transitive dependencies, such that all version constraints are satisfied.
  • In general, more than one solution to this problem can exist and the solver will take the first solution that it finds.
  • If you change the resolution strategy then Paket needs to find the oldest matching version.

Getting data

The constraint satisfaction problem is covered by many scientific papers, but a big challenge for Paket's resolver is that it doesn't have the full constraints available. The algorithm needs to evaluate the package dependency graph along the way by retrieving data from the NuGet source feeds.

The two important API questions are:

  • What versions of a package are available?
  • Given a concrete version of a package, what further dependencies are required?

Answering these questions is a very expensive operation since it involves a HTTP request and therefore the resolver has to minimize these requests and only access the API when really needed.

Basic algorithm

Starting from the paket.dependencies file we have a set of package requirements. Every requirement specifies a version range and a resolver strategy for a package:

type PackageRequirementSource =
| DependenciesFile of string
| Package of PackageName * SemVerInfo 

type ResolverStrategy = Max | Min

type PackageRequirement =
    { Name : PackageName
      VersionRequirement : VersionRequirement
      ResolverStrategy : ResolverStrategy
      Parent: PackageRequirementSource
      Sources : PackageSource list }

The algorithm works as a Breadth-first search. In every step it selects a requirement from the set of open requirements and checks if the requirement can be satisfied. If no conflict arises then a package version gets selected and all it's dependencies are added to the open requirements. A set of closed requirements is maintained in order to prevent cycles in the search graph.

If the selected requirement results in a conflict then the algorithm backtracks in the search tree and selects the next version.

let rec step(selectedPackageVersions:Set<ResolvedPackage>,
             openRequirements:Set<PackageRequirement>) =

    match selectNextRequirement openRequirements with
    | Some(currentRequirement,stillOpen) ->
        let availableVersions =
            match getSelectedPackageVersion currentRequirement.Name selectedPackageVersions with
            | Some version ->
                // we already selected a version so we can't pick a different
            | None ->
                // we didn't select a version yet so all versions are possible
                getAllVersionsFromNuget currentRequirement.Name

        let compatibleVersions =
            // consider only versions, which match the current requirement
            |> List.filter (isInRange currentRequirement.VersionRequirement)

        let sortedVersions =
            match currentRequirement.ResolverStrategy with
            | ResolverStrategy.Max -> List.sort compatibleVersions |> List.rev
            | ResolverStrategy.Min -> List.sort compatibleVersions
        let mutable conflictState = Resolution.Conflict(stillOpen)

        for versionToExplore in sortedVersions do
            match conflictState with
            | Resolution.Conflict _ ->
                let packageDetails = getPackageDetails(currentRequirement.Name,versionToExplore)
                conflictState <- 
                    step(Set.add packageDetails selectedPackageVersions,
                         Set.add currentRequirement closedRequirements,
            | Resolution.Ok _ -> ()

    | None ->
        // we are done - return the selected versions

Sorting package requirements

In order to make progress in the search tree the algorithm needs to determine the next package. Paket uses a heuristic, which tries to process packages with small version ranges and high conflict potential first. Therefore, it orders the requirements based on:

Package conflict boost

Whenever Paket encounters a package version conflict in the search tree it increases a boost factor for the involved packages. This heuristic influences the package evaluation order and forces the resolver to deal with conflicts much earlier in the search tree.

Branch and bound

Every known resolution conflict is stored in a HashSet. At every step Paket will always check if the current requirement set (union of open requirements and closed requirements) is a superset of a known conflict. In this case Paket can stop evaluating that part of the search tree.

Caching and lazy evaluation

Since HTTP requests to NuGet are very expensive Paket tries to reduce these calls as much as possible:

  • The function getAllVersionsFromNuget will call the NuGet API at most once per package and Paket run.
  • The function getPackageDetails will only call the NuGet API if package details are not found in the RAM or on disk.

The second caching improvement means that subsequent runs of paket update can get faster since package details are already stored on disk.

Error reporting

If the resolver can't find a valid resolution, then it needs to report an error to the user. Since the search tree can be very large and might contain lots of different kinds of failures, reporting a good error message is difficult. Paket will only report the last conflict that it can't resolve and also some information about the origin of this conflict.

If you need more information you can try the verbose mode by using the -v parameter.

Further reading

Multiple items
val string : value:'T -> string

Full name: Microsoft.FSharp.Core.Operators.string

type string = System.String

Full name: Microsoft.FSharp.Core.string
type PackageName = string

Full name: Resolver.PackageName
type SemVerInfo = string

Full name: Resolver.SemVerInfo
type FrameworkRestrictions = FrameworkRestriction list

Full name: Resolver.FrameworkRestrictions
type FrameworkRestriction = string

Full name: Resolver.FrameworkRestriction
type 'T list = List<'T>

Full name: Microsoft.FSharp.Collections.list<_>
type VersionRequirement = string

Full name: Resolver.VersionRequirement
type PackageSource = string

Full name: Resolver.PackageSource
type ResolvedPackage = PackageName * SemVerInfo

Full name: Resolver.ResolvedPackage
type PackageRequirementSource =
  | DependenciesFile of string
  | Package of PackageName * SemVerInfo

Full name: Resolver.PackageRequirementSource
union case PackageRequirementSource.DependenciesFile: string -> PackageRequirementSource
union case PackageRequirementSource.Package: PackageName * SemVerInfo -> PackageRequirementSource
type ResolverStrategy =
  | Max
  | Min

Full name: Resolver.ResolverStrategy
union case ResolverStrategy.Max: ResolverStrategy
union case ResolverStrategy.Min: ResolverStrategy
type PackageRequirement =
  {Name: PackageName;
   VersionRequirement: VersionRequirement;
   ResolverStrategy: ResolverStrategy;
   Parent: PackageRequirementSource;
   Sources: PackageSource list;}

Full name: Resolver.PackageRequirement
PackageRequirement.Name: PackageName
Multiple items
PackageRequirement.VersionRequirement: VersionRequirement

type VersionRequirement = string

Full name: Resolver.VersionRequirement
Multiple items
PackageRequirement.ResolverStrategy: ResolverStrategy

type ResolverStrategy =
  | Max
  | Min

Full name: Resolver.ResolverStrategy
PackageRequirement.Parent: PackageRequirementSource
PackageRequirement.Sources: PackageSource list
val selectNextRequirement : xs:Set<PackageRequirement> -> (PackageRequirement * Set<PackageRequirement>) option

Full name: Resolver.selectNextRequirement

 Orders the requirement set with a heuristic and selects the next requirement
val xs : Set<PackageRequirement>
Multiple items
module Set

from Microsoft.FSharp.Collections

type Set<'T (requires comparison)> =
  interface IComparable
  interface IEnumerable
  interface IEnumerable<'T>
  interface ICollection<'T>
  new : elements:seq<'T> -> Set<'T>
  member Add : value:'T -> Set<'T>
  member Contains : value:'T -> bool
  override Equals : obj -> bool
  member IsProperSubsetOf : otherSet:Set<'T> -> bool
  member IsProperSupersetOf : otherSet:Set<'T> -> bool

Full name: Microsoft.FSharp.Collections.Set<_>

new : elements:seq<'T> -> Set<'T>
union case Option.Some: Value: 'T -> Option<'T>
module Seq

from Microsoft.FSharp.Collections
val head : source:seq<'T> -> 'T

Full name: Microsoft.FSharp.Collections.Seq.head
val getAllVersionsFromNuget : x:PackageName -> SemVerInfo list

Full name: Resolver.getAllVersionsFromNuget

 Calls the NuGet API and retrieves all versions for a package
val x : PackageName
val isInRange : vr:VersionRequirement -> v:SemVerInfo -> bool

Full name: Resolver.isInRange

 Checks if the given version is in the specified version range
val vr : VersionRequirement
val v : SemVerInfo
type bool = System.Boolean

Full name: Microsoft.FSharp.Core.bool
val getPackageDetails : name:PackageName * version:SemVerInfo -> ResolvedPackage

Full name: Resolver.getPackageDetails
val name : PackageName
val version : SemVerInfo
module Unchecked

from Microsoft.FSharp.Core.Operators
val defaultof<'T> : 'T

Full name: Microsoft.FSharp.Core.Operators.Unchecked.defaultof
val getSelectedPackageVersion : name:PackageName -> selectedPackageVersions:Set<ResolvedPackage> -> SemVerInfo option

Full name: Resolver.getSelectedPackageVersion

 Looks into the cache if the algorithm already selected that package
val selectedPackageVersions : Set<ResolvedPackage>
type 'T option = Option<'T>

Full name: Microsoft.FSharp.Core.option<_>
union case Option.None: Option<'T>
val addDependenciesToOpenSet : packageDetails:ResolvedPackage * closed:Set<PackageRequirement> * stillOpen:Set<PackageRequirement> -> Set<PackageRequirement>

Full name: Resolver.addDependenciesToOpenSet

 Puts all dependencies of the package into the open set
val packageDetails : ResolvedPackage
val closed : Set<PackageRequirement>
val stillOpen : Set<PackageRequirement>
val empty<'T (requires comparison)> : Set<'T> (requires comparison)

Full name: Microsoft.FSharp.Collections.Set.empty
type Resolution =
  | Ok of Set<ResolvedPackage>
  | Conflict of Set<PackageRequirement>

Full name: Resolver.Resolution
union case Resolution.Ok: Set<ResolvedPackage> -> Resolution
union case Resolution.Conflict: Set<PackageRequirement> -> Resolution
val step : selectedPackageVersions:Set<ResolvedPackage> * closedRequirements:Set<PackageRequirement> * openRequirements:Set<PackageRequirement> -> Resolution

Full name: Resolver.step
val closedRequirements : Set<PackageRequirement>
val openRequirements : Set<PackageRequirement>
val currentRequirement : PackageRequirement
val availableVersions : SemVerInfo list
val compatibleVersions : SemVerInfo list
Multiple items
module List

from Microsoft.FSharp.Collections

type List<'T> =
  | ( [] )
  | ( :: ) of Head: 'T * Tail: 'T list
  interface IEnumerable
  interface IEnumerable<'T>
  member GetSlice : startIndex:int option * endIndex:int option -> 'T list
  member Head : 'T
  member IsEmpty : bool
  member Item : index:int -> 'T with get
  member Length : int
  member Tail : 'T list
  static member Cons : head:'T * tail:'T list -> 'T list
  static member Empty : 'T list

Full name: Microsoft.FSharp.Collections.List<_>
val filter : predicate:('T -> bool) -> list:'T list -> 'T list

Full name: Microsoft.FSharp.Collections.List.filter
PackageRequirement.VersionRequirement: VersionRequirement
val sortedVersions : SemVerInfo list
PackageRequirement.ResolverStrategy: ResolverStrategy
val sort : list:'T list -> 'T list (requires comparison)

Full name: Microsoft.FSharp.Collections.List.sort
val rev : list:'T list -> 'T list

Full name: Microsoft.FSharp.Collections.List.rev
val mutable conflictState : Resolution
val versionToExplore : SemVerInfo
val add : value:'T -> set:Set<'T> -> Set<'T> (requires comparison)

Full name: Microsoft.FSharp.Collections.Set.add
Fork me on GitHub