What are the differences between `nom::branch::alt` and `nom::branch::permutation` for parsing alternatives?

nom::branch::alt implements ordered choice: it tries each parser in sequence and returns the result of the first successful match, failing only when all alternatives fail. nom::branch::permutation applies all parsers exactly once in any order, succeeding when every parser matches and returning a tuple of all results. The fundamental difference is that alt is "one of these must succeed" while permutation is "all of these must succeed, in any order." Use alt for mutually exclusive alternatives like different literal tokens or keyword variations. Use permutation for unordered collections of required elements like command-line flags that can appear in any sequence.

Basic alt Behavior

use nom::branch::alt;
use nom::bytes::complete::tag;
use nom::IResult;
 
fn parse_color(input: &str) -> IResult<&str, &str> {
    // Try each parser in order, return first success
    alt((
        tag("red"),
        tag("green"),
        tag("blue"),
    ))(input)
}
 
fn main() {
    // Matches first successful alternative
    assert_eq!(parse_color("red"), Ok(("", "red")));
    assert_eq!(parse_color("green"), Ok(("", "green")));
    assert_eq!(parse_color("blue"), Ok(("", "blue")));
    
    // Order matters - "red" matches before "green" could
    assert_eq!(parse_color("greenish"), Ok(("ish", "green")));
    
    // Fails if no alternative matches
    assert!(parse_color("yellow").is_err());
}

alt returns the first successful result among alternatives.

Basic permutation Behavior

use nom::branch::permutation;
use nom::bytes::complete::tag;
use nom::IResult;
 
fn parse_pair(input: &str) -> IResult<&str, (&str, &str)> {
    // All parsers must match exactly once, in any order
    permutation((
        tag("a"),
        tag("b"),
    ))(input)
}
 
fn main() {
    // Order in input doesn't matter
    assert_eq!(parse_pair("ab"), Ok(("", ("a", "b"))));
    assert_eq!(parse_pair("ba"), Ok(("", ("b", "a"))));
    
    // Result is always in parser definition order
    let (remaining, (first, second)) = parse_pair("ba").unwrap();
    assert_eq!(first, "b");   // Was tag("a") - matched "b" at position 0
    assert_eq!(second, "a");  // Was tag("b") - matched "a" at position 1
    
    // Fails if any parser doesn't match
    assert!(parse_pair("ac").is_err());  // "b" not found
    assert!(parse_pair("aa").is_err());  // Each parser must match exactly once
}

permutation requires all parsers to match exactly once in any order.

Return Type Differences

use nom::branch::{alt, permutation};
use nom::bytes::complete::tag;
use nom::character::complete::digit1;
use nom::IResult;
 
fn alt_example(input: &str) -> IResult<&str, &str> {
    // alt returns ONE result - the type of successful parser
    alt((
        tag("hello"),
        tag("world"),
        tag("!"),
    ))(input)
}
 
fn permutation_example(input: &str) -> IResult<&str, (&str, &str, &str)> {
    // permutation returns TUPLE of all results
    permutation((
        tag("a"),
        tag("b"),
        tag("c"),
    ))(input)
}
 
fn main() {
    // alt: one result
    let result = alt_example("world!");
    assert_eq!(result, Ok(("!", "world")));
    
    // permutation: tuple of all results
    let result = permutation_example("cba");
    assert_eq!(result, Ok(("", ("c", "b", "a"))));
}

alt returns a single value; permutation returns a tuple of all values.

Order Sensitivity in alt

use nom::branch::alt;
use nom::bytes::complete::tag;
use nom::IResult;
 
fn parse_keyword(input: &str) -> IResult<&str, &str> {
    // ORDER MATTERS: try shorter matches first might consume wrong input
    alt((
        tag("let"),
        tag("letter"),
    ))(input)
}
 
fn parse_keyword_fixed(input: &str) -> IResult<&str, &str> {
    // ORDER MATTERS: try longer matches first
    alt((
        tag("letter"),
        tag("let"),
    ))(input)
}
 
fn main() {
    // Problem: "let" matches first, consuming "let" from "letter"
    assert_eq!(parse_keyword("letter"), Ok(("ter", "let")));
    
    // Fixed: try "letter" first
    assert_eq!(parse_keyword_fixed("letter"), Ok(("", "letter")));
    assert_eq!(parse_keyword_fixed("let"), Ok(("", "let")));
}

alt is ordered choice; parser order affects behavior significantly.

Order Insensitivity in permutation

use nom::branch::permutation;
use nom::bytes::complete::tag;
use nom::IResult;
 
