Why do we care about compile-time programming?

Constant initialization

// Lookup table for e^i with i in [0, 1000]
constexpr std::array<double, 1001> exps = compute_exp(0, 1000);

int main() {
  int i = read_from_user();
  std::cout << exps[i] << '\n';
  return 0;
}

Boilerplate reduction

enum class Color { RED, GREEN, BLUE, YELLOW, PURPLE };

std::ostream& operator<<(std::ostream& out, Color color) {
  switch (color) {
    case Color::RED:    out << "RED";    break;
    case Color::GREEN:  out << "GREEN";  break;
    case Color::BLUE:   out << "BLUE";   break;
    case Color::YELLOW: out << "YELLOW"; break;
    case Color::PURPLE: out << "PURPLE"; break;
  }
  return out;
}

int main() {
  Color color = read_from_user();
  std::cout << color << '\n';
  return 0;
}

Solving these problems used to be a nerdy topic

Now all the cool kids are on it

• The Reflection TS: wg21.link/n4746
• Standard containers and constexpr: p0784
• Making std::vector constexpr: p1004
• Making <algorithm> constexpr: p0202 & al
• std::is_constant_evaluated(): p0595
• constexpr! functions: p1073
• Metaclasses: p0707
• Value-based reflection: p0993
• Calling virtual functions in constexpr: p1064
• try-catch in constexpr: p1002

This can be difficult to follow

Even committee members are confused

So, what's the plan?

1. Make (almost) all of C++ available in constexpr
2. Provide a constexpr API to query the compiler
3. Provide a means for modifying the AST

Step 1: Expanding constexpr

Necessary in order to use non-trivial data structures and execute non-trivial logic at compile-time.

In C++11, constexpr was very limited

constexpr std::size_t count_lower(char const* s,
                                  std::size_t count = 0)
{
  return *s == '\0' ? count
                    : 'a' <= *s && *s <= 'z'
                        ? count_lower(s+1, count + 1)
                        : count_lower(s+1, count);
}

static_assert(count_lower("aBCdeF") == 3, "");

In C++14, many restrictions lifted

constexpr std::size_t count_lower(char const* s) {
  std::size_t count = 0;
  for (; *s != '\0'; ++s) {
    if ('a' <= *s && *s <= 'z') {
      ++count;
    }
  }
  return count;
}

static_assert(count_lower("aBCdeF") == 3, "");

In C++17, constexpr is still limited

• No allocations
• No try-catch
• No virtual calls
• No reinterpret_cast

This means we can't use variable-size containers

template <typename Predicate>
constexpr std::vector<int>
keep_if(int const* it, int const* last, Predicate pred) {
  std::vector<int> result;
  for (; it != last; ++it) {
    if (pred(*it)) {
      result.push_back(*it);
    }
  }
  return result;
}

constexpr int ints[] = {1, 2, 3, 4, 5, 6};
constexpr std::vector<int> odds =
                      keep_if(begin(ints), end(ints), is_odd);
// doesn't work!

We have to use fixed-size arrays, which is painful

template <std::size_t K, typename Predicate>
constexpr std::array<int, K>
keep_if(int const* it, int const* last, Predicate pred) {
  std::array<int, K> result;
  int* out = begin(result);
  for (; it != last; ++it) {
    if (pred(*it)) {
      *out++ = *it;
    }
  }
  return result;
}

constexpr int ints[] = {1, 2, 3, 4, 5, 6};
constexpr std::array<int, 3> odds =
                      keep_if<3>(begin(ints), end(ints), is_odd);

constexpr algorithms don't compose well

Enter p0784

More constexpr containers

• Enables new-expressions in constexpr
• Makes std::allocator usable in constexpr
• Promotes some constexpr objects to static storage

The following becomes valid

constexpr int* square(int* first, int* last) {
  std::size_t N = last - first;
  int* result = new int[N]; // <== HERE
  for (std::size_t i = 0; i != N; ++i, ++first) {
    result[i] = *first * *first;
  }
  return result;
}

constexpr void hello() {
  int ints[] = {1, 2, 3, 4, 5};
  int* squared = square(std::begin(ints), std::end(ints));
  delete[] squared;
}

Obvious next step

Make std::vector constexpr

But std::vector uses try-catch

So make try-catch constexpr!

Enter p1002

Try-catch blocks in constexpr functions

template <std::size_t N>
constexpr std::array<int, N>
square(std::array<int, N> array, int from, int to) {
  try {
    for (; from != to; ++from) {
      array.at(from) = array.at(from) * array.at(from);
    }
  } catch (std::out_of_range const& e) {
    // ...
  }
  return array;
}

constexpr auto OK     = square(std::array{1, 2, 3, 4}, 0, 4);
constexpr auto NOT_OK = square(std::array{1, 2, 3, 4}, 0, 10);

But it's not as cool as you think

throw is still not allowed

Line 14 works because we never execute a throw statement:

