C++Now 2017: Ben Deane & Jason Turner "constexpr ALL the things!"

[Ben Deane] I’m Ben, this is Jason. The genesis of this talk was: I was fishing around in January when the call for papers went out for C++Now and I didn’t have much idea and I messaged Jason and I said, “Do you want to do a collaboration?” And he said, “sure, what on?” I said, “I don’t know,” he said, “well I’ve got this title, it’s constexpr ALL the things!” I’m like, “that sounds great!” If you don’t know this meme, it’s from Allie Brosh’s excellent “Hyperbole and a Half” webcomic and book and we co-opted it This is Jason Turner. He doesn’t need much of an introduction, I’m sure, to many of you He is a trainer and contractor working out of Denver He is also the co-host, with Rob Irving, of CppCast and also the host of C++ Weekly, which just passed its year mark. And CppCast just passed its hundredth episode And somehow in between all that, he finds time to usually submit multiple talks to multiple conferences throughout the year [Jason Turner] Well, it helps when you don’t have a regular full-time job This is Ben Deane. He is a principal software engineer at Blizzard on the Battle.net team and Ben likes functional programming, and a lot of his talks have been casually related to functional programming in some way or another, he’s a regular speaker and attender at C++ conferences also [BD] That’s a polite way of saying I get all my ideas from Haskell In the interest of not burying the lead, we want to start out with the proof-of-concept. When I first heard about constexpr, and I heard about user defined literals I immediately thought: is this possible? Can we embed JSON literals in C++? Because JSON is ubiquitous. JSON’s kind of useful It’s not too difficult. It’s well understood – the grammar’s well understood It’s also sufficiently interesting because it’s fundamentally recursive, so there’s some interesting problems to solve. And to me this is kind of a bellwether for what’s possible with constexpr. If this is possible many many things are possible, and if this can be made easier many many things get easier, I think [JT] So the promise of constexpr – what we’re hoping to get out of this – is better runtime efficiency: if you’re calculating stuff at compile time, there’s less to do at runtime, pretty straightforward Clearer code, fewer magic numbers: this is an interesting thing that I think we’ll dig into for some of the options for what we mean by fewer magic numbers; and less cross-platform pain: so as Ben pointed out, we’re trying to lead towards this goal of being able to do a JSON parser at compile time and that eliminates the need to have an external tool that’s generating C++ code for us from our assets. [BD] And if you’re working in a cross-platform environment, deleting a step from your build chain is kind of a big win In putting together this talk, I thought, “How did we get here?” So a constexpr “History 101”: It struck me that there are three ages of constexpr. The first age was extreme recursion, we were only allowed one return expression per function in C++11 We started to see constexpr math functions, Scott Schurr gave a couple of great talks here and at CppCon and discovered things like the throw trick The trick there is, if you have a constexpr function you’re not always sure whether it’s being evaluated in [a constexpr context]. You might take the result of that and forget to put it in a constexpr context, so you might assign it to a non constexpr variable, and then the compiler would emit your function when you didn’t mean it to And so the throw trick was discovered, which is that you declare a symbol but you don’t define it, and then you put a line of code in the constexpr function which doesn’t get evaluated normally when you call it constexpr-wise. So think of, like, a square root function and if you pass it a negative number obviously, it’s undefined so you would throw, but you would throw an undefined symbol. And you effectively turn what would be accidental emission of the function into a link error So we saw things like this in the first age, and that was cool, and the ages seem to be, to me, characterized by what kind of string hashing you can do. So the mainstream discovered constexpr string hashing, and I’m sorry my comments are really really lost here,

but basically in the first age we had the fall of Gondolin, some balrogs destroyed, Morgoth defeated, and then constexpr string hashing discovered So at this point most people are probably familiar with this or something like it This kind of thing has been widely brought into the constexpr mainstream consciousness In the second age, we saw things like generalized constexpr being supported by Visual Studio. Which is cool A lot of more general compile time computation and optimization: things becoming const, things becoming constexpr; and that’s been popularized by things like C++ Weekly that Jason does. [JT] I did not put that line in the presentation just for the record And of course generalized constexpr string hashing, like Murmur3, has been discovered and constexpr libraries starting to appear I think So the end of the second age looks something like this Like I said, the Murmur hash. The mainstream consciousness seems to me to be following what string hashing is available. So I think now we’re at the dawn of the third age with C++17 and that means a lot of cool things. constexpr lambdas, which as we’ll see are very powerful We’ve got if constexpr, which is changing up how we do things like enable_if and template specializations And we’ve got at the moment an interesting selection of constexpr things in the STL Things are starting to be born into constexpr land – things like string_view; we’ve got constexpr coming into things like array, almost all of chrono and very soon I expect we’ll have constexpr cryptographic hashes Is it still me now? [JT] I think so. Okay One of the problems with constexpr is this inability to write a function and control or to even detect whether it’s being used in a constexpr context or not Sean Middleditch put this comment on reddit a couple of months ago now Basically the problem is that when you’re working in constexpr, you naturally have fewer tools than you do in runtime and so the kind of algorithms you use to solve problems at compile time aren’t necessarily as efficient as the ones you would want to use to solve the problems at runtime But you can’t tell which context you’re being evaluated in when you’re in a constexpr function So what you would like is something like this: imagine we have a function template that does a hash When we call it constexpr, we want it to use our constexpr version which is maybe this linear recursive thing – it’s not something we would choose to do at runtime And when we do it at runtime, we’d like it to be using all the efficiency features that we can bring to bear There’s still not really a very good story for this, but you can do, if you’re really determined, things like this. You can try constexpr SFINAE, and this is using something like the new detection idiom. This is the thing you would feed to the detection idiom, so if the T here is constexpr constructible, it’s admissible as a compile time argument to the comma operator on the end there, and so the result here is going to be a well-formed template argument In that sense the use of the comma operator here is similar to void_t void_t turns any type into void; the comma operator here turns any value into true And Marshall is waving a finger at me [Marshall Clow] Wants to plug his talk on Friday about the detection idiom Right. In fact, I rewrote this slide after I watched your talk on YouTube, Marshall Yes: Marshall is giving a talk about the detection idiom on Friday, and it’s really good So we can write something like this and then we can feed it to the detection idiom and we can have code like this that basically says: call the constexpr function if you can. Now the problem with this, as you probably are aware, is that there are many caveats Firstly constexpr constructible doesn’t mean constexpr hashable This wasn’t quite what we wanted Maybe we could get around that with a better expression, maybe not. But that’s the bigger problem with this is that, in fact, constexpr capable doesn’t necessarily mean it’s being called in a constexpr context. And that’s the thing you can’t really detect right now And you’ve got some verbosity and maybe some compile time issues. Those are probably less worrisome But if you’re going with this kind of thing it might mean, in the limit,

