O wyrażeniach regularnych. Podstępna różnica pomiędzy find i matches

Wyrażenia regularne to jedno z zagadnień dzielących programistów. Są tacy, którzy je uwielbiają i ci, którzy szczerze ich nienawidzą.

Sama zaliczam się do pierwszej grupy, być może z powodu upodobań lingwistycznych (wyrażenia regularne ≈ języki regularne ≈ automaty skończone). Wyrażenia regularne pozwalają na bardzo zwięzły i precyzyjny zapis warunków wyszukiwania, które – gdyby ograniczyć się do tradycyjnych konstrukcji zawartych w danym języku programowania – mogłyby zająć wiele linii. Po stronie minusów należy zapisać trudność zrozumienia dłuższych wyrażeń regularnych, zwłaszcza, jeżeli są dziełem kogoś innego.

W tym wpisie chcę podzielić się swoją niedawną przygodą optymalizacyjną. W najbliższym czasie (czyli przed końcem roku) wrzucę jeszcze stary tekst o pułapkach, w które można wpaść pisząc wyrażenia regularne w Javie oraz nowy o tym, jak regeksy mogą przydać się nieprogramistom w ich codziennych zadaniach.

Do rzeczy.

Napisałam ostatnio kod analizujący treść stron internetowych. Mniejsza z tym, po co to robił. Stanowił część większej całości (moduł mavenowy) i podobnie jak reszta kodu korzystał m.in. z Javy 8 i biblioteki JSoup. Napisałam masę testów jednostkowych, testowałam na kilkuset stronach… Jednak prawdziwa próba ognia miała nadejść kilka dni po oddaniu przeze mnie projektu, podczas uruchomienia pełnego łańcucha przetwarzania na kilkudziesięciu (kilkuset?) tysiącach stron.

W pięciu przypadkach mój kod zawiesił się na ponad dobę.

Naprawa, kiedy już do niej zasiadłam zajęła mi niecałą godzinę. Co się okazało? W kilku miejscach w moim kodzie użyłam metody Element::getElementsByAttributeValueMatching i dałam się zwieść nazwie. Na swoją obronę mam to, iż Javadoc też wprowadza w błąd. Otóż wyobraziłam sobie, iż gdzieś w głębinach metoda wywołuje metodę Matcher::matches, dlatego szukany przeze mnie fragment otoczyłam znakami ".*" przed i po adekwatnym wzorcu.

Skoro już wszystko się zapętliło, zajrzałam do środka, a tam:

... return element.hasAttr(key) && pattern.matcher(element.attr(key)).find(); ...

Podstawowa różnica pomiędzy wspomnianą już Matcher::matches a Matcher::find jest taka, iż matches szuka pełnych dopasowań (cały łańcuch znaków musi pasować do wzorca), a find zadowoli się dopasowaniem w środku łańcucha znaków (i może takich dopasowań zwrócić wiele).

Czyli jeżeli nasz wzorzec ma postać "[abc]e", to find dopasuje go do łańcucha "cel", w przeciwieństwie do metody matches:

Pattern p = Pattern.compile("[abc]e"); String a = "cel"; System.out.println(p.matcher(a).find()); //true System.out.println(p.matcher(a).matches()); //false

Jeśli dodam na początku i na końcu wzorca uniwersalne symbole ".*" (uzyskując ".*[abc]e.*") to również metoda matches uzna, iż mamy dopasowanie:

Pattern p = Pattern.compile(".*[abc]e.*"); String a = "cel"; System.out.println(p.matcher(a).find()); //true System.out.println(p.matcher(a).matches()); //true

Jednak jednak użyjemy metody find przy odpowiednio złożonym i zagnieżdzonym wyrażeniu regularnym z opcjonalnymi elementami i przy odpowiednio długim tekście, pojawi się tyle możliwości dopasowania wyrażenia do łańcucha znaków, iż wejdziemy na obszar tzw. Catastrophic Backtracking (katastrofalne nawracanie?).

Moja poprawka sprowadziła się, oczywiście, do usunięcia czterech znaków: ".*" z początku i końca wyrażenia przekazanego jako argument metodzie Element::getElementsByAttributeValueMatching.

Jaka z tego nauczka? Rutynowo zaglądać w cudzy kod, niestety.

PS. Polecam krzyżówki regeksowe: Regex Crossword.