[JSC] Implement Variable Count Parentheses in YarrJIT

6646c49

// JSTests/stress/regexp-greedy-nested-quantifier-backtrack.js
test(/((a+){2,3}){2,3}$/, "aaaaaa", "aaaaaa");
test(/((a+){2,4}){2,3}$/, "aaaaaa", "aaaaaa");
test(/(((a+){2}){2}){1,2}$/, "aaaa", "aaaa");
test(/((a+){2,3}){2,3}$/, "aaa", null);  // must correctly fail

YarrJIT는 ECMAScript 정규 표현식을 native machine code로 직접 컴파일합니다. backtracking 중 capture group 상태를 저장하고 복원하기 위해 ParenContext 객체를 사용합니다. 이전에는 최솟값이 0이 아닌 variable-count 그룹(예: {3,5})이 포함된 경우 JIT 컴파일이 실패하여, 조용히 느린 interpreter로 실행이 전환되었습니다.

이 commit은 m > 0인 {m,n} 괄호 quantifier를 JIT로 컴파일할 수 있도록 YarrJIT를 확장했습니다. 새로 도입된 count 강제 backtracking 경로는 다음과 같이 동작합니다. backtracking 중 반복 횟수가 최솟값 미만으로 떨어지면, 즉시 실패하는 대신 End.contentBacktrackEntryLabel을 통해 최근 iteration의 내용으로 재진입하여 대안 분기를 시도합니다. zero-length match가 발생하면 interpreter로 처리를 위임합니다. 한편 YarrInterpreter.cpp에도 동일한 correctness fix가 병행 적용되었습니다.

Significance

복잡한 backtracking state machine에 대해 안전한 interpreter fallback을 대신하는 새 JIT native code가 도입되었습니다. regex engine에서 correctness 버그, 나아가 memory safety 문제가 발견된 사례가 역사적으로 많은 영역인 만큼, 주의 깊은 검토가 필요합니다.

Audit directions

• count < min → contentBacktrackEntry is a new invariant enforced only by JIT-emitted branch logic. count register의 off-by-one 오류, 또는 count < min 상태에서 End.reentry(accept-fewer)에 도달하는 경로가 있으면, 패턴이 요구하는 것보다 적은 반복 횟수로 매칭이 성공하게 됩니다. 이는 regex 기반 allow/deny 필터를 조용히 우회하는 결과로 이어질 수 있습니다.
• ParenContext save/restore across the content-backtrack path. 엔진이 이전 iteration의 내용으로 되감길 때, capture group slot index는 올바른 save frame을 참조해야 합니다. stale frame pointer나 JIT register 할당에서의 잘못된 frame index가 있으면, 오류 없이 잘못된 $1..$N 값이 반환됩니다.
• Zero-length match detection. 하나의 iteration이 zero character와 매칭될 때 JIT는 interpreter로 처리를 위임하지만, 이 handoff 과정에서 count와 capture 상태가 정확하게 전달되어야 합니다. 불일치가 발생하면 divergence 버그로 이어집니다.
• Nested quantifiers ((((a+){2,3}){2,3})) 각 계층은 독립적인 ParenContext와 count register를 갖습니다. register 할당 중 계층 간 값이 덮어써지는 것은 조용한 mismatch 버그의 전형적인 원인이며, 다른 엔진에서는 type confusion으로 이어진 사례도 있습니다.
• Parallel YarrInterpreter.cpp fix to backtrackParentheses 동일한 논리적 오류가 두 엔진 모두에 존재했음을 나타냅니다. 조작된 edge-case 입력에 대해 interpreter와 JIT의 동작을 비교하면 남아있는 divergence를 발견할 수 있습니다.

---