// 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+ −
}+ −
}+ −