CS2852 Lab 4: Call Stack

Learning Outcomes

• Implement a class that provides an efficient implementation of the stack interface based on a singly linked list
• Implement small software systems that use one or more stack data structures

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

• Complete SLM4 before starting this assignment.

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:

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:

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:

• If pop() or peek() are called on an empty stack, an EmptyStackException must be thrown.
• Node must be a private static inner class that keeps track of a node in a singly-linked list
• The toString() method must return a String that displays the contents of the stack using the format shown in the examples below. (The width should be ten characters, as shown.)
• The size() method must count all the nodes (no size attribute).

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

• Method calls are represented by a name and be follwed by parentheses.
• The parentheses may contain a comma-separated list of integers, representing the values of arguments passed to the method.
• If a method returns an int, it must
  • begin the line with int (see line 2 above)
  • have a corresponding return statement that includes an integer value at the end of the line (see line 3 above)
• Methods that do not return a value may begin with void (see line 1 above) or not (see line 9 above)
• There may be whitespace at the beginning and/or ending of a line.
• There may be whitespace before or after punctuation ((, ), and ,).
• Lines that do not contain a method call or return statement must be ignored (including blank lines)
• You may assume that each method call is matched with the appropriate return statement (e.g., includes integer value if needed).

FileReaderUtils Class

You must implement the following class:

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

• isVoidReturn(String) — returns false unless the argument passed in contains only “return”
• parseReturnValue(String) — returns an empty OptionalInt unless the argument passed contains “return” and an integer value separated by whitespace. In that case, the integer value is returned.
• parseMethodName(String) — returns an empty Optional<String> unless the argument passed contains a method call. In that case, the method name is returned.
  • The argument contains a method call if it consists of a method name followed by parentheses.
  • There may be either void or int before the method name.
  • There may be whitespace between the method name and the opening parathesis.
  • There may be zero or more characters between the opening and closing parentheses.
• parseArguments(String) — returns an array of integers representing the arguments passed to a method.
  • null should be returned if the argument passed does not represent a method call.
  • An empty array should be returned if there are no arguments between the parentheses.
  • An array containing the values of the arguments should be returned if there are one or more arguments specified.
  • The method must throw an IllegalArgumentException if anything other than a comma-separated list of integers is found between the parentheses. Note: there may be whitespace after each comma.

ProgramStack Class

You must implement the following class:

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

• callMethod(String name, int... arguments) — This method should push the stack frame for the method call represented by the arguments onto the internal stack. Use the methodToProgramCounter() method to obtain the value for the program counter. In addition, you must push the size of the stack frame onto the stack (as described above).
• returnFromMethod() — This method removes the top-most stack frame off of the internal stack.
• returnFromMethod(int) — See below
• methodToProgramCounter(String name, int... arguments) — This method calculates a program counter value according to the following formula (note: this is completely made up and not how it would work in practice). The return value starts with the character value of the first multiplied by two. For each subsequent character, add the character value and multiple the result by two. Do this for all characters in the name. If there is at least one argument, add one to the result. See below for two examples.
• toString() — Returns the result of calling toString() on the internal stack.

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

(((′�′×2+′�′)×2+′�′)×2)=(((111×2+112)×2+101)×2)=((332×2+101)×2)=765×2=1530

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

(((′�′×2+′�′)×2+′�′)×2)+1=(((116×2+119)×2+111)×2+1=((351×2+111)×2+1=813×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()

int two(4)

return 8

return

Lab4 Class

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

• Asks the user for the name of an input file.
• Reads the input file and maintains the call stack.
• The program should display the line followed by the contents of the stack after the line is processed.

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:

• Support more than just integer values
• Support local variables (not just arguments passed to a method)
• Create alternative input files