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

100 %
0 %
Information about Determining Detailed Structural Correspondence for Generalization Tasks...
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 Modification Research University of Calgary

Deciding whether to generalize •  What commonalities and differences exist between two implementations? •  Should the commonalities be refactored? •  This is difficult 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-unification [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-unifier) Method A Method B Correspondence No Correspondence

Anti-unifier 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-unifiers. •  More advance approximation techniques. ‣  Weighting the AST nodes. ‣  Developer Input

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

Add a comment

Related presentations

Related pages

Determining detailed structural correspondence for ...

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

Determining detailed structural correspondence for ...

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

Abstract

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

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 ...
Read more

Rylan Cottrell | LinkedIn

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

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 ...
Read more

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 ...
Read more

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

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

CiteULike: spl's Walker [2 articles]

spl's Walker [2 articles] ... Determining Detailed Structural Correspondence for ... Generalization tasks are important for continual improvement ...
Read more

ESEC/FSE 2007 : Dubrovnik, Croatia, September 3-7, 2007 ...

... --Determining detailed structural correspondence for generalization ... Stefaniak --An analysis of developers' tasks using ... ESEC/FSE '07 : European ...
Read more