1 // A case of catastrophic backtracking in Swift

     2 //---------------------------------------------

     3 // example provided by Martin Mikusovic

     4 //

     5 // regex: (a*)*b

     6 // strings: aa...a

     7 //

     8 // compile with

     9 //

    10 // swiftc catastrophic.swift

    11 //

    12 // run with for example

    13 //

    14 // time ./catastrophic 20

    15 

    16 import Foundation

    17 

    18 let args = CommandLine.arguments

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

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

    21     calculateTime {

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

    23     }

    24 } else {

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

    26 }

    27 

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

    29     let start = DispatchTime.now()

    30     block()

    31     let end = DispatchTime.now()

    32     let nanoTime = end.uptimeNanoseconds - start.uptimeNanoseconds

    33     let timeInterval = Double(nanoTime) / 1_000_000_000

    34     print("\(timeInterval) s")

    35 }

    36 

    37 extension String {

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

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

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

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

    42     }

    43 }