Exactly when are templates expanded?

C++ templates are only expanded as necessary. The following is error-free even though does_not_exist() does indeed not exist. The method never_called() is never called and thus never expanded, and so does_not_exist() is never needed.

  template< typename X >
  struct
use_non_existant_stuff
  {
    int never_called( )  { does_not_exist( ); }
  };

// no errors or warnings here
use_non_existant_stuff< int > inst_that_does_not_use_methods;

But what about when a template method is expanded. When are the identifiers resolved? Consider the class uses_hidden_fn<..>.

  template< typename X >
  struct
uses_hidden_fn
  {
    X x;
    int call_hidden_fn( )  { return hidden_fn( x); }
  };

namespace hiding_ns {
int hidden_fn( double);
}

// This is OK.
uses_hidden_fn< double > inst_double;

// This fails because hidden_fn( double) is not visible.
int a = inst_double.call_hidden_fn( );

Invoking the method call_hidden_fn() fails because although hidden_fn(double) is defined, it is hidden in the hiding_ns namespace.

You can solve this problem with a simple using hiding_ns::hidden_fn; declaration. And hidden_fn(double) doesn’t have to be exposed before it is needed, only before the end of the compilation unit. The following compiles without error or warning.

  template< typename X >
  struct
uses_hidden_fn
  {
    X x;
    int call_hidden_fn( )  { return hidden_fn( x); }
  };

// This is OK.
uses_hidden_fn< double > inst_double;

// This is OK because hidden_fn( double) is declared below.
int a = inst_double.call_hidden_fn( );

// Declare hidden_fn(double) after we needed it above.
namespace hiding_ns {
int hidden_fn( double);
}
using hiding_ns::hidden_fn;

I’m testing this on the Microsoft (ms9) compiler, but I think it’s standard that templates are not expanded and identifiers are not bound until the end of the compilation unit.

This also compiles without complaint.

  template< typename X >
  struct
uses_hidden_fn
  {
    X x;
    int call_hidden_fn( )  { return hidden_fn( x); }
    int call_hidden_fn2( ) { return hidden_fn2( ); }
  };

namespace hiding_ns {
struct hidden_type { };
}

uses_hidden_fn< hiding_ns::hidden_type > inst;
int a = inst.call_hidden_fn( );
int b = inst.call_hidden_fn2( );

// Declare hidden_fn(..) after we needed it above.
namespace hiding_ns {
int hidden_fn( hidden_type &);
int hidden_fn2( );
}
using hiding_ns::hidden_fn2; // needed
//using hiding_ns::hidden_fn; // not needed!

I was surprised. I thought that we’d still need the using hiding_ns::hidden_fn; declaration at the bottom to make this work, but the (MS) compiler doesn’t complain. Apparently calling hidden_fn(..) with an argument whose type is in the hiding_ns namespace is enough of a hint for the compiler to dig hiding_ns::hidden_fn(hidden_type&) out of that namespace.

If you declare another hidden_fn(hiding_ns::hidden_type&) at top namespace scope the compiler complains that there are two hidden_fn(..)s to choose from. So it does not prefer the exposed declaration over the hidden one.

Although this sort of behavior is interesting, I would recommend strongly against relying on it. Even if it is standard (is it?), it feels like something on the edge. It is clearer to declare hiding_ns::hidden_fn(..) near the top of the file, followed by a using statement. That way hidden_fn(..) is exposed before uses_hidden_fn<..> is expanded.

Variadic tuple<..> — imperative meta programming

Since my last two posts (here and here) are about how might unpack and generate code if it were very smart, I thought I’d bring up a more difficult case. How do you build templated constructors inside the variadic template tuple class?

Remember, this is all fantasy code. The operator will not actually be able to do any of this. Also remember this problem can be solved by defining tuple using a recursive first/rest typelist scheme (see the current Boost implementation).

At first glance it might appear that it’s easy to define a constructor. Just do this.

/* fantasy code -- will not work */

  template< typename ... TYPEs >
  class
tuple
  {
      // Member variables - not a legal use of ...
      private:
      TYPEs ...
    values;

      // Constructor
      public:
    tuple( TYPEs && ... args)
      : values( std::forward( args)) ...
      { }

    /* .. etc .. */
  };

This is pretty good, but we’d like to make all the arguments optional. So we could do this.

/* fantasy code -- will not work */

  template< typename ... TYPEs >
  class
tuple
  {
      // Member variables
      private:
      TYPEs ...
    values;

      // Constructor
      public:
    tuple( TYPEs && ... args = TYPEs( ))
      : values( std::forward( args)) ...
      { }

    /* .. etc .. */
  };

I think the double expansion in the parameter list works. I’m pretty sure you only specify immediately before the variable to be packed, and that all the already-packed variables in the expression will be unpacked at the same time. So you don’t specify again after TYPEs( ).

