Benchmarks to measure '𝚁𝚎𝚐𝚞𝚕𝚊𝚛 𝙴𝚡𝚙𝚛𝚎𝚜𝚜𝚒𝚘𝚗 𝙳𝚎𝚗𝚒𝚊𝚕 𝚘𝚏 𝚂𝚎𝚛𝚟𝚒𝚌𝚎 (𝚁𝚎𝙳𝚘𝚂)'

ReDoS.swift

// Inspired from Medium post
// Decrypt Go: Why Is Go’s Regexp So Slow, and Why That’s Actually Smart
//
// https://pub.huizhou92.com/decrypt-go-why-is-gos-regexp-so-slow-and-why-that-s-actually-smart-32fedad4bd9c
//
// to run:
// swift package init --type executable --name ReDoS
// cp curr_gist Sources/ReDoS/ReDoS.swift
// swift run -c release -q ReDoS

import Foundation

func measureNsPerOp(_ iterations: Int, _ work: () -> Void) -> Double {
    let duration = ContinuousClock().measure(work)
    let comps = duration.components
    let totalNs =
        Double(comps.seconds) * 1_000_000_000 + Double(comps.attoseconds) / 1_000_000_000
    let nsPerOp = totalNs / Double(iterations)
    return nsPerOp
}

func benchmarkSimpleRegexp() {
    let iterations = 100_000
    let testInput = String(repeating: "aaaaaaaaaa", count: 100) + "b"
    let regex = /b/
    let nsPerOp = measureNsPerOp(iterations) {
        for _ in 0..<iterations {
            _ = testInput.firstMatch(of: regex)
        }
    }
    print(
        String(
            format: " %@ %11d %16.1f ns/op",
            "match regexp /b/ on \"aaa...ab\"",
            iterations,
            nsPerOp))
    fflush(stdout)
}

func benchmarkComplexRegexp() {
    let iterations = 100_000
    let testInput = String(repeating: "aaaaaaaaaa", count: 100) + "b"
    let regex = /(a+)+b/
    let nsPerOp = measureNsPerOp(iterations) {
        for _ in 0..<iterations {
            _ = testInput.firstMatch(of: regex)
        }
    }
    print(
        String(
            format: " %@ %6d %16.1f ns/op",
            "match regexp /(a+)+b/ on \"aaa...ab\"",
            iterations,
            nsPerOp))
    fflush(stdout)
}

func testReDoS(strLengths lenghts: [Int]) {
    let regex = /(a+)+b/
    for n in lenghts {
        let testInput = String(repeating: "a", count: n)
        let nsPerOp = measureNsPerOp(1) {
            _ = testInput.firstMatch(of: regex)
        }
        print(
            String(
                format: " %@ %6d %16.1f ns/op",
                "match regexp /(a+)+b/ on \"aaa...aa\"",
                n,
                nsPerOp))
        fflush(stdout)
    }
}

print("# Benchmark (1001-char str)      Iterations            Time per op")
fflush(stdout)
benchmarkSimpleRegexp()
benchmarkComplexRegexp()
print("------------------------------------------------------------------")
print("# Benchmark (ReDoS)                 Str len            Time per op")
fflush(stdout)
testReDoS(strLengths: [10, 15, 20])
print("\n")