Port fuzz tests from djot.lua

[jgm]

Any ideas why the jest timeout (3rd parameter in it) isn't working? @matklad

[matklad]

I am not sure how it could work -- as far as I know, there's no way to kill a running function in JavaScript. So what that timeout could do is to schedule some function to run later when the timeout is expired, but it can't do anything with already running code. Additionally, if the code monopolizes the event loop, that timeout firing code might not even fire....

Will go read the docs -- the existance of the timout parameter is much more surprising that the fact that it doesn't work )

[matklad]

describe("Fuzz tests", () => {
  it("does not exhibit pathological behavior on random input", async () => {
    for (let i = 1; i <= NUMTESTS; i++) {
      await new Promise(r => setTimeout(r, 0));
      let s = randomstring();
      const ast = parse(s, {warn: (() => {})});
      expect(ast).toBeTruthy();
    }
  }, 10);
});

This does the trick -- timeout only works for asynchronous functions, so adding a dummy sleep there gives the event loop ability to run the aborting code.

[jgm]

That definitely wasn't clear from the documentation!

[jgm]

OK, I don't think this actually works.

describe("Pathological tests", () => {
  for (const testname in tests) {
    it("does not exhibit pathological behavior on " + testname, async () => {
      await new Promise(r => setTimeout(r,0)); // dummy sleep see #6
      const test : string = tests[testname];
      const start = performance.now();
      const ast = parse(test, {warn: ignoreWarnings});
      const end = performance.now();
      expect(ast).toBeTruthy();
      expect(end - start).toBeLessThan(1000);
      console.log(end - start);
    }, 10);
  }
});

Note the timeout is set to 10 ms. However, the output clearly shows that it is taking > 10 ms for each parse, and the timeout doesn't engage. If I set the timeout to 1ms, it will kick in.

[matklad]

That's because the await point is the only place where timeout can engage I think. That is, I think that if you put the timeout at the end, this will work.

But also, if the goal here is just to test that the thing is fast, I'd maybe just manually measure the time and throw if its too long -- seems more direct and bullet proof that going through the framework

[jgm]

I do want to do that (and just pushed a commit that does).

However, we also need a timeout on the test -- otherwise the tests will hang if we get a pathological case.

[jgm]

Moving it to the end seems to work!

[matklad]

However, we also need a timeout on the test -- otherwise the tests will hang if we get a pathological case.

Yeah, that one I think wouldn't work, unless we introduce await point within the parser itself. The code can only be interrupted at an await point, so, if we end up in 2^n loop and there's no await here, we'll loop until the whole CI job is killed

[matklad]

In parcicular, moving it to the end would kill the test only after we finish parsing

[jgm]

Re-opening.

[jgm]

It seems to me that this is a really basic thing for a test framework to have -- a simple way of interrupting any test that hangs after a certain time. Why does this seem impossible?

[matklad]

It's ... not a basic thing. On a fundamental level, if there's some code running on a CPU, there's no way to stop it from outside within the process. The only two choices are:

• for the running code itself to check for some flag once in a while and to shutdown itself when the flag is set
• for the operating system to kill the whole process

Some runtime systems (eg, haskell with asynchronous exceptions) essentially automate the insertions of "flag checking points", but that's a rather odd feature. In two other cases I know (Java's interrupt and pthread_cancel), the current wisdom is that not a great thing to have, and that cancellation points should in general be flagged by the programmer (eg, via explicit .await point).

So, it's not really a defficiency of a testing framework, rather, it's a fundamental limitation of runtime system which doesn't support equivalent of asynchroneous exceptions.

Though, I would say that jest is at a fault for not explaining the limitation of their timeout (that it only works for async functions, and that it only is checked at await points). That's my confusion about the feature existing at all.

Practically, I'd maybe just rely on the CI to kill the process eventually?

[matklad]

Actually, let me check a thing...

[matklad]

Ok, so I think one way we can make this work is by running the body of the test in a worker thread:

https://nodejs.org/api/worker_threads.html#worker-threads

That way, parsing won't monopolise the event loop, and would get the chance for the timeout code to run, and the timeout code would be able to kill the worker

[jgm]

I'd maybe just rely on the CI to kill the process eventually?

The problem is that then we don't get information about the input that caused the hang, which is exactly the information we're trying to get out of the fuzz testing. (Note that jest won't put any output out to the console, even with console.log, until the test completes.)

The worker threads idea seems worth exploring, but I think it's beyond my current understanding of JS to implement it myself.

[jgm]

I'll close this, because we have the fuzz tests. They can still give useful negative information (no hangs or excessively long parses), even if they can't give positive information (hangs on string S). If you or someone else wants to explore the worker thread idea, go for it.