Auto merge of #78313 - lcnr:somebody-fold-me, r=nikomatsakis

TypeFoldable: take self by value

Implements https://github.com/rust-lang/compiler-team/issues/371 which is currently still in FCP.

r? `@nikomatsakis`

2 files changed, 84 insertions, 0 deletions

diff --git a/compiler/rustc_data_structures/src/functor.rs b/compiler/rustc_data_structures/src/functor.rs
new file mode 100644
index 00000000000..fe7a256d210
--- /dev/null
+++ b/compiler/rustc_data_structures/src/functor.rs
@@ -0,0 +1,82 @@
+use rustc_index::vec::{Idx, IndexVec};
+use std::mem;
+use std::ptr;
+
+pub trait IdFunctor {
+    type Inner;
+
+    fn map_id<F>(self, f: F) -> Self
+    where
+        F: FnMut(Self::Inner) -> Self::Inner;
+}
+
+impl<T> IdFunctor for Box<T> {
+    type Inner = T;
+
+    #[inline]
+    fn map_id<F>(self, mut f: F) -> Self
+    where
+        F: FnMut(Self::Inner) -> Self::Inner,
+    {
+        let raw = Box::into_raw(self);
+        unsafe {
+            // SAFETY: The raw pointer points to a valid value of type `T`.
+            let value = ptr::read(raw);
+            // SAFETY: Converts `Box<T>` to `Box<MaybeUninit<T>>` which is the
+            // inverse of `Box::assume_init()` and should be safe.
+            let mut raw: Box<mem::MaybeUninit<T>> = Box::from_raw(raw.cast());
+            // SAFETY: Write the mapped value back into the `Box`.
+            ptr::write(raw.as_mut_ptr(), f(value));
+            // SAFETY: We just initialized `raw`.
+            raw.assume_init()
+        }
+    }
+}
+
+impl<T> IdFunctor for Vec<T> {
+    type Inner = T;
+
+    #[inline]
+    fn map_id<F>(mut self, mut f: F) -> Self
+    where
+        F: FnMut(Self::Inner) -> Self::Inner,
+    {
+        // FIXME: We don't really care about panics here and leak
+        // far more than we should, but that should be fine for now.
+        let len = self.len();
+        unsafe {
+            self.set_len(0);
+            let start = self.as_mut_ptr();
+            for i in 0..len {
+                let p = start.add(i);
+                ptr::write(p, f(ptr::read(p)));
+            }
+            self.set_len(len);
+        }
+        self
+    }
+}
+
+impl<T> IdFunctor for Box<[T]> {
+    type Inner = T;
+
+    #[inline]
+    fn map_id<F>(self, f: F) -> Self
+    where
+        F: FnMut(Self::Inner) -> Self::Inner,
+    {
+        Vec::from(self).map_id(f).into()
+    }
+}
+
+impl<I: Idx, T> IdFunctor for IndexVec<I, T> {
+    type Inner = T;
+
+    #[inline]
+    fn map_id<F>(self, f: F) -> Self
+    where
+        F: FnMut(Self::Inner) -> Self::Inner,
+    {
+        IndexVec::from_raw(self.raw.map_id(f))
+    }
+}
diff --git a/compiler/rustc_data_structures/src/lib.rs b/compiler/rustc_data_structures/src/lib.rs
index 322c7a71160..6b952f20dd1 100644
--- a/compiler/rustc_data_structures/src/lib.rs
+++ b/compiler/rustc_data_structures/src/lib.rs
@@ -27,6 +27,7 @@
 #![feature(extend_one)]
 #![feature(const_panic)]
 #![feature(min_const_generics)]
+#![feature(new_uninit)]
 #![feature(once_cell)]
 #![feature(maybe_uninit_uninit_array)]
 #![allow(rustc::default_hash_types)]
@@ -70,6 +71,7 @@ pub mod box_region;
 pub mod captures;
 pub mod const_cstr;
 pub mod flock;
+pub mod functor;
 pub mod fx;
 pub mod graph;
 pub mod jobserver;