Re: [PATCH] avoid exponential regex match for java and objc function names

[demerphq <demerphq@gmail.com>]

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 <bonzini@gnu.org>:
> 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 <bonzini@gnu.org>
> ---
>  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/"