UML-Diffing

Themen

• Themen
• Uml-Diagramme und ihre Repräsentation
• Besonderheiten beim UML-diffing
• Difference Detection in UML Class Diagrams by Martin Girschick
  • Algorithmus
  • Vergleichsfunktion
  • Visualisierung
  • Implementierung
  • Weitere Arbeit
• UMLDiff by Zhenchang Xing, Eleni Stroulia
  • Namensähnlichkeit Heuristik
    • Longest Common Subbsequence (LCS)
    • Most Common Pairs
  • Global Similarity Algorithm
  • Produktiver Einsatz
  • Meine Meinung
• Generic Uml Diffing
  • Algorithmus

Uml-Diagramme und ihre Repräsentation

• Hierarchische Ordnung:
  Packages > Classes, Interfaces > methods,attributes
• Baumartige Struktur in Klassendiagramm - jedes Element hat genau einen Elternknoten

Besonderheiten beim UML-diffing

• Diffing im Allgemeinen: Vergleich zweier Subjekte welches in einer Formel resultiert die angibt welche Einfüge/Entferne und Verschiebe Operationen auf einem der beiden ausgeführt werden muss um das Andere zu erhalten
• Bekannteste 'diff' - vergleicht Textdokumente zeilenweise und nur Einfügen/Entfernen - wird z.B. in SVN benutzt
• Uml-Diagramme sind Textdokumente -> Xml-Dokumente -> haben spezielle Struktur und Semantik
  
  • diff - würde funktionieren (Textdokumente) - kann aber z.B. ein move nicht erkennen (löschen->einfügen)
    xmidiff.png In dem Screenshot sieht man, dass einige Attribute nach unten geschoben wurden, was in einem XML-Dokument eigentlich keine Relevanz haben sollte
    -> kein Gewinn das auf Textlevel zu vergleichen, da das höhere strukturierte Level dabei nicht respektiert wird.
  • generic xml-differ - theoretisch gute Idee - basiert darauf, dass XML-Dokumente Bäume sind und vergleicht dann 2 Bäume
    Könnte schon brauchbare Resultate liefern hat aber Nachteile:
    
    • meistens werden "Ähnlichkeiten" nicht unterstützt (z.B. bei Namen)
    • Basieren ähnlich wie diff nur auf Insert und Delete
    • benutzen nicht das uml-metamodel: können viele Informationen die theoretisch vorhanden sind nicht benutzen (Vergleich IKT: je mehr man über die Quelle kennt umso besser kann man sie behandeln)
  • UML-Diff:
    • Konzentration auf Ähnlichkeiten - im Besonderen Strings
    • Konzentration auf Metamodell
      • Suchalgorithmen suchen Schichtenweise. Vergleiche nur innerhalb einer Schicht: Klasse<->Klasse, Attribut<->Attribut
      • Suchalgorithmen von oben (Package) nach unten (Attribut,Operation)
      • Suchalgorithmen bauen sich Landmarks auf - zuerst Punkte die sehr ähnlich/gleich sind und als Referenz dienen

Difference Detection in UML Class Diagrams by Martin Girschick

