Implementing the visitor pattern in C++ using templates

Question

I am currently trying to implement a programming language in C++. After the parsing stage, I have an Abstract Syntax Tree that I can operate on, which includes type checking and bytecode generation. After that, there are different analysis classes that operate on this tree, like an ASTPrinter and the aforementioned type checker.

Previously, the visitor class' visit() methods returned void, but I recently realized that some visitors may need to return some values. I tried using templates, but I ran into an issue relating to static time polymorphism and runtime polymorphism as I learned about from here: C++ Virtual template method.

Here are the classes relating to this (I know it doesn't compile, but it illustrates what I am trying to do):

Expression.h

class Expression {
    public:
        template<typename R> R accept(ExprVisitor<R>& visitor);
};

ExprVisitor.h

template<typename R>
class ExprVisitor {
    public:
        virtual R visitAssignmentExpression(class Assignment* expression) = 0;
        virtual R visitBinaryExpression(class Binary* expression) = 0;
        // Rest of the visit methods...
};

Example Expression Class (Assignment.h)

class Assignment: public Expression {
    public:
         template<typename R> R accept(ExprVisitor<R>& visitor);
};

Example Visitor Class (ASTPrinter.h)

class ASTPrinter: public ExprVisitor<std::string> {
    public:
        std::string visitAssignmentExpression(Assignment* expression) override;
        std::string visitBinaryExpression(Binary* expression) override;
        // Rest of the visit methods...
};

As seen, the ASTPrinter needs to return a std::string. I believe the issue arises from the fact that the accept() method is not virtual in Expression.h (because I am using templates).

This is the exact error message I am getting (repeated for each AST node type):

undefined reference to `std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > Expression::accept<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >(ExprVisitor<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >&)'

My question is: is there another way to achieve the same thing? I have been stuck on this for a long time, and I appreciate any help. Thanks

---

Minimum Reproducible Example:

main.cpp

#include "Literal.h"
#include "Binary.h"
#include "ASTPrinter.h"


int main(int argc, char** argv) {
    Binary expr = Binary(Literal("10"), "+", Literal("10"));

    ASTPrinter ast = ASTPrinter();
    ast.constructTree(expr);
}

Expression.h

#ifndef CODEPULSAR_EXPRESSION_H
#define CODEPULSAR_EXPRESSION_H

#include "ExprVisitor.h"


class Expression {
    public:
        template<typename R> R accept(ExprVisitor<R>& visitor);
};


#endif

ExprVisitor.h

#ifndef CODEPULSAR_EXPRVISITOR_H
#define CODEPULSAR_EXPRVISITOR_H


template<typename R> class ExprVisitor {
    public:
        virtual R visitBinaryExpression(class Binary expression) = 0;
        virtual R visitLiteralExpression(class Literal expression) = 0;
};


#endif

ASTPrinter.*

// ASTPrinter.h
#ifndef CODEPULSAR_ASTPRINTER_H
#define CODEPULSAR_ASTPRINTER_H

#include <string>
#include <iostream>

#include "ExprVisitor.h"
#include "Expression.h"
#include "Binary.h"
#include "Literal.h"


class ASTPrinter: public ExprVisitor<std::string> {
    public:
        void constructTree(Expression ast);

        // Expression AST Visitors
        std::string visitBinaryExpression(Binary expression) override;
        std::string visitLiteralExpression(Literal expression) override;
};


#endif

// ASTPrinter.cpp
#include "ASTPrinter.h"


void ASTPrinter::constructTree(Expression ast) {
    std::cout << ast.accept(*this) << std::endl;
}

std::string ASTPrinter::visitBinaryExpression(Binary expression) {
    return "Binary(" + expression.left.accept(*this) + expression.operatorType + expression.right.accept(*this);
}

std::string ASTPrinter::visitLiteralExpression(Literal expression) {
    return "Literal(" + expression.value + ")";
}

Binary.*

// Binary.h
#ifndef CODEPULSAR_BINARY_H
#define CODEPULSAR_BINARY_H

#include <string>

#include "Expression.h"


class Binary: public Expression {
public:
    Binary(Expression left, std::string operatorType, Expression right);
    template<typename R> R accept(ExprVisitor<R>& visitor);

    Expression left;
    std::string operatorType;
    Expression right;
};


#endif

// Binary.cpp
#include "Binary.h"


Binary::Binary(Expression left, std::string operatorType, Expression right) {
    this->left = left;
    this->operatorType = operatorType;
    this->right = right;
}

template<typename R>
R Binary::accept(ExprVisitor<R>& visitor) {
    visitor.visitBinaryExpression(this);
}

Literal.*

// Literal.h
#ifndef CODEPULSAR_LITERAL_H
#define CODEPULSAR_LITERAL_H

#include <string>

#include "Expression.h"


class Literal: public Expression {
public:
    Literal(std::string value);
    template<typename R> R accept(ExprVisitor<R>& visitor);

    std::string value;
};


#endif

// Literal.cpp
#include "Literal.h"


Literal::Literal(std::string value) {
    this->value = value;
}

template<typename R>
R Literal::accept(ExprVisitor<R>& visitor) {
    visitor.visitLiteralExpression(this);
}

Answer 1

You add an "out" parameter to the actual implementation of Expression::accept and use it to fill pass a pointer to a default constructed result value and do the creation of the result value in a template function:

class Assignment;
class Binary;

class BaseVisitor
{
public:
    virtual void visitAssignmentExpression(Assignment& expression, void* context) = 0;
    virtual void visitBinaryExpression(Binary& expression, void* context) = 0;
    // Rest of the visit methods...
};

template<class T, class R>
class WrapperVisitor : public BaseVisitor
{
public:
    WrapperVisitor(T& wrapped) noexcept
        : m_wrapped(wrapped)
    {
    }

    void visitAssignmentExpression(Assignment& expression, void* context) override
    {
        R* result = static_cast<R*>(context);
        *result = m_wrapped.visitAssignmentExpression(expression);
    }

    void visitBinaryExpression(Binary& expression, void* context) override
    {
        R* result = static_cast<R*>(context);
        *result = m_wrapped.visitBinaryExpression(expression);
    }
    // Rest of the visit methods...
private:
    T& m_wrapped;
};

template<class T>
class WrapperVisitor<T, void> : public BaseVisitor
{
public:
    WrapperVisitor(T& wrapped) noexcept
        : m_wrapped(wrapped)
    {
    }

    void visitAssignmentExpression(Assignment& expression, void*) override
    {
        m_wrapped.visitAssignmentExpression(expression);
    }

    void visitBinaryExpression(Binary& expression, void*) override
    {
        m_wrapped.visitBinaryExpression(expression);
    }
    // Rest of the visit methods...
private:
    T& m_wrapped;
};

template<class T>
T& RefVal()
{
    static_assert(sizeof(T) != sizeof(T), "for use in unevaluated context only");
}

template<class T>
concept Visitor = requires(T visitor, Assignment & a, Binary & b)
{
    std::same_as<decltype(visitor.visitAssignmentExpression(a)), decltype(visitor.visitBinaryExpression(b))>;
};

template<class T>
concept VoidVisitor = requires(T visitor, Assignment& a, Binary& b)
{
    requires Visitor<T>;
    {visitor.visitAssignmentExpression(a) } -> std::same_as<void>;
};

class Expression {
public:
    template<Visitor Visitor> requires (!VoidVisitor<Visitor>)
    auto accept(Visitor& visitor)
    {
        using ResultType = decltype(std::declval<Visitor>().visitAssignmentExpression(RefVal<Assignment>()));

        ResultType result;

        WrapperVisitor<Visitor, ResultType> wrapperVisitor(visitor);
        acceptImpl(wrapperVisitor, &result);
        return result;
    }

    template<VoidVisitor Visitor>
    void accept(Visitor& visitor)
    {
        // check the return types are the same
        static_assert(std::is_void_v<decltype(std::declval<Visitor>().visitBinaryExpression(RefVal<Binary>()))>);

        WrapperVisitor<Visitor, void> wrapperVisitor(visitor);
        acceptImpl(wrapperVisitor, nullptr);
    }

protected:
    virtual void acceptImpl(BaseVisitor& visitor, void* context) = 0;

};

class Assignment : public Expression {
protected:
    virtual void acceptImpl(BaseVisitor& visitor, void* context) override
    {
        visitor.visitAssignmentExpression(*this, context);
    }
};

class Binary : public Expression {

protected:
    virtual void acceptImpl(BaseVisitor& visitor, void* context) override
    {
        visitor.visitBinaryExpression(*this, context);
    }
};

class ASTPrinter {
public:
    std::string visitAssignmentExpression(Assignment& expression)
    {
        return "Assignment";
    }

    std::string visitBinaryExpression(Binary& expression)
    {
        return "Binary";
    }
    // Rest of the visit methods...
};

int main(void) {
    ASTPrinter printer;
    Expression&& b = Binary();
    Expression&& a = Assignment();

    std::cout << b.accept(printer) << '\n'
        << a.accept(printer) << '\n';
}