Fuzzing a parser

The single biggest performance bottleneck of my JS parser is the tokenizer. And by far the most expensive problem in there is determining what to parse next.

Imagine this; you're in a random city. You have no idea where to go next. No google maps and the people around you are... no, actually, no people around you at all. You'll just start walking and every time you're at an intersection you need to make a decision. Left, right, forward? Once you've made that decision, you usually just follow the road though, careful about curves and bumps. Until the next intersection.

A parser does the same thing. You get a character, say ", and now you need to determine what the type of token is that you're parsing. Once you know that it's a string, the options for the following characters are limited so parsing is fast. But this decision is quite tough.

Imagine this, you're back in this stupid city but rather than a regular four way crossing, you're now on a 127 way crossing. Woops.

In JS, it's pretty much the same. The language constructs are built on most of the ascii range. On top of that the variable names ("identifiers") may contain unicode characters (like half of 0xffff) but they are actually extreme edge cases. So it's mostly a little more over a hundred you take into account. That's still a lot. And they distill into about eight types of tokens (and then some): whitespace, newlines, single comment, multi comment, string, number, regex literal, punctuator, and identifier. There's also EOF and ASI but they're not really relevant in this story.

Noteworthy is that the start of a token is context sensitive for JS for one character: the forward slash (/). Regular readers of my blog probably know these rules, the rest can google for them ;) In all other cases, a certain character at the start of a token tells you what to parse next.

In some (most?) cases, however, you may need the next character too in order to determine what type of token you're parsing. For example, the dot (.) can mean a punctuator but if it's succeeded by a number it'll be a number. JS parses in a greedy way, so as long as it can parse more, it will. However, every character has a predetermined parsing path. In any case, you only need to look ahead one character tops.

This story now becomes one of stats. Obviously there are many characters and obviously some characters will be used more than others. The problem with this is that, well, "it depends". Strongly, actually. It depends on your coding style. It depends on your tooling. It depends on the type of code you're writing. Three.js will probably use certain characters more than jQuery (and no, the dollar sign is actually not very common in the jQuery library, although it will be in any source that uses it). Minified code will see far less newlines and built code will probably only see one type of quote (double quotes seem far more common). It really depends.

However, you can generalize over this. For example, generally the most common character is a space (about 25-30%). Yes, a build tool could replace your regular spaces with one of the more obscure ones, but who the hell does that. No really, tell me so I know who to punch ;) And a style guide could state tabs, obviously diminishing the number of spaces in your project (though not eradicating them). Something that's not likely to change is the dot (though yes, you could replace all dot property access with dynamic access, and you'd be stupid). However, on average there's "only" about 6-7% of them. The next are newlines (5%, but do you give priority to CR or LF or both? What about parsing on a platform that only uses one of them? Would be a wasteful check for the other char. But if you don't ... ), parenthesis (4.5% each, these are actually pretty safe since they are part of common JS constructs), semi colons (3.7%, but could just as well not appear), comma (3.2%), etc.

Let's talk strategies.

Starting simple, we can do a switch. A switch would actually be perfect, would it not be that they are interpreted in JS and you have to rely on JIT to turn it into a jump table. And you can't. Because it often won't.

A switch would look something like this:

