feat(linter): regex parser

[ubugeeei]

Implement a regular expression parser equivalent to @eslint-community/regexpp.

Todo:

• [ ] Consider how to handle Maneren's branch
  • [ ] Check if any part can be integrated
  • [ ] See if the remaining issues can be shared in this repository
• [ ] Document the rules requiring the implementation of the parser as pending

Ref: https://github.com/web-infra-dev/oxc/issues/611

[Boshen]

Let's do this incrementally with proper testing, we can cherry-pick some of the code from Maneren's branch

My requirements:

1. 100% test coverage
2. Good documentation
3. use the same infra as oxc_parser, i.e. allocate the AST on oxc_allocator for maximum performance, have lexer / parser phase for maximum code control

[ubugeeei]

Roadmap (Draft) (For Contributors)

• [x] init crate -> https://github.com/oxc-project/oxc/pull/1500
• [x] Definition of AST -> https://github.com/oxc-project/oxc/pull/1500
  • [x] Understanding of oxc infrastructure
    • [x] Understanding of oxc_allocator
    • [x] Understanding of oxc_span
  • [x] Writing in Rust Refer to https://github.com/eslint-community/regexpp/blob/2e8f1af992fb12eae46a446253e8fa3f6cede92a/src/ast.ts
• [ ] Lexer (?)
  • [ ] Reading and understanding points to note (mainly performance requirements) from https://oxc-project.github.io/javascript-parser-in-rust/en/docs/lexer
  • [ ] Enumeration of Tokens
  • [ ] Implementation of Lexer (If possible, I would like to submit small PRs by dividing)
    • [ ] Writing tests (?)
• [ ] Parser, Validator
  • [ ] Implementing incrementally by narrowing down the target AST ※ Tasks will be added as needed
    • [ ] Understanding test262 https://github.com/tc39/test262/tree/main/test/language/literals/regexp
    • [ ] Implementation of parser and test
• [ ] Visitor

[Boshen]

@Ubugeeei Nice work! I hope your are learning a lot.

[IWANABETHATGUY]

Hello, I saw it has been 3 weeks since your last pr, are you still interested in this feature, or can I continue your work?

[Boshen]

@Ubugeeei is too busy with other stuff (vapor mode I guess?). Feel free to assign this to yourself @IWANABETHATGUY

[ubugeeei]

@IWANABETHATGUY

Hello, I saw it has been 3 weeks since your last pr, are you still interested in this feature, or can I continue your work?

Ah, sorry, I completely missed this comment. I was planning to work on it when I had time, if it was still pending, but I haven't been able to do anything yet, so please go ahead, there's no problem at all.

