Regular expressions — Java Fundamentals

A regular expression is a small program, and java.util.regex runs it by backtracking — trying a possibility, and on failure winding back to try another. That single implementation fact explains everything worth knowing here: why compile is worth hoisting, why greedy and reluctant differ, and why one pattern that looks harmless can take longer than the age of the universe on a forty-character input.

`Pattern` and `Matcher`

java

Pattern p = Pattern.compile("(\\d{4})-(\\d{2})-(\\d{2})");   // compile once
Matcher m = p.matcher("due 2026-09-11 ok");                  // one per input
 
if (m.find()) {
    m.group();    // "2026-09-11"  — group 0 is the whole match
    m.group(1);   // "2026"        — groups number by opening parenthesis
    m.start();    // 4
}

Pattern is immutable and thread-safe; Matcher is neither and is cheap. The split matters because compiling parses the pattern and builds a node tree, and the convenience methods hide that:

java

if (line.matches("\\d+"))               // compiles a Pattern. Every call.

String.matches and replaceAll call Pattern.compile internally, every time. In a loop over a million lines that is a million compilations, and hoisting the Pattern into a static final is worth a lot:

300,000 calls each, after warm-upplaintext

line.matches("\\d+")          35 ms   177,600,000 bytes
d.matcher(line).matches()      9 ms    52,800,000 bytes

split is the exception, and hoisting it makes things worse. For a separator that is a single non-metacharacter — or a backslash followed by a non-alphanumeric — String.split takes a fast path that never touches the regex engine at all:

the same 300,000 callsplaintext

split(",")     one char, not a metachar     28 ms   120,000,000 bytes
split("\\.")    escaped metachar             25 ms   120,000,000 bytes
split(".")     one char, IS a metachar      89 ms   256,800,000 bytes
split(",,")    two characters               34 ms   187,200,000 bytes
PATTERN.split(line)  pre-compiled           52 ms   172,800,000 bytes

The hoisted Pattern is the slowest single-character row on the list. It drags a loop that had escaped the engine back into it.

The rule, then, is not "always hoist" — it is know which convenience method is actually expensive. matches and replaceAll are; split on a literal separator is not.

The pieces

	Matches
`.`	any character except a line terminator
`\d` `\w` `\s`	digit, word character, whitespace (and `\D` `\W` `\S` for the negations)
`[a-z0-9_]`	a character class — a set, not a sequence
`*` `+` `?`	zero or more, one or more, zero or one
`{2,5}`	between two and five
`^` `$`	start and end of input, or of a line under `MULTILINE`
`\b`	a word boundary — a position, not a character
`(…)`	a capturing group
`(?:…)`	a group that does not capture
`(?<year>…)`	a named group, read back with `m.group("year")`

In Java the pattern is a String first, so every backslash is written twice: \\d in source is \d in the pattern. That doubling is the commonest source of a pattern that silently matches nothing, and the reason a long pattern is better built from a named constant you can read than inlined into a call.

Greedy, reluctant, possessive

Three behaviours, and the third is the one almost nobody uses and most needs.

java

String s = "<a>text<b>";
System.out.println(s.replaceAll("<.*>", "X"));    // greedy
System.out.println(s.replaceAll("<.*?>", "X"));   // reluctant
System.out.println(s.replaceAll("<.*+>", "X"));   // possessive

What does this print?

.* is greedy: it takes everything it can and then gives characters back until the rest of the pattern fits — so it matches from the first < to the last >, swallowing text along with the tags, and the whole line becomes one X. .*? is reluctant: it takes as little as possible and adds only when forced, so it stops at the first >, matches each tag on its own, and leaves text where it was.

.*+ is possessive: it takes everything and refuses to give any back. If the rest of the pattern then cannot match, the whole attempt fails rather than retrying — which is why the third line prints the input unchanged: .*+ swallowed the final > too, and would not hand it back. That sounds worse than greedy and is the entire fix for the next section.

Under the hood: backtracking, and when it explodes

Java's engine tries a path and unwinds on failure. For most patterns the number of paths is small. For some it is not. Press Play and watch it work on six characters:

Attempt 32 of 32. The outer + ran 6 times, taking 1 then 1 then 1 then 1 then 1 then 1. That was the last split, so now — and only now — the engine may answer "no match". Six as cost 32 attempts; 28 cost 134.2 million — 13.4 s.

32 / 32

The outer + can run any number of times, so it can carve six as into 6, into 5+1, into 4+2, into 4+1+1, and on down to six iterations of one character each. Every one of those is a distinct path, every one ends at the same missing b, and the engine may not conclude "no match" until it has tried the last of them. Thirty-two attempts for six characters.

Each extra a doubles that. Six is 32; twenty-eight is 134 million, which is about thirteen seconds of a core doing nothing else. That is why a pattern can pass every test you write and still hang in production — the input that breaks it is a few characters longer than the ones that did not, and nothing warns you as you cross over.

Compare a+b against (a+)+b, both matched against a string of as with no b.

a+b consumes every a once, looks for b, fails. n + 1 steps.
(a+)+b has an inner + and an outer +, so the group can split the as in any combination — 1+1+1, 2+1, 1+2, 3. There are exactly 2^(n-1) such splits, and the engine tries every one before it can conclude there is no b.

That is a counting fact, not an implementation quirk: any engine that backtracks and does not memoise has to visit all of them. At 32 characters it is 2.1 billion attempts against 33.

