Embed Size (px)
Citation preview
Thiago Pinheiro de Araújo
Arndt von Staa
SDiff: Uma ferramenta para comparação de documentos com base nas suas
estruturas sintáticas
Índice
• Introdução
• Motivação
• Estado da arte
• Objetivo
• Modelo conceitual
• A ferramenta SDiff
• Experimentos
• Conclusão e Trabalhos futuros
Introdução
• Ferramentas de comparação são utilizadas para identificar as diferenças existentes entre duas versões de um documento.
• Entende-se por documento qualquer artefato que possa ser comparado.
• Tais ferramentas costumam ser utilizadas acopladas a sistemas de controle de versão a fim de:
– Permitir que o usuário visualize as diferenças que serão adicionadas ao próximo changeset do projeto.
– Definir o incremento representado por cada changeset do projeto.
Motivação
• Toda ferramenta desta natureza possui uma unidade de comparação indivisível.
– Na maioria das ferramentas comerciais esta unidade costuma ser o parágrafo (linha de texto seguida de terminador de linha).
• Essa abordagem permite tratar de todos os arquivos de texto da mesma forma independente do tipo de conteúdo específico de cada um.
• Porém esta abordagem produz resultados imprecisos e com poucas informações sobre a evolução.
– A tarefa de identificar o trecho exato que foi modificado e a semântica associada a ele é delegada ao usuário.
Motivação
• Resultados pouco precisos dificultam a legibilidade das diferenças:
• Além disso, o versionamento de documentos não-textuais, como modelos, torna-se inviável.
Estado da arte
• Categorias de trabalhos encontrados na literatura:
– Operation-based.
• Conhece a seqüência de passos com as operações de edição.
• Depende de um ambiente instrumentado.
– Syntax-based.
• Baseia-se na estrutura sintática dos documentos.
• Depende de interpretadores para tratar cada tipo de sintaxe.
– Refactor-oriented.
• Procura identificar operações de refatoração.
• É complementar aos anteriores.
• Abordagem oriented-based depende de um ambiente instrumentado.
• Abordagem syntax-based depende da AST e de todo o código-fonte disponível.
Estado da arte
• Categorias de trabalhos encontrados na literatura:
– Model-oriented.
• Viabiliza o versionamento de documentos não-textuais.
• Contribui para a evolução de Model-driven development.
– Controles de versão com granularidade variável.
• Capazes de persistir todo o conteúdo sob a forma de elementos com granularidade variável.
• Quando associados a ambientes de desenvolvimento é possível manter identificadores persistentes para cada elemento.
• Depende de interpretadores para tratar cada tipo de sintaxe.
• Pesquisas relacionadas:
– Kim [2006] realizou um estudo comparativo sobre as técnicas existentes de comparação de código-fonte de software.
• Concluiu que um comparador hibrido produz melhores resultados.
Objetivo
• Criar um mecanismo de comparação de documentos textuais capaz de identificar com precisão as diferenças entre duas versões de um documento.
• Este mecanismo
– Deve se basear nas estruturas sintáticas dos documentos.
– Não deve depender de outros documentos que resolvam as dependências do documento comparado.
• Ex: Declarações em linguagens de programação.
• O mecanismo deve poder se aplicado a qualquer tipo de documento textual.
– Ex: Linguagens de programação, arquivos XML, arquivos Tex, etc.
Modelo conceitual
• Conceitos gerais
• Visão geral
• Estrutura sintática canônica
• Mecanismo de comparação
– Estrutura Diff
– Algoritmo de comparação
• Algoritmo de comparação textual.
• Algoritmo de comparação sintática.
• Comparação com o estado da arte
Conceitos gerais
• Comparações de documentos geram uma lista de diferenças.
• Cada diferença é representada nos documentos a partir de uma seleção.
• Uma seleção define os limites textuais de um elemento sintático, a partir de um ponto inicial e um ponto final.
• Um ponto indica uma posição no documento a partir de linha e coluna.
Conceitos gerais
• Cada diferença representa um tipo de operação:
– Inserção.
– Remoção.
– Modificação.
– Movimentação.
– União.
– Separação.
– Clone.
• Ferramentas comerciais costumam identificar inserções e remoções.
• Algumas mais elaboradas identificam também modificações.
• Porém, em ambos os casos, com precisão baixa.
Visão geral
Estrutura sintática canônica
• O algoritmo de comparação trabalha sobre uma estrutura sintática canônica, a fim de mantê-lo genérico para qualquer tipo de documento.
• Esta estrutura canônica:
– representa os elementos sintáticos presentes no documento e seus relacionamentos hierárquicos.
– é gerada por um conversor que recebe o conteúdo específico, interpreta-o, e retorna sua representação estrutural.
• Nesse processo são adicionadas propriedades sintáticas identificadas durante a interpretação do documento.
Estrutura sintática canônica
Mecanismo de comparação
• O resultado dessa conversão é retornado em um formato XML.
– Este é um formato flexível e genérico suficiente para representar a grande maioria dos documentos.
• Exemplo:
30. private:31. int m_var;
<VariableDeclaration visibility="private“ >
<TypeSpecifier value="int“ />
<Identifier value="m_var“ />
</VariableDeclaration>
Algoritmo de comparação
• Entrada: dois documentos na forma canônica.
• Saída: uma estrutura Diff contendo as diferenças identificadas.
– Como o algoritmo atua sobre uma árvore composta por elementos sintáticos, a resposta também é representada como uma árvore de diferenças.
– Esta estrutura também guarda o percentual de diferença calculado para o par de elementos comparados.
• Esta é a propriedade mais relevante para a tomada de decisão do algoritmo e possivelmente para se obter um bom resultado final.
• Este valor é calculado com base em três heurísticas apresentadas a seguir.
Algoritmo de comparação
Result:
Algoritmo de comparação
• O algoritmo de comparação:
1. Só compara os elementos se forem do mesmo tipo.
2. Realiza a comparação de propriedades.
3. Realiza a comparação de sub-elementos, que pode ser:
• Textual – Baseado no algoritmo LCS, considerando o caractere como unidade indivisível de comparação.
• Sintática – Explicado a seguir.
4. Calcula o percentual de diferença entre os elementos segundo a fórmula:
Algoritmo de comparação
• O algoritmo de comparação sintática:
1. Executa o algoritmo LCS sobre as listas de sub-elementos.
2. Constrói uma matriz Elemento Inseridos X Elementos Removidos
• O peso de cada par é calculado a partir dos valores:
1. Percentual de igualdade.
2. Proximidade (heurística).
3. Igualdade de nomes (heurística).
3. Executa um algoritmo de emparelhamento sobre esta matriz.
• Hungarian [Kuhn, 1955].
4. Define quais pares resultantes do emparelhamento são equivalentes, a partir de uma heurística.
5. Classifica os resultados em operações de modificação e movimentação.
Comparação com o estado da arte
• O modelo apresentado não é invasivo.
– Evita que o usuário final se restrinja a ferramentas especiais.
• O mecanismo de comparação respeita a hierarquia e os tipos dos elementos sintáticos.
• A utilização de heurísticas combinadas ao algoritmo de emparelhamento é uma inovação proposta por este trabalho que evita resultados rígidos.
• A proposta de Dig [DIG, et al., 2006] relacionada à detecção de operações de refactor com base em padrões conhecidos é complementar ao nosso modelo.
• O algoritmo implementado é híbrido: cada tipo de elemento define se o seu conteúdo será comparado utilizando o mecanismo de comparação sintática ou textual.
A ferramenta SDiff
• A implementação deste algoritmo produziu a ferramenta SDiff:
Inserção
Remoção
Modificação
Movimentação
Alteração no contexto
Modificação no elemento
Comparação com a ferramenta KDiff3
• Modificação
Comparação com a ferramenta KDiff3
• Movimentação
Comparação com a ferramenta KDiff3
• Reformatação
Comparação com a ferramenta KDiff3
• Extração de código
Experimentos em aplicações reais
• Aplicamos a ferramenta SDiff em versões consecutivas de documentos extraídos de aplicações reais com as características:
– Número de linhas alto (1 a 5 KLOC).
– Dependências não resolvidas.
• A ferramenta foi capaz de identificar com precisão a maior parte das diferenças.
• Dificuldades encontradas:
– Comparação de blocos de comentário formados por // consecutivos.
– Comparação de macros.
• Fizemos alguns testes para avaliar o desempenho da ferramenta quando submetida a diferentes tamanhos documentos.
Estatísticas da execução
Conclusão
• O objetivo deste trabalho foi projetar um mecanismo de comparação de documentos capaz de respeitar suas propriedades estruturais e sintáticas.
• Os principais benefícios obtidos do ponto de vista do usuário foram:
– Capacidade de identificar elementos movidos ou modificados.
– Precisão sintática nas diferenças.
– Ignorar diferenças irrelevantes para o usuário como identação ou formatação.
• A contribuição mais significativa deste trabalho é a aplicação de heurísticas para inferir operações mais específicas que uma simples inserção ou remoção de elementos.
Trabalhos futuros
• Melhorias no mecanismo de comparação:
– Identificar movimentações entre níveis.
– Criar heurísticas para detectar união, separação, clones e refactors.
– Extensão para tratar de documentos não-textuais.
• Melhorias na ferramenta SDiff:
– Implementar componentes que tratem outros tipos de documentos (Ex: Java, Lua, XML, HTML, Javascript, C#, etc).
– Criar um modo de visualização, específico para linguagens de programação:
• Ex: Diagramas de classe, DFDs, etc.
