ACP: Implement `TryFromIterator<T>` trait to compliment `FromIterator<T>` trait.

[stifskere]

Proposal

Problem statement

I want to compliment the FromIterator<T> trait with a TryFromIterator<T> trait as that would basically be a fallible alternative to FromIterator<T>, it would be the same but the trait would have an Error field and the function would return a Result<R, Self::Error>.

Motivating examples or use cases

A use case I recently had was this one, basically the use cases for his would be making iterator implementations safer.

Solution sketch

My solution for this ACP is basically this one

pub trait TryFromIterator<T>: Sized {
    type Error;

    fn try_from_iter<I: IntoIterator<Item = T>>(iter: I) -> Result<Self, Self::Error>;
}

Or something similar

Alternatives

Probably making this a crate in crates.io doesn't make much sense, the alternatives to this is implementing it per project.

Links and related work

This thread literally solves the problem.

What happens now?

This issue contains an API change proposal (or ACP) and is part of the libs-api team feature lifecycle. Once this issue is filed, the libs-api team will review open proposals as capability becomes available. Current response times do not have a clear estimate, but may be up to several months.

Possible responses

The libs team may respond in various different ways. First, the team will consider the problem (this doesn't require any concrete solution or alternatives to have been proposed):

• We think this problem seems worth solving, and the standard library might be the right place to solve it.
• We think that this probably doesn't belong in the standard library.

Second, if there's a concrete solution:

• We think this specific solution looks roughly right, approved, you or someone else should implement this. (Further review will still happen on the subsequent implementation PR.)
• We're not sure this is the right solution, and the alternatives or other materials don't give us enough information to be sure about that. Here are some questions we have that aren't answered, or rough ideas about alternatives we'd want to see discussed.

[programmerjake]

There could probably be a blanket impl which allows you to use iter_of_results.try_collect()?:

impl<T, E, S> TryFromIterator<Result<T, E>> for S
where
    S: TryFromIterator<T>,
    E: From<<S as TryFromIterator<T>>::Error>,
{
    type Error = E;

    fn try_from_iter<I: IntoIterator<Item = T>>(iter: I) -> Result<Self, Self::Error> {
        let mut err = None;
        let retval = <S as TryFromIterator<T>>::try_from_iter(iter.into_iter().map_while(|v| match v {
            Ok(v) => Some(v),
            Err(e) => {
                err = Some(e);
                None
            },
        }).fuse());
        if let Some(err) = err {
            return Err(err);
        }
        Ok(retval?)
    }
}

[joboet]

What is the advantage of this when compared to the existing Iterator::try_collect?

[programmerjake]

What is the advantage of this when compared to the existing Iterator::try_collect?

I think the general idea is you can implement TryFromIterator for arrays, but not really using the existing Iterator::try_collect since that still uses FromIterator which can't directly report errors such as not enough items to fill the array.

[stifskere]

What is the advantage of this when compared to the existing Iterator::try_collect?

I was thinking of clearer semantics, because while it is right that an implementation can already be done with the existing constructs but I feel it's more direct and is also probably more consistent, as you have FromIterator, if you have a group of collections that implement that for whatever reason, and one or many need to implement that in a fallible way it would be more consistent to have a TryFromIterator

[stifskere]

What is the advantage of this when compared to the existing Iterator::try_collect?

I think the general idea is you can implement TryFromIterator for arrays, but not really using the existing Iterator::try_collect since that still uses FromIterator which can't directly report errors such as not enough items to fill the array.

The whole idea is implementing some sort of fallible alternative in the std directly, some use cases as you mentioned the array size check, or probably the fact you wouldn't want a specific item or want to have some sort of check like whether a number is a valid coordinate to something, since FromIterator implies generating an object from an iterator, I find being able to do checks like that is necessary, or rather useful.

[traviscross]

T-libs-api discussed this today and was not sure that the use cases mentioned so far were compelling enough. The team wanted to see a more comprehensive write-up that discusses at least the possible uses of this for fallible allocation and collecting into a fixed size array. In particular, the team wanted to hear about any real use cases for these.

The team was also interested to hear about whether there was any part of the use case not covered by try_fold.

[stifskere]

Hello, sorry for answering late, I'm moving from my house to another house.

The difference between try_fold and TryFromIterator<T> would be mutability, try_fold requires the structure to be mutable, while TryFromIterator<T> doesn't. Basically this way a fallible FromIterator could be implemented without external mutability from the user or anything else, only the structure controls what is collected and how, not the user of the structure.

If some sort of log about that discussion could be shared, I could try and provide more details, thanks in advance.

[traviscross]

Thanks @stifskere for that. In looking at the minutes, there is unfortunately no more context from that discussion to share. The summary above is what people wanted to hear about this.

You've answered the bit about the difference between this and try_fold. Probably people will still want to hear more about the other things, if possible:

The team wanted to see a more comprehensive write-up that discusses at least the possible uses of this for fallible allocation and collecting into a fixed size array. In particular, the team wanted to hear about any real use cases for these.

[programmerjake]

one example of why it'd be nice to have collecting arrays from iterators -- when you want a chain of transforms applied to arrays and want functional syntax, but don't want any temporary arrays:

fn zip3_map<'a, 'b, 'c, A, B, C, R, const: N: usize>
    a: &'a [A; N],
    b: &'b [B; N],
    c: &'c [C; N],
    mut f: impl FnMut(&'a A, &'b B, &'c C) -> R
) -> Box<[R; N]> {
    // TryFromIterator makes this nice to implement:
    a.iter().zip(b).zip(c).map(|((a, b), c)| f(a, b, c)).try_collect().expect("unreachable")
}

[programmerjake]

another example for something I've actually encountered:

// simplified somewhat

// a path `::my_crate::m::MyType` or `MyType`
pub struct ParsedMyTypePath(syn::Path);

// a parsed `MyType<AType, BType, CType>`
pub struct ParsedMyType {
    pub my_type: ParsedMyTypePath,
    pub lt_token: Token![<],
    pub a: Box<ParsedType>,
    pub comma_token: Token![,],
    pub b: Box<ParsedType>,
    pub comma_token2: Token![,],
    pub c: Box<ParsedType>,
    pub gt_token: Token![>],
}

impl ParsedMyType {
    pub fn parse_from_path(path: syn::Path) -> syn::Result<Self> {
        let (my_type, args) = ParsedMyTypePath::parse_path_with_args(path)?;
        let syn::AngleBracketedGenericArguments {
            colon2_token: _,
            lt_token,
            args,
            gt_token,
        } = args;
        let [(a, comma_token), (b, comma_token2), (c, _)] = args.into_pairs().map(|p| {
            let (arg, punct) = p.into_tuple();
            Ok((Box::new(ParsedType::parse_arg(arg)?), punct.unwrap_or_default()))
        }).try_collect::<syn::Result<[_; 3]>>()??;
        Ok(Self {
            my_type,
            lt_token,
            a,
            comma_token,
            b,
            comma_token2,
            c,
            gt_token,
        })
    }
}

[scottmcm]

when you want a chain of transforms applied to arrays

That wants some form of combinators separated from iterators, though. When it's arrays, you don't want that .expect on the end.

There's a sketch in https://internals.rust-lang.org/t/should-there-by-an-array-zip-method/21611/8?u=scottmcm of what that might look like, which personally I think would be cool to explore.

It'd be neat to be able to build up the transformation pipeline once, then re-invoke that on arrays, vecs, iterators, whatever, subject to the constraints of the operations needed by the specific pipeline. (For example, replace the magic "well that happens to be in-place" for Vec with something that guarantees it for a specific trait bound on a transformation pipeline.)

[scottmcm]

Also, if the use-case is for collecting into arrays, I continue to think that's the wrong abstraction since there's too many error cases to think about and define semantics for. Something like Iterator::next_chunk is much clearer about what's happening around the edge cases, as is collecting into an ArrayVec, since both those cases make "too short" no longer an error case.

[stifskere]

Thanks @stifskere for that. In looking at the minutes, there is unfortunately no more context from that discussion to share. The summary above is what people wanted to hear about this.

You've answered the bit about the difference between this and try_fold. Probably people will still want to hear more about the other things, if possible:

The team wanted to see a more comprehensive write-up that discusses at least the possible uses of this for fallible allocation and collecting into a fixed size array. In particular, the team wanted to hear about any real use cases for these.

I was thinking about these possible use cases

Real time systems

When there is a process that keeps allocating collections in a fallible manner, for example "keep introducing documents" and in real time it keeps processing and allocating the data in multiple collections for whatever that document is doing, but to parse the document we need fallibility in case the document is invalid.

Large batch processing

When the size of what is going to be processed/allocated is not known, but we know it's going to be big we may fail if there is not enough memory to process that, this case would probably be more applicable to server applications or those with many users.

Streaming APIs

Allocating the content for the user to watch when consuming a streaming API for example if we need to validate what a specific frame does have, or we need to comply some sort of copyright protocol that asks us to do something that could succeed or fail in compliance of the rules, or if there was a connection error. Which is a more common issue, then we could fail for incomplete data or whatever the case would be. Even tho in any case this would be handled in another part of the program (or not).

Buffer management / Fixed size allocation

In this case, we would want to know the size of what is being allocated, probably if the size that gets passed to the function, which is probably from a dynamic collection into the buffer static size collection for any reason. We could fail if the size doesn't match for some reason, then we can simply fail that.