# Visitor

> Add new operations over a fixed set of node types without editing those types, by routing each node to a type-specific method on a visitor object.

- kind: pattern
- category: behavioral
- aliases: Double Dispatch
- canonical: https://aipatterns.dev/design-patterns/visitor
- inspired-by: https://refactoring.guru/design-patterns/visitor

## Intent

Separate operations from the object structure they run over. Each element type gets one `accept` method that calls back the matching method on a visitor, so a new operation is a new visitor class and the element classes stay untouched. The pattern makes new operations cheap and new element types expensive.

## Forces

- **A stable set of node types** vs **a growing list of operations**: an expression tree keeps the same four node kinds while evaluation, pretty-printing, linting and serialization pile up.
- **Cohesive operations** vs **cohesive types**: putting `evaluate`, `explain` and `toJson` on every node scatters each operation across many classes.
- **Type-specific behavior** vs **no type checks**: without help from the language, picking behavior by concrete type means `instanceof` chains that miss new types silently.
- **Encapsulation** vs **access**: a visitor needs to read each element's data, which pushes elements to expose more than they otherwise would.

## Therefore

**Give every element an `accept(visitor)` method that calls `visitor.visitX(this)`, and put each operation in its own visitor class with one method per element type.**

The two calls make up *double dispatch*: `accept` resolves the element's type, and `visitX` resolves the operation. The visitor interface lists every element type, so the compiler reports any visitor that misses one. In languages with sum types and exhaustive pattern matching, such as Rust, Kotlin, Scala, Swift, TypeScript discriminated unions or Java 21 sealed interfaces, a `switch` over the type gives you the same guarantee with no `accept` methods at all.

## Structure

```mermaid
classDiagram
  class Policy {
    <<interface>>
    +accept(v) R
  }
  class HasRole {
    -String role
    +accept(v) R
  }
  class AllOf {
    -List children
    +accept(v) R
  }
  class Not {
    -Policy inner
    +accept(v) R
  }
  class PolicyVisitor {
    <<interface>>
    +visitHasRole(p) R
    +visitAllOf(p) R
    +visitNot(p) R
  }
  class Evaluator {
    -Set roles
    +visitHasRole(p) bool
  }
  class Explainer {
    +visitHasRole(p) String
  }
  Policy <|.. HasRole
  Policy <|.. AllOf
  Policy <|.. Not
  PolicyVisitor <|.. Evaluator
  PolicyVisitor <|.. Explainer
  Policy ..> PolicyVisitor : accept calls visitX
```

### Participants

- **Element** (`Policy`): declares `accept(visitor)`.
- **Concrete elements** (`HasRole`, `AllOf`, `AnyOf`, `Not`): each implements `accept` by calling its own `visitX` method. They contain no operation logic.
- **Visitor** (`PolicyVisitor`): one method per concrete element type. Generic over the result type where the language allows it.
- **Concrete visitors** (`Evaluator`, `Explainer`): one operation each, with a case for every element type.
- **Object structure**: the tree or collection being visited. Composite visitors recurse into children by calling `child.accept(this)`.

## Use it when

- The element hierarchy is stable and owned by you, and new operations over it arrive often, as with ASTs, query plans, document models and rule trees.
- Operations need different behavior per node type, and you want the compiler to flag a missing case.
- Several unrelated operations would otherwise bloat every element class with methods that belong to other layers, such as rendering, persistence or metrics.
- An operation needs to accumulate state across a whole traversal, such as collecting every referenced role or counting nodes by kind.

## Do not use it when

