Prof. Dr. Rainer Koschke - Uni Bremen || Startseite · Supremum und In mum Verkurz tes Hasse-Diagramm Merkmalsuche Weitere Anwendungen der Begri sanalyse Wiederholungsfragen Rainer

Vorlesung Software-Reengineering

Prof. Dr. Rainer Koschke

Arbeitsgruppe SoftwaretechnikFachbereich Mathematik und Informatik

Universitat Bremen

Wintersemester 2008/09

Uberblick I

1 Merkmalsuche

Merkmalsuche

Merkmalsuche

1 MerkmalsucheAusgangsszenario fur MerkmalsucheStatische AnalyseDynamische AnalyseStatische und dynamische AnalysenFormale Begriffsanalyse

Partielle OrdnungSupremum und InfimumVerkurztes Hasse-Diagramm

MerkmalsucheWeitere Anwendungen der BegriffsanalyseWiederholungsfragen

Rainer Koschke (Univ. Bremen) Vorlesung Software-Reengineering WS 2008/2009 3 / 27

Merkmalsuche

Merkmalsuche

Lernziele

Ausnutzung aller verfugbarer Information (statisch und dynamisch)Suche nach Merkmalen (statt Programmmustern)

Kontext

Weitere Anwendung der BegriffsanalyseUnterstutzung der Lokalisierung beim Programmverstehen


Merkmalsuche

Szenario fur Merkmalsuche in einem Zeichentool

Ziel:

Rekonstruktion von Traceability-Abbildung:Merkmal (Feature) → Implementierungskomponenten



Ziel:

Rekonstruktion von Traceability-Abbildung:Merkmal (Feature) → Implementierungskomponenten

20

09

-02

-02


Merkmalsuche

Ausgangsszenario fur Merkmalsuche


• Ihre Aufgabe ist es, fur ein System mit mehr als 10,000 Routinen

– ein Merkmal hinzuzufugen, zu korrigieren oder zu andern– oder einfach die Implementierung eines Merkmals zu verstehen.

• Wo beginnen Sie?

• Merkmalsuche:

– welche Komponenten eines Systems implementieren ein einzelnesMerkmal bzw. eine Menge von Merkmalen?

Merkmalsuche

Merkmale und Komponenten

Ein Merkmal ist eine realisierte funktionale oder nicht-funktionaleEigenschaft des Systems.

Eine Komponente ist eine ausfuhrbare Einheit, z.B.:

eine einzelne Anweisung oder ein Ausdruck,

eine Routine (Funktion, Prozedur),

ein Modul,

ein Subsystem,

eine Task, ein Thread oder Prozess.

Im Folgenden:

Merkmal = von außen anstoßbares und beobachtbares Verhalten desSystems, das auf Komponenten abgebildet werden kann.

Komponente = Routine.


Merkmalsuche

Statische Analyse nach Chen und Rajlich (2000)

codesource

extractor

callgraph

traversal

callgraphcall graph

Probleme:

Wo beginnen?

Wo fortfahren?

Wo aufhoren?

Prazision der statischenExtraktion?

main

draw draw arc

set text

set ru ll

set centc

set cente

move

load

save


Merkmalsuche

Zwei dynamische Ausfuhrungs-Traces (Wilde u. a. 1992)

source

difference

starting set

for static

analysis

code

invoke with feature

invoke w/o feature

trace

trace

profiler

profiler

invoking

input set

excluding

input set

compiler executable


Merkmalsuche

Dynamische Aufrufgraphen

mit Merkmal

main

draw draw arc

set text

set ru ll

set centc

set cente

move

load

save

ohne Merkmal

main

draw draw arc

set text

set ru ll

set centc

set cente

move

load

save

Differenz:

main

draw draw arc

set text

set ru ll

set centc

set cente

move

load

save


Merkmalsuche

Probleme der dynamischen Analyse

Invoking-Input-Set – Excluding-Input-Set kann

immer noch sehr viele nicht-merkmalspezifische Routinensowie nicht wirklich merkmalspezifische Routinen enthalten.

Resultate hangen von der Eingabe ab;

d.h. Resultate bilden nur einen Startpunkt fur weitere statischeAnalysen.

Wo soll mit der statischen Analyse begonnen werden?

Das Resultat differenziert die identifizierten Routinen nicht weiter.


