Tracking issue for missing Iterator::size_hint implementations

[Phlosioneer]

size_hint() can sometimes allow for more efficient memory allocations, and other good performance things.

I intend to make a PR to implement the trivial / easy ones, at least. I've already made a PR for the first batch, #49201. The ones in that PR are omitted from this list.

This list will be updated as I sort through for false-positives.

Liballoc:

• Range<'a, K, V> (Add size_hints for btree iterators #49550) This is hard, but doable, and useful.
• RangeMut<'a, K, V> (Add size_hints for btree iterators #49550) This is hard, but doable, and useful.
• MergeIter<K, V, I> (Add size_hints for btree iterators #49550) This is hard, but doable, and useful.
• Range<'a, T> (Add size_hints for btree iterators #49550) This is hard, but doable, and useful.

Libcore:

• Pattern: $forward_iterator<'a, P> Impossible to provide upper or lower bounds.
• Pattern: $reverse_iterator<'a, P> Impossible to provide upper or lower bounds.

Libfmt_macros:

• Parser<'a> Both impossible and irrelevant.

Libproc_macro:

• TokenTreeIter Implementation is not trivial. It would be nice to do it eventually, though.

Librustc:

• NodesMatchingSuffix<'o, 'tcx>
• EnumerateAndAdjust<I> (Implement some trivial size_hints for various iterators #49201)
• TraitObligationStackList<'o, 'tcx>
• Ancestors Not trivial, and probably going to change.
• Elaborator<'cx, 'gcx, 'tcx> No way to define an upper bound.
• SupertraitDefIds<'cx, 'gcx, 'tcx> No way to define an upper bound.
• TypeWalker<'tcx> No way to define an upper bound.
• Iter<'dom, Node>
• Iter<'a, T>
• Iter<'a>
• Prefixes<'cx, 'gcx, 'tcx>
• ValueIter
• Autoderef<'a, 'gcx, 'tcx>

Librustdoc:

• CodeBlocks<'a, I>
• LinkReplacer<'a, 'b, I>
• HeadingLinks<'a, 'b, I>
• SummaryLine<'a, I>
• Footnotes<'a, I>
• Parser<T>

Libstd:

• fs
  • ReadDir (Implement size_hint on various sys iterators #49552)(implement size_hint on sys iterators #71308)
• io
  • Bytes<R> There's no way to do this.
  • Chars<R> There's no way to do this.
  • Split<B> There's no way to do this.
• net
  • Lines<B> Depreciated.
  • Incoming<'a> There's no way to provide anything better than (1, None)
• path
  • Iter<'a> (Implement size_hint on various sys iterators #49552)
  • Components<'a> Writing a size_hint for this is hard. But it would be useful; this is often collect()-ed.
  • Ancestors<'a> Writing a size_hint for this is hard, and not very useful.
• sync
  • Iter<'a, T> Inherently unbounded iterator.
  • TryIter<'a, T> Inherently unbounded iterator.
  • IntoIter<T> Inherently unbounded iterator.
  • Packets Impossible to write an upper bound.
• sys
  • cloudabi
    • ReadDir (Implement size_hint on various sys iterators #49552) (implement size_hint on sys iterators #71308)
    • LookupHost (Implement size_hint on various sys iterators #49552) (implement size_hint on sys iterators #71308)
    • SplitPaths<'a> (Implement size_hint on various sys iterators #49552)(implement size_hint on sys iterators #71308)
  • redox
    • ReadDir (Implement size_hint on various sys iterators #49552)
    • LookupHost (Implement size_hint on various sys iterators #49552)
  • unix
    • ReadDir No cheap way to do this.
    • LookupHost (Implement size_hint on various sys iterators #49552)
  • wasm
    • ReadDir (Implement size_hint on various sys iterators #49552) (implement size_hint on sys iterators #71308)
    • LookupHost (Implement size_hint on various sys iterators #49552) (implement size_hint on sys iterators #71308)
    • SplitPaths<'a> (Implement size_hint on various sys iterators #49552) (implement size_hint on sys iterators #71308)
    • Env (Implement size_hint on various sys iterators #49552) (implement size_hint on sys iterators #71308)
  • windows
    • ReadDir There's no cheap way to do this.
    • Env There's no safe way to do this.
    • SplitPaths<'a> (Implement size_hint on various sys iterators #49552) (implement size_hint on sys iterators #71308)
• sys_common
  • LookupHost There's no safe way to do this.
• unicode
  • ToLowercase (Implement size_hint for several unicode-based iterators. #50208)
  • ToUppercase (Implement size_hint for several unicode-based iterators. #50208)
  • CaseMappingIter (Implement size_hint for several unicode-based iterators. #50208)
  • Utf8LossyChunksIter<'a> (Implement size_hint for several unicode-based iterators. #50208)
  • SplitWhitespace<'a> (Implement size_hint for several unicode-based iterators. #50208)

Libsyntax:

• Frame
• Cursor

Cargo:
rust-lang/cargo#5211

I found them by running grep -r -n "impl.*\bIterator for \|fn size_hint" src > size_hint_todo.txt. Then, delete any pairs of an Iterator line followed by a size_hint line, and manually check the remaining Iterator lines for false positives.

It may be a good idea to make a lint for implementing size_hint. It would be opt-in, of course. It's really easy to forget, even if you're trying to optimize performance.

[KodrAus]

It looks like this one has been idle for a few years with PRs closed (mostly just from inactivity). In an effort to prune our open tracking issues to those with unstable features and those that are in progress I’ll go ahead and close this one, but if anybody from @rust-lang/libs thinks we should keep it open please feel free to re-open!

[Phlosioneer]

I went through several of them. ToLowercase, ToUppercase, and CaseMappingIter are the only ones that are both trivial and possibly useful.

I don't have a local fork of rust setup anymore, but the code should be pretty simple. The PR that I opened #50208 was dropped because I wasn't interested in writing tests, and I wanted to add traits; but the code for those three size_hints alone should be fine. It's ~10 LoC plus tests.

Writing this comment for anyone in the future seeing this issue.