катастрофическое регулярное выражение при сопоставлении вложенного пути в Django

Question

У меня есть иерархическая структура данных в Django, и я хочу сопоставить путь к объекту в шаблоне URL Django.Вот мой шаблон:

url(r'^products/(?P<path>(?:[-\w]+\/?)+)/$',
    CategoriesListView.as_view(model=Product),
    name='product_categories_list'
),

Цель состоит в том, чтобы соответствовать весь путь, но без косой черты.Проблема в том, что при определенных входных данных это регулярное выражение полностью ухудшается в производительности.Основная проблема, кажется, строки, которые содержат точку:

In [1]: import re

In [2]: s = re.compile(r'^products/(?P<path>(?:[-\w]+/?)+)/$')

In [3]: s.search('products/111111111111111111111111.c')

Это занимает около 5 секунд.Увеличение длины строки приводит к экспоненциальному росту времени выполнения.

Как мне переписать это регулярное выражение, чтобы оно все еще совпадало с теми же строками, но не съедало мой процессор на завтрак?

Answer 1

Вы можете написать:

r'^products/(?P<path>[-\w/]+)/$'

, который соответствует тому же набору строк , за исключением , что он не применяет запрет на нетерминал //. Если этот запрет важен, вы можете написать:

r'^products(?!.*//.)/(?P<path>[-\w/]+)/$'

, который использует отрицательное прогнозное утверждение для обеспечения соблюдения этого запрета более дешевым способом.