Compile-time Type ID of Integral Type?

[Andrew Tomazos]

One of the things we want to do in SG7 Reflection is offer primitives that enable at compile-time the equivalent functionality of typeid, std::type_info and std::type_index (only observing static types of course).

This entails providing a name for the type as a string literal (compile-time string), and providing a hashable and comparable constant expression value for a type.

So for hashablility you should be able to use the primitives to define a variable template like:

    template<typename T>

    constexpr size_t hash_type = /* a hash code for type T */;

And for comparability you should be able to define a variable template like:

    template<typename A, typename B>

    constexpr bool is_less_type = /* is A less than B in some ordering */;

I'm trying to think how to specify the primitives and specifically I want to know if it is feasible to require implementations to provide an integral ID for a type?

For example imagine a standard type trait like:

    template<typename T>

    struct type_id_number : integral_constant<size_t, __type_id_number(T)> {}

    A unique integer for type T.  type_id_number<A> == type_id_number<B> if and only if is_same<A,B>

If this is feasible it seems like the ideal way to cover the hash and comparison use cases.  It would also mean that the value could be used as a non-type template parameter, and also as the condition in a switch.

My questions are:

 - Is it feasible for implementations to provide type_id_number<A> and the supporting intrinsic?

 - If so, what is the effort?

(I'm imagining a counter that increments each time a static type is introduced in a program, but the interaction across TUs and linking isn't clear)

The alternative would be to "raise" the primitives to only standardize hash_type<T> and is_less_type<A,B>, but this offers less flexibility.

[David Krauss]

On 2014–03–29, at 9:24 PM, Andrew Tomazos <andrew...@gmail.com> wrote:

I'm trying to think how to specify the primitives and specifically I want to know if it is feasible to require implementations to provide an integral ID for a type?

You are of course aware of std::type_info::hash_code?

I see no reason it shouldn’t be constexpr. Since C++11 typeid expressions can appear in constant expressions, but there’s nothing you can do with the type_info. So this smells like a defect.

[Bengt Gustafsson]

I think it would be very advantageous if this could be arranged, especially if the numbers could be guaranteed to be "small positive" ints so that a vector or similar can be indexed by the type id number without risk that the vector is suddenly gigabytes in size due to large holes in the number series. This would allow very fast lookup of per-type information that may be needed for instance for serialization etc. and no the least for a RTTI system built on top of the CTTI system.

[David Krauss]

On 2014–03–30, at 12:05 AM, Bengt Gustafsson <bengt.gu...@beamways.com> wrote:

I think it would be very advantageous if this could be arranged, especially if the numbers could be guaranteed to be "small positive” ints

These could only be determined at program load time, which doesn’t really qualify as “compile time” any more.

so that a vector or similar can be indexed by the type id number without risk that the vector is suddenly gigabytes in size due to large holes in the number series.

You can assign serial numbers to types using overload set counting. Be sure that the same numbers are assigned in each TU.

This would allow very fast lookup of per-type information that may be needed for instance for serialization etc. and no the least for a RTTI system built on top of the CTTI system.

Yes, but be careful what you wish for :P .

[Andrew Tomazos]

The current run-time equivalent use cases of the minimum functionality (name, hashable, comparable) are roughly:

    struct foo {};

    template<typename T>

    std::string type_name = typeid(T).name();

    template<typename T>

    size_t hash_type = typeid(T).hash_code();

    template<typename A, typename B>

    bool is_less_type = typeid(A).before(typeid(B));

    int main()

    {

        assert(type_name<foo> == "foo");

        assert(hash_type<foo> == hash_type<foo>);

        assert((!is_less_type<foo, foo>));

    }

The compile-time use cases are therefore something like:

    template<typename T>

    constexpr std::string_literal type_name = ...;

    template<typename T>

    constexpr size_t hash_type = ...;

    template<typename A, typename B>

    constexpr bool is_less_type = ...;

    static_assert(type_name<foo> == "foo");

    static_assert(hash_type<foo> == hash_type<foo>);

    static_assert((!is_less_type<foo, foo>));

