Idea: constexpr type_info

[Myriachan]

I think that it would be nice if typeid(T) for type T and typeid(X) for compile-time constant expression X would return something considered to be a compile-time constant expression itself, such as what amounts to a const reference to a "__declspec(selectany) extern const std::type_info" global, to use Microsoft "selectany" terminology.  Then, have the name(), before(), ==() and !=() member functions be constexpr as well.

This would allow the compile-time acquisition of type names as strings without using macros.

hashcode() is possible to be a constexpr as well, but there are a few reasons to not allow this; prevention of denial-of-service attacks is one reason that hashcode() may return different values each run of a program, and making it a constexpr would break that.

Melissa

[Andrew Tomazos]

This is something we've been working on over at SG7: https://groups.google.com/a/isocpp.org/forum/?fromgroups#!forum/reflection

We would welcome a formal proposal and reference implementation something like a constexpr std::type_info.  I studied it and concluded that "upgrading" std::type_info without breaking changes would be a hassle, so the latest idea was to have a TextTrait (see N4113) called std::type_name<T>.  To streamline N4113 I removed std::type_name<T>, so if you want to take a run at it you would be welcome.

For the constant expression (rather than type) version you could use std::type_name<decltype(X)>.  The idea was that the name would also be comparable (before) and hashable (hashcode).

If you're interested write up a paper (for constexpr std::type_info or std::type_name<T> or something else) and post it to the previously linked SG7 reflector.

Cheers,

Andrew.

--

---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposal...@isocpp.org.
To post to this group, send email to std-pr...@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/.

[David Krauss]

On 2014–07–10, at 11:38 AM, Andrew Tomazos <andrew...@gmail.com> wrote:

This is something we've been working on over at SG7: https://groups.google.com/a/isocpp.org/forum/?fromgroups#!forum/reflection

We would welcome a formal proposal and reference implementation something like a constexpr std::type_info.  I studied it and concluded that "upgrading" std::type_info without breaking changes would be a hassle, so the latest idea was to have a TextTrait (see N4113) called std::type_name<T>.  To streamline N4113 I removed std::type_name<T>, so if you want to take a run at it you would be welcome.

The problem is that type_info is (potentially) polymorphic, right? How much resistance is there to fixing that problem at the source, and allowing polymorphic literal types?

[Andrew Tomazos]

I can't remember what the problem was now to be honest, I would need to take another look at it.  I think it also had something to do with comparing unrelated pointers.

As for adding polymorphic literal types, it doesn't seem that insane - but judging by how conservative EWG is, there would have to be a pretty thorough paper with an implementation to get any traction.

[Daniel Krügler]

2014-07-10 6:17 GMT+02:00 David Krauss <pot...@gmail.com>:
> The problem is that type_info is (potentially) polymorphic, right?

Right.

> How much
> resistance is there to fixing that problem at the source, and allowing
> polymorphic literal types?

The other alternative is to change type_info not to be polymorphic.
There exists a corresponding library issue for this,

http://cplusplus.github.io/LWG/lwg-active.html#2398

- Daniel

[Richard Smith]

On Wed, Jul 9, 2014 at 8:26 PM, Myriachan <myri...@gmail.com> wrote:

I think that it would be nice if typeid(T) for type T and typeid(X) for compile-time constant expression X would return something considered to be a compile-time constant expression itself,

In the interest of precision: this is already the case, unless X is a glvalue of polymorphic class type. (The 'unless' clause here is unnecessary, but EWG were unconvinced by my suggestion that it be removed.)

Then, have the name(), before(), ==() and !=() member functions be constexpr as well.

We can't do this for before() without breaking ABIs, because before() orders by address of the type name in some implementations, and that's not a compile time constant.

name(), ==(), and !=() present technical problems too, because implementations use bit-fiddling tricks here that can't be directly modeled in constexpr evaluation, but we can at least in principle support those through compiler extensions.

This would allow the compile-time acquisition of type names as strings without using macros.

hashcode() is possible to be a constexpr as well, but there are a few reasons to not allow this; prevention of denial-of-service attacks is one reason that hashcode() may return different values each run of a program, and making it a constexpr would break that.

hashcode() suffers the same problem as before(); in some implementations, it just returns a pointer to the type name, cast to an integer type.

[Myriachan]

On Thursday, July 10, 2014 2:18:42 PM UTC-7, Richard Smith wrote:

On Wed, Jul 9, 2014 at 8:26 PM, Myriachan <myri...@gmail.com> wrote:

