Regex experts - Why does this email address pattern matching code never return?

[Jaikiran Pai]

My skills at regex aren't too great but I have a relatively simple regex which is expected to match email address patterns from a string. The code is pretty straightforward and works fine except when it gets passed a very specific input. While trying to match that input it goes into a never ending loop within the Java regex library. The CPU gets pegged to 100% and even after a few hours of running it never completes. Here's a very simple code which reproduces it:

package org.myapp;

public class RegexFun {
    public static void main(String[] args) {
        // The very specific content which triggers the problem. It's a series of underscore characters
        final String content =  "______________________________________________________________________";
        // The email address matching pattern
        final Pattern emailPattern = Pattern.compile("(\\w+)([\\._%+-]\\w+)*@(\\w+[\\.-])(\\w+)(\\.\\w+)*");
        final Matcher matcher = emailPattern.matcher(content);
        final Set<String> addresses = new HashSet<String>();
        while (matcher.find()) { // this call never returns
            final String emailFound = matcher.group().toLowerCase();
            addresses.add(emailFound);
        }
        System.out.println("got addresses " + addresses);
    }

}

Here's the thread dump taken when this code never returned after a few minutes:

"main" prio=10 tid=0xb6709800 nid=0x4710 runnable [0xb6888000]
   java.lang.Thread.State: RUNNABLE
	at java.util.regex.Pattern$BmpCharProperty.match(Pattern.java:3366)
	at java.util.regex.Pattern$Curly.match(Pattern.java:3737)
	at java.util.regex.Pattern$BmpCharProperty.match(Pattern.java:3366)
	at java.util.regex.Pattern$GroupHead.match(Pattern.java:4168)
	at java.util.regex.Pattern$Loop.match(Pattern.java:4295)
	at java.util.regex.Pattern$GroupTail.match(Pattern.java:4227)
	at java.util.regex.Pattern$Curly.match0(Pattern.java:3782)
	at java.util.regex.Pattern$Curly.match(Pattern.java:3744)
	at java.util.regex.Pattern$BmpCharProperty.match(Pattern.java:3366)
	at java.util.regex.Pattern$GroupHead.match(Pattern.java:4168)
	at java.util.regex.Pattern$Loop.match(Pattern.java:4295)
	at java.util.regex.Pattern$GroupTail.match(Pattern.java:4227)
	at java.util.regex.Pattern$Curly.match0(Pattern.java:3782)
	at java.util.regex.Pattern$Curly.match(Pattern.java:3744)
	at java.util.regex.Pattern$BmpCharProperty.match(Pattern.java:3366)
	at java.util.regex.Pattern$GroupHead.match(Pattern.java:4168)
	at java.util.regex.Pattern$Loop.match(Pattern.java:4295)
	at java.util.regex.Pattern$GroupTail.match(Pattern.java:4227)
	at java.util.regex.Pattern$Curly.match0(Pattern.java:3782)
	at java.util.regex.Pattern$Curly.match(Pattern.java:3744)
	at java.util.regex.Pattern$BmpCharProperty.match(Pattern.java:3366)
	at java.util.regex.Pattern$GroupHead.match(Pattern.java:4168)
	at java.util.regex.Pattern$Loop.match(Pattern.java:4295)
	at java.util.regex.Pattern$GroupTail.match(Pattern.java:4227)
	at java.util.regex.Pattern$Curly.match0(Pattern.java:3782)
	at java.util.regex.Pattern$Curly.match(Pattern.java:3744)
	at java.util.regex.Pattern$BmpCharProperty.match(Pattern.java:3366)
	at java.util.regex.Pattern$GroupHead.match(Pattern.java:4168)
	at java.util.regex.Pattern$Loop.match(Pattern.java:4295)
	at java.util.regex.Pattern$GroupTail.match(Pattern.java:4227)
	at java.util.regex.Pattern$Curly.match0(Pattern.java:3782)
	at java.util.regex.Pattern$Curly.match(Pattern.java:3744)
	at java.util.regex.Pattern$BmpCharProperty.match(Pattern.java:3366)
	at java.util.regex.Pattern$GroupHead.match(Pattern.java:4168)
	at java.util.regex.Pattern$Loop.match(Pattern.java:4295)
	at java.util.regex.Pattern$GroupTail.match(Pattern.java:4227)
	at java.util.regex.Pattern$Curly.match0(Pattern.java:3782)
	at java.util.regex.Pattern$Curly.match(Pattern.java:3744)
	at java.util.regex.Pattern$BmpCharProperty.match(Pattern.java:3366)
	at java.util.regex.Pattern$GroupHead.match(Pattern.java:4168)
	at java.util.regex.Pattern$Loop.match(Pattern.java:4295)
	at java.util.regex.Pattern$GroupTail.match(Pattern.java:4227)
	at java.util.regex.Pattern$Curly.match0(Pattern.java:3782)
	at java.util.regex.Pattern$Curly.match(Pattern.java:3744)
	at java.util.regex.Pattern$BmpCharProperty.match(Pattern.java:3366)
	at java.util.regex.Pattern$GroupHead.match(Pattern.java:4168)
	at java.util.regex.Pattern$Loop.match(Pattern.java:4295)
	at java.util.regex.Pattern$GroupTail.match(Pattern.java:4227)
	at java.util.regex.Pattern$Curly.match0(Pattern.java:3782)
	at java.util.regex.Pattern$Curly.match(Pattern.java:3744)
	at java.util.regex.Pattern$BmpCharProperty.match(Pattern.java:3366)
	at java.util.regex.Pattern$GroupHead.match(Pattern.java:4168)
	at java.util.regex.Pattern$Loop.match(Pattern.java:4295)
	at java.util.regex.Pattern$GroupTail.match(Pattern.java:4227)
	at java.util.regex.Pattern$Curly.match0(Pattern.java:3782)
	at java.util.regex.Pattern$Curly.match(Pattern.java:3744)
	at java.util.regex.Pattern$BmpCharProperty.match(Pattern.java:3366)
	at java.util.regex.Pattern$GroupHead.match(Pattern.java:4168)
	at java.util.regex.Pattern$Loop.match(Pattern.java:4295)
	at java.util.regex.Pattern$GroupTail.match(Pattern.java:4227)
	at java.util.regex.Pattern$Curly.match0(Pattern.java:3782)
	at java.util.regex.Pattern$Curly.match(Pattern.java:3744)
	at java.util.regex.Pattern$BmpCharProperty.match(Pattern.java:3366)
	at java.util.regex.Pattern$GroupHead.match(Pattern.java:4168)
	at java.util.regex.Pattern$Loop.match(Pattern.java:4295)
	at java.util.regex.Pattern$GroupTail.match(Pattern.java:4227)
	at java.util.regex.Pattern$Curly.match0(Pattern.java:3782)
	at java.util.regex.Pattern$Curly.match(Pattern.java:3744)
	at java.util.regex.Pattern$BmpCharProperty.match(Pattern.java:3366)
	at java.util.regex.Pattern$GroupHead.match(Pattern.java:4168)
	at java.util.regex.Pattern$Loop.matchInit(Pattern.java:4314)
	at java.util.regex.Pattern$Prolog.match(Pattern.java:4251)
	at java.util.regex.Pattern$GroupTail.match(Pattern.java:4227)
	at java.util.regex.Pattern$Curly.match0(Pattern.java:3782)
	at java.util.regex.Pattern$Curly.match(Pattern.java:3744)
	at java.util.regex.Pattern$GroupHead.match(Pattern.java:4168)
	at java.util.regex.Pattern$Start.match(Pattern.java:3055)
	at java.util.regex.Matcher.search(Matcher.java:1105)
	at java.util.regex.Matcher.find(Matcher.java:535)
	at org.myapp.RegexFun.main(RegexFun.java:15)
	at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
	at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:39)
	at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:25)
	at java.lang.reflect.Method.invoke(Method.java:597)
	at com.intellij.rt.execution.application.AppMain.main(AppMain.java:120)

