What is the difference between `nom::branch::alt` and `choice` for multiple parser alternatives?

nom::branch::alt and nom::branch::choice are both parser combinators for trying multiple alternatives, but they differ in how they handle backtracking and error reporting: alt tries each parser in sequence and returns the first successful result, while choice is a more generic abstraction that requires the input type to implement Clone and can work with dynamically sized alternatives. The practical difference is that alt is a macro that expands to a cascade of or operations optimized at compile time, producing precise error locations, whereas choice works with slices/vectors of parsers and may have different error accumulation behavior. For most parsing tasks, alt is preferred for its better error messages and compile-time optimization, while choice is useful when the set of alternatives is determined at runtime.

Understanding Parser Alternatives

use nom::{IResult, bytes::complete::tag, branch::alt};
 
// In parser combinators, you often need to try multiple alternatives:
// - Parse either "true" or "false"
// - Parse either a number or a string
// - Parse either an expression or a statement
 
// The challenge: if the first alternative fails, try the next one
// If all alternatives fail, report an appropriate error
 
fn example() {
    let input = "hello world";
    
    // We want to parse either "hello" or "world"
    // If "hello" fails, try "world"
    // If both fail, return an error
}

Parser alternatives are fundamental to describing grammar choices.

Basic alt Usage

use nom::{IResult, bytes::complete::tag, branch::alt};
 
// alt tries each parser in sequence, returning the first success
fn parse_greeting(input: &str) -> IResult<&str, &str> {
    alt((
        tag("hello"),
        tag("hi"),
        tag("hey"),
        tag("greetings"),
    ))(input)
}
 
fn main() {
    // Success: matches "hello"
    let result = parse_greeting("hello world");
    assert_eq!(result, Ok((" world", "hello")));
    
    // Success: matches "hi"
    let result = parse_greeting("hi there");
    assert_eq!(result, Ok((" there", "hi")));
    
    // Success: matches "hey"
    let result = parse_greeting("hey you");
    assert_eq!(result, Ok((" you", "hey")));
    
    // Failure: no alternatives match
    let result = parse_greeting("goodbye");
    assert!(result.is_err());
}

alt tries parsers in order, returning the first successful match.

The choice Function

use nom::{IResult, bytes::complete::tag, branch::choice};
 
// choice works similarly but operates on a slice of parsers
// It's more generic but requires InputLength trait
 
fn parse_greeting_choice(input: &str) -> IResult<&str, &str> {
    choice((
        tag("hello"),
        tag("hi"),
        tag("hey"),
    ))(input)
}
 
fn main() {
    let result = parse_greeting_choice("hello world");
    assert_eq!(result, Ok((" world", "hello")));
}
 
// Note: In recent versions of nom, choice and alt are often
// implemented similarly. The key historical difference:
// - alt: macro, compile-time expansion
// - choice: function, runtime dispatch

choice provides similar functionality with a different implementation approach.

Error Reporting Differences

use nom::{IResult, bytes::complete::tag, branch::{alt, choice}, error::{Error, ErrorKind}};
 
fn error_reporting() {
    // alt provides better error messages for the specific failure
    // It knows which alternatives were tried
    
    // With alt:
    let result: IResult<&str, &str, Error<&str>> = alt((
        tag("hello"),
        tag("hi"),
        tag("hey"),
    ))("goodbye");
    
    match result {
        Err(nom::Err::Error(e)) => {
            // Error indicates what was expected
            // The error kind helps identify the failure point
            println!("Error: {:?}", e);
        }
        _ => unreachable!(),
    }
    
    // choice accumulates errors differently
    // May report all failed alternatives
    
    let result: IResult<&str, &str, Error<&str>> = choice((
        tag("hello"),
        tag("hi"),
        tag("hey"),
    ))("goodbye");
    
    // Both fail, but error details may differ
}

Error messages differ based on how alternatives are combined.

Compile-Time vs Runtime Dispatch

