docs/HowToSetUpLLVMStyleRTTI.rst

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