diff options
Diffstat (limited to 'compiler/rustc_data_structures')
25 files changed, 426 insertions, 483 deletions
diff --git a/compiler/rustc_data_structures/Cargo.toml b/compiler/rustc_data_structures/Cargo.toml index 80b6e72e49b..2b61e17efa2 100644 --- a/compiler/rustc_data_structures/Cargo.toml +++ b/compiler/rustc_data_structures/Cargo.toml @@ -9,7 +9,7 @@ arrayvec = { version = "0.7", default-features = false } bitflags = "2.4.1" either = "1.0" elsa = "=1.7.1" -ena = "0.14.2" +ena = "0.14.3" indexmap = { version = "2.0.0" } jobserver_crate = { version = "0.1.28", package = "jobserver" } libc = "0.2" diff --git a/compiler/rustc_data_structures/src/base_n.rs b/compiler/rustc_data_structures/src/base_n.rs index a3eb2b9c416..aed89fadc4c 100644 --- a/compiler/rustc_data_structures/src/base_n.rs +++ b/compiler/rustc_data_structures/src/base_n.rs @@ -1,6 +1,7 @@ /// Converts unsigned integers into a string representation with some base. /// Bases up to and including 36 can be used for case-insensitive things. -use std::str; +use std::ascii; +use std::fmt; #[cfg(test)] mod tests; @@ -9,36 +10,101 @@ pub const MAX_BASE: usize = 64; pub const ALPHANUMERIC_ONLY: usize = 62; pub const CASE_INSENSITIVE: usize = 36; -const BASE_64: &[u8; MAX_BASE] = - b"0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ@$"; +const BASE_64: [ascii::Char; MAX_BASE] = { + let bytes = b"0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ@$"; + let Some(ascii) = bytes.as_ascii() else { panic!() }; + *ascii +}; -#[inline] -pub fn push_str(mut n: u128, base: usize, output: &mut String) { - debug_assert!(base >= 2 && base <= MAX_BASE); - let mut s = [0u8; 128]; - let mut index = s.len(); +pub struct BaseNString { + start: usize, + buf: [ascii::Char; 128], +} + +impl std::ops::Deref for BaseNString { + type Target = str; - let base = base as u128; + fn deref(&self) -> &str { + self.buf[self.start..].as_str() + } +} + +impl AsRef<str> for BaseNString { + fn as_ref(&self) -> &str { + self.buf[self.start..].as_str() + } +} + +impl fmt::Display for BaseNString { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.write_str(self) + } +} + +// This trait just lets us reserve the exact right amount of space when doing fixed-length +// case-insensitve encoding. Add any impls you need. +pub trait ToBaseN: Into<u128> { + fn encoded_len(base: usize) -> usize; + + fn to_base_fixed_len(self, base: usize) -> BaseNString { + let mut encoded = self.to_base(base); + encoded.start = encoded.buf.len() - Self::encoded_len(base); + encoded + } - loop { - index -= 1; - s[index] = BASE_64[(n % base) as usize]; - n /= base; + fn to_base(self, base: usize) -> BaseNString { + let mut output = [ascii::Char::Digit0; 128]; - if n == 0 { - break; + let mut n: u128 = self.into(); + + let mut index = output.len(); + loop { + index -= 1; + output[index] = BASE_64[(n % base as u128) as usize]; + n /= base as u128; + + if n == 0 { + break; + } + } + assert_eq!(n, 0); + + BaseNString { start: index, buf: output } + } +} + +impl ToBaseN for u128 { + fn encoded_len(base: usize) -> usize { + let mut max = u128::MAX; + let mut len = 0; + while max > 0 { + len += 1; + max /= base as u128; } + len } +} - output.push_str(unsafe { - // SAFETY: `s` is populated using only valid utf8 characters from `BASE_64` - str::from_utf8_unchecked(&s[index..]) - }); +impl ToBaseN for u64 { + fn encoded_len(base: usize) -> usize { + let mut max = u64::MAX; + let mut len = 0; + while max > 0 { + len += 1; + max /= base as u64; + } + len + } } -#[inline] -pub fn encode(n: u128, base: usize) -> String { - let mut s = String::new(); - push_str(n, base, &mut s); - s +impl ToBaseN for u32 { + fn encoded_len(base: usize) -> usize { + let mut max = u32::MAX; + let mut len = 0; + while max > 0 { + len += 1; + max /= base as u32; + } + len + } } diff --git a/compiler/rustc_data_structures/src/base_n/tests.rs b/compiler/rustc_data_structures/src/base_n/tests.rs index 2be2f0532c9..148d8dde02a 100644 --- a/compiler/rustc_data_structures/src/base_n/tests.rs +++ b/compiler/rustc_data_structures/src/base_n/tests.rs @@ -1,9 +1,17 @@ use super::*; #[test] -fn test_encode() { +fn limits() { + assert_eq!(Ok(u128::MAX), u128::from_str_radix(&u128::MAX.to_base(36), 36)); + assert_eq!(Ok(u64::MAX), u64::from_str_radix(&u64::MAX.to_base(36), 36)); + assert_eq!(Ok(u32::MAX), u32::from_str_radix(&u32::MAX.to_base(36), 36)); +} + +#[test] +fn test_to_base() { fn test(n: u128, base: usize) { - assert_eq!(Ok(n), u128::from_str_radix(&encode(n, base), base as u32)); + assert_eq!(Ok(n), u128::from_str_radix(&n.to_base(base), base as u32)); + assert_eq!(Ok(n), u128::from_str_radix(&n.to_base_fixed_len(base), base as u32)); } for base in 2..37 { diff --git a/compiler/rustc_data_structures/src/fingerprint.rs b/compiler/rustc_data_structures/src/fingerprint.rs index 9995c08345c..1bee159489d 100644 --- a/compiler/rustc_data_structures/src/fingerprint.rs +++ b/compiler/rustc_data_structures/src/fingerprint.rs @@ -1,3 +1,4 @@ +use crate::stable_hasher::impl_stable_traits_for_trivial_type; use crate::stable_hasher::{Hash64, StableHasher, StableHasherResult}; use rustc_serialize::{Decodable, Decoder, Encodable, Encoder}; use std::hash::{Hash, Hasher}; diff --git a/compiler/rustc_data_structures/src/flock/windows.rs b/compiler/rustc_data_structures/src/flock/windows.rs index 9be1065135a..7dc72661939 100644 --- a/compiler/rustc_data_structures/src/flock/windows.rs +++ b/compiler/rustc_data_structures/src/flock/windows.rs @@ -2,6 +2,7 @@ use std::fs::{File, OpenOptions}; use std::io; use std::os::windows::prelude::*; use std::path::Path; +use tracing::debug; use windows::{ Win32::Foundation::{ERROR_INVALID_FUNCTION, HANDLE}, diff --git a/compiler/rustc_data_structures/src/graph/implementation/mod.rs b/compiler/rustc_data_structures/src/graph/implementation/mod.rs index 3910c6fa46d..8cf4b4153db 100644 --- a/compiler/rustc_data_structures/src/graph/implementation/mod.rs +++ b/compiler/rustc_data_structures/src/graph/implementation/mod.rs @@ -22,6 +22,7 @@ use rustc_index::bit_set::BitSet; use std::fmt::Debug; +use tracing::debug; #[cfg(test)] mod tests; diff --git a/compiler/rustc_data_structures/src/graph/implementation/tests.rs b/compiler/rustc_data_structures/src/graph/implementation/tests.rs index 3ae5f5868f0..b4dbd65db94 100644 --- a/compiler/rustc_data_structures/src/graph/implementation/tests.rs +++ b/compiler/rustc_data_structures/src/graph/implementation/tests.rs @@ -1,4 +1,5 @@ use crate::graph::implementation::*; +use tracing::debug; type TestGraph = Graph<&'static str, &'static str>; diff --git a/compiler/rustc_data_structures/src/graph/iterate/mod.rs b/compiler/rustc_data_structures/src/graph/iterate/mod.rs index 7a77f2c0dbb..78d05a6e195 100644 --- a/compiler/rustc_data_structures/src/graph/iterate/mod.rs +++ b/compiler/rustc_data_structures/src/graph/iterate/mod.rs @@ -70,21 +70,21 @@ pub fn reverse_post_order<G: DirectedGraph + Successors>( } /// A "depth-first search" iterator for a directed graph. -pub struct DepthFirstSearch<'graph, G> +pub struct DepthFirstSearch<G> where - G: ?Sized + DirectedGraph + Successors, + G: DirectedGraph + Successors, { - graph: &'graph G, + graph: G, stack: Vec<G::Node>, visited: BitSet<G::Node>, } -impl<'graph, G> DepthFirstSearch<'graph, G> +impl<G> DepthFirstSearch<G> where - G: ?Sized + DirectedGraph + Successors, + G: DirectedGraph + Successors, { - pub fn new(graph: &'graph G) -> Self { - Self { graph, stack: vec![], visited: BitSet::new_empty(graph.num_nodes()) } + pub fn new(graph: G) -> Self { + Self { stack: vec![], visited: BitSet::new_empty(graph.num_nodes()), graph } } /// Version of `push_start_node` that is convenient for chained @@ -125,9 +125,9 @@ where } } -impl<G> std::fmt::Debug for DepthFirstSearch<'_, G> +impl<G> std::fmt::Debug for DepthFirstSearch<G> where - G: ?Sized + DirectedGraph + Successors, + G: DirectedGraph + Successors, { fn fmt(&self, fmt: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { let mut f = fmt.debug_set(); @@ -138,9 +138,9 @@ where } } -impl<G> Iterator for DepthFirstSearch<'_, G> +impl<G> Iterator for DepthFirstSearch<G> where - G: ?Sized + DirectedGraph + Successors, + G: DirectedGraph + Successors, { type Item = G::Node; diff --git a/compiler/rustc_data_structures/src/graph/mod.rs b/compiler/rustc_data_structures/src/graph/mod.rs index 3ae3023a91b..103ddd917bf 100644 --- a/compiler/rustc_data_structures/src/graph/mod.rs +++ b/compiler/rustc_data_structures/src/graph/mod.rs @@ -46,9 +46,35 @@ where .is_some() } -pub fn depth_first_search<G>(graph: &G, from: G::Node) -> iterate::DepthFirstSearch<'_, G> +pub fn depth_first_search<G>(graph: G, from: G::Node) -> iterate::DepthFirstSearch<G> where - G: ?Sized + Successors, + G: Successors, { iterate::DepthFirstSearch::new(graph).with_start_node(from) } + +pub fn depth_first_search_as_undirected<G>( + graph: G, + from: G::Node, +) -> iterate::DepthFirstSearch<impl Successors<Node = G::Node>> +where + G: Successors + Predecessors, +{ + struct AsUndirected<G>(G); + + impl<G: DirectedGraph> DirectedGraph for AsUndirected<G> { + type Node = G::Node; + + fn num_nodes(&self) -> usize { + self.0.num_nodes() + } + } + + impl<G: Successors + Predecessors> Successors for AsUndirected<G> { + fn successors(&self, node: Self::Node) -> impl Iterator<Item = Self::Node> { + self.0.successors(node).chain(self.0.predecessors(node)) + } + } + + iterate::DepthFirstSearch::new(AsUndirected(graph)).with_start_node(from) +} diff --git a/compiler/rustc_data_structures/src/graph/scc/mod.rs b/compiler/rustc_data_structures/src/graph/scc/mod.rs index 5021e5e8fc0..914a6a16348 100644 --- a/compiler/rustc_data_structures/src/graph/scc/mod.rs +++ b/compiler/rustc_data_structures/src/graph/scc/mod.rs @@ -10,6 +10,7 @@ use crate::graph::vec_graph::VecGraph; use crate::graph::{DirectedGraph, NumEdges, Successors}; use rustc_index::{Idx, IndexSlice, IndexVec}; use std::ops::Range; +use tracing::{debug, instrument}; #[cfg(test)] mod tests; diff --git a/compiler/rustc_data_structures/src/graph/vec_graph/mod.rs b/compiler/rustc_data_structures/src/graph/vec_graph/mod.rs index 26c86469fad..120244c8918 100644 --- a/compiler/rustc_data_structures/src/graph/vec_graph/mod.rs +++ b/compiler/rustc_data_structures/src/graph/vec_graph/mod.rs @@ -1,99 +1,235 @@ -use crate::graph::{DirectedGraph, NumEdges, Successors}; +use crate::graph::{DirectedGraph, NumEdges, Predecessors, Successors}; use rustc_index::{Idx, IndexVec}; #[cfg(test)] mod tests; -pub struct VecGraph<N: Idx> { - /// Maps from a given node to an index where the set of successors - /// for that node starts. The index indexes into the `edges` - /// vector. To find the range for a given node, we look up the - /// start for that node and then the start for the next node - /// (i.e., with an index 1 higher) and get the range between the - /// two. This vector always has an extra entry so that this works - /// even for the max element. +/// A directed graph, efficient for cases where node indices are pre-existing. +/// +/// If `BR` is true, the graph will store back-references, allowing you to get predecessors. +pub struct VecGraph<N: Idx, const BR: bool = false> { + // This is basically a `HashMap<N, (Vec<N>, If<BR, Vec<N>>)>` -- a map from a node index, to + // a list of targets of outgoing edges and (if enabled) a list of sources of incoming edges. + // + // However, it is condensed into two arrays as an optimization. + // + // `node_starts[n]` is the start of the list of targets of outgoing edges for node `n`. + // So you can get node's successors with `edge_targets[node_starts[n]..node_starts[n + 1]]`. + // + // If `BR` is true (back references are enabled), then `node_starts[n + edge_count]` is the + // start of the list of *sources* of incoming edges. You can get predecessors of a node + // similarly to its successors but offsetting by `edge_count`. `edge_count` is + // `edge_targets.len()/2` (again, in case BR is true) because half of the vec is back refs. + // + // All of this might be confusing, so here is an example graph and its representation: + // + // n3 ----+ + // ^ | (if BR = true) + // | v outgoing edges incoming edges + // n0 -> n1 -> n2 ______________ __________________ + // / \ / \ + // node indices[1]: n0, n1, n2, n3, n0, n1, n2, n3, n/a + // vec indices: n0, n1, n2, n3, n4, n5, n6, n7, n8 + // node_starts: [0, 1, 3, 4 4, 4, 5, 7, 8] + // | | | | | | | | | + // | | +---+ +---+ | +---+ | + // | | | | | | | + // v v v v v v v + // edge_targets: [n1, n2, n3, n2 n0, n1, n3, n1] + // / \____/ | | \____/ \ + // n0->n1 / | | \ n3<-n1 + // / n3->n2 [2] n1<-n0 [2] \ + // n1->n2, n1->n3 n2<-n1, n2<-n3 + // + // The incoming edges are basically stored in the same way as outgoing edges, but offset and + // the graph they store is the inverse of the original. Last index in the `node_starts` array + // always points to one-past-the-end, so that we don't need to bound check `node_starts[n + 1]` + // + // [1]: "node indices" are the indices a user of `VecGraph` might use, + // note that they are different from "vec indices", + // which are the real indices you need to index `node_starts` + // + // [2]: Note that even though n2 also points to here, + // the next index also points here, so n2 has no + // successors (`edge_targets[3..3] = []`). + // Similarly with n0 and incoming edges + // + // If this is still confusing... then sorry :( + // + /// Indices into `edge_targets` that signify a start of list of edges. node_starts: IndexVec<N, usize>, + /// Targets (or sources for back refs) of edges edge_targets: Vec<N>, } -impl<N: Idx + Ord> VecGraph<N> { +impl<N: Idx + Ord, const BR: bool> VecGraph<N, BR> { pub fn new(num_nodes: usize, mut edge_pairs: Vec<(N, N)>) -> Self { + let num_edges = edge_pairs.len(); + + let nodes_cap = match BR { + // +1 for special entry at the end, pointing one past the end of `edge_targets` + false => num_nodes + 1, + // *2 for back references + true => (num_nodes * 2) + 1, + }; + + let edges_cap = match BR { + false => num_edges, + // *2 for back references + true => num_edges * 2, + }; + + let mut node_starts = IndexVec::with_capacity(nodes_cap); + let mut edge_targets = Vec::with_capacity(edges_cap); + // Sort the edges by the source -- this is important. edge_pairs.sort(); - let num_edges = edge_pairs.len(); + // Fill forward references + create_index( + num_nodes, + &mut edge_pairs.iter().map(|&(src, _)| src), + &mut edge_pairs.iter().map(|&(_, tgt)| tgt), + &mut edge_targets, + &mut node_starts, + ); - // Store the *target* of each edge into `edge_targets`. - let edge_targets: Vec<N> = edge_pairs.iter().map(|&(_, target)| target).collect(); - - // Create the *edge starts* array. We are iterating over the - // (sorted) edge pairs. We maintain the invariant that the - // length of the `node_starts` array is enough to store the - // current source node -- so when we see that the source node - // for an edge is greater than the current length, we grow the - // edge-starts array by just enough. - let mut node_starts = IndexVec::with_capacity(num_edges); - for (index, &(source, _)) in edge_pairs.iter().enumerate() { - // If we have a list like `[(0, x), (2, y)]`: - // - // - Start out with `node_starts` of `[]` - // - Iterate to `(0, x)` at index 0: - // - Push one entry because `node_starts.len()` (0) is <= the source (0) - // - Leaving us with `node_starts` of `[0]` - // - Iterate to `(2, y)` at index 1: - // - Push one entry because `node_starts.len()` (1) is <= the source (2) - // - Push one entry because `node_starts.len()` (2) is <= the source (2) - // - Leaving us with `node_starts` of `[0, 1, 1]` - // - Loop terminates - while node_starts.len() <= source.index() { - node_starts.push(index); - } - } + // Fill back references + if BR { + // Pop the special "last" entry, it will be replaced by first back ref + node_starts.pop(); - // Pad out the `node_starts` array so that it has `num_nodes + - // 1` entries. Continuing our example above, if `num_nodes` is - // be `3`, we would push one more index: `[0, 1, 1, 2]`. - // - // Interpretation of that vector: - // - // [0, 1, 1, 2] - // ---- range for N=2 - // ---- range for N=1 - // ---- range for N=0 - while node_starts.len() <= num_nodes { - node_starts.push(edge_targets.len()); - } + // Re-sort the edges so that they are sorted by target + edge_pairs.sort_by_key(|&(src, tgt)| (tgt, src)); - assert_eq!(node_starts.len(), num_nodes + 1); + create_index( + // Back essentially double the number of nodes + num_nodes * 2, + // NB: the source/target are switched here too + // NB: we double the key index, so that we can later use *2 to get the back references + &mut edge_pairs.iter().map(|&(_, tgt)| N::new(tgt.index() + num_nodes)), + &mut edge_pairs.iter().map(|&(src, _)| src), + &mut edge_targets, + &mut node_starts, + ); + } Self { node_starts, edge_targets } } /// Gets the successors for `source` as a slice. pub fn successors(&self, source: N) -> &[N] { + assert!(source.index() < self.num_nodes()); + let start_index = self.node_starts[source]; let end_index = self.node_starts[source.plus(1)]; &self.edge_targets[start_index..end_index] } } -impl<N: Idx> DirectedGraph for VecGraph<N> { +impl<N: Idx + Ord> VecGraph<N, true> { + /// Gets the predecessors for `target` as a slice. + pub fn predecessors(&self, target: N) -> &[N] { + assert!(target.index() < self.num_nodes()); + + let target = N::new(target.index() + self.num_nodes()); + + let start_index = self.node_starts[target]; + let end_index = self.node_starts[target.plus(1)]; + &self.edge_targets[start_index..end_index] + } +} + +/// Creates/initializes the index for the [`VecGraph`]. A helper for [`VecGraph::new`]. +/// +/// - `num_nodes` is the target number of nodes in the graph +/// - `sorted_edge_sources` are the edge sources, sorted +/// - `associated_edge_targets` are the edge *targets* in the same order as sources +/// - `edge_targets` is the vec of targets to be extended +/// - `node_starts` is the index to be filled +fn create_index<N: Idx + Ord>( + num_nodes: usize, + sorted_edge_sources: &mut dyn Iterator<Item = N>, + associated_edge_targets: &mut dyn Iterator<Item = N>, + edge_targets: &mut Vec<N>, + node_starts: &mut IndexVec<N, usize>, +) { + let offset = edge_targets.len(); + + // Store the *target* of each edge into `edge_targets`. + edge_targets.extend(associated_edge_targets); + + // Create the *edge starts* array. We are iterating over the + // (sorted) edge pairs. We maintain the invariant that the + // length of the `node_starts` array is enough to store the + // current source node -- so when we see that the source node + // for an edge is greater than the current length, we grow the + // edge-starts array by just enough. + for (index, source) in sorted_edge_sources.enumerate() { + // If we have a list like `[(0, x), (2, y)]`: + // + // - Start out with `node_starts` of `[]` + // - Iterate to `(0, x)` at index 0: + // - Push one entry because `node_starts.len()` (0) is <= the source (0) + // - Leaving us with `node_starts` of `[0]` + // - Iterate to `(2, y)` at index 1: + // - Push one entry because `node_starts.len()` (1) is <= the source (2) + // - Push one entry because `node_starts.len()` (2) is <= the source (2) + // - Leaving us with `node_starts` of `[0, 1, 1]` + // - Loop terminates + while node_starts.len() <= source.index() { + node_starts.push(index + offset); + } + } + + // Pad out the `node_starts` array so that it has `num_nodes + + // 1` entries. Continuing our example above, if `num_nodes` is + // be `3`, we would push one more index: `[0, 1, 1, 2]`. + // + // Interpretation of that vector: + // + // [0, 1, 1, 2] + // ---- range for N=2 + // ---- range for N=1 + // ---- range for N=0 + while node_starts.len() <= num_nodes { + node_starts.push(edge_targets.len()); + } + + assert_eq!(node_starts.len(), num_nodes + 1); +} + +impl<N: Idx, const BR: bool> DirectedGraph for VecGraph<N, BR> { type Node = N; fn num_nodes(&self) -> usize { - self.node_starts.len() - 1 + match BR { + false => self.node_starts.len() - 1, + // If back refs are enabled, half of the array is said back refs + true => (self.node_starts.len() - 1) / 2, + } } } -impl<N: Idx> NumEdges for VecGraph<N> { +impl<N: Idx, const BR: bool> NumEdges for VecGraph<N, BR> { fn num_edges(&self) -> usize { - self.edge_targets.len() + match BR { + false => self.edge_targets.len(), + // If back refs are enabled, half of the array is reversed edges for them + true => self.edge_targets.len() / 2, + } } } -impl<N: Idx + Ord> Successors for VecGraph<N> { +impl<N: Idx + Ord, const BR: bool> Successors for VecGraph<N, BR> { fn successors(&self, node: N) -> impl Iterator<Item = Self::Node> { self.successors(node).iter().cloned() } } + +impl<N: Idx + Ord> Predecessors for VecGraph<N, true> { + fn predecessors(&self, node: Self::Node) -> impl Iterator<Item = Self::Node> { + self.predecessors(node).iter().cloned() + } +} diff --git a/compiler/rustc_data_structures/src/graph/vec_graph/tests.rs b/compiler/rustc_data_structures/src/graph/vec_graph/tests.rs index 87c8d25f094..a077d9d0813 100644 --- a/compiler/rustc_data_structures/src/graph/vec_graph/tests.rs +++ b/compiler/rustc_data_structures/src/graph/vec_graph/tests.rs @@ -18,10 +18,18 @@ fn create_graph() -> VecGraph<usize> { VecGraph::new(7, vec![(0, 1), (1, 2), (1, 3), (3, 4), (5, 1)]) } +fn create_graph_with_back_refs() -> VecGraph<usize, true> { + // Same as above + VecGraph::new(7, vec![(0, 1), (1, 2), (1, 3), (3, 4), (5, 1)]) +} + #[test] fn num_nodes() { let graph = create_graph(); assert_eq!(graph.num_nodes(), 7); + + let graph = create_graph_with_back_refs(); + assert_eq!(graph.num_nodes(), 7); } #[test] @@ -34,6 +42,27 @@ fn successors() { assert_eq!(graph.successors(4), &[] as &[usize]); assert_eq!(graph.successors(5), &[1]); assert_eq!(graph.successors(6), &[] as &[usize]); + + let graph = create_graph_with_back_refs(); + assert_eq!(graph.successors(0), &[1]); + assert_eq!(graph.successors(1), &[2, 3]); + assert_eq!(graph.successors(2), &[] as &[usize]); + assert_eq!(graph.successors(3), &[4]); + assert_eq!(graph.successors(4), &[] as &[usize]); + assert_eq!(graph.successors(5), &[1]); + assert_eq!(graph.successors(6), &[] as &[usize]); +} + +#[test] +fn predecessors() { + let graph = create_graph_with_back_refs(); + assert_eq!(graph.predecessors(0), &[]); + assert_eq!(graph.predecessors(1), &[0, 5]); + assert_eq!(graph.predecessors(2), &[1]); + assert_eq!(graph.predecessors(3), &[1]); + assert_eq!(graph.predecessors(4), &[3]); + assert_eq!(graph.predecessors(5), &[]); + assert_eq!(graph.predecessors(6), &[]); } #[test] @@ -41,4 +70,8 @@ fn dfs() { let graph = create_graph(); let dfs: Vec<_> = graph::depth_first_search(&graph, 0).collect(); assert_eq!(dfs, vec![0, 1, 3, 4, 2]); + + let graph = create_graph_with_back_refs(); + let dfs: Vec<_> = graph::depth_first_search(&graph, 0).collect(); + assert_eq!(dfs, vec![0, 1, 3, 4, 2]); } diff --git a/compiler/rustc_data_structures/src/lib.rs b/compiler/rustc_data_structures/src/lib.rs index b82a9a909e6..9781aae22eb 100644 --- a/compiler/rustc_data_structures/src/lib.rs +++ b/compiler/rustc_data_structures/src/lib.rs @@ -16,16 +16,17 @@ #![doc(rust_logo)] #![feature(allocator_api)] #![feature(array_windows)] +#![feature(ascii_char)] +#![feature(ascii_char_variants)] #![feature(auto_traits)] #![feature(cfg_match)] #![feature(core_intrinsics)] #![feature(extend_one)] -#![feature(generic_nonzero)] #![feature(hash_raw_entry)] #![feature(hasher_prefixfree_extras)] -#![feature(lazy_cell)] #![feature(lint_reasons)] #![feature(macro_metavar_expr)] +#![feature(map_try_insert)] #![feature(maybe_uninit_uninit_array)] #![feature(min_specialization)] #![feature(negative_impls)] @@ -40,68 +41,59 @@ #![feature(unwrap_infallible)] // tidy-alphabetical-end -#[macro_use] -extern crate tracing; -#[macro_use] -extern crate rustc_macros; - -use std::fmt; - +pub use atomic_ref::AtomicRef; +pub use ena::snapshot_vec; +pub use ena::undo_log; +pub use ena::unify; pub use rustc_index::static_assert_size; -/// This calls the passed function while ensuring it won't be inlined into the caller. -#[inline(never)] -#[cold] -pub fn outline<F: FnOnce() -> R, R>(f: F) -> R { - f() -} +use std::fmt; +pub mod aligned; pub mod base_n; pub mod binary_search_util; pub mod captures; +pub mod fingerprint; pub mod flat_map_in_place; pub mod flock; +pub mod frozen; pub mod fx; pub mod graph; pub mod intern; pub mod jobserver; -pub mod macros; +pub mod marker; +pub mod memmap; pub mod obligation_forest; +pub mod owned_slice; +pub mod packed; +pub mod profiling; +pub mod sharded; pub mod sip128; pub mod small_c_str; pub mod snapshot_map; -pub mod svh; -pub use ena::snapshot_vec; -pub mod memmap; pub mod sorted_map; -#[macro_use] +pub mod sso; pub mod stable_hasher; -mod atomic_ref; -pub mod fingerprint; -pub mod marker; -pub mod profiling; -pub mod sharded; pub mod stack; -pub mod sync; -pub mod tiny_list; -pub mod transitive_relation; -pub mod vec_linked_list; -pub mod work_queue; -pub use atomic_ref::AtomicRef; -pub mod aligned; -pub mod frozen; -mod hashes; -pub mod owned_slice; -pub mod packed; -pub mod sso; pub mod steal; +pub mod svh; +pub mod sync; pub mod tagged_ptr; pub mod temp_dir; +pub mod transitive_relation; pub mod unhash; pub mod unord; +pub mod work_queue; -pub use ena::undo_log; -pub use ena::unify; +mod atomic_ref; +mod hashes; + +/// This calls the passed function while ensuring it won't be inlined into the caller. +#[inline(never)] +#[cold] +pub fn outline<F: FnOnce() -> R, R>(f: F) -> R { + f() +} /// Returns a structure that calls `f` when dropped. pub fn defer<F: FnOnce()>(f: F) -> OnDrop<F> { @@ -147,9 +139,9 @@ pub fn make_display(f: impl Fn(&mut fmt::Formatter<'_>) -> fmt::Result) -> impl Printer { f } } -// See comments in compiler/rustc_middle/src/tests.rs +// See comment in compiler/rustc_middle/src/tests.rs and issue #27438. #[doc(hidden)] -pub fn __noop_fix_for_27438() {} +pub fn __noop_fix_for_windows_dllimport_issue() {} #[macro_export] macro_rules! external_bitflags_debug { diff --git a/compiler/rustc_data_structures/src/macros.rs b/compiler/rustc_data_structures/src/macros.rs deleted file mode 100644 index e05491f6ff6..00000000000 --- a/compiler/rustc_data_structures/src/macros.rs +++ /dev/null @@ -1,37 +0,0 @@ -#[macro_export] -macro_rules! enum_from_u32 { - ($(#[$attr:meta])* pub enum $name:ident { - $($(#[$var_attr:meta])* $variant:ident = $e:expr,)* - }) => { - $(#[$attr])* - pub enum $name { - $($(#[$var_attr])* $variant = $e),* - } - - impl $name { - pub fn from_u32(u: u32) -> Option<$name> { - $(if u == $name::$variant as u32 { - return Some($name::$variant) - })* - None - } - } - }; - ($(#[$attr:meta])* pub enum $name:ident { - $($(#[$var_attr:meta])* $variant:ident,)* - }) => { - $(#[$attr])* - pub enum $name { - $($(#[$var_attr])* $variant,)* - } - - impl $name { - pub fn from_u32(u: u32) -> Option<$name> { - $(if u == $name::$variant as u32 { - return Some($name::$variant) - })* - None - } - } - } -} diff --git a/compiler/rustc_data_structures/src/obligation_forest/mod.rs b/compiler/rustc_data_structures/src/obligation_forest/mod.rs index a47908648ba..d477b86da74 100644 --- a/compiler/rustc_data_structures/src/obligation_forest/mod.rs +++ b/compiler/rustc_data_structures/src/obligation_forest/mod.rs @@ -70,12 +70,12 @@ //! aren't needed anymore. use crate::fx::{FxHashMap, FxHashSet}; - use std::cell::Cell; use std::collections::hash_map::Entry; use std::fmt::Debug; use std::hash; use std::marker::PhantomData; +use tracing::debug; mod graphviz; diff --git a/compiler/rustc_data_structures/src/packed.rs b/compiler/rustc_data_structures/src/packed.rs index b8d4b295dfa..0a392d91988 100644 --- a/compiler/rustc_data_structures/src/packed.rs +++ b/compiler/rustc_data_structures/src/packed.rs @@ -3,8 +3,10 @@ use rustc_serialize::{Decodable, Decoder, Encodable, Encoder}; use std::cmp::Ordering; use std::fmt; -#[repr(packed(8))] +/// A packed 128-bit integer. Useful for reducing the size of structures in +/// some cases. #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq, PartialOrd, Ord)] +#[repr(packed(8))] pub struct Pu128(pub u128); impl Pu128 { diff --git a/compiler/rustc_data_structures/src/profiling.rs b/compiler/rustc_data_structures/src/profiling.rs index 2569684df3f..c6d51a5d6b4 100644 --- a/compiler/rustc_data_structures/src/profiling.rs +++ b/compiler/rustc_data_structures/src/profiling.rs @@ -99,6 +99,7 @@ pub use measureme::EventId; use measureme::{EventIdBuilder, Profiler, SerializableString, StringId}; use parking_lot::RwLock; use smallvec::SmallVec; +use tracing::warn; bitflags::bitflags! { #[derive(Clone, Copy)] diff --git a/compiler/rustc_data_structures/src/sorted_map.rs b/compiler/rustc_data_structures/src/sorted_map.rs index 1436628139f..21d7c91ec48 100644 --- a/compiler/rustc_data_structures/src/sorted_map.rs +++ b/compiler/rustc_data_structures/src/sorted_map.rs @@ -1,4 +1,5 @@ use crate::stable_hasher::{HashStable, StableHasher, StableOrd}; +use rustc_macros::{Decodable_Generic, Encodable_Generic}; use std::borrow::Borrow; use std::fmt::Debug; use std::mem; diff --git a/compiler/rustc_data_structures/src/stable_hasher.rs b/compiler/rustc_data_structures/src/stable_hasher.rs index 8418b4bbd47..b5bdf2e1790 100644 --- a/compiler/rustc_data_structures/src/stable_hasher.rs +++ b/compiler/rustc_data_structures/src/stable_hasher.rs @@ -296,6 +296,8 @@ macro_rules! impl_stable_traits_for_trivial_type { }; } +pub(crate) use impl_stable_traits_for_trivial_type; + impl_stable_traits_for_trivial_type!(i8); impl_stable_traits_for_trivial_type!(i16); impl_stable_traits_for_trivial_type!(i32); diff --git a/compiler/rustc_data_structures/src/svh.rs b/compiler/rustc_data_structures/src/svh.rs index 1cfc9fecd47..38629ea9801 100644 --- a/compiler/rustc_data_structures/src/svh.rs +++ b/compiler/rustc_data_structures/src/svh.rs @@ -6,9 +6,9 @@ //! compiled from distinct sources. use crate::fingerprint::Fingerprint; -use std::fmt; - use crate::stable_hasher; +use rustc_macros::{Decodable_Generic, Encodable_Generic}; +use std::fmt; #[derive(Copy, Clone, PartialEq, Eq, Debug, Encodable_Generic, Decodable_Generic, Hash)] pub struct Svh { diff --git a/compiler/rustc_data_structures/src/sync.rs b/compiler/rustc_data_structures/src/sync.rs index eab6d8168ca..ecb85db33f7 100644 --- a/compiler/rustc_data_structures/src/sync.rs +++ b/compiler/rustc_data_structures/src/sync.rs @@ -46,6 +46,7 @@ use std::collections::HashMap; use std::hash::{BuildHasher, Hash}; mod lock; +#[doc(no_inline)] pub use lock::{Lock, LockGuard, Mode}; mod worker_local; @@ -199,10 +200,15 @@ cfg_match! { pub use std::rc::Rc as Lrc; pub use std::rc::Weak as Weak; + #[doc(no_inline)] pub use std::cell::Ref as ReadGuard; + #[doc(no_inline)] pub use std::cell::Ref as MappedReadGuard; + #[doc(no_inline)] pub use std::cell::RefMut as WriteGuard; + #[doc(no_inline)] pub use std::cell::RefMut as MappedWriteGuard; + #[doc(no_inline)] pub use std::cell::RefMut as MappedLockGuard; pub use std::cell::OnceCell as OnceLock; diff --git a/compiler/rustc_data_structures/src/tiny_list.rs b/compiler/rustc_data_structures/src/tiny_list.rs deleted file mode 100644 index 11a408f216a..00000000000 --- a/compiler/rustc_data_structures/src/tiny_list.rs +++ /dev/null @@ -1,80 +0,0 @@ -//! A singly-linked list. -//! -//! Using this data structure only makes sense under very specific -//! circumstances: -//! -//! - If you have a list that rarely stores more than one element, then this -//! data-structure can store the element without allocating and only uses as -//! much space as an `Option<(T, usize)>`. If T can double as the `Option` -//! discriminant, it will even only be as large as `T, usize`. -//! -//! If you expect to store more than 1 element in the common case, steer clear -//! and use a `Vec<T>`, `Box<[T]>`, or a `SmallVec<T>`. - -#[cfg(test)] -mod tests; - -#[derive(Clone)] -pub struct TinyList<T> { - head: Option<Element<T>>, -} - -impl<T: PartialEq> TinyList<T> { - #[inline] - pub fn new() -> TinyList<T> { - TinyList { head: None } - } - - #[inline] - pub fn new_single(data: T) -> TinyList<T> { - TinyList { head: Some(Element { data, next: None }) } - } - - #[inline] - pub fn insert(&mut self, data: T) { - self.head = Some(Element { data, next: self.head.take().map(Box::new) }); - } - - #[inline] - pub fn remove(&mut self, data: &T) -> bool { - self.head = match &mut self.head { - Some(head) if head.data == *data => head.next.take().map(|x| *x), - Some(head) => return head.remove_next(data), - None => return false, - }; - true - } - - #[inline] - pub fn contains(&self, data: &T) -> bool { - let mut elem = self.head.as_ref(); - while let Some(e) = elem { - if &e.data == data { - return true; - } - elem = e.next.as_deref(); - } - false - } -} - -#[derive(Clone)] -struct Element<T> { - data: T, - next: Option<Box<Element<T>>>, -} - -impl<T: PartialEq> Element<T> { - fn remove_next(mut self: &mut Self, data: &T) -> bool { - loop { - match self.next { - Some(ref mut next) if next.data == *data => { - self.next = next.next.take(); - return true; - } - Some(ref mut next) => self = next, - None => return false, - } - } - } -} diff --git a/compiler/rustc_data_structures/src/tiny_list/tests.rs b/compiler/rustc_data_structures/src/tiny_list/tests.rs deleted file mode 100644 index 4b95e62bef0..00000000000 --- a/compiler/rustc_data_structures/src/tiny_list/tests.rs +++ /dev/null @@ -1,155 +0,0 @@ -use super::*; - -extern crate test; -use test::{black_box, Bencher}; - -impl<T> TinyList<T> { - fn len(&self) -> usize { - let (mut elem, mut count) = (self.head.as_ref(), 0); - while let Some(e) = elem { - count += 1; - elem = e.next.as_deref(); - } - count - } -} - -#[test] -fn test_contains_and_insert() { - fn do_insert(i: u32) -> bool { - i % 2 == 0 - } - - let mut list = TinyList::new(); - - for i in 0..10 { - for j in 0..i { - if do_insert(j) { - assert!(list.contains(&j)); - } else { - assert!(!list.contains(&j)); - } - } - - assert!(!list.contains(&i)); - - if do_insert(i) { - list.insert(i); - assert!(list.contains(&i)); - } - } -} - -#[test] -fn test_remove_first() { - let mut list = TinyList::new(); - list.insert(1); - list.insert(2); - list.insert(3); - list.insert(4); - assert_eq!(list.len(), 4); - - assert!(list.remove(&4)); - assert!(!list.contains(&4)); - - assert_eq!(list.len(), 3); - assert!(list.contains(&1)); - assert!(list.contains(&2)); - assert!(list.contains(&3)); -} - -#[test] -fn test_remove_last() { - let mut list = TinyList::new(); - list.insert(1); - list.insert(2); - list.insert(3); - list.insert(4); - assert_eq!(list.len(), 4); - - assert!(list.remove(&1)); - assert!(!list.contains(&1)); - - assert_eq!(list.len(), 3); - assert!(list.contains(&2)); - assert!(list.contains(&3)); - assert!(list.contains(&4)); -} - -#[test] -fn test_remove_middle() { - let mut list = TinyList::new(); - list.insert(1); - list.insert(2); - list.insert(3); - list.insert(4); - assert_eq!(list.len(), 4); - - assert!(list.remove(&2)); - assert!(!list.contains(&2)); - - assert_eq!(list.len(), 3); - assert!(list.contains(&1)); - assert!(list.contains(&3)); - assert!(list.contains(&4)); -} - -#[test] -fn test_remove_single() { - let mut list = TinyList::new(); - list.insert(1); - assert_eq!(list.len(), 1); - - assert!(list.remove(&1)); - assert!(!list.contains(&1)); - - assert_eq!(list.len(), 0); -} - -#[bench] -fn bench_insert_empty(b: &mut Bencher) { - b.iter(|| { - let mut list = black_box(TinyList::new()); - list.insert(1); - list - }) -} - -#[bench] -fn bench_insert_one(b: &mut Bencher) { - b.iter(|| { - let mut list = black_box(TinyList::new_single(0)); - list.insert(1); - list - }) -} - -#[bench] -fn bench_contains_empty(b: &mut Bencher) { - b.iter(|| black_box(TinyList::new()).contains(&1)); -} - -#[bench] -fn bench_contains_unknown(b: &mut Bencher) { - b.iter(|| black_box(TinyList::new_single(0)).contains(&1)); -} - -#[bench] -fn bench_contains_one(b: &mut Bencher) { - b.iter(|| black_box(TinyList::new_single(1)).contains(&1)); -} - -#[bench] -fn bench_remove_empty(b: &mut Bencher) { - b.iter(|| black_box(TinyList::new()).remove(&1)); -} - -#[bench] -fn bench_remove_unknown(b: &mut Bencher) { - b.iter(|| black_box(TinyList::new_single(0)).remove(&1)); -} - -#[bench] -fn bench_remove_one(b: &mut Bencher) { - b.iter(|| black_box(TinyList::new_single(1)).remove(&1)); -} diff --git a/compiler/rustc_data_structures/src/unord.rs b/compiler/rustc_data_structures/src/unord.rs index a99e2062039..1ccd22a56c9 100644 --- a/compiler/rustc_data_structures/src/unord.rs +++ b/compiler/rustc_data_structures/src/unord.rs @@ -3,6 +3,8 @@ //! as required by the query system. use rustc_hash::{FxHashMap, FxHashSet}; +use rustc_macros::{Decodable_Generic, Encodable_Generic}; +use std::collections::hash_map::OccupiedError; use std::{ borrow::{Borrow, BorrowMut}, collections::hash_map::Entry, @@ -469,6 +471,11 @@ impl<K: Eq + Hash, V> UnordMap<K, V> { } #[inline] + pub fn try_insert(&mut self, k: K, v: V) -> Result<&mut V, OccupiedError<'_, K, V>> { + self.inner.try_insert(k, v) + } + + #[inline] pub fn contains_key<Q: ?Sized>(&self, k: &Q) -> bool where K: Borrow<Q>, diff --git a/compiler/rustc_data_structures/src/vec_linked_list.rs b/compiler/rustc_data_structures/src/vec_linked_list.rs deleted file mode 100644 index fda72c9a3b2..00000000000 --- a/compiler/rustc_data_structures/src/vec_linked_list.rs +++ /dev/null @@ -1,70 +0,0 @@ -use rustc_index::{Idx, IndexVec}; - -pub fn iter<Ls>( - first: Option<Ls::LinkIndex>, - links: &Ls, -) -> impl Iterator<Item = Ls::LinkIndex> + '_ -where - Ls: Links, -{ - VecLinkedListIterator { links, current: first } -} - -pub struct VecLinkedListIterator<Ls> -where - Ls: Links, -{ - links: Ls, - current: Option<Ls::LinkIndex>, -} - -impl<Ls> Iterator for VecLinkedListIterator<Ls> -where - Ls: Links, -{ - type Item = Ls::LinkIndex; - - fn next(&mut self) -> Option<Ls::LinkIndex> { - if let Some(c) = self.current { - self.current = <Ls as Links>::next(&self.links, c); - Some(c) - } else { - None - } - } -} - -pub trait Links { - type LinkIndex: Copy; - - fn next(links: &Self, index: Self::LinkIndex) -> Option<Self::LinkIndex>; -} - -impl<Ls> Links for &Ls -where - Ls: Links, -{ - type LinkIndex = Ls::LinkIndex; - - fn next(links: &Self, index: Ls::LinkIndex) -> Option<Ls::LinkIndex> { - <Ls as Links>::next(links, index) - } -} - -pub trait LinkElem { - type LinkIndex: Copy; - - fn next(elem: &Self) -> Option<Self::LinkIndex>; -} - -impl<L, E> Links for IndexVec<L, E> -where - E: LinkElem<LinkIndex = L>, - L: Idx, -{ - type LinkIndex = L; - - fn next(links: &Self, index: L) -> Option<L> { - <E as LinkElem>::next(&links[index]) - } -} |