Multiple thread dumps at regular interval show the same stacktrace. I'm on:

java version "1.6.0_26"
Java(TM) SE Runtime Environment (build 1.6.0_26-b03)
Java HotSpot(TM) Server VM (build 20.1-b02, mixed mode)

I did find a similar JDK bug reported here http://bugs.java.com/bugdatabase/view_bug.do?bug_id=6882582 but in my case the code never returns back not even with that error.

Does anyone know why this regex pattern with that input would trigger this never ending loop within the JDK classes? Any inputs on how to get this working or do you see something that can be improved in that regex pattern?

[Winston Gutkowski]

Jaikiran Pai wrote:My skills at regex aren't too great but I have a relatively simple regex which is expected to match email address patterns from a string. The code is pretty straightforward and works fine except when it gets passed a very specific input.

What input? Just off the top of my head, that '\\w+' looks wrong, but without knowing when it has problems, it's difficult to say.

My advice: Write out, in English, what you expect that regex to do. You can even post it here if you want. There are plenty of regex dweebs here who will tell you if you're wrong.

Winston

[Jaikiran Pai]

Winston Gutkowski wrote:
What input?

The one in the code I posted:

// The very specific content which triggers the problem. It's a series of underscore characters  
        final String content =  "______________________________________________________________________";  

