Visitor Pattern

The Visitor pattern separates algorithms from the object structure they operate on. It allows adding new operations to existing object structures without modifying those structures.

Key concepts:

• Visitor: Declares visit operations for each element type
• Element: Accepts visitors via accept method
• Concrete elements: Implement accept to call appropriate visit method
• Object structure: Collection of elements that can be visited

The Rust perspective:

• Enums with match provide a simpler alternative for closed hierarchies
• Trait objects enable the classic OOP visitor pattern
• Double dispatch is achieved through accept/visit method pairs
• Closures can replace simple visitors

// Two main approaches:

// 1. Enum-based (preferred in Rust for closed types)
enum Expr {
    Num(i64),
    Add(Box<Expr>, Box<Expr>),
    Mul(Box<Expr>, Box<Expr>),
}

fn eval(expr: &Expr) -> i64 {
    match expr {
        Expr::Num(n) => *n,
        Expr::Add(a, b) => eval(a) + eval(b),
        Expr::Mul(a, b) => eval(a) * eval(b),
    }
}

// 2. Trait-based (for extensible hierarchies)
trait Visitor {
    fn visit_num(&mut self, n: i64);
    fn visit_add(&mut self, left: &dyn Element, right: &dyn Element);
}

Appropriate use cases:

1. AST/syntax tree processing (compilers, interpreters)
2. Document processing (XML, JSON traversal)
3. File system operations
4. Multiple unrelated operations on complex structures
5. Generating different outputs from same structure

When to avoid:

1. Object structure changes frequently
2. Simple operations that match handles well
3. Only one or two operations needed
4. Performance-critical paths (virtual dispatch overhead)

A complete expression system with multiple visitors.

/// Expression AST
#[derive(Debug, Clone)]
pub enum Expr {
    // Literals
    Integer(i64),
    Float(f64),
    Bool(bool),
    String(String),

    // Identifiers
    Variable(String),

    // Binary operations
    Add(Box<Expr>, Box<Expr>),
    Sub(Box<Expr>, Box<Expr>),
    Mul(Box<Expr>, Box<Expr>),
    Div(Box<Expr>, Box<Expr>),
    Mod(Box<Expr>, Box<Expr>),

    // Comparison
    Eq(Box<Expr>, Box<Expr>),
    Ne(Box<Expr>, Box<Expr>),
    Lt(Box<Expr>, Box<Expr>),
    Le(Box<Expr>, Box<Expr>),
    Gt(Box<Expr>, Box<Expr>),
    Ge(Box<Expr>, Box<Expr>),

    // Logical
    And(Box<Expr>, Box<Expr>),
    Or(Box<Expr>, Box<Expr>),
    Not(Box<Expr>),

    // Control flow
    If {
        condition: Box<Expr>,
        then_branch: Box<Expr>,
        else_branch: Option<Box<Expr>>,
    },

    // Functions
    Call {
        name: String,
        args: Vec<Expr>,
    },

    // Let binding
    Let {
        name: String,
        value: Box<Expr>,
        body: Box<Expr>,
    },
}

/// Runtime value
#[derive(Debug, Clone)]
pub enum Value {
    Integer(i64),
    Float(f64),
    Bool(bool),
    String(String),
    Unit,
}

impl std::fmt::Display for Value {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            Value::Integer(n) => write!(f, "{}", n),
            Value::Float(n) => write!(f, "{}", n),
            Value::Bool(b) => write!(f, "{}", b),
            Value::String(s) => write!(f, "\"{}\"", s),
            Value::Unit => write!(f, "()"),
        }
    }
}

/// Visitor trait for expressions
pub trait ExprVisitor {
    type Output;

    fn visit_integer(&mut self, n: i64) -> Self::Output;
    fn visit_float(&mut self, n: f64) -> Self::Output;
    fn visit_bool(&mut self, b: bool) -> Self::Output;
    fn visit_string(&mut self, s: &str) -> Self::Output;
    fn visit_variable(&mut self, name: &str) -> Self::Output;
    fn visit_binary(&mut self, op: BinaryOp, left: &Expr, right: &Expr) -> Self::Output;
    fn visit_not(&mut self, expr: &Expr) -> Self::Output;
    fn visit_if(&mut self, cond: &Expr, then_br: &Expr, else_br: Option<&Expr>) -> Self::Output;
    fn visit_call(&mut self, name: &str, args: &[Expr]) -> Self::Output;
    fn visit_let(&mut self, name: &str, value: &Expr, body: &Expr) -> Self::Output;
}

#[derive(Debug, Clone, Copy)]
pub enum BinaryOp {
    Add, Sub, Mul, Div, Mod,
    Eq, Ne, Lt, Le, Gt, Ge,
    And, Or,
}

