Elm-pubgrub: a state of the art dependency solver, in elm

Show and Tell
1

code: https://github.com/mpizenberg/elm-pubgrub
api doc: https://elm-doc-preview.netlify.app/?repo=mpizenberg/elm-pubgrub
demo: https://mpizenberg.github.io/elm-pubgrub/

Hi all,

I’ve been working for quite some time on an Elm implementation of a state of the art dependency solver called PubGrub, and it’s finally at a state where I can share all this with you. The result is the elm-pubgrub package (which is not published yet).

Special thanks to @harrysarson , @avh4 and @malaire who have helped me along the way. I’ve copied the readme below if you want to know more about it.

This package provides an implementation of the PubGrub version solving algorithm in the Elm programming language.

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)

Examples

Two examples are located in the examples/ folder. The conflict_resolution example, is a rather simple usage of the library with a custom dependency system (not Elm packages). You can start it easily with elm-reactor or elm-live.

The second example is an advanced usage of the library API, in order to create a dependency solver for actual Elm packages. You can build it locally with elm-live src/Main.elm -- --output=Main.js or just try it online directly at https://mpizenberg.github.io/elm-pubgrub/.

image
image1027×826

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. The API documentation is available on elm-doc-preview.

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.

PubGrub

PubGrub is a version solving algorithm, written in 2018 by Natalie Weizenbaum for the Dart package manager. It is supposed to be very fast and to explain errors more clearly than the alternatives. An introductory blog post was published on Medium by its author.

The detailed explanation of the algorithm is provided on GitHub. The foundation of the algorithm is based on ASP (Answer Set Programming) and a book called “Answer Set Solving in Practice” by Martin Gebser, Roland Kaminski, Benjamin Kaufmann and Torsten Schaub.

33 Likes
2

Really cool works! Thank you for your effort on that!

1 Like
3

I may add that currently the code base still have 3 instances of Debug.todo and that is the main reason why I did not publish it yet. Those todo are there because of branches that should never happen. It would be awesome to have more usage of the code to confirm that those can be replaced by something publishable. So don’t hesitate to use elm-pubgrub for your project before publication and make sure to report an issue if you find a case triggering those.

$ rg "Debug.todo" src/
src/PubGrub/Internal/PartialSolution.elm
248:            Debug.todo "should always find something"

src/PubGrub/Internal/Incompatibility.elm
417:            Debug.todo "This should not appear in the report tree"

src/PubGrub/Internal/Memory.elm
135:                    Debug.todo "Cannot change a decision already made!"
4

This topic was automatically closed 10 days after the last reply. New replies are no longer allowed.