Struct rustc_data_structures::graph::scc::SccsConstruction

source ·
struct SccsConstruction<'c, G, S, A, F>
where G: DirectedGraph + Successors, S: Idx, A: Annotation, F: Fn(G::Node) -> A,
{ graph: &'c G, node_states: IndexVec<G::Node, NodeState<G::Node, S, A>>, node_stack: Vec<G::Node>, successors_stack: Vec<S>, duplicate_set: FxHashSet<S>, scc_data: SccData<S, A>, to_annotation: F, }

Fields§

§graph: &'c G§node_states: IndexVec<G::Node, NodeState<G::Node, S, A>>

The state of each node; used during walk to record the stack and after walk to record what cycle each node ended up being in.

§node_stack: Vec<G::Node>

The stack of nodes that we are visiting as part of the DFS.

§successors_stack: Vec<S>

The stack of successors: as we visit a node, we mark our position in this stack, and when we encounter a successor SCC, we push it on the stack. When we complete an SCC, we can pop everything off the stack that was found along the way.

§duplicate_set: FxHashSet<S>

A set used to strip duplicates. As we accumulate successors into the successors_stack, we sometimes get duplicate entries. We use this set to remove those – we also keep its storage around between successors to amortize memory allocation costs.

§scc_data: SccData<S, A>§to_annotation: F

A function that constructs an initial SCC annotation out of a single node.

Implementations§

source§

impl<'c, G, S, A, F> SccsConstruction<'c, G, S, A, F>
where G: DirectedGraph + Successors, S: Idx, F: Fn(G::Node) -> A, A: Annotation,

source

fn construct(graph: &'c G, to_annotation: F) -> Sccs<G::Node, S, A>

Identifies SCCs in the graph G and computes the resulting DAG. This uses a variant of Tarjan’s algorithm. The high-level summary of the algorithm is that we do a depth-first search. Along the way, we keep a stack of each node whose successors are being visited. We track the depth of each node on this stack (there is no depth if the node is not on the stack). When we find that some node N with depth D can reach some other node N’ with lower depth D’ (i.e., D’ < D), we know that N, N’, and all nodes in between them on the stack are part of an SCC.

Additionally, we keep track of a current annotation of the SCC.

source

fn start_walk_from(&mut self, node: G::Node) -> WalkReturn<S, A>

source

fn inspect_node(&mut self, node: G::Node) -> Option<WalkReturn<S, A>>

Inspect a node during the DFS. We first examine its current state – if it is not yet visited (NotVisited), return None so that the caller might push it onto the stack and start walking its successors.

If it is already on the DFS stack it will be in the state BeingVisited. In that case, we have found a cycle and we return the depth from the stack.

Otherwise, we are looking at a node that has already been completely visited. We therefore return WalkReturn::Complete with its associated SCC index.

source

fn find_state(&mut self, node: G::Node) -> NodeState<G::Node, S, A>

Fetches the state of the node r. If r is recorded as being in a cycle with some other node r2, then fetches the state of r2 (and updates r to reflect current result). This is basically the “find” part of a standard union-find algorithm (with path compression).

source

fn walk_unvisited_node(&mut self, initial: G::Node) -> WalkReturn<S, A>

Walks a node that has never been visited before.

Call this method when inspect_node has returned None. Having the caller decide avoids mutual recursion between the two methods and allows us to maintain an allocated stack for nodes on the path between calls.

Auto Trait Implementations§

§

impl<'c, G, S, A, F> Freeze for SccsConstruction<'c, G, S, A, F>
where F: Freeze,

§

impl<'c, G, S, A, F> RefUnwindSafe for SccsConstruction<'c, G, S, A, F>

§

impl<'c, G, S, A, F> Send for SccsConstruction<'c, G, S, A, F>
where F: Send, G: Sync, A: Send, S: Send, <G as DirectedGraph>::Node: Send,

§

impl<'c, G, S, A, F> Sync for SccsConstruction<'c, G, S, A, F>
where F: Sync, G: Sync, <G as DirectedGraph>::Node: Sync, S: Sync, A: Sync,

§

impl<'c, G, S, A, F> Unpin for SccsConstruction<'c, G, S, A, F>
where F: Unpin, <G as DirectedGraph>::Node: Unpin, S: Unpin, A: Unpin,

§

impl<'c, G, S, A, F> UnwindSafe for SccsConstruction<'c, G, S, A, F>

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>,

source§

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>,

source§

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: Unable to compute type layout, possibly due to this type having generic parameters. Layout can only be computed for concrete, fully-instantiated types.