Static call analysis: overwriting and implementing calls about java-callgraph HOT 9 OPEN

These are different kinds of relationships, though. They are not call relationships, and thus should not be mixed with them.

from java-callgraph.

from java-callgraph.

I think I see what you mean, and I could understand the need. But it seems to me that such addition would have a significant impact on the tool.

I just proposed a pull request for a better identification of lambdas in #22 (and I am glad it was accepted), but what I did was fix to better identify a one-to-one relationships between the lambda and the method instantiating it.

In your case it is not a one-to-one relationships. If you take the first point, with overriding. Here is an example:

class Root {
  void doSomething() {
    System.out.println("I am root!");
  }
}
class Child1 extends Root {
  @Override
  void doSomething() {
    System.out.println("I am child1!");
  }
}
class Child2 extends Root {
  @Override
  void doSomething() {
    System.out.println("I am child2!");
  }
}

Now you have a method accepting a Root:

void execute(Root root) {
  root.doSomething();
}

The point is that the call graph here would depend on the agument's value:

execute(new Root());
execute(new Child1());
execute(new Child2());

All three are valid calls, but then each of them calls the doSomething() of a different class. You would need to look for all the calls to execute(...) in the JAR, look which type of instance is passed in argument, and consequently add the call in the list. Basically, it would mean that the analysis should say that the method execute() calls all 3.

The second point, with interface implementation, is exactly the same, excepted that Root has no implementation. So you won't have the code details of Root.doSomething() since it does not exist, but the result in terms of execute() calls would be the same.

The problem here is that you cannot do it in a single pass without consuming huge amounts of space (RAM or hard disk, depending on the strategy used). Indeed, execute may be called anywhere in the JAR, and thus you won't know all the calls before you have looked everywhere.

If you do it in 2 passes, then during the first pass you need to store the types of the various instances passed to execute(). You need only one per type, so if you have few override/implement then it is only few, but you need to store them recursively, since the value given to execute() might come from its own caller, which may have received it from its own caller, and so on recursively. You need to store all the types for each level during the first pass (space complexity O(NxM)), and then exploit this information during the second pass to add all the calls relationships. If you it happens to be done to an object that pass more or less everywhere (e.g. a context state), then you may fill your RAM with a huge amount of data.

If you do it in 1 pass, you need to remember instead which methods might be impacted by such behaviours. But since you cannot guess in advance all the override/implement relationships, then you must assume it may happen for any (non-final) type. Which means you need to remember more or less every method you have seen, or said another way store a complete graph of the calls in the JAR. Which means that you need to store at least the same amount of information that you generate in output, which is really costly for huge JARs. More other, you need then to browse this graph when you discover an override/implement relationships, in order to know where to add it. This is one again really costly, but this time in terms of computation time. You would need to use even more space to optimize it.

Briefly, with 1 pass you obtain a tool which consumes more than it generates at the end, and with 2 passes you still need to consume way more than what you currently do. So it might be useful, but the impact would be huge.

Maybe it would make sense in the dynamic analysis (which I am not familiar with and I did not use), but in static analysis it seems to me like a tool killer.

Just too finish on a good note : if it is about adding the override/implement relationships between methods, then it might be OK, because you only need to list them once for all. Then all the calls relationships can be inferred from what is generated in output. So the information would be there. But retrieving the calls themselves... I would not recommend it for this tool. Just make a script/additional tool which builds on the result of the JAR analysis for that.

from java-callgraph.

java-callgraph was supposed to be a quick-and-dirty call graph generator. Resolving virtual dispatch calls (which is what we are discussing here) is not a trivial problem and other, more advanced tools (such as Soot and Wala) feature multiple implementations of algorithms proposed in scientific literature. I am not sure that we should implement those in java-callgraph.

from java-callgraph.

from java-callgraph.

Thanks for the comment. I don't disagree with the algorithm you propose, what I am saying is that tools such as Wala and Soot already offer this functionality (actually, more advanced versions of it). It would take me a lot of time (which I don't have currently) to implement this and get it right, so I will probably pass. However, I am open to PRs!

from java-callgraph.

If it is only about adding the overriding/implementing relationships then it should be doable in one pass with few impacts. This is a similar analysis than I did for the lambdas, so you may look and inspire from the class DynamicCallManager that I wrote for them (and the Cucumber feature tests to ensure it works). Actually, you may add your methods in the same class, since its purpose is to deal with such dynamic analysis.

I would gladly review your pull request if you make one.

from java-callgraph.

from java-callgraph.

Hi Peter, yes I am interested to see a PR that implements the functionality you are discussing here. Please also make sure you update the README file with the new output formats.

from java-callgraph.