{"id":9577,"date":"2020-08-27T09:17:05","date_gmt":"2020-08-27T07:17:05","guid":{"rendered":"https:\/\/sii.pl\/blog\/?p=9577"},"modified":"2023-10-23T10:43:14","modified_gmt":"2023-10-23T08:43:14","slug":"implementing-a-state-machine-in-c17-part-3-compile-time-strings","status":"publish","type":"post","link":"https:\/\/sii.pl\/blog\/en\/implementing-a-state-machine-in-c17-part-3-compile-time-strings\/","title":{"rendered":"Implementing a State Machine in C++17 \u2013 part 3 \u2013 compile time strings"},"content":{"rendered":"\n

In the previous series of articles (part1<\/a>, part2<\/a>) we’ve played with a simple state machine with some basic functionality. As the machine grows bigger, the need for debugging utilities becomes more important. To implement such utilities we need to do some groundwork first. All state, event, and action names are known at compile-time and for most of them, we could easily generate a string with the name during compilation. What’s problematic is that some of the types could be parametrized and would require some form of compile-time string concatenation. That’s exactly what we are going to explore in this article \ud83d\ude42<\/p>\n\n\n\n

Basics<\/h2>\n\n\n\n
\"\"<\/a><\/figure>\n\n\n\n

As most of you probably know, string literals in C++ are of type const char[N]<\/code><\/strong> and what’s more important they always include the terminating null character. Another important fact is that string literals are known at compile-time, which means we can do something like this:<\/p>\n\n\n

\nconstexpr char[] value = \"Foo\";\n<\/pre><\/div>\n\n\n
For each variable marked with constexpr<\/code><\/strong> the compiler enforces that it’s value must be calculated during compilation (C++20 expands this idea with consteval<\/code><\/strong> and constinit<\/code><\/strong> keywords, but that’s a story for another article). For functions there’s a slight difference. There are some restrictions placed on constexpr<\/code><\/strong> functions so that their return value could be used as a compile time constant, but what’s important is that the compiler will still generate an ‘ordinary’ (non-constexpr) function that would be used when non-constexpr arguments are passed.<\/p>\n\n\n\n
So, getting back to string literals. Unfortunately, there are no easy ways to return a native array from a function. What’s even more disappointing is that extra care needs to be taken when passing arrays to functions. Take a look at this example:<\/p>\n\n\n
\nvoid trap(const char arr[7])\n{\nstd::cout << sizeof(arr) << std::endl;\n}\n<\/pre><\/div>\n\n\n
Since array arguments automatically decay to pointers this code is equivalent to:<\/p>\n\n\n
\nvoid trap(const char* arr)\n{\nstd::cout << sizeof(arr) << std::endl;\n}\n<\/pre><\/div>\n\n\n
Looks different. Doesn’t it? \ud83d\ude42 What’s even more annoying we cannot use template parameter deduction to ‘extract’ the size of the array<\/p>\n\n\n
\ntemplate <typename T, std::size_t N>\nvoid trap(T arr[N]) \/\/ <-- This doesn't work\n{\nstd::cout << (sizeof(T) * N) << std::endl;\n}\n<\/pre><\/div>\n\n\n
Fortunately there’s a neat little C++ trick that we can use here. Even though arrays automatically decay to pointers, references to arrays do not follow this rule…<\/p>\n\n\n
\ntemplate <typename T, std::size_t N>\nvoid trap(T (&arr)[N]) \/\/ <-- Works!\n{\nstd::cout << sizeof(arr) << std::endl; \/\/ <-- This also works\n}\n<\/pre><\/div>\n\n\n
Syntax looks a bit odd due to the parenthesis, but at least it works \ud83d\ude42 . Since storing a reference to an array (which might be temporary value) is not always the best idea, we’ll use std::array<\/code><\/strong> to hold the values. It’s just a thin wrapper around a regular array and most of its methods are already constexpr<\/code><\/strong>. A bit of required functionality is missing though, so we’ll need to implement it ourselves.<\/p>\n\n\n\n
Extending std::array<\/h2>\n\n\n\n
As we discussed before, a string literal is just an array of characters, and since we’ll be working mostly with std::array<\/code><\/strong> we need to have a mechanism to convert one to another. Let’s start with the conversion from a regular array. std::array<\/code><\/strong> uses aggregate initialisation so we cannot simply pass an array as a constructor argument. So we’re on our own here. There are of course multiple ways to do implement such a function. Let’s start with something based on index sequences and parameter packs.<\/p>\n\n\n
\ntemplate <typename T, std::size_t N>\nconstexpr std::array<T, N> toStdArray(T (&arr)[N])\n{\nreturn toStdArray(arr, std::make_index_sequence<N>());\n}\n<\/pre><\/div>\n\n\n
The rough idea is quite straightforward. We start with capturing the array by reference, then we create an index sequence from 0 to (N-1) and pass it to a template with a parameter pack<\/p>\n\n\n
\ntemplate <typename T, std::size_t N, std::size_t... Idx>\nconstexpr std::array<T, N> toStdArray(T (&arr)[N], std::index_sequence<Idx...>)\n{\nreturn {arr[Idx]...};\n}\n<\/pre><\/div>\n\n\n
Here we just need to expand the parameter pack containing the indexes and we’re ready to construct the array. Note that std::index_sequence<\/code><\/strong> is only used to deduce a parameter pack containing all the numbers 0 to N-1.
Ok, we know how to construct a std::array<\/code><\/strong> out of a regular array. Now we need to implement a function that combines two arrays together.<\/p>\n\n\n
\ntemplate <typename T, std::size_t LeftSize, std::size_t RightSize, std::size_t... LeftIdx, std::size_t... RightIdx>\nconstexpr std::array join(const std::array& lhs,\nconst std::array& rhs,\nstd::index_sequence<LeftIdx...>,\nstd::index_sequence<RightIdx...>)\n{\nreturn {lhs[LeftIdx]..., rhs[RightIdx]...};\n}\n \ntemplate <typename T, std::size_t LeftSize, std::size_t RightSize>\nconstexpr std::array<T, LeftSize + RightSize> join(const std::array<T, LeftSize>& lhs,\nconst std::array<T, RightSize>& rhs)\n{\nreturn join(lhs,\nrhs,\nstd::make_index_sequence<LeftSize>(),\nstd::make_index_sequence<RightSize>());\n}\n<\/pre><\/div>\n\n\n
That’s the same idea but with a bit more template parameters \ud83d\ude42 .<\/p>\n\n\n\n
There’s one slight detail still missing. Remember that all string literals end with a null value at the end and we don’t want that value to end up in the middle of a newly joined string. We need a mechanism to trim or in more general terms, resize the array.<\/p>\n\n\n
\ntemplate <std::size_t NewSize, typename T, std::size_t OldSize, std::size_t... Indexes>\nconstexpr std::array<T, NewSize> resize(const std::array<T, OldSize>& arr, std::index_sequence<Indexes...>)\n{\nreturn {arr[Indexes]...};\n}\n \ntemplate <std::size_t NewSize, typename T, std::size_t OldSize>\nconstexpr std::array<T, NewSize> resize(const std::array<T, OldSize>& arr)\n{\nconstexpr std::size_t minSize = std::min(OldSize, NewSize);\nreturn resize(arr, std::make_index_sequence());\n}\n<\/pre><\/div>\n\n\n
Biggest difference here is that we can specify the result array size, so we could create a new, larger array and use the previous one as initial values.<\/p>\n\n\n\n
As a last utility function we’ll implement areEqual<\/code>. Even though std::array<\/code><\/strong> provides an equality operator it’s not marked as constexpr (but will be in C++20) and we can’t use it. We’ll once again use the std::index_sequence<\/code><\/strong> trick, but this time we’ll also use a fold expresion (introduced in C++17) to generate a big boolean expression comparing all the elements.<\/p>\n\n\n
\ntemplate <typename T, std::size_t N, std::size_t... Idx>\nconstexpr bool areEqual(const std::array<T, N>& lhs, const std::array<T, N>& rhs, std::index_sequence<Idx...>)\n{\nreturn ((lhs[Idx] == rhs[Idx]) && ...);\n}\n \ntemplate <typename T, std::size_t N>\nconstexpr bool areEqual(const std::array<T, N>& lhs, const std::array<T, N>& rhs)\n{\nreturn areEqual(lhs, rhs, std::make_index_sequence());\n}\n<\/pre><\/div>\n\n\n
The fold expression will expand to something like: (lhs[0] == rhs[0]) && (lhs[1] == rhs[1]) && ... && (lhs[N-1] == rhs[N-1])<\/code> which has this nice property that it will stop at first difference due to short circuit evaluation.<\/p>\n\n\n\n
Compile time tests<\/h2>\n\n\n\n
constexpr<\/code><\/strong> modifier on functions allows those functions to be used in static assertions. What we can achieve with it is that we can create simple compile-time tests that could be included in the header. When we make a mistake or a typo the compiler would see a failed static_assert<\/code><\/strong> and stop the compilation with an error. In other words, the code compiles only when all the tests pass, which is pretty neat. On the other hand, we don’t want to include test-only code in the resulting binary, so we need to add some special measures to circumvent it.
First of all, it would be a good idea to wrap the code in an anonymous namespace. This causes all the functions in that namespace to have an internal linkage so most compilers would be able to remove those functions if they’re not called in the same file. Unfortunately, this also leads to a warning. There’s an easy fix for that. We could mark those functions with a maybe_unused<\/code><\/strong> attribute.<\/p>\n\n\n
\nnamespace tests\n{\nnamespace\n{\n \n[[maybe_unused]] constexpr void testToStdArray()\n{\nconstexpr int input[] = {1, 2, 3};\nconstexpr auto output = toStdArray(input);\nconstexpr std::array expected = {1, 2, 3};\nstatic_assert(areEqual(expected, output));\n}\n \n[[maybe_unused]] constexpr void testJoin()\n{\nconstexpr std::array inputA = {1, 2, 3};\nconstexpr std::array inputB = {4, 5};\nconstexpr std::array expected = {1, 2, 3, 4, 5};\nstatic_assert(areEqual(expected, join(inputA, inputB)));\n}\n \n[[maybe_unused]] constexpr void testResize()\n{\nconstexpr std::array input = {1, 2, 3};\nconstexpr std::array expectedShorter = {1, 2};\nconstexpr std::array expectedLonger = {1, 2, 3, 0};\nstatic_assert(areEqual(expectedShorter, resize(input)));\nstatic_assert(areEqual(expectedLonger, resize(input)));\n}\n \n}\n}\n<\/pre><\/div>\n\n\n
Creating StaticString<\/code><\/strong> class<\/h2>\n\n\n\n
Now we have all the necessary tools to create StaticString<\/code><\/strong> class. The class itself needs to be a template parametrized by string length, but hopefully in most cases the compiler will be able to deduce the exact value for us. The most convenient way to create a StaticString<\/code><\/strong> instance would be to create it from a string literal and since we plan to store the data in a std::array<\/code><\/strong> let’s add another constructor for that case.<\/p>\n\n\n
\ntemplate <std::size_t N>\nclass StaticString\n{\npublic:\nconstexpr StaticString(const char (&chars)[N])\n: chars(toStdArray(chars))\n{\n}\n \nconstexpr StaticString(std::array<const char, N> chars)\n: chars(std::move(chars))\n{\n}\n \nprivate:\nstd::array<const char, N> chars;\n};\n<\/pre><\/div>\n\n\n
Now it’s time to implement the main functionality – ability to add two StaticStrings<\/code><\/strong> together. The operation itself is pretty straightforward with two minor details. First of all, we need to consider the null character when joining the strings, but that can be circumvented by simply shrinking the first string by 1 character. The second issue is a bit more subtle. StaticStrings<\/code><\/strong> of different lengths are considered different types and thus cannot access each other’s private members. Fortunately, there’s a way to fix it without exposing the data to unrelated classes. Friend specification can be introduced as a template, meaning we can give access to a range of types with a single statement.<\/p>\n\n\n\n
\"\"<\/a><\/figure>\n\n\n
\ntemplate <std::size_t M>\nconstexpr StaticString<N + M - 1> operator+(const StaticString<M> &rhs) const\n{\nreturn join(resize<N-1>(chars), rhs.chars);\n}\n \ntemplate <std::size_t M>\nfriend class StaticString;\n<\/pre><\/div>\n\n\n
Since we’d like to test our implementation, let’s also add an equality operator.<\/p>\n\n\n
\nconstexpr bool operator==(const StaticString<N> &rhs) const\n{\nreturn areEqual(chars, rhs.chars);\n}\n<\/pre><\/div>\n\n\n
As a bonus we can provide a getter for data pointer for easier printing later on.<\/p>\n\n\n
\nconstexpr const char* data() const\n{\nreturn chars.data();\n}\n<\/pre><\/div>\n\n\n
Finally we can add tests for joining strings to see if they work as planned<\/p>\n\n\n
\nnamespace tests\n{\nnamespace\n{\n \n[[maybe_unused]] constexpr void testAdding()\n{\nconstexpr StaticString lhs{\"abc\"};\nconstexpr StaticString rhs{\"de\"};\nconstexpr StaticString expected{\"abcde\"};\nstatic_assert(expected == lhs + rhs);\n}\n \n}\n}\n<\/pre><\/div>\n\n\n
Looking at the generated code<\/h2>\n\n\n\n
Let’s create a simple test function and look at the disassembled code<\/p>\n\n\n
\n__attribute__((noinline)) void test()\n{\nconstexpr StaticString first{"<"};\nconstexpr StaticString second{"hello"};\nconstexpr StaticString third{">"};\nputs(first + second + third);\n}\n<\/pre><\/div>\n\n
\n0000000000401180 <test()>:\n401180:       50                      push   rax\n401181:       48 b8 3c 68 65 6c 6c    movabs rax,0x3e6f6c6c65683c\n401188:       6f 3e 00\n40118b:       48 89 04 24             mov    QWORD PTR [rsp],rax\n40118f:       48 89 e7                mov    rdi,rsp\n401192:       e8 b9 fe ff ff          call   401050\n401197:       58                      pop    rax\n401198:       c3                      ret\n401199:       0f 1f 80 00 00 00 00    nop    DWORD PTR [rax+0x0]\n<\/pre><\/div>\n\n\n
As you can see the compiler got rid of most of the copies and reassignments and leaves us with just the evaluated result passed to puts<\/code><\/strong> function.<\/p>\n\n\n\n
Summary<\/h2>\n\n\n\n
In this article, we explored the possibility to join strings at compile time. The feat itself might not be so impressive, but it’s one of the things needed to generate a transition table at compile time. As always, you can find the code in my Github repository: (link<\/a>)<\/p>\n\n\n\n
In the next article, we’ll play a bit with the type system, trying to extract as much information as possible with a hint of functional programming \ud83d\ude09<\/p>\n\n\n\n
Stay tuned!<\/p>\n\n\n
\n            \n
\n    \n
\n            
\n            \n\n
<\/div>\n        <\/div>\n            
\n            \n\n
<\/div>\n        <\/div>\n            
\n            \n\n
<\/div>\n        <\/div>\n            
\n            \n\n
<\/div>\n        <\/div>\n            
\n            \n\n
<\/div>\n        <\/div>\n    <\/div>\n    \n
\n            
\n            \n\n
<\/div>\n        <\/div>\n            
\n            \n\n
<\/div>\n        <\/div>\n            
\n            \n\n
<\/div>\n        <\/div>\n            
\n            \n\n
<\/div>\n        <\/div>\n            
\n            \n\n
<\/div>\n        <\/div>\n    <\/div>\n<\/div>\n                \n\n
\n            5\/5 ( votes: 5)    <\/div>\n    <\/div>\n","protected":false},"excerpt":{"rendered":"
In the previous series of articles (part1, part2) we’ve played with a simple state machine with some basic functionality. As … Continued<\/a><\/p>\n","protected":false},"author":193,"featured_media":9658,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"_editorskit_title_hidden":false,"_editorskit_reading_time":0,"_editorskit_is_block_options_detached":false,"_editorskit_block_options_position":"{}","inline_featured_image":false,"footnotes":""},"categories":[1320],"tags":[1395,1402,1375,1401,1400],"class_list":["post-9577","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-hard-development","tag-c17-en","tag-constexpr-en","tag-embedded-competency-center-en","tag-parameter-pack-en","tag-templates-en"],"acf":[],"aioseo_notices":[],"republish_history":[],"featured_media_url":"https:\/\/sii.pl\/blog\/wp-content\/uploads\/2020\/07\/embedded-state-machine-3.png","category_names":["Hard development"],"_links":{"self":[{"href":"https:\/\/sii.pl\/blog\/en\/wp-json\/wp\/v2\/posts\/9577"}],"collection":[{"href":"https:\/\/sii.pl\/blog\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/sii.pl\/blog\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/sii.pl\/blog\/en\/wp-json\/wp\/v2\/users\/193"}],"replies":[{"embeddable":true,"href":"https:\/\/sii.pl\/blog\/en\/wp-json\/wp\/v2\/comments?post=9577"}],"version-history":[{"count":2,"href":"https:\/\/sii.pl\/blog\/en\/wp-json\/wp\/v2\/posts\/9577\/revisions"}],"predecessor-version":[{"id":25123,"href":"https:\/\/sii.pl\/blog\/en\/wp-json\/wp\/v2\/posts\/9577\/revisions\/25123"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/sii.pl\/blog\/en\/wp-json\/wp\/v2\/media\/9658"}],"wp:attachment":[{"href":"https:\/\/sii.pl\/blog\/en\/wp-json\/wp\/v2\/media?parent=9577"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/sii.pl\/blog\/en\/wp-json\/wp\/v2\/categories?post=9577"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/sii.pl\/blog\/en\/wp-json\/wp\/v2\/tags?post=9577"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}