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 Self::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 Self::process_obligation for details.

reused_node_vec: Vec<usize>

A vector reused in Self::compress() and Self::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) -> OUTwhere
    P: ObligationProcessor<Obligation = O>,
    OUT: OutcomeTrait<Obligation = O, Error = Error<O, P::Error>>,

Performs a fixpoint computation over the obligation list.

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.

Layout

Note: Most layout information is completely unstable and may even differ between compilations. The only exception is types with certain repr(...) attributes. Please see the Rust Reference’s “Type Layout” chapter for details on type layout guarantees.

Size: 160 bytes