Зазеркалье

[zHz00]

С детства нас учат правильно выбирать тип переменной. Например, если числа она должна представлять только положительные, её можно сделать типа unsigned int -- тогда она сможет представить в два раза больший набор значений.

Итак, в одном из проектов у нас есть маленький модуль. Он реализует обработку команд на специальном птичьем языке програмирования. Он был придуман давным-давно, ещё до моего прихода в нашу организацию. Этот язык не поддерживает условия, но поддерживает циклы. Перед выполнением циклы "разворачиваются", в итоге получается фиксированная последовательность команд без переходов, которая исполняется последовательно.

То есть, до разворачивания макрос выглядел так:

loop 3
command1
command2
endloop

А после разворачивания так:

nop
command1
command2
nop
nop
command1
command2
nop
nop
command1
command2
nop

По тактическим соображениям команды начала и конца цикла не удалялись, а заменялись на nop (пустая команда).

Циклы поддерживались только одного уровня вложенности, в то время как существовала необходимость сделать циклы минимум вложенности 2. Это задание было выдано мне. Я решил сразу делать цикл вложенности n. Как определять границы циклов -- плёвая задача. В итоге я написал функцию:

void Unfold(CMacros *pMacros, unsigned int nStart, unsigned int nEnd);

Она должна была брать макрос pMacros, извлекать из него заданный набор команд -- от номера nStart до номера nEnd -- повторять их заданное число раз (тут этот момент опущен) и вставлять после первого встречания тела цикла. Там было написано примерно следующее:

unsigned int x;
for(x=nEnd;x>=nStart;x--)
	{
		pMacros->aCommands->InsertAt(nEnd+1,pMacros->aCommands->GetAt(x));
	}

InsertAt -- вставляет в заданную позицию, сдвигая то, что там было (и всё дальнейшее), дальше по массиву.
aCommands -- массив команд.
GetAt -- обращение к массиву по заданному индексу.

Эта штука работала без нареканий 2 года. Но сегодня ружьё выстрелило. Программа падает. Почему? Выход за границы массива в GetAt.

ОКАЗАЛОСЬ, что nStart равен нулю. Два года работы, десятки скриптов. Ни у одного из них начало цикла не было первой командой! Поэтому значение типа unsigned int (переменная x) всегда сравнивалось с числом 1 или больше (очевидно, первая команда имела номер 0, а не 1). И когда оно становилось равно в худшем случае нулю, цикл прекращался. Когда же цикл оказался стоящим первой командой, возникла прикольная ситуация. Число типа unsigned всегда будет больше либо равно нуля! Если из него вычесть 1, оно станет равно 2^32-1 (если int 32 бита). Перенос! И по этому четырёхмиллиардному смещению программа пытается что-то там прочитать.

Я смотрю на это и говорю -- а давайте поменяем тип x на int. Тогда он станет равным -1, а -1>=0 это ложь. Т.к. условие в цикле for проверяется ДО тела, то цикл завершится ещё до того, как -1 попадёт в аргумент GetAt.

Сделали. Но не помогло. Происходил вход в тело цикла! Тогда мы заменили nStart и nEnd тоже на просто int -- и всё заработало!

Что это означает? Что при проверке условия x>=nStart по неизвестной причине int преобразуется к unsigned int, а не наоборот! И -1 при сравнении превращалась в ту же 2^32-1 или может и во что похуже, но это значения не имеет, т.к. оно было типа unsigned int, а любое число этого типа будет заведомо больше либо равно нулю.

Мораль. Не использовать тип unsigned в циклах с обратным счётом. Тут такой цикл был нужен, чтобы вставлять команды в одну и ту же точку массива, сдвигая его конец всё дальше. Чтобы порядок команд не стал обратным, надо было запихивать их в массив задом наперёд, но по одному и тому же смещению.

Comments

[korrshun]

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

#include <stdio.h>

int main(void)
{
    short int x;
    short unsigned int nEnd = 100;
    short unsigned int nStart = 0;
    for(x=nEnd;x>=nStart;x--)
    {
        printf("%d\n", x);
    }
}

работает? ^_^'

спойлер

stackoverflow.com/questions/17832815/c-implicit... - про расширение до unsigned написано тут.
а про short отгадка - другая цитата из стандарта

Each  of  the  operators < (less  than), > (greater  than), <= (less  than  or  equal  to),  and >= (greater than or equal to) shall yield 1 if the specified relation is true and 0 if it is false.The result has type int.

[zHz00]

korrshun, да, твой фрагмент работает (MSVS 2010, C++), но не по тому способу, что ты описал.

Приведённая цитата означает, что результат сравнения имеет тип инт. То есть, 1.0<0.5 равно 0 и этот 0 имеет тип инт. Кроме того, твоя цитата из стандарта языка Си, а наблюдаемый эффект был на MSVS 2003, 2010. В Си++ же результаты логических операций имеют тип bool. Что, правда, не отражается на дедовские методы работы, т.к. все проверки условий корректно обрабатывают и целые числа и bool.

В приведённом же фрагменте кода происходит нечто иное.
(short)-1 >= (unsigned short) 0 даёт false.
Я решил заменить >= на + и с удивлением обнаружил, что результат равен -1, а тип результата (в окошке Quick Watch отображается и тип тоже) -- int! То есть, перед сложением ОБА операнда преобразуются к инту!

Я имею право для эксперимента заменить сравнение на +, т.к. в пункте 6.5.8, 3 сказано:
>>If both of the operands have arithmetic type, the usual arithmetic conversions are performed.
(я ссылаюсь на черновик ISO/IEC 9899:201x)

Осталось выяснить, что это за usual arithmetic conversions.
Во-первых, об этом написано в 6.3.1.8, 1. Там сказано, что сначала для чисел делается integer promotion, а потом проводится одно из нескольких преобразований. Нас эти преобразования не интересуют, т.к.:
>>If both operands have the same type, then no further conversion is needed.
(оттуда же)
После проведения integer promotion тип у операндов будет одинаковый.

А integer promotion описан в 6.3.1.3, 2:
>>The following may be used in an expression wherever an int or unsigned int may be used:
— An object or expression with an integer type (other than int or unsigned int) whose integer conversion rank is less than or equal to the rank of int and unsigned int.
— A bit-field of type _Bool, int, signed int, or unsigned int.
If an int can represent all values of the original type (as restricted by the width, for a bit-field), the value is converted to an int; otherwise, it is converted to an unsigned int. These are called the integer promotions.

То есть, все целые типы размером инт и меньше при преобразовании преобразуются либо в инт, либо в ансигнед инт (если типы операндов разные).
То есть:
int+unsigned int => unsigned int
int+int => int
short+int => int
short+unsigned int => unsigned int
short+unsigned short => int -- и именно этот случай ты представил.
И, на сладкое:
short+bool => int

[zHz00]

>>То есть, все целые типы размером инт и меньше при преобразовании преобразуются либо в инт, либо в ансигнед инт (если типы операндов разные).

Я написал не совсем правильно. Не "размером" инт и меньше, а "рангом" инт и меньше. Лонг инт даже если имеет тот же размер, ранг его выше. Если ранги выше, работают другие правила. Про ранги написано в 6.3.1.1, 1:
>> The rank of long long int shall be greater than the rank of long int, which shall be greater than the rank of int, which shall be greater than the rank of short int, which shall be greater than the rank of signed char.

[korrshun]

ну вот да. как я понял, производится промоушен до типа результата, если ранг операндов ниже, чем он, а тип результата int.
В общем я в "восхищении" от стандарта.