Struct rustc_data_structures::obligation_forest::ObligationForest

pub struct ObligationForest<O: ForestObligation> {
    nodes: Vec<Node<O>>,
    done_cache: FxHashSet<O::CacheKey>,
    active_cache: FxHashMap<O::CacheKey, usize>,
    reused_node_vec: Vec<usize>,
    obligation_tree_id_generator: Map<RangeFrom<usize>, fn(_: usize) -> ObligationTreeId>,
    error_cache: FxHashMap<ObligationTreeId, FxHashSet<O::CacheKey>>,
}

Fields

nodes: Vec<Node<O>>

The list of obligations. In between calls to process_obligations, this list only contains nodes in the Pending or Waiting state.

usize indices are used here and throughout this module, rather than rustc_index::newtype_index! indices, because this code is hot enough that the u32-to-usize conversions that would be required are significant, and space considerations are not important.

done_cache: FxHashSet<O::CacheKey>

A cache of predicates that have been successfully completed.

active_cache: FxHashMap<O::CacheKey, usize>

A cache of the nodes in nodes, indexed by predicate. Unfortunately, its contents are not guaranteed to match those of nodes. See the comments in process_obligation for details.

reused_node_vec: Vec<usize>

A vector reused in compress() and find_cycles_from_node(), to avoid allocating new vectors.

obligation_tree_id_generator: Map<RangeFrom<usize>, fn(_: usize) -> ObligationTreeId>

error_cache: FxHashMap<ObligationTreeId, FxHashSet<O::CacheKey>>

Per tree error cache. This is used to deduplicate errors, which is necessary to avoid trait resolution overflow in some cases.

See this for details.

Implementations

impl<O: ForestObligation> ObligationForest<O>

pub fn dump_graphviz<P: AsRef<Path>>(&self, dir: P, description: &str)

Creates a graphviz representation of the obligation forest. Given a directory this will create files with name of the format <counter>_<description>.gv. The counter is global and is maintained internally.

Calling this will do nothing unless the environment variable DUMP_OBLIGATION_FOREST_GRAPHVIZ is defined.

A few post-processing that you might want to do make the forest easier to visualize:

• sed 's,std::[a-z]*::,,g' — Deletes the std::<package>:: prefix of paths.
• sed 's,"Binder(TraitPredicate(<\(.*\)>)) (\([^)]*\))","\1 (\2)",' — Transforms Binder(TraitPredicate(<predicate>)) into just <predicate>.

impl<O: ForestObligation> ObligationForest<O>

pub fn new() -> ObligationForest<O>

pub fn len(&self) -> usize

Returns the total number of nodes in the forest that have not yet been fully resolved.

pub fn register_obligation(&mut self, obligation: O)

Registers an obligation.

fn register_obligation_at(
    &mut self,
    obligation: O,
    parent: Option<usize>
) -> Result<(), ()>

pub fn to_errors<E: Clone>(&mut self, error: E) -> Vec<Error<O, E>>

Converts all remaining obligations to the given error.

pub fn map_pending_obligations<P, F>(&self, f: F) -> Vec<P> where
    F: Fn(&O) -> P, 

Returns the set of obligations that are in a pending state.

fn insert_into_error_cache(&mut self, index: usize)

pub fn process_obligations<P, OUT>(&mut self, processor: &mut P) -> OUT where
    P: ObligationProcessor<Obligation = O>,
    OUT: OutcomeTrait<Obligation = O, Error = Error<O, P::Error>>, 

Performs a pass through the obligation list. This must be called in a loop until outcome.stalled is false.

This cannot be unrolled (presently, at least).

fn error_at(&self, index: usize) -> Vec<O>

Returns a vector of obligations for p and all of its ancestors, putting them into the error state in the process.

fn mark_successes(&self)

Mark all Waiting nodes as Success, except those that depend on a pending node.

fn inlined_mark_dependents_as_waiting(&self, node: &Node<O>)

fn uninlined_mark_dependents_as_waiting(&self, node: &Node<O>)

fn process_cycles<P>(&mut self, processor: &mut P) where
    P: ObligationProcessor<Obligation = O>, 

Report cycles between all Success nodes, and convert all Success nodes to Done. This must be called after mark_successes.

fn find_cycles_from_node<P>(
    &self,
    stack: &mut Vec<usize>,
    processor: &mut P,
    index: usize
) where
    P: ObligationProcessor<Obligation = O>, 

fn compress(&mut self, outcome_cb: impl FnMut(&O))

Compresses the vector, removing all popped nodes. This adjusts the indices and hence invalidates any outstanding indices. process_cycles must be run beforehand to remove any cycles on Success nodes.

fn apply_rewrites(&mut self, node_rewrites: &[usize])

Trait Implementations

impl<'a, O: ForestObligation + 'a> GraphWalk<'a> for &'a ObligationForest<O>

type Node = usize

type Edge = (usize, usize)

fn nodes(&self) -> Nodes<'_, Self::Node>

Returns all the nodes in this graph.

fn edges(&self) -> Edges<'_, Self::Edge>

Returns all of the edges in this graph.

fn source(&self, (s, _): &Self::Edge) -> Self::Node

The source node for edge.

fn target(&self, (_, t): &Self::Edge) -> Self::Node

The target node for edge.

impl<'a, O: ForestObligation + 'a> Labeller<'a> for &'a ObligationForest<O>

type Node = usize

type Edge = (usize, usize)

fn graph_id(&self) -> Id<'_>

Must return a DOT compatible identifier naming the graph.

fn node_id(&self, index: &Self::Node) -> Id<'_>

Maps n to a unique identifier with respect to self. The implementor is responsible for ensuring that the returned name is a valid DOT identifier.

fn node_label(&self, index: &Self::Node) -> LabelText<'_>

Maps n to a label that will be used in the rendered output. The label need not be unique, and may be the empty string; the default is just the output from node_id.

fn edge_label(
    &self,
    (_index_source, _index_target): &Self::Edge
) -> LabelText<'_>

Maps e to a label that will be used in the rendered output. The label need not be unique, and may be the empty string; the default is in fact the empty string.

fn node_shape(&'a self, _node: &Self::Node) -> Option<LabelText<'a>>

Maps n to one of the graphviz shape names. If None is returned, no shape attribute is specified.

fn node_style(&'a self, _n: &Self::Node) -> Style

Maps n to a style that will be used in the rendered output.

fn edge_style(&'a self, _e: &Self::Edge) -> Style

Maps e to a style that will be used in the rendered output.