1======================================================
2How to set up LLVM-style RTTI for your class hierarchy
3======================================================
4
5.. contents::
6
7Background
8==========
9
10LLVM avoids using C++'s built in RTTI. Instead, it  pervasively uses its
11own hand-rolled form of RTTI which is much more efficient and flexible,
12although it requires a bit more work from you as a class author.
13
14A description of how to use LLVM-style RTTI from a client's perspective is
15given in the `Programmer's Manual <ProgrammersManual.html#isa>`_. This
16document, in contrast, discusses the steps you need to take as a class
17hierarchy author to make LLVM-style RTTI available to your clients.
18
19Before diving in, make sure that you are familiar with the Object Oriented
20Programming concept of "`is-a`_".
21
22.. _is-a: http://en.wikipedia.org/wiki/Is-a
23
24Basic Setup
25===========
26
27This 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
29RTTI 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
53The most basic working setup for LLVM-style RTTI requires the following
54steps:
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
239Although for this small example setting up LLVM-style RTTI seems like a lot
240of "boilerplate", if your classes are doing anything interesting then this
241will end up being a tiny fraction of the code.
242
243Concrete Bases and Deeper Hierarchies
244=====================================
245
246For concrete bases (i.e. non-abstract interior nodes of the inheritance
247tree), the ``Kind`` check inside ``classof`` needs to be a bit more
248complicated. 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
257Say that ``SpecialSquare`` and ``OtherSpecialSquare`` derive
258from ``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
269Then 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
281The reason that we need to test a range like this instead of just equality
282is that both ``SpecialSquare`` and ``OtherSpecialSquare`` "is-a"
283``Square``, and so ``classof`` needs to return ``true`` for them.
284
285This approach can be made to scale to arbitrarily deep hierarchies. The
286trick is that you arrange the enum values so that they correspond to a
287preorder traversal of the class hierarchy tree. With that arrangement, all
288subclass tests can be done with two comparisons as shown above. If you just
289list the class hierarchy like a list of bullet points, you'll get the
290ordering right::
291
292   | Shape
293     | Square
294       | SpecialSquare
295       | OtherSpecialSquare
296     | Circle
297
298A Bug to be Aware Of
299--------------------
300
301The example just given opens the door to bugs where the ``classof``\s are
302not updated to match the ``Kind`` enum when adding (or removing) classes to
303(from) the hierarchy.
304
305Continuing the example above, suppose we add a ``SomewhatSpecialSquare`` as
306a 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
318Now, suppose that we forget to update ``Square::classof()``, so it still
319looks 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
330As the comment indicates, this code contains a bug. A straightforward and
331non-clever way to avoid this is to introduce an explicit ``SK_LastSquare``
332entry in the enum when adding the first subclass(es). For example, we could
333rewrite the example at the beginning of `Concrete Bases and Deeper
334Hierarchies`_ 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
355Then, 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
368Notice that ``Square::classof`` does not need to be changed.
369
370.. _classof-contract:
371
372The Contract of ``classof``
373---------------------------
374
375To be more precise, let ``classof`` be inside a class ``C``.  Then the
376contract for ``classof`` is "return ``true`` if the dynamic type of the
377argument is-a ``C``".  As long as your implementation fulfills this
378contract, you can tweak and optimize it as much as you want.
379
380For example, LLVM-style RTTI can work fine in the presence of
381multiple-inheritance by defining an appropriate ``classof``.
382An 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>`_
385inside Clang.
386The ``Decl`` hierarchy is done very similarly to the example setup
387demonstrated in this tutorial.
388The key part is how to then incorporate ``DeclContext``: all that is needed
389is in ``bool DeclContext::classof(const Decl *)``, which asks the question
390"Given a ``Decl``, how can I determine if it is-a ``DeclContext``?".
391It answers this with a simple switch over the set of ``Decl`` "kinds", and
392returning 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
401Rules 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``.
415