Introduce a section to the programmers manual about type hierarchies, polymorphism, and virtual dispatch.

[chandlerc]

Summary

This is essentially trying to explain the emerging design techniques
being used in LLVM these days somewhere more accessible than the
comments on a particular piece of infrastructure. It covers the
"concepts-based polymorphism" that caused some confusion during initial
reviews of the new pass manager as well as the tagged-dispatch mechanism
used pervasively in LLVM and Clang.

Perhaps most notably, I've tried to provide some criteria to help
developers choose between these options when designing new pieces of
infrastructure.

I'm going to send an email to llvm-dev and cfe-dev with the content of this
change to collect more general feedback as well, but sending this as a diff for
folks to review in Phabricator if that is more convenient.

[chandlerc]

Fix a typo by replacing 'used' with 'use' (and re-flowing the text)...

[kristof.beyls]

docs/ProgrammersManual.rst

2540 ↗

(On Diff #18799)

I'm not a C++ nor object oriented design expert, but could understand the explanation up to this point reasonably well.
I am not sure what is meant with "manual tagged dispatch". A web search gave me some
explanations - but no great ones. I'm wondering if it would be possible to also give a pointer
that explains "tag dispatching" and how it results in closed type hierarchies?
Or maybe one of the videos pointed to above explain it (sorry - haven't watched those yet)?

I think it's a good idea to record and explain best practice used in LLVM object-oriented/type hierarchy design.

[mehdi_amini]

docs/ProgrammersManual.rst

2506 ↗

(On Diff #18799)

" is to that of ", is it correct English? This is not clear to me (I'm not an English-native speaker).

[echristo]

docs/ProgrammersManual.rst

2506 ↗

(On Diff #18799)

Not in this context no. It should probably be "is that of". Though the sentence might read more clearly as: "An alternate, and preferred within LLVM, strategy for the second use case is that of generic programming."

[silvas]

I really like it. Some minor suggestions.

docs/ProgrammersManual.rst

2505–2506 ↗

(On Diff #18799)

Somewhere in this paragraph it might be worth mentioning that the buzz-words "compile-time duck typing" or "static polymorphism" is sometimes used to describe this.

2507–2508 ↗

(On Diff #18799)

I would suggest making a connection with "concepts", e.g. ... that conforms to the interface (sometimes called a "concept").

2519–2527 ↗

(On Diff #18799)

I think it would be useful to give explicit guidance to the reader as to which of these to look at first. I think it's reasonable to get up to speed on this pattern from these resources from a single ~30min video. It's not clear to the reader from this list whether getting up to speed on this pattern is something that they can click through one of these videos and watch it while eating a sandwich, or whether it is more weekend-scale.

When I encountered this stuff for the first time, IIRC I sort of skipped through the C++Now! 2012 and that really got my interest, then I watched the GoingNative 2013 talk and finally skimmed through some of the resources linked from the github. Based on my anecdotal experience, I would probably favor calling out the GoingNative 2013 talk as "watch this for a quickstart".

2538–2539 ↗

(On Diff #18799)

Probably want a link to http://llvm.org/docs/HowToSetUpLLVMStyleRTTI.html . You may want to use the catch-phrase "LLVM-style RTTI" somewhere here as well.

Also feel free to make changes to HowToSetUpLLVMStyleRTTI to better fit into the context of the discussion you're adding here.

[silvas]

Some minor wording suggestions.

docs/ProgrammersManual.rst

2506 ↗

(On Diff #18799)

"An alternative strategy (preferred within LLVM) for the second use case is generic programming". Commas can be used for a lot of things in English, and sometimes even native speakers have to backtrack to figure out what kind of use it is (in this case, they are delimiting a parenthetical, so just use parentheses).

2529–2530 ↗

(On Diff #18799)

The different "and"'s here are sort of confusing. Maybe "creating a type hierarchy with virtual dispatch" to avoid one of them?

[dexonsmith]

Chandler: nice writeup.

[kristof.beyls]

llvm/trunk/docs/ProgrammersManual.rst

2551

Thanks, this makes the "closed type hierarchies" and "manual tagged dispatch" clear to me now.
I don't have any further remarks on the text - looks good to me.

llvm/trunk/docs/ProgrammersManual.rst

 ``Use**`` on every modification.  Accordingly getters must strip the tag bits.
 
 For layout b) instead of the ``User`` we find a pointer (``User*`` with LSBit
 set).  Following this pointer brings us to the ``User``.  A portable trick
 ensures that the first bytes of ``User`` (if interpreted as a pointer) never has
 the LSBit set. (Portability is relying on the fact that all known compilers
 place the ``vptr`` in the first word of the instances.)
 
+.. _polymorphism:
+
+Designing Type Hiercharies and Polymorphic Interfaces
+-----------------------------------------------------
+
+There are two different design patterns that tend to result in the use of
+virtual dispatch for methods in a type hierarchy in C++ programs. The first is
+a genuine type hierarchy where different types in the hierarchy model
+a specific subset of the functionality and semantics, and these types nest
+strictly within each other. Good examples of this can be seen in the ``Value``
+or ``Type`` type hierarchies.
+
+A second is the desire to dispatch dynamically across a collection of
+polymorphic interface implementations. This latter use case can be modeled with
+virtual dispatch and inheritance by defining an abstract interface base class
+which all implementations derive from and override. However, this
+implementation strategy forces an **"is-a"** relationship to exist that is not
+actually meaningful. There is often not some nested hierarchy of useful
+generalizations which code might interact with and move up and down. Instead,
+there is a singular interface which is dispatched across a range of
+implementations.
+
+The preferred implementation strategy for the second use case is that of
+generic programming (sometimes called "compile-time duck typing" or "static
+polymorphism"). For example, a template over some type parameter ``T`` can be
+instantiated across any particular implementation that conforms to the
+interface or *concept*. A good example here is the highly generic properties of
+any type which models a node in a directed graph. LLVM models these primarily
+through templates and generic programming. Such templates include the
+``LoopInfoBase`` and ``DominatorTreeBase``. When this type of polymorphism
+truly needs **dynamic** dispatch you can generalize it using a technique
+called *concept-based polymorphism*. This pattern emulates the interfaces and
+behaviors of templates using a very limited form of virtual dispatch for type
+erasure inside its implementation. You can find examples of this technique in
+the ``PassManager.h`` system, and there is a more detailed introduction to it
+by Sean Parent in several of his talks and papers:
+
+#. `Inheritance Is The Base Class of Evil
+   <http://channel9.msdn.com/Events/GoingNative/2013/Inheritance-Is-The-Base-Class-of-Evil>`_
+   - The GoingNative 2013 talk describing this technique, and probably the best
+   place to start.
+#. `Value Semantics and Concepts-based Polymorphism
+   <http://www.youtube.com/watch?v=_BpMYeUFXv8>`_ - The C++Now! 2012 talk
+   describing this technique in more detail.
+#. `Sean Parent's Papers and Presentations
+   <http://github.com/sean-parent/sean-parent.github.com/wiki/Papers-and-Presentations>`_
+   - A Github project full of links to slides, video, and sometimes code.
+
+When deciding between creating a type hierarchy (with either tagged or virtual
+dispatch) and using templates or concepts-based polymorphism, consider whether
+there is some refinement of an abstract base class which is a semantically
+meaningful type on an interface boundary. If anything more refined than the
+root abstract interface is meaningless to talk about as a partial extension of
+the semantic model, then your use case likely fits better with polymorphism and
+you should avoid using virtual dispatch. However, there may be some exigent
+circumstances that require one technique or the other to be used.
+
+If you do need to introduce a type hierarchy, we prefer to use explicitly
+closed type hierarchies with manual tagged dispatch and/or RTTI rather than the
+open inheritance model and virtual dispatch that is more common in C++ code.
+This is because LLVM rarely encourages library consumers to extend its core
+types, and leverages the closed and tag-dispatched nature of its hierarchies to
+generate significantly more efficient code. We have also found that a large
+amount of our usage of type hierarchies fits better with tag-based pattern
+matching rather than dynamic dispatch across a common interface. Within LLVM we
+have built custom helpers to facilitate this design. See this document's
+section on `isa and dyn_cast <isa>`_ and our `detailed document
+<http://llvm.org/docs/HowToSetUpLLVMStyleRTTI.html>`_ which describes how you
+can implement this pattern for use with the LLVM helpers.
+
 .. _coreclasses:
 
 The Core LLVM Class Hierarchy Reference
 =======================================
 
 ``#include "llvm/IR/Type.h"``
 
 header source: `Type.h <http://llvm.org/doxygen/Type_8h-source.html>`_