Research : Dependency Resolution algorithm - PubGrub

[vincentparrett]

The currently implemented dependency resolution algorithm works well in small graphs, but will most likely cause performance issues with larger/deeper graphs, or where there are larger numbers of package versions.

The algorithm in Dart's package manager Pub uses a relatively new algorithm called PubGrub, which provides much better resolution performance. It also provides much better error reporting, explaining resolution failures in plain language that is easy to understand.

https://medium.com/@nex3/pubgrub-2fb6470504f

https://github.com/dart-lang/pub/blob/master/doc/solver.md

Other implementations (not all are complete/working)

Ruby - https://github.com/jhawthorn/pub_grub
Ruby - https://github.com/Richard-Degenne/pub-grub-poc
Elm - https://github.com/mpizenberg/elm-pubgrub
Rust - https://github.com/pubgrub-rs/pubgrub
Rust - https://github.com/elba/elba/tree/master/src/lib/resolve
C++ - https://github.com/vector-of-bool/pubgrub

I would love to see a delphi implementation of this algorithm.