nom::branch::alt handles at most 21 parsers

[luca-i]

Hi, I'm not sure this is a bug, maybe it is a current limitation not documented.
I think nom::branch::alt can currently handle only 21 parsers.

rustc 1.42.0 (b8cedc004 2020-03-09)
nom = "5.1.1"

use nom::branch::alt;
use nom::bytes::complete::tag;
use nom::IResult;

fn match_alternatives(input: &str) -> IResult<&str, &str> {
    alt((
        tag("alternative_01"),
        tag("alternative_02"),
        tag("alternative_03"),
        tag("alternative_04"),
        tag("alternative_05"),
        tag("alternative_06"),
        tag("alternative_07"),
        tag("alternative_08"),
        tag("alternative_09"),
        tag("alternative_10"),
        tag("alternative_11"),
        tag("alternative_12"),
        tag("alternative_13"),
        tag("alternative_14"),
        tag("alternative_15"),
        tag("alternative_16"),
        tag("alternative_17"),
        tag("alternative_18"),
        tag("alternative_19"),
        tag("alternative_20"),
        tag("alternative_21"),
        // tag("alternative_22"), // uncomment to get compiler error
    ))(input)
}

fn main() {}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_alternatives() {
        assert_eq!(
            match_alternatives("alternative_21"),
            IResult::Ok(("", "alternative_21"))
        );

        // to match "alternative_22" you must uncomment the
        // appropriate tag inside match_alternative, but at that moment
        // the code won't compile any more
        assert_eq!(
            match_alternatives("alternative_22"),
            IResult::Ok(("", "alternative_22"))
        );
    }
}

In order to get the compiler error you have to uncomment the following line inside match_alternatives function:

// tag("alternative_22"), // uncomment to get compiler error

The error message to me is a bit unclear:

^ the trait nom::branch::Alt<_, _, _> is not implemented for (impl std::ops::Fn<(_,)>, impl std::ops::Fn<(_,)>, impl std::ops::Fn<(_,)>, impl std::ops::Fn<(_,)>, impl std::ops::Fn<(_,)>, impl std::ops::Fn<(_,)>, impl std::ops::Fn<(_,)>, impl std::ops::Fn<(_,)>, impl std::ops::Fn<(_,)>, impl std::ops::Fn<(_,)>, impl std::ops::Fn<(_,)>, impl std::ops::Fn<(_,)>, impl std::ops::Fn<(_,)>, impl std::ops::Fn<(_,)>, impl std::ops::Fn<(_,)>, impl std::ops::Fn<(_,)>, impl std::ops::Fn<(_,)>, impl std::ops::Fn<(_,)>, impl std::ops::Fn<(_,)>, impl std::ops::Fn<(_,)>, impl std::ops::Fn<(_,)>, impl std::ops::Fn<(_,)>)

Is there a way to overcome this limitation?
Thank you, Luca-

[snylonue]

The trait nom::alt::Alt is not implement for tuples with over 21 items. This is a limitation in rust.
You can probably implement it for your custom type to support more parsers

By the way, I think it will be useful that alt supports collection types like slice and vec.

[parasyte]

Workaround: You can nest alt combinators arbitrarily deep. Your test will pass with this:

fn match_alternatives(input: &str) -> IResult<&str, &str> {
    alt((
        alt((
            tag("alternative_01"),
            tag("alternative_02"),
            tag("alternative_03"),
            tag("alternative_04"),
            tag("alternative_05"),
            tag("alternative_06"),
            tag("alternative_07"),
            tag("alternative_08"),
            tag("alternative_09"),
            tag("alternative_10"),
            tag("alternative_11"),
            tag("alternative_12"),
            tag("alternative_13"),
            tag("alternative_14"),
            tag("alternative_15"),
            tag("alternative_16"),
            tag("alternative_17"),
            tag("alternative_18"),
            tag("alternative_19"),
            tag("alternative_20"),
            tag("alternative_21"),
        )),
        alt((
            tag("alternative_22"),
            tag("alternative_23"),
            tag("alternative_24"),
            tag("alternative_25"),
            tag("alternative_26"),
            tag("alternative_27"),
        )),
    ))(input)
}

[luca-i]

