Konstantin Romanovsky
email: kromanovsky@yandex.ru

Dmitry Koznov
email: dkoznov@yandex.ru

Leonid Minchin

Refactoring the Documentation of Software Product Lines

Keywords: Software Product Line, Refactoring, Documentation

de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Technical documentation is an important part of commercial software. The Development and maintenance of requirements and design specifications, user manuals, tutorials, etc. is a labor-intensive part of any software development process. Exactly like software, documentation could be volatile and multi-versioned, and it may also have a complex structure. Moreover, documentation is often developed in several natural languages and in different target formats, like HTML, PDF, and HTML Help. The Documentation of a software product line [START_REF] Northrop | A Framework for Software Product Line Practice[END_REF] (SPL), which is a set of software applications sharing a common set of features, -appears to be even more complicated than the documentation for stand-alone applications, since it contains multiple repetitions that should be explicitly managed to reduce documentation development effort.

In [START_REF] Koznov | DocLine: a Method for Software Product Line Documentation Development[END_REF] we presented DocLine -a technology for developing SPL documentation, which supports planned adaptive reuse. By providing an XML-language for documentation development, DocLine allows a three-level representation of documentation, namely as diagrams of reuse structure, as XML-specification and as generated target documents in PDF, HTML or other format. DocLine also provides process guidelines and is supported by the Eclipse-based toolset.

SPL development is a complicated evolutional process: While new products are developed, existing ones need maintenance and enhancement. The refactoring of SPL architecture and common assets is a popular approach to improving SPLs [START_REF] Trujillo | Feature Refactoring a Multi-Representation Program into a Product Line[END_REF][START_REF] Calheiros | Product Line Variability Refactoring Tool. 1st Workshop on Refactoring Tools[END_REF][START_REF] Liu | Feature oriented refactoring of legacy applications[END_REF][START_REF] Critchlow | Refactoring product line architectures[END_REF][START_REF] Alves | Refactoring Product Lines[END_REF].

The purpose of this paper is to extend the idea of SPL refactoring to documentation development. Indeed, XML-based approaches to documentation development (like DocBook [START_REF] Walsh | DocBook: The Definitive Guide[END_REF], DITA [START_REF] Day | Introduction to the Darwin Information Typing Architecture -Toward portable technical information[END_REF]) are becoming more and more popular, while turning documentation into a kind of formal specification. If we extract and explicitly mark up reusable text fragments to be used in newly created documents, the target representation of existing documents should not change (though XML-specification would be changed). Therefore, we consider it reasonable to use the term refactoring for such transformations.

In this paper, we propose a refactoring-based documentation development process model, as well as offering a set of refactoring operations. Also, we describe their implementation in the context of DocLine toolset, and discuss an experiment in which we applied the proposed approach to the documentation of a telecommunication systems SPL.

Background

Software Product Line Development

Back in 1976, Parnas noted that it was efficient to create whole product families [START_REF] Parnas | On the Design and Development of Program Families[END_REF] instead of creating stand-alone systems. In present, this idea is actively being developed. In [START_REF] Clements | Software Product Lines: Practices and Patterns[END_REF], a software product line is defined as "a set of software-intensive systems that share a common, managed set of features satisfying the specific needs of a particular market segment or mission and that are developed from a common set of core assets in a prescribed way".

Product line evolution is an important issue in product line development. At first, top-down methods of product line development were created, for example DSSA [START_REF] Tracz | Collected Overview Reports from the DSSA Project[END_REF]. Top-down methods involved starting development with an in-depth domain analysis, identifying potential reuse areas, and developing common assets, and, afterwards, moving to product line members' development. Such methods require a lot of investment, but ensure flexible reuse, efficient maintenance and new products creation [START_REF] Clements | Being Proactive Pays Off[END_REF], thus bringing significant economic (and time-to-market) gain after the development of several products. Ultimately, new product development could be done just by selecting and configuring common assets [START_REF] Krueger | New Methods in Software Product Line Practice[END_REF]. These methods, however, involve serious risks, because, should the number of developed products remain small, investment will not pay off.

Light-weight bottom-up methods were designed to mitigate these risks. They suggest starting from developing a single product and moving to developing a product line only when product perspectives become clear [START_REF] Krueger | Eliminating the Adoption Barrier[END_REF]. To facilitate this move, common assets are extracted from "donors" (stand-alone products) and form the basis of further development. This approach significantly reduces cost and time to market for the first product, but brings in less profit when a number of products increases.

The protagonists of both approaches agree that the need for change in SPL architecture or common assets arises regularly during product line evolution, but this change should not affect the behavior of products. Moreover, in bottom-up approaches such changes are the foundation of the development process.

Refactoring

Refactoring is the process of changing a software system in such a way that it does not alter the external behavior of the code, yet improves its internal structure [START_REF] Fowler | Refactoring: Improving the Design of Existing Code[END_REF]. It became popular in agile software development methods because it provides an alternative to expensive preliminary design by allowing for constant improvement of software architecture while preserving the behavior of software.

Refactoring helps to fulfill particular tasks, like code structure and code representation refinement (dead code elimination, conditional expressions simplification, method extraction, etc.), and OO-hierarchy refinement (moving a field between classes, class extracting, pulling a field up/down the hierarchy, etc.). Also, there are so called "big refactorings", for example, transition from procedural to object-oriented design.

Refactoring can be done manually, but ensuring that the behavior of a system remains unchanged is not an easy task. As trivial an operation as it may seem like, renaming a method involves finding and modifying all of its calls (including calls via objects of all derived classes) and could affect the entire application source code. There are tools that facilitate refactoring by automating typical refactoring operations while ensuring correctness of source code transformations (correctness here means that the code remains compilable and its external behavior remains the same). Moreover, some toolsets support manual refactoring, including big refactoring, by providing means for automated regression testing (including, but not limited to unit testing).

Refactoring in Product Line Development

A lot of research focuses on SPL refactoring. In [START_REF] Calheiros | Product Line Variability Refactoring Tool. 1st Workshop on Refactoring Tools[END_REF], a feature model refactoring method is proposed as a way to improve the set of all possible product line configurations, that is, to maximize the potential for new products creation. In [START_REF] Trujillo | Feature Refactoring a Multi-Representation Program into a Product Line[END_REF], the authors introduce a method of decomposing an application to a set of features for using them in product line development. What is offered in [START_REF] Critchlow | Refactoring product line architectures[END_REF] is a set of metrics and a tool for refactoring SPL architecture. All the methods above are aimed to get better product line variability by extracting common assets and improving their configurability.

XML-Based Approaches to Technical Documentation Development

Many documentation development approaches employ the concept of content and formatting separation, which means that meaningful document constructions, for example parts, chapters, sections, tables, are separated from their formatting (for example, information about a title font and size selection is not part of content; therefore it is defined separately). This idea was introduced well in advance of XML and it was implemented, for example, in the TeX typesetting system [17] by Donald Knuth. Modern XML-based approaches to documentation development make use of this idea as well as supporting single sourcing, that is developing several documents on the basis of a single source representation [START_REF] Rockley | Managing Enterprise Content: A Unified Content Strategy[END_REF]. The appropriateness of using such technologies is widely discussed by technical writers [START_REF] Clark | Rhetoric of Present Single-Sourcing Methodologies[END_REF]. Research data in this area show that the advantages of using XML technology in middle-size and large companies justify the cost of their adoption (see, for instance, [START_REF] Albing | Combining Human-Authored and Machine-Generated Software Product Documentation[END_REF]). In practice, such XML-based technologies as DocBook [START_REF] Walsh | DocBook: The Definitive Guide[END_REF] and DITA [START_REF] Day | Introduction to the Darwin Information Typing Architecture -Toward portable technical information[END_REF], are actively adopted by the industry in dozens of large companies and projects, including IBM, PostgreSQL, Adobe, Sun, Cray Inc. [21], Unix-systems distributives, window environments (GNOME, KDE) [22].

The DocLine Approach

Basic Ideas

The DocLine approach [START_REF] Koznov | DocLine: a Method for Software Product Line Documentation Development[END_REF] was designed for developing and maintaining SPL technical documentation. One distinct characteristic of such documentation is that there are a lot of text reuse opportunities both in single product documentation and among similar documents for different products. DocLine introduces planned adaptive reuse of documentation fragments. Reuse is planned with the help of a visual modeling technique which allows creating, navigating and modifying a scheme of reusable fragments (common assets) and their relations. Adaptive reuse means that common assets can be configured independently for each usage context. DocLine features an XML-based language DRL (Documentation Reuse Language), intended for designing and implementing reusable documentation. It also offers a model of documentation development process, and a toolset integrated into Eclipse IDE. DocLine was presented in detail in [START_REF] Koznov | DocLine: a Method for Software Product Line Documentation Development[END_REF]; therefore we now focus on the basic features of DRL which are critical to explaining the refactoring operations we propose. Also we describe a process model for developing product line documentation, provided by DocLine.

In order to implement text markup we use the well known DocBook [START_REF] Walsh | DocBook: The Definitive Guide[END_REF] approach that is a standard de factum in the Linux/Unix world. In fact, DRL extends DocBook to include an adaptive reuse mechanism. DRL-specifications are first translated by the DocLine toolset into plain DocBook format; then, the DocBook utilities are used to produce target documents in a variety of formats (PDF, HTML, etc).

DRL Overview

The most important kind of common assets in DRL is an information element, which is defined as а context-independent reusable text fragment. In order to put a set of information elements together, DocLine provides what is called an information product, which is a template of a real document, like a user guide or a reference manual. Every information element could be included in any other information element or information product. These inclusions can be optional or mutually dependent, and all such variation points must be resolved to derive the specific document from an information product.

DRL provides two mechanisms of adaptive reuse: customizable information elements and multi-view item catalogs.

Customizable information elements. Let us look at the documentation of a phones product line with a CallerID function. It could have an information element named "Receiving incoming calls" containing a text like this:

Once you receive an incoming call, the phone gets CallerID information and displays it on the screen.

(

) 1
Phone may have additional ways of indicating a caller, e.g. a phone for the visually impaired could have a voice announcement instead of a visual presentation, and thus the example (1) would look as follows:

Once you receive an incoming call, the phone gets CallerID information and reads it out.

