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:

Mindestlänge

Da sich jedes Programm aus den atomaren Elementen (z. B. Schlüsselwörter, Operatoren, Bezeichner, …) der jeweiligen Programmiersprache zusammensetzt, besteht auf dieser Ebene immer Ähnlichkeit zwischen verschiedenen Codefragmenten. Allerdings gibt es auf dieser Ebene selten sinnvolle Abstraktionsmöglichkeiten und diese atomaren Elemente schon als Klone anzusehen ist selten hilfreich. Daher gehört zur Definition der Ähnlichkeit die Festlegung einer Mindestlänge, die angibt wie lang Codeabschnitte mindestens sein müssen, damit sie als Klone angesehen werden. In welcher Einheit diese Mindestlänge angegeben wird, richtet sich nach dem Erkennungsverfahren. Beispiele für Mindestlängen sind Werte wie 10 Zeilen, 100 Tokens, 7 Anweisungen usw.

Normalisierung

Neben der Mindestlänge hat es sich bewährt, den Code hinsichtlich der Definition von Ähnlichkeit zu normalisieren. So werden in vielen Fällen Leerräume, Einrückungsstil und Kommentare im Code in Bezug auf Klone ignoriert. Eine weitere oftmals angewandte Normalisierung ist die Abstraktion von Bezeichnern, d. h. zwei Schleifen werden als Klone angesehen, auch wenn in der einen i und in der anderen j als Schleifenvariable verwendet wird. In ähnlicher Weise können Literale normalisiert werden. Komplexere Normalisierung könnte zum Beispiel darin bestehen, bei kommutativen Operationen die Reihenfolge der Operanden eindeutig zu machen oder bei Schleifenkonstrukten von der Art der Schleife zu abstrahieren. Welche Normalisierung sinnvoll ist, richtet sich im Allgemeinen stark nach dem Anwendungsfall. Da die Normalisierung aber einen sehr großen Einfluss auf die Ergebnisse hat, sollte diese gewissenhaft vorgenommen werden. Hierfür ist nicht zuletzt eine gewisse Erfahrung im Bereich der Klonerkennung erforderlich.

Ungleiche Abschnitte („Gaps“)

Auch wenn man mit der Normalisierung die Definition der Ähnlichkeit schon sehr weit fassen kann, ist weiterhin zu überlegen, ob Klone darüber hinaus kleinere ungleiche Abschnitte („Gaps“) beinhalten dürfen. Der Vorteil ist, dass mehrere kleine Klone dadurch zu größeren Klonen verschmelzen, was die Redundanz auf höherer Ebene sichtbar macht. Die Gaps weisen zudem auf Unterschiede hin, die möglicherweise unbeabsichtigt sind. Allerdings wird die Erkennung von Klonen mit Gaps nicht von allen Werkzeugen unterstützt. Zudem muss festgelegt werden, wie viele Gaps ein Klon enthalten darf.

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.

Klon

Ein Quelltextabschnitt der zu mindestens einem anderen Quelltextabschnitt ähnlich ist. Alternativ wird auch der Begriff Fragment verwendet. Die Ähnlichkeit wird entweder durch ein Klonpaar oder eine Klonklasse repräsentiert.

Typ-1-Klone

Identische Quelltextabschnitte bis auf Layout und Kommentare.

Typ-1-Klonpaar

int a = 0; int b = a * a; String str = "Peter";

int a = 0; // Comment int b = a * a; String str = "Peter";

Typ-2-Klone

Typ-1-Klone, bei denen zusätzlich Unterschiede in den Bezeichnern oder Literalen existieren.

Typ-2-Klonpaar

int a = 0; int b = a * a; String str = "Peter";

int a = 0; // Comment int x = a * a; String str = "Peter";

Typ-3-Klone

Typ-2-Klone, die ungleiche Abschnitte (Gaps) enthalten. Insbesondere in der englischsprachigen Literatur wird auch der Begriff Near-Miss Clone verwendet.

Typ-3-Klonpaar

int a = 0; int b = a * a; String str = "Peter";

int a = 0; // Comment int x = a * a; print(b); String str = "Peter";

Typ-4-Klone

Klone, die semantisch ähnlich, aber nicht zwingend syntaktisch ähnlich sind. Die syntaktische Ähnlichkeit liegt typischerweise unter 16 % und andere Unterschiede liegen in den genutzten Algorithmen, Datenstrukturen, benutzten Bibliotheken, Ein-/Ausgabebehandlung und dem objektorientierten Design. Aufgrund der Unmöglichkeit der Bestimmung von semantischer Ähnlichkeit hat dieser Klontyp wenig praktischen Nutzen.

Klonpaar

Ein Klonpaar repräsentiert die Relation zwischen exakt zwei ähnlichen Quelltextabschnitten (Klonen).

Klonklasse

Eine Klonklasse repräsentiert die Relation zwischen zwei oder mehr ähnlichen Quelltextabschnitten (Klonen).

Klonüberdeckung

Der Anteil des Systems der Teil eines Klons ist. Wird häufig verwendet, um das Ausmaß der Redundanz in einem System zu quantifizieren.

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.