CS1632-Supplementary Exercise 2 Solved

For this exercise, you will practice a software testing technique called
property-based testing.  Please review Lecture 14: Property-based Testing
before starting on this exercise.  Property-based testing is a type of dynamic
testing but differs from your regular unit testing in that it tests properties
rather than individual values to check behavior.  Instead of saying: "for this
particular set of input values, I expect this output value to be returned", a
property says: "regardless of what input values are provided, I expect this
property to hold no matter what".

The fact that a property is invariant across the entire set of inputs allows a
property-based test to be used with any input.  That means, instead of manually
encoding inputs (say, as part of JUnit test scripts), we can even auto-generate
some random inputs and test them against our property!  This type of testing
is called stochastic testing, or random testing.  Stochastic testing is a
synonym for property-based testing.  And by the way, this broad applicability
of properties is what made them so useful for model checking and exhaustive
program state space exploration in Exercise 5.

For this exercise, we are going to use a JUnit extension library called
QuickCheck.  Existing JUnit annotations such as @Test, @Before, @After still
apply as usual but we are going to learn about some new annotations that enable
us to do property-based testing.

## List of Files

IntegerOps.java - Methods to perform simple integer arithmetic such as add and subtract (**modify**).

StringsOps.java - Methods to perform some String operations such as checking whether two strings are equal and checking a string is valid HTML (**modify**).

IntegerOpsTest.java - A QuickCheck JUnit class that performs property-based testing on IntegerOps (**modify**).

StringOpsTest.java - A QuickCheck JUnit class that performs property-based testing on StringOps (**modify**).

ABCStringGenerator.java - A QuickCheck generator class that generates random strings containing the characters 'A', 'B', and 'C'.

ValidHTMLStringGenerator.java - A QuickCheck generator class that generates random valid HTML strings containing HTML tags such as <b, </b, <i, </i (**modify**).

TestRunner.java - Driver class that contains the main method to invoke JUnit on IntegerOpsTest and StringOpsTest.

## How to Run QuickCheck

1. Running QuickCheck. For Windows do:
    ```
    runTest.bat
    ```
1. For Mac / Linux do:
    ```
    bash runTest.sh
    ```    

Initially, you should see one test already failing:
```
testIsValidHTMLTrue(StringOpsTest): Property named 'testIsValidHTMLTrue' failed:
With arguments: [<i<b<i</i</b<b</b<b<i</i</b<i<b<i</i</b</i<i</i</i]
Seeds for reproduction: [4133865354563074415]

!!! - At least one failure, see above.
```
You may see a different seed and string because it is randomly generated.

Alternatively, I've created an Eclipse project for you so you can use Eclipse
to import the existing project and run either IntegerOpsTest or StringOpsTest
individually as JUnit classes.

## What to do

The goal is to debug IntegerOps and StringOps using the QuickCheck test classes
IntegerOpsTest and StringOpsTest.  The QuickCheck classes are incomplete as of
now so you will have to complete those first.  All places where you need to
modify are marked by // TODO comments.  Pay close attention to the Javadoc
comment above each method that describes what each method does, or is supposed
to do.

## Task 1: Complete IntegerOpsTest

Open IntegerOpsTest.java.  Look at the testAdd method:

```
@Property(trials = 1000)
public void testAdd(int x, int y) {
     // System.out.println("testAdd x='" + x + "', y='" + y + "'");
     // TODO: Fill in.
}
```

Note that each method has the @Property(trials = 1000) annotation.  The
@Property annotation tells QuickCheck that this is a property-based test and
QuickCheck is to do 1000 trial runs using 1000 randomized input values.  Note
that unlike a regular @Test JUnit method, an @Property method has input
parameters x and y.  These input parameters are where the randomized input
values generated by QuickCheck are passed.  So on each of the 1000 trials, x
and y will be passed a different value.  Not only that, the first time you run
it with the 1000 trials will be different from the second set of 1000 trials
(that is, x and y are going to be different values).  You can observe this
yourself by un-commenting the System.out.println.  That is the beauty of
property-based testing: as you run the tests repeatedly, you will gradually
gain higher coverage without you having to do anything!

Now it's time to fill in the method.  Fill in the code according to the
invariant property specified in the Javadoc comment above the method.  If you
implemented it properly, you should get something similar to the following
message when you execute runTest.bat again (actual numbers may differ due to
randomness):

```
testAdd(IntegerOpsTest): Property named 'testAdd' failed:
With arguments: [1091099725, 1056406418]
First arguments found to also provoke a failure: [1936803025, 1056406418]
```

