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.Markus Bautsch: Codewiederholung – Symbolische Konstanten. In: Strukturierte Programmierung. Wikibook
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.Stefan Wagner, Asim Abdulkhaleq, Ivan Bogicevic, Jan-Peter Ostberg, Jasmin Ramandani. How are functionally similar code clones different?. PeerJ Preprints, 2015. 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 eine 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.