Call stack #

A call stack is a stack that keeps track of the methods that are active during the execution of a program. By “active”, we mean that an execution of the method has started and has not terminated yet.

When the execution of a method starts, the method is “pushed” on top of the stack. When it terminates, the method is “popped” from the stack, and control is passed back to the method that called it (which is now on top of the stack).

A debugger provides a representation of the successive states of a call stack, with references to the source code. This gives the illusion of source code being interpreted verbatim.

Example. In our game, consider the following implementation of the method callReinforcement:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38


public class Backend implements EventHandler {

  Snapshot currentSnapshot;
  ...

  @Override
  public void callReinforcement() {

    Player activePlayer = currentSnapshot.getActivePlayer();
    int unitsToInsert = currentSnapshot.getSizeOfReinforcement(activePlayer);

    while (unitsToInsert > 0){
      Unit unit = generateRandomUnit();
      TileCoordinates coordinates = findInsertionSpot(unit);
      if(coordinates != null) {
        addUnit(coordinates, unit);
        unitsToInsert--;
      }
    }
  }

  private Unit generateRandomUnit() {
    ...
  }

  private TileCoordinates findInsertionSpot(Unit unit) {
    ...
  }

  private void addUnit(TileCoordinates coordinates, Unit unit) {
    currentSnapshot.getBoard().addUnit(coordinates.rowIndex(), coordinates.columnIndex(), unit);
    performUnitMerges();
  }

  private void performUnitMerges() {
    ...
  }
}

When the method callReinforcement is called, it is added (a.k.a. pushed) on top of the call stack. This is rendered by a debugger as:

callReinforcement
<rest of the call stack>

If execution “reaches” Line 13, then the method generateRandomUnit is called and added to the stack:

generateRandomUnit
callReinforcement: 13
<rest of the call stack>

When the method generateRandomUnit terminates, it passes control (as well as a Unit) back to the method that called it, namely callReinforcement, which can resume its execution:

callReinforcement
<rest of the call stack>

Similarly, when execution “reaches” Line 14, findInsertionSpot is added to the stack, executed, and then removed from the stack, passing control back to callReinforcement.

Then if execution “reaches” Line 16, addUnit is executed, which in turn calls performUnitMerges:

performUnitMerges
addUnit: 32
callReinforcement: 16
<rest of the call stack>

etc.

Note. If a method is recursive (i.e. if it calls itself, directly or indirectly), then it may appear multiple times in the call stack. E.g.:
method1
method2: 16
method1: 8
<rest of the call stack>

Definition. A stack overflow occurs when the size of the call stack exceeds the capacity allowed by the execution environment. This is usually due to a non-terminating recursive method.