777
Christian Urban <christian.urban@kcl.ac.uk>
parents:
diff
changeset
|
1 |
/// A case of catastrophic backtracking in Dart
|
Christian Urban <christian.urban@kcl.ac.uk>
parents:
diff
changeset
|
2 |
///---------------------------------------------
|
Christian Urban <christian.urban@kcl.ac.uk>
parents:
diff
changeset
|
3 |
/// example provided by Martin Todorov
|
Christian Urban <christian.urban@kcl.ac.uk>
parents:
diff
changeset
|
4 |
///
|
Christian Urban <christian.urban@kcl.ac.uk>
parents:
diff
changeset
|
5 |
/// regex: (a*)*b
|
Christian Urban <christian.urban@kcl.ac.uk>
parents:
diff
changeset
|
6 |
/// strings: aa...a
|
Christian Urban <christian.urban@kcl.ac.uk>
parents:
diff
changeset
|
7 |
///
|
Christian Urban <christian.urban@kcl.ac.uk>
parents:
diff
changeset
|
8 |
/// run with
|
Christian Urban <christian.urban@kcl.ac.uk>
parents:
diff
changeset
|
9 |
///
|
Christian Urban <christian.urban@kcl.ac.uk>
parents:
diff
changeset
|
10 |
/// dart catastrophic.dart n
|
Christian Urban <christian.urban@kcl.ac.uk>
parents:
diff
changeset
|
11 |
|
Christian Urban <christian.urban@kcl.ac.uk>
parents:
diff
changeset
|
12 |
|
Christian Urban <christian.urban@kcl.ac.uk>
parents:
diff
changeset
|
13 |
main(List<String> args) {
|
Christian Urban <christian.urban@kcl.ac.uk>
parents:
diff
changeset
|
14 |
final n = int.parse(args[0]);
|
Christian Urban <christian.urban@kcl.ac.uk>
parents:
diff
changeset
|
15 |
final evilRegex = RegExp("(a*)*b");
|
Christian Urban <christian.urban@kcl.ac.uk>
parents:
diff
changeset
|
16 |
|
Christian Urban <christian.urban@kcl.ac.uk>
parents:
diff
changeset
|
17 |
for(int i = 1; i <= n; i++) {
|
Christian Urban <christian.urban@kcl.ac.uk>
parents:
diff
changeset
|
18 |
final toMatch = "a" * i;
|
Christian Urban <christian.urban@kcl.ac.uk>
parents:
diff
changeset
|
19 |
final stopwatch = Stopwatch()..start();
|
Christian Urban <christian.urban@kcl.ac.uk>
parents:
diff
changeset
|
20 |
evilRegex.hasMatch(toMatch);
|
Christian Urban <christian.urban@kcl.ac.uk>
parents:
diff
changeset
|
21 |
print("$i a's matched in ${stopwatch.elapsed}");
|
Christian Urban <christian.urban@kcl.ac.uk>
parents:
diff
changeset
|
22 |
}
|
Christian Urban <christian.urban@kcl.ac.uk>
parents:
diff
changeset
|
23 |
}
|