From: demerphq Date: Wed, 17 Jun 2009 15:46:54 GMT Subject: Re: [PATCH] avoid exponential regex match for java and objc function names Message-ID: <9b18b3110906170846o5b3c3000r72506bf62765a044@mail.gmail.com> In-Reply-To: <1245248766-14867-1-git-send-email-bonzini@gnu.org> 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 : > 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 > --- >  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/"