impl Expr {
    /// Accept a visitor
    pub fn accept<V: ExprVisitor>(&self, visitor: &mut V) -> V::Output {
        match self {
            Expr::Integer(n) => visitor.visit_integer(*n),
            Expr::Float(n) => visitor.visit_float(*n),
            Expr::Bool(b) => visitor.visit_bool(*b),
            Expr::String(s) => visitor.visit_string(s),
            Expr::Variable(name) => visitor.visit_variable(name),

            Expr::Add(l, r) => visitor.visit_binary(BinaryOp::Add, l, r),
            Expr::Sub(l, r) => visitor.visit_binary(BinaryOp::Sub, l, r),
            Expr::Mul(l, r) => visitor.visit_binary(BinaryOp::Mul, l, r),
            Expr::Div(l, r) => visitor.visit_binary(BinaryOp::Div, l, r),
            Expr::Mod(l, r) => visitor.visit_binary(BinaryOp::Mod, l, r),

            Expr::Eq(l, r) => visitor.visit_binary(BinaryOp::Eq, l, r),
            Expr::Ne(l, r) => visitor.visit_binary(BinaryOp::Ne, l, r),
            Expr::Lt(l, r) => visitor.visit_binary(BinaryOp::Lt, l, r),
            Expr::Le(l, r) => visitor.visit_binary(BinaryOp::Le, l, r),
            Expr::Gt(l, r) => visitor.visit_binary(BinaryOp::Gt, l, r),
            Expr::Ge(l, r) => visitor.visit_binary(BinaryOp::Ge, l, r),

            Expr::And(l, r) => visitor.visit_binary(BinaryOp::And, l, r),
            Expr::Or(l, r) => visitor.visit_binary(BinaryOp::Or, l, r),

            Expr::Not(e) => visitor.visit_not(e),

            Expr::If { condition, then_branch, else_branch } => {
                visitor.visit_if(condition, then_branch, else_branch.as_deref())
            }

            Expr::Call { name, args } => visitor.visit_call(name, args),

            Expr::Let { name, value, body } => visitor.visit_let(name, value, body),
        }
    }
}

/// Interpreter visitor - evaluates expressions
pub struct Interpreter {
    env: std::collections::HashMap<String, Value>,
}

impl Interpreter {
    pub fn new() -> Self {
        Self {
            env: std::collections::HashMap::new(),
        }
    }

    pub fn eval(&mut self, expr: &Expr) -> Result<Value, String> {
        expr.accept(self)
    }

    fn eval_to_int(&mut self, expr: &Expr) -> Result<i64, String> {
        match self.eval(expr)? {
            Value::Integer(n) => Ok(n),
            other => Err(format!("Expected integer, got {:?}", other)),
        }
    }

    fn eval_to_bool(&mut self, expr: &Expr) -> Result<bool, String> {
        match self.eval(expr)? {
            Value::Bool(b) => Ok(b),
            other => Err(format!("Expected bool, got {:?}", other)),
        }
    }
}

impl Default for Interpreter {
    fn default() -> Self {
        Self::new()
    }
}

impl ExprVisitor for Interpreter {
    type Output = Result<Value, String>;

    fn visit_integer(&mut self, n: i64) -> Self::Output {
        Ok(Value::Integer(n))
    }

    fn visit_float(&mut self, n: f64) -> Self::Output {
        Ok(Value::Float(n))
    }

    fn visit_bool(&mut self, b: bool) -> Self::Output {
        Ok(Value::Bool(b))
    }

    fn visit_string(&mut self, s: &str) -> Self::Output {
        Ok(Value::String(s.to_string()))
    }

    fn visit_variable(&mut self, name: &str) -> Self::Output {
        self.env
            .get(name)
            .cloned()
            .ok_or_else(|| format!("Undefined variable: {}", name))
    }

    fn visit_binary(&mut self, op: BinaryOp, left: &Expr, right: &Expr) -> Self::Output {
        match op {
            BinaryOp::Add => {
                let l = self.eval_to_int(left)?;
                let r = self.eval_to_int(right)?;
                Ok(Value::Integer(l + r))
            }
            BinaryOp::Sub => {
                let l = self.eval_to_int(left)?;
                let r = self.eval_to_int(right)?;
                Ok(Value::Integer(l - r))
            }
            BinaryOp::Mul => {
                let l = self.eval_to_int(left)?;
                let r = self.eval_to_int(right)?;
                Ok(Value::Integer(l * r))
            }
            BinaryOp::Div => {
                let l = self.eval_to_int(left)?;
                let r = self.eval_to_int(right)?;
                if r == 0 {
                    Err("Division by zero".to_string())
                } else {
                    Ok(Value::Integer(l / r))
                }
            }
            BinaryOp::Mod => {
                let l = self.eval_to_int(left)?;
                let r = self.eval_to_int(right)?;
                Ok(Value::Integer(l % r))
            }
            BinaryOp::Eq => {
                let l = self.eval_to_int(left)?;
                let r = self.eval_to_int(right)?;
                Ok(Value::Bool(l == r))
            }
            BinaryOp::Ne => {
                let l = self.eval_to_int(left)?;
                let r = self.eval_to_int(right)?;
                Ok(Value::Bool(l != r))
            }
            BinaryOp::Lt => {
                let l = self.eval_to_int(left)?;
                let r = self.eval_to_int(right)?;
                Ok(Value::Bool(l < r))
            }
            BinaryOp::Le => {
                let l = self.eval_to_int(left)?;
                let r = self.eval_to_int(right)?;
                Ok(Value::Bool(l <= r))
            }
            BinaryOp::Gt => {
                let l = self.eval_to_int(left)?;
                let r = self.eval_to_int(right)?;
                Ok(Value::Bool(l > r))
            }
            BinaryOp::Ge => {
                let l = self.eval_to_int(left)?;
                let r = self.eval_to_int(right)?;
                Ok(Value::Bool(l >= r))
            }
            BinaryOp::And => {
                let l = self.eval_to_bool(left)?;
                if !l {
                    Ok(Value::Bool(false))
                } else {
                    let r = self.eval_to_bool(right)?;
                    Ok(Value::Bool(r))
                }
            }
            BinaryOp::Or => {
                let l = self.eval_to_bool(left)?;
                if l {
                    Ok(Value::Bool(true))
                } else {
                    let r = self.eval_to_bool(right)?;
                    Ok(Value::Bool(r))
                }
            }
        }
    }

