Quelltextklon

Bei Quelltextklonen (auch Codeduplikate, Softwareklonen oder einfach nur Klonen) handelt es sich um ähnliche Abschnitte im Quelltext eines Computerprogramms. Solche Klone sind eine Form von redundantem Code und entstehen vorwiegend durch Kopieren und Einfügen. Da sie negative Auswirkungen auf die Wartung haben, sind Klone ein starker Indikator für mangelnde Qualität.

Ähnlichkeit

Bei Klonen handelt es sich im Allgemeinen um ähnliche Quelltextabschnitte. Damit ist die Definition der Ähnlichkeit ein zentraler Punkt, der auch in der Forschung noch intensiv diskutiert wird. Es herrscht allerdings Übereinstimmung darüber, dass es keine universell einsetzbare Definition gibt, sondern sich diese immer nach dem konkreten Anwendungsfall richtet. Bei der Definition der Ähnlichkeit sind unter anderem die folgenden Aspekte zu berücksichtigen:

Abgrenzung zu redundanten Literalen

Klone definieren sich darüber, dass Quelltextabschnitte einer gewissen Größe zueinander ähnlich sind. Aus diesem Grund spricht man bei einzelnen duplizierten Tokens üblicherweise nicht von Klonen. Dies betrifft vorwiegend redundante Literale im Quelltext, die besser als symbolische Konstante repräsentiert werden sollten (zum Beispiel alle Vorkommen des Literals 3.14159 durch eine Konstante mit dem Bezeichner PI). Um die Wiederholung von Ausdrücken in den Quelltexten zu vermeiden, sollten also schon aus Gründen der Wartbarkeit und der effizienteren Fehlersuche kategorisch symbolische Konstanten verwendet werden.

Begriffe

Es existiert eine Reihe von Begriffen, die sich mit der Zeit im Bereich der Softwareklone etabliert haben.

Gründe

Klone entstehen fast ausschließlich durch „copy-&-paste-Programmierung“. Für das Entstehen von Klonen gibt es eine Reihe von Gründen, die sich in die folgenden Kategorien einteilen lassen:

• Entwicklungsstrategie: Bestehende Funktionalität wird als Vorlage für neu zu erstellende Funktionalität verwendet. Dabei wird der bereits existierende Code kopiert und nach Bedarf angepasst. Hierzu zählen auch Situationen, in denen Code dupliziert wird, um Änderungen zu erproben ohne die Funktion des Systems zu gefährden (Branching).
• Vorteile bei der Wartung: Durch die Wiederverwendung von existierendem Code soll die zukünftige Wartung erleichtert werden. So wird zum Beispiel bewährter Code wiederverwendet, um das Risiko neuer Fehler zu minimieren. Außerdem können durch das Kopieren von Code unerwünschte Abhängigkeiten zwischen Komponenten vermieden und eine getrennte Wartung ermöglicht werden.
• Umgehen von Einschränkungen: Programmiersprachen bieten unterschiedliche Arten von Abstraktionsmechanismen. Sollte in einer bestimmten Situation keine geeignete Abstraktionsmöglichkeit vorhanden sein, wird dieses Problem oft durch Klone gelöst. Klone können aber auch aufgrund von Zeitdruck und fehlenden Kenntnissen des Entwicklers entstehen.
• Unabhängige Implementierung: Aufgrund mangelnder Kenntnis bestehender Funktionalität wird diese mehrfach implementiert. Zudem können Klone durch die Verwendung von Bibliotheken entstehen, die ein bestimmtes Protokoll erfordern.

Negative Auswirkungen

Klone werden im Allgemeinen als Anti-Pattern angesehen, da sie dem Prinzip "Don’t repeat yourself" (DRY) widersprechen und als das am häufigsten auftretende Merkmal für schlechten Code gelten. Sie führen aus den genannten Gründen die Liste der sogenannten Code-Smells an. Auch wenn es eine Vielzahl von Gründen für ihre Entstehung gibt, so haben Klone mitunter gravierende negative Auswirkungen auf die Software und ihre Wartung.