Merkmalsuche

Statisch und dynamisch nach Eisenbarth u. a. (2003)

codesource

extractor

callgraph

traversal

callgraphcall graph

invoke feature f1

invoke feature f2

compiler executable

trace

trace

trace

profiler

profiler

profilerinvoke feature fn

concept

analysis

latticeconcept

... ... ... ...

,. . .

routines (f1)

routines (f2)

routines (fn)

invocationtable


Merkmalsuche

Szenarien fur das Grafikprogramm

zE eine Ellipse zeichnenzK einen Kreis zeichnenzR ein Rechteck zeichnenzT Text zeichnen


Merkmalsuche

Aufruftabelle

zE zK zR zT

main × × × ×draw × × × ×draw arc × ×set centc ×set cente ×set ru ll ×set text ×


Aufruftabelle

zE zK zR zT


20

09

-02

-02


Merkmalsuche

Statische und dynamische Analysen

Aufruftabelle

Die Darstellung der Relation in Form einer Aufruftabelle erfolgt im Kontext der Merkmalsuche aus Platzgrundenkonsequent transponiert, da wir es stets mit mehr Routinen als Merkmalen zu tun haben werden.

Merkmalsuche

Begriffsanalyse (Concept Analysis)

Menge O von Objekten

Menge A von Attributen

Relation I ⊆ O ×Adas Tripel C = (O,A, I) wird formaler Kontext genannt

fur eine Menge von Objekten O ⊆ O ist α(O) die Mengegemeinsamer Attribute:

α(O) := {a ∈ A | (o, a) ∈ I fur alle o ∈ O}

fur eine Menge von Attributen A ⊆ A ist ω(A) die Menge dergemeinsamen Objekte:

ω(A) := {o ∈ O | (o, a) ∈ I fur alle a ∈ A}


Merkmalsuche

Begriffsanalyse (Concept Analysis)

Ein Paar aus Objekten und Attributen c = (O,A) heißt Begriff(Concept), genau dann, wenn

A = α(O)

und gleichzeitigO = ω(A)

Begriff entspricht einem maximalen Rechteck in der Tabelle (moduloZeilen- und Spaltenpermutationen).

Fur einen Begriff c = (O,A) ist

O = extent(c) (extent) undA = intent(c) (intent) des Begriffs c .


Merkmalsuche

zE zK zR zT


({main, draw},{zE,zK, zT, zR })({draw arc, main, draw}, {zE,zK})({set cente, draw arc, main, draw}, {zE})({set centc, draw arc, main, draw}, {zK})({set text, main, draw},{zT})({set ru ll, main, draw},{zR})({set ru ll, set text, set centc, set cente, draw arc, main, draw}, ∅)


Merkmalsuche

Partielle Ordnung von Begriffen

Partielle Ordnung ≤:

Seien c1 = (O1,A1) und c2 = (O2,A2) zwei Begriffe; dann

c1 ≤ c2 :⇔ O1 ⊆ O2

oder, dualc1 ≤ c2 :⇔ A2 ⊆ A1

c2 ist Oberbegriff (Superconcept) von c1

c1 ist Unterbegriff (Subconcept) von c2

⇒ c2 hat mindestens die Objekte von c1 und c1 hat mindestens dieAttribute von c2.

Bsp.: ({draw arc, main, draw}, {zE,zK})≤ ({set centc, draw arc, main, draw}, {zK})Falls weder c1 ≤ c2 noch c2 ≤ c1, dann sind c1 und c2

unvergleichbar.


Merkmalsuche

Begriffsverband

Menge L aller Begriffe eines Kontexts C zusammen mit Halbordnung ≤bilden einen vollstandigen Verband, den so genannten Begriffsverband:

L(C ) = {(O,A) ∈ 2O× 2A | A = α(O) und O = ω(A)}

Hasse-Diagramme visualisieren die Relation <:

c1 < c2 ⇔ c1 ≤ c2 und es gibt keinen Begriff c(6= c1, c2), mit c1 ≤ c ≤ c2


Merkmalsuche

Hasse-Diagramm

draw Circledraw Ellipsis

maindraw

maindraw

draw arc

maindraw

draw arc

set ru llset textset centcset cente

maindraw

draw arc

maindraw

maindraw

