Bring back nice arena types

hendrikvanantwerpen · Mar 13, 2023 · Mar 13, 2023 · Mar 13, 2023 · Mar 13, 2023 · Mar 13, 2023
commit 0a00cc9b6b560eb2e691c617c84eb3ae59de0710
@@ -563,11 +563,15 @@ pub struct ListCell<T> {
     tail: Handle<ListCell<T>>,
 }
 
+pub trait ListArena<T>: Arena<ListCell<T>> {}
+
+impl<T, A> ListArena<T> for A where A: Arena<ListCell<T>> {}
+
 const EMPTY_LIST_HANDLE: NonZeroU32 = unsafe { NonZeroU32::new_unchecked(u32::MAX) };
 
 impl<T> List<T> {
     /// Creates a new arena that will manage lists of this type.
-    pub fn new_arena() -> impl Arena<ListCell<T>> {
+    pub fn new_arena() -> impl ListArena<T> {
         VecArena::new()
     }
 
@@ -594,7 +598,7 @@ impl<T> List<T> {
     }
 
     /// Pushes a new element onto the front of this list.
-    pub fn push_front(&mut self, arena: &mut impl Arena<ListCell<T>>, head: T) {
+    pub fn push_front(&mut self, arena: &mut impl ListArena<T>, head: T) {
         self.cells = arena.add(ListCell {
             head,
             tail: self.cells,
@@ -603,7 +607,7 @@ impl<T> List<T> {
 
     /// Removes and returns the element at the front of this list.  If the list is empty, returns
     /// `None`.
-    pub fn pop_front<'a>(&mut self, arena: &'a impl Arena<ListCell<T>>) -> Option<&'a T> {
+    pub fn pop_front<'a>(&mut self, arena: &'a impl ListArena<T>) -> Option<&'a T> {
         if self.is_empty() {
             return None;
         }
@@ -615,15 +619,15 @@ impl<T> List<T> {
 
 impl<'a, T: 'a> List<T> {
     /// Returns an iterator over the elements of this list.
-    pub fn iter(mut self, arena: &'a impl Arena<ListCell<T>>) -> impl Iterator<Item = &'a T> + 'a {
+    pub fn iter(mut self, arena: &'a impl ListArena<T>) -> impl Iterator<Item = &'a T> + 'a {
         std::iter::from_fn(move || self.pop_front(arena))
     }
 }
 
 impl<T> List<T> {
     pub fn equals_with<F>(
         mut self,
-        arena: &impl Arena<ListCell<T>>,
+        arena: &impl ListArena<T>,
         mut other: List<T>,
         mut eq: F,
     ) -> bool
@@ -642,7 +646,7 @@ impl<T> List<T> {
 
     pub fn cmp_with<F>(
         mut self,
-        arena: &impl Arena<ListCell<T>>,
+        arena: &impl ListArena<T>,
         mut other: List<T>,
         mut cmp: F,
     ) -> std::cmp::Ordering
@@ -666,7 +670,7 @@ impl<T> List<T>
 where
     T: Eq,
 {
-    pub fn equals(self, arena: &impl Arena<ListCell<T>>, other: List<T>) -> bool {
+    pub fn equals(self, arena: &impl ListArena<T>, other: List<T>) -> bool {
         self.equals_with(arena, other, |a, b| *a == *b)
     }
 }
@@ -675,7 +679,7 @@ impl<T> List<T>
 where
     T: Ord,
 {
-    pub fn cmp(self, arena: &impl Arena<ListCell<T>>, other: List<T>) -> std::cmp::Ordering {
+    pub fn cmp(self, arena: &impl ListArena<T>, other: List<T>) -> std::cmp::Ordering {
         self.cmp_with(arena, other, |a, b| a.cmp(b))
     }
 }
@@ -717,9 +721,13 @@ pub struct ReversibleListCell<T> {
     reversed: Cell<Option<Handle<ReversibleListCell<T>>>>,
 }
 
+pub trait ReversibleListArena<T>: Arena<ReversibleListCell<T>> {}
+
+impl<T, A> ReversibleListArena<T> for A where A: Arena<ReversibleListCell<T>> {}
+
 impl<T> ReversibleList<T> {
     /// Creates a new arena that will manage lists of this type.
-    pub fn new_arena() -> impl Arena<ReversibleListCell<T>> {
+    pub fn new_arena() -> impl ReversibleListArena<T> {
         VecArena::new()
     }
 
@@ -737,7 +745,7 @@ impl<T> ReversibleList<T> {
     }
 
     /// Returns whether we have already calculated the reversal of this list.
-    pub fn have_reversal(&self, arena: &impl Arena<ReversibleListCell<T>>) -> bool {
+    pub fn have_reversal(&self, arena: &impl ReversibleListArena<T>) -> bool {
         if self.is_empty() {
             // The empty list is already reversed.
             return true;
@@ -746,13 +754,13 @@ impl<T> ReversibleList<T> {
     }
 
     /// Pushes a new element onto the front of this list.
-    pub fn push_front(&mut self, arena: &mut impl Arena<ReversibleListCell<T>>, head: T) {
+    pub fn push_front(&mut self, arena: &mut impl ReversibleListArena<T>, head: T) {
         self.cells = arena.add(ReversibleListCell::new(head, self.cells, None));
     }
 
     /// Removes and returns the element at the front of this list.  If the list is empty, returns
     /// `None`.
-    pub fn pop_front<'a>(&mut self, arena: &'a impl Arena<ReversibleListCell<T>>) -> Option<&'a T> {
+    pub fn pop_front<'a>(&mut self, arena: &'a impl ReversibleListArena<T>) -> Option<&'a T> {
         if self.is_empty() {
             return None;
         }
@@ -766,7 +774,7 @@ impl<'a, T: 'a> ReversibleList<T> {
     /// Returns an iterator over the elements of this list.
     pub fn iter(
         mut self,
-        arena: &'a impl Arena<ReversibleListCell<T>>,
+        arena: &'a impl ReversibleListArena<T>,
     ) -> impl Iterator<Item = &'a T> + 'a {
         std::iter::from_fn(move || self.pop_front(arena))
     }
@@ -779,7 +787,7 @@ where
     /// Reverses the list.  Since we're already caching everything in an arena, we make sure to
     /// only calculate the reversal once, returning it as-is if you call this function multiple
     /// times.
-    pub fn reverse(&mut self, arena: &mut impl Arena<ReversibleListCell<T>>) {
+    pub fn reverse(&mut self, arena: &mut impl ReversibleListArena<T>) {
         if self.is_empty() {
             return;
         }
@@ -790,7 +798,7 @@ where
     /// Ensures that the reversal of this list is available.  It can be useful to precalculate this
     /// when you have mutable access to the arena, so that you can then reverse and un-reverse the
     /// list later when you only have shared access to it.
-    pub fn ensure_reversal_available(&self, arena: &mut impl Arena<ReversibleListCell<T>>) {
+    pub fn ensure_reversal_available(&self, arena: &mut impl ReversibleListArena<T>) {
         // First check to see if the list has already been reversed.
         if self.is_empty() {
             // The empty list is already reversed.
@@ -809,7 +817,7 @@ where
 impl<T> ReversibleList<T> {
     /// Reverses the list, assuming that the reversal has already been computed.  If it hasn't we
     /// return an error.
-    pub fn reverse_reused(&mut self, arena: &impl Arena<ReversibleListCell<T>>) -> Result<(), ()> {
+    pub fn reverse_reused(&mut self, arena: &impl ReversibleListArena<T>) -> Result<(), ()> {
         if self.is_empty() {
             // The empty list is already reversed.
             return Ok(());
@@ -847,7 +855,7 @@ where
 {
     fn reverse(
         forwards: Handle<ReversibleListCell<T>>,
-        arena: &mut impl Arena<ReversibleListCell<T>>,
+        arena: &mut impl ReversibleListArena<T>,
     ) -> Handle<ReversibleListCell<T>> {
         let mut reversed = ReversibleListCell::empty_handle();
         let mut current = forwards;
@@ -874,7 +882,7 @@ where
 impl<T> ReversibleList<T> {
     pub fn equals_with<F>(
         mut self,
-        arena: &impl Arena<ReversibleListCell<T>>,
+        arena: &impl ReversibleListArena<T>,
         mut other: ReversibleList<T>,
         mut eq: F,
     ) -> bool
@@ -893,7 +901,7 @@ impl<T> ReversibleList<T> {
 
     pub fn cmp_with<F>(
         mut self,
-        arena: &impl Arena<ReversibleListCell<T>>,
+        arena: &impl ReversibleListArena<T>,
         mut other: ReversibleList<T>,
         mut cmp: F,
     ) -> std::cmp::Ordering
@@ -917,11 +925,7 @@ impl<T> ReversibleList<T>
 where
     T: Eq,
 {
-    pub fn equals(
-        self,
-        arena: &impl Arena<ReversibleListCell<T>>,
-        other: ReversibleList<T>,
-    ) -> bool {
+    pub fn equals(self, arena: &impl ReversibleListArena<T>, other: ReversibleList<T>) -> bool {
         self.equals_with(arena, other, |a, b| *a == *b)
     }
 }
@@ -932,7 +936,7 @@ where
 {
     pub fn cmp(
         self,
-        arena: &impl Arena<ReversibleListCell<T>>,
+        arena: &impl ReversibleListArena<T>,
         other: ReversibleList<T>,
     ) -> std::cmp::Ordering {
         self.cmp_with(arena, other, |a, b| a.cmp(b))
@@ -956,6 +960,10 @@ impl<T> Copy for ReversibleList<T> {}
 
 pub type DequeCell<T> = ReversibleListCell<T>;
 
+pub trait DequeArena<T>: Arena<DequeCell<T>> {}
+
+impl<T, A> DequeArena<T> for A where A: Arena<DequeCell<T>> {}
+
 /// An arena-allocated deque.
 ///
 /// Under the covers, this is implemented as a [`List`][].  Because these lists are singly-linked,
@@ -996,7 +1004,7 @@ impl std::ops::Not for DequeDirection {
 
 impl<T> Deque<T> {
     /// Creates a new arena that will manage deques of this type.
-    pub fn new_arena() -> impl Arena<DequeCell<T>> {
+    pub fn new_arena() -> impl DequeArena<T> {
         VecArena::new()
     }
 
@@ -1019,7 +1027,7 @@ impl<T> Deque<T> {
     }
 
     /// Returns whether we have already calculated the reversal of this deque.
-    pub fn have_reversal(&self, arena: &impl Arena<DequeCell<T>>) -> bool {
+    pub fn have_reversal(&self, arena: &impl DequeArena<T>) -> bool {
         self.list.have_reversal(arena)
     }
 
@@ -1039,7 +1047,7 @@ impl<'a, T: 'a> Deque<T> {
     /// turn, means that we only need shared access to the arena, and not mutable access to it.)
     pub fn iter_unordered(
         &self,
-        arena: &'a impl Arena<DequeCell<T>>,
+        arena: &'a impl DequeArena<T>,
     ) -> impl Iterator<Item = &'a T> + 'a {
         self.list.iter(arena)
     }
@@ -1050,7 +1058,7 @@ where
     T: Clone,
 {
     /// Ensures that this deque has computed its backwards-facing list of elements.
-    pub fn ensure_backwards(&mut self, arena: &mut impl Arena<DequeCell<T>>) {
+    pub fn ensure_backwards(&mut self, arena: &mut impl DequeArena<T>) {
         if self.is_backwards() {
             return;
         }
@@ -1059,7 +1067,7 @@ where
     }
 
     /// Ensures that this deque has computed its forwards-facing list of elements.
-    pub fn ensure_forwards(&mut self, arena: &mut impl Arena<DequeCell<T>>) {
+    pub fn ensure_forwards(&mut self, arena: &mut impl DequeArena<T>) {
         if self.is_forwards() {
             return;
         }
@@ -1073,27 +1081,27 @@ where
     }
 
     /// Pushes a new element onto the front of this deque.
-    pub fn push_front(&mut self, arena: &mut impl Arena<DequeCell<T>>, element: T) {
+    pub fn push_front(&mut self, arena: &mut impl DequeArena<T>, element: T) {
         self.ensure_forwards(arena);
         self.list.push_front(arena, element);
     }
 
     /// Pushes a new element onto the back of this deque.
-    pub fn push_back(&mut self, arena: &mut impl Arena<DequeCell<T>>, element: T) {
+    pub fn push_back(&mut self, arena: &mut impl DequeArena<T>, element: T) {
         self.ensure_backwards(arena);
         self.list.push_front(arena, element);
     }
 
     /// Removes and returns the element from the front of this deque.  If the deque is empty,
     /// returns `None`.
-    pub fn pop_front<'a>(&mut self, arena: &'a mut impl Arena<DequeCell<T>>) -> Option<&'a T> {
+    pub fn pop_front<'a>(&mut self, arena: &'a mut impl DequeArena<T>) -> Option<&'a T> {
         self.ensure_forwards(arena);
         self.list.pop_front(arena)
     }
 
     /// Removes and returns the element from the back of this deque.  If the deque is empty,
     /// returns `None`.
-    pub fn pop_back<'a>(&mut self, arena: &'a mut impl Arena<DequeCell<T>>) -> Option<&'a T> {
+    pub fn pop_back<'a>(&mut self, arena: &'a mut impl DequeArena<T>) -> Option<&'a T> {
         self.ensure_backwards(arena);
         self.list.pop_front(arena)
     }
@@ -1102,11 +1110,7 @@ where
     /// direction, as long as they're the same, so do the minimum amount of work to bring this
     /// about.  (In particular, if we've already calculated the reversal of one of the deques,
     /// reverse that one.)
-    fn ensure_same_direction(
-        &mut self,
-        arena: &mut impl Arena<DequeCell<T>>,
-        other: &mut Deque<T>,
-    ) {
+    fn ensure_same_direction(&mut self, arena: &mut impl DequeArena<T>, other: &mut Deque<T>) {
         if self.direction == other.direction {
             return;
         }
@@ -1125,10 +1129,7 @@ where
     T: Clone,
 {
     /// Returns an iterator over the contents of this deque in a forwards direction.
-    pub fn iter(
-        &self,
-        arena: &'a mut impl Arena<DequeCell<T>>,
-    ) -> impl Iterator<Item = &'a T> + 'a {
+    pub fn iter(&self, arena: &'a mut impl DequeArena<T>) -> impl Iterator<Item = &'a T> + 'a {
         let mut list = self.list;
         if self.is_backwards() {
             list.reverse(arena);
@@ -1139,7 +1140,7 @@ where
     /// Returns an iterator over the contents of this deque in a backwards direction.
     pub fn iter_reversed(
         &self,
-        arena: &'a mut impl Arena<DequeCell<T>>,
+        arena: &'a mut impl DequeArena<T>,
     ) -> impl Iterator<Item = &'a T> + 'a {
         let mut list = self.list;
         if self.is_forwards() {
@@ -1155,7 +1156,7 @@ where
 {
     pub fn equals_with<F>(
         mut self,
-        arena: &mut impl Arena<DequeCell<T>>,
+        arena: &mut impl DequeArena<T>,
         mut other: Deque<T>,
         eq: F,
     ) -> bool
@@ -1168,7 +1169,7 @@ where
 
     pub fn cmp_with<F>(
         mut self,
-        arena: &mut impl Arena<DequeCell<T>>,
+        arena: &mut impl DequeArena<T>,
         mut other: Deque<T>,
         cmp: F,
     ) -> std::cmp::Ordering
@@ -1187,7 +1188,7 @@ impl<T> Deque<T>
 where
     T: Clone + Eq,
 {
-    pub fn equals(self, arena: &mut impl Arena<DequeCell<T>>, other: Deque<T>) -> bool {
+    pub fn equals(self, arena: &mut impl DequeArena<T>, other: Deque<T>) -> bool {
         self.equals_with(arena, other, |a, b| *a == *b)
     }
 }
@@ -1196,7 +1197,7 @@ impl<T> Deque<T>
 where
     T: Clone + Ord,
 {
-    pub fn cmp(self, arena: &mut impl Arena<DequeCell<T>>, other: Deque<T>) -> std::cmp::Ordering {
+    pub fn cmp(self, arena: &mut impl DequeArena<T>, other: Deque<T>) -> std::cmp::Ordering {
         self.cmp_with(arena, other, |a, b| a.cmp(b))
     }
 }
@@ -1207,10 +1208,7 @@ impl<'a, T: 'a> Deque<T> {
     /// Panics if we haven't already computed it.
     ///
     /// [`ensure_forwards`]: #method.ensure_forwards
-    pub fn iter_reused(
-        &self,
-        arena: &'a impl Arena<DequeCell<T>>,
-    ) -> impl Iterator<Item = &'a T> + 'a {
+    pub fn iter_reused(&self, arena: &'a impl DequeArena<T>) -> impl Iterator<Item = &'a T> + 'a {
         let mut list = self.list;
         if self.is_backwards() {
             list.reverse_reused(arena)
@@ -1226,7 +1224,7 @@ impl<'a, T: 'a> Deque<T> {
     /// [`ensure_backwards`]: #method.ensure_backwards
     pub fn iter_reversed_reused(
         &self,
-        arena: &'a impl Arena<DequeCell<T>>,
+        arena: &'a impl DequeArena<T>,
     ) -> impl Iterator<Item = &'a T> + 'a {
         let mut list = self.list;
         if self.is_forwards() {