Arc<Mutex>

Guides

Rust walkthroughs

← Back to all guides

What are the trade-offs between nom::branch::alt and permutation for parsing alternatives in different orders?

alt attempts parsers in a fixed sequence and returns on the first match, while permutation matches all specified parsers in any order, collecting all results. alt is for "one of these" semantics—you want exactly one alternative to succeed. permutation is for "all of these, in any order" semantics—you need all parsers to succeed but the order doesn't matter. The choice affects parser behavior, error messages, and performance in ways that matter for complex parsing tasks.

The alt Combinator: Ordered Choice

use nom::{
    branch::alt,
    bytes::complete::tag,
    character::complete::alpha1,
    IResult,
};
 
fn main() {
    // alt tries parsers in order, returns first success
    fn parse_greeting(input: &str) -> IResult<&str, &str> {
        alt((
            tag("hello"),
            tag("hi"),
            tag("hey"),
        ))(input)
    }
    
    // Tries "hello" first, then "hi", then "hey"
    assert_eq!(parse_greeting("hello world"), Ok((" world", "hello")));
    assert_eq!(parse_greeting("hi there"), Ok((" there", "hi")));
    assert_eq!(parse_greeting("hey you"), Ok((" you", "hey")));
    
    // None match - returns error
    assert!(parse_greeting("goodbye").is_err());
    
    // Order matters for overlapping prefixes
    fn parse_overlapping(input: &str) -> IResult<&str, &str> {
        alt((
            tag("hell"),    // Would match "hell" but...
            tag("hello"),   // This never runs if "hell" matches first
        ))(input)
    }
    
    // "hell" is tried first and matches
    assert_eq!(parse_overlapping("hello"), Ok(("o", "hell")));
    // "hello" is never tried because "hell" matched first
}

alt implements ordered choice—the first matching parser wins.

The permutation Combinator: Unordered Collection

use nom::{
    combinator::map,
    multi::permutation,
    bytes::complete::tag,
    sequence::pair,
    IResult,
};
 
fn main() {
    // permutation matches ALL parsers in ANY order
    fn parse_flags(input: &str) -> IResult<&str, (&str, &str, &str)> {
        permutation((
            tag("a"),
            tag("b"),
            tag("c"),
        ))(input)
    }
    
    // All three must match, but order doesn't matter
    assert_eq!(parse_flags("abc"), Ok(("", ("a", "b", "c"))));
    assert_eq!(parse_flags("bac"), Ok(("", ("b", "a", "c"))));
    assert_eq!(parse_flags("cab"), Ok(("", ("c", "a", "b"))));
    assert_eq!(parse_flags("cba"), Ok(("", ("c", "b", "a"))));
    
    // Missing any one flag fails
    assert!(parse_flags("ab").is_err());
    assert!(parse_flags("ac").is_err());
    
    // Note: permutation can't handle overlapping patterns well
    // Each parser must be distinguishable or it gets confusing
    
    // More practical example: configuration options
    fn parse_config(input: &str) -> IResult<&str, (Option<&str>, Option<&str>, Option<&str>)> {
        // Using permutation for optional flags in any order
        permutation((
            // Each parser can succeed or fail independently
            // But with permutation, ALL must succeed
            // For optional, use permutation with opt
        ))(input)
    }
    
    // For truly optional elements in any order, use fold_permute
    // or a different approach
}

permutation requires all parsers to succeed but accepts any ordering.

Semantic Difference: One vs All

use nom::{
    branch::alt,
    multi::permutation,
    bytes::complete::tag,
    IResult,
};
 
fn main() {
    // alt: "ONE OF these parsers must match"
    fn parse_one(input: &str) -> IResult<&str, &str> {
        alt((
            tag("cat"),
            tag("dog"),
            tag("bird"),
        ))(input)
    }
    
    // Returns single match
    assert_eq!(parse_one("cat"), Ok(("", "cat")));
    assert_eq!(parse_one("dog"), Ok(("", "dog")));
    // Only one result
    
    // permutation: "ALL of these parsers must match (any order)"
    fn parse_all(input: &str) -> IResult<&str, (&str, &str, &str)> {
        permutation((
            tag("cat"),
            tag("dog"),
            tag("bird"),
        ))(input)
    }
    
    // Requires all three to be present
    assert_eq!(parse_all("catdogbird"), Ok(("", ("cat", "dog", "bird"))));
    assert_eq!(parse_all("birddogcat"), Ok(("", ("bird", "dog", "cat"))));
    
    // Missing one fails
    assert!(parse_all("catdog").is_err());
    
    // The key difference:
    // alt: 1 of N must match (returns single result)
    // permutation: N of N must match (returns tuple of all)
}

