0

I want to write a test (using clojure.test) that verifies that some sample code does not cause an infinite loop. If the code that I'm testing is buggy and does cause an infinite loop, I want the test harness to report failure -- rather than just going off and looping forever. (I'm assuming a kind of infinite loop that does not overflow the stack.)

Any ideas how to do this?

Improve this question
2
  • 2
    In the general case [with some spherical-cow assumptions such as infinite memory], you (provably, comp-sci 101 mathematical impossibility) can't do that in any language. I could conceive of an answer that works in some special cases -- ie. recompiling the code to find trampolines or loop/recur calls and comparing current state to every prior observed state and aborting if a state has ever been seen before -- but an infinite loop that never repeats a given state twice isn't exactly hard to come by. Commented Aug 29, 2016 at 20:33
  • 1
    ...now, if you just want to make an assertion such as "this shall always complete in less than N milliseconds of wall-clock time" (or CPU time or what-have-you), that's a lot easier. Commented Aug 29, 2016 at 20:37

3 Answers 3

Reset to default
4

While of course you can't do this in the general case, if you are interested in solving a simpler problem such as "does this function finish executing in at most five seconds?" then you can do it relatively easily. See, for example, a test for the same thing in clojure itself:

(defn sample [& args]
  0)

(deftest test-vars-apply-lazily
  (is (= 0 (deref (future (apply sample (range)))
                  1000 :timeout)))
  (is (= 0 (deref (future (apply #'sample (range)))
                  1000 :timeout))))

Create a future that does the thing you want to do, and then deref that future with a timeout.

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

Thanks for understanding the spirit of the question.
This answer does not stop (apply sample (range)) from running in the background consuming resources. future-cancel can stop futures. How would you integrate terminating the future into this answer?
@Teodor future-cancel can cancel some futures, some of the time. But only when the action taking place on that thread performs some operation that gives the JVM a chance to signal that it should stop: usually this is I/O. The operations in this question cannot be stopped even with future-cancel, and in general I advise not relying on future-cancel for correctness of your program.
Thanks for the explanation. For reference, future-cancel worked on a function that counted from 1 with a (Thread/sleep 1000) 1 second wait between each println.
Yes, because Thread/sleep is explicitly one of those operations I named: it causes the thread to give up control temporarily, and requires the thread to plan for the possibility that the thread has been cancelled in the mean time.
4

That would be equivalent to solving the halting problem, which is impossible.

Improve this answer

2 Comments

In writing unit tests, we define an expected behavior. You are right that, if I wanted to define an expected behavior of, "this code eventually returns a value, even if it takes a billion years", I'd have to solve the halting problem. I don't really find that to be a reasonable interpretation of the question, but you're right that I didn't specify that the code would be expected to return a value within a reasonable period. You have given a correct answer to a question nobody would ever ask (on Stack Overflow)
Answers and comments like this illustrates how well the QA format works. No, finding out in advance if an application will ever terminate is impossible. However, for practical purposes we can use a timeout to get an answer. Upvotes for both!
0

Also, if your loop is known to pass the same data to the next iteration for the same input data (is pure in a way), then you can probably be sure, that if you encounter the same loop parameters on different itarations the loop is probably infinite (meaning it has cycled itself somewhere). For example (quite a stupid one):

(loop [i 20]
  (if (zero? i)
    (recur 10)
    (recur (dec i))))

so when you encounter (= i 10) for the second time, you know it is infinite.

maybe you could creates some macro, for test purposes only, what would track loop's parameters and find the repeated ones like in this answer:

clojure loop see values

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.