Call graph classes¶

The CodeQL library for Java/Kotlin provides two abstract classes for representing a program’s call graph:Callable andCall. The former is simply the common superclass ofMethod andConstructor, the latter is a common superclass ofMethodAccess,ClassInstanceExpression,ThisConstructorInvocationStmt andSuperConstructorInvocationStmt. Simply put, aCallable is something that can be invoked, and aCall is something that invokes aCallable.

For example, in the following program all callables and calls have been annotated with comments:

classSuper{intx;// callablepublicSuper(){this(23);// call}// callablepublicSuper(intx){this.x=x;}// callablepublicintgetX(){returnx;}}classSubextendsSuper{// callablepublicSub(intx){super(x+19);// call}// callablepublicintgetX(){returnx-19;}}classClient{// callablepublicstaticvoidmain(String[]args){Supers=newSub(42);// calls.getX();// call}}

ClassCall provides two call graph navigation predicates:

• getCallee returns theCallable that this call (statically) resolves to; note that for a call to an instance (that is, non-static) method, the actual method invoked at runtime may be some other method that overrides this method.

• getCaller returns theCallable of which this call is syntactically part.

For instance, in our examplegetCallee of the second call inClient.main would returnSuper.getX. At runtime, though, this call would actually invokeSub.getX.

ClassCallable defines a large number of member predicates; for our purposes, the two most important ones are:

• calls(Callabletarget) succeeds if this callable contains a call whose callee istarget.

• polyCalls(Callabletarget) succeeds if this callable may calltarget at runtime; this is the case if it contains a call whose callee is eithertarget or a method thattarget overrides.

In our example,Client.main calls the constructorSub(int) and the methodSuper.getX; additionally, itpolyCalls methodSub.getX.

Example: Finding unused methods¶

We can use theCallable class to write a query that finds methods that are not called by any other method:

importjavafromCallablecalleewherenotexists(Callablecaller|caller.polyCalls(callee))selectcallee

This simple query typically returns a large number of results.

Note

We have to usepolyCalls instead ofcalls here: we want to be reasonably sure thatcallee is not called, either directly or via overriding.

Running this query on a typical Java/Kotlin project results in lots of hits in the Java/Kotlin standard library. This makes sense, since no single client program uses every method of the standard library. More generally, we may want to exclude methods and constructors from compiled libraries. We can use the predicatefromSource to check whether a compilation unit is a source file, and refine our query:

importjavafromCallablecalleewherenotexists(Callablecaller|caller.polyCalls(callee))andcallee.getCompilationUnit().fromSource()selectcallee,"Not called."

This change reduces the number of results returned for most codebases.

We might also notice several unused methods with the somewhat strange name<clinit>: these are class initializers; while they are not explicitly called anywhere in the code, they are called implicitly whenever the surrounding class is loaded. Hence it makes sense to exclude them from our query. While we are at it, we can also exclude finalizers, which are similarly invoked implicitly:

importjavafromCallablecalleewherenotexists(Callablecaller|caller.polyCalls(callee))andcallee.getCompilationUnit().fromSource()andnotcallee.hasName("<clinit>")andnotcallee.hasName("finalize")selectcallee,"Not called."

This also reduces the number of results returned by most codebases.

We may also want to exclude public methods from our query, since they may be external API entry points:

importjavafromCallablecalleewherenotexists(Callablecaller|caller.polyCalls(callee))andcallee.getCompilationUnit().fromSource()andnotcallee.hasName("<clinit>")andnotcallee.hasName("finalize")andnotcallee.isPublic()selectcallee,"Not called."

This should have a more noticeable effect on the number of results returned.

A further special case is non-public default constructors: in the singleton pattern, for example, a class is provided with private empty default constructor to prevent it from being instantiated. Since the very purpose of such constructors is their not being called, they should not be flagged up:

importjavafromCallablecalleewherenotexists(Callablecaller|caller.polyCalls(callee))andcallee.getCompilationUnit().fromSource()andnotcallee.hasName("<clinit>")andnotcallee.hasName("finalize")andnotcallee.isPublic()andnotcallee.(Constructor).getNumberOfParameters()=0selectcallee,"Not called."

This change has a large effect on the results for some projects but little effect on the results for others. Use of this pattern varies widely between different projects.

Finally, on many Java projects there are methods that are invoked indirectly by reflection. So, while there are no calls invoking these methods, they are, in fact, used. It is in general very hard to identify such methods. A very common special case, however, is JUnit test methods, which are reflectively invoked by a test runner. The CodeQL library for Java has support for recognizing test classes of JUnit and other testing frameworks, which we can employ to filter out methods defined in such classes:

importjavafromCallablecalleewherenotexists(Callablecaller|caller.polyCalls(callee))andcallee.getCompilationUnit().fromSource()andnotcallee.hasName("<clinit>")andnotcallee.hasName("finalize")andnotcallee.isPublic()andnotcallee.(Constructor).getNumberOfParameters()=0andnotcallee.getDeclaringType()instanceofTestClassselectcallee,"Not called."

This should give a further reduction in the number of results returned.

Further reading¶

• CodeQL queries for Java

• Example queries for Java

• CodeQL library reference for Java

• “QL language reference”

• “CodeQL tools”