lab_inheritance - CS 225 Fall 2017: Data Structures

Assignment Description

In this lab you will get experience with some of the implementation issues and conceptual details of inheritance. Inheritance is a mechanism for increasing the reusability and reliability of C++ code. It is worth mentioning that inheritance is a characteristic of all object oriented programming languages. Our goal is to give you a glimpse of the functionality of inheritance, so that you can make informed design decisions in the future. Please read through the entire lab before you begin. The compilation notes at the bottom will tell you how to organize your development files.

Checking out the code

After reading this lab specification, the first task is to check out the provided code from the class repository. To check out your files for this lab, type the following into the command console:

svn up

This will create a new directory in your working directory called lab_inheritance.

The code for this activity resides in the lab_inheritance/ directory. Get there by typing this in your working directory:

cd lab_inheritance/

You will only need to modify the following files:

shape.{cpp,h}
circle.{cpp,h}
truck.{cpp,h}
flower.{cpp,h}
drawable.h

Class Hierarchy

To help us understand class hierarchies better here is an example of a simple class hierarchy showing that a Dog is a Animal.

The code would look something like the following:

class Animal {
   public:
      string name;

      virtual void speak() = 0;
      /* The = 0 at the end of the method means that the method is a pure virtual method
       * meaning that it does not have an implementation and it delegates the task
       * of implementing the method to the classes that is derived from it */
};

class Dog : public Animal {
   public:
      string breed;

      /* Dog inherits speak from Animal */
      void speak();

};

void Dog::speak() {
    cout << "Woof Woof" << endl;
}

In this example Animals have a name and can speak but since speak is a pure virtual method we CANNOT construct an Animal by itself. That is Animal is an abstract class and it can only be constructed by one of its derived classes. For example, a Dog is a derived class of Animal. This means that a Dog is a Animal, and, therefore, it inherits a name and a speak method from Animal. However, since the Animal’s speak does not have an implementation, Dog must implement the speak method.

Here is an example of how we could use a Dog object:

Dog* d = new Dog();

/* Like usual we can access all the public methods and member variables of a
 * Dog */
d->breed;

/* But now since a Dog is an Animal we can also do this too */
d->name;     // inherited from Animal
d->speak();  // inherited from Animal and since it is a Dog speak() will print
             // "Woof Woof"

/* Additionally we can treat our Dog only like an Animal like this */
Animal* a = d;

/* But now we can only do the following */
a->name;
a->speak();  // Still prints "Woof Woof" because speak is a virtual method.

a->breed     // ERROR! This will NOT work since we perceive it as an Animal now

/* Additionally, if we try to have our Animal pointer point back to a Dog
 * pointer this will cause a problem because an Animal Is NOT A Dog. */
Dog* d2 = a;  // ERROR!  Animal Is NOT A Dog

/* Furthermore, since Animal is abstract and has a pure virtual method
 * we CANNOT construct one! */
Animal a2;  // ERROR! Animal is an abstract class

Now that we can understand a simple class hierarchy, let’s look at a more complex one. Here is a diagram depicting the class hierarchy that is used in this lab. (Note: This diagram is missing some information, e.g. methods, member variables, etc.., for demonstration purposes)

This means everything is a Drawable and will have a draw method. Code like the following is perfectly acceptable:

Drawable* triangle  = new Triangle(....);
Drawable* circle    = new Circle(...);
Drawable* rectangle = new Rectangle(....);
Drawable* truck     = new Truck(...);
Drawable* flower    = new Flower(....);

/* Now the only thing we can use on triangle, circle, rectangle, truck, and
 * flower is draw but what gets drawn will change depending on what type the
 * pointer is actually pointing to. This is called polymorphism, the behavior
 * changes depending on the actual type of the object being pointed to. */

PNG canvas;
triangle->draw(&canvas);   // draws a Triangle even though triangle is a Drawable*
circle->draw(&canvas);     // draws a Circle even though circle is a Drawable*
rectangle->draw(&canvas);  // draws a Rectangle even though rectangle is a Drawable*
truck->draw(&canvas);      // draws a Truck even though truck is a Drawable*
flower->draw(&canvas);     // draws a Flower even though flower is a Drawable*

Look at main.cpp for a working example executable in action. main.cpp gets compiled and linked into an executable named lab_inheritance. Follow the instructions below to build, run, and view the output:

The Makefile provided for this MP will create two useful executables when you run make. It will generate lab_inheritance and lab_inheritance-asan. So when you want to test a specific part of your MP you can use either of those. For example when you run

./lab_inheritance

You could also run it as:

./lab_inheritance-asan

if you want to test it with Address Sanitizer, and to check for memory leaks:

./lab_inheritance-asan

Additionally you’re free to run Valgrind on the normal executable:

valgrind --leak-check=full ./lab_inheritance

This lab will use all of these objects in interesting ways but as you will quickly see they are not working the way the should. Your objective for this lab is to go through the 5 test executables and fix the code to work correctly by modifying how the classes in the hierarchy declare and implement their methods.