Workaround: You can nest alt combinators arbitrarily deep.

Thank you for your answer. You are right, I wonder if the generated code is as efficient as if alt was able to accept tuples of any length (I wonder if given the text alternative_22 it matches alternative_2 that is common among the first and the second alt and then 2 without having to match again alternative_2 when the first alt fails).

[luca-i]

The trait nom::alt::Alt is not implement for tuples with over 21 items. This is a limitation in rust.

Thank you for your explanation, I looked at the implementation in the source code and, for what I can understand, the problem is that the source code must provide an implementation for every tuple length. I wonder if the 21 limit is somewhat a limitation of Rust or if providing a new implementation for a tuple of 22 elements could solve the problem.

[Geal]

@luca-i having more or less branches in alt compared to nesting is not likely to change performance much. I just had to find an arbitrary limit and stick to it (in libstd, they limit PartialEq implementation to tuples of 12 elements max). For cases like yours nesting should be fine.
It might be good to track rust-lang/rfcs#1935 and rust-lang/rfcs#376 though

[kdheepak]

I'm getting the same error for tuple too:

error[E0277]: the trait bound `(impl FnMut(&str)-> Result<(&str, usize), nom::Err<nom::error::Error<&str>>>, impl FnMut(&str)-> Result<(&str, f64), nom::Err<nom::error::Error<&str>>>, impl FnMut(&str)-> Result<(&str, f64), nom::Err<nom::error::Error<&str>>>, impl FnMut(&str)-> Result<(&str, f64), nom::Err<nom::error::Error<&str>>>, impl FnMut(&str)-> Result<(&str, f64), nom::Err<nom::error::Error<&str>>>, impl FnMut(&str)-> Result<(&str, f64), nom::Err<nom::error::Error<&str>>>, impl FnMut(&str)-> Result<(&str, f64), nom::Err<nom::error::Error<&str>>>, impl FnMut(&str)-> Result<(&str, usize), nom::Err<nom::error::Error<&str>>>, impl FnMut(&str)-> Result<(&str, f64), nom::Err<nom::error::Error<&str>>>, impl FnMut(&str)-> Result<(&str, f64), nom::Err<nom::error::Error<&str>>>, impl FnMut(&str)-> Result<(&str, f64), nom::Err<nom::error::Error<&str>>>, impl FnMut(&str)-> Result<(&str, f64), nom::Err<nom::error::Error<&str>>>, impl FnMut(&str)-> Result<(&str, f64), nom::Err<nom::error::Error<&str>>>, impl FnMut(&str)-> Result<(&str, f64), nom::Err<nom::error::Error<&str>>>, impl FnMut(&str)-> Result<(&str, f64), nom::Err<nom::error::Error<&str>>>, impl FnMut(&str)-> Result<(&str, f64), nom::Err<nom::error::Error<&str>>>, impl FnMut(&str)-> Result<(&str, f64), nom::Err<nom::error::Error<&str>>>, impl FnMut(&str)-> Result<(&str, f64), nom::Err<nom::error::Error<&str>>>, impl FnMut(&str)-> Result<(&str, f64), nom::Err<nom::error::Error<&str>>>, impl FnMut(&str)-> Result<(&str, f64), nom::Err<nom::error::Error<&str>>>, impl FnMut(&str)-> Result<(&str, f64), nom::Err<nom::error::Error<&str>>>, impl FnMut(&str)-> Result<(&str, std::option::Option<f64>), nom::Err<nom::error::Error<&str>>>, impl FnMut(&str)-> Result<(&str, std::option::Option<f64>), nom::Err<nom::error::Error<&str>>>, impl FnMut(&str)-> Result<(&str, std::option::Option<f64>), nom::Err<nom::error::Error<&str>>>, impl FnMut(&str)-> Result<(&str, std::option::Option<f64>), nom::Err<nom::error::Error<&str>>>): Tuple<_, _, _>` is not satisfied
   --> src/case.rs:251:22
    |
251 |     let parser = tuple((
    |  ________________-----_^
    | |                |
    | |                required by a bound introduced by this call

If I remove the 22nd element in the tuple I don't get an error

I don't see that written in the documentation though? I'm new to nom, is the recommended approach here to implement a trait?