[squeak-dev] SUnit infinite loop detection

I wanted to assert some infiniteLoop, but found no other support than:
should:notTakeMoreThanMilliseconds:

I do not really like it, because it may vary
- a fast machine could exhaust memory and crash before duration
- a slow machine could fail

I put a proposal for recursive loops at
http://bugs.squeak.org/view.php?id=7111

In case of Error during block execution, my implementation makes the
test pass. I think it's wrong, but do not know how to handle...

And i am still interested by a way to assert infinite iterative loop
(the whileTrue/whileFalse case). Anyone has an idea about it?

Nicolas

On 5-Jul-08, at 5:49 PM, nicolas cellier wrote:

> And i am still interested by a way to assert infinite iterative loop  
> (the whileTrue/whileFalse case). Anyone has an idea about it?

Wouldn't that involve solving the halting problem?

Colin

On 5-Jul-08, at 9:58 PM, Colin Putney wrote:

>
> On 5-Jul-08, at 5:49 PM, nicolas cellier wrote:
>
>> And i am still interested by a way to assert infinite iterative  
>> loop (the whileTrue/whileFalse case). Anyone has an idea about it?
>
> Wouldn't that involve solving the halting problem?
Well to quote one of my siglines
"The theorists have proven that this is impossible, but there's three  
of us and we're smart..."
Hmm, and right next it it -
"For those of you who are into writing programs that are as obscure  
and complicated as possible, there are opportunities for... real fun  
here"
That about covers it.

tim
--
tim Rowledge; [hidden email]; http://www.rowledge.org/tim
Strange OpCodes: ED: Eject Disk

tim Rowledge a écrit :
Ah yes, thank you to remind me, this is impossible.
I'm not smart enough to fight such powerfull proofs.
Sorry, i'm just an engineer...

I'm dumbfully pragmatic and just want to provide a hint on the loop count.
This work for recursive loops thanks to stack depth Context spying.
Unfortunately (fortunately!), #WhileTrue and the like are optimized with
the jump byte code.

If anyone has an idea not as heavy as a simulator, I take it.
A kind of VM instrumentation support would be great...
A VM could count number of backward jump per Context... (i know, Context
slot are not cheap).

By now, i use a wall clock threshold.
This hint is by far more rough than a loop counter...
It is very sensitive to underlying hardware.
Well spy process also is, due to the delay between two probes.
That would deserve some kind of calibration to be reset at
#returnFromSnapshot!

Finally, i could tally it myself the hard way with the spy process:
observe instruction counter of each context in the stack, compare to
previous snapshot and increment a backward loop counter. But i guess it
would be statistically biased. If first instructions in the loop are
fast, and last is long, i might not be able to detect a loop at all...

Nicolas

If your code is likely to run into an infinite loop, you should assert that in
your application code. This is one of the things tests can not do for you.

No everything can be solved with schoolbook engineering :)

cheers,
AA

Adrian Kuhn a écrit :
> If your code is likely to run into an infinite loop, you should assert that in
> your application code. This is one of the things tests can not do for you.
>

would it be only my code, that i would manage.
This is the squeak kernel code i'm interested in.

Some infinite loops have been removed (presumably).
And I want to be able to write non regression SUnit tests that's all.

How would you do it?

> No everything can be solved with schoolbook engineering :)
>
> cheers,
> AA
>

On 6-Jul-08, at 1:33 PM, nicolas cellier wrote:

> Some infinite loops have been removed (presumably).
> And I want to be able to write non regression SUnit tests that's all.
>
> How would you do it?

It's try to find some way to measure the progress of the algorithm. If  
you're testing #printOn:, can you monitor the stream to see if any  
digits have been printed? Are there some intermediate results that you  
can check?

Another approach to isolate the bugfix and test that specifically.  
When you fixed the infinite loop, what did you change? Is there a way  
to test that in a narrow sense? For example, say the bug was that an  
index into an array wasn't getting incremented at the end of the loop.  
Now you've added code to do the increment. Is there a way to test that  
the index gets incremented rather than testing the overall behavior of  
the loop?

Maybe this "untestability" is a code smell - perhaps there's some  
refactoring that could be done to expose more parts of the algorithm  
to testing in isolation.

