Auto merge of #18984 - dsandeephegde:master, r=jdm

 Initial steps of Mutation testing

<!-- Please describe your changes on the following line: -->
- Added one strategy of mutation which is replacing occurrences && to ||.
- Added test mapping framework for running mutation tests corresponding to a mutant.
- Added one test_mapping.json to map source file in a folder to WPT test.
- Added README mentioning about Mutation testing.
- Added CI script to invoke mutation test.
---
<!-- Thank you for contributing to Servo! Please replace each `[ ]` by `[X]` when the step is complete, and replace `__` with appropriate data: -->
- [x] `./mach build -d` does not report any errors
- [x] `./mach test-tidy` does not report any errors
- [x] These changes #18529 (github issue number if applicable).
- [x] These changes do not require tests because it is a python script to run mutation test and does not change any behavior.

<!-- Also, please make sure that "Allow edits from maintainers" checkbox is checked, so that we can help you if you get stuck somewhere along the way.-->

<!-- Pull requests that do not address these steps are welcome, but they will require additional verification as part of the review process. -->

<!-- Reviewable:start -->
---
This change is [<img src="https://reviewable.io/review_button.svg" height="34" align="absmiddle" alt="Reviewable"/>](https://reviewable.io/reviews/servo/servo/18984)
<!-- Reviewable:end -->

3 files changed, 212 insertions, 0 deletions

diff --git a/python/servo/mutation/README.md b/python/servo/mutation/README.md
new file mode 100644
index 00000000000..fe051642703
--- /dev/null
+++ b/python/servo/mutation/README.md
@@ -0,0 +1,79 @@
+## Implement Mutation Testing on Servo Parallel Browsing Project

+

+

+The motivation for mutation testing is to test the breadth coverage of tests for source code. Faults (or mutations) are automatically seeded into the code, then tests are run. If tests fail then the mutation is killed, if the tests pass then the mutation lived. The quality of tests can be gauged from the percentage of mutations killed.

+

+For more info refer [Wiki page](https://en.wikipedia.org/wiki/Mutation_testing).

+

+Here Mutation testing is used to test the coverage of WPT for Servo's browser engine.

+

+### Mutation Strategy

+This version of mutation testing consists of a Python script that finds random uses of && in Servo's code base and replaces them by ||. The expectation from the WPT tests is to catch this mutation and result in failures when executed on the corresponding code base.

+

+### Test Run Strategy

+The mutation test aims to run only tests which are concerned with the mutant. Therefore part of WPT test is related to the source code under mutation is invoked. For this it requires a test mapping in source folders.

+

+#### test_mapping.json

+The file test_mapping.json is used to map the source code to their corresponding WPT tests. The user must maintain a updated version of this file in the path where mutation testing needs to be performed. Additionally, the test_mapping.json will only consist of maps of source codes that are present in the current directory. Hence, each folder will have a unique test_mapping.json file. Any source code files that may be present in a path but are not mapped to a WPT in test_mapping.json will not be covered for mutation testing.

+

+#### Sample test_mapping.json format

+A sample of test_mapping.json is as shown below:

+

+```

+{

+  "xmlhttprequest.rs": [

+    "XMLHttpRequest"

+  ],  

+  "range.rs": [

+    "dom/ranges"

+  ]

+}

+```

+

+Please ensure that each folder that requires a mutant to be generated consists of test_mapping.json file so that the script can function as expected. Wildcards are not allowed in test_mapping.json.

+

+If we want to run mutation test for a source path then there should be test_mapping.json in that path and all the subdirectories which has source files.

+

+Eg: There should be test mapping in following folders if we run mutation test on 'components/script' path.

+* components/script/test_mapping.json

+* components/script/dom/test_mapping.json

+* components/script/task_source/test_mapping.json

+* components/script/dom/bindings/test_mapping.json

+* ...

+

+### Running Mutation test

+The mutation tests can be run by running the below command from the servo directory on the command line interface:

+

+`python python/servo/mutation/init.py <Mutation path>`

+

+Eg. `python python/servo/mutation/init.py components/script/dom`

+

+### Running Mutation Test from CI

+

+The CI script for running mutation testing is present in /etc/ci folder. It can be called by executing the below command from the CLI:

+

+`python /etc/ci/mutation_test.py`

+

+### Execution Flow

+1. The script is called from the command line, it searches for test_mapping.json in the path entered by user.

+2. If found, it reads the json file and parses it, gets source file to tests mapping.

+3. If the source file does not have any local changes then it is mutated at a random line.

+4. The corresponding WPT tests are run for this mutant and the test results are logged.

+5. Once all WPT are run for the first source file, the mutation continues for other source files mentioned in the json file and runs their corresponding WPT tests.

+6. Once it has completed executing mutation testing for the entered path, it repeats the above procedure for sub-paths present inside the entered path.

+

+### Test Summary

+

+At the end of the test run the test summary displayed which looks like this:

+```

+Test Summary:

+Mutant Killed (Success)         25

+Mutant Survived (Failure)       10

+Mutation Skipped                1

+Unexpected error in mutation    0

+```

+

+* Mutant Killed (Success): The mutant was successfully killed by WPT test suite.

+* Mutant Survived (Failure): The mutation has survived the WPT Test Suite, tests in WPT could not catch this mutation.

+* Mutation Skipped: Files is skipped for mutation test due to the local changes in that file.

+* Unexpected error in mutation: Mutation test could not run due to unexpected failures. (example: if no && preset in the file to replace)

diff --git a/python/servo/mutation/init.py b/python/servo/mutation/init.py
new file mode 100644
index 00000000000..a3461779bbb
--- /dev/null
+++ b/python/servo/mutation/init.py
@@ -0,0 +1,55 @@
+# Copyright 2013 The Servo Project Developers. See the COPYRIGHT
+# file at the top-level directory of this distribution.
+#
+# Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+# http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+# <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+# option. This file may not be copied, modified, or distributed
+# except according to those terms.
+
+from os import listdir
+from os.path import isfile, isdir, join
+import json
+import sys
+import test
+test_summary = {
+    test.Status.KILLED: 0,
+    test.Status.SURVIVED: 0,
+    test.Status.SKIPPED: 0,
+    test.Status.UNEXPECTED: 0
+}
+
+
+def get_folders_list(path):
+    folder_list = []
+    for filename in listdir(path):
+        if isdir(join(path, filename)):
+            folder_name = join(path, filename)
+            folder_list.append(folder_name)
+        return folder_list
+
+
+def mutation_test_for(mutation_path):
+    test_mapping_file = join(mutation_path, 'test_mapping.json')
+    if isfile(test_mapping_file):
+        json_data = open(test_mapping_file).read()
+        test_mapping = json.loads(json_data)
+        # Run mutation test for all source files in mapping file.
+        for src_file in test_mapping.keys():
+            status = test.mutation_test(join(mutation_path, src_file.encode('utf-8')), test_mapping[src_file])
+            test_summary[status] += 1
+        # Run mutation test in all folder in the path.
+        for folder in get_folders_list(mutation_path):
+            mutation_test_for(folder)
+    else:
+        print("This folder {0} has no test mapping file.".format(mutation_path))
+
+
+mutation_test_for(sys.argv[1])
+print "\nTest Summary:"
+print "Mutant Killed (Success) \t{0}".format(test_summary[test.Status.KILLED])
+print "Mutant Survived (Failure) \t{0}".format(test_summary[test.Status.SURVIVED])
+print "Mutation Skipped \t\t{0}".format(test_summary[test.Status.SKIPPED])
+print "Unexpected error in mutation \t{0}".format(test_summary[test.Status.UNEXPECTED])
+if test_summary[test.Status.SURVIVED]:
+    sys.exit(1)
diff --git a/python/servo/mutation/test.py b/python/servo/mutation/test.py
new file mode 100644
index 00000000000..2248f81ccd3
--- /dev/null
+++ b/python/servo/mutation/test.py
@@ -0,0 +1,78 @@
+# Copyright 2013 The Servo Project Developers. See the COPYRIGHT
+# file at the top-level directory of this distribution.
+#
+# Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+# http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+# <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+# option. This file may not be copied, modified, or distributed
+# except according to those terms.
+
+import fileinput
+import re
+import subprocess
+import sys
+import os
+import random
+from enum import Enum
+DEVNULL = open(os.devnull, 'wb')
+
+
+class Status(Enum):
+    KILLED = 0
+    SURVIVED = 1
+    SKIPPED = 2
+    UNEXPECTED = 3
+
+
+def mutate_random_line(file_name, strategy):
+    line_numbers = []
+    for line in fileinput.input(file_name):
+        if re.search(strategy['regex'], line):
+            line_numbers.append(fileinput.lineno())
+    if len(line_numbers) == 0:
+        return -1
+    else:
+        mutation_line_number = line_numbers[random.randint(0, len(line_numbers) - 1)]
+        for line in fileinput.input(file_name, inplace=True):
+            if fileinput.lineno() == mutation_line_number:
+                line = re.sub(strategy['regex'], strategy['replaceString'], line)
+            print line.rstrip()
+        return mutation_line_number
+
+
+def mutation_test(file_name, tests):
+    status = Status.UNEXPECTED
+    local_changes_present = subprocess.call('git diff --quiet {0}'.format(file_name), shell=True)
+    if local_changes_present == 1:
+        status = Status.SKIPPED
+        print "{0} has local changes, please commit/remove changes before running the test".format(file_name)
+    else:
+        strategy = {'regex': r'\s&&\s', 'replaceString': ' || '}
+        mutated_line = mutate_random_line(file_name, strategy)
+        if mutated_line != -1:
+            print "Mutating {0} at line {1}".format(file_name, mutated_line)
+            print "compiling mutant {0}:{1}".format(file_name, mutated_line)
+            sys.stdout.flush()
+            subprocess.call('python mach build --release', shell=True, stdout=DEVNULL)
+            for test in tests:
+                test_command = "python mach test-wpt {0} --release".format(test.encode('utf-8'))
+                print "running `{0}` test for mutant {1}:{2}".format(test, file_name, mutated_line)
+                sys.stdout.flush()
+                test_status = subprocess.call(test_command, shell=True, stdout=DEVNULL)
+                if test_status != 0:
+                    print("Failed: while running `{0}`".format(test_command))
+                    print "mutated file {0} diff".format(file_name)
+                    sys.stdout.flush()
+                    subprocess.call('git --no-pager diff {0}'.format(file_name), shell=True)
+                    status = Status.SURVIVED
+                else:
+                    print("Success: Mutation killed by {0}".format(test.encode('utf-8')))
+                    status = Status.KILLED
+                    break
+            print "reverting mutant {0}:{1}".format(file_name, mutated_line)
+            sys.stdout.flush()
+            subprocess.call('git checkout {0}'.format(file_name), shell=True)
+        else:
+            print "Cannot mutate {0}".format(file_name)
+        print "-" * 80 + "\n"
+    return status