alt is for alternatives; permutation is for unordered sequences.

Error Handling Behavior

use nom::{
    branch::alt,
    multi::permutation,
    bytes::complete::tag,
    character::complete::digit1,
    IResult,
    error::{Error, ErrorKind},
};
 
fn main() {
    // alt: returns first parser's error if none match
    fn parse_word(input: &str) -> IResult<&str, &str> {
        alt((
            tag("hello"),
            tag("world"),
        ))(input)
    }
    
    let result = parse_word("goodbye");
    match result {
        Err(nom::Err::Error(e)) => {
            // Error from first parser that consumed input
            // or the last parser tried
            println!("Error at: {:?}", e);
        }
        _ => {}
    }
    
    // permutation: reports which parsers are missing
    fn parse_items(input: &str) -> IResult<&str, (&str, &str)> {
        permutation((
            tag("alpha"),
            tag("beta"),
        ))(input)
    }
    
    let result = parse_items("alpha");
    match result {
        Err(nom::Err::Error(e)) => {
            // Error indicates "beta" was expected but not found
            println!("Missing parser in permutation: {:?}", e);
        }
        _ => {}
    }
    
    // Error messages differ significantly:
    // alt: "expected one of these alternatives"
    // permutation: "expected this specific parser to match"
}

alt errors are about choice; permutation errors are about missing elements.

Performance Characteristics

use nom::{
    branch::alt,
    multi::permutation,
    bytes::complete::tag,
    IResult,
};
 
fn main() {
    // alt: O(n) in worst case, but short-circuits
    // First match returns immediately
    
    fn parse_alt(input: &str) -> IResult<&str, &str> {
        alt((
            tag("a"),
            tag("b"),
            tag("c"),
            tag("d"),
            tag("e"),
        ))(input)
    }
    
    // "a" matches first - only one comparison
    // "e" requires five comparisons
    
    // permutation: More complex matching
    // Must try to find all parsers somewhere in input
    
    fn parse_perm(input: &str) -> IResult<&str, (&str, &str, &str)> {
        permutation((
            tag("x"),
            tag("y"),
            tag("z"),
        ))(input)
    }
    
    // permutation needs to:
    // 1. Try each parser at current position
    // 2. If match, move forward, try remaining parsers
    // 3. Backtrack if stuck
    // 4. More expensive than alt
    
    // Performance implications:
    // - alt: faster when first alternatives are common
    // - alt: order parsers by frequency/likelihood
    // - permutation: O(n!m) in worst case (n parsers, m positions)
    // - permutation: avoid for long sequences
    
    // Best practice for alt:
    fn parse_keywords(input: &str) -> IResult<&str, &str> {
        alt((
            tag("if"),      // Most common first
            tag("else"),    // Then less common
            tag("while"),
            tag("for"),
            tag("match"),   // Least common last
        ))(input)
    }
}

Order matters for alt performance; permutation has higher overhead.

Practical Use Case: Command-Line Arguments

use nom::{
    branch::alt,
    multi::permutation,
    bytes::complete::tag,
    character::complete::{space1, alpha1},
    sequence::preceded,
    combinator::{map, opt},
    IResult,
};
 