use nom::{IResult, bytes::complete::tag, branch::alt};
 
// alt: compile-time expansion
// The macro expands to a cascade of 'or' operations
 
fn compile_time_example(input: &str) -> IResult<&str, &str> {
    alt((
        tag("hello"),
        tag("hi"),
        tag("hey"),
    ))(input)
}
 
// This expands roughly to:
// tag("hello")(input)
//     .or_else(|_| tag("hi")(input))
//     .or_else(|_| tag("hey")(input))
 
// Benefits:
// - Compiler can optimize the cascade
// - Inlining possible
// - No dynamic dispatch overhead
 
// choice: runtime dispatch
// The set of alternatives can be dynamic
 
fn runtime_example(input: &str, keywords: &[&str]) -> IResult<&str, &str> {
    // Can't use alt because keywords is dynamic
    // Would need to build parsers at runtime
    
    // Note: This specific pattern requires dynamic parser creation
    // which nom handles differently
    unimplemented!()
}

alt is optimized at compile time; choice can work with runtime-determined alternatives.

Static vs Dynamic Parser Sets

use nom::{IResult, bytes::complete::tag, branch::alt};
 
// alt requires known parsers at compile time
fn static_alternatives(input: &str) -> IResult<&str, &str> {
    // All alternatives must be known at compile time
    alt((
        tag("one"),
        tag("two"),
        tag("three"),
    ))(input)
}
 
// For dynamic alternatives, you need different approaches
// (choice in older nom versions supported this)
 
// Modern approach for dynamic alternatives:
// Use a fold or try each in a loop
 
fn dynamic_alternatives<'a>(
    input: &'a str,
    keywords: &[&'a str],
) -> IResult<&'a str, &'a str> {
    // Try each keyword in order
    for keyword in keywords {
        if let Ok(result) = tag(*keyword)(input) {
            return Ok(result);
        }
    }
    
    // All failed
    Err(nom::Err::Error(nom::error::Error::new(input, nom::error::ErrorKind::Tag)))
}
 
fn main() {
    let keywords = vec!["one", "two", "three"];
    let result = dynamic_alternatives("two more", &keywords);
    assert_eq!(result, Ok((" more", "two")));
}

alt requires static alternatives; dynamic sets need different handling.

Tuple-Based Alternatives

use nom::{IResult, bytes::complete::tag, branch::alt};
 
// alt works with tuples of parsers
// The tuple size must be known at compile time
 
fn parse_keyword(input: &str) -> IResult<&str, &str> {
    // 2 alternatives
    alt((
        tag("if"),
        tag("else"),
    ))(input)
}
 
fn parse_keyword_three(input: &str) -> IResult<&str, &str> {
    // 3 alternatives
    alt((
        tag("if"),
        tag("else"),
        tag("while"),
    ))(input)
}
 
fn parse_keyword_many(input: &str) -> IResult<&str, &str> {
    // Many alternatives - all compile-time known
    alt((
        tag("if"),
        tag("else"),
        tag("while"),
        tag("for"),
        tag("match"),
        tag("return"),
    ))(input)
}
 
// All tuples expand to optimized code
// No runtime dispatch

alt tuples can have any fixed size known at compile time.

Performance Characteristics

use nom::{IResult, bytes::complete::tag, branch::alt};
 
// alt performance characteristics:
 
fn performance_example() {
    // alt tries alternatives in order
    // - First match wins
    // - No backtracking beyond trying next alternative
    // - Short-circuits on first success
    
    let input = "hello world";
    
    // Order matters for performance
    // Put common cases first
    let result: IResult<&str, &str> = alt((
        tag("hello"),  // Most common, try first
        tag("hi"),     // Less common
        tag("hey"),   // Least common
    ))(input);
    
    // If "hello" matches, "hi" and "hey" are never tried
    // Performance: O(n) where n is position of first match
    
    // Compare to:
    let result: IResult<&str, &str> = alt((
        tag("rare"),   // Rare, unlikely to match
        tag("hello"),  // Common, but tried second
        tag("hi"),
    ))(input);
    // Still works, but tries "rare" first (wasted effort)
}
 
