add support for type inference

[monperrus]

Spoon relies on the declared static of variables and methods.

For some transformations, it would be very useful to have the actual type of a variable / expression.

For this, we could add a method getInferredType() in the metamodel.

[Egor18]

Do you mean that you want to add data-flow analysis for type inference? Consider the following example:

List list = new ArrayList();
if (condition)
{
    list = new LinkedList();
}
//getInferredType() - ?

How are you going to specify the type of list element here?

[monperrus]

Yes.

To my knowledge, nobody is working on this at the moment.

Are you interested in contributing on this?

[Egor18]

Implementing data-flow analysis is a big task. I think the best approach is to use some SMT solver as a backend for this.

Getting possible types statically is pretty much the same thing as getting possible values.

But even with an SMT solver, it could not be 100% accurate - we need to handle loops, virtual function calls and so on.

So I was curious how do you see data-flow analyzer in Spoon.

[monperrus]

What other tools do you know that do this for Java?

[Egor18]

I was quite curious, so I made a small data-flow analyzer with Spoon and Z3 SMT solver from Microsoft: https://github.com/Egor18/jdataflow (Check out the README.md for a more detailed explanation)

Here are just several examples of what it is able to detect right now:

void f(boolean c) {
    int x = 5;
    int y = c ? 3 : 2;
    if (x < y) {} // <= always false
}

void g(int x, int y) {
    if (2 * x + 3 * y == 12) {
        if (5 * x - 2 * y == 11) {
            if (x == 3) {} // <= always true
            if (y == 2) {} // <= always true
        }
    }
}

void h(Something x) {
    if (x == null) {
        x.f(); // <= null dereference
    }
}

void m() {
    C a = new C();
    a.x = 10;
    C b = a;
    b.x = 20;
    if (a.x == 20) {} // <= always true
}

At the moment it calculates values only, but it should be relatively easy to add types too.

[monperrus]

Hi Egor,

Cool to see progress here. Your README is remarkably clear, the test runner is clever and elegant, and the tests are quite comprehensive.

Overall, this is impressive.

Would you be interested in having this as a submodule in the Spoon main repo?

(we already have two other submodules control-flow and decompiler)

[Egor18]

I'm ok with putting it into the main repo, but you'd probably want some different API. Right now it is built in such a way that all the checks are performed inside the checkers (see AlwaysTrueFalseChecker and NullDereferenceChecker), and the checkers are applied while visiting the code with DataFlowScanner. Or do you want to merge it as is?

[monperrus]

I'm ok with putting it into the main repo

Excellent, that will be a super interesting module. Spoon modules are exactly meant for this: to be more experimental, more exploratory than spoon-core.

Do you plan to improve the API in the short term?

[Egor18]

In fact, it is not clear how the "better" API should look like. I mean, it works for me (i.e. for doing some static analysis with checkers).

[monperrus]

Then, let's import an initial version as a Spoon module. A module can be experimental, the API will evolve over time.

What would be a good name to your opinion? spoon-dataflow? spoon-symbolic?

[Egor18]

spoon-dataflow seems good

[monperrus]

perfect, it seems we're along the same line to make the pull-request!

[monperrus]

looking forward to your PR with spoon-dataflow!!

[Egor18]

I'm working on some minor improvements. Do you want it to be maven-based project or gradle is fine?

[monperrus]

great! gradle is fine, we can call gradle from Travis.