This is telling you that QuickCheck was able to determine that testAdd fails
when x = 1091099725 and y = 1056406418.  What is the part about: "First
arguments found to also provoke a failure"?  That's telling you that among the
1000 trials, [1936803025, 1056406418] were the first set of values where a
defect was found.  From those values, QuickCheck progressively refined or
"shrunk" them to the final values [1091099725, 1056406418].  QuickCheck always
tries to "shrink" input values to the simplest or smallest values that still
trigger the defect to make debugging easier.  Rather that just reporting
[1936803025, 1056406418], [1091099725, 1056406418] gives you more information.
1091099725 + 1056406418 = 2147506143 which is just slightly bigger than
Integer.MAX_VALUE = 2147483647.  So this strongly suggests the defect has
something to do with integer overflow.  Otherwise, we would have had to find
this out by trial-and-error.

If you left the System.out.println un-commented, you can see what's happening
behind the scenes by observing the output:

```
testAdd x='-1967126952', y='1194075525'
testAdd x='1191001002', y='529527415'
testAdd x='-427676937', y='1415513158'
testAdd x='898946678', y='-810210174'
testAdd x='-2096855516', y='147305889'
testAdd x='-1427326142', y='201626672'
testAdd x='927999071', y='-507009504'
testAdd x='-1575502058', y='-1850940687'
testAdd x='-82004065', y='-1320953857'
testAdd x='275074581', y='-1498381415'
testAdd x='1936803025', y='1056406418'  <--- First discovery of defect, starting shrinking ...
testAdd x='0', y='1056406418'
testAdd x='968401512', y='1056406418'
testAdd x='1452602268', y='1056406418'
testAdd x='0', y='1056406418'
testAdd x='726301134', y='1056406418'
testAdd x='1089451701', y='1056406418'
...
testAdd x='1090899926', y='1056406418'
testAdd x='1091033125', y='1056406418'
testAdd x='1091099725', y='1056406418'  <--- Smallest input while still triggering defect
testAdd x='0', y='1056406418'
testAdd x='545549862', y='1056406418'
testAdd x='818324793', y='1056406418'
testAdd x='954712259', y='1056406418'
...
```

You can see how QuickCheck is methodically doing the trial-and-error behind the
scenes, so that you don't have to do it.

## Task 2: Debug IntegerOps

Now debug IntegerOps.add(int x, int y) so that the test passes.  All you have
to do is: if you detect integer overflow (you add two positive numbers but you
end up with a negative number), then return 0.

Complete testSubstract in the same way and debug IntegerOps.subtract(int x, int
y).

### IntegerOpsTest Lessons

These are the three things you should have learned through this exercise:
1. A @Property QuickCheck test goes through many randomized trials during a
   single test run where each trial is provided with randomized input values.
1. A property check must be an invariant assertion that is true no matter what
   randomized input values are tested.  For example, things like: the addition
of two positive integer should result in a positive integer.
1. When a @Property test fails, not only does QuickCheck provide you with the
   set of input values triggering the defect, but it also "shrinks" them to the
smallest set of defect-triggering values meant to help you debug.

## Task 3: Complete StringOpsTest testEquals method

Open StringOpsTest.java.  Look at the testEquals method:

```
@Property(trials = 1000)
public void testEquals(String s1, String s2) {
     // System.out.println("testEquals s1='" + s1 + "', s2='" + s2 + "'");
     // TODO: Fill in.
}
```

Fill in the test as before based on the Javadoc comments.  Now, this time, even
after filling in the test the test passes (and it will pass no matter how many
times you run it unless you are very lucky).  Does that mean StringOps is
bug-free?  Absolutely not!  If you see StringOps.equals(String s1, String s2),
you can see the two strings are compared only up to Integer.min(s1.length(),
s2.length()).  So if one string is shorter than the other, but the two strings
are identical up to that point, equals will return true.  That cannot be
correct behavior.

Why wasn't the defect caught during the 1000 trials?  That is because the
defect manifests only when s1 and s2 fit a certain pattern (one is a substring
of the other).  And given uniform distribution, it is very unlikely that s1 and
s2 will show any resemblance whatsoever.  If you uncomment System.out.println
and observe the strings passed, you will see what I mean.

That means we have to generate a distribution more likely to uncover the
defect.  Remember in Lecture 14, I stressed that stochastic testing requires a
lot of thinking about the distribution you generate in order to be effective?
This is just such a case.  Modify the testEquals method declaration as such to
use @From annotations:

```
@Property(trials = 1000)
public void testEquals(@From(ABCStringGenerator.class) String s1, @From(ABCStringGenerator.class) String s2) {
     ...
}
```

