Module rustc_data_structures::graph

🔬 This is a nightly-only experimental API. (rustc_private)

this crate is being loaded from the sysroot, an unstable location; did you mean to load this crate from crates.io via Cargo.toml instead?

A graph module for use in dataflow, region resolution, and elsewhere.

Interface details

You customize the graph by specifying a "node data" type N and an "edge data" type E. You can then later gain access (mutable or immutable) to these "user-data" bits. Currently, you can only add nodes or edges to the graph. You cannot remove or modify them once added. This could be changed if we have a need.

Implementation details

The main tricky thing about this code is the way that edges are stored. The edges are stored in a central array, but they are also threaded onto two linked lists for each node, one for incoming edges and one for outgoing edges. Note that every edge is a member of some incoming list and some outgoing list. Basically you can load the first index of the linked list from the node data structures (the field first_edge) and then, for each edge, load the next index from the field next_edge). Each of those fields is an array that should be indexed by the direction (see the type Direction).

Structs

AdjacentEdges	[ Experimental ]
AdjacentSources	[ Experimental ]
AdjacentTargets	[ Experimental ]
DepthFirstTraversal	[ Experimental ]
Direction	[ Experimental ]
Edge	[ Experimental ]
EdgeIndex	[ Experimental ]
EnumeratedEdges	[ Experimental ]
EnumeratedNodes	[ Experimental ]
Graph	[ Experimental ]
Node	[ Experimental ]
NodeIndex	[ Experimental ]

Constants

INCOMING	[ Experimental ]
INVALID_EDGE_INDEX	[ Experimental ]
OUTGOING	[ Experimental ]