Lab 4: Call Stack

Learning Outcomes

Overview

In this assignment you will implement a stack using singly-linked nodes and use that stack to simulate the call stack used by the JVM to track program flow and manage local variables.

Resources

Assignment

The JVM makes use of a program counter to keep track of what bytecode instruction should be run next. Whenever a method is called, the JVM must keep track of what instruction needs to be run when we return from the method called. The JVM makes use of something called the call stack to store local variables and the memory address to which the program counter must be set when returning from a method call.

Each time a method is called, a stack frame for that method is created. The stack frame includes the memory address to which the program counter should be set when the method returns, all of the arguments passed to the method, and all local variables declared in the method. Consider the following method:

public static void useless(int count) {
    int x = 3;
    int y = 8;
    System.out.println(x + y + count);
}

If this method is called as useless(18);, the stack frame for the method may look like this:

valuerepresents
8<-- y
3<-- x
18<-- count
xx<-- program counter value on return

In our simulation, we will also place a value at the top of each stack frame indicating the size of the stack frame (so that we know how much to pop off the stack when we return from the method). The above example becomes:
4<-- size of stack frame
8<-- y
3<-- x
18<-- count
xx<-- program counter value on return

Details

You will need to implement four classes and associated test classes for this assignment: IntStack, FileReaderUtils, ProgramStack, and Lab4.

IntStack Class

You must implement the following class:

classDiagram class IntStack { -head: Node +push(int value) +pop() int +peek() int +isEmpty() boolean +size() int +toString(): String }
Figure 1: IntStack Class Diagram
push(1)            push(50000)
push(2)            push(-30)
push(3)

|          |
|----------|      |          |
|        3 |      |----------|
|        2 |      |      -30 |
|        1 |      |    50000 |
+----------+      +----------+

You may choose to align the columns so that the output looks better, but it is not required for this assignment.

Input File

To simplify your simulation, you only need to support method arguments, the return program counter value, and the return value. Other local variables need not be supported.

Your program must accept an input file that follows this format:

void first()
  int second(8, 13, 2)
  return 55
  int third()
    void fourth()
    return
  return 0
  fifth()
  return
  sixth()
  return
return

FileReaderUtils Class

You must implement the following class:

classDiagram class FileReaderUtils { +isVoidReturn(String line)$ boolean +parseReturnValue(String line)$ OptionalInt +parseMethodName(String line)$ Optional~String~ +parseArguments(String line)$ int[] }
Figure 2: ProgramFileReaderUtils Class Diagram

This class consists of a number of class methods that should make reading the input file easier.

ProgramStack Class

You must implement the following class:

classDiagram class ProgramStack { -stack: IntStack +ProgramStack() +callMethod(String name, int... arguments) void +returnFromMethod() void +returnFromMethod(int returnValue) void +methodToProgramCounter(String name, int... arguments) int +toString(): String }
Figure 3: ProgramStack Class Diagram

This class will simulate the call stack found in the JVM.

If the name is one and there are no arguments, then the program counter is calculated as:

\[ ((('o' \times 2 + 'n') \times 2 + 'e') \times 2) = (((111 \times 2 + 112) \times 2 + 101) \times 2) = ((332 \times 2 + 101) \times 2) = 765 \times 2 = 1530 \]

If the name is two and there is one argument, then the program counter is calculated as:

\[ ((('t' \times 2 + 'w') \times 2 + 'o') \times 2) + 1 = (((116 \times 2 + 119) \times 2 + 111) \times 2 + 1 = ((351 \times 2 + 111) \times 2 + 1 = 813 \times 2 + 1 = 1627 \]

returnFromMethod(int)

This method removes the top-most stack from off of the internal stack and adds the returnValue as a local variable to the next top-most stack frame (if one exists).

In order to add the return value as a local variable to the next top-most stack frame, you will need to add the value and increase the size of the stack frame by one. To do this, you will need to remove the integer at the top of the stack (which represents the size of the stack frame), push the return value onto the stack, and then push the size of the stack frame + 1 onto the top of the stack.

Suppose we have the following input file:

one()
  int two(4)
  return 8
return

Here is what the stack should look like after each line of the file has been processed:

one()
1
1530

int two(4)
2
4
1627
1
1530

return 8
2
8
1530

return

Lab4 Class

This class contains the main() method for a program that:

Below is an example of an input file and the corresponding program output.

Input File

one()
  int two(4)
blah, blah, blah
  return 8
return

Sample Output

Please enter the name of the input file: calls.txt

one()
|          |
|----------|
|        1 |
|     1530 |
+----------+

  int two(4)
|          |
|----------|
|        2 |
|        4 |
|     1627 |
|        1 |
|     1530 |
+----------+

blah, blah, blah
Invalid line, ignored

  return 8
|          |
|----------|
|        2 |
|        8 |
|     1530 |
+----------+

return
|          |
|----------|
+----------+

Just For Fun

Once the minimum requirements are met, ambitious students may wish to:

Acknowledgment

This laboratory assignment was developed by Dr. Chris Taylor.

See your professor's instructions for details on submission guidelines and due dates.