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

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

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”字符）是典型的灾难性正则表达式失败。这将需要数万年才能完成（至少使用 Python 或 Perl。awk 不同）。

尝试 3 秒后，它优雅地超时并打印：

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