Possessive Quantifier — *+ ++ ?+

이 quantifier 의 backtracking 비활성화

Possessive quantifier — *+, ++, ?+, {n,m}+ 로 작성 — greedy 처럼 매칭, 하지만 한 번 소비하면 돌려주길 거부. 이 quantifier 통한 backtracking 없음.

제한적으로 들리지만, 빠르고 ReDoS-safe 패턴 작성 비결. Backtracking 이 적대적 입력에 정규식 느려지게 하는 것. backtracking 도움 안 되는 자리에서 비활성화하면 엔진이 날아.

성능 win

패턴 a+b 입력 aaaaaaa: greedy a+ 가 a 7개 다 잡음, b 매칭 못 함, 한 a 씩 backtrack (7번 시도) 후 실패. Possessive a++b: a 7개 다 잡음, b 매칭 못 함, backtrack 거부, 즉시 실패. 같은 결과, 훨씬 적은 일.

ReDoS 보호 (트랙 8) 에 이게 전부. (a+)+b 같은 패턴은 지수적 — a+ 가 외부 + 로 backtrack 가능하니까. Possessive 로 — (a++)+b — 만들면 linear.

Flavor 지원

Possessive quantifier 는 PCRE, Java, Ruby (1.9+), .NET (5+) 에 존재. Python re 는 없음 (추가하는 regex 모듈 사용) 또는 JavaScript 에 없음. RE2 는 backtrack 자체 안 해서 필요 없음.

엔진이 possessive 미지원이면 등가는 atomic group (?>...), 트랙 8 에서.

Code

Possessive quantifier (PCRE/Java/Ruby)·text

# Java 에서
Pattern.matches("a++b", "aaaaaaa")  // false, backtracking 시도 없음

# PHP/PCRE 에서
preg_match('/a++b/', 'aaaaaaa')  // 0

# Python 에서 (third-party 'regex' 라이브러리 필요, 내장 're' 아님)
import regex
regex.findall(r'a++b', 'aaaaaaa')  # []  — 빠르게 실패

# Atomic group 등가 — Python re 에서도 동작
import re
re.findall(r'(?>a+)b', 'aaaaaaa')  # re 가 atomic group 지원하면

# 큰 입력에서 성능 차이 보임
# 'a' * 30 + 'X'  — 적대적 입력
# (a+)+ → 지수 시간, 분 단위로 멈출 수 있음
# (a++)+ → linear 시간, 즉시 실패

Possessive Quantifier — *+ ++ ?+

이 quantifier 의 backtracking 비활성화

성능 win

Flavor 지원

Code

External links

Exercise

Progress

댓글 0