Cụm bài Regex: 1. Cú pháp, Java API và bài tập validate · 2. Bài tập: cấu hình mạng, log sang CSV, lookbehind, dòng trùng · 3. Engine, backtracking và catastrophic backtracking · 4. ReDoS trong Java: sự cố và phòng thủ
Bốn bài regex sát việc backend thật: tách field từ cấu hình nhiều dòng, biến log thành CSV, lấy đúng một con số giữa các số cùng định dạng, và xử lý dòng trùng. Bài cuối còn dạy một kỹ năng quan trọng không kém: nhận ra lúc regex là công cụ sai. Cần nắm cú pháp ở bài 1 trước (named group, lookaround, backreference, cờ MULTILINE, DOTALL); pattern có nguy cơ chạy chậm được phân tích ở bài 3.
Sơ đồ tóm tắt:
flowchart TD
A["Case phải khớp"] --> C["Thử regex101 đúng flavor"]
B["Case gần giống không khớp"] --> C
C --> D["Khoá bằng unit test"]
D --> E{"So giữa các dòng?"}
E -->|"Không"| F["Regex từng dòng, có neo"]
E -->|"Có"| G["HashSet, awk, sort uniq"]
Cách mình kiểm một regex trước khi dùng
Ý chính: viết case phải khớp và case gần giống không được khớp, thử trên regex101 đúng flavor, khoá bằng unit test, rồi hỏi input lớn cỡ nào.
- Input mẫu hai nhóm: nhóm “gần giống nhưng không được khớp” mới là nơi bắt lỗi:
U109cạnhU1092,1234A56cạnh1234.56, “citizen id” cạnh “passport no”. - regex101 với đúng flavor (flavor = biến thể cú pháp của từng engine): Java 8 cho code Java, PCRE2 cho Nginx, POSIX ERE cho
grep -E,sed -E. Tab “Regex Debugger” cho thấy engine đã thử bao nhiêu bước. - Unit test để người sửa pattern sau biết ngay mình làm hỏng case nào:
@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);
}
- Kích thước input: một dòng 100 ký tự hay cả file 2 GB? Input do người ngoài gửi tới thì đọc bài 3 và bài 4 trước khi lên production.
Test trên dùng JUnit 5 và AssertJ, không chạy trong bài; PassportParser là lời giải 2 của bài thử thách, bọc trong method trả Optional. Mọi lời giải khác đã chạy trên JDK 21 (một file Exercises.java, chạy bằng java Exercises.java), output ghi ngay dưới code.
Bài tập
Bài 1: Tách cấu hình mạng
Input là cấu hình switch: mỗi block bắt đầu bằng interface <tên>, rồi status on|off, một dòng ip address <ip> <mask>, và có thể có ip address secondary <ip> <mask>. Với mỗi interface, in interface, status, ip00 (IP chính), ip01 (IP phụ, null nếu không có).
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
- Named group cho mỗi field: đọc
m.group("ip01")thay vì đếm ngoặc. - Dòng IP phụ nằm trong
(?:...)?; vắng thìgroup("ip01")trảnull, đúng output yêu cầu. \h(khoảng trắng ngang) thay\sđể không nuốt xuống dòng;\Rkhớp cả\nlẫn\r\ncủa file lưu từ Windows.
Chi tiết bài 1: text block, khớp IPv4, khi nào bỏ pattern lớn
\ở cuối dòng trong text block nối dòng mà không chèn\n, nên pattern vẫn là một dòng.[\d.]+là cách khớp IPv4 thô: nó nhận cả999.1.1.1. Muốn kiểm tra thật thì parse bằngInetAddresssau khi tách.- Khi cấu hình có nhiều loại dòng hơn hoặc thứ tự dòng thay đổi, một pattern khổng lồ sẽ vỡ. Lúc đó tách block theo
^interface, parse từng dòng bằng pattern nhỏ, hoặc viết parser riêng.
Case study: chuyển log thành CSV
Input là log ứng dụng, gồm hai loại dòng:
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
Yêu cầu: chỉ lấy dòng nhận voucher, xuất CSV timestamp, userId, voucherId, ví dụ 2023-09-12T13:23:48.796+07:00, U56, V12. Slide gợi ý làm ngay trong VS Code; có ba cách tuỳ hoàn cảnh: editor cho việc một lần, Java cho job định kỳ, sed/awk khi đang SSH vào server.
Java, khi việc này thành job chạy định kỳ:
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"));
Output đúng năm dòng nhận voucher (U123, U78, U56, U11, U12). File lớn thì đọc từng dòng bằng Files.lines(path) và matcher(line).matches(), đừng nạp cả file thành một String.
Cách làm trong VS Code find/replace và bằng sed, awk
VS Code find/replace (bật nút .* để dùng regex):
- Find
^(\S+)\s+INFO\s+\d+\s+Application: User (U\d+) claimed voucher (V\d+)$, Replace$1, $2, $3, bấm Replace All. Các dòng voucher đã thành CSV. - Find
^.*Application: .*\n, Replace để trống. Các dòng còn lại (login) bị xoá, vì dòng CSV không còn chữ “Application:”.
Bước 2 lợi dụng việc dòng đã biến đổi trông khác dòng gốc. Cách tổng quát hơn: xoá trước những dòng không chứa “claimed voucher” bằng negative lookahead ^(?!.*claimed voucher).*\n, rồi mới replace.
Dòng lệnh, khi đang SSH vào 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 kèm cờ p chỉ in những dòng thay được. POSIX ERE không có \d hay \S, nên phải viết [0-9] và [^ ]. Bản awk không cần regex phức tạp vì log đã tách bằng khoảng trắng.
Thử thách: chỉ lấy số hộ chiếu
Anton Chigurh, a serial killer, Passport Number: 31193421, Citizen Id: 87693455
Patrick Bateman, a psychopath, citizen id: 67192342, passport no: 12183421
Số hộ chiếu và số căn cước cùng 8 chữ số, nên \d{8} không phân biệt được. Thứ phân biệt là nhãn đứng trước, có hai cách viết (Passport Number, passport no), hoa thường lẫn lộn. Gợi ý của slide là “một phép chưa học”: lookaround (kiểm tra xung quanh vị trí mà không đưa vào match).
Lời giải 1: lookbehind, match chỉ gồm con số:
static final Pattern PASSPORT = Pattern.compile(
"(?<=passport (?:number|no): )\\d{8}", Pattern.CASE_INSENSITIVE);
// [31193421, 12183421]
Hợp lệ trong Java vì hai nhánh number, no có độ dài hữu hạn, nên độ dài tối đa xác định được.
Lookbehind chịu nhiều khoảng trắng trên JDK 21
Cần chịu nhiều khoảng trắng thì viết \s{1,3}, đừng viết \s*: trên JDK 21, lookbehind có hai \s* compile được nhưng không bao giờ khớp; xem bài 1, mục 2.6.
Lời giải 2: capturing group, chạy ở mọi flavor và chịu khoảng trắng tuỳ ý:
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]
Trong code Java mình chọn lời giải 2: không vướng giới hạn lookbehind, dễ đọc hơn. Lookbehind có ích khi công cụ chỉ trả toàn bộ match, không trả group (vài ô tìm kiếm của editor, grep -oP, rule của vài hệ thống log).
Bài tập về nhà: dòng trùng
Danh sách user id, mỗi dòng một id: U123 U234 U452 U341 U123 U789 U1092 U109 U2342 U1092 U603 U745. Làm ba việc: tìm dòng trùng, xoá dòng trùng (giữ một bản), xoá dòng trùng và cả bản gốc.
Tìm dòng trùng. Một dòng là trùng nếu phía sau còn một dòng y hệt:
Pattern dup = Pattern.compile("(?m)^(.+)$(?=[\\s\\S]*^\\1$)");
// [U123, U1092]
[\s\S]* nhảy qua mọi thứ kể cả xuống dòng; ^\1$ đòi một dòng giống trọn vẹn dòng đã bắt.
Lời giải: xoá dòng trùng bằng regex (giữ bản cuối, giữ bản đầu, xoá cả bản gốc)
Xoá dòng trùng, giữ một bản. Xoá mọi dòng mà phía sau còn bản sao, chỉ cần một lần Replace All, nhưng kết quả giữ bản cuối:
users.replaceAll("(?m)^(.+)\\R(?=[\\s\\S]*^\\1$)", "");
// U234 U452 U341 U123 U789 U109 U2342 U1092 U603 U745
Muốn giữ bản đầu (giữ thứ tự xuất hiện), regex phải xoá các bản phía sau. Java không cho lookbehind dài tuỳ ý, nên lặp replaceFirst tới khi không còn gì đổi:
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
Xoá dòng trùng và cả bản gốc, tức chỉ giữ dòng xuất hiện đúng một lần:
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
Pattern bắt cặp (bản đầu, bản sau) và chỉ giữ đoạn giữa hai bản. Nó đúng với dữ liệu này, nơi mỗi id xuất hiện tối đa hai lần; id xuất hiện ba lần trở lên thì bản thứ ba còn sót, cần thêm một vòng xử lý.
Công cụ đúng cho việc này. Các lời giải regex là bài luyện tay. Mỗi lookahead [\s\S]* quét phần còn lại của input, nên chi phí ít nhất O(n²) theo số dòng, chưa kể vòng lặp replaceFirst; file vài trăm nghìn dòng sẽ chạy rất lâu. Cấu trúc dữ liệu làm trong O(n):
List<String> lines = users.lines().toList();
new LinkedHashSet<>(lines); // bỏ trùng, giữ bản đầu và thứ tự
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(); // chỉ các dòng không trùng
awk '!seen[$0]++' users.txt # bỏ trùng, giữ bản đầu, giữ thứ tự, O(n)
sort users.txt | uniq -d # liệt kê dòng trùng
sort users.txt | uniq -u # chỉ dòng xuất hiện đúng 1 lần (mất thứ tự)
awk 'NR==FNR{c[$0]++; next} c[$0]==1' users.txt users.txt # như trên nhưng giữ thứ tự
sort là O(n log n) nhưng chạy được cả khi file lớn hơn RAM (nó sort ngoài bộ nhớ); awk và LinkedHashSet phải giữ mọi dòng khác nhau trong bộ nhớ.
Luyện thêm: mục Quiz trên regex101, mỗi câu cho sẵn test case phải khớp và không được khớp.
Ghi nhớ
- Viết được bộ test cho một regex, có cả case “gần giống nhưng không được khớp”.
- Giải thích được vì sao nhóm tuỳ chọn vắng trả
null, và khác gì với nhóm khớp 0 ký tự. - Biết khi nào dùng lookbehind, khi nào dùng capturing group, và giới hạn lookbehind của Java.
- Giải thích được vì sao
\1cần^...$khi tìm dòng trùng. - Biết khi nào bỏ regex để dùng
LinkedHashSet,awk,sort | uniq, parser hay structured logging.
Câu hỏi phỏng vấn
Junior
Làm sao bỏ dòng trùng mà vẫn giữ thứ tự xuất hiện trong Java?
Đưa các dòng vào LinkedHashSet, hoặc dùng lines.stream().distinct().toList().
Phần hash bỏ trùng trong O(1) mỗi phần tử, phần “linked” giữ thứ tự chèn, nên bản đầu tiên của mỗi dòng được giữ. distinct() cũng giữ thứ tự gặp đầu tiên. Trên dòng lệnh: awk '!seen[$0]++' file.
Vì sao phải dùng sed -E với [0-9] thay vì \d?
Vì sed và grep dùng POSIX regex, không có các shorthand kiểu Perl như \d, \S hay lookaround.
POSIX ERE (-E) có +, ?, |, {n,m} và nhóm không cần escape. Viết [0-9], [^ ], hoặc lớp POSIX [[:digit:]], [[:space:]]. grep -P (GNU) dùng được cú pháp PCRE nhưng không có trên grep của macOS.
Mid
Backreference \1 không có anchor gây ra lỗi gì khi tìm dòng trùng?
\1 khớp lại chuỗi con đã bắt ở bất kỳ đâu, nên dòng nằm bên trong dòng khác bị coi là trùng.
Với (?m)^(.+)$(?=[\s\S]*\1), U109 bị coi là trùng vì nằm trong U1092, và U234 vì nằm trong U2342. Phải neo cả dòng: (?=[\s\S]*^\1$) với MULTILINE. Bài học chung: test regex luôn cần case “gần giống nhưng không được khớp”.
Một block nhiều dòng có phần tuỳ chọn. Bạn viết pattern và đọc kết quả thế nào?
Đặt phần tuỳ chọn trong (?:...)? với named group bên trong, và xử lý group(name) trả null khi phần đó vắng.
Dùng \R cho xuống dòng (chịu được \r\n) và \h cho khoảng trắng ngang, để pattern không nuốt sang dòng sau. Bọc kết quả bằng Optional. Nếu thứ tự dòng có thể đổi, tách block trước (theo dòng mở đầu) rồi parse từng dòng bằng pattern nhỏ, thay vì một pattern lớn.
Senior
Khi nào bạn không dùng regex dù dùng được?
Khi so sánh giữa các dòng, khi định dạng lồng nhau, khi đã có thư viện chuyên dụng, và khi sửa được phía tạo dữ liệu.
- So giữa các dòng (trùng, đếm): cấu trúc dữ liệu làm trong O(n), regex là O(n²) và khó đọc.
- Định dạng lồng nhau như JSON, HTML, XML, SQL: regex không parse được ngôn ngữ lồng nhau, dùng parser.
- Có thư viện:
InetAddresscho IP,LocalDate.parsecho ngày,URIcho URL,BigDecimalhayNumberFormatcho số. - Đổi được phía tạo dữ liệu: structured logging thay cho regex trên message log.
Regex trích xuất log của team bỗng ra 0 kết quả sau một lần deploy. Bạn điều tra và phòng ngừa thế nào?
Nghi đầu tiên là định dạng message đã đổi; phòng ngừa bằng cách coi định dạng log là một hợp đồng có test và alert.
- Điều tra: định dạng có thể đổi do sửa câu chữ, thêm field, đổi pattern của logback, đổi locale của timestamp. So một dòng log mới với pattern trên regex101 (đúng flavor) để tìm phần lệch.
- Phòng ngừa: unit test dựng dòng log từ chính code logging và chạy pattern lên nó; structured logging với field
event; alert khi số match giảm về 0 bất thường. - Số liệu nghiệp vụ: lấy từ database hay event stream thay vì từ log.
Từ vựng tiếng Anh
| Term | Phát âm | Nghĩa | Ví dụ câu tiếng Anh dùng trong phỏng vấn |
|---|---|---|---|
| named group | /neɪmd ɡruːp/ | nhóm có tên | “Named groups let the code read the field by name instead of counting parentheses.” |
| optional group | /ˈɒpʃənl ɡruːp/ | nhóm tuỳ chọn | “When the optional group doesn’t participate, group() returns null.” |
| backreference | /ˈbækˌrefrəns/ | tham chiếu lại nhóm | “The backreference needs line anchors, otherwise U109 matches inside U1092.” |
| lookbehind | /ˈlʊkbɪhaɪnd/ | kiểm tra phía trước vị trí | “Java only accepts a lookbehind with a bounded maximum length.” |
| false positive | /fɔːls ˈpɒzətɪv/ | khớp nhầm | “Near-miss test cases are how you catch false positives.” |
| near-miss case | /ˈnɪə mɪs keɪs/ | case gần giống nhưng không được khớp | “I always add a near-miss case next to every positive example.” |
| structured logging | /ˈstrʌktʃərd ˈlɒɡɪŋ/ | ghi log có cấu trúc | “With structured logging, the query filters on a field instead of parsing the message.” |
| one-liner | /ˌwʌn ˈlaɪnər/ | lệnh một dòng | “For a quick look on the server, an awk one-liner is enough.” |
| deduplicate | /diːˈdjuːplɪkeɪt/ | bỏ trùng | “LinkedHashSet deduplicates while keeping the original order.” |
| quadratic | /kwɒˈdrætɪk/ | bậc hai, O(n²) | “Each lookahead rescans the rest of the file, so the regex approach is quadratic.” |
| ad hoc | /ˌæd ˈhɒk/ | làm một lần, tuỳ tình huống | “Regex in the editor is fine for an ad hoc cleanup, not for a recurring job.” |
Ghi chép dựa trên khoá Advanced Backend (Ronin Engineer), viết lại theo cách hiểu của mình.