Hispanopedia WikiLa bisección es un método utilizado en el desarrollo de software para identificar conjuntos de cambios que resultan en una modificación específica del comportamiento. Se emplea principalmente para encontrar el parche que introdujo un error . Otra aplicación consiste en encontrar el parche que corrigió indirectamente un error.
Descripción general
El proceso de localizar el conjunto de cambios que introdujo una regresión específica fue descrito como "aislamiento de cambios de origen" en 1997 por Brian Ness y Viet Ngo de Cray Research . Las pruebas de regresión se realizaron en los compiladores de Cray en ediciones que comprendían uno o más conjuntos de cambios. Las ediciones con regresiones conocidas no podían validarse hasta que los desarrolladores abordaran el problema. El aislamiento de cambios de origen redujo la causa a un único conjunto de cambios que luego podía excluirse de las ediciones, desbloqueándolas con respecto a este problema, mientras el autor del cambio trabajaba en una solución. Ness y Ngo describieron los métodos de búsqueda lineal y binaria para realizar este aislamiento. [ 1 ]
La búsqueda binaria de código tiene como objetivo minimizar el esfuerzo necesario para encontrar un conjunto de cambios específico. Emplea un algoritmo de divide y vencerás que depende del acceso al historial del código, el cual suele conservarse mediante el control de versiones en un repositorio de código .
Método de bisección
algoritmo de bisección de código
El historial de código tiene la estructura de un grafo dirigido acíclico que puede ordenarse topológicamente . Esto permite utilizar un algoritmo de búsqueda de divide y vencerás que:
- divide el espacio de búsqueda de las revisiones candidatas
- pruebas para el comportamiento en cuestión
- reduce el espacio de búsqueda dependiendo del resultado de la prueba
- Reitera los pasos anteriores hasta que quede un rango con como máximo un candidato a parche bisecable.
Complejidad algorítmica
La bisección está en LSPACE con una complejidad algorítmica deconque denota el número de revisiones en el espacio de búsqueda, y es similar a una búsqueda binaria .
Propiedades deseables del repositorio
Para la búsqueda binaria de código, es deseable que cada revisión en el espacio de búsqueda se pueda construir y probar de forma independiente.
Monotonicidad
Para que el algoritmo de bisección identifique un único conjunto de cambios que haya provocado la modificación del comportamiento evaluado, este debe cambiar de forma monótona en todo el espacio de búsqueda. En el caso de una función booleana, como una prueba de aprobado/reprobado, esto significa que solo cambia una vez en todos los conjuntos de cambios entre el inicio y el final del espacio de búsqueda.
Si existen varios conjuntos de cambios en el espacio de búsqueda donde el comportamiento que se está probando varía entre falso y verdadero, el algoritmo de bisección encontrará uno de ellos, pero no necesariamente será la causa raíz del cambio de comportamiento entre el inicio y el final del espacio de búsqueda. La causa raíz podría ser otro conjunto de cambios o una combinación de dos o más conjuntos de cambios en el espacio de búsqueda. Para ayudar a solucionar este problema, las herramientas automatizadas permiten ignorar conjuntos de cambios específicos durante una búsqueda por bisección.
Soporte de automatización
Aunque el método de bisección puede completarse manualmente, una de sus principales ventajas es que se puede automatizar fácilmente. [ 1 ] Por lo tanto, puede integrarse en los procesos de automatización de pruebas existentes: los fallos en las pruebas de regresión automatizadas exhaustivas pueden activar la bisección automatizada para localizar fallos. Ness y Ngo se centraron en su potencial en el entorno de entrega continua de Cray, en el que el conjunto de cambios defectuosos aislado automáticamente podía excluirse automáticamente de las compilaciones. [ 2 ]
Los sistemas de control de versiones Fossil , Git y Mercurial tienen funcionalidad integrada para la búsqueda binaria de código. [ 3 ] [ 4 ] [ 5 ] El usuario puede iniciar una sesión de búsqueda binaria con un rango específico de revisiones, de las cuales el sistema de control de versiones propone una revisión para probar. El usuario indica al sistema si la revisión probada es "buena" o "mala", y el proceso se repite hasta que se identifica la revisión "mala" específica. Otros sistemas de control de versiones, como Bazaar o Subversion , admiten la búsqueda binaria mediante complementos [ 6 ] o scripts externos. [ 7 ]
Phoronix Test Suite puede realizar una búsqueda binaria automáticamente para detectar regresiones de rendimiento.
Véase también
- Depuración delta (generalización de la búsqueda de la causa mínima de un error)
- Anotación § Control de versiones (determinación de los conjuntos de cambios que editaron una línea en un archivo)
Referencias
- 1 2 Ness, Brian; Ngo, Viet (1997). Regression containment through source change isolation . Computer Software and Applications Conference. IEEE. doi : 10.1109/CMPSAC.1997.625082 .
- ↑ Zeller, Andreas (1999). Ayer mi programa funcionaba. Hoy no. ¿Por qué? Conferencia Europea de Ingeniería de Software. Toulouse, Francia. doi : 10.1145/318774.318946 .
- ↑ "Fósil: Ayuda: bisect" . www.fossil-scm.org . Consultado el 3 de septiembre de 2020 .
- ↑ "git-bisect(1)" . git-scm.com . Consultado el 5 de agosto de 2017 .
- ↑ "hg" . Selenic.com . Consultado el 9 de enero de 2017 .
- ↑ "bisect - Encuentra la revisión que introduce un error usando una búsqueda binaria — Documentación de Bazaar 2.8.0dev1" . Doc.bazaar.canonical.com . Consultado el 9 de enero de 2017 .
- ↑ "svn-bisect" . Metacpan.org . Consultado el 3 de agosto de 2022 .
- Control de versiones
- Sistemas de control de versiones
- proceso de desarrollo de software
- Algoritmos