fn parse_command_flags(input: &str) -> IResult<&str, (&str, &str, &str)> {
    // Order doesn't matter - all must appear somewhere
    permutation((
        tag("-v"),
        tag("-f"),
        tag("-q"),
    ))(input)
}
 
fn main() {
    // Any order works
    assert_eq!(parse_command_flags("-v-f-q"), Ok(("", ("-v", "-f", "-q"))));
    assert_eq!(parse_command_flags("-q-v-f"), Ok(("", ("-q", "-v", "-f"))));
    assert_eq!(parse_command_flags("-f-q-v"), Ok(("", ("-f", "-q", "-v"))));
    
    // All flags required
    assert!(parse_command_flags("-v-f").is_err());  // Missing -q
}

permutation matches elements in any order; all must be present.

Combining with Other Parsers

use nom::branch::{alt, permutation};
use nom::bytes::complete::tag;
use nom::character::complete::{alpha1, digit1};
use nom::sequence::tuple;
use nom::IResult;
 
fn alt_with_complex_parsers(input: &str) -> IResult<&str, &str> {
    // alt can combine any parser types
    alt((
        digit1,
        alpha1,
        tag("!"),
    ))(input)
}
 
fn permutation_with_complex_parsers(input: &str) -> IResult<&str, (&str, &str)> {
    // permutation requires each parser to match once
    permutation((
        digit1,
        alpha1,
    ))(input)
}
 
fn main() {
    // alt: tries each in order
    assert_eq!(alt_with_complex_parsers("123"), Ok(("", "123")));
    assert_eq!(alt_with_complex_parsers("abc"), Ok(("", "abc")));
    assert_eq!(alt_with_complex_parsers("!"), Ok(("", "!")));
    
    // permutation: both must match
    assert_eq!(permutation_with_complex_parsers("123abc"), Ok(("", ("123", "abc"))));
    assert_eq!(permutation_with_complex_parsers("abc123"), Ok(("", ("abc", "123"))));
}

Both combinators work with any parser type, not just tag.

Parsing Structured Data with alt

use nom::branch::alt;
use nom::bytes::complete::tag;
use nom::character::complete::{char, digit1};
use nom::sequence::delimited;
use nom::IResult;
 
#[derive(Debug)]
enum Value {
    Number(i64),
    String(String),
    Boolean(bool),
}
 
fn parse_value(input: &str) -> IResult<&str, Value> {
    alt((
        // Try each alternative in order
        |i| {
            let (i, _) = tag("true")(i)?;
            Ok((i, Value::Boolean(true)))
        },
        |i| {
            let (i, _) = tag("false")(i)?;
            Ok((i, Value::Boolean(false)))
        },
        |i| {
            let (i, num) = digit1(i)?;
            Ok((i, Value::Number(num.parse().unwrap())))
        },
        |i| {
            let (i, s) = delimited(char('"'), |i| {
                // Simplified string parsing
                let (i, content) = nom::character::complete::alphanumeric1(i)?;
                Ok((i, content.to_string()))
            }, char('"'))(i)?;
            Ok((i, Value::String(s)))
        },
    ))(input)
}
 
fn main() {
    assert_eq!(parse_value("true").unwrap().1, Value::Boolean(true));
    assert_eq!(parse_value("42").unwrap().1, Value::Number(42));
    assert_eq!(parse_value("\"hello\"").unwrap().1, Value::String("hello".to_string()));
}

alt is ideal for mutually exclusive alternatives like different value types.

Parsing Command Arguments with permutation

use nom::branch::permutation;
use nom::bytes::complete::tag;
use nom::character::complete::multispace0;
use nom::sequence::preceded;
use nom::IResult;
 
#[derive(Debug, Default)]
struct Args {
    verbose: bool,
    force: bool,
    quiet: bool,
}
 
fn parse_flag(input: &str, flag: &str) -> impl Fn(&str) -> IResult<&str, bool> + '_ {
    move |i: &str| {
        let (i, _) = tag(flag)(i)?;
        Ok((i, true))
    }
}
 
fn parse_args(input: &str) -> IResult<&str, (bool, bool, bool)> {
    permutation((
        preceded(multispace0, parse_flag(input, "-v")),
        preceded(multispace0, parse_flag(input, "-f")),
        preceded(multispace0, parse_flag(input, "-q")),
    ))(input)
}
 
fn main() {
    // Flags in any order
    let (rem, (v, f, q)) = parse_args("-v -f -q").unwrap();
    println!("verbose: {}, force: {}, quiet: {}", v, f, q);
    
    let (rem, (v, f, q)) = parse_args("-q -v -f").unwrap();
    println!("verbose: {}, force: {}, quiet: {}", v, f, q);
}

