# Determining Detailed Structural Correspondence for Generalization Tasks (ESEC/FSE 07)

100 %
0 %
Technology

Published on November 19, 2008

Author: rylan.cottrell

Source: slideshare.net

## Description

Automatically determining correspondences as an early step in a generalization task.

http://doi.acm.org/10.1145/1287624.1287649

Determining Detailed Structural Correspondence for Generalization Tasks Rylan Cottrell, Joseph J. C. Chang, Robert J. Walker, Jörg Denzinger Laboratory for Software Modiﬁcation Research University of Calgary

Deciding whether to generalize •  What commonalities and differences exist between two implementations? •  Should the commonalities be refactored? •  This is difﬁcult to do because: •  Fine grained details matter. •  Ordering, name changes, and typing obfuscate commonalities. •  Manual approach requires mental juggling.

Example Problem Method B Method A Rec computeBounds ( Tree tree, Rec computeBounds ( TreeItem item) { TableItem item, Table table) { Rec cell = item.getBounds(); Rec rect = item.getImageBounds(); Rec cell = item.getBounds(); cell.y = rect.y + rect.width; Rec rect = item.getImageBounds(); cell.x = rect.x + rect.height; cell.x = rect.x + rect.width; Rec area = tree.getClientArea(); cell.width -= rect.getLength(); cell.width -= rect.getLength(); Rec area = table.getClientArea(); Rec editorRect = new Rec(cell.x, cell.y); Rec editorRect = new Rec(cell.x, cell.y); if (grabHorizontal) { if (grabHorizontal) if (tree.getColumnCount() == 0) editorRect.width = Math.max( cell.width = area.x + area.width - cell.x; cell.width, area.width); editorRect.width = Math.max( return editorRect; cell.width, area.width); } } return editorRect; }

Example Problem Method B Method A Rec computeBounds ( Tree tree, Rec computeBounds ( TreeItem item) { TableItem item, Table table) { Rec cell = item.getBounds(); Rec rect = item.getImageBounds(); Rec cell = item.getBounds(); cell.y = rect.y + rect.width; Rec rect = item.getImageBounds(); cell.x = rect.x + rect.height; cell.x = rect.x + rect.width; Rec area = tree.getClientArea(); cell.width -= rect.getLength(); cell.width -= rect.getLength(); Rec area = table.getClientArea(); Rec editorRect = new Rec(cell.x, cell.y); Rec editorRect = new Rec(cell.x, cell.y); if (grabHorizontal) { if (grabHorizontal) if (tree.getColumnCount() == 0) editorRect.width = Math.max( cell.width = area.x + area.width - cell.x; cell.width, area.width); editorRect.width = Math.max( return editorRect; cell.width, area.width); } } Correspondence return editorRect; } No Correspondence

