12 Окт 2011

Точка следования

12 Окт 2011

Точка следования (англ. Sequence point) — в программировании любая точка программы, в которой гарантируется, что все побочные эффекты предыдущих вычислений уже проявились, а побочные эффекты последующих еще отсутствуют.

Их часто упоминают, говоря о языках Си и Си++, поскольку в этих языках особенно просто записать выражение, значение которого может зависеть от неопределённого порядка проявления побочных эффектов. Добавление одной или нескольких точек следования задает порядок более жестко и является одним из методов достижения устойчивого (т.е. корректного) результата.

Точки следования необходимы в ситуации, когда одна и та же переменная изменяется в выражении более одного раза. Часто в качестве примера приводят выражение i=i++, в котором происходит присваивание переменной i и её же инкремент. Какое значение примет i? Стандарт языка должен либо указать одно из возможных поведений программы как единственно допустимое, либо указать диапазон допустимых поведений, либо указать, что поведение программы в данном случае совершенно не определено. В языках Си и Си++ вычисление выражения i=i++ приводит к неопределённому поведению, поскольку это выражение не содержит внутри себя ни одной точки следования.

В Cи и Си++ определены следующие точки следования:

Между вычислением левого и правого операндов в операторах && (логическом И), || (логическом ИЛИ) и операторах-запятых. Например, в выражении *p++ != 0 && *q++ != 0 все побочные эффекты левого операнда *p++ != 0 проявятся до начала каких либо действий в правом.
Между вычислением первого, второго или третьего операндов в операторе условия. В строке a = (*p++) ? (*p++) : 0 точка находится после первого операнда *p++. При вычислении второго выражения, переменная p уже увеличена на 1.
В конце всего выражения. Эта категория включает в себя инструкции-выражения (a=b;), выражения в инструкциях return, управляющие выражения в круглых скобках инструкций ветвления if или switch и циклов while или do-while и все три выражения в круглых скобках цикла for.
Перед входом в вызываемую функцию. Порядок, в котором вычисляются аргументы, не определен, но эта точка следования гарантирует, что все ее побочные эффекты проявятся на момент входа в функцию. В выражении f(i++) + g(j++) + h(k++) каждая из трёх переменных: i, j и k, принимает новое значение перед входом в f, g и h соответственно. Однако, порядок вызова функций f(), g(), h() не определён, следовательно, не определён и порядок инкремента i, j, k. Значения j и k в теле функции f оказываются неопределенными. Следует заметить, вызов функции нескольких аргументов f(a,b,c) не является случаем применения оператора-запятой и не определяет порядок вычисления значений аргументов.
При возврате из функции, на момент когда возвращаемое значение будет скопировано в вызывающий контекст. (Явно описана только в стандарте С++, в отличие от С.)
В объявлении с инициализацией на момент завершения вычисления инициализирующего значения, например, на момент завершения вычисления (1+i++) в int a = (1+i++);.
В Си++ перегруженные операторы выступают в роли функций, поэтому точкой следования является вызов перегруженного оператора.

Рассмотрим теперь несколько примеров, приводящих к неопределенному поведению:

int i, j;
...
X[i]=++i;
X[i++] = i;
j = i + X[++i];
i = 6 + i++ + 2000;
j = i++ + ++i;
i = ++i + ++i;

Во всех этих случаях невозможно предсказать результат вычислений. Конечно, эти примеры искусственны и опасность в них видна сразу. Рассмотрим фрагмент кода, найденный анализатором PVS-Studio в реальном приложении:

while (!(m_pBitArray[m_nCurrentBitIndex >> 5] &
         Powers_of_Two_Reversed[m_nCurrentBitIndex++ & 31]))
{}
return (m_nCurrentBitIndex - BitInitial - 1);

Компилятор может вычислить вначале как левый, так и правый аргумент оператора '&'. Это значит, что переменная m_nCurrentBitIndex может быть уже увеличена на единицу при вычислении "m_pBitArray[m_nCurrentBitIndex >> 5]". А может быть ещё не увеличена.

Этот код может долго и исправно работать. Однако следует учитывать, что гарантированно корректно он будет себя вести только при сборке определенной версией компилятора с неизменным набором параметров компиляции. Корректный вариант кода:

while (!(m_pBitArray[m_nCurrentBitIndex >> 5] &
         Powers_of_Two_Reversed[m_nCurrentBitIndex & 31]))
{ ++m_nCurrentBitIndex; }
return (m_nCurrentBitIndex - BitInitial);

Этот код более не содержит неоднозначностей. Заодно исчезла магическая константа "-1".

Программисты часто считают, что неопределенное поведение может возникать только при использовании постинкремента, в то время как преинкремент безопасен. Это не так. Рассмотрим пример общения на эту тему.

Вопрос:

Скачал ознакомительную версию PVS-Studio, прогнал свой проект и получил такое предупреждение: V567 Undefined behavior. The 'i_acc' variable is modified while being used twice between sequence points.

Код

i_acc = (++i_acc) % N_acc;

Как мне кажется, здесь нет undefined behavior, так как переменная i_acc не участвует в выражении дважды.

Ответ:

Неопределенное поведение здесь есть. Другое дело, что вероятность проявления ошибки весьма мала. Оператор '=' не является точкой следования. Это значит, что вначале компилятор может поместить значение переменной i_acc в регистр. Затем увеличить значение в регистре. После чего вычислить выражение и записать результат в переменную i_acc. После чего вновь записать в эту переменную регистр с увеличенным значением. В результате мы получим код вида:

REG = i_acc;
REG++;
i_acc = (REG) % N_acc;
i_acc = REG;

Компилятор имеет на это полное право. Конечно, на практике, скорее всего он сразу увеличит значение переменной, и тогда всё будет работать так, как ожидает программист. Но полагаться на это нельзя.