Developing quality code is a major concern for the software community. Producing bug-free, extensible, and adaptable code is a hard task. It requires skills, experience, and a deep understanding of the structure and behavior of the software under development. Methods and tools exist to alleviate the coding task for developers. However, helping in the comprehension and modification of the application is still a major problem. This problem of comprehension and modification is even more acute for maintenance.

Maintenance represents 75 percent of the life cycle of an application and the comprehension of the software takes up to 80 percent of the maintainers' time [Woods et al., 1998]. Therefore, the correction, extension, and adaptation of legacy object-oriented software are left to experts with both forward engineering and reverse engineering skills that can efficiently picture large and complicated software.

Many studies address the problems of automating the detection and the correction of intra-class design defects [Fowler, 1999], [Jahnke et al., 1997] , [Wake, 2000a]. Intra-class design defects appear in the definition of the class itself (in the definition of its fields, of its methods). Intra-class design defects have been extensively studied and automated. A reason is the similarity of intra-class design defects with defects in procedural programming languages. Procedural programming languages exist for more than 50 years and have been subject to several studies.

Few studies aim at the automation of the detection and correction of inter-class design defects [Rich and Waters, 1988], [Wake, 2000b]. Inter-class design defects appear in the architecture of the application, their detection requires understanding the software architecture. Inter-class design defects are difficult to define independently of the application and its context (foreseen evolution, life span, cost, ...): A same architecture may be valid for an application and incorrect for another.

We make four hypotheses:

1. Design patterns published in [Gamma et al., 1994]embody quality architectural solutions, independent of the context or of the language;
2. Inter-class design defects and design patterns relate to one another;
3. The detection of groups of entities similar to a design pattern corresponds to the detection of a subset of design defects;
4. The modification of the groups of participants and their relationships, such that they comply precisely with the design pattern, improves the quality of the architecture.

We define a meta-model that handles uniformly design patterns instantiation and detection. (Instantiation refers to the transformation of existing code to comply with the specification of a design pattern or to the production of the code implementing a design pattern.) The meta-model embodies a set of entities and the interaction rules among them. All the entities needed to describe structure and behavior of design patterns introduced in [Gamma et al., 1994] are present.

We use the meta-model to define abstract models of design patterns. An abstract model describes the entities of a design pattern and their relationships. It is qualified as abstract because of its independence from any particular context. We use this abstract model to detect sets of entities matching the description of this design pattern in a given source code. Once the identification of sets of entities done, we transform the corresponding source code such that it complies with the design pattern abstract model.

We can generate the variables and the constraints associated with an abstract model of a design pattern. For each entity defined in the abstract model, we create a variable. For each relationship between two entities (or the lack thereof), we define a constraint between the two corresponding variables.

We use a constraints solver with automatic constraint relaxation to detect sets of entities similar to a design pattern [?]. We express the constraints in the Claire programming language [Caseau and Laburthe, 1996], used to implement the Propagate and Learn with Move (PaLM) constraints solver [Jussien and Barichard, 2000]. The PaLM solver is different from other constraint solvers (such as the Ilog constraint solver) because it provides contradiction explanation and automatic constraint relaxation.

This approach presents two main advantages:

1. The system automatically discovers distorted forms of a design pattern in source code from a precise definition of it. Thus, this approach differs from the use of logic programming where developers need to foresee and explicitly express all possible distortions.
2. Each solution of a distorted form is associated with the set of constraints relaxed to obtain it. Thus, it is possible to explain a solution according to the constraints relaxed. For example, if a constraint states class must be public, the distorted solutions -- found without this constraint -- reference this constraint as the reason why they are solutions.

This section illustrates our hypotheses using the Composite pattern example. The Composite pattern composes "objects into tree structures to represent part-whole hierarchies. Composite lets clients treat individual objects and compositions of object uniformly" ([Gamma et al., 1994], page 163). We use the implementation version where child management is defined in the Composite class, which is the most common use of this pattern (for instance, see classes Component and Container of the Java AWT package). The Composite pattern is a relatively simple structural design pattern and is often used as an example either for code production or for detection. Despite its simplicity, it includes all the common constituents of structural patterns: Classes and interfaces; methods and fields; and, inheritance, association, and delegation relationships. This section also illustrate our tool, Ptidej (Pattern Trace Identification, Detection, and Enhancement in Java).

The input source code in which we want to detect the Composite design pattern is a simple application of text document description. A Document contains elements (class Element), which can be Title, Paragraph or indented paragraph, IndentedParagraph. The Main class creates an instance of Document and fills it up with titles, paragraphs, and indented paragraphs. The relationships among the classes Element, Document, Title, Paragraph and IndentedParagraph are typical of a Composite pattern. However, class Document should be a subclass of Element because we want a uniform interface between the composition object and individual objects.

We apply the constraints defined for the Composite pattern on the source code corresponding to the application modelled using the meta-model. The following figure shows a graphical UML-like representation of the application, as displayed by our tool Ptidej. (A class is depicted as a box containing the class name. An association is represented as a plain arrow from the aggregate class to its component with a diamond at its base. A dotted arrow pictures an instance creation. A square line with an empty triangle corresponds to inheritance.)

The PaLM constraints solver generates the set of all the groups of entities similar to the abstract model of the Composite pattern. These groups are visible on the following figure as the gray boxes outlining the classes. The group of entities Element, Paragraph and Document is one example. The greater is the number of constraints relaxed, the less similar to the Composite pattern is the group solution and the lighter are the outlining boxes.

When a box is selected, the tool highlights all the entities belonging to this particular group and presents the related information: The degree of similarity of group with the original abstract model, the constituents of this group, their values and the associated transformation rules.

On the following example the group composed of classes Element, Document, IndentedParagraph, Paragraph, and Title is similar at 50% to the Composite pattern. The transformation to apply is given by the XCommand field:

Composite, Component | javaXL.XClass c1, javaXL.XClass c2| c1.setSuperclass(c2.getName());

That is, the class playing the role of Composite must be subclass of the class playing the role of Component: In the example, the class Document must be subclass of class Element. The transformation engine performs automatically the modifications on the application by executing the XCommand on the source code. Then, the result is loaded back into the tool. The following figure illustrates the resulting architecture of the application.

We hypothesize that design patterns represent good architectures and that pieces of code similar to design patterns represent potential places for improvements. We define a meta-model used to model design patterns and source code. We deduce detection rules and transformation rules from design pattern abstract models. The detection rules are defined as constraints on the source code, associated with transformation rules that modify the source code such that it complies with the constraints.

The use of explanation-based constraint programming appears as a straight and efficient way to solve the problem of the detection and correction of design defects. However, two issues limit the usability and effectiveness of our approach:

• First, the scalability of the results is limited. The detection of groups of entities similar to a design pattern in a medium- / large-size application produces too many solution groups. Most of the groups are uninteresting and constitute noise. We must find a way to limit the number of solution groups. We are currently investigating several possibilities, including the definition of k-NN CSP.
• Second, we must assess the limits of the automation and of the user-interaction to produce a tool that is really usable in an industrial environment.