[Solved] CS1632 Supplement2

For this exercise, you will practice a software testing technique calledproperty-based testing. Please review Lecture 14: Property-based Testingbefore starting on this exercise. Property-based testing is a type of dynamictesting but differs from your regular unit testing in that it tests propertiesrather than individual values to check behavior. Instead of saying: for thisparticular set of input values, I expect this output value to be returned, aproperty says: regardless of what input values are provided, I expect thisproperty to hold no matter what.

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

For this exercise, we are going to use a JUnit extension library calledQuickCheck. Existing JUnit annotations such as @Test, @Before, @After stillapply as usual but we are going to learn about some new annotations that enableus 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, Ive created an Eclipse project for you so you can use Eclipseto import the existing project and run either IntegerOpsTest or StringOpsTestindividually as JUnit classes.

## What to do

The goal is to debug IntegerOps and StringOps using the QuickCheck test classesIntegerOpsTest and StringOpsTest. The QuickCheck classes are incomplete as ofnow so you will have to complete those first. All places where you need tomodify are marked by // TODO comments. Pay close attention to the Javadoccomment above each method that describes what each method does, or is supposedto 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 andQuickCheck is to do 1000 trial runs using 1000 randomized input values. Notethat unlike a regular @Test JUnit method, an @Property method has inputparameters x and y. These input parameters are where the randomized inputvalues generated by QuickCheck are passed. So on each of the 1000 trials, xand y will be passed a different value. Not only that, the first time you runit 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 thisyourself by un-commenting the System.out.println. That is the beauty ofproperty-based testing: as you run the tests repeatedly, you will graduallygain higher coverage without you having to do anything!

Now its time to fill in the method. Fill in the code according to theinvariant property specified in the Javadoc comment above the method. If youimplemented it properly, you should get something similar to the followingmessage when you execute runTest.bat again (actual numbers may differ due torandomness):

`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 failswhen x = 1091099725 and y = 1056406418. What is the part about: Firstarguments found to also provoke a failure? Thats telling you that among the1000 trials, [1936803025, 1056406418] were the first set of values where adefect was found. From those values, QuickCheck progressively refined orshrunk them to the final values [1091099725, 1056406418]. QuickCheck alwaystries to shrink input values to the simplest or smallest values that stilltrigger 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 thanInteger.MAX_VALUE = 2147483647. So this strongly suggests the defect hassomething to do with integer overflow. Otherwise, we would have had to findthis out by trial-and-error.

If you left the System.out.println un-commented, you can see whats happeningbehind the scenes by observing the output:

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

You can see how QuickCheck is methodically doing the trial-and-error behind thescenes, so that you dont have to do it.

## Task 2: Debug IntegerOps

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

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

### 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 asingle 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 whatrandomized input values are tested. For example, things like: the additionof two positive integer should result in a positive integer.1. When a @Property test fails, not only does QuickCheck provide you with theset of input values triggering the defect, but it also shrinks them to thesmallest 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, evenafter filling in the test the test passes (and it will pass no matter how manytimes you run it unless you are very lucky). Does that mean StringOps isbug-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 stringsare identical up to that point, equals will return true. That cannot becorrect behavior.

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

That means we have to generate a distribution more likely to uncover thedefect. Remember in Lecture 14, I stressed that stochastic testing requires alot 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 touse @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.classinstead of the default uniform String generator to generate s1 and s2. OpenABCStringGenerator.java, and focus on the overridden generate method. Ioverrode the default method such that now the generated strings only containAs, Bs, and Cs. This greatly increases the chance that the two stringswill 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. Notehow I also overrode the doShrink method

`@Overridepublic 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 upperhalf are tried again respectively. Implementing the doShrink method allowsQuickCheck 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 todebug. The progressive shrinking happens as before:

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

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

## Task 5: Complete ValidHTMLStringGenerator doShrink method

Now its time to look at the testIsValidHTML method:

A uniform distribution will not give us valid HTML strings. So we need a differentgenerator 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 validHTML so the invariant is that they all return true whenStringOps.isValidHTML(s) is called. ValidHtmlStringGenerator is another customgenerator that is able to rigorously test your program by generating random butonly valid HTML strings. If you run the above, you will immediately see afailure. But the failed input is probably going to be too long for easydebugging. That is because the doShrink method is incomplete as of now.Currently, it returns an empty list of candidates meaning that the candidatesearch ends immediately and the original string is not shrunk.

Fill in the doShrink method after reading the comments and comparing againstABCStringGenerator. If you implement this properly, you should see somethinglike 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 ofinputs. In these situations, going with the default uniform distribution ofinputs will lead to horrible test coverage.1. QuickCheck allows you to create your own generator by inheriting fromexisting generators and overriding some methods. This allows you tocustomize your own distribution. In this exercise, we only practicedgenerating integers and Strings but there is nothing preventing you fromgenerating objects. For example, in the above StringOpsTest.testEquals(Strings1, String s2) method, we could have generated the two strings s1 and s2 aspart of the same object such that we correlate s1 and s2 in some way ratherthan generating them separately.

## Submission

You will create a GitHub repository just for Supplementary Exercise 2. Addyour partner as a collaborator so both of you have access. Make sure you keepthe repository *PRIVATE* so that nobody else can access your repository. Onceyou are done modifying code, dont forget to commit and push your changes tothe repository. When you are done, submit your repository to GradeScope at theSupplementary Exercise 2 GitHub link.

The autograder will test your updated IntegerOpsTest, StringOpsTest, andValidHTMLStringGenerator classes against the original IntegerOps and StringOpsclasses. Since we are testing against the original classes before debugging, we expected all tests to fail, if you have done the work.