src/librustc_data_structures/obligation_forest/README.md

   1 The `ObligationForest` is a utility data structure used in trait
   2 matching to track the set of outstanding obligations (those not yet
   3 resolved to success or error). It also tracks the "backtrace" of each
   4 pending obligation (why we are trying to figure this out in the first
   5 place).
   6
   7 ### External view
   8
   9 `ObligationForest` supports two main public operations (there are a
  10 few others not discussed here):
  11
  12 1. Add a new root obligations (`push_tree`).
  13 2. Process the pending obligations (`process_obligations`).
  14
  15 When a new obligation `N` is added, it becomes the root of an
  16 obligation tree. This tree can also carry some per-tree state `T`,
  17 which is given at the same time. This tree is a singleton to start, so
  18 `N` is both the root and the only leaf. Each time the
  19 `process_obligations` method is called, it will invoke its callback
  20 with every pending obligation (so that will include `N`, the first
  21 time). The callback also receives a (mutable) reference to the
  22 per-tree state `T`. The callback should process the obligation `O`
  23 that it is given and return one of three results:
  24
  25 - `Ok(None)` -> ambiguous result. Obligation was neither a success
  26   nor a failure. It is assumed that further attempts to process the
  27   obligation will yield the same result unless something in the
  28   surrounding environment changes.
  29 - `Ok(Some(C))` - the obligation was *shallowly successful*. The
  30   vector `C` is a list of subobligations. The meaning of this is that
  31   `O` was successful on the assumption that all the obligations in `C`
  32   are also successful. Therefore, `O` is only considered a "true"
  33   success if `C` is empty. Otherwise, `O` is put into a suspended
  34   state and the obligations in `C` become the new pending
  35   obligations. They will be processed the next time you call
  36   `process_obligations`.
  37 - `Err(E)` -> obligation failed with error `E`. We will collect this
  38   error and return it from `process_obligations`, along with the
  39   "backtrace" of obligations (that is, the list of obligations up to
  40   and including the root of the failed obligation). No further
  41   obligations from that same tree will be processed, since the tree is
  42   now considered to be in error.
  43
  44 When the call to `process_obligations` completes, you get back an `Outcome`,
  45 which includes three bits of information:
  46
  47 - `completed`: a list of obligations where processing was fully
  48   completed without error (meaning that all transitive subobligations
  49   have also been completed). So, for example, if the callback from
  50   `process_obligations` returns `Ok(Some(C))` for some obligation `O`,
  51   then `O` will be considered completed right away if `C` is the
  52   empty vector. Otherwise it will only be considered completed once
  53   all the obligations in `C` have been found completed.
  54 - `errors`: a list of errors that occurred and associated backtraces
  55   at the time of error, which can be used to give context to the user.
  56 - `stalled`: if true, then none of the existing obligations were
  57   *shallowly successful* (that is, no callback returned `Ok(Some(_))`).
  58   This implies that all obligations were either errors or returned an
  59   ambiguous result, which means that any further calls to
  60   `process_obligations` would simply yield back further ambiguous
  61   results. This is used by the `FulfillmentContext` to decide when it
  62   has reached a steady state.
  63
  64 #### Snapshots
  65
  66 The `ObligationForest` supports a limited form of snapshots; see
  67 `start_snapshot`; `commit_snapshot`; and `rollback_snapshot`. In
  68 particular, you can use a snapshot to roll back new root
  69 obligations. However, it is an error to attempt to
  70 `process_obligations` during a snapshot.
  71
  72 ### Implementation details
  73
  74 For the most part, comments specific to the implementation are in the
  75 code.  This file only contains a very high-level overview. Basically,
  76 the forest is stored in a vector. Each element of the vector is a node
  77 in some tree. Each node in the vector has the index of an (optional)
  78 parent and (for convenience) its root (which may be itself). It also
  79 has a current state, described by `NodeState`. After each
  80 processing step, we compress the vector to remove completed and error
  81 nodes, which aren't needed anymore.
  82
  83