diff options
| -rw-r--r-- | compiler/rustc_data_structures/src/graph/linked_graph/mod.rs (renamed from compiler/rustc_data_structures/src/graph/implementation/mod.rs) | 36 | ||||
| -rw-r--r-- | compiler/rustc_data_structures/src/graph/linked_graph/tests.rs (renamed from compiler/rustc_data_structures/src/graph/implementation/tests.rs) | 8 | ||||
| -rw-r--r-- | compiler/rustc_data_structures/src/graph/mod.rs | 2 | ||||
| -rw-r--r-- | compiler/rustc_incremental/src/assert_dep_graph.rs | 2 | ||||
| -rw-r--r-- | compiler/rustc_infer/src/infer/lexical_region_resolve/mod.rs | 8 | ||||
| -rw-r--r-- | compiler/rustc_query_system/src/dep_graph/query.rs | 6 |
6 files changed, 39 insertions, 23 deletions
diff --git a/compiler/rustc_data_structures/src/graph/implementation/mod.rs b/compiler/rustc_data_structures/src/graph/linked_graph/mod.rs index a80365938b9..ecb0095626b 100644 --- a/compiler/rustc_data_structures/src/graph/implementation/mod.rs +++ b/compiler/rustc_data_structures/src/graph/linked_graph/mod.rs @@ -1,4 +1,4 @@ -//! A graph module for use in dataflow, region resolution, and elsewhere. +//! See [`LinkedGraph`]. //! //! # Interface details //! @@ -28,7 +28,23 @@ use tracing::debug; #[cfg(test)] mod tests; -pub struct Graph<N, E> { +/// A concrete graph implementation that supports: +/// - Nodes and/or edges labelled with custom data types (`N` and `E` respectively). +/// - Incremental addition of new nodes/edges (but not removal). +/// - Flat storage of node/edge data in a pair of vectors. +/// - Iteration over any node's out-edges or in-edges, via linked lists +/// threaded through the node/edge data. +/// +/// # Caution +/// This is an older graph implementation that is still used by some pieces +/// of diagnostic/debugging code. New code that needs a graph data structure +/// should consider using `VecGraph` instead, or implementing its own +/// special-purpose graph with the specific features needed. +/// +/// This graph implementation predates the later [graph traits](crate::graph), +/// and does not implement those traits, so it has its own implementations of a +/// few basic graph algorithms. +pub struct LinkedGraph<N, E> { nodes: Vec<Node<N>>, edges: Vec<Edge<E>>, } @@ -71,13 +87,13 @@ impl NodeIndex { } } -impl<N: Debug, E: Debug> Graph<N, E> { - pub fn new() -> Graph<N, E> { - Graph { nodes: Vec::new(), edges: Vec::new() } +impl<N: Debug, E: Debug> LinkedGraph<N, E> { + pub fn new() -> Self { + Self { nodes: Vec::new(), edges: Vec::new() } } - pub fn with_capacity(nodes: usize, edges: usize) -> Graph<N, E> { - Graph { nodes: Vec::with_capacity(nodes), edges: Vec::with_capacity(edges) } + pub fn with_capacity(nodes: usize, edges: usize) -> Self { + Self { nodes: Vec::with_capacity(nodes), edges: Vec::with_capacity(edges) } } // # Simple accessors @@ -249,7 +265,7 @@ impl<N: Debug, E: Debug> Graph<N, E> { // # Iterators pub struct AdjacentEdges<'g, N, E> { - graph: &'g Graph<N, E>, + graph: &'g LinkedGraph<N, E>, direction: Direction, next: EdgeIndex, } @@ -285,7 +301,7 @@ impl<'g, N: Debug, E: Debug> Iterator for AdjacentEdges<'g, N, E> { } pub struct DepthFirstTraversal<'g, N, E> { - graph: &'g Graph<N, E>, + graph: &'g LinkedGraph<N, E>, stack: Vec<NodeIndex>, visited: DenseBitSet<usize>, direction: Direction, @@ -293,7 +309,7 @@ pub struct DepthFirstTraversal<'g, N, E> { impl<'g, N: Debug, E: Debug> DepthFirstTraversal<'g, N, E> { pub fn with_start_node( - graph: &'g Graph<N, E>, + graph: &'g LinkedGraph<N, E>, start_node: NodeIndex, direction: Direction, ) -> Self { diff --git a/compiler/rustc_data_structures/src/graph/implementation/tests.rs b/compiler/rustc_data_structures/src/graph/linked_graph/tests.rs index 32a6d9ec881..357aa81a57c 100644 --- a/compiler/rustc_data_structures/src/graph/implementation/tests.rs +++ b/compiler/rustc_data_structures/src/graph/linked_graph/tests.rs @@ -1,11 +1,11 @@ use tracing::debug; -use crate::graph::implementation::*; +use super::{Debug, LinkedGraph, NodeIndex}; -type TestGraph = Graph<&'static str, &'static str>; +type TestGraph = LinkedGraph<&'static str, &'static str>; fn create_graph() -> TestGraph { - let mut graph = Graph::new(); + let mut graph = LinkedGraph::new(); // Create a simple graph // @@ -56,7 +56,7 @@ fn each_edge() { } fn test_adjacent_edges<N: PartialEq + Debug, E: PartialEq + Debug>( - graph: &Graph<N, E>, + graph: &LinkedGraph<N, E>, start_index: NodeIndex, start_data: N, expected_incoming: &[(E, N)], diff --git a/compiler/rustc_data_structures/src/graph/mod.rs b/compiler/rustc_data_structures/src/graph/mod.rs index 4a1e5db6768..20416b472b2 100644 --- a/compiler/rustc_data_structures/src/graph/mod.rs +++ b/compiler/rustc_data_structures/src/graph/mod.rs @@ -1,8 +1,8 @@ use rustc_index::Idx; pub mod dominators; -pub mod implementation; pub mod iterate; +pub mod linked_graph; mod reference; pub mod reversed; pub mod scc; diff --git a/compiler/rustc_incremental/src/assert_dep_graph.rs b/compiler/rustc_incremental/src/assert_dep_graph.rs index 1b2056f541f..0e04a2a784e 100644 --- a/compiler/rustc_incremental/src/assert_dep_graph.rs +++ b/compiler/rustc_incremental/src/assert_dep_graph.rs @@ -38,7 +38,7 @@ use std::fs::{self, File}; use std::io::Write; use rustc_data_structures::fx::FxIndexSet; -use rustc_data_structures::graph::implementation::{Direction, INCOMING, NodeIndex, OUTGOING}; +use rustc_data_structures::graph::linked_graph::{Direction, INCOMING, NodeIndex, OUTGOING}; use rustc_hir::def_id::{CRATE_DEF_ID, DefId, LocalDefId}; use rustc_hir::intravisit::{self, Visitor}; use rustc_middle::dep_graph::{ diff --git a/compiler/rustc_infer/src/infer/lexical_region_resolve/mod.rs b/compiler/rustc_infer/src/infer/lexical_region_resolve/mod.rs index e3522137d83..2185886901e 100644 --- a/compiler/rustc_infer/src/infer/lexical_region_resolve/mod.rs +++ b/compiler/rustc_infer/src/infer/lexical_region_resolve/mod.rs @@ -3,8 +3,8 @@ use std::fmt; use rustc_data_structures::fx::FxHashSet; -use rustc_data_structures::graph::implementation::{ - Direction, Graph, INCOMING, NodeIndex, OUTGOING, +use rustc_data_structures::graph::linked_graph::{ + Direction, INCOMING, LinkedGraph, NodeIndex, OUTGOING, }; use rustc_data_structures::intern::Interned; use rustc_data_structures::unord::UnordSet; @@ -118,7 +118,7 @@ struct RegionAndOrigin<'tcx> { origin: SubregionOrigin<'tcx>, } -type RegionGraph<'tcx> = Graph<(), Constraint<'tcx>>; +type RegionGraph<'tcx> = LinkedGraph<(), Constraint<'tcx>>; struct LexicalResolver<'cx, 'tcx> { region_rels: &'cx RegionRelations<'cx, 'tcx>, @@ -668,7 +668,7 @@ impl<'cx, 'tcx> LexicalResolver<'cx, 'tcx> { fn construct_graph(&self) -> RegionGraph<'tcx> { let num_vars = self.num_vars(); - let mut graph = Graph::new(); + let mut graph = LinkedGraph::new(); for _ in 0..num_vars { graph.add_node(()); diff --git a/compiler/rustc_query_system/src/dep_graph/query.rs b/compiler/rustc_query_system/src/dep_graph/query.rs index 624f4e4578e..724a01327ab 100644 --- a/compiler/rustc_query_system/src/dep_graph/query.rs +++ b/compiler/rustc_query_system/src/dep_graph/query.rs @@ -1,11 +1,11 @@ use rustc_data_structures::fx::FxHashMap; -use rustc_data_structures::graph::implementation::{Direction, Graph, INCOMING, NodeIndex}; +use rustc_data_structures::graph::linked_graph::{Direction, INCOMING, LinkedGraph, NodeIndex}; use rustc_index::IndexVec; use super::{DepNode, DepNodeIndex}; pub struct DepGraphQuery { - pub graph: Graph<DepNode, ()>, + pub graph: LinkedGraph<DepNode, ()>, pub indices: FxHashMap<DepNode, NodeIndex>, pub dep_index_to_index: IndexVec<DepNodeIndex, Option<NodeIndex>>, } @@ -15,7 +15,7 @@ impl DepGraphQuery { let node_count = prev_node_count + prev_node_count / 4; let edge_count = 6 * node_count; - let graph = Graph::with_capacity(node_count, edge_count); + let graph = LinkedGraph::with_capacity(node_count, edge_count); let indices = FxHashMap::default(); let dep_index_to_index = IndexVec::new(); |