Why is this nested lambda not considered constexpr?

Question

I'm trying to create a curried interface using nested constexpr lambdas, but the compiler does not consider it to be a constant expression.

namespace hana = boost::hana;
using namespace hana::literals;

struct C1 {};

template < typename T,
           std::size_t size >
struct Array {};

constexpr auto array_ = [] (auto size) {
      return [=] (auto type) {
        return hana::type_c<Array<typename decltype(type)::type, size()>>;
      };
    };

int main() {

  constexpr auto c1 = hana::type_c<C1>;
  constexpr auto test = hana::type_c<Array<typename decltype(c1)::type, hana::size_c<100>()>>;
  constexpr auto test2 = array_(hana::size_c<100>)(c1);
}

I post a question earlier because I found a different minimal example, but it wasn't enough.

Error:

test2.cpp: In instantiation of ‘<lambda(auto:1)>::<lambda(auto:2)> [with auto:2 = boost::hana::type_impl<C1>::_; auto:1 = boost::hana::integral_constant<long unsigned int, 100>]’:
test2.cpp:31:54:   required from here
test2.cpp:20:16: error: ‘__closure’ is not a constant expression
         return hana::type_c<Array<typename decltype(type)::type, size()>>;
                ^~~~
test2.cpp:20:16: note: in template argument for type ‘long unsigned int’ 
test2.cpp: In function ‘int main()’:
test2.cpp:31:18: error: ‘constexpr const void test2’ has incomplete type
   constexpr auto test2 = array_(hana::size_c<100>)(c1);

__closure is not a constant expression : if someone could explain me this error that would be a great help. I ran into that error before but can't remember why.

Answer 1

I reduced your test case to this:

#include <type_traits>

constexpr auto f = [](auto size) {
  return [=](){
    constexpr auto s = size();
    return 1;
  };
};

static_assert(f(std::integral_constant<int, 100>{})(), "");

int main() { }

As said in the comments above, this happens because size is not a constant expression from within the function body. This is not specific to Hana. As a workaround, you can use

constexpr auto f = [](auto size) {
  return [=](){
    constexpr auto s = decltype(size)::value;
    return 1;
  };
};

or anything similar.

Answer 2

The problem is you are trying to odr-use one of a lambda's captured variables in a template non-type argument.

  return hana::type_c<Array<typename decltype(type)::type, size()>>;
//                                                         ^~~~

A template non-type argument must be a constant expression. Inside a lambda, you can't odr-use a captured variable in a constant expression. Whether or not the lambda is constexpr is irrelevant.

But you can odr-use ordinary variables in constant expressions, even if they are not constexpr variables. For example, this is legal:

std::integral_constant<int, 100> i; // i is not constexpr
std::array<int, i()> a; // using i in a constant expression

So why can't we odr-use captured variables in constant expressions? I don't know the motivation for this rule, but here it is in the standard:

[expr.const]

(¶2) A conditional-expression is a core constant expression unless... (¶2.11) in a lambda-expression, a reference to this or to a variable with automatic storage duration defined outside that lambda-expression, where the reference would be an odr-use.

CWG1613 may hold some clue.

If we were to rewrite the inner lambda as a named class, we would have a different but related problem:

template <typename T>
struct Closure {
  T size;
  constexpr Closure(T size_) : size(size_) {}

  template <typename U>
  constexpr auto operator()(U type) const {
    return hana::type_c<Array<typename decltype(type)::type, size()>>;
  }
};
constexpr auto array_ = [] (auto size) {
  return Closure { size };
};

Now the error would be the implicit use of the this pointer in a template non-type argument.

  return hana::type_c<Array<typename decltype(type)::type, size()>>;
//                                                         ^~~~~

I declared Closure::operator()() as a constexpr function for consistency, but that is immaterial. The this pointer is forbidden to be used in a constant expression ([expr.const] ¶2.1). Functions declared constexpr do not get special dispensation to relax the rules for the constant expressions that may appear within them.

Now the original error makes a little bit more sense, because captured variables are transformed into data members of the lambda's closure type, so using captured variables is a little bit like indirecting through the lambda's own "this pointer".

This is the workaround that introduces the least alteration to the code:

constexpr auto array_ = [] (auto size) {
  return [=] (auto type) {
    const auto size_ = size;
    return hana::type_c<Array<typename decltype(type)::type, size_()>>;
  };
};

Now we are using the captured variable outside of a constant expression, to initialize an ordinary variable which we can then use in the template non-type argument.

This answer has been edited a few times, so the comments below may reference previous revisions.