separating all your types. One set for compile time and one set for run time. And having some hopefully cheap conversion at run time for when your compile time things come out into your run time But in our opinion, the better solution to this is a current proposal from Daveed, which is a constexpr operator which exactly solves the problem of: how do I know if I’m in a constexpr context? And that would allow you to properly write functions that use all the [runtime] efficiency you want, but if you’re in a constexpr context, just use the tools you have and get the job done correctly And that would work [JT] So this is what we started with: we want to do some sort of constexpr compile time parsing of our JSON and we have two issues: the first is how to represent JSON values in a constexpr capable way Which I’ll be talking about next and then we’ll lead into how to actually parse these JSON values A JSON value is a discriminated union of: null, boolean, a number, a string, an array of values, and an object – which is a map of string to value So clearly we’re going to need some sort of recursion because we’re going to have to have objects that can contain objects, and maps that can contain objects and strings, etc, and we’re going to need constexpr ways to deal with string, vector and map So we’re going to see where we can get with that For constexpr strings C++17 adds std::string_view, and it’s great, but like a lot of C++17 things, the exact status of it depends on your current standard library implementation And string_view – it’s kind of in the name – is really only intended for viewing strings. It’s not intended for storing strings I’ve seen some articles lately about, if you were to put data that was on the stack into a string_view, and then keep a handle to the string_view, and now you’re accessing things that have popped off the stack, this is entirely possible. So string_view is not really what we want there. We need a way to pass and store, in general work with, character literals And string_view mixes metaphors We don’t want to be using something that’s called string *view* if we’re actually holding or manipulating strings So our first thing that we created was this static string class So (knock over random bottles of water around here) This, the first constructor, uses the ability to determine that you’re actually working with a const char array, so a const char array – or a string literal, specifically, is guaranteed to live for the lifetime of the program This I’m sure can be abused because you could create a const char array locally on the stack and then pop – or a char array locally on the stack, [and] pass it to this, but the idea is that we’re trying to detect that you’re actually working with a string that we know the lifetime of, on the first constructor, and it deduces the size of it And then the second constructor gives us a way to look at a subset of the string. And this is pretty straightforward: a constexpr default constructor and our sized C string data pointers. Anyone have any questions on this? All right [Vittorio Romeo] Is it different from string_view? In terms of what does it bring to the table? [JT] My microphone is static What does it bring to the table that string_view does not? Primarily this first constructor So that it’s easy to construct it from a const char literal And Marshall has a comment [Marshall] You have the sv suffix now. [JT] Right yes, so we could have used the _sv, suffix And we do actually use that. We do, it’s not underscore. It’s not underscore Oh, it’s just sv. It’s standardized so it’s just sv, and you will see that later. Okay. Right [Michał Dominiak] But it’s in a namespace! [Marshall] Yeah, I know [JT] It’s more of a semantic question because we want to pass these around and store them and have some degree of confidence that we’re doing something reasonable doing that So that leads us from string to vector, and we have our There’s an implied namespace here by the way: all these are in our cx constexpr namespace. [BD] Right, so in later slides, if you see something cx qualified, that’s what that is. [JT] Right. So, it’s constexpr. We cannot allocate memory, so we must know ahead of time approximately how big we want this array to be. In this case, we have a default value of five which is small, but

we’ll get into in a minute, why that size was chosen for these earlier examples. So it’s just an array that is default initialized because everything in constexpr context must be initialized So I had to fill this with whatever it’s got, and the size is equal to zero, that’s reasonable. Yes? [Michał] Maybe you have [it] later, but it’s worth mentioning Daveed’s proposal for a constexpr vector [JT] Yes, we will mention that later. So we don’t need to get it on the microphone, yeah So we just need to implement our iterator’s push_back. That’s the comments that you can’t read here The push_back and index operator, but we’ll get there So our begin and end constexpr: that’s easy push_back? So, all right, I like audience participation Why would I be – Let’s talk about this throw here Does anyone have a problem with the fact that I’m throwing in a constexpr function? [Audience] It just won’t compile it. [JT] It won’t compile if you get too big. And that’s the idea But it also wouldn’t compile if you got past the end in a constexpr context either Yes, Louis? [Louis Dionne] It is going to compile, unless you I mean, it’s going to compile if you’re going to do that at runtime, right? Unless you force it into a constexpr expression But since you’re returning void it’s unclear to me how you’re doing that I mean you probably can do that [JT] Well I mean this definitely all works The basic concept is: each time we push something back it increments the size, and that’s fine, and then if we get past the size? Now if I did not have this throw in it, and you’re using it in a constexpr context, and you get beyond the maximum size, you’re going to get a compile time error because it’s going to say that you’re accessing past the end of an array By adding the throw to it I give us something that can be used safely in a runtime context or in a compile time constexpr context. Make sense? [Tony Van Eerd] Do you also get a better error message, in the compiler? [JT] Do you get a better error message? I don’t [know] [Tony] Do you see “index past end of vector” show up? [JT] I don’t recall – do you? [BD] I don’t remember either [JT] I think it says you did a constexpr no-no; you threw. [BD] Yes, and I think it would show the line and the content of the line So, notice on the bottom here we’re not able to use next here, and that seems to be a bug in our implementation So for all these, the unspoken thing is we’re using GCC for all of this. [BD] Right, GCC7 I think the latest one I used was April 20th [JT] I don’t remember when I last compiled, but really bleeding-edge clang has been hit or miss: we got it almost all the way compiling with clang Partially it’s standard library issues. [BD] Yeah, we’ll cover stuff as we go [JT] Hey, it showed up! [BD] Yeah, it’s loaded there, it’s just not loaded there. [JT] That’s great So we can see in the compiler explorer here that the iterator category is not constexpr constructible in GCC’s internal implementation, so we can’t use std::next, even though we’d really like to, so I’m just doing Iterator pointer math… but it’s fine. [Vittorio] Did you report a bug? No. I am reluctant to report bugs on things that are changing every day, honestly But I didn’t also [BD] I didn’t report any bugs we found. [JT] No. Maybe we should go back and do that. [BD] It’s rather a class of bugs than one single bug So our vector can now look like a std::vector pretty much, and so you just push_back into it, yay! And in a constexpr context, now we can do a static_assert We can do a compile time check, say: “hey look, we have a vector of size 1, that’s what we’re expecting,” and it works So from here we build mutable constexpr strings We are doing that simply by inheriting from vector And so our concept of basic_string takes the char type and takes the size, and passes that to our vector base class, and then we have a couple of constructors to build from our static_string that we mentioned earlier and from std::string_view This does play a couple tricks; bullet points: constexpr data members must be initialized. That means we know that all of the data in our string is equal to 0. So that gives us implicitly a null terminator on our strings

A little bit of a cheat, and I have not yet provided any methods for shrinking the data structure but all you’d have to do is set that last terminating zero, and it should be good So carrying on from there, map is kind of obvious. It’s just an array of pairs of keys and values Although I guess to call this map is not 100% correct – you came up with a good name for it, I think you did. [BD] It is a flat map. [JT] It’s a flat map, but it’s also a flat unordered map and – [BD] Something like that. [JT] And depending on what you did you might even get multi_map It’s not very well constrained at the moment [BD] [Also] cx::pair Yes, and cx::pair, which we’ll get to in a couple slides. We’re using our own implementation of pair; that’s important – we’ll show why in a minute. [BD] It’s very minimal [JT] Extremely minimal. Actually we don’t even show the implementation of pair But we explain why we needed it Building on this, we can just make our index operator do a find to see if the thing’s there; if it’s not, insert it, and then you can use compile time maps like this We’re doing constexpr auto colors = get_colors(). So we’re just getting a thing that’s populated with a map of colors and the one that’s returning red we get returns 0xff0000 because that’s what we populated with at the top, and the one that says colors[“blue”] is a compile-time error And Richard does not like that for some reason? Why do we get a compile-time error? Because it’s a constexpr thing, and we did not populate the value “blue” [BD] The find inside our map is failing [RIchard Powell] It’s not going to return a default value? No, we can’t, because it’s constant. It would have to initialize the it would have to populate the member of the map for that value, if it were to keep with normal map semantics, and it can’t So it’s a compile-time error And, there’s a discussion about magic values I could argue that this is better than using an enum If I wanted to. Does anyone want to argue with me on it? Looking for some You want to argue? [Louis] Are you inferring that there’s absolutely no runtime cost associated with that? Because the color is – so in the int main, the colors[“red”] and [“blue”] are not in a constant expression, therefore it’s implementation – it’s quality of implementation whether there’s anything done there And I hear you laughing, but check the assembly [BD] True, true. This slide, I take responsibility for all slide errors [JT] No, I don’t know if I agree though because you will definitely get a compile-time error on the blue version, no? Wouldn’t you? I thought I ran it. Now I’m wondering [BD] I think the observation is that unless you assign the result of colors[“red”] to a constexpr variable, it’s not going to be in a constexpr context necessarily [Louis] Yeah that’s what I’m saying. That’s exactly what I’m saying. Therefore you don’t know whether there’s any code generated for that [JT] Right, I guess it’s possible Oh! Yes, right. We would have to – yes, okay. You’re right. [Marshall] “constexpr auto foo = …” [JT] Yeah, you have to – and that’s a continuing theme that we don’t mention specifically, but actually testing constexpr data structures takes discipline [BD] Yes, I would say [JT] So… can you…? [BD] I think I can Just Let’s try it This is an embedded Compiler Explorer view. [JT] Yes. So, if you didn’t know, Compiler Explorer supports embedded HTML views So why did we have to make our own pair? This is why: because pair’s assignment operator is not constexpr. It is the only part of pair that is not defined as constexpr, and I cannot think of any reason why it’s not The only thing I can come up with is perhaps the people that were doing an audit of constexpr things in the library said, “Well it’s constexpr, why would you need to reassign it?” But you do need to reassign it. [Michał] Did you submit a library issue? No, but I’m building in my mind the things, because it goes beyond constexpr, the things that are coming up in my head and the more time I spent with this. And we should probably do that [BD] Yeah, we should. We’ll make a pass

