Index: llvm/trunk/docs/ProgrammersManual.rst =================================================================== --- llvm/trunk/docs/ProgrammersManual.rst +++ llvm/trunk/docs/ProgrammersManual.rst @@ -2480,6 +2480,76 @@ 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 + `_ + - The GoingNative 2013 talk describing this technique, and probably the best + place to start. +#. `Value Semantics and Concepts-based Polymorphism + `_ - The C++Now! 2012 talk + describing this technique in more detail. +#. `Sean Parent's 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 `_ and our `detailed document +`_ which describes how you +can implement this pattern for use with the LLVM helpers. + .. _coreclasses: The Core LLVM Class Hierarchy Reference