Czy wyrażenie regularne może zawiesić naszą aplikację?

Rozmawiałem dzisiaj z kumplem z zespołu na temat jednego z zadań i trochę od niechcenie rzuciłem, że można by zastosować tutaj wyrażenie regularne, które dodatkowo byłoby konfigurowalne. Ta z pozoru niewinna uwaga doprowadziła do ciekawej dyskusji. Otóż Tomek stwierdził, że nie jest dobrym pomysłem aby umieszczać wyrażenia regularne w konfiguracji, która może zostać zmieniona przez użytkownika. Dlaczego? W ten sposób umożliwiamy użytkownikowi zawieszenie naszej aplikacji i to nie dlatego, że wyrażenie będzie zawierało błędy składniowe. Aby zrozumieć o co chodzi przyjrzyjmy się takiemu prostemu przykładowi, w którym testuję dwa wyrażenie regularne:

private static void Main(string[] args)
{
   var input1 = "xxxxxxxxxxxxxxxxxxxxxxxxxy";
   var input2 = "xxxxxxxxxxxxxxxxxxxxxxxxx";

   var regex1 = "x+y";
   var regex2 = "(x+)+y";

   TestRegex(regex1, input1);
   TestRegex(regex2, input1);

   TestRegex(regex1, input2);
   TestRegex(regex2, input2);

   Console.WriteLine("Press any key...");
   Console.ReadLine();
}

private static void TestRegex(string r, string input)
{
   var regex = new Regex(r);
   var sw = new Stopwatch();

   sw.Start();

   regex.Match(input);

   sw.Stop();

   Console.WriteLine("{0} ms", sw.ElapsedMilliseconds);
}

Oba użyte wyrażenie są proste. Drugie jest "dziwne" bo po co stosować tutaj konstrukcję grupującą. Oczywiście nie ma to tutaj sensu, ale zrobiłem to aby pokazać ideę problemu. Teraz przejdźmy do setna. Na moim komputerze powyższy program wypisze takie czasy:

30 ticks 0 ms
13 ticks 0 ms
31 ticks 0 ms
21621843 ticks 9246 ms

Różnica jest porażająca. Z pozoru niewinne wyrażenie regularne (x+)+y w przypadku kiedy wejściowy dane do niego nie pasują (w drugim przypadku na końcu ciągu znaków brakuje litery y) jest o duże kilka rzędów wielkości wolniejsze niż wyrażenie x+y Co gorsze im więcej x'ów w danych wejściowych tym te czasy będą gorsze:

Liczba x'ów	Czas (ms)
10	0
14	4
15	9
18	71
20	291
22	1169
24	4685
26	18741
28	74078

Mamy tutaj do czynienia z złożonością wykładniczą! Problem tkwi natomiast w użyciu w drugim wyrażeniu backtracking'u, który powoduje, że silnik wyrażeń regularnych niepotrzebnie wielokrotnie (na)wraca do znalezionych wcześniej dopasowań. Do tego potrzebne są również odpowiednio dobrane dane. Można mówić, że przykład jest tendencyjny (jak to przykład), ale skoro jest to możliwe to kiedyś się zdarzy i dlatego trzeba być świadomym takich rzeczy.

Kilka uwag końcowych:

• Pewnym obejściem problemu jest wyłączenie backtracking'u dla danej grupy w taki sposób: (?>(x+)+)y
• Można również określić maksymalny dopuszczalny czas przetwarzania wyrażenia regularnego np.: new Regex(r, RegexOptions.None, new TimeSpan(0,0,0,1))
• Jeśli to możliwe to zamiast backtracking'u należy stosować tzw. lookahead/lookbehind assertions, które nie nawracają.
• Problem opisałem na przykładzie .NET, ale może od dotyczyć każdego silnika wyrażeń regularnych, który obsługuje backtracking i który domyślnie z niego korzysta.
• Jeśli chcecie pogłębić temat to polecam ten artykuł albo ten.