Where's the Template?
=====================

   C++ templates are the first language feature to require more
intelligence from the environment than one usually finds on a UNIX
system.  Somehow the compiler and linker have to make sure that each
template instance occurs exactly once in the executable if it is needed,
and not at all otherwise.  There are two basic approaches to this
problem, which I will refer to as the Borland model and the Cfront
model.

Borland model
     Borland C++ solved the template instantiation problem by adding
     the code equivalent of common blocks to their linker; template
     instances are emitted in each translation unit that uses them, and
     they are collapsed together at run time.  The advantage of this
     model is that the linker only has to consider the object files
     themselves; there is no external complexity to worry about.  This
     disadvantage is that compilation time is increased because the
     template code is being compiled repeatedly.  Code written for this
     model tends to include definitions of all member templates in the
     header file, since they must be seen to be compiled.

Cfront model
     The AT&T C++ translator, Cfront, solved the template instantiation
     problem by creating the notion of a template repository, an
     automatically maintained place where template instances are
     stored.  As individual object files are built, notes are placed in
     the repository to record where templates and potential type
     arguments were seen so that the subsequent instantiation step
     knows where to find them.  At link time, any needed instances are
     generated and linked in.  The advantages of this model are more
     optimal compilation speed and the ability to use the system
     linker; to implement the Borland model a compiler vendor also
     needs to replace the linker.  The disadvantages are vastly
     increased complexity, and thus potential for error; theoretically,
     this should be just as transparent, but in practice it has been
     very difficult to build multiple programs in one directory and one
     program in multiple directories using Cfront.  Code written for
     this model tends to separate definitions of non-inline member
     templates into a separate file, which is magically found by the
     link preprocessor when a template needs to be instantiated.

   Currently, g++ implements neither automatic model.  In the mean time,
you have three options for dealing with template instantiations:

  1. Do nothing.  Pretend g++ does implement automatic instantiation
     management.  Code written for the Borland model will work fine, but
     each translation unit will contain instances of each of the
     templates it uses.  In a large program, this can lead to an
     unacceptable amount of code duplication.

  2. Add `#pragma interface' to all files containing template
     definitions.  For each of these files, add `#pragma implementation
     "FILENAME"' to the top of some `.C' file which `#include's it.
     Then compile everything with -fexternal-templates.  The templates
     will then only be expanded in the translation unit which
     implements them (i.e. has a `#pragma implementation' line for the
     file where they live); all other files will use external
     references.  If you're lucky, everything should work properly.  If
     you get undefined symbol errors, you need to make sure that each
     template instance which is used in the program is used in the file
     which implements that template.  If you don't have any use for a
     particular instance in that file, you can just instantiate it
     explicitly, using the syntax from the latest C++ working paper:

          template class A<int>;
          template ostream& operator << (ostream&, const A<int>&);

     This strategy will work with code written for either model.  If
     you are using code written for the Cfront model, the file
     containing a class template and the file containing its member
     templates should be implemented in the same translation unit.

     A slight variation on this approach is to use the flag
     -falt-external-templates instead; this flag causes template
     instances to be emitted in the translation unit that implements
     the header where they are first instantiated, rather than the one
     which implements the file where the templates are defined.  This
     header must be the same in all translation units, or things are
     likely to break.

     See Declarations and Definitions in One Header: C++ Interface,
     for more discussion of these pragmas.

  3. Explicitly instantiate all the template instances you use, and
     compile with -fno-implicit-templates.  This is probably your best
     bet; it may require more knowledge of exactly which templates you
     are using, but it's less mysterious than the previous approach,
     and it doesn't require any `#pragma's or other g++-specific code.
     You can scatter the instantiations throughout your program, you
     can create one big file to do all the instantiations, or you can
     create tiny files like

          #include "Foo.h"
          #include "Foo.cc"
          
          template class Foo<int>;

     for each instance you need, and create a template instantiation
     library from those.  I'm partial to the last, but your mileage may
     vary.  If you are using Cfront-model code, you can probably get
     away with not using -fno-implicit-templates when compiling files
     that don't `#include' the member template definitions.