• Erhöhter Wartungsaufwand: Klone erhöhen den Aufwand für die Wartung signifikant. Oft muss identischer Code mehrfach gelesen und verstanden werden. Zusätzlicher Aufwand ist erforderlich, um zu verstehen, ob kleine Unterschiede gewollt oder unbeabsichtigt sind. Im Fall einer Änderung muss diese mehrfach durchgeführt und getestet werden. Dabei muss für jede Kopie mindestens geprüft werden, ob die Änderung auch hier durchgeführt werden muss – selbst wenn die Kopie am Ende nicht verändert wird.
• Inkonsistente Änderungen: Im Rahmen von Änderungen an Klonen besteht immer die Gefahr, einzelne Kopien zu übersehen. Dieses Problem ist umso stärker, je mehr Entwickler in einem Projekt beteiligt sind und unwissentlich voneinander kopieren. Auch wenn bestehender Code als Vorlage verwendet wird und angepasst werden muss, besteht immer die Gefahr, dass diese Anpassung nicht korrekt durchgeführt wird. Ungewollt inkonsistente Änderungen können insbesondere dann problematisch sein, wenn es sich bei der Änderung um einen Bugfix handelt. Der Fehler wird an einer Stelle behoben und es wird angenommen, dass das Problem damit gelöst sei, obwohl der Fehler an noch mindestens einer anderen Stelle im System verbleibt. Diese unbeabsichtigten inkonsistenten Änderungen existieren nachweislich in hoher Zahl in produktiven Systemen.
• Erhöhter Speicherbedarf: Klone vergrößern den Codeumfang. Dies betrifft sowohl den Speicherplatz der Quelltextdateien als auch die Größe des kompilierten Systems. Dies kann insbesondere im Bereich der eingebetteten Systeme zu Problemen führen und teurere Hardware erforderlich machen. Zudem hat ein erhöhter Codeumfang auch einen längere Kompilierung zur Folge.
• Kopieren von Fehlern: Es besteht die Gefahr, dass der kopierte Quelltext Fehler enthält. In der Folge kommt es zu den Problemen, die unter „Inkonsistente Änderungen“ beschrieben sind.

Klonerkennung

Es existiert eine Vielzahl an Klonerkennungsverfahren, die sich grob anhand der Programmrepräsentation, mit der sie arbeiten, kategorisieren lassen. Die Verfahren unterscheiden sich unter anderem in der Laufzeit, Komplexität, Qualität der Ergebnisse und verfügbaren Normalisierungen.

• Text: Diese Verfahren haben keinerlei sprachspezifisches Wissen und interpretieren den Quelltext als reinen Text. Dadurch sind diese Verfahren vergleichsweise schnell und einfach zu implementieren. Der Nachteil ist, dass sie vom Layout des Quelltextes abhängig sind und nur sehr wenige Möglichkeiten der Normalisierung bieten.
• Tokens: Diese Verfahren basieren auf einer lexikalischen Analyse des Quelltextes und arbeiten auf einer Sequenz aus Tokens. Diese Verfahren sind immer noch vergleichsweise schnell und einfach zu implementieren. Durch eine gewisse Kenntnis der analysierten Sprache lassen sich Normalisierungen wie z. B. das Ignorieren von Kommentaren oder das Abstrahieren von Bezeichnern durchführen. Zudem sind diese Verfahren nicht anfällig gegen Unterschiede im Layout des Quelltextes.
• Baum: Diese Verfahren arbeiten auf dem abstrakten Syntaxbaum (AST) des Programms und suchen darin nach ähnlichen Teilbäumen. Dadurch bieten sie noch weitere Möglichkeiten der Normalisierung wie z. B. die Abstraktion von der Art einer Schleife oder die Reihenfolge der Operanden in kommutativen Operationen. Baumbasierte Verfahren sind allerdings komplexer zu implementieren und benötigen deutlich mehr Laufzeit. Zudem erfordern sie, dass der Quelltext syntaktisch korrekt ist und geparst werden kann. Dies ist ein deutlicher Nachteil gegenüber textbasierten und tokenbasierten Verfahren.
• Graph: Diese Verfahren arbeiten zumeist auf dem Program Dependency Graph (PDG) und suchen nach ähnlichen Teilgraphen. Damit sind sie die am komplexesten zu implementierenden und zugleich langsamsten Verfahren. Ihr Vorteil besteht darin, dass sie Klone mit geringer syntaktischer Ähnlichkeit erkennen können, die von keinem der anderen Verfahren gefunden werden.
• Metriken: Diese Verfahren berechnen für bestimmte Entitäten im Quelltext (z. B. Methoden) Metriken und erkennen Klone durch den Vergleich dieser Metriken. Sie sind recht einfach zu implementieren und auch vergleichsweise schnell. Der Nachteil besteht darin, dass Klone nur auf der vorher festgelegten Granularitätsstufe gefunden werden können. So können z. B. keine Klone innerhalb von Methoden gefunden werden, wenn die Metriken auf Basis ganzer Methoden berechnet werden. In der Praxis finden diese Verfahren wenig Anwendung, da viele Entitäten rein zufällig ähnliche Metrikwerte aufweisen, ohne dass eine syntaktische oder semantische Ähnlichkeit besteht.