    fn visit_not(&mut self, expr: &Expr) -> Self::Output {
        let b = self.eval_to_bool(expr)?;
        Ok(Value::Bool(!b))
    }

    fn visit_if(&mut self, cond: &Expr, then_br: &Expr, else_br: Option<&Expr>) -> Self::Output {
        let condition = self.eval_to_bool(cond)?;
        if condition {
            self.eval(then_br)
        } else if let Some(else_expr) = else_br {
            self.eval(else_expr)
        } else {
            Ok(Value::Unit)
        }
    }

    fn visit_call(&mut self, name: &str, args: &[Expr]) -> Self::Output {
        // Built-in functions
        match name {
            "print" => {
                for (i, arg) in args.iter().enumerate() {
                    if i > 0 { print!(" "); }
                    let val = self.eval(arg)?;
                    print!("{}", val);
                }
                println!();
                Ok(Value::Unit)
            }
            "abs" => {
                if args.len() != 1 {
                    return Err("abs expects 1 argument".to_string());
                }
                let n = self.eval_to_int(&args[0])?;
                Ok(Value::Integer(n.abs()))
            }
            "max" => {
                if args.len() != 2 {
                    return Err("max expects 2 arguments".to_string());
                }
                let a = self.eval_to_int(&args[0])?;
                let b = self.eval_to_int(&args[1])?;
                Ok(Value::Integer(a.max(b)))
            }
            "min" => {
                if args.len() != 2 {
                    return Err("min expects 2 arguments".to_string());
                }
                let a = self.eval_to_int(&args[0])?;
                let b = self.eval_to_int(&args[1])?;
                Ok(Value::Integer(a.min(b)))
            }
            _ => Err(format!("Unknown function: {}", name)),
        }
    }

    fn visit_let(&mut self, name: &str, value: &Expr, body: &Expr) -> Self::Output {
        let val = self.eval(value)?;
        let old = self.env.insert(name.to_string(), val);
        let result = self.eval(body);
        // Restore old binding (or remove if didn't exist)
        if let Some(old_val) = old {
            self.env.insert(name.to_string(), old_val);
        } else {
            self.env.remove(name);
        }
        result
    }
}

/// Pretty printer visitor
pub struct PrettyPrinter {
    indent: usize,
    output: String,
}

impl PrettyPrinter {
    pub fn new() -> Self {
        Self {
            indent: 0,
            output: String::new(),
        }
    }

    pub fn print(expr: &Expr) -> String {
        let mut printer = Self::new();
        expr.accept(&mut printer);
        printer.output
    }

    fn indent_str(&self) -> String {
        "  ".repeat(self.indent)
    }
}

impl Default for PrettyPrinter {
    fn default() -> Self {
        Self::new()
    }
}

impl ExprVisitor for PrettyPrinter {
    type Output = ();

    fn visit_integer(&mut self, n: i64) {
        self.output.push_str(&n.to_string());
    }

    fn visit_float(&mut self, n: f64) {
        self.output.push_str(&n.to_string());
    }

    fn visit_bool(&mut self, b: bool) {
        self.output.push_str(if b { "true" } else { "false" });
    }

    fn visit_string(&mut self, s: &str) {
        self.output.push('"');
        self.output.push_str(s);
        self.output.push('"');
    }

    fn visit_variable(&mut self, name: &str) {
        self.output.push_str(name);
    }

    fn visit_binary(&mut self, op: BinaryOp, left: &Expr, right: &Expr) {
        self.output.push('(');
        left.accept(self);
        let op_str = match op {
            BinaryOp::Add => " + ",
            BinaryOp::Sub => " - ",
            BinaryOp::Mul => " * ",
            BinaryOp::Div => " / ",
            BinaryOp::Mod => " % ",
            BinaryOp::Eq => " == ",
            BinaryOp::Ne => " != ",
            BinaryOp::Lt => " < ",
            BinaryOp::Le => " <= ",
            BinaryOp::Gt => " > ",
            BinaryOp::Ge => " >= ",
            BinaryOp::And => " && ",
            BinaryOp::Or => " || ",
        };
        self.output.push_str(op_str);
        right.accept(self);
        self.output.push(')');
    }

    fn visit_not(&mut self, expr: &Expr) {
        self.output.push('!');
        expr.accept(self);
    }