// choice has similar performance but:
// - May have overhead for dynamic dispatch
// - Error handling may be slower
// - Depends on implementation version

Order alternatives by likelihood for better performance.

Combining with Other Combinators

use nom::{IResult, bytes::complete::tag, branch::alt, sequence::preceded, character::complete::space0};
 
// alt integrates well with other combinators
 
fn parse_expression(input: &str) -> IResult<&str, &str> {
    // Parse one of several expressions
    alt((
        tag("true"),
        tag("false"),
        tag("null"),
    ))(input)
}
 
fn parse_keyword_expr(input: &str) -> IResult<&str, &str> {
    // Parse a keyword optionally preceded by whitespace
    preceded(
        space0,
        alt((
            tag("if"),
            tag("else"),
            tag("while"),
        )),
    )(input)
}
 
fn main() {
    let result = parse_keyword_expr("   while true");
    assert_eq!(result, Ok((" true", "while")));
}
 
// alt results can be further processed
fn parse_value(input: &str) -> IResult<&str, i32> {
    let (remaining, matched) = alt((
        tag("one"),
        tag("two"),
        tag("three"),
    ))(input)?;
    
    let value = match matched {
        "one" => 1,
        "two" => 2,
        "three" => 3,
        _ => unreachable!(),
    };
    
    Ok((remaining, value))
}

alt combines naturally with sequence and transformation combinators.

Return Type Variants

use nom::{IResult, bytes::complete::tag, branch::alt, combinator::map};
 
// When alternatives return different types, use map to unify
 
fn parse_literal(input: &str) -> IResult<&str, Literal> {
    alt((
        map(tag("true"), |_| Literal::Bool(true)),
        map(tag("false"), |_| Literal::Bool(false)),
        map(tag("null"), |_| Literal::Null),
    ))(input)
}
 
#[derive(Debug, PartialEq)]
enum Literal {
    Bool(bool),
    Null,
}
 
fn main() {
    let result = parse_literal("true");
    assert_eq!(result, Ok(("", Literal::Bool(true))));
    
    let result = parse_literal("null");
    assert_eq!(result, Ok(("", Literal::Null)));
}
 
// All alternatives must have the same return type
// Use map, value, or into to unify types

All alternatives in alt must return compatible types.

Error Accumulation

use nom::{IResult, bytes::complete::tag, branch::alt, error::VerboseError};
 
// How errors are accumulated depends on the error type
 
fn with_verbose_error(input: &str) -> IResult<&str, &str, VerboseError<&str>> {
    alt((
        tag("hello"),
        tag("hi"),
        tag("hey"),
    ))(input)
}
 
fn main() {
    let result = with_verbose_error("goodbye");
    
    match result {
        Err(nom::Err::Error(e)) => {
            // VerboseError contains context for each failed alternative
            // Shows all attempted parsers
            println!("Verbose error: {:?}", e);
        }
        _ => unreachable!(),
    }
}
 
// With basic Error type:
fn with_basic_error(input: &str) -> IResult<&str, &str> {
    alt((
        tag("hello"),
        tag("hi"),
        tag("hey"),
    ))(input)
}
 
// Basic Error only shows the last failed attempt

Error types determine how much information is accumulated.

Recursive Alternatives

use nom::{IResult, bytes::complete::tag, branch::alt, sequence::delimited};
 
// For recursive grammars, alt needs special handling
 
// This doesn't work directly due to recursion:
// fn parse_expr(input: &str) -> IResult<&str, Expr> {
//     alt((
//         parse_atom,
//         parse_paren_expr,  // which calls parse_expr recursively
//     ))(input)
// }
 
// Use a function wrapper for recursion:
fn parse_expr(input: &str) -> IResult<&str, Expr> {
    alt((
        parse_atom,
        parse_paren_expr,
    ))(input)
}
 