If type_id_number<T> is feasible the later two could be implemented pure library as:

    template<typename T>

    constexpr size_t hash_type = std::type_id_number<T>;

    template<typename A, typename B>

    constexpr bool is_less_type = std::type_id_number<A> < std::type_id_number<B>;

If it is not feasible, then the later two would have to be provided as the primitives in some form.  In this case we would consider extending std::type_info somehow, by making name, before and hash_code constexpr for example, but there are a couple of wrinkles with this approach that need further study.  typeid strips the cv-qualifiers and reference from the type, we would like to leave them to the user to decide whether to apply the appropriate remove traits.  typeid also returns a reference, so requiring that this be a reference constant expression could interact badly with the dynamic version of typeid.  Also specifying std::type_info as a literal type when it is polymorphic is non-trivial.  My current feeling about this is that there might be a separate interface equivalent std::static_type_info<T> class template that provides these functions as static functions or variables - or, more likely, that all three would be three separate type traits in the usual form.

[David Krauss]

On Sunday, March 30, 2014 3:26:37 AM UTC+8, Andrew Tomazos wrote:

The current run-time equivalent use cases of the minimum functionality (name, hashable, comparable) are roughly:

I see that you changed some consts to constexprs between these two illustrations, but I don't get what you're trying to illustrate.
 

If type_id_number<T> is feasible the later two could be implemented pure library as:

Obviously we can't have a perfect hash of types to integers because integers are bounded and types aren't.
 

typeid strips the cv-qualifiers and reference from the type, we would like to leave them to the user to decide whether to apply the appropriate remove traits.  

They won't be stripped if inside a template argument, so I'd recommend taking the id of identity< T > in the corner cases where you want to preserve top-level reference and const. Also note that expressions don't have reference type and scalar expressions don't have top-level const; those things are only re-added by decltype.
 

typeid also returns a reference, so requiring that this be a reference constant expression could interact badly with the dynamic version of typeid.  

It returns an lvalue; expressions don't have reference type. Presumably it's already a reference constant expressions since it's allowed in a constant expression, but this point should be clarified.
 

Also specifying std::type_info as a literal type when it is polymorphic is non-trivial.  

type_info does not behave differently for polymorphic types. They have more internal RTTI properties but I don't see the relevance or the problem.
 

My current feeling about this is that there might be a separate interface equivalent std::static_type_info<T> class template that provides these functions as static functions or variables - or, more likely, that all three would be three separate type traits in the usual form.

Why not let std::static_type_info<T> be a variable template of invariant type? It seems like the application for which variable templates were invented.

The type_info objects from various TUs would need to be merged. This problem is why typeid has slightly weird semantics. But it seems it already must be solved for a platform to support variable templates, so maybe typeid should be tidied up as well.

[David Krauss]

On Sunday, March 30, 2014 10:50:15 AM UTC+8, David Krauss wrote:

The type_info objects from various TUs would need to be merged. This problem is why typeid has slightly weird semantics. But it seems it already must be solved for a platform to support variable templates, so maybe typeid should be tidied up as well.

To be clear: variable templates solve the compile-time identifier-value issue, because you can use the address of the variable template instantiation.

You just can't use relative comparisons on the addresses, or cast to intptr_t in a constant expression.

My impression is that hash_value already just gives you a suitably casted address of a typeinfo object. The easiest way out of all this is probably just to verify that's a suitable spec, and specify it just as such.

[David Krauss]

On 2014–03–30, at 10:57 AM, David Krauss <pot...@gmail.com> wrote:

My impression is that hash_value already just gives you a suitably casted address of a typeinfo object. The easiest way out of all this is probably just to verify that's a suitable spec, and specify it just as such.

Oh. I have been dancing around the problem that hash_value may computed by the linker or loader.

For what it’s worth, I don’t see what a global “small” serial number for all types solves anyway, because it will get big when someone else uses the facility more heavily.

A well-behaved introspective type-map enumerates its contents, and then you can use my overload-set counting. Asking template instantiations in two TUs to form a relative ordering is a tall order though. It could probably be done with an export template model but otherwise it seems contrary to the fundamentals.

As for solving the problem at hand, rather than mucking about with compile time strings, it might be better to make constexpr typeinfo::operator== and before. The latter forces the collation order not to depend on addresses though, but rather something like strcmp. To avoid disturbing ABIs, it might be better to introduce operator< instead with a potentially different ordering. (While we’re at it, make it a non-member!)