    fn visit_if(&mut self, cond: &Expr, then_br: &Expr, else_br: Option<&Expr>) {
        self.output.push_str("if ");
        cond.accept(self);
        self.output.push_str(" {\n");
        self.indent += 1;
        self.output.push_str(&self.indent_str());
        then_br.accept(self);
        self.indent -= 1;
        self.output.push_str("\n}");
        if let Some(else_expr) = else_br {
            self.output.push_str(" else {\n");
            self.indent += 1;
            self.output.push_str(&self.indent_str());
            else_expr.accept(self);
            self.indent -= 1;
            self.output.push_str("\n}");
        }
    }

    fn visit_call(&mut self, name: &str, args: &[Expr]) {
        self.output.push_str(name);
        self.output.push('(');
        for (i, arg) in args.iter().enumerate() {
            if i > 0 {
                self.output.push_str(", ");
            }
            arg.accept(self);
        }
        self.output.push(')');
    }

    fn visit_let(&mut self, name: &str, value: &Expr, body: &Expr) {
        self.output.push_str("let ");
        self.output.push_str(name);
        self.output.push_str(" = ");
        value.accept(self);
        self.output.push_str(" in\n");
        self.indent += 1;
        self.output.push_str(&self.indent_str());
        body.accept(self);
        self.indent -= 1;
    }
}

/// Variable collector visitor
pub struct VariableCollector {
    variables: std::collections::HashSet<String>,
}

impl VariableCollector {
    pub fn new() -> Self {
        Self {
            variables: std::collections::HashSet::new(),
        }
    }

    pub fn collect(expr: &Expr) -> std::collections::HashSet<String> {
        let mut collector = Self::new();
        expr.accept(&mut collector);
        collector.variables
    }
}

impl Default for VariableCollector {
    fn default() -> Self {
        Self::new()
    }
}

impl ExprVisitor for VariableCollector {
    type Output = ();

    fn visit_integer(&mut self, _: i64) {}
    fn visit_float(&mut self, _: f64) {}
    fn visit_bool(&mut self, _: bool) {}
    fn visit_string(&mut self, _: &str) {}

    fn visit_variable(&mut self, name: &str) {
        self.variables.insert(name.to_string());
    }

    fn visit_binary(&mut self, _: BinaryOp, left: &Expr, right: &Expr) {
        left.accept(self);
        right.accept(self);
    }

    fn visit_not(&mut self, expr: &Expr) {
        expr.accept(self);
    }

    fn visit_if(&mut self, cond: &Expr, then_br: &Expr, else_br: Option<&Expr>) {
        cond.accept(self);
        then_br.accept(self);
        if let Some(e) = else_br {
            e.accept(self);
        }
    }

    fn visit_call(&mut self, _: &str, args: &[Expr]) {
        for arg in args {
            arg.accept(self);
        }
    }

    fn visit_let(&mut self, name: &str, value: &Expr, body: &Expr) {
        value.accept(self);
        // Collect from body, but 'name' is bound there
        body.accept(self);
        // Remove bound variable (it's not free)
        self.variables.remove(name);
    }
}

fn main() {
    // Build expression: let x = 10 in let y = 20 in if x < y { x + y } else { x - y }
    let expr = Expr::Let {
        name: "x".to_string(),
        value: Box::new(Expr::Integer(10)),
        body: Box::new(Expr::Let {
            name: "y".to_string(),
            value: Box::new(Expr::Integer(20)),
            body: Box::new(Expr::If {
                condition: Box::new(Expr::Lt(
                    Box::new(Expr::Variable("x".to_string())),
                    Box::new(Expr::Variable("y".to_string())),
                )),
                then_branch: Box::new(Expr::Add(
                    Box::new(Expr::Variable("x".to_string())),
                    Box::new(Expr::Variable("y".to_string())),
                )),
                else_branch: Some(Box::new(Expr::Sub(
                    Box::new(Expr::Variable("x".to_string())),
                    Box::new(Expr::Variable("y".to_string())),
                ))),
            }),
        }),
    };

    // Pretty print
    println!("Expression:");
    println!("{}", PrettyPrinter::print(&expr));
    println!();

    // Evaluate
    let mut interpreter = Interpreter::new();
    match interpreter.eval(&expr) {
        Ok(value) => println!("Result: {}", value),
        Err(e) => println!("Error: {}", e),
    }

    // Collect variables
    let vars = VariableCollector::collect(&expr);
    println!("Free variables: {:?}", vars);

    // More complex expression with function call
    let expr2 = Expr::Call {
        name: "print".to_string(),
        args: vec![
            Expr::String("The maximum is:".to_string()),
            Expr::Call {
                name: "max".to_string(),
                args: vec![Expr::Integer(42), Expr::Integer(17)],
            },
        ],
    };

    println!("\nExecuting: {}", PrettyPrinter::print(&expr2));
    let _ = interpreter.eval(&expr2);
}

A visitor for traversing and operating on file systems.

use std::path::{Path, PathBuf};
use std::collections::HashMap;

/// File system node
#[derive(Debug, Clone)]
pub enum FsNode {
    File {
        name: String,
        path: PathBuf,
        size: u64,
        extension: Option<String>,
    },
    Directory {
        name: String,
        path: PathBuf,
        children: Vec<FsNode>,
    },
    Symlink {
        name: String,
        path: PathBuf,
        target: PathBuf,
    },
}

