null

Страх и ненависть в C++ template'ах

В ходе работы мне потребовался код на языке C++, совершающий простую операцию: зеркальное отражение младшей половины бит целого беззнакового числа на старшую половину (см. пример)

0010 -> 0110
0000 0101 -> 1010 0101
0000 0000 1100 1010 -> 0101 0011 1100 1010
...

Идейно реализация должна быть простой и могла быть описана примерно таким кодом (для типа uint64_t, например)

uint64_t mirror(uint64_t arg) {
  uint64_t result = arg;
  for (int i = 0; i < sizeof(arg) * 8 / 2; ++i) {
    uint64_t current_bit = arg & ((uint64_t)1 << i);
    result |= (current_bit << (sizeof(arg) * 8 - 1 - i - i));
  }
  return result;
}

К своему сожалению, в тот момент я открывал для себя магию плюсовых шаблонов (templates), потому и подход к решению я выбрал эзотерический.

Первое мое пожелание по улучшению этого кода вполне естественно: параметризация функции для работы с различными беззнаковыми целыми. В данный код не нужно вносить много изменений: достаточно заменить все вхождения типа uint64_t на шаблонный параметр.

template<typename T>
T mirror(T arg) {
  T result = arg;
...

Недостатком данного кода является то, что функцию можно будет вызвать от любого аргумента, а не только от беззнакового целого. Результатом станет целая простыня ошибок и предупреждений во время компиляции. Во внесении такого ограничения с более понятным сообщением об ошибке могут помочь type traits и static assert.

Type traits — часть стандартной библиотеки, набор шаблонных классов, позволяющих получать метанформацию о шаблонных типах: проверить, является ли шаблонный аргумент указателем, константой, обладает ли конструктором, и в том числе, является ли аргумент беззнаковым.

Отличительной особоенностью шаблонов в C++ от, например, дженериков в Java, заключается в том, что они основаны не на полиморфизме, а на генерации кода. Таким образом, type traits, как и любой другой шаблонный класс, "работают" на этапе компиляции.

Static assert позволяет проверить что-то, вычислимое на этапе компляции, и выдасть ошибку, если проверка не пройдена.

В сумме эти два механихма позволят добавить удобочитаемое сообщение об ошибке (хоть и не избавит от простыни остальных ошибок).

static_assert(is_unsigned<T>::value, "mirror function works only with unsigned integers");

Шаблонным параметром может быть не только тип данных, но и число. Вкупе с перегрузками и рекурсией шаблоны превращаются в мощный инструмент. Остановиться я уже не мог, потому цикл превратился в рекурсивный вызов.

template<typename T>
constexpr size_t bits(T arg) {
  return sizeof(T) * 8;
}

template<typename T>
constexpr size_t bits() {
  return sizeof(T) * 8;
}

template<typename T, size_t N = bits<T>() / 2 - 1>
T mirror(T arg) {
  static_assert(is_unsigned<T>::value, "mirror function is only for unsigned integers");
  T current_bit = arg & ((T)1 << N);
  if (N == 0) {
    return (current_bit << bits(arg) - 1) | arg;
  }
  return mirror<T, N - 1>((current_bit >> N << (bits(arg) - 1 - N)) | arg);
}

Наверное, в этом коде есть что пояснить.

Модификатор constexpr — нововведение C++11, выражение (или функция), которое обязательно будет вычисляться во время компляции.

Функция mirror стала принимать еще один шаблонный аргумент — size_t N, который заменил счетчик i в предыдущей версии. Цикл стал организован с помощью рекурсии с постепенным уменьшением значения счетчика N.

К сожалению, этот код не компилируется. gcc version 6.3.0 выдает (помимо множества предупреждений) сообщение об ошибке:

fatal error: template instantiation depth exceeds maximum of 900 (use -ftemplate-depth= to increase the maximum)
     return (current_bit << bits(arg) - 1) | arg;

В чем же проблема? Если посмотреть предупреждения выше, то можно увидеть следующее:

In instantiation of ‘T mirror(T) [with T = long unsigned int; long unsigned int N = 18446744073709550749ul]’:

Почему-то шаблонный параметр N стал равен 18446744073709550749ul, хотя у рекурсии было условие выхода N == 0. В этот момент стоит вспомнить, что шаблон раскрывается во время компиляции, а проверка if (N == 0)  происходит во время выполнения. В результате начинает генерироваться множество шаблонных функций от различного аргумента N, что и приводит к ошибке. Нужно как-то ограничить глубину раскрытия. Благо, это можно сделать с помощью тернарного оператора

return mirror<T, (N > 0 ? N - 1 : N)>

В данном случае тернарный оператор выполнится во время компиляции, потому раскрытие шаблона остановится, когда N достигнет нуля.

Засим откланиваюсь, прощайте.