이 정규 표현식을 "치명적인 역 추적"으로 만들지 못하게하려면 어떻게해야합니까?

Question

은 내가 another question에 대한 답변을 바탕으로 http://daringfireball.net/2010/07/improved_regex_for_matching_urls

(?xi) 
\b 
(      # Capture 1: entire matched URL 
    (?: 
    https?://    # http or https protocol 
    |      # or 
    www\d{0,3}[.]   # "www.", "www1.", "www2." … "www999." 
    |       # or 
    [a-z0-9.\-]+[.][a-z]{2,4}/ # looks like domain name followed by a slash 
) 
    (?:      # One or more: 
    [^\s()<>]+     # Run of non-space, non-()<> 
    |       # or 
    \(([^\s()<>]+|(\([^\s()<>]+\)))*\) # balanced parens, up to 2 levels 
)+ 
    (?:      # End with: 
    \(([^\s()<>]+|(\([^\s()<>]+\)))*\) # balanced parens, up to 2 levels 
    |        # or 
    [^\s`!()\[\]{};:'".,<>?«»“”‘’]  # not a space or one of these punct chars 
) 
) 

에서 가져온 정규 표현식과 일치하는 URL을 사용하기 위해 노력하고있어, backtrack catastrophically이 정규식을 일으킬 경우가 나타납니다. 예를 들어 :

(?:      # One or more: 
    [^\s()<>]+     # Run of non-space, non-()<> 
    |       # or 
    \(([^\s()<>]+|(\([^\s()<>]+\)))*\) # balanced parens, up to 2 levels 
)+ 

:

var re = /\b((?:https?:\/\/|www\d{0,3}[.]|[a-z0-9.\-]+[.][a-z]{2,4}\/)(?:[^\s()<>]+|\(([^\s()<>]+|(\([^\s()<>]+\)))*\))+(?:\(([^\s()<>]+|(\([^\s()<>]+\)))*\)|[^\s`!()\[\]{};:'".,<>?«»“”‘’]))/i; 
re.test("http://google.com/?q=(AAAAAAAAAAAAAAAAAAAAAAAAAAAAA)") 

는

는 ... 문제가 코드의이 부분에 있다고

이 날 것으로 보인다 (크롬 등)을 실행하기 위해 정말 시간이 오래 걸릴 수 있습니다

은 ... 어떤은 (.+)+

을 포함처럼 나는 그 것을 피할 수 변화가 보이는, (.+|\((.+|(\(.+\)))*\))+ 거의 비슷 것으로 보인다?

Answer 1

이하로 변경하면 치명적인 역행 방지해야

(?xi) 
\b 
(      # Capture 1: entire matched URL 
    (?: 
    https?://    # http or https protocol 
    |      # or 
    www\d{0,3}[.]   # "www.", "www1.", "www2." … "www999." 
    |       # or 
    [a-z0-9.\-]+[.][a-z]{2,4}/ # looks like domain name followed by a slash 
) 
    (?:      # One or more: 
    [^\s()<>]+     # Run of non-space, non-()<> 
    |       # or 
    \(([^\s()<>]|(\([^\s()<>]+\)))*\) # balanced parens, up to 2 levels 
)+ 
    (?:      # End with: 
    \(([^\s()<>]|(\([^\s()<>]+\)))*\) # balanced parens, up to 2 levels 
    |        # or 
    [^\s`!()\[\]{};:'".,<>?«»“”‘’]  # not a space or one of these punct chars 
) 
) 

은 "균형 괄호"정규식의 부분들 각각의 제 [^\s()<>] 후 + 제거 하였다되었다 유일한 변화.

var re = /\b((?:https?:\/\/|www\d{0,3}[.]|[a-z0-9.\-]+[.][a-z]{2,4}\/)(?:[^\s()<>]+|\(([^\s()<>]|(\([^\s()<>]+\)))*\))+(?:\(([^\s()<>]|(\([^\s()<>]+\)))*\)|[^\s`!()\[\]{};:'".,<>?«»“”‘’]))/i; 
re.test("http://google.com/?q=(AAAAAAAAAAAAAAAAAAAAAAAAAAAAA") 

원래 정규식의 문제 부분은 균형 잡힌 괄호 섹션의 역행 내가 완전히에 갈거야 발생하는 이유에 대한 설명을 단순화하기 : 여기

은 JS와 테스트를위한 한 줄 버전입니다 여기에 관련이없는 때문에 그것의 중첩 된 괄호 부분을 제거합니다

\(([^\s()<>]+|(\([^\s()<>]+\)))*\) # original 
\(([^\s()<>]+)*\)      # expanded below 

\(    # literal '(' 
(    # start group, repeat zero or more times 
    [^\s()<>]+  # one or more non-special characters 
)*    # end group 
\)    # literal ')' 

문자열 '(AAAAA' 여기 무슨 일 고려, 문자 그대로 (이 일치하고것 그룹에 의해이 소비되고 )이 일치하지 않습니다. 이 시점에서 그룹은 A을 포기하고 AAAA을 붙잡고이 시점에서 경기를 계속하려고 시도합니다. 그룹에이어서 *이 있으므로 그룹이 여러 번 일치 할 수 있으므로 ([^\s()<>]+)*이 AAAA과 일치하고 두 번째 패스에서 A이됩니다. 이것이 실패 할 때 추가 A은 원래 캡처에 의해 포기되고 두 번째 캡처에 의해 소비됩니다.

이 위해에 갈 것이라고 긴 인스턴스가 일치하는 다음 각 쉼표로 구분 된 그룹이 그룹이 일치하는 다른 시간을 나타냅니다 일치하도록 시도하고있는 문자의 결과로 동안 :

AAAAA 
AAAA, A 
AAA, AA 
AAA, A, A 
AA, AAA 
AA, AA, A 
AA, A, AA 
AA, A, A, A 
.... 

내가 잘못 계산했을 수도 있지만 정규식이 일치하지 않는다고 판단되기 전에 최대 16 단계를 추가한다고 확신합니다. 문자열에 추가 문자를 계속 추가하면이를 계산하는 단계가 기하 급수적으로 늘어납니다.

+을 제거하고 이것을 \(([^\s()<>])*\)으로 변경하면이 역 추적 시나리오를 피할 수 있습니다.

중첩 된 괄호를 확인하기 위해 교대를 다시 추가해도 문제가 발생하지 않습니다. 현재 "http://google.com/?q=(AAAAAAAAAAAAAAAAAAAAAAAAAAAAA" 방금 ​​전에 (에 일치하기 때문에 당신은 문자열의 끝 앵커의 어떤 종류를 추가 할 수 있습니다

주, 그래서 re.test(...)는 truehttp://google.com/?q= 때문에 일치하는 항목을 반환합니다.