Simulating Partial Specialization

From: Mat Marcus (mmarcus_at_[hidden])
Date: 2000-09-29 17:03:29

Colleagues:

Today much of the current C++ literature laments the lack of 
widespread compiler support for partial template specialization. 
There are some well known workarounds, but they tend to be of limited 
applicability. We are currently employing a "simulated partial 
specialization" technique that applies to a broader range of 
problems. In particular allows specialization of template classes for 
pointer types. One interesting application is to allow improved STL 
implementations on non-compliant compilers. The following code was 
tested on Microsoft Visual C++ 6 service pack 3. In this toy example 
we present a simple vector class which is specialized for pointer 
types. The template metaprogramming techniques used support 
simulation of other partial specialization features, e.g. holding one 
or more template parameters fixed, as well as a kind of poor man's 
typeof. We have enjoyed some success applying these techniques to a 
larger STL-style generic container library.

Here is an outline of the idea. We make use of the IF template 
metafunction  (or SWITCH if there is more than one specialization) 
and the sizeof operator.

IF --- IF is actually a template struct based on a bool and two type 
parameters - IF<bool, IfType, ElseType>. It 'returns'  the 
appropriate type via the RET typedef where RET stands for return.

sizeof --- we recently learned of the flexibility of the sizeof 
operator.In particular sizeof can accept a function expression 
without evaluating the function. We declare (but do not define) a 
pair of discriminating functions to determine if a specialization 
applies. In the case of pointers we (essentially) use

        char IsPtr(const volatile void*);
        int IsPtr(...);

We convert this pair of discriminating functions into a template 
metafunction ISPTR<T>.  That is, ISPTR <T> returns true in the RET 
enum if and only if T is a pointer type. Finally this allows us to 
write IF<ISPTR<T>::RET, PointerSpecialized<T>, 
Unspecialized<T> >::RET to achieve simulated partial specialization 
where PointerSpecialized is the specialized version of the type and 
Unspecialized is the general case. By varying these discriminators we 
can specialize on other criteria.

As stated above we can generalize this technique using the SWITCH 
metafunction and more than two discriminating functions. For example 
we might define a discriminating metafunction SPECIALIZER which 
returns an int rather than a bool. Than the simulated specialization 
would look like

         SWITCH<SPECIALIZER<T>,
                 CASE<1, FIRST_SPECIALIZATION<T>,
                 CASE<2, SECOND_SPECIALIZATION<T>,
                 CASE<DEFAULT, GENERAL_CASE<T> >::RET

Needless to say it is possible to discriminate on more than one 
template parameter.

Hope you find this useful,

Mat Marcus  - mmarcus_at_[hidden]
Jesse Jones - jejones_at_[hidden]

References:
Thanks to Krzysztof Czarnecki & Ulrich Eisenecker for the 
metaprogramming skills from the book Generative Programming. Thanks 
to Scott Meyers and Andrei Alexandrescu for the posts regarding the 
utility of the sizeof operator. Thanks to John R. Bandela for making 
us consider whether there might be some  portable way to simulate 
partial specialization.

License: The Adobe source code below is provided under the Adobe Open 
Source License 1.0. Please see file AdobeLicense.txt for licensing 
information.

//##################################################################
//  File:   PartialSpecialization.cpp
// Authors: Mat Marcus and Jesse Jones
// Copyright 2000 Adobe Systems Incorporated and others. All rights reserved.
// The original version of this source code may be found at 
http://opensource.adobe.com.
// The contents of this file are subject to the Adobe Open Source
// License Version 1.0.

#include <iostream>
#include <string>
#include "metactrl.h"   // General template meta-functions
#include "is_ptr.h"     // IsPtr template meta-function

template <class T>
struct SimpleVector {
     // Simple example vector class. We omit almost all implementation.
     friend std::ostream& operator<<(std::ostream& out, const SimpleVector<T>&)
     {
         return out << "is a simple vector";
     }
};

template <class T>
struct PtrVector {
     // Simple example vector of pointers class. We omit almost all 
implementation.
     friend std::ostream& operator<<(std::ostream& out, const PtrVector<T>&)
     {
         return out << "is a pointer vector";
     }

};

template <class T>
struct SELECT_VECTOR {
     // The SELECT_VECTOR   meta-function exists simply to make
     // the following code more readable.
      typedef typename metactrl::IF<metactrl::ISPTR<T>::RET,
                                                      PtrVector<T>,
                                                      SimpleVector<T>
                                                     >::RET Vector;
};

/* The heart of the matter. The meta-function metactrl::IF takes a boolean
    and returns the second type parameter if true else the third. This is a
    useful tool in template metaprogramming (see metactrl.h for details).
    The meta-function metactrl::ISPTR makes use of the sizeof operator to
    convert a type into a bool indicating whether or not it is a pointer.
    See is_ptr.h for details.
*/

