[414owen]

View all comments

Where:
A: ExactSizeIterator,
B: Clone,

And the symmetrical instance.

The only other instance for ExactSizeIterator<Zip<_, _>> requires each zipped iterator to be ExactSizeIterator, and since Repeat does not implement ExactSizeIterator, these instances don't overlap with anything.

---

I posted on the internals forum, and was told these instances would be insta-stable.

The stable attribute seems to require feature and since attributes, which I'm not entirely sure I've done correctly. Pointers are welcome.

[rustbot]

r? @ibraheemdev

rustbot has assigned @ibraheemdev.
They will have a look at your PR within the next two weeks and either review your PR or reassign to another reviewer.

Use r? to explicitly pick a reviewer

[yotamofek]

Cool idea!

I think they could/should also be TrustedLen, which is even more useful than ESI in cases where you're extending or collecting into, i.e.:

rust/library/alloc/src/vec/mod.rs

Lines 3811 to 3840 in eec6bd9

	fn extend_trusted(&mut self, iterator: impl iter::TrustedLen<Item = T>) {
	let (low, high) = iterator.size_hint();
	if let Some(additional) = high {
	debug_assert_eq!(
	low,
	additional,
	"TrustedLen iterator's size hint is not exact: {:?}",
	(low, high)
	);
	self.reserve(additional);
	unsafe {
	let ptr = self.as_mut_ptr();
	let mut local_len = SetLenOnDrop::new(&mut self.len);
	iterator.for_each(move |element| {
	ptr::write(ptr.add(local_len.current_len()), element);
	// Since the loop executes user code which can panic we have to update
	// the length every step to correctly drop what we've written.
	// NB can't overflow since we would have had to alloc the address space
	local_len.increment_len(1);
	});
	}
	} else {
	// Per TrustedLen contract a `None` upper bound means that the iterator length
	// truly exceeds usize::MAX, which would eventually lead to a capacity overflow anyway.
	// Since the other branch already panics eagerly (via `reserve()`) we do the same here.
	// This avoids additional codegen for a fallback code path which would eventually
	// panic anyway.
	panic!("capacity overflow");
	}
	}

[414owen]

Thanks @yotamofek :)

There's already a:

unsafe impl<A, B> TrustedLen for Zip<A, B>
where
    A: TrustedLen,
    B: TrustedLen,
{
}

And since Repeat implements TrustedLen itself, I think this case is already covered?

[yotamofek]

Ah right, sorry, missed that!

[scottmcm]

I think what this really wants it an InfiniteIterator trait for Repeat and RangeFrom and such to implement. Because why Zip<A, Repeat<B>> but not Zip<A, RangeFrom<B>> or Zip<A, RepeatWith<B>> or ...

[414owen]

@scottmcm I had the same thought, but I figured this would be easier to get through, first.

[VorpalBlade]

RepeatWith could also be added to the list @scottmcm mentioned. Such a trait would also scale better outside std in case other iterators outside std can both implement said trait and make use of said trait for their own optimisations.

[414owen]

Although for InfiniteIterator my motivation was more for iter.chain(repeat(n)), etc.

The instance for Zip would overlap with the existing ExactSizeIterator trait, and I'm not sure what the best way to tell the compiler they're mutually exclusive traits would be... (edit, looks like I can use negative bounds, nowadays?)

[ibraheemdev]

r? libs-api

[414owen]

@scottmcm @VorpalBlade please see #146668, and the comment I added there.

[clarfonthey]

r? libs

[JohnTitor]

r? libs

[Mark-Simulacrum]

@rfcbot fcp merge libs

[rust-rfcbot]

@Mark-Simulacrum has proposed to merge this. The next step is review by the rest of the tagged team members:

• @ChrisDenton
• @Mark-Simulacrum
• @cuviper
• @dtolnay
• @joshtriplett
• @nia-e
• @the8472
• @thomcc

Concerns:

• infinite-iterator (Implement ExactSizeIterator for Zip<A, Repeat<B>> #146642 (comment))

Once a majority of reviewers approve (and at most 2 approvals are outstanding), this will enter its final comment period. If you spot a major issue that hasn't been raised at any point in this process, please speak up!

cc @rust-lang/libs-ping: FCP proposed for libs, please feel free to register concerns.
See this document for info about what commands tagged team members can give me.

[rustbot]

This PR was rebased onto a different main commit. Here's a range-diff highlighting what actually changed.

Rebasing is a normal part of keeping PRs up to date, so no action is needed—this note is just to help reviewers.

[clarfonthey]

I think we should register a formal concern for InfiniteIterator to be an alternative to this, as mentioned in #146642 (comment)

[Mark-Simulacrum]

Is doing this a blocker to later adding InfiniteIterator? It seems like we should be able to replace this impl with that more general impl if/when we decide to do that?

[clarfonthey]

It could, but we're also setting the precedent that we are fine just adding in cases that would be better suited for that trait in the meantime, and I propose we don't do that. Essentially, proposing that only two options are acceptable:

1. Saying we won't merge impls like this in general because it's not useful
2. Solving the problem in general with a trait like InfiniteIterator

The third option ends up kind of saying that we do this for Repeat as a special case, then maybe later someone has a compelling reason to use RepeatWith, then we're just choosing to pile up FCPs instead of solving the problem properly. And Scott put a pretty compelling case: I can see complicated combinations like zipping with (N…).step_by(M) being useful and I don't think that we should canonise Repeat as being the case where this is okay without including all those other options.

[Mark-Simulacrum]

@rfcbot fcp concern infinite-iterator

Ok, I'll cut a concern on your behalf. I'm not sure I would jump to a general solution until we have at least a few cases, but 🤷 no strong opinion on it. Interested in other opinions on this.

It does seem like it'd be good to cut an ACP for infinite iterator in that case...

[clarfonthey]

I mean, strictly speaking, I was providing a compelling case based upon Scott's comment which included RangeFrom and RepeatWith

Enumerate is effectively a special case of iter.zip(0usize..) and there are other cases where it might be useful to zip theoretically infinite sequences while still desiring the ability to depend on the left-hand-side's bound. The (N..).step_by(M) example, for example, is what you might use if you wanted an equivalent to enumerate for slice[N..].chunks(M).

[414owen]

Just a refresher, since this issue is a little old:

A more general solution runs into problems (InfiniteIterator hits some overlapping instances).
To get around those, you need an even more general solution, (QuantifiedIterator, detailed in this proposal: rust-lang/libs-team#659). This almost works, but would require a constraint synonym language feature to be 100% backwards-compatible.

Since I don't see a way to actually get a more general solution in, (apart from possibly adding it to a new language edition?), I still think that merging this PR is a good idea.
Even if this ends up being generalized, since generalization seems to require backwards-compatibility, I don't see a problem with merging this.

edit: Perfect is the enemy of good, and all that.