Contents


p4-web

EECS 280 Project 4: Web

Project Due Thursday, 13 June 2019, 8pm

In this project, you will build a small web server for an office hours queue. The server will read and write an HTTP subset on stdin and stdout. When you’re done, you’ll have a working web application accessible through your browser.

Table of Contents

Project roadmap

This is a big picture view of how to do this project.

Setup

Use the tutorial from project 1 to get your visual debugger set up. Use this wget link https://eecs280staff.github.io/p4-web/starter-files.tar.gz.

Before setting up your visual debugger, you’ll need to rename each .h.starter file to a .h file.

$ mv List.h.starter List.h

You’ll also need to create these new files and add function stubs.

$ touch api.cpp

These are the executables you’ll use in this project.

If you’re working in a partnership, set up version control for a team.

Review the code structure

The code structure is templated and object-oriented, with a class representing a doubly-linked list. Additionally, the list will be used as a queue.

Implement the main application

Write and test a main() function in api.cpp that runs an office hours queue web site REST API. Use the standard library list, std::list. See the Office hours queue specification section.

Test and implement List

Implement and test a List ADT that works like std::list from the STL. See the Linked list specification section.

Submit

Submit the following files to the autograder.

Introduction

When you browse to a web site like our EECS 280 office hours queue https://lobster.eecs.umich.edu/eecsoh/, your computer makes a request and a server returns a response.

HTTP is the protocol that describes what requests and responses should look like. Both are plain text sent from one computer to another computer through the internet.

Your web browser makes a request when you visit a page. First, it connects to the lobster.eecs.umich.edu server, then requests the /eecsoh/index.html page (“no filename” is a shortcut for index.html).

GET /eecsoh/ HTTP/1.1

The lobster.eecs.umich.edu server responds with plain text in HTML format. Your browser renders the HTML, adding colors, formatting and images.

HTTP/1.1 200 OK

<html>
  <body>
    EECS Office Hours
    ...
  </body>
</html>

In Web 2.0 applications like the EECS 280 office hours queue, the server can also respond to a request with data in JSON format. This data is read by the JavaScript code and displayed on the page.

HTTP/1.1 200 OK

[
    {
        "uniqname": "awdeorio",
        "location": "Table 3"
    },
    {
        "uniqname": "akamil",
        "location": "Table 15"
    }
]

A server that responds to requests with data instead of HTML is called a REST API. REST APIs return data in a machine-readable format like JSON.

In this project, you will build the REST API for an office hours queue.

Office hours queue specification

The top-level application is an office hours queue REST API that reads requests from stdin (cin) and writes responses to stdout (cout). Requests and responses are formatted using a simplified subset of real HTTP.

A queue contains items stored in first-in-first-out order: the first item to be added is also the first one to be removed. Queues are commonly implemented using a linked list. A linked list allows insertion and removal at both ends, allowing items to be added at one end and removed at the other. This is in contrast to a vector, which only allows insertion and removal at one end.

Use the standard library list so you can get started on this project right away. Later, you’ll implement your own linked list that works just like the STL.

The REST API will implement the requests summarized in this table. The following sections provide more detail.

Request Description
GET /api/ Read routes
GET /api/queue/ Read all queue positions
GET /api/queue/head/ Read first queue position
PUT /api/queue/tail/ Create last queue position
DELETE /api/queue/head/ Delete first queue position

Sample browser session

The following is an example of a browser session that adds three people to an empty queue and then retrieves the full queue.

The browser starts by sending a PUT request to the /api/queue/tail path to add a student. The request body includes the student’s uniqname and location.

PUT /api/queue/tail/ HTTP/1.1
Host: localhost
Content-Type: application/json; charset=utf-8
Content-Length: 57

{
    "uniqname": "awdeorio",
    "location": "Table 3"
}

The server returns the following response, indicating success:

HTTP/1.1 201 Created
Content-Type: application/json; charset=utf-8
Content-Length: 76

