Proposal: break out of infinite loops using a hit counter

[nicojs]

Is your feature request related to a problem? Please describe.

Stryker might be mutating your code to be an infinite loop. There is no way around that, because of something called the Halting problem. For example:

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

Currently, StrykerJS's way to handle infinite loops is to kill the worker process and start a new one. This works, but it can be very expensive, especially when webpack or other JIT build steps are involved. Take an Angular project for example. Having a new test runner worker process take a minute to start is quite 'normal' for larger projects (besides the fact that a new browser is started as well).

Describe the solution you'd like

When StrykerJS is instrumenting the code, we could add a hit counter that counts the number of times that mutant is executed. If an absolute limit is reached, we can set a "hitCountLimitReached" flag and throw an error. Then in the test runner, we can check for the presence of the flag and report the mutant as a timeout result.

Pseudo code:

function activeMutant(id) {
  if (id === global.__stryker__.activeMutant) {
    if (global.__stryker__.hitCount  !== undefined && ++global.__stryker__.hitCount > global.__stryker__hitCountLimit) {
      throw new Error('Mutant hit count reached');
    }
    return true;
  }
  return false;
}

As you can see, Stryker will throw an error when the hitCount of a mutant exceeds a predetermined limit. The predetermined limit can be based on the number of hits during normal (unmutated) execution, which can be determined during the dry run.

hitLimit(mutant) = hits(mutant) * hitLimitFactor + hitLimitOffset

The higher the hitLimitFactor, the longer it takes to break out of an infinite loop, but setting the hitLimitFactor too low might result in false negatives. We could start with a safe factory (i.e. 100) and see what that gives us.

We could also add a reason field to our TimeouMutantRunResult. The reason can be provided by the test runner as "Hit limit of x reached" (or something like that). That way you can identify these results in the HTML report.

There are some disadvantages to this approach:

• It is difficult to determine a universal "hard limit". For some tasks (image processing, performance tests, etc) a hard limit of 1000 would be far too low. I think therefore this limit should be configurable: --mutantHitLimit? Setting this value to 0 could mean turning the hit limit off. @hcoles came up with an excellent idea in Proposal: break out of infinite loops using a hit counter #3023 (comment) . The limit will be determined based on the normal hit count, which can be calculated during the dry run (initial test run). This removes the need for --mutantHitLimit entirely. We might want to introduce a configurable --mutantHitLimitFactory in the future, but for now, we can use a hard factory of 100 for example (to be on the safe side)
• The error might not be handled properly by the test. It might result in an unhandled exception or unhandled promise rejection. We might want to think about adding handlers for those, or investigate if each test runner properly handles that already.
• The error might be caught by your code. This can have unexpected consequences
  • If the error is caught inside the loop, the loop won't be broken and remain infinite.
  • If the error is caught outside of the loop, where a different error was expected to be handled. This probably will result in a failing test (which should be converted to a timeout by the test runner), but still: unexpected behavior.
• Test runners will get more complicated (although we could move some of this code to @stryker-mutator/utils):
  • decide when there is a timeout based on the global "hitCountLimitReached" flag.
  • Reset both the hitCount and the hitCountLimit variables. If we forget to reset, false negatives will occur.

As you can see, it can only ever be a best-effort approach and Stryker will always need its current behavior to handle infinite loops in addition.

Note that there are still timeouts that are unhandled by this implementation, especially with regards to using callbacks in your test logic. For example:

// foo.js
function maybeEmitFooEvent(a, b) {
  if (activeMutant(1) ? a > b : a < b) {
     emitter.emit('foo');
  }
}

// foo.spec.js
it('should raise event', (done) => {
  emitter.on('foo', done);
  maybeEmitFooEvent(1, 2);
});

Describe alternatives you've considered

There is no real alternative that I can think of, other than what we're doing now.

Additional context

Karma has difficulties with infinite loops: #2989 (comment)

[nicojs]

@Garethp What do you think of this? I know we had multiple discussions about infinite loops in the past.

[hcoles]

I've been meaning to implement this in pitest for years. Rather than a fixed hard limit I'd always planned to record the number of hits each test made to the method in its unmutated state, then error out if the mutate probe hit the code 'x' times more than that for the current test.

[nicojs]

Ohhh I like that approach! More work to do for the test runner plugin (set the limit), but that is a relatively small addition. It might remove the need for a configuration option altogether, or can you still think of a reason to disable the feature?

@hcoles why didn't you implement the feature yet? Is byte code mutation limiting you in some way?

[hcoles]

Not a byte code issue, just quite a lot of work given how the code has evolved. I'd need a solid week or two to sit down and look at it, which I've never had.

[Garethp]

I think it's not a bad idea and calculating the number of hits per test is probably a way safer way to do things IMO. I'm not sure that making the number of hits user configurable is all that valuable since it requires the user to know what a good amount is. I think the concerns about where the error is caught is valid, maybe it would be better for it to send a signal up to it's thread parent indicating an infinite loop so the thread can be killed and marked that way?

Personally I'm still a fan of the heartbeat idea we talked about as a long term solution to this

[nicojs]

I'm not sure that making the number of hits user configurable is all that valuable since it requires the user to know what a good amount is.

We could still allow users to configure a factor. For example, a factor of 2 would mean twice as many times as in the dry run. However, I agree that we shouldn't want to make that configurable, since it should not be needed. We can make the internal factor a high number to lean on the safe side (for example, a factor of 100).'

I think the concerns about where the error is caught are valid, maybe it would be better for it to send a signal up to its thread parent indicating an infinite loop so the thread can be killed and marked that way?

Hmm, interesting. However, tests might run inside the browser (karma), or inside a VM (jest). So this implementation should be test-runner dependent.

maybe it would be better for it to send a signal up to its thread parent indicating an infinite loop so the thread can be killed and marked that way?

What do you mean by "thread parent" and "the thread can be killed"? JS is single-threaded. Test runner processes generally run tests in their thread, except for karma, which runs the tests inside the browser (also single-threaded). The only way to recover from this, without breaking out of the loop, would be to kill the test runner worker and start a new process. With the sending of the "signal" as you put it, we could kill and restart sooner than we normally would, because we wouldn't have to wait for the timeout timer to expire, but it would still be expensive for JIT heavy projects.

Therefore, I prefer the "throw Error" approach. It can be baked into the instrumenter, so less work for the test runner. A mutant run would look like this in the test runner:

class FooTestRunner {
  async runMutant(options) {
    // Prepare hit counter stuff
    global.__stryker__.hitCount = 0;
    global.__stryker__.hitCountLimitReached = false;
    global.__stryker__.hitCountLimit = options.hitCountLimit;
    
     // Switch active mutant
    global.__stryker__.activeMutant = options.activeMutant.id;
    
    // Do the actual test run
    const result = await underlyingTestRunner.run();
    
    // See if it was a timeout
    if (global.__stryker__.hitCountLimitReached) {
      return { state: 'timeout' };
    } else {
      return result
    }
  }
}

The nice thing is that the test-runner could choose to ignore the hit counter stuff entirely. If a test runner doesn't implement it, we would still be able to handle timeouts as we now do.

[bartekleon]

That looks really good. When we were profiling stryker, we have already noticed that restarting processes is quite expensive so it might really help in performance. I believe it might also help with stability, since restarting childProcesses could theoretically mess something in runs :)

[nicojs]

This feature just got released for Stryker 5.3 (karma runner only) please give it a try