Problem: Performance discrepancy when filtering by getCompilationUnit vs. getSignature in a query

[oriana19993926782]

Hello,

I wrote a query to:

1. find all the focal methods (It means a method called inside an assert statement, such as assertEqual) in apache/shardingsphere-elasticjob.
2. then find all the callees by navigating the call graph for each focal method.
3. finally order the callees in a BFS (breadth-first search) order for each focal method.

My query works perfectly if you specify the signatures of the focal methods you're targeting at by adding something like and focalMethod.getSignature() = "getShardingContexts()" in the where section. (This focal method is the most complex one in my project, it has 700+ callees).

However when you don't specify the focal method, and you run my query directly, it will be like going into an infinite loop, running forever without any query result returned.

Then I thought, maybe it is because apache/shardingsphere-elasticjob is too complex for this task.(Actually it is not quite complex, the whole project has only 3500+ callees)

So I tried scoping my query to a specific class/compilationUnit. That's when the problem I mentioned in the title came up.

I chose a very simple class named DataSourceConfiguration, it only contains one focal method equals(java.lang.Object.
Even when narrowing the scope of my query to this "DataSourceConfiguration" class by adding and focalMethod.getCompilationUnit().toString() = "DataSourceConfiguration", the query execution does not show any improvement in runtime than before, still runs forever with no result. However, when narrowing the scope to the only focal method equals(java.lang.Object that this class has by adding and focalMethod.getSignature() = "equals(java.lang.Object)", the query runs smoothly without delay.

This is very odd, since "DataSourceConfiguration" only has one focal method "equals(java.lang.Object)". There should not be any performance discrepancy between adding and focalMethod.getSignature() = "equals(java.lang.Object)" and adding and focalMethod.getSignature() = "equals(java.lang.Object)". The same odd discrepancy is observed across other packages and their focal methods in my project(for example, class "LiteJobFacade" and its 4 focal methods, which I included and commented out in my query).

To sum up, limiting the scope from all classes of the whole project to only one class did not give us any improvement on running-forever problem. And using getCompilationUnit vs. getSignature to specify the same one method gives us performance discrepancy.

Note that this performance discrepancy and running-forever problem disappeared when I commented out all the parts related to getCallDepth(Callable start, Callable target) in my query. This getCallDepth is used to calculate the depth of callee and its direct caller, so that I can order all the callees in a BFS way.

My query is down below. Any insights or assistance on this matter would be greatly appreciated. Thank you!!!

import java

class TestMethod extends Method {
  TestMethod() {
    this.getAnAnnotation().toString().matches("Test")
  }
}

class AssertMethodCall extends MethodAccess { 
  AssertMethodCall() {
    this.getMethod().getDeclaringType().getQualifiedName().matches("%Assert%") and
    this.getEnclosingCallable() instanceof TestMethod
  }
}

predicate hasMethodCall(Expr expr) {
  expr instanceof MethodAccess
  or
  exists(Expr child |
    child = expr.getAChildExpr() and
    hasMethodCall(child))
}

int getCallDepth(Callable start, Callable target) {
  if (start = target)
    then result = 0
  else
    exists(Callable intermediate |
      start.polyCalls(intermediate) and
      result = 1 + getCallDepth(intermediate, target)
    )
}

from AssertMethodCall assertMethodCall, Callable focalMethod, Callable callee, Callable directCaller
, int depth_directCaller, int depth_callee, Call c, Interface interface
where 
  exists(MethodAccess methodCall |
    hasMethodCall(assertMethodCall.getAnArgument()) and
    methodCall = assertMethodCall.getAnArgument().getAChildExpr*().(MethodAccess) and
    focalMethod = methodCall.getMethod() 
    // and focalMethod.getSignature() = "getShardingContexts()" 

    // and focalMethod.getCompilationUnit().toString() = "DataSourceConfiguration"
    // and focalMethod.getSignature() = "equals(java.lang.Object)"



    // and focalMethod.getCompilationUnit().toString() = "LiteJobFacade"
    // and
    // (focalMethod.getSignature() = "getShardingContexts()" or
    // focalMethod.getSignature() = "isNeedSharding()"  or
    // focalMethod.getSignature() = "misfireIfRunning(java.util.Collection)" or
    // focalMethod.getSignature() = "loadJobConfiguration(boolean)")


    and focalMethod.polyCalls+(callee) 
    and callee.fromSource()
    and depth_callee = getCallDepth(focalMethod, callee)

    // Find the direct caller of 'callee' in the call graph
    and ((directCaller.polyCalls(callee) and focalMethod.polyCalls+(directCaller))
    or (focalMethod = directCaller and depth_callee = 1)
    )
    and depth_directCaller = getCallDepth(focalMethod, directCaller)
    and depth_callee = depth_directCaller + 1
    
    and c.getCaller() = directCaller
    and 
    ( //if c.Callee() here is an interface method, and check if it is implemented by callee
    (c.getCallee().getDeclaringType() = interface
    and callee.getDeclaringType().getASupertype*() = interface
    and c.getCallee().getSignature() = callee.getSignature()
    ) 
    // this is the case when c.Callee() is callee, not an interface
    or 
    c.getCallee() = callee
    )
)

select 
  focalMethod.getSignature() as fm_Signature,
  focalMethod.getCompilationUnit().getRelativePath() as fm_CompilationUnit,
  focalMethod.getBody(),
  directCaller.getSignature(),
  directCaller.getBody(),
  depth_directCaller,
  callee.getBody(),
  callee.getSignature(),
  depth_callee,
  c.getLocation().getStartLine() as where_callee_called_inside_its_directCaller

order by   
// order the callees in a Breadth-first search way
  fm_Signature, 
  fm_CompilationUnit, 
  depth_callee,
  where_callee_called_inside_its_directCaller asc

[smowton]

Your fundamental problem is that cycles in the call graph (due to real recursion, or apparent recursion via virtual dispatch that can't really happen in practice) mean that getCallDepth taken in isolation could calculate a potentially infinite number of answers for a particular (start, target) pair. In the simple example where f calls g and itself, then (f, g) has distance 1, 2, 3, 4, ...

There are two options here depending on whether you care about such loops: take the shortest distance, or limit the distance to some fixed maximum value using a simple result < 100 sort of side condition.

For shortest distance calculations there is a higher-order predicate shortestDistance that takes a unary predicate identifying roots and a binary predicate identifying graph edges and finds all shortest paths. Here is an example rewritten to use that:

import java

class TestMethod extends Method {
  TestMethod() { this.getAnAnnotation().toString().matches("Test") }
}

class AssertMethodCall extends MethodAccess {
  AssertMethodCall() {
    this.getMethod().getDeclaringType().getQualifiedName().matches("%Assert%") and
    this.getEnclosingCallable() instanceof TestMethod
  }
}

predicate hasMethodCall(Expr expr) {
  expr instanceof MethodAccess
  or
  exists(Expr child |
    child = expr.getAChildExpr() and
    hasMethodCall(child)
  )
}

predicate isFocalMethod(Callable method) {
  exists(AssertMethodCall assertMethodCall |
    method = assertMethodCall.getAnArgument().getAChildExpr*().(MethodAccess).getMethod()
  )
}

predicate polyCallsAsPredicate(Callable fromNode, Callable toNode) { fromNode.polyCalls(toNode) }

int getCallDepth(Callable start, Callable target) =
  shortestDistances(isFocalMethod/1, polyCallsAsPredicate/2)(start, target, result)

from
  Callable focalMethod, Callable callee, Callable directCaller, int depth_callee, Call c,
  Interface interface
where
  isFocalMethod(focalMethod) and
  focalMethod.polyCalls+(callee) and
  callee.fromSource() and
  depth_callee = getCallDepth(focalMethod, callee) and
  // Find the direct caller of 'callee' in the call graph
  (
    directCaller.polyCalls(callee) and focalMethod.polyCalls+(directCaller)
    or
    focalMethod = directCaller and depth_callee = 1
  ) and
  c.getCaller() = directCaller and
  (
    //if c.Callee() here is an interface method, and check if it is implemented by callee
    c.getCallee().getDeclaringType() = interface and
    callee.getDeclaringType().getASupertype*() = interface and
    c.getCallee().getSignature() = callee.getSignature()
    or
    // this is the case when c.Callee() is callee, not an interface
    c.getCallee() = callee
  )
select focalMethod.getSignature() as fm_Signature,
  focalMethod.getCompilationUnit().getRelativePath() as fm_CompilationUnit, focalMethod.getBody(),
  directCaller.getSignature(), directCaller.getBody(), callee.getBody(), callee.getSignature(),
  depth_callee, c.getLocation().getStartLine() as where_callee_called_inside_its_directCaller
  order by
    // order the callees in a Breadth-first search way
    fm_Signature, fm_CompilationUnit, depth_callee, where_callee_called_inside_its_directCaller

Note I have excluded the other usage of getCallDepth so that I could restrict that predicate to only compute paths starting from focal methods; I think the directCaller.polyCalls(target) and indirectCaller.polyCalls*(directCaller) stuff achieved the same result.

So, why were your side conditions sometimes causing your original query to work anyhow? By default a predicate is evaluated for all possible values of its arguments and results; in the case of getCallDepth this is a very expensive (not quite infinite, because int will eventually saturate) computation. Predicates can be limited either explicitly by the user inserting side-conditions, or implicitly by the compiler choosing to infer side-conditions from the predicate's usage -- the latter being an optimisation technique called magic. By varying the side-conditions accompanying the use-sites of getCallDepth, you were very likely nudging the compiler to either choose to optimise that predicate, or leave it alone and try to evaluate it for all possible methods.

Ancillary notes on the QL above:

• The interface signature matching at //if c.Callee() here is an interface method can be replaced by viableCallable
• hasMethodCall(assertMethodCall.getAnArgument()) and methodCall = assertMethodCall.getAnArgument()... is redundant, since methodCall can be given a value if and only if hasMethodCall holds -- therefore the hasMethodCall condition could be dropped (and has been in my rewritten example above)
• If you're looking for focalMethod -n-> directCaller -1-> callee, it is probably better to measure the depth to directCaller and then just take one more polyCalls (or if you care about the specific call, getCaller ... or ... viableCallable) step than to measure depth to callee and then back up one step.

[oriana19993926782]

Thank you very much!! I think the fundamental problem has been solved and I've understood that some method might have some inner loop that might cause getCallDepth to get infinite possible depths. However, there is one problem I still could not understand, which is the fact that I used 2 different ways to scope the query to the same one focal method but got performance discrepancy, the 1st way is to add and focalMethod.getCompilationUnit().toString() = "DataSourceConfiguration", the 2rd way is to add and focalMethod.getSignature() = "equals(java.lang.Object)". The former way ends up with running-forever problem, but the latter way works fine.(Those 2 way point to the same focal method cause this class/compilationUnit only has one focal method). It feels like a bug to me, but I guess it is probably not.

I also want to consult you with 2 questions. I'll appreciate it a lot if you can help with them. Question 1: My previous query and the query you provided will leave the focal methods with no callee out in the query result, is there any way I can have both the focal methods with no callee and the focal methods with callees in the query result simultaneously? Or do I have to write another query for focal methods without any callee? Question 2: I've noticed that some callee method body(callee.getBody()) only consists of some Lombok annotation, like “@RequiredArgsConstructor”、“@AllArgsConstructor” 、“ @Builder”、 “@Setter” and so on, I was wondering is there any effective way to leave them out in the query result? I have made some trials, but I have not found an effective solution

[smowton]

Why did one formulation result in optimisation and not the other? It's very unlikely to be a bug per se -- the optimiser, like all programming language optimisers, tries its best and it's sometimes possible to knock it into good or bad behaviour by changes you'd expect to be semantically no-ops. In extremis there are pragma statements to direct it more carefully, but here just explicitly limiting the predicate to apply to the right inputs is the best approach.

Q1. I don't think there can be a focal method with no callee, because the definition of a focal method involved a MethodAccess that calls it. However in theory there are a few different approaches you can take, depending on what you want to do with it:

The simple string-based approach:

s = "The callee is " + getCallee(...)
or
not exists(getCallee(...)) and s = "No callee"

The more principled optional approach:

newtype TOptCallable = TSomeCallable(Callable c) or TNoCallable()

class OptCallable extends TOptCallable {
  string toString() { this = TNoCallable() and result = "No callable" or exists(Callable c | this = TSomeCallable(c) and result = "Some callable: " + c.toString()) }
}

Q2. The annotation as a body is surprising. Got an example DB?

[oriana19993926782]

Here is an example for Q2:

Add the following code in the where section, and run, you will see the Lombok annotation@AllArgsConstructor as a callee method body. (If you comment out and not callee.hasName("<obinit>", you'll see the other callee method body, which is public final class TaskResultStatistics {. But if I try using this and not callee.hasName("<obinit>" to filter out all the callees like above, the query running will stall)

 and focalMethod.getSignature() = "findTaskResultStatistics(java.util.Date,org.apache.shardingsphere.elasticjob.cloud.statistics.StatisticInterval)"
 and not callee.hasName("<obinit>")

For Q1:
I saw you said "I don't think there can be a focal method with no callee, because the definition of a focal method involved a MethodAccess that calls it.", sorry, it seems that I did not make myself clear before. So, I'm giving you an example here too. By focalMethods without any callee inside, I mean, focalMethods such as the following doMath method. This doMath method could be called in, say assertEquals(-5, doMath(-4, 9)), but this doMath does not further call any callee inside its body, to put it in another way, it does not have any dependent/children method, thus it does not have any directCaller and callee. So, running my query or your query will leave out focalMethods like this doMath, which I want to keep in the query result simultaneously. I was wondering is there an effective solution?

public static int doMath(int a, int b){
    int c = a+b;
    a++;
    b = a+c;
    return (b+a)*c;
}

[smowton]

Re: Q2 neither your original nor my altered query seem to return anything relating to AllArgsConstructor when using the database downloaded from project apache/shardingsphere-elasticjob. I'm afraid you'd have to give more precise instructions to reproduce.

Re: Q1, it depends what you want the results to be when the assertion directly uses a leaf method like this. Would it be enough to say polyCalls* (i.e., allowing zero calls) instead of polyCalls+, so that the focal method itself is included as a 'callee' of the focal method? In that case the direct callee could be figured differently (focalMethod itself as a special case? The method containing the assertion?)