Repository: ota-meshi/eslint-plugin-regexp
Pull request #423 (2022-04-20 12:51:25)

Use LSS comparison for `sort-alternatives`
This PR implements a char set comparison function that has the properties described in #420. It works by comparing two char sets by comparing the lists of characters accepted by the char sets. At least, that's what it behaves like. It's still implemented based on ranges.

That's what I implemented, but I'm not sure whether this is actually better than what we had. As we can see when looking at the tests, `(?:sample|(?:un)?stable)` is now sorted "correctly". However, there are a few examples where the order is now worse. E.g. `(false|[ft]|true)` used to be ordered as `([ft]|false|true)` which was a lot better IMO.

---

Frankly, I'm starting to question whether sorting based on prefixes is even a good idea. It's (relatively) easy to do, but is it the best we can do?

How about this sorting method: Let `a` and `b` be the two alternatives we want to compare. Let `w` be the lexicographically smallest string that is accepted by either `a` or `b` but not both. If no such string exists, then `a == b`. If `w` is accepted by `a`, then `a < b`. If `w` is accepted by `b`, then `a > b`.

This sorting method will neatly order `(?:sample|(?:un)?stable)` and `([ft]|false|true)`. It's also more intuitive IMO.

The only problem with this sorting method is that it doesn't work. The "lexicographically smallest string" is only defined for finite sets of strings. I.e. What's the lexicographically smallest string for `a+b`? `ab` > `aab` > `aaab` > `aaaaaaaaaaaab` > ... I'm not sure how this could be fixed.

ota-meshi: Thank you for the detailed explanation.

I think it would be best if we could sort it in lexicographically as you say.

> The only problem with this sorting method is that it doesn't work. The "lexicographically smallest string" is only defined for finite sets of strings. I.e. What's the lexicographically smallest string for a+b? ab > aab > aaab > aaaaaaaaaaaab > ... I'm not sure how this could be fixed.

What do you think about limiting the maximum number of repeats? (For example, 10 repeats)
I think it works for most of the regexes that are actually used.


RunDevelopment: > What do you think about limiting the maximum number of repeats?

That's difficult to do right. E.g. how do we limit the repeats in `((((a+)+)+)+)+`?

---

I was thinking about implementing this a little more. To find the lexicographically smallest string (LSS) in either `a` or `b` but not both, we would need to compute the (symmetric) difference of `a` and `b`. This is a `O(2^n)` operation with regexes and might be a little too slow for us. 

So how about we use a hybrid method? I was thinking about this:
1. Find the LSS for both `a` and `b` respectively. Let's call those strings `a'` and `b'`.
2. If both `a'` and `b'` are defined/were computed successfully:
    1. If `a' < b'`, then return `a < b`. 
    2. If `a' > b'`, then return `a > b`.
3. Otherwise, compare using prefixes as implemented in this PR.

This has a bunch of nice properties:
- If the LSS is defined, it's used in the comparison.
- We don't have to compute any differences, so it's fast.
- The LSS is computed per alternative, so it's easy to cache.
- Two alternatives having the same LSS should be pretty rare in the wild, so we will likely not fallback to prefix-based comparisons too often.

However, there's a problem again: the comparison function isn't transitive. The problem is that based on LSS comparison, an alternative without an LSS is "equal" to all other alternatives. This can be fixed using a little trick: if the LSS of an alternative isn't defined, we compute the prefix and pick the LSS of the prefix. With this little trick, the comparison function becomes transitive.

I'll try implementing this. 
ota-meshi: > That's difficult to do right. E.g. how do we limit the repeats in ((((a+)+)+)+)+?

You are right. The maximum is not a good idea 😓.

The hybrid method sounds good to me :+1:




RunDevelopment: Alright, I implemented it. 

Computing the LSS is fairly simple for NFAs, so I convert alternatives into NFAs using refa, and then compute the LSS. Since this is fairly costly, I also implemented a "fast" path when the alternative is just a simple sequence of characters.

I tested this on Prism and the results are pretty good. They are mostly (~99%) the same as before, but it finally gets difficult cases like `(?:sample|(?:un)?stable)` right.

Patch:
diff --git a/lib/rules/sort-alternatives.ts b/lib/rules/sort-alternatives.ts
index 702e048..aa1c92b 100644
--- a/lib/rules/sort-alternatives.ts
+++ b/lib/rules/sort-alternatives.ts
@@ -1,5 +1,13 @@
 import type { RegExpVisitor } from "regexpp/visitor"
-import type { Alternative, Element, Pattern } from "regexpp/ast"
+import type {
+    Alternative,
+    Character,
+    CharacterClass,
+    CharacterSet,
+    Element,
+    Node,
+    Pattern,
+} from "regexpp/ast"
 import type { RegExpContext } from "../utils"
 import {
     CP_MINUS,
@@ -21,10 +29,12 @@ import {
     hasSomeDescendant,
     canReorder,
     getLongestPrefix,
+    toCharSet,
 } from "regexp-ast-analysis"
-import type { CharSet } from "refa"
-import { JS } from "refa"
+import type { CharSet, Word, ReadonlyWord } from "refa"
+import { NFA, JS, transform } from "refa"
 import { getPossiblyConsumedChar } from "../utils/regexp-ast"
+import { RegExpParser } from "regexpp"
 
 interface AllowedChars {
     allowed: CharSet
@@ -82,53 +92,267 @@ function containsOnlyLiterals(
     )
 }
 
+const lssCache = new WeakMap<Alternative, ReadonlyWord>()
+
 /**
- * Compare two string independent of the current locale by byte order.
+ * A cached version of {@link approximateLexicographicallySmallest}.
  */
-function compareByteOrder(a: string, b: string): number {
-    if (a === b) {
-        return 0
+function cachedApproximateLexicographicallySmallest(
+    alternative: Alternative,
+    parser: JS.Parser,
+    flags: ReadonlyFlags,
+): ReadonlyWord {
+    let cached = lssCache.get(alternative)
+    if (cached === undefined) {
+        cached = approximateLexicographicallySmallest(
+            alternative,
+            parser,
+            flags,
+        )
+        lssCache.set(alternative, cached)
     }
-    return a < b ? -1 : +1
+    return cached
+}
+
+const LONGEST_PREFIX_OPTIONS: GetLongestPrefixOptions = {
+    includeAfter: true,
+    onlyInside: true,
+    looseGroups: true,
 }
 
 /**
- * Compare two char sets by byte order.
+ * Return an approximation of the lexicographically smallest string (LSS)
+ * accepted by the given alternative.
+ *
+ * If the LSS is defined for the given alternative and shorter than 1000
+ * characters, then the LSS will be returned. Otherwise, a prefix-based
+ * approximation will be returned.
+ *
+ * Assertions will be ignored when computing the LSS.
+ *
+ * Backreferences will be disabled when computing the LSS, but the prefix-based
+ * approximation will account for them.
  */
-function compareCharSets(a: CharSet, b: CharSet): number {
-    // empty char set > everything else
-    if (a.isEmpty) {
-        return 1
-    } else if (b.isEmpty) {
-        return -1
+function approximateLexicographicallySmallest(
+    alternative: Alternative,
+    parser: JS.Parser,
+    flags: ReadonlyFlags,
+): Word {
+    const lss = getLexicographicallySmallestFromAlternative(
+        alternative,
+        parser,
+        flags,
+    )
+    if (lss !== undefined) return lss
+
+    // prefix-based approximation
+    const prefix = getLongestPrefix(
+        alternative,
+        "ltr",
+        flags,
+        LONGEST_PREFIX_OPTIONS,
+    )
+    return getLexicographicallySmallestFromCharSets(prefix)
+}
+
+/**
+ * If defined, this will return the lexicographically smallest string accepted
+ * by the given alternative (ignoring assertions).
+ */
+function getLexicographicallySmallestFromAlternative(
+    alternative: Alternative,
+    parser: JS.Parser,
+    flags: ReadonlyFlags,
+): Word | undefined {
+    const { elements } = alternative
+    if (isOnlyCharacters(elements)) {
+        // fast path to avoid converting simple alternatives into NFAs
+        const smallest: Word = []
+        for (const e of elements) {
+            const cs = toCharSet(e, flags)
+            if (cs.isEmpty) return undefined
+            smallest.push(cs.ranges[0].min)
+        }
+        return smallest
     }
 
-    // the first character is different
-    if (a.ranges[0].min !== b.ranges[0].min) {
-        return a.ranges[0].min - b.ranges[0].min
+    try {
+        const result = parser.parseElement(alternative, {
+            assertions: "unknown",
+            backreferences: "disable",
+            maxBackreferenceWords: 4,
+            maxNodes: 1000,
+        })
+
+        // remove all unknowns (assertions)
+        const expression = transform(
+            {
+                onConcatenation(concat) {
+                    concat.elements = concat.elements.filter(
+                        (e) => e.type !== "Unknown",
+                    )
+                },
+            },
+            result.expression,
+        )
+
+        const nfa = NFA.fromRegex(
+            expression,
+            { maxCharacter: result.maxCharacter },
+            { maxNodes: 1000 },
+        )
+
+        return getLexicographicallySmallestFromNfa(
+            nfa.nodes.initial,
+            nfa.nodes.finals,
+        )
+    } catch (error) {
+        return undefined
     }
+}
 
-    // Now for the difficult part: We want to compare them by byte-order but
-    // what does that mean for a set of characters?
-    // We will define it as such: Let x be the smallest character in the
-    // symmetric difference of a and b. If x is in a then a < b. Otherwise
-    // b < a. If the symmetric difference is empty, then a == b.
+/** Returns whether the given array of nodes contains only characters. */
+function isOnlyCharacters(
+    nodes: readonly Node[],
+): nodes is readonly (Character | CharacterClass | CharacterSet)[] {
+    return nodes.every(
+        (e) =>
+            e.type === "Character" ||
+            e.type === "CharacterClass" ||
+            e.type === "CharacterSet",
+    )
+}
 
-    const symDiff = a.union(b).without(a.intersect(b))
-    if (symDiff.isEmpty) {
-        // a == b
-        return 0
+/**
+ * If defined, this will return the lexicographically smallest string accepted
+ * by the given NFA.
+ */
+function getLexicographicallySmallestFromNfa(
+    initial: NFA.ReadonlyNode,
+    finals: ReadonlySet<NFA.ReadonlyNode>,
+): Word | undefined {
+    // this is a variation on Thompson's algorithm
+    const smallest: Word = []
+    let currentStates = [initial]
+    const newStatesSet = new Set<NFA.ReadonlyNode>()
+
+    const MAX_LENGTH = 1000
+    for (let i = 0; i < MAX_LENGTH; i++) {
+        if (currentStates.some((n) => finals.has(n))) {
+            // one of the current states is a final state
+            return smallest
+        }
+
+        // find the smallest character
+        let min = Infinity
+        for (const state of currentStates) {
+            // eslint-disable-next-line no-loop-func -- false positive
+            state.out.forEach((charSet) => {
+                if (!charSet.isEmpty) {
+                    min = Math.min(min, charSet.ranges[0].min)
+                }
+            })
+        }
+
+        if (min === Infinity) {
+            // the NFA doesn't accept any words
+            return undefined
+        }
+        smallest.push(min)
+
+        const newStates: NFA.ReadonlyNode[] = []
+        newStatesSet.clear()
+
+        for (const state of currentStates) {
+            // eslint-disable-next-line no-loop-func -- false positive
+            state.out.forEach((charSet, to) => {
+                if (charSet.has(min) && !newStatesSet.has(to)) {
+                    newStates.push(to)
+                    newStatesSet.add(to)
+                }
+            })
+        }
+
+        currentStates = newStates
     }
 
-    const min = symDiff.ranges[0].min
+    // the lexicographically smallest string either has more than
+    // MAX_LENGTH characters or doesn't exist.
+    return undefined
+}
 
-    if (a.has(min)) {
-        // a < b
-        return -1
+/**
+ * If defined, this will return the lexicographically smallest string accepted
+ * by the given sequence of character sets.
+ *
+ * If any of the given character sets is empty, the current smallest will be
+ * returned.
+ */
+function getLexicographicallySmallestFromCharSets(
+    word: Iterable<CharSet>,
+): Word {
+    const result: Word = []
+    for (const set of word) {
+        if (set.isEmpty) break
+        result.push(set.ranges[0].min)
     }
+    return result
+}
 
-    // b < a
-    return 1
+/**
+ * Compare two string independent of the current locale by byte order.
+ */
+function compareByteOrder(a: string, b: string): number {
+    if (a === b) {
+        return 0
+    }
+    return a < b ? -1 : +1
+}
+
+/**
+ * Compare two char sets by byte order.
+ */
+function compareCharSets(a: CharSet, b: CharSet): number {
+    // The basic idea here is the following:
+    // We want to sort the two sets based on their characters. To do that, we
+    // will consider the sort lists of characters (see `CharSet#characters()`)
+    // of the two sets respectively. We will then lexicographically compare
+    // these lists of characters.
+    // Obviously, we don't actually look at the full list of characters.
+    // CharSets are represented as ranges, and we will take advantage of that.
+    // In lexicographical sorting, we just have to find the first character
+    // that differs in the two sequences, and that's quite simple to do in the
+    // range representation. Further, if one sequence ends before that
+    // character was found, we compare the length of the two sequences. That is
+    // trivial to do in the range form as well.
+
+    const aRanges = a.ranges
+    const bRanges = b.ranges
+    for (let i = 0; i < aRanges.length && i < bRanges.length; i++) {
+        const aR = aRanges[i]
+        const bR = bRanges[i]
+
+        if (aR.min !== bR.min) return aR.min - bR.min
+        if (aR.max !== bR.max) {
+            if (aR.max < bR.max) {
+                // [aR.min .. aR.max]           [...?]
+                // [bR.min .. aR.max .. bR.max]
+
+                // If there is another range for a, then a is larger than b
+                return i + 1 < aRanges.length ? +1 : -1
+
+                // eslint-disable-next-line no-else-return -- x
+            } else {
+                // [aR.min .. bR.max .. aR.max]
+                // [bR.min .. bR.max]           [...?]
+
+                // If there is another range for b, then a is smaller than b
+                return i + 1 < bRanges.length ? -1 : +1
+            }
+        }
+    }
+
+    return aRanges.length - bRanges.length
 }
 
 /**
@@ -149,20 +373,46 @@ function compareCharSetStrings(
     return a.length - b.length
 }
 
-const LONGEST_PREFIX_OPTIONS: GetLongestPrefixOptions = {
-    includeAfter: true,
-    onlyInside: true,
-    looseGroups: true,
+/**
+ * Compare two strings of char sets by byte order.
+ */
+function compareWords(a: ReadonlyWord, b: ReadonlyWord): number {
+    const l = Math.min(a.length, b.length)
+    for (let i = 0; i < l; i++) {
+        const aI = a[i]
+        const bI = b[i]
+        if (aI !== bI) return aI - bI
+    }
+    return a.length - b.length
 }
 
 /**
  * Sorts the given alternatives.
+ *
+ * The comparison function implemented by this function has 3 parts:
+ *
+ * 1) Comparison based on the lexicographically smallest strings (LSS) accepted
+ *    by the alternatives.
+ * 2) Comparison based on the longest prefix of the alternatives.
+ * 3) Comparison based on the raw source code of the alternatives.
+ *
+ * For more information on why we use LSS-based comparison and how it works,
+ * see https://github.com/ota-meshi/eslint-plugin-regexp/pull/423.
  */
 function sortAlternatives(
     alternatives: Alternative[],
+    parser: JS.Parser,
     flags: ReadonlyFlags,
 ): void {
     alternatives.sort((a, b) => {
+        const lssDiff = compareWords(
+            cachedApproximateLexicographicallySmallest(a, parser, flags),
+            cachedApproximateLexicographicallySmallest(b, parser, flags),
+        )
+        if (lssDiff !== 0) {
+            return lssDiff
+        }
+
         const prefixDiff = compareCharSetStrings(
             getLongestPrefix(a, "ltr", flags, LONGEST_PREFIX_OPTIONS),
             getLongestPrefix(b, "ltr", flags, LONGEST_PREFIX_OPTIONS),
@@ -290,12 +540,28 @@ export default createRule("sort-alternatives", {
         function createVisitor(
             regexpContext: RegExpContext,
         ): RegExpVisitor.Handlers {
-            const { node, getRegexpLocation, fixReplaceNode, flags } =
-                regexpContext
+            const {
+                node,
+                getRegexpLocation,
+                fixReplaceNode,
+                flags,
+                flagsString,
+                patternAst,
+            } = regexpContext
 
             const allowedChars = getAllowedChars(flags)
 
             const possibleCharsCache = new Map<Alternative, CharSet>()
+            const parser = JS.Parser.fromAst({
+                pattern: patternAst,
+                flags: new RegExpParser().parseFlags(
+                    [
+                        ...new Set(
+                            (flagsString || "").replace(/[^gimsuy]/gu, ""),
+                        ),
+                    ].join(""),
+                ),
+            })
 
             /** A cached version of getPossiblyConsumedChar */
             function getPossibleChars(a: Alternative): CharSet {
@@ -313,7 +579,7 @@ export default createRule("sort-alternatives", {
 
                 if (canReorder(alternatives, flags)) {
                     // alternatives can be reordered freely
-                    sortAlternatives(alternatives, flags)
+                    sortAlternatives(alternatives, parser, flags)
                     trySortNumberAlternatives(alternatives)
                 } else {
                     const consumedChars = Chars.empty(flags).union(


Test patch:
diff --git a/tests/lib/rules/sort-alternatives.ts b/tests/lib/rules/sort-alternatives.ts
index 17a9fb5..b645884 100644
--- a/tests/lib/rules/sort-alternatives.ts
+++ b/tests/lib/rules/sort-alternatives.ts
@@ -15,6 +15,11 @@ tester.run("sort-alternatives", rule as any, {
         String.raw`/^(?:a|ab)a/u`,
         String.raw`/^(?:a|ab)c/u`,
         String.raw`/^(?:deg|g?rad|turn)\b/`,
+        String.raw`/\b(?:sample|(?:un)?stable)\b/u`,
+        String.raw`/\b(?:sharpen|(?:spatial|temporal)soften)\b/u`,
+        String.raw`/\b(x?Rec|RequestOptionsPage)\b/`,
+        String.raw`/\b([ft]|false|true)\b/`,
+        String.raw`/\b(a+b|a+c)\b/`,
     ],
     invalid: [
         {