Add ByNeed and Predicate traits

[SimonSapin]

#18424 "Implement collections reform" was closed with one part left not implemented yet:

Tracking issue for rust-lang/rfcs#235, there are a number of sub-issues associated with this:

[...]

Backwards compatible changes that will require additional language features:

• Add ByNeed and Predicate traits (needs negative bounds to work with unboxed closures)

In particular, making Iterator::position generic over a Predicate trait would help replacing [T]::position_elem, which was deprecated in #26914, without the verbosity of .position(|i| i == &x)

CC @alexcrichton, @aturon

[bluss]

This should sync method names with &str and their pattern API if possible IMO, and futher API inspiration from there as well. The substring search algorithm we use does in theory work on all "orderable alphabets".

[Gankra]

To my knowledge ByNeed and Predicate were totally busted and are unimplementable because of mumble mumble something something overlapping implementation stuff. In particular this RFC was merged while closures were known to be Boxed which somehow avoided conflicts. Now unboxed closures exist so everything falls apart.

Not even specialization is supposed to be able to fix this.

This is all vague out-of-cache memory though, @aturon should be able to recall the precise details if pressed.

Something about () -> T being ByNeed<Self> and ByNeed<T>

[aturon]

Yeah, for example, the following fails to compile:

trait Foo<T> {}

impl<T, U> Foo<U> for T where T: Fn(&U) -> bool {}
impl<'a, T> Foo<T> for &'a T {}

and as @gankro mentioned I was hoping specialization would solve it, but doing so requires some crazypants rules.

Still, there are other ways to address this, possibly including getting the compiler to reason more about #[fundamental], adding explicit "low-priority" impls to specialization, or introducing negative bounds.

[aturon]

(To be clear, the reason the example fails to compile is that in principle you could have &T: Fn(&T) -> bool, in which case both impls would apply; specialization as proposed doesn't help because neither impl is strictly more general. But since the relevant types/traits here are marked #[fundamental], some negative reasoning is already permitted, and if we took full advantage might be enough to work around this limitation.)

[alexcrichton]

Lots of time has passed since these were originally designed, so they would likely basically require another RFC to be added today, so closing.