RunDevelopment/eslint-plugin-clean-regex

Detect non-disjoint alternatives

RunDevelopment opened this issue · 2 comments

To prevent exponential backtracking, the alternatives of a quantified group have to be disjoint (aside from the empty string and assertions).

For a RE /(A1|A2|...|An)*/, its alternatives have to disjoint such that:
∀ Aj: ( L(/(A1|...|Aj-1|Aj+1|An)*/) ∩ L(/Aj*/) ) \ {ε} = ∅ where L is a function which returns the language of the given RE and ε is the empty string.

This will be difficult to implement because we need to be able to construct an NFA from the RE and assertions don't make this any easier.

Test case: (?=[\t ]+[\S]{1,}|[\t ]+['"][\S]|[\t ]+$|$)

Resolved by #22.