Winston Gutkowski wrote:
My advice: Write out, in English, what you expect that regex to do.

I idea is to match/find a string which could be considered as a email addresses. So:

1) A word (ex: abcd)
2) possibly followed by certain special characters (ex: the underscore character, the dot character)
3) possibly followed by another word again
4) Followed by the @ character
5) Followed by another word (ex: gmail)
6) Followed by the dot character
7) Followed by another word (ex: com)
8) Possibly followed by a combination of dot character and a word (ex: .co.uk)

Putting that all together it would be [e-mail] (just a random example).

Winston Gutkowski wrote:
There are plenty of regex dweebs here who will tell you if you're wrong ;)

That's what I'm hoping for

[Ulf Dittmer]

My guess is that it will terminate eventually, given enough time and memory. Have you tried it with a much shorter input string only composed of underscore characters? This could be a situation where the time required grows exponentially with the length of the input string; see http://ocpsoft.org/regex/how-to-interrupt-a-long-running-infinite-java-regular-expression/

[Winston Gutkowski]

Jaikiran Pai wrote:1) A word (ex: abcd)

OK, well the boundary is '\\w', NOT '\\w+'. You also need to define what a "word" is.

2) possibly followed by certain special characters (ex: the underscore character, the dot character)

Too vague. What characters? Precisely. E-mail addresses have a specification, so you need to get those from there.

3) possibly followed by another word again

Again: too vague. Do you specifically mean the characters detailed in Steps 1 and 2?

4) Followed by the @ character

Fair enough. But is an e-mail address allowed to have TWO '@'s?

5) Followed by another word (ex: gmail)

See above.

6) Followed by the dot character

Fine.

7) Followed by another word (ex: com)

Are you sure?

8) Possibly followed by a combination of dot character and a word (ex: .co.uk)

I think you'll find that these last 3 things are covered by the specification for domain names.

Putting that all together it would be [e-mail] (just a random example).

Right. But, as you're discovering, what you really want are examples that MUSTN'T match.

HIH

Winston

[Bin Smith]

This is happening because of backtracking of greedy quantifiers in regex.
To avoid backtracking I know two choices : atomic group or possessive quantifiers. Both mean match as many symbols as possible with greedy quantifier and never release(backtrack) symbols.
So I just used atomic group for first greedy plus and problem has gone.
So, regex becomes:

(?>\\w+)([\\._%+-]\\w+)*@(\\w+[\\.-])(\\w+)(\\.\\w+)*

(?>\\w+) means, that it matches as many one of [a-zA-Z0-9_] as possible and never release matched symbol.

This article will be useful to read.

[Jaikiran Pai]

Ulf Dittmer wrote:My guess is that it will terminate eventually, given enough time and memory. Have you tried it with a much shorter input string only composed of underscore characters? This could be a situation where the time required grows exponentially with the length of the input string;

