SDiff: Uma ferramenta para comparação
de documentos com base nas suas
estruturas sintáticas
Thiago Pinheiro de Araújo
Arndt von Staa
Í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.
Estatísticas da execução
• Fizemos alguns testes para avaliar o desempenho da
ferramenta quando submetida a diferentes tamanhos
documentos.
Tempo (s)
9
8
7
6
5
Carga de A
4
Carga de B
3
Comparação
2
1
0
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
Linhas no documento (KLOC)
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.
Perguntas?
Thiago Pinheiro de Araújo
[email protected]
PUC-Rio – Departamento de Informática