draw Ellipsisdraw Circledraw Textdraw Rectangle

2 4 53

0

1

draw arc

set cente

set ru ll

draw Rectangle

draw Ellipsis

set centc

draw Circle

draw Textset text

6

maindraw


Merkmalsuche

Infimum und Infimum

Fur zwei Begriffe c1 und c2

Gemeinsamer Unterbegriff Infimum u

(O1,A1)u(O2,A2) = (O1 ∩ O2, α(O1 ∩ O2))

Begriff, der die Menge der gemeinsamen Attribute zweierObjektmengen enthalt

Gemeinsamer Oberbegriff Supremum (t)

(O1,A1)t(O2,A2) = (ω(A1 ∩ A2),A1 ∩ A2)

Begriff, der die Menge der gemeinsamen Objekte zweierAttributmengen umfasst


Merkmalsuche

Verkurztes Hasse-Diagramm des Begriffsverbands

2 4 53

0

1

draw arc

set cente

set ru ll

draw Rectangle

draw Ellipsis

set centc

draw Circle

draw Textset text

6

maindraw


Merkmalsuche

Merkmalsuche

2 4 53

0

1

draw arc

set cente

set ru ll

draw Rectangle

draw Ellipsis

set centc

draw Circle

draw Textset text

6

maindraw

Fur Kreis zeichnen:

spezifisch: set centcsehr relevant: draw arcetwas relevant main, drawirrelevant alle anderen

main

draw draw arc

set text

set ru ll

set centc

set cente

move

load

save


Merkmalsuche

Weitere Anwendungen der Begriffsanalyse

Anwendungsbeispiel: Refactoring von Klassenhierarchien:

Sammle alle erforderlichen Attribute fur jede Instanz einer Klasse →Tabelle

Erstelle Begriffsverband fur Tabelle.

→ Jedes Konzept ist prinzipiell eine Klasse.

→ Die ≤-Relation stellt die Vererbung dar.

→ Supremum: gemeinsame Oberklasse.

→ Infimum: gemeinsame Unterklasse.

– Snelting und Tip (2000)


Merkmalsuche

Wiederholungs- und Vertiefungsfragen I

Wie kann man bei der Lokalisierung von Merkmalen prinzipiellvorgehen, d.h. welche Verfahren kommen in Frage?

Wie konnnen Merkmale mit Hilfe der Begriffsanalyse identifiziertwerden?

Was ist der formale Kontext hierfur?

Welche Rolle spielt der Begriffsverband? Wie lasst er sichinterpretieren?

Welche Rolle spielt die statische Analyse? Warum ist sie notwendig?

Wie funktioniert die inkrementelle Begriffsanalyse? Und wie kann diesfur die Merkmalsuche ausgenutzt werden?

Wie findet man Merkmale, wenn es keine Ein-zu-eins-Beziehungzwischen Merkmalen und Szenarien existiert?


Merkmalsuche

1 Chen und Rajlich 2000 Chen, Kunrong ; Rajlich, Vaclav: CaseStudy of Feature Location Using Dependence Graph. In: Proceedings ofthe 8th International Workshop on Program Comprehension. Limerick,Irland : IEEE Computer Society Press, Juni 2000, S. 241–249

2 Eisenbarth u. a. 2003 Eisenbarth, Thomas ; Koschke, Rainer ;Simon, Daniel: Locating Features in Source Code. In: IEEE ComputerSociety Transactions on Software Engineering 29 (2003), Marz, Nr. 3,S. 210–224

3 Snelting und Tip 2000 Snelting, Gregor ; Tip, Frank:Understanding Class Hierarchies Using Concept Analysis. In: ACMTransactions on Programming Languages and Systems 22 (2000), Mai,Nr. 3, S. 540–582

4 Wilde u. a. 1992 Wilde, Norman ; Gomez, Juan A. ; Gust,Thomas ; Strasburg, Douglas: Locating User Functionality in OldCode. In: Proceedings of the International Conference on SoftwareMaintenance. Orlando, FL, USA : IEEE Computer Society Press,November 1992, S. 200–205


Documents

Prof. Dr. Rainer Koschke - Uni Bremen || Startseite · Supremum und In mum Verkurz tes Hasse-Diagramm Merkmalsuche Weitere Anwendungen der Begri sanalyse Wiederholungsfragen Rainer