Project 0: Program trace verification

Due: Sunday, 8/28/2022, by 12:00pm noon

You will receive 100% if you turn the project in on time, and a 25% late penalty will be applied if the program is turned-in past the deadline. Points will be deducted accordingly if it does not pass the style guidelines.

Total points: 10

Before you start this project, you should have read the project submission guidelines and the coding style rules.

After that, get started on the project immediately! Remember you also have Homework 0 to do, so manage your time wisely.

Project Description

The goals of this project are to:
  • Brush up your C++ skills.
  • Use the stack data structure, which you are familiar with.
  • Use standard libraries and classes for standard input/output, which will be used a lot in this class.
  • Test your program in the command line environment, and
  • Get used to how this course uses Upload Site.

When a compiled C++ program executes, it usually starts in the function called main(). From there, it can call another function, say read_input(), which in turn might call another function, such as get_data(), etc. The executing program also returns from each called function, in the reverse order from the call order. So continuing our example, it must first return from get_data(), then return from read_input(), then return from main(). Conversely, it could not return from read_input() before it had returned from the inner call to get_data().

There are many program analysis tools that allow programmers to examine the behavior of executing programs. You're probably familiar with debuggers, which allow a programmer to pause an executing program, examine variables, etc. Valgrind (pronounced "val-grinned") is another tool which examines executing programs for various problems like memory leaks. Many such tools can operate on or produce program traces, which describe things like the order of function calls and returns. We expect traces to be valid, in that every function call has an appropriately matched return from that function.

Here are examples of both valid and an invalid program traces. Both assume that we are starting in the (unnamed) outermost function (e.g. main()).

Trace 1 (valid) Trace 2 (invalid) Trace 3 (invalid) Trace 4 (invalid) 
call read_input
call get_data
return get_data
call get_data
return get_data
return read_input
call solve
call log
return log
call abs
return abs
call wrt_data
return wrt_data
return solve

call read_input
call get_data
return get_data
call get_data
return read_input
call solve
call log
return log
call abs
return abs
call wrt_data
return wrt_data
return solve

call read_input
call get_data
return get_data
call get_data
return get_data
return read_input
call log
return log
call abs
return abs
call wrt_data
return wrt_data
return solve

call read_input
call get_data
return get_data
call get_data
return get_data
return read_input
call solve
call log
return log
call abs
return abs
call wrt_data
return wrt_data
Trace 1 is valid, because every function call return in the correct order.
Traces 2-4 are invalid, because:
  • Trace 2 returns from read_input() before it returns from get_data.
  • Trace 3 returns from solve(), but that function was never called.
  • Trace 4 does not return from solve().

Your task for this project is to determine the validity of program traces. You'll be given a trace of an executing program, and you should determine whether the trace is valid or not. If it's not valid, your program should describe why.

You will use a standard stack to keep track of called functions. Here is a good algorithm for validating program traces. For each function called, place the function's name on the stack. When a function returns, check that its name matches the name on the top of the stack. Finally, at the end of the trace, check that the stack is empty.

You might want to refer to the STL documentation on the stack and string data types.

The cpp file in your program that tests the main functionalities is called a "driver". For this project, your driver file should be named: driver-proj0.cpp

Input format

Your program should read from standard input. It will write to standard output. This is the way ALL of our projects will be, unless otherwise indicated.

Each input will consist of one trace. Each line of input will contain either a call or a return, followed by a space, followed by the name of the function. The name of the function may not contain whitespace. When comparing two function names to see if they match, case IS important.

Program output

Here are the outputs your program may produce: 
  Valid trace
  Maximum call depth was DEPTH
for valid traces, and the output of 
  Invalid trace at line LINENUMBER
followed by one of the following: 
  Returning from FUNCTION1 instead of FUNCTION2
  Returning from FUNCTION which was not called
  Not all functions returned
followed by a stack trace. The difference between the first two errors is whether any functions are on the stack. See (and use) the executables below for details.

Your program should produce only one of these statements per document. In addition, if the trace is invalid, your program should produce the stack trace (the functions on the stack when the error is detected), one line per function. If there are multiple errors, print only the first one detected (earliest in the input). The terms in all-caps are defined as follows:
  • DEPTH: the number of items on the stack
  • LINENUMBER: the line number of the input (where the error is detected)
  • FUNCTION1, FUNCTION2, FUNCTION: names of functions (FUNCTION1 is the function that is trying to return, while FUNCTION2 is the function on top of the stack)
See below for real examples of program outputs.

Provided code

You should use the .cpp file provided here, modify it appropriately, and upload your solution. You may modify anything you like, but it has a basic structure you can follow.
driver-proj0.cpp

Sample executables

Here are sample executables for you which correctly solve this problem. When you design test cases, you can judge your output against the output from the correct solution. Here is a correct solution in various compiled formats:

For each of these, you need to run them from the command-line (i.e. DOS or bash or Terminal.app). You can't just download them and double-click them to run. Also, for the linux and OSX binaries, after you've downloaded them you need to make sure that they are executable. To do this, from the command line type chmod +x file, where file is the name of the program you downloaded.

If you give a command-line argument to these executables, they will print extra information about how it is processing the input. For example, this will execute the program like normal, redirecting input from a file called my_input.txt: 
  % project0_solution_dos.exe < my_input.txt

But here is the mode of operation that will cause the program to print out what it is doing in more detail: 
  % project0_solution_dos.exe printMore < my_input.txt
The command-line argument doesn't have to be the word "printMore", it can be anything.

Sample input files

Use these sample input files to compare the output of your solution to the correct output. You can get the correct output by running the input through one of the sample executables. You should download these input files to your computer (in other words, don't copy and paste), and use file redirection to redirect the inputs into the sample executable and into your program. You should also use file redirection to capture the outputs from these programs. Don't use copy/paste, and don't type things directly into your program. Please read this for a more complete description of how to test your program, and how to use file redirection..

Please note that you may see the wrong thing if you view these input files in your web browser — it may interpret the text as HTML, when it should show you plain text. Instead, you should download them directly to your computer (e.g. right-click on each link and select the appropriate download option). In general, you should AVOID copy-and-pasting input and output in this class.

Here are sample test cases for you which correctly solve this problem. When you design test cases, you can judge your output against the output from the correct solution. Here is a list of sample test cases:

These are not the only inputs your program must solve; they are merely examples. The professor will have more secret tests, to which you do not have access. Therefore, making your own tests is essential.

Submission

First, test your program carefully.

Second, check your code for style and make sure it follows the guidelines. Once you are sure it passes the coding style guidelines submit your driver on Upload Site and make sure its file name and class is driver-proj0.cpp as specified before.

To summarize, after passing your own tests, you will submit on Upload Site one file containing your aesthetically beautiful driver:
  • driver-proj0.cpp

Final notes

Remember when writing this program to adhere to the coding style guidelines. This is an individual project, so you must work alone. No credit will be given for a solution which does not pass the style guidelines. For instructions on compiling C++ programs or submitting files on Upload Site, read the project submission guidelines.