Comments (6)
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?
from heros.
@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.
from heros.
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.
from heros.
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?
from heros.
@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.
from heros.
No, apologies, the project I was working on ended and I am no longer using Heros
from heros.
Related Issues (20)
- InterruptException in CountLatch HOT 1
- Automatically return All-bottom edge function for seeds HOT 2
- How do I use it? HOT 2
- Incorrect source value for Phase II(i) value computation HOT 5
- Errors in heros like semicolon missing, return type of method is missing HOT 1
- I want to use heros implement inter-procedural analysis,but I didn't how to use it. HOT 2
- flowfunc/Transfer uses == instead of equals(..) HOT 2
- How to validate ICFG? HOT 3
- IDESolver never uses more than 1 thread HOT 2
- AllTop.meetWith(otherFunction) should return AllTop HOT 1
- Type mismatch error when running example code HOT 2
- Rename DefaultIDETabulationProblem.createJoinLattice
- How to use FieldSensitiveIFDSSolver? HOT 3
- How to run backwards IFDS? HOT 1
- Handle exceptional flows more precisely
- How to analyse a specific method ? HOT 3
- Inter-procedural Analysis on Shimple Bytecode HOT 1
- Virtual Invokes only triggers getCallToReturnFlowFunction HOT 4
- How to taint class instance HOT 1
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from heros.