Nicht jedes Verfahren lässt sich eindeutig einer der Kategorien zuordnen, da manche Verfahren Elemente aus verschiedenen Kategorien vereinen. So existieren z. B. hybride Verfahren, die zunächst einen abstrakten Syntaxbaum erstellen, diesen dann serialisieren und ein tokenbasiertes Verfahren zur Erkennung von Klonen in der Sequenz der serialisierten Knoten einsetzen.

Weiterhin lassen sich Klonerkennungsverfahren danach unterschieden, ob sie inkrementell arbeiten oder nicht. Ein inkrementelles Verfahren erkennt Klone in mehreren aufeinanderfolgenden Versionen des Quelltextes. Im Vergleich zur wiederholten Anwendung eines nicht-inkrementellen Verfahrens für jede einzelne Version, machen sich inkrementelle Verfahren die Analyseergebnisse der vorherigen Version zunutze. Dadurch bieten inkrementelle Verfahren einen deutlichen Geschwindigkeitsvorteil bei der Klonerkennung über mehrere Versionen des Quelltextes.

Werkzeuge

Es gibt verschiedene Werkzeuge zur statischen Analyse von Programmcode, die auch Quelltextklone finden können. Dazu gehören zahlreiche freie Werkzeugen wie das PMD-Plugin CPD (Copy/Paste Detector), Clone Digger (für Python und Java), Cppcheck (für C++ und C) und ConQAT (für Ada, ABAP, C#, C, C++, COBOL, Java, Visual Basic, PL/I) sowie proprietäre Werkzeuge wie CCFinder (Code Clone Finder) oder Simian (Similarity Analyser).

Klonmanagement

Klonmanagement fasst alle Tätigkeiten im Umgang mit Klonen zusammen. Dazu gehört sowohl die werkzeuggestützte Erkennung von Klonen als auch die Auswahl und Durchführung entsprechender Gegenmaßnahmen. Zu den möglichen Gegenmaßnahmen zählen unter anderem:

Entfernen

Die Klone werden entfernt, indem eine geeignete Abstraktion geschaffen wird, mit der die redundanten Quelltextabschnitte vereinheitlicht werden können. Dies kann zum Beispiel durch die Auslagerung von wiederkehrenden Algorithmen in Prozeduren oder Methoden erfolgen. Häufig wird hierfür das Extract-Method-Refactoring angewendet.

In objektorientierten Sprache besteht zudem die Möglichkeit, Klone durch Ausnutzen der Vererbung und das Zusammenfassen der Kopien in einer gemeinsamen Basisklasse (Pull-Up-Method-Refactoring) zu entfernen.

In Sprachen, die einen Präprozessor beinhalten, lassen sich Klone unter Umständen durch entsprechende Makros entfernen. Bei Klonen, die mehrere Dateien oder ganze Subsysteme umfassen („Strukturelle Klone“), bietet sich an, die Klone durch Auslagerung in Module oder Bibliotheken zu entfernen.

Beobachten

Nicht immer lassen Klone sich einfach entfernen. Ein alternativer Umgang besteht darin, die Klone durch ein entsprechendes Werkzeug zu beobachten. Bei der Änderung eines Klons wird der Entwickler auf das Vorhandensein weiterer Kopien hingewiesen. Dadurch wird das Risiko von ungewollt inkonsistenten Änderungen vermieden.

Klone außerhalb des Quelltextes

Klonerkennung fokussiert sich stark auf ähnliche Abschnitte im Quelltext eines Programms. Darüber hinaus existieren Klone aber auch in anderen Artefakten der Softwareentwicklung wie z. B. Modellen oder Anforderungsspezifikationen. Die Gründe für die Klone und deren negative Auswirkungen sind weitestgehend übertragbar. Die Definition der Ähnlichkeit hingegen muss angepasst werden. Während es für die Erkennung von Klonen im Quelltext bereits etablierte Verfahren gibt, wird an der Erkennung von Klonen in anderen Artefakten noch intensiv geforscht.

Beispiel

Das folgende Beispiel in Java zeigt wie Klone durch ein Extract-Method-Refactoring entfernt werden können. Der Quelltext berechnet die Summe der Werte in zwei Arrays.

public int sum(int[] values1, int[] values2) {  int sum1 = 0;  int sum2 = 0;  for (int i = 0; i < values1.length; i++)  {  sum1 += values1[i];  }  for (int i = 0; i < values2.length; i++)  {  sum2 += values2[i];  }  return sum1 + sum2; } 

Die Schleife, die die eigentliche Berechnung vornimmt, kann in eine eigene Funktion extrahiert werden.

public int sum(int[] values) {  int sum = 0;  for (int i = 0; i < values.length; i++)  {  sum += values[i];  }  return sum; } 

Die neue Funktion kann für jedes Array einmal aufgerufen werden. Dadurch wurden die Klone entfernt und die Redundanz verringert.

public int sum(int[] values1, int[] values2) {  return sum(values1) + sum(values2); } 

Die Berechnung der Summe der Werte eines Arrays stellt einen Klon außerhalb des Quelltextes dar, da ab Java 8 für derartige Anforderungen Streams existieren. Die public int sum(int[] values) Methode kann daher gelöscht werden und die zweite Methode folgendermaßen geändert werden:

public int sum(int[] values1, int[] values2) {  return IntStream.of(values1).sum() + IntStream.of(values2).sum(); } 

Literatur

• Martin Fowler: Refactoring. Wie Sie das Design vorhandener Software verbessern. Addison-Wesley, München 2000 (Originaltitel: Refactoring. Improving The Design Of Existing Code, übersetzt von Bernd Kahlbrandt), ISBN 3-8273-1630-8.
• Nils Göde: Clone Evolution. Dissertation, Universität Bremen, Logos Verlag Berlin GmbH, Berlin 2011, ISBN 978-3-8325-2920-8.
• Elmar Juergens, Florian Deissenboeck, Benjamin Hummel: A Workbench for Clone Detection Research. (PDF; 359 kB) In: Proceedings of the 31^st International Conference on Software Engineering, IEEE Computer Society, 2009.
• Elmar Juergens, Florian Deissenboeck, Benjamin Hummel, Stefan Wagner: Do code clones matter? (PDF; 259 kB) In: Proceedings of the 31^st International Conference on Software Engineering, S. 485–495. IEEE Computer Society, 2009.
• Rainer Koschke: Survey of Research on Software Clones. (PDF; 222 kB) Dagstuhl Seminar: Duplication, Redundancy, and Similarity in Software, 2006.
• Dhavleesh Rattan, Rajesh Bhatia, Maninder Singh: Software clone detection: A systematic review. Information and Software Technology, Band 55, 2013, Ausgabe 7, S. 1165–1199.
• Chanchal Kumar Roy, James R. Cordy: A survey on software clone detection research. (PDF; 577 kB) Technical report, Queens University at Kingston, Ontario (Canada) 2007.

Weblinks

• Robert Tairas: Code Clones Literature. Abgerufen am 28. August 2013.

Einzelnachweise

1. Markus Bautsch: Codewiederholung – Symbolische Konstanten. In: Strukturierte Programmierung. Wikibook
2. Stefan Wagner, Asim Abdulkhaleq, Ivan Bogicevic, Jan-Peter Ostberg, Jasmin Ramandani. How are functionally similar code clones different?. PeerJ Preprints, 2015.
3. Chanchal Kumar Roy, James R. Cordy: A survey on software clone detection research. (PDF; 577 kB) Technical report, Queens University at Kingston, Ontario (Canada) 2007, S. 3–7.
4. Martin Fowler: Refactoring. Wie Sie das Design vorhandener Software verbessern. Addison-Wesley, München 2000 (Originaltitel: Refactoring. Improving The Design Of Existing Code, übersetzt von Bernd Kahlbrandt), ISBN 3-8273-1630-8, S. 67–82
5. Elmar Juergens, Florian Deissenboeck, Benjamin Hummel, Stefan Wagner: Do code clones matter? (PDF; 259 kB) In: Proceedings of the 31^st International Conference on Software Engineering. IEEE Computer Society, 2009, S. 485–495.
6. Nils Göde: Clone Evolution. Dissertation, Universität Bremen, 2011, S. 15–21.
7. Nils Göde, Rainer Koschke: Incremental clone detection. In: Proceedings of the 13^th European Conference on Software Maintenance and Reengineering. IEEE Computer Society, 2009, S. 219–228.
8. Benjamin Hummel, Elmar Juergens, Lars Heinemann, Michael Conradt: Index-based code clone detection. Incremental, distributed, scalable. (PDF; 440 kB) In: Proceedings of the 26^th International Conference on Software Maintenance. IEEE Computer Society, 2010.
9. Rainer Koschke: Frontiers of software clone management. In: Proceedings of Frontiers of Software Maintenance. IEEE Computer Society, 2008, S. 119–128.
10. Markus Bautsch: Codewiederholung – Methodenaufrufe. In: Strukturierte Programmierung. Wikibook
11. Markus Bautsch: Vermeidung von Codewiederholung durch Vererbung. In: Strukturierte Programmierung. Wikibook
12. Florian Deissenboeck, Benjamin Hummel, Elmar Jürgens, Bernhard Schätz, Stefan Wagner, Jean-François Girard, Stefan Teuchert: Clone detection in automotive model-based development. (PDF; 409 kB) In: Proceedings of the 30^th International Conference on Software Engineering. ACM, 2008, S. 603–612.
13. Florian Deissenboeck, Benjamin Hummel, Elmar Juergens, Michael Pfaehler: Model clone detection in practice. (PDF; 291 kB) In: Proceedings of the 4^th International Workshop on Software Clones. ACM, 2010, S. 57–64.
14. Harald Störrle: Towards clone detection in UML domain models. In: Proceedings of the 4^th European Conference on Software Architecture. ACM, 2010, Companion Volume, S. 285–293.
15. Christoph Domann, Elmar Juergens, Jonathan Streit: The curse of copy&paste–cloning in requirements specifications. (PDF; 107 kB) In: Proceedings of the 3^rd International Symposium on Empirical Software Engineering and Measurement. IEEE Computer Society, 2009, S. 443–446.
16. Elmar Juergens, Florian Deissenboeck, Martin Feilkas, Benjamin Hummel, Bernhard Schaetz, Stefan Wagner, Christoph Domann, Jonathan Streit: Can clone detection support quality assessments of requirements specifications? (PDF; 400 kB) In: Proceedings of the 32^nd International Conference on Software Engineering. ACM, 2010, S. 79–88.