fn main() {
    // alt: parse one of several commands
    fn parse_command(input: &str) -> IResult<&str, &str> {
        alt((
            tag("run"),
            tag("build"),
            tag("test"),
            tag("clean"),
        ))(input)
    }
    
    assert_eq!(parse_command("run --release"), Ok((" --release", "run")));
    // Returns exactly one command
    
    // permutation: parse multiple flags in any order
    fn parse_flags(input: &str) -> IResult<&str, (Option<&str>, Option<&str>, Option<&str>)> {
        // Note: This is simplified; real permutation doesn't work with
        // optional parsers directly - need a different approach
        
        // For truly optional unordered flags, use fold/reduce patterns
        // or parse each with alt of "flag" or "skip"
        
        permutation((
            map(tag("--verbose"), |_| "--verbose"),
            map(tag("--release"), |_| "--release"),
            map(tag("--quiet"), |_| "--quiet"),
        ))(input)
    }
    
    // permutation works when all must be present:
    assert_eq!(
        parse_flags("--release --quiet --verbose"),
        Ok(("", ("--verbose", "--release", "--quiet")))
    );
    
    // For optional flags in any order, combination of alt and many0:
    fn parse_optional_flags(input: &str) -> IResult<&str, Vec<&str>> {
        nom::multi::many0(alt((
            tag("--verbose"),
            tag("--release"),
            tag("--quiet"),
        )))(input)
    }
    
    // This allows any subset in any order
    assert_eq!(
        parse_optional_flags("--release --verbose"),
        Ok(("", vec!("--release", "--verbose")))
    );
}

Use alt for mutually exclusive options; use other patterns for unordered optional elements.

Handling Overlapping Patterns

use nom::{
    branch::alt,
    bytes::complete::tag,
    IResult,
};
 
fn main() {
    // Problem: overlapping prefixes in alt
    fn parse_overlapping(input: &str) -> IResult<&str, &str> {
        alt((
            tag("let"),
            tag("letter"),   // Never reached!
            tag("letting"),   // Never reached!
        ))(input)
    }
    
    // "let" always matches first, consuming those characters
    assert_eq!(parse_overlapping("letter"), Ok(("ter", "let")));
    
    // Solution: order longest first
    fn parse_correct(input: &str) -> IResult<&str, &str> {
        alt((
            tag("letting"),   // Longest first
            tag("letter"),
            tag("let"),       // Shortest last
        ))(input)
    }
    
    assert_eq!(parse_correct("letting"), Ok(("", "letting")));
    assert_eq!(parse_correct("letter"), Ok(("", "letter")));
    assert_eq!(parse_correct("let"), Ok(("", "let")));
    
    // permutation doesn't have this issue:
    // Parsers must be mutually exclusive for permutation
    // to work correctly (no overlap in what they consume)
    
    fn parse_perm(input: &str) -> IResult<&str, (&str, &str)> {
        nom::multi::permutation((
            tag("ab"),
            tag("cd"),
        ))(input)
    }
    
    // These don't overlap, so order doesn't matter
    assert_eq!(parse_perm("abcd"), Ok(("", ("ab", "cd"))));
    assert_eq!(parse_perm("cdab"), Ok(("", ("cd", "ab"))));
}

alt requires careful ordering for overlapping patterns; permutation requires non-overlapping patterns.

Combining alt and permutation

use nom::{
    branch::alt,
    multi::permutation,
    bytes::complete::tag,
    sequence::tuple,
    IResult,
};
 
fn main() {
    // Real parsers often combine both
    
    // Example: parse command with optional ordered args
    
    // Command is one of several (alt)
    fn parse_command(input: &str) -> IResult<&str, &str> {
        alt((
            tag("connect"),
            tag("disconnect"),
            tag("status"),
        ))(input)
    }
    
    // Arguments must all be present, in any order (permutation)
    fn parse_args(input: &str) -> IResult<&str, (&str, &str, &str)> {
        permutation((
            tag("--host"),
            tag("--port"),
            tag("--timeout"),
        ))(input)
    }
    
    // Full parser: command followed by ordered args
    fn parse_full(input: &str) -> IResult<&str, (&str, (&str, &str, &str))> {
        tuple((
            parse_command,
            tag(" "),
            parse_args,
        ))(input)
    }
    
    // Or use alt within permutation
    fn parse_mixed(input: &str) -> IResult<&str, (&str, &str)> {
        permutation((
            // First position: one of several options
            alt((tag("a"), tag("b"))),
            // Second position: required
            tag("x"),
        ))(input)
    }
    
    assert_eq!(parse_mixed("ax"), Ok(("", ("a", "x"))));
    assert_eq!(parse_mixed("bx"), Ok(("", ("b", "x"))));
    assert_eq!(parse_mixed("xa"), Ok(("", ("x", "a"))));
    assert_eq!(parse_mixed("xb"), Ok(("", ("x", "b"))));
}