To be clear:

• before may be faster at runtime because addresses are available, but cannot be constexpr.
• operator< may be slow at runtime yet may be constexpr.
• An implementation of operator== would want to use operator< at compile time and before at runtime.

Anyone have a better idea?

[Andrew Tomazos]

On Sunday, March 30, 2014 4:50:15 AM UTC+2, David Krauss wrote:

On Sunday, March 30, 2014 3:26:37 AM UTC+8, Andrew Tomazos wrote:

If type_id_number<T> is feasible the later two could be implemented pure library as:

Obviously we can't have a perfect hash of types to integers because integers are bounded and types aren't.

Within a single program there are going to be less than 2^32 types, but I think might be right that type_id_number<T> can't be calculated until link/load time, so can't be an integer constant expression.

  

typeid strips the cv-qualifiers and reference from the type, we would like to leave them to the user to decide whether to apply the appropriate remove traits.  

They won't be stripped if inside a template argument, so I'd recommend taking the id of identity< T > in the corner cases where you want to preserve top-level reference and const. Also note that expressions don't have reference type and scalar expressions don't have top-level const; those things are only re-added by decltype.

That would be a reasonable workaround, but I'll still need to consider how it appears within the reflection use cases and next to type traits.  My sense is that reflecting const and reference will be common enough to warrant being the default.

 

typeid also returns a reference, so requiring that this be a reference constant expression could interact badly with the dynamic version of typeid.  

It returns an lvalue; expressions don't have reference type. Presumably it's already a reference constant expressions since it's allowed in a constant expression, but this point should be clarified.

 

Yes fine, that is what I meant, it is an lvalue in a constant expression.  This can cause problems.

Also specifying std::type_info as a literal type when it is polymorphic is non-trivial.  

type_info does not behave differently for polymorphic types. They have more internal RTTI properties but I don't see the relevance or the problem.

I meant std::type_info can be itself a polymorphic type, but actually this may be wrong.  It can be a base class of some derived type.

 

My current feeling about this is that there might be a separate interface equivalent std::static_type_info<T> class template that provides these functions as static functions or variables - or, more likely, that all three would be three separate type traits in the usual form.

Why not let std::static_type_info<T> be a variable template of invariant type? It seems like the application for which variable templates were invented.

 

For presentation, given the integral ID isn't feasible, the current front-runner is three separate type traits (one for type name, one for type hash and the other for type less).  You can then compose them however you want.

To be clear: variable templates solve the compile-time identifier-value issue, because you can use the address of the variable template instantiation.

Well you can already get a per-type address constant expression with:

    template<class T> int x;

    template<class T> constexpr int* p = &x<T>;

But you can't hash it or compare it in a constant expression, so it doesn't solve the problem.

As for solving the problem at hand, rather than mucking about with compile time strings, it might be better to make constexpr typeinfo::operator== and before. The latter forces the collation order not to depend on addresses though, but rather something like strcmp. To avoid disturbing ABIs, it might be better to introduce operator< instead with a potentially different ordering. (While we’re at it, make it a non-member!)

I guess my current design would have `std::is_less<A,B>` next to `std::is_same<A,B>` where is_less is implementation-defined, but in practice may be based on mangling the type to a string and using a lexical comparison.  The same string could be hashed to provide `std::hash_type<T>`.

I think keeping it separate from std::type_info is the better approach given the clearly different environments of compile-time and run-time.  You can always compose the primitives and build out a system that can be shared with run-time if you so desire. 

[Thiago Macieira]

Em dom 30 mar 2014, às 04:18:07, Andrew Tomazos escreveu:
> I meant std::type_info can be itself a polymorphic type, but actually this
> may be wrong. It can be a base class of some derived type.

And it is in the portable C++ ABI.

--
Thiago Macieira - thiago (AT) macieira.info - thiago (AT) kde.org
Software Architect - Intel Open Source Technology Center
PGP/GPG: 0x6EF45358; fingerprint:
E067 918B B660 DBD1 105C 966C 33F5 F005 6EF4 5358