Comments (23)
.(dot) and [\s\S] are different for Unicode IGNORE-CASE.
(?i:[\S]) cannot be contained within a character class because some characters are case-converted to multiple characters in Unicode. Therefore, choices for elements other than the character class are generated after the character class.
In fact, it would be correct to do the same for .(dot), but this is not done because of the high cost.
Since \S is also implemented internally with [\S], it should be the same, but it was not done. I think I simply forgot to do this. It may be best not to change it now.
The reason it works correctly for https://testsite.com/aaa..... is probably because there are no or few matches for 'a' among the choices generated.
from oniguruma.
The problem occurs with the combination of "[\S]+
" and ignore-case.
"\S+
" and "[s]+
" and "s+
" do not cause problems. However, I've only just started looking into it.
----------- oniguruma/test/test_utf8.c --------------
/* All of the following test results are "success". */
// This will be the basis for the following tests.
e("1(?i)[\\S]+?2", "12sssssssssssssssss", ONIGERR_RETRY_LIMIT_IN_MATCH_OVER); // "s" x 17
// One "s" has been removed from text.
n("1(?i)[\\S]+?2", "12ssssssssssssssss"); // No error. "s" x 16
// changed "1" to "\A"
n("\\A(?i)[\\S]+?2", "2sssssssssssssssss"); // No error. Probably due to optimization.
// "Success" also when "s" is 100,000 pieces.
// changed "[\S]" to "\S"
n("1(?i)\\S+?2", "12sssssssssssssssss"); // No error. This error requires a character class.
// "Success" also when "s" is 100,000 pieces.
// changed "+?" to "+"
e("1(?i)[\\S]+2", "12sssssssssssssssss", ONIGERR_RETRY_LIMIT_IN_MATCH_OVER);
// changed "[\\S]" to "[s2]"
n("1(?i)[s2]+?2", "12sssssssssssssssss"); // No error. "Success" also when "s" is 100,000 pieces.
// changed "[\\S]+?" to "2?s+?"
n("1(?i)2?s+?2", "12sssssssssssssssss"); // No error. "Success" also when "s" is 100,000 pieces.
from oniguruma.
that regex doesn't match cause NEXT_CAMPAIGN_EDITOR
and BUDGET_SCHEDULE_ADSET
doesn't exist in the string
@spershin you could possibly upgrade all the +
greedy quantifiers to possessive greedy (>[A-Z_]++)
and/or change the (>[A-Z_]+)
groups to atomic groups (?>>[A-Z_]+)
and/or put an atomic group around each group and following keyword (?>(>[A-Z_]+){0,200}?>SET_CAMPAIGN_OBJECTIVE_SALES)
all combined
(CREATE_CAMPAIGN_FROM_TABLE(?>(?>>[A-Z_]++){0,2000}?>SET_CAMPAIGN_OBJECTIVE_SALES)(?>(?>>[A-Z_]++){0,2000}?>CONTINUE_QUICK_CREATE_CAMPAIGN)(?>(?>>[A-Z_]++){0,2000}?>SELECT_MANUAL_SALES_CAMPAIGN)(?>(?>>[A-Z_]++){0,2000}?>CONTINUE_CAMPAIGN_PACKAGE_SELECTION)(?>(?>>[A-Z_]++){0,2000}?>TURN_ADVANTAGE_BUDGET_ON)(?>(?>>[A-Z_]++){0,2000}?>SELECT_BUDGET_CURRENCY)(?>(?>>[A-Z_]++){0,2000}?>NEXT_CAMPAIGN_EDITOR)(?>(?>>[A-Z_]++){0,2000}?>BUDGET_SCHEDULE_ADSET))
(I had to increase the max in-between keywords
to 2000
. could even change the {0,200}?
to *?
)
original regex was taking ~300ms
for me (3ms
on successful match)
new regex is 1.3ms
(0.4ms
on successful match)
tho this may only improve match time performance rather than fix the error
from oniguruma.
@kkos , @tonco-miyazawa
Seems like @simulified needs to be banned from GH, not sure how to do it.
from oniguruma.
onig_scan searches the entire string and calls a callback function for each match.
onig_search performs matching within the specified range and returns the first successful match position.
Those with _with_param have no other differences except that OnigMatchParam* can be passed as an argument. (Usually not used.)
Retry limits are applied to both a single match and the entire search.
Unlimited
onig_set_retry_limit_in_match(0);
onig_set_retry_limit_in_search(0);
from oniguruma.
Sorry if this answer is off-topic. Are you having trouble with that error?
If so, please check the regular expression you created.
Regular expressions like below will greatly increase the number of retries.
a*a*
(b*)*
(a+|b+|c+|d+|e+)*
(?:)*
About counting retries
Use the following regular expression as an example.
"aaaab" =~ /^a*$/
-
^a*
matches up to"aaaa"
. -
But since
"$"
is not found,"a*"
lets go of the last"a"
of"aaaa"
.
At this time, the count increases by 1 . -
Similarly, each time it decrease
"a"
by 1, the count increases by 1.
"aaaa"
"aaa" # count1
"aa" # count2
"a" # count3
"" # count4
If you set the limit to "2" , an error will occur and the search will end
as soon as the count reaches "3" .
The default value of this limit is "10000000" .
You can check the operation by changing this number to a smaller number.
Line 97 in e62a8e5
However, the number of retries may not be counted due to optimization.
Example, "aaaa" =~ /^a*b/
It is probably detecting that there is no "b" in the text.
from oniguruma.
I will show you how to suppress retries in regular expressions.
(?>a*)
Lines 318 to 319 in e62a8e5
a*+
Lines 159 to 169 in e62a8e5
Perl's explanation is also helpful.
https://perldoc.perl.org/perlre#%28%3F%3Epattern%29
https://perldoc.perl.org/perlre#Quantifiers
As perl explains, /a++a/
does not match 'aaaa'
.
Therefore, please note that there are situations where you should not use it.
CALLOUTS.BUILTIN
Although this is not easy to understand.
Learning how to use it will help you optimize regular expressions.
CALLOUTS.BUILTIN ( Available from version 6.8.0 ? )
https://github.com/kkos/oniguruma/blob/master/doc/CALLOUTS.BUILTIN
https://github.com/kkos/oniguruma/blob/master/doc/CALLOUTS.BUILTIN.ja (in Japanese)
This is a sample of CALLOUTS.BUILTIN.
https://github.com/kkos/oniguruma/blob/master/sample/callout.c
Perl5 also has a similar function, so it may be helpful.
perl5: Special Backtracking Control Verbs
https://perldoc.perl.org/perlre#Special-Backtracking-Control-Verbs
This is a note I wrote about "callout.c". (in Japanese)
https://github.com/tonco-miyazawa/regex_etc/tree/master/MEMO_onig/callout
from oniguruma.
Thanks for the reply.
My regex is https:\/\/[\s\S]+?\.testsite\.com\/
which tries to match urls
https://testsite.com/aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
- Not match but succeeded
https://testsite.com/testandtest1testandtest2test2test3test3test4test4test5test5test6
- throw retry-limit-in-match over
exception
I was using \s\S
to match everything which is not true in this case for matching a url, we have changed it to https:\/\/.+?\.testsite\.com\/
and it works.
I just want to understand why the second one can hit the limit but the first one doesn't when two urls have the same length? Should they retry exactly the same times?
I also want to ask the "another choice" mentioned in another thread. Does the retry happen because \s\S
has "another choice" but .
doesn't?
One more thing, if we get this exception, can we catch it and just say it doesn't match?
from oniguruma.
Thanks, I also tried the same test as you. However, no error occurred.
Additionally, I increased the length of the URL, but the error did not occur.
------- /sample/callout.c ------
// search fail
test(enc, mp, "https:\\/\\/[\\s\\S]+?\\.testsite\\.com\\/", "https://testsite.com/aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa");
// search fail
test(enc, mp, "https:\\/\\/[\\s\\S]+?\\.testsite\\.com\\/", "https://testsite.com/testandtest1testandtest2test2test3test3test4test4test5test5test6");
// search fail
test(enc, mp, "https:\\/\\/.+?\\.testsite\\.com\\/", "https://testsite.com/aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa");
// search fail
test(enc, mp, "https:\\/\\/.+?\\.testsite\\.com\\/", "https://testsite.com/testandtest1testandtest2test2test3test3test4test4test5test5test6");
May I ask what version of Oniguruma you are using? I want to test with the same version as you.
( My environment: oniguruma6.9.9[UTF-8,ONIG_SYNTAX_ONIGURUMA] , ubuntu22.04 LTS , gcc11.4.0 )
Terminal command: onig-config --version
or
Please have a look at "oniguruma/src/oniguruma.h".
Lines 37 to 39 in e62a8e5
I also want to ask the "another choice" mentioned in another thread.
Does the retry happen because \s\S has "another choice" but . doesn't?One more thing, if we get this exception, can we catch it and just say it doesn't match?
Sorry, I don't have the knowledge to answer these questions. Is there anyone who can answer?
from oniguruma.
@jliu-siteimprove
Are you writing about the case where the character encoding is utf-8 and the option is ignore-case?
It is not written that way.
from oniguruma.
@kkos (Owner)
Thank you very much, thanks to you I was able to see the retry limit error.
I will investigate the conditions under which this phenomenon occurs.
@jliu-siteimprove
I think this is probably caused by the inclusion of "s
" in "\S
".
"s
" matches multibyte characters if ignore-case is in effect.
The combination of "s
" and ignore-case has caused various problems until now.
Therefore, this problem can be prevented by simply applying (?-i)
.
Or you can also use the (?I)
option. This option prevents matching multibyte characters.
Lines 292 to 299 in e62a8e5
from oniguruma.
Thanks @kkos @tonco-miyazawa Yes, we are using IGNORE-CASE and \S
which cause the problem
from oniguruma.
This problem needs to be addressed by the user, so I'll add an explanation.
The reason for the error is the same as the code below. Please note that ignore-case is disabled.
e("1(?>2?)(?-i)(?:s|t|st|ss)+?2","12stststststststststststststststststststst", ONIGERR_RETRY_LIMIT_IN_MATCH_OVER);
For the following reasons, /(?i)[\S]/
contains behavior similar to /(?-i)(?:s|t|st|ss)/
.
// [\S] contains the following 4 characters.
x2("[\\S]" , "s", 0, 1); // [\S] match "s" .
x2("[\\S]" , "t", 0, 1); // [\S] match "t" .
x2("[\\S]" , "\u00DF", 0, 2); // [\S] match "U+00DF" .
x2("[\\S]" , "\uFB05", 0, 3); // [\S] match "U+FB05" .
// If ignore-case is in effect, these match two characters.
x2("(?i)\\x{00DF}" , "ss", 0, 2); // (?i)"U+00DF" match "ss" .
x2("(?i)\\x{FB05}" , "st", 0, 2); // (?i)"U+FB05" match "st" .
So [\S]
is just one of the things that causes problems. Example, [\D]
, [\H]
, [\p{^Space}]
, [[:^space:]]
etc..
If the text contains "st
" or "ss
", Significantly increases the number of retries when backtracking.
The text below contains a lot of "st
". These "st
" cause problems.
"https://testsite.com/testandtest1testandtest2test2test3test3test4test4test5test5test6
"
The text "_s_s_s_s_s_s_s_
" does not contain "st
", "ss
", etc., so no retry-explosion occurs.
There are other strings besides "st
" and "ss
" that can cause problems. (Example, "ff
")
https://www.unicode.org/charts/PDF/UFB00.pdf
The solution to this problem is to use (?-i:[\S])
.
However, please note that (?i:[\S])
and (?-i:[\S])
behave differently.
/^(?-i:[\S])$/
does not match things like "st
", "ss
", or "ff
" .
Another workaround is to use (?>[\S])
. This is the same principle as why /^(?>s|ss)$/
does not match "ss
".
However, this depends on the order of internal processing.
I recommend that you enable ignore-case only for parts that require it.
Also consider using atomic-group(?> )
, possessive"?+
, *+
, ++
", and ONIG_OPTION_IGNORECASE_IS_ASCII(?I)
.
In perl5.34.0, /[\S]/i
does not match multiple characters.
## st #########################
"st" =~ m/^\N{U+FB05}$/i # true
"st" =~ m/^\N{U+FB06}$/i # true
"st" =~ m/^.$/i # false
"st" =~ m/^\D$/i # false
"st" =~ m/^\S$/i # false
"st" =~ m/^[\D]$/i # false
"st" =~ m/^[\S]$/i # false
"st" =~ m/^[^\s]$/i # false
"st" =~ m/^[[:^space:]]$/i # false
"st" =~ m/^\P{Space}$/i # false
## ss #########################
"ss" =~ m/^\N{U+00DF}$/i # true
"ss" =~ m/^.$/i # false
"ss" =~ m/^\S$/i # false
"ss" =~ m/^[\S]$/i # false
## ff #########################
"ff" =~ m/^\N{U+FB00}$/i # true
"ff" =~ m/^.$/i # false
"ff" =~ m/^\S$/i # false
"ff" =~ m/^[\S]$/i # false
About "(?-i)(?:s|t|st|ss)+
" in perl5.34.0 .
When I avoided perl5 optimization, a retry-explosion occurred.
The retry-limit didn't work and I had to type Ctrl+C
to stop it.
from oniguruma.
From my testing this also seems to be the cause of microsoft/vscode#40279 and microsoft/vscode-textmate#59
[\x{0}-\x{7fffffff}]
seems to act very similar to [\S]
tho apparently it works in atom just fine
microsoft/vscode#40279 (comment)
Interstingly it works in Atom, so maybe there is some trick we miss in vscode-textmate.
from oniguruma.
vscode-textmate/issues/59
That "test.php" contains "SSSSSSSSSSSSSSSSSS
". ( 'S
'x 18 )
There are also many "ff
" and several "st
". These are enough to cause a retry-explosion.
from oniguruma.
@RedCMD
I looked into Atom. However, I could not confirm any unique behavior in Atom.
In other words, Atom behaves the same as the original oniguruma.
The issue where VSCode freezes is a VSCode-only issue.
This is an effect of oniguruma's optimization process.
If you want to check whether the optimization process is working, please test as follows.
https://github.com/kkos/oniguruma/blob/master/sample/callout.c
test(enc, mp, "::(?{XXXXXXXXXXXX})\\(" , "::abc");
test(enc, mp, "::(?{YYYYYYYYYYYY})(?=\\()" , "::abc");
/(?{XXXXXXXXXXXX})/
can be used like /(?{print("XXXXXXXXXXXX");})/
of perl5.
In this case, "XXXXXXXXXXXX"
will not be output.
This is because the optimization process found the "search fail"
first.
If possible, use regular expressions that can be optimized.
from oniguruma.
@tonco-miyazawa , @kkos
Guys, sorry to post in a closed issue, but we've just hit this problem in one of our queries.
Reproducible with:
regexp_like(
"CREATE_CAMPAIGN_FROM_TABLE>SET_CAMPAIGN_OBJECTIVE_SALES>CONTINUE_QUICK_CREATE_CAMPAIGN>ORG>SELECT_MANUAL_SALES_CAMPAIGN>CONTINUE_CAMPAIGN_PACKAGE_SELECTION>AFE>KLZ>DYU>CLOSE_EDITOR_DRAWER>SELECT_CAMPAIGN_TAB>AD_ACCOUNT_MENU_CAMPAIGN_PAGE>XKV>SELECT_CAMPAIGN_TAB>NAV_TO_BILLING_AND_PAYMENTS>SELECT_CAMPAIGN>DDN>DELETE>VIEW_INSIGHTS>TOGGLE_CAMPAIGN_STATUS>TOGGLE_CAMPAIGN_STATUS>TOGGLE_CAMPAIGN_STATUS>TOGGLE_CAMPAIGN_STATUS>TOGGLE_CAMPAIGN_STATUS>XYR>CREATE_CAMPAIGN_FROM_TABLE>SET_CAMPAIGN_OBJECTIVE_SALES>CONTINUE_QUICK_CREATE_CAMPAIGN>ORG>SELECT_MANUAL_SALES_CAMPAIGN>CONTINUE_CAMPAIGN_PACKAGE_SELECTION>AFE>KLZ>DYU>CLOSE_EDITOR_DRAWER>IDU>KIY>DISCARD>FPQ>SELECT_CAMPAIGN_TAB>AD_ACCOUNT_MENU_CAMPAIGN_PAGE>XKV>CREATE_CAMPAIGN_FROM_TABLE>SET_CAMPAIGN_OBJECTIVE_SALES>CONTINUE_QUICK_CREATE_CAMPAIGN>ORG>SELECT_MANUAL_SALES_CAMPAIGN>CONTINUE_CAMPAIGN_PACKAGE_SELECTION>EDIT_CAMPAIGN_NAME>EDIT_CAMPAIGN_NAME>EDIT_CAMPAIGN_NAME>EDIT_CAMPAIGN_NAME>AFE>KLZ>DYU>RWA>PXU>SELECT_PURCHASE_CONVERSION_GOAL>SUGGEST_AN_AUDIENCE>USE_ORIGINAL_AUDIENCE>SELECT_CURRENCY>SELECT_CURRENCY>SELECT_CURRENCY>EDIT_ADSET_TARGETING>ADSET_EDIT_TARGETING_AGE_SELECTOR>ADSET_EDIT_TARGETING_AGE_SELECTOR_FEMALE>EDIT_ADSET_TARGETING>SET_TARGETING_GENDER>ADSET_EDIT_TARGETING_AGE_SELECTOR_FEMALE>ADSET_EDIT_TARGETING_AGE_SELECTOR>EDIT_ADSET_PLACEMENT>QLQ>EDIT_ADSET_PLACEMENT>GVM>ZNF>QLQ>ADSET_PLACEMENT_MANUAL_SELECTOR>AZT>HBO>EPT>OQF>ADD_MEDIA_AD>ADD_IMAGE_AD_EDITOR>UPLOAD_AD_MEDIA>UPLOAD_AD_MEDIA>NEXT_MEDIA_PICKER_AD>NEXT_MEDIA_PICKER_AD>DONE_MEDIA_PICKER>EDIT_AD_MESSAGE>EPR>EPR>EPR>EDIT_AD_HEADLINE>LEARN_MORE_CALL_TO_ACTION>LLC>PLG>JQR>KHJ>PLG>PLG>VXT>KHJ>PUBLISH_AD>CLOSE_AD_EDITOR>SELECT_CAMPAIGN_TAB>XYR>VQU>IVB>CREATE_CAMPAIGN_FROM_TABLE>SET_CAMPAIGN_OBJECTIVE_SALES>CONTINUE_QUICK_CREATE_CAMPAIGN>ORG>SELECT_MANUAL_SALES_CAMPAIGN>CONTINUE_CAMPAIGN_PACKAGE_SELECTION>EDIT_CAMPAIGN_NAME>EDIT_CAMPAIGN_NAME>EDIT_CAMPAIGN_NAME>EDIT_CAMPAIGN_NAME>TURN_ADVANTAGE_BUDGET_ON>SELECT_BUDGET_CURRENCY>SELECT_BUDGET_CURRENCY>SELECT_BUDGET_CURRENCY>AFE>KLZ>SELECT_PIXEL_CONVERSION_GOAL>RWA>PXU>SELECT_PURCHASE_CONVERSION_GOAL>SUGGEST_AN_AUDIENCE>USE_ORIGINAL_AUDIENCE>EDIT_ADSET_TARGETING>ADSET_EDIT_TARGETING_AGE_SELECTOR>ADSET_EDIT_TARGETING_AGE_SELECTOR>QAK>EDIT_ADSET_TARGETING>SET_TARGETING_GENDER>EDIT_ADSET_PLACEMENT>QLQ>NAV_ADSET_LEVEL_TO_AD_LEVEL>HBO>HBO>BSK>USE_EXISTING_POST>NRN>NRN>CCD>NRN>NRN>NRN>NRN>NRN>NRN>NRN>SELECT_POST_AD>GIS>CONTINUE>TEY>HBG>ADD_MEDIA_AD>ADD_IMAGE_AD_EDITOR>UPLOAD_AD_MEDIA>NEXT_MEDIA_PICKER_AD>NEXT_MEDIA_PICKER_AD>DONE_MEDIA_PICKER>LEARN_MORE_CALL_TO_ACTION>LLC>PUBLISH_AD>CLOSE_AD_EDITOR>SELECT_CAMPAIGN_TAB>REFRESH_PAGE>SELECT_CAMPAIGN>CREATE_CAMPAIGN_FROM_TABLE>SET_CAMPAIGN_OBJECTIVE_SALES>CONTINUE_QUICK_CREATE_CAMPAIGN>ORG>SELECT_MANUAL_SALES_CAMPAIGN>CONTINUE_CAMPAIGN_PACKAGE_SELECTION>EDIT_CAMPAIGN_NAME>EDIT_CAMPAIGN_NAME>EDIT_CAMPAIGN_NAME>EDIT_CAMPAIGN_NAME>TURN_ADVANTAGE_BUDGET_ON>SELECT_BUDGET_CURRENCY>SELECT_BUDGET_CURRENCY>SELECT_BUDGET_CURRENCY>AFE>KLZ>PXU>SELECT_PIXEL_CONVERSION_GOAL>RWA>PXU>SELECT_PURCHASE_CONVERSION_GOAL>SUGGEST_AN_AUDIENCE>USE_ORIGINAL_AUDIENCE>EDIT_ADSET_TARGETING>EDIT_ADSET_TARGETING>ADSET_EDIT_TARGETING_AGE_SELECTOR>ADSET_EDIT_TARGETING_AGE_SELECTOR>EDIT_ADSET_PLACEMENT>QLQ>EDIT_ADSET_PLACEMENT>GVM>ZNF>JYI>JYI>ZNF>AZT>HBO>HBO>LEARN_MORE_CALL_TO_ACTION>LLC>ADD_MEDIA_AD>ADD_IMAGE_AD_EDITOR>UPLOAD_AD_MEDIA>NEXT_MEDIA_PICKER_AD>NEXT_MEDIA_PICKER_AD>DONE_MEDIA_PICKER>EDIT_AD_MESSAGE>EDIT_AD_HEADLINE>EDIT_AD_HEADLINE>EDIT_AD_HEADLINE>EDIT_AD_HEADLINE>EDIT_AD_HEADLINE>EDIT_AD_HEADLINE>CHJ>VXT>KHJ>PUBLISH_AD>FFX>TWE>SELECT_CAMPAIGN>CREATE_CAMPAIGN_FROM_TABLE>SET_CAMPAIGN_OBJECTIVE_SALES>ZWN>DUPLICATE_CAMPAIGN>IHD>CLOSE_CREATION_PACKAGE>OCS>ZMF>DISCARD>MLH>REFRESH_PAGE>TDB>CREATE_CAMPAIGN_FROM_TABLE>SET_CAMPAIGN_OBJECTIVE_SALES>CONTINUE_QUICK_CREATE_CAMPAIGN>ORG>SELECT_MANUAL_SALES_CAMPAIGN>CONTINUE_CAMPAIGN_PACKAGE_SELECTION>EDIT_CAMPAIGN_NAME>EDIT_CAMPAIGN_NAME>EDIT_CAMPAIGN_NAME>EDIT_CAMPAIGN_NAME>TURN_ADVANTAGE_BUDGET_ON>SELECT_BUDGET_CURRENCY>SELECT_BUDGET_CURRENCY>SELECT_BUDGET_CURRENCY>AFE>KLZ>DYU>RWA>PXU>SELECT_PURCHASE_CONVERSION_GOAL>SUGGEST_AN_AUDIENCE>USE_ORIGINAL_AUDIENCE>EDIT_ADSET_TARGETING>ADSET_EDIT_TARGETING_AGE_SELECTOR>ADSET_EDIT_TARGETING_AGE_SELECTOR>EDIT_ADSET_TARGETING>SET_TARGETING_GENDER>EDIT_ADSET_PLACEMENT>QLQ>GVM>ZNF>AZT>HBO>HBO>BSK>USE_EXISTING_POST>SELECT_POST_AD>DEC>TEY>HBG>OQF>ADD_MEDIA_AD>ADD_IMAGE_AD_EDITOR>UPLOAD_AD_MEDIA>NEXT_MEDIA_PICKER_AD>NEXT_MEDIA_PICKER_AD>DONE_MEDIA_PICKER>PLG>EDIT_AD_MESSAGE>EDIT_AD_HEADLINE>LEARN_MORE_CALL_TO_ACTION>LLC>FFX>AFE>AZT>PUBLISH_AD>CLOSE_AD_EDITOR>SELECT_CAMPAIGN_TAB>REFRESH_PAGE>VIEW_INSIGHTS>XYR>VQU>IVB>DUPLICATE_CAMPAIGN>EQJ>CONTINUE_CAMPAIGN_DUPLICATION>CONFIRM_DUPLICATE_CAMPAIGN>DUPLICATION_DIALOG_GENERIC>EDIT_CAMPAIGN_NAME>EDIT_CAMPAIGN_NAME>AFE>ADSET_EDIT_TARGETING_AGE_SELECTOR>ADSET_EDIT_TARGETING_AGE_SELECTOR>JYI>FRO>AZT>WPL>JTU>ADD_MEDIA_AD>ADD_IMAGE_AD_EDITOR>UPLOAD_AD_MEDIA>NEXT_MEDIA_PICKER_AD>NEXT_MEDIA_PICKER_AD>DONE_MEDIA_PICKER>EPR>PUBLISH_AD>CLOSE_AD_EDITOR>SELECT_CAMPAIGN_TAB>REFRESH_PAGE>CREATE_CAMPAIGN_FROM_TABLE>SET_CAMPAIGN_OBJECTIVE_SALES>CONTINUE_QUICK_CREATE_CAMPAIGN>ORG>SELECT_MANUAL_SALES_CAMPAIGN>CONTINUE_CAMPAIGN_PACKAGE_SELECTION>EDIT_CAMPAIGN_NAME>EDIT_CAMPAIGN_NAME>EDIT_CAMPAIGN_NAME>EDIT_CAMPAIGN_NAME>AFE>KLZ>SELECT_PIXEL_CONVERSION_GOAL>RWA>PXU>SELECT_PURCHASE_CONVERSION_GOAL>SUGGEST_AN_AUDIENCE>USE_ORIGINAL_AUDIENCE>EDIT_ADSET_TARGETING>LIB>CLOSE_ADSET_TARGETING>EDIT_ADSET_TARGETING>SET_TARGETING_GENDER>EDIT_ADSET_TARGETING>ADSET_EDIT_TARGETING_AGE_SELECTOR>ADSET_EDIT_TARGETING_AGE_SELECTOR>EDIT_ADSET_PLACEMENT>QLQ>GVM>ZNF>AZT>HBO>HBO>OQF>ADD_MEDIA_AD>ADD_IMAGE_AD_EDITOR>UPLOAD_AD_MEDIA>NEXT_MEDIA_PICKER_AD>NEXT_MEDIA_PICKER_AD>DONE_MEDIA_PICKER>EDIT_AD_MESSAGE>EDIT_AD_HEADLINE>LEARN_MORE_CALL_TO_ACTION>LLC>ELS>AZT>PUBLISH_AD>FFX>TURN_ADVANTAGE_BUDGET_ON>SELECT_BUDGET_CURRENCY>SELECT_BUDGET_CURRENCY>SELECT_BUDGET_CURRENCY>PUBLISH>AFE>CLOSE_EDITOR_DRAWER>SELECT_CAMPAIGN_TAB>REFRESH_PAGE>SELECT_CAMPAIGN>CREATE_CAMPAIGN_FROM_TABLE>SET_CAMPAIGN_OBJECTIVE_ENGAGEMENT>SET_CAMPAIGN_OBJECTIVE_SALES>CONTINUE_QUICK_CREATE_CAMPAIGN>ORG>SELECT_MANUAL_SALES_CAMPAIGN>CONTINUE_CAMPAIGN_PACKAGE_SELECTION>EDIT_CAMPAIGN_NAME>EDIT_CAMPAIGN_NAME>EDIT_CAMPAIGN_NAME>TURN_ADVANTAGE_BUDGET_ON>SELECT_BUDGET_CURRENCY>SELECT_BUDGET_CURRENCY>SELECT_BUDGET_CURRENCY>AFE>KLZ>SELECT_PIXEL_CONVERSION_GOAL>SELECT_PIXEL_CONVERSION_GOAL>SELECT_PIXEL_CONVERSION_GOAL>SELECT_PIXEL_CONVERSION_GOAL>SELECT_PIXEL_CONVERSION_GOAL>SELECT_PIXEL_CONVERSION_GOAL>YCX>EDIT_CAMPAIGN_NAME>EDIT_CAMPAIGN_NAME>AFE>PXU>SELECT_PURCHASE_CONVERSION_GOAL>SUGGEST_AN_AUDIENCE>USE_ORIGINAL_AUDIENCE>EDIT_ADSET_TARGETING>EDIT_ADSET_TARGETING>LIB>CLOSE_ADSET_TARGETING>EDIT_ADSET_TARGETING>SET_TARGETING_GENDER>EDIT_ADSET_TARGETING>YDE>YDE>EDIT_ADSET_PLACEMENT>AZT>HBO>HBO>HBO>OQF>ADD_MEDIA_AD>ADD_IMAGE_AD_EDITOR>UPLOAD_AD_MEDIA>NEXT_MEDIA_PICKER_AD>NEXT_MEDIA_PICKER_AD>DONE_MEDIA_PICKER>LEARN_MORE_CALL_TO_ACTION>PQN>TVO>LLC>PUBLISH_AD>CLOSE_AD_EDITOR>SELECT_CAMPAIGN_TAB>XYR>VQU>IVB>KJY>AFE>EDIT_ADSET_TARGETING>YDE>PUBLISH_ADSET>CLOSE_EDITOR_DRAWER>SELECT_CAMPAIGN_TAB>LEFT_NAV>LEFT_NAV>CREATE_CAMPAIGN_FROM_TABLE>SET_CAMPAIGN_OBJECTIVE_SALES>CONTINUE_QUICK_CREATE_CAMPAIGN>ORG>SELECT_MANUAL_SALES_CAMPAIGN>CONTINUE_CAMPAIGN_PACKAGE_SELECTION>AFE>KLZ>DYU>SELECT_PIXEL_CONVERSION_GOAL>DYU>QFK>DIN>DYU>CLOSE_EDITOR_DRAWER>IDU>KIY>DISCARD>FPQ>SELECT_CAMPAIGN_TAB>REFRESH_PAGE>REFRESH_PAGE>LEFT_NAV>LEFT_NAV>CREATE_CAMPAIGN_FROM_TABLE>SET_CAMPAIGN_OBJECTIVE_SALES>CONTINUE_QUICK_CREATE_CAMPAIGN>ORG>SELECT_MANUAL_SALES_CAMPAIGN>CONTINUE_CAMPAIGN_PACKAGE_SELECTION>AFE>KLZ>DYU>SELECT_PIXEL_CONVERSION_GOAL>CLOSE_EDITOR_DRAWER>IDU>KIY>DISCARD>FPQ>FPQ>SELECT_CAMPAIGN_TAB>ZMF>DISCARD>MLH>REFRESH_PAGE>VIEW_INSIGHTS>DUPLICATE_CAMPAIGN>IHD>JIE>QPD>EOW>RDO>UPLOAD_ASSET_CREATION_PACKAGE>NEXT>NEXT>UTU>PUBLISH_CREATION_PACKAGE>GZD>SELECT_CAMPAIGN_TAB>IVB>VQU>XYR>SELECT_CAMPAIGN>SELECT_CAMPAIGN>SELECT_CAMPAIGN>SELECT_CAMPAIGN>SELECT_CAMPAIGN>SELECT_CAMPAIGN>DUPLICATE>EDIT>GNR>SELECT_CAMPAIGN>SELECT_CAMPAIGN>SELECT_CAMPAIGN>SELECT_CAMPAIGN>SELECT_CAMPAIGN>SELECT_CAMPAIGN>SELECT_CAMPAIGN>SELECT_ALL_ROWS>EDIT>LCB>SELECT_CAMPAIGN_TAB>EDIT>GNR>REFRESH_PAGE>SELECT_ALL_ROWS>SELECT_ALL_ROWS>GZD>SELECT_CAMPAIGN_TAB>SELECT_CAMPAIGN>KJY>TURN_ADVANTAGE_BUDGET_ON>SELECT_BUDGET_CURRENCY>SELECT_BUDGET_CURRENCY>SELECT_BUDGET_CURRENCY>PUBLISH>TWE>SELECT_CAMPAIGN>FWC>SELECT_CURRENCY>SELECT_CURRENCY>SELECT_CURRENCY>PUBLISH>SELECT_CAMPAIGN>FWC>SELECT_CURRENCY>SELECT_CURRENCY>SELECT_CURRENCY>PUBLISH>FWC>SELECT_CURRENCY>SELECT_CURRENCY>SELECT_CURRENCY>PUBLISH>SELECT_CAMPAIGN>SEARCH_TABLE>REFRESH_PAGE>REFRESH_PAGE>REFRESH_PAGE>REFRESH_PAGE>LEFT_NAV>LEFT_NAV",
"(CREATE_CAMPAIGN_FROM_TABLE(>[A-Z_]+){0,200}?>SET_CAMPAIGN_OBJECTIVE_SALES(>[A-Z_]+){0,200}?>CONTINUE_QUICK_CREATE_CAMPAIGN(>[A-Z_]+){0,200}?>SELECT_MANUAL_SALES_CAMPAIGN(>[A-Z_]+){0,200}?>CONTINUE_CAMPAIGN_PACKAGE_SELECTION(>[A-Z_]+){0,200}?>TURN_ADVANTAGE_BUDGET_ON(>[A-Z_]+){0,200}?>SELECT_BUDGET_CURRENCY(>[A-Z_]+){0,200}?>NEXT_CAMPAIGN_EDITOR(>[A-Z_]+){0,200}?>BUDGET_SCHEDULE_ADSET)"
);
Smaller pattern works for the whole query, as well as this pattern works for many rows.
However, on some rows (like above) it fails with "retry-limit-in-match over" error.
I don't see that the reason is similar to what is discussed in this issue.
Was wondering if you can recommend either pattern rewrite or maybe some Oni config/settings change for such queries to pass.
Thank you!
from oniguruma.
@RedCMD
The "greedy quantifiers to possessive greedy" idea ((>[A-Z_]+)
-> (>[A-Z_]++))
worked really well.
No errors for that query!
So, I did more tests...
On a single (one particular) day data (2293850 rows):
(>[A-Z_]+){0,200}?
- fails with the error.
(>[A-Z_]++){0,200}?
- succeeds.
(?>>[A-Z_]++){0,200}?
- succeeds.
(?>>[A-Z_]++){0,2000}?
- fails with the error.
(?>>[A-Z_]++)*?
- fails with the error.
However, even the succeeding options fail on data from other days.
One particular input string is 15646 characters!
Funny that I haven't seen any one string that matches the pattern.
Is there a setting/option that can be modified to increase this limit?
I also lack context in the implementation and don't know what kind of limit this input+pattern are triggering (retry-limit-in-match over
).
Is it because the query is matching too many blocks?
The pattern itself has what, 16 blocks: tag + (greater + AZ_) - this is 8 times.
And we have (greater + AZ_) can repeat 200 times.
So, we can potentially have 201 * 8 = 1608 matches parts. That's not too much or is it?
I ran the query using JONI and RE2 - they both succeed on the original query.
Wondering if Oni has some kind on inefficiency triggered in this case?
Also, should I create a new issue for this?
Update:
Did more tests: removed the last two parts (they aren't found in any input) and the query succeeded with (>[A-Z_]++){0,200}?
. Likely because on very long strings it actually found a match.
But with (>[A-Z_]+){0,200}?
the query still failed.
Update:
I'm seeing these contants:
#define DEFAULT_PARSE_DEPTH_LIMIT 4096
#define INIT_MATCH_STACK_SIZE 160
#define DEFAULT_MATCH_STACK_LIMIT_SIZE 0 /* unlimited */
#define DEFAULT_RETRY_LIMIT_IN_MATCH 10000000
#define DEFAULT_RETRY_LIMIT_IN_SEARCH 0 /* unlimited */
#define DEFAULT_SUBEXP_CALL_LIMIT_IN_SEARCH 0 /* unlimited */
#define DEFAULT_SUBEXP_CALL_MAX_NEST_LEVEL 20
What is interesting is that MATCH has 10M retries limit and SEARCH is unlimited.
I'm calling onig_search(), how come the retry is not unlimited?
Or maybe some other constant is being used? I find it hard to believe that we reach 10M retries.
Also, where could I read about difference between onig_scan
, onig_search
, onig_search_with_param
, onig_match
, onig_match_with_param
?
from oniguruma.
201 * 8 = 1608
it's more like 200^8 = 2.56e18
but definitely wrap each block in its own atomic group
it should limit it to 8
(CREATE_CAMPAIGN_FROM_TABLE(?>(?>>[A-Z_]++)*?>SET_CAMPAIGN_OBJECTIVE_SALES)(?>(?>>[A-Z_]++)*?>CONTINUE_QUICK_CREATE_CAMPAIGN)(?>(?>>[A-Z_]++)*?>SELECT_MANUAL_SALES_CAMPAIGN)(?>(?>>[A-Z_]++)*?>CONTINUE_CAMPAIGN_PACKAGE_SELECTION)(?>(?>>[A-Z_]++)*?>TURN_ADVANTAGE_BUDGET_ON)(?>(?>>[A-Z_]++)*?>SELECT_BUDGET_CURRENCY)(?>(?>>[A-Z_]++)*?>NEXT_CAMPAIGN_EDITOR)(?>(?>>[A-Z_]++)*?>BUDGET_SCHEDULE_ADSET))
from oniguruma.
I think I can fix your regex. Which syntax do you want to use?
syntax-oniguruma? syntax-java? syntax-your-own-JONI?
I need to change the regex depending on which syntax you use.
Your regex has a similar problem to this:
a.*b.*c.*d.*e
The number of backtracks grows exponentially if no match is found.
I would fix this as follows:
a.*+b.*+c.*+d.*+e
possessive (greedy and does not backtrack once match)
Lines 159 to 169 in 00ad92b
"negative look-ahead" is useful for this fix.
negative look-ahead
Line 304 in 00ad92b
Modifying a.*?b
to a(?:(?!b).)*+b
gives us "possessive".
In this case, we are promised that ".
" is not "b
".
This is difficult, so don't worry about figuring it out right now.
from oniguruma.
This is the regular expression for "ONIG_SYNTAX_ONIGURUMA
" .
This regular expression greatly reduces backtracking.
(?<tag0>CREATE_CAMPAIGN_FROM_TABLE){0}(?<tag1>SET_CAMPAIGN_OBJECTIVE_SALES){0}(?<tag2>CONTINUE_QUICK_CREATE_CAMPAIGN){0}(?<tag3>SELECT_MANUAL_SALES_CAMPAIGN){0}(?<tag4>CONTINUE_CAMPAIGN_PACKAGE_SELECTION){0}(?<tag5>TURN_ADVANTAGE_BUDGET_ON){0}(?<tag6>SELECT_BUDGET_CURRENCY){0}(?<tag7>NEXT_CAMPAIGN_EDITOR){0}(?<tag8>BUDGET_SCHEDULE_ADSET){0}(?<tag_char>[A-Z_]){0}(?<tag_end>(?=[>\\s]|$)){0}\\g<tag0>(?>(?~|>\\g<tag1>\\g<tag_end>|(?:>\\g<tag_char>++){0,200}))>\\g<tag1>\\g<tag_end>(?>(?~|>\\g<tag2>\\g<tag_end>|(?:>\\g<tag_char>++){0,200}))>\\g<tag2>\\g<tag_end>(?>(?~|>\\g<tag3>\\g<tag_end>|(?:>\\g<tag_char>++){0,200}))>\\g<tag3>\\g<tag_end>(?>(?~|>\\g<tag4>\\g<tag_end>|(?:>\\g<tag_char>++){0,200}))>\\g<tag4>\\g<tag_end>(?>(?~|>\\g<tag5>\\g<tag_end>|(?:>\\g<tag_char>++){0,200}))>\\g<tag5>\\g<tag_end>(?>(?~|>\\g<tag6>\\g<tag_end>|(?:>\\g<tag_char>++){0,200}))>\\g<tag6>\\g<tag_end>(?>(?~|>\\g<tag7>\\g<tag_end>|(?:>\\g<tag_char>++){0,200}))>\\g<tag7>\\g<tag_end>(?>(?~|>\\g<tag8>\\g<tag_end>|(?:>\\g<tag_char>++){0,200}))>\\g<tag8>\\g<tag_end>
The above regular expression uses "Absent expression".
Lines 369 to 371 in 2640194
This feature allows you to write /a(?:(?!b).)*+b/
concisely.
/a(?:(?!b).)*+b/
== /a(?>(?~|b|.*))b/
There is no need to rush to reply because I understand you are busy.
from oniguruma.
Below is the test code for "/test/test_syntax.c
".
Please rewrite the contents from <tag0>
to <tag8>
and use them.
// for oniguruma6.9.9 #290
Syntax = ONIG_SYNTAX_ONIGURUMA;
x2(
"(?<tag0>AAA){0}"
"(?<tag1>BBB){0}"
"(?<tag2>CCC){0}"
"(?<tag3>DDD){0}"
"(?<tag4>EEE){0}"
"(?<tag5>FFF){0}"
"(?<tag6>GGG){0}"
"(?<tag7>HHH){0}"
"(?<tag8>III){0}"
"(?<tag_char>[A-Z_]){0}"
"(?<tag_end>(?=[>\\s]|$)){0}"
////////// 0 ////////////
"\\g<tag0>"
////////// 1 ////////////
"(?>"
"(?~|"
">\\g<tag1>\\g<tag_end>"
"|"
"(?:"
">\\g<tag_char>++"
"){0,200}"
")"
")"
">\\g<tag1>\\g<tag_end>"
////////// 2 ////////////
"(?>"
"(?~|"
">\\g<tag2>\\g<tag_end>"
"|"
"(?:"
">\\g<tag_char>++"
"){0,200}"
")"
")"
">\\g<tag2>\\g<tag_end>"
////////// 3 ////////////
"(?>"
"(?~|"
">\\g<tag3>\\g<tag_end>"
"|"
"(?:"
">\\g<tag_char>++"
"){0,200}"
")"
")"
">\\g<tag3>\\g<tag_end>"
////////// 4 ////////////
"(?>"
"(?~|"
">\\g<tag4>\\g<tag_end>"
"|"
"(?:"
">\\g<tag_char>++"
"){0,200}"
")"
")"
">\\g<tag4>\\g<tag_end>"
////////// 5 ////////////
"(?>"
"(?~|"
">\\g<tag5>\\g<tag_end>"
"|"
"(?:"
">\\g<tag_char>++"
"){0,200}"
")"
")"
">\\g<tag5>\\g<tag_end>"
////////// 6 ////////////
"(?>"
"(?~|"
">\\g<tag6>\\g<tag_end>"
"|"
"(?:"
">\\g<tag_char>++"
"){0,200}"
")"
")"
">\\g<tag6>\\g<tag_end>"
////////// 7 ////////////
"(?>"
"(?~|"
">\\g<tag7>\\g<tag_end>"
"|"
"(?:"
">\\g<tag_char>++"
"){0,200}"
")"
")"
">\\g<tag7>\\g<tag_end>"
////////// 8 ////////////
"(?>"
"(?~|"
">\\g<tag8>\\g<tag_end>"
"|"
"(?:"
">\\g<tag_char>++"
"){0,200}"
")"
")"
">\\g<tag8>\\g<tag_end>"
, "AAA>CCC>BBB>CCC>DDD>EEE>AAA>FFF>GGG>HHH>III>JJJ>III>JJJ", 0, 43);
// Start of the matched position == 0
// End of the matched position == 43
Below is the command for testing above.
Please copy "/test/test_syntax.c
" to "Documents
" folder.
$ gcc ~/Documents/test_syntax.c -L/usr/local/lib -lonig
$ ./a.out
from oniguruma.
Unlimited
onig_set_retry_limit_in_match(0);
onig_set_retry_limit_in_search(0);
Called these two functions and still getting "retry-limit-in-match over" error on the example I posted above.
Edit:
Extra interesting detail:
When called these two functions right after onig_initialize() Iget the following test failing with the "retry-limit-in-match over" error:
regexp_like("123RMA", "(?<!RMA)$");
Did calling them with zero set the limit to actual zero?
Edit2:
Calling these fixes the example.
Will run more tests soon to see if any query still hits the error or any other bad effects with such limits.
onig_set_retry_limit_in_match(std::numeric_limits<unsigned long>::max());
onig_set_retry_limit_in_search(std::numeric_limits<unsigned long>::max());
@tonco-miyazawa
Thank you for the ideas. I don't understand them at the moment, but they might come in handy when we start the migration for real.
I haven't decided yet on the final syntax we want to use. Probably ONIG_SYNTAX_ONIGURUMA if I can figure out how to support '(?s)' in it.
from oniguruma.
Related Issues (20)
- oniguruma not able to installed on PPC64le architecture HOT 3
- `.{0,99}` and `.*` behave differently on short input HOT 2
- mbc_enc_len(const UChar* p) to be improved HOT 4
- Does Oniguruma support POSIX collating symbols or equivalence classes? HOT 1
- New version?🤔 HOT 1
- ONIG_SYN_CONTEXT_INDEP_REPEAT_OPS not working for ^* pattern HOT 1
- Literal escaped braces HOT 2
- what is escape code for `.` (literal dot)? HOT 1
- onig_match() can return wrong results with lookbehind at the end of the string HOT 2
- ONIG_SYNTAX_EMACS doesn't support "shy groups"
- With ONIG_SYNTAX_DEFAULT pattern '(?s)ABC' fails with 'undefined group option'. HOT 12
- Error 'unmatched range specifier in char-class' with hyphen in character class. HOT 1
- typos HOT 1
- :alpha: character class matches "non-letter" unicode characters. HOT 4
- Sample pattern and content to trigger error in onig_search? HOT 2
- Invalid utf8 sequence matches the pattern while it probably should not. HOT 1
- Test files ( 'e' function )
- How do I statically link the library to my project without installing it on my system
- How to build ARM64 platform for Windows HOT 1
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from oniguruma.