\documentclass[british]{scrartcl}

\usepackage[british]{babel}
\usepackage{csquotes}
\usepackage{enumerate}
\usepackage[hidelinks]{hyperref}
\usepackage{minted}
\setminted{fontsize=\small,breaklines}
\usepackage{skak}
\usepackage{tikz}
\usetikzlibrary{arrows, matrix, positioning}
\usepackage{cleveref}

\title{Testing the \texttt{chesshs} Haskell Package}
\subtitle{Test Plan, Manual Testing and Automated Testing}
\author{
	Ren\'e den Hertog\footnote{s1007823} \and
	Camil Staps\footnote{s4498062} \and
	Erin van der Veen\footnote{s4431200}
}
% Remove the date from '\maketitle'.
\makeatletter
	\patchcmd
		{\@maketitle}
		{{\usekomafont{date}{\@date\par}}\vskip\z@\@plus 1em}
		{}
		{}
		{}
\makeatother

\begin{document}

\maketitle

\section{Test Plan}

\subsection*{System Under Test (SUT) Description}

The chosen SUT is the \texttt{chesshs} Haskell package.
\cite{SUT} It should be able to run in any software environment and hardware platform which supports Haskell.
The latest version of the SUT, since the 13\textsuperscript{th} of March 2015, is \texttt{0.2.1}.

\subsubsection*{Executing/Running the SUT}

It is required to be able to compile Haskell,
	typically through the Glasgow Haskell Compiler (GHC),
	and having the \texttt{chesshs} package installed,
		normally through Cabal via the \mintinline{bash}{cabal install chesshs} command~\cite{GHC, C}.
On our systems,
	compiling and starting the SUT is done with the \mintinline{bash}{make} and \mintinline{bash}{./runchess} commands, respectively.

The SUT is used by providing it with standard input containing a game of Chess in Portable Game Notation~\cite{PGN}.
After computation,
	some general information about the Chess match is given on standard output,
	including the end result,
	followed by the state of the board after each move.
In case of a parse error or an invalid move, an error message is displayed.

As is common with all software, the SUT is likely to contain faults.
However, few risks are associated with the program, due to the very low impact of the program faulting.
As for our expectation, the most \enquote{risky} scenario for the SUT is at a notable Chess competition.
In the case the program does not behave as intended,
	it is almost certain that a human referee would take over its place.
Furthermore, we expect such a system to be used as a supporting tool for match officials
	and not as a replacement for regulation.

\subsection*{Test Goals}

\subsubsection*{Specification}

The specification of the SUT is for the most part similar to the input-output behaviour described above.
Because the SUT is strongly related to Chess,
	many finer details of its specification can be derived from documentation from the world of Chess.