The shape to recognise is a quantifier inside a group that is itself quantified, where the inner and outer can match the same characters: (a+)+, (a|a)*, (\s*,)*. It is called catastrophic backtracking, and it is a denial-of-service vector whenever the input comes from a request — one crafted field and a thread is gone.

Three fixes:

Make the inner quantifier possessive: (a++)+b. The group cannot give characters back, so there is one split to try. Same language, linear time.
Remove the ambiguity. (a+)+ and a+ accept the same strings; the nesting was never doing anything.
Bound the input before matching. A pattern that is safe on 30 characters is not safe on 3,000.

Walkthrough: the validator that took the service down

An email validator had shipped for three years. A pattern from a blog post, roughly ^([a-zA-Z0-9_\.\-])+\@(([a-zA-Z\-])+\.)+([a-zA-Z]{2,4})$.

One afternoon every request thread was busy and the pod stopped answering health checks. A thread dump showed forty threads inside Pattern$Curly.match, all on the same stack.

The input was a sign-up form field containing sixty a characters and no @. ([a-zA-Z0-9_\.\-])+ is a quantified group whose body is a single character — exactly the shape above — and without an @ the engine explored the splits until the request timed out, then the next one arrived.

The fix was three lines: a length limit of 254, a possessive quantifier, and eventually dropping the regex for a check of @ position and a DNS-safe domain test. The third was the one that made it boring.

Try it yourself

What does `split` do with the trailing empties?

java

"a,b,,,".split(",")          // length?
"a,b,,,".split(",", -1)      // length?
",,a".split(",")             // length?
"a.b.c".split(".")           // length?
"".split(",")                // length?

Answer

2, 5, 3, 0, 1.

With no limit argument, split removes trailing empty strings — a documented behaviour that quietly loses data when parsing CSV. A negative limit keeps every field. Leading empties are kept either way, which is why ",,a" gives three.

"a.b.c".split(".") gives zero, and it is the most common regex bug in Java. . is a metacharacter that matches every character, so every field is empty, every empty is trailing, and split drops them all. You wanted split("\\."), which gives 3.

"".split(",") gives one, not zero — an array holding the empty string. Code that checks split(...).length == 0 to mean "no input" never fires.

Why does this match nothing?

java

Pattern.compile("C:\new").matcher("C:\\new folder").find();

Answer

"C:\new" in Java source is C:, a newline, ew — the compiler consumed \n before the regex engine ever saw it. To match a literal backslash the source needs "C:\\\\new": two characters in the string, which the regex reads as one escaped backslash. Pattern.quote("C:\\new") avoids the counting entirely and is what to reach for with any literal.

Which of these is dangerous?

java

"^(\\w+\\s?)*$"        // 1
"^\\w+(\\s\\w+)*$"     // 2

Answer

(\w+\s?)* is a quantified group whose body can match without consuming the optional space, so the same characters can be divided between iterations in exponentially many ways — the (a+)+ shape wearing different clothes. On a long input with a trailing character that fails the anchor, it hangs. 2 is safe because each iteration must consume a space before the word, so there is only one way to divide the input.

When not to use one

A regex is the right tool for a pattern in flat text that you control or can bound. It is the wrong tool for:

Nested structure — HTML, JSON, source code. These are not regular languages; a regex cannot count brackets, and every attempt is a near-miss that fails on real input.
Parsing a format that has a parser. LocalDate.parse, URI.create, a CSV library and a JSON library all handle the cases your pattern will not.
Anything a String method already does. startsWith, contains, indexOf and split on a plain character are faster and say what they mean.

The test is whether a reader six months from now can say what the pattern accepts. If the answer needs a paragraph, the paragraph should be code.

Misconceptions

"matches() finds the pattern." It requires the whole input to match. find() searches.
"Compiling is cheap." It parses the pattern and builds a tree. String.matches does it on every call.
"Greedy means it matches more." It means it tries more first, then gives characters back. The final match may be shorter than you expect once the rest of the pattern is satisfied.
"Catastrophic backtracking needs a pathological pattern." ([a-z]+)+, (\w+\s?)* and the common email patterns all have the shape. It is ordinary-looking code.
"A timeout will save me." java.util.regex has none. You would need to run the match on another thread and abandon it, which does not stop it burning a core.

Going deeper

java.util.regex.Pattern's class javadoc — the full syntax reference, including the possessive quantifiers most tutorials never mention.
Russ Cox, Regular Expression Matching Can Be Simple And Fast — why RE2 and Go's regexp have no backtracking, and what they give up for it.
OWASP's entry on Regular Expression Denial of Service, for the same problem written as a security finding.

#Pattern and Matcher

#The pieces

#Greedy, reluctant, possessive

#Under the hood: backtracking, and when it explodes

#Walkthrough: the validator that took the service down

#Try it yourself

#What does split do with the trailing empties?

#Why does this match nothing?

#Which of these is dangerous?

#When not to use one

#Misconceptions

#Going deeper

`Pattern` and `Matcher`

The pieces

Greedy, reluctant, possessive

Under the hood: backtracking, and when it explodes

Walkthrough: the validator that took the service down

Try it yourself

What does `split` do with the trailing empties?

Why does this match nothing?

Which of these is dangerous?

When not to use one

Misconceptions

Going deeper