(

To facilitate the transformation of the sentence in (1) into the sentence in (2) using an adaptive reuse technique, the corresponding information element must be written in the following way (in the syntax of DRL):

<infelement id=CallerIdent>
Once you receive an incoming call, the phone gets CallerID information <nest id=DisplayOptions> and displays it on the screen</nest>. </infelement> [START_REF] Trujillo | Feature Refactoring a Multi-Representation Program into a Product Line[END_REF] In this example, we define an information element (<infelement/> tag) and an extension point inside it (<nest/> tag). When this information element is included in a particular context, any extension point can be removed, replaced or appended with custom content without having to modify the information element itself. If no customization is defined, the information element in (3) will produce the text as in (1) seen. The following customization transforms it into the text in (2): <infelemref infelemid=CallerIdent> <replace-nest nestid=DisplayOptions> and reads it out</replace-nest> </infelemref> (4)

The example (4) shows a reference to the information element (<infelemref/>) defined in the example (3) and the replacement of the extension point defined in this information element by new content (<replace-nest/>).

Multi-view item catalogs. In the documentation of most software products one can find descriptions of typical items of the same kind, for example, GUI commands. In different documents and contexts they are accompanied by a different set of details. In toolbar documentation, for example, commands are defined as an icon with a name and a description. In menu documentation you will see the name of a command, its description and accelerator key sequence; an online help also will contain a relevant tooltip text that shows up when a user drags the mouse cursor over the command button. All these fragments have common attributes of corresponding items. To allow the reuse of such attributes, DocLine introduces the concept of a catalog. A catalog contains a collection of items represented by a set of attributes, e.g. the GUI commands catalog may include a collection of GUI commands, each of them having a name, an icon, a description, an accelerator, a tooltip text, a list of side effects, usage rules, etc. Here is an example of such a collection of GUI commands for some software product represented as a catalog in DRL: <directory name="GUICommands"> <entry name="Print"> <attr name="name">Print</attr> <attr name="icon">Print.bmp</attr> <attr name="descr">This command …</attr> </entry> <entry name=" Save"> <attr name="name">Save</attr> <attr name="icon">Save.bmp</attr> <attr name="descr">This command …</attr> </entry> </directory>

In addition to a collection of items, a catalog contains a set of representation templates that define how to combine item attributes to get a particular item representation. The template in the example below represents a short notation of GUI commands including only the icon and the name: <dirtemplate name="toolbar_short" directory="GUICommands"> <fig>Images/<attrref name='icon'/></fig><attrref name="name"/> </dirtemplate> A representation template contains some text and references to item attributes (<attrref/>). When a technical writer includes a catalog item into a particular context, he or she must indicate the corresponding representation template and the item identifier. Then, the content of the template will be inserted into the target context and all the references to attributes will be replaced by corresponding attribute values.

Documentation Development Process Model

As we discussed above, there are two major models of product line evolution: topdown and bottom-up. Consequently, there are two models of documentation development. DocLine supports both models, but focuses mainly on the latter since it is more often used in practice. The scheme of the bottom-up model is shown in Fig. 1.

In case of the bottom-up model, a technical writer starts from the documentation of a particular product and does not pay attention to reuse techniques. Priority is given to achieving a specific business goal (e.g., a good documentation package for a concrete product), while further perspectives might not be clear. However, once a need for new products documentation arises, a technical writer can benefit from a reuse technique by analyzing reuse options, extracting common assets, and proceeding with the development of documentation on the basis of the common assets. This is an appropriate moment to adopt the DocLine technique. It is a straightforward task if the documentation has been developed by means of DocBook, or it can be easily converted to DocBook. In other cases the existing documentation should be manually ported to DocBook and then marked up with DRL constructions.

Refactoring of Product Lines Documentation 4.1 Refactoring Process

Let us look at the bottom-up process model for product line documentation development in greater detail from refactoring perspective:

1. DocLine is adopted when new product documentation is to be created.

2. To use DocLine, а technical writer analyzes the functionality of a new product, and finds similarities, additions and modifications compared to the functionality of existing products. 3. Then, a technical writer finds all fragments in the existing documentation that should be preserved, modified, added or deleted. 4. Then, some formal transformations are applied to documentation sources in order to turn them into correct DRL-specification (if documentation was developed using plain DocBook; otherwise documentation must be ported to DocBook before this step) and to explicitly mark common assets. Existing and newly created pieces of text which are not reused (or are identically the same) should be converted into a single large information element. DRLspecification is decomposed in-depth if the information element varies from one product to another, or if there are other compelling reasons for decomposition, e.g., simultaneous documentation editing by several technical writers.

The same model remains relevant when a new product is added to a product line, whose documentation has been already developed by using DocLine. In this case, some common assets could be reused "as is" in new product documentation, but typically there is always a need for the refinement of existing assets and the creation of new common assets.

Refactoring Operations

Let us discuss how exactly refactoring ideas are realized in text transformations. The first group consists of text transformations aimed at extracting common assets.

Extracting information element.

A fragment of text is extracted to a stand-alone information element. Then, it is replaced by a reference to the newly created information element. If the extracted fragment contains extension points, new adapters are created for all final information products to ensure that all manipulations with extension points are preserved. 2. Splitting information element. An information element is split into two information elements. All references and adapters are updated. 3. Importing of DocBook documentation. The entire DocBook documentation for a product is imported into the DocLine toolset. All the necessary elements are created: the entire documentation is placed into an information element that is included into a newly created information product. Also, a final information product is created. As a result, we receive the same target documentation as the documentation derived from initial DocBook documentation. 4. Extracting information product. A selected document (or a fragment) is extracted to an information product. It is followed by the creation of a final information product that uses the newly created element to produce the exact copy of the original document. This operation is normally used when plain documentation in DocBook is imported into the DocLine toolset and a technical writer needs to extract several information products from it.

The following operations are designed to facilitate core assets tuning (extending their configurability).

Converting to extension point. A text fragment inside an information element is

surrounded by an extension point. 6. Extracting to insert after / insert before. A trailing / heading text fragment inside an extension point is extracted and inserted into all existing references to the original information element as an Insert After / Insert Before construction.

If the text is outside any extension point, but inside an information element, a new empty extension point is created before / after the fragment. 7. Making a reference to an information element optional. A particular mandatory reference to an information element (infelemref) is re-declared as optional. In all existing final information products containing the above-mentioned information element, an adapter is created (or updated) to force the inclusion of the optional information element. 8. Converting to conditional. A selected text fragment is marked as conditional text (condition shall be provided by the technical writer). In all existing final information products containing the fragment, the condition is set to true to force the inclusion of the conditional text. 9. Switching default behavior on optional references to information element.

Depending on a technical writer's preferences optional references may be treated as included by default or excluded by default. When default behavior is switched, all adapters must be updated to ensure that the target documents stay unchanged.

The following operations are designed to facilitate the use of small-grained reuse constructions -dictionaries and multi-view item catalogs (directories). 10. Extracting to dictionary. A selected text fragment (typically, it is a single word or a word combination) is extracted to a dictionary and its entry is replaced by a reference to the newly created dictionary item. Then, documentation is scanned for other entries of the same item. Found entries could be replaced by references to the dictionary item.

Extracting to multi-view item catalog (directory). A new multi-view item

catalog item is created based on a selected text fragment. Then, the fragment is replaced by a reference to the newly created dictionary item with a selected (or newly created) item representation template. 12. Copying/moving dictionary/directory item to/from product documentation. A selected dictionary (or directory) item is copied (or moved) from the common assets to the context of particular product(s) documentation and vice versa. Thus the scope of the item is extended or narrowed.

The following operations facilitate renaming various structural elements of documentation.

13. Renaming. The following documentation items can be renamed: an information element, an information product, a dictionary, a directory, a dictionary item, a directory item, an extension point, a reference to an information element, a dictionary representation template. All references to renamed elements are updated.

Refactoring Operation Example

Let us consider an example of applying the refactoring operation of extracting information element. The purpose of this example is to show that refactoring operations require non-local source text modifications in order to keep target documents unchanged. Here is a fragment of a documentation source in DRL (note that all these constructions may be stored in physically different files):

<InfProduct id="phone_manual"> <InfElemRef id="basic_ref" infelemid="basic_function"/> </InfProduct> <InfElement id="basic_functions"> <Nest id="connect_options">You can connect your phone to </Nest> <Nest id="dial_options">You can dial numbers using </Nest> </InfElement> <FinalInfProduct name="office_phone" infproductid = "phone_manual"> <Adapter infelemrefid = "basic_ref"> <Insert-After nestid = "connect_options"> urban telephone network or office exchange. </Insert-After> <Insert-After nestid = "dial_options"> built-in numeric key-pad or phone memory. </Insert-After> </Adapter> </FinalInfProduct> This fragment contains an information product phone_manual that is the template of the user manual for a phone set. It contains a reference to the information element basic_functions describing basic phone functionality. Also, there is a specialization of the user manual: it is a final information product office_phone, that uses the phone_manual information product to produce a manual for an office phone.

If we run the operation of extracting information element for an extension point (nest) dial_options, we get the following changes. The information element basic_functions will look as follows (changed text is typed in boldface): <InfElement id="basic_functions"> <Nest id="connect_options">You can connect your phone to </Nest> <InfElemRef id="dial_number_ref" infelemid="dial_number"/> </InfElement> A new information element is created out of the extracted text fragment: <InfElement id="dial_number"> <Nest id="dial_options">You can dial numbers using </Nest> </InfElement> Finally, let us look at changes in the final information product office_phone (a changed text is typed in boldface): <FinalInfProduct name="office_phone" infproductid = "phone_manual"> <Adapter infelemrefid = "basic_ref"> <Insert-After nestid = "connect_options"> urban telephone network or office exchange. </Insert-After> </Adapter> <Adapter infelemrefid = "dial_number_ref"> <Insert-After nestid = "dial_options"> built-in numeric key-pad or phone memory. </Insert-After> </Adapter> </FinalInfProduct> As you can see, the manipulations with the extracted extension point were moved from the existing adapter to a newly created one that defines adaptations of the new information element.

The Toolset

Most of the proposed refactoring operations are implemented as part of the DocLine toolset. DocLine toolset is designed as a set of plug-ins for Eclipse IDE [START_REF] Koznov | DocLine: a Method for Software Product Line Documentation Development[END_REF]. The refactoring tool is embedded into the DRL text editor. In addition to the operations, the refactoring tool provides a framework for implementing new refactoring operations, and a support library that perform tasks typical of most refactoring operations, like DRL parsing (supporting multi-file documentation structure) and DRL generation.

The Experiment

The approach to refactoring of SPL documentation presented in this paper was applied to the documentation of a telecommunication systems product line. This product line includes phone exchanges of various purposes: private branch exchanges, inter-city gateways, transit exchanges, etc. For our experiment we selected two product line members -an exchange for public switched telephone network (hereinafter called PSTNX) and a special-purpose exchange (hereinafter called SPX). We decided to port user manuals of these products to DocLine.

During the analysis, we found that historically SPX was developed as a version of PSTNX with reduced functionality. In course of evolution, some functions of SPX were changed, so its user manual was updated accordingly.

First, we converted the documentation to DocBook (in our experiment it was done manually, although for some cases it could have been automated). Then, we started to introduce a DRL markup. We discovered a series of common terms and word combinations in the documentation and created dictionaries and directories to guarantee their unified use across the documents. After that, we "mined" some text fragments, which were similar in both documents, and wrapped them with information element constructions to make them available for reuse in various contexts. Then, we "fine-tuned" these information elements to prepare them for use in both documents.

We used the following refactoring operations in our experiment: importing of DocBook documentation, extracting information element, converting to extension point, extracting to insert after / insert before, making reference to information element optional, extracting to dictionary, extracting to directory. These operations helped us to build an efficient internal structure of the documentation and enable the reuse of text fragments across the two documents while preserving the view of the target documents.

One of our findings is that joining two products to form a family significantly differs from deriving a new product from an existing one to form a family. Let us consider an extracting information element operation. How do we find what to extract? Likely candidates are similar but not identical text fragments, but finding them in two documents with a total of 300 pages proved to be a very difficult task. This suggests that there is a need for a specific tool which a technical writer could use alongside with the refactoring tool, to facilitate finding potential common assets.

Conclusions and Further Work

The product line documentation refactoring approach proposed in this paper is designed to facilitate moving from monolithic documentation for one or several products to reusable documentation of a software product line with explicitly defined common assets. It can also be used for developing documentation for newly created product line members.

In our further research we plan to enable intelligent selection of candidates for refactoring: fragments to be extracted as information elements, frequently used words to be extracted to dictionaries and common word combinations to form multi-view item catalogs. What seems to be a promising approach to find candidates for an information element extraction is source code clones detection, since it could be enhanced so as to identify "polymorphic" clones. Techniques for product line variability management are also of interest to us because they could provide a technical writer with information on products variability that is more or less reflected in the documentation structure (e.g. common features in a product variability model correspond to information elements in a documentation).

Fig. 1 .

 1 Fig. 1. Bottom-up documentation development process.

We also plan to introduce means for "big refactorings" (major changes of documentation composed of series of automated and manual transformations). Entire automation for such an operation is impossible, but we could offer some useful services, for example, the automated checking of target documentation consistency.

Another area for further research is the pragmatics of refactoring, and we would like to propose some ideas of how to guide documentation refactoring. As for program code refactoring, there are coding conventions, rules of building OO hierarchy, off-the-shelf recommendations on using various refactoring operations, etc. We plan to develop a set of similar recommendations for our case. One more question of pragmatics is how to keep a balance between the configurability of documentation and the complexity of its structure.

Finally, we intend making a larger experiment which main goal will be to test the scalability of the proposed approach.

* This research is partially supported by RFFI (grant 08-07-08066-з).


Tomáš Tureček
email: tomas.turecek@vsb.cz

Petr Šaloun
email: petr.saloun@osu.cz

Advanced Data Organization for Java-Powered Mobile Devices

Keywords: Java, J2ME, Database, Midlet, Midletbase, storage

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Mobile devices are all around of us. They became so cheap and so useful that almost everyone of us has its own cellular phone. Today's cellular phones are quite universal as they can run various applications. The paper reports on continuation of previous research related to remote access to information systems [START_REF] Tureček | Remote Access to Information System via PDA[END_REF] and it describes advantages of using Java-powered portable devices and wireless connections. The paper presents research on J2ME database framework we are working on.

Motivation

There are many ways of integrating portable device with existing systems. One is to extend an existing IS with some interface and to implement thick client application into the mobile device communicating with the IS through this interface. We have applied this approach as it allows implementation of more complex logic into thick client. That is an advantage in cases like offline access to IS data. During our work on synchronization of thick IS clients we have noticed some weaknesses of J2ME storage capabilities. We were forced every time to create custom wrappers around RMS storage (Record Management System [START_REF] Keogh | J2ME: The Complete Reference[END_REF]). Those problems have inspired us to create extension to RMS in form of relational database.

Problem to solve

Thick client application demands some kind of storage to persist needed data. Reason for that can be fount in [START_REF] Tureček | Data organization on Java powered mobile devices[END_REF]. J2ME offers just simple storage called RMS (Record Management System [START_REF] Keogh | J2ME: The Complete Reference[END_REF]), which is in fact capable of storing byte arrays only. Developers are forced then to invent again and again their own RMS extension to persist primitive Java types. We have focused on this problem and we have created RMS extension simulating relational database over simple RMS storage.

Solution

State of the art was quite empty in the time we have started with our own database implementation. Only available solution was commercial solution PointBase Micro [START_REF][END_REF] and series of implementations of remote access to remote databases like Oracle Database Lite Edition [START_REF]Oracle Database Lite Edition[END_REF]. These particular solutions did not satisfy our needs because we needed combination of all those solutions. We needed J2ME relational database which can be easily extended with new functionality such as remote access to remote systems.

Presented solution behaves as usual relational database but it uses RMS for storing data. We call the extension as Midletbase (Midlet [START_REF] Keogh | J2ME: The Complete Reference[END_REF] database). Extension offers easy-to-use API to database engine allowing creating or dropping tables and inserting/ updating/deleting/searching table entries. Our database framework can look like another J2ME layer to J2ME developers (see Figure 1).

Fig. 1. Midletbase represents additional (database) layer to J2ME

Midletbase adds to J2ME following features:

• Data to store are organized into entries with defined data types.

• Entries are stored in tables.

• Tables are organized in databases.

• Database structure as well as data is persisted in RMS to have it accessible even after device restart. • Data is accessible through simple API with the same way that it is usual in relational databases. • API allows creating and dropping tables.

• API allows inserting, updating, deleting and searching over data in RMS.

• Midletbase is extensible so it enables developer to extend Midletbase functionality plug-in way and implement his/her own behaviour for database operations.

Preliminary implementation results were already published in [START_REF] Tureček | Data organization on Java powered mobile devices[END_REF]. Inspiration for our solution was based on our experience with J2ME and also on existing solutions [START_REF][END_REF][START_REF]Oracle Database Lite Edition[END_REF].

As the target platform we have selected CLDC 1.0 and MIDP 1.0. Reason for that is the Midletbase framework then will be usable on every single cell phone with Java support.

API

One of the requirements for the Midletbase framework was usability. Interface allows developers to use the storage with a simple way and following piece of code shows how easy is to initialize storage and to create table and insert there some entries.

Extensibility

Midletbase database engine implements Interceptor design pattern [START_REF]Interceptor design pattern on Daily development[END_REF]. Database engine is implemented as a chain of Interceptors and developer (using Midletbase) can create his/her own interceptors and plug them into database engine and to create this way some additional functionality (e.g. logging or triggers to his/her application). Developer is even able to completely change the engine behaviour like not to store data to RMS but to create connection to the server application and store data there.

Measures

We have performed set of measures showing characteristics of algorithms used in the implementation. They can be used for estimation of the effectiveness of Midletbase usage for certain purposes. This section shows characteristics of two usually used Midletbase use cases -create table and search the table. Following charts show average results from 20 measures. Unfortunately the short space in this paper prevents us from showing more characteristics of the framework.

Fig. 3. Characteristics of the create table algorithm.

Figure 3 shows the create table algorithm characteristics. Dependency is not linear and it opens opportunity for future work to optimize algorithms for better performance. Objective of the measure is to get chart trend so the concrete time values are not relevant here; also the measuring is done with emulator1 .

Fig. 4. Characteristics of the search table algorithm.

Figure 4 shows needed time for searching for entries (by key) in table with different number of entries. The characteristic is quite linear with some small overhead in case of first record store access. Chart above represents search without cache.

Future work

We are now working on JDBC driver for Midletbase to allow developers to use also standard DB interface.

Midletbase does not contain functionality related to database structure change. Tables and databases can be created or dropped but not altered. Functionality is not included so far because it is not needed functionality when we consider the framework usage -storage for deployed application. Such application has already steady DB structure.

In future we want also to focus on algorithms used in Midletbase. As we can see from section 2.5 there are opportunities to optimize those algorithms.

The topic of the research is really actual and solves incompleteness of today used standards. As a proof we can take [START_REF] Alier | J2MEMicroDB an open source distributed database engine for mobile applications[END_REF] where we can find similar solution to our independent one but our solution is more focused on extensibility and usage.

Conclusion

The paper presents an ongoing research responding to real needs reported by many developers of Java mobile applications. The need is to have smart-enough storage on J2ME CDLC 1.0+ MIDP 1.0+ platform. Presented solution fulfils those needs by providing a package implementing a relational database with many features and a user friendly interface. The work is still ongoing but we plan to release Midletbase package as soon as we get a stable well tested version. The current version is available only for pilot applications.

Fig. 2 .

 2 Fig. 2. Simplified class diagram depicting interceptor design pattern involvement in architecture and how the custom interceptors can be passed from Storage initialization throughTable to StorageInterceptingPoint class.

Performed with Sun Microsystems Wireless Toolkit emulator

2.5.3 on Dell Latitude D620 laptop (CPU Genuine Intel T2400, 2GB RAM)


Michal Dobi²
email: dobism@zmail.sk

Ubomír Majtás
email: majtas@fiit.stuba.sk

Mining Design Patterns from Existing Projects Using Static and Run-Time Analysis

Keywords:

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

It is not easy to develop a good design of a complex system. Experienced designer of object oriented software often rely on usage of design patterns that are known as good solutions to recurring problems. A design pattern can impact scalability of a system and denes the way of modication of the architecture without decreasing its quality. Patterns are based on experience of many software developers and they are abstractions of eective, reliable and robust solutions to repeating problems. A pattern describes a problem, its context and supplies some alternative solutions, each of them consisting of collaborating objects, their methods and services.

Introducing patterns to software design provides one more benet. While class in the object oriented paradigm makes it easier to understand the code by encapsulating the functionality and the data, an instance of a design pattern identies the basic idea behind the relations between classes. It is an abstract term that can help to understand design decisions made by the original developer. But how to nd instances of design patterns in the implemented system, when they represent an idea rather than just an implementation template? A large system has usually long lifetime and original architect of a particular component can leave the team before the system life cycle ends. Modication of the internal structure of a software component is a common need during the maintenance or when developing it for a long time. Therefore the precise documentation of design decisions by describing used design patterns becomes necessary. Unfortunately, such documentation is mostly obsolete or absent at all.

There can be plenty of design pattern instances in a large system, and each pattern can have many implementation variants. Moreover, a code fragment can play role in more than one pattern. It is unlikely to expect a human being to be able to orientate in a large mesh of connected classes forming a system. Thus, automatic analysis and search have to be done. We focused our eort on analysis of intermediate code produced by compilers of modern object oriented programming languages like C#. This code is also directly executable so its runtime behavior can be inspected as well. With the proposed method and the implemented tool, the valid pattern instances can be found more precisely, so the developers can become familiar with the analyzed system easier and have all the information necessary to make the correct design decisions while modifying it. Besides that, the library of patterns is kept open and new ones can be added using a special editor or by directly editing XML les.

Related work

There are some tools that support reverse engineering with design pattern support, but this feature is far from perfect and there is still research needed to be done. There are three main questions to answer when developing a solid design patterns mining tool.

First question that comes out is What to nd? It represents the challenge of dening a formal language for the design pattern description that would allow dynamic editing of the catalogue. For humans the most suitable is natural language as it is used in works like the GoF's catalogue [START_REF] Gamma | Design Patterns, Elements of Reusable Object-Oriented Software[END_REF]. It is good for description of the pattern's variability, but is insucient for the computer processing. UMLbased Design Pattern Modeling Language [START_REF] Mapelsden | Design Pattern Modelling and Instantiation using DPML[END_REF] is visual language consisting of 3 models (specication, instantiation and class diagram) that uses extensions capability of UML but authors propose just the forward engineering way of model transformations. Mathematical logic with its power is introduced in LanguagE for Patterns' Uniform Specication (LePUS) [START_REF] Eden | Precise Specication of Design Patterns and Tool Support in Their Application[END_REF]. It, however, is dicult to capture the leitmotif of pattern using LePUS -even GoF patterns are not fully written in it. Progressive way of pattern description applicable in the context of pattern mining utilizes XML -Design Pattern Markup Language [START_REF] Balanyi | Mining Design Patterns from C++ Source Code[END_REF] denes basic requirements on each class, operation and attribute so the group of them can be considered a pattern instance.

The answer to the question Where to search? starts with creation of system model. There are three basic ways how to get it automatically. First, static analysis of the source code comes in mind. It is straightforward, but the drawback is that it would require development of a new parser for each language analyzed system could use. Thus, lower level language would be useful -that is intermediate language like Java byte-code (JBC) or Common Intermediate Language (CIL).

All the languages of the .Net family (C#. Visual Basic, managed C++, J#, DotLisp, etc.) are translated to CIL when compiled. There exists also a transformation between the JBC and CIL using IKVM.NET [START_REF] Frijters | [END_REF]. Some behavioral analysis can be done directly from the statically written code -good examples are tools like Pinot (Pattern INference and recOvery Tool) [START_REF] Shi | Reverse Engineering of Design Patterns from Java Source Code[END_REF] or Hedgehog [START_REF] Blewitt | Automatic Verication of Design Patterns in Java[END_REF] identify blocks of code and data ow between them to gain the simple image of the idea behind the code and its dynamic nature. More precise perspective of a system can be gain by dynamic analysis realizable through proling API (e.g. CLR Proler uses it). Running the system and monitoring its behavior might not be the most reliable method, but it is the only way how to gain some very useful information about it (e.g. Wendehals uses this, but his tool is not really automatic [START_REF] Wendehals | Improving design pattern instance recognition by dynamic analysis[END_REF]).

Last of the three questions is How to search? There has been some works utilizing a graph theory to search the patterns in graph model of analyzed system, while mostly just static information were taken in account [START_REF] Balanyi | Mining Design Patterns from C++ Source Code[END_REF]. Similar to it, distance between graphs of an analyzed system and a pattern (dierence in the similarity of graphs) was introduced in the literature [START_REF] Tsantalis | Design Pattern Detection Using Similarity Scoring[END_REF]. A quick method of pattern recognition, useful mostly to speed up the search process in combination with something else, comes from the utilization of object oriented software metrics known from the algorithms for looking for bad smells in the code [START_REF] Antoniol | Using Metrics to Identify Design Patterns in Object-Oriented Software[END_REF].

Finally, rules and logic programming come alive in System for Pattern Query and Recognition [START_REF] Smith | SPQR: Flexible Automated Design Pattern Extraction From Source Code[END_REF] in cooperation with already mentioned language LePUS with all its benets and drawbacks.

Our approach

The main reason for design pattern mining is making the system understandable and easier for modication. The problem of many mining approaches presented before is the relatively high false acceptance ratio, they often identify elements that just look like pattern instance, but they are certainly not. Therefore we decided to focus on preciseness of the searching method that would try to identify only correct pattern instances that meet all constrains a man could dene on a pattern. The collaborating classes, methods and elds are marked as instance of particular design pattern when they really t the design pattern denition; so the software engineer can gain benets from using it.

The rst information that a software developer learns about a design pattern is mostly its structure. This static information is very important but is useless without the knowledge of the idea represented by pattern. What we want from our products -systems and programs -is the behavior rather than the structure and that is what species pattern most accurately.

To provide reliable results we decided to take three dierent types of analysis that need to come to an agreement whether the examined elements complies with pattern constrains or not: structural, semidynamic and dynamic (run-time) analysis.

Structural analysis

The rst and the easiest phase of the precise system analysis is the recognition of all types, their operations and data (attributes, local variables, method parameters). The search algorithm is based on graph theory, so we form the three types of vertex from these elements. Following information are recognized for each of them:

Unique identier of each element.

Recognition whether it is static.

Identication of parent -the element in which the current one is dened inside.

Type

The Type vertex represents class, abstract class, interface, delegate, enumeration or generic parameter. It contains identication of element type (Boolean values indicating whether it is a class, interface, etc.). Special type of edge identies the types the element derives from -this list contains the base type and all the interfaces implemented by it. Finally the child elements (inner classes, operations, attributes, etc.) are recognized forming new vertices connected to the current one with parent-identication edge.

Operation

The business logic of applications is dened inside the methods and constructors.

For these types of elements we recognize the following information:

Identication whether the operation is virtual. If so, the overridden virtual or abstract element is searched.

Recognition whether it is abstract.

Distinction between the constructors and common methods.

Returned type.

Parameters and local variables of the operation.

Data

Attributes, parameters and local variables are represented as the vertices of type data having the original scope stored as the vertex attribute. Each data eld has its type (identied by an edge connected to the vertex standing for the type). The type of collections is not important when looking for design pattern instances. The important information is the type of elements in the collection in combination with additional information, that the reference (the data eld)

is not only one instance, but it stays for a group of elements of the recognized type.

Event Some modern object oriented languages dene language level implementation of design pattern Observer. In .Net, the denition of events is similar to common class property -it has its type (delegate) and name. The dierence is that during the compilation two new methods on the class containing the event are dened.

These are used to attach and detach listeners (observers).

From the design pattern mining point of view we can say, that the events are single-purpose. The denition of an event and references to it exactly dene the Observer pattern instance that is implemented correctly. It is clear that when looking for this kind of pattern implementation, we can mark each occurance of the key-word. Thus, we store this information in the system model, but do not discuss this in the paper bellow.

Semidynamic analysis

Application behavior is represented by methods, invocations between them and object creations. Some information can be gathered already from static representation of an analyzed system -the most important information is the call from one operation to another one.

The necessity of the information about the calls was introduced in many recent works [START_REF] Balanyi | Mining Design Patterns from C++ Source Code[END_REF] [3] [START_REF] Shi | Reverse Engineering of Design Patterns from Java Source Code[END_REF] concerning the design patterns mining. However, just a few of them inspected the whole body of operations in more detail. We nd the placement of a method call (whether inside a condition, cycle or directly in a method) equally important as the basic recognition of the call. Most of the design patterns dene the condition, that the particular call should be invoked just when an if-clause is evaluated as true (e.g. Singleton, Proxy) or it needs to be realized inside a cycle (e.g. Composite). It, however, should not forbid it -the inclusion inside a condition can be done due to many other reasons not aecting the design pattern instance. For some design patterns is also important the count of calls to a single operation placed inside the current operation (e.g.

Adapter ).

During the semidynamic analysis there we also analyze the class attributes.

The access to a member variable from an operation brings some very useful information enhancing the image we can gain about the behavior from the statically written system. If a method plays the role of operation GetInstance in pattern Singleton, it is insucient to have just the structural information, it needs to have a reference to the static eld instance and modify it during the lazy initialization.

The Fig. 1 presents the example results of the static and semidynamic analysis.

Dynamic analysis

The only time, we can really observe the behavior of a system, is the run time.

When we execute the analyzed system we can see, what is really happening Fig. 1. Graph of the system structure enhanced with semidynamic information inside the system. To do so, we decided to enrich the model (graph) with four simple information collected automatically.

Count of instances

Several design patterns say how many instances a particular class should have during one system execution. The simplest example should be the Singleton pattern -it is obvious that there needs to be exactly one instance of the class.

The suitability and the goal we want to achieve by counting instances of concrete types is obvious. We decided to increase the number also for class A when an instance of class B is created whereas B derives from A. The reason for doing this is the fact that patterns usually do not forbid to derive from classes playing the roles in pattern instance. Thus, there might be a class that derives from Singleton but the method GetInstace still has to return the same object -Singleton needs to have just one instance no matter how many subclasses of it are dened in the system.

Count of the operation invokes

In the previous section we have already introduced the importance of the information how many times an operation was invoked. The Prototype example illustrates the comparison of the count of operation Clone invokes to the count of instances of a particular type. More common however, is the comparison to count of invokes of calls done from a particular operation (useful when searching for e.g. Composite or Proxy). Thanks to this information it is easy to verify whether the placement of a call inside a loop really increases, resp. the placement inside a condition decreases, the count of call executions. Using this information we can check also whether e.g. Composite really does its job and groups more components forming a tree structure.

Less common is to compare count of invokes of two separate operations.

The reason is that mostly we do not know whether the target operation really gets executed -there might be lazy binding and the pattern denition would be useless. We could increase the count of invokes not only for the operation really called, but also for the overridden one. It might seem similar to the situation we have with the classes (previous chapter) but there are some dierences. First of all, it is sometimes useful to distinguish exactly the called operation and modifying the count of overridden method would make it a little bit harder. The most important dierence, however, is that we have another useful information when considering the operation invokes -we can identify the source and desired target by monitoring invokes of the calls from one operation to another.

Count of the calls invokes

The call from an operation is mostly polymorphic -its target is a virtual method that can but (in case it is not abstract) does not have to be overridden in a subclass. As described in previous section, this information can serve as verication of the real usage of a loop or a condition during the system run time. A good example is the Proxy pattern, where we can observe whether the condition really leads to lower calls to the RealSubject and is not just a result of coding standards or an accident.

Count of changes in attributes

Some patterns require tracking the value-changes in data variables. It might be interesting to monitor changes in all of them including local variables and method parameters, but we do not nd this really useful and it would lead to performance problems due to many logging. What we nd useful and sucient is to count, how many times a value in a class attribute changes.

The importance of tracking the changes can be seen in several design patterns -even when considering the very simple pattern Singleton we can propose a restriction that value stored in the static eld instance should change just once. More changes would cause the program to loose the reference to the only instance, thus the pattern instance would behave incorrect.

The most important, however, is the value to identify patterns Strategy and State. They have been discussed many times in literature so far [START_REF] Balanyi | Mining Design Patterns from C++ Source Code[END_REF]. When trying to recognize these patterns in a system automatically, most of the approaches presented earlier simply sets the instance as Strategy or State -since they were using just the static analysis they were unable to distinguish one from other. The approaches that took the challenge and proposed the ability to distinguish them used some additional information, restriction that do not t always and were added by them [3] [11]. Very common is the denition that a concrete state needs to know about its successor (one concrete state has reference to another concrete state) or the context simply creates the concrete states. This is usually true and is a very good assumption. We have identied dierent assumption that allows us to recognize these patterns: states should change, whereas strategies should not. This means that we need to know whether the attribute in Context class (its reference to abstract state or strategy) changes or not. We can say that the Strategy pattern says about algorithm a context can be congured with.

Strategy encapsulates behavior used by a system, its part or a single class and it should not change during the client (Context ) life time. Thus, the restriction we placed is, that there can not exist any class that contains a parameter of type Strategy (reference to abstract strategy) that changes too many times -the highest possible count of changes in the eld referencing from the Context to the Strategy is the count of instances of the Context class. Having the Strategy clear, we know how to nd a State -when all the other requirements (structural, semidynamic, other dynamic restrictions) are met, there needs to be a Context class that has an attribute of type State that was changed (the value stored in the variable was changed) more times than the Context class was instantiated.

Design pattern model and the search

We have introduced several constraints that can be used to exact recognition of design pattern instances. Because of these new constraints, we had to develop a new pattern description that includes improved structural and behavioral information. As we mentioned earlier, the analyzed system is represented as a graph with four kinds of vertices: type, operation, data and call. Each type of vertex has its own attributes (as they are described in chapters 3.1, 3.2 and 3.3) and can be connected with the other vertices using typed edges. The pattern is a rule that describes constraints on a subgraph of this graph -its vertices including values of the attributes, types and edges.

Patterns usually dene roles that might (or should be) played by more system elements -e.g. they dene a concrete strategy, but expect that there will be more of them in a single instance of the pattern. It means that the multiplicity of items playing role concrete strategy should be at least 2. The multiplicity is crucial for all patterns (dening the minimal and maximal value of it for each pattern element) -it is clear that there should not be a public constructor available in the class Singleton, thus its multiplicity needs to be exactly 0. There needs to be at least one private constructor, so multiplicity of this element has the minimum at 1. The multiplicity is even more interesting when we look for an Abstract Factory instances -when we take the denition of pattern very precisely, we can propose a constraint on count of abstract products demanding it to be the same as the count of methods of the factory that create objects of dierent types. The minimal and maximal value is used also for all the information gathered using the dynamic analysis and can be set as constant number or as a reference to another numeric value evaluated on the pattern instance.

The Tool

To prove our concept we have developed a complex reverse engineering tool that is able to analyze any system built on the .Net platform and search the instances of design patterns dened in an editable catalogue (see Fig. 2 for the screenshot of the tool). The analysis process starts with selection of assemblies (DLL and EXE les) and specifying namespaces that should be included. The content of the assemblies is written in Common Intermediate Language, that is produced by every compiler of all the languages of the .Net family. CIL can be read in various ways. The simplest one is the usage of the reection that is commonly available in the .Net environment and is sucient for the needs of structural analysis. The content of the operations that is investigated by the rest of the analysis process is available as plain CIL. We nd here all the references to attributes (data elds), method calls and recognize whether they are positioned inside a condition, loop or directly in the method body. Finally, the dynamic analysis is done using .Net proling API that allows us to inject logging instructions into every operation of the analyzed system. This is done before Just-In-Time compilation (from CIL to machine code) of each method starts.

Before we could search for something, we needed to dene it. Therefore we have created an editable catalogue of design patterns stored in an XML-based language that we have created from original Design Pattern Markup Language (DPML) [START_REF] Balanyi | Mining Design Patterns from C++ Source Code[END_REF] enhancing it by the features we added (we call it DPMLd ). The search for design patterns instances itself is based on graph theory and utilizes GrGen.Net [START_REF] Geiss | [END_REF]. GrGen.Net allows a developer to dene his own model of graph that contains typed vertices, each type of vertex having its own attributes and connected with other vertices using typed edges. Upon the dened graph, there can be a graph-rewrite-rule created. The rule consists of conditional and changing part and can be used to specify conditions on subgraphs we want to search for.

The tool we created transforms the graph of analyzed system into the GrGen.Net form and produces the graph-rewrite-rules from specication of design patterns.

Finally, it collects the found subgraphs -basic fragments of candidates of design pattern instance (e.g. group of vertices that represent an instance of State with only one concrete state). These fragments are grouped together if they have common group-dening elements -this is for example the abstract state class, or the template method. Which elements are the group-dening is dened by the pattern and it can be any type, operation or data. The last step of the search is done when subgraphs are grouped into the candidates. It consists of multiplicity checks verifying the correct count of elements in the pattern instance.

Results

The Fig. 3 illustrates the benets of the individual steps of the analysis we proposed in this article. It contains wrong and good implementations of the simplest of the GoF design patterns -the Singleton. considering the Singleton, it checks whether there is no public constructor and at least one private one in a class that contains static attribute of its own type and a static method returning the type. However, all these conditions are met already in the case of class NearlySingleton1 (part A in the gure). Even more, the method GetInstance has reference to the instance data eld and calls the private constructor. The semidynamic analysis checks all this and adds another feature -it requires the call to be placed inside a condition (if-clause). It might seem enough, but as we can see the NearlySingleton2 (part B in the gure) ts also these constraints and still is not a correct instance of the singleton pattern.

Finally, the dynamic analysis adds some something that ensures the correctness -it checks the count of instances of the class (to be more exact it checks also the count of value changes in the instance eld and count of method and call invokes) and veries that the Singleton1 and Singleton2 are the valid Singleton pattern instances in the system. Please note, that the call to the private constructor in the Singleton2 is not placed in a condition as it is written in the code. However, we can say there is a hidden (suppressed) else block because the precious if-block ends with the return statement (the tool recognizes this correctly).

We have lled the catalogue of the implemented tool with all GoF design patterns having one group of implementation variants for each pattern. This means that all common implementation variants are found, but some correct pattern instances that rely on transitive relations might stay undiscovered. The resolution to this is by adjusting the level of accuracy of the pattern denition or by adding the denitions of the additional variants (all using the GUI of the tool; automatic transitive relations are to be added during future work). The Observer and Iterator patterns are also included. We, however, decided not to search for Fig. 3. Experiments with singleton pattern the language-level implementation of them -this would be just the keyword based search for event or foreach. We dened these two as they are described in the GoF catalogue and search just in the client code. As expected, none of the projects we tested was reinventing the wheel (they used the language level features instead of coding it at their own). Thus, we do not show these results in the tables bellow.

We have checked our tool on the code of our tool itself (PatternFinder ). We chose our own tool for examination because it is an untrivial piece of code and we know about occurrence of all instances in it. The tool was able to nd all the pattern instances correctly (except Mediator -it did not nd it since it has colleagues made from system types that were skipped during the analysis process).

It was also able to nd some pattern instances we included unintentionally.

The other tests were made on both -the free (mostly open source) and the commercial projects on the .Net platform (since we do not need sources, we need just the DLL and EXE). The Table 1 presents results of the examination executed on the dierent projects. Please note that we looked just for a single variant of each design pattern (resp. small group of variants covered using single pattern description in the DPMLd pattern language we proposed). The variants can be modied or some new one can be added to the tool using the editor it contains or by writing it as the XML.

The table columns marked with S are based on static (structural and semidynamic) analysis and the D columns contain results that came from complete static and dynamic analysis Each table cell contains three numbers formatted like x / y / z, where:

x -count of all subgraphs (smallest fragments that meet the basic requirements).

y -count of all candidates that arrised from grouping of the subgraphs.

z -count of the found pattern instances.

6 Conclusions and Future work

In the previous sections we have introduced a method for searching instances of design patterns in an intermediate code and a tool that is a proof-of-concept.

We have focused on preciseness of search results, therefore we have proposed a method based on three dierent types of analysis. All of them need to agree before they mark the pattern instance, so they together provide interesting results with low false acceptance ratio.

The implemented tool provides identication of pattern instances in the intermediate language of the .Net platform. Choosing intermediate language as an input to the analysis removes the necessity of access to the source code. As a result we are able to check any software developed for the .Net platform, including COTS products provided by third parties. The search process is driven by a pattern specication which is written in an XML-based language. The tool provides a GUI editor for the language, what allows users to modify pattern descriptions or specify other patterns. Through modication of a pattern description a user can even congure the level of search preciseness.

In the future, we would like to improve our specication language to allow searching more variants of design patterns. An interesting approach in this area has been introduced by Nagl [START_REF] Nágl | Catalog of software knowledge with variability modeling[END_REF]. He uses feature modeling [START_REF] Czarnecki | Staged Conguration Through Specialization and Multi-Level Conguration of Feature Models[END_REF] for specication of design pattern variability. Another improvement can be gained by allowing the transitive relationships which are sometimes parts of the software design (for example indirect inheritance, multiple code delegation, etc.).

Fig. 2 .

 2 Fig. 2. The results dialog window of the tool

Acknowledgement. This work was partially supported by the project of APVV (Slovak Research and Development Agency), No. APVV-0391-06 Semantic Composition of Web and Grid Services and the Scientic Grant Agency of Republic of Slovakia, grant No. VG1/3102/06.

Table 1.

Experiments on existing projects