- The element types are a closed set defined in your own code, and each operation visits every type once. Model the elements as a sealed or union type and write one `switch`/`match` per operation: it is shorter, keeps each operation in one function, and the compiler still reports a missing case. This covers TypeScript (discriminated unions with a `never` check), Rust, Kotlin, Swift, Scala and Java 21+. When the classes cannot share a union - different owners, different packages - this bullet does not apply.
- New element types arrive more often than new operations. Every new element type forces a new method on the visitor interface and an edit to every visitor. Put the operation on the element instead, with plain polymorphism.
- You don't own the element classes and can't add `accept`. Use a type switch, a lookup by type, or an adapter.
- There is one operation. A method on each element (plain polymorphism) is simpler.
- The structure is a flat list of one type. Use a loop or [Iterator](https://aipatterns.dev/design-patterns/iterator.md).

## Application grill

**Inspect first:** the node set's stability (visitors assume it is frozen) and who would add node types; existing pattern matching or exhaustive switches over the same types; whether the code is compiler-shaped (ASTs, documents) where visitors are natural.

**Missing pieces:** none beyond the language: in languages with discriminated unions, an exhaustive switch or pattern match is the modern form and gives compiler errors on new nodes for free.

**Ask before you build:**

- **Scale:** how often are new node types added versus new operations - visitors pay off only when operations change more often than types?
- **Performance:** does dispatch overhead matter in tight AST loops - measure before choosing the shape?
- **Reliability:** what does a partial visitor do for a node it does not handle - default case or type error?
- **Budget:** an exhaustive switch gives compiler-enforced completeness without an interface - is the visitor interface buying anything beyond that?
- **Implementation:** does the visitor carry per-node return types, and who keeps the double-dispatch glue honest?

## Implementation steps

1. Confirm the set of element types is stable and that new operations, not new types, are the expected change.
2. Declare the visitor interface with one `visitX` method per concrete element. Make it generic over the return type if the language allows, to avoid mutable result fields.
3. Add `accept(visitor)` to the element interface, and implement it in each element as a single call to its own `visitX`.
4. Move each operation, often a [Switch Statements](https://aipatterns.dev/refactoring/smells/switch-statements.md) smell over node types, into a visitor class, one method per case.
5. Decide who traverses children. Usually the visitor recurses by calling `child.accept(this)`, which lets it control order and short-circuit.
6. Delete the old type checks and run the tests.

## Example

An internal admin tool stores access rules as small expression trees such as "admin, or billing and not a contractor". The same tree must be evaluated against a user and explained in plain text on the settings page.

```ts title="policy.ts"
interface PolicyVisitor<R> {
  visitHasRole(p: HasRole): R;
  visitAllOf(p: AllOf): R;
  visitAnyOf(p: AnyOf): R;
  visitNot(p: Not): R;
}

interface Policy {
  accept<R>(v: PolicyVisitor<R>): R;
}

class HasRole implements Policy {
  constructor(readonly role: string) {}
  accept<R>(v: PolicyVisitor<R>): R { return v.visitHasRole(this); }
}
class AllOf implements Policy {
  constructor(readonly children: Policy[]) {}
  accept<R>(v: PolicyVisitor<R>): R { return v.visitAllOf(this); }
}
class AnyOf implements Policy {
  constructor(readonly children: Policy[]) {}
  accept<R>(v: PolicyVisitor<R>): R { return v.visitAnyOf(this); }
}
class Not implements Policy {
  constructor(readonly inner: Policy) {}
  accept<R>(v: PolicyVisitor<R>): R { return v.visitNot(this); }
}

class Evaluator implements PolicyVisitor<boolean> {
  constructor(private readonly roles: ReadonlySet<string>) {}
  visitHasRole(p: HasRole): boolean { return this.roles.has(p.role); }
  visitAllOf(p: AllOf): boolean { return p.children.every((c) => c.accept(this)); }
  visitAnyOf(p: AnyOf): boolean { return p.children.some((c) => c.accept(this)); }
  visitNot(p: Not): boolean { return !p.inner.accept(this); }
}

class Explainer implements PolicyVisitor<string> {
  visitHasRole(p: HasRole): string { return p.role; }
  visitAllOf(p: AllOf): string { return `(${p.children.map((c) => c.accept(this)).join(" AND ")})`; }
  visitAnyOf(p: AnyOf): string { return p.children.map((c) => c.accept(this)).join(" OR "); }
  visitNot(p: Not): string { return `NOT ${p.inner.accept(this)}`; }
}

const canIssueRefunds = new AnyOf([
  new HasRole("admin"),
  new AllOf([new HasRole("billing"), new Not(new HasRole("contractor"))]),
]);

console.log(canIssueRefunds.accept(new Explainer())); // admin OR (billing AND NOT contractor)
console.log(canIssueRefunds.accept(new Evaluator(new Set(["billing"])))); // true
console.log(canIssueRefunds.accept(new Evaluator(new Set(["billing", "contractor"])))); // false
```

```python title="policy.py"
from __future__ import annotations

from dataclasses import dataclass
from typing import Generic, Protocol, TypeVar

R = TypeVar("R", covariant=True)

class PolicyVisitor(Protocol[R]):
    def visit_has_role(self, p: HasRole) -> R: ...
    def visit_all_of(self, p: AllOf) -> R: ...
    def visit_any_of(self, p: AnyOf) -> R: ...
    def visit_not(self, p: Not) -> R: ...

@dataclass(frozen=True)
class HasRole:
    role: str
    def accept(self, v: PolicyVisitor[R]) -> R: return v.visit_has_role(self)

@dataclass(frozen=True)
class AllOf:
    children: tuple[Policy, ...]
    def accept(self, v: PolicyVisitor[R]) -> R: return v.visit_all_of(self)

@dataclass(frozen=True)
class AnyOf:
    children: tuple[Policy, ...]
    def accept(self, v: PolicyVisitor[R]) -> R: return v.visit_any_of(self)

@dataclass(frozen=True)
class Not:
    inner: Policy
    def accept(self, v: PolicyVisitor[R]) -> R: return v.visit_not(self)

Policy = HasRole | AllOf | AnyOf | Not

class Evaluator:
    def __init__(self, roles: set[str]) -> None:
        self.roles = roles

    def visit_has_role(self, p: HasRole) -> bool: return p.role in self.roles
    def visit_all_of(self, p: AllOf) -> bool: return all(c.accept(self) for c in p.children)
    def visit_any_of(self, p: AnyOf) -> bool: return any(c.accept(self) for c in p.children)
    def visit_not(self, p: Not) -> bool: return not p.inner.accept(self)

class Explainer:
    def visit_has_role(self, p: HasRole) -> str: return p.role
    def visit_all_of(self, p: AllOf) -> str:
        return "(" + " AND ".join(c.accept(self) for c in p.children) + ")"
    def visit_any_of(self, p: AnyOf) -> str: return " OR ".join(c.accept(self) for c in p.children)
    def visit_not(self, p: Not) -> str: return f"NOT {p.inner.accept(self)}"

if __name__ == "__main__":
    can_issue_refunds = AnyOf((
        HasRole("admin"),
        AllOf((HasRole("billing"), Not(HasRole("contractor")))),
    ))
    print(can_issue_refunds.accept(Explainer()))  # admin OR (billing AND NOT contractor)
    print(can_issue_refunds.accept(Evaluator({"billing"})))  # True
    print(can_issue_refunds.accept(Evaluator({"billing", "contractor"})))  # False
```

```go title="policy.go"
package main

import (
	"fmt"
	"strings"
)

// Go methods can't be generic, so visitors store their result in a field.
// Idiomatic Go often skips Visitor and uses a type switch over Policy instead.
type PolicyVisitor interface {
	VisitHasRole(p HasRole)
	VisitAllOf(p AllOf)
	VisitAnyOf(p AnyOf)
	VisitNot(p Not)
}

type Policy interface{ Accept(v PolicyVisitor) }

type HasRole struct{ Role string }
type AllOf struct{ Children []Policy }
type AnyOf struct{ Children []Policy }
type Not struct{ Inner Policy }

func (p HasRole) Accept(v PolicyVisitor) { v.VisitHasRole(p) }
func (p AllOf) Accept(v PolicyVisitor)   { v.VisitAllOf(p) }
func (p AnyOf) Accept(v PolicyVisitor)   { v.VisitAnyOf(p) }
func (p Not) Accept(v PolicyVisitor)     { v.VisitNot(p) }

type Evaluator struct {
	Roles  map[string]bool
	result bool
}

func (e *Evaluator) eval(p Policy) bool { p.Accept(e); return e.result }

func (e *Evaluator) VisitHasRole(p HasRole) { e.result = e.Roles[p.Role] }
func (e *Evaluator) VisitNot(p Not)         { e.result = !e.eval(p.Inner) }
func (e *Evaluator) VisitAllOf(p AllOf) {
	ok := true
	for _, c := range p.Children {
		ok = ok && e.eval(c)
	}
	e.result = ok
}
func (e *Evaluator) VisitAnyOf(p AnyOf) {
	ok := false
	for _, c := range p.Children {
		ok = ok || e.eval(c)
	}
	e.result = ok
}

type Explainer struct{ out string }

func (x *Explainer) explain(p Policy) string { p.Accept(x); return x.out }
func (x *Explainer) join(ps []Policy, sep string) string {
	parts := make([]string, len(ps))
	for i, c := range ps {
		parts[i] = x.explain(c)
	}
	return strings.Join(parts, sep)
}

func (x *Explainer) VisitHasRole(p HasRole) { x.out = p.Role }
func (x *Explainer) VisitAllOf(p AllOf)     { x.out = "(" + x.join(p.Children, " AND ") + ")" }
func (x *Explainer) VisitAnyOf(p AnyOf)     { x.out = x.join(p.Children, " OR ") }
func (x *Explainer) VisitNot(p Not)         { x.out = "NOT " + x.explain(p.Inner) }

func main() {
	canIssueRefunds := AnyOf{[]Policy{
		HasRole{"admin"},
		AllOf{[]Policy{HasRole{"billing"}, Not{HasRole{"contractor"}}}},
	}}
	fmt.Println((&Explainer{}).explain(canIssueRefunds)) // admin OR (billing AND NOT contractor)
	billing := &Evaluator{Roles: map[string]bool{"billing": true}}
	fmt.Println(billing.eval(canIssueRefunds)) // true
	contractor := &Evaluator{Roles: map[string]bool{"billing": true, "contractor": true}}
	fmt.Println(contractor.eval(canIssueRefunds)) // false
}
```

```java title="Policies.java"
import java.util.List;
import java.util.Set;
import java.util.stream.Collectors;

public class Policies {
    interface PolicyVisitor<R> {
        R visitHasRole(HasRole p);
        R visitAllOf(AllOf p);
        R visitAnyOf(AnyOf p);
        R visitNot(Not p);
    }

    interface Policy {
        <R> R accept(PolicyVisitor<R> v);
    }

    record HasRole(String role) implements Policy {
        public <R> R accept(PolicyVisitor<R> v) { return v.visitHasRole(this); }
    }
    record AllOf(List<Policy> children) implements Policy {
        public <R> R accept(PolicyVisitor<R> v) { return v.visitAllOf(this); }
    }
    record AnyOf(List<Policy> children) implements Policy {
        public <R> R accept(PolicyVisitor<R> v) { return v.visitAnyOf(this); }
    }
    record Not(Policy inner) implements Policy {
        public <R> R accept(PolicyVisitor<R> v) { return v.visitNot(this); }
    }

    record Evaluator(Set<String> roles) implements PolicyVisitor<Boolean> {
        public Boolean visitHasRole(HasRole p) { return roles.contains(p.role()); }
        public Boolean visitAllOf(AllOf p) { return p.children().stream().allMatch(c -> c.accept(this)); }
        public Boolean visitAnyOf(AnyOf p) { return p.children().stream().anyMatch(c -> c.accept(this)); }
        public Boolean visitNot(Not p) { return !p.inner().accept(this); }
    }

    static final class Explainer implements PolicyVisitor<String> {
        public String visitHasRole(HasRole p) { return p.role(); }
        public String visitAllOf(AllOf p) { return "(" + join(p.children(), " AND ") + ")"; }
        public String visitAnyOf(AnyOf p) { return join(p.children(), " OR "); }
        public String visitNot(Not p) { return "NOT " + p.inner().accept(this); }

        private String join(List<Policy> ps, String sep) {
            return ps.stream().map(c -> c.accept(this)).collect(Collectors.joining(sep));
        }
    }

    public static void main(String[] args) {
        Policy canIssueRefunds = new AnyOf(List.of(
            new HasRole("admin"),
            new AllOf(List.of(new HasRole("billing"), new Not(new HasRole("contractor"))))));

        System.out.println(canIssueRefunds.accept(new Explainer())); // admin OR (billing AND NOT contractor)
        System.out.println(canIssueRefunds.accept(new Evaluator(Set.of("billing")))); // true
        System.out.println(canIssueRefunds.accept(new Evaluator(Set.of("billing", "contractor")))); // false
    }
}
```

## Trade-offs

**Gains**
- A new operation is one new class; element classes don't change.
- Each operation's logic sits in one place instead of being spread across every element.
- The compiler reports any visitor that misses an element type.
- Visitors can carry state across a traversal, such as a symbol table, counters or an output buffer.

**Costs**
- Adding an element type means a new method on the visitor interface and an edit to every visitor. This is the price, and it grows with each visitor you write.
- Elements must expose the data visitors read, which weakens encapsulation.
- The `accept`/`visitX` round trip is indirect and confuses readers who haven't seen double dispatch.
- In languages without generic methods, such as Go, results travel through mutable fields, which is error-prone.
- Pattern matching over a closed type does the same job with less code in most modern languages.

## Relations

- [Composite](https://aipatterns.dev/design-patterns/composite.md) is the usual structure a visitor walks; composite elements pass the visitor to their children.
- [Iterator](https://aipatterns.dev/design-patterns/iterator.md) walks a collection without caring about element types. Visitor exists for structures whose elements have different types and need different handling.
- [Command](https://aipatterns.dev/design-patterns/command.md) wraps one action as an object. A visitor is a family of related actions, one per element type, bundled into one object.
- [Strategy](https://aipatterns.dev/design-patterns/strategy.md) swaps one algorithm for a single type. Visitor adds an algorithm across a whole hierarchy of types.

## Agent checklist

- [ ] You checked whether the language offers sealed/union types with exhaustive matching, and Visitor is still the better fit.
- [ ] The element hierarchy is stable and owned by you; new element types are rare.
- [ ] Each `accept` is a single call to its own `visitX`, with no logic.
- [ ] Every visitor handles every element type; no default case swallows new types silently.
- [ ] Traversal order is decided in one place (usually the visitor) and covered by a test.
- [ ] Old type checks (`instanceof` chains, type switches) for the moved operations are deleted, and existing tests pass.