In any case, this still needs improvement. This requires that all TYPEs have a copy constructor even if they are going to be default constructed. We really want a bunch of constructors, taking zero, one, two, etc arguments.

/* fantasy code -- will not work */

  template< typename ... TYPEs >
  class
tuple
  {
      // Member variables
      private:
      TYPEs ...
    values;

      // Generate a family of constructors (not legal C++).
      // If TYPEs has three types <A, B, C> this
      // generates four constructors:
      //   constructor( )
      //   constructor( A &&)
      //   constructor( A &&, B &&)
      //   constructor( A &&, B &&, C &&)
      for... ( size_t
          N = 0
        ; N <= sizeof...( TYPEs )
        ; ++ N )
      {
          public:
        tuple( TYPEs && unpack...( N ) args)
          : values( std::forward( args)) ...
          { }
      }

    /* .. etc .. */
  };

Yikes, that’s not C++, and we’re not in Kansas anymore. In this fantasy code for… is a meta keyword, interpreted by the compiler and producing a series of constructors. And unpack…(N) only unpacks the first N items in the packed variable TYPEs, and not the entire list.

Instead of for… in the above example we could use plain old for and say the compiler should run code that is not in a code-defining context. But we’d still need to quote or emit the tokens inside the loop above. Something like this.

/* fantasy code -- will not work */

  template< typename ... TYPEs >
  class
tuple
  {
    /* .. etc .. */

      for ( size_t
          N = 0
        ; N <= sizeof...( TYPEs )
        ; ++ N )
      {
        emit {
            public:
          tuple( TYPEs && unpack...( N ) args)
            : values( std::forward( args)) ...
            { }
         }
      }

    /* .. etc .. */
  };

This implementation is still incomplete however. The constructor methods themselves should be templated so you can construct tuples from values with convertible types. With that in mind, here is the last implementation.

/* fantasy code -- will not work */

  template< typename ... TYPEs >
  class
tuple
  {
      // Member variables
      private:
      TYPEs ...
    values;

      // Generate a family of constructors.
      // If TYPEs has three types <A, B, C> this
      // generates four constructors with compatible
      // types:
      //     template< >
      //   constructor( )
      //     template< typename AC >
      //   constructor( AC &&)
      //     template< typename AC, typename BC >
      //   constructor( AC &&, BC &&)
      //     template< typename AC, typename BC, typename CC >
      //   constructor( AC &&, BC &&, CC &&)
      for... ( size_t
          N = 0
        ; N <= sizeof...( TYPEs )
        ; ++ N )
      {
          public:
          template< typename generate...( N ) ARG_TYPEs >
        tuple( ARG_TYPEs && ... args)
          : values( std::forward( args)) ...
          { }
      }

    /* .. etc .. */
  };

This introduces the fantasy generate...(N) meta function to generate a template parameter list of N typenames. This also unpacks values and args at the same time (and in parallel) even though values is packed from TYPEs while args is packed from ARG_TYPES. And args usually packs fewer names than values.

This kind of imperative code generation is sometimes easier to create and understand than the declarative templates C++ currently provides. But it also adds more syntax and keywords to C++, which is plenty complicated already. And a declarative solution that isn't as restrictive as C++ templates may be a better than this imperative suggestion. So I'm not advocating any of this stuff. I'm just thinking out loud, writing it down to see what it looks like.

Variadic tuple<..> — the get<N>() method

In my last post I talked about how a naive implementation of tuple might be easier to understand, and I showed how you might define the member values with the operator, if only were very smart about unpacking (which it isn’t).

The get<N>() method presents additional challenges.

/* fantasy code -- will not work */

  template< typename ... TYPEs >
  class
tuple
  {
      // Member variables
      private:
      TYPEs ...
    values;

      // Generalized get<N>( ) template method
      private:
      template< size_t >
      void
    get( ) const
      { BOOST_STATIC_ASSERT( false); }

      // Specialized get<N>( ) methods:
      //   get<0>( ), get<1>( ), get<2>( ), etc
      // Introduces indexof...(), which is like sizeof...()
      public:
      template< >
      decltype( values ) &
    get< indexof...( values ) >( )
      { return values ; }
      ...

      // Specialized get<N>( ) const methods
      public:
      template< >
      decltype( values ) const &
    get< indexof...( values ) >( ) const
      { return values ; }
      ...

    /* .. etc .. */
  };

You can see how this would work if only could unpack to create a bunch of method specializations. This also requires indexof…(values) which expands into 0, 1, 2, 3 and so on as it unpacks the member variables packed into values.

This would also have to work when a type was const or a reference. But that’s a topic for another day.

Next Page →