Acorn's makePredicate function requires 'unsafe-eval'

[NeilFraser]

Michael Bean reported an issue that the JS-Interpreter required 'unsafe-eval' to be added to the Content Security Policy. This was traced to Acorn which built up some custom functions by concatenating code strings to produce five highly efficient functions: isReservedWord3, isReservedWord5, isStrictReservedWord, isStrictBadIdWord, and isKeyword. This function generator was completely safe and did not take any user-input. However, the CSP requirements make this approach undesirable.

Here is the original makePredicate function: https://github.com/NeilFraser/JS-Interpreter/blob/c6e74b83405e2b939bf460efb0050accaef6a551/acorn.js#L345 It's ridiculously optimized to generate functions which check if an arbitrary string is in a fixed set.

As an immediate fix, I made this commit which uses a simple loop instead: https://github.com/NeilFraser/JS-Interpreter/commit/edaa67d7ff1ab683a4a336945b4fffeae7f425bb However, the generated functions are performance-sensitive, and I'd like to ensure that we have the best option.

This issue is intended to be a record of comparative approaches and their respective performances.

[NeilFraser]

There are several options I'd like to formally compare:

1. Length-partitioned case structures (the original implementation).
2. Sorted loop scan (current implementation).
3. A Set().
4. An Object.
5. String.indexOf.
6. Array.indexOf.

Startup time is considered irrelevant since it's a one-off. What matters most is the performance of calling these functions with a matching or non-matching string. Other considerations are code size, and maintainability. A couple of the above options are not available on all browsers (Set, Array.indexOf), so if either these are used, fallbacks would be needed for older browsers.

Testing will be done on Firefox 95.0.2, Chrome 97.0.4692.71, and Safari 15.2 on OSX 11.6.2 running on a MacBook Pro (Mid 2014). The test framework is https://neil.fraser.name/news/2021/06/07/

The tests in all cases will be:

function isKeyword(str) {
  ...
}

var tests = ["break", "case", "catch", "continue", "debugger", "default", "do", "else", "finally", "for", "function", "if", "return", "switch", "throw", "try", "var", "while", "with", "null", "true", "false", "instanceof", "typeof", "void", "delete", "new", "in", "this",
             "breaX", "casX", "catcX", "continuX", "debuggeX", "defaulX", "dX", "elsX", "finallX", "foX", "functioX", "iX", "returX", "switcX", "throX", "trX", "vaX", "whilX", "witX", "nulX", "truX", "falsX", "instanceoX", "typeoX", "voiX", "deletX", "neX", "iX", "thiX"];
console.time();
for (var i = 0; i < 10000; i++) {
  for (var j = 0; j < tests.length; j++) {
    isKeyword(tests[j]);
  }
}
console.timeEnd();

1. Length-partitioned case structures (the original implementation).

function isKeyword(str) {
  switch (str.length) {
    case 4:
      switch (str) {
        case "case":
        case "else":
        case "with":
        case "null":
        case "true":
        case "void":
        case "this":
          return true
      }
      return false;
    case 5:
      switch (str) {
        case "break":
        case "catch":
        case "throw":
        case "while":
        case "false":
          return true
      }
      return false;
    case 3:
      switch (str) {
        case "for":
        case "try":
        case "var":
        case "new":
          return true
      }
      return false;
    case 6:
      switch (str) {
        case "return":
        case "switch":
        case "typeof":
        case "delete":
          return true
      }
      return false;
    case 8:
      switch (str) {
        case "continue":
        case "debugger":
        case "function":
          return true
      }
      return false;
    case 2:
      switch (str) {
        case "do":
        case "if":
        case "in":
          return true
      }
      return false;
    case 7:
      switch (str) {
        case "default":
        case "finally":
          return true
      }
      return false;
    case 10:
      return str === "instanceof";
  }
}

Firefox: 9ms Chrome: 2ms Safari: 10ms

2. Sorted loop scan (current implementation).

var words = 'break case catch continue debugger default do else finally for function if return switch throw try var while with null true false instanceof typeof void delete new in this';
words = words.split(' ');
words.sort();
function isKeyword(str) {
  for (var i = 0; i < words.length; i++) {
    if (words[i] >= str) {
      if (words[i] === str) {
        return true;
      }
      break;
    }
  }
  return false;
}

Firefox: 214ms Chrome: 57ms Safari: 110ms

3. A Set().

var words = 'break case catch continue debugger default do else finally for function if return switch throw try var while with null true false instanceof typeof void delete new in this';
words = new Set(words.split(' '));
function isKeyword(str) {
  return words.has(str);
}

Firefox: 10ms Chrome: 9ms Safari: 20ms

4. An Object.

var words = 'break case catch continue debugger default do else finally for function if return switch throw try var while with null true false instanceof typeof void delete new in this';
words = words.split(' ');
var obj = Object.create(null);
for (var i = 0; i < words.length; i++) {
  obj[words[i]] = true;
}
function isKeyword(str) {
  return obj[str] || false;
}

Firefox: 18ms Chrome: 6ms Safari: 22ms

5. String.indexOf.

var words = 'break case catch continue debugger default do else finally for function if return switch throw try var while with null true false instanceof typeof void delete new in this';
words = ' ' + words + ' ';
function isKeyword(str) {
  return words.indexOf(' ' + str + ' ') !== -1;
}

Firefox: 144ms Chrome: 1ms (Whoa!) Safari: 125ms

6. Array.indexOf.

var words = 'break case catch continue debugger default do else finally for function if return switch throw try var while with null true false instanceof typeof void delete new in this';
words = words.split(' ');
function isKeyword(str) {
  return words.indexOf(str) !== -1;
}

Firefox: 90ms Chrome: 17ms Safari: 63ms

My conclusion is that option 4 (An Object) is the best solution given that it is reasonably fast, cross-browser, and easy to read.

[NeilFraser]

Implemented and committed.