Module rustc_data_structures::obligation_forest
source · Expand description
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):
- Add a new root obligations (
register_obligation
). - 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
:
Unchanged
-> ambiguous result. Obligation was neither a success nor a failure. It is assumed that further attempts to process the obligation will yield the same result unless something in the surrounding environment changes.Changed(C)
- the obligation was shallowly successful. The vectorC
is a list of subobligations. The meaning of this is thatO
was successful on the assumption that all the obligations inC
are also successful. Therefore,O
is only considered a “true” success ifC
is empty. Otherwise,O
is put into a suspended state and the obligations inC
become the new pending obligations. They will be processed the next time you callprocess_obligations
.Error(E)
-> obligation failed with errorE
. We will collect this error and return it fromprocess_obligations
, along with the “backtrace” of obligations (that is, the list of obligations up to and including the root of the failed obligation). No further obligations from that same tree will be processed, since the tree is now considered to be in error.
When the call to process_obligations
completes, you get back an Outcome
,
which includes two bits of information:
completed
: a list of obligations where processing was fully completed without error (meaning that all transitive subobligations have also been completed). So, for example, if the callback fromprocess_obligations
returnsChanged(C)
for some obligationO
, thenO
will be considered completed right away ifC
is the empty vector. Otherwise it will only be considered completed once all the obligations inC
have been found completed.errors
: a list of errors that occurred and associated backtraces at the time of error, which can be used to give context to the user.
Upon completion, none of the existing obligations were shallowly
successful (that is, no callback returned Changed(_)
). This implies that
all obligations were either errors or returned an ambiguous result.
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
- Node 🔒
Enums
- 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. - The result type used by
process_obligation
.
Traits
- This trait allows us to have two different Outcome types: