non-constant constant-expressions, is it really possible?

[Filip Roséen]

Good evening [std-discussion],

I just finished an article/blog post that in detail explains a technique that adds "state" to constant-expressions;

• http://b.atch.se/posts/non-constant-constant-expressions/

Though, the question is whether there is any part of the standard (C++11) that renders the technique explained ill-formed, or to suffer from undefined-behavior?

Best Regards,

Filip Roséen

[Chris Hallock]

Does the last restriction in 14.6/8 put a stick through the spokes?

[...] If a hypothetical instantiation of a template immediately following its definition would be ill-formed due to a construct that does not depend on a template parameter, the program is ill-formed; no diagnostic is required. If the interpretation of such a construct in the hypothetical instantiation is different from the interpretation of the corresponding construct in any actual instantiation of the template, the program is ill-formed; no diagnostic is required. [...]

(This wording is not in C++14 but was added to the working draft by DR#1850.)

[David Krauss]

I haven’t read your article in depth, but it looks familiar. See this recent thread. Here is a partial defect report, which I haven’t yet submitted:

A friend function defined in a class template is treated as if it were defined at the point of instantiation of the specialization ([temp.inject] §14.6.5). The point of instantiation is retroactively before any non-template function declaration or definition which incurred the chain of instantiations leading to the friend, if the outermost instantiation was a function ([temp.point] 14.6.4.1; this distinction is arbitrary but significant in this context).

The existence of such a friend may be observed after the point of instantiation, but before the specialization has been mentioned within the function. This does not violate [temp.dep.candidate] 14.6.4.2 because there are not two valid specializations in two instantiation contexts, but only one correct interpretation which is impossible because the initial instantiation context depends on things at the point of instantiation which do not yet exist.

constexpr int get();

template< int value >

class set { // Instantiate this exactly once.

    friend constexpr int get() { return value; }

};

// Point of instantiation is here.

int main() {

    char a[ get() ]; // OK but impossible: get() was already defined at the POI.

    set< 5 > b;

    char c[ get() ]; // This is also well-defined, and it actually works.

}

[Filip Roséen]

Hmm, I don't think it applies - an instantiation of the template would never be ill-formed. 

As from the defect report; "Presumably a rule is needed to make it ill-formed, no diagnostic required, if the validity of such a reference changes between the two contexts.‎"

The template is valid no matter where it is instantiated, however.. it wouldn't be if we were to actually try and evaluate the constexpr function call `flag(0)` in the post (but that doesn't happen).

The section that follows your quote deals with evaluation of constant-expressions (among other things), and says that an evaluation of an undefined constant-expression would render the template ill-formed; the "problem" is that we never evaluate the function call (since it is an unevaluated operand to `noexcept`).

:: Filip Roséen (via BlackBerry)
:: +46701448424 
:: filip....@gmail.com

--

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

[Richard Smith]

I know of no language rule that this technique violates, but it does slip past one rule on a technicality (that a template specialization that has multiple points of instantiation behaves the same at all of them) -- because the default template arguments aren't part of the instantiated specialization itself.

If we wanted for this to not be OK, I think one natural way to get that effect would be to say that you can only use information from a friend defined inline in a class if that class was an associated class of the name lookup that found the friend -- that friends defined inline are "ADL-only" -- but that might break a lot of reasonable code.

Another natural way might be to say that *any* substitution (including template parameters, default arguments, etc) must give the same results at all points of substitution, not just template instantiations.

[David Krauss]

On 2015–04–27, at 9:28 AM, Richard Smith <ric...@metafoo.co.uk> wrote:

Another natural way might be to say that *any* substitution (including template parameters, default arguments, etc) must give the same results at all points of substitution, not just template instantiations.

I occasionally use default arguments to get different meanings from one template-id. It’s the only way to define the trait is_incomplete. (However, that’s a somewhat dangerous trait, and I don’t recall another use offhand, aside from working around some compiler bugs.)

Otherwise, the technique looks similar to the one I described, and it has the same point-of-instantiation weakness. This should be described in the article. Currently the point-of-instantiation rules are merely referenced, but there’s no discussion of what it means for usage of the library.

[Filip Roséen]

Hmm, I am not sure I agree with your wording related to the point of instantiation, because the explicit specialization is not there until we have actually seen the (implicit) instantiation happen; that's my take on the relevant sections of the Standard.

14.6.5p1 (n3337) says "when a template is instantiated", in my book this (and other sections) means that such state cannot leak out prior to the instantiation.

You can always point (with your finger) at an instantiations "point of instantiation", but the effects of such instantiation are not present until we have actually instantiated it.

This is addressed in the blog post as; "It is important to note that a point of instantation (1) denotes in what context the compiler may generate the relevant code. What triggers the instantiation is where the change actually takes effect ((2) and (3))."

Sorry for the potentially weird formatting; I'm currently on my phone!

:: Filip Roséen (via BlackBerry)
:: +46701448424 
:: filip....@gmail.com

From: David Krauss Sent: Monday, April 27, 2015 3:44 AM To: std-dis...@isocpp.org Reply To: std-dis...@isocpp.org

--

[David Krauss]

On 2015–04–27, at 12:28 PM, Filip Roséen <filip....@gmail.com> wrote:

Hmm, I am not sure I agree with your wording related to the point of instantiation,

What wording? Please quote.

because the explicit specialization is not there until we have actually seen the (implicit) instantiation happen; that's my take on the relevant sections of the Standard.

The problem is that the standard doesn’t describe an order for the instantiations to happen. Our examples rely on the idea that specializations used in prior statements will be instantiated before (or in an enclosing declarative scope to) ones in subsequent statements. But it would be just as conforming to process the function from the end to the beginning, or randomly.

14.6.5p1 (n3337) says "when a template is instantiated", in my book this (and other sections) means that such state cannot leak out prior to the instantiation.

I disagree. Besides instantiations not having a well-defined order, there’s no sense temporality at all. The intent is that templates are mathematically pure and you can’t observe whether a template has yet been instantiated or not. Name lookup happens from a place or context in the program text, not a point in time, because there is no such thing as time.

I would like to propose a guaranteed beginning-to-end order of statements and to introduce finer scoping so that our tricks will work. But it’s a tricky situation, and perhaps doomed to fail. See also CWG DR 993:

The intent is that it is a permissible implementation technique to do template instantiation at the end of a translation unit rather than at an actual point of instantiation. This idea is not reflected in the current rules, however.

(Note, this defect was accepted and resolved for C++11. The solution was to add additional points of instantiation, which I mention below.)

In other words, the intent of the committee thus far is that the compiler can plow through your entire function definition, and up to the end of the TU, without ever instantiating a friend.

This is addressed in the blog post as; "It is important to note that a point of instantation (1) denotes in what context the compiler may generate the relevant code. What triggers the instantiation is where the change actually takes effect ((2) and (3)).”

Yes, but you’re skipping some major issues.

1. Your utility won’t work from inside a template. It must always be used from a non-template context, because a second instantiation of the same template would see the friends generated by the first instantiation. Every specialization that is used at all has at least two points of instantiation, including one at the end of the TU. (In practice, though, you will probably get consistent behavior for templates with only exactly two PoI’s.)

My utility specifically avoids this, by the way, because it only implements a map, and you’re not allowed to observe the absence of an entry in the map. Functions can progressively generate compile-time state, but not change it, and a query for non-existent state produces a failure.

2. Points of instantiation are defined for each specific kind of entity: after the enclosing namespace-scope declaration for “a function template specialization, a member function template specialization, or a specialization for a member function or static data member of a class template” and before for “a class template specialization, a class member template specialization, or a specialization for a class member of a class template.”

Your utility requires the point instantiation of the friend function to be before the point of use. Otherwise, it wouldn’t be in scope. However, there is no point of instantiation defined for friends at all. You’re relying on friends being treated like classes, not like other functions, which seems especially brittle.

My utility avoids this by only relying on the declaration of the friend function: it’s never defined (instantiated) at all. The friend declaration, sans body, can more reasonably be regarded as part of the class.

[Filip Roséen]

> 1. Your utility won’t work from inside a template. It must always be used from a non-template context, because a second instantiation of the same template would see the friends generated by the first instantiation. Every specialization that is used at all has at least two points of instantiation, including one at the end of the TU. (In practice, though, you will probably get consistent behavior for templates with only exactly two PoI’s.)

Unless they rely on different friends, so the above is not really an issue, also; class template specializations has at most one point of instantiation - not two, that only applies to function templates.

> The problem is that the standard doesn’t describe an order for the instantiations to happen.

Unless we are talking dependency, where it must happen in some order - this does not only include literally dependent types. The example in the current post is not sufficient enough to explain this in detail, but an explanation will be included in upcoming posts (there are more neat little tricks to be published).

> Your utility requires the point instantiation of the friend function to be before the point of use. Otherwise, it wouldn’t be in scope. However, there is no point of instantiation defined for friends at all. You’re relying on friends being treated like classes, not like other functions, which seems especially brittle.

This is not entirely true, it requires the point of instantiation of the class-template specialization to be where it needs to be; please note that default template-arguments are not part of the specialization itself, that means that `sizeof(...)` used as a default-argument to the template function effectively puts the instantiation of the relevant class prior to `main` (not prior to the instantiation of the function template specialization). The post "abuses" the instantiation of class template specializations, not function template specializations.

By the way, a variation of your method is what makes some other stuff possible to implement - it is not directly equivalent, but it is somewhat similar. I will however explain this in detail in upcoming posts.

--

[David Krauss]

On 2015–04–27, at 1:53 PM, Filip Roséen <filip....@gmail.com> wrote:

> 1. Your utility won’t work from inside a template. It must always be used from a non-template context, because a second instantiation of the same template would see the friends generated by the first instantiation. Every specialization that is used at all has at least two points of instantiation, including one at the end of the TU. (In practice, though, you will probably get consistent behavior for templates with only exactly two PoI’s.)

Unless they rely on different friends, so the above is not really an issue,

You mean the two instantiations of the same specialization would access different friends? That’s ill-formed, NDR.

also; class template specializations has at most one point of instantiation - not two, that only applies to function templates.

Your utility is only intended for use within functions, so those are what’s relevant.

> The problem is that the standard doesn’t describe an order for the instantiations to happen.

Unless we are talking dependency, where it must happen in some order - this does not only include literally dependent types. The example in the current post is not sufficient enough to explain this in detail, but an explanation will be included in upcoming posts (there are more neat little tricks to be published).

There is no dependency between the statements in your post, and that seems to be the whole purpose: to let compile-time information flow from one statement to the next without using the type system.

It would be more responsible to provide a disclaimer in your article if you believe its examples to be nonconforming, especially if an edit is in the works.

> Your utility requires the point instantiation of the friend function to be before the point of use. Otherwise, it wouldn’t be in scope. However, there is no point of instantiation defined for friends at all. You’re relying on friends being treated like classes, not like other functions, which seems especially brittle.

This is not entirely true, it requires the point of instantiation of the class-template specialization to be where it needs to be;

Calling the constexpr function requires its definition to precede the use. You’re assuming that the functions are defined by the class template instantiation: “Please note that the functions func (short) and func (float) are undefined until A<short> and A<float> have been instantiated, respectively.” This is not a safe assumption, because the point of instantiation may render the definition invisible to the current function.

please note that default template-arguments are not part of the specialization itself, that means that `sizeof(...)` used as a default-argument to the template function effectively puts the instantiation of the relevant class prior to `main` (not prior to the instantiation of the function template specialization). The post "abuses" the instantiation of class template specializations, not function template specializations.

I’m not sure what you mean by “prior to the instantiation of the function template specialization.” Points of instantiation are before or after non-template declarations at namespace scope. Classes come before, functions come after. Friends are unspecified, but they are functions, so we can extrapolate.

Actually, constexpr function templates can’t usually form constant expressions at all according to the current rules. This needs a DR.

[Richard Smith]

FYI, this should be covered by core issue 1581 -- we're essentially planning to require that constexpr function template specializations are instantiated "at" the first point of reference (presumably with a single PoI before the current declaration, like a class template specialization). And likewise for function templates with a deduced return type.

[Filip Roséen]