impl FsNode {
    pub fn name(&self) -> &str {
        match self {
            FsNode::File { name, .. }
            | FsNode::Directory { name, .. }
            | FsNode::Symlink { name, .. } => name,
        }
    }

    pub fn path(&self) -> &Path {
        match self {
            FsNode::File { path, .. }
            | FsNode::Directory { path, .. }
            | FsNode::Symlink { path, .. } => path,
        }
    }

    /// Accept a visitor
    pub fn accept<V: FsVisitor>(&self, visitor: &mut V) -> V::Output {
        match self {
            FsNode::File { name, path, size, extension } => {
                visitor.visit_file(name, path, *size, extension.as_deref())
            }
            FsNode::Directory { name, path, children } => {
                visitor.visit_directory(name, path, children)
            }
            FsNode::Symlink { name, path, target } => {
                visitor.visit_symlink(name, path, target)
            }
        }
    }
}

/// File system visitor trait
pub trait FsVisitor {
    type Output;

    fn visit_file(
        &mut self,
        name: &str,
        path: &Path,
        size: u64,
        extension: Option<&str>,
    ) -> Self::Output;

    fn visit_directory(
        &mut self,
        name: &str,
        path: &Path,
        children: &[FsNode],
    ) -> Self::Output;

    fn visit_symlink(
        &mut self,
        name: &str,
        path: &Path,
        target: &Path,
    ) -> Self::Output;
}

/// Calculate total size
pub struct SizeCalculator {
    total_size: u64,
    file_count: usize,
    dir_count: usize,
}

impl SizeCalculator {
    pub fn new() -> Self {
        Self {
            total_size: 0,
            file_count: 0,
            dir_count: 0,
        }
    }

    pub fn calculate(root: &FsNode) -> (u64, usize, usize) {
        let mut calc = Self::new();
        root.accept(&mut calc);
        (calc.total_size, calc.file_count, calc.dir_count)
    }
}

impl Default for SizeCalculator {
    fn default() -> Self {
        Self::new()
    }
}

impl FsVisitor for SizeCalculator {
    type Output = u64;

    fn visit_file(&mut self, _: &str, _: &Path, size: u64, _: Option<&str>) -> u64 {
        self.total_size += size;
        self.file_count += 1;
        size
    }

    fn visit_directory(&mut self, _: &str, _: &Path, children: &[FsNode]) -> u64 {
        self.dir_count += 1;
        let mut dir_size = 0;
        for child in children {
            dir_size += child.accept(self);
        }
        dir_size
    }

    fn visit_symlink(&mut self, _: &str, _: &Path, _: &Path) -> u64 {
        0 // Symlinks don't contribute to size
    }
}

/// Find files by extension
pub struct ExtensionFinder {
    target_ext: String,
    found: Vec<PathBuf>,
}

impl ExtensionFinder {
    pub fn find(root: &FsNode, extension: &str) -> Vec<PathBuf> {
        let mut finder = Self {
            target_ext: extension.to_lowercase(),
            found: Vec::new(),
        };
        root.accept(&mut finder);
        finder.found
    }
}

impl FsVisitor for ExtensionFinder {
    type Output = ();

    fn visit_file(&mut self, _: &str, path: &Path, _: u64, extension: Option<&str>) {
        if let Some(ext) = extension {
            if ext.to_lowercase() == self.target_ext {
                self.found.push(path.to_path_buf());
            }
        }
    }

    fn visit_directory(&mut self, _: &str, _: &Path, children: &[FsNode]) {
        for child in children {
            child.accept(self);
        }
    }

    fn visit_symlink(&mut self, _: &str, _: &Path, _: &Path) {}
}

/// Generate file listing
pub struct TreePrinter {
    output: String,
    prefix: String,
}

impl TreePrinter {
    pub fn print(root: &FsNode) -> String {
        let mut printer = Self {
            output: String::new(),
            prefix: String::new(),
        };
        root.accept(&mut printer);
        printer.output
    }
}

impl FsVisitor for TreePrinter {
    type Output = ();

    fn visit_file(&mut self, name: &str, _: &Path, size: u64, _: Option<&str>) {
        self.output.push_str(&format!("{}📄 {} ({} bytes)\n", self.prefix, name, size));
    }

    fn visit_directory(&mut self, name: &str, _: &Path, children: &[FsNode]) {
        self.output.push_str(&format!("{}📁 {}/\n", self.prefix, name));

        let old_prefix = self.prefix.clone();
        self.prefix = format!("{}  ", self.prefix);

        for child in children {
            child.accept(self);
        }

        self.prefix = old_prefix;
    }

    fn visit_symlink(&mut self, name: &str, _: &Path, target: &Path) {
        self.output.push_str(&format!(
            "{}🔗 {} -> {}\n",
            self.prefix,
            name,
            target.display()
        ));
    }
}

/// Statistics by file type
pub struct TypeStatistics {
    stats: HashMap<String, (usize, u64)>,
}

impl TypeStatistics {
    pub fn collect(root: &FsNode) -> HashMap<String, (usize, u64)> {
        let mut stats = Self {
            stats: HashMap::new(),
        };
        root.accept(&mut stats);
        stats.stats
    }
}

