c++ - ¿Por qué i=v[i++] no está definido?

language-lawyer (8)

Desde el estándar de C ++ (C ++ 11), §1.9.15 que trata el orden de evaluación, es el siguiente código de ejemplo:

void g(int i, int* v) { i = v[i++]; // the behavior is undefined }

Como se señaló en el ejemplo de código, el comportamiento no está definido.

(Nota: la respuesta a otra pregunta con el constructo ligeramente diferente i + i++ , ¿Por qué a = i + i ++ no está definido y no es un comportamiento no especificado , podría aplicarse aquí? La respuesta es esencialmente que el comportamiento no está definido por razones históricas y no está fuera Sin embargo, el estándar parece implicar una cierta justificación para que esto no esté definido (ver cita inmediatamente a continuación). Además, esa pregunta vinculada indica que el comportamiento no debe ser especificado , mientras que en esta pregunta me pregunto por qué no está bien el comportamiento. especificado .)

El razonamiento dado por el estándar para el comportamiento indefinido es el siguiente:

Si un efecto secundario en un objeto escalar no tiene secuencia en relación con otro efecto secundario en el mismo objeto escalar o un cálculo de valor utilizando el valor del mismo objeto escalar, el comportamiento es indefinido.

En este ejemplo, creo que la subexpresión i++ se evaluaría completamente antes de evaluar la subexpresión v[...] , y que el resultado de la evaluación de la subexpresión es i (antes del incremento), pero que el valor de i es el valor incrementado después de esa subexpresión ha sido completamente evaluado. Creo que en ese momento (después de que se haya evaluado completamente la subexpresión i++ ), se lleva a cabo v[...] la evaluación v[...] , seguida de la asignación i = ...

Por lo tanto, aunque el incremento de i tiene sentido, no obstante, creo que esto debería definirse .

¿Por qué es este comportamiento indefinido?

En este ejemplo, creo que la subexpresión i ++ se evaluaría completamente antes de evaluar la subexpresión v, y que el resultado de la evaluación de la subexpresión es i (antes del incremento), pero que el valor de i es el valor incrementado después de esa subexpresión ha sido completamente evaluado.

El incremento en i++ debe evaluarse antes de indexar v y, por lo tanto, antes de asignarlo a i , pero no es necesario que el almacenamiento del valor de ese incremento en la memoria ocurra antes. En la declaración i = v[i++] hay dos suboperaciones que modifican i (es decir, terminarán causando un almacenamiento de un registro en la variable i ). La expresión i++ es equivalente a x=i+1 , i=x , y no hay ningún requisito de que ambas operaciones deban realizarse de forma secuencial:

x = i+1; y = v[i]; i = y; i = x;

Con esa expansión, el resultado de i no está relacionado con el valor en v[i] . En una expansión diferente, la asignación i = x podría tener lugar antes de la asignación i = y , y el resultado sería i = v[i]

Pensaría que la subexpresión i ++ se evaluaría completamente antes de evaluar la subexpresión v

Pero ¿por qué piensas eso?

Una razón histórica para que este código sea UB es permitir que las optimizaciones del compilador muevan los efectos secundarios en cualquier lugar entre los puntos de secuencia. Cuantos menos puntos de secuencia, más oportunidades potenciales de optimizar, pero los programadores más confundidos. Si el código dice:

a = v[i++];

La intención de la norma es que el código emitido puede ser:

a = v[i]; ++i;

que podrían ser dos instrucciones donde:

tmp = i; ++i; a = v[tmp];

Serían más de dos.

El "código optimizado" se rompe cuando a es i , pero el estándar permite la optimización de todos modos , diciendo que el comportamiento del código original no está definido cuando a es i .

El estándar fácilmente podría decir que i++ debe evaluarse antes de la asignación como usted sugiere. Entonces el comportamiento estaría completamente definido y la optimización estaría prohibida. Pero no es así como C y C ++ hacen negocios.

También tenga en cuenta que muchos ejemplos presentados en estas discusiones hacen que sea más fácil decir que hay UB alrededor de lo que es en general. Esto lleva a la gente a decir que es "obvio" que se debe definir el comportamiento y que se debe prohibir la optimización. Pero considere:

void g(int *i, int* v, int *dst) { *dst = v[(*i)++]; }

El comportamiento de esta función se define cuando i != dst , y en ese caso querría tener toda la optimización que puede obtener (por lo que C99 introduce restrict , para permitir más optimizaciones que C89 o C ++). Para darle la optimización, el comportamiento no está definido cuando i == dst . Los estándares C y C ++ marcan una línea fina cuando se trata de crear alias, entre un comportamiento indefinido que no espera el programador y prohibir optimizaciones deseables que fallan en ciertos casos. La cantidad de preguntas sobre el mismo en SO sugiere que los interrogadores preferirían un poco menos de optimización y un poco más de comportamiento definido, pero aún así no es sencillo trazar la línea.

Aparte de si el comportamiento está completamente definido es el problema de si debe ser UB, o simplemente un orden de ejecución no especificado de ciertas operaciones bien definidas correspondientes a las subexpresiones. La razón por la que C se usa para UB tiene que ver con la idea de puntos de secuencia, y el hecho de que el compilador no tenga realmente una noción del valor de un objeto modificado, hasta el siguiente punto de secuencia. Entonces, en lugar de restringir el optimizador diciendo que "el valor" cambia en algún punto no especificado, el estándar simplemente dice (parafraseando): (1) cualquier código que se base en el valor de un objeto modificado antes del siguiente punto de secuencia, tiene UB; (2) cualquier código que modifique un objeto modificado tiene UB. Donde un "objeto modificado" es cualquier objeto que se habría modificado desde la última secuencia en uno o más de los órdenes legales de evaluación de las subexpresiones.

Otros lenguajes (p. Ej., Java) abarcan todo el proceso y definen completamente el orden de expresión de los efectos secundarios, por lo que definitivamente hay un caso en contra del enfoque de C. C ++ simplemente no acepta ese caso.

Compartiría sus argumentos si el ejemplo fuera v[++i] , pero como i++ modifica i como efecto secundario, no está definido cuando se modifica el valor. El estándar probablemente podría imponer un resultado de una manera u otra, pero no hay una manera verdadera de saber cuál debería ser el valor de i : (i + 1) o (v[i + 1]) .

Hay dos reglas.

La primera regla se refiere a las escrituras múltiples que dan lugar a un "peligro de escritura-escritura": el mismo objeto no se puede modificar más de una vez entre dos puntos de secuencia.

La segunda regla es sobre "peligros de lectura-escritura". Es esto: si un objeto se modifica en una expresión, y también se accede, entonces todos los accesos a su valor deben ser con el propósito de calcular el nuevo valor.

Expresiones como i++ + i++ y su expresión i = v[i++] violan la primera regla. Modifican un objeto dos veces.

Una expresión como i + i++ viola la segunda regla. La subexpresión i de la izquierda observa el valor de un objeto modificado, sin involucrarse en el cálculo de su nuevo valor.

Entonces, i = v[i++] viola una regla diferente (escritura incorrecta) de i + i++ (lectura / escritura incorrecta).

Las reglas son demasiado simplistas, lo que da lugar a clases de expresiones desconcertantes. Considera esto:

p = p->next = q

Esto parece tener una dependencia de flujo de datos sensata que está libre de peligros: la asignación p = no puede realizarse hasta que se conozca el nuevo valor. El nuevo valor es el resultado de p->next = q . El valor q no debe "correr por delante" y entrar en p , de manera que p->next se vea afectado.

Sin embargo, esta expresión rompe la segunda regla: p se modifica, y también se usa para un propósito no relacionado con calcular su nuevo valor, es decir, ¡determinar la ubicación de almacenamiento donde se coloca el valor de q !

Entonces, perversamente, a los compiladores se les permite evaluar parcialmente p->next = q para determinar que el resultado es q , y almacenarlo en p , y luego regresar y completar la asignación p->next = . O eso parece.

Una cuestión clave aquí es, ¿cuál es el valor de una expresión de asignación? El estándar C dice que el valor de una expresión de asignación es el del valor l, después de la asignación . Pero eso es ambiguo: podría interpretarse como que significa "el valor que tendrá el lvalue, una vez que la asignación tenga lugar" o como "el valor que se puede observar en el lvalue después de que la asignación haya tenido lugar". En C ++, esto queda claro con la frase "[i] n todos los casos, la asignación se secuencia después del cálculo del valor de los operandos derecho e izquierdo, y antes del cálculo del valor de la expresión de asignación", por lo que p = p->next = q parece ser válido en C ++, pero dudoso C.

La razón no es sólo histórica. Ejemplo:

int f(int& i0, int& i1) { return i0 + i1++; }

Ahora, qué pasa con esta llamada:

int i = 3; int j = f(i, i);

Ciertamente es posible poner requisitos en el código en f para que el resultado de esta llamada esté bien definido (Java hace esto), pero C y C ++ no imponen restricciones; Esto da más libertad a los optimizadores.

Piense en las secuencias de operaciones de la máquina necesarias para cada una de las siguientes declaraciones de asignación, asumiendo que las declaraciones dadas están en efecto:

extern int *foo(void); extern int *p; *p = *foo(); *foo() = *p;

Si la evaluación del subíndice en el lado izquierdo y el valor en el lado derecho no tienen secuencia, las formas más eficientes de procesar las dos llamadas de función probablemente serían algo como:

[For *p = *foo()] call foo (which yields result in r0 and trashes r1) load r0 from address held in r0 load r1 from address held in p store r0 to address held in r1 [For *foo() = *p] call foo (which yields result in r0 and trashes r1) load r1 from address held in p load r1 from address held in r1 store r1 to address held in r0

En cualquier caso, si p o * p se leyeron en un registro antes de la llamada a foo, entonces, a menos que "foo" prometa no molestar ese registro, el compilador deberá agregar un paso adicional para guardar su valor antes de llamar "foo" , y otro paso adicional para restaurar el valor después. Ese paso adicional podría evitarse usando un registro que "foo" no molestará, pero eso solo ayudaría si existiera un registro que no tuviera un valor necesario para el código circundante.

Permitir que el compilador lea el valor de "p" antes o después de la llamada a la función, en su tiempo libre, permitirá que ambos patrones anteriores se manejen de manera eficiente. Requerir que la dirección del operando de la izquierda de "=" siempre se evalúe antes de que el lado derecho probablemente haga que la primera asignación anterior sea menos eficiente de lo que podría ser, y exigiendo que la dirección del operando de la izquierda sea evaluada después del lado derecho haría la segunda asignación menos eficiente.

Se refiere específicamente al estándar de C ++ 11, así que voy a responder con la respuesta de C ++ 11. Sin embargo, es muy similar a la respuesta de C ++ 03, pero la definición de secuenciación es diferente.

C ++ 11 define una secuencia antes de la relación entre evaluaciones en un solo hilo. Es asimétrica, transitiva y por pares. Si alguna evaluación A no está secuenciada antes que alguna evaluación B y B tampoco está secuenciada antes de A, entonces las dos evaluaciones no tienen secuencia .

La evaluación de una expresión incluye tanto los cálculos de valor (como el valor de alguna expresión) y los efectos secundarios. Una instancia de un efecto secundario es la modificación de un objeto, que es el más importante para responder una pregunta. Otras cosas también cuentan como efectos secundarios. Si un efecto secundario no está relacionado con otro efecto o cálculo de valor en el mismo objeto, entonces su programa tiene un comportamiento indefinido.

Así que esa es la configuración. La primera regla importante es:

Cada cálculo de valor y efecto secundario asociado con una expresión completa se secuencia antes de cada cálculo de valor y efecto secundario asociado con la siguiente expresión completa a evaluar.

Por lo tanto, cualquier expresión completa se evalúa completamente antes de la siguiente expresión completa. En su pregunta, solo estamos tratando con una expresión completa, a saber, i = v[i++] , por lo que no debemos preocuparnos por esto. La siguiente regla importante es:

Excepto donde se indique, las evaluaciones de los operandos de los operadores individuales y de las subexpresiones de las expresiones individuales no tienen secuencia.

Eso significa que en a + b , por ejemplo, la evaluación de a y b tienen secuencia (pueden evaluarse en cualquier orden). Ahora para nuestra regla final importante:

Los cálculos de valores de los operandos de un operador se secuencian antes del cálculo de valores del resultado del operador.

Entonces para a + b , las relaciones secuenciadas antes pueden representarse por un árbol donde una flecha dirigida representa la relación secuenciada antes:

a + b (value computation) ^ ^ | | a b (value computation)

Si se producen dos evaluaciones en ramas separadas del árbol, no tienen secuencia, por lo que este árbol muestra que las evaluaciones de a y b tienen secuencia entre sí.

Ahora, hagamos lo mismo con su ejemplo i = v[i++] . Hacemos uso del hecho de que v[i++] se define como equivalente a *(v + (i++)) . También utilizamos algunos conocimientos adicionales sobre la secuenciación del incremento postfix:

El cálculo del valor de la expresión ++ se secuencia antes de la modificación del objeto operando.

Así que aquí vamos (un nodo del árbol es un cálculo de valor a menos que se especifique como un efecto secundario):

i = v[i++] ^ ^ | | i★ v[i++] = *(v + (i++)) ^ | v + (i++) ^ ^ | | v ++ (side effect on i)★ ^ | i

Aquí puede ver que el efecto secundario en i , i++ , está en una rama separada del uso de i delante del operador de asignación (marqué cada una de estas evaluaciones con una ★). ¡Así que definitivamente tenemos un comportamiento indefinido! Recomiendo encarecidamente dibujar estos diagramas si alguna vez se pregunta si su secuencia de evaluaciones le causará problemas.

Así que ahora tenemos la pregunta sobre el hecho de que el valor de i antes del operador de asignación no importa, porque escribimos sobre él de todos modos. Pero en realidad, en el caso general, eso no es cierto. Podemos anular el operador de asignación y hacer uso del valor del objeto antes de la asignación. A la norma no le importa que no utilicemos ese valor; las reglas se definen de tal manera que tener cualquier cálculo de valor sin secuencia con un efecto secundario será un comportamiento indefinido. Sin peros. Este comportamiento indefinido está ahí para permitir que el compilador emita más código optimizado. Si agregamos secuencia para el operador de asignación, esta optimización no se puede emplear.

Voy a diseñar una computadora patológica ¹ . Es un sistema de subprocesos múltiples, de alta latencia y de un solo subproceso con uniones de subprocesos que funciona con instrucciones de nivel de byte. Entonces, hace una solicitud para que algo suceda, luego la computadora ejecuta (en su propio "subproceso" o "tarea") un conjunto de instrucciones a nivel de byte, y una cierta cantidad de ciclos más tarde, la operación está completa.

Mientras tanto, el hilo principal de ejecución continúa:

void foo(int v[], int i){ i = v[i++]; }

se convierte en pseudocódigo:

input variable i // = 0x00000000 input variable v // = &[0xBAADF00D, 0xABABABABAB, 0x10101010] task get_i_value: GET_VAR_VALUE<int>(i) reg indx = WAIT(get_i_value) task write_i++_back: WRITE(i, INC(indx)) task get_v_value: GET_VAR_VALUE<int*>(v) reg arr = WAIT(get_v_value) task get_v[i]_value = CALC(arr + sizeof(int)*indx) reg pval = WAIT(get_v[i]_value) task read_v[i]_value = LOAD_VALUE<int>(pval) reg got_value = WAIT(read_v[i]_value) task write_i_value_again = WRITE(i, got_value) (discard, discard) = WAIT(write_i++_back, write_i_value_again)

Entonces notará que no write_i++_back en write_i++_back hasta el final, al mismo tiempo que esperé en write_i_value_again (valor que write_i_value_again de v[] ). Y, de hecho, esas escrituras son las únicas escrituras en la memoria.

Imagínese si escribir en la memoria es la parte realmente lenta de este diseño de computadora, y se agrupan en una cola de cosas que se procesan mediante una unidad de modificación de memoria paralela que hace las cosas por byte.

Por lo tanto, la write(i, 0x00000001) y la write(i, 0xBAADF00D) ejecutan sin orden y en paralelo. Cada uno se convierte en escrituras de nivel de byte, y se ordenan aleatoriamente.

Terminamos escribiendo 0x00 luego 0xBA al byte alto, luego 0xAD y 0x00 al siguiente byte, luego 0xF0 0x00 al siguiente byte, y finalmente 0x0D 0x01 al byte bajo. El valor resultante en i es 0xBA000001 , que pocos esperarían, pero sería un resultado válido para su operación indefinida.

Ahora, todo lo que hice allí resultó en un valor no especificado. No hemos estrellado el sistema. Pero el compilador sería libre de hacerlo completamente indefinido; tal vez el envío de dos solicitudes de este tipo al controlador de memoria para la misma dirección en el mismo lote de instrucciones realmente bloquee el sistema. Esa sería una forma "válida" de compilar C ++ y un entorno de ejecución "válido".

Recuerde, este es un lenguaje donde la restricción del tamaño de los punteros a 8 bits sigue siendo un entorno de ejecución válido. C ++ permite la compilación de objetivos más bien wonkey.

¹ : Como se señala en el comentario de @ SteveJessop a continuación, el chiste es que esta computadora patológica se comporta de manera muy parecida a una computadora de escritorio moderna, hasta que se pasa a las operaciones de nivel de byte. La escritura int no atómica por parte de una CPU no es tan rara en algunos hardware (por ejemplo, cuando la int no está alineada de la manera en que la CPU quiere que esté alineada).