0
\$\begingroup\$

After some exposure to Haskell I came to love ADTs to describe 'is one of' and tree-like structures. But now that I work with C++ a lot more I want to use them in C++ too. As far as I know I have two options for this:

  1. inheritance
  2. tagged unions

And I really dislike inheritance.

Below is my implementation of an expression part of an AST. Each kind of expression is implemented as a plain struct with one tagged union to describe "any expression". On usage you have to do pattern matching on expr by having a switch case over the expressions tag.

  • Is there anything inherently wrong or to improve?
  • Are the ownership semantics implemented correctly?
  • Is there an easier way to instantiate the structs where I don't have too write all the constructors by hand? Something like C's compound literals?
struct expr;

struct int_expr {
    int_expr(uint64_t value): value(value) {}

    uint64_t value;
};

struct ident_expr {
    ident_expr(std::shared_ptr<std::string> ident): ident(ident) {
        assert(ident != nullptr);
    }

    std::shared_ptr<std::string> ident;
};

struct bin_expr {
    enum class op { ADD, SUB };

    bin_expr(bin_expr::op op, expr *left, expr *right)
        : op(op), 
          left(std::unique_ptr<expr>(left), 
          right(std::unique_ptr<expr>(right) {
        assert(left != nullptr);
        assert(right != nullptr);
    }

    bin_expr::op op;
    std::unique_ptr<expr> left;
    std::unique_ptr<expr> right;
};

struct expr {
   enum class tag { INT, IDENT, BIN };

   expr(int_expr&& expr): tag(expr::tag::INT), variant(expr) {}
   expr(ident_expr&& expr): tag(expr::tag::IDENT), variant(expr) {}
   expr(bin_expr&& expr): tag(expr::tag::BIN), variant(expr) {}

   expr::tag tag;
   std::variant<int_expr, ident_expr, bin_expr> variant;
};

As requested here are some usages of expr:

////////////////////////////////////////////////////////////////
// Printing ; example for a function where every
// case of expression is handeled inline.
std::ostream &operator<<(std::ostream &stream, expr const &expr) {
    switch (expr.tag) {
    case expr::tag::IDENT:
        return stream << "<ident " << *expr.variant.get<ident_expr>().ident << ">";
    case expr::tag::INT:
        return stream << "<int " << expr.variant.get<int_expr>().value << ">";
    case expr::tag::BIN:
        return stream << "<bin"
                      << *expr.variant.get<bin_expr>().left
                      << " "
                      << *expr.variant.get<bin_expr>().right
                      << ">";
    default:
        // Can never occur... but compilers complain
        throw "Invalid expr tag";
    }
}

////////////////////////////////////////////////////////////////
// IR generation ; example for a function where every
// case of expression is handeled in an own function
llvm::Value *r_value(ident_expr const &expr) {
    return llvm_builder_.CreateLoad(lookup(*expr.ident));
}

llvm::Value *r_value(int_expr const &expr) {
    return llvm_builder_.getInt64(expr.value);
}

llvm::Value *r_value(bin_expr const &expr) {
    auto left = r_value(*expr.left);
    auto right = r_value(*expr.right);

    switch (expr.op) {
    case bin_expr::op::ADD:
        return llvm_builder_.CreateAdd(left, right);
    case bin_expr::op::SUB:
        return llvm_builder_.CreateSub(left, right);
    default:
        throw "invalid bin op";
    }
}

llvm::Value *r_value(expr const &expr) {
switch (expr.tag) {
    case expr::tag::IDENT:
        return r_value(*expr.variant.get<ident_expr>());
    case expr::tag::INT:
        return r_value(*expr.variant.get<int_expr>());
    case expr::tag::BIN:
        return r_value(*expr.variant.get<bin_expr>());
    default:
        throw "Invalid expr tag";
    }
}


////////////////////////////////////////////////////////////////
// Parsing ; example for creation
expr *parser::parse_prim_expr() {
    switch (lookahead(1)) {
        case token::IDENT:
            auto ident = lookup(current_token_data.get<std::string>());
            return expr(ident_expr(ident));
        case token::INT:
            return expr(int_expr(current_token_data.get<uint64_t>()));
        default:
            throw compiler_error();
    }
}

expr* parser::parse_bin_expr() {
    auto left = parse_prim_expr();
    bin_expr::op op;

    switch (lookahead(1)) {
        case token::PLUS: op = bin_expr::op::ADD; break;
        case token::MINUS: op = bin_expr::op::MINUS; break;
        default: throw compiler_error();
    }

    auto right = parse_prim_expr();
    return expr(bin_expr(op, left, right));
}

New contributor
danielspaniol is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
\$\endgroup\$

put on hold as off-topic by Snowhawk, vnp, IEatBagels, Dannnno, Sᴀᴍ Onᴇᴌᴀ Feb 13 at 19:11

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Code not implemented or not working as intended: Code Review is a community where programmers peer-review your working code to address issues such as security, maintainability, performance, and scalability. We require that the code be working correctly, to the best of the author's knowledge, before proceeding with a review." – Snowhawk, IEatBagels, Dannnno, Sᴀᴍ Onᴇᴌᴀ
If this question can be reworded to fit the rules in the help center, please edit the question.

  • \$\begingroup\$ Did you intentionally miss std::variant from your list of options? If so, then why? \$\endgroup\$ – Toby Speight Feb 11 at 16:58
  • \$\begingroup\$ I implemented the tagged union using std::variant \$\endgroup\$ – danielspaniol Feb 11 at 16:59
  • 3
    \$\begingroup\$ Did you actually try compiling this code? It shouldn't compile. You are missing parentheses in the bin_expr constructor's member initializer list. \$\endgroup\$ – Mike Borkland Feb 12 at 1:20