import { CleanRegexRule , createRuleListener , getDocUrl } from "../rules-util" ; import { mention } from "../format" ; import { elementsToCharacterClass , FirstConsumedChar , getFirstCharConsumedBy , getParentPrefixAndSuffix , matchingDirection , underAStar , } from "../ast-util" ; import { Alternative , Assertion , CapturingGroup , CharacterClassElement , Element , Flags , Group , Pattern , } from "regexpp/ast" ; import { CharSet } from "refa" ; import { findIndex , findLastIndex , Simple } from "../util" ; import { toCharSet } from "../char-util" ; type CharElementArray = Readonly < Simple < CharacterClassElement > > [ ] ; interface CharacterAlternative { isCharacter : true ; alternative : Alternative ; elements : CharElementArray ; char : CharSet ; } interface NonCharacterAlternative { isCharacter : false ; alternative : Alternative ; } interface GenericCharAlt { isCharacter : true ; raw : string ; char : CharSet ; elements : CharElementArray ; } interface GenericNonCharAlt { isCharacter : false ; raw : string ; firstChar : FirstConsumedChar ; } /**
 * Tries to convert the given element into character class elements.
 *
 * The returned array may be empty.
 */ function toCharacterClassElement ( element ) { if ( element . type === "CharacterSet" ) { if ( element . kind === "any" ) { return null ; } else { return [ element ] ; } } else if ( element . type === "CharacterClass" ) { if ( ! element . negate ) { return [ ... element . elements ] ; } if ( element . elements . length === 1 && element . elements [ 0 ] . type === "CharacterSet" ) { const set = element . elements [ 0 ] ; if ( set . kind === "property" ) { const p = set . raw . substr ( 0 , 2 ) ; const raw = ( set . negate ? p . toLowerCase ( ) : p . toUpperCase ( ) ) + set . raw . substr ( 2 ) ; return [ { type : "CharacterSet" , kind : set . kind , key : set . key , value : set . value , negate : ! set . negate , raw , } , ] ; } else { const raw = set . negate ? set . raw . toLowerCase ( ) : set . raw . toUpperCase ( ) ; return [ { type : "CharacterSet" , kind : set . kind , negate : ! set . negate , raw , } , ] ; } } return null ; } else if ( element . type === "Character" ) { return [ element ] ; } else { return null ; } } /**
 * Given alternatives, this will return an array in which each alternative is categorized by whether it contains only a
 * single character (that can be combined with other characters in a character class) or not.
 */ function categorizeAlternatives ( alternatives , flags ) { return alternatives . map ( alternative => { if ( alternative . elements . length === 1 ) { const elements = toCharacterClassElement ( alternative . elements [ 0 ] ) ; if ( elements ) { return { isCharacter : true , alternative , elements , char : toCharSet ( elements , flags ) , } ; } } return { isCharacter : false , alternative , } ; } ) ; } function containsCharacterClass ( alts ) { for ( const alt of alts ) { if ( alt . isCharacter && alt . alternative . elements . length === 1 ) { const e = alt . alternative . elements [ 0 ] ; if ( e . type === "CharacterClass" ) { return true ; } } } return false ; } function combineElements ( alternatives ) { const elements = [ ] ; for ( const a of alternatives ) { if ( a . isCharacter ) { elements . push ( ... a . elements ) ; } } return elements ; } function toGenericAlts ( alternatives , flags ) { const result = [ ] ; for ( const a of alternatives ) { if ( a . isCharacter ) { result . push ( { isCharacter : true , elements : a . elements , char : a . char , raw : a . alternative . raw , } ) ; } else { result . push ( { isCharacter : false , firstChar : getFirstCharConsumedBy ( a . alternative , matchingDirection ( a . alternative ) , flags ) , raw : a . alternative . raw , } ) ; } } return result ; } function optimizeCharacterAlternatives ( alternatives , flags , reorder ) { function merge ( a , b ) { const elements = [ ... a . elements , ... b . elements ] ; return { isCharacter : true , char : a . char . union ( b . char ) , elements , raw : elementsToCharacterClass ( elements ) , } ; } function mergeRuns ( ) { for ( let i = 1 ; i < alternatives . length ; i ++ ) { const prev = alternatives [ i - 1 ] ; const curr = alternatives [ i ] ; if ( prev . isCharacter && curr . isCharacter ) { alternatives [ i - 1 ] = merge ( prev , curr ) ; alternatives . splice ( i , 1 ) ; i -- ; } } } function mergeWithReorder ( ) { for ( let i = 0 ; i < alternatives . length - 1 ; i ++ ) { let curr = alternatives [ i ] ; if ( ! curr . isCharacter ) { continue ; } /**
             * The union of all character sets a char alternative has to be disjoint with in order to be moved.
             */ let nonCharTotal = undefined ; for ( let j = i + 1 ; j < alternatives . length ; j ++ ) { const far = alternatives [ j ] ; if ( far . isCharacter ) { if ( nonCharTotal === undefined || far . char . isDisjointWith ( nonCharTotal ) ) { curr = merge ( curr , far ) ; alternatives . splice ( j , 1 ) ; j -- ; } else { break ; } } else { if ( ! far . firstChar . empty ) { if ( nonCharTotal === undefined ) { nonCharTotal = far . firstChar . char ; } else { nonCharTotal = nonCharTotal . union ( far . firstChar . char ) ; } if ( nonCharTotal . isAll ) { break ; } } else { break ; } } } alternatives [ i ] = curr ; } } if ( reorder ) { mergeWithReorder ( ) ; } else { mergeRuns ( ) ; } } /**
 * Return whether all character alternatives are disjoint with each other.
 */ function findNonDisjointAlt ( alternatives ) { let total = undefined ; for ( const a of alternatives ) { if ( a . isCharacter ) { if ( total === undefined ) { total = a . char ; } else { if ( ! total . isDisjointWith ( a . char ) ) { return a ; } total = total . union ( a . char ) ; } } } return null ; } function totalIsAll ( alternatives ) { let total = undefined ; for ( const a of alternatives ) { if ( a . isCharacter ) { if ( total === undefined ) { total = a . char ; } else { total = total . union ( a . char ) ; } } } return total !== undefined && total . isAll ; } export default { meta : { type : "suggestion" , docs : { description : "Prefer character classes wherever possible instead of alternations." , url : getDocUrl ( "prefer-character-class" ) , } , fixable : "code" , } , create ( context ) { return createRuleListener ( ( { visitAST , flags , replaceElement , reportElement , reportElements } ) => { function process ( node ) { if ( ! ( "alternatives" in node ) ) { return ; } if ( node . alternatives . length < 2 ) { return ; } const alts = categorizeAlternatives ( node . alternatives , flags ) ; const characterAlternativesCount = alts . filter ( a => a . isCharacter ) . length ; if ( characterAlternativesCount < 2 ) { return ; } if ( alts . every ( a => a . isCharacter ) ) { if ( alts . length >= 3 || findNonDisjointAlt ( alts ) || totalIsAll ( alts ) || containsCharacterClass ( alts ) ) { const [ prefix , suffix ] = node . type === "Group" ? [ "" , "" ] : getParentPrefixAndSuffix ( node ) ; const replacement = prefix + elementsToCharacterClass ( combineElements ( alts ) ) + suffix ; context . report ( { message : `This can be replaced with ${ mention ( replacement ) }.` , ... replaceElement ( node , replacement , { dependsOnFlags : true , } ) , } ) ; } return ; } const nonDisjointAlt = findNonDisjointAlt ( alts ) ; if ( nonDisjointAlt || characterAlternativesCount >= 3 || totalIsAll ( alts ) || containsCharacterClass ( alts ) ) { const genericAlts = toGenericAlts ( alts , flags ) ; optimizeCharacterAlternatives ( genericAlts , flags , true ) ; const [ prefix , suffix ] = getParentPrefixAndSuffix ( node ) ; const newRaw = prefix + genericAlts . map ( a => a . raw ) . join ( "|" ) + suffix ; if ( newRaw !== node . raw ) { const firstChanged = findIndex ( genericAlts , ( a , i ) => a . raw !== node . alternatives [ i ] . raw ) ; const lastChanged = findLastIndex ( genericAlts , ( a , i ) => a . raw !== node . alternatives [ node . alternatives . length + i - genericAlts . length ] . raw ) ; const changedNodes = [ node . alternatives [ firstChanged ] , node . alternatives [ node . alternatives . length + lastChanged - genericAlts . length ] , ] ; const displayRaw = firstChanged === 0 && lastChanged === genericAlts . length - 1 ? newRaw : genericAlts . slice ( firstChanged , lastChanged + 1 ) . map ( a => a . raw ) . join ( "|" ) ; context . report ( { message : `This can be replaced with ${ mention ( displayRaw ) }.` , ... replaceElement ( node , newRaw , { dependsOnFlags : true , } ) , ... reportElements ( changedNodes ) , } ) ; return ; } } if ( nonDisjointAlt ) { let expMessage ; if ( underAStar ( node ) ) { expMessage = "\nThis ambiguity is very likely to cause exponential backtracking." ; } else { expMessage = "" ; } context . report ( { message : `The set of characters accepted by ${ mention ( nonDisjointAlt . alternative ) } is not disjoint with the set of characters accepted by previous alternatives.` + " Try to remove this ambiguity." + expMessage , ... reportElement ( nonDisjointAlt . alternative ) , } ) ; return ; } } visitAST ( { onAssertionEnter : process , onCapturingGroupEnter : process , onGroupEnter : process , onPatternEnter : process , } ) ; } ) ; } , } as CleanRegexRule ;