6.031
6.031 — Software Construction
Fall 2018

Problem Set 4: Memory Scramble

Alpha due
Tuesday, November 13, 2018, 10:00 pm
Because this deadline is extended due to the holiday, you may take at most 1 slack day on PS4 alpha.
Code reviews due
Friday, November 16, 2018, 11:00 am
Beta due
Monday, November 19, 2018, 10:00 pm

The purpose of this problem set is to explore multithreaded programming with a shared mutable data type, which you will protect using different thread safety strategies; and to practice writing a client/server system.

Design Freedom and Restrictions

On this problem set, you have substantial design freedom.

Pay attention to the PS4 instructions in the provided code. You must satisfy the provided specifications for certain methods in Board, TextServer, and WebServer, and you should not change the code in ServerMain. You may rewrite or delete any of the other provided code, add new classes and methods, etc.

Take care that the coordinate system of your game board matches the specifications: (row, column) coordinates start at (1, 1) in the top left corner, increasing vertically downwards and horizontally to the right.

Your code will be tested against the text and HTTP protocols specified below. It is your responsibility to examine Didit feedback and make sure your code compiles and runs for grading, but you must do your own testing to ensure correctness.

Get the code

To get started,

  1. Ask Didit to create a remote psets/ps4 repository for you on GitHub.mit.

  2. Clone the repo. Find the ssh:// URL at the top of your Didit assignment page and run: git clone «URL»

  3. Import into Eclipse. See Problem Set 0 for if you need a refresher on how to create, clone, or import your repository.

Overview

On this problem set, you will build a networked multiplayer version of Memory, a.k.a. Concentration, the game in which you turn over face-down cards and try to find matching pairs. Our version will have players turning over cards simultaneously, rather than taking turns. We’ll call it Memory Scramble.

Problem 1: you will design and implement one or more ADTs for this game, without thread safety.

Problem 2: you will implement a game server that handles a single client at a time using a text protocol over network sockets.

Problem 3: you will revise your system to handle multiple simultaneous clients using a threadsafe game board.

Problems 4 & 5: you will design and implement watching for changes to the board, and implement a HTTP server. When you’re done, you can play Memory Scramble in your browser.

Iterative Development Recommendation

Both automatic and manual grading for the alpha will focus on your text server without concurrency.

First, do problems 1 & 2 without considering concurrency: don’t make your Board or other ADTs threadsafe, and don’t handle multiple concurrent connections in your text server. Implement the gameplay rules specified below by writing tests, choosing data structures, and writing code. Consider the abstraction functions and rep invariants of all your data types.

Then, revise your work in problem 3 to make your system safe for concurrency. Revise your choice of ADT operations based on the need for atomic actions, revise your implementation using threadsafe data structures and a technique for blocking calls, and write your thread safety arguments.

Finally, go on to problems 4 & 5.

Game board · Gameplay rules · Example game transcript · Playing over text socket · Playing on the web

Game board

The Memory Scramble game board has a grid of spaces. Each space starts with a card. As cards are matched and removed, spaces become empty.

A card in our game is a non-empty case-sensitive string of non-whitespace non-newline characters. This allows “pictures” like Hello and pictures like 🌈 by using emoji characters. For example:

👁 💖 M √-1 ☕️

All cards start face down. Players will turn them face up, and the cards will either turn face down again (if the player turned over cards that don’t match) or be removed from the board (if they do match).

A game may start with either…

A randomly-generated board, where the user specifies dimensions and a set of cards, and those cards are distributed randomly and as evenly as possible. For example:

A random 3×3 board with
{
🌈, 🦄
}
 → 
🦄🦄🌈
🌈🌈🦄
🌈🦄🌈

Or, a board loaded from a file. Here is the formal grammar for board files:

BOARD_FILE ::= ROW NEWLINE COLUMN NEWLINE (CARD NEWLINE)+

CARD ::= [^\s\n\r]+
ROW ::= INT
COLUMN ::= INT
INT ::= [0-9]+
NEWLINE ::= "\n" | "\r" "\n"?

In BOARD_FILE, ROW is the number of rows, COLUMN is the number of columns, and the cards are listed reading across each row, starting with the top row.

For example, the board above would be specified in a file as:

3↵
3↵
🦄↵
🦄↵
🌈↵
🌈↵
🌈↵
🦄↵
🌈↵
🦄↵
🌈↵

