Git Product home page Git Product logo

Comments (23)

kkos avatar kkos commented on September 5, 2024 2

.(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.

tonco-miyazawa avatar tonco-miyazawa commented on September 5, 2024 1

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.

RedCMD avatar RedCMD commented on September 5, 2024 1

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.

spershin avatar spershin commented on September 5, 2024 1

@kkos , @tonco-miyazawa
Seems like @simulified needs to be banned from GH, not sure how to do it.

from oniguruma.

kkos avatar kkos commented on September 5, 2024 1

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.

tonco-miyazawa avatar tonco-miyazawa commented on September 5, 2024

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*$/

  1. ^a* matches up to "aaaa" .

  2. But since "$" is not found, "a*" lets go of the last "a" of "aaaa" .
    At this time, the count increases by 1 .

  3. 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.

oniguruma/src/regint.h

Line 97 in e62a8e5

#define DEFAULT_RETRY_LIMIT_IN_MATCH 10000000

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.

tonco-miyazawa avatar tonco-miyazawa commented on September 5, 2024

I will show you how to suppress retries in regular expressions.

(?>a*)

oniguruma/doc/RE

Lines 318 to 319 in e62a8e5

(?>subexp) atomic group
no backtracks in subexp.

a*+

oniguruma/doc/RE

Lines 159 to 169 in e62a8e5

possessive (greedy and does not backtrack once match)
?+ 1 or 0 times
*+ 0 or more times
++ 1 or more times
{n,m} (n > m) at least m but not more than n times
{n,m}+, {n,}+, {n}+ are possessive operators in ONIG_SYNTAX_JAVA and
ONIG_SYNTAX_PERL only.
ex. /a*+/ === /(?>a*)/

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.

jliu-siteimprove avatar jliu-siteimprove commented on September 5, 2024

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.

tonco-miyazawa avatar tonco-miyazawa commented on September 5, 2024

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".

oniguruma/src/oniguruma.h

Lines 37 to 39 in e62a8e5

#define ONIGURUMA_VERSION_MAJOR 6
#define ONIGURUMA_VERSION_MINOR 9
#define ONIGURUMA_VERSION_TEENY 9

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.

kkos avatar kkos commented on September 5, 2024

@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.

tonco-miyazawa avatar tonco-miyazawa commented on September 5, 2024

@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.

oniguruma/doc/RE

Lines 292 to 299 in e62a8e5

/(?CIL).../, /(?CIL:...)/ whole option
This option must be placed in a position that
affects the entire regular expression.
C: ONIG_OPTION_DONT_CAPTURE_GROUP
I: ONIG_OPTION_IGNORECASE_IS_ASCII
L: ONIG_OPTION_FIND_LONGEST

from oniguruma.

jliu-siteimprove avatar jliu-siteimprove commented on September 5, 2024

Thanks @kkos @tonco-miyazawa Yes, we are using IGNORE-CASE and \S which cause the problem

from oniguruma.

tonco-miyazawa avatar tonco-miyazawa commented on September 5, 2024

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.

RedCMD avatar RedCMD commented on September 5, 2024

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.

tonco-miyazawa avatar tonco-miyazawa commented on September 5, 2024

@RedCMD

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.

tonco-miyazawa avatar tonco-miyazawa commented on September 5, 2024

@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.

microsoft/vscode#40279 (comment)

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.

spershin avatar spershin commented on September 5, 2024

@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.

spershin avatar spershin commented on September 5, 2024

@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.

RedCMD avatar RedCMD commented on September 5, 2024

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.

tonco-miyazawa avatar tonco-miyazawa commented on September 5, 2024

@spershin

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)

oniguruma/doc/RE

Lines 159 to 169 in 00ad92b

possessive (greedy and does not backtrack once match)
?+ 1 or 0 times
*+ 0 or more times
++ 1 or more times
{n,m} (n > m) at least m but not more than n times
{n,m}+, {n,}+, {n}+ are possessive operators in ONIG_SYNTAX_JAVA and
ONIG_SYNTAX_PERL only.
ex. /a*+/ === /(?>a*)/

"negative look-ahead" is useful for this fix.
negative look-ahead

oniguruma/doc/RE

Line 304 in 00ad92b

(?!subexp) negative look-ahead

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.

tonco-miyazawa avatar tonco-miyazawa commented on September 5, 2024

@spershin

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".

oniguruma/doc/RE

Lines 369 to 371 in 2640194

(?~|absent|exp) Absent expression (* original)
This works like "exp", but it is limited by the range
that does not include the string match with <absent>.

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.

tonco-miyazawa avatar tonco-miyazawa commented on September 5, 2024

@spershin

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.

spershin avatar spershin commented on September 5, 2024

Unlimited
onig_set_retry_limit_in_match(0);
onig_set_retry_limit_in_search(0);

@kkos

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)

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo 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.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.