diff options
Diffstat (limited to 'compiler/rustc_data_structures')
| -rw-r--r-- | compiler/rustc_data_structures/Cargo.toml | 23 | ||||
| -rw-r--r-- | compiler/rustc_data_structures/src/fingerprint.rs | 4 | ||||
| -rw-r--r-- | compiler/rustc_data_structures/src/fx.rs | 15 | ||||
| -rw-r--r-- | compiler/rustc_data_structures/src/lib.rs | 2 | ||||
| -rw-r--r-- | compiler/rustc_data_structures/src/map_in_place.rs | 2 | ||||
| -rw-r--r-- | compiler/rustc_data_structures/src/obligation_forest/mod.rs | 41 | ||||
| -rw-r--r-- | compiler/rustc_data_structures/src/obligation_forest/tests.rs | 8 | ||||
| -rw-r--r-- | compiler/rustc_data_structures/src/sorted_map.rs | 20 | ||||
| -rw-r--r-- | compiler/rustc_data_structures/src/sync.rs | 2 | ||||
| -rw-r--r-- | compiler/rustc_data_structures/src/thin_vec.rs | 180 | ||||
| -rw-r--r-- | compiler/rustc_data_structures/src/thin_vec/tests.rs | 42 |
11 files changed, 77 insertions, 262 deletions
diff --git a/compiler/rustc_data_structures/Cargo.toml b/compiler/rustc_data_structures/Cargo.toml index 5c641f54f68..2d8658db5e6 100644 --- a/compiler/rustc_data_structures/Cargo.toml +++ b/compiler/rustc_data_structures/Cargo.toml @@ -8,25 +8,26 @@ doctest = false [dependencies] arrayvec = { version = "0.7", default-features = false } +bitflags = "1.2.1" +cfg-if = "0.1.2" ena = "0.14" indexmap = { version = "1.9.1" } -tracing = "0.1" jobserver_crate = { version = "0.1.13", package = "jobserver" } -rustc_serialize = { path = "../rustc_serialize" } -rustc_macros = { path = "../rustc_macros" } -rustc_graphviz = { path = "../rustc_graphviz" } -cfg-if = "0.1.2" -stable_deref_trait = "1.0.0" -rayon = { version = "0.4.0", package = "rustc-rayon", optional = true } +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_graphviz = { path = "../rustc_graphviz" } rustc-hash = "1.1.0" -smallvec = { version = "1.8.1", features = ["const_generics", "union", "may_dangle"] } rustc_index = { path = "../rustc_index", package = "rustc_index" } -bitflags = "1.2.1" -measureme = "10.0.0" -libc = "0.2" +rustc_macros = { path = "../rustc_macros" } +rustc_serialize = { path = "../rustc_serialize" } +smallvec = { version = "1.8.1", features = ["const_generics", "union", "may_dangle"] } +stable_deref_trait = "1.0.0" stacker = "0.1.14" tempfile = "3.2" +thin-vec = "0.2.8" +tracing = "0.1" [dependencies.parking_lot] version = "0.11" diff --git a/compiler/rustc_data_structures/src/fingerprint.rs b/compiler/rustc_data_structures/src/fingerprint.rs index 5ff2d18dd2b..a39178016ce 100644 --- a/compiler/rustc_data_structures/src/fingerprint.rs +++ b/compiler/rustc_data_structures/src/fingerprint.rs @@ -29,7 +29,7 @@ impl Fingerprint { // quality hash values, let's still combine the two values because the // Fingerprints in DefPathHash have the StableCrateId portion which is // the same for all DefPathHashes from the same crate. Combining the - // two halfs makes sure we get a good quality hash in such cases too. + // two halves makes sure we get a good quality hash in such cases too. self.0.wrapping_mul(3).wrapping_add(self.1) } @@ -120,7 +120,7 @@ impl FingerprintHasher for crate::unhash::Unhasher { // quality hash values, let's still combine the two values because the // Fingerprints in DefPathHash have the StableCrateId portion which is // the same for all DefPathHashes from the same crate. Combining the - // two halfs makes sure we get a good quality hash in such cases too. + // two halves makes sure we get a good quality hash in such cases too. // // Since `Unhasher` is used only in the context of HashMaps, it is OK // to combine the two components in an order-independent way (which is diff --git a/compiler/rustc_data_structures/src/fx.rs b/compiler/rustc_data_structures/src/fx.rs index bbeb193dba3..0d0c51b6819 100644 --- a/compiler/rustc_data_structures/src/fx.rs +++ b/compiler/rustc_data_structures/src/fx.rs @@ -2,13 +2,26 @@ use std::hash::BuildHasherDefault; pub use rustc_hash::{FxHashMap, FxHashSet, FxHasher}; +pub type StdEntry<'a, K, V> = std::collections::hash_map::Entry<'a, K, V>; + pub type FxIndexMap<K, V> = indexmap::IndexMap<K, V, BuildHasherDefault<FxHasher>>; pub type FxIndexSet<V> = indexmap::IndexSet<V, BuildHasherDefault<FxHasher>>; +pub type IndexEntry<'a, K, V> = indexmap::map::Entry<'a, K, V>; #[macro_export] macro_rules! define_id_collections { - ($map_name:ident, $set_name:ident, $key:ty) => { + ($map_name:ident, $set_name:ident, $entry_name:ident, $key:ty) => { pub type $map_name<T> = $crate::fx::FxHashMap<$key, T>; pub type $set_name = $crate::fx::FxHashSet<$key>; + pub type $entry_name<'a, T> = $crate::fx::StdEntry<'a, $key, T>; + }; +} + +#[macro_export] +macro_rules! define_stable_id_collections { + ($map_name:ident, $set_name:ident, $entry_name:ident, $key:ty) => { + pub type $map_name<T> = $crate::fx::FxIndexMap<$key, T>; + pub type $set_name = $crate::fx::FxIndexSet<$key>; + pub type $entry_name<'a, T> = $crate::fx::IndexEntry<'a, $key, T>; }; } diff --git a/compiler/rustc_data_structures/src/lib.rs b/compiler/rustc_data_structures/src/lib.rs index c8b09cffe01..467ac401d08 100644 --- a/compiler/rustc_data_structures/src/lib.rs +++ b/compiler/rustc_data_structures/src/lib.rs @@ -13,7 +13,6 @@ #![feature(cell_leak)] #![feature(control_flow_enum)] #![feature(extend_one)] -#![feature(let_else)] #![feature(hash_raw_entry)] #![feature(hasher_prefixfree_extras)] #![feature(maybe_uninit_uninit_array)] @@ -75,7 +74,6 @@ pub mod profiling; pub mod sharded; pub mod stack; pub mod sync; -pub mod thin_vec; pub mod tiny_list; pub mod transitive_relation; pub mod vec_linked_list; diff --git a/compiler/rustc_data_structures/src/map_in_place.rs b/compiler/rustc_data_structures/src/map_in_place.rs index d912211443a..a0d4b7ade1f 100644 --- a/compiler/rustc_data_structures/src/map_in_place.rs +++ b/compiler/rustc_data_structures/src/map_in_place.rs @@ -1,6 +1,6 @@ -use crate::thin_vec::ThinVec; 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) diff --git a/compiler/rustc_data_structures/src/obligation_forest/mod.rs b/compiler/rustc_data_structures/src/obligation_forest/mod.rs index 07a96dd7dbb..10e673cd929 100644 --- a/compiler/rustc_data_structures/src/obligation_forest/mod.rs +++ b/compiler/rustc_data_structures/src/obligation_forest/mod.rs @@ -95,6 +95,10 @@ pub trait ForestObligation: Clone + Debug { pub trait ObligationProcessor { type Obligation: ForestObligation; type Error: Debug; + type OUT: OutcomeTrait< + Obligation = Self::Obligation, + Error = Error<Self::Obligation, Self::Error>, + >; fn needs_process_obligation(&self, obligation: &Self::Obligation) -> bool; @@ -111,12 +115,20 @@ pub trait ObligationProcessor { /// In other words, if we had O1 which required O2 which required /// O3 which required O1, we would give an iterator yielding O1, /// O2, O3 (O1 is not yielded twice). - fn process_backedge<'c, I>(&mut self, cycle: I, _marker: PhantomData<&'c Self::Obligation>) + fn process_backedge<'c, I>( + &mut self, + cycle: I, + _marker: PhantomData<&'c Self::Obligation>, + ) -> Result<(), Self::Error> where I: Clone + Iterator<Item = &'c Self::Obligation>; } /// The result type used by `process_obligation`. +// `repr(C)` to inhibit the niche filling optimization. Otherwise, the `match` appearing +// in `process_obligations` is significantly slower, which can substantially affect +// benchmarks like `rustc-perf`'s inflate and keccak. +#[repr(C)] #[derive(Debug)] pub enum ProcessResult<O, E> { Unchanged, @@ -398,12 +410,11 @@ impl<O: ForestObligation> ObligationForest<O> { /// Performs a fixpoint computation over the obligation list. #[inline(never)] - pub fn process_obligations<P, OUT>(&mut self, processor: &mut P) -> OUT + pub fn process_obligations<P>(&mut self, processor: &mut P) -> P::OUT where P: ObligationProcessor<Obligation = O>, - OUT: OutcomeTrait<Obligation = O, Error = Error<O, P::Error>>, { - let mut outcome = OUT::new(); + let mut outcome = P::OUT::new(); // Fixpoint computation: we repeat until the inner loop stalls. loop { @@ -469,7 +480,7 @@ impl<O: ForestObligation> ObligationForest<O> { } self.mark_successes(); - self.process_cycles(processor); + self.process_cycles(processor, &mut outcome); self.compress(|obl| outcome.record_completed(obl)); } @@ -554,7 +565,7 @@ impl<O: ForestObligation> ObligationForest<O> { /// Report cycles between all `Success` nodes, and convert all `Success` /// nodes to `Done`. This must be called after `mark_successes`. - fn process_cycles<P>(&mut self, processor: &mut P) + fn process_cycles<P>(&mut self, processor: &mut P, outcome: &mut P::OUT) where P: ObligationProcessor<Obligation = O>, { @@ -564,7 +575,7 @@ impl<O: ForestObligation> ObligationForest<O> { // to handle the no-op cases immediately to avoid the cost of the // function call. if node.state.get() == NodeState::Success { - self.find_cycles_from_node(&mut stack, processor, index); + self.find_cycles_from_node(&mut stack, processor, index, outcome); } } @@ -572,8 +583,13 @@ impl<O: ForestObligation> ObligationForest<O> { self.reused_node_vec = stack; } - fn find_cycles_from_node<P>(&self, stack: &mut Vec<usize>, processor: &mut P, index: usize) - where + fn find_cycles_from_node<P>( + &self, + stack: &mut Vec<usize>, + processor: &mut P, + index: usize, + outcome: &mut P::OUT, + ) where P: ObligationProcessor<Obligation = O>, { let node = &self.nodes[index]; @@ -582,17 +598,20 @@ impl<O: ForestObligation> ObligationForest<O> { None => { stack.push(index); for &dep_index in node.dependents.iter() { - self.find_cycles_from_node(stack, processor, dep_index); + self.find_cycles_from_node(stack, processor, dep_index, outcome); } stack.pop(); node.state.set(NodeState::Done); } Some(rpos) => { // Cycle detected. - processor.process_backedge( + let result = processor.process_backedge( stack[rpos..].iter().map(|&i| &self.nodes[i].obligation), PhantomData, ); + if let Err(err) = result { + outcome.record_error(Error { error: err, backtrace: self.error_at(index) }); + } } } } diff --git a/compiler/rustc_data_structures/src/obligation_forest/tests.rs b/compiler/rustc_data_structures/src/obligation_forest/tests.rs index e2991aae174..bc252f772a1 100644 --- a/compiler/rustc_data_structures/src/obligation_forest/tests.rs +++ b/compiler/rustc_data_structures/src/obligation_forest/tests.rs @@ -64,6 +64,7 @@ where { type Obligation = O; type Error = E; + type OUT = TestOutcome<O, E>; fn needs_process_obligation(&self, _obligation: &Self::Obligation) -> bool { true @@ -76,10 +77,15 @@ where (self.process_obligation)(obligation) } - fn process_backedge<'c, I>(&mut self, _cycle: I, _marker: PhantomData<&'c Self::Obligation>) + fn process_backedge<'c, I>( + &mut self, + _cycle: I, + _marker: PhantomData<&'c Self::Obligation>, + ) -> Result<(), Self::Error> where I: Clone + Iterator<Item = &'c Self::Obligation>, { + Ok(()) } } diff --git a/compiler/rustc_data_structures/src/sorted_map.rs b/compiler/rustc_data_structures/src/sorted_map.rs index 9efea1228ab..937cb671573 100644 --- a/compiler/rustc_data_structures/src/sorted_map.rs +++ b/compiler/rustc_data_structures/src/sorted_map.rs @@ -164,7 +164,7 @@ impl<K: Ord, V> SortedMap<K, V> { /// It is up to the caller to make sure that the elements are sorted by key /// and that there are no duplicates. #[inline] - pub fn insert_presorted(&mut self, mut elements: Vec<(K, V)>) { + pub fn insert_presorted(&mut self, elements: Vec<(K, V)>) { if elements.is_empty() { return; } @@ -173,28 +173,28 @@ impl<K: Ord, V> SortedMap<K, V> { let start_index = self.lookup_index_for(&elements[0].0); - let drain = match start_index { + let elements = match start_index { Ok(index) => { - let mut drain = elements.drain(..); - self.data[index] = drain.next().unwrap(); - drain + let mut elements = elements.into_iter(); + self.data[index] = elements.next().unwrap(); + elements } Err(index) => { if index == self.data.len() || elements.last().unwrap().0 < self.data[index].0 { // We can copy the whole range without having to mix with // existing elements. - self.data.splice(index..index, elements.drain(..)); + self.data.splice(index..index, elements.into_iter()); return; } - let mut drain = elements.drain(..); - self.data.insert(index, drain.next().unwrap()); - drain + let mut elements = elements.into_iter(); + self.data.insert(index, elements.next().unwrap()); + elements } }; // Insert the rest - for (k, v) in drain { + for (k, v) in elements { self.insert(k, v); } } diff --git a/compiler/rustc_data_structures/src/sync.rs b/compiler/rustc_data_structures/src/sync.rs index 258780ecaea..9c0fb8265cf 100644 --- a/compiler/rustc_data_structures/src/sync.rs +++ b/compiler/rustc_data_structures/src/sync.rs @@ -48,7 +48,7 @@ cfg_if! { /// the native atomic types. /// You should use this type through the `AtomicU64`, `AtomicUsize`, etc, type aliases /// as it's not intended to be used separately. - #[derive(Debug)] + #[derive(Debug, Default)] pub struct Atomic<T: Copy>(Cell<T>); impl<T: Copy> Atomic<T> { diff --git a/compiler/rustc_data_structures/src/thin_vec.rs b/compiler/rustc_data_structures/src/thin_vec.rs deleted file mode 100644 index fce42e709ab..00000000000 --- a/compiler/rustc_data_structures/src/thin_vec.rs +++ /dev/null @@ -1,180 +0,0 @@ -use crate::stable_hasher::{HashStable, StableHasher}; - -use std::iter::FromIterator; - -/// A vector type optimized for cases where this size is usually 0 (cf. `SmallVec`). -/// The `Option<Box<..>>` wrapping allows us to represent a zero sized vector with `None`, -/// which uses only a single (null) pointer. -#[derive(Clone, Encodable, Decodable, Debug, Hash, Eq, PartialEq)] -pub struct ThinVec<T>(Option<Box<Vec<T>>>); - -impl<T> ThinVec<T> { - pub fn new() -> Self { - ThinVec(None) - } - - pub fn iter(&self) -> std::slice::Iter<'_, T> { - self.into_iter() - } - - pub fn iter_mut(&mut self) -> std::slice::IterMut<'_, T> { - self.into_iter() - } - - pub fn push(&mut self, item: T) { - match *self { - ThinVec(Some(ref mut vec)) => vec.push(item), - ThinVec(None) => *self = vec![item].into(), - } - } - - /// Note: if `set_len(0)` is called on a non-empty `ThinVec`, it will - /// remain in the `Some` form. This is required for some code sequences - /// (such as the one in `flat_map_in_place`) that call `set_len(0)` before - /// an operation that might panic, and then call `set_len(n)` again - /// afterwards. - pub unsafe fn set_len(&mut self, new_len: usize) { - match *self { - ThinVec(None) => { - // A prerequisite of `Vec::set_len` is that `new_len` must be - // less than or equal to capacity(). The same applies here. - if new_len != 0 { - panic!("unsafe ThinVec::set_len({})", new_len); - } - } - ThinVec(Some(ref mut vec)) => vec.set_len(new_len), - } - } - - pub fn insert(&mut self, index: usize, value: T) { - match *self { - ThinVec(None) => { - if index == 0 { - *self = vec![value].into(); - } else { - panic!("invalid ThinVec::insert"); - } - } - ThinVec(Some(ref mut vec)) => vec.insert(index, value), - } - } - - pub fn remove(&mut self, index: usize) -> T { - match self { - ThinVec(None) => panic!("invalid ThinVec::remove"), - ThinVec(Some(vec)) => vec.remove(index), - } - } - - pub fn as_slice(&self) -> &[T] { - match self { - ThinVec(None) => &[], - ThinVec(Some(vec)) => vec.as_slice(), - } - } -} - -impl<T> From<Vec<T>> for ThinVec<T> { - fn from(vec: Vec<T>) -> Self { - if vec.is_empty() { ThinVec(None) } else { ThinVec(Some(Box::new(vec))) } - } -} - -impl<T> Into<Vec<T>> for ThinVec<T> { - fn into(self) -> Vec<T> { - match self { - ThinVec(None) => Vec::new(), - ThinVec(Some(vec)) => *vec, - } - } -} - -impl<T> ::std::ops::Deref for ThinVec<T> { - type Target = [T]; - fn deref(&self) -> &[T] { - match *self { - ThinVec(None) => &[], - ThinVec(Some(ref vec)) => vec, - } - } -} - -impl<T> ::std::ops::DerefMut for ThinVec<T> { - fn deref_mut(&mut self) -> &mut [T] { - match *self { - ThinVec(None) => &mut [], - ThinVec(Some(ref mut vec)) => vec, - } - } -} - -impl<T> FromIterator<T> for ThinVec<T> { - fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self { - // `Vec::from_iter()` should not allocate if the iterator is empty. - let vec: Vec<_> = iter.into_iter().collect(); - if vec.is_empty() { ThinVec(None) } else { ThinVec(Some(Box::new(vec))) } - } -} - -impl<T> IntoIterator for ThinVec<T> { - type Item = T; - type IntoIter = std::vec::IntoIter<T>; - - fn into_iter(self) -> Self::IntoIter { - // This is still performant because `Vec::new()` does not allocate. - self.0.map_or_else(Vec::new, |ptr| *ptr).into_iter() - } -} - -impl<'a, T> IntoIterator for &'a ThinVec<T> { - type Item = &'a T; - type IntoIter = std::slice::Iter<'a, T>; - - fn into_iter(self) -> Self::IntoIter { - self.as_ref().iter() - } -} - -impl<'a, T> IntoIterator for &'a mut ThinVec<T> { - type Item = &'a mut T; - type IntoIter = std::slice::IterMut<'a, T>; - - fn into_iter(self) -> Self::IntoIter { - self.as_mut().iter_mut() - } -} - -impl<T> Extend<T> for ThinVec<T> { - fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) { - match *self { - ThinVec(Some(ref mut vec)) => vec.extend(iter), - ThinVec(None) => *self = iter.into_iter().collect::<Vec<_>>().into(), - } - } - - fn extend_one(&mut self, item: T) { - self.push(item) - } - - fn extend_reserve(&mut self, additional: usize) { - match *self { - ThinVec(Some(ref mut vec)) => vec.reserve(additional), - ThinVec(None) => *self = Vec::with_capacity(additional).into(), - } - } -} - -impl<T: HashStable<CTX>, CTX> HashStable<CTX> for ThinVec<T> { - fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher) { - (**self).hash_stable(hcx, hasher) - } -} - -impl<T> Default for ThinVec<T> { - fn default() -> Self { - Self(None) - } -} - -#[cfg(test)] -mod tests; diff --git a/compiler/rustc_data_structures/src/thin_vec/tests.rs b/compiler/rustc_data_structures/src/thin_vec/tests.rs deleted file mode 100644 index 0221b9912bb..00000000000 --- a/compiler/rustc_data_structures/src/thin_vec/tests.rs +++ /dev/null @@ -1,42 +0,0 @@ -use super::*; - -impl<T> ThinVec<T> { - fn into_vec(self) -> Vec<T> { - self.into() - } -} - -#[test] -fn test_from_iterator() { - assert_eq!(std::iter::empty().collect::<ThinVec<String>>().into_vec(), Vec::<String>::new()); - assert_eq!(std::iter::once(42).collect::<ThinVec<_>>().into_vec(), vec![42]); - assert_eq!([1, 2].into_iter().collect::<ThinVec<_>>().into_vec(), vec![1, 2]); - assert_eq!([1, 2, 3].into_iter().collect::<ThinVec<_>>().into_vec(), vec![1, 2, 3]); -} - -#[test] -fn test_into_iterator_owned() { - assert_eq!(ThinVec::new().into_iter().collect::<Vec<String>>(), Vec::<String>::new()); - assert_eq!(ThinVec::from(vec![1]).into_iter().collect::<Vec<_>>(), vec![1]); - assert_eq!(ThinVec::from(vec![1, 2]).into_iter().collect::<Vec<_>>(), vec![1, 2]); - assert_eq!(ThinVec::from(vec![1, 2, 3]).into_iter().collect::<Vec<_>>(), vec![1, 2, 3]); -} - -#[test] -fn test_into_iterator_ref() { - assert_eq!(ThinVec::new().iter().collect::<Vec<&String>>(), Vec::<&String>::new()); - assert_eq!(ThinVec::from(vec![1]).iter().collect::<Vec<_>>(), vec![&1]); - assert_eq!(ThinVec::from(vec![1, 2]).iter().collect::<Vec<_>>(), vec![&1, &2]); - assert_eq!(ThinVec::from(vec![1, 2, 3]).iter().collect::<Vec<_>>(), vec![&1, &2, &3]); -} - -#[test] -fn test_into_iterator_ref_mut() { - assert_eq!(ThinVec::new().iter_mut().collect::<Vec<&mut String>>(), Vec::<&mut String>::new()); - assert_eq!(ThinVec::from(vec![1]).iter_mut().collect::<Vec<_>>(), vec![&mut 1]); - assert_eq!(ThinVec::from(vec![1, 2]).iter_mut().collect::<Vec<_>>(), vec![&mut 1, &mut 2]); - assert_eq!( - ThinVec::from(vec![1, 2, 3]).iter_mut().collect::<Vec<_>>(), - vec![&mut 1, &mut 2, &mut 3], - ); -} |