How to Hack C++ with Templates and Friends

Andrey Karpovskii

Templates are a very powerful feature in C++, because they allow you to write generic programs that accept a data type as an extra parameter. This feature of them means that we don’t need to repeat similar code for different data types.

When templates were first introduced in C++, their capabilities were unforeseen. Since then templates have grown into a separate functional language inside of C++. This language has its own syntax, rules, and huge number of specifics, one of which I will discuss later.

How Templates Work

Each template defines a family of functions. It is, after all, a functional language. But the family does not produce any code on its own. Instead, the compiler generates code only for functions that are actually used in the program. This process is a multi-step process called instantiation.

template<typename T>
struct Foo {
  T val;
};

template<>                      // generated code
struct Foo<int> {
  int val;
};

...
template struct Foo<int>;       // explicit specialization
Foo<int> foo;                   // implicit specialization
...

First, the user must request a specialization, either explicit or implicit. Seeing this, the complier starts the instantiation process which includes things like the substitution of template parameters. If the code with the substituted template arguments is valid, then the compiler generates the actual specialization.

Making New Friends

“Friendship” in C++ is commonly thought of as a means of granting non-member functions or another class access to private and protected members of a class. This is done to allow symmetric conversions on non-member comparison operators or to allow a factory class exclusive access to the constructor of the class, among other reasons.

void bar();

struct Foo {
  // bar now may use private members of Foo
  friend void bar();
};

Note that function bar is not required to be defined in the same translation unit. But what happens when we forget to define it?

struct Foo {
  friend void bar();
};

Well, it still will compile. This might come as a surprise to you, but the result is completely valid code.

This is called a friend declaration. It declares function bar, if it hasn’t been declared before. (If it has, then it redeclares one.) Such declarations do have some limitations as compared to regular ones, but the limitations are not essential to this topic.

Okay, so it declares a function. But what scope does this function have? When a function is first declared in a friend declaration within a class, it becomes a member of the innermost enclosing namespace of that class. But it is not a member of the class it is declared in.

struct Foo {
  friend void bar();
};

...
bar();		// error - bar is not declared
::bar();	// error - bar is not in the global ns
Foo::bar();	// error - bar is not a member of Foo
...

The only way to call the function is to use an Argument Dependent Lookup (ADL). ADL is a set of rules for looking up unqualified function names. These function names are looked up in the namespace of their arguments, in addition to the scopes and namespaces considered by the usual unqualified name lookups.

Let me change the example, as shown by the figure below.

struct Foo {
  friend void bar(Foo) { cout << "Got it!" << endl; }
};

...
Foo foo;
bar(foo);	// Ok - found through ADL
...

Note that friend functions can be defined inside class definitions. These are inline functions and, like member inline functions, they behave as though they are defined immediately after all class members are seen, but before the class scope is closed.

Down the Rabbit Hole

Let me now combine the techniques I described above.

template<typename T>
struct Foo {
  friend void bar() { cout << "Got it!" << endl; }
};

As before, we have a structure Foo and a hidden friend bar, only now the structure is templated. We know that to call bar we have to declare it in global namespace. Let’s try this.

template<typename T>
struct Foo {
  friend void bar() { cout << "Got it!" << endl; }
};

void bar();

...
bar();	// error - unresolved external symbol
...

Hmm... what happened? The compiler generates templates instantiations only when they are requested. Because there is no instantiation of structure Foo, the definition of bar also does not exist. The compiler doesn’t know about the content of the structure, and so we have to instantiate Foo explicitly.

template<typename T>
struct Foo {
  friend void bar() { cout << "Got it!" << endl; }
};

void bar();
template struct Foo<int>;

...
bar();	// Ok
...

And now it works! It’s all fun and games, but can you spot an issue? Well, there are actually two issues.

First, note that bar is a plain function (not a templated one) that refers to a specific specialization of the structure Foo. What this means is that we can use all the template parameters passed to Foo – even when the parameter is a pointer to a private member of another class. This feature is described later.

Second, whether the function is defined depends on whether the specialization of Foo is instantiated by the compiler. And this is the internal state of the compiler. Templates in C++ have a way to check this state: SFINAE, or “substitution failure is not an error.”

There are plenty examples of using this technique, but for ease of understanding we will look at the implementation of the compile-time counter. As this code is not production-ready, we will use a new feature of C++20 which I describe later.

Accessing Private Members

Imagine that you have a class containing two private inner classes, one of which is templated, and a public method func.

class Parent {
  struct ChildA {};
  template<typename N> class ChildB {};

public:
  void func();	// Do something with ChildB<ChildA> 
};

Imagine that the specialization ChildB<ChildA> is used in method func. You want to explicitly instantiate such specialization. How would you implement it? Simple question – simple answer. Just do what you always do:

class Parent {
  struct ChildA {};
  template<typename N> class ChildB {};

public:
  void func();	// Do something with ChildB<ChildA>

template class Parent::ChildB<Parent::ChildA>;

Here is a tricky part. The explicit specialization is in the global namespace, not in the class itself. But how does the compiler know that you are allowed to use private inner classes? The answer is, it doesn’t! For such cases the C++ standard contains the following wording:

§ 14.7.2/12

The usual access checking rules do not apply to names used to specify explicit instantiations. [Note: In particular, the template arguments and names used in the function declarator (including parameter types, return types and exception specifications) may be private types or objects which would normally not be accessible and the template may be a member template or member function which would not normally be accessible. – end note.]

In short, it does not check whether you allowed to do it, or not. This means that we can write an external getter for any class we want. Let’s try writing it.

class Private {
  int data;
};

template<int Private::* Member>
int& dataGetter(Private& iObj) {
  return iObj.*Member;
}

template int& dataGetter<&Private::data>(Private&);

...
Private obj;
dataGetter<&Private::data>(obj);	//error
...

Here we defined a function that is parametrized with a pointer to a member of the class Private with a type int. The fancy-looking syntax in the return statement is just a way to access a member by its pointer.

When we make an attempt to call this function, it will, unfortunately, fail. A call is not an explicit instantiation and the access rules will be checked.

Luckily, we can use a friend injection to make things work.

template<int Private::* Member>
struct Stealer {
  friend int& dataGetter(Private& iObj) {
    return iObj.*Member;
  }
};

template struct Stealer<&Private::data>;
int& dataGetter(Private&);	//redeclare in global ns

...
Private obj;
dataGetter(obj) = 31;	// Ok
...

And so we changed a private member of an arbitrary class.

Compile-time Counter

Let’s move on to the second part to see how a compile-time counter can be implemented. First of all, let’s look at the use of the counter.

template<int R = reader<0>(int{})>
constexpr int next() {
  return R;
}

...
static_assert(next() == 0);
static_assert(next() == 1);
static_assert(next() == 2);
...

Isn’t it beautiful? We just violated one of the fundamental aspects of the language! And yet, I emphasize, everything is in full compliance with the C++ standard.

So, what is happening here? Well, next is a constexpr template function with a single argument R that has a default value. The default value is generated with template function reader which accepts an integer as a parameter. If you are familiar with template metaprogramming, then you can guess that reader is implemented as a tail recursive function which iterates over all successive numbers starting from the number 0.

template<int>                                         
struct Flag {
  friend constexpr bool flag(Flag);
};

template<int N>
struct Writer {
  friend constexpr bool flag(Flag<N>) { 
    return true; 
  }
  static constexpr int value = N;
};

template<int N = 0>
constexpr int reader(float) {
  return Writer<N>::value;
}

template<int N = 0,
         bool = flag(Flag<N>{}),
         auto = unique()>
constexpr int reader(int) {
  return reader<N + 1>(int{});
}

The end of the recursion is controlled not by the number itself, but by the presence of the definition of a special function flag in the global namespace. If the definition has been generated previously, then the control is passed to the successive reader function. If not, then the definition is injected into the global namespace by Writer, and the current value is returned.

Note that the first overload of reader has a lower priority, because it accepts float. Choosing this overload requires an implicit floating-integral conversion.

The last thing worth looking at is an implementation of unique function. As the name implies, unique produces something unique on every call. More specifically, it produces an object with the unique type. It is necessary to bypass the caching of default arguments by the compiler. How can it be implemented?

template<auto T = []{}>
constexpr auto unique() {
  return T;
}

Starting with C++20, the list of types applicable as non-type template parameters has been extended, and now it includes lambdas. Every lambda is implicitly converted to a functor with a unique type. It even works with default arguments!

Current Status of Stateful Metaprogramming

Here is what the C++ Standard says about stateful metaprogramming:

2118. Stateful metaprogramming via friend injection

Section: 17.7.5 [temp.inject] Status: open Submitter: Richard Smith Date: 2015-04-27

Defining a friend function in a template, then referencing that function later provides a means of capturing and retrieving metaprogramming state. This technique is arcane and should be made ill-formed.

Notes from the May, 2015 meeting:

CWG agreed that such techniques should be ill-formed, although the mechanism for prohibiting them is as yet undetermined.

http://www.open-std.org/jtc1/sc22/wg21/docs/cwg_active.html

From reading this, it may seem to you that stateful metaprogramming ought to be illegal, and that the committee feels the same way. The problem is that they do not know what to do with this “feature” that they introduced accidentally. The technique was found back in 2015, and since then the issue has remained open.

Conclusion

Friendships and templates are powerful tools in C++. Like other tools in C++, they can surprise us with their behavior, behavior that can become confusing when combined together. Not that such aspects of C++ are rare, but they again demonstrate how complex the language has become.


Read more:
On C++ code bloat
Fast Debug in Visual C++
Which Missing C++ Features Are Needed Most?



CPP C++