permutation handles flags/arguments that can appear in any order.

Failure Behavior Differences

use nom::branch::{alt, permutation};
use nom::bytes::complete::tag;
use nom::error::Error;
use nom::IResult;
 
fn main() {
    // alt: succeeds if ANY alternative succeeds
    let result: IResult<&str, &str, Error<&str>> = alt((
        tag("a"),
        tag("b"),
        tag("c"),
    ))("d");
    
    assert!(result.is_err());
    // Error: all alternatives failed
    
    // permutation: succeeds if ALL parsers match
    let result: IResult<&str, (&str, &str), Error<&str>> = permutation((
        tag("a"),
        tag("b"),
    ))("ab");
    
    assert_eq!(result, Ok(("", ("a", "b"))));
    
    // permutation fails if any parser fails to match
    let result: IResult<&str, (&str, &str), Error<&str>> = permutation((
        tag("a"),
        tag("b"),
    ))("ac");
    
    assert!(result.is_err());  // "b" not found
}

alt fails when all alternatives fail; permutation fails when any parser fails.

Backtracking Behavior

use nom::branch::alt;
use nom::bytes::complete::tag;
use nom::sequence::pair;
use nom::IResult;
 
fn main() {
    // alt backtracks between alternatives
    // If first parser partially matches but fails later, tries next
    
    fn parser1(input: &str) -> IResult<&str, (&str, &str)> {
        pair(tag("ab"), tag("c"))(input)  // Must match "abc"
    }
    
    fn parser2(input: &str) -> IResult<&str, (&str, &str)> {
        pair(tag("ab"), tag("d"))(input)  // Must match "abd"
    }
    
    let result = alt((parser1, parser2))("abd");
    // parser1 tries "abc", fails at "c" vs "d"
    // alt backtracks, tries parser2, succeeds
    
    assert_eq!(result, Ok(("", ("ab", "d"))));
    
    // permutation also backtracks when trying different orders
    use nom::branch::permutation;
    
    let result = permutation((
        tag("ab"),
        tag("cd"),
    ))("abcd");
    
    // Tries to match parsers in different orders until finding valid order
    assert_eq!(result, Ok(("", ("ab", "cd"))));
}

Both alt and permutation backtrack when trying alternatives.

Performance Considerations

use nom::branch::{alt, permutation};
use nom::bytes::complete::tag;
use nom::IResult;
 
fn main() {
    // alt: O(n) where n = number of alternatives
    // Each parser tried in order until success
    
    // For many alternatives, put common ones first
    fn parse_keyword(input: &str) -> IResult<&str, &str> {
        alt((
            tag("if"),       // Common
            tag("else"),     // Common
            tag("while"),    // Less common
            tag("for"),      // Less common
            // ... many more
        ))(input)
    }
    
    // permutation: tries all orderings
    // O(n!) worst case, but practical for small n
    // n = number of parsers
    
    // For many elements, permutation can be slow
    fn parse_many(input: &str) -> IResult<&str, (&str, &str, &str)> {
        permutation((
            tag("a"),
            tag("b"),
            tag("c"),
        ))(input)
    }
    
    // OK: 3 parsers = manageable
    // Avoid: 10+ parsers = exponential complexity
}

alt is linear in alternatives; permutation is factorial in worst case.

Nested Combinators

use nom::branch::{alt, permutation};
use nom::bytes::complete::tag;
use nom::IResult;
 
fn main() {
    // alt inside alt: more alternatives
    fn parse_animal(input: &str) -> IResult<&str, &str> {
        alt((
            alt((tag("cat"), tag("dog"))),
            alt((tag("bird"), tag("fish"))),
        ))(input)
    }
    
    assert_eq!(parse_animal("cat"), Ok(("", "cat")));
    assert_eq!(parse_animal("fish"), Ok(("", "fish")));
    
    // permutation inside permutation: nested groups
    fn parse_nested(input: &str) -> IResult<&str, ((&str, &str), (&str, &str))> {
        permutation((
            permutation((tag("a"), tag("b"))),
            permutation((tag("c"), tag("d"))),
        ))(input)
    }
    
    // Each inner permutation must match in any order
    // Outer permutation: groups can appear in any order
    assert_eq!(parse_nested("abcd"), Ok(("", (("a", "b"), ("c", "d")))));
    assert_eq!(parse_nested("cdab"), Ok(("", (("c", "d"), ("a", "b")))));
    
    // alt inside permutation: choices for each position
    fn parse_flags(input: &str) -> IResult<&str, (&str, &str)> {
        permutation((
            alt((tag("-v"), tag("--verbose"))),
            alt((tag("-f"), tag("--force"))),
        ))(input)
    }
    
    assert_eq!(parse_flags("-v-f"), Ok(("", ("-v", "-f"))));
    assert_eq!(parse_flags("--verbose--force"), Ok(("", ("--verbose", "--force"))));
    assert_eq!(parse_flags("-f--verbose"), Ok(("", ("-f", "--verbose"))));
}

