# Iterator Namepocalypse

*Itertools* is a Rust crate that extends Rust's `Iterator`s with more than 100 additional methods. The crate is both one of Rust's oldest (in development since Jul 28, 2014), most depended upon (~4,300 direct dependants), and most downloaded (115+ million downloads).

The Itertools mission is two-fold:
- to make the experience of working with iterators more pleasant
- to serve as a laboratory for future improvements to Rust's standard library `Iterator` trait

This document addresses a persistent name-conflict issue between Itertools and the Rust standard library that undermines this mission.

## Technical Context
The Itertools crate implements the *extension trait* design pattern. In this pattern, a library-defined trait is used to add additional methods to third-party code.

Concretely, Itertools extends the `Iterator` trait defined by the Rust standard library:

/* in `std::iter` */

trait Iterator {
    type Item;

    fn next(&mut self) -> Option<Self::Item>;
    
    /* additional methods */
}

It does so by defining a trait called `Itertools` that extends `Iterator` and is implemented for all types implementing `Iterator`:

/* in `itertools` */

// `Itertools` extends `Iterator`
trait Itertools: Iterator {
    // And provides methods, like `flatten`, that are
    // not available on `Iterator.
    fn flatten(self) -> Flatten<Self> ⓘ
    where
        Self: Sized,
        Self::Item: IntoIterator
    {
        /* ... */
    }
}

// These methods are made available by providing a
// blanket-implementation of `Itertools` for all things
// that implement `Iterator`.
impl Itertools for I
where
    I: Iterator
{}

### Fatal Flaw
The trait extension pattern used by Itertools falters if any other applicable traits define the same methods. For instance, if `Iterator` were to *also* define a `flatten` method, Rust would begin to produce compilation errors at all `.flatten()` call-sites.

## Historical Context

In 2018, [a PR was opened](https://github.com/rust-lang/rust/pull/48115) on rust-lang/rust to promote `Itertools::flatten` into the standard library's `Iterator` trait. Upon release, this (unstable) change caused rustc to produce a compilation error at all existing callsites of `.flatten()`.

Three counter measures were adopted, and by the time `flatten` was stabilized, [only 11 crates](https://github.com/rust-lang/rust/pull/51511#issuecomment-397239344) were broken directly by the addition (and 26 crates, transitively).

#### Resolve unstable methods with lower priority and warn about future incompatibility.
Rust [was modified](https://github.com/rust-lang/rust/pull/48552) to depriotitize and warn (rather than error) in cases where the conflicting method is unstable.

This change creates a buffer period in which customers (provided that they are using an up-to-date Rust) receive a warning that breakage is impending.

#### Add free-function alternatives to `Itertools` methods.
Itertools began to add 'free' function alternatives to its methods. Concerned or affected users are encouraged to use these functions instead of `Itertools` method calls, since these functions are unaffected by naming conflicts. These functions are generally less ergonomic than their method counterparts.

#### Discourage potentially-conflicting new contributions to `Itertools`.
Itertools adopted a policy of discouraging new contributions that could conflict with future additions to `Iterator`.

## Naming Conflicts Continue
In 2020, [a PR was opened](https://github.com/rust-lang/rust/pull/79479) on rust-lang/rust to promote `Itertools::intersperse` into the standard library's `Iterator` trait.

This PR was merged and stabilized without substantial consideration of the breakage it could cause. The stabilization was reverted [upon discovery](https://github.com/rust-lang/rust/issues/88967) that it broke 59 direct (and 538 indirect) dependents of Itertools.

Although this kind of breakage is expressly allowed by Rust's compatibility guarantees, the Rust Library Team takes, in practice, a more conservative position and tries to avoid breakage whenever possible. The stabilization of `intersperse` remains incomplete.

## Corrective Action
The persistent risk of naming conflicts between `Iterator` and `Itertools` undermines the maintenance of both of these projects; e.g.:
- The Rust Library Team is unable to stabilize much-desired features in `Iterator` for fear of causing widespread breakage.
- The Itertools Team is unable to accept new useful contributions that could, plausibly, become future additions to `Iterator`.

### Rust: Supertrait Item Shadowing
[*RFC2845: Supertrait Item Shadowing*](https://github.com/rust-lang/rfcs/pull/2845) proposes altering Rust's method resolution to (mostly) eliminate this class of compiler errors. Specifically, Rust would instead treat same-named items in sub-traits as 'shadowing' their counterparts in super-traits. This RFC was accepted in September 2021, but has not yet been implemented.

If implemented, the Rust Library Team could freely promote items from `Itertools` into `Iterator` without causing breakage.

There would remain some risk that users would get 'stuck' on the sub-optimal implementations provideded by `Itertools` (since standard library iterator adapters can make optimizations that crates cannot), but Itertools would mitigate this by periodically removing items that have been promoted into the standard library.

### Itertools: Rename Methods
Itertools could prefix its methods with `it_`, making future conflicts with `Iterator` far less likely. This approach could be readily implemented by `Itertools`, but would cause a brief period of breakage (or, at least, myriad compiler warnings) for *all* users of Itertools.

## Next Steps
RFC2845 has every advantage over *Rename Methods*, except that it would surely take longer to release. However, given its advantages (namley: no breakage for itertools users), we should at least investigate implementing it. I asked Michael Goulet (@compiler-errors) for his impression on feasibility: A few (probably amendable) corner cases aside, he believes it would not be too difficult to implement.

If it proves to be too difficult, we can always *Rename Methods*.