{
    "location": "Table 3",
    "position": 1,
    "uniqname": "awdeorio"
}

The browser sends a second PUT request to add another student:

PUT /api/queue/tail/ HTTP/1.1
Host: localhost
Content-Type: application/json; charset=utf-8
Content-Length: 56

{
    "uniqname": "akamil",
    "location": "Table 15"
}

The server responds:

HTTP/1.1 201 Created
Content-Type: application/json; charset=utf-8
Content-Length: 75

{
    "location": "Table 15",
    "position": 2,
    "uniqname": "akamil"
}

The browser adds one more student to the queue:

PUT /api/queue/tail/ HTTP/1.1
Host: localhost
Content-Type: application/json; charset=utf-8
Content-Length: 74

{
    "uniqname": "jklooste",
    "location": "Desks behind bookshelves"
}

The server response:

HTTP/1.1 201 Created
Content-Type: application/json; charset=utf-8
Content-Length: 93

{
    "location": "Desks behind bookshelves",
    "position": 3,
    "uniqname": "jklooste"
}

The browser now sends a GET request to the /api/queue/ path to obtain the entire queue:

GET /api/queue/ HTTP/1.1
Host: localhost
Content-Type: application/json; charset=utf-8
Content-Length: 0

The server responds with the contents of the queue in order:

HTTP/1.1 200 OK
Content-Type: application/json; charset=utf-8
Content-Length: 411

{
    "count": 3,
    "results": [
        {
            "location": "Table 3",
            "position": 1,
            "uniqname": "awdeorio"
        },
        {
            "location": "Table 15",
            "position": 2,
            "uniqname": "akamil"
        },
        {
            "location": "Desks behind bookshelves",
            "position": 3,
            "uniqname": "jklooste"
        }
    ]
}

The requests for this example are in the file test02.in, and the responses are in test02.out.correct.

Request format

Every request has the same format. The only parts that change are the method (GET in this example), the path (/api/ in this example), the content length (0 here) and the body (empty here). Note that there is a blank line after Content-Length: 0.

GET /api/ HTTP/1.1
Host: localhost
Content-Type: application/json; charset=utf-8
Content-Length: 0

Response format

Every response has the same format. The only parts that change are the response code (200 in this example), the content length (159) and the body. The body is everything inside the curly braces { ... }.

HTTP/1.1 200 OK
Content-Type: application/json; charset=utf-8
Content-Length: 159

{
    "queue_head_url": "http://localhost/queue/head/",
    "queue_list_url": "http://localhost/queue/",
    "queue_tail_url": "http://localhost/queue/tail/"
}

Your implementation must order key-value pairs alphabetically by key. Use the process in Writing JSON to a stream to ensure that the ordering is correct. The content length for a response is the number of bytes in the body. There must be a newline before the body and after the body, but these do not count towards the content length.

Error handling

Your implementation may assume that requests are properly formatted, and that the HTTP method is one of GET, DELETE, or PUT. However, you must handle the following errors:

If one of the errors above occurs, discard the request and return the following response. Note that there is a blank line after Content-Length: 0.

HTTP/1.1 400 Bad Request
Content-Type: application/json; charset=utf-8
Content-Length: 0

The Content-Length in the HTTP header tells you whether or not there is a body. If the length is nonzero, a body follows. You may assume that the Content-Length of a request is correct.

GET /api/

The /api/ route accepts a GET request and returns a list of URLs supported by this REST API. It always returns the same data. See the examples in Request format and Response format for the input and output for this path.

Run the unit test.

$ make api.exe
$ ./api.exe < test01.in > test01.out
$ diff test01.out test01.out.correct

PUT /api/queue/tail/

The /api/queue/tail/ route accepts a PUT request and creates one new person on the queue. As a simplification, we do not check if a person is already on the queue, thus the same uniqname may appear multiple times.

Example request

PUT /api/queue/tail/ HTTP/1.1
Host: localhost
Content-Type: application/json; charset=utf-8
Content-Length: 57

{
    "uniqname": "jackgood",
    "location": "Table 5"
}

Example response

HTTP/1.1 201 Created
Content-Type: application/json; charset=utf-8
Content-Length: 76

{
    "location": "Table 5",
    "position": 1,
    "uniqname": "jackgood"
}

Run the unit test.

$ make api.exe
$ ./api.exe < test04.in > test04.out
$ diff test04.out test04.out.correct

GET /api/queue/head/

The /api/queue/head route accepts a GET request and returns the person at the head of the queue. Fields are in the order shown by the example, and the person at the head of the queue always has position 1. If the queue is empty, return a 400 error.

Example request

GET /api/queue/head/ HTTP/1.1
Host: localhost
Content-Type: application/json; charset=utf-8
Content-Length: 0

Example response

HTTP/1.1 200 OK
Content-Type: application/json; charset=utf-8
Content-Length: 76

{
    "location": "Table 3",
    "position": 1,
    "uniqname": "awdeorio"
}

Run the unit test.

$ make api.exe
$ ./api.exe < test03.in > test03.out
$ diff test03.out test03.out.correct

GET /api/queue/

The /api/queue/ route accepts a GET request and returns a list of everyone on the queue, including location, position and uniqname in that order. The list is ordered by position, which always starts with 1 for the person currently at the head of the queue.

Example request

GET /api/queue/ HTTP/1.1
Host: localhost
Content-Type: application/json; charset=utf-8
Content-Length: 0

Example response

HTTP/1.1 200 OK
Content-Type: application/json; charset=utf-8
Content-Length: 411

{
    "count": 3,
    "results": [
        {
            "location": "Table 3",
            "position": 1,
            "uniqname": "awdeorio"
        },
        {
            "location": "Table 15",
            "position": 2,
            "uniqname": "akamil"
        },
        {
            "location": "Desks behind bookshelves",
            "position": 3,
            "uniqname": "jklooste"
        }
    ]
}

If the queue is empty, the response should be:

HTTP/1.1 200 OK
Content-Type: application/json; charset=utf-8
Content-Length: 39

{
    "count": 0,
    "results": null
}

Run the unit test.

$ make api.exe
$ ./api.exe < test02.in > test02.out
$ diff test02.out test02.out.correct

DELETE /api/queue/head/

The /api/queue/head/ route accepts a DELETE request and removes the person at the head of the queue.

Example request

DELETE /api/queue/head/ HTTP/1.1
Host: localhost
Content-Type: application/json; charset=utf-8
Content-Length: 0

Example response

HTTP/1.1 204 No Content
Content-Type: application/json; charset=utf-8
Content-Length: 0

If the queue is empty, return a 400 error.

Run the unit test.

$ make api.exe
$ ./api.exe < test05.in > test05.out
$ diff test05.out test05.out.correct

Linked list specification

Implement your doubly linked list in List.h. List.h.starter provides prototypes for each function. Because List is a templated container, function implementations go in List.h. There is no List.cpp.

While the List from lecture was singly linked, this List is doubly linked. This List also contains an iterator interface.

Do not modify the public interface of the List class. Implement a doubly-linked list. No arrays or vectors, etc. Manage memory allocation so that there are no memory leaks.

Compile and run the provided compile check and List tests.

$ make List_compile_check.exe
$ make List_public_test.exe
$ ./List_public_test.exe

Unit tests

You will write and submit tests for your doubly linked list. Your test cases must use the provided unit test framework.

Unit tests should be small and run quickly. You may submit up to 50 TEST() items and the entire test suite must run in less than 5 seconds.

Compile and run your List tests.

$ make List_tests.exe
$ ./List_tests.exe

