SanD is a tool to detect design patterns in legacy Java code to support program understanding. To accomplish this task the tool generates static and dynamic analysis algorithms from design pattern specifications
To specify design patterns accordingly, we define two languages: a powerful, extensible, low-level language called SanD-Prolog (Static and Dynamic Prolog Specification) consisting of Prolog predicates that specify the static structure and dynamic behavior of design patterns and a high-level language SanD (Static and Dynamic Specification Language) that allows to specify design patterns intuitively. We implemented a simple compiler that transforms SanD specifications into SanD-Prolog specifications. The static analysis is performed on the Prolog database representing the source programs' attributed abstract syntax trees by a Prolog query derived from the SanD-Prolog specification. The result is a set of candidate tuples that are further classified by the dynamic analysis according to the patterns' behavioral specification. The behavioral specification consists of SanD-Prolog predicates representing states and state transitions of the program to analyze that are associated to certain real program states. The dynamic analysis then monitors the execution of the program to analyze and validates the behavioral specification by simulating the execution of a pattern instance on the specified states using the specified state transitions both associated to the executed program element. Violation of the constraints leads to rejection of the candidate instance. We use the degree of conformance of a candidate instance to classify it. Our analyses do not depend on coding or naming conventions. We demonstrate our approach and evaluate our tool by detecting instances of the Observer, Composite and Decorator patterns in Java code.
In order to faciliate the generation of analyses to detect design patterns or more generally interaction patterns, we decided to specify patterns using an executable specification in the form of Prolog programs. First, we specify a design pattern (instance) by static and dynamic constraints as Prolog predicates. The former restrict the code structure, the latter the runtime behavior. To perform the static analyis, we first represent the program to be analyzed by Prolog facts that encode its abstract syntax trees. Then, the static analysis applies the static constraints as a Prolog query to this representation. The static analysis is thus performed by a Prolog interpreter. The result of this step is a set of pattern instance candidates represented as tuples of program elements such as classes, methods or attributes. In practice this set is large and programmers hardly want to screen all of them to detect the actual instances. We therefore investigate these candidate tuples further by the dynamic analysis derived from the dynamic constraints of the pattern specification to reduce the amount of false positives: The dynamic analysis executes the program under investigation and checks the execution behavior (protocol) of the candidate instances with respect to the dynamic constraints. It classifies the candidate tuples proposed by the static analysis according to their conformance to the expected pattern behavior. The categories are full match (full protocol conformance), may match (a prefix of a correct protocol could be detected, the candidate does not violate the protocol though), mismatch (violation of the protocol) and no decision (candidate not executed). The following Figure illustrates our approach.
We discuss the particular steps of our approach using the Observer pattern as a running example. The following code sketches an implementation of the pattern.
public class ConcreteSubject {
private Container c = new Container();
private State s = new State();
public void addObserver(Listener l) {
c.add(l);
}
public void detachObserver(Listener l) {
c.remove(l);
}
public void notifyObservers() {
if (s.notChanged())
return;
for each l in c:
l.update(s);
}
}
interface ListenerInterface {
public void updateObserver(Object o);
}
public class ConcreteListener implements ListenerInterface {
public void updateObserver(Object o) {
doSomething(o);
}
}
An example of a corresponding candidate tuple provided by the static
analysis therefore is:
(ConcreteSubject.addObserver, ConcreteSubject.removeObserver,
ConcreteListener.notifyObservers, ConcreteListener.updateObserver)
Note, that we distinguish the role of a program element in a pattern
from the program element itself. Subject
and Listener}, e.g., are roles
of classes in
the Observer pattern. ConcreteSubject and
ConcreteListener can be two concrete classes in the two
roles. Similarly, a concrete method addObserver could
play the attach role in an
Observer pattern. The following naming conventions refer to roles of
certain methods of the Observer pattern:
This naming convention is only used for explanations in this paper, the static analysis does not refer to those names. i.e., role names are not concrete method names. In our example, we assume that the methods in the attach, detach or notify roles are contained in a single class and are not distributed among different hierarchies.
Moreover, we even distinguish an object instance from a design pattern
instance, if the latter contains class program elements. As an example
consider, that there may exist different object instances of
ConcreteSubject each with several object instances of
ConcreteListener, or,
e.g. AnotherConcreteListener attached to it.
Consider the following sketch of sample program to analyze for instances of the Observer pattern:
public class Main {
public static void main(String[] args) {
ConcreteSubject cs =
new ConcreteSubject();
Listener l1 = new
ConcreteListener();
Listener l2 = new
ConcreteListener();
cs.addObserver(l1);
cs.addObserver(l2);
cs.notifyObservers();
}
}
This program only contains one instance of the Observer pattern as well as only one object instance consisting of one subject object and two listener objects conforming to the full Observer protocol. The dynamic analysis thus classifies this tuple as full 1:n match.
Last update: 01.10.2003