docs/HowToSetUpLLVMStyleRTTI.rst

   1 .. _how-to-set-up-llvm-style-rtti:
   2
   3 ======================================================
   4 How to set up LLVM-style RTTI for your class hierarchy
   5 ======================================================
   6
   7 .. sectionauthor:: Sean Silva <silvas@purdue.edu>
   8
   9 .. contents::
  10
  11 Background
  12 ==========
  13
  14 LLVM avoids using C++'s built in RTTI. Instead, it  pervasively uses its
  15 own hand-rolled form of RTTI which is much more efficient and flexible,
  16 although it requires a bit more work from you as a class author.
  17
  18 A description of how to use LLVM-style RTTI from a client's perspective is
  19 given in the `Programmer's Manual <ProgrammersManual.html#isa>`_. This
  20 document, in contrast, discusses the steps you need to take as a class
  21 hierarchy author to make LLVM-style RTTI available to your clients.
  22
  23 Before diving in, make sure that you are familiar with the Object Oriented
  24 Programming concept of "`is-a`_".
  25
  26 .. _is-a: http://en.wikipedia.org/wiki/Is-a
  27
  28 Basic Setup
  29 ===========
  30
  31 This section describes how to set up the most basic form of LLVM-style RTTI
  32 (which is sufficient for 99.9% of the cases). We will set up LLVM-style
  33 RTTI for this class hierarchy:
  34
  35 .. code-block:: c++
  36
  37    class Shape {
  38    public:
  39      Shape() {}
  40      virtual double computeArea() = 0;
  41    };
  42
  43    class Square : public Shape {
  44      double SideLength;
  45    public:
  46      Square(double S) : SideLength(S) {}
  47      double computeArea() /* override */;
  48    };
  49
  50    class Circle : public Shape {
  51      double Radius;
  52    public:
  53      Circle(double R) : Radius(R) {}
  54      double computeArea() /* override */;
  55    };
  56
  57 The most basic working setup for LLVM-style RTTI requires the following
  58 steps:
  59
  60 #. In the header where you declare ``Shape``, you will want to ``#include
  61    "llvm/Support/Casting.h"``, which declares LLVM's RTTI templates. That
  62    way your clients don't even have to think about it.
  63
  64    .. code-block:: c++
  65
  66       #include "llvm/Support/Casting.h"
  67
  68 #. In the base class, introduce an enum which discriminates all of the
  69    different concrete classes in the hierarchy, and stash the enum value
  70    somewhere in the base class.
  71
  72    Here is the code after introducing this change:
  73
  74    .. code-block:: c++
  75
  76        class Shape {
  77        public:
  78       +  /// Discriminator for LLVM-style RTTI (dyn_cast<> et al.)
  79       +  enum ShapeKind {
  80       +    SK_Square,
  81       +    SK_Circle
  82       +  };
  83       +private:
  84       +  const ShapeKind Kind;
  85       +public:
  86       +  ShapeKind getKind() const { return Kind; }
  87       +
  88          Shape() {}
  89          virtual double computeArea() = 0;
  90        };
  91
  92    You will usually want to keep the ``Kind`` member encapsulated and
  93    private, but let the enum ``ShapeKind`` be public along with providing a
  94    ``getKind()`` method. This is convenient for clients so that they can do
  95    a ``switch`` over the enum.
  96
  97    A common naming convention is that these enums are "kind"s, to avoid
  98    ambiguity with the words "type" or "class" which have overloaded meanings
  99    in many contexts within LLVM. Sometimes there will be a natural name for
 100    it, like "opcode". Don't bikeshed over this; when in doubt use ``Kind``.
 101
 102    You might wonder why the ``Kind`` enum doesn't have an entry for
 103    ``Shape``. The reason for this is that since ``Shape`` is abstract
 104    (``computeArea() = 0;``), you will never actually have non-derived
 105    instances of exactly that class (only subclasses). See `Concrete Bases
 106    and Deeper Hierarchies`_ for information on how to deal with
 107    non-abstract bases. It's worth mentioning here that unlike
 108    ``dynamic_cast<>``, LLVM-style RTTI can be used (and is often used) for
 109    classes that don't have v-tables.
 110
 111 #. Next, you need to make sure that the ``Kind`` gets initialized to the
 112    value corresponding to the dynamic type of the class. Typically, you will
 113    want to have it be an argument to the constructor of the base class, and
 114    then pass in the respective ``XXXKind`` from subclass constructors.
 115
 116    Here is the code after that change:
 117
 118    .. code-block:: c++
 119
 120        class Shape {
 121        public:
 122          /// Discriminator for LLVM-style RTTI (dyn_cast<> et al.)
 123          enum ShapeKind {
 124            SK_Square,
 125            SK_Circle
 126          };
 127        private:
 128          const ShapeKind Kind;
 129        public:
 130          ShapeKind getKind() const { return Kind; }
 131
 132       -  Shape() {}
 133       +  Shape(ShapeKind K) : Kind(K) {}
 134          virtual double computeArea() = 0;
 135        };
 136
 137        class Square : public Shape {
 138          double SideLength;
 139        public:
 140       -  Square(double S) : SideLength(S) {}
 141       +  Square(double S) : Shape(SK_Square), SideLength(S) {}
 142          double computeArea() /* override */;
 143        };
 144
 145        class Circle : public Shape {
 146          double Radius;
 147        public:
 148       -  Circle(double R) : Radius(R) {}
 149       +  Circle(double R) : Shape(SK_Circle), Radius(R) {}
 150          double computeArea() /* override */;
 151        };
 152
 153 #. Finally, you need to inform LLVM's RTTI templates how to dynamically
 154    determine the type of a class (i.e. whether the ``isa<>``/``dyn_cast<>``
 155    should succeed). The default "99.9% of use cases" way to accomplish this
 156    is through a small static member function ``classof``. In order to have
 157    proper context for an explanation, we will display this code first, and
 158    then below describe each part:
 159
 160    .. code-block:: c++
 161
 162        class Shape {
 163        public:
 164          /// Discriminator for LLVM-style RTTI (dyn_cast<> et al.)
 165          enum ShapeKind {
 166            SK_Square,
 167            SK_Circle
 168          };
 169        private:
 170          const ShapeKind Kind;
 171        public:
 172          ShapeKind getKind() const { return Kind; }
 173
 174          Shape(ShapeKind K) : Kind(K) {}
 175          virtual double computeArea() = 0;
 176        };
 177
 178        class Square : public Shape {
 179          double SideLength;
 180        public:
 181          Square(double S) : Shape(SK_Square), SideLength(S) {}
 182          double computeArea() /* override */;
 183       +
 184       +  static bool classof(const Shape *S) {
 185       +    return S->getKind() == SK_Square;
 186       +  }
 187        };
 188
 189        class Circle : public Shape {
 190          double Radius;
 191        public:
 192          Circle(double R) : Shape(SK_Circle), Radius(R) {}
 193          double computeArea() /* override */;
 194       +
 195       +  static bool classof(const Shape *S) {
 196       +    return S->getKind() == SK_Circle;
 197       +  }
 198        };
 199
 200    The job of ``classof`` is to dynamically determine whether an object of
 201    a base class is in fact of a particular derived class.  In order to
 202    downcast a type ``Base`` to a type ``Derived``, there needs to be a
 203    ``classof`` in ``Derived`` which will accept an object of type ``Base``.
 204
 205    To be concrete, consider the following code:
 206
 207    .. code-block:: c++
 208
 209       Shape *S = ...;
 210       if (isa<Circle>(S)) {
 211         /* do something ... */
 212       }
 213
 214    The code of the ``isa<>`` test in this code will eventually boil
 215    down---after template instantiation and some other machinery---to a
 216    check roughly like ``Circle::classof(S)``. For more information, see
 217    :ref:`classof-contract`.
 218
 219    The argument to ``classof`` should always be an *ancestor* class because
 220    the implementation has logic to allow and optimize away
 221    upcasts/up-``isa<>``'s automatically. It is as though every class
 222    ``Foo`` automatically has a ``classof`` like:
 223
 224    .. code-block:: c++
 225
 226       class Foo {
 227         [...]
 228         template <class T>
 229         static bool classof(const T *,
 230                             ::llvm::enable_if_c<
 231                               ::llvm::is_base_of<Foo, T>::value
 232                             >::type* = 0) { return true; }
 233         [...]
 234       };
 235
 236    Note that this is the reason that we did not need to introduce a
 237    ``classof`` into ``Shape``: all relevant classes derive from ``Shape``,
 238    and ``Shape`` itself is abstract (has no entry in the ``Kind`` enum),
 239    so this notional inferred ``classof`` is all we need. See `Concrete
 240    Bases and Deeper Hierarchies`_ for more information about how to extend
 241    this example to more general hierarchies.
 242
 243 Although for this small example setting up LLVM-style RTTI seems like a lot
 244 of "boilerplate", if your classes are doing anything interesting then this
 245 will end up being a tiny fraction of the code.
 246
 247 Concrete Bases and Deeper Hierarchies
 248 =====================================
 249
 250 For concrete bases (i.e. non-abstract interior nodes of the inheritance
 251 tree), the ``Kind`` check inside ``classof`` needs to be a bit more
 252 complicated. The situation differs from the example above in that
 253
 254 * Since the class is concrete, it must itself have an entry in the ``Kind``
 255   enum because it is possible to have objects with this class as a dynamic
 256   type.
 257
 258 * Since the class has children, the check inside ``classof`` must take them
 259   into account.
 260
 261 Say that ``SpecialSquare`` and ``OtherSpecialSquare`` derive
 262 from ``Square``, and so ``ShapeKind`` becomes:
 263
 264 .. code-block:: c++
 265
 266     enum ShapeKind {
 267       SK_Square,
 268    +  SK_SpecialSquare,
 269    +  SK_OtherSpecialSquare,
 270       SK_Circle
 271     }
 272
 273 Then in ``Square``, we would need to modify the ``classof`` like so:
 274
 275 .. code-block:: c++
 276
 277    -  static bool classof(const Shape *S) {
 278    -    return S->getKind() == SK_Square;
 279    -  }
 280    +  static bool classof(const Shape *S) {
 281    +    return S->getKind() >= SK_Square &&
 282    +           S->getKind() <= SK_OtherSpecialSquare;
 283    +  }
 284
 285 The reason that we need to test a range like this instead of just equality
 286 is that both ``SpecialSquare`` and ``OtherSpecialSquare`` "is-a"
 287 ``Square``, and so ``classof`` needs to return ``true`` for them.
 288
 289 This approach can be made to scale to arbitrarily deep hierarchies. The
 290 trick is that you arrange the enum values so that they correspond to a
 291 preorder traversal of the class hierarchy tree. With that arrangement, all
 292 subclass tests can be done with two comparisons as shown above. If you just
 293 list the class hierarchy like a list of bullet points, you'll get the
 294 ordering right::
 295
 296    | Shape
 297      | Square
 298        | SpecialSquare
 299        | OtherSpecialSquare
 300      | Circle
 301
 302 .. _classof-contract:
 303
 304 The Contract of ``classof``
 305 ---------------------------
 306
 307 To be more precise, let ``classof`` be inside a class ``C``.  Then the
 308 contract for ``classof`` is "return ``true`` if the dynamic type of the
 309 argument is-a ``C``".  As long as your implementation fulfills this
 310 contract, you can tweak and optimize it as much as you want.
 311
 312 .. TODO::
 313
 314    Touch on some of the more advanced features, like ``isa_impl`` and
 315    ``simplify_type``. However, those two need reference documentation in
 316    the form of doxygen comments as well. We need the doxygen so that we can
 317    say "for full details, see http://llvm.org/doxygen/..."
 318
 319 Rules of Thumb
 320 ==============
 321
 322 #. The ``Kind`` enum should have one entry per concrete class, ordered
 323    according to a preorder traversal of the inheritance tree.
 324 #. The argument to ``classof`` should be a ``const Base *``, where ``Base``
 325    is some ancestor in the inheritance hierarchy. The argument should
 326    *never* be a derived class or the class itself: the template machinery
 327    for ``isa<>`` already handles this case and optimizes it.
 328 #. For each class in the hierarchy that has no children, implement a
 329    ``classof`` that checks only against its ``Kind``.
 330 #. For each class in the hierarchy that has children, implement a
 331    ``classof`` that checks a range of the first child's ``Kind`` and the
 332    last child's ``Kind``.