Detecting Structural Design Patterns Based On Quick-Search Sequence And Behavior Template

Design patterns are widely used to address the recurring design problems during the process of software design and development.The information about design patterns used in software source code – design pattern instances reveal much about the high-level abstract design ideas.Accurately identifying and detecting design pattern instances in a software system can help developers and maintainers to understand its original design and implementation,facilitating maintenance,update and re-development.In recent years,many approaches have been proposed to automatically or semi-automatically detecting design pattern instances from software source code.Among these approaches,some approaches transform software source code and design patterns into certain graphs,and then exploit subgraph isomorphism techniques to detect design pattern instances.However,as mining isomorphic subgraphs is an NP-complete problem,those approaches usually fail to achieve satisfactory efficiency.In order to effectively solve the inefficiency of the approaches which are based on subgraph isomorphism,we propose an efficient approach to detect structural design pattern instances based on quick-search sequences and behavior templates.In the proposed approach,we transform software source code and design patterns into a certain form of weighted and directed graph namely Class Relationship Graph,and then detect all the subgraphs from the source code graph which are isomorphic to the Class Relationship Graph of a certain design pattern.The classes that each isomorphic subgraph's vertices represent then consist of a candidate instance.During the process of detecting design pattern instances,we construct a quick-search sequence for each design pattern,which describes the structural characteristics of design pattern and specify an order to efficiently search the roles of each design pattern.According to the quick-search sequence,we can greatly reduce the search space.Afterwards,we construct a specific behavior template,which is used to filter the false positives in the candidate instance set and further improve the processing efficiency.Finally,we exploit our approach on four well-known open-source software systems.The results demonstrate that our approach not only achieves nearly 100% recall and relatively high precision and F-measure on the benchmark we construct,but also significantlyimprove the performance.