Tracking issue for iter_order_by

[KodrAus]

Landed in #62205

Public API

pub mod core {
    pub mod iter {
        mod traits {
            mod iterator {
                pub trait Iterator {
                    fn cmp_by<I, F>(mut self, other: I, mut cmp: F) -> Ordering
                    where
                        Self: Sized,
                        I: IntoIterator,
                        F: FnMut(Self::Item, I::Item) -> Ordering,
                    {
                    }
                    fn partial_cmp_by<I, F>(
                        mut self,
                        other: I,
                        mut partial_cmp: F,
                    ) -> Option<Ordering>
                    where
                        Self: Sized,
                        I: IntoIterator,
                        F: FnMut(Self::Item, I::Item) -> Option<Ordering>,
                    {
                    }
                    fn eq_by<I, F>(mut self, other: I, mut eq: F) -> bool
                    where
                        Self: Sized,
                        I: IntoIterator,
                        F: FnMut(Self::Item, I::Item) -> bool,
                    {
                    }
                }
            }
        }
    }
}

Before stabilization:

• Stabilization PR

Open questions

• Should we use size_hint as an optimization for equality checking? That means buggy iterators may return incorrect results for eq_by. We could optimize for just a handful of TrustedLen iterators instead.

[KodrAus]

A comment was made on Twitter about whether or not this should be able to use size_hint to determine whether or not the iterators have any chance of containing equal elements.

size_hint can't be relied upon for safety, but it seems like it could be reasonable to use it for short-circuiting eq_by.

[yoshuawuyts]

An example usage of this is in rust-analyzer where it's part of its internal stdx crate which contains stdlib extensions.

[chrysn]

TrustedLen is an unsafe trait, which I understand is there to catch cases when wrong lengths would result in soundness holes. The size hint is a bit more than a hint -- an iterator that does not adhere to the bounds is considered buggy by size_hint's documentation. I'd place returning false to eq_by on an erroneous iterator in a similar category as a run-time integer overflow that is not caught because the wrong index is not a soundness violation (just a follow-up program error from a previous program error).

Is that the only contested point about this interface? If not, what is needed to move this toward stabilization? (If it's user reports: it simplifies code in coap-handler-implementations quite a bit).

[Hiten-Tandon]

Function should be renamed to related_by, because, in the function we're not checking for equality, rather we're checking for relation between the values of the two iterators.

[orlp]

So is there any progress on this? What's blocking stabilization?

Regarding the size hint being used, that's currently not being done for the already stable Iterator::eq. I think there are really only two paths forward:

1. Don't check the size hint.
2. Check the size hint in all Iterator PartialEq-related methods. This means deciding it's not considered a breaking change to start doing this for Iterator::eq.

I really don't think there is ever a viable future for having some of the methods check the size hint and others do not, so I really believe the two above choices are the only ones. It's just too much of a footgun.

However regardless of which of these two choices you make, Iterator::eq_by's stabilization is not blocked by it. In scenario 1 the current implementation is fine. In scenario 2 you've already decided it's not a breaking change so it can be stabilized.

[leb-kuchen]

I think the question should be TrustedLen or ExaxtSizeIterator. ExaxtSizeIterator is also user implemented, but is supposed to be exact and not only a hint.