Then, have the name(), before(), ==() and !=() member functions be constexpr as well.

We can't do this for before() without breaking ABIs, because before() orders by address of the type name in some implementations, and that's not a compile time constant.

name(), ==(), and !=() present technical problems too, because implementations use bit-fiddling tricks here that can't be directly modeled in constexpr evaluation, but we can at least in principle support those through compiler extensions.

name, operator == and operator != in principle all could be implemented if it were possible to overload on whether the functions were called in a constexpr context (__builtin_constant_p?) even if the runtime implementation were significantly more complicated.  operator ==() and operator !=() are just std::is_same, and name() could be implemented several different ways.

This would allow the compile-time acquisition of type names as strings without using macros.

hashcode() is possible to be a constexpr as well, but there are a few reasons to not allow this; prevention of denial-of-service attacks is one reason that hashcode() may return different values each run of a program, and making it a constexpr would break that.

hashcode() suffers the same problem as before(); in some implementations, it just returns a pointer to the type name, cast to an integer type.

I agree that hashcode() and before() are significantly harder; they're also significantly less important to have available in constexpr-context.

Melissa

[Andrew Tomazos]

On Sun, Jul 13, 2014 at 4:28 AM, Myriachan <myri...@gmail.com> wrote:

This would allow the compile-time acquisition of type names as strings without using macros.

hashcode() is possible to be a constexpr as well, but there are a few reasons to not allow this; prevention of denial-of-service attacks is one reason that hashcode() may return different values each run of a program, and making it a constexpr would break that.

hashcode() suffers the same problem as before(); in some implementations, it just returns a pointer to the type name, cast to an integer type.

I agree that hashcode() and before() are significantly harder; they're also significantly less important to have available in constexpr-context.

Ahhh, no.  The utility of before and hashcode is the same at compile-time as at run-time.  For example if you want to have a compile-time data structure keyed by type (sorted array, binary tree, hash table, etc).  If you only have equality then you have to linear search for a type in a type list.  Also consider the case where you want to prepare one of the above data structures at compile-time for use at run-time.  You need access to (the same) before/hash functions in order to lay it out.

[David Krauss]

On 2014–07–11, at 5:18 AM, Richard Smith <ric...@metafoo.co.uk> wrote:

name(), ==(), and !=() present technical problems too, because implementations use bit-fiddling tricks here that can't be directly modeled in constexpr evaluation, but we can at least in principle support those through compiler extensions.

Let those be implemented as intrinsics, discriminating runtime from compile time. For implementations that guarantee uniqueness of type_info objects, comparing pointer identity is already constexpr safe. (I have deja vu on this suggestion.)

GCC accepts this but Clang complains "not an integral constant expression." Why?

static_assert ( & typeid( int ) == & typeid( int ), "" );

It is unfortunate, but the root problem is unfixable, so we might as well work within the set limits.

Right now, hash_code is not required to be unique per type (N3936 §18.7.1/8 only says “should”). Normatively we have the freedom to require an imperfect hash function at compile time (carried over to runtime), but this is a non-starter because programs already depend on the common implementations providing uniqueness.

Perhaps a truly imperfect hash should be added by a new interface. ABIs and individual metaprograms can sort out the gory usage details, but it’s no worse than things have always been, in terms of standardization. The spec of hash_code might be adjusted to require a perfect hash, or maybe not, if any remaining current ABIs don’t use the pointer trick. Either way, uniqueness should be an implementation-specified property since it’s so common.

[Andrew Tomazos]

This sounds like it's reaching the same conclusion I came to.  Create a new, completely separate system from std::type_info, for compile-time type name, equality, comparison and hash.

Further, if we could have a std::type_name<T> compile-time string such that std::type_name<A> == std::type_name<B> iff std::is_same<A,B> - these equality, comparison and hash functions could be simply the usual ones for strings.  I think the sticking point here was encoding a unique ID within the string to identify the translation unit, for types that didn't have external linkage.  For example:

TU1:

    struct {} a1;

    char* s1 = std::type_name_v<decltype(a1);

TU2:

    struct {} a2;

    char* s2 = std::type_name_v<decltype(a2)>;

TU3:

    extern char *s1, *s2;

    int main()
    {
        assert(strcmp(s1, s2) != 0);
    }

s1 and s2 must be different strings.  How shall they be formed?  If they were from the same TU we could just use a counter.  We need a way to encode the source TU identity at compile-time.  I thought of secure hashing the TU, or similarly generating a random TU ID of sufficient size at compile-time - but I haven't had much time to think about this further.

