Repository: ota-meshi/eslint-plugin-regexp (ts)

Issue:
Sort word lists rule
Some regexes contain (potentially long) lists of words. E.g. almost every language over at Prism has at least one regex [like this](https://github.com/PrismJS/prism/blob/01cc18eda9e59198ab2f596944fc3338ac85a2c0/components/prism-aql.js#L18).

For many of those lists, the order of alternatives doesn't matter. I.e. most word lists in Prism are surrounded with `\b`s. In this case, we are free to reorder (=sort) the alternatives.

Sorting these lists is beneficial because it makes it easier for humans to find words. This makes it easier to maintain the regexes containing these lists.

Another additional advantage is that compression algorithms (e.g. gzip) are typically able to better compress sorted lists. I tested this with a few examples and sorted lists were around 10% smaller when compressed with gzip.

---

This rule is basically [`order-in-character-class`](https://ota-meshi.github.io/eslint-plugin-regexp/rules/order-in-character-class.html) but for groups.


Pull request description:
Add `sort-alternatives` rule
This resolves #214.

This adds the `sort-alternatives` rule. 

I constrained the rule to only sort alternatives containing certain characters and non-star quantifiers. We might want to change these constraints in the future but they seem to be a good balance right now.

The implementation will be able to handle any change in constraints. Even without any constraints, it will still work correctly (= it won't sort alternatives if it changes the pattern) but the sorting might not make much sense (e.g. it will sort lists of punctuation characters). 

One important note: numbers get special treatments. List (and sublists) containing only numbers will be sorted by value and not lexicographically. E.g. `3|5|16|1|32` will be sorted as `1|3|5|16|32` and not `1|16|3|32|5`.

Patch:
diff --git a/README.md b/README.md
index 918b32f..9752a8f 100644
--- a/README.md
+++ b/README.md
@@ -148,6 +148,7 @@ The rules with the following star :star: are included in the `plugin:regexp/reco
 | [regexp/prefer-range](https://ota-meshi.github.io/eslint-plugin-regexp/rules/prefer-range.html) | enforce using character class range | :wrench: |
 | [regexp/prefer-regexp-exec](https://ota-meshi.github.io/eslint-plugin-regexp/rules/prefer-regexp-exec.html) | enforce that `RegExp#exec` is used instead of `String#match` if no global flag is provided |  |
 | [regexp/prefer-regexp-test](https://ota-meshi.github.io/eslint-plugin-regexp/rules/prefer-regexp-test.html) | enforce that `RegExp#test` is used instead of `String#match` and `RegExp#exec` | :wrench: |
+| [regexp/sort-alternatives](https://ota-meshi.github.io/eslint-plugin-regexp/rules/sort-alternatives.html) | sort alternatives if order doesn't matter | :wrench: |
 
 ### Stylistic Issues
 
diff --git a/docs/rules/README.md b/docs/rules/README.md
index c1c0048..eea0228 100644
--- a/docs/rules/README.md
+++ b/docs/rules/README.md
@@ -62,6 +62,7 @@ The rules with the following star :star: are included in the `plugin:regexp/reco
 | [regexp/prefer-range](./prefer-range.md) | enforce using character class range | :wrench: |
 | [regexp/prefer-regexp-exec](./prefer-regexp-exec.md) | enforce that `RegExp#exec` is used instead of `String#match` if no global flag is provided |  |
 | [regexp/prefer-regexp-test](./prefer-regexp-test.md) | enforce that `RegExp#test` is used instead of `String#match` and `RegExp#exec` | :wrench: |
+| [regexp/sort-alternatives](./sort-alternatives.md) | sort alternatives if order doesn't matter | :wrench: |
 
 ### Stylistic Issues
 
diff --git a/docs/rules/sort-alternatives.md b/docs/rules/sort-alternatives.md
new file mode 100644
index 0000000..e4f4622
--- /dev/null
+++ b/docs/rules/sort-alternatives.md
@@ -0,0 +1,46 @@
+---
+pageClass: "rule-details"
+sidebarDepth: 0
+title: "regexp/sort-alternatives"
+description: "sort alternatives if order doesn't matter"
+---
+# regexp/sort-alternatives
+
+> sort alternatives if order doesn't matter
+
+- :exclamation: <badge text="This rule has not been released yet." vertical="middle" type="error"> ***This rule has not been released yet.*** </badge>
+- :wrench: The `--fix` option on the [command line](https://eslint.org/docs/user-guide/command-line-interface#fixing-problems) can automatically fix some of the problems reported by this rule.
+
+## :book: Rule Details
+
+This rule will sort alternatives to improve readability and maintainability.
+
+The primary target of this rule are lists of words and/or numbers. These lists are somewhat common and sorting them makes it easy for readers to check whether a particular word or number is included.
+
+This rule will only sort alternatives if reordering the alternatives doesn't affect the pattern.
+
+<eslint-code-block fix>
+
+```js
+/* eslint regexp/sort-alternatives: "error" */
+
+/* ✓ GOOD */
+var foo = /\b(1|2|3)\b/;
+var foo = /\b(alpha|beta|gamma)\b/;
+
+/* ✗ BAD */
+var foo = /\b(2|1|3)\b/;
+var foo = /__(?:Foo|Bar)__/;
+var foo = /\((?:TM|R|C)\)/;
+```
+
+</eslint-code-block>
+
+## :wrench: Options
+
+Nothing.
+
+## :mag: Implementation
+
+- [Rule source](https://github.com/ota-meshi/eslint-plugin-regexp/blob/master/lib/rules/sort-alternatives.ts)
+- [Test source](https://github.com/ota-meshi/eslint-plugin-regexp/blob/master/tests/lib/rules/sort-alternatives.ts)
diff --git a/lib/rules/sort-alternatives.ts b/lib/rules/sort-alternatives.ts
new file mode 100644
index 0000000..40362f0
--- /dev/null
+++ b/lib/rules/sort-alternatives.ts
@@ -0,0 +1,414 @@
+import type { RegExpVisitor } from "regexpp/visitor"
+import type {
+    Alternative,
+    CapturingGroup,
+    Element,
+    Group,
+    LookaroundAssertion,
+    Pattern,
+} from "regexpp/ast"
+import type { RegExpContext } from "../utils"
+import {
+    CP_MINUS,
+    CP_SPACE,
+    CP_APOSTROPHE,
+    createRule,
+    defineRegexpVisitor,
+} from "../utils"
+import type { ReadonlyFlags } from "regexp-ast-analysis"
+import {
+    getLengthRange,
+    Chars,
+    getFirstCharAfter,
+    getFirstConsumedChar,
+    hasSomeDescendant,
+    isEmptyBackreference,
+} from "regexp-ast-analysis"
+import type { CharRange, CharSet } from "refa"
+import { JS } from "refa"
+import type { SourceLocation, Position } from "estree"
+
+interface AllowedChars {
+    allowed: CharSet
+    required: CharSet
+}
+const cache = new Map<string, Readonly<AllowedChars>>()
+
+/** */
+function getAllowedChars(flags: ReadonlyFlags) {
+    const cacheKey = (flags.ignoreCase ? "i" : "") + (flags.unicode ? "u" : "")
+    let result = cache.get(cacheKey)
+    if (result === undefined) {
+        result = {
+            allowed: JS.createCharSet(
+                [
+                    { kind: "word", negate: false },
+                    { min: CP_SPACE, max: CP_SPACE },
+                    { min: CP_MINUS, max: CP_MINUS },
+                    { min: CP_APOSTROPHE, max: CP_APOSTROPHE },
+                ],
+                flags,
+            ),
+            required: Chars.word(flags),
+        }
+        cache.set(cacheKey, result)
+    }
+    return result
+}
+
+/**
+ * Returns the union of all characters that can possibly be consumed by the
+ * given element.
+ */
+function getConsumedChars(
+    element: Element | Pattern | Alternative,
+    context: RegExpContext,
+): CharSet {
+    const ranges: CharRange[] = []
+
+    // we misuse hasSomeDescendant to iterate all relevant elements
+    hasSomeDescendant(
+        element,
+        (d) => {
+            if (
+                d.type === "Character" ||
+                d.type === "CharacterClass" ||
+                d.type === "CharacterSet"
+            ) {
+                ranges.push(...context.toCharSet(d).ranges)
+            } else if (d.type === "Backreference" && !isEmptyBackreference(d)) {
+                ranges.push(...getConsumedChars(d.resolved, context).ranges)
+            }
+
+            // always continue to the next element
+            return false
+        },
+        // don't go into assertions
+        (d) => d.type !== "Assertion" && d.type !== "CharacterClass",
+    )
+
+    return Chars.empty(context.flags).union(ranges)
+}
+
+type Parent = Group | CapturingGroup | Pattern | LookaroundAssertion
+
+/**
+ * Assuming that the given group only consumes the given characters, this will
+ * return whether the alternatives of the group can be reordered freely without
+ * affecting the behavior of the regex.
+ *
+ * This also assumes that the alternatives of the given group do not contain
+ * capturing group in such a way that their order matters.
+ */
+function canReorder(
+    parent: Parent,
+    consumedChars: CharSet,
+    context: RegExpContext,
+): boolean {
+    const lengthRange = getLengthRange(parent.alternatives)
+    if (lengthRange && lengthRange.min === lengthRange.max) {
+        return true
+    }
+
+    if (parent.type === "Pattern" || parent.type === "Assertion") {
+        return false
+    }
+
+    return (
+        getFirstCharAfter(parent, "rtl", context.flags).char.isDisjointWith(
+            consumedChars,
+        ) &&
+        getFirstCharAfter(parent, "ltr", context.flags).char.isDisjointWith(
+            consumedChars,
+        )
+    )
+}
+
+/**
+ * Returns whether the given element contains only literal characters and
+ * groups/other elements containing literal characters.
+ */
+function containsOnlyLiterals(
+    element: Element | Pattern | Alternative,
+): boolean {
+    return !hasSomeDescendant(
+        element,
+        (d) => {
+            return (
+                d.type === "Backreference" ||
+                d.type === "CharacterSet" ||
+                (d.type === "Quantifier" && d.max === Infinity) ||
+                (d.type === "CharacterClass" && d.negate)
+            )
+        },
+        (d) => d.type !== "Assertion",
+    )
+}
+
+/**
+ * Compare two string independent of the current locale by byte order.
+ */
+function compareByteOrder(a: string, b: string): number {
+    const l = Math.min(a.length, b.length)
+    for (let i = 0; i < l; i++) {
+        const diff = a.charCodeAt(i) - b.charCodeAt(i)
+        if (diff !== 0) {
+            return diff
+        }
+    }
+
+    return a.length - b.length
+}
+
+/**
+ * Sorts the given alternatives.
+ */
+function sortAlternatives(
+    alternatives: Alternative[],
+    context: RegExpContext,
+): void {
+    const firstChars = new Map<Alternative, number>()
+    for (const a of alternatives) {
+        const chars = getFirstConsumedChar(a, "ltr", context.flags)
+        const char =
+            chars.empty || chars.char.isEmpty
+                ? Infinity
+                : chars.char.ranges[0].min
+        firstChars.set(a, char)
+    }
+
+    alternatives.sort((a, b) => {
+        const firstA = firstChars.get(a)!
+        const firstB = firstChars.get(b)!
+        if (firstA !== firstB) {
+            return firstA - firstB
+        }
+
+        if (context.flags.ignoreCase) {
+            return (
+                compareByteOrder(a.raw.toUpperCase(), b.raw.toUpperCase()) ||
+                compareByteOrder(a.raw, b.raw)
+            )
+        }
+
+        return compareByteOrder(a.raw, b.raw)
+    })
+}
+
+/**
+ * This tries to sort the given alternatives by assuming that all alternatives
+ * are a number.
+ */
+function trySortNumberAlternatives(alternatives: Alternative[]): void {
+    const numberRanges: [number, number][] = []
+    {
+        let start = 0
+        for (let i = 0; i < alternatives.length; i++) {
+            if (!/^0|[1-9]\d*$/.test(alternatives[i].raw)) {
+                if (start < i) {
+                    numberRanges.push([start, i])
+                }
+                start = i + 1
+            }
+        }
+        if (start < alternatives.length) {
+            numberRanges.push([start, alternatives.length])
+        }
+    }
+
+    for (const [start, end] of numberRanges) {
+        const slice = alternatives.slice(start, end)
+
+        slice.sort((a, b) => {
+            return Number(a.raw) - Number(b.raw)
+        })
+
+        alternatives.splice(start, end - start, ...slice)
+    }
+}
+
+/**
+ * Returns the combined source location of the two given locations.
+ */
+function unionLocations(a: SourceLocation, b: SourceLocation): SourceLocation {
+    /** x < y */
+    function less(x: Position, y: Position): boolean {
+        if (x.line < y.line) {
+            return true
+        } else if (x.line > y.line) {
+            return false
+        }
+        return x.column < y.column
+    }
+
+    return {
+        start: { ...(less(a.start, b.start) ? a.start : b.start) },
+        end: { ...(less(a.end, b.end) ? b.end : a.end) },
+    }
+}
+
+/**
+ * Returns the indexes of the first and last of original array that is changed
+ * when compared with the reordered one.
+ */
+function getReorderingBounds<T>(
+    original: readonly T[],
+    reorder: readonly T[],
+): [number, number] | undefined {
+    if (original.length !== reorder.length) {
+        return undefined
+    }
+
+    const len = original.length
+
+    let first = 0
+    for (; first < len && original[first] === reorder[first]; first++);
+
+    if (first === len) {
+        return undefined
+    }
+
+    let last = len - 1
+    for (; last >= 0 && original[last] === reorder[last]; last--);
+
+    return [first, last]
+}
+
+export default createRule("sort-alternatives", {
+    meta: {
+        docs: {
+            description: "sort alternatives if order doesn't matter",
+            category: "Best Practices",
+            recommended: false,
+        },
+        fixable: "code",
+        schema: [],
+        messages: {
+            sort:
+                "The alternatives of this group can be sorted without affecting the regex.",
+        },
+        type: "suggestion", // "problem",
+    },
+    create(context) {
+        /**
+         * Create visitor
+         */
+        function createVisitor(
+            regexpContext: RegExpContext,
+        ): RegExpVisitor.Handlers {
+            const {
+                node,
+                getRegexpLocation,
+                fixReplaceNode,
+                flags,
+            } = regexpContext
+
+            const allowedChars = getAllowedChars(flags)
+
+            /**
+             * Creates a report if the sorted alternatives are different from
+             * the unsorted ones.
+             */
+            function enforceSorted(sorted: Alternative[]): void {
+                const parent = sorted[0].parent
+                const unsorted = parent.alternatives
+
+                const bounds = getReorderingBounds(unsorted, sorted)
+                if (!bounds) {
+                    return
+                }
+
+                const loc = unionLocations(
+                    getRegexpLocation(unsorted[bounds[0]]),
+                    getRegexpLocation(unsorted[bounds[1]]),
+                )
+
+                context.report({
+                    node,
+                    loc,
+                    messageId: "sort",
+                    fix: fixReplaceNode(parent, () => {
+                        const prefix = parent.raw.slice(
+                            0,
+                            parent.alternatives[0].start - parent.start,
+                        )
+                        const suffix = parent.raw.slice(
+                            parent.alternatives[parent.alternatives.length - 1]
+                                .end - parent.start,
+                        )
+
+                        return (
+                            prefix + sorted.map((a) => a.raw).join("|") + suffix
+                        )
+                    }),
+                })
+            }
+
+            /** The handler for parents */
+            function onParent(parent: Parent): void {
+                if (parent.alternatives.length < 2) {
+                    return
+                }
+
+                if (!containsOnlyLiterals(parent)) {
+                    return
+                }
+
+                if (
+                    hasSomeDescendant(
+                        parent,
+                        (d) => d !== parent && d.type === "CapturingGroup",
+                    )
+                ) {
+                    // it's not safe to reorder alternatives with capturing groups
+                    return
+                }
+
+                const consumedChars = getConsumedChars(parent, regexpContext)
+                if (consumedChars.isEmpty) {
+                    // all alternatives are either empty or only contain
+                    // assertions
+                    return
+                }
+                if (!consumedChars.isSubsetOf(allowedChars.allowed)) {
+                    // contains some chars that are not allowed
+                    return
+                }
+                if (consumedChars.isDisjointWith(allowedChars.required)) {
+                    // doesn't contain required chars
+                    return
+                }
+
+                const alternatives = [...parent.alternatives]
+
+                if (canReorder(parent, consumedChars, regexpContext)) {
+                    // alternatives can be reordered freely
+                    sortAlternatives(alternatives, regexpContext)
+                    trySortNumberAlternatives(alternatives)
+                } else if (
+                    !consumedChars.isDisjointWith(Chars.digit(flags)) &&
+                    canReorder(
+                        parent,
+                        consumedChars.intersect(Chars.digit(flags)),
+                        regexpContext,
+                    )
+                ) {
+                    // let's try to at least sort numbers
+                    trySortNumberAlternatives(alternatives)
+                }
+
+                enforceSorted(alternatives)
+            }
+
+            return {
+                onGroupEnter: onParent,
+                onPatternEnter: onParent,
+                onCapturingGroupEnter: onParent,
+            }
+        }
+
+        return defineRegexpVisitor(context, {
+            createVisitor,
+        })
+    },
+})
diff --git a/lib/utils/rules.ts b/lib/utils/rules.ts
index 28fe09d..1dfdfb5 100644
--- a/lib/utils/rules.ts
+++ b/lib/utils/rules.ts
@@ -57,6 +57,7 @@ import preferStarQuantifier from "../rules/prefer-star-quantifier"
 import preferT from "../rules/prefer-t"
 import preferUnicodeCodepointEscapes from "../rules/prefer-unicode-codepoint-escapes"
 import preferW from "../rules/prefer-w"
+import sortAlternatives from "../rules/sort-alternatives"
 import sortFlags from "../rules/sort-flags"
 import strict from "../rules/strict"
 import unicodeEscape from "../rules/unicode-escape"
@@ -120,6 +121,7 @@ export const rules = [
     preferT,
     preferUnicodeCodepointEscapes,
     preferW,
+    sortAlternatives,
     sortFlags,
     strict,
     unicodeEscape,
diff --git a/lib/utils/unicode.ts b/lib/utils/unicode.ts
index 8de82a4..ee1773e 100644
--- a/lib/utils/unicode.ts
+++ b/lib/utils/unicode.ts
@@ -24,6 +24,7 @@ export const CP_BACK_SLASH = "\\".codePointAt(0)!
 export const CP_CLOSING_BRACKET = "]".codePointAt(0)!
 export const CP_CARET = "^".codePointAt(0)!
 export const CP_BACKTICK = "`".codePointAt(0)!
+export const CP_APOSTROPHE = "'".codePointAt(0)!
 export const CP_OPENING_BRACE = "{".codePointAt(0)!
 export const CP_PIPE = "|".codePointAt(0)!
 export const CP_CLOSING_BRACE = "}".codePointAt(0)!


Test patch:
diff --git a/tests/lib/rules/sort-alternatives.ts b/tests/lib/rules/sort-alternatives.ts
new file mode 100644
index 0000000..0eb74d9
--- /dev/null
+++ b/tests/lib/rules/sort-alternatives.ts
@@ -0,0 +1,100 @@
+import { RuleTester } from "eslint"
+import rule from "../../../lib/rules/sort-alternatives"
+
+const tester = new RuleTester({
+    parserOptions: {
+        ecmaVersion: 2020,
+        sourceType: "module",
+    },
+})
+
+tester.run("sort-alternatives", rule as any, {
+    valid: [String.raw`/c|bb|a/`, String.raw`/\b(?:a|\d+|c|b)\b/`],
+    invalid: [
+        {
+            code: String.raw`/c|b|a/`,
+            output: String.raw`/a|b|c/`,
+            errors: [
+                "The alternatives of this group can be sorted without affecting the regex.",
+            ],
+        },
+        {
+            code: String.raw`/\b(?:c|b|a)\b/`,
+            output: String.raw`/\b(?:a|b|c)\b/`,
+            errors: [
+                "The alternatives of this group can be sorted without affecting the regex.",
+            ],
+        },
+        {
+            code: String.raw`/\b(?:A|a|C|c|B|b)\b/`,
+            output: String.raw`/\b(?:A|B|C|a|b|c)\b/`,
+            errors: [
+                "The alternatives of this group can be sorted without affecting the regex.",
+            ],
+        },
+        {
+            code: String.raw`/\b(?:aa|aA|aB|ab)\b/`,
+            output: String.raw`/\b(?:aA|aB|aa|ab)\b/`,
+            errors: [
+                "The alternatives of this group can be sorted without affecting the regex.",
+            ],
+        },
+        {
+            code: String.raw`/\b(?:A|a|C|c|B|b)\b/i`,
+            output: String.raw`/\b(?:A|a|B|b|C|c)\b/i`,
+            errors: [
+                "The alternatives of this group can be sorted without affecting the regex.",
+            ],
+        },
+        {
+            code: String.raw`/\b(?:a|A|c|C|b|B)\b/i`,
+            output: String.raw`/\b(?:A|a|B|b|C|c)\b/i`,
+            errors: [
+                "The alternatives of this group can be sorted without affecting the regex.",
+            ],
+        },
+        {
+            code: String.raw`/\b(?:aa|aA|aB|ab)\b/i`,
+            output: String.raw`/\b(?:aA|aa|aB|ab)\b/i`,
+            errors: [
+                "The alternatives of this group can be sorted without affecting the regex.",
+            ],
+        },
+        {
+            code: String.raw`/\b(?:1|2|4|8|16|32|64|128|256|0)\b/`,
+            output: String.raw`/\b(?:0|1|2|4|8|16|32|64|128|256)\b/`,
+            errors: [
+                "The alternatives of this group can be sorted without affecting the regex.",
+            ],
+        },
+
+        {
+            code: String.raw`/\b(?:[Nn]umber|[Ss]tring|[Bb]oolean|Function|any|mixed|null|void)\b/`,
+            output: String.raw`/\b(?:[Bb]oolean|Function|[Nn]umber|[Ss]tring|any|mixed|null|void)\b/`,
+            errors: [
+                "The alternatives of this group can be sorted without affecting the regex.",
+            ],
+        },
+        {
+            code: String.raw`/_(?:SERVER|GET|POST|FILES|REQUEST|SESSION|ENV|COOKIE)\b/`,
+            output: String.raw`/_(?:COOKIE|ENV|FILES|GET|POST|REQUEST|SERVER|SESSION)\b/`,
+            errors: [
+                "The alternatives of this group can be sorted without affecting the regex.",
+            ],
+        },
+        {
+            code: String.raw`/\b[ui](?:128|16|32|64|8|size)\b/`,
+            output: String.raw`/\b[ui](?:8|16|32|64|128|size)\b/`,
+            errors: [
+                "The alternatives of this group can be sorted without affecting the regex.",
+            ],
+        },
+        {
+            code: String.raw`/\((?:TM|R|C)\)/`,
+            output: String.raw`/\((?:C|R|TM)\)/`,
+            errors: [
+                "The alternatives of this group can be sorted without affecting the regex.",
+            ],
+        },
+    ],
+})