The @From annotation tells QuickCheck to use the ABCStringGenerator.class
instead of the default uniform String generator to generate s1 and s2.  Open
ABCStringGenerator.java, and focus on the overridden generate method.  I
overrode the default method such that now the generated strings only contain
'A's, 'B's, and 'C's.  This greatly increases the chance that the two strings
will resemble each other, giving us a better chance of uncovering the defect.
Once you make the change, testEquals should fail after one or two runs.  Note
how I also overrode the doShrink method

```
@Override
public List<String doShrink(SourceOfRandomness random, String larger) {
     if (larger.length() == 0)
           return Collections.emptyList();

     // In this case, the string is shrunk simply by chopping it in half.
     // Both the left and right half are added to the list of strings to check.
     List<String list = new ArrayList<();
     list.add(larger.substring(0, larger.length() / 2));
     list.add(larger.substring(larger.length() / 2));
     return list;
}
```

If a String fails a test, it is chopped in half and the lower half and upper
half are tried again respectively.  Implementing the doShrink method allows
QuickCheck to shrink the input values just like before:

```
testEquals(StringOpsTest): Property named 'testEquals' failed:
With arguments: [, A]
First arguments found to also provoke a failure: [AB, ABC]
```

Inputs [AB, ABC] has been shrunk to [, A].  You can see how this is easier to
debug.  The progressive shrinking happens as before:

```
testEquals s1='', s2=''
testEquals s1='AB', s2='ABC'
testEquals s1='A', s2='ABC'
testEquals s1='', s2='ABC'
testEquals s1='', s2='A'
testEquals s1='', s2=''
```
## Task 4: Debug StringOps equals method

Fix equals() based on the feedback given by QuickCheck.

## Task 5: Complete ValidHTMLStringGenerator doShrink method

Now it's time to look at the testIsValidHTML method:

A uniform distribution will not give us valid HTML strings.  So we need a different
generator just like before, namely the HTMLStringGenerator.

```
@Property(trials = 1000)
public void testIsValidHTML(@From(ValidHTMLStringGenerator.class) String s) {
     // System.out.println("testIsValidHTMLTrue s='" + s + "'");
     assertTrue(StringOps.isValidHTML(s));
}
```

ValidHtmlStringGenerator generates randomized HTML strings with matching
<b...</b and <i...</i tags.  All strings passed by this generator are valid
HTML so the invariant is that they all return true when
StringOps.isValidHTML(s) is called.  ValidHtmlStringGenerator is another custom
generator that is able to rigorously test your program by generating random but
only valid HTML strings.  If you run the above, you will immediately see a
failure.  But the failed input is probably going to be too long for easy
debugging.  That is because the doShrink method is incomplete as of now.
Currently, it returns an empty list of candidates meaning that the candidate
search ends immediately and the original string is not shrunk.

Fill in the doShrink method after reading the comments and comparing against
ABCStringGenerator.  If you implement this properly, you should see something
like this on the console:

```
testIsValidHTMLTrue s='<i<i<i</i</i<b<i<i</i</i<b<i</i<i</i</b</b</i'
testIsValidHTMLTrue s='<i<i</i<b<i<i</i</i<b<i</i<i</i</b</b</i'
testIsValidHTMLTrue s='<i<b<i<i</i</i<b<i</i<i</i</b</b</i'
testIsValidHTMLTrue s='<i<b<i</i<b<i</i<i</i</b</b</i'
testIsValidHTMLTrue s='<i<b<b<i</i<i</i</b</b</i'
testIsValidHTMLTrue s='<i<b<b<i</i</b</b</i'
testIsValidHTMLTrue s='<i<b<b</b</b</i'
testIsValidHTMLTrue s='<i<b</b</i'
testIsValidHTMLTrue s='<i</i'
testIsValidHTMLTrue s=''
```

## Task 6: Debug StringOps isValidHTML method

Debug StringOps.isValidHTML based on the feedback so that now all tests pass.

### StringOpsTest Lessons

These are the two things you should have learned through this exercise:
1. Sometimes a program functions meaningfully only for a certain pattern of
   inputs.  In these situations, going with the default uniform distribution of
inputs will lead to horrible test coverage.
1. QuickCheck allows you to create your own generator by inheriting from
   existing generators and overriding some methods.  This allows you to
customize your own distribution.  In this exercise, we only practiced
generating integers and Strings but there is nothing preventing you from
generating objects.  For example, in the above StringOpsTest.testEquals(String
s1, String s2) method, we could have generated the two strings s1 and s2 as
part of the same object such that we correlate s1 and s2 in some way rather
than generating them separately.