#First time implementing IntoIterator

103 messages · Page 1 of 1 (latest)

wild horizon
#

This is the first time I've implemented IntoIterator myself so I was wondering if there are any conventions I didn't follow properly, or really just anything I could improve with this implementation.

📎 iter.rs
whole gale
#

why all the Send + Sync

#

what's a FixedVec

#

one slight drawback here regarding unwind safety

wild horizon
# whole gale what's a `FixedVec`

My own type of vec, main difference is just that it doesn't allocate more memory if the capacity is exceeded & it uses an atomic usize for tracking length, but besides that, the layout in memory is the same as a vec; it's just a contiguous array of elements

whole gale
#

if drop_in_place(elems) panics, you won't deallocate the memory

#

this is generally handled either through a field, or a drop guard

wild horizon
whole gale
#

yes

#

it calls Drop::drop on each element

#

which is user defined

#

and may panic

#

for the dropguard example

whole gale
#

also you might actually want to do a little bit of
unsafe impl Sync/Send

wild horizon
# whole gale don't think you need all the `Send + Sync` bounds then

Oh right, I could just add it as trait bounds to T only on the Send/Sync impls?

pub struct FixedVec<T> {
    ptr: NonNull<T>,
    next_idx: AtomicUsize,
    len: AtomicUsize,
    cap: usize,
}

// SAFETY: operations on the same value are atomic.
unsafe impl<T: Send> Send for FixedVec<T> {}
// SAFETY: addresses are all based on the atomic length and unmodified pointer.
// They cannot overlap.
unsafe impl<T: Sync> Sync for FixedVec<T> {}
whole gale
#

i don't know what api FixedVec provides

#

so i can't tell you if these are correct

#

i doubt it though

#

i can tell you for IntoIter though

wild horizon
#

well the only reason I had Send + Sync on my iterator is cause I originally had those bounds on FixedVec. Wouldn't removing the Send + Sync bounds from the iterator mean removing them from FixedVec too?

whole gale
#

you shouldn't have the bound on the FixedVec type either

whole gale
whole gale
# whole gale i can tell you for `IntoIter` though 
// SAFETY : IntoIter has no public field, and no method taking `&self` (including Clone and Copy), therefore it is unconditionally Sync
unsafe impl<T> Sync for IntoIter<T> {}

// SAFETY : IntoIter is transparent regarding Send-ness, it owns a collection of Ts by value and can gives them out through a &mut operation, much like `vec::IntoIter`
unsafe impl<T : Send> Send for IntoIter<T> {}
wild horizon
whole gale
wild horizon
#

*Send & Sync

whole gale
#

i think the safety comments were clear, i can try to explain more ifyou can tell me what you find unclear

#

the way to think about it in terms of std type equivalent, is that it's very much like a std::sync::Exclusive<std::vec::IntoIter<T>>

wild horizon
wild horizon
whole gale
gleaming sinew
#

Some improvements would be implementing DoubleEndedIterator (allows calling rev to go backwards from the other end of the vector), FusedIterator (turns iter.fuse() into a no-op since the iterator is already fused, which prevents wrapping it in an iterator adapter that does extra work to stop producing Somes after the first None), and ExactSizeIterator (can optimize some things that rely on the exact number of remaining elements, like iter.collect) onto your IntoIter type (https://doc.rust-lang.org/core/iter/index.html#traits).

#

DoubleEndedIterator can be facilitated by using start_idx (inclusive bound) and end_idx (exclusive bound) (or start and end) instead of idx.

#

The default implementation of Iterator methods can be improved quite a bit by implementing most or all methods from Iterator and those other traits that don't take a closure, require nightly, or wrap the iterator in another type (like Cycle<Self> for the cycle method). For example, you can give an exact response for size_hint based on the number of elements that haven't been iterated over yet rather than the default which says that there are between zero and infinity items.

wild horizon
native wedge
# wild horizon is retain still usable on a FusedIterator?

Why wouldn't it? Also note: even if a method "makes a fused iter a nonfused iter", it would simply retuen an iterator wrapper type that doesn't inpl FusedIterator regardless of if the inner iter does or not.

This applies to all traits that may be used by an iterator bdw

native wedge
wild horizon
native wedge
#

It's ok <33
Now you know at least xD :]

wild horizon
#

yep :)

wild horizon
whole gale
wild horizon
#

I believe I've implemented all recommendations now

gleaming sinew
#

I'd recommend end being an exclusive bound (1 past the last item), as when self.len() == 0, end currently starts off as -1, which is an overflow.

#

Some other nice Iterator methods to implement efficiently to avoid calling next repeatedly until the iterator is exhausted:

  • Iterator::count can just return a quickly calculated count of remaining items.
  • Iterator::last can just call DoubleEndedIterator::next_back.
#

Other than that, I can't see any massive improvements.

wild horizon
native wedge
#

