summaryrefslogtreecommitdiffstats
path: root/compiler/rustc_data_structures
diff options
context:
space:
mode:
authorDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-17 12:06:31 +0000
committerDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-17 12:06:31 +0000
commit2ff14448863ac1a1dd9533461708e29aae170c2d (patch)
tree85b9fea2bbfe3f06473cfa381eed11f273b57c5c /compiler/rustc_data_structures
parentAdding debian version 1.64.0+dfsg1-1. (diff)
downloadrustc-2ff14448863ac1a1dd9533461708e29aae170c2d.tar.xz
rustc-2ff14448863ac1a1dd9533461708e29aae170c2d.zip
Adding debian version 1.65.0+dfsg1-2.debian/1.65.0+dfsg1-2
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'compiler/rustc_data_structures')
-rw-r--r--compiler/rustc_data_structures/Cargo.toml23
-rw-r--r--compiler/rustc_data_structures/src/fingerprint.rs4
-rw-r--r--compiler/rustc_data_structures/src/fx.rs15
-rw-r--r--compiler/rustc_data_structures/src/lib.rs5
-rw-r--r--compiler/rustc_data_structures/src/map_in_place.rs127
-rw-r--r--compiler/rustc_data_structures/src/obligation_forest/mod.rs4
-rw-r--r--compiler/rustc_data_structures/src/sorted_map.rs20
-rw-r--r--compiler/rustc_data_structures/src/sync.rs4
-rw-r--r--compiler/rustc_data_structures/src/thin_vec.rs135
-rw-r--r--compiler/rustc_data_structures/src/thin_vec/tests.rs42
-rw-r--r--compiler/rustc_data_structures/src/transitive_relation.rs121
-rw-r--r--compiler/rustc_data_structures/src/transitive_relation/tests.rs48
12 files changed, 194 insertions, 354 deletions
diff --git a/compiler/rustc_data_structures/Cargo.toml b/compiler/rustc_data_structures/Cargo.toml
index 5c641f54f..2d8658db5 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 5ff2d18dd..a39178016 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 bbeb193db..0d0c51b68 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 265f45b72..56f7823ef 100644
--- a/compiler/rustc_data_structures/src/lib.rs
+++ b/compiler/rustc_data_structures/src/lib.rs
@@ -13,7 +13,7 @@
#![feature(cell_leak)]
#![feature(control_flow_enum)]
#![feature(extend_one)]
-#![feature(let_else)]
+#![cfg_attr(bootstrap, feature(let_else))]
#![feature(hash_raw_entry)]
#![feature(hasher_prefixfree_extras)]
#![feature(maybe_uninit_uninit_array)]
@@ -28,6 +28,8 @@
#![feature(vec_into_raw_parts)]
#![allow(rustc::default_hash_types)]
#![allow(rustc::potential_query_instability)]
+#![deny(rustc::untranslatable_diagnostic)]
+#![deny(rustc::diagnostic_outside_of_impl)]
#[macro_use]
extern crate tracing;
@@ -73,7 +75,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 874de03d3..a0d4b7ade 100644
--- a/compiler/rustc_data_structures/src/map_in_place.rs
+++ b/compiler/rustc_data_structures/src/map_in_place.rs
@@ -1,5 +1,6 @@
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)
@@ -15,94 +16,64 @@ pub trait MapInPlace<T>: Sized {
I: IntoIterator<Item = T>;
}
-impl<T> MapInPlace<T> for Vec<T> {
- fn flat_map_in_place<F, I>(&mut self, mut f: F)
- where
- F: FnMut(T) -> I,
- I: IntoIterator<Item = T>,
- {
- let mut read_i = 0;
- let mut write_i = 0;
- unsafe {
- let mut old_len = self.len();
- self.set_len(0); // make sure we just leak elements in case of panic
+// The implementation of this method is syntactically identical for all the
+// different vector types.
+macro_rules! flat_map_in_place {
+ () => {
+ fn flat_map_in_place<F, I>(&mut self, mut f: F)
+ where
+ F: FnMut(T) -> I,
+ I: IntoIterator<Item = T>,
+ {
+ let mut read_i = 0;
+ let mut write_i = 0;
+ unsafe {
+ let mut old_len = self.len();
+ self.set_len(0); // make sure we just leak elements in case of panic
- while read_i < old_len {
- // move the read_i'th item out of the vector and map it
- // to an iterator
- let e = ptr::read(self.as_ptr().add(read_i));
- let iter = f(e).into_iter();
- read_i += 1;
+ while read_i < old_len {
+ // move the read_i'th item out of the vector and map it
+ // to an iterator
+ let e = ptr::read(self.as_ptr().add(read_i));
+ let iter = f(e).into_iter();
+ read_i += 1;
- for e in iter {
- if write_i < read_i {
- ptr::write(self.as_mut_ptr().add(write_i), e);
- write_i += 1;
- } else {
- // If this is reached we ran out of space
- // in the middle of the vector.
- // However, the vector is in a valid state here,
- // so we just do a somewhat inefficient insert.
- self.set_len(old_len);
- self.insert(write_i, e);
+ for e in iter {
+ if write_i < read_i {
+ ptr::write(self.as_mut_ptr().add(write_i), e);
+ write_i += 1;
+ } else {
+ // If this is reached we ran out of space
+ // in the middle of the vector.
+ // However, the vector is in a valid state here,
+ // so we just do a somewhat inefficient insert.
+ self.set_len(old_len);
+ self.insert(write_i, e);
- old_len = self.len();
- self.set_len(0);
+ old_len = self.len();
+ self.set_len(0);
- read_i += 1;
- write_i += 1;
+ read_i += 1;
+ write_i += 1;
+ }
}
}
- }
- // write_i tracks the number of actually written new items.
- self.set_len(write_i);
+ // write_i tracks the number of actually written new items.
+ self.set_len(write_i);
+ }
}
- }
+ };
}
-impl<T, A: Array<Item = T>> MapInPlace<T> for SmallVec<A> {
- fn flat_map_in_place<F, I>(&mut self, mut f: F)
- where
- F: FnMut(T) -> I,
- I: IntoIterator<Item = T>,
- {
- let mut read_i = 0;
- let mut write_i = 0;
- unsafe {
- let mut old_len = self.len();
- self.set_len(0); // make sure we just leak elements in case of panic
-
- while read_i < old_len {
- // move the read_i'th item out of the vector and map it
- // to an iterator
- let e = ptr::read(self.as_ptr().add(read_i));
- let iter = f(e).into_iter();
- read_i += 1;
-
- for e in iter {
- if write_i < read_i {
- ptr::write(self.as_mut_ptr().add(write_i), e);
- write_i += 1;
- } else {
- // If this is reached we ran out of space
- // in the middle of the vector.
- // However, the vector is in a valid state here,
- // so we just do a somewhat inefficient insert.
- self.set_len(old_len);
- self.insert(write_i, e);
-
- old_len = self.len();
- self.set_len(0);
+impl<T> MapInPlace<T> for Vec<T> {
+ flat_map_in_place!();
+}
- read_i += 1;
- write_i += 1;
- }
- }
- }
+impl<T, A: Array<Item = T>> MapInPlace<T> for SmallVec<A> {
+ flat_map_in_place!();
+}
- // write_i tracks the number of actually written new items.
- self.set_len(write_i);
- }
- }
+impl<T> MapInPlace<T> for ThinVec<T> {
+ flat_map_in_place!();
}
diff --git a/compiler/rustc_data_structures/src/obligation_forest/mod.rs b/compiler/rustc_data_structures/src/obligation_forest/mod.rs
index 07a96dd7d..e351b650a 100644
--- a/compiler/rustc_data_structures/src/obligation_forest/mod.rs
+++ b/compiler/rustc_data_structures/src/obligation_forest/mod.rs
@@ -117,6 +117,10 @@ pub trait ObligationProcessor {
}
/// 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,
diff --git a/compiler/rustc_data_structures/src/sorted_map.rs b/compiler/rustc_data_structures/src/sorted_map.rs
index 9efea1228..937cb6715 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 52952a793..9c0fb8265 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> {
@@ -56,9 +56,7 @@ cfg_if! {
pub fn new(v: T) -> Self {
Atomic(Cell::new(v))
}
- }
- impl<T: Copy> Atomic<T> {
#[inline]
pub fn into_inner(self) -> T {
self.0.into_inner()
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 716259142..000000000
--- a/compiler/rustc_data_structures/src/thin_vec.rs
+++ /dev/null
@@ -1,135 +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(),
- }
- }
-}
-
-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 0221b9912..000000000
--- 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],
- );
-}
diff --git a/compiler/rustc_data_structures/src/transitive_relation.rs b/compiler/rustc_data_structures/src/transitive_relation.rs
index 0ff64969b..f016c391f 100644
--- a/compiler/rustc_data_structures/src/transitive_relation.rs
+++ b/compiler/rustc_data_structures/src/transitive_relation.rs
@@ -1,45 +1,57 @@
+use crate::frozen::Frozen;
use crate::fx::FxIndexSet;
-use crate::sync::Lock;
use rustc_index::bit_set::BitMatrix;
use std::fmt::Debug;
use std::hash::Hash;
use std::mem;
+use std::ops::Deref;
#[cfg(test)]
mod tests;
#[derive(Clone, Debug)]
-pub struct TransitiveRelation<T> {
+pub struct TransitiveRelationBuilder<T> {
// List of elements. This is used to map from a T to a usize.
elements: FxIndexSet<T>,
// List of base edges in the graph. Require to compute transitive
// closure.
edges: Vec<Edge>,
+}
+
+#[derive(Debug)]
+pub struct TransitiveRelation<T> {
+ // Frozen transitive relation elements and edges.
+ builder: Frozen<TransitiveRelationBuilder<T>>,
- // This is a cached transitive closure derived from the edges.
- // Currently, we build it lazily and just throw out any existing
- // copy whenever a new edge is added. (The Lock is to permit
- // the lazy computation.) This is kind of silly, except for the
- // fact its size is tied to `self.elements.len()`, so I wanted to
- // wait before building it up to avoid reallocating as new edges
- // are added with new elements. Perhaps better would be to ask the
- // user for a batch of edges to minimize this effect, but I
- // already wrote the code this way. :P -nmatsakis
- closure: Lock<Option<BitMatrix<usize, usize>>>,
+ // Cached transitive closure derived from the edges.
+ closure: Frozen<BitMatrix<usize, usize>>,
}
-// HACK(eddyb) manual impl avoids `Default` bound on `T`.
-impl<T: Eq + Hash> Default for TransitiveRelation<T> {
- fn default() -> Self {
+impl<T> Deref for TransitiveRelation<T> {
+ type Target = Frozen<TransitiveRelationBuilder<T>>;
+
+ fn deref(&self) -> &Self::Target {
+ &self.builder
+ }
+}
+
+impl<T: Clone> Clone for TransitiveRelation<T> {
+ fn clone(&self) -> Self {
TransitiveRelation {
- elements: Default::default(),
- edges: Default::default(),
- closure: Default::default(),
+ builder: Frozen::freeze(self.builder.deref().clone()),
+ closure: Frozen::freeze(self.closure.deref().clone()),
}
}
}
+// HACK(eddyb) manual impl avoids `Default` bound on `T`.
+impl<T: Eq + Hash> Default for TransitiveRelationBuilder<T> {
+ fn default() -> Self {
+ TransitiveRelationBuilder { elements: Default::default(), edges: Default::default() }
+ }
+}
+
#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Debug)]
struct Index(usize);
@@ -49,7 +61,7 @@ struct Edge {
target: Index,
}
-impl<T: Eq + Hash + Copy> TransitiveRelation<T> {
+impl<T: Eq + Hash + Copy> TransitiveRelationBuilder<T> {
pub fn is_empty(&self) -> bool {
self.edges.is_empty()
}
@@ -63,23 +75,19 @@ impl<T: Eq + Hash + Copy> TransitiveRelation<T> {
}
fn add_index(&mut self, a: T) -> Index {
- let (index, added) = self.elements.insert_full(a);
- if added {
- // if we changed the dimensions, clear the cache
- *self.closure.get_mut() = None;
- }
+ let (index, _added) = self.elements.insert_full(a);
Index(index)
}
/// Applies the (partial) function to each edge and returns a new
- /// relation. If `f` returns `None` for any end-point, returns
- /// `None`.
- pub fn maybe_map<F, U>(&self, mut f: F) -> Option<TransitiveRelation<U>>
+ /// relation builder. If `f` returns `None` for any end-point,
+ /// returns `None`.
+ pub fn maybe_map<F, U>(&self, mut f: F) -> Option<TransitiveRelationBuilder<U>>
where
F: FnMut(T) -> Option<U>,
U: Clone + Debug + Eq + Hash + Copy,
{
- let mut result = TransitiveRelation::default();
+ let mut result = TransitiveRelationBuilder::default();
for edge in &self.edges {
result.add(f(self.elements[edge.source.0])?, f(self.elements[edge.target.0])?);
}
@@ -93,10 +101,38 @@ impl<T: Eq + Hash + Copy> TransitiveRelation<T> {
let edge = Edge { source: a, target: b };
if !self.edges.contains(&edge) {
self.edges.push(edge);
+ }
+ }
+
+ /// Compute the transitive closure derived from the edges, and converted to
+ /// the final result. After this, all elements will be immutable to maintain
+ /// the correctness of the result.
+ pub fn freeze(self) -> TransitiveRelation<T> {
+ let mut matrix = BitMatrix::new(self.elements.len(), self.elements.len());
+ let mut changed = true;
+ while changed {
+ changed = false;
+ for edge in &self.edges {
+ // add an edge from S -> T
+ changed |= matrix.insert(edge.source.0, edge.target.0);
- // added an edge, clear the cache
- *self.closure.get_mut() = None;
+ // add all outgoing edges from T into S
+ changed |= matrix.union_rows(edge.target.0, edge.source.0);
+ }
}
+ TransitiveRelation { builder: Frozen::freeze(self), closure: Frozen::freeze(matrix) }
+ }
+}
+
+impl<T: Eq + Hash + Copy> TransitiveRelation<T> {
+ /// Applies the (partial) function to each edge and returns a new
+ /// relation including transitive closures.
+ pub fn maybe_map<F, U>(&self, f: F) -> Option<TransitiveRelation<U>>
+ where
+ F: FnMut(T) -> Option<U>,
+ U: Clone + Debug + Eq + Hash + Copy,
+ {
+ Some(self.builder.maybe_map(f)?.freeze())
}
/// Checks whether `a < target` (transitively)
@@ -322,30 +358,7 @@ impl<T: Eq + Hash + Copy> TransitiveRelation<T> {
where
OP: FnOnce(&BitMatrix<usize, usize>) -> R,
{
- let mut closure_cell = self.closure.borrow_mut();
- let mut closure = closure_cell.take();
- if closure.is_none() {
- closure = Some(self.compute_closure());
- }
- let result = op(closure.as_ref().unwrap());
- *closure_cell = closure;
- result
- }
-
- fn compute_closure(&self) -> BitMatrix<usize, usize> {
- let mut matrix = BitMatrix::new(self.elements.len(), self.elements.len());
- let mut changed = true;
- while changed {
- changed = false;
- for edge in &self.edges {
- // add an edge from S -> T
- changed |= matrix.insert(edge.source.0, edge.target.0);
-
- // add all outgoing edges from T into S
- changed |= matrix.union_rows(edge.target.0, edge.source.0);
- }
- }
- matrix
+ op(&self.closure)
}
/// Lists all the base edges in the graph: the initial _non-transitive_ set of element
diff --git a/compiler/rustc_data_structures/src/transitive_relation/tests.rs b/compiler/rustc_data_structures/src/transitive_relation/tests.rs
index e1f4c7ee0..e756c546e 100644
--- a/compiler/rustc_data_structures/src/transitive_relation/tests.rs
+++ b/compiler/rustc_data_structures/src/transitive_relation/tests.rs
@@ -10,9 +10,10 @@ impl<T: Eq + Hash + Copy> TransitiveRelation<T> {
#[test]
fn test_one_step() {
- let mut relation = TransitiveRelation::default();
+ let mut relation = TransitiveRelationBuilder::default();
relation.add("a", "b");
relation.add("a", "c");
+ let relation = relation.freeze();
assert!(relation.contains("a", "c"));
assert!(relation.contains("a", "b"));
assert!(!relation.contains("b", "a"));
@@ -21,7 +22,7 @@ fn test_one_step() {
#[test]
fn test_many_steps() {
- let mut relation = TransitiveRelation::default();
+ let mut relation = TransitiveRelationBuilder::default();
relation.add("a", "b");
relation.add("a", "c");
relation.add("a", "f");
@@ -31,6 +32,7 @@ fn test_many_steps() {
relation.add("b", "e");
relation.add("e", "g");
+ let relation = relation.freeze();
assert!(relation.contains("a", "b"));
assert!(relation.contains("a", "c"));
@@ -51,9 +53,10 @@ fn mubs_triangle() {
// ^
// |
// b
- let mut relation = TransitiveRelation::default();
+ let mut relation = TransitiveRelationBuilder::default();
relation.add("a", "tcx");
relation.add("b", "tcx");
+ let relation = relation.freeze();
assert_eq!(relation.minimal_upper_bounds("a", "b"), vec!["tcx"]);
assert_eq!(relation.parents("a"), vec!["tcx"]);
assert_eq!(relation.parents("b"), vec!["tcx"]);
@@ -72,7 +75,7 @@ fn mubs_best_choice1() {
// need the second pare down call to get the right result (after
// intersection, we have [1, 2], but 2 -> 1).
- let mut relation = TransitiveRelation::default();
+ let mut relation = TransitiveRelationBuilder::default();
relation.add("0", "1");
relation.add("0", "2");
@@ -80,6 +83,7 @@ fn mubs_best_choice1() {
relation.add("3", "1");
relation.add("3", "2");
+ let relation = relation.freeze();
assert_eq!(relation.minimal_upper_bounds("0", "3"), vec!["2"]);
assert_eq!(relation.parents("0"), vec!["2"]);
@@ -99,7 +103,7 @@ fn mubs_best_choice2() {
// Like the preceding test, but in this case intersection is [2,
// 1], and hence we rely on the first pare down call.
- let mut relation = TransitiveRelation::default();
+ let mut relation = TransitiveRelationBuilder::default();
relation.add("0", "1");
relation.add("0", "2");
@@ -107,6 +111,7 @@ fn mubs_best_choice2() {
relation.add("3", "1");
relation.add("3", "2");
+ let relation = relation.freeze();
assert_eq!(relation.minimal_upper_bounds("0", "3"), vec!["1"]);
assert_eq!(relation.parents("0"), vec!["1"]);
@@ -118,12 +123,13 @@ fn mubs_best_choice2() {
fn mubs_no_best_choice() {
// in this case, the intersection yields [1, 2], and the "pare
// down" calls find nothing to remove.
- let mut relation = TransitiveRelation::default();
+ let mut relation = TransitiveRelationBuilder::default();
relation.add("0", "1");
relation.add("0", "2");
relation.add("3", "1");
relation.add("3", "2");
+ let relation = relation.freeze();
assert_eq!(relation.minimal_upper_bounds("0", "3"), vec!["1", "2"]);
assert_eq!(relation.parents("0"), vec!["1", "2"]);
@@ -135,7 +141,7 @@ fn mubs_best_choice_scc() {
// in this case, 1 and 2 form a cycle; we pick arbitrarily (but
// consistently).
- let mut relation = TransitiveRelation::default();
+ let mut relation = TransitiveRelationBuilder::default();
relation.add("0", "1");
relation.add("0", "2");
@@ -144,6 +150,7 @@ fn mubs_best_choice_scc() {
relation.add("3", "1");
relation.add("3", "2");
+ let relation = relation.freeze();
assert_eq!(relation.minimal_upper_bounds("0", "3"), vec!["1"]);
assert_eq!(relation.parents("0"), vec!["1"]);
@@ -157,13 +164,14 @@ fn pdub_crisscross() {
// /\ |
// b -> b1 ---+
- let mut relation = TransitiveRelation::default();
+ let mut relation = TransitiveRelationBuilder::default();
relation.add("a", "a1");
relation.add("a", "b1");
relation.add("b", "a1");
relation.add("b", "b1");
relation.add("a1", "x");
relation.add("b1", "x");
+ let relation = relation.freeze();
assert_eq!(relation.minimal_upper_bounds("a", "b"), vec!["a1", "b1"]);
assert_eq!(relation.postdom_upper_bound("a", "b"), Some("x"));
@@ -179,7 +187,7 @@ fn pdub_crisscross_more() {
// /\ /\ |
// b -> b1 -> b2 ---------+
- let mut relation = TransitiveRelation::default();
+ let mut relation = TransitiveRelationBuilder::default();
relation.add("a", "a1");
relation.add("a", "b1");
relation.add("b", "a1");
@@ -194,6 +202,7 @@ fn pdub_crisscross_more() {
relation.add("a3", "x");
relation.add("b2", "x");
+ let relation = relation.freeze();
assert_eq!(relation.minimal_upper_bounds("a", "b"), vec!["a1", "b1"]);
assert_eq!(relation.minimal_upper_bounds("a1", "b1"), vec!["a2", "b2"]);
@@ -210,11 +219,12 @@ fn pdub_lub() {
// |
// b -> b1 ---+
- let mut relation = TransitiveRelation::default();
+ let mut relation = TransitiveRelationBuilder::default();
relation.add("a", "a1");
relation.add("b", "b1");
relation.add("a1", "x");
relation.add("b1", "x");
+ let relation = relation.freeze();
assert_eq!(relation.minimal_upper_bounds("a", "b"), vec!["x"]);
assert_eq!(relation.postdom_upper_bound("a", "b"), Some("x"));
@@ -233,10 +243,11 @@ fn mubs_intermediate_node_on_one_side_only() {
// b
// "digraph { a -> c -> d; b -> d; }",
- let mut relation = TransitiveRelation::default();
+ let mut relation = TransitiveRelationBuilder::default();
relation.add("a", "c");
relation.add("c", "d");
relation.add("b", "d");
+ let relation = relation.freeze();
assert_eq!(relation.minimal_upper_bounds("a", "b"), vec!["d"]);
}
@@ -252,12 +263,13 @@ fn mubs_scc_1() {
// b
// "digraph { a -> c -> d; d -> c; a -> d; b -> d; }",
- let mut relation = TransitiveRelation::default();
+ let mut relation = TransitiveRelationBuilder::default();
relation.add("a", "c");
relation.add("c", "d");
relation.add("d", "c");
relation.add("a", "d");
relation.add("b", "d");
+ let relation = relation.freeze();
assert_eq!(relation.minimal_upper_bounds("a", "b"), vec!["c"]);
}
@@ -272,12 +284,13 @@ fn mubs_scc_2() {
// +--- b
// "digraph { a -> c -> d; d -> c; b -> d; b -> c; }",
- let mut relation = TransitiveRelation::default();
+ let mut relation = TransitiveRelationBuilder::default();
relation.add("a", "c");
relation.add("c", "d");
relation.add("d", "c");
relation.add("b", "d");
relation.add("b", "c");
+ let relation = relation.freeze();
assert_eq!(relation.minimal_upper_bounds("a", "b"), vec!["c"]);
}
@@ -292,13 +305,14 @@ fn mubs_scc_3() {
// b ---+
// "digraph { a -> c -> d -> e -> c; b -> d; b -> e; }",
- let mut relation = TransitiveRelation::default();
+ let mut relation = TransitiveRelationBuilder::default();
relation.add("a", "c");
relation.add("c", "d");
relation.add("d", "e");
relation.add("e", "c");
relation.add("b", "d");
relation.add("b", "e");
+ let relation = relation.freeze();
assert_eq!(relation.minimal_upper_bounds("a", "b"), vec!["c"]);
}
@@ -314,13 +328,14 @@ fn mubs_scc_4() {
// b ---+
// "digraph { a -> c -> d -> e -> c; a -> d; b -> e; }"
- let mut relation = TransitiveRelation::default();
+ let mut relation = TransitiveRelationBuilder::default();
relation.add("a", "c");
relation.add("c", "d");
relation.add("d", "e");
relation.add("e", "c");
relation.add("a", "d");
relation.add("b", "e");
+ let relation = relation.freeze();
assert_eq!(relation.minimal_upper_bounds("a", "b"), vec!["c"]);
}
@@ -352,10 +367,11 @@ fn parent() {
(1, /*->*/ 3),
];
- let mut relation = TransitiveRelation::default();
+ let mut relation = TransitiveRelationBuilder::default();
for (a, b) in pairs {
relation.add(a, b);
}
+ let relation = relation.freeze();
let p = relation.postdom_parent(3);
assert_eq!(p, Some(0));