• Typ eines XML-Elements nicht änderbar (Klasse wird nie Attribut)
• Reihenfolge Klassen, Attribute, Operationen nicht relevant.
• Reihenfolge Parameter relevant.
• Klassen, Attribute, Operationen, Parameter besitzen immer Attribut name
• name innerhalb eines Containers eindeutig (Außer überladene Operationen -> Signatur benutzen
• die id im xml diagramm ist eindeutig und nicht änderbar
• Stereotypen
  beschreibt Funktion des Elements aus einem festen Wortschatz z.B. bei Assoziation: Implicit
  wiki
  nicht änderbar (nur delete,add)
• Der Supplier einer Generalisierung kann nur entlang der eigenen Vererbungshierarchie verändert werden (ansonsten ist es andere Generalisierung)
• Assoziationen nur entlang der Vererbungshierarchie bewegt

Algorithmus

1. Pakete
   • modify (name) - verschieben und umbenennen
2. Klassen
   • suche im gesammten diagramm
   • verschoben - move - mit ihrem Inhalt
   • modify - name,typ
   • add, delete
3. Generalisierungen
   • modify - verschiebung innerhalb vererbungshierarchie
   • add, delete
4. Attribute - verschobenes Attribut kann verschobene Assoziation bedeuten
5. Assoziation
6. Operationen - auch klonbar
7. Operationen-Parameter

Vergleichsfunktion

	
findMatch(varElement, baseDiagram)
{
	varContainer = varElement.Container;
	baseContainer = getMatch(varContainer, baseDiagram);
	foreach (baseContainer)
		maxElement = highest match there;
	if (value(maxElement) < DEFINED_LIMIT)
		// maxElement = suche in anderen containtern auf der gleichen hierarchie ebene
	if (value(maxElement) < DEFINED_LIMIT2) // das element ist neu
		return null;
	return maxElement;
}
	

• location - 1. an der alten Stelle - 2. Vererbungshierarchie
• name - 1. Gleichheit, 2. Groß/KleinSchreibung, 3. Neuer Anfang,Ende 4. anderer Name
• stereotype - manche stereotype einmalig in container und können identifizierungsmerkmal sein
• type - Rückgabetyp oder bei Assoziationen supplier
• signature - bei Operation sehr markant
• parts - Inhalte von Paketen,Klassen
• predecesor - physischer vorgänger gleich

Visualisierung

Implementierung

Weitere Arbeit

UMLDiff by Zhenchang Xing, Eleni Stroulia

• Ziel tool "JDEvAn"
  • parst java-code und erstellt UML-Diagramm
  • über mehrere Versionen können strukturelle Differenzen gefunden werden
• Datenmodell = Baum mit virtuellen Wurzelknoten
• Matcht Elemente mit
  • Namensähnlichkeit Heuristik - Sicher, da es selten vorkommt dass ein Element entfernt wird und mit exakt dem gleichen Namen ein neues dazu kommt
  • Ähnliche Beziehungen zu anderen Elementen - z.B. Klassen mit gleichen Attributen und Methoden

Namensähnlichkeit Heuristik

Longest Common Subbsequence (LCS)

	
getLCSMetric(string s1, string s2)
{
	return length(LCS(s1, s2)) * 2 / (length(s1) + length(s2));
}
	

Most Common Pairs

	
getMostCommonPairs(string s1, string s2)
{
	s1 = upper(s1); // since reordering words will invalidate case sensitiveness
	s2 = upper(s2);
	s1 = pairs(s1); // will split abcde to ['ab', 'bc', 'cd', 'de']
	s2 = pairs(s2);
	union = len(s1) + len(s2);
	s1.retainAll(s2); // will only keep those blocks which both have in common
	return len(s1)*2 / union;
}
	

Global Similarity Algorithm

• next - matching-Elemente eines anderen levels, für nächste runde
• match - matching-elemente auf dem jetzigen level
• results - verarbeitete

Umldiff(vr1, vr2) {
	Queue next, match, results;
	level=VIRTUAL_ROOT; // beginnt mit virtuellen Root
	next.add([vr1, vr2]); // fügt model1 und model2 in die next-queue
	while (next != null) {
		match = next.duplicate();
		next.clear();
		// die schleife sucht nach neuen matches
		while(match != null) {
			Set s = match.pop();
			temp_match.add(s);
			HashMap[] c1 = s[1].getChildren();
			HashMap[] c2 = s[2].getChildren();
			identifyMatch(c1, c2, match, next);
		}
		match.addAll(temp_match);

		// leert die match-schlange und fügt sie zum ergebnis hinzu
		// gleichzeitig wird geguckt ob die kinder matchen und werden in die nextschleife eingereiht
		while(match != null) {
			Set s = match.pop();
			results.add(s);
			HashMap[] c1 = s[1].getChildren();
			HashMap[] c2 = s[2].getChildren();
			if(!childrenMatchChecked(s[1],s[2]))
				identifyMatch(c1, c2, match, next);
			// else ??
			identifyRename(c1, c2, match, next);
		}
		HashMap[] m1 = generateMoveCandidates(vr1, level);
		HashMap[] m2 = generateMoveCandidates(vr2, level);
		// versucht verschiebungen zu finden - also über mehrere level
		identifyMove(m1, m2, next);
		// geht eine ebene tiefer
		level++ ;
	}
	results.addAll(markAllUnmatchEntities(vr1, remove));
	results.addAll(markAllUnmatchEntities(vr2, add));
	diffAttributesAndDependencies(results);
}


identifyMatch(set1, set2, match, next) {
	for all e1 of a particular entity type in set1 {
		e2 = set2.search_entity(e1.name);
		if(e2 != null)
		{
			if(e2.level==level)
				match.add([e1, e2]);
			else
				 next.add([e1, e2]);
		}
	}
}

Produktiver Einsatz

Meine Meinung

Generic Uml Diffing

• Dokument hat einige Elemente
• Elemente haben speziellen typ und haben Beziehung zu anderen Elementen über ihre Referenz-Klasse
  Beispiele: Packages, Classes, operations, attributes, parameters
• Attribute hat name und value Paare - z.B. isAbstract mit true,false
• Composite: elemente haben subelemente

Algorithmus