[New Feature] Add regular expression support

[lasinicl]

This consists of 4 sub-tasks.

• Specifying regular expression syntax and semantics
• Adding regular expression type
• Adding langlib functions using regular expressions
• Adding minimal Unicode support to lang.string

1. Specifying regular expression syntax and semantics
The syntax for a regular expression is as follows.

RegExp := ReDisjunction

ReDisjunction := ReSequence ("|" ReSequence)*
ReSequence := ReTerm*
ReTerm :=
   ReAtom [ReQuantifier]
   | ReAssertion
ReAssertion := "^" | "$"

ReQuantifier := ReBaseQuantifier ["?"]

ReBaseQuantifier :=
   "*"
  | "+"
  | "?"
  | "{" Digit+ ["," Digit*] "}"

ReAtom :=
   ReLiteralChar
   | ReEscape
   | "."
   | "[" ["^"] [ReCharSet] "]" 
   | "(" ["?" ReFlagsOnOff ":"] ReDisjunction ")"

ReLiteralChar := ^ ReSyntaxChar

ReSyntaxChar :=
  "^" | "$" | "\" | "." | "*" | "+" | "?"
  | "(" | ")" | "[" | "]" | "{" | "}" | "|"

ReEscape :=
   NumericEscape
   | ControlEscape
   | ReQuoteEscape
   | ReUnicodePropEscape
   | ReSimpleCharClassEscape

ReQuoteEscape := "\" ReSyntaxChar
ControlEscape := "\r" | "\n" | "\t"

ReSimpleCharClassEscape := "\" ReSimpleCharClassCode

ReSimpleCharClassCode := "d" | "D" | "s" | "S" | "w" | "W"

ReUnicodePropertyEscape := "\" ("p" | "P") "{"ReUnicodeProperty "}"

ReUnicodeProperty :=  ReUnicodeScript | ReUnicodeGeneralCategory

ReUnicodeScript := "sc=" ReUnicodePropertyValue

ReUnicodePropertyValue := ReUnicodePropertyValueChar+

ReUnicodePropertyValueChar := AsciiLetter | Digit | "_"

ReUnicodeGeneralCategory := [gc=] ReUnicodeGeneralCategoryAbbr

ReUnicodeGeneralCategoryAbbr :=
 L [ u | l | t | m | o ] 
 | M [ n | c | e ] 
 | N [ d | l | o ] 
 | S [ m | c | k | o ] 
 | P [ c | d | s | e | i | f | o ] 
 | Z [ s | l | p ] 
 | C [ c | f | o | n ] 

ReCharSetAtom :=
  ReCharSetLiteralChar
  | ReEscape
  | "\-"

ReCharSetLiteralChar := ^ ("\" | "]" | "-")

ReCharSet :=
  ReCharSetAtom
  | ReCharSetRange [ReCharSet]
  | ReCharSetAtom ReCharSetNoDash

ReCharSetRange := ReCharSetAtom "-" ReCharSetAtom

ReCharSetNoDash :=
  ReCharSetAtom
  | ReCharSetRangeNoDash [ReCharSet]
  | ReCharSetAtomNoDash ReCharSetNoDash
  
ReCharSetRangeNoDash := ReCharSetAtomNoDash "-" ReCharSetAtom

ReFlagsOnOff := ReFlags ["-" ReFlags]
ReFlags := ReFlag*
ReFlag :=
  ReMultilineFlag
  | ReDotAllFlag
  | ReIgnoreCaseFlag
  | ReCommentFlag

ReMultilineFlag := "m"
ReDotAllFlag := "s"
ReIgnoreCaseFlag := "i"
ReCommentFlag := "x"

• The semantics are as defined by ECMAScript with the u RegExp flag - https://tc39.es/ecma262/#sec-parsepattern
• Semantics of \p and \P depend on unicode 10
• . matches any character other than LF (0xA) and CR (0xD)
• \s matches TAB (0x9), SPACE (0x20), LF (0xA) and CR (0xD); (as in ECMAScript, \S matches any character not matched by \s)
• In a template, insertions will be allowed where ReAtom can occur, and effectively surround the inserted regexp with (?: and )
• In ReFlagsOnOff , m, s and i flags correspond to flags specified in ECMAScript after the closing /. But the flags apply only within the scope of the group in which the flags are specified. The x flag causes whitespace outside character classes (which should be Ballerina white space) and comments (starting with # and continuing to the end of the line) to be ignored as the regexp is parsed (this allows a complex regexp to be broken up over multiple lines).

Please share your thoughts on this.

Note: Details on the other subtasks will be updated in due course.

[pcnfernando]

We'll have to create a composite grammar from the parts specified in the spec issue and https://tc39.es/ecma262/#prod-Pattern. Some requirements not in grammar are as in ECMAScript spec.

[pcnfernando]

Extracting from ballerina-platform/ballerina-spec#1132 (comment)
(let's use re tag until its decided )

regexp-constructor-expr := re BacktickString

[pcnfernando]

@lasinicl lets add few regexp samples supported with the mentioned syntax

[pcnfernando]

// TOM or JERRY
// Next, followed by any character that appears one or more times.
// Next, followed by CAT. ignore the case for CAT
// text: "I saw TOM, TOM is a cat"
// matchedText: "TOM, TOM is a cat"
string:RegExp letters = re `(TOM|JERRY).+(?i:CAT)`;

[lasinicl]

Some examples supported with the new syntax

re `^`
re `^AB`
re `$`
re `AB$`

re `ABCD|^AB|AB$`

re `^AB|AB$`
re `ABCD`

re `A*`
re `B+`
re `AB?`
re `A{2}`
re `A{2,}`
re `a{1,3}`

re `A*?`
re `B+?`
re `AB??`
re `A{2}?`
re `A{2,}?`
re `a{1,3}?`

re `.A`

re `[]`
re `[^]`
re `[ABC]`
re `[^ABC]`

re `\u0000`
re `\r`
re `\n`
re `\t`
re `\^`
re `\$`
re `\d`
re `\D`
re `\s`
re `\S`
re `\w`
re `\W`

re `\p{sc=Latin}`
re `\p{sc=123}`
re `\p{sc=_}`

re `(,)`
re `(?m:A)`
re `(?ms:A)`
re `(?m-i:A)`
re `(?ms-ix:A)`

[pcnfernando]

[lochana-chathura]

Is this about how we tokenize this? Can't we allow this in the RegExprLexer?

[pcnfernando]

The regexp syntax will be translated to Java syntax. But there are some differences as explained in ballerina-platform/ballerina-spec#1125 (comment).
Hence, instead of handling the regexp-template-expr simply as a literal, we'll be maintaining separate nodes and map to what we are supporting

[pcnfernando]

Feature merged through #37916

[pcnfernando]

Pending tasks

• Improve parser logic ([Task]: Improve RegExp parser #37735)
• Parse compound value using regexp parser after insertions are handled ([Bug]: Invalid insertions are not handled in regular expressions #38069)
• Const expr support (Add regular expression type to language ballerina-spec#1132 (comment))
• Add conformance tests for regexp type [Task]: Add spec conformance tests for regular expressions #38073
• Add conformance tests for regexp langlib [Task]: Add spec conformance tests for regexp langlib #38074
• Add language server (completion/goto def/references) support for regexp [New Feature]: Provide completion and related LS support for new regex support #38095