impl FsVisitor for TypeStatistics {
    type Output = ();

    fn visit_file(&mut self, _: &str, _: &Path, size: u64, extension: Option<&str>) {
        let ext = extension.unwrap_or("(no extension)").to_lowercase();
        let entry = self.stats.entry(ext).or_insert((0, 0));
        entry.0 += 1;
        entry.1 += size;
    }

    fn visit_directory(&mut self, _: &str, _: &Path, children: &[FsNode]) {
        for child in children {
            child.accept(self);
        }
    }

    fn visit_symlink(&mut self, _: &str, _: &Path, _: &Path) {}
}

/// Duplicate file finder (by size)
pub struct DuplicateFinder {
    size_map: HashMap<u64, Vec<PathBuf>>,
}

impl DuplicateFinder {
    pub fn find_potential_duplicates(root: &FsNode) -> Vec<(u64, Vec<PathBuf>)> {
        let mut finder = Self {
            size_map: HashMap::new(),
        };
        root.accept(&mut finder);

        finder
            .size_map
            .into_iter()
            .filter(|(_, paths)| paths.len() > 1)
            .collect()
    }
}

impl FsVisitor for DuplicateFinder {
    type Output = ();

    fn visit_file(&mut self, _: &str, path: &Path, size: u64, _: Option<&str>) {
        self.size_map
            .entry(size)
            .or_insert_with(Vec::new)
            .push(path.to_path_buf());
    }

    fn visit_directory(&mut self, _: &str, _: &Path, children: &[FsNode]) {
        for child in children {
            child.accept(self);
        }
    }

    fn visit_symlink(&mut self, _: &str, _: &Path, _: &Path) {}
}

fn main() {
    // Build a sample file system tree
    let fs_tree = FsNode::Directory {
        name: "project".to_string(),
        path: PathBuf::from("/home/user/project"),
        children: vec![
            FsNode::File {
                name: "Cargo.toml".to_string(),
                path: PathBuf::from("/home/user/project/Cargo.toml"),
                size: 512,
                extension: Some("toml".to_string()),
            },
            FsNode::File {
                name: "README.md".to_string(),
                path: PathBuf::from("/home/user/project/README.md"),
                size: 2048,
                extension: Some("md".to_string()),
            },
            FsNode::Directory {
                name: "src".to_string(),
                path: PathBuf::from("/home/user/project/src"),
                children: vec![
                    FsNode::File {
                        name: "main.rs".to_string(),
                        path: PathBuf::from("/home/user/project/src/main.rs"),
                        size: 1024,
                        extension: Some("rs".to_string()),
                    },
                    FsNode::File {
                        name: "lib.rs".to_string(),
                        path: PathBuf::from("/home/user/project/src/lib.rs"),
                        size: 4096,
                        extension: Some("rs".to_string()),
                    },
                    FsNode::File {
                        name: "utils.rs".to_string(),
                        path: PathBuf::from("/home/user/project/src/utils.rs"),
                        size: 2048,
                        extension: Some("rs".to_string()),
                    },
                ],
            },
            FsNode::Directory {
                name: "tests".to_string(),
                path: PathBuf::from("/home/user/project/tests"),
                children: vec![FsNode::File {
                    name: "integration.rs".to_string(),
                    path: PathBuf::from("/home/user/project/tests/integration.rs"),
                    size: 2048,
                    extension: Some("rs".to_string()),
                }],
            },
            FsNode::Symlink {
                name: "latest".to_string(),
                path: PathBuf::from("/home/user/project/latest"),
                target: PathBuf::from("./target/release/app"),
            },
        ],
    };

    // Print tree structure
    println!("File System Tree:");
    println!("{}", TreePrinter::print(&fs_tree));

    // Calculate size
    let (total_size, file_count, dir_count) = SizeCalculator::calculate(&fs_tree);
    println!("Statistics:");
    println!("  Total size: {} bytes", total_size);
    println!("  Files: {}", file_count);
    println!("  Directories: {}", dir_count);

    // Find Rust files
    let rust_files = ExtensionFinder::find(&fs_tree, "rs");
    println!("\nRust files:");
    for path in &rust_files {
        println!("  {}", path.display());
    }

    // Type statistics
    let type_stats = TypeStatistics::collect(&fs_tree);
    println!("\nFiles by type:");
    for (ext, (count, size)) in &type_stats {
        println!("  .{}: {} files, {} bytes", ext, count, size);
    }

    // Find potential duplicates
    let duplicates = DuplicateFinder::find_potential_duplicates(&fs_tree);
    if !duplicates.is_empty() {
        println!("\nPotential duplicates (same size):");
        for (size, paths) in &duplicates {
            println!("  {} bytes:", size);
            for path in paths {
                println!("    {}", path.display());
            }
        }
    }
}

A visitor for HTML/DOM manipulation.

use std::collections::HashMap;

/// HTML Node types
#[derive(Debug, Clone)]
pub enum HtmlNode {
    Element {
        tag: String,
        attributes: HashMap<String, String>,
        children: Vec<HtmlNode>,
    },
    Text(String),
    Comment(String),
}

