[][src]Module rustc_data_structures::obligation_forest

The ObligationForest is a utility data structure used in trait matching to track the set of outstanding obligations (those not yet resolved to success or error). It also tracks the "backtrace" of each pending obligation (why we are trying to figure this out in the first place).

External view

ObligationForest supports two main public operations (there are a few others not discussed here):

  1. Add a new root obligations (register_obligation).
  2. Process the pending obligations (process_obligations).

When a new obligation N is added, it becomes the root of an obligation tree. This tree can also carry some per-tree state T, which is given at the same time. This tree is a singleton to start, so N is both the root and the only leaf. Each time the process_obligations method is called, it will invoke its callback with every pending obligation (so that will include N, the first time). The callback also receives a (mutable) reference to the per-tree state T. The callback should process the obligation O that it is given and return a ProcessResult:

When the call to process_obligations completes, you get back an Outcome, which includes three bits of information:

Implementation details

For the most part, comments specific to the implementation are in the code. This file only contains a very high-level overview. Basically, the forest is stored in a vector. Each element of the vector is a node in some tree. Each node in the vector has the index of its dependents, including the first dependent which is known as the parent. It also has a current state, described by NodeState. After each processing step, we compress the vector to remove completed and error nodes, which aren't needed anymore.

Modules

graphviz

Structs

Error
GetObligation
Node
ObligationForest
ObligationTreeId
Outcome

Enums

DoCompleted

Should process_obligations compute the Outcome::completed field of its result?

NodeState

The state of one node in some tree within the forest. This represents the current state of processing for the obligation (of type O) associated with this node.

ProcessResult

The result type used by process_obligation.

Traits

ForestObligation
ObligationProcessor

Type Definitions

ObligationTreeIdGenerator