Diagnosable validity

Certain combinations of types and expressions can make a C++ program ill-formed. “Ill-formed” is a term taken from the C++ Standard and it means that a program is not valid, and compiler must (in most of the cases) reject it. This is quite obvious:

int main()
{
  auto i = "some text".size(); // invalid expression
};

String literals do not have member functions, therefore compiler cannot accept this program, and must report an error. This puts a responsibility on programmers to learn which expressions and types are valid in a given context and use only these. Again, I am saying a very obvious thing.

What is less obvious is that there is a way in C++ to enter a type or expression of which we do not know if it is valid or not, in an isolated environment, where it does not render the entire program ill-formed, but instead it returns a yes-no (or rather valid-invalid) answer, which we can use at compile-time to make a decision how we want the program to behave. When requested, compiler can analyze all the declarations it has seen so far, and make an approximated judgement whether a given type or expression would make the program ill-formed or not, if used outside the isolated environment. The compiler’s approximated answer is not always correct, but it is just enough most of the time.

Ere we proceed, one question needs to be answered: why would anyone need to ask the compiler whether a given expression is valid or not? Why not just learn from a given type’s declarations or from documentation what interface the type provides, and just use what we have learned is valid? Compiler already informs us about ill-formed programs anyway (by refusing to compile), doesn’t it?

For now, we must go with a short and incomplete answer. When we are defining a class or function template, we are dealing with an ‘unknown’ T which can be anything. For such abstract T we cannot know its full interface in advance, so sometimes we may need to use a tool for querying what this T can do.

Although I tried to make it sound incredible and new, the functionality I am describing is quite old and you have probably used it many a time; e.g., in the form of type traits:

int main()
{
  if (std::is_convertible<int, std::string>::value)
    puts("int converts to string");
  else
    puts("int does not convert to string");
};

The condition inside the if-statement checks whether an int is convertible to std::string, but let’s think for a while what this really means. Imagine a hypothetical declaration:

std::string s = 1;

It might be valid or not. If it is valid, the program that uses it compiles fine and can use variable of type std::string, named s, with some initial value. If it is invalid, the program that uses it is ill-formed, and compiler will refuse to create an executable.

But what type trait does is to define this construct in an isolated environment; or pretend that it does so. In this isolated environment, the construct being invalid does not affect the correctness of the external program. The compiler is able to turn the results of the ‘experiment’ into compile-time constant of type bool which it passes to the program as a member variable named value.

Can you see why I insist on using the term ‘isolated environment’? If there wasn’t one, the above program would have been ill-formed if it tried to convert an int to a std::string to check if this is a valid conversion.

Type traits are not the only way to check if an expression would be invalid if used outside the isolated environment. Here is another:

template <typename T>
auto range_begin(const T& r) -> decltype(r.begin())
{
  return r.begin();
}

Obviously, this defines a function template (a set of overloaded functions) where the returned type is deduced. But this is only a part of the story. This does one more thing. It says more-less this:

When program makes a call to (potentially) overloaded function range_begin, before considering this candidate check (in isolated environment) if expression r.begin() is valid. If it is not, just do not consider this candidate function and proceed to matching others.

Again, we test expression validity. But at no point do we have any variable of type bool that would contain the result of our test. However, word “if” I used in the description indicates that at some point there is a yes-no answer that the compiler makes use of.

This feature of hiding an overload upon failed test in isolated environment is often referred to as sfinae, which is an acronym for “substitution failure is not an error”, which can be further expanded as:

Substitute function argument types for template formal parameters and check if the resulting expression is valid. If not (i.e., if we end in substitution failure) do not make it an ill-formed program (an error) but instead skip to the next overload.

Accuracy

I said before that compiler only gives an approximated answer to the question whether a given expression would be valid or not. Now it is time to expand on this.

In order to determine whether an expression would be valid, compiler only inspects the declarations of functions and classes. It will not instantiate the body of any function template, or generate an implicitly declared function (except for one case explained later). Consider the following example:

struct Rational
{
  int numerator, denominator;