fn parse_paren_expr(input: &str) -> IResult<&str, Expr> {
    delimited(
        tag("("),
        parse_expr,  // Recursive call
        tag(")"),
    )(input)
    .map(|(remaining, expr)| (remaining, Expr::Paren(Box::new(expr))))
}
 
fn parse_atom(input: &str) -> IResult<&str, Expr> {
    alt((
        tag("true"),
        tag("false"),
    ))(input)
    .map(|(remaining, matched)| {
        let value = matched == "true";
        (remaining, Expr::Bool(value))
    })
}
 
#[derive(Debug)]
enum Expr {
    Bool(bool),
    Paren(Box<Expr>),
}

Recursive alternatives work naturally with alt using function references.

Practical Comparison Summary

use nom::{IResult, bytes::complete::tag, branch::alt};
 
fn main() {
    // Use alt when:
    // 1. Alternatives are known at compile time
    // 2. You want precise error messages
    // 3. Performance matters (compile-time optimization)
    // 4. Simple alternatives that return same type
    
    // alt is the go-to choice for most parsing tasks:
    fn parse_keyword(input: &str) -> IResult<&str, &str> {
        alt((
            tag("if"),
            tag("else"),
            tag("while"),
            tag("for"),
            tag("return"),
        ))(input)
    }
    
    // Consider alternatives when:
    // 1. You need dynamic alternatives (runtime-determined)
    // 2. You're working with parser combinators from a library
    //    that provides specialized choice implementations
    
    // In modern nom (5.x+), alt is preferred for most use cases
    // choice exists but is often implemented in terms of alt
}

alt is the primary choice for static alternatives in modern nom.

Synthesis

alt characteristics:

// alt((parser1, parser2, parser3))(input)
// - Tries parsers in sequence
// - Returns first successful result
// - Compile-time optimization
// - Precise error messages
// - Works with tuples of any size
// - Requires same return type for all alternatives
 
fn example_alt(input: &str) -> IResult<&str, &str> {
    alt((
        tag("hello"),
        tag("hi"),
        tag("hey"),
    ))(input)
}

choice characteristics:

// choice((parser1, parser2, parser3))(input)
// - Similar to alt in recent versions
// - May have different error handling
// - Can work with slice/vector in some implementations
// - Runtime dispatch possible
// - Less common in modern nom code
 
// Historical distinction:
// - alt: macro, expanded at compile time
// - choice: function, runtime dispatch
// Modern nom often uses alt for both cases

Key differences:

// 1. Implementation approach
// alt: Macro expansion to cascade of 'or' operations
// choice: Function call with dynamic dispatch potential
 
// 2. Error handling
// alt: Better compile-time error tracking
// choice: May accumulate errors differently
 
// 3. Use case preference
// alt: Static alternatives (compile-time known)
// choice: Dynamic alternatives (runtime determined) - though
//         this requires special handling in modern nom
 
// In practice:
// Use alt for most parsing tasks
// It's more widely used and better documented

Key insight: nom::branch::alt and nom::branch::choice both implement the parser alternative pattern—try multiple parsers and return the first success—but differ in their implementation approach and use cases. alt is a macro that expands to a compile-time cascade of or operations, providing better optimization and error messages for statically-known alternatives. choice is a more generic abstraction that can potentially work with dynamically-determined parser sets, though in modern nom versions (5.x+), alt is the primary recommended approach for most use cases. The practical guidance is: use alt when your alternatives are known at compile time (which is the common case), and consider alternative approaches for dynamic alternatives. Both require that all parsers return the same type, and both try alternatives in the order specified, returning the first successful result. The choice between them is rarely performance-critical—focus on readability and whether you need compile-time optimization (prefer alt) or runtime flexibility (may need custom handling beyond choice).

What is the difference between nom::branch::alt and choice for multiple parser alternatives?