In this example, is used to show newlines. This board is provided in the boards folder of the problem set as perfect.txt.

A valid board file must have exactly ROW×COLUMN newline-terminated CARD lines.

Gameplay rules

Multiple players manipulate the cards on the board concurrently. They play the game by trying to turn over pairs of identical cards. Here’s an informal summary of the rules:

1
When a player turns over a first card in a pair, they control that card. If someone else already controls it, they block until they can take control.
2
When the player turns over a second card, if the cards match, the player keeps control of them; otherwise, the player gives up control. The cards stay face up for now.
3
When the player makes their next move, if their previous cards matched, those cards are removed from the board; otherwise, if no one controls them, they turn face down.

Complete rules

First card: a player tries to turn over a first card by identifying a space on the board…

1-A
If there is no card there (the player identified an empty space, perhaps because the card was just removed by another player), the operation fails.
1-B
If the card is face down, it turns face up (all players can now see it) and the player controls that card.
1-C
If the card is already face up, but not controlled by another player, then it remains face up, and the player controls the card.
1-D
And if the card is face up and controlled by another player, the operation blocks. The player will contend with other players to take control of the card at the next opportunity.

Second card: once a player has turned over a first card, they can try to turn over a second card…

2-A
If there is no card there, the operation fails. The player also relinquishes control of their first card (but it remains face up for now).
2-B
If the card is face up and controlled by a player (another player or themselves), the operation fails. To avoid deadlocks, the operation does not block. The player also relinquishes control of their first card (but it remains face up for now).
If the card is face down, or if the card is face up but not controlled by a player, then:
2-C
If it is face down, it turns face up.
2-D
If the two cards are the same, that’s a successful match! The player keeps control of both cards (and they remain face up on the board for now).
2-E
If they are not the same, the player relinquishes control of both cards (again, they remain face up for now).

While one player is blocked turning over a first card, other players continue to play normally. They are not blocked, unless they also try to turn over a first card controlled by another player.

After trying to turn over a second card, successfully or not, the player will try again to turn over a first card. When they do that, before following the rules above, they finish their previous play:

3-A
If they had turned over a matching pair, they control both cards. Now, those cards are removed from the board, and they relinquish control of them. Score-keeping is not specified as part of the game.
3-B
Otherwise, they had turned over one or two non-matching cards, and relinquished control but left them face up on the board. Now, for each of those card(s), if the card is still on the board, currently face up, and currently not controlled by another player, the card is turned face down.

If the player never tries to turn over a new first card, then then the steps of 3-A/B never occur.

Example game transcript

❤️💛❤️
💚💛💚
💜💜💜

We start with a 3×3 grid of face-down cards and 3 players: Alice, Bob, and Charlie.

Alice turns over the top left card. She controls that card for the moment (rule 1-B).

❤️💛❤️
💚💛💚
💜💜💜
❤️💛❤️
💚💛💚
💜💜💜

Bob and Charlie also try to turn over that card at the same time.

Both are now blocked waiting for the chance to control it (1-D).

Alice turns over the bottom right card (2-C). It doesn’t match.

Alice no longer controls any cards, but they stay face up for now (2-E).

Either Bob or Charlie will now get to control the top left card.

❤️💛❤️
💚💛💚
💜💜💜
❤️💛❤️
💚💛💚
💜💜💜

Bob becomes the controller of that red heart card (1-C).

Alice hasn’t made another move, so the purple heart is still face up.

Charlie is still waiting.

Alice goes ahead and turns over a new first card, a yellow heart at the center of the board.

The red heart is controlled by Bob, so it stays face up (3-B).

But the purple heart isn’t controlled, so it turns face down (same 3-B).

❤️💛❤️
💚💛💚
💜💜💜
❤️💛❤️
💚💛💚
💜💜💜

While Alice is thinking about her second card, Bob turns over the top right card.

His first and second cards are a match!

He keeps control of them for now (2-D). Charlie is still blocked.

Bob turns over a new first card, a green heart on the left side.

His matched red hearts are removed from the board (3-A).

💛
💚💛💚
💜💜💜
💛
💚💛💚
💜💜💜

Charlie finally gets a chance at the top left card — but it’s gone (1-A).

Charlie is now ready to turn over a new first card.

Alice and Bob each control one card and will try to turn over a matching second.

Playing over text socket

To support playing on a memory game server over the network, we’ll define two protocols for client/server memory games: a text protocol (played using a client we provide) and a HTTP protocol (played in the web browser).