Good point. I hadn't read about the backtracking so wasn't aware of the exponential time possibility. It looks like you are right, since I modified the code to print out the time it takes to do the computation, every time I add one more underscore character in the input:

public static void main(String[] args) {
        // The very specific content which triggers the problem. It's a series of underscore characters
        StringBuilder content =  new StringBuilder();
        for (int i = 0; i < 100; i++) {
            content.append("_");
            // The email address matching pattern
            final Pattern emailPattern = Pattern.compile("(\\w+)([\\._%+-]\\w+)*@(\\w+[\\.-])(\\w+)(\\.\\w+)*");
            final Matcher matcher = emailPattern.matcher(content);
            final Set<String> addresses = new HashSet<String>();
            final long start = System.currentTimeMillis();
            while (matcher.find()) { // this call never returns
                final String emailFound = matcher.group().toLowerCase();
                addresses.add(emailFound);
            }
            final long end = System.currentTimeMillis();
            System.out.println("Computation for a string with " + (i+1) + " underscore characters completed in " + (end - start) + " milli seconds");
        }
    }

Here are the timings and the program hasn't yet finished:

Computation for a string with 1 underscore characters completed in 0 milli seconds
Computation for a string with 2 underscore characters completed in 0 milli seconds
Computation for a string with 3 underscore characters completed in 0 milli seconds
Computation for a string with 4 underscore characters completed in 0 milli seconds
Computation for a string with 5 underscore characters completed in 0 milli seconds
Computation for a string with 6 underscore characters completed in 0 milli seconds
Computation for a string with 7 underscore characters completed in 0 milli seconds
Computation for a string with 8 underscore characters completed in 0 milli seconds
Computation for a string with 9 underscore characters completed in 1 milli seconds
Computation for a string with 10 underscore characters completed in 0 milli seconds
Computation for a string with 11 underscore characters completed in 1 milli seconds
Computation for a string with 12 underscore characters completed in 2 milli seconds
Computation for a string with 13 underscore characters completed in 2 milli seconds
Computation for a string with 14 underscore characters completed in 3 milli seconds
Computation for a string with 15 underscore characters completed in 5 milli seconds
Computation for a string with 16 underscore characters completed in 10 milli seconds
Computation for a string with 17 underscore characters completed in 12 milli seconds
Computation for a string with 18 underscore characters completed in 16 milli seconds
Computation for a string with 19 underscore characters completed in 24 milli seconds
Computation for a string with 20 underscore characters completed in 23 milli seconds
Computation for a string with 21 underscore characters completed in 3 milli seconds
Computation for a string with 22 underscore characters completed in 4 milli seconds
Computation for a string with 23 underscore characters completed in 8 milli seconds
Computation for a string with 24 underscore characters completed in 13 milli seconds
Computation for a string with 25 underscore characters completed in 20 milli seconds
Computation for a string with 26 underscore characters completed in 33 milli seconds
Computation for a string with 27 underscore characters completed in 54 milli seconds
Computation for a string with 28 underscore characters completed in 89 milli seconds
Computation for a string with 29 underscore characters completed in 137 milli seconds
Computation for a string with 30 underscore characters completed in 228 milli seconds
Computation for a string with 31 underscore characters completed in 362 milli seconds
Computation for a string with 32 underscore characters completed in 585 milli seconds
Computation for a string with 33 underscore characters completed in 949 milli seconds
Computation for a string with 34 underscore characters completed in 1515 milli seconds
Computation for a string with 35 underscore characters completed in 2461 milli seconds
Computation for a string with 36 underscore characters completed in 4028 milli seconds
Computation for a string with 37 underscore characters completed in 6413 milli seconds
Computation for a string with 38 underscore characters completed in 10537 milli seconds
Computation for a string with 39 underscore characters completed in 17184 milli seconds
Computation for a string with 40 underscore characters completed in 27485 milli seconds
Computation for a string with 41 underscore characters completed in 43936 milli seconds
Computation for a string with 42 underscore characters completed in 71364 milli seconds
Computation for a string with 43 underscore characters completed in 116703 milli seconds
Computation for a string with 44 underscore characters completed in 186775 milli seconds
Computation for a string with 45 underscore characters completed in 302412 milli seconds
Computation for a string with 46 underscore characters completed in 485721 milli seconds
<still running>

