Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

What guarantees does core::iter::Repeat give around observing calls to clone? #81292

Closed
lopopolo opened this issue Jan 23, 2021 · 1 comment · Fixed by #85338
Closed

What guarantees does core::iter::Repeat give around observing calls to clone? #81292

lopopolo opened this issue Jan 23, 2021 · 1 comment · Fixed by #85338
Labels
A-iterators Area: Iterators I-slow Issue: Problems and improvements with respect to performance of generated code. T-libs Relevant to the library team, which will review and decide on the PR/issue.

Comments

@lopopolo
Copy link
Contributor

lopopolo commented Jan 23, 2021

Currently, core::iter::Repeat::nth calls core::iter::Repeat::next n times.

This allows a struct with interior mutability or other global state and a custom clone implementation to observe the number of times it has been cloned.

use std::sync::atomic::{AtomicUsize, Ordering};

static COUNTER: AtomicUsize = AtomicUsize::new(0);

struct X;

impl Clone for X {
    fn clone(&self) -> Self {
        COUNTER.fetch_add(1, Ordering::SeqCst);
        Self
    }
}

fn main() {
    let mut iter = core::iter::repeat(X);
    for _ in 0..10_000 {
        let _ = iter.next();
    }
    println!("counter: {}", COUNTER.load(Ordering::SeqCst));
    let _ = iter.nth(555);
    println!("counter: {}", COUNTER.load(Ordering::SeqCst));
}

Currently, this program outputs:

counter: 10000
counter: 10556

Would it be possible to override the implementations of some Iterator methods that have default implementations without breaking any documented contract?

impl<A: Clone> Iterator for Repeat<A> {
    type Item = A;

    #[inline]
    fn next(&mut self) -> Option<A> {
        Some(self.element.clone())
    }

    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        (usize::MAX, None)
    }

    #[inline]
    fn advance_by(&mut self, n: usize) -> Result<(), usize> {
        // Advancing an infinite iterator of a single element is a no-op.
        let _ = n;
    }

    #[inline]
    fn nth(&mut self, n: usize) -> Option<T> {
        let _ = n;
        Some(self.element.clone())
    }

    fn last(self) -> Option<T> {
        loop {}
    }

    fn count(self) -> usize {
        loop {}
    }
}

impl<A: Clone> DoubleEndedIterator for Repeat<A> {
    #[inline]
    fn next_back(&mut self) -> Option<A> {
        Some(self.element.clone())
    }

    #[inline]
    fn advance_back_by(&mut self, n: usize) -> Result<(), usize> {
        // Advancing an infinite iterator of a single element is a no-op.
        let _ = n;
    }

    #[inline]
    fn nth_back(&mut self, n: usize) -> Option<T> {
        let _ = n;
        Some(self.element.clone())
    }
}
@camelid camelid added I-slow Issue: Problems and improvements with respect to performance of generated code. T-libs Relevant to the library team, which will review and decide on the PR/issue. A-iterators Area: Iterators labels Jan 23, 2021
@the8472
Copy link
Member

the8472 commented Mar 6, 2021

At the very least it would be a valid specialization for T: Copy since their clone implementation must be equivalent to copying the value.

https://doc.rust-lang.org/std/clone/trait.Clone.html#how-can-i-implement-clone

GuillaumeGomez added a commit to GuillaumeGomez/rust that referenced this issue May 18, 2021
…gh-81292, r=joshtriplett

Implement more Iterator methods on core::iter::Repeat

`core::iter::Repeat` always returns the same element, which means we can
do better than implementing most `Iterator` methods in terms of
`Iterator::next`.

Fixes rust-lang#81292.

rust-lang#81292 raises the question of whether these changes violate the contract of `core::iter::Repeat`, but as far as I can tell `core::iter::repeat` doesn't make any guarantees around how it calls `Clone::clone`.
GuillaumeGomez added a commit to GuillaumeGomez/rust that referenced this issue May 18, 2021
…gh-81292, r=joshtriplett

Implement more Iterator methods on core::iter::Repeat

`core::iter::Repeat` always returns the same element, which means we can
do better than implementing most `Iterator` methods in terms of
`Iterator::next`.

Fixes rust-lang#81292.

rust-lang#81292 raises the question of whether these changes violate the contract of `core::iter::Repeat`, but as far as I can tell `core::iter::repeat` doesn't make any guarantees around how it calls `Clone::clone`.
@bors bors closed this as completed in 963bd3b May 18, 2021
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
A-iterators Area: Iterators I-slow Issue: Problems and improvements with respect to performance of generated code. T-libs Relevant to the library team, which will review and decide on the PR/issue.
Projects
None yet
Development

Successfully merging a pull request may close this issue.

3 participants