(Do wanna add that you can almost always impove iterator implementations fkr most stuff, there might seam like there is a lot of stuff so if it's too much I do also recommend taking it slowly, everything here does apply but don't force yourself to do too much such that you also understand and are not beign rushed or you don't feal that ur makign a bajilion cha ged and all that)

wild horizon
wild horizon
gleaming sinew
#

Yes, that's right.

wild horizon
#

Iterator::last can just call DoubleEndedIterator::next_back.
Ah Iterator::last, similarly, is also iterating over the whole thing

gleaming sinew
#

Right.

wild horizon
#

If I also want to implement iterator on references to my Vec, should that just call the existing get_unchecked() rather than re-implement that?

gleaming sinew
wild horizon
# gleaming sinew Yes, that should be fine.

it seems it works for immutable get_unchecked but not when I try to implement it for mutable references using get_mut_unchecked (both are exactly the same implementation, apart from the latter being mutable). Oddly enough, the issue isn't a double mut borrow one, it's a lifetime issue ferrisThink

gleaming sinew
#

For mut you might need a splitting function since otherwise it will lock the whole vector or slice (only one reference to the slice can normally exist without unsafe since mutable also means unique).

#

Or you can just cast mut pointers to mut references, being very careful not to produce the same index twice.

#

In fact, if you can get a mutable slice from your vector, you can reuse its iterator.

wild horizon
wild horizon
turbid roost
wild horizon
turbid roost
#

the reason why it was unconditionally Sync before doesn't hold anymore

#

technically size_hint takes &self but it doesn't touch the Ts so it was fine

wild horizon
#

IntoIter owns the memory

turbid roost
#

yes and ?

wild horizon
turbid roost
#

if you have an idempotent &C -> &T, then C : Sync must require T : Sync at least

#

ah i misunderstood

#

i thought you wanted to add as_slice & as_mut_slice to IntoIter

wild horizon
turbid roost
#

as long as you don't have &IntoIter<T> -> &T, IntoIter<T> can stay unconditionally Sync.

wild horizon
#

should I be using #[may_dangle]? idk what it does, but the standard library's vec uses that

unsafe impl<#[may_dangle] T, A: Allocator> Drop for Vec<T, A> {
    fn drop(&mut self) {
        unsafe {
            // use drop for [T]
            // use a raw slice to refer to the elements of the vector as weakest necessary type;
            // could avoid questions of validity in certain cases
            ptr::drop_in_place(ptr::slice_from_raw_parts_mut(self.as_mut_ptr(), self.len))
        }
        // RawVec handles deallocation
    }
}
gleaming sinew
#

Do you use dangling pointers (points at nothing, but not set to NULL)? Vec uses it so that it doesn't have to allocate when the Vec is new and empty.

wild horizon
# gleaming sinew Do you use dangling pointers (points at nothing, but not set to NULL)? `Vec` use...

Yeah if the layout size is 0, I get a dangling pointer

    #[inline]
    pub fn new(capacity: usize) -> Self {
        let ptr;
        let layout = Layout::array::<T>(capacity).expect("Layout overflow");
        if layout.size() == 0 {
            ptr = NonNull::dangling();
        } else {
            // SAFETY: we check for a zero-sized type or capacity above.
            let raw_ptr = unsafe { alloc(layout) } as *mut T;

            if raw_ptr.is_null() {
                handle_alloc_error(layout);
            }

            // SAFETY: we check for a null pointer above.
            ptr = unsafe { NonNull::new_unchecked(raw_ptr) };
        }

        Self {
            ptr,
            next_idx: AtomicUsize::new(0),
            len: AtomicUsize::new(0),
            cap: capacity,
        }
    }
gleaming sinew
#

There's also #dark-arts if you don't get help here.

turbid roost
#

it's about dangling types

#

and is indeed appropriate for the situation

wild horizon
turbid roost
#

this is how most similar types work

#

the escape hatch is not necessary for casual use

#

it just makes more things posible

wild horizon
turbid roost
#

no, it does work with non -'static T rn

wild horizon
turbid roost
# wild horizon hmm? so what would adding `#[may_dangle]` do? 
struct IntoIter<'a, T>(T, &'a str);

impl<'a, T> Drop for IntoIter<'a, T> {
    fn drop(&mut self) {
        println!("Inspector(_, {}) knows when *not* to inspect.", self.1);
    }
}

struct World<'a, T> {
    iter: Option<IntoIter<T>>,
    days: Box<u8>,
}

fn main() {
    let mut world = World {
        iter: None,
        days: Box::new(1),
    };
    world.iter = Some(IntoIter(&world.days, "gadget"));
}
#

this doesn't compile

# 
#![feature(dropck_eyepatch)]

struct IntoIter<'a, T>(T, &'a str);

unsafe impl<'a, #[may_dangle] T> Drop for IntoIter<'a, T> {
    fn drop(&mut self) {
        println!("Inspector(_, {}) knows when *not* to inspect.", self.1);
    }
}

struct World<'a, T> {
    iter: Option<IntoIter<'a, T>>,
    days: Box<u8>,
}

fn main() {
    let mut world = World {
        iter: None,
        days: Box::new(1),
    };
    world.iter = Some(IntoIter(&world.days, "gadget"));
}

but this does

wild horizon