impl HtmlNode {
    pub fn element(tag: &str) -> Self {
        HtmlNode::Element {
            tag: tag.to_string(),
            attributes: HashMap::new(),
            children: Vec::new(),
        }
    }

    pub fn with_attr(mut self, key: &str, value: &str) -> Self {
        if let HtmlNode::Element { ref mut attributes, .. } = self {
            attributes.insert(key.to_string(), value.to_string());
        }
        self
    }

    pub fn with_child(mut self, child: HtmlNode) -> Self {
        if let HtmlNode::Element { ref mut children, .. } = self {
            children.push(child);
        }
        self
    }

    pub fn with_text(self, text: &str) -> Self {
        self.with_child(HtmlNode::Text(text.to_string()))
    }

    pub fn accept<V: HtmlVisitor>(&self, visitor: &mut V) -> V::Output {
        match self {
            HtmlNode::Element { tag, attributes, children } => {
                visitor.visit_element(tag, attributes, children)
            }
            HtmlNode::Text(text) => visitor.visit_text(text),
            HtmlNode::Comment(comment) => visitor.visit_comment(comment),
        }
    }
}

/// HTML Visitor trait
pub trait HtmlVisitor {
    type Output;

    fn visit_element(
        &mut self,
        tag: &str,
        attributes: &HashMap<String, String>,
        children: &[HtmlNode],
    ) -> Self::Output;

    fn visit_text(&mut self, text: &str) -> Self::Output;
    fn visit_comment(&mut self, comment: &str) -> Self::Output;
}

/// Render HTML to string
pub struct HtmlRenderer {
    output: String,
    indent: usize,
    pretty: bool,
}

impl HtmlRenderer {
    pub fn render(node: &HtmlNode, pretty: bool) -> String {
        let mut renderer = Self {
            output: String::new(),
            indent: 0,
            pretty,
        };
        node.accept(&mut renderer);
        renderer.output
    }

    fn newline(&self) -> &str {
        if self.pretty { "\n" } else { "" }
    }

    fn indent_str(&self) -> String {
        if self.pretty {
            "  ".repeat(self.indent)
        } else {
            String::new()
        }
    }
}

impl HtmlVisitor for HtmlRenderer {
    type Output = ();

    fn visit_element(
        &mut self,
        tag: &str,
        attributes: &HashMap<String, String>,
        children: &[HtmlNode],
    ) {
        self.output.push_str(&self.indent_str());
        self.output.push('<');
        self.output.push_str(tag);

        for (key, value) in attributes {
            self.output.push(' ');
            self.output.push_str(key);
            self.output.push_str("=\"");
            self.output.push_str(&html_escape(value));
            self.output.push('"');
        }

        // Void elements (self-closing)
        let void_elements = ["br", "hr", "img", "input", "meta", "link"];
        if void_elements.contains(&tag.as_str()) && children.is_empty() {
            self.output.push_str(" />");
            self.output.push_str(self.newline());
            return;
        }

        self.output.push('>');
        self.output.push_str(self.newline());

        self.indent += 1;
        for child in children {
            child.accept(self);
        }
        self.indent -= 1;

        self.output.push_str(&self.indent_str());
        self.output.push_str("</");
        self.output.push_str(tag);
        self.output.push('>');
        self.output.push_str(self.newline());
    }

    fn visit_text(&mut self, text: &str) {
        self.output.push_str(&self.indent_str());
        self.output.push_str(&html_escape(text));
        self.output.push_str(self.newline());
    }

    fn visit_comment(&mut self, comment: &str) {
        self.output.push_str(&self.indent_str());
        self.output.push_str("<!-- ");
        self.output.push_str(comment);
        self.output.push_str(" -->");
        self.output.push_str(self.newline());
    }
}

fn html_escape(s: &str) -> String {
    s.replace('&', "&amp;")
        .replace('<', "&lt;")
        .replace('>', "&gt;")
        .replace('"', "&quot;")
}

/// Extract all text content
pub struct TextExtractor {
    text: Vec<String>,
}

impl TextExtractor {
    pub fn extract(node: &HtmlNode) -> String {
        let mut extractor = Self { text: Vec::new() };
        node.accept(&mut extractor);
        extractor.text.join(" ")
    }
}

impl HtmlVisitor for TextExtractor {
    type Output = ();

    fn visit_element(&mut self, _: &str, _: &HashMap<String, String>, children: &[HtmlNode]) {
        for child in children {
            child.accept(self);
        }
    }

    fn visit_text(&mut self, text: &str) {
        let trimmed = text.trim();
        if !trimmed.is_empty() {
            self.text.push(trimmed.to_string());
        }
    }

    fn visit_comment(&mut self, _: &str) {}
}

/// Find elements by tag name
pub struct ElementFinder {
    target_tag: String,
    found: Vec<HtmlNode>,
}

impl ElementFinder {
    pub fn find_by_tag(node: &HtmlNode, tag: &str) -> Vec<HtmlNode> {
        let mut finder = Self {
            target_tag: tag.to_lowercase(),
            found: Vec::new(),
        };
        node.accept(&mut finder);
        finder.found
    }
}

impl HtmlVisitor for ElementFinder {
    type Output = ();

    fn visit_element(
        &mut self,
        tag: &str,
        attributes: &HashMap<String, String>,
        children: &[HtmlNode],
    ) {
        if tag.to_lowercase() == self.target_tag {
            self.found.push(HtmlNode::Element {
                tag: tag.to_string(),
                attributes: attributes.clone(),
                children: children.to_vec(),
            });
        }

        for child in children {
            child.accept(self);
        }
    }

    fn visit_text(&mut self, _: &str) {}
    fn visit_comment(&mut self, _: &str) {}
}

/// Link extractor for web scraping
pub struct LinkExtractor {
    links: Vec<(String, Option<String>)>,
}

impl LinkExtractor {
    pub fn extract_links(node: &HtmlNode) -> Vec<(String, Option<String>)> {
        let mut extractor = Self { links: Vec::new() };
        node.accept(&mut extractor);
        extractor.links
    }
}

impl HtmlVisitor for LinkExtractor {
    type Output = ();

    fn visit_element(
        &mut self,
        tag: &str,
        attributes: &HashMap<String, String>,
        children: &[HtmlNode],
    ) {
        if tag.to_lowercase() == "a" {
            if let Some(href) = attributes.get("href") {
                // Extract link text
                let text = TextExtractor::extract(&HtmlNode::Element {
                    tag: tag.to_string(),
                    attributes: attributes.clone(),
                    children: children.to_vec(),
                });
                let text = if text.is_empty() { None } else { Some(text) };
                self.links.push((href.clone(), text));
            }
        }

        for child in children {
            child.accept(self);
        }
    }

    fn visit_text(&mut self, _: &str) {}
    fn visit_comment(&mut self, _: &str) {}
}

fn main() {
    // Build an HTML document
    let html = HtmlNode::element("html")
        .with_child(
            HtmlNode::element("head")
                .with_child(
                    HtmlNode::element("title")
                        .with_text("Sample Page")
                )
                .with_child(
                    HtmlNode::element("meta")
                        .with_attr("charset", "utf-8")
                )
        )
        .with_child(
            HtmlNode::element("body")
                .with_child(
                    HtmlNode::element("h1")
                        .with_attr("class", "header")
                        .with_text("Welcome")
                )
                .with_child(
                    HtmlNode::element("p")
                        .with_text("This is a ")
                        .with_child(
                            HtmlNode::element("a")
                                .with_attr("href", "https://example.com")
                                .with_text("sample link")
                        )
                        .with_child(HtmlNode::Text(" in a paragraph.".to_string()))
                )
                .with_child(
                    HtmlNode::element("ul")
                        .with_child(
                            HtmlNode::element("li")
                                .with_child(
                                    HtmlNode::element("a")
                                        .with_attr("href", "/page1")
                                        .with_text("Page 1")
                                )
                        )
                        .with_child(
                            HtmlNode::element("li")
                                .with_child(
                                    HtmlNode::element("a")
                                        .with_attr("href", "/page2")
                                        .with_text("Page 2")
                                )
                        )
                )
                .with_child(HtmlNode::Comment("Footer goes here".to_string()))
        );

    // Render to HTML
    println!("Rendered HTML:");
    println!("{}", HtmlRenderer::render(&html, true));

    // Extract all text
    println!("Extracted text:");
    println!("{}", TextExtractor::extract(&html));

    // Find all links
    println!("\nFound links:");
    for (href, text) in LinkExtractor::extract_links(&html) {
        println!("  {} -> {:?}", href, text);
    }

    // Find specific elements
    let paragraphs = ElementFinder::find_by_tag(&html, "p");
    println!("\nFound {} paragraph(s)", paragraphs.len());
}

| Approach | Add New Types | Add New Operations | Performance | Complexity |

|----------|---------------|-------------------|-------------|------------|

| Visitor pattern | Hard | Easy | Good | High |

| Pattern matching | Easy | Hard | Best | Low |

| Extension traits | Medium | Medium | Good | Medium |

| Double dispatch | Hard | Easy | Good | High |

1. Prefer enums with match for closed hierarchies - More idiomatic in Rust
2. Use visitor for truly open-ended operations - When new operations are common
3. Consider fold/reduce patterns - Often simpler than full visitor
4. Document traversal order - Pre-order, post-order, etc.
5. Provide default implementations - For partial visitors
6. Use associated types for output - Cleaner than generic parameters

| Pattern | Dispatch | Memory | Cache Friendliness |

|---------|----------|--------|-------------------|

| Enum match | Static | Stack | Excellent |

| Trait visitor | Dynamic | Heap possible | Good |

| Closure visitor | Indirect | Stack/Heap | Good |

1. Create a shape visitor that calculates area and perimeter
2. Build a JSON value visitor for serialization

1. Implement a Markdown AST with visitors for HTML and plain text output
2. Create a CSS selector visitor for DOM querying

1. Build an SQL query optimizer using visitor transformations
2. Implement a type checker visitor for a simple language

• Visitor Pattern - Refactoring Guru
• Expression Problem
• Rust Design Patterns
• Double Dispatch

• syn crate: Rust syntax tree visitor for procedural macros
• serde: Data format visitors for serialization
• regex-syntax: AST visitors for regex optimization
• swc: JavaScript/TypeScript AST visitors
• tree-sitter: Syntax tree traversal