[David Krauss]

On 2014–07–13, at 1:16 PM, Andrew Tomazos <andrew...@gmail.com> wrote:

This sounds like it's reaching the same conclusion I came to.  Create a new, completely separate system from std::type_info, for compile-time type name, equality, comparison and hash.

Since type_info is already polymorphic, and assuming no technical barrier to literal polymorphic types,

1. Why not put new features in struct new_type_info< T > : type_info? 

2. Why not require is_same< decltype( typeid( T ) ), new_type_info< T > >? This should be mostly compatible with existing polymorphic type_info extensions, it just adds another layer under whatever the vendor has.

3. Since decltype( typeid( T ) ) is already suitable for nested-name-specifiers, there’s no need for a “new_type_info” name in the library at all.

Unless there’s a reason to jettison type_info, it seems perfect for extension.

Although, now that I think about it, #2 creates a rabbit-hole like

    std::type_info const * ti = & typeid( std::type_info );

    for (;;) ti = & typeid( * ti ); // Each iteration reveals a unique object of a unique type.

Perhaps all typeid( decltype( typeid( T ) ) ) should be represented by a common type. Doesn’t seem so bad.

Further, if we could have a std::type_name<T> compile-time string such that std::type_name<A> == std::type_name<B> iff std::is_same<A,B> - these equality, comparison and hash functions could be simply the usual ones for strings.  I think the sticking point here was encoding a unique ID within the string to identify the translation unit, for types that didn't have external linkage. 

Huh, I didn’t realize that typeid(T).name() wasn’t unique, but it’s not. But, mangled name uniqueness sounds more like an ABI quality issue.

Where is the advantage over & typeid(T) for identity (which I think is already constexpr-safe since C++11, I need to check the Clang bugtracker) and a constexpr array-backed typeid(T).name() for debugging?

s1 and s2 must be different strings.  How shall they be formed?  If they were from the same TU we could just use a counter. 

You mean a numeric string like "542"? How is that better than serializing a pointer? (They won’t be stable across builds.) Can you clarify the use case?

[Richard Smith]

On Sat, Jul 12, 2014 at 9:38 PM, David Krauss <pot...@gmail.com> wrote:

On 2014–07–11, at 5:18 AM, Richard Smith <ric...@metafoo.co.uk> wrote:

name(), ==(), and !=() present technical problems too, because implementations use bit-fiddling tricks here that can't be directly modeled in constexpr evaluation, but we can at least in principle support those through compiler extensions.

Let those be implemented as intrinsics, discriminating runtime from compile time. For implementations that guarantee uniqueness of type_info objects, comparing pointer identity is already constexpr safe. (I have deja vu on this suggestion.)

GCC accepts this but Clang complains "not an integral constant expression." Why?

static_assert ( & typeid( int ) == & typeid( int ), "" );

It is unspecified whether those two typeid expressions produce glvalues referring to the same object. Therefore this is "a relational or equality operator where the result is unspecified", so it's non-constant per 5.19/2 bullet 19.

Clang is not deliberately giving this result; I didn't think of this case when implementing support for typeid expressions in constexpr evaluation. Indeed, Clang gives the opposite result for this:

constexpr const std::type_info &x() { return typeid(int); } 

static_assert(&x() == &x(), "");

