Diagnosing the cause of a StackOverflowError can be fairly straightfoward if the code has been compiled with the debug option turned on so that line numbers are available in the resulting stack trace. In such cases, it is typically simply a matter of finding the repeating pattern of line numbers in the stack trace. The pattern of repeating line numbers is helpful because a StackOverflowError is often caused by unterminated recursion. The repeating line numbers indicate the code that is being directly or indirectly recursively called. Note that there are situations other than unbounded recursion in which a stack overflow might occur, but this blog posting is limited to
StackOverflowError caused by unbounded recursion.The relationship of recursion gone bad to
StackOverflowError is noted in the Javadoc description for StackOverflowError that states that this Error is "Thrown when a stack overflow occurs because an application recurses too deeply." It is significant that StackOverflowError ends with the word Error and is an Error (extends java.lang.Error via java.lang.VirtualMachineError) rather than a checked or runtime Exception. The difference is significant. The Error and Exception are each a specialized Throwable, but their intended handling is quite different. The Java Tutorial points out that Errors are typically external to the Java application and thus normally cannot and should not be caught or handled by the application.I will demonstrate running into
StackOverflowError via unbounded recursion with three different examples. The code used for these examples is contained in three classes, the first of which (and the main class) is shown next. I list all three classes in their entirety because line numbers are significant when debugging the StackOverflowError.StackOverflowErrorDemonstrator.java
package dustin.examples.stackoverflow;
import java.io.IOException;
import java.io.OutputStream;
/**
* This class demonstrates different ways that a StackOverflowError might
* occur.
*/
public class StackOverflowErrorDemonstrator
{
private static final String NEW_LINE = System.getProperty("line.separator");
/** Arbitrary String-based data member. */
private String stringVar = "";
/**
* Simple accessor that will shown unintentional recursion gone bad. Once
* invoked, this method will repeatedly call itself. Because there is no
* specified termination condition to terminate the recursion, a
* StackOverflowError is to be expected.
*
* @return String variable.
*/
public String getStringVar()
{
//
// WARNING:
//
// This is BAD! This will recursively call itself until the stack
// overflows and a StackOverflowError is thrown. The intended line in
// this case should have been:
// return this.stringVar;
return getStringVar();
}
/**
* Calculate factorial of the provided integer. This method relies upon
* recursion.
*
* @param number The number whose factorial is desired.
* @return The factorial value of the provided number.
*/
public int calculateFactorial(final int number)
{
// WARNING: This will end badly if a number less than zero is provided.
// A better way to do this is shown here, but commented out.
//return number <= 1 ? 1 : number * calculateFactorial(number-1);
return number == 1 ? 1 : number * calculateFactorial(number-1);
}
/**
* This method demonstrates how unintended recursion often leads to
* StackOverflowError because no termination condition is provided for the
* unintended recursion.
*/
public void runUnintentionalRecursionExample()
{
final String unusedString = this.getStringVar();
}
/**
* This method demonstrates how unintended recursion as part of a cyclic
* dependency can lead to StackOverflowError if not carefully respected.
*/
public void runUnintentionalCyclicRecusionExample()
{
final State newMexico = State.buildState("New Mexico", "NM", "Santa Fe");
System.out.println("The newly constructed State is:");
System.out.println(newMexico);
}
/**
* Demonstrates how even intended recursion can result in a StackOverflowError
* when the terminating condition of the recursive functionality is never
* satisfied.
*/
public void runIntentionalRecursiveWithDysfunctionalTermination()
{
final int numberForFactorial = -1;
System.out.print("The factorial of " + numberForFactorial + " is: ");
System.out.println(calculateFactorial(numberForFactorial));
}
/**
* Write this class's main options to the provided OutputStream.
*
* @param out OutputStream to which to write this test application's options.
*/
public static void writeOptionsToStream(final OutputStream out)
{
final String option1 =
"1. Unintentional (no termination condition) single method recursion";
final String option2 =
"2. Unintentional (no termination condition) cyclic recursion";
final String option3 =
"3. Flawed termination recursion";
try
{
out.write((option1 + NEW_LINE).getBytes());
out.write((option2 + NEW_LINE).getBytes());
out.write((option3 + NEW_LINE).getBytes());
}
catch (IOException ioEx)
{
System.err.println("(Unable to write to provided OutputStream)");
System.out.println(option1);
System.out.println(option2);
System.out.println(option3);
}
}
/**
* Main function for running StackOverflowErrorDemonstrator.
*/
public static void main(final String[] arguments)
{
if (arguments.length < 1)
{
System.err.println(
"You must provide an argument and that single argument should be");
System.err.println(
"one of the following options:");
writeOptionsToStream(System.err);
System.exit(-1);
}
int option = 0;
try
{
option = Integer.valueOf(arguments[0]);
}
catch (NumberFormatException notNumericFormat)
{
System.err.println(
"You entered an non-numeric (invalid) option [" + arguments[0] + "]");
writeOptionsToStream(System.err);
System.exit(-2);
}
final StackOverflowErrorDemonstrator me = new StackOverflowErrorDemonstrator();
switch (option)
{
case 1 :
me.runUnintentionalRecursionExample();
break;
case 2 :
me.runUnintentionalCyclicRecusionExample();
break;
case 3 :
me.runIntentionalRecursiveWithDysfunctionalTermination();
break;
default :
System.err.println("You provided an unexpected option [" + option + "]");
}
}
}
The class above demonstrates three types of unbounded recursion: accidental and completely unintended recursion, unintended recursion associated with intentionally cyclic relationships, and intended recursion with insufficient termination condition. Each of these and their output are discussed next.
Completely Unintended Recursion
There can be times when recursion occurs with no intent of it whatsoever. A common cause might be having a method accidentally call itself. For example, it is not too difficult to get a little too careless and select an IDE's first recommendation on a return value for a "get" method that might end up being a call to that very same method! This is in fact the example shown in the class above. The
getStringVar() method repeatedly calls itself until the StackOverflowError is encountered. The output will appear as follows:
Exception in thread "main" java.lang.StackOverflowError
at dustin.examples.stackoverflow.StackOverflowErrorDemonstrator.getStringVar(StackOverflowErrorDemonstrator.java:34)
at dustin.examples.stackoverflow.StackOverflowErrorDemonstrator.getStringVar(StackOverflowErrorDemonstrator.java:34)
at dustin.examples.stackoverflow.StackOverflowErrorDemonstrator.getStringVar(StackOverflowErrorDemonstrator.java:34)
at dustin.examples.stackoverflow.StackOverflowErrorDemonstrator.getStringVar(StackOverflowErrorDemonstrator.java:34)
at dustin.examples.stackoverflow.StackOverflowErrorDemonstrator.getStringVar(StackOverflowErrorDemonstrator.java:34)
at dustin.examples.stackoverflow.StackOverflowErrorDemonstrator.getStringVar(StackOverflowErrorDemonstrator.java:34)
at dustin.examples.stackoverflow.StackOverflowErrorDemonstrator.getStringVar(StackOverflowErrorDemonstrator.java:34)
at dustin.examples.stackoverflow.StackOverflowErrorDemonstrator.getStringVar(StackOverflowErrorDemonstrator.java:34)
at dustin.examples.stackoverflow.StackOverflowErrorDemonstrator.getStringVar(StackOverflowErrorDemonstrator.java:34)
at
The stack trace shown above actually is many times longer than that which I placed above, but it is simply the same repeating pattern. Because the pattern is repeating, it is easy to diagnose that line 34 of the class is the problem-causer. When we look at that line, we see that it is indeed the statement
return getStringVar() that ends up repeatedly calling itself. In this case, we can quickly realize that the intended behavior was to instead return this.stringVar;.Unintended Recursion with Cyclic Relationships
There are certain risks to having cyclic relationships between classes. One of these risks is the greater likelihood of running into unintended recursion where the cyclic dependencies are continually called between objects until the stack overflows. To demonstrate this, I use two more classes. The
State class and the City class have a cyclic relationshiop because a State instance has a reference to its capital City and a City has a reference to the State in which it is located.State.java
package dustin.examples.stackoverflow;
/**
* A class that represents a state and is intentionally part of a cyclic
* relationship between City and State.
*/
public class State
{
private static final String NEW_LINE = System.getProperty("line.separator");
/** Name of the state. */
private String name;
/** Two-letter abbreviation for state. */
private String abbreviation;
/** City that is the Capital of the State. */
private City capitalCity;
/**
* Static builder method that is the intended method for instantiation of me.
*
* @param newName Name of newly instantiated State.
* @param newAbbreviation Two-letter abbreviation of State.
* @param newCapitalCityName Name of capital city.
*/
public static State buildState(
final String newName,
final String newAbbreviation,
final String newCapitalCityName)
{
final State instance = new State(newName, newAbbreviation);
instance.capitalCity = new City(newCapitalCityName, instance);
return instance;
}
/**
* Parameterized constructor accepting data to populate new instance of State.
*
* @param newName Name of newly instantiated State.
* @param newAbbreviation Two-letter abbreviation of State.
*/
private State(
final String newName,
final String newAbbreviation)
{
this.name = newName;
this.abbreviation = newAbbreviation;
}
/**
* Provide String representation of the State instance.
*
* @return My String representation.
*/
@Override
public String toString()
{
// WARNING: This will end badly because it calls City's toString()
// method implicitly and City's toString() method calls this
// State.toString() method.
return "StateName: " + this.name + NEW_LINE
+ "StateAbbreviation: " + this.abbreviation + NEW_LINE
+ "CapitalCity: " + this.capitalCity;
}
}
City.java
package dustin.examples.stackoverflow;
/**
* Encapsulates City information and provides example of cyclic dependency.
*/
public class City
{
private static final String NEW_LINE = System.getProperty("line.separator");
/** Name of City. */
private String name;
/** Name of State the city is part of. */
private State state;
/**
* Parameterized constructor accepting parameters to populate me.
*
* @param newCityName Name of this newly instantiated city.
* @param newState State to which this city belongs.
*/
public City(
final String newCityName,
final State newState)
{
this.name = newCityName;
this.state = newState;
}
/**
* Provide String representation of this instance of City.
*
* @return My String representation.
*/
@Override
public String toString()
{
// WARNING: This will end badly because it calls State's toString()
// method implicitly and State's toString() method calls this
// City.toString() method.
return "City Name: " + this.name + NEW_LINE
+ "State: " + this.state;
}
}
In my example, the
StackOverflowError occurs when the respective toString() methods of each object try to call one another. They do so repeatedly until they overflow the stack. The output from running the test is shown next:
The newly constructed State is:
Exception in thread "main" java.lang.StackOverflowError
at java.lang.StringBuilder.append(StringBuilder.java:119)
at dustin.examples.stackoverflow.City.toString(City.java:41)
at java.lang.String.valueOf(String.java:2826)
at java.lang.StringBuilder.append(StringBuilder.java:115)
at dustin.examples.stackoverflow.State.toString(State.java:62)
at java.lang.String.valueOf(String.java:2826)
at java.lang.StringBuilder.append(StringBuilder.java:115)
at dustin.examples.stackoverflow.City.toString(City.java:41)
at java.lang.String.valueOf(String.java:2826)
at java.lang.StringBuilder.append(StringBuilder.java:115)
at dustin.examples.stackoverflow.State.toString(State.java:62)
at java.lang.String.valueOf(String.java:2826)
at java.lang.StringBuilder.append(StringBuilder.java:115)
at dustin.examples.stackoverflow.City.toString(City.java:41)
at java.lang.String.valueOf(String.java:2826)
at java.lang.StringBuilder.append(StringBuilder.java:115)
at dustin.examples.stackoverflow.State.toString(State.java:62)
at java.lang.String.valueOf(String.java:2826)
at java.lang.StringBuilder.append(StringBuilder.java:115)
at dustin.examples.stackoverflow.City.toString(City.java:41)
at java.lang.String.valueOf(String.java:2826)
As with the stack trace shown in the previous example, this one actually goes on much longer than the small sample I included above. Like that previous example, the remainder was simply repeated lines of what is shown in the above sample. In this case, we can see repeated line numbers. In particular, we see that line 41 of City.java and line 62 of State.java are repeat offenders. When we look at what these lines are in these two classes, it is not surprising that it is the "return" statement in each class's respective
toString implementation where the other class's toString method is implicitly invoked.Once we see the repeating pattern and identify the cause as the cyclic
toString invocations, we have several choices for fixing the situation. An obvious and easy approach is to reference portions of the "other" object rather than relying on the other object's toString. For example, we could add "get" methods to each object to return the name of the city or state and then have the toString implementations only call the getName() of the other class. We would only need to do this for one or the other to break the cycle, but we might choose that approach for both anyway.Intended Recursion with Dysfunctional Termination Condition
Even with intentional recursion, we might run into a
StackOverflowError if our terminating condition is insufficient for all cases our code might encounter. In the example in this blog posting, the everyday recursion example of implementing a factorial is used. However, the terminating condition is changed just enough to lead to problems
The factorial of -1 is: Exception in thread "main" java.lang.StackOverflowError
at dustin.examples.stackoverflow.StackOverflowErrorDemonstrator.calculateFactorial(StackOverflowErrorDemonstrator.java:49)
at dustin.examples.stackoverflow.StackOverflowErrorDemonstrator.calculateFactorial(StackOverflowErrorDemonstrator.java:49)
at dustin.examples.stackoverflow.StackOverflowErrorDemonstrator.calculateFactorial(StackOverflowErrorDemonstrator.java:49)
at dustin.examples.stackoverflow.StackOverflowErrorDemonstrator.calculateFactorial(StackOverflowErrorDemonstrator.java:49)
at dustin.examples.stackoverflow.StackOverflowErrorDemonstrator.calculateFactorial(StackOverflowErrorDemonstrator.java:49)
at dustin.examples.stackoverflow.StackOverflowErrorDemonstrator.calculateFactorial(StackOverflowErrorDemonstrator.java:49)
at dustin.examples.stackoverflow.StackOverflowErrorDemonstrator.calculateFactorial(StackOverflowErrorDemonstrator.java:49)
at dustin.examples.stackoverflow.StackOverflowErrorDemonstrator.calculateFactorial(StackOverflowErrorDemonstrator.java:49)
at dustin.examples.stackoverflow.StackOverflowErrorDemonstrator.calculateFactorial(StackOverflowErrorDemonstrator.java:49)
at
Like the other two previously displayed stack traces, only a small sample of this one is shown. The remainder of it is the same anyway.
This last
StackOverflowError could have been avoided in a couple ways. First, we could have improved the termination condition to check for a passed in number less than or equal to one to return 1. The result of the factorial calculation might still not be correct, but at least it would not result in a StackOverflowError. An even better solution might be to check the passed-in integer to ensure that it is positive and throw an IllegalArgumentException if it is not.Whether the appropriate recursion termination condition is enforced prior to applying recursion or as part of the recursion termination condition itself or both, the important point here is that all paths into the recursive functionality must be accounted for and terminated appropriately. Otherwise, recursive functionality can become unbounded and result in a
StackOverflowError.StackOverflowError sans Recursion
As I mentioned earlier, a
StackOverflowError might be encountered for reasons other than unbounded recursion. In such situations, the fix will be something other than bounding recursion. Solutions might include eliminating obscenely large objects allocated on the stack or increasing the default stack size (-Xss JVM option on HotSpot JVM). Most often, however, I have seen StackOverflowError associated with uncontrolled recursion and these are often easily addressed.Conclusion
The
StackOverflowError is often one of the easier errors to debug and diagnose. Because it is commonly associated with unterminated recursion, the key to diagnosing the error is to typically look for patterns of repetitious code calls and then figure out why that series of calls never reaches a terminating condition. The StackOverflowError is a runtime error by nature. The best way to avoid it is to carefully consider one's termination conditions when using explicit recursion, be cautious when using cyclic references, and to be on the watch for accidental and completely unintended recursion. Fortunately, if an unterminated recursive condition does creep in, it is typically relatively easy to diagnose and often not too difficult to resolve.
No comments:
Post a Comment