[Bryce Adelstein-Lelbach] Please file a library issue! Yes, we’ll – but it’s more fun to reveal it live in a talk [Marshall] You guys don’t get it – it’s not an either/or thing. Embrace the healing power of and! Right, but we have to present this first, and then we can submit the library issues. [BD] This is our motivation Yes Now we have to submit it. Ok, this: constexpr find_if. Looking at this implementation, does anyone see how it differs from the idiomatic version of find_if? Anyone? Anyone? Ok, I’ll tell you. [Marshall] It’s got extra curly braces. [JT] What’s that? It has extra curly braces, is that what you said? Marshall! Okay. How it differs is we added the keyword constexpr right before the return type! So I can try and re- re-open our notes Minor technical difficulties, excuse us So yes, and that leads us to… Bryce! [Bryce] Yes? [BD] Yes! We watch the Twitters! [JT] Bryce said, “Reviewing code I wrote last week, I found three implementations of constexpr transform. constexpr algorithms, please!” Many of them, you just need to add constexpr to the beginning of it, and it’s now a constexpr algorithm [Michał] And I can see at least several people who are in this room, “liked” that Yes [BD] Quite possibly! [JT] It’s probably… oh oh hey, there’s Vittorio! Recognize that one. Oh, and you, right, yeah Okay, so other algorithms that we had to do basically the same thing to, and I don’t know about you – you implemented some of them. The ones that I implemented, I literally copied the cppreference version and added constexpr to the front of it. [BD] Yes, that’s what find_if was. That’s what all these were, too [Audience] That should have been “library in a week.” [BD] Yes, library in a week. [Jeff Garland] We’re still open for suggestions! Anyhow, those are the things that we had to do. So that brings us to – I think I might be moving a little slowly – that brings us to: how do we actually represent our JSON value? And I have to admit 100% that I completely lacked the imagination for how to do this, and Ben pointed me in the right direction for revision one. Ben gets into much better revisions So we have our JSON value. Notice the template parameter depth equals five at the top? Yes, Bryce? [Bryce] Before we get too far away from algorithms, my answer to “can we have constexpr parallel algorithms?” remains “no.” Bryce says we cannot have constexpr parallel algorithms. I think he’s wimping out here, personally We constexpr ALL the things, Bryce So we have a struct – notice the depth equals five on the top line, and we have our struct data. Now, this should be a union, not a struct here, it was a struct because of a misunderstanding between me and the compiler, but in the version that’s up on github right now it’s a union So we have our data and our possibilities: our bool, our number, our string, our array, and our object Notice the depth-1 for each of these vector and map implementations? This is how we’re building our tree So it’s a tree that starts with a max depth of five and works its way down So it’s a tree that expands by – our max vector size and max map size are six and six each – so each layer could have six vector elements or six map elements in it five deep, and what did you calculate? That’s 7,000-some things. [BD] Just less than 8,000. [JT] Eight thousand template instantiations? [BD] 8,000 instances, I don’t know if it’s template instantiations This is the first thing we thought of that could work. I think that’s the way to put it [JT] It’d actually be like 8,000 times 3 because it’s the map and the vectors and the values and the – well anyhow And then the terminating zero at the bottom so that we don’t continue to go any further And then we just treat this like a JSON object We have a to_Array method: the const version of it asserts that it is currently an array; if it is not then it throws and in a constexpr context we have a compile time error. Yes, Bryce? [Bryce] Seems like you want a constexpr std::variant. Why don’t you just have that instead? [JT] A constexpr std::variant? I’ll tell you why in a few minutes Our non-const version

coerces the type into an array just as it would in the world of JSON things, and returns the value And then we can do things like this in a constexpr context, and they work; we can index into objects, we can set things and we can push values. [BD] And you can imagine, we showed to_Array, but we have to_String, to_Number, to_Object and indexing does the to_Object implicitly. [JT] Right So: why not std::variant, Bryce? Similarly to std::pair, variant is missing a few key constexpr things Notably, it does not have a constexpr copy constructor, does not have a constexpr move constructor, copy assignment, or move assignment. And those were all necessary, well, at least two of those were necessary to get this to compile. We need assignment and copy at least, I believe As far as I can tell there’s no reason why in the library it couldn’t just be made constexpr. Yes? [Louis] To implement variant you need you need to in-place new some stuff, right? Sometimes? Or all the times? It is not trivial [JT] So if it’s not trivial then you must in-place new it which is why we can’t do constexpr in these cases. Right [Louis] Now I suppose what you’re going to say probably is: Why can’t we have in-place new in a constexpr context? And that opens a huge can of worms Yes. I won’t get into the “why cannot we have in-place new in a constexpr context.” I’m not involved in this discussion [BD] So treat these as empirical observations, I guess and we can argue about all the implications [Louis] My only point is, there’s a very good reason why those cannot be a in a constant expression right now [JT] Right, ok. There’s a reason they can’t be. Go ahead. [Michał] It could be conditionally constexpr. [JT] Well yes. Right [Louis] Did you say these examples were all from GCC? [JT] Yes All right so, what things can we store in our containers? What are basically the requirements for our compile time things? They must have at least one constexpr constructor, and they must be trivially destructible Nothing else is required, assuming it does not get invoked in a constexpr context. So we found these shortcomings Array is an implementation thing. Some of the standard library implementations, depending on which compiler you’re using, may or may not have full array support string obviously is not constexpr, but there are versions of it that could be string_view we found corner cases where it didn’t do quite what we wanted it to pair and optional and variant are the things that we just talked about without being able to do assignment, and std::swap is not constexpr anywhere I might get an argument here, but I’m 99% sure that it could be I can’t imagine why it couldn’t be constexpr No one’s arguing with me: so std::swap can be constexpr; we’ll submit that [BD] The interesting part here is that some of these things were born into the constexpr world, like string_view and string_view does the best job of any of these things at being constexpr but there are still a few implementation issues that we find here and there [JT] Our containers have a fixed maximum size. They currently cannot shrink, but that could be done And they require types that are default constructible Because you saw that I have to initialize the array of things I posit the idea that we could wrap all of the things inside our arrays as std::optional and then we wouldn’t require them to be default constructible, we could just emplace them with the construction that we wanted. I didn’t actually try that yet, and it should be possible to templatize on constexpr enabled allocators, making all of these things optionally constexpr Does anyone…? Everyone’s okay with that [Audience] To have an allocator, you need constexpr placement new, and that isn’t available So you need constexpr placement new – you see this is the thing that I was overlooking in all these conversations: the constexpr placement new issue, I guess. [Marshall] Because that’s how allocators construct things, is placement new [JT] Right But if it were one that was intended only for constexpr allocation, it would not need to use placement new, it could default construct the array of things inside it, like on this slide, then simply reassign those things as it needed to and keep a free list I believe that you could implement an allocator that is intended for types that can be used in a constexpr context And hopefully I didn’t move too slowly

