Similitud de Instrucciones en Código de Fuente C #.

Guillermo de la Torre - Hernán Sarmiento

Descripcion del Problema | Descripción de los Datos | Limpieza de los Datos | Exploración de Datos | Resultados | Conclusiones

Descripción del Problema

La Minería de Repositorios de Software está enfocada en estudiar los artefactos producidos durante el desarrollo de software para apoyar en la toma de las decisiones pertinentes. Un interés recurrente de investigación en esta área es la caracterización de la evolución de artefactos como los correos electrónicos, la corrección de errores y en especial los cambios ocurridos en el código fuente.

Existen varias alternativas para analizar los cambios producidos entre pares de revisiones, probablemente consecutivas, de un mismo archivo de código fuente. Por lo general las estrategias dependen de una representación particular del código fuente, la detección de pares de instrucciones similares y finalmente la generación de un conjunto de operaciones para transformar la versión original en la modificada.

Una estrategia empleada frecuentemente es la de representar cada versión de código fuente mediante Árboles de Sintaxis Abstracta (AST: Abstract Syntax Tree), cuyos nodos son comparados para producir un conjunto de pares similares a partir del cual son inferidas las operaciones para transformar el AST original en el AST modificado. Las operaciones de transformación que pueden ser entonces inferidas son inserción, movimiento y alineación de nodos, actualización de valores de nodos y eliminación de subárboles. El conjunto final de las operaciones producidas, conocido como el Edit Script, describe las diferencias entre ambos árboles y consecuentemente los cambios ocurridos desde la versión original respecto a la modificada.

Representación de un Abstract Syntax Tree

Representación de un Abstract Syntax Tree

Chawathe et al. [1] presentó algoritmos para generar un conjunto de pares de nodos similares y un script de transformación a partir de tal conjunto. Generar un Edit Script de costo mínimo es un problema NP completo, pero la solución introducida en [1] es considerada como óptima. Sin embargo, su lógica para generar el conjunto de pares de nodos similares fue inicialmente concebida para estructuras jerárquicas como las de los documentos Latex y partiendo de propiedades que no son aplicables sobre los AST de  código fuente.

La mayoría de los algoritmos existentes se reducen a resolver el sub-problema de generar el conjunto de los pares de nodos similares que serán entradas del algoritmo [1], especializado en finalmente obtener los cambios producidos entre ambas versiones de código fuente como un Edit Script. Algoritmos como [2] y [3] aplican heurísticas de matching para determinar similitud entre tales nodos. Los criterios generalmente varían dependiendo de si los nodos son hojas o no en el AST y han sido validados con resultados aceptables sobre patrones comunes, incluso de renombramiento de los identificadores de entidades como variables, tipos y funciones. Sin embargo, sospechamos que tomando cuenta el dominio específico de las instrucciones que los nodos representan (por ejemplo, el lenguaje de programación al que pertenecen y su estructura) pueden mejorarse los actuales resultados de matching.

La siguiente figura muestra una anomalía en los cambios detectados cuando las construcciones sintácticas del lenguaje son ignoradas. Dados dos fragmentos de código consecutivos, de izquierda a derecha el original y el modificado respectivamente, los cambios sucedidos son dos actualizaciones: los tipos de las variables. Sin embargo, el algoritmo ChangeDistiller y su criterio de similitud para nodos hojas infiere <“int i = 0;”, “uint j = 0;”> como un par de nodos similares. En consecuencia produce la inserción de “float i = 0;”, la actualización de la instrucción “int i = 0;” por “uint j = 0;” y la eliminación de “decimal j = 0”. Un mejor resultado pudo haberse obtenido, por ejemplo considerando que al tratarse de declaraciones de variables los nombres pudieron haber sido determinantes. Este caso es francamente una versión minimalista de nuestra investigación, cuyo proyecto actual surge con el propósito de ensayar métodos de exploración del problema y la obtención de resultados preliminares que justifiquen o descarten una futura profundización basada en los distintos tipos de nodos que pudieran existir en un AST de C#.

Anomalías de cambios detectados cuando las reglas sintácticas son ignoradas

Anomalías de cambios detectados cuando las reglas sintácticas son ignoradas

Nuestro objetivo actual es explorar el impacto en la determinación de los pares de nodos similares dado un sentido más consciente de la sintaxis del lenguaje en que estarían escritas ambas versiones del código fuente. En particular, estamos interesados en analizar el comportamiento de los criterios existentes a la hora de comparar declaraciones de campos de clases (variables de clase), aplicados sobre ASTs de código fuente C#, contrastando perspectivas ignorantes o conscientes de la sintaxis del lenguaje.

Nuestros datos serán pares de nodos que representan instrucciones de C#, recolectados a partir de pares de versiones consecutivas de ficheros, original y modificado, de un proyecto local Git. Una declaración de campo tiene la siguiente anatomía:

FIELD DECLARATION = ATTRIBUTES MODIFIERS Id [= INITIALIZER] 
(ej: [Serializable] public static table = new Table(“Customer”);)

A partir de la cual ensayamos las siguientes representaciones a la hora de comparar basado en el algoritmo Change Distiller [2]:

  • Leaf Raw: El nodo es considerado una hoja en el árbol, se consideran similares aquellos cuyo valor del nodo superen un umbral de similitud (>=t1).
  • Leaf: Similar al anterior, pero al comparar no se consideran los atributos ni los modificadores, intuitivamente clasificados como stop words.
  • Inner Raw: El nodo es considerado un nodo interno. Se consideran similares si tanto los valores (>=t1) como sus hijos son similares (>=t2) o si simplemente los hijos son similares a un nivel suficiente (>=t3;t3>t2).

Referencias

  • [1] S. S. Chawathe, A. Rajaraman, H. Garcia-Molina, and J. Widom, “Change detection in hierarchically structured information,” ACM SIGMOD Rec., vol. 25, no. 2, pp. 493–504, Jun. 1996.
  • [2] B. Fluri, M. Wuersch, M. PInzger, and H. Gall, “Change Distilling:Tree Differencing for Fine-Grained Source Code Change Extraction,” IEEE Trans. Softw. Eng., vol. 33, no. 11, pp. 725–743, Nov. 2007.
  • [3] J.-R. Falleri, F. Morandat, X. Blanc, M. Martinez, and M. Montperrus, “Fine-grained and accurate source code differencing,” in Proceedings of the 29th ACM/IEEE international conference on Automated software engineering - ASE ’14, 2014, pp. 313–324.