‎> You mean the two instantiations of the same specialization would access different friends? That’s ill-formed, NDR.

No, two different specializations of the same template (of course).

> Your utility is only intended for use within functions, so those are what’s relevant.

I think you are focusing on the wrong part; the instantiation order of the functions has nothing to do with the template default-arguments (which effectively instantiates the class template).. the template default-arguments are what is important.

In reply to the rest: the code is confirming, no edit is pending, there are cases where the order of function template instantiation matters - but the example provided is not one of them.

It is important to note that constexpr functions follow the same rules of normal functions, and just to make this even more clear one could also have expressed the method in the post by "abusing" default-arguments (non-template, regular arguments) since these expressions are said to be evaluated each time the function is invoked.

The use of a template instead of a non-template is simply because the upcoming examples will be working with a similar concept (since that is shorter, but regular function default-arguments can accomplish the same thing).

:: Filip Roséen (via BlackBerry)
:: +46701448424 
:: filip....@gmail.com

From: David Krauss Sent: Monday, April 27, 2015 8:35 AM To: std-dis...@isocpp.org Reply To: std-dis...@isocpp.org Subject: Re: [std-discussion] non-constant constant-expressions, is it really possible?

--

[David Krauss]

On 2015–04–27, at 2:57 PM, Filip Roséen <filip....@gmail.com> wrote:

‎No, two different specializations of the same template (of course).

My point is that the way you change state, by adding namespace-scope declarations, persists after the function definition. A second instantiation of the same function template specialization, as is always done automatically, will observe the changed state in a context where the first instantiation observed unchanged state. That’s ill-formed.

