Mutation testing for Servo

[asajeffrey]

Implement mutation testing (https://en.wikipedia.org/wiki/Mutation_testing) for Servo, based on the WPT test suite.

[asajeffrey]

cc @edunham @jdm

[edunham]

This came up in a conversation with Lonnen about a similar project on Firefox, so he can also be a resource if someone or a team embarks on this.

[dsandeephegde]

We have done initial steps Mutation testing project. This is our pull request
Highlights of the changes are:

1. One mutation strategy is introduced - replacing occurrences && to ||.
2. Test mapping framework for mapping source code to WPT tests.
3. Run Mutation test in linux-rel-nogate step on CI.

More Info

[dsandeephegde]

Test mapping is introduced to reduce the time taken to run the tests. As for each mutant, we need to run only small part of the WPT tests, It would be time-consuming to run all tests so a multiple number of times.

sample test_mapping.josn

{
  "xmlhttprequest.rs": [
     "XMLHttpRequest"
  ],
   "range.rs": [
    "dom/ranges"
  ]
}

Now test mapping is present for a couple of known source code files. The rest of the mapping needs to be filled. We need to come up with a way finding out test mapping for WPT tests. It could be done by something similar to the test coverage tool, which keeps track of the code executed when the tests run.

Is there code coverage tool for WPT test in servo?
Is there any other simpler way to populate test mapping?

[jdm]

There is no code coverage tool for tests in Servo, unfortunately.

[dsandeephegde]

Then the only way is to add the mapping manually by a person who knows about the particular part of the code? It would be a cumbersome task.
This could actually be a one time task for the full project. Then always update the test mapping when source code or test changes.

[dsandeephegde]

We are now implementing more strategies we would need more test mappings so that we can run it on more files. So if manually adding the test mapping is the only solution then someone can start with it.
Or alternatively, we can just run the whole WPT test for each mutant, if populating the mapping file is too hard. But this would cause additional ~20mins to run tests for each mutant.

We need suggestion on these approaches. Appreciate your thoughts.

[jdm]

What's wrong with falling back to all tests for any files that do not have known mappings?

[dsandeephegde]

Time would be the main constraint here. Each mutant will take 25-30mins. If we scale it to the whole servo project there are ~1000 source files then it will take days.
Even if we run only required tests, the build step is taking a lot of time which we are not able to avoid. If we run all tests which will take more time than the build, then we will be in big trouble in terms of time.

[edunham]

Could we procedurally generate the mappings using a one-time, highly aggressive set of tests? Basically perform a mutation that's guaranteed to break any tests relevant to the file, then use whichever tests break as a result as the list of tests which map to that file.

I'm pretty sure the mutation of deleting each function's body and replacing it with a single line to return a constant of that function's type would be such a "guaranteed mutation".

[dsandeephegde]

Yes, this looks like a very good option to generate test mapping, with a few manual verification. We should definitely consider this approach. But, we currently don't have such a strong mutation strategy, which will not have a lot of false negatives (no test mapping is generated even if there should be one). So, the plan is to finish the existing goals in this project, then come back to this when we are better equipped to tackle this.

[jdm]

This was implemented.