  template <typename I>
  Rational(I i) : numerator(i), denominator(1)
  {
    static_assert(!std::is_floating_point<I>::value,
                  "conversion from floats disallowed");
  }
};

static_assert(std::is_convertible<double, Rational>::value,
              "not convertible");

Rational r = 1.5;

This is a similar problem to the one described in this post.

We provide a converting constructor from any type. But later, using static_assert we make the program ill-formed, if someone wants to use this constructor to convert a floating-point type to Rational.

When we use type trait is_convertible to check if the conversion from double to Rational works, in line 13, the trait returns true (the conversion works). But if we later try to use it in line 16, we get a compile-time error: “conversion from floats disallowed”.

This is because the mechanism for testing validity only looks at function signatures: whether such function is declared, whether it is not private, whether it is not deleted or sfinaed away. But it does not peek into the function’s body.

So, not only is it important to turn certain bugs into compile-time errors, but also it is important which technique you use to trigger a compile-time error. This post suggests another solution for turning the erroneous usage of the constructor into a compile-time error:

# define REQUIRES(...) \
  std::enable_if_t<(__VA_ARGS__), int> = 0

struct Rational
{
  int numerator, denominator;

  template <typename I,
            REQUIRES (!std::is_floating_point<I>::value)>
  Rational(I i)
   : numerator(i), denominator(1)
  {}
};

static_assert(!std::is_convertible<double, Rational>::value,
              "unintentionally convertible");

The difference is that now the code responsible for rendering some constructor usages invalid is moved from function’s body to its signature, and this way it is made accessible to validity testing mechanism. The only downside now is that unlike with static_assert we are not in control of what error message is displayed to the programmer.

We skip the description of how macro REQUIRES works. But for the purpose of this post it should suffice to say that it obtains a compile-time constant of type bool, and if the value is false it renders the function’s signature invalid in a way that is detectable to the validity testing mechanism — it sfinaes the function away.

There is also a second ‘imperfection’ in the validity testing mechanism. The environment in which we test for validity is not perfectly isolated, and sometimes forming an invalid type or an expression inside may in fact end up in the entire program being ill-formed. This may happen when in the process of determining the validity of language constructs, compiler needs to instantiate a class template or a function template and an invalid type or expression is formed during this instantiation.

This can be illustrated with the following example:

template <typename T>
struct tool_helper : T {};

struct tool_x
{
  tool_x(long) {};

  template <typename T,
            typename U = typename tool_helper<T>::type> 
    tool_x(T, U = {}) {};
};

Class tool_x has two converting constructors. The first is quite simple, it just takes a long int. The second is tricky, it is a template, so it looks it might work for conversions from any type, but in fact it relies on the existence of the nested dependent type tool_helper<T>::type, which can only be checked by instantiating class template tool_helper<T>, which inherits from T. Since you cannot inherit from a built-in type, calling this constructor is invalid for built-in types.

Now, if we try to test the validity:

if (std::is_convertible<int, tool_x>::value)
  puts("conversion");
else
  puts("no conversion");

We get a compiler error: the entire program is ill-formed. This is what happens. Compiler sees the converting constructor from long int. Technically, it could use it for conversion from plain int, but it has to look for a better match. It tries to check the constructor template, but in order to do this it has to instantiate class template specialization tool_helper<int>. This instantiation fails (you cannot inherit from int), and errors in class template instantiation ‘propagate’ across the isolation layer.

This is the nature of the contract between C++ compiler writers, and their users. Compiler vendors are not forced to maintain the ‘stack’ of class/function template instantiations, and be able to get back to any past state. This would make their job too difficult, and compile times even slower.

If we change the second constructor a bit:

struct tool_x
{
  tool_x(long) {};

  template <typename T,
            typename U = tool_helper<T>> 
    tool_x(T, U = {}) {};
};

The result becomes dependent on the compiler you are using. On MSVC the above program compiles fine, and the type trait returns true (you can convert from int to tool_x). But if you try to actually perform the conversion, you get an ill-formed program. So, the behavior is similar as this with class Rational.

On GCC and Clang, the above test still results in compile-time failure. Interestingly, on these compilers, if we test the convertibility from long int in the last example, there is no error:

static_assert(std::is_convertible<long, tool_x>::value, "");

I suppose, this is because having seen the constructor taking long the compiler can be certain it will not find a better match, and can be relieved of inspecting the other candidates, which can only be worse.

Now, given that MSVC and GCC/Clang display different behaviors, you might ask which compiler is correct. In fact, they both are. The Standard gives a provision to compiler vendors: only the “immediate context” of language constructs is considered; but what constitutes an “immediate context” is not specified. In most situations, it is quite obvious what should be treated as immediate context, but the last case above is controversial. Checking the validity of the second constructor does not really require instantiating template tool_helper with type int, so only building type tool_helper<int> looks fine. Of course trying to instantiate it would fail, but compilers are not forced to do it for the purpose of determining the validity unless this failure is in the “immediate context”. Apparently MSVC chooses the interpretation that what the class derives from is not in the immediate context, whereas GCC and clang assume the opposite.

Thus, a validity test can render an ill-formed program or return a false positive. It never returns a false negative, unless we consider the following case:

class A
{
  A(int);
  friend class B;
};

class B
{
  void test() {
    static_assert(!std::is_convertible<int, A>::value,
                  "unintentionally convertible");
    A a = 1;
  }
};

But this is a bit unfair because, by contract, validity tests only check validity in the context external to any friend declarations.

Now, I said the similar isolation breakage applies when a function template is instantiated; but earlier I had said that the validity testing does not try to instantiate function template bodies. There is one exception: this is when we need to deduce the function’s return type from its body.

Let’s illustrate it with an example. But this will not be observable in MSVC (which does not fully support expression-based sfinae). Suppose we want to define a free-standing function that returns the begin-iterator for any STL container:

// overload (1)
template <typename T>
auto range_begin(T&& r) // deduce return type (C++14)
{
  return std::forward<T>(r).begin();
}

This is supposed to return an iterator-to-const when we bind to a constant range, and iterator-to-non-const when we bind to a mutable range. The usage of std::forward is not necessary for STL ranges, but in case a user-defined range provides an overload of begin() for rvalue reference ranges, we want to make use of it too.

This looks like a good candidate for type inference. We do not want to waste time typing the return type, which is obvious both to us and the compiler. Now, this does not work for raw arrays, so we add dedicated overloads:

// overload (2)
template <typename T, int N>
auto range_begin(T (&a) [N]) -> T*
{
  return a;
}

// overload (3)
template <typename T, int N>
auto range_begin(const T (&a) [N]) -> const T*
{
  return a;
}

Now, let’s try to use this overload set:

struct tool_y
{
  std::string name = "y";
  int range[2] = {0, 1};
};

int main()
{
  tool_y t;
  tool_y const ct;

  range_begin(t.name);         // picks (1)
  range_begin(t.range);        // picks (2)
  range_begin(ct.name);        // picks (1)
  range_begin(ct.range);       // picks (3)
  range_begin(tool_y{}.range); // ERROR!
}

So, sometimes we get a hard error. First, let’s analyze why this works fine in line 13. Overload selection determines that overload (2) is an ideal match when int is substituted for T. Therefore it has no reason to make substitutions to determine the return type of overload (1), which can only be worse.

In line 16 however, because we get an rvalue array, overload (3) is a viable candidate, but not an ideal one, and overload (1) may be a better one; however, in order to determine its return type, we have to instantiate the body of the function template, and this instantiation renders an invalid expression. In turn, invalid expression in function template instantiation propagates outside the isolated environment, and we get an ill-formed program.

Now, if we replace overload (1) with the following one:

// overload (1*)
template <typename T>
auto range_begin(T&& r) 
  -> decltype(std::forward<T>(r).begin())
{
  return std::forward<T>(r).begin();
}

Our test works fine:

int main()
{
  tool_y t;
  tool_y const ct;

  range_begin(t.name);         // picks (1*)
  range_begin(t.range);        // picks (2)
  range_begin(ct.name);        // picks (1*)
  range_begin(ct.range);       // picks (3)
  range_begin(tool_y{}.range); // picks (3)
}