(My time bottleneck is my main job... Actually, Vapor often has discussions that are put on hold, so it's not that busy yet..)

[maurice]

This seems like the kind of self-inflicted torture that I'd enjoy. May I have a go at moving it forward?

[Boshen]

@IWANABETHATGUY have you started working on this?

[IWANABETHATGUY]

@IWANABETHATGUY have you started working on this?

WIP

[Boshen]

@maurice it seems like @IWANABETHATGUY is working on it, I'll let him coordinate the tasks.

[leaysgur]

I have quick investigated the current status of this issue and the rules related to @eslint-community/regexpp, so I am leaving a NOTE...

Rules related to regexpp

ESLint uses an ECMAScript RegExp parser implementation called @eslint-community/regexpp.

There are currently 10 rules implemented that depend on it.

• eslint/no-misleading-character-class
  • Enforce u flag, \q{} with v flag
  • parsePattern(), onCharacterClassEnter()
• eslint/no-invalid-regexp ( #611 )
  • Prevent syntax error at runtime
  • validatePattern(), validateFlags()
• eslint/no-useless-backreference
  • Report backrefs refer to another alternatives, appers later, etc
  • parsePattern(), onBackreferenceEnter()
  • ⚠️ Need to resolve ref > groups
• eslint/prefer-named-capture-group
  • Prefer named over normal(indexed) capture group
  • parsePattern(), onCapturingGroupEnter()
  • ⚠️ Only for fixer
• eslint/prefer-regex-literals
  • Prefer /abc/i over new RegExp("abc", "i")
  • validatePattern(), validateFlags(), onCharacterEnter()
• eslint/require-unicode-regexp
  • Enforce using u or v flags
  • validatePattern()
  • ⚠️ Only for fixer
• eslint/no-control-regex
  • Disallow control characters and some escape characters
  • onCharacter()
• eslint/no-empty-character-class
  • Disallow empty character class like /a[]/
  • onCharacterClassEnter()
• eslint/no-useless-escape
  • Disallow unnecessary escape characters
  • parsePattern(), onCharacterClass(Enter|Leave)(), onExpressionCharacterClass(Enter|Leave)(), onCharacterEnter()
• eslint/no-regex-spaces
  • Disallow multiple consecutive spaces
  • parsePattern(), onCharacterClassEnter()

https://github.com/search?q=repo%3Aeslint%2Feslint+%28%22%40eslint-community%2Fregexpp%22+OR+%22utils%2Fregular-expressions%22%29&type=code

And there is a related plugin ota-meshi/eslint-plugin-regexp too. / #3263

Implementation status of oxlint

• It seems that 4/10 rules are already implemented:
  • eslint/no-control-regex
    • Already implemented with regex crate
  • eslint/no-empty-character-class
    • Already implemented with regex crate
  • eslint/no-useless-escape
    • Already implemented with manual char checking
  • eslint/no-regex-spaces
    • Already implemented with manual char checking

But it should be re-implemented with regexpp for better performance.

What to do

• Complete regexpp port for Rust #3824
• Integrate it into AST visiting for oxlint
• Re-implement already implemented 4 rules
• Implement the remaining 6 rules
• Implement eslint-plugin-regex...?

[Boshen]

Linting regexp may be doable without a parser, but it'll definitely be easier to lint by visiting an AST.

I still want to regex parser for oxc for maximum performance gains 😅 We should only parse the regex once and visit the AST once for linting.

There completeness, there is also https://github.com/ota-meshi/eslint-plugin-regexp from the same author.

[leaysgur]

We should only parse the regex once and visit the AST once

Ah~, I see, that makes sense! I've updated my comment.

ota-meshi/eslint-plugin-regexp

I didn't know this... And this looks also... challenging! 😂

[Boshen]

@leaysgur The current blocking task is the parser, we can always distribute the linter rules to future contributors. You don't need to implement the linter rules like you did with the jsdoc plugins 😅

[leaysgur]

Yes, I understand. I have finally grasped the situation now. 👍🏻

you did with the jsdoc plugins

🙈

---

Now, I will tackle the implementation of the parser. (Since it seems like many people are actively developing the playground. 👀 )

I'm going to read the regexpp implementation and to spend a few days for the oxc_parser architecture and #2030.

[leaysgur]

@Boshen

I'm going through the code and written a bit myself, then I'd like to confirm a few things.

Is a Lexer necessary?

In the original implementation of regexpp, it seems to handle characters directly without using Tokens. To create something that works for now, I'm thinking of following the original approach and not implementing a Lexer.

What do you think?

Support for strict mode (annexB) and various ecmaVersions?

These options seem to significantly affect behavior and implementation. What should we do about them? One option might be to always support only the latest version... 🤔

[Boshen]

Is a Lexer necessary?

Probably not, since there is no whitespace or semi colons like JavaScript.

We can try one without a lexer.

Support for strict mode (annexB) and various ecmaVersions?

We always support the latest ecma version, just like our parser.

For strict mode, you may leave them out from your first version.

[leaysgur]

OK, thanks! 🙏 I'll try it minimally for the first step.

[Boshen]

@leaysgur Do you intend to start from scratch? You can start from a new branch by coping over some of the code from https://github.com/oxc-project/oxc/pull/2030

Once you have something, I'll help you with the test infrastructure - running the regex parser on all regexes from test262, babel and typescript.

[leaysgur]

I pushed current progress #3824 , of course it is WIP... 😴

Do you intend to start from scratch?

Maybe yes. But I will refer to or pick up on them as necessary.

Currently, they are in /_oxc_js_regex dir, just for reference.

I'll help you with the test infrastructure - running the regex parser on all regexes from test262, babel and typescript.

That is very helpful! I was just thinking about what to do. 😅

[leaysgur]

Progress update:

Implementation is ongoing. 🚧 #3824 Most of the syntax is implemented, except for [character_class] and v flag related stuff.

But there's still some work to complete.(Early errors, test262 tests and integration to Linter, etc...)

While working on this, I went through the specification and the regexpp implementation several times. As a result, I realized that the regexpp implementation may not be fully compliant with the specification.

• There are some patterns where the implementation is not complete
• Some parts simply aren't up to date

Also, for ease of rewriting in Rust, it cannot be implemented as a complete 1-to-1 copy. (since it relies heavily on the dynamic nature of JavaScript)

For these reasons, I'm thinking of abandoning original goal of re-implementing regexpp in Rust and focusing on implementing it as an original specification-compliant parser. (It may not have cared about compatibility in the first place, though 🤔 )

Fortunately or unfortunately, there are no de-facts like ESTree, and I think there are any problems, but just in case, I'll look at the specific usecases of the Lint rules that depend on regexpp first.

---

I'll look at the specific usecases of the Lint rules that depend on regexpp first.

All usecase were just as expected. I updated my comment above. ⬆️

[Boshen]

and focusing on implementing it as an original specification-compliant parser

👍 always bet on the spec!

[leaysgur]

Progress update:

Implementation part

https://github.com/oxc-project/oxc/pull/3824

Finally completed all ES2024 specs! 🎉

However, we noticed that while it supports the literal pattern /(.)\1/, it misbehaves the pattern for new RegExp("(.)\\1") whose strings are escaped...

In JavaScript, \\ is treated as \. But in Rust, \\ is \\.

Now I'm thinking how to cope with this. Perhaps a pre-treatment, such as a lexer for RegExp parser is required?

Integration part

https://github.com/oxc-project/oxc/pull/4242

RegExp parser is now integrated in oxc_parser itself. It emits error when invalid RegExp literal is found.

But how to use parsed result in user land like linter is still considering.

@Boshen Could you please take a look these and give your feedback if you have time? 🙏🏻

[Boshen]

Progress update:

Implementation part

#3824

Finally completed all ES2024 specs! 🎉

However, we noticed that while it supports the literal pattern /(.)\1/, it misbehaves the pattern for new RegExp("(.)\\1") whose strings are escaped...

In JavaScript, \\ is treated as \. But in Rust, \\ is \\.

Now I'm thinking how to cope with this. Perhaps a pre-treatment, such as a lexer for RegExp parser is required?

Integration part

#4242

RegExp parser is now integrated in oxc_parser itself. It emits error when invalid RegExp literal is found.

But how to use parsed result in user land like linter is still considering.

@Boshen Could you please take a look these and give your feedback if you have time? 🙏🏻

Thank you for the tremendous effort! I'll take a look at the problems soon.

[leaysgur]

Progress update:

• oxc_regular_expression crate is finally merged into main branch ✨
• Now oxc_parser can emit syntax error if invalid regex literals are found
  • This is optional https://github.com/oxc-project/oxc/blob/f73d486d25055e7b1f42a5110f2e942fffc0f90c/crates/oxc_parser/src/lib.rs#L109-L112
  • Only /literals/v is checked, RegExp("string", "v") is not checked

However, to officially use parsed AST in linter, there is a little more to do. e.g. #5060 , how to use it with RegExp("string")?, etc.

As for the remaining tasks, we can address them in a separate issue. But for now, can't we close this long-lived issue? 😃

[Boshen]

Thank you again @leaysgur, and also everyone who participated in this. Thank you all!