The ideas behind the following query stem from a conversation with Frank Tip.
Our concern is to find badly modularised code, in the sense that lots of different packages depend on each other -- in Java, a package is a (reasonably) self-contained unit, and system architectures tend to layer one package on top of another; thus, having a big cyclical dependency can indicate that something isn't quite right with the package structure.
First of all, we need to specify what exactly we mean when we say a package
depends on another package.
Let us consider two reference types, T1 and T2. T2 depends on T1 if
- T2 inherits T1
- T2 has a field of type T1
- T2 has a method or constructor that
- has T1 as its return type (only for methods)
- has a parameter of type T1
- throws an exception of type T1
- T2 calls some method defined on T1
In other words, T2 depends on T1 if it uses T1 in some way. Let's express this as a .QL predicate:
predicate depends(RefType t, RefType dep) {
t.hasSupertype(dep)
or
t.getAField().getType() = dep
or
exists(RawMethod m | m.getDeclaringType() = t and
(m.getType() = dep or m.getAParamType() = dep))
or
t.getAConstructor().getAParamType() = dep
or
t.getACallable().getAnException().getType() = dep
or
t.getACallable().getACall().getDeclaringType() = dep
}
You may notice that I took special care in the above to check the return types and parameter types only for
raw methods. The reason is that otherwise, you get unexpectedly many dependency cycles: Many classes will depend on, say, java.util.List (using lists is quite common). But if that list is instantiated to some type as List<MyType>, then for example the list's get() method will return something of type MyType, and so java.util.List will suddenly depend on your code -- clearly not a very useful notion
Now, defining package dependence is easy: A package depends on another if it contains a type that depends on a type in the other package. Let's define a custom .QL class called DepPackage to encapsulate this concern:
class DepPackage extends Package {
DepPackage() { this.fromSource() }
predicate depends(Package p) {
this != p and depends(this.getARefType(), p.getARefType())
}
}
In the constructor (or, more precisely, the
characteristic predicate), we restrict our interest to packages that were populated from source. We then define a custom depends() predicate, exactly as explained above.
Next, we need to find cycles in the dependency graph of all packages. More precisely, we are interested in
strongly connected components (
SCCs) in that graph. An SCC corresponds to a set of mutually dependent packages.
Let's add some methods to the class DepPackage to deal with this:
class DepPackage extends Package {
DepPackage() { this.fromSource() }
predicate depends(Package p) {
this != p and depends(this.getARefType(), p.getARefType())
}
DepPackage getACycleMember() {
result.depends*(this) and this.depends*(result)
}
int getCycleSize() {
result = count(this.getACycleMember())
}
predicate isRepresentative() {
this.getName() = min(DepPackage p | p = this.getACycleMember() | p.getName())
}
}
Another DepPackage is a member of this package's dependency cycle if both
this transitively depends on that package, and that package transitively depends on
this.
I've also defined two auxiliary methods that will be useful in our query:
getCycleSize returns the number of packages that mutually depend on the current package, and
isRepresentative can be used to pick out the representative element of a SCC: This is just the package whose name is alphabetically first.
Now we can write the following query:
from DepPackage p
where p.getCycleSize() > 1 and p.isRepresentative()
select "SCC of size " + p.getCycleSize().toString() + " for " + p.getName() as s,
p.getACycleMember()
order by s desc
This will show us all mutual depdency cycles of size greater than 1, and enumerate all packages in each cycle.
Applying this query to the JHotDraw project from the tutorial reveals exactly two cycles. The smaller contains org.jhotdraw.app, org.jhotdraw.app.action, org.jhotdraw.gui and org.jhotdraw.gui.event -- and maybe the fact that these all depend on each other is part of the design of the system.
The second cycle contains 6 packages, showing some mutual dependencies between org.jhotdraw.draw and org.jhotdraw.samples, which is unexpected (to say the least).