template <std::size_t N>
constexpr std::array<int, N>
square(std::array<int, N> array, int from, int to) {
  try {
    for (; from != to; ++from) {
      array.at(from) = array.at(from) * array.at(from);
    }
  } catch (std::out_of_range const& e) {
    // ...
  }
  return array;
}

constexpr auto OK     = square(std::array{1, 2, 3, 4}, 0, 4);
constexpr auto NOT_OK = square(std::array{1, 2, 3, 4}, 0, 10);

Line 15 fails when we execute the throw inside array::at:

template <class T, std::size_t Size>
constexpr typename array<T, Size>::reference
array<T, Size>::at(std::size_t n) {
  if (n >= Size)
    throw std::out_of_range("array::at"); // compilation error here

  return elements_[n];
}

In the future, we can extend the language

Back to std::vector

In C++20, this will just work:

template <typename Predicate>
constexpr std::vector<int>
keep_if(int const* it, int const* last, Predicate pred) {
  std::vector<int> result;
  for (; it != last; ++it) {
    if (pred(*it)) {
      result.push_back(*it);
    }
  }
  return result;
}

constexpr std::vector<int> ints = {1, 2, 3, 4, 5, 6};
constexpr std::vector<int> odds =
                      keep_if(begin(ints), end(ints), is_odd);

Promotion to static storage

Also called non-transient allocations

What happens with this code?

Where is table stored?

constexpr std::vector<int> table = compute_table();

int main(int argc, char* argv[]) {
  int from = std::atoi(argv[1]);
  int to = std::atoi(argv[2]);
  for (; from != to; ++from) {
    std::cout << table[from] << '\n';
  }
}

Answer: promoted to static storage

• If a constexpr object "leaks" from compile-time
• And its destructor would clean up if it were called
• Then it is promoted to static storage

That's really nothing new

Here, table will be in the data segment

constexpr std::array<int, 4> table = {1, 2, 3, 4};

int main(int argc, char* argv[]) {
  int from = std::atoi(argv[1]);
  int to = std::atoi(argv[2]);
  for (; from != to; ++from) {
    std::cout << table[from] << '\n';
  }
}

If executing the destructor would not clean up, then it's not a constant expression

Corollary

If you can evaluate a function call in a constant expression, then that function call is leak-free for the provided inputs.

The compiler turns into a leak detector 😏

Future constexpr additions

• std::string
• std::map and std::unordered_map
• std::optional/std::variant?
• Math functions?
• std::thread (multithreaded compilation) 🤕
• Almost everything? Join the effort!

Challenges

• reinterpret_cast (e.g. std::string SBO)
• non-constexpr builtins (e.g. __builtin_memcpy)
• Raw memory allocation (e.g. malloc)
• Other annotations (e.g. UBSan in libc++)

Enter p0595

• Adds std::is_constant_evaluated()
• Allows detecting whether the current function is evaluated as part of a constant expression

For example

template <typename T>
void vector<T>::clear() noexcept {
  size_t old_size = size();
  // destroy [begin(), end())
  __annotate_shrink(old_size); // ASAN annotation
  __invalidate_all_iterators(); // Debug mode checks
}

Making this constexpr

template <typename T>
constexpr void vector<T>::clear() noexcept {
  size_t old_size = size();
  // destroy [begin(), end())
  if (!std::is_constant_evaluated()) {
    __annotate_shrink(old_size); // ASAN annotation
    __invalidate_all_iterators(); // Debug mode checks
  }
}

How this works

constexpr int f() {
  std::vector<int> v = {1, 2, 3};
  v.clear();
  return 0;
}

int main() {
  // is_constant_evaluated() true, no annotations
  constexpr int X = f();

  // is_constant_evaluated() false, normal runtime code
  int Y = f();
}

Another common problem

constexpr does not require compile-time evaluation

Enter constexpr! (p1073)

constexpr! int square(int x) {
  return x * x;
}

constexpr int x = square(3); // OK

int y = 3;
int z = square(y); // ERROR: square(y) is not a constant expression

Summary of constexpr changes

• Expand constexpr to support more use cases
• Allow persisting data structures to the data segment
• Allow writing different code for constexpr and runtime when needed
• Require compile-time evaluation with constexpr!

Step 2: an API to speak to the compiler

Basically, extract information about types

We can already do some of it

type_traits, operators like sizeof

struct Foo {
  int x;
  int y;
};

constexpr std::size_t size = sizeof(Foo);
constexpr bool is_aggregate = std::is_aggregate_v<Foo>;

But we're severely limited

Currently, limited to queries whose answer is a primitive type

struct Foo {
  int x;
  int y;
};

constexpr auto members = ???; // list of Foo's members

Enter the Reflection TS: n4746

Purpose:

• Figure out what this query API should look like
• Not the specific implementation of this API
• For now, the API uses template metaprogramming

Example: extracting members

struct Foo {
  int x;
  long y;
};

using MetaFoo = reflexpr(Foo);
using Members = std::reflect::get_data_members_t<MetaFoo>;

using MetaX = std::reflect::get_element_t<0, Members>; // Not an int!
constexpr bool is_public = std::reflect::is_public_v<MetaX>;

