<div dir="ltr"><div>The proposed addition to ProgrammersManuel.rst is below the break...</div><div><br></div><div>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.</div><div><br></div><div>Perhaps most notably, I've tried to provide some criteria to help developers choose between these options when designing new pieces of infrastructure.</div><div><br></div><div>Many thanks to Richard Smith who helped me crystalize this, as well as Eric, Dave, and Nick who helped me talk it through.</div><div><br></div><div>You can find the actual patch and make comments on Phabricator here: <a href="http://reviews.llvm.org/D7191">http://reviews.llvm.org/D7191</a></div><div><br></div><div>I'm just going to paste the text below however as I think that'll more easily facilitate discussion!</div><div><br></div><div>========</div><div><br></div><div><div>.. _polymorphism:</div><div><br></div><div>Designing Type Hiercharies and Polymorphic Interfaces</div><div>-----------------------------------------------------</div><div><br></div><div>There are two different design patterns that tend to result in the use of</div><div>virtual dispatch for methods in a type hierarchy in C++ programs. The first is</div><div>a genuine type hierarchy where different types in the hierarchy model</div><div>a specific subset of the functionality and semantics, and these types nest</div><div>strictly within each other. Good examples of this can be seen in the ``Value``</div><div>or ``Type`` type hierarchies.</div><div><br></div><div>A second is the desire to dispatch dynamically across a collection of</div><div>polymorphic interface implementations. This latter use case can be modeled with</div><div>virtual dispatch and inheritance by defining an abstract interface base class</div><div>which all implementations derive from and override. However, this</div><div>implementation strategy forces an **"is-a"** relationship to exist that is not</div><div>actually meaningful. There is often not some nested hierarchy of useful</div><div>generalizations which code might interact with and move up and down. Instead,</div><div>there is a singular interface which is dispatched across a range of</div><div>implementations.</div><div><br></div><div>An alternate implementation strategy for the second use case which should be</div><div>preferred within LLVM is to that of generic programming. For example, a template</div><div>over some type parameter ``T`` can be instantiated across any particular</div><div>implementation that conforms to the interface. A good example here is the</div><div>highly generic properties of any type which models a node in a directed graph.</div><div>LLVM models these primarily through templates and generic programming. Such</div><div>templates include the ``LoopInfoBase`` and ``DominatorTreeBase``. When this</div><div>type of polymorphism truly needs **dynamic** dispatch, you can generalize it</div><div>using a technique called *concept-based polymorphism* which emulates the</div><div>interfaces and behaviors of templates while using a very limited form of</div><div>virtual dispatch for type erasure inside its implementation. You can find</div><div>examples of this technique in the ``PassManager.h`` system, and there is a more</div><div>detailed introduction to it by Sean Parent in several of his talks and papers:</div><div><br></div><div>#. `Sean Parent's Papers and Presentations</div><div>   <<a href="http://github.com/sean-parent/sean-parent.github.com/wiki/Papers-and-Presentations">http://github.com/sean-parent/sean-parent.github.com/wiki/Papers-and-Presentations</a>>`_</div><div>   - A Github project full of links to slides, video, and sometimes code.</div><div>#. `Value Semantics and Concepts-based Polymorphism</div><div>   <<a href="http://www.youtube.com/watch?v=_BpMYeUFXv8">http://www.youtube.com/watch?v=_BpMYeUFXv8</a>>`_ - The C++Now! 2012 talk</div><div>   describing this technique.</div><div>#. `Inheritance Is The Base Class of Evil</div><div>   <<a href="http://channel9.msdn.com/Events/GoingNative/2013/Inheritance-Is-The-Base-Class-of-Evil">http://channel9.msdn.com/Events/GoingNative/2013/Inheritance-Is-The-Base-Class-of-Evil</a>>`_</div><div>   - The GoingNative 2013 talk describing this technique.</div><div><br></div><div>When deciding between creating a type hierarchy and using virtual dispatch and</div><div>using templates or concepts-based polymorphism, consider whether there is some</div><div>refinement of an abstract base class which is actually a useful type on an</div><div>interface boundary. If anything more refined than the root abstract interface</div><div>is meaningless to talk about as a partial extension of the semantic model, then</div><div>your use case fits better with polymorphism and you should avoid using virtual</div><div>dispatch. However, there may be some exigent circumstances that require one</div><div>technique or the other to be used.</div><div><br></div><div>If you do need to introduce a type hierarchy, we often prefer to used</div><div>explicitly closed type hierarchies with manual tagged dispatch rather than the</div><div>open inheritance model and virtual dispatch that is more common in C++ code.</div><div>This is because LLVM rarely encourages library consumers to extend its core</div><div>types, and leverages the closed and tag-dispatched nature of its hierarchies to</div><div>generate significantly more efficient code. We have also found that a large</div><div>amount of our usage of type hierarchies fits better with tag-based pattern</div><div>matching rather than dynamic dispatch across a common interface.</div></div></div>