template <class T>
struct Vector : public SELECT_VECTOR<T>::Vector {
     // One way to achieve a general Vector class is to inherit from the
     // appropriate specialization. Clients can simply use Vector<T> and
     // we will specialize accordingly. However this inheritance based
     // wrapper approach has some limitations.
};

// We illustrate two approaches to simulated partial specialization

int main(int argc, char* argv[])
{
// Example 1 using the inheritance based wrapper approach
     Vector<int> vi;
     std::cout << "Vector of int " << vi << std::endl;
     //Output: Vector of int is a simple vector

     Vector<int*> vip;
     std::cout << "Vector of int* " << vip << std::endl;
     //Output: Vector of int* is a pointer vector

// Example 2 using the direct approach
     SELECT_VECTOR<std::string>::Vector ds;
     std::cout << "Vector of string " << ds << std::endl;
     //Output: Vector of string is a simple vector

     SELECT_VECTOR<std::string*>:: Vector dsp;
     std::cout << "Vector of string* " << dsp << std::endl;
     //Output: Vector of string* is a pointer vector

     return 0;
}

//##################################################################

//  File:   is_ptr.h
//  Authors: Mat Marcus and Jesse Jones
// Copyright 2000 Adobe Systems Incorporated and others. All rights reserved.
// The original version of this source code may be found at 
http://opensource.adobe.com.
// The contents of this file are subject to the Adobe Open Source
// License Version 1.0.

namespace metactrl {
     namespace intimate {
         struct PointerShim {
         // Since the compiler only allows at most one non-trivial
         // implicit conversion we can make use of a shim class to
         // be sure that IsPtr below doesn't accept classes with
         // implicit pointer conversion operators
             PointerShim(const volatile void*); // no implementation
         };

         // These are the discriminating functions
         char IsPtr(PointerShim); // no implementation is required
         int IsPtr(...);          // no implementation is required
     }

     template <class T>
     struct ISPTR {
         // This template meta function takes a type T
         // and returns true exactly when T is a pointer.
         // One can imagine meta-functions discriminating on
         // other criteria.

         enum { RET = (sizeof(intimate::IsPtr(*(T*)0)) == 1) };
     };
}

//##################################################################

//  File:   metactrl.h
//  Authors: Krzysztof Czarnecki & Ulrich Eisenecker
//  We present only a small subset here

/* The following functions come from chapter 10 of the indispensable book
Generative Programming by Krzysztof Czarnecki & Ulrich Eisenecker
  (C) Copyright Krzysztof Czarnecki & Ulrich Eisenecker 1998-2000.
Permission to copy, use, modify, sell and distribute this software is
granted provided this copyright notice appears in all copies. In case of
modification, the modified files should carry a notice stating that
you changed the files.
This software is provided "as is" without express or implied
warranty, and with no claim as to its suitability for any purpose.
*/
namespace metactrl
{

// IF<> // version for compilers without partial specialization

   namespace intimate
   {
         struct SelectThen
         {       template<class Then, class Else>
                 struct Result
                 {       typedef Then RET;
                 };
         }; // end SelectThen

         struct SelectElse
         {       template<class Then, class Else>
                 struct Result
                 {       typedef Else RET;
                 };
         }; // end SelectElse

         template<bool Condition>
         struct Selector
         {       typedef SelectThen RET;
         }; // end Selector

         template<>
         struct Selector<false>
         {       typedef SelectElse RET;
         }; // end Selector<false>
   } // end namespace intimate

   template<bool Condition, class Then, class Else>
   struct IF
   {     typedef intimate::Selector<Condition>::RET select;
         typedef select::Result<Then,Else>::RET RET;
   }; // IF
} // end  namespace metactrl

// CASE<>, SWITCH<> // version for compilers without partial specialization

const int DEFAULT = -32767;

namespace intimate
{
     const int NilValue = -32768;

     struct NilCase
     {   enum {tag = NilValue};
         typedef NilCase RET;
     }; // NilCase
} // end namespace intimate;

template <int Tag,class Statement,class Next = intimate::NilCase>
struct CASE
{   enum {tag = Tag};
     typedef Statement statement;
     typedef Next next;
}; // CASE

template <int Tag,class aCase>
struct SWITCH
{       typedef aCase::next nextCase;
enum {  tag = aCase::tag,   // VC++ 5.0 doesn't operate directly on 
aCase::value in IF<>
         nextTag = nextCase::tag,// Thus we need a little cheat
         found = (tag == Tag || tag == DEFAULT)
      };
typedef IF<(nextTag == intimate::NilValue),
             intimate::NilCase,
             SWITCH<Tag,nextCase> >
         ::RET nextSwitch;
typedef IF<(found != 0),
             aCase::statement,
             nextSwitch::RET>
         ::RET RET;
}; // SWITCH

//#########################################
//file: AdobeLicense.txt

