PubGrub

PubGrub version solving algorithm.

It consists in efficiently finding a set of packages and versions that satisfy all the constraints of a given project dependencies. In addition, when that is not possible, PubGrub tries to provide a very human-readable and clear explaination as to why that failed. Below is an example of explanation present in the introductory blog post about PubGrub (elm-pubgrub is almost there ^^).

Because dropdown >=2.0.0 depends on icons >=2.0.0 and
  root depends on icons <2.0.0, dropdown >=2.0.0 is forbidden.

And because menu >=1.1.0 depends on dropdown >=2.0.0,
  menu >=1.1.0 is forbidden.

And because menu <1.1.0 depends on dropdown >=1.0.0 <2.0.0
  which depends on intl <4.0.0, every version of menu
  requires intl <4.0.0.

So, because root depends on both menu >=1.0.0 and intl >=5.0.0,
  version solving failed.

The algorithm is generic and works for any type of dependency system with the following caracteristics, not only Elm packages.

  • Versions use the semantic versioning scheme (Major.Minor.Patch).
  • Packages cannot be simultaneously present at two different versions.
  • Dependencies are expressed in one of the following forms
    • exact version (foo 1.0.0 depends bar 1.0.0)
    • higher or equal version (foo 1.0.0 depends on bar >= 1.0.0)
    • stricly lower version (foo 1.0.0 depends on bar < 2.0.0)
    • ranges of versions (foo 1.0.0 depends on bar 1.0.0 <= v < 2.0.0)

API

The algorithm is provided in two forms, synchronous and asynchronous. The synchronous API is quite straightforward. The async one uses the Effect pattern to be easily integrated into the TEA architecture.

Direct sync call

PubGrub.solve config package version

Where config provides the list of available packages and versions, as well as the dependencies of every available package. The call to PubGrub.solve for a given package at a given version will compute the set of packages and versions needed.

Async API

Sometimes, it is too expensive to provide upfront the list of all packages and versions, as well as all dependencies for every one of those. This may very well require some network or other async requests. For this reason, it is possible to run the PubGrub algorithm step by step. Every time an effect may be required, it stops and informs the caller, which may resume the algorithm once necessary data is loaded.

PubGrub.update : Cache -> Msg -> State -> ( State, Effect )

The Effect type is public to enable the caller to perform the required task before resuming. The Msg type is also public to drive the algorithm according to what was expected in the last effect when resuming.

At any point between two update calls, the caller can update the Cache of already loaded data.

The algorithm informs the caller that all is done when the SignalEnd result effect is emitted.

Common to sync and async

type alias Solution =
List ( String, Version )

Solution of the algorithm containing the list of required packages with their version number.

Sync

type alias PackagesConfig =
{ listAvailableVersions : String -> List Version
, getDependencies :
String -> Version -> Maybe (List ( String, Range ))
}

Configuration of available packages to solve dependencies. The strategy of which version should be preferably picked in the list of available versions is implied by the order of the list: first version in the list will be tried first.

solve : PackagesConfig -> String -> Version -> Result String Solution

PubGrub version solving algorithm.

packagesConfigFromCache : Cache -> PackagesConfig

Convenient conversion of a cache into available packages configuration. This is basically:

packagesConfigFromCache cache =
    { listAvailableVersions = Cache.listVersions cache
    , getDependencies = Cache.listDependencies cache
    }

Async

type State

Internal state of the PubGrub algorithm.

stateToString : State -> String

Convert a state into a printable string (for human reading).

type Effect
= NoEffect
| ListVersions ( String, Term )
| RetrieveDependencies ( String, Version )
| SignalEnd (Result String Solution)

Those are the effects required by the PubGrub algorithm. Once emitted, they may require you to retrieve some data, and then send the adequate message to the algorithm.

Convert an effect into a printable string (for human reading).

type Msg
= NoMsg
| AvailableVersions String Term (List Version)
| PackageDependencies
String
(Maybe (List ( String, Range )))

Messages used to progress in the algorithm.

You should pick the one you need depending on the last effect emitted. For example, the ListVersions effect is asking you to retrieve available versions for a given package. Once done, inform PubGrub with the AvailableVersions message (and pass around the Term value).

init : Cache -> String -> Version -> ( State, Effect )

Initialize PubGrub algorithm.

update : Cache -> Msg -> State -> ( State, Effect )

Update the state of the PubGrub algorithm.

For messages of the AvailableVersions variant, it is the caller responsability to order the versions in the list with preferred versions at the beginning of the list. As such, it is easy to try to pick the newest versions compatible by ordering the versions with a decreasing order. Alternatively, it can also be interesting to find the minimal versions (oldest) in order to verify that the tests pass with those.

elm doc
preview
Open Files
Close Preview
Browse Source
    dmy@2025