Reduce impact of parsing crafted templates with repeat tags

[Jake Howard]

The template system uses a regex to extract template tags from text. Given certain inputs, this can take an excessive amount of time:

In [2]: %timeit Template("{%" * 2000)
34.7 ms ± 153 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [3]: %timeit Template("{%" * 10000)
877 ms ± 1.49 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [4]: %timeit Template("{%" * 20000)
3.49 s ± 47 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [5]: %timeit Template("{%")
11.5 µs ± 55.3 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

The cause is excessive backtracking in the ​pattern used. Since the template system is so versatile and performance-critical, fixing the issue appears non-trivial.

Note: This bug was raised with the Security Team prior to opening, however was not deemed a security vulnerability since parsing untrusted (or semi-trusted) templates is ​explicitly warned against.

[Natalia Bidart]

Thank you Jake for taking the time to create this report. Accepting following the conversation within the Security Team.

[Aditya Chaudhary]

Can't we use precompiling a regex pattern to enhance performance by avoiding repeated compilation overhead for frequent matches?

[Jake Howard]

Can't we use precompiling a regex pattern

No, this regex is already compiled before execution (see the linked code above). Repeat compiling isn't the performance hit here, it's the backtracking in the pattern itself.

[Hailey Johnson]

See PR #19360​https://github.com/django/django/pull/19360