... which is arguably ill-formed for the same reason. I suspect (but don't know for sure) that GCC accepts this code because they too didn't think of this case (and in their implementation the representation for both address-of-typeid expressions happens to be the same, so the comparison succeeds).

Having said all that, I'm definitely sympathetic to making your static_assert work -- I'd suggest that within a single translation unit, all non-dynamic typeid expressions whose arguments refer to the same type should be defined to produce the glvalues referring to the same type_info object.

On 2014–07–13, at 10:49 AM, Andrew Tomazos <andrew...@gmail.com> wrote:

On Sun, Jul 13, 2014 at 4:28 AM, Myriachan <myri...@gmail.com> wrote:

I agree that hashcode() and before() are significantly harder; they're also significantly less important to have available in constexpr-context.

Ahhh, no.  The utility of before and hashcode is the same at compile-time as at run-time.  For example if you want to have a compile-time data structure keyed by type (sorted array, binary tree, hash table, etc).  If you only have equality then you have to linear search for a type in a type list.  Also consider the case where you want to prepare one of the above data structures at compile-time for use at run-time.  You need access to (the same) before/hash functions in order to lay it out.

It is unfortunate, but the root problem is unfixable, so we might as well work within the set limits.

Right now, hash_code is not required to be unique per type (N3936 §18.7.1/8 only says “should”). Normatively we have the freedom to require an imperfect hash function at compile time (carried over to runtime), but this is a non-starter because programs already depend on the common implementations providing uniqueness.

Perhaps a truly imperfect hash should be added by a new interface. ABIs and individual metaprograms can sort out the gory usage details, but it’s no worse than things have always been, in terms of standardization. The spec of hash_code might be adjusted to require a perfect hash, or maybe not, if any remaining current ABIs don’t use the pointer trick. Either way, uniqueness should be an implementation-specified property since it’s so common.

[Ville Voutilainen]

On 14 July 2014 23:59, Richard Smith <ric...@metafoo.co.uk> wrote:
> Having said all that, I'm definitely sympathetic to making your
> static_assert work -- I'd suggest that within a single translation unit, all
> non-dynamic typeid expressions whose arguments refer to the same type should
> be defined to produce the glvalues referring to the same type_info object.

A short proposal targeting EWG and authored by Mr. Smith would be nice. ;)

[David Krauss]

On 2014–07–15, at 4:59 AM, Richard Smith <ric...@metafoo.co.uk> wrote:

Indeed, Clang gives the opposite result for this:

constexpr const std::type_info &x() { return typeid(int); } 

static_assert(&x() == &x(), "");

