diff options
Diffstat (limited to 'compiler/rustc_data_structures')
16 files changed, 178 insertions, 111 deletions
diff --git a/compiler/rustc_data_structures/Cargo.toml b/compiler/rustc_data_structures/Cargo.toml index 889a8299c18..a8f83ca13e2 100644 --- a/compiler/rustc_data_structures/Cargo.toml +++ b/compiler/rustc_data_structures/Cargo.toml @@ -8,13 +8,13 @@ edition = "2021" arrayvec = { version = "0.7", default-features = false } bitflags = "2.4.1" either = "1.0" -elsa = "=1.7.1" +elsa = "1.11.0" ena = "0.14.3" -indexmap = { version = "2.4.0", features = ["rustc-rayon"] } +indexmap = "2.4.0" jobserver_crate = { version = "0.1.28", package = "jobserver" } measureme = "11" rustc-hash = "2.0.0" -rustc-rayon = "0.5.0" +rustc-rayon = { version = "0.5.1", features = ["indexmap"] } rustc-stable-hash = { version = "0.1.0", features = ["nightly"] } rustc_arena = { path = "../rustc_arena" } rustc_graphviz = { path = "../rustc_graphviz" } diff --git a/compiler/rustc_data_structures/src/graph/dominators/tests.rs b/compiler/rustc_data_structures/src/graph/dominators/tests.rs index ef82193a4b9..6c078ca7c6e 100644 --- a/compiler/rustc_data_structures/src/graph/dominators/tests.rs +++ b/compiler/rustc_data_structures/src/graph/dominators/tests.rs @@ -15,17 +15,10 @@ fn diamond() { #[test] fn paper() { // example from the paper: - let graph = TestGraph::new(6, &[ - (6, 5), - (6, 4), - (5, 1), - (4, 2), - (4, 3), - (1, 2), - (2, 3), - (3, 2), - (2, 1), - ]); + let graph = TestGraph::new( + 6, + &[(6, 5), (6, 4), (5, 1), (4, 2), (4, 3), (1, 2), (2, 3), (3, 2), (2, 1)], + ); let d = dominators(&graph); assert_eq!(d.immediate_dominator(0), None); // <-- note that 0 is not in graph @@ -40,19 +33,10 @@ fn paper() { #[test] fn paper_slt() { // example from the paper: - let graph = TestGraph::new(1, &[ - (1, 2), - (1, 3), - (2, 3), - (2, 7), - (3, 4), - (3, 6), - (4, 5), - (5, 4), - (6, 7), - (7, 8), - (8, 5), - ]); + let graph = TestGraph::new( + 1, + &[(1, 2), (1, 3), (2, 3), (2, 7), (3, 4), (3, 6), (4, 5), (5, 4), (6, 7), (7, 8), (8, 5)], + ); dominators(&graph); } @@ -69,21 +53,24 @@ fn immediate_dominator() { #[test] fn transitive_dominator() { - let graph = TestGraph::new(0, &[ - // First tree branch. - (0, 1), - (1, 2), - (2, 3), - (3, 4), - // Second tree branch. - (1, 5), - (5, 6), - // Third tree branch. - (0, 7), - // These links make 0 the dominator for 2 and 3. - (7, 2), - (5, 3), - ]); + let graph = TestGraph::new( + 0, + &[ + // First tree branch. + (0, 1), + (1, 2), + (2, 3), + (3, 4), + // Second tree branch. + (1, 5), + (5, 6), + // Third tree branch. + (0, 7), + // These links make 0 the dominator for 2 and 3. + (7, 2), + (5, 3), + ], + ); let d = dominators(&graph); assert_eq!(d.immediate_dominator(2), Some(0)); diff --git a/compiler/rustc_data_structures/src/graph/implementation/tests.rs b/compiler/rustc_data_structures/src/graph/implementation/tests.rs index 7a240f4e58b..32a6d9ec881 100644 --- a/compiler/rustc_data_structures/src/graph/implementation/tests.rs +++ b/compiler/rustc_data_structures/src/graph/implementation/tests.rs @@ -110,10 +110,13 @@ fn each_adjacent_from_a() { #[test] fn each_adjacent_from_b() { let graph = create_graph(); - test_adjacent_edges(&graph, NodeIndex(1), "B", &[("FB", "F"), ("AB", "A")], &[ - ("BD", "D"), - ("BC", "C"), - ]); + test_adjacent_edges( + &graph, + NodeIndex(1), + "B", + &[("FB", "F"), ("AB", "A")], + &[("BD", "D"), ("BC", "C")], + ); } #[test] diff --git a/compiler/rustc_data_structures/src/graph/mod.rs b/compiler/rustc_data_structures/src/graph/mod.rs index 92035e8bc48..4a1e5db6768 100644 --- a/compiler/rustc_data_structures/src/graph/mod.rs +++ b/compiler/rustc_data_structures/src/graph/mod.rs @@ -14,7 +14,23 @@ mod tests; pub trait DirectedGraph { type Node: Idx; + /// Returns the total number of nodes in this graph. + /// + /// Several graph algorithm implementations assume that every node ID is + /// strictly less than the number of nodes, i.e. nodes are densely numbered. + /// That assumption allows them to use `num_nodes` to allocate per-node + /// data structures, indexed by node. fn num_nodes(&self) -> usize; + + /// Iterates over all nodes of a graph in ascending numeric order. + /// + /// Assumes that nodes are densely numbered, i.e. every index in + /// `0..num_nodes` is a valid node. + fn iter_nodes( + &self, + ) -> impl Iterator<Item = Self::Node> + DoubleEndedIterator + ExactSizeIterator { + (0..self.num_nodes()).map(<Self::Node as Idx>::new) + } } pub trait NumEdges: DirectedGraph { diff --git a/compiler/rustc_data_structures/src/graph/scc/mod.rs b/compiler/rustc_data_structures/src/graph/scc/mod.rs index 06fedef00fc..93f6192b10b 100644 --- a/compiler/rustc_data_structures/src/graph/scc/mod.rs +++ b/compiler/rustc_data_structures/src/graph/scc/mod.rs @@ -333,8 +333,8 @@ where to_annotation, }; - let scc_indices = (0..num_nodes) - .map(G::Node::new) + let scc_indices = graph + .iter_nodes() .map(|node| match this.start_walk_from(node) { WalkReturn::Complete { scc_index, .. } => scc_index, WalkReturn::Cycle { min_depth, .. } => { diff --git a/compiler/rustc_data_structures/src/graph/scc/tests.rs b/compiler/rustc_data_structures/src/graph/scc/tests.rs index 7c876c82af2..373f87bfdbc 100644 --- a/compiler/rustc_data_structures/src/graph/scc/tests.rs +++ b/compiler/rustc_data_structures/src/graph/scc/tests.rs @@ -326,46 +326,49 @@ fn test_bug_max_leak_minimised() { #[test] fn test_bug_max_leak() { - let graph = TestGraph::new(8, &[ - (0, 0), - (0, 18), - (0, 19), - (0, 1), - (0, 2), - (0, 7), - (0, 8), - (0, 23), - (18, 0), - (18, 12), - (19, 0), - (19, 25), - (12, 18), - (12, 3), - (12, 5), - (3, 12), - (3, 21), - (3, 22), - (5, 13), - (21, 3), - (22, 3), - (13, 5), - (13, 4), - (4, 13), - (4, 0), - (2, 11), - (7, 6), - (6, 20), - (20, 6), - (8, 17), - (17, 9), - (9, 16), - (16, 26), - (26, 15), - (15, 10), - (10, 14), - (14, 27), - (23, 24), - ]); + let graph = TestGraph::new( + 8, + &[ + (0, 0), + (0, 18), + (0, 19), + (0, 1), + (0, 2), + (0, 7), + (0, 8), + (0, 23), + (18, 0), + (18, 12), + (19, 0), + (19, 25), + (12, 18), + (12, 3), + (12, 5), + (3, 12), + (3, 21), + (3, 22), + (5, 13), + (21, 3), + (22, 3), + (13, 5), + (13, 4), + (4, 13), + (4, 0), + (2, 11), + (7, 6), + (6, 20), + (20, 6), + (8, 17), + (17, 9), + (9, 16), + (16, 26), + (26, 15), + (15, 10), + (10, 14), + (14, 27), + (23, 24), + ], + ); let sccs: MaxReachedSccs = Sccs::new_with_annotation(&graph, |w| match w { 22 => MaxReached(1), 24 => MaxReached(2), diff --git a/compiler/rustc_data_structures/src/lib.rs b/compiler/rustc_data_structures/src/lib.rs index 65d586124b3..6ef73debadd 100644 --- a/compiler/rustc_data_structures/src/lib.rs +++ b/compiler/rustc_data_structures/src/lib.rs @@ -76,6 +76,7 @@ pub mod sync; pub mod tagged_ptr; pub mod temp_dir; pub mod thinvec; +pub mod thousands; pub mod transitive_relation; pub mod unhash; pub mod unord; diff --git a/compiler/rustc_data_structures/src/memmap.rs b/compiler/rustc_data_structures/src/memmap.rs index c7f66b2fee8..d64a5862f4e 100644 --- a/compiler/rustc_data_structures/src/memmap.rs +++ b/compiler/rustc_data_structures/src/memmap.rs @@ -3,13 +3,13 @@ use std::io; use std::ops::{Deref, DerefMut}; /// A trivial wrapper for [`memmap2::Mmap`] (or `Vec<u8>` on WASM). -#[cfg(not(target_arch = "wasm32"))] +#[cfg(not(any(miri, target_arch = "wasm32")))] pub struct Mmap(memmap2::Mmap); -#[cfg(target_arch = "wasm32")] +#[cfg(any(miri, target_arch = "wasm32"))] pub struct Mmap(Vec<u8>); -#[cfg(not(target_arch = "wasm32"))] +#[cfg(not(any(miri, target_arch = "wasm32")))] impl Mmap { /// # Safety /// @@ -29,7 +29,7 @@ impl Mmap { } } -#[cfg(target_arch = "wasm32")] +#[cfg(any(miri, target_arch = "wasm32"))] impl Mmap { #[inline] pub unsafe fn map(mut file: File) -> io::Result<Self> { @@ -56,13 +56,13 @@ impl AsRef<[u8]> for Mmap { } } -#[cfg(not(target_arch = "wasm32"))] +#[cfg(not(any(miri, target_arch = "wasm32")))] pub struct MmapMut(memmap2::MmapMut); -#[cfg(target_arch = "wasm32")] +#[cfg(any(miri, target_arch = "wasm32"))] pub struct MmapMut(Vec<u8>); -#[cfg(not(target_arch = "wasm32"))] +#[cfg(not(any(miri, target_arch = "wasm32")))] impl MmapMut { #[inline] pub fn map_anon(len: usize) -> io::Result<Self> { @@ -82,7 +82,7 @@ impl MmapMut { } } -#[cfg(target_arch = "wasm32")] +#[cfg(any(miri, target_arch = "wasm32"))] impl MmapMut { #[inline] pub fn map_anon(len: usize) -> io::Result<Self> { diff --git a/compiler/rustc_data_structures/src/obligation_forest/tests.rs b/compiler/rustc_data_structures/src/obligation_forest/tests.rs index 739ef74e3f7..1916a8e2b6b 100644 --- a/compiler/rustc_data_structures/src/obligation_forest/tests.rs +++ b/compiler/rustc_data_structures/src/obligation_forest/tests.rs @@ -349,10 +349,10 @@ fn diamond() { )); assert_eq!(d_count, 1); assert_eq!(ok.len(), 0); - assert_eq!(err, vec![super::Error { - error: "operation failed", - backtrace: vec!["D'", "A'.1", "A'"] - }]); + assert_eq!( + err, + vec![super::Error { error: "operation failed", backtrace: vec!["D'", "A'.1", "A'"] }] + ); let errors = forest.to_errors(()); assert_eq!(errors.len(), 0); diff --git a/compiler/rustc_data_structures/src/owned_slice.rs b/compiler/rustc_data_structures/src/owned_slice.rs index c8be0ab52e9..17c48aee6fa 100644 --- a/compiler/rustc_data_structures/src/owned_slice.rs +++ b/compiler/rustc_data_structures/src/owned_slice.rs @@ -1,15 +1,15 @@ use std::borrow::Borrow; use std::ops::Deref; +use std::sync::Arc; // Use our fake Send/Sync traits when on not parallel compiler, // so that `OwnedSlice` only implements/requires Send/Sync // for parallel compiler builds. use crate::sync; -use crate::sync::Lrc; /// An owned slice. /// -/// This is similar to `Lrc<[u8]>` but allows slicing and using anything as the +/// This is similar to `Arc<[u8]>` but allows slicing and using anything as the /// backing buffer. /// /// See [`slice_owned`] for `OwnedSlice` construction and examples. @@ -34,7 +34,7 @@ pub struct OwnedSlice { // \/ // ⊂(´･◡･⊂ )∘˚˳° (I am the phantom remnant of #97770) #[expect(dead_code)] - owner: Lrc<dyn sync::Send + sync::Sync>, + owner: Arc<dyn sync::Send + sync::Sync>, } /// Makes an [`OwnedSlice`] out of an `owner` and a `slicer` function. @@ -86,7 +86,7 @@ where // N.B. the HRTB on the `slicer` is important — without it the caller could provide // a short lived slice, unrelated to the owner. - let owner = Lrc::new(owner); + let owner = Arc::new(owner); let bytes = slicer(&*owner)?; Ok(OwnedSlice { bytes, owner }) diff --git a/compiler/rustc_data_structures/src/stack.rs b/compiler/rustc_data_structures/src/stack.rs index 3d6d0003483..102b3640911 100644 --- a/compiler/rustc_data_structures/src/stack.rs +++ b/compiler/rustc_data_structures/src/stack.rs @@ -17,6 +17,18 @@ const STACK_PER_RECURSION: usize = 16 * 1024 * 1024; // 16MB /// /// Should not be sprinkled around carelessly, as it causes a little bit of overhead. #[inline] +#[cfg(not(miri))] pub fn ensure_sufficient_stack<R>(f: impl FnOnce() -> R) -> R { stacker::maybe_grow(RED_ZONE, STACK_PER_RECURSION, f) } + +/// Grows the stack on demand to prevent stack overflow. Call this in strategic locations +/// to "break up" recursive calls. E.g. almost any call to `visit_expr` or equivalent can benefit +/// from this. +/// +/// Should not be sprinkled around carelessly, as it causes a little bit of overhead. +#[cfg(miri)] +#[inline] +pub fn ensure_sufficient_stack<R>(f: impl FnOnce() -> R) -> R { + f() +} diff --git a/compiler/rustc_data_structures/src/sync.rs b/compiler/rustc_data_structures/src/sync.rs index 7a9533031f4..bea87a6685d 100644 --- a/compiler/rustc_data_structures/src/sync.rs +++ b/compiler/rustc_data_structures/src/sync.rs @@ -18,7 +18,6 @@ //! //! | Type | Serial version | Parallel version | //! | ----------------------- | ------------------- | ------------------------------- | -//! | `Lrc<T>` | `rc::Rc<T>` | `sync::Arc<T>` | //! |` Weak<T>` | `rc::Weak<T>` | `sync::Weak<T>` | //! | `LRef<'a, T>` [^2] | `&'a mut T` | `&'a T` | //! | | | | @@ -109,7 +108,7 @@ pub use std::marker::{Send, Sync}; #[cfg(target_has_atomic = "64")] pub use std::sync::atomic::AtomicU64; pub use std::sync::atomic::{AtomicBool, AtomicU32, AtomicUsize}; -pub use std::sync::{Arc as Lrc, OnceLock, Weak}; +pub use std::sync::{OnceLock, Weak}; pub use mode::{is_dyn_thread_safe, set_dyn_thread_safe_mode}; pub use parking_lot::{ diff --git a/compiler/rustc_data_structures/src/thousands/mod.rs b/compiler/rustc_data_structures/src/thousands/mod.rs new file mode 100644 index 00000000000..e7ab7ec2932 --- /dev/null +++ b/compiler/rustc_data_structures/src/thousands/mod.rs @@ -0,0 +1,16 @@ +//! This is an extremely bare-bones alternative to the `thousands` crate on +//! crates.io, for printing large numbers in a readable fashion. + +#[cfg(test)] +mod tests; + +// Converts the number to a string, with underscores as the thousands separator. +pub fn format_with_underscores(n: usize) -> String { + let mut s = n.to_string(); + let mut i = s.len(); + while i > 3 { + i -= 3; + s.insert(i, '_'); + } + s +} diff --git a/compiler/rustc_data_structures/src/thousands/tests.rs b/compiler/rustc_data_structures/src/thousands/tests.rs new file mode 100644 index 00000000000..906605d9a93 --- /dev/null +++ b/compiler/rustc_data_structures/src/thousands/tests.rs @@ -0,0 +1,14 @@ +use super::*; + +#[test] +fn test_format_with_underscores() { + assert_eq!("0", format_with_underscores(0)); + assert_eq!("1", format_with_underscores(1)); + assert_eq!("99", format_with_underscores(99)); + assert_eq!("345", format_with_underscores(345)); + assert_eq!("1_000", format_with_underscores(1_000)); + assert_eq!("12_001", format_with_underscores(12_001)); + assert_eq!("999_999", format_with_underscores(999_999)); + assert_eq!("1_000_000", format_with_underscores(1_000_000)); + assert_eq!("12_345_678", format_with_underscores(12_345_678)); +} diff --git a/compiler/rustc_data_structures/src/vec_cache.rs b/compiler/rustc_data_structures/src/vec_cache.rs index eb251b587c8..2ff60ab7f36 100644 --- a/compiler/rustc_data_structures/src/vec_cache.rs +++ b/compiler/rustc_data_structures/src/vec_cache.rs @@ -206,6 +206,19 @@ impl SlotIndex { } } +/// In-memory cache for queries whose keys are densely-numbered IDs +/// (e.g `CrateNum`, `LocalDefId`), and can therefore be used as indices +/// into a dense vector of cached values. +/// +/// (As of [#124780] the underlying storage is not an actual `Vec`, but rather +/// a series of increasingly-large buckets, for improved performance when the +/// parallel frontend is using multiple threads.) +/// +/// Each entry in the cache stores the query's return value (`V`), and also +/// an associated index (`I`), which in practice is a `DepNodeIndex` used for +/// query dependency tracking. +/// +/// [#124780]: https://github.com/rust-lang/rust/pull/124780 pub struct VecCache<K: Idx, V, I> { // Entries per bucket: // Bucket 0: 4096 2^12 diff --git a/compiler/rustc_data_structures/src/vec_cache/tests.rs b/compiler/rustc_data_structures/src/vec_cache/tests.rs index a05f2741362..3b65c14162e 100644 --- a/compiler/rustc_data_structures/src/vec_cache/tests.rs +++ b/compiler/rustc_data_structures/src/vec_cache/tests.rs @@ -58,11 +58,14 @@ fn concurrent_stress_check() { #[test] fn slot_entries_table() { - assert_eq!(ENTRIES_BY_BUCKET, [ - 4096, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, - 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, - 2147483648 - ]); + assert_eq!( + ENTRIES_BY_BUCKET, + [ + 4096, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, + 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, + 1073741824, 2147483648 + ] + ); } #[test] |