Flattening a nested iterator of results

Does anyone have suggestions on an elegant and easy way to flatten an iterator of result of iterator of result into an iterator of result? I would love to be able to do this using the standard library or itertools without implementing my own Iterator. Since I’m planning to use this with Result::from_iter, it’s fine if the solution stops as soon as it hits the first error.

pub fn flatten_nested_results<T, E>(
    i: impl Iterator<Item = Result<impl Iterator<Item = Result<T, E>>, E>>,
) -> impl Iterator<Item = Result<T, E>> {
    unimplemented!()
}

#[test]
fn test_all_ok() {
    let i = vec![Ok(vec![Ok(1), Ok(2)]), Ok(vec![Ok(3), Ok(4)])]
        .into_iter()
        .map(|x| x.map(Vec::into_iter));
    let expected: Result<Vec<u8>, u8> = Ok(vec![1, 2, 3, 4]);
    assert_eq!(expected, flatten_nested_results(i).collect())
}

#[test]
fn test_inner_err() {
    let i = vec![Ok(vec![Ok(1), Err(2)]), Ok(vec![Ok(3), Err(4)])]
        .into_iter()
        .map(|x| x.map(Vec::into_iter));
    let expected: Result<Vec<u8>, u8> = Err(2);
    assert_eq!(expected, flatten_nested_results(i).collect())
}

#[test]
fn test_outer_err() {
    let i = vec![Err(8), Err(9)]
        .into_iter()
        .map(|x| x.map(Vec::into_iter));
    let expected: Result<Vec<u8>, u8> = Err(8);
    assert_eq!(expected, flatten_nested_results(i).collect())
}

#[test]
fn test_inner_err_before_outer() {
    let i = vec![Ok(vec![Ok(1), Err(2)]), Err(9)]
        .into_iter()
        .map(|x| x.map(Vec::into_iter));
    let expected: Result<Vec<u8>, u8> = Err(2);
    assert_eq!(expected, flatten_nested_results(i).collect())
}

So far, the closest that I’ve gotten is below. Unfortunately, this results in a match arm with an incompatible type compilation error because I’m trying to return a different type of iterator from each of the two arms of the match statement. Although both returned types do satisfy impl Iterator<Item = Result<T, E>>, they are not the same concrete type.

pub fn flatten_nested_results<T, E>(
    i: impl Iterator<Item = Result<impl Iterator<Item = Result<T, E>>, E>>,
) -> impl Iterator<Item = Result<T, E>> {
    i.flat_map(|iter_inner_result| match iter_inner_result {
        Ok(iter_inner) => iter_inner,
        Err(err) => vec![Err(err)].into_iter()
    })
}

I figured out a solution using the either crate, which is a dependency of itertools. Actually, currently it’s the only dependency of itertools. This solution works because Either<L, R> is an iterator if both L and R are iterators with the same Item type.

I’m pretty happy with this, but if anyone has alternative solutions, I’d be happy to hear them too!

pub fn flatten_nested_results<T, E>(
    i: impl Iterator<Item = Result<impl Iterator<Item = Result<T, E>>, E>>,
) -> impl Iterator<Item = Result<T, E>> {
    i.flat_map(|iter_inner_result| match iter_inner_result {
        Ok(iter_inner) => Either::Left(iter_inner),
        Err(err) => Either::Right(vec![Err(err)].into_iter())
    })
}

I think you can just use std::iter::once(Err(err)) here, and save a Vec allocation.

Alas, std::iter::Iterator::next() returns Option<> rather than Result<>. Although this makes iterators simpler to learn for the beginner, flattening a fallible iterator (one that returns a Result<>) is not intuitive. Many strategies have been employed to rectify this including a fallible iterators crate, but each has its disadvantages.

At the moment, my preferred strategy is to use the iterr crate. Its lift_err iterator adapter is quite portable in the sense that it does not break compatibility with standard rust iterators as many other strategies do. The crate itself is a lightweight dependency with minimal size/complexity. I've written an example below demonstrating how to flatten a vector of file-path-matching glob patterns. The example may seem long, but the flattening bit is actually achieved in just 1-2 lines with a lot of surrounding comments.

Refer to the documentation for lift_err for a more detailed explanation of how this iterator adapter works. You could also choose to use trap_err.

use iterr::ItErr;

// Shorthand for Result using cumbersome dyn Error trait object.
pub type TryResult<T> = std::result::Result<
	T,
	std::boxed::Box< dyn
		std::error::Error   // must implement Error to satisfy Try
		+ std::marker::Send // needed to move errors between threads
		+ std::marker::Sync // needed to move errors between threads
	>
>;

fn main() -> TryResult<()> {
	// Some example globs to worth with.
	// /home/*/* is valid
	// /root/* generates a GlobError because access to /root is denied
	// *** generates a PatternError because it is not a valid pattern
	let globs = vec!["/home/*/*", "/root/*", "***"];
	
	// Strategy 1: Use statically-typed errors.
	// Advantage: No overhead of trait objects.
	globs
		// Works with iter() or into_iter().
		.iter()
		
		// Map each &str to a Result<glob::Paths, glob::PatternError>.
		.map(|pattern| glob::glob(pattern))
		
		// Lift the Paths out of the Result<Paths, PatternError>.
		// Then flatten over all paths.
		// We need an additional map to wrap each Result<std::path::PathBuf, glob::GlobError>
		// into a Result<Result<std::path::PathBuf, glob::GlobError>, glob::PatternError>,
		// which is the type that lift_err expects.
		.lift_err(|paths| paths.flatten().map(|path| Ok::<_, glob::PatternError>(path)))
		
		// The innermost loop will iterate over each path generated by all the patterns in globs.
		// Iteration will terminate early on the first error.
		.try_for_each(|path| -> TryResult<()> {
			// We must use the ? operator twice,
			// first to unwrap the Result<Result<std::path::PathBuf, glob::GlobError>, glob::PatternError>,
			// then to unwrap the Result<std::path::PathBuf, glob::GlobError>.
			println!("{:?}", path??);
			Ok(())
		})?;
	
	// Strategy 2: Use a trait object for the errors.
	// Advantage: Errors are also flattened, so we just need one ? operator.
	globs
		// Works with iter() or into_iter().
		.into_iter()
		
		// Map each &str to a Result<glob::Paths, glob::PatternError>
		// using the type hint `-> TryResult<_>` and a combination of Ok with operator ?
		// to convert the glob::PatternError to a dyn Error,
		// getting out a Result<glob::Paths, dyn Error>.
		.map(|pattern| -> TryResult<_> { Ok(glob::glob(pattern)?) })
		
		// Lift the Paths out of the Result<Paths, dyn Error>.
		// Then flatten over all paths.
		// We again use the type hint `-> TryResult<_>` with Ok and operator ?
		// this time to convert glob::GlobError to dyn Error.
		// Because this is the same error type lift_err is expecting,
		// we can flatten Result<Result<>> from Strategy 1
		// into Result<std::path::PathBuf, dyn Error>.
		.lift_err(|paths| paths.flatten().map(|path| -> TryResult<_> { Ok(path?) }))
		
		// The innermost loop will iterate over each path generated by all the patterns in globs.
		// Iteration will terminate early on the first error.
		.try_for_each(|path| -> TryResult<()> {
			// The type of path is Result<std::path::PathBuf, dyn Error>
			// therefore we need only use the ? operator once.
			println!("{:?}", path?);
			Ok(())
		})?;
	
	// Return success.
	return Ok(());
}