[YARR] Add auto-possession optimization

2a8223d

Source/JavaScriptCore/yarr/YarrPattern.cpp

Source/JavaScriptCore/yarr/YarrJIT.cpp

YARR (Yet Another Regex Runtime)는 WebKit의 regex 엔진입니다. 패턴을 parser에 통과시켜 YarrPattern IR(PatternTerm 노드로 구성)로 변환한 뒤, interpreter로 처리하거나 YarrJIT을 통해 native code로 컴파일합니다. Possessive quantifier는 최대한 매칭한 뒤, 이미 소모한 문자를 다음 term에 반환하지 않습니다. Greedy quantifier가 backtrack 시 문자를 반환하는 것과 대조됩니다. Auto-possessification은 greedy quantifier를 possessive로 취급해도 된다는 사실을 정적으로 증명하는 분석입니다. Greedy term이 매칭 가능한 문자 집합과 뒤따르는 필수 term이 요구하는 문자 집합이 완전히 disjoint하다면, 모든 backtrack 반복은 어차피 실패합니다. 따라서 give-back loop 자체를 생략할 수 있습니다.

이번 commit은 optimizePossessiveQuantifiers 분석 패스와 대응하는 JIT code path를 추가했습니다. 분석 패스는 컴파일된 PatternTerm을 순회하며, 뒤따르는 필수 term의 문자 집합이 disjoint함이 증명 가능한 경우 greedy 단일 문자 term을 possessive로 표시합니다. 뒤따르는 term에 /i 플래그가 적용된 경우에는 case folding도 함께 고려합니다. 이후 YarrJIT은 해당 term에 대해 backtrack loop를 건너뛰는 코드를 생성하여, /a+b/나 /[0-9a-f]{1,4}:/ 같은 패턴에서 불필요한 give-back 반복을 제거합니다.

Significance

Disjointness 분석의 정확성은 구현 전체를 떠받치는 핵심입니다. 두 문자 집합이 단 하나의 code point만 공유하더라도 disjoint하다고 잘못 판단하는 false positive가 발생하면, JIT은 backtracking을 조용히 건너뛰고 잘못된 non-match를 반환합니다. 이는 regex 기반 security validator를 무력화하는 버그 유형에 정확히 해당합니다.

분석은 Unicode case folding, non-BMP surrogate pair, inverted/variable-width character class를 정확하게 처리해야 합니다. 모두 미묘한 부분이며 세심하게 살펴볼 필요가 있습니다.

Audit directions