switch (c) {
case ORD_SPACE: return this.__plusOne(WHITE);
case ORD_DOT: return this.__parseDot();
case ORD_CR: return this.__parseCR();
case ORD_LF: return this.__newline();
case ORD_OPEN_PAREN: return this.__plusOne(PUNCTUATOR);
case ORD_CLOSE_PAREN: return this.__plusOne(PUNCTUATOR);
case ORD_SEMI: return this.__plusOne(PUNCTUATOR);
case ORD_COMMA: return this.__plusOne(PUNCTUATOR);
case ORD_IS: return this.__parseEqualSigns();
case ORD_L_T: return this.__parseIdentifier();
case ORD_OPEN_CURLY: return this.__plusOne(PUNCTUATOR);
case ORD_CLOSE_CURLY: return this.__plusOne(PUNCTUATOR);
case ORD_TAB: return this.__plusOne(WHITE);
case ORD_L_I: return this.__parseIdentifier();
case ORD_L_F: return this.__parseIdentifier();
case ORD_L_A: return this.__parseIdentifier();

Etc. The problem at hand of course is that JS will walk the switch, top to bottom, and evaluate every case expression until entering the right one. That means a worst case 105 checks until finally determining a very expensive unicode check and after that, throwing a syntax error. On average though, this seems to be around 12 checks per token for that switch.

Now 12 comparisons might not sound too shabby in terms of comparing two numbers to each other. But we're gunning for the high numbers here. A benchmark of 16mb runs at about 6 million tokens. That means it will do a staggering 6*12=72 million number comparisons for just determining the start of a token. So you can see, cutting this number down can be quite interesting in the long run.

A first obvious problem with a switch is that you can't really do range checks. As you can see near the end of the example, it starts checking individual letters. But for a computer on the low level, a range check is equally as slow as a direct comparison. I can't tell on the high level, but I would guess that it's not much different, even at this scale.

While lower case letters individually don't amount to much in terms of starting tokens, as a group they do. In fact, a token starts most with the letter t (consider this, true, try, and throw as well as the popularity of the letter in general) with about 3%. Combined, though, lower case letters start about 20% of the tokens (mileage might vary, though minifiers usually tend to start with the lower case and variables in JS usually only start with a capital if they signify a class). So that's 20% at not 26 checks, but a measly two range checks! And we'll throw in a free splitting up of characters in there as well! Well, later we will.

In an if-else structure the code would look something like this:

if (c === ORD_SPACE) return this.__plusOne(WHITE);
if (c >= ORD_L_A && c <= ORD_L_Z) return this.__parseIdentifier(); // 25%
if (c === ORD_DOT) return this.__parseDot();
if (c === ORD_OPEN_PAREN || c === ORD_CLOSE_PAREN || c === ORD_SEMI || c === ORD_COMMA) return this.__plusOne(PUNCTUATOR);
if (c === ORD_IS) return this.__parseEqualSigns();
if (c === ORD_CR) return this.__parseCR();
if (c === ORD_LF) return this.__newline();
if (c === ORD_OPEN_CURLY || c === ORD_CLOSE_CURLY) return this.__plusOne(PUNCTUATOR);
if (c === ORD_DQUOTE) return this.__parseDoubleString();
if (c === ORD_COLON || c === ORD_OPEN_SQUARE || c === ORD_CLOSE_SQUARE) { ++this.pos; return PUNCTUATOR; }
if (c === ORD_LODASH) return this.__parseIdentifier();

Etc. The average look up time for the token start with this structure is about 6! Imagine that, 36 million checks cut down by just rearranging the logic a bit. Such wow.

For a while, this is the structure I used in zeparser2. It's easy to follow and it got the job done. Recently however I've been hitting performance walls and need to get more micro. So currently I'm revisiting this structure a bit. Because seriously, we can do better than an average of 6. Come on!

It's actually a search algorithm. Or rather, that's what the tokenizer is doing. It's searching. And one of the best strategies is divide and conquer, with a bit of smartness. So having a straight `if-else` structure like above looks nice and massive, but it's still not uber efficient. For example, if you have ten items, and three of these items have a high percentage while the rest has a low percentage (but total to a high amount) it might make sense to divide the search area. Heck, it's just a tree right? We could do binary search on it or something.

At this point I'm just looking at checks. Thing is, a range comparison is an expensive check. It has to reduce the average number enough to warrant the extra check for all characters that are divided by it. For example compare these three cases:

if (1) ... 3%;
if (2) ... 25%
if (3) ... 41%
if (4) ... 3%
if (5) ... 25%
if (6) ... 3%

Ordered this would be an average of (41*1 + 25*2 + 25*3 + 3*4 + 3*5 + 3*6) / 100 = 2.11. While this:


if (<4) { total: 69%
if (3) ... 41%
if (2) ... 25%
if (1) ... 3%;
} else { total: 31%
if (5) ... 25%
if (4) ... 3%
if (6) ... 3%
}

Is ((41*2 + 25*3 + 3*4) + (25*2 + 3*3 + 3*4)) / 100 = 2.4. But if you move out the biggest one (save 1 check for that character but add one to all the others) you get:


if (3) ... 41%
if (<4) { total: 28%
if (2) ... 25%
if (1) ... 3%;
} else { total: 31%
if (5) ... 25%
if (4) ... 3%
if (6) ... 3%
}

(41*1 + (25*3 + 3*4) + (25*3 + 3*4 + 3*5)) / 100 = 2.3

In this case, the straight if check is best because it lowers the average check to 2.11. In our original case that's not true though since the straight if check amounts to about 6 checks. My best complex structure so far is 3.65 checks, and I'm still searching!

Searching is actually quite hard. As you can see by the last two examples, moving a condition out of an if block can improve the numbers dramatically. However, repeat it and you'll tip the scales against you because every time you move out a check, you add an extra check to anything that follows. It's about finding the proper balance.

In the last two examples above, moving out the 3 is actually better than not doing so because it means 41% get one check less while 31% gets one check more (note that the other branch already had that check factored in so it's not exactly a "one check for everyone" kind of deal). Netto that means 10% gets one check less so the average drops.

I started doing this balancing act manually, but quickly figured the math involved and the chaos theory behind it. The searching area is huge. I can fiddle all I want but it's too much effort to go and try a change and test it. So I quickly gave up on that.

Enter fuzzing. I wrote a fuzzer to generate these snippets of code for me. It generates the body of checks to determine the rest of the token. It will randomly generate these if-else structures. For pure random example, this is its current best:

if (++steps && c < ORD_PLUS) { /* sum: 48.440000000000005 */
if (++steps && c < ORD_VTAB) { /* sum: 1.89 */
if (++steps && c === ORD_TAB) return this.__plusOne(WHITE); /* 1.89 */
if (++steps && c === ORD_LF) return this.__newline(); /* 0 */
} else { /* sum: 46.550000000000004 */
if (++steps && c === ORD_SPACE) return this.__plusOne(WHITE); /* 29.71 */
if ((++steps && c === ORD_OPEN_PAREN) || (++steps && c === ORD_CLOSE_PAREN)) return this.__plusOne(PUNCTUATOR); /* sum: 9.32 */
if (++steps && c === ORD_CR) return this.__parseCR(); /* 5.14 */
if (++steps && c === ORD_DQUOTE) return this.__parseDoubleString(); /* 1.24 */
if (++steps && c === ORD_EXCL) return this.__parseEqualSigns(); /* 0.33 */
if (++steps && c === ORD_AND) return this.__parseSameOrCompound(c); /* 0.26 */
if (++steps && c === ORD_STAR) return this.__parseCompound(); /* 0.2 */
if (++steps && c === ORD_SQUOTE) return this.__parseSingleString(); /* 0.2 */
if (++steps && c === ORD_$) return this.__parseIdentifier(); /* 0.14 */
if (++steps && c === ORD_PERCENT) return this.__parseCompound(); /* 0.01 */
if (++steps && c === ORD_FF) return this.__plusOne(WHITE); /* 0 */
if (++steps && c === ORD_VTAB) return this.__plusOne(WHITE); /* 0 */
}
} else { /* sum: 54.809999999999995 */
if (++steps && c < ORD_L_A) { /* sum: 30.009999999999998 */
if (++steps && c < ORD_L_5) { /* sum: 15.540000000000001 */
if (++steps && c < ORD_COMMA) { /* sum: 0.61 */
if (++steps && c === ORD_PLUS) return this.__parseSameOrCompound(c); /* 0.61 */
} else { /* sum: 11.690000000000001 */
if (++steps && c === ORD_DOT) return this.__parseDot(); /* 6.59 */
if (++steps && c === ORD_COMMA) return this.__plusOne(PUNCTUATOR); /* 3.24 */
if (++steps && c === ORD_L_0) return this.__parseZero(); /* 0.53 */
if (++steps && c === ORD_L_1) return this.__parseNumber(); /* 0.41 */
if (++steps && c === ORD_FWDSLASH) return this.__parseFwdSlash(expressionStart); /* 0.41 */
if (++steps && c === ORD_DASH) return this.__parseSameOrCompound(c); /* 0.22 */
if (++steps && c === ORD_L_2) return this.__parseNumber(); /* 0.15 */
if (++steps && c === ORD_L_3) return this.__parseNumber(); /* 0.08 */
if (++steps && c === ORD_L_4) return this.__parseNumber(); /* 0.06 */
}
} else { /* sum: 14.439999999999998 */
if (++steps && c < ORD_L_A_UC) { /* sum: 8.389999999999997 */
if (++steps && c === ORD_SEMI) return this.__plusOne(PUNCTUATOR); /* 3.71 */
if (++steps && c === ORD_IS) return this.__parseEqualSigns(); /* 3.13 */
if (++steps && c === ORD_COLON) return this.__plusOne(PUNCTUATOR); /* 1.05 */
if (++steps && c === ORD_QMARK) return this.__plusOne(PUNCTUATOR); /* 0.15 */
if (++steps && c === ORD_LT) return this.__parseLtgtPunctuator(c); /* 0.14 */
if (++steps && c === ORD_GT) return this.__parseLtgtPunctuator(c); /* 0.08 */
if (++steps && c === ORD_L_6) return this.__parseNumber(); /* 0.03 */
if (++steps && c === ORD_L_5) return this.__parseNumber(); /* 0.03 */
if (++steps && c === ORD_L_8) return this.__parseNumber(); /* 0.03 */
if (++steps && c === ORD_L_7) return this.__parseNumber(); /* 0.02 */
if (++steps && c === ORD_L_9) return this.__parseNumber(); /* 0.02 */
} else if (++steps && c <= ORD_L_Z_UC) { /* sum: 3.2300000000000004*/
return this.__parseIdentifier();
} else { /* sum: 2.8200000000000003 */
if (++steps && c === ORD_OPEN_SQUARE) return this.__plusOne(PUNCTUATOR); /* 1.06 */
if (++steps && c === ORD_CLOSE_SQUARE) return this.__plusOne(PUNCTUATOR); /* 1.06 */
if (++steps && c === ORD_LODASH) return this.__parseIdentifier(); /* 0.7 */
if (++steps && c === ORD_XOR) return this.__parseCompound(); /* 0 */
if (++steps && c === ORD_BACKSLASH) return this.__parseBackslash(); /* 0 */
}
}
} else if (++steps && c <= ORD_L_Z) { /* sum: 20.679999999999996*/
return this.__parseIdentifier();
} else { /* sum: 4.12 */
if (++steps && c === ORD_OPEN_CURLY) return this.__plusOne(PUNCTUATOR); /* 1.95 */
if (++steps && c === ORD_CLOSE_CURLY) return this.__plusOne(PUNCTUATOR); /* 1.95 */
if (++steps && c === ORD_OR) return this.__parseSameOrCompound(c); /* 0.22 */
if (++steps && c === ORD_TILDE) return this.__parseCompound(); /* 0 */
if (++steps && c === ORD_PS) return this.__newline(); /* 0 */
if (++steps && c === ORD_NBSP) return this.__plusOne(WHITE); /* 0 */
if (++steps && c === ORD_BOM) return this.__plusOne(WHITE); /* 0 */
if (++steps && c === ORD_LS) return this.__newline(); /* 0 */
}
}


(The ++steps are to count the steps, at the end of parsing it divides the total steps to the number of tokens and this is the average.)

It averages at 4.05 checks. Because it checks that too, of course, how else would you know what to keep. Note that the structure above is unprocessed. I can usually squeeze a little more out of it using my wits. See, the fuzzer is really just a dumb combinator. It has a set of characters and ranges. I've put in the percentages of occurrence as I use them right now (prints them too, as you can see). Some of them are actually ranges, like lower case and upper case letters, numbers, and one or two other characters. For ranges it will randomly try either the range as a double check, put them as individual characters (you can see it did so with numbers above) or an if-then-else three pass range check. The first check divides the "pack" a little. For ranges you'll have to do two checks anyways but why waste the first one when it gives you information?

After making a list of characters or ranges to check it randomizes them. Then it starts adding some arbitrary range checks. Split the list up between chars less than x and the rest. Just arbitrary cuts in hopes of randomly finding a more efficient way of dividing the list. It will order the groups of checks inside a condition by percentage. Highest percentage first of course. It will then take the top character and there's a small chance that it promotes it (promoting the space check of 20% this way often leads to a better average as I think it should be one of the second checks).

After it has done all that it starts generating source code based on the resulting structure. Quite literally so actually. It will also print the percentages and add the totals up for the conditions so I can more easily do the math described above.

When it did all that, it will take the source code for the tokenizer and replace the body of the nextToken function. It will run the parser, first on jquery (which is a small file so it runs fast) and then on threejs (just under a megabyte, for confirmation and against stat bias). When the average number of steps is low in both cases, it is remembered (printed) and the code starts again. Over and over again until I say stop.

This is doing what the saying "if a thousand monkeys on blablabla" means. It's also what fuzzing means. Maybe it'll find the perfect solution, maybe it won't. Right now it seems to do about 6-9 steps on average. It's best is 4. It's all about lowering the average result though, since that increases the odds of a lower outlier. I'll post some other example outputs below so you can compare.

I still have some ideas for improving it. For example when a range has been torn apart, we can still recombine them. If a block has to do 10 individual letter checks, he could instead have the result in two. Like the numbers in the above example:

// original
if (++steps && c === ORD_L_0) return this.__parseZero(); /* 0.53 */
if (++steps && c === ORD_L_1) return this.__parseNumber(); /* 0.41 */
if (++steps && c === ORD_FWDSLASH) return this.__parseFwdSlash(expressionStart); /* 0.41 */
if (++steps && c === ORD_DASH) return this.__parseSameOrCompound(c); /* 0.22 */
if (++steps && c === ORD_L_2) return this.__parseNumber(); /* 0.15 */
if (++steps && c === ORD_L_3) return this.__parseNumber(); /* 0.08 */
if (++steps && c === ORD_L_4) return this.__parseNumber(); /* 0.06 */

// combine
if (++steps && c === ORD_L_0) return this.__parseZero(); /* 0.53 */
if (++steps && c === ORD_FWDSLASH) return this.__parseFwdSlash(expressionStart); /* 0.41 */
if (++steps && c === ORD_DASH) return this.__parseSameOrCompound(c); /* 0.22 */
if (++steps && c === ORD_L_1 && ++steps && c <= ORD_L_9) return this.__parseNumber(); /* 0.41 */

// move up because it now combines the % of 1-9, or actually 1-4 in this case
if (++steps && c === ORD_L_0) return this.__parseZero(); /* 0.53 */
if (++steps && c === ORD_FWDSLASH) return this.__parseFwdSlash(expressionStart); /* 0.41 */
if (++steps && c === ORD_L_1 && ++steps && c <= ORD_L_9) return this.__parseNumber(); /* 0.70 */
if (++steps && c === ORD_DASH) return this.__parseSameOrCompound(c); /* 0.22 */

Boom. I do this manually right now but this can be automated too. The math is harder on this one though because changing to a range check increases the checks for 1 from one to two, for an extra % reach of 0.29%. So it's actually 1 check for 0.29% meaning you can move it one up (because it's better than the 0.22%) but not necessarily beyond the forward slash because that would add an extra check while the uptick is less. However this means that the original 1 condition disappears so I'm not sure whether it should be moved up or not. This is exactly why I wrote a fuzzer ;)

I know it's all fairly simple math in the end, it's just a long equation. The printed numbers and operations only make this more apparent, which is good. Less guessing and more factual improvements.

Okay that's enough geeking out for now :)

You can see the fuzzer at work at http://qfox.nl/fuzzer/fuzz.html but be careful, it's quite mesmerizing :) Also, ping if you get anything under 3.5 ;)



Some more examples. Only the first one has been manually post-processed (down from 4.1), the rest I still have to check out.


// 3.6662683413113855
if (++steps && c < ORD_DOT) { /* sum: 52.510000000000005 */
if (++steps && c === ORD_SPACE) return this.__plusOne(WHITE); /* 29.71 */
if (++steps && c < ORD_OPEN_PAREN) {
if (++steps && c === ORD_CR) return this.__parseCR(); /* 5.14 */
if (++steps && c === ORD_TAB) return this.__plusOne(WHITE); /* 1.89 */
if (++steps && c === ORD_DQUOTE) return this.__parseDoubleString(); /* 1.24 */
if (++steps && c === ORD_EXCL) return this.__parseEqualSigns(); /* 0.33 */
if (++steps && c === ORD_AND) return this.__parseSameOrCompound(c); /* 0.26 */
if (++steps && c === ORD_SQUOTE) return this.__parseSingleString(); /* 0.2 */
if (++steps && c === ORD_$) return this.__parseIdentifier(); /* 0.14 */
if (++steps && c === ORD_PERCENT) return this.__parseCompound(); /* 0.01 */
if (++steps && c === ORD_FF) return this.__plusOne(WHITE); /* 0 */
if (++steps && c === ORD_VTAB) return this.__plusOne(WHITE); /* 0 */
if (++steps && c === ORD_LF) return this.__newline(); /* 0 */
} else if (++steps && c <= ORD_CLOSE_PAREN) {
return this.__plusOne(PUNCTUATOR); /* 4.66 + 4.66 */
} else {
if (++steps && c === ORD_COMMA) return this.__plusOne(PUNCTUATOR); /* 3.24 */
if (++steps && c === ORD_STAR) return this.__parseCompound(); /* 0.2 */
// + or -
return this.__parseSameOrCompound(c); /* 0.83 */
}
} else { /* sum: 48.62 */
if (++steps && c < ORD_L_A) { /* sum: 23.82 */
if (++steps && c < ORD_L_A_UC) {
// . / 019 : ; < = > ? @
if (++steps && c === ORD_DOT) return this.__parseDot(); /* 6.59 */
if (++steps && c === ORD_SEMI) return this.__plusOne(PUNCTUATOR); /* 3.71 */
if (++steps && c === ORD_IS) return this.__parseEqualSigns(); /* 3.13 */
if (++steps && c === ORD_COLON) return this.__plusOne(PUNCTUATOR); /* 1.05 */
if (++steps && c >= ORD_L_1 && ++steps && c <= ORD_L_9) return this.__parseNumber(); /* sum: 0.8300000000000001 */
if (++steps && c === ORD_L_0) return this.__parseZero(); /* 0.53 */
if (++steps && c === ORD_FWDSLASH) return this.__parseFwdSlash(expressionStart); /* 0.41 */
// ORD_LT + ORD_GT
if (++steps && c <= ORD_GT) return this.__parseLtgtPunctuator(c); /* 0.22 */
if (++steps && c === ORD_QMARK) return this.__plusOne(PUNCTUATOR); /* 0.15 */
} else if (++steps && c <= ORD_L_Z_UC) {
return this.__parseIdentifier(); /* 0.28 */
} else {
if (++steps && c === ORD_OPEN_SQUARE) return this.__plusOne(PUNCTUATOR); /* 1.06 */
if (++steps && c === ORD_CLOSE_SQUARE) return this.__plusOne(PUNCTUATOR); /* 1.06 */
if (++steps && c === ORD_LODASH) return this.__parseIdentifier(); /* 0.7 */
if (++steps && c === ORD_BACKSLASH) return this.__parseBackslash(); /* 0 */
if (++steps && c === ORD_XOR) return this.__parseCompound(); /* 0 */
}
} else if (++steps && c <= ORD_L_Z) { /* sum: 20.679999999999996*/
return this.__parseIdentifier();
} else { /* sum: 4.12 */
if (++steps && c === ORD_CLOSE_CURLY) return this.__plusOne(PUNCTUATOR); /* 1.95 */
if (++steps && c === ORD_OPEN_CURLY) return this.__plusOne(PUNCTUATOR); /* 1.95 */
if (++steps && c === ORD_OR) return this.__parseSameOrCompound(c); /* 0.22 */
if (++steps && c === ORD_LS) return this.__newline(); /* 0 */
if (++steps && c === ORD_TILDE) return this.__parseCompound(); /* 0 */
if (++steps && c === ORD_PS) return this.__newline(); /* 0 */
if (++steps && c === ORD_BOM) return this.__plusOne(WHITE); /* 0 */
if (++steps && c === ORD_NBSP) return this.__plusOne(WHITE); /* 0 */
}
}



// 3.938048946881937
if (++steps && c < ORD_SQUOTE) {
if (++steps && c === ORD_SPACE) return this.__plusOne(WHITE); /* 20.5 */
if (++steps && c < ORD_CR) {
if (++steps && c === ORD_TAB) return this.__plusOne(WHITE); /* 1.27 */
if (++steps && c === ORD_LF) return this.__newline(); /* 0 */
if (++steps && c === ORD_VTAB) return this.__plusOne(WHITE); /* 0 */
if (++steps && c === ORD_FF) return this.__plusOne(WHITE); /* 0 */
} else {
if (++steps && c === ORD_CR) return this.__parseCR(); /* 3.47 */
if (++steps && c === ORD_DQUOTE) return this.__parseDoubleString(); /* 0.84 */
if (++steps && c === ORD_EXCL) return this.__parseEqualSigns(); /* 0.22 */
if (++steps && c === ORD_AND) return this.__parseSameOrCompound(c); /* 0.18 */
if (++steps && c === ORD_$) return this.__parseIdentifier(); /* 0.09 */
if (++steps && c === ORD_PERCENT) return this.__parseCompound(); /* 0 */
}
} else {
if (++steps && c < ORD_L_A) {
if (++steps && c < ORD_L_0) {
if (++steps && c === ORD_DOT) return this.__parseDot(); /* 4.45 */
if (++steps && c === ORD_CLOSE_PAREN) return this.__plusOne(PUNCTUATOR); /* 3.14 */
if (++steps && c === ORD_OPEN_PAREN) return this.__plusOne(PUNCTUATOR); /* 3.14 */
if (++steps && c === ORD_COMMA) return this.__plusOne(PUNCTUATOR); /* 2.19 */
if (++steps && c === ORD_PLUS) return this.__parseSameOrCompound(c); /* 0.41 */
if (++steps && c === ORD_FWDSLASH) return this.__parseFwdSlash(expressionStart); /* 0.28 */
if (++steps && c === ORD_DASH) return this.__parseSameOrCompound(c); /* 0.15 */
if (++steps && c === ORD_SQUOTE) return this.__parseSingleString(); /* 0.14 */
if (++steps && c === ORD_STAR) return this.__parseCompound(); /* 0.13 */
} else {
if (++steps && c < ORD_L_A_UC) {
if (++steps && c === ORD_SEMI) return this.__plusOne(PUNCTUATOR); /* 2.51 */
if (++steps && c === ORD_IS) return this.__parseEqualSigns(); /* 2.11 */
if (++steps && c === ORD_COLON) return this.__plusOne(PUNCTUATOR); /* 0.71 */
if (++steps && c === ORD_L_0) return this.__parseZero(); /* 0.35 */
if (++steps && c === ORD_L_1) return this.__parseNumber(); /* 0.28 */
if (++steps && c === ORD_QMARK) return this.__plusOne(PUNCTUATOR); /* 0.1 */
if (++steps && c === ORD_LT) return this.__parseLtgtPunctuator(c); /* 0.1 */
if (++steps && c === ORD_L_2) return this.__parseNumber(); /* 0.1 */
if (++steps && c === ORD_L_3) return this.__parseNumber(); /* 0.06 */
if (++steps && c === ORD_GT) return this.__parseLtgtPunctuator(c); /* 0.06 */
if (++steps && c === ORD_L_4) return this.__parseNumber(); /* 0.04 */
if (++steps && c === ORD_L_6) return this.__parseNumber(); /* 0.02 */
if (++steps && c === ORD_L_7) return this.__parseNumber(); /* 0.02 */
if (++steps && c === ORD_L_8) return this.__parseNumber(); /* 0.02 */
if (++steps && c === ORD_L_5) return this.__parseNumber(); /* 0.02 */
if (++steps && c === ORD_L_9) return this.__parseNumber(); /* 0.01 */
} else if (++steps && c <= ORD_L_Z_UC) {
return this.__parseIdentifier();
} else {
if (++steps && c === ORD_CLOSE_SQUARE) return this.__plusOne(PUNCTUATOR); /* 0.72 */
if (++steps && c === ORD_OPEN_SQUARE) return this.__plusOne(PUNCTUATOR); /* 0.72 */
if (++steps && c === ORD_LODASH) return this.__parseIdentifier(); /* 0.47 */
if (++steps && c === ORD_XOR) return this.__parseCompound(); /* 0 */
if (++steps && c === ORD_BACKSLASH) return this.__parseBackslash(); /* 0 */
}
}
} else if (++steps && c <= ORD_L_Z) {
return this.__parseIdentifier();
} else {
if (++steps && c === ORD_CLOSE_CURLY) return this.__plusOne(PUNCTUATOR); /* 1.32 */
if (++steps && c === ORD_OPEN_CURLY) return this.__plusOne(PUNCTUATOR); /* 1.32 */
if (++steps && c === ORD_OR) return this.__parseSameOrCompound(c); /* 0.15 */
if (++steps && c === ORD_TILDE) return this.__parseCompound(); /* 0 */
if (++steps && c === ORD_NBSP) return this.__plusOne(WHITE); /* 0 */
if (++steps && c === ORD_LS) return this.__newline(); /* 0 */
if (++steps && c === ORD_BOM) return this.__plusOne(WHITE); /* 0 */
if (++steps && c === ORD_PS) return this.__newline(); /* 0 */
}
}



// 3.8342642703170005
if (++steps && c < ORD_DASH) {
if (++steps && c === ORD_SPACE) return this.__plusOne(WHITE); /* 20.5 */
if (++steps && c < ORD_FF) {
if (++steps && c === ORD_TAB) return this.__plusOne(WHITE); /* 1.27 */
if (++steps && c === ORD_LF) return this.__newline(); /* 0 */
if (++steps && c === ORD_VTAB) return this.__plusOne(WHITE); /* 0 */
} else if (++steps && c < ORD_OPEN_PAREN) {
if (++steps && c === ORD_CR) return this.__parseCR(); /* 3.47 */
if (++steps && c === ORD_DQUOTE) return this.__parseDoubleString(); /* 0.84 */
if (++steps && c === ORD_EXCL) return this.__parseEqualSigns(); /* 0.22 */
if (++steps && c === ORD_AND) return this.__parseSameOrCompound(c); /* 0.18 */
if (++steps && c === ORD_SQUOTE) return this.__parseSingleString(); /* 0.14 */
if (++steps && c === ORD_$) return this.__parseIdentifier(); /* 0.09 */
if (++steps && c === ORD_PERCENT) return this.__parseCompound(); /* 0 */
if (++steps && c === ORD_FF) return this.__plusOne(WHITE); /* 0 */
} else if (++steps && c <= ORD_CLOSE_PAREN) {
return this.__plusOne(PUNCTUATOR);
} else {
if (++steps && c === ORD_COMMA) return this.__plusOne(PUNCTUATOR); /* 2.19 */
if (++steps && c === ORD_PLUS) return this.__parseSameOrCompound(c); /* 0.41 */
if (++steps && c === ORD_STAR) return this.__parseCompound(); /* 0.13 */
}
} else if (++steps && c < ORD_L_A) {
if (++steps && c === ORD_DOT) return this.__parseDot(); /* 4.45 */
if (++steps && c < ORD_L_A_UC) {
if (++steps && c === ORD_SEMI) return this.__plusOne(PUNCTUATOR); /* 2.51 */
if (++steps && c === ORD_IS) return this.__parseEqualSigns(); /* 2.11 */
if (++steps && c === ORD_COLON) return this.__plusOne(PUNCTUATOR); /* 0.71 */
if (++steps && c < ORD_L_1) {
if (++steps && c === ORD_L_0) return this.__parseZero(); /* 0.35 */
if (++steps && c === ORD_FWDSLASH) return this.__parseFwdSlash(expressionStart); /* 0.28 */
if (++steps && c === ORD_DASH) return this.__parseSameOrCompound(c); /* 0.15 */
} else if (++steps && c <= ORD_L_9) {
return this.__parseNumber(); /* 0.57 */
} else {
if (++steps && c === ORD_LT) return this.__parseLtgtPunctuator(c); /* 0.1 */
if (++steps && c === ORD_QMARK) return this.__plusOne(PUNCTUATOR); /* 0.1 */
if (++steps && c === ORD_GT) return this.__parseLtgtPunctuator(c); /* 0.06 */
}
} else if (++steps && c <= ORD_L_Z_UC) {
return this.__parseIdentifier();
} else {
if (++steps && c === ORD_CLOSE_SQUARE) return this.__plusOne(PUNCTUATOR); /* 0.72 */
if (++steps && c === ORD_OPEN_SQUARE) return this.__plusOne(PUNCTUATOR); /* 0.72 */
if (++steps && c === ORD_LODASH) return this.__parseIdentifier(); /* 0.47 */
if (++steps && c === ORD_BACKSLASH) return this.__parseBackslash(); /* 0 */
if (++steps && c === ORD_XOR) return this.__parseCompound(); /* 0 */
}
} else if (++steps && c <= ORD_L_Z) {
return this.__parseIdentifier();
} else {
if (++steps && c === ORD_CLOSE_CURLY) return this.__plusOne(PUNCTUATOR); /* 1.32 */
if (++steps && c === ORD_OPEN_CURLY) return this.__plusOne(PUNCTUATOR); /* 1.32 */
if (++steps && c === ORD_OR) return this.__parseSameOrCompound(c); /* 0.15 */
if (++steps && c === ORD_NBSP) return this.__plusOne(WHITE); /* 0 */
if (++steps && c === ORD_LS) return this.__newline(); /* 0 */
if (++steps && c === ORD_BOM) return this.__plusOne(WHITE); /* 0 */
if (++steps && c === ORD_TILDE) return this.__parseCompound(); /* 0 */
if (++steps && c === ORD_PS) return this.__newline(); /* 0 */
}



// 4.089422814197396 (unchecked)
if (++steps && c < ORD_PLUS) { /* sum: 48.440000000000005 */
if (++steps && c < ORD_VTAB) { /* sum: 1.89 */
if (++steps && c === ORD_TAB) return this.__plusOne(WHITE); /* 1.89 */
if (++steps && c === ORD_LF) return this.__newline(); /* 0 */
} else { /* sum: 46.550000000000004 */
if (++steps && c === ORD_SPACE) return this.__plusOne(WHITE); /* 29.71 */
if ((++steps && c === ORD_OPEN_PAREN) || (++steps && c === ORD_CLOSE_PAREN)) return this.__plusOne(PUNCTUATOR); /* sum: 9.32 */
if (++steps && c === ORD_CR) return this.__parseCR(); /* 5.14 */
if (++steps && c === ORD_DQUOTE) return this.__parseDoubleString(); /* 1.24 */
if (++steps && c === ORD_EXCL) return this.__parseEqualSigns(); /* 0.33 */
if (++steps && c === ORD_AND) return this.__parseSameOrCompound(c); /* 0.26 */
if (++steps && c === ORD_STAR) return this.__parseCompound(); /* 0.2 */
if (++steps && c === ORD_SQUOTE) return this.__parseSingleString(); /* 0.2 */
if (++steps && c === ORD_$) return this.__parseIdentifier(); /* 0.14 */
if (++steps && c === ORD_PERCENT) return this.__parseCompound(); /* 0.01 */
if (++steps && c === ORD_VTAB) return this.__plusOne(WHITE); /* 0 */
if (++steps && c === ORD_FF) return this.__plusOne(WHITE); /* 0 */
}
} else { /* sum: 51.54 */
if (++steps && c < ORD_L_A) { /* sum: 26.740000000000002 */
if (++steps && c < ORD_L_A_UC) { /* sum: 20.69 */
if (++steps && c === ORD_DOT) return this.__parseDot(); /* 6.59 */
if (++steps && c === ORD_SEMI) return this.__plusOne(PUNCTUATOR); /* 3.71 */
if (++steps && c === ORD_COMMA) return this.__plusOne(PUNCTUATOR); /* 3.24 */
if (++steps && c === ORD_IS) return this.__parseEqualSigns(); /* 3.13 */
if (++steps && c === ORD_COLON) return this.__plusOne(PUNCTUATOR); /* 1.05 */
if (++steps && c >= ORD_L_1 && ++steps && c <= ORD_L_9) return this.__parseNumber(); /* sum: 0.8300000000000001 */
if (++steps && c === ORD_PLUS) return this.__parseSameOrCompound(c); /* 0.61 */
if (++steps && c === ORD_L_0) return this.__parseZero(); /* 0.53 */
if (++steps && c === ORD_FWDSLASH) return this.__parseFwdSlash(expressionStart); /* 0.41 */
if (++steps && c === ORD_DASH) return this.__parseSameOrCompound(c); /* 0.22 */
if (++steps && c === ORD_QMARK) return this.__plusOne(PUNCTUATOR); /* 0.15 */
if (++steps && c === ORD_LT) return this.__parseLtgtPunctuator(c); /* 0.14 */
if (++steps && c === ORD_GT) return this.__parseLtgtPunctuator(c); /* 0.08 */
} else if (++steps && c <= ORD_L_Z_UC) { /* sum: 3.2300000000000004*/
return this.__parseIdentifier();
} else { /* sum: 2.8200000000000003 */
if (++steps && c === ORD_OPEN_SQUARE) return this.__plusOne(PUNCTUATOR); /* 1.06 */
if (++steps && c === ORD_CLOSE_SQUARE) return this.__plusOne(PUNCTUATOR); /* 1.06 */
if (++steps && c === ORD_LODASH) return this.__parseIdentifier(); /* 0.7 */
if (++steps && c === ORD_BACKSLASH) return this.__parseBackslash(); /* 0 */
if (++steps && c === ORD_XOR) return this.__parseCompound(); /* 0 */
}
} else if (++steps && c <= ORD_L_Z) { /* sum: 20.679999999999996*/
return this.__parseIdentifier();
} else { /* sum: 4.12 */
if (++steps && c === ORD_OPEN_CURLY) return this.__plusOne(PUNCTUATOR); /* 1.95 */
if (++steps && c === ORD_CLOSE_CURLY) return this.__plusOne(PUNCTUATOR); /* 1.95 */
if (++steps && c === ORD_OR) return this.__parseSameOrCompound(c); /* 0.22 */
if (++steps && c === ORD_BOM) return this.__plusOne(WHITE); /* 0 */
if (++steps && c === ORD_TILDE) return this.__parseCompound(); /* 0 */
if (++steps && c === ORD_NBSP) return this.__plusOne(WHITE); /* 0 */
if (++steps && c === ORD_LS) return this.__newline(); /* 0 */
if (++steps && c === ORD_PS) return this.__newline(); /* 0 */
}
}