c++ - ¿En qué punto del bucle el desbordamiento de enteros se convierte en un comportamiento indefinido?

undefined-behavior integer-overflow (12)

Este es un ejemplo para ilustrar mi pregunta que involucra un código mucho más complicado que no puedo publicar aquí.

#include <stdio.h> int main() { int a = 0; for (int i = 0; i < 3; i++) { printf("Hello/n"); a = a + 1000000000; } }

Este programa contiene un comportamiento indefinido en mi plataforma porque se desbordará en el tercer ciclo.

¿Eso hace que todo el programa tenga un comportamiento indefinido, o solo después de que realmente ocurra el desbordamiento ? ¿Podría el compilador llegar a la conclusión de que a desbordamiento se desbordará para que pueda declarar todo el ciclo indefinido y no molestarse en ejecutar printfs a pesar de que todos suceden antes del desbordamiento?

_{(Etiquetado C y C ++ aunque son diferentes porque me interesarían las respuestas para ambos lenguajes si son diferentes).}

La respuesta principal es un error (pero común) erróneo:

El comportamiento indefinido es una propiedad de tiempo de ejecución *. ¡ NO PUEDE "viajar en el tiempo"!

Ciertas operaciones están definidas (según el estándar) para tener efectos secundarios y no se pueden optimizar. Las operaciones que realizan E / S o que acceden a variables volatile entran en esta categoría.

Sin embargo , hay una advertencia: UB puede ser cualquier comportamiento, incluido el comportamiento que deshace las operaciones anteriores. Esto puede tener consecuencias similares, en algunos casos, para optimizar el código anterior.

De hecho, esto es consistente con la cita en la respuesta superior (énfasis mío):

Una implementación conforme que ejecute un programa bien formado producirá el mismo comportamiento observable que una de las ejecuciones posibles de la instancia correspondiente de la máquina abstracta con el mismo programa y la misma entrada.
Sin embargo, si dicha ejecución contiene una operación indefinida, esta Norma Internacional no impone ningún requisito a la implementación que ejecute ese programa con esa entrada (ni siquiera con respecto a las operaciones que preceden a la primera operación indefinida).

Sí, esta cita dice "ni siquiera con respecto a las operaciones que preceden a la primera operación indefinida" , pero tenga en cuenta que esto se trata específicamente del código que se está ejecutando , no simplemente compilado.
Después de todo, el comportamiento indefinido que no se alcanza realmente no hace nada, y para que la línea que contiene UB se alcance realmente, ¡el código que precede debe ejecutarse primero!

Entonces, sí, una vez que se ejecuta UB , cualquier efecto de las operaciones anteriores se vuelve indefinido. Pero hasta que eso suceda, la ejecución del programa está bien definida.

Sin embargo, tenga en cuenta que todas las ejecuciones del programa que dan lugar a que esto suceda pueden optimizarse para programas equivalentes , incluidos los que realizan operaciones anteriores pero luego anulan sus efectos. En consecuencia, el código anterior se puede optimizar cuando hacerlo sería equivalente a deshacer sus efectos ; de lo contrario, no puede. Vea a continuación un ejemplo.

* Nota: Esto no es inconsistente con UB que ocurre en tiempo de compilación . Si el compilador puede probar que el código UB siempre se ejecutará para todas las entradas, entonces UB puede extenderse al tiempo de compilación. Sin embargo, esto requiere saber que todo el código anterior finalmente regresa , lo cual es un requisito importante. Nuevamente, vea a continuación un ejemplo / explicación.

Para hacer esto concreto, tenga en cuenta que el siguiente código debe imprimir foo y esperar su entrada, independientemente de cualquier comportamiento indefinido que le siga:

printf("foo"); getchar(); *(char*)1 = 1;

Sin embargo, también tenga en cuenta que no hay garantía de que foo permanecerá en la pantalla después de que ocurra el UB, o que el carácter que escribió ya no estará en el búfer de entrada; ambas operaciones se pueden "deshacer", lo que tiene un efecto similar al "viaje en el tiempo" de UB.

Si la getchar() línea no estuviera allí, sería legal que las líneas se optimizaran si y solo si eso sería indistinguible de la salida foo y luego "no hacerlo".

Si los dos serían indistinguibles o no dependería por completo de la implementación (es decir, de su compilador y biblioteca estándar). Por ejemplo, ¿puede printf bloquear su hilo aquí mientras espera que otro programa lea la salida? ¿O volverá de inmediato?

Si puede bloquear aquí, entonces otro programa puede negarse a leer su salida completa, y es posible que nunca regrese y, en consecuencia, UB puede que nunca ocurra.
Si puede regresar inmediatamente aquí, entonces sabemos que debe regresar, y por lo tanto, optimizarlo es completamente indistinguible de ejecutarlo y luego deshacer sus efectos.

Por supuesto, dado que el compilador sabe qué comportamiento es permisible para su versión particular printf , puede optimizar en consecuencia y, en consecuencia, printf puede optimizarse en algunos casos y no en otros. Pero, una vez más, la justificación es que esto sería indistinguible de las operaciones anteriores que no hicieron UB, no que el código anterior esté "envenenado" debido a UB.

Como esta pregunta es C y C ++ con doble etiqueta, intentaré abordar ambas. C y C ++ toman diferentes enfoques aquí.

En C, la implementación debe ser capaz de demostrar que se invocará el comportamiento indefinido para tratar el programa completo como si tuviera un comportamiento indefinido. En el ejemplo de OP, parecería trivial que el compilador lo pruebe y, por lo tanto, es como si todo el programa no estuviera definido.

Podemos ver esto en el Informe de defectos 109, que en su punto crucial pregunta:

Sin embargo, si el Estándar C reconoce la existencia por separado de "valores indefinidos" (cuya mera creación no implica totalmente "comportamiento indefinido"), una persona que realiza pruebas de compilación podría escribir un caso de prueba como el siguiente, y él / ella también podría esperar (o posiblemente exija) que una implementación conforme debería, como mínimo, compilar este código (y posiblemente también permitir que se ejecute) sin "falla".

int array1[5]; int array2[5]; int *p1 = &array1[0]; int *p2 = &array2[0]; int foo() { int i; i = (p1 > p2); /* Must this be "successfully translated"? */ 1/0; /* Must this be "successfully translated"? */ return 0; }
Entonces, la pregunta final es esta: ¿el código anterior debe "traducirse correctamente" (lo que sea que eso signifique)? (Véase la nota a pie de página adjunta a la subcláusula 5.1.1.3.)

y la respuesta fue:

El estándar C utiliza el término "valor indeterminado", no "valor indefinido". El uso de un objeto de valor indeterminado da como resultado un comportamiento indefinido. La nota al pie de la subcláusula 5.1.1.3 señala que una implementación es libre de producir cualquier número de diagnósticos, siempre y cuando un programa válido todavía se traduzca correctamente. Si una expresión cuya evacuación resultaría en un comportamiento indefinido aparece en un contexto donde se requiere una expresión constante, el programa que lo contiene no se ajusta estrictamente. Además, si cada posible ejecución de un programa dado resultaría en un comportamiento indefinido, el programa dado no se ajusta estrictamente. Una implementación conforme no debe dejar de traducir un programa estrictamente conforme simplemente porque alguna posible ejecución de ese programa resultaría en un comportamiento indefinido. Debido a que foo nunca podría ser llamado, el ejemplo dado debe ser traducido con éxito por una implementación conforme.

En C ++, el enfoque parece más relajado y sugeriría que un programa tiene un comportamiento indefinido independientemente de si la implementación puede probarlo estáticamente o no.

Tenemos [intro.abstrac]p5 que dice:

Una implementación conforme que ejecute un programa bien formado producirá el mismo comportamiento observable que una de las ejecuciones posibles de la instancia correspondiente de la máquina abstracta con el mismo programa y la misma entrada. Sin embargo, si alguna de estas ejecuciones contiene una operación indefinida, este documento no exige que la implementación ejecute ese programa con esa entrada (ni siquiera con respecto a las operaciones que preceden a la primera operación indefinida).

El comportamiento indefinido es, por definición, un área gris. Simplemente no puede predecir lo que hará o no hará; eso es lo que significa "comportamiento indefinido".

Desde tiempos inmemoriales, los programadores siempre han tratado de salvar los restos de la definición de una situación indefinida. Tienen un código que realmente quieren usar, pero que resulta ser indefinido, por lo que intentan argumentar: "Sé que no está definido, pero seguramente, en el peor de los casos, hará esto o esto; nunca hará eso". ". Y a veces estos argumentos son más o menos correctos, pero a menudo están equivocados. Y a medida que los compiladores se vuelven más y más inteligentes (o, algunas personas podrían decir, más astutos y más astutos), los límites de la pregunta siguen cambiando.

Entonces, realmente, si desea escribir código que garantice que funcione, y que siga funcionando durante mucho tiempo, solo hay una opción: evitar el comportamiento indefinido a toda costa. Verdaderamente, si incursionas en ello, volverá para atormentarte.

La respuesta de TartanLlama es correcta. El comportamiento indefinido puede ocurrir en cualquier momento, incluso durante el tiempo de compilación. Esto puede parecer absurdo, pero es una característica clave para permitir que los compiladores hagan lo que tienen que hacer. No siempre es fácil ser un compilador. Tienes que hacer exactamente lo que dice la especificación, cada vez. Sin embargo, a veces puede ser monstruosamente difícil demostrar que está ocurriendo un comportamiento particular. Si recuerda el problema de detención, es bastante trivial desarrollar software para el que no puede probar si completa o ingresa a un bucle infinito cuando se alimenta una entrada en particular.

Podríamos hacer que los compiladores sean pesimistas y compilen constantemente por temor a que la próxima instrucción sea uno de estos problemas de detención, como problemas, pero eso no es razonable. En cambio, le damos al compilador un pase: sobre estos temas de "comportamiento indefinido", están libres de cualquier responsabilidad. El comportamiento indefinido consiste en todos los comportamientos que son tan sutilmente nefastos que tenemos problemas para separarlos de los problemas de detención realmente desagradables y nefastos y demás.

Hay un ejemplo que me encanta publicar, aunque admito que perdí la fuente, así que tengo que parafrasear. Era de una versión particular de MySQL. En MySQL, tenían un búfer circular que estaba lleno de datos proporcionados por el usuario. Ellos, por supuesto, querían asegurarse de que los datos no desbordaran el búfer, por lo que hicieron una comprobación:

if (currentPtr + numberOfNewChars > endOfBufferPtr) { doOverflowLogic(); }

Parece lo suficientemente cuerdo. Sin embargo, ¿qué pasa si numberOfNewChars es realmente grande y se desborda? Luego se ajusta y se convierte en un puntero más pequeño que endOfBufferPtr , por lo que nunca se llamará a la lógica de desbordamiento. Entonces agregaron una segunda verificación, antes de esa:

if (currentPtr + numberOfNewChars < currentPtr) { detectWrapAround(); }

Parece que te has ocupado del error de desbordamiento del búfer, ¿verdad? Sin embargo, se envió un error que indica que este búfer se desbordó en una versión particular de Debian. Una investigación cuidadosa mostró que esta versión de Debian fue la primera en usar una versión particularmente innovadora de gcc. En esta versión de gcc, el compilador reconoció que currentPtr + numberOfNewChars nunca puede ser un puntero más pequeño que currentPtr porque el desbordamiento de los punteros es un comportamiento indefinido. ¡Eso fue suficiente para que gcc optimizara la verificación completa, y de repente no estaba protegido contra desbordamientos del búfer a pesar de que escribió el código para verificarlo!

Este fue el comportamiento de especificaciones. Todo era legal (aunque por lo que escuché, gcc hizo retroceder este cambio en la próxima versión). No es lo que consideraría un comportamiento intuitivo, pero si estira un poco su imaginación, es fácil ver cómo una ligera variante de esta situación podría convertirse en un problema para el compilador. Debido a esto, los escritores de especificaciones lo convirtieron en "Comportamiento indefinido" y declararon que el compilador podía hacer absolutamente cualquier cosa que quisiera.

Más allá de las respuestas teóricas, una observación práctica sería que durante mucho tiempo los compiladores han aplicado varias transformaciones en bucles para reducir la cantidad de trabajo realizado dentro de ellos. Por ejemplo, dado:

for (int i=0; i<n; i++) foo[i] = i*scale;

un compilador podría transformar eso en:

int temp = 0; for (int i=0; i<n; i++) { foo[i] = temp; temp+=scale; }

Guardando así una multiplicación con cada iteración de bucle. Una forma adicional de optimización, que los compiladores adaptaron con diversos grados de agresividad, convertiría eso en:

if (n > 0) { int temp1 = n*scale; int *temp2 = foo; do { temp1 -= scale; *temp2++ = temp1; } while(temp1); }

Incluso en máquinas con envoltura silenciosa en desbordamiento, eso podría funcionar mal si hubiera un número menor que n que, multiplicado por la escala, produciría 0. También podría convertirse en un bucle sin fin si la escala se leyera de la memoria más de una vez y algo cambió su valor inesperadamente (en cualquier caso donde "scale" podría cambiar a mitad de ciclo sin invocar a UB, un compilador no podría realizar la optimización).

Si bien la mayoría de estas optimizaciones no tendrían ningún problema en los casos en que se multipliquen dos tipos cortos sin signo para obtener un valor que esté entre INT_MAX + 1 y UINT_MAX, gcc tiene algunos casos en los que dicha multiplicación dentro de un ciclo puede hacer que el ciclo salga temprano . No he notado tales comportamientos derivados de las instrucciones de comparación en el código generado, pero es observable en los casos en que el compilador usa el desbordamiento para inferir que un bucle puede ejecutarse como máximo 4 o menos veces; no genera por defecto advertencias en casos en que algunas entradas causarían UB y otras no, incluso si sus inferencias hacen que se ignore el límite superior del bucle.

Para entender por qué el comportamiento indefinido puede ''viajar en el tiempo'' como lo expresa adecuadamente @TartanLlama , echemos un vistazo a la regla ''como si'':

1.9 Ejecución del programa

¹ Las descripciones semánticas en esta Norma Internacional definen una máquina abstracta no determinizada parametrizada. Esta Norma Internacional no impone ningún requisito sobre la estructura de las implementaciones conformes. En particular, no necesitan copiar o emular la estructura de la máquina abstracta. Más bien, se requieren implementaciones conformes para emular (solo) el comportamiento observable de la máquina abstracta como se explica a continuación.

Con esto, podríamos ver el programa como una ''caja negra'' con una entrada y una salida. La entrada podría ser entrada del usuario, archivos y muchas otras cosas. La salida es el "comportamiento observable" mencionado en el estándar.

El estándar solo define una asignación entre la entrada y la salida, nada más. Lo hace al describir un "cuadro negro de ejemplo", pero dice explícitamente que cualquier otro cuadro negro con el mismo mapeo es igualmente válido. Esto significa que el contenido del cuadro negro es irrelevante.

Con esto en mente, no tendría sentido decir que un comportamiento indefinido ocurre en un momento determinado. En la implementación de muestra del cuadro negro, podríamos decir dónde y cuándo sucede, pero el cuadro negro real podría ser algo completamente diferente, por lo que ya no podemos decir dónde y cuándo sucede. Teóricamente, un compilador podría, por ejemplo, decidir enumerar todas las entradas posibles y calcular previamente las salidas resultantes. Entonces el comportamiento indefinido habría sucedido durante la compilación.

El comportamiento indefinido es la inexistencia de un mapeo entre entrada y salida. Un programa puede tener un comportamiento indefinido para alguna entrada, pero un comportamiento definido para otra. Entonces la asignación entre entrada y salida es simplemente incompleta; hay una entrada para la cual no existe una asignación a la salida.
El programa en la pregunta tiene un comportamiento indefinido para cualquier entrada, por lo que la asignación está vacía.

Primero, permítanme corregir el título de esta pregunta:

El comportamiento indefinido no es (específicamente) del ámbito de la ejecución.

El comportamiento indefinido afecta a todos los pasos: compilación, vinculación, carga y ejecución.

Algunos ejemplos para consolidar esto, tenga en cuenta que ninguna sección es exhaustiva:

el compilador puede suponer que las porciones de código que contienen Comportamiento indefinido nunca se ejecutan y, por lo tanto, asume que las rutas de ejecución que los conducirían son código muerto. Vea lo que todo programador en C debe saber sobre el comportamiento indefinido de Chris Lattner.
el enlazador puede suponer que, en presencia de múltiples definiciones de un símbolo débil (reconocido por su nombre), todas las definiciones son idénticas gracias a la Regla de Una Definición
el cargador (en caso de que use bibliotecas dinámicas) puede asumir lo mismo, eligiendo así el primer símbolo que encuentre; esto generalmente se usa (ab) para interceptar llamadas usando trucos LD_PRELOAD en Unixes
la ejecución podría fallar (SIGSEV) si usa punteros colgantes

Esto es lo que da tanto miedo del comportamiento indefinido: es casi imposible predecir, con anticipación, qué comportamiento exacto ocurrirá, y esta predicción debe revisarse en cada actualización de la cadena de herramientas, sistema operativo subyacente, ...

Recomiendo ver este video de Michael Spencer (Desarrollador LLVM): CppCon 2016: My Little Optimizer: Undefined Behavior is Magic .

Si está interesado en una respuesta puramente teórica, el estándar C ++ permite un comportamiento indefinido para "viajar en el tiempo":

[intro.execution]/5: Una implementación conforme que ejecute un programa bien formado producirá el mismo comportamiento observable que una de las posibles ejecuciones de la instancia correspondiente de la máquina abstracta con el mismo programa y la misma entrada. Sin embargo, si dicha ejecución contiene una operación indefinida, esta Norma Internacional no impone ningún requisito a la implementación que ejecuta ese programa con esa entrada (ni siquiera con respecto a las operaciones que preceden a la primera operación indefinida)

Como tal, si su programa contiene un comportamiento indefinido, entonces el comportamiento de todo su programa es indefinido.

Suponiendo que int es de 32 bits, el comportamiento indefinido ocurre en la tercera iteración. Entonces, si, por ejemplo, el bucle solo fuera accesible condicionalmente, o pudiera terminarse condicionalmente antes de la tercera iteración, no habría un comportamiento indefinido a menos que la tercera iteración se alcance realmente. Sin embargo, en el caso de un comportamiento indefinido, toda la salida del programa es indefinida, incluida la salida que está "en el pasado" en relación con la invocación de un comportamiento indefinido. Por ejemplo, en su caso, esto significa que no hay garantía de ver 3 mensajes de "Hola" en la salida.

Técnicamente, según el estándar C ++, si un programa contiene un comportamiento indefinido, el comportamiento de todo el programa, incluso en tiempo de compilación (incluso antes de que se ejecute el programa), no está definido.

En la práctica, debido a que el compilador puede suponer (como parte de una optimización) que el desbordamiento no ocurrirá, al menos el comportamiento del programa en la tercera iteración del bucle (suponiendo una máquina de 32 bits) será indefinido, aunque es probable que obtenga resultados correctos antes de la tercera iteración. Sin embargo, dado que el comportamiento de todo el programa es técnicamente indefinido, no hay nada que impida que el programa genere resultados completamente incorrectos (incluida la ausencia de resultados), que se bloquee en el tiempo de ejecución en cualquier momento durante la ejecución, o incluso que no se compile por completo (ya que el comportamiento indefinido se extiende a tiempo de compilación).

El comportamiento indefinido proporciona al compilador más espacio para optimizar porque eliminan ciertas suposiciones sobre lo que debe hacer el código. Al hacerlo, no se garantiza que los programas que se basan en supuestos que impliquen un comportamiento indefinido funcionen como se espera. Como tal, no debe confiar en ningún comportamiento particular que se considere indefinido según el estándar C ++.

Un compilador de C o C ++ de optimización agresiva dirigido a un int 16 bits sabrá que el comportamiento al agregar 1000000000 a un tipo int no está definido .

Está permitido por cualquiera de los estándares hacer lo que quiera, que podría incluir la eliminación de todo el programa, dejando int main(){} .

Pero, ¿qué pasa con int s más grandes? Todavía no conozco un compilador que haga esto (y no soy un experto en diseño de compiladores C y C ++ de ninguna manera), pero imagino que en algún momento un compilador dirigido a un int 32 o superior descubrirá que el el bucle es infinito (no cambia) y, por lo tanto, eventualmente se desbordará Entonces, una vez más, puede optimizar la salida a int main(){} . El punto que estoy tratando de aclarar aquí es que a medida que las optimizaciones del compilador se vuelven progresivamente más agresivas, cada vez más construcciones de comportamiento indefinidas se manifiestan de maneras inesperadas.

El hecho de que su bucle sea infinito no está en sí mismo indefinido, ya que está escribiendo en la salida estándar en el cuerpo del bucle.

Una cosa que su ejemplo no considera es la optimización. a se establece en el bucle pero nunca se usa, y un optimizador podría resolver esto. Como tal, es legítimo que el optimizador descarte a completo, y en ese caso todo comportamiento indefinido se desvanece como la víctima de un boojum.

Sin embargo, por supuesto, esto en sí mismo no está definido, porque la optimización no está definida. :)