AllBottom.composeWith is broken

[langston-barrett]

It is currently implemented like this:
https://github.com/Sable/heros/blob/1a0a5be37bc321b0745c3e080e3e70543f5f04b4/src/heros/edgefunc/AllBottom.java#L28-L32

The if case is right, but the else case is wrong. The value should not be secondFunction, but a constant function that returns the the value secondFunction.computeTarget(bottomElement).

Unfortunately, this is not easy to fix: there is no generic way to construct a constant edge function since the user can supply their own lattice and edge functions. Something to this effect would have be added to the EdgeFunction interface or something.

[ericbodden]

Unfortunately I do not think your suggestion is valid. In IDE, edge functions are composed before they are evaluated. Composition happens in step 1 of the algorithm, evaluation in step 2. Hence it would be invalid to do as you propose: this would intertwine composition and evaluation.

I wonder: what gave you the idea that the current implementation could be incorrect?

[langston-barrett]

@ericbodden Apologies, my initial post was a bit misleading. Let me try to clarify. The defining identity of function composition is this: for appropriate f, g, and x

 (f o g)(x) = f(g(x)) 

(In words, the composition of f and g applied to x is the same as f applied to g applied to x). Insofar as the EdgeFunction class models functions, I would expect the following analogous identity to hold for any f, g, and x:

    f.composeWith(g).computeTarget(x) == g.computeTarget(f.computeTarget(x))

And indeed, if f is a constant function and

    AllBottom<T> allBot = new AllBottom(bot);

the following does hold:

    allBot.composeWith(f).computeTarget(x) == f.computeTarget(allBottom.computeTarget(x))

However, if f is not a constant function, you will get an incorrect result, as demonstrated by the following failing test case:

    @Test
    public void test_compose() {
        final Object top = new Object(); // top of the lattice
        final Object bot = new Object(); // bottom of the lattice
        final Object ele1 = new Object(); // some element in the lattice
        final Object ele2 = new Object(); // some other element in the lattice
        final AllTop<Object> allTop = new AllTop<Object>(top);
        final AllBottom<Object> allBot = new AllBottom<Object>(bot);
        final EdgeFunction<Object> func = new EdgeFunction<Object>(){

            @Override
            public EdgeFunction<Object> meetWith(EdgeFunction<Object> otherFunction) {
                return null;
            }

            @Override
            public boolean equalTo(EdgeFunction<Object> other) {
                return null;
            }

            @Override
            public Object computeTarget(Object source) {
                if (source == bot) {
                    return ele2;
                }
                return ele1;
            }

            @Override
            public EdgeFunction<Object> composeWith(EdgeFunction<Object> secondFunction) {
                return null;
            }
        };
        Assert.assertTrue("", allBot.composeWith(func).computeTarget(ele2).equals(func.computeTarget(allBot.computeTarget(ele2))));
    }

However, from your comments on #36, it sounds like you might not expect this to work. In this case, I think there should either be a comment at the top of AllBottom explaining that it should not be used externally to Heros, or it should be made into a private class.

[ericbodden]

Hi again. I have given this some more thought. The current implementation does make sense in the context in which it is used - the IFDS solver - but only there. However, I agree with you that it would make sense to make this class usable also in other contexts. In this case, your original suggestion makes a lot of sense, actually (generating a constant function). I will see whether this is possible without too large a change.

[ericbodden]

Hmm, as you already foresaw, I am struggling a bit. Please have a look here...
https://github.com/Sable/heros/blob/feature/ImprovedAllBottom/src/heros/edgefunc/AllBottom.java
... and here:
https://github.com/Sable/heros/blob/feature/ImprovedAllBottom/src/heros/edgefunc/ConstantFunction.java

The problem seems to be within ConstantFunction. It's unclear a priory how a constant function's meet should be computed without knowing the entire lattice. A more clear design, I guess, would be to externalize the meet operation into some other class/interface, but that would be a larger change. Do you have any better idea?

[ericbodden]

@langston-barrett do you have any more input on this? If not then I'd go the route of not actually opening up those classes after all, but rather documenting that they are for internal use only, and that one would need customized classes for a custom value domain.

[langston-barrett]

No, apologies, the project I was working on ended and I am no longer using Heros