Notice to User: Adobe Systems Incorporated ("Adobe") is providing the 
source code in these documents for use under the terms of this Adobe 
Open Source License Agreement ("Agreement"). Any use, reproduction, 
modification, or distribution of the source code, resulting object 
code, or related documentation on this site, or any derivatives 
thereof (collectively, the "Software") constitutes your acceptance of 
this Agreement. Adobe reserves the right to make changes to this 
Agreement from time to time at its sole discretion. The version of 
this Agreement posted on the date you download the Software will 
apply to that version of the Software.
1.	License Grant
Subject to the terms of this Agreement, Adobe grants you a 
non-exclusive, worldwide, royalty free license to use, reproduce, 
prepare derivative works, publicly display, publicly perform, 
distribute, and sublicense the Software for any purpose, provided the 
copyright notice below, appears in a conspicuous location within the 
source code of the distributed Software and this license is 
distributed with the version of the Software you distribute in the 
supporting documentation.
        Copyright (Date Here) Adobe Systems Incorporated and others. 
All rights reserved.
The original version of this source code may be found at 
http://opensource.adobe.com.

If you choose to distribute the Software in a commercial product, you 
do so with the understanding that you agree to defend, indemnify, and 
hold harmless Adobe against any losses, damages, and costs, arising 
from the claims, lawsuits, and other legal actions, arising out of 
such distribution. You may distribute the Software in object code 
form under your own license, provided that your license agreement:
(a)	complies with the terms and conditions of this license agreement;
(b)	effectively disclaims all warranties and conditions, express 
or implied, on behalf of Adobe;
(c)	effectively excludes all liability for damages, on behalf of Adobe;
(d)	states that any provisions that differ from this Agreement 
are offered by you alone and not Adobe; and
(e)	states that the Software covered by this Agreement is 
available from you or Adobe and informs licenses how to obtain it in 
a reasonable manner on or through a medium customarily used for 
software exchange.
2.	Disclaimer of Warranty
ADOBE LICENSES THE SOFTWARE TO YOU ONLY ON AN "AS IS" BASIS WITHOUT 
WARRANTIES OR CONDITIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED, 
INCLUDING WITHOUT LIMITATION ANY WARRANTIES OR CONDITIONS OF TITLE, 
NON-INFRINGEMENT, MERCHANTABILITY OR FITNESS FOR A PARTICULAR 
PURPOSE. ADOBE MAKES NO WARRANTY THAT THE SOFTWARE WILL BE 
ERROR-FREE. Each user of the Software is solely responsible for 
determining the appropriateness of using and distributing the 
Software and assumes all risks associated with its exercise of rights 
under this Agreement, including but not limited to the risks and 
costs of program errors, compliance with applicable laws, damage to 
or loss of data, programs, or equipment, and unavailability or 
interruption of operations. Use of the Software is done so with the 
understanding that Adobe will not provide you with any technical or 
customer support or maintenance. Some states or jurisdictions do not 
allow the exclusion of implied warranties or limitations on how long 
an implied warranty may last, so the above limitations may not apply 
to you. To the extent permissible, any implied warranties are limited 
to ninety (90) days.
3.	Limitation of Liability
ADOBE SHALL NOT BE LIABLE FOR LOSS OR DAMAGE ARISING OUT OF THIS 
AGREEMENT OR FROM THE USE OF THE SOFTWARE. IN NO EVENT WILL ADOBE BE 
LIABLE TO YOU OR ANY THIRD PARTY FOR ANY DIRECT, INDIRECT, 
CONSEQUENTIAL, INCIDENTAL, OR SPECIAL DAMAGES INCLUDING LOST PROFITS, 
LOST SAVINGS, COSTS, FEES, OR EXPENSES OF ANY KIND ARISING OUT OF ANY 
PROVISION OF THIS AGREEMENT OR THE USE OR THE INABILITY TO USE THE 
SOFTWARE, HOWEVER CAUSED AND UNDER ANY THEORY OF LIABILITY, WHETHER 
IN CONTRACT, STRICT LIABILITY OR TORT (INCLUDING NEGLIGENCE OR 
OTHERWISE), EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.
4.	Trademark Usage
Adobe is a trademark or registered trademark of Adobe Systems 
Incorporated in the United States and/or other countries. Neither the 
Adobe name nor the Adobe logo may be used to endorse or promote 
products derived from this site.
5.	Termination
User rights shall terminate under this Agreement if the user fails to 
comply with any of the material terms or conditions of this Agreement 
and does not cure such failure in a reasonable period of time after 
becoming aware of such noncompliance. If all user's rights under this 
Agreement terminate, user agrees to cease use and distribution of the 
Software as soon as reasonably practicable.
6.	Governing Law and Jurisdiction
This Agreement is governed by the statutes and laws of the State of 
California, without regard to the conflicts of law principles 
thereof. If any part of this Agreement is found void and 
unenforceable, it will not affect the validity of the balance of the 
Agreement, which shall remain valid and enforceable according to its 
terms. This is the entire agreement between Adobe and you relating to 
the Software.