feat(hit limit): infinite loop prevention in karma-runner

[nicojs]

Add infinite loop prevention using a hit counter in the core and the karma runner.

I want to add this functionality to the other test runners as well, but first want to see how it behaves in the wild. The karma runner is also the most expensive one to restart, so it has the most to gain with this functionality.

During mutation testing, Stryker might create an infinite loop. For example:

let i = 0;
while (i < 10){
  if(activeMutant("1")) {
    i--;   // 👈 mutant that creates an infinite loop
  } else {
    i++;
  }
}

In the past, Stryker would eventually report a timeout. This is expensive because Stryker has to kill the test runner process and start a new one. This can take anywhere from less than a second to multiple minutes, depending on the test runner.

With this PR, infinite-loop-prevention code is generated during code instrumentation:

function isActive(id) {
  if (ns.activeMutant === id) {
    if (ns.hitCount !== void 0 && ++ns.hitCount > ns.hitLimit) {
      throw new Error('Stryker: Hit count limit reached (' + ns.hitCount + ')');
    }
    return true;
  }
  return false;
}

As you can see, an error is thrown when a limit is reached. This hopefully breaks the infinite loop but it might not, since the error can be caught and handled by user-code inside the loop, making it infinite once again. I don't see a way around this, since js has no goto statement and I don't know of another way to "break out of infinity". In such cases, the timeout will still occur and the test runner process will be killed.

The job of preventing infinite loops is a shared responsibility between Stryker and the test runner plugin.

• Stryker is responsible for adding the infinite loop prevention code and providing the hit limit to the test runner.
• The test runner plugin is responsible to set the hitLimit and reset the hitCount on the __stryker__ variable and determining whether or not the hit limit was reached.

Important to note is that this functionality is optional. If the test runner doesn't set the __stryker__.hitCount and __stryker.hitLimit variables, the functionality will simply be ignored.

The hit limit is provided to the test runner in the MutantRunOptions. Stryker calculates it using the hitCount from the dry run:

hitLimit(m) = hitCount(m) * hitLimitFactor

Choosing a good hitLimitFactor here is crucial. If the value is too low, it might increase false positives. If the value is too high, it might take longer to complete. However, I've chosen to start with a factor of 100, to lean to the save side. We might want to make this factor configurable in the future.

Note that there are theoretical cases where this functionality results in false positives, no matter how high we make the hitLimitFactor. For example:

let i = 0;
while (i < 10 && i > -9999){
 if(activeMutant("1")) {
    i--;   // 👈 mutant that will "falsly" be reported as a timeout
  } else {
    i++;
  }
}

There is one case I can think of that isn't theoretical. Namely when someone is using a property testing library, like jsverify. During property testing, a failing scenario might be executed a lot of times to determine the smallest possible counterexample. I haven't tested this yet, but I am planning to do that.

List of changes:

• API
  • Add hitLimit to the MutantRunOptions
  • Add hitCount and hitLimit to InstrumenterContext
  • Add hitCount to MutantTestCoverage result.
  • Add optional reason field to Timeout test runner results.
  • Add determineHitLimitReached helper function to determine wether or not a hit limit is reached
• Instrumenter
  • Add instrumentation for hit limit and counting hits.
• Core
  • Determine the hitCount based on the mutant coverage.
  • Determine the hitLimit based on the hitCount and provide it in MutantRunOptions
• Karma runner
  • Grap hitLimit and configure it using the test hooks middleware.
  • Determine if a timeout occurred using the determineHitLimitReached helper.
  • Add integration test for this new behavior
• e2e
  • Add new hit-limit e2e test.

Closes #3023

[nicojs]

@hcoles I've decided to go with your approach of using the dry-run result to determine the 'normal' hit count as you can see in the description. Thanks again for that great insight.

[hcoles]

@nicojs Glad someone is going to implement it.

[simondel]

Looks good!