Re: how should Chain.iterator(n,n-1) work?

[Ondrej LHOTAK <olhotak@sable.mcgill.ca>]

Hi John...

I agree that this is a problem. Things like chain which are used all
over the place shouldn't just silently do weird things when passed
illegal arguments. On the other hand, because it's used all over the
place, I'm not very happy with the O(n) validation of the arguments.
So, here's one idea up for discussion: Let's have the chain handle the
special case of when the end statement is one before the start
statement, and in other cases, throw an exception. Specifically, an
exception should be thrown if:

1) the start statement is not in the chain, or
2) iteration reaches the end of the chain without encountering the end
statement.

What does everyone think about this compromise?

Ondrej


On Mon, Aug 23, 2004 at 09:24:16PM -0600, John Jorgensen wrote:
> I've just diagnosed a bug in my code which I strongly suspect
> exists in other parts of Soot, and I'm looking for counsel on how
> to deal with it.
> 
> My bug was due to an iterator created like this:
> 
>   Iterator unitIt = units.iterator(trap.getBeginUnit(), 
> 				   units.getPredOf(trap.getEndUnit());
> 
> which misbehaves for empty Traps, where getBeginUnit() == getEndUnit(),
> since in the call to 
> 
>  Chain.iterator(Object head, Object tail)
> 
> the tail object precedes the head object.  The iterator, which I
> would like to iterate 0 times (though I won't pretend I actually
> foresaw the need to deal with zero-length Traps), ends up
> iterating to the end of the method instead.
> 
> Now you could make a good case that people who ask for iterators
> from p to p-1 get what they deserve. And it would be easy for me
> to add a test to my code to check if getBeginUnit() ==
> getEndUnit() and treat that as a special case. But I'm not the
> only person to use this idiom.  
> 
> grep says that calls of the form
> 
>   Chain.iterator(Trap.getBeginUnit(), Chain.getPredOf(Trap.getEndUnit())
> 
> also appear in soot.TrapManager and
> soot.dava.toolkits.base.misc.ThrowFinder. And there may be other
> code which makes no references to Traps, but which nevertheless
> implicitly assumes that Chain.iterator(p,p-1) iterates 0 times.
> 
> So before I change my code (and TrapManager and ThrowFinder), I
> thought I should ask if people think that Chain.iterator() should
> instead be changed to iterate 0 times when tail precedes head.
> 
> The nuisance with such a change is (unless you want to deal
> only with the special case where tail is the immediate predecessor of
> head) you need to make an O(n) search of the Chain to find out if
> tail precedes head. You also have to decide what to do if the
> tail object is not in the Chain at all. Currently, such a call to
> 
>   Chain.iterator(p, randomJunk)
> 
> will also iterate from p to the end of the method.
> So does consistency demand that if Chain.iterator(p,p-1)
> iterates 0 times, so should Chain.iterator(p,randomJunk)? Or
> should it throw an exception? (For the morbidly curious,
> 
>   Chain.iterator(randomJunk,whatever) 
> 
> already iterates 0 times)
> 
> Not so incidentally: while grepping for those similar iterator
> calls, I think I discovered two off-by-one errors that result
> from a mistaken assumption that Trap.getEndUnit() returns the
> last trapped unit (it actually returns the first unit after the
> last trapped unit, presumably to match the behaviour of the
> indices that mark the scope of exception handlers in bytecode).
> If there's anybody around with a better understanding of
> 
>   soot.jimple.toolkits.invoke.ThrowManager.isExceptionCaughtAt()
> 
> and
> 
>   soot.jimple.toolkits.base.ExceptionChecker.isExceptionCaught()
> 
> I would appreciate it if they would check that code to verify or
> dispel my suspicion that it is mistakenly treating the first
> untrapped unit after the Trap's scope as if it were trapped.
> 
> I've just checked in some changes to soot.Trap's javadoc, 
> in the hope of forestalling more such confusion in future. It
> would have been cleaner if Trap and Chain.iterator() shared
> the same convention about the exclusiveness/inclusiveness of
> their boundary points, but I think the current behaviour is far
> too deeply embedded to contemplate changing it.