[Jaikiran Pai]

Winston Gutkowski wrote:

Jaikiran Pai wrote:1) A word (ex: abcd)

OK, well the boundary is '\\w', NOT '\\w+'.

Winston Gutkowski wrote:
You also need to define what a "word" is.

For this example, as noted in the local part section http://en.wikipedia.org/wiki/Email_address#Local_part I'm considering multiple instances of the characters between a-z or A-Z or the digits 0-9.

Winston Gutkowski wrote:

2) possibly followed by certain special characters (ex: the underscore character, the dot character)

Too vague. What characters? Precisely. E-mail addresses have a specification, so you need to get those from there.

In this example, I'm only considering + - . _ and % which are all allowed by the spec.

Winston Gutkowski wrote:

3) possibly followed by another word again

Again: too vague. Do you specifically mean the characters detailed in Steps 1 and 2?

More precisely, I'm considering multiple instances of the characters between a-z or A-Z or the digits 0-9 here too.

Winston Gutkowski wrote:

5) Followed by another word (ex: gmail)

See above.

In this example, I'm considering multiple instances of the characters between a-z or A-Z or the digits 0-9.

Winston Gutkowski wrote:

7) Followed by another word (ex: com)

Are you sure?

The domain name, allows letters and digits (which is what I vaguely called a word) to be part of the domain. So yes.

[Jaikiran Pai]

Volodymyr Levytskyi wrote:This is happening because of backtracking of greedy quantifiers in regex.
To avoid backtracking I know two choices : atomic group or possessive quantifiers. Both mean match as many symbols as possible with greedy quantifier and never release(backtrack) symbols.
So I just used atomic group for first greedy plus and problem has gone.
So, regex becomes:

(?>\\w+)([\\._%+-]\\w+)*@(\\w+[\\.-])(\\w+)(\\.\\w+)*

(?>\\w+) means, that it matches as many one of [a-zA-Z0-9_] as possible and never release matched symbol.

Thank you for explaining that change, I'll give that a try.

Volodymyr Levytskyi wrote:
This article will be useful to read.

I was actually reading that very article from the one Ulf linked to. I'm going to spend some more time to understand it completely.

[Jeanne Boyarsky]

Another approach is to simplify the problem. Real humans don't have long strings of underscores in their email. If you see say five or more underscores, you could skip the regexp check completely and just assume it should be invalid/removed from the list.

[Akaine Harga]

I always used this regexp to validate emails, works just fine: ^[_A-Za-z0-9-]+(\\.[_A-Za-z0-9-]+)*@[A-Za-z0-9-]+(\\.[A-Za-z0-9-]+)*(\\.[A-Za-z]{2,})$

[Ulf Dittmer]

As I understand it, the problem is not validating emails, it's finding emails in a larger piece of text - a slightly different problem. If the problem is validation, then using something like org.apache.commons.validator.routines.EmailValidator is likely a better approach than trying to roll one's own (which invariably is either too strict or too loose).

[Jaikiran Pai]

Ulf Dittmer wrote:As I understand it, the problem is not validating emails, it's finding emails in a larger piece of test

That's correct.

[Jaikiran Pai]

The article about regex backtracking helped. While reading that article and co-relating it with the email pattern I had, I realized there was a small but significant oversight in that pattern:

 Pattern.compile("(\\w+)([\\._%+-]\\w+)*@(\\w+[\\.-])(\\w+)(\\.\\w+)*");

a \w already includes the _ character so there's no need to include it in the second group in that pattern. I changed that pattern to:

 Pattern.compile("(\\w+)([\\.%+-]\\w+)*@(\\w+[\\.-])(\\w+)(\\.\\w+)*");

and that fixed the backtracking issue which was causing the never ending loop.