Given an expression 'r' containing a possessive qualifier, for example: "[ab]*+b"
Given 'r₁' the repeated sub-expression with a possessive qualifier, in the above example "[ab]"
Given 'r₂' the continuation after the repetition, in the above example "b"
Then the regular expression will always fail if every possible match of 'r₂' has a prefix that can be matched by 'r₁'.
Test cases:
"x*+x" // Noncompliant "x*+xy" // Noncompliant "(xy)*+xy" // Noncompliant "(xy)*+xyz" // Noncompliant "(xy)*+x" // Compliant "(xy|ab)*+xy" // Noncompliant "(xy)*+(xy|ab)" // Compliant, but the xy is dead code "(xy|ab)*+(xy|ab)" // Noncompliant "(xy|a)*+(xy|ab)" // Noncompliant "[aeoiu]*+[a-z]" // Compliant possible - the [a-z] can never match vowels, but that’s likely intended "[a-z]*+[aeiou]" // Noncompliant
Verification algorithm:
boolean doesRepetitionContinuationAlwaysFail(RepetitionTree repetitionTree) { return repetitionTree.getQuantifier().getModifier() == Modifier.POSSESSIVE && isSupersetOfPrefix(repetitionTree, repetitionTree.continuation(), repetitionTree.continuation(), new HashSet<>()); }
- contributes to
-
MMF-2182 Help Java developers writing regexp running fast, with the correct amount of resources and really doing what developers intended
-
- Resolved
-
- depends upon
-
SONARJAVA-3549 Add support for automata-based analyses for regular expressions
-
- Closed
-
-
SONARJAVA-3564 Implement intersects and supersetOf helper for regex automata
-
- Closed
-
- relates to
-
RSPEC-5994 Regex patterns following a possessive quantifier should not always fail
- Active
- supercedes
-
SONARJAVA-3475 Expand the scope of S5840
-
- Closed
-