Skip to content

Instantly share code, notes, and snippets.

@Lucretiel
Last active October 29, 2020 19:41
Show Gist options
  • Save Lucretiel/477bf0b5b222eca8f3b77e412518a59c to your computer and use it in GitHub Desktop.
Save Lucretiel/477bf0b5b222eca8f3b77e412518a59c to your computer and use it in GitHub Desktop.
Proposed simple implementation of IntoIter for [T; N]
#![feature(min_const_generics)]
use core::mem::ManuallyDrop;
use core::iter::FusedIterator;
use core::mem;
struct Array<T, const N: usize> {
data: [T; N],
}
impl<T, const N: usize> IntoIterator for Array<T, N> {
type IntoIter = ArrayIntoIter<T, N>;
type Item = T;
fn into_iter(self) -> Self::IntoIter {
ArrayIntoIter {
next_front: 0,
next_back: N,
// Safety: self.data is [T; N], Iter.data is [ManuallyDrop<T>, N].
// ManuallyDrop is repr(transparent) so it definitely has the same layout.
data: unsafe {
let data = self.data;
// Would prefer mem::transmute, but right now it fails with
// U is a different size than T (presumably b/c of const
// generic limitations)
let transmuted = mem::transmute_copy(&data);
mem::forget(data);
transmuted
},
}
}
}
struct ArrayIntoIter<T, const N: usize> {
next_front: usize,
next_back: usize, // one-past-the-end
data: [ManuallyDrop<T>; N],
}
impl<T, const N: usize> Iterator for ArrayIntoIter<T, N> {
type Item = T;
fn next(&mut self) -> Option<T> {
if self.next_front >= self.next_back {
None
} else {
let next = self.next_front;
// Safety: next_front < next_back, so this can never overflow
self.next_front += 1;
// Safety: next_front always points to the next good element in the
// list. We already incremented, so even if anything in this line
// panics, it's the same as if we mem::forgot the item.
let next = unsafe { ManuallyDrop::take(&mut self.data[next]) };
Some(next)
}
}
fn size_hint(&self) -> (usize, Option<usize>) {
(self.len(), Some(self.len()))
}
fn count(self) -> usize {
self.len()
}
fn last(mut self) -> Option<T> {
self.next_back()
}
}
impl<T, const N: usize> ExactSizeIterator for ArrayIntoIter<T, N> {
fn len(&self) -> usize {
self.next_back - self.next_front
}
}
impl<T, const N: usize> FusedIterator for ArrayIntoIter<T, N> {}
impl<T, const N: usize> DoubleEndedIterator for ArrayIntoIter<T, N> {
fn next_back(&mut self) -> Option<T> {
if self.next_front >= self.next_back {
None
} else {
// Safety: next_back > next_front, so this can never underflow
self.next_back -= 1;
// Safety: next_back always points to one past the end of the list,
// so decerementing it points to the last good element in the list.
let next = unsafe { ManuallyDrop::take(&mut self.data[self.next_back]) };
Some(next)
}
}
}
impl<T, const N: usize> Drop for ArrayIntoIter<T, N> {
fn drop(&mut self) {
// Could do it more efficiently with drop-in-place, but
// for now doing the no-unsafe version and trusting the
// optimizer
self.for_each(mem::drop);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment