Not logged in.

Quick Search - Contribution

Contribution Details

Type Master's Thesis
Scope Discipline-based scholarship
Title Improving Abstract Syntax Tree based Source Code Change Detection
Organization Unit
Authors
  • Michael Würsch
Supervisors
  • Harald Gall
  • Beat Fluri
Institution University of Zurich
Faculty Faculty of Economics, Business Administration and Information Technology
Date 2006
Abstract Text Changes are a crucial part of the life-cycle of modern software systems. Common versioning systems such as CVS store version histories of source code. Usually, they are not capable of tracking changes on a more sophisticated level. They provide lexical but not syntactical change analysis. The existing Eclipse-plug-in ChangeDistiller bridges this gap by providing a sophisticated analysis of structural source code changes. It uses an abstract syntax tree (AST) representation of subsequent revisions of source code files and compares the trees by using a change detection algorithm for hierarchically structured information. The outcome is an edit script describing the operations that are necessary to transform the original version of the tree into the modified one. We aim at improving the sub-algorithm responsible for matching trees. It yields insufficiencies in terms of matching leaves in general, it often produces sub-optimal results for small subtrees, and it is not able to handle large number of changes adequately. To overcome this issues, we propose customized similarity measures and a similarity ranking algorithm for leaves, as well as dynamic modulation of the tree similarity thresholds whenever small tree structures are encountered. To prove our claims, we establish an extensive benchmark for investigating runtime performance and accuracy. The benchmark is based on the JUnit regression testing framework and relies on artificial source code examples, as well as on examples taken from a medium-sized real project.
Zusammenfassung Änderungen sind ein wichtiger Bestandteil im Lebenszyklus eines jeden modernen Software Systems. Versionierungssysteme, wie zum Beispiel CVS, verwalten die Änderungen von Programmcode über Zeit. Werkzeuge zum Vergleich zweier Programmversionen basieren üblicherweise auf lexikalischen, also text-basierten, Methoden und sind nicht in der Lage strukturelle Änderungen zu erfassen. ChangeDistiller, ein existierendes Plug-In für Eclipse, geht einen Schritt weiter, indem es eine umfassende Analyse von Änderungen in der Programmstruktur bereitstellt. Um dies zu bewerkstelligen, generiert das Werkzeug eine auf abstrakten Syntaxbäumen basierende Repräsentation von Programmcode. Die Bäume werden mittels eines auf Änderungen in hierarchisch-strukturierten Informationen spezialisierten Algorithmus verglichen. Das Resultat ist eine Menge von Änderungsoperationen, die die ursprügliche Programmversion in die modifizierte Fassung überführen. Diese Diplomarbeit bezweckt eine Verbesserung des Teilalgorithmus, welcher Übereinstimmungen zwischen Bäumen lokalisiert. Der Algorithmus birgt einige Schwächen. Ähnlichkeiten zwischen Bättern der verglichenen Bäume werden nicht immer erkannt. Desweiteren werden meist suboptimale Resultate erzielt, wenn kleine Subbäume analysiert werden oder zu umfangreiche Änderungen zwischen zwei aufeinanderfolgenden Versionen von statten gegangen sind. Um diesen Einschränkungen Herr zu werden, schlagen wir nun folgende Massnahmen vor: Zum Einen empfehlen wir neue, auf Programmcode spezialisierte, Metriken zur Ähnlichkeitsbestimmung. Zum Anderen haben wir den Algorithmus dahingehend angepasst, dass er eine auf Ähnlichkeiten basierende Rangfolge zwischen möglichen Paaren von Blättern berechnet. Um das Problem kleiner Subbäume zu mildern, verwenden wir eine dynamische Anpassung der Grenzwerte, welche darüber entscheiden, ob zwei Teilbäume in ausreichendem Masse Ähnlichkeiten aufweisen, um als Übereinstimmung gewertet zu werden. Um die Auswirkungen unserer Massnahmen zu untersuchen, stellen wir umfangreiche Untersuchungen an. Wir testen das Laufzeitverhalten, sowie die Präzision unseres Algorithmus mittels dem JUnit-Framework für Regressionstests. Als Testgrundlage wählen wir eine Kombination aus konstruierten Testfällen und realen Beispielen, die einem Projekt mittlerer Grösse entnommen wurden.
PDF File Download
Export BibTeX