The implementation of `InPlaceIterable` for `Flatten`&`FlatMap` is unsound

[steffahn]

const S: String = String::new();
fn main() {
    let v = vec![[S, "Hello World!".into()], [S, S]];
    let mut i = v.into_iter().flatten();
    let _ = i.next();
    let result: Vec<String> = i.clone().collect();
    println!("{result:?}");
}

(playground)

["\0\0\0\0\0\0\0\0rld!", "\0\0\0\0\0\0\0\0rld!", ""]
free(): invalid pointer
[1]    1131073 IOT instruction (core dumped)

The above code is analogous to #85322 but applied to Flatten instead of Peekable: cloning the whole iterator doesn't preserve capacity in the inner vec::IntoIter. (This also applies to FlatMap.)

Introduced in 1.76

cc @the8472, #110353

@rustbot label T-libs, I-unsound, A-iterators

[the8472]

Oof... looks like I didn't learn from #85322 :(
I can prepare a backportable PR that disables the specialization for flatten/flatmap without ripping out all the changes and then do more cleanup afterwards if I can't figure out a way to recover this... it'd likely require cloning the full capacity or extending the clone interface somehow...

Edit: PR at #135104

[steffahn]

Right… either change something about the clone; or add some way to detect the after-clone state.

---

I'm thinking the latter might be quite approachable. If there's a method added to … InPlaceIterable I suppose … that asks “do you have extra elements outside of the underlying vec::IntoIter?” The most common case of wanting the in-place behavior if the consumption of the iterator starts on a freshly constructed stack of iterators would be fully covered.

So that's one method like

/// Conservaticely returns true whenever the iterator *may* contain extra items on the side
/// E.g. if the peeked element is `Some` in `Peekable`,
/// or either `frontiter` or `backiter` is `Some` for `Flatten`/`FlatMap`
fn has_extra_items(&self) -> bool

E.g. as an easy first extra step, there can be a const (or specialization marker?¹) that says

/// For optimization, `true`, if `has_extra_items` *never* returns `true`
const NEVER_HAS_EXTRA_ITEMS: bool;

---

One can potentially get successively even more precise later… e.g. we consider if it's worth adding an additional field to Peekable and Flatten/FlatMap that tracks whether or not the local “extra items” are truly “potentially additional items”. The Clone impl would ensure to set this field to “yes, they are potentially additional items” in the clone (unless the value being cloned contained only None-valued extra-item-carrying fields [peeked, frontiter, backiter]]); but the normal constructor via .peekable() or .flatten() etc… would always be able to set these fields to (false) (and the relevant fields are None anyway).

Footnotes

1. what exactly is better about those? IMHO the whole of in-place-iteration could be reduced town entirely to const items that are part of Iterator anyway… we don't need any specialization for this at all; this could also achieve an "or" logic for determining a source in Zip ↩

[the8472]

I'm thinking the latter might be quite approachable.

Hrrm, you mean with fallback to the default collect implementation? Yeah, that would work but I'm concerned that it'd lead to code bloat. Currently the path is chosen at compile time, a runtime fallback would require both paths to exist.

I'm thinking about specializing clone calls to pass down an upper bound of how many empty slots it'd have to preserve (if any), similar to the EXPAND_BY tracking. But if that gets too hairy then collect fallback may be the better choice.

IMHO the whole of in-place-iteration could be reduced town entirely to const items that are part of Interator anyway…

That could work for InPlaceIterable but we'd still need SourceIter and idk how we could select that at constant time? Offsets and field accesses maybe, but that'd be wildly unsafe.

[steffahn]

Yeah, that would work but I'm concerned that it'd lead to code bloat. Currently the path is chosen at compile time, a runtime fallback would require both paths to exist.

I guess that's a valid concern.

That could work for InPlaceIterable but we'd still need SourceIter and idk how we could select that at constant time?

Something like a const containing an Option<fn(&mut Self) -> &mut Source>; but I don't know how well that works with codegen and stuff…

[the8472]

Not certain, but it might work.
Currently the SourceIter trait is designed to support other in-place-collect impls by having different associated Source types, e.g. we could have a separate one for VecDeque sources that'd put in some extra work for rearranging the items or even one for reusing the HashSet allocation. But that flexibility is unused so for constification it could be stripped out.

[steffahn]

Looks like const might be a problem with dyn-safety.

[the8472]

And doing it through a helper trait runs into the issue that it'll require a blanket impl and then specializing that, which requires full specialization for const items, not min_specialization.