... which is arguably ill-formed for the same reason. I suspect (but don't know for sure) that GCC accepts this code because they too didn't think of this case (and in their implementation the representation for both address-of-typeid expressions happens to be the same, so the comparison succeeds).

Having said all that, I'm definitely sympathetic to making your static_assert work -- I'd suggest that within a single translation unit, all non-dynamic typeid expressions whose arguments refer to the same type should be defined to produce the glvalues referring to the same type_info object.

This (and your above example) cannot be reconciled with the ODR. It requires ODR-compliant inline functions definitions in different TUs to produce different behavior. (Please forward this to CWG per the Clang bug report comment.)

Apparently my mind wandered between subsequent sentences, because right before I gave my example, I’d mentioned “implementations that guarantee uniqueness of type_info objects.” Looks like I underestimated the nasal demons, by assuming that runtime identity of type_info objects (which I’m currently assuming, without verification, are a property of the common ABI or at least Clang) is sufficient to guarantee compile-time identity.

The real solution is what I mentioned next: split the compile-tme and runtime uniqueness guarantees between two separate interfaces, essentially adding a new type_info::static_hash_code(). But, using &typeid() as a model, pointers are better than hashes because their identity can be tested at compile time, but no other observations exist like numeric conversions. They are also inferior in that before() is sacrificed.

Extrapolating back to my suggestions, now I suggest two new interfaces, with ABI-specified details:

— constexpr void * type_info::unique_key() const which may be implemented as returning a pointer to a dummy function/object of vague linkage (an inline function or variable template instantiation, casted to void*), or just this on systems that prevent duplicate type_info instances.

— constexpr uintptr_t type_info::static_hash() const which may be implemented as a compile-time string hash, perhaps adding an appropriately stable TU identifier into the mix. To the user, this is constexpr-friendly but inferior to hash_id.

Things that would be nice to resolve, or else definitively prove impossible:

— constexpr full ordering of types must depend on a hash function which potentially has collisions.

— void * unique_key(), being not a number, cannot be used for a hash table or a search algorithm faster than O(N). The user is stuck with linear search, which is only acceptable at compile time. Perhaps this can be resolved by somehow hooking an intrinsic into std::type_index.

[Richard Smith]

On Mon, Jul 14, 2014 at 8:13 PM, David Krauss <pot...@gmail.com> wrote:

On 2014–07–15, at 4:59 AM, Richard Smith <ric...@metafoo.co.uk> wrote:

Indeed, Clang gives the opposite result for this:

constexpr const std::type_info &x() { return typeid(int); } 

static_assert(&x() == &x(), "");

... which is arguably ill-formed for the same reason. I suspect (but don't know for sure) that GCC accepts this code because they too didn't think of this case (and in their implementation the representation for both address-of-typeid expressions happens to be the same, so the comparison succeeds).

Having said all that, I'm definitely sympathetic to making your static_assert work -- I'd suggest that within a single translation unit, all non-dynamic typeid expressions whose arguments refer to the same type should be defined to produce the glvalues referring to the same type_info object.

This (and your above example) cannot be reconciled with the ODR. It requires ODR-compliant inline functions definitions in different TUs to produce different behavior. (Please forward this to CWG per the Clang bug report comment.)

My mail to core already had a discussion of this problem in it =)

Apparently my mind wandered between subsequent sentences, because right before I gave my example, I’d mentioned “implementations that guarantee uniqueness of type_info objects.” Looks like I underestimated the nasal demons, by assuming that runtime identity of type_info objects (which I’m currently assuming, without verification, are a property of the common ABI or at least Clang) is sufficient to guarantee compile-time identity.

The real solution is what I mentioned next: split the compile-tme and runtime uniqueness guarantees between two separate interfaces, essentially adding a new type_info::static_hash_code(). But, using &typeid() as a model, pointers are better than hashes because their identity can be tested at compile time, but no other observations exist like numeric conversions. They are also inferior in that before() is sacrificed.

Extrapolating back to my suggestions, now I suggest two new interfaces, with ABI-specified details:

— constexpr void * type_info::unique_key() const which may be implemented as returning a pointer to a dummy function/object of vague linkage (an inline function or variable template instantiation, casted to void*), or just this on systems that prevent duplicate type_info instances.

— constexpr uintptr_t type_info::static_hash() const which may be implemented as a compile-time string hash, perhaps adding an appropriately stable TU identifier into the mix. To the user, this is constexpr-friendly but inferior to hash_id.

Things that would be nice to resolve, or else definitively prove impossible:

— constexpr full ordering of types must depend on a hash function which potentially has collisions.

— void * unique_key(), being not a number, cannot be used for a hash table or a search algorithm faster than O(N). The user is stuck with linear search, which is only acceptable at compile time. Perhaps this can be resolved by somehow hooking an intrinsic into std::type_index.

I think the utility of these will be somewhat limited since we don't have the ability to allocate memory during constexpr evaluation (but a fixed-size hash table is probably good enough for a lot of use cases).

[David Krauss]

On 2014–07–15, at 11:37 AM, Richard Smith <ric...@metafoo.co.uk> wrote:

On Mon, Jul 14, 2014 at 8:13 PM, David Krauss <pot...@gmail.com> wrote:

— constexpr void * type_info::unique_key() const which may be implemented as returning a pointer to a dummy function/object of vague linkage (an inline function or variable template instantiation, casted to void*), or just this on systems that prevent duplicate type_info instances.

— constexpr uintptr_t type_info::static_hash() const which may be implemented as a compile-time string hash, perhaps adding an appropriately stable TU identifier into the mix. To the user, this is constexpr-friendly but inferior to hash_id.

I think the utility of these will be somewhat limited since we don't have the ability to allocate memory during constexpr evaluation (but a fixed-size hash table is probably good enough for a lot of use cases).

I’ve not played much with it, but I would expect the constexpr code to calculate the size of an array and initialize that, or just generate a braced-init-list and use that for std::initializer_list. The linear or O(log N) search would be based on indexes.

One of the first things I tried with C++11 constexpr is a binary search, over linked global objects as opposed to a single container object. It continues to serve well in my project, although I don’t know if I’d call the experiment a success, the same general pattern is still viable in C++14 and higher.

[Andrew Tomazos]

On Tue, Jul 15, 2014 at 5:37 AM, Richard Smith <ric...@metafoo.co.uk> wrote:

I think the utility of these will be somewhat limited since we don't have the ability to allocate memory during constexpr evaluation (but a fixed-size hash table is probably good enough for a lot of use cases).

The use of the term "fixed-size" here is misleading.  You can calculate during compile-time the required size of a compile-time data structure based on the data it will hold (or whatever other factors), and then "allocate" that amount of memory for the data structure by passing in the calculated size(s) as template parameter(s).

After writing my `has_member_function` paper that happens to use this technique, I have had a lot of interest from people in the paper because of the technique itself (and unrelated to reflection).

I think C++14 compile-time data structures (enabled by the constexpr function relaxations) are going to be heavily used, because it is so much easier/better than the old Boost MPL style.  We should therefore endeavour to enable equality, comparison and hash for all standard library literal types, including this specific case of a literal wrapper type for types themselves.

(Having said that, the predynamic storage duration stuff is still welcome, but as I mention in the std::string_literal paper - I expect it will get a similar reaction from EWG to Classes of Runtime Size.)