First, the text protocol to use over a plain socket connection…

Each connection to the server is considered a single player. If the client disconnects from the server and reconnects, they are now playing as a different player.

Here is the formal grammar for requests and responses:

REQUEST ::= LOOK_REQUEST | FLIP_REQUEST | QUIT_REQUEST
LOOK_REQUEST ::= "look" NEWLINE
FLIP_REQUEST ::= "flip" SPACE ROW SPACE COLUMN NEWLINE
QUIT_REQUEST ::= "quit" NEWLINE

RESPONSE ::= ROW SPACE COLUMN SPACE SPOT (SPACE SPOT)* NEWLINE

SPOT ::= "*" | "_" | CARD
CARD ::= ">"? [^\s\n\r]+
ROW ::= INT
COLUMN ::= INT
INT ::= [0-9]+
SPACE ::= " "
NEWLINE ::= "\n" | "\r" "\n"?

Rows and columns on the board are indexed starting from 1 at the top left.

For both LOOK_REQUEST and FLIP_REQUEST requests, the server RESPONSE describes the game board. ROW is the number of rows, COLUMN is the number of columns, and subsequent SPOT elements describe the cards, reading across each row, starting with the top row.

To the left of each card is a > if the player who sent the request controls that card.

Face-down cards are represented by *, and missing cards by _.

Cards are separated by spaces.

A valid RESPONSE must have exactly ROW×COLUMN space-separated SPOT elements.

This protocol works best when none of the cards are * or _, since those symbols have special meaning.

We have provided a simple client that does basic parsing and display of RESPONSE boards. You can also speak the protocol directly with Telnet (depending on your terminal or Telnet client, emoji may not work ☹️).

For example:

3␣3␣A␣*␣*␣_␣>B␣_␣*␣*␣C↵
AAA
B
CCC

In this example, is used to show blank spaces and to show newlines.

There are no cards at (2,1) or (2,3).

The cards at (1,1), (2,2) and (3,3) are face up, and the player receiving this message controls the B card at (2,2).

look

The server responds with the current board.

flip row column

The server tries to flip over the card at (row, column) for the player, following the rules above, and responds with the current board after trying to flip.

Since the response is sent after the flip, this request may block waiting for another player to relinquish control of a card. When the blocking operation completes, the response is sent, and subsequent requests from the client are processed.

quit

The server takes no action, sends no response, and closes the connection with the client.

Any cards that player controls will, unfortunately, never be relinquished.

Playing on the web

The second protocol will work over standard HTTP, which means every communication is a client request with a server response. All of our client requests will be GET requests for a particular path, and all server responses will be plain text.

In this protocol, requests include a player ID chosen by the client. All requests with the same player ID are the actions of a single player.

Here is the formal grammar for requests and responses:

REQUEST ::= "/look/" PLAYER
          | "/flip/" PLAYER "/" ROW "," COLUMN
          | "/watch/" PLAYER

RESPONSE ::= ROW NEWLINE COLUMN NEWLINE (SPOT NEWLINE)+

PLAYER ::= [\w]+
SPOT ::= "none" | "down" | "up " CARD | "my " CARD
CARD ::= [^\s\n\r]+
ROW ::= INT
COLUMN ::= INT
INT ::= [0-9]+
NEWLINE ::= "\n" | "\r" "\n"?

Rows and columns on the board are indexed starting from 1 at the top left.

For all requests, the server responds with the current board. In the response, ROW is the number of rows, COLUMN is the number of columns, and the cards are listed reading across each row, starting with the top row.

none indicates no card in that location, down is a face-down card, up indicates a face-up card controlled by another player (or by no one), and my is a face-up card controlled by the player who sent the request.

For example, the same board above for the same player:

3↵
3↵
up␣A↵
down↵
down↵
none↵
my␣B↵
none↵
down↵
down↵
up␣C↵
AAA
B
CCC

Again, is used to show blank spaces and to show newlines.

Unlike the text server protocol, this format does not suffer from ambiguity for * or _ cards.

The text protocol used newlines to separate whole messages, while this one (like the board file format) uses newlines to separate tokens within a single message.

GET /look/player

The server responds with the current board.

GET /flip/player/row,column

The server tries to flip over the card at (row, column) for the player, following the rules above, and responds with the current board after trying to flip.

