[Перевод] Неопределенное поведение может привести к путешествиям во времени
Языки C и C++ печально известны большими областями на картах, которые отмечены предупреждением »тут обитают драконы», а если говорить более формально, речь идет о неопределенном поведении (undefined behavior).
Когда мы сталкиваемся с неопределенным поведением, может произойти все что угодно. Например, переменная может быть одновременно и true, и false. В блоге Джона Регера (John Regehr) есть парочка интересных примеров неопределенного поведения, а также определены несколько победителей объявленного в комментариях конкурса на самый сумасшедший объектный код, генерируемый компилятором в результате неопределенного поведения.
Рассмотрим следующую функцию:
int table[4];
bool exists_in_table(int v)
{
for (int i = 0; i <= 4; i++) {
if (table[i] == v) return true;
}
return false;
}Какое это имеет отношение к путешествию во времени, спросите вы? Погодите, немного терпения.
Прежде всего, в схеме управления циклом вы могли заметить ошибку смещения на единицу. В результате чего, функция будет считывать еще один элемент, следующий за конечным элементом массива данных в table, прежде чем цикл завершится. Классический компилятор не особо это заботит. Он просто сгенерирует код для чтения элемента за границей массива (несмотря на то, что это нарушение правил синтаксиса языка), и вернет true, если в памяти за пределами массива, оказалось бы подходящее по типу значение.
С другой стороны, постклассический компилятор мог бы выполнить следующий анализ:
Когда i равно 4, в коде происходит неопределенное поведение. Поскольку неопределенное поведение позволяет мне делать все, что угодно, я могу полностью проигнорировать этот случай и предположить, что i никогда не будет равно четырем. (Если предположение окажется ошибочным, произойдет что-то непредвиденное, но это нормально, потому что неопределенное поведение позволяет мне действовать непредсказуемо.)
Случай, когда i равно 5, невозможен, потому что для того, чтобы это произошло, нужно сначала пройти через i = 4, что, как нам позволено считать, может не произойти.
Таким образом, постклассический компилятор может оптимизировать функцию следующим образом:
bool exists_in_table(int v)
{
return true;
}Так, вот это уже выглядит странно. Функция была оптимизирована практически до ничего из-за неопределенного поведения. Обратите внимание, что даже если значение отсутствует в table (включая даже недопустимый пятый элемент), функция все равно вернет true.
Теперь мы можем продвинуть постклассическое поведение еще на один шаг: поскольку компилятор может допустить, что неопределенное поведение никогда не возникнет (ведь, если это происходит, компилятор может делать все, что угодно), например, он может использовать неопределенное поведение в целях оптимизации.
int value_or_fallback(int *p)
{
return p ? *p : 42;
}Вышеупомянутая функция получает указатель на целое число и либо возвращает указанное значение, либо (если указатель равен null) возвращает резервное значение 42. Здесь пока все нормально.
Теперь, в целях дебага давайте добавим в функцию эту строчку.
int value_or_fallback(int *p)
{
printf("The value of *p is %d\n", *p);
return p ? *p : 42;
}Добавленная строчка содержит баг: она разыменовывает указатель p, не проверив предварительно, равен ли он null. Однако этот маленький баг влечет масштабные последствия. Постклассический компилятор оптимизирует функцию, потому что он видит, что проверка нулевого указателя больше не требуется, следующим образом:
int value_or_fallback(int *p)
{
printf("The value of *p is %d\n", *p);
return *p;
}Если бы указатель был равен null, тогда printf уже вызвал бы неопределенное поведение, поэтому компилятору разрешено делать что угодно в случае, если указатель имеет значение null (даже например, представить, что указатель не равен null).
Ладно, тут нет ничего удивительного. Возможно, что это и есть та оптимизация, которую вы ожидаете от компилятора. (Например, если тернарный оператор был спрятан в макрос, можно ожидать, что компилятор не проведет проверку, которая гарантированно будет false.)
Но постклассический компилятор теперь может использовать содержащую ошибки функцию, чтобы начать путешествие во времени.
void unwitting(bool door_is_open)
{
if (door_is_open) {
walk_on_in();
} else {
ring_bell();
// ждем, пока дверь откроется, со значением по умолчанию
fallback = value_or_fallback(nullptr);
wait_for_door_to_open(fallback);
}
}Постклассический компилятор может оптимизировать всю функцию следующим образом:
void unwitting(bool door_is_open)
{
walk_on_in();
}Что произошло?
Компилятор заметил, что вызов value_or_fallback(nullptr) приводит к неопределенному поведению по всем путям кода. Распространяя этот анализ назад, компилятор замечает, что если door_is_open имеет значение false, то в ветке else вызывается неопределенное поведение по всем путям кода. Следовательно, всю else ветвь можно считать невозможной.²
А теперь мы наконец-то переходим к путешествию во времени:
void keep_checking_door()
{
for (;;) {
printf("Is the door open? ");
fflush(stdout);
char response;
if (scanf("%c", &response) != 1) return;
bool door_is_open = response == 'Y';
unwitting(door_is_open);
}
}Постклассический компилятор может запомнить вывод, что «если door_is_open равно false, то происходит неопределенное поведение», и переписать эту функцию следующим образом:
void keep_checking_door()
{
for (;;) {
printf("Is the door open? ");
fflush(stdout);
char response;
if (scanf("%c", &response) != 1) return;
bool door_is_open = response == 'Y';
if (!door_is_open) abort();
walk_on_in();
}
}Обратите внимание, что исходный код звонил в колокольчик перед сбоем, а оптимизированная функция пропускает звонок и сразу же вылетает. Можно сказать, что компилятор вернулся в прошлое и отменил прозвеневший звонок.
«Путешествие в прошлое» возможно даже для объектов с внешней видимостью, например файлов, потому что стандарт допускает, чтобы все происходило в момент, когда обнаруживается неопределенное поведение. И это позволяет прыгнуть в машину времени и притвориться, что вы никогда не звонили fwrite.
Даже если вы возьметесь утверждать, что компилятору не разрешено путешествовать во времени, все равно можно увидеть, что предыдущие операции отменены. Например, может так случиться, что неопределенная операция приведет к повреждению буферов файлов, поэтому данные на самом деле никогда не записывались. Даже если буферы были очищены, эта операция могла привести к вызову функции ftruncate, созданную для логического удаления только что записанных данных. Или же это могло привести к тому, что DeleteFile удалил файл, которые вы предполагали, что создали.
Все эти виды поведения имеют один общий заметный эффект, а именно отмена предыдущего действия. Было ли действие выполнено, было изменено или никогда не происходило, вопрос спорный с точки зрения теории компиляторов.
Компилятор также мог в прошлом размножить эффект неопределенной операции.
¹ Примечание автора: согласно стандарту — путешествие во времени допустимо перед возникновением неопределенного поведения:
Однако, если любое такое выполнение содержит неопределенную операцию, этот международный стандарт не налагает никаких требований на реализацию, выполняющую эту программу с этим входом (также это касается операций, предшествующих первой неопределенной операции).
² Другой способ взглянуть на это преобразование состоит в том, что компилятор увидел, что else ветвь вызывает неопределенное поведение для всех путей кода, после чего он переписал код, воспользовавшись правилом, согласно которому неопределенное поведение допускает что угодно:
void unwitting(bool door_is_open)
{
if (door_is_open) {
walk_on_in();
} else {
walk_on_in();
}
}В данном случае, »walk_on_in» по ошибке было принято за «anything».
Дополнительная информация: обратите внимание, что есть некоторые категории неопределенного поведения, которые могут быть неочевидными. Например, разыменование нулевого указателя является неопределенным поведением, даже если вы пытаетесь противодействовать разыменованию до того, как он сделает что-нибудь опасное.
int p = nullptr;
int& i = p;
foo(&i); // undefinedВы можете подумать, что & и взаимоуничтожаются, и результат остается такой же, как если бы вы написали foo (p), но тот факт, что вы создали ссылку на несуществующий объект, даже если вы по сути не делали этого, вызывает неопределенное поведение (§8.5.3 (1)).
Похожие статьи: Что должен знать каждый программист на C о неопределенном поведении, часть 1, часть 2, часть 3.
Обновление: разделил & на две строки, потому что одиночная является проблемой.
Материал подготовлен в рамках курса «Программист С».
Всех желающих приглашаем на бесплатное demo-занятие «WinAPI: пишем GUI приложение на C и кросскомпилируем из-под Linux». На открытом уроке мы разберём несложное приложение с графическим интерфейсом, использующее WinAPI, а так же скомпилируем выполняемый .exe файл для Windows, находясь в Linux, с помощью инструмента сборки CMake.
>> РЕГИСТРАЦИЯ
