Wyrażenie regularne które specjalnie jest wolne

0

Witam!

Próbuję zrobić benchmark mojej biblioteki do wyrażeń regularnych, ale są inconclusive - nie mogę dostać czystego wyniku, ponieważ operacje są wykonywane za szybko.

Szukam jakiegoś wyrażenia regularnego które specjalnie jest zaprojektowane tak żeby było wolne, im "gorsze" tym lepsze, najlepiej takie żęby miało dużo backtrackingu ale nie za dużo, dużo grup, dużo lookaheadów, tak żęby mieliło silnik do czerwoności.

Ma ktoś jakiś przykład wraz ze stringiem który może go złapać?

5

^(a+)+$

aaaaaaaaaaaaaaa=aaaaaaaaaaaaaaaaaaaa;

screenshot-20220429162811.png

Przy większej liczbie wystąpień a toole rzucają

Catastrophic backtracking has been detected and the execution of your expression has been halted. To find out more and what this is, please read the following article: Runaway Regular Expressions

src: https://sekurak.pl/zabilo-cale-cloudflare-przerywamy-spotkanie-wszystkie-rece-do-konsol/

3
TomRiddle napisał(a):

Witam!

Próbuję zrobić benchmark mojej biblioteki do wyrażeń regularnych, ale są inconclusive - nie mogę dostać czystego wyniku, ponieważ operacje są wykonywane za szybko.

Nawet nie napisałeś, w jaki sposób robisz ten benchmark. Trudno w jakikolwiek sposób pomóc.

Są do tego odpowiednie narzędzia, ale nie napisałeś co konkretnie chcesz zrobić poza lakonicznym "zrobić benchmark mojej biblioteki do wyrażeń regularnych".

Szukam jakiegoś wyrażenia regularnego które specjalnie jest zaprojektowane tak żeby było wolne, im "gorsze" tym lepsze, najlepiej takie żęby miało dużo backtrackingu ale nie za dużo, dużo grup, dużo lookaheadów, tak żęby mieliło silnik do czerwoności.

Ta twoja biblioteka samodzielnie implementuje te regexy, czy tylko "owija" gotowe rozwiązanie:

  • jeśli samodzielnie, a nie masz ważnego powodu, to: NIH - moim zdaniem należy skorzystać z gotowego rozwiązania

  • jeśli "owijasz" istniejące rozwiązanie, to taki benchmark należy robić dla możliwie najszybciej wykonujących się regexów, o ile rzeczywiście chcesz zmierzyć wydajność twojego wrappera, a nie wykorzystanej pod spodem biblioteki

Ma ktoś jakiś przykład wraz ze stringiem który może go złapać?

Tak, ktoś ma.

Jednak Twoje pytanie wygląda mi na XY

0

Widziałem, nawet przeglądałem kod, ale co z tego?

Dla mnie właśnie zaczął się dlugi weekend, którego nie chcę spędzić przeglądając kod T-Regx celem ustalenia, o co @TomRiddle chodziło, zwłaszcza że PHP nie znam xD

0

@1a2b3c4d5e: Dzięki, ale mi nie chodzi o catastrophic backtracking. Chciałbym żęby silnik mielił długo, ale jednak znalazł match. Z Twoim przykładem będzie 0 matchy.

@pms_enable_synaptics: Nie chce mi się tlumaczyć dokładnie do czego tego potrzebuje, bo nie chcę marnować dwudziestu stron żeby Ci to wyjaśnić. Mam konkretny benchmark już dwóch rozwiązań w wewnętrznej implementacji biblioteki, i mam duże powody przypuszczać, że ten benchmark będzie bardziej wiarygodny na bardzo nieoptymalnym wyrażeniu regularnym, dlatego takiego szukam. Możesz sobie to uważać za X/Y, I don't care. To jest coś co wynika z tego że muszę podjąć pewną decyzję, ta decyzja jest podparta kilkoma czynnikami, gdybym teraz powiedział co to za decyzja, to wyjechałbyś z pomysłami nad którymi się zastanawiam od miesięcy. Wydestylowałem odpowiedź na to pytanie do benchmarku libki, ale na razie jest on nie miarodajny, przez to że silnik łapie matcha za szybko, dlatego potrzebuje wyrażenia które specjalnie jest słabe. Więc albo rzuć pomysł niewydajnego wyrażenia regularnego, które znajduje match'a, albo nie zaśmiecaj tematu.

Dziękuję.

Nawet nie napisałeś, w jaki sposób robisz ten benchmark. Trudno w jakikolwiek sposób pomóc.

Bo to nie ma znaczenia, wiem co robię.

Są do tego odpowiednie narzędzia, ale nie napisałeś co konkretnie chcesz zrobić poza lakonicznym "zrobić benchmark mojej biblioteki do wyrażeń regularnych".

To też nie ma znaczenia w tym wątku.

jeśli "owijasz" istniejące rozwiązanie, to taki benchmark należy robić dla możliwie najszybciej wykonujących się regexów, o ile rzeczywiście chcesz zmierzyć wydajność twojego wrappera, a nie wykorzystanej pod spodem biblioteki

Tak, taki już zrobiłem. Teraz chcę zrobić drugi, dla najwolniejszych.

0
TomRiddle napisał(a):

(...) rzuć pomysł niewydajnego wyrażenia regularnego, które znajduje match'a (...)

@import[cunit]@invoke[cunit]

Matchuje kod źródłowy jednostki kompilacji C i potrafi trochę "pomielić" dla większych jednostek kompilacji.

Działa na SYSVRE w trybie VRE z flagą UNSAFE, wymaga zainstalowanego systemowego devkitu.

Tylko, że SYSVRE to komponent całkiem niszowego systemu operacyjnego, więc nie wiem czy się przyda.

0

Byc moze wyrazenie regularne ktore ma duzo lookaheadow, a jednoczesnie nie ma grup atomicznych byloby dobre (tzn zle :D Ale dobre w tym sensie, ze jest wolne i jest tym czego szukam).

2

@hauleth: kiedyś na discordzie wrzucił.

"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa".match(/(a*)*b/)

https://regexr.com/6kpi1

screenshot-20220502145558.png

0
several napisał(a):

@hauleth: kiedyś na discordzie wrzucił.

"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa".match(/(a*)*b/)

https://regexr.com/6kpi1

screenshot-20220502145558.png

Dzięki, ale zauważ, że ten regexp też nie złapał matcha, bo jest error.

Ja szukam takiego, który owszem trwa długo, ale jednak się wykona. Tylko po prostu będzie skrajnie nieoptymalny.

1 użytkowników online, w tym zalogowanych: 0, gości: 1