Tracking issue for TrustedLen (`trusted_len`)

[bluss]

Implemented in #37306

Open Questions:

• <Anything?>

[est31]

Oh, finally this thing is there!

I was avoiding collect() like the plague because of this missing.

[photino]

I think it is better named TrustedLenIterator, since we don't call ExactSizeIterator as ExactSize.

[jethrogb]

Or perhaps TrustedSizeIterator?

[cyplo]

As the referenced code is merged - is this still an issue ? thank you !

[bluss]

Yes, tracking issues keep note on the code while it is still an unstable feature; they are closed when the feature is stabilized or removed.

[alexbool]

By the way, what is holding stabilization right now?

[vadixidav]

I feel that ExactSizeIterator should be addressed in the documentation for TrustedLen. Although the default implementation should be correct, TrustedLen should also specify that any override in ExactSizeIterator (or rather that the trait overall) should also fulfill the contract to be implemented.

Any thoughts?

[ishitatsuyuki]

Do we need a RFC for stabilization? Also, is TrustedLen meant to be the successor (replacement) of ExactSizeIterator?

[bluss]

It serves a different purpose, so I don't think it is a successor. Good start towards stabilization would be to incorporate the naming suggestions from this tracking issue I think.

[BatmanAoD]

Unless I misunderstand (which is likely), this trait indicates that the number of iterations can be calculated in advance, and that it will be a finite number, possibly greater than max usize.

In that case, I would suggest one of FiniteSizeIterator or KnownSizeIterator.

• ...SizeIterator is consistent with ExactSizeIterator, as mentioned above.
  • "Size" is possibly ambiguous since it usually refers to bytes-of-memory, so I think ...LenIterator would be a better name for both traits, but I also think that consistency is a more important consideration.
  • If and when #41517 is completed, ...SizeIterator traits could be renamed to ...LenIterator and the old names can be aliased to the new ones, then deprecated in the next epoch.
• "Known" may be a bit of a misnomer, since the length isn't technically required to be cached prior to calling size_hint, and as far as I can tell even calling size_hint won't necessarily actually calculate the exact number if it's larger than the maximum usize. But the value must in principle be knowable, and KnownSizeIterator seems cleaner and more user-friendly than KnowableSizeIterator.
• "Finite", by implicit contrast to "infinite" or "non-finite", nicely avoids implying that the number is small enough to be useful as, e.g., an array length--which is the primary important distinguishing characteristic from ExactSizeIterator.

I also considered BoundedSizeIterator, but this seems strictly inferior to FiniteSizeIterator since it carries the same correct connotation of having a possibly large-size but fails to indicate that the upper and lower bounds should match.

By the way, what exactly does size_hint return as the lower-bound when the actual length is too large to fit in a usize?

[sfackler]

usize::max_value()

[scottmcm]

The Trusted part here makes me think of rust-lang/rfcs#2237 (comment). It sortof feels like the things currently specializing on TrustedLen want instead of specialize on I: unsafe ExactSizeIterator as a way to say "I need to trust that this actually does what its documentation says it does".

is TrustedLen meant to be the successor (replacement) of ExactSizeIterator?

As currently spec'd, they're complements of each other. Speaking roughly, ExactSizeIterator can be shrunk but not grown, whereas TrustedLen can be grown but not shrunk. (For specific examples, Skip propagates ExactSizeIterator but not TrustedLen, and Chain propagates TrustedLen but not ExactSizeIterator.)

[SimonSapin]

The libs team discussed this and the consensus was that, since this trait was introduced in order to specialize on it, it should stay unstable until trait specialization itself becomes closer to stabilization.

[Phlosioneer]

ExactSizeIterator should be a strict subset of TrustedLen. Therefore, it should make sense to define impl<T: ExactSizeIterator> TrustedLen for T. Is there any reason we haven't already done that?

[sfackler]

TrustedLen is an unsafe trait and ExactSizeIterator is not.

[scottmcm]

@Phlosioneer

ExactSizeIterator should be a strict subset of TrustedLen

That's not quite true; see the example in #37572 (comment).

[Phlosioneer]

TrustedLen is an unsafe trait and ExactSizeIterator is not.

Ah. So perhaps eventually.

@scottmcm
I saw that example. I agree, they're not the same, and must be propagated differently. But if you already have an ExactSizeIterator, then you clearly also satisfy the requirements of a TrustedLen where the length fits inside of a usize.

The type doesn't actually mean anything inherently; it's only a refinement on the return value of size_hint.

[clarfon]

IMHO we're missing UnboundedIterator, which was one of the ideas TrustedLen aimed to solve. It seems silly to have an unsafe trait for this when a safe one would suffice. (Silly note on semantics: "unbounded" here means can't be bounded by a usize, which may still be finite.)

As far as TrustedLen goes, I'd go with BoundedIterator, where the size_hint is (usize, usize) rather than (usize, Option<usize>). That would essentially replace TrustedLen, minus the unbounded case.

[Phlosioneer]

I think there are only two things blocking stability for this trait. First, there's questions about what the name should be. Second, we need to improve documentation to make the distinction between this and ExactSizeIterator crystal clear.

There are also open questions here about methods that may be included, but they can be handled as separate issues to allow the trait to continue toward stabilization.

Here's what is not in question:

• The trait serves a useful purpose as-is. The RFC goes into details about performance improvements (#37306 (comment)).
• The trait needs to be labeled unsafe. No concerns regarding this have been raised about this.

I suggest the lang team (or lib team? I get the teams all mixed up) should consider the options presented here and revise the name. Then we can change the name in nightly, and see if there are any comments for a few months. This allows us to make small, steady steps forward.

Edit: I spotted the comment #37572 (comment) that said the team wanted to block this until trait specialization is done. I'd still like to make small steps forward, but if they want to hold off then I understand. Sorry for the disruption.