Should Concepts be Friendly?

The concepts proposals that have come out of Indiana have had the notion of “concept friends” and “concept map friends”, which allow classes to declare concepts or concept maps as friends. Although the feature has never been implemented in ConceptGCC, it’s intent and use were obvious: if you wanted to write a concept map for a particular concept, but that concept map required access to some of the private members of the class, one would use a concept map friend. It’s easy to construct an example where this seems plausible:

concept Vector<typename T> {
  typename scalar;
  int length(const T&);
  scalar& operator[](T&, int);
  // ...
};

// A class for complex numbers
template<typename T>
class complex {
public:
  // ...
  T real() const;
  void set_real(T x);
  T imag() const;
  void set_imag(T x);

private:
  T real_;
  T imag_;

  friend concept_map Vector<complex<T> >;
};

// Make an std::complex into a Vector
template<typename T>
concept_map Vector<complex<T> > {
  typedef T scalar;
  int length(const complex<T>&) { return 2; }
  T& operator[](complex<T>& c, int i) {
    return i == 0? c.real_ : c.imag_;
  }
};
      

In this example, the author of complex<T> chose to provide accessors to the real and imaginary parts of the complex number, but there is no way in the public interface to get a true reference to the underlying variables. However, the Vector concept requires access to the values through an actual reference. Concept map friends save the day, by allowing the concept map to access the private members of complex, thereby exposing the references.

Was this the right solution? I don’t know. One could make the case that this complex template really doesn’t meet the requirements of the Vector concept, because the author chose to hide the implementation details for a reason (e.g., they may change). Introducing the concept friend is really a hack that exposes more implementation details of complex, but without making those implementations part of the public interface. Granted, this is a general argument against friends, which do have their uses. What about this particular use?

Another way to consider whether concept map friends were the right solution here is to think of the multi-author, multi-library case. It’s likely that Vector was written for a particular library, then complex was written for a different library by a different programmer. Now, a third person, integrating those two libraries, needs to make a complex model Vector. Unfortunately, this third person can’t make this happen without modifying the definition of complex to introduce a new concept friend declaration. In other words, concept friends do not permit truly retroactive modeling. To do that, we would need to be able to declare friendly outside of the class definition, but such a feature completely breaks encapsulation. Thus, there are at least four ways we could go with concept (map) friends:

1. Eliminate them entirely, because we don’t believe that they are really necessary or are not sufficiently useful to warrant specifying and implementing them.
2. Allow them only in class definitions, so that we can break encapsulation in small ways when we need to, just like we can with classes and templates today.
3. Allow them anywhere, so that we could break encapsulation when needed. However, this means that encapsulation wouldn’t really exist at all, since it would be so easy to break.
4. Eliminate access checking within concept maps, allowing any concept map to access the private members of any class. This makes concept maps somehow “special”, because they have access to everything, but solves the problem with a minimum specification burden.

Implicit Assignments and Construction

What kind of iterator is std::map<int, int>::iterator? It’s a bidirectional iterator, of course, but is it mutable or constant? With the common sequence containers having mutable iterators and constant const_iterators, it’s easy to forget that the value type of a std::map<int, int> is actually a std::pair<const int, int>. It’s that const that causes the trouble, because it means that std::pair<const int, int> is not Assignable, and therefore map’s iterators don’t meet the requirements of a Mutable Bidirectional Iterator. While this may be interesting trivia for your next C++ interview, why does it matter for ConceptGCC?

It matters for ConceptGCC because we originally got it wrong, and wrote a concept map like this:

template<typename Val>
  concept_map MutableBidirectionalIterator<_Rb_tree_iterator<Val> > { };
      

_Rb_tree_iterator is a secret iterator type used by libstdc++ to implement iterators into the red-black tree that underlies the set and map containers. The big problem here is that ConceptGCC accepted the concept map, and even instantiated it. However, doing so resulted in a harmful fallacy: ConceptGCC generated a concept map for Assignable<std::pair<const int, int> >, but that concept map can’t be instantiated: the implicitly defined operator= for std::pair<const int, int> fails to compile! Why did the compiler generate a concept map that can’t compile? First, let’s take a look at the Assignable concept:

auto concept Assignable<typename T, typename U = T> {
  typename result_type;
  result_type operator=(T&, U);
}
      

When the compiler builds the concept map in question, it produces the following code and attempts to type-check it.

concept_map Assignable<std::pair<const int, int> > {
  typedef std::pair<const int, int> result_type;
  result_type operator=(std::pair<const int, int>& x, const std::pair<const int, int>& y) {
    return x = y;
  }
};
      

To type-check the body of operator=, we only need to see a suitable declaration of operator= for pairs, which is implicitly generated by the compiler. That declaration looks like this:

template<typename T, typename U>
class pair {
public:
  T first;
  U second;

  // implicitly generated assignment operator...
  pair<T, U>& operator=(const pair<T, U>&);
};
    

With that implicitly-generated declaration, the Assignable concept map type-checks. However, eventually we are going to have to implicitly generate a definition for operator=. That definition looks like this:

template<typename T, typename U>
  pair<T, U>& operator=(const pair<T, U>& other) {
    first = other.first;
    second = other.second;
    return *this;
  }
      

When the compiler type-checks this definition, it fails: one cannot copy-assign a const value. How do we fix the problem? Well, we somehow need to avoid declaring operator= unless we’re sure that its definition will compile. ConceptC++ actually does have a way to do this for member templates, although ConceptGCC does not yet support the syntax. It looks like this:

template<typename T, typename U>
class pair {
  // ...
  where Assignable<T> && Assignable<U>
    pair<T, U>& operator=(const pair<T, U>& other) {
      first = other.first;
      second = other.second;
      return *this;
    }
};
      

This construct says that the assignment operator will only be declared if both T and U are Assignable. In the case of std::pair<const int, int>, const int is not Assignable, therefore no operator= will be declared and we no longer have a problem.

Even with this fix for pair, we really haven’t solved the problems. There are many classes that have non-copyable members, but the assignment operators are never used. However, when ConceptGCC is searching for concept maps, it will try to find these assignment operators and we will see failures similar to those that occur with std::pair<const int, int>. Some of these classes aren’t even templates, so the trick with the where clause does not apply.

It seems that we need to fix the implicit generation of assignment operators, so that declarations are only generated when the definitions will compile. The same issue also affects implicitly-generated default and copy constructors. It also seems possible that we could instead make Assignable, DefaultConstructible, and CopyConstructible into special concepts that perform additional checking when defining concept maps. However, this last idea feels like a hack.

ConceptGCC will soon have a partial fix to this problem: after generating the declaration for the assignment operator, ConceptGCC will determine if the assignment operator’s definition will compile. If not, the assignment operator will be marked “private”. This won’t work perfectly, but it’s close enough for now, as my prior attempts to completely eliminate the implicitly-defined members of classes have met with SIGSEGVs.