java-topology/defects/spark/unit/TestSparkExplore.java

import java.util.regex.*;
import java.util.concurrent.*;

public class TestSparkExplore {
    static long timedFind(Pattern p, String s, long timeoutMs) {
        ExecutorService exec = Executors.newSingleThreadExecutor();
        long start = System.nanoTime();
        Future<Boolean> f = exec.submit(() -> p.matcher(s).find());
        try {
            f.get(timeoutMs, TimeUnit.MILLISECONDS);
            return (System.nanoTime() - start) / 1_000_000;
        } catch (TimeoutException e) {
            f.cancel(true);
            return -1;
        } catch (Exception e) {
            return -2;
        } finally {
            exec.shutdownNow();
        }
    }

    public static void main(String[] args) {
        // Pattern 1: (\[[A-Z0-9_\s,]+\] )+\S+
        // The overlap is \s inside the character class and the literal space after ]
        // Key insight: a SPACE can be consumed by [A-Z0-9_\s,]+ OR by the literal ' ' after ]
        // But ] is not in the character class. So the ] is an unambiguous boundary.
        // The only overlap is: when the last char before ] is a space, AND the literal space after ] 
        // This doesn't cause exponential backtracking because ] forces a boundary.

        // Pattern 2: (SPARK[-\s]*[0-9]{3,6})+
        // [-\s]* matches dashes and whitespace. SPARK is literal.
        // The - in [-\s] can match a literal dash. 
        // What about: SPARK--123SPARK--456 ... where -- creates ambiguity?
        // No: [-\s]* is greedy, eats all dashes/spaces, then [0-9]{3,6} needs digits.
        // No ambiguity about where [-\s]* ends (it ends at first digit).

        // Actually for pattern 2, the real issue: what if there are NO digits?
        // (SPARK[-\s]*[0-9]{3,6})+ on "SPARK---SPARK---X"
        // First attempt: SPARK + --- (from [-\s]*) + needs 3-6 digits -> fails
        // [-\s]* backs off one: SPARK + -- -> needs digits at '-' -> fails
        // ... linear backtrack to SPARK + '' -> needs digits at '-' -> fails
        // Then outer + can't start second iteration because we're at '-'
        // Move start position forward by 1. Linear overall.

        // These patterns, despite having nested quantifiers, do NOT cause exponential
        // backtracking because the literal anchors (SPARK, [, ]) eliminate ambiguity.
        // The fix still improves the patterns (removes unnecessary [-\s]* flexibility,
        // requires explicit hyphen) but the vulnerability is theoretical, not practical.

        Pattern p1 = Pattern.compile("(\\[[A-Z0-9_\\s,]+\\] )+\\S+");
        Pattern p2 = Pattern.compile("(SPARK[-\\s]*[0-9]{3,6})+", Pattern.CASE_INSENSITIVE);

        // Try many variations for pattern 1
        System.out.println("=== Pattern 1 exploration ===");

        // Spaces between bracket groups (should these cause backtracking?)
        for (int n : new int[]{20, 30, 40, 50}) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < n; i++) sb.append("[A] ");
            long t = timedFind(p1, sb.toString(), 3000);
            System.out.println("  [A]_space * " + n + ": " + (t == -1 ? "TIMEOUT" : t + "ms"));
        }

        // What about spaces INSIDE the brackets that could be the space AFTER ]?
        // This can't happen because ] is not in the character class.

        // Pattern with lots of spaces inside brackets (should be fast — no ambiguity)
        for (int n : new int[]{20, 30, 40, 50}) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < n; i++) sb.append("[A " + " ".repeat(5) + "] ");
            long t = timedFind(p1, sb.toString(), 3000);
            System.out.println("  [A_____]_space * " + n + ": " + (t == -1 ? "TIMEOUT" : t + "ms"));
        }

        System.out.println("\n=== Pattern 2 exploration ===");
        // SPARK with spaces ([-\s]* eats them)
        for (int n : new int[]{20, 30, 40, 50}) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < n; i++) sb.append("SPARK   ");
            sb.append("X");
            long t = timedFind(p2, sb.toString(), 3000);
            System.out.println("  SPARK___*" + n + "X: " + (t == -1 ? "TIMEOUT" : t + "ms"));
        }

        // SPARK with dashes
        for (int n : new int[]{20, 30, 40, 50}) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < n; i++) sb.append("SPARK---");
            sb.append("X");
            long t = timedFind(p2, sb.toString(), 3000);
            System.out.println("  SPARK---*" + n + "X: " + (t == -1 ? "TIMEOUT" : t + "ms"));
        }

        System.out.println("\nConclusion: Spark patterns do not exhibit exponential backtracking.");
        System.out.println("Literal anchors (SPARK, [, ]) prevent ambiguous partitioning.");
        System.out.println("Fix remains valuable: tighter semantics, defense-in-depth.");
    }
}