testunit and infinite loop

[Bil Kleb]

My searching abilities are failing me today...

How does one detect an infinite loop bug with testunit?

We are writing code test-first and we have found a test which causes
an (erroneous) infinite loop, but we do not know how to write an
*automated* test to expose it -- i.e., we do not have the luxury
of using ctrl-c when this piece of testing code gets inserted into
our build/test robot.

We have been considering the following hack:

a) spawn two threads, one calling the code with the infinite
loop bug and another that merely sleeps for a period of
time much longer that the first task should ever take if
the bug weren't there.

b) raise an exception if the sleeping thread returns before
the other one.

Any tips or comments welcomed,

 

[Nathaniel Talbott]

My searching abilities are failing me today...

How does one detect an infinite loop bug with testunit?

We are writing code test-first and we have found a test which causes
an (erroneous) infinite loop, but we do not know how to write an
*automated* test to expose it -- i.e., we do not have the luxury
of using ctrl-c when this piece of testing code gets inserted into
our build/test robot.

We have been considering the following hack:

a) spawn two threads, one calling the code with the infinite
loop bug and another that merely sleeps for a period of
time much longer that the first task should ever take if
the bug weren't there.

b) raise an exception if the sleeping thread returns before
the other one.

Could you just use timeout?

require 'test/unit'
require 'timeout'

class TC < Test::Unit::TestCase
def test_it
assert_nothing_raised do
timeout(5) do
loop{sleep(1)}
end
end
end
end

ntalbott@jacob:~/sandbox$ ruby t.rb
Loaded suite t
Started
F
Finished in 5.186834 seconds.

1) Failure:
test_it(TC) [t.rb:10]:
Exception raised:
Class: <Timeout::Error>
Message: <"execution expired">
---Backtrace---
/usr/local/lib/ruby/1.9/timeout.rb:42:in `test_it'
t.rb:8:in `loop'
t.rb:8:in `test_it'
t.rb:7:in `timeout'
/usr/local/lib/ruby/1.9/timeout.rb:55:in `timeout'
t.rb:7:in `test_it'
t.rb:6:in `assert_nothing_raised'
t.rb:10:in `test_it'
---------------

1 tests, 1 assertions, 1 failures, 0 errors

Please let me know if I'm misunderstanding your question.

HTH,


Nathaniel

<(><

 

[Bil Kleb]

How does one detect an infinite loop bug with testunit?

We are writing code test-first and we have found a test which causes
an (erroneous) infinite loop, but we do not know how to write an
*automated* test to expose it [..]

Could you just use timeout?

Perfect. Thanks.

However, it still seems like a bit of a hack to have to pick
a large time, but maybe that's the only way out of this paradox?

Regards,

 

[Stephan Kämper]

Perfect. Thanks.

However, it still seems like a bit of a hack to have to pick
a large time, but maybe that's the only way out of this paradox?

Well, I don't think there's a paradox. But I do think the this is a (and
may be even the) way out of this situation.

The question is: Can you tell - by just running the code - whether it
will potentially run forever? And the answer is, no you can't: No
matter how long you wait, the code in question might just need just one
second longer than you 're willinf to wait. (Or it may not...)

BTW, the time out gives you some kind of performance measurement in
addition to the plain functional test.
Not that this would be a recommended way of performance testing...

Happy rubying

Stephan

 

[Eric Schwartz]

How does one detect an infinite loop bug with testunit?

One doesn't. We've known this since Alan Turing proved it in 1936.

Heuristic hacks (such as the timeout solution mentioned) can sometimes
lead you to "good enough" solutions that get you as close as you care
to get, but it is impossible to determine whether a given program can
run forever or not without actually running it.

There's a sketch of the proof in the Wikipedia article on the Halting
Problem (as it's commonly known):

http://en2.wikipedia.org/wiki/Halting_problem

Along with brief mentions of related theorems, such as Rice's Theorem,
which states that "any non-trivial statement about the function that
is defined by an algorithm is undecidable."

IOW, You Can't Get There From Here(tm).

-=Eric, glad his CS degree was useful for *something*