diff options
Diffstat (limited to 'compiler/rustc_data_structures')
33 files changed, 647 insertions, 2766 deletions
diff --git a/compiler/rustc_data_structures/Cargo.toml b/compiler/rustc_data_structures/Cargo.toml index 29cb2c0a3..2102f09c5 100644 --- a/compiler/rustc_data_structures/Cargo.toml +++ b/compiler/rustc_data_structures/Cargo.toml @@ -9,18 +9,19 @@ edition = "2021" arrayvec = { version = "0.7", default-features = false } bitflags = "1.2.1" cfg-if = "1.0" -ena = "0.14.1" -indexmap = { version = "1.9.1" } +ena = "0.14.2" +indexmap = { version = "1.9.3" } jobserver_crate = { version = "0.1.13", package = "jobserver" } libc = "0.2" measureme = "10.0.0" -rayon-core = { version = "0.4.0", package = "rustc-rayon-core", optional = true } -rayon = { version = "0.4.0", package = "rustc-rayon", optional = true } +rustc-rayon-core = { version = "0.5.0", optional = true } +rustc-rayon = { version = "0.5.0", optional = true } rustc_graphviz = { path = "../rustc_graphviz" } rustc-hash = "1.1.0" rustc_index = { path = "../rustc_index", package = "rustc_index" } rustc_macros = { path = "../rustc_macros" } rustc_serialize = { path = "../rustc_serialize" } +serde_json = "1.0.59" smallvec = { version = "1.8.1", features = [ "const_generics", "union", @@ -31,16 +32,24 @@ stacker = "0.1.15" tempfile = "3.2" thin-vec = "0.2.12" tracing = "0.1" -elsa = "1.8" +elsa = "=1.7.1" +itertools = "0.10.1" [dependencies.parking_lot] version = "0.11" -[target.'cfg(windows)'.dependencies] -winapi = { version = "0.3", features = ["fileapi", "psapi", "winerror"] } +[target.'cfg(windows)'.dependencies.windows] +version = "0.46.0" +features = [ + "Win32_Foundation", + "Win32_Storage_FileSystem", + "Win32_System_IO", + "Win32_System_ProcessStatus", + "Win32_System_Threading", +] [target.'cfg(not(target_arch = "wasm32"))'.dependencies] memmap2 = "0.2.1" [features] -rustc_use_parallel_compiler = ["indexmap/rustc-rayon", "rayon", "rayon-core"] +rustc_use_parallel_compiler = ["indexmap/rustc-rayon", "rustc-rayon", "rustc-rayon-core"] diff --git a/compiler/rustc_data_structures/src/map_in_place.rs b/compiler/rustc_data_structures/src/flat_map_in_place.rs index a0d4b7ade..f58844f28 100644 --- a/compiler/rustc_data_structures/src/map_in_place.rs +++ b/compiler/rustc_data_structures/src/flat_map_in_place.rs @@ -2,14 +2,7 @@ use smallvec::{Array, SmallVec}; use std::ptr; use thin_vec::ThinVec; -pub trait MapInPlace<T>: Sized { - fn map_in_place<F>(&mut self, mut f: F) - where - F: FnMut(T) -> T, - { - self.flat_map_in_place(|e| Some(f(e))) - } - +pub trait FlatMapInPlace<T>: Sized { fn flat_map_in_place<F, I>(&mut self, f: F) where F: FnMut(T) -> I, @@ -66,14 +59,14 @@ macro_rules! flat_map_in_place { }; } -impl<T> MapInPlace<T> for Vec<T> { +impl<T> FlatMapInPlace<T> for Vec<T> { flat_map_in_place!(); } -impl<T, A: Array<Item = T>> MapInPlace<T> for SmallVec<A> { +impl<T, A: Array<Item = T>> FlatMapInPlace<T> for SmallVec<A> { flat_map_in_place!(); } -impl<T> MapInPlace<T> for ThinVec<T> { +impl<T> FlatMapInPlace<T> for ThinVec<T> { flat_map_in_place!(); } diff --git a/compiler/rustc_data_structures/src/flock.rs b/compiler/rustc_data_structures/src/flock.rs index e395d8dbb..efdb44248 100644 --- a/compiler/rustc_data_structures/src/flock.rs +++ b/compiler/rustc_data_structures/src/flock.rs @@ -4,9 +4,6 @@ //! green/native threading. This is just a bare-bones enough solution for //! librustdoc, it is not production quality at all. -#![allow(non_camel_case_types)] -#![allow(nonstandard_style)] - cfg_if! { if #[cfg(target_os = "linux")] { mod linux; @@ -16,7 +13,7 @@ cfg_if! { use unix as imp; } else if #[cfg(windows)] { mod windows; - use windows as imp; + use self::windows as imp; } else { mod unsupported; use unsupported as imp; diff --git a/compiler/rustc_data_structures/src/flock/windows.rs b/compiler/rustc_data_structures/src/flock/windows.rs index 43e6caaa1..da128f464 100644 --- a/compiler/rustc_data_structures/src/flock/windows.rs +++ b/compiler/rustc_data_structures/src/flock/windows.rs @@ -1,13 +1,16 @@ use std::fs::{File, OpenOptions}; use std::io; -use std::mem; use std::os::windows::prelude::*; use std::path::Path; -use winapi::shared::winerror::ERROR_INVALID_FUNCTION; -use winapi::um::fileapi::LockFileEx; -use winapi::um::minwinbase::{LOCKFILE_EXCLUSIVE_LOCK, LOCKFILE_FAIL_IMMEDIATELY, OVERLAPPED}; -use winapi::um::winnt::{FILE_SHARE_DELETE, FILE_SHARE_READ, FILE_SHARE_WRITE}; +use windows::{ + Win32::Foundation::{ERROR_INVALID_FUNCTION, HANDLE}, + Win32::Storage::FileSystem::{ + LockFileEx, FILE_SHARE_DELETE, FILE_SHARE_READ, FILE_SHARE_WRITE, LOCKFILE_EXCLUSIVE_LOCK, + LOCKFILE_FAIL_IMMEDIATELY, LOCK_FILE_FLAGS, + }, + Win32::System::IO::OVERLAPPED, +}; #[derive(Debug)] pub struct Lock { @@ -25,7 +28,7 @@ impl Lock { let share_mode = FILE_SHARE_DELETE | FILE_SHARE_READ | FILE_SHARE_WRITE; let mut open_options = OpenOptions::new(); - open_options.read(true).share_mode(share_mode); + open_options.read(true).share_mode(share_mode.0); if create { open_options.create(true).write(true); @@ -43,33 +46,42 @@ impl Lock { } }; - let ret = unsafe { - let mut overlapped: OVERLAPPED = mem::zeroed(); + let mut flags = LOCK_FILE_FLAGS::default(); + if !wait { + flags |= LOCKFILE_FAIL_IMMEDIATELY; + } - let mut dwFlags = 0; - if !wait { - dwFlags |= LOCKFILE_FAIL_IMMEDIATELY; - } + if exclusive { + flags |= LOCKFILE_EXCLUSIVE_LOCK; + } - if exclusive { - dwFlags |= LOCKFILE_EXCLUSIVE_LOCK; - } + let mut overlapped = OVERLAPPED::default(); - debug!("attempting to acquire lock on lock file `{}`", p.display()); - LockFileEx(file.as_raw_handle(), dwFlags, 0, 0xFFFF_FFFF, 0xFFFF_FFFF, &mut overlapped) - }; - if ret == 0 { - let err = io::Error::last_os_error(); - debug!("failed acquiring file lock: {}", err); - Err(err) - } else { - debug!("successfully acquired lock"); - Ok(Lock { _file: file }) + debug!("attempting to acquire lock on lock file `{}`", p.display()); + + unsafe { + LockFileEx( + HANDLE(file.as_raw_handle() as isize), + flags, + 0, + u32::MAX, + u32::MAX, + &mut overlapped, + ) } + .ok() + .map_err(|e| { + let err = io::Error::from_raw_os_error(e.code().0); + debug!("failed acquiring file lock: {}", err); + err + })?; + + debug!("successfully acquired lock"); + Ok(Lock { _file: file }) } pub fn error_unsupported(err: &io::Error) -> bool { - err.raw_os_error() == Some(ERROR_INVALID_FUNCTION as i32) + err.raw_os_error() == Some(ERROR_INVALID_FUNCTION.0 as i32) } } diff --git a/compiler/rustc_data_structures/src/graph/dominators/mod.rs b/compiler/rustc_data_structures/src/graph/dominators/mod.rs index 0a21a4249..0df9dc112 100644 --- a/compiler/rustc_data_structures/src/graph/dominators/mod.rs +++ b/compiler/rustc_data_structures/src/graph/dominators/mod.rs @@ -10,7 +10,7 @@ //! <https://www.cs.princeton.edu/courses/archive/spr03/cs423/download/dominators.pdf> use super::ControlFlowGraph; -use rustc_index::vec::{Idx, IndexVec}; +use rustc_index::vec::{Idx, IndexSlice, IndexVec}; use std::cmp::Ordering; #[cfg(test)] @@ -256,10 +256,10 @@ pub fn dominators<G: ControlFlowGraph>(graph: G) -> Dominators<G::Node> { /// where `+>` is a proper ancestor and `*>` is just an ancestor. #[inline] fn eval( - ancestor: &mut IndexVec<PreorderIndex, PreorderIndex>, + ancestor: &mut IndexSlice<PreorderIndex, PreorderIndex>, lastlinked: Option<PreorderIndex>, - semi: &IndexVec<PreorderIndex, PreorderIndex>, - label: &mut IndexVec<PreorderIndex, PreorderIndex>, + semi: &IndexSlice<PreorderIndex, PreorderIndex>, + label: &mut IndexSlice<PreorderIndex, PreorderIndex>, node: PreorderIndex, ) -> PreorderIndex { if is_processed(node, lastlinked) { @@ -277,10 +277,10 @@ fn is_processed(v: PreorderIndex, lastlinked: Option<PreorderIndex>) -> bool { #[inline] fn compress( - ancestor: &mut IndexVec<PreorderIndex, PreorderIndex>, + ancestor: &mut IndexSlice<PreorderIndex, PreorderIndex>, lastlinked: Option<PreorderIndex>, - semi: &IndexVec<PreorderIndex, PreorderIndex>, - label: &mut IndexVec<PreorderIndex, PreorderIndex>, + semi: &IndexSlice<PreorderIndex, PreorderIndex>, + label: &mut IndexSlice<PreorderIndex, PreorderIndex>, v: PreorderIndex, ) { assert!(is_processed(v, lastlinked)); diff --git a/compiler/rustc_data_structures/src/graph/implementation/mod.rs b/compiler/rustc_data_structures/src/graph/implementation/mod.rs index 1aa7ac024..9ff401c3c 100644 --- a/compiler/rustc_data_structures/src/graph/implementation/mod.rs +++ b/compiler/rustc_data_structures/src/graph/implementation/mod.rs @@ -206,17 +206,11 @@ impl<N: Debug, E: Debug> Graph<N, E> { AdjacentEdges { graph: self, direction, next: first_edge } } - pub fn successor_nodes<'a>( - &'a self, - source: NodeIndex, - ) -> impl Iterator<Item = NodeIndex> + 'a { + pub fn successor_nodes(&self, source: NodeIndex) -> impl Iterator<Item = NodeIndex> + '_ { self.outgoing_edges(source).targets() } - pub fn predecessor_nodes<'a>( - &'a self, - target: NodeIndex, - ) -> impl Iterator<Item = NodeIndex> + 'a { + pub fn predecessor_nodes(&self, target: NodeIndex) -> impl Iterator<Item = NodeIndex> + '_ { self.incoming_edges(target).sources() } diff --git a/compiler/rustc_data_structures/src/graph/iterate/mod.rs b/compiler/rustc_data_structures/src/graph/iterate/mod.rs index 8a9af300c..01a83b40a 100644 --- a/compiler/rustc_data_structures/src/graph/iterate/mod.rs +++ b/compiler/rustc_data_structures/src/graph/iterate/mod.rs @@ -1,6 +1,6 @@ use super::{DirectedGraph, WithNumNodes, WithStartNode, WithSuccessors}; use rustc_index::bit_set::BitSet; -use rustc_index::vec::IndexVec; +use rustc_index::vec::{IndexSlice, IndexVec}; use std::ops::ControlFlow; #[cfg(test)] @@ -31,7 +31,7 @@ fn post_order_walk<G: DirectedGraph + WithSuccessors + WithNumNodes>( graph: &G, node: G::Node, result: &mut Vec<G::Node>, - visited: &mut IndexVec<G::Node, bool>, + visited: &mut IndexSlice<G::Node, bool>, ) { struct PostOrderFrame<Node, Iter> { node: Node, diff --git a/compiler/rustc_data_structures/src/graph/scc/mod.rs b/compiler/rustc_data_structures/src/graph/scc/mod.rs index c4b11951a..28c357e54 100644 --- a/compiler/rustc_data_structures/src/graph/scc/mod.rs +++ b/compiler/rustc_data_structures/src/graph/scc/mod.rs @@ -8,7 +8,7 @@ use crate::fx::FxHashSet; use crate::graph::vec_graph::VecGraph; use crate::graph::{DirectedGraph, GraphSuccessors, WithNumEdges, WithNumNodes, WithSuccessors}; -use rustc_index::vec::{Idx, IndexVec}; +use rustc_index::vec::{Idx, IndexSlice, IndexVec}; use std::ops::Range; #[cfg(test)] @@ -43,7 +43,7 @@ impl<N: Idx, S: Idx + Ord> Sccs<N, S> { SccsConstruction::construct(graph) } - pub fn scc_indices(&self) -> &IndexVec<N, S> { + pub fn scc_indices(&self) -> &IndexSlice<N, S> { &self.scc_indices } @@ -123,7 +123,7 @@ impl<S: Idx> SccData<S> { self.ranges.len() } - pub fn ranges(&self) -> &IndexVec<S, Range<usize>> { + pub fn ranges(&self) -> &IndexSlice<S, Range<usize>> { &self.ranges } diff --git a/compiler/rustc_data_structures/src/graph/scc/tests.rs b/compiler/rustc_data_structures/src/graph/scc/tests.rs index 820a70fc8..513df666d 100644 --- a/compiler/rustc_data_structures/src/graph/scc/tests.rs +++ b/compiler/rustc_data_structures/src/graph/scc/tests.rs @@ -56,7 +56,7 @@ fn test_three_sccs() { assert_eq!(sccs.scc(1), 0); assert_eq!(sccs.scc(2), 0); assert_eq!(sccs.scc(3), 2); - assert_eq!(sccs.successors(0), &[]); + assert_eq!(sccs.successors(0), &[] as &[usize]); assert_eq!(sccs.successors(1), &[0]); assert_eq!(sccs.successors(2), &[0]); } @@ -113,7 +113,7 @@ fn test_find_state_2() { assert_eq!(sccs.scc(2), 0); assert_eq!(sccs.scc(3), 0); assert_eq!(sccs.scc(4), 0); - assert_eq!(sccs.successors(0), &[]); + assert_eq!(sccs.successors(0), &[] as &[usize]); } #[test] @@ -138,7 +138,7 @@ fn test_find_state_3() { assert_eq!(sccs.scc(3), 0); assert_eq!(sccs.scc(4), 0); assert_eq!(sccs.scc(5), 1); - assert_eq!(sccs.successors(0), &[]); + assert_eq!(sccs.successors(0), &[] as &[usize]); assert_eq!(sccs.successors(1), &[0]); } 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 c8f979267..7c866da60 100644 --- a/compiler/rustc_data_structures/src/graph/vec_graph/tests.rs +++ b/compiler/rustc_data_structures/src/graph/vec_graph/tests.rs @@ -27,11 +27,11 @@ fn successors() { let graph = create_graph(); assert_eq!(graph.successors(0), &[1]); assert_eq!(graph.successors(1), &[2, 3]); - assert_eq!(graph.successors(2), &[]); + assert_eq!(graph.successors(2), &[] as &[usize]); assert_eq!(graph.successors(3), &[4]); - assert_eq!(graph.successors(4), &[]); + assert_eq!(graph.successors(4), &[] as &[usize]); assert_eq!(graph.successors(5), &[1]); - assert_eq!(graph.successors(6), &[]); + assert_eq!(graph.successors(6), &[] as &[usize]); } #[test] diff --git a/compiler/rustc_data_structures/src/lib.rs b/compiler/rustc_data_structures/src/lib.rs index a94e52fdf..e373bd184 100644 --- a/compiler/rustc_data_structures/src/lib.rs +++ b/compiler/rustc_data_structures/src/lib.rs @@ -1,5 +1,5 @@ //! Various data structures used by the Rust compiler. The intention -//! is that code in here should be not be *specific* to rustc, so that +//! is that code in here should not be *specific* to rustc, so that //! it can be easily unit tested and so forth. //! //! # Note @@ -20,13 +20,15 @@ #![feature(never_type)] #![feature(type_alias_impl_trait)] #![feature(new_uninit)] -#![feature(once_cell)] +#![feature(lazy_cell)] #![feature(rustc_attrs)] #![feature(negative_impls)] #![feature(test)] #![feature(thread_id_value)] #![feature(vec_into_raw_parts)] #![feature(get_mut_unchecked)] +#![feature(lint_reasons)] +#![feature(unwrap_infallible)] #![allow(rustc::default_hash_types)] #![allow(rustc::potential_query_instability)] #![deny(rustc::untranslatable_diagnostic)] @@ -50,6 +52,7 @@ pub fn cold_path<F: FnOnce() -> R, R>(f: F) -> R { pub mod base_n; pub mod binary_search_util; pub mod captures; +pub mod flat_map_in_place; pub mod flock; pub mod functor; pub mod fx; @@ -57,9 +60,7 @@ pub mod graph; pub mod intern; pub mod jobserver; pub mod macros; -pub mod map_in_place; pub mod obligation_forest; -pub mod owning_ref; pub mod sip128; pub mod small_c_str; pub mod small_str; @@ -79,10 +80,10 @@ pub mod sync; pub mod tiny_list; pub mod transitive_relation; pub mod vec_linked_list; -pub mod vec_map; pub mod work_queue; pub use atomic_ref::AtomicRef; pub mod frozen; +pub mod owned_slice; pub mod sso; pub mod steal; pub mod tagged_ptr; diff --git a/compiler/rustc_data_structures/src/memmap.rs b/compiler/rustc_data_structures/src/memmap.rs index 3d44e17f3..ef37a606f 100644 --- a/compiler/rustc_data_structures/src/memmap.rs +++ b/compiler/rustc_data_structures/src/memmap.rs @@ -2,9 +2,7 @@ use std::fs::File; use std::io; use std::ops::{Deref, DerefMut}; -use crate::owning_ref::StableAddress; - -/// A trivial wrapper for [`memmap2::Mmap`] that implements [`StableAddress`]. +/// A trivial wrapper for [`memmap2::Mmap`] (or `Vec<u8>` on WASM). #[cfg(not(target_arch = "wasm32"))] pub struct Mmap(memmap2::Mmap); @@ -42,16 +40,10 @@ impl Deref for Mmap { impl AsRef<[u8]> for Mmap { fn as_ref(&self) -> &[u8] { - &*self.0 + &self.0 } } -// SAFETY: On architectures other than WASM, mmap is used as backing storage. The address of this -// memory map is stable. On WASM, `Vec<u8>` is used as backing storage. The `Mmap` type doesn't -// export any function that can cause the `Vec` to be re-allocated. As such the address of the -// bytes inside this `Vec` is stable. -unsafe impl StableAddress for Mmap {} - #[cfg(not(target_arch = "wasm32"))] pub struct MmapMut(memmap2::MmapMut); diff --git a/compiler/rustc_data_structures/src/obligation_forest/mod.rs b/compiler/rustc_data_structures/src/obligation_forest/mod.rs index 91abdaada..27a869eb7 100644 --- a/compiler/rustc_data_structures/src/obligation_forest/mod.rs +++ b/compiler/rustc_data_structures/src/obligation_forest/mod.rs @@ -97,7 +97,17 @@ pub trait ObligationProcessor { type Error: Debug; type OUT: OutcomeTrait<Obligation = Self::Obligation, Error = Error<Self::Obligation, Self::Error>>; - fn needs_process_obligation(&self, obligation: &Self::Obligation) -> bool; + /// Implementations can provide a fast-path to obligation-processing + /// by counting the prefix of the passed iterator for which + /// `needs_process_obligation` would return false. + fn skippable_obligations<'a>( + &'a self, + _it: impl Iterator<Item = &'a Self::Obligation>, + ) -> usize { + 0 + } + + fn needs_process_obligation(&self, _obligation: &Self::Obligation) -> bool; fn process_obligation( &mut self, @@ -416,6 +426,10 @@ impl<O: ForestObligation> ObligationForest<O> { loop { let mut has_changed = false; + // This is the super fast path for cheap-to-check conditions. + let mut index = + processor.skippable_obligations(self.nodes.iter().map(|n| &n.obligation)); + // Note that the loop body can append new nodes, and those new nodes // will then be processed by subsequent iterations of the loop. // @@ -424,9 +438,8 @@ impl<O: ForestObligation> ObligationForest<O> { // `for index in 0..self.nodes.len() { ... }` because the range would // be computed with the initial length, and we would miss the appended // nodes. Therefore we use a `while` loop. - let mut index = 0; while let Some(node) = self.nodes.get_mut(index) { - // This test is extremely hot. + // This is the moderately fast path when the prefix skipping above didn't work out. if node.state.get() != NodeState::Pending || !processor.needs_process_obligation(&node.obligation) { diff --git a/compiler/rustc_data_structures/src/owned_slice.rs b/compiler/rustc_data_structures/src/owned_slice.rs new file mode 100644 index 000000000..048401f66 --- /dev/null +++ b/compiler/rustc_data_structures/src/owned_slice.rs @@ -0,0 +1,118 @@ +use std::{borrow::Borrow, ops::Deref}; + +// 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::{Send, Sync}; + +/// An owned slice. +/// +/// This is similar to `Box<[u8]>` but allows slicing and using anything as the +/// backing buffer. +/// +/// See [`slice_owned`] for `OwnedSlice` construction and examples. +/// +/// --------------------------------------------------------------------------- +/// +/// This is essentially a replacement for `owning_ref` which is a lot simpler +/// and even sound! 🌸 +pub struct OwnedSlice { + /// This is conceptually a `&'self.owner [u8]`. + bytes: *const [u8], + + // +---------------------------------------+ + // | We expect `dead_code` lint here, | + // | because we don't want to accidentally | + // | touch the owner — otherwise the owner | + // | could invalidate out `bytes` pointer | + // | | + // | so be quiet | + // +----+ +-------------------------------+ + // \/ + // ⊂(´･◡･⊂ )∘˚˳° (I am the phantom remnant of #97770) + #[expect(dead_code)] + owner: Box<dyn Send + Sync>, +} + +/// Makes an [`OwnedSlice`] out of an `owner` and a `slicer` function. +/// +/// ## Examples +/// +/// ```rust +/// # use rustc_data_structures::owned_slice::{OwnedSlice, slice_owned}; +/// let vec = vec![1, 2, 3, 4]; +/// +/// // Identical to slicing via `&v[1..3]` but produces an owned slice +/// let slice: OwnedSlice = slice_owned(vec, |v| &v[1..3]); +/// assert_eq!(&*slice, [2, 3]); +/// ``` +/// +/// ```rust +/// # use rustc_data_structures::owned_slice::{OwnedSlice, slice_owned}; +/// # use std::ops::Deref; +/// let vec = vec![1, 2, 3, 4]; +/// +/// // Identical to slicing via `&v[..]` but produces an owned slice +/// let slice: OwnedSlice = slice_owned(vec, Deref::deref); +/// assert_eq!(&*slice, [1, 2, 3, 4]); +/// ``` +pub fn slice_owned<O, F>(owner: O, slicer: F) -> OwnedSlice +where + O: Send + Sync + 'static, + F: FnOnce(&O) -> &[u8], +{ + try_slice_owned(owner, |x| Ok::<_, !>(slicer(x))).into_ok() +} + +/// Makes an [`OwnedSlice`] out of an `owner` and a `slicer` function that can fail. +/// +/// See [`slice_owned`] for the infallible version. +pub fn try_slice_owned<O, F, E>(owner: O, slicer: F) -> Result<OwnedSlice, E> +where + O: Send + Sync + 'static, + F: FnOnce(&O) -> Result<&[u8], E>, +{ + // We box the owner of the bytes, so it doesn't move. + // + // Since the owner does not move and we don't access it in any way + // before drop, there is nothing that can invalidate the bytes pointer. + // + // Thus, "extending" the lifetime of the reference returned from `F` is fine. + // We pretend that we pass it a reference that lives as long as the returned slice. + // + // 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 = Box::new(owner); + let bytes = slicer(&*owner)?; + + Ok(OwnedSlice { bytes, owner }) +} + +impl Deref for OwnedSlice { + type Target = [u8]; + + #[inline] + fn deref(&self) -> &[u8] { + // Safety: + // `self.bytes` is valid per the construction in `slice_owned` + // (which is the only constructor) + unsafe { &*self.bytes } + } +} + +impl Borrow<[u8]> for OwnedSlice { + #[inline] + fn borrow(&self) -> &[u8] { + self + } +} + +// Safety: `OwnedSlice` is conceptually `(&'self.1 [u8], Box<dyn Send + Sync>)`, which is `Send` +unsafe impl Send for OwnedSlice {} + +// Safety: `OwnedSlice` is conceptually `(&'self.1 [u8], Box<dyn Send + Sync>)`, which is `Sync` +unsafe impl Sync for OwnedSlice {} + +#[cfg(test)] +mod tests; diff --git a/compiler/rustc_data_structures/src/owned_slice/tests.rs b/compiler/rustc_data_structures/src/owned_slice/tests.rs new file mode 100644 index 000000000..e715fb553 --- /dev/null +++ b/compiler/rustc_data_structures/src/owned_slice/tests.rs @@ -0,0 +1,74 @@ +use std::{ + ops::Deref, + sync::{ + atomic::{self, AtomicBool}, + Arc, + }, +}; + +use crate::{ + owned_slice::{slice_owned, try_slice_owned, OwnedSlice}, + OnDrop, +}; + +#[test] +fn smoke() { + let slice = slice_owned(vec![1, 2, 3, 4, 5, 6], Vec::as_slice); + + assert_eq!(&*slice, [1, 2, 3, 4, 5, 6]); +} + +#[test] +fn static_storage() { + let slice = slice_owned(Box::new(String::from("what")), |_| b"bytes boo"); + + assert_eq!(&*slice, b"bytes boo"); +} + +#[test] +fn slice_the_slice() { + let slice = slice_owned(vec![1, 2, 3, 4, 5, 6], Vec::as_slice); + let slice = slice_owned(slice, |s| &s[1..][..4]); + let slice = slice_owned(slice, |s| s); + let slice = slice_owned(slice, |s| &s[1..]); + + assert_eq!(&*slice, &[1, 2, 3, 4, 5, 6][1..][..4][1..]); +} + +#[test] +fn try_and_fail() { + let res = try_slice_owned(vec![0], |v| v.get(12..).ok_or(())); + + assert!(res.is_err()); +} + +#[test] +fn boxed() { + // It's important that we don't cause UB because of `Box`'es uniqueness + + let boxed: Box<[u8]> = vec![1, 1, 2, 3, 5, 8, 13, 21].into_boxed_slice(); + let slice = slice_owned(boxed, Deref::deref); + + assert_eq!(&*slice, [1, 1, 2, 3, 5, 8, 13, 21]); +} + +#[test] +fn drop_drops() { + let flag = Arc::new(AtomicBool::new(false)); + let flag_prime = Arc::clone(&flag); + let d = OnDrop(move || flag_prime.store(true, atomic::Ordering::Relaxed)); + + let slice = slice_owned(d, |_| &[]); + + assert_eq!(flag.load(atomic::Ordering::Relaxed), false); + + drop(slice); + + assert_eq!(flag.load(atomic::Ordering::Relaxed), true); +} + +#[test] +fn send_sync() { + crate::sync::assert_send::<OwnedSlice>(); + crate::sync::assert_sync::<OwnedSlice>(); +} diff --git a/compiler/rustc_data_structures/src/owning_ref/LICENSE b/compiler/rustc_data_structures/src/owning_ref/LICENSE deleted file mode 100644 index dff72d1e4..000000000 --- a/compiler/rustc_data_structures/src/owning_ref/LICENSE +++ /dev/null @@ -1,21 +0,0 @@ -The MIT License (MIT) - -Copyright (c) 2015 Marvin Löbel - -Permission is hereby granted, free of charge, to any person obtaining a copy -of this software and associated documentation files (the "Software"), to deal -in the Software without restriction, including without limitation the rights -to use, copy, modify, merge, publish, distribute, sublicense, and/or sell -copies of the Software, and to permit persons to whom the Software is -furnished to do so, subject to the following conditions: - -The above copyright notice and this permission notice shall be included in all -copies or substantial portions of the Software. - -THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR -IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, -FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE -AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER -LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, -OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE -SOFTWARE. diff --git a/compiler/rustc_data_structures/src/owning_ref/mod.rs b/compiler/rustc_data_structures/src/owning_ref/mod.rs deleted file mode 100644 index d1d92b905..000000000 --- a/compiler/rustc_data_structures/src/owning_ref/mod.rs +++ /dev/null @@ -1,1211 +0,0 @@ -#![warn(missing_docs)] - -/*! -# An owning reference. - -This crate provides the _owning reference_ types `OwningRef` and `OwningRefMut` -that enables it to bundle a reference together with the owner of the data it points to. -This allows moving and dropping of an `OwningRef` without needing to recreate the reference. - -This can sometimes be useful because Rust borrowing rules normally prevent -moving a type that has been moved from. For example, this kind of code gets rejected: - -```compile_fail,E0515 -fn return_owned_and_referenced<'a>() -> (Vec<u8>, &'a [u8]) { - let v = vec![1, 2, 3, 4]; - let s = &v[1..3]; - (v, s) -} -``` - -Even though, from a memory-layout point of view, this can be entirely safe -if the new location of the vector still lives longer than the lifetime `'a` -of the reference because the backing allocation of the vector does not change. - -This library enables this safe usage by keeping the owner and the reference -bundled together in a wrapper type that ensure that lifetime constraint: - -``` -# use rustc_data_structures::owning_ref::OwningRef; -# fn main() { -fn return_owned_and_referenced() -> OwningRef<Vec<u8>, [u8]> { - let v = vec![1, 2, 3, 4]; - let or = OwningRef::new(v); - let or = or.map(|v| &v[1..3]); - or -} -# } -``` - -It works by requiring owner types to dereference to stable memory locations -and preventing mutable access to root containers, which in practice requires heap allocation -as provided by `Box<T>`, `Rc<T>`, etc. - -Also provided are typedefs for common owner type combinations, -which allow for less verbose type signatures. -For example, `BoxRef<T>` instead of `OwningRef<Box<T>, T>`. - -The crate also provides the more advanced `OwningHandle` type, -which allows more freedom in bundling a dependent handle object -along with the data it depends on, at the cost of some unsafe needed in the API. -See the documentation around `OwningHandle` for more details. - -# Examples - -## Basics - -``` -use rustc_data_structures::owning_ref::BoxRef; - -fn main() { - // Create an array owned by a Box. - let arr = Box::new([1, 2, 3, 4]) as Box<[i32]>; - - // Transfer into a BoxRef. - let arr: BoxRef<[i32]> = BoxRef::new(arr); - assert_eq!(&*arr, &[1, 2, 3, 4]); - - // We can slice the array without losing ownership or changing type. - let arr: BoxRef<[i32]> = arr.map(|arr| &arr[1..3]); - assert_eq!(&*arr, &[2, 3]); - - // Also works for Arc, Rc, String and Vec! -} -``` - -## Caching a reference to a struct field - -``` -use rustc_data_structures::owning_ref::BoxRef; - -fn main() { - struct Foo { - tag: u32, - x: u16, - y: u16, - z: u16, - } - let foo = Foo { tag: 1, x: 100, y: 200, z: 300 }; - - let or = BoxRef::new(Box::new(foo)).map(|foo| { - match foo.tag { - 0 => &foo.x, - 1 => &foo.y, - 2 => &foo.z, - _ => panic!(), - } - }); - - assert_eq!(*or, 200); -} -``` - -## Caching a reference to an entry in a vector - -``` -use rustc_data_structures::owning_ref::VecRef; - -fn main() { - let v = VecRef::new(vec![1, 2, 3, 4, 5]).map(|v| &v[3]); - assert_eq!(*v, 4); -} -``` - -## Caching a subslice of a String - -``` -use rustc_data_structures::owning_ref::StringRef; - -fn main() { - let s = StringRef::new("hello world".to_owned()) - .map(|s| s.split(' ').nth(1).unwrap()); - - assert_eq!(&*s, "world"); -} -``` - -## Reference counted slices that share ownership of the backing storage - -``` -use rustc_data_structures::owning_ref::RcRef; -use std::rc::Rc; - -fn main() { - let rc: RcRef<[i32]> = RcRef::new(Rc::new([1, 2, 3, 4]) as Rc<[i32]>); - assert_eq!(&*rc, &[1, 2, 3, 4]); - - let rc_a: RcRef<[i32]> = rc.clone().map(|s| &s[0..2]); - let rc_b = rc.clone().map(|s| &s[1..3]); - let rc_c = rc.clone().map(|s| &s[2..4]); - assert_eq!(&*rc_a, &[1, 2]); - assert_eq!(&*rc_b, &[2, 3]); - assert_eq!(&*rc_c, &[3, 4]); - - let rc_c_a = rc_c.clone().map(|s| &s[1]); - assert_eq!(&*rc_c_a, &4); -} -``` - -## Atomic reference counted slices that share ownership of the backing storage - -``` -use rustc_data_structures::owning_ref::ArcRef; -use std::sync::Arc; - -fn main() { - use std::thread; - - fn par_sum(rc: ArcRef<[i32]>) -> i32 { - if rc.len() == 0 { - return 0; - } else if rc.len() == 1 { - return rc[0]; - } - let mid = rc.len() / 2; - let left = rc.clone().map(|s| &s[..mid]); - let right = rc.map(|s| &s[mid..]); - - let left = thread::spawn(move || par_sum(left)); - let right = thread::spawn(move || par_sum(right)); - - left.join().unwrap() + right.join().unwrap() - } - - let rc: Arc<[i32]> = Arc::new([1, 2, 3, 4]); - let rc: ArcRef<[i32]> = rc.into(); - - assert_eq!(par_sum(rc), 10); -} -``` - -## References into RAII locks - -``` -use rustc_data_structures::owning_ref::RefRef; -use std::cell::{RefCell, Ref}; - -fn main() { - let refcell = RefCell::new((1, 2, 3, 4)); - // Also works with Mutex and RwLock - - let refref = { - let refref = RefRef::new(refcell.borrow()).map(|x| &x.3); - assert_eq!(*refref, 4); - - // We move the RAII lock and the reference to one of - // the subfields in the data it guards here: - refref - }; - - assert_eq!(*refref, 4); - - drop(refref); - - assert_eq!(*refcell.borrow(), (1, 2, 3, 4)); -} -``` - -## Mutable reference - -When the owned container implements `DerefMut`, it is also possible to make -a _mutable owning reference_. (e.g., with `Box`, `RefMut`, `MutexGuard`) - -``` -use rustc_data_structures::owning_ref::RefMutRefMut; -use std::cell::{RefCell, RefMut}; - -fn main() { - let refcell = RefCell::new((1, 2, 3, 4)); - - let mut refmut_refmut = { - let mut refmut_refmut = RefMutRefMut::new(refcell.borrow_mut()).map_mut(|x| &mut x.3); - assert_eq!(*refmut_refmut, 4); - *refmut_refmut *= 2; - - refmut_refmut - }; - - assert_eq!(*refmut_refmut, 8); - *refmut_refmut *= 2; - - drop(refmut_refmut); - - assert_eq!(*refcell.borrow(), (1, 2, 3, 16)); -} -``` -*/ - -pub use stable_deref_trait::{ - CloneStableDeref as CloneStableAddress, StableDeref as StableAddress, -}; -use std::mem; - -/// An owning reference. -/// -/// This wraps an owner `O` and a reference `&T` pointing -/// at something reachable from `O::Target` while keeping -/// the ability to move `self` around. -/// -/// The owner is usually a pointer that points at some base type. -/// -/// For more details and examples, see the module and method docs. -pub struct OwningRef<O, T: ?Sized> { - owner: O, - reference: *const T, -} - -/// An mutable owning reference. -/// -/// This wraps an owner `O` and a reference `&mut T` pointing -/// at something reachable from `O::Target` while keeping -/// the ability to move `self` around. -/// -/// The owner is usually a pointer that points at some base type. -/// -/// For more details and examples, see the module and method docs. -pub struct OwningRefMut<O, T: ?Sized> { - owner: O, - reference: *mut T, -} - -/// Helper trait for an erased concrete type an owner dereferences to. -/// This is used in form of a trait object for keeping -/// something around to (virtually) call the destructor. -pub trait Erased {} -impl<T> Erased for T {} - -/// Helper trait for erasing the concrete type of what an owner dereferences to, -/// for example `Box<T> -> Box<Erased>`. This would be unneeded with -/// higher kinded types support in the language. -#[allow(unused_lifetimes)] -pub unsafe trait IntoErased<'a> { - /// Owner with the dereference type substituted to `Erased`. - type Erased; - /// Performs the type erasure. - fn into_erased(self) -> Self::Erased; -} - -/// Helper trait for erasing the concrete type of what an owner dereferences to, -/// for example `Box<T> -> Box<Erased + Send>`. This would be unneeded with -/// higher kinded types support in the language. -#[allow(unused_lifetimes)] -pub unsafe trait IntoErasedSend<'a> { - /// Owner with the dereference type substituted to `Erased + Send`. - type Erased: Send; - /// Performs the type erasure. - fn into_erased_send(self) -> Self::Erased; -} - -/// Helper trait for erasing the concrete type of what an owner dereferences to, -/// for example `Box<T> -> Box<Erased + Send + Sync>`. This would be unneeded with -/// higher kinded types support in the language. -#[allow(unused_lifetimes)] -pub unsafe trait IntoErasedSendSync<'a> { - /// Owner with the dereference type substituted to `Erased + Send + Sync`. - type Erased: Send + Sync; - /// Performs the type erasure. - fn into_erased_send_sync(self) -> Self::Erased; -} - -///////////////////////////////////////////////////////////////////////////// -// OwningRef -///////////////////////////////////////////////////////////////////////////// - -impl<O, T: ?Sized> OwningRef<O, T> { - /// Creates a new owning reference from an owner - /// initialized to the direct dereference of it. - /// - /// # Example - /// ``` - /// use rustc_data_structures::owning_ref::OwningRef; - /// - /// fn main() { - /// let owning_ref = OwningRef::new(Box::new(42)); - /// assert_eq!(*owning_ref, 42); - /// } - /// ``` - pub fn new(o: O) -> Self - where - O: StableAddress, - O: Deref<Target = T>, - { - OwningRef { reference: &*o, owner: o } - } - - /// Like `new`, but doesn’t require `O` to implement the `StableAddress` trait. - /// Instead, the caller is responsible to make the same promises as implementing the trait. - /// - /// This is useful for cases where coherence rules prevents implementing the trait - /// without adding a dependency to this crate in a third-party library. - pub unsafe fn new_assert_stable_address(o: O) -> Self - where - O: Deref<Target = T>, - { - OwningRef { reference: &*o, owner: o } - } - - /// Converts `self` into a new owning reference that points at something reachable - /// from the previous one. - /// - /// This can be a reference to a field of `U`, something reachable from a field of - /// `U`, or even something unrelated with a `'static` lifetime. - /// - /// # Example - /// ``` - /// use rustc_data_structures::owning_ref::OwningRef; - /// - /// fn main() { - /// let owning_ref = OwningRef::new(Box::new([1, 2, 3, 4])); - /// - /// // create an owning reference that points at the - /// // third element of the array. - /// let owning_ref = owning_ref.map(|array| &array[2]); - /// assert_eq!(*owning_ref, 3); - /// } - /// ``` - pub fn map<F, U: ?Sized>(self, f: F) -> OwningRef<O, U> - where - O: StableAddress, - F: FnOnce(&T) -> &U, - { - OwningRef { reference: f(&self), owner: self.owner } - } - - /// Tries to convert `self` into a new owning reference that points - /// at something reachable from the previous one. - /// - /// This can be a reference to a field of `U`, something reachable from a field of - /// `U`, or even something unrelated with a `'static` lifetime. - /// - /// # Example - /// ``` - /// use rustc_data_structures::owning_ref::OwningRef; - /// - /// fn main() { - /// let owning_ref = OwningRef::new(Box::new([1, 2, 3, 4])); - /// - /// // create an owning reference that points at the - /// // third element of the array. - /// let owning_ref = owning_ref.try_map(|array| { - /// if array[2] == 3 { Ok(&array[2]) } else { Err(()) } - /// }); - /// assert_eq!(*owning_ref.unwrap(), 3); - /// } - /// ``` - pub fn try_map<F, U: ?Sized, E>(self, f: F) -> Result<OwningRef<O, U>, E> - where - O: StableAddress, - F: FnOnce(&T) -> Result<&U, E>, - { - Ok(OwningRef { reference: f(&self)?, owner: self.owner }) - } - - /// Converts `self` into a new owning reference with a different owner type. - /// - /// The new owner type needs to still contain the original owner in some way - /// so that the reference into it remains valid. This function is marked unsafe - /// because the user needs to manually uphold this guarantee. - pub unsafe fn map_owner<F, P>(self, f: F) -> OwningRef<P, T> - where - O: StableAddress, - P: StableAddress, - F: FnOnce(O) -> P, - { - OwningRef { reference: self.reference, owner: f(self.owner) } - } - - /// Converts `self` into a new owning reference where the owner is wrapped - /// in an additional `Box<O>`. - /// - /// This can be used to safely erase the owner of any `OwningRef<O, T>` - /// to an `OwningRef<Box<Erased>, T>`. - pub fn map_owner_box(self) -> OwningRef<Box<O>, T> { - OwningRef { reference: self.reference, owner: Box::new(self.owner) } - } - - /// Erases the concrete base type of the owner with a trait object. - /// - /// This allows mixing of owned references with different owner base types. - /// - /// # Example - /// ``` - /// use rustc_data_structures::owning_ref::{OwningRef, Erased}; - /// - /// fn main() { - /// // N.B., using the concrete types here for explicitness. - /// // For less verbose code type aliases like `BoxRef` are provided. - /// - /// let owning_ref_a: OwningRef<Box<[i32; 4]>, [i32; 4]> - /// = OwningRef::new(Box::new([1, 2, 3, 4])); - /// - /// let owning_ref_b: OwningRef<Box<Vec<(i32, bool)>>, Vec<(i32, bool)>> - /// = OwningRef::new(Box::new(vec![(0, false), (1, true)])); - /// - /// let owning_ref_a: OwningRef<Box<[i32; 4]>, i32> - /// = owning_ref_a.map(|a| &a[0]); - /// - /// let owning_ref_b: OwningRef<Box<Vec<(i32, bool)>>, i32> - /// = owning_ref_b.map(|a| &a[1].0); - /// - /// let owning_refs: [OwningRef<Box<dyn Erased>, i32>; 2] - /// = [owning_ref_a.erase_owner(), owning_ref_b.erase_owner()]; - /// - /// assert_eq!(*owning_refs[0], 1); - /// assert_eq!(*owning_refs[1], 1); - /// } - /// ``` - pub fn erase_owner<'a>(self) -> OwningRef<O::Erased, T> - where - O: IntoErased<'a>, - { - OwningRef { reference: self.reference, owner: self.owner.into_erased() } - } - - /// Erases the concrete base type of the owner with a trait object which implements `Send`. - /// - /// This allows mixing of owned references with different owner base types. - pub fn erase_send_owner<'a>(self) -> OwningRef<O::Erased, T> - where - O: IntoErasedSend<'a>, - { - OwningRef { reference: self.reference, owner: self.owner.into_erased_send() } - } - - /// Erases the concrete base type of the owner with a trait object - /// which implements `Send` and `Sync`. - /// - /// This allows mixing of owned references with different owner base types. - pub fn erase_send_sync_owner<'a>(self) -> OwningRef<O::Erased, T> - where - O: IntoErasedSendSync<'a>, - { - OwningRef { reference: self.reference, owner: self.owner.into_erased_send_sync() } - } - - // UNIMPLEMENTED: wrap_owner - - // FIXME: Naming convention? - /// A getter for the underlying owner. - pub fn owner(&self) -> &O { - &self.owner - } - - // FIXME: Naming convention? - /// Discards the reference and retrieves the owner. - pub fn into_inner(self) -> O { - self.owner - } -} - -impl<O, T: ?Sized> OwningRefMut<O, T> { - /// Creates a new owning reference from an owner - /// initialized to the direct dereference of it. - /// - /// # Example - /// ``` - /// use rustc_data_structures::owning_ref::OwningRefMut; - /// - /// fn main() { - /// let owning_ref_mut = OwningRefMut::new(Box::new(42)); - /// assert_eq!(*owning_ref_mut, 42); - /// } - /// ``` - pub fn new(mut o: O) -> Self - where - O: StableAddress, - O: DerefMut<Target = T>, - { - OwningRefMut { reference: &mut *o, owner: o } - } - - /// Like `new`, but doesn’t require `O` to implement the `StableAddress` trait. - /// Instead, the caller is responsible to make the same promises as implementing the trait. - /// - /// This is useful for cases where coherence rules prevents implementing the trait - /// without adding a dependency to this crate in a third-party library. - pub unsafe fn new_assert_stable_address(mut o: O) -> Self - where - O: DerefMut<Target = T>, - { - OwningRefMut { reference: &mut *o, owner: o } - } - - /// Converts `self` into a new _shared_ owning reference that points at - /// something reachable from the previous one. - /// - /// This can be a reference to a field of `U`, something reachable from a field of - /// `U`, or even something unrelated with a `'static` lifetime. - /// - /// # Example - /// ``` - /// use rustc_data_structures::owning_ref::OwningRefMut; - /// - /// fn main() { - /// let owning_ref_mut = OwningRefMut::new(Box::new([1, 2, 3, 4])); - /// - /// // create an owning reference that points at the - /// // third element of the array. - /// let owning_ref = owning_ref_mut.map(|array| &array[2]); - /// assert_eq!(*owning_ref, 3); - /// } - /// ``` - pub fn map<F, U: ?Sized>(mut self, f: F) -> OwningRef<O, U> - where - O: StableAddress, - F: FnOnce(&mut T) -> &U, - { - OwningRef { reference: f(&mut self), owner: self.owner } - } - - /// Converts `self` into a new _mutable_ owning reference that points at - /// something reachable from the previous one. - /// - /// This can be a reference to a field of `U`, something reachable from a field of - /// `U`, or even something unrelated with a `'static` lifetime. - /// - /// # Example - /// ``` - /// use rustc_data_structures::owning_ref::OwningRefMut; - /// - /// fn main() { - /// let owning_ref_mut = OwningRefMut::new(Box::new([1, 2, 3, 4])); - /// - /// // create an owning reference that points at the - /// // third element of the array. - /// let owning_ref_mut = owning_ref_mut.map_mut(|array| &mut array[2]); - /// assert_eq!(*owning_ref_mut, 3); - /// } - /// ``` - pub fn map_mut<F, U: ?Sized>(mut self, f: F) -> OwningRefMut<O, U> - where - O: StableAddress, - F: FnOnce(&mut T) -> &mut U, - { - OwningRefMut { reference: f(&mut self), owner: self.owner } - } - - /// Tries to convert `self` into a new _shared_ owning reference that points - /// at something reachable from the previous one. - /// - /// This can be a reference to a field of `U`, something reachable from a field of - /// `U`, or even something unrelated with a `'static` lifetime. - /// - /// # Example - /// ``` - /// use rustc_data_structures::owning_ref::OwningRefMut; - /// - /// fn main() { - /// let owning_ref_mut = OwningRefMut::new(Box::new([1, 2, 3, 4])); - /// - /// // create an owning reference that points at the - /// // third element of the array. - /// let owning_ref = owning_ref_mut.try_map(|array| { - /// if array[2] == 3 { Ok(&array[2]) } else { Err(()) } - /// }); - /// assert_eq!(*owning_ref.unwrap(), 3); - /// } - /// ``` - pub fn try_map<F, U: ?Sized, E>(mut self, f: F) -> Result<OwningRef<O, U>, E> - where - O: StableAddress, - F: FnOnce(&mut T) -> Result<&U, E>, - { - Ok(OwningRef { reference: f(&mut self)?, owner: self.owner }) - } - - /// Tries to convert `self` into a new _mutable_ owning reference that points - /// at something reachable from the previous one. - /// - /// This can be a reference to a field of `U`, something reachable from a field of - /// `U`, or even something unrelated with a `'static` lifetime. - /// - /// # Example - /// ``` - /// use rustc_data_structures::owning_ref::OwningRefMut; - /// - /// fn main() { - /// let owning_ref_mut = OwningRefMut::new(Box::new([1, 2, 3, 4])); - /// - /// // create an owning reference that points at the - /// // third element of the array. - /// let owning_ref_mut = owning_ref_mut.try_map_mut(|array| { - /// if array[2] == 3 { Ok(&mut array[2]) } else { Err(()) } - /// }); - /// assert_eq!(*owning_ref_mut.unwrap(), 3); - /// } - /// ``` - pub fn try_map_mut<F, U: ?Sized, E>(mut self, f: F) -> Result<OwningRefMut<O, U>, E> - where - O: StableAddress, - F: FnOnce(&mut T) -> Result<&mut U, E>, - { - Ok(OwningRefMut { reference: f(&mut self)?, owner: self.owner }) - } - - /// Converts `self` into a new owning reference with a different owner type. - /// - /// The new owner type needs to still contain the original owner in some way - /// so that the reference into it remains valid. This function is marked unsafe - /// because the user needs to manually uphold this guarantee. - pub unsafe fn map_owner<F, P>(self, f: F) -> OwningRefMut<P, T> - where - O: StableAddress, - P: StableAddress, - F: FnOnce(O) -> P, - { - OwningRefMut { reference: self.reference, owner: f(self.owner) } - } - - /// Converts `self` into a new owning reference where the owner is wrapped - /// in an additional `Box<O>`. - /// - /// This can be used to safely erase the owner of any `OwningRefMut<O, T>` - /// to an `OwningRefMut<Box<Erased>, T>`. - pub fn map_owner_box(self) -> OwningRefMut<Box<O>, T> { - OwningRefMut { reference: self.reference, owner: Box::new(self.owner) } - } - - /// Erases the concrete base type of the owner with a trait object. - /// - /// This allows mixing of owned references with different owner base types. - /// - /// # Example - /// ``` - /// use rustc_data_structures::owning_ref::{OwningRefMut, Erased}; - /// - /// fn main() { - /// // N.B., using the concrete types here for explicitness. - /// // For less verbose code type aliases like `BoxRef` are provided. - /// - /// let owning_ref_mut_a: OwningRefMut<Box<[i32; 4]>, [i32; 4]> - /// = OwningRefMut::new(Box::new([1, 2, 3, 4])); - /// - /// let owning_ref_mut_b: OwningRefMut<Box<Vec<(i32, bool)>>, Vec<(i32, bool)>> - /// = OwningRefMut::new(Box::new(vec![(0, false), (1, true)])); - /// - /// let owning_ref_mut_a: OwningRefMut<Box<[i32; 4]>, i32> - /// = owning_ref_mut_a.map_mut(|a| &mut a[0]); - /// - /// let owning_ref_mut_b: OwningRefMut<Box<Vec<(i32, bool)>>, i32> - /// = owning_ref_mut_b.map_mut(|a| &mut a[1].0); - /// - /// let owning_refs_mut: [OwningRefMut<Box<dyn Erased>, i32>; 2] - /// = [owning_ref_mut_a.erase_owner(), owning_ref_mut_b.erase_owner()]; - /// - /// assert_eq!(*owning_refs_mut[0], 1); - /// assert_eq!(*owning_refs_mut[1], 1); - /// } - /// ``` - pub fn erase_owner<'a>(self) -> OwningRefMut<O::Erased, T> - where - O: IntoErased<'a>, - { - OwningRefMut { reference: self.reference, owner: self.owner.into_erased() } - } - - // UNIMPLEMENTED: wrap_owner - - // FIXME: Naming convention? - /// A getter for the underlying owner. - pub fn owner(&self) -> &O { - &self.owner - } - - // FIXME: Naming convention? - /// Discards the reference and retrieves the owner. - pub fn into_inner(self) -> O { - self.owner - } -} - -///////////////////////////////////////////////////////////////////////////// -// OwningHandle -///////////////////////////////////////////////////////////////////////////// - -use std::ops::{Deref, DerefMut}; - -/// `OwningHandle` is a complement to `OwningRef`. Where `OwningRef` allows -/// consumers to pass around an owned object and a dependent reference, -/// `OwningHandle` contains an owned object and a dependent _object_. -/// -/// `OwningHandle` can encapsulate a `RefMut` along with its associated -/// `RefCell`, or an `RwLockReadGuard` along with its associated `RwLock`. -/// However, the API is completely generic and there are no restrictions on -/// what types of owning and dependent objects may be used. -/// -/// `OwningHandle` is created by passing an owner object (which dereferences -/// to a stable address) along with a callback which receives a pointer to -/// that stable location. The callback may then dereference the pointer and -/// mint a dependent object, with the guarantee that the returned object will -/// not outlive the referent of the pointer. -/// -/// Since the callback needs to dereference a raw pointer, it requires `unsafe` -/// code. To avoid forcing this unsafety on most callers, the `ToHandle` trait is -/// implemented for common data structures. Types that implement `ToHandle` can -/// be wrapped into an `OwningHandle` without passing a callback. -pub struct OwningHandle<O, H> -where - O: StableAddress, - H: Deref, -{ - handle: H, - _owner: O, -} - -impl<O, H> Deref for OwningHandle<O, H> -where - O: StableAddress, - H: Deref, -{ - type Target = H::Target; - fn deref(&self) -> &H::Target { - self.handle.deref() - } -} - -unsafe impl<O, H> StableAddress for OwningHandle<O, H> -where - O: StableAddress, - H: StableAddress, -{ -} - -impl<O, H> DerefMut for OwningHandle<O, H> -where - O: StableAddress, - H: DerefMut, -{ - fn deref_mut(&mut self) -> &mut H::Target { - self.handle.deref_mut() - } -} - -/// Trait to implement the conversion of owner to handle for common types. -pub trait ToHandle { - /// The type of handle to be encapsulated by the OwningHandle. - type Handle: Deref; - - /// Given an appropriately-long-lived pointer to ourselves, create a - /// handle to be encapsulated by the `OwningHandle`. - unsafe fn to_handle(x: *const Self) -> Self::Handle; -} - -/// Trait to implement the conversion of owner to mutable handle for common types. -pub trait ToHandleMut { - /// The type of handle to be encapsulated by the OwningHandle. - type HandleMut: DerefMut; - - /// Given an appropriately-long-lived pointer to ourselves, create a - /// mutable handle to be encapsulated by the `OwningHandle`. - unsafe fn to_handle_mut(x: *const Self) -> Self::HandleMut; -} - -impl<O, H> OwningHandle<O, H> -where - O: StableAddress<Target: ToHandle<Handle = H>>, - H: Deref, -{ - /// Creates a new `OwningHandle` for a type that implements `ToHandle`. For types - /// that don't implement `ToHandle`, callers may invoke `new_with_fn`, which accepts - /// a callback to perform the conversion. - pub fn new(o: O) -> Self { - OwningHandle::new_with_fn(o, |x| unsafe { O::Target::to_handle(x) }) - } -} - -impl<O, H> OwningHandle<O, H> -where - O: StableAddress<Target: ToHandleMut<HandleMut = H>>, - H: DerefMut, -{ - /// Creates a new mutable `OwningHandle` for a type that implements `ToHandleMut`. - pub fn new_mut(o: O) -> Self { - OwningHandle::new_with_fn(o, |x| unsafe { O::Target::to_handle_mut(x) }) - } -} - -impl<O, H> OwningHandle<O, H> -where - O: StableAddress, - H: Deref, -{ - /// Creates a new OwningHandle. The provided callback will be invoked with - /// a pointer to the object owned by `o`, and the returned value is stored - /// as the object to which this `OwningHandle` will forward `Deref` and - /// `DerefMut`. - pub fn new_with_fn<F>(o: O, f: F) -> Self - where - F: FnOnce(*const O::Target) -> H, - { - let h: H; - { - h = f(o.deref() as *const O::Target); - } - - OwningHandle { handle: h, _owner: o } - } - - /// Creates a new OwningHandle. The provided callback will be invoked with - /// a pointer to the object owned by `o`, and the returned value is stored - /// as the object to which this `OwningHandle` will forward `Deref` and - /// `DerefMut`. - pub fn try_new<F, E>(o: O, f: F) -> Result<Self, E> - where - F: FnOnce(*const O::Target) -> Result<H, E>, - { - let h: H; - { - h = f(o.deref() as *const O::Target)?; - } - - Ok(OwningHandle { handle: h, _owner: o }) - } -} - -///////////////////////////////////////////////////////////////////////////// -// std traits -///////////////////////////////////////////////////////////////////////////// - -use std::borrow::Borrow; -use std::cmp::Ordering; -use std::fmt::{self, Debug}; -use std::hash::{Hash, Hasher}; - -impl<O, T: ?Sized> Deref for OwningRef<O, T> { - type Target = T; - - fn deref(&self) -> &T { - unsafe { &*self.reference } - } -} - -impl<O, T: ?Sized> Deref for OwningRefMut<O, T> { - type Target = T; - - fn deref(&self) -> &T { - unsafe { &*self.reference } - } -} - -impl<O, T: ?Sized> DerefMut for OwningRefMut<O, T> { - fn deref_mut(&mut self) -> &mut T { - unsafe { &mut *self.reference } - } -} - -unsafe impl<O, T: ?Sized> StableAddress for OwningRef<O, T> {} - -impl<O, T: ?Sized> AsRef<T> for OwningRef<O, T> { - fn as_ref(&self) -> &T { - self - } -} - -impl<O, T: ?Sized> AsRef<T> for OwningRefMut<O, T> { - fn as_ref(&self) -> &T { - self - } -} - -impl<O, T: ?Sized> AsMut<T> for OwningRefMut<O, T> { - fn as_mut(&mut self) -> &mut T { - self - } -} - -impl<O, T: ?Sized> Borrow<T> for OwningRef<O, T> { - fn borrow(&self) -> &T { - self - } -} - -impl<O, T: ?Sized> From<O> for OwningRef<O, T> -where - O: StableAddress, - O: Deref<Target = T>, -{ - fn from(owner: O) -> Self { - OwningRef::new(owner) - } -} - -impl<O, T: ?Sized> From<O> for OwningRefMut<O, T> -where - O: StableAddress, - O: DerefMut<Target = T>, -{ - fn from(owner: O) -> Self { - OwningRefMut::new(owner) - } -} - -impl<O, T: ?Sized> From<OwningRefMut<O, T>> for OwningRef<O, T> -where - O: StableAddress, - O: DerefMut<Target = T>, -{ - fn from(other: OwningRefMut<O, T>) -> Self { - OwningRef { owner: other.owner, reference: other.reference } - } -} - -// ^ FIXME: Is an Into impl for calling into_inner() possible as well? - -impl<O, T: ?Sized> Debug for OwningRef<O, T> -where - O: Debug, - T: Debug, -{ - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - write!(f, "OwningRef {{ owner: {:?}, reference: {:?} }}", self.owner(), &**self) - } -} - -impl<O, T: ?Sized> Debug for OwningRefMut<O, T> -where - O: Debug, - T: Debug, -{ - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - write!(f, "OwningRefMut {{ owner: {:?}, reference: {:?} }}", self.owner(), &**self) - } -} - -impl<O, T: ?Sized> Clone for OwningRef<O, T> -where - O: CloneStableAddress, -{ - fn clone(&self) -> Self { - OwningRef { owner: self.owner.clone(), reference: self.reference } - } -} - -unsafe impl<O, T: ?Sized> CloneStableAddress for OwningRef<O, T> where O: CloneStableAddress {} - -unsafe impl<O, T: ?Sized> Send for OwningRef<O, T> -where - O: Send, - for<'a> &'a T: Send, -{ -} -unsafe impl<O, T: ?Sized> Sync for OwningRef<O, T> -where - O: Sync, - for<'a> &'a T: Sync, -{ -} - -unsafe impl<O, T: ?Sized> Send for OwningRefMut<O, T> -where - O: Send, - for<'a> &'a mut T: Send, -{ -} -unsafe impl<O, T: ?Sized> Sync for OwningRefMut<O, T> -where - O: Sync, - for<'a> &'a mut T: Sync, -{ -} - -impl Debug for dyn Erased { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - write!(f, "<Erased>",) - } -} - -impl<O, T: ?Sized> PartialEq for OwningRef<O, T> -where - T: PartialEq, -{ - fn eq(&self, other: &Self) -> bool { - self.deref().eq(other.deref()) - } -} - -impl<O, T: ?Sized> Eq for OwningRef<O, T> where T: Eq {} - -impl<O, T: ?Sized> PartialOrd for OwningRef<O, T> -where - T: PartialOrd, -{ - fn partial_cmp(&self, other: &Self) -> Option<Ordering> { - self.deref().partial_cmp(other.deref()) - } -} - -impl<O, T: ?Sized> Ord for OwningRef<O, T> -where - T: Ord, -{ - fn cmp(&self, other: &Self) -> Ordering { - self.deref().cmp(other.deref()) - } -} - -impl<O, T: ?Sized> Hash for OwningRef<O, T> -where - T: Hash, -{ - fn hash<H: Hasher>(&self, state: &mut H) { - self.deref().hash(state); - } -} - -impl<O, T: ?Sized> PartialEq for OwningRefMut<O, T> -where - T: PartialEq, -{ - fn eq(&self, other: &Self) -> bool { - self.deref().eq(other.deref()) - } -} - -impl<O, T: ?Sized> Eq for OwningRefMut<O, T> where T: Eq {} - -impl<O, T: ?Sized> PartialOrd for OwningRefMut<O, T> -where - T: PartialOrd, -{ - fn partial_cmp(&self, other: &Self) -> Option<Ordering> { - self.deref().partial_cmp(other.deref()) - } -} - -impl<O, T: ?Sized> Ord for OwningRefMut<O, T> -where - T: Ord, -{ - fn cmp(&self, other: &Self) -> Ordering { - self.deref().cmp(other.deref()) - } -} - -impl<O, T: ?Sized> Hash for OwningRefMut<O, T> -where - T: Hash, -{ - fn hash<H: Hasher>(&self, state: &mut H) { - self.deref().hash(state); - } -} - -///////////////////////////////////////////////////////////////////////////// -// std types integration and convenience type defs -///////////////////////////////////////////////////////////////////////////// - -use std::cell::{Ref, RefCell, RefMut}; -use std::rc::Rc; -use std::sync::Arc; -use std::sync::{MutexGuard, RwLockReadGuard, RwLockWriteGuard}; - -impl<T: 'static> ToHandle for RefCell<T> { - type Handle = Ref<'static, T>; - unsafe fn to_handle(x: *const Self) -> Self::Handle { - (*x).borrow() - } -} - -impl<T: 'static> ToHandleMut for RefCell<T> { - type HandleMut = RefMut<'static, T>; - unsafe fn to_handle_mut(x: *const Self) -> Self::HandleMut { - (*x).borrow_mut() - } -} - -// N.B., implementing ToHandle{,Mut} for Mutex and RwLock requires a decision -// about which handle creation to use (i.e., read() vs try_read()) as well as -// what to do with error results. - -/// Typedef of an owning reference that uses a `Box` as the owner. -pub type BoxRef<T, U = T> = OwningRef<Box<T>, U>; -/// Typedef of an owning reference that uses a `Vec` as the owner. -pub type VecRef<T, U = T> = OwningRef<Vec<T>, U>; -/// Typedef of an owning reference that uses a `String` as the owner. -pub type StringRef = OwningRef<String, str>; - -/// Typedef of an owning reference that uses an `Rc` as the owner. -pub type RcRef<T, U = T> = OwningRef<Rc<T>, U>; -/// Typedef of an owning reference that uses an `Arc` as the owner. -pub type ArcRef<T, U = T> = OwningRef<Arc<T>, U>; - -/// Typedef of an owning reference that uses a `Ref` as the owner. -pub type RefRef<'a, T, U = T> = OwningRef<Ref<'a, T>, U>; -/// Typedef of an owning reference that uses a `RefMut` as the owner. -pub type RefMutRef<'a, T, U = T> = OwningRef<RefMut<'a, T>, U>; -/// Typedef of an owning reference that uses a `MutexGuard` as the owner. -pub type MutexGuardRef<'a, T, U = T> = OwningRef<MutexGuard<'a, T>, U>; -/// Typedef of an owning reference that uses an `RwLockReadGuard` as the owner. -pub type RwLockReadGuardRef<'a, T, U = T> = OwningRef<RwLockReadGuard<'a, T>, U>; -/// Typedef of an owning reference that uses an `RwLockWriteGuard` as the owner. -pub type RwLockWriteGuardRef<'a, T, U = T> = OwningRef<RwLockWriteGuard<'a, T>, U>; - -/// Typedef of a mutable owning reference that uses a `Box` as the owner. -pub type BoxRefMut<T, U = T> = OwningRefMut<Box<T>, U>; -/// Typedef of a mutable owning reference that uses a `Vec` as the owner. -pub type VecRefMut<T, U = T> = OwningRefMut<Vec<T>, U>; -/// Typedef of a mutable owning reference that uses a `String` as the owner. -pub type StringRefMut = OwningRefMut<String, str>; - -/// Typedef of a mutable owning reference that uses a `RefMut` as the owner. -pub type RefMutRefMut<'a, T, U = T> = OwningRefMut<RefMut<'a, T>, U>; -/// Typedef of a mutable owning reference that uses a `MutexGuard` as the owner. -pub type MutexGuardRefMut<'a, T, U = T> = OwningRefMut<MutexGuard<'a, T>, U>; -/// Typedef of a mutable owning reference that uses an `RwLockWriteGuard` as the owner. -pub type RwLockWriteGuardRefMut<'a, T, U = T> = OwningRef<RwLockWriteGuard<'a, T>, U>; - -unsafe impl<'a, T: 'a> IntoErased<'a> for Box<T> { - type Erased = Box<dyn Erased + 'a>; - fn into_erased(self) -> Self::Erased { - self - } -} -unsafe impl<'a, T: 'a> IntoErased<'a> for Rc<T> { - type Erased = Rc<dyn Erased + 'a>; - fn into_erased(self) -> Self::Erased { - self - } -} -unsafe impl<'a, T: 'a> IntoErased<'a> for Arc<T> { - type Erased = Arc<dyn Erased + 'a>; - fn into_erased(self) -> Self::Erased { - self - } -} - -unsafe impl<'a, T: Send + 'a> IntoErasedSend<'a> for Box<T> { - type Erased = Box<dyn Erased + Send + 'a>; - fn into_erased_send(self) -> Self::Erased { - self - } -} - -unsafe impl<'a, T: Send + 'a> IntoErasedSendSync<'a> for Box<T> { - type Erased = Box<dyn Erased + Sync + Send + 'a>; - fn into_erased_send_sync(self) -> Self::Erased { - let result: Box<dyn Erased + Send + 'a> = self; - // This is safe since Erased can always implement Sync - // Only the destructor is available and it takes &mut self - unsafe { mem::transmute(result) } - } -} - -unsafe impl<'a, T: Send + Sync + 'a> IntoErasedSendSync<'a> for Arc<T> { - type Erased = Arc<dyn Erased + Send + Sync + 'a>; - fn into_erased_send_sync(self) -> Self::Erased { - self - } -} - -/// Typedef of an owning reference that uses an erased `Box` as the owner. -pub type ErasedBoxRef<U> = OwningRef<Box<dyn Erased>, U>; -/// Typedef of an owning reference that uses an erased `Rc` as the owner. -pub type ErasedRcRef<U> = OwningRef<Rc<dyn Erased>, U>; -/// Typedef of an owning reference that uses an erased `Arc` as the owner. -pub type ErasedArcRef<U> = OwningRef<Arc<dyn Erased>, U>; - -/// Typedef of a mutable owning reference that uses an erased `Box` as the owner. -pub type ErasedBoxRefMut<U> = OwningRefMut<Box<dyn Erased>, U>; - -#[cfg(test)] -mod tests; diff --git a/compiler/rustc_data_structures/src/owning_ref/tests.rs b/compiler/rustc_data_structures/src/owning_ref/tests.rs deleted file mode 100644 index a9b187c4c..000000000 --- a/compiler/rustc_data_structures/src/owning_ref/tests.rs +++ /dev/null @@ -1,711 +0,0 @@ -// FIXME: owning_ref is not sound under stacked borrows. Preferably, get rid of it. -#[cfg(not(miri))] -mod owning_ref { - use super::super::OwningRef; - use super::super::{BoxRef, Erased, ErasedBoxRef, RcRef}; - use std::cmp::Ordering; - use std::collections::hash_map::DefaultHasher; - use std::collections::HashMap; - use std::hash::{Hash, Hasher}; - use std::rc::Rc; - - #[derive(Debug, PartialEq)] - struct Example(u32, String, [u8; 3]); - fn example() -> Example { - Example(42, "hello world".to_string(), [1, 2, 3]) - } - - #[test] - fn new_deref() { - let or: OwningRef<Box<()>, ()> = OwningRef::new(Box::new(())); - assert_eq!(&*or, &()); - } - - #[test] - fn into() { - let or: OwningRef<Box<()>, ()> = Box::new(()).into(); - assert_eq!(&*or, &()); - } - - #[test] - fn map_offset_ref() { - let or: BoxRef<Example> = Box::new(example()).into(); - let or: BoxRef<_, u32> = or.map(|x| &x.0); - assert_eq!(&*or, &42); - - let or: BoxRef<Example> = Box::new(example()).into(); - let or: BoxRef<_, u8> = or.map(|x| &x.2[1]); - assert_eq!(&*or, &2); - } - - #[test] - fn map_heap_ref() { - let or: BoxRef<Example> = Box::new(example()).into(); - let or: BoxRef<_, str> = or.map(|x| &x.1[..5]); - assert_eq!(&*or, "hello"); - } - - #[test] - fn map_static_ref() { - let or: BoxRef<()> = Box::new(()).into(); - let or: BoxRef<_, str> = or.map(|_| "hello"); - assert_eq!(&*or, "hello"); - } - - #[test] - fn map_chained() { - let or: BoxRef<String> = Box::new(example().1).into(); - let or: BoxRef<_, str> = or.map(|x| &x[1..5]); - let or: BoxRef<_, str> = or.map(|x| &x[..2]); - assert_eq!(&*or, "el"); - } - - #[test] - fn map_chained_inference() { - let or = BoxRef::new(Box::new(example().1)).map(|x| &x[..5]).map(|x| &x[1..3]); - assert_eq!(&*or, "el"); - } - - #[test] - fn owner() { - let or: BoxRef<String> = Box::new(example().1).into(); - let or = or.map(|x| &x[..5]); - assert_eq!(&*or, "hello"); - assert_eq!(&**or.owner(), "hello world"); - } - - #[test] - fn into_inner() { - let or: BoxRef<String> = Box::new(example().1).into(); - let or = or.map(|x| &x[..5]); - assert_eq!(&*or, "hello"); - let s = *or.into_inner(); - assert_eq!(&s, "hello world"); - } - - #[test] - fn fmt_debug() { - let or: BoxRef<String> = Box::new(example().1).into(); - let or = or.map(|x| &x[..5]); - let s = format!("{:?}", or); - assert_eq!(&s, "OwningRef { owner: \"hello world\", reference: \"hello\" }"); - } - - #[test] - fn erased_owner() { - let o1: BoxRef<Example, str> = BoxRef::new(Box::new(example())).map(|x| &x.1[..]); - - let o2: BoxRef<String, str> = BoxRef::new(Box::new(example().1)).map(|x| &x[..]); - - let os: Vec<ErasedBoxRef<str>> = vec![o1.erase_owner(), o2.erase_owner()]; - assert!(os.iter().all(|e| &e[..] == "hello world")); - } - - #[test] - fn raii_locks() { - use super::super::{MutexGuardRef, RwLockReadGuardRef, RwLockWriteGuardRef}; - use super::super::{RefMutRef, RefRef}; - use std::cell::RefCell; - use std::sync::{Mutex, RwLock}; - - { - let a = RefCell::new(1); - let a = { - let a = RefRef::new(a.borrow()); - assert_eq!(*a, 1); - a - }; - assert_eq!(*a, 1); - drop(a); - } - { - let a = RefCell::new(1); - let a = { - let a = RefMutRef::new(a.borrow_mut()); - assert_eq!(*a, 1); - a - }; - assert_eq!(*a, 1); - drop(a); - } - { - let a = Mutex::new(1); - let a = { - let a = MutexGuardRef::new(a.lock().unwrap()); - assert_eq!(*a, 1); - a - }; - assert_eq!(*a, 1); - drop(a); - } - { - let a = RwLock::new(1); - let a = { - let a = RwLockReadGuardRef::new(a.read().unwrap()); - assert_eq!(*a, 1); - a - }; - assert_eq!(*a, 1); - drop(a); - } - { - let a = RwLock::new(1); - let a = { - let a = RwLockWriteGuardRef::new(a.write().unwrap()); - assert_eq!(*a, 1); - a - }; - assert_eq!(*a, 1); - drop(a); - } - } - - #[test] - fn eq() { - let or1: BoxRef<[u8]> = BoxRef::new(vec![1, 2, 3].into_boxed_slice()); - let or2: BoxRef<[u8]> = BoxRef::new(vec![1, 2, 3].into_boxed_slice()); - assert_eq!(or1.eq(&or2), true); - } - - #[test] - fn cmp() { - let or1: BoxRef<[u8]> = BoxRef::new(vec![1, 2, 3].into_boxed_slice()); - let or2: BoxRef<[u8]> = BoxRef::new(vec![4, 5, 6].into_boxed_slice()); - assert_eq!(or1.cmp(&or2), Ordering::Less); - } - - #[test] - fn partial_cmp() { - let or1: BoxRef<[u8]> = BoxRef::new(vec![4, 5, 6].into_boxed_slice()); - let or2: BoxRef<[u8]> = BoxRef::new(vec![1, 2, 3].into_boxed_slice()); - assert_eq!(or1.partial_cmp(&or2), Some(Ordering::Greater)); - } - - #[test] - fn hash() { - let mut h1 = DefaultHasher::new(); - let mut h2 = DefaultHasher::new(); - - let or1: BoxRef<[u8]> = BoxRef::new(vec![1, 2, 3].into_boxed_slice()); - let or2: BoxRef<[u8]> = BoxRef::new(vec![1, 2, 3].into_boxed_slice()); - - or1.hash(&mut h1); - or2.hash(&mut h2); - - assert_eq!(h1.finish(), h2.finish()); - } - - #[test] - fn borrow() { - let mut hash = HashMap::new(); - let key = RcRef::<String>::new(Rc::new("foo-bar".to_string())).map(|s| &s[..]); - - hash.insert(key.clone().map(|s| &s[..3]), 42); - hash.insert(key.clone().map(|s| &s[4..]), 23); - - assert_eq!(hash.get("foo"), Some(&42)); - assert_eq!(hash.get("bar"), Some(&23)); - } - - #[test] - fn total_erase() { - let a: OwningRef<Vec<u8>, [u8]> = OwningRef::new(vec![]).map(|x| &x[..]); - let b: OwningRef<Box<[u8]>, [u8]> = - OwningRef::new(vec![].into_boxed_slice()).map(|x| &x[..]); - - let c: OwningRef<Rc<Vec<u8>>, [u8]> = unsafe { a.map_owner(Rc::new) }; - let d: OwningRef<Rc<Box<[u8]>>, [u8]> = unsafe { b.map_owner(Rc::new) }; - - let e: OwningRef<Rc<dyn Erased>, [u8]> = c.erase_owner(); - let f: OwningRef<Rc<dyn Erased>, [u8]> = d.erase_owner(); - - let _g = e.clone(); - let _h = f.clone(); - } - - #[test] - fn total_erase_box() { - let a: OwningRef<Vec<u8>, [u8]> = OwningRef::new(vec![]).map(|x| &x[..]); - let b: OwningRef<Box<[u8]>, [u8]> = - OwningRef::new(vec![].into_boxed_slice()).map(|x| &x[..]); - - let c: OwningRef<Box<Vec<u8>>, [u8]> = a.map_owner_box(); - let d: OwningRef<Box<Box<[u8]>>, [u8]> = b.map_owner_box(); - - let _e: OwningRef<Box<dyn Erased>, [u8]> = c.erase_owner(); - let _f: OwningRef<Box<dyn Erased>, [u8]> = d.erase_owner(); - } - - #[test] - fn try_map1() { - use std::any::Any; - - let x = Box::new(123_i32); - let y: Box<dyn Any> = x; - - assert!(OwningRef::new(y).try_map(|x| x.downcast_ref::<i32>().ok_or(())).is_ok()); - } - - #[test] - fn try_map2() { - use std::any::Any; - - let x = Box::new(123_i32); - let y: Box<dyn Any> = x; - - assert!(!OwningRef::new(y).try_map(|x| x.downcast_ref::<i32>().ok_or(())).is_err()); - } -} - -mod owning_handle { - use super::super::OwningHandle; - use super::super::RcRef; - use std::cell::RefCell; - use std::rc::Rc; - use std::sync::Arc; - use std::sync::RwLock; - - #[test] - fn owning_handle() { - use std::cell::RefCell; - let cell = Rc::new(RefCell::new(2)); - let cell_ref = RcRef::new(cell); - let mut handle = - OwningHandle::new_with_fn(cell_ref, |x| unsafe { x.as_ref() }.unwrap().borrow_mut()); - assert_eq!(*handle, 2); - *handle = 3; - assert_eq!(*handle, 3); - } - - #[test] - fn try_owning_handle_ok() { - use std::cell::RefCell; - let cell = Rc::new(RefCell::new(2)); - let cell_ref = RcRef::new(cell); - let mut handle = OwningHandle::try_new::<_, ()>(cell_ref, |x| { - Ok(unsafe { x.as_ref() }.unwrap().borrow_mut()) - }) - .unwrap(); - assert_eq!(*handle, 2); - *handle = 3; - assert_eq!(*handle, 3); - } - - #[test] - fn try_owning_handle_err() { - use std::cell::RefCell; - let cell = Rc::new(RefCell::new(2)); - let cell_ref = RcRef::new(cell); - let handle = OwningHandle::try_new::<_, ()>(cell_ref, |x| { - if false { - return Ok(unsafe { x.as_ref() }.unwrap().borrow_mut()); - } - Err(()) - }); - assert!(handle.is_err()); - } - - #[test] - fn nested() { - use std::cell::RefCell; - use std::sync::{Arc, RwLock}; - - let result = { - let complex = Rc::new(RefCell::new(Arc::new(RwLock::new("someString")))); - let curr = RcRef::new(complex); - let curr = - OwningHandle::new_with_fn(curr, |x| unsafe { x.as_ref() }.unwrap().borrow_mut()); - let mut curr = OwningHandle::new_with_fn(curr, |x| { - unsafe { x.as_ref() }.unwrap().try_write().unwrap() - }); - assert_eq!(*curr, "someString"); - *curr = "someOtherString"; - curr - }; - assert_eq!(*result, "someOtherString"); - } - - #[test] - fn owning_handle_safe() { - use std::cell::RefCell; - let cell = Rc::new(RefCell::new(2)); - let cell_ref = RcRef::new(cell); - let handle = OwningHandle::new(cell_ref); - assert_eq!(*handle, 2); - } - - #[test] - fn owning_handle_mut_safe() { - use std::cell::RefCell; - let cell = Rc::new(RefCell::new(2)); - let cell_ref = RcRef::new(cell); - let mut handle = OwningHandle::new_mut(cell_ref); - assert_eq!(*handle, 2); - *handle = 3; - assert_eq!(*handle, 3); - } - - #[test] - fn owning_handle_safe_2() { - let result = { - let complex = Rc::new(RefCell::new(Arc::new(RwLock::new("someString")))); - let curr = RcRef::new(complex); - let curr = - OwningHandle::new_with_fn(curr, |x| unsafe { x.as_ref() }.unwrap().borrow_mut()); - let mut curr = OwningHandle::new_with_fn(curr, |x| { - unsafe { x.as_ref() }.unwrap().try_write().unwrap() - }); - assert_eq!(*curr, "someString"); - *curr = "someOtherString"; - curr - }; - assert_eq!(*result, "someOtherString"); - } -} - -// FIXME: owning_ref is not sound under stacked borrows. Preferably, get rid of it. -#[cfg(not(miri))] -mod owning_ref_mut { - use super::super::BoxRef; - use super::super::{BoxRefMut, Erased, ErasedBoxRefMut, OwningRefMut}; - use std::cmp::Ordering; - use std::collections::hash_map::DefaultHasher; - use std::collections::HashMap; - use std::hash::{Hash, Hasher}; - - #[derive(Debug, PartialEq)] - struct Example(u32, String, [u8; 3]); - fn example() -> Example { - Example(42, "hello world".to_string(), [1, 2, 3]) - } - - #[test] - fn new_deref() { - let or: OwningRefMut<Box<()>, ()> = OwningRefMut::new(Box::new(())); - assert_eq!(&*or, &()); - } - - #[test] - fn new_deref_mut() { - let mut or: OwningRefMut<Box<()>, ()> = OwningRefMut::new(Box::new(())); - assert_eq!(&mut *or, &mut ()); - } - - #[test] - fn mutate() { - let mut or: OwningRefMut<Box<usize>, usize> = OwningRefMut::new(Box::new(0)); - assert_eq!(&*or, &0); - *or = 1; - assert_eq!(&*or, &1); - } - - #[test] - fn into() { - let or: OwningRefMut<Box<()>, ()> = Box::new(()).into(); - assert_eq!(&*or, &()); - } - - #[test] - fn map_offset_ref() { - let or: BoxRefMut<Example> = Box::new(example()).into(); - let or: BoxRef<_, u32> = or.map(|x| &mut x.0); - assert_eq!(&*or, &42); - - let or: BoxRefMut<Example> = Box::new(example()).into(); - let or: BoxRef<_, u8> = or.map(|x| &mut x.2[1]); - assert_eq!(&*or, &2); - } - - #[test] - fn map_heap_ref() { - let or: BoxRefMut<Example> = Box::new(example()).into(); - let or: BoxRef<_, str> = or.map(|x| &mut x.1[..5]); - assert_eq!(&*or, "hello"); - } - - #[test] - fn map_static_ref() { - let or: BoxRefMut<()> = Box::new(()).into(); - let or: BoxRef<_, str> = or.map(|_| "hello"); - assert_eq!(&*or, "hello"); - } - - #[test] - fn map_mut_offset_ref() { - let or: BoxRefMut<Example> = Box::new(example()).into(); - let or: BoxRefMut<_, u32> = or.map_mut(|x| &mut x.0); - assert_eq!(&*or, &42); - - let or: BoxRefMut<Example> = Box::new(example()).into(); - let or: BoxRefMut<_, u8> = or.map_mut(|x| &mut x.2[1]); - assert_eq!(&*or, &2); - } - - #[test] - fn map_mut_heap_ref() { - let or: BoxRefMut<Example> = Box::new(example()).into(); - let or: BoxRefMut<_, str> = or.map_mut(|x| &mut x.1[..5]); - assert_eq!(&*or, "hello"); - } - - #[test] - fn map_mut_static_ref() { - static mut MUT_S: [u8; 5] = *b"hello"; - - let mut_s: &'static mut [u8] = unsafe { &mut MUT_S }; - - let or: BoxRefMut<()> = Box::new(()).into(); - let or: BoxRefMut<_, [u8]> = or.map_mut(move |_| mut_s); - assert_eq!(&*or, b"hello"); - } - - #[test] - fn map_mut_chained() { - let or: BoxRefMut<String> = Box::new(example().1).into(); - let or: BoxRefMut<_, str> = or.map_mut(|x| &mut x[1..5]); - let or: BoxRefMut<_, str> = or.map_mut(|x| &mut x[..2]); - assert_eq!(&*or, "el"); - } - - #[test] - fn map_chained_inference() { - let or = BoxRefMut::new(Box::new(example().1)) - .map_mut(|x| &mut x[..5]) - .map_mut(|x| &mut x[1..3]); - assert_eq!(&*or, "el"); - } - - #[test] - fn try_map_mut() { - let or: BoxRefMut<String> = Box::new(example().1).into(); - let or: Result<BoxRefMut<_, str>, ()> = or.try_map_mut(|x| Ok(&mut x[1..5])); - assert_eq!(&*or.unwrap(), "ello"); - - let or: BoxRefMut<String> = Box::new(example().1).into(); - let or: Result<BoxRefMut<_, str>, ()> = or.try_map_mut(|_| Err(())); - assert!(or.is_err()); - } - - #[test] - fn owner() { - let or: BoxRefMut<String> = Box::new(example().1).into(); - let or = or.map_mut(|x| &mut x[..5]); - assert_eq!(&*or, "hello"); - assert_eq!(&**or.owner(), "hello world"); - } - - #[test] - fn into_inner() { - let or: BoxRefMut<String> = Box::new(example().1).into(); - let or = or.map_mut(|x| &mut x[..5]); - assert_eq!(&*or, "hello"); - let s = *or.into_inner(); - assert_eq!(&s, "hello world"); - } - - #[test] - fn fmt_debug() { - let or: BoxRefMut<String> = Box::new(example().1).into(); - let or = or.map_mut(|x| &mut x[..5]); - let s = format!("{:?}", or); - assert_eq!(&s, "OwningRefMut { owner: \"hello world\", reference: \"hello\" }"); - } - - #[test] - fn erased_owner() { - let o1: BoxRefMut<Example, str> = - BoxRefMut::new(Box::new(example())).map_mut(|x| &mut x.1[..]); - - let o2: BoxRefMut<String, str> = - BoxRefMut::new(Box::new(example().1)).map_mut(|x| &mut x[..]); - - let os: Vec<ErasedBoxRefMut<str>> = vec![o1.erase_owner(), o2.erase_owner()]; - assert!(os.iter().all(|e| &e[..] == "hello world")); - } - - #[test] - fn raii_locks() { - use super::super::RefMutRefMut; - use super::super::{MutexGuardRefMut, RwLockWriteGuardRefMut}; - use std::cell::RefCell; - use std::sync::{Mutex, RwLock}; - - { - let a = RefCell::new(1); - let a = { - let a = RefMutRefMut::new(a.borrow_mut()); - assert_eq!(*a, 1); - a - }; - assert_eq!(*a, 1); - drop(a); - } - { - let a = Mutex::new(1); - let a = { - let a = MutexGuardRefMut::new(a.lock().unwrap()); - assert_eq!(*a, 1); - a - }; - assert_eq!(*a, 1); - drop(a); - } - { - let a = RwLock::new(1); - let a = { - let a = RwLockWriteGuardRefMut::new(a.write().unwrap()); - assert_eq!(*a, 1); - a - }; - assert_eq!(*a, 1); - drop(a); - } - } - - #[test] - fn eq() { - let or1: BoxRefMut<[u8]> = BoxRefMut::new(vec![1, 2, 3].into_boxed_slice()); - let or2: BoxRefMut<[u8]> = BoxRefMut::new(vec![1, 2, 3].into_boxed_slice()); - assert_eq!(or1.eq(&or2), true); - } - - #[test] - fn cmp() { - let or1: BoxRefMut<[u8]> = BoxRefMut::new(vec![1, 2, 3].into_boxed_slice()); - let or2: BoxRefMut<[u8]> = BoxRefMut::new(vec![4, 5, 6].into_boxed_slice()); - assert_eq!(or1.cmp(&or2), Ordering::Less); - } - - #[test] - fn partial_cmp() { - let or1: BoxRefMut<[u8]> = BoxRefMut::new(vec![4, 5, 6].into_boxed_slice()); - let or2: BoxRefMut<[u8]> = BoxRefMut::new(vec![1, 2, 3].into_boxed_slice()); - assert_eq!(or1.partial_cmp(&or2), Some(Ordering::Greater)); - } - - #[test] - fn hash() { - let mut h1 = DefaultHasher::new(); - let mut h2 = DefaultHasher::new(); - - let or1: BoxRefMut<[u8]> = BoxRefMut::new(vec![1, 2, 3].into_boxed_slice()); - let or2: BoxRefMut<[u8]> = BoxRefMut::new(vec![1, 2, 3].into_boxed_slice()); - - or1.hash(&mut h1); - or2.hash(&mut h2); - - assert_eq!(h1.finish(), h2.finish()); - } - - #[test] - fn borrow() { - let mut hash = HashMap::new(); - let key1 = BoxRefMut::<String>::new(Box::new("foo".to_string())).map(|s| &s[..]); - let key2 = BoxRefMut::<String>::new(Box::new("bar".to_string())).map(|s| &s[..]); - - hash.insert(key1, 42); - hash.insert(key2, 23); - - assert_eq!(hash.get("foo"), Some(&42)); - assert_eq!(hash.get("bar"), Some(&23)); - } - - #[test] - fn total_erase() { - let a: OwningRefMut<Vec<u8>, [u8]> = OwningRefMut::new(vec![]).map_mut(|x| &mut x[..]); - let b: OwningRefMut<Box<[u8]>, [u8]> = - OwningRefMut::new(vec![].into_boxed_slice()).map_mut(|x| &mut x[..]); - - let c: OwningRefMut<Box<Vec<u8>>, [u8]> = unsafe { a.map_owner(Box::new) }; - let d: OwningRefMut<Box<Box<[u8]>>, [u8]> = unsafe { b.map_owner(Box::new) }; - - let _e: OwningRefMut<Box<dyn Erased>, [u8]> = c.erase_owner(); - let _f: OwningRefMut<Box<dyn Erased>, [u8]> = d.erase_owner(); - } - - #[test] - fn total_erase_box() { - let a: OwningRefMut<Vec<u8>, [u8]> = OwningRefMut::new(vec![]).map_mut(|x| &mut x[..]); - let b: OwningRefMut<Box<[u8]>, [u8]> = - OwningRefMut::new(vec![].into_boxed_slice()).map_mut(|x| &mut x[..]); - - let c: OwningRefMut<Box<Vec<u8>>, [u8]> = a.map_owner_box(); - let d: OwningRefMut<Box<Box<[u8]>>, [u8]> = b.map_owner_box(); - - let _e: OwningRefMut<Box<dyn Erased>, [u8]> = c.erase_owner(); - let _f: OwningRefMut<Box<dyn Erased>, [u8]> = d.erase_owner(); - } - - #[test] - fn try_map1() { - use std::any::Any; - - let x = Box::new(123_i32); - let y: Box<dyn Any> = x; - - assert!(OwningRefMut::new(y).try_map_mut(|x| x.downcast_mut::<i32>().ok_or(())).is_ok()); - } - - #[test] - fn try_map2() { - use std::any::Any; - - let x = Box::new(123_i32); - let y: Box<dyn Any> = x; - - assert!(!OwningRefMut::new(y).try_map_mut(|x| x.downcast_mut::<i32>().ok_or(())).is_err()); - } - - #[test] - fn try_map3() { - use std::any::Any; - - let x = Box::new(123_i32); - let y: Box<dyn Any> = x; - - assert!(OwningRefMut::new(y).try_map(|x| x.downcast_ref::<i32>().ok_or(())).is_ok()); - } - - #[test] - fn try_map4() { - use std::any::Any; - - let x = Box::new(123_i32); - let y: Box<dyn Any> = x; - - assert!(!OwningRefMut::new(y).try_map(|x| x.downcast_ref::<i32>().ok_or(())).is_err()); - } - - #[test] - fn into_owning_ref() { - use super::super::BoxRef; - - let or: BoxRefMut<()> = Box::new(()).into(); - let or: BoxRef<()> = or.into(); - assert_eq!(&*or, &()); - } - - struct Foo { - u: u32, - } - struct Bar { - f: Foo, - } - - #[test] - fn ref_mut() { - use std::cell::RefCell; - - let a = RefCell::new(Bar { f: Foo { u: 42 } }); - let mut b = OwningRefMut::new(a.borrow_mut()); - assert_eq!(b.f.u, 42); - b.f.u = 43; - let mut c = b.map_mut(|x| &mut x.f); - assert_eq!(c.u, 43); - c.u = 44; - let mut d = c.map_mut(|x| &mut x.u); - assert_eq!(*d, 44); - *d = 45; - assert_eq!(*d, 45); - } -} diff --git a/compiler/rustc_data_structures/src/profiling.rs b/compiler/rustc_data_structures/src/profiling.rs index 443316836..1ed584eaf 100644 --- a/compiler/rustc_data_structures/src/profiling.rs +++ b/compiler/rustc_data_structures/src/profiling.rs @@ -97,6 +97,7 @@ use std::time::{Duration, Instant}; pub use measureme::EventId; use measureme::{EventIdBuilder, Profiler, SerializableString, StringId}; use parking_lot::RwLock; +use serde_json::json; use smallvec::SmallVec; bitflags::bitflags! { @@ -145,6 +146,15 @@ const EVENT_FILTERS_BY_NAME: &[(&str, EventFilter)] = &[ /// Something that uniquely identifies a query invocation. pub struct QueryInvocationId(pub u32); +/// Which format to use for `-Z time-passes` +#[derive(Clone, Copy, PartialEq, Hash, Debug)] +pub enum TimePassesFormat { + /// Emit human readable text + Text, + /// Emit structured JSON + Json, +} + /// A reference to the SelfProfiler. It can be cloned and sent across thread /// boundaries at will. #[derive(Clone)] @@ -158,14 +168,14 @@ pub struct SelfProfilerRef { // actually enabled. event_filter_mask: EventFilter, - // Print verbose generic activities to stderr? - print_verbose_generic_activities: bool, + // Print verbose generic activities to stderr. + print_verbose_generic_activities: Option<TimePassesFormat>, } impl SelfProfilerRef { pub fn new( profiler: Option<Arc<SelfProfiler>>, - print_verbose_generic_activities: bool, + print_verbose_generic_activities: Option<TimePassesFormat>, ) -> SelfProfilerRef { // If there is no SelfProfiler then the filter mask is set to NONE, // ensuring that nothing ever tries to actually access it. @@ -207,9 +217,10 @@ impl SelfProfilerRef { /// a measureme event, "verbose" generic activities also print a timing entry to /// stderr if the compiler is invoked with -Ztime-passes. pub fn verbose_generic_activity(&self, event_label: &'static str) -> VerboseTimingGuard<'_> { - let message = self.print_verbose_generic_activities.then(|| event_label.to_owned()); + let message_and_format = + self.print_verbose_generic_activities.map(|format| (event_label.to_owned(), format)); - VerboseTimingGuard::start(message, self.generic_activity(event_label)) + VerboseTimingGuard::start(message_and_format, self.generic_activity(event_label)) } /// Like `verbose_generic_activity`, but with an extra arg. @@ -221,11 +232,14 @@ impl SelfProfilerRef { where A: Borrow<str> + Into<String>, { - let message = self + let message_and_format = self .print_verbose_generic_activities - .then(|| format!("{}({})", event_label, event_arg.borrow())); + .map(|format| (format!("{}({})", event_label, event_arg.borrow()), format)); - VerboseTimingGuard::start(message, self.generic_activity_with_arg(event_label, event_arg)) + VerboseTimingGuard::start( + message_and_format, + self.generic_activity_with_arg(event_label, event_arg), + ) } /// Start profiling a generic activity. Profiling continues until the @@ -703,17 +717,32 @@ impl<'a> TimingGuard<'a> { } } +struct VerboseInfo { + start_time: Instant, + start_rss: Option<usize>, + message: String, + format: TimePassesFormat, +} + #[must_use] pub struct VerboseTimingGuard<'a> { - start_and_message: Option<(Instant, Option<usize>, String)>, + info: Option<VerboseInfo>, _guard: TimingGuard<'a>, } impl<'a> VerboseTimingGuard<'a> { - pub fn start(message: Option<String>, _guard: TimingGuard<'a>) -> Self { + pub fn start( + message_and_format: Option<(String, TimePassesFormat)>, + _guard: TimingGuard<'a>, + ) -> Self { VerboseTimingGuard { _guard, - start_and_message: message.map(|msg| (Instant::now(), get_resident_set_size(), msg)), + info: message_and_format.map(|(message, format)| VerboseInfo { + start_time: Instant::now(), + start_rss: get_resident_set_size(), + message, + format, + }), } } @@ -726,10 +755,10 @@ impl<'a> VerboseTimingGuard<'a> { impl Drop for VerboseTimingGuard<'_> { fn drop(&mut self) { - if let Some((start_time, start_rss, ref message)) = self.start_and_message { + if let Some(info) = &self.info { let end_rss = get_resident_set_size(); - let dur = start_time.elapsed(); - print_time_passes_entry(message, dur, start_rss, end_rss); + let dur = info.start_time.elapsed(); + print_time_passes_entry(&info.message, dur, info.start_rss, end_rss, info.format); } } } @@ -739,7 +768,22 @@ pub fn print_time_passes_entry( dur: Duration, start_rss: Option<usize>, end_rss: Option<usize>, + format: TimePassesFormat, ) { + match format { + TimePassesFormat::Json => { + let json = json!({ + "pass": what, + "time": dur.as_secs_f64(), + "rss_start": start_rss, + "rss_end": end_rss, + }); + eprintln!("time: {json}"); + return; + } + TimePassesFormat::Text => (), + } + // Print the pass if its duration is greater than 5 ms, or it changed the // measured RSS. let is_notable = || { @@ -796,21 +840,26 @@ fn get_thread_id() -> u32 { cfg_if! { if #[cfg(windows)] { pub fn get_resident_set_size() -> Option<usize> { - use std::mem::{self, MaybeUninit}; - use winapi::shared::minwindef::DWORD; - use winapi::um::processthreadsapi::GetCurrentProcess; - use winapi::um::psapi::{GetProcessMemoryInfo, PROCESS_MEMORY_COUNTERS}; - - let mut pmc = MaybeUninit::<PROCESS_MEMORY_COUNTERS>::uninit(); - match unsafe { - GetProcessMemoryInfo(GetCurrentProcess(), pmc.as_mut_ptr(), mem::size_of_val(&pmc) as DWORD) - } { - 0 => None, - _ => { - let pmc = unsafe { pmc.assume_init() }; - Some(pmc.WorkingSetSize as usize) - } + use std::mem; + + use windows::{ + Win32::System::ProcessStatus::{K32GetProcessMemoryInfo, PROCESS_MEMORY_COUNTERS}, + Win32::System::Threading::GetCurrentProcess, + }; + + let mut pmc = PROCESS_MEMORY_COUNTERS::default(); + let pmc_size = mem::size_of_val(&pmc); + unsafe { + K32GetProcessMemoryInfo( + GetCurrentProcess(), + &mut pmc, + pmc_size as u32, + ) } + .ok() + .ok()?; + + Some(pmc.WorkingSetSize) } } else if #[cfg(target_os = "macos")] { pub fn get_resident_set_size() -> Option<usize> { diff --git a/compiler/rustc_data_structures/src/sharded.rs b/compiler/rustc_data_structures/src/sharded.rs index 01d292dde..bd7a86f67 100644 --- a/compiler/rustc_data_structures/src/sharded.rs +++ b/compiler/rustc_data_structures/src/sharded.rs @@ -5,7 +5,7 @@ use std::collections::hash_map::RawEntryMut; use std::hash::{Hash, Hasher}; use std::mem; -#[derive(Clone, Default)] +#[derive(Default)] #[cfg_attr(parallel_compiler, repr(align(64)))] struct CacheAligned<T>(T); @@ -21,7 +21,6 @@ const SHARD_BITS: usize = 0; pub const SHARDS: usize = 1 << SHARD_BITS; /// An array of cache-line aligned inner locked structures with convenience methods. -#[derive(Clone)] pub struct Sharded<T> { shards: [CacheAligned<Lock<T>>; SHARDS], } @@ -141,6 +140,7 @@ pub fn make_hash<K: Hash + ?Sized>(val: &K) -> u64 { /// `hash` can be computed with any hasher, so long as that hasher is used /// consistently for each `Sharded` instance. #[inline] +#[allow(clippy::modulo_one)] pub fn get_shard_index_by_hash(hash: u64) -> usize { let hash_len = mem::size_of::<usize>(); // Ignore the top 7 bits as hashbrown uses these and get the next SHARD_BITS highest bits. diff --git a/compiler/rustc_data_structures/src/sip128.rs b/compiler/rustc_data_structures/src/sip128.rs index 90793a97e..d849fe037 100644 --- a/compiler/rustc_data_structures/src/sip128.rs +++ b/compiler/rustc_data_structures/src/sip128.rs @@ -247,7 +247,7 @@ impl SipHasher128 { for i in 0..BUFFER_CAPACITY { let elem = self.buf.get_unchecked(i).assume_init().to_le(); self.state.v3 ^= elem; - Sip24Rounds::c_rounds(&mut self.state); + Sip13Rounds::c_rounds(&mut self.state); self.state.v0 ^= elem; } @@ -327,7 +327,7 @@ impl SipHasher128 { for i in 0..last { let elem = self.buf.get_unchecked(i).assume_init().to_le(); self.state.v3 ^= elem; - Sip24Rounds::c_rounds(&mut self.state); + Sip13Rounds::c_rounds(&mut self.state); self.state.v0 ^= elem; } @@ -340,7 +340,7 @@ impl SipHasher128 { for _ in 0..elems_left { let elem = (msg.as_ptr().add(processed) as *const u64).read_unaligned().to_le(); self.state.v3 ^= elem; - Sip24Rounds::c_rounds(&mut self.state); + Sip13Rounds::c_rounds(&mut self.state); self.state.v0 ^= elem; processed += ELEM_SIZE; } @@ -368,7 +368,7 @@ impl SipHasher128 { for i in 0..last { let elem = unsafe { self.buf.get_unchecked(i).assume_init().to_le() }; state.v3 ^= elem; - Sip24Rounds::c_rounds(&mut state); + Sip13Rounds::c_rounds(&mut state); state.v0 ^= elem; } @@ -392,15 +392,15 @@ impl SipHasher128 { let b: u64 = ((length as u64 & 0xff) << 56) | elem; state.v3 ^= b; - Sip24Rounds::c_rounds(&mut state); + Sip13Rounds::c_rounds(&mut state); state.v0 ^= b; state.v2 ^= 0xee; - Sip24Rounds::d_rounds(&mut state); + Sip13Rounds::d_rounds(&mut state); let _0 = state.v0 ^ state.v1 ^ state.v2 ^ state.v3; state.v1 ^= 0xdd; - Sip24Rounds::d_rounds(&mut state); + Sip13Rounds::d_rounds(&mut state); let _1 = state.v0 ^ state.v1 ^ state.v2 ^ state.v3; (_0, _1) @@ -477,13 +477,12 @@ impl Hasher for SipHasher128 { } #[derive(Debug, Clone, Default)] -struct Sip24Rounds; +struct Sip13Rounds; -impl Sip24Rounds { +impl Sip13Rounds { #[inline] fn c_rounds(state: &mut State) { compress!(state); - compress!(state); } #[inline] @@ -491,6 +490,5 @@ impl Sip24Rounds { compress!(state); compress!(state); compress!(state); - compress!(state); } } diff --git a/compiler/rustc_data_structures/src/sip128/tests.rs b/compiler/rustc_data_structures/src/sip128/tests.rs index 5fe967c41..cc6d3b0f4 100644 --- a/compiler/rustc_data_structures/src/sip128/tests.rs +++ b/compiler/rustc_data_structures/src/sip128/tests.rs @@ -22,269 +22,76 @@ fn hash_with<T: Hash>(mut st: SipHasher128, x: &T) -> (u64, u64) { fn hash<T: Hash>(x: &T) -> (u64, u64) { hash_with(SipHasher128::new_with_keys(0, 0), x) } - +#[rustfmt::skip] const TEST_VECTOR: [[u8; 16]; 64] = [ - [ - 0xa3, 0x81, 0x7f, 0x04, 0xba, 0x25, 0xa8, 0xe6, 0x6d, 0xf6, 0x72, 0x14, 0xc7, 0x55, 0x02, - 0x93, - ], - [ - 0xda, 0x87, 0xc1, 0xd8, 0x6b, 0x99, 0xaf, 0x44, 0x34, 0x76, 0x59, 0x11, 0x9b, 0x22, 0xfc, - 0x45, - ], - [ - 0x81, 0x77, 0x22, 0x8d, 0xa4, 0xa4, 0x5d, 0xc7, 0xfc, 0xa3, 0x8b, 0xde, 0xf6, 0x0a, 0xff, - 0xe4, - ], - [ - 0x9c, 0x70, 0xb6, 0x0c, 0x52, 0x67, 0xa9, 0x4e, 0x5f, 0x33, 0xb6, 0xb0, 0x29, 0x85, 0xed, - 0x51, - ], - [ - 0xf8, 0x81, 0x64, 0xc1, 0x2d, 0x9c, 0x8f, 0xaf, 0x7d, 0x0f, 0x6e, 0x7c, 0x7b, 0xcd, 0x55, - 0x79, - ], - [ - 0x13, 0x68, 0x87, 0x59, 0x80, 0x77, 0x6f, 0x88, 0x54, 0x52, 0x7a, 0x07, 0x69, 0x0e, 0x96, - 0x27, - ], - [ - 0x14, 0xee, 0xca, 0x33, 0x8b, 0x20, 0x86, 0x13, 0x48, 0x5e, 0xa0, 0x30, 0x8f, 0xd7, 0xa1, - 0x5e, - ], - [ - 0xa1, 0xf1, 0xeb, 0xbe, 0xd8, 0xdb, 0xc1, 0x53, 0xc0, 0xb8, 0x4a, 0xa6, 0x1f, 0xf0, 0x82, - 0x39, - ], - [ - 0x3b, 0x62, 0xa9, 0xba, 0x62, 0x58, 0xf5, 0x61, 0x0f, 0x83, 0xe2, 0x64, 0xf3, 0x14, 0x97, - 0xb4, - ], - [ - 0x26, 0x44, 0x99, 0x06, 0x0a, 0xd9, 0xba, 0xab, 0xc4, 0x7f, 0x8b, 0x02, 0xbb, 0x6d, 0x71, - 0xed, - ], - [ - 0x00, 0x11, 0x0d, 0xc3, 0x78, 0x14, 0x69, 0x56, 0xc9, 0x54, 0x47, 0xd3, 0xf3, 0xd0, 0xfb, - 0xba, - ], - [ - 0x01, 0x51, 0xc5, 0x68, 0x38, 0x6b, 0x66, 0x77, 0xa2, 0xb4, 0xdc, 0x6f, 0x81, 0xe5, 0xdc, - 0x18, - ], - [ - 0xd6, 0x26, 0xb2, 0x66, 0x90, 0x5e, 0xf3, 0x58, 0x82, 0x63, 0x4d, 0xf6, 0x85, 0x32, 0xc1, - 0x25, - ], - [ - 0x98, 0x69, 0xe2, 0x47, 0xe9, 0xc0, 0x8b, 0x10, 0xd0, 0x29, 0x93, 0x4f, 0xc4, 0xb9, 0x52, - 0xf7, - ], - [ - 0x31, 0xfc, 0xef, 0xac, 0x66, 0xd7, 0xde, 0x9c, 0x7e, 0xc7, 0x48, 0x5f, 0xe4, 0x49, 0x49, - 0x02, - ], - [ - 0x54, 0x93, 0xe9, 0x99, 0x33, 0xb0, 0xa8, 0x11, 0x7e, 0x08, 0xec, 0x0f, 0x97, 0xcf, 0xc3, - 0xd9, - ], - [ - 0x6e, 0xe2, 0xa4, 0xca, 0x67, 0xb0, 0x54, 0xbb, 0xfd, 0x33, 0x15, 0xbf, 0x85, 0x23, 0x05, - 0x77, - ], - [ - 0x47, 0x3d, 0x06, 0xe8, 0x73, 0x8d, 0xb8, 0x98, 0x54, 0xc0, 0x66, 0xc4, 0x7a, 0xe4, 0x77, - 0x40, - ], - [ - 0xa4, 0x26, 0xe5, 0xe4, 0x23, 0xbf, 0x48, 0x85, 0x29, 0x4d, 0xa4, 0x81, 0xfe, 0xae, 0xf7, - 0x23, - ], - [ - 0x78, 0x01, 0x77, 0x31, 0xcf, 0x65, 0xfa, 0xb0, 0x74, 0xd5, 0x20, 0x89, 0x52, 0x51, 0x2e, - 0xb1, - ], - [ - 0x9e, 0x25, 0xfc, 0x83, 0x3f, 0x22, 0x90, 0x73, 0x3e, 0x93, 0x44, 0xa5, 0xe8, 0x38, 0x39, - 0xeb, - ], - [ - 0x56, 0x8e, 0x49, 0x5a, 0xbe, 0x52, 0x5a, 0x21, 0x8a, 0x22, 0x14, 0xcd, 0x3e, 0x07, 0x1d, - 0x12, - ], - [ - 0x4a, 0x29, 0xb5, 0x45, 0x52, 0xd1, 0x6b, 0x9a, 0x46, 0x9c, 0x10, 0x52, 0x8e, 0xff, 0x0a, - 0xae, - ], - [ - 0xc9, 0xd1, 0x84, 0xdd, 0xd5, 0xa9, 0xf5, 0xe0, 0xcf, 0x8c, 0xe2, 0x9a, 0x9a, 0xbf, 0x69, - 0x1c, - ], - [ - 0x2d, 0xb4, 0x79, 0xae, 0x78, 0xbd, 0x50, 0xd8, 0x88, 0x2a, 0x8a, 0x17, 0x8a, 0x61, 0x32, - 0xad, - ], - [ - 0x8e, 0xce, 0x5f, 0x04, 0x2d, 0x5e, 0x44, 0x7b, 0x50, 0x51, 0xb9, 0xea, 0xcb, 0x8d, 0x8f, - 0x6f, - ], - [ - 0x9c, 0x0b, 0x53, 0xb4, 0xb3, 0xc3, 0x07, 0xe8, 0x7e, 0xae, 0xe0, 0x86, 0x78, 0x14, 0x1f, - 0x66, - ], - [ - 0xab, 0xf2, 0x48, 0xaf, 0x69, 0xa6, 0xea, 0xe4, 0xbf, 0xd3, 0xeb, 0x2f, 0x12, 0x9e, 0xeb, - 0x94, - ], - [ - 0x06, 0x64, 0xda, 0x16, 0x68, 0x57, 0x4b, 0x88, 0xb9, 0x35, 0xf3, 0x02, 0x73, 0x58, 0xae, - 0xf4, - ], - [ - 0xaa, 0x4b, 0x9d, 0xc4, 0xbf, 0x33, 0x7d, 0xe9, 0x0c, 0xd4, 0xfd, 0x3c, 0x46, 0x7c, 0x6a, - 0xb7, - ], - [ - 0xea, 0x5c, 0x7f, 0x47, 0x1f, 0xaf, 0x6b, 0xde, 0x2b, 0x1a, 0xd7, 0xd4, 0x68, 0x6d, 0x22, - 0x87, - ], - [ - 0x29, 0x39, 0xb0, 0x18, 0x32, 0x23, 0xfa, 0xfc, 0x17, 0x23, 0xde, 0x4f, 0x52, 0xc4, 0x3d, - 0x35, - ], - [ - 0x7c, 0x39, 0x56, 0xca, 0x5e, 0xea, 0xfc, 0x3e, 0x36, 0x3e, 0x9d, 0x55, 0x65, 0x46, 0xeb, - 0x68, - ], - [ - 0x77, 0xc6, 0x07, 0x71, 0x46, 0xf0, 0x1c, 0x32, 0xb6, 0xb6, 0x9d, 0x5f, 0x4e, 0xa9, 0xff, - 0xcf, - ], - [ - 0x37, 0xa6, 0x98, 0x6c, 0xb8, 0x84, 0x7e, 0xdf, 0x09, 0x25, 0xf0, 0xf1, 0x30, 0x9b, 0x54, - 0xde, - ], - [ - 0xa7, 0x05, 0xf0, 0xe6, 0x9d, 0xa9, 0xa8, 0xf9, 0x07, 0x24, 0x1a, 0x2e, 0x92, 0x3c, 0x8c, - 0xc8, - ], - [ - 0x3d, 0xc4, 0x7d, 0x1f, 0x29, 0xc4, 0x48, 0x46, 0x1e, 0x9e, 0x76, 0xed, 0x90, 0x4f, 0x67, - 0x11, - ], - [ - 0x0d, 0x62, 0xbf, 0x01, 0xe6, 0xfc, 0x0e, 0x1a, 0x0d, 0x3c, 0x47, 0x51, 0xc5, 0xd3, 0x69, - 0x2b, - ], - [ - 0x8c, 0x03, 0x46, 0x8b, 0xca, 0x7c, 0x66, 0x9e, 0xe4, 0xfd, 0x5e, 0x08, 0x4b, 0xbe, 0xe7, - 0xb5, - ], - [ - 0x52, 0x8a, 0x5b, 0xb9, 0x3b, 0xaf, 0x2c, 0x9c, 0x44, 0x73, 0xcc, 0xe5, 0xd0, 0xd2, 0x2b, - 0xd9, - ], - [ - 0xdf, 0x6a, 0x30, 0x1e, 0x95, 0xc9, 0x5d, 0xad, 0x97, 0xae, 0x0c, 0xc8, 0xc6, 0x91, 0x3b, - 0xd8, - ], - [ - 0x80, 0x11, 0x89, 0x90, 0x2c, 0x85, 0x7f, 0x39, 0xe7, 0x35, 0x91, 0x28, 0x5e, 0x70, 0xb6, - 0xdb, - ], - [ - 0xe6, 0x17, 0x34, 0x6a, 0xc9, 0xc2, 0x31, 0xbb, 0x36, 0x50, 0xae, 0x34, 0xcc, 0xca, 0x0c, - 0x5b, - ], - [ - 0x27, 0xd9, 0x34, 0x37, 0xef, 0xb7, 0x21, 0xaa, 0x40, 0x18, 0x21, 0xdc, 0xec, 0x5a, 0xdf, - 0x89, - ], - [ - 0x89, 0x23, 0x7d, 0x9d, 0xed, 0x9c, 0x5e, 0x78, 0xd8, 0xb1, 0xc9, 0xb1, 0x66, 0xcc, 0x73, - 0x42, - ], - [ - 0x4a, 0x6d, 0x80, 0x91, 0xbf, 0x5e, 0x7d, 0x65, 0x11, 0x89, 0xfa, 0x94, 0xa2, 0x50, 0xb1, - 0x4c, - ], - [ - 0x0e, 0x33, 0xf9, 0x60, 0x55, 0xe7, 0xae, 0x89, 0x3f, 0xfc, 0x0e, 0x3d, 0xcf, 0x49, 0x29, - 0x02, - ], - [ - 0xe6, 0x1c, 0x43, 0x2b, 0x72, 0x0b, 0x19, 0xd1, 0x8e, 0xc8, 0xd8, 0x4b, 0xdc, 0x63, 0x15, - 0x1b, - ], - [ - 0xf7, 0xe5, 0xae, 0xf5, 0x49, 0xf7, 0x82, 0xcf, 0x37, 0x90, 0x55, 0xa6, 0x08, 0x26, 0x9b, - 0x16, - ], - [ - 0x43, 0x8d, 0x03, 0x0f, 0xd0, 0xb7, 0xa5, 0x4f, 0xa8, 0x37, 0xf2, 0xad, 0x20, 0x1a, 0x64, - 0x03, - ], - [ - 0xa5, 0x90, 0xd3, 0xee, 0x4f, 0xbf, 0x04, 0xe3, 0x24, 0x7e, 0x0d, 0x27, 0xf2, 0x86, 0x42, - 0x3f, - ], - [ - 0x5f, 0xe2, 0xc1, 0xa1, 0x72, 0xfe, 0x93, 0xc4, 0xb1, 0x5c, 0xd3, 0x7c, 0xae, 0xf9, 0xf5, - 0x38, - ], - [ - 0x2c, 0x97, 0x32, 0x5c, 0xbd, 0x06, 0xb3, 0x6e, 0xb2, 0x13, 0x3d, 0xd0, 0x8b, 0x3a, 0x01, - 0x7c, - ], - [ - 0x92, 0xc8, 0x14, 0x22, 0x7a, 0x6b, 0xca, 0x94, 0x9f, 0xf0, 0x65, 0x9f, 0x00, 0x2a, 0xd3, - 0x9e, - ], - [ - 0xdc, 0xe8, 0x50, 0x11, 0x0b, 0xd8, 0x32, 0x8c, 0xfb, 0xd5, 0x08, 0x41, 0xd6, 0x91, 0x1d, - 0x87, - ], - [ - 0x67, 0xf1, 0x49, 0x84, 0xc7, 0xda, 0x79, 0x12, 0x48, 0xe3, 0x2b, 0xb5, 0x92, 0x25, 0x83, - 0xda, - ], - [ - 0x19, 0x38, 0xf2, 0xcf, 0x72, 0xd5, 0x4e, 0xe9, 0x7e, 0x94, 0x16, 0x6f, 0xa9, 0x1d, 0x2a, - 0x36, - ], - [ - 0x74, 0x48, 0x1e, 0x96, 0x46, 0xed, 0x49, 0xfe, 0x0f, 0x62, 0x24, 0x30, 0x16, 0x04, 0x69, - 0x8e, - ], - [ - 0x57, 0xfc, 0xa5, 0xde, 0x98, 0xa9, 0xd6, 0xd8, 0x00, 0x64, 0x38, 0xd0, 0x58, 0x3d, 0x8a, - 0x1d, - ], - [ - 0x9f, 0xec, 0xde, 0x1c, 0xef, 0xdc, 0x1c, 0xbe, 0xd4, 0x76, 0x36, 0x74, 0xd9, 0x57, 0x53, - 0x59, - ], - [ - 0xe3, 0x04, 0x0c, 0x00, 0xeb, 0x28, 0xf1, 0x53, 0x66, 0xca, 0x73, 0xcb, 0xd8, 0x72, 0xe7, - 0x40, - ], - [ - 0x76, 0x97, 0x00, 0x9a, 0x6a, 0x83, 0x1d, 0xfe, 0xcc, 0xa9, 0x1c, 0x59, 0x93, 0x67, 0x0f, - 0x7a, - ], - [ - 0x58, 0x53, 0x54, 0x23, 0x21, 0xf5, 0x67, 0xa0, 0x05, 0xd5, 0x47, 0xa4, 0xf0, 0x47, 0x59, - 0xbd, - ], - [ - 0x51, 0x50, 0xd1, 0x77, 0x2f, 0x50, 0x83, 0x4a, 0x50, 0x3e, 0x06, 0x9a, 0x97, 0x3f, 0xbd, - 0x7c, - ], + [0xe7, 0x7e, 0xbc, 0xb2, 0x27, 0x88, 0xa5, 0xbe, 0xfd, 0x62, 0xdb, 0x6a, 0xdd, 0x30, 0x30, 0x01], + [0xfc, 0x6f, 0x37, 0x04, 0x60, 0xd3, 0xed, 0xa8, 0x5e, 0x05, 0x73, 0xcc, 0x2b, 0x2f, 0xf0, 0x63], + [0x75, 0x78, 0x7f, 0x09, 0x05, 0x69, 0x83, 0x9b, 0x85, 0x5b, 0xc9, 0x54, 0x8c, 0x6a, 0xea, 0x95], + [0x6b, 0xc5, 0xcc, 0xfa, 0x1e, 0xdc, 0xf7, 0x9f, 0x48, 0x23, 0x18, 0x77, 0x12, 0xeb, 0xd7, 0x43], + [0x0c, 0x78, 0x4e, 0x71, 0xac, 0x2b, 0x28, 0x5a, 0x9f, 0x8e, 0x92, 0xe7, 0x8f, 0xbf, 0x2c, 0x25], + [0xf3, 0x28, 0xdb, 0x89, 0x34, 0x5b, 0x62, 0x0c, 0x79, 0x52, 0x29, 0xa4, 0x26, 0x95, 0x84, 0x3e], + [0xdc, 0xd0, 0x3d, 0x29, 0xf7, 0x43, 0xe7, 0x10, 0x09, 0x51, 0xb0, 0xe8, 0x39, 0x85, 0xa6, 0xf8], + [0x10, 0x84, 0xb9, 0x23, 0xf2, 0xaa, 0xe0, 0xc3, 0xa6, 0x2f, 0x2e, 0xc8, 0x08, 0x48, 0xab, 0x77], + [0xaa, 0x12, 0xfe, 0xe1, 0xd5, 0xe3, 0xda, 0xb4, 0x72, 0x4f, 0x16, 0xab, 0x35, 0xf9, 0xc7, 0x99], + [0x81, 0xdd, 0xb8, 0x04, 0x2c, 0xf3, 0x39, 0x94, 0xf4, 0x72, 0x0e, 0x00, 0x94, 0x13, 0x7c, 0x42], + [0x4f, 0xaa, 0x54, 0x1d, 0x5d, 0x49, 0x8e, 0x89, 0xba, 0x0e, 0xa4, 0xc3, 0x87, 0xb2, 0x2f, 0xb4], + [0x72, 0x3b, 0x9a, 0xf3, 0x55, 0x44, 0x91, 0xdb, 0xb1, 0xd6, 0x63, 0x3d, 0xfc, 0x6e, 0x0c, 0x4e], + [0xe5, 0x3f, 0x92, 0x85, 0x9e, 0x48, 0x19, 0xa8, 0xdc, 0x06, 0x95, 0x73, 0x9f, 0xea, 0x8c, 0x65], + [0xb2, 0xf8, 0x58, 0xc7, 0xc9, 0xea, 0x80, 0x1d, 0x53, 0xd6, 0x03, 0x59, 0x6d, 0x65, 0x78, 0x44], + [0x87, 0xe7, 0x62, 0x68, 0xdb, 0xc9, 0x22, 0x72, 0x26, 0xb0, 0xca, 0x66, 0x5f, 0x64, 0xe3, 0x78], + [0xc1, 0x7e, 0x55, 0x05, 0xb2, 0xbd, 0x52, 0x6c, 0x29, 0x21, 0xcd, 0xec, 0x1e, 0x7e, 0x01, 0x09], + [0xd0, 0xa8, 0xd9, 0x57, 0x15, 0x51, 0x8e, 0xeb, 0xb5, 0x13, 0xb0, 0xf8, 0x3d, 0x9e, 0x17, 0x93], + [0x23, 0x41, 0x26, 0xf9, 0x3f, 0xbb, 0x66, 0x8d, 0x97, 0x51, 0x12, 0xe8, 0xfe, 0xbd, 0xf7, 0xec], + [0xef, 0x42, 0xf0, 0x3d, 0xb7, 0x8f, 0x70, 0x4d, 0x02, 0x3c, 0x44, 0x9f, 0x16, 0xb7, 0x09, 0x2b], + [0xab, 0xf7, 0x62, 0x38, 0xc2, 0x0a, 0xf1, 0x61, 0xb2, 0x31, 0x4b, 0x4d, 0x55, 0x26, 0xbc, 0xe9], + [0x3c, 0x2c, 0x2f, 0x11, 0xbb, 0x90, 0xcf, 0x0b, 0xe3, 0x35, 0xca, 0x9b, 0x2e, 0x91, 0xe9, 0xb7], + [0x2a, 0x7a, 0x68, 0x0f, 0x22, 0xa0, 0x2a, 0x92, 0xf4, 0x51, 0x49, 0xd2, 0x0f, 0xec, 0xe0, 0xef], + [0xc9, 0xa8, 0xd1, 0x30, 0x23, 0x1d, 0xd4, 0x3e, 0x42, 0xe6, 0x45, 0x69, 0x57, 0xf8, 0x37, 0x79], + [0x1d, 0x12, 0x7b, 0x84, 0x40, 0x5c, 0xea, 0xb9, 0x9f, 0xd8, 0x77, 0x5a, 0x9b, 0xe6, 0xc5, 0x59], + [0x9e, 0x4b, 0xf8, 0x37, 0xbc, 0xfd, 0x92, 0xca, 0xce, 0x09, 0xd2, 0x06, 0x1a, 0x84, 0xd0, 0x4a], + [0x39, 0x03, 0x1a, 0x96, 0x5d, 0x73, 0xb4, 0xaf, 0x5a, 0x27, 0x4d, 0x18, 0xf9, 0x73, 0xb1, 0xd2], + [0x7f, 0x4d, 0x0a, 0x12, 0x09, 0xd6, 0x7e, 0x4e, 0xd0, 0x6f, 0x75, 0x38, 0xe1, 0xcf, 0xad, 0x64], + [0xe6, 0x1e, 0xe2, 0x40, 0xfb, 0xdc, 0xce, 0x38, 0x96, 0x9f, 0x4c, 0xd2, 0x49, 0x27, 0xdd, 0x93], + [0x4c, 0x3b, 0xa2, 0xb3, 0x7b, 0x0f, 0xdd, 0x8c, 0xfa, 0x5e, 0x95, 0xc1, 0x89, 0xb2, 0x94, 0x14], + [0xe0, 0x6f, 0xd4, 0xca, 0x06, 0x6f, 0xec, 0xdd, 0x54, 0x06, 0x8a, 0x5a, 0xd8, 0x89, 0x6f, 0x86], + [0x5c, 0xa8, 0x4c, 0x34, 0x13, 0x9c, 0x65, 0x80, 0xa8, 0x8a, 0xf2, 0x49, 0x90, 0x72, 0x07, 0x06], + [0x42, 0xea, 0x96, 0x1c, 0x5b, 0x3c, 0x85, 0x8b, 0x17, 0xc3, 0xe5, 0x50, 0xdf, 0xa7, 0x90, 0x10], + [0x40, 0x6c, 0x44, 0xde, 0xe6, 0x78, 0x57, 0xb2, 0x94, 0x31, 0x60, 0xf3, 0x0c, 0x74, 0x17, 0xd3], + [0xc5, 0xf5, 0x7b, 0xae, 0x13, 0x20, 0xfc, 0xf4, 0xb4, 0xe8, 0x68, 0xe7, 0x1d, 0x56, 0xc6, 0x6b], + [0x04, 0xbf, 0x73, 0x7a, 0x5b, 0x67, 0x6b, 0xe7, 0xc3, 0xde, 0x05, 0x01, 0x7d, 0xf4, 0xbf, 0xf9], + [0x51, 0x63, 0xc9, 0xc0, 0x3f, 0x19, 0x07, 0xea, 0x10, 0x44, 0xed, 0x5c, 0x30, 0x72, 0x7b, 0x4f], + [0x37, 0xa1, 0x10, 0xf0, 0x02, 0x71, 0x8e, 0xda, 0xd2, 0x4b, 0x3f, 0x9e, 0xe4, 0x53, 0xf1, 0x40], + [0xb9, 0x87, 0x7e, 0x38, 0x1a, 0xed, 0xd3, 0xda, 0x08, 0xc3, 0x3e, 0x75, 0xff, 0x23, 0xac, 0x10], + [0x7c, 0x50, 0x04, 0x00, 0x5e, 0xc5, 0xda, 0x4c, 0x5a, 0xc9, 0x44, 0x0e, 0x5c, 0x72, 0x31, 0x93], + [0x81, 0xb8, 0x24, 0x37, 0x83, 0xdb, 0xc6, 0x46, 0xca, 0x9d, 0x0c, 0xd8, 0x2a, 0xbd, 0xb4, 0x6c], + [0x50, 0x57, 0x20, 0x54, 0x3e, 0xb9, 0xb4, 0x13, 0xd5, 0x0b, 0x3c, 0xfa, 0xd9, 0xee, 0xf9, 0x38], + [0x94, 0x5f, 0x59, 0x4d, 0xe7, 0x24, 0x11, 0xe4, 0xd3, 0x35, 0xbe, 0x87, 0x44, 0x56, 0xd8, 0xf3], + [0x37, 0x92, 0x3b, 0x3e, 0x37, 0x17, 0x77, 0xb2, 0x11, 0x70, 0xbf, 0x9d, 0x7e, 0x62, 0xf6, 0x02], + [0x3a, 0xd4, 0xe7, 0xc8, 0x57, 0x64, 0x96, 0x46, 0x11, 0xeb, 0x0a, 0x6c, 0x4d, 0x62, 0xde, 0x56], + [0xcd, 0x91, 0x39, 0x6c, 0x44, 0xaf, 0x4f, 0x51, 0x85, 0x57, 0x8d, 0x9d, 0xd9, 0x80, 0x3f, 0x0a], + [0xfe, 0x28, 0x15, 0x8e, 0x72, 0x7b, 0x86, 0x8f, 0x39, 0x03, 0xc9, 0xac, 0xda, 0x64, 0xa2, 0x58], + [0x40, 0xcc, 0x10, 0xb8, 0x28, 0x8c, 0xe5, 0xf0, 0xbc, 0x3a, 0xc0, 0xb6, 0x8a, 0x0e, 0xeb, 0xc8], + [0x6f, 0x14, 0x90, 0xf5, 0x40, 0x69, 0x9a, 0x3c, 0xd4, 0x97, 0x44, 0x20, 0xec, 0xc9, 0x27, 0x37], + [0xd5, 0x05, 0xf1, 0xb7, 0x5e, 0x1a, 0x84, 0xa6, 0x03, 0xc4, 0x35, 0x83, 0xb2, 0xed, 0x03, 0x08], + [0x49, 0x15, 0x73, 0xcf, 0xd7, 0x2b, 0xb4, 0x68, 0x2b, 0x7c, 0xa5, 0x88, 0x0e, 0x1c, 0x8d, 0x6f], + [0x3e, 0xd6, 0x9c, 0xfe, 0x45, 0xab, 0x40, 0x3f, 0x2f, 0xd2, 0xad, 0x95, 0x9b, 0xa2, 0x76, 0x66], + [0x8b, 0xe8, 0x39, 0xef, 0x1b, 0x20, 0xb5, 0x7c, 0x83, 0xba, 0x7e, 0xb6, 0xa8, 0xc2, 0x2b, 0x6a], + [0x14, 0x09, 0x18, 0x6a, 0xb4, 0x22, 0x31, 0xfe, 0xde, 0xe1, 0x81, 0x62, 0xcf, 0x1c, 0xb4, 0xca], + [0x2b, 0xf3, 0xcc, 0xc2, 0x4a, 0xb6, 0x72, 0xcf, 0x15, 0x1f, 0xb8, 0xd2, 0xf3, 0xf3, 0x06, 0x9b], + [0xb9, 0xb9, 0x3a, 0x28, 0x82, 0xd6, 0x02, 0x5c, 0xdb, 0x8c, 0x56, 0xfa, 0x13, 0xf7, 0x53, 0x7b], + [0xd9, 0x7c, 0xca, 0x36, 0x94, 0xfb, 0x20, 0x6d, 0xb8, 0xbd, 0x1f, 0x36, 0x50, 0xc3, 0x33, 0x22], + [0x94, 0xec, 0x2e, 0x19, 0xa4, 0x0b, 0xe4, 0x1a, 0xf3, 0x94, 0x0d, 0x6b, 0x30, 0xc4, 0x93, 0x84], + [0x4b, 0x41, 0x60, 0x3f, 0x20, 0x9a, 0x04, 0x5b, 0xe1, 0x40, 0xa3, 0x41, 0xa3, 0xdf, 0xfe, 0x10], + [0x23, 0xfb, 0xcb, 0x30, 0x9f, 0x1c, 0xf0, 0x94, 0x89, 0x07, 0x55, 0xab, 0x1b, 0x42, 0x65, 0x69], + [0xe7, 0xd9, 0xb6, 0x56, 0x90, 0x91, 0x8a, 0x2b, 0x23, 0x2f, 0x2f, 0x5c, 0x12, 0xc8, 0x30, 0x0e], + [0xad, 0xe8, 0x3c, 0xf7, 0xe7, 0xf3, 0x84, 0x7b, 0x36, 0xfa, 0x4b, 0x54, 0xb0, 0x0d, 0xce, 0x61], + [0x06, 0x10, 0xc5, 0xf2, 0xee, 0x57, 0x1c, 0x8a, 0xc8, 0x0c, 0xbf, 0xe5, 0x38, 0xbd, 0xf1, 0xc7], + [0x27, 0x1d, 0x5d, 0x00, 0xfb, 0xdb, 0x5d, 0x15, 0x5d, 0x9d, 0xce, 0xa9, 0x7c, 0xb4, 0x02, 0x18], + [0x4c, 0x58, 0x00, 0xe3, 0x4e, 0xfe, 0x42, 0x6f, 0x07, 0x9f, 0x6b, 0x0a, 0xa7, 0x52, 0x60, 0xad], ]; -// Test vector from reference implementation #[test] -fn test_siphash_2_4_test_vector() { +fn test_siphash_1_3_test_vector() { let k0 = 0x_07_06_05_04_03_02_01_00; let k1 = 0x_0f_0e_0d_0c_0b_0a_09_08; diff --git a/compiler/rustc_data_structures/src/sso/either_iter.rs b/compiler/rustc_data_structures/src/sso/either_iter.rs deleted file mode 100644 index bca6c0955..000000000 --- a/compiler/rustc_data_structures/src/sso/either_iter.rs +++ /dev/null @@ -1,73 +0,0 @@ -use std::fmt; -use std::iter::FusedIterator; - -/// Iterator which may contain instance of -/// one of two specific implementations. -/// -/// Note: For most methods providing custom -/// implementation may marginally -/// improve performance by avoiding -/// doing Left/Right match on every step -/// and doing it only once instead. -#[derive(Clone)] -pub enum EitherIter<L, R> { - Left(L), - Right(R), -} - -impl<L, R> Iterator for EitherIter<L, R> -where - L: Iterator, - R: Iterator<Item = L::Item>, -{ - type Item = L::Item; - - fn next(&mut self) -> Option<Self::Item> { - match self { - EitherIter::Left(l) => l.next(), - EitherIter::Right(r) => r.next(), - } - } - - fn size_hint(&self) -> (usize, Option<usize>) { - match self { - EitherIter::Left(l) => l.size_hint(), - EitherIter::Right(r) => r.size_hint(), - } - } -} - -impl<L, R> ExactSizeIterator for EitherIter<L, R> -where - L: ExactSizeIterator, - R: ExactSizeIterator, - EitherIter<L, R>: Iterator, -{ - fn len(&self) -> usize { - match self { - EitherIter::Left(l) => l.len(), - EitherIter::Right(r) => r.len(), - } - } -} - -impl<L, R> FusedIterator for EitherIter<L, R> -where - L: FusedIterator, - R: FusedIterator, - EitherIter<L, R>: Iterator, -{ -} - -impl<L, R> fmt::Debug for EitherIter<L, R> -where - L: fmt::Debug, - R: fmt::Debug, -{ - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - match self { - EitherIter::Left(l) => l.fmt(f), - EitherIter::Right(r) => r.fmt(f), - } - } -} diff --git a/compiler/rustc_data_structures/src/sso/map.rs b/compiler/rustc_data_structures/src/sso/map.rs index 7cdac5819..89b8c8526 100644 --- a/compiler/rustc_data_structures/src/sso/map.rs +++ b/compiler/rustc_data_structures/src/sso/map.rs @@ -1,24 +1,24 @@ -use super::either_iter::EitherIter; use crate::fx::FxHashMap; use arrayvec::ArrayVec; +use itertools::Either; use std::fmt; use std::hash::Hash; use std::ops::Index; -// For pointer-sized arguments arrays -// are faster than set/map for up to 64 -// arguments. -// -// On the other hand such a big array -// hurts cache performance, makes passing -// sso structures around very expensive. -// -// Biggest performance benefit is gained -// for reasonably small arrays that stay -// small in vast majority of cases. -// -// '8' is chosen as a sane default, to be -// reevaluated later. +/// For pointer-sized arguments arrays +/// are faster than set/map for up to 64 +/// arguments. +/// +/// On the other hand such a big array +/// hurts cache performance, makes passing +/// sso structures around very expensive. +/// +/// Biggest performance benefit is gained +/// for reasonably small arrays that stay +/// small in vast majority of cases. +/// +/// '8' is chosen as a sane default, to be +/// reevaluated later. const SSO_ARRAY_SIZE: usize = 8; /// Small-storage-optimized implementation of a map. @@ -138,8 +138,8 @@ impl<K, V> SsoHashMap<K, V> { /// The iterator element type is `&'a K`. pub fn keys(&self) -> impl Iterator<Item = &'_ K> { match self { - SsoHashMap::Array(array) => EitherIter::Left(array.iter().map(|(k, _v)| k)), - SsoHashMap::Map(map) => EitherIter::Right(map.keys()), + SsoHashMap::Array(array) => Either::Left(array.iter().map(|(k, _v)| k)), + SsoHashMap::Map(map) => Either::Right(map.keys()), } } @@ -147,8 +147,8 @@ impl<K, V> SsoHashMap<K, V> { /// The iterator element type is `&'a V`. pub fn values(&self) -> impl Iterator<Item = &'_ V> { match self { - SsoHashMap::Array(array) => EitherIter::Left(array.iter().map(|(_k, v)| v)), - SsoHashMap::Map(map) => EitherIter::Right(map.values()), + SsoHashMap::Array(array) => Either::Left(array.iter().map(|(_k, v)| v)), + SsoHashMap::Map(map) => Either::Right(map.values()), } } @@ -156,8 +156,8 @@ impl<K, V> SsoHashMap<K, V> { /// The iterator element type is `&'a mut V`. pub fn values_mut(&mut self) -> impl Iterator<Item = &'_ mut V> { match self { - SsoHashMap::Array(array) => EitherIter::Left(array.iter_mut().map(|(_k, v)| v)), - SsoHashMap::Map(map) => EitherIter::Right(map.values_mut()), + SsoHashMap::Array(array) => Either::Left(array.iter_mut().map(|(_k, v)| v)), + SsoHashMap::Map(map) => Either::Right(map.values_mut()), } } @@ -165,8 +165,8 @@ impl<K, V> SsoHashMap<K, V> { /// allocated memory for reuse. pub fn drain(&mut self) -> impl Iterator<Item = (K, V)> + '_ { match self { - SsoHashMap::Array(array) => EitherIter::Left(array.drain(..)), - SsoHashMap::Map(map) => EitherIter::Right(map.drain()), + SsoHashMap::Array(array) => Either::Left(array.drain(..)), + SsoHashMap::Map(map) => Either::Right(map.drain()), } } } @@ -406,16 +406,16 @@ where } impl<K, V> IntoIterator for SsoHashMap<K, V> { - type IntoIter = EitherIter< - <ArrayVec<(K, V), 8> as IntoIterator>::IntoIter, + type IntoIter = Either< + <ArrayVec<(K, V), SSO_ARRAY_SIZE> as IntoIterator>::IntoIter, <FxHashMap<K, V> as IntoIterator>::IntoIter, >; type Item = <Self::IntoIter as Iterator>::Item; fn into_iter(self) -> Self::IntoIter { match self { - SsoHashMap::Array(array) => EitherIter::Left(array.into_iter()), - SsoHashMap::Map(map) => EitherIter::Right(map.into_iter()), + SsoHashMap::Array(array) => Either::Left(array.into_iter()), + SsoHashMap::Map(map) => Either::Right(map.into_iter()), } } } @@ -435,9 +435,9 @@ fn adapt_array_mut_it<K, V>(pair: &mut (K, V)) -> (&K, &mut V) { } impl<'a, K, V> IntoIterator for &'a SsoHashMap<K, V> { - type IntoIter = EitherIter< + type IntoIter = Either< std::iter::Map< - <&'a ArrayVec<(K, V), 8> as IntoIterator>::IntoIter, + <&'a ArrayVec<(K, V), SSO_ARRAY_SIZE> as IntoIterator>::IntoIter, fn(&'a (K, V)) -> (&'a K, &'a V), >, <&'a FxHashMap<K, V> as IntoIterator>::IntoIter, @@ -446,16 +446,16 @@ impl<'a, K, V> IntoIterator for &'a SsoHashMap<K, V> { fn into_iter(self) -> Self::IntoIter { match self { - SsoHashMap::Array(array) => EitherIter::Left(array.into_iter().map(adapt_array_ref_it)), - SsoHashMap::Map(map) => EitherIter::Right(map.iter()), + SsoHashMap::Array(array) => Either::Left(array.into_iter().map(adapt_array_ref_it)), + SsoHashMap::Map(map) => Either::Right(map.iter()), } } } impl<'a, K, V> IntoIterator for &'a mut SsoHashMap<K, V> { - type IntoIter = EitherIter< + type IntoIter = Either< std::iter::Map< - <&'a mut ArrayVec<(K, V), 8> as IntoIterator>::IntoIter, + <&'a mut ArrayVec<(K, V), SSO_ARRAY_SIZE> as IntoIterator>::IntoIter, fn(&'a mut (K, V)) -> (&'a K, &'a mut V), >, <&'a mut FxHashMap<K, V> as IntoIterator>::IntoIter, @@ -464,8 +464,8 @@ impl<'a, K, V> IntoIterator for &'a mut SsoHashMap<K, V> { fn into_iter(self) -> Self::IntoIter { match self { - SsoHashMap::Array(array) => EitherIter::Left(array.into_iter().map(adapt_array_mut_it)), - SsoHashMap::Map(map) => EitherIter::Right(map.iter_mut()), + SsoHashMap::Array(array) => Either::Left(array.into_iter().map(adapt_array_mut_it)), + SsoHashMap::Map(map) => Either::Right(map.iter_mut()), } } } diff --git a/compiler/rustc_data_structures/src/sso/mod.rs b/compiler/rustc_data_structures/src/sso/mod.rs index dd21bc8e6..ef634b9ad 100644 --- a/compiler/rustc_data_structures/src/sso/mod.rs +++ b/compiler/rustc_data_structures/src/sso/mod.rs @@ -1,4 +1,3 @@ -mod either_iter; mod map; mod set; diff --git a/compiler/rustc_data_structures/src/stable_hasher.rs b/compiler/rustc_data_structures/src/stable_hasher.rs index e0d77cdae..3ed1de1bc 100644 --- a/compiler/rustc_data_structures/src/stable_hasher.rs +++ b/compiler/rustc_data_structures/src/stable_hasher.rs @@ -312,14 +312,14 @@ impl<CTX> HashStable<CTX> for ::std::num::NonZeroUsize { impl<CTX> HashStable<CTX> for f32 { fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { - let val: u32 = unsafe { ::std::mem::transmute(*self) }; + let val: u32 = self.to_bits(); val.hash_stable(ctx, hasher); } } impl<CTX> HashStable<CTX> for f64 { fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { - let val: u64 = unsafe { ::std::mem::transmute(*self) }; + let val: u64 = self.to_bits(); val.hash_stable(ctx, hasher); } } @@ -617,18 +617,10 @@ where } } -impl<K, R, HCX> HashStable<HCX> for ::std::collections::HashSet<K, R> -where - K: ToStableHashKey<HCX> + Eq, - R: BuildHasher, -{ - fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) { - stable_hash_reduce(hcx, hasher, self.iter(), self.len(), |hasher, hcx, key| { - let key = key.to_stable_hash_key(hcx); - key.hash_stable(hcx, hasher); - }); - } -} +// It is not safe to implement HashStable for HashSet or any other collection type +// with unstable but observable iteration order. +// See https://github.com/rust-lang/compiler-team/issues/533 for further information. +impl<V, HCX> !HashStable<HCX> for std::collections::HashSet<V> {} impl<K, V, HCX> HashStable<HCX> for ::std::collections::BTreeMap<K, V> where diff --git a/compiler/rustc_data_structures/src/stable_hasher/tests.rs b/compiler/rustc_data_structures/src/stable_hasher/tests.rs index 724be5888..a98b1bc36 100644 --- a/compiler/rustc_data_structures/src/stable_hasher/tests.rs +++ b/compiler/rustc_data_structures/src/stable_hasher/tests.rs @@ -39,7 +39,7 @@ fn test_hash_integers() { test_isize.hash(&mut h); // This depends on the hashing algorithm. See note at top of file. - let expected = (1784307454142909076, 11471672289340283879); + let expected = (13997337031081104755, 6178945012502239489); assert_eq!(h.finalize(), expected); } @@ -53,7 +53,7 @@ fn test_hash_usize() { test_usize.hash(&mut h); // This depends on the hashing algorithm. See note at top of file. - let expected = (5798740672699530587, 11186240177685111648); + let expected = (12037165114281468837, 3094087741167521712); assert_eq!(h.finalize(), expected); } @@ -67,7 +67,7 @@ fn test_hash_isize() { test_isize.hash(&mut h); // This depends on the hashing algorithm. See note at top of file. - let expected = (2789913510339652884, 674280939192711005); + let expected = (3979067582695659080, 2322428596355037273); assert_eq!(h.finalize(), expected); } diff --git a/compiler/rustc_data_structures/src/stack.rs b/compiler/rustc_data_structures/src/stack.rs index 3bdd67512..7ff1339c5 100644 --- a/compiler/rustc_data_structures/src/stack.rs +++ b/compiler/rustc_data_structures/src/stack.rs @@ -5,7 +5,7 @@ const RED_ZONE: usize = 100 * 1024; // 100k // Only the first stack that is pushed, grows exponentially (2^n * STACK_PER_RECURSION) from then // on. This flag has performance relevant characteristics. Don't set it too high. -const STACK_PER_RECURSION: usize = 1 * 1024 * 1024; // 1MB +const STACK_PER_RECURSION: usize = 1024 * 1024; // 1MB /// 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 diff --git a/compiler/rustc_data_structures/src/sync.rs b/compiler/rustc_data_structures/src/sync.rs index 31323c21d..ef1da8519 100644 --- a/compiler/rustc_data_structures/src/sync.rs +++ b/compiler/rustc_data_structures/src/sync.rs @@ -1,23 +1,45 @@ -//! This module defines types which are thread safe if cfg!(parallel_compiler) is true. +//! This module defines various operations and types that are implemented in +//! one way for the serial compiler, and another way the parallel compiler. //! -//! `Lrc` is an alias of `Arc` if cfg!(parallel_compiler) is true, `Rc` otherwise. +//! Operations +//! ---------- +//! The parallel versions of operations use Rayon to execute code in parallel, +//! while the serial versions degenerate straightforwardly to serial execution. +//! The operations include `join`, `parallel`, `par_iter`, and `par_for_each`. //! -//! `Lock` is a mutex. -//! It internally uses `parking_lot::Mutex` if cfg!(parallel_compiler) is true, -//! `RefCell` otherwise. +//! Types +//! ----- +//! The parallel versions of types provide various kinds of synchronization, +//! while the serial compiler versions do not. //! -//! `RwLock` is a read-write lock. -//! It internally uses `parking_lot::RwLock` if cfg!(parallel_compiler) is true, -//! `RefCell` otherwise. +//! The following table shows how the types are implemented internally. Except +//! where noted otherwise, the type in column one is defined as a +//! newtype around the type from column two or three. //! -//! `MTLock` is a mutex which disappears if cfg!(parallel_compiler) is false. +//! | Type | Serial version | Parallel version | +//! | ----------------------- | ------------------- | ------------------------------- | +//! | `Lrc<T>` | `rc::Rc<T>` | `sync::Arc<T>` | +//! |` Weak<T>` | `rc::Weak<T>` | `sync::Weak<T>` | +//! | | | | +//! | `AtomicBool` | `Cell<bool>` | `atomic::AtomicBool` | +//! | `AtomicU32` | `Cell<u32>` | `atomic::AtomicU32` | +//! | `AtomicU64` | `Cell<u64>` | `atomic::AtomicU64` | +//! | `AtomicUsize` | `Cell<usize>` | `atomic::AtomicUsize` | +//! | | | | +//! | `Lock<T>` | `RefCell<T>` | `parking_lot::Mutex<T>` | +//! | `RwLock<T>` | `RefCell<T>` | `parking_lot::RwLock<T>` | +//! | `MTLock<T>` [^1] | `T` | `Lock<T>` | +//! | `MTLockRef<'a, T>` [^2] | `&'a mut MTLock<T>` | `&'a MTLock<T>` | +//! | | | | +//! | `ParallelIterator` | `Iterator` | `rayon::iter::ParallelIterator` | //! -//! `MTRef` is an immutable reference if cfg!(parallel_compiler), and a mutable reference otherwise. +//! [^1] `MTLock` is similar to `Lock`, but the serial version avoids the cost +//! of a `RefCell`. This is appropriate when interior mutability is not +//! required. //! -//! `rustc_erase_owner!` erases an OwningRef owner into Erased or Erased + Send + Sync -//! depending on the value of cfg!(parallel_compiler). +//! [^2] `MTLockRef` is a typedef. -use crate::owning_ref::{Erased, OwningRef}; +use crate::owned_slice::OwnedSlice; use std::collections::HashMap; use std::hash::{BuildHasher, Hash}; use std::ops::{Deref, DerefMut}; @@ -26,24 +48,17 @@ use std::panic::{catch_unwind, resume_unwind, AssertUnwindSafe}; pub use std::sync::atomic::Ordering; pub use std::sync::atomic::Ordering::SeqCst; -pub use vec::AppendOnlyVec; +pub use vec::{AppendOnlyIndexVec, AppendOnlyVec}; mod vec; cfg_if! { if #[cfg(not(parallel_compiler))] { - pub auto trait Send {} - pub auto trait Sync {} + pub unsafe auto trait Send {} + pub unsafe auto trait Sync {} - impl<T> Send for T {} - impl<T> Sync for T {} - - #[macro_export] - macro_rules! rustc_erase_owner { - ($v:expr) => { - $v.erase_owner() - } - } + unsafe impl<T> Send for T {} + unsafe impl<T> Sync for T {} use std::ops::Add; @@ -82,6 +97,14 @@ cfg_if! { } } + impl Atomic<bool> { + pub fn fetch_or(&self, val: bool, _: Ordering) -> bool { + let result = self.0.get() | val; + self.0.set(val); + result + } + } + impl<T: Copy + PartialEq> Atomic<T> { #[inline] pub fn compare_exchange(&self, @@ -164,7 +187,7 @@ cfg_if! { } } - pub type MetadataRef = OwningRef<Box<dyn Erased>, [u8]>; + pub type MetadataRef = OwnedSlice; pub use std::rc::Rc as Lrc; pub use std::rc::Weak as Weak; @@ -209,7 +232,7 @@ cfg_if! { } } - pub type MTRef<'a, T> = &'a mut T; + pub type MTLockRef<'a, T> = &'a mut MTLock<T>; #[derive(Debug, Default)] pub struct MTLock<T>(T); @@ -267,7 +290,7 @@ cfg_if! { pub use std::sync::Arc as Lrc; pub use std::sync::Weak as Weak; - pub type MTRef<'a, T> = &'a T; + pub type MTLockRef<'a, T> = &'a MTLock<T>; #[derive(Debug, Default)] pub struct MTLock<T>(Lock<T>); @@ -347,20 +370,11 @@ cfg_if! { }); } - pub type MetadataRef = OwningRef<Box<dyn Erased + Send + Sync>, [u8]>; + pub type MetadataRef = OwnedSlice; /// This makes locks panic if they are already held. /// It is only useful when you are running in a single thread const ERROR_CHECKING: bool = false; - - #[macro_export] - macro_rules! rustc_erase_owner { - ($v:expr) => {{ - let v = $v; - ::rustc_data_structures::sync::assert_send_val(&v); - v.erase_send_sync_owner() - }} - } } } @@ -456,14 +470,6 @@ impl<T: Default> Default for Lock<T> { } } -// FIXME: Probably a bad idea -impl<T: Clone> Clone for Lock<T> { - #[inline] - fn clone(&self) -> Self { - Lock::new(self.borrow().clone()) - } -} - #[derive(Debug, Default)] pub struct RwLock<T>(InnerRwLock<T>); @@ -555,18 +561,6 @@ impl<T> RwLock<T> { #[cfg(not(parallel_compiler))] #[inline(always)] - pub fn clone_guard<'a>(rg: &ReadGuard<'a, T>) -> ReadGuard<'a, T> { - ReadGuard::clone(rg) - } - - #[cfg(parallel_compiler)] - #[inline(always)] - pub fn clone_guard<'a>(rg: &ReadGuard<'a, T>) -> ReadGuard<'a, T> { - ReadGuard::rwlock(&rg).read() - } - - #[cfg(not(parallel_compiler))] - #[inline(always)] pub fn leak(&self) -> &T { ReadGuard::leak(self.read()) } diff --git a/compiler/rustc_data_structures/src/sync/vec.rs b/compiler/rustc_data_structures/src/sync/vec.rs index cbea4f059..1783b4b35 100644 --- a/compiler/rustc_data_structures/src/sync/vec.rs +++ b/compiler/rustc_data_structures/src/sync/vec.rs @@ -2,7 +2,8 @@ use std::marker::PhantomData; use rustc_index::vec::Idx; -pub struct AppendOnlyVec<I: Idx, T: Copy> { +#[derive(Default)] +pub struct AppendOnlyIndexVec<I: Idx, T: Copy> { #[cfg(not(parallel_compiler))] vec: elsa::vec::FrozenVec<T>, #[cfg(parallel_compiler)] @@ -10,7 +11,7 @@ pub struct AppendOnlyVec<I: Idx, T: Copy> { _marker: PhantomData<fn(&I)>, } -impl<I: Idx, T: Copy> AppendOnlyVec<I, T> { +impl<I: Idx, T: Copy> AppendOnlyIndexVec<I, T> { pub fn new() -> Self { Self { #[cfg(not(parallel_compiler))] @@ -39,3 +40,66 @@ impl<I: Idx, T: Copy> AppendOnlyVec<I, T> { return self.vec.get(i); } } + +#[derive(Default)] +pub struct AppendOnlyVec<T: Copy> { + #[cfg(not(parallel_compiler))] + vec: elsa::vec::FrozenVec<T>, + #[cfg(parallel_compiler)] + vec: elsa::sync::LockFreeFrozenVec<T>, +} + +impl<T: Copy> AppendOnlyVec<T> { + pub fn new() -> Self { + Self { + #[cfg(not(parallel_compiler))] + vec: elsa::vec::FrozenVec::new(), + #[cfg(parallel_compiler)] + vec: elsa::sync::LockFreeFrozenVec::new(), + } + } + + pub fn push(&self, val: T) -> usize { + #[cfg(not(parallel_compiler))] + let i = self.vec.len(); + #[cfg(not(parallel_compiler))] + self.vec.push(val); + #[cfg(parallel_compiler)] + let i = self.vec.push(val); + i + } + + pub fn get(&self, i: usize) -> Option<T> { + #[cfg(not(parallel_compiler))] + return self.vec.get_copy(i); + #[cfg(parallel_compiler)] + return self.vec.get(i); + } + + pub fn iter_enumerated(&self) -> impl Iterator<Item = (usize, T)> + '_ { + (0..) + .map(|i| (i, self.get(i))) + .take_while(|(_, o)| o.is_some()) + .filter_map(|(i, o)| Some((i, o?))) + } + + pub fn iter(&self) -> impl Iterator<Item = T> + '_ { + (0..).map(|i| self.get(i)).take_while(|o| o.is_some()).flatten() + } +} + +impl<T: Copy + PartialEq> AppendOnlyVec<T> { + pub fn contains(&self, val: T) -> bool { + self.iter_enumerated().any(|(_, v)| v == val) + } +} + +impl<A: Copy> FromIterator<A> for AppendOnlyVec<A> { + fn from_iter<T: IntoIterator<Item = A>>(iter: T) -> Self { + let this = Self::new(); + for val in iter { + this.push(val); + } + this + } +} diff --git a/compiler/rustc_data_structures/src/unord.rs b/compiler/rustc_data_structures/src/unord.rs index f35f18e51..6c8d54146 100644 --- a/compiler/rustc_data_structures/src/unord.rs +++ b/compiler/rustc_data_structures/src/unord.rs @@ -109,6 +109,12 @@ impl<T, I: Iterator<Item = T>> UnordItems<T, I> { } } +impl<T> UnordItems<T, std::iter::Empty<T>> { + pub fn empty() -> Self { + UnordItems(std::iter::empty()) + } +} + impl<'a, T: Clone + 'a, I: Iterator<Item = &'a T>> UnordItems<&'a T, I> { #[inline] pub fn cloned(self) -> UnordItems<T, impl Iterator<Item = T>> { @@ -133,6 +139,20 @@ impl<T: Ord, I: Iterator<Item = T>> UnordItems<T, I> { items } + #[inline] + pub fn into_sorted_stable_ord(self, use_stable_sort: bool) -> Vec<T> + where + T: Ord + StableOrd, + { + let mut items: Vec<T> = self.0.collect(); + if use_stable_sort { + items.sort(); + } else { + items.sort_unstable() + } + items + } + pub fn into_sorted_small_vec<HCX, const LEN: usize>(self, hcx: &HCX) -> SmallVec<[T; LEN]> where T: ToStableHashKey<HCX>, @@ -176,6 +196,11 @@ impl<V: Eq + Hash> UnordSet<V> { } #[inline] + pub fn is_empty(&self) -> bool { + self.inner.is_empty() + } + + #[inline] pub fn insert(&mut self, v: V) -> bool { self.inner.insert(v) } @@ -199,7 +224,7 @@ impl<V: Eq + Hash> UnordSet<V> { } #[inline] - pub fn items<'a>(&'a self) -> UnordItems<&'a V, impl Iterator<Item = &'a V>> { + pub fn items(&self) -> UnordItems<&V, impl Iterator<Item = &V>> { UnordItems(self.inner.iter()) } @@ -253,7 +278,7 @@ impl<V: Eq + Hash> UnordSet<V> { // We can safely extend this UnordSet from a set of unordered values because that // won't expose the internal ordering anywhere. #[inline] - pub fn extend<I: Iterator<Item = V>>(&mut self, items: UnordItems<V, I>) { + pub fn extend_unord<I: Iterator<Item = V>>(&mut self, items: UnordItems<V, I>) { self.inner.extend(items.0) } @@ -277,6 +302,12 @@ impl<V: Hash + Eq> FromIterator<V> for UnordSet<V> { } } +impl<V: Hash + Eq> From<FxHashSet<V>> for UnordSet<V> { + fn from(value: FxHashSet<V>) -> Self { + UnordSet { inner: value } + } +} + impl<HCX, V: Hash + Eq + HashStable<HCX>> HashStable<HCX> for UnordSet<V> { #[inline] fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) { @@ -384,7 +415,7 @@ impl<K: Eq + Hash, V> UnordMap<K, V> { } #[inline] - pub fn items<'a>(&'a self) -> UnordItems<(&'a K, &'a V), impl Iterator<Item = (&'a K, &'a V)>> { + pub fn items(&self) -> UnordItems<(&K, &V), impl Iterator<Item = (&K, &V)>> { UnordItems(self.inner.iter()) } diff --git a/compiler/rustc_data_structures/src/vec_map.rs b/compiler/rustc_data_structures/src/vec_map.rs deleted file mode 100644 index d1a99bcae..000000000 --- a/compiler/rustc_data_structures/src/vec_map.rs +++ /dev/null @@ -1,192 +0,0 @@ -use std::borrow::Borrow; -use std::fmt::Debug; -use std::slice::Iter; -use std::vec::IntoIter; - -use crate::stable_hasher::{HashStable, StableHasher}; - -/// A map type implemented as a vector of pairs `K` (key) and `V` (value). -/// It currently provides a subset of all the map operations, the rest could be added as needed. -#[derive(Clone, Encodable, Decodable, Debug)] -pub struct VecMap<K, V>(Vec<(K, V)>); - -impl<K, V> VecMap<K, V> -where - K: Debug + PartialEq, - V: Debug, -{ - pub fn new() -> Self { - VecMap(Default::default()) - } - - /// Sets the value of the entry, and returns the entry's old value. - pub fn insert(&mut self, k: K, v: V) -> Option<V> { - if let Some(elem) = self.0.iter_mut().find(|(key, _)| *key == k) { - Some(std::mem::replace(&mut elem.1, v)) - } else { - self.0.push((k, v)); - None - } - } - - /// Removes the entry from the map and returns the removed value - pub fn remove(&mut self, k: &K) -> Option<V> { - self.0.iter().position(|(k2, _)| k2 == k).map(|pos| self.0.remove(pos).1) - } - - /// Gets a reference to the value in the entry. - pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V> - where - K: Borrow<Q>, - Q: Eq, - { - self.0.iter().find(|(key, _)| k == key.borrow()).map(|elem| &elem.1) - } - - /// Gets a mutable reference to the value in the entry. - pub fn get_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut V> - where - K: Borrow<Q>, - Q: Eq, - { - self.0.iter_mut().find(|(key, _)| k == key.borrow()).map(|elem| &mut elem.1) - } - - /// Returns the any value corresponding to the supplied predicate filter. - /// - /// The supplied predicate will be applied to each (key, value) pair and it will return a - /// reference to the values where the predicate returns `true`. - pub fn any_value_matching(&self, mut predicate: impl FnMut(&(K, V)) -> bool) -> Option<&V> { - self.0.iter().find(|kv| predicate(kv)).map(|elem| &elem.1) - } - - /// Returns the value corresponding to the supplied predicate filter. It crashes if there's - /// more than one matching element. - /// - /// The supplied predicate will be applied to each (key, value) pair and it will return a - /// reference to the value where the predicate returns `true`. - pub fn get_value_matching(&self, mut predicate: impl FnMut(&(K, V)) -> bool) -> Option<&V> { - let mut filter = self.0.iter().filter(|kv| predicate(kv)); - let (_, value) = filter.next()?; - // This should return just one element, otherwise it's a bug - assert!( - filter.next().is_none(), - "Collection {self:#?} should have just one matching element" - ); - Some(value) - } - - /// Returns `true` if the map contains a value for the specified key. - /// - /// The key may be any borrowed form of the map's key type, - /// [`Eq`] on the borrowed form *must* match those for - /// the key type. - pub fn contains_key<Q: ?Sized>(&self, k: &Q) -> bool - where - K: Borrow<Q>, - Q: Eq, - { - self.get(k).is_some() - } - - /// Returns `true` if the map contains no elements. - pub fn is_empty(&self) -> bool { - self.0.is_empty() - } - - pub fn iter(&self) -> Iter<'_, (K, V)> { - self.into_iter() - } - - pub fn iter_mut(&mut self) -> impl Iterator<Item = (&K, &mut V)> { - self.into_iter() - } - - pub fn retain(&mut self, f: impl Fn(&(K, V)) -> bool) { - self.0.retain(f) - } -} - -impl<K, V> Default for VecMap<K, V> { - #[inline] - fn default() -> Self { - Self(Default::default()) - } -} - -impl<K, V> From<Vec<(K, V)>> for VecMap<K, V> { - fn from(vec: Vec<(K, V)>) -> Self { - Self(vec) - } -} - -impl<K, V> Into<Vec<(K, V)>> for VecMap<K, V> { - fn into(self) -> Vec<(K, V)> { - self.0 - } -} - -impl<K, V> FromIterator<(K, V)> for VecMap<K, V> { - fn from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> Self { - Self(iter.into_iter().collect()) - } -} - -impl<'a, K, V> IntoIterator for &'a VecMap<K, V> { - type Item = &'a (K, V); - type IntoIter = Iter<'a, (K, V)>; - - #[inline] - fn into_iter(self) -> Self::IntoIter { - self.0.iter() - } -} - -impl<'a, K: 'a, V: 'a> IntoIterator for &'a mut VecMap<K, V> { - type Item = (&'a K, &'a mut V); - type IntoIter = impl Iterator<Item = Self::Item>; - - #[inline] - fn into_iter(self) -> Self::IntoIter { - self.0.iter_mut().map(|(k, v)| (&*k, v)) - } -} - -impl<K, V> IntoIterator for VecMap<K, V> { - type Item = (K, V); - type IntoIter = IntoIter<(K, V)>; - - #[inline] - fn into_iter(self) -> Self::IntoIter { - self.0.into_iter() - } -} - -impl<K: PartialEq + Debug, V: Debug> Extend<(K, V)> for VecMap<K, V> { - fn extend<I: IntoIterator<Item = (K, V)>>(&mut self, iter: I) { - for (k, v) in iter { - self.insert(k, v); - } - } - - fn extend_one(&mut self, (k, v): (K, V)) { - self.insert(k, v); - } - - fn extend_reserve(&mut self, additional: usize) { - self.0.extend_reserve(additional); - } -} - -impl<K, V, CTX> HashStable<CTX> for VecMap<K, V> -where - K: HashStable<CTX> + Eq, - V: HashStable<CTX>, -{ - fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher) { - self.0.hash_stable(hcx, hasher) - } -} - -#[cfg(test)] -mod tests; diff --git a/compiler/rustc_data_structures/src/vec_map/tests.rs b/compiler/rustc_data_structures/src/vec_map/tests.rs deleted file mode 100644 index 458b60077..000000000 --- a/compiler/rustc_data_structures/src/vec_map/tests.rs +++ /dev/null @@ -1,48 +0,0 @@ -use super::*; - -impl<K, V> VecMap<K, V> { - fn into_vec(self) -> Vec<(K, V)> { - self.0.into() - } -} - -#[test] -fn test_from_iterator() { - assert_eq!( - std::iter::empty().collect::<VecMap<i32, bool>>().into_vec(), - Vec::<(i32, bool)>::new() - ); - assert_eq!(std::iter::once((42, true)).collect::<VecMap<_, _>>().into_vec(), vec![(42, true)]); - assert_eq!( - [(1, true), (2, false)].into_iter().collect::<VecMap<_, _>>().into_vec(), - vec![(1, true), (2, false)] - ); -} - -#[test] -fn test_into_iterator_owned() { - assert_eq!(VecMap::new().into_iter().collect::<Vec<(i32, bool)>>(), Vec::<(i32, bool)>::new()); - assert_eq!(VecMap::from(vec![(1, true)]).into_iter().collect::<Vec<_>>(), vec![(1, true)]); - assert_eq!( - VecMap::from(vec![(1, true), (2, false)]).into_iter().collect::<Vec<_>>(), - vec![(1, true), (2, false)] - ); -} - -#[test] -fn test_insert() { - let mut v = VecMap::new(); - assert_eq!(v.insert(1, true), None); - assert_eq!(v.insert(2, false), None); - assert_eq!(v.clone().into_vec(), vec![(1, true), (2, false)]); - assert_eq!(v.insert(1, false), Some(true)); - assert_eq!(v.into_vec(), vec![(1, false), (2, false)]); -} - -#[test] -fn test_get() { - let v = [(1, true), (2, false)].into_iter().collect::<VecMap<_, _>>(); - assert_eq!(v.get(&1), Some(&true)); - assert_eq!(v.get(&2), Some(&false)); - assert_eq!(v.get(&3), None); -} |