angle-left

Вычисляем числа Фибоначчи, пока компилируется C++

Доброе утро!

Как-то раз мне захотелось научиться вычислять значение функций во время компиляции исходных кодов на C++. Сегодня я расскажу, что из этого получилось.

Вычисления во время компиляции — давно известная тема. Для этого в C++ есть шаблоны, а с C++11 всё становится ещё проще. Приступим.

Для начала попробуем реализовать вычисление чисел Фибоначчи. Напомню, числа Фибоначчи — это следующая последовательность:

f0 = f1 = 1, fn = fn-1 + fn-2.

Как написано — так и сделаем!

Определим шаблонную структуру, принимающую индекс числа и рекуррентно вычисляющую новое:

using xy_type = std::enable_if<std::is_integral<unsigned decltype(N)>::value,
      unsigned decltype(N)>::type;

template <xy_type n = N>
struct fib {
  constexpr static xy_type f = fib<n-1>().f + fib<n-2>().f;
};

Здесь всё довольно просто: в структуре есть поле, значение которого — сумма этого же поля из таких же структур, но с другим шаблонным аргументом.

Определим первые два значения, чтобы рекурсия закончилась:

template <>
struct fib<0> {
  constexpr static xy_type f = 1;
};

template <>
struct fib<1> {
  constexpr static xy_type f = 1;
};

Ну и посчитаем:

constexpr static xy_type f = fib<N>().f;

int main() {
  std::cout << f << std::endl;
  return 0;
}

Кроме того, добавим вывод ошибки, если при компиляции указано некорректное N:

#define STR(X) #X
#define DEFER(M,...) M(__VA_ARGS__)
#define CUSTOM_ERROR_(a) _Pragma(STR(a))
#define CUSTOM_ERROR(...) CUSTOM_ERROR_(GCC error DEFER(STR, __VA_ARGS__))

#ifndef N
CUSTOM_ERROR(usage: c++ --std=c++11 -fmax-errors=1 -DN=<argument> __FILE__)
#endif // N

Запустим то, что у нас получилось:

$ g++ ./fibonacci_valid.cpp 
./fibonacci_valid.cpp:10:11: error: usage: c++ --std=c++11 -fmax-errors=1 -DN=<argument> "./fibonacci_valid.cpp"
 CUSTOM_ERROR(usage: c++ --std=c++11 -fmax-errors=1 -DN=<argument> __FILE__)
           ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~               
./fibonacci_valid.cpp:13:67: error: ‘N’ was not declared in this scope
 using xy_type = std::enable_if<std::is_integral<unsigned decltype(N)>::value,
...skipping...

$ g++ -DN=abc ./fibonacci_valid.cpp
<command-line>:0:3: error: ‘abc’ was not declared in this scope
./fibonacci_valid.cpp:13:67: note: in expansion of macro ‘N’
 using xy_type = std::enable_if<std::is_integral<unsigned decltype(N)>::value,
...skipping...
$ g++ -DN=5 ./fibonacci_valid.cpp
$ ./a.out 
8
$ g++ -DN=1 ./fibonacci_valid.cpp
$ ./a.out 
1
$ g++ -DN=20 ./fibonacci_valid.cpp
$ ./a.out                         
10946 

Отлично, мы увидели, что есть реакция на отсутствие аргумента (компилятор услужливо подчеркнул usage), есть реакция на строки вместо чисел, и успешная компиляция и какие-то расчёты при корректно заданном N.

Но это скучно. Давайте и ответ выведем во время компиляции. Изменения каснутся лишь последней части. Создадим удалённую шаблонную функцию и попробуем ею воспользоваться:

template <xy_type answer>
bool deleted() = delete;

static bool n = deleted<f>();

int main() {
  return 0;
}

Запустим компиляцию:

$ g++ -DN=10 ./fibonacci.cpp           
./fibonacci.cpp:36:28: error: use of deleted function ‘bool deleted() [with int answer = 89]’
 static bool n = deleted<f>();
                            ^
./fibonacci.cpp:34:6: note: declared here
 bool deleted() = delete;
      ^~~~~~~
$ clang++ -std=c++11 -DN=10 ./fibonacci.cpp
./fibonacci.cpp:36:17: error: call to deleted function 'deleted'
static bool n = deleted<f>();
                ^~~~~~~~~~
./fibonacci.cpp:34:6: note: candidate function [with answer = 89] has been explicitly deleted
bool deleted() = delete;
     ^
1 error generated.

Видим теперь ошибку компиляции, содержащую строку вида with answer = XXX. Это то, чего мы и добивались, получив answer благодаря удачно подобранному имени шаблонного аргумента удалённой функции. Ну и, конечно, пользуемся тем, как clang и gcc одинаково выводят подобную ошибку, демонстрируя значение шаблонного параметра.

На всякий случай приведу полный код:

#include <iostream>
#include <type_traits>

#define STR(X) #X
#define DEFER(M,...) M(__VA_ARGS__)
#define CUSTOM_ERROR_(a) _Pragma(STR(a))
#define CUSTOM_ERROR(...) CUSTOM_ERROR_(GCC error DEFER(STR, __VA_ARGS__))

#ifndef N
CUSTOM_ERROR(usage: c++ --std=c++11 -fmax-errors=1 -DN=<argument> __FILE__)
#endif // N

using xy_type = std::enable_if<std::is_integral<decltype(N)>::value,
      decltype(N)>::type;