Combinators can nest to create complex parsing patterns.

Practical Example: Configuration Parser

use nom::branch::{alt, permutation};
use nom::bytes::complete::tag;
use nom::character::complete::{alphanumeric1, multispace0, space0};
use nom::sequence::{preceded, terminated};
use nom::IResult;
 
#[derive(Debug, Default)]
struct Config {
    host: Option<String>,
    port: Option<u16>,
    debug: bool,
}
 
fn parse_host(input: &str) -> IResult<&str, String> {
    let (i, _) = tag("host=")(input)?;
    let (i, host) = alphanumeric1(i)?;
    Ok((i, host.to_string()))
}
 
fn parse_port(input: &str) -> IResult<&str, u16> {
    let (i, _) = tag("port=")(input)?;
    let (i, port) = nom::character::complete::u16(i)?;
    Ok((i, port))
}
 
fn parse_debug(input: &str) -> IResult<&str, bool> {
    let (i, _) = tag("debug")(input)?;
    Ok((i, true))
}
 
fn parse_config_item(input: &str) -> IResult<&str, ConfigItem> {
    // Each item is mutually exclusive - use alt
    alt((
        |i| parse_host(i).map(|(rem, h)| (rem, ConfigItem::Host(h))),
        |i| parse_port(i).map(|(rem, p)| (rem, ConfigItem::Port(p))),
        |i| parse_debug(i).map(|(rem, _)| (rem, ConfigItem::Debug)),
    ))(input)
}
 
enum ConfigItem {
    Host(String),
    Port(u16),
    Debug(bool),
}
 
fn main() {
    // alt for individual item types
    let result = alt((
        tag("host=localhost"),
        tag("port=8080"),
        tag("debug"),
    ))("port=8080");
    
    // In practice, use permutation for ordered items:
    // host=X port=Y debug - any order
    
    // But alt for the value of each: host=(X|Y|Z)
}

Combine alt and permutation for realistic parsing scenarios.

Error Context

use nom::branch::alt;
use nom::bytes::complete::tag;
use nom::error::{Error, ErrorKind};
use nom::IResult;
 
fn main() {
    // alt returns error from last alternative
    let result: IResult<&str, &str, Error<&str>> = alt((
        tag("a"),
        tag("b"),
        tag("c"),
    ))("xyz");
    
    if let Err(nom::Err::Error(e)) = result {
        // Error from last parser that was tried
        println!("Error at input: {:?}", e.input);
        println!("Error kind: {:?}", e.code);
    }
    
    // All alternatives tried, last error returned
    // Consider nom::error::VerboseError for better diagnostics
}

alt returns the error from the last alternative tried.

Synthesis

Core distinction:

alt: "one of these must succeed" (ordered choice, first success wins)
permutation: "all of these must succeed in any order" (unordered collection)

Return types:

alt((A, B, C)) returns A | B | C (one result)
permutation((A, B, C)) returns (A, B, C) (tuple of all results)

Order sensitivity:

alt: order matters (first match wins, like if/else if)
permutation: order irrelevant (matches in any order)

Failure conditions:

alt: fails when ALL alternatives fail
permutation: fails when ANY parser fails

Use alt for:

Mutually exclusive alternatives (keywords, operators, literals)
Parsing one of several types
Optional syntax variations
Order-dependent choice (longest match first)

Use permutation for:

Unordered collections (flags, attributes, parameters)
Elements that must all appear but order doesn't matter
Structured data with flexible ordering

Performance:

alt: O(n) for n alternatives, linear scan
permutation: O(n!) worst case, but practical for small n

Key insight: The choice between alt and permutation depends on your semantics. If alternatives are mutually exclusive (only one should match), use alt. If elements are complementary (all should match, order irrelevant), use permutation. For complex grammars, combine them: alt for choices within a position, permutation for ordering flexibility across positions. The ordered choice in alt requires careful ordering (longer matches before shorter to avoid premature matching), while permutation handles ordering transparently but requires all elements to be present.

What are the differences between nom::branch::alt and nom::branch::permutation for parsing alternatives?