I wrote a simple AST using a recursive std::variant, as I thought it would be an elegant alternative to inheritance.

using Value = std::variant<std::monostate, double, std::string>;

using ASTStringNode = std::string;
using ASTDoubleNode = double;
struct ASTBinaryOpNode;
struct ASTUnaryOpNode;

using ASTNode = std::variant<std::monostate, ASTStringNode, ASTDoubleNode>;

struct ASTBinaryOpNode {
std::function<Value(const Value&, const Value&)> op;
std::shared_ptr<ASTNode> leftOp, rightOp;
};

struct ASTUnaryOpNode {
std::function<Value(const Value&)> op;
std::shared_ptr<ASTNode> operand;
};

This works fine and as expected. The problem began when I tried to make deep copies of the tree – the construction takes place in a std::stack<ASTNode> , as my parser is calling back with parsed nodes, which get placed on top of the stack, building the tree as operators get encountered. The end result is a std::stack<ASTNode> with one item – the root of the tree, which I want to move out of the stack.

I tried implementing copy constructors and assignment operators for the variant types

struct ASTBinaryOpNode {

ASTBinaryOpNode& operator=(const ASTBinaryOpNode& other) {
    // implementation that calls std::make_shared<ASTNode> at some point
}

ASTBinaryOpNode(const ASTBinaryOpNode& other) {
    // implementation that calls std::make_shared<ASTNode> at some point
}

std::function<Value(const Value&, const Value&)> op;
std::shared_ptr<ASTNode> leftOp, rightOp;
};

struct ASTUnaryOpNode {
    ASTUnaryOpNode& operator=(const ASTUnaryOpNode& other) {
        // implementation that calls std::make_shared<ASTNode> at some point
    }
        
    ASTUnaryOpNode(const ASTUnaryOpNode& other) {
       // implementation that calls std::make_shared<ASTNode> at some point
    }
std::function<Value(const Value&)> op;
std::shared_ptr<ASTNode> operand;
};

However, these copy operations need to call std::make_shared<ASTNode>() at some point. This fails to compile due to ASTNode being an incomplete type.

From my observations, it looks like this approach works only as long as there is only one variant type that is recursive.

I also tried implementing a separate deep copy method, but in the end, I always needed to move out the AST root from the top of the stack even inside the deep copy method.

Am I missing something? Is there a way to make a deep copy of the tree? Or do I need to completely restructure my approach?