`>>` is cheaper than `>>>` because `>>` produces a 32-bit _signed_ integer which is V8's native number type (SMI). `>>>` produces a 32-bit _unsigned_ integer, which needs to be boxed and stored on the heap.
Source text in raw transfer is limited to 1 GiB, and therefore source offsets, number of lines, number of tokens, and number of comments after all less than `1 << 30`. Therefore even the sum of 2 of them cannot reach `1 << 31` (the maximum positive integer which can be stored as a positive signed 31-bit int. Therefore it's safe to use `>>` in these binary loops.
Fix a JS-side memory leak from tokens and comments.
## The problem
V8 uses "SlicedString" optimization to avoid copying string data. `sourceText.slice(10, 20)` does not copy bytes 10..20 to a new string, but references the original string data of `sourceText` (much like `&str` in Rust).
#19978 and #20362 introduced caching and recycling of `Token` and `Comment` objects. This was a large performance gain.
However, it contained a flaw. The problem is that `Token` objects now live forever, and they contain little slices of the source text in their `value` property. This means they prevent the source text which they reference from being garbage-collected, and therefore it lives forever too (or at least until another file with an equal or greater number of tokens overwrites the `value` property of all the `Token` objects).
## Solution in this PR
Fix this by setting the `value` property of all `Token`s and `Comment`s to `null` after linting a file in `resetTokens` and `resetComments`.
## Implementation details
This requires some additional book-keeping to track which tokens have been deserialized and which haven't, so that `resetTokens` / `resetComments` do the minimum amount of work necessary - only resetting tokens / comments which actually had their `value` property set in the first place.
The indexes of tokens are stored in 2 x `Uint32Array`s `deserializedTokenIndexes` and `deserializedCommentIndexes`. A simpler solution would have been to store the `Token` / `Comment` objects themselves in a plain `Array`, but `Uint32Array` has 3 advantages:
* 4 bytes to store index (`u32`) per token/comment, instead of 8 bytes to store a pointer to the `Token` / `Comment` itself.
* Faster to write to `Uint32Array` - no write barrier checks.
* On GC runs, a `Uint32Array` is known not to contain references to any other heap objects, so GC tracing doesn't need to walk it, which it would with an `Array`.
`Uint32Array` does have one disadvantage over `Array`:
* 1 level of indirection in `resetTokens` / `resetComments`. You have to read the index, then index in to `cachedTokens` array to get the `Token` object, in order to reset it.
The latter will only have a significant effect when there's a large number of tokens/comments to reset. We avoid this in the worst case where *all* tokens have been deserialized (e.g. by accessing `ast.tokens`). When `allTokensDeserialized === true`, `resetTokens` just loops through `cachedTokens` itself, and ignores the `Uint32Array` entirely.
## Future potential optimizations
It's probably not necessary to reset all tokens quite so aggressively when all tokens have been deserialized. If a rule has done that on 1 file, chances are it'll do it again on the next file, at which point most `Token`s get their `value` property overwritten with slices of *that* source text anyway.
It's acceptable for source texts to hang around in memory for a bit, just not forever. We could choose to do token resetting only e.g. once every 10 files, to reduce the cost.
Possibly clean-up operations could also run in next tick, so they happen in parallel while Rust side is prepping the next file to send over to JS, rather than blocking.
Performance improvement to tokens and comments APIs.
## The problem
Previously, all tokens and comments methods would deserialize *all* tokens/comments into an array of `Token` / `Comment` / `Token | Comment` objects, and then binary search through those arrays to find the token(s) / comment(s) they're looking for.
This has 2 major disadvantages:
1. Files typically contain *a lot* of tokens (even more than the number of AST nodes). Deserializing them all is very costly (up to 30% of total Oxlint runtime when run with only a JS rule which just calls a tokens-related method).
2. The binary searches these methods do are quite expensive. Even in TurboFan-optimized code, accessing `token.start` involves getting pointer to the `Token` object from the `tokens` array, an "is this object a `Token`?" safety check, then reading the `start` field from the `Token` - all just to access a single `u32`, and that happens over and over.
## This PR's solution
Solve both these problems by making tokens and comments methods read `start` / `end` offsets directly from the buffers which contain the tokens/comments data.
This data is tightly packed in memory, and strongly typed (read from `Uint32Array`s), so getting `start` / `end` of a token requires no indirection and no type checks.
More importantly, it removes the need to deserialize all tokens / comments upfront. The desired token(s) are located, touching only the buffer, and then *only* the ones which need to be returned to rule code are deserialized into JS objects.
If a rule accesses `ast.tokens`, `ast.comments`, or `sourceCode.tokensAndComments` then all tokens / comments need to be deserialized, as they're all returned to the rule as an array - but that's unavoidable. This PR doesn't make that any cheaper, but it doesn't make it measurably more costly either.
But where no rule requires the full array of tokens / comments, and they only use token/comment search methods (e.g. `getFirstToken`, `getCommentsBefore`), a great deal of work will be saved. This covers the vast majority of rules.
## Implementation details
The main complication is the `includeComments` option to tokens methods. When `true`, search needs to be over a combined set of both tokens and comments.
When `includeComments: true` option is passed to a tokens method, a buffer is created containing data about all tokens and comments, interleaved in source code order. This buffer can then be used for binary search in tokens methods.
Whether each token / comment has been deserialized already or not is tracked by a "deserialized" flag in the tokens/comments buffers. Each token / comment in the buffer is 16 bytes. This flag lives in byte 15. For tokens, this byte is always already 0 in the buffer when it arrives from Rust side. For comments, we manually set `comment.content = CommentContent::None;` for every comment on Rust side. `comment.content` is positioned at byte 15 in the `Comment` struct, and `CommentContent::None` is stored as 0.
## Possible future improvements
### SoA storage
Binary search operates only on `start` field of tokens / comments, which are 16 bytes apart in the buffer. It would be more efficient if tokens were stored in struct-of-arrays (SoA) style so all `start` values were tightly packed together. This would reduce CPU cache misses in the hot loops of binary searches.
### Pre-compute tokens-and-comments buffer on Rust side
The buffer containing tokens and comments, required to support `includeComments: true`, is currently generated on JS side (but lazily). We could move that to Rust side, which would be faster. However, it might be redundant work in many cases because the buffer is only required if a rule uses `includeComments: true`.
We could alternatively keep the laziness optimization, by calling back into Rust to build the buffer on demand - but JS-Rust calls have a cost too. Maybe communicating via `Atomics` would be faster than an actual function call?
If we had a way to share buffers with WASM, optimal solution might be to generate the buffer lazily (as now) but in WASM, which would be faster for this kind of pure number-crunching, but without the overhead of calling into Rust.
#20310 and #20311 reduce code size and complexity by moving binary search routine which is used in all tokens and comments methods into a shared function `firstTokenAtOrAfter`.
However, as noted in #20310, the downside of that change is a perf hit due to the cost of function calls.
This PR fixes that regression by adding a TSDown plugin to the build which inlines the body of `firstTokenAtOrAfter` into all the call sites in tokens and comments methods. The net result is that the final code in bundled output is almost identical to before #20310, but the source code is much shorter and easier to understand.
This unlocks a large optimization which will follow in a future PR (see #20310 for more details).
All tokens methods contain binary searches through `tokens` array. The code is repeated inline in every method to avoid the cost of function calls, but the downside is that it makes the code verbose and hard to understand.
Break out the binary search logic into a function which is used in every method.
This is a perf regression due to the extra cost of function calls, but that is fixed in #20312 by a TSDown plugin which inlines `firstTokenAtOrAfter` into all call sites, producing code in final build that is almost identical to before this PR.
This change makes the code shorter and easier to understand, but main motivation is to enable switching in a future PR to performing the binary searches reading directly from the buffer, without touching token objects. This means that tokens can be deserialized lazily, instead of having to deserialize the entire tokens array eagerly as we do now. This will be a large perf gain, but would be impractically complex if the convoluted buffer-search logic had to be repeated in 20+ places.
Many token methods return either `Token` or `Token | Comment` depending on whether `includeComments` option is passed. Make the return type of these methods match this behavior.
It's annoying otherwise as you call e.g. `sourceCode.getFirstToken(node)` and then it's a type error to access the `regex` field on the token, because `Comment`s don't have this property (whereas `Token` does).
Pure refactor. `tokens.ts` was getting too large. Split it into 2 files:
* `tokens.ts`: Tokens lifecycle methods - initialization, deserialization, and reset.
* `tokens_methods.ts`: Public methods on `SourceCode` e.g. `sourceCode.getFirstToken`.
Boshen