python2 re.sub：放弃回溯灾难模式

Question

我使用re.sub() 与一些复杂的模式（由代码创建），可能会导致回溯。

在Python 2.6中经过一定次数的迭代之后，是否有任何实际的方法可以中止re.sub（假设找不到模式或者引发错误）？

样品（这当然是一个愚蠢的模式，但它是由一个复杂的文本处理引擎动态创建的）：

>>>re.sub('[i1l!|](?:[^i1l!|\\w]|[i1l!|])*[l1i!|](?:[^l1i!||\\w]|[l1i!|])*[i1l!|](?:[^i1l!|\\w]|[i1l!|])*[l1i!|](?:[^l1i!||\\w]|[l1i!|])*[i1l!|](?:[^i1l!|\\w]|[i1l!|])*[l1i!|](?:[^l1i!||\\w]|[l1i!|])*[i1l!|](?:[^i1l!|\\w]|[i1l!|])*[l1i!|](?:[^l1i!||\\w]|[l1i!|])*[i1l!|](?:[^i1l!|\\w]|[i1l!|])*[l1i!|](?:[^l1i!||\\w]|[l1i!|])*[i1l!|](?:[^i1l!|\\w]|[i1l!|])*[l1i!|](?:[^l1i!||\\w]|[l1i!|])*[i1l!|](?:[^i1l!|\\w]|[i1l!|])*[l1i!|](?:[^l1i!||\\w]|[l1i!|])*[i1l!|](?:[^i1l!|\\w]|[i1l!|])*[l1i!|](?:[^l1i!||\\w]|[l1i!|])*[i1l!|](?:[^i1l!|\\w]|[i1l!|])*[l1i!|](?:[^l1i!||\\w]|[l1i!|])*[i1l!|](?:[^i1l!|\\w]|[i1l!|])*[l1i!|](?:[^l1i!||\\w]|[l1i!|])*[i1l!|](?:[^i1l!|\\w]|[i1l!|])*[l1i!|](?:[^l1i!||\\w]|[l1i!|])*[i1l!|](?:[^i1l!|\\w]|[i1l!|])*[l1i!|](?:[^l1i!||\\w]|[l1i!|])*[i1l!|](?:[^i1l!|\\w]|[i1l!|])*[l1i!|](?:[^l1i!||\\w]|[l1i!|])*[i1l!|](?:[^i1l!|\\w]|[i1l!|])*[l1i!|](?:[^l1i!||\\w]|[l1i!|])*','*','ilililililililililililililililililililililililililililililililililil :x')

Answer 1

count可以帮助你在这里：

In [9]: re.sub ? 
Type:  function 
Base Class: <type 'function'> 
String Form:<function sub at 0x00AC7CF0> 
Namespace: Interactive 
File:  c:\python27\lib\re.py 
Definition: re.sub(pattern, repl, string, count=0, flags=0) 
Docstring: 
Return the string obtained by replacing the leftmost 
non-overlapping occurrences of the pattern in string by the 
replacement repl. repl can be either a string or a callable; 
if a string, backslash escapes in it are processed. If it is 
a callable, it's passed the match object and must return 
a replacement string to be used. 


In [13]: a = "bbbbbbb" 

In [14]: x = re.sub('b', 'a', a, count=3) 

In [15]: x 
Out[15]: 'aaabbbb' 

Answer 2

比其他分析潜在的灾难性回溯的正则表达式（一个外部正则表达式的难题）或者使用不允许回溯的不同正则表达式引擎，我认为唯一的方法是在这种性质的超时：

import re 
import signal 

class Timeout(Exception): 
    pass 

def try_one(pat,rep,s,t=3): 
    def timeout_handler(signum, frame): 
     raise Timeout() 

    old_handler = signal.signal(signal.SIGALRM, timeout_handler) 
    signal.alarm(t) 

    try: 
     ret=re.sub(pat, rep, s) 

    except Timeout: 
     print('"{}" timed out after {} seconds'.format(pat,t)) 
     return None 

    finally: 
     signal.signal(signal.SIGALRM, old_handler) 

    signal.alarm(0) 
    return ret 

try_one(r'^(.+?)\1+$', r'\1' ,"a" * 1000000 + "b") 

试图代替单个字符的大重复（在这种情况下百万 'A' 的字符）是classic catastrophic regex failure。完成需要几万年的时间（至少在Python或Perl中，awk是不同的）。

的努力，超时摆好3秒钟，打印完毕后：

"^(.+?)\1+$" timed out after 3 seconds