Circular Dependency Issue in My Visitor Design Pattern

Question

I am trying to implement the visitor design pattern to build a tree of expressions for an interpreter. I am declaring everything in a header file and run into an issue where I need to define visitor before everything else but that's impossible because my Expr class needs visitor defined before it but then thats impossible because the other classes need Expr defined before them and I'm just unsure what to do.

#include "Token.h"

template <typename R>
class Visitor {
        virtual R visitBinaryExpr(Binary expr);
};

class Expr {
public:
template<typename R>
    R accept(Visitor<R> visitor);
};

class Binary : public Expr {
public:
    Binary(Expr left, Token oper, Expr right) : left(left), oper(oper), right(right)    {
    }

    template<typename T>
    T accept(T visitor) {
        return visitor.visitBinaryExpr(this);
    }

    const Expr left;
    const Token oper;
    const Expr right;
};

Gives syntax error: identifier 'Binary' on line 5

Heres a small example of the code. Any help would be appreciated!

Answer 1

The problem with cyclic references has been solved by a visitor pattern shown by Andrei Alexandrescu in his book: " Modern C++ Design: Generic Programming and Design Patterns Applied"

He calls the pattern: "Acyclic Visitor"

To be honest. You program looks very much like his example. But anyway. To make it happen, you could do slight modifications.

I also implemented such a generic visitor here.

Code:

// ------------------------------------------------------------------------------------------------------------------------------------------------
// 1. Visitor part

    // You need to derive a Visitor class from VisitorBase. That is mandatory
    class VisitorBase
    {
        public:
            VisitorBase(void) {}
            virtual ~VisitorBase(void) {}
    };


    // Additionally you need to derive your visitor class from this class
    // and as many times as you want to visit specific classes that you must define
    // as template parameters.
    //
    // So a typical visitor class definition looks like
    //
    // class AVisitorForSomeOtherTypes :    public VisitorBase
    //                                      public Visitor<VisitibleType1>,
    //                                      public Visitor<VisitibleType2>,
    //                                      public Visitor<VisitibleTypex>
    //
    // With such a Visitor you can visit the classes specified in the template parameters
    //
    template <class T>
    class Visitor
    {
        public:
            Visitor(void) {}
            virtual ~Visitor(void) {}
            
            virtual void visit(T&) = 0;
    };


// ------------------------------------------------------------------------------------------------------------------------------------------------
// 2. Visitable part

    class VisitableBase
    {
        public:
            VisitableBase(void) {}
            virtual ~VisitableBase() {}
            // Will be overridden by macro
            // If somebody forgets to insert the macro, we will do nothing
            virtual void acceptAGuestVisitor(VisitorBase&) { };
        protected:
        
            // Because the DEFINE_VISITABLE macro will be used to finally call this function
            // Type T, set to "this" of the class where the macro was defined, T will be
            // of the type of the class where the macro was defined
            // This is just a redirector. And it avoids circular forward declarations
            // Hence "Acyclic"
            
            template <class TypeOfClassThatWillBeVisited>
            static void acceptDecoupled(TypeOfClassThatWillBeVisited& visited, VisitorBase* guestVisitorWhoWillVisitSomeOtherClass)
            {
                // Apply the Acyclic Visitor
                // Since Visitor classes are always derived from VisitorBase
                // and specific Visitor <templated> classes, the dynamic cast will 
                // work, if the guest, is also in the list of Base Classes from which 
                // the visitor is derived
                //
                // The visit function will not be called for unknown Visitors
                // in the example above, not for a "VisitibleTypekkk"
                
                if (Visitor<TypeOfClassThatWillBeVisited>* visitorGuest =   dynamic_cast<Visitor< TypeOfClassThatWillBeVisited>*>(guestVisitorWhoWillVisitSomeOtherClass))
                {
                    // Call the Visitors visit function (if existing)
                    visitorGuest->visit(visited);
                }
                return;
            }
    };


// This Macro hast to be defined in the class that shall be visited.
// So, in the visitable class.
// It will define the accept function which is typical for the visitor pattern.
// Accept will then call the "static acceptDecoupled" function, which 
// calls the visit function with "*this" (of the class where the macro was defined)
// as parameter.
#define DEFINE_VISITABLE() virtual void acceptAGuestVisitor(VisitorBase* guestVisitorWhoWillVisitSomeOtherClass) { acceptDecoupled(*this, guestVisitorWhoWillVisitSomeOtherClass); }

Answer 2

Well that was fast! Yup, forward declaration was what I needed. I was confusing another issue caused by not defining my methods as some sort of problem with my use of forward declaration. My code now looks like,

#include "Token.h"

class Binary;
class Grouping;
class LiteralExpression;
class Unary;

template <typename R>
class Visitor {
    virtual R visitBinaryExpr(Binary expr) { R temp; return temp; };
};

class Expr {
public:
    template<typename R>
    R accept(Visitor<R> visitor) { R temp; return temp; };
};

class Binary : public Expr {
public:
    Binary(Expr left, Token oper, Expr right) : left(left), oper(oper), right(right)    {
    }

    template<typename T>
    T accept(T visitor) {
        return visitor.visitBinaryExpr(this);
    }

    const Expr left;
    const Token oper;
    const Expr right;
};

Though, now I am a bit worried as to whether the accept method will work or if it will just call my temp one from the base Expr class. Oh well, that's a question for another time. Thanks for the help!