We will autograde your List unit tests by running them against several buggy instructor solutions. If a test of yours fails for one of those implementations, that is considered a report of a bug in that implementation. This is called mutation testing.

  1. The autograder compiles and runs your test cases with a correct solution. Test cases that pass are considered valid. Tests that fail (i.e. falsely report a bug in the solution) are invalid. The autograder gives you feedback about which test cases are valid/invalid. Since unit tests should be small and run quickly, your whole test suite must finish running in less than 5 seconds.
  2. We have a set of intentionally incorrect implementations that contain bugs. You get points for each of these buggy implementations that your valid tests can catch.
  3. How do you catch the bugs? We compile and run all of your valid test cases against each buggy implementation. If any of these test cases fail (i.e. report a bug), we consider that you have caught the bug and you earn the points for that bug.

Requirements and restrictions

It is our goal for you to gain practice with good C++ code, classes, and dynamic memory.

DO DO NOT
Modify .cpp files and List.h Modify other .h files
For List, make helper member functions private Modify the public interface of List
Use these libraries: <iostream>, <string>, <cassert>, <sstream>, <utility> Use other libraries
Use <list> (and optionally <algorithm>) in api.cpp Use <algorithm>, <list>, or other containers in List.h
#include a library to use its functions Assume that the compiler will find the library for you (some do, some don’t)
Use C++ strings Use C-strings
Send all output to standard out (AKA stdout) by using cout Send any output to standard error (AKA stderr) by using cerr
Pass large structs or classes by reference Pass large structs or classes by value
Pass by const reference when appropriate “I don’t think I’ll modify it …”
Use Valgrind to check for memory errors “It’s probably fine…”

Starter code

You can obtain the starter files by following the instructions in Setup.

File(s) Description
List.h.starter Skeleton List class template header file without function implementations. Rename this file to List.h and then add your function implementations.
List_tests.cpp Add your List unit tests to this file.
List_compile_check.cpp A “does my code compile” test for List.h
List_public_test.cpp A very small test case for List.h.
test01.in
test01.out.correct
test02.in
test02.out.correct
test03.in
test03.out.correct
test04.in
test04.out.correct
test05.in
test05.out.correct		 Simple test cases for the server program.
Makefile A Makefile that has targets for compiling the published test cases and your own tests. Use
$ make test
to compile and run all tests.
json.hpp The library you must use to work with JSON. See Appendix A: Working with JSON for details.
unit_test_framework.h The unit test framework you must use to write your test cases.
server.py Python wrapper script for running the office hours queue server.
index.html HTML for the office hours queue.

Appendix A: Working with JSON

The starter code includes json.hpp, a library for working with JSON in C++. To use the library, place the following at the top of a .cpp file:

#include "json.hpp"
using nlohmann::json;

JSON format

The JSON format is a simple text-based standard for representing structured data. It consists of the following data types:

Constructing a JSON object

The json.hpp library defines the json type to represent a JSON value. The documentation has an example of constructing a json object in C++ code. We summarize the example here. Suppose we wanted to construct the following JSON object:

{
  "pi": 3.141,
  "happy": true,
  "name": "Niels",
  "nothing": null,
  "a_list": [1, 0, 2],
  "an_object": {
    "currency": "USD",
    "value": 42.99
  }
}

This object has the following key-value pairs:

We can create the JSON object in C++ as follows:

json j2;
j2["pi"] = 3.141;
j2["happy"] = true;
j2["name"] = "Niels";
j2["nothing"] = json();
j2["a_list"] = {1, 0, 2};
j2["an_object"] = {
  {"currency", "USD"},
  {"value", 42.99}
};

The value for a particular key can be read using the same subscript syntax:

cout << j2["pi"] << endl;      // prints 3.141
cout << j2["answer"] << endl;  // prints {"everything":42}
j2["tau"] = 6.283;             // inserts "tau":6.283 into j2
cout << j2["tau"] << endl;     // prints 6.283

A JSON object can also be created with an initializer list, as in:

j2["an_object"] = {
  {"currency", "USD"},
  {"value", 42.99}
};

Each element of the initializer list must be another initializer list, containing both a key and a value. In this example, the key "currency" is associated with the string "USD", and the key "value" is associated with the number 42.99.

The following creates the same object as j2 above using initializer lists:

json j2 = {
  {"pi", 3.141},
  {"happy", true},
  {"name", "Niels"},
  {"nothing", nullptr},
  {"a_list", {1, 0, 2}},
  {"an_object", {
      {"currency", "USD"},
      {"value", 42.99}
    }
  }
};

JSON lists

Build a JSON list using push_back().

json output;

json j4 = {
  {"happy", true},
  {"pi", 3.141}
};
output.push_back(j4);

json j5 = {
  {"happy", true},
  {"pi", 3.14159265359}
};
output.push_back(j5);

The resulting JSON is

[
    {
        "happy": true,
        "pi": 3.141
    },
    {
        "happy": true,
        "pi": 3.14159265359
    }
]

Reading JSON from a stream

JSON-formatted data can be read from a stream into a json object using operator>>:

json j3;
cin >> j3;

Writing JSON to a stream

A json object can be inserted directly into a stream. However, it does not get “pretty printed” with proper indentation. Instead, use the dump() member function to convert a json object into a string and then insert the string into a stream:

json j4 = {
  {"happy", true},
  {"pi", 3.141}
};
string str2 = j4.dump(4);  // dump with indentation using 4 spaces
cout << str2 << endl;      // print the dumped string

This results in the following:

{
    "happy": true,
    "pi": 3.141
}

The key-value pairs are ordered alphabetically by key.

The content length for a request or response can be computed from the length of the dumped string:

size_t content_length = str2.length();

Appendix B: Real web server

The REST API you built works in a real network. We’ve provided a Python wrapper script with the networking code.

Build and start the server. You might need to install Python 3 with brew install python3 (macOS) or apt-get install python3 (WSL or Linux).

$ make api.exe
$ python3 server.py
Starting server on localhost:8000

In a web browser, navigate to http://localhost:8000/index.html. You should see a web page. A shortcut is http://localhost:8000.

Now try http://localhost:8000/api/. You should see JSON data.

Your browser is sending a GET request over the network. Let’s try it using the command line using a second terminal.

$ curl localhost:8000/api/
{
    "queue_head_url": "http://localhost/queue/head/",
    "queue_list_url": "http://localhost/queue/",
    "queue_tail_url": "http://localhost/queue/tail/"
}

The server.py script listens for incoming network requests. If the client request path starts with /api, it copies the request to the stdin of api.exe and copies the stdout of api.exe back to the client. Otherwise, server.py copies a file to the client over the network (e.g., index.html).

Appendix C: What’s in a typename?

You saw the use of typename for declaring templates. When compiling your project, you may get the following kind of error:

./List_tests.cpp:94:8: error: missing 'typename' prior to dependent type name 'List<T>::Iterator'
List<T>::Iterator i;
^~~~~~~

If you see an error message that talks about missing ‘typename’ prior to dependent type name, simply stick in the keyword “typename” before the type declaration. In the instance above, it would become:

typename List<T>::Iterator i;

The same thing would apply if you declared a loop variable. For example:

for (List<T>::Iterator i; /*...*/)

may need to become (if you get an error from the compiler):

for (typename List<T>::Iterator i; /*...*/)

Discussion of dependent types and why we have to insert the keyword typename is beyond the scope of this course (the reason is quite subtle and deep). If you want to see some explanation, see this article:

http://pages.cs.wisc.edu/~driscoll/typename.html

Appendix D: Project 4 Coding Practices Checklist

The following are coding practices you should adhere to when implementing the project. Adhering to these guidelines will make your life easier and improve the staff’s ability to help you in office hours. You do not have to submit this checklist.

General code quality:

Test case quality:

Project-specific quality: