Le pattern Visitor pour parcourir un AST

Le problème

Sans Visitor, il reste deux options. Ajouter une méthode par opération dans chaque classe de nœud : les classes grossissent à chaque nouvelle étape et mélangent des responsabilités sans rapport. Ou écrire de grands switch sur le type du nœud : c’est fragile, et rien ne prévient d’un cas oublié.

Le principe

Chaque nœud expose une seule méthode, accept(visitor), qui rappelle la méthode visit correspondant à son propre type : c’est le double dispatch. Une opération devient alors une classe qui implémente visit pour chaque type de nœud.

#include <iostream>

struct Num;
struct Add;

struct Visitor {
    virtual void visit(const Num&) = 0;
    virtual void visit(const Add&) = 0;
    virtual ~Visitor() = default;
};

struct Expr {
    virtual void accept(Visitor& v) const = 0;
    virtual ~Expr() = default;
};

struct Num : Expr {
    int value;
    explicit Num(int v) : value(v) {}
    void accept(Visitor& v) const override { v.visit(*this); }
};

struct Add : Expr {
    const Expr &lhs, &rhs;
    Add(const Expr& l, const Expr& r) : lhs(l), rhs(r) {}
    void accept(Visitor& v) const override { v.visit(*this); }
};

struct Printer : Visitor {
    void visit(const Num& n) override { std::cout << n.value; }
    void visit(const Add& a) override {
        std::cout << '(';
        a.lhs.accept(*this);
        std::cout << " + ";
        a.rhs.accept(*this);
        std::cout << ')';
    }
};

struct Evaluator : Visitor {
    int result = 0;
    void visit(const Num& n) override { result = n.value; }
    void visit(const Add& a) override {
        a.lhs.accept(*this);
        int left = result;
        a.rhs.accept(*this);
        result = left + result;
    }
};

Sur l’expression (1 + 2) + 3, Printer affiche ((1 + 2) + 3) (il parenthèse chaque addition) et Evaluator renvoie 6. Les nœuds n’ont pas changé : seules deux classes ont été ajoutées.

Dans un compilateur

Le pretty-printer, le binder, le type checker et le générateur de code sont autant de visitors sur le même AST. Un visitor peut aussi porter un état : table des symboles, pile de portées, ou résultat intermédiaire comme result dans Evaluator.

Les limites

Le Visitor ouvre le code aux nouvelles opérations mais le ferme aux nouveaux types de nœud : ajouter un type oblige à modifier tous les visitors. C’est ce qu’on appelle l’expression problem.

Les langages dotés de types somme et de pattern matching (OCaml, Haskell, ou std::variant avec std::visit en C++17) obtiennent le même résultat avec moins de code, et le compilateur signale les cas oubliés.

Sources

• cppreference : std::visit