By the way, I have implemented a compile-time counter (http://stackoverflow.com/a/6174263/153285 ) which does support counting inside functions, with a little elbow grease (http://coliru.stacked-crooked.com/a/f9840581681e3155 ). It’s safe for templates because the changes get reverted when you exit the local scope, which also renders the feature somewhat useless. Hence there’s no mention on the StackOverflow page. (Only the C++98 version has this capability.)

I think you are focusing on the wrong part; the instantiation order of the functions has nothing to do with the template default-arguments (which effectively instantiates the class template).. the template default-arguments are what is important.

I’m not talking about any components of your system, but its effect on a function template which might use it. The point is that it can only be used within non-template functions. You should note this in your article because it’s a major restriction.

In reply to the rest: the code is confirming, no edit is pending, there are cases where the order of function template instantiation matters - but the example provided is not one of them.

If you’re so confident, why ask for review in the first place?

Where in the standard does it say the compiler can’t process your function back-to-front and implement the compile-time state progress in reverse order, so in line 1 the function is defined and in line 2 it’s undefined? Both lines are in the same scope.

It is important to note that constexpr functions follow the same rules of normal functions,

As Richard just noted, you are depending on a proposed rule which is specific to constexpr function templates.

and just to make this even more clear one could also have expressed the method in the post by "abusing" default-arguments (non-template, regular arguments) since these expressions are said to be evaluated each time the function is invoked.

A default argument of a function template is a template in and of itself, equivalent to a function template, with a well-defined point of instantiation ([temp.inst] §14.7.1/13, [temp.point] §14.6.4.1/2). Default arguments need to produce consistent values wherever functions must.

The rules of default template argument evaluation are unspecified, as far as I know. It is merely common practice to evaluate them at each point of use, allowing different values at different uses. I hazily recall planning to file a DR long ago, but getting scared away because there’s a fair chance that the consensus will be more conservative: that different values shouldn’t be allowed. The simplest extrapolation from ordinary default arguments would suggest that default template arguments should be equivalent to constexpr function templates.

A default argument of an ordinary function, which seems to be what you’re getting at, can’t do anything interesting because it has no point of instantiation to make ADL aware of the context where it’s used. It gets compiled once and for all when it’s encountered in the function declarator.

The use of a template instead of a non-template is simply because the upcoming examples will be working with a similar concept (since that is shorter, but regular function default-arguments can accomplish the same thing).

You are in implementation-specific territory.

[Filip Roséen]

No, the "second" instantiation will use the template-parameters that are decided when the default-arguments are evaluated (this means that the "two" instantiations are the same, nothing ill-formed), ie. When the specialization is referenced.

The important part is that the template-parameters are decided when the implicit instantiation takes place, the default-arguments will only be evaluated once (at that time) (and such the meaning of the specialization remains the same no matter where the compiler generates the code for it)!

I hope the above explains what I mean, I'm currently on the subway and I get distracted quite easily.


I've also implemented a compile-time counter, and jftr everything the post (that this thread is about) talks about has already been implemented (and compiles with gcc, clang, msvc, and "somewhat" in ICC (because of the lack of proper support for constexpr in ICC).

Your implementation is very clever, and I'll be sure to let you know when the post including my compile-time counter (and container) has been posted.

I also want to thank you for taking time with posting on this very interesting topic!

/F

:: Filip Roséen (via BlackBerry)
:: +46701448424 
:: filip....@gmail.com

From: David Krauss Sent: Monday, April 27, 2015 10:29 AM To: std-dis...@isocpp.org Reply To: std-dis...@isocpp.org Subject: Re: [std-discussion] non-constant constant-expressions, is it really possible?

--

[David Krauss]

On 2015–04–27, at 4:44 PM, Filip Roséen <filip....@gmail.com> wrote:

No, the "second" instantiation will use the template-parameters that

Again, I’m not talking about the template f() or any other part of your utility. I’m talking about any function template which *uses* your utility.

The problem is absent from your examples, but you should still mention that your utility can’t be used within a (function) template.

I hope the above explains what I mean, I'm currently on the subway and I get distracted quite easily.

I understand your program perfectly well. I’ve used all these tricks before, except for using noexcept to detect constant expressions. I’m also familiar with the frustration inherent in this area, the excitement and the disappointment. If you have a lot of StackOverflow reputation, you can even see a friend-based compile-time counter that I posted before arriving at the final answer linked earlier: http://stackoverflow.com/a/6166338/153285 . (I was fortunate to have Johannes Schaub reviewing my work — we were competing to see who could solve the problem first.)

I've also implemented a compile-time counter, and jftr everything the post (that this thread is about) talks about has already been implemented (and compiles with gcc, clang, msvc, and "somewhat" in ICC (because of the lack of proper support for constexpr in ICC).

Unfortunately, implementations are only weakly correlated with the theoretical ideal of the language. There are permissible things that no current implementation does, for example, concurrent processing of statements in a function. There are requirements that aren’t universally implemented, for example evaluating the unevaluated context of noexcept as a constant expression.

I hope you will stop to consider how much of the observed behavior is guaranteed by the standard.

[Filip Roséen]

On Mon, Apr 27, 2015 at 12:00 PM, David Krauss <pot...@gmail.com> wrote:

On 2015–04–27, at 4:44 PM, Filip Roséen <filip....@gmail.com> wrote:

No, the "second" instantiation will use the template-parameters that

Again, I’m not talking about the template f() or any other part of your utility. I’m talking about any function template which *uses* your utility.

The problem is absent from your examples, but you should still mention that your utility can’t be used within a (function) template.

No worries, this will be mentioned in future posts because one needs to know about those things in order to understand what doesn't, and more importantly what does, work.

Maybe I misunderstood your intention, I thought you were talking about the contents of the post specifically (not circumstances under which it might not yield behavior which was never intended), you got a point - one has to be very careful when dealing with these things.

 

I hope the above explains what I mean, I'm currently on the subway and I get distracted quite easily.

I understand your program perfectly well. I’ve used all these tricks before, except for using noexcept to detect constant expressions. I’m also familiar with the frustration inherent in this area, the excitement and the disappointment. If you have a lot of StackOverflow reputation, you can even see a friend-based compile-time counter that I posted before arriving at the final answer linked earlier: http://stackoverflow.com/a/6166338/153285 . (I was fortunate to have Johannes Schaub reviewing my work — we were competing to see who could solve the problem first.)

I've spent fair share of time discussing things with litb (back when ##c++  @ freenode was.. different), and I do have "enough" reputation to look at your post - no worries (and thanks for linking)!

 

I've also implemented a compile-time counter, and jftr everything the post (that this thread is about) talks about has already been implemented (and compiles with gcc, clang, msvc, and "somewhat" in ICC (because of the lack of proper support for constexpr in ICC).

Unfortunately, implementations are only weakly correlated with the theoretical ideal of the language. There are permissible things that no current implementation does, for example, concurrent processing of statements in a function. There are requirements that aren’t universally implemented, for example evaluating the unevaluated context of noexcept as a constant expression.

I hope you will stop to consider how much of the observed behavior is guaranteed by the standard.

The only thing I've done in my spare time during this last week is trying to make sure that I only rely on things guaranteed by the standard, and I'm being very careful not to make any false assumptions - and threads like this certainly help me with that; so once again, thank you!

[Filip Roséen]

I now realize that my phone must have truncated some (or all) of the messages I replied to in this thread, because when rereading it there are a bunch of stuff which I didn't know got posted - and that is why I didn't address them in previous messages; I deeply apologize for that. I'm currently working on the upcoming post, which will include contents that address some (if not all) of the points mentioned in this thread, once again; thanks for keeping me on my feet!

Peace,

To unsubscribe from this group and stop receiving emails from it, send an email to std-discussion+unsubscribe@isocpp.org.

[David Krauss]

Bad news from the Lenexa CWG minutes:

•  Core issue 2118 Stateful metaprogramming via friend injection: We will make it ill-formed.

I might write a paper attempting to sway this position, but I don’t really think the mission is very hopeful. Also, I can’t guarantee that the use case I’d present would help with the one in this thread.

[Nicol Bolas]

On Friday, May 15, 2015 at 10:27:13 PM UTC-4, David Krauss wrote:

Bad news from the Lenexa CWG minutes:

Are those publicly available yet?

[David Krauss]

They’re on the Wiki.

I don’t really understand the permissions scheme there. Is the password supposed to be private or just a measure against spam?

Sorry if I divulged some secret :P .

[Ville Voutilainen]

On 16 May 2015 at 09:37, David Krauss <pot...@mac.com> wrote:
> I don’t really understand the permissions scheme there. Is the password
> supposed to be private or just a measure against spam?

It's not supposed to be distributed to the public at large.

[herb.sutter]

Right, the wiki password is not public (one might add, "by definition"). Also, we usually don't quote from the wiki notes because they are unofficial and not vetted for complete accuracy; they are the subgroup's scribes' best efforts to jot down the discussion as it happens.

The official progress on all issues is always made publicly available via the issues lists, which are posted shortly after the meeting. In this case, in a few days you'll see the updated post-Lenexa Core issues list, and you can check it for the actual state of Core 2118 (and other issues). This is the authoritative list to refer to.

Herb

 

[Filip Roséen]

If you would like to co-author such paper I would be happy to contribute, there are a few more quirks in the standard that allows one to reach the same "goal" without using friend-injection.

I'm currently working on the 3rd part of the series of articles on b.atch.se, the 4th one will address all "issues" that I know at the current time of writing, and proposed resolution if one really wants them all to be ill-formed. Given the fact that there is a lot of wording to be changed, and that it could potentially kill already widely used implementations of other (non-related) thingies, there might be a possibility to sway the current opinion of the CWG.

Thanks for the update, much appreciated!

Best Regards,
Filip Roséen

[David Krauss]

> On 2015–05–28, at 3:30 AM, Filip Roséen <filip....@gmail.com> wrote:
>
>
> If you would like to co-author such paper I would be happy to contribute, there are a few more quirks in the standard that allows one to reach the same "goal" without using friend-injection.

I’m thinking of elaborated-type-specifiers. Is there yet another one?

The committee justifiably tries to be conservative about what usage is valid. I have avoided bringing these techniques to their attention because it’s hard to put a positive spin. Likewise to the greater public.

We can collaborate on a paper :) . I’m not yet committed to writing anything. Relying on NDR is good enough for me, for now. I don’t think implementations are going to start detecting this anytime soon, whatever the committee decides. I’ve never released such code into the wild, and not likely to do so, although my use-case is quite practical, and necessary for the problem it solves.

[david.s...@gmail.com]

Did Core issue 2118 die?  It's still listed as open more than a year later and I can't find any updates to it.