[BD] I think you bowed out quickly there to avoid more arguments? [JT] I’m also looking at the clock, making sure that we don’t take too long here. [BD] Ok, all right So that’s where we were in our first implementation of actually representing JSON values So then the part that fell to me was the parsing part [JT] The easy part! [BD] Yes, from my point of view the easier part As you know, I take all my inspiration from Haskell, so what is a parser? There’s this great serendipitous phrase: “a parser for things is a function from strings to lists of pairs of things and strings.” If Dr. Seuss had been a computer scientist, he would have said this but actually Fritz Ruehr, who is a functional programming lecturer at Willamette University, came up with this But what this means is – and in the coming slides, you’ll see I have Haskell type signatures to explain things for those that can read them, and for those that can’t read them they’re very easy to read so you’ll probably able to read them in a few slides So a parser is a thing that takes something like a string and turns it into the thing you want to parse out of it, and the rest of the string – that’s the pair – and then the list part is just representing: there might be multiple ways we can parse this Now in C++, we might write a signature something like this. And just an aside on this slide: I’ve started adopting trailing return type syntax, even in template aliases, because I think it’s really useful [JT] Yeah, that is not a deduction guide, just for the record. Which is what I thought it was when I first looked at it [BD] Right, that’s a function from strings to lists of pairs of things and strings Of course in C++, we don’t really mean lists of pairs of things and strings. Or even functions, so when we say “strings” we mean any string like thing. string_view, for instance, which will do nicely for a compile-time string So the input to the parser is a string_view, and the leftover part when you’ve parsed the thing out is also a string_view And the list here, well, nobody likes lists anyway; the list represents optionality, the multiple parsing. We’re going to be real simple and just say a parser can either succeed or fail and we’ll replace that with an optional: a constexpr-friendly optional type And of course when we say function we mean the usual thing we mean when we say function: anything that’s invocable. For instance, a constexpr lambda So let’s have a look at a really simple parser And I’ve got a couple of aliases, so parse_input_t is string_view, whenever you see that, and I’m just going to use this parse_result_t alias, to wrap up the pair of the optional so it doesn’t get too wordy So this thing: we give it the parse input and the char and it will either match the char, or fail So it very simply looks at the string_view: if it’s empty we obviously fail, or if the thing doesn’t match we fail, and that’s returning nullopt; otherwise we return the result, which is the char we matched and the rest of the string literal. You can see the data+1 and the size-1 is giving us the rest of the string_view So that’s really simple: that will match a character that we give it, and a string_view that we give it Now if you’ve been paying attention, you’ll realize this isn’t actually a parser yet, because that’s the wrong type signature The comment says, “ceci n’est pas une parser,” but you can’t see it So it’s not quite a parser because it doesn’t take only a string_view, it has the wrong signature. The signature is what we said before But given that we have constexpr lambdas, we can write a function that returns a parser which is itself a constexpr lambda And here it is. The body of this is exactly what you saw before except we’ve wrapped it up in a lambda, which is the actual parser and the make_char_parser function takes the char [and] captures it in the lambda. The lambda is then our parser for that character Yes? Easy, right? Well now that’s the simplest parser we could make; let’s move on to some other parsers Parsing fundamentally works on string-like things, so it’s going to be useful to write something like this We can only match one char so far, what if we wanted to match any one of a number of chars? We might write something like this, and I call it one_of So we pass it the set of characters that we want to match: any one of that set And what it returns – this is again a parser, which is a lambda of this type signature, and It’s just doing the kind of obvious thing. It’s saying take the first character in the in the string_view you give me, I’m going to look for it in my set, and if I

find it, I succeed and I parsed that character, but if I don’t find it, I fail and I return nullopt Happy? All right Well now we have one_of, you can imagine very very similarly, if we just negate the predicate in there, we get none_of, which is a parser that matches a character which isn’t in the set we give it. You can imagine how to write that based on what we saw before Likewise, we can write a parser which exactly matches a string that we give it. So we want to parse an entire string and exactly match that string We can do that, and the invisible comment says that we basically stuck constexpr on the front of std::mismatch to do that So you give it a string you want to match, it captures that, when you parse, you mismatch that and either succeed or fail in the parser So that’s a few primitive parsers We can parse chars; we can parse one_of a number of chars; we can parse strings In order to build up into being able to parse JSON objects, we need to be able to combine parsers and to do that we need parser combinators So here are a few parser combinators, and if you know a few functional programming patterns this will start to look very familiar One thing we want to do is change the result type of a parser. So we’ve got a parser that parses out a character; we might want to turn that into an int. Well we can easily write a function that turns a character into an int, and then we want to inject that into our parser, and then where we did have a parser for characters, you’ve now got a parser for ints. And that’s fmap Because in the functional pattern speak that’s a functor – a parser is a functor Likewise, a parser is a monad: we can take the result of one parser and feed it into another parser, do something based on that, and that’s what bind does Parsers also turn out to be monoids and applicative functors, so I’ll get to these in the next couple of slides, but here is fmap. So again, the Haskell type signature is at the top you give it a function and a parser, and it simply runs that parser That’s this line, running the parser. If the parser failed, obviously you can’t apply the function to what it returns, so your parser fails But if it succeeded, all you do is apply the function to what was inside it, wrap that up in your parser return type, and you’re done. The return type is just – parse_t here is the inverse of parse_result_t if you like. It’s the way to get the T out of a parser rather than making a parse type out of it So the result of running the function on what the parser is going to produce is going to be the result type of the parser that you’re going to produce And you simply do that All right, so that’s fmap Alternation, the alternation operator, operator bar, is a combinator that you give it two parsers, and it’s going to run the first one and if that fails, run the second one and return the result. If the first one succeeds, it doesn’t need to handle the second one. If the second one fails as well, then the whole parser fails And they have to be of the same type, because what you’re returning is the parser of the type, the both types that you put in So that’s what we have here This is just saying, “give me two parsers, and they better be the same type,” then what I’m going to do is simply run the first one; if it’s good, then I’m all good; otherwise return the result of running the second one. So real simple This is the monoid operation on parsers, and the unit for the monoid is the parser that always fails So, a parser that always fails – if you combine it, if you alternate it with any other parser, you’ll always get the result of the other parser. If you put it in the first place and it fails, you get the result of the second one; put it in the second place the first one is run first so that fails it fails and if it doesn’t fail, it goes. So this function is just easy: it returns the parser that always fails But, it returns the thing of the right type that you want [JT] If I may point out briefly, to make sure everyone’s catching this: every single one of these is returning a lambda So this is basically impossible before C++17 – or extraordinarily difficult [BD] I would say. It might be possible constexpr lambdas really make this whole thing work, and actually make it easy In my opinion So that’s fmap; that’s alternation – alternation turns out to be really useful The applicative operation on parsers is combining them, so if you look at the type signature at the top here, we give it two parsers, and we give it a function that will combine the results of those parsers into another thing, and what we get out is the parser for the thing that the function produces

