This note describes how to implement tagged unions for tree-like data
structures, like the type and intermediate representation hierarchies.
The utilities for working with tagged unions implemented this way can
be found in hail/tunion.hpp, and are described below.

How are tagged unions implemented?  They will normally be passed as
pointers.  The key idea is to lay out the cases so each one starts
with a tag:

  int tag;
  ... data of case corresponding to tag ...

This is a classic pattern.  In C++, we'll implement this with a base
class that carries the tag.  Let's consider a simple example: a
constant literals with two cases: an integer and a floating-point
number.

First, let's create the base class:

  class Literal {
  public:
    using BaseType = Literal;
    enum class Tag {
      INT,
      DOUBLE
    };
    const Tag tag;
    Literal(Tag tag) : tag(tag) {}
    virtual ~Literal();
  };

The Literal base class has some notable features:
 - All literals know their base class, in this case, Literal.
 - The base class defines a tag type that enumerates all the cases.
 - The base class stores a single member, the tag, which is defined at
   construction time.
 - The destructor is virtual when the cases need to run destructors.

Now let's implement one of the cases:

  class IntLiteral : public Literal {
  public:
    static const Tag self_tag = Literal::Tag::INT;
    int value;
    IntInteral(int value) : Literal(self_tag), value(value) {}
  };

Each case knows its own tag as self_tag.  DoubleLiteral is
defined similarly.

What are the operations on tagged unions, and how are they used?
Tagged unions are normally manipulated as pointers and allocated with
operator new:

  Literal *l = new IntLiteral(5);

Once you have a literal pointer, there are a few things you can do
with it.

You can grab its tag with l->tag:

  const char *literal_type(Literal *l) {
    switch(l->tag) {
      case Literal::Tag::INT: return "int";
      case Literal::Tag::DOUBLE: retrn "double";
      default: abort();
    }
  }

You can ask if it is a particular case: isa<IntLiteral>(l).  isa is
implemented as:

  template<class T> bool
  isa(const typename T::BaseType *p) {
    return p->tag == T::self_tag;
  }

You might want to downcast l to a specific case.  Downcast has two
forms.  The first asserts if the pointer is not of the expected case:
cast<IntLiteral>(l).  It is implemented as:

  template<class T> T *
  cast(typename T::BaseType *p) {
    assert(isa<T>(p));
    return static_cast<T *>(p);
  }

There is also a const version.

The second form returns null if the pointer is not of the expected
case:

  template<class T> T *
  dyn_cast(typename T::BaseType *p) {
    if (isa<T>(p))
      return static_cast<T *>(p);
    else
      return nullptr;
  }

It can be used like this:

  if (auto il = dyn_cast<IntLiteral>(l)) {
    ..
  }

There is also a const version.

The interface here loosely based on the LLVM interface.  For more,
see:

https://llvm.org/docs/ProgrammersManual.html#the-isa-cast-and-dyn-cast-templates
https://llvm.org/docs/HowToSetUpLLVMStyleRTTI.html