using X = std::reflect::get_reflected_type_t<MetaX>; // This is int!

Another example: printing an enum

enum class Color { RED, GREEN, BLUE, YELLOW, PURPLE };

std::ostream& operator<<(std::ostream& out, Color color) {
  using Enumerators = std::reflect::get_enumerators_t<reflexpr(Color)>;
  auto helper = [&]<std::size_t ...i>(std::index_sequence<i...>) {
    ([&] {
      using Enumerator = std::reflect::get_element_t<i, Enumerators>;
      if (color == std::reflect::get_constant_v<Enumerator>) {
        out << std::reflect::get_name_v<Enumerator>;
      }
    }(), ...);
  };

  constexpr std::size_t N = std::reflect::get_size_v<Enumerators>;
  helper(std::make_index_sequence<N>{});
  return out;
}

Other features:

• Get source line/column of a type definition
• Get the name of an entity as a string
• Get member types/enums/etc of a type
• Get base classes of a type
• Get whether variable is static/constexpr
• Get properties of base classes: virtual/public/etc

More features planned in the future

• Reflecting functions: p0670
• Plans to reflect on arbitrary expressions too!!!

Final syntax not settled yet: p0953

struct Foo {
  int x;
  long y;
};

constexpr std::reflect::Record meta_foo = reflexpr(Foo);
constexpr std::vector members = meta_foo.get_data_members();

constexpr std::reflect::RecordMember meta_x = members[0];
constexpr bool is_public = meta_x.is_public();
constexpr std::reflect::Type x = meta_x.get_reflected_type();

using X = unreflexpr(x); // This is int!

Another example: print an enum

enum class Color { RED, GREEN, BLUE, YELLOW, PURPLE };

std::ostream& operator<<(std::ostream& out, Color color) {
  constexpr std::vector enumerators = reflexpr(Color).get_enumerators();
  for... (constexpr std::reflect::Enumerator enumerator : enumerators) {
    if (color == enumerator.get_constant()) {
      out << enumerator.get_name();
    }
  }
  return out;
}

for...? P0589

std::ostream& operator<<(std::ostream& out, Color color) {
  constexpr std::vector enumerators = reflexpr(Color).get_enumerators();
  for... (constexpr std::reflect::Enumerator enumerator : enumerators) {
    if (color == enumerator.get_constant()) {
      out << enumerator.get_name();
    }
  }
  return out;
}

Expands roughly to

std::ostream& operator<<(std::ostream& out, Color color) {
  constexpr std::vector enumerators = reflexpr(Color).get_enumerators();
  {
    constexpr std::reflect::Enumerator enumerator = enumerators[0];
    if (color == enumerator.get_constant()) {
      out << enumerator.get_name();
    }
  }
  {
    constexpr std::reflect::Enumerator enumerator = enumerators[1];
    if (color == enumerator.get_constant()) {
      out << enumerator.get_name();
    }
  }
  // ...
  return out;
}

Status of reflection

1. Reflection TS figures out the compiler query API
2. Will rebase on top of the constexpr work
3. Aim is to write normal-looking C++ code

Step 3: Code injection

Alternatives considered in p0633

1. Raw string injection
2. Programmatic API
3. Token-sequence injection

Illustration: creating interfaces

struct Shape {
  int area() const;
  void scale_by(double factor);
};

Should magically transform to

struct Shape {
  virtual int area() const = 0;
  virtual void scale_by(double factor) = 0;
  virtual ~Shape() noexcept { }
};

Define the transformation

constexpr! void interface(std::reflect::Type source) {
  for (auto f : source.functions()) {
    if (!f.has_access())
      f.make_public();
    f.make_pure_virtual();
    -> f;
  }

  -> class C {
    virtual ~C() noexcept { }
  };
}

Apply the transformation

struct Shape {
  int area() const;
  void scale_by(double factor);
};

class IShape {
  constexpr {
    interface(reflexpr(Shape));
  }
};

What about metaclasses (p0707)?

They can be built on top of code injection

class(interface) IShape {
  int area() const;
  void scale_by(double factor);
};

Desugars roughly to

class IShape {
  class __IShape {
    int area() const;
    void scale_by(double factor);
  };
  constexpr { interface(reflexpr(__IShape)); }
};

Status of code injection

• Provide a way to influence the AST
• Exact means not settled yet
• Should interact well with constexpr control flow
• Metaclasses can be built on top

What can we hope for?

This is just my optimistic prediction, not a promise!

C++20

• More constexpr:
  • std::vector, std::string, std::map
  • language features required by those
• <experimental/reflect> (syntax TBD)

C++23

• Even more constexpr: where do we stop?
• Some code injection mechanism
• <reflect> based on constexpr

This will change the face of C++

This opens endless possibilities

• For incredible libraries
• For code reuse
• For interoperation with other languages
• To shoot oneself in the foot

With great power comes...

Lots of fun!!!

Acknowledgments

Thank you

Louis Dionne <@LouisDionne>

C++ Standard Library Engineer @ Apple