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 record all fragments they want to evaluate and only those. Fragments are represented by an integral FragmentId, but 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 specified fragments as the solver explores the dependency graph.

Solver::run and Solver::step will incrementally explore the depedency graph and call Problem::evaluate on fragments that have all of its dependencies met.

In the end, all requested fragments will either have been evaluated or will be proven to be 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 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 is safe but 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.

Build Features

This crate has multiple features. From those, there are three where users must specify exactly one of: futures-lock, tokio-lock, or async-std-lock. Use whichever is most convenient.

std

Use std. Solver::run will be unavailable if std is disabled. TODO: actually make this assertion true.

js-bindings

Build the JavaScript API if building for WASM.

futures-lock

Use the locks implemented by the futures crate.

tokio-lock

Use the locks implemented by the tokio crate.

async-std-lock

Use the locks implemented by the async-lock crate.

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 two 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_evaluated or Solver::clone_with_evaluation_assumptions. This enables a much simpler implementation.