Re: [PATCH] avoid exponential regex match for java and objc function names
From: demerphq <hidden>
Date: 2016-06-15 22:46:57
Possibly related (same subject, not in this thread)
- 2016-06-15 · Re: [PATCH] avoid exponential regex match for java and objc function names · Junio C Hamano <hidden>
- 2016-06-15 · Re: [PATCH] avoid exponential regex match for java and objc function names · Paolo Bonzini <hidden>
Just a note, but If the Java regex library you are using supports the PCRE compatible (?>...) atomic matching construct (or their equivalent *+ and ++) then these patterns can be significantly improved beyond their current state. 2009/6/17 Paolo Bonzini [off-list ref]:
quoted hunk ↗ jump to hunk
In the old regex ^[ \t]*(([ \t]*[A-Za-z_][A-Za-z_0-9]*){2,}[ \t]*\([^;]*)$ ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ you can backtrack arbitrarily from [A-Za-z_0-9]* into [A-Za-z_], thus causing an exponential number of backtracks. Ironically it also causes the regex not to work as intended; for example "catch" can match the underlined part of the regex, the first repetition matching "c" and the second matching "atch". The replacement regex avoids this problem, because it makes sure that at least a space/tab is eaten on each repetition. In other words, a suffix of a repetition can never be a prefix of the next repetition. Signed-off-by: Paolo Bonzini <redacted> --- userdiff.c | 5 +++-- 1 files changed, 3 insertions(+), 2 deletions(-)diff --git a/userdiff.c b/userdiff.c index d556da9..57529ae 100644 --- a/userdiff.c +++ b/userdiff.c@@ -13,7 +13,8 @@ PATTERNS("html", "^[ \t]*(<[Hh][1-6][ \t].*>.*)$","[^<>= \t]+|[^[:space:]]|[\x80-\xff]+"), PATTERNS("java", "!^[ \t]*(catch|do|for|if|instanceof|new|return|switch|throw|while)\n" - "^[ \t]*(([ \t]*[A-Za-z_][A-Za-z_0-9]*){2,}[ \t]*\\([^;]*)$", + "^[ \t]*(([A-Za-z_][A-Za-z_0-9]*[ \t]+)+[A-Za-z_][A-Za-z_0-9]*[ \t]*\\([^;]*)$", + /* -- */ "[a-zA-Z_][a-zA-Z0-9_]*" "|[-+0-9.e]+[fFlL]?|0[xXbB]?[0-9a-fA-F]+[lL]?" "|[-+*/<>%&^|=!]="@@ -25,7 +26,7 @@ PATTERNS("objc",/* Objective-C methods */ "^[ \t]*([-+][ \t]*\\([ \t]*[A-Za-z_][A-Za-z_0-9* \t]*\\)[ \t]*[A-Za-z_].*)$\n" /* C functions */ - "^[ \t]*(([ \t]*[A-Za-z_][A-Za-z_0-9]*){2,}[ \t]*\\([^;]*)$\n" + "^[ \t]*(([A-Za-z_][A-Za-z_0-9]*[ \t]+)+[A-Za-z_][A-Za-z_0-9]*[ \t]*\\([^;]*)$\n" /* Objective-C class/protocol definitions */ "^(@(implementation|interface|protocol)[ \t].*)$", /* -- */ -- 1.6.0.3 -- To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
-- perl -Mre=debug -e "/just|another|perl|hacker/"