Thoth’s resolver

As Python is a dynamic programming language, the actual resolution of Python software stacks might take some time (you’ve probably encountered this already). One of the reasons behind it is the fact that all packages need to be downloaded and installed to verify version range satisfaction during the installation. This is also one of the reasons Thoth builds its knowledge base - Thoth pre-computes dependencies in the Python ecosystem so that resolving can be done offline without interacting with the outside world.

Thoth’s resolver performs steps (corresponding to actions in a Markov Decision Process) to resolve final states out of initial states by running pipeline sieves and steps. Internally, there are computed all the combinations that can occur and there are produced new states that are added to a pool of states, called beam. Resolver tightly cooperates with predictor that guides resolver to resolve desired software stacks.

Resolver and predictor in action.

Thoth’s resolver respects Python ecosystem to resolve software stacks as done by pip or Pipenv. This is achieved in a different way to also include observations about Python packages from Thoth’s knowledge base. Instead of implementing 3SAT or backtracking algorithm the resolver operates directly on dependency graphs that are lazily expanded by expanding not-yet resolved dependencies in resolver states. The whole resolution is treated as a Markov Decision Process (MDP) and the expansion of dependencies is seen as a step in the MDP. See Introduction section on more info and intuition behind MDP in the resolver implementation.

Dependencies of not-yet resolved packages (unresolved dependencies) are resolved based on pre-computed dependency information stored in the Thoth’s knowledge base. This information is aggregated by Thoth’s solvers that are run for different software environments. An example can be a solver for Fedora:33 running Python3.9 or UBI:8 running Python3.8. These software environments can be then used as base software environments for running Python applications (container images, also suitable as base for OpenShift’s s2i build process - see s2i base images provided by Thoth that are analyzed by Thoth itself and Thoth has information to drive recommendations for these container images used in an s2i build).

The resolver has two main purposes:

  • resolve software stacks for Dependency Monkey runs and verify generated software stacks on Amun

  • resolve software stacks for recommendations

To instantiate a resolver, one can use two main functions:

To resolve raw pipeline products, one can use Resolver.resolve_products method that yields raw products during a pipeline run. Another method, Resolver.resolve creates a complete report of an adviser run together with some additional pipeline run information. See pipeline section for code examples.


Pipeline unit methods Unit.post_run_report and predictor’s Predictor.post_run_report are called only when Resolver.resolve method is used to resolve software stacks.

Resolver instance transparently runs stack resolution pipeline to produce scored software stacks.

During the whole run, resolver keeps context that is updated during runs and is accessible in pipeline units as well as passed to predictor’s run method to guide resolver in next states to be resolve.