Background on ASAN

ASAN checks for a wide variety of things. Here are some things that may pop up when debugging:

Out-of-bounds access to heap, stack, and globals. This error occurs when you allocate some memory and then try to access a region outside your allocated space.
Example
```
int * arr = new int[100];
return arr[100];
```
Use-after-free (dangling pointer reference). This error occurs when you try to use memory you have already freed. It is especially helpful when you have several pointers referring to the same memory.
Example
```
int * arr = new int[100];
delete [] arr;
return arr[5]; //NOPE
```
Heap buffer overflow. This error occurs when you go out of bounds within an array created on the heap.
Example
```
int * arr = new int[100];
arr[0] = 0;
int ret = arr[5 + 100]; //NOPE
delete [] arr;
return ret;
```
Stack buffer overflow. This error occurs when you go out of bounds within an array created on the stack.
Example
```
int arr[100];
arr[1] = 0;
arr[5 + 100]; //NOPE
```
Use after return. This error occurs when you return a stack variable at the end of a function and try to use it after it’s out of scope.
Example
```
int * arr1;
void func() {
   int arr2[100];
   arr1 = arr2;
}
int main() {
   func();
   return arr1[10]; //NOPE
}
```
Double free or Invalid free. Double free occus when you free an heap object twice. Invalid free’s occur when you free a non-heap object.
Example
```
int * arr = new int[100];
delete [] arr;
delete [] arr; //NOPE
```
```
int arr[100];
delete [] arr; //NOPE
```
Memory leak detection. ASAN can detect three sources of memory leakage.
- A still reachable block happens when you forget to delete an object, the pointer to the object still exists, and the memory for object is still allocated.
- A lost block is a little tricky. A pointer to some part of the block of memory still exists, but it is not clear whether it is pointing to the block or is independent of it.
- A definitely lost block occurs when the block is not deleted but no pointer to it is found.

Fixing Memory Bugs (using ASAN)

Before fixing the bugs, you’ll need to compile the code. ASAN terminates the program upon the first invalid memory access. So, if you have an invalid memory access, you’ll have to fix it before moving on to other errors. This incremental procedure should help you step through memory bugs one at a time.

To compile the code for the lab, run

make

(In this and future assignments, make will produce 2 versions of each executable: the “normal” version and a version that has ASAN enabled.)

This will create two executable files named assignment and assignment-asan. Run the ASAN version with

./assignment-asan

which will check for both memory errors and leaks.

Once you have fixed all the memory errors, you can test your program output using the details described below.

Using Valgrind

In the past, Valgrind has been a useful tool to detect memory errors and memory leaks. Valgrind does what ASAN does but because it doesn’t make the memory checking code into the binary executable, it has to interpret the code during runtime. Therefore, Valgrind can be slower than ASAN – however, it still has some advantages! Nonetheless, if you are interested in how it works, you can read on about Valgrind. NOTE: You cannot used Valgrind and ASAN at the same time. Make sure to run it only on the non-ASAN executable!

Background on Valgrind

Valgrind is a free utility for memory debugging, memory leak detection, and profiling. It runs only on Linux systems. To prepare your project to be examined by Valgrind you need to compile and to link it with the debug options -g and -O0. Make sure your Makefile is using these options when compiling. In order to test your program with Valgrind you should use the following command:

valgrind ./yourprogram

To instruct valgrind to also check for memory leaks, run:

valgrind --leak-check=full ./yourprogram

You will see a report about all found mistakes or inconsistencies. Each row of the report starts with the process ID (the process ID is a number assigned by the operating system to a running program). Each error has a description, a stack trace (showing where the error occurred), and other data about the error. It is important to eliminate errors in the order that they occur during execution, since a single error early could cause others later on.

Here is a list of some of the errors that Valgrind can detect and report. (Note that not all of these errors are present in the exercise code.)

Invalid read/write errors. This error will happen when your code reads or writes to a memory address which you did not allocate. Sometimes this error occurs when an array is indexed beyond its boundary, which is referred to as an “overrun” error. Unfortunately, Valgrind is unable to check for locally-allocated arrays (i.e., those that are on the stack.) Overrun checking is only performed for dynamic memory.
Example
```
int * arr = new int[6];
arr[10] = -5;
```
Use of an uninitialized value. This type of error will occur when your code uses a declared variable before any kind of explicit assignment is made to the variable.
Example
```
int x;
cout << x << endl;
```
Invalid free error. This occurs when your code attempts to delete allocated memory twice, or delete memory that was not allocated with new.
Example
```
int * x = new int;
delete x;
delete x;
```
Mismatched free() / delete / delete []. Valgrind keeps track of the method your code uses when allocating memory. If it is deallocated with different method, you will be notified about the error.
Example
```
int * x = new int[6];
delete x;
```
Memory leak detection. Valgrind can detect three sources of memory leakage.
- A still reachable block happens when you forget to delete an object, the pointer to the object still exists, and the memory for object is still allocated.
  Example
