🎬 Pattern Matching Exhaustive match, destructuring, guards, let-else — compiler-verified branching.

📝 Text version (for readers / accessibility)

• match is exhaustive — the compiler ensures every variant is handled

• Destructuring extracts fields from structs, tuples, and enums in one step

• Guards (if conditions) add extra logic to match arms

• if let and let-else provide concise single-pattern matching

• Nested patterns and @ bindings handle complex data shapes elegantly

040: Dotstring Parse

Difficulty: ⭐⭐ Level: Foundations Parse a dotstring into a binary tree with proper error handling using `Result`.

The Problem This Solves

Example 039 showed the dotstring format. This example focuses on the parsing direction — and adds something critical for real software: error handling. What if the input is an empty string? What if there are extra characters after a valid tree? What if the string is malformed? In a library or API, you can't just panic — you need to return a meaningful error that callers can handle. Rust's `Result<T, E>` type makes error handling a first-class concern. The parser either returns `Ok(tree)` or `Err(reason)`. The compiler forces you to handle both cases. No exceptions that bubble up silently, no null returns to check "or was it valid?".

The Intuition

In Python or Java, a parser might throw an exception on bad input:

def parse(s):
 if not s:
     raise ValueError("empty input")
 ...

You catch it somewhere (maybe) or you don't (oops). In Rust, errors are values in the type system:

fn parse_dotstring(s: &str) -> Result<Tree, ParseError>

The return type says this can fail. Callers must handle both `Ok` and `Err`. You can't accidentally ignore an error — the compiler won't let you use the tree without unwrapping the `Result`. This is especially important for the "trailing characters" case. `"x..extra"` is a valid tree (`x`) followed by garbage. A strict parser should reject this. Our parser checks that it consumed all the input:

if consumed != chars.len() {
 return Err(ParseError::TrailingChars(consumed));
}

How It Works in Rust

#[derive(Debug, PartialEq)]
enum ParseError {
 UnexpectedEnd,          // ran out of input mid-tree
 TrailingChars(usize),   // valid tree, but leftover input
}

fn parse_dotstring(s: &str) -> Result<Tree, ParseError> {
 let chars: Vec<char> = s.chars().collect();
 let (tree, consumed) = parse_inner(&chars, 0)?;  // '?' propagates errors

 if consumed != chars.len() {
     Err(ParseError::TrailingChars(consumed))
 } else {
     Ok(tree)
 }
}

fn parse_inner(chars: &[char], pos: usize)
 -> Result<(Tree, usize), ParseError>
{
 if pos >= chars.len() {
     return Err(ParseError::UnexpectedEnd);  // ran off the end
 }
 match chars[pos] {
     '.' => Ok((Tree::leaf(), pos + 1)),

     c => {
         let (left, pos2) = parse_inner(chars, pos + 1)?;  // ? propagates
         let (right, pos3) = parse_inner(chars, pos2)?;
         Ok((Tree::node(left, c, right), pos3))
     }
 }
}

The `?` operator is Rust's shorthand for "if this is `Err`, return it immediately; if `Ok`, unwrap the value." It threads errors up the call stack without explicit `match` at every step. This is equivalent to checked exceptions, but explicit in the type signature. Using the parser:

match parse_dotstring("abd..e..") {
 Ok(tree)  => println!("Parsed: {:?}", tree),
 Err(e)    => println!("Error: {:?}", e),
}

parse_dotstring("")          // Err(UnexpectedEnd)
parse_dotstring("x..extra")  // Err(TrailingChars(3))
parse_dotstring(".")         // Ok(Leaf)
parse_dotstring("x..")       // Ok(Node('x', Leaf, Leaf))

What This Unlocks

Real parsers: every production parser uses `Result` (or equivalent) for error propagation.
`?` operator: once you understand this pattern, Rust error handling feels clean and ergonomic.
Library APIs: returning `Result` instead of panicking makes your code usable in all contexts.

Key Differences

