Index: docs/ProgrammersManual.rst =================================================================== --- docs/ProgrammersManual.rst +++ docs/ProgrammersManual.rst @@ -2480,6 +2480,70 @@ 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. + +An alternate implementation strategy for the second use case which should be +preferred within LLVM is to that of generic programming. For example, a template +over some type parameter ``T`` can be instantiated across any particular +implementation that conforms to the interface. 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* which emulates the +interfaces and behaviors of templates while 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: + +#. `Sean Parent's Papers and Presentations + `_ + - A Github project full of links to slides, video, and sometimes code. +#. `Value Semantics and Concepts-based Polymorphism + `_ - The C++Now! 2012 talk + describing this technique. +#. `Inheritance Is The Base Class of Evil + `_ + - The GoingNative 2013 talk describing this technique. + +When deciding between creating a type hierarchy and using virtual dispatch and +using templates or concepts-based polymorphism, consider whether there is some +refinement of an abstract base class which is actually a useful 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 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 often prefer to use explicitly +closed type hierarchies with manual tagged dispatch 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. + .. _coreclasses: The Core LLVM Class Hierarchy Reference