Commonalities & Differences Rec computeBounds ( ? Item, Tree tree, TableItem  ? ? ){ TreeItem Table table Rec cell = item.getBounds(); Rec rect = item.getImageBounds(); ? cell.y = rect.y + rect.width; rect.width; cell.x = rect.x + ? rect.height; ? cell.width -= rect.getLength(); Rec area = ? tree.getClientArea(); Rec area = Rec editorRect = new Rec(cell.x, cell.y); table.getClientArea(); if (grabHorizontal){ ? if (tree.getColumnCount() == 0) editorRect.width = Math.max( cell.width = cell.width, area.width); area.x + area.width - cell.x; return editorRect; Method A Method B Commonalities

Related Work •  lone detection [e.g., Baxter et al., ICSM 1998] C ‣  ail to show the detailed commonalities and F differences. •  eneralization based refactorings [Tip et al., G OOPSLA 2003] ‣  o indication of where to apply the N refactorings. •  nti-uniﬁcation [e.g., Burghardt. AIJ 2005] A ‣  he general problem of identifying detailed T correspondences is formally undecidable.

Correspondence Rec computeBounds (TableItem item, Rec computeBounds (Tree tree, Table table) { TreeItem item) { Rec cell = item.getBounds(); Rec cell = item.getBounds(); Rec rect = item.getImageBounds(); Rec rect = item.getImageBounds(); cell.x = rect.x + rect.width; cell.y = rect.y + rect.width; cell.width -= rect.getLength(); cell.x = rect.x + rect.height; Rec area = table.getClientArea(); Rec area = tree.getClientArea(); Rec editorRect = new Rec(cell.x, cell.y); cell.width -= rect.getLength(); Rec editorRect = new Rec(cell.x, cell.y); if (grabHorizontal) editorRect.width = Math.max( if (grabHorizontal) { cell.width, area.width); if (tree.getColumnCount() == 0) cell.width = area.x + area.width - cell.x; return editorRect; } editorRect.width = Math.max( ` cell.width, area.width); } Method A return editorRect; } Method B

Correspondence Method A Method B

Correspondence Method A Method B

Correspondence Method A Method B

Correspondence Method A Method B

Correspondence Method A Method B

Similarity Measure • Recursive computation over subtree •  The similarity of two nodes is the percentage of the nodes in their subtrees that are “simply similar”. •  Two nodes are “simply similar” if the values they contain are equal (1 or 0) •  For example: = = area tree area table Rec getClientArea() Rec getClientArea()

Selecting Correspondence • Greedy algorithm. • Two nodes correspond, if the similarity is higher then a predetermined threshold value. • Unordered vs Ordered Determination

Unordered Determination •  Fields, methods Class A Class B computeBounds computeBounds

Unordered Determination •  Fields, methods Class A Class B computeBounds computeBounds

Unordered Determination •  Fields, methods Class A Class B computeBounds computeBounds

Unordered Determination •  Fields, methods Class A Class B computeBounds computeBounds

Ordered Determination ... ... cell.width -= rect.getLength(); Rec area = table.getClientArea(); Rec area = table.getClientArea(); cell.width -= rect.getLength(); ... ...

Resulting Correspondence (Anti-uniﬁer) Method A Method B Correspondence No Correspondence

Anti-uniﬁer Correspondence No Correspondence Variable Placeholders

Breakaway •  A plug-in to the Eclipse Integrated Development Environment (v3.2). •  Input ‣  Two Java classes. •  Output ‣  Generalized view.

Breakaway’s Output Rec computeBounds ( TableItem\$TreeItem item, Table\$Tree table\$tree) { Rec cell = item.getBounds(); Rec rect = item.getImageBounds(); /* Method B: cell.y = rect.y + rect.width; */ cell.x = rect.x + rect.width\$height; /* Method B: Rec area = table\$tree.getClientArea(); */ cell.width -= rect.getLength(); /* Method A: Rec area = table\$tree.getClientArea(); */ Rec editorRect = new Rec(cell.x, cell.y); if (grabHorizontal){ /* Method B: if (tree.getColumnCount() == 0) cell.width = area.x + area.width - cell.x; */ editorRect.width = Math.max(cell.width, area.width); } return editorRect; }

Evaluation I •  “Does Breakaway produce detailed- correspondence views comparable or better quality than developers?” •  11 test cases, 2 participants •  Produced generalizations that are within 13% of the developer generalized lines of code. •  Total time savings of 99% for those test cases.

Evaluation II •  “Does Breakaway assist developers in performing generalization tasks?” •  4 participants, 2 refactoring tasks. •  Observations •  A strategy of “differences” (when performing the task with the tool) was adopted. •  “The tool helped me quickly see where the two differed.” •  Knowing the detailed correspondences was important in performing the tasks.

Future Work •  Multiple Correspondences (Higher-order) ‣  Name differences can be eliminated ‣  Abundant amount of potential anti-uniﬁers. •  More advance approximation techniques. ‣  Weighting the AST nodes. ‣  Developer Input

Conclusion •  Outlined an approach for the creation of a generalized view, inspired by anti-uniﬁcation. •  We created a tool called Breakaway, plug-in to the Eclipse IDE. •  Demonstrated its potential beneﬁt to developers.

 User name: Comment:

## Related presentations

#### Neuquén y el Gobierno Abierto

October 30, 2014

Presentación que realice en el Evento Nacional de Gobierno Abierto, realizado los ...

#### Decision CAMP 2014 - Erik Marutian - Using rules-b...

October 16, 2014

In this presentation we will describe our experience developing with a highly dyna...

#### Schema.org: What It Means For You and Your Library

November 7, 2014

Presentation to the LITA Forum 7th November 2014 Albuquerque, NM

#### WearableTech: Una transformación social de los p...

November 3, 2014

Un recorrido por los cambios que nos generará el wearabletech en el futuro

#### O Impacto de Wearable Computers na vida das pessoa...

November 5, 2014

Um paralelo entre as novidades & mercado em Wearable Computing e Tecnologias Assis...

#### All you need to know about the Microsoft Band

November 6, 2014

Microsoft finally joins the smartwatch and fitness tracker game by introducing the...

## Related pages

### Determining detailed structural correspondence for ...

Determining detailed structural correspondence for generalization tasks. ... ESEC-FSE '07 Proceedings of ... the detailed structural correspondence ...

### Determining detailed structural correspondence for ...

... Determining detailed structural correspondence for generalization tasks ... Determining Detailed Structural Correspondence for Generalization Tasks

### Abstract

Determining detailed structural ... Generalization tasks ... An important step in generalization is identifying the detailed structural correspondence ...

### Vdiff: a program differencing algorithm for Verilog ...

Abstract. During code review tasks, comparing two versions of a hardware design description using existing program differencing tools such as diff is ...

View Rylan Cottrell’s ... Determining detailed structural correspondence for generalization tasks In Proceeding ESEC-FSE '07 Proceedings of ...

### ESEC/FSE 2007 - Research in Innovation, Design and ...

Determining Detailed Structural Correspondence for Generalization Tasks, Rylan R. Cottrell, ... A Structural Test Adequacy Criterion for Behavior ...

### A program differencing algorithm for verilog HDL

Determining detailed structural correspondence for generalization tasks. In ESEC-FSE ’07, ... determining the evolution of a set of lines of code is a ...

### dblp: 11. ESEC / 15. SIGSOFT FSE 2007: Dubrovnik, Croatia

SIGSOFT FSE 2007: Dubrovnik, Croatia. ... Determining detailed structural correspondence for generalization tasks. 165-174.