Crate gpp_solver[−][src]
Expand description
Generic Push-Pull Solver.
This crate implements a generic solver for anything that can have a clear dependency graph. The implementation is a mix of push (eager) and pull (lazy) architectures with user-driven recursion.
Functionality is centered on the Solver struct. Users records all fragments they want to
evaluate and only those. What is a fragment is arbitrary and the solver does not care. It
may represent a variable, an action, an object, or anything else.
Users must also implement the Problem trait, which defines a dependency graph and an
interface for evaluating fragments that the solver finds are both solvable and required. This
dependency graph does not need to be complete or explicit, as long as implementors can return
the direct dependencies of fragments as the solver explores this graph.
Solver::run and Solver::step will incrementally explore the depedency graph, calling
Problem::evaluate on fragments that have all of its dependencies met.
In the end, all requested fragments will either have been evaluated or some of those will have
been permanently punted (see next paragraph) due to being a part of a dependency cycle. The
user may choose to report cycles as errors, or break them with Solver::assume_evaluated or
[Solver::clone_with_evaluation_assumptions]. See also Solver::status.
Solver::punted_iter will return an iterator yielding all fragments that have been punted
so far. A punted fragment is one that has been considered for evaluation but its dependencies
haven’t been met yet. If the solver is done, punted fragments must be are part of at least one
cycle.
Concurrency
Solver is fully asynchronous but the core algorithm is not parallel at the moment. Running
multiple Solver::step concurrently or calling Solver::run with concurrency > 1 will
not make the solver itself run faster. What this does allow is for multiple
Problem::direct_dependencies and Problem::evaluate calls to run concurrently.
Internals
Solver implements a hybrid push-pull architecture. Fragments are only evaluated if needed
(pull, lazy evaluation), but instead of evaluating dependencies recursively, this process will
only evaluate fragments that already have all of its direct dependencies met. If that’s not
the case, the fragment will be punted: stored away and only considered again if all its
dependencies are met sometime in the future.
On the other hand, if a fragment is successfully evaluated, punted fragments that depend on it will be evaluated eagerly (push) if all other dependencies have also been evaluated.
This architecture has three major advantages:
- It is lazy. Only fragments that are explicitly requested to be evaluated, and the fragments those depend on, will be evaluated. And never more than once.
- There is no need to explicitly detect nor handle cycles, unlike both pure push and pure
pull. Fragments that are part of cycles will naturally be punted and never considered again.
Unless the cycle is explicitly broken with
Solver::assume_evaluatedor [Solver::clone_with_evaluation_assumptions].
Modules
This module contains reexported symbols that are imported from different places depending on how the crate was compiled.
Structs
ID of a fragment.
Hybrid push-pull solver.