[Soot-list] PointsToSet and equals/hashcode

[Eric Bodden]

Hmmm... it just came to my mind that was not 100% appropriate since it did not take calls to equals(..) into account which come from the JDK. So I wrote another aspect monitoring whenever we put PointsToSet into a Map or Collection and that gave the following two traces:

class soot.jimple.paddle.DoublePointsToSet

used at:
	at soot.jimple.paddle.PropWorklist.fieldUpdate(PropWorklist.java:128)
	at soot.jimple.paddle.AbsPropagator$1.update(AbsPropagator.java:56)
	at soot.jimple.paddle.DependencyManager.update(DependencyManager.java:76)
	at soot.jimple.paddle.OFCGScene.solve(OFCGScene.java:168)
	at soot.jimple.paddle.OFCGConfig.solve(OFCGConfig.java:35)
	at soot.jimple.paddle.PaddleScene.solve(PaddleScene.java:1386)
	at soot.jimple.paddle.PaddleTransformer.solve(PaddleTransformer.java:99)
	at soot.jimple.paddle.PaddleTransformer.internalTransform(PaddleTransformer.java:46)
	at soot.SceneTransformer.transform(SceneTransformer.java:39)
	at soot.jimple.paddle.PaddleHook.internalTransform(PaddleHook.java:43)
	at soot.SceneTransformer.transform(SceneTransformer.java:39)
	at soot.Transform.apply(Transform.java:89)
	at soot.RadioScenePack.internalApply(RadioScenePack.java:60)
	at soot.jimple.toolkits.callgraph.CallGraphPack.internalApply(CallGraphPack.java:40)
	at soot.Pack.apply(Pack.java:110)
	at abc.tm.weaving.weaver.tmanalysis.TracematchAnalysis.buildAbstractedCallGraph(TracematchAnalysis.java:259)
	at abc.tm.weaving.weaver.tmanalysis.TracematchAnalysis.analyze(TracematchAnalysis.java:146)
	at abc.weaving.weaver.ReweavingPass$Worker.run(ReweavingPass.java:148)
	at java.lang.Thread.run(Thread.java:595)

class soot.jimple.paddle.DoublePointsToSet

used at:
	at soot.jimple.toolkits.pointer.MemoryEfficientRasUnion.addAll(MemoryEfficientRasUnion.java:56)
	at abc.tm.weaving.weaver.tmanalysis.VariableSMEdgeFactory$SMVariableEdge.importVariableMapping(VariableSMEdgeFactory.java:139)
	at abc.tm.weaving.weaver.tmanalysis.UGStateMachine.addVariableMappings(UGStateMachine.java:310)
	at abc.tm.weaving.weaver.tmanalysis.UGStateMachine.newTransition(UGStateMachine.java:289)
	at abc.tm.weaving.weaver.tmanalysis.UGStateMachine.addStatesFor(UGStateMachine.java:240)
	at abc.tm.weaving.weaver.tmanalysis.UGStateMachine.addStatesFor(UGStateMachine.java:242)
	at abc.tm.weaving.weaver.tmanalysis.UGStateMachine.addStatesFor(UGStateMachine.java:242)
	at abc.tm.weaving.weaver.tmanalysis.UGStateMachine.addStatesFor(UGStateMachine.java:242)
	at abc.tm.weaving.weaver.tmanalysis.UGStateMachine.<init>(UGStateMachine.java:101)
	at abc.tm.weaving.weaver.tmanalysis.TracematchAnalysis.buildUnitGraphStateMachine(TracematchAnalysis.java:316)
	at abc.tm.weaving.weaver.tmanalysis.TracematchAnalysis.buildUnitGraphStateMachines(TracematchAnalysis.java:280)
	at abc.tm.weaving.weaver.tmanalysis.TracematchAnalysis.analyze(TracematchAnalysis.java:150)
	at abc.weaving.weaver.ReweavingPass$Worker.run(ReweavingPass.java:148)
	at java.lang.Thread.run(Thread.java:595)

Regarding the latter, I would have to modify this class anyway when I proceed. Regarding the former, Ondrej could you please give me an indication whether implementing equals/hashcode for the DoublePointsToSet at this point could have any performance negative implications or could otherwise break assumptions you make?

Thanks a lot,

Eric


> -----Original Message-----
> From: soot-list-bounces at sable.mcgill.ca [mailto:soot-list-
> bounces at sable.mcgill.ca] On Behalf Of Eric Bodden
> Sent: Tuesday, August 15, 2006 2:48 PM
> To: soot-list at sable.mcgill.ca
> Subject: RE: [Soot-list] PointsToSet and equals/hashcode
> 
> Ok, since nobody answered so far, I investigated a little myself. Using
> AspectJ (thanks, Laurie, for the idea) I was able to determine that
> apparently "equals" is never called on any implementation of
> PointsToSet within Paddle or Soot.
> 
> Hence I conclude that it cannot hurt if I implement those methods,
> which I will go ahead with now.
> 
> Cheers,
> Eric
> 
> 
> > -----Original Message-----
> > From: soot-list-bounces at sable.mcgill.ca [mailto:soot-list-
> > bounces at sable.mcgill.ca] On Behalf Of Eric Bodden
> > Sent: Sunday, August 13, 2006 8:20 PM
> > To: soot-list at sable.mcgill.ca
> > Subject: [Soot-list] PointsToSet and equals/hashcode
> >
> > Hi all.
> >
> > I am implementing some flow analysis that uses points-to sets as
> > analysis information. As usual, the fixed point iteration stops when
> > the analysis information does not change any more, i.e. when the new
> > one is EQUAL to the old one. EQUAL here means equal based on whatever
> > the equals(Object) method says.
> >
> > Unfortunately the available implementations for PointsToSet in Soot
> do
> > not implements equals nor hashcode, which causes my iteration to go
> on
> > forever. My question is now how to best overcome this issue.
> >
> > Is there any reason for why those methods are not implemented? (It
> > seems that in fact there *can* be multiple instances of one and the
> > same "equal" points-to set so reference-equality is actually not very
> > satisfactory here in my eyes.)
> >
> > Should I just go ahead and implement those methods for
> > PointsToSetInternal etc.? If so, are there any particular hidden
> issues
> > I should take in account?
> >
> > Is there any other way you could think of how to fix my analysis
> > without implementing those methods?
> >
> > Thanks a lot,
> > Eric
> >
> > --
> > Eric Bodden
> > Sable Research Group, McGill University
> > Montréal, Québec, Canada
> >
> > _______________________________________________
> > Soot-list mailing list
> > Soot-list at sable.mcgill.ca
> > http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list
> _______________________________________________
> Soot-list mailing list
> Soot-list at sable.mcgill.ca
> http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list