Simplifing tuples

[Giovanni Bajo]

Benjamin Kosnik wrote:

> We used to compute <limits> at build time, and it only worked (well)
> for native targets. I don't see why this should be a limitation for tuple.

To be fair, <limits> is an example of a header which is *strictly* dependent on
the platform. <tuple> is much more independent. Another point towards
build-time complexity is that it's done once, that is it's faster for the end
user. But let's wait for Chris.

>> I think there is no perfect solution for this. If it were up to me,
>> I would try to generate everything with preprocessor magic, but
>> without making it recursive ala Boost. There is probably a way to
>> flat the template hierarchy so that you do not get hundreds of lines
>> of instantiation context.
>
> Did you have something specific in mind?

Well, if you look at the Boost implementation, they convert the types of the
elements into a typelist, which is then used recursively. Also the data
representation is recursive:

template <class Head, class Tail>
struct cons
{
   Head data;
   Tail rest;
};

where of course the trick is that 'Tail' can be a cons<> again. Now (just how
Chris showed us) this means that accessing an element is O(n) at *compile*
time[1] because the list is traversed linearly by the compiler. The stack of
instantiations / function calls will be linear in the index of the element. So,
if there is an error accessing an element at index #4, it will have an
instatition stack printed which two times bigger than an item at index #2.

This was done to keep the implementation simple. Now, we could have tuple<>
layered out like this (assuming max 4 elements for simplicity):

template <class T1, class T2=none_t, class T3=none_t, class T4=none_t>
struct tuple
{
   T1 t1;
   T2 t2;
   T3 t3;
   T4 t4;
};

template <class T1, class T2, class T3>
struct tuple<T1,T2,T3,none_t>
{
   T1 t1;
   T2 t2;
   T3 t3;
};

template <class T1, class T2, class T3>
struct tuple<T1,T2,none_t,none_t>
{
   T1 t1;
   T2 t2;
};

template <class T1, class T2, class T3>
struct tuple<T1,none_t,none_t,none_t>
{
   T1 t1;
};


This is a flat representation, so errors are going to have a O(1) instantiation
stack on the number of elements. All the methods have to be probably duplicate,
and this is where I would probably use the preprocessor magic.



> Perhaps it would be best if
> we both wait for Chris to post something....

Sure.


>> Working on an extension to drive the error machinery from the
>> compiler is also preferrable. I think the best would be to come up
>> with a way to write a static assert such as:
>>
>> STATIC_ASSERT(sizeof(T) > N,  "type %qT too small", T);
>>
>> which would emit something like:
>>
>> blah.h:2345: error: type 'int' too small
>>
>> I wonder if __builtin_static_assert(sizeof(T)>N, "type %qT too
>> small", T) would do the trick.
>
> You might ask Chris about this. I think this might be useful,
> actually. However, here we go again, with dependent expressions.....

AFAICT, we can use dependent types in builtin functions. It's not a problem.

> Do you have an implementation in mind?

Wes, but we will have to push it to get it into 4.0.

> If you come up with one perhaps we could
> experiment with it, and see. This would probably be useful, actually:

Yeah, I can see *many* uses. For instance, thinking of tuples, if you implement
the get<> accessor you will need a template function to return the type of the
Nth element:

template <int N>
typename get_element_type<N,4>::type  get(void)   // 4 because it's a 4-ary
tuple
{
    __builtin_static_assert(N >= 4, "invalid index %d for %d-ary tuple '%T'",
N, 4, tuple);  // tuple is the injected class name :)
}

error: invalid index 4 for a 2-ary tuple 'tuple<int, float>'

Of course, you need get_element_type *not* to do a compile-time error for
out-of-range indexes (like, returning none_t or whatever), so that the error
can be caught when the function is called. I dare anybody generating a better
error message actually.

Also, the concept check machinery you use everywhere could be rewritten to use
__builtin_static_assert() and thus providing a cute, informative error message:

error: The iterator you passed 'struct MyIterator' is not a Bidirectional
Iterator so it cannot be used for this function


Another thing that came to my mind is that __builtin_static_assert would have
another argument which is the exact number of instantiation contexts to hide
while priting the error. For instance, with the static_assert above you get
this:

int main(void)
{
  tuple<int, float> t;
  int a = t.get<4>();     // line #10
}

In function main():
/tr1/tuple:123: instantiatied from 'typename get_element_type<N,4>
tuple<int,float,none_t,none_t>::get(void) [with N = 2]'
main:10: instantiated from here
/tr1/tuple:123: invalid index 4 for a 2-ary tuple 'tuple<int,float>'

But if we specify a way to skip instantiation contexts, we could use it to skip
1 context in this case, line in:

__builint_static_assert(1, N >= 4, "invalid index %d for %d-ary tuple '%T'", N,
4, tuple);
// see the first argument 1, means skip '1' instantiation context because we
know that we are 1 function deep wrt user call.


In function main():
main:10: instantiated from here
main:10: invalid index 4 for a 2-ary tuple 'tuple<int,float>'

Notice how also the error location was skipped one position up into the
instantiation stack. In this very case, the instantiation context will happen
to be emtpy, so G++ could be probably smarter and cut it away completely to
get:

main:10: invalid index 4 for a 2-ary tuple 'tuple<int,float>'

And when you see this, you would wonder if tuple<> is a compiler builtin...
which is not :)

Giovanni Bajo