\paragraph{F\'ed\'eration Internationale Des Echecs (FIDE)}
Due to the popularity of Chess, most people are familiar with how it is played.
Hence, a summary of the rules is omitted here.
However, due to the competitive nature of the game,
	the World Chess Federation describes the rules painfully precise~\cite{FIDE}.

\paragraph{Portable Game Notation (PGN)}
Many Chess matches are recorded in PGN~\cite{PGN}, an example of which is shown in \cref{L:PGNE}.

\begin{listing}
	\inputminted[lastline=19]{text}{../test/database/m0.in}
	\dots
	\inputminted[firstline=42]{text}{../test/database/m0.in}
	\caption{An example of Portable Game Notation (PGN).\label{L:PGNE}}
\end{listing}

PGN consists of two parts: the tag pairs and the movetext.

The tag pairs encode properties of the game of Chess in question,
	such as the name of the tournament or match event,
	the player of the white pieces and the player of the black pieces,
	and the result of the game.
It is possible to add self defined tag pairs.
During our testing, we have added the name of the test with a \texttt{TestName} tag pair.
Tag pairs always follow the structure

\begin{minted}{text}
	[<Tag Name> "<Tag Value>"]
\end{minted}

where \texttt{'Tag Name'} holds the name of the tag
	(\texttt{Event}, \texttt{White}, \texttt{Black}, \texttt{Result}, ...)
	and \texttt{'Tag Value'} the value of the tag
	(\texttt{Third Rosenwald Trophy}, \texttt{Donald Byrne}, \texttt{Robert James Fischer}, \texttt{0-1}, ...).

The movetext encodes the actual game of Chess in question.
It mainly consists of the moves made during the match, which are encoded with

\begin{minted}{text}
	<Round Number>. <White's Move> <Black's Move>
\end{minted}

where each player's move is recorded in the Standard Algebraic Notation (SAN).

\subparagraph{Standard Algebraic Notation (SAN)}

Most moves are recorded with the SAN, which adheres to the following structure~\cite{SAN}:

\begin{minted}{text}
	<Piece Identifier>[x]<End Position>
\end{minted}

The \texttt{Piece Identifier} denotes the piece being moved by a single capital letter:
	\texttt{B} (Bishop), \texttt{K} (King), \texttt{N} (Knight), \texttt{Q} (Queen) and \texttt{R} (Rook).
Pawns either do not have an abbreviation or are denoted with \texttt{P}.
In the case the abbreviation alone is not sufficient to identify the piece being moved,
	(partial) initial position information is added to resolve ambiguity,
	according to the notation explained in \cref{F:SN}.
The \texttt{Piece Identifier} is followed by \texttt{x} only if the move resulted in a capture.
The \texttt{End Position} records the final position of the moved piece using the notation explained in \cref{F:SN}.
Additional notation exists to describe more specialized aspects of Chess moves.
For example, \texttt{+} is appended to checking moves and \texttt{O-O} alone denotes king side castling moves.

\begin{figure}
	\centering
	\newgame
	\showboard
	\caption{Square Notation: Each square is noted by its file (column letter) and rank (row number).\label{F:SN}}
\end{figure}

\paragraph{Testing Scope}

The SUT is the \texttt{chesshs} library.
However, it is useful to have an actual program that can be run.
To this end, we have written a small wrapper program that acts as a command-line interface to the library.
The source code of the wrapper is shown in \cref{L:WI}.
This program is kept as minimal as possible to contain (almost) no logic that might influence our tests.

The \texttt{chesshs} package contains several subsystems.
Specifically, we will test

\begin{enumerate}
	\item PGN parsing; \label{EI:PGNP}
	\item move legality verification and \label{EI:MLV}
	\item checkmate position determination. \label{EI:CPD}
\end{enumerate}

The PGN specification has effect on \ref{EI:PGNP};
	the FIDE Chess rules have an effect on \ref{EI:MLV} and \ref{EI:CPD}.
Some Chess rules not implemented in the \texttt{chesshs} library,
	like those concerning timing,
	can and will not be tested.

Our main focus will lie on the quality characteristic of functionality.
We would like to have a reasonable level of certainty that the SUT behaves as specified
	and correctly implements the rules of Chess.
Reliability is also relevant to the SUT,
	especially because it is a library that other systems depend on:
	we do not expect any crashes; exceptions should be handled using \texttt{Maybe}s and the like.
Usability does not apply in the same way to libraries as it does to end user programs.
The actual users are the programmers that use the library in their code.
Hence, usability mainly concerns whether the API has sensible, well-scoped functions.
We will be able to comment on the usability as we have written the small wrapper,
	but will not attempt to achieve an objective judgement in this aspect
	--- that would require finding a reasonably large set of programmers using \texttt{chesshs},
		and we suspect that may be hard.

White box and grey box testing would look somewhat similar when testing the SUT, due to the fact that the system is a package.
Grey box testing would only look at the components available to other programs, that is, the exported elements.
For instance, we might look at the types of functions, but not their implementation.
White box testing would also look at every component of the library including their implementation.
Grey box testing would consider every component as a black box:
	it would only focus on testing if each component adheres to its related specification.
White box testing would consider every component by its literal code.
In conclusion, white box testing would focus on the actual implementation of the library's functionality
	and grey box testing would only focus on the library's exported component's functionality without considering any actual code.

\subsection*{Test Method}

Our tests are mainly at the unit level, and somewhat at the integration level.
The SUT only consists of two components: the wrapper and the \texttt{chesshs} package.
Both are \enquote{atomic} enough to be tested via unit testing.
The interaction between these two, mostly the usage of the library by the wrapper, will be tested via integration testing.
Testing at the module, system and acceptance level is not reasonable in the case of our SUT, as its scale and number of subsystems limits us to lower testing levels.

\paragraph{Test Generation Techniques}

The majority of our test generation techniques are based upon or similar to black box methods. However, we also will apply some white box testing techniques.

\subparagraph{Black Box Techniques}

The focus of the black box testing is on the SUT in its entirety, that is, the \texttt{chesshs} package surrounded by the wrapper. The black box tester will try to find faults in the input-output behavior of the program as described in \S\ref{P:ERSUT}. In this type, test generation is based on error guessing and an examples database.

Error guessing is based mostly on our collective experience of developing and testing software in the past. But also somewhat on our experience with the game of Chess and using other similar SUTs.

The examples database consists of a collection of text files describing a game of Chess in (possibly illegal) PGN (the `\texttt{.in}' files) and the expected output of the SUT (the `\texttt{.out}' files).

We will manually create test cases of this form, where we will be possibly introducing illegal PGN guided by error guessing.

Sadly, equivalence partitioning and boundary value analysis are hard to apply to our SUT, given that the collection of all possible Chess games is nearly impossible to categorize. Use case testing is also tricky to apply. The wrapper is very limited in its interaction and is designed purely to make the \texttt{chesshs} package ``usable" for testing. Since the core of our SUT is a library, no \emph{end} user will likely interact with it directly. In summary, it does not feel reasonable to apply use case testing to the SUT.

\subparagraph{White Box Techniques}

The focus of the white box testing is on the \texttt{chesshs} package only, that is, the components of the library. The white box tester will try to find faults in the implementation of the package with regards to its specification. In this type, test generation is based on statement coverage and manual path based coverage.

Statement coverage, in Haskell's case, marks the lines of code that have been executed at least once.

Path based coverage analysis is not included in the testing tools used. To compensate, we will measure path based coverage manually. By hand, the implementation is transformed into a control flow graph, and we manually determine how the test cases ``traverse" the code.

We will continuously adapt the white box tester until it reaches a sufficient level of coverage, that is full coverage, unless achieving so is unfeasible or unreasonable.

Sadly, path, branch and condition coverage are not included in the tools we will be using during the testing. Hence, it is substantially harder to implement these test generation techniques and will not be applied during our testing. \\

As every software developer and tester knows, it is very hard, if not impossible, to completely test a given system. Noting that the risks surrounding our SUT are almost negligible (see \S\ref{P:ERSUT}), the pressure on the testing is not noticeable. However, we still feel the tests as described should give a more than sufficient scrutiny. The black box testing will likely find, if any, faults in the wrapper and the interaction with the \texttt{chesshs} package. The white box testing will likely find, if any, errors in the implementation of the library.

\subsection*{Test Environment}

Since the SUT is in actuality the \texttt{chesshs} package, a user interface is clearly lacking. Thats why we have written a wrapper which makes the library interactive. See listing \ref{L:WI} for the full implementation. \\

\begin{listing}
	\inputminted{haskell}{../src/runchess.hs}
	\caption{Wrapper Implementation} \label{L:WI}
\end{listing}

Black box tests will be automatically performed using shell scripting. In our case, we will be using bash and Linux compatible scripts. Test automation for white box testing is achieved by functionalities available in the to be used testing tool Quick Check. \cite{QC} \\

The software environments we will be using for testing our SUT are the operating system Linux, specifically Debian and Ubuntu, and the Haskell Platform \texttt{2014.2.0.0}, which includes, the Glasgow Haskell Compiler (GHC) \texttt{7.10.3}, Cabal \texttt{1.22.6.0} (\texttt{1.22.5.0} for the library) and Quick Check \texttt{2.8.1}. \cite{HP, GHC, C, QC} The hardware platforms are three differently powerful laptops, notably Acer and Toshiba.

The testing architecture is best described by the graphic shown in figure \ref{F:TAGO}.

\begin{figure}
	\centering
	\begin{tikzpicture}[
			every node/.style={draw,rectangle},
			title/.style={draw=none},
			->,>=open triangle 60]
		\node (bbtest) at (4,0)  {Black Box Tester (\texttt{test.sh})};
		\node[matrix,row sep=.5em] (prog) at (0,0) {
			\node[title] {Wrapper};\\
			\node (chesshs) {\texttt{chesshs}};\\
		};
		\node[left=2em of chesshs] (wbtest) {White Box Tester (\texttt{test.hs})};
		\node[below of=wbtest] (quickcheck) {Quick Check};
		\draw (bbtest) -- (prog);
		\draw (wbtest) -- (chesshs);
		\draw (quickcheck) -- (wbtest);
	\end{tikzpicture}
	\caption{Testing Architecture Graphical Overview} \label{F:TAGO}
\end{figure}

No stubs nor drivers are necessary for executing the testing architecture. \\

Most, if not all, documentation surrounding the tests, test results and test environment will be included in this document. It is possible that some tests and test results will contain information not stated here, such as the name of a test case and the possible flaw that it (tries to) detect(s). However, any external information will easily be found in the appropriate files.

The tests will either be stored in the examples database (directory) or will be part of the Quick Check unit test module(s) (source file). The test results will be stored, if necessary, in the same files as their related test or in another easy to locate file. The test environment will be stored, as every other testing component, in a Git repository found at \url{https://gitlab.science.ru.nl/eveen/Testing-Techniques.git}.

Since Haskell, as most functional programming languages, is ``stable" in terms of side effects and randomness, reproductivity should no be an issue. Nevertheless, we will make sure every test case can be reproduced, that is, run again leading to the same results as is documented.

\section{Manual Testing}

Since the SUT is an Application Programming Interface all tests are constructed not as an sequence of interactions, but rather as something that can be fed to the wrapper.
In turn, the wrapper uses the API of \texttt{chesshs} to construct the position sequence.
This position sequence is then compared to a user defined expected output.

In essence, this implies that the Manual Tests and Automated Tests are the same.

If the wrapper were extended to support interactivity, manual testing would have a more prominent place.

\section{Automated Testing}

The input of the automated tests are stored in individual files.
These files contain one or more PGN games that are fed to the wrapper.
The wrapper then passes these PGN games to the chesshs library, and outputs the board state after every move.
\begin{listing}
	\inputminted{bash}{../test/test.sh}
	\caption{Automated Test script\label{L:ATS}}
\end{listing}

A small bash script, shown in \cref{L:ATS}, is used
	to compare the output that is produced by the wrapper with a user defined expected output.
If there is no difference between the two, the test is considered \enquote{passed}.
If there is a difference, this is output by the script.

\begin{thebibliography}{8}
	\bibitem[C]    {C}    \url{http://haskell.org/cabal}
	\bibitem[FIDE] {FIDE} \url{http://fide.com/fide/handbook.html}
	\bibitem[GHC]  {GHC}  \url{http://haskell.org/ghc}
	\bibitem[HP]   {HP}   \url{http://haskell.org/platform}
	\bibitem[PGN]  {PGN}  \url{http://saremba.de/chessgml/standards/pgn/pgn-complete.htm}
	\bibitem[QC]   {QC}   \url{http://hackage.haskell.org/package/QuickCheck}
	\bibitem[SAN]  {SAN}  \url{http://cfajohnson.com/chess/SAN}
	\bibitem[SUT]  {SUT}  \url{http://hackage.haskell.org/package/chesshs}
\end{thebibliography}

\end{document}
