// A case of catastrophic backtracking in Swift

//---------------------------------------------

// example provided by Martin Mikusovic

//

// regex: (a*)*b

// strings: aa...a

//

// compile with

//

// swiftc catastrophic.swift

//

// run with for example

//

// time ./catastrophic 20

import Foundation

let args = CommandLine.arguments

if args.count >= 2, let count = Int(args[1]) {

    let s = String(repeating: "a", count: count)

    calculateTime {

        let _ = s ~= "(a*)*b"

    }

} else {

    print("Please enter a valid number argument.")

}

func calculateTime(block: () -> ()) {

    let start = DispatchTime.now()

    block()

    let end = DispatchTime.now()

    let nanoTime = end.uptimeNanoseconds - start.uptimeNanoseconds

    let timeInterval = Double(nanoTime) / 1_000_000_000

    print("\(timeInterval) s")

}

extension String {

    static func ~=(lhs: String, rhs: String) -> Bool {

        guard let regex = try? NSRegularExpression(pattern: rhs) else { return false }

        let range = NSRange(location: 0, length: lhs.utf16.count)

        return regex.firstMatch(in: lhs, options: [], range: range) != nil

    }

}