Since the response is sent after the flip, this request may block waiting for another player to relinquish control of a card.

Sending concurrent GET /flip/... requests while the player is waiting for a blocked flip to complete is not allowed.

GET /watch/player

The server does not immediately respond. Instead, this requests blocks, and the server waits until the next time the board changes. At that point, it responds with the current board.

A change is defined as any cards turning face up or face down or being removed from the board.

A GET /watch/player request must block until such a change occurs. When there is no change in the state of the cards — for example, if a player tries to turn over an empty space, or if a player takes control or relinquishes control of a card but it does not turn face up or down — pending watch requests must continue to block.

While a GET /watch/player request is blocked, the player may send other requests, and they will be processed normally. For example, a concurrent GET /look/player request must not block.


Problem 1: Game board

Specify, test, and implement a mutable Board ADT to represent the Memory Scramble game board. It may be useful to define other ADTs as well.

Board.java defines two static factory methods for creating new boards that you must support:

parseFromFile(filename): creates a board by parsing a file in the format described above

generateRandom(rows,columns,cards): generates a new rows-×-columns—size board filled randomly with the given cards in as equal numbers as possible

Remember to include: a specification for every class and every method you write; abstraction functions and rep invariants, and checkRep and toString; and safety from rep exposure arguments.

Iterative development recommendation: implement a single-threaded board first, and connect it to a single-threaded text server in Problem 2. The alpha grading will focus on your text server without concurrency. Then revise for thread safety and correct behavior with concurrent players in Problem 3.

For parsing board files, a parser generator (like ParserLib) is more complexity than you need. Reminder: Problem Set 2 suggested several ways to read in files.

To implement player identity:

  • Each player might use a different identifier, e.g. a unique number.
  • Each player might be represented by a different object, e.g. a Player ADT. Some of the player’s state might be stored in the Player object, or the Board might store all the state.

You decide which actions are atomic, since the rules do not specify. In rule 3-B, for example, turning the two cards back over might be a single action — where no other player can see or manipulate the intermediate board — or two separate actions. But the board must never reach an inconsistent state, such as two players controlling the same card, or having a face-down card that a player still controls.

To implement blocking according to the gameplay rules, synchronized blocks alone may not be enough:

  • Threads might wait for a message from a blocking queue.

  • You might use Object methods wait() (to block) and notifyAll() (to wake up blocked threads). These calls must be inside a synchronized block. When waiting threads wake up, only one will win the race for the lock, similar to how only one waiting consumer can take a single message from a blocking queue. wait() must be used in a condition-checking loop. See, e.g., Guarded Blocks in The Java Tutorials for an example.

  • Or you might use another tool from the java.util.concurrent package.

When a player is waiting, the thread must be blocked waiting for an event, it must not be busy-waiting (see the Reordering example in Concurrency).

For keeping track of which players control cards, or matched (or mismatched) pairs that need to be removed (or turned face down), threadsafe data structures may be useful:

Tips for reading and writing

BufferedReader.readLine() reads a line of text from an input stream. Its definition of a line (terminated by \n, \r, or \r\n) matches the NEWLINE productions in our grammars. You can wrap a BufferedReader around both InputStreamReader and FileReader objects.

PrintWriter.println() prints formatted text to an output stream, and terminates the current line by writing the line separator string. It always writes a line separator, even if the input string already ends with one. The line separator is \n on *nix systems and \r\n on Windows, both of which are allowed by the NEWLINE productions in our grammars. You can wrap a PrintWriter around a Writer or OutputStream objects.

Simulating a game

In SimulationMain.java we have provided skeleton code for a program that simulates one player interacting with a board, randomly flipping over several cards.

You should be able to fill in the blanks in that main() method and run simulated single-player Memory Scramble games.

Problem 2: Text server

In TextServer.java we have provided skeleton code for a single-threaded server that accepts connections from one client at a time:

  • The constructor makes a new ServerSocket for this TextServer.
  • The serve() method waits for a new client, calls handleConnection() to exchange messages with that client, then waits for a new client again.
  • The handleRequest() method is called in handleConnection() for each request. It has example code to handle requests that begin with "hello". We’ll say that a valid hello request has a single word (matching the regex \w+) that the server should greet.
  • "hello" requests are not part of our protocol, and you should replace the example code once you understand it.

In the provided TextServerTest.java file:

  • testHelloValid tests the behavior of the provided server on the valid request "hello world".
  • testHelloInvalid tests its behavior on the invalid request "hello 🌍".

To see the example code running, use ServerMain.java. This provided class parses command-line arguments, calls one of the static Board creators based on those arguments, and creates and starts a server. You should not need to change any of this code.

To run ServerMain in Eclipse

First right click ServerMain and select Run AsJava Application. You should see an error in the console. Then go to RunRun Configurations…, select the “Arguments” tab, and enter in the “Program arguments” box:

text 4444 3 3 1F308 1F984

See Unicode’s Full Emoji List to find character codes for other emoji. To start the server with a board from a file, give the filename instead of size and cards:

text 4444 boards/perfect.txt

To run ServerMain on the command line, first cd to your ps4 directory. Then start a text server on port 4444 with a 3×3 board of rainbows and unicorns:

java -ea -cp bin memory.ServerMain text 4444 3 3 1F308 1F984

Windows users: your system’s default character encoding might not be UTF-8. If you encounter problems with emoji on the command line 😱, use:

java -Dfile.encoding=UTF-8 -ea -cp bin memory.ServerMain ...

If you find that emoji don’t work in your terminal or Telnet client 😭, use letter cards instead. In the arguments to Server­Main for a random board, capital A is 41, B is 42, etc. For example, to start a 3×3 board of A and B:

java -ea -cp bin memory.ServerMain text 4444 3 3 41 42

Once the server is running, connect using ClientMain.java. This provided class facilitates communication with a text protocol server. You should not need to change its code.

To run ClientMain: in another terminal window in your ps4 directory, run:

java -cp bin memory.ClientMain localhost 4444

Or, in Eclipse, right click ClientMain, Run AsJava Application, then RunRun Configurations…, “Arguments”, “Program arguments”: localhost 4444.

If you run both client and server in Eclipse, or if you run multiple clients in Eclipse, the Console tab will only show one at a time. Click the tiny down arrow next to the console button to switch between them.

Telnet

You can also connect to the text server with Telnet: see Sockets & Networking for an introduction to telnet. Here is an example session. For input to the connection, newlines (pressing enter) are shown with :

$ telnet localhost 4444
Trying ::1...
Connected to localhost.
Escape character is '^]'.
hello world↵
Hello, world!
hello (world)↵
Go away, (world).
Ctrl-]
telnet> quit↵
Connection closed.

Our server doesn’t support the quit request yet, so instead we type the escape character Ctrl-] and quit the Telnet program to close the connection.

The TextServer doesn’t use the game board yet, but we can try out the handler for hello requests. Here is an example session. User input is shown in green:

$ java -cp bin memory.ClientMain localhost 4444
? hello world
Exception in thread "main" java.lang.NumberFormatException: For input string: "Hello,"

This simple client can’t parse the server’s response — it was looking for an integer number of rows at the beginning of the line. For debugging, you can ask the client to show raw lines of response text from the server, prefixed with <:

$ java -cp bin memory.ClientMain localhost 4444
? !debug
debugging on
? hello world
< Hello, world!
Exception in thread "main" java.lang.NumberFormatException: For input string: "Hello,"

The client parses board responses and tries to align columns to make the board easier to read. Emoji (especially ZWJ sequences) can break the alignment, but boards with letter cards should display nicely.

For example, the board from Playing over text socket looks like: 

Each displayed board line has a | prefix.

|  A  *  *
|  _ >B  _ 
|  *  *  C

Use quit to send a "quit" request to the server, which should close the connection. Press enter at the ? prompt (i.e., empty input) to exit the client and close the socket without sending "quit".

Remember that the server keeps running until you terminate its process, and if you try to run a second server on the same port, it will fail with “address already in use”. If you run the server on the command line, use Ctrl-C in that terminal. If you run the server in Eclipse, click the double-gray-X button to close consoles for terminated programs, then click the stop button.

Specify, test, and implement a single-threaded text server.

In TextServer, complete the constructor and the handleRequest method so the server implements the text protocol and gameplay rules above, using a single instance of your game board ADT.

The specifications of the constructor, port(), and serve() are required, but you are free to change any of the code in this class. You can and should change the spec of handleRequest(), for example to keep track of the current player, or to handle QUIT_REQUEST inputs that have no response.

See tips for reading and writing in Problem 1. Also:

  • The example code in handleConnection() creates a PrintWriter with automatic flushing: calling println() will flush the stream automatically. If you use another method, like print(), remember to call flush().
  • It is easy to end up with an extra newline at the end of a response, by calling println() with a string that already has a newline at the end. Make sure you follow the protocol to the letter.

