Concept archetypes — update

An observant reader indicated that in the previous post where I was trying to implement a concept archetype — a type with minimal interface that models a given concept — I actually failed. This deserves a closer examination.

Let’s recall. We have the following concept:

template <typename T>
concept Addable = 
  std::regular<T> &&
  std::totally_ordered<T> &&
  requires(T x, T y) {
    { x += y } -> std::same_as<T&>;
    { x +  y } -> std::convertible_to<T>;
  }; 

and we have the following type that we believe to be an archetype for the concept:

class A
{
  struct Rslt { 
    operator A() { return {}; } 
  };
 
public:
  A() = default;
  A(A&&) = default;
  A(A const&) = default;
  A& operator=(A &&) = default;
  A& operator=(A const&) = default;
  ~A() = default;
     
  void operator&() const = delete;
  friend void operator,(A const&, A const&) = delete;
 
  A& operator+=(A const&) { return *this; }
  friend Rslt operator+(A const&, A const&) { return {}; }
   
  friend auto operator<=>(A const&, A const&) = default;
};

The thing to note is the usage of intermediate type A::Rslt that attempts to reflect that the result of adding two A's does not have to be another A but just something convertible to it.

Now imagine that our generic function sum() that uses our concept as a constraint is implemented slightly different than in the previous post:

template <typename T>
auto sum_impl(T a, T b)
{
  assert (a >= b);
  auto r = a + b;
  return r;
}
 
template <Addable T>
T sum(T a, T b)
{
  if (b > a) 
    return sum_impl(b, a);
  else
    return sum_impl(a, b);
}

The difference now is that rather than immediately converting the result of operator+ to T, we return exactly the type produced. Testing it against the archetype reveals no problem. The following compiles fine:

inline void test_concept_usage(A a, A b)
{
  sum(a, b);
}

But now imagine the following user defined type which uses expression-template-style signature for operator+:

struct Num
{
  int i;
  friend auto operator<=>(Num, Num) = default;

  Num& operator+=(Num const& n) { 
    i += n.i; 
    return *this; 
  }
};

struct NumAddExpr
{
  Num const& lhs;
  Num const& rhs;

  operator Num() { 
    return Num{lhs} += rhs; 
  }
    
  NumAddExpr(Num const& x, Num const& y)
   : lhs{x}, rhs{y} {}

  NumAddExpr(NumAddExpr&&) = delete;
};

NumAddExpr operator+(Num const& x, Num const& y)
{
  return {x, y}; 
}

static_assert(Addable<Num>);

Declaring move constructor as deleted also declares all special member constructors and assignments as deleted, so the only use that can be made of NumAddExpr is to convert it to Num. The static assertion in the last line demonstrates that type Num satisfies the concept.

So, let’s use it:

int main()
{
  sum(Num{1}, Num{2});  
}

And now we get the ugly error message resulting from template instantiation: function template sum_impl() which was supposed to be an implementation detail.

Why did our archetype not detect it? Because the concept only required that the result of the addition is convertible to T, whereas the archetype additionally makes this type std::semiregular by providing implicitly declared constructors and assignments. A more decent archetype should look like this:

class A
{
  struct Rslt { 
    operator A() { return {}; } 
    Rslt(Rslt&&) = delete;
    void operator&() const = delete;
    friend void operator,(Rslt, Rslt) = delete;
  };
    
  static Rslt make() { throw 0; }
 
public:
  A() = default;
  A(A&&) = default;
  A(A const&) = default;
  A& operator=(A &&) = default;
  A& operator=(A const&) = default;
  ~A() = default;
     
  void operator&() const = delete;
  friend void operator,(A const&, A const&) = delete;
 
  A& operator+=(A const&) { return *this; }
  friend Rslt operator+(A, A) { return make(); }
   
  friend auto operator<=>(A const&, A const&) = default;
};

The observation here — as indicated by the reader who reported this — is that associated types that we model (like Rslt) in our archetype are subject to the same rule as the archetype itself: declare all special member functions as deleted.

Now, is this refined version a really minimum interface that models the concept? After this exercise, I would not dare to answer this question with certainty. For instance, our concept only requires that expression a + b for operands of type T is well defined (possibly including conversions) but does not require that in the signature of the operator the types are exactly T; whereas our archetype has exactly T. It is possible to imagine a contrived implementation of an algorithm that works with our archetype but not with sufficiently contorted user-defined type.

My observation here is that making sure that the archetype has really the minimum interface is a manual job, and it is difficult. But even if the archetype is not 100% minimum, it can still help us detect many bugs early in the development cycle.

I would like to thank Marcel Krüger for pointing out this issue in the previous post.