The difference stems from the fact that now the invalid expression has been moved from the function’s body to its signature. When selecting the best overload, overload (1*) can be safely ignored, and overload (3) — not an ideal one, but still viable — selected.

Thus, we can see that there is more to letting the function’s return type be deduced, than just less typing. Declarations (1) and (1*) mean different things. And it still makes sense to have a helper macro like this one:

# define RETURNS(...) \
  -> decltype(__VA_ARGS__) { return __VA_ARGS__; }

Because declaration:

template <typename T>
auto range_begin(T&& r) RETURNS( std::forward<T>(r).begin() );

Is superior both to overload (1) (no hard errors) and overload (1*) (no repetition).

Thus we covered invalid constructs inside class templates and function template bodies. In C++ we have two other kinds of templates: alias templates and variable templates.

I will not go into variable templates, and will only say one remark: it is an unexplored land — both by programmers and people who create the Standard — so I recommend against relying on what it does in validity testing.

Regarding alias templates, the situation is quite clear. In one of the above examples we used a Standard Library component std::enable_if_t. This is an alias template defined as follows:

template <bool b, class T = void>
using enable_if_t = typename enable_if<b, T>::type;

The mechanism that makes enable_if work is based on having or not having the nested type type defined based on condition b. In other words, dependent type typename enable_if<b, T>::type is valid or not. Now the purpose of alias template std::enable_if_t is to make the idiom shorter; and obviously, it is meant still to work. Therefore, forming an invalid type inside an alias template definition has to be, and is, detectable in validity testing. Otherwise, there would be no point in adding features like enable_if_t into the Standard Library.

Is this all true?

So, where is this all defined in the Standard? Interestingly, it is defined only partially. The Standard does not say precisely when validity testing is not accurate. It only uses an undefined term “immediate context” and offers an informal text (a note) saying:

Only the validity of the immediate context of the expression is considered. [Note: The compilation of the expression can result in side effects such as the instantiation of class template specializations and function template specializations, the generation of implicitly-defined functions, and so on. Such side effects are not in the “immediate context” and can result in the program being ill-formed. —end note]

So, the Standard taken formally in this case is not a reliable source of information. Instead, as a source of information, I take the following. The sole existence of Standard Library entities like is_convertible_if, enable_if, enable_if_t reveals the intention of the Standard. Also, experiments with GCC, Clang, MSVC confirm this. Another source of information are statements by people who actually create the Standard, who can say about the intentions and directions of the language.

100% accurate validity testing?

We know Concepts Lite can be used for a similar purpose: testing if certain language constructs are valid, and using the outcome to do branching (displaying error messages, or selecting appropriate overloads). Are they a superior alternative to what we have seen so far in terms of test accuracy?

While Concepts Lite offer many advantages over type traits or sfinae-based solution, they suffer from the same accuracy problems. They do not peek into function template bodies to see the assertions, and in complex cases testing for a concept match may result in a hard error. For a code example, see here.

One other reason to check the validity of en expression is while unit-testing. Sometimes it is a feature of our library, that it triggers a compile-time error when someone tries to use it incorrectly. We have seen an example above, with class Rational. We should test if our safety feature works. In such cases we may need something more reliable than validity testing feature. We may need a 100% accuracy. There is no way to check it from within C++, and there is not going to be any: it has been clearly laid out, that compiler vendors cannot be forced to implement a “speculative compilation” and backtracking from arbitrarily deep template instantiation failures.

A practical way to check if a given construct fails to compile is to do it from outside C++: prepare a small test program with erroneous construct, compile it, and test if compiler reports compilation failure. This is how “negative” unit tests work with Boost.Build. For an example, see this negative test form Boost.Optional library: optional_test_fail_convert_from_null.cpp. In configuration file it is annotated as compile-fail, meaning that test passes only if compilation fails.

Acknowledgements

I am grateful to a number of people who devoted their time to lay out the various details of C++ validity testing mechanism to me; in particular, Tomasz Kamiński and Richard Smith.