Colin

Temporarily, replace a method in method dictionary with 'test' object
or compiled method
(Squeak can use any object as 'method', not just to a compiled method).
There you can inspect arguments and see, if your loop is still infinite.
Of course its implies , that you have sends within a loop, which can
be intercepted in that way.

2008/7/6 Colin Putney <[hidden email]>:


--
Best regards,
Igor Stasenko AKA sig.

Colin, Igor,
thank you, you have some good ideas.
They do not match my requirement though.
I don't want to test a specific implementation,
I want to test a feature.

     self should: [33 printStringBase: 1] raise: Error.

The idea is to have some generic tests automated to check base images
and/or packages.

Unfortunately, current implementation will not fail, it will loop!
Knowing this, I can protect the test with something like

     self
         should: [self should: [10 printStringBase: 1] raise: Error]
         notTakeLongerThanMilliseconds: 1000.

In little better English:
     self
         should: [10 printStringBase: 1]
         notTakeLongerThanMilliseconds: 1000
        toRaise: Error.

The 1000ms figure here is quite arbitrary.
If delay is too short, would the test pass on a 486 µ-proc running a
Simulator?
If a long delay is ran on a fast machine, some recursive loop might
exhaust memory and crash the VM (the VM should be robust, but...).
This can easily happen, you load incompatible changes and
printStringBase: send printOn:base: sends printStringBase: etc...

I thought the idea of a generic SUnit support message for counting loops
would be smarter:

     self
         should: [self should: [33 printStringBase: 1] raise: Error]
         notLoopMoreThan: 100.

Up to test maker to provide a reasonnable hint.
Here, even a loop on bits should hardly loop more than (33 highBit + 1).

As said before, support is easy for recursive loop, not for iterative...

Now, when i think of it, does it really add some value?
The point is why would i protect only this specific TestCase? Because I
know it fails, but maybe there are plenty others ready to fail and they
will block the testing image...

That should rather be a general rule: a single test case consuming too
much resource (memory and/or cpu) should be halted and declared failing.
That would be a a nice application: an image monitoring another...
A job for a HydraVM?

...or maybe monitoring a bunch of others: you want to test N packages?
Well that is 2^N different partitions, hope the multi-core won't stop at
1000, that makes only 10 packages to test together... As an exercize,
compute number of message sends required to test all the SqueakMap
packages combinations (Who is the smart guy that will fight the
combinatorial hydra?).

Cheers

Nicolas

Igor Stasenko a écrit :

On 7-Jul-08, at 2:31 PM, nicolas cellier wrote:

I understand what you'd like to achieve. One of the most important  
design goals in test cases is clarity on what it means to pass the  
test and what it means to fail. Ideally, you want assertions you make  
about your code to correspond to your goals as a programmer as closely  
as possible. So yes, you'd like to write something like:

self denyLoopsInfinitely: [10 printStringBase: 1].

But that's impossible for the general case. So my suggestions were  
about finding a degenerate case that would at least make it possible  
to detect whether or not your fix has been applied. That would at  
least prevent regressions. That kind of test is ugly and brittle,  
though, and it might be better just of fix the infinite loop and move  
on.

Your idea of automated test suites that put limits on the resources  
that can be consumed during testing is interesting. I do think that  
Squeak should have some kind of automated nightly regression tests,  
and that might be something to implement there.

Colin

>  The 1000ms figure here is quite arbitrary.

Why not measure how long it takes to evaluate the similar expression:

    t := [ 100 timesRepeat: [ 33 printStringBase: 2 ] ] timeToRun

and then use the result t as an upper-bound to the execution time of
evaluating [ 33 printStringBase: 1 ] once? You probably have to play a
bit with the factor to get meaningful results.

Cheers,
Lukas

--
Lukas Renggli
http://www.lukas-renggli.ch

Lukas Renggli a écrit :
If you play with (Installer ensureFix: 6887)
on a recent machine, that might well be zero.

The idea of calibrating sounds good.
The idea of milliseconds sounds... deprecated.
(We should use Duration objects and let the VM devide for granularity).

Nicolas