Can I use CRTP with virtual functions or functors for visitor algorithms tolerant of changes to the classes

Question

I am working on re-writing the IR of a compiler where both the IR classes and the algorithms are in flux. The current compiler has at least 2 current IRs that are used in different phases that I want to merge.

First, we have an AST hierarchy, based upon a Node abstract base class and a visitor pattern associated with it. Next, we have a separate semantic hierarchy that uses a variety of classes (that I can probably all rebase so that Node is the lowest level class for all them too). The semantic hierarchy is likely to grow as we recognize more specializations. There is a separate Visitor pattern for these classes. There are 2 "executable" IRs that are created for executing the resulting program.

My goal is to merge the AST and semantic hierarchy and to merge the executable forms that they generate. This will reduce the number of bugs due to inconsistencies in the two forms.

However, as I noted, the semantic hierarchy is likely to get new classes added to it. Moreover, we are also likely to add new visitor algorithms.

So, what I would like is to do something like this:

class VisitorBase;
class Node;

template Visitable<T> {
   virtual preVisitAccept(VisitorBase *v) { 
      v->preVisit(static_cast<T *>this); }
   virtual inVisitAccept(VisitorBase *v) { 
      v->inVisit(static_cast<T *>this); }
   virtual postVisitAccept(VisitorBase *v) { 
      v->postVisit(static_cast<T *>this); }
   };

template Visitor<T> {
   virtual preVisit(Node *n) { /* do nothing by default */ }
   virtual inVisit(Node *n) { /* do nothing by default */ }
   virtual postVisit(Node *n) { /* do nothing by default */ }
   };

class VisitorBase : Visitor<VistorBase> {
   };

class Node : Visitable<Node> {
   // Code that walks the tree will be probably here 
   // invoking pre, in, and post visit functions as appropriate
}

class ArithOp: node {
   // I don't mind repeating this in each class
   // Some visitor may be specialized on this function
   preVisitAccept(VisitorBase *v) override { 
      v->preVisit(static_cast<arithOp *>this); }
   ...
}

class PrettyPrintVisitor : VisitorBase {
    //  Here is a specialized visitor
    preVisit(ArithOp *n) override { /* specialized code /* }
}

I don't mind repeating some code in each derived node class or each visitor class.

What I want to get away from is a fragile static list (that we have to update) of all the types inherited from Node, but still be able to double dispatch on them. It would be especially bad if we had to repeat such a list more than once. I basically don't want the nodes knowing about the visitors (except perhaps when there are visitors that are customized for that node) nor about other node classes. I also don't want the visitors knowing about the nodes (except for the node types where the visitor is customized). Moreover, I don't want any central repositories of such information, as that will be a header that is always triggering recompile the world....

Any thoughts on code experiments I should try? We are likely to compile this with G++ or CLang.

Answer 1

The double dispatch performed in visitor is a function (in the mathematical sense of function) that associates a pair (visitor_dynamic_type,acceptor_dynamic_type) to a function (C++ function).

As you do not want the base visitor to know all types that derives from the base acceptor, the acceptor_dynamic_type must be identified by a way that abstracts the type. So we can use type_index for that. (You may find better approach to give an id that could be more friendly for some kind of maps)

So you could implement the visitor this way (in almost pseudo code):

template<class T>
struct Visitor {
   map<type_index,void(T&,Node&)>* vfuncs //equivalent a vtbl_ptr
   void Visit(Node& n){
      //manual devirtualization step1: look if a function exist
      //                               for the dynamic type of the acceptor
      if (auto it=vfuncs.find(typeid(n));it!=vfuncs.end()){
          (*it)(statis_cast<T&>(*this),n);
          }
      else{ //do default stuff}
      };
   };
//only visit concrete_Node
struct concrete_visitor:visitor_base{
   static void visit(visitor_base& v,Node& n){
       //manual devirtualization step2: cast references
       auto& cn = static_cast<concrete_Node&>(n);
       auto& self = static_cast<concrete_visitor&>(v);
       //...
       }
   static inline map<type_index,void(visitor_base&,Node&)> vfuncs
                                             {typeid(concrete_Node),&visit};
   concrete_visitor():visitor_base{&vfuncs}{} //vtbl_ptr initialization
   };

Concretely is not a visitor pattern any more. It is just a raw brute force de-virtualization at the cost of a search in a map.