That’s what you can see the code doing here. So once again, we run the first parser, and they both have to succeed, otherwise the function wouldn’t have anything to work on Bryce? [Bryce] How would you do that at all before 17? With like a local struct? [BD] How would you do that before 17? Yeah, I don’t know Probably by implementing your own lambdas somehow. [JT] Yeah, local callable struct? [Bryce] The only thing I can think of is a local struct [BD] Yeah, returning a local struct. [JT] And then returning that by auto [BD] But as you can see, this makes it much fewer lines of code, I imagine So combine – I chose to call it combine, because I didn’t really have a good name for it – but it runs both of the parsers you give it; in particular, it runs the second one on the thing left over from the first one So it’s running them in sequence Assuming they both succeed it’s going to run the function on both of the results, and then the leftover is the leftover from the second one because you’ve sequenced them Now, there’s a couple of uses of combine that turned out to be really useful, and so I put them under operator overloads. So I use greater than and less than So these are very simple applications of combine, and all they do is run the two parsers, and then throw away either the right hand side or the left hand side You keep the thing that is on the greater-than side, if you like. And that’s what this is doing, this operator<. It's just calling combine, and the function to combine the arguments just throws away the left-hand side here And you can imagine that operator> would just throw away the right-hand side. So this turns out to be really useful. I think I had not very many uses of combine that weren’t one of these And both of these operators are nice. They’re left-associative. They’re the same precedence. They work really well for building things up All right. We’re building up, and we’re building up things that enable us to build up further. There’s a few more things that form a pattern, and that is the pattern of accumulation Sometimes you want to run a parser multiple times and accumulate the result as you go, and that’s what these things do You can see from the type signatures, and I’m not going to show you the C++ code, but you can maybe imagine how it works You get a parser of a’s, and this is your seed value in accumulate-speak, and then here’s your accumulation function, which knows how to fold in parsed things into the seed And what you get out is a parser for the accumulated type. So, many is a parser that will run something zero or many times many1 is a combinator that will run a parser at least once, but possibly many times exactly_n, as you can imagine, runs a parser exactly n times and so it also has this integer argument, which is the n And separated_by turns out to be this incredibly useful thing, especially for – you can imagine – parsing lists of things What you’re going to be doing is parsing values, separated by commas, so it’s going to take a main parser, and then the in-between parser, and again it’s an accumulation style function signature to put things together. And it’s going to alternately run the parser for a’s and the parser for your separator And it’s going to end up accumulating into your list type, or whatever it is you’re accumulating Any questions about this? These are starting to look like building blocks now that we can use to parse real things All right, so here’s a few concrete examples This parser just eats whitespace. Really simple. So all we’re doing is space, or tab, or new line, or line feed, we’re making char parsers for each of those: that was really simple We’re alternating them together, so it will match any one We could have equally used one_of That would do the same thing. And then all we’re doing is saying, run that parser many times And I don’t care to catch the result so I’m just using monostate in my accumulation function So this parser just eats up all the whitespace that you give it in the string This parser simply parses a decimal integer. Just assuming a positive decimal integer. So we start out – we can’t start an integer with zero, so we start out matching one_of 1 through 9, and we bind the result of that, so we forward the result of that into the next lambda and then after that initial digit, we’re going to match one_of 0 through 9 many times I’m going to combine them all in the obvious way of shifting and multiplying and adding

Clear? All right The next one is a very simple string parser. A string is a quote, followed by a bunch of things that aren’t a quote, followed by a quote. And that’s what this is saying So here’s our quote parser; our string parser says many of not-quotes All this is doing in the accumulation is just taking the sub-string_view from the string_view you passed in. So it’s building that up as you go along And here you can see the greater-than less-than coming into play: this is very nice syntax. So just combining parsers together We just want to throw away the quotes at either end, and return the string [Michał] This doesn’t work with escaped characters [BD] Not yet! Right. We’re starting simple. Yes, it doesn’t work with escaped characters Okay, so this is what our JSON thing looks like again A reasonable approach to a first cut at this is to use parsers for each individual thing that it could be, and just alternate them together So we’re going to have six different parsers, each of which parses a thing that a JSON value can be, and we’re going to alternate them together [JT] So if you haven’t been paying attention up to this point, this is where Ben proves that he can make magical things happen and anything’s possible at constexpr time [BD] Well, it’s all in the lambdas! Once I heard of constexpr lambdas, I’m like, “this can be done!” So this wall of text is, as you can see, alternating six parsers together, and a couple of them were too complicated to fit on the slide, but then for each parser, it’s fmapping in a function to turn it into the [JSON_Value] given the appropriate thing that was parsed So either either the null, or the true or false, or the number, or the string The array parser and object parser we’ll get to I decided to take a disciplined approach to dealing with whitespace, you could put that skip_whitespace parser everywhere, sprinkle it everywhere. It’s idempotent – it wouldn’t matter if there was no whitespace. But to take a disciplined approach, I decided to put it before values So anytime you parse a value, it’ll eat the whitespace before it, and then parse the value, and then stop I said we’d get to these, although they’re too much to fit on a slide, but you can imagine now how they work now that I’ve shown you the way that things combine, and the separated_by combinator in particular. So array_parser will parse open square bracket, followed by values separated by commas, followed by close square bracket Accumulate that all into a JSON array value And object_parser works the same way, except instead of parsing values, it’s parsing key-value pairs All of this is inside – is this a function template? Yes, these are all function templates at the moment So we need a specialization for the base case, which is that last thing which just fails at zero And given this, this actually works This is the first cut that we had that actually worked, and so we can write now a constexpr user-defined literal And all it does is forward the string_view that effectively it’s given, into the value parser. And that produces a JSON object A JSON value All right, let’s talk a little bit – so once we got here, this was proof-of-concept. Now I started to think about error messages, and the story is not great Primarily because I have no way to tell the compiler to print out the string. I know where it failed, I just can’t get the compiler to tell anyone that. The best I can do is things like this where I deliberately alternate the failing parser with a throw here, so that I’ll get a constexpr problem in the compile, and the compiler will say, “hey, this isn’t constexpr: you made a mistake on this line,” and this will be somewhere in the output Vittorio? [Vittorio] If you don’t care about running this at runtime, you might be able to use static_assert with a dependent type, in order to trigger it only [BD] Okay, I might be able to use static_assert with a dependent type apparently [Bryce] I think ironically, you might end up back at the old way that boost::spirit used to report errors [BD] Okay, so boost::spirit has some tricks for reporting error messages [JT] Well hopefully moving forward we find better ways. [BD] Yeah, there’s actually a proposal There’s a proposal. [Audience] You would think so All right, so what we have now is the simplest proof of concept, right? It works; for suitable values, it works

Now it’s a good starting point, but there are some problems we need to address. Problem number one: a JSON number isn’t an integer. It’s this thing But we actually have almost all the mechanisms we need to parse this. I found it useful to add just one extra combinator, which I call option. Which is for this first optional minus. You can make a combinator which says run this parser, and if it fails just return a default value. The assumption being that the default value is plus, for implicit positive integers This is a problem, but this is a solvable problem with all the stuff we have Michał said strings aren’t string_views and he was perfectly correct, and the problem here is that in general, the size of the output is not the size of the input. You can’t just naively say, “Oh, yeah, I’ll take that string_view.” You have to actually convert characters And for the unicode stuff you’ll see that’s why I had exactly_n because it’s four hexadecimal digits Again, we fundamentally have all the tools to do this. We can output this into Jason’s contexpr string type and this can be solved with the tools we have. Problem three was a little more challenging, and problem three was that templates, especially function templates, especially recursive function templates, take a long time to compile So we need to get rid of some templates; and problem four is that we have pretty draconian arbitrary limits [Louis] I’m worried that you have so many template instantiations. You have a lot of constexpr code that has homogeneous constexpr [BD] Right. Well, the templates come from the fact that our JSON value is a template and therefore of all of our parse functions are templates instantiated every time for the level that we’re parsing [JT] Because the tree itself – the size of the tree has to be known at compile time So it’s recursive template instantiations of all the tree [Louis] But the depth of the tree is only 5 or whatever? [JT] Yeah, but I mean, it was still a lot, and it was slow [Louis] I’m questioning the idea that it’s caused by template instantiation, actually Chandler told me at some point that currently constexpr calculations are pretty slow Comparable to template instantiation [JT] Ben fixes that, so [Chandler Carruth] To clarify: Each step of an evaluation of a constexpr function is much faster than a step of template instantiation. But template instantiations can be memoized Which can reduce the algorithmic complexity of a large computation So N queens is much more efficient in a template instantiation metaprogram but small steps are much faster in constexpr [BD] Okay, so Chandler’s point was that because templates are memoized, so constepxr is faster to evaluate individual steps – much faster than instantiating templates, but once you’ve instantiated a template, it’s memoized, so your template version can beat the complexity of your constexpr. [JT] But with this tree, you’re not instantiating the same thing twice [BD] Yes, because the non-type parameter has to decrease All right, anyway these are significant problems and the next thing was to try and get rid of these. So the problem is we have templates, and all these recursive templates are problematic I just made a parsing framework, so I’m like, “what can I do with this?” The solution is obviously more parsing What we have now is given a literal, and parsing a JSON value out of it. What we can do is write another parser that runs over a literal, and tells us the number of JSON values we’re going to need. And if we know the number we’re going to need, then we can right-size an array, parse again into that array, and we can fix the templates And writing a parser that returns the number of values is fairly easy compared to actually returning the values All you do is say, arrays are 1 plus their children; objects are 1 plus their children; everything else is 1 You’ve already got all the structural stuff you need to do to understand running over the JSON So that’s what I did Given the result of that, we can now take out… this is – before, this was the function, this was the top-level function template we had before Well now, the template is up at the struct level. All the functions are just static constexpr functions. They’re not templates; they don’t need to be instantiated for every level of the tree. And we have right-sized our vector that we’re going to parse into