alt and permutation can be nested to express complex grammars.

When to Use Each

use nom::{
    branch::alt,
    multi::{permutation, many0, many1},
    bytes::complete::tag,
    IResult,
};
 
fn main() {
    // Use alt when:
    // 1. You need exactly one match from several alternatives
    
    fn parse_keyword(input: &str) -> IResult<&str, &str> {
        alt((
            tag("fn"), tag("let"), tag("if"), tag("else"),
            tag("while"), tag("for"), tag("match"),
        ))(input)
    }
    
    // 2. Alternatives are mutually exclusive
    
    fn parse_number_type(input: &str) -> IResult<&str, &str> {
        alt((
            tag("int"),
            tag("float"),
            tag("decimal"),
        ))(input)
    }
    
    // 3. You want first-match semantics
    
    fn parse_identifier_or_keyword(input: &str) -> IResult<&str, &str> {
        alt((
            // Keywords checked first
            alt((tag("if"), tag("else"), tag("while"))),
            // Then identifiers
            nom::character::complete::alpha1,
        ))(input)
    }
    
    // Use permutation when:
    // 1. All elements must be present but order doesn't matter
    
    fn parse_required_flags(input: &str) -> IResult<&str, (&str, &str)> {
        permutation((
            tag("--input"),
            tag("--output"),
        ))(input)
    }
    
    // 2. Configuration where fields can appear in any order
    
    // Note: For truly optional unordered fields, permutation
    // isn't directly applicable - use many0 with alt:
    
    fn parse_optional_unordered(input: &str) -> IResult<&str, Vec<&str>> {
        many0(alt((
            tag("--verbose"),
            tag("--quiet"),
            tag("--debug"),
        )))(input)
    }
    
    // This allows any subset in any order
    // But allows duplicates and doesn't require presence
    
    // For "each at most once, in any order":
    // Need custom combinator or careful design
}

Choose alt for exclusive choice; permutation for required unordered elements.

Synthesis

Quick reference:

use nom::{branch::alt, multi::permutation, bytes::complete::tag, IResult};
 
fn main() {
    // alt: one of N alternatives
    // - Ordered choice (first match wins)
    // - Returns single result
    // - Short-circuits on match
    // - Order affects behavior and performance
    // - Use for keywords, operators, alternatives
    
    fn with_alt(input: &str) -> IResult<&str, &str> {
        alt((tag("a"), tag("b"), tag("c")))(input)
    }
    // "a" OR "b" OR "c" (try in order, return first match)
    
    // permutation: all of N in any order
    // - Unordered matching
    // - Returns tuple of all results
    // - Tries all permutations
    // - More expensive than alt
    // - Use for unordered required elements
    
    fn with_permutation(input: &str) -> IResult<&str, (&str, &str, &str)> {
        permutation((tag("a"), tag("b"), tag("c")))(input)
    }
    // "a" AND "b" AND "c" (in any order, all must be present)
    
    // Key differences:
    // 1. Semantics: "one of" vs "all of (unordered)"
    // 2. Result: single value vs tuple
    // 3. Performance: O(n) vs potentially O(n!m)
    // 4. Error messages: choice failed vs missing element
    
    // When to use alt:
    // - Keywords, operators, alternatives
    // - Mutual exclusive options
    // - First-match-wins semantics
    
    // When to use permutation:
    // - Required fields in any order
    // - Configuration elements
    // - Non-overlapping, all-required patterns
    
    // Avoid permutation for:
    // - Optional elements (use many0(alt(...)))
    // - Large numbers of parsers
    // - Overlapping patterns
}

Key insight: alt and permutation solve fundamentally different problems. alt is about choice—"pick one from these alternatives"—and order matters for both semantics and performance. permutation is about collection—"match all of these in any order"—and requires all parsers to succeed. Use alt for keywords, operators, and mutually exclusive alternatives. Use permutation for required elements that can appear in any order, like configuration fields or command flags. For optional unordered elements, use many0(alt(...)) instead of permutation, or design a custom combinator that handles "at most once each" semantics.