import { CharSet } from "refa" ; import { visitRegExpAST , AST } from "regexpp" ; import { Alternative , Assertion , LookaroundAssertion , Backreference , CapturingGroup , Character , CharacterClass , CharacterClassElement , CharacterSet , Group , Quantifier , Element , Node , Pattern , EscapeCharacterSet , UnicodePropertyCharacterSet , BranchNode , CharacterClassRange , RegExpLiteral , EdgeAssertion , } from "regexpp/ast" ; import { allCharSet , emptyCharSet , lineTerminatorCharSet , toCharSet } from "./char-util" ; import { assertNever , Simple } from "./util" ; type Flags = Partial < Readonly < AST . Flags > > ; /**
 * Returns whether the given node is constant meaning that it can only match one string and what this string is.
 * If the node is constant, it will return the constant string.
 */ export function getConstant ( node , flags ) { switch ( node . type ) { case "Alternative" : { let word = "" ; for ( const element of node . elements ) { const elementResult = getConstant ( element , flags ) ; if ( elementResult === false ) { return false ; } else { word += elementResult . word ; } } return { word } ; } case "Assertion" : case "Flags" : { return { word : "" } ; } case "Backreference" : { if ( isEmptyBackreference ( node ) ) { return { word : "" } ; } else { return getConstant ( node . resolved , flags ) ; } } case "CapturingGroup" : case "Group" : case "Pattern" : { if ( node . alternatives . length == 0 ) { return { word : "" } ; } else if ( node . alternatives . length == 1 ) { return getConstant ( node . alternatives [ 0 ] , flags ) ; } else { let word = false ; for ( const alt of node . alternatives ) { const altResult = getConstant ( alt , flags ) ; if ( altResult === false ) { return false ; } else if ( word === false ) { word = altResult . word ; } else if ( word !== altResult . word ) { return false ; } } return word === false ? false : { word } ; } } case "Character" : { const string = String . fromCodePoint ( node . value ) ; if ( flags . ignoreCase && string . toLowerCase ( ) !== string . toUpperCase ( ) ) { return false ; } return { word : string } ; } case "CharacterClass" : { if ( node . negate ) { return false ; } let word = false ; for ( const element of node . elements ) { const elementResult = getConstant ( element , flags ) ; if ( elementResult === false ) { return false ; } else if ( word === false ) { word = elementResult . word ; } else if ( word !== elementResult . word ) { return false ; } } return word === false ? false : { word } ; } case "CharacterClassRange" : { return node . min . value == node . max . value && getConstant ( node . min , flags ) ; } case "CharacterSet" : { return false ; } case "Quantifier" : { if ( node . max === 0 ) { return { word : "" } ; } const elementResult = getConstant ( node . element , flags ) ; if ( elementResult !== false ) { if ( elementResult . word === "" ) { return elementResult ; } else if ( node . min === node . max ) { let word = "" ; for ( let i = node . min ; i > 0 ; i -- ) { word += elementResult . word ; } return { word } ; } } return false ; } case "RegExpLiteral" : { return getConstant ( node . pattern , flags ) ; } default : return false ; } } /**
 * Returns whether all paths of the given element don't move the position of the automaton.
 */ export function isZeroLength ( element ) { if ( Array . isArray ( element ) ) { return element . every ( a => isZeroLength ( a ) ) ; } switch ( element . type ) { case "Alternative" : return element . elements . every ( e => isZeroLength ( e ) ) ; case "Assertion" : return true ; case "Character" : case "CharacterClass" : case "CharacterSet" : return false ; case "Quantifier" : return element . max === 0 || isZeroLength ( element . element ) ; case "Backreference" : return isEmptyBackreference ( element ) ; case "CapturingGroup" : case "Group" : return isZeroLength ( element . alternatives ) ; default : throw assertNever ( element ) ; } } /**
 * Returns whether at least one path of the given element does not move the position of the automation.
 */ export function isPotentiallyZeroLength ( element ) { if ( Array . isArray ( element ) ) { return element . some ( a => isPotentiallyZeroLength ( a ) ) ; } switch ( element . type ) { case "Alternative" : return element . elements . every ( e => isPotentiallyZeroLength ( e ) ) ; case "Assertion" : return true ; case "Backreference" : if ( isEmptyBackreference ( element ) ) { return true ; } return isPotentiallyZeroLength ( element . resolved ) ; case "Character" : case "CharacterClass" : case "CharacterSet" : return false ; case "CapturingGroup" : case "Group" : return isPotentiallyZeroLength ( element . alternatives ) ; case "Quantifier" : return element . min === 0 || isPotentiallyZeroLength ( element . element ) ; default : throw assertNever ( element ) ; } } param { Element | Alternative | Alternative [ ] } element export function isEmpty ( element ) { if ( Array . isArray ( element ) ) { return element . every ( isEmpty ) ; } switch ( element . type ) { case "Alternative" : return element . elements . every ( isEmpty ) ; case "Assertion" : if ( element . kind === "lookahead" || element . kind === "lookbehind" ) { if ( ! element . negate && isPotentiallyEmpty ( element . alternatives ) ) { return true ; } } return false ; case "Backreference" : if ( isEmptyBackreference ( element ) ) { return true ; } return isEmpty ( element . resolved ) ; case "Character" : case "CharacterClass" : case "CharacterSet" : return false ; case "CapturingGroup" : case "Group" : return isEmpty ( element . alternatives ) ; case "Quantifier" : return element . max === 0 || isEmpty ( element . element ) ; default : throw assertNever ( element ) ; } } export interface IsPotentiallyEmptyOptions { /**
     * If `true`, then backreferences that aren't guaranteed to always be replaced with the empty string will be
     * assumed to be non-empty.
     */ backreferencesAreNonEmpty ? : boolean ; } /**
 * Returns whether at least one path of the given element does not move the position of the automation and accepts
 * regardless of prefix and suffix.
 *
 * This basically means that it can match the empty string and that it does that at any position in any string.
 * Lookarounds do not affect this as (as mentioned above) all prefixes and suffixes are accepted.
 */ export function isPotentiallyEmpty ( element , options = { } ) { if ( Array . isArray ( element ) ) { return element . some ( a => isPotentiallyEmpty ( a , options ) ) ; } switch ( element . type ) { case "Alternative" : return element . elements . every ( e => isPotentiallyEmpty ( e , options ) ) ; case "Assertion" : if ( element . kind === "lookahead" || element . kind === "lookbehind" ) { if ( ! element . negate && isPotentiallyEmpty ( element . alternatives , options ) ) { return true ; } } return false ; case "Backreference" : if ( isEmptyBackreference ( element ) ) { return true ; } if ( options . backreferencesAreNonEmpty ) { return false ; } else { return ! backreferenceAlwaysAfterGroup ( element ) || isPotentiallyEmpty ( element . resolved , options ) ; } case "Character" : case "CharacterClass" : case "CharacterSet" : return false ; case "CapturingGroup" : case "Group" : return isPotentiallyEmpty ( element . alternatives , options ) ; case "Quantifier" : return element . min === 0 || isPotentiallyEmpty ( element . element , options ) ; default : throw assertNever ( element ) ; } } /**
 * Returns whether any of the ancestors of the given node fulfills the given condition.
 *
 * The ancestors will be iterated in the order from closest to farthest.
 * The condition function will not be called on the given node.
 */ export function hasSomeAncestor ( node , conditionFn ) { let parent = node . parent ; while ( parent ) { if ( conditionFn ( parent ) ) { return true ; } parent = parent . parent ; } return false ; } export type Descendants < T > = T | ( T extends Node ? RealDescendants < T > : never ) ; type RealDescendants < T extends Node > = T extends Alternative | CapturingGroup | Group | LookaroundAssertion | Quantifier | Pattern ? Element | CharacterClassElement : never | T extends CharacterClass ? CharacterClassElement : never | T extends CharacterClassRange ? Character : never | T extends RegExpLiteral ? Flags | Pattern | Element | CharacterClassElement : never ; param node param conditionFn param descentConditionFn export function hasSomeDescendant < T extends Node > ( node , conditionFn , descentConditionFn ? ) { if ( conditionFn ( node ) ) { return true ; } if ( descentConditionFn && ! descentConditionFn ( node ) ) { return false ; } switch ( node . type ) { case "Alternative" : return node . elements . some ( e => hasSomeDescendant ( e , conditionFn , descentConditionFn ) ) ; case "Assertion" : if ( node . kind === "lookahead" || node . kind === "lookbehind" ) { return node . alternatives . some ( a => hasSomeDescendant ( a , conditionFn , descentConditionFn ) ) ; } return false ; case "CapturingGroup" : case "Group" : case "Pattern" : return node . alternatives . some ( a => hasSomeDescendant ( a , conditionFn , descentConditionFn ) ) ; case "CharacterClass" : return node . elements . some ( e => hasSomeDescendant ( e , conditionFn , descentConditionFn ) ) ; case "CharacterClassRange" : return ( hasSomeDescendant ( node . min , conditionFn , descentConditionFn ) || hasSomeDescendant ( node . max , conditionFn , descentConditionFn ) ) ; case "Quantifier" : return hasSomeDescendant ( node . element , conditionFn , descentConditionFn ) ; case "RegExpLiteral" : return ( hasSomeDescendant ( node . pattern , conditionFn , descentConditionFn ) || hasSomeDescendant ( node . flags , conditionFn , descentConditionFn ) ) ; } return false ; } param node export function hasCapturingGroup ( node ) { return hasSomeDescendant ( node , d => d . type === "CapturingGroup" ) ; } /**
 * Returns whether two nodes are semantically equivalent.
 */ export function areEqual ( x , y ) { if ( x == y ) { return true ; } if ( ! x || ! y || x . type != y . type ) { return false ; } function manyAreEqual ( a , b ) { if ( a . length !== b . length ) { return false ; } for ( let i = 0 ; i < a . length ; i ++ ) { if ( ! areEqual ( a [ i ] , b [ i ] ) ) { return false ; } } return true ; } function alternativesAreEqual ( a , b ) { return manyAreEqual ( a . alternatives , b . alternatives ) ; } switch ( x . type ) { case "Alternative" : { const other = y as Alternative ; return manyAreEqual ( x . elements , other . elements ) ; } case "Assertion" : { const other = y as Assertion ; if ( x . kind === other . kind ) { if ( x . kind === "lookahead" || x . kind === "lookbehind" ) { const otherLookaround = y as LookaroundAssertion ; return x . negate === otherLookaround . negate && alternativesAreEqual ( x , otherLookaround ) ; } else { return x . raw === other . raw ; } } return false ; } case "Backreference" : { const other = y as Backreference ; return areEqual ( x . resolved , other . resolved ) ; } case "CapturingGroup" : { const other = y as CapturingGroup ; const p1 = getPattern ( x ) ; const p2 = getPattern ( other ) ; if ( p1 && p2 ) { const n1 = getCapturingGroupNumber ( p1 , x ) ; const n2 = getCapturingGroupNumber ( p2 , other ) ; if ( n1 && n2 ) { return n1 === n2 && alternativesAreEqual ( x , other ) ; } } return false ; } case "Character" : { const other = y as Character ; return x . value === other . value ; } case "CharacterClass" : { const other = y as CharacterClass ; return x . negate === other . negate && manyAreEqual ( x . elements , other . elements ) ; } case "CharacterClassRange" : { const other = y as CharacterClassRange ; return areEqual ( x . min , other . min ) && areEqual ( x . max , other . max ) ; } case "CharacterSet" : { const other = y as CharacterSet ; if ( x . kind === "property" && other . kind === "property" ) { return x . negate === other . negate && x . key === other . key ; } else { return x . raw === other . raw ; } } case "Flags" : { const other = y as Flags ; return ( x . dotAll === other . dotAll && x . global === other . global && x . ignoreCase === other . ignoreCase && x . multiline === other . multiline && x . sticky === other . sticky && x . unicode === other . unicode ) ; } case "Group" : case "Pattern" : { const other = y as Group ; return alternativesAreEqual ( x , other ) ; } case "Quantifier" : { const other = y as Quantifier ; return ( x . min === other . min && x . max === other . max && x . greedy === other . greedy && areEqual ( x . element , other . element ) ) ; } case "RegExpLiteral" : { const other = y as RegExpLiteral ; return areEqual ( x . flags , other . flags ) && areEqual ( x . pattern , other . pattern ) ; } default : throw assertNever ( x ) ; } } export function getCapturingGroupNumber ( pattern , group ) { let found = 0 ; try { visitRegExpAST ( pattern , { onCapturingGroupEnter ( node ) { found ++ ; if ( node === group ) { throw new Error ( ) ; } } , } ) ; return null ; } catch ( error ) { return found ; } } export function getPattern ( node ) { switch ( node . type ) { case "Pattern" : return node ; case "RegExpLiteral" : return node . pattern ; case "Flags" : return node . parent ? node . parent . pattern : null ; default : return getPattern ( node . parent ) ; } } /**
 * Returns the minimal hexadecimal escape sequence of a given code point.
 *
 * This will use one of the following formats: `\xFF`, `\uFFFF`, or `\u{10FFFF}`.
 */ export function minimalHexEscape ( codePoint ) { if ( codePoint <= 0xff ) { return "\\x" + codePoint . toString ( 16 ) . padStart ( 2 , "0" ) ; } else if ( codePoint <= 0xffff ) { return "\\u" + codePoint . toString ( 16 ) . padStart ( 4 , "0" ) ; } else { return "\\u{" + codePoint . toString ( 16 ) + "}" ; } } /**
 * Returns whether the given character is written as an octal escape sequence (e.g. `\0`, `\12`).
 */ export function isOctalEscapeSequence ( node ) { return /^\\[0-7]+$/ . test ( node . raw ) ; } /**
 * Returns whether the given character is written as a control escape sequence (e.g. `\cI`).
 */ export function isControlEscapeSequence ( node ) { return /^\\c[A-Za-z]$/ . test ( node . raw ) ; } /**
 * Returns whether the given character is written as a hexadecimal escape sequence (e.g. `\xFF` `\u00FFF` `\u{FF}`).
 */ export function isHexadecimalEscapeSequence ( node ) { return /^\\(?:x[\da-fA-F]{2}|u[\da-fA-F]{4}|u\{[\da-fA-F]+\})$/ . test ( node . raw ) ; } /**
 * Returns whether the given node is a escape sequence.
 *
 * This includes octal escapes (e.g. `\31`), hexadecimal escapes (e.g. `\xFF` `\u00FFF` `\u{FF}`), control character
 * escapes (e.g. `\cI`), and other escape sequences like `\n` and `\t`.
 *
 * This does not include the character-class-exclusive `\b` escape for backspace.
 *
 * This does not include literal escapes where the escaped character is equal to the character after the backslash
 * (e.g. `\G`, `\\`, `\?`) and character sequences.
 */ export function isEscapeSequence ( node ) { return ( isOctalEscapeSequence ( node ) || isHexadecimalEscapeSequence ( node ) || isControlEscapeSequence ( node ) || /^\\[fnrtv]$/ . test ( node . raw ) ) ; } export function nodeAt ( root , index ) { if ( index < root . start || root . end >= index ) { return undefined ; } if ( root . start == index ) { return root ; } switch ( root . type ) { case "Assertion" : case "CapturingGroup" : case "Group" : case "Pattern" : if ( root . type === "Assertion" && ! ( root . kind === "lookahead" || root . kind === "lookbehind" ) ) { break ; } for ( const alt of root . alternatives ) { if ( alt . end >= index ) { break ; } const result = nodeAt ( alt , index ) ; if ( result ) { return result ; } } break ; case "Quantifier" : { const res = nodeAt ( root . element , index ) ; if ( res ) { return res ; } break ; } case "RegExpLiteral" : { let res = nodeAt ( root . flags , index ) ; if ( res ) { return res ; } res = nodeAt ( root . pattern , index ) ; if ( res ) { return res ; } break ; } default : break ; } return root ; } export interface Quant { min : number ; max : number ; greedy ? : boolean ; } /**
 * Returns the string representation of the given quantifier.
 */ export function quantToString ( quant ) { if ( quant . max < quant . min || quant . min < 0 || ! Number . isInteger ( quant . min ) || ! ( Number . isInteger ( quant . max ) || quant . max === Infinity ) ) { throw new Error ( `Invalid quantifier { min: ${ quant . min }, max: ${ quant . max } }` ) ; } let value ; if ( quant . min === 0 && quant . max === 1 ) { value = "?" ; } else if ( quant . min === 0 && quant . max === Infinity ) { value = "*" ; } else if ( quant . min === 1 && quant . max === Infinity ) { value = "+" ; } else if ( quant . min === quant . max ) { value = `{${ quant . min }}` ; } else if ( quant . max === Infinity ) { value = `{${ quant . min },}` ; } else { value = `{${ quant . min },${ quant . max }}` ; } if ( ! quant . greedy ) { return value + "?" ; } else { return value ; } } export function quantAdd ( quant , other ) { if ( typeof other === "number" ) { return { min : quant . min + other , max : quant . max + other , greedy : quant . greedy , } ; } else { if ( quant . greedy === other . greedy || quant . greedy === undefined || other . greedy === undefined ) { return { min : quant . min + other . min , max : quant . max + other . max , greedy : quant . greedy ?? other . greedy , } ; } else { throw Error ( "The `greedy` property of the given quants is not compatible." ) ; } } } /**
 * Returns the raw string of the negated character set.
 *
 * I.e. for a given `\S` is will return `"\s"`.
 *
 * This __does not__ support the dot character set.
 */ export function negateCharacterSetRaw ( charSet ) { let type = charSet . raw [ 1 ] ; if ( type . toLowerCase ( ) === type ) { type = type . toUpperCase ( ) ; } else { type = type . toLowerCase ( ) ; } return `\\${ type }${ charSet . raw . substr ( 2 ) }` ; } /**
 * Returns the string representation of the given character class elements in a character class.
 */ export function elementsToCharacterClass ( elements , negate = false ) { let result = "" ; elements . forEach ( ( e , i ) => { switch ( e . type ) { case "Character" : if ( e . raw === "-" ) { if ( i === 0 || i === elements . length - 1 ) { result += "-" ; } else { result += "\\-" ; } } else if ( e . raw === "^" ) { if ( i === 0 ) { result += "\\^" ; } else { result += "^" ; } } else if ( e . raw === "]" ) { result += "\\]" ; } else { result += e . raw ; } break ; case "CharacterClassRange" : if ( e . min . raw === "^" && i === 0 ) { result += "\\^-" + e . max . raw ; } else { result += e . min . raw + "-" + e . max . raw ; } break ; case "CharacterSet" : result += e . raw ; break ; default : throw assertNever ( e ) ; } } ) ; return "[" + ( negate ? "^" : "" ) + result + "]" ; } /**
 * Returns whether the given backreference will always be replaced with the empty string.
 */ export function isEmptyBackreference ( backreference ) { const group = backreference . resolved ; if ( hasSomeAncestor ( backreference , a => a === group ) ) { return true ; } if ( isZeroLength ( group ) ) { return true ; } function findBackreference ( node ) { const parent = node . parent ; switch ( parent . type ) { case "Alternative" : { const index = parent . elements . indexOf ( node ) ; let next ; if ( matchingDirection ( node ) === "ltr" ) { next = parent . elements . slice ( index + 1 ) ; } else { next = parent . elements . slice ( 0 , index ) ; } if ( next . some ( e => hasSomeDescendant ( e , d => d === backreference ) ) ) { return true ; } const parentParent = parent . parent ; if ( parentParent . type === "Pattern" ) { return false ; } else { return findBackreference ( parentParent ) ; } } case "Quantifier" : return findBackreference ( parent ) ; default : throw new Error ( "What happened?" ) ; } } return ! findBackreference ( group ) ; } /**
 * Returns whether the given backreference is always matched __after__ the referenced group was matched.
 *
 * If there exists any accepting path which goes through the backreference but not through the referenced group,
 * this will return `false`.
 */ export function backreferenceAlwaysAfterGroup ( backreference ) { const group = backreference . resolved ; if ( hasSomeAncestor ( backreference , a => a === group ) ) { return false ; } function findBackreference ( node ) { const parent = node . parent ; switch ( parent . type ) { case "Alternative" : { const index = parent . elements . indexOf ( node ) ; let next ; if ( matchingDirection ( node ) === "ltr" ) { next = parent . elements . slice ( index + 1 ) ; } else { next = parent . elements . slice ( 0 , index ) ; } if ( next . some ( e => hasSomeDescendant ( e , d => d === backreference ) ) ) { return true ; } const parentParent = parent . parent ; if ( parentParent . type === "Pattern" ) { return false ; } else { if ( parentParent . alternatives . length > 1 ) { return false ; } return findBackreference ( parentParent ) ; } } case "Quantifier" : if ( parent . min === 0 ) { return false ; } return findBackreference ( parent ) ; default : throw new Error ( "What happened?" ) ; } } return findBackreference ( group ) ; } /**
 * Returns the raw string of the quantifier without the quantified element.
 *
 * E.g. for `a+?`, `+?` will be returned.
 */ export function getQuantifierRaw ( quantifier ) { return quantifier . raw . substr ( quantifier . element . end - quantifier . start ) ; } export type MatchingDirection = "ltr" | "rtl" ; /**
 * Returns the direction which which the given node will be matched relative to the closest parent alternative.
 */ export function matchingDirection ( node ) { let closestLookaround ; hasSomeAncestor ( node , a => { if ( a . type === "Assertion" ) { closestLookaround = a ; return true ; } return false ; } ) ; if ( closestLookaround !== undefined && closestLookaround . kind === "lookbehind" ) { return "rtl" ; } return "ltr" ; } /**
 * `lookahead` is here equivalent to `ltr` and `lookbehind` is equivalent to `rtl`.
 */ export function invertMatchingDirection ( direction ) { return direction === "ltr" || direction === "lookahead" ? "rtl" : "ltr" ; } export function assertionKindToMatchingDirection ( kind ) { return kind === "end" || kind === "lookahead" ? "ltr" : "rtl" ; } /**
 * Returns whether the given element contains or is an assertion that looks into the given direction.
 *
 * `lookahead` is here equivalent to `ltr` and `lookbehind` is equivalent to `rtl`.
 */ export function hasAssertionWithDirection ( element , direction ) { return hasSomeDescendant ( element , d => { if ( d . type === "Assertion" ) { if ( d . kind === "word" ) { return true ; } if ( isPotentiallyEmpty ( element ) ) { return false ; } if ( direction === "lookahead" || direction === "ltr" ) { return d . kind === "lookahead" || d . kind === "end" ; } else { return d . kind === "lookbehind" || d . kind === "start" ; } } return false ; } ) ; } /**
 * Returns how many characters the given element can consume at most and has to consume at least.
 *
 * If `undefined`, then the given element can't consume any characters.
 */ export function getLengthRange ( element ) { if ( Array . isArray ( element ) ) { let min = Infinity ; let max = 0 ; for ( const e of element ) { const eRange = getLengthRange ( e ) ; if ( eRange ) { min = Math . min ( min , eRange . min ) ; max = Math . max ( max , eRange . max ) ; } } if ( min > max ) { return undefined ; } else { return { min , max } ; } } switch ( element . type ) { case "Assertion" : return { min : 0 , max : 0 } ; case "Character" : case "CharacterClass" : case "CharacterSet" : return { min : 1 , max : 1 } ; case "Quantifier" : { if ( element . max === 0 ) { return { min : 0 , max : 0 } ; } const elementRange = getLengthRange ( element . element ) ; if ( ! elementRange ) { return element . min === 0 ? { min : 0 , max : 0 } : undefined ; } if ( elementRange . max === 0 ) { return { min : 0 , max : 0 } ; } elementRange . min *= element . min ; elementRange . max *= element . max ; return elementRange ; } case "Alternative" : { let min = 0 ; let max = 0 ; for ( const e of element . elements ) { const eRange = getLengthRange ( e ) ; if ( ! eRange ) { return undefined ; } min += eRange . min ; max += eRange . max ; } return { min , max } ; } case "CapturingGroup" : case "Group" : return getLengthRange ( element . alternatives ) ; case "Backreference" : { if ( isEmptyBackreference ( element ) ) { return { min : 0 , max : 0 } ; } const resolvedRange = getLengthRange ( element . resolved ) ; if ( ! resolvedRange ) { return backreferenceAlwaysAfterGroup ( element ) ? undefined : { min : 0 , max : 0 } ; } if ( resolvedRange . min > 0 && ! backreferenceAlwaysAfterGroup ( element ) ) { resolvedRange . min = 0 ; } return resolvedRange ; } default : throw assertNever ( element ) ; } } export interface FirstLookChar { /**
     * A super set of the first character.
     *
     * We can usually only guarantee a super set because lookaround in the pattern may narrow down the actual character
     * set.
     */ char : CharSet ; /**
     * If `true`, then the first character can be the start/end of the string.
     */ edge : boolean ; /**
     * If `true`, then `char` is guaranteed to be exactly the first character and not just a super set of it.
     */ exact : boolean ; } export type FirstConsumedChar = FirstFullyConsumedChar | FirstPartiallyConsumedChar ; /**
 * This is equivalent to a regex fragment `[char]`.
 */ export interface FirstFullyConsumedChar { /**
     * A super set of the first character.
     *
     * We can usually only guarantee a super set because lookaround in the pattern may narrow down the actual character
     * set.
     */ char : CharSet ; /**
     * If `true`, then the first character also includes the empty word.
     */ empty : false ; /**
     * If `true`, then `char` is guaranteed to be exactly the first character and not just a super set of it.
     */ exact : boolean ; } /**
 * This is equivalent to a regex fragment `[char]|(?=[look.char])` or `[char]|(?=[look.char]|$)` depending on
 * `look.edge`.
 */ export interface FirstPartiallyConsumedChar { /**
     * A super set of the first character.
     *
     * We can usually only guarantee a super set because lookaround in the pattern may narrow down the actual character
     * set.
     */ char : CharSet ; /**
     * If `true`, then the first character also includes the empty word.
     */ empty : true ; /**
     * If `true`, then `char` is guaranteed to be exactly the first character and not just a super set of it.
     */ exact : boolean ; /**
     * A set of characters that may come after the consumed character
     */ look : FirstLookChar ; } /**
 * If a character is returned, it guaranteed to be a super set of the actual character. If the given element is
 * always of zero length, then the empty character set will be returned.
 *
 * If `exact` is `true` then it is guaranteed that the returned character is guaranteed to be the actual
 * character at all times if this element is not influenced by lookarounds outside itself.
 */ export function getFirstCharConsumedBy ( element , direction , flags ) { if ( Array . isArray ( element ) ) { return firstConsumedCharUnion ( element . map ( e => getFirstCharConsumedBy ( e , direction , flags ) ) , flags ) ; } switch ( element . type ) { case "Assertion" : switch ( element . kind ) { case "word" : return misdirectedAssertion ( ) ; case "end" : case "start" : if ( assertionKindToMatchingDirection ( element . kind ) === direction ) { if ( flags . multiline ) { return lineAssertion ( ) ; } else { return edgeAssertion ( ) ; } } else { return misdirectedAssertion ( ) ; } case "lookahead" : case "lookbehind" : if ( assertionKindToMatchingDirection ( element . kind ) === direction ) { if ( element . negate ) { if ( hasSomeDescendant ( element , d => d !== element && d . type === "Assertion" ) ) { return misdirectedAssertion ( ) ; } const firstChar = getFirstCharConsumedBy ( element . alternatives , direction , flags ) ; const range = getLengthRange ( element . alternatives ) ; if ( firstChar . empty || ! range ) { return { char : emptyCharSet ( flags ) , empty : false , exact : true } ; } if ( ! firstChar . exact || range . max !== 1 ) { return misdirectedAssertion ( ) ; } else { return emptyWord ( { char : firstChar . char . negate ( ) , edge : true , exact : true } ) ; } } else { const firstChar = getFirstCharConsumedBy ( element . alternatives , direction , flags ) ; return emptyWord ( firstConsumedToLook ( firstChar ) ) ; } } else { return misdirectedAssertion ( ) ; } default : throw assertNever ( element ) ; } case "Character" : case "CharacterSet" : case "CharacterClass" : return { char : toCharSet ( element , flags ) , empty : false , exact : true } ; case "Quantifier" : { if ( element . max === 0 ) { return emptyWord ( ) ; } const firstChar = getFirstCharConsumedBy ( element . element , direction , flags ) ; if ( element . min === 0 ) { return firstConsumedCharUnion ( [ emptyWord ( ) , firstChar ] , flags ) ; } else { return firstChar ; } } case "Alternative" : { let elements = element . elements ; if ( direction === "rtl" ) { elements = [ ... elements ] ; elements . reverse ( ) ; } return firstConsumedCharConcat ( ( function * ( ) : Iterable < FirstConsumedChar > { for ( const e of elements ) { yield getFirstCharConsumedBy ( e , direction , flags ) ; } } ) ( ) , flags ) ; } case "CapturingGroup" : case "Group" : return getFirstCharConsumedBy ( element . alternatives , direction , flags ) ; case "Backreference" : { if ( isEmptyBackreference ( element ) ) { return emptyWord ( ) ; } const resolvedChar = getFirstCharConsumedBy ( element . resolved , direction , flags ) ; resolvedChar . exact = resolvedChar . exact && resolvedChar . char . size <= 1 ; if ( backreferenceAlwaysAfterGroup ( element ) ) { return resolvedChar ; } else { return firstConsumedCharUnion ( [ resolvedChar , emptyWord ( ) ] , flags ) ; } } default : throw assertNever ( element ) ; } /**
     * The result for an assertion that (partly) assert for the wrong matching direction.
     */ function misdirectedAssertion ( ) { return emptyWord ( { char : allCharSet ( flags ) , edge : true , exact : false , } ) ; } function edgeAssertion ( ) { return emptyWord ( firstLookCharEdgeAccepting ( flags ) ) ; } function lineAssertion ( ) { return emptyWord ( { char : lineTerminatorCharSet ( flags ) , edge : true , exact : true , } ) ; } function emptyWord ( look ? ) { return firstConsumedCharEmptyWord ( flags , look ) ; } } /**
 * Returns first-look-char that is equivalent to a trivially-accepting lookaround.
 */ function firstLookCharTriviallyAccepting ( flags ) { return { char : allCharSet ( flags ) , edge : true , exact : true } ; } /**
 * Returns first-look-char that is equivalent to `/$/`.
 */ function firstLookCharEdgeAccepting ( flags ) { return { char : emptyCharSet ( flags ) , edge : true , exact : true } ; } /**
 * Returns first-consumed-char that is equivalent to consuming nothing (the empty word) followed by a trivially
 * accepting lookaround.
 */ function firstConsumedCharEmptyWord ( flags , look ? ) { return { char : emptyCharSet ( flags ) , empty : true , exact : true , look : look ?? firstLookCharTriviallyAccepting ( flags ) , } ; } class CharUnion { char : CharSet ; exact : boolean ; private constructor ( char ) { this . char = char ; this . exact = true ; } add ( char , exact ) { if ( this . exact && ! exact && ! this . char . isSupersetOf ( char ) ) { this . exact = false ; } else if ( ! this . exact && exact && char . isSupersetOf ( this . char ) ) { this . exact = true ; } this . char = this . char . union ( char ) ; } static emptyFromFlags ( flags ) { return new CharUnion ( emptyCharSet ( flags ) ) ; } static emptyFromMaximum ( maximum ) { return new CharUnion ( CharSet . empty ( maximum ) ) ; } } function firstConsumedCharUnion ( iter , flags ) { const union = CharUnion . emptyFromFlags ( flags ) ; const looks = [ ] ; for ( const itemChar of iter ) { union . add ( itemChar . char , itemChar . exact ) ; if ( itemChar . empty ) { looks . push ( itemChar . look ) ; } } if ( looks . length > 0 ) { const lookUnion = CharUnion . emptyFromFlags ( flags ) ; let edge = false ; for ( const look of looks ) { lookUnion . add ( look . char , look . exact ) ; edge = edge || look . edge ; } return { char : union . char , exact : union . exact , empty : true , look : { char : lookUnion . char , exact : lookUnion . exact , edge } , } ; } else { return { char : union . char , exact : union . exact , empty : false } ; } } function firstConsumedCharConcat ( iter , flags ) { const union = CharUnion . emptyFromFlags ( flags ) ; let look = firstLookCharTriviallyAccepting ( flags ) ; for ( const item of iter ) { union . add ( item . char . intersect ( look . char ) , look . exact && item . exact ) ; if ( item . empty ) { const charIntersection = look . char . intersect ( item . look . char ) ; look = { char : charIntersection , exact : ( look . exact && item . look . exact ) || charIntersection . isEmpty , edge : look . edge && item . look . edge , } ; } else { return { char : union . char , exact : union . exact , empty : false } ; } } return { char : union . char , exact : union . exact , empty : true , look } ; } /**
 * This wraps the first-consumed-char object in a look.
 */ function firstConsumedToLook ( first ) { if ( first . empty ) { const union = CharUnion . emptyFromMaximum ( first . char . maximum ) ; union . add ( first . char , first . exact ) ; union . add ( first . look . char , first . look . exact ) ; return { char : union . char , exact : union . exact , edge : first . look . edge , } ; } else { return { char : first . char , exact : first . exact , edge : false , } ; } } export interface FollowOperations < S > { /**
     * Split off a new path from the given one.
     *
     * The given state should not be modified. If the state is immutable, then `fork` may be implemented as the identify
     * function in regard to `state`.
     */ fork ( state , direction ) : S ; /**
     * Joins any number but of paths to create a combined path.
     */ join ( states , direction ) : S ; /**
     * This function is called when dealing to general lookarounds (it will __not__ be called for predefined assertion -
     * `^`, `$`, `\b`, `\B`).
     */ assert ? : ( state : S , direction : MatchingDirection , assertion : S , assertionDirection : MatchingDirection ) => S ; enter ? : ( element : Element , state : S , direction : MatchingDirection ) => S ; leave ? : ( element : Element , state : S , direction : MatchingDirection ) => S ; endPath ? : ( state : S , direction : MatchingDirection , reason : "pattern" | "assertion" ) => S ; /**
     * Whether the current path should go into the given element (return `true`) or whether it should be skipped
     * (return `false`). If the element is skipped, the given state will not be changed and passed as-is to the `leave`
     * function.
     *
     * You shouldn't modify state in this function. Modify state in the `enter` function instead.
     */ continueInto ? : ( element : Element , state : S , direction : MatchingDirection ) => boolean ; /**
     * Whether the current path should continue after the given element (return `true`) or whether all elements that
     * follow this element should be skipped (return `false`).
     *
     * If the current path is a fork path, then only the elements until the fork is joined will be skipped. A stopped
     * fork path will be joined with all other forks like normal.
     *
     * You shouldn't modify state in this function. Modify state in the `leave` function instead.
     */ continueAfter ? : ( element : Element , state : S , direction : MatchingDirection ) => boolean ; } param start param startMode param initialState param operations param direction export function followPaths < S > ( start , startMode , initialState , operations , direction ? ) { function opEnter ( element , state , direction ) { state = operations . enter ?. ( element , state , direction ) ?? state ; const continueInto = operations . continueInto ?. ( element , state , direction ) ?? true ; if ( continueInto ) { switch ( element . type ) { case "Assertion" : { if ( element . kind === "lookahead" || element . kind === "lookbehind" ) { const assertionDirection = assertionKindToMatchingDirection ( element . kind ) ; const assertion = operations . join ( element . alternatives . map ( a => enterAlternative ( a , operations . fork ( state , direction ) , assertionDirection ) ) , assertionDirection ) ; state = operations . endPath ?. ( state , assertionDirection , "assertion" ) ?? state ; state = operations . assert ?. ( state , direction , assertion , assertionDirection ) ?? state ; } break ; } case "Group" : case "CapturingGroup" : { state = operations . join ( element . alternatives . map ( a => enterAlternative ( a , operations . fork ( state , direction ) , direction ) ) , direction ) ; break ; } case "Quantifier" : { if ( element . max === 0 ) { } else if ( element . min === 0 ) { state = operations . join ( [ state , opEnter ( element . element , operations . fork ( state , direction ) , direction ) ] , direction ) ; } else { state = opEnter ( element . element , state , direction ) ; } break ; } } } state = operations . leave ?. ( element , state , direction ) ?? state ; return state ; } function enterAlternative ( alternative , state , direction ) { let i = direction === "ltr" ? 0 : alternative . elements . length - 1 ; const increment = direction === "ltr" ? + 1 : - 1 ; let element ; for ( ; ( element = alternative . elements [ i ] ) ; i += increment ) { state = opEnter ( element , state , direction ) ; const continueAfter = operations . continueAfter ?. ( element , state , direction ) ?? true ; if ( ! continueAfter ) { break ; } } return state ; } function opNext ( element , state , direction ) { type NextElement = false | Element | "pattern" | "assertion" | [ Quantifier , NextElement ] ; function getNextElement ( element ) { const parent = element . parent ; if ( parent . type === "CharacterClass" || parent . type === "CharacterClassRange" ) { throw new Error ( "The given element cannot be part of a character class." ) ; } const continuePath = operations . continueAfter ?. ( element , state , direction ) ?? true ; if ( ! continuePath ) { return false ; } if ( parent . type === "Quantifier" ) { if ( parent . max <= 1 ) { return getNextElement ( parent ) ; } else { return [ parent , getNextElement ( parent ) ] ; } } else { const nextIndex = parent . elements . indexOf ( element ) + ( direction === "ltr" ? + 1 : - 1 ) ; const nextElement = parent . elements [ nextIndex ] ; if ( nextElement ) { return nextElement ; } else { const parentParent = parent . parent ; if ( parentParent . type === "Pattern" ) { return "pattern" ; } else if ( parentParent . type === "Assertion" ) { return "assertion" ; } else if ( parentParent . type === "CapturingGroup" || parentParent . type === "Group" ) { return getNextElement ( parentParent ) ; } throw assertNever ( parentParent ) ; } } } while ( true ) { let after = getNextElement ( element ) ; while ( Array . isArray ( after ) ) { const [ quant , other ] = after ; state = operations . join ( [ state , opEnter ( quant , operations . fork ( state , direction ) , direction ) ] , direction ) ; after = other ; } if ( after === false ) { return state ; } else if ( after === "assertion" || after === "pattern" ) { state = operations . endPath ?. ( state , direction , after ) ?? state ; return state ; } else { state = opEnter ( after , state , direction ) ; element = after ; } } } if ( ! direction ) { direction = matchingDirection ( start ) ; } if ( startMode === "enter" ) { initialState = opEnter ( start , initialState , direction ) ; } return opNext ( start , initialState , direction ) ; } export interface FirstConsumedCharAfter { char : FirstConsumedChar ; elements : Element [ ] ; } export function getFirstConsumedCharAfter ( afterThis , direction , flags ) { type State = Readonly < FirstConsumedCharAfter > ; const result = followPaths < State > ( afterThis , "next" , { char : firstConsumedCharEmptyWord ( flags ) , elements : [ ] } , { fork ( state ) { return state ; } , join ( states ) { const elements = new Set < Element > ( ) ; states . forEach ( s => s . elements . forEach ( e => elements . add ( e ) ) ) ; return { char : firstConsumedCharUnion ( states . map ( s => s . char ) , flags ) , elements : [ ... elements ] , } ; } , enter ( element , state , direction ) { const first = getFirstCharConsumedBy ( element , direction , flags ) ; return { char : firstConsumedCharConcat ( [ state . char , first ] , flags ) , elements : [ ... state . elements , element ] , } ; } , continueInto ( ) { return false ; } , continueAfter ( _ , state ) { return state . char . empty ; } , } , direction ) ; return { char : result . char , elements : result . elements } ; } export interface FirstCharAfter { /**
     * The first character after the given element.
     */ char : FirstLookChar ; /**
     * A list of elements that all contributed to the result. All sub-elements of the listed elements also contribute.
     */ elements : Element [ ] ; } /**
 * Returns the first character after the given element.
 *
 * What "after" means depends the on the given direction which will be interpreted as the current matching
 * direction. You can use this to get the previous character of an element as well.
 */ export function getFirstCharAfter ( afterThis , direction , flags ) { const result = getFirstConsumedCharAfter ( afterThis , direction , flags ) ; return { char : firstConsumedToLook ( result . char ) , elements : [ ... result . elements ] } ; } export interface SingleConsumedChar { char : CharSet ; exact : boolean ; empty : boolean ; } param element param ignoreAssertions param flags export function getSingleConsumedChar ( element , ignoreAssertions , flags ) { if ( Array . isArray ( element ) ) { let empty = false ; const union = CharUnion . emptyFromFlags ( flags ) ; for ( const a of element ) { const single = getSingleConsumedChar ( a , ignoreAssertions , flags ) ; empty = empty || single . empty ; union . add ( single . char , single . exact ) ; } return { char : union . char , exact : union . exact , empty } ; } function multipleChars ( ) { return { char : emptyCharSet ( flags ) , exact : true , empty : false } ; } function zeroChars ( ) { return { char : emptyCharSet ( flags ) , exact : true , empty : true } ; } switch ( element . type ) { case "Alternative" : { let nonEmptyResult = undefined ; const emptyUnion = CharUnion . emptyFromFlags ( flags ) ; for ( const e of element . elements ) { const single = getSingleConsumedChar ( e , ignoreAssertions , flags ) ; if ( nonEmptyResult === undefined ) { if ( single . empty ) { emptyUnion . add ( single . char , single . exact ) ; } else { nonEmptyResult = single ; } } else { if ( single . empty ) { } else { return multipleChars ( ) ; } } } if ( nonEmptyResult ) { return nonEmptyResult ; } else { return { char : emptyUnion . char , exact : emptyUnion . exact , empty : true } ; } } case "Assertion" : { return { char : emptyCharSet ( flags ) , exact : false , empty : ignoreAssertions } ; } case "Character" : case "CharacterClass" : case "CharacterSet" : { return { char : toCharSet ( element , flags ) , exact : true , empty : false } ; } case "CapturingGroup" : case "Group" : { return getSingleConsumedChar ( element . alternatives , ignoreAssertions , flags ) ; } case "Backreference" : { if ( isEmptyBackreference ( element ) ) { return zeroChars ( ) ; } const resolvedSingle = getSingleConsumedChar ( element . resolved , ignoreAssertions , flags ) ; resolvedSingle . exact = resolvedSingle . exact && resolvedSingle . char . size <= 1 ; resolvedSingle . empty = resolvedSingle . empty || ! backreferenceAlwaysAfterGroup ( element ) ; return resolvedSingle ; } case "Quantifier" : { if ( element . max === 0 ) { return zeroChars ( ) ; } const single = getSingleConsumedChar ( element . element , ignoreAssertions , flags ) ; if ( ! single . empty ) { if ( element . min === 0 ) { single . empty = true ; } else if ( element . min >= 2 ) { return multipleChars ( ) ; } } return single ; } default : throw assertNever ( element ) ; } } /**
 * Returns how many times the regex engine may match the given node against a string.
 */ export function effectiveQuantifierMax ( node ) { if ( node == null ) { return 1 ; } else { const parent = effectiveQuantifierMax ( node . parent ) ; if ( node . type === "Quantifier" ) { if ( node . max === 0 || parent === 0 ) { return 0 ; } else { return parent * node . max ; } } else { return parent ; } } } /**
 * Returns whether the given node either is or is under an effectively star quantifier.
 *
 * All quantifiers with a max larger than a certain threshold are assumed to have a max of infinity.
 */ export function underAStar ( node ) { return effectiveQuantifierMax ( node ) > 20 ; } /**
 * Returns the content prefix and suffix of the given parent node.
 */ export function getParentPrefixAndSuffix ( parent ) { switch ( parent . type ) { case "Assertion" : return [ "(?" + ( parent . kind === "lookahead" ? "" : "<" ) + ( parent . negate ? "!" : "=" ) , ")" ] ; case "CapturingGroup" : if ( parent . name !== null ) { return [ "(?<" + parent . name + ">" , ")" ] ; } else { return [ "(" , ")" ] ; } case "Group" : return [ "(?:" , ")" ] ; case "Pattern" : return [ "" , "" ] ; default : throw assertNever ( parent ) ; } }