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śli 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, że Javadoc też wprowadza w błąd. Otóż wyobraziłam sobie, że gdzieś w głębinach metoda wywołuje metodę Matcher::matches, dlatego szukany przeze mnie fragment otoczyłam znakami ".*" przed i po właściwym wzorcu.

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

Podstawowa różnica pomiędzy wspomnianą już Matcher::matches a Matcher::find jest taka, że 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śli nasz wzorzec ma postać "[abc]e", to find dopasuje go do łańcucha "cel", w przeciwieństwie do metody matches:

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

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, że 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.

Komentarze

5 myśli nt. „O wyrażeniach regularnych. Podstępna różnica pomiędzy find i matches”

  1. Hmm. Ostatnio usunąłem z jednego z naszych perlowych skryptów do przetwarzania logów dokładnie takie same otaczające pary ‚.*’ z kilku wyrażeń regularnych, co skróciło czas wykonania skryptu o jakieś 2 rzędy wielkości.

    Wyrażenia regularne, jak wiele potężnych narzędzi, pozwalają popełniać subtelne błędy.

    Prawie na temat: https://swtch.com/~rsc/regexp/regexp1.html

  2. „Po stronie minusów należy zapisać trudność zrozumienia dłuższych wyrażeń regularnych, zwłaszcza, jeśli są dziełem kogoś innego.”
    Ja powiem szczerze to często mam problem zrozumieć swoje wyrażenia po pewnym czasie.
    Dla mnie regex to zło, niestety konieczne i przydatne. Nigdy nie potrafiłem zapamiętać całej składni. Praktycznie zawsze gdy chcę skorzystać z regexp to zaczynam od nowa 🙂

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *