diff options
Diffstat (limited to '')
10 files changed, 470 insertions, 66 deletions
diff --git a/compiler/rustc_data_structures/src/flock/linux.rs b/compiler/rustc_data_structures/src/flock/linux.rs index bb3ecfbc3..9ed26e490 100644 --- a/compiler/rustc_data_structures/src/flock/linux.rs +++ b/compiler/rustc_data_structures/src/flock/linux.rs @@ -14,12 +14,7 @@ pub struct Lock { impl Lock { pub fn new(p: &Path, wait: bool, create: bool, exclusive: bool) -> io::Result<Lock> { - let file = OpenOptions::new() - .read(true) - .write(true) - .create(create) - .mode(libc::S_IRWXU as u32) - .open(p)?; + let file = OpenOptions::new().read(true).write(true).create(create).mode(0o600).open(p)?; let mut operation = if exclusive { libc::LOCK_EX } else { libc::LOCK_SH }; if !wait { diff --git a/compiler/rustc_data_structures/src/graph/vec_graph/mod.rs b/compiler/rustc_data_structures/src/graph/vec_graph/mod.rs index 3d91bcade..e8efbd09a 100644 --- a/compiler/rustc_data_structures/src/graph/vec_graph/mod.rs +++ b/compiler/rustc_data_structures/src/graph/vec_graph/mod.rs @@ -29,8 +29,8 @@ impl<N: Idx + Ord> VecGraph<N> { // Store the *target* of each edge into `edge_targets`. let edge_targets: Vec<N> = edge_pairs.iter().map(|&(_, target)| target).collect(); - // Create the *edge starts* array. We are iterating over over - // the (sorted) edge pairs. We maintain the invariant that the + // Create the *edge starts* array. We are iterating over the + // (sorted) edge pairs. We maintain the invariant that the // length of the `node_starts` array is enough to store the // current source node -- so when we see that the source node // for an edge is greater than the current length, we grow the diff --git a/compiler/rustc_data_structures/src/lib.rs b/compiler/rustc_data_structures/src/lib.rs index 56f7823ef..3a2000233 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)] -#![cfg_attr(bootstrap, feature(let_else))] #![feature(hash_raw_entry)] #![feature(hasher_prefixfree_extras)] #![feature(maybe_uninit_uninit_array)] @@ -23,6 +22,7 @@ #![feature(new_uninit)] #![feature(once_cell)] #![feature(rustc_attrs)] +#![feature(negative_impls)] #![feature(test)] #![feature(thread_id_value)] #![feature(vec_into_raw_parts)] @@ -87,6 +87,7 @@ pub mod steal; pub mod tagged_ptr; pub mod temp_dir; pub mod unhash; +pub mod unord; pub use ena::undo_log; pub use ena::unify; diff --git a/compiler/rustc_data_structures/src/obligation_forest/mod.rs b/compiler/rustc_data_structures/src/obligation_forest/mod.rs index e351b650a..10e673cd9 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,7 +115,11 @@ 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>; } @@ -402,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 { @@ -473,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)); } @@ -558,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>, { @@ -568,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); } } @@ -576,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]; @@ -586,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 e2991aae1..bc252f772 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/profiling.rs b/compiler/rustc_data_structures/src/profiling.rs index d8b26f984..ba1960805 100644 --- a/compiler/rustc_data_structures/src/profiling.rs +++ b/compiler/rustc_data_structures/src/profiling.rs @@ -158,30 +158,21 @@ pub struct SelfProfilerRef { // actually enabled. event_filter_mask: EventFilter, - // Print verbose generic activities to stdout + // Print verbose generic activities to stderr? print_verbose_generic_activities: bool, - - // Print extra verbose generic activities to stdout - print_extra_verbose_generic_activities: bool, } impl SelfProfilerRef { pub fn new( profiler: Option<Arc<SelfProfiler>>, print_verbose_generic_activities: bool, - print_extra_verbose_generic_activities: bool, ) -> SelfProfilerRef { // If there is no SelfProfiler then the filter mask is set to NONE, // ensuring that nothing ever tries to actually access it. let event_filter_mask = profiler.as_ref().map_or(EventFilter::empty(), |p| p.event_filter_mask); - SelfProfilerRef { - profiler, - event_filter_mask, - print_verbose_generic_activities, - print_extra_verbose_generic_activities, - } + SelfProfilerRef { profiler, event_filter_mask, print_verbose_generic_activities } } /// This shim makes sure that calls only get executed if the filter mask @@ -214,7 +205,7 @@ impl SelfProfilerRef { /// Start profiling a verbose generic activity. Profiling continues until the /// VerboseTimingGuard returned from this call is dropped. In addition to recording /// a measureme event, "verbose" generic activities also print a timing entry to - /// stdout if the compiler is invoked with -Ztime or -Ztime-passes. + /// stderr if the compiler is invoked with -Ztime-passes. pub fn verbose_generic_activity<'a>( &'a self, event_label: &'static str, @@ -225,11 +216,8 @@ impl SelfProfilerRef { VerboseTimingGuard::start(message, self.generic_activity(event_label)) } - /// Start profiling an extra verbose generic activity. Profiling continues until the - /// VerboseTimingGuard returned from this call is dropped. In addition to recording - /// a measureme event, "extra verbose" generic activities also print a timing entry to - /// stdout if the compiler is invoked with -Ztime-passes. - pub fn extra_verbose_generic_activity<'a, A>( + /// Like `verbose_generic_activity`, but with an extra arg. + pub fn verbose_generic_activity_with_arg<'a, A>( &'a self, event_label: &'static str, event_arg: A, @@ -237,7 +225,7 @@ impl SelfProfilerRef { where A: Borrow<str> + Into<String>, { - let message = if self.print_extra_verbose_generic_activities { + let message = if self.print_verbose_generic_activities { Some(format!("{}({})", event_label, event_arg.borrow())) } else { None @@ -745,27 +733,9 @@ impl Drop for VerboseTimingGuard<'_> { if let Some((start_time, start_rss, ref message)) = self.start_and_message { let end_rss = get_resident_set_size(); let dur = start_time.elapsed(); - - if should_print_passes(dur, start_rss, end_rss) { - print_time_passes_entry(&message, dur, start_rss, end_rss); - } - } - } -} - -fn should_print_passes(dur: Duration, start_rss: Option<usize>, end_rss: Option<usize>) -> bool { - if dur.as_millis() > 5 { - return true; - } - - if let (Some(start_rss), Some(end_rss)) = (start_rss, end_rss) { - let change_rss = end_rss.abs_diff(start_rss); - if change_rss > 0 { - return true; + print_time_passes_entry(&message, dur, start_rss, end_rss); } } - - false } pub fn print_time_passes_entry( @@ -774,6 +744,26 @@ pub fn print_time_passes_entry( start_rss: Option<usize>, end_rss: Option<usize>, ) { + // Print the pass if its duration is greater than 5 ms, or it changed the + // measured RSS. + let is_notable = || { + if dur.as_millis() > 5 { + return true; + } + + if let (Some(start_rss), Some(end_rss)) = (start_rss, end_rss) { + let change_rss = end_rss.abs_diff(start_rss); + if change_rss > 0 { + return true; + } + } + + false + }; + if !is_notable() { + return; + } + let rss_to_mb = |rss| (rss as f64 / 1_000_000.0).round() as usize; let rss_change_to_mb = |rss| (rss as f64 / 1_000_000.0).round() as i128; diff --git a/compiler/rustc_data_structures/src/sorted_map.rs b/compiler/rustc_data_structures/src/sorted_map.rs index 937cb6715..fe257e102 100644 --- a/compiler/rustc_data_structures/src/sorted_map.rs +++ b/compiler/rustc_data_structures/src/sorted_map.rs @@ -96,6 +96,23 @@ impl<K: Ord, V> SortedMap<K, V> { } } + /// Gets a mutable reference to the value in the entry, or insert a new one. + #[inline] + pub fn get_mut_or_insert_default(&mut self, key: K) -> &mut V + where + K: Eq, + V: Default, + { + let index = match self.lookup_index_for(&key) { + Ok(index) => index, + Err(index) => { + self.data.insert(index, (key, V::default())); + index + } + }; + unsafe { &mut self.data.get_unchecked_mut(index).1 } + } + #[inline] pub fn clear(&mut self) { self.data.clear(); diff --git a/compiler/rustc_data_structures/src/sso/set.rs b/compiler/rustc_data_structures/src/sso/set.rs index 4fda3adb7..406f0270d 100644 --- a/compiler/rustc_data_structures/src/sso/set.rs +++ b/compiler/rustc_data_structures/src/sso/set.rs @@ -27,7 +27,7 @@ pub struct SsoHashSet<T> { map: SsoHashMap<T, ()>, } -/// Adapter function used ot return +/// Adapter function used to return /// result if SsoHashMap functions into /// result SsoHashSet should return. #[inline(always)] diff --git a/compiler/rustc_data_structures/src/transitive_relation.rs b/compiler/rustc_data_structures/src/transitive_relation.rs index f016c391f..cf6162038 100644 --- a/compiler/rustc_data_structures/src/transitive_relation.rs +++ b/compiler/rustc_data_structures/src/transitive_relation.rs @@ -1,5 +1,5 @@ use crate::frozen::Frozen; -use crate::fx::FxIndexSet; +use crate::fx::{FxHashSet, FxIndexSet}; use rustc_index::bit_set::BitMatrix; use std::fmt::Debug; use std::hash::Hash; @@ -16,7 +16,7 @@ pub struct TransitiveRelationBuilder<T> { // List of base edges in the graph. Require to compute transitive // closure. - edges: Vec<Edge>, + edges: FxHashSet<Edge>, } #[derive(Debug)] @@ -52,10 +52,10 @@ impl<T: Eq + Hash> Default for TransitiveRelationBuilder<T> { } } -#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Debug)] +#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Debug, Hash)] struct Index(usize); -#[derive(Clone, PartialEq, Eq, Debug)] +#[derive(Clone, PartialEq, Eq, Debug, Hash)] struct Edge { source: Index, target: Index, @@ -99,9 +99,7 @@ impl<T: Eq + Hash + Copy> TransitiveRelationBuilder<T> { let a = self.add_index(a); let b = self.add_index(b); let edge = Edge { source: a, target: b }; - if !self.edges.contains(&edge) { - self.edges.push(edge); - } + self.edges.insert(edge); } /// Compute the transitive closure derived from the edges, and converted to diff --git a/compiler/rustc_data_structures/src/unord.rs b/compiler/rustc_data_structures/src/unord.rs new file mode 100644 index 000000000..c015f1232 --- /dev/null +++ b/compiler/rustc_data_structures/src/unord.rs @@ -0,0 +1,382 @@ +//! This module contains collection types that don't expose their internal +//! ordering. This is a useful property for deterministic computations, such +//! as required by the query system. + +use rustc_hash::{FxHashMap, FxHashSet}; +use smallvec::SmallVec; +use std::{ + borrow::Borrow, + hash::Hash, + iter::{Product, Sum}, +}; + +use crate::{ + fingerprint::Fingerprint, + stable_hasher::{HashStable, StableHasher, ToStableHashKey}, +}; + +/// `UnordItems` is the order-less version of `Iterator`. It only contains methods +/// that don't (easily) expose an ordering of the underlying items. +/// +/// Most methods take an `Fn` where the `Iterator`-version takes an `FnMut`. This +/// is to reduce the risk of accidentally leaking the internal order via the closure +/// environment. Otherwise one could easily do something like +/// +/// ```rust,ignore (pseudo code) +/// let mut ordered = vec![]; +/// unordered_items.all(|x| ordered.push(x)); +/// ``` +/// +/// It's still possible to do the same thing with an `Fn` by using interior mutability, +/// but the chance of doing it accidentally is reduced. +pub struct UnordItems<T, I: Iterator<Item = T>>(I); + +impl<T, I: Iterator<Item = T>> UnordItems<T, I> { + #[inline] + pub fn map<U, F: Fn(T) -> U>(self, f: F) -> UnordItems<U, impl Iterator<Item = U>> { + UnordItems(self.0.map(f)) + } + + #[inline] + pub fn all<U, F: Fn(T) -> bool>(mut self, f: F) -> bool { + self.0.all(f) + } + + #[inline] + pub fn any<U, F: Fn(T) -> bool>(mut self, f: F) -> bool { + self.0.any(f) + } + + #[inline] + pub fn filter<U, F: Fn(&T) -> bool>(self, f: F) -> UnordItems<T, impl Iterator<Item = T>> { + UnordItems(self.0.filter(f)) + } + + #[inline] + pub fn filter_map<U, F: Fn(T) -> Option<U>>( + self, + f: F, + ) -> UnordItems<U, impl Iterator<Item = U>> { + UnordItems(self.0.filter_map(f)) + } + + #[inline] + pub fn max(self) -> Option<T> + where + T: Ord, + { + self.0.max() + } + + #[inline] + pub fn min(self) -> Option<T> + where + T: Ord, + { + self.0.min() + } + + #[inline] + pub fn sum<S>(self) -> S + where + S: Sum<T>, + { + self.0.sum() + } + + #[inline] + pub fn product<S>(self) -> S + where + S: Product<T>, + { + self.0.product() + } + + #[inline] + pub fn count(self) -> usize { + self.0.count() + } +} + +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>> { + UnordItems(self.0.cloned()) + } +} + +impl<'a, T: Copy + 'a, I: Iterator<Item = &'a T>> UnordItems<&'a T, I> { + #[inline] + pub fn copied(self) -> UnordItems<T, impl Iterator<Item = T>> { + UnordItems(self.0.copied()) + } +} + +impl<T: Ord, I: Iterator<Item = T>> UnordItems<T, I> { + pub fn into_sorted<HCX>(self, hcx: &HCX) -> Vec<T> + where + T: ToStableHashKey<HCX>, + { + let mut items: Vec<T> = self.0.collect(); + items.sort_by_cached_key(|x| x.to_stable_hash_key(hcx)); + items + } + + pub fn into_sorted_small_vec<HCX, const LEN: usize>(self, hcx: &HCX) -> SmallVec<[T; LEN]> + where + T: ToStableHashKey<HCX>, + { + let mut items: SmallVec<[T; LEN]> = self.0.collect(); + items.sort_by_cached_key(|x| x.to_stable_hash_key(hcx)); + items + } +} + +/// This is a set collection type that tries very hard to not expose +/// any internal iteration. This is a useful property when trying to +/// uphold the determinism invariants imposed by the query system. +/// +/// This collection type is a good choice for set-like collections the +/// keys of which don't have a semantic ordering. +/// +/// See [MCP 533](https://github.com/rust-lang/compiler-team/issues/533) +/// for more information. +#[derive(Debug, Eq, PartialEq, Clone, Encodable, Decodable)] +pub struct UnordSet<V: Eq + Hash> { + inner: FxHashSet<V>, +} + +impl<V: Eq + Hash> Default for UnordSet<V> { + fn default() -> Self { + Self { inner: FxHashSet::default() } + } +} + +impl<V: Eq + Hash> UnordSet<V> { + #[inline] + pub fn new() -> Self { + Self { inner: Default::default() } + } + + #[inline] + pub fn len(&self) -> usize { + self.inner.len() + } + + #[inline] + pub fn insert(&mut self, v: V) -> bool { + self.inner.insert(v) + } + + #[inline] + pub fn contains<Q: ?Sized>(&self, v: &Q) -> bool + where + V: Borrow<Q>, + Q: Hash + Eq, + { + self.inner.contains(v) + } + + #[inline] + pub fn items<'a>(&'a self) -> UnordItems<&'a V, impl Iterator<Item = &'a V>> { + UnordItems(self.inner.iter()) + } + + #[inline] + pub fn into_items(self) -> UnordItems<V, impl Iterator<Item = V>> { + UnordItems(self.inner.into_iter()) + } + + // 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>) { + self.inner.extend(items.0) + } +} + +impl<V: Hash + Eq> Extend<V> for UnordSet<V> { + fn extend<T: IntoIterator<Item = V>>(&mut self, iter: T) { + self.inner.extend(iter) + } +} + +impl<HCX, V: Hash + Eq + HashStable<HCX>> HashStable<HCX> for UnordSet<V> { + #[inline] + fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) { + hash_iter_order_independent(self.inner.iter(), hcx, hasher); + } +} + +/// This is a map collection type that tries very hard to not expose +/// any internal iteration. This is a useful property when trying to +/// uphold the determinism invariants imposed by the query system. +/// +/// This collection type is a good choice for map-like collections the +/// keys of which don't have a semantic ordering. +/// +/// See [MCP 533](https://github.com/rust-lang/compiler-team/issues/533) +/// for more information. +#[derive(Debug, Eq, PartialEq, Clone, Encodable, Decodable)] +pub struct UnordMap<K: Eq + Hash, V> { + inner: FxHashMap<K, V>, +} + +impl<K: Eq + Hash, V> Default for UnordMap<K, V> { + fn default() -> Self { + Self { inner: FxHashMap::default() } + } +} + +impl<K: Hash + Eq, V> Extend<(K, V)> for UnordMap<K, V> { + fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) { + self.inner.extend(iter) + } +} + +impl<K: Eq + Hash, V> UnordMap<K, V> { + #[inline] + pub fn len(&self) -> usize { + self.inner.len() + } + + #[inline] + pub fn insert(&mut self, k: K, v: V) -> Option<V> { + self.inner.insert(k, v) + } + + #[inline] + pub fn contains_key<Q: ?Sized>(&self, k: &Q) -> bool + where + K: Borrow<Q>, + Q: Hash + Eq, + { + self.inner.contains_key(k) + } + + #[inline] + pub fn items<'a>(&'a self) -> UnordItems<(&'a K, &'a V), impl Iterator<Item = (&'a K, &'a V)>> { + UnordItems(self.inner.iter()) + } + + #[inline] + pub fn into_items(self) -> UnordItems<(K, V), impl Iterator<Item = (K, V)>> { + UnordItems(self.inner.into_iter()) + } + + // We can safely extend this UnordMap from a set of unordered values because that + // won't expose the internal ordering anywhere. + #[inline] + pub fn extend<I: Iterator<Item = (K, V)>>(&mut self, items: UnordItems<(K, V), I>) { + self.inner.extend(items.0) + } +} + +impl<HCX, K: Hash + Eq + HashStable<HCX>, V: HashStable<HCX>> HashStable<HCX> for UnordMap<K, V> { + #[inline] + fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) { + hash_iter_order_independent(self.inner.iter(), hcx, hasher); + } +} + +/// This is a collection type that tries very hard to not expose +/// any internal iteration. This is a useful property when trying to +/// uphold the determinism invariants imposed by the query system. +/// +/// This collection type is a good choice for collections the +/// keys of which don't have a semantic ordering and don't implement +/// `Hash` or `Eq`. +/// +/// See [MCP 533](https://github.com/rust-lang/compiler-team/issues/533) +/// for more information. +#[derive(Default, Debug, Eq, PartialEq, Clone, Encodable, Decodable)] +pub struct UnordBag<V> { + inner: Vec<V>, +} + +impl<V> UnordBag<V> { + #[inline] + pub fn new() -> Self { + Self { inner: Default::default() } + } + + #[inline] + pub fn len(&self) -> usize { + self.inner.len() + } + + #[inline] + pub fn push(&mut self, v: V) { + self.inner.push(v); + } + + #[inline] + pub fn items<'a>(&'a self) -> UnordItems<&'a V, impl Iterator<Item = &'a V>> { + UnordItems(self.inner.iter()) + } + + #[inline] + pub fn into_items(self) -> UnordItems<V, impl Iterator<Item = V>> { + UnordItems(self.inner.into_iter()) + } + + // 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>) { + self.inner.extend(items.0) + } +} + +impl<T> Extend<T> for UnordBag<T> { + fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) { + self.inner.extend(iter) + } +} + +impl<HCX, V: Hash + Eq + HashStable<HCX>> HashStable<HCX> for UnordBag<V> { + #[inline] + fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) { + hash_iter_order_independent(self.inner.iter(), hcx, hasher); + } +} + +fn hash_iter_order_independent< + HCX, + T: HashStable<HCX>, + I: Iterator<Item = T> + ExactSizeIterator, +>( + mut it: I, + hcx: &mut HCX, + hasher: &mut StableHasher, +) { + let len = it.len(); + len.hash_stable(hcx, hasher); + + match len { + 0 => { + // We're done + } + 1 => { + // No need to instantiate a hasher + it.next().unwrap().hash_stable(hcx, hasher); + } + _ => { + let mut accumulator = Fingerprint::ZERO; + for item in it { + let mut item_hasher = StableHasher::new(); + item.hash_stable(hcx, &mut item_hasher); + let item_fingerprint: Fingerprint = item_hasher.finish(); + accumulator = accumulator.combine_commutative(item_fingerprint); + } + accumulator.hash_stable(hcx, hasher); + } + } +} + +// Do not implement IntoIterator for the collections in this module. +// They only exist to hide iteration order in the first place. +impl<T> !IntoIterator for UnordBag<T> {} +impl<V> !IntoIterator for UnordSet<V> {} +impl<K, V> !IntoIterator for UnordMap<K, V> {} +impl<T, I> !IntoIterator for UnordItems<T, I> {} |