c++ - 使用模板在 C++ 中实现访问者模式

Question

我目前正在尝试用 C++ 实现一种编程语言。在解析阶段之后，我有一个可以操作的抽象语法树，其中包括类型检查和字节码生成。之后，有不同的分析类在这棵树上运行，例如 ASTPrinter 和前面提到的类型检查器。

以前，访问者类的 visit() 方法返回 void，但我最近意识到某些访问者可能需要返回一些值。我尝试使用模板，但遇到了与静态时间多态性和运行时多态性相关的问题，正如我从这里了解到的:C++ Virtual template method .

以下是与此相关的类(我知道它无法编译，但它说明了我正在尝试做的事情):

表达式.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...
};

示例表达式类 (Assignment.h)

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

访问者类示例 (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...
};

正如所见，ASTPrinter 需要返回一个 std::string。我认为问题是由于 accept() 方法在 Expression.h 中不是虚拟的(因为我使用的是模板)。

这是我收到的确切错误消息(针对每个 AST 节点类型重复):

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> > >&)'

我的问题是:是否有其他方法可以实现同样的目标？我已经被困在这个问题上很长时间了，我很感谢任何帮助。谢谢

---

最小可重现示例:

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);
}

表达式.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.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.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

您将“out”参数添加到Expression::accept的实际实现中，并使用它来填充传递指向默认构造结果值的指针，并在模板函数:

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';
}