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: impl Iterator<Item = 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: impl Iterator<Item = 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§

source§

impl<O: ForestObligation> ObligationForest<O>

source

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>.
source§

impl<O: ForestObligation> ObligationForest<O>

source

pub fn new() -> ObligationForest<O>

source

pub fn len(&self) -> usize

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

source

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

Registers an obligation.

source

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

source

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

Converts all remaining obligations to the given error.

source

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.

source

fn insert_into_error_cache(&mut self, index: usize)

source

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

Performs a fixpoint computation over the obligation list.

source

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.

source

fn mark_successes(&self)

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

source

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

source

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

source

fn process_cycles<P>(&mut self, processor: &mut P, outcome: &mut P::OUT)
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.

source

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

source

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.

source

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

Trait Implementations§

source§

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

§

type Node = usize

§

type Edge = (usize, usize)

source§

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

Returns all the nodes in this graph.
source§

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

Returns all of the edges in this graph.
source§

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

The source node for edge.
source§

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

The target node for edge.
source§

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

§

type Node = usize

§

type Edge = (usize, usize)

source§

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

Must return a DOT compatible identifier naming the graph.
source§

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.
source§

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.
source§

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.
source§

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.
source§

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

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

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

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

Auto Trait Implementations§

Blanket Implementations§

source§

impl<T> Aligned for T

source§

const ALIGN: Alignment = const ALIGN: Alignment = Alignment::of::<Self>();

Alignment of Self.
source§

impl<T> Any for T
where T: 'static + ?Sized,

source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
source§

impl<T> Borrow<T> for T
where T: ?Sized,

source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
source§

impl<T> From<T> for T

source§

fn from(t: T) -> T

Returns the argument unchanged.

source§

impl<T> Instrument for T

source§

fn instrument(self, span: Span) -> Instrumented<Self>

Instruments this type with the provided Span, returning an Instrumented wrapper. Read more
source§

fn in_current_span(self) -> Instrumented<Self>

Instruments this type with the current Span, returning an Instrumented wrapper. Read more
source§

impl<T, U> Into<U> for T
where U: From<T>,

source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

source§

impl<T> IntoEither for T

source§

fn into_either(self, into_left: bool) -> Either<Self, Self>

Converts self into a Left variant of Either<Self, Self> if into_left is true. Converts self into a Right variant of Either<Self, Self> otherwise. Read more
source§

fn into_either_with<F>(self, into_left: F) -> Either<Self, Self>
where F: FnOnce(&Self) -> bool,

Converts self into a Left variant of Either<Self, Self> if into_left(&self) returns true. Converts self into a Right variant of Either<Self, Self> otherwise. Read more
source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

§

type Error = Infallible

The type returned in the event of a conversion error.
source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.
source§

impl<T> WithSubscriber for T

source§

fn with_subscriber<S>(self, subscriber: S) -> WithDispatch<Self>
where S: Into<Dispatch>,

Attaches the provided Subscriber to this type, returning a WithDispatch wrapper. Read more
source§

fn with_current_subscriber(self) -> WithDispatch<Self>

Attaches the current default Subscriber to this type, returning a WithDispatch wrapper. Read more
source§

impl<'a, T> Captures<'a> for T
where T: ?Sized,

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: 152 bytes