Concept	OCaml	Rust
Error type	`exception` or `result` type	`Result<T, E>` enum — `Ok(T)` or `Err(E)`
Error propagation	`raise` / exception	`?` operator — explicit in function signature
Trailing input check	Manual check on position	Same — compare `consumed` to `chars.len()`
Custom errors	Variant of exception type	Custom `enum ParseError { ... }`
Force caller to handle	Not enforced (exceptions)	Compiler enforces — can't use `T` without unwrapping `Result<T,E>`

// Dotstring Parse — 99 Problems #40
// Parse a dotstring into a binary tree and verify round-trips.
// This focuses on the parsing direction and error handling.

#[derive(Debug, PartialEq, Clone)]
enum Tree {
    Leaf,
    Node(Box<Tree>, char, Box<Tree>),
}

impl Tree {
    fn leaf() -> Self { Tree::Leaf }
    fn node(l: Tree, v: char, r: Tree) -> Self {
        Tree::Node(Box::new(l), v, Box::new(r))
    }
}

#[derive(Debug, PartialEq)]
enum ParseError {
    UnexpectedEnd,
    TrailingChars(usize),
}

/// Parse a dot-string with proper error handling.
fn parse_dotstring(s: &str) -> Result<Tree, ParseError> {
    let chars: Vec<char> = s.chars().collect();
    let (tree, consumed) = parse_inner(&chars, 0)?;
    if consumed != chars.len() {
        Err(ParseError::TrailingChars(consumed))
    } else {
        Ok(tree)
    }
}

fn parse_inner(chars: &[char], pos: usize) -> Result<(Tree, usize), ParseError> {
    if pos >= chars.len() {
        return Err(ParseError::UnexpectedEnd);
    }
    let c = chars[pos];
    if c == '.' {
        Ok((Tree::leaf(), pos + 1))
    } else {
        let (left, pos2) = parse_inner(chars, pos + 1)?;
        let (right, pos3) = parse_inner(chars, pos2)?;
        Ok((Tree::node(left, c, right), pos3))
    }
}

fn tree_to_dotstring(tree: &Tree) -> String {
    match tree {
        Tree::Leaf => ".".to_string(),
        Tree::Node(l, v, r) => format!("{}{}{}", v, tree_to_dotstring(l), tree_to_dotstring(r)),
    }
}

fn sample_tree() -> Tree {
    Tree::node(
        Tree::node(
            Tree::node(Tree::leaf(), 'd', Tree::leaf()),
            'b',
            Tree::node(Tree::leaf(), 'e', Tree::leaf()),
        ),
        'a',
        Tree::node(Tree::leaf(), 'c', Tree::node(Tree::leaf(), 'f', Tree::leaf())),
    )
}

fn main() {
    let t = sample_tree();
    let s = tree_to_dotstring(&t);
    println!("Dotstring: {}", s);

    match parse_dotstring(&s) {
        Ok(parsed) => println!("Parsed OK: {}", parsed == t),
        Err(e) => println!("Error: {:?}", e),
    }

    // Error cases
    println!("Parse '':       {:?}", parse_dotstring(""));
    println!("Parse 'x..extra': {:?}", parse_dotstring("x..extra"));
    println!("Parse '.':      {:?}", parse_dotstring("."));
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_parse_leaf() {
        assert_eq!(parse_dotstring("."), Ok(Tree::leaf()));
    }

    #[test]
    fn test_parse_single_node() {
        assert_eq!(
            parse_dotstring("x.."),
            Ok(Tree::node(Tree::leaf(), 'x', Tree::leaf()))
        );
    }

    #[test]
    fn test_round_trip() {
        let t = sample_tree();
        let s = tree_to_dotstring(&t);
        assert_eq!(parse_dotstring(&s), Ok(t));
    }

    #[test]
    fn test_parse_empty_error() {
        assert_eq!(parse_dotstring(""), Err(ParseError::UnexpectedEnd));
    }

    #[test]
    fn test_parse_trailing_chars() {
        // "x.." parses a single node, then "xx" is trailing
        assert_eq!(
            parse_dotstring("x..extra"),
            Err(ParseError::TrailingChars(3))
        );
    }
}

(* Dotstring Parse *)
(* OCaml 99 Problems #40 *)

(* Implementation for example 40 *)

(* Tests *)
let () =
  (* Add tests *)
  print_endline "✓ OCaml tests passed"