This requires a slight change to the JSON value, which was that the vector and the map inside it no longer store values. What they store are offsets into the array of values that we’ve parsed In particular, offsets from their own ‘this’, as it were This is what an example parse ends up looking like in object layout We’ve got an array which contains three values, and one of the values is itself an array So what we’re going to get out in our – our number-of-values parser comes back with six, because it’s two arrays and four numbers And then when we parse into our JSON value array, we get what you’d expect. So we parse the outer array, and then its children are The first child goes into the next one, the next child is itself an array, so we recurse into that and we get its children, and then finally we pop out of that and we get the third child of the top-level But we’ve right-sized the value array at this point (Tony Van Eerd claps) Thanks Tony. It gets better. There’s more to come. This did require this template form of the literal, which I believe is a GNU extension right now? [JT] Yes, but it should work with the regular [BD] I don’t know enough about it. [JT] Well according to the standard, it should work, but we couldn’t get it to compile with any compiler, but this compiles. [BD] This was proposal N3599 by Richard Smith There’s no reason we couldn’t have it in the standard The thing here is, to run the first parser, as soon as you get a parameter, parameters aren’t constexpr, so you need to turn your function parameters into template parameters, and you just expand them in an initializer_list and then you can call another template function which runs your numobjects parser here, return the value, and only then, because that was constexpr, you can use that as the template argument for your right-sized array What you end up producing here is the entire array of values, and the root value is at index zero So the cost of an extra pass, we don’t get the recursive function templates anymore, and there is no arbitrarily hard-coded depth limit, which means we can do silly things in our tests I just mashed the bracket until I had something, and then I guessed at the number of zeroes We still have some arbitrary limits though, on strings, arrays, and object sizes So hey, I’ve got a parsing framework: let’s use it. We can use the exact same technique we used for values, for strings We can write a parser that pulls out the entire string size that we’re going to use, the same way we pulled out the entire number size we were going to use So we precompute that, right-size a character buffer in the same way we right-size the value buffer, and then our strings in our JSON values become effectively string_views into the externalized string array Array of chars And in fact, we can merge this in with the number-of-values parser, because they’re not altering anything. They’re just parsing two values When I did this I did find out that structural bindings don’t currently work constexpr [Audience] Yet! So this is what that looks like This time we have, very similar to before, the array setup with the strings Number of values is still 6; total string size of all of the strings comes out as 14 We right-size a character buffer, and we right-size our value buffer, and now our strings contain effectively string_views into our externalized thing. So “X” here, and then this is the string_view that covers “all”, etc etc So you can see that works exactly the same way Now we’re down to limits on array size and object size And we can’t naively do the same thing we did with strings, because values within – the children aren’t necessarily contiguous, right? Because arrays can contain arrays or objects or anything in general You can see here the outer array: its children aren’t contiguous. If they were contiguous, we could store offset plus extent So to make them contiguous, we just need to turn a depth-first parse, which is inherently depth-first, into a breadth-first parse. I had this idea, but normally the way we would do this is by using a queue or something like that, and anything like that would have to grow, and we wouldn’t know at

compile time how to size it. But hey, we’ve got parsers. So let’s use them So all we need to do is make a parser that parses out the unparsed string_view that represents our child. And then we can effectively lazily parse that We extend our JSON value with one extra field representing the uninitialized value, which is still the string_view that’s going to produce the value And now when we have this we can write a parser, and this is the intermediate stage, so when we’re parsing this outer array, what we’re going to do is parse its children into unparsed states, which are the string_views that represent them Then once we’ve done that, hey our children are all contiguous now, we can go back and reparse them, and just put them on the end So that’s the intermediate state: the unparsed children are the string_views representing the values they will be So arrays are now offset plus extent: no limit on array size Similarly to arrays we can do objects, because objects are fundamentally alternating keys and values Keys are strings. We already know how to deal with externalizing strings, so just make object keys into values that happen to be strings, and everything is going to be happy This is an object, and it’s an array, but it’s an array of alternating values, so effectively its children are contiguous Alternating string and number, and string and number That’s the result of parsing that So now our JSON value. Now that we have all this parsing framework, which is doing what we want, our JSON value boils down to just this The string and the array and the object have all become effectively views into our external storage which is part of our constexpr object now. This is no limits. This is our final representation Given all of our parsers, we can do this So the conclusion to parsing is: constexpr lambdas really enable this. As soon as I heard about constexpr lambdas, I’m like, “I think we can do this now.” Parser combinators are the key to this, and the key is that when you combine parsers, what you get is another parser So they’re all composable and can be built up like this The template user defined literal stuff unlocks the ability to do multiple passes. In particular to do that initial pass where you right-size the value array and the string array And adding extra passes can solve almost any problem, as I found out Maybe a parser is a concept. I’m not sure: I don’t know enough about concepts yet to really answer that question But maybe this could have been helped by concepts And that is the end of that section [JT] So, for the future: currently we have a problem with destructors Any type with a non-trivial destructor cannot be used in a constexpr context. So we’re going to have a little quiz! Is this trivially destructible? Is S trivially destructible? Let’s raise hands – anyone says yes? Okay, everyone agrees Is S still trivially destructible? Everyone agrees. Is S still trivially destructible? Half? One and a half hands? No it can’t be because unique_ptr is not trivially destructible itself, so S cannot be trivially destructible Is S trivially destructible now? [Audience] No. I wish! [JT] “I wish!” was the answer from the crowd. Yes, we have this problem Why is this a problem? This is my example of why this is a problem. I’ve taken the concept of my constexpr-enabled container and said, “well, what if we got past the end of our statically allocated array?” In this case of 10. In our push_back we say well, length is greater than or equal to our size, and we have not yet allocated something. Let’s allocate some more storage and just expand it at runtime. And this works. And if you were to use this in a runtime context and go beyond those tens it would work. And if you use it in a compile time context and go beyond 10, then you get a compile time error It’s exactly what you would want But we have a problem: we can’t add a destructor. So if we want to do this we are required to leak memory I mean, “required” to leak memory – the compiler won’t let us do anything else with it