template <xy_type n = N>
struct fib {
  constexpr static xy_type f = fib<n-1>().f + fib<n-2>().f;
};

template <>
struct fib<0> {
  constexpr static xy_type f = 1;
};

template <>
struct fib<1> {
  constexpr static xy_type f = 1;
};

constexpr static xy_type f = fib<N>().f;

template <xy_type answer>
bool deleted() = delete;

static bool n = deleted<f>();

int main() {
  return 0;
}

В качестве бонуса, проведём эксперимент:

$ g++ -DN=10000000 ./fibonacci.cpp 
./fibonacci.cpp: In instantiation of ‘constexpr const xy_type fib<9999101>::f’:
./fibonacci.cpp:18:43:   recursively required from ‘constexpr const xy_type fib<9999999>::f’
./fibonacci.cpp:18:43:   required from ‘constexpr const xy_type fib<10000000>::f’
./fibonacci.cpp:31:39:   required from here
./fibonacci.cpp:18:32: fatal error: template instantiation depth exceeds maximum of 900 (use -ftemplate-depth= to increase the maximum)
   constexpr static xy_type f = fib<n-1>().f + fib<n-2>().f;
                                ^~~~~~~~~~
compilation terminated.

$ g++ -ftemplate-depth=100000000 -DN=10000000 ./fibonacci.cpp
g++: internal compiler error: Segmentation fault (program cc1plus)
Please submit a full bug report,
with preprocessed source if appropriate.
See <file:///usr/share/doc/gcc-7/README.Bugs> for instructions.

$ clang++ -std=c++11 -ftemplate-depth=100000000 -DN=10000000 ./fibonacci.cpp
#0 0x00007f0ebe18e155 llvm::sys::PrintStackTrace(llvm::raw_ostream&) (/usr/lib/llvm-4.0/bin/../lib/libLLVM-4.0.so.1+0x780155)
#1 0x00007f0ebe18c3b6 llvm::sys::RunSignalHandlers() (/usr/lib/llvm-4.0/bin/../lib/libLLVM-4.0.so.1+0x77e3b6)
#2 0x00007f0ebe18c4d3 (/usr/lib/llvm-4.0/bin/../lib/libLLVM-4.0.so.1+0x77e4d3)
...skipping...
Stack dump:
0.      Program arguments: /usr/lib/llvm-4.0/bin/clang -cc1 -triple x86_64-pc-linux-gnu -emit-obj -mrelax-all -disable-free -disable-llvm-verifier -discard-value-names -main-file-name fibonacci.cpp -mrelocation-model static -mthread-model posix -mdisable-fp-elim -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -resource-dir /usr/lib/llvm-4.0/bin/../lib/clang/4.0.1 -D N=10000000 -internal-isystem /usr/bin/../lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/c++/7.3.0 -internal-isystem /usr/bin/../lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/x86_64-linux-gnu/c++/7.3.0 -internal-isystem /usr/bin/../lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/x86_64-linux-gnu/c++/7.3.0 -internal-isystem /usr/bin/../lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/c++/7.3.0/backward -internal-isystem /usr/include/clang/4.0.1/include/ -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-4.0/bin/../lib/clang/4.0.1/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -std=c++11 -fdeprecated-macro -fdebug-compilation-dir /home/valeriyk/doc/tpl -ftemplate-depth 100000000 -ferror-limit 19 -fmessage-length 227 -fobjc-runtime=gcc -fcxx-exceptions -fexceptions -fdiagnostics-show-option -fcolor-diagnostics -o /tmp/fibonacci-eb891d.o -x c++ ./fibonacci.cpp 
1.      ./fibonacci.cpp:31:38: current parser token '.'
2.      ./fibonacci.cpp:17:8: instantiating class definition 'fib<10000000>'
3.      ./fibonacci.cpp:17:8: instantiating class definition 'fib<9999999>'
4.      ./fibonacci.cpp:17:8: instantiating class definition 'fib<9999998>'
5.      ./fibonacci.cpp:17:8: instantiating class definition 'fib<9999997>'
...skipping...
740.    ./fibonacci.cpp:17:8: instantiating class definition 'fib<9999262>'
741.    ./fibonacci.cpp:17:8: instantiating class definition 'fib<9999261>'
clang: error: unable to execute command: Segmentation fault
clang: error: clang frontend command failed due to signal (use -v to see invocation)
clang version 4.0.1-10+b1 (tags/RELEASE_401/final)
Target: x86_64-pc-linux-gnu
Thread model: posix
InstalledDir: /usr/bin
clang: note: diagnostic msg: PLEASE submit a bug report to http://llvm.org/bugs/ and include the crash backtrace, preprocessed source, and associated run script.
clang: note: diagnostic msg: 
********************

PLEASE ATTACH THE FOLLOWING FILES TO THE BUG REPORT:
Preprocessed source(s) and associated run script(s) are located at:
clang: note: diagnostic msg: /tmp/fibonacci-548661.cpp
clang: note: diagnostic msg: /tmp/fibonacci-548661.sh
clang: note: diagnostic msg: 

********************

Вот мы и ссегфолтили компиляторы! Те, кто любят пожёстче, могут написать ulimit -s unlimited перед запуском.

Если тема статьи понравилась, то в качестве упражнения читателю предлагается сделать реализацию ещё чего-нибудь, к примеру — факториала.