When you write tests in TextServerTest, you may write tests similar to the examples we’ve provided, and you may also write tests using ByteArrayInput/OutputStream stubs as described in Sockets & Networking.

At this point, your TextServer does not need to maintain multiple client connections simultaneously, but it should be able to handle multiple clients that connect, play, and disconnect in sequence.

Make sure your TextServer has: complete specifications; abstraction function, rep invariant, and checkRep; and a safety from rep exposure argument.

Problem 3: Revise for concurrent players

3.1 Threadsafe Board

Revise Board to make it threadsafe, updating other ADTs as needed. Make sure it has a clear, complete thread safety argument.

In SimulationMain.java, increase the value of players to simulate multi-player Memory Scramble games. By instrumenting your code, for example with println statements or by keeping track of cards that different players flip over, you should observe correct control of cards, correct blocking when players try to flip over a first card, and correct removal of matching cards when players make a next move.

Notice that your simulation should not terminate if one player turns over matching cards in their last move (leaving two cards face up under that player’s control) and another player tries to flip one of them as their first card. In Eclipse, click the stop button to terminate the program.

3.2 Multi-player TextServer

Modify TextServer so it can handle multiple client connections simultaneously, and clients can play together on the same game board. Each client connection should be maintained by its own thread. See the Multithreaded server code in Sockets & Networking.

When one client is blocked waiting to control a card, other clients must be able to continue playing normally.

Make sure TextServer has a clear, complete thread safety argument. While TextServer does not need to be a threadsafe type (it may only be safe to call a TextServer instance’s public methods from one thread), it must document why its use of multiple internal threads is safe.

Manual testing

Don’t rely on manual testing to build a correct system: each ADT should have a JUnit test suite constructed with a principled testing strategy; and a clear, complete thread safety argument.

However, if there are specifications you are not sure how to test automatically, you can document manual tests that cover parts of some partitions. Document these tests in the relevant JUnit test file — for example, manual TextServer tests belong in TestServerTest.java — immediately below the testing strategy.

For each manual test: give it a descriptive name, list the parts covered, and briefly but precisely describe each step a human tester should follow, along with assertions about expected results at each step.

For example, imagine you are testing the MIT web site:

/*
 * Manual test: navigate to academic calendar
 * Covers: page=home, type=static, type=redirect, data-source=registrar
 * 1. browse to http://web.mit.edu => assert that header contains today's date
 * 2. click "education"
 * 3. click "academic calendar" => assert that page shows previous June through next June
 */

Follow the same guidelines as for automated tests: test first, design a small set of tests, keep each test short, and make sure the tests are testing the spec.

Problem 4: Web server

To implement the web server, we will use the com.sun.net.httpserver HTTP server library provided as part of the Oracle implementation of Java 10.

In WebServer.java we have provided skeleton code for a web game server:

  • The WebServer constructor creates a HttpServer and sets it to handle concurrent requests by automatically creating and reusing multiple threads (Executors.newCachedThreadPool).
  • The constructor has an example of attaching a handler for requests to paths that begin with the prefix /hello/. The handler receives a HttpExchange object that represents a single client/server request/response. The handler callback will run on a background thread, not the main thread. Since the server handles concurrent requests on multiple threads, multiple threads may be running various callbacks concurrently.
  • The example handler calls the private method handleHello(), which demonstrates how to use the HttpExchange to examine the request and send a response. If handleHello were to block, the client would be blocked waiting to read the response.
  • The constructor also adds a pair of filters to the /hello/ handler: log logs every request to stderr, and headers adds required HTTP headers. You should add those filters to all your handlers.
  • Requests for /hello/ are not part of our protocol, and you should replace the example code once you understand it.

In the provided WebServerTest.java file:

  • testHelloValid tests the behavior of the provided server on the valid request GET /hello/w0rld.
  • testHelloInvalid tests its behavior on invalid request GET /hello/world!.

To see the example code running, use ServerMain.java to start a web server on port 8080. For example, on the command line:

java -cp bin memory.ServerMain web 8080 3 3 1F308 1F984

The WebServer doesn’t use the game board yet, but we can try out the handler for /hello/. Browse to:

Specify, test, and implement support for /look/player and /flip/player/row,column requests according to the HTTP game protocol. (You will implement /watch/player requests in the next problem.)

In WebServer, the specifications of the constructor, port(), start(), and stop() are required, but you are free to change any of the code in this class.

While one request is blocked, other requests must be handled normally. In the provided code,
  server.setExecutor(Executors.newCachedThreadPool());
handles each request on a separate thread.

Make sure your WebServer has: complete specifications; abstraction function, rep invariant, and checkRep; safety from rep exposure; and a clear, complete thread safety argument. While WebServer does not need to be a threadsafe type (it may only be safe to use a WebServer instance from one thread), it must document why it is safe to call back its own request handlers from multiple internal threads.

Problem 5: Board events

Specify, test, and implement support for informing clients of the game board about when it has changed.

You may choose to implement either notification of only a single change, or notification of all future changes.

First try using your change notifications in SimulationMain.java to watch the board during a simulated game.

Then use your change notifications to specify, test, and implement support for web server /watch/player requests, notifying players when the board changes. In that specification:

  • A change is defined as any cards turning face up or face down or being removed from the board.
  • When there is no change in the state of the cards — for example, if a player tries to turn over an empty space, or if a player takes control or relinquishes control of a card but it does not turn face up or down — it is not considered a change.

You decide the specification for Board event notification:

  • If the client receives only a single change, it might be a blocking method that returns when the board changes.
  • Listeners might implement a callback interface specified by Board, and call a method to add themselves as a listener. The board will call them back on each change.
  • Clients might be consumers of a threadsafe queue of events provided by the board. The board puts an event object on the queue for each change.

You decide which changes are atomic. The “watch” request specification does not say whether, when a pair of matched (or mismatched) cards is removed (or turned face down), that is reported as a single change or two separate changes.

Make sure to update the internal documentation of WebServer where needed.

Once your server is complete, you can play the game online! We’ve built a client web page that speaks the game protocol with your server:

Play Memory Scramble

Enter the address of your running server (the default is localhost:8080), or connect to a friend’s server by IP address. There is no code running on the web.mit.edu server here: the web page is running JavaScript in your browser that talks directly with your game server.


Before you’re done

  • Make sure you have documented specifications, in the form of properly-formatted Javadoc comments, for all your types and operations.

    The spec of every type should include whether it is threadsafe.

  • Make sure you have documented abstraction functions and representation invariants, in the form of a comment near the field declarations, for all your implementations.

    With the rep invariant, also say how the type prevents rep exposure.

  • Make sure every threadsafe type has a documented thread safety argument that explains why that type is threadsafe.

    For every type that creates or uses multiple threads, its thread safety argument must explain why its use of multiple threads is safe.

  • When you implement blocking behavior, make sure the thread is blocked waiting for an event, not busy-waiting.

  • Make sure you specify, test, and implement equals() and hashCode() for all immutable types.

  • Use @Override when you override toString(), equals(), and hashCode().

    Also use @Override when a class implements an interface method, to remind readers where they can find the spec.

  • Make sure you have a thorough, principled test suite for every type.


Submitting

Make sure you commit AND push your work by 10:00pm on the deadline date.

This problem set can take much longer for Didit to process than previous psets, so push early.

Remember that Didit feedback is provided on a best-effort basis:

  • There is no guarantee that Didit tests will run within any particular timeframe, or at all. If you push code close to the deadline, the large number of submissions will slow the turnaround time before your code is examined.
  • If you commit and push right before the deadline, the Didit build does not have to complete in order for that commit to be graded.
  • Passing some or all of the public tests on Didit is no guarantee that you will pass the full battery of autograding tests, but:
    • Failing the TextProtocolTest is sure to mean many lost points on the problem set.
    • Failing the WebProtocolTest is sure to mean many lost points on the beta.

Grading

Your overall ps4 grade will be computed as approximately:
35% alpha autograde + 5% alpha manual grade + 45% beta autograde + 15% beta manual grade

The autograder test cases will not change from the alpha to the beta, but their point values will. In order to encourage incremental development, alpha autograding will focus on the text protocol, not HTTP; and on situations where clients make moves in series, not concurrently. On the beta, autograding will look at both servers, and situations with more concurrency.

Manual grading of the alpha will only examine internal documentation (AF, RI, etc.) and implementation that does not relate to concurrency. Manual grading of the beta may examine any part, including re-examining those docs or code, and how you addressed code review feedback.