Utilidades de diferencia semántica [cerrado]

105

Estoy tratando de encontrar algunos buenos ejemplos de utilidades semánticas de diferenciación / fusión. El paradigma tradicional de comparar archivos de código fuente funciona comparando líneas y caracteres ... pero ¿hay alguna utilidad (para cualquier idioma) que realmente considere la estructura del código al comparar archivos?

Por ejemplo, los programas diff existentes informarán "diferencia encontrada en el carácter 2 de la línea 125. El archivo x contiene vacío, donde el archivo y contiene bool". Una herramienta especializada debería poder informar "Tipo de retorno del método doSomething () cambiado de void a bool".

Yo diría que este tipo de información semántica es en realidad lo que el usuario busca al comparar código, y debería ser el objetivo de las herramientas de programación de próxima generación. ¿Hay ejemplos de esto en las herramientas disponibles?

Jasonmray
fuente
3
Parece que se han realizado algunas investigaciones sobre la distancia de edición del árbol. Aplicar eso a los AST parece ser lo primero que debe intentar. (Si alguien quisiera intentar escribir este tipo de cosas.)
Jay Kominek
2
No estoy seguro de si realmente sería útil. una diferencia como la que mencionaste es más fácil de ver que de leer, especialmente si tienes una herramienta que resalta las diferencias dentro de una línea. la capacidad de reconocer si algún código se ha movido sin cambios sería más fácil y más útil, en mi humilde opinión.
TíoZeiv
2
@UncleZeiv Espero que esa característica se siga naturalmente de la naturaleza de la herramienta. Además, sería capaz de detectar que no hay cambios si alguien pasa y cambia las llaves o estilos de sangría, por ejemplo, o reorganiza el archivo para agrupar los métodos estáticos, etc.
jasonmray
8
Necesito esto en Visual Studio ahora. Obligar a los desarrolladores dentro de un equipo a usar la misma estructura de formato para facilitar las diferencias es pensar al revés. El código debe formatearse a algún estándar al registrarse, y cada vez que un desarrollador abre un archivo, debe formatearlo a su gusto. Me sorprende que este tipo de pensamiento no esté más extendido en este momento.
Langdon
3
En mi humilde opinión, este es un buen tema para SO. Si está de acuerdo, vote para "reabrir"
Ira Baxter

Respuestas:

37

Hemos desarrollado una herramienta que es capaz de abordar con precisión este escenario. Consulte http://www.semanticmerge.com

Se fusiona (y diferencia) en función de la estructura del código y no utiliza algoritmos basados ​​en texto, lo que básicamente le permite tratar casos como el siguiente, que implican una fuerte refactorización. También es capaz de representar tanto las diferencias como los conflictos de fusión, como puede ver a continuación:

ingrese la descripción de la imagen aquí

Y en lugar de confundirse con los bloques de texto que se mueven, ya que analiza primero, puede mostrar los conflictos por método (por elemento de hecho). Un caso como el anterior ni siquiera tendrá conflictos manuales que resolver.

ingrese la descripción de la imagen aquí

Es una herramienta de fusión consciente del idioma y ha sido genial poder finalmente responder a esta pregunta SO :-)

pablo
fuente
¿Es posible integrarlo con SVN?
Anterior
1
Sin embargo, las versiones de Linux y Mac son antiguas.
Michael Piefel
29

Eclipse ha tenido esta característica durante mucho tiempo. Se llama "Comparación de estructuras" y es muy agradable. Aquí hay una captura de pantalla de muestra para Java, seguida de otra para un archivo XML:

(Tenga en cuenta los iconos menos y más en los métodos en el panel superior).

Comparador de estructuras Java de Eclipse Comparador de estructuras XML de Eclipse

Hosam Aly
fuente
3
¿Structure Compare le permite fusionar cambios como otros editores de fusión de control de código fuente? Es decir, copie este método de esta versión a la otra versión.
Jonathan Parker
1
Sí, cuando selecciona un cambio o una diferencia (ya sea en los paneles superior o inferior), los botones de la barra de herramientas (que se muestran en las capturas de pantalla) le dan la opción de copiar el cambio de izquierda a derecha o viceversa.
Hosam Aly
1
Desafortunadamente, las capturas de pantalla ya no están visibles en tu respuesta (¡la más votada y aceptada!). ¿Podrías enviarlos de nuevo?
blubb
@blubb Gracias por notificarme. He corregido el error con la imagen de Java Comparer. Intentaré agregar una captura de pantalla para el Comparador de estructuras XML pronto.
Hosam Aly
1
¿Y eso funciona para otros lenguajes además de Java?
einpoklum
14

Para hacer bien las "comparaciones semánticas", es necesario comparar los árboles de sintaxis de los idiomas y tener en cuenta el significado de los símbolos. Una diferencia semántica realmente buena entendería la semántica del lenguaje y se daría cuenta de cuándo un bloque de código es equivalente en función a otro. Llegar tan lejos requiere un demostrador de teoremas, y aunque sería extremadamente lindo, actualmente no es práctico para una herramienta real.

Una aproximación viable de esto es simplemente comparar árboles de sintaxis e informar cambios en términos de estructuras insertadas, eliminadas, movidas o modificadas. Acercándose un poco más a una "comparación semántica", se podría informar cuando un identificador se cambia consistentemente en un bloque de código.

Consulte nuestro http://www.semanticdesigns.com/Products/SmartDifferencer/index.html para obtener un motor de comparación basado en árbol de sintaxis que funciona con muchos idiomas, que hace la aproximación anterior.

EDITAR Enero de 2010: Versiones disponibles para C ++, C #, Java, PHP y COBOL. El sitio web muestra ejemplos específicos para la mayoría de ellos.

EDITAR Mayo de 2010: Python y JavaScript agregados.

EDITAR Oct 2010: EGL agregado.

EDITAR Nov 2010: VB6, VBScript, VB.net agregado

Ira Baxter
fuente
2
Hola Ira, ¿has publicado un artículo sobre tu algoritmo diff? Tengo problemas para encontrar literatura de diferencias de distancia de edición de árbol. Gracias, Terence.
Terence Parr
Para ser más específico, busque diff3 no simple diff2
Terence Parr
2
@Terence: No existe publicación de nuestro algoritmo diff. Es un cálculo de distancia mínima de Levenstein que usa árboles de sufijos para identificar subárboles iguales, con algunos huerstics para manejar el cambio de nombre. IIRC, Yang tuvo un artículo sobre esto en Práctica y experiencia de software. El nuestro y el de Yang son diff2, no diff3.
Ira Baxter
@IraBaxter El enlace está actualmente roto y el sitio parece no funcionar cuando se abre desde el enlace de Google.
Răzvan Flavius ​​Panda
El sitio está respaldado, el enlace debería estar bien.
Ira Baxter
12

Lo que estás buscando es una "diferencia de árbol". Resulta que esto es mucho más difícil de hacer bien que una simple diferencia textual orientada a líneas, que en realidad es solo la comparación de dos secuencias planas.

" Un enfoque de comparación estructural XML detallado " concluye, en parte con:

Nuestro estudio teórico, así como nuestra evaluación experimental, mostraron que el método propuesto produce mejores resultados de similitud estructural con respecto a las alternativas existentes, mientras que tiene la misma complejidad de tiempo (O (N ^ 2))

(énfasis mío)

De hecho, si está buscando más ejemplos de diferenciación de árboles, le sugiero que se centre en XML, ya que ha impulsado desarrollos prácticos en esa área.

doblando
fuente
Gracias por el enlace. Puedo pensar en algunos enfoques diferentes para implementar herramientas de diferenciación semántica, y tienes razón: la mayoría se puede resumir en un "árbol de diferenciación". Es posible que incluso sea necesario resumir situaciones más complejas en un "gráfico diferencial".
Jasonmray
Sí. Rational Modeler de IBM (construido sobre eclipse) intenta hacer esto con modelos UML (mostrando las diferencias entre dos modelos gráficamente). No puedo comentar sobre la utilidad de los resultados porque no los uso mucho.
bendin
Estoy de acuerdo en que XML es un buen lugar para comenzar, ya que simplemente puede crear esquemas para representar otras estructuras (como el código Java, por ejemplo) y usar un árbol-diff basado en XML para implementar un código diff.
Jasonmray
"hacer esto" => hacer algo parecido a una "diferencia de gráfico".
Bendin
1
Consulte semdesigns.com/Products/SmartDifferencer/index.html para obtener un motor de comparación basado en árbol de sintaxis que funciona con muchos idiomas.
Ira Baxter
2

La solución a esto sería por idioma. Es decir, a menos que esté diseñado con una arquitectura de complemento que difiera gran parte del análisis del código en un árbol y la comparación semántica con un complemento específico de un idioma, será muy difícil admitir varios idiomas. Para qué idioma (s) está interesado en tener una herramienta de este tipo. Personalmente, me encantaría uno para C #.

Para C # hay un complemento diff de ensamblado para Reflector, pero solo hace una diferencia en el IL, no en el C #.

Puede descargar el complemento diff aquí [zip] o ir al proyecto en el sitio del codeplex aquí .

Jonathan Parker
fuente
1
Consulte semdesigns.com/Products/SmartDifferencer/index.html para obtener un motor de comparación basado en árbol de sintaxis que funciona con muchos idiomas, utilizando exactamente el estilo de complemento de idioma. Aún no se ha lanzado, pero una versión de C # está muy cerca.
Ira Baxter
Enero de 2010: lanzamiento de C # Smart Differencer.
Ira Baxter
2

Una empresa llamada Zynamics ofrece una herramienta de diferencia semántica de nivel binario. Utiliza un lenguaje de metaensamblador llamado REIL para realizar un análisis teórico de gráficos de 2 versiones de un binario y produce un gráfico codificado por colores para ilustrar las diferencias entre ellos. No estoy seguro del precio, pero dudo que sea gratis.

David V McKay
fuente
Enlace a la diferencia semántica de nivel binario: zynamics.com/bindiff.html
emallove
2

http://prettydiff.com/

Pretty Diff minimiza cada entrada para eliminar comentarios y espacios en blanco innecesarios y luego embellece el código antes del algoritmo diff. De todos modos, no puedo pensar en convertirme en un código más semántico que esto. Y su JavaScript escrito para que se ejecute directamente en el navegador.

Austincheney
fuente
5
¡Entonces tienes una imaginación limitada! ¿Qué hay de cambiar las posiciones de dos métodos en un archivo sin cambiarlos? ¿Qué pasa con las refactorizaciones?
Robin Green
(No puede intercambiar declaraciones de datos en Java de esta manera, y aún tener equivalencia, debido a los inicializadores; supongo que C # tiene problemas similares). Si opta por la diferencia semántica pura, entonces está tratando de resolver la equivalencia de la máquina de Turing. Hay mucho margen para hacerlo mejor que la coincidencia de texto puro, y peor que Turing imposible.
Ira Baxter
@IraBaxter La herramienta, conceptualmente, obviamente solo mostrará cosas equivalentes que en realidad son equivalentes. Si está codificado correctamente, no tendrá el tipo de problema que está mencionando.
Răzvan Flavius ​​Panda
"Codificado correctamente" significa demostrar la equivalencia del algoritmo si desea la herramienta definitiva. Las pruebas de equivalencia de algoritmos son de Turing-hard en general, por lo que no obtendrá una herramienta de este tipo en la práctica. Lo que puede obtener es una herramienta que maneja algunas equivalencias además de los cambios de sintaxis. Hasta la fecha, no he visto a nadie intentar construir una herramienta de este tipo.
Ira Baxter