Доброе утро!
Как-то раз мне захотелось научиться вычислять значение функций во время компиляции исходных кодов на 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 перед запуском.
Если тема статьи понравилась, то в качестве упражнения читателю предлагается сделать реализацию ещё чего-нибудь, к примеру — факториала.
