Support More Regex Related Linting Rules

[notJoon]

Description

Regular expressions (regex) can potentially use a lot of memory unintentionally. Therefore, it would be useful if the linter could detect this, and we could consider the following elements:

Avoid Catastrophic Backtracking

Some regex patterns migh cause exponential execution time as input size increase. For example, a pattern like ^(a+)+$ can cause performance issues with input like aaaaX. This pattern should be simplified like ^a+$.

Detect Greedy Quantifier on Large Input

Greedy quantifier can use a lot of memory on large input. For example, use pattern .*? instead of .* to make it non-greedy.

Detect Unnecessary Capture Group

Capture groups are use memory, so they should be removed when not really needed.

We can use (?:...) pattern when capturing is not necessary

// Unnecessary capture group
re := regexp.MustCompile(`(abc)`)
// Improved version
re := regexp.MustCompile(`(?:abc)`)

Minimize Regex (regex => NFA => DFA)

Go seems to simplify internally, by using regexp/syntax package. but need to check if the same applies to gno.

If it possible to minimize the given regex while maintain the its functionalities, we must show the minimized regex as suggestion. But not important features (YAGNI alert).

Related

#43