This post is an extension to the Infinite loops, halting problem and FindBugs containing slightly refactored core code and prepared unit tests using Java SE 8 capabilities. The main extension point is the class LoopUtils which provides methods allowing to verify loops finiteness. Thanks to these methods it is possible to classify methods to finite and infinite. Finiteness is determined by a flexible defined timeout. When a single method’s execution time reaches value of timeout then an execution is classified as infinite. The new code takes advantages on few Java SE 8 new possibilities. The source code is in the same repository but in a dedicated java8enabled branch [1].
1. Development and runtime environment
The provided source code [1] is Java SE 8 compatible.
It was compiled, tested and developed on the following:
- Java version “1.8.0_05″
- Apache Maven 3.2.1
- Spring Tool Suite Version: 3.5.0.RELEASE with Java 8 update
2. Redesigned classes
The following classes were redesign to have only non-static members: RecursiveLoops, SimpleLoops and Halting. In the further part are provided sources of these classes.
2.1. SimpleLoops
package com.softexploration.loops;
import java.util.Scanner;
public class SimpleLoops {
public void alwaysLoops() {
while (true) {
// do nothing
}
}
public void alwaysLoopsVar() {
boolean always = true;
while (always) {
// do nothing
}
}
public void alwaysLoopsFinalVar() {
final boolean always = true;
while (always) {
// do nothing
}
}
public void neverLoops() {
final boolean isNull = "string" == null;
while (isNull) {
// do nothing
}
}
/**
* Loops when reads on input value compatible with Boolean.TRUE
*/
public void somtimesLoops() {
Scanner in = new Scanner(System.in);
final boolean input = Boolean.valueOf(in.next());
in.close();
while (input) {
// do nothing
}
}
}
2.2. RecursiveLoops
package com.softexploration.loops;
public class RecursiveLoops {
public static final long DEFAULT_RECURSIVE_INVOCATION_DELAY = 1;
/**
* Delay [ms] in recursive invocation
*/
private long recursiveInvocationDelay = DEFAULT_RECURSIVE_INVOCATION_DELAY;
public void setRecursiveInvocationDelay(final long recursiveInvocationDelay) {
this.recursiveInvocationDelay = recursiveInvocationDelay;
}
/**
* @return delay [ms] in recursive invocation
*/
public long getRecursiveInvocationDelay() {
return recursiveInvocationDelay;
}
public void f() {
delay();
f();
}
public boolean g() {
delay();
if (g()) {
return true;
} else {
return g();
}
}
public boolean h(final boolean in) {
delay();
if (in) {
h(!in);
}
return false;
}
public int fibonacci(int n) {
delay();
if (n < 2) {
return n;
} else {
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
private void delay() {
try {
Thread.sleep(recursiveInvocationDelay);
} catch (InterruptedException e) {
// interrupted
}
}
}
2.3. Halting
package com.softexploration.loops.halting;
public class Halting {
public boolean halts(final String program) {
return Boolean.valueOf(program);
}
}
3. LoopUtils
This is a new class with loopsForever methods family. All the methods take functional interface as a parameter and some of them have additional value parameters. The goal of the loopsForever is to inform whether a method in a functional interface is infinite or not. If an execution of a method takes more time than the defined through infinityTimeout property then loopsForever returns true. Default loopsForever value is defined in DEFAULT_INFINITY_TIMEOUT field and is equal to 5000 ms. The loopsForever can be adjusted to the actual expectations. Value should be always higher than the longest expected execution time of a studied method.
Even though it is possible analyzing execution time using JUnit timeout parameter in @Test annotation, the presented approach introduces a more elegant and versatile way. The mentioned loopsForever methods take a functional interface as a parameter. A functional interface is a interface having only one method [1]. It allows then introducing lambda expressions or method references instead regular instance of any functional interface.
Units tests (presented in details in further Test classes part) invoke loopsForever on LoopUtils class passing references to the methods from RecursiveLoops, SimpleLoops and Halting classes. The other Java 8 feature used in the code is lambda expression [1]. All overloaded loopsForever methods form LoopUtils except the taking Runnable functional interface invoke internally the loopsForever(final Runnable runnable) passing actual argument as a lambda expression (see these implementation in the LoopUtils source).
Summary of loopsForever method:
- returns true when execution time exceeds infinityTimeout
- takes functional interface as a parameter
- uses internally ExecutorService to determine execution time
LoopUtils
package com.softexploration.loops.util;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;
/**
* Operations on loops
*/
public class LoopUtils {
public static final long DEFAULT_INFINITY_TIMEOUT = 5000L;
/**
* timeout [ms] expressing infinity
*/
private static long infinityTimeout = DEFAULT_INFINITY_TIMEOUT;
public static void setInfinityTimeout(final long infinityTimeout) {
LoopUtils.infinityTimeout = infinityTimeout;
}
/**
* @return timeout [ms] expressing infinity
*/
public static long getInfinityTimeout() {
return infinityTimeout;
}
/**
* Informs whether {@code runnable.run()} loops forever. Loop is considered
* to be infinite if the execution time is longer than
* {@link LoopUtils#getInfinityTimeout()}.
*
* @param runnable
* - runnable to test
* @return informs whether {@code runnable.run()} loops forever
*/
public static boolean loopsForever(final Runnable runnable) {
final ExecutorService executorService = Executors.newFixedThreadPool(1);
executorService.execute(runnable);
executorService.shutdown();
try {
return !executorService.awaitTermination(infinityTimeout,
TimeUnit.MILLISECONDS);
} catch (InterruptedException e) {
throw new RuntimeException(e);
} finally {
executorService.shutdownNow();
}
}
/**
* Informs whether {@code method.f()} loops forever. Loop is considered to
* be infinite if the execution time is longer than
* {@link LoopUtils#getInfinityTimeout()}.
*
* @param method
* - method to test
* @return informs whether {@code method.f()} loops forever
*/
public static boolean loopsForever(final BooleanRetNoArgsMethod method) {
return loopsForever(() -> {
method.f();
});
}
/**
* Informs whether {@code method.f()} loops forever. Loop is considered to
* be infinite if the execution time is longer than
* {@link LoopUtils#getInfinityTimeout()}.
*
* @param method
* - method to test
* @return informs whether {@code method.f()} loops forever
*/
public static boolean loopsForever(final BooleanRetBooleanArgMethod method,
final boolean value) {
return loopsForever(() -> {
method.f(value);
});
}
/**
* Informs whether {@code method.f()} loops forever. Loop is considered to
* be infinite if the execution time is longer than
* {@link LoopUtils#getInfinityTimeout()}.
*
* @param method
* - method to test
* @return informs whether {@code method.f()} loops forever
*/
public static boolean loopsForever(final IntegerRetIntegerArgMethod method,
final int value) {
return loopsForever(() -> {
method.f(value);
});
}
}
4. Test classes
These tests are pretty straightforward. There are tested all methods from RecursiveLoops, SimpleLoops and Halting classes against infiniteness. All the methods are tested by passing their references to loopsForever methods in the LoopUtils class. I encourage take a look on these test methods.
4.1. SimpleLoopsTest
package com.softexploration.loops;
import java.io.ByteArrayInputStream;
import java.io.InputStream;
import org.junit.Assert;
import org.junit.Before;
import org.junit.Test;
import com.softexploration.loops.util.LoopUtils;
public class SimpleLoopsTest {
private SimpleLoops simpleLoops;
@Before
public void setup() {
simpleLoops = new SimpleLoops();
LoopUtils.setInfinityTimeout(1000L);
}
@Test
public void alwaysLoops() {
Assert.assertTrue(LoopUtils.loopsForever(simpleLoops::alwaysLoops));
}
@Test
public void alwaysLoopsVar() {
Assert.assertTrue(LoopUtils.loopsForever(simpleLoops::alwaysLoopsVar));
}
@Test
public void alwaysLoopsFinalVar() {
Assert.assertTrue(LoopUtils
.loopsForever(simpleLoops::alwaysLoopsFinalVar));
}
@Test
public void neverLoops() {
Assert.assertFalse(LoopUtils.loopsForever(simpleLoops::neverLoops));
}
@Test
public void somtimesLoopsFalse() {
final InputStream systemIn = System.in;
System.setIn(new ByteArrayInputStream(Boolean.FALSE.toString()
.getBytes()));
final boolean loopsForever = LoopUtils
.loopsForever(simpleLoops::somtimesLoops);
System.setIn(systemIn);
Assert.assertFalse(loopsForever);
}
@Test
public void somtimesLoopsTrue() {
final InputStream systemIn = System.in;
System.setIn(new ByteArrayInputStream(Boolean.TRUE.toString()
.getBytes()));
final boolean loopsForever = LoopUtils
.loopsForever(simpleLoops::somtimesLoops);
System.setIn(systemIn);
Assert.assertTrue(loopsForever);
}
}
4.2. RecursiveLoopsTest
package com.softexploration.loops;
import org.junit.Assert;
import org.junit.Before;
import org.junit.Test;
import com.softexploration.loops.util.LoopUtils;
public class RecursiveLoopsTest {
private RecursiveLoops recursiveLoops;
@Before
public void setup() {
recursiveLoops = new RecursiveLoops();
LoopUtils.setInfinityTimeout(1000L);
}
@Test
public void f() {
Assert.assertTrue(LoopUtils.loopsForever(recursiveLoops::f));
}
@Test
public void g() {
Assert.assertTrue(LoopUtils.loopsForever(recursiveLoops::g));
}
@Test
public void hFalse() {
Assert.assertFalse(LoopUtils.loopsForever(recursiveLoops::h, false));
}
@Test
public void hTrue() {
Assert.assertFalse(LoopUtils.loopsForever(recursiveLoops::h, true));
}
@Test
public void fibonacci$0() {
Assert.assertFalse(LoopUtils.loopsForever(recursiveLoops::fibonacci, 0));
}
@Test
public void fibonacci$10() {
Assert.assertFalse(LoopUtils
.loopsForever(recursiveLoops::fibonacci, 10));
}
}
4.3. HaltingTest
<
package com.softexploration.loops;
import org.junit.Assert;
import org.junit.Before;
import org.junit.Test;
import com.softexploration.loops.halting.Halting;
import com.softexploration.loops.util.LoopUtils;
public class HaltingTest {
@Before
public void setup() {
LoopUtils.setInfinityTimeout(1000L);
}
@Test
public void doNotHalt() {
final String halts = Boolean.TRUE.toString();
Assert.assertTrue(LoopUtils.loopsForever(() -> {
final Halting halting = new Halting();
if (halting.halts(halts)) {
while (true) {
// do nothing
}
}
}) );
}
@Test
public void doHalt() {
final String halts = Boolean.FALSE.toString();
Assert.assertFalse(LoopUtils.loopsForever(() -> {
final Halting halting = new Halting();
if (halting.halts(halts)) {
while (true) {
// do nothing
}
}
}) );
}
}
Summary
This post shows that thanks to new Java 8 features it is possible to develop more reusable and concise code. Java SE 8 offers much more possibilities. The official statements can be found in [2]. I also see in this provided code, mainly in LoopUtils class, an approach to testing and maybe proving some not so obvious programming concepts (e.g. functions finiteness).
References
[1] http://www.oracle.com/webfolder/technetwork/tutorials/obe/java/Lambda-QuickStart/index.html
[2] http://www.oracle.com/technetwork/java/javase/8-whats-new-2157071.html
Resources
[1] https://github.com/softexploration/com.softexploration.loops/tree/java8enabled