```
int * x = new int[6]; // no corresponding delete x
```
- A lost block is a little tricky. A pointer to some part of the block of memory still exists, but it is not clear whether it is pointing to the block or is independent of it.
- A definitely lost block occurs when the block is not deleted but no pointer to it is found.

More information about the Valgrind utility can be found at the following links:

Fixing Memory Bugs (using Valgrind)

Before fixing the bugs, you’ll need to compile the code:

make

This will create an executable file called assignment, which you can run with:

./assignment

You can then run Valgrind on assignment:

valgrind ./assignment

This works fine for fixing the memory errors, however, to fix the memory leaks, you’ll need to add --leak-check=full before ./allocate:

valgrind --leak-check=full ./assignment

Once you have fixed all the Valgrind errors, you can test your program output following the directions below.

Exercise 1: Fix the Virtual Methods

Please build and run test_virtual:

make test_virtual test_virtual-asan # make test_virtual
./test_virtual-asan                 # run test_virtual with asan
valgrind ./test_virtual             # run test_virtual with valgrind

As you will see when you run test_virtual, the output will say:

The Perimeters are NOT the same.
The Areas are NOT the same.

However, if you look closely at the code they should be the same because both of the pointers in test_virtual.cpp point to the same object!

Exercise

Investigate and fix the code so that the areas and the perimeters are the same.
To fix this problem you should only need to modify shape.cpp and/or shape.h.

Exercise 2: Fix the Destructor

Please build and run test_destructor:

make test_destructor test_destructor-asan    # make test_destructor
valgrind --leak-check=full ./test_destructor # run test_destructor in valgrind
./test_destructor-asan                       # test it with Address Sanitizer and check for leaks

When you run test_destructor in Valgrind or ASAN you will see that test_destructor is leaking memory. However, if you look closely, Triangle does have a valid destructor and it is being called in test_destructor!

Exercise

Investigate and fix the code so that the there is no more memory leak inside of test_destructor.
To fix this problem you should only need to modify drawable.h and shape.h.

Exercise 3: Fix the Constructor

Please build and run test_constructor:

make test_constructor # make test_constructor
./test_constructor    # run test_constructor

When you run test_constructor you will see the following output:

Circle's color is NOT correct!
Circle's center is NOT correct!

If you look closely, we are constructing a Circle with a valid center and color. However, when it is being drawn and when we ask for the Circle’s center and color they are not the same!

Exercise

Investigate and fix the code so that the Circle is being constructed with the proper center and color.
To fix this problem you should only need to modify circle.cpp
The correct test_constructor.png should look like the following:

Exercise 4: Fix the Pure Virtual Method

Please build and run test_pure_virtual.

make test_pure_virtual # make test_pure_virtual
./test_pure_virtual    # run test_pure_virtual

When you try to make test_pure_virtual you will see that it does not compile.

However, if you look at the truck.{h,cpp} it is a fully featured class! Why is it not compiling?

Exercise

Investigate and fix the code so that test_pure_virtual compiles, runs, and outputs a Truck.
To fix this problem you should only need to modify truck.h and truck.cpp.
In order to have the Truck draw properly you will first need to have Exercise 3 completed.
The correct test_pure_virtual.png should look like the following:

Exercise 5: Fix the Slicing

Please build and run test_slicing with:

make test_slicing # make test_slicing
./test_slicing    # run test_slicing

After you run test_slicing open up its output test_slicing.png. You will see that a Flower has NOT been drawn. For some reason just a bunch of X’s has been drawn and a red circle.

If you look at flower.h and flower.cpp, we have all of the proper member variables set up. However, when we try to draw them they are drawn incorrectly.

Exercise

Investigate and fix the code so that test_slicing outputs a Flower.
To fix this problem you should only need to modify flower.h and flower.cpp.
You must use polymorphism!
The correct test_slicing.png output should look like the following:

Committing Your Code

To commit your code, simply run:

svn ci -m "lab_inheritance submission"

Testing Your Code

Run the Catch tests as follows (this requires your code to compile when run simply as make):

make test
./test

Grading Information

The following files are used to grade this assignment:

shape.cpp
shape.h
circle.cpp
circle.h
truck.cpp
truck.h
flower.cpp
flower.h
drawable.h

lab_inheritance Insidious Inheritance

Assignment Description

Checking out the code

Class Hierarchy

Background on ASAN

Fixing Memory Bugs (using ASAN)

Using Valgrind

Background on Valgrind

Fixing Memory Bugs (using Valgrind)

Exercise 1: Fix the Virtual Methods

Exercise 2: Fix the Destructor

Exercise 3: Fix the Constructor

Exercise 4: Fix the Pure Virtual Method

Exercise 5: Fix the Slicing

Committing Your Code

Testing Your Code

Grading Information