From c89e64363ba25a4bf487d71a4ad6e9a8cbe40384 Mon Sep 17 00:00:00 2001 From: Giacomo Stevanato Date: Fri, 26 Feb 2021 15:44:35 +0100 Subject: Fix invalid slice access in String::retain --- library/alloc/src/string.rs | 37 ++++++++++++++++++++++--------------- 1 file changed, 22 insertions(+), 15 deletions(-) (limited to 'library/alloc/src') diff --git a/library/alloc/src/string.rs b/library/alloc/src/string.rs index 6fb3fcbb63b..e8d83d3f18d 100644 --- a/library/alloc/src/string.rs +++ b/library/alloc/src/string.rs @@ -1233,37 +1233,44 @@ impl String { where F: FnMut(char) -> bool, { - let len = self.len(); - let mut del_bytes = 0; - let mut idx = 0; + struct SetLenOnDrop<'a> { + s: &'a mut String, + idx: usize, + del_bytes: usize, + } - unsafe { - self.vec.set_len(0); + impl<'a> Drop for SetLenOnDrop<'a> { + fn drop(&mut self) { + let new_len = self.idx - self.del_bytes; + debug_assert!(new_len <= self.s.len()); + unsafe { self.s.vec.set_len(new_len) }; + } } - while idx < len { - let ch = unsafe { self.get_unchecked(idx..len).chars().next().unwrap() }; + let len = self.len(); + let mut guard = SetLenOnDrop { s: self, idx: 0, del_bytes: 0 }; + + while guard.idx < len { + let ch = unsafe { guard.s.get_unchecked(guard.idx..len).chars().next().unwrap() }; let ch_len = ch.len_utf8(); if !f(ch) { - del_bytes += ch_len; - } else if del_bytes > 0 { + guard.del_bytes += ch_len; + } else if guard.del_bytes > 0 { unsafe { ptr::copy( - self.vec.as_ptr().add(idx), - self.vec.as_mut_ptr().add(idx - del_bytes), + guard.s.vec.as_ptr().add(guard.idx), + guard.s.vec.as_mut_ptr().add(guard.idx - guard.del_bytes), ch_len, ); } } // Point idx to the next char - idx += ch_len; + guard.idx += ch_len; } - unsafe { - self.vec.set_len(len - del_bytes); - } + drop(guard); } /// Inserts a character into this `String` at a byte position. -- cgit 1.4.1-3-g733a5 From 236c0cf103aa485db1748587ad87213943bcfb33 Mon Sep 17 00:00:00 2001 From: The8472 Date: Sun, 31 Jan 2021 21:12:43 +0100 Subject: implement TrustedLen and TrustedRandomAccess for VecDeque iterators --- .../alloc/src/collections/vec_deque/into_iter.rs | 32 +++++++++++++++++++++- library/alloc/src/collections/vec_deque/iter.rs | 24 +++++++++++++++- .../alloc/src/collections/vec_deque/iter_mut.rs | 24 +++++++++++++++- 3 files changed, 77 insertions(+), 3 deletions(-) (limited to 'library/alloc/src') diff --git a/library/alloc/src/collections/vec_deque/into_iter.rs b/library/alloc/src/collections/vec_deque/into_iter.rs index 465b058cd98..1c635dd4f27 100644 --- a/library/alloc/src/collections/vec_deque/into_iter.rs +++ b/library/alloc/src/collections/vec_deque/into_iter.rs @@ -1,5 +1,5 @@ use core::fmt; -use core::iter::FusedIterator; +use core::iter::{FusedIterator, TrustedLen, TrustedRandomAccess}; use super::VecDeque; @@ -36,6 +36,22 @@ impl Iterator for IntoIter { let len = self.inner.len(); (len, Some(len)) } + + #[inline] + unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item + where + Self: TrustedRandomAccess, + { + // Safety: The TrustedRandomAccess contract requires that callers only pass an index + // that is in bounds. + // Additionally Self: TrustedRandomAccess is only implemented for T: Copy which means even + // multiple repeated reads of the same index would be safe and the + // values are !Drop, thus won't suffer from double drops. + unsafe { + let idx = self.inner.wrap_add(self.inner.tail, idx); + self.inner.buffer_read(idx) + } + } } #[stable(feature = "rust1", since = "1.0.0")] @@ -55,3 +71,17 @@ impl ExactSizeIterator for IntoIter { #[stable(feature = "fused", since = "1.26.0")] impl FusedIterator for IntoIter {} + +#[unstable(feature = "trusted_len", issue = "37572")] +unsafe impl TrustedLen for IntoIter {} + +#[doc(hidden)] +#[unstable(feature = "trusted_random_access", issue = "none")] +// T: Copy as approximation for !Drop since get_unchecked does not update the pointers +// and thus we can't implement drop-handling +unsafe impl TrustedRandomAccess for IntoIter +where + T: Copy, +{ + const MAY_HAVE_SIDE_EFFECT: bool = false; +} diff --git a/library/alloc/src/collections/vec_deque/iter.rs b/library/alloc/src/collections/vec_deque/iter.rs index ad31b991cb6..e4cfb3acdfd 100644 --- a/library/alloc/src/collections/vec_deque/iter.rs +++ b/library/alloc/src/collections/vec_deque/iter.rs @@ -1,5 +1,5 @@ use core::fmt; -use core::iter::FusedIterator; +use core::iter::{FusedIterator, TrustedLen, TrustedRandomAccess}; use core::ops::Try; use super::{count, wrap_index, RingSlices}; @@ -101,6 +101,19 @@ impl<'a, T> Iterator for Iter<'a, T> { fn last(mut self) -> Option<&'a T> { self.next_back() } + + #[inline] + unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item + where + Self: TrustedRandomAccess, + { + // Safety: The TrustedRandomAccess contract requires that callers only pass an index + // that is in bounds. + unsafe { + let idx = wrap_index(self.tail.wrapping_add(idx), self.ring.len()); + self.ring.get_unchecked(idx) + } + } } #[stable(feature = "rust1", since = "1.0.0")] @@ -157,3 +170,12 @@ impl ExactSizeIterator for Iter<'_, T> { #[stable(feature = "fused", since = "1.26.0")] impl FusedIterator for Iter<'_, T> {} + +#[unstable(feature = "trusted_len", issue = "37572")] +unsafe impl TrustedLen for Iter<'_, T> {} + +#[doc(hidden)] +#[unstable(feature = "trusted_random_access", issue = "none")] +unsafe impl TrustedRandomAccess for Iter<'_, T> { + const MAY_HAVE_SIDE_EFFECT: bool = false; +} diff --git a/library/alloc/src/collections/vec_deque/iter_mut.rs b/library/alloc/src/collections/vec_deque/iter_mut.rs index 3d0c3094e26..9493676e66b 100644 --- a/library/alloc/src/collections/vec_deque/iter_mut.rs +++ b/library/alloc/src/collections/vec_deque/iter_mut.rs @@ -1,5 +1,5 @@ use core::fmt; -use core::iter::FusedIterator; +use core::iter::{FusedIterator, TrustedLen, TrustedRandomAccess}; use core::marker::PhantomData; use super::{count, wrap_index, RingSlices}; @@ -87,6 +87,19 @@ impl<'a, T> Iterator for IterMut<'a, T> { fn last(mut self) -> Option<&'a mut T> { self.next_back() } + + #[inline] + unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item + where + Self: TrustedRandomAccess, + { + // Safety: The TrustedRandomAccess contract requires that callers only pass an index + // that is in bounds. + unsafe { + let idx = wrap_index(self.tail.wrapping_add(idx), self.ring.len()); + &mut *self.ring.get_unchecked_mut(idx) + } + } } #[stable(feature = "rust1", since = "1.0.0")] @@ -126,3 +139,12 @@ impl ExactSizeIterator for IterMut<'_, T> { #[stable(feature = "fused", since = "1.26.0")] impl FusedIterator for IterMut<'_, T> {} + +#[unstable(feature = "trusted_len", issue = "37572")] +unsafe impl TrustedLen for IterMut<'_, T> {} + +#[doc(hidden)] +#[unstable(feature = "trusted_random_access", issue = "none")] +unsafe impl TrustedRandomAccess for IterMut<'_, T> { + const MAY_HAVE_SIDE_EFFECT: bool = false; +} -- cgit 1.4.1-3-g733a5 From 1438207c3d150ce42804e857537b12082c68c79b Mon Sep 17 00:00:00 2001 From: The8472 Date: Sun, 31 Jan 2021 21:13:04 +0100 Subject: use BITS constant --- library/alloc/src/collections/vec_deque/mod.rs | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'library/alloc/src') diff --git a/library/alloc/src/collections/vec_deque/mod.rs b/library/alloc/src/collections/vec_deque/mod.rs index 7a0de74eb23..d3e70991ad5 100644 --- a/library/alloc/src/collections/vec_deque/mod.rs +++ b/library/alloc/src/collections/vec_deque/mod.rs @@ -58,7 +58,7 @@ mod tests; const INITIAL_CAPACITY: usize = 7; // 2^3 - 1 const MINIMUM_CAPACITY: usize = 1; // 2 - 1 -const MAXIMUM_ZST_CAPACITY: usize = 1 << (core::mem::size_of::() * 8 - 1); // Largest possible power of two +const MAXIMUM_ZST_CAPACITY: usize = 1 << (usize::BITS - 1); // Largest possible power of two /// A double-ended queue implemented with a growable ring buffer. /// -- cgit 1.4.1-3-g733a5