Your Task: write tests

One common style of software engineering is called “Test-Driven Development” (TDD). With this workflow, you write tests for the intended behavior before writing the code which implements that behavior. This is what you will be doing!

For the purposes of this assignment, you are only doing the first part of TDD: writing the tests. You are provided with the public interfaces for two modules, Article and Wiki, along with several compiled object (.o) files that implement those interfaces. One implementation is correct, while several others contain different bugs. See the “provided files” section below for more details on the starter files and workflow.

Your task is not to modify or debug the implementation. Instead, you will treat the library as a black box and write a comprehensive suite of unit tests that exercise its public API. A good test suite should pass on the correct implementation while exposing the bugs in the buggy implementations.

As you are writing tests, you can run them against our provided implementation of the algorithm. All your unit tests must pass when run on the correct solution — that is the point of automated testing! You will run your tests against some buggy implementations too. Your score is an indicator of the number of buggy programs your unit tests identified.

This assignment emphasizes an important software engineering skill: writing tests based solely on a specification, without relying on implementation details. The real challenge is in thinking through which cases should be tested.

Understanding the Library

Part of the goal of TDD is that you don’t know how the algorithm is implemented, so you aren’t biased by the aspects you believe to be correct – you’re going in blind! That being said, you do need to understand its behavior.

The provided library implements a small Wikipedia-like data structure.

The Article module represents an individual Wikipedia article. An article stores its title along with the outgoing links that appear within the article. The interface provides functions to

  • create and destroy articles,
  • create an article from a link file,
  • determine whether an article contains a particular link, and
  • iterate over an article’s outgoing links.

The Wiki module represents a collection of articles. It provides functions to

  • create and destroy a wiki,
  • add articles,
  • look up articles by title,
  • iterate over an article’s outgoing links through the wiki, and
  • find which articles link to another article.

The behavior of each function is documented in Article.h and Wiki.h. These comments of their preconditions and postconditions are the specification that your tests should verify.

Do not modify either header file.

Black-Box Testing

Notice that the header files intentionally hide the implementation details.

For example, the Article type is declared as

struct Article;
typedef struct Article Article;

and similarly for Wiki.

You cannot access their internal fields directly, and your tests should interact with them only through the functions declared in the headers.

Since you do not have the implementation source code, your tests must be written entirely from the documented behavior of the interface.

The safe_assert test framework

We gave a brief overview of the custom safe_assert test framework in lecture.

You will use this testing framework to write your tests.

All of your tests should be placed in a file named test_suite.c. As a reminder, there should only ever be one “suite” declaration in the file, and there should only be one file for tests. To see an example of what test_suite.c should look like, look at the testing code we included with the HW3 starter code.

You are encouraged to write helper functions if they simplify your tests or reduce duplicated code.

Some of the functions you will be testing involve “link files”, which are just files containing a list of Wikilinks. It’s helpful to test these by making your own .links files using the code you wrote in HW2. Try the following in your HW2 directory:

./get_one_article.sh Kichio_Allen_Arai | ./extract_all_links > Kichio_Allen_Arai.links

You can replace Kichio_Allen_Arai with the slug for whichever page you want to get the .links for. It can be helpful for testing to generate the .links files for several pages that link to each other. For example, Odyssey, Homer, Odysseus, and Penelope all have links between each other.

Provided files, workflow and getting started

Your hw4 folder contains the following files:

  • Article.h Public interface for the Article module.
  • Wiki.h Public interface for the Wiki module.
  • safe_assert.h Unit testing framework.
  • Cosmo_Specialty_Fibers.links Sample article input file.
  • Article.o Correct implementation of the Article module.
  • Wiki.o Correct implementation of the Wiki module.
  • Article_a.o, Wiki_a.o Buggy implementation set A.
  • Article_b.o, Wiki_b.o Buggy implementation set B.
  • Article_c.o, Wiki_c.o Buggy implementation set C.
  • Article_d.o, Wiki_d.o Buggy implementation set D.
  • Makefile Builds your test suite against each implementation

Each buggy implementation contains different bugs. Your goal is to write tests that distinguish the correct implementation from as many buggy implementations as possible.

Building and Running Tests

The provided Makefile builds your test suite against multiple implementations.

To build and run your tests against the correct implementation:

make test_suite
./test_suite

To test against the buggy implementations:

make test_suite_a
./test_suite_a

make test_suite_b
./test_suite_b

make test_suite_c
./test_suite_c

make test_suite_d
./test_suite_d

Or you can run make all to build all of the versions above.

As you develop your tests, they should pass on test_suite (the correct implementation), and fail on one or more of the buggy implementations whenever they expose incorrect behavior.

In past assignments, you have had all of the source code available to you, and were able to try things out incrementally to see what happens. This is not quite true in HW4: we provide no way to edit the implementation. This mimics a true test-driven development workflow, where your goal is to write the tests first. You must come up with test cases using only your mind, the correct implementation (which, in the real word, would also be imagined), and the autograder output. You should rely on the first two more than the autograder, since it will not give you all the information you need to identify the scenario.