Visitor pattern. Is void* an acceptable return type for a completely abstract interface?

Question

I have an AST, represented in the usual way (a tree of nodes of an abstract type). I have several uses cases for traversing this tree (an optimizer, which returns another AST; IR code generation, which returns a llvm::Value*; and a debug analyzer, which simply outputs to stdout and returns nothing).

A visitor feels like the right way to go here, but the differing return types through each use case of the visitor make it hard to see how to implement an interface for this. I considered this:

class Visitor;

class ASTNode {
public:
  virtual void accept(Visitor *visitor);
};

class Visitor {
public:
  virtual void visit(CallNode *node) = 0;
  virtual void visit(BinExprNode *node) = 0;
  // etc
};

Because of the lack of return value, each Visitor implementation would need to build up internal state and provide a result() method with a suitable return type. That is complex, however, since each call to visit() needs some context around the expression being visited (i.e. the call standing alone, or is it being used as part of a binary expression?). It makes it tricky for things like binary expression code generation to collect return values from visiting the nodes of the operands (I could do it with an internal temporary state variable or some such, but it feels over-engineered) and hard to reason about (the state keeps changing).

class OptimizingVisitor : public Visitor {
  ASTNode *m_result;
public:
  ASTNode *result() {
    return m_result;
  }

  void setResult(ASTNode *node) {
    m_result = node;
  }

  void visit(CallNode *node) {
    node->left()->accept(this);
    ASTNode *optimizedL = result();
    node->right()->accept(this);
    ASTNode *optimizedR = result();
    setResult(new CallNode(optimizedL, optimizedR));
  }

  // ... snip ...
};

I could make it even more complex to avoid the "state keeps changing" issue by passing in a new visitor for each node. It just feels like this problem warrants a more functional solution.

Really, I'd like to write the above much more simply and easier to read:

class OptimizingVisitor : public Visitor {
public:
  ASTNode* visit(CallNode *node) {
    ASTNode *optimizedL = node->left()->accept(this);
    ASTNode *optimizedR = node->right()->accept(this);
    return new CallNode(optimizedL, optimizedR);
  }

  // ... snip ...
};

Of course now I've changed the return type, so it doesn't fit my Visitor contract. Far from defining completely separate interfaces for each possible implementation of a a Visitor and making the AST aware of those visitor types, it seems the only really logical thing to use is a void*. Does this sort of API warrant the use of void*? Is there a better way to do this?

Answer 1

If I get this right, I might have something useful. Referring to your sample at https://gist.github.com/d11wtq/9575063, you cannot have

class ASTNode {
public:
   template <class T>
   virtual T accept(Visitor<T> *visitor);
};

because there are no template virtual functions. However, you may have a generic class

template <class D, class T>
struct host {
   virtual T accept(Visitor<T> * visitor);
   // I guess, { return visitor->visit(static_cast <D*>(this)); }
};

and a collection

template <class D, class... T>
struct hosts : host <D, T>... { };

so that, when the set of possible return types is limited, you can say e.g.

class ASTNode : public hosts <ASTNode, T1, T2, T3> {
public:
   // ...
};

Now you have three different Visitor contracts of return types T1,T2,T3.

Answer 2

Maybe this is helpful.

Using return type covariance to make accept() calls type-safe:

class Visitor;

class ASTNode
{
public:
    virtual ASTNode* accept(Visitor* visitor);
};

class CallNode;
class BinaryExpressionNode;

class Visitor
{
public:
    virtual CallNode* visit(CallNode* node) = 0;
    virtual BinaryExpressionNode* visit(BinaryExpressionNode* node) = 0;
};

Implementations:

class CallNode : public ASTNode
{
public:
    CallNode(BinaryExpressionNode* left, BinaryExpressionNode* right);

    // return type covariance
    CallNode* accept(Visitor* visitor) override
    {
        return visitor->visit(this);
    }

    BinaryExpressionNode* left();
    BinaryExpressionNode* right();
};

class BinaryExpressionNode : public ASTNode
{
public:
    BinaryExpressionNode* accept(Visitor* visitor) override
    {
        return visitor->visit(this);
    }
}

class OptimizingVisitor : public Visitor
{
public:
    CallNode* visit(CallNode* node) override
    {
        // return type covariance will make this operation type-safe:
        BinaryExpressionNode* left = node->left()->accept(this);
        auto right = node->right()->accept(this);
        return new CallNode(left, right);
    }

    BinaryExpressionNode* visit(BinaryExpressionNode* node) override
    {
        return new BinaryExpressionNode(node);
    }
};