There are proposals to try and address this We have a proposal that suggests that if the body of the destructor is empty then it should still be allowed in a constexpr context. So by using if constexpr we could create something with an empty destructor optionally. But there are other tricks to do this You know I meant to actually put a slide up in here and I never did. [Michał] So you would basically write ‘if constexpr (constexpr())’ With the constexpr operator. [JT] That would be awesome! I didn’t even consider that. ‘if constexpr (constexpr())’. If that first proposal that we talked about goes through, then we would have a way to actually determine constexpr context. That’s brilliant But you could still accomplish the same thing maybe, because there are tricks right now that some of the standard library things use, that have to be trivially destructible if all of the things that they can contain – like variant is trivially destructible if all the things that it can contain are trivially destructible. And you can do that by conditionally inheriting from a base class that is trivially destructible. So using your trick, we wouldn’t even need this. We might be able to do the same thing, if we have the constexpr operator [Michał] All the boilerplate for the base class is everywhere [JT] The boilerplate for the base class is awful. Yeah, I played with it. It wasn’t horrible. [Michał] Did you see how it looks in libc++? [JT] No, I played with my own implementation not with the standard library one. [Michał] Go check out the the actual implementation in libc++ [It’s not pretty. [Marshall] That’s why we bury it in the standard library! [JT] I was going to say, you might have offended someone here with that, saying it’s not pretty I personally think that a destructor should be treated like anything else: if you don’t call code that is not allowed in a constexpr context in your destructor, then it’s constexpr-allowed. Why not? Yes? [Louis] Is that part of your proposal? [JT] I have not actually created a proposal for this. I’m just saying these are possible solutions that I think would be interesting [Louis] Is there anyone in the room who knows for sure why it was specifically ruled out of the list of things that can appear in a constant expression? [Bryce] Most of the answers to why something isn’t constexpr seem to be, “because we didn’t think about it.” [JT] So Bryce just said most of what he’s heard is, things aren’t constexpr because they didn’t think about it [Bryce] I would not assume that there was an intention to exclude it It’s very possible that it’s just never been considered [JT] So it’s possible it was just never considered that you might have a constexpr destructor allowed [Marshall] Or it might have been considered and somebody said, “Yeah, I need to go investigate it,” and never did. [JT] And never had the investigation. Yes? [Lisa Lippincott] And there are many, many, many things to be considered individually [JT] Yes, there are many things to be considered individually. [BD] We’re still just at the dawn of the third age of constexpr, so many things are unknown [JT] We also have a debugging problem So, what line does GCC report an error on? Who wants to throw answers out? [Audience] Six! [JT] No, it’s not six. [Audience] Internal compiler error! [JT] No, I actually got very few ICEs, I think on this project [BD] I didn’t get that many [JT] But when you’re working with nightly builds of bleeding-edge compilers, I think you can expect it to some extent So the answer is you get the error on nine, on the actual constexpr invocation But that doesn’t tell you what went wrong, right? It just says, “you accessed past the end of an array.” This is a trivial example When you’re talking about building up these data structures that we’re playing with, it wasn’t obvious [BD] Can we agree that four would be a good choice? [JT] And for the record, clang does actually give you the trace in this case and tell you where the error happened but GCC does not Did I just skip this slide? No sorry, okay Personally for me, several times while debugging I had to actually take the

examples for the data structures out of compile time constexpr context, put it intentionally into a runtime context so that I could hop into the debugger to see what I was doing wrong And you have a different story that you’ll get to I guess. [BD] My story was I didn’t so much have to take things out. I was mostly working, I had to go back and make sure the types lined up in all the lambdas I was composing. It was mostly a case of scaling it back to simpler stuff, and building up, and figuring out where I’d gone wrong [JT] The same person who proposed the constexpr operator has also proposed constexpr_trace and constexpr_assert, which will give us the ability to actually – instead of having to do some static_assert kind of trick, or throw something, you could actually put a message in here and get a reason why something got invoked that you didn’t expect it to Then there’s another proposal also, and I don’t know who this person is. Does anyone know him? [BD] Daveed Vandevoorde – he’s the author of “C++ Templates” [Bryce] We should probably make sure that you meet him [JT] Okay, I need to meet him. [Michał] Come to Toronto! [JT] I’m like, “That’s Odin. That’s not Daveed! I’m sure of this.” [Odin Holmes] A comment on the previous slide: that would allow you to express errors in templates when you have exceptions off Because that’s a big problem. [JT] Oh Okay So this would allow you to express errors in templates when exceptions are turned off. Okay. And yes, you’ve got a question? [Alex Zaitsev] Instead of a constexpr_vector proposal, you’ve got to write a proposal for a constexpr allocator [JT] Oh there’s already a proposal for a constexpr allocator? I don’t know about that one Whaaaaat? [BD] The constexpr_trace would be I’m sure widely usable [Michał] This is the best thing ever! [JT] So constexpr_vector is a vector that can grow at compile time; it requires compiler support, and it could have basically eliminated a lot of the stuff that you had to do With right sizing everything. Maybe? [BD] Quite possibly While we’re on the topic, a constexpr random_device? Would be very useful for cryptographic string hashing [JT] It is currently possible to generate random numbers at compile time. [Audience] constexpr fstring! [JT] constexpr fstring? [BD] Yes, you can write constexpr random number stuff, but the problem is you don’t have a great deal of entropy available at compile time. [JT] The best I’ve come up with is using __DATE__ and __TIME__ macros. But you can, it works. So why not? Why not a random device? [Audience] People will hate you for the [lack of] reproducible builds [JT] We’re not so concerned about reproducible builds when we’re doing experimental fun talks in Aspen [Tony] You can always just return nine. [JT] Yes. Nine, nine nine, No way to know if it’s random or not! We’re running low on time. [Gašper Ažman] Do you think that is one thing that should be a macro? [JT] A random number? [Gašper] Yeah – so you can set it from the compiler [command] line? [JT] That would make more sense than random_device, yeah I would be okay with that [Gašper] __RANDOM_SEED__? [JT] Why not? [BD] Some way to get entropy from the compiler, which it can do [Gašper] Just ‘-D’ it on the compile line. [JT] I just have to convince Chandler to add it for us and Let’s see if he’s paying attention [Audience] #include ? [JT] Would that work? [BD] That wouldn’t terminate. [JT] Yeah it wouldn’t terminate, that’s what I’m thinking Currently the only three algorithms that we are aware of that could not be made constexpr with their current requirements are stable_sort, inplace_merge and stable_partition, right? Because they’re all allowed to allocate temporary buffers. [Audience] They optionally allocate! [JT] Yes, they’re allowed to is the thing. [BD] They should, to be efficient I think is the point. We know how to do these algorithms without allocating Actually I think they are required to allocate the buffers in order to meet the complexity guarantees which are required

I think maybe that’s the case. No? [Audience] The spec says that they are O(n) if memory is available [JT] If memory is available. Oh, so you could just say if operator constexpr, memory’s not available [BD] Okay, so these could be made constexpr – we know how to do it. [JT] Go forth and implement! [Audience] stable_partition, in-place_merge… [Bryce] I think that is the list [BD] Yeah, those are the three. [JT] stable_sort, inplace_merge and stable_partition [BD] Marshall’s checking up. [JT] Yeah, we’ve got five minutes, all right [Bryce] You guys can go over. The food’s not going to be ready at the picnic, don’t worry [JT] I’ll be hungry though is the problem! [Marshall] I’ve got to go out and cook it [Audience] Yeah, some of us have to go cook! [JT] Marshall, you’re allowed to leave [BD] We made these constexpr containers, and We see no reason why many iterators, if they’re working with constexpr containers, shouldn’t be all constexpr [JT] There’s only little pieces, like std::next is supposed to be constexpr, but an implementation problem And distance, yes But why not back_insert_iterator? My vector has a push_back. There’s no reason it couldn’t work, but the standard doesn’t currently Ben’ll write all this up after we’re done, and submit a proposal! [Michał] You should do that so you have to come to Toronto, say to meet Daveed [JT] When is Toronto? [Audience] July. [JT] Oh, that’s not going to be possible [Michał] Then Albuquerque, in November? [JT] That’s also not possible on the other end for me. I’m hoping to be at another conference then So, cost? To me, the flat data structures that we’re talking about were easy to reason about constexpr code I think forces you to consider what your code is doing in the lifetime of objects in a good way. In fact for me personally, after working on this, now everything that I write I start with constexpr in front of the function, and then decide if I can’t make it constexpr I think that building these tree like data structures was difficult to reason about [BD] Tree-like data structures, maybe yes. Tree-like evolution of processes in recursive way, that’s a little easier to reason about sometimes, because you can just sort of assume magic happens in a recursive case And then it works! [JT] Proof by induction. [BD] Yes. You just have to embrace induction! [Audience] Is constexpr another default that is wrong? [JT] I think I’ve been told to not be negative about these things I’m sorry, the question was, “is constexpr a default that’s wrong?” I’ve been bad about repeating some of the comments I think, maybe? And noexcept maybe too, on the other end Error messages. You had an anecdote about your error messages? [BD] I was running my compiles from within Emacs. Frequently I had to kill the compile, because a single line of the compiler’s output was going to be megabytes in size, and it was just slowing down the editor When you have lambdas containing lambdas containing lambdas, it builds up a bit My approach to debugging was just, look at the code some more and figure out where I went wrong. I couldn’t really use error messages Go back, and think about the types. That was it [JT] Cost of building a debug build. So everyone wants know compile time cost Six gigs of RAM. Well, I’ll get into the disconnect here in a second. More than two minutes for our simplest test cases, and produced a 338 k binary But Tweaking the debug level had some effect on this Ggoing to the next slide I was communicating with Ben, saying, “How are you compiling this? It’s taking me minutes, I’m running out of RAM. My VM isn’t big enough.” And he said, “I don’t know you’re talking about. It takes five seconds to build for me.” And it turned out I was doing debug builds, and he was doing release builds. [BD] You see, that’s the great thing about constexpr. There’s nothing to debug! If it builds, it works! [JT] So we think this must be something related to shuffling around

debugging symbols and that kind of thing in the compiler, that we don’t know enough about. I certainly don’t know enough about 9k. So the release stuff is spot-on. [BD] This is a much better story, I hope you agree [JT] This is a complete program Using the same nightly build of GCC, how long does this take to compile? You want to take guesses? [Audience] debug build? [JT] Either. I have numbers up for both as soon as I click next [Audience] Six seconds. [JT] Six seconds? That’s about right. Five seconds for the debug, seven and a half seconds for release. So the stuff that Ben did You know, why not? Totally usable If you don’t care about debug builds. [BD] Like I say, there’s nothing to debug! It’s all compile time [Audience] What was the memory usage? [JT] I don’t recall on this slide. I’m sorry, and I didn’t write the number down [BD] In conclusion. [JT] Yes. All but three standard algorithms can easily be made constexpr, we believe [BD] There are a few holes in the STL, mostly around assignment operators, some of which could be overcome. [Marshall] I hope you have a list [JT] Well, this is most of the list We can make it, yes But the problem is, I think I have to roll it into other stuff that I’ve been looking at [Marshall] Doesn’t have to be today. [JT] Okay By tomorrow, we’ll have a list. [BD] All the time we’re working on this, Jason is like, “I want to put this in C++ Weekly!” Lost of grist! [JT] Yes, I was restraining myself. There’s lots of things I wanted to show and other examples Iterator operations, right. I have a concern that the – what’s that? [Marshall] There are LWG issues about that about. [JT] cmath? [Marshall] No, iterator operations [JT] Oh, okay. [Marshall] There are open LWG issues. [Bryce] cmath is harder; I filed a national body comment to this Yes, I think that this might hold us back on some constexpr things – and Bryce is agreeing – because of the interaction with math.h and cmath. Can we make things constexpr that C wouldn’t understand what that means? [Bryce] Depends how much you want Okay. [BD] We’ve generated a lot of work [Bryce] So the things in cmath, my understanding is that they need to be the same function, same addresses. If they need to have forwarding [Audience] So why not cxmath? [JT] Yes, why not have a cxmath, or if the internal implementation of the – oh no, because you’d still have to put it on the signature [Bryce] I think a cxmath is probably fine, but the ones that are actually in cmath, we probably can’t. [Audience] Why do we have that on cmath and not most everything else? [Bryce] No, it’s any of the stuff we import from C [JT] Any of the stuff that we import from C might have a problem We’re going to keep clicking. [Michał] A lot of stuff we import from C already has __throw on it [JT] That’s interesting. [Michał] So we could have __constexpr? Let’s try to wrap this up. We’ve only got like two clicks left [BD] constexpr lambdas? They can do everything [JT] I think constexpr allocators are possible. Apparently there’s a proposal for that And I think it should be doable, with enough work, that we could actually unify our containers and say, “Well I want something with a statically-sized constexpr thing, and it’s a std::vector.” And have it do what we expect it to. I think that should be possible [BD] So, thank you very much, and that’s the github [link] [JT] And now Marshall gets to go cook [BD] We may have a few lingering questions. I don’t know if we have time to take them [Marshall] I’m very serious about the list. I’d love to see the problems you ran into. [JT] Yeah, we need to put it all together [Marshall] Both standards problems, and library implementation problems [BD] In the back? [Audience] A quick comment. One of the reasons the committee has been more conversative about adding constexpr is because adding constexpr to std::invoke broke. It changed semantics, because it triggered early instantiations of templates So just a comment to be mindful of that. [BD] Right. The comment is: it’s as well to be careful about adding constexpr. Adding constexpr to std::invoke broke and changed semantics

So we’re a bit careful about that sort of thing Sorry, we can’t both be pointing at people, I’ll just [Odin] This could be completely wrong, because it’s not my domain, but that might the reason that you can’t make every std::swap constexpr be because of polymorphic allocators in the things that you’re swapping? [JT] Just marking a function constexpr doesn’t mean that everything that is invoked by it would be usable in a constexpr context. I’m almost positive we just need that constexpr keyword on the front of swap, and if you try to use it with a type that can’t be done in a constexpr context, in a constexpr constext, then you would get a compile time error. Otherwise, it would just work I think I get agreement. Yes, Juan? [Juan] I suspect that maybe you could decrease the compile time a lot if you remove the sizes from the types. I was wondering if you could get away by having something like an array allocator where you basically put in your vectors and everything, just put memory for it, and you could… Looking at how your parser works, I was wondering, probably you can find a constant factor of the input stream that will give you always enough memory to actually… [JT] That’s effectively what Ben did He pre-allocated all the storage and then indexed into it [Juan] But you were still like [BD] Yes, it would be possible. My first thought was, let’s just make a big buffer and go into it But then I thought you know, I’m not satisfied with having all that slack I want something that’s rightsized We’re all C++ programmers, right? [Juan] You are reinstantiating, I think, a lot of the parsing functions for the sizes of the things It’s just an optimization. I admit, it’s much more elegant, I think, the way you did it from a type point of view [BD] Like I said, our first cut was the simplest thing that worked, and it was pretty bad This is only the second cut. There’s a lot more that can be done, I’m sure Zach? [Zach Laine] I just want to point out that there’s a real fear in LEWG that adding constexpr or noexcept to types for which it is not part of fundamental design that they have those, is constraining implementations that want to experiment with these things, or introducing possible problems like std::invoke. And so the idea is: don’t tell implementers they can’t add it, and don’t add it now unless it’s part of the sign of that type that needs it That’s kind of what people are feeling in LEWG these days [JT] The comment was you don’t want to overly constrain the standard requirements by saying constexpr on things that we don’t know the full implications of? [Zach] The feeling is that we don’t, as a community, have a real great grasp on what best practices are yet [BD] But constexpr is, a lot of times, types are born intended to be constexpr Adding constexpr speculatively elsewhere is something we need to be careful about [JT] But I find the one that really stands out to me is std::pair Every aspect of it is constexpr, except the assignment operator So you can do pair.first and assign it; pair.second and assign it, and get the same effect I feel like that should be considered a defect, that we can submit a proposal or something [Audience] You can get the same effect? With these trivial types, definitely. Yes [Bryce] Louis, you may need to clarify this for me. My understanding is there’s one place in C++17 where we can have a function that is constexpr without being marked. And that’s a lambda’s call operator. The constexpr is optional [BD] That’s right. [Bryce] This idea about trying to figure out lists of all the things that we should make constexpr? I would prefer that we try to figure out more ways that we can make things that the compiler can determine are constexpr, and just be constexpr out of the box. [JT] That is way outside of my knowledge We probably really should wrap up, I think. [BD] One more, then VIttorio put his hand up right before you said that [Vittorio] There has been some discussion on slack about a possible way of passing constexpr parameters by wrapping this up inside a lambda which is implicitly constexpr, and passing the lambda, and then calling it from the function. That guarantees that what you’re getting out of the lambda is constexpr. So that’s a way you can do constexpr. [JT] Does that work, currently?

[Vittorio] Yes, there are some some examples. I haven’t tried it yet, but it’s promising [Michał] A classic example of adding a layer of indirection! [BD] From Vittorio, to the world: if you want constexpr function parameters, wrap them inside lambdas which are then constexpr-callable. And you can get them out. [JT] I feel like there’s another Dr Seuss thing in there about lambdas of parameters of All right, thank you all! See more C++ captions and translations at cppvap.wikidot.com