Struct rustc_query_system::dep_graph::graph::CurrentDepGraph

pub(super) struct CurrentDepGraph<K> {
    data: Lock<DepNodeData<K>>,
    new_node_to_index: Sharded<FxHashMap<DepNode<K>, DepNodeIndex>>,
    prev_index_to_index: Lock<IndexVec<SerializedDepNodeIndex, Option<DepNodeIndex>>>,
    forbidden_edge: Option<EdgeFilter>,
    anon_id_seed: Fingerprint,
    total_read_count: AtomicU64,
    total_duplicate_read_count: AtomicU64,
}

CurrentDepGraph stores the dependency graph for the current session. It will be populated as we run queries or tasks. We never remove nodes from the graph: they are only added.

The nodes in it are identified by a DepNodeIndex. Internally, this maps to a HybridIndex, which identifies which collection in the data field contains a node’s data. Which collection is used for a node depends on whether the node was present in the PreviousDepGraph, and if so, the color of the node. Each type of node can share more or less data with the previous graph. When possible, we can store just the index of the node in the previous graph, rather than duplicating its data in our own collections. This is important, because these graph structures are some of the largest in the compiler.

For the same reason, we also avoid storing DepNodes more than once as map keys. The new_node_to_index map only contains nodes not in the previous graph, and we map nodes in the previous graph to indices via a two-step mapping. PreviousDepGraph maps from DepNode to SerializedDepNodeIndex, and the prev_index_to_index vector (which is more compact and faster than using a map) maps from SerializedDepNodeIndex to DepNodeIndex.

This struct uses three locks internally. The data, new_node_to_index, and prev_index_to_index fields are locked separately. Operations that take a DepNodeIndex typically just access the data field.

We only need to manipulate at most two locks simultaneously: new_node_to_index and data, or prev_index_to_index and data. When manipulating both, we acquire new_node_to_index or prev_index_to_index first, and data second.

Fields

data: Lock<DepNodeData<K>>

new_node_to_index: Sharded<FxHashMap<DepNode<K>, DepNodeIndex>>

prev_index_to_index: Lock<IndexVec<SerializedDepNodeIndex, Option<DepNodeIndex>>>

forbidden_edge: Option<EdgeFilter>

Used to trap when a specific edge is added to the graph. This is used for debug purposes and is only active with debug_assertions.

anon_id_seed: Fingerprint

Anonymous DepNodes are nodes whose IDs we compute from the list of their edges. This has the beneficial side-effect that multiple anonymous nodes can be coalesced into one without changing the semantics of the dependency graph. However, the merging of nodes can lead to a subtle problem during red-green marking: The color of an anonymous node from the current session might “shadow” the color of the node with the same ID from the previous session. In order to side-step this problem, we make sure that anonymous NodeIds allocated in different sessions don’t overlap. This is implemented by mixing a session-key into the ID fingerprint of each anon node. The session-key is just a random number generated when the DepGraph is created.

total_read_count: AtomicU64

These are simple counters that are for profiling and debugging and only active with debug_assertions.

total_duplicate_read_count: AtomicU64

Implementations

impl<K: DepKind> CurrentDepGraph<K>

fn new(prev_graph_node_count: usize) -> CurrentDepGraph<K>

fn intern_new_node(
    &self,
    prev_graph: &PreviousDepGraph<K>,
    dep_node: DepNode<K>,
    edges: SmallVec<[DepNodeIndex; 8]>,
    fingerprint: Fingerprint
) -> DepNodeIndex

fn intern_red_node(
    &self,
    prev_graph: &PreviousDepGraph<K>,
    prev_index: SerializedDepNodeIndex,
    edges: SmallVec<[DepNodeIndex; 8]>,
    fingerprint: Fingerprint
) -> DepNodeIndex

fn intern_light_green_node(
    &self,
    prev_graph: &PreviousDepGraph<K>,
    prev_index: SerializedDepNodeIndex,
    edges: SmallVec<[DepNodeIndex; 8]>
) -> DepNodeIndex

fn intern_dark_green_node(
    &self,
    prev_graph: &PreviousDepGraph<K>,
    prev_index: SerializedDepNodeIndex
) -> DepNodeIndex

fn debug_assert_not_in_new_nodes(
    &self,
    prev_graph: &PreviousDepGraph<K>,
    prev_index: SerializedDepNodeIndex
)