What happens if you specialise a template when a library
is already using the unspecialised version?

----------------------------------------------------------------

            ISO:       WG21/N0xxx
            ANSI:      94-xxxx
            Author:    John Max Skaller
            Date:      April 1994
            Reply to:  maxtal@suphys.physics.su.oz.au

TEMPLATE SPECIALISATIONS and NAMESPACES
---------------------------------------

Executive Summary: A specialisation of a template may be
declared or defined in a namespace other than that
of the original template.


THE STATUS QUO
--------------

At present it is my interpretation that a specialisation
must be declared and defined in the namespace in which
the template it specialises is declared and defined.


THE HIJACKING PROBLEM
---------------------

Specialisations in the same namespace have a serious
software engineering problem. Suppose a programmer
provides a library which defines a template X,
and also uses an unspecialised X<U> for some U
in the imlementation of the library.


   template<class T> void f(T) { ..}
   template<class T> class X { .. };

   void g() {
        X<U> xu;
        f(xu);
   }

If another programmer then defines a specialisation
of X<T>, two definitions of X<T> exist.

   void f<U>(U) { ..} // specialisation
   class X<U> { .. }; // specialisation

   void h() {
        X<U> xu;
        f(xu);
   }

A diagnostic may or may not be issued, and the source code for
the library may not be available to allow the programmer
to determine what the cause of the problem is.

This hijacking can only be prevented by the library writer
documenting every use of all templates, implementation
details that may change with versions of the library and
which the application programmer should not be exposed to.

   // IN MY LIBRARY I USE THE UNSPECIALISED FUNCTION f(U)
   // AND THE UNSPECIALISED CLASS X<U>
   // PLEASE DONT SPECIALISE THESE TEMPLATES

A similar problem occurs if the library uses specialisations,
but the requirement that these must be declared helps
alleviate the problem: however this is still only documentation,
no error is detected if the user simply provides a conflicting
specialisation that matches the declaration.

Simply saying that the behaviour in the presence of
conflicting definitions is undefined is not adequate: it is lousy
management to give a programmer responsibilities without
the information or techniques necessary to act responsibly.

HIJACKING THE STANDARD LIBRARY
------------------------------

The problem for user specialisations of Standard Library
templates is worse: the only way to specialise them
is to invade the Standard Library namespace.


   // user code ..
   namespace std {
     class basic_string<MyChar> { .. }
   }

It would be better to reserve the "std" namespace exclusively
for implementors, but preventing user specialisations of
Standard Library templates is draconian.

In addition it is unclear that a declaration added to
a namespace is actually visible if the extension is done
after a using declaration has been issued: at present
my interpretation is that only declarations visible at the
point of issuing the using declaration are "injected"
and those added afterwards are not made visible.


THE SOLUTION
------------

Luckily there is a simple and very effective solution to this
problem: it requires no new features but a clarification
of the way that templates interact with namespaces.

The idea is simple: if a template X is declared in namespace A,
you may declare or define a specialisation X<U> in namespace B
provided the template A::X is visible.

When you use X<U>, two searches are performed. The first search
looks for the template X and finds it in A, the second search
then looks for any specialisations X<U> and finds one in B.
If no specialisation is found, the use is bound to the
generated instance A::X<U>.

This mechanism allows multiple user specialisations to
coexist in harmony without conflict, as well as allow
use of unspecialised versions.

EXAMPLE
-------

     // here two specialised and one unspecialised definitions
     // coexist peacefully

     template<class T> class X { ..  } // original template ::X

     X<int> xi1; // use of default, generated, or unspecialised version

     namespace user1 {
       class X<int> { .. } // announce specialisation
       X<int> xi2;           // bind interface to ::X<int>
                             // bind definition to user1::X<int>
     }

     namespace user2 {
       class X<int> { .. } // announce specialisation
       X<int> xi3;           // bind interface to ::X<int>
                             // bind definition to user2::X<int>
     }

     // the dual binding of interface and definition is
     // analogous to virtual functions, the use of namespaces
     // to inheritance

   Implementation: When an instance is used,
   search for a true declaration of the template first, ignoring
   specialisation declarations.

   Then search for specialisation declarations. Ensure the name of the
   namespace in which the specialisation is defined is
   mangled into its external linkage name.


OPEN CLOSED PRINCIPLE
---------------------

  The open closed principle requires a module to be simultaneously
  closed so it can be used, and open so it can be extended.

  That classes and inheritance allow this is the keystone of
  class based object oriented languages.

  That declaration of specialisations in namespaces allows the
  original template to be closed and protected from interference
  while at the same time being open by permitting specialisations
  in namespaces is strong theoretical evidence that the proposal
  is coherent and sound.


IMPLEMENTATION METHOD
---------------------

Implementation is straightforward. Each use of a template
instance needs to bound to a particular definition.
For a function, that binding is performed as usual
by use of an external name which has the namespace
of the definition mangled into it.

For a class, binding the interface is done by normal
lookup and scope rules, binding the methods is again
a matter of name mangling involving the appropriate namespace name.

Since most compilers already supporting specialisations and
namespaces probably do this anyhow, I dont see any problems
with implementation here.

DIFFICULTIES
------------

The proposal introduces a difficulty which has several
possible resolutions. Consider:

  template<class T> class X { ..}
  namespace user {
    X<U> xu1;         // use unspecialised version
    class X<U> { .. } // specialisation
    X<U> xu2;         // use specialised version
  }

It does not appear consistent to allow X<U> to mean two
different things in the same namespace, however in fact
it is consistent and existing practice in other circumstances:

   class A { .. }
   namespace user {
     A a1;
     class A { .. }
     A a2;
   }


However consider:

   template<class T> void f(U) { ..}
   U u;
   f(u); // calls unspecialised version
   void f<U>(U) { .. } // specialisation
   f(u); // calls specialisation

While allowing the above code is consistent
it requires two definitions of the same function in the
same namespace.  This can be implemented by marking
the mangled names of specialisations and unspecialised generated
definitions differently, but I dont consider it very nice.

A compromise rule banning definition of a specialisation in
the same namespace as the declaration of the template
after use of an unspecialised version provides compatibility
but is too ugly.

It is not so easy to extend this solution to other namespaces:

  template<class T> class X { ..}
  namespace user {
    namespace inner {
      X<U> xu1;         // use unspecialised version
    }
    class X<U> { .. } // specialisation
    namespace inner {
      X<U> xu2;         // use specialised version
    }
  }

because here the specialisation is not in either the
namespace of the template or the use of the instance X<U>.

A more general rule:

  "Every use of a template instance in a declarative region
   shall use the same specialisation or the unspecialised version"

provides complete consistency, however. Unfortunately,
breaches of this rule cannot always be diagnosed because
namespaces are not encapsulated.







--
        JOHN (MAX) SKALLER,         INTERNET:maxtal@suphys.physics.su.oz.au
 Maxtal Pty Ltd,      CSERVE:10236.1703
        6 MacKay St ASHFIELD,     Mem: SA IT/9/22,SC22/WG21
        NSW 2131, AUSTRALIA