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

public class TestNeo4jExplore {
    static long timedMatch(Pattern p, String s, long timeoutMs) {
        ExecutorService exec = Executors.newSingleThreadExecutor();
        long start = System.nanoTime();
        Future<Boolean> f = exec.submit(() -> p.matcher(s).matches());
        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: ^\s*(?<key>(`([^`])*`)+?)\s*=>\s*(?<value>.+)$
        // Inner: ([^`])* matches zero or more non-backtick chars
        // Middle: `([^`])*` matches a backtick-quoted segment (possibly empty)
        // Outer: (`([^`])*`)+? matches one or more such segments (lazy)
        //
        // For exponential backtracking we need ambiguity in how to partition
        // the input into groups. Each backtick pair `...` is unambiguous because
        // ` is not in [^`]. So the boundaries are clear.
        //
        // BUT: what about EMPTY backtick pairs ``?
        // `` = backtick + zero [^`] chars + backtick
        // ```` = two empty pairs, or... wait, each pair consumes exactly 2 backticks.
        // So 2N backticks = exactly N empty pairs. No ambiguity.
        //
        // What about content between backticks?
        // `a``b` = (`a`)(`b`) — unambiguous because ` ends a group
        //
        // The +? (lazy outer) shouldn't cause issues — it just means try fewer groups first.
        // But the engine still has to explore if the lazy match fails.
        //
        // Hmm. Actually, with +? being LAZY and the pattern requiring \s*=>\s*(?<value>.+)$ 
        // AFTER the groups, the engine tries:
        // 1. One group `...`, then check if rest matches \s*=>...
        // 2. If not, try two groups, etc.
        // This is linear, not exponential.
        //
        // The exponential case would be if ([^`])* could overlap with the outer repetition,
        // but it can't because ` is an unambiguous delimiter.
        
        Pattern vuln = Pattern.compile(
            "^\\s*(?<key>(`([^`])*`)+?)\\s*=>\\s*(?<value>.+)$");
        
        System.out.println("=== Neo4j backtick pattern exploration ===");
        
        // Even backticks (clean pairs)
        for (int n : new int[]{10, 20, 50, 100, 200}) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < n; i++) sb.append("``");
            sb.append(" => val");
            long t = timedMatch(vuln, sb.toString(), 3000);
            System.out.println("  even_backticks n=" + n + ": " + (t == -1 ? "TIMEOUT" : t + "ms"));
        }
        
        // Odd backticks (no clean pairing possible)
        for (int n : new int[]{10, 20, 50, 100, 200}) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 2*n + 1; i++) sb.append('`');
            sb.append(" => val");
            long t = timedMatch(vuln, sb.toString(), 3000);
            System.out.println("  odd_backticks n=" + n + ": " + (t == -1 ? "TIMEOUT" : t + "ms"));
        }
        
        // Backticks with content
        for (int n : new int[]{10, 20, 50, 100}) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < n; i++) sb.append("`a`");
            sb.append("X => val");
            long t = timedMatch(vuln, sb.toString(), 3000);
            System.out.println("  bt_a_pairs n=" + n + ": " + (t == -1 ? "TIMEOUT" : t + "ms"));
        }
        
        // Input with NO backtick pairing possible
        for (int n : new int[]{10, 20, 50, 100}) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < n; i++) sb.append("`X");
            sb.append(" => val");
            long t = timedMatch(vuln, sb.toString(), 3000);
            System.out.println("  bt_X_interleaved n=" + n + ": " + (t == -1 ? "TIMEOUT" : t + "ms"));
        }
        
        System.out.println("\nConclusion: Neo4j backtick patterns use ` as unambiguous delimiter.");
        System.out.println("([^`])* cannot consume ` so group boundaries are fixed.");
        System.out.println("No exponential backtracking observed.");
    }
}