Regex series: 1. Syntax, the Java API and validation exercises · 2. Exercises: network configs, logs to CSV, lookbehind, duplicate lines · 3. The engine, backtracking and catastrophic backtracking · 4. ReDoS in Java: outages and defences
Four regex problems close to real backend work: pull fields out of a multi-line config, turn logs into CSV, extract exactly one number when another with the same format sits next to it, and handle duplicate lines. The last one also teaches a skill that matters just as much: recognising when regex is the wrong tool. You’ll want the syntax from part 1 first (named groups, lookaround, backreferences, the MULTILINE and DOTALL flags); patterns at risk of running slowly are analysed in part 3.
At a glance:
flowchart TD
A["Cases that must match"] --> C["Try regex101, right flavor"]
B["Near misses must not"] --> C
C --> D["Lock in unit tests"]
D --> E{"Compare across lines?"}
E -->|"No"| F["Per-line regex, anchored"]
E -->|"Yes"| G["HashSet, awk, sort uniq"]
How I check a regex before using it
Key idea: write cases that must match and near-miss cases that must not, try them on regex101 in the right flavor, pin them with a unit test, then ask how big the input is.
- Sample input in two groups: the “almost the same but must not match” group is where bugs get caught:
U109next toU1092,1234A56next to1234.56, “citizen id” next to “passport no”. - regex101 in the right flavor (flavor = each engine’s syntax variant): Java 8 for Java code, PCRE2 for Nginx, POSIX ERE for
grep -Eandsed -E. The “Regex Debugger” tab shows how many steps the engine took. - A unit test, so whoever edits the pattern later immediately sees which case they broke:
@ParameterizedTest
@CsvSource({
"Passport Number: 31193421, 31193421",
"passport no: 12183421, 12183421",
"citizen id: 67192342, ''"
})
void extractsOnlyPassportNumbers(String line, String expected) {
assertThat(PassportParser.extract(line).orElse("")).isEqualTo(expected);
}
- Input size: a 100-character line or a 2 GB file? If the input comes from outside, read part 3 and part 4 before shipping it.
The test above uses JUnit 5 and AssertJ and wasn’t run for this post; PassportParser is solution 2 of the challenge, wrapped in a method that returns an Optional. Every other solution was run on JDK 21 (one Exercises.java file, run with java Exercises.java); the output sits right under each snippet.
Exercises
Exercise 1: Parse a network configuration
The input is a switch configuration: each block starts with interface <name>, then status on|off, one ip address <ip> <mask> line, and optionally an ip address secondary <ip> <mask> line. For each interface, print interface, status, ip00 (the primary IP) and ip01 (the secondary IP, or null if there isn’t one).
static final Pattern IFACE = Pattern.compile("""
^interface\\h+(?<iface>\\S+)\\R\
status\\h+(?<status>on|off)\\R\
ip\\h+address\\h+(?<ip00>[\\d.]+\\h+[\\d.]+)\
(?:\\Rip\\h+address\\h+secondary\\h+(?<ip01>[\\d.]+\\h+[\\d.]+))?""",
Pattern.MULTILINE);
Matcher m = IFACE.matcher(config);
int i = 1;
while (m.find()) {
System.out.printf("Match %d: interface=%s status=%s ip00=%s ip01=%s%n",
i++, m.group("iface"), m.group("status"), m.group("ip00"), m.group("ip01"));
}
// Match 1: interface=Gi1/0/1 status=on ip00=1.1.1.1 255.255.255.0 ip01=2.2.2.2 255.255.255.0
// Match 2: interface=Gi1/0/2 status=off ip00=3.3.3.3 255.255.255.0 ip01=null
- One named group per field: read
m.group("ip01")instead of counting parentheses. - The secondary IP line sits inside
(?:...)?; when it’s absent,group("ip01")returnsnull, exactly the required output. \h(horizontal whitespace) instead of\s, so the pattern can’t swallow a line break;\Rmatches both\nand the\r\nof a file saved on Windows.
Exercise 1 details: text blocks, matching IPv4, when to drop the big pattern
- A
\at the end of a line in a text block joins lines without inserting\n, so the pattern is still a single line. [\d.]+is a crude IPv4 match: it accepts999.1.1.1. For real validation, parse withInetAddressafter extracting.- When the config has more line types, or the line order can vary, one giant pattern will break. At that point, split the input into blocks on
^interface, parse each line with small patterns, or write a proper parser.
Case study: turning logs into CSV
The input is an application log with two kinds of lines:
2023-09-12T13:23:48.796+07:00 INFO 49211 Application: User U123 claimed voucher V34
2023-09-12T13:23:49.796+07:00 INFO 99211 Application: User U56 logged in
Requirement: keep only the voucher-claim lines and output CSV as timestamp, userId, voucherId, e.g. 2023-09-12T13:23:48.796+07:00, U56, V12. The slides suggest doing it right in VS Code; there are three ways depending on context: the editor for a one-off, Java for a recurring job, sed/awk when you’re SSH’d into a server.
Java, when this becomes a recurring job:
static final Pattern VOUCHER = Pattern.compile(
"^(\\S+)\\s+INFO\\s+\\d+\\s+Application: User (U\\d+) claimed voucher (V\\d+)$",
Pattern.MULTILINE);
String csv = VOUCHER.matcher(log).results()
.map(r -> r.group(1) + ", " + r.group(2) + ", " + r.group(3))
.collect(Collectors.joining("\n"));
The output is exactly the five voucher-claim lines (U123, U78, U56, U11, U12). For large files, read line by line with Files.lines(path) and matcher(line).matches() instead of loading the whole file into one String.
Doing it with VS Code find/replace, and with sed and awk
VS Code find/replace (turn on the .* button for regex mode):
- Find
^(\S+)\s+INFO\s+\d+\s+Application: User (U\d+) claimed voucher (V\d+)$, replace with$1, $2, $3, Replace All. The voucher lines are now CSV. - Find
^.*Application: .*\n, replace with nothing. The remaining (login) lines disappear, because the CSV lines no longer contain “Application:”.
Step 2 relies on the transformed lines looking different from the originals. A more general approach is to delete lines that don’t contain “claimed voucher” first, with a negative lookahead ^(?!.*claimed voucher).*\n, and only then run the replace.
The command line, when you’re SSH’d into a server:
sed -nE 's/^([^ ]+) +INFO +[0-9]+ +Application: User (U[0-9]+) claimed voucher (V[0-9]+)$/\1, \2, \3/p' app.log
awk '/claimed voucher/ {print $1 ", " $6 ", " $9}' app.log
sed -n with the p flag prints only the lines where the substitution happened. POSIX ERE has no \d or \S, so you write [0-9] and [^ ]. The awk version needs no complex regex at all, because the log is already whitespace-separated.
Challenge: extract only passport numbers
Anton Chigurh, a serial killer, Passport Number: 31193421, Citizen Id: 87693455
Patrick Bateman, a psychopath, citizen id: 67192342, passport no: 12183421
Passport numbers and citizen ids share the same 8-digit format, so \d{8} can’t tell them apart. The label in front of the number is what distinguishes them, and it comes in two spellings (Passport Number, passport no) with mixed case. The slide’s hint is “an operation we haven’t covered yet”: lookaround.
Solution 1: lookbehind, so the match is just the number:
static final Pattern PASSPORT = Pattern.compile(
"(?<=passport (?:number|no): )\\d{8}", Pattern.CASE_INSENSITIVE);
// [31193421, 12183421]
This is legal in Java because both branches, number and no, have finite length, so the maximum length is known.
A lookbehind that tolerates extra whitespace on JDK 21
If you need to tolerate extra whitespace, write \s{1,3}, not \s*: on JDK 21, a lookbehind with two \s* compiles but never matches; see part 1, section 2.6.
Solution 2: a capturing group, which works in every flavor and tolerates any amount of whitespace:
static final Pattern PASSPORT = Pattern.compile("(?i)passport\\s+(?:number|no)\\s*:\\s*(\\d{8})");
PASSPORT.matcher(text).results().map(r -> r.group(1)).toList(); // [31193421, 12183421]
In Java code I pick solution 2: no lookbehind restrictions, and easier to read. Lookbehind earns its place when the tool only returns the whole match, not groups (some editor search boxes, grep -oP, rules in some log systems).
Homework: duplicate lines
A list of user ids, one per line: U123 U234 U452 U341 U123 U789 U1092 U109 U2342 U1092 U603 U745. Do three things: find duplicate lines, remove duplicates (keeping one copy), and remove duplicates together with the original.
Find duplicates. A line is a duplicate if an identical line appears later:
Pattern dup = Pattern.compile("(?m)^(.+)$(?=[\\s\\S]*^\\1$)");
// [U123, U1092]
[\s\S]* skips over anything including newlines; ^\1$ demands a line that is entirely equal to the captured one.
Solutions: removing duplicates with regex (keep the last, keep the first, drop the original too)
Remove duplicates, keeping one copy. Deleting every line that has a copy further down takes a single Replace All, but it keeps the last copy:
users.replaceAll("(?m)^(.+)\\R(?=[\\s\\S]*^\\1$)", "");
// U234 U452 U341 U123 U789 U109 U2342 U1092 U603 U745
To keep the first copy (preserving the original order), the regex has to delete the later copies. Java doesn’t allow an unbounded lookbehind, so repeat replaceFirst until nothing changes:
Pattern later = Pattern.compile("(?m)^(.+)$([\\s\\S]*?)\\R\\1$");
String s = users, prev;
do { prev = s; s = later.matcher(s).replaceFirst("$1$2"); } while (!s.equals(prev));
// U123 U234 U452 U341 U789 U1092 U109 U2342 U603 U745
Remove duplicates and the original, i.e. keep only lines that appear exactly once:
Pattern both = Pattern.compile("(?m)^(.+)\\R((?:[\\s\\S]*?\\R)?)\\1(?:\\R|$)");
String t = users, p;
do { p = t; t = both.matcher(t).replaceFirst("$2"); } while (!t.equals(p));
// U234 U452 U341 U789 U109 U2342 U603 U745
The pattern captures a (first copy, later copy) pair and keeps only the text between them. It’s correct for this data, where each id appears at most twice; with an id appearing three or more times, the third copy survives and needs another pass.
The right tool for this job. The regex solutions are finger exercises. Each [\s\S]* lookahead rescans the rest of the input, so the cost is at least O(n²) in the number of lines, before even counting the replaceFirst loop; a file with a few hundred thousand lines will take a very long time. Data structures do it in O(n):
List<String> lines = users.lines().toList();
new LinkedHashSet<>(lines); // dedupe, keep the first copy and the order
Map<String, Long> count = lines.stream()
.collect(Collectors.groupingBy(x -> x, LinkedHashMap::new, Collectors.counting()));
count.entrySet().stream().filter(e -> e.getValue() > 1).map(Map.Entry::getKey).toList(); // [U123, U1092]
count.entrySet().stream().filter(e -> e.getValue() == 1).map(Map.Entry::getKey).toList(); // only the non-duplicated lines
awk '!seen[$0]++' users.txt # dedupe, keep first copy and order, O(n)
sort users.txt | uniq -d # list duplicated lines
sort users.txt | uniq -u # lines that occur exactly once (order lost)
awk 'NR==FNR{c[$0]++; next} c[$0]==1' users.txt users.txt # same, keeping the order
sort is O(n log n) but works even when the file is bigger than RAM (it sorts externally); awk and LinkedHashSet must keep every distinct line in memory.
For more practice: the Quiz section on regex101, where each quiz comes with test cases that must and must not match.
Remember
- Write a test set for a regex, including “almost the same but must not match” cases.
- Explain why an absent optional group returns
null, and how that differs from a group that matched zero characters. - Know when to use lookbehind versus a capturing group, and Java’s lookbehind limit.
- Explain why
\1needs^...$when finding duplicate lines. - Know when to drop regex for
LinkedHashSet,awk,sort | uniq, a parser or structured logging.
Interview questions
Junior
How do you remove duplicate lines in Java while keeping the original order?
Put the lines into a LinkedHashSet, or use lines.stream().distinct().toList().
The hash part dedupes in O(1) per element and the linked part keeps insertion order, so the first copy of each line survives. distinct() also keeps encounter order. On the command line: awk '!seen[$0]++' file.
Why use [0-9] with sed -E instead of \d?
Because sed and grep use POSIX regex, which has no Perl-style shorthands like \d, \S, and no lookaround.
POSIX ERE (-E) has +, ?, |, {n,m} and unescaped groups. Write [0-9], [^ ], or POSIX classes such as [[:digit:]] and [[:space:]]. GNU grep -P accepts PCRE syntax, but it isn’t available in macOS’s grep.
Mid
What goes wrong when you use an unanchored \1 to find duplicate lines?
\1 re-matches the captured substring anywhere, so a line contained inside another line counts as a duplicate.
With (?m)^(.+)$(?=[\s\S]*\1), U109 counts as a duplicate because it appears inside U1092, and U234 because of U2342. Anchor the whole line: (?=[\s\S]*^\1$) with MULTILINE. The general lesson: regex tests always need “almost the same but must not match” cases.
A multi-line block has an optional part. How do you write the pattern and read the result?
Put the optional part in (?:...)? with named groups inside, and handle group(name) returning null when it’s absent.
Use \R for line breaks (it copes with \r\n) and \h for horizontal whitespace, so the pattern can’t run into the next line. Wrap the result in an Optional. If the line order can change, split the input into blocks first (on the opening line) and parse each line with a small pattern, rather than one big pattern.
Senior
When would you not use regex even though it could work?
When comparing lines with each other, when the format is nested, when a purpose-built library exists, and when you can change the producer of the data.
- Comparing lines (duplicates, counts): data structures do it in O(n); regex is O(n²) and hard to read.
- Nested formats like JSON, HTML, XML, SQL: regex can’t parse nested languages, so use a parser.
- A library exists:
InetAddressfor IPs,LocalDate.parsefor dates,URIfor URLs,BigDecimalorNumberFormatfor numbers. - You can change the producer: structured logging instead of regex over log messages.
The team’s log-extraction regex suddenly returns zero results after a deploy. How do you investigate and prevent it?
First suspect a change in the message format; prevent it by treating the log format as a contract with tests and alerts.
- Investigate: the format can change through reworded text, an extra field, a new logback pattern, a timestamp in a different locale. Compare a fresh log line with the pattern on regex101 (in the right flavor) to find the mismatch.
- Prevent: a unit test that produces a log line through the real logging code and runs the pattern on it; structured logging with an
eventfield; an alert when the match count drops to zero unexpectedly. - Business metrics: read them from the database or the event stream rather than the logs.
Useful phrases for interviews
- “Every positive example gets a near-miss example next to it; that’s how I catch false positives.”
- “The optional group didn’t participate in the match, so
group()returned null rather than an empty string.” - “A backreference matches a substring, so I anchor it to whole lines with
^\1$.” - “Java needs a bounded lookbehind, so I usually reach for a capturing group instead; it’s portable and easier to read.”
- “For a quick look on the server, an awk one-liner is enough; for a recurring job I’d write it in Java with a precompiled pattern.”
- “Each lookahead rescans the rest of the file, so the regex approach is quadratic; a
LinkedHashSetdoes it in linear time.” - “If the numbers matter to the business, I’d rather count events than parse log messages.”
- “Regex in the editor is fine for an ad hoc cleanup, not for something that runs every night.”
Notes based on the Advanced Backend course (Ronin Engineer), rewritten in my own words.